1245512Sdelphij/* 2245512Sdelphij * LZ4 - Fast LZ compression algorithm 3245512Sdelphij * Header File 4245512Sdelphij * Copyright (C) 2011-2013, Yann Collet. 5245512Sdelphij * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 6245512Sdelphij * 7245512Sdelphij * Redistribution and use in source and binary forms, with or without 8245512Sdelphij * modification, are permitted provided that the following conditions are 9245512Sdelphij * met: 10245512Sdelphij * 11245512Sdelphij * * Redistributions of source code must retain the above copyright 12245512Sdelphij * notice, this list of conditions and the following disclaimer. 13245512Sdelphij * * Redistributions in binary form must reproduce the above 14245512Sdelphij * copyright notice, this list of conditions and the following disclaimer 15245512Sdelphij * in the documentation and/or other materials provided with the 16245512Sdelphij * distribution. 17245512Sdelphij * 18245512Sdelphij * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19245512Sdelphij * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20245512Sdelphij * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21245512Sdelphij * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22245512Sdelphij * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23245512Sdelphij * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24245512Sdelphij * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25245512Sdelphij * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26245512Sdelphij * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27245512Sdelphij * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28245512Sdelphij * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29245512Sdelphij * 30245512Sdelphij * You can contact the author at : 31245512Sdelphij * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html 32245512Sdelphij * - LZ4 source repository : http://code.google.com/p/lz4/ 33245512Sdelphij */ 34245512Sdelphij 35245512Sdelphij#include <sys/zfs_context.h> 36245512Sdelphij 37245512Sdelphijstatic int real_LZ4_compress(const char *source, char *dest, int isize, 38245512Sdelphij int osize); 39245512Sdelphijstatic int LZ4_compressBound(int isize); 40245512Sdelphijstatic int LZ4_uncompress_unknownOutputSize(const char *source, char *dest, 41245512Sdelphij int isize, int maxOutputSize); 42245512Sdelphijstatic int LZ4_compressCtx(void *ctx, const char *source, char *dest, 43245512Sdelphij int isize, int osize); 44245512Sdelphijstatic int LZ4_compress64kCtx(void *ctx, const char *source, char *dest, 45245512Sdelphij int isize, int osize); 46245512Sdelphij 47262164Smavstatic kmem_cache_t *lz4_ctx_cache; 48262164Smav 49245512Sdelphij/*ARGSUSED*/ 50245512Sdelphijsize_t 51245512Sdelphijlz4_compress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n) 52245512Sdelphij{ 53245512Sdelphij uint32_t bufsiz; 54245512Sdelphij char *dest = d_start; 55245512Sdelphij 56245512Sdelphij ASSERT(d_len >= sizeof (bufsiz)); 57245512Sdelphij 58245512Sdelphij bufsiz = real_LZ4_compress(s_start, &dest[sizeof (bufsiz)], s_len, 59245512Sdelphij d_len - sizeof (bufsiz)); 60245512Sdelphij 61245512Sdelphij /* Signal an error if the compression routine returned zero. */ 62245512Sdelphij if (bufsiz == 0) 63245512Sdelphij return (s_len); 64245512Sdelphij 65245512Sdelphij /* 66245512Sdelphij * Encode the compresed buffer size at the start. We'll need this in 67245512Sdelphij * decompression to counter the effects of padding which might be 68245512Sdelphij * added to the compressed buffer and which, if unhandled, would 69245512Sdelphij * confuse the hell out of our decompression function. 70245512Sdelphij */ 71245512Sdelphij *(uint32_t *)dest = BE_32(bufsiz); 72245512Sdelphij 73245512Sdelphij return (bufsiz + sizeof (bufsiz)); 74245512Sdelphij} 75245512Sdelphij 76245512Sdelphij/*ARGSUSED*/ 77245512Sdelphijint 78245512Sdelphijlz4_decompress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n) 79245512Sdelphij{ 80245512Sdelphij const char *src = s_start; 81245512Sdelphij uint32_t bufsiz = BE_IN32(src); 82245512Sdelphij 83245512Sdelphij /* invalid compressed buffer size encoded at start */ 84245512Sdelphij if (bufsiz + sizeof (bufsiz) > s_len) 85245512Sdelphij return (1); 86245512Sdelphij 87245512Sdelphij /* 88245512Sdelphij * Returns 0 on success (decompression function returned non-negative) 89245512Sdelphij * and non-zero on failure (decompression function returned negative. 90245512Sdelphij */ 91245512Sdelphij return (LZ4_uncompress_unknownOutputSize(&src[sizeof (bufsiz)], 92245512Sdelphij d_start, bufsiz, d_len) < 0); 93245512Sdelphij} 94245512Sdelphij 95245512Sdelphij/* 96245512Sdelphij * LZ4 API Description: 97245512Sdelphij * 98245512Sdelphij * Simple Functions: 99245512Sdelphij * real_LZ4_compress() : 100245512Sdelphij * isize : is the input size. Max supported value is ~1.9GB 101245512Sdelphij * return : the number of bytes written in buffer dest 102245512Sdelphij * or 0 if the compression fails (if LZ4_COMPRESSMIN is set). 103245512Sdelphij * note : destination buffer must be already allocated. 104245512Sdelphij * destination buffer must be sized to handle worst cases 105245512Sdelphij * situations (input data not compressible) worst case size 106245512Sdelphij * evaluation is provided by function LZ4_compressBound(). 107245512Sdelphij * 108245512Sdelphij * Advanced Functions 109245512Sdelphij * 110245512Sdelphij * LZ4_compressBound() : 111245512Sdelphij * Provides the maximum size that LZ4 may output in a "worst case" 112245512Sdelphij * scenario (input data not compressible) primarily useful for memory 113245512Sdelphij * allocation of output buffer. 114245512Sdelphij * 115245512Sdelphij * isize : is the input size. Max supported value is ~1.9GB 116245512Sdelphij * return : maximum output size in a "worst case" scenario 117245512Sdelphij * note : this function is limited by "int" range (2^31-1) 118245512Sdelphij * 119245512Sdelphij * LZ4_uncompress_unknownOutputSize() : 120245512Sdelphij * isize : is the input size, therefore the compressed size 121245512Sdelphij * maxOutputSize : is the size of the destination buffer (which must be 122245512Sdelphij * already allocated) 123245512Sdelphij * return : the number of bytes decoded in the destination buffer 124245512Sdelphij * (necessarily <= maxOutputSize). If the source stream is 125245512Sdelphij * malformed, the function will stop decoding and return a 126245512Sdelphij * negative result, indicating the byte position of the faulty 127245512Sdelphij * instruction. This function never writes beyond dest + 128245512Sdelphij * maxOutputSize, and is therefore protected against malicious 129245512Sdelphij * data packets. 130245512Sdelphij * note : Destination buffer must be already allocated. 131245512Sdelphij * 132245512Sdelphij * LZ4_compressCtx() : 133245512Sdelphij * This function explicitly handles the CTX memory structure. 134245512Sdelphij * 135245512Sdelphij * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated 136245512Sdelphij * by the caller (either on the stack or using kmem_zalloc). Passing NULL 137245512Sdelphij * isn't valid. 138245512Sdelphij * 139245512Sdelphij * LZ4_compress64kCtx() : 140245512Sdelphij * Same as LZ4_compressCtx(), but specific to small inputs (<64KB). 141245512Sdelphij * isize *Must* be <64KB, otherwise the output will be corrupted. 142245512Sdelphij * 143245512Sdelphij * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated 144245512Sdelphij * by the caller (either on the stack or using kmem_zalloc). Passing NULL 145245512Sdelphij * isn't valid. 146245512Sdelphij */ 147245512Sdelphij 148245512Sdelphij/* 149245512Sdelphij * Tuning parameters 150245512Sdelphij */ 151245512Sdelphij 152245512Sdelphij/* 153245512Sdelphij * COMPRESSIONLEVEL: Increasing this value improves compression ratio 154245512Sdelphij * Lowering this value reduces memory usage. Reduced memory usage 155245512Sdelphij * typically improves speed, due to cache effect (ex: L1 32KB for Intel, 156245512Sdelphij * L1 64KB for AMD). Memory usage formula : N->2^(N+2) Bytes 157245512Sdelphij * (examples : 12 -> 16KB ; 17 -> 512KB) 158245512Sdelphij */ 159245512Sdelphij#define COMPRESSIONLEVEL 12 160245512Sdelphij 161245512Sdelphij/* 162245512Sdelphij * NOTCOMPRESSIBLE_CONFIRMATION: Decreasing this value will make the 163245512Sdelphij * algorithm skip faster data segments considered "incompressible". 164245512Sdelphij * This may decrease compression ratio dramatically, but will be 165245512Sdelphij * faster on incompressible data. Increasing this value will make 166245512Sdelphij * the algorithm search more before declaring a segment "incompressible". 167245512Sdelphij * This could improve compression a bit, but will be slower on 168245512Sdelphij * incompressible data. The default value (6) is recommended. 169245512Sdelphij */ 170245512Sdelphij#define NOTCOMPRESSIBLE_CONFIRMATION 6 171245512Sdelphij 172245512Sdelphij/* 173245512Sdelphij * BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE: This will provide a boost to 174245512Sdelphij * performance for big endian cpu, but the resulting compressed stream 175245512Sdelphij * will be incompatible with little-endian CPU. You can set this option 176245512Sdelphij * to 1 in situations where data will stay within closed environment. 177245512Sdelphij * This option is useless on Little_Endian CPU (such as x86). 178245512Sdelphij */ 179245512Sdelphij/* #define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1 */ 180245512Sdelphij 181245512Sdelphij/* 182245512Sdelphij * CPU Feature Detection 183245512Sdelphij */ 184245512Sdelphij 185245512Sdelphij/* 32 or 64 bits ? */ 186245512Sdelphij#if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || \ 187245512Sdelphij defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || \ 188245512Sdelphij defined(__LP64__) || defined(_LP64)) 189245512Sdelphij#define LZ4_ARCH64 1 190245512Sdelphij/* 191245512Sdelphij * Illumos: On amd64 we have 20k of stack and 24k on sun4u and sun4v, so we 192245512Sdelphij * can spend 16k on the algorithm 193245512Sdelphij */ 194246586Sdelphij/* FreeBSD: Use heap for all platforms for now */ 195246586Sdelphij#define STACKLIMIT 0 196245512Sdelphij#else 197245512Sdelphij#define LZ4_ARCH64 0 198245512Sdelphij/* 199245512Sdelphij * Illumos: On i386 we only have 12k of stack, so in order to maintain the 200245512Sdelphij * same COMPRESSIONLEVEL we have to use heap allocation. Performance will 201245512Sdelphij * suck, but alas, it's ZFS on 32-bit we're talking about, so... 202245512Sdelphij */ 203246586Sdelphij#define STACKLIMIT 0 204245512Sdelphij#endif 205245512Sdelphij 206245512Sdelphij/* 207245512Sdelphij * Little Endian or Big Endian? 208245512Sdelphij * Note: overwrite the below #define if you know your architecture endianess. 209245512Sdelphij */ 210246586Sdelphij#if BYTE_ORDER == BIG_ENDIAN 211245512Sdelphij#define LZ4_BIG_ENDIAN 1 212245512Sdelphij#else 213245512Sdelphij/* 214245512Sdelphij * Little Endian assumed. PDP Endian and other very rare endian format 215245512Sdelphij * are unsupported. 216245512Sdelphij */ 217245512Sdelphij#endif 218245512Sdelphij 219245512Sdelphij/* 220245512Sdelphij * Unaligned memory access is automatically enabled for "common" CPU, 221245512Sdelphij * such as x86. For others CPU, the compiler will be more cautious, and 222245512Sdelphij * insert extra code to ensure aligned access is respected. If you know 223245512Sdelphij * your target CPU supports unaligned memory access, you may want to 224245512Sdelphij * force this option manually to improve performance 225245512Sdelphij */ 226245512Sdelphij#if defined(__ARM_FEATURE_UNALIGNED) 227245512Sdelphij#define LZ4_FORCE_UNALIGNED_ACCESS 1 228245512Sdelphij#endif 229245512Sdelphij 230245512Sdelphij/* 231247309Sdelphij * FreeBSD: can't use GCC's __builtin_ctz when using sparc64 because 232247309Sdelphij * gcc currently rely on libcompiler_rt. 233247309Sdelphij * 234247309Sdelphij * TODO: revisit this when situation changes. 235247309Sdelphij */ 236247309Sdelphij#if defined(__sparc64__) 237247309Sdelphij#define LZ4_FORCE_SW_BITCOUNT 238247309Sdelphij#endif 239247309Sdelphij 240247309Sdelphij/* 241245512Sdelphij * Compiler Options 242245512Sdelphij */ 243245512Sdelphij#if __STDC_VERSION__ >= 199901L /* C99 */ 244245512Sdelphij/* "restrict" is a known keyword */ 245245512Sdelphij#else 246245512Sdelphij/* Disable restrict */ 247245512Sdelphij#define restrict 248245512Sdelphij#endif 249245512Sdelphij 250245512Sdelphij#define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | \ 251245512Sdelphij (((x) & 0xffu) << 8))) 252245512Sdelphij 253245512Sdelphij#define expect(expr, value) (__builtin_expect((expr), (value))) 254246586Sdelphij 255246586Sdelphij#if defined(likely) 256246586Sdelphij#undef likely 257245512Sdelphij#endif 258246586Sdelphij#if defined(unlikely) 259246586Sdelphij#undef unlikely 260246586Sdelphij#endif 261245512Sdelphij 262245512Sdelphij#define likely(expr) expect((expr) != 0, 1) 263245512Sdelphij#define unlikely(expr) expect((expr) != 0, 0) 264245512Sdelphij 265245512Sdelphij/* Basic types */ 266245512Sdelphij#define BYTE uint8_t 267245512Sdelphij#define U16 uint16_t 268245512Sdelphij#define U32 uint32_t 269245512Sdelphij#define S32 int32_t 270245512Sdelphij#define U64 uint64_t 271245512Sdelphij 272245512Sdelphij#ifndef LZ4_FORCE_UNALIGNED_ACCESS 273245512Sdelphij#pragma pack(1) 274245512Sdelphij#endif 275245512Sdelphij 276245512Sdelphijtypedef struct _U16_S { 277245512Sdelphij U16 v; 278245512Sdelphij} U16_S; 279245512Sdelphijtypedef struct _U32_S { 280245512Sdelphij U32 v; 281245512Sdelphij} U32_S; 282245512Sdelphijtypedef struct _U64_S { 283245512Sdelphij U64 v; 284245512Sdelphij} U64_S; 285245512Sdelphij 286245512Sdelphij#ifndef LZ4_FORCE_UNALIGNED_ACCESS 287245512Sdelphij#pragma pack() 288245512Sdelphij#endif 289245512Sdelphij 290245512Sdelphij#define A64(x) (((U64_S *)(x))->v) 291245512Sdelphij#define A32(x) (((U32_S *)(x))->v) 292245512Sdelphij#define A16(x) (((U16_S *)(x))->v) 293245512Sdelphij 294245512Sdelphij/* 295245512Sdelphij * Constants 296245512Sdelphij */ 297245512Sdelphij#define MINMATCH 4 298245512Sdelphij 299245512Sdelphij#define HASH_LOG COMPRESSIONLEVEL 300245512Sdelphij#define HASHTABLESIZE (1 << HASH_LOG) 301245512Sdelphij#define HASH_MASK (HASHTABLESIZE - 1) 302245512Sdelphij 303245512Sdelphij#define SKIPSTRENGTH (NOTCOMPRESSIBLE_CONFIRMATION > 2 ? \ 304245512Sdelphij NOTCOMPRESSIBLE_CONFIRMATION : 2) 305245512Sdelphij 306245512Sdelphij/* 307245512Sdelphij * Defines if memory is allocated into the stack (local variable), 308245512Sdelphij * or into the heap (kmem_alloc()). 309245512Sdelphij */ 310245512Sdelphij#define HEAPMODE (HASH_LOG > STACKLIMIT) 311245512Sdelphij#define COPYLENGTH 8 312245512Sdelphij#define LASTLITERALS 5 313245512Sdelphij#define MFLIMIT (COPYLENGTH + MINMATCH) 314245512Sdelphij#define MINLENGTH (MFLIMIT + 1) 315245512Sdelphij 316245512Sdelphij#define MAXD_LOG 16 317245512Sdelphij#define MAX_DISTANCE ((1 << MAXD_LOG) - 1) 318245512Sdelphij 319245512Sdelphij#define ML_BITS 4 320245512Sdelphij#define ML_MASK ((1U<<ML_BITS)-1) 321245512Sdelphij#define RUN_BITS (8-ML_BITS) 322245512Sdelphij#define RUN_MASK ((1U<<RUN_BITS)-1) 323245512Sdelphij 324245512Sdelphij 325245512Sdelphij/* 326245512Sdelphij * Architecture-specific macros 327245512Sdelphij */ 328245512Sdelphij#if LZ4_ARCH64 329245512Sdelphij#define STEPSIZE 8 330245512Sdelphij#define UARCH U64 331245512Sdelphij#define AARCH A64 332245512Sdelphij#define LZ4_COPYSTEP(s, d) A64(d) = A64(s); d += 8; s += 8; 333245512Sdelphij#define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d) 334245512Sdelphij#define LZ4_SECURECOPY(s, d, e) if (d < e) LZ4_WILDCOPY(s, d, e) 335245512Sdelphij#define HTYPE U32 336245512Sdelphij#define INITBASE(base) const BYTE* const base = ip 337245512Sdelphij#else /* !LZ4_ARCH64 */ 338245512Sdelphij#define STEPSIZE 4 339245512Sdelphij#define UARCH U32 340245512Sdelphij#define AARCH A32 341245512Sdelphij#define LZ4_COPYSTEP(s, d) A32(d) = A32(s); d += 4; s += 4; 342245512Sdelphij#define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d); LZ4_COPYSTEP(s, d); 343245512Sdelphij#define LZ4_SECURECOPY LZ4_WILDCOPY 344245512Sdelphij#define HTYPE const BYTE * 345245512Sdelphij#define INITBASE(base) const int base = 0 346245512Sdelphij#endif /* !LZ4_ARCH64 */ 347245512Sdelphij 348245512Sdelphij#if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE)) 349245512Sdelphij#define LZ4_READ_LITTLEENDIAN_16(d, s, p) \ 350245512Sdelphij { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; } 351245512Sdelphij#define LZ4_WRITE_LITTLEENDIAN_16(p, i) \ 352245512Sdelphij { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p += 2; } 353245512Sdelphij#else 354245512Sdelphij#define LZ4_READ_LITTLEENDIAN_16(d, s, p) { d = (s) - A16(p); } 355245512Sdelphij#define LZ4_WRITE_LITTLEENDIAN_16(p, v) { A16(p) = v; p += 2; } 356245512Sdelphij#endif 357245512Sdelphij 358245512Sdelphij 359245512Sdelphij/* Local structures */ 360245512Sdelphijstruct refTables { 361245512Sdelphij HTYPE hashTable[HASHTABLESIZE]; 362245512Sdelphij}; 363245512Sdelphij 364245512Sdelphij 365245512Sdelphij/* Macros */ 366245512Sdelphij#define LZ4_HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH * 8) - \ 367245512Sdelphij HASH_LOG)) 368245512Sdelphij#define LZ4_HASH_VALUE(p) LZ4_HASH_FUNCTION(A32(p)) 369245512Sdelphij#define LZ4_WILDCOPY(s, d, e) do { LZ4_COPYPACKET(s, d) } while (d < e); 370245512Sdelphij#define LZ4_BLINDCOPY(s, d, l) { BYTE* e = (d) + l; LZ4_WILDCOPY(s, d, e); \ 371245512Sdelphij d = e; } 372245512Sdelphij 373245512Sdelphij 374245512Sdelphij/* Private functions */ 375245512Sdelphij#if LZ4_ARCH64 376245512Sdelphij 377245512Sdelphijstatic inline int 378245512SdelphijLZ4_NbCommonBytes(register U64 val) 379245512Sdelphij{ 380245512Sdelphij#if defined(LZ4_BIG_ENDIAN) 381247309Sdelphij#if !defined(LZ4_FORCE_SW_BITCOUNT) 382245512Sdelphij return (__builtin_clzll(val) >> 3); 383245512Sdelphij#else 384247309Sdelphij int r; 385247309Sdelphij if (!(val >> 32)) { 386247309Sdelphij r = 4; 387247309Sdelphij } else { 388247309Sdelphij r = 0; 389247309Sdelphij val >>= 32; 390247309Sdelphij } 391247309Sdelphij if (!(val >> 16)) { 392247309Sdelphij r += 2; 393247309Sdelphij val >>= 8; 394247309Sdelphij } else { 395247309Sdelphij val >>= 24; 396247309Sdelphij } 397247309Sdelphij r += (!val); 398247309Sdelphij return (r); 399247309Sdelphij#endif 400247309Sdelphij#else 401247309Sdelphij#if !defined(LZ4_FORCE_SW_BITCOUNT) 402245512Sdelphij return (__builtin_ctzll(val) >> 3); 403247309Sdelphij#else 404247309Sdelphij static const int DeBruijnBytePos[64] = 405247309Sdelphij { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 406247309Sdelphij 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 407247309Sdelphij 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 408247309Sdelphij 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 409247309Sdelphij }; 410247309Sdelphij return DeBruijnBytePos[((U64) ((val & -val) * 0x0218A392CDABBD3F)) >> 411247309Sdelphij 58]; 412245512Sdelphij#endif 413247309Sdelphij#endif 414245512Sdelphij} 415245512Sdelphij 416245512Sdelphij#else 417245512Sdelphij 418245512Sdelphijstatic inline int 419245512SdelphijLZ4_NbCommonBytes(register U32 val) 420245512Sdelphij{ 421245512Sdelphij#if defined(LZ4_BIG_ENDIAN) 422247309Sdelphij#if !defined(LZ4_FORCE_SW_BITCOUNT) 423245512Sdelphij return (__builtin_clz(val) >> 3); 424245512Sdelphij#else 425247309Sdelphij int r; 426247309Sdelphij if (!(val >> 16)) { 427247309Sdelphij r = 2; 428247309Sdelphij val >>= 8; 429247309Sdelphij } else { 430247309Sdelphij r = 0; 431247309Sdelphij val >>= 24; 432247309Sdelphij } 433247309Sdelphij r += (!val); 434247309Sdelphij return (r); 435247309Sdelphij#endif 436247309Sdelphij#else 437247309Sdelphij#if !defined(LZ4_FORCE_SW_BITCOUNT) 438245512Sdelphij return (__builtin_ctz(val) >> 3); 439247309Sdelphij#else 440247309Sdelphij static const int DeBruijnBytePos[32] = { 441247309Sdelphij 0, 0, 3, 0, 3, 1, 3, 0, 442247309Sdelphij 3, 2, 2, 1, 3, 2, 0, 1, 443247309Sdelphij 3, 3, 1, 2, 2, 2, 2, 0, 444247309Sdelphij 3, 1, 2, 0, 1, 0, 1, 1 445247309Sdelphij }; 446247309Sdelphij return DeBruijnBytePos[((U32) ((val & -(S32) val) * 0x077CB531U)) >> 447247309Sdelphij 27]; 448245512Sdelphij#endif 449247309Sdelphij#endif 450245512Sdelphij} 451245512Sdelphij 452245512Sdelphij#endif 453245512Sdelphij 454245512Sdelphij/* Public functions */ 455245512Sdelphij 456245512Sdelphijstatic int 457245512SdelphijLZ4_compressBound(int isize) 458245512Sdelphij{ 459245512Sdelphij return (isize + (isize / 255) + 16); 460245512Sdelphij} 461245512Sdelphij 462245512Sdelphij/* Compression functions */ 463245512Sdelphij 464245512Sdelphij/*ARGSUSED*/ 465245512Sdelphijstatic int 466245512SdelphijLZ4_compressCtx(void *ctx, const char *source, char *dest, int isize, 467245512Sdelphij int osize) 468245512Sdelphij{ 469245512Sdelphij#if HEAPMODE 470245512Sdelphij struct refTables *srt = (struct refTables *)ctx; 471245512Sdelphij HTYPE *HashTable = (HTYPE *) (srt->hashTable); 472245512Sdelphij#else 473245512Sdelphij HTYPE HashTable[HASHTABLESIZE] = { 0 }; 474245512Sdelphij#endif 475245512Sdelphij 476245512Sdelphij const BYTE *ip = (BYTE *) source; 477245512Sdelphij INITBASE(base); 478245512Sdelphij const BYTE *anchor = ip; 479245512Sdelphij const BYTE *const iend = ip + isize; 480245512Sdelphij const BYTE *const oend = (BYTE *) dest + osize; 481245512Sdelphij const BYTE *const mflimit = iend - MFLIMIT; 482245512Sdelphij#define matchlimit (iend - LASTLITERALS) 483245512Sdelphij 484245512Sdelphij BYTE *op = (BYTE *) dest; 485245512Sdelphij 486245512Sdelphij int len, length; 487245512Sdelphij const int skipStrength = SKIPSTRENGTH; 488245512Sdelphij U32 forwardH; 489245512Sdelphij 490245512Sdelphij 491245512Sdelphij /* Init */ 492245512Sdelphij if (isize < MINLENGTH) 493245512Sdelphij goto _last_literals; 494245512Sdelphij 495245512Sdelphij /* First Byte */ 496245512Sdelphij HashTable[LZ4_HASH_VALUE(ip)] = ip - base; 497245512Sdelphij ip++; 498245512Sdelphij forwardH = LZ4_HASH_VALUE(ip); 499245512Sdelphij 500245512Sdelphij /* Main Loop */ 501245512Sdelphij for (;;) { 502245512Sdelphij int findMatchAttempts = (1U << skipStrength) + 3; 503245512Sdelphij const BYTE *forwardIp = ip; 504245512Sdelphij const BYTE *ref; 505245512Sdelphij BYTE *token; 506245512Sdelphij 507245512Sdelphij /* Find a match */ 508245512Sdelphij do { 509245512Sdelphij U32 h = forwardH; 510245512Sdelphij int step = findMatchAttempts++ >> skipStrength; 511245512Sdelphij ip = forwardIp; 512245512Sdelphij forwardIp = ip + step; 513245512Sdelphij 514245512Sdelphij if unlikely(forwardIp > mflimit) { 515245512Sdelphij goto _last_literals; 516245512Sdelphij } 517245512Sdelphij 518245512Sdelphij forwardH = LZ4_HASH_VALUE(forwardIp); 519245512Sdelphij ref = base + HashTable[h]; 520245512Sdelphij HashTable[h] = ip - base; 521245512Sdelphij 522245512Sdelphij } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip))); 523245512Sdelphij 524245512Sdelphij /* Catch up */ 525245512Sdelphij while ((ip > anchor) && (ref > (BYTE *) source) && 526245512Sdelphij unlikely(ip[-1] == ref[-1])) { 527245512Sdelphij ip--; 528245512Sdelphij ref--; 529245512Sdelphij } 530245512Sdelphij 531245512Sdelphij /* Encode Literal length */ 532245512Sdelphij length = ip - anchor; 533245512Sdelphij token = op++; 534245512Sdelphij 535245512Sdelphij /* Check output limit */ 536245512Sdelphij if unlikely(op + length + (2 + 1 + LASTLITERALS) + 537245512Sdelphij (length >> 8) > oend) 538245512Sdelphij return (0); 539245512Sdelphij 540245512Sdelphij if (length >= (int)RUN_MASK) { 541245512Sdelphij *token = (RUN_MASK << ML_BITS); 542245512Sdelphij len = length - RUN_MASK; 543245512Sdelphij for (; len > 254; len -= 255) 544245512Sdelphij *op++ = 255; 545245512Sdelphij *op++ = (BYTE)len; 546245512Sdelphij } else 547245512Sdelphij *token = (length << ML_BITS); 548245512Sdelphij 549245512Sdelphij /* Copy Literals */ 550245512Sdelphij LZ4_BLINDCOPY(anchor, op, length); 551245512Sdelphij 552245512Sdelphij _next_match: 553245512Sdelphij /* Encode Offset */ 554245512Sdelphij LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref); 555245512Sdelphij 556245512Sdelphij /* Start Counting */ 557245512Sdelphij ip += MINMATCH; 558245512Sdelphij ref += MINMATCH; /* MinMatch verified */ 559245512Sdelphij anchor = ip; 560245512Sdelphij while likely(ip < matchlimit - (STEPSIZE - 1)) { 561245512Sdelphij UARCH diff = AARCH(ref) ^ AARCH(ip); 562245512Sdelphij if (!diff) { 563245512Sdelphij ip += STEPSIZE; 564245512Sdelphij ref += STEPSIZE; 565245512Sdelphij continue; 566245512Sdelphij } 567245512Sdelphij ip += LZ4_NbCommonBytes(diff); 568245512Sdelphij goto _endCount; 569245512Sdelphij } 570245512Sdelphij#if LZ4_ARCH64 571245512Sdelphij if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) { 572245512Sdelphij ip += 4; 573245512Sdelphij ref += 4; 574245512Sdelphij } 575245512Sdelphij#endif 576245512Sdelphij if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) { 577245512Sdelphij ip += 2; 578245512Sdelphij ref += 2; 579245512Sdelphij } 580245512Sdelphij if ((ip < matchlimit) && (*ref == *ip)) 581245512Sdelphij ip++; 582245512Sdelphij _endCount: 583245512Sdelphij 584245512Sdelphij /* Encode MatchLength */ 585245512Sdelphij len = (ip - anchor); 586245512Sdelphij /* Check output limit */ 587245512Sdelphij if unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend) 588245512Sdelphij return (0); 589245512Sdelphij if (len >= (int)ML_MASK) { 590245512Sdelphij *token += ML_MASK; 591245512Sdelphij len -= ML_MASK; 592245512Sdelphij for (; len > 509; len -= 510) { 593245512Sdelphij *op++ = 255; 594245512Sdelphij *op++ = 255; 595245512Sdelphij } 596245512Sdelphij if (len > 254) { 597245512Sdelphij len -= 255; 598245512Sdelphij *op++ = 255; 599245512Sdelphij } 600245512Sdelphij *op++ = (BYTE)len; 601245512Sdelphij } else 602245512Sdelphij *token += len; 603245512Sdelphij 604245512Sdelphij /* Test end of chunk */ 605245512Sdelphij if (ip > mflimit) { 606245512Sdelphij anchor = ip; 607245512Sdelphij break; 608245512Sdelphij } 609245512Sdelphij /* Fill table */ 610245512Sdelphij HashTable[LZ4_HASH_VALUE(ip - 2)] = ip - 2 - base; 611245512Sdelphij 612245512Sdelphij /* Test next position */ 613245512Sdelphij ref = base + HashTable[LZ4_HASH_VALUE(ip)]; 614245512Sdelphij HashTable[LZ4_HASH_VALUE(ip)] = ip - base; 615245512Sdelphij if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) { 616245512Sdelphij token = op++; 617245512Sdelphij *token = 0; 618245512Sdelphij goto _next_match; 619245512Sdelphij } 620245512Sdelphij /* Prepare next loop */ 621245512Sdelphij anchor = ip++; 622245512Sdelphij forwardH = LZ4_HASH_VALUE(ip); 623245512Sdelphij } 624245512Sdelphij 625245512Sdelphij _last_literals: 626245512Sdelphij /* Encode Last Literals */ 627245512Sdelphij { 628245512Sdelphij int lastRun = iend - anchor; 629245512Sdelphij if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) > 630245512Sdelphij oend) 631245512Sdelphij return (0); 632245512Sdelphij if (lastRun >= (int)RUN_MASK) { 633245512Sdelphij *op++ = (RUN_MASK << ML_BITS); 634245512Sdelphij lastRun -= RUN_MASK; 635245512Sdelphij for (; lastRun > 254; lastRun -= 255) { 636245512Sdelphij *op++ = 255; 637245512Sdelphij } 638245512Sdelphij *op++ = (BYTE)lastRun; 639245512Sdelphij } else 640245512Sdelphij *op++ = (lastRun << ML_BITS); 641245512Sdelphij (void) memcpy(op, anchor, iend - anchor); 642245512Sdelphij op += iend - anchor; 643245512Sdelphij } 644245512Sdelphij 645245512Sdelphij /* End */ 646245512Sdelphij return (int)(((char *)op) - dest); 647245512Sdelphij} 648245512Sdelphij 649245512Sdelphij 650245512Sdelphij 651245512Sdelphij/* Note : this function is valid only if isize < LZ4_64KLIMIT */ 652245512Sdelphij#define LZ4_64KLIMIT ((1 << 16) + (MFLIMIT - 1)) 653245512Sdelphij#define HASHLOG64K (HASH_LOG + 1) 654245512Sdelphij#define HASH64KTABLESIZE (1U << HASHLOG64K) 655245512Sdelphij#define LZ4_HASH64K_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8) - \ 656245512Sdelphij HASHLOG64K)) 657245512Sdelphij#define LZ4_HASH64K_VALUE(p) LZ4_HASH64K_FUNCTION(A32(p)) 658245512Sdelphij 659245512Sdelphij/*ARGSUSED*/ 660245512Sdelphijstatic int 661245512SdelphijLZ4_compress64kCtx(void *ctx, const char *source, char *dest, int isize, 662245512Sdelphij int osize) 663245512Sdelphij{ 664245512Sdelphij#if HEAPMODE 665245512Sdelphij struct refTables *srt = (struct refTables *)ctx; 666245512Sdelphij U16 *HashTable = (U16 *) (srt->hashTable); 667245512Sdelphij#else 668245512Sdelphij U16 HashTable[HASH64KTABLESIZE] = { 0 }; 669245512Sdelphij#endif 670245512Sdelphij 671245512Sdelphij const BYTE *ip = (BYTE *) source; 672245512Sdelphij const BYTE *anchor = ip; 673245512Sdelphij const BYTE *const base = ip; 674245512Sdelphij const BYTE *const iend = ip + isize; 675245512Sdelphij const BYTE *const oend = (BYTE *) dest + osize; 676245512Sdelphij const BYTE *const mflimit = iend - MFLIMIT; 677245512Sdelphij#define matchlimit (iend - LASTLITERALS) 678245512Sdelphij 679245512Sdelphij BYTE *op = (BYTE *) dest; 680245512Sdelphij 681245512Sdelphij int len, length; 682245512Sdelphij const int skipStrength = SKIPSTRENGTH; 683245512Sdelphij U32 forwardH; 684245512Sdelphij 685245512Sdelphij /* Init */ 686245512Sdelphij if (isize < MINLENGTH) 687245512Sdelphij goto _last_literals; 688245512Sdelphij 689245512Sdelphij /* First Byte */ 690245512Sdelphij ip++; 691245512Sdelphij forwardH = LZ4_HASH64K_VALUE(ip); 692245512Sdelphij 693245512Sdelphij /* Main Loop */ 694245512Sdelphij for (;;) { 695245512Sdelphij int findMatchAttempts = (1U << skipStrength) + 3; 696245512Sdelphij const BYTE *forwardIp = ip; 697245512Sdelphij const BYTE *ref; 698245512Sdelphij BYTE *token; 699245512Sdelphij 700245512Sdelphij /* Find a match */ 701245512Sdelphij do { 702245512Sdelphij U32 h = forwardH; 703245512Sdelphij int step = findMatchAttempts++ >> skipStrength; 704245512Sdelphij ip = forwardIp; 705245512Sdelphij forwardIp = ip + step; 706245512Sdelphij 707245512Sdelphij if (forwardIp > mflimit) { 708245512Sdelphij goto _last_literals; 709245512Sdelphij } 710245512Sdelphij 711245512Sdelphij forwardH = LZ4_HASH64K_VALUE(forwardIp); 712245512Sdelphij ref = base + HashTable[h]; 713245512Sdelphij HashTable[h] = ip - base; 714245512Sdelphij 715245512Sdelphij } while (A32(ref) != A32(ip)); 716245512Sdelphij 717245512Sdelphij /* Catch up */ 718245512Sdelphij while ((ip > anchor) && (ref > (BYTE *) source) && 719245512Sdelphij (ip[-1] == ref[-1])) { 720245512Sdelphij ip--; 721245512Sdelphij ref--; 722245512Sdelphij } 723245512Sdelphij 724245512Sdelphij /* Encode Literal length */ 725245512Sdelphij length = ip - anchor; 726245512Sdelphij token = op++; 727245512Sdelphij 728245512Sdelphij /* Check output limit */ 729245512Sdelphij if unlikely(op + length + (2 + 1 + LASTLITERALS) + 730245512Sdelphij (length >> 8) > oend) 731245512Sdelphij return (0); 732245512Sdelphij 733245512Sdelphij if (length >= (int)RUN_MASK) { 734245512Sdelphij *token = (RUN_MASK << ML_BITS); 735245512Sdelphij len = length - RUN_MASK; 736245512Sdelphij for (; len > 254; len -= 255) 737245512Sdelphij *op++ = 255; 738245512Sdelphij *op++ = (BYTE)len; 739245512Sdelphij } else 740245512Sdelphij *token = (length << ML_BITS); 741245512Sdelphij 742245512Sdelphij /* Copy Literals */ 743245512Sdelphij LZ4_BLINDCOPY(anchor, op, length); 744245512Sdelphij 745245512Sdelphij _next_match: 746245512Sdelphij /* Encode Offset */ 747245512Sdelphij LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref); 748245512Sdelphij 749245512Sdelphij /* Start Counting */ 750245512Sdelphij ip += MINMATCH; 751245512Sdelphij ref += MINMATCH; /* MinMatch verified */ 752245512Sdelphij anchor = ip; 753245512Sdelphij while (ip < matchlimit - (STEPSIZE - 1)) { 754245512Sdelphij UARCH diff = AARCH(ref) ^ AARCH(ip); 755245512Sdelphij if (!diff) { 756245512Sdelphij ip += STEPSIZE; 757245512Sdelphij ref += STEPSIZE; 758245512Sdelphij continue; 759245512Sdelphij } 760245512Sdelphij ip += LZ4_NbCommonBytes(diff); 761245512Sdelphij goto _endCount; 762245512Sdelphij } 763245512Sdelphij#if LZ4_ARCH64 764245512Sdelphij if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) { 765245512Sdelphij ip += 4; 766245512Sdelphij ref += 4; 767245512Sdelphij } 768245512Sdelphij#endif 769245512Sdelphij if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) { 770245512Sdelphij ip += 2; 771245512Sdelphij ref += 2; 772245512Sdelphij } 773245512Sdelphij if ((ip < matchlimit) && (*ref == *ip)) 774245512Sdelphij ip++; 775245512Sdelphij _endCount: 776245512Sdelphij 777245512Sdelphij /* Encode MatchLength */ 778245512Sdelphij len = (ip - anchor); 779245512Sdelphij /* Check output limit */ 780245512Sdelphij if unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend) 781245512Sdelphij return (0); 782245512Sdelphij if (len >= (int)ML_MASK) { 783245512Sdelphij *token += ML_MASK; 784245512Sdelphij len -= ML_MASK; 785245512Sdelphij for (; len > 509; len -= 510) { 786245512Sdelphij *op++ = 255; 787245512Sdelphij *op++ = 255; 788245512Sdelphij } 789245512Sdelphij if (len > 254) { 790245512Sdelphij len -= 255; 791245512Sdelphij *op++ = 255; 792245512Sdelphij } 793245512Sdelphij *op++ = (BYTE)len; 794245512Sdelphij } else 795245512Sdelphij *token += len; 796245512Sdelphij 797245512Sdelphij /* Test end of chunk */ 798245512Sdelphij if (ip > mflimit) { 799245512Sdelphij anchor = ip; 800245512Sdelphij break; 801245512Sdelphij } 802245512Sdelphij /* Fill table */ 803245512Sdelphij HashTable[LZ4_HASH64K_VALUE(ip - 2)] = ip - 2 - base; 804245512Sdelphij 805245512Sdelphij /* Test next position */ 806245512Sdelphij ref = base + HashTable[LZ4_HASH64K_VALUE(ip)]; 807245512Sdelphij HashTable[LZ4_HASH64K_VALUE(ip)] = ip - base; 808245512Sdelphij if (A32(ref) == A32(ip)) { 809245512Sdelphij token = op++; 810245512Sdelphij *token = 0; 811245512Sdelphij goto _next_match; 812245512Sdelphij } 813245512Sdelphij /* Prepare next loop */ 814245512Sdelphij anchor = ip++; 815245512Sdelphij forwardH = LZ4_HASH64K_VALUE(ip); 816245512Sdelphij } 817245512Sdelphij 818245512Sdelphij _last_literals: 819245512Sdelphij /* Encode Last Literals */ 820245512Sdelphij { 821245512Sdelphij int lastRun = iend - anchor; 822245512Sdelphij if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) > 823245512Sdelphij oend) 824245512Sdelphij return (0); 825245512Sdelphij if (lastRun >= (int)RUN_MASK) { 826245512Sdelphij *op++ = (RUN_MASK << ML_BITS); 827245512Sdelphij lastRun -= RUN_MASK; 828245512Sdelphij for (; lastRun > 254; lastRun -= 255) 829245512Sdelphij *op++ = 255; 830245512Sdelphij *op++ = (BYTE)lastRun; 831245512Sdelphij } else 832245512Sdelphij *op++ = (lastRun << ML_BITS); 833245512Sdelphij (void) memcpy(op, anchor, iend - anchor); 834245512Sdelphij op += iend - anchor; 835245512Sdelphij } 836245512Sdelphij 837245512Sdelphij /* End */ 838245512Sdelphij return (int)(((char *)op) - dest); 839245512Sdelphij} 840245512Sdelphij 841245512Sdelphijstatic int 842245512Sdelphijreal_LZ4_compress(const char *source, char *dest, int isize, int osize) 843245512Sdelphij{ 844245512Sdelphij#if HEAPMODE 845262164Smav void *ctx = kmem_cache_alloc(lz4_ctx_cache, KM_NOSLEEP); 846245512Sdelphij int result; 847245512Sdelphij 848245512Sdelphij /* 849245512Sdelphij * out of kernel memory, gently fall through - this will disable 850245512Sdelphij * compression in zio_compress_data 851245512Sdelphij */ 852245512Sdelphij if (ctx == NULL) 853245512Sdelphij return (0); 854245512Sdelphij 855262164Smav bzero(ctx, sizeof(struct refTables)); 856245512Sdelphij if (isize < LZ4_64KLIMIT) 857245512Sdelphij result = LZ4_compress64kCtx(ctx, source, dest, isize, osize); 858245512Sdelphij else 859245512Sdelphij result = LZ4_compressCtx(ctx, source, dest, isize, osize); 860245512Sdelphij 861262164Smav kmem_cache_free(lz4_ctx_cache, ctx); 862245512Sdelphij return (result); 863245512Sdelphij#else 864245512Sdelphij if (isize < (int)LZ4_64KLIMIT) 865245512Sdelphij return (LZ4_compress64kCtx(NULL, source, dest, isize, osize)); 866245512Sdelphij return (LZ4_compressCtx(NULL, source, dest, isize, osize)); 867245512Sdelphij#endif 868245512Sdelphij} 869245512Sdelphij 870245512Sdelphij/* Decompression functions */ 871245512Sdelphij 872245512Sdelphij/* 873247309Sdelphij * Note: The decoding functionLZ4_uncompress_unknownOutputSize() is safe 874247309Sdelphij * against "buffer overflow" attack type. They will never write nor 875247309Sdelphij * read outside of the provided output buffers. 876247309Sdelphij * LZ4_uncompress_unknownOutputSize() also insures that it will never 877247309Sdelphij * read outside of the input buffer. A corrupted input will produce 878247309Sdelphij * an error result, a negative int, indicating the position of the 879247309Sdelphij * error within input stream. 880245512Sdelphij */ 881245512Sdelphij 882245512Sdelphijstatic int 883245512SdelphijLZ4_uncompress_unknownOutputSize(const char *source, char *dest, int isize, 884245512Sdelphij int maxOutputSize) 885245512Sdelphij{ 886245512Sdelphij /* Local Variables */ 887245512Sdelphij const BYTE *restrict ip = (const BYTE *) source; 888245512Sdelphij const BYTE *const iend = ip + isize; 889245512Sdelphij const BYTE *ref; 890245512Sdelphij 891245512Sdelphij BYTE *op = (BYTE *) dest; 892245512Sdelphij BYTE *const oend = op + maxOutputSize; 893245512Sdelphij BYTE *cpy; 894245512Sdelphij 895245512Sdelphij size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; 896245512Sdelphij#if LZ4_ARCH64 897245512Sdelphij size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3}; 898245512Sdelphij#endif 899245512Sdelphij 900245512Sdelphij /* Main Loop */ 901245512Sdelphij while (ip < iend) { 902245512Sdelphij unsigned token; 903245512Sdelphij size_t length; 904245512Sdelphij 905245512Sdelphij /* get runlength */ 906245512Sdelphij token = *ip++; 907245512Sdelphij if ((length = (token >> ML_BITS)) == RUN_MASK) { 908245512Sdelphij int s = 255; 909245512Sdelphij while ((ip < iend) && (s == 255)) { 910245512Sdelphij s = *ip++; 911245512Sdelphij length += s; 912245512Sdelphij } 913245512Sdelphij } 914245512Sdelphij /* copy literals */ 915245512Sdelphij cpy = op + length; 916245512Sdelphij if ((cpy > oend - COPYLENGTH) || 917245512Sdelphij (ip + length > iend - COPYLENGTH)) { 918245512Sdelphij if (cpy > oend) 919245512Sdelphij /* Error: writes beyond output buffer */ 920245512Sdelphij goto _output_error; 921245512Sdelphij if (ip + length != iend) 922245512Sdelphij /* 923245512Sdelphij * Error: LZ4 format requires to consume all 924245512Sdelphij * input at this stage 925245512Sdelphij */ 926245512Sdelphij goto _output_error; 927245512Sdelphij (void) memcpy(op, ip, length); 928245512Sdelphij op += length; 929245512Sdelphij /* Necessarily EOF, due to parsing restrictions */ 930245512Sdelphij break; 931245512Sdelphij } 932245512Sdelphij LZ4_WILDCOPY(ip, op, cpy); 933245512Sdelphij ip -= (op - cpy); 934245512Sdelphij op = cpy; 935245512Sdelphij 936245512Sdelphij /* get offset */ 937245512Sdelphij LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip); 938245512Sdelphij ip += 2; 939245512Sdelphij if (ref < (BYTE * const) dest) 940245512Sdelphij /* 941245512Sdelphij * Error: offset creates reference outside of 942245512Sdelphij * destination buffer 943245512Sdelphij */ 944245512Sdelphij goto _output_error; 945245512Sdelphij 946245512Sdelphij /* get matchlength */ 947245512Sdelphij if ((length = (token & ML_MASK)) == ML_MASK) { 948245512Sdelphij while (ip < iend) { 949245512Sdelphij int s = *ip++; 950245512Sdelphij length += s; 951245512Sdelphij if (s == 255) 952245512Sdelphij continue; 953245512Sdelphij break; 954245512Sdelphij } 955245512Sdelphij } 956245512Sdelphij /* copy repeated sequence */ 957245512Sdelphij if unlikely(op - ref < STEPSIZE) { 958245512Sdelphij#if LZ4_ARCH64 959245512Sdelphij size_t dec64 = dec64table[op-ref]; 960245512Sdelphij#else 961245512Sdelphij const int dec64 = 0; 962245512Sdelphij#endif 963245512Sdelphij op[0] = ref[0]; 964245512Sdelphij op[1] = ref[1]; 965245512Sdelphij op[2] = ref[2]; 966245512Sdelphij op[3] = ref[3]; 967245512Sdelphij op += 4; 968245512Sdelphij ref += 4; 969245512Sdelphij ref -= dec32table[op-ref]; 970245512Sdelphij A32(op) = A32(ref); 971245512Sdelphij op += STEPSIZE - 4; 972245512Sdelphij ref -= dec64; 973245512Sdelphij } else { 974245512Sdelphij LZ4_COPYSTEP(ref, op); 975245512Sdelphij } 976245512Sdelphij cpy = op + length - (STEPSIZE - 4); 977245512Sdelphij if (cpy > oend - COPYLENGTH) { 978245512Sdelphij if (cpy > oend) 979245512Sdelphij /* 980245512Sdelphij * Error: request to write outside of 981245512Sdelphij * destination buffer 982245512Sdelphij */ 983245512Sdelphij goto _output_error; 984245512Sdelphij LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH)); 985245512Sdelphij while (op < cpy) 986245512Sdelphij *op++ = *ref++; 987245512Sdelphij op = cpy; 988245512Sdelphij if (op == oend) 989245512Sdelphij /* 990245512Sdelphij * Check EOF (should never happen, since 991245512Sdelphij * last 5 bytes are supposed to be literals) 992245512Sdelphij */ 993245512Sdelphij goto _output_error; 994245512Sdelphij continue; 995245512Sdelphij } 996245512Sdelphij LZ4_SECURECOPY(ref, op, cpy); 997245512Sdelphij op = cpy; /* correction */ 998245512Sdelphij } 999245512Sdelphij 1000245512Sdelphij /* end of decoding */ 1001245512Sdelphij return (int)(((char *)op) - dest); 1002245512Sdelphij 1003245512Sdelphij /* write overflow error detected */ 1004245512Sdelphij _output_error: 1005245512Sdelphij return (int)(-(((char *)ip) - source)); 1006245512Sdelphij} 1007262164Smav 1008262164Smavextern void 1009262164Smavlz4_init(void) 1010262164Smav{ 1011262164Smav 1012262164Smav#if HEAPMODE 1013262164Smav lz4_ctx_cache = kmem_cache_create("lz4_ctx", sizeof(struct refTables), 1014262164Smav 0, NULL, NULL, NULL, NULL, NULL, 0); 1015262164Smav#endif 1016262164Smav} 1017262164Smav 1018262164Smavextern void 1019262164Smavlz4_fini(void) 1020262164Smav{ 1021262164Smav 1022262164Smav#if HEAPMODE 1023262164Smav kmem_cache_destroy(lz4_ctx_cache); 1024262164Smav#endif 1025262164Smav} 1026