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