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