1 /* 2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc. 3 * All rights reserved. 4 * 5 * This source code is licensed under both the BSD-style license (found in the 6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found 7 * in the COPYING file in the root directory of this source tree). 8 * You may select, at your option, one of the above-listed licenses. 9 */ 10 11 12 /****************************************** 13 * Includes 14 ******************************************/ 15 #include <stddef.h> /* size_t, ptrdiff_t */ 16 #include <string.h> /* memcpy */ 17 18 #include "zstd_v04.h" 19 #include "error_private.h" 20 21 22 /* ****************************************************************** 23 * mem.h 24 *******************************************************************/ 25 #ifndef MEM_H_MODULE 26 #define MEM_H_MODULE 27 28 #if defined (__cplusplus) 29 extern "C" { 30 #endif 31 32 33 /****************************************** 34 * Compiler-specific 35 ******************************************/ 36 #if defined(_MSC_VER) /* Visual Studio */ 37 # include <stdlib.h> /* _byteswap_ulong */ 38 # include <intrin.h> /* _byteswap_* */ 39 #endif 40 #if defined(__GNUC__) 41 # define MEM_STATIC static __attribute__((unused)) 42 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 43 # define MEM_STATIC static inline 44 #elif defined(_MSC_VER) 45 # define MEM_STATIC static __inline 46 #else 47 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */ 48 #endif 49 50 51 /**************************************************************** 52 * Basic Types 53 *****************************************************************/ 54 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 55 # include <stdint.h> 56 typedef uint8_t BYTE; 57 typedef uint16_t U16; 58 typedef int16_t S16; 59 typedef uint32_t U32; 60 typedef int32_t S32; 61 typedef uint64_t U64; 62 typedef int64_t S64; 63 #else 64 typedef unsigned char BYTE; 65 typedef unsigned short U16; 66 typedef signed short S16; 67 typedef unsigned int U32; 68 typedef signed int S32; 69 typedef unsigned long long U64; 70 typedef signed long long S64; 71 #endif 72 73 74 /*-************************************* 75 * Debug 76 ***************************************/ 77 #include "debug.h" 78 #ifndef assert 79 # define assert(condition) ((void)0) 80 #endif 81 82 83 /**************************************************************** 84 * Memory I/O 85 *****************************************************************/ 86 /* MEM_FORCE_MEMORY_ACCESS 87 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable. 88 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal. 89 * The below switch allow to select different access method for improved performance. 90 * Method 0 (default) : use `memcpy()`. Safe and portable. 91 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable). 92 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`. 93 * Method 2 : direct access. This method is portable but violate C standard. 94 * It can generate buggy code on targets generating assembly depending on alignment. 95 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6) 96 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details. 97 * Prefer these methods in priority order (0 > 1 > 2) 98 */ 99 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */ 100 # if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) ) 101 # define MEM_FORCE_MEMORY_ACCESS 2 102 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \ 103 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) )) 104 # define MEM_FORCE_MEMORY_ACCESS 1 105 # endif 106 #endif 107 108 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; } 109 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; } 110 111 MEM_STATIC unsigned MEM_isLittleEndian(void) 112 { 113 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ 114 return one.c[0]; 115 } 116 117 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2) 118 119 /* violates C standard on structure alignment. 120 Only use if no other choice to achieve best performance on target platform */ 121 MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; } 122 MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; } 123 MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; } 124 125 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; } 126 127 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1) 128 129 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ 130 /* currently only defined for gcc and icc */ 131 typedef union { U16 u16; U32 u32; U64 u64; } __attribute__((packed)) unalign; 132 133 MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; } 134 MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } 135 MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; } 136 137 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; } 138 139 #else 140 141 /* default method, safe and standard. 142 can sometimes prove slower */ 143 144 MEM_STATIC U16 MEM_read16(const void* memPtr) 145 { 146 U16 val; memcpy(&val, memPtr, sizeof(val)); return val; 147 } 148 149 MEM_STATIC U32 MEM_read32(const void* memPtr) 150 { 151 U32 val; memcpy(&val, memPtr, sizeof(val)); return val; 152 } 153 154 MEM_STATIC U64 MEM_read64(const void* memPtr) 155 { 156 U64 val; memcpy(&val, memPtr, sizeof(val)); return val; 157 } 158 159 MEM_STATIC void MEM_write16(void* memPtr, U16 value) 160 { 161 memcpy(memPtr, &value, sizeof(value)); 162 } 163 164 #endif // MEM_FORCE_MEMORY_ACCESS 165 166 167 MEM_STATIC U16 MEM_readLE16(const void* memPtr) 168 { 169 if (MEM_isLittleEndian()) 170 return MEM_read16(memPtr); 171 else 172 { 173 const BYTE* p = (const BYTE*)memPtr; 174 return (U16)(p[0] + (p[1]<<8)); 175 } 176 } 177 178 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val) 179 { 180 if (MEM_isLittleEndian()) 181 { 182 MEM_write16(memPtr, val); 183 } 184 else 185 { 186 BYTE* p = (BYTE*)memPtr; 187 p[0] = (BYTE)val; 188 p[1] = (BYTE)(val>>8); 189 } 190 } 191 192 MEM_STATIC U32 MEM_readLE32(const void* memPtr) 193 { 194 if (MEM_isLittleEndian()) 195 return MEM_read32(memPtr); 196 else 197 { 198 const BYTE* p = (const BYTE*)memPtr; 199 return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24)); 200 } 201 } 202 203 204 MEM_STATIC U64 MEM_readLE64(const void* memPtr) 205 { 206 if (MEM_isLittleEndian()) 207 return MEM_read64(memPtr); 208 else 209 { 210 const BYTE* p = (const BYTE*)memPtr; 211 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24) 212 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56)); 213 } 214 } 215 216 217 MEM_STATIC size_t MEM_readLEST(const void* memPtr) 218 { 219 if (MEM_32bits()) 220 return (size_t)MEM_readLE32(memPtr); 221 else 222 return (size_t)MEM_readLE64(memPtr); 223 } 224 225 226 #if defined (__cplusplus) 227 } 228 #endif 229 230 #endif /* MEM_H_MODULE */ 231 232 /* 233 zstd - standard compression library 234 Header File for static linking only 235 */ 236 #ifndef ZSTD_STATIC_H 237 #define ZSTD_STATIC_H 238 239 240 /* ************************************* 241 * Types 242 ***************************************/ 243 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 11 244 245 /** from faster to stronger */ 246 typedef enum { ZSTD_fast, ZSTD_greedy, ZSTD_lazy, ZSTD_lazy2, ZSTD_btlazy2 } ZSTD_strategy; 247 248 typedef struct 249 { 250 U64 srcSize; /* optional : tells how much bytes are present in the frame. Use 0 if not known. */ 251 U32 windowLog; /* largest match distance : larger == more compression, more memory needed during decompression */ 252 U32 contentLog; /* full search segment : larger == more compression, slower, more memory (useless for fast) */ 253 U32 hashLog; /* dispatch table : larger == more memory, faster */ 254 U32 searchLog; /* nb of searches : larger == more compression, slower */ 255 U32 searchLength; /* size of matches : larger == faster decompression, sometimes less compression */ 256 ZSTD_strategy strategy; 257 } ZSTD_parameters; 258 259 typedef ZSTDv04_Dctx ZSTD_DCtx; 260 261 /* ************************************* 262 * Advanced functions 263 ***************************************/ 264 /** ZSTD_decompress_usingDict 265 * Same as ZSTD_decompressDCtx, using a Dictionary content as prefix 266 * Note : dict can be NULL, in which case, it's equivalent to ZSTD_decompressDCtx() */ 267 static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx, 268 void* dst, size_t maxDstSize, 269 const void* src, size_t srcSize, 270 const void* dict,size_t dictSize); 271 272 273 /* ************************************** 274 * Streaming functions (direct mode) 275 ****************************************/ 276 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx); 277 static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize); 278 static void ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* src, size_t srcSize); 279 280 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx); 281 static size_t ZSTD_decompressContinue(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize); 282 283 /** 284 Streaming decompression, bufferless mode 285 286 A ZSTD_DCtx object is required to track streaming operations. 287 Use ZSTD_createDCtx() / ZSTD_freeDCtx() to manage it. 288 A ZSTD_DCtx object can be re-used multiple times. Use ZSTD_resetDCtx() to return to fresh status. 289 290 First operation is to retrieve frame parameters, using ZSTD_getFrameParams(). 291 This function doesn't consume its input. It needs enough input data to properly decode the frame header. 292 Objective is to retrieve *params.windowlog, to know minimum amount of memory required during decoding. 293 Result : 0 when successful, it means the ZSTD_parameters structure has been filled. 294 >0 : means there is not enough data into src. Provides the expected size to successfully decode header. 295 errorCode, which can be tested using ZSTD_isError() (For example, if it's not a ZSTD header) 296 297 Then, you can optionally insert a dictionary. 298 This operation must mimic the compressor behavior, otherwise decompression will fail or be corrupted. 299 300 Then it's possible to start decompression. 301 Use ZSTD_nextSrcSizeToDecompress() and ZSTD_decompressContinue() alternatively. 302 ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue(). 303 ZSTD_decompressContinue() requires this exact amount of bytes, or it will fail. 304 ZSTD_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog). 305 They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible. 306 307 @result of ZSTD_decompressContinue() is the number of bytes regenerated within 'dst'. 308 It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header. 309 310 A frame is fully decoded when ZSTD_nextSrcSizeToDecompress() returns zero. 311 Context can then be reset to start a new decompression. 312 */ 313 314 315 316 317 #endif /* ZSTD_STATIC_H */ 318 319 320 /* 321 zstd_internal - common functions to include 322 Header File for include 323 */ 324 #ifndef ZSTD_CCOMMON_H_MODULE 325 #define ZSTD_CCOMMON_H_MODULE 326 327 /* ************************************* 328 * Common macros 329 ***************************************/ 330 #define MIN(a,b) ((a)<(b) ? (a) : (b)) 331 #define MAX(a,b) ((a)>(b) ? (a) : (b)) 332 333 334 /* ************************************* 335 * Common constants 336 ***************************************/ 337 #define ZSTD_MAGICNUMBER 0xFD2FB524 /* v0.4 */ 338 339 #define KB *(1 <<10) 340 #define MB *(1 <<20) 341 #define GB *(1U<<30) 342 343 #define BLOCKSIZE (128 KB) /* define, for static allocation */ 344 345 static const size_t ZSTD_blockHeaderSize = 3; 346 static const size_t ZSTD_frameHeaderSize_min = 5; 347 #define ZSTD_frameHeaderSize_max 5 /* define, for static allocation */ 348 349 #define BIT7 128 350 #define BIT6 64 351 #define BIT5 32 352 #define BIT4 16 353 #define BIT1 2 354 #define BIT0 1 355 356 #define IS_RAW BIT0 357 #define IS_RLE BIT1 358 359 #define MINMATCH 4 360 #define REPCODE_STARTVALUE 4 361 362 #define MLbits 7 363 #define LLbits 6 364 #define Offbits 5 365 #define MaxML ((1<<MLbits) - 1) 366 #define MaxLL ((1<<LLbits) - 1) 367 #define MaxOff ((1<<Offbits)- 1) 368 #define MLFSELog 10 369 #define LLFSELog 10 370 #define OffFSELog 9 371 #define MaxSeq MAX(MaxLL, MaxML) 372 373 #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/) 374 #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE) 375 376 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2) 377 378 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t; 379 380 381 /* ****************************************** 382 * Shared functions to include for inlining 383 ********************************************/ 384 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); } 385 386 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; } 387 388 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */ 389 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length) 390 { 391 const BYTE* ip = (const BYTE*)src; 392 BYTE* op = (BYTE*)dst; 393 BYTE* const oend = op + length; 394 do 395 COPY8(op, ip) 396 while (op < oend); 397 } 398 399 400 401 /* ****************************************************************** 402 FSE : Finite State Entropy coder 403 header file 404 ****************************************************************** */ 405 #ifndef FSE_H 406 #define FSE_H 407 408 #if defined (__cplusplus) 409 extern "C" { 410 #endif 411 412 413 /* ***************************************** 414 * Includes 415 ******************************************/ 416 #include <stddef.h> /* size_t, ptrdiff_t */ 417 418 419 /* ***************************************** 420 * FSE simple functions 421 ******************************************/ 422 static size_t FSE_decompress(void* dst, size_t maxDstSize, 423 const void* cSrc, size_t cSrcSize); 424 /*! 425 FSE_decompress(): 426 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize', 427 into already allocated destination buffer 'dst', of size 'maxDstSize'. 428 return : size of regenerated data (<= maxDstSize) 429 or an error code, which can be tested using FSE_isError() 430 431 ** Important ** : FSE_decompress() doesn't decompress non-compressible nor RLE data !!! 432 Why ? : making this distinction requires a header. 433 Header management is intentionally delegated to the user layer, which can better manage special cases. 434 */ 435 436 437 /* ***************************************** 438 * Tool functions 439 ******************************************/ 440 /* Error Management */ 441 static unsigned FSE_isError(size_t code); /* tells if a return value is an error code */ 442 443 444 445 /* ***************************************** 446 * FSE detailed API 447 ******************************************/ 448 /*! 449 FSE_compress() does the following: 450 1. count symbol occurrence from source[] into table count[] 451 2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog) 452 3. save normalized counters to memory buffer using writeNCount() 453 4. build encoding table 'CTable' from normalized counters 454 5. encode the data stream using encoding table 'CTable' 455 456 FSE_decompress() does the following: 457 1. read normalized counters with readNCount() 458 2. build decoding table 'DTable' from normalized counters 459 3. decode the data stream using decoding table 'DTable' 460 461 The following API allows targeting specific sub-functions for advanced tasks. 462 For example, it's possible to compress several blocks using the same 'CTable', 463 or to save and provide normalized distribution using external method. 464 */ 465 466 467 /* *** DECOMPRESSION *** */ 468 469 /*! 470 FSE_readNCount(): 471 Read compactly saved 'normalizedCounter' from 'rBuffer'. 472 return : size read from 'rBuffer' 473 or an errorCode, which can be tested using FSE_isError() 474 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */ 475 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize); 476 477 /*! 478 Constructor and Destructor of type FSE_DTable 479 Note that its size depends on 'tableLog' */ 480 typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */ 481 482 /*! 483 FSE_buildDTable(): 484 Builds 'dt', which must be already allocated, using FSE_createDTable() 485 return : 0, 486 or an errorCode, which can be tested using FSE_isError() */ 487 static size_t FSE_buildDTable ( FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog); 488 489 /*! 490 FSE_decompress_usingDTable(): 491 Decompress compressed source 'cSrc' of size 'cSrcSize' using 'dt' 492 into 'dst' which must be already allocated. 493 return : size of regenerated data (necessarily <= maxDstSize) 494 or an errorCode, which can be tested using FSE_isError() */ 495 static size_t FSE_decompress_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const FSE_DTable* dt); 496 497 /*! 498 Tutorial : 499 ---------- 500 (Note : these functions only decompress FSE-compressed blocks. 501 If block is uncompressed, use memcpy() instead 502 If block is a single repeated byte, use memset() instead ) 503 504 The first step is to obtain the normalized frequencies of symbols. 505 This can be performed by FSE_readNCount() if it was saved using FSE_writeNCount(). 506 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short. 507 In practice, that means it's necessary to know 'maxSymbolValue' beforehand, 508 or size the table to handle worst case situations (typically 256). 509 FSE_readNCount() will provide 'tableLog' and 'maxSymbolValue'. 510 The result of FSE_readNCount() is the number of bytes read from 'rBuffer'. 511 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that. 512 If there is an error, the function will return an error code, which can be tested using FSE_isError(). 513 514 The next step is to build the decompression tables 'FSE_DTable' from 'normalizedCounter'. 515 This is performed by the function FSE_buildDTable(). 516 The space required by 'FSE_DTable' must be already allocated using FSE_createDTable(). 517 If there is an error, the function will return an error code, which can be tested using FSE_isError(). 518 519 'FSE_DTable' can then be used to decompress 'cSrc', with FSE_decompress_usingDTable(). 520 'cSrcSize' must be strictly correct, otherwise decompression will fail. 521 FSE_decompress_usingDTable() result will tell how many bytes were regenerated (<=maxDstSize). 522 If there is an error, the function will return an error code, which can be tested using FSE_isError(). (ex: dst buffer too small) 523 */ 524 525 526 #if defined (__cplusplus) 527 } 528 #endif 529 530 #endif /* FSE_H */ 531 532 533 /* ****************************************************************** 534 bitstream 535 Part of NewGen Entropy library 536 header file (to include) 537 Copyright (C) 2013-2015, Yann Collet. 538 539 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 540 541 Redistribution and use in source and binary forms, with or without 542 modification, are permitted provided that the following conditions are 543 met: 544 545 * Redistributions of source code must retain the above copyright 546 notice, this list of conditions and the following disclaimer. 547 * Redistributions in binary form must reproduce the above 548 copyright notice, this list of conditions and the following disclaimer 549 in the documentation and/or other materials provided with the 550 distribution. 551 552 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 553 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 554 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 555 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 556 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 557 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 558 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 559 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 560 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 561 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 562 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 563 564 You can contact the author at : 565 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 566 - Public forum : https://groups.google.com/forum/#!forum/lz4c 567 ****************************************************************** */ 568 #ifndef BITSTREAM_H_MODULE 569 #define BITSTREAM_H_MODULE 570 571 #if defined (__cplusplus) 572 extern "C" { 573 #endif 574 575 576 /* 577 * This API consists of small unitary functions, which highly benefit from being inlined. 578 * Since link-time-optimization is not available for all compilers, 579 * these functions are defined into a .h to be included. 580 */ 581 582 /********************************************** 583 * bitStream decompression API (read backward) 584 **********************************************/ 585 typedef struct 586 { 587 size_t bitContainer; 588 unsigned bitsConsumed; 589 const char* ptr; 590 const char* start; 591 } BIT_DStream_t; 592 593 typedef enum { BIT_DStream_unfinished = 0, 594 BIT_DStream_endOfBuffer = 1, 595 BIT_DStream_completed = 2, 596 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */ 597 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */ 598 599 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize); 600 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits); 601 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD); 602 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD); 603 604 605 606 607 /****************************************** 608 * unsafe API 609 ******************************************/ 610 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits); 611 /* faster, but works only if nbBits >= 1 */ 612 613 614 615 /**************************************************************** 616 * Helper functions 617 ****************************************************************/ 618 MEM_STATIC unsigned BIT_highbit32 (U32 val) 619 { 620 # if defined(_MSC_VER) /* Visual */ 621 unsigned long r=0; 622 _BitScanReverse ( &r, val ); 623 return (unsigned) r; 624 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */ 625 return 31 - __builtin_clz (val); 626 # else /* Software version */ 627 static const unsigned DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; 628 U32 v = val; 629 unsigned r; 630 v |= v >> 1; 631 v |= v >> 2; 632 v |= v >> 4; 633 v |= v >> 8; 634 v |= v >> 16; 635 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27]; 636 return r; 637 # endif 638 } 639 640 641 /********************************************************** 642 * bitStream decoding 643 **********************************************************/ 644 645 /*!BIT_initDStream 646 * Initialize a BIT_DStream_t. 647 * @bitD : a pointer to an already allocated BIT_DStream_t structure 648 * @srcBuffer must point at the beginning of a bitStream 649 * @srcSize must be the exact size of the bitStream 650 * @result : size of stream (== srcSize) or an errorCode if a problem is detected 651 */ 652 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize) 653 { 654 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); } 655 656 if (srcSize >= sizeof(size_t)) /* normal case */ 657 { 658 U32 contain32; 659 bitD->start = (const char*)srcBuffer; 660 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t); 661 bitD->bitContainer = MEM_readLEST(bitD->ptr); 662 contain32 = ((const BYTE*)srcBuffer)[srcSize-1]; 663 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */ 664 bitD->bitsConsumed = 8 - BIT_highbit32(contain32); 665 } 666 else 667 { 668 U32 contain32; 669 bitD->start = (const char*)srcBuffer; 670 bitD->ptr = bitD->start; 671 bitD->bitContainer = *(const BYTE*)(bitD->start); 672 switch(srcSize) 673 { 674 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);/* fall-through */ 675 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);/* fall-through */ 676 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);/* fall-through */ 677 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24; /* fall-through */ 678 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16; /* fall-through */ 679 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8; /* fall-through */ 680 default: break; 681 } 682 contain32 = ((const BYTE*)srcBuffer)[srcSize-1]; 683 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */ 684 bitD->bitsConsumed = 8 - BIT_highbit32(contain32); 685 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8; 686 } 687 688 return srcSize; 689 } 690 691 MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits) 692 { 693 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1; 694 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask); 695 } 696 697 /*! BIT_lookBitsFast : 698 * unsafe version; only works only if nbBits >= 1 */ 699 MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits) 700 { 701 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1; 702 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask); 703 } 704 705 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits) 706 { 707 bitD->bitsConsumed += nbBits; 708 } 709 710 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits) 711 { 712 size_t value = BIT_lookBits(bitD, nbBits); 713 BIT_skipBits(bitD, nbBits); 714 return value; 715 } 716 717 /*!BIT_readBitsFast : 718 * unsafe version; only works only if nbBits >= 1 */ 719 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits) 720 { 721 size_t value = BIT_lookBitsFast(bitD, nbBits); 722 BIT_skipBits(bitD, nbBits); 723 return value; 724 } 725 726 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD) 727 { 728 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */ 729 return BIT_DStream_overflow; 730 731 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) 732 { 733 bitD->ptr -= bitD->bitsConsumed >> 3; 734 bitD->bitsConsumed &= 7; 735 bitD->bitContainer = MEM_readLEST(bitD->ptr); 736 return BIT_DStream_unfinished; 737 } 738 if (bitD->ptr == bitD->start) 739 { 740 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer; 741 return BIT_DStream_completed; 742 } 743 { 744 U32 nbBytes = bitD->bitsConsumed >> 3; 745 BIT_DStream_status result = BIT_DStream_unfinished; 746 if (bitD->ptr - nbBytes < bitD->start) 747 { 748 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */ 749 result = BIT_DStream_endOfBuffer; 750 } 751 bitD->ptr -= nbBytes; 752 bitD->bitsConsumed -= nbBytes*8; 753 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */ 754 return result; 755 } 756 } 757 758 /*! BIT_endOfDStream 759 * @return Tells if DStream has reached its exact end 760 */ 761 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream) 762 { 763 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8)); 764 } 765 766 #if defined (__cplusplus) 767 } 768 #endif 769 770 #endif /* BITSTREAM_H_MODULE */ 771 772 773 774 /* ****************************************************************** 775 FSE : Finite State Entropy coder 776 header file for static linking (only) 777 Copyright (C) 2013-2015, Yann Collet 778 779 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 780 781 Redistribution and use in source and binary forms, with or without 782 modification, are permitted provided that the following conditions are 783 met: 784 785 * Redistributions of source code must retain the above copyright 786 notice, this list of conditions and the following disclaimer. 787 * Redistributions in binary form must reproduce the above 788 copyright notice, this list of conditions and the following disclaimer 789 in the documentation and/or other materials provided with the 790 distribution. 791 792 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 793 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 794 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 795 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 796 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 797 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 798 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 799 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 800 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 801 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 802 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 803 804 You can contact the author at : 805 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 806 - Public forum : https://groups.google.com/forum/#!forum/lz4c 807 ****************************************************************** */ 808 #ifndef FSE_STATIC_H 809 #define FSE_STATIC_H 810 811 #if defined (__cplusplus) 812 extern "C" { 813 #endif 814 815 816 /* ***************************************** 817 * Static allocation 818 *******************************************/ 819 /* FSE buffer bounds */ 820 #define FSE_NCOUNTBOUND 512 821 #define FSE_BLOCKBOUND(size) (size + (size>>7)) 822 #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ 823 824 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */ 825 #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2)) 826 #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog)) 827 828 829 /* ***************************************** 830 * FSE advanced API 831 *******************************************/ 832 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits); 833 /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */ 834 835 static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue); 836 /* build a fake FSE_DTable, designed to always generate the same symbolValue */ 837 838 839 840 /* ***************************************** 841 * FSE symbol decompression API 842 *******************************************/ 843 typedef struct 844 { 845 size_t state; 846 const void* table; /* precise table may vary, depending on U16 */ 847 } FSE_DState_t; 848 849 850 static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt); 851 852 static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD); 853 854 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr); 855 856 857 /* ***************************************** 858 * FSE unsafe API 859 *******************************************/ 860 static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD); 861 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */ 862 863 864 /* ***************************************** 865 * Implementation of inlined functions 866 *******************************************/ 867 /* decompression */ 868 869 typedef struct { 870 U16 tableLog; 871 U16 fastMode; 872 } FSE_DTableHeader; /* sizeof U32 */ 873 874 typedef struct 875 { 876 unsigned short newState; 877 unsigned char symbol; 878 unsigned char nbBits; 879 } FSE_decode_t; /* size == U32 */ 880 881 MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt) 882 { 883 FSE_DTableHeader DTableH; 884 memcpy(&DTableH, dt, sizeof(DTableH)); 885 DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog); 886 BIT_reloadDStream(bitD); 887 DStatePtr->table = dt + 1; 888 } 889 890 MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) 891 { 892 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 893 const U32 nbBits = DInfo.nbBits; 894 BYTE symbol = DInfo.symbol; 895 size_t lowBits = BIT_readBits(bitD, nbBits); 896 897 DStatePtr->state = DInfo.newState + lowBits; 898 return symbol; 899 } 900 901 MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) 902 { 903 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 904 const U32 nbBits = DInfo.nbBits; 905 BYTE symbol = DInfo.symbol; 906 size_t lowBits = BIT_readBitsFast(bitD, nbBits); 907 908 DStatePtr->state = DInfo.newState + lowBits; 909 return symbol; 910 } 911 912 MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr) 913 { 914 return DStatePtr->state == 0; 915 } 916 917 918 #if defined (__cplusplus) 919 } 920 #endif 921 922 #endif /* FSE_STATIC_H */ 923 924 /* ****************************************************************** 925 FSE : Finite State Entropy coder 926 Copyright (C) 2013-2015, Yann Collet. 927 928 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 929 930 Redistribution and use in source and binary forms, with or without 931 modification, are permitted provided that the following conditions are 932 met: 933 934 * Redistributions of source code must retain the above copyright 935 notice, this list of conditions and the following disclaimer. 936 * Redistributions in binary form must reproduce the above 937 copyright notice, this list of conditions and the following disclaimer 938 in the documentation and/or other materials provided with the 939 distribution. 940 941 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 942 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 943 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 944 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 945 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 946 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 947 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 948 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 949 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 950 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 951 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 952 953 You can contact the author at : 954 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy 955 - Public forum : https://groups.google.com/forum/#!forum/lz4c 956 ****************************************************************** */ 957 958 #ifndef FSE_COMMONDEFS_ONLY 959 960 /* ************************************************************** 961 * Tuning parameters 962 ****************************************************************/ 963 /*!MEMORY_USAGE : 964 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) 965 * Increasing memory usage improves compression ratio 966 * Reduced memory usage can improve speed, due to cache effect 967 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */ 968 #define FSE_MAX_MEMORY_USAGE 14 969 #define FSE_DEFAULT_MEMORY_USAGE 13 970 971 /*!FSE_MAX_SYMBOL_VALUE : 972 * Maximum symbol value authorized. 973 * Required for proper stack allocation */ 974 #define FSE_MAX_SYMBOL_VALUE 255 975 976 977 /* ************************************************************** 978 * template functions type & suffix 979 ****************************************************************/ 980 #define FSE_FUNCTION_TYPE BYTE 981 #define FSE_FUNCTION_EXTENSION 982 #define FSE_DECODE_TYPE FSE_decode_t 983 984 985 #endif /* !FSE_COMMONDEFS_ONLY */ 986 987 /* ************************************************************** 988 * Compiler specifics 989 ****************************************************************/ 990 #ifdef _MSC_VER /* Visual Studio */ 991 # define FORCE_INLINE static __forceinline 992 # include <intrin.h> /* For Visual 2005 */ 993 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 994 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */ 995 #else 996 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 997 # ifdef __GNUC__ 998 # define FORCE_INLINE static inline __attribute__((always_inline)) 999 # else 1000 # define FORCE_INLINE static inline 1001 # endif 1002 # else 1003 # define FORCE_INLINE static 1004 # endif /* __STDC_VERSION__ */ 1005 #endif 1006 1007 1008 /* ************************************************************** 1009 * Dependencies 1010 ****************************************************************/ 1011 #include <stdlib.h> /* malloc, free, qsort */ 1012 #include <string.h> /* memcpy, memset */ 1013 #include <stdio.h> /* printf (debug) */ 1014 1015 1016 /* *************************************************************** 1017 * Constants 1018 *****************************************************************/ 1019 #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2) 1020 #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG) 1021 #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1) 1022 #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2) 1023 #define FSE_MIN_TABLELOG 5 1024 1025 #define FSE_TABLELOG_ABSOLUTE_MAX 15 1026 #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX 1027 #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported" 1028 #endif 1029 1030 1031 /* ************************************************************** 1032 * Error Management 1033 ****************************************************************/ 1034 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 1035 1036 1037 /* ************************************************************** 1038 * Complex types 1039 ****************************************************************/ 1040 typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]; 1041 1042 1043 /*-************************************************************** 1044 * Templates 1045 ****************************************************************/ 1046 /* 1047 designed to be included 1048 for type-specific functions (template emulation in C) 1049 Objective is to write these functions only once, for improved maintenance 1050 */ 1051 1052 /* safety checks */ 1053 #ifndef FSE_FUNCTION_EXTENSION 1054 # error "FSE_FUNCTION_EXTENSION must be defined" 1055 #endif 1056 #ifndef FSE_FUNCTION_TYPE 1057 # error "FSE_FUNCTION_TYPE must be defined" 1058 #endif 1059 1060 /* Function names */ 1061 #define FSE_CAT(X,Y) X##Y 1062 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y) 1063 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y) 1064 1065 static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; } 1066 1067 1068 static size_t FSE_buildDTable(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) 1069 { 1070 FSE_DTableHeader DTableH; 1071 void* const tdPtr = dt+1; /* because dt is unsigned, 32-bits aligned on 32-bits */ 1072 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr); 1073 const U32 tableSize = 1 << tableLog; 1074 const U32 tableMask = tableSize-1; 1075 const U32 step = FSE_tableStep(tableSize); 1076 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1]; 1077 U32 position = 0; 1078 U32 highThreshold = tableSize-1; 1079 const S16 largeLimit= (S16)(1 << (tableLog-1)); 1080 U32 noLarge = 1; 1081 U32 s; 1082 1083 /* Sanity Checks */ 1084 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge); 1085 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); 1086 1087 /* Init, lay down lowprob symbols */ 1088 memset(tableDecode, 0, sizeof(FSE_DECODE_TYPE) * (maxSymbolValue+1) ); /* useless init, but keep static analyzer happy, and we don't need to performance optimize legacy decoders */ 1089 DTableH.tableLog = (U16)tableLog; 1090 for (s=0; s<=maxSymbolValue; s++) 1091 { 1092 if (normalizedCounter[s]==-1) 1093 { 1094 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s; 1095 symbolNext[s] = 1; 1096 } 1097 else 1098 { 1099 if (normalizedCounter[s] >= largeLimit) noLarge=0; 1100 symbolNext[s] = normalizedCounter[s]; 1101 } 1102 } 1103 1104 /* Spread symbols */ 1105 for (s=0; s<=maxSymbolValue; s++) 1106 { 1107 int i; 1108 for (i=0; i<normalizedCounter[s]; i++) 1109 { 1110 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s; 1111 position = (position + step) & tableMask; 1112 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */ 1113 } 1114 } 1115 1116 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ 1117 1118 /* Build Decoding table */ 1119 { 1120 U32 i; 1121 for (i=0; i<tableSize; i++) 1122 { 1123 FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol); 1124 U16 nextState = symbolNext[symbol]++; 1125 tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) ); 1126 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize); 1127 } 1128 } 1129 1130 DTableH.fastMode = (U16)noLarge; 1131 memcpy(dt, &DTableH, sizeof(DTableH)); 1132 return 0; 1133 } 1134 1135 1136 #ifndef FSE_COMMONDEFS_ONLY 1137 /****************************************** 1138 * FSE helper functions 1139 ******************************************/ 1140 static unsigned FSE_isError(size_t code) { return ERR_isError(code); } 1141 1142 1143 /**************************************************************** 1144 * FSE NCount encoding-decoding 1145 ****************************************************************/ 1146 static short FSE_abs(short a) 1147 { 1148 return a<0 ? -a : a; 1149 } 1150 1151 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr, 1152 const void* headerBuffer, size_t hbSize) 1153 { 1154 const BYTE* const istart = (const BYTE*) headerBuffer; 1155 const BYTE* const iend = istart + hbSize; 1156 const BYTE* ip = istart; 1157 int nbBits; 1158 int remaining; 1159 int threshold; 1160 U32 bitStream; 1161 int bitCount; 1162 unsigned charnum = 0; 1163 int previous0 = 0; 1164 1165 if (hbSize < 4) return ERROR(srcSize_wrong); 1166 bitStream = MEM_readLE32(ip); 1167 nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */ 1168 if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge); 1169 bitStream >>= 4; 1170 bitCount = 4; 1171 *tableLogPtr = nbBits; 1172 remaining = (1<<nbBits)+1; 1173 threshold = 1<<nbBits; 1174 nbBits++; 1175 1176 while ((remaining>1) && (charnum<=*maxSVPtr)) 1177 { 1178 if (previous0) 1179 { 1180 unsigned n0 = charnum; 1181 while ((bitStream & 0xFFFF) == 0xFFFF) 1182 { 1183 n0+=24; 1184 if (ip < iend-5) 1185 { 1186 ip+=2; 1187 bitStream = MEM_readLE32(ip) >> bitCount; 1188 } 1189 else 1190 { 1191 bitStream >>= 16; 1192 bitCount+=16; 1193 } 1194 } 1195 while ((bitStream & 3) == 3) 1196 { 1197 n0+=3; 1198 bitStream>>=2; 1199 bitCount+=2; 1200 } 1201 n0 += bitStream & 3; 1202 bitCount += 2; 1203 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall); 1204 while (charnum < n0) normalizedCounter[charnum++] = 0; 1205 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) 1206 { 1207 ip += bitCount>>3; 1208 bitCount &= 7; 1209 bitStream = MEM_readLE32(ip) >> bitCount; 1210 } 1211 else 1212 bitStream >>= 2; 1213 } 1214 { 1215 const short max = (short)((2*threshold-1)-remaining); 1216 short count; 1217 1218 if ((bitStream & (threshold-1)) < (U32)max) 1219 { 1220 count = (short)(bitStream & (threshold-1)); 1221 bitCount += nbBits-1; 1222 } 1223 else 1224 { 1225 count = (short)(bitStream & (2*threshold-1)); 1226 if (count >= threshold) count -= max; 1227 bitCount += nbBits; 1228 } 1229 1230 count--; /* extra accuracy */ 1231 remaining -= FSE_abs(count); 1232 normalizedCounter[charnum++] = count; 1233 previous0 = !count; 1234 while (remaining < threshold) 1235 { 1236 nbBits--; 1237 threshold >>= 1; 1238 } 1239 1240 { 1241 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) 1242 { 1243 ip += bitCount>>3; 1244 bitCount &= 7; 1245 } 1246 else 1247 { 1248 bitCount -= (int)(8 * (iend - 4 - ip)); 1249 ip = iend - 4; 1250 } 1251 bitStream = MEM_readLE32(ip) >> (bitCount & 31); 1252 } 1253 } 1254 } 1255 if (remaining != 1) return ERROR(GENERIC); 1256 *maxSVPtr = charnum-1; 1257 1258 ip += (bitCount+7)>>3; 1259 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong); 1260 return ip-istart; 1261 } 1262 1263 1264 /********************************************************* 1265 * Decompression (Byte symbols) 1266 *********************************************************/ 1267 static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue) 1268 { 1269 void* ptr = dt; 1270 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 1271 void* dPtr = dt + 1; 1272 FSE_decode_t* const cell = (FSE_decode_t*)dPtr; 1273 1274 DTableH->tableLog = 0; 1275 DTableH->fastMode = 0; 1276 1277 cell->newState = 0; 1278 cell->symbol = symbolValue; 1279 cell->nbBits = 0; 1280 1281 return 0; 1282 } 1283 1284 1285 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits) 1286 { 1287 void* ptr = dt; 1288 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 1289 void* dPtr = dt + 1; 1290 FSE_decode_t* const dinfo = (FSE_decode_t*)dPtr; 1291 const unsigned tableSize = 1 << nbBits; 1292 const unsigned tableMask = tableSize - 1; 1293 const unsigned maxSymbolValue = tableMask; 1294 unsigned s; 1295 1296 /* Sanity checks */ 1297 if (nbBits < 1) return ERROR(GENERIC); /* min size */ 1298 1299 /* Build Decoding Table */ 1300 DTableH->tableLog = (U16)nbBits; 1301 DTableH->fastMode = 1; 1302 for (s=0; s<=maxSymbolValue; s++) 1303 { 1304 dinfo[s].newState = 0; 1305 dinfo[s].symbol = (BYTE)s; 1306 dinfo[s].nbBits = (BYTE)nbBits; 1307 } 1308 1309 return 0; 1310 } 1311 1312 FORCE_INLINE size_t FSE_decompress_usingDTable_generic( 1313 void* dst, size_t maxDstSize, 1314 const void* cSrc, size_t cSrcSize, 1315 const FSE_DTable* dt, const unsigned fast) 1316 { 1317 BYTE* const ostart = (BYTE*) dst; 1318 BYTE* op = ostart; 1319 BYTE* const omax = op + maxDstSize; 1320 BYTE* const olimit = omax-3; 1321 1322 BIT_DStream_t bitD; 1323 FSE_DState_t state1; 1324 FSE_DState_t state2; 1325 size_t errorCode; 1326 1327 /* Init */ 1328 errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */ 1329 if (FSE_isError(errorCode)) return errorCode; 1330 1331 FSE_initDState(&state1, &bitD, dt); 1332 FSE_initDState(&state2, &bitD, dt); 1333 1334 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD) 1335 1336 /* 4 symbols per loop */ 1337 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4) 1338 { 1339 op[0] = FSE_GETSYMBOL(&state1); 1340 1341 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1342 BIT_reloadDStream(&bitD); 1343 1344 op[1] = FSE_GETSYMBOL(&state2); 1345 1346 if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1347 { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } } 1348 1349 op[2] = FSE_GETSYMBOL(&state1); 1350 1351 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1352 BIT_reloadDStream(&bitD); 1353 1354 op[3] = FSE_GETSYMBOL(&state2); 1355 } 1356 1357 /* tail */ 1358 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */ 1359 while (1) 1360 { 1361 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) ) 1362 break; 1363 1364 *op++ = FSE_GETSYMBOL(&state1); 1365 1366 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) ) 1367 break; 1368 1369 *op++ = FSE_GETSYMBOL(&state2); 1370 } 1371 1372 /* end ? */ 1373 if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2)) 1374 return op-ostart; 1375 1376 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */ 1377 1378 return ERROR(corruption_detected); 1379 } 1380 1381 1382 static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize, 1383 const void* cSrc, size_t cSrcSize, 1384 const FSE_DTable* dt) 1385 { 1386 FSE_DTableHeader DTableH; 1387 U32 fastMode; 1388 1389 memcpy(&DTableH, dt, sizeof(DTableH)); 1390 fastMode = DTableH.fastMode; 1391 1392 /* select fast mode (static) */ 1393 if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1); 1394 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0); 1395 } 1396 1397 1398 static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize) 1399 { 1400 const BYTE* const istart = (const BYTE*)cSrc; 1401 const BYTE* ip = istart; 1402 short counting[FSE_MAX_SYMBOL_VALUE+1]; 1403 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */ 1404 unsigned tableLog; 1405 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE; 1406 size_t errorCode; 1407 1408 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */ 1409 1410 /* normal FSE decoding mode */ 1411 errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize); 1412 if (FSE_isError(errorCode)) return errorCode; 1413 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */ 1414 ip += errorCode; 1415 cSrcSize -= errorCode; 1416 1417 errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog); 1418 if (FSE_isError(errorCode)) return errorCode; 1419 1420 /* always return, even if it is an error code */ 1421 return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); 1422 } 1423 1424 1425 1426 #endif /* FSE_COMMONDEFS_ONLY */ 1427 1428 1429 /* ****************************************************************** 1430 Huff0 : Huffman coder, part of New Generation Entropy library 1431 header file 1432 Copyright (C) 2013-2015, Yann Collet. 1433 1434 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1435 1436 Redistribution and use in source and binary forms, with or without 1437 modification, are permitted provided that the following conditions are 1438 met: 1439 1440 * Redistributions of source code must retain the above copyright 1441 notice, this list of conditions and the following disclaimer. 1442 * Redistributions in binary form must reproduce the above 1443 copyright notice, this list of conditions and the following disclaimer 1444 in the documentation and/or other materials provided with the 1445 distribution. 1446 1447 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1448 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1449 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1450 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1451 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1452 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1453 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1454 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1455 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1456 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1457 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1458 1459 You can contact the author at : 1460 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 1461 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1462 ****************************************************************** */ 1463 #ifndef HUFF0_H 1464 #define HUFF0_H 1465 1466 #if defined (__cplusplus) 1467 extern "C" { 1468 #endif 1469 1470 1471 /* **************************************** 1472 * Dependency 1473 ******************************************/ 1474 #include <stddef.h> /* size_t */ 1475 1476 1477 /* **************************************** 1478 * Huff0 simple functions 1479 ******************************************/ 1480 static size_t HUF_decompress(void* dst, size_t dstSize, 1481 const void* cSrc, size_t cSrcSize); 1482 /*! 1483 HUF_decompress(): 1484 Decompress Huff0 data from buffer 'cSrc', of size 'cSrcSize', 1485 into already allocated destination buffer 'dst', of size 'dstSize'. 1486 'dstSize' must be the exact size of original (uncompressed) data. 1487 Note : in contrast with FSE, HUF_decompress can regenerate RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, because it knows size to regenerate. 1488 @return : size of regenerated data (== dstSize) 1489 or an error code, which can be tested using HUF_isError() 1490 */ 1491 1492 1493 /* **************************************** 1494 * Tool functions 1495 ******************************************/ 1496 /* Error Management */ 1497 static unsigned HUF_isError(size_t code); /* tells if a return value is an error code */ 1498 1499 1500 #if defined (__cplusplus) 1501 } 1502 #endif 1503 1504 #endif /* HUFF0_H */ 1505 1506 1507 /* ****************************************************************** 1508 Huff0 : Huffman coder, part of New Generation Entropy library 1509 header file for static linking (only) 1510 Copyright (C) 2013-2015, Yann Collet 1511 1512 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1513 1514 Redistribution and use in source and binary forms, with or without 1515 modification, are permitted provided that the following conditions are 1516 met: 1517 1518 * Redistributions of source code must retain the above copyright 1519 notice, this list of conditions and the following disclaimer. 1520 * Redistributions in binary form must reproduce the above 1521 copyright notice, this list of conditions and the following disclaimer 1522 in the documentation and/or other materials provided with the 1523 distribution. 1524 1525 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1526 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1527 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1528 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1529 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1530 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1531 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1532 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1533 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1534 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1535 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1536 1537 You can contact the author at : 1538 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 1539 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1540 ****************************************************************** */ 1541 #ifndef HUFF0_STATIC_H 1542 #define HUFF0_STATIC_H 1543 1544 #if defined (__cplusplus) 1545 extern "C" { 1546 #endif 1547 1548 1549 1550 /* **************************************** 1551 * Static allocation macros 1552 ******************************************/ 1553 /* static allocation of Huff0's DTable */ 1554 #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */ 1555 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \ 1556 unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 1557 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \ 1558 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 1559 #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \ 1560 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog } 1561 1562 1563 /* **************************************** 1564 * Advanced decompression functions 1565 ******************************************/ 1566 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ 1567 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */ 1568 1569 1570 /* **************************************** 1571 * Huff0 detailed API 1572 ******************************************/ 1573 /*! 1574 HUF_decompress() does the following: 1575 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics 1576 2. build Huffman table from save, using HUF_readDTableXn() 1577 3. decode 1 or 4 segments in parallel using HUF_decompressSXn_usingDTable 1578 1579 */ 1580 static size_t HUF_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize); 1581 static size_t HUF_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize); 1582 1583 static size_t HUF_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable); 1584 static size_t HUF_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable); 1585 1586 1587 #if defined (__cplusplus) 1588 } 1589 #endif 1590 1591 #endif /* HUFF0_STATIC_H */ 1592 1593 1594 1595 /* ****************************************************************** 1596 Huff0 : Huffman coder, part of New Generation Entropy library 1597 Copyright (C) 2013-2015, Yann Collet. 1598 1599 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1600 1601 Redistribution and use in source and binary forms, with or without 1602 modification, are permitted provided that the following conditions are 1603 met: 1604 1605 * Redistributions of source code must retain the above copyright 1606 notice, this list of conditions and the following disclaimer. 1607 * Redistributions in binary form must reproduce the above 1608 copyright notice, this list of conditions and the following disclaimer 1609 in the documentation and/or other materials provided with the 1610 distribution. 1611 1612 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1613 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1614 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1615 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1616 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1617 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1618 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1619 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1620 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1621 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1622 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1623 1624 You can contact the author at : 1625 - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy 1626 ****************************************************************** */ 1627 1628 /* ************************************************************** 1629 * Compiler specifics 1630 ****************************************************************/ 1631 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 1632 /* inline is defined */ 1633 #elif defined(_MSC_VER) 1634 # define inline __inline 1635 #else 1636 # define inline /* disable inline */ 1637 #endif 1638 1639 1640 #ifdef _MSC_VER /* Visual Studio */ 1641 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 1642 #endif 1643 1644 1645 /* ************************************************************** 1646 * Includes 1647 ****************************************************************/ 1648 #include <stdlib.h> /* malloc, free, qsort */ 1649 #include <string.h> /* memcpy, memset */ 1650 #include <stdio.h> /* printf (debug) */ 1651 1652 1653 /* ************************************************************** 1654 * Constants 1655 ****************************************************************/ 1656 #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */ 1657 #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */ 1658 #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */ 1659 #define HUF_MAX_SYMBOL_VALUE 255 1660 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG) 1661 # error "HUF_MAX_TABLELOG is too large !" 1662 #endif 1663 1664 1665 /* ************************************************************** 1666 * Error Management 1667 ****************************************************************/ 1668 static unsigned HUF_isError(size_t code) { return ERR_isError(code); } 1669 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 1670 1671 1672 1673 /*-******************************************************* 1674 * Huff0 : Huffman block decompression 1675 *********************************************************/ 1676 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */ 1677 1678 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */ 1679 1680 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t; 1681 1682 /*! HUF_readStats 1683 Read compact Huffman tree, saved by HUF_writeCTable 1684 @huffWeight : destination buffer 1685 @return : size read from `src` 1686 */ 1687 static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats, 1688 U32* nbSymbolsPtr, U32* tableLogPtr, 1689 const void* src, size_t srcSize) 1690 { 1691 U32 weightTotal; 1692 U32 tableLog; 1693 const BYTE* ip = (const BYTE*) src; 1694 size_t iSize; 1695 size_t oSize; 1696 U32 n; 1697 1698 if (!srcSize) return ERROR(srcSize_wrong); 1699 iSize = ip[0]; 1700 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */ 1701 1702 if (iSize >= 128) /* special header */ 1703 { 1704 if (iSize >= (242)) /* RLE */ 1705 { 1706 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 }; 1707 oSize = l[iSize-242]; 1708 memset(huffWeight, 1, hwSize); 1709 iSize = 0; 1710 } 1711 else /* Incompressible */ 1712 { 1713 oSize = iSize - 127; 1714 iSize = ((oSize+1)/2); 1715 if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 1716 if (oSize >= hwSize) return ERROR(corruption_detected); 1717 ip += 1; 1718 for (n=0; n<oSize; n+=2) 1719 { 1720 huffWeight[n] = ip[n/2] >> 4; 1721 huffWeight[n+1] = ip[n/2] & 15; 1722 } 1723 } 1724 } 1725 else /* header compressed with FSE (normal case) */ 1726 { 1727 if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 1728 oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */ 1729 if (FSE_isError(oSize)) return oSize; 1730 } 1731 1732 /* collect weight stats */ 1733 memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32)); 1734 weightTotal = 0; 1735 for (n=0; n<oSize; n++) 1736 { 1737 if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 1738 rankStats[huffWeight[n]]++; 1739 weightTotal += (1 << huffWeight[n]) >> 1; 1740 } 1741 if (weightTotal == 0) return ERROR(corruption_detected); 1742 1743 /* get last non-null symbol weight (implied, total must be 2^n) */ 1744 tableLog = BIT_highbit32(weightTotal) + 1; 1745 if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 1746 { 1747 U32 total = 1 << tableLog; 1748 U32 rest = total - weightTotal; 1749 U32 verif = 1 << BIT_highbit32(rest); 1750 U32 lastWeight = BIT_highbit32(rest) + 1; 1751 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */ 1752 huffWeight[oSize] = (BYTE)lastWeight; 1753 rankStats[lastWeight]++; 1754 } 1755 1756 /* check tree construction validity */ 1757 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */ 1758 1759 /* results */ 1760 *nbSymbolsPtr = (U32)(oSize+1); 1761 *tableLogPtr = tableLog; 1762 return iSize+1; 1763 } 1764 1765 1766 /**************************/ 1767 /* single-symbol decoding */ 1768 /**************************/ 1769 1770 static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize) 1771 { 1772 BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1]; 1773 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */ 1774 U32 tableLog = 0; 1775 size_t iSize; 1776 U32 nbSymbols = 0; 1777 U32 n; 1778 U32 nextRankStart; 1779 void* const dtPtr = DTable + 1; 1780 HUF_DEltX2* const dt = (HUF_DEltX2*)dtPtr; 1781 1782 HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */ 1783 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */ 1784 1785 iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize); 1786 if (HUF_isError(iSize)) return iSize; 1787 1788 /* check result */ 1789 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */ 1790 DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */ 1791 1792 /* Prepare ranks */ 1793 nextRankStart = 0; 1794 for (n=1; n<=tableLog; n++) 1795 { 1796 U32 current = nextRankStart; 1797 nextRankStart += (rankVal[n] << (n-1)); 1798 rankVal[n] = current; 1799 } 1800 1801 /* fill DTable */ 1802 for (n=0; n<nbSymbols; n++) 1803 { 1804 const U32 w = huffWeight[n]; 1805 const U32 length = (1 << w) >> 1; 1806 U32 i; 1807 HUF_DEltX2 D; 1808 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w); 1809 for (i = rankVal[w]; i < rankVal[w] + length; i++) 1810 dt[i] = D; 1811 rankVal[w] += length; 1812 } 1813 1814 return iSize; 1815 } 1816 1817 static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog) 1818 { 1819 const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */ 1820 const BYTE c = dt[val].byte; 1821 BIT_skipBits(Dstream, dt[val].nbBits); 1822 return c; 1823 } 1824 1825 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \ 1826 *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog) 1827 1828 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \ 1829 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \ 1830 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 1831 1832 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \ 1833 if (MEM_64bits()) \ 1834 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 1835 1836 static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog) 1837 { 1838 BYTE* const pStart = p; 1839 1840 /* up to 4 symbols at a time */ 1841 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4)) 1842 { 1843 HUF_DECODE_SYMBOLX2_2(p, bitDPtr); 1844 HUF_DECODE_SYMBOLX2_1(p, bitDPtr); 1845 HUF_DECODE_SYMBOLX2_2(p, bitDPtr); 1846 HUF_DECODE_SYMBOLX2_0(p, bitDPtr); 1847 } 1848 1849 /* closer to the end */ 1850 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd)) 1851 HUF_DECODE_SYMBOLX2_0(p, bitDPtr); 1852 1853 /* no more data to retrieve from bitstream, hence no need to reload */ 1854 while (p < pEnd) 1855 HUF_DECODE_SYMBOLX2_0(p, bitDPtr); 1856 1857 return pEnd-pStart; 1858 } 1859 1860 1861 static size_t HUF_decompress4X2_usingDTable( 1862 void* dst, size_t dstSize, 1863 const void* cSrc, size_t cSrcSize, 1864 const U16* DTable) 1865 { 1866 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 1867 1868 { 1869 const BYTE* const istart = (const BYTE*) cSrc; 1870 BYTE* const ostart = (BYTE*) dst; 1871 BYTE* const oend = ostart + dstSize; 1872 const void* const dtPtr = DTable; 1873 const HUF_DEltX2* const dt = ((const HUF_DEltX2*)dtPtr) +1; 1874 const U32 dtLog = DTable[0]; 1875 size_t errorCode; 1876 1877 /* Init */ 1878 BIT_DStream_t bitD1; 1879 BIT_DStream_t bitD2; 1880 BIT_DStream_t bitD3; 1881 BIT_DStream_t bitD4; 1882 const size_t length1 = MEM_readLE16(istart); 1883 const size_t length2 = MEM_readLE16(istart+2); 1884 const size_t length3 = MEM_readLE16(istart+4); 1885 size_t length4; 1886 const BYTE* const istart1 = istart + 6; /* jumpTable */ 1887 const BYTE* const istart2 = istart1 + length1; 1888 const BYTE* const istart3 = istart2 + length2; 1889 const BYTE* const istart4 = istart3 + length3; 1890 const size_t segmentSize = (dstSize+3) / 4; 1891 BYTE* const opStart2 = ostart + segmentSize; 1892 BYTE* const opStart3 = opStart2 + segmentSize; 1893 BYTE* const opStart4 = opStart3 + segmentSize; 1894 BYTE* op1 = ostart; 1895 BYTE* op2 = opStart2; 1896 BYTE* op3 = opStart3; 1897 BYTE* op4 = opStart4; 1898 U32 endSignal; 1899 1900 length4 = cSrcSize - (length1 + length2 + length3 + 6); 1901 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 1902 errorCode = BIT_initDStream(&bitD1, istart1, length1); 1903 if (HUF_isError(errorCode)) return errorCode; 1904 errorCode = BIT_initDStream(&bitD2, istart2, length2); 1905 if (HUF_isError(errorCode)) return errorCode; 1906 errorCode = BIT_initDStream(&bitD3, istart3, length3); 1907 if (HUF_isError(errorCode)) return errorCode; 1908 errorCode = BIT_initDStream(&bitD4, istart4, length4); 1909 if (HUF_isError(errorCode)) return errorCode; 1910 1911 /* 16-32 symbols per loop (4-8 symbols per stream) */ 1912 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 1913 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; ) 1914 { 1915 HUF_DECODE_SYMBOLX2_2(op1, &bitD1); 1916 HUF_DECODE_SYMBOLX2_2(op2, &bitD2); 1917 HUF_DECODE_SYMBOLX2_2(op3, &bitD3); 1918 HUF_DECODE_SYMBOLX2_2(op4, &bitD4); 1919 HUF_DECODE_SYMBOLX2_1(op1, &bitD1); 1920 HUF_DECODE_SYMBOLX2_1(op2, &bitD2); 1921 HUF_DECODE_SYMBOLX2_1(op3, &bitD3); 1922 HUF_DECODE_SYMBOLX2_1(op4, &bitD4); 1923 HUF_DECODE_SYMBOLX2_2(op1, &bitD1); 1924 HUF_DECODE_SYMBOLX2_2(op2, &bitD2); 1925 HUF_DECODE_SYMBOLX2_2(op3, &bitD3); 1926 HUF_DECODE_SYMBOLX2_2(op4, &bitD4); 1927 HUF_DECODE_SYMBOLX2_0(op1, &bitD1); 1928 HUF_DECODE_SYMBOLX2_0(op2, &bitD2); 1929 HUF_DECODE_SYMBOLX2_0(op3, &bitD3); 1930 HUF_DECODE_SYMBOLX2_0(op4, &bitD4); 1931 1932 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 1933 } 1934 1935 /* check corruption */ 1936 if (op1 > opStart2) return ERROR(corruption_detected); 1937 if (op2 > opStart3) return ERROR(corruption_detected); 1938 if (op3 > opStart4) return ERROR(corruption_detected); 1939 /* note : op4 supposed already verified within main loop */ 1940 1941 /* finish bitStreams one by one */ 1942 HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog); 1943 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog); 1944 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog); 1945 HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog); 1946 1947 /* check */ 1948 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4); 1949 if (!endSignal) return ERROR(corruption_detected); 1950 1951 /* decoded size */ 1952 return dstSize; 1953 } 1954 } 1955 1956 1957 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 1958 { 1959 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG); 1960 const BYTE* ip = (const BYTE*) cSrc; 1961 size_t errorCode; 1962 1963 errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize); 1964 if (HUF_isError(errorCode)) return errorCode; 1965 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); 1966 ip += errorCode; 1967 cSrcSize -= errorCode; 1968 1969 return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 1970 } 1971 1972 1973 /***************************/ 1974 /* double-symbols decoding */ 1975 /***************************/ 1976 1977 static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed, 1978 const U32* rankValOrigin, const int minWeight, 1979 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize, 1980 U32 nbBitsBaseline, U16 baseSeq) 1981 { 1982 HUF_DEltX4 DElt; 1983 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; 1984 U32 s; 1985 1986 /* get pre-calculated rankVal */ 1987 memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 1988 1989 /* fill skipped values */ 1990 if (minWeight>1) 1991 { 1992 U32 i, skipSize = rankVal[minWeight]; 1993 MEM_writeLE16(&(DElt.sequence), baseSeq); 1994 DElt.nbBits = (BYTE)(consumed); 1995 DElt.length = 1; 1996 for (i = 0; i < skipSize; i++) 1997 DTable[i] = DElt; 1998 } 1999 2000 /* fill DTable */ 2001 for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */ 2002 { 2003 const U32 symbol = sortedSymbols[s].symbol; 2004 const U32 weight = sortedSymbols[s].weight; 2005 const U32 nbBits = nbBitsBaseline - weight; 2006 const U32 length = 1 << (sizeLog-nbBits); 2007 const U32 start = rankVal[weight]; 2008 U32 i = start; 2009 const U32 end = start + length; 2010 2011 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8))); 2012 DElt.nbBits = (BYTE)(nbBits + consumed); 2013 DElt.length = 2; 2014 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */ 2015 2016 rankVal[weight] += length; 2017 } 2018 } 2019 2020 typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1]; 2021 2022 static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog, 2023 const sortedSymbol_t* sortedList, const U32 sortedListSize, 2024 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight, 2025 const U32 nbBitsBaseline) 2026 { 2027 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; 2028 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */ 2029 const U32 minBits = nbBitsBaseline - maxWeight; 2030 U32 s; 2031 2032 memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 2033 2034 /* fill DTable */ 2035 for (s=0; s<sortedListSize; s++) 2036 { 2037 const U16 symbol = sortedList[s].symbol; 2038 const U32 weight = sortedList[s].weight; 2039 const U32 nbBits = nbBitsBaseline - weight; 2040 const U32 start = rankVal[weight]; 2041 const U32 length = 1 << (targetLog-nbBits); 2042 2043 if (targetLog-nbBits >= minBits) /* enough room for a second symbol */ 2044 { 2045 U32 sortedRank; 2046 int minWeight = nbBits + scaleLog; 2047 if (minWeight < 1) minWeight = 1; 2048 sortedRank = rankStart[minWeight]; 2049 HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits, 2050 rankValOrigin[nbBits], minWeight, 2051 sortedList+sortedRank, sortedListSize-sortedRank, 2052 nbBitsBaseline, symbol); 2053 } 2054 else 2055 { 2056 U32 i; 2057 const U32 end = start + length; 2058 HUF_DEltX4 DElt; 2059 2060 MEM_writeLE16(&(DElt.sequence), symbol); 2061 DElt.nbBits = (BYTE)(nbBits); 2062 DElt.length = 1; 2063 for (i = start; i < end; i++) 2064 DTable[i] = DElt; 2065 } 2066 rankVal[weight] += length; 2067 } 2068 } 2069 2070 static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize) 2071 { 2072 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1]; 2073 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1]; 2074 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 }; 2075 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 }; 2076 U32* const rankStart = rankStart0+1; 2077 rankVal_t rankVal; 2078 U32 tableLog, maxW, sizeOfSort, nbSymbols; 2079 const U32 memLog = DTable[0]; 2080 size_t iSize; 2081 void* dtPtr = DTable; 2082 HUF_DEltX4* const dt = ((HUF_DEltX4*)dtPtr) + 1; 2083 2084 HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */ 2085 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge); 2086 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */ 2087 2088 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize); 2089 if (HUF_isError(iSize)) return iSize; 2090 2091 /* check result */ 2092 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */ 2093 2094 /* find maxWeight */ 2095 for (maxW = tableLog; rankStats[maxW]==0; maxW--) 2096 { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */ 2097 2098 /* Get start index of each weight */ 2099 { 2100 U32 w, nextRankStart = 0; 2101 for (w=1; w<=maxW; w++) 2102 { 2103 U32 current = nextRankStart; 2104 nextRankStart += rankStats[w]; 2105 rankStart[w] = current; 2106 } 2107 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/ 2108 sizeOfSort = nextRankStart; 2109 } 2110 2111 /* sort symbols by weight */ 2112 { 2113 U32 s; 2114 for (s=0; s<nbSymbols; s++) 2115 { 2116 U32 w = weightList[s]; 2117 U32 r = rankStart[w]++; 2118 sortedSymbol[r].symbol = (BYTE)s; 2119 sortedSymbol[r].weight = (BYTE)w; 2120 } 2121 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */ 2122 } 2123 2124 /* Build rankVal */ 2125 { 2126 const U32 minBits = tableLog+1 - maxW; 2127 U32 nextRankVal = 0; 2128 U32 w, consumed; 2129 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */ 2130 U32* rankVal0 = rankVal[0]; 2131 for (w=1; w<=maxW; w++) 2132 { 2133 U32 current = nextRankVal; 2134 nextRankVal += rankStats[w] << (w+rescale); 2135 rankVal0[w] = current; 2136 } 2137 for (consumed = minBits; consumed <= memLog - minBits; consumed++) 2138 { 2139 U32* rankValPtr = rankVal[consumed]; 2140 for (w = 1; w <= maxW; w++) 2141 { 2142 rankValPtr[w] = rankVal0[w] >> consumed; 2143 } 2144 } 2145 } 2146 2147 HUF_fillDTableX4(dt, memLog, 2148 sortedSymbol, sizeOfSort, 2149 rankStart0, rankVal, maxW, 2150 tableLog+1); 2151 2152 return iSize; 2153 } 2154 2155 2156 static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog) 2157 { 2158 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 2159 memcpy(op, dt+val, 2); 2160 BIT_skipBits(DStream, dt[val].nbBits); 2161 return dt[val].length; 2162 } 2163 2164 static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog) 2165 { 2166 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 2167 memcpy(op, dt+val, 1); 2168 if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits); 2169 else 2170 { 2171 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) 2172 { 2173 BIT_skipBits(DStream, dt[val].nbBits); 2174 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8)) 2175 DStream->bitsConsumed = (sizeof(DStream->bitContainer)*8); /* ugly hack; works only because it's the last symbol. Note : can't easily extract nbBits from just this symbol */ 2176 } 2177 } 2178 return 1; 2179 } 2180 2181 2182 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \ 2183 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2184 2185 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \ 2186 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \ 2187 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2188 2189 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \ 2190 if (MEM_64bits()) \ 2191 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2192 2193 static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog) 2194 { 2195 BYTE* const pStart = p; 2196 2197 /* up to 8 symbols at a time */ 2198 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7)) 2199 { 2200 HUF_DECODE_SYMBOLX4_2(p, bitDPtr); 2201 HUF_DECODE_SYMBOLX4_1(p, bitDPtr); 2202 HUF_DECODE_SYMBOLX4_2(p, bitDPtr); 2203 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); 2204 } 2205 2206 /* closer to the end */ 2207 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2)) 2208 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); 2209 2210 while (p <= pEnd-2) 2211 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */ 2212 2213 if (p < pEnd) 2214 p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog); 2215 2216 return p-pStart; 2217 } 2218 2219 static size_t HUF_decompress4X4_usingDTable( 2220 void* dst, size_t dstSize, 2221 const void* cSrc, size_t cSrcSize, 2222 const U32* DTable) 2223 { 2224 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 2225 2226 { 2227 const BYTE* const istart = (const BYTE*) cSrc; 2228 BYTE* const ostart = (BYTE*) dst; 2229 BYTE* const oend = ostart + dstSize; 2230 const void* const dtPtr = DTable; 2231 const HUF_DEltX4* const dt = ((const HUF_DEltX4*)dtPtr) +1; 2232 const U32 dtLog = DTable[0]; 2233 size_t errorCode; 2234 2235 /* Init */ 2236 BIT_DStream_t bitD1; 2237 BIT_DStream_t bitD2; 2238 BIT_DStream_t bitD3; 2239 BIT_DStream_t bitD4; 2240 const size_t length1 = MEM_readLE16(istart); 2241 const size_t length2 = MEM_readLE16(istart+2); 2242 const size_t length3 = MEM_readLE16(istart+4); 2243 size_t length4; 2244 const BYTE* const istart1 = istart + 6; /* jumpTable */ 2245 const BYTE* const istart2 = istart1 + length1; 2246 const BYTE* const istart3 = istart2 + length2; 2247 const BYTE* const istart4 = istart3 + length3; 2248 const size_t segmentSize = (dstSize+3) / 4; 2249 BYTE* const opStart2 = ostart + segmentSize; 2250 BYTE* const opStart3 = opStart2 + segmentSize; 2251 BYTE* const opStart4 = opStart3 + segmentSize; 2252 BYTE* op1 = ostart; 2253 BYTE* op2 = opStart2; 2254 BYTE* op3 = opStart3; 2255 BYTE* op4 = opStart4; 2256 U32 endSignal; 2257 2258 length4 = cSrcSize - (length1 + length2 + length3 + 6); 2259 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 2260 errorCode = BIT_initDStream(&bitD1, istart1, length1); 2261 if (HUF_isError(errorCode)) return errorCode; 2262 errorCode = BIT_initDStream(&bitD2, istart2, length2); 2263 if (HUF_isError(errorCode)) return errorCode; 2264 errorCode = BIT_initDStream(&bitD3, istart3, length3); 2265 if (HUF_isError(errorCode)) return errorCode; 2266 errorCode = BIT_initDStream(&bitD4, istart4, length4); 2267 if (HUF_isError(errorCode)) return errorCode; 2268 2269 /* 16-32 symbols per loop (4-8 symbols per stream) */ 2270 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 2271 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; ) 2272 { 2273 HUF_DECODE_SYMBOLX4_2(op1, &bitD1); 2274 HUF_DECODE_SYMBOLX4_2(op2, &bitD2); 2275 HUF_DECODE_SYMBOLX4_2(op3, &bitD3); 2276 HUF_DECODE_SYMBOLX4_2(op4, &bitD4); 2277 HUF_DECODE_SYMBOLX4_1(op1, &bitD1); 2278 HUF_DECODE_SYMBOLX4_1(op2, &bitD2); 2279 HUF_DECODE_SYMBOLX4_1(op3, &bitD3); 2280 HUF_DECODE_SYMBOLX4_1(op4, &bitD4); 2281 HUF_DECODE_SYMBOLX4_2(op1, &bitD1); 2282 HUF_DECODE_SYMBOLX4_2(op2, &bitD2); 2283 HUF_DECODE_SYMBOLX4_2(op3, &bitD3); 2284 HUF_DECODE_SYMBOLX4_2(op4, &bitD4); 2285 HUF_DECODE_SYMBOLX4_0(op1, &bitD1); 2286 HUF_DECODE_SYMBOLX4_0(op2, &bitD2); 2287 HUF_DECODE_SYMBOLX4_0(op3, &bitD3); 2288 HUF_DECODE_SYMBOLX4_0(op4, &bitD4); 2289 2290 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 2291 } 2292 2293 /* check corruption */ 2294 if (op1 > opStart2) return ERROR(corruption_detected); 2295 if (op2 > opStart3) return ERROR(corruption_detected); 2296 if (op3 > opStart4) return ERROR(corruption_detected); 2297 /* note : op4 supposed already verified within main loop */ 2298 2299 /* finish bitStreams one by one */ 2300 HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog); 2301 HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog); 2302 HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog); 2303 HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog); 2304 2305 /* check */ 2306 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4); 2307 if (!endSignal) return ERROR(corruption_detected); 2308 2309 /* decoded size */ 2310 return dstSize; 2311 } 2312 } 2313 2314 2315 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2316 { 2317 HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG); 2318 const BYTE* ip = (const BYTE*) cSrc; 2319 2320 size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize); 2321 if (HUF_isError(hSize)) return hSize; 2322 if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 2323 ip += hSize; 2324 cSrcSize -= hSize; 2325 2326 return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2327 } 2328 2329 2330 /**********************************/ 2331 /* Generic decompression selector */ 2332 /**********************************/ 2333 2334 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t; 2335 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] = 2336 { 2337 /* single, double, quad */ 2338 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */ 2339 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */ 2340 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */ 2341 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */ 2342 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */ 2343 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */ 2344 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */ 2345 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */ 2346 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */ 2347 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */ 2348 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */ 2349 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */ 2350 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */ 2351 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */ 2352 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */ 2353 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */ 2354 }; 2355 2356 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); 2357 2358 static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2359 { 2360 static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL }; 2361 /* estimate decompression time */ 2362 U32 Q; 2363 const U32 D256 = (U32)(dstSize >> 8); 2364 U32 Dtime[3]; 2365 U32 algoNb = 0; 2366 int n; 2367 2368 /* validation checks */ 2369 if (dstSize == 0) return ERROR(dstSize_tooSmall); 2370 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */ 2371 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */ 2372 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */ 2373 2374 /* decoder timing evaluation */ 2375 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */ 2376 for (n=0; n<3; n++) 2377 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256); 2378 2379 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */ 2380 2381 if (Dtime[1] < Dtime[0]) algoNb = 1; 2382 2383 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize); 2384 2385 //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */ 2386 //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */ 2387 //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */ 2388 } 2389 2390 2391 2392 #endif /* ZSTD_CCOMMON_H_MODULE */ 2393 2394 2395 /* 2396 zstd - decompression module fo v0.4 legacy format 2397 Copyright (C) 2015-2016, Yann Collet. 2398 2399 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 2400 2401 Redistribution and use in source and binary forms, with or without 2402 modification, are permitted provided that the following conditions are 2403 met: 2404 * Redistributions of source code must retain the above copyright 2405 notice, this list of conditions and the following disclaimer. 2406 * Redistributions in binary form must reproduce the above 2407 copyright notice, this list of conditions and the following disclaimer 2408 in the documentation and/or other materials provided with the 2409 distribution. 2410 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2411 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2412 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2413 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2414 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2415 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2416 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2417 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2418 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2419 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2420 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2421 2422 You can contact the author at : 2423 - zstd source repository : https://github.com/Cyan4973/zstd 2424 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c 2425 */ 2426 2427 /* *************************************************************** 2428 * Tuning parameters 2429 *****************************************************************/ 2430 /*! 2431 * HEAPMODE : 2432 * Select how default decompression function ZSTD_decompress() will allocate memory, 2433 * in memory stack (0), or in memory heap (1, requires malloc()) 2434 */ 2435 #ifndef ZSTD_HEAPMODE 2436 # define ZSTD_HEAPMODE 1 2437 #endif 2438 2439 2440 /* ******************************************************* 2441 * Includes 2442 *********************************************************/ 2443 #include <stdlib.h> /* calloc */ 2444 #include <string.h> /* memcpy, memmove */ 2445 #include <stdio.h> /* debug : printf */ 2446 2447 2448 /* ******************************************************* 2449 * Compiler specifics 2450 *********************************************************/ 2451 #ifdef _MSC_VER /* Visual Studio */ 2452 # include <intrin.h> /* For Visual 2005 */ 2453 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 2454 # pragma warning(disable : 4324) /* disable: C4324: padded structure */ 2455 #endif 2456 2457 2458 /* ************************************* 2459 * Local types 2460 ***************************************/ 2461 typedef struct 2462 { 2463 blockType_t blockType; 2464 U32 origSize; 2465 } blockProperties_t; 2466 2467 2468 /* ******************************************************* 2469 * Memory operations 2470 **********************************************************/ 2471 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); } 2472 2473 2474 /* ************************************* 2475 * Error Management 2476 ***************************************/ 2477 2478 /*! ZSTD_isError 2479 * tells if a return value is an error code */ 2480 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); } 2481 2482 2483 /* ************************************************************* 2484 * Context management 2485 ***************************************************************/ 2486 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader, 2487 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock } ZSTD_dStage; 2488 2489 struct ZSTDv04_Dctx_s 2490 { 2491 U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)]; 2492 U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)]; 2493 U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)]; 2494 const void* previousDstEnd; 2495 const void* base; 2496 const void* vBase; 2497 const void* dictEnd; 2498 size_t expected; 2499 size_t headerSize; 2500 ZSTD_parameters params; 2501 blockType_t bType; 2502 ZSTD_dStage stage; 2503 const BYTE* litPtr; 2504 size_t litSize; 2505 BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */]; 2506 BYTE headerBuffer[ZSTD_frameHeaderSize_max]; 2507 }; /* typedef'd to ZSTD_DCtx within "zstd_static.h" */ 2508 2509 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx) 2510 { 2511 dctx->expected = ZSTD_frameHeaderSize_min; 2512 dctx->stage = ZSTDds_getFrameHeaderSize; 2513 dctx->previousDstEnd = NULL; 2514 dctx->base = NULL; 2515 dctx->vBase = NULL; 2516 dctx->dictEnd = NULL; 2517 return 0; 2518 } 2519 2520 static ZSTD_DCtx* ZSTD_createDCtx(void) 2521 { 2522 ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx)); 2523 if (dctx==NULL) return NULL; 2524 ZSTD_resetDCtx(dctx); 2525 return dctx; 2526 } 2527 2528 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx) 2529 { 2530 free(dctx); 2531 return 0; 2532 } 2533 2534 2535 /* ************************************************************* 2536 * Decompression section 2537 ***************************************************************/ 2538 /** ZSTD_decodeFrameHeader_Part1 2539 * decode the 1st part of the Frame Header, which tells Frame Header size. 2540 * srcSize must be == ZSTD_frameHeaderSize_min 2541 * @return : the full size of the Frame Header */ 2542 static size_t ZSTD_decodeFrameHeader_Part1(ZSTD_DCtx* zc, const void* src, size_t srcSize) 2543 { 2544 U32 magicNumber; 2545 if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong); 2546 magicNumber = MEM_readLE32(src); 2547 if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown); 2548 zc->headerSize = ZSTD_frameHeaderSize_min; 2549 return zc->headerSize; 2550 } 2551 2552 2553 static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize) 2554 { 2555 U32 magicNumber; 2556 if (srcSize < ZSTD_frameHeaderSize_min) return ZSTD_frameHeaderSize_max; 2557 magicNumber = MEM_readLE32(src); 2558 if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown); 2559 memset(params, 0, sizeof(*params)); 2560 params->windowLog = (((const BYTE*)src)[4] & 15) + ZSTD_WINDOWLOG_ABSOLUTEMIN; 2561 if ((((const BYTE*)src)[4] >> 4) != 0) return ERROR(frameParameter_unsupported); /* reserved bits */ 2562 return 0; 2563 } 2564 2565 /** ZSTD_decodeFrameHeader_Part2 2566 * decode the full Frame Header 2567 * srcSize must be the size provided by ZSTD_decodeFrameHeader_Part1 2568 * @return : 0, or an error code, which can be tested using ZSTD_isError() */ 2569 static size_t ZSTD_decodeFrameHeader_Part2(ZSTD_DCtx* zc, const void* src, size_t srcSize) 2570 { 2571 size_t result; 2572 if (srcSize != zc->headerSize) return ERROR(srcSize_wrong); 2573 result = ZSTD_getFrameParams(&(zc->params), src, srcSize); 2574 if ((MEM_32bits()) && (zc->params.windowLog > 25)) return ERROR(frameParameter_unsupported); 2575 return result; 2576 } 2577 2578 2579 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr) 2580 { 2581 const BYTE* const in = (const BYTE* const)src; 2582 BYTE headerFlags; 2583 U32 cSize; 2584 2585 if (srcSize < 3) return ERROR(srcSize_wrong); 2586 2587 headerFlags = *in; 2588 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16); 2589 2590 bpPtr->blockType = (blockType_t)(headerFlags >> 6); 2591 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0; 2592 2593 if (bpPtr->blockType == bt_end) return 0; 2594 if (bpPtr->blockType == bt_rle) return 1; 2595 return cSize; 2596 } 2597 2598 static size_t ZSTD_copyRawBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 2599 { 2600 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall); 2601 memcpy(dst, src, srcSize); 2602 return srcSize; 2603 } 2604 2605 2606 /** ZSTD_decompressLiterals 2607 @return : nb of bytes read from src, or an error code*/ 2608 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr, 2609 const void* src, size_t srcSize) 2610 { 2611 const BYTE* ip = (const BYTE*)src; 2612 2613 const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 2614 const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 2615 2616 if (litSize > *maxDstSizePtr) return ERROR(corruption_detected); 2617 if (litCSize + 5 > srcSize) return ERROR(corruption_detected); 2618 2619 if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected); 2620 2621 *maxDstSizePtr = litSize; 2622 return litCSize + 5; 2623 } 2624 2625 2626 /** ZSTD_decodeLiteralsBlock 2627 @return : nb of bytes read from src (< srcSize ) */ 2628 static size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx, 2629 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */ 2630 { 2631 const BYTE* const istart = (const BYTE*) src; 2632 2633 /* any compressed block with literals segment must be at least this size */ 2634 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected); 2635 2636 switch(*istart & 3) 2637 { 2638 /* compressed */ 2639 case 0: 2640 { 2641 size_t litSize = BLOCKSIZE; 2642 const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize); 2643 dctx->litPtr = dctx->litBuffer; 2644 dctx->litSize = litSize; 2645 memset(dctx->litBuffer + dctx->litSize, 0, 8); 2646 return readSize; /* works if it's an error too */ 2647 } 2648 case IS_RAW: 2649 { 2650 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 2651 if (litSize > srcSize-11) /* risk of reading too far with wildcopy */ 2652 { 2653 if (litSize > srcSize-3) return ERROR(corruption_detected); 2654 memcpy(dctx->litBuffer, istart, litSize); 2655 dctx->litPtr = dctx->litBuffer; 2656 dctx->litSize = litSize; 2657 memset(dctx->litBuffer + dctx->litSize, 0, 8); 2658 return litSize+3; 2659 } 2660 /* direct reference into compressed stream */ 2661 dctx->litPtr = istart+3; 2662 dctx->litSize = litSize; 2663 return litSize+3; } 2664 case IS_RLE: 2665 { 2666 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 2667 if (litSize > BLOCKSIZE) return ERROR(corruption_detected); 2668 memset(dctx->litBuffer, istart[3], litSize + 8); 2669 dctx->litPtr = dctx->litBuffer; 2670 dctx->litSize = litSize; 2671 return 4; 2672 } 2673 default: 2674 return ERROR(corruption_detected); /* forbidden nominal case */ 2675 } 2676 } 2677 2678 2679 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr, 2680 FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb, 2681 const void* src, size_t srcSize) 2682 { 2683 const BYTE* const istart = (const BYTE* const)src; 2684 const BYTE* ip = istart; 2685 const BYTE* const iend = istart + srcSize; 2686 U32 LLtype, Offtype, MLtype; 2687 U32 LLlog, Offlog, MLlog; 2688 size_t dumpsLength; 2689 2690 /* check */ 2691 if (srcSize < 5) return ERROR(srcSize_wrong); 2692 2693 /* SeqHead */ 2694 *nbSeq = MEM_readLE16(ip); ip+=2; 2695 LLtype = *ip >> 6; 2696 Offtype = (*ip >> 4) & 3; 2697 MLtype = (*ip >> 2) & 3; 2698 if (*ip & 2) 2699 { 2700 dumpsLength = ip[2]; 2701 dumpsLength += ip[1] << 8; 2702 ip += 3; 2703 } 2704 else 2705 { 2706 dumpsLength = ip[1]; 2707 dumpsLength += (ip[0] & 1) << 8; 2708 ip += 2; 2709 } 2710 *dumpsPtr = ip; 2711 ip += dumpsLength; 2712 *dumpsLengthPtr = dumpsLength; 2713 2714 /* check */ 2715 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */ 2716 2717 /* sequences */ 2718 { 2719 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL >= MaxOff */ 2720 size_t headerSize; 2721 2722 /* Build DTables */ 2723 switch(LLtype) 2724 { 2725 case bt_rle : 2726 LLlog = 0; 2727 FSE_buildDTable_rle(DTableLL, *ip++); break; 2728 case bt_raw : 2729 LLlog = LLbits; 2730 FSE_buildDTable_raw(DTableLL, LLbits); break; 2731 default : 2732 { U32 max = MaxLL; 2733 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip); 2734 if (FSE_isError(headerSize)) return ERROR(GENERIC); 2735 if (LLlog > LLFSELog) return ERROR(corruption_detected); 2736 ip += headerSize; 2737 FSE_buildDTable(DTableLL, norm, max, LLlog); 2738 } } 2739 2740 switch(Offtype) 2741 { 2742 case bt_rle : 2743 Offlog = 0; 2744 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 2745 FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */ 2746 break; 2747 case bt_raw : 2748 Offlog = Offbits; 2749 FSE_buildDTable_raw(DTableOffb, Offbits); break; 2750 default : 2751 { U32 max = MaxOff; 2752 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip); 2753 if (FSE_isError(headerSize)) return ERROR(GENERIC); 2754 if (Offlog > OffFSELog) return ERROR(corruption_detected); 2755 ip += headerSize; 2756 FSE_buildDTable(DTableOffb, norm, max, Offlog); 2757 } } 2758 2759 switch(MLtype) 2760 { 2761 case bt_rle : 2762 MLlog = 0; 2763 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 2764 FSE_buildDTable_rle(DTableML, *ip++); break; 2765 case bt_raw : 2766 MLlog = MLbits; 2767 FSE_buildDTable_raw(DTableML, MLbits); break; 2768 default : 2769 { U32 max = MaxML; 2770 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip); 2771 if (FSE_isError(headerSize)) return ERROR(GENERIC); 2772 if (MLlog > MLFSELog) return ERROR(corruption_detected); 2773 ip += headerSize; 2774 FSE_buildDTable(DTableML, norm, max, MLlog); 2775 } } } 2776 2777 return ip-istart; 2778 } 2779 2780 2781 typedef struct { 2782 size_t litLength; 2783 size_t offset; 2784 size_t matchLength; 2785 } seq_t; 2786 2787 typedef struct { 2788 BIT_DStream_t DStream; 2789 FSE_DState_t stateLL; 2790 FSE_DState_t stateOffb; 2791 FSE_DState_t stateML; 2792 size_t prevOffset; 2793 const BYTE* dumps; 2794 const BYTE* dumpsEnd; 2795 } seqState_t; 2796 2797 2798 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState) 2799 { 2800 size_t litLength; 2801 size_t prevOffset; 2802 size_t offset; 2803 size_t matchLength; 2804 const BYTE* dumps = seqState->dumps; 2805 const BYTE* const de = seqState->dumpsEnd; 2806 2807 /* Literal length */ 2808 litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream)); 2809 prevOffset = litLength ? seq->offset : seqState->prevOffset; 2810 if (litLength == MaxLL) { 2811 U32 add = *dumps++; 2812 if (add < 255) litLength += add; 2813 else { 2814 litLength = dumps[0] + (dumps[1]<<8) + (dumps[2]<<16); 2815 dumps += 3; 2816 } 2817 if (dumps > de) { litLength = MaxLL+255; } /* late correction, to avoid using uninitialized memory */ 2818 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */ 2819 } 2820 2821 /* Offset */ 2822 { static const U32 offsetPrefix[MaxOff+1] = { 2823 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256, 2824 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 2825 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 }; 2826 U32 offsetCode, nbBits; 2827 offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */ 2828 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream)); 2829 nbBits = offsetCode - 1; 2830 if (offsetCode==0) nbBits = 0; /* cmove */ 2831 offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits); 2832 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream)); 2833 if (offsetCode==0) offset = prevOffset; /* cmove */ 2834 if (offsetCode | !litLength) seqState->prevOffset = seq->offset; /* cmove */ 2835 } 2836 2837 /* MatchLength */ 2838 matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream)); 2839 if (matchLength == MaxML) { 2840 U32 add = *dumps++; 2841 if (add < 255) matchLength += add; 2842 else { 2843 matchLength = dumps[0] + (dumps[1]<<8) + (dumps[2]<<16); 2844 dumps += 3; 2845 } 2846 if (dumps > de) { matchLength = MaxML+255; } /* late correction, to avoid using uninitialized memory */ 2847 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */ 2848 } 2849 matchLength += MINMATCH; 2850 2851 /* save result */ 2852 seq->litLength = litLength; 2853 seq->offset = offset; 2854 seq->matchLength = matchLength; 2855 seqState->dumps = dumps; 2856 } 2857 2858 2859 static size_t ZSTD_execSequence(BYTE* op, 2860 BYTE* const oend, seq_t sequence, 2861 const BYTE** litPtr, const BYTE* const litLimit, 2862 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd) 2863 { 2864 static const int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */ 2865 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */ 2866 BYTE* const oLitEnd = op + sequence.litLength; 2867 const size_t sequenceLength = sequence.litLength + sequence.matchLength; 2868 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */ 2869 BYTE* const oend_8 = oend-8; 2870 const BYTE* const litEnd = *litPtr + sequence.litLength; 2871 const BYTE* match = oLitEnd - sequence.offset; 2872 2873 /* check */ 2874 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */ 2875 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */ 2876 if (litEnd > litLimit) return ERROR(corruption_detected); /* risk read beyond lit buffer */ 2877 2878 /* copy Literals */ 2879 ZSTD_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */ 2880 op = oLitEnd; 2881 *litPtr = litEnd; /* update for next sequence */ 2882 2883 /* copy Match */ 2884 if (sequence.offset > (size_t)(oLitEnd - base)) 2885 { 2886 /* offset beyond prefix */ 2887 if (sequence.offset > (size_t)(oLitEnd - vBase)) 2888 return ERROR(corruption_detected); 2889 match = dictEnd - (base-match); 2890 if (match + sequence.matchLength <= dictEnd) 2891 { 2892 memmove(oLitEnd, match, sequence.matchLength); 2893 return sequenceLength; 2894 } 2895 /* span extDict & currentPrefixSegment */ 2896 { 2897 size_t length1 = dictEnd - match; 2898 memmove(oLitEnd, match, length1); 2899 op = oLitEnd + length1; 2900 sequence.matchLength -= length1; 2901 match = base; 2902 if (op > oend_8 || sequence.matchLength < MINMATCH) { 2903 while (op < oMatchEnd) *op++ = *match++; 2904 return sequenceLength; 2905 } 2906 } 2907 } 2908 /* Requirement: op <= oend_8 */ 2909 2910 /* match within prefix */ 2911 if (sequence.offset < 8) { 2912 /* close range match, overlap */ 2913 const int sub2 = dec64table[sequence.offset]; 2914 op[0] = match[0]; 2915 op[1] = match[1]; 2916 op[2] = match[2]; 2917 op[3] = match[3]; 2918 match += dec32table[sequence.offset]; 2919 ZSTD_copy4(op+4, match); 2920 match -= sub2; 2921 } else { 2922 ZSTD_copy8(op, match); 2923 } 2924 op += 8; match += 8; 2925 2926 if (oMatchEnd > oend-(16-MINMATCH)) 2927 { 2928 if (op < oend_8) 2929 { 2930 ZSTD_wildcopy(op, match, oend_8 - op); 2931 match += oend_8 - op; 2932 op = oend_8; 2933 } 2934 while (op < oMatchEnd) *op++ = *match++; 2935 } 2936 else 2937 { 2938 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8, but must be signed */ 2939 } 2940 return sequenceLength; 2941 } 2942 2943 2944 static size_t ZSTD_decompressSequences( 2945 ZSTD_DCtx* dctx, 2946 void* dst, size_t maxDstSize, 2947 const void* seqStart, size_t seqSize) 2948 { 2949 const BYTE* ip = (const BYTE*)seqStart; 2950 const BYTE* const iend = ip + seqSize; 2951 BYTE* const ostart = (BYTE* const)dst; 2952 BYTE* op = ostart; 2953 BYTE* const oend = ostart + maxDstSize; 2954 size_t errorCode, dumpsLength; 2955 const BYTE* litPtr = dctx->litPtr; 2956 const BYTE* const litEnd = litPtr + dctx->litSize; 2957 int nbSeq; 2958 const BYTE* dumps; 2959 U32* DTableLL = dctx->LLTable; 2960 U32* DTableML = dctx->MLTable; 2961 U32* DTableOffb = dctx->OffTable; 2962 const BYTE* const base = (const BYTE*) (dctx->base); 2963 const BYTE* const vBase = (const BYTE*) (dctx->vBase); 2964 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd); 2965 2966 /* Build Decoding Tables */ 2967 errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength, 2968 DTableLL, DTableML, DTableOffb, 2969 ip, iend-ip); 2970 if (ZSTD_isError(errorCode)) return errorCode; 2971 ip += errorCode; 2972 2973 /* Regen sequences */ 2974 { 2975 seq_t sequence; 2976 seqState_t seqState; 2977 2978 memset(&sequence, 0, sizeof(sequence)); 2979 sequence.offset = 4; 2980 seqState.dumps = dumps; 2981 seqState.dumpsEnd = dumps + dumpsLength; 2982 seqState.prevOffset = 4; 2983 errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip); 2984 if (ERR_isError(errorCode)) return ERROR(corruption_detected); 2985 FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL); 2986 FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb); 2987 FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML); 2988 2989 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; ) 2990 { 2991 size_t oneSeqSize; 2992 nbSeq--; 2993 ZSTD_decodeSequence(&sequence, &seqState); 2994 oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd); 2995 if (ZSTD_isError(oneSeqSize)) return oneSeqSize; 2996 op += oneSeqSize; 2997 } 2998 2999 /* check if reached exact end */ 3000 if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* DStream should be entirely and exactly consumed; otherwise data is corrupted */ 3001 3002 /* last literal segment */ 3003 { 3004 size_t lastLLSize = litEnd - litPtr; 3005 if (litPtr > litEnd) return ERROR(corruption_detected); 3006 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall); 3007 if (op != litPtr) memcpy(op, litPtr, lastLLSize); 3008 op += lastLLSize; 3009 } 3010 } 3011 3012 return op-ostart; 3013 } 3014 3015 3016 static void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst) 3017 { 3018 if (dst != dctx->previousDstEnd) /* not contiguous */ 3019 { 3020 dctx->dictEnd = dctx->previousDstEnd; 3021 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); 3022 dctx->base = dst; 3023 dctx->previousDstEnd = dst; 3024 } 3025 } 3026 3027 3028 static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx, 3029 void* dst, size_t maxDstSize, 3030 const void* src, size_t srcSize) 3031 { 3032 /* blockType == blockCompressed */ 3033 const BYTE* ip = (const BYTE*)src; 3034 3035 /* Decode literals sub-block */ 3036 size_t litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize); 3037 if (ZSTD_isError(litCSize)) return litCSize; 3038 ip += litCSize; 3039 srcSize -= litCSize; 3040 3041 return ZSTD_decompressSequences(dctx, dst, maxDstSize, ip, srcSize); 3042 } 3043 3044 3045 static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx, 3046 void* dst, size_t maxDstSize, 3047 const void* src, size_t srcSize, 3048 const void* dict, size_t dictSize) 3049 { 3050 const BYTE* ip = (const BYTE*)src; 3051 const BYTE* iend = ip + srcSize; 3052 BYTE* const ostart = (BYTE* const)dst; 3053 BYTE* op = ostart; 3054 BYTE* const oend = ostart + maxDstSize; 3055 size_t remainingSize = srcSize; 3056 blockProperties_t blockProperties; 3057 3058 /* init */ 3059 ZSTD_resetDCtx(ctx); 3060 if (dict) 3061 { 3062 ZSTD_decompress_insertDictionary(ctx, dict, dictSize); 3063 ctx->dictEnd = ctx->previousDstEnd; 3064 ctx->vBase = (const char*)dst - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base)); 3065 ctx->base = dst; 3066 } 3067 else 3068 { 3069 ctx->vBase = ctx->base = ctx->dictEnd = dst; 3070 } 3071 3072 /* Frame Header */ 3073 { 3074 size_t frameHeaderSize; 3075 if (srcSize < ZSTD_frameHeaderSize_min+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong); 3076 frameHeaderSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min); 3077 if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize; 3078 if (srcSize < frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong); 3079 ip += frameHeaderSize; remainingSize -= frameHeaderSize; 3080 frameHeaderSize = ZSTD_decodeFrameHeader_Part2(ctx, src, frameHeaderSize); 3081 if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize; 3082 } 3083 3084 /* Loop on each block */ 3085 while (1) 3086 { 3087 size_t decodedSize=0; 3088 size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties); 3089 if (ZSTD_isError(cBlockSize)) return cBlockSize; 3090 3091 ip += ZSTD_blockHeaderSize; 3092 remainingSize -= ZSTD_blockHeaderSize; 3093 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); 3094 3095 switch(blockProperties.blockType) 3096 { 3097 case bt_compressed: 3098 decodedSize = ZSTD_decompressBlock_internal(ctx, op, oend-op, ip, cBlockSize); 3099 break; 3100 case bt_raw : 3101 decodedSize = ZSTD_copyRawBlock(op, oend-op, ip, cBlockSize); 3102 break; 3103 case bt_rle : 3104 return ERROR(GENERIC); /* not yet supported */ 3105 break; 3106 case bt_end : 3107 /* end of frame */ 3108 if (remainingSize) return ERROR(srcSize_wrong); 3109 break; 3110 default: 3111 return ERROR(GENERIC); /* impossible */ 3112 } 3113 if (cBlockSize == 0) break; /* bt_end */ 3114 3115 if (ZSTD_isError(decodedSize)) return decodedSize; 3116 op += decodedSize; 3117 ip += cBlockSize; 3118 remainingSize -= cBlockSize; 3119 } 3120 3121 return op-ostart; 3122 } 3123 3124 /* ZSTD_errorFrameSizeInfoLegacy() : 3125 assumes `cSize` and `dBound` are _not_ NULL */ 3126 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret) 3127 { 3128 *cSize = ret; 3129 *dBound = ZSTD_CONTENTSIZE_ERROR; 3130 } 3131 3132 void ZSTDv04_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound) 3133 { 3134 const BYTE* ip = (const BYTE*)src; 3135 size_t remainingSize = srcSize; 3136 size_t nbBlocks = 0; 3137 blockProperties_t blockProperties; 3138 3139 /* Frame Header */ 3140 if (srcSize < ZSTD_frameHeaderSize_min) { 3141 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 3142 return; 3143 } 3144 if (MEM_readLE32(src) != ZSTD_MAGICNUMBER) { 3145 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown)); 3146 return; 3147 } 3148 ip += ZSTD_frameHeaderSize_min; remainingSize -= ZSTD_frameHeaderSize_min; 3149 3150 /* Loop on each block */ 3151 while (1) 3152 { 3153 size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties); 3154 if (ZSTD_isError(cBlockSize)) { 3155 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize); 3156 return; 3157 } 3158 3159 ip += ZSTD_blockHeaderSize; 3160 remainingSize -= ZSTD_blockHeaderSize; 3161 if (cBlockSize > remainingSize) { 3162 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 3163 return; 3164 } 3165 3166 if (cBlockSize == 0) break; /* bt_end */ 3167 3168 ip += cBlockSize; 3169 remainingSize -= cBlockSize; 3170 nbBlocks++; 3171 } 3172 3173 *cSize = ip - (const BYTE*)src; 3174 *dBound = nbBlocks * BLOCKSIZE; 3175 } 3176 3177 /* ****************************** 3178 * Streaming Decompression API 3179 ********************************/ 3180 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx) 3181 { 3182 return dctx->expected; 3183 } 3184 3185 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3186 { 3187 /* Sanity check */ 3188 if (srcSize != ctx->expected) return ERROR(srcSize_wrong); 3189 ZSTD_checkContinuity(ctx, dst); 3190 3191 /* Decompress : frame header; part 1 */ 3192 switch (ctx->stage) 3193 { 3194 case ZSTDds_getFrameHeaderSize : 3195 /* get frame header size */ 3196 if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */ 3197 ctx->headerSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min); 3198 if (ZSTD_isError(ctx->headerSize)) return ctx->headerSize; 3199 memcpy(ctx->headerBuffer, src, ZSTD_frameHeaderSize_min); 3200 if (ctx->headerSize > ZSTD_frameHeaderSize_min) return ERROR(GENERIC); /* impossible */ 3201 ctx->expected = 0; /* not necessary to copy more */ 3202 /* fallthrough */ 3203 case ZSTDds_decodeFrameHeader: 3204 /* get frame header */ 3205 { size_t const result = ZSTD_decodeFrameHeader_Part2(ctx, ctx->headerBuffer, ctx->headerSize); 3206 if (ZSTD_isError(result)) return result; 3207 ctx->expected = ZSTD_blockHeaderSize; 3208 ctx->stage = ZSTDds_decodeBlockHeader; 3209 return 0; 3210 } 3211 case ZSTDds_decodeBlockHeader: 3212 /* Decode block header */ 3213 { blockProperties_t bp; 3214 size_t const blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp); 3215 if (ZSTD_isError(blockSize)) return blockSize; 3216 if (bp.blockType == bt_end) 3217 { 3218 ctx->expected = 0; 3219 ctx->stage = ZSTDds_getFrameHeaderSize; 3220 } 3221 else 3222 { 3223 ctx->expected = blockSize; 3224 ctx->bType = bp.blockType; 3225 ctx->stage = ZSTDds_decompressBlock; 3226 } 3227 return 0; 3228 } 3229 case ZSTDds_decompressBlock: 3230 { 3231 /* Decompress : block content */ 3232 size_t rSize; 3233 switch(ctx->bType) 3234 { 3235 case bt_compressed: 3236 rSize = ZSTD_decompressBlock_internal(ctx, dst, maxDstSize, src, srcSize); 3237 break; 3238 case bt_raw : 3239 rSize = ZSTD_copyRawBlock(dst, maxDstSize, src, srcSize); 3240 break; 3241 case bt_rle : 3242 return ERROR(GENERIC); /* not yet handled */ 3243 break; 3244 case bt_end : /* should never happen (filtered at phase 1) */ 3245 rSize = 0; 3246 break; 3247 default: 3248 return ERROR(GENERIC); 3249 } 3250 ctx->stage = ZSTDds_decodeBlockHeader; 3251 ctx->expected = ZSTD_blockHeaderSize; 3252 ctx->previousDstEnd = (char*)dst + rSize; 3253 return rSize; 3254 } 3255 default: 3256 return ERROR(GENERIC); /* impossible */ 3257 } 3258 } 3259 3260 3261 static void ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* dict, size_t dictSize) 3262 { 3263 ctx->dictEnd = ctx->previousDstEnd; 3264 ctx->vBase = (const char*)dict - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base)); 3265 ctx->base = dict; 3266 ctx->previousDstEnd = (const char*)dict + dictSize; 3267 } 3268 3269 3270 3271 /* 3272 Buffered version of Zstd compression library 3273 Copyright (C) 2015, Yann Collet. 3274 3275 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 3276 3277 Redistribution and use in source and binary forms, with or without 3278 modification, are permitted provided that the following conditions are 3279 met: 3280 * Redistributions of source code must retain the above copyright 3281 notice, this list of conditions and the following disclaimer. 3282 * Redistributions in binary form must reproduce the above 3283 copyright notice, this list of conditions and the following disclaimer 3284 in the documentation and/or other materials provided with the 3285 distribution. 3286 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 3287 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 3288 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 3289 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 3290 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3291 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3292 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3293 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3294 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3295 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3296 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3297 3298 You can contact the author at : 3299 - zstd source repository : https://github.com/Cyan4973/zstd 3300 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c 3301 */ 3302 3303 /* The objects defined into this file should be considered experimental. 3304 * They are not labelled stable, as their prototype may change in the future. 3305 * You can use them for tests, provide feedback, or if you can endure risk of future changes. 3306 */ 3307 3308 /* ************************************* 3309 * Includes 3310 ***************************************/ 3311 #include <stdlib.h> 3312 3313 3314 /** ************************************************ 3315 * Streaming decompression 3316 * 3317 * A ZBUFF_DCtx object is required to track streaming operation. 3318 * Use ZBUFF_createDCtx() and ZBUFF_freeDCtx() to create/release resources. 3319 * Use ZBUFF_decompressInit() to start a new decompression operation. 3320 * ZBUFF_DCtx objects can be reused multiple times. 3321 * 3322 * Use ZBUFF_decompressContinue() repetitively to consume your input. 3323 * *srcSizePtr and *maxDstSizePtr can be any size. 3324 * The function will report how many bytes were read or written by modifying *srcSizePtr and *maxDstSizePtr. 3325 * Note that it may not consume the entire input, in which case it's up to the caller to call again the function with remaining input. 3326 * The content of dst will be overwritten (up to *maxDstSizePtr) at each function call, so save its content if it matters or change dst . 3327 * return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency) 3328 * or 0 when a frame is completely decoded 3329 * or an error code, which can be tested using ZBUFF_isError(). 3330 * 3331 * Hint : recommended buffer sizes (not compulsory) 3332 * output : 128 KB block size is the internal unit, it ensures it's always possible to write a full block when it's decoded. 3333 * input : just follow indications from ZBUFF_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 . 3334 * **************************************************/ 3335 3336 typedef enum { ZBUFFds_init, ZBUFFds_readHeader, ZBUFFds_loadHeader, ZBUFFds_decodeHeader, 3337 ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFF_dStage; 3338 3339 /* *** Resource management *** */ 3340 3341 #define ZSTD_frameHeaderSize_max 5 /* too magical, should come from reference */ 3342 struct ZBUFFv04_DCtx_s { 3343 ZSTD_DCtx* zc; 3344 ZSTD_parameters params; 3345 char* inBuff; 3346 size_t inBuffSize; 3347 size_t inPos; 3348 char* outBuff; 3349 size_t outBuffSize; 3350 size_t outStart; 3351 size_t outEnd; 3352 size_t hPos; 3353 const char* dict; 3354 size_t dictSize; 3355 ZBUFF_dStage stage; 3356 unsigned char headerBuffer[ZSTD_frameHeaderSize_max]; 3357 }; /* typedef'd to ZBUFF_DCtx within "zstd_buffered.h" */ 3358 3359 typedef ZBUFFv04_DCtx ZBUFF_DCtx; 3360 3361 3362 static ZBUFF_DCtx* ZBUFF_createDCtx(void) 3363 { 3364 ZBUFF_DCtx* zbc = (ZBUFF_DCtx*)malloc(sizeof(ZBUFF_DCtx)); 3365 if (zbc==NULL) return NULL; 3366 memset(zbc, 0, sizeof(*zbc)); 3367 zbc->zc = ZSTD_createDCtx(); 3368 zbc->stage = ZBUFFds_init; 3369 return zbc; 3370 } 3371 3372 static size_t ZBUFF_freeDCtx(ZBUFF_DCtx* zbc) 3373 { 3374 if (zbc==NULL) return 0; /* support free on null */ 3375 ZSTD_freeDCtx(zbc->zc); 3376 free(zbc->inBuff); 3377 free(zbc->outBuff); 3378 free(zbc); 3379 return 0; 3380 } 3381 3382 3383 /* *** Initialization *** */ 3384 3385 static size_t ZBUFF_decompressInit(ZBUFF_DCtx* zbc) 3386 { 3387 zbc->stage = ZBUFFds_readHeader; 3388 zbc->hPos = zbc->inPos = zbc->outStart = zbc->outEnd = zbc->dictSize = 0; 3389 return ZSTD_resetDCtx(zbc->zc); 3390 } 3391 3392 3393 static size_t ZBUFF_decompressWithDictionary(ZBUFF_DCtx* zbc, const void* src, size_t srcSize) 3394 { 3395 zbc->dict = (const char*)src; 3396 zbc->dictSize = srcSize; 3397 return 0; 3398 } 3399 3400 static size_t ZBUFF_limitCopy(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3401 { 3402 size_t length = MIN(maxDstSize, srcSize); 3403 memcpy(dst, src, length); 3404 return length; 3405 } 3406 3407 /* *** Decompression *** */ 3408 3409 static size_t ZBUFF_decompressContinue(ZBUFF_DCtx* zbc, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr) 3410 { 3411 const char* const istart = (const char*)src; 3412 const char* ip = istart; 3413 const char* const iend = istart + *srcSizePtr; 3414 char* const ostart = (char*)dst; 3415 char* op = ostart; 3416 char* const oend = ostart + *maxDstSizePtr; 3417 U32 notDone = 1; 3418 3419 DEBUGLOG(5, "ZBUFF_decompressContinue"); 3420 while (notDone) 3421 { 3422 switch(zbc->stage) 3423 { 3424 3425 case ZBUFFds_init : 3426 DEBUGLOG(5, "ZBUFF_decompressContinue: stage==ZBUFFds_init => ERROR(init_missing)"); 3427 return ERROR(init_missing); 3428 3429 case ZBUFFds_readHeader : 3430 /* read header from src */ 3431 { size_t const headerSize = ZSTD_getFrameParams(&(zbc->params), src, *srcSizePtr); 3432 if (ZSTD_isError(headerSize)) return headerSize; 3433 if (headerSize) { 3434 /* not enough input to decode header : tell how many bytes would be necessary */ 3435 memcpy(zbc->headerBuffer+zbc->hPos, src, *srcSizePtr); 3436 zbc->hPos += *srcSizePtr; 3437 *maxDstSizePtr = 0; 3438 zbc->stage = ZBUFFds_loadHeader; 3439 return headerSize - zbc->hPos; 3440 } 3441 zbc->stage = ZBUFFds_decodeHeader; 3442 break; 3443 } 3444 3445 case ZBUFFds_loadHeader: 3446 /* complete header from src */ 3447 { size_t headerSize = ZBUFF_limitCopy( 3448 zbc->headerBuffer + zbc->hPos, ZSTD_frameHeaderSize_max - zbc->hPos, 3449 src, *srcSizePtr); 3450 zbc->hPos += headerSize; 3451 ip += headerSize; 3452 headerSize = ZSTD_getFrameParams(&(zbc->params), zbc->headerBuffer, zbc->hPos); 3453 if (ZSTD_isError(headerSize)) return headerSize; 3454 if (headerSize) { 3455 /* not enough input to decode header : tell how many bytes would be necessary */ 3456 *maxDstSizePtr = 0; 3457 return headerSize - zbc->hPos; 3458 } } 3459 /* intentional fallthrough */ 3460 3461 case ZBUFFds_decodeHeader: 3462 /* apply header to create / resize buffers */ 3463 { size_t const neededOutSize = (size_t)1 << zbc->params.windowLog; 3464 size_t const neededInSize = BLOCKSIZE; /* a block is never > BLOCKSIZE */ 3465 if (zbc->inBuffSize < neededInSize) { 3466 free(zbc->inBuff); 3467 zbc->inBuffSize = neededInSize; 3468 zbc->inBuff = (char*)malloc(neededInSize); 3469 if (zbc->inBuff == NULL) return ERROR(memory_allocation); 3470 } 3471 if (zbc->outBuffSize < neededOutSize) { 3472 free(zbc->outBuff); 3473 zbc->outBuffSize = neededOutSize; 3474 zbc->outBuff = (char*)malloc(neededOutSize); 3475 if (zbc->outBuff == NULL) return ERROR(memory_allocation); 3476 } } 3477 if (zbc->dictSize) 3478 ZSTD_decompress_insertDictionary(zbc->zc, zbc->dict, zbc->dictSize); 3479 if (zbc->hPos) { 3480 /* some data already loaded into headerBuffer : transfer into inBuff */ 3481 memcpy(zbc->inBuff, zbc->headerBuffer, zbc->hPos); 3482 zbc->inPos = zbc->hPos; 3483 zbc->hPos = 0; 3484 zbc->stage = ZBUFFds_load; 3485 break; 3486 } 3487 zbc->stage = ZBUFFds_read; 3488 /* fall-through */ 3489 case ZBUFFds_read: 3490 { 3491 size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc); 3492 if (neededInSize==0) /* end of frame */ 3493 { 3494 zbc->stage = ZBUFFds_init; 3495 notDone = 0; 3496 break; 3497 } 3498 if ((size_t)(iend-ip) >= neededInSize) 3499 { 3500 /* directly decode from src */ 3501 size_t decodedSize = ZSTD_decompressContinue(zbc->zc, 3502 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart, 3503 ip, neededInSize); 3504 if (ZSTD_isError(decodedSize)) return decodedSize; 3505 ip += neededInSize; 3506 if (!decodedSize) break; /* this was just a header */ 3507 zbc->outEnd = zbc->outStart + decodedSize; 3508 zbc->stage = ZBUFFds_flush; 3509 break; 3510 } 3511 if (ip==iend) { notDone = 0; break; } /* no more input */ 3512 zbc->stage = ZBUFFds_load; 3513 } 3514 /* fall-through */ 3515 case ZBUFFds_load: 3516 { 3517 size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc); 3518 size_t toLoad = neededInSize - zbc->inPos; /* should always be <= remaining space within inBuff */ 3519 size_t loadedSize; 3520 if (toLoad > zbc->inBuffSize - zbc->inPos) return ERROR(corruption_detected); /* should never happen */ 3521 loadedSize = ZBUFF_limitCopy(zbc->inBuff + zbc->inPos, toLoad, ip, iend-ip); 3522 ip += loadedSize; 3523 zbc->inPos += loadedSize; 3524 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */ 3525 { 3526 size_t decodedSize = ZSTD_decompressContinue(zbc->zc, 3527 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart, 3528 zbc->inBuff, neededInSize); 3529 if (ZSTD_isError(decodedSize)) return decodedSize; 3530 zbc->inPos = 0; /* input is consumed */ 3531 if (!decodedSize) { zbc->stage = ZBUFFds_read; break; } /* this was just a header */ 3532 zbc->outEnd = zbc->outStart + decodedSize; 3533 zbc->stage = ZBUFFds_flush; 3534 /* ZBUFFds_flush follows */ 3535 } 3536 } 3537 /* fall-through */ 3538 case ZBUFFds_flush: 3539 { 3540 size_t toFlushSize = zbc->outEnd - zbc->outStart; 3541 size_t flushedSize = ZBUFF_limitCopy(op, oend-op, zbc->outBuff + zbc->outStart, toFlushSize); 3542 op += flushedSize; 3543 zbc->outStart += flushedSize; 3544 if (flushedSize == toFlushSize) 3545 { 3546 zbc->stage = ZBUFFds_read; 3547 if (zbc->outStart + BLOCKSIZE > zbc->outBuffSize) 3548 zbc->outStart = zbc->outEnd = 0; 3549 break; 3550 } 3551 /* cannot flush everything */ 3552 notDone = 0; 3553 break; 3554 } 3555 default: return ERROR(GENERIC); /* impossible */ 3556 } 3557 } 3558 3559 *srcSizePtr = ip-istart; 3560 *maxDstSizePtr = op-ostart; 3561 3562 { 3563 size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zbc->zc); 3564 if (nextSrcSizeHint > 3) nextSrcSizeHint+= 3; /* get the next block header while at it */ 3565 nextSrcSizeHint -= zbc->inPos; /* already loaded*/ 3566 return nextSrcSizeHint; 3567 } 3568 } 3569 3570 3571 /* ************************************* 3572 * Tool functions 3573 ***************************************/ 3574 unsigned ZBUFFv04_isError(size_t errorCode) { return ERR_isError(errorCode); } 3575 const char* ZBUFFv04_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); } 3576 3577 size_t ZBUFFv04_recommendedDInSize() { return BLOCKSIZE + 3; } 3578 size_t ZBUFFv04_recommendedDOutSize() { return BLOCKSIZE; } 3579 3580 3581 3582 /*- ========================================================================= -*/ 3583 3584 /* final wrapping stage */ 3585 3586 size_t ZSTDv04_decompressDCtx(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3587 { 3588 return ZSTD_decompress_usingDict(dctx, dst, maxDstSize, src, srcSize, NULL, 0); 3589 } 3590 3591 size_t ZSTDv04_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3592 { 3593 #if defined(ZSTD_HEAPMODE) && (ZSTD_HEAPMODE==1) 3594 size_t regenSize; 3595 ZSTD_DCtx* dctx = ZSTD_createDCtx(); 3596 if (dctx==NULL) return ERROR(memory_allocation); 3597 regenSize = ZSTDv04_decompressDCtx(dctx, dst, maxDstSize, src, srcSize); 3598 ZSTD_freeDCtx(dctx); 3599 return regenSize; 3600 #else 3601 ZSTD_DCtx dctx; 3602 return ZSTDv04_decompressDCtx(&dctx, dst, maxDstSize, src, srcSize); 3603 #endif 3604 } 3605 3606 size_t ZSTDv04_resetDCtx(ZSTDv04_Dctx* dctx) { return ZSTD_resetDCtx(dctx); } 3607 3608 size_t ZSTDv04_nextSrcSizeToDecompress(ZSTDv04_Dctx* dctx) 3609 { 3610 return ZSTD_nextSrcSizeToDecompress(dctx); 3611 } 3612 3613 size_t ZSTDv04_decompressContinue(ZSTDv04_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3614 { 3615 return ZSTD_decompressContinue(dctx, dst, maxDstSize, src, srcSize); 3616 } 3617 3618 3619 3620 ZBUFFv04_DCtx* ZBUFFv04_createDCtx(void) { return ZBUFF_createDCtx(); } 3621 size_t ZBUFFv04_freeDCtx(ZBUFFv04_DCtx* dctx) { return ZBUFF_freeDCtx(dctx); } 3622 3623 size_t ZBUFFv04_decompressInit(ZBUFFv04_DCtx* dctx) { return ZBUFF_decompressInit(dctx); } 3624 size_t ZBUFFv04_decompressWithDictionary(ZBUFFv04_DCtx* dctx, const void* src, size_t srcSize) 3625 { return ZBUFF_decompressWithDictionary(dctx, src, srcSize); } 3626 3627 size_t ZBUFFv04_decompressContinue(ZBUFFv04_DCtx* dctx, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr) 3628 { 3629 DEBUGLOG(5, "ZBUFFv04_decompressContinue"); 3630 return ZBUFF_decompressContinue(dctx, dst, maxDstSizePtr, src, srcSizePtr); 3631 } 3632 3633 ZSTD_DCtx* ZSTDv04_createDCtx(void) { return ZSTD_createDCtx(); } 3634 size_t ZSTDv04_freeDCtx(ZSTD_DCtx* dctx) { return ZSTD_freeDCtx(dctx); } 3635