1 /* 2 LZ4 - Fast LZ compression algorithm 3 Copyright (C) 2011-2020, 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 #include "../../lv_conf_internal.h" 36 #if LV_USE_LZ4_INTERNAL 37 38 /*-************************************ 39 * Tuning parameters 40 **************************************/ 41 /* 42 * LZ4_HEAPMODE : 43 * Select how stateless compression functions like `LZ4_compress_default()` 44 * allocate memory for their hash table, 45 * in memory stack (0:default, fastest), or in memory heap (1:requires malloc()). 46 */ 47 #ifndef LZ4_HEAPMODE 48 # define LZ4_HEAPMODE 0 49 #endif 50 51 /* 52 * LZ4_ACCELERATION_DEFAULT : 53 * Select "acceleration" for LZ4_compress_fast() when parameter value <= 0 54 */ 55 #define LZ4_ACCELERATION_DEFAULT 1 56 /* 57 * LZ4_ACCELERATION_MAX : 58 * Any "acceleration" value higher than this threshold 59 * get treated as LZ4_ACCELERATION_MAX instead (fix #876) 60 */ 61 #define LZ4_ACCELERATION_MAX 65537 62 63 64 /*-************************************ 65 * CPU Feature Detection 66 **************************************/ 67 /* LZ4_FORCE_MEMORY_ACCESS 68 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable. 69 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal. 70 * The below switch allow to select different access method for improved performance. 71 * Method 0 (default) : use `memcpy()`. Safe and portable. 72 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable). 73 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`. 74 * Method 2 : direct access. This method is portable but violate C standard. 75 * It can generate buggy code on targets which assembly generation depends on alignment. 76 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6) 77 * See https://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details. 78 * Prefer these methods in priority order (0 > 1 > 2) 79 */ 80 #ifndef LZ4_FORCE_MEMORY_ACCESS /* can be defined externally */ 81 # if defined(__GNUC__) && \ 82 ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) \ 83 || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) ) 84 # define LZ4_FORCE_MEMORY_ACCESS 2 85 # elif (defined(__INTEL_COMPILER) && !defined(_WIN32)) || defined(__GNUC__) || defined(_MSC_VER) 86 # define LZ4_FORCE_MEMORY_ACCESS 1 87 # endif 88 #endif 89 90 /* 91 * LZ4_FORCE_SW_BITCOUNT 92 * Define this parameter if your target system or compiler does not support hardware bit count 93 */ 94 #if defined(_MSC_VER) && defined(_WIN32_WCE) /* Visual Studio for WinCE doesn't support Hardware bit count */ 95 # undef LZ4_FORCE_SW_BITCOUNT /* avoid double def */ 96 # define LZ4_FORCE_SW_BITCOUNT 97 #endif 98 99 100 101 /*-************************************ 102 * Dependency 103 **************************************/ 104 /* 105 * LZ4_SRC_INCLUDED: 106 * Amalgamation flag, whether lz4.c is included 107 */ 108 #ifndef LZ4_SRC_INCLUDED 109 # define LZ4_SRC_INCLUDED 1 110 #endif 111 112 #ifndef LZ4_STATIC_LINKING_ONLY 113 #define LZ4_STATIC_LINKING_ONLY 114 #endif 115 116 #ifndef LZ4_DISABLE_DEPRECATE_WARNINGS 117 #define LZ4_DISABLE_DEPRECATE_WARNINGS /* due to LZ4_decompress_safe_withPrefix64k */ 118 #endif 119 120 #define LZ4_STATIC_LINKING_ONLY /* LZ4_DISTANCE_MAX */ 121 #include "lz4.h" 122 /* see also "memory routines" below */ 123 124 125 /*-************************************ 126 * Compiler Options 127 **************************************/ 128 #if defined(_MSC_VER) && (_MSC_VER >= 1400) /* Visual Studio 2005+ */ 129 # include <intrin.h> /* only present in VS2005+ */ 130 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 131 # pragma warning(disable : 6237) /* disable: C6237: conditional expression is always 0 */ 132 #endif /* _MSC_VER */ 133 134 #ifndef LZ4_FORCE_INLINE 135 # ifdef _MSC_VER /* Visual Studio */ 136 # define LZ4_FORCE_INLINE static __forceinline 137 # else 138 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 139 # ifdef __GNUC__ 140 # define LZ4_FORCE_INLINE static inline __attribute__((always_inline)) 141 # else 142 # define LZ4_FORCE_INLINE static inline 143 # endif 144 # else 145 # define LZ4_FORCE_INLINE static 146 # endif /* __STDC_VERSION__ */ 147 # endif /* _MSC_VER */ 148 #endif /* LZ4_FORCE_INLINE */ 149 150 /* LZ4_FORCE_O2 and LZ4_FORCE_INLINE 151 * gcc on ppc64le generates an unrolled SIMDized loop for LZ4_wildCopy8, 152 * together with a simple 8-byte copy loop as a fall-back path. 153 * However, this optimization hurts the decompression speed by >30%, 154 * because the execution does not go to the optimized loop 155 * for typical compressible data, and all of the preamble checks 156 * before going to the fall-back path become useless overhead. 157 * This optimization happens only with the -O3 flag, and -O2 generates 158 * a simple 8-byte copy loop. 159 * With gcc on ppc64le, all of the LZ4_decompress_* and LZ4_wildCopy8 160 * functions are annotated with __attribute__((optimize("O2"))), 161 * and also LZ4_wildCopy8 is forcibly inlined, so that the O2 attribute 162 * of LZ4_wildCopy8 does not affect the compression speed. 163 */ 164 #if defined(__PPC64__) && defined(__LITTLE_ENDIAN__) && defined(__GNUC__) && !defined(__clang__) 165 # define LZ4_FORCE_O2 __attribute__((optimize("O2"))) 166 # undef LZ4_FORCE_INLINE 167 # define LZ4_FORCE_INLINE static __inline __attribute__((optimize("O2"),always_inline)) 168 #else 169 # define LZ4_FORCE_O2 170 #endif 171 172 #if (defined(__GNUC__) && (__GNUC__ >= 3)) || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 800)) || defined(__clang__) 173 # define expect(expr,value) (__builtin_expect ((expr),(value)) ) 174 #else 175 # define expect(expr,value) (expr) 176 #endif 177 178 #ifndef likely 179 #define likely(expr) expect((expr) != 0, 1) 180 #endif 181 #ifndef unlikely 182 #define unlikely(expr) expect((expr) != 0, 0) 183 #endif 184 185 /* Should the alignment test prove unreliable, for some reason, 186 * it can be disabled by setting LZ4_ALIGN_TEST to 0 */ 187 #ifndef LZ4_ALIGN_TEST /* can be externally provided */ 188 # define LZ4_ALIGN_TEST 1 189 #endif 190 191 192 /*-************************************ 193 * Memory routines 194 **************************************/ 195 196 /*! LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION : 197 * Disable relatively high-level LZ4/HC functions that use dynamic memory 198 * allocation functions (malloc(), calloc(), free()). 199 * 200 * Note that this is a compile-time switch. And since it disables 201 * public/stable LZ4 v1 API functions, we don't recommend using this 202 * symbol to generate a library for distribution. 203 * 204 * The following public functions are removed when this symbol is defined. 205 * - lz4 : LZ4_createStream, LZ4_freeStream, 206 * LZ4_createStreamDecode, LZ4_freeStreamDecode, LZ4_create (deprecated) 207 * - lz4hc : LZ4_createStreamHC, LZ4_freeStreamHC, 208 * LZ4_createHC (deprecated), LZ4_freeHC (deprecated) 209 * - lz4frame, lz4file : All LZ4F_* functions 210 */ 211 #if defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION) 212 # define ALLOC(s) lz4_error_memory_allocation_is_disabled 213 # define ALLOC_AND_ZERO(s) lz4_error_memory_allocation_is_disabled 214 # define FREEMEM(p) lz4_error_memory_allocation_is_disabled 215 #elif defined(LZ4_USER_MEMORY_FUNCTIONS) 216 /* memory management functions can be customized by user project. 217 * Below functions must exist somewhere in the Project 218 * and be available at link time */ 219 void* LZ4_malloc(size_t s); 220 void* LZ4_calloc(size_t n, size_t s); 221 void LZ4_free(void* p); 222 # define ALLOC(s) LZ4_malloc(s) 223 # define ALLOC_AND_ZERO(s) LZ4_calloc(1,s) 224 # define FREEMEM(p) LZ4_free(p) 225 #else 226 # include <stdlib.h> /* malloc, calloc, free */ 227 # define ALLOC(s) malloc(s) 228 # define ALLOC_AND_ZERO(s) calloc(1,s) 229 # define FREEMEM(p) free(p) 230 #endif 231 232 #if ! LZ4_FREESTANDING 233 # include <string.h> /* memset, memcpy */ 234 #endif 235 #if !defined(LZ4_memset) 236 # define LZ4_memset(p,v,s) memset((p),(v),(s)) 237 #endif 238 #define MEM_INIT(p,v,s) LZ4_memset((p),(v),(s)) 239 240 241 /*-************************************ 242 * Common Constants 243 **************************************/ 244 #define MINMATCH 4 245 246 #define WILDCOPYLENGTH 8 247 #define LASTLITERALS 5 /* see ../doc/lz4_Block_format.md#parsing-restrictions */ 248 #define MFLIMIT 12 /* see ../doc/lz4_Block_format.md#parsing-restrictions */ 249 #define MATCH_SAFEGUARD_DISTANCE ((2*WILDCOPYLENGTH) - MINMATCH) /* ensure it's possible to write 2 x wildcopyLength without overflowing output buffer */ 250 #define FASTLOOP_SAFE_DISTANCE 64 251 static const int LZ4_minLength = (MFLIMIT+1); 252 253 #define KB *(1 <<10) 254 #define MB *(1 <<20) 255 #define GB *(1U<<30) 256 257 #define LZ4_DISTANCE_ABSOLUTE_MAX 65535 258 #if (LZ4_DISTANCE_MAX > LZ4_DISTANCE_ABSOLUTE_MAX) /* max supported by LZ4 format */ 259 # error "LZ4_DISTANCE_MAX is too big : must be <= 65535" 260 #endif 261 262 #define ML_BITS 4 263 #define ML_MASK ((1U<<ML_BITS)-1) 264 #define RUN_BITS (8-ML_BITS) 265 #define RUN_MASK ((1U<<RUN_BITS)-1) 266 267 268 /*-************************************ 269 * Error detection 270 **************************************/ 271 #if defined(LZ4_DEBUG) && (LZ4_DEBUG>=1) 272 # include <assert.h> 273 #else 274 # ifndef assert 275 # define assert(condition) ((void)0) 276 # endif 277 #endif 278 279 #define LZ4_STATIC_ASSERT(c) { enum { LZ4_static_assert = 1/(int)(!!(c)) }; } /* use after variable declarations */ 280 281 #if defined(LZ4_DEBUG) && (LZ4_DEBUG>=2) 282 # include <stdio.h> 283 static int g_debuglog_enable = 1; 284 # define DEBUGLOG(l, ...) { \ 285 if ((g_debuglog_enable) && (l<=LZ4_DEBUG)) { \ 286 fprintf(stderr, __FILE__ " %i: ", __LINE__); \ 287 fprintf(stderr, __VA_ARGS__); \ 288 fprintf(stderr, " \n"); \ 289 } } 290 #else 291 # define DEBUGLOG(l, ...) {} /* disabled */ 292 #endif 293 LZ4_isAligned(const void * ptr,size_t alignment)294 static int LZ4_isAligned(const void* ptr, size_t alignment) 295 { 296 return ((size_t)ptr & (alignment -1)) == 0; 297 } 298 299 300 /*-************************************ 301 * Types 302 **************************************/ 303 #include <limits.h> 304 #if defined(__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 305 # include <stdint.h> 306 typedef uint8_t BYTE; 307 typedef uint16_t U16; 308 typedef uint32_t U32; 309 typedef int32_t S32; 310 typedef uint64_t U64; 311 typedef uintptr_t uptrval; 312 #else 313 # if UINT_MAX != 4294967295UL 314 # error "LZ4 code (when not C++ or C99) assumes that sizeof(int) == 4" 315 # endif 316 typedef unsigned char BYTE; 317 typedef unsigned short U16; 318 typedef unsigned int U32; 319 typedef signed int S32; 320 typedef unsigned long long U64; 321 typedef size_t uptrval; /* generally true, except OpenVMS-64 */ 322 #endif 323 324 #if defined(__x86_64__) 325 typedef U64 reg_t; /* 64-bits in x32 mode */ 326 #else 327 typedef size_t reg_t; /* 32-bits in x32 mode */ 328 #endif 329 330 typedef enum { 331 notLimited = 0, 332 limitedOutput = 1, 333 fillOutput = 2 334 } limitedOutput_directive; 335 336 337 /*-************************************ 338 * Reading and writing into memory 339 **************************************/ 340 341 /** 342 * LZ4 relies on memcpy with a constant size being inlined. In freestanding 343 * environments, the compiler can't assume the implementation of memcpy() is 344 * standard compliant, so it can't apply its specialized memcpy() inlining 345 * logic. When possible, use __builtin_memcpy() to tell the compiler to analyze 346 * memcpy() as if it were standard compliant, so it can inline it in freestanding 347 * environments. This is needed when decompressing the Linux Kernel, for example. 348 */ 349 #if !defined(LZ4_memcpy) 350 # if defined(__GNUC__) && (__GNUC__ >= 4) 351 # define LZ4_memcpy(dst, src, size) __builtin_memcpy(dst, src, size) 352 # else 353 # define LZ4_memcpy(dst, src, size) memcpy(dst, src, size) 354 # endif 355 #endif 356 357 #if !defined(LZ4_memmove) 358 # if defined(__GNUC__) && (__GNUC__ >= 4) 359 # define LZ4_memmove __builtin_memmove 360 # else 361 # define LZ4_memmove memmove 362 # endif 363 #endif 364 LZ4_isLittleEndian(void)365 static unsigned LZ4_isLittleEndian(void) 366 { 367 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ 368 return one.c[0]; 369 } 370 371 #if defined(__GNUC__) || defined(__INTEL_COMPILER) 372 #define LZ4_PACK( __Declaration__ ) __Declaration__ __attribute__((__packed__)) 373 #elif defined(_MSC_VER) 374 #define LZ4_PACK( __Declaration__ ) __pragma( pack(push, 1) ) __Declaration__ __pragma( pack(pop)) 375 #endif 376 377 #if defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==2) 378 /* lie to the compiler about data alignment; use with caution */ 379 LZ4_read16(const void * memPtr)380 static U16 LZ4_read16(const void* memPtr) { return *(const U16*) memPtr; } LZ4_read32(const void * memPtr)381 static U32 LZ4_read32(const void* memPtr) { return *(const U32*) memPtr; } LZ4_read_ARCH(const void * memPtr)382 static reg_t LZ4_read_ARCH(const void* memPtr) { return *(const reg_t*) memPtr; } 383 LZ4_write16(void * memPtr,U16 value)384 static void LZ4_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; } LZ4_write32(void * memPtr,U32 value)385 static void LZ4_write32(void* memPtr, U32 value) { *(U32*)memPtr = value; } 386 387 #elif defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==1) 388 389 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ 390 /* currently only defined for gcc and icc */ 391 LZ4_PACK(typedef struct { U16 u16; }) LZ4_unalign16; 392 LZ4_PACK(typedef struct { U32 u32; }) LZ4_unalign32; 393 LZ4_PACK(typedef struct { reg_t uArch; }) LZ4_unalignST; 394 LZ4_read16(const void * ptr)395 static U16 LZ4_read16(const void* ptr) { return ((const LZ4_unalign16*)ptr)->u16; } LZ4_read32(const void * ptr)396 static U32 LZ4_read32(const void* ptr) { return ((const LZ4_unalign32*)ptr)->u32; } LZ4_read_ARCH(const void * ptr)397 static reg_t LZ4_read_ARCH(const void* ptr) { return ((const LZ4_unalignST*)ptr)->uArch; } 398 LZ4_write16(void * memPtr,U16 value)399 static void LZ4_write16(void* memPtr, U16 value) { ((LZ4_unalign16*)memPtr)->u16 = value; } LZ4_write32(void * memPtr,U32 value)400 static void LZ4_write32(void* memPtr, U32 value) { ((LZ4_unalign32*)memPtr)->u32 = value; } 401 402 #else /* safe and portable access using memcpy() */ 403 LZ4_read16(const void * memPtr)404 static U16 LZ4_read16(const void* memPtr) 405 { 406 U16 val; LZ4_memcpy(&val, memPtr, sizeof(val)); return val; 407 } 408 LZ4_read32(const void * memPtr)409 static U32 LZ4_read32(const void* memPtr) 410 { 411 U32 val; LZ4_memcpy(&val, memPtr, sizeof(val)); return val; 412 } 413 LZ4_read_ARCH(const void * memPtr)414 static reg_t LZ4_read_ARCH(const void* memPtr) 415 { 416 reg_t val; LZ4_memcpy(&val, memPtr, sizeof(val)); return val; 417 } 418 LZ4_write16(void * memPtr,U16 value)419 static void LZ4_write16(void* memPtr, U16 value) 420 { 421 LZ4_memcpy(memPtr, &value, sizeof(value)); 422 } 423 LZ4_write32(void * memPtr,U32 value)424 static void LZ4_write32(void* memPtr, U32 value) 425 { 426 LZ4_memcpy(memPtr, &value, sizeof(value)); 427 } 428 429 #endif /* LZ4_FORCE_MEMORY_ACCESS */ 430 431 LZ4_readLE16(const void * memPtr)432 static U16 LZ4_readLE16(const void* memPtr) 433 { 434 if (LZ4_isLittleEndian()) { 435 return LZ4_read16(memPtr); 436 } else { 437 const BYTE* p = (const BYTE*)memPtr; 438 return (U16)((U16)p[0] + (p[1]<<8)); 439 } 440 } 441 LZ4_writeLE16(void * memPtr,U16 value)442 static void LZ4_writeLE16(void* memPtr, U16 value) 443 { 444 if (LZ4_isLittleEndian()) { 445 LZ4_write16(memPtr, value); 446 } else { 447 BYTE* p = (BYTE*)memPtr; 448 p[0] = (BYTE) value; 449 p[1] = (BYTE)(value>>8); 450 } 451 } 452 453 /* customized variant of memcpy, which can overwrite up to 8 bytes beyond dstEnd */ 454 LZ4_FORCE_INLINE LZ4_wildCopy8(void * dstPtr,const void * srcPtr,void * dstEnd)455 void LZ4_wildCopy8(void* dstPtr, const void* srcPtr, void* dstEnd) 456 { 457 BYTE* d = (BYTE*)dstPtr; 458 const BYTE* s = (const BYTE*)srcPtr; 459 BYTE* const e = (BYTE*)dstEnd; 460 461 do { LZ4_memcpy(d,s,8); d+=8; s+=8; } while (d<e); 462 } 463 464 static const unsigned inc32table[8] = {0, 1, 2, 1, 0, 4, 4, 4}; 465 static const int dec64table[8] = {0, 0, 0, -1, -4, 1, 2, 3}; 466 467 468 #ifndef LZ4_FAST_DEC_LOOP 469 # if defined __i386__ || defined _M_IX86 || defined __x86_64__ || defined _M_X64 470 # define LZ4_FAST_DEC_LOOP 1 471 # elif defined(__aarch64__) && defined(__APPLE__) 472 # define LZ4_FAST_DEC_LOOP 1 473 # elif defined(__aarch64__) && !defined(__clang__) 474 /* On non-Apple aarch64, we disable this optimization for clang because 475 * on certain mobile chipsets, performance is reduced with clang. For 476 * more information refer to https://github.com/lz4/lz4/pull/707 */ 477 # define LZ4_FAST_DEC_LOOP 1 478 # else 479 # define LZ4_FAST_DEC_LOOP 0 480 # endif 481 #endif 482 483 #if LZ4_FAST_DEC_LOOP 484 485 LZ4_FORCE_INLINE void LZ4_memcpy_using_offset_base(BYTE * dstPtr,const BYTE * srcPtr,BYTE * dstEnd,const size_t offset)486 LZ4_memcpy_using_offset_base(BYTE* dstPtr, const BYTE* srcPtr, BYTE* dstEnd, const size_t offset) 487 { 488 assert(srcPtr + offset == dstPtr); 489 if (offset < 8) { 490 LZ4_write32(dstPtr, 0); /* silence an msan warning when offset==0 */ 491 dstPtr[0] = srcPtr[0]; 492 dstPtr[1] = srcPtr[1]; 493 dstPtr[2] = srcPtr[2]; 494 dstPtr[3] = srcPtr[3]; 495 srcPtr += inc32table[offset]; 496 LZ4_memcpy(dstPtr+4, srcPtr, 4); 497 srcPtr -= dec64table[offset]; 498 dstPtr += 8; 499 } else { 500 LZ4_memcpy(dstPtr, srcPtr, 8); 501 dstPtr += 8; 502 srcPtr += 8; 503 } 504 505 LZ4_wildCopy8(dstPtr, srcPtr, dstEnd); 506 } 507 508 /* customized variant of memcpy, which can overwrite up to 32 bytes beyond dstEnd 509 * this version copies two times 16 bytes (instead of one time 32 bytes) 510 * because it must be compatible with offsets >= 16. */ 511 LZ4_FORCE_INLINE void LZ4_wildCopy32(void * dstPtr,const void * srcPtr,void * dstEnd)512 LZ4_wildCopy32(void* dstPtr, const void* srcPtr, void* dstEnd) 513 { 514 BYTE* d = (BYTE*)dstPtr; 515 const BYTE* s = (const BYTE*)srcPtr; 516 BYTE* const e = (BYTE*)dstEnd; 517 518 do { LZ4_memcpy(d,s,16); LZ4_memcpy(d+16,s+16,16); d+=32; s+=32; } while (d<e); 519 } 520 521 /* LZ4_memcpy_using_offset() presumes : 522 * - dstEnd >= dstPtr + MINMATCH 523 * - there is at least 8 bytes available to write after dstEnd */ 524 LZ4_FORCE_INLINE void LZ4_memcpy_using_offset(BYTE * dstPtr,const BYTE * srcPtr,BYTE * dstEnd,const size_t offset)525 LZ4_memcpy_using_offset(BYTE* dstPtr, const BYTE* srcPtr, BYTE* dstEnd, const size_t offset) 526 { 527 BYTE v[8]; 528 529 assert(dstEnd >= dstPtr + MINMATCH); 530 531 switch(offset) { 532 case 1: 533 MEM_INIT(v, *srcPtr, 8); 534 break; 535 case 2: 536 LZ4_memcpy(v, srcPtr, 2); 537 LZ4_memcpy(&v[2], srcPtr, 2); 538 #if defined(_MSC_VER) && (_MSC_VER <= 1937) /* MSVC 2022 ver 17.7 or earlier */ 539 # pragma warning(push) 540 # pragma warning(disable : 6385) /* warning C6385: Reading invalid data from 'v'. */ 541 #endif 542 LZ4_memcpy(&v[4], v, 4); 543 #if defined(_MSC_VER) && (_MSC_VER <= 1937) /* MSVC 2022 ver 17.7 or earlier */ 544 # pragma warning(pop) 545 #endif 546 break; 547 case 4: 548 LZ4_memcpy(v, srcPtr, 4); 549 LZ4_memcpy(&v[4], srcPtr, 4); 550 break; 551 default: 552 LZ4_memcpy_using_offset_base(dstPtr, srcPtr, dstEnd, offset); 553 return; 554 } 555 556 LZ4_memcpy(dstPtr, v, 8); 557 dstPtr += 8; 558 while (dstPtr < dstEnd) { 559 LZ4_memcpy(dstPtr, v, 8); 560 dstPtr += 8; 561 } 562 } 563 #endif 564 565 566 /*-************************************ 567 * Common functions 568 **************************************/ LZ4_NbCommonBytes(reg_t val)569 static unsigned LZ4_NbCommonBytes (reg_t val) 570 { 571 assert(val != 0); 572 if (LZ4_isLittleEndian()) { 573 if (sizeof(val) == 8) { 574 # if defined(_MSC_VER) && (_MSC_VER >= 1800) && (defined(_M_AMD64) && !defined(_M_ARM64EC)) && !defined(LZ4_FORCE_SW_BITCOUNT) 575 /*-************************************************************************************************* 576 * ARM64EC is a Microsoft-designed ARM64 ABI compatible with AMD64 applications on ARM64 Windows 11. 577 * The ARM64EC ABI does not support AVX/AVX2/AVX512 instructions, nor their relevant intrinsics 578 * including _tzcnt_u64. Therefore, we need to neuter the _tzcnt_u64 code path for ARM64EC. 579 ****************************************************************************************************/ 580 # if defined(__clang__) && (__clang_major__ < 10) 581 /* Avoid undefined clang-cl intrinsics issue. 582 * See https://github.com/lz4/lz4/pull/1017 for details. */ 583 return (unsigned)__builtin_ia32_tzcnt_u64(val) >> 3; 584 # else 585 /* x64 CPUS without BMI support interpret `TZCNT` as `REP BSF` */ 586 return (unsigned)_tzcnt_u64(val) >> 3; 587 # endif 588 # elif defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT) 589 unsigned long r = 0; 590 _BitScanForward64(&r, (U64)val); 591 return (unsigned)r >> 3; 592 # elif (defined(__clang__) || (defined(__GNUC__) && ((__GNUC__ > 3) || \ 593 ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))))) && \ 594 !defined(LZ4_FORCE_SW_BITCOUNT) 595 return (unsigned)__builtin_ctzll((U64)val) >> 3; 596 # else 597 const U64 m = 0x0101010101010101ULL; 598 val ^= val - 1; 599 return (unsigned)(((U64)((val & (m - 1)) * m)) >> 56); 600 # endif 601 } else /* 32 bits */ { 602 # if defined(_MSC_VER) && (_MSC_VER >= 1400) && !defined(LZ4_FORCE_SW_BITCOUNT) 603 unsigned long r; 604 _BitScanForward(&r, (U32)val); 605 return (unsigned)r >> 3; 606 # elif (defined(__clang__) || (defined(__GNUC__) && ((__GNUC__ > 3) || \ 607 ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))))) && \ 608 !defined(__TINYC__) && !defined(LZ4_FORCE_SW_BITCOUNT) 609 return (unsigned)__builtin_ctz((U32)val) >> 3; 610 # else 611 const U32 m = 0x01010101; 612 return (unsigned)((((val - 1) ^ val) & (m - 1)) * m) >> 24; 613 # endif 614 } 615 } else /* Big Endian CPU */ { 616 if (sizeof(val)==8) { 617 # if (defined(__clang__) || (defined(__GNUC__) && ((__GNUC__ > 3) || \ 618 ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))))) && \ 619 !defined(__TINYC__) && !defined(LZ4_FORCE_SW_BITCOUNT) 620 return (unsigned)__builtin_clzll((U64)val) >> 3; 621 # else 622 #if 1 623 /* this method is probably faster, 624 * but adds a 128 bytes lookup table */ 625 static const unsigned char ctz7_tab[128] = { 626 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 627 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 628 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 629 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 630 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 631 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 632 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 633 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 634 }; 635 U64 const mask = 0x0101010101010101ULL; 636 U64 const t = (((val >> 8) - mask) | val) & mask; 637 return ctz7_tab[(t * 0x0080402010080402ULL) >> 57]; 638 #else 639 /* this method doesn't consume memory space like the previous one, 640 * but it contains several branches, 641 * that may end up slowing execution */ 642 static const U32 by32 = sizeof(val)*4; /* 32 on 64 bits (goal), 16 on 32 bits. 643 Just to avoid some static analyzer complaining about shift by 32 on 32-bits target. 644 Note that this code path is never triggered in 32-bits mode. */ 645 unsigned r; 646 if (!(val>>by32)) { r=4; } else { r=0; val>>=by32; } 647 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } 648 r += (!val); 649 return r; 650 #endif 651 # endif 652 } else /* 32 bits */ { 653 # if (defined(__clang__) || (defined(__GNUC__) && ((__GNUC__ > 3) || \ 654 ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))))) && \ 655 !defined(LZ4_FORCE_SW_BITCOUNT) 656 return (unsigned)__builtin_clz((U32)val) >> 3; 657 # else 658 val >>= 8; 659 val = ((((val + 0x00FFFF00) | 0x00FFFFFF) + val) | 660 (val + 0x00FF0000)) >> 24; 661 return (unsigned)val ^ 3; 662 # endif 663 } 664 } 665 } 666 667 668 #define STEPSIZE sizeof(reg_t) 669 LZ4_FORCE_INLINE LZ4_count(const BYTE * pIn,const BYTE * pMatch,const BYTE * pInLimit)670 unsigned LZ4_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* pInLimit) 671 { 672 const BYTE* const pStart = pIn; 673 674 if (likely(pIn < pInLimit-(STEPSIZE-1))) { 675 reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn); 676 if (!diff) { 677 pIn+=STEPSIZE; pMatch+=STEPSIZE; 678 } else { 679 return LZ4_NbCommonBytes(diff); 680 } } 681 682 while (likely(pIn < pInLimit-(STEPSIZE-1))) { 683 reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn); 684 if (!diff) { pIn+=STEPSIZE; pMatch+=STEPSIZE; continue; } 685 pIn += LZ4_NbCommonBytes(diff); 686 return (unsigned)(pIn - pStart); 687 } 688 689 if ((STEPSIZE==8) && (pIn<(pInLimit-3)) && (LZ4_read32(pMatch) == LZ4_read32(pIn))) { pIn+=4; pMatch+=4; } 690 if ((pIn<(pInLimit-1)) && (LZ4_read16(pMatch) == LZ4_read16(pIn))) { pIn+=2; pMatch+=2; } 691 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++; 692 return (unsigned)(pIn - pStart); 693 } 694 695 696 #ifndef LZ4_COMMONDEFS_ONLY 697 /*-************************************ 698 * Local Constants 699 **************************************/ 700 static const int LZ4_64Klimit = ((64 KB) + (MFLIMIT-1)); 701 static const U32 LZ4_skipTrigger = 6; /* Increase this value ==> compression run slower on incompressible data */ 702 703 704 /*-************************************ 705 * Local Structures and types 706 **************************************/ 707 typedef enum { clearedTable = 0, byPtr, byU32, byU16 } tableType_t; 708 709 /** 710 * This enum distinguishes several different modes of accessing previous 711 * content in the stream. 712 * 713 * - noDict : There is no preceding content. 714 * - withPrefix64k : Table entries up to ctx->dictSize before the current blob 715 * blob being compressed are valid and refer to the preceding 716 * content (of length ctx->dictSize), which is available 717 * contiguously preceding in memory the content currently 718 * being compressed. 719 * - usingExtDict : Like withPrefix64k, but the preceding content is somewhere 720 * else in memory, starting at ctx->dictionary with length 721 * ctx->dictSize. 722 * - usingDictCtx : Everything concerning the preceding content is 723 * in a separate context, pointed to by ctx->dictCtx. 724 * ctx->dictionary, ctx->dictSize, and table entries 725 * in the current context that refer to positions 726 * preceding the beginning of the current compression are 727 * ignored. Instead, ctx->dictCtx->dictionary and ctx->dictCtx 728 * ->dictSize describe the location and size of the preceding 729 * content, and matches are found by looking in the ctx 730 * ->dictCtx->hashTable. 731 */ 732 typedef enum { noDict = 0, withPrefix64k, usingExtDict, usingDictCtx } dict_directive; 733 typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive; 734 735 736 /*-************************************ 737 * Local Utils 738 **************************************/ LZ4_versionNumber(void)739 int LZ4_versionNumber (void) { return LZ4_VERSION_NUMBER; } LZ4_versionString(void)740 const char* LZ4_versionString(void) { return LZ4_VERSION_STRING; } LZ4_compressBound(int isize)741 int LZ4_compressBound(int isize) { return LZ4_COMPRESSBOUND(isize); } LZ4_sizeofState(void)742 int LZ4_sizeofState(void) { return sizeof(LZ4_stream_t); } 743 744 745 /*-**************************************** 746 * Internal Definitions, used only in Tests 747 *******************************************/ 748 #if defined (__cplusplus) 749 extern "C" { 750 #endif 751 752 int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int srcSize); 753 754 int LZ4_decompress_safe_forceExtDict(const char* source, char* dest, 755 int compressedSize, int maxOutputSize, 756 const void* dictStart, size_t dictSize); 757 int LZ4_decompress_safe_partial_forceExtDict(const char* source, char* dest, 758 int compressedSize, int targetOutputSize, int dstCapacity, 759 const void* dictStart, size_t dictSize); 760 #if defined (__cplusplus) 761 } 762 #endif 763 764 /*-****************************** 765 * Compression functions 766 ********************************/ LZ4_hash4(U32 sequence,tableType_t const tableType)767 LZ4_FORCE_INLINE U32 LZ4_hash4(U32 sequence, tableType_t const tableType) 768 { 769 if (tableType == byU16) 770 return ((sequence * 2654435761U) >> ((MINMATCH*8)-(LZ4_HASHLOG+1))); 771 else 772 return ((sequence * 2654435761U) >> ((MINMATCH*8)-LZ4_HASHLOG)); 773 } 774 LZ4_hash5(U64 sequence,tableType_t const tableType)775 LZ4_FORCE_INLINE U32 LZ4_hash5(U64 sequence, tableType_t const tableType) 776 { 777 const U32 hashLog = (tableType == byU16) ? LZ4_HASHLOG+1 : LZ4_HASHLOG; 778 if (LZ4_isLittleEndian()) { 779 const U64 prime5bytes = 889523592379ULL; 780 return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog)); 781 } else { 782 const U64 prime8bytes = 11400714785074694791ULL; 783 return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog)); 784 } 785 } 786 LZ4_hashPosition(const void * const p,tableType_t const tableType)787 LZ4_FORCE_INLINE U32 LZ4_hashPosition(const void* const p, tableType_t const tableType) 788 { 789 if ((sizeof(reg_t)==8) && (tableType != byU16)) return LZ4_hash5(LZ4_read_ARCH(p), tableType); 790 return LZ4_hash4(LZ4_read32(p), tableType); 791 } 792 LZ4_clearHash(U32 h,void * tableBase,tableType_t const tableType)793 LZ4_FORCE_INLINE void LZ4_clearHash(U32 h, void* tableBase, tableType_t const tableType) 794 { 795 switch (tableType) 796 { 797 default: /* fallthrough */ 798 case clearedTable: { /* illegal! */ assert(0); return; } 799 case byPtr: { const BYTE** hashTable = (const BYTE**)tableBase; hashTable[h] = NULL; return; } 800 case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = 0; return; } 801 case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = 0; return; } 802 } 803 } 804 LZ4_putIndexOnHash(U32 idx,U32 h,void * tableBase,tableType_t const tableType)805 LZ4_FORCE_INLINE void LZ4_putIndexOnHash(U32 idx, U32 h, void* tableBase, tableType_t const tableType) 806 { 807 switch (tableType) 808 { 809 default: /* fallthrough */ 810 case clearedTable: /* fallthrough */ 811 case byPtr: { /* illegal! */ assert(0); return; } 812 case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = idx; return; } 813 case byU16: { U16* hashTable = (U16*) tableBase; assert(idx < 65536); hashTable[h] = (U16)idx; return; } 814 } 815 } 816 817 /* LZ4_putPosition*() : only used in byPtr mode */ LZ4_putPositionOnHash(const BYTE * p,U32 h,void * tableBase,tableType_t const tableType)818 LZ4_FORCE_INLINE void LZ4_putPositionOnHash(const BYTE* p, U32 h, 819 void* tableBase, tableType_t const tableType) 820 { 821 const BYTE** const hashTable = (const BYTE**)tableBase; 822 assert(tableType == byPtr); (void)tableType; 823 hashTable[h] = p; 824 } 825 LZ4_putPosition(const BYTE * p,void * tableBase,tableType_t tableType)826 LZ4_FORCE_INLINE void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType) 827 { 828 U32 const h = LZ4_hashPosition(p, tableType); 829 LZ4_putPositionOnHash(p, h, tableBase, tableType); 830 } 831 832 /* LZ4_getIndexOnHash() : 833 * Index of match position registered in hash table. 834 * hash position must be calculated by using base+index, or dictBase+index. 835 * Assumption 1 : only valid if tableType == byU32 or byU16. 836 * Assumption 2 : h is presumed valid (within limits of hash table) 837 */ LZ4_getIndexOnHash(U32 h,const void * tableBase,tableType_t tableType)838 LZ4_FORCE_INLINE U32 LZ4_getIndexOnHash(U32 h, const void* tableBase, tableType_t tableType) 839 { 840 LZ4_STATIC_ASSERT(LZ4_MEMORY_USAGE > 2); 841 if (tableType == byU32) { 842 const U32* const hashTable = (const U32*) tableBase; 843 assert(h < (1U << (LZ4_MEMORY_USAGE-2))); 844 return hashTable[h]; 845 } 846 if (tableType == byU16) { 847 const U16* const hashTable = (const U16*) tableBase; 848 assert(h < (1U << (LZ4_MEMORY_USAGE-1))); 849 return hashTable[h]; 850 } 851 assert(0); return 0; /* forbidden case */ 852 } 853 LZ4_getPositionOnHash(U32 h,const void * tableBase,tableType_t tableType)854 static const BYTE* LZ4_getPositionOnHash(U32 h, const void* tableBase, tableType_t tableType) 855 { 856 assert(tableType == byPtr); (void)tableType; 857 { const BYTE* const* hashTable = (const BYTE* const*) tableBase; return hashTable[h]; } 858 } 859 860 LZ4_FORCE_INLINE const BYTE* LZ4_getPosition(const BYTE * p,const void * tableBase,tableType_t tableType)861 LZ4_getPosition(const BYTE* p, 862 const void* tableBase, tableType_t tableType) 863 { 864 U32 const h = LZ4_hashPosition(p, tableType); 865 return LZ4_getPositionOnHash(h, tableBase, tableType); 866 } 867 868 LZ4_FORCE_INLINE void LZ4_prepareTable(LZ4_stream_t_internal * const cctx,const int inputSize,const tableType_t tableType)869 LZ4_prepareTable(LZ4_stream_t_internal* const cctx, 870 const int inputSize, 871 const tableType_t tableType) { 872 /* If the table hasn't been used, it's guaranteed to be zeroed out, and is 873 * therefore safe to use no matter what mode we're in. Otherwise, we figure 874 * out if it's safe to leave as is or whether it needs to be reset. 875 */ 876 if ((tableType_t)cctx->tableType != clearedTable) { 877 assert(inputSize >= 0); 878 if ((tableType_t)cctx->tableType != tableType 879 || ((tableType == byU16) && cctx->currentOffset + (unsigned)inputSize >= 0xFFFFU) 880 || ((tableType == byU32) && cctx->currentOffset > 1 GB) 881 || tableType == byPtr 882 || inputSize >= 4 KB) 883 { 884 DEBUGLOG(4, "LZ4_prepareTable: Resetting table in %p", cctx); 885 MEM_INIT(cctx->hashTable, 0, LZ4_HASHTABLESIZE); 886 cctx->currentOffset = 0; 887 cctx->tableType = (U32)clearedTable; 888 } else { 889 DEBUGLOG(4, "LZ4_prepareTable: Re-use hash table (no reset)"); 890 } 891 } 892 893 /* Adding a gap, so all previous entries are > LZ4_DISTANCE_MAX back, 894 * is faster than compressing without a gap. 895 * However, compressing with currentOffset == 0 is faster still, 896 * so we preserve that case. 897 */ 898 if (cctx->currentOffset != 0 && tableType == byU32) { 899 DEBUGLOG(5, "LZ4_prepareTable: adding 64KB to currentOffset"); 900 cctx->currentOffset += 64 KB; 901 } 902 903 /* Finally, clear history */ 904 cctx->dictCtx = NULL; 905 cctx->dictionary = NULL; 906 cctx->dictSize = 0; 907 } 908 909 /** LZ4_compress_generic_validated() : 910 * inlined, to ensure branches are decided at compilation time. 911 * The following conditions are presumed already validated: 912 * - source != NULL 913 * - inputSize > 0 914 */ LZ4_compress_generic_validated(LZ4_stream_t_internal * const cctx,const char * const source,char * const dest,const int inputSize,int * inputConsumed,const int maxOutputSize,const limitedOutput_directive outputDirective,const tableType_t tableType,const dict_directive dictDirective,const dictIssue_directive dictIssue,const int acceleration)915 LZ4_FORCE_INLINE int LZ4_compress_generic_validated( 916 LZ4_stream_t_internal* const cctx, 917 const char* const source, 918 char* const dest, 919 const int inputSize, 920 int* inputConsumed, /* only written when outputDirective == fillOutput */ 921 const int maxOutputSize, 922 const limitedOutput_directive outputDirective, 923 const tableType_t tableType, 924 const dict_directive dictDirective, 925 const dictIssue_directive dictIssue, 926 const int acceleration) 927 { 928 int result; 929 const BYTE* ip = (const BYTE*)source; 930 931 U32 const startIndex = cctx->currentOffset; 932 const BYTE* base = (const BYTE*)source - startIndex; 933 const BYTE* lowLimit; 934 935 const LZ4_stream_t_internal* dictCtx = (const LZ4_stream_t_internal*) cctx->dictCtx; 936 const BYTE* const dictionary = 937 dictDirective == usingDictCtx ? dictCtx->dictionary : cctx->dictionary; 938 const U32 dictSize = 939 dictDirective == usingDictCtx ? dictCtx->dictSize : cctx->dictSize; 940 const U32 dictDelta = 941 (dictDirective == usingDictCtx) ? startIndex - dictCtx->currentOffset : 0; /* make indexes in dictCtx comparable with indexes in current context */ 942 943 int const maybe_extMem = (dictDirective == usingExtDict) || (dictDirective == usingDictCtx); 944 U32 const prefixIdxLimit = startIndex - dictSize; /* used when dictDirective == dictSmall */ 945 const BYTE* const dictEnd = dictionary ? dictionary + dictSize : dictionary; 946 const BYTE* anchor = (const BYTE*) source; 947 const BYTE* const iend = ip + inputSize; 948 const BYTE* const mflimitPlusOne = iend - MFLIMIT + 1; 949 const BYTE* const matchlimit = iend - LASTLITERALS; 950 951 /* the dictCtx currentOffset is indexed on the start of the dictionary, 952 * while a dictionary in the current context precedes the currentOffset */ 953 const BYTE* dictBase = (dictionary == NULL) ? NULL : 954 (dictDirective == usingDictCtx) ? 955 dictionary + dictSize - dictCtx->currentOffset : 956 dictionary + dictSize - startIndex; 957 958 BYTE* op = (BYTE*) dest; 959 BYTE* const olimit = op + maxOutputSize; 960 961 U32 offset = 0; 962 U32 forwardH; 963 964 DEBUGLOG(5, "LZ4_compress_generic_validated: srcSize=%i, tableType=%u", inputSize, tableType); 965 assert(ip != NULL); 966 if (tableType == byU16) assert(inputSize<LZ4_64Klimit); /* Size too large (not within 64K limit) */ 967 if (tableType == byPtr) assert(dictDirective==noDict); /* only supported use case with byPtr */ 968 /* If init conditions are not met, we don't have to mark stream 969 * as having dirty context, since no action was taken yet */ 970 if (outputDirective == fillOutput && maxOutputSize < 1) { return 0; } /* Impossible to store anything */ 971 assert(acceleration >= 1); 972 973 lowLimit = (const BYTE*)source - (dictDirective == withPrefix64k ? dictSize : 0); 974 975 /* Update context state */ 976 if (dictDirective == usingDictCtx) { 977 /* Subsequent linked blocks can't use the dictionary. */ 978 /* Instead, they use the block we just compressed. */ 979 cctx->dictCtx = NULL; 980 cctx->dictSize = (U32)inputSize; 981 } else { 982 cctx->dictSize += (U32)inputSize; 983 } 984 cctx->currentOffset += (U32)inputSize; 985 cctx->tableType = (U32)tableType; 986 987 if (inputSize<LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */ 988 989 /* First Byte */ 990 { U32 const h = LZ4_hashPosition(ip, tableType); 991 if (tableType == byPtr) { 992 LZ4_putPositionOnHash(ip, h, cctx->hashTable, byPtr); 993 } else { 994 LZ4_putIndexOnHash(startIndex, h, cctx->hashTable, tableType); 995 } } 996 ip++; forwardH = LZ4_hashPosition(ip, tableType); 997 998 /* Main Loop */ 999 for ( ; ; ) { 1000 const BYTE* match; 1001 BYTE* token; 1002 const BYTE* filledIp; 1003 1004 /* Find a match */ 1005 if (tableType == byPtr) { 1006 const BYTE* forwardIp = ip; 1007 int step = 1; 1008 int searchMatchNb = acceleration << LZ4_skipTrigger; 1009 do { 1010 U32 const h = forwardH; 1011 ip = forwardIp; 1012 forwardIp += step; 1013 step = (searchMatchNb++ >> LZ4_skipTrigger); 1014 1015 if (unlikely(forwardIp > mflimitPlusOne)) goto _last_literals; 1016 assert(ip < mflimitPlusOne); 1017 1018 match = LZ4_getPositionOnHash(h, cctx->hashTable, tableType); 1019 forwardH = LZ4_hashPosition(forwardIp, tableType); 1020 LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType); 1021 1022 } while ( (match+LZ4_DISTANCE_MAX < ip) 1023 || (LZ4_read32(match) != LZ4_read32(ip)) ); 1024 1025 } else { /* byU32, byU16 */ 1026 1027 const BYTE* forwardIp = ip; 1028 int step = 1; 1029 int searchMatchNb = acceleration << LZ4_skipTrigger; 1030 do { 1031 U32 const h = forwardH; 1032 U32 const current = (U32)(forwardIp - base); 1033 U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType); 1034 assert(matchIndex <= current); 1035 assert(forwardIp - base < (ptrdiff_t)(2 GB - 1)); 1036 ip = forwardIp; 1037 forwardIp += step; 1038 step = (searchMatchNb++ >> LZ4_skipTrigger); 1039 1040 if (unlikely(forwardIp > mflimitPlusOne)) goto _last_literals; 1041 assert(ip < mflimitPlusOne); 1042 1043 if (dictDirective == usingDictCtx) { 1044 if (matchIndex < startIndex) { 1045 /* there was no match, try the dictionary */ 1046 assert(tableType == byU32); 1047 matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32); 1048 match = dictBase + matchIndex; 1049 matchIndex += dictDelta; /* make dictCtx index comparable with current context */ 1050 lowLimit = dictionary; 1051 } else { 1052 match = base + matchIndex; 1053 lowLimit = (const BYTE*)source; 1054 } 1055 } else if (dictDirective == usingExtDict) { 1056 if (matchIndex < startIndex) { 1057 DEBUGLOG(7, "extDict candidate: matchIndex=%5u < startIndex=%5u", matchIndex, startIndex); 1058 assert(startIndex - matchIndex >= MINMATCH); 1059 assert(dictBase); 1060 match = dictBase + matchIndex; 1061 lowLimit = dictionary; 1062 } else { 1063 match = base + matchIndex; 1064 lowLimit = (const BYTE*)source; 1065 } 1066 } else { /* single continuous memory segment */ 1067 match = base + matchIndex; 1068 } 1069 forwardH = LZ4_hashPosition(forwardIp, tableType); 1070 LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType); 1071 1072 DEBUGLOG(7, "candidate at pos=%u (offset=%u \n", matchIndex, current - matchIndex); 1073 if ((dictIssue == dictSmall) && (matchIndex < prefixIdxLimit)) { continue; } /* match outside of valid area */ 1074 assert(matchIndex < current); 1075 if ( ((tableType != byU16) || (LZ4_DISTANCE_MAX < LZ4_DISTANCE_ABSOLUTE_MAX)) 1076 && (matchIndex+LZ4_DISTANCE_MAX < current)) { 1077 continue; 1078 } /* too far */ 1079 assert((current - matchIndex) <= LZ4_DISTANCE_MAX); /* match now expected within distance */ 1080 1081 if (LZ4_read32(match) == LZ4_read32(ip)) { 1082 if (maybe_extMem) offset = current - matchIndex; 1083 break; /* match found */ 1084 } 1085 1086 } while(1); 1087 } 1088 1089 /* Catch up */ 1090 filledIp = ip; 1091 assert(ip > anchor); /* this is always true as ip has been advanced before entering the main loop */ 1092 if ((match > lowLimit) && unlikely(ip[-1] == match[-1])) { 1093 do { ip--; match--; } while (((ip > anchor) & (match > lowLimit)) && (unlikely(ip[-1] == match[-1]))); 1094 } 1095 1096 /* Encode Literals */ 1097 { unsigned const litLength = (unsigned)(ip - anchor); 1098 token = op++; 1099 if ((outputDirective == limitedOutput) && /* Check output buffer overflow */ 1100 (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > olimit)) ) { 1101 return 0; /* cannot compress within `dst` budget. Stored indexes in hash table are nonetheless fine */ 1102 } 1103 if ((outputDirective == fillOutput) && 1104 (unlikely(op + (litLength+240)/255 /* litlen */ + litLength /* literals */ + 2 /* offset */ + 1 /* token */ + MFLIMIT - MINMATCH /* min last literals so last match is <= end - MFLIMIT */ > olimit))) { 1105 op--; 1106 goto _last_literals; 1107 } 1108 if (litLength >= RUN_MASK) { 1109 int len = (int)(litLength - RUN_MASK); 1110 *token = (RUN_MASK<<ML_BITS); 1111 for(; len >= 255 ; len-=255) *op++ = 255; 1112 *op++ = (BYTE)len; 1113 } 1114 else *token = (BYTE)(litLength<<ML_BITS); 1115 1116 /* Copy Literals */ 1117 LZ4_wildCopy8(op, anchor, op+litLength); 1118 op+=litLength; 1119 DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i", 1120 (int)(anchor-(const BYTE*)source), litLength, (int)(ip-(const BYTE*)source)); 1121 } 1122 1123 _next_match: 1124 /* at this stage, the following variables must be correctly set : 1125 * - ip : at start of LZ operation 1126 * - match : at start of previous pattern occurrence; can be within current prefix, or within extDict 1127 * - offset : if maybe_ext_memSegment==1 (constant) 1128 * - lowLimit : must be == dictionary to mean "match is within extDict"; must be == source otherwise 1129 * - token and *token : position to write 4-bits for match length; higher 4-bits for literal length supposed already written 1130 */ 1131 1132 if ((outputDirective == fillOutput) && 1133 (op + 2 /* offset */ + 1 /* token */ + MFLIMIT - MINMATCH /* min last literals so last match is <= end - MFLIMIT */ > olimit)) { 1134 /* the match was too close to the end, rewind and go to last literals */ 1135 op = token; 1136 goto _last_literals; 1137 } 1138 1139 /* Encode Offset */ 1140 if (maybe_extMem) { /* static test */ 1141 DEBUGLOG(6, " with offset=%u (ext if > %i)", offset, (int)(ip - (const BYTE*)source)); 1142 assert(offset <= LZ4_DISTANCE_MAX && offset > 0); 1143 LZ4_writeLE16(op, (U16)offset); op+=2; 1144 } else { 1145 DEBUGLOG(6, " with offset=%u (same segment)", (U32)(ip - match)); 1146 assert(ip-match <= LZ4_DISTANCE_MAX); 1147 LZ4_writeLE16(op, (U16)(ip - match)); op+=2; 1148 } 1149 1150 /* Encode MatchLength */ 1151 { unsigned matchCode; 1152 1153 if ( (dictDirective==usingExtDict || dictDirective==usingDictCtx) 1154 && (lowLimit==dictionary) /* match within extDict */ ) { 1155 const BYTE* limit = ip + (dictEnd-match); 1156 assert(dictEnd > match); 1157 if (limit > matchlimit) limit = matchlimit; 1158 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, limit); 1159 ip += (size_t)matchCode + MINMATCH; 1160 if (ip==limit) { 1161 unsigned const more = LZ4_count(limit, (const BYTE*)source, matchlimit); 1162 matchCode += more; 1163 ip += more; 1164 } 1165 DEBUGLOG(6, " with matchLength=%u starting in extDict", matchCode+MINMATCH); 1166 } else { 1167 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit); 1168 ip += (size_t)matchCode + MINMATCH; 1169 DEBUGLOG(6, " with matchLength=%u", matchCode+MINMATCH); 1170 } 1171 1172 if ((outputDirective) && /* Check output buffer overflow */ 1173 (unlikely(op + (1 + LASTLITERALS) + (matchCode+240)/255 > olimit)) ) { 1174 if (outputDirective == fillOutput) { 1175 /* Match description too long : reduce it */ 1176 U32 newMatchCode = 15 /* in token */ - 1 /* to avoid needing a zero byte */ + ((U32)(olimit - op) - 1 - LASTLITERALS) * 255; 1177 ip -= matchCode - newMatchCode; 1178 assert(newMatchCode < matchCode); 1179 matchCode = newMatchCode; 1180 if (unlikely(ip <= filledIp)) { 1181 /* We have already filled up to filledIp so if ip ends up less than filledIp 1182 * we have positions in the hash table beyond the current position. This is 1183 * a problem if we reuse the hash table. So we have to remove these positions 1184 * from the hash table. 1185 */ 1186 const BYTE* ptr; 1187 DEBUGLOG(5, "Clearing %u positions", (U32)(filledIp - ip)); 1188 for (ptr = ip; ptr <= filledIp; ++ptr) { 1189 U32 const h = LZ4_hashPosition(ptr, tableType); 1190 LZ4_clearHash(h, cctx->hashTable, tableType); 1191 } 1192 } 1193 } else { 1194 assert(outputDirective == limitedOutput); 1195 return 0; /* cannot compress within `dst` budget. Stored indexes in hash table are nonetheless fine */ 1196 } 1197 } 1198 if (matchCode >= ML_MASK) { 1199 *token += ML_MASK; 1200 matchCode -= ML_MASK; 1201 LZ4_write32(op, 0xFFFFFFFF); 1202 while (matchCode >= 4*255) { 1203 op+=4; 1204 LZ4_write32(op, 0xFFFFFFFF); 1205 matchCode -= 4*255; 1206 } 1207 op += matchCode / 255; 1208 *op++ = (BYTE)(matchCode % 255); 1209 } else 1210 *token += (BYTE)(matchCode); 1211 } 1212 /* Ensure we have enough space for the last literals. */ 1213 assert(!(outputDirective == fillOutput && op + 1 + LASTLITERALS > olimit)); 1214 1215 anchor = ip; 1216 1217 /* Test end of chunk */ 1218 if (ip >= mflimitPlusOne) break; 1219 1220 /* Fill table */ 1221 { U32 const h = LZ4_hashPosition(ip-2, tableType); 1222 if (tableType == byPtr) { 1223 LZ4_putPositionOnHash(ip-2, h, cctx->hashTable, byPtr); 1224 } else { 1225 U32 const idx = (U32)((ip-2) - base); 1226 LZ4_putIndexOnHash(idx, h, cctx->hashTable, tableType); 1227 } } 1228 1229 /* Test next position */ 1230 if (tableType == byPtr) { 1231 1232 match = LZ4_getPosition(ip, cctx->hashTable, tableType); 1233 LZ4_putPosition(ip, cctx->hashTable, tableType); 1234 if ( (match+LZ4_DISTANCE_MAX >= ip) 1235 && (LZ4_read32(match) == LZ4_read32(ip)) ) 1236 { token=op++; *token=0; goto _next_match; } 1237 1238 } else { /* byU32, byU16 */ 1239 1240 U32 const h = LZ4_hashPosition(ip, tableType); 1241 U32 const current = (U32)(ip-base); 1242 U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType); 1243 assert(matchIndex < current); 1244 if (dictDirective == usingDictCtx) { 1245 if (matchIndex < startIndex) { 1246 /* there was no match, try the dictionary */ 1247 assert(tableType == byU32); 1248 matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32); 1249 match = dictBase + matchIndex; 1250 lowLimit = dictionary; /* required for match length counter */ 1251 matchIndex += dictDelta; 1252 } else { 1253 match = base + matchIndex; 1254 lowLimit = (const BYTE*)source; /* required for match length counter */ 1255 } 1256 } else if (dictDirective==usingExtDict) { 1257 if (matchIndex < startIndex) { 1258 assert(dictBase); 1259 match = dictBase + matchIndex; 1260 lowLimit = dictionary; /* required for match length counter */ 1261 } else { 1262 match = base + matchIndex; 1263 lowLimit = (const BYTE*)source; /* required for match length counter */ 1264 } 1265 } else { /* single memory segment */ 1266 match = base + matchIndex; 1267 } 1268 LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType); 1269 assert(matchIndex < current); 1270 if ( ((dictIssue==dictSmall) ? (matchIndex >= prefixIdxLimit) : 1) 1271 && (((tableType==byU16) && (LZ4_DISTANCE_MAX == LZ4_DISTANCE_ABSOLUTE_MAX)) ? 1 : (matchIndex+LZ4_DISTANCE_MAX >= current)) 1272 && (LZ4_read32(match) == LZ4_read32(ip)) ) { 1273 token=op++; 1274 *token=0; 1275 if (maybe_extMem) offset = current - matchIndex; 1276 DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i", 1277 (int)(anchor-(const BYTE*)source), 0, (int)(ip-(const BYTE*)source)); 1278 goto _next_match; 1279 } 1280 } 1281 1282 /* Prepare next loop */ 1283 forwardH = LZ4_hashPosition(++ip, tableType); 1284 1285 } 1286 1287 _last_literals: 1288 /* Encode Last Literals */ 1289 { size_t lastRun = (size_t)(iend - anchor); 1290 if ( (outputDirective) && /* Check output buffer overflow */ 1291 (op + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > olimit)) { 1292 if (outputDirective == fillOutput) { 1293 /* adapt lastRun to fill 'dst' */ 1294 assert(olimit >= op); 1295 lastRun = (size_t)(olimit-op) - 1/*token*/; 1296 lastRun -= (lastRun + 256 - RUN_MASK) / 256; /*additional length tokens*/ 1297 } else { 1298 assert(outputDirective == limitedOutput); 1299 return 0; /* cannot compress within `dst` budget. Stored indexes in hash table are nonetheless fine */ 1300 } 1301 } 1302 DEBUGLOG(6, "Final literal run : %i literals", (int)lastRun); 1303 if (lastRun >= RUN_MASK) { 1304 size_t accumulator = lastRun - RUN_MASK; 1305 *op++ = RUN_MASK << ML_BITS; 1306 for(; accumulator >= 255 ; accumulator-=255) *op++ = 255; 1307 *op++ = (BYTE) accumulator; 1308 } else { 1309 *op++ = (BYTE)(lastRun<<ML_BITS); 1310 } 1311 LZ4_memcpy(op, anchor, lastRun); 1312 ip = anchor + lastRun; 1313 op += lastRun; 1314 } 1315 1316 if (outputDirective == fillOutput) { 1317 *inputConsumed = (int) (((const char*)ip)-source); 1318 } 1319 result = (int)(((char*)op) - dest); 1320 assert(result > 0); 1321 DEBUGLOG(5, "LZ4_compress_generic: compressed %i bytes into %i bytes", inputSize, result); 1322 return result; 1323 } 1324 1325 /** LZ4_compress_generic() : 1326 * inlined, to ensure branches are decided at compilation time; 1327 * takes care of src == (NULL, 0) 1328 * and forward the rest to LZ4_compress_generic_validated */ LZ4_compress_generic(LZ4_stream_t_internal * const cctx,const char * const src,char * const dst,const int srcSize,int * inputConsumed,const int dstCapacity,const limitedOutput_directive outputDirective,const tableType_t tableType,const dict_directive dictDirective,const dictIssue_directive dictIssue,const int acceleration)1329 LZ4_FORCE_INLINE int LZ4_compress_generic( 1330 LZ4_stream_t_internal* const cctx, 1331 const char* const src, 1332 char* const dst, 1333 const int srcSize, 1334 int *inputConsumed, /* only written when outputDirective == fillOutput */ 1335 const int dstCapacity, 1336 const limitedOutput_directive outputDirective, 1337 const tableType_t tableType, 1338 const dict_directive dictDirective, 1339 const dictIssue_directive dictIssue, 1340 const int acceleration) 1341 { 1342 DEBUGLOG(5, "LZ4_compress_generic: srcSize=%i, dstCapacity=%i", 1343 srcSize, dstCapacity); 1344 1345 if ((U32)srcSize > (U32)LZ4_MAX_INPUT_SIZE) { return 0; } /* Unsupported srcSize, too large (or negative) */ 1346 if (srcSize == 0) { /* src == NULL supported if srcSize == 0 */ 1347 if (outputDirective != notLimited && dstCapacity <= 0) return 0; /* no output, can't write anything */ 1348 DEBUGLOG(5, "Generating an empty block"); 1349 assert(outputDirective == notLimited || dstCapacity >= 1); 1350 assert(dst != NULL); 1351 dst[0] = 0; 1352 if (outputDirective == fillOutput) { 1353 assert (inputConsumed != NULL); 1354 *inputConsumed = 0; 1355 } 1356 return 1; 1357 } 1358 assert(src != NULL); 1359 1360 return LZ4_compress_generic_validated(cctx, src, dst, srcSize, 1361 inputConsumed, /* only written into if outputDirective == fillOutput */ 1362 dstCapacity, outputDirective, 1363 tableType, dictDirective, dictIssue, acceleration); 1364 } 1365 1366 LZ4_compress_fast_extState(void * state,const char * source,char * dest,int inputSize,int maxOutputSize,int acceleration)1367 int LZ4_compress_fast_extState(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration) 1368 { 1369 LZ4_stream_t_internal* const ctx = & LZ4_initStream(state, sizeof(LZ4_stream_t)) -> internal_donotuse; 1370 assert(ctx != NULL); 1371 if (acceleration < 1) acceleration = LZ4_ACCELERATION_DEFAULT; 1372 if (acceleration > LZ4_ACCELERATION_MAX) acceleration = LZ4_ACCELERATION_MAX; 1373 if (maxOutputSize >= LZ4_compressBound(inputSize)) { 1374 if (inputSize < LZ4_64Klimit) { 1375 return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, 0, notLimited, byU16, noDict, noDictIssue, acceleration); 1376 } else { 1377 const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)source > LZ4_DISTANCE_MAX)) ? byPtr : byU32; 1378 return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, 0, notLimited, tableType, noDict, noDictIssue, acceleration); 1379 } 1380 } else { 1381 if (inputSize < LZ4_64Klimit) { 1382 return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue, acceleration); 1383 } else { 1384 const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)source > LZ4_DISTANCE_MAX)) ? byPtr : byU32; 1385 return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, noDict, noDictIssue, acceleration); 1386 } 1387 } 1388 } 1389 1390 /** 1391 * LZ4_compress_fast_extState_fastReset() : 1392 * A variant of LZ4_compress_fast_extState(). 1393 * 1394 * Using this variant avoids an expensive initialization step. It is only safe 1395 * to call if the state buffer is known to be correctly initialized already 1396 * (see comment in lz4.h on LZ4_resetStream_fast() for a definition of 1397 * "correctly initialized"). 1398 */ LZ4_compress_fast_extState_fastReset(void * state,const char * src,char * dst,int srcSize,int dstCapacity,int acceleration)1399 int LZ4_compress_fast_extState_fastReset(void* state, const char* src, char* dst, int srcSize, int dstCapacity, int acceleration) 1400 { 1401 LZ4_stream_t_internal* const ctx = &((LZ4_stream_t*)state)->internal_donotuse; 1402 if (acceleration < 1) acceleration = LZ4_ACCELERATION_DEFAULT; 1403 if (acceleration > LZ4_ACCELERATION_MAX) acceleration = LZ4_ACCELERATION_MAX; 1404 assert(ctx != NULL); 1405 1406 if (dstCapacity >= LZ4_compressBound(srcSize)) { 1407 if (srcSize < LZ4_64Klimit) { 1408 const tableType_t tableType = byU16; 1409 LZ4_prepareTable(ctx, srcSize, tableType); 1410 if (ctx->currentOffset) { 1411 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, 0, notLimited, tableType, noDict, dictSmall, acceleration); 1412 } else { 1413 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, 0, notLimited, tableType, noDict, noDictIssue, acceleration); 1414 } 1415 } else { 1416 const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)src > LZ4_DISTANCE_MAX)) ? byPtr : byU32; 1417 LZ4_prepareTable(ctx, srcSize, tableType); 1418 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, 0, notLimited, tableType, noDict, noDictIssue, acceleration); 1419 } 1420 } else { 1421 if (srcSize < LZ4_64Klimit) { 1422 const tableType_t tableType = byU16; 1423 LZ4_prepareTable(ctx, srcSize, tableType); 1424 if (ctx->currentOffset) { 1425 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, dstCapacity, limitedOutput, tableType, noDict, dictSmall, acceleration); 1426 } else { 1427 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, dstCapacity, limitedOutput, tableType, noDict, noDictIssue, acceleration); 1428 } 1429 } else { 1430 const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)src > LZ4_DISTANCE_MAX)) ? byPtr : byU32; 1431 LZ4_prepareTable(ctx, srcSize, tableType); 1432 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, dstCapacity, limitedOutput, tableType, noDict, noDictIssue, acceleration); 1433 } 1434 } 1435 } 1436 1437 LZ4_compress_fast(const char * src,char * dest,int srcSize,int dstCapacity,int acceleration)1438 int LZ4_compress_fast(const char* src, char* dest, int srcSize, int dstCapacity, int acceleration) 1439 { 1440 int result; 1441 #if (LZ4_HEAPMODE) 1442 LZ4_stream_t* const ctxPtr = (LZ4_stream_t*)ALLOC(sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */ 1443 if (ctxPtr == NULL) return 0; 1444 #else 1445 LZ4_stream_t ctx; 1446 LZ4_stream_t* const ctxPtr = &ctx; 1447 #endif 1448 result = LZ4_compress_fast_extState(ctxPtr, src, dest, srcSize, dstCapacity, acceleration); 1449 1450 #if (LZ4_HEAPMODE) 1451 FREEMEM(ctxPtr); 1452 #endif 1453 return result; 1454 } 1455 1456 LZ4_compress_default(const char * src,char * dst,int srcSize,int dstCapacity)1457 int LZ4_compress_default(const char* src, char* dst, int srcSize, int dstCapacity) 1458 { 1459 return LZ4_compress_fast(src, dst, srcSize, dstCapacity, 1); 1460 } 1461 1462 1463 /* Note!: This function leaves the stream in an unclean/broken state! 1464 * It is not safe to subsequently use the same state with a _fastReset() or 1465 * _continue() call without resetting it. */ LZ4_compress_destSize_extState(LZ4_stream_t * state,const char * src,char * dst,int * srcSizePtr,int targetDstSize)1466 static int LZ4_compress_destSize_extState (LZ4_stream_t* state, const char* src, char* dst, int* srcSizePtr, int targetDstSize) 1467 { 1468 void* const s = LZ4_initStream(state, sizeof (*state)); 1469 assert(s != NULL); (void)s; 1470 1471 if (targetDstSize >= LZ4_compressBound(*srcSizePtr)) { /* compression success is guaranteed */ 1472 return LZ4_compress_fast_extState(state, src, dst, *srcSizePtr, targetDstSize, 1); 1473 } else { 1474 if (*srcSizePtr < LZ4_64Klimit) { 1475 return LZ4_compress_generic(&state->internal_donotuse, src, dst, *srcSizePtr, srcSizePtr, targetDstSize, fillOutput, byU16, noDict, noDictIssue, 1); 1476 } else { 1477 tableType_t const addrMode = ((sizeof(void*)==4) && ((uptrval)src > LZ4_DISTANCE_MAX)) ? byPtr : byU32; 1478 return LZ4_compress_generic(&state->internal_donotuse, src, dst, *srcSizePtr, srcSizePtr, targetDstSize, fillOutput, addrMode, noDict, noDictIssue, 1); 1479 } } 1480 } 1481 1482 LZ4_compress_destSize(const char * src,char * dst,int * srcSizePtr,int targetDstSize)1483 int LZ4_compress_destSize(const char* src, char* dst, int* srcSizePtr, int targetDstSize) 1484 { 1485 #if (LZ4_HEAPMODE) 1486 LZ4_stream_t* const ctx = (LZ4_stream_t*)ALLOC(sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */ 1487 if (ctx == NULL) return 0; 1488 #else 1489 LZ4_stream_t ctxBody; 1490 LZ4_stream_t* const ctx = &ctxBody; 1491 #endif 1492 1493 int result = LZ4_compress_destSize_extState(ctx, src, dst, srcSizePtr, targetDstSize); 1494 1495 #if (LZ4_HEAPMODE) 1496 FREEMEM(ctx); 1497 #endif 1498 return result; 1499 } 1500 1501 1502 1503 /*-****************************** 1504 * Streaming functions 1505 ********************************/ 1506 1507 #if !defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION) LZ4_createStream(void)1508 LZ4_stream_t* LZ4_createStream(void) 1509 { 1510 LZ4_stream_t* const lz4s = (LZ4_stream_t*)ALLOC(sizeof(LZ4_stream_t)); 1511 LZ4_STATIC_ASSERT(sizeof(LZ4_stream_t) >= sizeof(LZ4_stream_t_internal)); 1512 DEBUGLOG(4, "LZ4_createStream %p", lz4s); 1513 if (lz4s == NULL) return NULL; 1514 LZ4_initStream(lz4s, sizeof(*lz4s)); 1515 return lz4s; 1516 } 1517 #endif 1518 LZ4_stream_t_alignment(void)1519 static size_t LZ4_stream_t_alignment(void) 1520 { 1521 #if LZ4_ALIGN_TEST 1522 typedef struct { char c; LZ4_stream_t t; } t_a; 1523 return sizeof(t_a) - sizeof(LZ4_stream_t); 1524 #else 1525 return 1; /* effectively disabled */ 1526 #endif 1527 } 1528 LZ4_initStream(void * buffer,size_t size)1529 LZ4_stream_t* LZ4_initStream (void* buffer, size_t size) 1530 { 1531 DEBUGLOG(5, "LZ4_initStream"); 1532 if (buffer == NULL) { return NULL; } 1533 if (size < sizeof(LZ4_stream_t)) { return NULL; } 1534 if (!LZ4_isAligned(buffer, LZ4_stream_t_alignment())) return NULL; 1535 MEM_INIT(buffer, 0, sizeof(LZ4_stream_t_internal)); 1536 return (LZ4_stream_t*)buffer; 1537 } 1538 1539 /* resetStream is now deprecated, 1540 * prefer initStream() which is more general */ LZ4_resetStream(LZ4_stream_t * LZ4_stream)1541 void LZ4_resetStream (LZ4_stream_t* LZ4_stream) 1542 { 1543 DEBUGLOG(5, "LZ4_resetStream (ctx:%p)", LZ4_stream); 1544 MEM_INIT(LZ4_stream, 0, sizeof(LZ4_stream_t_internal)); 1545 } 1546 LZ4_resetStream_fast(LZ4_stream_t * ctx)1547 void LZ4_resetStream_fast(LZ4_stream_t* ctx) { 1548 LZ4_prepareTable(&(ctx->internal_donotuse), 0, byU32); 1549 } 1550 1551 #if !defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION) LZ4_freeStream(LZ4_stream_t * LZ4_stream)1552 int LZ4_freeStream (LZ4_stream_t* LZ4_stream) 1553 { 1554 if (!LZ4_stream) return 0; /* support free on NULL */ 1555 DEBUGLOG(5, "LZ4_freeStream %p", LZ4_stream); 1556 FREEMEM(LZ4_stream); 1557 return (0); 1558 } 1559 #endif 1560 1561 1562 #define HASH_UNIT sizeof(reg_t) LZ4_loadDict(LZ4_stream_t * LZ4_dict,const char * dictionary,int dictSize)1563 int LZ4_loadDict (LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize) 1564 { 1565 LZ4_stream_t_internal* const dict = &LZ4_dict->internal_donotuse; 1566 const tableType_t tableType = byU32; 1567 const BYTE* p = (const BYTE*)dictionary; 1568 const BYTE* const dictEnd = p + dictSize; 1569 U32 idx32; 1570 1571 DEBUGLOG(4, "LZ4_loadDict (%i bytes from %p into %p)", dictSize, dictionary, LZ4_dict); 1572 1573 /* It's necessary to reset the context, 1574 * and not just continue it with prepareTable() 1575 * to avoid any risk of generating overflowing matchIndex 1576 * when compressing using this dictionary */ 1577 LZ4_resetStream(LZ4_dict); 1578 1579 /* We always increment the offset by 64 KB, since, if the dict is longer, 1580 * we truncate it to the last 64k, and if it's shorter, we still want to 1581 * advance by a whole window length so we can provide the guarantee that 1582 * there are only valid offsets in the window, which allows an optimization 1583 * in LZ4_compress_fast_continue() where it uses noDictIssue even when the 1584 * dictionary isn't a full 64k. */ 1585 dict->currentOffset += 64 KB; 1586 1587 if (dictSize < (int)HASH_UNIT) { 1588 return 0; 1589 } 1590 1591 if ((dictEnd - p) > 64 KB) p = dictEnd - 64 KB; 1592 dict->dictionary = p; 1593 dict->dictSize = (U32)(dictEnd - p); 1594 dict->tableType = (U32)tableType; 1595 idx32 = dict->currentOffset - dict->dictSize; 1596 1597 while (p <= dictEnd-HASH_UNIT) { 1598 U32 const h = LZ4_hashPosition(p, tableType); 1599 LZ4_putIndexOnHash(idx32, h, dict->hashTable, tableType); 1600 p+=3; idx32+=3; 1601 } 1602 1603 return (int)dict->dictSize; 1604 } 1605 LZ4_attach_dictionary(LZ4_stream_t * workingStream,const LZ4_stream_t * dictionaryStream)1606 void LZ4_attach_dictionary(LZ4_stream_t* workingStream, const LZ4_stream_t* dictionaryStream) 1607 { 1608 const LZ4_stream_t_internal* dictCtx = (dictionaryStream == NULL) ? NULL : 1609 &(dictionaryStream->internal_donotuse); 1610 1611 DEBUGLOG(4, "LZ4_attach_dictionary (%p, %p, size %u)", 1612 workingStream, dictionaryStream, 1613 dictCtx != NULL ? dictCtx->dictSize : 0); 1614 1615 if (dictCtx != NULL) { 1616 /* If the current offset is zero, we will never look in the 1617 * external dictionary context, since there is no value a table 1618 * entry can take that indicate a miss. In that case, we need 1619 * to bump the offset to something non-zero. 1620 */ 1621 if (workingStream->internal_donotuse.currentOffset == 0) { 1622 workingStream->internal_donotuse.currentOffset = 64 KB; 1623 } 1624 1625 /* Don't actually attach an empty dictionary. 1626 */ 1627 if (dictCtx->dictSize == 0) { 1628 dictCtx = NULL; 1629 } 1630 } 1631 workingStream->internal_donotuse.dictCtx = dictCtx; 1632 } 1633 1634 LZ4_renormDictT(LZ4_stream_t_internal * LZ4_dict,int nextSize)1635 static void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, int nextSize) 1636 { 1637 assert(nextSize >= 0); 1638 if (LZ4_dict->currentOffset + (unsigned)nextSize > 0x80000000) { /* potential ptrdiff_t overflow (32-bits mode) */ 1639 /* rescale hash table */ 1640 U32 const delta = LZ4_dict->currentOffset - 64 KB; 1641 const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize; 1642 int i; 1643 DEBUGLOG(4, "LZ4_renormDictT"); 1644 for (i=0; i<LZ4_HASH_SIZE_U32; i++) { 1645 if (LZ4_dict->hashTable[i] < delta) LZ4_dict->hashTable[i]=0; 1646 else LZ4_dict->hashTable[i] -= delta; 1647 } 1648 LZ4_dict->currentOffset = 64 KB; 1649 if (LZ4_dict->dictSize > 64 KB) LZ4_dict->dictSize = 64 KB; 1650 LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize; 1651 } 1652 } 1653 1654 LZ4_compress_fast_continue(LZ4_stream_t * LZ4_stream,const char * source,char * dest,int inputSize,int maxOutputSize,int acceleration)1655 int LZ4_compress_fast_continue (LZ4_stream_t* LZ4_stream, 1656 const char* source, char* dest, 1657 int inputSize, int maxOutputSize, 1658 int acceleration) 1659 { 1660 const tableType_t tableType = byU32; 1661 LZ4_stream_t_internal* const streamPtr = &LZ4_stream->internal_donotuse; 1662 const char* dictEnd = streamPtr->dictSize ? (const char*)streamPtr->dictionary + streamPtr->dictSize : NULL; 1663 1664 DEBUGLOG(5, "LZ4_compress_fast_continue (inputSize=%i, dictSize=%u)", inputSize, streamPtr->dictSize); 1665 1666 LZ4_renormDictT(streamPtr, inputSize); /* fix index overflow */ 1667 if (acceleration < 1) acceleration = LZ4_ACCELERATION_DEFAULT; 1668 if (acceleration > LZ4_ACCELERATION_MAX) acceleration = LZ4_ACCELERATION_MAX; 1669 1670 /* invalidate tiny dictionaries */ 1671 if ( (streamPtr->dictSize < 4) /* tiny dictionary : not enough for a hash */ 1672 && (dictEnd != source) /* prefix mode */ 1673 && (inputSize > 0) /* tolerance : don't lose history, in case next invocation would use prefix mode */ 1674 && (streamPtr->dictCtx == NULL) /* usingDictCtx */ 1675 ) { 1676 DEBUGLOG(5, "LZ4_compress_fast_continue: dictSize(%u) at addr:%p is too small", streamPtr->dictSize, streamPtr->dictionary); 1677 /* remove dictionary existence from history, to employ faster prefix mode */ 1678 streamPtr->dictSize = 0; 1679 streamPtr->dictionary = (const BYTE*)source; 1680 dictEnd = source; 1681 } 1682 1683 /* Check overlapping input/dictionary space */ 1684 { const char* const sourceEnd = source + inputSize; 1685 if ((sourceEnd > (const char*)streamPtr->dictionary) && (sourceEnd < dictEnd)) { 1686 streamPtr->dictSize = (U32)(dictEnd - sourceEnd); 1687 if (streamPtr->dictSize > 64 KB) streamPtr->dictSize = 64 KB; 1688 if (streamPtr->dictSize < 4) streamPtr->dictSize = 0; 1689 streamPtr->dictionary = (const BYTE*)dictEnd - streamPtr->dictSize; 1690 } 1691 } 1692 1693 /* prefix mode : source data follows dictionary */ 1694 if (dictEnd == source) { 1695 if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) 1696 return LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, withPrefix64k, dictSmall, acceleration); 1697 else 1698 return LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, withPrefix64k, noDictIssue, acceleration); 1699 } 1700 1701 /* external dictionary mode */ 1702 { int result; 1703 if (streamPtr->dictCtx) { 1704 /* We depend here on the fact that dictCtx'es (produced by 1705 * LZ4_loadDict) guarantee that their tables contain no references 1706 * to offsets between dictCtx->currentOffset - 64 KB and 1707 * dictCtx->currentOffset - dictCtx->dictSize. This makes it safe 1708 * to use noDictIssue even when the dict isn't a full 64 KB. 1709 */ 1710 if (inputSize > 4 KB) { 1711 /* For compressing large blobs, it is faster to pay the setup 1712 * cost to copy the dictionary's tables into the active context, 1713 * so that the compression loop is only looking into one table. 1714 */ 1715 LZ4_memcpy(streamPtr, streamPtr->dictCtx, sizeof(*streamPtr)); 1716 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingExtDict, noDictIssue, acceleration); 1717 } else { 1718 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingDictCtx, noDictIssue, acceleration); 1719 } 1720 } else { /* small data <= 4 KB */ 1721 if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) { 1722 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingExtDict, dictSmall, acceleration); 1723 } else { 1724 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingExtDict, noDictIssue, acceleration); 1725 } 1726 } 1727 streamPtr->dictionary = (const BYTE*)source; 1728 streamPtr->dictSize = (U32)inputSize; 1729 return result; 1730 } 1731 } 1732 1733 1734 /* Hidden debug function, to force-test external dictionary mode */ LZ4_compress_forceExtDict(LZ4_stream_t * LZ4_dict,const char * source,char * dest,int srcSize)1735 int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int srcSize) 1736 { 1737 LZ4_stream_t_internal* const streamPtr = &LZ4_dict->internal_donotuse; 1738 int result; 1739 1740 LZ4_renormDictT(streamPtr, srcSize); 1741 1742 if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) { 1743 result = LZ4_compress_generic(streamPtr, source, dest, srcSize, NULL, 0, notLimited, byU32, usingExtDict, dictSmall, 1); 1744 } else { 1745 result = LZ4_compress_generic(streamPtr, source, dest, srcSize, NULL, 0, notLimited, byU32, usingExtDict, noDictIssue, 1); 1746 } 1747 1748 streamPtr->dictionary = (const BYTE*)source; 1749 streamPtr->dictSize = (U32)srcSize; 1750 1751 return result; 1752 } 1753 1754 1755 /*! LZ4_saveDict() : 1756 * If previously compressed data block is not guaranteed to remain available at its memory location, 1757 * save it into a safer place (char* safeBuffer). 1758 * Note : no need to call LZ4_loadDict() afterwards, dictionary is immediately usable, 1759 * one can therefore call LZ4_compress_fast_continue() right after. 1760 * @return : saved dictionary size in bytes (necessarily <= dictSize), or 0 if error. 1761 */ LZ4_saveDict(LZ4_stream_t * LZ4_dict,char * safeBuffer,int dictSize)1762 int LZ4_saveDict (LZ4_stream_t* LZ4_dict, char* safeBuffer, int dictSize) 1763 { 1764 LZ4_stream_t_internal* const dict = &LZ4_dict->internal_donotuse; 1765 1766 DEBUGLOG(5, "LZ4_saveDict : dictSize=%i, safeBuffer=%p", dictSize, safeBuffer); 1767 1768 if ((U32)dictSize > 64 KB) { dictSize = 64 KB; } /* useless to define a dictionary > 64 KB */ 1769 if ((U32)dictSize > dict->dictSize) { dictSize = (int)dict->dictSize; } 1770 1771 if (safeBuffer == NULL) assert(dictSize == 0); 1772 if (dictSize > 0) { 1773 const BYTE* const previousDictEnd = dict->dictionary + dict->dictSize; 1774 assert(dict->dictionary); 1775 LZ4_memmove(safeBuffer, previousDictEnd - dictSize, (size_t)dictSize); 1776 } 1777 1778 dict->dictionary = (const BYTE*)safeBuffer; 1779 dict->dictSize = (U32)dictSize; 1780 1781 return dictSize; 1782 } 1783 1784 1785 1786 /*-******************************* 1787 * Decompression functions 1788 ********************************/ 1789 1790 typedef enum { decode_full_block = 0, partial_decode = 1 } earlyEnd_directive; 1791 1792 #undef MIN 1793 #define MIN(a,b) ( (a) < (b) ? (a) : (b) ) 1794 1795 1796 /* variant for decompress_unsafe() 1797 * does not know end of input 1798 * presumes input is well formed 1799 * note : will consume at least one byte */ read_long_length_no_check(const BYTE ** pp)1800 static size_t read_long_length_no_check(const BYTE** pp) 1801 { 1802 size_t b, l = 0; 1803 do { b = **pp; (*pp)++; l += b; } while (b==255); 1804 DEBUGLOG(6, "read_long_length_no_check: +length=%zu using %zu input bytes", l, l/255 + 1) 1805 return l; 1806 } 1807 1808 /* core decoder variant for LZ4_decompress_fast*() 1809 * for legacy support only : these entry points are deprecated. 1810 * - Presumes input is correctly formed (no defense vs malformed inputs) 1811 * - Does not know input size (presume input buffer is "large enough") 1812 * - Decompress a full block (only) 1813 * @return : nb of bytes read from input. 1814 * Note : this variant is not optimized for speed, just for maintenance. 1815 * the goal is to remove support of decompress_fast*() variants by v2.0 1816 **/ 1817 LZ4_FORCE_INLINE int LZ4_decompress_unsafe_generic(const BYTE * const istart,BYTE * const ostart,int decompressedSize,size_t prefixSize,const BYTE * const dictStart,const size_t dictSize)1818 LZ4_decompress_unsafe_generic( 1819 const BYTE* const istart, 1820 BYTE* const ostart, 1821 int decompressedSize, 1822 1823 size_t prefixSize, 1824 const BYTE* const dictStart, /* only if dict==usingExtDict */ 1825 const size_t dictSize /* note: =0 if dictStart==NULL */ 1826 ) 1827 { 1828 const BYTE* ip = istart; 1829 BYTE* op = (BYTE*)ostart; 1830 BYTE* const oend = ostart + decompressedSize; 1831 const BYTE* const prefixStart = ostart - prefixSize; 1832 1833 DEBUGLOG(5, "LZ4_decompress_unsafe_generic"); 1834 if (dictStart == NULL) assert(dictSize == 0); 1835 1836 while (1) { 1837 /* start new sequence */ 1838 unsigned token = *ip++; 1839 1840 /* literals */ 1841 { size_t ll = token >> ML_BITS; 1842 if (ll==15) { 1843 /* long literal length */ 1844 ll += read_long_length_no_check(&ip); 1845 } 1846 if ((size_t)(oend-op) < ll) return -1; /* output buffer overflow */ 1847 LZ4_memmove(op, ip, ll); /* support in-place decompression */ 1848 op += ll; 1849 ip += ll; 1850 if ((size_t)(oend-op) < MFLIMIT) { 1851 if (op==oend) break; /* end of block */ 1852 DEBUGLOG(5, "invalid: literals end at distance %zi from end of block", oend-op); 1853 /* incorrect end of block : 1854 * last match must start at least MFLIMIT==12 bytes before end of output block */ 1855 return -1; 1856 } } 1857 1858 /* match */ 1859 { size_t ml = token & 15; 1860 size_t const offset = LZ4_readLE16(ip); 1861 ip+=2; 1862 1863 if (ml==15) { 1864 /* long literal length */ 1865 ml += read_long_length_no_check(&ip); 1866 } 1867 ml += MINMATCH; 1868 1869 if ((size_t)(oend-op) < ml) return -1; /* output buffer overflow */ 1870 1871 { const BYTE* match = op - offset; 1872 1873 /* out of range */ 1874 if (offset > (size_t)(op - prefixStart) + dictSize) { 1875 DEBUGLOG(6, "offset out of range"); 1876 return -1; 1877 } 1878 1879 /* check special case : extDict */ 1880 if (offset > (size_t)(op - prefixStart)) { 1881 /* extDict scenario */ 1882 const BYTE* const dictEnd = dictStart + dictSize; 1883 const BYTE* extMatch = dictEnd - (offset - (size_t)(op-prefixStart)); 1884 size_t const extml = (size_t)(dictEnd - extMatch); 1885 if (extml > ml) { 1886 /* match entirely within extDict */ 1887 LZ4_memmove(op, extMatch, ml); 1888 op += ml; 1889 ml = 0; 1890 } else { 1891 /* match split between extDict & prefix */ 1892 LZ4_memmove(op, extMatch, extml); 1893 op += extml; 1894 ml -= extml; 1895 } 1896 match = prefixStart; 1897 } 1898 1899 /* match copy - slow variant, supporting overlap copy */ 1900 { size_t u; 1901 for (u=0; u<ml; u++) { 1902 op[u] = match[u]; 1903 } } } 1904 op += ml; 1905 if ((size_t)(oend-op) < LASTLITERALS) { 1906 DEBUGLOG(5, "invalid: match ends at distance %zi from end of block", oend-op); 1907 /* incorrect end of block : 1908 * last match must stop at least LASTLITERALS==5 bytes before end of output block */ 1909 return -1; 1910 } 1911 } /* match */ 1912 } /* main loop */ 1913 return (int)(ip - istart); 1914 } 1915 1916 1917 /* Read the variable-length literal or match length. 1918 * 1919 * @ip : input pointer 1920 * @ilimit : position after which if length is not decoded, the input is necessarily corrupted. 1921 * @initial_check - check ip >= ipmax before start of loop. Returns initial_error if so. 1922 * @error (output) - error code. Must be set to 0 before call. 1923 **/ 1924 typedef size_t Rvl_t; 1925 static const Rvl_t rvl_error = (Rvl_t)(-1); 1926 LZ4_FORCE_INLINE Rvl_t read_variable_length(const BYTE ** ip,const BYTE * ilimit,int initial_check)1927 read_variable_length(const BYTE** ip, const BYTE* ilimit, 1928 int initial_check) 1929 { 1930 Rvl_t s, length = 0; 1931 assert(ip != NULL); 1932 assert(*ip != NULL); 1933 assert(ilimit != NULL); 1934 if (initial_check && unlikely((*ip) >= ilimit)) { /* read limit reached */ 1935 return rvl_error; 1936 } 1937 do { 1938 s = **ip; 1939 (*ip)++; 1940 length += s; 1941 if (unlikely((*ip) > ilimit)) { /* read limit reached */ 1942 return rvl_error; 1943 } 1944 /* accumulator overflow detection (32-bit mode only) */ 1945 if ((sizeof(length)<8) && unlikely(length > ((Rvl_t)(-1)/2)) ) { 1946 return rvl_error; 1947 } 1948 } while (s==255); 1949 1950 return length; 1951 } 1952 1953 /*! LZ4_decompress_generic() : 1954 * This generic decompression function covers all use cases. 1955 * It shall be instantiated several times, using different sets of directives. 1956 * Note that it is important for performance that this function really get inlined, 1957 * in order to remove useless branches during compilation optimization. 1958 */ 1959 LZ4_FORCE_INLINE int LZ4_decompress_generic(const char * const src,char * const dst,int srcSize,int outputSize,earlyEnd_directive partialDecoding,dict_directive dict,const BYTE * const lowPrefix,const BYTE * const dictStart,const size_t dictSize)1960 LZ4_decompress_generic( 1961 const char* const src, 1962 char* const dst, 1963 int srcSize, 1964 int outputSize, /* If endOnInput==endOnInputSize, this value is `dstCapacity` */ 1965 1966 earlyEnd_directive partialDecoding, /* full, partial */ 1967 dict_directive dict, /* noDict, withPrefix64k, usingExtDict */ 1968 const BYTE* const lowPrefix, /* always <= dst, == dst when no prefix */ 1969 const BYTE* const dictStart, /* only if dict==usingExtDict */ 1970 const size_t dictSize /* note : = 0 if noDict */ 1971 ) 1972 { 1973 if ((src == NULL) || (outputSize < 0)) { return -1; } 1974 1975 { const BYTE* ip = (const BYTE*) src; 1976 const BYTE* const iend = ip + srcSize; 1977 1978 BYTE* op = (BYTE*) dst; 1979 BYTE* const oend = op + outputSize; 1980 BYTE* cpy; 1981 1982 const BYTE* const dictEnd = (dictStart == NULL) ? NULL : dictStart + dictSize; 1983 1984 const int checkOffset = (dictSize < (int)(64 KB)); 1985 1986 1987 /* Set up the "end" pointers for the shortcut. */ 1988 const BYTE* const shortiend = iend - 14 /*maxLL*/ - 2 /*offset*/; 1989 const BYTE* const shortoend = oend - 14 /*maxLL*/ - 18 /*maxML*/; 1990 1991 const BYTE* match; 1992 size_t offset; 1993 unsigned token; 1994 size_t length; 1995 1996 1997 DEBUGLOG(5, "LZ4_decompress_generic (srcSize:%i, dstSize:%i)", srcSize, outputSize); 1998 1999 /* Special cases */ 2000 assert(lowPrefix <= op); 2001 if (unlikely(outputSize==0)) { 2002 /* Empty output buffer */ 2003 if (partialDecoding) return 0; 2004 return ((srcSize==1) && (*ip==0)) ? 0 : -1; 2005 } 2006 if (unlikely(srcSize==0)) { return -1; } 2007 2008 /* LZ4_FAST_DEC_LOOP: 2009 * designed for modern OoO performance cpus, 2010 * where copying reliably 32-bytes is preferable to an unpredictable branch. 2011 * note : fast loop may show a regression for some client arm chips. */ 2012 #if LZ4_FAST_DEC_LOOP 2013 if ((oend - op) < FASTLOOP_SAFE_DISTANCE) { 2014 DEBUGLOG(6, "skip fast decode loop"); 2015 goto safe_decode; 2016 } 2017 2018 /* Fast loop : decode sequences as long as output < oend-FASTLOOP_SAFE_DISTANCE */ 2019 DEBUGLOG(6, "using fast decode loop"); 2020 while (1) { 2021 /* Main fastloop assertion: We can always wildcopy FASTLOOP_SAFE_DISTANCE */ 2022 assert(oend - op >= FASTLOOP_SAFE_DISTANCE); 2023 assert(ip < iend); 2024 token = *ip++; 2025 length = token >> ML_BITS; /* literal length */ 2026 2027 /* decode literal length */ 2028 if (length == RUN_MASK) { 2029 size_t const addl = read_variable_length(&ip, iend-RUN_MASK, 1); 2030 if (addl == rvl_error) { 2031 DEBUGLOG(6, "error reading long literal length"); 2032 goto _output_error; 2033 } 2034 length += addl; 2035 if (unlikely((uptrval)(op)+length<(uptrval)(op))) { goto _output_error; } /* overflow detection */ 2036 if (unlikely((uptrval)(ip)+length<(uptrval)(ip))) { goto _output_error; } /* overflow detection */ 2037 2038 /* copy literals */ 2039 LZ4_STATIC_ASSERT(MFLIMIT >= WILDCOPYLENGTH); 2040 if ((op+length>oend-32) || (ip+length>iend-32)) { goto safe_literal_copy; } 2041 LZ4_wildCopy32(op, ip, op+length); 2042 ip += length; op += length; 2043 } else if (ip <= iend-(16 + 1/*max lit + offset + nextToken*/)) { 2044 /* We don't need to check oend, since we check it once for each loop below */ 2045 DEBUGLOG(7, "copy %u bytes in a 16-bytes stripe", (unsigned)length); 2046 /* Literals can only be <= 14, but hope compilers optimize better when copy by a register size */ 2047 LZ4_memcpy(op, ip, 16); 2048 ip += length; op += length; 2049 } else { 2050 goto safe_literal_copy; 2051 } 2052 2053 /* get offset */ 2054 offset = LZ4_readLE16(ip); ip+=2; 2055 DEBUGLOG(6, " offset = %zu", offset); 2056 match = op - offset; 2057 assert(match <= op); /* overflow check */ 2058 2059 /* get matchlength */ 2060 length = token & ML_MASK; 2061 2062 if (length == ML_MASK) { 2063 size_t const addl = read_variable_length(&ip, iend - LASTLITERALS + 1, 0); 2064 if (addl == rvl_error) { 2065 DEBUGLOG(6, "error reading long match length"); 2066 goto _output_error; 2067 } 2068 length += addl; 2069 length += MINMATCH; 2070 if (unlikely((uptrval)(op)+length<(uptrval)op)) { goto _output_error; } /* overflow detection */ 2071 if (op + length >= oend - FASTLOOP_SAFE_DISTANCE) { 2072 goto safe_match_copy; 2073 } 2074 } else { 2075 length += MINMATCH; 2076 if (op + length >= oend - FASTLOOP_SAFE_DISTANCE) { 2077 goto safe_match_copy; 2078 } 2079 2080 /* Fastpath check: skip LZ4_wildCopy32 when true */ 2081 if ((dict == withPrefix64k) || (match >= lowPrefix)) { 2082 if (offset >= 8) { 2083 assert(match >= lowPrefix); 2084 assert(match <= op); 2085 assert(op + 18 <= oend); 2086 2087 LZ4_memcpy(op, match, 8); 2088 LZ4_memcpy(op+8, match+8, 8); 2089 LZ4_memcpy(op+16, match+16, 2); 2090 op += length; 2091 continue; 2092 } } } 2093 2094 if ( checkOffset && (unlikely(match + dictSize < lowPrefix)) ) { 2095 DEBUGLOG(6, "Error : pos=%zi, offset=%zi => outside buffers", op-lowPrefix, op-match); 2096 goto _output_error; 2097 } 2098 /* match starting within external dictionary */ 2099 if ((dict==usingExtDict) && (match < lowPrefix)) { 2100 assert(dictEnd != NULL); 2101 if (unlikely(op+length > oend-LASTLITERALS)) { 2102 if (partialDecoding) { 2103 DEBUGLOG(7, "partialDecoding: dictionary match, close to dstEnd"); 2104 length = MIN(length, (size_t)(oend-op)); 2105 } else { 2106 DEBUGLOG(6, "end-of-block condition violated") 2107 goto _output_error; 2108 } } 2109 2110 if (length <= (size_t)(lowPrefix-match)) { 2111 /* match fits entirely within external dictionary : just copy */ 2112 LZ4_memmove(op, dictEnd - (lowPrefix-match), length); 2113 op += length; 2114 } else { 2115 /* match stretches into both external dictionary and current block */ 2116 size_t const copySize = (size_t)(lowPrefix - match); 2117 size_t const restSize = length - copySize; 2118 LZ4_memcpy(op, dictEnd - copySize, copySize); 2119 op += copySize; 2120 if (restSize > (size_t)(op - lowPrefix)) { /* overlap copy */ 2121 BYTE* const endOfMatch = op + restSize; 2122 const BYTE* copyFrom = lowPrefix; 2123 while (op < endOfMatch) { *op++ = *copyFrom++; } 2124 } else { 2125 LZ4_memcpy(op, lowPrefix, restSize); 2126 op += restSize; 2127 } } 2128 continue; 2129 } 2130 2131 /* copy match within block */ 2132 cpy = op + length; 2133 2134 assert((op <= oend) && (oend-op >= 32)); 2135 if (unlikely(offset<16)) { 2136 LZ4_memcpy_using_offset(op, match, cpy, offset); 2137 } else { 2138 LZ4_wildCopy32(op, match, cpy); 2139 } 2140 2141 op = cpy; /* wildcopy correction */ 2142 } 2143 safe_decode: 2144 #endif 2145 2146 /* Main Loop : decode remaining sequences where output < FASTLOOP_SAFE_DISTANCE */ 2147 DEBUGLOG(6, "using safe decode loop"); 2148 while (1) { 2149 assert(ip < iend); 2150 token = *ip++; 2151 length = token >> ML_BITS; /* literal length */ 2152 2153 /* A two-stage shortcut for the most common case: 2154 * 1) If the literal length is 0..14, and there is enough space, 2155 * enter the shortcut and copy 16 bytes on behalf of the literals 2156 * (in the fast mode, only 8 bytes can be safely copied this way). 2157 * 2) Further if the match length is 4..18, copy 18 bytes in a similar 2158 * manner; but we ensure that there's enough space in the output for 2159 * those 18 bytes earlier, upon entering the shortcut (in other words, 2160 * there is a combined check for both stages). 2161 */ 2162 if ( (length != RUN_MASK) 2163 /* strictly "less than" on input, to re-enter the loop with at least one byte */ 2164 && likely((ip < shortiend) & (op <= shortoend)) ) { 2165 /* Copy the literals */ 2166 LZ4_memcpy(op, ip, 16); 2167 op += length; ip += length; 2168 2169 /* The second stage: prepare for match copying, decode full info. 2170 * If it doesn't work out, the info won't be wasted. */ 2171 length = token & ML_MASK; /* match length */ 2172 offset = LZ4_readLE16(ip); ip += 2; 2173 match = op - offset; 2174 assert(match <= op); /* check overflow */ 2175 2176 /* Do not deal with overlapping matches. */ 2177 if ( (length != ML_MASK) 2178 && (offset >= 8) 2179 && (dict==withPrefix64k || match >= lowPrefix) ) { 2180 /* Copy the match. */ 2181 LZ4_memcpy(op + 0, match + 0, 8); 2182 LZ4_memcpy(op + 8, match + 8, 8); 2183 LZ4_memcpy(op +16, match +16, 2); 2184 op += length + MINMATCH; 2185 /* Both stages worked, load the next token. */ 2186 continue; 2187 } 2188 2189 /* The second stage didn't work out, but the info is ready. 2190 * Propel it right to the point of match copying. */ 2191 goto _copy_match; 2192 } 2193 2194 /* decode literal length */ 2195 if (length == RUN_MASK) { 2196 size_t const addl = read_variable_length(&ip, iend-RUN_MASK, 1); 2197 if (addl == rvl_error) { goto _output_error; } 2198 length += addl; 2199 if (unlikely((uptrval)(op)+length<(uptrval)(op))) { goto _output_error; } /* overflow detection */ 2200 if (unlikely((uptrval)(ip)+length<(uptrval)(ip))) { goto _output_error; } /* overflow detection */ 2201 } 2202 2203 #if LZ4_FAST_DEC_LOOP 2204 safe_literal_copy: 2205 #endif 2206 /* copy literals */ 2207 cpy = op+length; 2208 2209 LZ4_STATIC_ASSERT(MFLIMIT >= WILDCOPYLENGTH); 2210 if ((cpy>oend-MFLIMIT) || (ip+length>iend-(2+1+LASTLITERALS))) { 2211 /* We've either hit the input parsing restriction or the output parsing restriction. 2212 * In the normal scenario, decoding a full block, it must be the last sequence, 2213 * otherwise it's an error (invalid input or dimensions). 2214 * In partialDecoding scenario, it's necessary to ensure there is no buffer overflow. 2215 */ 2216 if (partialDecoding) { 2217 /* Since we are partial decoding we may be in this block because of the output parsing 2218 * restriction, which is not valid since the output buffer is allowed to be undersized. 2219 */ 2220 DEBUGLOG(7, "partialDecoding: copying literals, close to input or output end") 2221 DEBUGLOG(7, "partialDecoding: literal length = %u", (unsigned)length); 2222 DEBUGLOG(7, "partialDecoding: remaining space in dstBuffer : %i", (int)(oend - op)); 2223 DEBUGLOG(7, "partialDecoding: remaining space in srcBuffer : %i", (int)(iend - ip)); 2224 /* Finishing in the middle of a literals segment, 2225 * due to lack of input. 2226 */ 2227 if (ip+length > iend) { 2228 length = (size_t)(iend-ip); 2229 cpy = op + length; 2230 } 2231 /* Finishing in the middle of a literals segment, 2232 * due to lack of output space. 2233 */ 2234 if (cpy > oend) { 2235 cpy = oend; 2236 assert(op<=oend); 2237 length = (size_t)(oend-op); 2238 } 2239 } else { 2240 /* We must be on the last sequence (or invalid) because of the parsing limitations 2241 * so check that we exactly consume the input and don't overrun the output buffer. 2242 */ 2243 if ((ip+length != iend) || (cpy > oend)) { 2244 DEBUGLOG(6, "should have been last run of literals") 2245 DEBUGLOG(6, "ip(%p) + length(%i) = %p != iend (%p)", ip, (int)length, ip+length, iend); 2246 DEBUGLOG(6, "or cpy(%p) > oend(%p)", cpy, oend); 2247 goto _output_error; 2248 } 2249 } 2250 LZ4_memmove(op, ip, length); /* supports overlapping memory regions, for in-place decompression scenarios */ 2251 ip += length; 2252 op += length; 2253 /* Necessarily EOF when !partialDecoding. 2254 * When partialDecoding, it is EOF if we've either 2255 * filled the output buffer or 2256 * can't proceed with reading an offset for following match. 2257 */ 2258 if (!partialDecoding || (cpy == oend) || (ip >= (iend-2))) { 2259 break; 2260 } 2261 } else { 2262 LZ4_wildCopy8(op, ip, cpy); /* can overwrite up to 8 bytes beyond cpy */ 2263 ip += length; op = cpy; 2264 } 2265 2266 /* get offset */ 2267 offset = LZ4_readLE16(ip); ip+=2; 2268 match = op - offset; 2269 2270 /* get matchlength */ 2271 length = token & ML_MASK; 2272 2273 _copy_match: 2274 if (length == ML_MASK) { 2275 size_t const addl = read_variable_length(&ip, iend - LASTLITERALS + 1, 0); 2276 if (addl == rvl_error) { goto _output_error; } 2277 length += addl; 2278 if (unlikely((uptrval)(op)+length<(uptrval)op)) goto _output_error; /* overflow detection */ 2279 } 2280 length += MINMATCH; 2281 2282 #if LZ4_FAST_DEC_LOOP 2283 safe_match_copy: 2284 #endif 2285 if ((checkOffset) && (unlikely(match + dictSize < lowPrefix))) goto _output_error; /* Error : offset outside buffers */ 2286 /* match starting within external dictionary */ 2287 if ((dict==usingExtDict) && (match < lowPrefix)) { 2288 assert(dictEnd != NULL); 2289 if (unlikely(op+length > oend-LASTLITERALS)) { 2290 if (partialDecoding) length = MIN(length, (size_t)(oend-op)); 2291 else goto _output_error; /* doesn't respect parsing restriction */ 2292 } 2293 2294 if (length <= (size_t)(lowPrefix-match)) { 2295 /* match fits entirely within external dictionary : just copy */ 2296 LZ4_memmove(op, dictEnd - (lowPrefix-match), length); 2297 op += length; 2298 } else { 2299 /* match stretches into both external dictionary and current block */ 2300 size_t const copySize = (size_t)(lowPrefix - match); 2301 size_t const restSize = length - copySize; 2302 LZ4_memcpy(op, dictEnd - copySize, copySize); 2303 op += copySize; 2304 if (restSize > (size_t)(op - lowPrefix)) { /* overlap copy */ 2305 BYTE* const endOfMatch = op + restSize; 2306 const BYTE* copyFrom = lowPrefix; 2307 while (op < endOfMatch) *op++ = *copyFrom++; 2308 } else { 2309 LZ4_memcpy(op, lowPrefix, restSize); 2310 op += restSize; 2311 } } 2312 continue; 2313 } 2314 assert(match >= lowPrefix); 2315 2316 /* copy match within block */ 2317 cpy = op + length; 2318 2319 /* partialDecoding : may end anywhere within the block */ 2320 assert(op<=oend); 2321 if (partialDecoding && (cpy > oend-MATCH_SAFEGUARD_DISTANCE)) { 2322 size_t const mlen = MIN(length, (size_t)(oend-op)); 2323 const BYTE* const matchEnd = match + mlen; 2324 BYTE* const copyEnd = op + mlen; 2325 if (matchEnd > op) { /* overlap copy */ 2326 while (op < copyEnd) { *op++ = *match++; } 2327 } else { 2328 LZ4_memcpy(op, match, mlen); 2329 } 2330 op = copyEnd; 2331 if (op == oend) { break; } 2332 continue; 2333 } 2334 2335 if (unlikely(offset<8)) { 2336 LZ4_write32(op, 0); /* silence msan warning when offset==0 */ 2337 op[0] = match[0]; 2338 op[1] = match[1]; 2339 op[2] = match[2]; 2340 op[3] = match[3]; 2341 match += inc32table[offset]; 2342 LZ4_memcpy(op+4, match, 4); 2343 match -= dec64table[offset]; 2344 } else { 2345 LZ4_memcpy(op, match, 8); 2346 match += 8; 2347 } 2348 op += 8; 2349 2350 if (unlikely(cpy > oend-MATCH_SAFEGUARD_DISTANCE)) { 2351 BYTE* const oCopyLimit = oend - (WILDCOPYLENGTH-1); 2352 if (cpy > oend-LASTLITERALS) { goto _output_error; } /* Error : last LASTLITERALS bytes must be literals (uncompressed) */ 2353 if (op < oCopyLimit) { 2354 LZ4_wildCopy8(op, match, oCopyLimit); 2355 match += oCopyLimit - op; 2356 op = oCopyLimit; 2357 } 2358 while (op < cpy) { *op++ = *match++; } 2359 } else { 2360 LZ4_memcpy(op, match, 8); 2361 if (length > 16) { LZ4_wildCopy8(op+8, match+8, cpy); } 2362 } 2363 op = cpy; /* wildcopy correction */ 2364 } 2365 2366 /* end of decoding */ 2367 DEBUGLOG(5, "decoded %i bytes", (int) (((char*)op)-dst)); 2368 return (int) (((char*)op)-dst); /* Nb of output bytes decoded */ 2369 2370 /* Overflow error detected */ 2371 _output_error: 2372 return (int) (-(((const char*)ip)-src))-1; 2373 } 2374 } 2375 2376 2377 /*===== Instantiate the API decoding functions. =====*/ 2378 2379 LZ4_FORCE_O2 LZ4_decompress_safe(const char * source,char * dest,int compressedSize,int maxDecompressedSize)2380 int LZ4_decompress_safe(const char* source, char* dest, int compressedSize, int maxDecompressedSize) 2381 { 2382 return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize, 2383 decode_full_block, noDict, 2384 (BYTE*)dest, NULL, 0); 2385 } 2386 2387 LZ4_FORCE_O2 LZ4_decompress_safe_partial(const char * src,char * dst,int compressedSize,int targetOutputSize,int dstCapacity)2388 int LZ4_decompress_safe_partial(const char* src, char* dst, int compressedSize, int targetOutputSize, int dstCapacity) 2389 { 2390 dstCapacity = MIN(targetOutputSize, dstCapacity); 2391 return LZ4_decompress_generic(src, dst, compressedSize, dstCapacity, 2392 partial_decode, 2393 noDict, (BYTE*)dst, NULL, 0); 2394 } 2395 2396 LZ4_FORCE_O2 LZ4_decompress_fast(const char * source,char * dest,int originalSize)2397 int LZ4_decompress_fast(const char* source, char* dest, int originalSize) 2398 { 2399 DEBUGLOG(5, "LZ4_decompress_fast"); 2400 return LZ4_decompress_unsafe_generic( 2401 (const BYTE*)source, (BYTE*)dest, originalSize, 2402 0, NULL, 0); 2403 } 2404 2405 /*===== Instantiate a few more decoding cases, used more than once. =====*/ 2406 2407 LZ4_FORCE_O2 /* Exported, an obsolete API function. */ LZ4_decompress_safe_withPrefix64k(const char * source,char * dest,int compressedSize,int maxOutputSize)2408 int LZ4_decompress_safe_withPrefix64k(const char* source, char* dest, int compressedSize, int maxOutputSize) 2409 { 2410 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, 2411 decode_full_block, withPrefix64k, 2412 (BYTE*)dest - 64 KB, NULL, 0); 2413 } 2414 2415 LZ4_FORCE_O2 LZ4_decompress_safe_partial_withPrefix64k(const char * source,char * dest,int compressedSize,int targetOutputSize,int dstCapacity)2416 static int LZ4_decompress_safe_partial_withPrefix64k(const char* source, char* dest, int compressedSize, int targetOutputSize, int dstCapacity) 2417 { 2418 dstCapacity = MIN(targetOutputSize, dstCapacity); 2419 return LZ4_decompress_generic(source, dest, compressedSize, dstCapacity, 2420 partial_decode, withPrefix64k, 2421 (BYTE*)dest - 64 KB, NULL, 0); 2422 } 2423 2424 /* Another obsolete API function, paired with the previous one. */ LZ4_decompress_fast_withPrefix64k(const char * source,char * dest,int originalSize)2425 int LZ4_decompress_fast_withPrefix64k(const char* source, char* dest, int originalSize) 2426 { 2427 return LZ4_decompress_unsafe_generic( 2428 (const BYTE*)source, (BYTE*)dest, originalSize, 2429 64 KB, NULL, 0); 2430 } 2431 2432 LZ4_FORCE_O2 LZ4_decompress_safe_withSmallPrefix(const char * source,char * dest,int compressedSize,int maxOutputSize,size_t prefixSize)2433 static int LZ4_decompress_safe_withSmallPrefix(const char* source, char* dest, int compressedSize, int maxOutputSize, 2434 size_t prefixSize) 2435 { 2436 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, 2437 decode_full_block, noDict, 2438 (BYTE*)dest-prefixSize, NULL, 0); 2439 } 2440 2441 LZ4_FORCE_O2 LZ4_decompress_safe_partial_withSmallPrefix(const char * source,char * dest,int compressedSize,int targetOutputSize,int dstCapacity,size_t prefixSize)2442 static int LZ4_decompress_safe_partial_withSmallPrefix(const char* source, char* dest, int compressedSize, int targetOutputSize, int dstCapacity, 2443 size_t prefixSize) 2444 { 2445 dstCapacity = MIN(targetOutputSize, dstCapacity); 2446 return LZ4_decompress_generic(source, dest, compressedSize, dstCapacity, 2447 partial_decode, noDict, 2448 (BYTE*)dest-prefixSize, NULL, 0); 2449 } 2450 2451 LZ4_FORCE_O2 LZ4_decompress_safe_forceExtDict(const char * source,char * dest,int compressedSize,int maxOutputSize,const void * dictStart,size_t dictSize)2452 int LZ4_decompress_safe_forceExtDict(const char* source, char* dest, 2453 int compressedSize, int maxOutputSize, 2454 const void* dictStart, size_t dictSize) 2455 { 2456 DEBUGLOG(5, "LZ4_decompress_safe_forceExtDict"); 2457 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, 2458 decode_full_block, usingExtDict, 2459 (BYTE*)dest, (const BYTE*)dictStart, dictSize); 2460 } 2461 2462 LZ4_FORCE_O2 LZ4_decompress_safe_partial_forceExtDict(const char * source,char * dest,int compressedSize,int targetOutputSize,int dstCapacity,const void * dictStart,size_t dictSize)2463 int LZ4_decompress_safe_partial_forceExtDict(const char* source, char* dest, 2464 int compressedSize, int targetOutputSize, int dstCapacity, 2465 const void* dictStart, size_t dictSize) 2466 { 2467 dstCapacity = MIN(targetOutputSize, dstCapacity); 2468 return LZ4_decompress_generic(source, dest, compressedSize, dstCapacity, 2469 partial_decode, usingExtDict, 2470 (BYTE*)dest, (const BYTE*)dictStart, dictSize); 2471 } 2472 2473 LZ4_FORCE_O2 LZ4_decompress_fast_extDict(const char * source,char * dest,int originalSize,const void * dictStart,size_t dictSize)2474 static int LZ4_decompress_fast_extDict(const char* source, char* dest, int originalSize, 2475 const void* dictStart, size_t dictSize) 2476 { 2477 return LZ4_decompress_unsafe_generic( 2478 (const BYTE*)source, (BYTE*)dest, originalSize, 2479 0, (const BYTE*)dictStart, dictSize); 2480 } 2481 2482 /* The "double dictionary" mode, for use with e.g. ring buffers: the first part 2483 * of the dictionary is passed as prefix, and the second via dictStart + dictSize. 2484 * These routines are used only once, in LZ4_decompress_*_continue(). 2485 */ 2486 LZ4_FORCE_INLINE LZ4_decompress_safe_doubleDict(const char * source,char * dest,int compressedSize,int maxOutputSize,size_t prefixSize,const void * dictStart,size_t dictSize)2487 int LZ4_decompress_safe_doubleDict(const char* source, char* dest, int compressedSize, int maxOutputSize, 2488 size_t prefixSize, const void* dictStart, size_t dictSize) 2489 { 2490 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, 2491 decode_full_block, usingExtDict, 2492 (BYTE*)dest-prefixSize, (const BYTE*)dictStart, dictSize); 2493 } 2494 2495 /*===== streaming decompression functions =====*/ 2496 2497 #if !defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION) LZ4_createStreamDecode(void)2498 LZ4_streamDecode_t* LZ4_createStreamDecode(void) 2499 { 2500 LZ4_STATIC_ASSERT(sizeof(LZ4_streamDecode_t) >= sizeof(LZ4_streamDecode_t_internal)); 2501 return (LZ4_streamDecode_t*) ALLOC_AND_ZERO(sizeof(LZ4_streamDecode_t)); 2502 } 2503 LZ4_freeStreamDecode(LZ4_streamDecode_t * LZ4_stream)2504 int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream) 2505 { 2506 if (LZ4_stream == NULL) { return 0; } /* support free on NULL */ 2507 FREEMEM(LZ4_stream); 2508 return 0; 2509 } 2510 #endif 2511 2512 /*! LZ4_setStreamDecode() : 2513 * Use this function to instruct where to find the dictionary. 2514 * This function is not necessary if previous data is still available where it was decoded. 2515 * Loading a size of 0 is allowed (same effect as no dictionary). 2516 * @return : 1 if OK, 0 if error 2517 */ LZ4_setStreamDecode(LZ4_streamDecode_t * LZ4_streamDecode,const char * dictionary,int dictSize)2518 int LZ4_setStreamDecode (LZ4_streamDecode_t* LZ4_streamDecode, const char* dictionary, int dictSize) 2519 { 2520 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse; 2521 lz4sd->prefixSize = (size_t)dictSize; 2522 if (dictSize) { 2523 assert(dictionary != NULL); 2524 lz4sd->prefixEnd = (const BYTE*) dictionary + dictSize; 2525 } else { 2526 lz4sd->prefixEnd = (const BYTE*) dictionary; 2527 } 2528 lz4sd->externalDict = NULL; 2529 lz4sd->extDictSize = 0; 2530 return 1; 2531 } 2532 2533 /*! LZ4_decoderRingBufferSize() : 2534 * when setting a ring buffer for streaming decompression (optional scenario), 2535 * provides the minimum size of this ring buffer 2536 * to be compatible with any source respecting maxBlockSize condition. 2537 * Note : in a ring buffer scenario, 2538 * blocks are presumed decompressed next to each other. 2539 * When not enough space remains for next block (remainingSize < maxBlockSize), 2540 * decoding resumes from beginning of ring buffer. 2541 * @return : minimum ring buffer size, 2542 * or 0 if there is an error (invalid maxBlockSize). 2543 */ LZ4_decoderRingBufferSize(int maxBlockSize)2544 int LZ4_decoderRingBufferSize(int maxBlockSize) 2545 { 2546 if (maxBlockSize < 0) return 0; 2547 if (maxBlockSize > LZ4_MAX_INPUT_SIZE) return 0; 2548 if (maxBlockSize < 16) maxBlockSize = 16; 2549 return LZ4_DECODER_RING_BUFFER_SIZE(maxBlockSize); 2550 } 2551 2552 /* 2553 *_continue() : 2554 These decoding functions allow decompression of multiple blocks in "streaming" mode. 2555 Previously decoded blocks must still be available at the memory position where they were decoded. 2556 If it's not possible, save the relevant part of decoded data into a safe buffer, 2557 and indicate where it stands using LZ4_setStreamDecode() 2558 */ 2559 LZ4_FORCE_O2 LZ4_decompress_safe_continue(LZ4_streamDecode_t * LZ4_streamDecode,const char * source,char * dest,int compressedSize,int maxOutputSize)2560 int LZ4_decompress_safe_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxOutputSize) 2561 { 2562 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse; 2563 int result; 2564 2565 if (lz4sd->prefixSize == 0) { 2566 /* The first call, no dictionary yet. */ 2567 assert(lz4sd->extDictSize == 0); 2568 result = LZ4_decompress_safe(source, dest, compressedSize, maxOutputSize); 2569 if (result <= 0) return result; 2570 lz4sd->prefixSize = (size_t)result; 2571 lz4sd->prefixEnd = (BYTE*)dest + result; 2572 } else if (lz4sd->prefixEnd == (BYTE*)dest) { 2573 /* They're rolling the current segment. */ 2574 if (lz4sd->prefixSize >= 64 KB - 1) 2575 result = LZ4_decompress_safe_withPrefix64k(source, dest, compressedSize, maxOutputSize); 2576 else if (lz4sd->extDictSize == 0) 2577 result = LZ4_decompress_safe_withSmallPrefix(source, dest, compressedSize, maxOutputSize, 2578 lz4sd->prefixSize); 2579 else 2580 result = LZ4_decompress_safe_doubleDict(source, dest, compressedSize, maxOutputSize, 2581 lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize); 2582 if (result <= 0) return result; 2583 lz4sd->prefixSize += (size_t)result; 2584 lz4sd->prefixEnd += result; 2585 } else { 2586 /* The buffer wraps around, or they're switching to another buffer. */ 2587 lz4sd->extDictSize = lz4sd->prefixSize; 2588 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; 2589 result = LZ4_decompress_safe_forceExtDict(source, dest, compressedSize, maxOutputSize, 2590 lz4sd->externalDict, lz4sd->extDictSize); 2591 if (result <= 0) return result; 2592 lz4sd->prefixSize = (size_t)result; 2593 lz4sd->prefixEnd = (BYTE*)dest + result; 2594 } 2595 2596 return result; 2597 } 2598 2599 LZ4_FORCE_O2 int LZ4_decompress_fast_continue(LZ4_streamDecode_t * LZ4_streamDecode,const char * source,char * dest,int originalSize)2600 LZ4_decompress_fast_continue (LZ4_streamDecode_t* LZ4_streamDecode, 2601 const char* source, char* dest, int originalSize) 2602 { 2603 LZ4_streamDecode_t_internal* const lz4sd = 2604 (assert(LZ4_streamDecode!=NULL), &LZ4_streamDecode->internal_donotuse); 2605 int result; 2606 2607 DEBUGLOG(5, "LZ4_decompress_fast_continue (toDecodeSize=%i)", originalSize); 2608 assert(originalSize >= 0); 2609 2610 if (lz4sd->prefixSize == 0) { 2611 DEBUGLOG(5, "first invocation : no prefix nor extDict"); 2612 assert(lz4sd->extDictSize == 0); 2613 result = LZ4_decompress_fast(source, dest, originalSize); 2614 if (result <= 0) return result; 2615 lz4sd->prefixSize = (size_t)originalSize; 2616 lz4sd->prefixEnd = (BYTE*)dest + originalSize; 2617 } else if (lz4sd->prefixEnd == (BYTE*)dest) { 2618 DEBUGLOG(5, "continue using existing prefix"); 2619 result = LZ4_decompress_unsafe_generic( 2620 (const BYTE*)source, (BYTE*)dest, originalSize, 2621 lz4sd->prefixSize, 2622 lz4sd->externalDict, lz4sd->extDictSize); 2623 if (result <= 0) return result; 2624 lz4sd->prefixSize += (size_t)originalSize; 2625 lz4sd->prefixEnd += originalSize; 2626 } else { 2627 DEBUGLOG(5, "prefix becomes extDict"); 2628 lz4sd->extDictSize = lz4sd->prefixSize; 2629 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; 2630 result = LZ4_decompress_fast_extDict(source, dest, originalSize, 2631 lz4sd->externalDict, lz4sd->extDictSize); 2632 if (result <= 0) return result; 2633 lz4sd->prefixSize = (size_t)originalSize; 2634 lz4sd->prefixEnd = (BYTE*)dest + originalSize; 2635 } 2636 2637 return result; 2638 } 2639 2640 2641 /* 2642 Advanced decoding functions : 2643 *_usingDict() : 2644 These decoding functions work the same as "_continue" ones, 2645 the dictionary must be explicitly provided within parameters 2646 */ 2647 LZ4_decompress_safe_usingDict(const char * source,char * dest,int compressedSize,int maxOutputSize,const char * dictStart,int dictSize)2648 int LZ4_decompress_safe_usingDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize) 2649 { 2650 if (dictSize==0) 2651 return LZ4_decompress_safe(source, dest, compressedSize, maxOutputSize); 2652 if (dictStart+dictSize == dest) { 2653 if (dictSize >= 64 KB - 1) { 2654 return LZ4_decompress_safe_withPrefix64k(source, dest, compressedSize, maxOutputSize); 2655 } 2656 assert(dictSize >= 0); 2657 return LZ4_decompress_safe_withSmallPrefix(source, dest, compressedSize, maxOutputSize, (size_t)dictSize); 2658 } 2659 assert(dictSize >= 0); 2660 return LZ4_decompress_safe_forceExtDict(source, dest, compressedSize, maxOutputSize, dictStart, (size_t)dictSize); 2661 } 2662 LZ4_decompress_safe_partial_usingDict(const char * source,char * dest,int compressedSize,int targetOutputSize,int dstCapacity,const char * dictStart,int dictSize)2663 int LZ4_decompress_safe_partial_usingDict(const char* source, char* dest, int compressedSize, int targetOutputSize, int dstCapacity, const char* dictStart, int dictSize) 2664 { 2665 if (dictSize==0) 2666 return LZ4_decompress_safe_partial(source, dest, compressedSize, targetOutputSize, dstCapacity); 2667 if (dictStart+dictSize == dest) { 2668 if (dictSize >= 64 KB - 1) { 2669 return LZ4_decompress_safe_partial_withPrefix64k(source, dest, compressedSize, targetOutputSize, dstCapacity); 2670 } 2671 assert(dictSize >= 0); 2672 return LZ4_decompress_safe_partial_withSmallPrefix(source, dest, compressedSize, targetOutputSize, dstCapacity, (size_t)dictSize); 2673 } 2674 assert(dictSize >= 0); 2675 return LZ4_decompress_safe_partial_forceExtDict(source, dest, compressedSize, targetOutputSize, dstCapacity, dictStart, (size_t)dictSize); 2676 } 2677 LZ4_decompress_fast_usingDict(const char * source,char * dest,int originalSize,const char * dictStart,int dictSize)2678 int LZ4_decompress_fast_usingDict(const char* source, char* dest, int originalSize, const char* dictStart, int dictSize) 2679 { 2680 if (dictSize==0 || dictStart+dictSize == dest) 2681 return LZ4_decompress_unsafe_generic( 2682 (const BYTE*)source, (BYTE*)dest, originalSize, 2683 (size_t)dictSize, NULL, 0); 2684 assert(dictSize >= 0); 2685 return LZ4_decompress_fast_extDict(source, dest, originalSize, dictStart, (size_t)dictSize); 2686 } 2687 2688 2689 /*=************************************************* 2690 * Obsolete Functions 2691 ***************************************************/ 2692 /* obsolete compression functions */ LZ4_compress_limitedOutput(const char * source,char * dest,int inputSize,int maxOutputSize)2693 int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize) 2694 { 2695 return LZ4_compress_default(source, dest, inputSize, maxOutputSize); 2696 } LZ4_compress(const char * src,char * dest,int srcSize)2697 int LZ4_compress(const char* src, char* dest, int srcSize) 2698 { 2699 return LZ4_compress_default(src, dest, srcSize, LZ4_compressBound(srcSize)); 2700 } LZ4_compress_limitedOutput_withState(void * state,const char * src,char * dst,int srcSize,int dstSize)2701 int LZ4_compress_limitedOutput_withState (void* state, const char* src, char* dst, int srcSize, int dstSize) 2702 { 2703 return LZ4_compress_fast_extState(state, src, dst, srcSize, dstSize, 1); 2704 } LZ4_compress_withState(void * state,const char * src,char * dst,int srcSize)2705 int LZ4_compress_withState (void* state, const char* src, char* dst, int srcSize) 2706 { 2707 return LZ4_compress_fast_extState(state, src, dst, srcSize, LZ4_compressBound(srcSize), 1); 2708 } LZ4_compress_limitedOutput_continue(LZ4_stream_t * LZ4_stream,const char * src,char * dst,int srcSize,int dstCapacity)2709 int LZ4_compress_limitedOutput_continue (LZ4_stream_t* LZ4_stream, const char* src, char* dst, int srcSize, int dstCapacity) 2710 { 2711 return LZ4_compress_fast_continue(LZ4_stream, src, dst, srcSize, dstCapacity, 1); 2712 } LZ4_compress_continue(LZ4_stream_t * LZ4_stream,const char * source,char * dest,int inputSize)2713 int LZ4_compress_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize) 2714 { 2715 return LZ4_compress_fast_continue(LZ4_stream, source, dest, inputSize, LZ4_compressBound(inputSize), 1); 2716 } 2717 2718 /* 2719 These decompression functions are deprecated and should no longer be used. 2720 They are only provided here for compatibility with older user programs. 2721 - LZ4_uncompress is totally equivalent to LZ4_decompress_fast 2722 - LZ4_uncompress_unknownOutputSize is totally equivalent to LZ4_decompress_safe 2723 */ LZ4_uncompress(const char * source,char * dest,int outputSize)2724 int LZ4_uncompress (const char* source, char* dest, int outputSize) 2725 { 2726 return LZ4_decompress_fast(source, dest, outputSize); 2727 } LZ4_uncompress_unknownOutputSize(const char * source,char * dest,int isize,int maxOutputSize)2728 int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize) 2729 { 2730 return LZ4_decompress_safe(source, dest, isize, maxOutputSize); 2731 } 2732 2733 /* Obsolete Streaming functions */ 2734 LZ4_sizeofStreamState(void)2735 int LZ4_sizeofStreamState(void) { return sizeof(LZ4_stream_t); } 2736 LZ4_resetStreamState(void * state,char * inputBuffer)2737 int LZ4_resetStreamState(void* state, char* inputBuffer) 2738 { 2739 (void)inputBuffer; 2740 LZ4_resetStream((LZ4_stream_t*)state); 2741 return 0; 2742 } 2743 2744 #if !defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION) LZ4_create(char * inputBuffer)2745 void* LZ4_create (char* inputBuffer) 2746 { 2747 (void)inputBuffer; 2748 return LZ4_createStream(); 2749 } 2750 #endif 2751 LZ4_slideInputBuffer(void * state)2752 char* LZ4_slideInputBuffer (void* state) 2753 { 2754 /* avoid const char * -> char * conversion warning */ 2755 return (char *)(uptrval)((LZ4_stream_t*)state)->internal_donotuse.dictionary; 2756 } 2757 2758 #endif /* LZ4_COMMONDEFS_ONLY */ 2759 2760 #endif /* LV_USE_LZ4_INTERNAL */ 2761 2762
