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