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