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