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