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