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 */ 34 35 #include <sys/zfs_context.h> 36 37 static int real_LZ4_compress(const char *source, char *dest, int isize, 38 int osize); 39 static int real_LZ4_uncompress(const char *source, char *dest, 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 * real_LZ4_uncompress() : 108 * osize : is the output size, therefore the original size 109 * return : the number of bytes read in the source buffer. 110 * If the source stream is malformed, the function will stop 111 * decoding and return a negative result, indicating the byte 112 * position of the faulty instruction. This function never 113 * writes beyond dest + osize, and is therefore protected 114 * against malicious data packets. 115 * note : destination buffer must be already allocated 116 * 117 * Advanced Functions 118 * 119 * LZ4_compressBound() : 120 * Provides the maximum size that LZ4 may output in a "worst case" 121 * scenario (input data not compressible) primarily useful for memory 122 * allocation of output buffer. 123 * 124 * isize : is the input size. Max supported value is ~1.9GB 125 * return : maximum output size in a "worst case" scenario 126 * note : this function is limited by "int" range (2^31-1) 127 * 128 * LZ4_uncompress_unknownOutputSize() : 129 * isize : is the input size, therefore the compressed size 130 * maxOutputSize : is the size of the destination buffer (which must be 131 * already allocated) 132 * return : the number of bytes decoded in the destination buffer 133 * (necessarily <= maxOutputSize). If the source stream is 134 * malformed, the function will stop decoding and return a 135 * negative result, indicating the byte position of the faulty 136 * instruction. This function never writes beyond dest + 137 * maxOutputSize, and is therefore protected against malicious 138 * data packets. 139 * note : Destination buffer must be already allocated. 140 * This version is slightly slower than real_LZ4_uncompress() 141 * 142 * LZ4_compressCtx() : 143 * This function explicitly handles the CTX memory structure. 144 * 145 * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated 146 * by the caller (either on the stack or using kmem_zalloc). Passing NULL 147 * isn't valid. 148 * 149 * LZ4_compress64kCtx() : 150 * Same as LZ4_compressCtx(), but specific to small inputs (<64KB). 151 * isize *Must* be <64KB, otherwise the output will be corrupted. 152 * 153 * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated 154 * by the caller (either on the stack or using kmem_zalloc). Passing NULL 155 * isn't valid. 156 */ 157 158 /* 159 * Tuning parameters 160 */ 161 162 /* 163 * COMPRESSIONLEVEL: Increasing this value improves compression ratio 164 * Lowering this value reduces memory usage. Reduced memory usage 165 * typically improves speed, due to cache effect (ex: L1 32KB for Intel, 166 * L1 64KB for AMD). Memory usage formula : N->2^(N+2) Bytes 167 * (examples : 12 -> 16KB ; 17 -> 512KB) 168 */ 169 #define COMPRESSIONLEVEL 12 170 171 /* 172 * NOTCOMPRESSIBLE_CONFIRMATION: Decreasing this value will make the 173 * algorithm skip faster data segments considered "incompressible". 174 * This may decrease compression ratio dramatically, but will be 175 * faster on incompressible data. Increasing this value will make 176 * the algorithm search more before declaring a segment "incompressible". 177 * This could improve compression a bit, but will be slower on 178 * incompressible data. The default value (6) is recommended. 179 */ 180 #define NOTCOMPRESSIBLE_CONFIRMATION 6 181 182 /* 183 * BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE: This will provide a boost to 184 * performance for big endian cpu, but the resulting compressed stream 185 * will be incompatible with little-endian CPU. You can set this option 186 * to 1 in situations where data will stay within closed environment. 187 * This option is useless on Little_Endian CPU (such as x86). 188 */ 189 /* #define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1 */ 190 191 /* 192 * CPU Feature Detection 193 */ 194 195 /* 32 or 64 bits ? */ 196 #if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || \ 197 defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || \ 198 defined(__LP64__) || defined(_LP64)) 199 #define LZ4_ARCH64 1 200 #else 201 #define LZ4_ARCH64 0 202 #endif 203 204 /* 205 * Limits the amount of stack space that the algorithm may consume to hold 206 * the compression lookup table. The value `9' here means we'll never use 207 * more than 2k of stack (see above for a description of COMPRESSIONLEVEL). 208 * If more memory is needed, it is allocated from the heap. 209 */ 210 #define STACKLIMIT 9 211 212 /* 213 * Little Endian or Big Endian? 214 * Note: overwrite the below #define if you know your architecture endianess. 215 */ 216 #if (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || \ 217 defined(_BIG_ENDIAN) || defined(_ARCH_PPC) || defined(__PPC__) || \ 218 defined(__PPC) || defined(PPC) || defined(__powerpc__) || \ 219 defined(__powerpc) || defined(powerpc) || \ 220 ((defined(__BYTE_ORDER__)&&(__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)))) 221 #define LZ4_BIG_ENDIAN 1 222 #else 223 /* 224 * Little Endian assumed. PDP Endian and other very rare endian format 225 * are unsupported. 226 */ 227 #endif 228 229 /* 230 * Unaligned memory access is automatically enabled for "common" CPU, 231 * such as x86. For others CPU, the compiler will be more cautious, and 232 * insert extra code to ensure aligned access is respected. If you know 233 * your target CPU supports unaligned memory access, you may want to 234 * force this option manually to improve performance 235 */ 236 #if defined(__ARM_FEATURE_UNALIGNED) 237 #define LZ4_FORCE_UNALIGNED_ACCESS 1 238 #endif 239 240 #ifdef __sparc 241 #define LZ4_FORCE_SW_BITCOUNT 242 #endif 243 244 /* 245 * Compiler Options 246 */ 247 #if __STDC_VERSION__ >= 199901L /* C99 */ 248 /* "restrict" is a known keyword */ 249 #else 250 /* Disable restrict */ 251 #define restrict 252 #endif 253 254 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) 255 256 #ifdef _MSC_VER 257 /* Visual Studio */ 258 /* Visual is not C99, but supports some kind of inline */ 259 #define inline __forceinline 260 #if LZ4_ARCH64 261 /* For Visual 2005 */ 262 #pragma intrinsic(_BitScanForward64) 263 #pragma intrinsic(_BitScanReverse64) 264 #else /* !LZ4_ARCH64 */ 265 /* For Visual 2005 */ 266 #pragma intrinsic(_BitScanForward) 267 #pragma intrinsic(_BitScanReverse) 268 #endif /* !LZ4_ARCH64 */ 269 #endif /* _MSC_VER */ 270 271 #ifdef _MSC_VER 272 #define lz4_bswap16(x) _byteswap_ushort(x) 273 #else /* !_MSC_VER */ 274 #define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | \ 275 (((x) & 0xffu) << 8))) 276 #endif /* !_MSC_VER */ 277 278 #if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__) 279 #define expect(expr, value) (__builtin_expect((expr), (value))) 280 #else 281 #define expect(expr, value) (expr) 282 #endif 283 284 #define likely(expr) expect((expr) != 0, 1) 285 #define unlikely(expr) expect((expr) != 0, 0) 286 287 /* Basic types */ 288 #if defined(_MSC_VER) 289 /* Visual Studio does not support 'stdint' natively */ 290 #define BYTE unsigned __int8 291 #define U16 unsigned __int16 292 #define U32 unsigned __int32 293 #define S32 __int32 294 #define U64 unsigned __int64 295 #else /* !defined(_MSC_VER) */ 296 #define BYTE uint8_t 297 #define U16 uint16_t 298 #define U32 uint32_t 299 #define S32 int32_t 300 #define U64 uint64_t 301 #endif /* !defined(_MSC_VER) */ 302 303 #ifndef LZ4_FORCE_UNALIGNED_ACCESS 304 #pragma pack(1) 305 #endif 306 307 typedef struct _U16_S { 308 U16 v; 309 } U16_S; 310 typedef struct _U32_S { 311 U32 v; 312 } U32_S; 313 typedef struct _U64_S { 314 U64 v; 315 } U64_S; 316 317 #ifndef LZ4_FORCE_UNALIGNED_ACCESS 318 #pragma pack() 319 #endif 320 321 #define A64(x) (((U64_S *)(x))->v) 322 #define A32(x) (((U32_S *)(x))->v) 323 #define A16(x) (((U16_S *)(x))->v) 324 325 /* 326 * Constants 327 */ 328 #define MINMATCH 4 329 330 #define HASH_LOG COMPRESSIONLEVEL 331 #define HASHTABLESIZE (1 << HASH_LOG) 332 #define HASH_MASK (HASHTABLESIZE - 1) 333 334 #define SKIPSTRENGTH (NOTCOMPRESSIBLE_CONFIRMATION > 2 ? \ 335 NOTCOMPRESSIBLE_CONFIRMATION : 2) 336 337 /* 338 * Defines if memory is allocated into the stack (local variable), 339 * or into the heap (kmem_alloc()). 340 */ 341 #define HEAPMODE (HASH_LOG > STACKLIMIT) 342 #define COPYLENGTH 8 343 #define LASTLITERALS 5 344 #define MFLIMIT (COPYLENGTH + MINMATCH) 345 #define MINLENGTH (MFLIMIT + 1) 346 347 #define MAXD_LOG 16 348 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1) 349 350 #define ML_BITS 4 351 #define ML_MASK ((1U<<ML_BITS)-1) 352 #define RUN_BITS (8-ML_BITS) 353 #define RUN_MASK ((1U<<RUN_BITS)-1) 354 355 356 /* 357 * Architecture-specific macros 358 */ 359 #if LZ4_ARCH64 360 #define STEPSIZE 8 361 #define UARCH U64 362 #define AARCH A64 363 #define LZ4_COPYSTEP(s, d) A64(d) = A64(s); d += 8; s += 8; 364 #define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d) 365 #define LZ4_SECURECOPY(s, d, e) if (d < e) LZ4_WILDCOPY(s, d, e) 366 #define HTYPE U32 367 #define INITBASE(base) const BYTE* const base = ip 368 #else /* !LZ4_ARCH64 */ 369 #define STEPSIZE 4 370 #define UARCH U32 371 #define AARCH A32 372 #define LZ4_COPYSTEP(s, d) A32(d) = A32(s); d += 4; s += 4; 373 #define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d); LZ4_COPYSTEP(s, d); 374 #define LZ4_SECURECOPY LZ4_WILDCOPY 375 #define HTYPE const BYTE * 376 #define INITBASE(base) const int base = 0 377 #endif /* !LZ4_ARCH64 */ 378 379 #if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE)) 380 #define LZ4_READ_LITTLEENDIAN_16(d, s, p) \ 381 { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; } 382 #define LZ4_WRITE_LITTLEENDIAN_16(p, i) \ 383 { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p += 2; } 384 #else 385 #define LZ4_READ_LITTLEENDIAN_16(d, s, p) { d = (s) - A16(p); } 386 #define LZ4_WRITE_LITTLEENDIAN_16(p, v) { A16(p) = v; p += 2; } 387 #endif 388 389 390 /* Local structures */ 391 struct refTables { 392 HTYPE hashTable[HASHTABLESIZE]; 393 }; 394 395 396 /* Macros */ 397 #define LZ4_HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH * 8) - \ 398 HASH_LOG)) 399 #define LZ4_HASH_VALUE(p) LZ4_HASH_FUNCTION(A32(p)) 400 #define LZ4_WILDCOPY(s, d, e) do { LZ4_COPYPACKET(s, d) } while (d < e); 401 #define LZ4_BLINDCOPY(s, d, l) { BYTE* e = (d) + l; LZ4_WILDCOPY(s, d, e); \ 402 d = e; } 403 404 405 /* Private functions */ 406 #if LZ4_ARCH64 407 408 static inline int 409 LZ4_NbCommonBytes(register U64 val) 410 { 411 #if defined(LZ4_BIG_ENDIAN) 412 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) 413 unsigned long r = 0; 414 _BitScanReverse64(&r, val); 415 return (int)(r >> 3); 416 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && \ 417 !defined(LZ4_FORCE_SW_BITCOUNT) 418 return (__builtin_clzll(val) >> 3); 419 #else 420 int r; 421 if (!(val >> 32)) { 422 r = 4; 423 } else { 424 r = 0; 425 val >>= 32; 426 } 427 if (!(val >> 16)) { 428 r += 2; 429 val >>= 8; 430 } else { 431 val >>= 24; 432 } 433 r += (!val); 434 return (r); 435 #endif 436 #else 437 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) 438 unsigned long r = 0; 439 _BitScanForward64(&r, val); 440 return (int)(r >> 3); 441 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && \ 442 !defined(LZ4_FORCE_SW_BITCOUNT) 443 return (__builtin_ctzll(val) >> 3); 444 #else 445 static const int DeBruijnBytePos[64] = 446 { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 447 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 448 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 449 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 450 }; 451 return DeBruijnBytePos[((U64) ((val & -val) * 0x0218A392CDABBD3F)) >> 452 58]; 453 #endif 454 #endif 455 } 456 457 #else 458 459 static inline int 460 LZ4_NbCommonBytes(register U32 val) 461 { 462 #if defined(LZ4_BIG_ENDIAN) 463 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) 464 unsigned long r = 0; 465 _BitScanReverse(&r, val); 466 return (int)(r >> 3); 467 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && \ 468 !defined(LZ4_FORCE_SW_BITCOUNT) 469 return (__builtin_clz(val) >> 3); 470 #else 471 int r; 472 if (!(val >> 16)) { 473 r = 2; 474 val >>= 8; 475 } else { 476 r = 0; 477 val >>= 24; 478 } 479 r += (!val); 480 return (r); 481 #endif 482 #else 483 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) 484 unsigned long r = 0; 485 _BitScanForward(&r, val); 486 return (int)(r >> 3); 487 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && \ 488 !defined(LZ4_FORCE_SW_BITCOUNT) 489 return (__builtin_ctz(val) >> 3); 490 #else 491 static const int DeBruijnBytePos[32] = { 492 0, 0, 3, 0, 3, 1, 3, 0, 493 3, 2, 2, 1, 3, 2, 0, 1, 494 3, 3, 1, 2, 2, 2, 2, 0, 495 3, 1, 2, 0, 1, 0, 1, 1 496 }; 497 return DeBruijnBytePos[((U32) ((val & -(S32) val) * 0x077CB531U)) >> 498 27]; 499 #endif 500 #endif 501 } 502 503 #endif 504 505 /* Public functions */ 506 507 static int 508 LZ4_compressBound(int isize) 509 { 510 return (isize + (isize / 255) + 16); 511 } 512 513 /* Compression functions */ 514 515 /*ARGSUSED*/ 516 static int 517 LZ4_compressCtx(void *ctx, const char *source, char *dest, int isize, 518 int osize) 519 { 520 #if HEAPMODE 521 struct refTables *srt = (struct refTables *)ctx; 522 HTYPE *HashTable = (HTYPE *) (srt->hashTable); 523 #else 524 HTYPE HashTable[HASHTABLESIZE] = { 0 }; 525 #endif 526 527 const BYTE *ip = (BYTE *) source; 528 INITBASE(base); 529 const BYTE *anchor = ip; 530 const BYTE *const iend = ip + isize; 531 const BYTE *const oend = (BYTE *) dest + osize; 532 const BYTE *const mflimit = iend - MFLIMIT; 533 #define matchlimit (iend - LASTLITERALS) 534 535 BYTE *op = (BYTE *) dest; 536 537 int len, length; 538 const int skipStrength = SKIPSTRENGTH; 539 U32 forwardH; 540 541 542 /* Init */ 543 if (isize < MINLENGTH) 544 goto _last_literals; 545 546 /* First Byte */ 547 HashTable[LZ4_HASH_VALUE(ip)] = ip - base; 548 ip++; 549 forwardH = LZ4_HASH_VALUE(ip); 550 551 /* Main Loop */ 552 for (;;) { 553 int findMatchAttempts = (1U << skipStrength) + 3; 554 const BYTE *forwardIp = ip; 555 const BYTE *ref; 556 BYTE *token; 557 558 /* Find a match */ 559 do { 560 U32 h = forwardH; 561 int step = findMatchAttempts++ >> skipStrength; 562 ip = forwardIp; 563 forwardIp = ip + step; 564 565 if unlikely(forwardIp > mflimit) { 566 goto _last_literals; 567 } 568 569 forwardH = LZ4_HASH_VALUE(forwardIp); 570 ref = base + HashTable[h]; 571 HashTable[h] = ip - base; 572 573 } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip))); 574 575 /* Catch up */ 576 while ((ip > anchor) && (ref > (BYTE *) source) && 577 unlikely(ip[-1] == ref[-1])) { 578 ip--; 579 ref--; 580 } 581 582 /* Encode Literal length */ 583 length = ip - anchor; 584 token = op++; 585 586 /* Check output limit */ 587 if unlikely(op + length + (2 + 1 + LASTLITERALS) + 588 (length >> 8) > oend) 589 return (0); 590 591 if (length >= (int)RUN_MASK) { 592 *token = (RUN_MASK << ML_BITS); 593 len = length - RUN_MASK; 594 for (; len > 254; len -= 255) 595 *op++ = 255; 596 *op++ = (BYTE)len; 597 } else 598 *token = (length << ML_BITS); 599 600 /* Copy Literals */ 601 LZ4_BLINDCOPY(anchor, op, length); 602 603 _next_match: 604 /* Encode Offset */ 605 LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref); 606 607 /* Start Counting */ 608 ip += MINMATCH; 609 ref += MINMATCH; /* MinMatch verified */ 610 anchor = ip; 611 while likely(ip < matchlimit - (STEPSIZE - 1)) { 612 UARCH diff = AARCH(ref) ^ AARCH(ip); 613 if (!diff) { 614 ip += STEPSIZE; 615 ref += STEPSIZE; 616 continue; 617 } 618 ip += LZ4_NbCommonBytes(diff); 619 goto _endCount; 620 } 621 #if LZ4_ARCH64 622 if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) { 623 ip += 4; 624 ref += 4; 625 } 626 #endif 627 if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) { 628 ip += 2; 629 ref += 2; 630 } 631 if ((ip < matchlimit) && (*ref == *ip)) 632 ip++; 633 _endCount: 634 635 /* Encode MatchLength */ 636 len = (ip - anchor); 637 /* Check output limit */ 638 if unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend) 639 return (0); 640 if (len >= (int)ML_MASK) { 641 *token += ML_MASK; 642 len -= ML_MASK; 643 for (; len > 509; len -= 510) { 644 *op++ = 255; 645 *op++ = 255; 646 } 647 if (len > 254) { 648 len -= 255; 649 *op++ = 255; 650 } 651 *op++ = (BYTE)len; 652 } else 653 *token += len; 654 655 /* Test end of chunk */ 656 if (ip > mflimit) { 657 anchor = ip; 658 break; 659 } 660 /* Fill table */ 661 HashTable[LZ4_HASH_VALUE(ip - 2)] = ip - 2 - base; 662 663 /* Test next position */ 664 ref = base + HashTable[LZ4_HASH_VALUE(ip)]; 665 HashTable[LZ4_HASH_VALUE(ip)] = ip - base; 666 if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) { 667 token = op++; 668 *token = 0; 669 goto _next_match; 670 } 671 /* Prepare next loop */ 672 anchor = ip++; 673 forwardH = LZ4_HASH_VALUE(ip); 674 } 675 676 _last_literals: 677 /* Encode Last Literals */ 678 { 679 int lastRun = iend - anchor; 680 if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) > 681 oend) 682 return (0); 683 if (lastRun >= (int)RUN_MASK) { 684 *op++ = (RUN_MASK << ML_BITS); 685 lastRun -= RUN_MASK; 686 for (; lastRun > 254; lastRun -= 255) { 687 *op++ = 255; 688 } 689 *op++ = (BYTE)lastRun; 690 } else 691 *op++ = (lastRun << ML_BITS); 692 (void) memcpy(op, anchor, iend - anchor); 693 op += iend - anchor; 694 } 695 696 /* End */ 697 return (int)(((char *)op) - dest); 698 } 699 700 701 702 /* Note : this function is valid only if isize < LZ4_64KLIMIT */ 703 #define LZ4_64KLIMIT ((1 << 16) + (MFLIMIT - 1)) 704 #define HASHLOG64K (HASH_LOG + 1) 705 #define HASH64KTABLESIZE (1U << HASHLOG64K) 706 #define LZ4_HASH64K_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8) - \ 707 HASHLOG64K)) 708 #define LZ4_HASH64K_VALUE(p) LZ4_HASH64K_FUNCTION(A32(p)) 709 710 /*ARGSUSED*/ 711 static int 712 LZ4_compress64kCtx(void *ctx, const char *source, char *dest, int isize, 713 int osize) 714 { 715 #if HEAPMODE 716 struct refTables *srt = (struct refTables *)ctx; 717 U16 *HashTable = (U16 *) (srt->hashTable); 718 #else 719 U16 HashTable[HASH64KTABLESIZE] = { 0 }; 720 #endif 721 722 const BYTE *ip = (BYTE *) source; 723 const BYTE *anchor = ip; 724 const BYTE *const base = ip; 725 const BYTE *const iend = ip + isize; 726 const BYTE *const oend = (BYTE *) dest + osize; 727 const BYTE *const mflimit = iend - MFLIMIT; 728 #define matchlimit (iend - LASTLITERALS) 729 730 BYTE *op = (BYTE *) dest; 731 732 int len, length; 733 const int skipStrength = SKIPSTRENGTH; 734 U32 forwardH; 735 736 /* Init */ 737 if (isize < MINLENGTH) 738 goto _last_literals; 739 740 /* First Byte */ 741 ip++; 742 forwardH = LZ4_HASH64K_VALUE(ip); 743 744 /* Main Loop */ 745 for (;;) { 746 int findMatchAttempts = (1U << skipStrength) + 3; 747 const BYTE *forwardIp = ip; 748 const BYTE *ref; 749 BYTE *token; 750 751 /* Find a match */ 752 do { 753 U32 h = forwardH; 754 int step = findMatchAttempts++ >> skipStrength; 755 ip = forwardIp; 756 forwardIp = ip + step; 757 758 if (forwardIp > mflimit) { 759 goto _last_literals; 760 } 761 762 forwardH = LZ4_HASH64K_VALUE(forwardIp); 763 ref = base + HashTable[h]; 764 HashTable[h] = ip - base; 765 766 } while (A32(ref) != A32(ip)); 767 768 /* Catch up */ 769 while ((ip > anchor) && (ref > (BYTE *) source) && 770 (ip[-1] == ref[-1])) { 771 ip--; 772 ref--; 773 } 774 775 /* Encode Literal length */ 776 length = ip - anchor; 777 token = op++; 778 779 /* Check output limit */ 780 if unlikely(op + length + (2 + 1 + LASTLITERALS) + 781 (length >> 8) > oend) 782 return (0); 783 784 if (length >= (int)RUN_MASK) { 785 *token = (RUN_MASK << ML_BITS); 786 len = length - RUN_MASK; 787 for (; len > 254; len -= 255) 788 *op++ = 255; 789 *op++ = (BYTE)len; 790 } else 791 *token = (length << ML_BITS); 792 793 /* Copy Literals */ 794 LZ4_BLINDCOPY(anchor, op, length); 795 796 _next_match: 797 /* Encode Offset */ 798 LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref); 799 800 /* Start Counting */ 801 ip += MINMATCH; 802 ref += MINMATCH; /* MinMatch verified */ 803 anchor = ip; 804 while (ip < matchlimit - (STEPSIZE - 1)) { 805 UARCH diff = AARCH(ref) ^ AARCH(ip); 806 if (!diff) { 807 ip += STEPSIZE; 808 ref += STEPSIZE; 809 continue; 810 } 811 ip += LZ4_NbCommonBytes(diff); 812 goto _endCount; 813 } 814 #if LZ4_ARCH64 815 if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) { 816 ip += 4; 817 ref += 4; 818 } 819 #endif 820 if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) { 821 ip += 2; 822 ref += 2; 823 } 824 if ((ip < matchlimit) && (*ref == *ip)) 825 ip++; 826 _endCount: 827 828 /* Encode MatchLength */ 829 len = (ip - anchor); 830 /* Check output limit */ 831 if unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend) 832 return (0); 833 if (len >= (int)ML_MASK) { 834 *token += ML_MASK; 835 len -= ML_MASK; 836 for (; len > 509; len -= 510) { 837 *op++ = 255; 838 *op++ = 255; 839 } 840 if (len > 254) { 841 len -= 255; 842 *op++ = 255; 843 } 844 *op++ = (BYTE)len; 845 } else 846 *token += len; 847 848 /* Test end of chunk */ 849 if (ip > mflimit) { 850 anchor = ip; 851 break; 852 } 853 /* Fill table */ 854 HashTable[LZ4_HASH64K_VALUE(ip - 2)] = ip - 2 - base; 855 856 /* Test next position */ 857 ref = base + HashTable[LZ4_HASH64K_VALUE(ip)]; 858 HashTable[LZ4_HASH64K_VALUE(ip)] = ip - base; 859 if (A32(ref) == A32(ip)) { 860 token = op++; 861 *token = 0; 862 goto _next_match; 863 } 864 /* Prepare next loop */ 865 anchor = ip++; 866 forwardH = LZ4_HASH64K_VALUE(ip); 867 } 868 869 _last_literals: 870 /* Encode Last Literals */ 871 { 872 int lastRun = iend - anchor; 873 if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) > 874 oend) 875 return (0); 876 if (lastRun >= (int)RUN_MASK) { 877 *op++ = (RUN_MASK << ML_BITS); 878 lastRun -= RUN_MASK; 879 for (; lastRun > 254; lastRun -= 255) 880 *op++ = 255; 881 *op++ = (BYTE)lastRun; 882 } else 883 *op++ = (lastRun << ML_BITS); 884 (void) memcpy(op, anchor, iend - anchor); 885 op += iend - anchor; 886 } 887 888 /* End */ 889 return (int)(((char *)op) - dest); 890 } 891 892 static int 893 real_LZ4_compress(const char *source, char *dest, int isize, int osize) 894 { 895 #if HEAPMODE 896 void *ctx = kmem_zalloc(sizeof (struct refTables), KM_NOSLEEP); 897 int result; 898 899 /* 900 * out of kernel memory, gently fall through - this will disable 901 * compression in zio_compress_data 902 */ 903 if (ctx == NULL) 904 return (0); 905 906 if (isize < LZ4_64KLIMIT) 907 result = LZ4_compress64kCtx(ctx, source, dest, isize, osize); 908 else 909 result = LZ4_compressCtx(ctx, source, dest, isize, osize); 910 911 kmem_free(ctx, sizeof (struct refTables)); 912 return (result); 913 #else 914 if (isize < (int)LZ4_64KLIMIT) 915 return (LZ4_compress64kCtx(NULL, source, dest, isize, osize)); 916 return (LZ4_compressCtx(NULL, source, dest, isize, osize)); 917 #endif 918 } 919 920 /* Decompression functions */ 921 922 /* 923 * Note: The decoding functions real_LZ4_uncompress() and 924 * LZ4_uncompress_unknownOutputSize() are safe against "buffer overflow" 925 * attack type. They will never write nor read outside of the provided 926 * output buffers. LZ4_uncompress_unknownOutputSize() also insures that 927 * it will never read outside of the input buffer. A corrupted input 928 * will produce an error result, a negative int, indicating the position 929 * of the error within input stream. 930 */ 931 932 static int 933 real_LZ4_uncompress(const char *source, char *dest, int osize) 934 { 935 /* Local Variables */ 936 const BYTE *restrict ip = (const BYTE *) source; 937 const BYTE *ref; 938 939 BYTE *op = (BYTE *) dest; 940 BYTE *const oend = op + osize; 941 BYTE *cpy; 942 943 unsigned token; 944 945 size_t length; 946 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; 947 #if LZ4_ARCH64 948 size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3}; 949 #endif 950 951 /* Main Loop */ 952 for (;;) { 953 /* get runlength */ 954 token = *ip++; 955 if ((length = (token >> ML_BITS)) == RUN_MASK) { 956 size_t len; 957 for (; (len = *ip++) == 255; length += 255) { 958 } 959 length += len; 960 } 961 /* copy literals */ 962 cpy = op + length; 963 if unlikely(cpy > oend - COPYLENGTH) { 964 if (cpy != oend) 965 /* Error: we must necessarily stand at EOF */ 966 goto _output_error; 967 (void) memcpy(op, ip, length); 968 ip += length; 969 break; /* EOF */ 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 create reference outside destination 981 * buffer 982 */ 983 goto _output_error; 984 985 /* get matchlength */ 986 if ((length = (token & ML_MASK)) == ML_MASK) { 987 for (; *ip == 255; length += 255) { 988 ip++; 989 } 990 length += *ip++; 991 } 992 /* copy repeated sequence */ 993 if unlikely(op - ref < STEPSIZE) { 994 #if LZ4_ARCH64 995 size_t dec64 = dec64table[op-ref]; 996 #else 997 const int dec64 = 0; 998 #endif 999 op[0] = ref[0]; 1000 op[1] = ref[1]; 1001 op[2] = ref[2]; 1002 op[3] = ref[3]; 1003 op += 4; 1004 ref += 4; 1005 ref -= dec32table[op-ref]; 1006 A32(op) = A32(ref); 1007 op += STEPSIZE - 4; 1008 ref -= dec64; 1009 } else { 1010 LZ4_COPYSTEP(ref, op); 1011 } 1012 cpy = op + length - (STEPSIZE - 4); 1013 if (cpy > oend - COPYLENGTH) { 1014 if (cpy > oend) 1015 /* 1016 * Error: request to write beyond destination 1017 * buffer 1018 */ 1019 goto _output_error; 1020 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH)); 1021 while (op < cpy) 1022 *op++ = *ref++; 1023 op = cpy; 1024 if (op == oend) 1025 /* 1026 * Check EOF (should never happen, since last 1027 * 5 bytes are supposed to be literals) 1028 */ 1029 goto _output_error; 1030 continue; 1031 } 1032 LZ4_SECURECOPY(ref, op, cpy); 1033 op = cpy; /* correction */ 1034 } 1035 1036 /* end of decoding */ 1037 return (int)(((char *)ip) - source); 1038 1039 /* write overflow error detected */ 1040 _output_error: 1041 return (int)(-(((char *)ip) - source)); 1042 } 1043 1044 static int 1045 LZ4_uncompress_unknownOutputSize(const char *source, char *dest, int isize, 1046 int maxOutputSize) 1047 { 1048 /* Local Variables */ 1049 const BYTE *restrict ip = (const BYTE *) source; 1050 const BYTE *const iend = ip + isize; 1051 const BYTE *ref; 1052 1053 BYTE *op = (BYTE *) dest; 1054 BYTE *const oend = op + maxOutputSize; 1055 BYTE *cpy; 1056 1057 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; 1058 #if LZ4_ARCH64 1059 size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3}; 1060 #endif 1061 1062 /* Main Loop */ 1063 while (ip < iend) { 1064 unsigned token; 1065 size_t length; 1066 1067 /* get runlength */ 1068 token = *ip++; 1069 if ((length = (token >> ML_BITS)) == RUN_MASK) { 1070 int s = 255; 1071 while ((ip < iend) && (s == 255)) { 1072 s = *ip++; 1073 length += s; 1074 } 1075 } 1076 /* copy literals */ 1077 cpy = op + length; 1078 if ((cpy > oend - COPYLENGTH) || 1079 (ip + length > iend - COPYLENGTH)) { 1080 if (cpy > oend) 1081 /* Error: writes beyond output buffer */ 1082 goto _output_error; 1083 if (ip + length != iend) 1084 /* 1085 * Error: LZ4 format requires to consume all 1086 * input at this stage 1087 */ 1088 goto _output_error; 1089 (void) memcpy(op, ip, length); 1090 op += length; 1091 /* Necessarily EOF, due to parsing restrictions */ 1092 break; 1093 } 1094 LZ4_WILDCOPY(ip, op, cpy); 1095 ip -= (op - cpy); 1096 op = cpy; 1097 1098 /* get offset */ 1099 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip); 1100 ip += 2; 1101 if (ref < (BYTE * const) dest) 1102 /* 1103 * Error: offset creates reference outside of 1104 * destination buffer 1105 */ 1106 goto _output_error; 1107 1108 /* get matchlength */ 1109 if ((length = (token & ML_MASK)) == ML_MASK) { 1110 while (ip < iend) { 1111 int s = *ip++; 1112 length += s; 1113 if (s == 255) 1114 continue; 1115 break; 1116 } 1117 } 1118 /* copy repeated sequence */ 1119 if unlikely(op - ref < STEPSIZE) { 1120 #if LZ4_ARCH64 1121 size_t dec64 = dec64table[op-ref]; 1122 #else 1123 const int dec64 = 0; 1124 #endif 1125 op[0] = ref[0]; 1126 op[1] = ref[1]; 1127 op[2] = ref[2]; 1128 op[3] = ref[3]; 1129 op += 4; 1130 ref += 4; 1131 ref -= dec32table[op-ref]; 1132 A32(op) = A32(ref); 1133 op += STEPSIZE - 4; 1134 ref -= dec64; 1135 } else { 1136 LZ4_COPYSTEP(ref, op); 1137 } 1138 cpy = op + length - (STEPSIZE - 4); 1139 if (cpy > oend - COPYLENGTH) { 1140 if (cpy > oend) 1141 /* 1142 * Error: request to write outside of 1143 * destination buffer 1144 */ 1145 goto _output_error; 1146 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH)); 1147 while (op < cpy) 1148 *op++ = *ref++; 1149 op = cpy; 1150 if (op == oend) 1151 /* 1152 * Check EOF (should never happen, since 1153 * last 5 bytes are supposed to be literals) 1154 */ 1155 goto _output_error; 1156 continue; 1157 } 1158 LZ4_SECURECOPY(ref, op, cpy); 1159 op = cpy; /* correction */ 1160 } 1161 1162 /* end of decoding */ 1163 return (int)(((char *)op) - dest); 1164 1165 /* write overflow error detected */ 1166 _output_error: 1167 return (int)(-(((char *)ip) - source)); 1168 } 1169