sys/cddl/contrib/opensolaris/uts/common/fs/zfs/lz4.c

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