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