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 }