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 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2) 2373 2374 static const size_t ZSTD_blockHeaderSize = 3; 2375 static const size_t ZSTD_frameHeaderSize = 4; 2376 2377 2378 /* ******************************************************* 2379 * Memory operations 2380 **********************************************************/ 2381 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); } 2382 2383 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); } 2384 2385 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; } 2386 2387 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */ 2388 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length) 2389 { 2390 const BYTE* ip = (const BYTE*)src; 2391 BYTE* op = (BYTE*)dst; 2392 BYTE* const oend = op + length; 2393 do COPY8(op, ip) while (op < oend); 2394 } 2395 2396 2397 /* ************************************** 2398 * Local structures 2399 ****************************************/ 2400 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t; 2401 2402 typedef struct 2403 { 2404 blockType_t blockType; 2405 U32 origSize; 2406 } blockProperties_t; 2407 2408 typedef struct { 2409 void* buffer; 2410 U32* offsetStart; 2411 U32* offset; 2412 BYTE* offCodeStart; 2413 BYTE* offCode; 2414 BYTE* litStart; 2415 BYTE* lit; 2416 BYTE* litLengthStart; 2417 BYTE* litLength; 2418 BYTE* matchLengthStart; 2419 BYTE* matchLength; 2420 BYTE* dumpsStart; 2421 BYTE* dumps; 2422 } seqStore_t; 2423 2424 2425 /* ************************************* 2426 * Error Management 2427 ***************************************/ 2428 /*! ZSTD_isError 2429 * tells if a return value is an error code */ 2430 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); } 2431 2432 2433 2434 /* ************************************************************* 2435 * Decompression section 2436 ***************************************************************/ 2437 struct ZSTD_DCtx_s 2438 { 2439 U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)]; 2440 U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)]; 2441 U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)]; 2442 void* previousDstEnd; 2443 void* base; 2444 size_t expected; 2445 blockType_t bType; 2446 U32 phase; 2447 const BYTE* litPtr; 2448 size_t litSize; 2449 BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */]; 2450 }; /* typedef'd to ZSTD_Dctx within "zstd_static.h" */ 2451 2452 2453 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr) 2454 { 2455 const BYTE* const in = (const BYTE* const)src; 2456 BYTE headerFlags; 2457 U32 cSize; 2458 2459 if (srcSize < 3) return ERROR(srcSize_wrong); 2460 2461 headerFlags = *in; 2462 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16); 2463 2464 bpPtr->blockType = (blockType_t)(headerFlags >> 6); 2465 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0; 2466 2467 if (bpPtr->blockType == bt_end) return 0; 2468 if (bpPtr->blockType == bt_rle) return 1; 2469 return cSize; 2470 } 2471 2472 static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 2473 { 2474 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall); 2475 memcpy(dst, src, srcSize); 2476 return srcSize; 2477 } 2478 2479 2480 /** ZSTD_decompressLiterals 2481 @return : nb of bytes read from src, or an error code*/ 2482 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr, 2483 const void* src, size_t srcSize) 2484 { 2485 const BYTE* ip = (const BYTE*)src; 2486 2487 const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 2488 const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 2489 2490 if (litSize > *maxDstSizePtr) return ERROR(corruption_detected); 2491 if (litCSize + 5 > srcSize) return ERROR(corruption_detected); 2492 2493 if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected); 2494 2495 *maxDstSizePtr = litSize; 2496 return litCSize + 5; 2497 } 2498 2499 2500 /** ZSTD_decodeLiteralsBlock 2501 @return : nb of bytes read from src (< srcSize )*/ 2502 static size_t ZSTD_decodeLiteralsBlock(void* ctx, 2503 const void* src, size_t srcSize) 2504 { 2505 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx; 2506 const BYTE* const istart = (const BYTE* const)src; 2507 2508 /* any compressed block with literals segment must be at least this size */ 2509 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected); 2510 2511 switch(*istart & 3) 2512 { 2513 default: 2514 case 0: 2515 { 2516 size_t litSize = BLOCKSIZE; 2517 const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize); 2518 dctx->litPtr = dctx->litBuffer; 2519 dctx->litSize = litSize; 2520 memset(dctx->litBuffer + dctx->litSize, 0, 8); 2521 return readSize; /* works if it's an error too */ 2522 } 2523 case IS_RAW: 2524 { 2525 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 2526 if (litSize > srcSize-11) /* risk of reading too far with wildcopy */ 2527 { 2528 if (litSize > srcSize-3) return ERROR(corruption_detected); 2529 memcpy(dctx->litBuffer, istart, litSize); 2530 dctx->litPtr = dctx->litBuffer; 2531 dctx->litSize = litSize; 2532 memset(dctx->litBuffer + dctx->litSize, 0, 8); 2533 return litSize+3; 2534 } 2535 /* direct reference into compressed stream */ 2536 dctx->litPtr = istart+3; 2537 dctx->litSize = litSize; 2538 return litSize+3; 2539 } 2540 case IS_RLE: 2541 { 2542 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 2543 if (litSize > BLOCKSIZE) return ERROR(corruption_detected); 2544 memset(dctx->litBuffer, istart[3], litSize + 8); 2545 dctx->litPtr = dctx->litBuffer; 2546 dctx->litSize = litSize; 2547 return 4; 2548 } 2549 } 2550 } 2551 2552 2553 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr, 2554 FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb, 2555 const void* src, size_t srcSize) 2556 { 2557 const BYTE* const istart = (const BYTE* const)src; 2558 const BYTE* ip = istart; 2559 const BYTE* const iend = istart + srcSize; 2560 U32 LLtype, Offtype, MLtype; 2561 U32 LLlog, Offlog, MLlog; 2562 size_t dumpsLength; 2563 2564 /* check */ 2565 if (srcSize < 5) return ERROR(srcSize_wrong); 2566 2567 /* SeqHead */ 2568 *nbSeq = MEM_readLE16(ip); ip+=2; 2569 LLtype = *ip >> 6; 2570 Offtype = (*ip >> 4) & 3; 2571 MLtype = (*ip >> 2) & 3; 2572 if (*ip & 2) 2573 { 2574 dumpsLength = ip[2]; 2575 dumpsLength += ip[1] << 8; 2576 ip += 3; 2577 } 2578 else 2579 { 2580 dumpsLength = ip[1]; 2581 dumpsLength += (ip[0] & 1) << 8; 2582 ip += 2; 2583 } 2584 *dumpsPtr = ip; 2585 ip += dumpsLength; 2586 *dumpsLengthPtr = dumpsLength; 2587 2588 /* check */ 2589 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */ 2590 2591 /* sequences */ 2592 { 2593 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL and MaxOff */ 2594 size_t headerSize; 2595 2596 /* Build DTables */ 2597 switch(LLtype) 2598 { 2599 case bt_rle : 2600 LLlog = 0; 2601 FSE_buildDTable_rle(DTableLL, *ip++); break; 2602 case bt_raw : 2603 LLlog = LLbits; 2604 FSE_buildDTable_raw(DTableLL, LLbits); break; 2605 default : 2606 { U32 max = MaxLL; 2607 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip); 2608 if (FSE_isError(headerSize)) return ERROR(GENERIC); 2609 if (LLlog > LLFSELog) return ERROR(corruption_detected); 2610 ip += headerSize; 2611 FSE_buildDTable(DTableLL, norm, max, LLlog); 2612 } } 2613 2614 switch(Offtype) 2615 { 2616 case bt_rle : 2617 Offlog = 0; 2618 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 2619 FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */ 2620 break; 2621 case bt_raw : 2622 Offlog = Offbits; 2623 FSE_buildDTable_raw(DTableOffb, Offbits); break; 2624 default : 2625 { U32 max = MaxOff; 2626 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip); 2627 if (FSE_isError(headerSize)) return ERROR(GENERIC); 2628 if (Offlog > OffFSELog) return ERROR(corruption_detected); 2629 ip += headerSize; 2630 FSE_buildDTable(DTableOffb, norm, max, Offlog); 2631 } } 2632 2633 switch(MLtype) 2634 { 2635 case bt_rle : 2636 MLlog = 0; 2637 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 2638 FSE_buildDTable_rle(DTableML, *ip++); break; 2639 case bt_raw : 2640 MLlog = MLbits; 2641 FSE_buildDTable_raw(DTableML, MLbits); break; 2642 default : 2643 { U32 max = MaxML; 2644 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip); 2645 if (FSE_isError(headerSize)) return ERROR(GENERIC); 2646 if (MLlog > MLFSELog) return ERROR(corruption_detected); 2647 ip += headerSize; 2648 FSE_buildDTable(DTableML, norm, max, MLlog); 2649 } } } 2650 2651 return ip-istart; 2652 } 2653 2654 2655 typedef struct { 2656 size_t litLength; 2657 size_t offset; 2658 size_t matchLength; 2659 } seq_t; 2660 2661 typedef struct { 2662 BIT_DStream_t DStream; 2663 FSE_DState_t stateLL; 2664 FSE_DState_t stateOffb; 2665 FSE_DState_t stateML; 2666 size_t prevOffset; 2667 const BYTE* dumps; 2668 const BYTE* dumpsEnd; 2669 } seqState_t; 2670 2671 2672 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState) 2673 { 2674 size_t litLength; 2675 size_t prevOffset; 2676 size_t offset; 2677 size_t matchLength; 2678 const BYTE* dumps = seqState->dumps; 2679 const BYTE* const de = seqState->dumpsEnd; 2680 2681 /* Literal length */ 2682 litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream)); 2683 prevOffset = litLength ? seq->offset : seqState->prevOffset; 2684 seqState->prevOffset = seq->offset; 2685 if (litLength == MaxLL) 2686 { 2687 U32 add = *dumps++; 2688 if (add < 255) litLength += add; 2689 else 2690 { 2691 litLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */ 2692 dumps += 3; 2693 } 2694 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */ 2695 } 2696 2697 /* Offset */ 2698 { 2699 static const size_t offsetPrefix[MaxOff+1] = { /* note : size_t faster than U32 */ 2700 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256, 2701 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 2702 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 }; 2703 U32 offsetCode, nbBits; 2704 offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */ 2705 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream)); 2706 nbBits = offsetCode - 1; 2707 if (offsetCode==0) nbBits = 0; /* cmove */ 2708 offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits); 2709 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream)); 2710 if (offsetCode==0) offset = prevOffset; /* cmove */ 2711 } 2712 2713 /* MatchLength */ 2714 matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream)); 2715 if (matchLength == MaxML) 2716 { 2717 U32 add = *dumps++; 2718 if (add < 255) matchLength += add; 2719 else 2720 { 2721 matchLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */ 2722 dumps += 3; 2723 } 2724 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */ 2725 } 2726 matchLength += MINMATCH; 2727 2728 /* save result */ 2729 seq->litLength = litLength; 2730 seq->offset = offset; 2731 seq->matchLength = matchLength; 2732 seqState->dumps = dumps; 2733 } 2734 2735 2736 static size_t ZSTD_execSequence(BYTE* op, 2737 seq_t sequence, 2738 const BYTE** litPtr, const BYTE* const litLimit, 2739 BYTE* const base, BYTE* const oend) 2740 { 2741 static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */ 2742 static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11}; /* subtracted */ 2743 const BYTE* const ostart = op; 2744 BYTE* const oLitEnd = op + sequence.litLength; 2745 BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength; /* risk : address space overflow (32-bits) */ 2746 BYTE* const oend_8 = oend-8; 2747 const BYTE* const litEnd = *litPtr + sequence.litLength; 2748 2749 /* checks */ 2750 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */ 2751 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */ 2752 if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */ 2753 2754 /* copy Literals */ 2755 ZSTD_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */ 2756 op = oLitEnd; 2757 *litPtr = litEnd; /* update for next sequence */ 2758 2759 /* copy Match */ 2760 { 2761 const BYTE* match = op - sequence.offset; 2762 2763 /* check */ 2764 if (sequence.offset > (size_t)op) return ERROR(corruption_detected); /* address space overflow test (this test seems kept by clang optimizer) */ 2765 //if (match > op) return ERROR(corruption_detected); /* address space overflow test (is clang optimizer removing this test ?) */ 2766 if (match < base) return ERROR(corruption_detected); 2767 2768 /* close range match, overlap */ 2769 if (sequence.offset < 8) 2770 { 2771 const int dec64 = dec64table[sequence.offset]; 2772 op[0] = match[0]; 2773 op[1] = match[1]; 2774 op[2] = match[2]; 2775 op[3] = match[3]; 2776 match += dec32table[sequence.offset]; 2777 ZSTD_copy4(op+4, match); 2778 match -= dec64; 2779 } 2780 else 2781 { 2782 ZSTD_copy8(op, match); 2783 } 2784 op += 8; match += 8; 2785 2786 if (oMatchEnd > oend-(16-MINMATCH)) 2787 { 2788 if (op < oend_8) 2789 { 2790 ZSTD_wildcopy(op, match, oend_8 - op); 2791 match += oend_8 - op; 2792 op = oend_8; 2793 } 2794 while (op < oMatchEnd) *op++ = *match++; 2795 } 2796 else 2797 { 2798 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */ 2799 } 2800 } 2801 2802 return oMatchEnd - ostart; 2803 } 2804 2805 static size_t ZSTD_decompressSequences( 2806 void* ctx, 2807 void* dst, size_t maxDstSize, 2808 const void* seqStart, size_t seqSize) 2809 { 2810 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx; 2811 const BYTE* ip = (const BYTE*)seqStart; 2812 const BYTE* const iend = ip + seqSize; 2813 BYTE* const ostart = (BYTE* const)dst; 2814 BYTE* op = ostart; 2815 BYTE* const oend = ostart + maxDstSize; 2816 size_t errorCode, dumpsLength; 2817 const BYTE* litPtr = dctx->litPtr; 2818 const BYTE* const litEnd = litPtr + dctx->litSize; 2819 int nbSeq; 2820 const BYTE* dumps; 2821 U32* DTableLL = dctx->LLTable; 2822 U32* DTableML = dctx->MLTable; 2823 U32* DTableOffb = dctx->OffTable; 2824 BYTE* const base = (BYTE*) (dctx->base); 2825 2826 /* Build Decoding Tables */ 2827 errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength, 2828 DTableLL, DTableML, DTableOffb, 2829 ip, iend-ip); 2830 if (ZSTD_isError(errorCode)) return errorCode; 2831 ip += errorCode; 2832 2833 /* Regen sequences */ 2834 { 2835 seq_t sequence; 2836 seqState_t seqState; 2837 2838 memset(&sequence, 0, sizeof(sequence)); 2839 seqState.dumps = dumps; 2840 seqState.dumpsEnd = dumps + dumpsLength; 2841 seqState.prevOffset = sequence.offset = 4; 2842 errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip); 2843 if (ERR_isError(errorCode)) return ERROR(corruption_detected); 2844 FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL); 2845 FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb); 2846 FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML); 2847 2848 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; ) 2849 { 2850 size_t oneSeqSize; 2851 nbSeq--; 2852 ZSTD_decodeSequence(&sequence, &seqState); 2853 oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend); 2854 if (ZSTD_isError(oneSeqSize)) return oneSeqSize; 2855 op += oneSeqSize; 2856 } 2857 2858 /* check if reached exact end */ 2859 if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* requested too much : data is corrupted */ 2860 if (nbSeq<0) return ERROR(corruption_detected); /* requested too many sequences : data is corrupted */ 2861 2862 /* last literal segment */ 2863 { 2864 size_t lastLLSize = litEnd - litPtr; 2865 if (litPtr > litEnd) return ERROR(corruption_detected); 2866 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall); 2867 if (op != litPtr) memmove(op, litPtr, lastLLSize); 2868 op += lastLLSize; 2869 } 2870 } 2871 2872 return op-ostart; 2873 } 2874 2875 2876 static size_t ZSTD_decompressBlock( 2877 void* ctx, 2878 void* dst, size_t maxDstSize, 2879 const void* src, size_t srcSize) 2880 { 2881 /* blockType == blockCompressed */ 2882 const BYTE* ip = (const BYTE*)src; 2883 2884 /* Decode literals sub-block */ 2885 size_t litCSize = ZSTD_decodeLiteralsBlock(ctx, src, srcSize); 2886 if (ZSTD_isError(litCSize)) return litCSize; 2887 ip += litCSize; 2888 srcSize -= litCSize; 2889 2890 return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize); 2891 } 2892 2893 2894 static size_t ZSTD_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 2895 { 2896 const BYTE* ip = (const BYTE*)src; 2897 const BYTE* iend = ip + srcSize; 2898 BYTE* const ostart = (BYTE* const)dst; 2899 BYTE* op = ostart; 2900 BYTE* const oend = ostart + maxDstSize; 2901 size_t remainingSize = srcSize; 2902 U32 magicNumber; 2903 blockProperties_t blockProperties; 2904 2905 /* Frame Header */ 2906 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong); 2907 magicNumber = MEM_readLE32(src); 2908 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown); 2909 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize; 2910 2911 /* Loop on each block */ 2912 while (1) 2913 { 2914 size_t decodedSize=0; 2915 size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties); 2916 if (ZSTD_isError(cBlockSize)) return cBlockSize; 2917 2918 ip += ZSTD_blockHeaderSize; 2919 remainingSize -= ZSTD_blockHeaderSize; 2920 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); 2921 2922 switch(blockProperties.blockType) 2923 { 2924 case bt_compressed: 2925 decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize); 2926 break; 2927 case bt_raw : 2928 decodedSize = ZSTD_copyUncompressedBlock(op, oend-op, ip, cBlockSize); 2929 break; 2930 case bt_rle : 2931 return ERROR(GENERIC); /* not yet supported */ 2932 break; 2933 case bt_end : 2934 /* end of frame */ 2935 if (remainingSize) return ERROR(srcSize_wrong); 2936 break; 2937 default: 2938 return ERROR(GENERIC); /* impossible */ 2939 } 2940 if (cBlockSize == 0) break; /* bt_end */ 2941 2942 if (ZSTD_isError(decodedSize)) return decodedSize; 2943 op += decodedSize; 2944 ip += cBlockSize; 2945 remainingSize -= cBlockSize; 2946 } 2947 2948 return op-ostart; 2949 } 2950 2951 static size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 2952 { 2953 ZSTD_DCtx ctx; 2954 ctx.base = dst; 2955 return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize); 2956 } 2957 2958 /* ZSTD_errorFrameSizeInfoLegacy() : 2959 assumes `cSize` and `dBound` are _not_ NULL */ 2960 MEM_STATIC void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret) 2961 { 2962 *cSize = ret; 2963 *dBound = ZSTD_CONTENTSIZE_ERROR; 2964 } 2965 2966 void ZSTDv03_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound) 2967 { 2968 const BYTE* ip = (const BYTE*)src; 2969 size_t remainingSize = srcSize; 2970 size_t nbBlocks = 0; 2971 U32 magicNumber; 2972 blockProperties_t blockProperties; 2973 2974 /* Frame Header */ 2975 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) { 2976 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 2977 return; 2978 } 2979 magicNumber = MEM_readLE32(src); 2980 if (magicNumber != ZSTD_magicNumber) { 2981 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown)); 2982 return; 2983 } 2984 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize; 2985 2986 /* Loop on each block */ 2987 while (1) 2988 { 2989 size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties); 2990 if (ZSTD_isError(cBlockSize)) { 2991 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize); 2992 return; 2993 } 2994 2995 ip += ZSTD_blockHeaderSize; 2996 remainingSize -= ZSTD_blockHeaderSize; 2997 if (cBlockSize > remainingSize) { 2998 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 2999 return; 3000 } 3001 3002 if (cBlockSize == 0) break; /* bt_end */ 3003 3004 ip += cBlockSize; 3005 remainingSize -= cBlockSize; 3006 nbBlocks++; 3007 } 3008 3009 *cSize = ip - (const BYTE*)src; 3010 *dBound = nbBlocks * BLOCKSIZE; 3011 } 3012 3013 3014 /******************************* 3015 * Streaming Decompression API 3016 *******************************/ 3017 3018 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx) 3019 { 3020 dctx->expected = ZSTD_frameHeaderSize; 3021 dctx->phase = 0; 3022 dctx->previousDstEnd = NULL; 3023 dctx->base = NULL; 3024 return 0; 3025 } 3026 3027 static ZSTD_DCtx* ZSTD_createDCtx(void) 3028 { 3029 ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx)); 3030 if (dctx==NULL) return NULL; 3031 ZSTD_resetDCtx(dctx); 3032 return dctx; 3033 } 3034 3035 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx) 3036 { 3037 free(dctx); 3038 return 0; 3039 } 3040 3041 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx) 3042 { 3043 return dctx->expected; 3044 } 3045 3046 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3047 { 3048 /* Sanity check */ 3049 if (srcSize != ctx->expected) return ERROR(srcSize_wrong); 3050 if (dst != ctx->previousDstEnd) /* not contiguous */ 3051 ctx->base = dst; 3052 3053 /* Decompress : frame header */ 3054 if (ctx->phase == 0) 3055 { 3056 /* Check frame magic header */ 3057 U32 magicNumber = MEM_readLE32(src); 3058 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown); 3059 ctx->phase = 1; 3060 ctx->expected = ZSTD_blockHeaderSize; 3061 return 0; 3062 } 3063 3064 /* Decompress : block header */ 3065 if (ctx->phase == 1) 3066 { 3067 blockProperties_t bp; 3068 size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp); 3069 if (ZSTD_isError(blockSize)) return blockSize; 3070 if (bp.blockType == bt_end) 3071 { 3072 ctx->expected = 0; 3073 ctx->phase = 0; 3074 } 3075 else 3076 { 3077 ctx->expected = blockSize; 3078 ctx->bType = bp.blockType; 3079 ctx->phase = 2; 3080 } 3081 3082 return 0; 3083 } 3084 3085 /* Decompress : block content */ 3086 { 3087 size_t rSize; 3088 switch(ctx->bType) 3089 { 3090 case bt_compressed: 3091 rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize); 3092 break; 3093 case bt_raw : 3094 rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize); 3095 break; 3096 case bt_rle : 3097 return ERROR(GENERIC); /* not yet handled */ 3098 break; 3099 case bt_end : /* should never happen (filtered at phase 1) */ 3100 rSize = 0; 3101 break; 3102 default: 3103 return ERROR(GENERIC); 3104 } 3105 ctx->phase = 1; 3106 ctx->expected = ZSTD_blockHeaderSize; 3107 ctx->previousDstEnd = (void*)( ((char*)dst) + rSize); 3108 return rSize; 3109 } 3110 3111 } 3112 3113 3114 /* wrapper layer */ 3115 3116 unsigned ZSTDv03_isError(size_t code) 3117 { 3118 return ZSTD_isError(code); 3119 } 3120 3121 size_t ZSTDv03_decompress( void* dst, size_t maxOriginalSize, 3122 const void* src, size_t compressedSize) 3123 { 3124 return ZSTD_decompress(dst, maxOriginalSize, src, compressedSize); 3125 } 3126 3127 ZSTDv03_Dctx* ZSTDv03_createDCtx(void) 3128 { 3129 return (ZSTDv03_Dctx*)ZSTD_createDCtx(); 3130 } 3131 3132 size_t ZSTDv03_freeDCtx(ZSTDv03_Dctx* dctx) 3133 { 3134 return ZSTD_freeDCtx((ZSTD_DCtx*)dctx); 3135 } 3136 3137 size_t ZSTDv03_resetDCtx(ZSTDv03_Dctx* dctx) 3138 { 3139 return ZSTD_resetDCtx((ZSTD_DCtx*)dctx); 3140 } 3141 3142 size_t ZSTDv03_nextSrcSizeToDecompress(ZSTDv03_Dctx* dctx) 3143 { 3144 return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx*)dctx); 3145 } 3146 3147 size_t ZSTDv03_decompressContinue(ZSTDv03_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 3148 { 3149 return ZSTD_decompressContinue((ZSTD_DCtx*)dctx, dst, maxDstSize, src, srcSize); 3150 } 3151