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