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