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