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