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