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