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__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403) 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__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403) 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 843 /*-**************************************** 844 * unsafe API 845 ******************************************/ 846 MEM_STATIC size_t BITv06_readBitsFast(BITv06_DStream_t* bitD, unsigned nbBits); 847 /* faster, but works only if nbBits >= 1 */ 848 849 850 851 /*-************************************************************** 852 * Internal functions 853 ****************************************************************/ 854 MEM_STATIC unsigned BITv06_highbit32 ( U32 val) 855 { 856 # if defined(_MSC_VER) /* Visual */ 857 unsigned long r=0; 858 _BitScanReverse ( &r, val ); 859 return (unsigned) r; 860 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */ 861 return 31 - __builtin_clz (val); 862 # else /* Software version */ 863 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 }; 864 U32 v = val; 865 unsigned r; 866 v |= v >> 1; 867 v |= v >> 2; 868 v |= v >> 4; 869 v |= v >> 8; 870 v |= v >> 16; 871 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27]; 872 return r; 873 # endif 874 } 875 876 877 878 /*-******************************************************** 879 * bitStream decoding 880 **********************************************************/ 881 /*! BITv06_initDStream() : 882 * Initialize a BITv06_DStream_t. 883 * `bitD` : a pointer to an already allocated BITv06_DStream_t structure. 884 * `srcSize` must be the *exact* size of the bitStream, in bytes. 885 * @return : size of stream (== srcSize) or an errorCode if a problem is detected 886 */ 887 MEM_STATIC size_t BITv06_initDStream(BITv06_DStream_t* bitD, const void* srcBuffer, size_t srcSize) 888 { 889 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); } 890 891 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */ 892 bitD->start = (const char*)srcBuffer; 893 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer); 894 bitD->bitContainer = MEM_readLEST(bitD->ptr); 895 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1]; 896 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ 897 bitD->bitsConsumed = 8 - BITv06_highbit32(lastByte); } 898 } else { 899 bitD->start = (const char*)srcBuffer; 900 bitD->ptr = bitD->start; 901 bitD->bitContainer = *(const BYTE*)(bitD->start); 902 switch(srcSize) 903 { 904 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);/* fall-through */ 905 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);/* fall-through */ 906 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);/* fall-through */ 907 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24; /* fall-through */ 908 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16; /* fall-through */ 909 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8; /* fall-through */ 910 default: break; 911 } 912 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1]; 913 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ 914 bitD->bitsConsumed = 8 - BITv06_highbit32(lastByte); } 915 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8; 916 } 917 918 return srcSize; 919 } 920 921 922 MEM_STATIC size_t BITv06_lookBits(const BITv06_DStream_t* bitD, U32 nbBits) 923 { 924 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1; 925 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask); 926 } 927 928 /*! BITv06_lookBitsFast() : 929 * unsafe version; only works only if nbBits >= 1 */ 930 MEM_STATIC size_t BITv06_lookBitsFast(const BITv06_DStream_t* bitD, U32 nbBits) 931 { 932 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1; 933 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask); 934 } 935 936 MEM_STATIC void BITv06_skipBits(BITv06_DStream_t* bitD, U32 nbBits) 937 { 938 bitD->bitsConsumed += nbBits; 939 } 940 941 MEM_STATIC size_t BITv06_readBits(BITv06_DStream_t* bitD, U32 nbBits) 942 { 943 size_t const value = BITv06_lookBits(bitD, nbBits); 944 BITv06_skipBits(bitD, nbBits); 945 return value; 946 } 947 948 /*! BITv06_readBitsFast() : 949 * unsafe version; only works only if nbBits >= 1 */ 950 MEM_STATIC size_t BITv06_readBitsFast(BITv06_DStream_t* bitD, U32 nbBits) 951 { 952 size_t const value = BITv06_lookBitsFast(bitD, nbBits); 953 BITv06_skipBits(bitD, nbBits); 954 return value; 955 } 956 957 MEM_STATIC BITv06_DStream_status BITv06_reloadDStream(BITv06_DStream_t* bitD) 958 { 959 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */ 960 return BITv06_DStream_overflow; 961 962 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) { 963 bitD->ptr -= bitD->bitsConsumed >> 3; 964 bitD->bitsConsumed &= 7; 965 bitD->bitContainer = MEM_readLEST(bitD->ptr); 966 return BITv06_DStream_unfinished; 967 } 968 if (bitD->ptr == bitD->start) { 969 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv06_DStream_endOfBuffer; 970 return BITv06_DStream_completed; 971 } 972 { U32 nbBytes = bitD->bitsConsumed >> 3; 973 BITv06_DStream_status result = BITv06_DStream_unfinished; 974 if (bitD->ptr - nbBytes < bitD->start) { 975 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */ 976 result = BITv06_DStream_endOfBuffer; 977 } 978 bitD->ptr -= nbBytes; 979 bitD->bitsConsumed -= nbBytes*8; 980 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */ 981 return result; 982 } 983 } 984 985 /*! BITv06_endOfDStream() : 986 * @return Tells if DStream has exactly reached its end (all bits consumed). 987 */ 988 MEM_STATIC unsigned BITv06_endOfDStream(const BITv06_DStream_t* DStream) 989 { 990 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8)); 991 } 992 993 #if defined (__cplusplus) 994 } 995 #endif 996 997 #endif /* BITSTREAM_H_MODULE */ 998 /* ****************************************************************** 999 FSE : Finite State Entropy coder 1000 header file for static linking (only) 1001 Copyright (C) 2013-2015, Yann Collet 1002 1003 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1004 1005 Redistribution and use in source and binary forms, with or without 1006 modification, are permitted provided that the following conditions are 1007 met: 1008 1009 * Redistributions of source code must retain the above copyright 1010 notice, this list of conditions and the following disclaimer. 1011 * Redistributions in binary form must reproduce the above 1012 copyright notice, this list of conditions and the following disclaimer 1013 in the documentation and/or other materials provided with the 1014 distribution. 1015 1016 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1017 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1018 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1019 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1020 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1021 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1022 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1023 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1024 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1025 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1026 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1027 1028 You can contact the author at : 1029 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 1030 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1031 ****************************************************************** */ 1032 #ifndef FSEv06_STATIC_H 1033 #define FSEv06_STATIC_H 1034 1035 #if defined (__cplusplus) 1036 extern "C" { 1037 #endif 1038 1039 1040 /* ***************************************** 1041 * Static allocation 1042 *******************************************/ 1043 /* FSE buffer bounds */ 1044 #define FSEv06_NCOUNTBOUND 512 1045 #define FSEv06_BLOCKBOUND(size) (size + (size>>7)) 1046 #define FSEv06_COMPRESSBOUND(size) (FSEv06_NCOUNTBOUND + FSEv06_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ 1047 1048 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */ 1049 #define FSEv06_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog)) 1050 1051 1052 /* ***************************************** 1053 * FSE advanced API 1054 *******************************************/ 1055 size_t FSEv06_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize); 1056 /* same as FSEv06_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */ 1057 1058 size_t FSEv06_buildDTable_raw (FSEv06_DTable* dt, unsigned nbBits); 1059 /* build a fake FSEv06_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */ 1060 1061 size_t FSEv06_buildDTable_rle (FSEv06_DTable* dt, unsigned char symbolValue); 1062 /* build a fake FSEv06_DTable, designed to always generate the same symbolValue */ 1063 1064 1065 /* ***************************************** 1066 * FSE symbol decompression API 1067 *******************************************/ 1068 typedef struct 1069 { 1070 size_t state; 1071 const void* table; /* precise table may vary, depending on U16 */ 1072 } FSEv06_DState_t; 1073 1074 1075 static void FSEv06_initDState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD, const FSEv06_DTable* dt); 1076 1077 static unsigned char FSEv06_decodeSymbol(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD); 1078 1079 1080 /* ***************************************** 1081 * FSE unsafe API 1082 *******************************************/ 1083 static unsigned char FSEv06_decodeSymbolFast(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD); 1084 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */ 1085 1086 1087 /* ***************************************** 1088 * Implementation of inlined functions 1089 *******************************************/ 1090 1091 1092 /* ====== Decompression ====== */ 1093 1094 typedef struct { 1095 U16 tableLog; 1096 U16 fastMode; 1097 } FSEv06_DTableHeader; /* sizeof U32 */ 1098 1099 typedef struct 1100 { 1101 unsigned short newState; 1102 unsigned char symbol; 1103 unsigned char nbBits; 1104 } FSEv06_decode_t; /* size == U32 */ 1105 1106 MEM_STATIC void FSEv06_initDState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD, const FSEv06_DTable* dt) 1107 { 1108 const void* ptr = dt; 1109 const FSEv06_DTableHeader* const DTableH = (const FSEv06_DTableHeader*)ptr; 1110 DStatePtr->state = BITv06_readBits(bitD, DTableH->tableLog); 1111 BITv06_reloadDStream(bitD); 1112 DStatePtr->table = dt + 1; 1113 } 1114 1115 MEM_STATIC BYTE FSEv06_peekSymbol(const FSEv06_DState_t* DStatePtr) 1116 { 1117 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state]; 1118 return DInfo.symbol; 1119 } 1120 1121 MEM_STATIC void FSEv06_updateState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD) 1122 { 1123 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state]; 1124 U32 const nbBits = DInfo.nbBits; 1125 size_t const lowBits = BITv06_readBits(bitD, nbBits); 1126 DStatePtr->state = DInfo.newState + lowBits; 1127 } 1128 1129 MEM_STATIC BYTE FSEv06_decodeSymbol(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD) 1130 { 1131 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state]; 1132 U32 const nbBits = DInfo.nbBits; 1133 BYTE const symbol = DInfo.symbol; 1134 size_t const lowBits = BITv06_readBits(bitD, nbBits); 1135 1136 DStatePtr->state = DInfo.newState + lowBits; 1137 return symbol; 1138 } 1139 1140 /*! FSEv06_decodeSymbolFast() : 1141 unsafe, only works if no symbol has a probability > 50% */ 1142 MEM_STATIC BYTE FSEv06_decodeSymbolFast(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD) 1143 { 1144 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state]; 1145 U32 const nbBits = DInfo.nbBits; 1146 BYTE const symbol = DInfo.symbol; 1147 size_t const lowBits = BITv06_readBitsFast(bitD, nbBits); 1148 1149 DStatePtr->state = DInfo.newState + lowBits; 1150 return symbol; 1151 } 1152 1153 1154 1155 #ifndef FSEv06_COMMONDEFS_ONLY 1156 1157 /* ************************************************************** 1158 * Tuning parameters 1159 ****************************************************************/ 1160 /*!MEMORY_USAGE : 1161 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) 1162 * Increasing memory usage improves compression ratio 1163 * Reduced memory usage can improve speed, due to cache effect 1164 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */ 1165 #define FSEv06_MAX_MEMORY_USAGE 14 1166 #define FSEv06_DEFAULT_MEMORY_USAGE 13 1167 1168 /*!FSEv06_MAX_SYMBOL_VALUE : 1169 * Maximum symbol value authorized. 1170 * Required for proper stack allocation */ 1171 #define FSEv06_MAX_SYMBOL_VALUE 255 1172 1173 1174 /* ************************************************************** 1175 * template functions type & suffix 1176 ****************************************************************/ 1177 #define FSEv06_FUNCTION_TYPE BYTE 1178 #define FSEv06_FUNCTION_EXTENSION 1179 #define FSEv06_DECODE_TYPE FSEv06_decode_t 1180 1181 1182 #endif /* !FSEv06_COMMONDEFS_ONLY */ 1183 1184 1185 /* *************************************************************** 1186 * Constants 1187 *****************************************************************/ 1188 #define FSEv06_MAX_TABLELOG (FSEv06_MAX_MEMORY_USAGE-2) 1189 #define FSEv06_MAX_TABLESIZE (1U<<FSEv06_MAX_TABLELOG) 1190 #define FSEv06_MAXTABLESIZE_MASK (FSEv06_MAX_TABLESIZE-1) 1191 #define FSEv06_DEFAULT_TABLELOG (FSEv06_DEFAULT_MEMORY_USAGE-2) 1192 #define FSEv06_MIN_TABLELOG 5 1193 1194 #define FSEv06_TABLELOG_ABSOLUTE_MAX 15 1195 #if FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX 1196 #error "FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX is not supported" 1197 #endif 1198 1199 #define FSEv06_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3) 1200 1201 1202 #if defined (__cplusplus) 1203 } 1204 #endif 1205 1206 #endif /* FSEv06_STATIC_H */ 1207 /* 1208 Common functions of New Generation Entropy library 1209 Copyright (C) 2016, Yann Collet. 1210 1211 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1212 1213 Redistribution and use in source and binary forms, with or without 1214 modification, are permitted provided that the following conditions are 1215 met: 1216 1217 * Redistributions of source code must retain the above copyright 1218 notice, this list of conditions and the following disclaimer. 1219 * Redistributions in binary form must reproduce the above 1220 copyright notice, this list of conditions and the following disclaimer 1221 in the documentation and/or other materials provided with the 1222 distribution. 1223 1224 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1225 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1226 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1227 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1228 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1229 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1230 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1231 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1232 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1233 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1234 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1235 1236 You can contact the author at : 1237 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy 1238 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1239 *************************************************************************** */ 1240 1241 1242 /*-**************************************** 1243 * FSE Error Management 1244 ******************************************/ 1245 unsigned FSEv06_isError(size_t code) { return ERR_isError(code); } 1246 1247 const char* FSEv06_getErrorName(size_t code) { return ERR_getErrorName(code); } 1248 1249 1250 /* ************************************************************** 1251 * HUF Error Management 1252 ****************************************************************/ 1253 static unsigned HUFv06_isError(size_t code) { return ERR_isError(code); } 1254 1255 1256 /*-************************************************************** 1257 * FSE NCount encoding-decoding 1258 ****************************************************************/ 1259 static short FSEv06_abs(short a) { return a<0 ? -a : a; } 1260 1261 size_t FSEv06_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr, 1262 const void* headerBuffer, size_t hbSize) 1263 { 1264 const BYTE* const istart = (const BYTE*) headerBuffer; 1265 const BYTE* const iend = istart + hbSize; 1266 const BYTE* ip = istart; 1267 int nbBits; 1268 int remaining; 1269 int threshold; 1270 U32 bitStream; 1271 int bitCount; 1272 unsigned charnum = 0; 1273 int previous0 = 0; 1274 1275 if (hbSize < 4) return ERROR(srcSize_wrong); 1276 bitStream = MEM_readLE32(ip); 1277 nbBits = (bitStream & 0xF) + FSEv06_MIN_TABLELOG; /* extract tableLog */ 1278 if (nbBits > FSEv06_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge); 1279 bitStream >>= 4; 1280 bitCount = 4; 1281 *tableLogPtr = nbBits; 1282 remaining = (1<<nbBits)+1; 1283 threshold = 1<<nbBits; 1284 nbBits++; 1285 1286 while ((remaining>1) && (charnum<=*maxSVPtr)) { 1287 if (previous0) { 1288 unsigned n0 = charnum; 1289 while ((bitStream & 0xFFFF) == 0xFFFF) { 1290 n0+=24; 1291 if (ip < iend-5) { 1292 ip+=2; 1293 bitStream = MEM_readLE32(ip) >> bitCount; 1294 } else { 1295 bitStream >>= 16; 1296 bitCount+=16; 1297 } } 1298 while ((bitStream & 3) == 3) { 1299 n0+=3; 1300 bitStream>>=2; 1301 bitCount+=2; 1302 } 1303 n0 += bitStream & 3; 1304 bitCount += 2; 1305 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall); 1306 while (charnum < n0) normalizedCounter[charnum++] = 0; 1307 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { 1308 ip += bitCount>>3; 1309 bitCount &= 7; 1310 bitStream = MEM_readLE32(ip) >> bitCount; 1311 } 1312 else 1313 bitStream >>= 2; 1314 } 1315 { short const max = (short)((2*threshold-1)-remaining); 1316 short count; 1317 1318 if ((bitStream & (threshold-1)) < (U32)max) { 1319 count = (short)(bitStream & (threshold-1)); 1320 bitCount += nbBits-1; 1321 } else { 1322 count = (short)(bitStream & (2*threshold-1)); 1323 if (count >= threshold) count -= max; 1324 bitCount += nbBits; 1325 } 1326 1327 count--; /* extra accuracy */ 1328 remaining -= FSEv06_abs(count); 1329 normalizedCounter[charnum++] = count; 1330 previous0 = !count; 1331 while (remaining < threshold) { 1332 nbBits--; 1333 threshold >>= 1; 1334 } 1335 1336 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { 1337 ip += bitCount>>3; 1338 bitCount &= 7; 1339 } else { 1340 bitCount -= (int)(8 * (iend - 4 - ip)); 1341 ip = iend - 4; 1342 } 1343 bitStream = MEM_readLE32(ip) >> (bitCount & 31); 1344 } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */ 1345 if (remaining != 1) return ERROR(GENERIC); 1346 *maxSVPtr = charnum-1; 1347 1348 ip += (bitCount+7)>>3; 1349 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong); 1350 return ip-istart; 1351 } 1352 /* ****************************************************************** 1353 FSE : Finite State Entropy decoder 1354 Copyright (C) 2013-2015, Yann Collet. 1355 1356 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1357 1358 Redistribution and use in source and binary forms, with or without 1359 modification, are permitted provided that the following conditions are 1360 met: 1361 1362 * Redistributions of source code must retain the above copyright 1363 notice, this list of conditions and the following disclaimer. 1364 * Redistributions in binary form must reproduce the above 1365 copyright notice, this list of conditions and the following disclaimer 1366 in the documentation and/or other materials provided with the 1367 distribution. 1368 1369 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1370 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1371 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1372 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1373 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1374 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1375 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1376 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1377 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1378 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1379 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1380 1381 You can contact the author at : 1382 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy 1383 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1384 ****************************************************************** */ 1385 1386 1387 /* ************************************************************** 1388 * Compiler specifics 1389 ****************************************************************/ 1390 #ifdef _MSC_VER /* Visual Studio */ 1391 # define FORCE_INLINE static __forceinline 1392 # include <intrin.h> /* For Visual 2005 */ 1393 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 1394 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */ 1395 #else 1396 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 1397 # ifdef __GNUC__ 1398 # define FORCE_INLINE static inline __attribute__((always_inline)) 1399 # else 1400 # define FORCE_INLINE static inline 1401 # endif 1402 # else 1403 # define FORCE_INLINE static 1404 # endif /* __STDC_VERSION__ */ 1405 #endif 1406 1407 1408 /* ************************************************************** 1409 * Error Management 1410 ****************************************************************/ 1411 #define FSEv06_isError ERR_isError 1412 #define FSEv06_STATIC_ASSERT(c) { enum { FSEv06_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 1413 1414 1415 /* ************************************************************** 1416 * Complex types 1417 ****************************************************************/ 1418 typedef U32 DTable_max_t[FSEv06_DTABLE_SIZE_U32(FSEv06_MAX_TABLELOG)]; 1419 1420 1421 /* ************************************************************** 1422 * Templates 1423 ****************************************************************/ 1424 /* 1425 designed to be included 1426 for type-specific functions (template emulation in C) 1427 Objective is to write these functions only once, for improved maintenance 1428 */ 1429 1430 /* safety checks */ 1431 #ifndef FSEv06_FUNCTION_EXTENSION 1432 # error "FSEv06_FUNCTION_EXTENSION must be defined" 1433 #endif 1434 #ifndef FSEv06_FUNCTION_TYPE 1435 # error "FSEv06_FUNCTION_TYPE must be defined" 1436 #endif 1437 1438 /* Function names */ 1439 #define FSEv06_CAT(X,Y) X##Y 1440 #define FSEv06_FUNCTION_NAME(X,Y) FSEv06_CAT(X,Y) 1441 #define FSEv06_TYPE_NAME(X,Y) FSEv06_CAT(X,Y) 1442 1443 1444 /* Function templates */ 1445 FSEv06_DTable* FSEv06_createDTable (unsigned tableLog) 1446 { 1447 if (tableLog > FSEv06_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv06_TABLELOG_ABSOLUTE_MAX; 1448 return (FSEv06_DTable*)malloc( FSEv06_DTABLE_SIZE_U32(tableLog) * sizeof (U32) ); 1449 } 1450 1451 void FSEv06_freeDTable (FSEv06_DTable* dt) 1452 { 1453 free(dt); 1454 } 1455 1456 size_t FSEv06_buildDTable(FSEv06_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) 1457 { 1458 void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */ 1459 FSEv06_DECODE_TYPE* const tableDecode = (FSEv06_DECODE_TYPE*) (tdPtr); 1460 U16 symbolNext[FSEv06_MAX_SYMBOL_VALUE+1]; 1461 1462 U32 const maxSV1 = maxSymbolValue + 1; 1463 U32 const tableSize = 1 << tableLog; 1464 U32 highThreshold = tableSize-1; 1465 1466 /* Sanity Checks */ 1467 if (maxSymbolValue > FSEv06_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge); 1468 if (tableLog > FSEv06_MAX_TABLELOG) return ERROR(tableLog_tooLarge); 1469 1470 /* Init, lay down lowprob symbols */ 1471 { FSEv06_DTableHeader DTableH; 1472 DTableH.tableLog = (U16)tableLog; 1473 DTableH.fastMode = 1; 1474 { S16 const largeLimit= (S16)(1 << (tableLog-1)); 1475 U32 s; 1476 for (s=0; s<maxSV1; s++) { 1477 if (normalizedCounter[s]==-1) { 1478 tableDecode[highThreshold--].symbol = (FSEv06_FUNCTION_TYPE)s; 1479 symbolNext[s] = 1; 1480 } else { 1481 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0; 1482 symbolNext[s] = normalizedCounter[s]; 1483 } } } 1484 memcpy(dt, &DTableH, sizeof(DTableH)); 1485 } 1486 1487 /* Spread symbols */ 1488 { U32 const tableMask = tableSize-1; 1489 U32 const step = FSEv06_TABLESTEP(tableSize); 1490 U32 s, position = 0; 1491 for (s=0; s<maxSV1; s++) { 1492 int i; 1493 for (i=0; i<normalizedCounter[s]; i++) { 1494 tableDecode[position].symbol = (FSEv06_FUNCTION_TYPE)s; 1495 position = (position + step) & tableMask; 1496 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */ 1497 } } 1498 1499 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ 1500 } 1501 1502 /* Build Decoding table */ 1503 { U32 u; 1504 for (u=0; u<tableSize; u++) { 1505 FSEv06_FUNCTION_TYPE const symbol = (FSEv06_FUNCTION_TYPE)(tableDecode[u].symbol); 1506 U16 nextState = symbolNext[symbol]++; 1507 tableDecode[u].nbBits = (BYTE) (tableLog - BITv06_highbit32 ((U32)nextState) ); 1508 tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize); 1509 } } 1510 1511 return 0; 1512 } 1513 1514 1515 1516 #ifndef FSEv06_COMMONDEFS_ONLY 1517 1518 /*-******************************************************* 1519 * Decompression (Byte symbols) 1520 *********************************************************/ 1521 size_t FSEv06_buildDTable_rle (FSEv06_DTable* dt, BYTE symbolValue) 1522 { 1523 void* ptr = dt; 1524 FSEv06_DTableHeader* const DTableH = (FSEv06_DTableHeader*)ptr; 1525 void* dPtr = dt + 1; 1526 FSEv06_decode_t* const cell = (FSEv06_decode_t*)dPtr; 1527 1528 DTableH->tableLog = 0; 1529 DTableH->fastMode = 0; 1530 1531 cell->newState = 0; 1532 cell->symbol = symbolValue; 1533 cell->nbBits = 0; 1534 1535 return 0; 1536 } 1537 1538 1539 size_t FSEv06_buildDTable_raw (FSEv06_DTable* dt, unsigned nbBits) 1540 { 1541 void* ptr = dt; 1542 FSEv06_DTableHeader* const DTableH = (FSEv06_DTableHeader*)ptr; 1543 void* dPtr = dt + 1; 1544 FSEv06_decode_t* const dinfo = (FSEv06_decode_t*)dPtr; 1545 const unsigned tableSize = 1 << nbBits; 1546 const unsigned tableMask = tableSize - 1; 1547 const unsigned maxSV1 = tableMask+1; 1548 unsigned s; 1549 1550 /* Sanity checks */ 1551 if (nbBits < 1) return ERROR(GENERIC); /* min size */ 1552 1553 /* Build Decoding Table */ 1554 DTableH->tableLog = (U16)nbBits; 1555 DTableH->fastMode = 1; 1556 for (s=0; s<maxSV1; s++) { 1557 dinfo[s].newState = 0; 1558 dinfo[s].symbol = (BYTE)s; 1559 dinfo[s].nbBits = (BYTE)nbBits; 1560 } 1561 1562 return 0; 1563 } 1564 1565 FORCE_INLINE size_t FSEv06_decompress_usingDTable_generic( 1566 void* dst, size_t maxDstSize, 1567 const void* cSrc, size_t cSrcSize, 1568 const FSEv06_DTable* dt, const unsigned fast) 1569 { 1570 BYTE* const ostart = (BYTE*) dst; 1571 BYTE* op = ostart; 1572 BYTE* const omax = op + maxDstSize; 1573 BYTE* const olimit = omax-3; 1574 1575 BITv06_DStream_t bitD; 1576 FSEv06_DState_t state1; 1577 FSEv06_DState_t state2; 1578 1579 /* Init */ 1580 { size_t const errorCode = BITv06_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */ 1581 if (FSEv06_isError(errorCode)) return errorCode; } 1582 1583 FSEv06_initDState(&state1, &bitD, dt); 1584 FSEv06_initDState(&state2, &bitD, dt); 1585 1586 #define FSEv06_GETSYMBOL(statePtr) fast ? FSEv06_decodeSymbolFast(statePtr, &bitD) : FSEv06_decodeSymbol(statePtr, &bitD) 1587 1588 /* 4 symbols per loop */ 1589 for ( ; (BITv06_reloadDStream(&bitD)==BITv06_DStream_unfinished) && (op<olimit) ; op+=4) { 1590 op[0] = FSEv06_GETSYMBOL(&state1); 1591 1592 if (FSEv06_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1593 BITv06_reloadDStream(&bitD); 1594 1595 op[1] = FSEv06_GETSYMBOL(&state2); 1596 1597 if (FSEv06_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1598 { if (BITv06_reloadDStream(&bitD) > BITv06_DStream_unfinished) { op+=2; break; } } 1599 1600 op[2] = FSEv06_GETSYMBOL(&state1); 1601 1602 if (FSEv06_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1603 BITv06_reloadDStream(&bitD); 1604 1605 op[3] = FSEv06_GETSYMBOL(&state2); 1606 } 1607 1608 /* tail */ 1609 /* note : BITv06_reloadDStream(&bitD) >= FSEv06_DStream_partiallyFilled; Ends at exactly BITv06_DStream_completed */ 1610 while (1) { 1611 if (op>(omax-2)) return ERROR(dstSize_tooSmall); 1612 1613 *op++ = FSEv06_GETSYMBOL(&state1); 1614 1615 if (BITv06_reloadDStream(&bitD)==BITv06_DStream_overflow) { 1616 *op++ = FSEv06_GETSYMBOL(&state2); 1617 break; 1618 } 1619 1620 if (op>(omax-2)) return ERROR(dstSize_tooSmall); 1621 1622 *op++ = FSEv06_GETSYMBOL(&state2); 1623 1624 if (BITv06_reloadDStream(&bitD)==BITv06_DStream_overflow) { 1625 *op++ = FSEv06_GETSYMBOL(&state1); 1626 break; 1627 } } 1628 1629 return op-ostart; 1630 } 1631 1632 1633 size_t FSEv06_decompress_usingDTable(void* dst, size_t originalSize, 1634 const void* cSrc, size_t cSrcSize, 1635 const FSEv06_DTable* dt) 1636 { 1637 const void* ptr = dt; 1638 const FSEv06_DTableHeader* DTableH = (const FSEv06_DTableHeader*)ptr; 1639 const U32 fastMode = DTableH->fastMode; 1640 1641 /* select fast mode (static) */ 1642 if (fastMode) return FSEv06_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1); 1643 return FSEv06_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0); 1644 } 1645 1646 1647 size_t FSEv06_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize) 1648 { 1649 const BYTE* const istart = (const BYTE*)cSrc; 1650 const BYTE* ip = istart; 1651 short counting[FSEv06_MAX_SYMBOL_VALUE+1]; 1652 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */ 1653 unsigned tableLog; 1654 unsigned maxSymbolValue = FSEv06_MAX_SYMBOL_VALUE; 1655 1656 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */ 1657 1658 /* normal FSE decoding mode */ 1659 { size_t const NCountLength = FSEv06_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize); 1660 if (FSEv06_isError(NCountLength)) return NCountLength; 1661 if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */ 1662 ip += NCountLength; 1663 cSrcSize -= NCountLength; 1664 } 1665 1666 { size_t const errorCode = FSEv06_buildDTable (dt, counting, maxSymbolValue, tableLog); 1667 if (FSEv06_isError(errorCode)) return errorCode; } 1668 1669 return FSEv06_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); /* always return, even if it is an error code */ 1670 } 1671 1672 1673 1674 #endif /* FSEv06_COMMONDEFS_ONLY */ 1675 /* ****************************************************************** 1676 Huffman coder, part of New Generation Entropy library 1677 header file 1678 Copyright (C) 2013-2016, Yann Collet. 1679 1680 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1681 1682 Redistribution and use in source and binary forms, with or without 1683 modification, are permitted provided that the following conditions are 1684 met: 1685 1686 * Redistributions of source code must retain the above copyright 1687 notice, this list of conditions and the following disclaimer. 1688 * Redistributions in binary form must reproduce the above 1689 copyright notice, this list of conditions and the following disclaimer 1690 in the documentation and/or other materials provided with the 1691 distribution. 1692 1693 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1694 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1695 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1696 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1697 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1698 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1699 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1700 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1701 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1702 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1703 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1704 1705 You can contact the author at : 1706 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 1707 ****************************************************************** */ 1708 #ifndef HUFv06_H 1709 #define HUFv06_H 1710 1711 #if defined (__cplusplus) 1712 extern "C" { 1713 #endif 1714 1715 1716 /* **************************************** 1717 * HUF simple functions 1718 ******************************************/ 1719 size_t HUFv06_decompress(void* dst, size_t dstSize, 1720 const void* cSrc, size_t cSrcSize); 1721 /* 1722 HUFv06_decompress() : 1723 Decompress HUF data from buffer 'cSrc', of size 'cSrcSize', 1724 into already allocated destination buffer 'dst', of size 'dstSize'. 1725 `dstSize` : must be the **exact** size of original (uncompressed) data. 1726 Note : in contrast with FSE, HUFv06_decompress can regenerate 1727 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, 1728 because it knows size to regenerate. 1729 @return : size of regenerated data (== dstSize) 1730 or an error code, which can be tested using HUFv06_isError() 1731 */ 1732 1733 1734 /* **************************************** 1735 * Tool functions 1736 ******************************************/ 1737 size_t HUFv06_compressBound(size_t size); /**< maximum compressed size */ 1738 1739 1740 #if defined (__cplusplus) 1741 } 1742 #endif 1743 1744 #endif /* HUFv06_H */ 1745 /* ****************************************************************** 1746 Huffman codec, part of New Generation Entropy library 1747 header file, for static linking only 1748 Copyright (C) 2013-2016, Yann Collet 1749 1750 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1751 1752 Redistribution and use in source and binary forms, with or without 1753 modification, are permitted provided that the following conditions are 1754 met: 1755 1756 * Redistributions of source code must retain the above copyright 1757 notice, this list of conditions and the following disclaimer. 1758 * Redistributions in binary form must reproduce the above 1759 copyright notice, this list of conditions and the following disclaimer 1760 in the documentation and/or other materials provided with the 1761 distribution. 1762 1763 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1764 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1765 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1766 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1767 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1768 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1769 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1770 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1771 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1772 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1773 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1774 1775 You can contact the author at : 1776 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 1777 ****************************************************************** */ 1778 #ifndef HUFv06_STATIC_H 1779 #define HUFv06_STATIC_H 1780 1781 #if defined (__cplusplus) 1782 extern "C" { 1783 #endif 1784 1785 1786 /* **************************************** 1787 * Static allocation 1788 ******************************************/ 1789 /* HUF buffer bounds */ 1790 #define HUFv06_CTABLEBOUND 129 1791 #define HUFv06_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */ 1792 #define HUFv06_COMPRESSBOUND(size) (HUFv06_CTABLEBOUND + HUFv06_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ 1793 1794 /* static allocation of HUF's DTable */ 1795 #define HUFv06_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) 1796 #define HUFv06_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \ 1797 unsigned short DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 1798 #define HUFv06_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \ 1799 unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 1800 #define HUFv06_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \ 1801 unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog } 1802 1803 1804 /* **************************************** 1805 * Advanced decompression functions 1806 ******************************************/ 1807 size_t HUFv06_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ 1808 size_t HUFv06_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */ 1809 1810 1811 1812 /*! 1813 HUFv06_decompress() does the following: 1814 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics 1815 2. build Huffman table from save, using HUFv06_readDTableXn() 1816 3. decode 1 or 4 segments in parallel using HUFv06_decompressSXn_usingDTable 1817 */ 1818 size_t HUFv06_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize); 1819 size_t HUFv06_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize); 1820 1821 size_t HUFv06_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable); 1822 size_t HUFv06_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable); 1823 1824 1825 /* single stream variants */ 1826 size_t HUFv06_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ 1827 size_t HUFv06_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */ 1828 1829 size_t HUFv06_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable); 1830 size_t HUFv06_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable); 1831 1832 1833 1834 /* ************************************************************** 1835 * Constants 1836 ****************************************************************/ 1837 #define HUFv06_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUFv06_MAX_TABLELOG. Beyond that value, code does not work */ 1838 #define HUFv06_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUFv06_ABSOLUTEMAX_TABLELOG */ 1839 #define HUFv06_DEFAULT_TABLELOG HUFv06_MAX_TABLELOG /* tableLog by default, when not specified */ 1840 #define HUFv06_MAX_SYMBOL_VALUE 255 1841 #if (HUFv06_MAX_TABLELOG > HUFv06_ABSOLUTEMAX_TABLELOG) 1842 # error "HUFv06_MAX_TABLELOG is too large !" 1843 #endif 1844 1845 1846 1847 /*! HUFv06_readStats() : 1848 Read compact Huffman tree, saved by HUFv06_writeCTable(). 1849 `huffWeight` is destination buffer. 1850 @return : size read from `src` 1851 */ 1852 MEM_STATIC size_t HUFv06_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats, 1853 U32* nbSymbolsPtr, U32* tableLogPtr, 1854 const void* src, size_t srcSize) 1855 { 1856 U32 weightTotal; 1857 const BYTE* ip = (const BYTE*) src; 1858 size_t iSize; 1859 size_t oSize; 1860 1861 if (!srcSize) return ERROR(srcSize_wrong); 1862 iSize = ip[0]; 1863 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */ 1864 1865 if (iSize >= 128) { /* special header */ 1866 if (iSize >= (242)) { /* RLE */ 1867 static U32 l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 }; 1868 oSize = l[iSize-242]; 1869 memset(huffWeight, 1, hwSize); 1870 iSize = 0; 1871 } 1872 else { /* Incompressible */ 1873 oSize = iSize - 127; 1874 iSize = ((oSize+1)/2); 1875 if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 1876 if (oSize >= hwSize) return ERROR(corruption_detected); 1877 ip += 1; 1878 { U32 n; 1879 for (n=0; n<oSize; n+=2) { 1880 huffWeight[n] = ip[n/2] >> 4; 1881 huffWeight[n+1] = ip[n/2] & 15; 1882 } } } } 1883 else { /* header compressed with FSE (normal case) */ 1884 if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 1885 oSize = FSEv06_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */ 1886 if (FSEv06_isError(oSize)) return oSize; 1887 } 1888 1889 /* collect weight stats */ 1890 memset(rankStats, 0, (HUFv06_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32)); 1891 weightTotal = 0; 1892 { U32 n; for (n=0; n<oSize; n++) { 1893 if (huffWeight[n] >= HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 1894 rankStats[huffWeight[n]]++; 1895 weightTotal += (1 << huffWeight[n]) >> 1; 1896 } } 1897 if (weightTotal == 0) return ERROR(corruption_detected); 1898 1899 /* get last non-null symbol weight (implied, total must be 2^n) */ 1900 { U32 const tableLog = BITv06_highbit32(weightTotal) + 1; 1901 if (tableLog > HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 1902 *tableLogPtr = tableLog; 1903 /* determine last weight */ 1904 { U32 const total = 1 << tableLog; 1905 U32 const rest = total - weightTotal; 1906 U32 const verif = 1 << BITv06_highbit32(rest); 1907 U32 const lastWeight = BITv06_highbit32(rest) + 1; 1908 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */ 1909 huffWeight[oSize] = (BYTE)lastWeight; 1910 rankStats[lastWeight]++; 1911 } } 1912 1913 /* check tree construction validity */ 1914 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */ 1915 1916 /* results */ 1917 *nbSymbolsPtr = (U32)(oSize+1); 1918 return iSize+1; 1919 } 1920 1921 1922 1923 #if defined (__cplusplus) 1924 } 1925 #endif 1926 1927 #endif /* HUFv06_STATIC_H */ 1928 /* ****************************************************************** 1929 Huffman decoder, part of New Generation Entropy library 1930 Copyright (C) 2013-2016, Yann Collet. 1931 1932 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1933 1934 Redistribution and use in source and binary forms, with or without 1935 modification, are permitted provided that the following conditions are 1936 met: 1937 1938 * Redistributions of source code must retain the above copyright 1939 notice, this list of conditions and the following disclaimer. 1940 * Redistributions in binary form must reproduce the above 1941 copyright notice, this list of conditions and the following disclaimer 1942 in the documentation and/or other materials provided with the 1943 distribution. 1944 1945 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1946 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1947 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1948 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1949 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1950 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1951 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1952 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1953 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1954 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1955 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1956 1957 You can contact the author at : 1958 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy 1959 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1960 ****************************************************************** */ 1961 1962 /* ************************************************************** 1963 * Compiler specifics 1964 ****************************************************************/ 1965 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 1966 /* inline is defined */ 1967 #elif defined(_MSC_VER) 1968 # define inline __inline 1969 #else 1970 # define inline /* disable inline */ 1971 #endif 1972 1973 1974 #ifdef _MSC_VER /* Visual Studio */ 1975 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 1976 #endif 1977 1978 1979 1980 /* ************************************************************** 1981 * Error Management 1982 ****************************************************************/ 1983 #define HUFv06_STATIC_ASSERT(c) { enum { HUFv06_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 1984 1985 1986 1987 /* ******************************************************* 1988 * HUF : Huffman block decompression 1989 *********************************************************/ 1990 typedef struct { BYTE byte; BYTE nbBits; } HUFv06_DEltX2; /* single-symbol decoding */ 1991 1992 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv06_DEltX4; /* double-symbols decoding */ 1993 1994 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t; 1995 1996 1997 1998 /*-***************************/ 1999 /* single-symbol decoding */ 2000 /*-***************************/ 2001 2002 size_t HUFv06_readDTableX2 (U16* DTable, const void* src, size_t srcSize) 2003 { 2004 BYTE huffWeight[HUFv06_MAX_SYMBOL_VALUE + 1]; 2005 U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */ 2006 U32 tableLog = 0; 2007 size_t iSize; 2008 U32 nbSymbols = 0; 2009 U32 n; 2010 U32 nextRankStart; 2011 void* const dtPtr = DTable + 1; 2012 HUFv06_DEltX2* const dt = (HUFv06_DEltX2*)dtPtr; 2013 2014 HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */ 2015 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */ 2016 2017 iSize = HUFv06_readStats(huffWeight, HUFv06_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize); 2018 if (HUFv06_isError(iSize)) return iSize; 2019 2020 /* check result */ 2021 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */ 2022 DTable[0] = (U16)tableLog; /* maybe should separate sizeof allocated DTable, from used size of DTable, in case of re-use */ 2023 2024 /* Prepare ranks */ 2025 nextRankStart = 0; 2026 for (n=1; n<tableLog+1; n++) { 2027 U32 current = nextRankStart; 2028 nextRankStart += (rankVal[n] << (n-1)); 2029 rankVal[n] = current; 2030 } 2031 2032 /* fill DTable */ 2033 for (n=0; n<nbSymbols; n++) { 2034 const U32 w = huffWeight[n]; 2035 const U32 length = (1 << w) >> 1; 2036 U32 i; 2037 HUFv06_DEltX2 D; 2038 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w); 2039 for (i = rankVal[w]; i < rankVal[w] + length; i++) 2040 dt[i] = D; 2041 rankVal[w] += length; 2042 } 2043 2044 return iSize; 2045 } 2046 2047 2048 static BYTE HUFv06_decodeSymbolX2(BITv06_DStream_t* Dstream, const HUFv06_DEltX2* dt, const U32 dtLog) 2049 { 2050 const size_t val = BITv06_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */ 2051 const BYTE c = dt[val].byte; 2052 BITv06_skipBits(Dstream, dt[val].nbBits); 2053 return c; 2054 } 2055 2056 #define HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \ 2057 *ptr++ = HUFv06_decodeSymbolX2(DStreamPtr, dt, dtLog) 2058 2059 #define HUFv06_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \ 2060 if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \ 2061 HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 2062 2063 #define HUFv06_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \ 2064 if (MEM_64bits()) \ 2065 HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 2066 2067 static inline size_t HUFv06_decodeStreamX2(BYTE* p, BITv06_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv06_DEltX2* const dt, const U32 dtLog) 2068 { 2069 BYTE* const pStart = p; 2070 2071 /* up to 4 symbols at a time */ 2072 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p <= pEnd-4)) { 2073 HUFv06_DECODE_SYMBOLX2_2(p, bitDPtr); 2074 HUFv06_DECODE_SYMBOLX2_1(p, bitDPtr); 2075 HUFv06_DECODE_SYMBOLX2_2(p, bitDPtr); 2076 HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr); 2077 } 2078 2079 /* closer to the end */ 2080 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p < pEnd)) 2081 HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr); 2082 2083 /* no more data to retrieve from bitstream, hence no need to reload */ 2084 while (p < pEnd) 2085 HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr); 2086 2087 return pEnd-pStart; 2088 } 2089 2090 size_t HUFv06_decompress1X2_usingDTable( 2091 void* dst, size_t dstSize, 2092 const void* cSrc, size_t cSrcSize, 2093 const U16* DTable) 2094 { 2095 BYTE* op = (BYTE*)dst; 2096 BYTE* const oend = op + dstSize; 2097 const U32 dtLog = DTable[0]; 2098 const void* dtPtr = DTable; 2099 const HUFv06_DEltX2* const dt = ((const HUFv06_DEltX2*)dtPtr)+1; 2100 BITv06_DStream_t bitD; 2101 2102 { size_t const errorCode = BITv06_initDStream(&bitD, cSrc, cSrcSize); 2103 if (HUFv06_isError(errorCode)) return errorCode; } 2104 2105 HUFv06_decodeStreamX2(op, &bitD, oend, dt, dtLog); 2106 2107 /* check */ 2108 if (!BITv06_endOfDStream(&bitD)) return ERROR(corruption_detected); 2109 2110 return dstSize; 2111 } 2112 2113 size_t HUFv06_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2114 { 2115 HUFv06_CREATE_STATIC_DTABLEX2(DTable, HUFv06_MAX_TABLELOG); 2116 const BYTE* ip = (const BYTE*) cSrc; 2117 2118 size_t const errorCode = HUFv06_readDTableX2 (DTable, cSrc, cSrcSize); 2119 if (HUFv06_isError(errorCode)) return errorCode; 2120 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); 2121 ip += errorCode; 2122 cSrcSize -= errorCode; 2123 2124 return HUFv06_decompress1X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2125 } 2126 2127 2128 size_t HUFv06_decompress4X2_usingDTable( 2129 void* dst, size_t dstSize, 2130 const void* cSrc, size_t cSrcSize, 2131 const U16* DTable) 2132 { 2133 /* Check */ 2134 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 2135 2136 { const BYTE* const istart = (const BYTE*) cSrc; 2137 BYTE* const ostart = (BYTE*) dst; 2138 BYTE* const oend = ostart + dstSize; 2139 const void* const dtPtr = DTable; 2140 const HUFv06_DEltX2* const dt = ((const HUFv06_DEltX2*)dtPtr) +1; 2141 const U32 dtLog = DTable[0]; 2142 size_t errorCode; 2143 2144 /* Init */ 2145 BITv06_DStream_t bitD1; 2146 BITv06_DStream_t bitD2; 2147 BITv06_DStream_t bitD3; 2148 BITv06_DStream_t bitD4; 2149 const size_t length1 = MEM_readLE16(istart); 2150 const size_t length2 = MEM_readLE16(istart+2); 2151 const size_t length3 = MEM_readLE16(istart+4); 2152 size_t length4; 2153 const BYTE* const istart1 = istart + 6; /* jumpTable */ 2154 const BYTE* const istart2 = istart1 + length1; 2155 const BYTE* const istart3 = istart2 + length2; 2156 const BYTE* const istart4 = istart3 + length3; 2157 const size_t segmentSize = (dstSize+3) / 4; 2158 BYTE* const opStart2 = ostart + segmentSize; 2159 BYTE* const opStart3 = opStart2 + segmentSize; 2160 BYTE* const opStart4 = opStart3 + segmentSize; 2161 BYTE* op1 = ostart; 2162 BYTE* op2 = opStart2; 2163 BYTE* op3 = opStart3; 2164 BYTE* op4 = opStart4; 2165 U32 endSignal; 2166 2167 length4 = cSrcSize - (length1 + length2 + length3 + 6); 2168 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 2169 errorCode = BITv06_initDStream(&bitD1, istart1, length1); 2170 if (HUFv06_isError(errorCode)) return errorCode; 2171 errorCode = BITv06_initDStream(&bitD2, istart2, length2); 2172 if (HUFv06_isError(errorCode)) return errorCode; 2173 errorCode = BITv06_initDStream(&bitD3, istart3, length3); 2174 if (HUFv06_isError(errorCode)) return errorCode; 2175 errorCode = BITv06_initDStream(&bitD4, istart4, length4); 2176 if (HUFv06_isError(errorCode)) return errorCode; 2177 2178 /* 16-32 symbols per loop (4-8 symbols per stream) */ 2179 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4); 2180 for ( ; (endSignal==BITv06_DStream_unfinished) && (op4<(oend-7)) ; ) { 2181 HUFv06_DECODE_SYMBOLX2_2(op1, &bitD1); 2182 HUFv06_DECODE_SYMBOLX2_2(op2, &bitD2); 2183 HUFv06_DECODE_SYMBOLX2_2(op3, &bitD3); 2184 HUFv06_DECODE_SYMBOLX2_2(op4, &bitD4); 2185 HUFv06_DECODE_SYMBOLX2_1(op1, &bitD1); 2186 HUFv06_DECODE_SYMBOLX2_1(op2, &bitD2); 2187 HUFv06_DECODE_SYMBOLX2_1(op3, &bitD3); 2188 HUFv06_DECODE_SYMBOLX2_1(op4, &bitD4); 2189 HUFv06_DECODE_SYMBOLX2_2(op1, &bitD1); 2190 HUFv06_DECODE_SYMBOLX2_2(op2, &bitD2); 2191 HUFv06_DECODE_SYMBOLX2_2(op3, &bitD3); 2192 HUFv06_DECODE_SYMBOLX2_2(op4, &bitD4); 2193 HUFv06_DECODE_SYMBOLX2_0(op1, &bitD1); 2194 HUFv06_DECODE_SYMBOLX2_0(op2, &bitD2); 2195 HUFv06_DECODE_SYMBOLX2_0(op3, &bitD3); 2196 HUFv06_DECODE_SYMBOLX2_0(op4, &bitD4); 2197 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4); 2198 } 2199 2200 /* check corruption */ 2201 if (op1 > opStart2) return ERROR(corruption_detected); 2202 if (op2 > opStart3) return ERROR(corruption_detected); 2203 if (op3 > opStart4) return ERROR(corruption_detected); 2204 /* note : op4 supposed already verified within main loop */ 2205 2206 /* finish bitStreams one by one */ 2207 HUFv06_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog); 2208 HUFv06_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog); 2209 HUFv06_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog); 2210 HUFv06_decodeStreamX2(op4, &bitD4, oend, dt, dtLog); 2211 2212 /* check */ 2213 endSignal = BITv06_endOfDStream(&bitD1) & BITv06_endOfDStream(&bitD2) & BITv06_endOfDStream(&bitD3) & BITv06_endOfDStream(&bitD4); 2214 if (!endSignal) return ERROR(corruption_detected); 2215 2216 /* decoded size */ 2217 return dstSize; 2218 } 2219 } 2220 2221 2222 size_t HUFv06_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2223 { 2224 HUFv06_CREATE_STATIC_DTABLEX2(DTable, HUFv06_MAX_TABLELOG); 2225 const BYTE* ip = (const BYTE*) cSrc; 2226 2227 size_t const errorCode = HUFv06_readDTableX2 (DTable, cSrc, cSrcSize); 2228 if (HUFv06_isError(errorCode)) return errorCode; 2229 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); 2230 ip += errorCode; 2231 cSrcSize -= errorCode; 2232 2233 return HUFv06_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2234 } 2235 2236 2237 /* *************************/ 2238 /* double-symbols decoding */ 2239 /* *************************/ 2240 2241 static void HUFv06_fillDTableX4Level2(HUFv06_DEltX4* DTable, U32 sizeLog, const U32 consumed, 2242 const U32* rankValOrigin, const int minWeight, 2243 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize, 2244 U32 nbBitsBaseline, U16 baseSeq) 2245 { 2246 HUFv06_DEltX4 DElt; 2247 U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1]; 2248 2249 /* get pre-calculated rankVal */ 2250 memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 2251 2252 /* fill skipped values */ 2253 if (minWeight>1) { 2254 U32 i, skipSize = rankVal[minWeight]; 2255 MEM_writeLE16(&(DElt.sequence), baseSeq); 2256 DElt.nbBits = (BYTE)(consumed); 2257 DElt.length = 1; 2258 for (i = 0; i < skipSize; i++) 2259 DTable[i] = DElt; 2260 } 2261 2262 /* fill DTable */ 2263 { U32 s; for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */ 2264 const U32 symbol = sortedSymbols[s].symbol; 2265 const U32 weight = sortedSymbols[s].weight; 2266 const U32 nbBits = nbBitsBaseline - weight; 2267 const U32 length = 1 << (sizeLog-nbBits); 2268 const U32 start = rankVal[weight]; 2269 U32 i = start; 2270 const U32 end = start + length; 2271 2272 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8))); 2273 DElt.nbBits = (BYTE)(nbBits + consumed); 2274 DElt.length = 2; 2275 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */ 2276 2277 rankVal[weight] += length; 2278 }} 2279 } 2280 2281 typedef U32 rankVal_t[HUFv06_ABSOLUTEMAX_TABLELOG][HUFv06_ABSOLUTEMAX_TABLELOG + 1]; 2282 2283 static void HUFv06_fillDTableX4(HUFv06_DEltX4* DTable, const U32 targetLog, 2284 const sortedSymbol_t* sortedList, const U32 sortedListSize, 2285 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight, 2286 const U32 nbBitsBaseline) 2287 { 2288 U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1]; 2289 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */ 2290 const U32 minBits = nbBitsBaseline - maxWeight; 2291 U32 s; 2292 2293 memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 2294 2295 /* fill DTable */ 2296 for (s=0; s<sortedListSize; s++) { 2297 const U16 symbol = sortedList[s].symbol; 2298 const U32 weight = sortedList[s].weight; 2299 const U32 nbBits = nbBitsBaseline - weight; 2300 const U32 start = rankVal[weight]; 2301 const U32 length = 1 << (targetLog-nbBits); 2302 2303 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */ 2304 U32 sortedRank; 2305 int minWeight = nbBits + scaleLog; 2306 if (minWeight < 1) minWeight = 1; 2307 sortedRank = rankStart[minWeight]; 2308 HUFv06_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits, 2309 rankValOrigin[nbBits], minWeight, 2310 sortedList+sortedRank, sortedListSize-sortedRank, 2311 nbBitsBaseline, symbol); 2312 } else { 2313 HUFv06_DEltX4 DElt; 2314 MEM_writeLE16(&(DElt.sequence), symbol); 2315 DElt.nbBits = (BYTE)(nbBits); 2316 DElt.length = 1; 2317 { U32 u; 2318 const U32 end = start + length; 2319 for (u = start; u < end; u++) DTable[u] = DElt; 2320 } } 2321 rankVal[weight] += length; 2322 } 2323 } 2324 2325 size_t HUFv06_readDTableX4 (U32* DTable, const void* src, size_t srcSize) 2326 { 2327 BYTE weightList[HUFv06_MAX_SYMBOL_VALUE + 1]; 2328 sortedSymbol_t sortedSymbol[HUFv06_MAX_SYMBOL_VALUE + 1]; 2329 U32 rankStats[HUFv06_ABSOLUTEMAX_TABLELOG + 1] = { 0 }; 2330 U32 rankStart0[HUFv06_ABSOLUTEMAX_TABLELOG + 2] = { 0 }; 2331 U32* const rankStart = rankStart0+1; 2332 rankVal_t rankVal; 2333 U32 tableLog, maxW, sizeOfSort, nbSymbols; 2334 const U32 memLog = DTable[0]; 2335 size_t iSize; 2336 void* dtPtr = DTable; 2337 HUFv06_DEltX4* const dt = ((HUFv06_DEltX4*)dtPtr) + 1; 2338 2339 HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */ 2340 if (memLog > HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge); 2341 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */ 2342 2343 iSize = HUFv06_readStats(weightList, HUFv06_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize); 2344 if (HUFv06_isError(iSize)) return iSize; 2345 2346 /* check result */ 2347 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */ 2348 2349 /* find maxWeight */ 2350 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */ 2351 2352 /* Get start index of each weight */ 2353 { U32 w, nextRankStart = 0; 2354 for (w=1; w<maxW+1; w++) { 2355 U32 current = nextRankStart; 2356 nextRankStart += rankStats[w]; 2357 rankStart[w] = current; 2358 } 2359 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/ 2360 sizeOfSort = nextRankStart; 2361 } 2362 2363 /* sort symbols by weight */ 2364 { U32 s; 2365 for (s=0; s<nbSymbols; s++) { 2366 U32 const w = weightList[s]; 2367 U32 const r = rankStart[w]++; 2368 sortedSymbol[r].symbol = (BYTE)s; 2369 sortedSymbol[r].weight = (BYTE)w; 2370 } 2371 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */ 2372 } 2373 2374 /* Build rankVal */ 2375 { U32* const rankVal0 = rankVal[0]; 2376 { int const rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */ 2377 U32 nextRankVal = 0; 2378 U32 w; 2379 for (w=1; w<maxW+1; w++) { 2380 U32 current = nextRankVal; 2381 nextRankVal += rankStats[w] << (w+rescale); 2382 rankVal0[w] = current; 2383 } } 2384 { U32 const minBits = tableLog+1 - maxW; 2385 U32 consumed; 2386 for (consumed = minBits; consumed < memLog - minBits + 1; consumed++) { 2387 U32* const rankValPtr = rankVal[consumed]; 2388 U32 w; 2389 for (w = 1; w < maxW+1; w++) { 2390 rankValPtr[w] = rankVal0[w] >> consumed; 2391 } } } } 2392 2393 HUFv06_fillDTableX4(dt, memLog, 2394 sortedSymbol, sizeOfSort, 2395 rankStart0, rankVal, maxW, 2396 tableLog+1); 2397 2398 return iSize; 2399 } 2400 2401 2402 static U32 HUFv06_decodeSymbolX4(void* op, BITv06_DStream_t* DStream, const HUFv06_DEltX4* dt, const U32 dtLog) 2403 { 2404 const size_t val = BITv06_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 2405 memcpy(op, dt+val, 2); 2406 BITv06_skipBits(DStream, dt[val].nbBits); 2407 return dt[val].length; 2408 } 2409 2410 static U32 HUFv06_decodeLastSymbolX4(void* op, BITv06_DStream_t* DStream, const HUFv06_DEltX4* dt, const U32 dtLog) 2411 { 2412 const size_t val = BITv06_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 2413 memcpy(op, dt+val, 1); 2414 if (dt[val].length==1) BITv06_skipBits(DStream, dt[val].nbBits); 2415 else { 2416 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) { 2417 BITv06_skipBits(DStream, dt[val].nbBits); 2418 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8)) 2419 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 */ 2420 } } 2421 return 1; 2422 } 2423 2424 2425 #define HUFv06_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \ 2426 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2427 2428 #define HUFv06_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \ 2429 if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \ 2430 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2431 2432 #define HUFv06_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \ 2433 if (MEM_64bits()) \ 2434 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2435 2436 static inline size_t HUFv06_decodeStreamX4(BYTE* p, BITv06_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv06_DEltX4* const dt, const U32 dtLog) 2437 { 2438 BYTE* const pStart = p; 2439 2440 /* up to 8 symbols at a time */ 2441 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p < pEnd-7)) { 2442 HUFv06_DECODE_SYMBOLX4_2(p, bitDPtr); 2443 HUFv06_DECODE_SYMBOLX4_1(p, bitDPtr); 2444 HUFv06_DECODE_SYMBOLX4_2(p, bitDPtr); 2445 HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr); 2446 } 2447 2448 /* closer to the end */ 2449 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p <= pEnd-2)) 2450 HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr); 2451 2452 while (p <= pEnd-2) 2453 HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */ 2454 2455 if (p < pEnd) 2456 p += HUFv06_decodeLastSymbolX4(p, bitDPtr, dt, dtLog); 2457 2458 return p-pStart; 2459 } 2460 2461 2462 size_t HUFv06_decompress1X4_usingDTable( 2463 void* dst, size_t dstSize, 2464 const void* cSrc, size_t cSrcSize, 2465 const U32* DTable) 2466 { 2467 const BYTE* const istart = (const BYTE*) cSrc; 2468 BYTE* const ostart = (BYTE*) dst; 2469 BYTE* const oend = ostart + dstSize; 2470 2471 const U32 dtLog = DTable[0]; 2472 const void* const dtPtr = DTable; 2473 const HUFv06_DEltX4* const dt = ((const HUFv06_DEltX4*)dtPtr) +1; 2474 2475 /* Init */ 2476 BITv06_DStream_t bitD; 2477 { size_t const errorCode = BITv06_initDStream(&bitD, istart, cSrcSize); 2478 if (HUFv06_isError(errorCode)) return errorCode; } 2479 2480 /* decode */ 2481 HUFv06_decodeStreamX4(ostart, &bitD, oend, dt, dtLog); 2482 2483 /* check */ 2484 if (!BITv06_endOfDStream(&bitD)) return ERROR(corruption_detected); 2485 2486 /* decoded size */ 2487 return dstSize; 2488 } 2489 2490 size_t HUFv06_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2491 { 2492 HUFv06_CREATE_STATIC_DTABLEX4(DTable, HUFv06_MAX_TABLELOG); 2493 const BYTE* ip = (const BYTE*) cSrc; 2494 2495 size_t const hSize = HUFv06_readDTableX4 (DTable, cSrc, cSrcSize); 2496 if (HUFv06_isError(hSize)) return hSize; 2497 if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 2498 ip += hSize; 2499 cSrcSize -= hSize; 2500 2501 return HUFv06_decompress1X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2502 } 2503 2504 size_t HUFv06_decompress4X4_usingDTable( 2505 void* dst, size_t dstSize, 2506 const void* cSrc, size_t cSrcSize, 2507 const U32* DTable) 2508 { 2509 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 2510 2511 { const BYTE* const istart = (const BYTE*) cSrc; 2512 BYTE* const ostart = (BYTE*) dst; 2513 BYTE* const oend = ostart + dstSize; 2514 const void* const dtPtr = DTable; 2515 const HUFv06_DEltX4* const dt = ((const HUFv06_DEltX4*)dtPtr) +1; 2516 const U32 dtLog = DTable[0]; 2517 size_t errorCode; 2518 2519 /* Init */ 2520 BITv06_DStream_t bitD1; 2521 BITv06_DStream_t bitD2; 2522 BITv06_DStream_t bitD3; 2523 BITv06_DStream_t bitD4; 2524 const size_t length1 = MEM_readLE16(istart); 2525 const size_t length2 = MEM_readLE16(istart+2); 2526 const size_t length3 = MEM_readLE16(istart+4); 2527 size_t length4; 2528 const BYTE* const istart1 = istart + 6; /* jumpTable */ 2529 const BYTE* const istart2 = istart1 + length1; 2530 const BYTE* const istart3 = istart2 + length2; 2531 const BYTE* const istart4 = istart3 + length3; 2532 const size_t segmentSize = (dstSize+3) / 4; 2533 BYTE* const opStart2 = ostart + segmentSize; 2534 BYTE* const opStart3 = opStart2 + segmentSize; 2535 BYTE* const opStart4 = opStart3 + segmentSize; 2536 BYTE* op1 = ostart; 2537 BYTE* op2 = opStart2; 2538 BYTE* op3 = opStart3; 2539 BYTE* op4 = opStart4; 2540 U32 endSignal; 2541 2542 length4 = cSrcSize - (length1 + length2 + length3 + 6); 2543 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 2544 errorCode = BITv06_initDStream(&bitD1, istart1, length1); 2545 if (HUFv06_isError(errorCode)) return errorCode; 2546 errorCode = BITv06_initDStream(&bitD2, istart2, length2); 2547 if (HUFv06_isError(errorCode)) return errorCode; 2548 errorCode = BITv06_initDStream(&bitD3, istart3, length3); 2549 if (HUFv06_isError(errorCode)) return errorCode; 2550 errorCode = BITv06_initDStream(&bitD4, istart4, length4); 2551 if (HUFv06_isError(errorCode)) return errorCode; 2552 2553 /* 16-32 symbols per loop (4-8 symbols per stream) */ 2554 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4); 2555 for ( ; (endSignal==BITv06_DStream_unfinished) && (op4<(oend-7)) ; ) { 2556 HUFv06_DECODE_SYMBOLX4_2(op1, &bitD1); 2557 HUFv06_DECODE_SYMBOLX4_2(op2, &bitD2); 2558 HUFv06_DECODE_SYMBOLX4_2(op3, &bitD3); 2559 HUFv06_DECODE_SYMBOLX4_2(op4, &bitD4); 2560 HUFv06_DECODE_SYMBOLX4_1(op1, &bitD1); 2561 HUFv06_DECODE_SYMBOLX4_1(op2, &bitD2); 2562 HUFv06_DECODE_SYMBOLX4_1(op3, &bitD3); 2563 HUFv06_DECODE_SYMBOLX4_1(op4, &bitD4); 2564 HUFv06_DECODE_SYMBOLX4_2(op1, &bitD1); 2565 HUFv06_DECODE_SYMBOLX4_2(op2, &bitD2); 2566 HUFv06_DECODE_SYMBOLX4_2(op3, &bitD3); 2567 HUFv06_DECODE_SYMBOLX4_2(op4, &bitD4); 2568 HUFv06_DECODE_SYMBOLX4_0(op1, &bitD1); 2569 HUFv06_DECODE_SYMBOLX4_0(op2, &bitD2); 2570 HUFv06_DECODE_SYMBOLX4_0(op3, &bitD3); 2571 HUFv06_DECODE_SYMBOLX4_0(op4, &bitD4); 2572 2573 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4); 2574 } 2575 2576 /* check corruption */ 2577 if (op1 > opStart2) return ERROR(corruption_detected); 2578 if (op2 > opStart3) return ERROR(corruption_detected); 2579 if (op3 > opStart4) return ERROR(corruption_detected); 2580 /* note : op4 supposed already verified within main loop */ 2581 2582 /* finish bitStreams one by one */ 2583 HUFv06_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog); 2584 HUFv06_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog); 2585 HUFv06_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog); 2586 HUFv06_decodeStreamX4(op4, &bitD4, oend, dt, dtLog); 2587 2588 /* check */ 2589 endSignal = BITv06_endOfDStream(&bitD1) & BITv06_endOfDStream(&bitD2) & BITv06_endOfDStream(&bitD3) & BITv06_endOfDStream(&bitD4); 2590 if (!endSignal) return ERROR(corruption_detected); 2591 2592 /* decoded size */ 2593 return dstSize; 2594 } 2595 } 2596 2597 2598 size_t HUFv06_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2599 { 2600 HUFv06_CREATE_STATIC_DTABLEX4(DTable, HUFv06_MAX_TABLELOG); 2601 const BYTE* ip = (const BYTE*) cSrc; 2602 2603 size_t hSize = HUFv06_readDTableX4 (DTable, cSrc, cSrcSize); 2604 if (HUFv06_isError(hSize)) return hSize; 2605 if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 2606 ip += hSize; 2607 cSrcSize -= hSize; 2608 2609 return HUFv06_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2610 } 2611 2612 2613 2614 2615 /* ********************************/ 2616 /* Generic decompression selector */ 2617 /* ********************************/ 2618 2619 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t; 2620 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] = 2621 { 2622 /* single, double, quad */ 2623 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */ 2624 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */ 2625 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */ 2626 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */ 2627 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */ 2628 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */ 2629 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */ 2630 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */ 2631 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */ 2632 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */ 2633 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */ 2634 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */ 2635 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */ 2636 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */ 2637 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */ 2638 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */ 2639 }; 2640 2641 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); 2642 2643 size_t HUFv06_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2644 { 2645 static const decompressionAlgo decompress[3] = { HUFv06_decompress4X2, HUFv06_decompress4X4, NULL }; 2646 U32 Dtime[3]; /* decompression time estimation */ 2647 2648 /* validation checks */ 2649 if (dstSize == 0) return ERROR(dstSize_tooSmall); 2650 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */ 2651 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */ 2652 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */ 2653 2654 /* decoder timing evaluation */ 2655 { U32 const Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */ 2656 U32 const D256 = (U32)(dstSize >> 8); 2657 U32 n; for (n=0; n<3; n++) 2658 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256); 2659 } 2660 2661 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */ 2662 2663 { U32 algoNb = 0; 2664 if (Dtime[1] < Dtime[0]) algoNb = 1; 2665 // if (Dtime[2] < Dtime[algoNb]) algoNb = 2; /* current speed of HUFv06_decompress4X6 is not good */ 2666 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize); 2667 } 2668 2669 //return HUFv06_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */ 2670 //return HUFv06_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */ 2671 //return HUFv06_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */ 2672 } 2673 /* 2674 Common functions of Zstd compression library 2675 Copyright (C) 2015-2016, Yann Collet. 2676 2677 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 2678 2679 Redistribution and use in source and binary forms, with or without 2680 modification, are permitted provided that the following conditions are 2681 met: 2682 * Redistributions of source code must retain the above copyright 2683 notice, this list of conditions and the following disclaimer. 2684 * Redistributions in binary form must reproduce the above 2685 copyright notice, this list of conditions and the following disclaimer 2686 in the documentation and/or other materials provided with the 2687 distribution. 2688 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2689 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2690 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2691 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2692 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2693 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2694 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2695 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2696 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2697 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2698 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2699 2700 You can contact the author at : 2701 - zstd homepage : http://www.zstd.net/ 2702 */ 2703 2704 2705 /*-**************************************** 2706 * Version 2707 ******************************************/ 2708 2709 /*-**************************************** 2710 * ZSTD Error Management 2711 ******************************************/ 2712 /*! ZSTDv06_isError() : 2713 * tells if a return value is an error code */ 2714 unsigned ZSTDv06_isError(size_t code) { return ERR_isError(code); } 2715 2716 /*! ZSTDv06_getErrorName() : 2717 * provides error code string from function result (useful for debugging) */ 2718 const char* ZSTDv06_getErrorName(size_t code) { return ERR_getErrorName(code); } 2719 2720 2721 /* ************************************************************** 2722 * ZBUFF Error Management 2723 ****************************************************************/ 2724 unsigned ZBUFFv06_isError(size_t errorCode) { return ERR_isError(errorCode); } 2725 2726 const char* ZBUFFv06_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); } 2727 /* 2728 zstd - standard compression library 2729 Copyright (C) 2014-2016, Yann Collet. 2730 2731 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 2732 2733 Redistribution and use in source and binary forms, with or without 2734 modification, are permitted provided that the following conditions are 2735 met: 2736 * Redistributions of source code must retain the above copyright 2737 notice, this list of conditions and the following disclaimer. 2738 * Redistributions in binary form must reproduce the above 2739 copyright notice, this list of conditions and the following disclaimer 2740 in the documentation and/or other materials provided with the 2741 distribution. 2742 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2743 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2744 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2745 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2746 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2747 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2748 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2749 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2750 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2751 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2752 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2753 2754 You can contact the author at : 2755 - zstd homepage : http://www.zstd.net 2756 */ 2757 2758 /* *************************************************************** 2759 * Tuning parameters 2760 *****************************************************************/ 2761 /*! 2762 * HEAPMODE : 2763 * Select how default decompression function ZSTDv06_decompress() will allocate memory, 2764 * in memory stack (0), or in memory heap (1, requires malloc()) 2765 */ 2766 #ifndef ZSTDv06_HEAPMODE 2767 # define ZSTDv06_HEAPMODE 1 2768 #endif 2769 2770 2771 2772 /*-******************************************************* 2773 * Compiler specifics 2774 *********************************************************/ 2775 #ifdef _MSC_VER /* Visual Studio */ 2776 # include <intrin.h> /* For Visual 2005 */ 2777 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 2778 # pragma warning(disable : 4324) /* disable: C4324: padded structure */ 2779 #endif 2780 2781 2782 /*-************************************* 2783 * Macros 2784 ***************************************/ 2785 #define ZSTDv06_isError ERR_isError /* for inlining */ 2786 #define FSEv06_isError ERR_isError 2787 #define HUFv06_isError ERR_isError 2788 2789 2790 /*_******************************************************* 2791 * Memory operations 2792 **********************************************************/ 2793 static void ZSTDv06_copy4(void* dst, const void* src) { memcpy(dst, src, 4); } 2794 2795 2796 /*-************************************************************* 2797 * Context management 2798 ***************************************************************/ 2799 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader, 2800 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock } ZSTDv06_dStage; 2801 2802 struct ZSTDv06_DCtx_s 2803 { 2804 FSEv06_DTable LLTable[FSEv06_DTABLE_SIZE_U32(LLFSELog)]; 2805 FSEv06_DTable OffTable[FSEv06_DTABLE_SIZE_U32(OffFSELog)]; 2806 FSEv06_DTable MLTable[FSEv06_DTABLE_SIZE_U32(MLFSELog)]; 2807 unsigned hufTableX4[HUFv06_DTABLE_SIZE(HufLog)]; 2808 const void* previousDstEnd; 2809 const void* base; 2810 const void* vBase; 2811 const void* dictEnd; 2812 size_t expected; 2813 size_t headerSize; 2814 ZSTDv06_frameParams fParams; 2815 blockType_t bType; /* used in ZSTDv06_decompressContinue(), to transfer blockType between header decoding and block decoding stages */ 2816 ZSTDv06_dStage stage; 2817 U32 flagRepeatTable; 2818 const BYTE* litPtr; 2819 size_t litSize; 2820 BYTE litBuffer[ZSTDv06_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH]; 2821 BYTE headerBuffer[ZSTDv06_FRAMEHEADERSIZE_MAX]; 2822 }; /* typedef'd to ZSTDv06_DCtx within "zstd_static.h" */ 2823 2824 size_t ZSTDv06_sizeofDCtx (void); /* Hidden declaration */ 2825 size_t ZSTDv06_sizeofDCtx (void) { return sizeof(ZSTDv06_DCtx); } 2826 2827 size_t ZSTDv06_decompressBegin(ZSTDv06_DCtx* dctx) 2828 { 2829 dctx->expected = ZSTDv06_frameHeaderSize_min; 2830 dctx->stage = ZSTDds_getFrameHeaderSize; 2831 dctx->previousDstEnd = NULL; 2832 dctx->base = NULL; 2833 dctx->vBase = NULL; 2834 dctx->dictEnd = NULL; 2835 dctx->hufTableX4[0] = HufLog; 2836 dctx->flagRepeatTable = 0; 2837 return 0; 2838 } 2839 2840 ZSTDv06_DCtx* ZSTDv06_createDCtx(void) 2841 { 2842 ZSTDv06_DCtx* dctx = (ZSTDv06_DCtx*)malloc(sizeof(ZSTDv06_DCtx)); 2843 if (dctx==NULL) return NULL; 2844 ZSTDv06_decompressBegin(dctx); 2845 return dctx; 2846 } 2847 2848 size_t ZSTDv06_freeDCtx(ZSTDv06_DCtx* dctx) 2849 { 2850 free(dctx); 2851 return 0; /* reserved as a potential error code in the future */ 2852 } 2853 2854 void ZSTDv06_copyDCtx(ZSTDv06_DCtx* dstDCtx, const ZSTDv06_DCtx* srcDCtx) 2855 { 2856 memcpy(dstDCtx, srcDCtx, 2857 sizeof(ZSTDv06_DCtx) - (ZSTDv06_BLOCKSIZE_MAX+WILDCOPY_OVERLENGTH + ZSTDv06_frameHeaderSize_max)); /* no need to copy workspace */ 2858 } 2859 2860 2861 /*-************************************************************* 2862 * Decompression section 2863 ***************************************************************/ 2864 2865 /* Frame format description 2866 Frame Header - [ Block Header - Block ] - Frame End 2867 1) Frame Header 2868 - 4 bytes - Magic Number : ZSTDv06_MAGICNUMBER (defined within zstd_static.h) 2869 - 1 byte - Frame Descriptor 2870 2) Block Header 2871 - 3 bytes, starting with a 2-bits descriptor 2872 Uncompressed, Compressed, Frame End, unused 2873 3) Block 2874 See Block Format Description 2875 4) Frame End 2876 - 3 bytes, compatible with Block Header 2877 */ 2878 2879 2880 /* Frame descriptor 2881 2882 1 byte, using : 2883 bit 0-3 : windowLog - ZSTDv06_WINDOWLOG_ABSOLUTEMIN (see zstd_internal.h) 2884 bit 4 : minmatch 4(0) or 3(1) 2885 bit 5 : reserved (must be zero) 2886 bit 6-7 : Frame content size : unknown, 1 byte, 2 bytes, 8 bytes 2887 2888 Optional : content size (0, 1, 2 or 8 bytes) 2889 0 : unknown 2890 1 : 0-255 bytes 2891 2 : 256 - 65535+256 2892 8 : up to 16 exa 2893 */ 2894 2895 2896 /* Compressed Block, format description 2897 2898 Block = Literal Section - Sequences Section 2899 Prerequisite : size of (compressed) block, maximum size of regenerated data 2900 2901 1) Literal Section 2902 2903 1.1) Header : 1-5 bytes 2904 flags: 2 bits 2905 00 compressed by Huff0 2906 01 unused 2907 10 is Raw (uncompressed) 2908 11 is Rle 2909 Note : using 01 => Huff0 with precomputed table ? 2910 Note : delta map ? => compressed ? 2911 2912 1.1.1) Huff0-compressed literal block : 3-5 bytes 2913 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream 2914 srcSize < 1 KB => 3 bytes (2-2-10-10) 2915 srcSize < 16KB => 4 bytes (2-2-14-14) 2916 else => 5 bytes (2-2-18-18) 2917 big endian convention 2918 2919 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes 2920 size : 5 bits: (IS_RAW<<6) + (0<<4) + size 2921 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8) 2922 size&255 2923 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16) 2924 size>>8&255 2925 size&255 2926 2927 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes 2928 size : 5 bits: (IS_RLE<<6) + (0<<4) + size 2929 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8) 2930 size&255 2931 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16) 2932 size>>8&255 2933 size&255 2934 2935 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes 2936 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream 2937 srcSize < 1 KB => 3 bytes (2-2-10-10) 2938 srcSize < 16KB => 4 bytes (2-2-14-14) 2939 else => 5 bytes (2-2-18-18) 2940 big endian convention 2941 2942 1- CTable available (stored into workspace ?) 2943 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?) 2944 2945 2946 1.2) Literal block content 2947 2948 1.2.1) Huff0 block, using sizes from header 2949 See Huff0 format 2950 2951 1.2.2) Huff0 block, using prepared table 2952 2953 1.2.3) Raw content 2954 2955 1.2.4) single byte 2956 2957 2958 2) Sequences section 2959 TO DO 2960 */ 2961 2962 /** ZSTDv06_frameHeaderSize() : 2963 * srcSize must be >= ZSTDv06_frameHeaderSize_min. 2964 * @return : size of the Frame Header */ 2965 static size_t ZSTDv06_frameHeaderSize(const void* src, size_t srcSize) 2966 { 2967 if (srcSize < ZSTDv06_frameHeaderSize_min) return ERROR(srcSize_wrong); 2968 { U32 const fcsId = (((const BYTE*)src)[4]) >> 6; 2969 return ZSTDv06_frameHeaderSize_min + ZSTDv06_fcs_fieldSize[fcsId]; } 2970 } 2971 2972 2973 /** ZSTDv06_getFrameParams() : 2974 * decode Frame Header, or provide expected `srcSize`. 2975 * @return : 0, `fparamsPtr` is correctly filled, 2976 * >0, `srcSize` is too small, result is expected `srcSize`, 2977 * or an error code, which can be tested using ZSTDv06_isError() */ 2978 size_t ZSTDv06_getFrameParams(ZSTDv06_frameParams* fparamsPtr, const void* src, size_t srcSize) 2979 { 2980 const BYTE* ip = (const BYTE*)src; 2981 2982 if (srcSize < ZSTDv06_frameHeaderSize_min) return ZSTDv06_frameHeaderSize_min; 2983 if (MEM_readLE32(src) != ZSTDv06_MAGICNUMBER) return ERROR(prefix_unknown); 2984 2985 /* ensure there is enough `srcSize` to fully read/decode frame header */ 2986 { size_t const fhsize = ZSTDv06_frameHeaderSize(src, srcSize); 2987 if (srcSize < fhsize) return fhsize; } 2988 2989 memset(fparamsPtr, 0, sizeof(*fparamsPtr)); 2990 { BYTE const frameDesc = ip[4]; 2991 fparamsPtr->windowLog = (frameDesc & 0xF) + ZSTDv06_WINDOWLOG_ABSOLUTEMIN; 2992 if ((frameDesc & 0x20) != 0) return ERROR(frameParameter_unsupported); /* reserved 1 bit */ 2993 switch(frameDesc >> 6) /* fcsId */ 2994 { 2995 default: /* impossible */ 2996 case 0 : fparamsPtr->frameContentSize = 0; break; 2997 case 1 : fparamsPtr->frameContentSize = ip[5]; break; 2998 case 2 : fparamsPtr->frameContentSize = MEM_readLE16(ip+5)+256; break; 2999 case 3 : fparamsPtr->frameContentSize = MEM_readLE64(ip+5); break; 3000 } } 3001 return 0; 3002 } 3003 3004 3005 /** ZSTDv06_decodeFrameHeader() : 3006 * `srcSize` must be the size provided by ZSTDv06_frameHeaderSize(). 3007 * @return : 0 if success, or an error code, which can be tested using ZSTDv06_isError() */ 3008 static size_t ZSTDv06_decodeFrameHeader(ZSTDv06_DCtx* zc, const void* src, size_t srcSize) 3009 { 3010 size_t const result = ZSTDv06_getFrameParams(&(zc->fParams), src, srcSize); 3011 if ((MEM_32bits()) && (zc->fParams.windowLog > 25)) return ERROR(frameParameter_unsupported); 3012 return result; 3013 } 3014 3015 3016 typedef struct 3017 { 3018 blockType_t blockType; 3019 U32 origSize; 3020 } blockProperties_t; 3021 3022 /*! ZSTDv06_getcBlockSize() : 3023 * Provides the size of compressed block from block header `src` */ 3024 static size_t ZSTDv06_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr) 3025 { 3026 const BYTE* const in = (const BYTE* const)src; 3027 U32 cSize; 3028 3029 if (srcSize < ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong); 3030 3031 bpPtr->blockType = (blockType_t)((*in) >> 6); 3032 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16); 3033 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0; 3034 3035 if (bpPtr->blockType == bt_end) return 0; 3036 if (bpPtr->blockType == bt_rle) return 1; 3037 return cSize; 3038 } 3039 3040 3041 static size_t ZSTDv06_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize) 3042 { 3043 if (dst==NULL) return ERROR(dstSize_tooSmall); 3044 if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall); 3045 memcpy(dst, src, srcSize); 3046 return srcSize; 3047 } 3048 3049 3050 /*! ZSTDv06_decodeLiteralsBlock() : 3051 @return : nb of bytes read from src (< srcSize ) */ 3052 static size_t ZSTDv06_decodeLiteralsBlock(ZSTDv06_DCtx* dctx, 3053 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */ 3054 { 3055 const BYTE* const istart = (const BYTE*) src; 3056 3057 /* any compressed block with literals segment must be at least this size */ 3058 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected); 3059 3060 switch(istart[0]>> 6) 3061 { 3062 case IS_HUF: 3063 { size_t litSize, litCSize, singleStream=0; 3064 U32 lhSize = ((istart[0]) >> 4) & 3; 3065 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */ 3066 switch(lhSize) 3067 { 3068 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ 3069 /* 2 - 2 - 10 - 10 */ 3070 lhSize=3; 3071 singleStream = istart[0] & 16; 3072 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2); 3073 litCSize = ((istart[1] & 3) << 8) + istart[2]; 3074 break; 3075 case 2: 3076 /* 2 - 2 - 14 - 14 */ 3077 lhSize=4; 3078 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6); 3079 litCSize = ((istart[2] & 63) << 8) + istart[3]; 3080 break; 3081 case 3: 3082 /* 2 - 2 - 18 - 18 */ 3083 lhSize=5; 3084 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2); 3085 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4]; 3086 break; 3087 } 3088 if (litSize > ZSTDv06_BLOCKSIZE_MAX) return ERROR(corruption_detected); 3089 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected); 3090 3091 if (HUFv06_isError(singleStream ? 3092 HUFv06_decompress1X2(dctx->litBuffer, litSize, istart+lhSize, litCSize) : 3093 HUFv06_decompress (dctx->litBuffer, litSize, istart+lhSize, litCSize) )) 3094 return ERROR(corruption_detected); 3095 3096 dctx->litPtr = dctx->litBuffer; 3097 dctx->litSize = litSize; 3098 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 3099 return litCSize + lhSize; 3100 } 3101 case IS_PCH: 3102 { size_t litSize, litCSize; 3103 U32 lhSize = ((istart[0]) >> 4) & 3; 3104 if (lhSize != 1) /* only case supported for now : small litSize, single stream */ 3105 return ERROR(corruption_detected); 3106 if (!dctx->flagRepeatTable) 3107 return ERROR(dictionary_corrupted); 3108 3109 /* 2 - 2 - 10 - 10 */ 3110 lhSize=3; 3111 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2); 3112 litCSize = ((istart[1] & 3) << 8) + istart[2]; 3113 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected); 3114 3115 { size_t const errorCode = HUFv06_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTableX4); 3116 if (HUFv06_isError(errorCode)) return ERROR(corruption_detected); 3117 } 3118 dctx->litPtr = dctx->litBuffer; 3119 dctx->litSize = litSize; 3120 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 3121 return litCSize + lhSize; 3122 } 3123 case IS_RAW: 3124 { size_t litSize; 3125 U32 lhSize = ((istart[0]) >> 4) & 3; 3126 switch(lhSize) 3127 { 3128 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ 3129 lhSize=1; 3130 litSize = istart[0] & 31; 3131 break; 3132 case 2: 3133 litSize = ((istart[0] & 15) << 8) + istart[1]; 3134 break; 3135 case 3: 3136 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2]; 3137 break; 3138 } 3139 3140 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */ 3141 if (litSize+lhSize > srcSize) return ERROR(corruption_detected); 3142 memcpy(dctx->litBuffer, istart+lhSize, litSize); 3143 dctx->litPtr = dctx->litBuffer; 3144 dctx->litSize = litSize; 3145 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 3146 return lhSize+litSize; 3147 } 3148 /* direct reference into compressed stream */ 3149 dctx->litPtr = istart+lhSize; 3150 dctx->litSize = litSize; 3151 return lhSize+litSize; 3152 } 3153 case IS_RLE: 3154 { size_t litSize; 3155 U32 lhSize = ((istart[0]) >> 4) & 3; 3156 switch(lhSize) 3157 { 3158 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ 3159 lhSize = 1; 3160 litSize = istart[0] & 31; 3161 break; 3162 case 2: 3163 litSize = ((istart[0] & 15) << 8) + istart[1]; 3164 break; 3165 case 3: 3166 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2]; 3167 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */ 3168 break; 3169 } 3170 if (litSize > ZSTDv06_BLOCKSIZE_MAX) return ERROR(corruption_detected); 3171 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH); 3172 dctx->litPtr = dctx->litBuffer; 3173 dctx->litSize = litSize; 3174 return lhSize+1; 3175 } 3176 default: 3177 return ERROR(corruption_detected); /* impossible */ 3178 } 3179 } 3180 3181 3182 /*! ZSTDv06_buildSeqTable() : 3183 @return : nb bytes read from src, 3184 or an error code if it fails, testable with ZSTDv06_isError() 3185 */ 3186 static size_t ZSTDv06_buildSeqTable(FSEv06_DTable* DTable, U32 type, U32 max, U32 maxLog, 3187 const void* src, size_t srcSize, 3188 const S16* defaultNorm, U32 defaultLog, U32 flagRepeatTable) 3189 { 3190 switch(type) 3191 { 3192 case FSEv06_ENCODING_RLE : 3193 if (!srcSize) return ERROR(srcSize_wrong); 3194 if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected); 3195 FSEv06_buildDTable_rle(DTable, *(const BYTE*)src); /* if *src > max, data is corrupted */ 3196 return 1; 3197 case FSEv06_ENCODING_RAW : 3198 FSEv06_buildDTable(DTable, defaultNorm, max, defaultLog); 3199 return 0; 3200 case FSEv06_ENCODING_STATIC: 3201 if (!flagRepeatTable) return ERROR(corruption_detected); 3202 return 0; 3203 default : /* impossible */ 3204 case FSEv06_ENCODING_DYNAMIC : 3205 { U32 tableLog; 3206 S16 norm[MaxSeq+1]; 3207 size_t const headerSize = FSEv06_readNCount(norm, &max, &tableLog, src, srcSize); 3208 if (FSEv06_isError(headerSize)) return ERROR(corruption_detected); 3209 if (tableLog > maxLog) return ERROR(corruption_detected); 3210 FSEv06_buildDTable(DTable, norm, max, tableLog); 3211 return headerSize; 3212 } } 3213 } 3214 3215 3216 static size_t ZSTDv06_decodeSeqHeaders(int* nbSeqPtr, 3217 FSEv06_DTable* DTableLL, FSEv06_DTable* DTableML, FSEv06_DTable* DTableOffb, U32 flagRepeatTable, 3218 const void* src, size_t srcSize) 3219 { 3220 const BYTE* const istart = (const BYTE* const)src; 3221 const BYTE* const iend = istart + srcSize; 3222 const BYTE* ip = istart; 3223 3224 /* check */ 3225 if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong); 3226 3227 /* SeqHead */ 3228 { int nbSeq = *ip++; 3229 if (!nbSeq) { *nbSeqPtr=0; return 1; } 3230 if (nbSeq > 0x7F) { 3231 if (nbSeq == 0xFF) { 3232 if (ip+2 > iend) return ERROR(srcSize_wrong); 3233 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2; 3234 } else { 3235 if (ip >= iend) return ERROR(srcSize_wrong); 3236 nbSeq = ((nbSeq-0x80)<<8) + *ip++; 3237 } 3238 } 3239 *nbSeqPtr = nbSeq; 3240 } 3241 3242 /* FSE table descriptors */ 3243 { U32 const LLtype = *ip >> 6; 3244 U32 const Offtype = (*ip >> 4) & 3; 3245 U32 const MLtype = (*ip >> 2) & 3; 3246 ip++; 3247 3248 /* check */ 3249 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */ 3250 3251 /* Build DTables */ 3252 { size_t const bhSize = ZSTDv06_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable); 3253 if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected); 3254 ip += bhSize; 3255 } 3256 { size_t const bhSize = ZSTDv06_buildSeqTable(DTableOffb, Offtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable); 3257 if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected); 3258 ip += bhSize; 3259 } 3260 { size_t const bhSize = ZSTDv06_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable); 3261 if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected); 3262 ip += bhSize; 3263 } } 3264 3265 return ip-istart; 3266 } 3267 3268 3269 typedef struct { 3270 size_t litLength; 3271 size_t matchLength; 3272 size_t offset; 3273 } seq_t; 3274 3275 typedef struct { 3276 BITv06_DStream_t DStream; 3277 FSEv06_DState_t stateLL; 3278 FSEv06_DState_t stateOffb; 3279 FSEv06_DState_t stateML; 3280 size_t prevOffset[ZSTDv06_REP_INIT]; 3281 } seqState_t; 3282 3283 3284 3285 static void ZSTDv06_decodeSequence(seq_t* seq, seqState_t* seqState) 3286 { 3287 /* Literal length */ 3288 U32 const llCode = FSEv06_peekSymbol(&(seqState->stateLL)); 3289 U32 const mlCode = FSEv06_peekSymbol(&(seqState->stateML)); 3290 U32 const ofCode = FSEv06_peekSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */ 3291 3292 U32 const llBits = LL_bits[llCode]; 3293 U32 const mlBits = ML_bits[mlCode]; 3294 U32 const ofBits = ofCode; 3295 U32 const totalBits = llBits+mlBits+ofBits; 3296 3297 static const U32 LL_base[MaxLL+1] = { 3298 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 3299 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 3300 0x2000, 0x4000, 0x8000, 0x10000 }; 3301 3302 static const U32 ML_base[MaxML+1] = { 3303 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 3304 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 3305 32, 34, 36, 38, 40, 44, 48, 56, 64, 80, 96, 0x80, 0x100, 0x200, 0x400, 0x800, 3306 0x1000, 0x2000, 0x4000, 0x8000, 0x10000 }; 3307 3308 static const U32 OF_base[MaxOff+1] = { 3309 0, 1, 3, 7, 0xF, 0x1F, 0x3F, 0x7F, 3310 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 3311 0xFFFF, 0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF, 3312 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, /*fake*/ 1, 1 }; 3313 3314 /* sequence */ 3315 { size_t offset; 3316 if (!ofCode) 3317 offset = 0; 3318 else { 3319 offset = OF_base[ofCode] + BITv06_readBits(&(seqState->DStream), ofBits); /* <= 26 bits */ 3320 if (MEM_32bits()) BITv06_reloadDStream(&(seqState->DStream)); 3321 } 3322 3323 if (offset < ZSTDv06_REP_NUM) { 3324 if (llCode == 0 && offset <= 1) offset = 1-offset; 3325 3326 if (offset != 0) { 3327 size_t temp = seqState->prevOffset[offset]; 3328 if (offset != 1) { 3329 seqState->prevOffset[2] = seqState->prevOffset[1]; 3330 } 3331 seqState->prevOffset[1] = seqState->prevOffset[0]; 3332 seqState->prevOffset[0] = offset = temp; 3333 3334 } else { 3335 offset = seqState->prevOffset[0]; 3336 } 3337 } else { 3338 offset -= ZSTDv06_REP_MOVE; 3339 seqState->prevOffset[2] = seqState->prevOffset[1]; 3340 seqState->prevOffset[1] = seqState->prevOffset[0]; 3341 seqState->prevOffset[0] = offset; 3342 } 3343 seq->offset = offset; 3344 } 3345 3346 seq->matchLength = ML_base[mlCode] + MINMATCH + ((mlCode>31) ? BITv06_readBits(&(seqState->DStream), mlBits) : 0); /* <= 16 bits */ 3347 if (MEM_32bits() && (mlBits+llBits>24)) BITv06_reloadDStream(&(seqState->DStream)); 3348 3349 seq->litLength = LL_base[llCode] + ((llCode>15) ? BITv06_readBits(&(seqState->DStream), llBits) : 0); /* <= 16 bits */ 3350 if (MEM_32bits() || 3351 (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BITv06_reloadDStream(&(seqState->DStream)); 3352 3353 /* ANS state update */ 3354 FSEv06_updateState(&(seqState->stateLL), &(seqState->DStream)); /* <= 9 bits */ 3355 FSEv06_updateState(&(seqState->stateML), &(seqState->DStream)); /* <= 9 bits */ 3356 if (MEM_32bits()) BITv06_reloadDStream(&(seqState->DStream)); /* <= 18 bits */ 3357 FSEv06_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <= 8 bits */ 3358 } 3359 3360 3361 static size_t ZSTDv06_execSequence(BYTE* op, 3362 BYTE* const oend, seq_t sequence, 3363 const BYTE** litPtr, const BYTE* const litLimit, 3364 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd) 3365 { 3366 BYTE* const oLitEnd = op + sequence.litLength; 3367 size_t const sequenceLength = sequence.litLength + sequence.matchLength; 3368 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */ 3369 BYTE* const oend_8 = oend-8; 3370 const BYTE* const iLitEnd = *litPtr + sequence.litLength; 3371 const BYTE* match = oLitEnd - sequence.offset; 3372 3373 /* check */ 3374 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */ 3375 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */ 3376 if (iLitEnd > litLimit) return ERROR(corruption_detected); /* over-read beyond lit buffer */ 3377 3378 /* copy Literals */ 3379 ZSTDv06_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */ 3380 op = oLitEnd; 3381 *litPtr = iLitEnd; /* update for next sequence */ 3382 3383 /* copy Match */ 3384 if (sequence.offset > (size_t)(oLitEnd - base)) { 3385 /* offset beyond prefix */ 3386 if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected); 3387 match = dictEnd - (base-match); 3388 if (match + sequence.matchLength <= dictEnd) { 3389 memmove(oLitEnd, match, sequence.matchLength); 3390 return sequenceLength; 3391 } 3392 /* span extDict & currentPrefixSegment */ 3393 { size_t const length1 = dictEnd - match; 3394 memmove(oLitEnd, match, length1); 3395 op = oLitEnd + length1; 3396 sequence.matchLength -= length1; 3397 match = base; 3398 if (op > oend_8 || sequence.matchLength < MINMATCH) { 3399 while (op < oMatchEnd) *op++ = *match++; 3400 return sequenceLength; 3401 } 3402 } } 3403 /* Requirement: op <= oend_8 */ 3404 3405 /* match within prefix */ 3406 if (sequence.offset < 8) { 3407 /* close range match, overlap */ 3408 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */ 3409 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */ 3410 int const sub2 = dec64table[sequence.offset]; 3411 op[0] = match[0]; 3412 op[1] = match[1]; 3413 op[2] = match[2]; 3414 op[3] = match[3]; 3415 match += dec32table[sequence.offset]; 3416 ZSTDv06_copy4(op+4, match); 3417 match -= sub2; 3418 } else { 3419 ZSTDv06_copy8(op, match); 3420 } 3421 op += 8; match += 8; 3422 3423 if (oMatchEnd > oend-(16-MINMATCH)) { 3424 if (op < oend_8) { 3425 ZSTDv06_wildcopy(op, match, oend_8 - op); 3426 match += oend_8 - op; 3427 op = oend_8; 3428 } 3429 while (op < oMatchEnd) *op++ = *match++; 3430 } else { 3431 ZSTDv06_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */ 3432 } 3433 return sequenceLength; 3434 } 3435 3436 3437 static size_t ZSTDv06_decompressSequences( 3438 ZSTDv06_DCtx* dctx, 3439 void* dst, size_t maxDstSize, 3440 const void* seqStart, size_t seqSize) 3441 { 3442 const BYTE* ip = (const BYTE*)seqStart; 3443 const BYTE* const iend = ip + seqSize; 3444 BYTE* const ostart = (BYTE* const)dst; 3445 BYTE* const oend = ostart + maxDstSize; 3446 BYTE* op = ostart; 3447 const BYTE* litPtr = dctx->litPtr; 3448 const BYTE* const litEnd = litPtr + dctx->litSize; 3449 FSEv06_DTable* DTableLL = dctx->LLTable; 3450 FSEv06_DTable* DTableML = dctx->MLTable; 3451 FSEv06_DTable* DTableOffb = dctx->OffTable; 3452 const BYTE* const base = (const BYTE*) (dctx->base); 3453 const BYTE* const vBase = (const BYTE*) (dctx->vBase); 3454 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd); 3455 int nbSeq; 3456 3457 /* Build Decoding Tables */ 3458 { size_t const seqHSize = ZSTDv06_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->flagRepeatTable, ip, seqSize); 3459 if (ZSTDv06_isError(seqHSize)) return seqHSize; 3460 ip += seqHSize; 3461 dctx->flagRepeatTable = 0; 3462 } 3463 3464 /* Regen sequences */ 3465 if (nbSeq) { 3466 seq_t sequence; 3467 seqState_t seqState; 3468 3469 memset(&sequence, 0, sizeof(sequence)); 3470 sequence.offset = REPCODE_STARTVALUE; 3471 { U32 i; for (i=0; i<ZSTDv06_REP_INIT; i++) seqState.prevOffset[i] = REPCODE_STARTVALUE; } 3472 { size_t const errorCode = BITv06_initDStream(&(seqState.DStream), ip, iend-ip); 3473 if (ERR_isError(errorCode)) return ERROR(corruption_detected); } 3474 FSEv06_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL); 3475 FSEv06_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb); 3476 FSEv06_initDState(&(seqState.stateML), &(seqState.DStream), DTableML); 3477 3478 for ( ; (BITv06_reloadDStream(&(seqState.DStream)) <= BITv06_DStream_completed) && nbSeq ; ) { 3479 nbSeq--; 3480 ZSTDv06_decodeSequence(&sequence, &seqState); 3481 3482 #if 0 /* debug */ 3483 static BYTE* start = NULL; 3484 if (start==NULL) start = op; 3485 size_t pos = (size_t)(op-start); 3486 if ((pos >= 5810037) && (pos < 5810400)) 3487 printf("Dpos %6u :%5u literals & match %3u bytes at distance %6u \n", 3488 pos, (U32)sequence.litLength, (U32)sequence.matchLength, (U32)sequence.offset); 3489 #endif 3490 3491 { size_t const oneSeqSize = ZSTDv06_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd); 3492 if (ZSTDv06_isError(oneSeqSize)) return oneSeqSize; 3493 op += oneSeqSize; 3494 } } 3495 3496 /* check if reached exact end */ 3497 if (nbSeq) return ERROR(corruption_detected); 3498 } 3499 3500 /* last literal segment */ 3501 { size_t const lastLLSize = litEnd - litPtr; 3502 if (litPtr > litEnd) return ERROR(corruption_detected); /* too many literals already used */ 3503 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall); 3504 memcpy(op, litPtr, lastLLSize); 3505 op += lastLLSize; 3506 } 3507 3508 return op-ostart; 3509 } 3510 3511 3512 static void ZSTDv06_checkContinuity(ZSTDv06_DCtx* dctx, const void* dst) 3513 { 3514 if (dst != dctx->previousDstEnd) { /* not contiguous */ 3515 dctx->dictEnd = dctx->previousDstEnd; 3516 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); 3517 dctx->base = dst; 3518 dctx->previousDstEnd = dst; 3519 } 3520 } 3521 3522 3523 static size_t ZSTDv06_decompressBlock_internal(ZSTDv06_DCtx* dctx, 3524 void* dst, size_t dstCapacity, 3525 const void* src, size_t srcSize) 3526 { /* blockType == blockCompressed */ 3527 const BYTE* ip = (const BYTE*)src; 3528 3529 if (srcSize >= ZSTDv06_BLOCKSIZE_MAX) return ERROR(srcSize_wrong); 3530 3531 /* Decode literals sub-block */ 3532 { size_t const litCSize = ZSTDv06_decodeLiteralsBlock(dctx, src, srcSize); 3533 if (ZSTDv06_isError(litCSize)) return litCSize; 3534 ip += litCSize; 3535 srcSize -= litCSize; 3536 } 3537 return ZSTDv06_decompressSequences(dctx, dst, dstCapacity, ip, srcSize); 3538 } 3539 3540 3541 size_t ZSTDv06_decompressBlock(ZSTDv06_DCtx* dctx, 3542 void* dst, size_t dstCapacity, 3543 const void* src, size_t srcSize) 3544 { 3545 ZSTDv06_checkContinuity(dctx, dst); 3546 return ZSTDv06_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize); 3547 } 3548 3549 3550 /*! ZSTDv06_decompressFrame() : 3551 * `dctx` must be properly initialized */ 3552 static size_t ZSTDv06_decompressFrame(ZSTDv06_DCtx* dctx, 3553 void* dst, size_t dstCapacity, 3554 const void* src, size_t srcSize) 3555 { 3556 const BYTE* ip = (const BYTE*)src; 3557 const BYTE* const iend = ip + srcSize; 3558 BYTE* const ostart = (BYTE* const)dst; 3559 BYTE* op = ostart; 3560 BYTE* const oend = ostart + dstCapacity; 3561 size_t remainingSize = srcSize; 3562 blockProperties_t blockProperties = { bt_compressed, 0 }; 3563 3564 /* check */ 3565 if (srcSize < ZSTDv06_frameHeaderSize_min+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong); 3566 3567 /* Frame Header */ 3568 { size_t const frameHeaderSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min); 3569 if (ZSTDv06_isError(frameHeaderSize)) return frameHeaderSize; 3570 if (srcSize < frameHeaderSize+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong); 3571 if (ZSTDv06_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected); 3572 ip += frameHeaderSize; remainingSize -= frameHeaderSize; 3573 } 3574 3575 /* Loop on each block */ 3576 while (1) { 3577 size_t decodedSize=0; 3578 size_t const cBlockSize = ZSTDv06_getcBlockSize(ip, iend-ip, &blockProperties); 3579 if (ZSTDv06_isError(cBlockSize)) return cBlockSize; 3580 3581 ip += ZSTDv06_blockHeaderSize; 3582 remainingSize -= ZSTDv06_blockHeaderSize; 3583 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); 3584 3585 switch(blockProperties.blockType) 3586 { 3587 case bt_compressed: 3588 decodedSize = ZSTDv06_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize); 3589 break; 3590 case bt_raw : 3591 decodedSize = ZSTDv06_copyRawBlock(op, oend-op, ip, cBlockSize); 3592 break; 3593 case bt_rle : 3594 return ERROR(GENERIC); /* not yet supported */ 3595 break; 3596 case bt_end : 3597 /* end of frame */ 3598 if (remainingSize) return ERROR(srcSize_wrong); 3599 break; 3600 default: 3601 return ERROR(GENERIC); /* impossible */ 3602 } 3603 if (cBlockSize == 0) break; /* bt_end */ 3604 3605 if (ZSTDv06_isError(decodedSize)) return decodedSize; 3606 op += decodedSize; 3607 ip += cBlockSize; 3608 remainingSize -= cBlockSize; 3609 } 3610 3611 return op-ostart; 3612 } 3613 3614 3615 size_t ZSTDv06_decompress_usingPreparedDCtx(ZSTDv06_DCtx* dctx, const ZSTDv06_DCtx* refDCtx, 3616 void* dst, size_t dstCapacity, 3617 const void* src, size_t srcSize) 3618 { 3619 ZSTDv06_copyDCtx(dctx, refDCtx); 3620 ZSTDv06_checkContinuity(dctx, dst); 3621 return ZSTDv06_decompressFrame(dctx, dst, dstCapacity, src, srcSize); 3622 } 3623 3624 3625 size_t ZSTDv06_decompress_usingDict(ZSTDv06_DCtx* dctx, 3626 void* dst, size_t dstCapacity, 3627 const void* src, size_t srcSize, 3628 const void* dict, size_t dictSize) 3629 { 3630 ZSTDv06_decompressBegin_usingDict(dctx, dict, dictSize); 3631 ZSTDv06_checkContinuity(dctx, dst); 3632 return ZSTDv06_decompressFrame(dctx, dst, dstCapacity, src, srcSize); 3633 } 3634 3635 3636 size_t ZSTDv06_decompressDCtx(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize) 3637 { 3638 return ZSTDv06_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0); 3639 } 3640 3641 3642 size_t ZSTDv06_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize) 3643 { 3644 #if defined(ZSTDv06_HEAPMODE) && (ZSTDv06_HEAPMODE==1) 3645 size_t regenSize; 3646 ZSTDv06_DCtx* dctx = ZSTDv06_createDCtx(); 3647 if (dctx==NULL) return ERROR(memory_allocation); 3648 regenSize = ZSTDv06_decompressDCtx(dctx, dst, dstCapacity, src, srcSize); 3649 ZSTDv06_freeDCtx(dctx); 3650 return regenSize; 3651 #else /* stack mode */ 3652 ZSTDv06_DCtx dctx; 3653 return ZSTDv06_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize); 3654 #endif 3655 } 3656 3657 size_t ZSTDv06_findFrameCompressedSize(const void* src, size_t srcSize) 3658 { 3659 const BYTE* ip = (const BYTE*)src; 3660 size_t remainingSize = srcSize; 3661 blockProperties_t blockProperties = { bt_compressed, 0 }; 3662 3663 /* Frame Header */ 3664 { size_t const frameHeaderSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min); 3665 if (ZSTDv06_isError(frameHeaderSize)) return frameHeaderSize; 3666 if (MEM_readLE32(src) != ZSTDv06_MAGICNUMBER) return ERROR(prefix_unknown); 3667 if (srcSize < frameHeaderSize+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong); 3668 ip += frameHeaderSize; remainingSize -= frameHeaderSize; 3669 } 3670 3671 /* Loop on each block */ 3672 while (1) { 3673 size_t const cBlockSize = ZSTDv06_getcBlockSize(ip, remainingSize, &blockProperties); 3674 if (ZSTDv06_isError(cBlockSize)) return cBlockSize; 3675 3676 ip += ZSTDv06_blockHeaderSize; 3677 remainingSize -= ZSTDv06_blockHeaderSize; 3678 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); 3679 3680 if (cBlockSize == 0) break; /* bt_end */ 3681 3682 ip += cBlockSize; 3683 remainingSize -= cBlockSize; 3684 } 3685 3686 return ip - (const BYTE*)src; 3687 } 3688 3689 /*_****************************** 3690 * Streaming Decompression API 3691 ********************************/ 3692 size_t ZSTDv06_nextSrcSizeToDecompress(ZSTDv06_DCtx* dctx) 3693 { 3694 return dctx->expected; 3695 } 3696 3697 size_t ZSTDv06_decompressContinue(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize) 3698 { 3699 /* Sanity check */ 3700 if (srcSize != dctx->expected) return ERROR(srcSize_wrong); 3701 if (dstCapacity) ZSTDv06_checkContinuity(dctx, dst); 3702 3703 /* Decompress : frame header; part 1 */ 3704 switch (dctx->stage) 3705 { 3706 case ZSTDds_getFrameHeaderSize : 3707 if (srcSize != ZSTDv06_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */ 3708 dctx->headerSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min); 3709 if (ZSTDv06_isError(dctx->headerSize)) return dctx->headerSize; 3710 memcpy(dctx->headerBuffer, src, ZSTDv06_frameHeaderSize_min); 3711 if (dctx->headerSize > ZSTDv06_frameHeaderSize_min) { 3712 dctx->expected = dctx->headerSize - ZSTDv06_frameHeaderSize_min; 3713 dctx->stage = ZSTDds_decodeFrameHeader; 3714 return 0; 3715 } 3716 dctx->expected = 0; /* not necessary to copy more */ 3717 /* fall-through */ 3718 case ZSTDds_decodeFrameHeader: 3719 { size_t result; 3720 memcpy(dctx->headerBuffer + ZSTDv06_frameHeaderSize_min, src, dctx->expected); 3721 result = ZSTDv06_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize); 3722 if (ZSTDv06_isError(result)) return result; 3723 dctx->expected = ZSTDv06_blockHeaderSize; 3724 dctx->stage = ZSTDds_decodeBlockHeader; 3725 return 0; 3726 } 3727 case ZSTDds_decodeBlockHeader: 3728 { blockProperties_t bp; 3729 size_t const cBlockSize = ZSTDv06_getcBlockSize(src, ZSTDv06_blockHeaderSize, &bp); 3730 if (ZSTDv06_isError(cBlockSize)) return cBlockSize; 3731 if (bp.blockType == bt_end) { 3732 dctx->expected = 0; 3733 dctx->stage = ZSTDds_getFrameHeaderSize; 3734 } else { 3735 dctx->expected = cBlockSize; 3736 dctx->bType = bp.blockType; 3737 dctx->stage = ZSTDds_decompressBlock; 3738 } 3739 return 0; 3740 } 3741 case ZSTDds_decompressBlock: 3742 { size_t rSize; 3743 switch(dctx->bType) 3744 { 3745 case bt_compressed: 3746 rSize = ZSTDv06_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize); 3747 break; 3748 case bt_raw : 3749 rSize = ZSTDv06_copyRawBlock(dst, dstCapacity, src, srcSize); 3750 break; 3751 case bt_rle : 3752 return ERROR(GENERIC); /* not yet handled */ 3753 break; 3754 case bt_end : /* should never happen (filtered at phase 1) */ 3755 rSize = 0; 3756 break; 3757 default: 3758 return ERROR(GENERIC); /* impossible */ 3759 } 3760 dctx->stage = ZSTDds_decodeBlockHeader; 3761 dctx->expected = ZSTDv06_blockHeaderSize; 3762 dctx->previousDstEnd = (char*)dst + rSize; 3763 return rSize; 3764 } 3765 default: 3766 return ERROR(GENERIC); /* impossible */ 3767 } 3768 } 3769 3770 3771 static void ZSTDv06_refDictContent(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize) 3772 { 3773 dctx->dictEnd = dctx->previousDstEnd; 3774 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); 3775 dctx->base = dict; 3776 dctx->previousDstEnd = (const char*)dict + dictSize; 3777 } 3778 3779 static size_t ZSTDv06_loadEntropy(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize) 3780 { 3781 size_t hSize, offcodeHeaderSize, matchlengthHeaderSize, litlengthHeaderSize; 3782 3783 hSize = HUFv06_readDTableX4(dctx->hufTableX4, dict, dictSize); 3784 if (HUFv06_isError(hSize)) return ERROR(dictionary_corrupted); 3785 dict = (const char*)dict + hSize; 3786 dictSize -= hSize; 3787 3788 { short offcodeNCount[MaxOff+1]; 3789 U32 offcodeMaxValue=MaxOff, offcodeLog; 3790 offcodeHeaderSize = FSEv06_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dict, dictSize); 3791 if (FSEv06_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted); 3792 if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted); 3793 { size_t const errorCode = FSEv06_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog); 3794 if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); } 3795 dict = (const char*)dict + offcodeHeaderSize; 3796 dictSize -= offcodeHeaderSize; 3797 } 3798 3799 { short matchlengthNCount[MaxML+1]; 3800 unsigned matchlengthMaxValue = MaxML, matchlengthLog; 3801 matchlengthHeaderSize = FSEv06_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dict, dictSize); 3802 if (FSEv06_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted); 3803 if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted); 3804 { size_t const errorCode = FSEv06_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog); 3805 if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); } 3806 dict = (const char*)dict + matchlengthHeaderSize; 3807 dictSize -= matchlengthHeaderSize; 3808 } 3809 3810 { short litlengthNCount[MaxLL+1]; 3811 unsigned litlengthMaxValue = MaxLL, litlengthLog; 3812 litlengthHeaderSize = FSEv06_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dict, dictSize); 3813 if (FSEv06_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted); 3814 if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted); 3815 { size_t const errorCode = FSEv06_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog); 3816 if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); } 3817 } 3818 3819 dctx->flagRepeatTable = 1; 3820 return hSize + offcodeHeaderSize + matchlengthHeaderSize + litlengthHeaderSize; 3821 } 3822 3823 static size_t ZSTDv06_decompress_insertDictionary(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize) 3824 { 3825 size_t eSize; 3826 U32 const magic = MEM_readLE32(dict); 3827 if (magic != ZSTDv06_DICT_MAGIC) { 3828 /* pure content mode */ 3829 ZSTDv06_refDictContent(dctx, dict, dictSize); 3830 return 0; 3831 } 3832 /* load entropy tables */ 3833 dict = (const char*)dict + 4; 3834 dictSize -= 4; 3835 eSize = ZSTDv06_loadEntropy(dctx, dict, dictSize); 3836 if (ZSTDv06_isError(eSize)) return ERROR(dictionary_corrupted); 3837 3838 /* reference dictionary content */ 3839 dict = (const char*)dict + eSize; 3840 dictSize -= eSize; 3841 ZSTDv06_refDictContent(dctx, dict, dictSize); 3842 3843 return 0; 3844 } 3845 3846 3847 size_t ZSTDv06_decompressBegin_usingDict(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize) 3848 { 3849 { size_t const errorCode = ZSTDv06_decompressBegin(dctx); 3850 if (ZSTDv06_isError(errorCode)) return errorCode; } 3851 3852 if (dict && dictSize) { 3853 size_t const errorCode = ZSTDv06_decompress_insertDictionary(dctx, dict, dictSize); 3854 if (ZSTDv06_isError(errorCode)) return ERROR(dictionary_corrupted); 3855 } 3856 3857 return 0; 3858 } 3859 3860 /* 3861 Buffered version of Zstd compression library 3862 Copyright (C) 2015-2016, Yann Collet. 3863 3864 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 3865 3866 Redistribution and use in source and binary forms, with or without 3867 modification, are permitted provided that the following conditions are 3868 met: 3869 * Redistributions of source code must retain the above copyright 3870 notice, this list of conditions and the following disclaimer. 3871 * Redistributions in binary form must reproduce the above 3872 copyright notice, this list of conditions and the following disclaimer 3873 in the documentation and/or other materials provided with the 3874 distribution. 3875 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 3876 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 3877 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 3878 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 3879 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3880 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3881 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3882 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3883 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3884 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3885 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3886 3887 You can contact the author at : 3888 - zstd homepage : http://www.zstd.net/ 3889 */ 3890 3891 3892 /*-*************************************************************************** 3893 * Streaming decompression howto 3894 * 3895 * A ZBUFFv06_DCtx object is required to track streaming operations. 3896 * Use ZBUFFv06_createDCtx() and ZBUFFv06_freeDCtx() to create/release resources. 3897 * Use ZBUFFv06_decompressInit() to start a new decompression operation, 3898 * or ZBUFFv06_decompressInitDictionary() if decompression requires a dictionary. 3899 * Note that ZBUFFv06_DCtx objects can be re-init multiple times. 3900 * 3901 * Use ZBUFFv06_decompressContinue() repetitively to consume your input. 3902 * *srcSizePtr and *dstCapacityPtr can be any size. 3903 * The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr. 3904 * Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again. 3905 * The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst. 3906 * @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency), 3907 * or 0 when a frame is completely decoded, 3908 * or an error code, which can be tested using ZBUFFv06_isError(). 3909 * 3910 * Hint : recommended buffer sizes (not compulsory) : ZBUFFv06_recommendedDInSize() and ZBUFFv06_recommendedDOutSize() 3911 * output : ZBUFFv06_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded. 3912 * input : ZBUFFv06_recommendedDInSize == 128KB + 3; 3913 * just follow indications from ZBUFFv06_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 . 3914 * *******************************************************************************/ 3915 3916 typedef enum { ZBUFFds_init, ZBUFFds_loadHeader, 3917 ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFFv06_dStage; 3918 3919 /* *** Resource management *** */ 3920 struct ZBUFFv06_DCtx_s { 3921 ZSTDv06_DCtx* zd; 3922 ZSTDv06_frameParams fParams; 3923 ZBUFFv06_dStage stage; 3924 char* inBuff; 3925 size_t inBuffSize; 3926 size_t inPos; 3927 char* outBuff; 3928 size_t outBuffSize; 3929 size_t outStart; 3930 size_t outEnd; 3931 size_t blockSize; 3932 BYTE headerBuffer[ZSTDv06_FRAMEHEADERSIZE_MAX]; 3933 size_t lhSize; 3934 }; /* typedef'd to ZBUFFv06_DCtx within "zstd_buffered.h" */ 3935 3936 3937 ZBUFFv06_DCtx* ZBUFFv06_createDCtx(void) 3938 { 3939 ZBUFFv06_DCtx* zbd = (ZBUFFv06_DCtx*)malloc(sizeof(ZBUFFv06_DCtx)); 3940 if (zbd==NULL) return NULL; 3941 memset(zbd, 0, sizeof(*zbd)); 3942 zbd->zd = ZSTDv06_createDCtx(); 3943 zbd->stage = ZBUFFds_init; 3944 return zbd; 3945 } 3946 3947 size_t ZBUFFv06_freeDCtx(ZBUFFv06_DCtx* zbd) 3948 { 3949 if (zbd==NULL) return 0; /* support free on null */ 3950 ZSTDv06_freeDCtx(zbd->zd); 3951 free(zbd->inBuff); 3952 free(zbd->outBuff); 3953 free(zbd); 3954 return 0; 3955 } 3956 3957 3958 /* *** Initialization *** */ 3959 3960 size_t ZBUFFv06_decompressInitDictionary(ZBUFFv06_DCtx* zbd, const void* dict, size_t dictSize) 3961 { 3962 zbd->stage = ZBUFFds_loadHeader; 3963 zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0; 3964 return ZSTDv06_decompressBegin_usingDict(zbd->zd, dict, dictSize); 3965 } 3966 3967 size_t ZBUFFv06_decompressInit(ZBUFFv06_DCtx* zbd) 3968 { 3969 return ZBUFFv06_decompressInitDictionary(zbd, NULL, 0); 3970 } 3971 3972 3973 3974 MEM_STATIC size_t ZBUFFv06_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize) 3975 { 3976 size_t length = MIN(dstCapacity, srcSize); 3977 memcpy(dst, src, length); 3978 return length; 3979 } 3980 3981 3982 /* *** Decompression *** */ 3983 3984 size_t ZBUFFv06_decompressContinue(ZBUFFv06_DCtx* zbd, 3985 void* dst, size_t* dstCapacityPtr, 3986 const void* src, size_t* srcSizePtr) 3987 { 3988 const char* const istart = (const char*)src; 3989 const char* const iend = istart + *srcSizePtr; 3990 const char* ip = istart; 3991 char* const ostart = (char*)dst; 3992 char* const oend = ostart + *dstCapacityPtr; 3993 char* op = ostart; 3994 U32 notDone = 1; 3995 3996 while (notDone) { 3997 switch(zbd->stage) 3998 { 3999 case ZBUFFds_init : 4000 return ERROR(init_missing); 4001 4002 case ZBUFFds_loadHeader : 4003 { size_t const hSize = ZSTDv06_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize); 4004 if (hSize != 0) { 4005 size_t const toLoad = hSize - zbd->lhSize; /* if hSize!=0, hSize > zbd->lhSize */ 4006 if (ZSTDv06_isError(hSize)) return hSize; 4007 if (toLoad > (size_t)(iend-ip)) { /* not enough input to load full header */ 4008 memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip); 4009 zbd->lhSize += iend-ip; 4010 *dstCapacityPtr = 0; 4011 return (hSize - zbd->lhSize) + ZSTDv06_blockHeaderSize; /* remaining header bytes + next block header */ 4012 } 4013 memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad; 4014 break; 4015 } } 4016 4017 /* Consume header */ 4018 { size_t const h1Size = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); /* == ZSTDv06_frameHeaderSize_min */ 4019 size_t const h1Result = ZSTDv06_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size); 4020 if (ZSTDv06_isError(h1Result)) return h1Result; 4021 if (h1Size < zbd->lhSize) { /* long header */ 4022 size_t const h2Size = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); 4023 size_t const h2Result = ZSTDv06_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size); 4024 if (ZSTDv06_isError(h2Result)) return h2Result; 4025 } } 4026 4027 /* Frame header instruct buffer sizes */ 4028 { size_t const blockSize = MIN(1 << zbd->fParams.windowLog, ZSTDv06_BLOCKSIZE_MAX); 4029 zbd->blockSize = blockSize; 4030 if (zbd->inBuffSize < blockSize) { 4031 free(zbd->inBuff); 4032 zbd->inBuffSize = blockSize; 4033 zbd->inBuff = (char*)malloc(blockSize); 4034 if (zbd->inBuff == NULL) return ERROR(memory_allocation); 4035 } 4036 { size_t const neededOutSize = ((size_t)1 << zbd->fParams.windowLog) + blockSize + WILDCOPY_OVERLENGTH * 2; 4037 if (zbd->outBuffSize < neededOutSize) { 4038 free(zbd->outBuff); 4039 zbd->outBuffSize = neededOutSize; 4040 zbd->outBuff = (char*)malloc(neededOutSize); 4041 if (zbd->outBuff == NULL) return ERROR(memory_allocation); 4042 } } } 4043 zbd->stage = ZBUFFds_read; 4044 /* fall-through */ 4045 case ZBUFFds_read: 4046 { size_t const neededInSize = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); 4047 if (neededInSize==0) { /* end of frame */ 4048 zbd->stage = ZBUFFds_init; 4049 notDone = 0; 4050 break; 4051 } 4052 if ((size_t)(iend-ip) >= neededInSize) { /* decode directly from src */ 4053 size_t const decodedSize = ZSTDv06_decompressContinue(zbd->zd, 4054 zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart, 4055 ip, neededInSize); 4056 if (ZSTDv06_isError(decodedSize)) return decodedSize; 4057 ip += neededInSize; 4058 if (!decodedSize) break; /* this was just a header */ 4059 zbd->outEnd = zbd->outStart + decodedSize; 4060 zbd->stage = ZBUFFds_flush; 4061 break; 4062 } 4063 if (ip==iend) { notDone = 0; break; } /* no more input */ 4064 zbd->stage = ZBUFFds_load; 4065 } 4066 /* fall-through */ 4067 case ZBUFFds_load: 4068 { size_t const neededInSize = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); 4069 size_t const toLoad = neededInSize - zbd->inPos; /* should always be <= remaining space within inBuff */ 4070 size_t loadedSize; 4071 if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected); /* should never happen */ 4072 loadedSize = ZBUFFv06_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip); 4073 ip += loadedSize; 4074 zbd->inPos += loadedSize; 4075 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */ 4076 4077 /* decode loaded input */ 4078 { size_t const decodedSize = ZSTDv06_decompressContinue(zbd->zd, 4079 zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart, 4080 zbd->inBuff, neededInSize); 4081 if (ZSTDv06_isError(decodedSize)) return decodedSize; 4082 zbd->inPos = 0; /* input is consumed */ 4083 if (!decodedSize) { zbd->stage = ZBUFFds_read; break; } /* this was just a header */ 4084 zbd->outEnd = zbd->outStart + decodedSize; 4085 zbd->stage = ZBUFFds_flush; 4086 // break; /* ZBUFFds_flush follows */ 4087 } 4088 } 4089 /* fall-through */ 4090 case ZBUFFds_flush: 4091 { size_t const toFlushSize = zbd->outEnd - zbd->outStart; 4092 size_t const flushedSize = ZBUFFv06_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize); 4093 op += flushedSize; 4094 zbd->outStart += flushedSize; 4095 if (flushedSize == toFlushSize) { 4096 zbd->stage = ZBUFFds_read; 4097 if (zbd->outStart + zbd->blockSize > zbd->outBuffSize) 4098 zbd->outStart = zbd->outEnd = 0; 4099 break; 4100 } 4101 /* cannot flush everything */ 4102 notDone = 0; 4103 break; 4104 } 4105 default: return ERROR(GENERIC); /* impossible */ 4106 } } 4107 4108 /* result */ 4109 *srcSizePtr = ip-istart; 4110 *dstCapacityPtr = op-ostart; 4111 { size_t nextSrcSizeHint = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); 4112 if (nextSrcSizeHint > ZSTDv06_blockHeaderSize) nextSrcSizeHint+= ZSTDv06_blockHeaderSize; /* get following block header too */ 4113 nextSrcSizeHint -= zbd->inPos; /* already loaded*/ 4114 return nextSrcSizeHint; 4115 } 4116 } 4117 4118 4119 4120 /* ************************************* 4121 * Tool functions 4122 ***************************************/ 4123 size_t ZBUFFv06_recommendedDInSize(void) { return ZSTDv06_BLOCKSIZE_MAX + ZSTDv06_blockHeaderSize /* block header size*/ ; } 4124 size_t ZBUFFv06_recommendedDOutSize(void) { return ZSTDv06_BLOCKSIZE_MAX; } 4125