1/* 2 * Copyright (c) Yann Collet, Facebook, Inc. 3 * All rights reserved. 4 * 5 * This source code is licensed under both the BSD-style license (found in the 6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found 7 * in the COPYING file in the root directory of this source tree). 8 * You may select, at your option, one of the above-listed licenses. 9 */ 10 11 12/*- Dependencies -*/ 13#include "zstd_v06.h" 14#include <stddef.h> /* size_t, ptrdiff_t */ 15#include <string.h> /* memcpy */ 16#include <stdlib.h> /* malloc, free, qsort */ 17#include "../common/error_private.h" 18 19 20 21/* ****************************************************************** 22 mem.h 23 low-level memory access routines 24 Copyright (C) 2013-2015, Yann Collet. 25 26 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 27 28 Redistribution and use in source and binary forms, with or without 29 modification, are permitted provided that the following conditions are 30 met: 31 32 * Redistributions of source code must retain the above copyright 33 notice, this list of conditions and the following disclaimer. 34 * Redistributions in binary form must reproduce the above 35 copyright notice, this list of conditions and the following disclaimer 36 in the documentation and/or other materials provided with the 37 distribution. 38 39 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 40 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 41 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 42 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 43 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 45 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 46 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 47 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 48 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 49 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 50 51 You can contact the author at : 52 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy 53 - Public forum : https://groups.google.com/forum/#!forum/lz4c 54****************************************************************** */ 55#ifndef MEM_H_MODULE 56#define MEM_H_MODULE 57 58#if defined (__cplusplus) 59extern "C" { 60#endif 61 62 63/*-**************************************** 64* Compiler specifics 65******************************************/ 66#if defined(_MSC_VER) /* Visual Studio */ 67# include <stdlib.h> /* _byteswap_ulong */ 68# include <intrin.h> /* _byteswap_* */ 69#endif 70#if defined(__GNUC__) 71# define MEM_STATIC static __attribute__((unused)) 72#elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 73# define MEM_STATIC static inline 74#elif defined(_MSC_VER) 75# define MEM_STATIC static __inline 76#else 77# define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */ 78#endif 79 80 81/*-************************************************************** 82* Basic Types 83*****************************************************************/ 84#if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) 85# if defined(_AIX) 86# include <inttypes.h> 87# else 88# include <stdint.h> /* intptr_t */ 89# endif 90 typedef uint8_t BYTE; 91 typedef uint16_t U16; 92 typedef int16_t S16; 93 typedef uint32_t U32; 94 typedef int32_t S32; 95 typedef uint64_t U64; 96 typedef int64_t S64; 97#else 98 typedef unsigned char BYTE; 99 typedef unsigned short U16; 100 typedef signed short S16; 101 typedef unsigned int U32; 102 typedef signed int S32; 103 typedef unsigned long long U64; 104 typedef signed long long S64; 105#endif 106 107 108/*-************************************************************** 109* Memory I/O 110*****************************************************************/ 111/* MEM_FORCE_MEMORY_ACCESS : 112 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable. 113 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal. 114 * The below switch allow to select different access method for improved performance. 115 * Method 0 (default) : use `memcpy()`. Safe and portable. 116 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable). 117 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`. 118 * Method 2 : direct access. This method is portable but violate C standard. 119 * It can generate buggy code on targets depending on alignment. 120 * In some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6) 121 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details. 122 * Prefer these methods in priority order (0 > 1 > 2) 123 */ 124#ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */ 125# if defined(__INTEL_COMPILER) || defined(__GNUC__) || defined(__ICCARM__) 126# define MEM_FORCE_MEMORY_ACCESS 1 127# endif 128#endif 129 130MEM_STATIC unsigned MEM_32bits(void) { return sizeof(size_t)==4; } 131MEM_STATIC unsigned MEM_64bits(void) { return sizeof(size_t)==8; } 132 133MEM_STATIC unsigned MEM_isLittleEndian(void) 134{ 135 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ 136 return one.c[0]; 137} 138 139#if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2) 140 141/* violates C standard, by lying on structure alignment. 142Only use if no other choice to achieve best performance on target platform */ 143MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; } 144MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; } 145MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; } 146 147MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; } 148 149#elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1) 150 151/* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ 152/* currently only defined for gcc and icc */ 153typedef union { U16 u16; U32 u32; U64 u64; size_t st; } __attribute__((packed)) unalign; 154 155MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; } 156MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } 157MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; } 158 159MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; } 160 161#else 162 163/* default method, safe and standard. 164 can sometimes prove slower */ 165 166MEM_STATIC U16 MEM_read16(const void* memPtr) 167{ 168 U16 val; memcpy(&val, memPtr, sizeof(val)); return val; 169} 170 171MEM_STATIC U32 MEM_read32(const void* memPtr) 172{ 173 U32 val; memcpy(&val, memPtr, sizeof(val)); return val; 174} 175 176MEM_STATIC U64 MEM_read64(const void* memPtr) 177{ 178 U64 val; memcpy(&val, memPtr, sizeof(val)); return val; 179} 180 181MEM_STATIC void MEM_write16(void* memPtr, U16 value) 182{ 183 memcpy(memPtr, &value, sizeof(value)); 184} 185 186 187#endif /* MEM_FORCE_MEMORY_ACCESS */ 188 189MEM_STATIC U32 MEM_swap32(U32 in) 190{ 191#if defined(_MSC_VER) /* Visual Studio */ 192 return _byteswap_ulong(in); 193#elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403) 194 return __builtin_bswap32(in); 195#else 196 return ((in << 24) & 0xff000000 ) | 197 ((in << 8) & 0x00ff0000 ) | 198 ((in >> 8) & 0x0000ff00 ) | 199 ((in >> 24) & 0x000000ff ); 200#endif 201} 202 203MEM_STATIC U64 MEM_swap64(U64 in) 204{ 205#if defined(_MSC_VER) /* Visual Studio */ 206 return _byteswap_uint64(in); 207#elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403) 208 return __builtin_bswap64(in); 209#else 210 return ((in << 56) & 0xff00000000000000ULL) | 211 ((in << 40) & 0x00ff000000000000ULL) | 212 ((in << 24) & 0x0000ff0000000000ULL) | 213 ((in << 8) & 0x000000ff00000000ULL) | 214 ((in >> 8) & 0x00000000ff000000ULL) | 215 ((in >> 24) & 0x0000000000ff0000ULL) | 216 ((in >> 40) & 0x000000000000ff00ULL) | 217 ((in >> 56) & 0x00000000000000ffULL); 218#endif 219} 220 221 222/*=== Little endian r/w ===*/ 223 224MEM_STATIC U16 MEM_readLE16(const void* memPtr) 225{ 226 if (MEM_isLittleEndian()) 227 return MEM_read16(memPtr); 228 else { 229 const BYTE* p = (const BYTE*)memPtr; 230 return (U16)(p[0] + (p[1]<<8)); 231 } 232} 233 234MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val) 235{ 236 if (MEM_isLittleEndian()) { 237 MEM_write16(memPtr, val); 238 } else { 239 BYTE* p = (BYTE*)memPtr; 240 p[0] = (BYTE)val; 241 p[1] = (BYTE)(val>>8); 242 } 243} 244 245MEM_STATIC U32 MEM_readLE32(const void* memPtr) 246{ 247 if (MEM_isLittleEndian()) 248 return MEM_read32(memPtr); 249 else 250 return MEM_swap32(MEM_read32(memPtr)); 251} 252 253 254MEM_STATIC U64 MEM_readLE64(const void* memPtr) 255{ 256 if (MEM_isLittleEndian()) 257 return MEM_read64(memPtr); 258 else 259 return MEM_swap64(MEM_read64(memPtr)); 260} 261 262 263MEM_STATIC size_t MEM_readLEST(const void* memPtr) 264{ 265 if (MEM_32bits()) 266 return (size_t)MEM_readLE32(memPtr); 267 else 268 return (size_t)MEM_readLE64(memPtr); 269} 270 271 272 273#if defined (__cplusplus) 274} 275#endif 276 277#endif /* MEM_H_MODULE */ 278 279/* 280 zstd - standard compression library 281 Header File for static linking only 282 Copyright (C) 2014-2016, Yann Collet. 283 284 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 285 286 Redistribution and use in source and binary forms, with or without 287 modification, are permitted provided that the following conditions are 288 met: 289 * Redistributions of source code must retain the above copyright 290 notice, this list of conditions and the following disclaimer. 291 * Redistributions in binary form must reproduce the above 292 copyright notice, this list of conditions and the following disclaimer 293 in the documentation and/or other materials provided with the 294 distribution. 295 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 296 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 297 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 298 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 299 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 300 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 301 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 302 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 303 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 304 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 305 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 306 307 You can contact the author at : 308 - zstd homepage : http://www.zstd.net 309*/ 310#ifndef ZSTDv06_STATIC_H 311#define ZSTDv06_STATIC_H 312 313/* The prototypes defined within this file are considered experimental. 314 * They should not be used in the context DLL as they may change in the future. 315 * Prefer static linking if you need them, to control breaking version changes issues. 316 */ 317 318#if defined (__cplusplus) 319extern "C" { 320#endif 321 322 323 324/*- Advanced Decompression functions -*/ 325 326/*! ZSTDv06_decompress_usingPreparedDCtx() : 327* Same as ZSTDv06_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded. 328* It avoids reloading the dictionary each time. 329* `preparedDCtx` must have been properly initialized using ZSTDv06_decompressBegin_usingDict(). 330* Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */ 331ZSTDLIBv06_API size_t ZSTDv06_decompress_usingPreparedDCtx( 332 ZSTDv06_DCtx* dctx, const ZSTDv06_DCtx* preparedDCtx, 333 void* dst, size_t dstCapacity, 334 const void* src, size_t srcSize); 335 336 337 338#define ZSTDv06_FRAMEHEADERSIZE_MAX 13 /* for static allocation */ 339static const size_t ZSTDv06_frameHeaderSize_min = 5; 340static const size_t ZSTDv06_frameHeaderSize_max = ZSTDv06_FRAMEHEADERSIZE_MAX; 341 342ZSTDLIBv06_API size_t ZSTDv06_decompressBegin(ZSTDv06_DCtx* dctx); 343 344/* 345 Streaming decompression, direct mode (bufferless) 346 347 A ZSTDv06_DCtx object is required to track streaming operations. 348 Use ZSTDv06_createDCtx() / ZSTDv06_freeDCtx() to manage it. 349 A ZSTDv06_DCtx object can be re-used multiple times. 350 351 First optional operation is to retrieve frame parameters, using ZSTDv06_getFrameParams(), which doesn't consume the input. 352 It can provide the minimum size of rolling buffer required to properly decompress data, 353 and optionally the final size of uncompressed content. 354 (Note : content size is an optional info that may not be present. 0 means : content size unknown) 355 Frame parameters are extracted from the beginning of compressed frame. 356 The amount of data to read is variable, from ZSTDv06_frameHeaderSize_min to ZSTDv06_frameHeaderSize_max (so if `srcSize` >= ZSTDv06_frameHeaderSize_max, it will always work) 357 If `srcSize` is too small for operation to succeed, function will return the minimum size it requires to produce a result. 358 Result : 0 when successful, it means the ZSTDv06_frameParams structure has been filled. 359 >0 : means there is not enough data into `src`. Provides the expected size to successfully decode header. 360 errorCode, which can be tested using ZSTDv06_isError() 361 362 Start decompression, with ZSTDv06_decompressBegin() or ZSTDv06_decompressBegin_usingDict(). 363 Alternatively, you can copy a prepared context, using ZSTDv06_copyDCtx(). 364 365 Then use ZSTDv06_nextSrcSizeToDecompress() and ZSTDv06_decompressContinue() alternatively. 366 ZSTDv06_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv06_decompressContinue(). 367 ZSTDv06_decompressContinue() requires this exact amount of bytes, or it will fail. 368 ZSTDv06_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog). 369 They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible. 370 371 @result of ZSTDv06_decompressContinue() is the number of bytes regenerated within 'dst' (necessarily <= dstCapacity) 372 It can be zero, which is not an error; it just means ZSTDv06_decompressContinue() has decoded some header. 373 374 A frame is fully decoded when ZSTDv06_nextSrcSizeToDecompress() returns zero. 375 Context can then be reset to start a new decompression. 376*/ 377 378 379/* ************************************** 380* Block functions 381****************************************/ 382/*! Block functions produce and decode raw zstd blocks, without frame metadata. 383 User will have to take in charge required information to regenerate data, such as compressed and content sizes. 384 385 A few rules to respect : 386 - Uncompressed block size must be <= ZSTDv06_BLOCKSIZE_MAX (128 KB) 387 - Compressing or decompressing requires a context structure 388 + Use ZSTDv06_createCCtx() and ZSTDv06_createDCtx() 389 - It is necessary to init context before starting 390 + compression : ZSTDv06_compressBegin() 391 + decompression : ZSTDv06_decompressBegin() 392 + variants _usingDict() are also allowed 393 + copyCCtx() and copyDCtx() work too 394 - When a block is considered not compressible enough, ZSTDv06_compressBlock() result will be zero. 395 In which case, nothing is produced into `dst`. 396 + User must test for such outcome and deal directly with uncompressed data 397 + ZSTDv06_decompressBlock() doesn't accept uncompressed data as input !! 398*/ 399 400#define ZSTDv06_BLOCKSIZE_MAX (128 * 1024) /* define, for static allocation */ 401ZSTDLIBv06_API size_t ZSTDv06_decompressBlock(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize); 402 403 404 405#if defined (__cplusplus) 406} 407#endif 408 409#endif /* ZSTDv06_STATIC_H */ 410/* 411 zstd_internal - common functions to include 412 Header File for include 413 Copyright (C) 2014-2016, Yann Collet. 414 415 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 416 417 Redistribution and use in source and binary forms, with or without 418 modification, are permitted provided that the following conditions are 419 met: 420 * Redistributions of source code must retain the above copyright 421 notice, this list of conditions and the following disclaimer. 422 * Redistributions in binary form must reproduce the above 423 copyright notice, this list of conditions and the following disclaimer 424 in the documentation and/or other materials provided with the 425 distribution. 426 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 427 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 428 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 429 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 430 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 431 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 432 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 433 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 434 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 435 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 436 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 437 438 You can contact the author at : 439 - zstd homepage : https://www.zstd.net 440*/ 441#ifndef ZSTDv06_CCOMMON_H_MODULE 442#define ZSTDv06_CCOMMON_H_MODULE 443 444 445/*-************************************* 446* Common macros 447***************************************/ 448#define MIN(a,b) ((a)<(b) ? (a) : (b)) 449#define MAX(a,b) ((a)>(b) ? (a) : (b)) 450 451 452/*-************************************* 453* Common constants 454***************************************/ 455#define ZSTDv06_DICT_MAGIC 0xEC30A436 456 457#define ZSTDv06_REP_NUM 3 458#define ZSTDv06_REP_INIT ZSTDv06_REP_NUM 459#define ZSTDv06_REP_MOVE (ZSTDv06_REP_NUM-1) 460 461#define KB *(1 <<10) 462#define MB *(1 <<20) 463#define GB *(1U<<30) 464 465#define BIT7 128 466#define BIT6 64 467#define BIT5 32 468#define BIT4 16 469#define BIT1 2 470#define BIT0 1 471 472#define ZSTDv06_WINDOWLOG_ABSOLUTEMIN 12 473static const size_t ZSTDv06_fcs_fieldSize[4] = { 0, 1, 2, 8 }; 474 475#define ZSTDv06_BLOCKHEADERSIZE 3 /* because C standard does not allow a static const value to be defined using another static const value .... :( */ 476static const size_t ZSTDv06_blockHeaderSize = ZSTDv06_BLOCKHEADERSIZE; 477typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t; 478 479#define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */ 480#define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */ 481 482#define HufLog 12 483 484#define IS_HUF 0 485#define IS_PCH 1 486#define IS_RAW 2 487#define IS_RLE 3 488 489#define LONGNBSEQ 0x7F00 490 491#define MINMATCH 3 492#define EQUAL_READ32 4 493#define REPCODE_STARTVALUE 1 494 495#define Litbits 8 496#define MaxLit ((1<<Litbits) - 1) 497#define MaxML 52 498#define MaxLL 35 499#define MaxOff 28 500#define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */ 501#define MLFSELog 9 502#define LLFSELog 9 503#define OffFSELog 8 504 505#define FSEv06_ENCODING_RAW 0 506#define FSEv06_ENCODING_RLE 1 507#define FSEv06_ENCODING_STATIC 2 508#define FSEv06_ENCODING_DYNAMIC 3 509 510#define ZSTD_CONTENTSIZE_ERROR (0ULL - 2) 511 512static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 513 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12, 514 13,14,15,16 }; 515static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 516 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1, 517 -1,-1,-1,-1 }; 518static const U32 LL_defaultNormLog = 6; 519 520static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 521 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 522 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11, 523 12,13,14,15,16 }; 524static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 525 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 526 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1, 527 -1,-1,-1,-1,-1 }; 528static const U32 ML_defaultNormLog = 6; 529 530static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 531 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 }; 532static const U32 OF_defaultNormLog = 5; 533 534 535/*-******************************************* 536* Shared functions to include for inlining 537*********************************************/ 538static void ZSTDv06_copy8(void* dst, const void* src) { memcpy(dst, src, 8); } 539#define COPY8(d,s) { ZSTDv06_copy8(d,s); d+=8; s+=8; } 540 541/*! ZSTDv06_wildcopy() : 542* custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */ 543#define WILDCOPY_OVERLENGTH 8 544MEM_STATIC void ZSTDv06_wildcopy(void* dst, const void* src, ptrdiff_t length) 545{ 546 const BYTE* ip = (const BYTE*)src; 547 BYTE* op = (BYTE*)dst; 548 BYTE* const oend = op + length; 549 do 550 COPY8(op, ip) 551 while (op < oend); 552} 553 554 555 556/*-******************************************* 557* Private interfaces 558*********************************************/ 559typedef struct { 560 U32 off; 561 U32 len; 562} ZSTDv06_match_t; 563 564typedef struct { 565 U32 price; 566 U32 off; 567 U32 mlen; 568 U32 litlen; 569 U32 rep[ZSTDv06_REP_INIT]; 570} ZSTDv06_optimal_t; 571 572typedef struct { U32 unused; } ZSTDv06_stats_t; 573 574typedef struct { 575 void* buffer; 576 U32* offsetStart; 577 U32* offset; 578 BYTE* offCodeStart; 579 BYTE* litStart; 580 BYTE* lit; 581 U16* litLengthStart; 582 U16* litLength; 583 BYTE* llCodeStart; 584 U16* matchLengthStart; 585 U16* matchLength; 586 BYTE* mlCodeStart; 587 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */ 588 U32 longLengthPos; 589 /* opt */ 590 ZSTDv06_optimal_t* priceTable; 591 ZSTDv06_match_t* matchTable; 592 U32* matchLengthFreq; 593 U32* litLengthFreq; 594 U32* litFreq; 595 U32* offCodeFreq; 596 U32 matchLengthSum; 597 U32 matchSum; 598 U32 litLengthSum; 599 U32 litSum; 600 U32 offCodeSum; 601 U32 log2matchLengthSum; 602 U32 log2matchSum; 603 U32 log2litLengthSum; 604 U32 log2litSum; 605 U32 log2offCodeSum; 606 U32 factor; 607 U32 cachedPrice; 608 U32 cachedLitLength; 609 const BYTE* cachedLiterals; 610 ZSTDv06_stats_t stats; 611} seqStore_t; 612 613void ZSTDv06_seqToCodes(const seqStore_t* seqStorePtr, size_t const nbSeq); 614 615 616#endif /* ZSTDv06_CCOMMON_H_MODULE */ 617/* ****************************************************************** 618 FSE : Finite State Entropy codec 619 Public Prototypes declaration 620 Copyright (C) 2013-2016, Yann Collet. 621 622 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 623 624 Redistribution and use in source and binary forms, with or without 625 modification, are permitted provided that the following conditions are 626 met: 627 628 * Redistributions of source code must retain the above copyright 629 notice, this list of conditions and the following disclaimer. 630 * Redistributions in binary form must reproduce the above 631 copyright notice, this list of conditions and the following disclaimer 632 in the documentation and/or other materials provided with the 633 distribution. 634 635 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 636 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 637 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 638 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 639 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 640 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 641 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 642 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 643 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 644 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 645 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 646 647 You can contact the author at : 648 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 649****************************************************************** */ 650#ifndef FSEv06_H 651#define FSEv06_H 652 653#if defined (__cplusplus) 654extern "C" { 655#endif 656 657 658 659/*-**************************************** 660* FSE simple functions 661******************************************/ 662/*! FSEv06_decompress(): 663 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize', 664 into already allocated destination buffer 'dst', of size 'dstCapacity'. 665 @return : size of regenerated data (<= maxDstSize), 666 or an error code, which can be tested using FSEv06_isError() . 667 668 ** Important ** : FSEv06_decompress() does not decompress non-compressible nor RLE data !!! 669 Why ? : making this distinction requires a header. 670 Header management is intentionally delegated to the user layer, which can better manage special cases. 671*/ 672size_t FSEv06_decompress(void* dst, size_t dstCapacity, 673 const void* cSrc, size_t cSrcSize); 674 675 676/*-***************************************** 677* Tool functions 678******************************************/ 679size_t FSEv06_compressBound(size_t size); /* maximum compressed size */ 680 681/* Error Management */ 682unsigned FSEv06_isError(size_t code); /* tells if a return value is an error code */ 683const char* FSEv06_getErrorName(size_t code); /* provides error code string (useful for debugging) */ 684 685 686 687/*-***************************************** 688* FSE detailed API 689******************************************/ 690/*! 691 692FSEv06_decompress() does the following: 6931. read normalized counters with readNCount() 6942. build decoding table 'DTable' from normalized counters 6953. decode the data stream using decoding table 'DTable' 696 697The following API allows targeting specific sub-functions for advanced tasks. 698For example, it's possible to compress several blocks using the same 'CTable', 699or to save and provide normalized distribution using external method. 700*/ 701 702 703/* *** DECOMPRESSION *** */ 704 705/*! FSEv06_readNCount(): 706 Read compactly saved 'normalizedCounter' from 'rBuffer'. 707 @return : size read from 'rBuffer', 708 or an errorCode, which can be tested using FSEv06_isError(). 709 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */ 710size_t FSEv06_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize); 711 712/*! Constructor and Destructor of FSEv06_DTable. 713 Note that its size depends on 'tableLog' */ 714typedef unsigned FSEv06_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */ 715FSEv06_DTable* FSEv06_createDTable(unsigned tableLog); 716void FSEv06_freeDTable(FSEv06_DTable* dt); 717 718/*! FSEv06_buildDTable(): 719 Builds 'dt', which must be already allocated, using FSEv06_createDTable(). 720 return : 0, or an errorCode, which can be tested using FSEv06_isError() */ 721size_t FSEv06_buildDTable (FSEv06_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog); 722 723/*! FSEv06_decompress_usingDTable(): 724 Decompress compressed source `cSrc` of size `cSrcSize` using `dt` 725 into `dst` which must be already allocated. 726 @return : size of regenerated data (necessarily <= `dstCapacity`), 727 or an errorCode, which can be tested using FSEv06_isError() */ 728size_t FSEv06_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv06_DTable* dt); 729 730/*! 731Tutorial : 732---------- 733(Note : these functions only decompress FSE-compressed blocks. 734 If block is uncompressed, use memcpy() instead 735 If block is a single repeated byte, use memset() instead ) 736 737The first step is to obtain the normalized frequencies of symbols. 738This can be performed by FSEv06_readNCount() if it was saved using FSEv06_writeNCount(). 739'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short. 740In practice, that means it's necessary to know 'maxSymbolValue' beforehand, 741or size the table to handle worst case situations (typically 256). 742FSEv06_readNCount() will provide 'tableLog' and 'maxSymbolValue'. 743The result of FSEv06_readNCount() is the number of bytes read from 'rBuffer'. 744Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that. 745If there is an error, the function will return an error code, which can be tested using FSEv06_isError(). 746 747The next step is to build the decompression tables 'FSEv06_DTable' from 'normalizedCounter'. 748This is performed by the function FSEv06_buildDTable(). 749The space required by 'FSEv06_DTable' must be already allocated using FSEv06_createDTable(). 750If there is an error, the function will return an error code, which can be tested using FSEv06_isError(). 751 752`FSEv06_DTable` can then be used to decompress `cSrc`, with FSEv06_decompress_usingDTable(). 753`cSrcSize` must be strictly correct, otherwise decompression will fail. 754FSEv06_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`). 755If there is an error, the function will return an error code, which can be tested using FSEv06_isError(). (ex: dst buffer too small) 756*/ 757 758 759#if defined (__cplusplus) 760} 761#endif 762 763#endif /* FSEv06_H */ 764/* ****************************************************************** 765 bitstream 766 Part of FSE library 767 header file (to include) 768 Copyright (C) 2013-2016, Yann Collet. 769 770 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 771 772 Redistribution and use in source and binary forms, with or without 773 modification, are permitted provided that the following conditions are 774 met: 775 776 * Redistributions of source code must retain the above copyright 777 notice, this list of conditions and the following disclaimer. 778 * Redistributions in binary form must reproduce the above 779 copyright notice, this list of conditions and the following disclaimer 780 in the documentation and/or other materials provided with the 781 distribution. 782 783 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 784 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 785 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 786 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 787 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 788 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 789 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 790 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 791 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 792 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 793 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 794 795 You can contact the author at : 796 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 797****************************************************************** */ 798#ifndef BITSTREAM_H_MODULE 799#define BITSTREAM_H_MODULE 800 801#if defined (__cplusplus) 802extern "C" { 803#endif 804 805 806/* 807* This API consists of small unitary functions, which must be inlined for best performance. 808* Since link-time-optimization is not available for all compilers, 809* these functions are defined into a .h to be included. 810*/ 811 812 813/*========================================= 814* Target specific 815=========================================*/ 816#if defined(__BMI__) && defined(__GNUC__) 817# include <immintrin.h> /* support for bextr (experimental) */ 818#endif 819 820 821 822/*-******************************************** 823* bitStream decoding API (read backward) 824**********************************************/ 825typedef struct 826{ 827 size_t bitContainer; 828 unsigned bitsConsumed; 829 const char* ptr; 830 const char* start; 831} BITv06_DStream_t; 832 833typedef enum { BITv06_DStream_unfinished = 0, 834 BITv06_DStream_endOfBuffer = 1, 835 BITv06_DStream_completed = 2, 836 BITv06_DStream_overflow = 3 } BITv06_DStream_status; /* result of BITv06_reloadDStream() */ 837 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */ 838 839MEM_STATIC size_t BITv06_initDStream(BITv06_DStream_t* bitD, const void* srcBuffer, size_t srcSize); 840MEM_STATIC size_t BITv06_readBits(BITv06_DStream_t* bitD, unsigned nbBits); 841MEM_STATIC BITv06_DStream_status BITv06_reloadDStream(BITv06_DStream_t* bitD); 842MEM_STATIC unsigned BITv06_endOfDStream(const BITv06_DStream_t* bitD); 843 844 845 846/*-**************************************** 847* unsafe API 848******************************************/ 849MEM_STATIC size_t BITv06_readBitsFast(BITv06_DStream_t* bitD, unsigned nbBits); 850/* faster, but works only if nbBits >= 1 */ 851 852 853 854/*-************************************************************** 855* Internal functions 856****************************************************************/ 857MEM_STATIC unsigned BITv06_highbit32 ( U32 val) 858{ 859# if defined(_MSC_VER) /* Visual */ 860 unsigned long r; 861 return _BitScanReverse(&r, val) ? (unsigned)r : 0; 862# elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */ 863 return __builtin_clz (val) ^ 31; 864# else /* Software version */ 865 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 }; 866 U32 v = val; 867 unsigned r; 868 v |= v >> 1; 869 v |= v >> 2; 870 v |= v >> 4; 871 v |= v >> 8; 872 v |= v >> 16; 873 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27]; 874 return r; 875# endif 876} 877 878 879 880/*-******************************************************** 881* bitStream decoding 882**********************************************************/ 883/*! BITv06_initDStream() : 884* Initialize a BITv06_DStream_t. 885* `bitD` : a pointer to an already allocated BITv06_DStream_t structure. 886* `srcSize` must be the *exact* size of the bitStream, in bytes. 887* @return : size of stream (== srcSize) or an errorCode if a problem is detected 888*/ 889MEM_STATIC size_t BITv06_initDStream(BITv06_DStream_t* bitD, const void* srcBuffer, size_t srcSize) 890{ 891 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); } 892 893 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */ 894 bitD->start = (const char*)srcBuffer; 895 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer); 896 bitD->bitContainer = MEM_readLEST(bitD->ptr); 897 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1]; 898 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ 899 bitD->bitsConsumed = 8 - BITv06_highbit32(lastByte); } 900 } else { 901 bitD->start = (const char*)srcBuffer; 902 bitD->ptr = bitD->start; 903 bitD->bitContainer = *(const BYTE*)(bitD->start); 904 switch(srcSize) 905 { 906 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);/* fall-through */ 907 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);/* fall-through */ 908 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);/* fall-through */ 909 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24; /* fall-through */ 910 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16; /* fall-through */ 911 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8; /* fall-through */ 912 default: break; 913 } 914 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1]; 915 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ 916 bitD->bitsConsumed = 8 - BITv06_highbit32(lastByte); } 917 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8; 918 } 919 920 return srcSize; 921} 922 923 924 MEM_STATIC size_t BITv06_lookBits(const BITv06_DStream_t* bitD, U32 nbBits) 925{ 926 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1; 927 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask); 928} 929 930/*! BITv06_lookBitsFast() : 931* unsafe version; only works only if nbBits >= 1 */ 932MEM_STATIC size_t BITv06_lookBitsFast(const BITv06_DStream_t* bitD, U32 nbBits) 933{ 934 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1; 935 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask); 936} 937 938MEM_STATIC void BITv06_skipBits(BITv06_DStream_t* bitD, U32 nbBits) 939{ 940 bitD->bitsConsumed += nbBits; 941} 942 943MEM_STATIC size_t BITv06_readBits(BITv06_DStream_t* bitD, U32 nbBits) 944{ 945 size_t const value = BITv06_lookBits(bitD, nbBits); 946 BITv06_skipBits(bitD, nbBits); 947 return value; 948} 949 950/*! BITv06_readBitsFast() : 951* unsafe version; only works only if nbBits >= 1 */ 952MEM_STATIC size_t BITv06_readBitsFast(BITv06_DStream_t* bitD, U32 nbBits) 953{ 954 size_t const value = BITv06_lookBitsFast(bitD, nbBits); 955 BITv06_skipBits(bitD, nbBits); 956 return value; 957} 958 959MEM_STATIC BITv06_DStream_status BITv06_reloadDStream(BITv06_DStream_t* bitD) 960{ 961 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */ 962 return BITv06_DStream_overflow; 963 964 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) { 965 bitD->ptr -= bitD->bitsConsumed >> 3; 966 bitD->bitsConsumed &= 7; 967 bitD->bitContainer = MEM_readLEST(bitD->ptr); 968 return BITv06_DStream_unfinished; 969 } 970 if (bitD->ptr == bitD->start) { 971 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv06_DStream_endOfBuffer; 972 return BITv06_DStream_completed; 973 } 974 { U32 nbBytes = bitD->bitsConsumed >> 3; 975 BITv06_DStream_status result = BITv06_DStream_unfinished; 976 if (bitD->ptr - nbBytes < bitD->start) { 977 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */ 978 result = BITv06_DStream_endOfBuffer; 979 } 980 bitD->ptr -= nbBytes; 981 bitD->bitsConsumed -= nbBytes*8; 982 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */ 983 return result; 984 } 985} 986 987/*! BITv06_endOfDStream() : 988* @return Tells if DStream has exactly reached its end (all bits consumed). 989*/ 990MEM_STATIC unsigned BITv06_endOfDStream(const BITv06_DStream_t* DStream) 991{ 992 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8)); 993} 994 995#if defined (__cplusplus) 996} 997#endif 998 999#endif /* BITSTREAM_H_MODULE */ 1000/* ****************************************************************** 1001 FSE : Finite State Entropy coder 1002 header file for static linking (only) 1003 Copyright (C) 2013-2015, Yann Collet 1004 1005 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1006 1007 Redistribution and use in source and binary forms, with or without 1008 modification, are permitted provided that the following conditions are 1009 met: 1010 1011 * Redistributions of source code must retain the above copyright 1012 notice, this list of conditions and the following disclaimer. 1013 * Redistributions in binary form must reproduce the above 1014 copyright notice, this list of conditions and the following disclaimer 1015 in the documentation and/or other materials provided with the 1016 distribution. 1017 1018 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1019 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1020 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1021 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1022 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1023 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1024 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1025 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1026 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1027 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1028 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1029 1030 You can contact the author at : 1031 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 1032 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1033****************************************************************** */ 1034#ifndef FSEv06_STATIC_H 1035#define FSEv06_STATIC_H 1036 1037#if defined (__cplusplus) 1038extern "C" { 1039#endif 1040 1041 1042/* ***************************************** 1043* Static allocation 1044*******************************************/ 1045/* FSE buffer bounds */ 1046#define FSEv06_NCOUNTBOUND 512 1047#define FSEv06_BLOCKBOUND(size) (size + (size>>7)) 1048#define FSEv06_COMPRESSBOUND(size) (FSEv06_NCOUNTBOUND + FSEv06_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ 1049 1050/* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */ 1051#define FSEv06_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog)) 1052 1053 1054/* ***************************************** 1055* FSE advanced API 1056*******************************************/ 1057size_t FSEv06_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize); 1058/* same as FSEv06_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */ 1059 1060size_t FSEv06_buildDTable_raw (FSEv06_DTable* dt, unsigned nbBits); 1061/* build a fake FSEv06_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */ 1062 1063size_t FSEv06_buildDTable_rle (FSEv06_DTable* dt, unsigned char symbolValue); 1064/* build a fake FSEv06_DTable, designed to always generate the same symbolValue */ 1065 1066 1067/* ***************************************** 1068* FSE symbol decompression API 1069*******************************************/ 1070typedef struct 1071{ 1072 size_t state; 1073 const void* table; /* precise table may vary, depending on U16 */ 1074} FSEv06_DState_t; 1075 1076 1077static void FSEv06_initDState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD, const FSEv06_DTable* dt); 1078 1079static unsigned char FSEv06_decodeSymbol(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD); 1080 1081 1082/* ***************************************** 1083* FSE unsafe API 1084*******************************************/ 1085static unsigned char FSEv06_decodeSymbolFast(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD); 1086/* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */ 1087 1088 1089/* ***************************************** 1090* Implementation of inlined functions 1091*******************************************/ 1092 1093 1094/* ====== Decompression ====== */ 1095 1096typedef struct { 1097 U16 tableLog; 1098 U16 fastMode; 1099} FSEv06_DTableHeader; /* sizeof U32 */ 1100 1101typedef struct 1102{ 1103 unsigned short newState; 1104 unsigned char symbol; 1105 unsigned char nbBits; 1106} FSEv06_decode_t; /* size == U32 */ 1107 1108MEM_STATIC void FSEv06_initDState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD, const FSEv06_DTable* dt) 1109{ 1110 const void* ptr = dt; 1111 const FSEv06_DTableHeader* const DTableH = (const FSEv06_DTableHeader*)ptr; 1112 DStatePtr->state = BITv06_readBits(bitD, DTableH->tableLog); 1113 BITv06_reloadDStream(bitD); 1114 DStatePtr->table = dt + 1; 1115} 1116 1117MEM_STATIC BYTE FSEv06_peekSymbol(const FSEv06_DState_t* DStatePtr) 1118{ 1119 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state]; 1120 return DInfo.symbol; 1121} 1122 1123MEM_STATIC void FSEv06_updateState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD) 1124{ 1125 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state]; 1126 U32 const nbBits = DInfo.nbBits; 1127 size_t const lowBits = BITv06_readBits(bitD, nbBits); 1128 DStatePtr->state = DInfo.newState + lowBits; 1129} 1130 1131MEM_STATIC BYTE FSEv06_decodeSymbol(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD) 1132{ 1133 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state]; 1134 U32 const nbBits = DInfo.nbBits; 1135 BYTE const symbol = DInfo.symbol; 1136 size_t const lowBits = BITv06_readBits(bitD, nbBits); 1137 1138 DStatePtr->state = DInfo.newState + lowBits; 1139 return symbol; 1140} 1141 1142/*! FSEv06_decodeSymbolFast() : 1143 unsafe, only works if no symbol has a probability > 50% */ 1144MEM_STATIC BYTE FSEv06_decodeSymbolFast(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD) 1145{ 1146 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state]; 1147 U32 const nbBits = DInfo.nbBits; 1148 BYTE const symbol = DInfo.symbol; 1149 size_t const lowBits = BITv06_readBitsFast(bitD, nbBits); 1150 1151 DStatePtr->state = DInfo.newState + lowBits; 1152 return symbol; 1153} 1154 1155 1156 1157#ifndef FSEv06_COMMONDEFS_ONLY 1158 1159/* ************************************************************** 1160* Tuning parameters 1161****************************************************************/ 1162/*!MEMORY_USAGE : 1163* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) 1164* Increasing memory usage improves compression ratio 1165* Reduced memory usage can improve speed, due to cache effect 1166* Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */ 1167#define FSEv06_MAX_MEMORY_USAGE 14 1168#define FSEv06_DEFAULT_MEMORY_USAGE 13 1169 1170/*!FSEv06_MAX_SYMBOL_VALUE : 1171* Maximum symbol value authorized. 1172* Required for proper stack allocation */ 1173#define FSEv06_MAX_SYMBOL_VALUE 255 1174 1175 1176/* ************************************************************** 1177* template functions type & suffix 1178****************************************************************/ 1179#define FSEv06_FUNCTION_TYPE BYTE 1180#define FSEv06_FUNCTION_EXTENSION 1181#define FSEv06_DECODE_TYPE FSEv06_decode_t 1182 1183 1184#endif /* !FSEv06_COMMONDEFS_ONLY */ 1185 1186 1187/* *************************************************************** 1188* Constants 1189*****************************************************************/ 1190#define FSEv06_MAX_TABLELOG (FSEv06_MAX_MEMORY_USAGE-2) 1191#define FSEv06_MAX_TABLESIZE (1U<<FSEv06_MAX_TABLELOG) 1192#define FSEv06_MAXTABLESIZE_MASK (FSEv06_MAX_TABLESIZE-1) 1193#define FSEv06_DEFAULT_TABLELOG (FSEv06_DEFAULT_MEMORY_USAGE-2) 1194#define FSEv06_MIN_TABLELOG 5 1195 1196#define FSEv06_TABLELOG_ABSOLUTE_MAX 15 1197#if FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX 1198#error "FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX is not supported" 1199#endif 1200 1201#define FSEv06_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3) 1202 1203 1204#if defined (__cplusplus) 1205} 1206#endif 1207 1208#endif /* FSEv06_STATIC_H */ 1209/* 1210 Common functions of New Generation Entropy library 1211 Copyright (C) 2016, Yann Collet. 1212 1213 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1214 1215 Redistribution and use in source and binary forms, with or without 1216 modification, are permitted provided that the following conditions are 1217 met: 1218 1219 * Redistributions of source code must retain the above copyright 1220 notice, this list of conditions and the following disclaimer. 1221 * Redistributions in binary form must reproduce the above 1222 copyright notice, this list of conditions and the following disclaimer 1223 in the documentation and/or other materials provided with the 1224 distribution. 1225 1226 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1227 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1228 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1229 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1230 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1231 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1232 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1233 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1234 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1235 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1236 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1237 1238 You can contact the author at : 1239 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy 1240 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1241*************************************************************************** */ 1242 1243 1244/*-**************************************** 1245* FSE Error Management 1246******************************************/ 1247unsigned FSEv06_isError(size_t code) { return ERR_isError(code); } 1248 1249const char* FSEv06_getErrorName(size_t code) { return ERR_getErrorName(code); } 1250 1251 1252/* ************************************************************** 1253* HUF Error Management 1254****************************************************************/ 1255static unsigned HUFv06_isError(size_t code) { return ERR_isError(code); } 1256 1257 1258/*-************************************************************** 1259* FSE NCount encoding-decoding 1260****************************************************************/ 1261static short FSEv06_abs(short a) { return a<0 ? -a : a; } 1262 1263size_t FSEv06_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr, 1264 const void* headerBuffer, size_t hbSize) 1265{ 1266 const BYTE* const istart = (const BYTE*) headerBuffer; 1267 const BYTE* const iend = istart + hbSize; 1268 const BYTE* ip = istart; 1269 int nbBits; 1270 int remaining; 1271 int threshold; 1272 U32 bitStream; 1273 int bitCount; 1274 unsigned charnum = 0; 1275 int previous0 = 0; 1276 1277 if (hbSize < 4) return ERROR(srcSize_wrong); 1278 bitStream = MEM_readLE32(ip); 1279 nbBits = (bitStream & 0xF) + FSEv06_MIN_TABLELOG; /* extract tableLog */ 1280 if (nbBits > FSEv06_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge); 1281 bitStream >>= 4; 1282 bitCount = 4; 1283 *tableLogPtr = nbBits; 1284 remaining = (1<<nbBits)+1; 1285 threshold = 1<<nbBits; 1286 nbBits++; 1287 1288 while ((remaining>1) && (charnum<=*maxSVPtr)) { 1289 if (previous0) { 1290 unsigned n0 = charnum; 1291 while ((bitStream & 0xFFFF) == 0xFFFF) { 1292 n0+=24; 1293 if (ip < iend-5) { 1294 ip+=2; 1295 bitStream = MEM_readLE32(ip) >> bitCount; 1296 } else { 1297 bitStream >>= 16; 1298 bitCount+=16; 1299 } } 1300 while ((bitStream & 3) == 3) { 1301 n0+=3; 1302 bitStream>>=2; 1303 bitCount+=2; 1304 } 1305 n0 += bitStream & 3; 1306 bitCount += 2; 1307 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall); 1308 while (charnum < n0) normalizedCounter[charnum++] = 0; 1309 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { 1310 ip += bitCount>>3; 1311 bitCount &= 7; 1312 bitStream = MEM_readLE32(ip) >> bitCount; 1313 } 1314 else 1315 bitStream >>= 2; 1316 } 1317 { short const max = (short)((2*threshold-1)-remaining); 1318 short count; 1319 1320 if ((bitStream & (threshold-1)) < (U32)max) { 1321 count = (short)(bitStream & (threshold-1)); 1322 bitCount += nbBits-1; 1323 } else { 1324 count = (short)(bitStream & (2*threshold-1)); 1325 if (count >= threshold) count -= max; 1326 bitCount += nbBits; 1327 } 1328 1329 count--; /* extra accuracy */ 1330 remaining -= FSEv06_abs(count); 1331 normalizedCounter[charnum++] = count; 1332 previous0 = !count; 1333 while (remaining < threshold) { 1334 nbBits--; 1335 threshold >>= 1; 1336 } 1337 1338 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { 1339 ip += bitCount>>3; 1340 bitCount &= 7; 1341 } else { 1342 bitCount -= (int)(8 * (iend - 4 - ip)); 1343 ip = iend - 4; 1344 } 1345 bitStream = MEM_readLE32(ip) >> (bitCount & 31); 1346 } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */ 1347 if (remaining != 1) return ERROR(GENERIC); 1348 *maxSVPtr = charnum-1; 1349 1350 ip += (bitCount+7)>>3; 1351 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong); 1352 return ip-istart; 1353} 1354/* ****************************************************************** 1355 FSE : Finite State Entropy decoder 1356 Copyright (C) 2013-2015, Yann Collet. 1357 1358 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1359 1360 Redistribution and use in source and binary forms, with or without 1361 modification, are permitted provided that the following conditions are 1362 met: 1363 1364 * Redistributions of source code must retain the above copyright 1365 notice, this list of conditions and the following disclaimer. 1366 * Redistributions in binary form must reproduce the above 1367 copyright notice, this list of conditions and the following disclaimer 1368 in the documentation and/or other materials provided with the 1369 distribution. 1370 1371 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1372 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1373 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1374 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1375 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1376 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1377 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1378 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1379 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1380 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1381 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1382 1383 You can contact the author at : 1384 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy 1385 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1386****************************************************************** */ 1387 1388 1389/* ************************************************************** 1390* Compiler specifics 1391****************************************************************/ 1392#ifdef _MSC_VER /* Visual Studio */ 1393# define FORCE_INLINE static __forceinline 1394# include <intrin.h> /* For Visual 2005 */ 1395# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 1396# pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */ 1397#else 1398# if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 1399# ifdef __GNUC__ 1400# define FORCE_INLINE static inline __attribute__((always_inline)) 1401# else 1402# define FORCE_INLINE static inline 1403# endif 1404# else 1405# define FORCE_INLINE static 1406# endif /* __STDC_VERSION__ */ 1407#endif 1408 1409 1410/* ************************************************************** 1411* Error Management 1412****************************************************************/ 1413#define FSEv06_isError ERR_isError 1414#define FSEv06_STATIC_ASSERT(c) { enum { FSEv06_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 1415 1416 1417/* ************************************************************** 1418* Complex types 1419****************************************************************/ 1420typedef U32 DTable_max_t[FSEv06_DTABLE_SIZE_U32(FSEv06_MAX_TABLELOG)]; 1421 1422 1423/* ************************************************************** 1424* Templates 1425****************************************************************/ 1426/* 1427 designed to be included 1428 for type-specific functions (template emulation in C) 1429 Objective is to write these functions only once, for improved maintenance 1430*/ 1431 1432/* safety checks */ 1433#ifndef FSEv06_FUNCTION_EXTENSION 1434# error "FSEv06_FUNCTION_EXTENSION must be defined" 1435#endif 1436#ifndef FSEv06_FUNCTION_TYPE 1437# error "FSEv06_FUNCTION_TYPE must be defined" 1438#endif 1439 1440/* Function names */ 1441#define FSEv06_CAT(X,Y) X##Y 1442#define FSEv06_FUNCTION_NAME(X,Y) FSEv06_CAT(X,Y) 1443#define FSEv06_TYPE_NAME(X,Y) FSEv06_CAT(X,Y) 1444 1445 1446/* Function templates */ 1447FSEv06_DTable* FSEv06_createDTable (unsigned tableLog) 1448{ 1449 if (tableLog > FSEv06_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv06_TABLELOG_ABSOLUTE_MAX; 1450 return (FSEv06_DTable*)malloc( FSEv06_DTABLE_SIZE_U32(tableLog) * sizeof (U32) ); 1451} 1452 1453void FSEv06_freeDTable (FSEv06_DTable* dt) 1454{ 1455 free(dt); 1456} 1457 1458size_t FSEv06_buildDTable(FSEv06_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) 1459{ 1460 void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */ 1461 FSEv06_DECODE_TYPE* const tableDecode = (FSEv06_DECODE_TYPE*) (tdPtr); 1462 U16 symbolNext[FSEv06_MAX_SYMBOL_VALUE+1]; 1463 1464 U32 const maxSV1 = maxSymbolValue + 1; 1465 U32 const tableSize = 1 << tableLog; 1466 U32 highThreshold = tableSize-1; 1467 1468 /* Sanity Checks */ 1469 if (maxSymbolValue > FSEv06_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge); 1470 if (tableLog > FSEv06_MAX_TABLELOG) return ERROR(tableLog_tooLarge); 1471 1472 /* Init, lay down lowprob symbols */ 1473 { FSEv06_DTableHeader DTableH; 1474 DTableH.tableLog = (U16)tableLog; 1475 DTableH.fastMode = 1; 1476 { S16 const largeLimit= (S16)(1 << (tableLog-1)); 1477 U32 s; 1478 for (s=0; s<maxSV1; s++) { 1479 if (normalizedCounter[s]==-1) { 1480 tableDecode[highThreshold--].symbol = (FSEv06_FUNCTION_TYPE)s; 1481 symbolNext[s] = 1; 1482 } else { 1483 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0; 1484 symbolNext[s] = normalizedCounter[s]; 1485 } } } 1486 memcpy(dt, &DTableH, sizeof(DTableH)); 1487 } 1488 1489 /* Spread symbols */ 1490 { U32 const tableMask = tableSize-1; 1491 U32 const step = FSEv06_TABLESTEP(tableSize); 1492 U32 s, position = 0; 1493 for (s=0; s<maxSV1; s++) { 1494 int i; 1495 for (i=0; i<normalizedCounter[s]; i++) { 1496 tableDecode[position].symbol = (FSEv06_FUNCTION_TYPE)s; 1497 position = (position + step) & tableMask; 1498 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */ 1499 } } 1500 1501 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ 1502 } 1503 1504 /* Build Decoding table */ 1505 { U32 u; 1506 for (u=0; u<tableSize; u++) { 1507 FSEv06_FUNCTION_TYPE const symbol = (FSEv06_FUNCTION_TYPE)(tableDecode[u].symbol); 1508 U16 nextState = symbolNext[symbol]++; 1509 tableDecode[u].nbBits = (BYTE) (tableLog - BITv06_highbit32 ((U32)nextState) ); 1510 tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize); 1511 } } 1512 1513 return 0; 1514} 1515 1516 1517 1518#ifndef FSEv06_COMMONDEFS_ONLY 1519 1520/*-******************************************************* 1521* Decompression (Byte symbols) 1522*********************************************************/ 1523size_t FSEv06_buildDTable_rle (FSEv06_DTable* dt, BYTE symbolValue) 1524{ 1525 void* ptr = dt; 1526 FSEv06_DTableHeader* const DTableH = (FSEv06_DTableHeader*)ptr; 1527 void* dPtr = dt + 1; 1528 FSEv06_decode_t* const cell = (FSEv06_decode_t*)dPtr; 1529 1530 DTableH->tableLog = 0; 1531 DTableH->fastMode = 0; 1532 1533 cell->newState = 0; 1534 cell->symbol = symbolValue; 1535 cell->nbBits = 0; 1536 1537 return 0; 1538} 1539 1540 1541size_t FSEv06_buildDTable_raw (FSEv06_DTable* dt, unsigned nbBits) 1542{ 1543 void* ptr = dt; 1544 FSEv06_DTableHeader* const DTableH = (FSEv06_DTableHeader*)ptr; 1545 void* dPtr = dt + 1; 1546 FSEv06_decode_t* const dinfo = (FSEv06_decode_t*)dPtr; 1547 const unsigned tableSize = 1 << nbBits; 1548 const unsigned tableMask = tableSize - 1; 1549 const unsigned maxSV1 = tableMask+1; 1550 unsigned s; 1551 1552 /* Sanity checks */ 1553 if (nbBits < 1) return ERROR(GENERIC); /* min size */ 1554 1555 /* Build Decoding Table */ 1556 DTableH->tableLog = (U16)nbBits; 1557 DTableH->fastMode = 1; 1558 for (s=0; s<maxSV1; s++) { 1559 dinfo[s].newState = 0; 1560 dinfo[s].symbol = (BYTE)s; 1561 dinfo[s].nbBits = (BYTE)nbBits; 1562 } 1563 1564 return 0; 1565} 1566 1567FORCE_INLINE size_t FSEv06_decompress_usingDTable_generic( 1568 void* dst, size_t maxDstSize, 1569 const void* cSrc, size_t cSrcSize, 1570 const FSEv06_DTable* dt, const unsigned fast) 1571{ 1572 BYTE* const ostart = (BYTE*) dst; 1573 BYTE* op = ostart; 1574 BYTE* const omax = op + maxDstSize; 1575 BYTE* const olimit = omax-3; 1576 1577 BITv06_DStream_t bitD; 1578 FSEv06_DState_t state1; 1579 FSEv06_DState_t state2; 1580 1581 /* Init */ 1582 { size_t const errorCode = BITv06_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */ 1583 if (FSEv06_isError(errorCode)) return errorCode; } 1584 1585 FSEv06_initDState(&state1, &bitD, dt); 1586 FSEv06_initDState(&state2, &bitD, dt); 1587 1588#define FSEv06_GETSYMBOL(statePtr) fast ? FSEv06_decodeSymbolFast(statePtr, &bitD) : FSEv06_decodeSymbol(statePtr, &bitD) 1589 1590 /* 4 symbols per loop */ 1591 for ( ; (BITv06_reloadDStream(&bitD)==BITv06_DStream_unfinished) && (op<olimit) ; op+=4) { 1592 op[0] = FSEv06_GETSYMBOL(&state1); 1593 1594 if (FSEv06_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1595 BITv06_reloadDStream(&bitD); 1596 1597 op[1] = FSEv06_GETSYMBOL(&state2); 1598 1599 if (FSEv06_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1600 { if (BITv06_reloadDStream(&bitD) > BITv06_DStream_unfinished) { op+=2; break; } } 1601 1602 op[2] = FSEv06_GETSYMBOL(&state1); 1603 1604 if (FSEv06_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 1605 BITv06_reloadDStream(&bitD); 1606 1607 op[3] = FSEv06_GETSYMBOL(&state2); 1608 } 1609 1610 /* tail */ 1611 /* note : BITv06_reloadDStream(&bitD) >= FSEv06_DStream_partiallyFilled; Ends at exactly BITv06_DStream_completed */ 1612 while (1) { 1613 if (op>(omax-2)) return ERROR(dstSize_tooSmall); 1614 1615 *op++ = FSEv06_GETSYMBOL(&state1); 1616 1617 if (BITv06_reloadDStream(&bitD)==BITv06_DStream_overflow) { 1618 *op++ = FSEv06_GETSYMBOL(&state2); 1619 break; 1620 } 1621 1622 if (op>(omax-2)) return ERROR(dstSize_tooSmall); 1623 1624 *op++ = FSEv06_GETSYMBOL(&state2); 1625 1626 if (BITv06_reloadDStream(&bitD)==BITv06_DStream_overflow) { 1627 *op++ = FSEv06_GETSYMBOL(&state1); 1628 break; 1629 } } 1630 1631 return op-ostart; 1632} 1633 1634 1635size_t FSEv06_decompress_usingDTable(void* dst, size_t originalSize, 1636 const void* cSrc, size_t cSrcSize, 1637 const FSEv06_DTable* dt) 1638{ 1639 const void* ptr = dt; 1640 const FSEv06_DTableHeader* DTableH = (const FSEv06_DTableHeader*)ptr; 1641 const U32 fastMode = DTableH->fastMode; 1642 1643 /* select fast mode (static) */ 1644 if (fastMode) return FSEv06_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1); 1645 return FSEv06_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0); 1646} 1647 1648 1649size_t FSEv06_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize) 1650{ 1651 const BYTE* const istart = (const BYTE*)cSrc; 1652 const BYTE* ip = istart; 1653 short counting[FSEv06_MAX_SYMBOL_VALUE+1]; 1654 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */ 1655 unsigned tableLog; 1656 unsigned maxSymbolValue = FSEv06_MAX_SYMBOL_VALUE; 1657 1658 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */ 1659 1660 /* normal FSE decoding mode */ 1661 { size_t const NCountLength = FSEv06_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize); 1662 if (FSEv06_isError(NCountLength)) return NCountLength; 1663 if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */ 1664 ip += NCountLength; 1665 cSrcSize -= NCountLength; 1666 } 1667 1668 { size_t const errorCode = FSEv06_buildDTable (dt, counting, maxSymbolValue, tableLog); 1669 if (FSEv06_isError(errorCode)) return errorCode; } 1670 1671 return FSEv06_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); /* always return, even if it is an error code */ 1672} 1673 1674 1675 1676#endif /* FSEv06_COMMONDEFS_ONLY */ 1677/* ****************************************************************** 1678 Huffman coder, part of New Generation Entropy library 1679 header file 1680 Copyright (C) 2013-2016, Yann Collet. 1681 1682 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1683 1684 Redistribution and use in source and binary forms, with or without 1685 modification, are permitted provided that the following conditions are 1686 met: 1687 1688 * Redistributions of source code must retain the above copyright 1689 notice, this list of conditions and the following disclaimer. 1690 * Redistributions in binary form must reproduce the above 1691 copyright notice, this list of conditions and the following disclaimer 1692 in the documentation and/or other materials provided with the 1693 distribution. 1694 1695 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1696 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1697 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1698 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1699 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1700 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1701 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1702 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1703 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1704 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1705 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1706 1707 You can contact the author at : 1708 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 1709****************************************************************** */ 1710#ifndef HUFv06_H 1711#define HUFv06_H 1712 1713#if defined (__cplusplus) 1714extern "C" { 1715#endif 1716 1717 1718/* **************************************** 1719* HUF simple functions 1720******************************************/ 1721size_t HUFv06_decompress(void* dst, size_t dstSize, 1722 const void* cSrc, size_t cSrcSize); 1723/* 1724HUFv06_decompress() : 1725 Decompress HUF data from buffer 'cSrc', of size 'cSrcSize', 1726 into already allocated destination buffer 'dst', of size 'dstSize'. 1727 `dstSize` : must be the **exact** size of original (uncompressed) data. 1728 Note : in contrast with FSE, HUFv06_decompress can regenerate 1729 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, 1730 because it knows size to regenerate. 1731 @return : size of regenerated data (== dstSize) 1732 or an error code, which can be tested using HUFv06_isError() 1733*/ 1734 1735 1736/* **************************************** 1737* Tool functions 1738******************************************/ 1739size_t HUFv06_compressBound(size_t size); /**< maximum compressed size */ 1740 1741 1742#if defined (__cplusplus) 1743} 1744#endif 1745 1746#endif /* HUFv06_H */ 1747/* ****************************************************************** 1748 Huffman codec, part of New Generation Entropy library 1749 header file, for static linking only 1750 Copyright (C) 2013-2016, Yann Collet 1751 1752 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1753 1754 Redistribution and use in source and binary forms, with or without 1755 modification, are permitted provided that the following conditions are 1756 met: 1757 1758 * Redistributions of source code must retain the above copyright 1759 notice, this list of conditions and the following disclaimer. 1760 * Redistributions in binary form must reproduce the above 1761 copyright notice, this list of conditions and the following disclaimer 1762 in the documentation and/or other materials provided with the 1763 distribution. 1764 1765 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1766 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1767 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1768 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1769 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1770 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1771 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1772 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1773 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1774 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1775 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1776 1777 You can contact the author at : 1778 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 1779****************************************************************** */ 1780#ifndef HUFv06_STATIC_H 1781#define HUFv06_STATIC_H 1782 1783#if defined (__cplusplus) 1784extern "C" { 1785#endif 1786 1787 1788/* **************************************** 1789* Static allocation 1790******************************************/ 1791/* HUF buffer bounds */ 1792#define HUFv06_CTABLEBOUND 129 1793#define HUFv06_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */ 1794#define HUFv06_COMPRESSBOUND(size) (HUFv06_CTABLEBOUND + HUFv06_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ 1795 1796/* static allocation of HUF's DTable */ 1797#define HUFv06_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) 1798#define HUFv06_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \ 1799 unsigned short DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 1800#define HUFv06_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \ 1801 unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 1802#define HUFv06_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \ 1803 unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog } 1804 1805 1806/* **************************************** 1807* Advanced decompression functions 1808******************************************/ 1809size_t HUFv06_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ 1810size_t HUFv06_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */ 1811 1812 1813 1814/*! 1815HUFv06_decompress() does the following: 18161. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics 18172. build Huffman table from save, using HUFv06_readDTableXn() 18183. decode 1 or 4 segments in parallel using HUFv06_decompressSXn_usingDTable 1819*/ 1820size_t HUFv06_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize); 1821size_t HUFv06_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize); 1822 1823size_t HUFv06_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable); 1824size_t HUFv06_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable); 1825 1826 1827/* single stream variants */ 1828size_t HUFv06_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ 1829size_t HUFv06_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */ 1830 1831size_t HUFv06_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable); 1832size_t HUFv06_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable); 1833 1834 1835 1836/* ************************************************************** 1837* Constants 1838****************************************************************/ 1839#define HUFv06_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUFv06_MAX_TABLELOG. Beyond that value, code does not work */ 1840#define HUFv06_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUFv06_ABSOLUTEMAX_TABLELOG */ 1841#define HUFv06_DEFAULT_TABLELOG HUFv06_MAX_TABLELOG /* tableLog by default, when not specified */ 1842#define HUFv06_MAX_SYMBOL_VALUE 255 1843#if (HUFv06_MAX_TABLELOG > HUFv06_ABSOLUTEMAX_TABLELOG) 1844# error "HUFv06_MAX_TABLELOG is too large !" 1845#endif 1846 1847 1848 1849/*! HUFv06_readStats() : 1850 Read compact Huffman tree, saved by HUFv06_writeCTable(). 1851 `huffWeight` is destination buffer. 1852 @return : size read from `src` 1853*/ 1854MEM_STATIC size_t HUFv06_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats, 1855 U32* nbSymbolsPtr, U32* tableLogPtr, 1856 const void* src, size_t srcSize) 1857{ 1858 U32 weightTotal; 1859 const BYTE* ip = (const BYTE*) src; 1860 size_t iSize; 1861 size_t oSize; 1862 1863 if (!srcSize) return ERROR(srcSize_wrong); 1864 iSize = ip[0]; 1865 /* memset(huffWeight, 0, hwSize); */ /* is not necessary, even though some analyzer complain ... */ 1866 1867 if (iSize >= 128) { /* special header */ 1868 if (iSize >= (242)) { /* RLE */ 1869 static U32 l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 }; 1870 oSize = l[iSize-242]; 1871 memset(huffWeight, 1, hwSize); 1872 iSize = 0; 1873 } 1874 else { /* Incompressible */ 1875 oSize = iSize - 127; 1876 iSize = ((oSize+1)/2); 1877 if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 1878 if (oSize >= hwSize) return ERROR(corruption_detected); 1879 ip += 1; 1880 { U32 n; 1881 for (n=0; n<oSize; n+=2) { 1882 huffWeight[n] = ip[n/2] >> 4; 1883 huffWeight[n+1] = ip[n/2] & 15; 1884 } } } } 1885 else { /* header compressed with FSE (normal case) */ 1886 if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 1887 oSize = FSEv06_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */ 1888 if (FSEv06_isError(oSize)) return oSize; 1889 } 1890 1891 /* collect weight stats */ 1892 memset(rankStats, 0, (HUFv06_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32)); 1893 weightTotal = 0; 1894 { U32 n; for (n=0; n<oSize; n++) { 1895 if (huffWeight[n] >= HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 1896 rankStats[huffWeight[n]]++; 1897 weightTotal += (1 << huffWeight[n]) >> 1; 1898 } } 1899 if (weightTotal == 0) return ERROR(corruption_detected); 1900 1901 /* get last non-null symbol weight (implied, total must be 2^n) */ 1902 { U32 const tableLog = BITv06_highbit32(weightTotal) + 1; 1903 if (tableLog > HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 1904 *tableLogPtr = tableLog; 1905 /* determine last weight */ 1906 { U32 const total = 1 << tableLog; 1907 U32 const rest = total - weightTotal; 1908 U32 const verif = 1 << BITv06_highbit32(rest); 1909 U32 const lastWeight = BITv06_highbit32(rest) + 1; 1910 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */ 1911 huffWeight[oSize] = (BYTE)lastWeight; 1912 rankStats[lastWeight]++; 1913 } } 1914 1915 /* check tree construction validity */ 1916 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */ 1917 1918 /* results */ 1919 *nbSymbolsPtr = (U32)(oSize+1); 1920 return iSize+1; 1921} 1922 1923 1924 1925#if defined (__cplusplus) 1926} 1927#endif 1928 1929#endif /* HUFv06_STATIC_H */ 1930/* ****************************************************************** 1931 Huffman decoder, part of New Generation Entropy library 1932 Copyright (C) 2013-2016, Yann Collet. 1933 1934 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 1935 1936 Redistribution and use in source and binary forms, with or without 1937 modification, are permitted provided that the following conditions are 1938 met: 1939 1940 * Redistributions of source code must retain the above copyright 1941 notice, this list of conditions and the following disclaimer. 1942 * Redistributions in binary form must reproduce the above 1943 copyright notice, this list of conditions and the following disclaimer 1944 in the documentation and/or other materials provided with the 1945 distribution. 1946 1947 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1948 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1949 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1950 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1951 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1952 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1953 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1954 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1955 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1956 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1957 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1958 1959 You can contact the author at : 1960 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy 1961 - Public forum : https://groups.google.com/forum/#!forum/lz4c 1962****************************************************************** */ 1963 1964/* ************************************************************** 1965* Compiler specifics 1966****************************************************************/ 1967#if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 1968/* inline is defined */ 1969#elif defined(_MSC_VER) 1970# define inline __inline 1971#else 1972# define inline /* disable inline */ 1973#endif 1974 1975 1976#ifdef _MSC_VER /* Visual Studio */ 1977# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 1978#endif 1979 1980 1981 1982/* ************************************************************** 1983* Error Management 1984****************************************************************/ 1985#define HUFv06_STATIC_ASSERT(c) { enum { HUFv06_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 1986 1987 1988 1989/* ******************************************************* 1990* HUF : Huffman block decompression 1991*********************************************************/ 1992typedef struct { BYTE byte; BYTE nbBits; } HUFv06_DEltX2; /* single-symbol decoding */ 1993 1994typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv06_DEltX4; /* double-symbols decoding */ 1995 1996typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t; 1997 1998 1999 2000/*-***************************/ 2001/* single-symbol decoding */ 2002/*-***************************/ 2003 2004size_t HUFv06_readDTableX2 (U16* DTable, const void* src, size_t srcSize) 2005{ 2006 BYTE huffWeight[HUFv06_MAX_SYMBOL_VALUE + 1]; 2007 U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */ 2008 U32 tableLog = 0; 2009 size_t iSize; 2010 U32 nbSymbols = 0; 2011 U32 n; 2012 U32 nextRankStart; 2013 void* const dtPtr = DTable + 1; 2014 HUFv06_DEltX2* const dt = (HUFv06_DEltX2*)dtPtr; 2015 2016 HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */ 2017 /* memset(huffWeight, 0, sizeof(huffWeight)); */ /* is not necessary, even though some analyzer complain ... */ 2018 2019 iSize = HUFv06_readStats(huffWeight, HUFv06_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize); 2020 if (HUFv06_isError(iSize)) return iSize; 2021 2022 /* check result */ 2023 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */ 2024 DTable[0] = (U16)tableLog; /* maybe should separate sizeof allocated DTable, from used size of DTable, in case of re-use */ 2025 2026 /* Prepare ranks */ 2027 nextRankStart = 0; 2028 for (n=1; n<tableLog+1; n++) { 2029 U32 current = nextRankStart; 2030 nextRankStart += (rankVal[n] << (n-1)); 2031 rankVal[n] = current; 2032 } 2033 2034 /* fill DTable */ 2035 for (n=0; n<nbSymbols; n++) { 2036 const U32 w = huffWeight[n]; 2037 const U32 length = (1 << w) >> 1; 2038 U32 i; 2039 HUFv06_DEltX2 D; 2040 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w); 2041 for (i = rankVal[w]; i < rankVal[w] + length; i++) 2042 dt[i] = D; 2043 rankVal[w] += length; 2044 } 2045 2046 return iSize; 2047} 2048 2049 2050static BYTE HUFv06_decodeSymbolX2(BITv06_DStream_t* Dstream, const HUFv06_DEltX2* dt, const U32 dtLog) 2051{ 2052 const size_t val = BITv06_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */ 2053 const BYTE c = dt[val].byte; 2054 BITv06_skipBits(Dstream, dt[val].nbBits); 2055 return c; 2056} 2057 2058#define HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \ 2059 *ptr++ = HUFv06_decodeSymbolX2(DStreamPtr, dt, dtLog) 2060 2061#define HUFv06_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \ 2062 if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \ 2063 HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 2064 2065#define HUFv06_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \ 2066 if (MEM_64bits()) \ 2067 HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 2068 2069static inline size_t HUFv06_decodeStreamX2(BYTE* p, BITv06_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv06_DEltX2* const dt, const U32 dtLog) 2070{ 2071 BYTE* const pStart = p; 2072 2073 /* up to 4 symbols at a time */ 2074 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p <= pEnd-4)) { 2075 HUFv06_DECODE_SYMBOLX2_2(p, bitDPtr); 2076 HUFv06_DECODE_SYMBOLX2_1(p, bitDPtr); 2077 HUFv06_DECODE_SYMBOLX2_2(p, bitDPtr); 2078 HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr); 2079 } 2080 2081 /* closer to the end */ 2082 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p < pEnd)) 2083 HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr); 2084 2085 /* no more data to retrieve from bitstream, hence no need to reload */ 2086 while (p < pEnd) 2087 HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr); 2088 2089 return pEnd-pStart; 2090} 2091 2092size_t HUFv06_decompress1X2_usingDTable( 2093 void* dst, size_t dstSize, 2094 const void* cSrc, size_t cSrcSize, 2095 const U16* DTable) 2096{ 2097 BYTE* op = (BYTE*)dst; 2098 BYTE* const oend = op + dstSize; 2099 const U32 dtLog = DTable[0]; 2100 const void* dtPtr = DTable; 2101 const HUFv06_DEltX2* const dt = ((const HUFv06_DEltX2*)dtPtr)+1; 2102 BITv06_DStream_t bitD; 2103 2104 { size_t const errorCode = BITv06_initDStream(&bitD, cSrc, cSrcSize); 2105 if (HUFv06_isError(errorCode)) return errorCode; } 2106 2107 HUFv06_decodeStreamX2(op, &bitD, oend, dt, dtLog); 2108 2109 /* check */ 2110 if (!BITv06_endOfDStream(&bitD)) return ERROR(corruption_detected); 2111 2112 return dstSize; 2113} 2114 2115size_t HUFv06_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2116{ 2117 HUFv06_CREATE_STATIC_DTABLEX2(DTable, HUFv06_MAX_TABLELOG); 2118 const BYTE* ip = (const BYTE*) cSrc; 2119 2120 size_t const errorCode = HUFv06_readDTableX2 (DTable, cSrc, cSrcSize); 2121 if (HUFv06_isError(errorCode)) return errorCode; 2122 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); 2123 ip += errorCode; 2124 cSrcSize -= errorCode; 2125 2126 return HUFv06_decompress1X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2127} 2128 2129 2130size_t HUFv06_decompress4X2_usingDTable( 2131 void* dst, size_t dstSize, 2132 const void* cSrc, size_t cSrcSize, 2133 const U16* DTable) 2134{ 2135 /* Check */ 2136 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 2137 2138 { const BYTE* const istart = (const BYTE*) cSrc; 2139 BYTE* const ostart = (BYTE*) dst; 2140 BYTE* const oend = ostart + dstSize; 2141 const void* const dtPtr = DTable; 2142 const HUFv06_DEltX2* const dt = ((const HUFv06_DEltX2*)dtPtr) +1; 2143 const U32 dtLog = DTable[0]; 2144 size_t errorCode; 2145 2146 /* Init */ 2147 BITv06_DStream_t bitD1; 2148 BITv06_DStream_t bitD2; 2149 BITv06_DStream_t bitD3; 2150 BITv06_DStream_t bitD4; 2151 const size_t length1 = MEM_readLE16(istart); 2152 const size_t length2 = MEM_readLE16(istart+2); 2153 const size_t length3 = MEM_readLE16(istart+4); 2154 size_t length4; 2155 const BYTE* const istart1 = istart + 6; /* jumpTable */ 2156 const BYTE* const istart2 = istart1 + length1; 2157 const BYTE* const istart3 = istart2 + length2; 2158 const BYTE* const istart4 = istart3 + length3; 2159 const size_t segmentSize = (dstSize+3) / 4; 2160 BYTE* const opStart2 = ostart + segmentSize; 2161 BYTE* const opStart3 = opStart2 + segmentSize; 2162 BYTE* const opStart4 = opStart3 + segmentSize; 2163 BYTE* op1 = ostart; 2164 BYTE* op2 = opStart2; 2165 BYTE* op3 = opStart3; 2166 BYTE* op4 = opStart4; 2167 U32 endSignal; 2168 2169 length4 = cSrcSize - (length1 + length2 + length3 + 6); 2170 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 2171 errorCode = BITv06_initDStream(&bitD1, istart1, length1); 2172 if (HUFv06_isError(errorCode)) return errorCode; 2173 errorCode = BITv06_initDStream(&bitD2, istart2, length2); 2174 if (HUFv06_isError(errorCode)) return errorCode; 2175 errorCode = BITv06_initDStream(&bitD3, istart3, length3); 2176 if (HUFv06_isError(errorCode)) return errorCode; 2177 errorCode = BITv06_initDStream(&bitD4, istart4, length4); 2178 if (HUFv06_isError(errorCode)) return errorCode; 2179 2180 /* 16-32 symbols per loop (4-8 symbols per stream) */ 2181 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4); 2182 for ( ; (endSignal==BITv06_DStream_unfinished) && (op4<(oend-7)) ; ) { 2183 HUFv06_DECODE_SYMBOLX2_2(op1, &bitD1); 2184 HUFv06_DECODE_SYMBOLX2_2(op2, &bitD2); 2185 HUFv06_DECODE_SYMBOLX2_2(op3, &bitD3); 2186 HUFv06_DECODE_SYMBOLX2_2(op4, &bitD4); 2187 HUFv06_DECODE_SYMBOLX2_1(op1, &bitD1); 2188 HUFv06_DECODE_SYMBOLX2_1(op2, &bitD2); 2189 HUFv06_DECODE_SYMBOLX2_1(op3, &bitD3); 2190 HUFv06_DECODE_SYMBOLX2_1(op4, &bitD4); 2191 HUFv06_DECODE_SYMBOLX2_2(op1, &bitD1); 2192 HUFv06_DECODE_SYMBOLX2_2(op2, &bitD2); 2193 HUFv06_DECODE_SYMBOLX2_2(op3, &bitD3); 2194 HUFv06_DECODE_SYMBOLX2_2(op4, &bitD4); 2195 HUFv06_DECODE_SYMBOLX2_0(op1, &bitD1); 2196 HUFv06_DECODE_SYMBOLX2_0(op2, &bitD2); 2197 HUFv06_DECODE_SYMBOLX2_0(op3, &bitD3); 2198 HUFv06_DECODE_SYMBOLX2_0(op4, &bitD4); 2199 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4); 2200 } 2201 2202 /* check corruption */ 2203 if (op1 > opStart2) return ERROR(corruption_detected); 2204 if (op2 > opStart3) return ERROR(corruption_detected); 2205 if (op3 > opStart4) return ERROR(corruption_detected); 2206 /* note : op4 supposed already verified within main loop */ 2207 2208 /* finish bitStreams one by one */ 2209 HUFv06_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog); 2210 HUFv06_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog); 2211 HUFv06_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog); 2212 HUFv06_decodeStreamX2(op4, &bitD4, oend, dt, dtLog); 2213 2214 /* check */ 2215 endSignal = BITv06_endOfDStream(&bitD1) & BITv06_endOfDStream(&bitD2) & BITv06_endOfDStream(&bitD3) & BITv06_endOfDStream(&bitD4); 2216 if (!endSignal) return ERROR(corruption_detected); 2217 2218 /* decoded size */ 2219 return dstSize; 2220 } 2221} 2222 2223 2224size_t HUFv06_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2225{ 2226 HUFv06_CREATE_STATIC_DTABLEX2(DTable, HUFv06_MAX_TABLELOG); 2227 const BYTE* ip = (const BYTE*) cSrc; 2228 2229 size_t const errorCode = HUFv06_readDTableX2 (DTable, cSrc, cSrcSize); 2230 if (HUFv06_isError(errorCode)) return errorCode; 2231 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); 2232 ip += errorCode; 2233 cSrcSize -= errorCode; 2234 2235 return HUFv06_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2236} 2237 2238 2239/* *************************/ 2240/* double-symbols decoding */ 2241/* *************************/ 2242 2243static void HUFv06_fillDTableX4Level2(HUFv06_DEltX4* DTable, U32 sizeLog, const U32 consumed, 2244 const U32* rankValOrigin, const int minWeight, 2245 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize, 2246 U32 nbBitsBaseline, U16 baseSeq) 2247{ 2248 HUFv06_DEltX4 DElt; 2249 U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1]; 2250 2251 /* get pre-calculated rankVal */ 2252 memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 2253 2254 /* fill skipped values */ 2255 if (minWeight>1) { 2256 U32 i, skipSize = rankVal[minWeight]; 2257 MEM_writeLE16(&(DElt.sequence), baseSeq); 2258 DElt.nbBits = (BYTE)(consumed); 2259 DElt.length = 1; 2260 for (i = 0; i < skipSize; i++) 2261 DTable[i] = DElt; 2262 } 2263 2264 /* fill DTable */ 2265 { U32 s; for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */ 2266 const U32 symbol = sortedSymbols[s].symbol; 2267 const U32 weight = sortedSymbols[s].weight; 2268 const U32 nbBits = nbBitsBaseline - weight; 2269 const U32 length = 1 << (sizeLog-nbBits); 2270 const U32 start = rankVal[weight]; 2271 U32 i = start; 2272 const U32 end = start + length; 2273 2274 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8))); 2275 DElt.nbBits = (BYTE)(nbBits + consumed); 2276 DElt.length = 2; 2277 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */ 2278 2279 rankVal[weight] += length; 2280 }} 2281} 2282 2283typedef U32 rankVal_t[HUFv06_ABSOLUTEMAX_TABLELOG][HUFv06_ABSOLUTEMAX_TABLELOG + 1]; 2284 2285static void HUFv06_fillDTableX4(HUFv06_DEltX4* DTable, const U32 targetLog, 2286 const sortedSymbol_t* sortedList, const U32 sortedListSize, 2287 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight, 2288 const U32 nbBitsBaseline) 2289{ 2290 U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1]; 2291 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */ 2292 const U32 minBits = nbBitsBaseline - maxWeight; 2293 U32 s; 2294 2295 memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 2296 2297 /* fill DTable */ 2298 for (s=0; s<sortedListSize; s++) { 2299 const U16 symbol = sortedList[s].symbol; 2300 const U32 weight = sortedList[s].weight; 2301 const U32 nbBits = nbBitsBaseline - weight; 2302 const U32 start = rankVal[weight]; 2303 const U32 length = 1 << (targetLog-nbBits); 2304 2305 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */ 2306 U32 sortedRank; 2307 int minWeight = nbBits + scaleLog; 2308 if (minWeight < 1) minWeight = 1; 2309 sortedRank = rankStart[minWeight]; 2310 HUFv06_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits, 2311 rankValOrigin[nbBits], minWeight, 2312 sortedList+sortedRank, sortedListSize-sortedRank, 2313 nbBitsBaseline, symbol); 2314 } else { 2315 HUFv06_DEltX4 DElt; 2316 MEM_writeLE16(&(DElt.sequence), symbol); 2317 DElt.nbBits = (BYTE)(nbBits); 2318 DElt.length = 1; 2319 { U32 u; 2320 const U32 end = start + length; 2321 for (u = start; u < end; u++) DTable[u] = DElt; 2322 } } 2323 rankVal[weight] += length; 2324 } 2325} 2326 2327size_t HUFv06_readDTableX4 (U32* DTable, const void* src, size_t srcSize) 2328{ 2329 BYTE weightList[HUFv06_MAX_SYMBOL_VALUE + 1]; 2330 sortedSymbol_t sortedSymbol[HUFv06_MAX_SYMBOL_VALUE + 1]; 2331 U32 rankStats[HUFv06_ABSOLUTEMAX_TABLELOG + 1] = { 0 }; 2332 U32 rankStart0[HUFv06_ABSOLUTEMAX_TABLELOG + 2] = { 0 }; 2333 U32* const rankStart = rankStart0+1; 2334 rankVal_t rankVal; 2335 U32 tableLog, maxW, sizeOfSort, nbSymbols; 2336 const U32 memLog = DTable[0]; 2337 size_t iSize; 2338 void* dtPtr = DTable; 2339 HUFv06_DEltX4* const dt = ((HUFv06_DEltX4*)dtPtr) + 1; 2340 2341 HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */ 2342 if (memLog > HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge); 2343 /* memset(weightList, 0, sizeof(weightList)); */ /* is not necessary, even though some analyzer complain ... */ 2344 2345 iSize = HUFv06_readStats(weightList, HUFv06_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize); 2346 if (HUFv06_isError(iSize)) return iSize; 2347 2348 /* check result */ 2349 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */ 2350 2351 /* find maxWeight */ 2352 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */ 2353 2354 /* Get start index of each weight */ 2355 { U32 w, nextRankStart = 0; 2356 for (w=1; w<maxW+1; w++) { 2357 U32 current = nextRankStart; 2358 nextRankStart += rankStats[w]; 2359 rankStart[w] = current; 2360 } 2361 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/ 2362 sizeOfSort = nextRankStart; 2363 } 2364 2365 /* sort symbols by weight */ 2366 { U32 s; 2367 for (s=0; s<nbSymbols; s++) { 2368 U32 const w = weightList[s]; 2369 U32 const r = rankStart[w]++; 2370 sortedSymbol[r].symbol = (BYTE)s; 2371 sortedSymbol[r].weight = (BYTE)w; 2372 } 2373 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */ 2374 } 2375 2376 /* Build rankVal */ 2377 { U32* const rankVal0 = rankVal[0]; 2378 { int const rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */ 2379 U32 nextRankVal = 0; 2380 U32 w; 2381 for (w=1; w<maxW+1; w++) { 2382 U32 current = nextRankVal; 2383 nextRankVal += rankStats[w] << (w+rescale); 2384 rankVal0[w] = current; 2385 } } 2386 { U32 const minBits = tableLog+1 - maxW; 2387 U32 consumed; 2388 for (consumed = minBits; consumed < memLog - minBits + 1; consumed++) { 2389 U32* const rankValPtr = rankVal[consumed]; 2390 U32 w; 2391 for (w = 1; w < maxW+1; w++) { 2392 rankValPtr[w] = rankVal0[w] >> consumed; 2393 } } } } 2394 2395 HUFv06_fillDTableX4(dt, memLog, 2396 sortedSymbol, sizeOfSort, 2397 rankStart0, rankVal, maxW, 2398 tableLog+1); 2399 2400 return iSize; 2401} 2402 2403 2404static U32 HUFv06_decodeSymbolX4(void* op, BITv06_DStream_t* DStream, const HUFv06_DEltX4* dt, const U32 dtLog) 2405{ 2406 const size_t val = BITv06_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 2407 memcpy(op, dt+val, 2); 2408 BITv06_skipBits(DStream, dt[val].nbBits); 2409 return dt[val].length; 2410} 2411 2412static U32 HUFv06_decodeLastSymbolX4(void* op, BITv06_DStream_t* DStream, const HUFv06_DEltX4* dt, const U32 dtLog) 2413{ 2414 const size_t val = BITv06_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 2415 memcpy(op, dt+val, 1); 2416 if (dt[val].length==1) BITv06_skipBits(DStream, dt[val].nbBits); 2417 else { 2418 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) { 2419 BITv06_skipBits(DStream, dt[val].nbBits); 2420 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8)) 2421 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 */ 2422 } } 2423 return 1; 2424} 2425 2426 2427#define HUFv06_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \ 2428 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2429 2430#define HUFv06_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \ 2431 if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \ 2432 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2433 2434#define HUFv06_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \ 2435 if (MEM_64bits()) \ 2436 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 2437 2438static inline size_t HUFv06_decodeStreamX4(BYTE* p, BITv06_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv06_DEltX4* const dt, const U32 dtLog) 2439{ 2440 BYTE* const pStart = p; 2441 2442 /* up to 8 symbols at a time */ 2443 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p < pEnd-7)) { 2444 HUFv06_DECODE_SYMBOLX4_2(p, bitDPtr); 2445 HUFv06_DECODE_SYMBOLX4_1(p, bitDPtr); 2446 HUFv06_DECODE_SYMBOLX4_2(p, bitDPtr); 2447 HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr); 2448 } 2449 2450 /* closer to the end */ 2451 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p <= pEnd-2)) 2452 HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr); 2453 2454 while (p <= pEnd-2) 2455 HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */ 2456 2457 if (p < pEnd) 2458 p += HUFv06_decodeLastSymbolX4(p, bitDPtr, dt, dtLog); 2459 2460 return p-pStart; 2461} 2462 2463 2464size_t HUFv06_decompress1X4_usingDTable( 2465 void* dst, size_t dstSize, 2466 const void* cSrc, size_t cSrcSize, 2467 const U32* DTable) 2468{ 2469 const BYTE* const istart = (const BYTE*) cSrc; 2470 BYTE* const ostart = (BYTE*) dst; 2471 BYTE* const oend = ostart + dstSize; 2472 2473 const U32 dtLog = DTable[0]; 2474 const void* const dtPtr = DTable; 2475 const HUFv06_DEltX4* const dt = ((const HUFv06_DEltX4*)dtPtr) +1; 2476 2477 /* Init */ 2478 BITv06_DStream_t bitD; 2479 { size_t const errorCode = BITv06_initDStream(&bitD, istart, cSrcSize); 2480 if (HUFv06_isError(errorCode)) return errorCode; } 2481 2482 /* decode */ 2483 HUFv06_decodeStreamX4(ostart, &bitD, oend, dt, dtLog); 2484 2485 /* check */ 2486 if (!BITv06_endOfDStream(&bitD)) return ERROR(corruption_detected); 2487 2488 /* decoded size */ 2489 return dstSize; 2490} 2491 2492size_t HUFv06_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2493{ 2494 HUFv06_CREATE_STATIC_DTABLEX4(DTable, HUFv06_MAX_TABLELOG); 2495 const BYTE* ip = (const BYTE*) cSrc; 2496 2497 size_t const hSize = HUFv06_readDTableX4 (DTable, cSrc, cSrcSize); 2498 if (HUFv06_isError(hSize)) return hSize; 2499 if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 2500 ip += hSize; 2501 cSrcSize -= hSize; 2502 2503 return HUFv06_decompress1X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2504} 2505 2506size_t HUFv06_decompress4X4_usingDTable( 2507 void* dst, size_t dstSize, 2508 const void* cSrc, size_t cSrcSize, 2509 const U32* DTable) 2510{ 2511 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 2512 2513 { const BYTE* const istart = (const BYTE*) cSrc; 2514 BYTE* const ostart = (BYTE*) dst; 2515 BYTE* const oend = ostart + dstSize; 2516 const void* const dtPtr = DTable; 2517 const HUFv06_DEltX4* const dt = ((const HUFv06_DEltX4*)dtPtr) +1; 2518 const U32 dtLog = DTable[0]; 2519 size_t errorCode; 2520 2521 /* Init */ 2522 BITv06_DStream_t bitD1; 2523 BITv06_DStream_t bitD2; 2524 BITv06_DStream_t bitD3; 2525 BITv06_DStream_t bitD4; 2526 const size_t length1 = MEM_readLE16(istart); 2527 const size_t length2 = MEM_readLE16(istart+2); 2528 const size_t length3 = MEM_readLE16(istart+4); 2529 size_t length4; 2530 const BYTE* const istart1 = istart + 6; /* jumpTable */ 2531 const BYTE* const istart2 = istart1 + length1; 2532 const BYTE* const istart3 = istart2 + length2; 2533 const BYTE* const istart4 = istart3 + length3; 2534 const size_t segmentSize = (dstSize+3) / 4; 2535 BYTE* const opStart2 = ostart + segmentSize; 2536 BYTE* const opStart3 = opStart2 + segmentSize; 2537 BYTE* const opStart4 = opStart3 + segmentSize; 2538 BYTE* op1 = ostart; 2539 BYTE* op2 = opStart2; 2540 BYTE* op3 = opStart3; 2541 BYTE* op4 = opStart4; 2542 U32 endSignal; 2543 2544 length4 = cSrcSize - (length1 + length2 + length3 + 6); 2545 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 2546 errorCode = BITv06_initDStream(&bitD1, istart1, length1); 2547 if (HUFv06_isError(errorCode)) return errorCode; 2548 errorCode = BITv06_initDStream(&bitD2, istart2, length2); 2549 if (HUFv06_isError(errorCode)) return errorCode; 2550 errorCode = BITv06_initDStream(&bitD3, istart3, length3); 2551 if (HUFv06_isError(errorCode)) return errorCode; 2552 errorCode = BITv06_initDStream(&bitD4, istart4, length4); 2553 if (HUFv06_isError(errorCode)) return errorCode; 2554 2555 /* 16-32 symbols per loop (4-8 symbols per stream) */ 2556 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4); 2557 for ( ; (endSignal==BITv06_DStream_unfinished) && (op4<(oend-7)) ; ) { 2558 HUFv06_DECODE_SYMBOLX4_2(op1, &bitD1); 2559 HUFv06_DECODE_SYMBOLX4_2(op2, &bitD2); 2560 HUFv06_DECODE_SYMBOLX4_2(op3, &bitD3); 2561 HUFv06_DECODE_SYMBOLX4_2(op4, &bitD4); 2562 HUFv06_DECODE_SYMBOLX4_1(op1, &bitD1); 2563 HUFv06_DECODE_SYMBOLX4_1(op2, &bitD2); 2564 HUFv06_DECODE_SYMBOLX4_1(op3, &bitD3); 2565 HUFv06_DECODE_SYMBOLX4_1(op4, &bitD4); 2566 HUFv06_DECODE_SYMBOLX4_2(op1, &bitD1); 2567 HUFv06_DECODE_SYMBOLX4_2(op2, &bitD2); 2568 HUFv06_DECODE_SYMBOLX4_2(op3, &bitD3); 2569 HUFv06_DECODE_SYMBOLX4_2(op4, &bitD4); 2570 HUFv06_DECODE_SYMBOLX4_0(op1, &bitD1); 2571 HUFv06_DECODE_SYMBOLX4_0(op2, &bitD2); 2572 HUFv06_DECODE_SYMBOLX4_0(op3, &bitD3); 2573 HUFv06_DECODE_SYMBOLX4_0(op4, &bitD4); 2574 2575 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4); 2576 } 2577 2578 /* check corruption */ 2579 if (op1 > opStart2) return ERROR(corruption_detected); 2580 if (op2 > opStart3) return ERROR(corruption_detected); 2581 if (op3 > opStart4) return ERROR(corruption_detected); 2582 /* note : op4 supposed already verified within main loop */ 2583 2584 /* finish bitStreams one by one */ 2585 HUFv06_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog); 2586 HUFv06_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog); 2587 HUFv06_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog); 2588 HUFv06_decodeStreamX4(op4, &bitD4, oend, dt, dtLog); 2589 2590 /* check */ 2591 endSignal = BITv06_endOfDStream(&bitD1) & BITv06_endOfDStream(&bitD2) & BITv06_endOfDStream(&bitD3) & BITv06_endOfDStream(&bitD4); 2592 if (!endSignal) return ERROR(corruption_detected); 2593 2594 /* decoded size */ 2595 return dstSize; 2596 } 2597} 2598 2599 2600size_t HUFv06_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2601{ 2602 HUFv06_CREATE_STATIC_DTABLEX4(DTable, HUFv06_MAX_TABLELOG); 2603 const BYTE* ip = (const BYTE*) cSrc; 2604 2605 size_t hSize = HUFv06_readDTableX4 (DTable, cSrc, cSrcSize); 2606 if (HUFv06_isError(hSize)) return hSize; 2607 if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 2608 ip += hSize; 2609 cSrcSize -= hSize; 2610 2611 return HUFv06_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 2612} 2613 2614 2615 2616 2617/* ********************************/ 2618/* Generic decompression selector */ 2619/* ********************************/ 2620 2621typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t; 2622static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] = 2623{ 2624 /* single, double, quad */ 2625 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */ 2626 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */ 2627 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */ 2628 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */ 2629 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */ 2630 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */ 2631 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */ 2632 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */ 2633 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */ 2634 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */ 2635 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */ 2636 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */ 2637 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */ 2638 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */ 2639 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */ 2640 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */ 2641}; 2642 2643typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); 2644 2645size_t HUFv06_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 2646{ 2647 static const decompressionAlgo decompress[3] = { HUFv06_decompress4X2, HUFv06_decompress4X4, NULL }; 2648 U32 Dtime[3]; /* decompression time estimation */ 2649 2650 /* validation checks */ 2651 if (dstSize == 0) return ERROR(dstSize_tooSmall); 2652 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */ 2653 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */ 2654 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */ 2655 2656 /* decoder timing evaluation */ 2657 { U32 const Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */ 2658 U32 const D256 = (U32)(dstSize >> 8); 2659 U32 n; for (n=0; n<3; n++) 2660 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256); 2661 } 2662 2663 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */ 2664 2665 { U32 algoNb = 0; 2666 if (Dtime[1] < Dtime[0]) algoNb = 1; 2667 /* if (Dtime[2] < Dtime[algoNb]) algoNb = 2; */ /* current speed of HUFv06_decompress4X6 is not good */ 2668 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize); 2669 } 2670 2671 /* return HUFv06_decompress4X2(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams single-symbol decoding */ 2672 /* return HUFv06_decompress4X4(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams double-symbols decoding */ 2673 /* return HUFv06_decompress4X6(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams quad-symbols decoding */ 2674} 2675/* 2676 Common functions of Zstd compression library 2677 Copyright (C) 2015-2016, Yann Collet. 2678 2679 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 2680 2681 Redistribution and use in source and binary forms, with or without 2682 modification, are permitted provided that the following conditions are 2683 met: 2684 * Redistributions of source code must retain the above copyright 2685 notice, this list of conditions and the following disclaimer. 2686 * Redistributions in binary form must reproduce the above 2687 copyright notice, this list of conditions and the following disclaimer 2688 in the documentation and/or other materials provided with the 2689 distribution. 2690 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2691 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2692 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2693 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2694 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2695 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2696 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2697 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2698 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2699 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2700 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2701 2702 You can contact the author at : 2703 - zstd homepage : http://www.zstd.net/ 2704*/ 2705 2706 2707/*-**************************************** 2708* Version 2709******************************************/ 2710 2711/*-**************************************** 2712* ZSTD Error Management 2713******************************************/ 2714/*! ZSTDv06_isError() : 2715* tells if a return value is an error code */ 2716unsigned ZSTDv06_isError(size_t code) { return ERR_isError(code); } 2717 2718/*! ZSTDv06_getErrorName() : 2719* provides error code string from function result (useful for debugging) */ 2720const char* ZSTDv06_getErrorName(size_t code) { return ERR_getErrorName(code); } 2721 2722 2723/* ************************************************************** 2724* ZBUFF Error Management 2725****************************************************************/ 2726unsigned ZBUFFv06_isError(size_t errorCode) { return ERR_isError(errorCode); } 2727 2728const char* ZBUFFv06_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); } 2729/* 2730 zstd - standard compression library 2731 Copyright (C) 2014-2016, Yann Collet. 2732 2733 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 2734 2735 Redistribution and use in source and binary forms, with or without 2736 modification, are permitted provided that the following conditions are 2737 met: 2738 * Redistributions of source code must retain the above copyright 2739 notice, this list of conditions and the following disclaimer. 2740 * Redistributions in binary form must reproduce the above 2741 copyright notice, this list of conditions and the following disclaimer 2742 in the documentation and/or other materials provided with the 2743 distribution. 2744 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2745 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2746 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2747 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2748 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2749 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2750 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2751 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2752 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2753 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2754 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2755 2756 You can contact the author at : 2757 - zstd homepage : http://www.zstd.net 2758*/ 2759 2760/* *************************************************************** 2761* Tuning parameters 2762*****************************************************************/ 2763/*! 2764 * HEAPMODE : 2765 * Select how default decompression function ZSTDv06_decompress() will allocate memory, 2766 * in memory stack (0), or in memory heap (1, requires malloc()) 2767 */ 2768#ifndef ZSTDv06_HEAPMODE 2769# define ZSTDv06_HEAPMODE 1 2770#endif 2771 2772 2773 2774/*-******************************************************* 2775* Compiler specifics 2776*********************************************************/ 2777#ifdef _MSC_VER /* Visual Studio */ 2778# include <intrin.h> /* For Visual 2005 */ 2779# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 2780# pragma warning(disable : 4324) /* disable: C4324: padded structure */ 2781#endif 2782 2783 2784/*-************************************* 2785* Macros 2786***************************************/ 2787#define ZSTDv06_isError ERR_isError /* for inlining */ 2788#define FSEv06_isError ERR_isError 2789#define HUFv06_isError ERR_isError 2790 2791 2792/*_******************************************************* 2793* Memory operations 2794**********************************************************/ 2795static void ZSTDv06_copy4(void* dst, const void* src) { memcpy(dst, src, 4); } 2796 2797 2798/*-************************************************************* 2799* Context management 2800***************************************************************/ 2801typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader, 2802 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock } ZSTDv06_dStage; 2803 2804struct ZSTDv06_DCtx_s 2805{ 2806 FSEv06_DTable LLTable[FSEv06_DTABLE_SIZE_U32(LLFSELog)]; 2807 FSEv06_DTable OffTable[FSEv06_DTABLE_SIZE_U32(OffFSELog)]; 2808 FSEv06_DTable MLTable[FSEv06_DTABLE_SIZE_U32(MLFSELog)]; 2809 unsigned hufTableX4[HUFv06_DTABLE_SIZE(HufLog)]; 2810 const void* previousDstEnd; 2811 const void* base; 2812 const void* vBase; 2813 const void* dictEnd; 2814 size_t expected; 2815 size_t headerSize; 2816 ZSTDv06_frameParams fParams; 2817 blockType_t bType; /* used in ZSTDv06_decompressContinue(), to transfer blockType between header decoding and block decoding stages */ 2818 ZSTDv06_dStage stage; 2819 U32 flagRepeatTable; 2820 const BYTE* litPtr; 2821 size_t litSize; 2822 BYTE litBuffer[ZSTDv06_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH]; 2823 BYTE headerBuffer[ZSTDv06_FRAMEHEADERSIZE_MAX]; 2824}; /* typedef'd to ZSTDv06_DCtx within "zstd_static.h" */ 2825 2826size_t ZSTDv06_sizeofDCtx (void); /* Hidden declaration */ 2827size_t ZSTDv06_sizeofDCtx (void) { return sizeof(ZSTDv06_DCtx); } 2828 2829size_t ZSTDv06_decompressBegin(ZSTDv06_DCtx* dctx) 2830{ 2831 dctx->expected = ZSTDv06_frameHeaderSize_min; 2832 dctx->stage = ZSTDds_getFrameHeaderSize; 2833 dctx->previousDstEnd = NULL; 2834 dctx->base = NULL; 2835 dctx->vBase = NULL; 2836 dctx->dictEnd = NULL; 2837 dctx->hufTableX4[0] = HufLog; 2838 dctx->flagRepeatTable = 0; 2839 return 0; 2840} 2841 2842ZSTDv06_DCtx* ZSTDv06_createDCtx(void) 2843{ 2844 ZSTDv06_DCtx* dctx = (ZSTDv06_DCtx*)malloc(sizeof(ZSTDv06_DCtx)); 2845 if (dctx==NULL) return NULL; 2846 ZSTDv06_decompressBegin(dctx); 2847 return dctx; 2848} 2849 2850size_t ZSTDv06_freeDCtx(ZSTDv06_DCtx* dctx) 2851{ 2852 free(dctx); 2853 return 0; /* reserved as a potential error code in the future */ 2854} 2855 2856void ZSTDv06_copyDCtx(ZSTDv06_DCtx* dstDCtx, const ZSTDv06_DCtx* srcDCtx) 2857{ 2858 memcpy(dstDCtx, srcDCtx, 2859 sizeof(ZSTDv06_DCtx) - (ZSTDv06_BLOCKSIZE_MAX+WILDCOPY_OVERLENGTH + ZSTDv06_frameHeaderSize_max)); /* no need to copy workspace */ 2860} 2861 2862 2863/*-************************************************************* 2864* Decompression section 2865***************************************************************/ 2866 2867/* Frame format description 2868 Frame Header - [ Block Header - Block ] - Frame End 2869 1) Frame Header 2870 - 4 bytes - Magic Number : ZSTDv06_MAGICNUMBER (defined within zstd_static.h) 2871 - 1 byte - Frame Descriptor 2872 2) Block Header 2873 - 3 bytes, starting with a 2-bits descriptor 2874 Uncompressed, Compressed, Frame End, unused 2875 3) Block 2876 See Block Format Description 2877 4) Frame End 2878 - 3 bytes, compatible with Block Header 2879*/ 2880 2881 2882/* Frame descriptor 2883 2884 1 byte, using : 2885 bit 0-3 : windowLog - ZSTDv06_WINDOWLOG_ABSOLUTEMIN (see zstd_internal.h) 2886 bit 4 : minmatch 4(0) or 3(1) 2887 bit 5 : reserved (must be zero) 2888 bit 6-7 : Frame content size : unknown, 1 byte, 2 bytes, 8 bytes 2889 2890 Optional : content size (0, 1, 2 or 8 bytes) 2891 0 : unknown 2892 1 : 0-255 bytes 2893 2 : 256 - 65535+256 2894 8 : up to 16 exa 2895*/ 2896 2897 2898/* Compressed Block, format description 2899 2900 Block = Literal Section - Sequences Section 2901 Prerequisite : size of (compressed) block, maximum size of regenerated data 2902 2903 1) Literal Section 2904 2905 1.1) Header : 1-5 bytes 2906 flags: 2 bits 2907 00 compressed by Huff0 2908 01 unused 2909 10 is Raw (uncompressed) 2910 11 is Rle 2911 Note : using 01 => Huff0 with precomputed table ? 2912 Note : delta map ? => compressed ? 2913 2914 1.1.1) Huff0-compressed literal block : 3-5 bytes 2915 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream 2916 srcSize < 1 KB => 3 bytes (2-2-10-10) 2917 srcSize < 16KB => 4 bytes (2-2-14-14) 2918 else => 5 bytes (2-2-18-18) 2919 big endian convention 2920 2921 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes 2922 size : 5 bits: (IS_RAW<<6) + (0<<4) + size 2923 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8) 2924 size&255 2925 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16) 2926 size>>8&255 2927 size&255 2928 2929 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes 2930 size : 5 bits: (IS_RLE<<6) + (0<<4) + size 2931 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8) 2932 size&255 2933 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16) 2934 size>>8&255 2935 size&255 2936 2937 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes 2938 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream 2939 srcSize < 1 KB => 3 bytes (2-2-10-10) 2940 srcSize < 16KB => 4 bytes (2-2-14-14) 2941 else => 5 bytes (2-2-18-18) 2942 big endian convention 2943 2944 1- CTable available (stored into workspace ?) 2945 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?) 2946 2947 2948 1.2) Literal block content 2949 2950 1.2.1) Huff0 block, using sizes from header 2951 See Huff0 format 2952 2953 1.2.2) Huff0 block, using prepared table 2954 2955 1.2.3) Raw content 2956 2957 1.2.4) single byte 2958 2959 2960 2) Sequences section 2961 TO DO 2962*/ 2963 2964/** ZSTDv06_frameHeaderSize() : 2965* srcSize must be >= ZSTDv06_frameHeaderSize_min. 2966* @return : size of the Frame Header */ 2967static size_t ZSTDv06_frameHeaderSize(const void* src, size_t srcSize) 2968{ 2969 if (srcSize < ZSTDv06_frameHeaderSize_min) return ERROR(srcSize_wrong); 2970 { U32 const fcsId = (((const BYTE*)src)[4]) >> 6; 2971 return ZSTDv06_frameHeaderSize_min + ZSTDv06_fcs_fieldSize[fcsId]; } 2972} 2973 2974 2975/** ZSTDv06_getFrameParams() : 2976* decode Frame Header, or provide expected `srcSize`. 2977* @return : 0, `fparamsPtr` is correctly filled, 2978* >0, `srcSize` is too small, result is expected `srcSize`, 2979* or an error code, which can be tested using ZSTDv06_isError() */ 2980size_t ZSTDv06_getFrameParams(ZSTDv06_frameParams* fparamsPtr, const void* src, size_t srcSize) 2981{ 2982 const BYTE* ip = (const BYTE*)src; 2983 2984 if (srcSize < ZSTDv06_frameHeaderSize_min) return ZSTDv06_frameHeaderSize_min; 2985 if (MEM_readLE32(src) != ZSTDv06_MAGICNUMBER) return ERROR(prefix_unknown); 2986 2987 /* ensure there is enough `srcSize` to fully read/decode frame header */ 2988 { size_t const fhsize = ZSTDv06_frameHeaderSize(src, srcSize); 2989 if (srcSize < fhsize) return fhsize; } 2990 2991 memset(fparamsPtr, 0, sizeof(*fparamsPtr)); 2992 { BYTE const frameDesc = ip[4]; 2993 fparamsPtr->windowLog = (frameDesc & 0xF) + ZSTDv06_WINDOWLOG_ABSOLUTEMIN; 2994 if ((frameDesc & 0x20) != 0) return ERROR(frameParameter_unsupported); /* reserved 1 bit */ 2995 switch(frameDesc >> 6) /* fcsId */ 2996 { 2997 default: /* impossible */ 2998 case 0 : fparamsPtr->frameContentSize = 0; break; 2999 case 1 : fparamsPtr->frameContentSize = ip[5]; break; 3000 case 2 : fparamsPtr->frameContentSize = MEM_readLE16(ip+5)+256; break; 3001 case 3 : fparamsPtr->frameContentSize = MEM_readLE64(ip+5); break; 3002 } } 3003 return 0; 3004} 3005 3006 3007/** ZSTDv06_decodeFrameHeader() : 3008* `srcSize` must be the size provided by ZSTDv06_frameHeaderSize(). 3009* @return : 0 if success, or an error code, which can be tested using ZSTDv06_isError() */ 3010static size_t ZSTDv06_decodeFrameHeader(ZSTDv06_DCtx* zc, const void* src, size_t srcSize) 3011{ 3012 size_t const result = ZSTDv06_getFrameParams(&(zc->fParams), src, srcSize); 3013 if ((MEM_32bits()) && (zc->fParams.windowLog > 25)) return ERROR(frameParameter_unsupported); 3014 return result; 3015} 3016 3017 3018typedef struct 3019{ 3020 blockType_t blockType; 3021 U32 origSize; 3022} blockProperties_t; 3023 3024/*! ZSTDv06_getcBlockSize() : 3025* Provides the size of compressed block from block header `src` */ 3026static size_t ZSTDv06_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr) 3027{ 3028 const BYTE* const in = (const BYTE*)src; 3029 U32 cSize; 3030 3031 if (srcSize < ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong); 3032 3033 bpPtr->blockType = (blockType_t)((*in) >> 6); 3034 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16); 3035 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0; 3036 3037 if (bpPtr->blockType == bt_end) return 0; 3038 if (bpPtr->blockType == bt_rle) return 1; 3039 return cSize; 3040} 3041 3042 3043static size_t ZSTDv06_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize) 3044{ 3045 if (dst==NULL) return ERROR(dstSize_tooSmall); 3046 if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall); 3047 memcpy(dst, src, srcSize); 3048 return srcSize; 3049} 3050 3051 3052/*! ZSTDv06_decodeLiteralsBlock() : 3053 @return : nb of bytes read from src (< srcSize ) */ 3054static size_t ZSTDv06_decodeLiteralsBlock(ZSTDv06_DCtx* dctx, 3055 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */ 3056{ 3057 const BYTE* const istart = (const BYTE*) src; 3058 3059 /* any compressed block with literals segment must be at least this size */ 3060 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected); 3061 3062 switch(istart[0]>> 6) 3063 { 3064 case IS_HUF: 3065 { size_t litSize, litCSize, singleStream=0; 3066 U32 lhSize = ((istart[0]) >> 4) & 3; 3067 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */ 3068 switch(lhSize) 3069 { 3070 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ 3071 /* 2 - 2 - 10 - 10 */ 3072 lhSize=3; 3073 singleStream = istart[0] & 16; 3074 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2); 3075 litCSize = ((istart[1] & 3) << 8) + istart[2]; 3076 break; 3077 case 2: 3078 /* 2 - 2 - 14 - 14 */ 3079 lhSize=4; 3080 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6); 3081 litCSize = ((istart[2] & 63) << 8) + istart[3]; 3082 break; 3083 case 3: 3084 /* 2 - 2 - 18 - 18 */ 3085 lhSize=5; 3086 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2); 3087 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4]; 3088 break; 3089 } 3090 if (litSize > ZSTDv06_BLOCKSIZE_MAX) return ERROR(corruption_detected); 3091 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected); 3092 3093 if (HUFv06_isError(singleStream ? 3094 HUFv06_decompress1X2(dctx->litBuffer, litSize, istart+lhSize, litCSize) : 3095 HUFv06_decompress (dctx->litBuffer, litSize, istart+lhSize, litCSize) )) 3096 return ERROR(corruption_detected); 3097 3098 dctx->litPtr = dctx->litBuffer; 3099 dctx->litSize = litSize; 3100 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 3101 return litCSize + lhSize; 3102 } 3103 case IS_PCH: 3104 { size_t litSize, litCSize; 3105 U32 lhSize = ((istart[0]) >> 4) & 3; 3106 if (lhSize != 1) /* only case supported for now : small litSize, single stream */ 3107 return ERROR(corruption_detected); 3108 if (!dctx->flagRepeatTable) 3109 return ERROR(dictionary_corrupted); 3110 3111 /* 2 - 2 - 10 - 10 */ 3112 lhSize=3; 3113 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2); 3114 litCSize = ((istart[1] & 3) << 8) + istart[2]; 3115 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected); 3116 3117 { size_t const errorCode = HUFv06_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTableX4); 3118 if (HUFv06_isError(errorCode)) return ERROR(corruption_detected); 3119 } 3120 dctx->litPtr = dctx->litBuffer; 3121 dctx->litSize = litSize; 3122 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 3123 return litCSize + lhSize; 3124 } 3125 case IS_RAW: 3126 { size_t litSize; 3127 U32 lhSize = ((istart[0]) >> 4) & 3; 3128 switch(lhSize) 3129 { 3130 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ 3131 lhSize=1; 3132 litSize = istart[0] & 31; 3133 break; 3134 case 2: 3135 litSize = ((istart[0] & 15) << 8) + istart[1]; 3136 break; 3137 case 3: 3138 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2]; 3139 break; 3140 } 3141 3142 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */ 3143 if (litSize+lhSize > srcSize) return ERROR(corruption_detected); 3144 memcpy(dctx->litBuffer, istart+lhSize, litSize); 3145 dctx->litPtr = dctx->litBuffer; 3146 dctx->litSize = litSize; 3147 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 3148 return lhSize+litSize; 3149 } 3150 /* direct reference into compressed stream */ 3151 dctx->litPtr = istart+lhSize; 3152 dctx->litSize = litSize; 3153 return lhSize+litSize; 3154 } 3155 case IS_RLE: 3156 { size_t litSize; 3157 U32 lhSize = ((istart[0]) >> 4) & 3; 3158 switch(lhSize) 3159 { 3160 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ 3161 lhSize = 1; 3162 litSize = istart[0] & 31; 3163 break; 3164 case 2: 3165 litSize = ((istart[0] & 15) << 8) + istart[1]; 3166 break; 3167 case 3: 3168 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2]; 3169 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */ 3170 break; 3171 } 3172 if (litSize > ZSTDv06_BLOCKSIZE_MAX) return ERROR(corruption_detected); 3173 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH); 3174 dctx->litPtr = dctx->litBuffer; 3175 dctx->litSize = litSize; 3176 return lhSize+1; 3177 } 3178 default: 3179 return ERROR(corruption_detected); /* impossible */ 3180 } 3181} 3182 3183 3184/*! ZSTDv06_buildSeqTable() : 3185 @return : nb bytes read from src, 3186 or an error code if it fails, testable with ZSTDv06_isError() 3187*/ 3188static size_t ZSTDv06_buildSeqTable(FSEv06_DTable* DTable, U32 type, U32 max, U32 maxLog, 3189 const void* src, size_t srcSize, 3190 const S16* defaultNorm, U32 defaultLog, U32 flagRepeatTable) 3191{ 3192 switch(type) 3193 { 3194 case FSEv06_ENCODING_RLE : 3195 if (!srcSize) return ERROR(srcSize_wrong); 3196 if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected); 3197 FSEv06_buildDTable_rle(DTable, *(const BYTE*)src); /* if *src > max, data is corrupted */ 3198 return 1; 3199 case FSEv06_ENCODING_RAW : 3200 FSEv06_buildDTable(DTable, defaultNorm, max, defaultLog); 3201 return 0; 3202 case FSEv06_ENCODING_STATIC: 3203 if (!flagRepeatTable) return ERROR(corruption_detected); 3204 return 0; 3205 default : /* impossible */ 3206 case FSEv06_ENCODING_DYNAMIC : 3207 { U32 tableLog; 3208 S16 norm[MaxSeq+1]; 3209 size_t const headerSize = FSEv06_readNCount(norm, &max, &tableLog, src, srcSize); 3210 if (FSEv06_isError(headerSize)) return ERROR(corruption_detected); 3211 if (tableLog > maxLog) return ERROR(corruption_detected); 3212 FSEv06_buildDTable(DTable, norm, max, tableLog); 3213 return headerSize; 3214 } } 3215} 3216 3217 3218static size_t ZSTDv06_decodeSeqHeaders(int* nbSeqPtr, 3219 FSEv06_DTable* DTableLL, FSEv06_DTable* DTableML, FSEv06_DTable* DTableOffb, U32 flagRepeatTable, 3220 const void* src, size_t srcSize) 3221{ 3222 const BYTE* const istart = (const BYTE*)src; 3223 const BYTE* const iend = istart + srcSize; 3224 const BYTE* ip = istart; 3225 3226 /* check */ 3227 if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong); 3228 3229 /* SeqHead */ 3230 { int nbSeq = *ip++; 3231 if (!nbSeq) { *nbSeqPtr=0; return 1; } 3232 if (nbSeq > 0x7F) { 3233 if (nbSeq == 0xFF) { 3234 if (ip+2 > iend) return ERROR(srcSize_wrong); 3235 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2; 3236 } else { 3237 if (ip >= iend) return ERROR(srcSize_wrong); 3238 nbSeq = ((nbSeq-0x80)<<8) + *ip++; 3239 } 3240 } 3241 *nbSeqPtr = nbSeq; 3242 } 3243 3244 /* FSE table descriptors */ 3245 if (ip + 4 > iend) return ERROR(srcSize_wrong); /* min : header byte + all 3 are "raw", hence no header, but at least xxLog bits per type */ 3246 { U32 const LLtype = *ip >> 6; 3247 U32 const Offtype = (*ip >> 4) & 3; 3248 U32 const MLtype = (*ip >> 2) & 3; 3249 ip++; 3250 3251 /* Build DTables */ 3252 { size_t const bhSize = ZSTDv06_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable); 3253 if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected); 3254 ip += bhSize; 3255 } 3256 { size_t const bhSize = ZSTDv06_buildSeqTable(DTableOffb, Offtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable); 3257 if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected); 3258 ip += bhSize; 3259 } 3260 { size_t const bhSize = ZSTDv06_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable); 3261 if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected); 3262 ip += bhSize; 3263 } } 3264 3265 return ip-istart; 3266} 3267 3268 3269typedef struct { 3270 size_t litLength; 3271 size_t matchLength; 3272 size_t offset; 3273} seq_t; 3274 3275typedef struct { 3276 BITv06_DStream_t DStream; 3277 FSEv06_DState_t stateLL; 3278 FSEv06_DState_t stateOffb; 3279 FSEv06_DState_t stateML; 3280 size_t prevOffset[ZSTDv06_REP_INIT]; 3281} seqState_t; 3282 3283 3284 3285static void ZSTDv06_decodeSequence(seq_t* seq, seqState_t* seqState) 3286{ 3287 /* Literal length */ 3288 U32 const llCode = FSEv06_peekSymbol(&(seqState->stateLL)); 3289 U32 const mlCode = FSEv06_peekSymbol(&(seqState->stateML)); 3290 U32 const ofCode = FSEv06_peekSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */ 3291 3292 U32 const llBits = LL_bits[llCode]; 3293 U32 const mlBits = ML_bits[mlCode]; 3294 U32 const ofBits = ofCode; 3295 U32 const totalBits = llBits+mlBits+ofBits; 3296 3297 static const U32 LL_base[MaxLL+1] = { 3298 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 3299 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 3300 0x2000, 0x4000, 0x8000, 0x10000 }; 3301 3302 static const U32 ML_base[MaxML+1] = { 3303 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 3304 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 3305 32, 34, 36, 38, 40, 44, 48, 56, 64, 80, 96, 0x80, 0x100, 0x200, 0x400, 0x800, 3306 0x1000, 0x2000, 0x4000, 0x8000, 0x10000 }; 3307 3308 static const U32 OF_base[MaxOff+1] = { 3309 0, 1, 3, 7, 0xF, 0x1F, 0x3F, 0x7F, 3310 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 3311 0xFFFF, 0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF, 3312 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, /*fake*/ 1, 1 }; 3313 3314 /* sequence */ 3315 { size_t offset; 3316 if (!ofCode) 3317 offset = 0; 3318 else { 3319 offset = OF_base[ofCode] + BITv06_readBits(&(seqState->DStream), ofBits); /* <= 26 bits */ 3320 if (MEM_32bits()) BITv06_reloadDStream(&(seqState->DStream)); 3321 } 3322 3323 if (offset < ZSTDv06_REP_NUM) { 3324 if (llCode == 0 && offset <= 1) offset = 1-offset; 3325 3326 if (offset != 0) { 3327 size_t temp = seqState->prevOffset[offset]; 3328 if (offset != 1) { 3329 seqState->prevOffset[2] = seqState->prevOffset[1]; 3330 } 3331 seqState->prevOffset[1] = seqState->prevOffset[0]; 3332 seqState->prevOffset[0] = offset = temp; 3333 3334 } else { 3335 offset = seqState->prevOffset[0]; 3336 } 3337 } else { 3338 offset -= ZSTDv06_REP_MOVE; 3339 seqState->prevOffset[2] = seqState->prevOffset[1]; 3340 seqState->prevOffset[1] = seqState->prevOffset[0]; 3341 seqState->prevOffset[0] = offset; 3342 } 3343 seq->offset = offset; 3344 } 3345 3346 seq->matchLength = ML_base[mlCode] + MINMATCH + ((mlCode>31) ? BITv06_readBits(&(seqState->DStream), mlBits) : 0); /* <= 16 bits */ 3347 if (MEM_32bits() && (mlBits+llBits>24)) BITv06_reloadDStream(&(seqState->DStream)); 3348 3349 seq->litLength = LL_base[llCode] + ((llCode>15) ? BITv06_readBits(&(seqState->DStream), llBits) : 0); /* <= 16 bits */ 3350 if (MEM_32bits() || 3351 (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BITv06_reloadDStream(&(seqState->DStream)); 3352 3353 /* ANS state update */ 3354 FSEv06_updateState(&(seqState->stateLL), &(seqState->DStream)); /* <= 9 bits */ 3355 FSEv06_updateState(&(seqState->stateML), &(seqState->DStream)); /* <= 9 bits */ 3356 if (MEM_32bits()) BITv06_reloadDStream(&(seqState->DStream)); /* <= 18 bits */ 3357 FSEv06_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <= 8 bits */ 3358} 3359 3360 3361static size_t ZSTDv06_execSequence(BYTE* op, 3362 BYTE* const oend, seq_t sequence, 3363 const BYTE** litPtr, const BYTE* const litLimit, 3364 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd) 3365{ 3366 BYTE* const oLitEnd = op + sequence.litLength; 3367 size_t const sequenceLength = sequence.litLength + sequence.matchLength; 3368 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */ 3369 BYTE* const oend_8 = oend-8; 3370 const BYTE* const iLitEnd = *litPtr + sequence.litLength; 3371 const BYTE* match = oLitEnd - sequence.offset; 3372 3373 /* check */ 3374 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */ 3375 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */ 3376 if (iLitEnd > litLimit) return ERROR(corruption_detected); /* over-read beyond lit buffer */ 3377 3378 /* copy Literals */ 3379 ZSTDv06_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */ 3380 op = oLitEnd; 3381 *litPtr = iLitEnd; /* update for next sequence */ 3382 3383 /* copy Match */ 3384 if (sequence.offset > (size_t)(oLitEnd - base)) { 3385 /* offset beyond prefix */ 3386 if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected); 3387 match = dictEnd - (base-match); 3388 if (match + sequence.matchLength <= dictEnd) { 3389 memmove(oLitEnd, match, sequence.matchLength); 3390 return sequenceLength; 3391 } 3392 /* span extDict & currentPrefixSegment */ 3393 { size_t const length1 = dictEnd - match; 3394 memmove(oLitEnd, match, length1); 3395 op = oLitEnd + length1; 3396 sequence.matchLength -= length1; 3397 match = base; 3398 if (op > oend_8 || sequence.matchLength < MINMATCH) { 3399 while (op < oMatchEnd) *op++ = *match++; 3400 return sequenceLength; 3401 } 3402 } } 3403 /* Requirement: op <= oend_8 */ 3404 3405 /* match within prefix */ 3406 if (sequence.offset < 8) { 3407 /* close range match, overlap */ 3408 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */ 3409 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */ 3410 int const sub2 = dec64table[sequence.offset]; 3411 op[0] = match[0]; 3412 op[1] = match[1]; 3413 op[2] = match[2]; 3414 op[3] = match[3]; 3415 match += dec32table[sequence.offset]; 3416 ZSTDv06_copy4(op+4, match); 3417 match -= sub2; 3418 } else { 3419 ZSTDv06_copy8(op, match); 3420 } 3421 op += 8; match += 8; 3422 3423 if (oMatchEnd > oend-(16-MINMATCH)) { 3424 if (op < oend_8) { 3425 ZSTDv06_wildcopy(op, match, oend_8 - op); 3426 match += oend_8 - op; 3427 op = oend_8; 3428 } 3429 while (op < oMatchEnd) *op++ = *match++; 3430 } else { 3431 ZSTDv06_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */ 3432 } 3433 return sequenceLength; 3434} 3435 3436 3437static size_t ZSTDv06_decompressSequences( 3438 ZSTDv06_DCtx* dctx, 3439 void* dst, size_t maxDstSize, 3440 const void* seqStart, size_t seqSize) 3441{ 3442 const BYTE* ip = (const BYTE*)seqStart; 3443 const BYTE* const iend = ip + seqSize; 3444 BYTE* const ostart = (BYTE*)dst; 3445 BYTE* const oend = ostart + maxDstSize; 3446 BYTE* op = ostart; 3447 const BYTE* litPtr = dctx->litPtr; 3448 const BYTE* const litEnd = litPtr + dctx->litSize; 3449 FSEv06_DTable* DTableLL = dctx->LLTable; 3450 FSEv06_DTable* DTableML = dctx->MLTable; 3451 FSEv06_DTable* DTableOffb = dctx->OffTable; 3452 const BYTE* const base = (const BYTE*) (dctx->base); 3453 const BYTE* const vBase = (const BYTE*) (dctx->vBase); 3454 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd); 3455 int nbSeq; 3456 3457 /* Build Decoding Tables */ 3458 { size_t const seqHSize = ZSTDv06_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->flagRepeatTable, ip, seqSize); 3459 if (ZSTDv06_isError(seqHSize)) return seqHSize; 3460 ip += seqHSize; 3461 dctx->flagRepeatTable = 0; 3462 } 3463 3464 /* Regen sequences */ 3465 if (nbSeq) { 3466 seq_t sequence; 3467 seqState_t seqState; 3468 3469 memset(&sequence, 0, sizeof(sequence)); 3470 sequence.offset = REPCODE_STARTVALUE; 3471 { U32 i; for (i=0; i<ZSTDv06_REP_INIT; i++) seqState.prevOffset[i] = REPCODE_STARTVALUE; } 3472 { size_t const errorCode = BITv06_initDStream(&(seqState.DStream), ip, iend-ip); 3473 if (ERR_isError(errorCode)) return ERROR(corruption_detected); } 3474 FSEv06_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL); 3475 FSEv06_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb); 3476 FSEv06_initDState(&(seqState.stateML), &(seqState.DStream), DTableML); 3477 3478 for ( ; (BITv06_reloadDStream(&(seqState.DStream)) <= BITv06_DStream_completed) && nbSeq ; ) { 3479 nbSeq--; 3480 ZSTDv06_decodeSequence(&sequence, &seqState); 3481 3482#if 0 /* debug */ 3483 static BYTE* start = NULL; 3484 if (start==NULL) start = op; 3485 size_t pos = (size_t)(op-start); 3486 if ((pos >= 5810037) && (pos < 5810400)) 3487 printf("Dpos %6u :%5u literals & match %3u bytes at distance %6u \n", 3488 pos, (U32)sequence.litLength, (U32)sequence.matchLength, (U32)sequence.offset); 3489#endif 3490 3491 { size_t const oneSeqSize = ZSTDv06_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd); 3492 if (ZSTDv06_isError(oneSeqSize)) return oneSeqSize; 3493 op += oneSeqSize; 3494 } } 3495 3496 /* check if reached exact end */ 3497 if (nbSeq) return ERROR(corruption_detected); 3498 } 3499 3500 /* last literal segment */ 3501 { size_t const lastLLSize = litEnd - litPtr; 3502 if (litPtr > litEnd) return ERROR(corruption_detected); /* too many literals already used */ 3503 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall); 3504 if (lastLLSize > 0) { 3505 memcpy(op, litPtr, lastLLSize); 3506 op += lastLLSize; 3507 } 3508 } 3509 3510 return op-ostart; 3511} 3512 3513 3514static void ZSTDv06_checkContinuity(ZSTDv06_DCtx* dctx, const void* dst) 3515{ 3516 if (dst != dctx->previousDstEnd) { /* not contiguous */ 3517 dctx->dictEnd = dctx->previousDstEnd; 3518 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); 3519 dctx->base = dst; 3520 dctx->previousDstEnd = dst; 3521 } 3522} 3523 3524 3525static size_t ZSTDv06_decompressBlock_internal(ZSTDv06_DCtx* dctx, 3526 void* dst, size_t dstCapacity, 3527 const void* src, size_t srcSize) 3528{ /* blockType == blockCompressed */ 3529 const BYTE* ip = (const BYTE*)src; 3530 3531 if (srcSize >= ZSTDv06_BLOCKSIZE_MAX) return ERROR(srcSize_wrong); 3532 3533 /* Decode literals sub-block */ 3534 { size_t const litCSize = ZSTDv06_decodeLiteralsBlock(dctx, src, srcSize); 3535 if (ZSTDv06_isError(litCSize)) return litCSize; 3536 ip += litCSize; 3537 srcSize -= litCSize; 3538 } 3539 return ZSTDv06_decompressSequences(dctx, dst, dstCapacity, ip, srcSize); 3540} 3541 3542 3543size_t ZSTDv06_decompressBlock(ZSTDv06_DCtx* dctx, 3544 void* dst, size_t dstCapacity, 3545 const void* src, size_t srcSize) 3546{ 3547 ZSTDv06_checkContinuity(dctx, dst); 3548 return ZSTDv06_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize); 3549} 3550 3551 3552/*! ZSTDv06_decompressFrame() : 3553* `dctx` must be properly initialized */ 3554static size_t ZSTDv06_decompressFrame(ZSTDv06_DCtx* dctx, 3555 void* dst, size_t dstCapacity, 3556 const void* src, size_t srcSize) 3557{ 3558 const BYTE* ip = (const BYTE*)src; 3559 const BYTE* const iend = ip + srcSize; 3560 BYTE* const ostart = (BYTE*)dst; 3561 BYTE* op = ostart; 3562 BYTE* const oend = ostart + dstCapacity; 3563 size_t remainingSize = srcSize; 3564 blockProperties_t blockProperties = { bt_compressed, 0 }; 3565 3566 /* check */ 3567 if (srcSize < ZSTDv06_frameHeaderSize_min+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong); 3568 3569 /* Frame Header */ 3570 { size_t const frameHeaderSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min); 3571 if (ZSTDv06_isError(frameHeaderSize)) return frameHeaderSize; 3572 if (srcSize < frameHeaderSize+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong); 3573 if (ZSTDv06_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected); 3574 ip += frameHeaderSize; remainingSize -= frameHeaderSize; 3575 } 3576 3577 /* Loop on each block */ 3578 while (1) { 3579 size_t decodedSize=0; 3580 size_t const cBlockSize = ZSTDv06_getcBlockSize(ip, iend-ip, &blockProperties); 3581 if (ZSTDv06_isError(cBlockSize)) return cBlockSize; 3582 3583 ip += ZSTDv06_blockHeaderSize; 3584 remainingSize -= ZSTDv06_blockHeaderSize; 3585 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); 3586 3587 switch(blockProperties.blockType) 3588 { 3589 case bt_compressed: 3590 decodedSize = ZSTDv06_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize); 3591 break; 3592 case bt_raw : 3593 decodedSize = ZSTDv06_copyRawBlock(op, oend-op, ip, cBlockSize); 3594 break; 3595 case bt_rle : 3596 return ERROR(GENERIC); /* not yet supported */ 3597 break; 3598 case bt_end : 3599 /* end of frame */ 3600 if (remainingSize) return ERROR(srcSize_wrong); 3601 break; 3602 default: 3603 return ERROR(GENERIC); /* impossible */ 3604 } 3605 if (cBlockSize == 0) break; /* bt_end */ 3606 3607 if (ZSTDv06_isError(decodedSize)) return decodedSize; 3608 op += decodedSize; 3609 ip += cBlockSize; 3610 remainingSize -= cBlockSize; 3611 } 3612 3613 return op-ostart; 3614} 3615 3616 3617size_t ZSTDv06_decompress_usingPreparedDCtx(ZSTDv06_DCtx* dctx, const ZSTDv06_DCtx* refDCtx, 3618 void* dst, size_t dstCapacity, 3619 const void* src, size_t srcSize) 3620{ 3621 ZSTDv06_copyDCtx(dctx, refDCtx); 3622 ZSTDv06_checkContinuity(dctx, dst); 3623 return ZSTDv06_decompressFrame(dctx, dst, dstCapacity, src, srcSize); 3624} 3625 3626 3627size_t ZSTDv06_decompress_usingDict(ZSTDv06_DCtx* dctx, 3628 void* dst, size_t dstCapacity, 3629 const void* src, size_t srcSize, 3630 const void* dict, size_t dictSize) 3631{ 3632 ZSTDv06_decompressBegin_usingDict(dctx, dict, dictSize); 3633 ZSTDv06_checkContinuity(dctx, dst); 3634 return ZSTDv06_decompressFrame(dctx, dst, dstCapacity, src, srcSize); 3635} 3636 3637 3638size_t ZSTDv06_decompressDCtx(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize) 3639{ 3640 return ZSTDv06_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0); 3641} 3642 3643 3644size_t ZSTDv06_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize) 3645{ 3646#if defined(ZSTDv06_HEAPMODE) && (ZSTDv06_HEAPMODE==1) 3647 size_t regenSize; 3648 ZSTDv06_DCtx* dctx = ZSTDv06_createDCtx(); 3649 if (dctx==NULL) return ERROR(memory_allocation); 3650 regenSize = ZSTDv06_decompressDCtx(dctx, dst, dstCapacity, src, srcSize); 3651 ZSTDv06_freeDCtx(dctx); 3652 return regenSize; 3653#else /* stack mode */ 3654 ZSTDv06_DCtx dctx; 3655 return ZSTDv06_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize); 3656#endif 3657} 3658 3659/* ZSTD_errorFrameSizeInfoLegacy() : 3660 assumes `cSize` and `dBound` are _not_ NULL */ 3661static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret) 3662{ 3663 *cSize = ret; 3664 *dBound = ZSTD_CONTENTSIZE_ERROR; 3665} 3666 3667void ZSTDv06_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound) 3668{ 3669 const BYTE* ip = (const BYTE*)src; 3670 size_t remainingSize = srcSize; 3671 size_t nbBlocks = 0; 3672 blockProperties_t blockProperties = { bt_compressed, 0 }; 3673 3674 /* Frame Header */ 3675 { size_t const frameHeaderSize = ZSTDv06_frameHeaderSize(src, srcSize); 3676 if (ZSTDv06_isError(frameHeaderSize)) { 3677 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, frameHeaderSize); 3678 return; 3679 } 3680 if (MEM_readLE32(src) != ZSTDv06_MAGICNUMBER) { 3681 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown)); 3682 return; 3683 } 3684 if (srcSize < frameHeaderSize+ZSTDv06_blockHeaderSize) { 3685 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 3686 return; 3687 } 3688 ip += frameHeaderSize; remainingSize -= frameHeaderSize; 3689 } 3690 3691 /* Loop on each block */ 3692 while (1) { 3693 size_t const cBlockSize = ZSTDv06_getcBlockSize(ip, remainingSize, &blockProperties); 3694 if (ZSTDv06_isError(cBlockSize)) { 3695 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize); 3696 return; 3697 } 3698 3699 ip += ZSTDv06_blockHeaderSize; 3700 remainingSize -= ZSTDv06_blockHeaderSize; 3701 if (cBlockSize > remainingSize) { 3702 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 3703 return; 3704 } 3705 3706 if (cBlockSize == 0) break; /* bt_end */ 3707 3708 ip += cBlockSize; 3709 remainingSize -= cBlockSize; 3710 nbBlocks++; 3711 } 3712 3713 *cSize = ip - (const BYTE*)src; 3714 *dBound = nbBlocks * ZSTDv06_BLOCKSIZE_MAX; 3715} 3716 3717/*_****************************** 3718* Streaming Decompression API 3719********************************/ 3720size_t ZSTDv06_nextSrcSizeToDecompress(ZSTDv06_DCtx* dctx) 3721{ 3722 return dctx->expected; 3723} 3724 3725size_t ZSTDv06_decompressContinue(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize) 3726{ 3727 /* Sanity check */ 3728 if (srcSize != dctx->expected) return ERROR(srcSize_wrong); 3729 if (dstCapacity) ZSTDv06_checkContinuity(dctx, dst); 3730 3731 /* Decompress : frame header; part 1 */ 3732 switch (dctx->stage) 3733 { 3734 case ZSTDds_getFrameHeaderSize : 3735 if (srcSize != ZSTDv06_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */ 3736 dctx->headerSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min); 3737 if (ZSTDv06_isError(dctx->headerSize)) return dctx->headerSize; 3738 memcpy(dctx->headerBuffer, src, ZSTDv06_frameHeaderSize_min); 3739 if (dctx->headerSize > ZSTDv06_frameHeaderSize_min) { 3740 dctx->expected = dctx->headerSize - ZSTDv06_frameHeaderSize_min; 3741 dctx->stage = ZSTDds_decodeFrameHeader; 3742 return 0; 3743 } 3744 dctx->expected = 0; /* not necessary to copy more */ 3745 /* fall-through */ 3746 case ZSTDds_decodeFrameHeader: 3747 { size_t result; 3748 memcpy(dctx->headerBuffer + ZSTDv06_frameHeaderSize_min, src, dctx->expected); 3749 result = ZSTDv06_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize); 3750 if (ZSTDv06_isError(result)) return result; 3751 dctx->expected = ZSTDv06_blockHeaderSize; 3752 dctx->stage = ZSTDds_decodeBlockHeader; 3753 return 0; 3754 } 3755 case ZSTDds_decodeBlockHeader: 3756 { blockProperties_t bp; 3757 size_t const cBlockSize = ZSTDv06_getcBlockSize(src, ZSTDv06_blockHeaderSize, &bp); 3758 if (ZSTDv06_isError(cBlockSize)) return cBlockSize; 3759 if (bp.blockType == bt_end) { 3760 dctx->expected = 0; 3761 dctx->stage = ZSTDds_getFrameHeaderSize; 3762 } else { 3763 dctx->expected = cBlockSize; 3764 dctx->bType = bp.blockType; 3765 dctx->stage = ZSTDds_decompressBlock; 3766 } 3767 return 0; 3768 } 3769 case ZSTDds_decompressBlock: 3770 { size_t rSize; 3771 switch(dctx->bType) 3772 { 3773 case bt_compressed: 3774 rSize = ZSTDv06_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize); 3775 break; 3776 case bt_raw : 3777 rSize = ZSTDv06_copyRawBlock(dst, dstCapacity, src, srcSize); 3778 break; 3779 case bt_rle : 3780 return ERROR(GENERIC); /* not yet handled */ 3781 break; 3782 case bt_end : /* should never happen (filtered at phase 1) */ 3783 rSize = 0; 3784 break; 3785 default: 3786 return ERROR(GENERIC); /* impossible */ 3787 } 3788 dctx->stage = ZSTDds_decodeBlockHeader; 3789 dctx->expected = ZSTDv06_blockHeaderSize; 3790 dctx->previousDstEnd = (char*)dst + rSize; 3791 return rSize; 3792 } 3793 default: 3794 return ERROR(GENERIC); /* impossible */ 3795 } 3796} 3797 3798 3799static void ZSTDv06_refDictContent(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize) 3800{ 3801 dctx->dictEnd = dctx->previousDstEnd; 3802 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); 3803 dctx->base = dict; 3804 dctx->previousDstEnd = (const char*)dict + dictSize; 3805} 3806 3807static size_t ZSTDv06_loadEntropy(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize) 3808{ 3809 size_t hSize, offcodeHeaderSize, matchlengthHeaderSize, litlengthHeaderSize; 3810 3811 hSize = HUFv06_readDTableX4(dctx->hufTableX4, dict, dictSize); 3812 if (HUFv06_isError(hSize)) return ERROR(dictionary_corrupted); 3813 dict = (const char*)dict + hSize; 3814 dictSize -= hSize; 3815 3816 { short offcodeNCount[MaxOff+1]; 3817 U32 offcodeMaxValue=MaxOff, offcodeLog; 3818 offcodeHeaderSize = FSEv06_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dict, dictSize); 3819 if (FSEv06_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted); 3820 if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted); 3821 { size_t const errorCode = FSEv06_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog); 3822 if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); } 3823 dict = (const char*)dict + offcodeHeaderSize; 3824 dictSize -= offcodeHeaderSize; 3825 } 3826 3827 { short matchlengthNCount[MaxML+1]; 3828 unsigned matchlengthMaxValue = MaxML, matchlengthLog; 3829 matchlengthHeaderSize = FSEv06_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dict, dictSize); 3830 if (FSEv06_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted); 3831 if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted); 3832 { size_t const errorCode = FSEv06_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog); 3833 if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); } 3834 dict = (const char*)dict + matchlengthHeaderSize; 3835 dictSize -= matchlengthHeaderSize; 3836 } 3837 3838 { short litlengthNCount[MaxLL+1]; 3839 unsigned litlengthMaxValue = MaxLL, litlengthLog; 3840 litlengthHeaderSize = FSEv06_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dict, dictSize); 3841 if (FSEv06_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted); 3842 if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted); 3843 { size_t const errorCode = FSEv06_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog); 3844 if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); } 3845 } 3846 3847 dctx->flagRepeatTable = 1; 3848 return hSize + offcodeHeaderSize + matchlengthHeaderSize + litlengthHeaderSize; 3849} 3850 3851static size_t ZSTDv06_decompress_insertDictionary(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize) 3852{ 3853 size_t eSize; 3854 U32 const magic = MEM_readLE32(dict); 3855 if (magic != ZSTDv06_DICT_MAGIC) { 3856 /* pure content mode */ 3857 ZSTDv06_refDictContent(dctx, dict, dictSize); 3858 return 0; 3859 } 3860 /* load entropy tables */ 3861 dict = (const char*)dict + 4; 3862 dictSize -= 4; 3863 eSize = ZSTDv06_loadEntropy(dctx, dict, dictSize); 3864 if (ZSTDv06_isError(eSize)) return ERROR(dictionary_corrupted); 3865 3866 /* reference dictionary content */ 3867 dict = (const char*)dict + eSize; 3868 dictSize -= eSize; 3869 ZSTDv06_refDictContent(dctx, dict, dictSize); 3870 3871 return 0; 3872} 3873 3874 3875size_t ZSTDv06_decompressBegin_usingDict(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize) 3876{ 3877 { size_t const errorCode = ZSTDv06_decompressBegin(dctx); 3878 if (ZSTDv06_isError(errorCode)) return errorCode; } 3879 3880 if (dict && dictSize) { 3881 size_t const errorCode = ZSTDv06_decompress_insertDictionary(dctx, dict, dictSize); 3882 if (ZSTDv06_isError(errorCode)) return ERROR(dictionary_corrupted); 3883 } 3884 3885 return 0; 3886} 3887 3888/* 3889 Buffered version of Zstd compression library 3890 Copyright (C) 2015-2016, Yann Collet. 3891 3892 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 3893 3894 Redistribution and use in source and binary forms, with or without 3895 modification, are permitted provided that the following conditions are 3896 met: 3897 * Redistributions of source code must retain the above copyright 3898 notice, this list of conditions and the following disclaimer. 3899 * Redistributions in binary form must reproduce the above 3900 copyright notice, this list of conditions and the following disclaimer 3901 in the documentation and/or other materials provided with the 3902 distribution. 3903 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 3904 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 3905 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 3906 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 3907 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3908 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3909 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3910 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3911 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3912 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3913 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3914 3915 You can contact the author at : 3916 - zstd homepage : http://www.zstd.net/ 3917*/ 3918 3919 3920/*-*************************************************************************** 3921* Streaming decompression howto 3922* 3923* A ZBUFFv06_DCtx object is required to track streaming operations. 3924* Use ZBUFFv06_createDCtx() and ZBUFFv06_freeDCtx() to create/release resources. 3925* Use ZBUFFv06_decompressInit() to start a new decompression operation, 3926* or ZBUFFv06_decompressInitDictionary() if decompression requires a dictionary. 3927* Note that ZBUFFv06_DCtx objects can be re-init multiple times. 3928* 3929* Use ZBUFFv06_decompressContinue() repetitively to consume your input. 3930* *srcSizePtr and *dstCapacityPtr can be any size. 3931* The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr. 3932* Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again. 3933* The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst. 3934* @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency), 3935* or 0 when a frame is completely decoded, 3936* or an error code, which can be tested using ZBUFFv06_isError(). 3937* 3938* Hint : recommended buffer sizes (not compulsory) : ZBUFFv06_recommendedDInSize() and ZBUFFv06_recommendedDOutSize() 3939* output : ZBUFFv06_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded. 3940* input : ZBUFFv06_recommendedDInSize == 128KB + 3; 3941* just follow indications from ZBUFFv06_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 . 3942* *******************************************************************************/ 3943 3944typedef enum { ZBUFFds_init, ZBUFFds_loadHeader, 3945 ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFFv06_dStage; 3946 3947/* *** Resource management *** */ 3948struct ZBUFFv06_DCtx_s { 3949 ZSTDv06_DCtx* zd; 3950 ZSTDv06_frameParams fParams; 3951 ZBUFFv06_dStage stage; 3952 char* inBuff; 3953 size_t inBuffSize; 3954 size_t inPos; 3955 char* outBuff; 3956 size_t outBuffSize; 3957 size_t outStart; 3958 size_t outEnd; 3959 size_t blockSize; 3960 BYTE headerBuffer[ZSTDv06_FRAMEHEADERSIZE_MAX]; 3961 size_t lhSize; 3962}; /* typedef'd to ZBUFFv06_DCtx within "zstd_buffered.h" */ 3963 3964 3965ZBUFFv06_DCtx* ZBUFFv06_createDCtx(void) 3966{ 3967 ZBUFFv06_DCtx* zbd = (ZBUFFv06_DCtx*)malloc(sizeof(ZBUFFv06_DCtx)); 3968 if (zbd==NULL) return NULL; 3969 memset(zbd, 0, sizeof(*zbd)); 3970 zbd->zd = ZSTDv06_createDCtx(); 3971 zbd->stage = ZBUFFds_init; 3972 return zbd; 3973} 3974 3975size_t ZBUFFv06_freeDCtx(ZBUFFv06_DCtx* zbd) 3976{ 3977 if (zbd==NULL) return 0; /* support free on null */ 3978 ZSTDv06_freeDCtx(zbd->zd); 3979 free(zbd->inBuff); 3980 free(zbd->outBuff); 3981 free(zbd); 3982 return 0; 3983} 3984 3985 3986/* *** Initialization *** */ 3987 3988size_t ZBUFFv06_decompressInitDictionary(ZBUFFv06_DCtx* zbd, const void* dict, size_t dictSize) 3989{ 3990 zbd->stage = ZBUFFds_loadHeader; 3991 zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0; 3992 return ZSTDv06_decompressBegin_usingDict(zbd->zd, dict, dictSize); 3993} 3994 3995size_t ZBUFFv06_decompressInit(ZBUFFv06_DCtx* zbd) 3996{ 3997 return ZBUFFv06_decompressInitDictionary(zbd, NULL, 0); 3998} 3999 4000 4001 4002MEM_STATIC size_t ZBUFFv06_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize) 4003{ 4004 size_t length = MIN(dstCapacity, srcSize); 4005 if (length > 0) { 4006 memcpy(dst, src, length); 4007 } 4008 return length; 4009} 4010 4011 4012/* *** Decompression *** */ 4013 4014size_t ZBUFFv06_decompressContinue(ZBUFFv06_DCtx* zbd, 4015 void* dst, size_t* dstCapacityPtr, 4016 const void* src, size_t* srcSizePtr) 4017{ 4018 const char* const istart = (const char*)src; 4019 const char* const iend = istart + *srcSizePtr; 4020 const char* ip = istart; 4021 char* const ostart = (char*)dst; 4022 char* const oend = ostart + *dstCapacityPtr; 4023 char* op = ostart; 4024 U32 notDone = 1; 4025 4026 while (notDone) { 4027 switch(zbd->stage) 4028 { 4029 case ZBUFFds_init : 4030 return ERROR(init_missing); 4031 4032 case ZBUFFds_loadHeader : 4033 { size_t const hSize = ZSTDv06_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize); 4034 if (hSize != 0) { 4035 size_t const toLoad = hSize - zbd->lhSize; /* if hSize!=0, hSize > zbd->lhSize */ 4036 if (ZSTDv06_isError(hSize)) return hSize; 4037 if (toLoad > (size_t)(iend-ip)) { /* not enough input to load full header */ 4038 memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip); 4039 zbd->lhSize += iend-ip; 4040 *dstCapacityPtr = 0; 4041 return (hSize - zbd->lhSize) + ZSTDv06_blockHeaderSize; /* remaining header bytes + next block header */ 4042 } 4043 memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad; 4044 break; 4045 } } 4046 4047 /* Consume header */ 4048 { size_t const h1Size = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); /* == ZSTDv06_frameHeaderSize_min */ 4049 size_t const h1Result = ZSTDv06_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size); 4050 if (ZSTDv06_isError(h1Result)) return h1Result; 4051 if (h1Size < zbd->lhSize) { /* long header */ 4052 size_t const h2Size = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); 4053 size_t const h2Result = ZSTDv06_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size); 4054 if (ZSTDv06_isError(h2Result)) return h2Result; 4055 } } 4056 4057 /* Frame header instruct buffer sizes */ 4058 { size_t const blockSize = MIN(1 << zbd->fParams.windowLog, ZSTDv06_BLOCKSIZE_MAX); 4059 zbd->blockSize = blockSize; 4060 if (zbd->inBuffSize < blockSize) { 4061 free(zbd->inBuff); 4062 zbd->inBuffSize = blockSize; 4063 zbd->inBuff = (char*)malloc(blockSize); 4064 if (zbd->inBuff == NULL) return ERROR(memory_allocation); 4065 } 4066 { size_t const neededOutSize = ((size_t)1 << zbd->fParams.windowLog) + blockSize + WILDCOPY_OVERLENGTH * 2; 4067 if (zbd->outBuffSize < neededOutSize) { 4068 free(zbd->outBuff); 4069 zbd->outBuffSize = neededOutSize; 4070 zbd->outBuff = (char*)malloc(neededOutSize); 4071 if (zbd->outBuff == NULL) return ERROR(memory_allocation); 4072 } } } 4073 zbd->stage = ZBUFFds_read; 4074 /* fall-through */ 4075 case ZBUFFds_read: 4076 { size_t const neededInSize = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); 4077 if (neededInSize==0) { /* end of frame */ 4078 zbd->stage = ZBUFFds_init; 4079 notDone = 0; 4080 break; 4081 } 4082 if ((size_t)(iend-ip) >= neededInSize) { /* decode directly from src */ 4083 size_t const decodedSize = ZSTDv06_decompressContinue(zbd->zd, 4084 zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart, 4085 ip, neededInSize); 4086 if (ZSTDv06_isError(decodedSize)) return decodedSize; 4087 ip += neededInSize; 4088 if (!decodedSize) break; /* this was just a header */ 4089 zbd->outEnd = zbd->outStart + decodedSize; 4090 zbd->stage = ZBUFFds_flush; 4091 break; 4092 } 4093 if (ip==iend) { notDone = 0; break; } /* no more input */ 4094 zbd->stage = ZBUFFds_load; 4095 } 4096 /* fall-through */ 4097 case ZBUFFds_load: 4098 { size_t const neededInSize = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); 4099 size_t const toLoad = neededInSize - zbd->inPos; /* should always be <= remaining space within inBuff */ 4100 size_t loadedSize; 4101 if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected); /* should never happen */ 4102 loadedSize = ZBUFFv06_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip); 4103 ip += loadedSize; 4104 zbd->inPos += loadedSize; 4105 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */ 4106 4107 /* decode loaded input */ 4108 { size_t const decodedSize = ZSTDv06_decompressContinue(zbd->zd, 4109 zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart, 4110 zbd->inBuff, neededInSize); 4111 if (ZSTDv06_isError(decodedSize)) return decodedSize; 4112 zbd->inPos = 0; /* input is consumed */ 4113 if (!decodedSize) { zbd->stage = ZBUFFds_read; break; } /* this was just a header */ 4114 zbd->outEnd = zbd->outStart + decodedSize; 4115 zbd->stage = ZBUFFds_flush; 4116 /* break; */ /* ZBUFFds_flush follows */ 4117 } 4118 } 4119 /* fall-through */ 4120 case ZBUFFds_flush: 4121 { size_t const toFlushSize = zbd->outEnd - zbd->outStart; 4122 size_t const flushedSize = ZBUFFv06_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize); 4123 op += flushedSize; 4124 zbd->outStart += flushedSize; 4125 if (flushedSize == toFlushSize) { 4126 zbd->stage = ZBUFFds_read; 4127 if (zbd->outStart + zbd->blockSize > zbd->outBuffSize) 4128 zbd->outStart = zbd->outEnd = 0; 4129 break; 4130 } 4131 /* cannot flush everything */ 4132 notDone = 0; 4133 break; 4134 } 4135 default: return ERROR(GENERIC); /* impossible */ 4136 } } 4137 4138 /* result */ 4139 *srcSizePtr = ip-istart; 4140 *dstCapacityPtr = op-ostart; 4141 { size_t nextSrcSizeHint = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); 4142 if (nextSrcSizeHint > ZSTDv06_blockHeaderSize) nextSrcSizeHint+= ZSTDv06_blockHeaderSize; /* get following block header too */ 4143 nextSrcSizeHint -= zbd->inPos; /* already loaded*/ 4144 return nextSrcSizeHint; 4145 } 4146} 4147 4148 4149 4150/* ************************************* 4151* Tool functions 4152***************************************/ 4153size_t ZBUFFv06_recommendedDInSize(void) { return ZSTDv06_BLOCKSIZE_MAX + ZSTDv06_blockHeaderSize /* block header size*/ ; } 4154size_t ZBUFFv06_recommendedDOutSize(void) { return ZSTDv06_BLOCKSIZE_MAX; } 4155