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