lz4.cc (57787B)
1 /* 2 LZ4 - Fast LZ compression algorithm 3 Copyright (C) 2011-2016, Yann Collet. 4 5 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 6 7 Redistribution and use in source and binary forms, with or without 8 modification, are permitted provided that the following conditions are 9 met: 10 11 * Redistributions of source code must retain the above copyright 12 notice, this list of conditions and the following disclaimer. 13 * Redistributions in binary form must reproduce the above 14 copyright notice, this list of conditions and the following disclaimer 15 in the documentation and/or other materials provided with the 16 distribution. 17 18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 30 You can contact the author at : 31 - LZ4 homepage : http://www.lz4.org 32 - LZ4 source repository : https://github.com/lz4/lz4 33 */ 34 35 36 /*-************************************ 37 * Tuning parameters 38 **************************************/ 39 /* 40 * HEAPMODE : 41 * Select how default compression functions will allocate memory for their hash table, 42 * in memory stack (0:default, fastest), or in memory heap (1:requires malloc()). 43 */ 44 #ifndef HEAPMODE 45 # define HEAPMODE 0 46 #endif 47 48 /* 49 * ACCELERATION_DEFAULT : 50 * Select "acceleration" for LZ4_compress_fast() when parameter value <= 0 51 */ 52 #define ACCELERATION_DEFAULT 1 53 54 55 /*-************************************ 56 * CPU Feature Detection 57 **************************************/ 58 /* LZ4_FORCE_MEMORY_ACCESS 59 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable. 60 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal. 61 * The below switch allow to select different access method for improved performance. 62 * Method 0 (default) : use `memcpy()`. Safe and portable. 63 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable). 64 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`. 65 * Method 2 : direct access. This method is portable but violate C standard. 66 * It can generate buggy code on targets which generate assembly depending on alignment. 67 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6) 68 * See https://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details. 69 * Prefer these methods in priority order (0 > 1 > 2) 70 */ 71 #ifndef LZ4_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */ 72 # if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) ) 73 # define LZ4_FORCE_MEMORY_ACCESS 2 74 # elif defined(__INTEL_COMPILER) || \ 75 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) )) 76 # define LZ4_FORCE_MEMORY_ACCESS 1 77 # endif 78 #endif 79 80 /* 81 * LZ4_FORCE_SW_BITCOUNT 82 * Define this parameter if your target system or compiler does not support hardware bit count 83 */ 84 #if defined(_MSC_VER) && defined(_WIN32_WCE) /* Visual Studio for Windows CE does not support Hardware bit count */ 85 # define LZ4_FORCE_SW_BITCOUNT 86 #endif 87 88 89 /*-************************************ 90 * Dependency 91 **************************************/ 92 #include "lz4.h" 93 /* see also "memory routines" below */ 94 95 96 /*-************************************ 97 * Compiler Options 98 **************************************/ 99 #ifdef _MSC_VER /* Visual Studio */ 100 # define FORCE_INLINE static __forceinline 101 # include <intrin.h> 102 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 103 # pragma warning(disable : 4293) /* disable: C4293: too large shift (32-bits) */ 104 #else 105 # if defined(__GNUC__) || defined(__clang__) 106 # define FORCE_INLINE static inline __attribute__((always_inline)) 107 # elif defined(__cplusplus) || (defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 108 # define FORCE_INLINE static inline 109 # else 110 # define FORCE_INLINE static 111 # endif 112 #endif /* _MSC_VER */ 113 114 #if (defined(__GNUC__) && (__GNUC__ >= 3)) || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 800)) || defined(__clang__) 115 # define expect(expr,value) (__builtin_expect ((expr),(value)) ) 116 #else 117 # define expect(expr,value) (expr) 118 #endif 119 120 #define likely(expr) expect((expr) != 0, 1) 121 #define unlikely(expr) expect((expr) != 0, 0) 122 123 124 /*-************************************ 125 * Memory routines 126 **************************************/ 127 #include <stdlib.h> /* malloc, calloc, free */ 128 #define ALLOCATOR(n,s) calloc(n,s) 129 #define FREEMEM free 130 #include <string.h> /* memset, memcpy */ 131 #define MEM_INIT memset 132 133 134 /*-************************************ 135 * Basic Types 136 **************************************/ 137 #if defined(__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 138 # include <stdint.h> 139 typedef uint8_t BYTE; 140 typedef uint16_t U16; 141 typedef uint32_t U32; 142 typedef int32_t S32; 143 typedef uint64_t U64; 144 typedef uintptr_t uptrval; 145 #else 146 typedef unsigned char BYTE; 147 typedef unsigned short U16; 148 typedef unsigned int U32; 149 typedef signed int S32; 150 typedef unsigned long long U64; 151 typedef size_t uptrval; /* generally true, except OpenVMS-64 */ 152 #endif 153 154 #if defined(__x86_64__) 155 typedef U64 reg_t; /* 64-bits in x32 mode */ 156 #else 157 typedef size_t reg_t; /* 32-bits in x32 mode */ 158 #endif 159 160 /*-************************************ 161 * Reading and writing into memory 162 **************************************/ 163 static unsigned LZ4_isLittleEndian(void) 164 { 165 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ 166 return one.c[0]; 167 } 168 169 170 #if defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==2) 171 /* lie to the compiler about data alignment; use with caution */ 172 173 static U16 LZ4_read16(const void* memPtr) { return *(const U16*) memPtr; } 174 static U32 LZ4_read32(const void* memPtr) { return *(const U32*) memPtr; } 175 static reg_t LZ4_read_ARCH(const void* memPtr) { return *(const reg_t*) memPtr; } 176 177 static void LZ4_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; } 178 static void LZ4_write32(void* memPtr, U32 value) { *(U32*)memPtr = value; } 179 180 #elif defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==1) 181 182 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ 183 /* currently only defined for gcc and icc */ 184 typedef union { U16 u16; U32 u32; reg_t uArch; } __attribute__((packed)) unalign; 185 186 static U16 LZ4_read16(const void* ptr) { return ((const unalign*)ptr)->u16; } 187 static U32 LZ4_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } 188 static reg_t LZ4_read_ARCH(const void* ptr) { return ((const unalign*)ptr)->uArch; } 189 190 static void LZ4_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; } 191 static void LZ4_write32(void* memPtr, U32 value) { ((unalign*)memPtr)->u32 = value; } 192 193 #else /* safe and portable access through memcpy() */ 194 195 static U16 LZ4_read16(const void* memPtr) 196 { 197 U16 val; memcpy(&val, memPtr, sizeof(val)); return val; 198 } 199 200 static U32 LZ4_read32(const void* memPtr) 201 { 202 U32 val; memcpy(&val, memPtr, sizeof(val)); return val; 203 } 204 205 static reg_t LZ4_read_ARCH(const void* memPtr) 206 { 207 reg_t val; memcpy(&val, memPtr, sizeof(val)); return val; 208 } 209 210 static void LZ4_write16(void* memPtr, U16 value) 211 { 212 memcpy(memPtr, &value, sizeof(value)); 213 } 214 215 static void LZ4_write32(void* memPtr, U32 value) 216 { 217 memcpy(memPtr, &value, sizeof(value)); 218 } 219 220 #endif /* LZ4_FORCE_MEMORY_ACCESS */ 221 222 223 static U16 LZ4_readLE16(const void* memPtr) 224 { 225 if (LZ4_isLittleEndian()) { 226 return LZ4_read16(memPtr); 227 } else { 228 const BYTE* p = (const BYTE*)memPtr; 229 return (U16)((U16)p[0] + (p[1]<<8)); 230 } 231 } 232 233 static void LZ4_writeLE16(void* memPtr, U16 value) 234 { 235 if (LZ4_isLittleEndian()) { 236 LZ4_write16(memPtr, value); 237 } else { 238 BYTE* p = (BYTE*)memPtr; 239 p[0] = (BYTE) value; 240 p[1] = (BYTE)(value>>8); 241 } 242 } 243 244 static void LZ4_copy8(void* dst, const void* src) 245 { 246 memcpy(dst,src,8); 247 } 248 249 /* customized variant of memcpy, which can overwrite up to 8 bytes beyond dstEnd */ 250 static void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd) 251 { 252 BYTE* d = (BYTE*)dstPtr; 253 const BYTE* s = (const BYTE*)srcPtr; 254 BYTE* const e = (BYTE*)dstEnd; 255 256 do { LZ4_copy8(d,s); d+=8; s+=8; } while (d<e); 257 } 258 259 260 /*-************************************ 261 * Common Constants 262 **************************************/ 263 #define MINMATCH 4 264 265 #define WILDCOPYLENGTH 8 266 #define LASTLITERALS 5 267 #define MFLIMIT (WILDCOPYLENGTH+MINMATCH) 268 static const int LZ4_minLength = (MFLIMIT+1); 269 270 #define KB *(1 <<10) 271 #define MB *(1 <<20) 272 #define GB *(1U<<30) 273 274 #define MAXD_LOG 16 275 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1) 276 277 #define ML_BITS 4 278 #define ML_MASK ((1U<<ML_BITS)-1) 279 #define RUN_BITS (8-ML_BITS) 280 #define RUN_MASK ((1U<<RUN_BITS)-1) 281 282 283 /*-************************************ 284 * Common Utils 285 **************************************/ 286 #define LZ4_STATIC_ASSERT(c) { enum { LZ4_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 287 288 289 /*-************************************ 290 * Common functions 291 **************************************/ 292 static unsigned LZ4_NbCommonBytes (register reg_t val) 293 { 294 if (LZ4_isLittleEndian()) { 295 if (sizeof(val)==8) { 296 # if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT) 297 unsigned long r = 0; 298 _BitScanForward64( &r, (U64)val ); 299 return (int)(r>>3); 300 # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT) 301 return (__builtin_ctzll((U64)val) >> 3); 302 # else 303 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 }; 304 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58]; 305 # endif 306 } else /* 32 bits */ { 307 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) 308 unsigned long r; 309 _BitScanForward( &r, (U32)val ); 310 return (int)(r>>3); 311 # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT) 312 return (__builtin_ctz((U32)val) >> 3); 313 # else 314 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 }; 315 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27]; 316 # endif 317 } 318 } else /* Big Endian CPU */ { 319 if (sizeof(val)==8) { 320 # if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT) 321 unsigned long r = 0; 322 _BitScanReverse64( &r, val ); 323 return (unsigned)(r>>3); 324 # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT) 325 return (__builtin_clzll((U64)val) >> 3); 326 # else 327 unsigned r; 328 if (!(val>>32)) { r=4; } else { r=0; val>>=32; } 329 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } 330 r += (!val); 331 return r; 332 # endif 333 } else /* 32 bits */ { 334 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) 335 unsigned long r = 0; 336 _BitScanReverse( &r, (unsigned long)val ); 337 return (unsigned)(r>>3); 338 # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT) 339 return (__builtin_clz((U32)val) >> 3); 340 # else 341 unsigned r; 342 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; } 343 r += (!val); 344 return r; 345 # endif 346 } 347 } 348 } 349 350 #define STEPSIZE sizeof(reg_t) 351 static unsigned LZ4_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* pInLimit) 352 { 353 const BYTE* const pStart = pIn; 354 355 while (likely(pIn<pInLimit-(STEPSIZE-1))) { 356 reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn); 357 if (!diff) { pIn+=STEPSIZE; pMatch+=STEPSIZE; continue; } 358 pIn += LZ4_NbCommonBytes(diff); 359 return (unsigned)(pIn - pStart); 360 } 361 362 if ((STEPSIZE==8) && (pIn<(pInLimit-3)) && (LZ4_read32(pMatch) == LZ4_read32(pIn))) { pIn+=4; pMatch+=4; } 363 if ((pIn<(pInLimit-1)) && (LZ4_read16(pMatch) == LZ4_read16(pIn))) { pIn+=2; pMatch+=2; } 364 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++; 365 return (unsigned)(pIn - pStart); 366 } 367 368 369 #ifndef LZ4_COMMONDEFS_ONLY 370 /*-************************************ 371 * Local Constants 372 **************************************/ 373 static const int LZ4_64Klimit = ((64 KB) + (MFLIMIT-1)); 374 static const U32 LZ4_skipTrigger = 6; /* Increase this value ==> compression run slower on incompressible data */ 375 376 377 /*-************************************ 378 * Local Structures and types 379 **************************************/ 380 typedef enum { notLimited = 0, limitedOutput = 1 } limitedOutput_directive; 381 typedef enum { byPtr, byU32, byU16 } tableType_t; 382 383 typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive; 384 typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive; 385 386 typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive; 387 typedef enum { full = 0, partial = 1 } earlyEnd_directive; 388 389 390 /*-************************************ 391 * Local Utils 392 **************************************/ 393 int LZ4_versionNumber (void) { return LZ4_VERSION_NUMBER; } 394 int LZ4_compressBound(int isize) { return LZ4_COMPRESSBOUND(isize); } 395 int LZ4_sizeofState() { return LZ4_STREAMSIZE; } 396 397 398 /*-****************************** 399 * Compression functions 400 ********************************/ 401 static U32 LZ4_hash4(U32 sequence, tableType_t const tableType) 402 { 403 if (tableType == byU16) 404 return ((sequence * 2654435761U) >> ((MINMATCH*8)-(LZ4_HASHLOG+1))); 405 else 406 return ((sequence * 2654435761U) >> ((MINMATCH*8)-LZ4_HASHLOG)); 407 } 408 409 static U32 LZ4_hash5(U64 sequence, tableType_t const tableType) 410 { 411 static const U64 prime5bytes = 889523592379ULL; 412 static const U64 prime8bytes = 11400714785074694791ULL; 413 const U32 hashLog = (tableType == byU16) ? LZ4_HASHLOG+1 : LZ4_HASHLOG; 414 if (LZ4_isLittleEndian()) 415 return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog)); 416 else 417 return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog)); 418 } 419 420 FORCE_INLINE U32 LZ4_hashPosition(const void* const p, tableType_t const tableType) 421 { 422 if ((sizeof(reg_t)==8) && (tableType != byU16)) return LZ4_hash5(LZ4_read_ARCH(p), tableType); 423 return LZ4_hash4(LZ4_read32(p), tableType); 424 } 425 426 static void LZ4_putPositionOnHash(const BYTE* p, U32 h, void* tableBase, tableType_t const tableType, const BYTE* srcBase) 427 { 428 switch (tableType) 429 { 430 case byPtr: { const BYTE** hashTable = (const BYTE**)tableBase; hashTable[h] = p; return; } 431 case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = (U32)(p-srcBase); return; } 432 case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = (U16)(p-srcBase); return; } 433 } 434 } 435 436 FORCE_INLINE void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase) 437 { 438 U32 const h = LZ4_hashPosition(p, tableType); 439 LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase); 440 } 441 442 static const BYTE* LZ4_getPositionOnHash(U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase) 443 { 444 if (tableType == byPtr) { const BYTE** hashTable = (const BYTE**) tableBase; return hashTable[h]; } 445 if (tableType == byU32) { const U32* const hashTable = (U32*) tableBase; return hashTable[h] + srcBase; } 446 { const U16* const hashTable = (U16*) tableBase; return hashTable[h] + srcBase; } /* default, to ensure a return */ 447 } 448 449 FORCE_INLINE const BYTE* LZ4_getPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase) 450 { 451 U32 const h = LZ4_hashPosition(p, tableType); 452 return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase); 453 } 454 455 456 /** LZ4_compress_generic() : 457 inlined, to ensure branches are decided at compilation time */ 458 FORCE_INLINE int LZ4_compress_generic( 459 LZ4_stream_t_internal* const cctx, 460 const char* const source, 461 char* const dest, 462 const int inputSize, 463 const int maxOutputSize, 464 const limitedOutput_directive outputLimited, 465 const tableType_t tableType, 466 const dict_directive dict, 467 const dictIssue_directive dictIssue, 468 const U32 acceleration) 469 { 470 const BYTE* ip = (const BYTE*) source; 471 const BYTE* base; 472 const BYTE* lowLimit; 473 const BYTE* const lowRefLimit = ip - cctx->dictSize; 474 const BYTE* const dictionary = cctx->dictionary; 475 const BYTE* const dictEnd = dictionary + cctx->dictSize; 476 const ptrdiff_t dictDelta = dictEnd - (const BYTE*)source; 477 const BYTE* anchor = (const BYTE*) source; 478 const BYTE* const iend = ip + inputSize; 479 const BYTE* const mflimit = iend - MFLIMIT; 480 const BYTE* const matchlimit = iend - LASTLITERALS; 481 482 BYTE* op = (BYTE*) dest; 483 BYTE* const olimit = op + maxOutputSize; 484 485 U32 forwardH; 486 487 /* Init conditions */ 488 if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported inputSize, too large (or negative) */ 489 switch(dict) 490 { 491 case noDict: 492 default: 493 base = (const BYTE*)source; 494 lowLimit = (const BYTE*)source; 495 break; 496 case withPrefix64k: 497 base = (const BYTE*)source - cctx->currentOffset; 498 lowLimit = (const BYTE*)source - cctx->dictSize; 499 break; 500 case usingExtDict: 501 base = (const BYTE*)source - cctx->currentOffset; 502 lowLimit = (const BYTE*)source; 503 break; 504 } 505 if ((tableType == byU16) && (inputSize>=LZ4_64Klimit)) return 0; /* Size too large (not within 64K limit) */ 506 if (inputSize<LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */ 507 508 /* First Byte */ 509 LZ4_putPosition(ip, cctx->hashTable, tableType, base); 510 ip++; forwardH = LZ4_hashPosition(ip, tableType); 511 512 /* Main Loop */ 513 for ( ; ; ) { 514 ptrdiff_t refDelta = 0; 515 const BYTE* match; 516 BYTE* token; 517 518 /* Find a match */ 519 { const BYTE* forwardIp = ip; 520 unsigned step = 1; 521 unsigned searchMatchNb = acceleration << LZ4_skipTrigger; 522 do { 523 U32 const h = forwardH; 524 ip = forwardIp; 525 forwardIp += step; 526 step = (searchMatchNb++ >> LZ4_skipTrigger); 527 528 if (unlikely(forwardIp > mflimit)) goto _last_literals; 529 530 match = LZ4_getPositionOnHash(h, cctx->hashTable, tableType, base); 531 if (dict==usingExtDict) { 532 if (match < (const BYTE*)source) { 533 refDelta = dictDelta; 534 lowLimit = dictionary; 535 } else { 536 refDelta = 0; 537 lowLimit = (const BYTE*)source; 538 } } 539 forwardH = LZ4_hashPosition(forwardIp, tableType); 540 LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType, base); 541 542 } while ( ((dictIssue==dictSmall) ? (match < lowRefLimit) : 0) 543 || ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip)) 544 || (LZ4_read32(match+refDelta) != LZ4_read32(ip)) ); 545 } 546 547 /* Catch up */ 548 while (((ip>anchor) & (match+refDelta > lowLimit)) && (unlikely(ip[-1]==match[refDelta-1]))) { ip--; match--; } 549 550 /* Encode Literals */ 551 { unsigned const litLength = (unsigned)(ip - anchor); 552 token = op++; 553 if ((outputLimited) && /* Check output buffer overflow */ 554 (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > olimit))) 555 return 0; 556 if (litLength >= RUN_MASK) { 557 int len = (int)litLength-RUN_MASK; 558 *token = (RUN_MASK<<ML_BITS); 559 for(; len >= 255 ; len-=255) *op++ = 255; 560 *op++ = (BYTE)len; 561 } 562 else *token = (BYTE)(litLength<<ML_BITS); 563 564 /* Copy Literals */ 565 LZ4_wildCopy(op, anchor, op+litLength); 566 op+=litLength; 567 } 568 569 _next_match: 570 /* Encode Offset */ 571 LZ4_writeLE16(op, (U16)(ip-match)); op+=2; 572 573 /* Encode MatchLength */ 574 { unsigned matchCode; 575 576 if ((dict==usingExtDict) && (lowLimit==dictionary)) { 577 const BYTE* limit; 578 match += refDelta; 579 limit = ip + (dictEnd-match); 580 if (limit > matchlimit) limit = matchlimit; 581 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, limit); 582 ip += MINMATCH + matchCode; 583 if (ip==limit) { 584 unsigned const more = LZ4_count(ip, (const BYTE*)source, matchlimit); 585 matchCode += more; 586 ip += more; 587 } 588 } else { 589 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit); 590 ip += MINMATCH + matchCode; 591 } 592 593 if ( outputLimited && /* Check output buffer overflow */ 594 (unlikely(op + (1 + LASTLITERALS) + (matchCode>>8) > olimit)) ) 595 return 0; 596 if (matchCode >= ML_MASK) { 597 *token += ML_MASK; 598 matchCode -= ML_MASK; 599 LZ4_write32(op, 0xFFFFFFFF); 600 while (matchCode >= 4*255) op+=4, LZ4_write32(op, 0xFFFFFFFF), matchCode -= 4*255; 601 op += matchCode / 255; 602 *op++ = (BYTE)(matchCode % 255); 603 } else 604 *token += (BYTE)(matchCode); 605 } 606 607 anchor = ip; 608 609 /* Test end of chunk */ 610 if (ip > mflimit) break; 611 612 /* Fill table */ 613 LZ4_putPosition(ip-2, cctx->hashTable, tableType, base); 614 615 /* Test next position */ 616 match = LZ4_getPosition(ip, cctx->hashTable, tableType, base); 617 if (dict==usingExtDict) { 618 if (match < (const BYTE*)source) { 619 refDelta = dictDelta; 620 lowLimit = dictionary; 621 } else { 622 refDelta = 0; 623 lowLimit = (const BYTE*)source; 624 } } 625 LZ4_putPosition(ip, cctx->hashTable, tableType, base); 626 if ( ((dictIssue==dictSmall) ? (match>=lowRefLimit) : 1) 627 && (match+MAX_DISTANCE>=ip) 628 && (LZ4_read32(match+refDelta)==LZ4_read32(ip)) ) 629 { token=op++; *token=0; goto _next_match; } 630 631 /* Prepare next loop */ 632 forwardH = LZ4_hashPosition(++ip, tableType); 633 } 634 635 _last_literals: 636 /* Encode Last Literals */ 637 { size_t const lastRun = (size_t)(iend - anchor); 638 if ( (outputLimited) && /* Check output buffer overflow */ 639 ((op - (BYTE*)dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize) ) 640 return 0; 641 if (lastRun >= RUN_MASK) { 642 size_t accumulator = lastRun - RUN_MASK; 643 *op++ = RUN_MASK << ML_BITS; 644 for(; accumulator >= 255 ; accumulator-=255) *op++ = 255; 645 *op++ = (BYTE) accumulator; 646 } else { 647 *op++ = (BYTE)(lastRun<<ML_BITS); 648 } 649 memcpy(op, anchor, lastRun); 650 op += lastRun; 651 } 652 653 /* End */ 654 return (int) (((char*)op)-dest); 655 } 656 657 658 int LZ4_compress_fast_extState(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration) 659 { 660 LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)state)->internal_donotuse; 661 LZ4_resetStream((LZ4_stream_t*)state); 662 if (acceleration < 1) acceleration = ACCELERATION_DEFAULT; 663 664 if (maxOutputSize >= LZ4_compressBound(inputSize)) { 665 if (inputSize < LZ4_64Klimit) 666 return LZ4_compress_generic(ctx, source, dest, inputSize, 0, notLimited, byU16, noDict, noDictIssue, acceleration); 667 else 668 return LZ4_compress_generic(ctx, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue, acceleration); 669 } else { 670 if (inputSize < LZ4_64Klimit) 671 return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue, acceleration); 672 else 673 return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue, acceleration); 674 } 675 } 676 677 678 int LZ4_compress_fast(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration) 679 { 680 #if (HEAPMODE) 681 void* ctxPtr = ALLOCATOR(1, sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */ 682 #else 683 LZ4_stream_t ctx; 684 void* const ctxPtr = &ctx; 685 #endif 686 687 int const result = LZ4_compress_fast_extState(ctxPtr, source, dest, inputSize, maxOutputSize, acceleration); 688 689 #if (HEAPMODE) 690 FREEMEM(ctxPtr); 691 #endif 692 return result; 693 } 694 695 696 int LZ4_compress_default(const char* source, char* dest, int inputSize, int maxOutputSize) 697 { 698 return LZ4_compress_fast(source, dest, inputSize, maxOutputSize, 1); 699 } 700 701 702 /* hidden debug function */ 703 /* strangely enough, gcc generates faster code when this function is uncommented, even if unused */ 704 int LZ4_compress_fast_force(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration) 705 { 706 LZ4_stream_t ctx; 707 LZ4_resetStream(&ctx); 708 709 if (inputSize < LZ4_64Klimit) 710 return LZ4_compress_generic(&ctx.internal_donotuse, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue, acceleration); 711 else 712 return LZ4_compress_generic(&ctx.internal_donotuse, source, dest, inputSize, maxOutputSize, limitedOutput, sizeof(void*)==8 ? byU32 : byPtr, noDict, noDictIssue, acceleration); 713 } 714 715 716 /*-****************************** 717 * *_destSize() variant 718 ********************************/ 719 720 static int LZ4_compress_destSize_generic( 721 LZ4_stream_t_internal* const ctx, 722 const char* const src, 723 char* const dst, 724 int* const srcSizePtr, 725 const int targetDstSize, 726 const tableType_t tableType) 727 { 728 const BYTE* ip = (const BYTE*) src; 729 const BYTE* base = (const BYTE*) src; 730 const BYTE* lowLimit = (const BYTE*) src; 731 const BYTE* anchor = ip; 732 const BYTE* const iend = ip + *srcSizePtr; 733 const BYTE* const mflimit = iend - MFLIMIT; 734 const BYTE* const matchlimit = iend - LASTLITERALS; 735 736 BYTE* op = (BYTE*) dst; 737 BYTE* const oend = op + targetDstSize; 738 BYTE* const oMaxLit = op + targetDstSize - 2 /* offset */ - 8 /* because 8+MINMATCH==MFLIMIT */ - 1 /* token */; 739 BYTE* const oMaxMatch = op + targetDstSize - (LASTLITERALS + 1 /* token */); 740 BYTE* const oMaxSeq = oMaxLit - 1 /* token */; 741 742 U32 forwardH; 743 744 745 /* Init conditions */ 746 if (targetDstSize < 1) return 0; /* Impossible to store anything */ 747 if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */ 748 if ((tableType == byU16) && (*srcSizePtr>=LZ4_64Klimit)) return 0; /* Size too large (not within 64K limit) */ 749 if (*srcSizePtr<LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */ 750 751 /* First Byte */ 752 *srcSizePtr = 0; 753 LZ4_putPosition(ip, ctx->hashTable, tableType, base); 754 ip++; forwardH = LZ4_hashPosition(ip, tableType); 755 756 /* Main Loop */ 757 for ( ; ; ) { 758 const BYTE* match; 759 BYTE* token; 760 761 /* Find a match */ 762 { const BYTE* forwardIp = ip; 763 unsigned step = 1; 764 unsigned searchMatchNb = 1 << LZ4_skipTrigger; 765 766 do { 767 U32 h = forwardH; 768 ip = forwardIp; 769 forwardIp += step; 770 step = (searchMatchNb++ >> LZ4_skipTrigger); 771 772 if (unlikely(forwardIp > mflimit)) goto _last_literals; 773 774 match = LZ4_getPositionOnHash(h, ctx->hashTable, tableType, base); 775 forwardH = LZ4_hashPosition(forwardIp, tableType); 776 LZ4_putPositionOnHash(ip, h, ctx->hashTable, tableType, base); 777 778 } while ( ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip)) 779 || (LZ4_read32(match) != LZ4_read32(ip)) ); 780 } 781 782 /* Catch up */ 783 while ((ip>anchor) && (match > lowLimit) && (unlikely(ip[-1]==match[-1]))) { ip--; match--; } 784 785 /* Encode Literal length */ 786 { unsigned litLength = (unsigned)(ip - anchor); 787 token = op++; 788 if (op + ((litLength+240)/255) + litLength > oMaxLit) { 789 /* Not enough space for a last match */ 790 op--; 791 goto _last_literals; 792 } 793 if (litLength>=RUN_MASK) { 794 unsigned len = litLength - RUN_MASK; 795 *token=(RUN_MASK<<ML_BITS); 796 for(; len >= 255 ; len-=255) *op++ = 255; 797 *op++ = (BYTE)len; 798 } 799 else *token = (BYTE)(litLength<<ML_BITS); 800 801 /* Copy Literals */ 802 LZ4_wildCopy(op, anchor, op+litLength); 803 op += litLength; 804 } 805 806 _next_match: 807 /* Encode Offset */ 808 LZ4_writeLE16(op, (U16)(ip-match)); op+=2; 809 810 /* Encode MatchLength */ 811 { size_t matchLength = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit); 812 813 if (op + ((matchLength+240)/255) > oMaxMatch) { 814 /* Match description too long : reduce it */ 815 matchLength = (15-1) + (oMaxMatch-op) * 255; 816 } 817 ip += MINMATCH + matchLength; 818 819 if (matchLength>=ML_MASK) { 820 *token += ML_MASK; 821 matchLength -= ML_MASK; 822 while (matchLength >= 255) { matchLength-=255; *op++ = 255; } 823 *op++ = (BYTE)matchLength; 824 } 825 else *token += (BYTE)(matchLength); 826 } 827 828 anchor = ip; 829 830 /* Test end of block */ 831 if (ip > mflimit) break; 832 if (op > oMaxSeq) break; 833 834 /* Fill table */ 835 LZ4_putPosition(ip-2, ctx->hashTable, tableType, base); 836 837 /* Test next position */ 838 match = LZ4_getPosition(ip, ctx->hashTable, tableType, base); 839 LZ4_putPosition(ip, ctx->hashTable, tableType, base); 840 if ( (match+MAX_DISTANCE>=ip) 841 && (LZ4_read32(match)==LZ4_read32(ip)) ) 842 { token=op++; *token=0; goto _next_match; } 843 844 /* Prepare next loop */ 845 forwardH = LZ4_hashPosition(++ip, tableType); 846 } 847 848 _last_literals: 849 /* Encode Last Literals */ 850 { size_t lastRunSize = (size_t)(iend - anchor); 851 if (op + 1 /* token */ + ((lastRunSize+240)/255) /* litLength */ + lastRunSize /* literals */ > oend) { 852 /* adapt lastRunSize to fill 'dst' */ 853 lastRunSize = (oend-op) - 1; 854 lastRunSize -= (lastRunSize+240)/255; 855 } 856 ip = anchor + lastRunSize; 857 858 if (lastRunSize >= RUN_MASK) { 859 size_t accumulator = lastRunSize - RUN_MASK; 860 *op++ = RUN_MASK << ML_BITS; 861 for(; accumulator >= 255 ; accumulator-=255) *op++ = 255; 862 *op++ = (BYTE) accumulator; 863 } else { 864 *op++ = (BYTE)(lastRunSize<<ML_BITS); 865 } 866 memcpy(op, anchor, lastRunSize); 867 op += lastRunSize; 868 } 869 870 /* End */ 871 *srcSizePtr = (int) (((const char*)ip)-src); 872 return (int) (((char*)op)-dst); 873 } 874 875 876 static int LZ4_compress_destSize_extState (LZ4_stream_t* state, const char* src, char* dst, int* srcSizePtr, int targetDstSize) 877 { 878 LZ4_resetStream(state); 879 880 if (targetDstSize >= LZ4_compressBound(*srcSizePtr)) { /* compression success is guaranteed */ 881 return LZ4_compress_fast_extState(state, src, dst, *srcSizePtr, targetDstSize, 1); 882 } else { 883 if (*srcSizePtr < LZ4_64Klimit) 884 return LZ4_compress_destSize_generic(&state->internal_donotuse, src, dst, srcSizePtr, targetDstSize, byU16); 885 else 886 return LZ4_compress_destSize_generic(&state->internal_donotuse, src, dst, srcSizePtr, targetDstSize, sizeof(void*)==8 ? byU32 : byPtr); 887 } 888 } 889 890 891 int LZ4_compress_destSize(const char* src, char* dst, int* srcSizePtr, int targetDstSize) 892 { 893 #if (HEAPMODE) 894 LZ4_stream_t* ctx = (LZ4_stream_t*)ALLOCATOR(1, sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */ 895 #else 896 LZ4_stream_t ctxBody; 897 LZ4_stream_t* ctx = &ctxBody; 898 #endif 899 900 int result = LZ4_compress_destSize_extState(ctx, src, dst, srcSizePtr, targetDstSize); 901 902 #if (HEAPMODE) 903 FREEMEM(ctx); 904 #endif 905 return result; 906 } 907 908 909 910 /*-****************************** 911 * Streaming functions 912 ********************************/ 913 914 LZ4_stream_t* LZ4_createStream(void) 915 { 916 LZ4_stream_t* lz4s = (LZ4_stream_t*)ALLOCATOR(8, LZ4_STREAMSIZE_U64); 917 LZ4_STATIC_ASSERT(LZ4_STREAMSIZE >= sizeof(LZ4_stream_t_internal)); /* A compilation error here means LZ4_STREAMSIZE is not large enough */ 918 LZ4_resetStream(lz4s); 919 return lz4s; 920 } 921 922 void LZ4_resetStream (LZ4_stream_t* LZ4_stream) 923 { 924 MEM_INIT(LZ4_stream, 0, sizeof(LZ4_stream_t)); 925 } 926 927 int LZ4_freeStream (LZ4_stream_t* LZ4_stream) 928 { 929 FREEMEM(LZ4_stream); 930 return (0); 931 } 932 933 934 #define HASH_UNIT sizeof(reg_t) 935 int LZ4_loadDict (LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize) 936 { 937 LZ4_stream_t_internal* dict = &LZ4_dict->internal_donotuse; 938 const BYTE* p = (const BYTE*)dictionary; 939 const BYTE* const dictEnd = p + dictSize; 940 const BYTE* base; 941 942 if ((dict->initCheck) || (dict->currentOffset > 1 GB)) /* Uninitialized structure, or reuse overflow */ 943 LZ4_resetStream(LZ4_dict); 944 945 if (dictSize < (int)HASH_UNIT) { 946 dict->dictionary = NULL; 947 dict->dictSize = 0; 948 return 0; 949 } 950 951 if ((dictEnd - p) > 64 KB) p = dictEnd - 64 KB; 952 dict->currentOffset += 64 KB; 953 base = p - dict->currentOffset; 954 dict->dictionary = p; 955 dict->dictSize = (U32)(dictEnd - p); 956 dict->currentOffset += dict->dictSize; 957 958 while (p <= dictEnd-HASH_UNIT) { 959 LZ4_putPosition(p, dict->hashTable, byU32, base); 960 p+=3; 961 } 962 963 return dict->dictSize; 964 } 965 966 967 static void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, const BYTE* src) 968 { 969 if ((LZ4_dict->currentOffset > 0x80000000) || 970 ((uptrval)LZ4_dict->currentOffset > (uptrval)src)) { /* address space overflow */ 971 /* rescale hash table */ 972 U32 const delta = LZ4_dict->currentOffset - 64 KB; 973 const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize; 974 int i; 975 for (i=0; i<LZ4_HASH_SIZE_U32; i++) { 976 if (LZ4_dict->hashTable[i] < delta) LZ4_dict->hashTable[i]=0; 977 else LZ4_dict->hashTable[i] -= delta; 978 } 979 LZ4_dict->currentOffset = 64 KB; 980 if (LZ4_dict->dictSize > 64 KB) LZ4_dict->dictSize = 64 KB; 981 LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize; 982 } 983 } 984 985 986 int LZ4_compress_fast_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration) 987 { 988 LZ4_stream_t_internal* streamPtr = &LZ4_stream->internal_donotuse; 989 const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; 990 991 const BYTE* smallest = (const BYTE*) source; 992 if (streamPtr->initCheck) return 0; /* Uninitialized structure detected */ 993 if ((streamPtr->dictSize>0) && (smallest>dictEnd)) smallest = dictEnd; 994 LZ4_renormDictT(streamPtr, smallest); 995 if (acceleration < 1) acceleration = ACCELERATION_DEFAULT; 996 997 /* Check overlapping input/dictionary space */ 998 { const BYTE* sourceEnd = (const BYTE*) source + inputSize; 999 if ((sourceEnd > streamPtr->dictionary) && (sourceEnd < dictEnd)) { 1000 streamPtr->dictSize = (U32)(dictEnd - sourceEnd); 1001 if (streamPtr->dictSize > 64 KB) streamPtr->dictSize = 64 KB; 1002 if (streamPtr->dictSize < 4) streamPtr->dictSize = 0; 1003 streamPtr->dictionary = dictEnd - streamPtr->dictSize; 1004 } 1005 } 1006 1007 /* prefix mode : source data follows dictionary */ 1008 if (dictEnd == (const BYTE*)source) { 1009 int result; 1010 if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) 1011 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k, dictSmall, acceleration); 1012 else 1013 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k, noDictIssue, acceleration); 1014 streamPtr->dictSize += (U32)inputSize; 1015 streamPtr->currentOffset += (U32)inputSize; 1016 return result; 1017 } 1018 1019 /* external dictionary mode */ 1020 { int result; 1021 if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) 1022 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingExtDict, dictSmall, acceleration); 1023 else 1024 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingExtDict, noDictIssue, acceleration); 1025 streamPtr->dictionary = (const BYTE*)source; 1026 streamPtr->dictSize = (U32)inputSize; 1027 streamPtr->currentOffset += (U32)inputSize; 1028 return result; 1029 } 1030 } 1031 1032 1033 /* Hidden debug function, to force external dictionary mode */ 1034 int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int inputSize) 1035 { 1036 LZ4_stream_t_internal* streamPtr = &LZ4_dict->internal_donotuse; 1037 int result; 1038 const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; 1039 1040 const BYTE* smallest = dictEnd; 1041 if (smallest > (const BYTE*) source) smallest = (const BYTE*) source; 1042 LZ4_renormDictT(streamPtr, smallest); 1043 1044 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, 0, notLimited, byU32, usingExtDict, noDictIssue, 1); 1045 1046 streamPtr->dictionary = (const BYTE*)source; 1047 streamPtr->dictSize = (U32)inputSize; 1048 streamPtr->currentOffset += (U32)inputSize; 1049 1050 return result; 1051 } 1052 1053 1054 /*! LZ4_saveDict() : 1055 * If previously compressed data block is not guaranteed to remain available at its memory location, 1056 * save it into a safer place (char* safeBuffer). 1057 * Note : you don't need to call LZ4_loadDict() afterwards, 1058 * dictionary is immediately usable, you can therefore call LZ4_compress_fast_continue(). 1059 * Return : saved dictionary size in bytes (necessarily <= dictSize), or 0 if error. 1060 */ 1061 int LZ4_saveDict (LZ4_stream_t* LZ4_dict, char* safeBuffer, int dictSize) 1062 { 1063 LZ4_stream_t_internal* const dict = &LZ4_dict->internal_donotuse; 1064 const BYTE* const previousDictEnd = dict->dictionary + dict->dictSize; 1065 1066 if ((U32)dictSize > 64 KB) dictSize = 64 KB; /* useless to define a dictionary > 64 KB */ 1067 if ((U32)dictSize > dict->dictSize) dictSize = dict->dictSize; 1068 1069 memmove(safeBuffer, previousDictEnd - dictSize, dictSize); 1070 1071 dict->dictionary = (const BYTE*)safeBuffer; 1072 dict->dictSize = (U32)dictSize; 1073 1074 return dictSize; 1075 } 1076 1077 1078 1079 /*-***************************** 1080 * Decompression functions 1081 *******************************/ 1082 /*! LZ4_decompress_generic() : 1083 * This generic decompression function cover all use cases. 1084 * It shall be instantiated several times, using different sets of directives 1085 * Note that it is important this generic function is really inlined, 1086 * in order to remove useless branches during compilation optimization. 1087 */ 1088 FORCE_INLINE int LZ4_decompress_generic( 1089 const char* const source, 1090 char* const dest, 1091 int inputSize, 1092 int outputSize, /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */ 1093 1094 int endOnInput, /* endOnOutputSize, endOnInputSize */ 1095 int partialDecoding, /* full, partial */ 1096 int targetOutputSize, /* only used if partialDecoding==partial */ 1097 int dict, /* noDict, withPrefix64k, usingExtDict */ 1098 const BYTE* const lowPrefix, /* == dest when no prefix */ 1099 const BYTE* const dictStart, /* only if dict==usingExtDict */ 1100 const size_t dictSize /* note : = 0 if noDict */ 1101 ) 1102 { 1103 /* Local Variables */ 1104 const BYTE* ip = (const BYTE*) source; 1105 const BYTE* const iend = ip + inputSize; 1106 1107 BYTE* op = (BYTE*) dest; 1108 BYTE* const oend = op + outputSize; 1109 BYTE* cpy; 1110 BYTE* oexit = op + targetOutputSize; 1111 const BYTE* const lowLimit = lowPrefix - dictSize; 1112 1113 const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize; 1114 const unsigned dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; 1115 const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3}; 1116 1117 const int safeDecode = (endOnInput==endOnInputSize); 1118 const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB))); 1119 1120 1121 /* Special cases */ 1122 if ((partialDecoding) && (oexit > oend-MFLIMIT)) oexit = oend-MFLIMIT; /* targetOutputSize too high => decode everything */ 1123 if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1; /* Empty output buffer */ 1124 if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1); 1125 1126 /* Main Loop : decode sequences */ 1127 while (1) { 1128 size_t length; 1129 const BYTE* match; 1130 size_t offset; 1131 1132 /* get literal length */ 1133 unsigned const token = *ip++; 1134 if ((length=(token>>ML_BITS)) == RUN_MASK) { 1135 unsigned s; 1136 do { 1137 s = *ip++; 1138 length += s; 1139 } while ( likely(endOnInput ? ip<iend-RUN_MASK : 1) & (s==255) ); 1140 if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)(op))) goto _output_error; /* overflow detection */ 1141 if ((safeDecode) && unlikely((uptrval)(ip)+length<(uptrval)(ip))) goto _output_error; /* overflow detection */ 1142 } 1143 1144 /* copy literals */ 1145 cpy = op+length; 1146 if ( ((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) ) 1147 || ((!endOnInput) && (cpy>oend-WILDCOPYLENGTH)) ) 1148 { 1149 if (partialDecoding) { 1150 if (cpy > oend) goto _output_error; /* Error : write attempt beyond end of output buffer */ 1151 if ((endOnInput) && (ip+length > iend)) goto _output_error; /* Error : read attempt beyond end of input buffer */ 1152 } else { 1153 if ((!endOnInput) && (cpy != oend)) goto _output_error; /* Error : block decoding must stop exactly there */ 1154 if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error; /* Error : input must be consumed */ 1155 } 1156 memcpy(op, ip, length); 1157 ip += length; 1158 op += length; 1159 break; /* Necessarily EOF, due to parsing restrictions */ 1160 } 1161 LZ4_wildCopy(op, ip, cpy); 1162 ip += length; op = cpy; 1163 1164 /* get offset */ 1165 offset = LZ4_readLE16(ip); ip+=2; 1166 match = op - offset; 1167 if ((checkOffset) && (unlikely(match < lowLimit))) goto _output_error; /* Error : offset outside buffers */ 1168 LZ4_write32(op, (U32)offset); /* costs ~1%; silence an msan warning when offset==0 */ 1169 1170 /* get matchlength */ 1171 length = token & ML_MASK; 1172 if (length == ML_MASK) { 1173 unsigned s; 1174 do { 1175 s = *ip++; 1176 if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error; 1177 length += s; 1178 } while (s==255); 1179 if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)op)) goto _output_error; /* overflow detection */ 1180 } 1181 length += MINMATCH; 1182 1183 /* check external dictionary */ 1184 if ((dict==usingExtDict) && (match < lowPrefix)) { 1185 if (unlikely(op+length > oend-LASTLITERALS)) goto _output_error; /* doesn't respect parsing restriction */ 1186 1187 if (length <= (size_t)(lowPrefix-match)) { 1188 /* match can be copied as a single segment from external dictionary */ 1189 memmove(op, dictEnd - (lowPrefix-match), length); 1190 op += length; 1191 } else { 1192 /* match encompass external dictionary and current block */ 1193 size_t const copySize = (size_t)(lowPrefix-match); 1194 size_t const restSize = length - copySize; 1195 memcpy(op, dictEnd - copySize, copySize); 1196 op += copySize; 1197 if (restSize > (size_t)(op-lowPrefix)) { /* overlap copy */ 1198 BYTE* const endOfMatch = op + restSize; 1199 const BYTE* copyFrom = lowPrefix; 1200 while (op < endOfMatch) *op++ = *copyFrom++; 1201 } else { 1202 memcpy(op, lowPrefix, restSize); 1203 op += restSize; 1204 } } 1205 continue; 1206 } 1207 1208 /* copy match within block */ 1209 cpy = op + length; 1210 if (unlikely(offset<8)) { 1211 const int dec64 = dec64table[offset]; 1212 op[0] = match[0]; 1213 op[1] = match[1]; 1214 op[2] = match[2]; 1215 op[3] = match[3]; 1216 match += dec32table[offset]; 1217 memcpy(op+4, match, 4); 1218 match -= dec64; 1219 } else { LZ4_copy8(op, match); match+=8; } 1220 op += 8; 1221 1222 if (unlikely(cpy>oend-12)) { 1223 BYTE* const oCopyLimit = oend-(WILDCOPYLENGTH-1); 1224 if (cpy > oend-LASTLITERALS) goto _output_error; /* Error : last LASTLITERALS bytes must be literals (uncompressed) */ 1225 if (op < oCopyLimit) { 1226 LZ4_wildCopy(op, match, oCopyLimit); 1227 match += oCopyLimit - op; 1228 op = oCopyLimit; 1229 } 1230 while (op<cpy) *op++ = *match++; 1231 } else { 1232 LZ4_copy8(op, match); 1233 if (length>16) LZ4_wildCopy(op+8, match+8, cpy); 1234 } 1235 op=cpy; /* correction */ 1236 } 1237 1238 /* end of decoding */ 1239 if (endOnInput) 1240 return (int) (((char*)op)-dest); /* Nb of output bytes decoded */ 1241 else 1242 return (int) (((const char*)ip)-source); /* Nb of input bytes read */ 1243 1244 /* Overflow error detected */ 1245 _output_error: 1246 return (int) (-(((const char*)ip)-source))-1; 1247 } 1248 1249 1250 int LZ4_decompress_safe(const char* source, char* dest, int compressedSize, int maxDecompressedSize) 1251 { 1252 return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize, endOnInputSize, full, 0, noDict, (BYTE*)dest, NULL, 0); 1253 } 1254 1255 int LZ4_decompress_safe_partial(const char* source, char* dest, int compressedSize, int targetOutputSize, int maxDecompressedSize) 1256 { 1257 return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize, endOnInputSize, partial, targetOutputSize, noDict, (BYTE*)dest, NULL, 0); 1258 } 1259 1260 int LZ4_decompress_fast(const char* source, char* dest, int originalSize) 1261 { 1262 return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, (BYTE*)(dest - 64 KB), NULL, 64 KB); 1263 } 1264 1265 1266 /*===== streaming decompression functions =====*/ 1267 1268 /* 1269 * If you prefer dynamic allocation methods, 1270 * LZ4_createStreamDecode() 1271 * provides a pointer (void*) towards an initialized LZ4_streamDecode_t structure. 1272 */ 1273 LZ4_streamDecode_t* LZ4_createStreamDecode(void) 1274 { 1275 LZ4_streamDecode_t* lz4s = (LZ4_streamDecode_t*) ALLOCATOR(1, sizeof(LZ4_streamDecode_t)); 1276 return lz4s; 1277 } 1278 1279 int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream) 1280 { 1281 FREEMEM(LZ4_stream); 1282 return 0; 1283 } 1284 1285 /*! 1286 * LZ4_setStreamDecode() : 1287 * Use this function to instruct where to find the dictionary. 1288 * This function is not necessary if previous data is still available where it was decoded. 1289 * Loading a size of 0 is allowed (same effect as no dictionary). 1290 * Return : 1 if OK, 0 if error 1291 */ 1292 int LZ4_setStreamDecode (LZ4_streamDecode_t* LZ4_streamDecode, const char* dictionary, int dictSize) 1293 { 1294 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse; 1295 lz4sd->prefixSize = (size_t) dictSize; 1296 lz4sd->prefixEnd = (const BYTE*) dictionary + dictSize; 1297 lz4sd->externalDict = NULL; 1298 lz4sd->extDictSize = 0; 1299 return 1; 1300 } 1301 1302 /* 1303 *_continue() : 1304 These decoding functions allow decompression of multiple blocks in "streaming" mode. 1305 Previously decoded blocks must still be available at the memory position where they were decoded. 1306 If it's not possible, save the relevant part of decoded data into a safe buffer, 1307 and indicate where it stands using LZ4_setStreamDecode() 1308 */ 1309 int LZ4_decompress_safe_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxOutputSize) 1310 { 1311 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse; 1312 int result; 1313 1314 if (lz4sd->prefixEnd == (BYTE*)dest) { 1315 result = LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, 1316 endOnInputSize, full, 0, 1317 usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize); 1318 if (result <= 0) return result; 1319 lz4sd->prefixSize += result; 1320 lz4sd->prefixEnd += result; 1321 } else { 1322 lz4sd->extDictSize = lz4sd->prefixSize; 1323 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; 1324 result = LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, 1325 endOnInputSize, full, 0, 1326 usingExtDict, (BYTE*)dest, lz4sd->externalDict, lz4sd->extDictSize); 1327 if (result <= 0) return result; 1328 lz4sd->prefixSize = result; 1329 lz4sd->prefixEnd = (BYTE*)dest + result; 1330 } 1331 1332 return result; 1333 } 1334 1335 int LZ4_decompress_fast_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int originalSize) 1336 { 1337 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse; 1338 int result; 1339 1340 if (lz4sd->prefixEnd == (BYTE*)dest) { 1341 result = LZ4_decompress_generic(source, dest, 0, originalSize, 1342 endOnOutputSize, full, 0, 1343 usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize); 1344 if (result <= 0) return result; 1345 lz4sd->prefixSize += originalSize; 1346 lz4sd->prefixEnd += originalSize; 1347 } else { 1348 lz4sd->extDictSize = lz4sd->prefixSize; 1349 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; 1350 result = LZ4_decompress_generic(source, dest, 0, originalSize, 1351 endOnOutputSize, full, 0, 1352 usingExtDict, (BYTE*)dest, lz4sd->externalDict, lz4sd->extDictSize); 1353 if (result <= 0) return result; 1354 lz4sd->prefixSize = originalSize; 1355 lz4sd->prefixEnd = (BYTE*)dest + originalSize; 1356 } 1357 1358 return result; 1359 } 1360 1361 1362 /* 1363 Advanced decoding functions : 1364 *_usingDict() : 1365 These decoding functions work the same as "_continue" ones, 1366 the dictionary must be explicitly provided within parameters 1367 */ 1368 1369 FORCE_INLINE int LZ4_decompress_usingDict_generic(const char* source, char* dest, int compressedSize, int maxOutputSize, int safe, const char* dictStart, int dictSize) 1370 { 1371 if (dictSize==0) 1372 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, noDict, (BYTE*)dest, NULL, 0); 1373 if (dictStart+dictSize == dest) { 1374 if (dictSize >= (int)(64 KB - 1)) 1375 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, withPrefix64k, (BYTE*)dest-64 KB, NULL, 0); 1376 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, noDict, (BYTE*)dest-dictSize, NULL, 0); 1377 } 1378 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, usingExtDict, (BYTE*)dest, (const BYTE*)dictStart, dictSize); 1379 } 1380 1381 int LZ4_decompress_safe_usingDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize) 1382 { 1383 return LZ4_decompress_usingDict_generic(source, dest, compressedSize, maxOutputSize, 1, dictStart, dictSize); 1384 } 1385 1386 int LZ4_decompress_fast_usingDict(const char* source, char* dest, int originalSize, const char* dictStart, int dictSize) 1387 { 1388 return LZ4_decompress_usingDict_generic(source, dest, 0, originalSize, 0, dictStart, dictSize); 1389 } 1390 1391 /* debug function */ 1392 int LZ4_decompress_safe_forceExtDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize) 1393 { 1394 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, usingExtDict, (BYTE*)dest, (const BYTE*)dictStart, dictSize); 1395 } 1396 1397 1398 /*=************************************************* 1399 * Obsolete Functions 1400 ***************************************************/ 1401 /* obsolete compression functions */ 1402 int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize) { return LZ4_compress_default(source, dest, inputSize, maxOutputSize); } 1403 int LZ4_compress(const char* source, char* dest, int inputSize) { return LZ4_compress_default(source, dest, inputSize, LZ4_compressBound(inputSize)); } 1404 int LZ4_compress_limitedOutput_withState (void* state, const char* src, char* dst, int srcSize, int dstSize) { return LZ4_compress_fast_extState(state, src, dst, srcSize, dstSize, 1); } 1405 int LZ4_compress_withState (void* state, const char* src, char* dst, int srcSize) { return LZ4_compress_fast_extState(state, src, dst, srcSize, LZ4_compressBound(srcSize), 1); } 1406 int LZ4_compress_limitedOutput_continue (LZ4_stream_t* LZ4_stream, const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_fast_continue(LZ4_stream, src, dst, srcSize, maxDstSize, 1); } 1407 int LZ4_compress_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize) { return LZ4_compress_fast_continue(LZ4_stream, source, dest, inputSize, LZ4_compressBound(inputSize), 1); } 1408 1409 /* 1410 These function names are deprecated and should no longer be used. 1411 They are only provided here for compatibility with older user programs. 1412 - LZ4_uncompress is totally equivalent to LZ4_decompress_fast 1413 - LZ4_uncompress_unknownOutputSize is totally equivalent to LZ4_decompress_safe 1414 */ 1415 int LZ4_uncompress (const char* source, char* dest, int outputSize) { return LZ4_decompress_fast(source, dest, outputSize); } 1416 int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize) { return LZ4_decompress_safe(source, dest, isize, maxOutputSize); } 1417 1418 1419 /* Obsolete Streaming functions */ 1420 1421 int LZ4_sizeofStreamState() { return LZ4_STREAMSIZE; } 1422 1423 static void LZ4_init(LZ4_stream_t* lz4ds, BYTE* base) 1424 { 1425 MEM_INIT(lz4ds, 0, sizeof(LZ4_stream_t)); 1426 lz4ds->internal_donotuse.bufferStart = base; 1427 } 1428 1429 int LZ4_resetStreamState(void* state, char* inputBuffer) 1430 { 1431 if ((((uptrval)state) & 3) != 0) return 1; /* Error : pointer is not aligned on 4-bytes boundary */ 1432 LZ4_init((LZ4_stream_t*)state, (BYTE*)inputBuffer); 1433 return 0; 1434 } 1435 1436 void* LZ4_create (char* inputBuffer) 1437 { 1438 LZ4_stream_t* lz4ds = (LZ4_stream_t*)ALLOCATOR(8, sizeof(LZ4_stream_t)); 1439 LZ4_init (lz4ds, (BYTE*)inputBuffer); 1440 return lz4ds; 1441 } 1442 1443 char* LZ4_slideInputBuffer (void* LZ4_Data) 1444 { 1445 LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)LZ4_Data)->internal_donotuse; 1446 int dictSize = LZ4_saveDict((LZ4_stream_t*)LZ4_Data, (char*)ctx->bufferStart, 64 KB); 1447 return (char*)(ctx->bufferStart + dictSize); 1448 } 1449 1450 /* Obsolete streaming decompression functions */ 1451 1452 int LZ4_decompress_safe_withPrefix64k(const char* source, char* dest, int compressedSize, int maxOutputSize) 1453 { 1454 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, withPrefix64k, (BYTE*)dest - 64 KB, NULL, 64 KB); 1455 } 1456 1457 int LZ4_decompress_fast_withPrefix64k(const char* source, char* dest, int originalSize) 1458 { 1459 return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, (BYTE*)dest - 64 KB, NULL, 64 KB); 1460 } 1461 1462 #endif /* LZ4_COMMONDEFS_ONLY */