1355d67fcSMatthew Dillon /* 2355d67fcSMatthew Dillon LZ4 - Fast LZ compression algorithm 3355d67fcSMatthew Dillon Copyright (C) 2011-2013, Yann Collet. 4355d67fcSMatthew Dillon BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 5355d67fcSMatthew Dillon 6355d67fcSMatthew Dillon Redistribution and use in source and binary forms, with or without 7355d67fcSMatthew Dillon modification, are permitted provided that the following conditions are 8355d67fcSMatthew Dillon met: 9355d67fcSMatthew Dillon 10355d67fcSMatthew Dillon * Redistributions of source code must retain the above copyright 11355d67fcSMatthew Dillon notice, this list of conditions and the following disclaimer. 12355d67fcSMatthew Dillon * Redistributions in binary form must reproduce the above 13355d67fcSMatthew Dillon copyright notice, this list of conditions and the following disclaimer 14355d67fcSMatthew Dillon in the documentation and/or other materials provided with the 15355d67fcSMatthew Dillon distribution. 16355d67fcSMatthew Dillon 17355d67fcSMatthew Dillon THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 18355d67fcSMatthew Dillon "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 19355d67fcSMatthew Dillon LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 20355d67fcSMatthew Dillon A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 21355d67fcSMatthew Dillon OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 22355d67fcSMatthew Dillon SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 23355d67fcSMatthew Dillon LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24355d67fcSMatthew Dillon DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25355d67fcSMatthew Dillon THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26355d67fcSMatthew Dillon (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 27355d67fcSMatthew Dillon OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28355d67fcSMatthew Dillon 29355d67fcSMatthew Dillon You can contact the author at : 30355d67fcSMatthew Dillon - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html 31355d67fcSMatthew Dillon - LZ4 source repository : http://code.google.com/p/lz4/ 32355d67fcSMatthew Dillon */ 33355d67fcSMatthew Dillon 34355d67fcSMatthew Dillon /* 35355d67fcSMatthew Dillon Note : this source file requires "hammer2_lz4_encoder.h" 36355d67fcSMatthew Dillon */ 37355d67fcSMatthew Dillon 38355d67fcSMatthew Dillon //************************************** 39355d67fcSMatthew Dillon // Tuning parameters 40355d67fcSMatthew Dillon //************************************** 41355d67fcSMatthew Dillon // MEMORY_USAGE : 42355d67fcSMatthew Dillon // Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB; 43355d67fcSMatthew Dillon // 16 -> 64KB; 20 -> 1MB; etc.) 44355d67fcSMatthew Dillon // Increasing memory usage improves compression ratio 45355d67fcSMatthew Dillon // Reduced memory usage can improve speed, due to cache effect 46355d67fcSMatthew Dillon // Default value is 14, for 16KB, which nicely fits into Intel x86 L1 cache 47355d67fcSMatthew Dillon #define MEMORY_USAGE 14 48355d67fcSMatthew Dillon 49355d67fcSMatthew Dillon // HEAPMODE : 50355d67fcSMatthew Dillon // Select how default compression function will allocate memory for its 51355d67fcSMatthew Dillon // hash table, 52355d67fcSMatthew Dillon // in memory stack (0:default, fastest), or in memory heap (1:requires 53355d67fcSMatthew Dillon // memory allocation (malloc)). 54355d67fcSMatthew Dillon // Default allocation strategy is to use stack (HEAPMODE 0) 55355d67fcSMatthew Dillon // Note : explicit functions *_stack* and *_heap* are unaffected by this setting 56355d67fcSMatthew Dillon #define HEAPMODE 1 57355d67fcSMatthew Dillon 58355d67fcSMatthew Dillon // BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE : 59355d67fcSMatthew Dillon // This will provide a small boost to performance for big endian cpu, 60355d67fcSMatthew Dillon // but the resulting compressed stream will be incompatible with little-endian CPU. 61355d67fcSMatthew Dillon // You can set this option to 1 in situations where data will remain within 62355d67fcSMatthew Dillon // closed environment 63355d67fcSMatthew Dillon // This option is useless on Little_Endian CPU (such as x86) 64355d67fcSMatthew Dillon //#define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1 65355d67fcSMatthew Dillon 66355d67fcSMatthew Dillon 67355d67fcSMatthew Dillon //************************************** 68355d67fcSMatthew Dillon // CPU Feature Detection 69355d67fcSMatthew Dillon //************************************** 70355d67fcSMatthew Dillon // 32 or 64 bits ? 71355d67fcSMatthew Dillon #if (defined(__x86_64__) || defined(_M_X64)) // Detects 64 bits mode 72355d67fcSMatthew Dillon # define LZ4_ARCH64 1 73355d67fcSMatthew Dillon #else 74355d67fcSMatthew Dillon # define LZ4_ARCH64 0 75355d67fcSMatthew Dillon #endif 76355d67fcSMatthew Dillon 77355d67fcSMatthew Dillon //This reduced library code is only Little Endian compatible, 78355d67fcSMatthew Dillon //if the need arises, please look for the appropriate defines in the 79355d67fcSMatthew Dillon //original complete LZ4 library. 80355d67fcSMatthew Dillon //Same is true for unaligned memory access which is enabled by default, 81355d67fcSMatthew Dillon //hardware bit count, also enabled by default, and Microsoft/Visual 82355d67fcSMatthew Dillon //Studio compilers. 83355d67fcSMatthew Dillon 84355d67fcSMatthew Dillon //************************************** 85355d67fcSMatthew Dillon // Compiler Options 86355d67fcSMatthew Dillon //************************************** 87355d67fcSMatthew Dillon #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L // C99 88355d67fcSMatthew Dillon /* "restrict" is a known keyword */ 89355d67fcSMatthew Dillon #else 90355d67fcSMatthew Dillon # define restrict // Disable restrict 91355d67fcSMatthew Dillon #endif 92355d67fcSMatthew Dillon 93355d67fcSMatthew Dillon #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) 94355d67fcSMatthew Dillon 95355d67fcSMatthew Dillon #if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__) 96355d67fcSMatthew Dillon # define expect(expr,value) (__builtin_expect ((expr),(value)) ) 97355d67fcSMatthew Dillon #else 98355d67fcSMatthew Dillon # define expect(expr,value) (expr) 99355d67fcSMatthew Dillon #endif 100355d67fcSMatthew Dillon 101355d67fcSMatthew Dillon #define likely(expr) expect((expr) != 0, 1) 102355d67fcSMatthew Dillon #define unlikely(expr) expect((expr) != 0, 0) 103355d67fcSMatthew Dillon 104355d67fcSMatthew Dillon 105355d67fcSMatthew Dillon //************************************** 106355d67fcSMatthew Dillon // Includes 107355d67fcSMatthew Dillon //************************************** 108355d67fcSMatthew Dillon #include "hammer2.h" 109355d67fcSMatthew Dillon #include "hammer2_lz4.h" 1103a4556b9Szrj #include <sys/malloc.h> //for malloc macros, hammer2.h includes sys/param.h 111355d67fcSMatthew Dillon 112355d67fcSMatthew Dillon 113355d67fcSMatthew Dillon //Declaration for kmalloc functions 1143a4556b9Szrj static MALLOC_DEFINE(C_HASHTABLE, "comphashtable", 115355d67fcSMatthew Dillon "A hash table used by LZ4 compression function."); 116355d67fcSMatthew Dillon 117355d67fcSMatthew Dillon 118355d67fcSMatthew Dillon //************************************** 119355d67fcSMatthew Dillon // Basic Types 120355d67fcSMatthew Dillon //************************************** 121355d67fcSMatthew Dillon #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L // C99 122*eaf07fa9Szrj # include <sys/stdint.h> 123355d67fcSMatthew Dillon typedef uint8_t BYTE; 124355d67fcSMatthew Dillon typedef uint16_t U16; 125355d67fcSMatthew Dillon typedef uint32_t U32; 126355d67fcSMatthew Dillon typedef int32_t S32; 127355d67fcSMatthew Dillon typedef uint64_t U64; 128355d67fcSMatthew Dillon #else 129355d67fcSMatthew Dillon typedef unsigned char BYTE; 130355d67fcSMatthew Dillon typedef unsigned short U16; 131355d67fcSMatthew Dillon typedef unsigned int U32; 132355d67fcSMatthew Dillon typedef signed int S32; 133355d67fcSMatthew Dillon typedef unsigned long long U64; 134355d67fcSMatthew Dillon #endif 135355d67fcSMatthew Dillon 136355d67fcSMatthew Dillon #if defined(__GNUC__) && !defined(LZ4_FORCE_UNALIGNED_ACCESS) 137355d67fcSMatthew Dillon # define _PACKED __attribute__ ((packed)) 138355d67fcSMatthew Dillon #else 139355d67fcSMatthew Dillon # define _PACKED 140355d67fcSMatthew Dillon #endif 141355d67fcSMatthew Dillon 142355d67fcSMatthew Dillon #if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__) 143355d67fcSMatthew Dillon # pragma pack(push, 1) 144355d67fcSMatthew Dillon #endif 145355d67fcSMatthew Dillon 146355d67fcSMatthew Dillon typedef struct _U16_S { U16 v; } _PACKED U16_S; 147355d67fcSMatthew Dillon typedef struct _U32_S { U32 v; } _PACKED U32_S; 148355d67fcSMatthew Dillon typedef struct _U64_S { U64 v; } _PACKED U64_S; 149355d67fcSMatthew Dillon 150355d67fcSMatthew Dillon #if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__) 151355d67fcSMatthew Dillon # pragma pack(pop) 152355d67fcSMatthew Dillon #endif 153355d67fcSMatthew Dillon 154355d67fcSMatthew Dillon #define A64(x) (((U64_S *)(x))->v) 155355d67fcSMatthew Dillon #define A32(x) (((U32_S *)(x))->v) 156355d67fcSMatthew Dillon #define A16(x) (((U16_S *)(x))->v) 157355d67fcSMatthew Dillon 158355d67fcSMatthew Dillon 159355d67fcSMatthew Dillon //************************************** 160355d67fcSMatthew Dillon // Constants 161355d67fcSMatthew Dillon //************************************** 162355d67fcSMatthew Dillon #define HASHTABLESIZE (1 << MEMORY_USAGE) 163355d67fcSMatthew Dillon 164355d67fcSMatthew Dillon #define MINMATCH 4 165355d67fcSMatthew Dillon 166355d67fcSMatthew Dillon #define COPYLENGTH 8 167355d67fcSMatthew Dillon #define LASTLITERALS 5 168355d67fcSMatthew Dillon #define MFLIMIT (COPYLENGTH+MINMATCH) 169355d67fcSMatthew Dillon #define MINLENGTH (MFLIMIT+1) 170355d67fcSMatthew Dillon 171355d67fcSMatthew Dillon #define LZ4_64KLIMIT ((1<<16) + (MFLIMIT-1)) 172355d67fcSMatthew Dillon #define SKIPSTRENGTH 6 173355d67fcSMatthew Dillon // Increasing this value will make the compression run slower on 174355d67fcSMatthew Dillon // incompressible data 175355d67fcSMatthew Dillon 176355d67fcSMatthew Dillon #define MAXD_LOG 16 177355d67fcSMatthew Dillon #define MAX_DISTANCE ((1 << MAXD_LOG) - 1) 178355d67fcSMatthew Dillon 179355d67fcSMatthew Dillon #define ML_BITS 4 180355d67fcSMatthew Dillon #define ML_MASK ((1U<<ML_BITS)-1) 181355d67fcSMatthew Dillon #define RUN_BITS (8-ML_BITS) 182355d67fcSMatthew Dillon #define RUN_MASK ((1U<<RUN_BITS)-1) 183355d67fcSMatthew Dillon 184355d67fcSMatthew Dillon 185355d67fcSMatthew Dillon //************************************** 186355d67fcSMatthew Dillon // Architecture-specific macros 187355d67fcSMatthew Dillon //************************************** 188355d67fcSMatthew Dillon #if LZ4_ARCH64 // 64-bit 189355d67fcSMatthew Dillon # define STEPSIZE 8 190355d67fcSMatthew Dillon # define UARCH U64 191355d67fcSMatthew Dillon # define AARCH A64 192355d67fcSMatthew Dillon # define LZ4_COPYSTEP(s,d) A64(d) = A64(s); d+=8; s+=8; 193355d67fcSMatthew Dillon # define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d) 194355d67fcSMatthew Dillon # define LZ4_SECURECOPY(s,d,e) if (d<e) LZ4_WILDCOPY(s,d,e) 195355d67fcSMatthew Dillon # define HTYPE U32 196355d67fcSMatthew Dillon # define INITBASE(base) BYTE* base = ip 197355d67fcSMatthew Dillon #else // 32-bit 198355d67fcSMatthew Dillon # define STEPSIZE 4 199355d67fcSMatthew Dillon # define UARCH U32 200355d67fcSMatthew Dillon # define AARCH A32 201355d67fcSMatthew Dillon # define LZ4_COPYSTEP(s,d) A32(d) = A32(s); d+=4; s+=4; 202355d67fcSMatthew Dillon # define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d); 203355d67fcSMatthew Dillon # define LZ4_SECURECOPY LZ4_WILDCOPY 204355d67fcSMatthew Dillon # define HTYPE BYTE* 205355d67fcSMatthew Dillon # define INITBASE(base) int base = 0 206355d67fcSMatthew Dillon #endif 207355d67fcSMatthew Dillon 208355d67fcSMatthew Dillon #if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE)) 209355d67fcSMatthew Dillon # define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); 210355d67fcSMatthew Dillon v = lz4_bswap16(v); 211355d67fcSMatthew Dillon d = (s) - v; } 212355d67fcSMatthew Dillon # define LZ4_WRITE_LITTLEENDIAN_16(p,i) { U16 v = (U16)(i); 213355d67fcSMatthew Dillon v = lz4_bswap16(v); 214355d67fcSMatthew Dillon A16(p) = v; 215355d67fcSMatthew Dillon p+=2; } 216355d67fcSMatthew Dillon #else // Little Endian 217355d67fcSMatthew Dillon # define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); } 218355d67fcSMatthew Dillon # define LZ4_WRITE_LITTLEENDIAN_16(p,v) { A16(p) = v; p+=2; } 219355d67fcSMatthew Dillon #endif 220355d67fcSMatthew Dillon 221355d67fcSMatthew Dillon 222355d67fcSMatthew Dillon //************************************** 223355d67fcSMatthew Dillon // Macros 224355d67fcSMatthew Dillon //************************************** 225355d67fcSMatthew Dillon #define LZ4_WILDCOPY(s,d,e) do { LZ4_COPYPACKET(s,d) } while (d<e); 226355d67fcSMatthew Dillon #define LZ4_BLINDCOPY(s,d,l) { BYTE* e=(d)+(l); LZ4_WILDCOPY(s,d,e); d=e; } 227355d67fcSMatthew Dillon 228355d67fcSMatthew Dillon 229355d67fcSMatthew Dillon //**************************** 230355d67fcSMatthew Dillon // Private functions 231355d67fcSMatthew Dillon //**************************** 232355d67fcSMatthew Dillon #if LZ4_ARCH64 233355d67fcSMatthew Dillon 234355d67fcSMatthew Dillon static 235355d67fcSMatthew Dillon inline 236355d67fcSMatthew Dillon int 237355d67fcSMatthew Dillon LZ4_NbCommonBytes (register U64 val) 238355d67fcSMatthew Dillon { 239355d67fcSMatthew Dillon #if defined(LZ4_BIG_ENDIAN) 240355d67fcSMatthew Dillon #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) 241355d67fcSMatthew Dillon unsigned long r = 0; 242355d67fcSMatthew Dillon _BitScanReverse64( &r, val ); 243355d67fcSMatthew Dillon return (int)(r>>3); 244355d67fcSMatthew Dillon #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) 245355d67fcSMatthew Dillon return (__builtin_clzll(val) >> 3); 246355d67fcSMatthew Dillon #else 247355d67fcSMatthew Dillon int r; 248355d67fcSMatthew Dillon if (!(val>>32)) { r=4; } else { r=0; val>>=32; } 249355d67fcSMatthew Dillon if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } 250355d67fcSMatthew Dillon r += (!val); 251355d67fcSMatthew Dillon return r; 252355d67fcSMatthew Dillon #endif 253355d67fcSMatthew Dillon #else 254355d67fcSMatthew Dillon #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) 255355d67fcSMatthew Dillon unsigned long r = 0; 256355d67fcSMatthew Dillon _BitScanForward64( &r, val ); 257355d67fcSMatthew Dillon return (int)(r>>3); 258355d67fcSMatthew Dillon #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) 259355d67fcSMatthew Dillon return (__builtin_ctzll(val) >> 3); 260355d67fcSMatthew Dillon #else 261355d67fcSMatthew Dillon static int DeBruijnBytePos[64] = { 262355d67fcSMatthew Dillon 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 263355d67fcSMatthew Dillon 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 264355d67fcSMatthew Dillon 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 265355d67fcSMatthew Dillon 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 266355d67fcSMatthew Dillon 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 267355d67fcSMatthew Dillon 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 268355d67fcSMatthew Dillon 7, 6, 7, 7 }; 269355d67fcSMatthew Dillon return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58]; 270355d67fcSMatthew Dillon #endif 271355d67fcSMatthew Dillon #endif 272355d67fcSMatthew Dillon } 273355d67fcSMatthew Dillon 274355d67fcSMatthew Dillon #else 275355d67fcSMatthew Dillon 276355d67fcSMatthew Dillon static 277355d67fcSMatthew Dillon inline 278355d67fcSMatthew Dillon int 279355d67fcSMatthew Dillon LZ4_NbCommonBytes (register U32 val) 280355d67fcSMatthew Dillon { 281355d67fcSMatthew Dillon #if defined(LZ4_BIG_ENDIAN) 282355d67fcSMatthew Dillon # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) 283355d67fcSMatthew Dillon unsigned long r = 0; 284355d67fcSMatthew Dillon _BitScanReverse( &r, val ); 285355d67fcSMatthew Dillon return (int)(r>>3); 286355d67fcSMatthew Dillon # elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) 287355d67fcSMatthew Dillon return (__builtin_clz(val) >> 3); 288355d67fcSMatthew Dillon # else 289355d67fcSMatthew Dillon int r; 290355d67fcSMatthew Dillon if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; } 291355d67fcSMatthew Dillon r += (!val); 292355d67fcSMatthew Dillon return r; 293355d67fcSMatthew Dillon # endif 294355d67fcSMatthew Dillon #else 295355d67fcSMatthew Dillon # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) 296355d67fcSMatthew Dillon unsigned long r; 297355d67fcSMatthew Dillon _BitScanForward( &r, val ); 298355d67fcSMatthew Dillon return (int)(r>>3); 299355d67fcSMatthew Dillon # elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) 300355d67fcSMatthew Dillon return (__builtin_ctz(val) >> 3); 301355d67fcSMatthew Dillon # else 302355d67fcSMatthew Dillon static int DeBruijnBytePos[32] = { 303355d67fcSMatthew Dillon 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 304355d67fcSMatthew Dillon 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 305355d67fcSMatthew Dillon 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 306355d67fcSMatthew Dillon 1, 1 }; 307355d67fcSMatthew Dillon return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27]; 308355d67fcSMatthew Dillon # endif 309355d67fcSMatthew Dillon #endif 310355d67fcSMatthew Dillon } 311355d67fcSMatthew Dillon 312355d67fcSMatthew Dillon #endif 313355d67fcSMatthew Dillon 314355d67fcSMatthew Dillon 315355d67fcSMatthew Dillon 316355d67fcSMatthew Dillon //****************************** 317355d67fcSMatthew Dillon // Compression functions 318355d67fcSMatthew Dillon //****************************** 319355d67fcSMatthew Dillon 320355d67fcSMatthew Dillon #include "hammer2_lz4_encoder.h" 321355d67fcSMatthew Dillon 322355d67fcSMatthew Dillon /* 323355d67fcSMatthew Dillon void* LZ4_createHeapMemory(); 324355d67fcSMatthew Dillon int LZ4_freeHeapMemory(void* ctx); 325355d67fcSMatthew Dillon 326355d67fcSMatthew Dillon Used to allocate and free hashTable memory 327355d67fcSMatthew Dillon to be used by the LZ4_compress_heap* family of functions. 328355d67fcSMatthew Dillon LZ4_createHeapMemory() returns NULL is memory allocation fails. 329355d67fcSMatthew Dillon */ 330355d67fcSMatthew Dillon void* 331355d67fcSMatthew Dillon LZ4_create(void) 332355d67fcSMatthew Dillon { 333355d67fcSMatthew Dillon return kmalloc(HASHTABLESIZE, C_HASHTABLE, M_INTWAIT); 334355d67fcSMatthew Dillon } 335355d67fcSMatthew Dillon 336355d67fcSMatthew Dillon int 337355d67fcSMatthew Dillon LZ4_free(void* ctx) 338355d67fcSMatthew Dillon { 339355d67fcSMatthew Dillon kfree(ctx, C_HASHTABLE); 340355d67fcSMatthew Dillon return 0; 341355d67fcSMatthew Dillon } 342355d67fcSMatthew Dillon 343355d67fcSMatthew Dillon int 344355d67fcSMatthew Dillon LZ4_compress_limitedOutput(char* source, char* dest, int inputSize, int maxOutputSize) 345355d67fcSMatthew Dillon { 346355d67fcSMatthew Dillon void* ctx = LZ4_create(); 347355d67fcSMatthew Dillon int result; 348355d67fcSMatthew Dillon if (ctx == NULL) return 0; // Failed allocation => compression not done 349355d67fcSMatthew Dillon if (inputSize < LZ4_64KLIMIT) 350355d67fcSMatthew Dillon result = LZ4_compress64k_heap_limitedOutput(ctx, source, dest, 351355d67fcSMatthew Dillon inputSize, maxOutputSize); 352355d67fcSMatthew Dillon else result = LZ4_compress_heap_limitedOutput(ctx, source, dest, 353355d67fcSMatthew Dillon inputSize, maxOutputSize); 354355d67fcSMatthew Dillon LZ4_free(ctx); 355355d67fcSMatthew Dillon return result; 356355d67fcSMatthew Dillon } 357355d67fcSMatthew Dillon 358355d67fcSMatthew Dillon 359355d67fcSMatthew Dillon //**************************** 360355d67fcSMatthew Dillon // Decompression functions 361355d67fcSMatthew Dillon //**************************** 362355d67fcSMatthew Dillon 363355d67fcSMatthew Dillon typedef enum { noPrefix = 0, withPrefix = 1 } prefix64k_directive; 364355d67fcSMatthew Dillon typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } end_directive; 365355d67fcSMatthew Dillon typedef enum { full = 0, partial = 1 } exit_directive; 366355d67fcSMatthew Dillon 367355d67fcSMatthew Dillon 368355d67fcSMatthew Dillon // This generic decompression function cover all use cases. 369355d67fcSMatthew Dillon // It shall be instanciated several times, using different sets of directives 370355d67fcSMatthew Dillon // Note that it is essential this generic function is really inlined, 371355d67fcSMatthew Dillon // in order to remove useless branches during compilation optimisation. 372355d67fcSMatthew Dillon static 373355d67fcSMatthew Dillon inline 374355d67fcSMatthew Dillon int LZ4_decompress_generic( 375355d67fcSMatthew Dillon char* source, 376355d67fcSMatthew Dillon char* dest, 377355d67fcSMatthew Dillon int inputSize, // 378355d67fcSMatthew Dillon int outputSize, 379355d67fcSMatthew Dillon // OutputSize must be != 0; if endOnInput==endOnInputSize, 380355d67fcSMatthew Dillon // this value is the max size of Output Buffer. 381355d67fcSMatthew Dillon 382355d67fcSMatthew Dillon int endOnInput, // endOnOutputSize, endOnInputSize 383355d67fcSMatthew Dillon int prefix64k, // noPrefix, withPrefix 384355d67fcSMatthew Dillon int partialDecoding, // full, partial 385355d67fcSMatthew Dillon int targetOutputSize // only used if partialDecoding==partial 386355d67fcSMatthew Dillon ) 387355d67fcSMatthew Dillon { 388355d67fcSMatthew Dillon // Local Variables 389355d67fcSMatthew Dillon BYTE* restrict ip = (BYTE*) source; 390355d67fcSMatthew Dillon BYTE* ref; 391355d67fcSMatthew Dillon BYTE* iend = ip + inputSize; 392355d67fcSMatthew Dillon 393355d67fcSMatthew Dillon BYTE* op = (BYTE*) dest; 394355d67fcSMatthew Dillon BYTE* oend = op + outputSize; 395355d67fcSMatthew Dillon BYTE* cpy; 396355d67fcSMatthew Dillon BYTE* oexit = op + targetOutputSize; 397355d67fcSMatthew Dillon 398355d67fcSMatthew Dillon size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; 399355d67fcSMatthew Dillon #if LZ4_ARCH64 400355d67fcSMatthew Dillon size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3}; 401355d67fcSMatthew Dillon #endif 402355d67fcSMatthew Dillon 403355d67fcSMatthew Dillon 404355d67fcSMatthew Dillon // Special case 405355d67fcSMatthew Dillon if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT; 406355d67fcSMatthew Dillon // targetOutputSize too large, better decode everything 407355d67fcSMatthew Dillon if unlikely(outputSize==0) goto _output_error; 408355d67fcSMatthew Dillon // Empty output buffer 409355d67fcSMatthew Dillon 410355d67fcSMatthew Dillon 411355d67fcSMatthew Dillon // Main Loop 412355d67fcSMatthew Dillon while (1) 413355d67fcSMatthew Dillon { 414355d67fcSMatthew Dillon unsigned token; 415355d67fcSMatthew Dillon size_t length; 416355d67fcSMatthew Dillon 417355d67fcSMatthew Dillon // get runlength 418355d67fcSMatthew Dillon token = *ip++; 419355d67fcSMatthew Dillon if ((length=(token>>ML_BITS)) == RUN_MASK) 420355d67fcSMatthew Dillon { 421355d67fcSMatthew Dillon unsigned s=255; 422355d67fcSMatthew Dillon while (((endOnInput)?ip<iend:1) && (s==255)) 423355d67fcSMatthew Dillon { 424355d67fcSMatthew Dillon s = *ip++; 425355d67fcSMatthew Dillon length += s; 426355d67fcSMatthew Dillon } 427355d67fcSMatthew Dillon } 428355d67fcSMatthew Dillon 429355d67fcSMatthew Dillon // copy literals 430355d67fcSMatthew Dillon cpy = op+length; 431355d67fcSMatthew Dillon if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) 432355d67fcSMatthew Dillon || (ip+length>iend-(2+1+LASTLITERALS))) ) 433355d67fcSMatthew Dillon || ((!endOnInput) && (cpy>oend-COPYLENGTH))) 434355d67fcSMatthew Dillon { 435355d67fcSMatthew Dillon if (partialDecoding) 436355d67fcSMatthew Dillon { 437355d67fcSMatthew Dillon if (cpy > oend) goto _output_error; 438355d67fcSMatthew Dillon // Error : write attempt beyond end of output buffer 439355d67fcSMatthew Dillon if ((endOnInput) && (ip+length > iend)) goto _output_error; 440355d67fcSMatthew Dillon // Error : read attempt beyond end of input buffer 441355d67fcSMatthew Dillon } 442355d67fcSMatthew Dillon else 443355d67fcSMatthew Dillon { 444355d67fcSMatthew Dillon if ((!endOnInput) && (cpy != oend)) goto _output_error; 445355d67fcSMatthew Dillon // Error : block decoding must stop exactly there, 446355d67fcSMatthew Dillon // due to parsing restrictions 447355d67fcSMatthew Dillon if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) 448355d67fcSMatthew Dillon goto _output_error; 449355d67fcSMatthew Dillon // Error : not enough place for another match (min 4) + 5 literals 450355d67fcSMatthew Dillon } 451355d67fcSMatthew Dillon memcpy(op, ip, length); 452355d67fcSMatthew Dillon ip += length; 453355d67fcSMatthew Dillon op += length; 454355d67fcSMatthew Dillon break; 455355d67fcSMatthew Dillon // Necessarily EOF, due to parsing restrictions 456355d67fcSMatthew Dillon } 457355d67fcSMatthew Dillon LZ4_WILDCOPY(ip, op, cpy); ip -= (op-cpy); op = cpy; 458355d67fcSMatthew Dillon 459355d67fcSMatthew Dillon // get offset 460355d67fcSMatthew Dillon LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2; 461355d67fcSMatthew Dillon if ((prefix64k==noPrefix) && unlikely(ref < (BYTE*)dest)) 462355d67fcSMatthew Dillon goto _output_error; // Error : offset outside destination buffer 463355d67fcSMatthew Dillon 464355d67fcSMatthew Dillon // get matchlength 465355d67fcSMatthew Dillon if ((length=(token&ML_MASK)) == ML_MASK) 466355d67fcSMatthew Dillon { 467355d67fcSMatthew Dillon while (endOnInput ? ip<iend-(LASTLITERALS+1) : 1) 468355d67fcSMatthew Dillon // A minimum nb of input bytes must remain for LASTLITERALS + token 469355d67fcSMatthew Dillon { 470355d67fcSMatthew Dillon unsigned s = *ip++; 471355d67fcSMatthew Dillon length += s; 472355d67fcSMatthew Dillon if (s==255) continue; 473355d67fcSMatthew Dillon break; 474355d67fcSMatthew Dillon } 475355d67fcSMatthew Dillon } 476355d67fcSMatthew Dillon 477355d67fcSMatthew Dillon // copy repeated sequence 478355d67fcSMatthew Dillon if unlikely((op-ref)<STEPSIZE) 479355d67fcSMatthew Dillon { 480355d67fcSMatthew Dillon #if LZ4_ARCH64 481355d67fcSMatthew Dillon size_t dec64 = dec64table[op-ref]; 482355d67fcSMatthew Dillon #else 483355d67fcSMatthew Dillon const size_t dec64 = 0; 484355d67fcSMatthew Dillon #endif 485355d67fcSMatthew Dillon op[0] = ref[0]; 486355d67fcSMatthew Dillon op[1] = ref[1]; 487355d67fcSMatthew Dillon op[2] = ref[2]; 488355d67fcSMatthew Dillon op[3] = ref[3]; 489355d67fcSMatthew Dillon op += 4, ref += 4; ref -= dec32table[op-ref]; 490355d67fcSMatthew Dillon A32(op) = A32(ref); 491355d67fcSMatthew Dillon op += STEPSIZE-4; ref -= dec64; 492355d67fcSMatthew Dillon } else { LZ4_COPYSTEP(ref,op); } 493355d67fcSMatthew Dillon cpy = op + length - (STEPSIZE-4); 494355d67fcSMatthew Dillon 495355d67fcSMatthew Dillon if unlikely(cpy>oend-(COPYLENGTH)-(STEPSIZE-4)) 496355d67fcSMatthew Dillon { 497355d67fcSMatthew Dillon if (cpy > oend-LASTLITERALS) goto _output_error; 498355d67fcSMatthew Dillon // Error : last 5 bytes must be literals 499355d67fcSMatthew Dillon LZ4_SECURECOPY(ref, op, (oend-COPYLENGTH)); 500355d67fcSMatthew Dillon while(op<cpy) *op++=*ref++; 501355d67fcSMatthew Dillon op=cpy; 502355d67fcSMatthew Dillon continue; 503355d67fcSMatthew Dillon } 504355d67fcSMatthew Dillon LZ4_WILDCOPY(ref, op, cpy); 505355d67fcSMatthew Dillon op=cpy; // correction 506355d67fcSMatthew Dillon } 507355d67fcSMatthew Dillon 508355d67fcSMatthew Dillon // end of decoding 509355d67fcSMatthew Dillon if (endOnInput) 510355d67fcSMatthew Dillon return (int) (((char*)op)-dest); // Nb of output bytes decoded 511355d67fcSMatthew Dillon else 512355d67fcSMatthew Dillon return (int) (((char*)ip)-source); // Nb of input bytes read 513355d67fcSMatthew Dillon 514355d67fcSMatthew Dillon // Overflow error detected 515355d67fcSMatthew Dillon _output_error: 516355d67fcSMatthew Dillon return (int) (-(((char*)ip)-source))-1; 517355d67fcSMatthew Dillon } 518355d67fcSMatthew Dillon 519355d67fcSMatthew Dillon 520355d67fcSMatthew Dillon int 521355d67fcSMatthew Dillon LZ4_decompress_safe(char* source, char* dest, int inputSize, int maxOutputSize) 522355d67fcSMatthew Dillon { 523355d67fcSMatthew Dillon return LZ4_decompress_generic(source, dest, inputSize, maxOutputSize, 524355d67fcSMatthew Dillon endOnInputSize, noPrefix, full, 0); 525355d67fcSMatthew Dillon } 526