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