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