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