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