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