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 <stddef.h> /* size_t, ptrdiff_t */ 14#include <string.h> /* memcpy */ 15#include <stdlib.h> /* malloc, free, qsort */ 16 17#ifndef XXH_STATIC_LINKING_ONLY 18# define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */ 19#endif 20#include "../common/xxhash.h" /* XXH64_* */ 21#include "zstd_v07.h" 22 23#define FSEv07_STATIC_LINKING_ONLY /* FSEv07_MIN_TABLELOG */ 24#define HUFv07_STATIC_LINKING_ONLY /* HUFv07_TABLELOG_ABSOLUTEMAX */ 25#define ZSTDv07_STATIC_LINKING_ONLY 26 27#include "../common/error_private.h" 28 29 30#ifdef ZSTDv07_STATIC_LINKING_ONLY 31 32/* ==================================================================================== 33 * The definitions in this section are considered experimental. 34 * They should never be used with a dynamic library, as they may change in the future. 35 * They are provided for advanced usages. 36 * Use them only in association with static linking. 37 * ==================================================================================== */ 38 39/*--- Constants ---*/ 40#define ZSTDv07_MAGIC_SKIPPABLE_START 0x184D2A50U 41 42#define ZSTDv07_WINDOWLOG_MAX_32 25 43#define ZSTDv07_WINDOWLOG_MAX_64 27 44#define ZSTDv07_WINDOWLOG_MAX ((U32)(MEM_32bits() ? ZSTDv07_WINDOWLOG_MAX_32 : ZSTDv07_WINDOWLOG_MAX_64)) 45#define ZSTDv07_WINDOWLOG_MIN 18 46#define ZSTDv07_CHAINLOG_MAX (ZSTDv07_WINDOWLOG_MAX+1) 47#define ZSTDv07_CHAINLOG_MIN 4 48#define ZSTDv07_HASHLOG_MAX ZSTDv07_WINDOWLOG_MAX 49#define ZSTDv07_HASHLOG_MIN 12 50#define ZSTDv07_HASHLOG3_MAX 17 51#define ZSTDv07_SEARCHLOG_MAX (ZSTDv07_WINDOWLOG_MAX-1) 52#define ZSTDv07_SEARCHLOG_MIN 1 53#define ZSTDv07_SEARCHLENGTH_MAX 7 54#define ZSTDv07_SEARCHLENGTH_MIN 3 55#define ZSTDv07_TARGETLENGTH_MIN 4 56#define ZSTDv07_TARGETLENGTH_MAX 999 57 58#define ZSTDv07_FRAMEHEADERSIZE_MAX 18 /* for static allocation */ 59static const size_t ZSTDv07_frameHeaderSize_min = 5; 60static const size_t ZSTDv07_frameHeaderSize_max = ZSTDv07_FRAMEHEADERSIZE_MAX; 61static const size_t ZSTDv07_skippableHeaderSize = 8; /* magic number + skippable frame length */ 62 63 64/* custom memory allocation functions */ 65typedef void* (*ZSTDv07_allocFunction) (void* opaque, size_t size); 66typedef void (*ZSTDv07_freeFunction) (void* opaque, void* address); 67typedef struct { ZSTDv07_allocFunction customAlloc; ZSTDv07_freeFunction customFree; void* opaque; } ZSTDv07_customMem; 68 69 70/*--- Advanced Decompression functions ---*/ 71 72/*! ZSTDv07_estimateDCtxSize() : 73 * Gives the potential amount of memory allocated to create a ZSTDv07_DCtx */ 74ZSTDLIBv07_API size_t ZSTDv07_estimateDCtxSize(void); 75 76/*! ZSTDv07_createDCtx_advanced() : 77 * Create a ZSTD decompression context using external alloc and free functions */ 78ZSTDLIBv07_API ZSTDv07_DCtx* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem); 79 80/*! ZSTDv07_sizeofDCtx() : 81 * Gives the amount of memory used by a given ZSTDv07_DCtx */ 82ZSTDLIBv07_API size_t ZSTDv07_sizeofDCtx(const ZSTDv07_DCtx* dctx); 83 84 85/* ****************************************************************** 86* Buffer-less streaming functions (synchronous mode) 87********************************************************************/ 88 89ZSTDLIBv07_API size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx* dctx); 90ZSTDLIBv07_API size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize); 91ZSTDLIBv07_API void ZSTDv07_copyDCtx(ZSTDv07_DCtx* dctx, const ZSTDv07_DCtx* preparedDCtx); 92 93ZSTDLIBv07_API size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx* dctx); 94ZSTDLIBv07_API size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize); 95 96/* 97 Buffer-less streaming decompression (synchronous mode) 98 99 A ZSTDv07_DCtx object is required to track streaming operations. 100 Use ZSTDv07_createDCtx() / ZSTDv07_freeDCtx() to manage it. 101 A ZSTDv07_DCtx object can be re-used multiple times. 102 103 First optional operation is to retrieve frame parameters, using ZSTDv07_getFrameParams(), which doesn't consume the input. 104 It can provide the minimum size of rolling buffer required to properly decompress data (`windowSize`), 105 and optionally the final size of uncompressed content. 106 (Note : content size is an optional info that may not be present. 0 means : content size unknown) 107 Frame parameters are extracted from the beginning of compressed frame. 108 The amount of data to read is variable, from ZSTDv07_frameHeaderSize_min to ZSTDv07_frameHeaderSize_max (so if `srcSize` >= ZSTDv07_frameHeaderSize_max, it will always work) 109 If `srcSize` is too small for operation to succeed, function will return the minimum size it requires to produce a result. 110 Result : 0 when successful, it means the ZSTDv07_frameParams structure has been filled. 111 >0 : means there is not enough data into `src`. Provides the expected size to successfully decode header. 112 errorCode, which can be tested using ZSTDv07_isError() 113 114 Start decompression, with ZSTDv07_decompressBegin() or ZSTDv07_decompressBegin_usingDict(). 115 Alternatively, you can copy a prepared context, using ZSTDv07_copyDCtx(). 116 117 Then use ZSTDv07_nextSrcSizeToDecompress() and ZSTDv07_decompressContinue() alternatively. 118 ZSTDv07_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv07_decompressContinue(). 119 ZSTDv07_decompressContinue() requires this exact amount of bytes, or it will fail. 120 121 @result of ZSTDv07_decompressContinue() is the number of bytes regenerated within 'dst' (necessarily <= dstCapacity). 122 It can be zero, which is not an error; it just means ZSTDv07_decompressContinue() has decoded some header. 123 124 ZSTDv07_decompressContinue() needs previous data blocks during decompression, up to `windowSize`. 125 They should preferably be located contiguously, prior to current block. 126 Alternatively, a round buffer of sufficient size is also possible. Sufficient size is determined by frame parameters. 127 ZSTDv07_decompressContinue() is very sensitive to contiguity, 128 if 2 blocks don't follow each other, make sure that either the compressor breaks contiguity at the same place, 129 or that previous contiguous segment is large enough to properly handle maximum back-reference. 130 131 A frame is fully decoded when ZSTDv07_nextSrcSizeToDecompress() returns zero. 132 Context can then be reset to start a new decompression. 133 134 135 == Special case : skippable frames == 136 137 Skippable frames allow the integration of user-defined data into a flow of concatenated frames. 138 Skippable frames will be ignored (skipped) by a decompressor. The format of skippable frame is following: 139 a) Skippable frame ID - 4 Bytes, Little endian format, any value from 0x184D2A50 to 0x184D2A5F 140 b) Frame Size - 4 Bytes, Little endian format, unsigned 32-bits 141 c) Frame Content - any content (User Data) of length equal to Frame Size 142 For skippable frames ZSTDv07_decompressContinue() always returns 0. 143 For skippable frames ZSTDv07_getFrameParams() returns fparamsPtr->windowLog==0 what means that a frame is skippable. 144 It also returns Frame Size as fparamsPtr->frameContentSize. 145*/ 146 147 148/* ************************************** 149* Block functions 150****************************************/ 151/*! Block functions produce and decode raw zstd blocks, without frame metadata. 152 Frame metadata cost is typically ~18 bytes, which can be non-negligible for very small blocks (< 100 bytes). 153 User will have to take in charge required information to regenerate data, such as compressed and content sizes. 154 155 A few rules to respect : 156 - Compressing and decompressing require a context structure 157 + Use ZSTDv07_createCCtx() and ZSTDv07_createDCtx() 158 - It is necessary to init context before starting 159 + compression : ZSTDv07_compressBegin() 160 + decompression : ZSTDv07_decompressBegin() 161 + variants _usingDict() are also allowed 162 + copyCCtx() and copyDCtx() work too 163 - Block size is limited, it must be <= ZSTDv07_getBlockSizeMax() 164 + If you need to compress more, cut data into multiple blocks 165 + Consider using the regular ZSTDv07_compress() instead, as frame metadata costs become negligible when source size is large. 166 - When a block is considered not compressible enough, ZSTDv07_compressBlock() result will be zero. 167 In which case, nothing is produced into `dst`. 168 + User must test for such outcome and deal directly with uncompressed data 169 + ZSTDv07_decompressBlock() doesn't accept uncompressed data as input !!! 170 + In case of multiple successive blocks, decoder must be informed of uncompressed block existence to follow proper history. 171 Use ZSTDv07_insertBlock() in such a case. 172*/ 173 174#define ZSTDv07_BLOCKSIZE_ABSOLUTEMAX (128 * 1024) /* define, for static allocation */ 175ZSTDLIBv07_API size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize); 176ZSTDLIBv07_API size_t ZSTDv07_insertBlock(ZSTDv07_DCtx* dctx, const void* blockStart, size_t blockSize); /**< insert block into `dctx` history. Useful for uncompressed blocks */ 177 178 179#endif /* ZSTDv07_STATIC_LINKING_ONLY */ 180 181 182/* ****************************************************************** 183 mem.h 184 low-level memory access routines 185 Copyright (C) 2013-2015, Yann Collet. 186 187 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 188 189 Redistribution and use in source and binary forms, with or without 190 modification, are permitted provided that the following conditions are 191 met: 192 193 * Redistributions of source code must retain the above copyright 194 notice, this list of conditions and the following disclaimer. 195 * Redistributions in binary form must reproduce the above 196 copyright notice, this list of conditions and the following disclaimer 197 in the documentation and/or other materials provided with the 198 distribution. 199 200 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 201 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 202 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 203 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 204 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 205 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 206 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 207 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 208 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 209 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 210 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 211 212 You can contact the author at : 213 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy 214 - Public forum : https://groups.google.com/forum/#!forum/lz4c 215****************************************************************** */ 216#ifndef MEM_H_MODULE 217#define MEM_H_MODULE 218 219#if defined (__cplusplus) 220extern "C" { 221#endif 222 223/*-**************************************** 224* Compiler specifics 225******************************************/ 226#if defined(_MSC_VER) /* Visual Studio */ 227# include <stdlib.h> /* _byteswap_ulong */ 228# include <intrin.h> /* _byteswap_* */ 229#endif 230#if defined(__GNUC__) 231# define MEM_STATIC static __attribute__((unused)) 232#elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 233# define MEM_STATIC static inline 234#elif defined(_MSC_VER) 235# define MEM_STATIC static __inline 236#else 237# define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */ 238#endif 239 240 241/*-************************************************************** 242* Basic Types 243*****************************************************************/ 244#if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) 245# if defined(_AIX) 246# include <inttypes.h> 247# else 248# include <stdint.h> /* intptr_t */ 249# endif 250 typedef uint8_t BYTE; 251 typedef uint16_t U16; 252 typedef int16_t S16; 253 typedef uint32_t U32; 254 typedef int32_t S32; 255 typedef uint64_t U64; 256 typedef int64_t S64; 257#else 258 typedef unsigned char BYTE; 259 typedef unsigned short U16; 260 typedef signed short S16; 261 typedef unsigned int U32; 262 typedef signed int S32; 263 typedef unsigned long long U64; 264 typedef signed long long S64; 265#endif 266 267 268/*-************************************************************** 269* Memory I/O 270*****************************************************************/ 271/* MEM_FORCE_MEMORY_ACCESS : 272 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable. 273 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal. 274 * The below switch allow to select different access method for improved performance. 275 * Method 0 (default) : use `memcpy()`. Safe and portable. 276 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable). 277 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`. 278 * Method 2 : direct access. This method is portable but violate C standard. 279 * It can generate buggy code on targets depending on alignment. 280 * In some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6) 281 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details. 282 * Prefer these methods in priority order (0 > 1 > 2) 283 */ 284#ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */ 285# if defined(__INTEL_COMPILER) || defined(__GNUC__) || defined(__ICCARM__) 286# define MEM_FORCE_MEMORY_ACCESS 1 287# endif 288#endif 289 290MEM_STATIC unsigned MEM_32bits(void) { return sizeof(size_t)==4; } 291MEM_STATIC unsigned MEM_64bits(void) { return sizeof(size_t)==8; } 292 293MEM_STATIC unsigned MEM_isLittleEndian(void) 294{ 295 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ 296 return one.c[0]; 297} 298 299#if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2) 300 301/* violates C standard, by lying on structure alignment. 302Only use if no other choice to achieve best performance on target platform */ 303MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; } 304MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; } 305MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; } 306 307MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; } 308 309#elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1) 310 311/* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ 312/* currently only defined for gcc and icc */ 313typedef union { U16 u16; U32 u32; U64 u64; size_t st; } __attribute__((packed)) unalign; 314 315MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; } 316MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } 317MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; } 318 319MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; } 320 321#else 322 323/* default method, safe and standard. 324 can sometimes prove slower */ 325 326MEM_STATIC U16 MEM_read16(const void* memPtr) 327{ 328 U16 val; memcpy(&val, memPtr, sizeof(val)); return val; 329} 330 331MEM_STATIC U32 MEM_read32(const void* memPtr) 332{ 333 U32 val; memcpy(&val, memPtr, sizeof(val)); return val; 334} 335 336MEM_STATIC U64 MEM_read64(const void* memPtr) 337{ 338 U64 val; memcpy(&val, memPtr, sizeof(val)); return val; 339} 340 341MEM_STATIC void MEM_write16(void* memPtr, U16 value) 342{ 343 memcpy(memPtr, &value, sizeof(value)); 344} 345 346#endif /* MEM_FORCE_MEMORY_ACCESS */ 347 348MEM_STATIC U32 MEM_swap32(U32 in) 349{ 350#if defined(_MSC_VER) /* Visual Studio */ 351 return _byteswap_ulong(in); 352#elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403) 353 return __builtin_bswap32(in); 354#else 355 return ((in << 24) & 0xff000000 ) | 356 ((in << 8) & 0x00ff0000 ) | 357 ((in >> 8) & 0x0000ff00 ) | 358 ((in >> 24) & 0x000000ff ); 359#endif 360} 361 362MEM_STATIC U64 MEM_swap64(U64 in) 363{ 364#if defined(_MSC_VER) /* Visual Studio */ 365 return _byteswap_uint64(in); 366#elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403) 367 return __builtin_bswap64(in); 368#else 369 return ((in << 56) & 0xff00000000000000ULL) | 370 ((in << 40) & 0x00ff000000000000ULL) | 371 ((in << 24) & 0x0000ff0000000000ULL) | 372 ((in << 8) & 0x000000ff00000000ULL) | 373 ((in >> 8) & 0x00000000ff000000ULL) | 374 ((in >> 24) & 0x0000000000ff0000ULL) | 375 ((in >> 40) & 0x000000000000ff00ULL) | 376 ((in >> 56) & 0x00000000000000ffULL); 377#endif 378} 379 380 381/*=== Little endian r/w ===*/ 382 383MEM_STATIC U16 MEM_readLE16(const void* memPtr) 384{ 385 if (MEM_isLittleEndian()) 386 return MEM_read16(memPtr); 387 else { 388 const BYTE* p = (const BYTE*)memPtr; 389 return (U16)(p[0] + (p[1]<<8)); 390 } 391} 392 393MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val) 394{ 395 if (MEM_isLittleEndian()) { 396 MEM_write16(memPtr, val); 397 } else { 398 BYTE* p = (BYTE*)memPtr; 399 p[0] = (BYTE)val; 400 p[1] = (BYTE)(val>>8); 401 } 402} 403 404MEM_STATIC U32 MEM_readLE32(const void* memPtr) 405{ 406 if (MEM_isLittleEndian()) 407 return MEM_read32(memPtr); 408 else 409 return MEM_swap32(MEM_read32(memPtr)); 410} 411 412 413MEM_STATIC U64 MEM_readLE64(const void* memPtr) 414{ 415 if (MEM_isLittleEndian()) 416 return MEM_read64(memPtr); 417 else 418 return MEM_swap64(MEM_read64(memPtr)); 419} 420 421MEM_STATIC size_t MEM_readLEST(const void* memPtr) 422{ 423 if (MEM_32bits()) 424 return (size_t)MEM_readLE32(memPtr); 425 else 426 return (size_t)MEM_readLE64(memPtr); 427} 428 429 430 431#if defined (__cplusplus) 432} 433#endif 434 435#endif /* MEM_H_MODULE */ 436/* ****************************************************************** 437 bitstream 438 Part of FSE library 439 header file (to include) 440 Copyright (C) 2013-2016, Yann Collet. 441 442 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 443 444 Redistribution and use in source and binary forms, with or without 445 modification, are permitted provided that the following conditions are 446 met: 447 448 * Redistributions of source code must retain the above copyright 449 notice, this list of conditions and the following disclaimer. 450 * Redistributions in binary form must reproduce the above 451 copyright notice, this list of conditions and the following disclaimer 452 in the documentation and/or other materials provided with the 453 distribution. 454 455 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 456 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 457 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 458 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 459 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 460 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 461 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 462 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 463 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 464 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 465 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 466 467 You can contact the author at : 468 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 469****************************************************************** */ 470#ifndef BITSTREAM_H_MODULE 471#define BITSTREAM_H_MODULE 472 473#if defined (__cplusplus) 474extern "C" { 475#endif 476 477 478/* 479* This API consists of small unitary functions, which must be inlined for best performance. 480* Since link-time-optimization is not available for all compilers, 481* these functions are defined into a .h to be included. 482*/ 483 484 485/*========================================= 486* Target specific 487=========================================*/ 488#if defined(__BMI__) && defined(__GNUC__) 489# include <immintrin.h> /* support for bextr (experimental) */ 490#endif 491 492/*-******************************************** 493* bitStream decoding API (read backward) 494**********************************************/ 495typedef struct 496{ 497 size_t bitContainer; 498 unsigned bitsConsumed; 499 const char* ptr; 500 const char* start; 501} BITv07_DStream_t; 502 503typedef enum { BITv07_DStream_unfinished = 0, 504 BITv07_DStream_endOfBuffer = 1, 505 BITv07_DStream_completed = 2, 506 BITv07_DStream_overflow = 3 } BITv07_DStream_status; /* result of BITv07_reloadDStream() */ 507 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */ 508 509MEM_STATIC size_t BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize); 510MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, unsigned nbBits); 511MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD); 512MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* bitD); 513 514 515 516/*-**************************************** 517* unsafe API 518******************************************/ 519MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, unsigned nbBits); 520/* faster, but works only if nbBits >= 1 */ 521 522 523 524/*-************************************************************** 525* Internal functions 526****************************************************************/ 527MEM_STATIC unsigned BITv07_highbit32 (U32 val) 528{ 529# if defined(_MSC_VER) /* Visual */ 530 unsigned long r; 531 return _BitScanReverse(&r, val) ? (unsigned)r : 0; 532# elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */ 533 return __builtin_clz (val) ^ 31; 534# else /* Software version */ 535 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 }; 536 U32 v = val; 537 v |= v >> 1; 538 v |= v >> 2; 539 v |= v >> 4; 540 v |= v >> 8; 541 v |= v >> 16; 542 return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27]; 543# endif 544} 545 546 547 548/*-******************************************************** 549* bitStream decoding 550**********************************************************/ 551/*! BITv07_initDStream() : 552* Initialize a BITv07_DStream_t. 553* `bitD` : a pointer to an already allocated BITv07_DStream_t structure. 554* `srcSize` must be the *exact* size of the bitStream, in bytes. 555* @return : size of stream (== srcSize) or an errorCode if a problem is detected 556*/ 557MEM_STATIC size_t BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize) 558{ 559 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); } 560 561 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */ 562 bitD->start = (const char*)srcBuffer; 563 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer); 564 bitD->bitContainer = MEM_readLEST(bitD->ptr); 565 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1]; 566 bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0; 567 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ } 568 } else { 569 bitD->start = (const char*)srcBuffer; 570 bitD->ptr = bitD->start; 571 bitD->bitContainer = *(const BYTE*)(bitD->start); 572 switch(srcSize) 573 { 574 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);/* fall-through */ 575 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);/* fall-through */ 576 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);/* fall-through */ 577 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24; /* fall-through */ 578 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16; /* fall-through */ 579 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8; /* fall-through */ 580 default: break; 581 } 582 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1]; 583 bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0; 584 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ } 585 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8; 586 } 587 588 return srcSize; 589} 590 591 592 MEM_STATIC size_t BITv07_lookBits(const BITv07_DStream_t* bitD, U32 nbBits) 593{ 594 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1; 595 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask); 596} 597 598/*! BITv07_lookBitsFast() : 599* unsafe version; only works only if nbBits >= 1 */ 600MEM_STATIC size_t BITv07_lookBitsFast(const BITv07_DStream_t* bitD, U32 nbBits) 601{ 602 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1; 603 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask); 604} 605 606MEM_STATIC void BITv07_skipBits(BITv07_DStream_t* bitD, U32 nbBits) 607{ 608 bitD->bitsConsumed += nbBits; 609} 610 611MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, U32 nbBits) 612{ 613 size_t const value = BITv07_lookBits(bitD, nbBits); 614 BITv07_skipBits(bitD, nbBits); 615 return value; 616} 617 618/*! BITv07_readBitsFast() : 619* unsafe version; only works only if nbBits >= 1 */ 620MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, U32 nbBits) 621{ 622 size_t const value = BITv07_lookBitsFast(bitD, nbBits); 623 BITv07_skipBits(bitD, nbBits); 624 return value; 625} 626 627MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD) 628{ 629 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should not happen => corruption detected */ 630 return BITv07_DStream_overflow; 631 632 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) { 633 bitD->ptr -= bitD->bitsConsumed >> 3; 634 bitD->bitsConsumed &= 7; 635 bitD->bitContainer = MEM_readLEST(bitD->ptr); 636 return BITv07_DStream_unfinished; 637 } 638 if (bitD->ptr == bitD->start) { 639 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv07_DStream_endOfBuffer; 640 return BITv07_DStream_completed; 641 } 642 { U32 nbBytes = bitD->bitsConsumed >> 3; 643 BITv07_DStream_status result = BITv07_DStream_unfinished; 644 if (bitD->ptr - nbBytes < bitD->start) { 645 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */ 646 result = BITv07_DStream_endOfBuffer; 647 } 648 bitD->ptr -= nbBytes; 649 bitD->bitsConsumed -= nbBytes*8; 650 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */ 651 return result; 652 } 653} 654 655/*! BITv07_endOfDStream() : 656* @return Tells if DStream has exactly reached its end (all bits consumed). 657*/ 658MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* DStream) 659{ 660 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8)); 661} 662 663#if defined (__cplusplus) 664} 665#endif 666 667#endif /* BITSTREAM_H_MODULE */ 668/* ****************************************************************** 669 FSE : Finite State Entropy codec 670 Public Prototypes declaration 671 Copyright (C) 2013-2016, Yann Collet. 672 673 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 674 675 Redistribution and use in source and binary forms, with or without 676 modification, are permitted provided that the following conditions are 677 met: 678 679 * Redistributions of source code must retain the above copyright 680 notice, this list of conditions and the following disclaimer. 681 * Redistributions in binary form must reproduce the above 682 copyright notice, this list of conditions and the following disclaimer 683 in the documentation and/or other materials provided with the 684 distribution. 685 686 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 687 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 688 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 689 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 690 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 691 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 692 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 693 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 694 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 695 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 696 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 697 698 You can contact the author at : 699 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 700****************************************************************** */ 701#ifndef FSEv07_H 702#define FSEv07_H 703 704#if defined (__cplusplus) 705extern "C" { 706#endif 707 708 709 710/*-**************************************** 711* FSE simple functions 712******************************************/ 713 714/*! FSEv07_decompress(): 715 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize', 716 into already allocated destination buffer 'dst', of size 'dstCapacity'. 717 @return : size of regenerated data (<= maxDstSize), 718 or an error code, which can be tested using FSEv07_isError() . 719 720 ** Important ** : FSEv07_decompress() does not decompress non-compressible nor RLE data !!! 721 Why ? : making this distinction requires a header. 722 Header management is intentionally delegated to the user layer, which can better manage special cases. 723*/ 724size_t FSEv07_decompress(void* dst, size_t dstCapacity, 725 const void* cSrc, size_t cSrcSize); 726 727 728/* Error Management */ 729unsigned FSEv07_isError(size_t code); /* tells if a return value is an error code */ 730const char* FSEv07_getErrorName(size_t code); /* provides error code string (useful for debugging) */ 731 732 733/*-***************************************** 734* FSE detailed API 735******************************************/ 736/*! 737FSEv07_decompress() does the following: 7381. read normalized counters with readNCount() 7392. build decoding table 'DTable' from normalized counters 7403. decode the data stream using decoding table 'DTable' 741 742The following API allows targeting specific sub-functions for advanced tasks. 743For example, it's possible to compress several blocks using the same 'CTable', 744or to save and provide normalized distribution using external method. 745*/ 746 747 748/* *** DECOMPRESSION *** */ 749 750/*! FSEv07_readNCount(): 751 Read compactly saved 'normalizedCounter' from 'rBuffer'. 752 @return : size read from 'rBuffer', 753 or an errorCode, which can be tested using FSEv07_isError(). 754 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */ 755size_t FSEv07_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize); 756 757/*! Constructor and Destructor of FSEv07_DTable. 758 Note that its size depends on 'tableLog' */ 759typedef unsigned FSEv07_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */ 760FSEv07_DTable* FSEv07_createDTable(unsigned tableLog); 761void FSEv07_freeDTable(FSEv07_DTable* dt); 762 763/*! FSEv07_buildDTable(): 764 Builds 'dt', which must be already allocated, using FSEv07_createDTable(). 765 return : 0, or an errorCode, which can be tested using FSEv07_isError() */ 766size_t FSEv07_buildDTable (FSEv07_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog); 767 768/*! FSEv07_decompress_usingDTable(): 769 Decompress compressed source `cSrc` of size `cSrcSize` using `dt` 770 into `dst` which must be already allocated. 771 @return : size of regenerated data (necessarily <= `dstCapacity`), 772 or an errorCode, which can be tested using FSEv07_isError() */ 773size_t FSEv07_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv07_DTable* dt); 774 775/*! 776Tutorial : 777---------- 778(Note : these functions only decompress FSE-compressed blocks. 779 If block is uncompressed, use memcpy() instead 780 If block is a single repeated byte, use memset() instead ) 781 782The first step is to obtain the normalized frequencies of symbols. 783This can be performed by FSEv07_readNCount() if it was saved using FSEv07_writeNCount(). 784'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short. 785In practice, that means it's necessary to know 'maxSymbolValue' beforehand, 786or size the table to handle worst case situations (typically 256). 787FSEv07_readNCount() will provide 'tableLog' and 'maxSymbolValue'. 788The result of FSEv07_readNCount() is the number of bytes read from 'rBuffer'. 789Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that. 790If there is an error, the function will return an error code, which can be tested using FSEv07_isError(). 791 792The next step is to build the decompression tables 'FSEv07_DTable' from 'normalizedCounter'. 793This is performed by the function FSEv07_buildDTable(). 794The space required by 'FSEv07_DTable' must be already allocated using FSEv07_createDTable(). 795If there is an error, the function will return an error code, which can be tested using FSEv07_isError(). 796 797`FSEv07_DTable` can then be used to decompress `cSrc`, with FSEv07_decompress_usingDTable(). 798`cSrcSize` must be strictly correct, otherwise decompression will fail. 799FSEv07_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`). 800If there is an error, the function will return an error code, which can be tested using FSEv07_isError(). (ex: dst buffer too small) 801*/ 802 803 804#ifdef FSEv07_STATIC_LINKING_ONLY 805 806 807/* ***************************************** 808* Static allocation 809*******************************************/ 810/* FSE buffer bounds */ 811#define FSEv07_NCOUNTBOUND 512 812#define FSEv07_BLOCKBOUND(size) (size + (size>>7)) 813 814/* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */ 815#define FSEv07_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog)) 816 817 818/* ***************************************** 819* FSE advanced API 820*******************************************/ 821size_t FSEv07_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize); 822/**< same as FSEv07_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */ 823 824unsigned FSEv07_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus); 825/**< same as FSEv07_optimalTableLog(), which used `minus==2` */ 826 827size_t FSEv07_buildDTable_raw (FSEv07_DTable* dt, unsigned nbBits); 828/**< build a fake FSEv07_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */ 829 830size_t FSEv07_buildDTable_rle (FSEv07_DTable* dt, unsigned char symbolValue); 831/**< build a fake FSEv07_DTable, designed to always generate the same symbolValue */ 832 833 834 835/* ***************************************** 836* FSE symbol decompression API 837*******************************************/ 838typedef struct 839{ 840 size_t state; 841 const void* table; /* precise table may vary, depending on U16 */ 842} FSEv07_DState_t; 843 844 845static void FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt); 846 847static unsigned char FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD); 848 849 850 851/* ***************************************** 852* FSE unsafe API 853*******************************************/ 854static unsigned char FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD); 855/* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */ 856 857 858/* ====== Decompression ====== */ 859 860typedef struct { 861 U16 tableLog; 862 U16 fastMode; 863} FSEv07_DTableHeader; /* sizeof U32 */ 864 865typedef struct 866{ 867 unsigned short newState; 868 unsigned char symbol; 869 unsigned char nbBits; 870} FSEv07_decode_t; /* size == U32 */ 871 872MEM_STATIC void FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt) 873{ 874 const void* ptr = dt; 875 const FSEv07_DTableHeader* const DTableH = (const FSEv07_DTableHeader*)ptr; 876 DStatePtr->state = BITv07_readBits(bitD, DTableH->tableLog); 877 BITv07_reloadDStream(bitD); 878 DStatePtr->table = dt + 1; 879} 880 881MEM_STATIC BYTE FSEv07_peekSymbol(const FSEv07_DState_t* DStatePtr) 882{ 883 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state]; 884 return DInfo.symbol; 885} 886 887MEM_STATIC void FSEv07_updateState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD) 888{ 889 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state]; 890 U32 const nbBits = DInfo.nbBits; 891 size_t const lowBits = BITv07_readBits(bitD, nbBits); 892 DStatePtr->state = DInfo.newState + lowBits; 893} 894 895MEM_STATIC BYTE FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD) 896{ 897 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state]; 898 U32 const nbBits = DInfo.nbBits; 899 BYTE const symbol = DInfo.symbol; 900 size_t const lowBits = BITv07_readBits(bitD, nbBits); 901 902 DStatePtr->state = DInfo.newState + lowBits; 903 return symbol; 904} 905 906/*! FSEv07_decodeSymbolFast() : 907 unsafe, only works if no symbol has a probability > 50% */ 908MEM_STATIC BYTE FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD) 909{ 910 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state]; 911 U32 const nbBits = DInfo.nbBits; 912 BYTE const symbol = DInfo.symbol; 913 size_t const lowBits = BITv07_readBitsFast(bitD, nbBits); 914 915 DStatePtr->state = DInfo.newState + lowBits; 916 return symbol; 917} 918 919 920 921#ifndef FSEv07_COMMONDEFS_ONLY 922 923/* ************************************************************** 924* Tuning parameters 925****************************************************************/ 926/*!MEMORY_USAGE : 927* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) 928* Increasing memory usage improves compression ratio 929* Reduced memory usage can improve speed, due to cache effect 930* Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */ 931#define FSEv07_MAX_MEMORY_USAGE 14 932#define FSEv07_DEFAULT_MEMORY_USAGE 13 933 934/*!FSEv07_MAX_SYMBOL_VALUE : 935* Maximum symbol value authorized. 936* Required for proper stack allocation */ 937#define FSEv07_MAX_SYMBOL_VALUE 255 938 939 940/* ************************************************************** 941* template functions type & suffix 942****************************************************************/ 943#define FSEv07_FUNCTION_TYPE BYTE 944#define FSEv07_FUNCTION_EXTENSION 945#define FSEv07_DECODE_TYPE FSEv07_decode_t 946 947 948#endif /* !FSEv07_COMMONDEFS_ONLY */ 949 950 951/* *************************************************************** 952* Constants 953*****************************************************************/ 954#define FSEv07_MAX_TABLELOG (FSEv07_MAX_MEMORY_USAGE-2) 955#define FSEv07_MAX_TABLESIZE (1U<<FSEv07_MAX_TABLELOG) 956#define FSEv07_MAXTABLESIZE_MASK (FSEv07_MAX_TABLESIZE-1) 957#define FSEv07_DEFAULT_TABLELOG (FSEv07_DEFAULT_MEMORY_USAGE-2) 958#define FSEv07_MIN_TABLELOG 5 959 960#define FSEv07_TABLELOG_ABSOLUTE_MAX 15 961#if FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX 962# error "FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX is not supported" 963#endif 964 965#define FSEv07_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3) 966 967 968#endif /* FSEv07_STATIC_LINKING_ONLY */ 969 970 971#if defined (__cplusplus) 972} 973#endif 974 975#endif /* FSEv07_H */ 976/* ****************************************************************** 977 Huffman coder, part of New Generation Entropy library 978 header file 979 Copyright (C) 2013-2016, Yann Collet. 980 981 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 982 983 Redistribution and use in source and binary forms, with or without 984 modification, are permitted provided that the following conditions are 985 met: 986 987 * Redistributions of source code must retain the above copyright 988 notice, this list of conditions and the following disclaimer. 989 * Redistributions in binary form must reproduce the above 990 copyright notice, this list of conditions and the following disclaimer 991 in the documentation and/or other materials provided with the 992 distribution. 993 994 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 995 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 996 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 997 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 998 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 999 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1000 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1001 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1002 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1003 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1004 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1005 1006 You can contact the author at : 1007 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 1008****************************************************************** */ 1009#ifndef HUFv07_H_298734234 1010#define HUFv07_H_298734234 1011 1012#if defined (__cplusplus) 1013extern "C" { 1014#endif 1015 1016 1017 1018/* *** simple functions *** */ 1019/** 1020HUFv07_decompress() : 1021 Decompress HUF data from buffer 'cSrc', of size 'cSrcSize', 1022 into already allocated buffer 'dst', of minimum size 'dstSize'. 1023 `dstSize` : **must** be the ***exact*** size of original (uncompressed) data. 1024 Note : in contrast with FSE, HUFv07_decompress can regenerate 1025 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, 1026 because it knows size to regenerate. 1027 @return : size of regenerated data (== dstSize), 1028 or an error code, which can be tested using HUFv07_isError() 1029*/ 1030size_t HUFv07_decompress(void* dst, size_t dstSize, 1031 const void* cSrc, size_t cSrcSize); 1032 1033 1034/* **************************************** 1035* Tool functions 1036******************************************/ 1037#define HUFv07_BLOCKSIZE_MAX (128 * 1024) 1038 1039/* Error Management */ 1040unsigned HUFv07_isError(size_t code); /**< tells if a return value is an error code */ 1041const char* HUFv07_getErrorName(size_t code); /**< provides error code string (useful for debugging) */ 1042 1043 1044/* *** Advanced function *** */ 1045 1046 1047#ifdef HUFv07_STATIC_LINKING_ONLY 1048 1049 1050/* *** Constants *** */ 1051#define HUFv07_TABLELOG_ABSOLUTEMAX 16 /* absolute limit of HUFv07_MAX_TABLELOG. Beyond that value, code does not work */ 1052#define HUFv07_TABLELOG_MAX 12 /* max configured tableLog (for static allocation); can be modified up to HUFv07_ABSOLUTEMAX_TABLELOG */ 1053#define HUFv07_TABLELOG_DEFAULT 11 /* tableLog by default, when not specified */ 1054#define HUFv07_SYMBOLVALUE_MAX 255 1055#if (HUFv07_TABLELOG_MAX > HUFv07_TABLELOG_ABSOLUTEMAX) 1056# error "HUFv07_TABLELOG_MAX is too large !" 1057#endif 1058 1059 1060/* **************************************** 1061* Static allocation 1062******************************************/ 1063/* HUF buffer bounds */ 1064#define HUFv07_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */ 1065 1066/* static allocation of HUF's DTable */ 1067typedef U32 HUFv07_DTable; 1068#define HUFv07_DTABLE_SIZE(maxTableLog) (1 + (1<<(maxTableLog))) 1069#define HUFv07_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \ 1070 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE((maxTableLog)-1)] = { ((U32)((maxTableLog)-1)*0x1000001) } 1071#define HUFv07_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \ 1072 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog)*0x1000001) } 1073 1074 1075/* **************************************** 1076* Advanced decompression functions 1077******************************************/ 1078size_t HUFv07_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */ 1079size_t HUFv07_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */ 1080 1081size_t HUFv07_decompress4X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< decodes RLE and uncompressed */ 1082size_t HUFv07_decompress4X_hufOnly(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< considers RLE and uncompressed as errors */ 1083size_t HUFv07_decompress4X2_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */ 1084size_t HUFv07_decompress4X4_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */ 1085 1086size_t HUFv07_decompress1X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); 1087size_t HUFv07_decompress1X2_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */ 1088size_t HUFv07_decompress1X4_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */ 1089 1090 1091/* **************************************** 1092* HUF detailed API 1093******************************************/ 1094/*! 1095The following API allows targeting specific sub-functions for advanced tasks. 1096For example, it's possible to compress several blocks using the same 'CTable', 1097or to save and regenerate 'CTable' using external methods. 1098*/ 1099/* FSEv07_count() : find it within "fse.h" */ 1100 1101/*! HUFv07_readStats() : 1102 Read compact Huffman tree, saved by HUFv07_writeCTable(). 1103 `huffWeight` is destination buffer. 1104 @return : size read from `src` , or an error Code . 1105 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() . */ 1106size_t HUFv07_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats, 1107 U32* nbSymbolsPtr, U32* tableLogPtr, 1108 const void* src, size_t srcSize); 1109 1110 1111/* 1112HUFv07_decompress() does the following: 11131. select the decompression algorithm (X2, X4) based on pre-computed heuristics 11142. build Huffman table from save, using HUFv07_readDTableXn() 11153. decode 1 or 4 segments in parallel using HUFv07_decompressSXn_usingDTable 1116*/ 1117 1118/** HUFv07_selectDecoder() : 1119* Tells which decoder is likely to decode faster, 1120* based on a set of pre-determined metrics. 1121* @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 . 1122* Assumption : 0 < cSrcSize < dstSize <= 128 KB */ 1123U32 HUFv07_selectDecoder (size_t dstSize, size_t cSrcSize); 1124 1125size_t HUFv07_readDTableX2 (HUFv07_DTable* DTable, const void* src, size_t srcSize); 1126size_t HUFv07_readDTableX4 (HUFv07_DTable* DTable, const void* src, size_t srcSize); 1127 1128size_t HUFv07_decompress4X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable); 1129size_t HUFv07_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable); 1130size_t HUFv07_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable); 1131 1132 1133/* single stream variants */ 1134size_t HUFv07_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ 1135size_t HUFv07_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */ 1136 1137size_t HUFv07_decompress1X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable); 1138size_t HUFv07_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable); 1139size_t HUFv07_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable); 1140 1141 1142#endif /* HUFv07_STATIC_LINKING_ONLY */ 1143 1144 1145#if defined (__cplusplus) 1146} 1147#endif 1148 1149#endif /* HUFv07_H_298734234 */ 1150/* 1151 Common functions of New Generation Entropy library 1152 Copyright (C) 2016, Yann Collet. 1153 1154 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1155 1156 Redistribution and use in source and binary forms, with or without 1157 modification, are permitted provided that the following conditions are 1158 met: 1159 1160 * Redistributions of source code must retain the above copyright 1161 notice, this list of conditions and the following disclaimer. 1162 * Redistributions in binary form must reproduce the above 1163 copyright notice, this list of conditions and the following disclaimer 1164 in the documentation and/or other materials provided with the 1165 distribution. 1166 1167 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1168 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1169 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1170 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1171 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1172 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1173 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1174 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1175 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1176 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1177 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1178 1179 You can contact the author at : 1180 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy 1181 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1182*************************************************************************** */ 1183 1184 1185 1186/*-**************************************** 1187* FSE Error Management 1188******************************************/ 1189unsigned FSEv07_isError(size_t code) { return ERR_isError(code); } 1190 1191const char* FSEv07_getErrorName(size_t code) { return ERR_getErrorName(code); } 1192 1193 1194/* ************************************************************** 1195* HUF Error Management 1196****************************************************************/ 1197unsigned HUFv07_isError(size_t code) { return ERR_isError(code); } 1198 1199const char* HUFv07_getErrorName(size_t code) { return ERR_getErrorName(code); } 1200 1201 1202/*-************************************************************** 1203* FSE NCount encoding-decoding 1204****************************************************************/ 1205static short FSEv07_abs(short a) { return (short)(a<0 ? -a : a); } 1206 1207size_t FSEv07_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr, 1208 const void* headerBuffer, size_t hbSize) 1209{ 1210 const BYTE* const istart = (const BYTE*) headerBuffer; 1211 const BYTE* const iend = istart + hbSize; 1212 const BYTE* ip = istart; 1213 int nbBits; 1214 int remaining; 1215 int threshold; 1216 U32 bitStream; 1217 int bitCount; 1218 unsigned charnum = 0; 1219 int previous0 = 0; 1220 1221 if (hbSize < 4) return ERROR(srcSize_wrong); 1222 bitStream = MEM_readLE32(ip); 1223 nbBits = (bitStream & 0xF) + FSEv07_MIN_TABLELOG; /* extract tableLog */ 1224 if (nbBits > FSEv07_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge); 1225 bitStream >>= 4; 1226 bitCount = 4; 1227 *tableLogPtr = nbBits; 1228 remaining = (1<<nbBits)+1; 1229 threshold = 1<<nbBits; 1230 nbBits++; 1231 1232 while ((remaining>1) && (charnum<=*maxSVPtr)) { 1233 if (previous0) { 1234 unsigned n0 = charnum; 1235 while ((bitStream & 0xFFFF) == 0xFFFF) { 1236 n0+=24; 1237 if (ip < iend-5) { 1238 ip+=2; 1239 bitStream = MEM_readLE32(ip) >> bitCount; 1240 } else { 1241 bitStream >>= 16; 1242 bitCount+=16; 1243 } } 1244 while ((bitStream & 3) == 3) { 1245 n0+=3; 1246 bitStream>>=2; 1247 bitCount+=2; 1248 } 1249 n0 += bitStream & 3; 1250 bitCount += 2; 1251 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall); 1252 while (charnum < n0) normalizedCounter[charnum++] = 0; 1253 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { 1254 ip += bitCount>>3; 1255 bitCount &= 7; 1256 bitStream = MEM_readLE32(ip) >> bitCount; 1257 } 1258 else 1259 bitStream >>= 2; 1260 } 1261 { short const max = (short)((2*threshold-1)-remaining); 1262 short count; 1263 1264 if ((bitStream & (threshold-1)) < (U32)max) { 1265 count = (short)(bitStream & (threshold-1)); 1266 bitCount += nbBits-1; 1267 } else { 1268 count = (short)(bitStream & (2*threshold-1)); 1269 if (count >= threshold) count -= max; 1270 bitCount += nbBits; 1271 } 1272 1273 count--; /* extra accuracy */ 1274 remaining -= FSEv07_abs(count); 1275 normalizedCounter[charnum++] = count; 1276 previous0 = !count; 1277 while (remaining < threshold) { 1278 nbBits--; 1279 threshold >>= 1; 1280 } 1281 1282 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { 1283 ip += bitCount>>3; 1284 bitCount &= 7; 1285 } else { 1286 bitCount -= (int)(8 * (iend - 4 - ip)); 1287 ip = iend - 4; 1288 } 1289 bitStream = MEM_readLE32(ip) >> (bitCount & 31); 1290 } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */ 1291 if (remaining != 1) return ERROR(GENERIC); 1292 *maxSVPtr = charnum-1; 1293 1294 ip += (bitCount+7)>>3; 1295 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong); 1296 return ip-istart; 1297} 1298 1299 1300/*! HUFv07_readStats() : 1301 Read compact Huffman tree, saved by HUFv07_writeCTable(). 1302 `huffWeight` is destination buffer. 1303 @return : size read from `src` , or an error Code . 1304 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() . 1305*/ 1306size_t HUFv07_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats, 1307 U32* nbSymbolsPtr, U32* tableLogPtr, 1308 const void* src, size_t srcSize) 1309{ 1310 U32 weightTotal; 1311 const BYTE* ip = (const BYTE*) src; 1312 size_t iSize; 1313 size_t oSize; 1314 1315 if (!srcSize) return ERROR(srcSize_wrong); 1316 iSize = ip[0]; 1317 /* memset(huffWeight, 0, hwSize); */ /* is not necessary, even though some analyzer complain ... */ 1318 1319 if (iSize >= 128) { /* special header */ 1320 if (iSize >= (242)) { /* RLE */ 1321 static U32 l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 }; 1322 oSize = l[iSize-242]; 1323 memset(huffWeight, 1, hwSize); 1324 iSize = 0; 1325 } 1326 else { /* Incompressible */ 1327 oSize = iSize - 127; 1328 iSize = ((oSize+1)/2); 1329 if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 1330 if (oSize >= hwSize) return ERROR(corruption_detected); 1331 ip += 1; 1332 { U32 n; 1333 for (n=0; n<oSize; n+=2) { 1334 huffWeight[n] = ip[n/2] >> 4; 1335 huffWeight[n+1] = ip[n/2] & 15; 1336 } } } } 1337 else { /* header compressed with FSE (normal case) */ 1338 if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 1339 oSize = FSEv07_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */ 1340 if (FSEv07_isError(oSize)) return oSize; 1341 } 1342 1343 /* collect weight stats */ 1344 memset(rankStats, 0, (HUFv07_TABLELOG_ABSOLUTEMAX + 1) * sizeof(U32)); 1345 weightTotal = 0; 1346 { U32 n; for (n=0; n<oSize; n++) { 1347 if (huffWeight[n] >= HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected); 1348 rankStats[huffWeight[n]]++; 1349 weightTotal += (1 << huffWeight[n]) >> 1; 1350 } } 1351 if (weightTotal == 0) return ERROR(corruption_detected); 1352 1353 /* get last non-null symbol weight (implied, total must be 2^n) */ 1354 { U32 const tableLog = BITv07_highbit32(weightTotal) + 1; 1355 if (tableLog > HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected); 1356 *tableLogPtr = tableLog; 1357 /* determine last weight */ 1358 { U32 const total = 1 << tableLog; 1359 U32 const rest = total - weightTotal; 1360 U32 const verif = 1 << BITv07_highbit32(rest); 1361 U32 const lastWeight = BITv07_highbit32(rest) + 1; 1362 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */ 1363 huffWeight[oSize] = (BYTE)lastWeight; 1364 rankStats[lastWeight]++; 1365 } } 1366 1367 /* check tree construction validity */ 1368 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */ 1369 1370 /* results */ 1371 *nbSymbolsPtr = (U32)(oSize+1); 1372 return iSize+1; 1373} 1374/* ****************************************************************** 1375 FSE : Finite State Entropy decoder 1376 Copyright (C) 2013-2015, Yann Collet. 1377 1378 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1379 1380 Redistribution and use in source and binary forms, with or without 1381 modification, are permitted provided that the following conditions are 1382 met: 1383 1384 * Redistributions of source code must retain the above copyright 1385 notice, this list of conditions and the following disclaimer. 1386 * Redistributions in binary form must reproduce the above 1387 copyright notice, this list of conditions and the following disclaimer 1388 in the documentation and/or other materials provided with the 1389 distribution. 1390 1391 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1392 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1393 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1394 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1395 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1396 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1397 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1398 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1399 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1400 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1401 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1402 1403 You can contact the author at : 1404 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy 1405 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1406****************************************************************** */ 1407 1408 1409/* ************************************************************** 1410* Compiler specifics 1411****************************************************************/ 1412#ifdef _MSC_VER /* Visual Studio */ 1413# define FORCE_INLINE static __forceinline 1414# include <intrin.h> /* For Visual 2005 */ 1415# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 1416# pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */ 1417#else 1418# if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 1419# ifdef __GNUC__ 1420# define FORCE_INLINE static inline __attribute__((always_inline)) 1421# else 1422# define FORCE_INLINE static inline 1423# endif 1424# else 1425# define FORCE_INLINE static 1426# endif /* __STDC_VERSION__ */ 1427#endif 1428 1429 1430/* ************************************************************** 1431* Error Management 1432****************************************************************/ 1433#define FSEv07_isError ERR_isError 1434#define FSEv07_STATIC_ASSERT(c) { enum { FSEv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 1435 1436 1437/* ************************************************************** 1438* Complex types 1439****************************************************************/ 1440typedef U32 DTable_max_t[FSEv07_DTABLE_SIZE_U32(FSEv07_MAX_TABLELOG)]; 1441 1442 1443/* ************************************************************** 1444* Templates 1445****************************************************************/ 1446/* 1447 designed to be included 1448 for type-specific functions (template emulation in C) 1449 Objective is to write these functions only once, for improved maintenance 1450*/ 1451 1452/* safety checks */ 1453#ifndef FSEv07_FUNCTION_EXTENSION 1454# error "FSEv07_FUNCTION_EXTENSION must be defined" 1455#endif 1456#ifndef FSEv07_FUNCTION_TYPE 1457# error "FSEv07_FUNCTION_TYPE must be defined" 1458#endif 1459 1460/* Function names */ 1461#define FSEv07_CAT(X,Y) X##Y 1462#define FSEv07_FUNCTION_NAME(X,Y) FSEv07_CAT(X,Y) 1463#define FSEv07_TYPE_NAME(X,Y) FSEv07_CAT(X,Y) 1464 1465 1466/* Function templates */ 1467FSEv07_DTable* FSEv07_createDTable (unsigned tableLog) 1468{ 1469 if (tableLog > FSEv07_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv07_TABLELOG_ABSOLUTE_MAX; 1470 return (FSEv07_DTable*)malloc( FSEv07_DTABLE_SIZE_U32(tableLog) * sizeof (U32) ); 1471} 1472 1473void FSEv07_freeDTable (FSEv07_DTable* dt) 1474{ 1475 free(dt); 1476} 1477 1478size_t FSEv07_buildDTable(FSEv07_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) 1479{ 1480 void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */ 1481 FSEv07_DECODE_TYPE* const tableDecode = (FSEv07_DECODE_TYPE*) (tdPtr); 1482 U16 symbolNext[FSEv07_MAX_SYMBOL_VALUE+1]; 1483 1484 U32 const maxSV1 = maxSymbolValue + 1; 1485 U32 const tableSize = 1 << tableLog; 1486 U32 highThreshold = tableSize-1; 1487 1488 /* Sanity Checks */ 1489 if (maxSymbolValue > FSEv07_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge); 1490 if (tableLog > FSEv07_MAX_TABLELOG) return ERROR(tableLog_tooLarge); 1491 1492 /* Init, lay down lowprob symbols */ 1493 { FSEv07_DTableHeader DTableH; 1494 DTableH.tableLog = (U16)tableLog; 1495 DTableH.fastMode = 1; 1496 { S16 const largeLimit= (S16)(1 << (tableLog-1)); 1497 U32 s; 1498 for (s=0; s<maxSV1; s++) { 1499 if (normalizedCounter[s]==-1) { 1500 tableDecode[highThreshold--].symbol = (FSEv07_FUNCTION_TYPE)s; 1501 symbolNext[s] = 1; 1502 } else { 1503 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0; 1504 symbolNext[s] = normalizedCounter[s]; 1505 } } } 1506 memcpy(dt, &DTableH, sizeof(DTableH)); 1507 } 1508 1509 /* Spread symbols */ 1510 { U32 const tableMask = tableSize-1; 1511 U32 const step = FSEv07_TABLESTEP(tableSize); 1512 U32 s, position = 0; 1513 for (s=0; s<maxSV1; s++) { 1514 int i; 1515 for (i=0; i<normalizedCounter[s]; i++) { 1516 tableDecode[position].symbol = (FSEv07_FUNCTION_TYPE)s; 1517 position = (position + step) & tableMask; 1518 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */ 1519 } } 1520 1521 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ 1522 } 1523 1524 /* Build Decoding table */ 1525 { U32 u; 1526 for (u=0; u<tableSize; u++) { 1527 FSEv07_FUNCTION_TYPE const symbol = (FSEv07_FUNCTION_TYPE)(tableDecode[u].symbol); 1528 U16 nextState = symbolNext[symbol]++; 1529 tableDecode[u].nbBits = (BYTE) (tableLog - BITv07_highbit32 ((U32)nextState) ); 1530 tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize); 1531 } } 1532 1533 return 0; 1534} 1535 1536 1537 1538#ifndef FSEv07_COMMONDEFS_ONLY 1539 1540/*-******************************************************* 1541* Decompression (Byte symbols) 1542*********************************************************/ 1543size_t FSEv07_buildDTable_rle (FSEv07_DTable* dt, BYTE symbolValue) 1544{ 1545 void* ptr = dt; 1546 FSEv07_DTableHeader* const DTableH = (FSEv07_DTableHeader*)ptr; 1547 void* dPtr = dt + 1; 1548 FSEv07_decode_t* const cell = (FSEv07_decode_t*)dPtr; 1549 1550 DTableH->tableLog = 0; 1551 DTableH->fastMode = 0; 1552 1553 cell->newState = 0; 1554 cell->symbol = symbolValue; 1555 cell->nbBits = 0; 1556 1557 return 0; 1558} 1559 1560 1561size_t FSEv07_buildDTable_raw (FSEv07_DTable* dt, unsigned nbBits) 1562{ 1563 void* ptr = dt; 1564 FSEv07_DTableHeader* const DTableH = (FSEv07_DTableHeader*)ptr; 1565 void* dPtr = dt + 1; 1566 FSEv07_decode_t* const dinfo = (FSEv07_decode_t*)dPtr; 1567 const unsigned tableSize = 1 << nbBits; 1568 const unsigned tableMask = tableSize - 1; 1569 const unsigned maxSV1 = tableMask+1; 1570 unsigned s; 1571 1572 /* Sanity checks */ 1573 if (nbBits < 1) return ERROR(GENERIC); /* min size */ 1574 1575 /* Build Decoding Table */ 1576 DTableH->tableLog = (U16)nbBits; 1577 DTableH->fastMode = 1; 1578 for (s=0; s<maxSV1; s++) { 1579 dinfo[s].newState = 0; 1580 dinfo[s].symbol = (BYTE)s; 1581 dinfo[s].nbBits = (BYTE)nbBits; 1582 } 1583 1584 return 0; 1585} 1586 1587FORCE_INLINE size_t FSEv07_decompress_usingDTable_generic( 1588 void* dst, size_t maxDstSize, 1589 const void* cSrc, size_t cSrcSize, 1590 const FSEv07_DTable* dt, const unsigned fast) 1591{ 1592 BYTE* const ostart = (BYTE*) dst; 1593 BYTE* op = ostart; 1594 BYTE* const omax = op + maxDstSize; 1595 BYTE* const olimit = omax-3; 1596 1597 BITv07_DStream_t bitD; 1598 FSEv07_DState_t state1; 1599 FSEv07_DState_t state2; 1600 1601 /* Init */ 1602 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */ 1603 if (FSEv07_isError(errorCode)) return errorCode; } 1604 1605 FSEv07_initDState(&state1, &bitD, dt); 1606 FSEv07_initDState(&state2, &bitD, dt); 1607 1608#define FSEv07_GETSYMBOL(statePtr) fast ? FSEv07_decodeSymbolFast(statePtr, &bitD) : FSEv07_decodeSymbol(statePtr, &bitD) 1609 1610 /* 4 symbols per loop */ 1611 for ( ; (BITv07_reloadDStream(&bitD)==BITv07_DStream_unfinished) && (op<olimit) ; op+=4) { 1612 op[0] = FSEv07_GETSYMBOL(&state1); 1613 1614 if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1615 BITv07_reloadDStream(&bitD); 1616 1617 op[1] = FSEv07_GETSYMBOL(&state2); 1618 1619 if (FSEv07_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1620 { if (BITv07_reloadDStream(&bitD) > BITv07_DStream_unfinished) { op+=2; break; } } 1621 1622 op[2] = FSEv07_GETSYMBOL(&state1); 1623 1624 if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1625 BITv07_reloadDStream(&bitD); 1626 1627 op[3] = FSEv07_GETSYMBOL(&state2); 1628 } 1629 1630 /* tail */ 1631 /* note : BITv07_reloadDStream(&bitD) >= FSEv07_DStream_partiallyFilled; Ends at exactly BITv07_DStream_completed */ 1632 while (1) { 1633 if (op>(omax-2)) return ERROR(dstSize_tooSmall); 1634 1635 *op++ = FSEv07_GETSYMBOL(&state1); 1636 1637 if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) { 1638 *op++ = FSEv07_GETSYMBOL(&state2); 1639 break; 1640 } 1641 1642 if (op>(omax-2)) return ERROR(dstSize_tooSmall); 1643 1644 *op++ = FSEv07_GETSYMBOL(&state2); 1645 1646 if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) { 1647 *op++ = FSEv07_GETSYMBOL(&state1); 1648 break; 1649 } } 1650 1651 return op-ostart; 1652} 1653 1654 1655size_t FSEv07_decompress_usingDTable(void* dst, size_t originalSize, 1656 const void* cSrc, size_t cSrcSize, 1657 const FSEv07_DTable* dt) 1658{ 1659 const void* ptr = dt; 1660 const FSEv07_DTableHeader* DTableH = (const FSEv07_DTableHeader*)ptr; 1661 const U32 fastMode = DTableH->fastMode; 1662 1663 /* select fast mode (static) */ 1664 if (fastMode) return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1); 1665 return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0); 1666} 1667 1668 1669size_t FSEv07_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize) 1670{ 1671 const BYTE* const istart = (const BYTE*)cSrc; 1672 const BYTE* ip = istart; 1673 short counting[FSEv07_MAX_SYMBOL_VALUE+1]; 1674 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */ 1675 unsigned tableLog; 1676 unsigned maxSymbolValue = FSEv07_MAX_SYMBOL_VALUE; 1677 1678 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */ 1679 1680 /* normal FSE decoding mode */ 1681 { size_t const NCountLength = FSEv07_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize); 1682 if (FSEv07_isError(NCountLength)) return NCountLength; 1683 if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */ 1684 ip += NCountLength; 1685 cSrcSize -= NCountLength; 1686 } 1687 1688 { size_t const errorCode = FSEv07_buildDTable (dt, counting, maxSymbolValue, tableLog); 1689 if (FSEv07_isError(errorCode)) return errorCode; } 1690 1691 return FSEv07_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); /* always return, even if it is an error code */ 1692} 1693 1694 1695 1696#endif /* FSEv07_COMMONDEFS_ONLY */ 1697 1698/* ****************************************************************** 1699 Huffman decoder, part of New Generation Entropy library 1700 Copyright (C) 2013-2016, Yann Collet. 1701 1702 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1703 1704 Redistribution and use in source and binary forms, with or without 1705 modification, are permitted provided that the following conditions are 1706 met: 1707 1708 * Redistributions of source code must retain the above copyright 1709 notice, this list of conditions and the following disclaimer. 1710 * Redistributions in binary form must reproduce the above 1711 copyright notice, this list of conditions and the following disclaimer 1712 in the documentation and/or other materials provided with the 1713 distribution. 1714 1715 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1716 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1717 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1718 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1719 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1720 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1721 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1722 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1723 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1724 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1725 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1726 1727 You can contact the author at : 1728 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy 1729 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1730****************************************************************** */ 1731 1732/* ************************************************************** 1733* Compiler specifics 1734****************************************************************/ 1735#if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 1736/* inline is defined */ 1737#elif defined(_MSC_VER) 1738# define inline __inline 1739#else 1740# define inline /* disable inline */ 1741#endif 1742 1743 1744#ifdef _MSC_VER /* Visual Studio */ 1745# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 1746#endif 1747 1748 1749 1750/* ************************************************************** 1751* Error Management 1752****************************************************************/ 1753#define HUFv07_STATIC_ASSERT(c) { enum { HUFv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 1754 1755 1756/*-***************************/ 1757/* generic DTableDesc */ 1758/*-***************************/ 1759 1760typedef struct { BYTE maxTableLog; BYTE tableType; BYTE tableLog; BYTE reserved; } DTableDesc; 1761 1762static DTableDesc HUFv07_getDTableDesc(const HUFv07_DTable* table) 1763{ 1764 DTableDesc dtd; 1765 memcpy(&dtd, table, sizeof(dtd)); 1766 return dtd; 1767} 1768 1769 1770/*-***************************/ 1771/* single-symbol decoding */ 1772/*-***************************/ 1773 1774typedef struct { BYTE byte; BYTE nbBits; } HUFv07_DEltX2; /* single-symbol decoding */ 1775 1776size_t HUFv07_readDTableX2 (HUFv07_DTable* DTable, const void* src, size_t srcSize) 1777{ 1778 BYTE huffWeight[HUFv07_SYMBOLVALUE_MAX + 1]; 1779 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1]; /* large enough for values from 0 to 16 */ 1780 U32 tableLog = 0; 1781 U32 nbSymbols = 0; 1782 size_t iSize; 1783 void* const dtPtr = DTable + 1; 1784 HUFv07_DEltX2* const dt = (HUFv07_DEltX2*)dtPtr; 1785 1786 HUFv07_STATIC_ASSERT(sizeof(DTableDesc) == sizeof(HUFv07_DTable)); 1787 /* memset(huffWeight, 0, sizeof(huffWeight)); */ /* is not necessary, even though some analyzer complain ... */ 1788 1789 iSize = HUFv07_readStats(huffWeight, HUFv07_SYMBOLVALUE_MAX + 1, rankVal, &nbSymbols, &tableLog, src, srcSize); 1790 if (HUFv07_isError(iSize)) return iSize; 1791 1792 /* Table header */ 1793 { DTableDesc dtd = HUFv07_getDTableDesc(DTable); 1794 if (tableLog > (U32)(dtd.maxTableLog+1)) return ERROR(tableLog_tooLarge); /* DTable too small, huffman tree cannot fit in */ 1795 dtd.tableType = 0; 1796 dtd.tableLog = (BYTE)tableLog; 1797 memcpy(DTable, &dtd, sizeof(dtd)); 1798 } 1799 1800 /* Prepare ranks */ 1801 { U32 n, nextRankStart = 0; 1802 for (n=1; n<tableLog+1; n++) { 1803 U32 current = nextRankStart; 1804 nextRankStart += (rankVal[n] << (n-1)); 1805 rankVal[n] = current; 1806 } } 1807 1808 /* fill DTable */ 1809 { U32 n; 1810 for (n=0; n<nbSymbols; n++) { 1811 U32 const w = huffWeight[n]; 1812 U32 const length = (1 << w) >> 1; 1813 U32 i; 1814 HUFv07_DEltX2 D; 1815 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w); 1816 for (i = rankVal[w]; i < rankVal[w] + length; i++) 1817 dt[i] = D; 1818 rankVal[w] += length; 1819 } } 1820 1821 return iSize; 1822} 1823 1824 1825static BYTE HUFv07_decodeSymbolX2(BITv07_DStream_t* Dstream, const HUFv07_DEltX2* dt, const U32 dtLog) 1826{ 1827 size_t const val = BITv07_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */ 1828 BYTE const c = dt[val].byte; 1829 BITv07_skipBits(Dstream, dt[val].nbBits); 1830 return c; 1831} 1832 1833#define HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \ 1834 *ptr++ = HUFv07_decodeSymbolX2(DStreamPtr, dt, dtLog) 1835 1836#define HUFv07_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \ 1837 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \ 1838 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 1839 1840#define HUFv07_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \ 1841 if (MEM_64bits()) \ 1842 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 1843 1844static inline size_t HUFv07_decodeStreamX2(BYTE* p, BITv07_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv07_DEltX2* const dt, const U32 dtLog) 1845{ 1846 BYTE* const pStart = p; 1847 1848 /* up to 4 symbols at a time */ 1849 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p <= pEnd-4)) { 1850 HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr); 1851 HUFv07_DECODE_SYMBOLX2_1(p, bitDPtr); 1852 HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr); 1853 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr); 1854 } 1855 1856 /* closer to the end */ 1857 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p < pEnd)) 1858 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr); 1859 1860 /* no more data to retrieve from bitstream, hence no need to reload */ 1861 while (p < pEnd) 1862 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr); 1863 1864 return pEnd-pStart; 1865} 1866 1867static size_t HUFv07_decompress1X2_usingDTable_internal( 1868 void* dst, size_t dstSize, 1869 const void* cSrc, size_t cSrcSize, 1870 const HUFv07_DTable* DTable) 1871{ 1872 BYTE* op = (BYTE*)dst; 1873 BYTE* const oend = op + dstSize; 1874 const void* dtPtr = DTable + 1; 1875 const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr; 1876 BITv07_DStream_t bitD; 1877 DTableDesc const dtd = HUFv07_getDTableDesc(DTable); 1878 U32 const dtLog = dtd.tableLog; 1879 1880 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize); 1881 if (HUFv07_isError(errorCode)) return errorCode; } 1882 1883 HUFv07_decodeStreamX2(op, &bitD, oend, dt, dtLog); 1884 1885 /* check */ 1886 if (!BITv07_endOfDStream(&bitD)) return ERROR(corruption_detected); 1887 1888 return dstSize; 1889} 1890 1891size_t HUFv07_decompress1X2_usingDTable( 1892 void* dst, size_t dstSize, 1893 const void* cSrc, size_t cSrcSize, 1894 const HUFv07_DTable* DTable) 1895{ 1896 DTableDesc dtd = HUFv07_getDTableDesc(DTable); 1897 if (dtd.tableType != 0) return ERROR(GENERIC); 1898 return HUFv07_decompress1X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable); 1899} 1900 1901size_t HUFv07_decompress1X2_DCtx (HUFv07_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 1902{ 1903 const BYTE* ip = (const BYTE*) cSrc; 1904 1905 size_t const hSize = HUFv07_readDTableX2 (DCtx, cSrc, cSrcSize); 1906 if (HUFv07_isError(hSize)) return hSize; 1907 if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 1908 ip += hSize; cSrcSize -= hSize; 1909 1910 return HUFv07_decompress1X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx); 1911} 1912 1913size_t HUFv07_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 1914{ 1915 HUFv07_CREATE_STATIC_DTABLEX2(DTable, HUFv07_TABLELOG_MAX); 1916 return HUFv07_decompress1X2_DCtx (DTable, dst, dstSize, cSrc, cSrcSize); 1917} 1918 1919 1920static size_t HUFv07_decompress4X2_usingDTable_internal( 1921 void* dst, size_t dstSize, 1922 const void* cSrc, size_t cSrcSize, 1923 const HUFv07_DTable* DTable) 1924{ 1925 /* Check */ 1926 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 1927 1928 { const BYTE* const istart = (const BYTE*) cSrc; 1929 BYTE* const ostart = (BYTE*) dst; 1930 BYTE* const oend = ostart + dstSize; 1931 const void* const dtPtr = DTable + 1; 1932 const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr; 1933 1934 /* Init */ 1935 BITv07_DStream_t bitD1; 1936 BITv07_DStream_t bitD2; 1937 BITv07_DStream_t bitD3; 1938 BITv07_DStream_t bitD4; 1939 size_t const length1 = MEM_readLE16(istart); 1940 size_t const length2 = MEM_readLE16(istart+2); 1941 size_t const length3 = MEM_readLE16(istart+4); 1942 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6); 1943 const BYTE* const istart1 = istart + 6; /* jumpTable */ 1944 const BYTE* const istart2 = istart1 + length1; 1945 const BYTE* const istart3 = istart2 + length2; 1946 const BYTE* const istart4 = istart3 + length3; 1947 const size_t segmentSize = (dstSize+3) / 4; 1948 BYTE* const opStart2 = ostart + segmentSize; 1949 BYTE* const opStart3 = opStart2 + segmentSize; 1950 BYTE* const opStart4 = opStart3 + segmentSize; 1951 BYTE* op1 = ostart; 1952 BYTE* op2 = opStart2; 1953 BYTE* op3 = opStart3; 1954 BYTE* op4 = opStart4; 1955 U32 endSignal; 1956 DTableDesc const dtd = HUFv07_getDTableDesc(DTable); 1957 U32 const dtLog = dtd.tableLog; 1958 1959 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 1960 { size_t const errorCode = BITv07_initDStream(&bitD1, istart1, length1); 1961 if (HUFv07_isError(errorCode)) return errorCode; } 1962 { size_t const errorCode = BITv07_initDStream(&bitD2, istart2, length2); 1963 if (HUFv07_isError(errorCode)) return errorCode; } 1964 { size_t const errorCode = BITv07_initDStream(&bitD3, istart3, length3); 1965 if (HUFv07_isError(errorCode)) return errorCode; } 1966 { size_t const errorCode = BITv07_initDStream(&bitD4, istart4, length4); 1967 if (HUFv07_isError(errorCode)) return errorCode; } 1968 1969 /* 16-32 symbols per loop (4-8 symbols per stream) */ 1970 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4); 1971 for ( ; (endSignal==BITv07_DStream_unfinished) && (op4<(oend-7)) ; ) { 1972 HUFv07_DECODE_SYMBOLX2_2(op1, &bitD1); 1973 HUFv07_DECODE_SYMBOLX2_2(op2, &bitD2); 1974 HUFv07_DECODE_SYMBOLX2_2(op3, &bitD3); 1975 HUFv07_DECODE_SYMBOLX2_2(op4, &bitD4); 1976 HUFv07_DECODE_SYMBOLX2_1(op1, &bitD1); 1977 HUFv07_DECODE_SYMBOLX2_1(op2, &bitD2); 1978 HUFv07_DECODE_SYMBOLX2_1(op3, &bitD3); 1979 HUFv07_DECODE_SYMBOLX2_1(op4, &bitD4); 1980 HUFv07_DECODE_SYMBOLX2_2(op1, &bitD1); 1981 HUFv07_DECODE_SYMBOLX2_2(op2, &bitD2); 1982 HUFv07_DECODE_SYMBOLX2_2(op3, &bitD3); 1983 HUFv07_DECODE_SYMBOLX2_2(op4, &bitD4); 1984 HUFv07_DECODE_SYMBOLX2_0(op1, &bitD1); 1985 HUFv07_DECODE_SYMBOLX2_0(op2, &bitD2); 1986 HUFv07_DECODE_SYMBOLX2_0(op3, &bitD3); 1987 HUFv07_DECODE_SYMBOLX2_0(op4, &bitD4); 1988 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4); 1989 } 1990 1991 /* check corruption */ 1992 if (op1 > opStart2) return ERROR(corruption_detected); 1993 if (op2 > opStart3) return ERROR(corruption_detected); 1994 if (op3 > opStart4) return ERROR(corruption_detected); 1995 /* note : op4 supposed already verified within main loop */ 1996 1997 /* finish bitStreams one by one */ 1998 HUFv07_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog); 1999 HUFv07_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog); 2000 HUFv07_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog); 2001 HUFv07_decodeStreamX2(op4, &bitD4, oend, dt, dtLog); 2002 2003 /* check */ 2004 endSignal = BITv07_endOfDStream(&bitD1) & BITv07_endOfDStream(&bitD2) & BITv07_endOfDStream(&bitD3) & BITv07_endOfDStream(&bitD4); 2005 if (!endSignal) return ERROR(corruption_detected); 2006 2007 /* decoded size */ 2008 return dstSize; 2009 } 2010} 2011 2012 2013size_t HUFv07_decompress4X2_usingDTable( 2014 void* dst, size_t dstSize, 2015 const void* cSrc, size_t cSrcSize, 2016 const HUFv07_DTable* DTable) 2017{ 2018 DTableDesc dtd = HUFv07_getDTableDesc(DTable); 2019 if (dtd.tableType != 0) return ERROR(GENERIC); 2020 return HUFv07_decompress4X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable); 2021} 2022 2023 2024size_t HUFv07_decompress4X2_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2025{ 2026 const BYTE* ip = (const BYTE*) cSrc; 2027 2028 size_t const hSize = HUFv07_readDTableX2 (dctx, cSrc, cSrcSize); 2029 if (HUFv07_isError(hSize)) return hSize; 2030 if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 2031 ip += hSize; cSrcSize -= hSize; 2032 2033 return HUFv07_decompress4X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, dctx); 2034} 2035 2036size_t HUFv07_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2037{ 2038 HUFv07_CREATE_STATIC_DTABLEX2(DTable, HUFv07_TABLELOG_MAX); 2039 return HUFv07_decompress4X2_DCtx(DTable, dst, dstSize, cSrc, cSrcSize); 2040} 2041 2042 2043/* *************************/ 2044/* double-symbols decoding */ 2045/* *************************/ 2046typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv07_DEltX4; /* double-symbols decoding */ 2047 2048typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t; 2049 2050static void HUFv07_fillDTableX4Level2(HUFv07_DEltX4* DTable, U32 sizeLog, const U32 consumed, 2051 const U32* rankValOrigin, const int minWeight, 2052 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize, 2053 U32 nbBitsBaseline, U16 baseSeq) 2054{ 2055 HUFv07_DEltX4 DElt; 2056 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1]; 2057 2058 /* get pre-calculated rankVal */ 2059 memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 2060 2061 /* fill skipped values */ 2062 if (minWeight>1) { 2063 U32 i, skipSize = rankVal[minWeight]; 2064 MEM_writeLE16(&(DElt.sequence), baseSeq); 2065 DElt.nbBits = (BYTE)(consumed); 2066 DElt.length = 1; 2067 for (i = 0; i < skipSize; i++) 2068 DTable[i] = DElt; 2069 } 2070 2071 /* fill DTable */ 2072 { U32 s; for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */ 2073 const U32 symbol = sortedSymbols[s].symbol; 2074 const U32 weight = sortedSymbols[s].weight; 2075 const U32 nbBits = nbBitsBaseline - weight; 2076 const U32 length = 1 << (sizeLog-nbBits); 2077 const U32 start = rankVal[weight]; 2078 U32 i = start; 2079 const U32 end = start + length; 2080 2081 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8))); 2082 DElt.nbBits = (BYTE)(nbBits + consumed); 2083 DElt.length = 2; 2084 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */ 2085 2086 rankVal[weight] += length; 2087 }} 2088} 2089 2090typedef U32 rankVal_t[HUFv07_TABLELOG_ABSOLUTEMAX][HUFv07_TABLELOG_ABSOLUTEMAX + 1]; 2091 2092static void HUFv07_fillDTableX4(HUFv07_DEltX4* DTable, const U32 targetLog, 2093 const sortedSymbol_t* sortedList, const U32 sortedListSize, 2094 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight, 2095 const U32 nbBitsBaseline) 2096{ 2097 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1]; 2098 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */ 2099 const U32 minBits = nbBitsBaseline - maxWeight; 2100 U32 s; 2101 2102 memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 2103 2104 /* fill DTable */ 2105 for (s=0; s<sortedListSize; s++) { 2106 const U16 symbol = sortedList[s].symbol; 2107 const U32 weight = sortedList[s].weight; 2108 const U32 nbBits = nbBitsBaseline - weight; 2109 const U32 start = rankVal[weight]; 2110 const U32 length = 1 << (targetLog-nbBits); 2111 2112 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */ 2113 U32 sortedRank; 2114 int minWeight = nbBits + scaleLog; 2115 if (minWeight < 1) minWeight = 1; 2116 sortedRank = rankStart[minWeight]; 2117 HUFv07_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits, 2118 rankValOrigin[nbBits], minWeight, 2119 sortedList+sortedRank, sortedListSize-sortedRank, 2120 nbBitsBaseline, symbol); 2121 } else { 2122 HUFv07_DEltX4 DElt; 2123 MEM_writeLE16(&(DElt.sequence), symbol); 2124 DElt.nbBits = (BYTE)(nbBits); 2125 DElt.length = 1; 2126 { U32 u; 2127 const U32 end = start + length; 2128 for (u = start; u < end; u++) DTable[u] = DElt; 2129 } } 2130 rankVal[weight] += length; 2131 } 2132} 2133 2134size_t HUFv07_readDTableX4 (HUFv07_DTable* DTable, const void* src, size_t srcSize) 2135{ 2136 BYTE weightList[HUFv07_SYMBOLVALUE_MAX + 1]; 2137 sortedSymbol_t sortedSymbol[HUFv07_SYMBOLVALUE_MAX + 1]; 2138 U32 rankStats[HUFv07_TABLELOG_ABSOLUTEMAX + 1] = { 0 }; 2139 U32 rankStart0[HUFv07_TABLELOG_ABSOLUTEMAX + 2] = { 0 }; 2140 U32* const rankStart = rankStart0+1; 2141 rankVal_t rankVal; 2142 U32 tableLog, maxW, sizeOfSort, nbSymbols; 2143 DTableDesc dtd = HUFv07_getDTableDesc(DTable); 2144 U32 const maxTableLog = dtd.maxTableLog; 2145 size_t iSize; 2146 void* dtPtr = DTable+1; /* force compiler to avoid strict-aliasing */ 2147 HUFv07_DEltX4* const dt = (HUFv07_DEltX4*)dtPtr; 2148 2149 HUFv07_STATIC_ASSERT(sizeof(HUFv07_DEltX4) == sizeof(HUFv07_DTable)); /* if compilation fails here, assertion is false */ 2150 if (maxTableLog > HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(tableLog_tooLarge); 2151 /* memset(weightList, 0, sizeof(weightList)); */ /* is not necessary, even though some analyzer complain ... */ 2152 2153 iSize = HUFv07_readStats(weightList, HUFv07_SYMBOLVALUE_MAX + 1, rankStats, &nbSymbols, &tableLog, src, srcSize); 2154 if (HUFv07_isError(iSize)) return iSize; 2155 2156 /* check result */ 2157 if (tableLog > maxTableLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */ 2158 2159 /* find maxWeight */ 2160 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */ 2161 2162 /* Get start index of each weight */ 2163 { U32 w, nextRankStart = 0; 2164 for (w=1; w<maxW+1; w++) { 2165 U32 current = nextRankStart; 2166 nextRankStart += rankStats[w]; 2167 rankStart[w] = current; 2168 } 2169 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/ 2170 sizeOfSort = nextRankStart; 2171 } 2172 2173 /* sort symbols by weight */ 2174 { U32 s; 2175 for (s=0; s<nbSymbols; s++) { 2176 U32 const w = weightList[s]; 2177 U32 const r = rankStart[w]++; 2178 sortedSymbol[r].symbol = (BYTE)s; 2179 sortedSymbol[r].weight = (BYTE)w; 2180 } 2181 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */ 2182 } 2183 2184 /* Build rankVal */ 2185 { U32* const rankVal0 = rankVal[0]; 2186 { int const rescale = (maxTableLog-tableLog) - 1; /* tableLog <= maxTableLog */ 2187 U32 nextRankVal = 0; 2188 U32 w; 2189 for (w=1; w<maxW+1; w++) { 2190 U32 current = nextRankVal; 2191 nextRankVal += rankStats[w] << (w+rescale); 2192 rankVal0[w] = current; 2193 } } 2194 { U32 const minBits = tableLog+1 - maxW; 2195 U32 consumed; 2196 for (consumed = minBits; consumed < maxTableLog - minBits + 1; consumed++) { 2197 U32* const rankValPtr = rankVal[consumed]; 2198 U32 w; 2199 for (w = 1; w < maxW+1; w++) { 2200 rankValPtr[w] = rankVal0[w] >> consumed; 2201 } } } } 2202 2203 HUFv07_fillDTableX4(dt, maxTableLog, 2204 sortedSymbol, sizeOfSort, 2205 rankStart0, rankVal, maxW, 2206 tableLog+1); 2207 2208 dtd.tableLog = (BYTE)maxTableLog; 2209 dtd.tableType = 1; 2210 memcpy(DTable, &dtd, sizeof(dtd)); 2211 return iSize; 2212} 2213 2214 2215static U32 HUFv07_decodeSymbolX4(void* op, BITv07_DStream_t* DStream, const HUFv07_DEltX4* dt, const U32 dtLog) 2216{ 2217 const size_t val = BITv07_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 2218 memcpy(op, dt+val, 2); 2219 BITv07_skipBits(DStream, dt[val].nbBits); 2220 return dt[val].length; 2221} 2222 2223static U32 HUFv07_decodeLastSymbolX4(void* op, BITv07_DStream_t* DStream, const HUFv07_DEltX4* dt, const U32 dtLog) 2224{ 2225 const size_t val = BITv07_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 2226 memcpy(op, dt+val, 1); 2227 if (dt[val].length==1) BITv07_skipBits(DStream, dt[val].nbBits); 2228 else { 2229 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) { 2230 BITv07_skipBits(DStream, dt[val].nbBits); 2231 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8)) 2232 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 */ 2233 } } 2234 return 1; 2235} 2236 2237 2238#define HUFv07_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \ 2239 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2240 2241#define HUFv07_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \ 2242 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \ 2243 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2244 2245#define HUFv07_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \ 2246 if (MEM_64bits()) \ 2247 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2248 2249static inline size_t HUFv07_decodeStreamX4(BYTE* p, BITv07_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv07_DEltX4* const dt, const U32 dtLog) 2250{ 2251 BYTE* const pStart = p; 2252 2253 /* up to 8 symbols at a time */ 2254 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p < pEnd-7)) { 2255 HUFv07_DECODE_SYMBOLX4_2(p, bitDPtr); 2256 HUFv07_DECODE_SYMBOLX4_1(p, bitDPtr); 2257 HUFv07_DECODE_SYMBOLX4_2(p, bitDPtr); 2258 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr); 2259 } 2260 2261 /* closer to end : up to 2 symbols at a time */ 2262 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p <= pEnd-2)) 2263 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr); 2264 2265 while (p <= pEnd-2) 2266 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */ 2267 2268 if (p < pEnd) 2269 p += HUFv07_decodeLastSymbolX4(p, bitDPtr, dt, dtLog); 2270 2271 return p-pStart; 2272} 2273 2274 2275static size_t HUFv07_decompress1X4_usingDTable_internal( 2276 void* dst, size_t dstSize, 2277 const void* cSrc, size_t cSrcSize, 2278 const HUFv07_DTable* DTable) 2279{ 2280 BITv07_DStream_t bitD; 2281 2282 /* Init */ 2283 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize); 2284 if (HUFv07_isError(errorCode)) return errorCode; 2285 } 2286 2287 /* decode */ 2288 { BYTE* const ostart = (BYTE*) dst; 2289 BYTE* const oend = ostart + dstSize; 2290 const void* const dtPtr = DTable+1; /* force compiler to not use strict-aliasing */ 2291 const HUFv07_DEltX4* const dt = (const HUFv07_DEltX4*)dtPtr; 2292 DTableDesc const dtd = HUFv07_getDTableDesc(DTable); 2293 HUFv07_decodeStreamX4(ostart, &bitD, oend, dt, dtd.tableLog); 2294 } 2295 2296 /* check */ 2297 if (!BITv07_endOfDStream(&bitD)) return ERROR(corruption_detected); 2298 2299 /* decoded size */ 2300 return dstSize; 2301} 2302 2303size_t HUFv07_decompress1X4_usingDTable( 2304 void* dst, size_t dstSize, 2305 const void* cSrc, size_t cSrcSize, 2306 const HUFv07_DTable* DTable) 2307{ 2308 DTableDesc dtd = HUFv07_getDTableDesc(DTable); 2309 if (dtd.tableType != 1) return ERROR(GENERIC); 2310 return HUFv07_decompress1X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable); 2311} 2312 2313size_t HUFv07_decompress1X4_DCtx (HUFv07_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2314{ 2315 const BYTE* ip = (const BYTE*) cSrc; 2316 2317 size_t const hSize = HUFv07_readDTableX4 (DCtx, cSrc, cSrcSize); 2318 if (HUFv07_isError(hSize)) return hSize; 2319 if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 2320 ip += hSize; cSrcSize -= hSize; 2321 2322 return HUFv07_decompress1X4_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx); 2323} 2324 2325size_t HUFv07_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2326{ 2327 HUFv07_CREATE_STATIC_DTABLEX4(DTable, HUFv07_TABLELOG_MAX); 2328 return HUFv07_decompress1X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize); 2329} 2330 2331static size_t HUFv07_decompress4X4_usingDTable_internal( 2332 void* dst, size_t dstSize, 2333 const void* cSrc, size_t cSrcSize, 2334 const HUFv07_DTable* DTable) 2335{ 2336 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 2337 2338 { const BYTE* const istart = (const BYTE*) cSrc; 2339 BYTE* const ostart = (BYTE*) dst; 2340 BYTE* const oend = ostart + dstSize; 2341 const void* const dtPtr = DTable+1; 2342 const HUFv07_DEltX4* const dt = (const HUFv07_DEltX4*)dtPtr; 2343 2344 /* Init */ 2345 BITv07_DStream_t bitD1; 2346 BITv07_DStream_t bitD2; 2347 BITv07_DStream_t bitD3; 2348 BITv07_DStream_t bitD4; 2349 size_t const length1 = MEM_readLE16(istart); 2350 size_t const length2 = MEM_readLE16(istart+2); 2351 size_t const length3 = MEM_readLE16(istart+4); 2352 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6); 2353 const BYTE* const istart1 = istart + 6; /* jumpTable */ 2354 const BYTE* const istart2 = istart1 + length1; 2355 const BYTE* const istart3 = istart2 + length2; 2356 const BYTE* const istart4 = istart3 + length3; 2357 size_t const segmentSize = (dstSize+3) / 4; 2358 BYTE* const opStart2 = ostart + segmentSize; 2359 BYTE* const opStart3 = opStart2 + segmentSize; 2360 BYTE* const opStart4 = opStart3 + segmentSize; 2361 BYTE* op1 = ostart; 2362 BYTE* op2 = opStart2; 2363 BYTE* op3 = opStart3; 2364 BYTE* op4 = opStart4; 2365 U32 endSignal; 2366 DTableDesc const dtd = HUFv07_getDTableDesc(DTable); 2367 U32 const dtLog = dtd.tableLog; 2368 2369 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 2370 { size_t const errorCode = BITv07_initDStream(&bitD1, istart1, length1); 2371 if (HUFv07_isError(errorCode)) return errorCode; } 2372 { size_t const errorCode = BITv07_initDStream(&bitD2, istart2, length2); 2373 if (HUFv07_isError(errorCode)) return errorCode; } 2374 { size_t const errorCode = BITv07_initDStream(&bitD3, istart3, length3); 2375 if (HUFv07_isError(errorCode)) return errorCode; } 2376 { size_t const errorCode = BITv07_initDStream(&bitD4, istart4, length4); 2377 if (HUFv07_isError(errorCode)) return errorCode; } 2378 2379 /* 16-32 symbols per loop (4-8 symbols per stream) */ 2380 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4); 2381 for ( ; (endSignal==BITv07_DStream_unfinished) && (op4<(oend-7)) ; ) { 2382 HUFv07_DECODE_SYMBOLX4_2(op1, &bitD1); 2383 HUFv07_DECODE_SYMBOLX4_2(op2, &bitD2); 2384 HUFv07_DECODE_SYMBOLX4_2(op3, &bitD3); 2385 HUFv07_DECODE_SYMBOLX4_2(op4, &bitD4); 2386 HUFv07_DECODE_SYMBOLX4_1(op1, &bitD1); 2387 HUFv07_DECODE_SYMBOLX4_1(op2, &bitD2); 2388 HUFv07_DECODE_SYMBOLX4_1(op3, &bitD3); 2389 HUFv07_DECODE_SYMBOLX4_1(op4, &bitD4); 2390 HUFv07_DECODE_SYMBOLX4_2(op1, &bitD1); 2391 HUFv07_DECODE_SYMBOLX4_2(op2, &bitD2); 2392 HUFv07_DECODE_SYMBOLX4_2(op3, &bitD3); 2393 HUFv07_DECODE_SYMBOLX4_2(op4, &bitD4); 2394 HUFv07_DECODE_SYMBOLX4_0(op1, &bitD1); 2395 HUFv07_DECODE_SYMBOLX4_0(op2, &bitD2); 2396 HUFv07_DECODE_SYMBOLX4_0(op3, &bitD3); 2397 HUFv07_DECODE_SYMBOLX4_0(op4, &bitD4); 2398 2399 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4); 2400 } 2401 2402 /* check corruption */ 2403 if (op1 > opStart2) return ERROR(corruption_detected); 2404 if (op2 > opStart3) return ERROR(corruption_detected); 2405 if (op3 > opStart4) return ERROR(corruption_detected); 2406 /* note : op4 supposed already verified within main loop */ 2407 2408 /* finish bitStreams one by one */ 2409 HUFv07_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog); 2410 HUFv07_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog); 2411 HUFv07_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog); 2412 HUFv07_decodeStreamX4(op4, &bitD4, oend, dt, dtLog); 2413 2414 /* check */ 2415 { U32 const endCheck = BITv07_endOfDStream(&bitD1) & BITv07_endOfDStream(&bitD2) & BITv07_endOfDStream(&bitD3) & BITv07_endOfDStream(&bitD4); 2416 if (!endCheck) return ERROR(corruption_detected); } 2417 2418 /* decoded size */ 2419 return dstSize; 2420 } 2421} 2422 2423 2424size_t HUFv07_decompress4X4_usingDTable( 2425 void* dst, size_t dstSize, 2426 const void* cSrc, size_t cSrcSize, 2427 const HUFv07_DTable* DTable) 2428{ 2429 DTableDesc dtd = HUFv07_getDTableDesc(DTable); 2430 if (dtd.tableType != 1) return ERROR(GENERIC); 2431 return HUFv07_decompress4X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable); 2432} 2433 2434 2435size_t HUFv07_decompress4X4_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2436{ 2437 const BYTE* ip = (const BYTE*) cSrc; 2438 2439 size_t hSize = HUFv07_readDTableX4 (dctx, cSrc, cSrcSize); 2440 if (HUFv07_isError(hSize)) return hSize; 2441 if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 2442 ip += hSize; cSrcSize -= hSize; 2443 2444 return HUFv07_decompress4X4_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx); 2445} 2446 2447size_t HUFv07_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2448{ 2449 HUFv07_CREATE_STATIC_DTABLEX4(DTable, HUFv07_TABLELOG_MAX); 2450 return HUFv07_decompress4X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize); 2451} 2452 2453 2454/* ********************************/ 2455/* Generic decompression selector */ 2456/* ********************************/ 2457 2458size_t HUFv07_decompress1X_usingDTable(void* dst, size_t maxDstSize, 2459 const void* cSrc, size_t cSrcSize, 2460 const HUFv07_DTable* DTable) 2461{ 2462 DTableDesc const dtd = HUFv07_getDTableDesc(DTable); 2463 return dtd.tableType ? HUFv07_decompress1X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) : 2464 HUFv07_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable); 2465} 2466 2467size_t HUFv07_decompress4X_usingDTable(void* dst, size_t maxDstSize, 2468 const void* cSrc, size_t cSrcSize, 2469 const HUFv07_DTable* DTable) 2470{ 2471 DTableDesc const dtd = HUFv07_getDTableDesc(DTable); 2472 return dtd.tableType ? HUFv07_decompress4X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) : 2473 HUFv07_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable); 2474} 2475 2476 2477typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t; 2478static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] = 2479{ 2480 /* single, double, quad */ 2481 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */ 2482 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */ 2483 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */ 2484 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */ 2485 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */ 2486 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */ 2487 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */ 2488 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */ 2489 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */ 2490 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */ 2491 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */ 2492 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */ 2493 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */ 2494 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */ 2495 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */ 2496 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */ 2497}; 2498 2499/** HUFv07_selectDecoder() : 2500* Tells which decoder is likely to decode faster, 2501* based on a set of pre-determined metrics. 2502* @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 . 2503* Assumption : 0 < cSrcSize < dstSize <= 128 KB */ 2504U32 HUFv07_selectDecoder (size_t dstSize, size_t cSrcSize) 2505{ 2506 /* decoder timing evaluation */ 2507 U32 const Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */ 2508 U32 const D256 = (U32)(dstSize >> 8); 2509 U32 const DTime0 = algoTime[Q][0].tableTime + (algoTime[Q][0].decode256Time * D256); 2510 U32 DTime1 = algoTime[Q][1].tableTime + (algoTime[Q][1].decode256Time * D256); 2511 DTime1 += DTime1 >> 3; /* advantage to algorithm using less memory, for cache eviction */ 2512 2513 return DTime1 < DTime0; 2514} 2515 2516 2517typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); 2518 2519size_t HUFv07_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2520{ 2521 static const decompressionAlgo decompress[2] = { HUFv07_decompress4X2, HUFv07_decompress4X4 }; 2522 2523 /* validation checks */ 2524 if (dstSize == 0) return ERROR(dstSize_tooSmall); 2525 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */ 2526 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */ 2527 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */ 2528 2529 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize); 2530 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize); 2531 } 2532 2533 /* return HUFv07_decompress4X2(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams single-symbol decoding */ 2534 /* return HUFv07_decompress4X4(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams double-symbols decoding */ 2535} 2536 2537size_t HUFv07_decompress4X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2538{ 2539 /* validation checks */ 2540 if (dstSize == 0) return ERROR(dstSize_tooSmall); 2541 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */ 2542 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */ 2543 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */ 2544 2545 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize); 2546 return algoNb ? HUFv07_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) : 2547 HUFv07_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ; 2548 } 2549} 2550 2551size_t HUFv07_decompress4X_hufOnly (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2552{ 2553 /* validation checks */ 2554 if (dstSize == 0) return ERROR(dstSize_tooSmall); 2555 if ((cSrcSize >= dstSize) || (cSrcSize <= 1)) return ERROR(corruption_detected); /* invalid */ 2556 2557 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize); 2558 return algoNb ? HUFv07_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) : 2559 HUFv07_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ; 2560 } 2561} 2562 2563size_t HUFv07_decompress1X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2564{ 2565 /* validation checks */ 2566 if (dstSize == 0) return ERROR(dstSize_tooSmall); 2567 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */ 2568 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */ 2569 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */ 2570 2571 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize); 2572 return algoNb ? HUFv07_decompress1X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) : 2573 HUFv07_decompress1X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ; 2574 } 2575} 2576/* 2577 Common functions of Zstd compression library 2578 Copyright (C) 2015-2016, Yann Collet. 2579 2580 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 2581 2582 Redistribution and use in source and binary forms, with or without 2583 modification, are permitted provided that the following conditions are 2584 met: 2585 * Redistributions of source code must retain the above copyright 2586 notice, this list of conditions and the following disclaimer. 2587 * Redistributions in binary form must reproduce the above 2588 copyright notice, this list of conditions and the following disclaimer 2589 in the documentation and/or other materials provided with the 2590 distribution. 2591 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2592 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2593 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2594 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2595 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2596 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2597 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2598 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2599 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2600 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2601 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2602 2603 You can contact the author at : 2604 - zstd homepage : http://www.zstd.net/ 2605*/ 2606 2607 2608 2609/*-**************************************** 2610* ZSTD Error Management 2611******************************************/ 2612/*! ZSTDv07_isError() : 2613* tells if a return value is an error code */ 2614unsigned ZSTDv07_isError(size_t code) { return ERR_isError(code); } 2615 2616/*! ZSTDv07_getErrorName() : 2617* provides error code string from function result (useful for debugging) */ 2618const char* ZSTDv07_getErrorName(size_t code) { return ERR_getErrorName(code); } 2619 2620 2621 2622/* ************************************************************** 2623* ZBUFF Error Management 2624****************************************************************/ 2625unsigned ZBUFFv07_isError(size_t errorCode) { return ERR_isError(errorCode); } 2626 2627const char* ZBUFFv07_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); } 2628 2629 2630 2631static void* ZSTDv07_defaultAllocFunction(void* opaque, size_t size) 2632{ 2633 void* address = malloc(size); 2634 (void)opaque; 2635 /* printf("alloc %p, %d opaque=%p \n", address, (int)size, opaque); */ 2636 return address; 2637} 2638 2639static void ZSTDv07_defaultFreeFunction(void* opaque, void* address) 2640{ 2641 (void)opaque; 2642 /* if (address) printf("free %p opaque=%p \n", address, opaque); */ 2643 free(address); 2644} 2645/* 2646 zstd_internal - common functions to include 2647 Header File for include 2648 Copyright (C) 2014-2016, Yann Collet. 2649 2650 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 2651 2652 Redistribution and use in source and binary forms, with or without 2653 modification, are permitted provided that the following conditions are 2654 met: 2655 * Redistributions of source code must retain the above copyright 2656 notice, this list of conditions and the following disclaimer. 2657 * Redistributions in binary form must reproduce the above 2658 copyright notice, this list of conditions and the following disclaimer 2659 in the documentation and/or other materials provided with the 2660 distribution. 2661 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2662 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2663 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2664 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2665 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2666 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2667 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2668 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2669 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2670 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2671 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2672 2673 You can contact the author at : 2674 - zstd homepage : https://www.zstd.net 2675*/ 2676#ifndef ZSTDv07_CCOMMON_H_MODULE 2677#define ZSTDv07_CCOMMON_H_MODULE 2678 2679 2680/*-************************************* 2681* Common macros 2682***************************************/ 2683#define MIN(a,b) ((a)<(b) ? (a) : (b)) 2684#define MAX(a,b) ((a)>(b) ? (a) : (b)) 2685 2686 2687/*-************************************* 2688* Common constants 2689***************************************/ 2690#define ZSTDv07_OPT_NUM (1<<12) 2691#define ZSTDv07_DICT_MAGIC 0xEC30A437 /* v0.7 */ 2692 2693#define ZSTDv07_REP_NUM 3 2694#define ZSTDv07_REP_INIT ZSTDv07_REP_NUM 2695#define ZSTDv07_REP_MOVE (ZSTDv07_REP_NUM-1) 2696static const U32 repStartValue[ZSTDv07_REP_NUM] = { 1, 4, 8 }; 2697 2698#define KB *(1 <<10) 2699#define MB *(1 <<20) 2700#define GB *(1U<<30) 2701 2702#define BIT7 128 2703#define BIT6 64 2704#define BIT5 32 2705#define BIT4 16 2706#define BIT1 2 2707#define BIT0 1 2708 2709#define ZSTDv07_WINDOWLOG_ABSOLUTEMIN 10 2710static const size_t ZSTDv07_fcs_fieldSize[4] = { 0, 2, 4, 8 }; 2711static const size_t ZSTDv07_did_fieldSize[4] = { 0, 1, 2, 4 }; 2712 2713#define ZSTDv07_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */ 2714static const size_t ZSTDv07_blockHeaderSize = ZSTDv07_BLOCKHEADERSIZE; 2715typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t; 2716 2717#define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */ 2718#define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */ 2719 2720#define HufLog 12 2721typedef enum { lbt_huffman, lbt_repeat, lbt_raw, lbt_rle } litBlockType_t; 2722 2723#define LONGNBSEQ 0x7F00 2724 2725#define MINMATCH 3 2726#define EQUAL_READ32 4 2727 2728#define Litbits 8 2729#define MaxLit ((1<<Litbits) - 1) 2730#define MaxML 52 2731#define MaxLL 35 2732#define MaxOff 28 2733#define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */ 2734#define MLFSELog 9 2735#define LLFSELog 9 2736#define OffFSELog 8 2737 2738#define FSEv07_ENCODING_RAW 0 2739#define FSEv07_ENCODING_RLE 1 2740#define FSEv07_ENCODING_STATIC 2 2741#define FSEv07_ENCODING_DYNAMIC 3 2742 2743#define ZSTD_CONTENTSIZE_ERROR (0ULL - 2) 2744 2745static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2746 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12, 2747 13,14,15,16 }; 2748static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2749 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1, 2750 -1,-1,-1,-1 }; 2751static const U32 LL_defaultNormLog = 6; 2752 2753static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2754 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2755 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11, 2756 12,13,14,15,16 }; 2757static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2758 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2759 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1, 2760 -1,-1,-1,-1,-1 }; 2761static const U32 ML_defaultNormLog = 6; 2762 2763static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2764 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 }; 2765static const U32 OF_defaultNormLog = 5; 2766 2767 2768/*-******************************************* 2769* Shared functions to include for inlining 2770*********************************************/ 2771static void ZSTDv07_copy8(void* dst, const void* src) { memcpy(dst, src, 8); } 2772#define COPY8(d,s) { ZSTDv07_copy8(d,s); d+=8; s+=8; } 2773 2774/*! ZSTDv07_wildcopy() : 2775* custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */ 2776#define WILDCOPY_OVERLENGTH 8 2777MEM_STATIC void ZSTDv07_wildcopy(void* dst, const void* src, ptrdiff_t length) 2778{ 2779 const BYTE* ip = (const BYTE*)src; 2780 BYTE* op = (BYTE*)dst; 2781 BYTE* const oend = op + length; 2782 do 2783 COPY8(op, ip) 2784 while (op < oend); 2785} 2786 2787 2788/*-******************************************* 2789* Private interfaces 2790*********************************************/ 2791typedef struct ZSTDv07_stats_s ZSTDv07_stats_t; 2792 2793typedef struct { 2794 U32 off; 2795 U32 len; 2796} ZSTDv07_match_t; 2797 2798typedef struct { 2799 U32 price; 2800 U32 off; 2801 U32 mlen; 2802 U32 litlen; 2803 U32 rep[ZSTDv07_REP_INIT]; 2804} ZSTDv07_optimal_t; 2805 2806struct ZSTDv07_stats_s { U32 unused; }; 2807 2808typedef struct { 2809 void* buffer; 2810 U32* offsetStart; 2811 U32* offset; 2812 BYTE* offCodeStart; 2813 BYTE* litStart; 2814 BYTE* lit; 2815 U16* litLengthStart; 2816 U16* litLength; 2817 BYTE* llCodeStart; 2818 U16* matchLengthStart; 2819 U16* matchLength; 2820 BYTE* mlCodeStart; 2821 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */ 2822 U32 longLengthPos; 2823 /* opt */ 2824 ZSTDv07_optimal_t* priceTable; 2825 ZSTDv07_match_t* matchTable; 2826 U32* matchLengthFreq; 2827 U32* litLengthFreq; 2828 U32* litFreq; 2829 U32* offCodeFreq; 2830 U32 matchLengthSum; 2831 U32 matchSum; 2832 U32 litLengthSum; 2833 U32 litSum; 2834 U32 offCodeSum; 2835 U32 log2matchLengthSum; 2836 U32 log2matchSum; 2837 U32 log2litLengthSum; 2838 U32 log2litSum; 2839 U32 log2offCodeSum; 2840 U32 factor; 2841 U32 cachedPrice; 2842 U32 cachedLitLength; 2843 const BYTE* cachedLiterals; 2844 ZSTDv07_stats_t stats; 2845} seqStore_t; 2846 2847void ZSTDv07_seqToCodes(const seqStore_t* seqStorePtr, size_t const nbSeq); 2848 2849/* custom memory allocation functions */ 2850static const ZSTDv07_customMem defaultCustomMem = { ZSTDv07_defaultAllocFunction, ZSTDv07_defaultFreeFunction, NULL }; 2851 2852#endif /* ZSTDv07_CCOMMON_H_MODULE */ 2853/* 2854 zstd - standard compression library 2855 Copyright (C) 2014-2016, Yann Collet. 2856 2857 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 2858 2859 Redistribution and use in source and binary forms, with or without 2860 modification, are permitted provided that the following conditions are 2861 met: 2862 * Redistributions of source code must retain the above copyright 2863 notice, this list of conditions and the following disclaimer. 2864 * Redistributions in binary form must reproduce the above 2865 copyright notice, this list of conditions and the following disclaimer 2866 in the documentation and/or other materials provided with the 2867 distribution. 2868 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2869 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2870 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2871 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2872 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2873 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2874 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2875 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2876 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2877 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2878 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2879 2880 You can contact the author at : 2881 - zstd homepage : http://www.zstd.net 2882*/ 2883 2884/* *************************************************************** 2885* Tuning parameters 2886*****************************************************************/ 2887/*! 2888 * HEAPMODE : 2889 * Select how default decompression function ZSTDv07_decompress() will allocate memory, 2890 * in memory stack (0), or in memory heap (1, requires malloc()) 2891 */ 2892#ifndef ZSTDv07_HEAPMODE 2893# define ZSTDv07_HEAPMODE 1 2894#endif 2895 2896 2897/*-******************************************************* 2898* Compiler specifics 2899*********************************************************/ 2900#ifdef _MSC_VER /* Visual Studio */ 2901# include <intrin.h> /* For Visual 2005 */ 2902# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 2903# pragma warning(disable : 4324) /* disable: C4324: padded structure */ 2904# pragma warning(disable : 4100) /* disable: C4100: unreferenced formal parameter */ 2905#endif 2906 2907 2908/*-************************************* 2909* Macros 2910***************************************/ 2911#define ZSTDv07_isError ERR_isError /* for inlining */ 2912#define FSEv07_isError ERR_isError 2913#define HUFv07_isError ERR_isError 2914 2915 2916/*_******************************************************* 2917* Memory operations 2918**********************************************************/ 2919static void ZSTDv07_copy4(void* dst, const void* src) { memcpy(dst, src, 4); } 2920 2921 2922/*-************************************************************* 2923* Context management 2924***************************************************************/ 2925typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader, 2926 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock, 2927 ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTDv07_dStage; 2928 2929struct ZSTDv07_DCtx_s 2930{ 2931 FSEv07_DTable LLTable[FSEv07_DTABLE_SIZE_U32(LLFSELog)]; 2932 FSEv07_DTable OffTable[FSEv07_DTABLE_SIZE_U32(OffFSELog)]; 2933 FSEv07_DTable MLTable[FSEv07_DTABLE_SIZE_U32(MLFSELog)]; 2934 HUFv07_DTable hufTable[HUFv07_DTABLE_SIZE(HufLog)]; /* can accommodate HUFv07_decompress4X */ 2935 const void* previousDstEnd; 2936 const void* base; 2937 const void* vBase; 2938 const void* dictEnd; 2939 size_t expected; 2940 U32 rep[3]; 2941 ZSTDv07_frameParams fParams; 2942 blockType_t bType; /* used in ZSTDv07_decompressContinue(), to transfer blockType between header decoding and block decoding stages */ 2943 ZSTDv07_dStage stage; 2944 U32 litEntropy; 2945 U32 fseEntropy; 2946 XXH64_state_t xxhState; 2947 size_t headerSize; 2948 U32 dictID; 2949 const BYTE* litPtr; 2950 ZSTDv07_customMem customMem; 2951 size_t litSize; 2952 BYTE litBuffer[ZSTDv07_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH]; 2953 BYTE headerBuffer[ZSTDv07_FRAMEHEADERSIZE_MAX]; 2954}; /* typedef'd to ZSTDv07_DCtx within "zstd_static.h" */ 2955 2956int ZSTDv07_isSkipFrame(ZSTDv07_DCtx* dctx); 2957 2958size_t ZSTDv07_sizeofDCtx (const ZSTDv07_DCtx* dctx) { return sizeof(*dctx); } 2959 2960size_t ZSTDv07_estimateDCtxSize(void) { return sizeof(ZSTDv07_DCtx); } 2961 2962size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx* dctx) 2963{ 2964 dctx->expected = ZSTDv07_frameHeaderSize_min; 2965 dctx->stage = ZSTDds_getFrameHeaderSize; 2966 dctx->previousDstEnd = NULL; 2967 dctx->base = NULL; 2968 dctx->vBase = NULL; 2969 dctx->dictEnd = NULL; 2970 dctx->hufTable[0] = (HUFv07_DTable)((HufLog)*0x1000001); 2971 dctx->litEntropy = dctx->fseEntropy = 0; 2972 dctx->dictID = 0; 2973 { int i; for (i=0; i<ZSTDv07_REP_NUM; i++) dctx->rep[i] = repStartValue[i]; } 2974 return 0; 2975} 2976 2977ZSTDv07_DCtx* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem) 2978{ 2979 ZSTDv07_DCtx* dctx; 2980 2981 if (!customMem.customAlloc && !customMem.customFree) 2982 customMem = defaultCustomMem; 2983 2984 if (!customMem.customAlloc || !customMem.customFree) 2985 return NULL; 2986 2987 dctx = (ZSTDv07_DCtx*) customMem.customAlloc(customMem.opaque, sizeof(ZSTDv07_DCtx)); 2988 if (!dctx) return NULL; 2989 memcpy(&dctx->customMem, &customMem, sizeof(ZSTDv07_customMem)); 2990 ZSTDv07_decompressBegin(dctx); 2991 return dctx; 2992} 2993 2994ZSTDv07_DCtx* ZSTDv07_createDCtx(void) 2995{ 2996 return ZSTDv07_createDCtx_advanced(defaultCustomMem); 2997} 2998 2999size_t ZSTDv07_freeDCtx(ZSTDv07_DCtx* dctx) 3000{ 3001 if (dctx==NULL) return 0; /* support free on NULL */ 3002 dctx->customMem.customFree(dctx->customMem.opaque, dctx); 3003 return 0; /* reserved as a potential error code in the future */ 3004} 3005 3006void ZSTDv07_copyDCtx(ZSTDv07_DCtx* dstDCtx, const ZSTDv07_DCtx* srcDCtx) 3007{ 3008 memcpy(dstDCtx, srcDCtx, 3009 sizeof(ZSTDv07_DCtx) - (ZSTDv07_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH + ZSTDv07_frameHeaderSize_max)); /* no need to copy workspace */ 3010} 3011 3012 3013/*-************************************************************* 3014* Decompression section 3015***************************************************************/ 3016 3017/* Frame format description 3018 Frame Header - [ Block Header - Block ] - Frame End 3019 1) Frame Header 3020 - 4 bytes - Magic Number : ZSTDv07_MAGICNUMBER (defined within zstd.h) 3021 - 1 byte - Frame Descriptor 3022 2) Block Header 3023 - 3 bytes, starting with a 2-bits descriptor 3024 Uncompressed, Compressed, Frame End, unused 3025 3) Block 3026 See Block Format Description 3027 4) Frame End 3028 - 3 bytes, compatible with Block Header 3029*/ 3030 3031 3032/* Frame Header : 3033 3034 1 byte - FrameHeaderDescription : 3035 bit 0-1 : dictID (0, 1, 2 or 4 bytes) 3036 bit 2 : checksumFlag 3037 bit 3 : reserved (must be zero) 3038 bit 4 : reserved (unused, can be any value) 3039 bit 5 : Single Segment (if 1, WindowLog byte is not present) 3040 bit 6-7 : FrameContentFieldSize (0, 2, 4, or 8) 3041 if (SkippedWindowLog && !FrameContentFieldsize) FrameContentFieldsize=1; 3042 3043 Optional : WindowLog (0 or 1 byte) 3044 bit 0-2 : octal Fractional (1/8th) 3045 bit 3-7 : Power of 2, with 0 = 1 KB (up to 2 TB) 3046 3047 Optional : dictID (0, 1, 2 or 4 bytes) 3048 Automatic adaptation 3049 0 : no dictID 3050 1 : 1 - 255 3051 2 : 256 - 65535 3052 4 : all other values 3053 3054 Optional : content size (0, 1, 2, 4 or 8 bytes) 3055 0 : unknown (fcfs==0 and swl==0) 3056 1 : 0-255 bytes (fcfs==0 and swl==1) 3057 2 : 256 - 65535+256 (fcfs==1) 3058 4 : 0 - 4GB-1 (fcfs==2) 3059 8 : 0 - 16EB-1 (fcfs==3) 3060*/ 3061 3062 3063/* Compressed Block, format description 3064 3065 Block = Literal Section - Sequences Section 3066 Prerequisite : size of (compressed) block, maximum size of regenerated data 3067 3068 1) Literal Section 3069 3070 1.1) Header : 1-5 bytes 3071 flags: 2 bits 3072 00 compressed by Huff0 3073 01 unused 3074 10 is Raw (uncompressed) 3075 11 is Rle 3076 Note : using 01 => Huff0 with precomputed table ? 3077 Note : delta map ? => compressed ? 3078 3079 1.1.1) Huff0-compressed literal block : 3-5 bytes 3080 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream 3081 srcSize < 1 KB => 3 bytes (2-2-10-10) 3082 srcSize < 16KB => 4 bytes (2-2-14-14) 3083 else => 5 bytes (2-2-18-18) 3084 big endian convention 3085 3086 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes 3087 size : 5 bits: (IS_RAW<<6) + (0<<4) + size 3088 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8) 3089 size&255 3090 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16) 3091 size>>8&255 3092 size&255 3093 3094 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes 3095 size : 5 bits: (IS_RLE<<6) + (0<<4) + size 3096 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8) 3097 size&255 3098 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16) 3099 size>>8&255 3100 size&255 3101 3102 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes 3103 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream 3104 srcSize < 1 KB => 3 bytes (2-2-10-10) 3105 srcSize < 16KB => 4 bytes (2-2-14-14) 3106 else => 5 bytes (2-2-18-18) 3107 big endian convention 3108 3109 1- CTable available (stored into workspace ?) 3110 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?) 3111 3112 3113 1.2) Literal block content 3114 3115 1.2.1) Huff0 block, using sizes from header 3116 See Huff0 format 3117 3118 1.2.2) Huff0 block, using prepared table 3119 3120 1.2.3) Raw content 3121 3122 1.2.4) single byte 3123 3124 3125 2) Sequences section 3126 TO DO 3127*/ 3128 3129/** ZSTDv07_frameHeaderSize() : 3130* srcSize must be >= ZSTDv07_frameHeaderSize_min. 3131* @return : size of the Frame Header */ 3132static size_t ZSTDv07_frameHeaderSize(const void* src, size_t srcSize) 3133{ 3134 if (srcSize < ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong); 3135 { BYTE const fhd = ((const BYTE*)src)[4]; 3136 U32 const dictID= fhd & 3; 3137 U32 const directMode = (fhd >> 5) & 1; 3138 U32 const fcsId = fhd >> 6; 3139 return ZSTDv07_frameHeaderSize_min + !directMode + ZSTDv07_did_fieldSize[dictID] + ZSTDv07_fcs_fieldSize[fcsId] 3140 + (directMode && !ZSTDv07_fcs_fieldSize[fcsId]); 3141 } 3142} 3143 3144 3145/** ZSTDv07_getFrameParams() : 3146* decode Frame Header, or require larger `srcSize`. 3147* @return : 0, `fparamsPtr` is correctly filled, 3148* >0, `srcSize` is too small, result is expected `srcSize`, 3149* or an error code, which can be tested using ZSTDv07_isError() */ 3150size_t ZSTDv07_getFrameParams(ZSTDv07_frameParams* fparamsPtr, const void* src, size_t srcSize) 3151{ 3152 const BYTE* ip = (const BYTE*)src; 3153 3154 if (srcSize < ZSTDv07_frameHeaderSize_min) return ZSTDv07_frameHeaderSize_min; 3155 memset(fparamsPtr, 0, sizeof(*fparamsPtr)); 3156 if (MEM_readLE32(src) != ZSTDv07_MAGICNUMBER) { 3157 if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTDv07_MAGIC_SKIPPABLE_START) { 3158 if (srcSize < ZSTDv07_skippableHeaderSize) return ZSTDv07_skippableHeaderSize; /* magic number + skippable frame length */ 3159 fparamsPtr->frameContentSize = MEM_readLE32((const char *)src + 4); 3160 fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */ 3161 return 0; 3162 } 3163 return ERROR(prefix_unknown); 3164 } 3165 3166 /* ensure there is enough `srcSize` to fully read/decode frame header */ 3167 { size_t const fhsize = ZSTDv07_frameHeaderSize(src, srcSize); 3168 if (srcSize < fhsize) return fhsize; } 3169 3170 { BYTE const fhdByte = ip[4]; 3171 size_t pos = 5; 3172 U32 const dictIDSizeCode = fhdByte&3; 3173 U32 const checksumFlag = (fhdByte>>2)&1; 3174 U32 const directMode = (fhdByte>>5)&1; 3175 U32 const fcsID = fhdByte>>6; 3176 U32 const windowSizeMax = 1U << ZSTDv07_WINDOWLOG_MAX; 3177 U32 windowSize = 0; 3178 U32 dictID = 0; 3179 U64 frameContentSize = 0; 3180 if ((fhdByte & 0x08) != 0) /* reserved bits, which must be zero */ 3181 return ERROR(frameParameter_unsupported); 3182 if (!directMode) { 3183 BYTE const wlByte = ip[pos++]; 3184 U32 const windowLog = (wlByte >> 3) + ZSTDv07_WINDOWLOG_ABSOLUTEMIN; 3185 if (windowLog > ZSTDv07_WINDOWLOG_MAX) 3186 return ERROR(frameParameter_unsupported); 3187 windowSize = (1U << windowLog); 3188 windowSize += (windowSize >> 3) * (wlByte&7); 3189 } 3190 3191 switch(dictIDSizeCode) 3192 { 3193 default: /* impossible */ 3194 case 0 : break; 3195 case 1 : dictID = ip[pos]; pos++; break; 3196 case 2 : dictID = MEM_readLE16(ip+pos); pos+=2; break; 3197 case 3 : dictID = MEM_readLE32(ip+pos); pos+=4; break; 3198 } 3199 switch(fcsID) 3200 { 3201 default: /* impossible */ 3202 case 0 : if (directMode) frameContentSize = ip[pos]; break; 3203 case 1 : frameContentSize = MEM_readLE16(ip+pos)+256; break; 3204 case 2 : frameContentSize = MEM_readLE32(ip+pos); break; 3205 case 3 : frameContentSize = MEM_readLE64(ip+pos); break; 3206 } 3207 if (!windowSize) windowSize = (U32)frameContentSize; 3208 if (windowSize > windowSizeMax) 3209 return ERROR(frameParameter_unsupported); 3210 fparamsPtr->frameContentSize = frameContentSize; 3211 fparamsPtr->windowSize = windowSize; 3212 fparamsPtr->dictID = dictID; 3213 fparamsPtr->checksumFlag = checksumFlag; 3214 } 3215 return 0; 3216} 3217 3218 3219/** ZSTDv07_getDecompressedSize() : 3220* compatible with legacy mode 3221* @return : decompressed size if known, 0 otherwise 3222 note : 0 can mean any of the following : 3223 - decompressed size is not provided within frame header 3224 - frame header unknown / not supported 3225 - frame header not completely provided (`srcSize` too small) */ 3226unsigned long long ZSTDv07_getDecompressedSize(const void* src, size_t srcSize) 3227{ 3228 ZSTDv07_frameParams fparams; 3229 size_t const frResult = ZSTDv07_getFrameParams(&fparams, src, srcSize); 3230 if (frResult!=0) return 0; 3231 return fparams.frameContentSize; 3232} 3233 3234 3235/** ZSTDv07_decodeFrameHeader() : 3236* `srcSize` must be the size provided by ZSTDv07_frameHeaderSize(). 3237* @return : 0 if success, or an error code, which can be tested using ZSTDv07_isError() */ 3238static size_t ZSTDv07_decodeFrameHeader(ZSTDv07_DCtx* dctx, const void* src, size_t srcSize) 3239{ 3240 size_t const result = ZSTDv07_getFrameParams(&(dctx->fParams), src, srcSize); 3241 if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID)) return ERROR(dictionary_wrong); 3242 if (dctx->fParams.checksumFlag) XXH64_reset(&dctx->xxhState, 0); 3243 return result; 3244} 3245 3246 3247typedef struct 3248{ 3249 blockType_t blockType; 3250 U32 origSize; 3251} blockProperties_t; 3252 3253/*! ZSTDv07_getcBlockSize() : 3254* Provides the size of compressed block from block header `src` */ 3255static size_t ZSTDv07_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr) 3256{ 3257 const BYTE* const in = (const BYTE*)src; 3258 U32 cSize; 3259 3260 if (srcSize < ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong); 3261 3262 bpPtr->blockType = (blockType_t)((*in) >> 6); 3263 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16); 3264 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0; 3265 3266 if (bpPtr->blockType == bt_end) return 0; 3267 if (bpPtr->blockType == bt_rle) return 1; 3268 return cSize; 3269} 3270 3271 3272static size_t ZSTDv07_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize) 3273{ 3274 if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall); 3275 if (srcSize > 0) { 3276 memcpy(dst, src, srcSize); 3277 } 3278 return srcSize; 3279} 3280 3281 3282/*! ZSTDv07_decodeLiteralsBlock() : 3283 @return : nb of bytes read from src (< srcSize ) */ 3284static size_t ZSTDv07_decodeLiteralsBlock(ZSTDv07_DCtx* dctx, 3285 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */ 3286{ 3287 const BYTE* const istart = (const BYTE*) src; 3288 3289 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected); 3290 3291 switch((litBlockType_t)(istart[0]>> 6)) 3292 { 3293 case lbt_huffman: 3294 { size_t litSize, litCSize, singleStream=0; 3295 U32 lhSize = (istart[0] >> 4) & 3; 3296 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */ 3297 switch(lhSize) 3298 { 3299 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ 3300 /* 2 - 2 - 10 - 10 */ 3301 lhSize=3; 3302 singleStream = istart[0] & 16; 3303 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2); 3304 litCSize = ((istart[1] & 3) << 8) + istart[2]; 3305 break; 3306 case 2: 3307 /* 2 - 2 - 14 - 14 */ 3308 lhSize=4; 3309 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6); 3310 litCSize = ((istart[2] & 63) << 8) + istart[3]; 3311 break; 3312 case 3: 3313 /* 2 - 2 - 18 - 18 */ 3314 lhSize=5; 3315 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2); 3316 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4]; 3317 break; 3318 } 3319 if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected); 3320 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected); 3321 3322 if (HUFv07_isError(singleStream ? 3323 HUFv07_decompress1X2_DCtx(dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) : 3324 HUFv07_decompress4X_hufOnly (dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) )) 3325 return ERROR(corruption_detected); 3326 3327 dctx->litPtr = dctx->litBuffer; 3328 dctx->litSize = litSize; 3329 dctx->litEntropy = 1; 3330 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 3331 return litCSize + lhSize; 3332 } 3333 case lbt_repeat: 3334 { size_t litSize, litCSize; 3335 U32 lhSize = ((istart[0]) >> 4) & 3; 3336 if (lhSize != 1) /* only case supported for now : small litSize, single stream */ 3337 return ERROR(corruption_detected); 3338 if (dctx->litEntropy==0) 3339 return ERROR(dictionary_corrupted); 3340 3341 /* 2 - 2 - 10 - 10 */ 3342 lhSize=3; 3343 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2); 3344 litCSize = ((istart[1] & 3) << 8) + istart[2]; 3345 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected); 3346 3347 { size_t const errorCode = HUFv07_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTable); 3348 if (HUFv07_isError(errorCode)) return ERROR(corruption_detected); 3349 } 3350 dctx->litPtr = dctx->litBuffer; 3351 dctx->litSize = litSize; 3352 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 3353 return litCSize + lhSize; 3354 } 3355 case lbt_raw: 3356 { size_t litSize; 3357 U32 lhSize = ((istart[0]) >> 4) & 3; 3358 switch(lhSize) 3359 { 3360 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ 3361 lhSize=1; 3362 litSize = istart[0] & 31; 3363 break; 3364 case 2: 3365 litSize = ((istart[0] & 15) << 8) + istart[1]; 3366 break; 3367 case 3: 3368 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2]; 3369 break; 3370 } 3371 3372 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */ 3373 if (litSize+lhSize > srcSize) return ERROR(corruption_detected); 3374 memcpy(dctx->litBuffer, istart+lhSize, litSize); 3375 dctx->litPtr = dctx->litBuffer; 3376 dctx->litSize = litSize; 3377 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 3378 return lhSize+litSize; 3379 } 3380 /* direct reference into compressed stream */ 3381 dctx->litPtr = istart+lhSize; 3382 dctx->litSize = litSize; 3383 return lhSize+litSize; 3384 } 3385 case lbt_rle: 3386 { size_t litSize; 3387 U32 lhSize = ((istart[0]) >> 4) & 3; 3388 switch(lhSize) 3389 { 3390 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ 3391 lhSize = 1; 3392 litSize = istart[0] & 31; 3393 break; 3394 case 2: 3395 litSize = ((istart[0] & 15) << 8) + istart[1]; 3396 break; 3397 case 3: 3398 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2]; 3399 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */ 3400 break; 3401 } 3402 if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected); 3403 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH); 3404 dctx->litPtr = dctx->litBuffer; 3405 dctx->litSize = litSize; 3406 return lhSize+1; 3407 } 3408 default: 3409 return ERROR(corruption_detected); /* impossible */ 3410 } 3411} 3412 3413 3414/*! ZSTDv07_buildSeqTable() : 3415 @return : nb bytes read from src, 3416 or an error code if it fails, testable with ZSTDv07_isError() 3417*/ 3418static size_t ZSTDv07_buildSeqTable(FSEv07_DTable* DTable, U32 type, U32 max, U32 maxLog, 3419 const void* src, size_t srcSize, 3420 const S16* defaultNorm, U32 defaultLog, U32 flagRepeatTable) 3421{ 3422 switch(type) 3423 { 3424 case FSEv07_ENCODING_RLE : 3425 if (!srcSize) return ERROR(srcSize_wrong); 3426 if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected); 3427 FSEv07_buildDTable_rle(DTable, *(const BYTE*)src); /* if *src > max, data is corrupted */ 3428 return 1; 3429 case FSEv07_ENCODING_RAW : 3430 FSEv07_buildDTable(DTable, defaultNorm, max, defaultLog); 3431 return 0; 3432 case FSEv07_ENCODING_STATIC: 3433 if (!flagRepeatTable) return ERROR(corruption_detected); 3434 return 0; 3435 default : /* impossible */ 3436 case FSEv07_ENCODING_DYNAMIC : 3437 { U32 tableLog; 3438 S16 norm[MaxSeq+1]; 3439 size_t const headerSize = FSEv07_readNCount(norm, &max, &tableLog, src, srcSize); 3440 if (FSEv07_isError(headerSize)) return ERROR(corruption_detected); 3441 if (tableLog > maxLog) return ERROR(corruption_detected); 3442 FSEv07_buildDTable(DTable, norm, max, tableLog); 3443 return headerSize; 3444 } } 3445} 3446 3447 3448static size_t ZSTDv07_decodeSeqHeaders(int* nbSeqPtr, 3449 FSEv07_DTable* DTableLL, FSEv07_DTable* DTableML, FSEv07_DTable* DTableOffb, U32 flagRepeatTable, 3450 const void* src, size_t srcSize) 3451{ 3452 const BYTE* const istart = (const BYTE*)src; 3453 const BYTE* const iend = istart + srcSize; 3454 const BYTE* ip = istart; 3455 3456 /* check */ 3457 if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong); 3458 3459 /* SeqHead */ 3460 { int nbSeq = *ip++; 3461 if (!nbSeq) { *nbSeqPtr=0; return 1; } 3462 if (nbSeq > 0x7F) { 3463 if (nbSeq == 0xFF) { 3464 if (ip+2 > iend) return ERROR(srcSize_wrong); 3465 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2; 3466 } else { 3467 if (ip >= iend) return ERROR(srcSize_wrong); 3468 nbSeq = ((nbSeq-0x80)<<8) + *ip++; 3469 } 3470 } 3471 *nbSeqPtr = nbSeq; 3472 } 3473 3474 /* FSE table descriptors */ 3475 if (ip + 4 > iend) return ERROR(srcSize_wrong); /* min : header byte + all 3 are "raw", hence no header, but at least xxLog bits per type */ 3476 { U32 const LLtype = *ip >> 6; 3477 U32 const OFtype = (*ip >> 4) & 3; 3478 U32 const MLtype = (*ip >> 2) & 3; 3479 ip++; 3480 3481 /* Build DTables */ 3482 { size_t const llhSize = ZSTDv07_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable); 3483 if (ZSTDv07_isError(llhSize)) return ERROR(corruption_detected); 3484 ip += llhSize; 3485 } 3486 { size_t const ofhSize = ZSTDv07_buildSeqTable(DTableOffb, OFtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable); 3487 if (ZSTDv07_isError(ofhSize)) return ERROR(corruption_detected); 3488 ip += ofhSize; 3489 } 3490 { size_t const mlhSize = ZSTDv07_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable); 3491 if (ZSTDv07_isError(mlhSize)) return ERROR(corruption_detected); 3492 ip += mlhSize; 3493 } } 3494 3495 return ip-istart; 3496} 3497 3498 3499typedef struct { 3500 size_t litLength; 3501 size_t matchLength; 3502 size_t offset; 3503} seq_t; 3504 3505typedef struct { 3506 BITv07_DStream_t DStream; 3507 FSEv07_DState_t stateLL; 3508 FSEv07_DState_t stateOffb; 3509 FSEv07_DState_t stateML; 3510 size_t prevOffset[ZSTDv07_REP_INIT]; 3511} seqState_t; 3512 3513 3514static seq_t ZSTDv07_decodeSequence(seqState_t* seqState) 3515{ 3516 seq_t seq; 3517 3518 U32 const llCode = FSEv07_peekSymbol(&(seqState->stateLL)); 3519 U32 const mlCode = FSEv07_peekSymbol(&(seqState->stateML)); 3520 U32 const ofCode = FSEv07_peekSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */ 3521 3522 U32 const llBits = LL_bits[llCode]; 3523 U32 const mlBits = ML_bits[mlCode]; 3524 U32 const ofBits = ofCode; 3525 U32 const totalBits = llBits+mlBits+ofBits; 3526 3527 static const U32 LL_base[MaxLL+1] = { 3528 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 3529 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 3530 0x2000, 0x4000, 0x8000, 0x10000 }; 3531 3532 static const U32 ML_base[MaxML+1] = { 3533 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 3534 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 3535 35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803, 3536 0x1003, 0x2003, 0x4003, 0x8003, 0x10003 }; 3537 3538 static const U32 OF_base[MaxOff+1] = { 3539 0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D, 3540 0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD, 3541 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD, 3542 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD }; 3543 3544 /* sequence */ 3545 { size_t offset; 3546 if (!ofCode) 3547 offset = 0; 3548 else { 3549 offset = OF_base[ofCode] + BITv07_readBits(&(seqState->DStream), ofBits); /* <= (ZSTDv07_WINDOWLOG_MAX-1) bits */ 3550 if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream)); 3551 } 3552 3553 if (ofCode <= 1) { 3554 if ((llCode == 0) & (offset <= 1)) offset = 1-offset; 3555 if (offset) { 3556 size_t const temp = seqState->prevOffset[offset]; 3557 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1]; 3558 seqState->prevOffset[1] = seqState->prevOffset[0]; 3559 seqState->prevOffset[0] = offset = temp; 3560 } else { 3561 offset = seqState->prevOffset[0]; 3562 } 3563 } else { 3564 seqState->prevOffset[2] = seqState->prevOffset[1]; 3565 seqState->prevOffset[1] = seqState->prevOffset[0]; 3566 seqState->prevOffset[0] = offset; 3567 } 3568 seq.offset = offset; 3569 } 3570 3571 seq.matchLength = ML_base[mlCode] + ((mlCode>31) ? BITv07_readBits(&(seqState->DStream), mlBits) : 0); /* <= 16 bits */ 3572 if (MEM_32bits() && (mlBits+llBits>24)) BITv07_reloadDStream(&(seqState->DStream)); 3573 3574 seq.litLength = LL_base[llCode] + ((llCode>15) ? BITv07_readBits(&(seqState->DStream), llBits) : 0); /* <= 16 bits */ 3575 if (MEM_32bits() || 3576 (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BITv07_reloadDStream(&(seqState->DStream)); 3577 3578 /* ANS state update */ 3579 FSEv07_updateState(&(seqState->stateLL), &(seqState->DStream)); /* <= 9 bits */ 3580 FSEv07_updateState(&(seqState->stateML), &(seqState->DStream)); /* <= 9 bits */ 3581 if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream)); /* <= 18 bits */ 3582 FSEv07_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <= 8 bits */ 3583 3584 return seq; 3585} 3586 3587 3588static 3589size_t ZSTDv07_execSequence(BYTE* op, 3590 BYTE* const oend, seq_t sequence, 3591 const BYTE** litPtr, const BYTE* const litLimit, 3592 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd) 3593{ 3594 BYTE* const oLitEnd = op + sequence.litLength; 3595 size_t const sequenceLength = sequence.litLength + sequence.matchLength; 3596 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */ 3597 BYTE* const oend_w = oend-WILDCOPY_OVERLENGTH; 3598 const BYTE* const iLitEnd = *litPtr + sequence.litLength; 3599 const BYTE* match = oLitEnd - sequence.offset; 3600 3601 /* check */ 3602 if ((oLitEnd>oend_w) | (oMatchEnd>oend)) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */ 3603 if (iLitEnd > litLimit) return ERROR(corruption_detected); /* over-read beyond lit buffer */ 3604 3605 /* copy Literals */ 3606 ZSTDv07_wildcopy(op, *litPtr, sequence.litLength); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */ 3607 op = oLitEnd; 3608 *litPtr = iLitEnd; /* update for next sequence */ 3609 3610 /* copy Match */ 3611 if (sequence.offset > (size_t)(oLitEnd - base)) { 3612 /* offset beyond prefix */ 3613 if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected); 3614 match = dictEnd - (base-match); 3615 if (match + sequence.matchLength <= dictEnd) { 3616 memmove(oLitEnd, match, sequence.matchLength); 3617 return sequenceLength; 3618 } 3619 /* span extDict & currentPrefixSegment */ 3620 { size_t const length1 = dictEnd - match; 3621 memmove(oLitEnd, match, length1); 3622 op = oLitEnd + length1; 3623 sequence.matchLength -= length1; 3624 match = base; 3625 if (op > oend_w || sequence.matchLength < MINMATCH) { 3626 while (op < oMatchEnd) *op++ = *match++; 3627 return sequenceLength; 3628 } 3629 } } 3630 /* Requirement: op <= oend_w */ 3631 3632 /* match within prefix */ 3633 if (sequence.offset < 8) { 3634 /* close range match, overlap */ 3635 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */ 3636 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */ 3637 int const sub2 = dec64table[sequence.offset]; 3638 op[0] = match[0]; 3639 op[1] = match[1]; 3640 op[2] = match[2]; 3641 op[3] = match[3]; 3642 match += dec32table[sequence.offset]; 3643 ZSTDv07_copy4(op+4, match); 3644 match -= sub2; 3645 } else { 3646 ZSTDv07_copy8(op, match); 3647 } 3648 op += 8; match += 8; 3649 3650 if (oMatchEnd > oend-(16-MINMATCH)) { 3651 if (op < oend_w) { 3652 ZSTDv07_wildcopy(op, match, oend_w - op); 3653 match += oend_w - op; 3654 op = oend_w; 3655 } 3656 while (op < oMatchEnd) *op++ = *match++; 3657 } else { 3658 ZSTDv07_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */ 3659 } 3660 return sequenceLength; 3661} 3662 3663 3664static size_t ZSTDv07_decompressSequences( 3665 ZSTDv07_DCtx* dctx, 3666 void* dst, size_t maxDstSize, 3667 const void* seqStart, size_t seqSize) 3668{ 3669 const BYTE* ip = (const BYTE*)seqStart; 3670 const BYTE* const iend = ip + seqSize; 3671 BYTE* const ostart = (BYTE*)dst; 3672 BYTE* const oend = ostart + maxDstSize; 3673 BYTE* op = ostart; 3674 const BYTE* litPtr = dctx->litPtr; 3675 const BYTE* const litEnd = litPtr + dctx->litSize; 3676 FSEv07_DTable* DTableLL = dctx->LLTable; 3677 FSEv07_DTable* DTableML = dctx->MLTable; 3678 FSEv07_DTable* DTableOffb = dctx->OffTable; 3679 const BYTE* const base = (const BYTE*) (dctx->base); 3680 const BYTE* const vBase = (const BYTE*) (dctx->vBase); 3681 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd); 3682 int nbSeq; 3683 3684 /* Build Decoding Tables */ 3685 { size_t const seqHSize = ZSTDv07_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->fseEntropy, ip, seqSize); 3686 if (ZSTDv07_isError(seqHSize)) return seqHSize; 3687 ip += seqHSize; 3688 } 3689 3690 /* Regen sequences */ 3691 if (nbSeq) { 3692 seqState_t seqState; 3693 dctx->fseEntropy = 1; 3694 { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) seqState.prevOffset[i] = dctx->rep[i]; } 3695 { size_t const errorCode = BITv07_initDStream(&(seqState.DStream), ip, iend-ip); 3696 if (ERR_isError(errorCode)) return ERROR(corruption_detected); } 3697 FSEv07_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL); 3698 FSEv07_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb); 3699 FSEv07_initDState(&(seqState.stateML), &(seqState.DStream), DTableML); 3700 3701 for ( ; (BITv07_reloadDStream(&(seqState.DStream)) <= BITv07_DStream_completed) && nbSeq ; ) { 3702 nbSeq--; 3703 { seq_t const sequence = ZSTDv07_decodeSequence(&seqState); 3704 size_t const oneSeqSize = ZSTDv07_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd); 3705 if (ZSTDv07_isError(oneSeqSize)) return oneSeqSize; 3706 op += oneSeqSize; 3707 } } 3708 3709 /* check if reached exact end */ 3710 if (nbSeq) return ERROR(corruption_detected); 3711 /* save reps for next block */ 3712 { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) dctx->rep[i] = (U32)(seqState.prevOffset[i]); } 3713 } 3714 3715 /* last literal segment */ 3716 { size_t const lastLLSize = litEnd - litPtr; 3717 /* if (litPtr > litEnd) return ERROR(corruption_detected); */ /* too many literals already used */ 3718 if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall); 3719 if (lastLLSize > 0) { 3720 memcpy(op, litPtr, lastLLSize); 3721 op += lastLLSize; 3722 } 3723 } 3724 3725 return op-ostart; 3726} 3727 3728 3729static void ZSTDv07_checkContinuity(ZSTDv07_DCtx* dctx, const void* dst) 3730{ 3731 if (dst != dctx->previousDstEnd) { /* not contiguous */ 3732 dctx->dictEnd = dctx->previousDstEnd; 3733 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); 3734 dctx->base = dst; 3735 dctx->previousDstEnd = dst; 3736 } 3737} 3738 3739 3740static size_t ZSTDv07_decompressBlock_internal(ZSTDv07_DCtx* dctx, 3741 void* dst, size_t dstCapacity, 3742 const void* src, size_t srcSize) 3743{ /* blockType == blockCompressed */ 3744 const BYTE* ip = (const BYTE*)src; 3745 3746 if (srcSize >= ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(srcSize_wrong); 3747 3748 /* Decode literals sub-block */ 3749 { size_t const litCSize = ZSTDv07_decodeLiteralsBlock(dctx, src, srcSize); 3750 if (ZSTDv07_isError(litCSize)) return litCSize; 3751 ip += litCSize; 3752 srcSize -= litCSize; 3753 } 3754 return ZSTDv07_decompressSequences(dctx, dst, dstCapacity, ip, srcSize); 3755} 3756 3757 3758size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx* dctx, 3759 void* dst, size_t dstCapacity, 3760 const void* src, size_t srcSize) 3761{ 3762 size_t dSize; 3763 ZSTDv07_checkContinuity(dctx, dst); 3764 dSize = ZSTDv07_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize); 3765 dctx->previousDstEnd = (char*)dst + dSize; 3766 return dSize; 3767} 3768 3769 3770/** ZSTDv07_insertBlock() : 3771 insert `src` block into `dctx` history. Useful to track uncompressed blocks. */ 3772ZSTDLIBv07_API size_t ZSTDv07_insertBlock(ZSTDv07_DCtx* dctx, const void* blockStart, size_t blockSize) 3773{ 3774 ZSTDv07_checkContinuity(dctx, blockStart); 3775 dctx->previousDstEnd = (const char*)blockStart + blockSize; 3776 return blockSize; 3777} 3778 3779 3780static size_t ZSTDv07_generateNxBytes(void* dst, size_t dstCapacity, BYTE byte, size_t length) 3781{ 3782 if (length > dstCapacity) return ERROR(dstSize_tooSmall); 3783 if (length > 0) { 3784 memset(dst, byte, length); 3785 } 3786 return length; 3787} 3788 3789 3790/*! ZSTDv07_decompressFrame() : 3791* `dctx` must be properly initialized */ 3792static size_t ZSTDv07_decompressFrame(ZSTDv07_DCtx* dctx, 3793 void* dst, size_t dstCapacity, 3794 const void* src, size_t srcSize) 3795{ 3796 const BYTE* ip = (const BYTE*)src; 3797 const BYTE* const iend = ip + srcSize; 3798 BYTE* const ostart = (BYTE*)dst; 3799 BYTE* const oend = ostart + dstCapacity; 3800 BYTE* op = ostart; 3801 size_t remainingSize = srcSize; 3802 3803 /* check */ 3804 if (srcSize < ZSTDv07_frameHeaderSize_min+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong); 3805 3806 /* Frame Header */ 3807 { size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min); 3808 if (ZSTDv07_isError(frameHeaderSize)) return frameHeaderSize; 3809 if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong); 3810 if (ZSTDv07_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected); 3811 ip += frameHeaderSize; remainingSize -= frameHeaderSize; 3812 } 3813 3814 /* Loop on each block */ 3815 while (1) { 3816 size_t decodedSize; 3817 blockProperties_t blockProperties; 3818 size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, iend-ip, &blockProperties); 3819 if (ZSTDv07_isError(cBlockSize)) return cBlockSize; 3820 3821 ip += ZSTDv07_blockHeaderSize; 3822 remainingSize -= ZSTDv07_blockHeaderSize; 3823 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); 3824 3825 switch(blockProperties.blockType) 3826 { 3827 case bt_compressed: 3828 decodedSize = ZSTDv07_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize); 3829 break; 3830 case bt_raw : 3831 decodedSize = ZSTDv07_copyRawBlock(op, oend-op, ip, cBlockSize); 3832 break; 3833 case bt_rle : 3834 decodedSize = ZSTDv07_generateNxBytes(op, oend-op, *ip, blockProperties.origSize); 3835 break; 3836 case bt_end : 3837 /* end of frame */ 3838 if (remainingSize) return ERROR(srcSize_wrong); 3839 decodedSize = 0; 3840 break; 3841 default: 3842 return ERROR(GENERIC); /* impossible */ 3843 } 3844 if (blockProperties.blockType == bt_end) break; /* bt_end */ 3845 3846 if (ZSTDv07_isError(decodedSize)) return decodedSize; 3847 if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, op, decodedSize); 3848 op += decodedSize; 3849 ip += cBlockSize; 3850 remainingSize -= cBlockSize; 3851 } 3852 3853 return op-ostart; 3854} 3855 3856 3857/*! ZSTDv07_decompress_usingPreparedDCtx() : 3858* Same as ZSTDv07_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded. 3859* It avoids reloading the dictionary each time. 3860* `preparedDCtx` must have been properly initialized using ZSTDv07_decompressBegin_usingDict(). 3861* Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */ 3862static size_t ZSTDv07_decompress_usingPreparedDCtx(ZSTDv07_DCtx* dctx, const ZSTDv07_DCtx* refDCtx, 3863 void* dst, size_t dstCapacity, 3864 const void* src, size_t srcSize) 3865{ 3866 ZSTDv07_copyDCtx(dctx, refDCtx); 3867 ZSTDv07_checkContinuity(dctx, dst); 3868 return ZSTDv07_decompressFrame(dctx, dst, dstCapacity, src, srcSize); 3869} 3870 3871 3872size_t ZSTDv07_decompress_usingDict(ZSTDv07_DCtx* dctx, 3873 void* dst, size_t dstCapacity, 3874 const void* src, size_t srcSize, 3875 const void* dict, size_t dictSize) 3876{ 3877 ZSTDv07_decompressBegin_usingDict(dctx, dict, dictSize); 3878 ZSTDv07_checkContinuity(dctx, dst); 3879 return ZSTDv07_decompressFrame(dctx, dst, dstCapacity, src, srcSize); 3880} 3881 3882 3883size_t ZSTDv07_decompressDCtx(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize) 3884{ 3885 return ZSTDv07_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0); 3886} 3887 3888 3889size_t ZSTDv07_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize) 3890{ 3891#if defined(ZSTDv07_HEAPMODE) && (ZSTDv07_HEAPMODE==1) 3892 size_t regenSize; 3893 ZSTDv07_DCtx* const dctx = ZSTDv07_createDCtx(); 3894 if (dctx==NULL) return ERROR(memory_allocation); 3895 regenSize = ZSTDv07_decompressDCtx(dctx, dst, dstCapacity, src, srcSize); 3896 ZSTDv07_freeDCtx(dctx); 3897 return regenSize; 3898#else /* stack mode */ 3899 ZSTDv07_DCtx dctx; 3900 return ZSTDv07_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize); 3901#endif 3902} 3903 3904/* ZSTD_errorFrameSizeInfoLegacy() : 3905 assumes `cSize` and `dBound` are _not_ NULL */ 3906static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret) 3907{ 3908 *cSize = ret; 3909 *dBound = ZSTD_CONTENTSIZE_ERROR; 3910} 3911 3912void ZSTDv07_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound) 3913{ 3914 const BYTE* ip = (const BYTE*)src; 3915 size_t remainingSize = srcSize; 3916 size_t nbBlocks = 0; 3917 3918 /* check */ 3919 if (srcSize < ZSTDv07_frameHeaderSize_min+ZSTDv07_blockHeaderSize) { 3920 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 3921 return; 3922 } 3923 3924 /* Frame Header */ 3925 { size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, srcSize); 3926 if (ZSTDv07_isError(frameHeaderSize)) { 3927 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, frameHeaderSize); 3928 return; 3929 } 3930 if (MEM_readLE32(src) != ZSTDv07_MAGICNUMBER) { 3931 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown)); 3932 return; 3933 } 3934 if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) { 3935 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 3936 return; 3937 } 3938 ip += frameHeaderSize; remainingSize -= frameHeaderSize; 3939 } 3940 3941 /* Loop on each block */ 3942 while (1) { 3943 blockProperties_t blockProperties; 3944 size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, remainingSize, &blockProperties); 3945 if (ZSTDv07_isError(cBlockSize)) { 3946 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize); 3947 return; 3948 } 3949 3950 ip += ZSTDv07_blockHeaderSize; 3951 remainingSize -= ZSTDv07_blockHeaderSize; 3952 3953 if (blockProperties.blockType == bt_end) break; 3954 3955 if (cBlockSize > remainingSize) { 3956 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 3957 return; 3958 } 3959 3960 ip += cBlockSize; 3961 remainingSize -= cBlockSize; 3962 nbBlocks++; 3963 } 3964 3965 *cSize = ip - (const BYTE*)src; 3966 *dBound = nbBlocks * ZSTDv07_BLOCKSIZE_ABSOLUTEMAX; 3967} 3968 3969/*_****************************** 3970* Streaming Decompression API 3971********************************/ 3972size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx* dctx) 3973{ 3974 return dctx->expected; 3975} 3976 3977int ZSTDv07_isSkipFrame(ZSTDv07_DCtx* dctx) 3978{ 3979 return dctx->stage == ZSTDds_skipFrame; 3980} 3981 3982/** ZSTDv07_decompressContinue() : 3983* @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity) 3984* or an error code, which can be tested using ZSTDv07_isError() */ 3985size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize) 3986{ 3987 /* Sanity check */ 3988 if (srcSize != dctx->expected) return ERROR(srcSize_wrong); 3989 if (dstCapacity) ZSTDv07_checkContinuity(dctx, dst); 3990 3991 switch (dctx->stage) 3992 { 3993 case ZSTDds_getFrameHeaderSize : 3994 if (srcSize != ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */ 3995 if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTDv07_MAGIC_SKIPPABLE_START) { 3996 memcpy(dctx->headerBuffer, src, ZSTDv07_frameHeaderSize_min); 3997 dctx->expected = ZSTDv07_skippableHeaderSize - ZSTDv07_frameHeaderSize_min; /* magic number + skippable frame length */ 3998 dctx->stage = ZSTDds_decodeSkippableHeader; 3999 return 0; 4000 } 4001 dctx->headerSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min); 4002 if (ZSTDv07_isError(dctx->headerSize)) return dctx->headerSize; 4003 memcpy(dctx->headerBuffer, src, ZSTDv07_frameHeaderSize_min); 4004 if (dctx->headerSize > ZSTDv07_frameHeaderSize_min) { 4005 dctx->expected = dctx->headerSize - ZSTDv07_frameHeaderSize_min; 4006 dctx->stage = ZSTDds_decodeFrameHeader; 4007 return 0; 4008 } 4009 dctx->expected = 0; /* not necessary to copy more */ 4010 /* fall-through */ 4011 case ZSTDds_decodeFrameHeader: 4012 { size_t result; 4013 memcpy(dctx->headerBuffer + ZSTDv07_frameHeaderSize_min, src, dctx->expected); 4014 result = ZSTDv07_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize); 4015 if (ZSTDv07_isError(result)) return result; 4016 dctx->expected = ZSTDv07_blockHeaderSize; 4017 dctx->stage = ZSTDds_decodeBlockHeader; 4018 return 0; 4019 } 4020 case ZSTDds_decodeBlockHeader: 4021 { blockProperties_t bp; 4022 size_t const cBlockSize = ZSTDv07_getcBlockSize(src, ZSTDv07_blockHeaderSize, &bp); 4023 if (ZSTDv07_isError(cBlockSize)) return cBlockSize; 4024 if (bp.blockType == bt_end) { 4025 if (dctx->fParams.checksumFlag) { 4026 U64 const h64 = XXH64_digest(&dctx->xxhState); 4027 U32 const h32 = (U32)(h64>>11) & ((1<<22)-1); 4028 const BYTE* const ip = (const BYTE*)src; 4029 U32 const check32 = ip[2] + (ip[1] << 8) + ((ip[0] & 0x3F) << 16); 4030 if (check32 != h32) return ERROR(checksum_wrong); 4031 } 4032 dctx->expected = 0; 4033 dctx->stage = ZSTDds_getFrameHeaderSize; 4034 } else { 4035 dctx->expected = cBlockSize; 4036 dctx->bType = bp.blockType; 4037 dctx->stage = ZSTDds_decompressBlock; 4038 } 4039 return 0; 4040 } 4041 case ZSTDds_decompressBlock: 4042 { size_t rSize; 4043 switch(dctx->bType) 4044 { 4045 case bt_compressed: 4046 rSize = ZSTDv07_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize); 4047 break; 4048 case bt_raw : 4049 rSize = ZSTDv07_copyRawBlock(dst, dstCapacity, src, srcSize); 4050 break; 4051 case bt_rle : 4052 return ERROR(GENERIC); /* not yet handled */ 4053 break; 4054 case bt_end : /* should never happen (filtered at phase 1) */ 4055 rSize = 0; 4056 break; 4057 default: 4058 return ERROR(GENERIC); /* impossible */ 4059 } 4060 dctx->stage = ZSTDds_decodeBlockHeader; 4061 dctx->expected = ZSTDv07_blockHeaderSize; 4062 dctx->previousDstEnd = (char*)dst + rSize; 4063 if (ZSTDv07_isError(rSize)) return rSize; 4064 if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, dst, rSize); 4065 return rSize; 4066 } 4067 case ZSTDds_decodeSkippableHeader: 4068 { memcpy(dctx->headerBuffer + ZSTDv07_frameHeaderSize_min, src, dctx->expected); 4069 dctx->expected = MEM_readLE32(dctx->headerBuffer + 4); 4070 dctx->stage = ZSTDds_skipFrame; 4071 return 0; 4072 } 4073 case ZSTDds_skipFrame: 4074 { dctx->expected = 0; 4075 dctx->stage = ZSTDds_getFrameHeaderSize; 4076 return 0; 4077 } 4078 default: 4079 return ERROR(GENERIC); /* impossible */ 4080 } 4081} 4082 4083 4084static size_t ZSTDv07_refDictContent(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize) 4085{ 4086 dctx->dictEnd = dctx->previousDstEnd; 4087 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); 4088 dctx->base = dict; 4089 dctx->previousDstEnd = (const char*)dict + dictSize; 4090 return 0; 4091} 4092 4093static size_t ZSTDv07_loadEntropy(ZSTDv07_DCtx* dctx, const void* const dict, size_t const dictSize) 4094{ 4095 const BYTE* dictPtr = (const BYTE*)dict; 4096 const BYTE* const dictEnd = dictPtr + dictSize; 4097 4098 { size_t const hSize = HUFv07_readDTableX4(dctx->hufTable, dict, dictSize); 4099 if (HUFv07_isError(hSize)) return ERROR(dictionary_corrupted); 4100 dictPtr += hSize; 4101 } 4102 4103 { short offcodeNCount[MaxOff+1]; 4104 U32 offcodeMaxValue=MaxOff, offcodeLog; 4105 size_t const offcodeHeaderSize = FSEv07_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr); 4106 if (FSEv07_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted); 4107 if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted); 4108 { size_t const errorCode = FSEv07_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog); 4109 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); } 4110 dictPtr += offcodeHeaderSize; 4111 } 4112 4113 { short matchlengthNCount[MaxML+1]; 4114 unsigned matchlengthMaxValue = MaxML, matchlengthLog; 4115 size_t const matchlengthHeaderSize = FSEv07_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr); 4116 if (FSEv07_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted); 4117 if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted); 4118 { size_t const errorCode = FSEv07_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog); 4119 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); } 4120 dictPtr += matchlengthHeaderSize; 4121 } 4122 4123 { short litlengthNCount[MaxLL+1]; 4124 unsigned litlengthMaxValue = MaxLL, litlengthLog; 4125 size_t const litlengthHeaderSize = FSEv07_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr); 4126 if (FSEv07_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted); 4127 if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted); 4128 { size_t const errorCode = FSEv07_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog); 4129 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); } 4130 dictPtr += litlengthHeaderSize; 4131 } 4132 4133 if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted); 4134 dctx->rep[0] = MEM_readLE32(dictPtr+0); if (dctx->rep[0] == 0 || dctx->rep[0] >= dictSize) return ERROR(dictionary_corrupted); 4135 dctx->rep[1] = MEM_readLE32(dictPtr+4); if (dctx->rep[1] == 0 || dctx->rep[1] >= dictSize) return ERROR(dictionary_corrupted); 4136 dctx->rep[2] = MEM_readLE32(dictPtr+8); if (dctx->rep[2] == 0 || dctx->rep[2] >= dictSize) return ERROR(dictionary_corrupted); 4137 dictPtr += 12; 4138 4139 dctx->litEntropy = dctx->fseEntropy = 1; 4140 return dictPtr - (const BYTE*)dict; 4141} 4142 4143static size_t ZSTDv07_decompress_insertDictionary(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize) 4144{ 4145 if (dictSize < 8) return ZSTDv07_refDictContent(dctx, dict, dictSize); 4146 { U32 const magic = MEM_readLE32(dict); 4147 if (magic != ZSTDv07_DICT_MAGIC) { 4148 return ZSTDv07_refDictContent(dctx, dict, dictSize); /* pure content mode */ 4149 } } 4150 dctx->dictID = MEM_readLE32((const char*)dict + 4); 4151 4152 /* load entropy tables */ 4153 dict = (const char*)dict + 8; 4154 dictSize -= 8; 4155 { size_t const eSize = ZSTDv07_loadEntropy(dctx, dict, dictSize); 4156 if (ZSTDv07_isError(eSize)) return ERROR(dictionary_corrupted); 4157 dict = (const char*)dict + eSize; 4158 dictSize -= eSize; 4159 } 4160 4161 /* reference dictionary content */ 4162 return ZSTDv07_refDictContent(dctx, dict, dictSize); 4163} 4164 4165 4166size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize) 4167{ 4168 { size_t const errorCode = ZSTDv07_decompressBegin(dctx); 4169 if (ZSTDv07_isError(errorCode)) return errorCode; } 4170 4171 if (dict && dictSize) { 4172 size_t const errorCode = ZSTDv07_decompress_insertDictionary(dctx, dict, dictSize); 4173 if (ZSTDv07_isError(errorCode)) return ERROR(dictionary_corrupted); 4174 } 4175 4176 return 0; 4177} 4178 4179 4180struct ZSTDv07_DDict_s { 4181 void* dict; 4182 size_t dictSize; 4183 ZSTDv07_DCtx* refContext; 4184}; /* typedef'd tp ZSTDv07_CDict within zstd.h */ 4185 4186static ZSTDv07_DDict* ZSTDv07_createDDict_advanced(const void* dict, size_t dictSize, ZSTDv07_customMem customMem) 4187{ 4188 if (!customMem.customAlloc && !customMem.customFree) 4189 customMem = defaultCustomMem; 4190 4191 if (!customMem.customAlloc || !customMem.customFree) 4192 return NULL; 4193 4194 { ZSTDv07_DDict* const ddict = (ZSTDv07_DDict*) customMem.customAlloc(customMem.opaque, sizeof(*ddict)); 4195 void* const dictContent = customMem.customAlloc(customMem.opaque, dictSize); 4196 ZSTDv07_DCtx* const dctx = ZSTDv07_createDCtx_advanced(customMem); 4197 4198 if (!dictContent || !ddict || !dctx) { 4199 customMem.customFree(customMem.opaque, dictContent); 4200 customMem.customFree(customMem.opaque, ddict); 4201 customMem.customFree(customMem.opaque, dctx); 4202 return NULL; 4203 } 4204 4205 memcpy(dictContent, dict, dictSize); 4206 { size_t const errorCode = ZSTDv07_decompressBegin_usingDict(dctx, dictContent, dictSize); 4207 if (ZSTDv07_isError(errorCode)) { 4208 customMem.customFree(customMem.opaque, dictContent); 4209 customMem.customFree(customMem.opaque, ddict); 4210 customMem.customFree(customMem.opaque, dctx); 4211 return NULL; 4212 } } 4213 4214 ddict->dict = dictContent; 4215 ddict->dictSize = dictSize; 4216 ddict->refContext = dctx; 4217 return ddict; 4218 } 4219} 4220 4221/*! ZSTDv07_createDDict() : 4222* Create a digested dictionary, ready to start decompression without startup delay. 4223* `dict` can be released after `ZSTDv07_DDict` creation */ 4224ZSTDv07_DDict* ZSTDv07_createDDict(const void* dict, size_t dictSize) 4225{ 4226 ZSTDv07_customMem const allocator = { NULL, NULL, NULL }; 4227 return ZSTDv07_createDDict_advanced(dict, dictSize, allocator); 4228} 4229 4230size_t ZSTDv07_freeDDict(ZSTDv07_DDict* ddict) 4231{ 4232 ZSTDv07_freeFunction const cFree = ddict->refContext->customMem.customFree; 4233 void* const opaque = ddict->refContext->customMem.opaque; 4234 ZSTDv07_freeDCtx(ddict->refContext); 4235 cFree(opaque, ddict->dict); 4236 cFree(opaque, ddict); 4237 return 0; 4238} 4239 4240/*! ZSTDv07_decompress_usingDDict() : 4241* Decompression using a pre-digested Dictionary 4242* Use dictionary without significant overhead. */ 4243ZSTDLIBv07_API size_t ZSTDv07_decompress_usingDDict(ZSTDv07_DCtx* dctx, 4244 void* dst, size_t dstCapacity, 4245 const void* src, size_t srcSize, 4246 const ZSTDv07_DDict* ddict) 4247{ 4248 return ZSTDv07_decompress_usingPreparedDCtx(dctx, ddict->refContext, 4249 dst, dstCapacity, 4250 src, srcSize); 4251} 4252/* 4253 Buffered version of Zstd compression library 4254 Copyright (C) 2015-2016, Yann Collet. 4255 4256 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 4257 4258 Redistribution and use in source and binary forms, with or without 4259 modification, are permitted provided that the following conditions are 4260 met: 4261 * Redistributions of source code must retain the above copyright 4262 notice, this list of conditions and the following disclaimer. 4263 * Redistributions in binary form must reproduce the above 4264 copyright notice, this list of conditions and the following disclaimer 4265 in the documentation and/or other materials provided with the 4266 distribution. 4267 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 4268 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 4269 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 4270 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 4271 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 4272 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 4273 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 4274 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 4275 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 4276 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 4277 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 4278 4279 You can contact the author at : 4280 - zstd homepage : http://www.zstd.net/ 4281*/ 4282 4283 4284 4285/*-*************************************************************************** 4286* Streaming decompression howto 4287* 4288* A ZBUFFv07_DCtx object is required to track streaming operations. 4289* Use ZBUFFv07_createDCtx() and ZBUFFv07_freeDCtx() to create/release resources. 4290* Use ZBUFFv07_decompressInit() to start a new decompression operation, 4291* or ZBUFFv07_decompressInitDictionary() if decompression requires a dictionary. 4292* Note that ZBUFFv07_DCtx objects can be re-init multiple times. 4293* 4294* Use ZBUFFv07_decompressContinue() repetitively to consume your input. 4295* *srcSizePtr and *dstCapacityPtr can be any size. 4296* The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr. 4297* Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again. 4298* The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst. 4299* @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency), 4300* or 0 when a frame is completely decoded, 4301* or an error code, which can be tested using ZBUFFv07_isError(). 4302* 4303* Hint : recommended buffer sizes (not compulsory) : ZBUFFv07_recommendedDInSize() and ZBUFFv07_recommendedDOutSize() 4304* output : ZBUFFv07_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded. 4305* input : ZBUFFv07_recommendedDInSize == 128KB + 3; 4306* just follow indications from ZBUFFv07_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 . 4307* *******************************************************************************/ 4308 4309typedef enum { ZBUFFds_init, ZBUFFds_loadHeader, 4310 ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFFv07_dStage; 4311 4312/* *** Resource management *** */ 4313struct ZBUFFv07_DCtx_s { 4314 ZSTDv07_DCtx* zd; 4315 ZSTDv07_frameParams fParams; 4316 ZBUFFv07_dStage stage; 4317 char* inBuff; 4318 size_t inBuffSize; 4319 size_t inPos; 4320 char* outBuff; 4321 size_t outBuffSize; 4322 size_t outStart; 4323 size_t outEnd; 4324 size_t blockSize; 4325 BYTE headerBuffer[ZSTDv07_FRAMEHEADERSIZE_MAX]; 4326 size_t lhSize; 4327 ZSTDv07_customMem customMem; 4328}; /* typedef'd to ZBUFFv07_DCtx within "zstd_buffered.h" */ 4329 4330ZSTDLIBv07_API ZBUFFv07_DCtx* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem); 4331 4332ZBUFFv07_DCtx* ZBUFFv07_createDCtx(void) 4333{ 4334 return ZBUFFv07_createDCtx_advanced(defaultCustomMem); 4335} 4336 4337ZBUFFv07_DCtx* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem) 4338{ 4339 ZBUFFv07_DCtx* zbd; 4340 4341 if (!customMem.customAlloc && !customMem.customFree) 4342 customMem = defaultCustomMem; 4343 4344 if (!customMem.customAlloc || !customMem.customFree) 4345 return NULL; 4346 4347 zbd = (ZBUFFv07_DCtx*)customMem.customAlloc(customMem.opaque, sizeof(ZBUFFv07_DCtx)); 4348 if (zbd==NULL) return NULL; 4349 memset(zbd, 0, sizeof(ZBUFFv07_DCtx)); 4350 memcpy(&zbd->customMem, &customMem, sizeof(ZSTDv07_customMem)); 4351 zbd->zd = ZSTDv07_createDCtx_advanced(customMem); 4352 if (zbd->zd == NULL) { ZBUFFv07_freeDCtx(zbd); return NULL; } 4353 zbd->stage = ZBUFFds_init; 4354 return zbd; 4355} 4356 4357size_t ZBUFFv07_freeDCtx(ZBUFFv07_DCtx* zbd) 4358{ 4359 if (zbd==NULL) return 0; /* support free on null */ 4360 ZSTDv07_freeDCtx(zbd->zd); 4361 if (zbd->inBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff); 4362 if (zbd->outBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff); 4363 zbd->customMem.customFree(zbd->customMem.opaque, zbd); 4364 return 0; 4365} 4366 4367 4368/* *** Initialization *** */ 4369 4370size_t ZBUFFv07_decompressInitDictionary(ZBUFFv07_DCtx* zbd, const void* dict, size_t dictSize) 4371{ 4372 zbd->stage = ZBUFFds_loadHeader; 4373 zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0; 4374 return ZSTDv07_decompressBegin_usingDict(zbd->zd, dict, dictSize); 4375} 4376 4377size_t ZBUFFv07_decompressInit(ZBUFFv07_DCtx* zbd) 4378{ 4379 return ZBUFFv07_decompressInitDictionary(zbd, NULL, 0); 4380} 4381 4382 4383/* internal util function */ 4384MEM_STATIC size_t ZBUFFv07_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize) 4385{ 4386 size_t const length = MIN(dstCapacity, srcSize); 4387 if (length > 0) { 4388 memcpy(dst, src, length); 4389 } 4390 return length; 4391} 4392 4393 4394/* *** Decompression *** */ 4395 4396size_t ZBUFFv07_decompressContinue(ZBUFFv07_DCtx* zbd, 4397 void* dst, size_t* dstCapacityPtr, 4398 const void* src, size_t* srcSizePtr) 4399{ 4400 const char* const istart = (const char*)src; 4401 const char* const iend = istart + *srcSizePtr; 4402 const char* ip = istart; 4403 char* const ostart = (char*)dst; 4404 char* const oend = ostart + *dstCapacityPtr; 4405 char* op = ostart; 4406 U32 notDone = 1; 4407 4408 while (notDone) { 4409 switch(zbd->stage) 4410 { 4411 case ZBUFFds_init : 4412 return ERROR(init_missing); 4413 4414 case ZBUFFds_loadHeader : 4415 { size_t const hSize = ZSTDv07_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize); 4416 if (ZSTDv07_isError(hSize)) return hSize; 4417 if (hSize != 0) { 4418 size_t const toLoad = hSize - zbd->lhSize; /* if hSize!=0, hSize > zbd->lhSize */ 4419 if (toLoad > (size_t)(iend-ip)) { /* not enough input to load full header */ 4420 memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip); 4421 zbd->lhSize += iend-ip; 4422 *dstCapacityPtr = 0; 4423 return (hSize - zbd->lhSize) + ZSTDv07_blockHeaderSize; /* remaining header bytes + next block header */ 4424 } 4425 memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad; 4426 break; 4427 } } 4428 4429 /* Consume header */ 4430 { size_t const h1Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd); /* == ZSTDv07_frameHeaderSize_min */ 4431 size_t const h1Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size); 4432 if (ZSTDv07_isError(h1Result)) return h1Result; 4433 if (h1Size < zbd->lhSize) { /* long header */ 4434 size_t const h2Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd); 4435 size_t const h2Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size); 4436 if (ZSTDv07_isError(h2Result)) return h2Result; 4437 } } 4438 4439 zbd->fParams.windowSize = MAX(zbd->fParams.windowSize, 1U << ZSTDv07_WINDOWLOG_ABSOLUTEMIN); 4440 4441 /* Frame header instruct buffer sizes */ 4442 { size_t const blockSize = MIN(zbd->fParams.windowSize, ZSTDv07_BLOCKSIZE_ABSOLUTEMAX); 4443 zbd->blockSize = blockSize; 4444 if (zbd->inBuffSize < blockSize) { 4445 zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff); 4446 zbd->inBuffSize = blockSize; 4447 zbd->inBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, blockSize); 4448 if (zbd->inBuff == NULL) return ERROR(memory_allocation); 4449 } 4450 { size_t const neededOutSize = zbd->fParams.windowSize + blockSize + WILDCOPY_OVERLENGTH * 2; 4451 if (zbd->outBuffSize < neededOutSize) { 4452 zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff); 4453 zbd->outBuffSize = neededOutSize; 4454 zbd->outBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, neededOutSize); 4455 if (zbd->outBuff == NULL) return ERROR(memory_allocation); 4456 } } } 4457 zbd->stage = ZBUFFds_read; 4458 /* pass-through */ 4459 /* fall-through */ 4460 case ZBUFFds_read: 4461 { size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd); 4462 if (neededInSize==0) { /* end of frame */ 4463 zbd->stage = ZBUFFds_init; 4464 notDone = 0; 4465 break; 4466 } 4467 if ((size_t)(iend-ip) >= neededInSize) { /* decode directly from src */ 4468 const int isSkipFrame = ZSTDv07_isSkipFrame(zbd->zd); 4469 size_t const decodedSize = ZSTDv07_decompressContinue(zbd->zd, 4470 zbd->outBuff + zbd->outStart, (isSkipFrame ? 0 : zbd->outBuffSize - zbd->outStart), 4471 ip, neededInSize); 4472 if (ZSTDv07_isError(decodedSize)) return decodedSize; 4473 ip += neededInSize; 4474 if (!decodedSize && !isSkipFrame) break; /* this was just a header */ 4475 zbd->outEnd = zbd->outStart + decodedSize; 4476 zbd->stage = ZBUFFds_flush; 4477 break; 4478 } 4479 if (ip==iend) { notDone = 0; break; } /* no more input */ 4480 zbd->stage = ZBUFFds_load; 4481 } 4482 /* fall-through */ 4483 case ZBUFFds_load: 4484 { size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd); 4485 size_t const toLoad = neededInSize - zbd->inPos; /* should always be <= remaining space within inBuff */ 4486 size_t loadedSize; 4487 if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected); /* should never happen */ 4488 loadedSize = ZBUFFv07_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip); 4489 ip += loadedSize; 4490 zbd->inPos += loadedSize; 4491 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */ 4492 4493 /* decode loaded input */ 4494 { const int isSkipFrame = ZSTDv07_isSkipFrame(zbd->zd); 4495 size_t const decodedSize = ZSTDv07_decompressContinue(zbd->zd, 4496 zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart, 4497 zbd->inBuff, neededInSize); 4498 if (ZSTDv07_isError(decodedSize)) return decodedSize; 4499 zbd->inPos = 0; /* input is consumed */ 4500 if (!decodedSize && !isSkipFrame) { zbd->stage = ZBUFFds_read; break; } /* this was just a header */ 4501 zbd->outEnd = zbd->outStart + decodedSize; 4502 zbd->stage = ZBUFFds_flush; 4503 /* break; */ 4504 /* pass-through */ 4505 } 4506 } 4507 /* fall-through */ 4508 case ZBUFFds_flush: 4509 { size_t const toFlushSize = zbd->outEnd - zbd->outStart; 4510 size_t const flushedSize = ZBUFFv07_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize); 4511 op += flushedSize; 4512 zbd->outStart += flushedSize; 4513 if (flushedSize == toFlushSize) { 4514 zbd->stage = ZBUFFds_read; 4515 if (zbd->outStart + zbd->blockSize > zbd->outBuffSize) 4516 zbd->outStart = zbd->outEnd = 0; 4517 break; 4518 } 4519 /* cannot flush everything */ 4520 notDone = 0; 4521 break; 4522 } 4523 default: return ERROR(GENERIC); /* impossible */ 4524 } } 4525 4526 /* result */ 4527 *srcSizePtr = ip-istart; 4528 *dstCapacityPtr = op-ostart; 4529 { size_t nextSrcSizeHint = ZSTDv07_nextSrcSizeToDecompress(zbd->zd); 4530 nextSrcSizeHint -= zbd->inPos; /* already loaded*/ 4531 return nextSrcSizeHint; 4532 } 4533} 4534 4535 4536 4537/* ************************************* 4538* Tool functions 4539***************************************/ 4540size_t ZBUFFv07_recommendedDInSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX + ZSTDv07_blockHeaderSize /* block header size*/ ; } 4541size_t ZBUFFv07_recommendedDOutSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX; } 4542