1 /* 2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc. 3 * All rights reserved. 4 * 5 * This source code is licensed under both the BSD-style license (found in the 6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found 7 * in the COPYING file in the root directory of this source tree). 8 * You may select, at your option, one of the above-listed licenses. 9 */ 10 11 12 /*- Dependencies -*/ 13 #include "zstd_v04.h" 14 #include "error_private.h" 15 16 17 /* ****************************************************************** 18 mem.h 19 ****************************************************************** */ 20 #ifndef MEM_H_MODULE 21 #define MEM_H_MODULE 22 23 #if defined (__cplusplus) 24 extern "C" { 25 #endif 26 27 /****************************************** 28 * Includes 29 ******************************************/ 30 #include <stddef.h> /* size_t, ptrdiff_t */ 31 #include <string.h> /* memcpy */ 32 33 34 /****************************************** 35 * Compiler-specific 36 ******************************************/ 37 #if defined(_MSC_VER) /* Visual Studio */ 38 # include <stdlib.h> /* _byteswap_ulong */ 39 # include <intrin.h> /* _byteswap_* */ 40 #endif 41 #if defined(__GNUC__) 42 # define MEM_STATIC static __attribute__((unused)) 43 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 44 # define MEM_STATIC static inline 45 #elif defined(_MSC_VER) 46 # define MEM_STATIC static __inline 47 #else 48 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */ 49 #endif 50 51 52 /**************************************************************** 53 * Basic Types 54 *****************************************************************/ 55 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 56 # include <stdint.h> 57 typedef uint8_t BYTE; 58 typedef uint16_t U16; 59 typedef int16_t S16; 60 typedef uint32_t U32; 61 typedef int32_t S32; 62 typedef uint64_t U64; 63 typedef int64_t S64; 64 #else 65 typedef unsigned char BYTE; 66 typedef unsigned short U16; 67 typedef signed short S16; 68 typedef unsigned int U32; 69 typedef signed int S32; 70 typedef unsigned long long U64; 71 typedef signed long long S64; 72 #endif 73 74 75 /*-************************************* 76 * Debug 77 ***************************************/ 78 #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=1) 79 # include <assert.h> 80 #else 81 # ifndef assert 82 # define assert(condition) ((void)0) 83 # endif 84 #endif 85 86 #define ZSTD_STATIC_ASSERT(c) { enum { ZSTD_static_assert = 1/(int)(!!(c)) }; } 87 88 #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=2) 89 # include <stdio.h> 90 extern int g_debuglog_enable; 91 /* recommended values for ZSTD_DEBUG display levels : 92 * 1 : no display, enables assert() only 93 * 2 : reserved for currently active debug path 94 * 3 : events once per object lifetime (CCtx, CDict, etc.) 95 * 4 : events once per frame 96 * 5 : events once per block 97 * 6 : events once per sequence (*very* verbose) */ 98 # define RAWLOG(l, ...) { \ 99 if ((g_debuglog_enable) & (l<=ZSTD_DEBUG)) { \ 100 fprintf(stderr, __VA_ARGS__); \ 101 } } 102 # define DEBUGLOG(l, ...) { \ 103 if ((g_debuglog_enable) & (l<=ZSTD_DEBUG)) { \ 104 fprintf(stderr, __FILE__ ": " __VA_ARGS__); \ 105 fprintf(stderr, " \n"); \ 106 } } 107 #else 108 # define RAWLOG(l, ...) {} /* disabled */ 109 # define DEBUGLOG(l, ...) {} /* disabled */ 110 #endif 111 112 113 /**************************************************************** 114 * Memory I/O 115 *****************************************************************/ 116 /* MEM_FORCE_MEMORY_ACCESS 117 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable. 118 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal. 119 * The below switch allow to select different access method for improved performance. 120 * Method 0 (default) : use `memcpy()`. Safe and portable. 121 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable). 122 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`. 123 * Method 2 : direct access. This method is portable but violate C standard. 124 * It can generate buggy code on targets generating assembly depending on alignment. 125 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6) 126 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details. 127 * Prefer these methods in priority order (0 > 1 > 2) 128 */ 129 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */ 130 # if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) ) 131 # define MEM_FORCE_MEMORY_ACCESS 2 132 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \ 133 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) )) 134 # define MEM_FORCE_MEMORY_ACCESS 1 135 # endif 136 #endif 137 138 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; } 139 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; } 140 141 MEM_STATIC unsigned MEM_isLittleEndian(void) 142 { 143 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ 144 return one.c[0]; 145 } 146 147 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2) 148 149 /* violates C standard on structure alignment. 150 Only use if no other choice to achieve best performance on target platform */ 151 MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; } 152 MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; } 153 MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; } 154 155 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; } 156 157 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1) 158 159 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ 160 /* currently only defined for gcc and icc */ 161 typedef union { U16 u16; U32 u32; U64 u64; } __attribute__((packed)) unalign; 162 163 MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; } 164 MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } 165 MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; } 166 167 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; } 168 169 #else 170 171 /* default method, safe and standard. 172 can sometimes prove slower */ 173 174 MEM_STATIC U16 MEM_read16(const void* memPtr) 175 { 176 U16 val; memcpy(&val, memPtr, sizeof(val)); return val; 177 } 178 179 MEM_STATIC U32 MEM_read32(const void* memPtr) 180 { 181 U32 val; memcpy(&val, memPtr, sizeof(val)); return val; 182 } 183 184 MEM_STATIC U64 MEM_read64(const void* memPtr) 185 { 186 U64 val; memcpy(&val, memPtr, sizeof(val)); return val; 187 } 188 189 MEM_STATIC void MEM_write16(void* memPtr, U16 value) 190 { 191 memcpy(memPtr, &value, sizeof(value)); 192 } 193 194 #endif // MEM_FORCE_MEMORY_ACCESS 195 196 197 MEM_STATIC U16 MEM_readLE16(const void* memPtr) 198 { 199 if (MEM_isLittleEndian()) 200 return MEM_read16(memPtr); 201 else 202 { 203 const BYTE* p = (const BYTE*)memPtr; 204 return (U16)(p[0] + (p[1]<<8)); 205 } 206 } 207 208 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val) 209 { 210 if (MEM_isLittleEndian()) 211 { 212 MEM_write16(memPtr, val); 213 } 214 else 215 { 216 BYTE* p = (BYTE*)memPtr; 217 p[0] = (BYTE)val; 218 p[1] = (BYTE)(val>>8); 219 } 220 } 221 222 MEM_STATIC U32 MEM_readLE32(const void* memPtr) 223 { 224 if (MEM_isLittleEndian()) 225 return MEM_read32(memPtr); 226 else 227 { 228 const BYTE* p = (const BYTE*)memPtr; 229 return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24)); 230 } 231 } 232 233 234 MEM_STATIC U64 MEM_readLE64(const void* memPtr) 235 { 236 if (MEM_isLittleEndian()) 237 return MEM_read64(memPtr); 238 else 239 { 240 const BYTE* p = (const BYTE*)memPtr; 241 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24) 242 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56)); 243 } 244 } 245 246 247 MEM_STATIC size_t MEM_readLEST(const void* memPtr) 248 { 249 if (MEM_32bits()) 250 return (size_t)MEM_readLE32(memPtr); 251 else 252 return (size_t)MEM_readLE64(memPtr); 253 } 254 255 256 #if defined (__cplusplus) 257 } 258 #endif 259 260 #endif /* MEM_H_MODULE */ 261 262 /* 263 zstd - standard compression library 264 Header File for static linking only 265 */ 266 #ifndef ZSTD_STATIC_H 267 #define ZSTD_STATIC_H 268 269 /* The objects defined into this file shall be considered experimental. 270 * They are not considered stable, as their prototype may change in the future. 271 * You can use them for tests, provide feedback, or if you can endure risks of future changes. 272 */ 273 274 #if defined (__cplusplus) 275 extern "C" { 276 #endif 277 278 /* ************************************* 279 * Types 280 ***************************************/ 281 #define ZSTD_WINDOWLOG_MAX 26 282 #define ZSTD_WINDOWLOG_MIN 18 283 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 11 284 #define ZSTD_CONTENTLOG_MAX (ZSTD_WINDOWLOG_MAX+1) 285 #define ZSTD_CONTENTLOG_MIN 4 286 #define ZSTD_HASHLOG_MAX 28 287 #define ZSTD_HASHLOG_MIN 4 288 #define ZSTD_SEARCHLOG_MAX (ZSTD_CONTENTLOG_MAX-1) 289 #define ZSTD_SEARCHLOG_MIN 1 290 #define ZSTD_SEARCHLENGTH_MAX 7 291 #define ZSTD_SEARCHLENGTH_MIN 4 292 293 /** from faster to stronger */ 294 typedef enum { ZSTD_fast, ZSTD_greedy, ZSTD_lazy, ZSTD_lazy2, ZSTD_btlazy2 } ZSTD_strategy; 295 296 typedef struct 297 { 298 U64 srcSize; /* optional : tells how much bytes are present in the frame. Use 0 if not known. */ 299 U32 windowLog; /* largest match distance : larger == more compression, more memory needed during decompression */ 300 U32 contentLog; /* full search segment : larger == more compression, slower, more memory (useless for fast) */ 301 U32 hashLog; /* dispatch table : larger == more memory, faster */ 302 U32 searchLog; /* nb of searches : larger == more compression, slower */ 303 U32 searchLength; /* size of matches : larger == faster decompression, sometimes less compression */ 304 ZSTD_strategy strategy; 305 } ZSTD_parameters; 306 307 typedef ZSTDv04_Dctx ZSTD_DCtx; 308 309 /* ************************************* 310 * Advanced functions 311 ***************************************/ 312 /** ZSTD_decompress_usingDict 313 * Same as ZSTD_decompressDCtx, using a Dictionary content as prefix 314 * Note : dict can be NULL, in which case, it's equivalent to ZSTD_decompressDCtx() */ 315 static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx, 316 void* dst, size_t maxDstSize, 317 const void* src, size_t srcSize, 318 const void* dict,size_t dictSize); 319 320 321 /* ************************************** 322 * Streaming functions (direct mode) 323 ****************************************/ 324 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx); 325 static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize); 326 static void ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* src, size_t srcSize); 327 328 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx); 329 static size_t ZSTD_decompressContinue(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize); 330 331 /** 332 Streaming decompression, bufferless mode 333 334 A ZSTD_DCtx object is required to track streaming operations. 335 Use ZSTD_createDCtx() / ZSTD_freeDCtx() to manage it. 336 A ZSTD_DCtx object can be re-used multiple times. Use ZSTD_resetDCtx() to return to fresh status. 337 338 First operation is to retrieve frame parameters, using ZSTD_getFrameParams(). 339 This function doesn't consume its input. It needs enough input data to properly decode the frame header. 340 Objective is to retrieve *params.windowlog, to know minimum amount of memory required during decoding. 341 Result : 0 when successful, it means the ZSTD_parameters structure has been filled. 342 >0 : means there is not enough data into src. Provides the expected size to successfully decode header. 343 errorCode, which can be tested using ZSTD_isError() (For example, if it's not a ZSTD header) 344 345 Then, you can optionally insert a dictionary. 346 This operation must mimic the compressor behavior, otherwise decompression will fail or be corrupted. 347 348 Then it's possible to start decompression. 349 Use ZSTD_nextSrcSizeToDecompress() and ZSTD_decompressContinue() alternatively. 350 ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue(). 351 ZSTD_decompressContinue() requires this exact amount of bytes, or it will fail. 352 ZSTD_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog). 353 They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible. 354 355 @result of ZSTD_decompressContinue() is the number of bytes regenerated within 'dst'. 356 It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header. 357 358 A frame is fully decoded when ZSTD_nextSrcSizeToDecompress() returns zero. 359 Context can then be reset to start a new decompression. 360 */ 361 362 363 #if defined (__cplusplus) 364 } 365 #endif 366 367 368 #endif /* ZSTD_STATIC_H */ 369 370 371 /* 372 zstd_internal - common functions to include 373 Header File for include 374 */ 375 #ifndef ZSTD_CCOMMON_H_MODULE 376 #define ZSTD_CCOMMON_H_MODULE 377 378 #if defined (__cplusplus) 379 extern "C" { 380 #endif 381 382 /* ************************************* 383 * Common macros 384 ***************************************/ 385 #define MIN(a,b) ((a)<(b) ? (a) : (b)) 386 #define MAX(a,b) ((a)>(b) ? (a) : (b)) 387 388 389 /* ************************************* 390 * Common constants 391 ***************************************/ 392 #define ZSTD_MAGICNUMBER 0xFD2FB524 /* v0.4 */ 393 394 #define KB *(1 <<10) 395 #define MB *(1 <<20) 396 #define GB *(1U<<30) 397 398 #define BLOCKSIZE (128 KB) /* define, for static allocation */ 399 400 static const size_t ZSTD_blockHeaderSize = 3; 401 static const size_t ZSTD_frameHeaderSize_min = 5; 402 #define ZSTD_frameHeaderSize_max 5 /* define, for static allocation */ 403 404 #define BIT7 128 405 #define BIT6 64 406 #define BIT5 32 407 #define BIT4 16 408 #define BIT1 2 409 #define BIT0 1 410 411 #define IS_RAW BIT0 412 #define IS_RLE BIT1 413 414 #define MINMATCH 4 415 #define REPCODE_STARTVALUE 4 416 417 #define MLbits 7 418 #define LLbits 6 419 #define Offbits 5 420 #define MaxML ((1<<MLbits) - 1) 421 #define MaxLL ((1<<LLbits) - 1) 422 #define MaxOff ((1<<Offbits)- 1) 423 #define MLFSELog 10 424 #define LLFSELog 10 425 #define OffFSELog 9 426 #define MaxSeq MAX(MaxLL, MaxML) 427 428 #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/) 429 #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE) 430 431 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t; 432 433 434 /* ****************************************** 435 * Shared functions to include for inlining 436 ********************************************/ 437 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); } 438 439 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; } 440 441 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */ 442 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length) 443 { 444 const BYTE* ip = (const BYTE*)src; 445 BYTE* op = (BYTE*)dst; 446 BYTE* const oend = op + length; 447 do 448 COPY8(op, ip) 449 while (op < oend); 450 } 451 452 453 #if defined (__cplusplus) 454 } 455 #endif 456 457 458 /* ****************************************************************** 459 FSE : Finite State Entropy coder 460 header file 461 ****************************************************************** */ 462 #ifndef FSE_H 463 #define FSE_H 464 465 #if defined (__cplusplus) 466 extern "C" { 467 #endif 468 469 470 /* ***************************************** 471 * Includes 472 ******************************************/ 473 #include <stddef.h> /* size_t, ptrdiff_t */ 474 475 476 /* ***************************************** 477 * FSE simple functions 478 ******************************************/ 479 static size_t FSE_decompress(void* dst, size_t maxDstSize, 480 const void* cSrc, size_t cSrcSize); 481 /*! 482 FSE_decompress(): 483 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize', 484 into already allocated destination buffer 'dst', of size 'maxDstSize'. 485 return : size of regenerated data (<= maxDstSize) 486 or an error code, which can be tested using FSE_isError() 487 488 ** Important ** : FSE_decompress() doesn't decompress non-compressible nor RLE data !!! 489 Why ? : making this distinction requires a header. 490 Header management is intentionally delegated to the user layer, which can better manage special cases. 491 */ 492 493 494 /* ***************************************** 495 * Tool functions 496 ******************************************/ 497 /* Error Management */ 498 static unsigned FSE_isError(size_t code); /* tells if a return value is an error code */ 499 500 501 502 /* ***************************************** 503 * FSE detailed API 504 ******************************************/ 505 /*! 506 FSE_compress() does the following: 507 1. count symbol occurrence from source[] into table count[] 508 2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog) 509 3. save normalized counters to memory buffer using writeNCount() 510 4. build encoding table 'CTable' from normalized counters 511 5. encode the data stream using encoding table 'CTable' 512 513 FSE_decompress() does the following: 514 1. read normalized counters with readNCount() 515 2. build decoding table 'DTable' from normalized counters 516 3. decode the data stream using decoding table 'DTable' 517 518 The following API allows targeting specific sub-functions for advanced tasks. 519 For example, it's possible to compress several blocks using the same 'CTable', 520 or to save and provide normalized distribution using external method. 521 */ 522 523 524 /* *** DECOMPRESSION *** */ 525 526 /*! 527 FSE_readNCount(): 528 Read compactly saved 'normalizedCounter' from 'rBuffer'. 529 return : size read from 'rBuffer' 530 or an errorCode, which can be tested using FSE_isError() 531 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */ 532 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize); 533 534 /*! 535 Constructor and Destructor of type FSE_DTable 536 Note that its size depends on 'tableLog' */ 537 typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */ 538 539 /*! 540 FSE_buildDTable(): 541 Builds 'dt', which must be already allocated, using FSE_createDTable() 542 return : 0, 543 or an errorCode, which can be tested using FSE_isError() */ 544 static size_t FSE_buildDTable ( FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog); 545 546 /*! 547 FSE_decompress_usingDTable(): 548 Decompress compressed source 'cSrc' of size 'cSrcSize' using 'dt' 549 into 'dst' which must be already allocated. 550 return : size of regenerated data (necessarily <= maxDstSize) 551 or an errorCode, which can be tested using FSE_isError() */ 552 static size_t FSE_decompress_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const FSE_DTable* dt); 553 554 /*! 555 Tutorial : 556 ---------- 557 (Note : these functions only decompress FSE-compressed blocks. 558 If block is uncompressed, use memcpy() instead 559 If block is a single repeated byte, use memset() instead ) 560 561 The first step is to obtain the normalized frequencies of symbols. 562 This can be performed by FSE_readNCount() if it was saved using FSE_writeNCount(). 563 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short. 564 In practice, that means it's necessary to know 'maxSymbolValue' beforehand, 565 or size the table to handle worst case situations (typically 256). 566 FSE_readNCount() will provide 'tableLog' and 'maxSymbolValue'. 567 The result of FSE_readNCount() is the number of bytes read from 'rBuffer'. 568 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that. 569 If there is an error, the function will return an error code, which can be tested using FSE_isError(). 570 571 The next step is to build the decompression tables 'FSE_DTable' from 'normalizedCounter'. 572 This is performed by the function FSE_buildDTable(). 573 The space required by 'FSE_DTable' must be already allocated using FSE_createDTable(). 574 If there is an error, the function will return an error code, which can be tested using FSE_isError(). 575 576 'FSE_DTable' can then be used to decompress 'cSrc', with FSE_decompress_usingDTable(). 577 'cSrcSize' must be strictly correct, otherwise decompression will fail. 578 FSE_decompress_usingDTable() result will tell how many bytes were regenerated (<=maxDstSize). 579 If there is an error, the function will return an error code, which can be tested using FSE_isError(). (ex: dst buffer too small) 580 */ 581 582 583 #if defined (__cplusplus) 584 } 585 #endif 586 587 #endif /* FSE_H */ 588 589 590 /* ****************************************************************** 591 bitstream 592 Part of NewGen Entropy library 593 header file (to include) 594 Copyright (C) 2013-2015, Yann Collet. 595 596 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 597 598 Redistribution and use in source and binary forms, with or without 599 modification, are permitted provided that the following conditions are 600 met: 601 602 * Redistributions of source code must retain the above copyright 603 notice, this list of conditions and the following disclaimer. 604 * Redistributions in binary form must reproduce the above 605 copyright notice, this list of conditions and the following disclaimer 606 in the documentation and/or other materials provided with the 607 distribution. 608 609 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 610 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 611 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 612 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 613 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 614 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 615 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 616 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 617 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 618 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 619 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 620 621 You can contact the author at : 622 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 623 - Public forum : https://groups.google.com/forum/#!forum/lz4c 624 ****************************************************************** */ 625 #ifndef BITSTREAM_H_MODULE 626 #define BITSTREAM_H_MODULE 627 628 #if defined (__cplusplus) 629 extern "C" { 630 #endif 631 632 633 /* 634 * This API consists of small unitary functions, which highly benefit from being inlined. 635 * Since link-time-optimization is not available for all compilers, 636 * these functions are defined into a .h to be included. 637 */ 638 639 /********************************************** 640 * bitStream decompression API (read backward) 641 **********************************************/ 642 typedef struct 643 { 644 size_t bitContainer; 645 unsigned bitsConsumed; 646 const char* ptr; 647 const char* start; 648 } BIT_DStream_t; 649 650 typedef enum { BIT_DStream_unfinished = 0, 651 BIT_DStream_endOfBuffer = 1, 652 BIT_DStream_completed = 2, 653 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */ 654 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */ 655 656 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize); 657 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits); 658 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD); 659 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD); 660 661 662 663 664 /****************************************** 665 * unsafe API 666 ******************************************/ 667 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits); 668 /* faster, but works only if nbBits >= 1 */ 669 670 671 672 /**************************************************************** 673 * Helper functions 674 ****************************************************************/ 675 MEM_STATIC unsigned BIT_highbit32 (U32 val) 676 { 677 # if defined(_MSC_VER) /* Visual */ 678 unsigned long r=0; 679 _BitScanReverse ( &r, val ); 680 return (unsigned) r; 681 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */ 682 return 31 - __builtin_clz (val); 683 # else /* Software version */ 684 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 }; 685 U32 v = val; 686 unsigned r; 687 v |= v >> 1; 688 v |= v >> 2; 689 v |= v >> 4; 690 v |= v >> 8; 691 v |= v >> 16; 692 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27]; 693 return r; 694 # endif 695 } 696 697 698 /********************************************************** 699 * bitStream decoding 700 **********************************************************/ 701 702 /*!BIT_initDStream 703 * Initialize a BIT_DStream_t. 704 * @bitD : a pointer to an already allocated BIT_DStream_t structure 705 * @srcBuffer must point at the beginning of a bitStream 706 * @srcSize must be the exact size of the bitStream 707 * @result : size of stream (== srcSize) or an errorCode if a problem is detected 708 */ 709 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize) 710 { 711 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); } 712 713 if (srcSize >= sizeof(size_t)) /* normal case */ 714 { 715 U32 contain32; 716 bitD->start = (const char*)srcBuffer; 717 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t); 718 bitD->bitContainer = MEM_readLEST(bitD->ptr); 719 contain32 = ((const BYTE*)srcBuffer)[srcSize-1]; 720 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */ 721 bitD->bitsConsumed = 8 - BIT_highbit32(contain32); 722 } 723 else 724 { 725 U32 contain32; 726 bitD->start = (const char*)srcBuffer; 727 bitD->ptr = bitD->start; 728 bitD->bitContainer = *(const BYTE*)(bitD->start); 729 switch(srcSize) 730 { 731 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);/* fall-through */ 732 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);/* fall-through */ 733 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);/* fall-through */ 734 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24; /* fall-through */ 735 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16; /* fall-through */ 736 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8; /* fall-through */ 737 default: break; 738 } 739 contain32 = ((const BYTE*)srcBuffer)[srcSize-1]; 740 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */ 741 bitD->bitsConsumed = 8 - BIT_highbit32(contain32); 742 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8; 743 } 744 745 return srcSize; 746 } 747 748 MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits) 749 { 750 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1; 751 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask); 752 } 753 754 /*! BIT_lookBitsFast : 755 * unsafe version; only works only if nbBits >= 1 */ 756 MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits) 757 { 758 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1; 759 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask); 760 } 761 762 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits) 763 { 764 bitD->bitsConsumed += nbBits; 765 } 766 767 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits) 768 { 769 size_t value = BIT_lookBits(bitD, nbBits); 770 BIT_skipBits(bitD, nbBits); 771 return value; 772 } 773 774 /*!BIT_readBitsFast : 775 * unsafe version; only works only if nbBits >= 1 */ 776 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits) 777 { 778 size_t value = BIT_lookBitsFast(bitD, nbBits); 779 BIT_skipBits(bitD, nbBits); 780 return value; 781 } 782 783 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD) 784 { 785 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */ 786 return BIT_DStream_overflow; 787 788 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) 789 { 790 bitD->ptr -= bitD->bitsConsumed >> 3; 791 bitD->bitsConsumed &= 7; 792 bitD->bitContainer = MEM_readLEST(bitD->ptr); 793 return BIT_DStream_unfinished; 794 } 795 if (bitD->ptr == bitD->start) 796 { 797 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer; 798 return BIT_DStream_completed; 799 } 800 { 801 U32 nbBytes = bitD->bitsConsumed >> 3; 802 BIT_DStream_status result = BIT_DStream_unfinished; 803 if (bitD->ptr - nbBytes < bitD->start) 804 { 805 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */ 806 result = BIT_DStream_endOfBuffer; 807 } 808 bitD->ptr -= nbBytes; 809 bitD->bitsConsumed -= nbBytes*8; 810 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */ 811 return result; 812 } 813 } 814 815 /*! BIT_endOfDStream 816 * @return Tells if DStream has reached its exact end 817 */ 818 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream) 819 { 820 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8)); 821 } 822 823 #if defined (__cplusplus) 824 } 825 #endif 826 827 #endif /* BITSTREAM_H_MODULE */ 828 829 830 831 /* ****************************************************************** 832 FSE : Finite State Entropy coder 833 header file for static linking (only) 834 Copyright (C) 2013-2015, Yann Collet 835 836 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 837 838 Redistribution and use in source and binary forms, with or without 839 modification, are permitted provided that the following conditions are 840 met: 841 842 * Redistributions of source code must retain the above copyright 843 notice, this list of conditions and the following disclaimer. 844 * Redistributions in binary form must reproduce the above 845 copyright notice, this list of conditions and the following disclaimer 846 in the documentation and/or other materials provided with the 847 distribution. 848 849 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 850 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 851 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 852 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 853 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 854 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 855 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 856 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 857 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 858 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 859 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 860 861 You can contact the author at : 862 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 863 - Public forum : https://groups.google.com/forum/#!forum/lz4c 864 ****************************************************************** */ 865 #ifndef FSE_STATIC_H 866 #define FSE_STATIC_H 867 868 #if defined (__cplusplus) 869 extern "C" { 870 #endif 871 872 873 /* ***************************************** 874 * Static allocation 875 *******************************************/ 876 /* FSE buffer bounds */ 877 #define FSE_NCOUNTBOUND 512 878 #define FSE_BLOCKBOUND(size) (size + (size>>7)) 879 #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ 880 881 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */ 882 #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2)) 883 #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog)) 884 885 886 /* ***************************************** 887 * FSE advanced API 888 *******************************************/ 889 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits); 890 /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */ 891 892 static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue); 893 /* build a fake FSE_DTable, designed to always generate the same symbolValue */ 894 895 896 897 /* ***************************************** 898 * FSE symbol decompression API 899 *******************************************/ 900 typedef struct 901 { 902 size_t state; 903 const void* table; /* precise table may vary, depending on U16 */ 904 } FSE_DState_t; 905 906 907 static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt); 908 909 static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD); 910 911 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr); 912 913 914 /* ***************************************** 915 * FSE unsafe API 916 *******************************************/ 917 static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD); 918 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */ 919 920 921 /* ***************************************** 922 * Implementation of inlined functions 923 *******************************************/ 924 /* decompression */ 925 926 typedef struct { 927 U16 tableLog; 928 U16 fastMode; 929 } FSE_DTableHeader; /* sizeof U32 */ 930 931 typedef struct 932 { 933 unsigned short newState; 934 unsigned char symbol; 935 unsigned char nbBits; 936 } FSE_decode_t; /* size == U32 */ 937 938 MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt) 939 { 940 FSE_DTableHeader DTableH; 941 memcpy(&DTableH, dt, sizeof(DTableH)); 942 DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog); 943 BIT_reloadDStream(bitD); 944 DStatePtr->table = dt + 1; 945 } 946 947 MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) 948 { 949 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 950 const U32 nbBits = DInfo.nbBits; 951 BYTE symbol = DInfo.symbol; 952 size_t lowBits = BIT_readBits(bitD, nbBits); 953 954 DStatePtr->state = DInfo.newState + lowBits; 955 return symbol; 956 } 957 958 MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) 959 { 960 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 961 const U32 nbBits = DInfo.nbBits; 962 BYTE symbol = DInfo.symbol; 963 size_t lowBits = BIT_readBitsFast(bitD, nbBits); 964 965 DStatePtr->state = DInfo.newState + lowBits; 966 return symbol; 967 } 968 969 MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr) 970 { 971 return DStatePtr->state == 0; 972 } 973 974 975 #if defined (__cplusplus) 976 } 977 #endif 978 979 #endif /* FSE_STATIC_H */ 980 981 /* ****************************************************************** 982 FSE : Finite State Entropy coder 983 Copyright (C) 2013-2015, Yann Collet. 984 985 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 986 987 Redistribution and use in source and binary forms, with or without 988 modification, are permitted provided that the following conditions are 989 met: 990 991 * Redistributions of source code must retain the above copyright 992 notice, this list of conditions and the following disclaimer. 993 * Redistributions in binary form must reproduce the above 994 copyright notice, this list of conditions and the following disclaimer 995 in the documentation and/or other materials provided with the 996 distribution. 997 998 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 999 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1000 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1001 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1002 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1003 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1004 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1005 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1006 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1007 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1008 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1009 1010 You can contact the author at : 1011 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy 1012 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1013 ****************************************************************** */ 1014 1015 #ifndef FSE_COMMONDEFS_ONLY 1016 1017 /* ************************************************************** 1018 * Tuning parameters 1019 ****************************************************************/ 1020 /*!MEMORY_USAGE : 1021 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) 1022 * Increasing memory usage improves compression ratio 1023 * Reduced memory usage can improve speed, due to cache effect 1024 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */ 1025 #define FSE_MAX_MEMORY_USAGE 14 1026 #define FSE_DEFAULT_MEMORY_USAGE 13 1027 1028 /*!FSE_MAX_SYMBOL_VALUE : 1029 * Maximum symbol value authorized. 1030 * Required for proper stack allocation */ 1031 #define FSE_MAX_SYMBOL_VALUE 255 1032 1033 1034 /* ************************************************************** 1035 * template functions type & suffix 1036 ****************************************************************/ 1037 #define FSE_FUNCTION_TYPE BYTE 1038 #define FSE_FUNCTION_EXTENSION 1039 #define FSE_DECODE_TYPE FSE_decode_t 1040 1041 1042 #endif /* !FSE_COMMONDEFS_ONLY */ 1043 1044 /* ************************************************************** 1045 * Compiler specifics 1046 ****************************************************************/ 1047 #ifdef _MSC_VER /* Visual Studio */ 1048 # define FORCE_INLINE static __forceinline 1049 # include <intrin.h> /* For Visual 2005 */ 1050 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 1051 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */ 1052 #else 1053 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 1054 # ifdef __GNUC__ 1055 # define FORCE_INLINE static inline __attribute__((always_inline)) 1056 # else 1057 # define FORCE_INLINE static inline 1058 # endif 1059 # else 1060 # define FORCE_INLINE static 1061 # endif /* __STDC_VERSION__ */ 1062 #endif 1063 1064 1065 /* ************************************************************** 1066 * Dependencies 1067 ****************************************************************/ 1068 #include <stdlib.h> /* malloc, free, qsort */ 1069 #include <string.h> /* memcpy, memset */ 1070 #include <stdio.h> /* printf (debug) */ 1071 1072 1073 /* *************************************************************** 1074 * Constants 1075 *****************************************************************/ 1076 #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2) 1077 #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG) 1078 #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1) 1079 #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2) 1080 #define FSE_MIN_TABLELOG 5 1081 1082 #define FSE_TABLELOG_ABSOLUTE_MAX 15 1083 #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX 1084 #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported" 1085 #endif 1086 1087 1088 /* ************************************************************** 1089 * Error Management 1090 ****************************************************************/ 1091 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 1092 1093 1094 /* ************************************************************** 1095 * Complex types 1096 ****************************************************************/ 1097 typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]; 1098 1099 1100 /*-************************************************************** 1101 * Templates 1102 ****************************************************************/ 1103 /* 1104 designed to be included 1105 for type-specific functions (template emulation in C) 1106 Objective is to write these functions only once, for improved maintenance 1107 */ 1108 1109 /* safety checks */ 1110 #ifndef FSE_FUNCTION_EXTENSION 1111 # error "FSE_FUNCTION_EXTENSION must be defined" 1112 #endif 1113 #ifndef FSE_FUNCTION_TYPE 1114 # error "FSE_FUNCTION_TYPE must be defined" 1115 #endif 1116 1117 /* Function names */ 1118 #define FSE_CAT(X,Y) X##Y 1119 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y) 1120 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y) 1121 1122 static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; } 1123 1124 1125 static size_t FSE_buildDTable(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) 1126 { 1127 FSE_DTableHeader DTableH; 1128 void* const tdPtr = dt+1; /* because dt is unsigned, 32-bits aligned on 32-bits */ 1129 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr); 1130 const U32 tableSize = 1 << tableLog; 1131 const U32 tableMask = tableSize-1; 1132 const U32 step = FSE_tableStep(tableSize); 1133 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1]; 1134 U32 position = 0; 1135 U32 highThreshold = tableSize-1; 1136 const S16 largeLimit= (S16)(1 << (tableLog-1)); 1137 U32 noLarge = 1; 1138 U32 s; 1139 1140 /* Sanity Checks */ 1141 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge); 1142 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); 1143 1144 /* Init, lay down lowprob symbols */ 1145 DTableH.tableLog = (U16)tableLog; 1146 for (s=0; s<=maxSymbolValue; s++) 1147 { 1148 if (normalizedCounter[s]==-1) 1149 { 1150 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s; 1151 symbolNext[s] = 1; 1152 } 1153 else 1154 { 1155 if (normalizedCounter[s] >= largeLimit) noLarge=0; 1156 symbolNext[s] = normalizedCounter[s]; 1157 } 1158 } 1159 1160 /* Spread symbols */ 1161 for (s=0; s<=maxSymbolValue; s++) 1162 { 1163 int i; 1164 for (i=0; i<normalizedCounter[s]; i++) 1165 { 1166 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s; 1167 position = (position + step) & tableMask; 1168 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */ 1169 } 1170 } 1171 1172 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ 1173 1174 /* Build Decoding table */ 1175 { 1176 U32 i; 1177 for (i=0; i<tableSize; i++) 1178 { 1179 FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol); 1180 U16 nextState = symbolNext[symbol]++; 1181 tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) ); 1182 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize); 1183 } 1184 } 1185 1186 DTableH.fastMode = (U16)noLarge; 1187 memcpy(dt, &DTableH, sizeof(DTableH)); 1188 return 0; 1189 } 1190 1191 1192 #ifndef FSE_COMMONDEFS_ONLY 1193 /****************************************** 1194 * FSE helper functions 1195 ******************************************/ 1196 static unsigned FSE_isError(size_t code) { return ERR_isError(code); } 1197 1198 1199 /**************************************************************** 1200 * FSE NCount encoding-decoding 1201 ****************************************************************/ 1202 static short FSE_abs(short a) 1203 { 1204 return a<0 ? -a : a; 1205 } 1206 1207 static size_t FSE_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) + FSE_MIN_TABLELOG; /* extract tableLog */ 1224 if (nbBits > FSE_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 { 1234 if (previous0) 1235 { 1236 unsigned n0 = charnum; 1237 while ((bitStream & 0xFFFF) == 0xFFFF) 1238 { 1239 n0+=24; 1240 if (ip < iend-5) 1241 { 1242 ip+=2; 1243 bitStream = MEM_readLE32(ip) >> bitCount; 1244 } 1245 else 1246 { 1247 bitStream >>= 16; 1248 bitCount+=16; 1249 } 1250 } 1251 while ((bitStream & 3) == 3) 1252 { 1253 n0+=3; 1254 bitStream>>=2; 1255 bitCount+=2; 1256 } 1257 n0 += bitStream & 3; 1258 bitCount += 2; 1259 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall); 1260 while (charnum < n0) normalizedCounter[charnum++] = 0; 1261 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) 1262 { 1263 ip += bitCount>>3; 1264 bitCount &= 7; 1265 bitStream = MEM_readLE32(ip) >> bitCount; 1266 } 1267 else 1268 bitStream >>= 2; 1269 } 1270 { 1271 const short max = (short)((2*threshold-1)-remaining); 1272 short count; 1273 1274 if ((bitStream & (threshold-1)) < (U32)max) 1275 { 1276 count = (short)(bitStream & (threshold-1)); 1277 bitCount += nbBits-1; 1278 } 1279 else 1280 { 1281 count = (short)(bitStream & (2*threshold-1)); 1282 if (count >= threshold) count -= max; 1283 bitCount += nbBits; 1284 } 1285 1286 count--; /* extra accuracy */ 1287 remaining -= FSE_abs(count); 1288 normalizedCounter[charnum++] = count; 1289 previous0 = !count; 1290 while (remaining < threshold) 1291 { 1292 nbBits--; 1293 threshold >>= 1; 1294 } 1295 1296 { 1297 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) 1298 { 1299 ip += bitCount>>3; 1300 bitCount &= 7; 1301 } 1302 else 1303 { 1304 bitCount -= (int)(8 * (iend - 4 - ip)); 1305 ip = iend - 4; 1306 } 1307 bitStream = MEM_readLE32(ip) >> (bitCount & 31); 1308 } 1309 } 1310 } 1311 if (remaining != 1) return ERROR(GENERIC); 1312 *maxSVPtr = charnum-1; 1313 1314 ip += (bitCount+7)>>3; 1315 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong); 1316 return ip-istart; 1317 } 1318 1319 1320 /********************************************************* 1321 * Decompression (Byte symbols) 1322 *********************************************************/ 1323 static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue) 1324 { 1325 void* ptr = dt; 1326 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 1327 void* dPtr = dt + 1; 1328 FSE_decode_t* const cell = (FSE_decode_t*)dPtr; 1329 1330 DTableH->tableLog = 0; 1331 DTableH->fastMode = 0; 1332 1333 cell->newState = 0; 1334 cell->symbol = symbolValue; 1335 cell->nbBits = 0; 1336 1337 return 0; 1338 } 1339 1340 1341 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits) 1342 { 1343 void* ptr = dt; 1344 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 1345 void* dPtr = dt + 1; 1346 FSE_decode_t* const dinfo = (FSE_decode_t*)dPtr; 1347 const unsigned tableSize = 1 << nbBits; 1348 const unsigned tableMask = tableSize - 1; 1349 const unsigned maxSymbolValue = tableMask; 1350 unsigned s; 1351 1352 /* Sanity checks */ 1353 if (nbBits < 1) return ERROR(GENERIC); /* min size */ 1354 1355 /* Build Decoding Table */ 1356 DTableH->tableLog = (U16)nbBits; 1357 DTableH->fastMode = 1; 1358 for (s=0; s<=maxSymbolValue; s++) 1359 { 1360 dinfo[s].newState = 0; 1361 dinfo[s].symbol = (BYTE)s; 1362 dinfo[s].nbBits = (BYTE)nbBits; 1363 } 1364 1365 return 0; 1366 } 1367 1368 FORCE_INLINE size_t FSE_decompress_usingDTable_generic( 1369 void* dst, size_t maxDstSize, 1370 const void* cSrc, size_t cSrcSize, 1371 const FSE_DTable* dt, const unsigned fast) 1372 { 1373 BYTE* const ostart = (BYTE*) dst; 1374 BYTE* op = ostart; 1375 BYTE* const omax = op + maxDstSize; 1376 BYTE* const olimit = omax-3; 1377 1378 BIT_DStream_t bitD; 1379 FSE_DState_t state1; 1380 FSE_DState_t state2; 1381 size_t errorCode; 1382 1383 /* Init */ 1384 errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */ 1385 if (FSE_isError(errorCode)) return errorCode; 1386 1387 FSE_initDState(&state1, &bitD, dt); 1388 FSE_initDState(&state2, &bitD, dt); 1389 1390 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD) 1391 1392 /* 4 symbols per loop */ 1393 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4) 1394 { 1395 op[0] = FSE_GETSYMBOL(&state1); 1396 1397 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1398 BIT_reloadDStream(&bitD); 1399 1400 op[1] = FSE_GETSYMBOL(&state2); 1401 1402 if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1403 { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } } 1404 1405 op[2] = FSE_GETSYMBOL(&state1); 1406 1407 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1408 BIT_reloadDStream(&bitD); 1409 1410 op[3] = FSE_GETSYMBOL(&state2); 1411 } 1412 1413 /* tail */ 1414 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */ 1415 while (1) 1416 { 1417 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) ) 1418 break; 1419 1420 *op++ = FSE_GETSYMBOL(&state1); 1421 1422 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) ) 1423 break; 1424 1425 *op++ = FSE_GETSYMBOL(&state2); 1426 } 1427 1428 /* end ? */ 1429 if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2)) 1430 return op-ostart; 1431 1432 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */ 1433 1434 return ERROR(corruption_detected); 1435 } 1436 1437 1438 static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize, 1439 const void* cSrc, size_t cSrcSize, 1440 const FSE_DTable* dt) 1441 { 1442 FSE_DTableHeader DTableH; 1443 U32 fastMode; 1444 1445 memcpy(&DTableH, dt, sizeof(DTableH)); 1446 fastMode = DTableH.fastMode; 1447 1448 /* select fast mode (static) */ 1449 if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1); 1450 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0); 1451 } 1452 1453 1454 static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize) 1455 { 1456 const BYTE* const istart = (const BYTE*)cSrc; 1457 const BYTE* ip = istart; 1458 short counting[FSE_MAX_SYMBOL_VALUE+1]; 1459 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */ 1460 unsigned tableLog; 1461 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE; 1462 size_t errorCode; 1463 1464 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */ 1465 1466 /* normal FSE decoding mode */ 1467 errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize); 1468 if (FSE_isError(errorCode)) return errorCode; 1469 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */ 1470 ip += errorCode; 1471 cSrcSize -= errorCode; 1472 1473 errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog); 1474 if (FSE_isError(errorCode)) return errorCode; 1475 1476 /* always return, even if it is an error code */ 1477 return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); 1478 } 1479 1480 1481 1482 #endif /* FSE_COMMONDEFS_ONLY */ 1483 1484 1485 /* ****************************************************************** 1486 Huff0 : Huffman coder, part of New Generation Entropy library 1487 header file 1488 Copyright (C) 2013-2015, Yann Collet. 1489 1490 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1491 1492 Redistribution and use in source and binary forms, with or without 1493 modification, are permitted provided that the following conditions are 1494 met: 1495 1496 * Redistributions of source code must retain the above copyright 1497 notice, this list of conditions and the following disclaimer. 1498 * Redistributions in binary form must reproduce the above 1499 copyright notice, this list of conditions and the following disclaimer 1500 in the documentation and/or other materials provided with the 1501 distribution. 1502 1503 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1504 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1505 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1506 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1507 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1508 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1509 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1510 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1511 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1512 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1513 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1514 1515 You can contact the author at : 1516 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 1517 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1518 ****************************************************************** */ 1519 #ifndef HUFF0_H 1520 #define HUFF0_H 1521 1522 #if defined (__cplusplus) 1523 extern "C" { 1524 #endif 1525 1526 1527 /* **************************************** 1528 * Dependency 1529 ******************************************/ 1530 #include <stddef.h> /* size_t */ 1531 1532 1533 /* **************************************** 1534 * Huff0 simple functions 1535 ******************************************/ 1536 static size_t HUF_decompress(void* dst, size_t dstSize, 1537 const void* cSrc, size_t cSrcSize); 1538 /*! 1539 HUF_decompress(): 1540 Decompress Huff0 data from buffer 'cSrc', of size 'cSrcSize', 1541 into already allocated destination buffer 'dst', of size 'dstSize'. 1542 'dstSize' must be the exact size of original (uncompressed) data. 1543 Note : in contrast with FSE, HUF_decompress can regenerate RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, because it knows size to regenerate. 1544 @return : size of regenerated data (== dstSize) 1545 or an error code, which can be tested using HUF_isError() 1546 */ 1547 1548 1549 /* **************************************** 1550 * Tool functions 1551 ******************************************/ 1552 /* Error Management */ 1553 static unsigned HUF_isError(size_t code); /* tells if a return value is an error code */ 1554 1555 1556 #if defined (__cplusplus) 1557 } 1558 #endif 1559 1560 #endif /* HUFF0_H */ 1561 1562 1563 /* ****************************************************************** 1564 Huff0 : Huffman coder, part of New Generation Entropy library 1565 header file for static linking (only) 1566 Copyright (C) 2013-2015, Yann Collet 1567 1568 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1569 1570 Redistribution and use in source and binary forms, with or without 1571 modification, are permitted provided that the following conditions are 1572 met: 1573 1574 * Redistributions of source code must retain the above copyright 1575 notice, this list of conditions and the following disclaimer. 1576 * Redistributions in binary form must reproduce the above 1577 copyright notice, this list of conditions and the following disclaimer 1578 in the documentation and/or other materials provided with the 1579 distribution. 1580 1581 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1582 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1583 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1584 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1585 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1586 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1587 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1588 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1589 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1590 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1591 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1592 1593 You can contact the author at : 1594 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 1595 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1596 ****************************************************************** */ 1597 #ifndef HUFF0_STATIC_H 1598 #define HUFF0_STATIC_H 1599 1600 #if defined (__cplusplus) 1601 extern "C" { 1602 #endif 1603 1604 1605 1606 /* **************************************** 1607 * Static allocation macros 1608 ******************************************/ 1609 /* static allocation of Huff0's DTable */ 1610 #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */ 1611 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \ 1612 unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 1613 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \ 1614 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 1615 #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \ 1616 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog } 1617 1618 1619 /* **************************************** 1620 * Advanced decompression functions 1621 ******************************************/ 1622 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ 1623 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */ 1624 1625 1626 /* **************************************** 1627 * Huff0 detailed API 1628 ******************************************/ 1629 /*! 1630 HUF_decompress() does the following: 1631 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics 1632 2. build Huffman table from save, using HUF_readDTableXn() 1633 3. decode 1 or 4 segments in parallel using HUF_decompressSXn_usingDTable 1634 1635 */ 1636 static size_t HUF_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize); 1637 static size_t HUF_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize); 1638 1639 static size_t HUF_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable); 1640 static size_t HUF_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable); 1641 1642 1643 #if defined (__cplusplus) 1644 } 1645 #endif 1646 1647 #endif /* HUFF0_STATIC_H */ 1648 1649 1650 1651 /* ****************************************************************** 1652 Huff0 : Huffman coder, part of New Generation Entropy library 1653 Copyright (C) 2013-2015, Yann Collet. 1654 1655 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1656 1657 Redistribution and use in source and binary forms, with or without 1658 modification, are permitted provided that the following conditions are 1659 met: 1660 1661 * Redistributions of source code must retain the above copyright 1662 notice, this list of conditions and the following disclaimer. 1663 * Redistributions in binary form must reproduce the above 1664 copyright notice, this list of conditions and the following disclaimer 1665 in the documentation and/or other materials provided with the 1666 distribution. 1667 1668 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1669 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1670 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1671 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1672 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1673 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1674 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1675 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1676 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1677 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1678 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1679 1680 You can contact the author at : 1681 - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy 1682 ****************************************************************** */ 1683 1684 /* ************************************************************** 1685 * Compiler specifics 1686 ****************************************************************/ 1687 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 1688 /* inline is defined */ 1689 #elif defined(_MSC_VER) 1690 # define inline __inline 1691 #else 1692 # define inline /* disable inline */ 1693 #endif 1694 1695 1696 #ifdef _MSC_VER /* Visual Studio */ 1697 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 1698 #endif 1699 1700 1701 /* ************************************************************** 1702 * Includes 1703 ****************************************************************/ 1704 #include <stdlib.h> /* malloc, free, qsort */ 1705 #include <string.h> /* memcpy, memset */ 1706 #include <stdio.h> /* printf (debug) */ 1707 1708 1709 /* ************************************************************** 1710 * Constants 1711 ****************************************************************/ 1712 #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */ 1713 #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */ 1714 #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */ 1715 #define HUF_MAX_SYMBOL_VALUE 255 1716 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG) 1717 # error "HUF_MAX_TABLELOG is too large !" 1718 #endif 1719 1720 1721 /* ************************************************************** 1722 * Error Management 1723 ****************************************************************/ 1724 static unsigned HUF_isError(size_t code) { return ERR_isError(code); } 1725 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 1726 1727 1728 1729 /*-******************************************************* 1730 * Huff0 : Huffman block decompression 1731 *********************************************************/ 1732 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */ 1733 1734 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */ 1735 1736 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t; 1737 1738 /*! HUF_readStats 1739 Read compact Huffman tree, saved by HUF_writeCTable 1740 @huffWeight : destination buffer 1741 @return : size read from `src` 1742 */ 1743 static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats, 1744 U32* nbSymbolsPtr, U32* tableLogPtr, 1745 const void* src, size_t srcSize) 1746 { 1747 U32 weightTotal; 1748 U32 tableLog; 1749 const BYTE* ip = (const BYTE*) src; 1750 size_t iSize; 1751 size_t oSize; 1752 U32 n; 1753 1754 if (!srcSize) return ERROR(srcSize_wrong); 1755 iSize = ip[0]; 1756 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */ 1757 1758 if (iSize >= 128) /* special header */ 1759 { 1760 if (iSize >= (242)) /* RLE */ 1761 { 1762 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 }; 1763 oSize = l[iSize-242]; 1764 memset(huffWeight, 1, hwSize); 1765 iSize = 0; 1766 } 1767 else /* Incompressible */ 1768 { 1769 oSize = iSize - 127; 1770 iSize = ((oSize+1)/2); 1771 if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 1772 if (oSize >= hwSize) return ERROR(corruption_detected); 1773 ip += 1; 1774 for (n=0; n<oSize; n+=2) 1775 { 1776 huffWeight[n] = ip[n/2] >> 4; 1777 huffWeight[n+1] = ip[n/2] & 15; 1778 } 1779 } 1780 } 1781 else /* header compressed with FSE (normal case) */ 1782 { 1783 if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 1784 oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */ 1785 if (FSE_isError(oSize)) return oSize; 1786 } 1787 1788 /* collect weight stats */ 1789 memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32)); 1790 weightTotal = 0; 1791 for (n=0; n<oSize; n++) 1792 { 1793 if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 1794 rankStats[huffWeight[n]]++; 1795 weightTotal += (1 << huffWeight[n]) >> 1; 1796 } 1797 if (weightTotal == 0) return ERROR(corruption_detected); 1798 1799 /* get last non-null symbol weight (implied, total must be 2^n) */ 1800 tableLog = BIT_highbit32(weightTotal) + 1; 1801 if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 1802 { 1803 U32 total = 1 << tableLog; 1804 U32 rest = total - weightTotal; 1805 U32 verif = 1 << BIT_highbit32(rest); 1806 U32 lastWeight = BIT_highbit32(rest) + 1; 1807 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */ 1808 huffWeight[oSize] = (BYTE)lastWeight; 1809 rankStats[lastWeight]++; 1810 } 1811 1812 /* check tree construction validity */ 1813 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */ 1814 1815 /* results */ 1816 *nbSymbolsPtr = (U32)(oSize+1); 1817 *tableLogPtr = tableLog; 1818 return iSize+1; 1819 } 1820 1821 1822 /**************************/ 1823 /* single-symbol decoding */ 1824 /**************************/ 1825 1826 static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize) 1827 { 1828 BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1]; 1829 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */ 1830 U32 tableLog = 0; 1831 size_t iSize; 1832 U32 nbSymbols = 0; 1833 U32 n; 1834 U32 nextRankStart; 1835 void* const dtPtr = DTable + 1; 1836 HUF_DEltX2* const dt = (HUF_DEltX2*)dtPtr; 1837 1838 HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */ 1839 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */ 1840 1841 iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize); 1842 if (HUF_isError(iSize)) return iSize; 1843 1844 /* check result */ 1845 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */ 1846 DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */ 1847 1848 /* Prepare ranks */ 1849 nextRankStart = 0; 1850 for (n=1; n<=tableLog; n++) 1851 { 1852 U32 current = nextRankStart; 1853 nextRankStart += (rankVal[n] << (n-1)); 1854 rankVal[n] = current; 1855 } 1856 1857 /* fill DTable */ 1858 for (n=0; n<nbSymbols; n++) 1859 { 1860 const U32 w = huffWeight[n]; 1861 const U32 length = (1 << w) >> 1; 1862 U32 i; 1863 HUF_DEltX2 D; 1864 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w); 1865 for (i = rankVal[w]; i < rankVal[w] + length; i++) 1866 dt[i] = D; 1867 rankVal[w] += length; 1868 } 1869 1870 return iSize; 1871 } 1872 1873 static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog) 1874 { 1875 const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */ 1876 const BYTE c = dt[val].byte; 1877 BIT_skipBits(Dstream, dt[val].nbBits); 1878 return c; 1879 } 1880 1881 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \ 1882 *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog) 1883 1884 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \ 1885 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \ 1886 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 1887 1888 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \ 1889 if (MEM_64bits()) \ 1890 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 1891 1892 static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog) 1893 { 1894 BYTE* const pStart = p; 1895 1896 /* up to 4 symbols at a time */ 1897 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4)) 1898 { 1899 HUF_DECODE_SYMBOLX2_2(p, bitDPtr); 1900 HUF_DECODE_SYMBOLX2_1(p, bitDPtr); 1901 HUF_DECODE_SYMBOLX2_2(p, bitDPtr); 1902 HUF_DECODE_SYMBOLX2_0(p, bitDPtr); 1903 } 1904 1905 /* closer to the end */ 1906 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd)) 1907 HUF_DECODE_SYMBOLX2_0(p, bitDPtr); 1908 1909 /* no more data to retrieve from bitstream, hence no need to reload */ 1910 while (p < pEnd) 1911 HUF_DECODE_SYMBOLX2_0(p, bitDPtr); 1912 1913 return pEnd-pStart; 1914 } 1915 1916 1917 static size_t HUF_decompress4X2_usingDTable( 1918 void* dst, size_t dstSize, 1919 const void* cSrc, size_t cSrcSize, 1920 const U16* DTable) 1921 { 1922 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 1923 1924 { 1925 const BYTE* const istart = (const BYTE*) cSrc; 1926 BYTE* const ostart = (BYTE*) dst; 1927 BYTE* const oend = ostart + dstSize; 1928 const void* const dtPtr = DTable; 1929 const HUF_DEltX2* const dt = ((const HUF_DEltX2*)dtPtr) +1; 1930 const U32 dtLog = DTable[0]; 1931 size_t errorCode; 1932 1933 /* Init */ 1934 BIT_DStream_t bitD1; 1935 BIT_DStream_t bitD2; 1936 BIT_DStream_t bitD3; 1937 BIT_DStream_t bitD4; 1938 const size_t length1 = MEM_readLE16(istart); 1939 const size_t length2 = MEM_readLE16(istart+2); 1940 const size_t length3 = MEM_readLE16(istart+4); 1941 size_t length4; 1942 const BYTE* const istart1 = istart + 6; /* jumpTable */ 1943 const BYTE* const istart2 = istart1 + length1; 1944 const BYTE* const istart3 = istart2 + length2; 1945 const BYTE* const istart4 = istart3 + length3; 1946 const size_t segmentSize = (dstSize+3) / 4; 1947 BYTE* const opStart2 = ostart + segmentSize; 1948 BYTE* const opStart3 = opStart2 + segmentSize; 1949 BYTE* const opStart4 = opStart3 + segmentSize; 1950 BYTE* op1 = ostart; 1951 BYTE* op2 = opStart2; 1952 BYTE* op3 = opStart3; 1953 BYTE* op4 = opStart4; 1954 U32 endSignal; 1955 1956 length4 = cSrcSize - (length1 + length2 + length3 + 6); 1957 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 1958 errorCode = BIT_initDStream(&bitD1, istart1, length1); 1959 if (HUF_isError(errorCode)) return errorCode; 1960 errorCode = BIT_initDStream(&bitD2, istart2, length2); 1961 if (HUF_isError(errorCode)) return errorCode; 1962 errorCode = BIT_initDStream(&bitD3, istart3, length3); 1963 if (HUF_isError(errorCode)) return errorCode; 1964 errorCode = BIT_initDStream(&bitD4, istart4, length4); 1965 if (HUF_isError(errorCode)) return errorCode; 1966 1967 /* 16-32 symbols per loop (4-8 symbols per stream) */ 1968 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 1969 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; ) 1970 { 1971 HUF_DECODE_SYMBOLX2_2(op1, &bitD1); 1972 HUF_DECODE_SYMBOLX2_2(op2, &bitD2); 1973 HUF_DECODE_SYMBOLX2_2(op3, &bitD3); 1974 HUF_DECODE_SYMBOLX2_2(op4, &bitD4); 1975 HUF_DECODE_SYMBOLX2_1(op1, &bitD1); 1976 HUF_DECODE_SYMBOLX2_1(op2, &bitD2); 1977 HUF_DECODE_SYMBOLX2_1(op3, &bitD3); 1978 HUF_DECODE_SYMBOLX2_1(op4, &bitD4); 1979 HUF_DECODE_SYMBOLX2_2(op1, &bitD1); 1980 HUF_DECODE_SYMBOLX2_2(op2, &bitD2); 1981 HUF_DECODE_SYMBOLX2_2(op3, &bitD3); 1982 HUF_DECODE_SYMBOLX2_2(op4, &bitD4); 1983 HUF_DECODE_SYMBOLX2_0(op1, &bitD1); 1984 HUF_DECODE_SYMBOLX2_0(op2, &bitD2); 1985 HUF_DECODE_SYMBOLX2_0(op3, &bitD3); 1986 HUF_DECODE_SYMBOLX2_0(op4, &bitD4); 1987 1988 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 1989 } 1990 1991 /* check corruption */ 1992 if (op1 > opStart2) return ERROR(corruption_detected); 1993 if (op2 > opStart3) return ERROR(corruption_detected); 1994 if (op3 > opStart4) return ERROR(corruption_detected); 1995 /* note : op4 supposed already verified within main loop */ 1996 1997 /* finish bitStreams one by one */ 1998 HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog); 1999 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog); 2000 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog); 2001 HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog); 2002 2003 /* check */ 2004 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4); 2005 if (!endSignal) return ERROR(corruption_detected); 2006 2007 /* decoded size */ 2008 return dstSize; 2009 } 2010 } 2011 2012 2013 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2014 { 2015 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG); 2016 const BYTE* ip = (const BYTE*) cSrc; 2017 size_t errorCode; 2018 2019 errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize); 2020 if (HUF_isError(errorCode)) return errorCode; 2021 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); 2022 ip += errorCode; 2023 cSrcSize -= errorCode; 2024 2025 return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2026 } 2027 2028 2029 /***************************/ 2030 /* double-symbols decoding */ 2031 /***************************/ 2032 2033 static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed, 2034 const U32* rankValOrigin, const int minWeight, 2035 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize, 2036 U32 nbBitsBaseline, U16 baseSeq) 2037 { 2038 HUF_DEltX4 DElt; 2039 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; 2040 U32 s; 2041 2042 /* get pre-calculated rankVal */ 2043 memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 2044 2045 /* fill skipped values */ 2046 if (minWeight>1) 2047 { 2048 U32 i, skipSize = rankVal[minWeight]; 2049 MEM_writeLE16(&(DElt.sequence), baseSeq); 2050 DElt.nbBits = (BYTE)(consumed); 2051 DElt.length = 1; 2052 for (i = 0; i < skipSize; i++) 2053 DTable[i] = DElt; 2054 } 2055 2056 /* fill DTable */ 2057 for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */ 2058 { 2059 const U32 symbol = sortedSymbols[s].symbol; 2060 const U32 weight = sortedSymbols[s].weight; 2061 const U32 nbBits = nbBitsBaseline - weight; 2062 const U32 length = 1 << (sizeLog-nbBits); 2063 const U32 start = rankVal[weight]; 2064 U32 i = start; 2065 const U32 end = start + length; 2066 2067 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8))); 2068 DElt.nbBits = (BYTE)(nbBits + consumed); 2069 DElt.length = 2; 2070 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */ 2071 2072 rankVal[weight] += length; 2073 } 2074 } 2075 2076 typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1]; 2077 2078 static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog, 2079 const sortedSymbol_t* sortedList, const U32 sortedListSize, 2080 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight, 2081 const U32 nbBitsBaseline) 2082 { 2083 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; 2084 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */ 2085 const U32 minBits = nbBitsBaseline - maxWeight; 2086 U32 s; 2087 2088 memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 2089 2090 /* fill DTable */ 2091 for (s=0; s<sortedListSize; s++) 2092 { 2093 const U16 symbol = sortedList[s].symbol; 2094 const U32 weight = sortedList[s].weight; 2095 const U32 nbBits = nbBitsBaseline - weight; 2096 const U32 start = rankVal[weight]; 2097 const U32 length = 1 << (targetLog-nbBits); 2098 2099 if (targetLog-nbBits >= minBits) /* enough room for a second symbol */ 2100 { 2101 U32 sortedRank; 2102 int minWeight = nbBits + scaleLog; 2103 if (minWeight < 1) minWeight = 1; 2104 sortedRank = rankStart[minWeight]; 2105 HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits, 2106 rankValOrigin[nbBits], minWeight, 2107 sortedList+sortedRank, sortedListSize-sortedRank, 2108 nbBitsBaseline, symbol); 2109 } 2110 else 2111 { 2112 U32 i; 2113 const U32 end = start + length; 2114 HUF_DEltX4 DElt; 2115 2116 MEM_writeLE16(&(DElt.sequence), symbol); 2117 DElt.nbBits = (BYTE)(nbBits); 2118 DElt.length = 1; 2119 for (i = start; i < end; i++) 2120 DTable[i] = DElt; 2121 } 2122 rankVal[weight] += length; 2123 } 2124 } 2125 2126 static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize) 2127 { 2128 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1]; 2129 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1]; 2130 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 }; 2131 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 }; 2132 U32* const rankStart = rankStart0+1; 2133 rankVal_t rankVal; 2134 U32 tableLog, maxW, sizeOfSort, nbSymbols; 2135 const U32 memLog = DTable[0]; 2136 size_t iSize; 2137 void* dtPtr = DTable; 2138 HUF_DEltX4* const dt = ((HUF_DEltX4*)dtPtr) + 1; 2139 2140 HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */ 2141 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge); 2142 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */ 2143 2144 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize); 2145 if (HUF_isError(iSize)) return iSize; 2146 2147 /* check result */ 2148 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */ 2149 2150 /* find maxWeight */ 2151 for (maxW = tableLog; rankStats[maxW]==0; maxW--) 2152 { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */ 2153 2154 /* Get start index of each weight */ 2155 { 2156 U32 w, nextRankStart = 0; 2157 for (w=1; w<=maxW; w++) 2158 { 2159 U32 current = nextRankStart; 2160 nextRankStart += rankStats[w]; 2161 rankStart[w] = current; 2162 } 2163 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/ 2164 sizeOfSort = nextRankStart; 2165 } 2166 2167 /* sort symbols by weight */ 2168 { 2169 U32 s; 2170 for (s=0; s<nbSymbols; s++) 2171 { 2172 U32 w = weightList[s]; 2173 U32 r = rankStart[w]++; 2174 sortedSymbol[r].symbol = (BYTE)s; 2175 sortedSymbol[r].weight = (BYTE)w; 2176 } 2177 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */ 2178 } 2179 2180 /* Build rankVal */ 2181 { 2182 const U32 minBits = tableLog+1 - maxW; 2183 U32 nextRankVal = 0; 2184 U32 w, consumed; 2185 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */ 2186 U32* rankVal0 = rankVal[0]; 2187 for (w=1; w<=maxW; w++) 2188 { 2189 U32 current = nextRankVal; 2190 nextRankVal += rankStats[w] << (w+rescale); 2191 rankVal0[w] = current; 2192 } 2193 for (consumed = minBits; consumed <= memLog - minBits; consumed++) 2194 { 2195 U32* rankValPtr = rankVal[consumed]; 2196 for (w = 1; w <= maxW; w++) 2197 { 2198 rankValPtr[w] = rankVal0[w] >> consumed; 2199 } 2200 } 2201 } 2202 2203 HUF_fillDTableX4(dt, memLog, 2204 sortedSymbol, sizeOfSort, 2205 rankStart0, rankVal, maxW, 2206 tableLog+1); 2207 2208 return iSize; 2209 } 2210 2211 2212 static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog) 2213 { 2214 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 2215 memcpy(op, dt+val, 2); 2216 BIT_skipBits(DStream, dt[val].nbBits); 2217 return dt[val].length; 2218 } 2219 2220 static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog) 2221 { 2222 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 2223 memcpy(op, dt+val, 1); 2224 if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits); 2225 else 2226 { 2227 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) 2228 { 2229 BIT_skipBits(DStream, dt[val].nbBits); 2230 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8)) 2231 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 */ 2232 } 2233 } 2234 return 1; 2235 } 2236 2237 2238 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \ 2239 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2240 2241 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \ 2242 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \ 2243 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2244 2245 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \ 2246 if (MEM_64bits()) \ 2247 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2248 2249 static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog) 2250 { 2251 BYTE* const pStart = p; 2252 2253 /* up to 8 symbols at a time */ 2254 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7)) 2255 { 2256 HUF_DECODE_SYMBOLX4_2(p, bitDPtr); 2257 HUF_DECODE_SYMBOLX4_1(p, bitDPtr); 2258 HUF_DECODE_SYMBOLX4_2(p, bitDPtr); 2259 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); 2260 } 2261 2262 /* closer to the end */ 2263 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2)) 2264 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); 2265 2266 while (p <= pEnd-2) 2267 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */ 2268 2269 if (p < pEnd) 2270 p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog); 2271 2272 return p-pStart; 2273 } 2274 2275 static size_t HUF_decompress4X4_usingDTable( 2276 void* dst, size_t dstSize, 2277 const void* cSrc, size_t cSrcSize, 2278 const U32* DTable) 2279 { 2280 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 2281 2282 { 2283 const BYTE* const istart = (const BYTE*) cSrc; 2284 BYTE* const ostart = (BYTE*) dst; 2285 BYTE* const oend = ostart + dstSize; 2286 const void* const dtPtr = DTable; 2287 const HUF_DEltX4* const dt = ((const HUF_DEltX4*)dtPtr) +1; 2288 const U32 dtLog = DTable[0]; 2289 size_t errorCode; 2290 2291 /* Init */ 2292 BIT_DStream_t bitD1; 2293 BIT_DStream_t bitD2; 2294 BIT_DStream_t bitD3; 2295 BIT_DStream_t bitD4; 2296 const size_t length1 = MEM_readLE16(istart); 2297 const size_t length2 = MEM_readLE16(istart+2); 2298 const size_t length3 = MEM_readLE16(istart+4); 2299 size_t length4; 2300 const BYTE* const istart1 = istart + 6; /* jumpTable */ 2301 const BYTE* const istart2 = istart1 + length1; 2302 const BYTE* const istart3 = istart2 + length2; 2303 const BYTE* const istart4 = istart3 + length3; 2304 const size_t segmentSize = (dstSize+3) / 4; 2305 BYTE* const opStart2 = ostart + segmentSize; 2306 BYTE* const opStart3 = opStart2 + segmentSize; 2307 BYTE* const opStart4 = opStart3 + segmentSize; 2308 BYTE* op1 = ostart; 2309 BYTE* op2 = opStart2; 2310 BYTE* op3 = opStart3; 2311 BYTE* op4 = opStart4; 2312 U32 endSignal; 2313 2314 length4 = cSrcSize - (length1 + length2 + length3 + 6); 2315 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 2316 errorCode = BIT_initDStream(&bitD1, istart1, length1); 2317 if (HUF_isError(errorCode)) return errorCode; 2318 errorCode = BIT_initDStream(&bitD2, istart2, length2); 2319 if (HUF_isError(errorCode)) return errorCode; 2320 errorCode = BIT_initDStream(&bitD3, istart3, length3); 2321 if (HUF_isError(errorCode)) return errorCode; 2322 errorCode = BIT_initDStream(&bitD4, istart4, length4); 2323 if (HUF_isError(errorCode)) return errorCode; 2324 2325 /* 16-32 symbols per loop (4-8 symbols per stream) */ 2326 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 2327 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; ) 2328 { 2329 HUF_DECODE_SYMBOLX4_2(op1, &bitD1); 2330 HUF_DECODE_SYMBOLX4_2(op2, &bitD2); 2331 HUF_DECODE_SYMBOLX4_2(op3, &bitD3); 2332 HUF_DECODE_SYMBOLX4_2(op4, &bitD4); 2333 HUF_DECODE_SYMBOLX4_1(op1, &bitD1); 2334 HUF_DECODE_SYMBOLX4_1(op2, &bitD2); 2335 HUF_DECODE_SYMBOLX4_1(op3, &bitD3); 2336 HUF_DECODE_SYMBOLX4_1(op4, &bitD4); 2337 HUF_DECODE_SYMBOLX4_2(op1, &bitD1); 2338 HUF_DECODE_SYMBOLX4_2(op2, &bitD2); 2339 HUF_DECODE_SYMBOLX4_2(op3, &bitD3); 2340 HUF_DECODE_SYMBOLX4_2(op4, &bitD4); 2341 HUF_DECODE_SYMBOLX4_0(op1, &bitD1); 2342 HUF_DECODE_SYMBOLX4_0(op2, &bitD2); 2343 HUF_DECODE_SYMBOLX4_0(op3, &bitD3); 2344 HUF_DECODE_SYMBOLX4_0(op4, &bitD4); 2345 2346 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 2347 } 2348 2349 /* check corruption */ 2350 if (op1 > opStart2) return ERROR(corruption_detected); 2351 if (op2 > opStart3) return ERROR(corruption_detected); 2352 if (op3 > opStart4) return ERROR(corruption_detected); 2353 /* note : op4 supposed already verified within main loop */ 2354 2355 /* finish bitStreams one by one */ 2356 HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog); 2357 HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog); 2358 HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog); 2359 HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog); 2360 2361 /* check */ 2362 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4); 2363 if (!endSignal) return ERROR(corruption_detected); 2364 2365 /* decoded size */ 2366 return dstSize; 2367 } 2368 } 2369 2370 2371 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2372 { 2373 HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG); 2374 const BYTE* ip = (const BYTE*) cSrc; 2375 2376 size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize); 2377 if (HUF_isError(hSize)) return hSize; 2378 if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 2379 ip += hSize; 2380 cSrcSize -= hSize; 2381 2382 return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2383 } 2384 2385 2386 /**********************************/ 2387 /* Generic decompression selector */ 2388 /**********************************/ 2389 2390 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t; 2391 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] = 2392 { 2393 /* single, double, quad */ 2394 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */ 2395 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */ 2396 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */ 2397 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */ 2398 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */ 2399 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */ 2400 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */ 2401 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */ 2402 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */ 2403 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */ 2404 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */ 2405 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */ 2406 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */ 2407 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */ 2408 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */ 2409 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */ 2410 }; 2411 2412 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); 2413 2414 static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2415 { 2416 static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL }; 2417 /* estimate decompression time */ 2418 U32 Q; 2419 const U32 D256 = (U32)(dstSize >> 8); 2420 U32 Dtime[3]; 2421 U32 algoNb = 0; 2422 int n; 2423 2424 /* validation checks */ 2425 if (dstSize == 0) return ERROR(dstSize_tooSmall); 2426 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */ 2427 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */ 2428 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */ 2429 2430 /* decoder timing evaluation */ 2431 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */ 2432 for (n=0; n<3; n++) 2433 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256); 2434 2435 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */ 2436 2437 if (Dtime[1] < Dtime[0]) algoNb = 1; 2438 2439 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize); 2440 2441 //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */ 2442 //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */ 2443 //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */ 2444 } 2445 2446 2447 2448 #endif /* ZSTD_CCOMMON_H_MODULE */ 2449 2450 2451 /* 2452 zstd - decompression module fo v0.4 legacy format 2453 Copyright (C) 2015-2016, Yann Collet. 2454 2455 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 2456 2457 Redistribution and use in source and binary forms, with or without 2458 modification, are permitted provided that the following conditions are 2459 met: 2460 * Redistributions of source code must retain the above copyright 2461 notice, this list of conditions and the following disclaimer. 2462 * Redistributions in binary form must reproduce the above 2463 copyright notice, this list of conditions and the following disclaimer 2464 in the documentation and/or other materials provided with the 2465 distribution. 2466 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2467 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2468 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2469 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2470 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2471 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2472 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2473 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2474 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2475 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2476 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2477 2478 You can contact the author at : 2479 - zstd source repository : https://github.com/Cyan4973/zstd 2480 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c 2481 */ 2482 2483 /* *************************************************************** 2484 * Tuning parameters 2485 *****************************************************************/ 2486 /*! 2487 * HEAPMODE : 2488 * Select how default decompression function ZSTD_decompress() will allocate memory, 2489 * in memory stack (0), or in memory heap (1, requires malloc()) 2490 */ 2491 #ifndef ZSTD_HEAPMODE 2492 # define ZSTD_HEAPMODE 1 2493 #endif 2494 2495 2496 /* ******************************************************* 2497 * Includes 2498 *********************************************************/ 2499 #include <stdlib.h> /* calloc */ 2500 #include <string.h> /* memcpy, memmove */ 2501 #include <stdio.h> /* debug : printf */ 2502 2503 2504 /* ******************************************************* 2505 * Compiler specifics 2506 *********************************************************/ 2507 #ifdef _MSC_VER /* Visual Studio */ 2508 # include <intrin.h> /* For Visual 2005 */ 2509 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 2510 # pragma warning(disable : 4324) /* disable: C4324: padded structure */ 2511 #endif 2512 2513 2514 /* ************************************* 2515 * Local types 2516 ***************************************/ 2517 typedef struct 2518 { 2519 blockType_t blockType; 2520 U32 origSize; 2521 } blockProperties_t; 2522 2523 2524 /* ******************************************************* 2525 * Memory operations 2526 **********************************************************/ 2527 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); } 2528 2529 2530 /* ************************************* 2531 * Error Management 2532 ***************************************/ 2533 2534 /*! ZSTD_isError 2535 * tells if a return value is an error code */ 2536 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); } 2537 2538 2539 /* ************************************************************* 2540 * Context management 2541 ***************************************************************/ 2542 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader, 2543 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock } ZSTD_dStage; 2544 2545 struct ZSTDv04_Dctx_s 2546 { 2547 U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)]; 2548 U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)]; 2549 U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)]; 2550 const void* previousDstEnd; 2551 const void* base; 2552 const void* vBase; 2553 const void* dictEnd; 2554 size_t expected; 2555 size_t headerSize; 2556 ZSTD_parameters params; 2557 blockType_t bType; 2558 ZSTD_dStage stage; 2559 const BYTE* litPtr; 2560 size_t litSize; 2561 BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */]; 2562 BYTE headerBuffer[ZSTD_frameHeaderSize_max]; 2563 }; /* typedef'd to ZSTD_DCtx within "zstd_static.h" */ 2564 2565 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx) 2566 { 2567 dctx->expected = ZSTD_frameHeaderSize_min; 2568 dctx->stage = ZSTDds_getFrameHeaderSize; 2569 dctx->previousDstEnd = NULL; 2570 dctx->base = NULL; 2571 dctx->vBase = NULL; 2572 dctx->dictEnd = NULL; 2573 return 0; 2574 } 2575 2576 static ZSTD_DCtx* ZSTD_createDCtx(void) 2577 { 2578 ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx)); 2579 if (dctx==NULL) return NULL; 2580 ZSTD_resetDCtx(dctx); 2581 return dctx; 2582 } 2583 2584 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx) 2585 { 2586 free(dctx); 2587 return 0; 2588 } 2589 2590 2591 /* ************************************************************* 2592 * Decompression section 2593 ***************************************************************/ 2594 /** ZSTD_decodeFrameHeader_Part1 2595 * decode the 1st part of the Frame Header, which tells Frame Header size. 2596 * srcSize must be == ZSTD_frameHeaderSize_min 2597 * @return : the full size of the Frame Header */ 2598 static size_t ZSTD_decodeFrameHeader_Part1(ZSTD_DCtx* zc, const void* src, size_t srcSize) 2599 { 2600 U32 magicNumber; 2601 if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong); 2602 magicNumber = MEM_readLE32(src); 2603 if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown); 2604 zc->headerSize = ZSTD_frameHeaderSize_min; 2605 return zc->headerSize; 2606 } 2607 2608 2609 static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize) 2610 { 2611 U32 magicNumber; 2612 if (srcSize < ZSTD_frameHeaderSize_min) return ZSTD_frameHeaderSize_max; 2613 magicNumber = MEM_readLE32(src); 2614 if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown); 2615 memset(params, 0, sizeof(*params)); 2616 params->windowLog = (((const BYTE*)src)[4] & 15) + ZSTD_WINDOWLOG_ABSOLUTEMIN; 2617 if ((((const BYTE*)src)[4] >> 4) != 0) return ERROR(frameParameter_unsupported); /* reserved bits */ 2618 return 0; 2619 } 2620 2621 /** ZSTD_decodeFrameHeader_Part2 2622 * decode the full Frame Header 2623 * srcSize must be the size provided by ZSTD_decodeFrameHeader_Part1 2624 * @return : 0, or an error code, which can be tested using ZSTD_isError() */ 2625 static size_t ZSTD_decodeFrameHeader_Part2(ZSTD_DCtx* zc, const void* src, size_t srcSize) 2626 { 2627 size_t result; 2628 if (srcSize != zc->headerSize) return ERROR(srcSize_wrong); 2629 result = ZSTD_getFrameParams(&(zc->params), src, srcSize); 2630 if ((MEM_32bits()) && (zc->params.windowLog > 25)) return ERROR(frameParameter_unsupported); 2631 return result; 2632 } 2633 2634 2635 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr) 2636 { 2637 const BYTE* const in = (const BYTE* const)src; 2638 BYTE headerFlags; 2639 U32 cSize; 2640 2641 if (srcSize < 3) return ERROR(srcSize_wrong); 2642 2643 headerFlags = *in; 2644 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16); 2645 2646 bpPtr->blockType = (blockType_t)(headerFlags >> 6); 2647 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0; 2648 2649 if (bpPtr->blockType == bt_end) return 0; 2650 if (bpPtr->blockType == bt_rle) return 1; 2651 return cSize; 2652 } 2653 2654 static size_t ZSTD_copyRawBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 2655 { 2656 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall); 2657 memcpy(dst, src, srcSize); 2658 return srcSize; 2659 } 2660 2661 2662 /** ZSTD_decompressLiterals 2663 @return : nb of bytes read from src, or an error code*/ 2664 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr, 2665 const void* src, size_t srcSize) 2666 { 2667 const BYTE* ip = (const BYTE*)src; 2668 2669 const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 2670 const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 2671 2672 if (litSize > *maxDstSizePtr) return ERROR(corruption_detected); 2673 if (litCSize + 5 > srcSize) return ERROR(corruption_detected); 2674 2675 if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected); 2676 2677 *maxDstSizePtr = litSize; 2678 return litCSize + 5; 2679 } 2680 2681 2682 /** ZSTD_decodeLiteralsBlock 2683 @return : nb of bytes read from src (< srcSize ) */ 2684 static size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx, 2685 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */ 2686 { 2687 const BYTE* const istart = (const BYTE*) src; 2688 2689 /* any compressed block with literals segment must be at least this size */ 2690 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected); 2691 2692 switch(*istart & 3) 2693 { 2694 /* compressed */ 2695 case 0: 2696 { 2697 size_t litSize = BLOCKSIZE; 2698 const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize); 2699 dctx->litPtr = dctx->litBuffer; 2700 dctx->litSize = litSize; 2701 memset(dctx->litBuffer + dctx->litSize, 0, 8); 2702 return readSize; /* works if it's an error too */ 2703 } 2704 case IS_RAW: 2705 { 2706 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 2707 if (litSize > srcSize-11) /* risk of reading too far with wildcopy */ 2708 { 2709 if (litSize > srcSize-3) return ERROR(corruption_detected); 2710 memcpy(dctx->litBuffer, istart, litSize); 2711 dctx->litPtr = dctx->litBuffer; 2712 dctx->litSize = litSize; 2713 memset(dctx->litBuffer + dctx->litSize, 0, 8); 2714 return litSize+3; 2715 } 2716 /* direct reference into compressed stream */ 2717 dctx->litPtr = istart+3; 2718 dctx->litSize = litSize; 2719 return litSize+3; } 2720 case IS_RLE: 2721 { 2722 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 2723 if (litSize > BLOCKSIZE) return ERROR(corruption_detected); 2724 memset(dctx->litBuffer, istart[3], litSize + 8); 2725 dctx->litPtr = dctx->litBuffer; 2726 dctx->litSize = litSize; 2727 return 4; 2728 } 2729 default: 2730 return ERROR(corruption_detected); /* forbidden nominal case */ 2731 } 2732 } 2733 2734 2735 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr, 2736 FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb, 2737 const void* src, size_t srcSize) 2738 { 2739 const BYTE* const istart = (const BYTE* const)src; 2740 const BYTE* ip = istart; 2741 const BYTE* const iend = istart + srcSize; 2742 U32 LLtype, Offtype, MLtype; 2743 U32 LLlog, Offlog, MLlog; 2744 size_t dumpsLength; 2745 2746 /* check */ 2747 if (srcSize < 5) return ERROR(srcSize_wrong); 2748 2749 /* SeqHead */ 2750 *nbSeq = MEM_readLE16(ip); ip+=2; 2751 LLtype = *ip >> 6; 2752 Offtype = (*ip >> 4) & 3; 2753 MLtype = (*ip >> 2) & 3; 2754 if (*ip & 2) 2755 { 2756 dumpsLength = ip[2]; 2757 dumpsLength += ip[1] << 8; 2758 ip += 3; 2759 } 2760 else 2761 { 2762 dumpsLength = ip[1]; 2763 dumpsLength += (ip[0] & 1) << 8; 2764 ip += 2; 2765 } 2766 *dumpsPtr = ip; 2767 ip += dumpsLength; 2768 *dumpsLengthPtr = dumpsLength; 2769 2770 /* check */ 2771 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */ 2772 2773 /* sequences */ 2774 { 2775 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL >= MaxOff */ 2776 size_t headerSize; 2777 2778 /* Build DTables */ 2779 switch(LLtype) 2780 { 2781 case bt_rle : 2782 LLlog = 0; 2783 FSE_buildDTable_rle(DTableLL, *ip++); break; 2784 case bt_raw : 2785 LLlog = LLbits; 2786 FSE_buildDTable_raw(DTableLL, LLbits); break; 2787 default : 2788 { U32 max = MaxLL; 2789 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip); 2790 if (FSE_isError(headerSize)) return ERROR(GENERIC); 2791 if (LLlog > LLFSELog) return ERROR(corruption_detected); 2792 ip += headerSize; 2793 FSE_buildDTable(DTableLL, norm, max, LLlog); 2794 } } 2795 2796 switch(Offtype) 2797 { 2798 case bt_rle : 2799 Offlog = 0; 2800 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 2801 FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */ 2802 break; 2803 case bt_raw : 2804 Offlog = Offbits; 2805 FSE_buildDTable_raw(DTableOffb, Offbits); break; 2806 default : 2807 { U32 max = MaxOff; 2808 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip); 2809 if (FSE_isError(headerSize)) return ERROR(GENERIC); 2810 if (Offlog > OffFSELog) return ERROR(corruption_detected); 2811 ip += headerSize; 2812 FSE_buildDTable(DTableOffb, norm, max, Offlog); 2813 } } 2814 2815 switch(MLtype) 2816 { 2817 case bt_rle : 2818 MLlog = 0; 2819 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 2820 FSE_buildDTable_rle(DTableML, *ip++); break; 2821 case bt_raw : 2822 MLlog = MLbits; 2823 FSE_buildDTable_raw(DTableML, MLbits); break; 2824 default : 2825 { U32 max = MaxML; 2826 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip); 2827 if (FSE_isError(headerSize)) return ERROR(GENERIC); 2828 if (MLlog > MLFSELog) return ERROR(corruption_detected); 2829 ip += headerSize; 2830 FSE_buildDTable(DTableML, norm, max, MLlog); 2831 } } } 2832 2833 return ip-istart; 2834 } 2835 2836 2837 typedef struct { 2838 size_t litLength; 2839 size_t offset; 2840 size_t matchLength; 2841 } seq_t; 2842 2843 typedef struct { 2844 BIT_DStream_t DStream; 2845 FSE_DState_t stateLL; 2846 FSE_DState_t stateOffb; 2847 FSE_DState_t stateML; 2848 size_t prevOffset; 2849 const BYTE* dumps; 2850 const BYTE* dumpsEnd; 2851 } seqState_t; 2852 2853 2854 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState) 2855 { 2856 size_t litLength; 2857 size_t prevOffset; 2858 size_t offset; 2859 size_t matchLength; 2860 const BYTE* dumps = seqState->dumps; 2861 const BYTE* const de = seqState->dumpsEnd; 2862 2863 /* Literal length */ 2864 litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream)); 2865 prevOffset = litLength ? seq->offset : seqState->prevOffset; 2866 if (litLength == MaxLL) { 2867 U32 add = *dumps++; 2868 if (add < 255) litLength += add; 2869 else { 2870 litLength = dumps[0] + (dumps[1]<<8) + (dumps[2]<<16); 2871 dumps += 3; 2872 } 2873 if (dumps > de) { litLength = MaxLL+255; } /* late correction, to avoid using uninitialized memory */ 2874 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */ 2875 } 2876 2877 /* Offset */ 2878 { static const U32 offsetPrefix[MaxOff+1] = { 2879 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256, 2880 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 2881 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 }; 2882 U32 offsetCode, nbBits; 2883 offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */ 2884 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream)); 2885 nbBits = offsetCode - 1; 2886 if (offsetCode==0) nbBits = 0; /* cmove */ 2887 offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits); 2888 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream)); 2889 if (offsetCode==0) offset = prevOffset; /* cmove */ 2890 if (offsetCode | !litLength) seqState->prevOffset = seq->offset; /* cmove */ 2891 } 2892 2893 /* MatchLength */ 2894 matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream)); 2895 if (matchLength == MaxML) { 2896 U32 add = *dumps++; 2897 if (add < 255) matchLength += add; 2898 else { 2899 matchLength = dumps[0] + (dumps[1]<<8) + (dumps[2]<<16); 2900 dumps += 3; 2901 } 2902 if (dumps > de) { matchLength = MaxML+255; } /* late correction, to avoid using uninitialized memory */ 2903 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */ 2904 } 2905 matchLength += MINMATCH; 2906 2907 /* save result */ 2908 seq->litLength = litLength; 2909 seq->offset = offset; 2910 seq->matchLength = matchLength; 2911 seqState->dumps = dumps; 2912 } 2913 2914 2915 static size_t ZSTD_execSequence(BYTE* op, 2916 BYTE* const oend, seq_t sequence, 2917 const BYTE** litPtr, const BYTE* const litLimit, 2918 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd) 2919 { 2920 static const int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */ 2921 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */ 2922 BYTE* const oLitEnd = op + sequence.litLength; 2923 const size_t sequenceLength = sequence.litLength + sequence.matchLength; 2924 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */ 2925 BYTE* const oend_8 = oend-8; 2926 const BYTE* const litEnd = *litPtr + sequence.litLength; 2927 const BYTE* match = oLitEnd - sequence.offset; 2928 2929 /* check */ 2930 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */ 2931 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */ 2932 if (litEnd > litLimit) return ERROR(corruption_detected); /* risk read beyond lit buffer */ 2933 2934 /* copy Literals */ 2935 ZSTD_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */ 2936 op = oLitEnd; 2937 *litPtr = litEnd; /* update for next sequence */ 2938 2939 /* copy Match */ 2940 if (sequence.offset > (size_t)(oLitEnd - base)) 2941 { 2942 /* offset beyond prefix */ 2943 if (sequence.offset > (size_t)(oLitEnd - vBase)) 2944 return ERROR(corruption_detected); 2945 match = dictEnd - (base-match); 2946 if (match + sequence.matchLength <= dictEnd) 2947 { 2948 memmove(oLitEnd, match, sequence.matchLength); 2949 return sequenceLength; 2950 } 2951 /* span extDict & currentPrefixSegment */ 2952 { 2953 size_t length1 = dictEnd - match; 2954 memmove(oLitEnd, match, length1); 2955 op = oLitEnd + length1; 2956 sequence.matchLength -= length1; 2957 match = base; 2958 if (op > oend_8 || sequence.matchLength < MINMATCH) { 2959 while (op < oMatchEnd) *op++ = *match++; 2960 return sequenceLength; 2961 } 2962 } 2963 } 2964 /* Requirement: op <= oend_8 */ 2965 2966 /* match within prefix */ 2967 if (sequence.offset < 8) { 2968 /* close range match, overlap */ 2969 const int sub2 = dec64table[sequence.offset]; 2970 op[0] = match[0]; 2971 op[1] = match[1]; 2972 op[2] = match[2]; 2973 op[3] = match[3]; 2974 match += dec32table[sequence.offset]; 2975 ZSTD_copy4(op+4, match); 2976 match -= sub2; 2977 } else { 2978 ZSTD_copy8(op, match); 2979 } 2980 op += 8; match += 8; 2981 2982 if (oMatchEnd > oend-(16-MINMATCH)) 2983 { 2984 if (op < oend_8) 2985 { 2986 ZSTD_wildcopy(op, match, oend_8 - op); 2987 match += oend_8 - op; 2988 op = oend_8; 2989 } 2990 while (op < oMatchEnd) *op++ = *match++; 2991 } 2992 else 2993 { 2994 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */ 2995 } 2996 return sequenceLength; 2997 } 2998 2999 3000 static size_t ZSTD_decompressSequences( 3001 ZSTD_DCtx* dctx, 3002 void* dst, size_t maxDstSize, 3003 const void* seqStart, size_t seqSize) 3004 { 3005 const BYTE* ip = (const BYTE*)seqStart; 3006 const BYTE* const iend = ip + seqSize; 3007 BYTE* const ostart = (BYTE* const)dst; 3008 BYTE* op = ostart; 3009 BYTE* const oend = ostart + maxDstSize; 3010 size_t errorCode, dumpsLength; 3011 const BYTE* litPtr = dctx->litPtr; 3012 const BYTE* const litEnd = litPtr + dctx->litSize; 3013 int nbSeq; 3014 const BYTE* dumps; 3015 U32* DTableLL = dctx->LLTable; 3016 U32* DTableML = dctx->MLTable; 3017 U32* DTableOffb = dctx->OffTable; 3018 const BYTE* const base = (const BYTE*) (dctx->base); 3019 const BYTE* const vBase = (const BYTE*) (dctx->vBase); 3020 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd); 3021 3022 /* Build Decoding Tables */ 3023 errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength, 3024 DTableLL, DTableML, DTableOffb, 3025 ip, iend-ip); 3026 if (ZSTD_isError(errorCode)) return errorCode; 3027 ip += errorCode; 3028 3029 /* Regen sequences */ 3030 { 3031 seq_t sequence; 3032 seqState_t seqState; 3033 3034 memset(&sequence, 0, sizeof(sequence)); 3035 sequence.offset = 4; 3036 seqState.dumps = dumps; 3037 seqState.dumpsEnd = dumps + dumpsLength; 3038 seqState.prevOffset = 4; 3039 errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip); 3040 if (ERR_isError(errorCode)) return ERROR(corruption_detected); 3041 FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL); 3042 FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb); 3043 FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML); 3044 3045 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; ) 3046 { 3047 size_t oneSeqSize; 3048 nbSeq--; 3049 ZSTD_decodeSequence(&sequence, &seqState); 3050 oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd); 3051 if (ZSTD_isError(oneSeqSize)) return oneSeqSize; 3052 op += oneSeqSize; 3053 } 3054 3055 /* check if reached exact end */ 3056 if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* DStream should be entirely and exactly consumed; otherwise data is corrupted */ 3057 3058 /* last literal segment */ 3059 { 3060 size_t lastLLSize = litEnd - litPtr; 3061 if (litPtr > litEnd) return ERROR(corruption_detected); 3062 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall); 3063 if (op != litPtr) memcpy(op, litPtr, lastLLSize); 3064 op += lastLLSize; 3065 } 3066 } 3067 3068 return op-ostart; 3069 } 3070 3071 3072 static void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst) 3073 { 3074 if (dst != dctx->previousDstEnd) /* not contiguous */ 3075 { 3076 dctx->dictEnd = dctx->previousDstEnd; 3077 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); 3078 dctx->base = dst; 3079 dctx->previousDstEnd = dst; 3080 } 3081 } 3082 3083 3084 static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx, 3085 void* dst, size_t maxDstSize, 3086 const void* src, size_t srcSize) 3087 { 3088 /* blockType == blockCompressed */ 3089 const BYTE* ip = (const BYTE*)src; 3090 3091 /* Decode literals sub-block */ 3092 size_t litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize); 3093 if (ZSTD_isError(litCSize)) return litCSize; 3094 ip += litCSize; 3095 srcSize -= litCSize; 3096 3097 return ZSTD_decompressSequences(dctx, dst, maxDstSize, ip, srcSize); 3098 } 3099 3100 3101 static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx, 3102 void* dst, size_t maxDstSize, 3103 const void* src, size_t srcSize, 3104 const void* dict, size_t dictSize) 3105 { 3106 const BYTE* ip = (const BYTE*)src; 3107 const BYTE* iend = ip + srcSize; 3108 BYTE* const ostart = (BYTE* const)dst; 3109 BYTE* op = ostart; 3110 BYTE* const oend = ostart + maxDstSize; 3111 size_t remainingSize = srcSize; 3112 blockProperties_t blockProperties; 3113 3114 /* init */ 3115 ZSTD_resetDCtx(ctx); 3116 if (dict) 3117 { 3118 ZSTD_decompress_insertDictionary(ctx, dict, dictSize); 3119 ctx->dictEnd = ctx->previousDstEnd; 3120 ctx->vBase = (const char*)dst - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base)); 3121 ctx->base = dst; 3122 } 3123 else 3124 { 3125 ctx->vBase = ctx->base = ctx->dictEnd = dst; 3126 } 3127 3128 /* Frame Header */ 3129 { 3130 size_t frameHeaderSize; 3131 if (srcSize < ZSTD_frameHeaderSize_min+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong); 3132 frameHeaderSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min); 3133 if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize; 3134 if (srcSize < frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong); 3135 ip += frameHeaderSize; remainingSize -= frameHeaderSize; 3136 frameHeaderSize = ZSTD_decodeFrameHeader_Part2(ctx, src, frameHeaderSize); 3137 if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize; 3138 } 3139 3140 /* Loop on each block */ 3141 while (1) 3142 { 3143 size_t decodedSize=0; 3144 size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties); 3145 if (ZSTD_isError(cBlockSize)) return cBlockSize; 3146 3147 ip += ZSTD_blockHeaderSize; 3148 remainingSize -= ZSTD_blockHeaderSize; 3149 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); 3150 3151 switch(blockProperties.blockType) 3152 { 3153 case bt_compressed: 3154 decodedSize = ZSTD_decompressBlock_internal(ctx, op, oend-op, ip, cBlockSize); 3155 break; 3156 case bt_raw : 3157 decodedSize = ZSTD_copyRawBlock(op, oend-op, ip, cBlockSize); 3158 break; 3159 case bt_rle : 3160 return ERROR(GENERIC); /* not yet supported */ 3161 break; 3162 case bt_end : 3163 /* end of frame */ 3164 if (remainingSize) return ERROR(srcSize_wrong); 3165 break; 3166 default: 3167 return ERROR(GENERIC); /* impossible */ 3168 } 3169 if (cBlockSize == 0) break; /* bt_end */ 3170 3171 if (ZSTD_isError(decodedSize)) return decodedSize; 3172 op += decodedSize; 3173 ip += cBlockSize; 3174 remainingSize -= cBlockSize; 3175 } 3176 3177 return op-ostart; 3178 } 3179 3180 static size_t ZSTD_findFrameCompressedSize(const void* src, size_t srcSize) 3181 { 3182 const BYTE* ip = (const BYTE*)src; 3183 size_t remainingSize = srcSize; 3184 blockProperties_t blockProperties; 3185 3186 /* Frame Header */ 3187 if (srcSize < ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong); 3188 if (MEM_readLE32(src) != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown); 3189 ip += ZSTD_frameHeaderSize_min; remainingSize -= ZSTD_frameHeaderSize_min; 3190 3191 /* Loop on each block */ 3192 while (1) 3193 { 3194 size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties); 3195 if (ZSTD_isError(cBlockSize)) return cBlockSize; 3196 3197 ip += ZSTD_blockHeaderSize; 3198 remainingSize -= ZSTD_blockHeaderSize; 3199 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); 3200 3201 if (cBlockSize == 0) break; /* bt_end */ 3202 3203 ip += cBlockSize; 3204 remainingSize -= cBlockSize; 3205 } 3206 3207 return ip - (const BYTE*)src; 3208 } 3209 3210 /* ****************************** 3211 * Streaming Decompression API 3212 ********************************/ 3213 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx) 3214 { 3215 return dctx->expected; 3216 } 3217 3218 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3219 { 3220 /* Sanity check */ 3221 if (srcSize != ctx->expected) return ERROR(srcSize_wrong); 3222 ZSTD_checkContinuity(ctx, dst); 3223 3224 /* Decompress : frame header; part 1 */ 3225 switch (ctx->stage) 3226 { 3227 case ZSTDds_getFrameHeaderSize : 3228 /* get frame header size */ 3229 if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */ 3230 ctx->headerSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min); 3231 if (ZSTD_isError(ctx->headerSize)) return ctx->headerSize; 3232 memcpy(ctx->headerBuffer, src, ZSTD_frameHeaderSize_min); 3233 if (ctx->headerSize > ZSTD_frameHeaderSize_min) return ERROR(GENERIC); /* impossible */ 3234 ctx->expected = 0; /* not necessary to copy more */ 3235 /* fallthrough */ 3236 case ZSTDds_decodeFrameHeader: 3237 /* get frame header */ 3238 { size_t const result = ZSTD_decodeFrameHeader_Part2(ctx, ctx->headerBuffer, ctx->headerSize); 3239 if (ZSTD_isError(result)) return result; 3240 ctx->expected = ZSTD_blockHeaderSize; 3241 ctx->stage = ZSTDds_decodeBlockHeader; 3242 return 0; 3243 } 3244 case ZSTDds_decodeBlockHeader: 3245 /* Decode block header */ 3246 { blockProperties_t bp; 3247 size_t const blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp); 3248 if (ZSTD_isError(blockSize)) return blockSize; 3249 if (bp.blockType == bt_end) 3250 { 3251 ctx->expected = 0; 3252 ctx->stage = ZSTDds_getFrameHeaderSize; 3253 } 3254 else 3255 { 3256 ctx->expected = blockSize; 3257 ctx->bType = bp.blockType; 3258 ctx->stage = ZSTDds_decompressBlock; 3259 } 3260 return 0; 3261 } 3262 case ZSTDds_decompressBlock: 3263 { 3264 /* Decompress : block content */ 3265 size_t rSize; 3266 switch(ctx->bType) 3267 { 3268 case bt_compressed: 3269 rSize = ZSTD_decompressBlock_internal(ctx, dst, maxDstSize, src, srcSize); 3270 break; 3271 case bt_raw : 3272 rSize = ZSTD_copyRawBlock(dst, maxDstSize, src, srcSize); 3273 break; 3274 case bt_rle : 3275 return ERROR(GENERIC); /* not yet handled */ 3276 break; 3277 case bt_end : /* should never happen (filtered at phase 1) */ 3278 rSize = 0; 3279 break; 3280 default: 3281 return ERROR(GENERIC); 3282 } 3283 ctx->stage = ZSTDds_decodeBlockHeader; 3284 ctx->expected = ZSTD_blockHeaderSize; 3285 ctx->previousDstEnd = (char*)dst + rSize; 3286 return rSize; 3287 } 3288 default: 3289 return ERROR(GENERIC); /* impossible */ 3290 } 3291 } 3292 3293 3294 static void ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* dict, size_t dictSize) 3295 { 3296 ctx->dictEnd = ctx->previousDstEnd; 3297 ctx->vBase = (const char*)dict - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base)); 3298 ctx->base = dict; 3299 ctx->previousDstEnd = (const char*)dict + dictSize; 3300 } 3301 3302 3303 3304 /* 3305 Buffered version of Zstd compression library 3306 Copyright (C) 2015, Yann Collet. 3307 3308 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 3309 3310 Redistribution and use in source and binary forms, with or without 3311 modification, are permitted provided that the following conditions are 3312 met: 3313 * Redistributions of source code must retain the above copyright 3314 notice, this list of conditions and the following disclaimer. 3315 * Redistributions in binary form must reproduce the above 3316 copyright notice, this list of conditions and the following disclaimer 3317 in the documentation and/or other materials provided with the 3318 distribution. 3319 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 3320 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 3321 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 3322 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 3323 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3324 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3325 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3326 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3327 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3328 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3329 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3330 3331 You can contact the author at : 3332 - zstd source repository : https://github.com/Cyan4973/zstd 3333 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c 3334 */ 3335 3336 /* The objects defined into this file should be considered experimental. 3337 * They are not labelled stable, as their prototype may change in the future. 3338 * You can use them for tests, provide feedback, or if you can endure risk of future changes. 3339 */ 3340 3341 /* ************************************* 3342 * Includes 3343 ***************************************/ 3344 #include <stdlib.h> 3345 3346 3347 /** ************************************************ 3348 * Streaming decompression 3349 * 3350 * A ZBUFF_DCtx object is required to track streaming operation. 3351 * Use ZBUFF_createDCtx() and ZBUFF_freeDCtx() to create/release resources. 3352 * Use ZBUFF_decompressInit() to start a new decompression operation. 3353 * ZBUFF_DCtx objects can be reused multiple times. 3354 * 3355 * Use ZBUFF_decompressContinue() repetitively to consume your input. 3356 * *srcSizePtr and *maxDstSizePtr can be any size. 3357 * The function will report how many bytes were read or written by modifying *srcSizePtr and *maxDstSizePtr. 3358 * Note that it may not consume the entire input, in which case it's up to the caller to call again the function with remaining input. 3359 * The content of dst will be overwritten (up to *maxDstSizePtr) at each function call, so save its content if it matters or change dst . 3360 * return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency) 3361 * or 0 when a frame is completely decoded 3362 * or an error code, which can be tested using ZBUFF_isError(). 3363 * 3364 * Hint : recommended buffer sizes (not compulsory) 3365 * output : 128 KB block size is the internal unit, it ensures it's always possible to write a full block when it's decoded. 3366 * input : just follow indications from ZBUFF_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 . 3367 * **************************************************/ 3368 3369 typedef enum { ZBUFFds_init, ZBUFFds_readHeader, ZBUFFds_loadHeader, ZBUFFds_decodeHeader, 3370 ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFF_dStage; 3371 3372 /* *** Resource management *** */ 3373 3374 #define ZSTD_frameHeaderSize_max 5 /* too magical, should come from reference */ 3375 struct ZBUFFv04_DCtx_s { 3376 ZSTD_DCtx* zc; 3377 ZSTD_parameters params; 3378 char* inBuff; 3379 size_t inBuffSize; 3380 size_t inPos; 3381 char* outBuff; 3382 size_t outBuffSize; 3383 size_t outStart; 3384 size_t outEnd; 3385 size_t hPos; 3386 const char* dict; 3387 size_t dictSize; 3388 ZBUFF_dStage stage; 3389 unsigned char headerBuffer[ZSTD_frameHeaderSize_max]; 3390 }; /* typedef'd to ZBUFF_DCtx within "zstd_buffered.h" */ 3391 3392 typedef ZBUFFv04_DCtx ZBUFF_DCtx; 3393 3394 3395 static ZBUFF_DCtx* ZBUFF_createDCtx(void) 3396 { 3397 ZBUFF_DCtx* zbc = (ZBUFF_DCtx*)malloc(sizeof(ZBUFF_DCtx)); 3398 if (zbc==NULL) return NULL; 3399 memset(zbc, 0, sizeof(*zbc)); 3400 zbc->zc = ZSTD_createDCtx(); 3401 zbc->stage = ZBUFFds_init; 3402 return zbc; 3403 } 3404 3405 static size_t ZBUFF_freeDCtx(ZBUFF_DCtx* zbc) 3406 { 3407 if (zbc==NULL) return 0; /* support free on null */ 3408 ZSTD_freeDCtx(zbc->zc); 3409 free(zbc->inBuff); 3410 free(zbc->outBuff); 3411 free(zbc); 3412 return 0; 3413 } 3414 3415 3416 /* *** Initialization *** */ 3417 3418 static size_t ZBUFF_decompressInit(ZBUFF_DCtx* zbc) 3419 { 3420 zbc->stage = ZBUFFds_readHeader; 3421 zbc->hPos = zbc->inPos = zbc->outStart = zbc->outEnd = zbc->dictSize = 0; 3422 return ZSTD_resetDCtx(zbc->zc); 3423 } 3424 3425 3426 static size_t ZBUFF_decompressWithDictionary(ZBUFF_DCtx* zbc, const void* src, size_t srcSize) 3427 { 3428 zbc->dict = (const char*)src; 3429 zbc->dictSize = srcSize; 3430 return 0; 3431 } 3432 3433 static size_t ZBUFF_limitCopy(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3434 { 3435 size_t length = MIN(maxDstSize, srcSize); 3436 memcpy(dst, src, length); 3437 return length; 3438 } 3439 3440 /* *** Decompression *** */ 3441 3442 static size_t ZBUFF_decompressContinue(ZBUFF_DCtx* zbc, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr) 3443 { 3444 const char* const istart = (const char*)src; 3445 const char* ip = istart; 3446 const char* const iend = istart + *srcSizePtr; 3447 char* const ostart = (char*)dst; 3448 char* op = ostart; 3449 char* const oend = ostart + *maxDstSizePtr; 3450 U32 notDone = 1; 3451 3452 DEBUGLOG(5, "ZBUFF_decompressContinue"); 3453 while (notDone) 3454 { 3455 switch(zbc->stage) 3456 { 3457 3458 case ZBUFFds_init : 3459 DEBUGLOG(5, "ZBUFF_decompressContinue: stage==ZBUFFds_init => ERROR(init_missing)"); 3460 return ERROR(init_missing); 3461 3462 case ZBUFFds_readHeader : 3463 /* read header from src */ 3464 { size_t const headerSize = ZSTD_getFrameParams(&(zbc->params), src, *srcSizePtr); 3465 if (ZSTD_isError(headerSize)) return headerSize; 3466 if (headerSize) { 3467 /* not enough input to decode header : tell how many bytes would be necessary */ 3468 memcpy(zbc->headerBuffer+zbc->hPos, src, *srcSizePtr); 3469 zbc->hPos += *srcSizePtr; 3470 *maxDstSizePtr = 0; 3471 zbc->stage = ZBUFFds_loadHeader; 3472 return headerSize - zbc->hPos; 3473 } 3474 zbc->stage = ZBUFFds_decodeHeader; 3475 break; 3476 } 3477 3478 case ZBUFFds_loadHeader: 3479 /* complete header from src */ 3480 { size_t headerSize = ZBUFF_limitCopy( 3481 zbc->headerBuffer + zbc->hPos, ZSTD_frameHeaderSize_max - zbc->hPos, 3482 src, *srcSizePtr); 3483 zbc->hPos += headerSize; 3484 ip += headerSize; 3485 headerSize = ZSTD_getFrameParams(&(zbc->params), zbc->headerBuffer, zbc->hPos); 3486 if (ZSTD_isError(headerSize)) return headerSize; 3487 if (headerSize) { 3488 /* not enough input to decode header : tell how many bytes would be necessary */ 3489 *maxDstSizePtr = 0; 3490 return headerSize - zbc->hPos; 3491 } } 3492 /* intentional fallthrough */ 3493 3494 case ZBUFFds_decodeHeader: 3495 /* apply header to create / resize buffers */ 3496 { size_t const neededOutSize = (size_t)1 << zbc->params.windowLog; 3497 size_t const neededInSize = BLOCKSIZE; /* a block is never > BLOCKSIZE */ 3498 if (zbc->inBuffSize < neededInSize) { 3499 free(zbc->inBuff); 3500 zbc->inBuffSize = neededInSize; 3501 zbc->inBuff = (char*)malloc(neededInSize); 3502 if (zbc->inBuff == NULL) return ERROR(memory_allocation); 3503 } 3504 if (zbc->outBuffSize < neededOutSize) { 3505 free(zbc->outBuff); 3506 zbc->outBuffSize = neededOutSize; 3507 zbc->outBuff = (char*)malloc(neededOutSize); 3508 if (zbc->outBuff == NULL) return ERROR(memory_allocation); 3509 } } 3510 if (zbc->dictSize) 3511 ZSTD_decompress_insertDictionary(zbc->zc, zbc->dict, zbc->dictSize); 3512 if (zbc->hPos) { 3513 /* some data already loaded into headerBuffer : transfer into inBuff */ 3514 memcpy(zbc->inBuff, zbc->headerBuffer, zbc->hPos); 3515 zbc->inPos = zbc->hPos; 3516 zbc->hPos = 0; 3517 zbc->stage = ZBUFFds_load; 3518 break; 3519 } 3520 zbc->stage = ZBUFFds_read; 3521 /* fall-through */ 3522 case ZBUFFds_read: 3523 { 3524 size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc); 3525 if (neededInSize==0) /* end of frame */ 3526 { 3527 zbc->stage = ZBUFFds_init; 3528 notDone = 0; 3529 break; 3530 } 3531 if ((size_t)(iend-ip) >= neededInSize) 3532 { 3533 /* directly decode from src */ 3534 size_t decodedSize = ZSTD_decompressContinue(zbc->zc, 3535 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart, 3536 ip, neededInSize); 3537 if (ZSTD_isError(decodedSize)) return decodedSize; 3538 ip += neededInSize; 3539 if (!decodedSize) break; /* this was just a header */ 3540 zbc->outEnd = zbc->outStart + decodedSize; 3541 zbc->stage = ZBUFFds_flush; 3542 break; 3543 } 3544 if (ip==iend) { notDone = 0; break; } /* no more input */ 3545 zbc->stage = ZBUFFds_load; 3546 } 3547 /* fall-through */ 3548 case ZBUFFds_load: 3549 { 3550 size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc); 3551 size_t toLoad = neededInSize - zbc->inPos; /* should always be <= remaining space within inBuff */ 3552 size_t loadedSize; 3553 if (toLoad > zbc->inBuffSize - zbc->inPos) return ERROR(corruption_detected); /* should never happen */ 3554 loadedSize = ZBUFF_limitCopy(zbc->inBuff + zbc->inPos, toLoad, ip, iend-ip); 3555 ip += loadedSize; 3556 zbc->inPos += loadedSize; 3557 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */ 3558 { 3559 size_t decodedSize = ZSTD_decompressContinue(zbc->zc, 3560 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart, 3561 zbc->inBuff, neededInSize); 3562 if (ZSTD_isError(decodedSize)) return decodedSize; 3563 zbc->inPos = 0; /* input is consumed */ 3564 if (!decodedSize) { zbc->stage = ZBUFFds_read; break; } /* this was just a header */ 3565 zbc->outEnd = zbc->outStart + decodedSize; 3566 zbc->stage = ZBUFFds_flush; 3567 /* ZBUFFds_flush follows */ 3568 } 3569 } 3570 /* fall-through */ 3571 case ZBUFFds_flush: 3572 { 3573 size_t toFlushSize = zbc->outEnd - zbc->outStart; 3574 size_t flushedSize = ZBUFF_limitCopy(op, oend-op, zbc->outBuff + zbc->outStart, toFlushSize); 3575 op += flushedSize; 3576 zbc->outStart += flushedSize; 3577 if (flushedSize == toFlushSize) 3578 { 3579 zbc->stage = ZBUFFds_read; 3580 if (zbc->outStart + BLOCKSIZE > zbc->outBuffSize) 3581 zbc->outStart = zbc->outEnd = 0; 3582 break; 3583 } 3584 /* cannot flush everything */ 3585 notDone = 0; 3586 break; 3587 } 3588 default: return ERROR(GENERIC); /* impossible */ 3589 } 3590 } 3591 3592 *srcSizePtr = ip-istart; 3593 *maxDstSizePtr = op-ostart; 3594 3595 { 3596 size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zbc->zc); 3597 if (nextSrcSizeHint > 3) nextSrcSizeHint+= 3; /* get the next block header while at it */ 3598 nextSrcSizeHint -= zbc->inPos; /* already loaded*/ 3599 return nextSrcSizeHint; 3600 } 3601 } 3602 3603 3604 /* ************************************* 3605 * Tool functions 3606 ***************************************/ 3607 unsigned ZBUFFv04_isError(size_t errorCode) { return ERR_isError(errorCode); } 3608 const char* ZBUFFv04_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); } 3609 3610 size_t ZBUFFv04_recommendedDInSize() { return BLOCKSIZE + 3; } 3611 size_t ZBUFFv04_recommendedDOutSize() { return BLOCKSIZE; } 3612 3613 3614 3615 /*- ========================================================================= -*/ 3616 3617 /* final wrapping stage */ 3618 3619 size_t ZSTDv04_decompressDCtx(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3620 { 3621 return ZSTD_decompress_usingDict(dctx, dst, maxDstSize, src, srcSize, NULL, 0); 3622 } 3623 3624 size_t ZSTDv04_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3625 { 3626 #if defined(ZSTD_HEAPMODE) && (ZSTD_HEAPMODE==1) 3627 size_t regenSize; 3628 ZSTD_DCtx* dctx = ZSTD_createDCtx(); 3629 if (dctx==NULL) return ERROR(memory_allocation); 3630 regenSize = ZSTDv04_decompressDCtx(dctx, dst, maxDstSize, src, srcSize); 3631 ZSTD_freeDCtx(dctx); 3632 return regenSize; 3633 #else 3634 ZSTD_DCtx dctx; 3635 return ZSTDv04_decompressDCtx(&dctx, dst, maxDstSize, src, srcSize); 3636 #endif 3637 } 3638 3639 size_t ZSTDv04_findFrameCompressedSize(const void* src, size_t srcSize) 3640 { 3641 return ZSTD_findFrameCompressedSize(src, srcSize); 3642 } 3643 3644 size_t ZSTDv04_resetDCtx(ZSTDv04_Dctx* dctx) { return ZSTD_resetDCtx(dctx); } 3645 3646 size_t ZSTDv04_nextSrcSizeToDecompress(ZSTDv04_Dctx* dctx) 3647 { 3648 return ZSTD_nextSrcSizeToDecompress(dctx); 3649 } 3650 3651 size_t ZSTDv04_decompressContinue(ZSTDv04_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3652 { 3653 return ZSTD_decompressContinue(dctx, dst, maxDstSize, src, srcSize); 3654 } 3655 3656 3657 3658 ZBUFFv04_DCtx* ZBUFFv04_createDCtx(void) { return ZBUFF_createDCtx(); } 3659 size_t ZBUFFv04_freeDCtx(ZBUFFv04_DCtx* dctx) { return ZBUFF_freeDCtx(dctx); } 3660 3661 size_t ZBUFFv04_decompressInit(ZBUFFv04_DCtx* dctx) { return ZBUFF_decompressInit(dctx); } 3662 size_t ZBUFFv04_decompressWithDictionary(ZBUFFv04_DCtx* dctx, const void* src, size_t srcSize) 3663 { return ZBUFF_decompressWithDictionary(dctx, src, srcSize); } 3664 3665 size_t ZBUFFv04_decompressContinue(ZBUFFv04_DCtx* dctx, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr) 3666 { 3667 DEBUGLOG(5, "ZBUFFv04_decompressContinue"); 3668 return ZBUFF_decompressContinue(dctx, dst, maxDstSizePtr, src, srcSizePtr); 3669 } 3670 3671 ZSTD_DCtx* ZSTDv04_createDCtx(void) { return ZSTD_createDCtx(); } 3672 size_t ZSTDv04_freeDCtx(ZSTD_DCtx* dctx) { return ZSTD_freeDCtx(dctx); } 3673 3674 size_t ZSTDv04_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize) 3675 { 3676 return ZSTD_getFrameParams(params, src, srcSize); 3677 } 3678