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 #define likely(expr)    expect((expr) != 0, 1)
 263 #define unlikely(expr)  expect((expr) != 0, 0)
 264
 265 /* Basic types */
 266 #define BYTE    uint8_t
 267 #define U16     uint16_t
 268 #define U32     uint32_t
 269 #define S32     int32_t
 270 #define U64     uint64_t
 271
 272 #ifndef LZ4_FORCE_UNALIGNED_ACCESS
 273 #pragma pack(1)
 274 #endif
 275
 276 typedef struct _U16_S {
 277         U16 v;
 278 } U16_S;
 279 typedef struct _U32_S {
 280         U32 v;
 281 } U32_S;
 282 typedef struct _U64_S {
 283         U64 v;
 284 } U64_S;
 285
 286 #ifndef LZ4_FORCE_UNALIGNED_ACCESS
 287 #pragma pack()
 288 #endif
 289
 290 #define A64(x) (((U64_S *)(x))->v)
 291 #define A32(x) (((U32_S *)(x))->v)
 292 #define A16(x) (((U16_S *)(x))->v)
 293
 294 /*
 295  * Constants
 296  */
 297 #define MINMATCH 4
 298
 299 #define HASH_LOG COMPRESSIONLEVEL
 300 #define HASHTABLESIZE (1 << HASH_LOG)
 301 #define HASH_MASK (HASHTABLESIZE - 1)
 302
 303 #define SKIPSTRENGTH (NOTCOMPRESSIBLE_CONFIRMATION > 2 ? \
 304         NOTCOMPRESSIBLE_CONFIRMATION : 2)
 305
 306 /*
 307  * Defines if memory is allocated into the stack (local variable),
 308  * or into the heap (kmem_alloc()).
 309  */
 310 #define HEAPMODE (HASH_LOG > STACKLIMIT)
 311 #define COPYLENGTH 8
 312 #define LASTLITERALS 5
 313 #define MFLIMIT (COPYLENGTH + MINMATCH)
 314 #define MINLENGTH (MFLIMIT + 1)
 315
 316 #define MAXD_LOG 16
 317 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
 318
 319 #define ML_BITS 4
 320 #define ML_MASK ((1U<<ML_BITS)-1)
 321 #define RUN_BITS (8-ML_BITS)
 322 #define RUN_MASK ((1U<<RUN_BITS)-1)
 323
 324
 325 /*
 326  * Architecture-specific macros
 327  */
 328 #if LZ4_ARCH64
 329 #define STEPSIZE 8
 330 #define UARCH U64
 331 #define AARCH A64
 332 #define LZ4_COPYSTEP(s, d)      A64(d) = A64(s); d += 8; s += 8;
 333 #define LZ4_COPYPACKET(s, d)    LZ4_COPYSTEP(s, d)
 334 #define LZ4_SECURECOPY(s, d, e) if (d < e) LZ4_WILDCOPY(s, d, e)
 335 #define HTYPE U32
 336 #define INITBASE(base)          const BYTE* const base = ip
 337 #else /* !LZ4_ARCH64 */
 338 #define STEPSIZE 4
 339 #define UARCH U32
 340 #define AARCH A32
 341 #define LZ4_COPYSTEP(s, d)      A32(d) = A32(s); d += 4; s += 4;
 342 #define LZ4_COPYPACKET(s, d)    LZ4_COPYSTEP(s, d); LZ4_COPYSTEP(s, d);
 343 #define LZ4_SECURECOPY          LZ4_WILDCOPY
 344 #define HTYPE const BYTE *
 345 #define INITBASE(base)          const int base = 0
 346 #endif /* !LZ4_ARCH64 */
 347
 348 #if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE))
 349 #define LZ4_READ_LITTLEENDIAN_16(d, s, p) \
 350         { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }
 351 #define LZ4_WRITE_LITTLEENDIAN_16(p, i) \
 352         { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p += 2; }
 353 #else
 354 #define LZ4_READ_LITTLEENDIAN_16(d, s, p) { d = (s) - A16(p); }
 355 #define LZ4_WRITE_LITTLEENDIAN_16(p, v)  { A16(p) = v; p += 2; }
 356 #endif
 357
 358
 359 /* Local structures */
 360 struct refTables {
 361         HTYPE hashTable[HASHTABLESIZE];
 362 };
 363
 364
 365 /* Macros */
 366 #define LZ4_HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH * 8) - \
 367         HASH_LOG))
 368 #define LZ4_HASH_VALUE(p) LZ4_HASH_FUNCTION(A32(p))
 369 #define LZ4_WILDCOPY(s, d, e) do { LZ4_COPYPACKET(s, d) } while (d < e);
 370 #define LZ4_BLINDCOPY(s, d, l) { BYTE* e = (d) + l; LZ4_WILDCOPY(s, d, e); \
 371         d = e; }
 372
 373
 374 /* Private functions */
 375 #if LZ4_ARCH64
 376
 377 static inline int
 378 LZ4_NbCommonBytes(register U64 val)
 379 {
 380 #if defined(LZ4_BIG_ENDIAN)
 381 #if !defined(LZ4_FORCE_SW_BITCOUNT)
 382         return (__builtin_clzll(val) >> 3);
 383 #else
 384         int r;
 385         if (!(val >> 32)) {
 386                 r = 4;
 387         } else {
 388                 r = 0;
 389                 val >>= 32;
 390         }
 391         if (!(val >> 16)) {
 392                 r += 2;
 393                 val >>= 8;
 394         } else {
 395                 val >>= 24;
 396         }
 397         r += (!val);
 398         return (r);
 399 #endif
 400 #else
 401 #if !defined(LZ4_FORCE_SW_BITCOUNT)
 402         return (__builtin_ctzll(val) >> 3);
 403 #else
 404         static const int DeBruijnBytePos[64] =
 405             { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5,
 406                 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5,
 407                 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4,
 408                 4, 5, 7, 2, 6, 5, 7, 6, 7, 7
 409         };
 410         return DeBruijnBytePos[((U64) ((val & -val) * 0x0218A392CDABBD3F)) >>
 411             58];
 412 #endif
 413 #endif
 414 }
 415
 416 #else
 417
 418 static inline int
 419 LZ4_NbCommonBytes(register U32 val)
 420 {
 421 #if defined(LZ4_BIG_ENDIAN)
 422 #if !defined(LZ4_FORCE_SW_BITCOUNT)
 423         return (__builtin_clz(val) >> 3);
 424 #else
 425         int r;
 426         if (!(val >> 16)) {
 427                 r = 2;
 428                 val >>= 8;
 429         } else {
 430                 r = 0;
 431                 val >>= 24;
 432         }
 433         r += (!val);
 434         return (r);
 435 #endif
 436 #else
 437 #if !defined(LZ4_FORCE_SW_BITCOUNT)
 438         return (__builtin_ctz(val) >> 3);
 439 #else
 440         static const int DeBruijnBytePos[32] = {
 441                 0, 0, 3, 0, 3, 1, 3, 0,
 442                 3, 2, 2, 1, 3, 2, 0, 1,
 443                 3, 3, 1, 2, 2, 2, 2, 0,
 444                 3, 1, 2, 0, 1, 0, 1, 1
 445         };
 446         return DeBruijnBytePos[((U32) ((val & -(S32) val) * 0x077CB531U)) >>
 447             27];
 448 #endif
 449 #endif
 450 }
 451
 452 #endif
 453
 454 /* Public functions */
 455
 456 static int
 457 LZ4_compressBound(int isize)
 458 {
 459         return (isize + (isize / 255) + 16);
 460 }
 461
 462 /* Compression functions */
 463
 464 /*ARGSUSED*/
 465 static int
 466 LZ4_compressCtx(void *ctx, const char *source, char *dest, int isize,
 467     int osize)
 468 {
 469 #if HEAPMODE
 470         struct refTables *srt = (struct refTables *)ctx;
 471         HTYPE *HashTable = (HTYPE *) (srt->hashTable);
 472 #else
 473         HTYPE HashTable[HASHTABLESIZE] = { 0 };
 474 #endif
 475
 476         const BYTE *ip = (BYTE *) source;
 477         INITBASE(base);
 478         const BYTE *anchor = ip;
 479         const BYTE *const iend = ip + isize;
 480         const BYTE *const oend = (BYTE *) dest + osize;
 481         const BYTE *const mflimit = iend - MFLIMIT;
 482 #define matchlimit (iend - LASTLITERALS)
 483
 484         BYTE *op = (BYTE *) dest;
 485
 486         int len, length;
 487         const int skipStrength = SKIPSTRENGTH;
 488         U32 forwardH;
 489
 490
 491         /* Init */
 492         if (isize < MINLENGTH)
 493                 goto _last_literals;
 494
 495         /* First Byte */
 496         HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
 497         ip++;
 498         forwardH = LZ4_HASH_VALUE(ip);
 499
 500         /* Main Loop */
 501         for (;;) {
 502                 int findMatchAttempts = (1U << skipStrength) + 3;
 503                 const BYTE *forwardIp = ip;
 504                 const BYTE *ref;
 505                 BYTE *token;
 506
 507                 /* Find a match */
 508                 do {
 509                         U32 h = forwardH;
 510                         int step = findMatchAttempts++ >> skipStrength;
 511                         ip = forwardIp;
 512                         forwardIp = ip + step;
 513
 514                         if unlikely(forwardIp > mflimit) {
 515                                 goto _last_literals;
 516                         }
 517
 518                         forwardH = LZ4_HASH_VALUE(forwardIp);
 519                         ref = base + HashTable[h];
 520                         HashTable[h] = ip - base;
 521
 522                 } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));
 523
 524                 /* Catch up */
 525                 while ((ip > anchor) && (ref > (BYTE *) source) &&
 526                     unlikely(ip[-1] == ref[-1])) {
 527                         ip--;
 528                         ref--;
 529                 }
 530
 531                 /* Encode Literal length */
 532                 length = ip - anchor;
 533                 token = op++;
 534
 535                 /* Check output limit */
 536                 if unlikely(op + length + (2 + 1 + LASTLITERALS) +
 537                     (length >> 8) > oend)
 538                         return (0);
 539
 540                 if (length >= (int)RUN_MASK) {
 541                         *token = (RUN_MASK << ML_BITS);
 542                         len = length - RUN_MASK;
 543                         for (; len > 254; len -= 255)
 544                                 *op++ = 255;
 545                         *op++ = (BYTE)len;
 546                 } else
 547                         *token = (length << ML_BITS);
 548
 549                 /* Copy Literals */
 550                 LZ4_BLINDCOPY(anchor, op, length);
 551
 552                 _next_match:
 553                 /* Encode Offset */
 554                 LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);
 555
 556                 /* Start Counting */
 557                 ip += MINMATCH;
 558                 ref += MINMATCH;        /* MinMatch verified */
 559                 anchor = ip;
 560                 while likely(ip < matchlimit - (STEPSIZE - 1)) {
 561                         UARCH diff = AARCH(ref) ^ AARCH(ip);
 562                         if (!diff) {
 563                                 ip += STEPSIZE;
 564                                 ref += STEPSIZE;
 565                                 continue;
 566                         }
 567                         ip += LZ4_NbCommonBytes(diff);
 568                         goto _endCount;
 569                 }
 570 #if LZ4_ARCH64
 571                 if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
 572                         ip += 4;
 573                         ref += 4;
 574                 }
 575 #endif
 576                 if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
 577                         ip += 2;
 578                         ref += 2;
 579                 }
 580                 if ((ip < matchlimit) && (*ref == *ip))
 581                         ip++;
 582                 _endCount:
 583
 584                 /* Encode MatchLength */
 585                 len = (ip - anchor);
 586                 /* Check output limit */
 587                 if unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend)
 588                         return (0);
 589                 if (len >= (int)ML_MASK) {
 590                         *token += ML_MASK;
 591                         len -= ML_MASK;
 592                         for (; len > 509; len -= 510) {
 593                                 *op++ = 255;
 594                                 *op++ = 255;
 595                         }
 596                         if (len > 254) {
 597                                 len -= 255;
 598                                 *op++ = 255;
 599                         }
 600                         *op++ = (BYTE)len;
 601                 } else
 602                         *token += len;
 603
 604                 /* Test end of chunk */
 605                 if (ip > mflimit) {
 606                         anchor = ip;
 607                         break;
 608                 }
 609                 /* Fill table */
 610                 HashTable[LZ4_HASH_VALUE(ip - 2)] = ip - 2 - base;
 611
 612                 /* Test next position */
 613                 ref = base + HashTable[LZ4_HASH_VALUE(ip)];
 614                 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
 615                 if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) {
 616                         token = op++;
 617                         *token = 0;
 618                         goto _next_match;
 619                 }
 620                 /* Prepare next loop */
 621                 anchor = ip++;
 622                 forwardH = LZ4_HASH_VALUE(ip);
 623         }
 624
 625         _last_literals:
 626         /* Encode Last Literals */
 627         {
 628                 int lastRun = iend - anchor;
 629                 if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) >
 630                     oend)
 631                         return (0);
 632                 if (lastRun >= (int)RUN_MASK) {
 633                         *op++ = (RUN_MASK << ML_BITS);
 634                         lastRun -= RUN_MASK;
 635                         for (; lastRun > 254; lastRun -= 255) {
 636                                 *op++ = 255;
 637                         }
 638                         *op++ = (BYTE)lastRun;
 639                 } else
 640                         *op++ = (lastRun << ML_BITS);
 641                 (void) memcpy(op, anchor, iend - anchor);
 642                 op += iend - anchor;
 643         }
 644
 645         /* End */
 646         return (int)(((char *)op) - dest);
 647 }
 648
 649
 650
 651 /* Note : this function is valid only if isize < LZ4_64KLIMIT */
 652 #define LZ4_64KLIMIT ((1 << 16) + (MFLIMIT - 1))
 653 #define HASHLOG64K (HASH_LOG + 1)
 654 #define HASH64KTABLESIZE (1U << HASHLOG64K)
 655 #define LZ4_HASH64K_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8) - \
 656         HASHLOG64K))
 657 #define LZ4_HASH64K_VALUE(p)    LZ4_HASH64K_FUNCTION(A32(p))
 658
 659 /*ARGSUSED*/
 660 static int
 661 LZ4_compress64kCtx(void *ctx, const char *source, char *dest, int isize,
 662     int osize)
 663 {
 664 #if HEAPMODE
 665         struct refTables *srt = (struct refTables *)ctx;
 666         U16 *HashTable = (U16 *) (srt->hashTable);
 667 #else
 668         U16 HashTable[HASH64KTABLESIZE] = { 0 };
 669 #endif
 670
 671         const BYTE *ip = (BYTE *) source;
 672         const BYTE *anchor = ip;
 673         const BYTE *const base = ip;
 674         const BYTE *const iend = ip + isize;
 675         const BYTE *const oend = (BYTE *) dest + osize;
 676         const BYTE *const mflimit = iend - MFLIMIT;
 677 #define matchlimit (iend - LASTLITERALS)
 678
 679         BYTE *op = (BYTE *) dest;
 680
 681         int len, length;
 682         const int skipStrength = SKIPSTRENGTH;
 683         U32 forwardH;
 684
 685         /* Init */
 686         if (isize < MINLENGTH)
 687                 goto _last_literals;
 688
 689         /* First Byte */
 690         ip++;
 691         forwardH = LZ4_HASH64K_VALUE(ip);
 692
 693         /* Main Loop */
 694         for (;;) {
 695                 int findMatchAttempts = (1U << skipStrength) + 3;
 696                 const BYTE *forwardIp = ip;
 697                 const BYTE *ref;
 698                 BYTE *token;
 699
 700                 /* Find a match */
 701                 do {
 702                         U32 h = forwardH;
 703                         int step = findMatchAttempts++ >> skipStrength;
 704                         ip = forwardIp;
 705                         forwardIp = ip + step;
 706
 707                         if (forwardIp > mflimit) {
 708                                 goto _last_literals;
 709                         }
 710
 711                         forwardH = LZ4_HASH64K_VALUE(forwardIp);
 712                         ref = base + HashTable[h];
 713                         HashTable[h] = ip - base;
 714
 715                 } while (A32(ref) != A32(ip));
 716
 717                 /* Catch up */
 718                 while ((ip > anchor) && (ref > (BYTE *) source) &&
 719                     (ip[-1] == ref[-1])) {
 720                         ip--;
 721                         ref--;
 722                 }
 723
 724                 /* Encode Literal length */
 725                 length = ip - anchor;
 726                 token = op++;
 727
 728                 /* Check output limit */
 729                 if unlikely(op + length + (2 + 1 + LASTLITERALS) +
 730                     (length >> 8) > oend)
 731                         return (0);
 732
 733                 if (length >= (int)RUN_MASK) {
 734                         *token = (RUN_MASK << ML_BITS);
 735                         len = length - RUN_MASK;
 736                         for (; len > 254; len -= 255)
 737                                 *op++ = 255;
 738                         *op++ = (BYTE)len;
 739                 } else
 740                         *token = (length << ML_BITS);
 741
 742                 /* Copy Literals */
 743                 LZ4_BLINDCOPY(anchor, op, length);
 744
 745                 _next_match:
 746                 /* Encode Offset */
 747                 LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);
 748
 749                 /* Start Counting */
 750                 ip += MINMATCH;
 751                 ref += MINMATCH;        /* MinMatch verified */
 752                 anchor = ip;
 753                 while (ip < matchlimit - (STEPSIZE - 1)) {
 754                         UARCH diff = AARCH(ref) ^ AARCH(ip);
 755                         if (!diff) {
 756                                 ip += STEPSIZE;
 757                                 ref += STEPSIZE;
 758                                 continue;
 759                         }
 760                         ip += LZ4_NbCommonBytes(diff);
 761                         goto _endCount;
 762                 }
 763 #if LZ4_ARCH64
 764                 if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
 765                         ip += 4;
 766                         ref += 4;
 767                 }
 768 #endif
 769                 if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
 770                         ip += 2;
 771                         ref += 2;
 772                 }
 773                 if ((ip < matchlimit) && (*ref == *ip))
 774                         ip++;
 775                 _endCount:
 776
 777                 /* Encode MatchLength */
 778                 len = (ip - anchor);
 779                 /* Check output limit */
 780                 if unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend)
 781                         return (0);
 782                 if (len >= (int)ML_MASK) {
 783                         *token += ML_MASK;
 784                         len -= ML_MASK;
 785                         for (; len > 509; len -= 510) {
 786                                 *op++ = 255;
 787                                 *op++ = 255;
 788                         }
 789                         if (len > 254) {
 790                                 len -= 255;
 791                                 *op++ = 255;
 792                         }
 793                         *op++ = (BYTE)len;
 794                 } else
 795                         *token += len;
 796
 797                 /* Test end of chunk */
 798                 if (ip > mflimit) {
 799                         anchor = ip;
 800                         break;
 801                 }
 802                 /* Fill table */
 803                 HashTable[LZ4_HASH64K_VALUE(ip - 2)] = ip - 2 - base;
 804
 805                 /* Test next position */
 806                 ref = base + HashTable[LZ4_HASH64K_VALUE(ip)];
 807                 HashTable[LZ4_HASH64K_VALUE(ip)] = ip - base;
 808                 if (A32(ref) == A32(ip)) {
 809                         token = op++;
 810                         *token = 0;
 811                         goto _next_match;
 812                 }
 813                 /* Prepare next loop */
 814                 anchor = ip++;
 815                 forwardH = LZ4_HASH64K_VALUE(ip);
 816         }
 817
 818         _last_literals:
 819         /* Encode Last Literals */
 820         {
 821                 int lastRun = iend - anchor;
 822                 if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) >
 823                     oend)
 824                         return (0);
 825                 if (lastRun >= (int)RUN_MASK) {
 826                         *op++ = (RUN_MASK << ML_BITS);
 827                         lastRun -= RUN_MASK;
 828                         for (; lastRun > 254; lastRun -= 255)
 829                                 *op++ = 255;
 830                         *op++ = (BYTE)lastRun;
 831                 } else
 832                         *op++ = (lastRun << ML_BITS);
 833                 (void) memcpy(op, anchor, iend - anchor);
 834                 op += iend - anchor;
 835         }
 836
 837         /* End */
 838         return (int)(((char *)op) - dest);
 839 }
 840
 841 static int
 842 real_LZ4_compress(const char *source, char *dest, int isize, int osize)
 843 {
 844 #if HEAPMODE
 845         void *ctx = kmem_cache_alloc(lz4_ctx_cache, KM_NOSLEEP);
 846         int result;
 847
 848         /*
 849          * out of kernel memory, gently fall through - this will disable
 850          * compression in zio_compress_data
 851          */
 852         if (ctx == NULL)
 853                 return (0);
 854
 855         bzero(ctx, sizeof(struct refTables));
 856         if (isize < LZ4_64KLIMIT)
 857                 result = LZ4_compress64kCtx(ctx, source, dest, isize, osize);
 858         else
 859                 result = LZ4_compressCtx(ctx, source, dest, isize, osize);
 860
 861         kmem_cache_free(lz4_ctx_cache, ctx);
 862         return (result);
 863 #else
 864         if (isize < (int)LZ4_64KLIMIT)
 865                 return (LZ4_compress64kCtx(NULL, source, dest, isize, osize));
 866         return (LZ4_compressCtx(NULL, source, dest, isize, osize));
 867 #endif
 868 }
 869
 870 /* Decompression functions */
 871
 872 /*
 873  * Note: The decoding function LZ4_uncompress_unknownOutputSize() is safe
 874  *      against "buffer overflow" attack type. They will never write nor
 875  *      read outside of the provided output buffers.
 876  *      LZ4_uncompress_unknownOutputSize() also insures that it will never
 877  *      read outside of the input buffer.  A corrupted input will produce
 878  *      an error result, a negative int, indicating the position of the
 879  *      error within input stream.
 880  */
 881
 882 static int
 883 LZ4_uncompress_unknownOutputSize(const char *source, char *dest, int isize,
 884     int maxOutputSize)
 885 {
 886         /* Local Variables */
 887         const BYTE *restrict ip = (const BYTE *) source;
 888         const BYTE *const iend = ip + isize;
 889         const BYTE *ref;
 890
 891         BYTE *op = (BYTE *) dest;
 892         BYTE *const oend = op + maxOutputSize;
 893         BYTE *cpy;
 894
 895         size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
 896 #if LZ4_ARCH64
 897         size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
 898 #endif
 899
 900         /* Main Loop */
 901         while (ip < iend) {
 902                 unsigned token;
 903                 size_t length;
 904
 905                 /* get runlength */
 906                 token = *ip++;
 907                 if ((length = (token >> ML_BITS)) == RUN_MASK) {
 908                         int s = 255;
 909                         while ((ip < iend) && (s == 255)) {
 910                                 s = *ip++;
 911                                 length += s;
 912                         }
 913                 }
 914                 /* copy literals */
 915                 cpy = op + length;
 916                 /* CORNER-CASE: cpy might overflow. */
 917                 if (cpy < op)
 918                         goto _output_error;     /* cpy was overflowed, bail! */
 919                 if ((cpy > oend - COPYLENGTH) ||
 920                     (ip + length > iend - COPYLENGTH)) {
 921                         if (cpy > oend)
 922                                 /* Error: writes beyond output buffer */
 923                                 goto _output_error;
 924                         if (ip + length != iend)
 925                                 /*
 926                                  * Error: LZ4 format requires to consume all
 927                                  * input at this stage
 928                                  */
 929                                 goto _output_error;
 930                         (void) memcpy(op, ip, length);
 931                         op += length;
 932                         /* Necessarily EOF, due to parsing restrictions */
 933                         break;
 934                 }
 935                 LZ4_WILDCOPY(ip, op, cpy);
 936                 ip -= (op - cpy);
 937                 op = cpy;
 938
 939                 /* get offset */
 940                 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
 941                 ip += 2;
 942                 if (ref < (BYTE * const) dest)
 943                         /*
 944                          * Error: offset creates reference outside of
 945                          * destination buffer
 946                          */
 947                         goto _output_error;
 948
 949                 /* get matchlength */
 950                 if ((length = (token & ML_MASK)) == ML_MASK) {
 951                         while (ip < iend) {
 952                                 int s = *ip++;
 953                                 length += s;
 954                                 if (s == 255)
 955                                         continue;
 956                                 break;
 957                         }
 958                 }
 959                 /* copy repeated sequence */
 960                 if unlikely(op - ref < STEPSIZE) {
 961 #if LZ4_ARCH64
 962                         size_t dec64 = dec64table[op-ref];
 963 #else
 964                         const int dec64 = 0;
 965 #endif
 966                         op[0] = ref[0];
 967                         op[1] = ref[1];
 968                         op[2] = ref[2];
 969                         op[3] = ref[3];
 970                         op += 4;
 971                         ref += 4;
 972                         ref -= dec32table[op-ref];
 973                         A32(op) = A32(ref);
 974                         op += STEPSIZE - 4;
 975                         ref -= dec64;
 976                 } else {
 977                         LZ4_COPYSTEP(ref, op);
 978                 }
 979                 cpy = op + length - (STEPSIZE - 4);
 980                 if (cpy > oend - COPYLENGTH) {
 981                         if (cpy > oend)
 982                                 /*
 983                                  * Error: request to write outside of
 984                                  * destination buffer
 985                                  */
 986                                 goto _output_error;
 987                         LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
 988                         while (op < cpy)
 989                                 *op++ = *ref++;
 990                         op = cpy;
 991                         if (op == oend)
 992                                 /*
 993                                  * Check EOF (should never happen, since
 994                                  * last 5 bytes are supposed to be literals)
 995                                  */
 996                                 goto _output_error;
 997                         continue;
 998                 }
 999                 LZ4_SECURECOPY(ref, op, cpy);
1000                 op = cpy;       /* correction */
1001         }
1002
1003         /* end of decoding */
1004         return (int)(((char *)op) - dest);
1005
1006         /* write overflow error detected */
1007         _output_error:
1008         return (int)(-(((char *)ip) - source));
1009 }
1010
1011 extern void
1012 lz4_init(void)
1013 {
1014
1015 #if HEAPMODE
1016         lz4_ctx_cache = kmem_cache_create("lz4_ctx", sizeof(struct refTables),
1017             0, NULL, NULL, NULL, NULL, NULL, 0);
1018 #endif
1019 }
1020
1021 extern void
1022 lz4_fini(void)
1023 {
1024
1025 #if HEAPMODE
1026         kmem_cache_destroy(lz4_ctx_cache);
1027 #endif
1028 }