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