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