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