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