1 /* 2 LZ4 - Fast LZ compression algorithm 3 Copyright (C) 2011-present, 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 * LZ4_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 LZ4_HEAPMODE 45 # define LZ4_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 assembly generation depends 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 */ 72 # if defined(__GNUC__) && \ 73 ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) \ 74 || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) ) 75 # define LZ4_FORCE_MEMORY_ACCESS 2 76 # elif (defined(__INTEL_COMPILER) && !defined(_WIN32)) || defined(__GNUC__) 77 # define LZ4_FORCE_MEMORY_ACCESS 1 78 # endif 79 #endif 80 81 /* 82 * LZ4_FORCE_SW_BITCOUNT 83 * Define this parameter if your target system or compiler does not support hardware bit count 84 */ 85 #if defined(_MSC_VER) && defined(_WIN32_WCE) /* Visual Studio for WinCE doesn't support Hardware bit count */ 86 # define LZ4_FORCE_SW_BITCOUNT 87 #endif 88 89 90 91 /*-************************************ 92 * Dependency 93 **************************************/ 94 #define LZ4_STATIC_LINKING_ONLY 95 #define LZ4_DISABLE_DEPRECATE_WARNINGS /* due to LZ4_decompress_safe_withPrefix64k */ 96 #include "lz4.h" 97 /* see also "memory routines" below */ 98 99 100 /*-************************************ 101 * Compiler Options 102 **************************************/ 103 #ifdef _MSC_VER /* Visual Studio */ 104 # include <intrin.h> 105 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 106 # pragma warning(disable : 4293) /* disable: C4293: too large shift (32-bits) */ 107 #endif /* _MSC_VER */ 108 109 #ifndef LZ4_FORCE_INLINE 110 # ifdef _MSC_VER /* Visual Studio */ 111 # define LZ4_FORCE_INLINE static __forceinline 112 # else 113 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 114 # ifdef __GNUC__ 115 # define LZ4_FORCE_INLINE static inline __attribute__((always_inline)) 116 # else 117 # define LZ4_FORCE_INLINE static inline 118 # endif 119 # else 120 # define LZ4_FORCE_INLINE static 121 # endif /* __STDC_VERSION__ */ 122 # endif /* _MSC_VER */ 123 #endif /* LZ4_FORCE_INLINE */ 124 125 /* LZ4_FORCE_O2_GCC_PPC64LE and LZ4_FORCE_O2_INLINE_GCC_PPC64LE 126 * Gcc on ppc64le generates an unrolled SIMDized loop for LZ4_wildCopy, 127 * together with a simple 8-byte copy loop as a fall-back path. 128 * However, this optimization hurts the decompression speed by >30%, 129 * because the execution does not go to the optimized loop 130 * for typical compressible data, and all of the preamble checks 131 * before going to the fall-back path become useless overhead. 132 * This optimization happens only with the -O3 flag, and -O2 generates 133 * a simple 8-byte copy loop. 134 * With gcc on ppc64le, all of the LZ4_decompress_* and LZ4_wildCopy 135 * functions are annotated with __attribute__((optimize("O2"))), 136 * and also LZ4_wildCopy is forcibly inlined, so that the O2 attribute 137 * of LZ4_wildCopy does not affect the compression speed. 138 */ 139 #if defined(__PPC64__) && defined(__LITTLE_ENDIAN__) && defined(__GNUC__) 140 # define LZ4_FORCE_O2_GCC_PPC64LE __attribute__((optimize("O2"))) 141 # define LZ4_FORCE_O2_INLINE_GCC_PPC64LE __attribute__((optimize("O2"))) LZ4_FORCE_INLINE 142 #else 143 # define LZ4_FORCE_O2_GCC_PPC64LE 144 # define LZ4_FORCE_O2_INLINE_GCC_PPC64LE static 145 #endif 146 147 #if (defined(__GNUC__) && (__GNUC__ >= 3)) || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 800)) || defined(__clang__) 148 # define expect(expr,value) (__builtin_expect ((expr),(value)) ) 149 #else 150 # define expect(expr,value) (expr) 151 #endif 152 153 #ifndef likely 154 #define likely(expr) expect((expr) != 0, 1) 155 #endif 156 #ifndef unlikely 157 #define unlikely(expr) expect((expr) != 0, 0) 158 #endif 159 160 161 /*-************************************ 162 * Memory routines 163 **************************************/ 164 #include <stdlib.h> /* malloc, calloc, free */ 165 #define ALLOC(s) malloc(s) 166 #define ALLOC_AND_ZERO(s) calloc(1,s) 167 #define FREEMEM(p) free(p) 168 #include <string.h> /* memset, memcpy */ 169 #define MEM_INIT(p,v,s) memset((p),(v),(s)) 170 171 172 /*-************************************ 173 * Basic Types 174 **************************************/ 175 #if defined(__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 176 # include <stdint.h> 177 typedef uint8_t BYTE; 178 typedef uint16_t U16; 179 typedef uint32_t U32; 180 typedef int32_t S32; 181 typedef uint64_t U64; 182 typedef uintptr_t uptrval; 183 #else 184 typedef unsigned char BYTE; 185 typedef unsigned short U16; 186 typedef unsigned int U32; 187 typedef signed int S32; 188 typedef unsigned long long U64; 189 typedef size_t uptrval; /* generally true, except OpenVMS-64 */ 190 #endif 191 192 #if defined(__x86_64__) 193 typedef U64 reg_t; /* 64-bits in x32 mode */ 194 #else 195 typedef size_t reg_t; /* 32-bits in x32 mode */ 196 #endif 197 198 /*-************************************ 199 * Reading and writing into memory 200 **************************************/ 201 static unsigned LZ4_isLittleEndian(void) 202 { 203 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ 204 return one.c[0]; 205 } 206 207 208 #if defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==2) 209 /* lie to the compiler about data alignment; use with caution */ 210 211 static U16 LZ4_read16(const void* memPtr) { return *(const U16*) memPtr; } 212 static U32 LZ4_read32(const void* memPtr) { return *(const U32*) memPtr; } 213 static reg_t LZ4_read_ARCH(const void* memPtr) { return *(const reg_t*) memPtr; } 214 215 static void LZ4_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; } 216 static void LZ4_write32(void* memPtr, U32 value) { *(U32*)memPtr = value; } 217 218 #elif defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==1) 219 220 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ 221 /* currently only defined for gcc and icc */ 222 typedef union { U16 u16; U32 u32; reg_t uArch; } __attribute__((packed)) unalign; 223 224 static U16 LZ4_read16(const void* ptr) { return ((const unalign*)ptr)->u16; } 225 static U32 LZ4_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } 226 static reg_t LZ4_read_ARCH(const void* ptr) { return ((const unalign*)ptr)->uArch; } 227 228 static void LZ4_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; } 229 static void LZ4_write32(void* memPtr, U32 value) { ((unalign*)memPtr)->u32 = value; } 230 231 #else /* safe and portable access through memcpy() */ 232 233 static U16 LZ4_read16(const void* memPtr) 234 { 235 U16 val; memcpy(&val, memPtr, sizeof(val)); return val; 236 } 237 238 static U32 LZ4_read32(const void* memPtr) 239 { 240 U32 val; memcpy(&val, memPtr, sizeof(val)); return val; 241 } 242 243 static reg_t LZ4_read_ARCH(const void* memPtr) 244 { 245 reg_t val; memcpy(&val, memPtr, sizeof(val)); return val; 246 } 247 248 static void LZ4_write16(void* memPtr, U16 value) 249 { 250 memcpy(memPtr, &value, sizeof(value)); 251 } 252 253 static void LZ4_write32(void* memPtr, U32 value) 254 { 255 memcpy(memPtr, &value, sizeof(value)); 256 } 257 258 #endif /* LZ4_FORCE_MEMORY_ACCESS */ 259 260 261 static U16 LZ4_readLE16(const void* memPtr) 262 { 263 if (LZ4_isLittleEndian()) { 264 return LZ4_read16(memPtr); 265 } else { 266 const BYTE* p = (const BYTE*)memPtr; 267 return (U16)((U16)p[0] + (p[1]<<8)); 268 } 269 } 270 271 static void LZ4_writeLE16(void* memPtr, U16 value) 272 { 273 if (LZ4_isLittleEndian()) { 274 LZ4_write16(memPtr, value); 275 } else { 276 BYTE* p = (BYTE*)memPtr; 277 p[0] = (BYTE) value; 278 p[1] = (BYTE)(value>>8); 279 } 280 } 281 282 /* customized variant of memcpy, which can overwrite up to 8 bytes beyond dstEnd */ 283 LZ4_FORCE_O2_INLINE_GCC_PPC64LE 284 void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd) 285 { 286 BYTE* d = (BYTE*)dstPtr; 287 const BYTE* s = (const BYTE*)srcPtr; 288 BYTE* const e = (BYTE*)dstEnd; 289 290 do { memcpy(d,s,8); d+=8; s+=8; } while (d<e); 291 } 292 293 294 /*-************************************ 295 * Common Constants 296 **************************************/ 297 #define MINMATCH 4 298 299 #define WILDCOPYLENGTH 8 300 #define LASTLITERALS 5 /* see ../doc/lz4_Block_format.md#parsing-restrictions */ 301 #define MFLIMIT 12 /* see ../doc/lz4_Block_format.md#parsing-restrictions */ 302 #define MATCH_SAFEGUARD_DISTANCE ((2*WILDCOPYLENGTH) - MINMATCH) /* ensure it's possible to write 2 x wildcopyLength without overflowing output buffer */ 303 static const int LZ4_minLength = (MFLIMIT+1); 304 305 #define KB *(1 <<10) 306 #define MB *(1 <<20) 307 #define GB *(1U<<30) 308 309 #define MAXD_LOG 16 310 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1) 311 312 #define ML_BITS 4 313 #define ML_MASK ((1U<<ML_BITS)-1) 314 #define RUN_BITS (8-ML_BITS) 315 #define RUN_MASK ((1U<<RUN_BITS)-1) 316 317 318 /*-************************************ 319 * Error detection 320 **************************************/ 321 #if defined(LZ4_DEBUG) && (LZ4_DEBUG>=1) 322 # include <assert.h> 323 #else 324 # ifndef assert 325 # define assert(condition) ((void)0) 326 # endif 327 #endif 328 329 #define LZ4_STATIC_ASSERT(c) { enum { LZ4_static_assert = 1/(int)(!!(c)) }; } /* use after variable declarations */ 330 331 #if defined(LZ4_DEBUG) && (LZ4_DEBUG>=2) 332 # include <stdio.h> 333 static int g_debuglog_enable = 1; 334 # define DEBUGLOG(l, ...) { \ 335 if ((g_debuglog_enable) && (l<=LZ4_DEBUG)) { \ 336 fprintf(stderr, __FILE__ ": "); \ 337 fprintf(stderr, __VA_ARGS__); \ 338 fprintf(stderr, " \n"); \ 339 } } 340 #else 341 # define DEBUGLOG(l, ...) {} /* disabled */ 342 #endif 343 344 345 /*-************************************ 346 * Common functions 347 **************************************/ 348 static unsigned LZ4_NbCommonBytes (reg_t val) 349 { 350 if (LZ4_isLittleEndian()) { 351 if (sizeof(val)==8) { 352 # if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT) 353 unsigned long r = 0; 354 _BitScanForward64( &r, (U64)val ); 355 return (int)(r>>3); 356 # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT) 357 return (__builtin_ctzll((U64)val) >> 3); 358 # else 359 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 360 0, 3, 1, 3, 1, 4, 2, 7, 361 0, 2, 3, 6, 1, 5, 3, 5, 362 1, 3, 4, 4, 2, 5, 6, 7, 363 7, 0, 1, 2, 3, 3, 4, 6, 364 2, 6, 5, 5, 3, 4, 5, 6, 365 7, 1, 2, 4, 6, 4, 4, 5, 366 7, 2, 6, 5, 7, 6, 7, 7 }; 367 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58]; 368 # endif 369 } else /* 32 bits */ { 370 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) 371 unsigned long r; 372 _BitScanForward( &r, (U32)val ); 373 return (int)(r>>3); 374 # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT) 375 return (__builtin_ctz((U32)val) >> 3); 376 # else 377 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 378 3, 2, 2, 1, 3, 2, 0, 1, 379 3, 3, 1, 2, 2, 2, 2, 0, 380 3, 1, 2, 0, 1, 0, 1, 1 }; 381 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27]; 382 # endif 383 } 384 } else /* Big Endian CPU */ { 385 if (sizeof(val)==8) { /* 64-bits */ 386 # if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT) 387 unsigned long r = 0; 388 _BitScanReverse64( &r, val ); 389 return (unsigned)(r>>3); 390 # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT) 391 return (__builtin_clzll((U64)val) >> 3); 392 # else 393 static const U32 by32 = sizeof(val)*4; /* 32 on 64 bits (goal), 16 on 32 bits. 394 Just to avoid some static analyzer complaining about shift by 32 on 32-bits target. 395 Note that this code path is never triggered in 32-bits mode. */ 396 unsigned r; 397 if (!(val>>by32)) { r=4; } else { r=0; val>>=by32; } 398 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } 399 r += (!val); 400 return r; 401 # endif 402 } else /* 32 bits */ { 403 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) 404 unsigned long r = 0; 405 _BitScanReverse( &r, (unsigned long)val ); 406 return (unsigned)(r>>3); 407 # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT) 408 return (__builtin_clz((U32)val) >> 3); 409 # else 410 unsigned r; 411 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; } 412 r += (!val); 413 return r; 414 # endif 415 } 416 } 417 } 418 419 #define STEPSIZE sizeof(reg_t) 420 LZ4_FORCE_INLINE 421 unsigned LZ4_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* pInLimit) 422 { 423 const BYTE* const pStart = pIn; 424 425 if (likely(pIn < pInLimit-(STEPSIZE-1))) { 426 reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn); 427 if (!diff) { 428 pIn+=STEPSIZE; pMatch+=STEPSIZE; 429 } else { 430 return LZ4_NbCommonBytes(diff); 431 } } 432 433 while (likely(pIn < pInLimit-(STEPSIZE-1))) { 434 reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn); 435 if (!diff) { pIn+=STEPSIZE; pMatch+=STEPSIZE; continue; } 436 pIn += LZ4_NbCommonBytes(diff); 437 return (unsigned)(pIn - pStart); 438 } 439 440 if ((STEPSIZE==8) && (pIn<(pInLimit-3)) && (LZ4_read32(pMatch) == LZ4_read32(pIn))) { pIn+=4; pMatch+=4; } 441 if ((pIn<(pInLimit-1)) && (LZ4_read16(pMatch) == LZ4_read16(pIn))) { pIn+=2; pMatch+=2; } 442 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++; 443 return (unsigned)(pIn - pStart); 444 } 445 446 447 #ifndef LZ4_COMMONDEFS_ONLY 448 /*-************************************ 449 * Local Constants 450 **************************************/ 451 static const int LZ4_64Klimit = ((64 KB) + (MFLIMIT-1)); 452 static const U32 LZ4_skipTrigger = 6; /* Increase this value ==> compression run slower on incompressible data */ 453 454 455 /*-************************************ 456 * Local Structures and types 457 **************************************/ 458 typedef enum { notLimited = 0, limitedOutput = 1, fillOutput = 2 } limitedOutput_directive; 459 typedef enum { clearedTable = 0, byPtr, byU32, byU16 } tableType_t; 460 461 /** 462 * This enum distinguishes several different modes of accessing previous 463 * content in the stream. 464 * 465 * - noDict : There is no preceding content. 466 * - withPrefix64k : Table entries up to ctx->dictSize before the current blob 467 * blob being compressed are valid and refer to the preceding 468 * content (of length ctx->dictSize), which is available 469 * contiguously preceding in memory the content currently 470 * being compressed. 471 * - usingExtDict : Like withPrefix64k, but the preceding content is somewhere 472 * else in memory, starting at ctx->dictionary with length 473 * ctx->dictSize. 474 * - usingDictCtx : Like usingExtDict, but everything concerning the preceding 475 * content is in a separate context, pointed to by 476 * ctx->dictCtx. ctx->dictionary, ctx->dictSize, and table 477 * entries in the current context that refer to positions 478 * preceding the beginning of the current compression are 479 * ignored. Instead, ctx->dictCtx->dictionary and ctx->dictCtx 480 * ->dictSize describe the location and size of the preceding 481 * content, and matches are found by looking in the ctx 482 * ->dictCtx->hashTable. 483 */ 484 typedef enum { noDict = 0, withPrefix64k, usingExtDict, usingDictCtx } dict_directive; 485 typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive; 486 487 488 /*-************************************ 489 * Local Utils 490 **************************************/ 491 int LZ4_versionNumber (void) { return LZ4_VERSION_NUMBER; } 492 const char* LZ4_versionString(void) { return LZ4_VERSION_STRING; } 493 int LZ4_compressBound(int isize) { return LZ4_COMPRESSBOUND(isize); } 494 int LZ4_sizeofState() { return LZ4_STREAMSIZE; } 495 496 497 /*-************************************ 498 * Internal Definitions used in Tests 499 **************************************/ 500 #if defined (__cplusplus) 501 extern "C" { 502 #endif 503 504 int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize); 505 506 int LZ4_decompress_safe_forceExtDict(const char* in, char* out, int inSize, int outSize, const void* dict, size_t dictSize); 507 508 #if defined (__cplusplus) 509 } 510 #endif 511 512 /*-****************************** 513 * Compression functions 514 ********************************/ 515 static U32 LZ4_hash4(U32 sequence, tableType_t const tableType) 516 { 517 if (tableType == byU16) 518 return ((sequence * 2654435761U) >> ((MINMATCH*8)-(LZ4_HASHLOG+1))); 519 else 520 return ((sequence * 2654435761U) >> ((MINMATCH*8)-LZ4_HASHLOG)); 521 } 522 523 static U32 LZ4_hash5(U64 sequence, tableType_t const tableType) 524 { 525 static const U64 prime5bytes = 889523592379ULL; 526 static const U64 prime8bytes = 11400714785074694791ULL; 527 const U32 hashLog = (tableType == byU16) ? LZ4_HASHLOG+1 : LZ4_HASHLOG; 528 if (LZ4_isLittleEndian()) 529 return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog)); 530 else 531 return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog)); 532 } 533 534 LZ4_FORCE_INLINE U32 LZ4_hashPosition(const void* const p, tableType_t const tableType) 535 { 536 if ((sizeof(reg_t)==8) && (tableType != byU16)) return LZ4_hash5(LZ4_read_ARCH(p), tableType); 537 return LZ4_hash4(LZ4_read32(p), tableType); 538 } 539 540 static void LZ4_putIndexOnHash(U32 idx, U32 h, void* tableBase, tableType_t const tableType) 541 { 542 switch (tableType) 543 { 544 default: /* fallthrough */ 545 case clearedTable: /* fallthrough */ 546 case byPtr: { /* illegal! */ assert(0); return; } 547 case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = idx; return; } 548 case byU16: { U16* hashTable = (U16*) tableBase; assert(idx < 65536); hashTable[h] = (U16)idx; return; } 549 } 550 } 551 552 static void LZ4_putPositionOnHash(const BYTE* p, U32 h, 553 void* tableBase, tableType_t const tableType, 554 const BYTE* srcBase) 555 { 556 switch (tableType) 557 { 558 case clearedTable: { /* illegal! */ assert(0); return; } 559 case byPtr: { const BYTE** hashTable = (const BYTE**)tableBase; hashTable[h] = p; return; } 560 case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = (U32)(p-srcBase); return; } 561 case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = (U16)(p-srcBase); return; } 562 } 563 } 564 565 LZ4_FORCE_INLINE void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase) 566 { 567 U32 const h = LZ4_hashPosition(p, tableType); 568 LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase); 569 } 570 571 /* LZ4_getIndexOnHash() : 572 * Index of match position registered in hash table. 573 * hash position must be calculated by using base+index, or dictBase+index. 574 * Assumption 1 : only valid if tableType == byU32 or byU16. 575 * Assumption 2 : h is presumed valid (within limits of hash table) 576 */ 577 static U32 LZ4_getIndexOnHash(U32 h, const void* tableBase, tableType_t tableType) 578 { 579 LZ4_STATIC_ASSERT(LZ4_MEMORY_USAGE > 2); 580 if (tableType == byU32) { 581 const U32* const hashTable = (const U32*) tableBase; 582 assert(h < (1U << (LZ4_MEMORY_USAGE-2))); 583 return hashTable[h]; 584 } 585 if (tableType == byU16) { 586 const U16* const hashTable = (const U16*) tableBase; 587 assert(h < (1U << (LZ4_MEMORY_USAGE-1))); 588 return hashTable[h]; 589 } 590 assert(0); return 0; /* forbidden case */ 591 } 592 593 static const BYTE* LZ4_getPositionOnHash(U32 h, const void* tableBase, tableType_t tableType, const BYTE* srcBase) 594 { 595 if (tableType == byPtr) { const BYTE* const* hashTable = (const BYTE* const*) tableBase; return hashTable[h]; } 596 if (tableType == byU32) { const U32* const hashTable = (const U32*) tableBase; return hashTable[h] + srcBase; } 597 { const U16* const hashTable = (const U16*) tableBase; return hashTable[h] + srcBase; } /* default, to ensure a return */ 598 } 599 600 LZ4_FORCE_INLINE const BYTE* LZ4_getPosition(const BYTE* p, 601 const void* tableBase, tableType_t tableType, 602 const BYTE* srcBase) 603 { 604 U32 const h = LZ4_hashPosition(p, tableType); 605 return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase); 606 } 607 608 LZ4_FORCE_INLINE void LZ4_prepareTable( 609 LZ4_stream_t_internal* const cctx, 610 const int inputSize, 611 const tableType_t tableType) { 612 /* If the table hasn't been used, it's guaranteed to be zeroed out, and is 613 * therefore safe to use no matter what mode we're in. Otherwise, we figure 614 * out if it's safe to leave as is or whether it needs to be reset. 615 */ 616 if (cctx->tableType != clearedTable) { 617 if (cctx->tableType != tableType 618 || (tableType == byU16 && cctx->currentOffset + inputSize >= 0xFFFFU) 619 || (tableType == byU32 && cctx->currentOffset > 1 GB) 620 || tableType == byPtr 621 || inputSize >= 4 KB) 622 { 623 DEBUGLOG(4, "LZ4_prepareTable: Resetting table in %p", cctx); 624 MEM_INIT(cctx->hashTable, 0, LZ4_HASHTABLESIZE); 625 cctx->currentOffset = 0; 626 cctx->tableType = clearedTable; 627 } else { 628 DEBUGLOG(4, "LZ4_prepareTable: Re-use hash table (no reset)"); 629 } 630 } 631 632 /* Adding a gap, so all previous entries are > MAX_DISTANCE back, is faster 633 * than compressing without a gap. However, compressing with 634 * currentOffset == 0 is faster still, so we preserve that case. 635 */ 636 if (cctx->currentOffset != 0 && tableType == byU32) { 637 DEBUGLOG(5, "LZ4_prepareTable: adding 64KB to currentOffset"); 638 cctx->currentOffset += 64 KB; 639 } 640 641 /* Finally, clear history */ 642 cctx->dictCtx = NULL; 643 cctx->dictionary = NULL; 644 cctx->dictSize = 0; 645 } 646 647 /** LZ4_compress_generic() : 648 inlined, to ensure branches are decided at compilation time */ 649 LZ4_FORCE_INLINE int LZ4_compress_generic( 650 LZ4_stream_t_internal* const cctx, 651 const char* const source, 652 char* const dest, 653 const int inputSize, 654 int *inputConsumed, /* only written when outputLimited == fillOutput */ 655 const int maxOutputSize, 656 const limitedOutput_directive outputLimited, 657 const tableType_t tableType, 658 const dict_directive dictDirective, 659 const dictIssue_directive dictIssue, 660 const U32 acceleration) 661 { 662 const BYTE* ip = (const BYTE*) source; 663 664 U32 const startIndex = cctx->currentOffset; 665 const BYTE* base = (const BYTE*) source - startIndex; 666 const BYTE* lowLimit; 667 668 const LZ4_stream_t_internal* dictCtx = (const LZ4_stream_t_internal*) cctx->dictCtx; 669 const BYTE* const dictionary = 670 dictDirective == usingDictCtx ? dictCtx->dictionary : cctx->dictionary; 671 const U32 dictSize = 672 dictDirective == usingDictCtx ? dictCtx->dictSize : cctx->dictSize; 673 const U32 dictDelta = (dictDirective == usingDictCtx) ? startIndex - dictCtx->currentOffset : 0; /* make indexes in dictCtx comparable with index in current context */ 674 675 int const maybe_extMem = (dictDirective == usingExtDict) || (dictDirective == usingDictCtx); 676 U32 const prefixIdxLimit = startIndex - dictSize; /* used when dictDirective == dictSmall */ 677 const BYTE* const dictEnd = dictionary + dictSize; 678 const BYTE* anchor = (const BYTE*) source; 679 const BYTE* const iend = ip + inputSize; 680 const BYTE* const mflimitPlusOne = iend - MFLIMIT + 1; 681 const BYTE* const matchlimit = iend - LASTLITERALS; 682 683 /* the dictCtx currentOffset is indexed on the start of the dictionary, 684 * while a dictionary in the current context precedes the currentOffset */ 685 const BYTE* dictBase = (dictDirective == usingDictCtx) ? 686 dictionary + dictSize - dictCtx->currentOffset : 687 dictionary + dictSize - startIndex; 688 689 BYTE* op = (BYTE*) dest; 690 BYTE* const olimit = op + maxOutputSize; 691 692 U32 offset = 0; 693 U32 forwardH; 694 695 DEBUGLOG(5, "LZ4_compress_generic: srcSize=%i, tableType=%u", inputSize, tableType); 696 /* Init conditions */ 697 if (outputLimited == fillOutput && maxOutputSize < 1) return 0; /* Impossible to store anything */ 698 if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported inputSize, too large (or negative) */ 699 if ((tableType == byU16) && (inputSize>=LZ4_64Klimit)) return 0; /* Size too large (not within 64K limit) */ 700 if (tableType==byPtr) assert(dictDirective==noDict); /* only supported use case with byPtr */ 701 assert(acceleration >= 1); 702 703 lowLimit = (const BYTE*)source - (dictDirective == withPrefix64k ? dictSize : 0); 704 705 /* Update context state */ 706 if (dictDirective == usingDictCtx) { 707 /* Subsequent linked blocks can't use the dictionary. */ 708 /* Instead, they use the block we just compressed. */ 709 cctx->dictCtx = NULL; 710 cctx->dictSize = (U32)inputSize; 711 } else { 712 cctx->dictSize += (U32)inputSize; 713 } 714 cctx->currentOffset += (U32)inputSize; 715 cctx->tableType = (U16)tableType; 716 717 if (inputSize<LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */ 718 719 /* First Byte */ 720 LZ4_putPosition(ip, cctx->hashTable, tableType, base); 721 ip++; forwardH = LZ4_hashPosition(ip, tableType); 722 723 /* Main Loop */ 724 for ( ; ; ) { 725 const BYTE* match; 726 BYTE* token; 727 728 /* Find a match */ 729 if (tableType == byPtr) { 730 const BYTE* forwardIp = ip; 731 unsigned step = 1; 732 unsigned searchMatchNb = acceleration << LZ4_skipTrigger; 733 do { 734 U32 const h = forwardH; 735 ip = forwardIp; 736 forwardIp += step; 737 step = (searchMatchNb++ >> LZ4_skipTrigger); 738 739 if (unlikely(forwardIp > mflimitPlusOne)) goto _last_literals; 740 assert(ip < mflimitPlusOne); 741 742 match = LZ4_getPositionOnHash(h, cctx->hashTable, tableType, base); 743 forwardH = LZ4_hashPosition(forwardIp, tableType); 744 LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType, base); 745 746 } while ( (match+MAX_DISTANCE < ip) 747 || (LZ4_read32(match) != LZ4_read32(ip)) ); 748 749 } else { /* byU32, byU16 */ 750 751 const BYTE* forwardIp = ip; 752 unsigned step = 1; 753 unsigned searchMatchNb = acceleration << LZ4_skipTrigger; 754 do { 755 U32 const h = forwardH; 756 U32 const current = (U32)(forwardIp - base); 757 U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType); 758 assert(matchIndex <= current); 759 assert(forwardIp - base < (ptrdiff_t)(2 GB - 1)); 760 ip = forwardIp; 761 forwardIp += step; 762 step = (searchMatchNb++ >> LZ4_skipTrigger); 763 764 if (unlikely(forwardIp > mflimitPlusOne)) goto _last_literals; 765 assert(ip < mflimitPlusOne); 766 767 if (dictDirective == usingDictCtx) { 768 if (matchIndex < startIndex) { 769 /* there was no match, try the dictionary */ 770 assert(tableType == byU32); 771 matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32); 772 match = dictBase + matchIndex; 773 matchIndex += dictDelta; /* make dictCtx index comparable with current context */ 774 lowLimit = dictionary; 775 } else { 776 match = base + matchIndex; 777 lowLimit = (const BYTE*)source; 778 } 779 } else if (dictDirective==usingExtDict) { 780 if (matchIndex < startIndex) { 781 DEBUGLOG(7, "extDict candidate: matchIndex=%5u < startIndex=%5u", matchIndex, startIndex); 782 assert(startIndex - matchIndex >= MINMATCH); 783 match = dictBase + matchIndex; 784 lowLimit = dictionary; 785 } else { 786 match = base + matchIndex; 787 lowLimit = (const BYTE*)source; 788 } 789 } else { /* single continuous memory segment */ 790 match = base + matchIndex; 791 } 792 forwardH = LZ4_hashPosition(forwardIp, tableType); 793 LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType); 794 795 if ((dictIssue == dictSmall) && (matchIndex < prefixIdxLimit)) continue; /* match outside of valid area */ 796 assert(matchIndex < current); 797 if ((tableType != byU16) && (matchIndex+MAX_DISTANCE < current)) continue; /* too far */ 798 if (tableType == byU16) assert((current - matchIndex) <= MAX_DISTANCE); /* too_far presumed impossible with byU16 */ 799 800 if (LZ4_read32(match) == LZ4_read32(ip)) { 801 if (maybe_extMem) offset = current - matchIndex; 802 break; /* match found */ 803 } 804 805 } while(1); 806 } 807 808 /* Catch up */ 809 while (((ip>anchor) & (match > lowLimit)) && (unlikely(ip[-1]==match[-1]))) { ip--; match--; } 810 811 /* Encode Literals */ 812 { unsigned const litLength = (unsigned)(ip - anchor); 813 token = op++; 814 if ((outputLimited == limitedOutput) && /* Check output buffer overflow */ 815 (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > olimit))) 816 return 0; 817 if ((outputLimited == fillOutput) && 818 (unlikely(op + (litLength+240)/255 /* litlen */ + litLength /* literals */ + 2 /* offset */ + 1 /* token */ + MFLIMIT - MINMATCH /* min last literals so last match is <= end - MFLIMIT */ > olimit))) { 819 op--; 820 goto _last_literals; 821 } 822 if (litLength >= RUN_MASK) { 823 int len = (int)litLength-RUN_MASK; 824 *token = (RUN_MASK<<ML_BITS); 825 for(; len >= 255 ; len-=255) *op++ = 255; 826 *op++ = (BYTE)len; 827 } 828 else *token = (BYTE)(litLength<<ML_BITS); 829 830 /* Copy Literals */ 831 LZ4_wildCopy(op, anchor, op+litLength); 832 op+=litLength; 833 DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i", 834 (int)(anchor-(const BYTE*)source), litLength, (int)(ip-(const BYTE*)source)); 835 } 836 837 _next_match: 838 /* at this stage, the following variables must be correctly set : 839 * - ip : at start of LZ operation 840 * - match : at start of previous pattern occurence; can be within current prefix, or within extDict 841 * - offset : if maybe_ext_memSegment==1 (constant) 842 * - lowLimit : must be == dictionary to mean "match is within extDict"; must be == source otherwise 843 * - token and *token : position to write 4-bits for match length; higher 4-bits for literal length supposed already written 844 */ 845 846 if ((outputLimited == fillOutput) && 847 (op + 2 /* offset */ + 1 /* token */ + MFLIMIT - MINMATCH /* min last literals so last match is <= end - MFLIMIT */ > olimit)) { 848 /* the match was too close to the end, rewind and go to last literals */ 849 op = token; 850 goto _last_literals; 851 } 852 853 /* Encode Offset */ 854 if (maybe_extMem) { /* static test */ 855 DEBUGLOG(6, " with offset=%u (ext if > %i)", offset, (int)(ip - (const BYTE*)source)); 856 assert(offset <= MAX_DISTANCE && offset > 0); 857 LZ4_writeLE16(op, (U16)offset); op+=2; 858 } else { 859 DEBUGLOG(6, " with offset=%u (same segment)", (U32)(ip - match)); 860 assert(ip-match <= MAX_DISTANCE); 861 LZ4_writeLE16(op, (U16)(ip - match)); op+=2; 862 } 863 864 /* Encode MatchLength */ 865 { unsigned matchCode; 866 867 if ( (dictDirective==usingExtDict || dictDirective==usingDictCtx) 868 && (lowLimit==dictionary) /* match within extDict */ ) { 869 const BYTE* limit = ip + (dictEnd-match); 870 assert(dictEnd > match); 871 if (limit > matchlimit) limit = matchlimit; 872 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, limit); 873 ip += MINMATCH + matchCode; 874 if (ip==limit) { 875 unsigned const more = LZ4_count(limit, (const BYTE*)source, matchlimit); 876 matchCode += more; 877 ip += more; 878 } 879 DEBUGLOG(6, " with matchLength=%u starting in extDict", matchCode+MINMATCH); 880 } else { 881 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit); 882 ip += MINMATCH + matchCode; 883 DEBUGLOG(6, " with matchLength=%u", matchCode+MINMATCH); 884 } 885 886 if ((outputLimited) && /* Check output buffer overflow */ 887 (unlikely(op + (1 + LASTLITERALS) + (matchCode>>8) > olimit)) ) { 888 if (outputLimited == limitedOutput) 889 return 0; 890 if (outputLimited == fillOutput) { 891 /* Match description too long : reduce it */ 892 U32 newMatchCode = 15 /* in token */ - 1 /* to avoid needing a zero byte */ + ((U32)(olimit - op) - 2 - 1 - LASTLITERALS) * 255; 893 ip -= matchCode - newMatchCode; 894 matchCode = newMatchCode; 895 } 896 } 897 if (matchCode >= ML_MASK) { 898 *token += ML_MASK; 899 matchCode -= ML_MASK; 900 LZ4_write32(op, 0xFFFFFFFF); 901 while (matchCode >= 4*255) { 902 op+=4; 903 LZ4_write32(op, 0xFFFFFFFF); 904 matchCode -= 4*255; 905 } 906 op += matchCode / 255; 907 *op++ = (BYTE)(matchCode % 255); 908 } else 909 *token += (BYTE)(matchCode); 910 } 911 912 anchor = ip; 913 914 /* Test end of chunk */ 915 if (ip >= mflimitPlusOne) break; 916 917 /* Fill table */ 918 LZ4_putPosition(ip-2, cctx->hashTable, tableType, base); 919 920 /* Test next position */ 921 if (tableType == byPtr) { 922 923 match = LZ4_getPosition(ip, cctx->hashTable, tableType, base); 924 LZ4_putPosition(ip, cctx->hashTable, tableType, base); 925 if ( (match+MAX_DISTANCE >= ip) 926 && (LZ4_read32(match) == LZ4_read32(ip)) ) 927 { token=op++; *token=0; goto _next_match; } 928 929 } else { /* byU32, byU16 */ 930 931 U32 const h = LZ4_hashPosition(ip, tableType); 932 U32 const current = (U32)(ip-base); 933 U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType); 934 assert(matchIndex < current); 935 if (dictDirective == usingDictCtx) { 936 if (matchIndex < startIndex) { 937 /* there was no match, try the dictionary */ 938 matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32); 939 match = dictBase + matchIndex; 940 lowLimit = dictionary; /* required for match length counter */ 941 matchIndex += dictDelta; 942 } else { 943 match = base + matchIndex; 944 lowLimit = (const BYTE*)source; /* required for match length counter */ 945 } 946 } else if (dictDirective==usingExtDict) { 947 if (matchIndex < startIndex) { 948 match = dictBase + matchIndex; 949 lowLimit = dictionary; /* required for match length counter */ 950 } else { 951 match = base + matchIndex; 952 lowLimit = (const BYTE*)source; /* required for match length counter */ 953 } 954 } else { /* single memory segment */ 955 match = base + matchIndex; 956 } 957 LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType); 958 assert(matchIndex < current); 959 if ( ((dictIssue==dictSmall) ? (matchIndex >= prefixIdxLimit) : 1) 960 && ((tableType==byU16) ? 1 : (matchIndex+MAX_DISTANCE >= current)) 961 && (LZ4_read32(match) == LZ4_read32(ip)) ) { 962 token=op++; 963 *token=0; 964 if (maybe_extMem) offset = current - matchIndex; 965 DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i", 966 (int)(anchor-(const BYTE*)source), 0, (int)(ip-(const BYTE*)source)); 967 goto _next_match; 968 } 969 } 970 971 /* Prepare next loop */ 972 forwardH = LZ4_hashPosition(++ip, tableType); 973 974 } 975 976 _last_literals: 977 /* Encode Last Literals */ 978 { size_t lastRun = (size_t)(iend - anchor); 979 if ( (outputLimited) && /* Check output buffer overflow */ 980 (op + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > olimit)) { 981 if (outputLimited == fillOutput) { 982 /* adapt lastRun to fill 'dst' */ 983 lastRun = (olimit-op) - 1; 984 lastRun -= (lastRun+240)/255; 985 } 986 if (outputLimited == limitedOutput) 987 return 0; 988 } 989 if (lastRun >= RUN_MASK) { 990 size_t accumulator = lastRun - RUN_MASK; 991 *op++ = RUN_MASK << ML_BITS; 992 for(; accumulator >= 255 ; accumulator-=255) *op++ = 255; 993 *op++ = (BYTE) accumulator; 994 } else { 995 *op++ = (BYTE)(lastRun<<ML_BITS); 996 } 997 memcpy(op, anchor, lastRun); 998 ip = anchor + lastRun; 999 op += lastRun; 1000 } 1001 1002 if (outputLimited == fillOutput) { 1003 *inputConsumed = (int) (((const char*)ip)-source); 1004 } 1005 DEBUGLOG(5, "LZ4_compress_generic: compressed %i bytes into %i bytes", inputSize, (int)(((char*)op) - dest)); 1006 return (int)(((char*)op) - dest); 1007 } 1008 1009 1010 int LZ4_compress_fast_extState(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration) 1011 { 1012 LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)state)->internal_donotuse; 1013 if (acceleration < 1) acceleration = ACCELERATION_DEFAULT; 1014 LZ4_resetStream((LZ4_stream_t*)state); 1015 if (maxOutputSize >= LZ4_compressBound(inputSize)) { 1016 if (inputSize < LZ4_64Klimit) { 1017 return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, 0, notLimited, byU16, noDict, noDictIssue, acceleration); 1018 } else { 1019 const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)source > MAX_DISTANCE)) ? byPtr : byU32; 1020 return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, 0, notLimited, tableType, noDict, noDictIssue, acceleration); 1021 } 1022 } else { 1023 if (inputSize < LZ4_64Klimit) {; 1024 return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue, acceleration); 1025 } else { 1026 const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)source > MAX_DISTANCE)) ? byPtr : byU32; 1027 return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, noDict, noDictIssue, acceleration); 1028 } 1029 } 1030 } 1031 1032 /** 1033 * LZ4_compress_fast_extState_fastReset() : 1034 * A variant of LZ4_compress_fast_extState(). 1035 * 1036 * Using this variant avoids an expensive initialization step. It is only safe 1037 * to call if the state buffer is known to be correctly initialized already 1038 * (see comment in lz4.h on LZ4_resetStream_fast() for a definition of 1039 * "correctly initialized"). 1040 */ 1041 int LZ4_compress_fast_extState_fastReset(void* state, const char* src, char* dst, int srcSize, int dstCapacity, int acceleration) 1042 { 1043 LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)state)->internal_donotuse; 1044 if (acceleration < 1) acceleration = ACCELERATION_DEFAULT; 1045 1046 if (dstCapacity >= LZ4_compressBound(srcSize)) { 1047 if (srcSize < LZ4_64Klimit) { 1048 const tableType_t tableType = byU16; 1049 LZ4_prepareTable(ctx, srcSize, tableType); 1050 if (ctx->currentOffset) { 1051 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, 0, notLimited, tableType, noDict, dictSmall, acceleration); 1052 } else { 1053 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, 0, notLimited, tableType, noDict, noDictIssue, acceleration); 1054 } 1055 } else { 1056 const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)src > MAX_DISTANCE)) ? byPtr : byU32; 1057 LZ4_prepareTable(ctx, srcSize, tableType); 1058 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, 0, notLimited, tableType, noDict, noDictIssue, acceleration); 1059 } 1060 } else { 1061 if (srcSize < LZ4_64Klimit) { 1062 const tableType_t tableType = byU16; 1063 LZ4_prepareTable(ctx, srcSize, tableType); 1064 if (ctx->currentOffset) { 1065 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, dstCapacity, limitedOutput, tableType, noDict, dictSmall, acceleration); 1066 } else { 1067 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, dstCapacity, limitedOutput, tableType, noDict, noDictIssue, acceleration); 1068 } 1069 } else { 1070 const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)src > MAX_DISTANCE)) ? byPtr : byU32; 1071 LZ4_prepareTable(ctx, srcSize, tableType); 1072 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, dstCapacity, limitedOutput, tableType, noDict, noDictIssue, acceleration); 1073 } 1074 } 1075 } 1076 1077 1078 int LZ4_compress_fast(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration) 1079 { 1080 int result; 1081 #if (LZ4_HEAPMODE) 1082 LZ4_stream_t* ctxPtr = ALLOC(sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */ 1083 if (ctxPtr == NULL) return 0; 1084 #else 1085 LZ4_stream_t ctx; 1086 LZ4_stream_t* const ctxPtr = &ctx; 1087 #endif 1088 result = LZ4_compress_fast_extState(ctxPtr, source, dest, inputSize, maxOutputSize, acceleration); 1089 1090 #if (LZ4_HEAPMODE) 1091 FREEMEM(ctxPtr); 1092 #endif 1093 return result; 1094 } 1095 1096 1097 int LZ4_compress_default(const char* source, char* dest, int inputSize, int maxOutputSize) 1098 { 1099 return LZ4_compress_fast(source, dest, inputSize, maxOutputSize, 1); 1100 } 1101 1102 1103 /* hidden debug function */ 1104 /* strangely enough, gcc generates faster code when this function is uncommented, even if unused */ 1105 int LZ4_compress_fast_force(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration) 1106 { 1107 LZ4_stream_t ctx; 1108 LZ4_resetStream(&ctx); 1109 1110 if (inputSize < LZ4_64Klimit) 1111 return LZ4_compress_generic(&ctx.internal_donotuse, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue, acceleration); 1112 else 1113 return LZ4_compress_generic(&ctx.internal_donotuse, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, sizeof(void*)==8 ? byU32 : byPtr, noDict, noDictIssue, acceleration); 1114 } 1115 1116 1117 /* Note!: This function leaves the stream in an unclean/broken state! 1118 * It is not safe to subsequently use the same state with a _fastReset() or 1119 * _continue() call without resetting it. */ 1120 static int LZ4_compress_destSize_extState (LZ4_stream_t* state, const char* src, char* dst, int* srcSizePtr, int targetDstSize) 1121 { 1122 LZ4_resetStream(state); 1123 1124 if (targetDstSize >= LZ4_compressBound(*srcSizePtr)) { /* compression success is guaranteed */ 1125 return LZ4_compress_fast_extState(state, src, dst, *srcSizePtr, targetDstSize, 1); 1126 } else { 1127 if (*srcSizePtr < LZ4_64Klimit) { 1128 return LZ4_compress_generic(&state->internal_donotuse, src, dst, *srcSizePtr, srcSizePtr, targetDstSize, fillOutput, byU16, noDict, noDictIssue, 1); 1129 } else { 1130 tableType_t const tableType = ((sizeof(void*)==4) && ((uptrval)src > MAX_DISTANCE)) ? byPtr : byU32; 1131 return LZ4_compress_generic(&state->internal_donotuse, src, dst, *srcSizePtr, srcSizePtr, targetDstSize, fillOutput, tableType, noDict, noDictIssue, 1); 1132 } } 1133 } 1134 1135 1136 int LZ4_compress_destSize(const char* src, char* dst, int* srcSizePtr, int targetDstSize) 1137 { 1138 #if (LZ4_HEAPMODE) 1139 LZ4_stream_t* ctx = (LZ4_stream_t*)ALLOC(sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */ 1140 if (ctx == NULL) return 0; 1141 #else 1142 LZ4_stream_t ctxBody; 1143 LZ4_stream_t* ctx = &ctxBody; 1144 #endif 1145 1146 int result = LZ4_compress_destSize_extState(ctx, src, dst, srcSizePtr, targetDstSize); 1147 1148 #if (LZ4_HEAPMODE) 1149 FREEMEM(ctx); 1150 #endif 1151 return result; 1152 } 1153 1154 1155 1156 /*-****************************** 1157 * Streaming functions 1158 ********************************/ 1159 1160 LZ4_stream_t* LZ4_createStream(void) 1161 { 1162 LZ4_stream_t* lz4s = (LZ4_stream_t*)ALLOC(sizeof(LZ4_stream_t)); 1163 LZ4_STATIC_ASSERT(LZ4_STREAMSIZE >= sizeof(LZ4_stream_t_internal)); /* A compilation error here means LZ4_STREAMSIZE is not large enough */ 1164 DEBUGLOG(4, "LZ4_createStream %p", lz4s); 1165 if (lz4s == NULL) return NULL; 1166 LZ4_resetStream(lz4s); 1167 return lz4s; 1168 } 1169 1170 void LZ4_resetStream (LZ4_stream_t* LZ4_stream) 1171 { 1172 DEBUGLOG(5, "LZ4_resetStream (ctx:%p)", LZ4_stream); 1173 MEM_INIT(LZ4_stream, 0, sizeof(LZ4_stream_t)); 1174 } 1175 1176 void LZ4_resetStream_fast(LZ4_stream_t* ctx) { 1177 LZ4_prepareTable(&(ctx->internal_donotuse), 0, byU32); 1178 } 1179 1180 int LZ4_freeStream (LZ4_stream_t* LZ4_stream) 1181 { 1182 if (!LZ4_stream) return 0; /* support free on NULL */ 1183 DEBUGLOG(5, "LZ4_freeStream %p", LZ4_stream); 1184 FREEMEM(LZ4_stream); 1185 return (0); 1186 } 1187 1188 1189 #define HASH_UNIT sizeof(reg_t) 1190 int LZ4_loadDict (LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize) 1191 { 1192 LZ4_stream_t_internal* dict = &LZ4_dict->internal_donotuse; 1193 const tableType_t tableType = byU32; 1194 const BYTE* p = (const BYTE*)dictionary; 1195 const BYTE* const dictEnd = p + dictSize; 1196 const BYTE* base; 1197 1198 DEBUGLOG(4, "LZ4_loadDict (%i bytes from %p into %p)", dictSize, dictionary, LZ4_dict); 1199 1200 /* It's necessary to reset the context, 1201 * and not just continue it with prepareTable() 1202 * to avoid any risk of generating overflowing matchIndex 1203 * when compressing using this dictionary */ 1204 LZ4_resetStream(LZ4_dict); 1205 1206 /* We always increment the offset by 64 KB, since, if the dict is longer, 1207 * we truncate it to the last 64k, and if it's shorter, we still want to 1208 * advance by a whole window length so we can provide the guarantee that 1209 * there are only valid offsets in the window, which allows an optimization 1210 * in LZ4_compress_fast_continue() where it uses noDictIssue even when the 1211 * dictionary isn't a full 64k. */ 1212 1213 if ((dictEnd - p) > 64 KB) p = dictEnd - 64 KB; 1214 base = dictEnd - 64 KB - dict->currentOffset; 1215 dict->dictionary = p; 1216 dict->dictSize = (U32)(dictEnd - p); 1217 dict->currentOffset += 64 KB; 1218 dict->tableType = tableType; 1219 1220 if (dictSize < (int)HASH_UNIT) { 1221 return 0; 1222 } 1223 1224 while (p <= dictEnd-HASH_UNIT) { 1225 LZ4_putPosition(p, dict->hashTable, tableType, base); 1226 p+=3; 1227 } 1228 1229 return dict->dictSize; 1230 } 1231 1232 void LZ4_attach_dictionary(LZ4_stream_t *working_stream, const LZ4_stream_t *dictionary_stream) { 1233 if (dictionary_stream != NULL) { 1234 /* If the current offset is zero, we will never look in the 1235 * external dictionary context, since there is no value a table 1236 * entry can take that indicate a miss. In that case, we need 1237 * to bump the offset to something non-zero. 1238 */ 1239 if (working_stream->internal_donotuse.currentOffset == 0) { 1240 working_stream->internal_donotuse.currentOffset = 64 KB; 1241 } 1242 working_stream->internal_donotuse.dictCtx = &(dictionary_stream->internal_donotuse); 1243 } else { 1244 working_stream->internal_donotuse.dictCtx = NULL; 1245 } 1246 } 1247 1248 1249 static void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, int nextSize) 1250 { 1251 if (LZ4_dict->currentOffset + nextSize > 0x80000000) { /* potential ptrdiff_t overflow (32-bits mode) */ 1252 /* rescale hash table */ 1253 U32 const delta = LZ4_dict->currentOffset - 64 KB; 1254 const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize; 1255 int i; 1256 DEBUGLOG(4, "LZ4_renormDictT"); 1257 for (i=0; i<LZ4_HASH_SIZE_U32; i++) { 1258 if (LZ4_dict->hashTable[i] < delta) LZ4_dict->hashTable[i]=0; 1259 else LZ4_dict->hashTable[i] -= delta; 1260 } 1261 LZ4_dict->currentOffset = 64 KB; 1262 if (LZ4_dict->dictSize > 64 KB) LZ4_dict->dictSize = 64 KB; 1263 LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize; 1264 } 1265 } 1266 1267 1268 int LZ4_compress_fast_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration) 1269 { 1270 const tableType_t tableType = byU32; 1271 LZ4_stream_t_internal* streamPtr = &LZ4_stream->internal_donotuse; 1272 const BYTE* dictEnd = streamPtr->dictionary + streamPtr->dictSize; 1273 1274 DEBUGLOG(5, "LZ4_compress_fast_continue (inputSize=%i)", inputSize); 1275 1276 if (streamPtr->initCheck) return 0; /* Uninitialized structure detected */ 1277 LZ4_renormDictT(streamPtr, inputSize); /* avoid index overflow */ 1278 if (acceleration < 1) acceleration = ACCELERATION_DEFAULT; 1279 1280 /* invalidate tiny dictionaries */ 1281 if ( (streamPtr->dictSize-1 < 4) /* intentional underflow */ 1282 && (dictEnd != (const BYTE*)source) ) { 1283 DEBUGLOG(5, "LZ4_compress_fast_continue: dictSize(%u) at addr:%p is too small", streamPtr->dictSize, streamPtr->dictionary); 1284 streamPtr->dictSize = 0; 1285 streamPtr->dictionary = (const BYTE*)source; 1286 dictEnd = (const BYTE*)source; 1287 } 1288 1289 /* Check overlapping input/dictionary space */ 1290 { const BYTE* sourceEnd = (const BYTE*) source + inputSize; 1291 if ((sourceEnd > streamPtr->dictionary) && (sourceEnd < dictEnd)) { 1292 streamPtr->dictSize = (U32)(dictEnd - sourceEnd); 1293 if (streamPtr->dictSize > 64 KB) streamPtr->dictSize = 64 KB; 1294 if (streamPtr->dictSize < 4) streamPtr->dictSize = 0; 1295 streamPtr->dictionary = dictEnd - streamPtr->dictSize; 1296 } 1297 } 1298 1299 /* prefix mode : source data follows dictionary */ 1300 if (dictEnd == (const BYTE*)source) { 1301 if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) 1302 return LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, withPrefix64k, dictSmall, acceleration); 1303 else 1304 return LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, withPrefix64k, noDictIssue, acceleration); 1305 } 1306 1307 /* external dictionary mode */ 1308 { int result; 1309 if (streamPtr->dictCtx) { 1310 /* We depend here on the fact that dictCtx'es (produced by 1311 * LZ4_loadDict) guarantee that their tables contain no references 1312 * to offsets between dictCtx->currentOffset - 64 KB and 1313 * dictCtx->currentOffset - dictCtx->dictSize. This makes it safe 1314 * to use noDictIssue even when the dict isn't a full 64 KB. 1315 */ 1316 if (inputSize > 4 KB) { 1317 /* For compressing large blobs, it is faster to pay the setup 1318 * cost to copy the dictionary's tables into the active context, 1319 * so that the compression loop is only looking into one table. 1320 */ 1321 memcpy(streamPtr, streamPtr->dictCtx, sizeof(LZ4_stream_t)); 1322 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingExtDict, noDictIssue, acceleration); 1323 } else { 1324 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingDictCtx, noDictIssue, acceleration); 1325 } 1326 } else { 1327 if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) { 1328 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingExtDict, dictSmall, acceleration); 1329 } else { 1330 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingExtDict, noDictIssue, acceleration); 1331 } 1332 } 1333 streamPtr->dictionary = (const BYTE*)source; 1334 streamPtr->dictSize = (U32)inputSize; 1335 return result; 1336 } 1337 } 1338 1339 1340 /* Hidden debug function, to force-test external dictionary mode */ 1341 int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int srcSize) 1342 { 1343 LZ4_stream_t_internal* streamPtr = &LZ4_dict->internal_donotuse; 1344 int result; 1345 1346 LZ4_renormDictT(streamPtr, srcSize); 1347 1348 if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) { 1349 result = LZ4_compress_generic(streamPtr, source, dest, srcSize, NULL, 0, notLimited, byU32, usingExtDict, dictSmall, 1); 1350 } else { 1351 result = LZ4_compress_generic(streamPtr, source, dest, srcSize, NULL, 0, notLimited, byU32, usingExtDict, noDictIssue, 1); 1352 } 1353 1354 streamPtr->dictionary = (const BYTE*)source; 1355 streamPtr->dictSize = (U32)srcSize; 1356 1357 return result; 1358 } 1359 1360 1361 /*! LZ4_saveDict() : 1362 * If previously compressed data block is not guaranteed to remain available at its memory location, 1363 * save it into a safer place (char* safeBuffer). 1364 * Note : you don't need to call LZ4_loadDict() afterwards, 1365 * dictionary is immediately usable, you can therefore call LZ4_compress_fast_continue(). 1366 * Return : saved dictionary size in bytes (necessarily <= dictSize), or 0 if error. 1367 */ 1368 int LZ4_saveDict (LZ4_stream_t* LZ4_dict, char* safeBuffer, int dictSize) 1369 { 1370 LZ4_stream_t_internal* const dict = &LZ4_dict->internal_donotuse; 1371 const BYTE* const previousDictEnd = dict->dictionary + dict->dictSize; 1372 1373 if ((U32)dictSize > 64 KB) dictSize = 64 KB; /* useless to define a dictionary > 64 KB */ 1374 if ((U32)dictSize > dict->dictSize) dictSize = dict->dictSize; 1375 1376 memmove(safeBuffer, previousDictEnd - dictSize, dictSize); 1377 1378 dict->dictionary = (const BYTE*)safeBuffer; 1379 dict->dictSize = (U32)dictSize; 1380 1381 return dictSize; 1382 } 1383 1384 1385 1386 /*-******************************* 1387 * Decompression functions 1388 ********************************/ 1389 1390 typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive; 1391 typedef enum { decode_full_block = 0, partial_decode = 1 } earlyEnd_directive; 1392 1393 #undef MIN 1394 #define MIN(a,b) ( (a) < (b) ? (a) : (b) ) 1395 1396 /*! LZ4_decompress_generic() : 1397 * This generic decompression function covers all use cases. 1398 * It shall be instantiated several times, using different sets of directives. 1399 * Note that it is important for performance that this function really get inlined, 1400 * in order to remove useless branches during compilation optimization. 1401 */ 1402 LZ4_FORCE_INLINE int 1403 LZ4_decompress_generic( 1404 const char* const src, 1405 char* const dst, 1406 int srcSize, 1407 int outputSize, /* If endOnInput==endOnInputSize, this value is `dstCapacity` */ 1408 1409 endCondition_directive endOnInput, /* endOnOutputSize, endOnInputSize */ 1410 earlyEnd_directive partialDecoding, /* full, partial */ 1411 dict_directive dict, /* noDict, withPrefix64k, usingExtDict */ 1412 const BYTE* const lowPrefix, /* always <= dst, == dst when no prefix */ 1413 const BYTE* const dictStart, /* only if dict==usingExtDict */ 1414 const size_t dictSize /* note : = 0 if noDict */ 1415 ) 1416 { 1417 const BYTE* ip = (const BYTE*) src; 1418 const BYTE* const iend = ip + srcSize; 1419 1420 BYTE* op = (BYTE*) dst; 1421 BYTE* const oend = op + outputSize; 1422 BYTE* cpy; 1423 1424 const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize; 1425 const unsigned inc32table[8] = {0, 1, 2, 1, 0, 4, 4, 4}; 1426 const int dec64table[8] = {0, 0, 0, -1, -4, 1, 2, 3}; 1427 1428 const int safeDecode = (endOnInput==endOnInputSize); 1429 const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB))); 1430 1431 /* Set up the "end" pointers for the shortcut. */ 1432 const BYTE* const shortiend = iend - (endOnInput ? 14 : 8) /*maxLL*/ - 2 /*offset*/; 1433 const BYTE* const shortoend = oend - (endOnInput ? 14 : 8) /*maxLL*/ - 18 /*maxML*/; 1434 1435 DEBUGLOG(5, "LZ4_decompress_generic (srcSize:%i, dstSize:%i)", srcSize, outputSize); 1436 1437 /* Special cases */ 1438 assert(lowPrefix <= op); 1439 assert(src != NULL); 1440 if ((endOnInput) && (unlikely(outputSize==0))) return ((srcSize==1) && (*ip==0)) ? 0 : -1; /* Empty output buffer */ 1441 if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0 ? 1 : -1); 1442 if ((endOnInput) && unlikely(srcSize==0)) return -1; 1443 1444 /* Main Loop : decode sequences */ 1445 while (1) { 1446 const BYTE* match; 1447 size_t offset; 1448 1449 unsigned const token = *ip++; 1450 size_t length = token >> ML_BITS; /* literal length */ 1451 1452 assert(!endOnInput || ip <= iend); /* ip < iend before the increment */ 1453 1454 /* A two-stage shortcut for the most common case: 1455 * 1) If the literal length is 0..14, and there is enough space, 1456 * enter the shortcut and copy 16 bytes on behalf of the literals 1457 * (in the fast mode, only 8 bytes can be safely copied this way). 1458 * 2) Further if the match length is 4..18, copy 18 bytes in a similar 1459 * manner; but we ensure that there's enough space in the output for 1460 * those 18 bytes earlier, upon entering the shortcut (in other words, 1461 * there is a combined check for both stages). 1462 */ 1463 if ( (endOnInput ? length != RUN_MASK : length <= 8) 1464 /* strictly "less than" on input, to re-enter the loop with at least one byte */ 1465 && likely((endOnInput ? ip < shortiend : 1) & (op <= shortoend)) ) { 1466 /* Copy the literals */ 1467 memcpy(op, ip, endOnInput ? 16 : 8); 1468 op += length; ip += length; 1469 1470 /* The second stage: prepare for match copying, decode full info. 1471 * If it doesn't work out, the info won't be wasted. */ 1472 length = token & ML_MASK; /* match length */ 1473 offset = LZ4_readLE16(ip); ip += 2; 1474 match = op - offset; 1475 assert(match <= op); /* check overflow */ 1476 1477 /* Do not deal with overlapping matches. */ 1478 if ( (length != ML_MASK) 1479 && (offset >= 8) 1480 && (dict==withPrefix64k || match >= lowPrefix) ) { 1481 /* Copy the match. */ 1482 memcpy(op + 0, match + 0, 8); 1483 memcpy(op + 8, match + 8, 8); 1484 memcpy(op +16, match +16, 2); 1485 op += length + MINMATCH; 1486 /* Both stages worked, load the next token. */ 1487 continue; 1488 } 1489 1490 /* The second stage didn't work out, but the info is ready. 1491 * Propel it right to the point of match copying. */ 1492 goto _copy_match; 1493 } 1494 1495 /* decode literal length */ 1496 if (length == RUN_MASK) { 1497 unsigned s; 1498 if (unlikely(endOnInput ? ip >= iend-RUN_MASK : 0)) goto _output_error; /* overflow detection */ 1499 do { 1500 s = *ip++; 1501 length += s; 1502 } while ( likely(endOnInput ? ip<iend-RUN_MASK : 1) & (s==255) ); 1503 if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)(op))) goto _output_error; /* overflow detection */ 1504 if ((safeDecode) && unlikely((uptrval)(ip)+length<(uptrval)(ip))) goto _output_error; /* overflow detection */ 1505 } 1506 1507 /* copy literals */ 1508 cpy = op+length; 1509 LZ4_STATIC_ASSERT(MFLIMIT >= WILDCOPYLENGTH); 1510 if ( ((endOnInput) && ((cpy>oend-MFLIMIT) || (ip+length>iend-(2+1+LASTLITERALS))) ) 1511 || ((!endOnInput) && (cpy>oend-WILDCOPYLENGTH)) ) 1512 { 1513 if (partialDecoding) { 1514 if (cpy > oend) { cpy = oend; length = oend-op; } /* Partial decoding : stop in the middle of literal segment */ 1515 if ((endOnInput) && (ip+length > iend)) goto _output_error; /* Error : read attempt beyond end of input buffer */ 1516 } else { 1517 if ((!endOnInput) && (cpy != oend)) goto _output_error; /* Error : block decoding must stop exactly there */ 1518 if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error; /* Error : input must be consumed */ 1519 } 1520 memcpy(op, ip, length); 1521 ip += length; 1522 op += length; 1523 if (!partialDecoding || (cpy == oend)) { 1524 /* Necessarily EOF, due to parsing restrictions */ 1525 break; 1526 } 1527 1528 } else { 1529 LZ4_wildCopy(op, ip, cpy); /* may overwrite up to WILDCOPYLENGTH beyond cpy */ 1530 ip += length; op = cpy; 1531 } 1532 1533 /* get offset */ 1534 offset = LZ4_readLE16(ip); ip+=2; 1535 match = op - offset; 1536 1537 /* get matchlength */ 1538 length = token & ML_MASK; 1539 1540 _copy_match: 1541 if ((checkOffset) && (unlikely(match + dictSize < lowPrefix))) goto _output_error; /* Error : offset outside buffers */ 1542 if (!partialDecoding) { 1543 assert(oend > op); 1544 assert(oend - op >= 4); 1545 LZ4_write32(op, 0); /* silence an msan warning when offset==0; costs <1%; */ 1546 } /* note : when partialDecoding, there is no guarantee that at least 4 bytes remain available in output buffer */ 1547 1548 if (length == ML_MASK) { 1549 unsigned s; 1550 do { 1551 s = *ip++; 1552 if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error; 1553 length += s; 1554 } while (s==255); 1555 if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)op)) goto _output_error; /* overflow detection */ 1556 } 1557 length += MINMATCH; 1558 1559 /* match starting within external dictionary */ 1560 if ((dict==usingExtDict) && (match < lowPrefix)) { 1561 if (unlikely(op+length > oend-LASTLITERALS)) { 1562 if (partialDecoding) length = MIN(length, (size_t)(oend-op)); 1563 else goto _output_error; /* doesn't respect parsing restriction */ 1564 } 1565 1566 if (length <= (size_t)(lowPrefix-match)) { 1567 /* match fits entirely within external dictionary : just copy */ 1568 memmove(op, dictEnd - (lowPrefix-match), length); 1569 op += length; 1570 } else { 1571 /* match stretches into both external dictionary and current block */ 1572 size_t const copySize = (size_t)(lowPrefix - match); 1573 size_t const restSize = length - copySize; 1574 memcpy(op, dictEnd - copySize, copySize); 1575 op += copySize; 1576 if (restSize > (size_t)(op - lowPrefix)) { /* overlap copy */ 1577 BYTE* const endOfMatch = op + restSize; 1578 const BYTE* copyFrom = lowPrefix; 1579 while (op < endOfMatch) *op++ = *copyFrom++; 1580 } else { 1581 memcpy(op, lowPrefix, restSize); 1582 op += restSize; 1583 } } 1584 continue; 1585 } 1586 1587 /* copy match within block */ 1588 cpy = op + length; 1589 1590 /* partialDecoding : may not respect endBlock parsing restrictions */ 1591 assert(op<=oend); 1592 if (partialDecoding && (cpy > oend-MATCH_SAFEGUARD_DISTANCE)) { 1593 size_t const mlen = MIN(length, (size_t)(oend-op)); 1594 const BYTE* const matchEnd = match + mlen; 1595 BYTE* const copyEnd = op + mlen; 1596 if (matchEnd > op) { /* overlap copy */ 1597 while (op < copyEnd) *op++ = *match++; 1598 } else { 1599 memcpy(op, match, mlen); 1600 } 1601 op = copyEnd; 1602 if (op==oend) break; 1603 continue; 1604 } 1605 1606 if (unlikely(offset<8)) { 1607 op[0] = match[0]; 1608 op[1] = match[1]; 1609 op[2] = match[2]; 1610 op[3] = match[3]; 1611 match += inc32table[offset]; 1612 memcpy(op+4, match, 4); 1613 match -= dec64table[offset]; 1614 } else { 1615 memcpy(op, match, 8); 1616 match += 8; 1617 } 1618 op += 8; 1619 1620 if (unlikely(cpy > oend-MATCH_SAFEGUARD_DISTANCE)) { 1621 BYTE* const oCopyLimit = oend - (WILDCOPYLENGTH-1); 1622 if (cpy > oend-LASTLITERALS) goto _output_error; /* Error : last LASTLITERALS bytes must be literals (uncompressed) */ 1623 if (op < oCopyLimit) { 1624 LZ4_wildCopy(op, match, oCopyLimit); 1625 match += oCopyLimit - op; 1626 op = oCopyLimit; 1627 } 1628 while (op < cpy) *op++ = *match++; 1629 } else { 1630 memcpy(op, match, 8); 1631 if (length > 16) LZ4_wildCopy(op+8, match+8, cpy); 1632 } 1633 op = cpy; /* wildcopy correction */ 1634 } 1635 1636 /* end of decoding */ 1637 if (endOnInput) 1638 return (int) (((char*)op)-dst); /* Nb of output bytes decoded */ 1639 else 1640 return (int) (((const char*)ip)-src); /* Nb of input bytes read */ 1641 1642 /* Overflow error detected */ 1643 _output_error: 1644 return (int) (-(((const char*)ip)-src))-1; 1645 } 1646 1647 1648 /*===== Instantiate the API decoding functions. =====*/ 1649 1650 LZ4_FORCE_O2_GCC_PPC64LE 1651 int LZ4_decompress_safe(const char* source, char* dest, int compressedSize, int maxDecompressedSize) 1652 { 1653 return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize, 1654 endOnInputSize, decode_full_block, noDict, 1655 (BYTE*)dest, NULL, 0); 1656 } 1657 1658 LZ4_FORCE_O2_GCC_PPC64LE 1659 int LZ4_decompress_safe_partial(const char* src, char* dst, int compressedSize, int targetOutputSize, int dstCapacity) 1660 { 1661 dstCapacity = MIN(targetOutputSize, dstCapacity); 1662 return LZ4_decompress_generic(src, dst, compressedSize, dstCapacity, 1663 endOnInputSize, partial_decode, 1664 noDict, (BYTE*)dst, NULL, 0); 1665 } 1666 1667 LZ4_FORCE_O2_GCC_PPC64LE 1668 int LZ4_decompress_fast(const char* source, char* dest, int originalSize) 1669 { 1670 return LZ4_decompress_generic(source, dest, 0, originalSize, 1671 endOnOutputSize, decode_full_block, withPrefix64k, 1672 (BYTE*)dest - 64 KB, NULL, 0); 1673 } 1674 1675 /*===== Instantiate a few more decoding cases, used more than once. =====*/ 1676 1677 LZ4_FORCE_O2_GCC_PPC64LE /* Exported, an obsolete API function. */ 1678 int LZ4_decompress_safe_withPrefix64k(const char* source, char* dest, int compressedSize, int maxOutputSize) 1679 { 1680 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, 1681 endOnInputSize, decode_full_block, withPrefix64k, 1682 (BYTE*)dest - 64 KB, NULL, 0); 1683 } 1684 1685 /* Another obsolete API function, paired with the previous one. */ 1686 int LZ4_decompress_fast_withPrefix64k(const char* source, char* dest, int originalSize) 1687 { 1688 /* LZ4_decompress_fast doesn't validate match offsets, 1689 * and thus serves well with any prefixed dictionary. */ 1690 return LZ4_decompress_fast(source, dest, originalSize); 1691 } 1692 1693 LZ4_FORCE_O2_GCC_PPC64LE 1694 static int LZ4_decompress_safe_withSmallPrefix(const char* source, char* dest, int compressedSize, int maxOutputSize, 1695 size_t prefixSize) 1696 { 1697 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, 1698 endOnInputSize, decode_full_block, noDict, 1699 (BYTE*)dest-prefixSize, NULL, 0); 1700 } 1701 1702 LZ4_FORCE_O2_GCC_PPC64LE 1703 int LZ4_decompress_safe_forceExtDict(const char* source, char* dest, 1704 int compressedSize, int maxOutputSize, 1705 const void* dictStart, size_t dictSize) 1706 { 1707 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, 1708 endOnInputSize, decode_full_block, usingExtDict, 1709 (BYTE*)dest, (const BYTE*)dictStart, dictSize); 1710 } 1711 1712 LZ4_FORCE_O2_GCC_PPC64LE 1713 static int LZ4_decompress_fast_extDict(const char* source, char* dest, int originalSize, 1714 const void* dictStart, size_t dictSize) 1715 { 1716 return LZ4_decompress_generic(source, dest, 0, originalSize, 1717 endOnOutputSize, decode_full_block, usingExtDict, 1718 (BYTE*)dest, (const BYTE*)dictStart, dictSize); 1719 } 1720 1721 /* The "double dictionary" mode, for use with e.g. ring buffers: the first part 1722 * of the dictionary is passed as prefix, and the second via dictStart + dictSize. 1723 * These routines are used only once, in LZ4_decompress_*_continue(). 1724 */ 1725 LZ4_FORCE_INLINE 1726 int LZ4_decompress_safe_doubleDict(const char* source, char* dest, int compressedSize, int maxOutputSize, 1727 size_t prefixSize, const void* dictStart, size_t dictSize) 1728 { 1729 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, 1730 endOnInputSize, decode_full_block, usingExtDict, 1731 (BYTE*)dest-prefixSize, (const BYTE*)dictStart, dictSize); 1732 } 1733 1734 LZ4_FORCE_INLINE 1735 int LZ4_decompress_fast_doubleDict(const char* source, char* dest, int originalSize, 1736 size_t prefixSize, const void* dictStart, size_t dictSize) 1737 { 1738 return LZ4_decompress_generic(source, dest, 0, originalSize, 1739 endOnOutputSize, decode_full_block, usingExtDict, 1740 (BYTE*)dest-prefixSize, (const BYTE*)dictStart, dictSize); 1741 } 1742 1743 /*===== streaming decompression functions =====*/ 1744 1745 LZ4_streamDecode_t* LZ4_createStreamDecode(void) 1746 { 1747 LZ4_streamDecode_t* lz4s = (LZ4_streamDecode_t*) ALLOC_AND_ZERO(sizeof(LZ4_streamDecode_t)); 1748 return lz4s; 1749 } 1750 1751 int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream) 1752 { 1753 if (!LZ4_stream) return 0; /* support free on NULL */ 1754 FREEMEM(LZ4_stream); 1755 return 0; 1756 } 1757 1758 /*! LZ4_setStreamDecode() : 1759 * Use this function to instruct where to find the dictionary. 1760 * This function is not necessary if previous data is still available where it was decoded. 1761 * Loading a size of 0 is allowed (same effect as no dictionary). 1762 * @return : 1 if OK, 0 if error 1763 */ 1764 int LZ4_setStreamDecode (LZ4_streamDecode_t* LZ4_streamDecode, const char* dictionary, int dictSize) 1765 { 1766 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse; 1767 lz4sd->prefixSize = (size_t) dictSize; 1768 lz4sd->prefixEnd = (const BYTE*) dictionary + dictSize; 1769 lz4sd->externalDict = NULL; 1770 lz4sd->extDictSize = 0; 1771 return 1; 1772 } 1773 1774 /*! LZ4_decoderRingBufferSize() : 1775 * when setting a ring buffer for streaming decompression (optional scenario), 1776 * provides the minimum size of this ring buffer 1777 * to be compatible with any source respecting maxBlockSize condition. 1778 * Note : in a ring buffer scenario, 1779 * blocks are presumed decompressed next to each other. 1780 * When not enough space remains for next block (remainingSize < maxBlockSize), 1781 * decoding resumes from beginning of ring buffer. 1782 * @return : minimum ring buffer size, 1783 * or 0 if there is an error (invalid maxBlockSize). 1784 */ 1785 int LZ4_decoderRingBufferSize(int maxBlockSize) 1786 { 1787 if (maxBlockSize < 0) return 0; 1788 if (maxBlockSize > LZ4_MAX_INPUT_SIZE) return 0; 1789 if (maxBlockSize < 16) maxBlockSize = 16; 1790 return LZ4_DECODER_RING_BUFFER_SIZE(maxBlockSize); 1791 } 1792 1793 /* 1794 *_continue() : 1795 These decoding functions allow decompression of multiple blocks in "streaming" mode. 1796 Previously decoded blocks must still be available at the memory position where they were decoded. 1797 If it's not possible, save the relevant part of decoded data into a safe buffer, 1798 and indicate where it stands using LZ4_setStreamDecode() 1799 */ 1800 LZ4_FORCE_O2_GCC_PPC64LE 1801 int LZ4_decompress_safe_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxOutputSize) 1802 { 1803 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse; 1804 int result; 1805 1806 if (lz4sd->prefixSize == 0) { 1807 /* The first call, no dictionary yet. */ 1808 assert(lz4sd->extDictSize == 0); 1809 result = LZ4_decompress_safe(source, dest, compressedSize, maxOutputSize); 1810 if (result <= 0) return result; 1811 lz4sd->prefixSize = result; 1812 lz4sd->prefixEnd = (BYTE*)dest + result; 1813 } else if (lz4sd->prefixEnd == (BYTE*)dest) { 1814 /* They're rolling the current segment. */ 1815 if (lz4sd->prefixSize >= 64 KB - 1) 1816 result = LZ4_decompress_safe_withPrefix64k(source, dest, compressedSize, maxOutputSize); 1817 else if (lz4sd->extDictSize == 0) 1818 result = LZ4_decompress_safe_withSmallPrefix(source, dest, compressedSize, maxOutputSize, 1819 lz4sd->prefixSize); 1820 else 1821 result = LZ4_decompress_safe_doubleDict(source, dest, compressedSize, maxOutputSize, 1822 lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize); 1823 if (result <= 0) return result; 1824 lz4sd->prefixSize += result; 1825 lz4sd->prefixEnd += result; 1826 } else { 1827 /* The buffer wraps around, or they're switching to another buffer. */ 1828 lz4sd->extDictSize = lz4sd->prefixSize; 1829 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; 1830 result = LZ4_decompress_safe_forceExtDict(source, dest, compressedSize, maxOutputSize, 1831 lz4sd->externalDict, lz4sd->extDictSize); 1832 if (result <= 0) return result; 1833 lz4sd->prefixSize = result; 1834 lz4sd->prefixEnd = (BYTE*)dest + result; 1835 } 1836 1837 return result; 1838 } 1839 1840 LZ4_FORCE_O2_GCC_PPC64LE 1841 int LZ4_decompress_fast_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int originalSize) 1842 { 1843 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse; 1844 int result; 1845 1846 if (lz4sd->prefixSize == 0) { 1847 assert(lz4sd->extDictSize == 0); 1848 result = LZ4_decompress_fast(source, dest, originalSize); 1849 if (result <= 0) return result; 1850 lz4sd->prefixSize = originalSize; 1851 lz4sd->prefixEnd = (BYTE*)dest + originalSize; 1852 } else if (lz4sd->prefixEnd == (BYTE*)dest) { 1853 if (lz4sd->prefixSize >= 64 KB - 1 || lz4sd->extDictSize == 0) 1854 result = LZ4_decompress_fast(source, dest, originalSize); 1855 else 1856 result = LZ4_decompress_fast_doubleDict(source, dest, originalSize, 1857 lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize); 1858 if (result <= 0) return result; 1859 lz4sd->prefixSize += originalSize; 1860 lz4sd->prefixEnd += originalSize; 1861 } else { 1862 lz4sd->extDictSize = lz4sd->prefixSize; 1863 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; 1864 result = LZ4_decompress_fast_extDict(source, dest, originalSize, 1865 lz4sd->externalDict, lz4sd->extDictSize); 1866 if (result <= 0) return result; 1867 lz4sd->prefixSize = originalSize; 1868 lz4sd->prefixEnd = (BYTE*)dest + originalSize; 1869 } 1870 1871 return result; 1872 } 1873 1874 1875 /* 1876 Advanced decoding functions : 1877 *_usingDict() : 1878 These decoding functions work the same as "_continue" ones, 1879 the dictionary must be explicitly provided within parameters 1880 */ 1881 1882 int LZ4_decompress_safe_usingDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize) 1883 { 1884 if (dictSize==0) 1885 return LZ4_decompress_safe(source, dest, compressedSize, maxOutputSize); 1886 if (dictStart+dictSize == dest) { 1887 if (dictSize >= 64 KB - 1) 1888 return LZ4_decompress_safe_withPrefix64k(source, dest, compressedSize, maxOutputSize); 1889 return LZ4_decompress_safe_withSmallPrefix(source, dest, compressedSize, maxOutputSize, dictSize); 1890 } 1891 return LZ4_decompress_safe_forceExtDict(source, dest, compressedSize, maxOutputSize, dictStart, dictSize); 1892 } 1893 1894 int LZ4_decompress_fast_usingDict(const char* source, char* dest, int originalSize, const char* dictStart, int dictSize) 1895 { 1896 if (dictSize==0 || dictStart+dictSize == dest) 1897 return LZ4_decompress_fast(source, dest, originalSize); 1898 return LZ4_decompress_fast_extDict(source, dest, originalSize, dictStart, dictSize); 1899 } 1900 1901 1902 /*=************************************************* 1903 * Obsolete Functions 1904 ***************************************************/ 1905 /* obsolete compression functions */ 1906 int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize) 1907 { 1908 return LZ4_compress_default(source, dest, inputSize, maxOutputSize); 1909 } 1910 int LZ4_compress(const char* source, char* dest, int inputSize) 1911 { 1912 return LZ4_compress_default(source, dest, inputSize, LZ4_compressBound(inputSize)); 1913 } 1914 int LZ4_compress_limitedOutput_withState (void* state, const char* src, char* dst, int srcSize, int dstSize) 1915 { 1916 return LZ4_compress_fast_extState(state, src, dst, srcSize, dstSize, 1); 1917 } 1918 int LZ4_compress_withState (void* state, const char* src, char* dst, int srcSize) 1919 { 1920 return LZ4_compress_fast_extState(state, src, dst, srcSize, LZ4_compressBound(srcSize), 1); 1921 } 1922 int LZ4_compress_limitedOutput_continue (LZ4_stream_t* LZ4_stream, const char* src, char* dst, int srcSize, int dstCapacity) 1923 { 1924 return LZ4_compress_fast_continue(LZ4_stream, src, dst, srcSize, dstCapacity, 1); 1925 } 1926 int LZ4_compress_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize) 1927 { 1928 return LZ4_compress_fast_continue(LZ4_stream, source, dest, inputSize, LZ4_compressBound(inputSize), 1); 1929 } 1930 1931 /* 1932 These decompression functions are deprecated and should no longer be used. 1933 They are only provided here for compatibility with older user programs. 1934 - LZ4_uncompress is totally equivalent to LZ4_decompress_fast 1935 - LZ4_uncompress_unknownOutputSize is totally equivalent to LZ4_decompress_safe 1936 */ 1937 int LZ4_uncompress (const char* source, char* dest, int outputSize) 1938 { 1939 return LZ4_decompress_fast(source, dest, outputSize); 1940 } 1941 int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize) 1942 { 1943 return LZ4_decompress_safe(source, dest, isize, maxOutputSize); 1944 } 1945 1946 /* Obsolete Streaming functions */ 1947 1948 int LZ4_sizeofStreamState() { return LZ4_STREAMSIZE; } 1949 1950 int LZ4_resetStreamState(void* state, char* inputBuffer) 1951 { 1952 (void)inputBuffer; 1953 LZ4_resetStream((LZ4_stream_t*)state); 1954 return 0; 1955 } 1956 1957 void* LZ4_create (char* inputBuffer) 1958 { 1959 (void)inputBuffer; 1960 return LZ4_createStream(); 1961 } 1962 1963 char* LZ4_slideInputBuffer (void* state) 1964 { 1965 /* avoid const char * -> char * conversion warning */ 1966 return (char *)(uptrval)((LZ4_stream_t*)state)->internal_donotuse.dictionary; 1967 } 1968 1969 #endif /* LZ4_COMMONDEFS_ONLY */ 1970
