lz4.c

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

FreeBSD/Linux Kernel Cross Reference
sys/cddl/contrib/opensolaris/common/lz4/lz4.c
