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