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