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