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) 55extern "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 127MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; } 128MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; } 129 130MEM_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. 139Only use if no other choice to achieve best performance on target platform */ 140MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; } 141MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; } 142MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; } 143 144MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; } 145MEM_STATIC void MEM_write32(void* memPtr, U32 value) { *(U32*)memPtr = value; } 146MEM_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 */ 152typedef union { U16 u16; U32 u32; U64 u64; size_t st; } __attribute__((packed)) unalign; 153 154MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; } 155MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } 156MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; } 157 158MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; } 159MEM_STATIC void MEM_write32(void* memPtr, U32 value) { ((unalign*)memPtr)->u32 = value; } 160MEM_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 167MEM_STATIC U16 MEM_read16(const void* memPtr) 168{ 169 U16 val; memcpy(&val, memPtr, sizeof(val)); return val; 170} 171 172MEM_STATIC U32 MEM_read32(const void* memPtr) 173{ 174 U32 val; memcpy(&val, memPtr, sizeof(val)); return val; 175} 176 177MEM_STATIC U64 MEM_read64(const void* memPtr) 178{ 179 U64 val; memcpy(&val, memPtr, sizeof(val)); return val; 180} 181 182MEM_STATIC void MEM_write16(void* memPtr, U16 value) 183{ 184 memcpy(memPtr, &value, sizeof(value)); 185} 186 187MEM_STATIC void MEM_write32(void* memPtr, U32 value) 188{ 189 memcpy(memPtr, &value, sizeof(value)); 190} 191 192MEM_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 200MEM_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 210MEM_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 221MEM_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 232MEM_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 244MEM_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) 299extern "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 */ 320size_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****************************************/ 329size_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 383size_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 449static const size_t ZSTDv05_blockHeaderSize = 3; 450static 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 494typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t; 495 496 497/*-******************************************* 498* Shared functions to include for inlining 499*********************************************/ 500static 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) */ 506MEM_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*********************************************/ 520typedef 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) 586extern "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******************************************/ 599size_t FSEv05_decompress(void* dst, size_t maxDstSize, 600 const void* cSrc, size_t cSrcSize); 601/*! 602FSEv05_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 */ 618unsigned FSEv05_isError(size_t code); /* tells if a return value is an error code */ 619const 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/*! 630FSEv05_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 */ 635size_t FSEv05_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize); 636 637/*! 638Constructor and Destructor of type FSEv05_DTable 639 Note that its size depends on 'tableLog' */ 640typedef unsigned FSEv05_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */ 641FSEv05_DTable* FSEv05_createDTable(unsigned tableLog); 642void FSEv05_freeDTable(FSEv05_DTable* dt); 643 644/*! 645FSEv05_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() */ 649size_t FSEv05_buildDTable (FSEv05_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog); 650 651/*! 652FSEv05_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() */ 657size_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) 704extern "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**********************************************/ 719typedef struct 720{ 721 size_t bitContainer; 722 unsigned bitsConsumed; 723 const char* ptr; 724 const char* start; 725} BITv05_DStream_t; 726 727typedef 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 733MEM_STATIC size_t BITv05_initDStream(BITv05_DStream_t* bitD, const void* srcBuffer, size_t srcSize); 734MEM_STATIC size_t BITv05_readBits(BITv05_DStream_t* bitD, unsigned nbBits); 735MEM_STATIC BITv05_DStream_status BITv05_reloadDStream(BITv05_DStream_t* bitD); 736MEM_STATIC unsigned BITv05_endOfDStream(const BITv05_DStream_t* bitD); 737 738 739/*-**************************************** 740* unsafe API 741******************************************/ 742MEM_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****************************************************************/ 750MEM_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*/ 784MEM_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 820MEM_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 */ 828MEM_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 834MEM_STATIC void BITv05_skipBits(BITv05_DStream_t* bitD, U32 nbBits) 835{ 836 bitD->bitsConsumed += nbBits; 837} 838 839MEM_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 */ 848MEM_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 855MEM_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*/ 887MEM_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) 935extern "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*******************************************/ 950size_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 953size_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*******************************************/ 961typedef struct 962{ 963 size_t state; 964 const void* table; /* precise table may vary, depending on U16 */ 965} FSEv05_DState_t; 966 967 968static void FSEv05_initDState(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD, const FSEv05_DTable* dt); 969 970static unsigned char FSEv05_decodeSymbol(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD); 971 972static unsigned FSEv05_endOfDState(const FSEv05_DState_t* DStatePtr); 973 974 975 976/* ***************************************** 977* FSEv05 unsafe API 978*******************************************/ 979static 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 988typedef struct { 989 U16 tableLog; 990 U16 fastMode; 991} FSEv05_DTableHeader; /* sizeof U32 */ 992 993typedef struct 994{ 995 unsigned short newState; 996 unsigned char symbol; 997 unsigned char nbBits; 998} FSEv05_decode_t; /* size == U32 */ 999 1000MEM_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 1009MEM_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 1015MEM_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 1026MEM_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 1037MEM_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****************************************************************/ 1165typedef 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 */ 1192static U32 FSEv05_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; } 1193 1194 1195 1196FSEv05_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 1202void FSEv05_freeDTable (FSEv05_DTable* dt) 1203{ 1204 free(dt); 1205} 1206 1207size_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 DTableH.tableLog = (U16)tableLog; 1228 for (s=0; s<=maxSymbolValue; s++) { 1229 if (normalizedCounter[s]==-1) { 1230 tableDecode[highThreshold--].symbol = (FSEv05_FUNCTION_TYPE)s; 1231 symbolNext[s] = 1; 1232 } else { 1233 if (normalizedCounter[s] >= largeLimit) noLarge=0; 1234 symbolNext[s] = normalizedCounter[s]; 1235 } } 1236 1237 /* Spread symbols */ 1238 for (s=0; s<=maxSymbolValue; s++) { 1239 int i; 1240 for (i=0; i<normalizedCounter[s]; i++) { 1241 tableDecode[position].symbol = (FSEv05_FUNCTION_TYPE)s; 1242 position = (position + step) & tableMask; 1243 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */ 1244 } } 1245 1246 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ 1247 1248 /* Build Decoding table */ 1249 { 1250 U32 i; 1251 for (i=0; i<tableSize; i++) { 1252 FSEv05_FUNCTION_TYPE symbol = (FSEv05_FUNCTION_TYPE)(tableDecode[i].symbol); 1253 U16 nextState = symbolNext[symbol]++; 1254 tableDecode[i].nbBits = (BYTE) (tableLog - BITv05_highbit32 ((U32)nextState) ); 1255 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize); 1256 } } 1257 1258 DTableH.fastMode = (U16)noLarge; 1259 memcpy(dt, &DTableH, sizeof(DTableH)); 1260 return 0; 1261} 1262 1263 1264#ifndef FSEv05_COMMONDEFS_ONLY 1265/*-**************************************** 1266* FSEv05 helper functions 1267******************************************/ 1268unsigned FSEv05_isError(size_t code) { return ERR_isError(code); } 1269 1270const char* FSEv05_getErrorName(size_t code) { return ERR_getErrorName(code); } 1271 1272 1273/*-************************************************************** 1274* FSEv05 NCount encoding-decoding 1275****************************************************************/ 1276static short FSEv05_abs(short a) { return a<0 ? -a : a; } 1277 1278 1279size_t FSEv05_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr, 1280 const void* headerBuffer, size_t hbSize) 1281{ 1282 const BYTE* const istart = (const BYTE*) headerBuffer; 1283 const BYTE* const iend = istart + hbSize; 1284 const BYTE* ip = istart; 1285 int nbBits; 1286 int remaining; 1287 int threshold; 1288 U32 bitStream; 1289 int bitCount; 1290 unsigned charnum = 0; 1291 int previous0 = 0; 1292 1293 if (hbSize < 4) return ERROR(srcSize_wrong); 1294 bitStream = MEM_readLE32(ip); 1295 nbBits = (bitStream & 0xF) + FSEv05_MIN_TABLELOG; /* extract tableLog */ 1296 if (nbBits > FSEv05_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge); 1297 bitStream >>= 4; 1298 bitCount = 4; 1299 *tableLogPtr = nbBits; 1300 remaining = (1<<nbBits)+1; 1301 threshold = 1<<nbBits; 1302 nbBits++; 1303 1304 while ((remaining>1) && (charnum<=*maxSVPtr)) { 1305 if (previous0) { 1306 unsigned n0 = charnum; 1307 while ((bitStream & 0xFFFF) == 0xFFFF) { 1308 n0+=24; 1309 if (ip < iend-5) { 1310 ip+=2; 1311 bitStream = MEM_readLE32(ip) >> bitCount; 1312 } else { 1313 bitStream >>= 16; 1314 bitCount+=16; 1315 } } 1316 while ((bitStream & 3) == 3) { 1317 n0+=3; 1318 bitStream>>=2; 1319 bitCount+=2; 1320 } 1321 n0 += bitStream & 3; 1322 bitCount += 2; 1323 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall); 1324 while (charnum < n0) normalizedCounter[charnum++] = 0; 1325 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { 1326 ip += bitCount>>3; 1327 bitCount &= 7; 1328 bitStream = MEM_readLE32(ip) >> bitCount; 1329 } 1330 else 1331 bitStream >>= 2; 1332 } 1333 { 1334 const short max = (short)((2*threshold-1)-remaining); 1335 short count; 1336 1337 if ((bitStream & (threshold-1)) < (U32)max) { 1338 count = (short)(bitStream & (threshold-1)); 1339 bitCount += nbBits-1; 1340 } else { 1341 count = (short)(bitStream & (2*threshold-1)); 1342 if (count >= threshold) count -= max; 1343 bitCount += nbBits; 1344 } 1345 1346 count--; /* extra accuracy */ 1347 remaining -= FSEv05_abs(count); 1348 normalizedCounter[charnum++] = count; 1349 previous0 = !count; 1350 while (remaining < threshold) { 1351 nbBits--; 1352 threshold >>= 1; 1353 } 1354 1355 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { 1356 ip += bitCount>>3; 1357 bitCount &= 7; 1358 } else { 1359 bitCount -= (int)(8 * (iend - 4 - ip)); 1360 ip = iend - 4; 1361 } 1362 bitStream = MEM_readLE32(ip) >> (bitCount & 31); 1363 } } 1364 if (remaining != 1) return ERROR(GENERIC); 1365 *maxSVPtr = charnum-1; 1366 1367 ip += (bitCount+7)>>3; 1368 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong); 1369 return ip-istart; 1370} 1371 1372 1373 1374/*-******************************************************* 1375* Decompression (Byte symbols) 1376*********************************************************/ 1377size_t FSEv05_buildDTable_rle (FSEv05_DTable* dt, BYTE symbolValue) 1378{ 1379 void* ptr = dt; 1380 FSEv05_DTableHeader* const DTableH = (FSEv05_DTableHeader*)ptr; 1381 void* dPtr = dt + 1; 1382 FSEv05_decode_t* const cell = (FSEv05_decode_t*)dPtr; 1383 1384 DTableH->tableLog = 0; 1385 DTableH->fastMode = 0; 1386 1387 cell->newState = 0; 1388 cell->symbol = symbolValue; 1389 cell->nbBits = 0; 1390 1391 return 0; 1392} 1393 1394 1395size_t FSEv05_buildDTable_raw (FSEv05_DTable* dt, unsigned nbBits) 1396{ 1397 void* ptr = dt; 1398 FSEv05_DTableHeader* const DTableH = (FSEv05_DTableHeader*)ptr; 1399 void* dPtr = dt + 1; 1400 FSEv05_decode_t* const dinfo = (FSEv05_decode_t*)dPtr; 1401 const unsigned tableSize = 1 << nbBits; 1402 const unsigned tableMask = tableSize - 1; 1403 const unsigned maxSymbolValue = tableMask; 1404 unsigned s; 1405 1406 /* Sanity checks */ 1407 if (nbBits < 1) return ERROR(GENERIC); /* min size */ 1408 1409 /* Build Decoding Table */ 1410 DTableH->tableLog = (U16)nbBits; 1411 DTableH->fastMode = 1; 1412 for (s=0; s<=maxSymbolValue; s++) { 1413 dinfo[s].newState = 0; 1414 dinfo[s].symbol = (BYTE)s; 1415 dinfo[s].nbBits = (BYTE)nbBits; 1416 } 1417 1418 return 0; 1419} 1420 1421FORCE_INLINE size_t FSEv05_decompress_usingDTable_generic( 1422 void* dst, size_t maxDstSize, 1423 const void* cSrc, size_t cSrcSize, 1424 const FSEv05_DTable* dt, const unsigned fast) 1425{ 1426 BYTE* const ostart = (BYTE*) dst; 1427 BYTE* op = ostart; 1428 BYTE* const omax = op + maxDstSize; 1429 BYTE* const olimit = omax-3; 1430 1431 BITv05_DStream_t bitD; 1432 FSEv05_DState_t state1; 1433 FSEv05_DState_t state2; 1434 size_t errorCode; 1435 1436 /* Init */ 1437 errorCode = BITv05_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */ 1438 if (FSEv05_isError(errorCode)) return errorCode; 1439 1440 FSEv05_initDState(&state1, &bitD, dt); 1441 FSEv05_initDState(&state2, &bitD, dt); 1442 1443#define FSEv05_GETSYMBOL(statePtr) fast ? FSEv05_decodeSymbolFast(statePtr, &bitD) : FSEv05_decodeSymbol(statePtr, &bitD) 1444 1445 /* 4 symbols per loop */ 1446 for ( ; (BITv05_reloadDStream(&bitD)==BITv05_DStream_unfinished) && (op<olimit) ; op+=4) { 1447 op[0] = FSEv05_GETSYMBOL(&state1); 1448 1449 if (FSEv05_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1450 BITv05_reloadDStream(&bitD); 1451 1452 op[1] = FSEv05_GETSYMBOL(&state2); 1453 1454 if (FSEv05_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1455 { if (BITv05_reloadDStream(&bitD) > BITv05_DStream_unfinished) { op+=2; break; } } 1456 1457 op[2] = FSEv05_GETSYMBOL(&state1); 1458 1459 if (FSEv05_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1460 BITv05_reloadDStream(&bitD); 1461 1462 op[3] = FSEv05_GETSYMBOL(&state2); 1463 } 1464 1465 /* tail */ 1466 /* note : BITv05_reloadDStream(&bitD) >= FSEv05_DStream_partiallyFilled; Ends at exactly BITv05_DStream_completed */ 1467 while (1) { 1468 if ( (BITv05_reloadDStream(&bitD)>BITv05_DStream_completed) || (op==omax) || (BITv05_endOfDStream(&bitD) && (fast || FSEv05_endOfDState(&state1))) ) 1469 break; 1470 1471 *op++ = FSEv05_GETSYMBOL(&state1); 1472 1473 if ( (BITv05_reloadDStream(&bitD)>BITv05_DStream_completed) || (op==omax) || (BITv05_endOfDStream(&bitD) && (fast || FSEv05_endOfDState(&state2))) ) 1474 break; 1475 1476 *op++ = FSEv05_GETSYMBOL(&state2); 1477 } 1478 1479 /* end ? */ 1480 if (BITv05_endOfDStream(&bitD) && FSEv05_endOfDState(&state1) && FSEv05_endOfDState(&state2)) 1481 return op-ostart; 1482 1483 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */ 1484 1485 return ERROR(corruption_detected); 1486} 1487 1488 1489size_t FSEv05_decompress_usingDTable(void* dst, size_t originalSize, 1490 const void* cSrc, size_t cSrcSize, 1491 const FSEv05_DTable* dt) 1492{ 1493 const void* ptr = dt; 1494 const FSEv05_DTableHeader* DTableH = (const FSEv05_DTableHeader*)ptr; 1495 const U32 fastMode = DTableH->fastMode; 1496 1497 /* select fast mode (static) */ 1498 if (fastMode) return FSEv05_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1); 1499 return FSEv05_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0); 1500} 1501 1502 1503size_t FSEv05_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize) 1504{ 1505 const BYTE* const istart = (const BYTE*)cSrc; 1506 const BYTE* ip = istart; 1507 short counting[FSEv05_MAX_SYMBOL_VALUE+1]; 1508 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */ 1509 unsigned tableLog; 1510 unsigned maxSymbolValue = FSEv05_MAX_SYMBOL_VALUE; 1511 size_t errorCode; 1512 1513 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */ 1514 1515 /* normal FSEv05 decoding mode */ 1516 errorCode = FSEv05_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize); 1517 if (FSEv05_isError(errorCode)) return errorCode; 1518 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */ 1519 ip += errorCode; 1520 cSrcSize -= errorCode; 1521 1522 errorCode = FSEv05_buildDTable (dt, counting, maxSymbolValue, tableLog); 1523 if (FSEv05_isError(errorCode)) return errorCode; 1524 1525 /* always return, even if it is an error code */ 1526 return FSEv05_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); 1527} 1528 1529 1530 1531#endif /* FSEv05_COMMONDEFS_ONLY */ 1532/* ****************************************************************** 1533 Huff0 : Huffman coder, part of New Generation Entropy library 1534 header file 1535 Copyright (C) 2013-2016, Yann Collet. 1536 1537 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1538 1539 Redistribution and use in source and binary forms, with or without 1540 modification, are permitted provided that the following conditions are 1541 met: 1542 1543 * Redistributions of source code must retain the above copyright 1544 notice, this list of conditions and the following disclaimer. 1545 * Redistributions in binary form must reproduce the above 1546 copyright notice, this list of conditions and the following disclaimer 1547 in the documentation and/or other materials provided with the 1548 distribution. 1549 1550 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1551 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1552 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1553 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1554 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1555 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1556 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1557 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1558 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1559 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1560 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1561 1562 You can contact the author at : 1563 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 1564****************************************************************** */ 1565#ifndef HUFF0_H 1566#define HUFF0_H 1567 1568#if defined (__cplusplus) 1569extern "C" { 1570#endif 1571 1572 1573 1574/* **************************************** 1575* Huff0 simple functions 1576******************************************/ 1577size_t HUFv05_decompress(void* dst, size_t dstSize, 1578 const void* cSrc, size_t cSrcSize); 1579/*! 1580HUFv05_decompress(): 1581 Decompress Huff0 data from buffer 'cSrc', of size 'cSrcSize', 1582 into already allocated destination buffer 'dst', of size 'dstSize'. 1583 @dstSize : must be the **exact** size of original (uncompressed) data. 1584 Note : in contrast with FSEv05, HUFv05_decompress can regenerate 1585 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, 1586 because it knows size to regenerate. 1587 @return : size of regenerated data (== dstSize) 1588 or an error code, which can be tested using HUFv05_isError() 1589*/ 1590 1591 1592/* **************************************** 1593* Tool functions 1594******************************************/ 1595/* Error Management */ 1596unsigned HUFv05_isError(size_t code); /* tells if a return value is an error code */ 1597const char* HUFv05_getErrorName(size_t code); /* provides error code string (useful for debugging) */ 1598 1599 1600#if defined (__cplusplus) 1601} 1602#endif 1603 1604#endif /* HUF0_H */ 1605/* ****************************************************************** 1606 Huff0 : Huffman codec, part of New Generation Entropy library 1607 header file, for static linking only 1608 Copyright (C) 2013-2016, Yann Collet 1609 1610 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1611 1612 Redistribution and use in source and binary forms, with or without 1613 modification, are permitted provided that the following conditions are 1614 met: 1615 1616 * Redistributions of source code must retain the above copyright 1617 notice, this list of conditions and the following disclaimer. 1618 * Redistributions in binary form must reproduce the above 1619 copyright notice, this list of conditions and the following disclaimer 1620 in the documentation and/or other materials provided with the 1621 distribution. 1622 1623 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1624 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1625 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1626 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1627 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1628 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1629 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1630 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1631 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1632 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1633 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1634 1635 You can contact the author at : 1636 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 1637****************************************************************** */ 1638#ifndef HUF0_STATIC_H 1639#define HUF0_STATIC_H 1640 1641#if defined (__cplusplus) 1642extern "C" { 1643#endif 1644 1645 1646 1647/* **************************************** 1648* Static allocation 1649******************************************/ 1650/* static allocation of Huff0's DTable */ 1651#define HUFv05_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) 1652#define HUFv05_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \ 1653 unsigned short DTable[HUFv05_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 1654#define HUFv05_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \ 1655 unsigned int DTable[HUFv05_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 1656#define HUFv05_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \ 1657 unsigned int DTable[HUFv05_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog } 1658 1659 1660/* **************************************** 1661* Advanced decompression functions 1662******************************************/ 1663size_t HUFv05_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ 1664size_t HUFv05_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */ 1665 1666 1667/* **************************************** 1668* Huff0 detailed API 1669******************************************/ 1670/*! 1671HUFv05_decompress() does the following: 16721. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics 16732. build Huffman table from save, using HUFv05_readDTableXn() 16743. decode 1 or 4 segments in parallel using HUFv05_decompressSXn_usingDTable 1675*/ 1676size_t HUFv05_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize); 1677size_t HUFv05_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize); 1678 1679size_t HUFv05_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable); 1680size_t HUFv05_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable); 1681 1682 1683/* single stream variants */ 1684 1685size_t HUFv05_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ 1686size_t HUFv05_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */ 1687 1688size_t HUFv05_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable); 1689size_t HUFv05_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable); 1690 1691 1692 1693#if defined (__cplusplus) 1694} 1695#endif 1696 1697#endif /* HUF0_STATIC_H */ 1698/* ****************************************************************** 1699 Huff0 : Huffman coder, part of New Generation Entropy library 1700 Copyright (C) 2013-2015, Yann Collet. 1701 1702 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1703 1704 Redistribution and use in source and binary forms, with or without 1705 modification, are permitted provided that the following conditions are 1706 met: 1707 1708 * Redistributions of source code must retain the above copyright 1709 notice, this list of conditions and the following disclaimer. 1710 * Redistributions in binary form must reproduce the above 1711 copyright notice, this list of conditions and the following disclaimer 1712 in the documentation and/or other materials provided with the 1713 distribution. 1714 1715 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1716 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1717 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1718 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1719 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1720 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1721 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1722 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1723 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1724 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1725 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1726 1727 You can contact the author at : 1728 - FSEv05+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy 1729 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1730****************************************************************** */ 1731 1732/* ************************************************************** 1733* Compiler specifics 1734****************************************************************/ 1735#if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 1736/* inline is defined */ 1737#elif defined(_MSC_VER) 1738# define inline __inline 1739#else 1740# define inline /* disable inline */ 1741#endif 1742 1743 1744#ifdef _MSC_VER /* Visual Studio */ 1745# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 1746#endif 1747 1748 1749/* ************************************************************** 1750* Includes 1751****************************************************************/ 1752#include <stdlib.h> /* malloc, free, qsort */ 1753#include <string.h> /* memcpy, memset */ 1754#include <stdio.h> /* printf (debug) */ 1755 1756 1757/* ************************************************************** 1758* Constants 1759****************************************************************/ 1760#define HUFv05_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUFv05_MAX_TABLELOG. Beyond that value, code does not work */ 1761#define HUFv05_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUFv05_ABSOLUTEMAX_TABLELOG */ 1762#define HUFv05_DEFAULT_TABLELOG HUFv05_MAX_TABLELOG /* tableLog by default, when not specified */ 1763#define HUFv05_MAX_SYMBOL_VALUE 255 1764#if (HUFv05_MAX_TABLELOG > HUFv05_ABSOLUTEMAX_TABLELOG) 1765# error "HUFv05_MAX_TABLELOG is too large !" 1766#endif 1767 1768 1769/* ************************************************************** 1770* Error Management 1771****************************************************************/ 1772unsigned HUFv05_isError(size_t code) { return ERR_isError(code); } 1773const char* HUFv05_getErrorName(size_t code) { return ERR_getErrorName(code); } 1774#define HUFv05_STATIC_ASSERT(c) { enum { HUFv05_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 1775 1776 1777/* ******************************************************* 1778* Huff0 : Huffman block decompression 1779*********************************************************/ 1780typedef struct { BYTE byte; BYTE nbBits; } HUFv05_DEltX2; /* single-symbol decoding */ 1781 1782typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv05_DEltX4; /* double-symbols decoding */ 1783 1784typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t; 1785 1786/*! HUFv05_readStats 1787 Read compact Huffman tree, saved by HUFv05_writeCTable 1788 @huffWeight : destination buffer 1789 @return : size read from `src` 1790*/ 1791static size_t HUFv05_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats, 1792 U32* nbSymbolsPtr, U32* tableLogPtr, 1793 const void* src, size_t srcSize) 1794{ 1795 U32 weightTotal; 1796 U32 tableLog; 1797 const BYTE* ip = (const BYTE*) src; 1798 size_t iSize; 1799 size_t oSize; 1800 U32 n; 1801 1802 if (!srcSize) return ERROR(srcSize_wrong); 1803 iSize = ip[0]; 1804 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */ 1805 1806 if (iSize >= 128) { /* special header */ 1807 if (iSize >= (242)) { /* RLE */ 1808 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 }; 1809 oSize = l[iSize-242]; 1810 memset(huffWeight, 1, hwSize); 1811 iSize = 0; 1812 } 1813 else { /* Incompressible */ 1814 oSize = iSize - 127; 1815 iSize = ((oSize+1)/2); 1816 if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 1817 if (oSize >= hwSize) return ERROR(corruption_detected); 1818 ip += 1; 1819 for (n=0; n<oSize; n+=2) { 1820 huffWeight[n] = ip[n/2] >> 4; 1821 huffWeight[n+1] = ip[n/2] & 15; 1822 } } } 1823 else { /* header compressed with FSEv05 (normal case) */ 1824 if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 1825 oSize = FSEv05_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */ 1826 if (FSEv05_isError(oSize)) return oSize; 1827 } 1828 1829 /* collect weight stats */ 1830 memset(rankStats, 0, (HUFv05_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32)); 1831 weightTotal = 0; 1832 for (n=0; n<oSize; n++) { 1833 if (huffWeight[n] >= HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 1834 rankStats[huffWeight[n]]++; 1835 weightTotal += (1 << huffWeight[n]) >> 1; 1836 } 1837 if (weightTotal == 0) return ERROR(corruption_detected); 1838 1839 /* get last non-null symbol weight (implied, total must be 2^n) */ 1840 tableLog = BITv05_highbit32(weightTotal) + 1; 1841 if (tableLog > HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 1842 { /* determine last weight */ 1843 U32 total = 1 << tableLog; 1844 U32 rest = total - weightTotal; 1845 U32 verif = 1 << BITv05_highbit32(rest); 1846 U32 lastWeight = BITv05_highbit32(rest) + 1; 1847 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */ 1848 huffWeight[oSize] = (BYTE)lastWeight; 1849 rankStats[lastWeight]++; 1850 } 1851 1852 /* check tree construction validity */ 1853 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */ 1854 1855 /* results */ 1856 *nbSymbolsPtr = (U32)(oSize+1); 1857 *tableLogPtr = tableLog; 1858 return iSize+1; 1859} 1860 1861 1862/*-***************************/ 1863/* single-symbol decoding */ 1864/*-***************************/ 1865 1866size_t HUFv05_readDTableX2 (U16* DTable, const void* src, size_t srcSize) 1867{ 1868 BYTE huffWeight[HUFv05_MAX_SYMBOL_VALUE + 1]; 1869 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */ 1870 U32 tableLog = 0; 1871 size_t iSize; 1872 U32 nbSymbols = 0; 1873 U32 n; 1874 U32 nextRankStart; 1875 void* const dtPtr = DTable + 1; 1876 HUFv05_DEltX2* const dt = (HUFv05_DEltX2*)dtPtr; 1877 1878 HUFv05_STATIC_ASSERT(sizeof(HUFv05_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */ 1879 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */ 1880 1881 iSize = HUFv05_readStats(huffWeight, HUFv05_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize); 1882 if (HUFv05_isError(iSize)) return iSize; 1883 1884 /* check result */ 1885 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */ 1886 DTable[0] = (U16)tableLog; /* maybe should separate sizeof allocated DTable, from used size of DTable, in case of re-use */ 1887 1888 /* Prepare ranks */ 1889 nextRankStart = 0; 1890 for (n=1; n<=tableLog; n++) { 1891 U32 current = nextRankStart; 1892 nextRankStart += (rankVal[n] << (n-1)); 1893 rankVal[n] = current; 1894 } 1895 1896 /* fill DTable */ 1897 for (n=0; n<nbSymbols; n++) { 1898 const U32 w = huffWeight[n]; 1899 const U32 length = (1 << w) >> 1; 1900 U32 i; 1901 HUFv05_DEltX2 D; 1902 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w); 1903 for (i = rankVal[w]; i < rankVal[w] + length; i++) 1904 dt[i] = D; 1905 rankVal[w] += length; 1906 } 1907 1908 return iSize; 1909} 1910 1911static BYTE HUFv05_decodeSymbolX2(BITv05_DStream_t* Dstream, const HUFv05_DEltX2* dt, const U32 dtLog) 1912{ 1913 const size_t val = BITv05_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */ 1914 const BYTE c = dt[val].byte; 1915 BITv05_skipBits(Dstream, dt[val].nbBits); 1916 return c; 1917} 1918 1919#define HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \ 1920 *ptr++ = HUFv05_decodeSymbolX2(DStreamPtr, dt, dtLog) 1921 1922#define HUFv05_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \ 1923 if (MEM_64bits() || (HUFv05_MAX_TABLELOG<=12)) \ 1924 HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 1925 1926#define HUFv05_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \ 1927 if (MEM_64bits()) \ 1928 HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 1929 1930static inline size_t HUFv05_decodeStreamX2(BYTE* p, BITv05_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv05_DEltX2* const dt, const U32 dtLog) 1931{ 1932 BYTE* const pStart = p; 1933 1934 /* up to 4 symbols at a time */ 1935 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p <= pEnd-4)) { 1936 HUFv05_DECODE_SYMBOLX2_2(p, bitDPtr); 1937 HUFv05_DECODE_SYMBOLX2_1(p, bitDPtr); 1938 HUFv05_DECODE_SYMBOLX2_2(p, bitDPtr); 1939 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr); 1940 } 1941 1942 /* closer to the end */ 1943 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p < pEnd)) 1944 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr); 1945 1946 /* no more data to retrieve from bitstream, hence no need to reload */ 1947 while (p < pEnd) 1948 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr); 1949 1950 return pEnd-pStart; 1951} 1952 1953size_t HUFv05_decompress1X2_usingDTable( 1954 void* dst, size_t dstSize, 1955 const void* cSrc, size_t cSrcSize, 1956 const U16* DTable) 1957{ 1958 BYTE* op = (BYTE*)dst; 1959 BYTE* const oend = op + dstSize; 1960 const U32 dtLog = DTable[0]; 1961 const void* dtPtr = DTable; 1962 const HUFv05_DEltX2* const dt = ((const HUFv05_DEltX2*)dtPtr)+1; 1963 BITv05_DStream_t bitD; 1964 1965 if (dstSize <= cSrcSize) return ERROR(dstSize_tooSmall); 1966 { size_t const errorCode = BITv05_initDStream(&bitD, cSrc, cSrcSize); 1967 if (HUFv05_isError(errorCode)) return errorCode; } 1968 1969 HUFv05_decodeStreamX2(op, &bitD, oend, dt, dtLog); 1970 1971 /* check */ 1972 if (!BITv05_endOfDStream(&bitD)) return ERROR(corruption_detected); 1973 1974 return dstSize; 1975} 1976 1977size_t HUFv05_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 1978{ 1979 HUFv05_CREATE_STATIC_DTABLEX2(DTable, HUFv05_MAX_TABLELOG); 1980 const BYTE* ip = (const BYTE*) cSrc; 1981 size_t errorCode; 1982 1983 errorCode = HUFv05_readDTableX2 (DTable, cSrc, cSrcSize); 1984 if (HUFv05_isError(errorCode)) return errorCode; 1985 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); 1986 ip += errorCode; 1987 cSrcSize -= errorCode; 1988 1989 return HUFv05_decompress1X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 1990} 1991 1992 1993size_t HUFv05_decompress4X2_usingDTable( 1994 void* dst, size_t dstSize, 1995 const void* cSrc, size_t cSrcSize, 1996 const U16* DTable) 1997{ 1998 const BYTE* const istart = (const BYTE*) cSrc; 1999 BYTE* const ostart = (BYTE*) dst; 2000 BYTE* const oend = ostart + dstSize; 2001 const void* const dtPtr = DTable; 2002 const HUFv05_DEltX2* const dt = ((const HUFv05_DEltX2*)dtPtr) +1; 2003 const U32 dtLog = DTable[0]; 2004 size_t errorCode; 2005 2006 /* Init */ 2007 BITv05_DStream_t bitD1; 2008 BITv05_DStream_t bitD2; 2009 BITv05_DStream_t bitD3; 2010 BITv05_DStream_t bitD4; 2011 const size_t length1 = MEM_readLE16(istart); 2012 const size_t length2 = MEM_readLE16(istart+2); 2013 const size_t length3 = MEM_readLE16(istart+4); 2014 size_t length4; 2015 const BYTE* const istart1 = istart + 6; /* jumpTable */ 2016 const BYTE* const istart2 = istart1 + length1; 2017 const BYTE* const istart3 = istart2 + length2; 2018 const BYTE* const istart4 = istart3 + length3; 2019 const size_t segmentSize = (dstSize+3) / 4; 2020 BYTE* const opStart2 = ostart + segmentSize; 2021 BYTE* const opStart3 = opStart2 + segmentSize; 2022 BYTE* const opStart4 = opStart3 + segmentSize; 2023 BYTE* op1 = ostart; 2024 BYTE* op2 = opStart2; 2025 BYTE* op3 = opStart3; 2026 BYTE* op4 = opStart4; 2027 U32 endSignal; 2028 2029 /* Check */ 2030 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 2031 2032 length4 = cSrcSize - (length1 + length2 + length3 + 6); 2033 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 2034 errorCode = BITv05_initDStream(&bitD1, istart1, length1); 2035 if (HUFv05_isError(errorCode)) return errorCode; 2036 errorCode = BITv05_initDStream(&bitD2, istart2, length2); 2037 if (HUFv05_isError(errorCode)) return errorCode; 2038 errorCode = BITv05_initDStream(&bitD3, istart3, length3); 2039 if (HUFv05_isError(errorCode)) return errorCode; 2040 errorCode = BITv05_initDStream(&bitD4, istart4, length4); 2041 if (HUFv05_isError(errorCode)) return errorCode; 2042 2043 /* 16-32 symbols per loop (4-8 symbols per stream) */ 2044 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4); 2045 for ( ; (endSignal==BITv05_DStream_unfinished) && (op4<(oend-7)) ; ) { 2046 HUFv05_DECODE_SYMBOLX2_2(op1, &bitD1); 2047 HUFv05_DECODE_SYMBOLX2_2(op2, &bitD2); 2048 HUFv05_DECODE_SYMBOLX2_2(op3, &bitD3); 2049 HUFv05_DECODE_SYMBOLX2_2(op4, &bitD4); 2050 HUFv05_DECODE_SYMBOLX2_1(op1, &bitD1); 2051 HUFv05_DECODE_SYMBOLX2_1(op2, &bitD2); 2052 HUFv05_DECODE_SYMBOLX2_1(op3, &bitD3); 2053 HUFv05_DECODE_SYMBOLX2_1(op4, &bitD4); 2054 HUFv05_DECODE_SYMBOLX2_2(op1, &bitD1); 2055 HUFv05_DECODE_SYMBOLX2_2(op2, &bitD2); 2056 HUFv05_DECODE_SYMBOLX2_2(op3, &bitD3); 2057 HUFv05_DECODE_SYMBOLX2_2(op4, &bitD4); 2058 HUFv05_DECODE_SYMBOLX2_0(op1, &bitD1); 2059 HUFv05_DECODE_SYMBOLX2_0(op2, &bitD2); 2060 HUFv05_DECODE_SYMBOLX2_0(op3, &bitD3); 2061 HUFv05_DECODE_SYMBOLX2_0(op4, &bitD4); 2062 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4); 2063 } 2064 2065 /* check corruption */ 2066 if (op1 > opStart2) return ERROR(corruption_detected); 2067 if (op2 > opStart3) return ERROR(corruption_detected); 2068 if (op3 > opStart4) return ERROR(corruption_detected); 2069 /* note : op4 supposed already verified within main loop */ 2070 2071 /* finish bitStreams one by one */ 2072 HUFv05_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog); 2073 HUFv05_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog); 2074 HUFv05_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog); 2075 HUFv05_decodeStreamX2(op4, &bitD4, oend, dt, dtLog); 2076 2077 /* check */ 2078 endSignal = BITv05_endOfDStream(&bitD1) & BITv05_endOfDStream(&bitD2) & BITv05_endOfDStream(&bitD3) & BITv05_endOfDStream(&bitD4); 2079 if (!endSignal) return ERROR(corruption_detected); 2080 2081 /* decoded size */ 2082 return dstSize; 2083} 2084 2085 2086size_t HUFv05_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2087{ 2088 HUFv05_CREATE_STATIC_DTABLEX2(DTable, HUFv05_MAX_TABLELOG); 2089 const BYTE* ip = (const BYTE*) cSrc; 2090 size_t errorCode; 2091 2092 errorCode = HUFv05_readDTableX2 (DTable, cSrc, cSrcSize); 2093 if (HUFv05_isError(errorCode)) return errorCode; 2094 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); 2095 ip += errorCode; 2096 cSrcSize -= errorCode; 2097 2098 return HUFv05_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2099} 2100 2101 2102/* *************************/ 2103/* double-symbols decoding */ 2104/* *************************/ 2105 2106static void HUFv05_fillDTableX4Level2(HUFv05_DEltX4* DTable, U32 sizeLog, const U32 consumed, 2107 const U32* rankValOrigin, const int minWeight, 2108 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize, 2109 U32 nbBitsBaseline, U16 baseSeq) 2110{ 2111 HUFv05_DEltX4 DElt; 2112 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1]; 2113 U32 s; 2114 2115 /* get pre-calculated rankVal */ 2116 memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 2117 2118 /* fill skipped values */ 2119 if (minWeight>1) { 2120 U32 i, skipSize = rankVal[minWeight]; 2121 MEM_writeLE16(&(DElt.sequence), baseSeq); 2122 DElt.nbBits = (BYTE)(consumed); 2123 DElt.length = 1; 2124 for (i = 0; i < skipSize; i++) 2125 DTable[i] = DElt; 2126 } 2127 2128 /* fill DTable */ 2129 for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */ 2130 const U32 symbol = sortedSymbols[s].symbol; 2131 const U32 weight = sortedSymbols[s].weight; 2132 const U32 nbBits = nbBitsBaseline - weight; 2133 const U32 length = 1 << (sizeLog-nbBits); 2134 const U32 start = rankVal[weight]; 2135 U32 i = start; 2136 const U32 end = start + length; 2137 2138 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8))); 2139 DElt.nbBits = (BYTE)(nbBits + consumed); 2140 DElt.length = 2; 2141 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */ 2142 2143 rankVal[weight] += length; 2144 } 2145} 2146 2147typedef U32 rankVal_t[HUFv05_ABSOLUTEMAX_TABLELOG][HUFv05_ABSOLUTEMAX_TABLELOG + 1]; 2148 2149static void HUFv05_fillDTableX4(HUFv05_DEltX4* DTable, const U32 targetLog, 2150 const sortedSymbol_t* sortedList, const U32 sortedListSize, 2151 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight, 2152 const U32 nbBitsBaseline) 2153{ 2154 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1]; 2155 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */ 2156 const U32 minBits = nbBitsBaseline - maxWeight; 2157 U32 s; 2158 2159 memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 2160 2161 /* fill DTable */ 2162 for (s=0; s<sortedListSize; s++) { 2163 const U16 symbol = sortedList[s].symbol; 2164 const U32 weight = sortedList[s].weight; 2165 const U32 nbBits = nbBitsBaseline - weight; 2166 const U32 start = rankVal[weight]; 2167 const U32 length = 1 << (targetLog-nbBits); 2168 2169 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */ 2170 U32 sortedRank; 2171 int minWeight = nbBits + scaleLog; 2172 if (minWeight < 1) minWeight = 1; 2173 sortedRank = rankStart[minWeight]; 2174 HUFv05_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits, 2175 rankValOrigin[nbBits], minWeight, 2176 sortedList+sortedRank, sortedListSize-sortedRank, 2177 nbBitsBaseline, symbol); 2178 } else { 2179 U32 i; 2180 const U32 end = start + length; 2181 HUFv05_DEltX4 DElt; 2182 2183 MEM_writeLE16(&(DElt.sequence), symbol); 2184 DElt.nbBits = (BYTE)(nbBits); 2185 DElt.length = 1; 2186 for (i = start; i < end; i++) 2187 DTable[i] = DElt; 2188 } 2189 rankVal[weight] += length; 2190 } 2191} 2192 2193size_t HUFv05_readDTableX4 (U32* DTable, const void* src, size_t srcSize) 2194{ 2195 BYTE weightList[HUFv05_MAX_SYMBOL_VALUE + 1]; 2196 sortedSymbol_t sortedSymbol[HUFv05_MAX_SYMBOL_VALUE + 1]; 2197 U32 rankStats[HUFv05_ABSOLUTEMAX_TABLELOG + 1] = { 0 }; 2198 U32 rankStart0[HUFv05_ABSOLUTEMAX_TABLELOG + 2] = { 0 }; 2199 U32* const rankStart = rankStart0+1; 2200 rankVal_t rankVal; 2201 U32 tableLog, maxW, sizeOfSort, nbSymbols; 2202 const U32 memLog = DTable[0]; 2203 size_t iSize; 2204 void* dtPtr = DTable; 2205 HUFv05_DEltX4* const dt = ((HUFv05_DEltX4*)dtPtr) + 1; 2206 2207 HUFv05_STATIC_ASSERT(sizeof(HUFv05_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */ 2208 if (memLog > HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge); 2209 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */ 2210 2211 iSize = HUFv05_readStats(weightList, HUFv05_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize); 2212 if (HUFv05_isError(iSize)) return iSize; 2213 2214 /* check result */ 2215 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */ 2216 2217 /* find maxWeight */ 2218 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */ 2219 2220 /* Get start index of each weight */ 2221 { 2222 U32 w, nextRankStart = 0; 2223 for (w=1; w<=maxW; w++) { 2224 U32 current = nextRankStart; 2225 nextRankStart += rankStats[w]; 2226 rankStart[w] = current; 2227 } 2228 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/ 2229 sizeOfSort = nextRankStart; 2230 } 2231 2232 /* sort symbols by weight */ 2233 { 2234 U32 s; 2235 for (s=0; s<nbSymbols; s++) { 2236 U32 w = weightList[s]; 2237 U32 r = rankStart[w]++; 2238 sortedSymbol[r].symbol = (BYTE)s; 2239 sortedSymbol[r].weight = (BYTE)w; 2240 } 2241 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */ 2242 } 2243 2244 /* Build rankVal */ 2245 { 2246 const U32 minBits = tableLog+1 - maxW; 2247 U32 nextRankVal = 0; 2248 U32 w, consumed; 2249 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */ 2250 U32* rankVal0 = rankVal[0]; 2251 for (w=1; w<=maxW; w++) { 2252 U32 current = nextRankVal; 2253 nextRankVal += rankStats[w] << (w+rescale); 2254 rankVal0[w] = current; 2255 } 2256 for (consumed = minBits; consumed <= memLog - minBits; consumed++) { 2257 U32* rankValPtr = rankVal[consumed]; 2258 for (w = 1; w <= maxW; w++) { 2259 rankValPtr[w] = rankVal0[w] >> consumed; 2260 } } } 2261 2262 HUFv05_fillDTableX4(dt, memLog, 2263 sortedSymbol, sizeOfSort, 2264 rankStart0, rankVal, maxW, 2265 tableLog+1); 2266 2267 return iSize; 2268} 2269 2270 2271static U32 HUFv05_decodeSymbolX4(void* op, BITv05_DStream_t* DStream, const HUFv05_DEltX4* dt, const U32 dtLog) 2272{ 2273 const size_t val = BITv05_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 2274 memcpy(op, dt+val, 2); 2275 BITv05_skipBits(DStream, dt[val].nbBits); 2276 return dt[val].length; 2277} 2278 2279static U32 HUFv05_decodeLastSymbolX4(void* op, BITv05_DStream_t* DStream, const HUFv05_DEltX4* dt, const U32 dtLog) 2280{ 2281 const size_t val = BITv05_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 2282 memcpy(op, dt+val, 1); 2283 if (dt[val].length==1) BITv05_skipBits(DStream, dt[val].nbBits); 2284 else { 2285 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) { 2286 BITv05_skipBits(DStream, dt[val].nbBits); 2287 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8)) 2288 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 */ 2289 } } 2290 return 1; 2291} 2292 2293 2294#define HUFv05_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \ 2295 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2296 2297#define HUFv05_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \ 2298 if (MEM_64bits() || (HUFv05_MAX_TABLELOG<=12)) \ 2299 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2300 2301#define HUFv05_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \ 2302 if (MEM_64bits()) \ 2303 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2304 2305static inline size_t HUFv05_decodeStreamX4(BYTE* p, BITv05_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv05_DEltX4* const dt, const U32 dtLog) 2306{ 2307 BYTE* const pStart = p; 2308 2309 /* up to 8 symbols at a time */ 2310 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p < pEnd-7)) { 2311 HUFv05_DECODE_SYMBOLX4_2(p, bitDPtr); 2312 HUFv05_DECODE_SYMBOLX4_1(p, bitDPtr); 2313 HUFv05_DECODE_SYMBOLX4_2(p, bitDPtr); 2314 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr); 2315 } 2316 2317 /* closer to the end */ 2318 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p <= pEnd-2)) 2319 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr); 2320 2321 while (p <= pEnd-2) 2322 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */ 2323 2324 if (p < pEnd) 2325 p += HUFv05_decodeLastSymbolX4(p, bitDPtr, dt, dtLog); 2326 2327 return p-pStart; 2328} 2329 2330 2331size_t HUFv05_decompress1X4_usingDTable( 2332 void* dst, size_t dstSize, 2333 const void* cSrc, size_t cSrcSize, 2334 const U32* DTable) 2335{ 2336 const BYTE* const istart = (const BYTE*) cSrc; 2337 BYTE* const ostart = (BYTE*) dst; 2338 BYTE* const oend = ostart + dstSize; 2339 2340 const U32 dtLog = DTable[0]; 2341 const void* const dtPtr = DTable; 2342 const HUFv05_DEltX4* const dt = ((const HUFv05_DEltX4*)dtPtr) +1; 2343 size_t errorCode; 2344 2345 /* Init */ 2346 BITv05_DStream_t bitD; 2347 errorCode = BITv05_initDStream(&bitD, istart, cSrcSize); 2348 if (HUFv05_isError(errorCode)) return errorCode; 2349 2350 /* finish bitStreams one by one */ 2351 HUFv05_decodeStreamX4(ostart, &bitD, oend, dt, dtLog); 2352 2353 /* check */ 2354 if (!BITv05_endOfDStream(&bitD)) return ERROR(corruption_detected); 2355 2356 /* decoded size */ 2357 return dstSize; 2358} 2359 2360size_t HUFv05_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2361{ 2362 HUFv05_CREATE_STATIC_DTABLEX4(DTable, HUFv05_MAX_TABLELOG); 2363 const BYTE* ip = (const BYTE*) cSrc; 2364 2365 size_t hSize = HUFv05_readDTableX4 (DTable, cSrc, cSrcSize); 2366 if (HUFv05_isError(hSize)) return hSize; 2367 if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 2368 ip += hSize; 2369 cSrcSize -= hSize; 2370 2371 return HUFv05_decompress1X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2372} 2373 2374size_t HUFv05_decompress4X4_usingDTable( 2375 void* dst, size_t dstSize, 2376 const void* cSrc, size_t cSrcSize, 2377 const U32* DTable) 2378{ 2379 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 2380 2381 { 2382 const BYTE* const istart = (const BYTE*) cSrc; 2383 BYTE* const ostart = (BYTE*) dst; 2384 BYTE* const oend = ostart + dstSize; 2385 const void* const dtPtr = DTable; 2386 const HUFv05_DEltX4* const dt = ((const HUFv05_DEltX4*)dtPtr) +1; 2387 const U32 dtLog = DTable[0]; 2388 size_t errorCode; 2389 2390 /* Init */ 2391 BITv05_DStream_t bitD1; 2392 BITv05_DStream_t bitD2; 2393 BITv05_DStream_t bitD3; 2394 BITv05_DStream_t bitD4; 2395 const size_t length1 = MEM_readLE16(istart); 2396 const size_t length2 = MEM_readLE16(istart+2); 2397 const size_t length3 = MEM_readLE16(istart+4); 2398 size_t length4; 2399 const BYTE* const istart1 = istart + 6; /* jumpTable */ 2400 const BYTE* const istart2 = istart1 + length1; 2401 const BYTE* const istart3 = istart2 + length2; 2402 const BYTE* const istart4 = istart3 + length3; 2403 const size_t segmentSize = (dstSize+3) / 4; 2404 BYTE* const opStart2 = ostart + segmentSize; 2405 BYTE* const opStart3 = opStart2 + segmentSize; 2406 BYTE* const opStart4 = opStart3 + segmentSize; 2407 BYTE* op1 = ostart; 2408 BYTE* op2 = opStart2; 2409 BYTE* op3 = opStart3; 2410 BYTE* op4 = opStart4; 2411 U32 endSignal; 2412 2413 length4 = cSrcSize - (length1 + length2 + length3 + 6); 2414 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 2415 errorCode = BITv05_initDStream(&bitD1, istart1, length1); 2416 if (HUFv05_isError(errorCode)) return errorCode; 2417 errorCode = BITv05_initDStream(&bitD2, istart2, length2); 2418 if (HUFv05_isError(errorCode)) return errorCode; 2419 errorCode = BITv05_initDStream(&bitD3, istart3, length3); 2420 if (HUFv05_isError(errorCode)) return errorCode; 2421 errorCode = BITv05_initDStream(&bitD4, istart4, length4); 2422 if (HUFv05_isError(errorCode)) return errorCode; 2423 2424 /* 16-32 symbols per loop (4-8 symbols per stream) */ 2425 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4); 2426 for ( ; (endSignal==BITv05_DStream_unfinished) && (op4<(oend-7)) ; ) { 2427 HUFv05_DECODE_SYMBOLX4_2(op1, &bitD1); 2428 HUFv05_DECODE_SYMBOLX4_2(op2, &bitD2); 2429 HUFv05_DECODE_SYMBOLX4_2(op3, &bitD3); 2430 HUFv05_DECODE_SYMBOLX4_2(op4, &bitD4); 2431 HUFv05_DECODE_SYMBOLX4_1(op1, &bitD1); 2432 HUFv05_DECODE_SYMBOLX4_1(op2, &bitD2); 2433 HUFv05_DECODE_SYMBOLX4_1(op3, &bitD3); 2434 HUFv05_DECODE_SYMBOLX4_1(op4, &bitD4); 2435 HUFv05_DECODE_SYMBOLX4_2(op1, &bitD1); 2436 HUFv05_DECODE_SYMBOLX4_2(op2, &bitD2); 2437 HUFv05_DECODE_SYMBOLX4_2(op3, &bitD3); 2438 HUFv05_DECODE_SYMBOLX4_2(op4, &bitD4); 2439 HUFv05_DECODE_SYMBOLX4_0(op1, &bitD1); 2440 HUFv05_DECODE_SYMBOLX4_0(op2, &bitD2); 2441 HUFv05_DECODE_SYMBOLX4_0(op3, &bitD3); 2442 HUFv05_DECODE_SYMBOLX4_0(op4, &bitD4); 2443 2444 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4); 2445 } 2446 2447 /* check corruption */ 2448 if (op1 > opStart2) return ERROR(corruption_detected); 2449 if (op2 > opStart3) return ERROR(corruption_detected); 2450 if (op3 > opStart4) return ERROR(corruption_detected); 2451 /* note : op4 supposed already verified within main loop */ 2452 2453 /* finish bitStreams one by one */ 2454 HUFv05_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog); 2455 HUFv05_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog); 2456 HUFv05_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog); 2457 HUFv05_decodeStreamX4(op4, &bitD4, oend, dt, dtLog); 2458 2459 /* check */ 2460 endSignal = BITv05_endOfDStream(&bitD1) & BITv05_endOfDStream(&bitD2) & BITv05_endOfDStream(&bitD3) & BITv05_endOfDStream(&bitD4); 2461 if (!endSignal) return ERROR(corruption_detected); 2462 2463 /* decoded size */ 2464 return dstSize; 2465 } 2466} 2467 2468 2469size_t HUFv05_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2470{ 2471 HUFv05_CREATE_STATIC_DTABLEX4(DTable, HUFv05_MAX_TABLELOG); 2472 const BYTE* ip = (const BYTE*) cSrc; 2473 2474 size_t hSize = HUFv05_readDTableX4 (DTable, cSrc, cSrcSize); 2475 if (HUFv05_isError(hSize)) return hSize; 2476 if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 2477 ip += hSize; 2478 cSrcSize -= hSize; 2479 2480 return HUFv05_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2481} 2482 2483 2484/* ********************************/ 2485/* Generic decompression selector */ 2486/* ********************************/ 2487 2488typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t; 2489static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] = 2490{ 2491 /* single, double, quad */ 2492 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */ 2493 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */ 2494 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */ 2495 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */ 2496 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */ 2497 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */ 2498 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */ 2499 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */ 2500 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */ 2501 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */ 2502 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */ 2503 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */ 2504 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */ 2505 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */ 2506 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */ 2507 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */ 2508}; 2509 2510typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); 2511 2512size_t HUFv05_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2513{ 2514 static const decompressionAlgo decompress[3] = { HUFv05_decompress4X2, HUFv05_decompress4X4, NULL }; 2515 /* estimate decompression time */ 2516 U32 Q; 2517 const U32 D256 = (U32)(dstSize >> 8); 2518 U32 Dtime[3]; 2519 U32 algoNb = 0; 2520 int n; 2521 2522 /* validation checks */ 2523 if (dstSize == 0) return ERROR(dstSize_tooSmall); 2524 if (cSrcSize >= dstSize) return ERROR(corruption_detected); /* invalid, or not compressed, but not compressed already dealt with */ 2525 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */ 2526 2527 /* decoder timing evaluation */ 2528 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */ 2529 for (n=0; n<3; n++) 2530 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256); 2531 2532 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */ 2533 2534 if (Dtime[1] < Dtime[0]) algoNb = 1; 2535 2536 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize); 2537 2538 //return HUFv05_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */ 2539 //return HUFv05_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */ 2540 //return HUFv05_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */ 2541} 2542/* 2543 zstd - standard compression library 2544 Copyright (C) 2014-2016, Yann Collet. 2545 2546 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 2547 2548 Redistribution and use in source and binary forms, with or without 2549 modification, are permitted provided that the following conditions are 2550 met: 2551 * Redistributions of source code must retain the above copyright 2552 notice, this list of conditions and the following disclaimer. 2553 * Redistributions in binary form must reproduce the above 2554 copyright notice, this list of conditions and the following disclaimer 2555 in the documentation and/or other materials provided with the 2556 distribution. 2557 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2558 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2559 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2560 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2561 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2562 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2563 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2564 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2565 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2566 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2567 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2568 2569 You can contact the author at : 2570 - zstd source repository : https://github.com/Cyan4973/zstd 2571*/ 2572 2573/* *************************************************************** 2574* Tuning parameters 2575*****************************************************************/ 2576/*! 2577 * HEAPMODE : 2578 * Select how default decompression function ZSTDv05_decompress() will allocate memory, 2579 * in memory stack (0), or in memory heap (1, requires malloc()) 2580 */ 2581#ifndef ZSTDv05_HEAPMODE 2582# define ZSTDv05_HEAPMODE 1 2583#endif 2584 2585 2586/*-******************************************************* 2587* Dependencies 2588*********************************************************/ 2589#include <stdlib.h> /* calloc */ 2590#include <string.h> /* memcpy, memmove */ 2591#include <stdio.h> /* debug only : printf */ 2592 2593 2594/*-******************************************************* 2595* Compiler specifics 2596*********************************************************/ 2597#ifdef _MSC_VER /* Visual Studio */ 2598# include <intrin.h> /* For Visual 2005 */ 2599# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 2600# pragma warning(disable : 4324) /* disable: C4324: padded structure */ 2601#endif 2602 2603 2604/*-************************************* 2605* Local types 2606***************************************/ 2607typedef struct 2608{ 2609 blockType_t blockType; 2610 U32 origSize; 2611} blockProperties_t; 2612 2613 2614/* ******************************************************* 2615* Memory operations 2616**********************************************************/ 2617static void ZSTDv05_copy4(void* dst, const void* src) { memcpy(dst, src, 4); } 2618 2619 2620/* ************************************* 2621* Error Management 2622***************************************/ 2623/*! ZSTDv05_isError() : 2624* tells if a return value is an error code */ 2625unsigned ZSTDv05_isError(size_t code) { return ERR_isError(code); } 2626 2627 2628/*! ZSTDv05_getErrorName() : 2629* provides error code string (useful for debugging) */ 2630const char* ZSTDv05_getErrorName(size_t code) { return ERR_getErrorName(code); } 2631 2632 2633/* ************************************************************* 2634* Context management 2635***************************************************************/ 2636typedef enum { ZSTDv05ds_getFrameHeaderSize, ZSTDv05ds_decodeFrameHeader, 2637 ZSTDv05ds_decodeBlockHeader, ZSTDv05ds_decompressBlock } ZSTDv05_dStage; 2638 2639struct ZSTDv05_DCtx_s 2640{ 2641 FSEv05_DTable LLTable[FSEv05_DTABLE_SIZE_U32(LLFSEv05Log)]; 2642 FSEv05_DTable OffTable[FSEv05_DTABLE_SIZE_U32(OffFSEv05Log)]; 2643 FSEv05_DTable MLTable[FSEv05_DTABLE_SIZE_U32(MLFSEv05Log)]; 2644 unsigned hufTableX4[HUFv05_DTABLE_SIZE(HufLog)]; 2645 const void* previousDstEnd; 2646 const void* base; 2647 const void* vBase; 2648 const void* dictEnd; 2649 size_t expected; 2650 size_t headerSize; 2651 ZSTDv05_parameters params; 2652 blockType_t bType; /* used in ZSTDv05_decompressContinue(), to transfer blockType between header decoding and block decoding stages */ 2653 ZSTDv05_dStage stage; 2654 U32 flagStaticTables; 2655 const BYTE* litPtr; 2656 size_t litSize; 2657 BYTE litBuffer[BLOCKSIZE + WILDCOPY_OVERLENGTH]; 2658 BYTE headerBuffer[ZSTDv05_frameHeaderSize_max]; 2659}; /* typedef'd to ZSTDv05_DCtx within "zstd_static.h" */ 2660 2661size_t ZSTDv05_sizeofDCtx (void) { return sizeof(ZSTDv05_DCtx); } 2662 2663size_t ZSTDv05_decompressBegin(ZSTDv05_DCtx* dctx) 2664{ 2665 dctx->expected = ZSTDv05_frameHeaderSize_min; 2666 dctx->stage = ZSTDv05ds_getFrameHeaderSize; 2667 dctx->previousDstEnd = NULL; 2668 dctx->base = NULL; 2669 dctx->vBase = NULL; 2670 dctx->dictEnd = NULL; 2671 dctx->hufTableX4[0] = HufLog; 2672 dctx->flagStaticTables = 0; 2673 return 0; 2674} 2675 2676ZSTDv05_DCtx* ZSTDv05_createDCtx(void) 2677{ 2678 ZSTDv05_DCtx* dctx = (ZSTDv05_DCtx*)malloc(sizeof(ZSTDv05_DCtx)); 2679 if (dctx==NULL) return NULL; 2680 ZSTDv05_decompressBegin(dctx); 2681 return dctx; 2682} 2683 2684size_t ZSTDv05_freeDCtx(ZSTDv05_DCtx* dctx) 2685{ 2686 free(dctx); 2687 return 0; /* reserved as a potential error code in the future */ 2688} 2689 2690void ZSTDv05_copyDCtx(ZSTDv05_DCtx* dstDCtx, const ZSTDv05_DCtx* srcDCtx) 2691{ 2692 memcpy(dstDCtx, srcDCtx, 2693 sizeof(ZSTDv05_DCtx) - (BLOCKSIZE+WILDCOPY_OVERLENGTH + ZSTDv05_frameHeaderSize_max)); /* no need to copy workspace */ 2694} 2695 2696 2697/* ************************************************************* 2698* Decompression section 2699***************************************************************/ 2700 2701/* Frame format description 2702 Frame Header - [ Block Header - Block ] - Frame End 2703 1) Frame Header 2704 - 4 bytes - Magic Number : ZSTDv05_MAGICNUMBER (defined within zstd_internal.h) 2705 - 1 byte - Window Descriptor 2706 2) Block Header 2707 - 3 bytes, starting with a 2-bits descriptor 2708 Uncompressed, Compressed, Frame End, unused 2709 3) Block 2710 See Block Format Description 2711 4) Frame End 2712 - 3 bytes, compatible with Block Header 2713*/ 2714 2715/* Block format description 2716 2717 Block = Literal Section - Sequences Section 2718 Prerequisite : size of (compressed) block, maximum size of regenerated data 2719 2720 1) Literal Section 2721 2722 1.1) Header : 1-5 bytes 2723 flags: 2 bits 2724 00 compressed by Huff0 2725 01 unused 2726 10 is Raw (uncompressed) 2727 11 is Rle 2728 Note : using 01 => Huff0 with precomputed table ? 2729 Note : delta map ? => compressed ? 2730 2731 1.1.1) Huff0-compressed literal block : 3-5 bytes 2732 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream 2733 srcSize < 1 KB => 3 bytes (2-2-10-10) 2734 srcSize < 16KB => 4 bytes (2-2-14-14) 2735 else => 5 bytes (2-2-18-18) 2736 big endian convention 2737 2738 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes 2739 size : 5 bits: (IS_RAW<<6) + (0<<4) + size 2740 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8) 2741 size&255 2742 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16) 2743 size>>8&255 2744 size&255 2745 2746 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes 2747 size : 5 bits: (IS_RLE<<6) + (0<<4) + size 2748 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8) 2749 size&255 2750 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16) 2751 size>>8&255 2752 size&255 2753 2754 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes 2755 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream 2756 srcSize < 1 KB => 3 bytes (2-2-10-10) 2757 srcSize < 16KB => 4 bytes (2-2-14-14) 2758 else => 5 bytes (2-2-18-18) 2759 big endian convention 2760 2761 1- CTable available (stored into workspace ?) 2762 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?) 2763 2764 2765 1.2) Literal block content 2766 2767 1.2.1) Huff0 block, using sizes from header 2768 See Huff0 format 2769 2770 1.2.2) Huff0 block, using prepared table 2771 2772 1.2.3) Raw content 2773 2774 1.2.4) single byte 2775 2776 2777 2) Sequences section 2778 TO DO 2779*/ 2780 2781 2782/** ZSTDv05_decodeFrameHeader_Part1() : 2783* decode the 1st part of the Frame Header, which tells Frame Header size. 2784* srcSize must be == ZSTDv05_frameHeaderSize_min. 2785* @return : the full size of the Frame Header */ 2786static size_t ZSTDv05_decodeFrameHeader_Part1(ZSTDv05_DCtx* zc, const void* src, size_t srcSize) 2787{ 2788 U32 magicNumber; 2789 if (srcSize != ZSTDv05_frameHeaderSize_min) 2790 return ERROR(srcSize_wrong); 2791 magicNumber = MEM_readLE32(src); 2792 if (magicNumber != ZSTDv05_MAGICNUMBER) return ERROR(prefix_unknown); 2793 zc->headerSize = ZSTDv05_frameHeaderSize_min; 2794 return zc->headerSize; 2795} 2796 2797 2798size_t ZSTDv05_getFrameParams(ZSTDv05_parameters* params, const void* src, size_t srcSize) 2799{ 2800 U32 magicNumber; 2801 if (srcSize < ZSTDv05_frameHeaderSize_min) return ZSTDv05_frameHeaderSize_max; 2802 magicNumber = MEM_readLE32(src); 2803 if (magicNumber != ZSTDv05_MAGICNUMBER) return ERROR(prefix_unknown); 2804 memset(params, 0, sizeof(*params)); 2805 params->windowLog = (((const BYTE*)src)[4] & 15) + ZSTDv05_WINDOWLOG_ABSOLUTEMIN; 2806 if ((((const BYTE*)src)[4] >> 4) != 0) return ERROR(frameParameter_unsupported); /* reserved bits */ 2807 return 0; 2808} 2809 2810/** ZSTDv05_decodeFrameHeader_Part2() : 2811* decode the full Frame Header. 2812* srcSize must be the size provided by ZSTDv05_decodeFrameHeader_Part1(). 2813* @return : 0, or an error code, which can be tested using ZSTDv05_isError() */ 2814static size_t ZSTDv05_decodeFrameHeader_Part2(ZSTDv05_DCtx* zc, const void* src, size_t srcSize) 2815{ 2816 size_t result; 2817 if (srcSize != zc->headerSize) 2818 return ERROR(srcSize_wrong); 2819 result = ZSTDv05_getFrameParams(&(zc->params), src, srcSize); 2820 if ((MEM_32bits()) && (zc->params.windowLog > 25)) return ERROR(frameParameter_unsupported); 2821 return result; 2822} 2823 2824 2825size_t ZSTDv05_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr) 2826{ 2827 const BYTE* const in = (const BYTE* const)src; 2828 BYTE headerFlags; 2829 U32 cSize; 2830 2831 if (srcSize < 3) 2832 return ERROR(srcSize_wrong); 2833 2834 headerFlags = *in; 2835 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16); 2836 2837 bpPtr->blockType = (blockType_t)(headerFlags >> 6); 2838 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0; 2839 2840 if (bpPtr->blockType == bt_end) return 0; 2841 if (bpPtr->blockType == bt_rle) return 1; 2842 return cSize; 2843} 2844 2845 2846static size_t ZSTDv05_copyRawBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 2847{ 2848 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall); 2849 memcpy(dst, src, srcSize); 2850 return srcSize; 2851} 2852 2853 2854/*! ZSTDv05_decodeLiteralsBlock() : 2855 @return : nb of bytes read from src (< srcSize ) */ 2856size_t ZSTDv05_decodeLiteralsBlock(ZSTDv05_DCtx* dctx, 2857 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */ 2858{ 2859 const BYTE* const istart = (const BYTE*) src; 2860 2861 /* any compressed block with literals segment must be at least this size */ 2862 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected); 2863 2864 switch(istart[0]>> 6) 2865 { 2866 case IS_HUFv05: 2867 { 2868 size_t litSize, litCSize, singleStream=0; 2869 U32 lhSize = ((istart[0]) >> 4) & 3; 2870 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */ 2871 switch(lhSize) 2872 { 2873 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ 2874 /* 2 - 2 - 10 - 10 */ 2875 lhSize=3; 2876 singleStream = istart[0] & 16; 2877 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2); 2878 litCSize = ((istart[1] & 3) << 8) + istart[2]; 2879 break; 2880 case 2: 2881 /* 2 - 2 - 14 - 14 */ 2882 lhSize=4; 2883 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6); 2884 litCSize = ((istart[2] & 63) << 8) + istart[3]; 2885 break; 2886 case 3: 2887 /* 2 - 2 - 18 - 18 */ 2888 lhSize=5; 2889 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2); 2890 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4]; 2891 break; 2892 } 2893 if (litSize > BLOCKSIZE) return ERROR(corruption_detected); 2894 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected); 2895 2896 if (HUFv05_isError(singleStream ? 2897 HUFv05_decompress1X2(dctx->litBuffer, litSize, istart+lhSize, litCSize) : 2898 HUFv05_decompress (dctx->litBuffer, litSize, istart+lhSize, litCSize) )) 2899 return ERROR(corruption_detected); 2900 2901 dctx->litPtr = dctx->litBuffer; 2902 dctx->litSize = litSize; 2903 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 2904 return litCSize + lhSize; 2905 } 2906 case IS_PCH: 2907 { 2908 size_t errorCode; 2909 size_t litSize, litCSize; 2910 U32 lhSize = ((istart[0]) >> 4) & 3; 2911 if (lhSize != 1) /* only case supported for now : small litSize, single stream */ 2912 return ERROR(corruption_detected); 2913 if (!dctx->flagStaticTables) 2914 return ERROR(dictionary_corrupted); 2915 2916 /* 2 - 2 - 10 - 10 */ 2917 lhSize=3; 2918 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2); 2919 litCSize = ((istart[1] & 3) << 8) + istart[2]; 2920 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected); 2921 2922 errorCode = HUFv05_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTableX4); 2923 if (HUFv05_isError(errorCode)) return ERROR(corruption_detected); 2924 2925 dctx->litPtr = dctx->litBuffer; 2926 dctx->litSize = litSize; 2927 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 2928 return litCSize + lhSize; 2929 } 2930 case IS_RAW: 2931 { 2932 size_t litSize; 2933 U32 lhSize = ((istart[0]) >> 4) & 3; 2934 switch(lhSize) 2935 { 2936 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ 2937 lhSize=1; 2938 litSize = istart[0] & 31; 2939 break; 2940 case 2: 2941 litSize = ((istart[0] & 15) << 8) + istart[1]; 2942 break; 2943 case 3: 2944 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2]; 2945 break; 2946 } 2947 2948 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */ 2949 if (litSize+lhSize > srcSize) return ERROR(corruption_detected); 2950 memcpy(dctx->litBuffer, istart+lhSize, litSize); 2951 dctx->litPtr = dctx->litBuffer; 2952 dctx->litSize = litSize; 2953 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 2954 return lhSize+litSize; 2955 } 2956 /* direct reference into compressed stream */ 2957 dctx->litPtr = istart+lhSize; 2958 dctx->litSize = litSize; 2959 return lhSize+litSize; 2960 } 2961 case IS_RLE: 2962 { 2963 size_t litSize; 2964 U32 lhSize = ((istart[0]) >> 4) & 3; 2965 switch(lhSize) 2966 { 2967 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ 2968 lhSize = 1; 2969 litSize = istart[0] & 31; 2970 break; 2971 case 2: 2972 litSize = ((istart[0] & 15) << 8) + istart[1]; 2973 break; 2974 case 3: 2975 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2]; 2976 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */ 2977 break; 2978 } 2979 if (litSize > BLOCKSIZE) return ERROR(corruption_detected); 2980 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH); 2981 dctx->litPtr = dctx->litBuffer; 2982 dctx->litSize = litSize; 2983 return lhSize+1; 2984 } 2985 default: 2986 return ERROR(corruption_detected); /* impossible */ 2987 } 2988} 2989 2990 2991size_t ZSTDv05_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr, 2992 FSEv05_DTable* DTableLL, FSEv05_DTable* DTableML, FSEv05_DTable* DTableOffb, 2993 const void* src, size_t srcSize, U32 flagStaticTable) 2994{ 2995 const BYTE* const istart = (const BYTE* const)src; 2996 const BYTE* ip = istart; 2997 const BYTE* const iend = istart + srcSize; 2998 U32 LLtype, Offtype, MLtype; 2999 U32 LLlog, Offlog, MLlog; 3000 size_t dumpsLength; 3001 3002 /* check */ 3003 if (srcSize < MIN_SEQUENCES_SIZE) 3004 return ERROR(srcSize_wrong); 3005 3006 /* SeqHead */ 3007 *nbSeq = *ip++; 3008 if (*nbSeq==0) return 1; 3009 if (*nbSeq >= 128) { 3010 if (ip >= iend) return ERROR(srcSize_wrong); 3011 *nbSeq = ((nbSeq[0]-128)<<8) + *ip++; 3012 } 3013 3014 if (ip >= iend) return ERROR(srcSize_wrong); 3015 LLtype = *ip >> 6; 3016 Offtype = (*ip >> 4) & 3; 3017 MLtype = (*ip >> 2) & 3; 3018 if (*ip & 2) { 3019 if (ip+3 > iend) return ERROR(srcSize_wrong); 3020 dumpsLength = ip[2]; 3021 dumpsLength += ip[1] << 8; 3022 ip += 3; 3023 } else { 3024 if (ip+2 > iend) return ERROR(srcSize_wrong); 3025 dumpsLength = ip[1]; 3026 dumpsLength += (ip[0] & 1) << 8; 3027 ip += 2; 3028 } 3029 *dumpsPtr = ip; 3030 ip += dumpsLength; 3031 *dumpsLengthPtr = dumpsLength; 3032 3033 /* check */ 3034 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */ 3035 3036 /* sequences */ 3037 { 3038 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL >= MaxOff */ 3039 size_t headerSize; 3040 3041 /* Build DTables */ 3042 switch(LLtype) 3043 { 3044 case FSEv05_ENCODING_RLE : 3045 LLlog = 0; 3046 FSEv05_buildDTable_rle(DTableLL, *ip++); 3047 break; 3048 case FSEv05_ENCODING_RAW : 3049 LLlog = LLbits; 3050 FSEv05_buildDTable_raw(DTableLL, LLbits); 3051 break; 3052 case FSEv05_ENCODING_STATIC: 3053 if (!flagStaticTable) return ERROR(corruption_detected); 3054 break; 3055 case FSEv05_ENCODING_DYNAMIC : 3056 default : /* impossible */ 3057 { U32 max = MaxLL; 3058 headerSize = FSEv05_readNCount(norm, &max, &LLlog, ip, iend-ip); 3059 if (FSEv05_isError(headerSize)) return ERROR(GENERIC); 3060 if (LLlog > LLFSEv05Log) return ERROR(corruption_detected); 3061 ip += headerSize; 3062 FSEv05_buildDTable(DTableLL, norm, max, LLlog); 3063 } } 3064 3065 switch(Offtype) 3066 { 3067 case FSEv05_ENCODING_RLE : 3068 Offlog = 0; 3069 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 3070 FSEv05_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */ 3071 break; 3072 case FSEv05_ENCODING_RAW : 3073 Offlog = Offbits; 3074 FSEv05_buildDTable_raw(DTableOffb, Offbits); 3075 break; 3076 case FSEv05_ENCODING_STATIC: 3077 if (!flagStaticTable) return ERROR(corruption_detected); 3078 break; 3079 case FSEv05_ENCODING_DYNAMIC : 3080 default : /* impossible */ 3081 { U32 max = MaxOff; 3082 headerSize = FSEv05_readNCount(norm, &max, &Offlog, ip, iend-ip); 3083 if (FSEv05_isError(headerSize)) return ERROR(GENERIC); 3084 if (Offlog > OffFSEv05Log) return ERROR(corruption_detected); 3085 ip += headerSize; 3086 FSEv05_buildDTable(DTableOffb, norm, max, Offlog); 3087 } } 3088 3089 switch(MLtype) 3090 { 3091 case FSEv05_ENCODING_RLE : 3092 MLlog = 0; 3093 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 3094 FSEv05_buildDTable_rle(DTableML, *ip++); 3095 break; 3096 case FSEv05_ENCODING_RAW : 3097 MLlog = MLbits; 3098 FSEv05_buildDTable_raw(DTableML, MLbits); 3099 break; 3100 case FSEv05_ENCODING_STATIC: 3101 if (!flagStaticTable) return ERROR(corruption_detected); 3102 break; 3103 case FSEv05_ENCODING_DYNAMIC : 3104 default : /* impossible */ 3105 { U32 max = MaxML; 3106 headerSize = FSEv05_readNCount(norm, &max, &MLlog, ip, iend-ip); 3107 if (FSEv05_isError(headerSize)) return ERROR(GENERIC); 3108 if (MLlog > MLFSEv05Log) return ERROR(corruption_detected); 3109 ip += headerSize; 3110 FSEv05_buildDTable(DTableML, norm, max, MLlog); 3111 } } } 3112 3113 return ip-istart; 3114} 3115 3116 3117typedef struct { 3118 size_t litLength; 3119 size_t matchLength; 3120 size_t offset; 3121} seq_t; 3122 3123typedef struct { 3124 BITv05_DStream_t DStream; 3125 FSEv05_DState_t stateLL; 3126 FSEv05_DState_t stateOffb; 3127 FSEv05_DState_t stateML; 3128 size_t prevOffset; 3129 const BYTE* dumps; 3130 const BYTE* dumpsEnd; 3131} seqState_t; 3132 3133 3134 3135static void ZSTDv05_decodeSequence(seq_t* seq, seqState_t* seqState) 3136{ 3137 size_t litLength; 3138 size_t prevOffset; 3139 size_t offset; 3140 size_t matchLength; 3141 const BYTE* dumps = seqState->dumps; 3142 const BYTE* const de = seqState->dumpsEnd; 3143 3144 /* Literal length */ 3145 litLength = FSEv05_peakSymbol(&(seqState->stateLL)); 3146 prevOffset = litLength ? seq->offset : seqState->prevOffset; 3147 if (litLength == MaxLL) { 3148 U32 add = *dumps++; 3149 if (add < 255) litLength += add; 3150 else { 3151 litLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no risk : dumps is always followed by seq tables > 1 byte */ 3152 if (litLength&1) litLength>>=1, dumps += 3; 3153 else litLength = (U16)(litLength)>>1, dumps += 2; 3154 } 3155 if (dumps > de) { litLength = MaxLL+255; } /* late correction, to avoid using uninitialized memory */ 3156 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */ 3157 } 3158 3159 /* Offset */ 3160 { 3161 static const U32 offsetPrefix[MaxOff+1] = { 3162 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256, 3163 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 3164 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 }; 3165 U32 offsetCode = FSEv05_peakSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */ 3166 U32 nbBits = offsetCode - 1; 3167 if (offsetCode==0) nbBits = 0; /* cmove */ 3168 offset = offsetPrefix[offsetCode] + BITv05_readBits(&(seqState->DStream), nbBits); 3169 if (MEM_32bits()) BITv05_reloadDStream(&(seqState->DStream)); 3170 if (offsetCode==0) offset = prevOffset; /* repcode, cmove */ 3171 if (offsetCode | !litLength) seqState->prevOffset = seq->offset; /* cmove */ 3172 FSEv05_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* update */ 3173 } 3174 3175 /* Literal length update */ 3176 FSEv05_decodeSymbol(&(seqState->stateLL), &(seqState->DStream)); /* update */ 3177 if (MEM_32bits()) BITv05_reloadDStream(&(seqState->DStream)); 3178 3179 /* MatchLength */ 3180 matchLength = FSEv05_decodeSymbol(&(seqState->stateML), &(seqState->DStream)); 3181 if (matchLength == MaxML) { 3182 U32 add = *dumps++; 3183 if (add < 255) matchLength += add; 3184 else { 3185 matchLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */ 3186 if (matchLength&1) matchLength>>=1, dumps += 3; 3187 else matchLength = (U16)(matchLength)>>1, dumps += 2; 3188 } 3189 if (dumps > de) { matchLength = MaxML+255; } /* late correction, to avoid using uninitialized memory */ 3190 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */ 3191 } 3192 matchLength += MINMATCH; 3193 3194 /* save result */ 3195 seq->litLength = litLength; 3196 seq->offset = offset; 3197 seq->matchLength = matchLength; 3198 seqState->dumps = dumps; 3199 3200#if 0 /* debug */ 3201 { 3202 static U64 totalDecoded = 0; 3203 printf("pos %6u : %3u literals & match %3u bytes at distance %6u \n", 3204 (U32)(totalDecoded), (U32)litLength, (U32)matchLength, (U32)offset); 3205 totalDecoded += litLength + matchLength; 3206 } 3207#endif 3208} 3209 3210 3211static size_t ZSTDv05_execSequence(BYTE* op, 3212 BYTE* const oend, seq_t sequence, 3213 const BYTE** litPtr, const BYTE* const litLimit, 3214 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd) 3215{ 3216 static const int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */ 3217 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */ 3218 BYTE* const oLitEnd = op + sequence.litLength; 3219 const size_t sequenceLength = sequence.litLength + sequence.matchLength; 3220 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */ 3221 BYTE* const oend_8 = oend-8; 3222 const BYTE* const litEnd = *litPtr + sequence.litLength; 3223 const BYTE* match = oLitEnd - sequence.offset; 3224 3225 /* check */ 3226 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */ 3227 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */ 3228 if (litEnd > litLimit) return ERROR(corruption_detected); /* risk read beyond lit buffer */ 3229 3230 /* copy Literals */ 3231 ZSTDv05_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */ 3232 op = oLitEnd; 3233 *litPtr = litEnd; /* update for next sequence */ 3234 3235 /* copy Match */ 3236 if (sequence.offset > (size_t)(oLitEnd - base)) { 3237 /* offset beyond prefix */ 3238 if (sequence.offset > (size_t)(oLitEnd - vBase)) 3239 return ERROR(corruption_detected); 3240 match = dictEnd - (base-match); 3241 if (match + sequence.matchLength <= dictEnd) { 3242 memmove(oLitEnd, match, sequence.matchLength); 3243 return sequenceLength; 3244 } 3245 /* span extDict & currentPrefixSegment */ 3246 { 3247 size_t length1 = dictEnd - match; 3248 memmove(oLitEnd, match, length1); 3249 op = oLitEnd + length1; 3250 sequence.matchLength -= length1; 3251 match = base; 3252 if (op > oend_8 || sequence.matchLength < MINMATCH) { 3253 while (op < oMatchEnd) *op++ = *match++; 3254 return sequenceLength; 3255 } 3256 } } 3257 /* Requirement: op <= oend_8 */ 3258 3259 /* match within prefix */ 3260 if (sequence.offset < 8) { 3261 /* close range match, overlap */ 3262 const int sub2 = dec64table[sequence.offset]; 3263 op[0] = match[0]; 3264 op[1] = match[1]; 3265 op[2] = match[2]; 3266 op[3] = match[3]; 3267 match += dec32table[sequence.offset]; 3268 ZSTDv05_copy4(op+4, match); 3269 match -= sub2; 3270 } else { 3271 ZSTDv05_copy8(op, match); 3272 } 3273 op += 8; match += 8; 3274 3275 if (oMatchEnd > oend-(16-MINMATCH)) { 3276 if (op < oend_8) { 3277 ZSTDv05_wildcopy(op, match, oend_8 - op); 3278 match += oend_8 - op; 3279 op = oend_8; 3280 } 3281 while (op < oMatchEnd) 3282 *op++ = *match++; 3283 } else { 3284 ZSTDv05_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */ 3285 } 3286 return sequenceLength; 3287} 3288 3289 3290static size_t ZSTDv05_decompressSequences( 3291 ZSTDv05_DCtx* dctx, 3292 void* dst, size_t maxDstSize, 3293 const void* seqStart, size_t seqSize) 3294{ 3295 const BYTE* ip = (const BYTE*)seqStart; 3296 const BYTE* const iend = ip + seqSize; 3297 BYTE* const ostart = (BYTE* const)dst; 3298 BYTE* op = ostart; 3299 BYTE* const oend = ostart + maxDstSize; 3300 size_t errorCode, dumpsLength; 3301 const BYTE* litPtr = dctx->litPtr; 3302 const BYTE* const litEnd = litPtr + dctx->litSize; 3303 int nbSeq; 3304 const BYTE* dumps; 3305 U32* DTableLL = dctx->LLTable; 3306 U32* DTableML = dctx->MLTable; 3307 U32* DTableOffb = dctx->OffTable; 3308 const BYTE* const base = (const BYTE*) (dctx->base); 3309 const BYTE* const vBase = (const BYTE*) (dctx->vBase); 3310 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd); 3311 3312 /* Build Decoding Tables */ 3313 errorCode = ZSTDv05_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength, 3314 DTableLL, DTableML, DTableOffb, 3315 ip, seqSize, dctx->flagStaticTables); 3316 if (ZSTDv05_isError(errorCode)) return errorCode; 3317 ip += errorCode; 3318 3319 /* Regen sequences */ 3320 if (nbSeq) { 3321 seq_t sequence; 3322 seqState_t seqState; 3323 3324 memset(&sequence, 0, sizeof(sequence)); 3325 sequence.offset = REPCODE_STARTVALUE; 3326 seqState.dumps = dumps; 3327 seqState.dumpsEnd = dumps + dumpsLength; 3328 seqState.prevOffset = REPCODE_STARTVALUE; 3329 errorCode = BITv05_initDStream(&(seqState.DStream), ip, iend-ip); 3330 if (ERR_isError(errorCode)) return ERROR(corruption_detected); 3331 FSEv05_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL); 3332 FSEv05_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb); 3333 FSEv05_initDState(&(seqState.stateML), &(seqState.DStream), DTableML); 3334 3335 for ( ; (BITv05_reloadDStream(&(seqState.DStream)) <= BITv05_DStream_completed) && nbSeq ; ) { 3336 size_t oneSeqSize; 3337 nbSeq--; 3338 ZSTDv05_decodeSequence(&sequence, &seqState); 3339 oneSeqSize = ZSTDv05_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd); 3340 if (ZSTDv05_isError(oneSeqSize)) return oneSeqSize; 3341 op += oneSeqSize; 3342 } 3343 3344 /* check if reached exact end */ 3345 if (nbSeq) return ERROR(corruption_detected); 3346 } 3347 3348 /* last literal segment */ 3349 { 3350 size_t lastLLSize = litEnd - litPtr; 3351 if (litPtr > litEnd) return ERROR(corruption_detected); /* too many literals already used */ 3352 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall); 3353 memcpy(op, litPtr, lastLLSize); 3354 op += lastLLSize; 3355 } 3356 3357 return op-ostart; 3358} 3359 3360 3361static void ZSTDv05_checkContinuity(ZSTDv05_DCtx* dctx, const void* dst) 3362{ 3363 if (dst != dctx->previousDstEnd) { /* not contiguous */ 3364 dctx->dictEnd = dctx->previousDstEnd; 3365 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); 3366 dctx->base = dst; 3367 dctx->previousDstEnd = dst; 3368 } 3369} 3370 3371 3372static size_t ZSTDv05_decompressBlock_internal(ZSTDv05_DCtx* dctx, 3373 void* dst, size_t dstCapacity, 3374 const void* src, size_t srcSize) 3375{ /* blockType == blockCompressed */ 3376 const BYTE* ip = (const BYTE*)src; 3377 size_t litCSize; 3378 3379 if (srcSize >= BLOCKSIZE) return ERROR(srcSize_wrong); 3380 3381 /* Decode literals sub-block */ 3382 litCSize = ZSTDv05_decodeLiteralsBlock(dctx, src, srcSize); 3383 if (ZSTDv05_isError(litCSize)) return litCSize; 3384 ip += litCSize; 3385 srcSize -= litCSize; 3386 3387 return ZSTDv05_decompressSequences(dctx, dst, dstCapacity, ip, srcSize); 3388} 3389 3390 3391size_t ZSTDv05_decompressBlock(ZSTDv05_DCtx* dctx, 3392 void* dst, size_t dstCapacity, 3393 const void* src, size_t srcSize) 3394{ 3395 ZSTDv05_checkContinuity(dctx, dst); 3396 return ZSTDv05_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize); 3397} 3398 3399 3400/*! ZSTDv05_decompress_continueDCtx 3401* dctx must have been properly initialized */ 3402static size_t ZSTDv05_decompress_continueDCtx(ZSTDv05_DCtx* dctx, 3403 void* dst, size_t maxDstSize, 3404 const void* src, size_t srcSize) 3405{ 3406 const BYTE* ip = (const BYTE*)src; 3407 const BYTE* iend = ip + srcSize; 3408 BYTE* const ostart = (BYTE* const)dst; 3409 BYTE* op = ostart; 3410 BYTE* const oend = ostart + maxDstSize; 3411 size_t remainingSize = srcSize; 3412 blockProperties_t blockProperties; 3413 3414 /* Frame Header */ 3415 { 3416 size_t frameHeaderSize; 3417 if (srcSize < ZSTDv05_frameHeaderSize_min+ZSTDv05_blockHeaderSize) return ERROR(srcSize_wrong); 3418 frameHeaderSize = ZSTDv05_decodeFrameHeader_Part1(dctx, src, ZSTDv05_frameHeaderSize_min); 3419 if (ZSTDv05_isError(frameHeaderSize)) return frameHeaderSize; 3420 if (srcSize < frameHeaderSize+ZSTDv05_blockHeaderSize) return ERROR(srcSize_wrong); 3421 ip += frameHeaderSize; remainingSize -= frameHeaderSize; 3422 frameHeaderSize = ZSTDv05_decodeFrameHeader_Part2(dctx, src, frameHeaderSize); 3423 if (ZSTDv05_isError(frameHeaderSize)) return frameHeaderSize; 3424 } 3425 3426 /* Loop on each block */ 3427 while (1) 3428 { 3429 size_t decodedSize=0; 3430 size_t cBlockSize = ZSTDv05_getcBlockSize(ip, iend-ip, &blockProperties); 3431 if (ZSTDv05_isError(cBlockSize)) return cBlockSize; 3432 3433 ip += ZSTDv05_blockHeaderSize; 3434 remainingSize -= ZSTDv05_blockHeaderSize; 3435 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); 3436 3437 switch(blockProperties.blockType) 3438 { 3439 case bt_compressed: 3440 decodedSize = ZSTDv05_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize); 3441 break; 3442 case bt_raw : 3443 decodedSize = ZSTDv05_copyRawBlock(op, oend-op, ip, cBlockSize); 3444 break; 3445 case bt_rle : 3446 return ERROR(GENERIC); /* not yet supported */ 3447 break; 3448 case bt_end : 3449 /* end of frame */ 3450 if (remainingSize) return ERROR(srcSize_wrong); 3451 break; 3452 default: 3453 return ERROR(GENERIC); /* impossible */ 3454 } 3455 if (cBlockSize == 0) break; /* bt_end */ 3456 3457 if (ZSTDv05_isError(decodedSize)) return decodedSize; 3458 op += decodedSize; 3459 ip += cBlockSize; 3460 remainingSize -= cBlockSize; 3461 } 3462 3463 return op-ostart; 3464} 3465 3466 3467size_t ZSTDv05_decompress_usingPreparedDCtx(ZSTDv05_DCtx* dctx, const ZSTDv05_DCtx* refDCtx, 3468 void* dst, size_t maxDstSize, 3469 const void* src, size_t srcSize) 3470{ 3471 ZSTDv05_copyDCtx(dctx, refDCtx); 3472 ZSTDv05_checkContinuity(dctx, dst); 3473 return ZSTDv05_decompress_continueDCtx(dctx, dst, maxDstSize, src, srcSize); 3474} 3475 3476 3477size_t ZSTDv05_decompress_usingDict(ZSTDv05_DCtx* dctx, 3478 void* dst, size_t maxDstSize, 3479 const void* src, size_t srcSize, 3480 const void* dict, size_t dictSize) 3481{ 3482 ZSTDv05_decompressBegin_usingDict(dctx, dict, dictSize); 3483 ZSTDv05_checkContinuity(dctx, dst); 3484 return ZSTDv05_decompress_continueDCtx(dctx, dst, maxDstSize, src, srcSize); 3485} 3486 3487 3488size_t ZSTDv05_decompressDCtx(ZSTDv05_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3489{ 3490 return ZSTDv05_decompress_usingDict(dctx, dst, maxDstSize, src, srcSize, NULL, 0); 3491} 3492 3493size_t ZSTDv05_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3494{ 3495#if defined(ZSTDv05_HEAPMODE) && (ZSTDv05_HEAPMODE==1) 3496 size_t regenSize; 3497 ZSTDv05_DCtx* dctx = ZSTDv05_createDCtx(); 3498 if (dctx==NULL) return ERROR(memory_allocation); 3499 regenSize = ZSTDv05_decompressDCtx(dctx, dst, maxDstSize, src, srcSize); 3500 ZSTDv05_freeDCtx(dctx); 3501 return regenSize; 3502#else 3503 ZSTDv05_DCtx dctx; 3504 return ZSTDv05_decompressDCtx(&dctx, dst, maxDstSize, src, srcSize); 3505#endif 3506} 3507 3508size_t ZSTDv05_findFrameCompressedSize(const void *src, size_t srcSize) 3509{ 3510 const BYTE* ip = (const BYTE*)src; 3511 size_t remainingSize = srcSize; 3512 blockProperties_t blockProperties; 3513 3514 /* Frame Header */ 3515 if (srcSize < ZSTDv05_frameHeaderSize_min) return ERROR(srcSize_wrong); 3516 if (MEM_readLE32(src) != ZSTDv05_MAGICNUMBER) return ERROR(prefix_unknown); 3517 ip += ZSTDv05_frameHeaderSize_min; remainingSize -= ZSTDv05_frameHeaderSize_min; 3518 3519 /* Loop on each block */ 3520 while (1) 3521 { 3522 size_t cBlockSize = ZSTDv05_getcBlockSize(ip, remainingSize, &blockProperties); 3523 if (ZSTDv05_isError(cBlockSize)) return cBlockSize; 3524 3525 ip += ZSTDv05_blockHeaderSize; 3526 remainingSize -= ZSTDv05_blockHeaderSize; 3527 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); 3528 3529 if (cBlockSize == 0) break; /* bt_end */ 3530 3531 ip += cBlockSize; 3532 remainingSize -= cBlockSize; 3533 } 3534 3535 return ip - (const BYTE*)src; 3536} 3537 3538/* ****************************** 3539* Streaming Decompression API 3540********************************/ 3541size_t ZSTDv05_nextSrcSizeToDecompress(ZSTDv05_DCtx* dctx) 3542{ 3543 return dctx->expected; 3544} 3545 3546size_t ZSTDv05_decompressContinue(ZSTDv05_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3547{ 3548 /* Sanity check */ 3549 if (srcSize != dctx->expected) return ERROR(srcSize_wrong); 3550 ZSTDv05_checkContinuity(dctx, dst); 3551 3552 /* Decompress : frame header; part 1 */ 3553 switch (dctx->stage) 3554 { 3555 case ZSTDv05ds_getFrameHeaderSize : 3556 /* get frame header size */ 3557 if (srcSize != ZSTDv05_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */ 3558 dctx->headerSize = ZSTDv05_decodeFrameHeader_Part1(dctx, src, ZSTDv05_frameHeaderSize_min); 3559 if (ZSTDv05_isError(dctx->headerSize)) return dctx->headerSize; 3560 memcpy(dctx->headerBuffer, src, ZSTDv05_frameHeaderSize_min); 3561 if (dctx->headerSize > ZSTDv05_frameHeaderSize_min) return ERROR(GENERIC); /* should never happen */ 3562 dctx->expected = 0; /* not necessary to copy more */ 3563 /* fallthrough */ 3564 case ZSTDv05ds_decodeFrameHeader: 3565 /* get frame header */ 3566 { size_t const result = ZSTDv05_decodeFrameHeader_Part2(dctx, dctx->headerBuffer, dctx->headerSize); 3567 if (ZSTDv05_isError(result)) return result; 3568 dctx->expected = ZSTDv05_blockHeaderSize; 3569 dctx->stage = ZSTDv05ds_decodeBlockHeader; 3570 return 0; 3571 } 3572 case ZSTDv05ds_decodeBlockHeader: 3573 { 3574 /* Decode block header */ 3575 blockProperties_t bp; 3576 size_t blockSize = ZSTDv05_getcBlockSize(src, ZSTDv05_blockHeaderSize, &bp); 3577 if (ZSTDv05_isError(blockSize)) return blockSize; 3578 if (bp.blockType == bt_end) { 3579 dctx->expected = 0; 3580 dctx->stage = ZSTDv05ds_getFrameHeaderSize; 3581 } 3582 else { 3583 dctx->expected = blockSize; 3584 dctx->bType = bp.blockType; 3585 dctx->stage = ZSTDv05ds_decompressBlock; 3586 } 3587 return 0; 3588 } 3589 case ZSTDv05ds_decompressBlock: 3590 { 3591 /* Decompress : block content */ 3592 size_t rSize; 3593 switch(dctx->bType) 3594 { 3595 case bt_compressed: 3596 rSize = ZSTDv05_decompressBlock_internal(dctx, dst, maxDstSize, src, srcSize); 3597 break; 3598 case bt_raw : 3599 rSize = ZSTDv05_copyRawBlock(dst, maxDstSize, src, srcSize); 3600 break; 3601 case bt_rle : 3602 return ERROR(GENERIC); /* not yet handled */ 3603 break; 3604 case bt_end : /* should never happen (filtered at phase 1) */ 3605 rSize = 0; 3606 break; 3607 default: 3608 return ERROR(GENERIC); /* impossible */ 3609 } 3610 dctx->stage = ZSTDv05ds_decodeBlockHeader; 3611 dctx->expected = ZSTDv05_blockHeaderSize; 3612 dctx->previousDstEnd = (char*)dst + rSize; 3613 return rSize; 3614 } 3615 default: 3616 return ERROR(GENERIC); /* impossible */ 3617 } 3618} 3619 3620 3621static void ZSTDv05_refDictContent(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize) 3622{ 3623 dctx->dictEnd = dctx->previousDstEnd; 3624 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); 3625 dctx->base = dict; 3626 dctx->previousDstEnd = (const char*)dict + dictSize; 3627} 3628 3629static size_t ZSTDv05_loadEntropy(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize) 3630{ 3631 size_t hSize, offcodeHeaderSize, matchlengthHeaderSize, errorCode, litlengthHeaderSize; 3632 short offcodeNCount[MaxOff+1]; 3633 U32 offcodeMaxValue=MaxOff, offcodeLog; 3634 short matchlengthNCount[MaxML+1]; 3635 unsigned matchlengthMaxValue = MaxML, matchlengthLog; 3636 short litlengthNCount[MaxLL+1]; 3637 unsigned litlengthMaxValue = MaxLL, litlengthLog; 3638 3639 hSize = HUFv05_readDTableX4(dctx->hufTableX4, dict, dictSize); 3640 if (HUFv05_isError(hSize)) return ERROR(dictionary_corrupted); 3641 dict = (const char*)dict + hSize; 3642 dictSize -= hSize; 3643 3644 offcodeHeaderSize = FSEv05_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dict, dictSize); 3645 if (FSEv05_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted); 3646 if (offcodeLog > OffFSEv05Log) return ERROR(dictionary_corrupted); 3647 errorCode = FSEv05_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog); 3648 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted); 3649 dict = (const char*)dict + offcodeHeaderSize; 3650 dictSize -= offcodeHeaderSize; 3651 3652 matchlengthHeaderSize = FSEv05_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dict, dictSize); 3653 if (FSEv05_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted); 3654 if (matchlengthLog > MLFSEv05Log) return ERROR(dictionary_corrupted); 3655 errorCode = FSEv05_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog); 3656 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted); 3657 dict = (const char*)dict + matchlengthHeaderSize; 3658 dictSize -= matchlengthHeaderSize; 3659 3660 litlengthHeaderSize = FSEv05_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dict, dictSize); 3661 if (litlengthLog > LLFSEv05Log) return ERROR(dictionary_corrupted); 3662 if (FSEv05_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted); 3663 errorCode = FSEv05_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog); 3664 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted); 3665 3666 dctx->flagStaticTables = 1; 3667 return hSize + offcodeHeaderSize + matchlengthHeaderSize + litlengthHeaderSize; 3668} 3669 3670static size_t ZSTDv05_decompress_insertDictionary(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize) 3671{ 3672 size_t eSize; 3673 U32 magic = MEM_readLE32(dict); 3674 if (magic != ZSTDv05_DICT_MAGIC) { 3675 /* pure content mode */ 3676 ZSTDv05_refDictContent(dctx, dict, dictSize); 3677 return 0; 3678 } 3679 /* load entropy tables */ 3680 dict = (const char*)dict + 4; 3681 dictSize -= 4; 3682 eSize = ZSTDv05_loadEntropy(dctx, dict, dictSize); 3683 if (ZSTDv05_isError(eSize)) return ERROR(dictionary_corrupted); 3684 3685 /* reference dictionary content */ 3686 dict = (const char*)dict + eSize; 3687 dictSize -= eSize; 3688 ZSTDv05_refDictContent(dctx, dict, dictSize); 3689 3690 return 0; 3691} 3692 3693 3694size_t ZSTDv05_decompressBegin_usingDict(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize) 3695{ 3696 size_t errorCode; 3697 errorCode = ZSTDv05_decompressBegin(dctx); 3698 if (ZSTDv05_isError(errorCode)) return errorCode; 3699 3700 if (dict && dictSize) { 3701 errorCode = ZSTDv05_decompress_insertDictionary(dctx, dict, dictSize); 3702 if (ZSTDv05_isError(errorCode)) return ERROR(dictionary_corrupted); 3703 } 3704 3705 return 0; 3706} 3707 3708/* 3709 Buffered version of Zstd compression library 3710 Copyright (C) 2015-2016, Yann Collet. 3711 3712 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 3713 3714 Redistribution and use in source and binary forms, with or without 3715 modification, are permitted provided that the following conditions are 3716 met: 3717 * Redistributions of source code must retain the above copyright 3718 notice, this list of conditions and the following disclaimer. 3719 * Redistributions in binary form must reproduce the above 3720 copyright notice, this list of conditions and the following disclaimer 3721 in the documentation and/or other materials provided with the 3722 distribution. 3723 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 3724 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 3725 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 3726 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 3727 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3728 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3729 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3730 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3731 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3732 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3733 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3734 3735 You can contact the author at : 3736 - zstd source repository : https://github.com/Cyan4973/zstd 3737 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c 3738*/ 3739 3740/* The objects defined into this file should be considered experimental. 3741 * They are not labelled stable, as their prototype may change in the future. 3742 * You can use them for tests, provide feedback, or if you can endure risk of future changes. 3743 */ 3744 3745 3746 3747/* ************************************* 3748* Constants 3749***************************************/ 3750static size_t ZBUFFv05_blockHeaderSize = 3; 3751 3752 3753 3754/* *** Compression *** */ 3755 3756static size_t ZBUFFv05_limitCopy(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3757{ 3758 size_t length = MIN(maxDstSize, srcSize); 3759 memcpy(dst, src, length); 3760 return length; 3761} 3762 3763 3764 3765 3766/** ************************************************ 3767* Streaming decompression 3768* 3769* A ZBUFFv05_DCtx object is required to track streaming operation. 3770* Use ZBUFFv05_createDCtx() and ZBUFFv05_freeDCtx() to create/release resources. 3771* Use ZBUFFv05_decompressInit() to start a new decompression operation. 3772* ZBUFFv05_DCtx objects can be reused multiple times. 3773* 3774* Use ZBUFFv05_decompressContinue() repetitively to consume your input. 3775* *srcSizePtr and *maxDstSizePtr can be any size. 3776* The function will report how many bytes were read or written by modifying *srcSizePtr and *maxDstSizePtr. 3777* 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. 3778* The content of dst will be overwritten (up to *maxDstSizePtr) at each function call, so save its content if it matters or change dst . 3779* return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency) 3780* or 0 when a frame is completely decoded 3781* or an error code, which can be tested using ZBUFFv05_isError(). 3782* 3783* Hint : recommended buffer sizes (not compulsory) 3784* output : 128 KB block size is the internal unit, it ensures it's always possible to write a full block when it's decoded. 3785* input : just follow indications from ZBUFFv05_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 . 3786* **************************************************/ 3787 3788typedef enum { ZBUFFv05ds_init, ZBUFFv05ds_readHeader, ZBUFFv05ds_loadHeader, ZBUFFv05ds_decodeHeader, 3789 ZBUFFv05ds_read, ZBUFFv05ds_load, ZBUFFv05ds_flush } ZBUFFv05_dStage; 3790 3791/* *** Resource management *** */ 3792 3793#define ZSTDv05_frameHeaderSize_max 5 /* too magical, should come from reference */ 3794struct ZBUFFv05_DCtx_s { 3795 ZSTDv05_DCtx* zc; 3796 ZSTDv05_parameters params; 3797 char* inBuff; 3798 size_t inBuffSize; 3799 size_t inPos; 3800 char* outBuff; 3801 size_t outBuffSize; 3802 size_t outStart; 3803 size_t outEnd; 3804 size_t hPos; 3805 ZBUFFv05_dStage stage; 3806 unsigned char headerBuffer[ZSTDv05_frameHeaderSize_max]; 3807}; /* typedef'd to ZBUFFv05_DCtx within "zstd_buffered.h" */ 3808 3809 3810ZBUFFv05_DCtx* ZBUFFv05_createDCtx(void) 3811{ 3812 ZBUFFv05_DCtx* zbc = (ZBUFFv05_DCtx*)malloc(sizeof(ZBUFFv05_DCtx)); 3813 if (zbc==NULL) return NULL; 3814 memset(zbc, 0, sizeof(*zbc)); 3815 zbc->zc = ZSTDv05_createDCtx(); 3816 zbc->stage = ZBUFFv05ds_init; 3817 return zbc; 3818} 3819 3820size_t ZBUFFv05_freeDCtx(ZBUFFv05_DCtx* zbc) 3821{ 3822 if (zbc==NULL) return 0; /* support free on null */ 3823 ZSTDv05_freeDCtx(zbc->zc); 3824 free(zbc->inBuff); 3825 free(zbc->outBuff); 3826 free(zbc); 3827 return 0; 3828} 3829 3830 3831/* *** Initialization *** */ 3832 3833size_t ZBUFFv05_decompressInitDictionary(ZBUFFv05_DCtx* zbc, const void* dict, size_t dictSize) 3834{ 3835 zbc->stage = ZBUFFv05ds_readHeader; 3836 zbc->hPos = zbc->inPos = zbc->outStart = zbc->outEnd = 0; 3837 return ZSTDv05_decompressBegin_usingDict(zbc->zc, dict, dictSize); 3838} 3839 3840size_t ZBUFFv05_decompressInit(ZBUFFv05_DCtx* zbc) 3841{ 3842 return ZBUFFv05_decompressInitDictionary(zbc, NULL, 0); 3843} 3844 3845 3846/* *** Decompression *** */ 3847 3848size_t ZBUFFv05_decompressContinue(ZBUFFv05_DCtx* zbc, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr) 3849{ 3850 const char* const istart = (const char*)src; 3851 const char* ip = istart; 3852 const char* const iend = istart + *srcSizePtr; 3853 char* const ostart = (char*)dst; 3854 char* op = ostart; 3855 char* const oend = ostart + *maxDstSizePtr; 3856 U32 notDone = 1; 3857 3858 while (notDone) { 3859 switch(zbc->stage) 3860 { 3861 case ZBUFFv05ds_init : 3862 return ERROR(init_missing); 3863 3864 case ZBUFFv05ds_readHeader : 3865 /* read header from src */ 3866 { 3867 size_t headerSize = ZSTDv05_getFrameParams(&(zbc->params), src, *srcSizePtr); 3868 if (ZSTDv05_isError(headerSize)) return headerSize; 3869 if (headerSize) { 3870 /* not enough input to decode header : tell how many bytes would be necessary */ 3871 memcpy(zbc->headerBuffer+zbc->hPos, src, *srcSizePtr); 3872 zbc->hPos += *srcSizePtr; 3873 *maxDstSizePtr = 0; 3874 zbc->stage = ZBUFFv05ds_loadHeader; 3875 return headerSize - zbc->hPos; 3876 } 3877 zbc->stage = ZBUFFv05ds_decodeHeader; 3878 break; 3879 } 3880 /* fall-through */ 3881 case ZBUFFv05ds_loadHeader: 3882 /* complete header from src */ 3883 { 3884 size_t headerSize = ZBUFFv05_limitCopy( 3885 zbc->headerBuffer + zbc->hPos, ZSTDv05_frameHeaderSize_max - zbc->hPos, 3886 src, *srcSizePtr); 3887 zbc->hPos += headerSize; 3888 ip += headerSize; 3889 headerSize = ZSTDv05_getFrameParams(&(zbc->params), zbc->headerBuffer, zbc->hPos); 3890 if (ZSTDv05_isError(headerSize)) return headerSize; 3891 if (headerSize) { 3892 /* not enough input to decode header : tell how many bytes would be necessary */ 3893 *maxDstSizePtr = 0; 3894 return headerSize - zbc->hPos; 3895 } 3896 // zbc->stage = ZBUFFv05ds_decodeHeader; break; /* useless : stage follows */ 3897 } 3898 /* fall-through */ 3899 case ZBUFFv05ds_decodeHeader: 3900 /* apply header to create / resize buffers */ 3901 { 3902 size_t neededOutSize = (size_t)1 << zbc->params.windowLog; 3903 size_t neededInSize = BLOCKSIZE; /* a block is never > BLOCKSIZE */ 3904 if (zbc->inBuffSize < neededInSize) { 3905 free(zbc->inBuff); 3906 zbc->inBuffSize = neededInSize; 3907 zbc->inBuff = (char*)malloc(neededInSize); 3908 if (zbc->inBuff == NULL) return ERROR(memory_allocation); 3909 } 3910 if (zbc->outBuffSize < neededOutSize) { 3911 free(zbc->outBuff); 3912 zbc->outBuffSize = neededOutSize; 3913 zbc->outBuff = (char*)malloc(neededOutSize); 3914 if (zbc->outBuff == NULL) return ERROR(memory_allocation); 3915 } } 3916 if (zbc->hPos) { 3917 /* some data already loaded into headerBuffer : transfer into inBuff */ 3918 memcpy(zbc->inBuff, zbc->headerBuffer, zbc->hPos); 3919 zbc->inPos = zbc->hPos; 3920 zbc->hPos = 0; 3921 zbc->stage = ZBUFFv05ds_load; 3922 break; 3923 } 3924 zbc->stage = ZBUFFv05ds_read; 3925 /* fall-through */ 3926 case ZBUFFv05ds_read: 3927 { 3928 size_t neededInSize = ZSTDv05_nextSrcSizeToDecompress(zbc->zc); 3929 if (neededInSize==0) { /* end of frame */ 3930 zbc->stage = ZBUFFv05ds_init; 3931 notDone = 0; 3932 break; 3933 } 3934 if ((size_t)(iend-ip) >= neededInSize) { 3935 /* directly decode from src */ 3936 size_t decodedSize = ZSTDv05_decompressContinue(zbc->zc, 3937 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart, 3938 ip, neededInSize); 3939 if (ZSTDv05_isError(decodedSize)) return decodedSize; 3940 ip += neededInSize; 3941 if (!decodedSize) break; /* this was just a header */ 3942 zbc->outEnd = zbc->outStart + decodedSize; 3943 zbc->stage = ZBUFFv05ds_flush; 3944 break; 3945 } 3946 if (ip==iend) { notDone = 0; break; } /* no more input */ 3947 zbc->stage = ZBUFFv05ds_load; 3948 } 3949 /* fall-through */ 3950 case ZBUFFv05ds_load: 3951 { 3952 size_t neededInSize = ZSTDv05_nextSrcSizeToDecompress(zbc->zc); 3953 size_t toLoad = neededInSize - zbc->inPos; /* should always be <= remaining space within inBuff */ 3954 size_t loadedSize; 3955 if (toLoad > zbc->inBuffSize - zbc->inPos) return ERROR(corruption_detected); /* should never happen */ 3956 loadedSize = ZBUFFv05_limitCopy(zbc->inBuff + zbc->inPos, toLoad, ip, iend-ip); 3957 ip += loadedSize; 3958 zbc->inPos += loadedSize; 3959 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */ 3960 { 3961 size_t decodedSize = ZSTDv05_decompressContinue(zbc->zc, 3962 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart, 3963 zbc->inBuff, neededInSize); 3964 if (ZSTDv05_isError(decodedSize)) return decodedSize; 3965 zbc->inPos = 0; /* input is consumed */ 3966 if (!decodedSize) { zbc->stage = ZBUFFv05ds_read; break; } /* this was just a header */ 3967 zbc->outEnd = zbc->outStart + decodedSize; 3968 zbc->stage = ZBUFFv05ds_flush; 3969 // break; /* ZBUFFv05ds_flush follows */ 3970 } 3971 } 3972 /* fall-through */ 3973 case ZBUFFv05ds_flush: 3974 { 3975 size_t toFlushSize = zbc->outEnd - zbc->outStart; 3976 size_t flushedSize = ZBUFFv05_limitCopy(op, oend-op, zbc->outBuff + zbc->outStart, toFlushSize); 3977 op += flushedSize; 3978 zbc->outStart += flushedSize; 3979 if (flushedSize == toFlushSize) { 3980 zbc->stage = ZBUFFv05ds_read; 3981 if (zbc->outStart + BLOCKSIZE > zbc->outBuffSize) 3982 zbc->outStart = zbc->outEnd = 0; 3983 break; 3984 } 3985 /* cannot flush everything */ 3986 notDone = 0; 3987 break; 3988 } 3989 default: return ERROR(GENERIC); /* impossible */ 3990 } } 3991 3992 *srcSizePtr = ip-istart; 3993 *maxDstSizePtr = op-ostart; 3994 3995 { size_t nextSrcSizeHint = ZSTDv05_nextSrcSizeToDecompress(zbc->zc); 3996 if (nextSrcSizeHint > ZBUFFv05_blockHeaderSize) nextSrcSizeHint+= ZBUFFv05_blockHeaderSize; /* get next block header too */ 3997 nextSrcSizeHint -= zbc->inPos; /* already loaded*/ 3998 return nextSrcSizeHint; 3999 } 4000} 4001 4002 4003 4004/* ************************************* 4005* Tool functions 4006***************************************/ 4007unsigned ZBUFFv05_isError(size_t errorCode) { return ERR_isError(errorCode); } 4008const char* ZBUFFv05_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); } 4009 4010size_t ZBUFFv05_recommendedDInSize(void) { return BLOCKSIZE + ZBUFFv05_blockHeaderSize /* block header size*/ ; } 4011size_t ZBUFFv05_recommendedDOutSize(void) { return BLOCKSIZE; } 4012