1 /*
2 * LZ4 - Fast LZ compression algorithm
3 * Header File
4 * Copyright (C) 2011-2013, Yann Collet.
5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are
9 * met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following disclaimer
15 * in the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 *
30 * You can contact the author at :
31 * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
32 * - LZ4 source repository : http://code.google.com/p/lz4/
33 * Upstream release : r91
34 */
35
36 #include <sys/zfs_context.h>
37
38 static int real_LZ4_compress(const char *source, char *dest, int isize,
39 int osize);
40 static int LZ4_compressBound(int isize);
41 static int LZ4_uncompress_unknownOutputSize(const char *source, char *dest,
42 int isize, int maxOutputSize);
43 static int LZ4_compressCtx(void *ctx, const char *source, char *dest,
44 int isize, int osize);
45 static int LZ4_compress64kCtx(void *ctx, const char *source, char *dest,
46 int isize, int osize);
47
48 /*ARGSUSED*/
49 size_t
50 lz4_compress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n)
51 {
52 uint32_t bufsiz;
53 char *dest = d_start;
54
55 ASSERT(d_len >= sizeof (bufsiz));
56
57 bufsiz = real_LZ4_compress(s_start, &dest[sizeof (bufsiz)], s_len,
58 d_len - sizeof (bufsiz));
59
60 /* Signal an error if the compression routine returned zero. */
61 if (bufsiz == 0)
62 return (s_len);
63
64 /*
65 * Encode the compresed buffer size at the start. We'll need this in
66 * decompression to counter the effects of padding which might be
67 * added to the compressed buffer and which, if unhandled, would
68 * confuse the hell out of our decompression function.
69 */
70 *(uint32_t *)dest = BE_32(bufsiz);
71
72 return (bufsiz + sizeof (bufsiz));
73 }
74
75 /*ARGSUSED*/
76 int
77 lz4_decompress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n)
78 {
79 const char *src = s_start;
80 uint32_t bufsiz = BE_IN32(src);
81
82 /* invalid compressed buffer size encoded at start */
83 if (bufsiz + sizeof (bufsiz) > s_len)
84 return (1);
85
86 /*
87 * Returns 0 on success (decompression function returned non-negative)
88 * and non-zero on failure (decompression function returned negative.
89 */
90 return (LZ4_uncompress_unknownOutputSize(&src[sizeof (bufsiz)],
91 d_start, bufsiz, d_len) < 0);
92 }
93
94 /*
95 * LZ4 API Description:
96 *
97 * Simple Functions:
98 * real_LZ4_compress() :
99 * isize : is the input size. Max supported value is ~1.9GB
100 * return : the number of bytes written in buffer dest
101 * or 0 if the compression fails (if LZ4_COMPRESSMIN is set).
102 * note : destination buffer must be already allocated.
103 * destination buffer must be sized to handle worst cases
104 * situations (input data not compressible) worst case size
105 * evaluation is provided by function LZ4_compressBound().
106 *
107 * Advanced Functions
108 *
109 * LZ4_compressBound() :
110 * Provides the maximum size that LZ4 may output in a "worst case"
111 * scenario (input data not compressible) primarily useful for memory
112 * allocation of output buffer.
113 *
114 * isize : is the input size. Max supported value is ~1.9GB
115 * return : maximum output size in a "worst case" scenario
116 * note : this function is limited by "int" range (2^31-1)
117 *
118 * LZ4_uncompress_unknownOutputSize() :
119 * isize : is the input size, therefore the compressed size
120 * maxOutputSize : is the size of the destination buffer (which must be
121 * already allocated)
122 * return : the number of bytes decoded in the destination buffer
123 * (necessarily <= maxOutputSize). If the source stream is
124 * malformed, the function will stop decoding and return a
125 * negative result, indicating the byte position of the faulty
126 * instruction. This function never writes beyond dest +
127 * maxOutputSize, and is therefore protected against malicious
128 * data packets.
129 * note : Destination buffer must be already allocated.
130 *
131 * LZ4_compressCtx() :
132 * This function explicitly handles the CTX memory structure.
133 *
134 * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
135 * by the caller (either on the stack or using kmem_zalloc). Passing NULL
136 * isn't valid.
137 *
138 * LZ4_compress64kCtx() :
139 * Same as LZ4_compressCtx(), but specific to small inputs (<64KB).
140 * isize *Must* be <64KB, otherwise the output will be corrupted.
141 *
142 * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
143 * by the caller (either on the stack or using kmem_zalloc). Passing NULL
144 * isn't valid.
145 */
146
147 /*
148 * Tuning parameters
149 */
150
151 /*
152 * COMPRESSIONLEVEL: Increasing this value improves compression ratio
153 * Lowering this value reduces memory usage. Reduced memory usage
154 * typically improves speed, due to cache effect (ex: L1 32KB for Intel,
155 * L1 64KB for AMD). Memory usage formula : N->2^(N+2) Bytes
156 * (examples : 12 -> 16KB ; 17 -> 512KB)
157 */
158 #define COMPRESSIONLEVEL 12
159
160 /*
161 * NOTCOMPRESSIBLE_CONFIRMATION: Decreasing this value will make the
162 * algorithm skip faster data segments considered "incompressible".
163 * This may decrease compression ratio dramatically, but will be
164 * faster on incompressible data. Increasing this value will make
165 * the algorithm search more before declaring a segment "incompressible".
166 * This could improve compression a bit, but will be slower on
167 * incompressible data. The default value (6) is recommended.
168 */
169 #define NOTCOMPRESSIBLE_CONFIRMATION 6
170
171 /*
172 * BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE: This will provide a boost to
173 * performance for big endian cpu, but the resulting compressed stream
174 * will be incompatible with little-endian CPU. You can set this option
175 * to 1 in situations where data will stay within closed environment.
176 * This option is useless on Little_Endian CPU (such as x86).
177 */
178 /* #define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1 */
179
180 /*
181 * CPU Feature Detection
182 */
183
184 /* 32 or 64 bits ? */
185 #if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || \
186 defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || \
187 defined(__LP64__) || defined(_LP64))
188 #define LZ4_ARCH64 1
189 #else
190 #define LZ4_ARCH64 0
191 #endif
192
193 /*
194 * Limits the amount of stack space that the algorithm may consume to hold
195 * the compression lookup table. The value `9' here means we'll never use
196 * more than 2k of stack (see above for a description of COMPRESSIONLEVEL).
197 * If more memory is needed, it is allocated from the heap.
198 */
199 #define STACKLIMIT 9
200
201 /*
202 * Little Endian or Big Endian?
203 * Note: overwrite the below #define if you know your architecture endianess.
204 */
205 #if (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || \
206 defined(_BIG_ENDIAN) || defined(_ARCH_PPC) || defined(__PPC__) || \
207 defined(__PPC) || defined(PPC) || defined(__powerpc__) || \
208 defined(__powerpc) || defined(powerpc) || \
209 ((defined(__BYTE_ORDER__)&&(__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__))))
210 #define LZ4_BIG_ENDIAN 1
211 #else
212 /*
213 * Little Endian assumed. PDP Endian and other very rare endian format
214 * are unsupported.
215 */
216 #endif
217
218 /*
219 * Unaligned memory access is automatically enabled for "common" CPU,
220 * such as x86. For others CPU, the compiler will be more cautious, and
221 * insert extra code to ensure aligned access is respected. If you know
222 * your target CPU supports unaligned memory access, you may want to
223 * force this option manually to improve performance
224 */
225 #if defined(__ARM_FEATURE_UNALIGNED)
226 #define LZ4_FORCE_UNALIGNED_ACCESS 1
227 #endif
228
229 /* #define LZ4_FORCE_SW_BITCOUNT */
230
231 /*
232 * Compiler Options
233 */
234 #if __STDC_VERSION__ >= 199901L /* C99 */
235 /* "restrict" is a known keyword */
236 #else
237 /* Disable restrict */
238 #define restrict
239 #endif
240
241 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
242
243 #ifdef _MSC_VER
244 /* Visual Studio */
245 /* Visual is not C99, but supports some kind of inline */
246 #define inline __forceinline
247 #if LZ4_ARCH64
248 /* For Visual 2005 */
249 #pragma intrinsic(_BitScanForward64)
250 #pragma intrinsic(_BitScanReverse64)
251 #else /* !LZ4_ARCH64 */
252 /* For Visual 2005 */
253 #pragma intrinsic(_BitScanForward)
254 #pragma intrinsic(_BitScanReverse)
255 #endif /* !LZ4_ARCH64 */
256 #endif /* _MSC_VER */
257
258 #ifdef _MSC_VER
259 #define lz4_bswap16(x) _byteswap_ushort(x)
260 #else /* !_MSC_VER */
261 #define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | \
262 (((x) & 0xffu) << 8)))
263 #endif /* !_MSC_VER */
264
265 #if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)
266 #define expect(expr, value) (__builtin_expect((expr), (value)))
267 #else
268 #define expect(expr, value) (expr)
269 #endif
270
271 #define likely(expr) expect((expr) != 0, 1)
272 #define unlikely(expr) expect((expr) != 0, 0)
273
274 /* Basic types */
275 #if defined(_MSC_VER)
276 /* Visual Studio does not support 'stdint' natively */
277 #define BYTE unsigned __int8
278 #define U16 unsigned __int16
279 #define U32 unsigned __int32
280 #define S32 __int32
281 #define U64 unsigned __int64
282 #else /* !defined(_MSC_VER) */
283 #define BYTE uint8_t
284 #define U16 uint16_t
285 #define U32 uint32_t
286 #define S32 int32_t
287 #define U64 uint64_t
288 #endif /* !defined(_MSC_VER) */
289
290 #ifndef LZ4_FORCE_UNALIGNED_ACCESS
291 #pragma pack(1)
292 #endif
293
294 typedef struct _U16_S {
295 U16 v;
296 } U16_S;
297 typedef struct _U32_S {
298 U32 v;
299 } U32_S;
300 typedef struct _U64_S {
301 U64 v;
302 } U64_S;
303
304 #ifndef LZ4_FORCE_UNALIGNED_ACCESS
305 #pragma pack()
306 #endif
307
308 #define A64(x) (((U64_S *)(x))->v)
309 #define A32(x) (((U32_S *)(x))->v)
310 #define A16(x) (((U16_S *)(x))->v)
311
312 /*
313 * Constants
314 */
315 #define MINMATCH 4
316
317 #define HASH_LOG COMPRESSIONLEVEL
318 #define HASHTABLESIZE (1 << HASH_LOG)
319 #define HASH_MASK (HASHTABLESIZE - 1)
320
321 #define SKIPSTRENGTH (NOTCOMPRESSIBLE_CONFIRMATION > 2 ? \
322 NOTCOMPRESSIBLE_CONFIRMATION : 2)
323
324 /*
325 * Defines if memory is allocated into the stack (local variable),
326 * or into the heap (kmem_alloc()).
327 */
328 #define HEAPMODE (HASH_LOG > STACKLIMIT)
329 #define COPYLENGTH 8
330 #define LASTLITERALS 5
331 #define MFLIMIT (COPYLENGTH + MINMATCH)
332 #define MINLENGTH (MFLIMIT + 1)
333
334 #define MAXD_LOG 16
335 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
336
337 #define ML_BITS 4
338 #define ML_MASK ((1U<<ML_BITS)-1)
339 #define RUN_BITS (8-ML_BITS)
340 #define RUN_MASK ((1U<<RUN_BITS)-1)
341
342
343 /*
344 * Architecture-specific macros
345 */
346 #if LZ4_ARCH64
347 #define STEPSIZE 8
348 #define UARCH U64
349 #define AARCH A64
350 #define LZ4_COPYSTEP(s, d) A64(d) = A64(s); d += 8; s += 8;
351 #define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d)
352 #define LZ4_SECURECOPY(s, d, e) if (d < e) LZ4_WILDCOPY(s, d, e)
353 #define HTYPE U32
354 #define INITBASE(base) const BYTE* const base = ip
355 #else /* !LZ4_ARCH64 */
356 #define STEPSIZE 4
357 #define UARCH U32
358 #define AARCH A32
359 #define LZ4_COPYSTEP(s, d) A32(d) = A32(s); d += 4; s += 4;
360 #define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d); LZ4_COPYSTEP(s, d);
361 #define LZ4_SECURECOPY LZ4_WILDCOPY
362 #define HTYPE const BYTE *
363 #define INITBASE(base) const int base = 0
364 #endif /* !LZ4_ARCH64 */
365
366 #if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE))
367 #define LZ4_READ_LITTLEENDIAN_16(d, s, p) \
368 { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }
369 #define LZ4_WRITE_LITTLEENDIAN_16(p, i) \
370 { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p += 2; }
371 #else
372 #define LZ4_READ_LITTLEENDIAN_16(d, s, p) { d = (s) - A16(p); }
373 #define LZ4_WRITE_LITTLEENDIAN_16(p, v) { A16(p) = v; p += 2; }
374 #endif
375
376
377 /* Local structures */
378 struct refTables {
379 HTYPE hashTable[HASHTABLESIZE];
380 };
381
382
383 /* Macros */
384 #define LZ4_HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH * 8) - \
385 HASH_LOG))
386 #define LZ4_HASH_VALUE(p) LZ4_HASH_FUNCTION(A32(p))
387 #define LZ4_WILDCOPY(s, d, e) do { LZ4_COPYPACKET(s, d) } while (d < e);
388 #define LZ4_BLINDCOPY(s, d, l) { BYTE* e = (d) + l; LZ4_WILDCOPY(s, d, e); \
389 d = e; }
390
391
392 /* Private functions */
393 #if LZ4_ARCH64
394
395 static inline int
396 LZ4_NbCommonBytes(register U64 val)
397 {
398 #if defined(LZ4_BIG_ENDIAN)
399 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
400 unsigned long r = 0;
401 _BitScanReverse64(&r, val);
402 return (int)(r >> 3);
403 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && \
404 !defined(LZ4_FORCE_SW_BITCOUNT)
405 return (__builtin_clzll(val) >> 3);
406 #else
407 int r;
408 if (!(val >> 32)) {
409 r = 4;
410 } else {
411 r = 0;
412 val >>= 32;
413 }
414 if (!(val >> 16)) {
415 r += 2;
416 val >>= 8;
417 } else {
418 val >>= 24;
419 }
420 r += (!val);
421 return (r);
422 #endif
423 #else
424 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
425 unsigned long r = 0;
426 _BitScanForward64(&r, val);
427 return (int)(r >> 3);
428 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && \
429 !defined(LZ4_FORCE_SW_BITCOUNT)
430 return (__builtin_ctzll(val) >> 3);
431 #else
432 static const int DeBruijnBytePos[64] =
433 { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5,
434 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5,
435 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4,
436 4, 5, 7, 2, 6, 5, 7, 6, 7, 7
437 };
438 return DeBruijnBytePos[((U64) ((val & -val) * 0x0218A392CDABBD3F)) >>
439 58];
440 #endif
441 #endif
442 }
443
444 #else
445
446 static inline int
447 LZ4_NbCommonBytes(register U32 val)
448 {
449 #if defined(LZ4_BIG_ENDIAN)
450 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
451 unsigned long r = 0;
452 _BitScanReverse(&r, val);
453 return (int)(r >> 3);
454 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && \
455 !defined(LZ4_FORCE_SW_BITCOUNT)
456 return (__builtin_clz(val) >> 3);
457 #else
458 int r;
459 if (!(val >> 16)) {
460 r = 2;
461 val >>= 8;
462 } else {
463 r = 0;
464 val >>= 24;
465 }
466 r += (!val);
467 return (r);
468 #endif
469 #else
470 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
471 unsigned long r = 0;
472 _BitScanForward(&r, val);
473 return (int)(r >> 3);
474 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && \
475 !defined(LZ4_FORCE_SW_BITCOUNT)
476 return (__builtin_ctz(val) >> 3);
477 #else
478 static const int DeBruijnBytePos[32] = {
479 0, 0, 3, 0, 3, 1, 3, 0,
480 3, 2, 2, 1, 3, 2, 0, 1,
481 3, 3, 1, 2, 2, 2, 2, 0,
482 3, 1, 2, 0, 1, 0, 1, 1
483 };
484 return DeBruijnBytePos[((U32) ((val & -(S32) val) * 0x077CB531U)) >>
485 27];
486 #endif
487 #endif
488 }
489
490 #endif
491
492 /* Public functions */
493
494 static int
495 LZ4_compressBound(int isize)
496 {
497 return (isize + (isize / 255) + 16);
498 }
499
500 /* Compression functions */
501
502 /*ARGSUSED*/
503 static int
504 LZ4_compressCtx(void *ctx, const char *source, char *dest, int isize,
505 int osize)
506 {
507 #if HEAPMODE
508 struct refTables *srt = (struct refTables *)ctx;
509 HTYPE *HashTable = (HTYPE *) (srt->hashTable);
510 #else
511 HTYPE HashTable[HASHTABLESIZE] = { 0 };
512 #endif
513
514 const BYTE *ip = (BYTE *) source;
515 INITBASE(base);
516 const BYTE *anchor = ip;
517 const BYTE *const iend = ip + isize;
518 const BYTE *const oend = (BYTE *) dest + osize;
519 const BYTE *const mflimit = iend - MFLIMIT;
520 #define matchlimit (iend - LASTLITERALS)
521
522 BYTE *op = (BYTE *) dest;
523
524 int length;
525 const int skipStrength = SKIPSTRENGTH;
526 U32 forwardH;
527
528
529 /* Init */
530 if (isize < MINLENGTH)
531 goto _last_literals;
532
533 /* First Byte */
534 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
535 ip++;
536 forwardH = LZ4_HASH_VALUE(ip);
537
538 /* Main Loop */
539 for (;;) {
540 int findMatchAttempts = (1U << skipStrength) + 3;
541 const BYTE *forwardIp = ip;
542 const BYTE *ref;
543 BYTE *token;
544
545 /* Find a match */
546 do {
547 U32 h = forwardH;
548 int step = findMatchAttempts++ >> skipStrength;
549 ip = forwardIp;
550 forwardIp = ip + step;
551
552 if unlikely(forwardIp > mflimit) {
553 goto _last_literals;
554 }
555
556 forwardH = LZ4_HASH_VALUE(forwardIp);
557 ref = base + HashTable[h];
558 HashTable[h] = ip - base;
559
560 } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));
561
562 /* Catch up */
563 while ((ip > anchor) && (ref > (BYTE *) source) &&
564 unlikely(ip[-1] == ref[-1])) {
565 ip--;
566 ref--;
567 }
568
569 /* Encode Literal length */
570 length = ip - anchor;
571 token = op++;
572
573 /* Check output limit */
574 if unlikely(op + length + (2 + 1 + LASTLITERALS) +
575 (length >> 8) > oend)
576 return (0);
577
578 if (length >= (int)RUN_MASK) {
579 int len;
580 *token = (RUN_MASK << ML_BITS);
581 len = length - RUN_MASK;
582 for (; len > 254; len -= 255)
583 *op++ = 255;
584 *op++ = (BYTE)len;
585 } else
586 *token = (length << ML_BITS);
587
588 /* Copy Literals */
589 LZ4_BLINDCOPY(anchor, op, length);
590
591 _next_match:
592 /* Encode Offset */
593 LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);
594
595 /* Start Counting */
596 ip += MINMATCH;
597 ref += MINMATCH; /* MinMatch already verified */
598 anchor = ip;
599 while likely(ip < matchlimit - (STEPSIZE - 1)) {
600 UARCH diff = AARCH(ref) ^ AARCH(ip);
601 if (!diff) {
602 ip += STEPSIZE;
603 ref += STEPSIZE;
604 continue;
605 }
606 ip += LZ4_NbCommonBytes(diff);
607 goto _endCount;
608 }
609 #if LZ4_ARCH64
610 if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
611 ip += 4;
612 ref += 4;
613 }
614 #endif
615 if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
616 ip += 2;
617 ref += 2;
618 }
619 if ((ip < matchlimit) && (*ref == *ip))
620 ip++;
621 _endCount:
622
623 /* Encode MatchLength */
624 length = (int)(ip - anchor);
625 /* Check output limit */
626 if unlikely(op + (1 + LASTLITERALS) + (length >> 8) > oend)
627 return (0);
628 if (length >= (int)ML_MASK) {
629 *token += ML_MASK;
630 length -= ML_MASK;
631 for (; length > 509; length -= 510) {
632 *op++ = 255;
633 *op++ = 255;
634 }
635 if (length > 254) {
636 length -= 255;
637 *op++ = 255;
638 }
639 *op++ = (BYTE)length;
640 } else
641 *token += length;
642
643 /* Test end of chunk */
644 if (ip > mflimit) {
645 anchor = ip;
646 break;
647 }
648 /* Fill table */
649 HashTable[LZ4_HASH_VALUE(ip - 2)] = ip - 2 - base;
650
651 /* Test next position */
652 ref = base + HashTable[LZ4_HASH_VALUE(ip)];
653 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
654 if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) {
655 token = op++;
656 *token = 0;
657 goto _next_match;
658 }
659 /* Prepare next loop */
660 anchor = ip++;
661 forwardH = LZ4_HASH_VALUE(ip);
662 }
663
664 _last_literals:
665 /* Encode Last Literals */
666 {
667 int lastRun = iend - anchor;
668 if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) >
669 oend)
670 return (0);
671 if (lastRun >= (int)RUN_MASK) {
672 *op++ = (RUN_MASK << ML_BITS);
673 lastRun -= RUN_MASK;
674 for (; lastRun > 254; lastRun -= 255) {
675 *op++ = 255;
676 }
677 *op++ = (BYTE)lastRun;
678 } else
679 *op++ = (lastRun << ML_BITS);
680 (void) memcpy(op, anchor, iend - anchor);
681 op += iend - anchor;
682 }
683
684 /* End */
685 return (int)(((char *)op) - dest);
686 }
687
688
689
690 /* Note : this function is valid only if isize < LZ4_64KLIMIT */
691 #define LZ4_64KLIMIT ((1 << 16) + (MFLIMIT - 1))
692 #define HASHLOG64K (HASH_LOG + 1)
693 #define HASH64KTABLESIZE (1U << HASHLOG64K)
694 #define LZ4_HASH64K_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8) - \
695 HASHLOG64K))
696 #define LZ4_HASH64K_VALUE(p) LZ4_HASH64K_FUNCTION(A32(p))
697
698 /*ARGSUSED*/
699 static int
700 LZ4_compress64kCtx(void *ctx, const char *source, char *dest, int isize,
701 int osize)
702 {
703 #if HEAPMODE
704 struct refTables *srt = (struct refTables *)ctx;
705 U16 *HashTable = (U16 *) (srt->hashTable);
706 #else
707 U16 HashTable[HASH64KTABLESIZE] = { 0 };
708 #endif
709
710 const BYTE *ip = (BYTE *) source;
711 const BYTE *anchor = ip;
712 const BYTE *const base = ip;
713 const BYTE *const iend = ip + isize;
714 const BYTE *const oend = (BYTE *) dest + osize;
715 const BYTE *const mflimit = iend - MFLIMIT;
716 #define matchlimit (iend - LASTLITERALS)
717
718 BYTE *op = (BYTE *) dest;
719
720 int len, length;
721 const int skipStrength = SKIPSTRENGTH;
722 U32 forwardH;
723
724 /* Init */
725 if (isize < MINLENGTH)
726 goto _last_literals;
727
728 /* First Byte */
729 ip++;
730 forwardH = LZ4_HASH64K_VALUE(ip);
731
732 /* Main Loop */
733 for (;;) {
734 int findMatchAttempts = (1U << skipStrength) + 3;
735 const BYTE *forwardIp = ip;
736 const BYTE *ref;
737 BYTE *token;
738
739 /* Find a match */
740 do {
741 U32 h = forwardH;
742 int step = findMatchAttempts++ >> skipStrength;
743 ip = forwardIp;
744 forwardIp = ip + step;
745
746 if (forwardIp > mflimit) {
747 goto _last_literals;
748 }
749
750 forwardH = LZ4_HASH64K_VALUE(forwardIp);
751 ref = base + HashTable[h];
752 HashTable[h] = ip - base;
753
754 } while (A32(ref) != A32(ip));
755
756 /* Catch up */
757 while ((ip > anchor) && (ref > (BYTE *) source) &&
758 (ip[-1] == ref[-1])) {
759 ip--;
760 ref--;
761 }
762
763 /* Encode Literal length */
764 length = ip - anchor;
765 token = op++;
766
767 /* Check output limit */
768 if unlikely(op + length + (2 + 1 + LASTLITERALS) +
769 (length >> 8) > oend)
770 return (0);
771
772 if (length >= (int)RUN_MASK) {
773 *token = (RUN_MASK << ML_BITS);
774 len = length - RUN_MASK;
775 for (; len > 254; len -= 255)
776 *op++ = 255;
777 *op++ = (BYTE)len;
778 } else
779 *token = (length << ML_BITS);
780
781 /* Copy Literals */
782 LZ4_BLINDCOPY(anchor, op, length);
783
784 _next_match:
785 /* Encode Offset */
786 LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);
787
788 /* Start Counting */
789 ip += MINMATCH;
790 ref += MINMATCH; /* MinMatch verified */
791 anchor = ip;
792 while (ip < matchlimit - (STEPSIZE - 1)) {
793 UARCH diff = AARCH(ref) ^ AARCH(ip);
794 if (!diff) {
795 ip += STEPSIZE;
796 ref += STEPSIZE;
797 continue;
798 }
799 ip += LZ4_NbCommonBytes(diff);
800 goto _endCount;
801 }
802 #if LZ4_ARCH64
803 if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
804 ip += 4;
805 ref += 4;
806 }
807 #endif
808 if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
809 ip += 2;
810 ref += 2;
811 }
812 if ((ip < matchlimit) && (*ref == *ip))
813 ip++;
814 _endCount:
815
816 /* Encode MatchLength */
817 len = (ip - anchor);
818 /* Check output limit */
819 if unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend)
820 return (0);
821 if (len >= (int)ML_MASK) {
822 *token += ML_MASK;
823 len -= ML_MASK;
824 for (; len > 509; len -= 510) {
825 *op++ = 255;
826 *op++ = 255;
827 }
828 if (len > 254) {
829 len -= 255;
830 *op++ = 255;
831 }
832 *op++ = (BYTE)len;
833 } else
834 *token += len;
835
836 /* Test end of chunk */
837 if (ip > mflimit) {
838 anchor = ip;
839 break;
840 }
841 /* Fill table */
842 HashTable[LZ4_HASH64K_VALUE(ip - 2)] = ip - 2 - base;
843
844 /* Test next position */
845 ref = base + HashTable[LZ4_HASH64K_VALUE(ip)];
846 HashTable[LZ4_HASH64K_VALUE(ip)] = ip - base;
847 if (A32(ref) == A32(ip)) {
848 token = op++;
849 *token = 0;
850 goto _next_match;
851 }
852 /* Prepare next loop */
853 anchor = ip++;
854 forwardH = LZ4_HASH64K_VALUE(ip);
855 }
856
857 _last_literals:
858 /* Encode Last Literals */
859 {
860 int lastRun = iend - anchor;
861 if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) >
862 oend)
863 return (0);
864 if (lastRun >= (int)RUN_MASK) {
865 *op++ = (RUN_MASK << ML_BITS);
866 lastRun -= RUN_MASK;
867 for (; lastRun > 254; lastRun -= 255)
868 *op++ = 255;
869 *op++ = (BYTE)lastRun;
870 } else
871 *op++ = (lastRun << ML_BITS);
872 (void) memcpy(op, anchor, iend - anchor);
873 op += iend - anchor;
874 }
875
876 /* End */
877 return (int)(((char *)op) - dest);
878 }
879
880 static int
881 real_LZ4_compress(const char *source, char *dest, int isize, int osize)
882 {
883 #if HEAPMODE
884 void *ctx = kmem_zalloc(sizeof (struct refTables), KM_NOSLEEP);
885 int result;
886
887 /*
888 * out of kernel memory, gently fall through - this will disable
889 * compression in zio_compress_data
890 */
891 if (ctx == NULL)
892 return (0);
893
894 if (isize < LZ4_64KLIMIT)
895 result = LZ4_compress64kCtx(ctx, source, dest, isize, osize);
896 else
897 result = LZ4_compressCtx(ctx, source, dest, isize, osize);
898
899 kmem_free(ctx, sizeof (struct refTables));
900 return (result);
901 #else
902 if (isize < (int)LZ4_64KLIMIT)
903 return (LZ4_compress64kCtx(NULL, source, dest, isize, osize));
904 return (LZ4_compressCtx(NULL, source, dest, isize, osize));
905 #endif
906 }
907
908 /* Decompression functions */
909
910 static int
911 LZ4_uncompress_unknownOutputSize(const char *source, char *dest, int isize,
912 int maxOutputSize)
913 {
914 /* Local Variables */
915 const BYTE *restrict ip = (const BYTE *) source;
916 const BYTE *const iend = ip + isize;
917 const BYTE *ref;
918
919 BYTE *op = (BYTE *) dest;
920 BYTE *const oend = op + maxOutputSize;
921 BYTE *cpy;
922
923 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
924 #if LZ4_ARCH64
925 size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
926 #endif
927
928 /*
929 * Special case
930 * A correctly formed null-compressed LZ4 must have at least
931 * one byte (token=0)
932 */
933 if (unlikely(ip == iend))
934 goto _output_error;
935
936 /* Main Loop */
937 /*LINTED E_CONSTANT_CONDITION*/
938 while (1) {
939 unsigned token;
940 size_t length;
941
942 /* get runlength */
943 token = *ip++;
944 if ((length = (token >> ML_BITS)) == RUN_MASK) {
945 int s = 255;
946 while ((ip < iend) && (s == 255)) {
947 s = *ip++;
948 length += s;
949 }
950 }
951 /* copy literals */
952 cpy = op + length;
953 if ((cpy > oend - MFLIMIT) ||
954 (ip + length > iend - (2 + 1 + LASTLITERALS))) {
955 if (cpy > oend)
956 /* Error: writes beyond output buffer */
957 goto _output_error;
958 if (ip + length != iend)
959 /*
960 * Error: LZ4 format requires to consume all
961 * input at this stage (no match within the
962 * last 11 bytes, and at least 8 remaining
963 * input bytes for another match + literals
964 */
965 goto _output_error;
966 (void) memcpy(op, ip, length);
967 op += length;
968 /* Necessarily EOF, due to parsing restrictions */
969 break;
970 }
971 LZ4_WILDCOPY(ip, op, cpy);
972 ip -= (op - cpy);
973 op = cpy;
974
975 /* get offset */
976 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
977 ip += 2;
978 if (unlikely(ref < (BYTE * const) dest))
979 /*
980 * Error: offset creates reference outside of
981 * destination buffer
982 */
983 goto _output_error;
984
985 /* get matchlength */
986 if ((length = (token & ML_MASK)) == ML_MASK) {
987 while (likely(ip < iend - (LASTLITERALS + 1))) {
988 int s = *ip++;
989 length += s;
990 if (s == 255)
991 continue;
992 break;
993 }
994 }
995 /* copy repeated sequence */
996 if unlikely(op - ref < STEPSIZE) {
997 #if LZ4_ARCH64
998 size_t dec64 = dec64table[op-ref];
999 #else
1000 const int dec64 = 0;
1001 #endif
1002 op[0] = ref[0];
1003 op[1] = ref[1];
1004 op[2] = ref[2];
1005 op[3] = ref[3];
1006 op += 4;
1007 ref += 4;
1008 ref -= dec32table[op-ref];
1009 A32(op) = A32(ref);
1010 op += STEPSIZE - 4;
1011 ref -= dec64;
1012 } else {
1013 LZ4_COPYSTEP(ref, op);
1014 }
1015 cpy = op + length - (STEPSIZE - 4);
1016 if (unlikely(cpy > oend - (COPYLENGTH + (STEPSIZE - 4)))) {
1017 if (cpy > oend - LASTLITERALS)
1018 /*
1019 * Error: last 5 bytes must be literals
1020 */
1021 goto _output_error;
1022 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
1023 while (op < cpy)
1024 *op++ = *ref++;
1025 op = cpy;
1026 if (op == oend)
1027 /*
1028 * Check EOF (should never happen, since
1029 * last 5 bytes are supposed to be literals)
1030 */
1031 goto _output_error;
1032 continue;
1033 }
1034 LZ4_WILDCOPY(ref, op, cpy);
1035 op = cpy; /* correction */
1036 }
1037
1038 /* end of decoding */
1039 return (int)(((char *)op) - dest);
1040
1041 /* write overflow error detected */
1042 _output_error:
1043 return (int)(-(((char *)ip) - source));
1044 }