10c16b537SWarner Losh /* 2*37f1f268SConrad Meyer * Copyright (c) 2016-2020, Yann Collet, Facebook, Inc. 30c16b537SWarner Losh * All rights reserved. 40c16b537SWarner Losh * 50c16b537SWarner Losh * This source code is licensed under both the BSD-style license (found in the 60c16b537SWarner Losh * LICENSE file in the root directory of this source tree) and the GPLv2 (found 70c16b537SWarner Losh * in the COPYING file in the root directory of this source tree). 80c16b537SWarner Losh * You may select, at your option, one of the above-listed licenses. 90c16b537SWarner Losh */ 100c16b537SWarner Losh 110c16b537SWarner Losh 120f743729SConrad Meyer /****************************************** 130f743729SConrad Meyer * Includes 140f743729SConrad Meyer ******************************************/ 150f743729SConrad Meyer #include <stddef.h> /* size_t, ptrdiff_t */ 160f743729SConrad Meyer #include <string.h> /* memcpy */ 170f743729SConrad Meyer 180c16b537SWarner Losh #include "zstd_v04.h" 19*37f1f268SConrad Meyer #include "../common/error_private.h" 200c16b537SWarner Losh 210c16b537SWarner Losh 220c16b537SWarner Losh /* ****************************************************************** 230f743729SConrad Meyer * mem.h 240c16b537SWarner Losh *******************************************************************/ 250c16b537SWarner Losh #ifndef MEM_H_MODULE 260c16b537SWarner Losh #define MEM_H_MODULE 270c16b537SWarner Losh 280c16b537SWarner Losh #if defined (__cplusplus) 290c16b537SWarner Losh extern "C" { 300c16b537SWarner Losh #endif 310c16b537SWarner Losh 320c16b537SWarner Losh 330c16b537SWarner Losh /****************************************** 340c16b537SWarner Losh * Compiler-specific 350c16b537SWarner Losh ******************************************/ 360c16b537SWarner Losh #if defined(_MSC_VER) /* Visual Studio */ 370c16b537SWarner Losh # include <stdlib.h> /* _byteswap_ulong */ 380c16b537SWarner Losh # include <intrin.h> /* _byteswap_* */ 390c16b537SWarner Losh #endif 400c16b537SWarner Losh #if defined(__GNUC__) 410c16b537SWarner Losh # define MEM_STATIC static __attribute__((unused)) 420c16b537SWarner Losh #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 430c16b537SWarner Losh # define MEM_STATIC static inline 440c16b537SWarner Losh #elif defined(_MSC_VER) 450c16b537SWarner Losh # define MEM_STATIC static __inline 460c16b537SWarner Losh #else 470c16b537SWarner Losh # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */ 480c16b537SWarner Losh #endif 490c16b537SWarner Losh 500c16b537SWarner Losh 510c16b537SWarner Losh /**************************************************************** 520c16b537SWarner Losh * Basic Types 530c16b537SWarner Losh *****************************************************************/ 540c16b537SWarner Losh #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 550c16b537SWarner Losh # include <stdint.h> 560c16b537SWarner Losh typedef uint8_t BYTE; 570c16b537SWarner Losh typedef uint16_t U16; 580c16b537SWarner Losh typedef int16_t S16; 590c16b537SWarner Losh typedef uint32_t U32; 600c16b537SWarner Losh typedef int32_t S32; 610c16b537SWarner Losh typedef uint64_t U64; 620c16b537SWarner Losh typedef int64_t S64; 630c16b537SWarner Losh #else 640c16b537SWarner Losh typedef unsigned char BYTE; 650c16b537SWarner Losh typedef unsigned short U16; 660c16b537SWarner Losh typedef signed short S16; 670c16b537SWarner Losh typedef unsigned int U32; 680c16b537SWarner Losh typedef signed int S32; 690c16b537SWarner Losh typedef unsigned long long U64; 700c16b537SWarner Losh typedef signed long long S64; 710c16b537SWarner Losh #endif 720c16b537SWarner Losh 730c16b537SWarner Losh 7419fcbaf1SConrad Meyer /*-************************************* 7519fcbaf1SConrad Meyer * Debug 7619fcbaf1SConrad Meyer ***************************************/ 770f743729SConrad Meyer #include "debug.h" 7819fcbaf1SConrad Meyer #ifndef assert 7919fcbaf1SConrad Meyer # define assert(condition) ((void)0) 8019fcbaf1SConrad Meyer #endif 8119fcbaf1SConrad Meyer 8219fcbaf1SConrad Meyer 830c16b537SWarner Losh /**************************************************************** 840c16b537SWarner Losh * Memory I/O 850c16b537SWarner Losh *****************************************************************/ 860c16b537SWarner Losh /* MEM_FORCE_MEMORY_ACCESS 870c16b537SWarner Losh * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable. 880c16b537SWarner Losh * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal. 890c16b537SWarner Losh * The below switch allow to select different access method for improved performance. 900c16b537SWarner Losh * Method 0 (default) : use `memcpy()`. Safe and portable. 910c16b537SWarner Losh * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable). 920c16b537SWarner Losh * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`. 930c16b537SWarner Losh * Method 2 : direct access. This method is portable but violate C standard. 940c16b537SWarner Losh * It can generate buggy code on targets generating assembly depending on alignment. 950c16b537SWarner Losh * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6) 960c16b537SWarner Losh * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details. 970c16b537SWarner Losh * Prefer these methods in priority order (0 > 1 > 2) 980c16b537SWarner Losh */ 990c16b537SWarner Losh #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */ 1000c16b537SWarner Losh # if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) ) 1010c16b537SWarner Losh # define MEM_FORCE_MEMORY_ACCESS 2 1020c16b537SWarner Losh # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \ 1030c16b537SWarner Losh (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) )) 1040c16b537SWarner Losh # define MEM_FORCE_MEMORY_ACCESS 1 1050c16b537SWarner Losh # endif 1060c16b537SWarner Losh #endif 1070c16b537SWarner Losh 1080c16b537SWarner Losh MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; } 1090c16b537SWarner Losh MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; } 1100c16b537SWarner Losh 1110c16b537SWarner Losh MEM_STATIC unsigned MEM_isLittleEndian(void) 1120c16b537SWarner Losh { 1130c16b537SWarner Losh const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ 1140c16b537SWarner Losh return one.c[0]; 1150c16b537SWarner Losh } 1160c16b537SWarner Losh 1170c16b537SWarner Losh #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2) 1180c16b537SWarner Losh 1190c16b537SWarner Losh /* violates C standard on structure alignment. 1200c16b537SWarner Losh Only use if no other choice to achieve best performance on target platform */ 1210c16b537SWarner Losh MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; } 1220c16b537SWarner Losh MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; } 1230c16b537SWarner Losh MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; } 1240c16b537SWarner Losh 1250c16b537SWarner Losh MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; } 1260c16b537SWarner Losh 1270c16b537SWarner Losh #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1) 1280c16b537SWarner Losh 1290c16b537SWarner Losh /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ 1300c16b537SWarner Losh /* currently only defined for gcc and icc */ 1310c16b537SWarner Losh typedef union { U16 u16; U32 u32; U64 u64; } __attribute__((packed)) unalign; 1320c16b537SWarner Losh 1330c16b537SWarner Losh MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; } 1340c16b537SWarner Losh MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } 1350c16b537SWarner Losh MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; } 1360c16b537SWarner Losh 1370c16b537SWarner Losh MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; } 1380c16b537SWarner Losh 1390c16b537SWarner Losh #else 1400c16b537SWarner Losh 1410c16b537SWarner Losh /* default method, safe and standard. 1420c16b537SWarner Losh can sometimes prove slower */ 1430c16b537SWarner Losh 1440c16b537SWarner Losh MEM_STATIC U16 MEM_read16(const void* memPtr) 1450c16b537SWarner Losh { 1460c16b537SWarner Losh U16 val; memcpy(&val, memPtr, sizeof(val)); return val; 1470c16b537SWarner Losh } 1480c16b537SWarner Losh 1490c16b537SWarner Losh MEM_STATIC U32 MEM_read32(const void* memPtr) 1500c16b537SWarner Losh { 1510c16b537SWarner Losh U32 val; memcpy(&val, memPtr, sizeof(val)); return val; 1520c16b537SWarner Losh } 1530c16b537SWarner Losh 1540c16b537SWarner Losh MEM_STATIC U64 MEM_read64(const void* memPtr) 1550c16b537SWarner Losh { 1560c16b537SWarner Losh U64 val; memcpy(&val, memPtr, sizeof(val)); return val; 1570c16b537SWarner Losh } 1580c16b537SWarner Losh 1590c16b537SWarner Losh MEM_STATIC void MEM_write16(void* memPtr, U16 value) 1600c16b537SWarner Losh { 1610c16b537SWarner Losh memcpy(memPtr, &value, sizeof(value)); 1620c16b537SWarner Losh } 1630c16b537SWarner Losh 164*37f1f268SConrad Meyer #endif /* MEM_FORCE_MEMORY_ACCESS */ 1650c16b537SWarner Losh 1660c16b537SWarner Losh 1670c16b537SWarner Losh MEM_STATIC U16 MEM_readLE16(const void* memPtr) 1680c16b537SWarner Losh { 1690c16b537SWarner Losh if (MEM_isLittleEndian()) 1700c16b537SWarner Losh return MEM_read16(memPtr); 1710c16b537SWarner Losh else 1720c16b537SWarner Losh { 1730c16b537SWarner Losh const BYTE* p = (const BYTE*)memPtr; 1740c16b537SWarner Losh return (U16)(p[0] + (p[1]<<8)); 1750c16b537SWarner Losh } 1760c16b537SWarner Losh } 1770c16b537SWarner Losh 1780c16b537SWarner Losh MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val) 1790c16b537SWarner Losh { 1800c16b537SWarner Losh if (MEM_isLittleEndian()) 1810c16b537SWarner Losh { 1820c16b537SWarner Losh MEM_write16(memPtr, val); 1830c16b537SWarner Losh } 1840c16b537SWarner Losh else 1850c16b537SWarner Losh { 1860c16b537SWarner Losh BYTE* p = (BYTE*)memPtr; 1870c16b537SWarner Losh p[0] = (BYTE)val; 1880c16b537SWarner Losh p[1] = (BYTE)(val>>8); 1890c16b537SWarner Losh } 1900c16b537SWarner Losh } 1910c16b537SWarner Losh 1924d3f1eafSConrad Meyer MEM_STATIC U32 MEM_readLE24(const void* memPtr) 1934d3f1eafSConrad Meyer { 1944d3f1eafSConrad Meyer return MEM_readLE16(memPtr) + (((const BYTE*)memPtr)[2] << 16); 1954d3f1eafSConrad Meyer } 1964d3f1eafSConrad Meyer 1970c16b537SWarner Losh MEM_STATIC U32 MEM_readLE32(const void* memPtr) 1980c16b537SWarner Losh { 1990c16b537SWarner Losh if (MEM_isLittleEndian()) 2000c16b537SWarner Losh return MEM_read32(memPtr); 2010c16b537SWarner Losh else 2020c16b537SWarner Losh { 2030c16b537SWarner Losh const BYTE* p = (const BYTE*)memPtr; 2040c16b537SWarner Losh return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24)); 2050c16b537SWarner Losh } 2060c16b537SWarner Losh } 2070c16b537SWarner Losh 2080c16b537SWarner Losh 2090c16b537SWarner Losh MEM_STATIC U64 MEM_readLE64(const void* memPtr) 2100c16b537SWarner Losh { 2110c16b537SWarner Losh if (MEM_isLittleEndian()) 2120c16b537SWarner Losh return MEM_read64(memPtr); 2130c16b537SWarner Losh else 2140c16b537SWarner Losh { 2150c16b537SWarner Losh const BYTE* p = (const BYTE*)memPtr; 2160c16b537SWarner Losh return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24) 2170c16b537SWarner Losh + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56)); 2180c16b537SWarner Losh } 2190c16b537SWarner Losh } 2200c16b537SWarner Losh 2210c16b537SWarner Losh 2220c16b537SWarner Losh MEM_STATIC size_t MEM_readLEST(const void* memPtr) 2230c16b537SWarner Losh { 2240c16b537SWarner Losh if (MEM_32bits()) 2250c16b537SWarner Losh return (size_t)MEM_readLE32(memPtr); 2260c16b537SWarner Losh else 2270c16b537SWarner Losh return (size_t)MEM_readLE64(memPtr); 2280c16b537SWarner Losh } 2290c16b537SWarner Losh 2300c16b537SWarner Losh 2310c16b537SWarner Losh #if defined (__cplusplus) 2320c16b537SWarner Losh } 2330c16b537SWarner Losh #endif 2340c16b537SWarner Losh 2350c16b537SWarner Losh #endif /* MEM_H_MODULE */ 2360c16b537SWarner Losh 2370c16b537SWarner Losh /* 2380c16b537SWarner Losh zstd - standard compression library 2390c16b537SWarner Losh Header File for static linking only 2400c16b537SWarner Losh */ 2410c16b537SWarner Losh #ifndef ZSTD_STATIC_H 2420c16b537SWarner Losh #define ZSTD_STATIC_H 2430c16b537SWarner Losh 2440c16b537SWarner Losh 2450c16b537SWarner Losh /* ************************************* 2460c16b537SWarner Losh * Types 2470c16b537SWarner Losh ***************************************/ 2480c16b537SWarner Losh #define ZSTD_WINDOWLOG_ABSOLUTEMIN 11 2490c16b537SWarner Losh 2500c16b537SWarner Losh /** from faster to stronger */ 2510c16b537SWarner Losh typedef enum { ZSTD_fast, ZSTD_greedy, ZSTD_lazy, ZSTD_lazy2, ZSTD_btlazy2 } ZSTD_strategy; 2520c16b537SWarner Losh 2530c16b537SWarner Losh typedef struct 2540c16b537SWarner Losh { 2550c16b537SWarner Losh U64 srcSize; /* optional : tells how much bytes are present in the frame. Use 0 if not known. */ 2560c16b537SWarner Losh U32 windowLog; /* largest match distance : larger == more compression, more memory needed during decompression */ 2570c16b537SWarner Losh U32 contentLog; /* full search segment : larger == more compression, slower, more memory (useless for fast) */ 2580c16b537SWarner Losh U32 hashLog; /* dispatch table : larger == more memory, faster */ 2590c16b537SWarner Losh U32 searchLog; /* nb of searches : larger == more compression, slower */ 2600c16b537SWarner Losh U32 searchLength; /* size of matches : larger == faster decompression, sometimes less compression */ 2610c16b537SWarner Losh ZSTD_strategy strategy; 2620c16b537SWarner Losh } ZSTD_parameters; 2630c16b537SWarner Losh 2640c16b537SWarner Losh typedef ZSTDv04_Dctx ZSTD_DCtx; 2650c16b537SWarner Losh 2660c16b537SWarner Losh /* ************************************* 2670c16b537SWarner Losh * Advanced functions 2680c16b537SWarner Losh ***************************************/ 2690c16b537SWarner Losh /** ZSTD_decompress_usingDict 2700c16b537SWarner Losh * Same as ZSTD_decompressDCtx, using a Dictionary content as prefix 2710c16b537SWarner Losh * Note : dict can be NULL, in which case, it's equivalent to ZSTD_decompressDCtx() */ 2720c16b537SWarner Losh static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx, 2730c16b537SWarner Losh void* dst, size_t maxDstSize, 2740c16b537SWarner Losh const void* src, size_t srcSize, 2750c16b537SWarner Losh const void* dict,size_t dictSize); 2760c16b537SWarner Losh 2770c16b537SWarner Losh 2780c16b537SWarner Losh /* ************************************** 2790c16b537SWarner Losh * Streaming functions (direct mode) 2800c16b537SWarner Losh ****************************************/ 2810c16b537SWarner Losh static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx); 2820c16b537SWarner Losh static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize); 2830c16b537SWarner Losh static void ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* src, size_t srcSize); 2840c16b537SWarner Losh 2850c16b537SWarner Losh static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx); 2860c16b537SWarner Losh static size_t ZSTD_decompressContinue(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize); 2870c16b537SWarner Losh 2880c16b537SWarner Losh /** 2890c16b537SWarner Losh Streaming decompression, bufferless mode 2900c16b537SWarner Losh 2910c16b537SWarner Losh A ZSTD_DCtx object is required to track streaming operations. 2920c16b537SWarner Losh Use ZSTD_createDCtx() / ZSTD_freeDCtx() to manage it. 2930c16b537SWarner Losh A ZSTD_DCtx object can be re-used multiple times. Use ZSTD_resetDCtx() to return to fresh status. 2940c16b537SWarner Losh 2950c16b537SWarner Losh First operation is to retrieve frame parameters, using ZSTD_getFrameParams(). 2960c16b537SWarner Losh This function doesn't consume its input. It needs enough input data to properly decode the frame header. 2970c16b537SWarner Losh Objective is to retrieve *params.windowlog, to know minimum amount of memory required during decoding. 2980c16b537SWarner Losh Result : 0 when successful, it means the ZSTD_parameters structure has been filled. 2990c16b537SWarner Losh >0 : means there is not enough data into src. Provides the expected size to successfully decode header. 3000c16b537SWarner Losh errorCode, which can be tested using ZSTD_isError() (For example, if it's not a ZSTD header) 3010c16b537SWarner Losh 3020c16b537SWarner Losh Then, you can optionally insert a dictionary. 3030c16b537SWarner Losh This operation must mimic the compressor behavior, otherwise decompression will fail or be corrupted. 3040c16b537SWarner Losh 3050c16b537SWarner Losh Then it's possible to start decompression. 3060c16b537SWarner Losh Use ZSTD_nextSrcSizeToDecompress() and ZSTD_decompressContinue() alternatively. 3070c16b537SWarner Losh ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue(). 3080c16b537SWarner Losh ZSTD_decompressContinue() requires this exact amount of bytes, or it will fail. 3090c16b537SWarner Losh ZSTD_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog). 3100c16b537SWarner Losh They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible. 3110c16b537SWarner Losh 3120c16b537SWarner Losh @result of ZSTD_decompressContinue() is the number of bytes regenerated within 'dst'. 3130c16b537SWarner Losh It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header. 3140c16b537SWarner Losh 3150c16b537SWarner Losh A frame is fully decoded when ZSTD_nextSrcSizeToDecompress() returns zero. 3160c16b537SWarner Losh Context can then be reset to start a new decompression. 3170c16b537SWarner Losh */ 3180c16b537SWarner Losh 3190c16b537SWarner Losh 3200c16b537SWarner Losh 3210c16b537SWarner Losh 3220c16b537SWarner Losh #endif /* ZSTD_STATIC_H */ 3230c16b537SWarner Losh 3240c16b537SWarner Losh 3250c16b537SWarner Losh /* 3260c16b537SWarner Losh zstd_internal - common functions to include 3270c16b537SWarner Losh Header File for include 3280c16b537SWarner Losh */ 3290c16b537SWarner Losh #ifndef ZSTD_CCOMMON_H_MODULE 3300c16b537SWarner Losh #define ZSTD_CCOMMON_H_MODULE 3310c16b537SWarner Losh 3320c16b537SWarner Losh /* ************************************* 3330c16b537SWarner Losh * Common macros 3340c16b537SWarner Losh ***************************************/ 3350c16b537SWarner Losh #define MIN(a,b) ((a)<(b) ? (a) : (b)) 3360c16b537SWarner Losh #define MAX(a,b) ((a)>(b) ? (a) : (b)) 3370c16b537SWarner Losh 3380c16b537SWarner Losh 3390c16b537SWarner Losh /* ************************************* 3400c16b537SWarner Losh * Common constants 3410c16b537SWarner Losh ***************************************/ 3420c16b537SWarner Losh #define ZSTD_MAGICNUMBER 0xFD2FB524 /* v0.4 */ 3430c16b537SWarner Losh 3440c16b537SWarner Losh #define KB *(1 <<10) 3450c16b537SWarner Losh #define MB *(1 <<20) 3460c16b537SWarner Losh #define GB *(1U<<30) 3470c16b537SWarner Losh 3480c16b537SWarner Losh #define BLOCKSIZE (128 KB) /* define, for static allocation */ 3490c16b537SWarner Losh 3500c16b537SWarner Losh static const size_t ZSTD_blockHeaderSize = 3; 3510c16b537SWarner Losh static const size_t ZSTD_frameHeaderSize_min = 5; 3520c16b537SWarner Losh #define ZSTD_frameHeaderSize_max 5 /* define, for static allocation */ 3530c16b537SWarner Losh 3540c16b537SWarner Losh #define BIT7 128 3550c16b537SWarner Losh #define BIT6 64 3560c16b537SWarner Losh #define BIT5 32 3570c16b537SWarner Losh #define BIT4 16 3580c16b537SWarner Losh #define BIT1 2 3590c16b537SWarner Losh #define BIT0 1 3600c16b537SWarner Losh 3610c16b537SWarner Losh #define IS_RAW BIT0 3620c16b537SWarner Losh #define IS_RLE BIT1 3630c16b537SWarner Losh 3640c16b537SWarner Losh #define MINMATCH 4 3650c16b537SWarner Losh #define REPCODE_STARTVALUE 4 3660c16b537SWarner Losh 3670c16b537SWarner Losh #define MLbits 7 3680c16b537SWarner Losh #define LLbits 6 3690c16b537SWarner Losh #define Offbits 5 3700c16b537SWarner Losh #define MaxML ((1<<MLbits) - 1) 3710c16b537SWarner Losh #define MaxLL ((1<<LLbits) - 1) 3720c16b537SWarner Losh #define MaxOff ((1<<Offbits)- 1) 3730c16b537SWarner Losh #define MLFSELog 10 3740c16b537SWarner Losh #define LLFSELog 10 3750c16b537SWarner Losh #define OffFSELog 9 3760c16b537SWarner Losh #define MaxSeq MAX(MaxLL, MaxML) 3770c16b537SWarner Losh 3780c16b537SWarner Losh #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/) 3790c16b537SWarner Losh #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE) 3800c16b537SWarner Losh 3812b9c00cbSConrad Meyer #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2) 3822b9c00cbSConrad Meyer 3830c16b537SWarner Losh typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t; 3840c16b537SWarner Losh 3850c16b537SWarner Losh 3860c16b537SWarner Losh /* ****************************************** 3870c16b537SWarner Losh * Shared functions to include for inlining 3880c16b537SWarner Losh ********************************************/ 3890c16b537SWarner Losh static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); } 3900c16b537SWarner Losh 3910c16b537SWarner Losh #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; } 3920c16b537SWarner Losh 3930c16b537SWarner Losh /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */ 3940c16b537SWarner Losh static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length) 3950c16b537SWarner Losh { 3960c16b537SWarner Losh const BYTE* ip = (const BYTE*)src; 3970c16b537SWarner Losh BYTE* op = (BYTE*)dst; 3980c16b537SWarner Losh BYTE* const oend = op + length; 3990c16b537SWarner Losh do 4000c16b537SWarner Losh COPY8(op, ip) 4010c16b537SWarner Losh while (op < oend); 4020c16b537SWarner Losh } 4030c16b537SWarner Losh 4040c16b537SWarner Losh 4050c16b537SWarner Losh 4060c16b537SWarner Losh /* ****************************************************************** 4070c16b537SWarner Losh FSE : Finite State Entropy coder 4080c16b537SWarner Losh header file 4090c16b537SWarner Losh ****************************************************************** */ 4100c16b537SWarner Losh #ifndef FSE_H 4110c16b537SWarner Losh #define FSE_H 4120c16b537SWarner Losh 4130c16b537SWarner Losh #if defined (__cplusplus) 4140c16b537SWarner Losh extern "C" { 4150c16b537SWarner Losh #endif 4160c16b537SWarner Losh 4170c16b537SWarner Losh 4180c16b537SWarner Losh /* ***************************************** 4190c16b537SWarner Losh * Includes 4200c16b537SWarner Losh ******************************************/ 4210c16b537SWarner Losh #include <stddef.h> /* size_t, ptrdiff_t */ 4220c16b537SWarner Losh 4230c16b537SWarner Losh 4240c16b537SWarner Losh /* ***************************************** 4250c16b537SWarner Losh * FSE simple functions 4260c16b537SWarner Losh ******************************************/ 4270c16b537SWarner Losh static size_t FSE_decompress(void* dst, size_t maxDstSize, 4280c16b537SWarner Losh const void* cSrc, size_t cSrcSize); 4290c16b537SWarner Losh /*! 4300c16b537SWarner Losh FSE_decompress(): 4310c16b537SWarner Losh Decompress FSE data from buffer 'cSrc', of size 'cSrcSize', 4320c16b537SWarner Losh into already allocated destination buffer 'dst', of size 'maxDstSize'. 4330c16b537SWarner Losh return : size of regenerated data (<= maxDstSize) 4340c16b537SWarner Losh or an error code, which can be tested using FSE_isError() 4350c16b537SWarner Losh 4360c16b537SWarner Losh ** Important ** : FSE_decompress() doesn't decompress non-compressible nor RLE data !!! 4370c16b537SWarner Losh Why ? : making this distinction requires a header. 4380c16b537SWarner Losh Header management is intentionally delegated to the user layer, which can better manage special cases. 4390c16b537SWarner Losh */ 4400c16b537SWarner Losh 4410c16b537SWarner Losh 4420c16b537SWarner Losh /* ***************************************** 4430c16b537SWarner Losh * Tool functions 4440c16b537SWarner Losh ******************************************/ 4450c16b537SWarner Losh /* Error Management */ 4460c16b537SWarner Losh static unsigned FSE_isError(size_t code); /* tells if a return value is an error code */ 4470c16b537SWarner Losh 4480c16b537SWarner Losh 4490c16b537SWarner Losh 4500c16b537SWarner Losh /* ***************************************** 4510c16b537SWarner Losh * FSE detailed API 4520c16b537SWarner Losh ******************************************/ 4530c16b537SWarner Losh /*! 4540c16b537SWarner Losh FSE_compress() does the following: 4550c16b537SWarner Losh 1. count symbol occurrence from source[] into table count[] 4560c16b537SWarner Losh 2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog) 4570c16b537SWarner Losh 3. save normalized counters to memory buffer using writeNCount() 4580c16b537SWarner Losh 4. build encoding table 'CTable' from normalized counters 4590c16b537SWarner Losh 5. encode the data stream using encoding table 'CTable' 4600c16b537SWarner Losh 4610c16b537SWarner Losh FSE_decompress() does the following: 4620c16b537SWarner Losh 1. read normalized counters with readNCount() 4630c16b537SWarner Losh 2. build decoding table 'DTable' from normalized counters 4640c16b537SWarner Losh 3. decode the data stream using decoding table 'DTable' 4650c16b537SWarner Losh 4660c16b537SWarner Losh The following API allows targeting specific sub-functions for advanced tasks. 4670c16b537SWarner Losh For example, it's possible to compress several blocks using the same 'CTable', 4680c16b537SWarner Losh or to save and provide normalized distribution using external method. 4690c16b537SWarner Losh */ 4700c16b537SWarner Losh 4710c16b537SWarner Losh 4720c16b537SWarner Losh /* *** DECOMPRESSION *** */ 4730c16b537SWarner Losh 4740c16b537SWarner Losh /*! 4750c16b537SWarner Losh FSE_readNCount(): 4760c16b537SWarner Losh Read compactly saved 'normalizedCounter' from 'rBuffer'. 4770c16b537SWarner Losh return : size read from 'rBuffer' 4780c16b537SWarner Losh or an errorCode, which can be tested using FSE_isError() 4790c16b537SWarner Losh maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */ 4800c16b537SWarner Losh static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize); 4810c16b537SWarner Losh 4820c16b537SWarner Losh /*! 4830c16b537SWarner Losh Constructor and Destructor of type FSE_DTable 4840c16b537SWarner Losh Note that its size depends on 'tableLog' */ 4850c16b537SWarner Losh typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */ 4860c16b537SWarner Losh 4870c16b537SWarner Losh /*! 4880c16b537SWarner Losh FSE_buildDTable(): 4890c16b537SWarner Losh Builds 'dt', which must be already allocated, using FSE_createDTable() 4900c16b537SWarner Losh return : 0, 4910c16b537SWarner Losh or an errorCode, which can be tested using FSE_isError() */ 4920c16b537SWarner Losh static size_t FSE_buildDTable ( FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog); 4930c16b537SWarner Losh 4940c16b537SWarner Losh /*! 4950c16b537SWarner Losh FSE_decompress_usingDTable(): 4960c16b537SWarner Losh Decompress compressed source 'cSrc' of size 'cSrcSize' using 'dt' 4970c16b537SWarner Losh into 'dst' which must be already allocated. 4980c16b537SWarner Losh return : size of regenerated data (necessarily <= maxDstSize) 4990c16b537SWarner Losh or an errorCode, which can be tested using FSE_isError() */ 5000c16b537SWarner Losh static size_t FSE_decompress_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const FSE_DTable* dt); 5010c16b537SWarner Losh 5020c16b537SWarner Losh /*! 5030c16b537SWarner Losh Tutorial : 5040c16b537SWarner Losh ---------- 5050c16b537SWarner Losh (Note : these functions only decompress FSE-compressed blocks. 5060c16b537SWarner Losh If block is uncompressed, use memcpy() instead 5070c16b537SWarner Losh If block is a single repeated byte, use memset() instead ) 5080c16b537SWarner Losh 5090c16b537SWarner Losh The first step is to obtain the normalized frequencies of symbols. 5100c16b537SWarner Losh This can be performed by FSE_readNCount() if it was saved using FSE_writeNCount(). 5110c16b537SWarner Losh 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short. 5120c16b537SWarner Losh In practice, that means it's necessary to know 'maxSymbolValue' beforehand, 5130c16b537SWarner Losh or size the table to handle worst case situations (typically 256). 5140c16b537SWarner Losh FSE_readNCount() will provide 'tableLog' and 'maxSymbolValue'. 5150c16b537SWarner Losh The result of FSE_readNCount() is the number of bytes read from 'rBuffer'. 5160c16b537SWarner Losh Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that. 5170c16b537SWarner Losh If there is an error, the function will return an error code, which can be tested using FSE_isError(). 5180c16b537SWarner Losh 5190c16b537SWarner Losh The next step is to build the decompression tables 'FSE_DTable' from 'normalizedCounter'. 5200c16b537SWarner Losh This is performed by the function FSE_buildDTable(). 5210c16b537SWarner Losh The space required by 'FSE_DTable' must be already allocated using FSE_createDTable(). 5220c16b537SWarner Losh If there is an error, the function will return an error code, which can be tested using FSE_isError(). 5230c16b537SWarner Losh 5240c16b537SWarner Losh 'FSE_DTable' can then be used to decompress 'cSrc', with FSE_decompress_usingDTable(). 5250c16b537SWarner Losh 'cSrcSize' must be strictly correct, otherwise decompression will fail. 5260c16b537SWarner Losh FSE_decompress_usingDTable() result will tell how many bytes were regenerated (<=maxDstSize). 5270c16b537SWarner Losh If there is an error, the function will return an error code, which can be tested using FSE_isError(). (ex: dst buffer too small) 5280c16b537SWarner Losh */ 5290c16b537SWarner Losh 5300c16b537SWarner Losh 5310c16b537SWarner Losh #if defined (__cplusplus) 5320c16b537SWarner Losh } 5330c16b537SWarner Losh #endif 5340c16b537SWarner Losh 5350c16b537SWarner Losh #endif /* FSE_H */ 5360c16b537SWarner Losh 5370c16b537SWarner Losh 5380c16b537SWarner Losh /* ****************************************************************** 5390c16b537SWarner Losh bitstream 5400c16b537SWarner Losh Part of NewGen Entropy library 5410c16b537SWarner Losh header file (to include) 5420c16b537SWarner Losh Copyright (C) 2013-2015, Yann Collet. 5430c16b537SWarner Losh 5440c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 5450c16b537SWarner Losh 5460c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 5470c16b537SWarner Losh modification, are permitted provided that the following conditions are 5480c16b537SWarner Losh met: 5490c16b537SWarner Losh 5500c16b537SWarner Losh * Redistributions of source code must retain the above copyright 5510c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 5520c16b537SWarner Losh * Redistributions in binary form must reproduce the above 5530c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 5540c16b537SWarner Losh in the documentation and/or other materials provided with the 5550c16b537SWarner Losh distribution. 5560c16b537SWarner Losh 5570c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 5580c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 5590c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 5600c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 5610c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 5620c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 5630c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 5640c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 5650c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 5660c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 5670c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 5680c16b537SWarner Losh 5690c16b537SWarner Losh You can contact the author at : 5700c16b537SWarner Losh - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 5710c16b537SWarner Losh - Public forum : https://groups.google.com/forum/#!forum/lz4c 5720c16b537SWarner Losh ****************************************************************** */ 5730c16b537SWarner Losh #ifndef BITSTREAM_H_MODULE 5740c16b537SWarner Losh #define BITSTREAM_H_MODULE 5750c16b537SWarner Losh 5760c16b537SWarner Losh #if defined (__cplusplus) 5770c16b537SWarner Losh extern "C" { 5780c16b537SWarner Losh #endif 5790c16b537SWarner Losh 5800c16b537SWarner Losh 5810c16b537SWarner Losh /* 5820c16b537SWarner Losh * This API consists of small unitary functions, which highly benefit from being inlined. 5830c16b537SWarner Losh * Since link-time-optimization is not available for all compilers, 5840c16b537SWarner Losh * these functions are defined into a .h to be included. 5850c16b537SWarner Losh */ 5860c16b537SWarner Losh 5870c16b537SWarner Losh /********************************************** 5880c16b537SWarner Losh * bitStream decompression API (read backward) 5890c16b537SWarner Losh **********************************************/ 5900c16b537SWarner Losh typedef struct 5910c16b537SWarner Losh { 5920c16b537SWarner Losh size_t bitContainer; 5930c16b537SWarner Losh unsigned bitsConsumed; 5940c16b537SWarner Losh const char* ptr; 5950c16b537SWarner Losh const char* start; 5960c16b537SWarner Losh } BIT_DStream_t; 5970c16b537SWarner Losh 5980c16b537SWarner Losh typedef enum { BIT_DStream_unfinished = 0, 5990c16b537SWarner Losh BIT_DStream_endOfBuffer = 1, 6000c16b537SWarner Losh BIT_DStream_completed = 2, 6010c16b537SWarner Losh BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */ 6020c16b537SWarner Losh /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */ 6030c16b537SWarner Losh 6040c16b537SWarner Losh MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize); 6050c16b537SWarner Losh MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits); 6060c16b537SWarner Losh MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD); 6070c16b537SWarner Losh MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD); 6080c16b537SWarner Losh 6090c16b537SWarner Losh 6100c16b537SWarner Losh 6110c16b537SWarner Losh 6120c16b537SWarner Losh /****************************************** 6130c16b537SWarner Losh * unsafe API 6140c16b537SWarner Losh ******************************************/ 6150c16b537SWarner Losh MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits); 6160c16b537SWarner Losh /* faster, but works only if nbBits >= 1 */ 6170c16b537SWarner Losh 6180c16b537SWarner Losh 6190c16b537SWarner Losh 6200c16b537SWarner Losh /**************************************************************** 6210c16b537SWarner Losh * Helper functions 6220c16b537SWarner Losh ****************************************************************/ 623052d3c12SConrad Meyer MEM_STATIC unsigned BIT_highbit32 (U32 val) 6240c16b537SWarner Losh { 6250c16b537SWarner Losh # if defined(_MSC_VER) /* Visual */ 6260c16b537SWarner Losh unsigned long r=0; 6270c16b537SWarner Losh _BitScanReverse ( &r, val ); 6280c16b537SWarner Losh return (unsigned) r; 6290c16b537SWarner Losh # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */ 6309cbefe25SConrad Meyer return __builtin_clz (val) ^ 31; 6310c16b537SWarner Losh # else /* Software version */ 6320c16b537SWarner Losh 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 }; 6330c16b537SWarner Losh U32 v = val; 6340c16b537SWarner Losh unsigned r; 6350c16b537SWarner Losh v |= v >> 1; 6360c16b537SWarner Losh v |= v >> 2; 6370c16b537SWarner Losh v |= v >> 4; 6380c16b537SWarner Losh v |= v >> 8; 6390c16b537SWarner Losh v |= v >> 16; 6400c16b537SWarner Losh r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27]; 6410c16b537SWarner Losh return r; 6420c16b537SWarner Losh # endif 6430c16b537SWarner Losh } 6440c16b537SWarner Losh 6450c16b537SWarner Losh 6460c16b537SWarner Losh /********************************************************** 6470c16b537SWarner Losh * bitStream decoding 6480c16b537SWarner Losh **********************************************************/ 6490c16b537SWarner Losh 6500c16b537SWarner Losh /*!BIT_initDStream 6510c16b537SWarner Losh * Initialize a BIT_DStream_t. 6520c16b537SWarner Losh * @bitD : a pointer to an already allocated BIT_DStream_t structure 6530c16b537SWarner Losh * @srcBuffer must point at the beginning of a bitStream 6540c16b537SWarner Losh * @srcSize must be the exact size of the bitStream 6550c16b537SWarner Losh * @result : size of stream (== srcSize) or an errorCode if a problem is detected 6560c16b537SWarner Losh */ 6570c16b537SWarner Losh MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize) 6580c16b537SWarner Losh { 6590c16b537SWarner Losh if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); } 6600c16b537SWarner Losh 6610c16b537SWarner Losh if (srcSize >= sizeof(size_t)) /* normal case */ 6620c16b537SWarner Losh { 6630c16b537SWarner Losh U32 contain32; 6640c16b537SWarner Losh bitD->start = (const char*)srcBuffer; 6650c16b537SWarner Losh bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t); 6660c16b537SWarner Losh bitD->bitContainer = MEM_readLEST(bitD->ptr); 6670c16b537SWarner Losh contain32 = ((const BYTE*)srcBuffer)[srcSize-1]; 6680c16b537SWarner Losh if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */ 6690c16b537SWarner Losh bitD->bitsConsumed = 8 - BIT_highbit32(contain32); 6700c16b537SWarner Losh } 6710c16b537SWarner Losh else 6720c16b537SWarner Losh { 6730c16b537SWarner Losh U32 contain32; 6740c16b537SWarner Losh bitD->start = (const char*)srcBuffer; 6750c16b537SWarner Losh bitD->ptr = bitD->start; 6760c16b537SWarner Losh bitD->bitContainer = *(const BYTE*)(bitD->start); 6770c16b537SWarner Losh switch(srcSize) 6780c16b537SWarner Losh { 6790c16b537SWarner Losh case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);/* fall-through */ 6800c16b537SWarner Losh case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);/* fall-through */ 6810c16b537SWarner Losh case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);/* fall-through */ 6820c16b537SWarner Losh case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24; /* fall-through */ 6830c16b537SWarner Losh case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16; /* fall-through */ 6840c16b537SWarner Losh case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8; /* fall-through */ 6850c16b537SWarner Losh default: break; 6860c16b537SWarner Losh } 6870c16b537SWarner Losh contain32 = ((const BYTE*)srcBuffer)[srcSize-1]; 6880c16b537SWarner Losh if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */ 6890c16b537SWarner Losh bitD->bitsConsumed = 8 - BIT_highbit32(contain32); 6900c16b537SWarner Losh bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8; 6910c16b537SWarner Losh } 6920c16b537SWarner Losh 6930c16b537SWarner Losh return srcSize; 6940c16b537SWarner Losh } 6950c16b537SWarner Losh 6960c16b537SWarner Losh MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits) 6970c16b537SWarner Losh { 6980c16b537SWarner Losh const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1; 6990c16b537SWarner Losh return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask); 7000c16b537SWarner Losh } 7010c16b537SWarner Losh 7020c16b537SWarner Losh /*! BIT_lookBitsFast : 7030c16b537SWarner Losh * unsafe version; only works only if nbBits >= 1 */ 7040c16b537SWarner Losh MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits) 7050c16b537SWarner Losh { 7060c16b537SWarner Losh const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1; 7070c16b537SWarner Losh return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask); 7080c16b537SWarner Losh } 7090c16b537SWarner Losh 7100c16b537SWarner Losh MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits) 7110c16b537SWarner Losh { 7120c16b537SWarner Losh bitD->bitsConsumed += nbBits; 7130c16b537SWarner Losh } 7140c16b537SWarner Losh 7150c16b537SWarner Losh MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits) 7160c16b537SWarner Losh { 7170c16b537SWarner Losh size_t value = BIT_lookBits(bitD, nbBits); 7180c16b537SWarner Losh BIT_skipBits(bitD, nbBits); 7190c16b537SWarner Losh return value; 7200c16b537SWarner Losh } 7210c16b537SWarner Losh 7220c16b537SWarner Losh /*!BIT_readBitsFast : 7230c16b537SWarner Losh * unsafe version; only works only if nbBits >= 1 */ 7240c16b537SWarner Losh MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits) 7250c16b537SWarner Losh { 7260c16b537SWarner Losh size_t value = BIT_lookBitsFast(bitD, nbBits); 7270c16b537SWarner Losh BIT_skipBits(bitD, nbBits); 7280c16b537SWarner Losh return value; 7290c16b537SWarner Losh } 7300c16b537SWarner Losh 7310c16b537SWarner Losh MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD) 7320c16b537SWarner Losh { 7330c16b537SWarner Losh if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */ 7340c16b537SWarner Losh return BIT_DStream_overflow; 7350c16b537SWarner Losh 7360c16b537SWarner Losh if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) 7370c16b537SWarner Losh { 7380c16b537SWarner Losh bitD->ptr -= bitD->bitsConsumed >> 3; 7390c16b537SWarner Losh bitD->bitsConsumed &= 7; 7400c16b537SWarner Losh bitD->bitContainer = MEM_readLEST(bitD->ptr); 7410c16b537SWarner Losh return BIT_DStream_unfinished; 7420c16b537SWarner Losh } 7430c16b537SWarner Losh if (bitD->ptr == bitD->start) 7440c16b537SWarner Losh { 7450c16b537SWarner Losh if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer; 7460c16b537SWarner Losh return BIT_DStream_completed; 7470c16b537SWarner Losh } 7480c16b537SWarner Losh { 7490c16b537SWarner Losh U32 nbBytes = bitD->bitsConsumed >> 3; 7500c16b537SWarner Losh BIT_DStream_status result = BIT_DStream_unfinished; 7510c16b537SWarner Losh if (bitD->ptr - nbBytes < bitD->start) 7520c16b537SWarner Losh { 7530c16b537SWarner Losh nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */ 7540c16b537SWarner Losh result = BIT_DStream_endOfBuffer; 7550c16b537SWarner Losh } 7560c16b537SWarner Losh bitD->ptr -= nbBytes; 7570c16b537SWarner Losh bitD->bitsConsumed -= nbBytes*8; 7580c16b537SWarner Losh bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */ 7590c16b537SWarner Losh return result; 7600c16b537SWarner Losh } 7610c16b537SWarner Losh } 7620c16b537SWarner Losh 7630c16b537SWarner Losh /*! BIT_endOfDStream 7640c16b537SWarner Losh * @return Tells if DStream has reached its exact end 7650c16b537SWarner Losh */ 7660c16b537SWarner Losh MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream) 7670c16b537SWarner Losh { 7680c16b537SWarner Losh return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8)); 7690c16b537SWarner Losh } 7700c16b537SWarner Losh 7710c16b537SWarner Losh #if defined (__cplusplus) 7720c16b537SWarner Losh } 7730c16b537SWarner Losh #endif 7740c16b537SWarner Losh 7750c16b537SWarner Losh #endif /* BITSTREAM_H_MODULE */ 7760c16b537SWarner Losh 7770c16b537SWarner Losh 7780c16b537SWarner Losh 7790c16b537SWarner Losh /* ****************************************************************** 7800c16b537SWarner Losh FSE : Finite State Entropy coder 7810c16b537SWarner Losh header file for static linking (only) 7820c16b537SWarner Losh Copyright (C) 2013-2015, Yann Collet 7830c16b537SWarner Losh 7840c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 7850c16b537SWarner Losh 7860c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 7870c16b537SWarner Losh modification, are permitted provided that the following conditions are 7880c16b537SWarner Losh met: 7890c16b537SWarner Losh 7900c16b537SWarner Losh * Redistributions of source code must retain the above copyright 7910c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 7920c16b537SWarner Losh * Redistributions in binary form must reproduce the above 7930c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 7940c16b537SWarner Losh in the documentation and/or other materials provided with the 7950c16b537SWarner Losh distribution. 7960c16b537SWarner Losh 7970c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 7980c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 7990c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 8000c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 8010c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 8020c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 8030c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 8040c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 8050c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 8060c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 8070c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 8080c16b537SWarner Losh 8090c16b537SWarner Losh You can contact the author at : 8100c16b537SWarner Losh - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 8110c16b537SWarner Losh - Public forum : https://groups.google.com/forum/#!forum/lz4c 8120c16b537SWarner Losh ****************************************************************** */ 8130c16b537SWarner Losh #ifndef FSE_STATIC_H 8140c16b537SWarner Losh #define FSE_STATIC_H 8150c16b537SWarner Losh 8160c16b537SWarner Losh #if defined (__cplusplus) 8170c16b537SWarner Losh extern "C" { 8180c16b537SWarner Losh #endif 8190c16b537SWarner Losh 8200c16b537SWarner Losh 8210c16b537SWarner Losh /* ***************************************** 8220c16b537SWarner Losh * Static allocation 8230c16b537SWarner Losh *******************************************/ 8240c16b537SWarner Losh /* FSE buffer bounds */ 8250c16b537SWarner Losh #define FSE_NCOUNTBOUND 512 8260c16b537SWarner Losh #define FSE_BLOCKBOUND(size) (size + (size>>7)) 8270c16b537SWarner Losh #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ 8280c16b537SWarner Losh 8290c16b537SWarner Losh /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */ 8300c16b537SWarner Losh #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2)) 8310c16b537SWarner Losh #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog)) 8320c16b537SWarner Losh 8330c16b537SWarner Losh 8340c16b537SWarner Losh /* ***************************************** 8350c16b537SWarner Losh * FSE advanced API 8360c16b537SWarner Losh *******************************************/ 8370c16b537SWarner Losh static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits); 8380c16b537SWarner Losh /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */ 8390c16b537SWarner Losh 8400c16b537SWarner Losh static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue); 8410c16b537SWarner Losh /* build a fake FSE_DTable, designed to always generate the same symbolValue */ 8420c16b537SWarner Losh 8430c16b537SWarner Losh 8440c16b537SWarner Losh 8450c16b537SWarner Losh /* ***************************************** 8460c16b537SWarner Losh * FSE symbol decompression API 8470c16b537SWarner Losh *******************************************/ 8480c16b537SWarner Losh typedef struct 8490c16b537SWarner Losh { 8500c16b537SWarner Losh size_t state; 8510c16b537SWarner Losh const void* table; /* precise table may vary, depending on U16 */ 8520c16b537SWarner Losh } FSE_DState_t; 8530c16b537SWarner Losh 8540c16b537SWarner Losh 8550c16b537SWarner Losh static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt); 8560c16b537SWarner Losh 8570c16b537SWarner Losh static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD); 8580c16b537SWarner Losh 8590c16b537SWarner Losh static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr); 8600c16b537SWarner Losh 8610c16b537SWarner Losh 8620c16b537SWarner Losh /* ***************************************** 8630c16b537SWarner Losh * FSE unsafe API 8640c16b537SWarner Losh *******************************************/ 8650c16b537SWarner Losh static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD); 8660c16b537SWarner Losh /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */ 8670c16b537SWarner Losh 8680c16b537SWarner Losh 8690c16b537SWarner Losh /* ***************************************** 8700c16b537SWarner Losh * Implementation of inlined functions 8710c16b537SWarner Losh *******************************************/ 8720c16b537SWarner Losh /* decompression */ 8730c16b537SWarner Losh 8740c16b537SWarner Losh typedef struct { 8750c16b537SWarner Losh U16 tableLog; 8760c16b537SWarner Losh U16 fastMode; 8770c16b537SWarner Losh } FSE_DTableHeader; /* sizeof U32 */ 8780c16b537SWarner Losh 8790c16b537SWarner Losh typedef struct 8800c16b537SWarner Losh { 8810c16b537SWarner Losh unsigned short newState; 8820c16b537SWarner Losh unsigned char symbol; 8830c16b537SWarner Losh unsigned char nbBits; 8840c16b537SWarner Losh } FSE_decode_t; /* size == U32 */ 8850c16b537SWarner Losh 8860c16b537SWarner Losh MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt) 8870c16b537SWarner Losh { 8880c16b537SWarner Losh FSE_DTableHeader DTableH; 8890c16b537SWarner Losh memcpy(&DTableH, dt, sizeof(DTableH)); 8900c16b537SWarner Losh DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog); 8910c16b537SWarner Losh BIT_reloadDStream(bitD); 8920c16b537SWarner Losh DStatePtr->table = dt + 1; 8930c16b537SWarner Losh } 8940c16b537SWarner Losh 8950c16b537SWarner Losh MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) 8960c16b537SWarner Losh { 8970c16b537SWarner Losh const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 8980c16b537SWarner Losh const U32 nbBits = DInfo.nbBits; 8990c16b537SWarner Losh BYTE symbol = DInfo.symbol; 9000c16b537SWarner Losh size_t lowBits = BIT_readBits(bitD, nbBits); 9010c16b537SWarner Losh 9020c16b537SWarner Losh DStatePtr->state = DInfo.newState + lowBits; 9030c16b537SWarner Losh return symbol; 9040c16b537SWarner Losh } 9050c16b537SWarner Losh 9060c16b537SWarner Losh MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) 9070c16b537SWarner Losh { 9080c16b537SWarner Losh const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 9090c16b537SWarner Losh const U32 nbBits = DInfo.nbBits; 9100c16b537SWarner Losh BYTE symbol = DInfo.symbol; 9110c16b537SWarner Losh size_t lowBits = BIT_readBitsFast(bitD, nbBits); 9120c16b537SWarner Losh 9130c16b537SWarner Losh DStatePtr->state = DInfo.newState + lowBits; 9140c16b537SWarner Losh return symbol; 9150c16b537SWarner Losh } 9160c16b537SWarner Losh 9170c16b537SWarner Losh MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr) 9180c16b537SWarner Losh { 9190c16b537SWarner Losh return DStatePtr->state == 0; 9200c16b537SWarner Losh } 9210c16b537SWarner Losh 9220c16b537SWarner Losh 9230c16b537SWarner Losh #if defined (__cplusplus) 9240c16b537SWarner Losh } 9250c16b537SWarner Losh #endif 9260c16b537SWarner Losh 9270c16b537SWarner Losh #endif /* FSE_STATIC_H */ 9280c16b537SWarner Losh 9290c16b537SWarner Losh /* ****************************************************************** 9300c16b537SWarner Losh FSE : Finite State Entropy coder 9310c16b537SWarner Losh Copyright (C) 2013-2015, Yann Collet. 9320c16b537SWarner Losh 9330c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 9340c16b537SWarner Losh 9350c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 9360c16b537SWarner Losh modification, are permitted provided that the following conditions are 9370c16b537SWarner Losh met: 9380c16b537SWarner Losh 9390c16b537SWarner Losh * Redistributions of source code must retain the above copyright 9400c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 9410c16b537SWarner Losh * Redistributions in binary form must reproduce the above 9420c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 9430c16b537SWarner Losh in the documentation and/or other materials provided with the 9440c16b537SWarner Losh distribution. 9450c16b537SWarner Losh 9460c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 9470c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 9480c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 9490c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 9500c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 9510c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 9520c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 9530c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 9540c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 9550c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 9560c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 9570c16b537SWarner Losh 9580c16b537SWarner Losh You can contact the author at : 9590c16b537SWarner Losh - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy 9600c16b537SWarner Losh - Public forum : https://groups.google.com/forum/#!forum/lz4c 9610c16b537SWarner Losh ****************************************************************** */ 9620c16b537SWarner Losh 9630c16b537SWarner Losh #ifndef FSE_COMMONDEFS_ONLY 9640c16b537SWarner Losh 9650c16b537SWarner Losh /* ************************************************************** 9660c16b537SWarner Losh * Tuning parameters 9670c16b537SWarner Losh ****************************************************************/ 9680c16b537SWarner Losh /*!MEMORY_USAGE : 9690c16b537SWarner Losh * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) 9700c16b537SWarner Losh * Increasing memory usage improves compression ratio 9710c16b537SWarner Losh * Reduced memory usage can improve speed, due to cache effect 9720c16b537SWarner Losh * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */ 9730c16b537SWarner Losh #define FSE_MAX_MEMORY_USAGE 14 9740c16b537SWarner Losh #define FSE_DEFAULT_MEMORY_USAGE 13 9750c16b537SWarner Losh 9760c16b537SWarner Losh /*!FSE_MAX_SYMBOL_VALUE : 9770c16b537SWarner Losh * Maximum symbol value authorized. 9780c16b537SWarner Losh * Required for proper stack allocation */ 9790c16b537SWarner Losh #define FSE_MAX_SYMBOL_VALUE 255 9800c16b537SWarner Losh 9810c16b537SWarner Losh 9820c16b537SWarner Losh /* ************************************************************** 9830c16b537SWarner Losh * template functions type & suffix 9840c16b537SWarner Losh ****************************************************************/ 9850c16b537SWarner Losh #define FSE_FUNCTION_TYPE BYTE 9860c16b537SWarner Losh #define FSE_FUNCTION_EXTENSION 9870c16b537SWarner Losh #define FSE_DECODE_TYPE FSE_decode_t 9880c16b537SWarner Losh 9890c16b537SWarner Losh 9900c16b537SWarner Losh #endif /* !FSE_COMMONDEFS_ONLY */ 9910c16b537SWarner Losh 9920c16b537SWarner Losh /* ************************************************************** 9930c16b537SWarner Losh * Compiler specifics 9940c16b537SWarner Losh ****************************************************************/ 9950c16b537SWarner Losh #ifdef _MSC_VER /* Visual Studio */ 9960c16b537SWarner Losh # define FORCE_INLINE static __forceinline 9970c16b537SWarner Losh # include <intrin.h> /* For Visual 2005 */ 9980c16b537SWarner Losh # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 9990c16b537SWarner Losh # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */ 10000c16b537SWarner Losh #else 10010c16b537SWarner Losh # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 10020c16b537SWarner Losh # ifdef __GNUC__ 10030c16b537SWarner Losh # define FORCE_INLINE static inline __attribute__((always_inline)) 10040c16b537SWarner Losh # else 10050c16b537SWarner Losh # define FORCE_INLINE static inline 10060c16b537SWarner Losh # endif 10070c16b537SWarner Losh # else 10080c16b537SWarner Losh # define FORCE_INLINE static 10090c16b537SWarner Losh # endif /* __STDC_VERSION__ */ 10100c16b537SWarner Losh #endif 10110c16b537SWarner Losh 10120c16b537SWarner Losh 10130c16b537SWarner Losh /* ************************************************************** 10140c16b537SWarner Losh * Dependencies 10150c16b537SWarner Losh ****************************************************************/ 10160c16b537SWarner Losh #include <stdlib.h> /* malloc, free, qsort */ 10170c16b537SWarner Losh #include <string.h> /* memcpy, memset */ 10180c16b537SWarner Losh #include <stdio.h> /* printf (debug) */ 10190c16b537SWarner Losh 10200c16b537SWarner Losh 10210c16b537SWarner Losh /* *************************************************************** 10220c16b537SWarner Losh * Constants 10230c16b537SWarner Losh *****************************************************************/ 10240c16b537SWarner Losh #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2) 10250c16b537SWarner Losh #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG) 10260c16b537SWarner Losh #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1) 10270c16b537SWarner Losh #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2) 10280c16b537SWarner Losh #define FSE_MIN_TABLELOG 5 10290c16b537SWarner Losh 10300c16b537SWarner Losh #define FSE_TABLELOG_ABSOLUTE_MAX 15 10310c16b537SWarner Losh #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX 10320c16b537SWarner Losh #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported" 10330c16b537SWarner Losh #endif 10340c16b537SWarner Losh 10350c16b537SWarner Losh 10360c16b537SWarner Losh /* ************************************************************** 10370c16b537SWarner Losh * Error Management 10380c16b537SWarner Losh ****************************************************************/ 10390c16b537SWarner Losh #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 10400c16b537SWarner Losh 10410c16b537SWarner Losh 10420c16b537SWarner Losh /* ************************************************************** 10430c16b537SWarner Losh * Complex types 10440c16b537SWarner Losh ****************************************************************/ 10450c16b537SWarner Losh typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]; 10460c16b537SWarner Losh 10470c16b537SWarner Losh 10480c16b537SWarner Losh /*-************************************************************** 10490c16b537SWarner Losh * Templates 10500c16b537SWarner Losh ****************************************************************/ 10510c16b537SWarner Losh /* 10520c16b537SWarner Losh designed to be included 10530c16b537SWarner Losh for type-specific functions (template emulation in C) 10540c16b537SWarner Losh Objective is to write these functions only once, for improved maintenance 10550c16b537SWarner Losh */ 10560c16b537SWarner Losh 10570c16b537SWarner Losh /* safety checks */ 10580c16b537SWarner Losh #ifndef FSE_FUNCTION_EXTENSION 10590c16b537SWarner Losh # error "FSE_FUNCTION_EXTENSION must be defined" 10600c16b537SWarner Losh #endif 10610c16b537SWarner Losh #ifndef FSE_FUNCTION_TYPE 10620c16b537SWarner Losh # error "FSE_FUNCTION_TYPE must be defined" 10630c16b537SWarner Losh #endif 10640c16b537SWarner Losh 10650c16b537SWarner Losh /* Function names */ 10660c16b537SWarner Losh #define FSE_CAT(X,Y) X##Y 10670c16b537SWarner Losh #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y) 10680c16b537SWarner Losh #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y) 10690c16b537SWarner Losh 10700c16b537SWarner Losh static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; } 10710c16b537SWarner Losh 10720c16b537SWarner Losh 10730c16b537SWarner Losh static size_t FSE_buildDTable(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) 10740c16b537SWarner Losh { 10750c16b537SWarner Losh FSE_DTableHeader DTableH; 10760c16b537SWarner Losh void* const tdPtr = dt+1; /* because dt is unsigned, 32-bits aligned on 32-bits */ 10770c16b537SWarner Losh FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr); 10780c16b537SWarner Losh const U32 tableSize = 1 << tableLog; 10790c16b537SWarner Losh const U32 tableMask = tableSize-1; 10800c16b537SWarner Losh const U32 step = FSE_tableStep(tableSize); 10810c16b537SWarner Losh U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1]; 10820c16b537SWarner Losh U32 position = 0; 10830c16b537SWarner Losh U32 highThreshold = tableSize-1; 10840c16b537SWarner Losh const S16 largeLimit= (S16)(1 << (tableLog-1)); 10850c16b537SWarner Losh U32 noLarge = 1; 10860c16b537SWarner Losh U32 s; 10870c16b537SWarner Losh 10880c16b537SWarner Losh /* Sanity Checks */ 10890c16b537SWarner Losh if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge); 10900c16b537SWarner Losh if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); 10910c16b537SWarner Losh 10920c16b537SWarner Losh /* Init, lay down lowprob symbols */ 10930f743729SConrad Meyer memset(tableDecode, 0, sizeof(FSE_DECODE_TYPE) * (maxSymbolValue+1) ); /* useless init, but keep static analyzer happy, and we don't need to performance optimize legacy decoders */ 10940c16b537SWarner Losh DTableH.tableLog = (U16)tableLog; 10950c16b537SWarner Losh for (s=0; s<=maxSymbolValue; s++) 10960c16b537SWarner Losh { 10970c16b537SWarner Losh if (normalizedCounter[s]==-1) 10980c16b537SWarner Losh { 10990c16b537SWarner Losh tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s; 11000c16b537SWarner Losh symbolNext[s] = 1; 11010c16b537SWarner Losh } 11020c16b537SWarner Losh else 11030c16b537SWarner Losh { 11040c16b537SWarner Losh if (normalizedCounter[s] >= largeLimit) noLarge=0; 11050c16b537SWarner Losh symbolNext[s] = normalizedCounter[s]; 11060c16b537SWarner Losh } 11070c16b537SWarner Losh } 11080c16b537SWarner Losh 11090c16b537SWarner Losh /* Spread symbols */ 11100c16b537SWarner Losh for (s=0; s<=maxSymbolValue; s++) 11110c16b537SWarner Losh { 11120c16b537SWarner Losh int i; 11130c16b537SWarner Losh for (i=0; i<normalizedCounter[s]; i++) 11140c16b537SWarner Losh { 11150c16b537SWarner Losh tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s; 11160c16b537SWarner Losh position = (position + step) & tableMask; 11170c16b537SWarner Losh while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */ 11180c16b537SWarner Losh } 11190c16b537SWarner Losh } 11200c16b537SWarner Losh 11210c16b537SWarner Losh if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ 11220c16b537SWarner Losh 11230c16b537SWarner Losh /* Build Decoding table */ 11240c16b537SWarner Losh { 11250c16b537SWarner Losh U32 i; 11260c16b537SWarner Losh for (i=0; i<tableSize; i++) 11270c16b537SWarner Losh { 11280c16b537SWarner Losh FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol); 11290c16b537SWarner Losh U16 nextState = symbolNext[symbol]++; 11300c16b537SWarner Losh tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) ); 11310c16b537SWarner Losh tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize); 11320c16b537SWarner Losh } 11330c16b537SWarner Losh } 11340c16b537SWarner Losh 11350c16b537SWarner Losh DTableH.fastMode = (U16)noLarge; 11360c16b537SWarner Losh memcpy(dt, &DTableH, sizeof(DTableH)); 11370c16b537SWarner Losh return 0; 11380c16b537SWarner Losh } 11390c16b537SWarner Losh 11400c16b537SWarner Losh 11410c16b537SWarner Losh #ifndef FSE_COMMONDEFS_ONLY 11420c16b537SWarner Losh /****************************************** 11430c16b537SWarner Losh * FSE helper functions 11440c16b537SWarner Losh ******************************************/ 11450c16b537SWarner Losh static unsigned FSE_isError(size_t code) { return ERR_isError(code); } 11460c16b537SWarner Losh 11470c16b537SWarner Losh 11480c16b537SWarner Losh /**************************************************************** 11490c16b537SWarner Losh * FSE NCount encoding-decoding 11500c16b537SWarner Losh ****************************************************************/ 11510c16b537SWarner Losh static short FSE_abs(short a) 11520c16b537SWarner Losh { 11530c16b537SWarner Losh return a<0 ? -a : a; 11540c16b537SWarner Losh } 11550c16b537SWarner Losh 11560c16b537SWarner Losh static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr, 11570c16b537SWarner Losh const void* headerBuffer, size_t hbSize) 11580c16b537SWarner Losh { 11590c16b537SWarner Losh const BYTE* const istart = (const BYTE*) headerBuffer; 11600c16b537SWarner Losh const BYTE* const iend = istart + hbSize; 11610c16b537SWarner Losh const BYTE* ip = istart; 11620c16b537SWarner Losh int nbBits; 11630c16b537SWarner Losh int remaining; 11640c16b537SWarner Losh int threshold; 11650c16b537SWarner Losh U32 bitStream; 11660c16b537SWarner Losh int bitCount; 11670c16b537SWarner Losh unsigned charnum = 0; 11680c16b537SWarner Losh int previous0 = 0; 11690c16b537SWarner Losh 11700c16b537SWarner Losh if (hbSize < 4) return ERROR(srcSize_wrong); 11710c16b537SWarner Losh bitStream = MEM_readLE32(ip); 11720c16b537SWarner Losh nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */ 11730c16b537SWarner Losh if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge); 11740c16b537SWarner Losh bitStream >>= 4; 11750c16b537SWarner Losh bitCount = 4; 11760c16b537SWarner Losh *tableLogPtr = nbBits; 11770c16b537SWarner Losh remaining = (1<<nbBits)+1; 11780c16b537SWarner Losh threshold = 1<<nbBits; 11790c16b537SWarner Losh nbBits++; 11800c16b537SWarner Losh 11810c16b537SWarner Losh while ((remaining>1) && (charnum<=*maxSVPtr)) 11820c16b537SWarner Losh { 11830c16b537SWarner Losh if (previous0) 11840c16b537SWarner Losh { 11850c16b537SWarner Losh unsigned n0 = charnum; 11860c16b537SWarner Losh while ((bitStream & 0xFFFF) == 0xFFFF) 11870c16b537SWarner Losh { 11880c16b537SWarner Losh n0+=24; 11890c16b537SWarner Losh if (ip < iend-5) 11900c16b537SWarner Losh { 11910c16b537SWarner Losh ip+=2; 11920c16b537SWarner Losh bitStream = MEM_readLE32(ip) >> bitCount; 11930c16b537SWarner Losh } 11940c16b537SWarner Losh else 11950c16b537SWarner Losh { 11960c16b537SWarner Losh bitStream >>= 16; 11970c16b537SWarner Losh bitCount+=16; 11980c16b537SWarner Losh } 11990c16b537SWarner Losh } 12000c16b537SWarner Losh while ((bitStream & 3) == 3) 12010c16b537SWarner Losh { 12020c16b537SWarner Losh n0+=3; 12030c16b537SWarner Losh bitStream>>=2; 12040c16b537SWarner Losh bitCount+=2; 12050c16b537SWarner Losh } 12060c16b537SWarner Losh n0 += bitStream & 3; 12070c16b537SWarner Losh bitCount += 2; 12080c16b537SWarner Losh if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall); 12090c16b537SWarner Losh while (charnum < n0) normalizedCounter[charnum++] = 0; 12100c16b537SWarner Losh if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) 12110c16b537SWarner Losh { 12120c16b537SWarner Losh ip += bitCount>>3; 12130c16b537SWarner Losh bitCount &= 7; 12140c16b537SWarner Losh bitStream = MEM_readLE32(ip) >> bitCount; 12150c16b537SWarner Losh } 12160c16b537SWarner Losh else 12170c16b537SWarner Losh bitStream >>= 2; 12180c16b537SWarner Losh } 12190c16b537SWarner Losh { 12200c16b537SWarner Losh const short max = (short)((2*threshold-1)-remaining); 12210c16b537SWarner Losh short count; 12220c16b537SWarner Losh 12230c16b537SWarner Losh if ((bitStream & (threshold-1)) < (U32)max) 12240c16b537SWarner Losh { 12250c16b537SWarner Losh count = (short)(bitStream & (threshold-1)); 12260c16b537SWarner Losh bitCount += nbBits-1; 12270c16b537SWarner Losh } 12280c16b537SWarner Losh else 12290c16b537SWarner Losh { 12300c16b537SWarner Losh count = (short)(bitStream & (2*threshold-1)); 12310c16b537SWarner Losh if (count >= threshold) count -= max; 12320c16b537SWarner Losh bitCount += nbBits; 12330c16b537SWarner Losh } 12340c16b537SWarner Losh 12350c16b537SWarner Losh count--; /* extra accuracy */ 12360c16b537SWarner Losh remaining -= FSE_abs(count); 12370c16b537SWarner Losh normalizedCounter[charnum++] = count; 12380c16b537SWarner Losh previous0 = !count; 12390c16b537SWarner Losh while (remaining < threshold) 12400c16b537SWarner Losh { 12410c16b537SWarner Losh nbBits--; 12420c16b537SWarner Losh threshold >>= 1; 12430c16b537SWarner Losh } 12440c16b537SWarner Losh 12450c16b537SWarner Losh { 12460c16b537SWarner Losh if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) 12470c16b537SWarner Losh { 12480c16b537SWarner Losh ip += bitCount>>3; 12490c16b537SWarner Losh bitCount &= 7; 12500c16b537SWarner Losh } 12510c16b537SWarner Losh else 12520c16b537SWarner Losh { 12530c16b537SWarner Losh bitCount -= (int)(8 * (iend - 4 - ip)); 12540c16b537SWarner Losh ip = iend - 4; 12550c16b537SWarner Losh } 12560c16b537SWarner Losh bitStream = MEM_readLE32(ip) >> (bitCount & 31); 12570c16b537SWarner Losh } 12580c16b537SWarner Losh } 12590c16b537SWarner Losh } 12600c16b537SWarner Losh if (remaining != 1) return ERROR(GENERIC); 12610c16b537SWarner Losh *maxSVPtr = charnum-1; 12620c16b537SWarner Losh 12630c16b537SWarner Losh ip += (bitCount+7)>>3; 12640c16b537SWarner Losh if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong); 12650c16b537SWarner Losh return ip-istart; 12660c16b537SWarner Losh } 12670c16b537SWarner Losh 12680c16b537SWarner Losh 12690c16b537SWarner Losh /********************************************************* 12700c16b537SWarner Losh * Decompression (Byte symbols) 12710c16b537SWarner Losh *********************************************************/ 12720c16b537SWarner Losh static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue) 12730c16b537SWarner Losh { 12740c16b537SWarner Losh void* ptr = dt; 12750c16b537SWarner Losh FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 12760c16b537SWarner Losh void* dPtr = dt + 1; 12770c16b537SWarner Losh FSE_decode_t* const cell = (FSE_decode_t*)dPtr; 12780c16b537SWarner Losh 12790c16b537SWarner Losh DTableH->tableLog = 0; 12800c16b537SWarner Losh DTableH->fastMode = 0; 12810c16b537SWarner Losh 12820c16b537SWarner Losh cell->newState = 0; 12830c16b537SWarner Losh cell->symbol = symbolValue; 12840c16b537SWarner Losh cell->nbBits = 0; 12850c16b537SWarner Losh 12860c16b537SWarner Losh return 0; 12870c16b537SWarner Losh } 12880c16b537SWarner Losh 12890c16b537SWarner Losh 12900c16b537SWarner Losh static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits) 12910c16b537SWarner Losh { 12920c16b537SWarner Losh void* ptr = dt; 12930c16b537SWarner Losh FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 12940c16b537SWarner Losh void* dPtr = dt + 1; 12950c16b537SWarner Losh FSE_decode_t* const dinfo = (FSE_decode_t*)dPtr; 12960c16b537SWarner Losh const unsigned tableSize = 1 << nbBits; 12970c16b537SWarner Losh const unsigned tableMask = tableSize - 1; 12980c16b537SWarner Losh const unsigned maxSymbolValue = tableMask; 12990c16b537SWarner Losh unsigned s; 13000c16b537SWarner Losh 13010c16b537SWarner Losh /* Sanity checks */ 13020c16b537SWarner Losh if (nbBits < 1) return ERROR(GENERIC); /* min size */ 13030c16b537SWarner Losh 13040c16b537SWarner Losh /* Build Decoding Table */ 13050c16b537SWarner Losh DTableH->tableLog = (U16)nbBits; 13060c16b537SWarner Losh DTableH->fastMode = 1; 13070c16b537SWarner Losh for (s=0; s<=maxSymbolValue; s++) 13080c16b537SWarner Losh { 13090c16b537SWarner Losh dinfo[s].newState = 0; 13100c16b537SWarner Losh dinfo[s].symbol = (BYTE)s; 13110c16b537SWarner Losh dinfo[s].nbBits = (BYTE)nbBits; 13120c16b537SWarner Losh } 13130c16b537SWarner Losh 13140c16b537SWarner Losh return 0; 13150c16b537SWarner Losh } 13160c16b537SWarner Losh 13170c16b537SWarner Losh FORCE_INLINE size_t FSE_decompress_usingDTable_generic( 13180c16b537SWarner Losh void* dst, size_t maxDstSize, 13190c16b537SWarner Losh const void* cSrc, size_t cSrcSize, 13200c16b537SWarner Losh const FSE_DTable* dt, const unsigned fast) 13210c16b537SWarner Losh { 13220c16b537SWarner Losh BYTE* const ostart = (BYTE*) dst; 13230c16b537SWarner Losh BYTE* op = ostart; 13240c16b537SWarner Losh BYTE* const omax = op + maxDstSize; 13250c16b537SWarner Losh BYTE* const olimit = omax-3; 13260c16b537SWarner Losh 13270c16b537SWarner Losh BIT_DStream_t bitD; 13280c16b537SWarner Losh FSE_DState_t state1; 13290c16b537SWarner Losh FSE_DState_t state2; 13300c16b537SWarner Losh size_t errorCode; 13310c16b537SWarner Losh 13320c16b537SWarner Losh /* Init */ 13330c16b537SWarner Losh errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */ 13340c16b537SWarner Losh if (FSE_isError(errorCode)) return errorCode; 13350c16b537SWarner Losh 13360c16b537SWarner Losh FSE_initDState(&state1, &bitD, dt); 13370c16b537SWarner Losh FSE_initDState(&state2, &bitD, dt); 13380c16b537SWarner Losh 13390c16b537SWarner Losh #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD) 13400c16b537SWarner Losh 13410c16b537SWarner Losh /* 4 symbols per loop */ 13420c16b537SWarner Losh for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4) 13430c16b537SWarner Losh { 13440c16b537SWarner Losh op[0] = FSE_GETSYMBOL(&state1); 13450c16b537SWarner Losh 13460c16b537SWarner Losh if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 13470c16b537SWarner Losh BIT_reloadDStream(&bitD); 13480c16b537SWarner Losh 13490c16b537SWarner Losh op[1] = FSE_GETSYMBOL(&state2); 13500c16b537SWarner Losh 13510c16b537SWarner Losh if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 13520c16b537SWarner Losh { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } } 13530c16b537SWarner Losh 13540c16b537SWarner Losh op[2] = FSE_GETSYMBOL(&state1); 13550c16b537SWarner Losh 13560c16b537SWarner Losh if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 13570c16b537SWarner Losh BIT_reloadDStream(&bitD); 13580c16b537SWarner Losh 13590c16b537SWarner Losh op[3] = FSE_GETSYMBOL(&state2); 13600c16b537SWarner Losh } 13610c16b537SWarner Losh 13620c16b537SWarner Losh /* tail */ 13630c16b537SWarner Losh /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */ 13640c16b537SWarner Losh while (1) 13650c16b537SWarner Losh { 13660c16b537SWarner Losh if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) ) 13670c16b537SWarner Losh break; 13680c16b537SWarner Losh 13690c16b537SWarner Losh *op++ = FSE_GETSYMBOL(&state1); 13700c16b537SWarner Losh 13710c16b537SWarner Losh if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) ) 13720c16b537SWarner Losh break; 13730c16b537SWarner Losh 13740c16b537SWarner Losh *op++ = FSE_GETSYMBOL(&state2); 13750c16b537SWarner Losh } 13760c16b537SWarner Losh 13770c16b537SWarner Losh /* end ? */ 13780c16b537SWarner Losh if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2)) 13790c16b537SWarner Losh return op-ostart; 13800c16b537SWarner Losh 13810c16b537SWarner Losh if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */ 13820c16b537SWarner Losh 13830c16b537SWarner Losh return ERROR(corruption_detected); 13840c16b537SWarner Losh } 13850c16b537SWarner Losh 13860c16b537SWarner Losh 13870c16b537SWarner Losh static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize, 13880c16b537SWarner Losh const void* cSrc, size_t cSrcSize, 13890c16b537SWarner Losh const FSE_DTable* dt) 13900c16b537SWarner Losh { 13910c16b537SWarner Losh FSE_DTableHeader DTableH; 13920c16b537SWarner Losh U32 fastMode; 13930c16b537SWarner Losh 13940c16b537SWarner Losh memcpy(&DTableH, dt, sizeof(DTableH)); 13950c16b537SWarner Losh fastMode = DTableH.fastMode; 13960c16b537SWarner Losh 13970c16b537SWarner Losh /* select fast mode (static) */ 13980c16b537SWarner Losh if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1); 13990c16b537SWarner Losh return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0); 14000c16b537SWarner Losh } 14010c16b537SWarner Losh 14020c16b537SWarner Losh 14030c16b537SWarner Losh static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize) 14040c16b537SWarner Losh { 14050c16b537SWarner Losh const BYTE* const istart = (const BYTE*)cSrc; 14060c16b537SWarner Losh const BYTE* ip = istart; 14070c16b537SWarner Losh short counting[FSE_MAX_SYMBOL_VALUE+1]; 14080c16b537SWarner Losh DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */ 14090c16b537SWarner Losh unsigned tableLog; 14100c16b537SWarner Losh unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE; 14110c16b537SWarner Losh size_t errorCode; 14120c16b537SWarner Losh 14130c16b537SWarner Losh if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */ 14140c16b537SWarner Losh 14150c16b537SWarner Losh /* normal FSE decoding mode */ 14160c16b537SWarner Losh errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize); 14170c16b537SWarner Losh if (FSE_isError(errorCode)) return errorCode; 14180c16b537SWarner Losh if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */ 14190c16b537SWarner Losh ip += errorCode; 14200c16b537SWarner Losh cSrcSize -= errorCode; 14210c16b537SWarner Losh 14220c16b537SWarner Losh errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog); 14230c16b537SWarner Losh if (FSE_isError(errorCode)) return errorCode; 14240c16b537SWarner Losh 14250c16b537SWarner Losh /* always return, even if it is an error code */ 14260c16b537SWarner Losh return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); 14270c16b537SWarner Losh } 14280c16b537SWarner Losh 14290c16b537SWarner Losh 14300c16b537SWarner Losh 14310c16b537SWarner Losh #endif /* FSE_COMMONDEFS_ONLY */ 14320c16b537SWarner Losh 14330c16b537SWarner Losh 14340c16b537SWarner Losh /* ****************************************************************** 14350c16b537SWarner Losh Huff0 : Huffman coder, part of New Generation Entropy library 14360c16b537SWarner Losh header file 14370c16b537SWarner Losh Copyright (C) 2013-2015, Yann Collet. 14380c16b537SWarner Losh 14390c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 14400c16b537SWarner Losh 14410c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 14420c16b537SWarner Losh modification, are permitted provided that the following conditions are 14430c16b537SWarner Losh met: 14440c16b537SWarner Losh 14450c16b537SWarner Losh * Redistributions of source code must retain the above copyright 14460c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 14470c16b537SWarner Losh * Redistributions in binary form must reproduce the above 14480c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 14490c16b537SWarner Losh in the documentation and/or other materials provided with the 14500c16b537SWarner Losh distribution. 14510c16b537SWarner Losh 14520c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 14530c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 14540c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 14550c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 14560c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 14570c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 14580c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 14590c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 14600c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 14610c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 14620c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 14630c16b537SWarner Losh 14640c16b537SWarner Losh You can contact the author at : 14650c16b537SWarner Losh - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 14660c16b537SWarner Losh - Public forum : https://groups.google.com/forum/#!forum/lz4c 14670c16b537SWarner Losh ****************************************************************** */ 14680c16b537SWarner Losh #ifndef HUFF0_H 14690c16b537SWarner Losh #define HUFF0_H 14700c16b537SWarner Losh 14710c16b537SWarner Losh #if defined (__cplusplus) 14720c16b537SWarner Losh extern "C" { 14730c16b537SWarner Losh #endif 14740c16b537SWarner Losh 14750c16b537SWarner Losh 14760c16b537SWarner Losh /* **************************************** 14770c16b537SWarner Losh * Dependency 14780c16b537SWarner Losh ******************************************/ 14790c16b537SWarner Losh #include <stddef.h> /* size_t */ 14800c16b537SWarner Losh 14810c16b537SWarner Losh 14820c16b537SWarner Losh /* **************************************** 14830c16b537SWarner Losh * Huff0 simple functions 14840c16b537SWarner Losh ******************************************/ 14850c16b537SWarner Losh static size_t HUF_decompress(void* dst, size_t dstSize, 14860c16b537SWarner Losh const void* cSrc, size_t cSrcSize); 14870c16b537SWarner Losh /*! 14880c16b537SWarner Losh HUF_decompress(): 14890c16b537SWarner Losh Decompress Huff0 data from buffer 'cSrc', of size 'cSrcSize', 14900c16b537SWarner Losh into already allocated destination buffer 'dst', of size 'dstSize'. 14910c16b537SWarner Losh 'dstSize' must be the exact size of original (uncompressed) data. 14920c16b537SWarner Losh Note : in contrast with FSE, HUF_decompress can regenerate RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, because it knows size to regenerate. 14930c16b537SWarner Losh @return : size of regenerated data (== dstSize) 14940c16b537SWarner Losh or an error code, which can be tested using HUF_isError() 14950c16b537SWarner Losh */ 14960c16b537SWarner Losh 14970c16b537SWarner Losh 14980c16b537SWarner Losh /* **************************************** 14990c16b537SWarner Losh * Tool functions 15000c16b537SWarner Losh ******************************************/ 15010c16b537SWarner Losh /* Error Management */ 15020c16b537SWarner Losh static unsigned HUF_isError(size_t code); /* tells if a return value is an error code */ 15030c16b537SWarner Losh 15040c16b537SWarner Losh 15050c16b537SWarner Losh #if defined (__cplusplus) 15060c16b537SWarner Losh } 15070c16b537SWarner Losh #endif 15080c16b537SWarner Losh 15090c16b537SWarner Losh #endif /* HUFF0_H */ 15100c16b537SWarner Losh 15110c16b537SWarner Losh 15120c16b537SWarner Losh /* ****************************************************************** 15130c16b537SWarner Losh Huff0 : Huffman coder, part of New Generation Entropy library 15140c16b537SWarner Losh header file for static linking (only) 15150c16b537SWarner Losh Copyright (C) 2013-2015, Yann Collet 15160c16b537SWarner Losh 15170c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 15180c16b537SWarner Losh 15190c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 15200c16b537SWarner Losh modification, are permitted provided that the following conditions are 15210c16b537SWarner Losh met: 15220c16b537SWarner Losh 15230c16b537SWarner Losh * Redistributions of source code must retain the above copyright 15240c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 15250c16b537SWarner Losh * Redistributions in binary form must reproduce the above 15260c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 15270c16b537SWarner Losh in the documentation and/or other materials provided with the 15280c16b537SWarner Losh distribution. 15290c16b537SWarner Losh 15300c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 15310c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 15320c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 15330c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 15340c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 15350c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 15360c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 15370c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 15380c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 15390c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 15400c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 15410c16b537SWarner Losh 15420c16b537SWarner Losh You can contact the author at : 15430c16b537SWarner Losh - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 15440c16b537SWarner Losh - Public forum : https://groups.google.com/forum/#!forum/lz4c 15450c16b537SWarner Losh ****************************************************************** */ 15460c16b537SWarner Losh #ifndef HUFF0_STATIC_H 15470c16b537SWarner Losh #define HUFF0_STATIC_H 15480c16b537SWarner Losh 15490c16b537SWarner Losh #if defined (__cplusplus) 15500c16b537SWarner Losh extern "C" { 15510c16b537SWarner Losh #endif 15520c16b537SWarner Losh 15530c16b537SWarner Losh 15540c16b537SWarner Losh 15550c16b537SWarner Losh /* **************************************** 15560c16b537SWarner Losh * Static allocation macros 15570c16b537SWarner Losh ******************************************/ 15580c16b537SWarner Losh /* static allocation of Huff0's DTable */ 15590c16b537SWarner Losh #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */ 15600c16b537SWarner Losh #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \ 15610c16b537SWarner Losh unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 15620c16b537SWarner Losh #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \ 15630c16b537SWarner Losh unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 15640c16b537SWarner Losh #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \ 15650c16b537SWarner Losh unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog } 15660c16b537SWarner Losh 15670c16b537SWarner Losh 15680c16b537SWarner Losh /* **************************************** 15690c16b537SWarner Losh * Advanced decompression functions 15700c16b537SWarner Losh ******************************************/ 15710c16b537SWarner Losh static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ 15720c16b537SWarner Losh static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */ 15730c16b537SWarner Losh 15740c16b537SWarner Losh 15750c16b537SWarner Losh /* **************************************** 15760c16b537SWarner Losh * Huff0 detailed API 15770c16b537SWarner Losh ******************************************/ 15780c16b537SWarner Losh /*! 15790c16b537SWarner Losh HUF_decompress() does the following: 15800c16b537SWarner Losh 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics 15810c16b537SWarner Losh 2. build Huffman table from save, using HUF_readDTableXn() 15820c16b537SWarner Losh 3. decode 1 or 4 segments in parallel using HUF_decompressSXn_usingDTable 15830c16b537SWarner Losh 15840c16b537SWarner Losh */ 15850c16b537SWarner Losh static size_t HUF_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize); 15860c16b537SWarner Losh static size_t HUF_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize); 15870c16b537SWarner Losh 15880c16b537SWarner Losh static size_t HUF_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable); 15890c16b537SWarner Losh static size_t HUF_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable); 15900c16b537SWarner Losh 15910c16b537SWarner Losh 15920c16b537SWarner Losh #if defined (__cplusplus) 15930c16b537SWarner Losh } 15940c16b537SWarner Losh #endif 15950c16b537SWarner Losh 15960c16b537SWarner Losh #endif /* HUFF0_STATIC_H */ 15970c16b537SWarner Losh 15980c16b537SWarner Losh 15990c16b537SWarner Losh 16000c16b537SWarner Losh /* ****************************************************************** 16010c16b537SWarner Losh Huff0 : Huffman coder, part of New Generation Entropy library 16020c16b537SWarner Losh Copyright (C) 2013-2015, Yann Collet. 16030c16b537SWarner Losh 16040c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 16050c16b537SWarner Losh 16060c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 16070c16b537SWarner Losh modification, are permitted provided that the following conditions are 16080c16b537SWarner Losh met: 16090c16b537SWarner Losh 16100c16b537SWarner Losh * Redistributions of source code must retain the above copyright 16110c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 16120c16b537SWarner Losh * Redistributions in binary form must reproduce the above 16130c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 16140c16b537SWarner Losh in the documentation and/or other materials provided with the 16150c16b537SWarner Losh distribution. 16160c16b537SWarner Losh 16170c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 16180c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 16190c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 16200c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 16210c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 16220c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 16230c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 16240c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 16250c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 16260c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 16270c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 16280c16b537SWarner Losh 16290c16b537SWarner Losh You can contact the author at : 16300c16b537SWarner Losh - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy 16310c16b537SWarner Losh ****************************************************************** */ 16320c16b537SWarner Losh 16330c16b537SWarner Losh /* ************************************************************** 16340c16b537SWarner Losh * Compiler specifics 16350c16b537SWarner Losh ****************************************************************/ 16360c16b537SWarner Losh #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 16370c16b537SWarner Losh /* inline is defined */ 16380c16b537SWarner Losh #elif defined(_MSC_VER) 16390c16b537SWarner Losh # define inline __inline 16400c16b537SWarner Losh #else 16410c16b537SWarner Losh # define inline /* disable inline */ 16420c16b537SWarner Losh #endif 16430c16b537SWarner Losh 16440c16b537SWarner Losh 16450c16b537SWarner Losh #ifdef _MSC_VER /* Visual Studio */ 16460c16b537SWarner Losh # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 16470c16b537SWarner Losh #endif 16480c16b537SWarner Losh 16490c16b537SWarner Losh 16500c16b537SWarner Losh /* ************************************************************** 16510c16b537SWarner Losh * Includes 16520c16b537SWarner Losh ****************************************************************/ 16530c16b537SWarner Losh #include <stdlib.h> /* malloc, free, qsort */ 16540c16b537SWarner Losh #include <string.h> /* memcpy, memset */ 16550c16b537SWarner Losh #include <stdio.h> /* printf (debug) */ 16560c16b537SWarner Losh 16570c16b537SWarner Losh 16580c16b537SWarner Losh /* ************************************************************** 16590c16b537SWarner Losh * Constants 16600c16b537SWarner Losh ****************************************************************/ 16610c16b537SWarner Losh #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */ 16620c16b537SWarner Losh #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */ 16630c16b537SWarner Losh #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */ 16640c16b537SWarner Losh #define HUF_MAX_SYMBOL_VALUE 255 16650c16b537SWarner Losh #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG) 16660c16b537SWarner Losh # error "HUF_MAX_TABLELOG is too large !" 16670c16b537SWarner Losh #endif 16680c16b537SWarner Losh 16690c16b537SWarner Losh 16700c16b537SWarner Losh /* ************************************************************** 16710c16b537SWarner Losh * Error Management 16720c16b537SWarner Losh ****************************************************************/ 16730c16b537SWarner Losh static unsigned HUF_isError(size_t code) { return ERR_isError(code); } 16740c16b537SWarner Losh #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 16750c16b537SWarner Losh 16760c16b537SWarner Losh 16770c16b537SWarner Losh 16780c16b537SWarner Losh /*-******************************************************* 16790c16b537SWarner Losh * Huff0 : Huffman block decompression 16800c16b537SWarner Losh *********************************************************/ 16810c16b537SWarner Losh typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */ 16820c16b537SWarner Losh 16830c16b537SWarner Losh typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */ 16840c16b537SWarner Losh 16850c16b537SWarner Losh typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t; 16860c16b537SWarner Losh 16870c16b537SWarner Losh /*! HUF_readStats 16880c16b537SWarner Losh Read compact Huffman tree, saved by HUF_writeCTable 16890c16b537SWarner Losh @huffWeight : destination buffer 16900c16b537SWarner Losh @return : size read from `src` 16910c16b537SWarner Losh */ 16920c16b537SWarner Losh static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats, 16930c16b537SWarner Losh U32* nbSymbolsPtr, U32* tableLogPtr, 16940c16b537SWarner Losh const void* src, size_t srcSize) 16950c16b537SWarner Losh { 16960c16b537SWarner Losh U32 weightTotal; 16970c16b537SWarner Losh U32 tableLog; 16980c16b537SWarner Losh const BYTE* ip = (const BYTE*) src; 16990c16b537SWarner Losh size_t iSize; 17000c16b537SWarner Losh size_t oSize; 17010c16b537SWarner Losh U32 n; 17020c16b537SWarner Losh 17030c16b537SWarner Losh if (!srcSize) return ERROR(srcSize_wrong); 17040c16b537SWarner Losh iSize = ip[0]; 17050c16b537SWarner Losh //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */ 17060c16b537SWarner Losh 17070c16b537SWarner Losh if (iSize >= 128) /* special header */ 17080c16b537SWarner Losh { 17090c16b537SWarner Losh if (iSize >= (242)) /* RLE */ 17100c16b537SWarner Losh { 17110c16b537SWarner Losh static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 }; 17120c16b537SWarner Losh oSize = l[iSize-242]; 17130c16b537SWarner Losh memset(huffWeight, 1, hwSize); 17140c16b537SWarner Losh iSize = 0; 17150c16b537SWarner Losh } 17160c16b537SWarner Losh else /* Incompressible */ 17170c16b537SWarner Losh { 17180c16b537SWarner Losh oSize = iSize - 127; 17190c16b537SWarner Losh iSize = ((oSize+1)/2); 17200c16b537SWarner Losh if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 17210c16b537SWarner Losh if (oSize >= hwSize) return ERROR(corruption_detected); 17220c16b537SWarner Losh ip += 1; 17230c16b537SWarner Losh for (n=0; n<oSize; n+=2) 17240c16b537SWarner Losh { 17250c16b537SWarner Losh huffWeight[n] = ip[n/2] >> 4; 17260c16b537SWarner Losh huffWeight[n+1] = ip[n/2] & 15; 17270c16b537SWarner Losh } 17280c16b537SWarner Losh } 17290c16b537SWarner Losh } 17300c16b537SWarner Losh else /* header compressed with FSE (normal case) */ 17310c16b537SWarner Losh { 17320c16b537SWarner Losh if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 17330c16b537SWarner Losh oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */ 17340c16b537SWarner Losh if (FSE_isError(oSize)) return oSize; 17350c16b537SWarner Losh } 17360c16b537SWarner Losh 17370c16b537SWarner Losh /* collect weight stats */ 17380c16b537SWarner Losh memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32)); 17390c16b537SWarner Losh weightTotal = 0; 17400c16b537SWarner Losh for (n=0; n<oSize; n++) 17410c16b537SWarner Losh { 17420c16b537SWarner Losh if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 17430c16b537SWarner Losh rankStats[huffWeight[n]]++; 17440c16b537SWarner Losh weightTotal += (1 << huffWeight[n]) >> 1; 17450c16b537SWarner Losh } 17460c16b537SWarner Losh if (weightTotal == 0) return ERROR(corruption_detected); 17470c16b537SWarner Losh 17480c16b537SWarner Losh /* get last non-null symbol weight (implied, total must be 2^n) */ 17490c16b537SWarner Losh tableLog = BIT_highbit32(weightTotal) + 1; 17500c16b537SWarner Losh if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 17510c16b537SWarner Losh { 17520c16b537SWarner Losh U32 total = 1 << tableLog; 17530c16b537SWarner Losh U32 rest = total - weightTotal; 17540c16b537SWarner Losh U32 verif = 1 << BIT_highbit32(rest); 17550c16b537SWarner Losh U32 lastWeight = BIT_highbit32(rest) + 1; 17560c16b537SWarner Losh if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */ 17570c16b537SWarner Losh huffWeight[oSize] = (BYTE)lastWeight; 17580c16b537SWarner Losh rankStats[lastWeight]++; 17590c16b537SWarner Losh } 17600c16b537SWarner Losh 17610c16b537SWarner Losh /* check tree construction validity */ 17620c16b537SWarner Losh if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */ 17630c16b537SWarner Losh 17640c16b537SWarner Losh /* results */ 17650c16b537SWarner Losh *nbSymbolsPtr = (U32)(oSize+1); 17660c16b537SWarner Losh *tableLogPtr = tableLog; 17670c16b537SWarner Losh return iSize+1; 17680c16b537SWarner Losh } 17690c16b537SWarner Losh 17700c16b537SWarner Losh 17710c16b537SWarner Losh /**************************/ 17720c16b537SWarner Losh /* single-symbol decoding */ 17730c16b537SWarner Losh /**************************/ 17740c16b537SWarner Losh 17750c16b537SWarner Losh static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize) 17760c16b537SWarner Losh { 17770c16b537SWarner Losh BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1]; 17780c16b537SWarner Losh U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */ 17790c16b537SWarner Losh U32 tableLog = 0; 17800c16b537SWarner Losh size_t iSize; 17810c16b537SWarner Losh U32 nbSymbols = 0; 17820c16b537SWarner Losh U32 n; 17830c16b537SWarner Losh U32 nextRankStart; 17840c16b537SWarner Losh void* const dtPtr = DTable + 1; 17850c16b537SWarner Losh HUF_DEltX2* const dt = (HUF_DEltX2*)dtPtr; 17860c16b537SWarner Losh 17870c16b537SWarner Losh HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */ 17880c16b537SWarner Losh //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */ 17890c16b537SWarner Losh 17900c16b537SWarner Losh iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize); 17910c16b537SWarner Losh if (HUF_isError(iSize)) return iSize; 17920c16b537SWarner Losh 17930c16b537SWarner Losh /* check result */ 17940c16b537SWarner Losh if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */ 17950c16b537SWarner Losh DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */ 17960c16b537SWarner Losh 17970c16b537SWarner Losh /* Prepare ranks */ 17980c16b537SWarner Losh nextRankStart = 0; 17990c16b537SWarner Losh for (n=1; n<=tableLog; n++) 18000c16b537SWarner Losh { 18010c16b537SWarner Losh U32 current = nextRankStart; 18020c16b537SWarner Losh nextRankStart += (rankVal[n] << (n-1)); 18030c16b537SWarner Losh rankVal[n] = current; 18040c16b537SWarner Losh } 18050c16b537SWarner Losh 18060c16b537SWarner Losh /* fill DTable */ 18070c16b537SWarner Losh for (n=0; n<nbSymbols; n++) 18080c16b537SWarner Losh { 18090c16b537SWarner Losh const U32 w = huffWeight[n]; 18100c16b537SWarner Losh const U32 length = (1 << w) >> 1; 18110c16b537SWarner Losh U32 i; 18120c16b537SWarner Losh HUF_DEltX2 D; 18130c16b537SWarner Losh D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w); 18140c16b537SWarner Losh for (i = rankVal[w]; i < rankVal[w] + length; i++) 18150c16b537SWarner Losh dt[i] = D; 18160c16b537SWarner Losh rankVal[w] += length; 18170c16b537SWarner Losh } 18180c16b537SWarner Losh 18190c16b537SWarner Losh return iSize; 18200c16b537SWarner Losh } 18210c16b537SWarner Losh 18220c16b537SWarner Losh static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog) 18230c16b537SWarner Losh { 18240c16b537SWarner Losh const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */ 18250c16b537SWarner Losh const BYTE c = dt[val].byte; 18260c16b537SWarner Losh BIT_skipBits(Dstream, dt[val].nbBits); 18270c16b537SWarner Losh return c; 18280c16b537SWarner Losh } 18290c16b537SWarner Losh 18300c16b537SWarner Losh #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \ 18310c16b537SWarner Losh *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog) 18320c16b537SWarner Losh 18330c16b537SWarner Losh #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \ 18340c16b537SWarner Losh if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \ 18350c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 18360c16b537SWarner Losh 18370c16b537SWarner Losh #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \ 18380c16b537SWarner Losh if (MEM_64bits()) \ 18390c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 18400c16b537SWarner Losh 18410c16b537SWarner Losh static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog) 18420c16b537SWarner Losh { 18430c16b537SWarner Losh BYTE* const pStart = p; 18440c16b537SWarner Losh 18450c16b537SWarner Losh /* up to 4 symbols at a time */ 18460c16b537SWarner Losh while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4)) 18470c16b537SWarner Losh { 18480c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(p, bitDPtr); 18490c16b537SWarner Losh HUF_DECODE_SYMBOLX2_1(p, bitDPtr); 18500c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(p, bitDPtr); 18510c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(p, bitDPtr); 18520c16b537SWarner Losh } 18530c16b537SWarner Losh 18540c16b537SWarner Losh /* closer to the end */ 18550c16b537SWarner Losh while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd)) 18560c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(p, bitDPtr); 18570c16b537SWarner Losh 18580c16b537SWarner Losh /* no more data to retrieve from bitstream, hence no need to reload */ 18590c16b537SWarner Losh while (p < pEnd) 18600c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(p, bitDPtr); 18610c16b537SWarner Losh 18620c16b537SWarner Losh return pEnd-pStart; 18630c16b537SWarner Losh } 18640c16b537SWarner Losh 18650c16b537SWarner Losh 18660c16b537SWarner Losh static size_t HUF_decompress4X2_usingDTable( 18670c16b537SWarner Losh void* dst, size_t dstSize, 18680c16b537SWarner Losh const void* cSrc, size_t cSrcSize, 18690c16b537SWarner Losh const U16* DTable) 18700c16b537SWarner Losh { 18710c16b537SWarner Losh if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 18720c16b537SWarner Losh 18730c16b537SWarner Losh { 18740c16b537SWarner Losh const BYTE* const istart = (const BYTE*) cSrc; 18750c16b537SWarner Losh BYTE* const ostart = (BYTE*) dst; 18760c16b537SWarner Losh BYTE* const oend = ostart + dstSize; 18770c16b537SWarner Losh const void* const dtPtr = DTable; 18780c16b537SWarner Losh const HUF_DEltX2* const dt = ((const HUF_DEltX2*)dtPtr) +1; 18790c16b537SWarner Losh const U32 dtLog = DTable[0]; 18800c16b537SWarner Losh size_t errorCode; 18810c16b537SWarner Losh 18820c16b537SWarner Losh /* Init */ 18830c16b537SWarner Losh BIT_DStream_t bitD1; 18840c16b537SWarner Losh BIT_DStream_t bitD2; 18850c16b537SWarner Losh BIT_DStream_t bitD3; 18860c16b537SWarner Losh BIT_DStream_t bitD4; 18870c16b537SWarner Losh const size_t length1 = MEM_readLE16(istart); 18880c16b537SWarner Losh const size_t length2 = MEM_readLE16(istart+2); 18890c16b537SWarner Losh const size_t length3 = MEM_readLE16(istart+4); 18900c16b537SWarner Losh size_t length4; 18910c16b537SWarner Losh const BYTE* const istart1 = istart + 6; /* jumpTable */ 18920c16b537SWarner Losh const BYTE* const istart2 = istart1 + length1; 18930c16b537SWarner Losh const BYTE* const istart3 = istart2 + length2; 18940c16b537SWarner Losh const BYTE* const istart4 = istart3 + length3; 18950c16b537SWarner Losh const size_t segmentSize = (dstSize+3) / 4; 18960c16b537SWarner Losh BYTE* const opStart2 = ostart + segmentSize; 18970c16b537SWarner Losh BYTE* const opStart3 = opStart2 + segmentSize; 18980c16b537SWarner Losh BYTE* const opStart4 = opStart3 + segmentSize; 18990c16b537SWarner Losh BYTE* op1 = ostart; 19000c16b537SWarner Losh BYTE* op2 = opStart2; 19010c16b537SWarner Losh BYTE* op3 = opStart3; 19020c16b537SWarner Losh BYTE* op4 = opStart4; 19030c16b537SWarner Losh U32 endSignal; 19040c16b537SWarner Losh 19050c16b537SWarner Losh length4 = cSrcSize - (length1 + length2 + length3 + 6); 19060c16b537SWarner Losh if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 19070c16b537SWarner Losh errorCode = BIT_initDStream(&bitD1, istart1, length1); 19080c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 19090c16b537SWarner Losh errorCode = BIT_initDStream(&bitD2, istart2, length2); 19100c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 19110c16b537SWarner Losh errorCode = BIT_initDStream(&bitD3, istart3, length3); 19120c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 19130c16b537SWarner Losh errorCode = BIT_initDStream(&bitD4, istart4, length4); 19140c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 19150c16b537SWarner Losh 19160c16b537SWarner Losh /* 16-32 symbols per loop (4-8 symbols per stream) */ 19170c16b537SWarner Losh endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 19180c16b537SWarner Losh for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; ) 19190c16b537SWarner Losh { 19200c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op1, &bitD1); 19210c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op2, &bitD2); 19220c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op3, &bitD3); 19230c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op4, &bitD4); 19240c16b537SWarner Losh HUF_DECODE_SYMBOLX2_1(op1, &bitD1); 19250c16b537SWarner Losh HUF_DECODE_SYMBOLX2_1(op2, &bitD2); 19260c16b537SWarner Losh HUF_DECODE_SYMBOLX2_1(op3, &bitD3); 19270c16b537SWarner Losh HUF_DECODE_SYMBOLX2_1(op4, &bitD4); 19280c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op1, &bitD1); 19290c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op2, &bitD2); 19300c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op3, &bitD3); 19310c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op4, &bitD4); 19320c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(op1, &bitD1); 19330c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(op2, &bitD2); 19340c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(op3, &bitD3); 19350c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(op4, &bitD4); 19360c16b537SWarner Losh 19370c16b537SWarner Losh endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 19380c16b537SWarner Losh } 19390c16b537SWarner Losh 19400c16b537SWarner Losh /* check corruption */ 19410c16b537SWarner Losh if (op1 > opStart2) return ERROR(corruption_detected); 19420c16b537SWarner Losh if (op2 > opStart3) return ERROR(corruption_detected); 19430c16b537SWarner Losh if (op3 > opStart4) return ERROR(corruption_detected); 19440c16b537SWarner Losh /* note : op4 supposed already verified within main loop */ 19450c16b537SWarner Losh 19460c16b537SWarner Losh /* finish bitStreams one by one */ 19470c16b537SWarner Losh HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog); 19480c16b537SWarner Losh HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog); 19490c16b537SWarner Losh HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog); 19500c16b537SWarner Losh HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog); 19510c16b537SWarner Losh 19520c16b537SWarner Losh /* check */ 19530c16b537SWarner Losh endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4); 19540c16b537SWarner Losh if (!endSignal) return ERROR(corruption_detected); 19550c16b537SWarner Losh 19560c16b537SWarner Losh /* decoded size */ 19570c16b537SWarner Losh return dstSize; 19580c16b537SWarner Losh } 19590c16b537SWarner Losh } 19600c16b537SWarner Losh 19610c16b537SWarner Losh 19620c16b537SWarner Losh static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 19630c16b537SWarner Losh { 19640c16b537SWarner Losh HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG); 19650c16b537SWarner Losh const BYTE* ip = (const BYTE*) cSrc; 19660c16b537SWarner Losh size_t errorCode; 19670c16b537SWarner Losh 19680c16b537SWarner Losh errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize); 19690c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 19700c16b537SWarner Losh if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); 19710c16b537SWarner Losh ip += errorCode; 19720c16b537SWarner Losh cSrcSize -= errorCode; 19730c16b537SWarner Losh 19740c16b537SWarner Losh return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 19750c16b537SWarner Losh } 19760c16b537SWarner Losh 19770c16b537SWarner Losh 19780c16b537SWarner Losh /***************************/ 19790c16b537SWarner Losh /* double-symbols decoding */ 19800c16b537SWarner Losh /***************************/ 19810c16b537SWarner Losh 19820c16b537SWarner Losh static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed, 19830c16b537SWarner Losh const U32* rankValOrigin, const int minWeight, 19840c16b537SWarner Losh const sortedSymbol_t* sortedSymbols, const U32 sortedListSize, 19850c16b537SWarner Losh U32 nbBitsBaseline, U16 baseSeq) 19860c16b537SWarner Losh { 19870c16b537SWarner Losh HUF_DEltX4 DElt; 19880c16b537SWarner Losh U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; 19890c16b537SWarner Losh U32 s; 19900c16b537SWarner Losh 19910c16b537SWarner Losh /* get pre-calculated rankVal */ 19920c16b537SWarner Losh memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 19930c16b537SWarner Losh 19940c16b537SWarner Losh /* fill skipped values */ 19950c16b537SWarner Losh if (minWeight>1) 19960c16b537SWarner Losh { 19970c16b537SWarner Losh U32 i, skipSize = rankVal[minWeight]; 19980c16b537SWarner Losh MEM_writeLE16(&(DElt.sequence), baseSeq); 19990c16b537SWarner Losh DElt.nbBits = (BYTE)(consumed); 20000c16b537SWarner Losh DElt.length = 1; 20010c16b537SWarner Losh for (i = 0; i < skipSize; i++) 20020c16b537SWarner Losh DTable[i] = DElt; 20030c16b537SWarner Losh } 20040c16b537SWarner Losh 20050c16b537SWarner Losh /* fill DTable */ 20060c16b537SWarner Losh for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */ 20070c16b537SWarner Losh { 20080c16b537SWarner Losh const U32 symbol = sortedSymbols[s].symbol; 20090c16b537SWarner Losh const U32 weight = sortedSymbols[s].weight; 20100c16b537SWarner Losh const U32 nbBits = nbBitsBaseline - weight; 20110c16b537SWarner Losh const U32 length = 1 << (sizeLog-nbBits); 20120c16b537SWarner Losh const U32 start = rankVal[weight]; 20130c16b537SWarner Losh U32 i = start; 20140c16b537SWarner Losh const U32 end = start + length; 20150c16b537SWarner Losh 20160c16b537SWarner Losh MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8))); 20170c16b537SWarner Losh DElt.nbBits = (BYTE)(nbBits + consumed); 20180c16b537SWarner Losh DElt.length = 2; 20190c16b537SWarner Losh do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */ 20200c16b537SWarner Losh 20210c16b537SWarner Losh rankVal[weight] += length; 20220c16b537SWarner Losh } 20230c16b537SWarner Losh } 20240c16b537SWarner Losh 20250c16b537SWarner Losh typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1]; 20260c16b537SWarner Losh 20270c16b537SWarner Losh static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog, 20280c16b537SWarner Losh const sortedSymbol_t* sortedList, const U32 sortedListSize, 20290c16b537SWarner Losh const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight, 20300c16b537SWarner Losh const U32 nbBitsBaseline) 20310c16b537SWarner Losh { 20320c16b537SWarner Losh U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; 20330c16b537SWarner Losh const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */ 20340c16b537SWarner Losh const U32 minBits = nbBitsBaseline - maxWeight; 20350c16b537SWarner Losh U32 s; 20360c16b537SWarner Losh 20370c16b537SWarner Losh memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 20380c16b537SWarner Losh 20390c16b537SWarner Losh /* fill DTable */ 20400c16b537SWarner Losh for (s=0; s<sortedListSize; s++) 20410c16b537SWarner Losh { 20420c16b537SWarner Losh const U16 symbol = sortedList[s].symbol; 20430c16b537SWarner Losh const U32 weight = sortedList[s].weight; 20440c16b537SWarner Losh const U32 nbBits = nbBitsBaseline - weight; 20450c16b537SWarner Losh const U32 start = rankVal[weight]; 20460c16b537SWarner Losh const U32 length = 1 << (targetLog-nbBits); 20470c16b537SWarner Losh 20480c16b537SWarner Losh if (targetLog-nbBits >= minBits) /* enough room for a second symbol */ 20490c16b537SWarner Losh { 20500c16b537SWarner Losh U32 sortedRank; 20510c16b537SWarner Losh int minWeight = nbBits + scaleLog; 20520c16b537SWarner Losh if (minWeight < 1) minWeight = 1; 20530c16b537SWarner Losh sortedRank = rankStart[minWeight]; 20540c16b537SWarner Losh HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits, 20550c16b537SWarner Losh rankValOrigin[nbBits], minWeight, 20560c16b537SWarner Losh sortedList+sortedRank, sortedListSize-sortedRank, 20570c16b537SWarner Losh nbBitsBaseline, symbol); 20580c16b537SWarner Losh } 20590c16b537SWarner Losh else 20600c16b537SWarner Losh { 20610c16b537SWarner Losh U32 i; 20620c16b537SWarner Losh const U32 end = start + length; 20630c16b537SWarner Losh HUF_DEltX4 DElt; 20640c16b537SWarner Losh 20650c16b537SWarner Losh MEM_writeLE16(&(DElt.sequence), symbol); 20660c16b537SWarner Losh DElt.nbBits = (BYTE)(nbBits); 20670c16b537SWarner Losh DElt.length = 1; 20680c16b537SWarner Losh for (i = start; i < end; i++) 20690c16b537SWarner Losh DTable[i] = DElt; 20700c16b537SWarner Losh } 20710c16b537SWarner Losh rankVal[weight] += length; 20720c16b537SWarner Losh } 20730c16b537SWarner Losh } 20740c16b537SWarner Losh 20750c16b537SWarner Losh static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize) 20760c16b537SWarner Losh { 20770c16b537SWarner Losh BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1]; 20780c16b537SWarner Losh sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1]; 20790c16b537SWarner Losh U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 }; 20800c16b537SWarner Losh U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 }; 20810c16b537SWarner Losh U32* const rankStart = rankStart0+1; 20820c16b537SWarner Losh rankVal_t rankVal; 20830c16b537SWarner Losh U32 tableLog, maxW, sizeOfSort, nbSymbols; 20840c16b537SWarner Losh const U32 memLog = DTable[0]; 20850c16b537SWarner Losh size_t iSize; 20860c16b537SWarner Losh void* dtPtr = DTable; 20870c16b537SWarner Losh HUF_DEltX4* const dt = ((HUF_DEltX4*)dtPtr) + 1; 20880c16b537SWarner Losh 20890c16b537SWarner Losh HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */ 20900c16b537SWarner Losh if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge); 20910c16b537SWarner Losh //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */ 20920c16b537SWarner Losh 20930c16b537SWarner Losh iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize); 20940c16b537SWarner Losh if (HUF_isError(iSize)) return iSize; 20950c16b537SWarner Losh 20960c16b537SWarner Losh /* check result */ 20970c16b537SWarner Losh if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */ 20980c16b537SWarner Losh 20990c16b537SWarner Losh /* find maxWeight */ 21000c16b537SWarner Losh for (maxW = tableLog; rankStats[maxW]==0; maxW--) 21010c16b537SWarner Losh { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */ 21020c16b537SWarner Losh 21030c16b537SWarner Losh /* Get start index of each weight */ 21040c16b537SWarner Losh { 21050c16b537SWarner Losh U32 w, nextRankStart = 0; 21060c16b537SWarner Losh for (w=1; w<=maxW; w++) 21070c16b537SWarner Losh { 21080c16b537SWarner Losh U32 current = nextRankStart; 21090c16b537SWarner Losh nextRankStart += rankStats[w]; 21100c16b537SWarner Losh rankStart[w] = current; 21110c16b537SWarner Losh } 21120c16b537SWarner Losh rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/ 21130c16b537SWarner Losh sizeOfSort = nextRankStart; 21140c16b537SWarner Losh } 21150c16b537SWarner Losh 21160c16b537SWarner Losh /* sort symbols by weight */ 21170c16b537SWarner Losh { 21180c16b537SWarner Losh U32 s; 21190c16b537SWarner Losh for (s=0; s<nbSymbols; s++) 21200c16b537SWarner Losh { 21210c16b537SWarner Losh U32 w = weightList[s]; 21220c16b537SWarner Losh U32 r = rankStart[w]++; 21230c16b537SWarner Losh sortedSymbol[r].symbol = (BYTE)s; 21240c16b537SWarner Losh sortedSymbol[r].weight = (BYTE)w; 21250c16b537SWarner Losh } 21260c16b537SWarner Losh rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */ 21270c16b537SWarner Losh } 21280c16b537SWarner Losh 21290c16b537SWarner Losh /* Build rankVal */ 21300c16b537SWarner Losh { 21310c16b537SWarner Losh const U32 minBits = tableLog+1 - maxW; 21320c16b537SWarner Losh U32 nextRankVal = 0; 21330c16b537SWarner Losh U32 w, consumed; 21340c16b537SWarner Losh const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */ 21350c16b537SWarner Losh U32* rankVal0 = rankVal[0]; 21360c16b537SWarner Losh for (w=1; w<=maxW; w++) 21370c16b537SWarner Losh { 21380c16b537SWarner Losh U32 current = nextRankVal; 21390c16b537SWarner Losh nextRankVal += rankStats[w] << (w+rescale); 21400c16b537SWarner Losh rankVal0[w] = current; 21410c16b537SWarner Losh } 21420c16b537SWarner Losh for (consumed = minBits; consumed <= memLog - minBits; consumed++) 21430c16b537SWarner Losh { 21440c16b537SWarner Losh U32* rankValPtr = rankVal[consumed]; 21450c16b537SWarner Losh for (w = 1; w <= maxW; w++) 21460c16b537SWarner Losh { 21470c16b537SWarner Losh rankValPtr[w] = rankVal0[w] >> consumed; 21480c16b537SWarner Losh } 21490c16b537SWarner Losh } 21500c16b537SWarner Losh } 21510c16b537SWarner Losh 21520c16b537SWarner Losh HUF_fillDTableX4(dt, memLog, 21530c16b537SWarner Losh sortedSymbol, sizeOfSort, 21540c16b537SWarner Losh rankStart0, rankVal, maxW, 21550c16b537SWarner Losh tableLog+1); 21560c16b537SWarner Losh 21570c16b537SWarner Losh return iSize; 21580c16b537SWarner Losh } 21590c16b537SWarner Losh 21600c16b537SWarner Losh 21610c16b537SWarner Losh static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog) 21620c16b537SWarner Losh { 21630c16b537SWarner Losh const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 21640c16b537SWarner Losh memcpy(op, dt+val, 2); 21650c16b537SWarner Losh BIT_skipBits(DStream, dt[val].nbBits); 21660c16b537SWarner Losh return dt[val].length; 21670c16b537SWarner Losh } 21680c16b537SWarner Losh 21690c16b537SWarner Losh static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog) 21700c16b537SWarner Losh { 21710c16b537SWarner Losh const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 21720c16b537SWarner Losh memcpy(op, dt+val, 1); 21730c16b537SWarner Losh if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits); 21740c16b537SWarner Losh else 21750c16b537SWarner Losh { 21760c16b537SWarner Losh if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) 21770c16b537SWarner Losh { 21780c16b537SWarner Losh BIT_skipBits(DStream, dt[val].nbBits); 21790c16b537SWarner Losh if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8)) 21800c16b537SWarner Losh 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 */ 21810c16b537SWarner Losh } 21820c16b537SWarner Losh } 21830c16b537SWarner Losh return 1; 21840c16b537SWarner Losh } 21850c16b537SWarner Losh 21860c16b537SWarner Losh 21870c16b537SWarner Losh #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \ 21880c16b537SWarner Losh ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 21890c16b537SWarner Losh 21900c16b537SWarner Losh #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \ 21910c16b537SWarner Losh if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \ 21920c16b537SWarner Losh ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 21930c16b537SWarner Losh 21940c16b537SWarner Losh #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \ 21950c16b537SWarner Losh if (MEM_64bits()) \ 21960c16b537SWarner Losh ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 21970c16b537SWarner Losh 21980c16b537SWarner Losh static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog) 21990c16b537SWarner Losh { 22000c16b537SWarner Losh BYTE* const pStart = p; 22010c16b537SWarner Losh 22020c16b537SWarner Losh /* up to 8 symbols at a time */ 22030c16b537SWarner Losh while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7)) 22040c16b537SWarner Losh { 22050c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(p, bitDPtr); 22060c16b537SWarner Losh HUF_DECODE_SYMBOLX4_1(p, bitDPtr); 22070c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(p, bitDPtr); 22080c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(p, bitDPtr); 22090c16b537SWarner Losh } 22100c16b537SWarner Losh 22110c16b537SWarner Losh /* closer to the end */ 22120c16b537SWarner Losh while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2)) 22130c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(p, bitDPtr); 22140c16b537SWarner Losh 22150c16b537SWarner Losh while (p <= pEnd-2) 22160c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */ 22170c16b537SWarner Losh 22180c16b537SWarner Losh if (p < pEnd) 22190c16b537SWarner Losh p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog); 22200c16b537SWarner Losh 22210c16b537SWarner Losh return p-pStart; 22220c16b537SWarner Losh } 22230c16b537SWarner Losh 22240c16b537SWarner Losh static size_t HUF_decompress4X4_usingDTable( 22250c16b537SWarner Losh void* dst, size_t dstSize, 22260c16b537SWarner Losh const void* cSrc, size_t cSrcSize, 22270c16b537SWarner Losh const U32* DTable) 22280c16b537SWarner Losh { 22290c16b537SWarner Losh if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 22300c16b537SWarner Losh 22310c16b537SWarner Losh { 22320c16b537SWarner Losh const BYTE* const istart = (const BYTE*) cSrc; 22330c16b537SWarner Losh BYTE* const ostart = (BYTE*) dst; 22340c16b537SWarner Losh BYTE* const oend = ostart + dstSize; 22350c16b537SWarner Losh const void* const dtPtr = DTable; 22360c16b537SWarner Losh const HUF_DEltX4* const dt = ((const HUF_DEltX4*)dtPtr) +1; 22370c16b537SWarner Losh const U32 dtLog = DTable[0]; 22380c16b537SWarner Losh size_t errorCode; 22390c16b537SWarner Losh 22400c16b537SWarner Losh /* Init */ 22410c16b537SWarner Losh BIT_DStream_t bitD1; 22420c16b537SWarner Losh BIT_DStream_t bitD2; 22430c16b537SWarner Losh BIT_DStream_t bitD3; 22440c16b537SWarner Losh BIT_DStream_t bitD4; 22450c16b537SWarner Losh const size_t length1 = MEM_readLE16(istart); 22460c16b537SWarner Losh const size_t length2 = MEM_readLE16(istart+2); 22470c16b537SWarner Losh const size_t length3 = MEM_readLE16(istart+4); 22480c16b537SWarner Losh size_t length4; 22490c16b537SWarner Losh const BYTE* const istart1 = istart + 6; /* jumpTable */ 22500c16b537SWarner Losh const BYTE* const istart2 = istart1 + length1; 22510c16b537SWarner Losh const BYTE* const istart3 = istart2 + length2; 22520c16b537SWarner Losh const BYTE* const istart4 = istart3 + length3; 22530c16b537SWarner Losh const size_t segmentSize = (dstSize+3) / 4; 22540c16b537SWarner Losh BYTE* const opStart2 = ostart + segmentSize; 22550c16b537SWarner Losh BYTE* const opStart3 = opStart2 + segmentSize; 22560c16b537SWarner Losh BYTE* const opStart4 = opStart3 + segmentSize; 22570c16b537SWarner Losh BYTE* op1 = ostart; 22580c16b537SWarner Losh BYTE* op2 = opStart2; 22590c16b537SWarner Losh BYTE* op3 = opStart3; 22600c16b537SWarner Losh BYTE* op4 = opStart4; 22610c16b537SWarner Losh U32 endSignal; 22620c16b537SWarner Losh 22630c16b537SWarner Losh length4 = cSrcSize - (length1 + length2 + length3 + 6); 22640c16b537SWarner Losh if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 22650c16b537SWarner Losh errorCode = BIT_initDStream(&bitD1, istart1, length1); 22660c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 22670c16b537SWarner Losh errorCode = BIT_initDStream(&bitD2, istart2, length2); 22680c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 22690c16b537SWarner Losh errorCode = BIT_initDStream(&bitD3, istart3, length3); 22700c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 22710c16b537SWarner Losh errorCode = BIT_initDStream(&bitD4, istart4, length4); 22720c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 22730c16b537SWarner Losh 22740c16b537SWarner Losh /* 16-32 symbols per loop (4-8 symbols per stream) */ 22750c16b537SWarner Losh endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 22760c16b537SWarner Losh for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; ) 22770c16b537SWarner Losh { 22780c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op1, &bitD1); 22790c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op2, &bitD2); 22800c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op3, &bitD3); 22810c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op4, &bitD4); 22820c16b537SWarner Losh HUF_DECODE_SYMBOLX4_1(op1, &bitD1); 22830c16b537SWarner Losh HUF_DECODE_SYMBOLX4_1(op2, &bitD2); 22840c16b537SWarner Losh HUF_DECODE_SYMBOLX4_1(op3, &bitD3); 22850c16b537SWarner Losh HUF_DECODE_SYMBOLX4_1(op4, &bitD4); 22860c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op1, &bitD1); 22870c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op2, &bitD2); 22880c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op3, &bitD3); 22890c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op4, &bitD4); 22900c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(op1, &bitD1); 22910c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(op2, &bitD2); 22920c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(op3, &bitD3); 22930c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(op4, &bitD4); 22940c16b537SWarner Losh 22950c16b537SWarner Losh endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 22960c16b537SWarner Losh } 22970c16b537SWarner Losh 22980c16b537SWarner Losh /* check corruption */ 22990c16b537SWarner Losh if (op1 > opStart2) return ERROR(corruption_detected); 23000c16b537SWarner Losh if (op2 > opStart3) return ERROR(corruption_detected); 23010c16b537SWarner Losh if (op3 > opStart4) return ERROR(corruption_detected); 23020c16b537SWarner Losh /* note : op4 supposed already verified within main loop */ 23030c16b537SWarner Losh 23040c16b537SWarner Losh /* finish bitStreams one by one */ 23050c16b537SWarner Losh HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog); 23060c16b537SWarner Losh HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog); 23070c16b537SWarner Losh HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog); 23080c16b537SWarner Losh HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog); 23090c16b537SWarner Losh 23100c16b537SWarner Losh /* check */ 23110c16b537SWarner Losh endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4); 23120c16b537SWarner Losh if (!endSignal) return ERROR(corruption_detected); 23130c16b537SWarner Losh 23140c16b537SWarner Losh /* decoded size */ 23150c16b537SWarner Losh return dstSize; 23160c16b537SWarner Losh } 23170c16b537SWarner Losh } 23180c16b537SWarner Losh 23190c16b537SWarner Losh 23200c16b537SWarner Losh static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 23210c16b537SWarner Losh { 23220c16b537SWarner Losh HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG); 23230c16b537SWarner Losh const BYTE* ip = (const BYTE*) cSrc; 23240c16b537SWarner Losh 23250c16b537SWarner Losh size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize); 23260c16b537SWarner Losh if (HUF_isError(hSize)) return hSize; 23270c16b537SWarner Losh if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 23280c16b537SWarner Losh ip += hSize; 23290c16b537SWarner Losh cSrcSize -= hSize; 23300c16b537SWarner Losh 23310c16b537SWarner Losh return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 23320c16b537SWarner Losh } 23330c16b537SWarner Losh 23340c16b537SWarner Losh 23350c16b537SWarner Losh /**********************************/ 23360c16b537SWarner Losh /* Generic decompression selector */ 23370c16b537SWarner Losh /**********************************/ 23380c16b537SWarner Losh 23390c16b537SWarner Losh typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t; 23400c16b537SWarner Losh static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] = 23410c16b537SWarner Losh { 23420c16b537SWarner Losh /* single, double, quad */ 23430c16b537SWarner Losh {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */ 23440c16b537SWarner Losh {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */ 23450c16b537SWarner Losh {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */ 23460c16b537SWarner Losh {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */ 23470c16b537SWarner Losh {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */ 23480c16b537SWarner Losh {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */ 23490c16b537SWarner Losh {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */ 23500c16b537SWarner Losh {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */ 23510c16b537SWarner Losh {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */ 23520c16b537SWarner Losh {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */ 23530c16b537SWarner Losh {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */ 23540c16b537SWarner Losh {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */ 23550c16b537SWarner Losh {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */ 23560c16b537SWarner Losh {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */ 23570c16b537SWarner Losh {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */ 23580c16b537SWarner Losh {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */ 23590c16b537SWarner Losh }; 23600c16b537SWarner Losh 23610c16b537SWarner Losh typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); 23620c16b537SWarner Losh 23630c16b537SWarner Losh static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 23640c16b537SWarner Losh { 23650c16b537SWarner Losh static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL }; 23660c16b537SWarner Losh /* estimate decompression time */ 23670c16b537SWarner Losh U32 Q; 23680c16b537SWarner Losh const U32 D256 = (U32)(dstSize >> 8); 23690c16b537SWarner Losh U32 Dtime[3]; 23700c16b537SWarner Losh U32 algoNb = 0; 23710c16b537SWarner Losh int n; 23720c16b537SWarner Losh 23730c16b537SWarner Losh /* validation checks */ 23740c16b537SWarner Losh if (dstSize == 0) return ERROR(dstSize_tooSmall); 23750c16b537SWarner Losh if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */ 23760c16b537SWarner Losh if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */ 23770c16b537SWarner Losh if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */ 23780c16b537SWarner Losh 23790c16b537SWarner Losh /* decoder timing evaluation */ 23800c16b537SWarner Losh Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */ 23810c16b537SWarner Losh for (n=0; n<3; n++) 23820c16b537SWarner Losh Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256); 23830c16b537SWarner Losh 23840c16b537SWarner Losh Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */ 23850c16b537SWarner Losh 23860c16b537SWarner Losh if (Dtime[1] < Dtime[0]) algoNb = 1; 23870c16b537SWarner Losh 23880c16b537SWarner Losh return decompress[algoNb](dst, dstSize, cSrc, cSrcSize); 23890c16b537SWarner Losh 23900c16b537SWarner Losh //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */ 23910c16b537SWarner Losh //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */ 23920c16b537SWarner Losh //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */ 23930c16b537SWarner Losh } 23940c16b537SWarner Losh 23950c16b537SWarner Losh 23960c16b537SWarner Losh 23970c16b537SWarner Losh #endif /* ZSTD_CCOMMON_H_MODULE */ 23980c16b537SWarner Losh 23990c16b537SWarner Losh 24000c16b537SWarner Losh /* 24010c16b537SWarner Losh zstd - decompression module fo v0.4 legacy format 24020c16b537SWarner Losh Copyright (C) 2015-2016, Yann Collet. 24030c16b537SWarner Losh 24040c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 24050c16b537SWarner Losh 24060c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 24070c16b537SWarner Losh modification, are permitted provided that the following conditions are 24080c16b537SWarner Losh met: 24090c16b537SWarner Losh * Redistributions of source code must retain the above copyright 24100c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 24110c16b537SWarner Losh * Redistributions in binary form must reproduce the above 24120c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 24130c16b537SWarner Losh in the documentation and/or other materials provided with the 24140c16b537SWarner Losh distribution. 24150c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24160c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 24170c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24180c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 24190c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24200c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24210c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24220c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24230c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24240c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 24250c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24260c16b537SWarner Losh 24270c16b537SWarner Losh You can contact the author at : 24280c16b537SWarner Losh - zstd source repository : https://github.com/Cyan4973/zstd 24290c16b537SWarner Losh - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c 24300c16b537SWarner Losh */ 24310c16b537SWarner Losh 24320c16b537SWarner Losh /* *************************************************************** 24330c16b537SWarner Losh * Tuning parameters 24340c16b537SWarner Losh *****************************************************************/ 24350c16b537SWarner Losh /*! 24360c16b537SWarner Losh * HEAPMODE : 24370c16b537SWarner Losh * Select how default decompression function ZSTD_decompress() will allocate memory, 24380c16b537SWarner Losh * in memory stack (0), or in memory heap (1, requires malloc()) 24390c16b537SWarner Losh */ 24400c16b537SWarner Losh #ifndef ZSTD_HEAPMODE 24410c16b537SWarner Losh # define ZSTD_HEAPMODE 1 24420c16b537SWarner Losh #endif 24430c16b537SWarner Losh 24440c16b537SWarner Losh 24450c16b537SWarner Losh /* ******************************************************* 24460c16b537SWarner Losh * Includes 24470c16b537SWarner Losh *********************************************************/ 24480c16b537SWarner Losh #include <stdlib.h> /* calloc */ 24490c16b537SWarner Losh #include <string.h> /* memcpy, memmove */ 24500c16b537SWarner Losh #include <stdio.h> /* debug : printf */ 24510c16b537SWarner Losh 24520c16b537SWarner Losh 24530c16b537SWarner Losh /* ******************************************************* 24540c16b537SWarner Losh * Compiler specifics 24550c16b537SWarner Losh *********************************************************/ 24560c16b537SWarner Losh #ifdef _MSC_VER /* Visual Studio */ 24570c16b537SWarner Losh # include <intrin.h> /* For Visual 2005 */ 24580c16b537SWarner Losh # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 24590c16b537SWarner Losh # pragma warning(disable : 4324) /* disable: C4324: padded structure */ 24600c16b537SWarner Losh #endif 24610c16b537SWarner Losh 24620c16b537SWarner Losh 24630c16b537SWarner Losh /* ************************************* 24640c16b537SWarner Losh * Local types 24650c16b537SWarner Losh ***************************************/ 24660c16b537SWarner Losh typedef struct 24670c16b537SWarner Losh { 24680c16b537SWarner Losh blockType_t blockType; 24690c16b537SWarner Losh U32 origSize; 24700c16b537SWarner Losh } blockProperties_t; 24710c16b537SWarner Losh 24720c16b537SWarner Losh 24730c16b537SWarner Losh /* ******************************************************* 24740c16b537SWarner Losh * Memory operations 24750c16b537SWarner Losh **********************************************************/ 24760c16b537SWarner Losh static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); } 24770c16b537SWarner Losh 24780c16b537SWarner Losh 24790c16b537SWarner Losh /* ************************************* 24800c16b537SWarner Losh * Error Management 24810c16b537SWarner Losh ***************************************/ 24820c16b537SWarner Losh 24830c16b537SWarner Losh /*! ZSTD_isError 24840c16b537SWarner Losh * tells if a return value is an error code */ 24850c16b537SWarner Losh static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); } 24860c16b537SWarner Losh 24870c16b537SWarner Losh 24880c16b537SWarner Losh /* ************************************************************* 24890c16b537SWarner Losh * Context management 24900c16b537SWarner Losh ***************************************************************/ 24910c16b537SWarner Losh typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader, 24920c16b537SWarner Losh ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock } ZSTD_dStage; 24930c16b537SWarner Losh 24940c16b537SWarner Losh struct ZSTDv04_Dctx_s 24950c16b537SWarner Losh { 24960c16b537SWarner Losh U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)]; 24970c16b537SWarner Losh U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)]; 24980c16b537SWarner Losh U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)]; 24990c16b537SWarner Losh const void* previousDstEnd; 25000c16b537SWarner Losh const void* base; 25010c16b537SWarner Losh const void* vBase; 25020c16b537SWarner Losh const void* dictEnd; 25030c16b537SWarner Losh size_t expected; 25040c16b537SWarner Losh size_t headerSize; 25050c16b537SWarner Losh ZSTD_parameters params; 25060c16b537SWarner Losh blockType_t bType; 25070c16b537SWarner Losh ZSTD_dStage stage; 25080c16b537SWarner Losh const BYTE* litPtr; 25090c16b537SWarner Losh size_t litSize; 25100c16b537SWarner Losh BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */]; 25110c16b537SWarner Losh BYTE headerBuffer[ZSTD_frameHeaderSize_max]; 25120c16b537SWarner Losh }; /* typedef'd to ZSTD_DCtx within "zstd_static.h" */ 25130c16b537SWarner Losh 25140c16b537SWarner Losh static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx) 25150c16b537SWarner Losh { 25160c16b537SWarner Losh dctx->expected = ZSTD_frameHeaderSize_min; 25170c16b537SWarner Losh dctx->stage = ZSTDds_getFrameHeaderSize; 25180c16b537SWarner Losh dctx->previousDstEnd = NULL; 25190c16b537SWarner Losh dctx->base = NULL; 25200c16b537SWarner Losh dctx->vBase = NULL; 25210c16b537SWarner Losh dctx->dictEnd = NULL; 25220c16b537SWarner Losh return 0; 25230c16b537SWarner Losh } 25240c16b537SWarner Losh 25250c16b537SWarner Losh static ZSTD_DCtx* ZSTD_createDCtx(void) 25260c16b537SWarner Losh { 25270c16b537SWarner Losh ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx)); 25280c16b537SWarner Losh if (dctx==NULL) return NULL; 25290c16b537SWarner Losh ZSTD_resetDCtx(dctx); 25300c16b537SWarner Losh return dctx; 25310c16b537SWarner Losh } 25320c16b537SWarner Losh 25330c16b537SWarner Losh static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx) 25340c16b537SWarner Losh { 25350c16b537SWarner Losh free(dctx); 25360c16b537SWarner Losh return 0; 25370c16b537SWarner Losh } 25380c16b537SWarner Losh 25390c16b537SWarner Losh 25400c16b537SWarner Losh /* ************************************************************* 25410c16b537SWarner Losh * Decompression section 25420c16b537SWarner Losh ***************************************************************/ 25430c16b537SWarner Losh /** ZSTD_decodeFrameHeader_Part1 25440c16b537SWarner Losh * decode the 1st part of the Frame Header, which tells Frame Header size. 25450c16b537SWarner Losh * srcSize must be == ZSTD_frameHeaderSize_min 25460c16b537SWarner Losh * @return : the full size of the Frame Header */ 25470c16b537SWarner Losh static size_t ZSTD_decodeFrameHeader_Part1(ZSTD_DCtx* zc, const void* src, size_t srcSize) 25480c16b537SWarner Losh { 25490c16b537SWarner Losh U32 magicNumber; 25500c16b537SWarner Losh if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong); 25510c16b537SWarner Losh magicNumber = MEM_readLE32(src); 25520c16b537SWarner Losh if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown); 25530c16b537SWarner Losh zc->headerSize = ZSTD_frameHeaderSize_min; 25540c16b537SWarner Losh return zc->headerSize; 25550c16b537SWarner Losh } 25560c16b537SWarner Losh 25570c16b537SWarner Losh 25580c16b537SWarner Losh static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize) 25590c16b537SWarner Losh { 25600c16b537SWarner Losh U32 magicNumber; 25610c16b537SWarner Losh if (srcSize < ZSTD_frameHeaderSize_min) return ZSTD_frameHeaderSize_max; 25620c16b537SWarner Losh magicNumber = MEM_readLE32(src); 25630c16b537SWarner Losh if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown); 25640c16b537SWarner Losh memset(params, 0, sizeof(*params)); 25650c16b537SWarner Losh params->windowLog = (((const BYTE*)src)[4] & 15) + ZSTD_WINDOWLOG_ABSOLUTEMIN; 25660c16b537SWarner Losh if ((((const BYTE*)src)[4] >> 4) != 0) return ERROR(frameParameter_unsupported); /* reserved bits */ 25670c16b537SWarner Losh return 0; 25680c16b537SWarner Losh } 25690c16b537SWarner Losh 25700c16b537SWarner Losh /** ZSTD_decodeFrameHeader_Part2 25710c16b537SWarner Losh * decode the full Frame Header 25720c16b537SWarner Losh * srcSize must be the size provided by ZSTD_decodeFrameHeader_Part1 25730c16b537SWarner Losh * @return : 0, or an error code, which can be tested using ZSTD_isError() */ 25740c16b537SWarner Losh static size_t ZSTD_decodeFrameHeader_Part2(ZSTD_DCtx* zc, const void* src, size_t srcSize) 25750c16b537SWarner Losh { 25760c16b537SWarner Losh size_t result; 25770c16b537SWarner Losh if (srcSize != zc->headerSize) return ERROR(srcSize_wrong); 25780c16b537SWarner Losh result = ZSTD_getFrameParams(&(zc->params), src, srcSize); 25790c16b537SWarner Losh if ((MEM_32bits()) && (zc->params.windowLog > 25)) return ERROR(frameParameter_unsupported); 25800c16b537SWarner Losh return result; 25810c16b537SWarner Losh } 25820c16b537SWarner Losh 25830c16b537SWarner Losh 25840c16b537SWarner Losh static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr) 25850c16b537SWarner Losh { 25860c16b537SWarner Losh const BYTE* const in = (const BYTE* const)src; 25870c16b537SWarner Losh BYTE headerFlags; 25880c16b537SWarner Losh U32 cSize; 25890c16b537SWarner Losh 25900c16b537SWarner Losh if (srcSize < 3) return ERROR(srcSize_wrong); 25910c16b537SWarner Losh 25920c16b537SWarner Losh headerFlags = *in; 25930c16b537SWarner Losh cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16); 25940c16b537SWarner Losh 25950c16b537SWarner Losh bpPtr->blockType = (blockType_t)(headerFlags >> 6); 25960c16b537SWarner Losh bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0; 25970c16b537SWarner Losh 25980c16b537SWarner Losh if (bpPtr->blockType == bt_end) return 0; 25990c16b537SWarner Losh if (bpPtr->blockType == bt_rle) return 1; 26000c16b537SWarner Losh return cSize; 26010c16b537SWarner Losh } 26020c16b537SWarner Losh 26030c16b537SWarner Losh static size_t ZSTD_copyRawBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 26040c16b537SWarner Losh { 26050c16b537SWarner Losh if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall); 2606*37f1f268SConrad Meyer if (srcSize > 0) { 26070c16b537SWarner Losh memcpy(dst, src, srcSize); 2608*37f1f268SConrad Meyer } 26090c16b537SWarner Losh return srcSize; 26100c16b537SWarner Losh } 26110c16b537SWarner Losh 26120c16b537SWarner Losh 26130c16b537SWarner Losh /** ZSTD_decompressLiterals 26140c16b537SWarner Losh @return : nb of bytes read from src, or an error code*/ 26150c16b537SWarner Losh static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr, 26160c16b537SWarner Losh const void* src, size_t srcSize) 26170c16b537SWarner Losh { 26180c16b537SWarner Losh const BYTE* ip = (const BYTE*)src; 26190c16b537SWarner Losh 26200c16b537SWarner Losh const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 26210c16b537SWarner Losh const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 26220c16b537SWarner Losh 26230c16b537SWarner Losh if (litSize > *maxDstSizePtr) return ERROR(corruption_detected); 26240c16b537SWarner Losh if (litCSize + 5 > srcSize) return ERROR(corruption_detected); 26250c16b537SWarner Losh 26260c16b537SWarner Losh if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected); 26270c16b537SWarner Losh 26280c16b537SWarner Losh *maxDstSizePtr = litSize; 26290c16b537SWarner Losh return litCSize + 5; 26300c16b537SWarner Losh } 26310c16b537SWarner Losh 26320c16b537SWarner Losh 26330c16b537SWarner Losh /** ZSTD_decodeLiteralsBlock 26340c16b537SWarner Losh @return : nb of bytes read from src (< srcSize ) */ 26350c16b537SWarner Losh static size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx, 26360c16b537SWarner Losh const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */ 26370c16b537SWarner Losh { 26380c16b537SWarner Losh const BYTE* const istart = (const BYTE*) src; 26390c16b537SWarner Losh 26400c16b537SWarner Losh /* any compressed block with literals segment must be at least this size */ 26410c16b537SWarner Losh if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected); 26420c16b537SWarner Losh 26430c16b537SWarner Losh switch(*istart & 3) 26440c16b537SWarner Losh { 26450c16b537SWarner Losh /* compressed */ 26460c16b537SWarner Losh case 0: 26470c16b537SWarner Losh { 26480c16b537SWarner Losh size_t litSize = BLOCKSIZE; 26490c16b537SWarner Losh const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize); 26500c16b537SWarner Losh dctx->litPtr = dctx->litBuffer; 26510c16b537SWarner Losh dctx->litSize = litSize; 26520c16b537SWarner Losh memset(dctx->litBuffer + dctx->litSize, 0, 8); 26530c16b537SWarner Losh return readSize; /* works if it's an error too */ 26540c16b537SWarner Losh } 26550c16b537SWarner Losh case IS_RAW: 26560c16b537SWarner Losh { 26570c16b537SWarner Losh const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 26580c16b537SWarner Losh if (litSize > srcSize-11) /* risk of reading too far with wildcopy */ 26590c16b537SWarner Losh { 26609cbefe25SConrad Meyer if (litSize > BLOCKSIZE) return ERROR(corruption_detected); 26610c16b537SWarner Losh if (litSize > srcSize-3) return ERROR(corruption_detected); 26620c16b537SWarner Losh memcpy(dctx->litBuffer, istart, litSize); 26630c16b537SWarner Losh dctx->litPtr = dctx->litBuffer; 26640c16b537SWarner Losh dctx->litSize = litSize; 26650c16b537SWarner Losh memset(dctx->litBuffer + dctx->litSize, 0, 8); 26660c16b537SWarner Losh return litSize+3; 26670c16b537SWarner Losh } 26680c16b537SWarner Losh /* direct reference into compressed stream */ 26690c16b537SWarner Losh dctx->litPtr = istart+3; 26700c16b537SWarner Losh dctx->litSize = litSize; 26710c16b537SWarner Losh return litSize+3; } 26720c16b537SWarner Losh case IS_RLE: 26730c16b537SWarner Losh { 26740c16b537SWarner Losh const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 26750c16b537SWarner Losh if (litSize > BLOCKSIZE) return ERROR(corruption_detected); 26760c16b537SWarner Losh memset(dctx->litBuffer, istart[3], litSize + 8); 26770c16b537SWarner Losh dctx->litPtr = dctx->litBuffer; 26780c16b537SWarner Losh dctx->litSize = litSize; 26790c16b537SWarner Losh return 4; 26800c16b537SWarner Losh } 26810c16b537SWarner Losh default: 26820c16b537SWarner Losh return ERROR(corruption_detected); /* forbidden nominal case */ 26830c16b537SWarner Losh } 26840c16b537SWarner Losh } 26850c16b537SWarner Losh 26860c16b537SWarner Losh 26870c16b537SWarner Losh static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr, 26880c16b537SWarner Losh FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb, 26890c16b537SWarner Losh const void* src, size_t srcSize) 26900c16b537SWarner Losh { 26910c16b537SWarner Losh const BYTE* const istart = (const BYTE* const)src; 26920c16b537SWarner Losh const BYTE* ip = istart; 26930c16b537SWarner Losh const BYTE* const iend = istart + srcSize; 26940c16b537SWarner Losh U32 LLtype, Offtype, MLtype; 26950c16b537SWarner Losh U32 LLlog, Offlog, MLlog; 26960c16b537SWarner Losh size_t dumpsLength; 26970c16b537SWarner Losh 26980c16b537SWarner Losh /* check */ 26990c16b537SWarner Losh if (srcSize < 5) return ERROR(srcSize_wrong); 27000c16b537SWarner Losh 27010c16b537SWarner Losh /* SeqHead */ 27020c16b537SWarner Losh *nbSeq = MEM_readLE16(ip); ip+=2; 27030c16b537SWarner Losh LLtype = *ip >> 6; 27040c16b537SWarner Losh Offtype = (*ip >> 4) & 3; 27050c16b537SWarner Losh MLtype = (*ip >> 2) & 3; 27060c16b537SWarner Losh if (*ip & 2) 27070c16b537SWarner Losh { 27080c16b537SWarner Losh dumpsLength = ip[2]; 27090c16b537SWarner Losh dumpsLength += ip[1] << 8; 27100c16b537SWarner Losh ip += 3; 27110c16b537SWarner Losh } 27120c16b537SWarner Losh else 27130c16b537SWarner Losh { 27140c16b537SWarner Losh dumpsLength = ip[1]; 27150c16b537SWarner Losh dumpsLength += (ip[0] & 1) << 8; 27160c16b537SWarner Losh ip += 2; 27170c16b537SWarner Losh } 27180c16b537SWarner Losh *dumpsPtr = ip; 27190c16b537SWarner Losh ip += dumpsLength; 27200c16b537SWarner Losh *dumpsLengthPtr = dumpsLength; 27210c16b537SWarner Losh 27220c16b537SWarner Losh /* check */ 27230c16b537SWarner Losh if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */ 27240c16b537SWarner Losh 27250c16b537SWarner Losh /* sequences */ 27260c16b537SWarner Losh { 27270c16b537SWarner Losh S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL >= MaxOff */ 27280c16b537SWarner Losh size_t headerSize; 27290c16b537SWarner Losh 27300c16b537SWarner Losh /* Build DTables */ 27310c16b537SWarner Losh switch(LLtype) 27320c16b537SWarner Losh { 27330c16b537SWarner Losh case bt_rle : 27340c16b537SWarner Losh LLlog = 0; 27350c16b537SWarner Losh FSE_buildDTable_rle(DTableLL, *ip++); break; 27360c16b537SWarner Losh case bt_raw : 27370c16b537SWarner Losh LLlog = LLbits; 27380c16b537SWarner Losh FSE_buildDTable_raw(DTableLL, LLbits); break; 27390c16b537SWarner Losh default : 27400c16b537SWarner Losh { U32 max = MaxLL; 27410c16b537SWarner Losh headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip); 27420c16b537SWarner Losh if (FSE_isError(headerSize)) return ERROR(GENERIC); 27430c16b537SWarner Losh if (LLlog > LLFSELog) return ERROR(corruption_detected); 27440c16b537SWarner Losh ip += headerSize; 27450c16b537SWarner Losh FSE_buildDTable(DTableLL, norm, max, LLlog); 27460c16b537SWarner Losh } } 27470c16b537SWarner Losh 27480c16b537SWarner Losh switch(Offtype) 27490c16b537SWarner Losh { 27500c16b537SWarner Losh case bt_rle : 27510c16b537SWarner Losh Offlog = 0; 27520c16b537SWarner Losh if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 27530c16b537SWarner Losh FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */ 27540c16b537SWarner Losh break; 27550c16b537SWarner Losh case bt_raw : 27560c16b537SWarner Losh Offlog = Offbits; 27570c16b537SWarner Losh FSE_buildDTable_raw(DTableOffb, Offbits); break; 27580c16b537SWarner Losh default : 27590c16b537SWarner Losh { U32 max = MaxOff; 27600c16b537SWarner Losh headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip); 27610c16b537SWarner Losh if (FSE_isError(headerSize)) return ERROR(GENERIC); 27620c16b537SWarner Losh if (Offlog > OffFSELog) return ERROR(corruption_detected); 27630c16b537SWarner Losh ip += headerSize; 27640c16b537SWarner Losh FSE_buildDTable(DTableOffb, norm, max, Offlog); 27650c16b537SWarner Losh } } 27660c16b537SWarner Losh 27670c16b537SWarner Losh switch(MLtype) 27680c16b537SWarner Losh { 27690c16b537SWarner Losh case bt_rle : 27700c16b537SWarner Losh MLlog = 0; 27710c16b537SWarner Losh if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 27720c16b537SWarner Losh FSE_buildDTable_rle(DTableML, *ip++); break; 27730c16b537SWarner Losh case bt_raw : 27740c16b537SWarner Losh MLlog = MLbits; 27750c16b537SWarner Losh FSE_buildDTable_raw(DTableML, MLbits); break; 27760c16b537SWarner Losh default : 27770c16b537SWarner Losh { U32 max = MaxML; 27780c16b537SWarner Losh headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip); 27790c16b537SWarner Losh if (FSE_isError(headerSize)) return ERROR(GENERIC); 27800c16b537SWarner Losh if (MLlog > MLFSELog) return ERROR(corruption_detected); 27810c16b537SWarner Losh ip += headerSize; 27820c16b537SWarner Losh FSE_buildDTable(DTableML, norm, max, MLlog); 27830c16b537SWarner Losh } } } 27840c16b537SWarner Losh 27850c16b537SWarner Losh return ip-istart; 27860c16b537SWarner Losh } 27870c16b537SWarner Losh 27880c16b537SWarner Losh 27890c16b537SWarner Losh typedef struct { 27900c16b537SWarner Losh size_t litLength; 27910c16b537SWarner Losh size_t offset; 27920c16b537SWarner Losh size_t matchLength; 27930c16b537SWarner Losh } seq_t; 27940c16b537SWarner Losh 27950c16b537SWarner Losh typedef struct { 27960c16b537SWarner Losh BIT_DStream_t DStream; 27970c16b537SWarner Losh FSE_DState_t stateLL; 27980c16b537SWarner Losh FSE_DState_t stateOffb; 27990c16b537SWarner Losh FSE_DState_t stateML; 28000c16b537SWarner Losh size_t prevOffset; 28010c16b537SWarner Losh const BYTE* dumps; 28020c16b537SWarner Losh const BYTE* dumpsEnd; 28030c16b537SWarner Losh } seqState_t; 28040c16b537SWarner Losh 28050c16b537SWarner Losh 28060c16b537SWarner Losh static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState) 28070c16b537SWarner Losh { 28080c16b537SWarner Losh size_t litLength; 28090c16b537SWarner Losh size_t prevOffset; 28100c16b537SWarner Losh size_t offset; 28110c16b537SWarner Losh size_t matchLength; 28120c16b537SWarner Losh const BYTE* dumps = seqState->dumps; 28130c16b537SWarner Losh const BYTE* const de = seqState->dumpsEnd; 28140c16b537SWarner Losh 28150c16b537SWarner Losh /* Literal length */ 28160c16b537SWarner Losh litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream)); 28170c16b537SWarner Losh prevOffset = litLength ? seq->offset : seqState->prevOffset; 28180c16b537SWarner Losh if (litLength == MaxLL) { 28194d3f1eafSConrad Meyer const U32 add = dumps<de ? *dumps++ : 0; 28200c16b537SWarner Losh if (add < 255) litLength += add; 28214d3f1eafSConrad Meyer else if (dumps + 3 <= de) { 28224d3f1eafSConrad Meyer litLength = MEM_readLE24(dumps); 28230c16b537SWarner Losh dumps += 3; 28240c16b537SWarner Losh } 28250c16b537SWarner Losh if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */ 28260c16b537SWarner Losh } 28270c16b537SWarner Losh 28280c16b537SWarner Losh /* Offset */ 28290c16b537SWarner Losh { static const U32 offsetPrefix[MaxOff+1] = { 28300c16b537SWarner Losh 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256, 28310c16b537SWarner Losh 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 28320c16b537SWarner Losh 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 }; 28330c16b537SWarner Losh U32 offsetCode, nbBits; 28340c16b537SWarner Losh offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */ 28350c16b537SWarner Losh if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream)); 28360c16b537SWarner Losh nbBits = offsetCode - 1; 28370c16b537SWarner Losh if (offsetCode==0) nbBits = 0; /* cmove */ 28380c16b537SWarner Losh offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits); 28390c16b537SWarner Losh if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream)); 28400c16b537SWarner Losh if (offsetCode==0) offset = prevOffset; /* cmove */ 28410c16b537SWarner Losh if (offsetCode | !litLength) seqState->prevOffset = seq->offset; /* cmove */ 28420c16b537SWarner Losh } 28430c16b537SWarner Losh 28440c16b537SWarner Losh /* MatchLength */ 28450c16b537SWarner Losh matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream)); 28460c16b537SWarner Losh if (matchLength == MaxML) { 28474d3f1eafSConrad Meyer const U32 add = dumps<de ? *dumps++ : 0; 28480c16b537SWarner Losh if (add < 255) matchLength += add; 28494d3f1eafSConrad Meyer else if (dumps + 3 <= de){ 28504d3f1eafSConrad Meyer matchLength = MEM_readLE24(dumps); 28510c16b537SWarner Losh dumps += 3; 28520c16b537SWarner Losh } 28530c16b537SWarner Losh if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */ 28540c16b537SWarner Losh } 28550c16b537SWarner Losh matchLength += MINMATCH; 28560c16b537SWarner Losh 28570c16b537SWarner Losh /* save result */ 28580c16b537SWarner Losh seq->litLength = litLength; 28590c16b537SWarner Losh seq->offset = offset; 28600c16b537SWarner Losh seq->matchLength = matchLength; 28610c16b537SWarner Losh seqState->dumps = dumps; 28620c16b537SWarner Losh } 28630c16b537SWarner Losh 28640c16b537SWarner Losh 28650c16b537SWarner Losh static size_t ZSTD_execSequence(BYTE* op, 28660c16b537SWarner Losh BYTE* const oend, seq_t sequence, 28670c16b537SWarner Losh const BYTE** litPtr, const BYTE* const litLimit, 28680c16b537SWarner Losh const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd) 28690c16b537SWarner Losh { 28700c16b537SWarner Losh static const int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */ 28712b9c00cbSConrad Meyer static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */ 28720c16b537SWarner Losh BYTE* const oLitEnd = op + sequence.litLength; 28730c16b537SWarner Losh const size_t sequenceLength = sequence.litLength + sequence.matchLength; 28740c16b537SWarner Losh BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */ 28750c16b537SWarner Losh BYTE* const oend_8 = oend-8; 28760c16b537SWarner Losh const BYTE* const litEnd = *litPtr + sequence.litLength; 28770c16b537SWarner Losh const BYTE* match = oLitEnd - sequence.offset; 28780c16b537SWarner Losh 28790c16b537SWarner Losh /* check */ 28800c16b537SWarner Losh if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */ 28810c16b537SWarner Losh if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */ 28820c16b537SWarner Losh if (litEnd > litLimit) return ERROR(corruption_detected); /* risk read beyond lit buffer */ 28830c16b537SWarner Losh 28840c16b537SWarner Losh /* copy Literals */ 28850c16b537SWarner Losh ZSTD_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */ 28860c16b537SWarner Losh op = oLitEnd; 28870c16b537SWarner Losh *litPtr = litEnd; /* update for next sequence */ 28880c16b537SWarner Losh 28890c16b537SWarner Losh /* copy Match */ 28900c16b537SWarner Losh if (sequence.offset > (size_t)(oLitEnd - base)) 28910c16b537SWarner Losh { 28920c16b537SWarner Losh /* offset beyond prefix */ 28930c16b537SWarner Losh if (sequence.offset > (size_t)(oLitEnd - vBase)) 28940c16b537SWarner Losh return ERROR(corruption_detected); 28950c16b537SWarner Losh match = dictEnd - (base-match); 28960c16b537SWarner Losh if (match + sequence.matchLength <= dictEnd) 28970c16b537SWarner Losh { 28980c16b537SWarner Losh memmove(oLitEnd, match, sequence.matchLength); 28990c16b537SWarner Losh return sequenceLength; 29000c16b537SWarner Losh } 29010c16b537SWarner Losh /* span extDict & currentPrefixSegment */ 29020c16b537SWarner Losh { 29030c16b537SWarner Losh size_t length1 = dictEnd - match; 29040c16b537SWarner Losh memmove(oLitEnd, match, length1); 29050c16b537SWarner Losh op = oLitEnd + length1; 29060c16b537SWarner Losh sequence.matchLength -= length1; 29070c16b537SWarner Losh match = base; 29080c16b537SWarner Losh if (op > oend_8 || sequence.matchLength < MINMATCH) { 29090c16b537SWarner Losh while (op < oMatchEnd) *op++ = *match++; 29100c16b537SWarner Losh return sequenceLength; 29110c16b537SWarner Losh } 29120c16b537SWarner Losh } 29130c16b537SWarner Losh } 29140c16b537SWarner Losh /* Requirement: op <= oend_8 */ 29150c16b537SWarner Losh 29160c16b537SWarner Losh /* match within prefix */ 29170c16b537SWarner Losh if (sequence.offset < 8) { 29180c16b537SWarner Losh /* close range match, overlap */ 29190c16b537SWarner Losh const int sub2 = dec64table[sequence.offset]; 29200c16b537SWarner Losh op[0] = match[0]; 29210c16b537SWarner Losh op[1] = match[1]; 29220c16b537SWarner Losh op[2] = match[2]; 29230c16b537SWarner Losh op[3] = match[3]; 29240c16b537SWarner Losh match += dec32table[sequence.offset]; 29250c16b537SWarner Losh ZSTD_copy4(op+4, match); 29260c16b537SWarner Losh match -= sub2; 29270c16b537SWarner Losh } else { 29280c16b537SWarner Losh ZSTD_copy8(op, match); 29290c16b537SWarner Losh } 29300c16b537SWarner Losh op += 8; match += 8; 29310c16b537SWarner Losh 29320c16b537SWarner Losh if (oMatchEnd > oend-(16-MINMATCH)) 29330c16b537SWarner Losh { 29340c16b537SWarner Losh if (op < oend_8) 29350c16b537SWarner Losh { 29360c16b537SWarner Losh ZSTD_wildcopy(op, match, oend_8 - op); 29370c16b537SWarner Losh match += oend_8 - op; 29380c16b537SWarner Losh op = oend_8; 29390c16b537SWarner Losh } 29400c16b537SWarner Losh while (op < oMatchEnd) *op++ = *match++; 29410c16b537SWarner Losh } 29420c16b537SWarner Losh else 29430c16b537SWarner Losh { 29440f743729SConrad Meyer ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8, but must be signed */ 29450c16b537SWarner Losh } 29460c16b537SWarner Losh return sequenceLength; 29470c16b537SWarner Losh } 29480c16b537SWarner Losh 29490c16b537SWarner Losh 29500c16b537SWarner Losh static size_t ZSTD_decompressSequences( 29510c16b537SWarner Losh ZSTD_DCtx* dctx, 29520c16b537SWarner Losh void* dst, size_t maxDstSize, 29530c16b537SWarner Losh const void* seqStart, size_t seqSize) 29540c16b537SWarner Losh { 29550c16b537SWarner Losh const BYTE* ip = (const BYTE*)seqStart; 29560c16b537SWarner Losh const BYTE* const iend = ip + seqSize; 29570c16b537SWarner Losh BYTE* const ostart = (BYTE* const)dst; 29580c16b537SWarner Losh BYTE* op = ostart; 29590c16b537SWarner Losh BYTE* const oend = ostart + maxDstSize; 29600c16b537SWarner Losh size_t errorCode, dumpsLength; 29610c16b537SWarner Losh const BYTE* litPtr = dctx->litPtr; 29620c16b537SWarner Losh const BYTE* const litEnd = litPtr + dctx->litSize; 29630c16b537SWarner Losh int nbSeq; 29640c16b537SWarner Losh const BYTE* dumps; 29650c16b537SWarner Losh U32* DTableLL = dctx->LLTable; 29660c16b537SWarner Losh U32* DTableML = dctx->MLTable; 29670c16b537SWarner Losh U32* DTableOffb = dctx->OffTable; 29680c16b537SWarner Losh const BYTE* const base = (const BYTE*) (dctx->base); 29690c16b537SWarner Losh const BYTE* const vBase = (const BYTE*) (dctx->vBase); 29700c16b537SWarner Losh const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd); 29710c16b537SWarner Losh 29720c16b537SWarner Losh /* Build Decoding Tables */ 29730c16b537SWarner Losh errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength, 29740c16b537SWarner Losh DTableLL, DTableML, DTableOffb, 29750c16b537SWarner Losh ip, iend-ip); 29760c16b537SWarner Losh if (ZSTD_isError(errorCode)) return errorCode; 29770c16b537SWarner Losh ip += errorCode; 29780c16b537SWarner Losh 29790c16b537SWarner Losh /* Regen sequences */ 29800c16b537SWarner Losh { 29810c16b537SWarner Losh seq_t sequence; 29820c16b537SWarner Losh seqState_t seqState; 29830c16b537SWarner Losh 29840c16b537SWarner Losh memset(&sequence, 0, sizeof(sequence)); 29850c16b537SWarner Losh sequence.offset = 4; 29860c16b537SWarner Losh seqState.dumps = dumps; 29870c16b537SWarner Losh seqState.dumpsEnd = dumps + dumpsLength; 29880c16b537SWarner Losh seqState.prevOffset = 4; 29890c16b537SWarner Losh errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip); 29900c16b537SWarner Losh if (ERR_isError(errorCode)) return ERROR(corruption_detected); 29910c16b537SWarner Losh FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL); 29920c16b537SWarner Losh FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb); 29930c16b537SWarner Losh FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML); 29940c16b537SWarner Losh 29950c16b537SWarner Losh for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; ) 29960c16b537SWarner Losh { 29970c16b537SWarner Losh size_t oneSeqSize; 29980c16b537SWarner Losh nbSeq--; 29990c16b537SWarner Losh ZSTD_decodeSequence(&sequence, &seqState); 30000c16b537SWarner Losh oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd); 30010c16b537SWarner Losh if (ZSTD_isError(oneSeqSize)) return oneSeqSize; 30020c16b537SWarner Losh op += oneSeqSize; 30030c16b537SWarner Losh } 30040c16b537SWarner Losh 30050c16b537SWarner Losh /* check if reached exact end */ 30060c16b537SWarner Losh if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* DStream should be entirely and exactly consumed; otherwise data is corrupted */ 30070c16b537SWarner Losh 30080c16b537SWarner Losh /* last literal segment */ 30090c16b537SWarner Losh { 30100c16b537SWarner Losh size_t lastLLSize = litEnd - litPtr; 30110c16b537SWarner Losh if (litPtr > litEnd) return ERROR(corruption_detected); 30120c16b537SWarner Losh if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall); 3013*37f1f268SConrad Meyer if (lastLLSize > 0) { 30140c16b537SWarner Losh if (op != litPtr) memcpy(op, litPtr, lastLLSize); 30150c16b537SWarner Losh op += lastLLSize; 30160c16b537SWarner Losh } 30170c16b537SWarner Losh } 3018*37f1f268SConrad Meyer } 30190c16b537SWarner Losh 30200c16b537SWarner Losh return op-ostart; 30210c16b537SWarner Losh } 30220c16b537SWarner Losh 30230c16b537SWarner Losh 30240c16b537SWarner Losh static void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst) 30250c16b537SWarner Losh { 30260c16b537SWarner Losh if (dst != dctx->previousDstEnd) /* not contiguous */ 30270c16b537SWarner Losh { 30280c16b537SWarner Losh dctx->dictEnd = dctx->previousDstEnd; 30290c16b537SWarner Losh dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); 30300c16b537SWarner Losh dctx->base = dst; 30310c16b537SWarner Losh dctx->previousDstEnd = dst; 30320c16b537SWarner Losh } 30330c16b537SWarner Losh } 30340c16b537SWarner Losh 30350c16b537SWarner Losh 30360c16b537SWarner Losh static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx, 30370c16b537SWarner Losh void* dst, size_t maxDstSize, 30380c16b537SWarner Losh const void* src, size_t srcSize) 30390c16b537SWarner Losh { 30400c16b537SWarner Losh /* blockType == blockCompressed */ 30410c16b537SWarner Losh const BYTE* ip = (const BYTE*)src; 30429cbefe25SConrad Meyer size_t litCSize; 30439cbefe25SConrad Meyer 30449cbefe25SConrad Meyer if (srcSize > BLOCKSIZE) return ERROR(corruption_detected); 30450c16b537SWarner Losh 30460c16b537SWarner Losh /* Decode literals sub-block */ 30479cbefe25SConrad Meyer litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize); 30480c16b537SWarner Losh if (ZSTD_isError(litCSize)) return litCSize; 30490c16b537SWarner Losh ip += litCSize; 30500c16b537SWarner Losh srcSize -= litCSize; 30510c16b537SWarner Losh 30520c16b537SWarner Losh return ZSTD_decompressSequences(dctx, dst, maxDstSize, ip, srcSize); 30530c16b537SWarner Losh } 30540c16b537SWarner Losh 30550c16b537SWarner Losh 30560c16b537SWarner Losh static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx, 30570c16b537SWarner Losh void* dst, size_t maxDstSize, 30580c16b537SWarner Losh const void* src, size_t srcSize, 30590c16b537SWarner Losh const void* dict, size_t dictSize) 30600c16b537SWarner Losh { 30610c16b537SWarner Losh const BYTE* ip = (const BYTE*)src; 30620c16b537SWarner Losh const BYTE* iend = ip + srcSize; 30630c16b537SWarner Losh BYTE* const ostart = (BYTE* const)dst; 30640c16b537SWarner Losh BYTE* op = ostart; 30650c16b537SWarner Losh BYTE* const oend = ostart + maxDstSize; 30660c16b537SWarner Losh size_t remainingSize = srcSize; 30670c16b537SWarner Losh blockProperties_t blockProperties; 30680c16b537SWarner Losh 30690c16b537SWarner Losh /* init */ 30700c16b537SWarner Losh ZSTD_resetDCtx(ctx); 30710c16b537SWarner Losh if (dict) 30720c16b537SWarner Losh { 30730c16b537SWarner Losh ZSTD_decompress_insertDictionary(ctx, dict, dictSize); 30740c16b537SWarner Losh ctx->dictEnd = ctx->previousDstEnd; 30750c16b537SWarner Losh ctx->vBase = (const char*)dst - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base)); 30760c16b537SWarner Losh ctx->base = dst; 30770c16b537SWarner Losh } 30780c16b537SWarner Losh else 30790c16b537SWarner Losh { 30800c16b537SWarner Losh ctx->vBase = ctx->base = ctx->dictEnd = dst; 30810c16b537SWarner Losh } 30820c16b537SWarner Losh 30830c16b537SWarner Losh /* Frame Header */ 30840c16b537SWarner Losh { 30850c16b537SWarner Losh size_t frameHeaderSize; 30860c16b537SWarner Losh if (srcSize < ZSTD_frameHeaderSize_min+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong); 30870c16b537SWarner Losh frameHeaderSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min); 30880c16b537SWarner Losh if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize; 30890c16b537SWarner Losh if (srcSize < frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong); 30900c16b537SWarner Losh ip += frameHeaderSize; remainingSize -= frameHeaderSize; 30910c16b537SWarner Losh frameHeaderSize = ZSTD_decodeFrameHeader_Part2(ctx, src, frameHeaderSize); 30920c16b537SWarner Losh if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize; 30930c16b537SWarner Losh } 30940c16b537SWarner Losh 30950c16b537SWarner Losh /* Loop on each block */ 30960c16b537SWarner Losh while (1) 30970c16b537SWarner Losh { 30980c16b537SWarner Losh size_t decodedSize=0; 30990c16b537SWarner Losh size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties); 31000c16b537SWarner Losh if (ZSTD_isError(cBlockSize)) return cBlockSize; 31010c16b537SWarner Losh 31020c16b537SWarner Losh ip += ZSTD_blockHeaderSize; 31030c16b537SWarner Losh remainingSize -= ZSTD_blockHeaderSize; 31040c16b537SWarner Losh if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); 31050c16b537SWarner Losh 31060c16b537SWarner Losh switch(blockProperties.blockType) 31070c16b537SWarner Losh { 31080c16b537SWarner Losh case bt_compressed: 31090c16b537SWarner Losh decodedSize = ZSTD_decompressBlock_internal(ctx, op, oend-op, ip, cBlockSize); 31100c16b537SWarner Losh break; 31110c16b537SWarner Losh case bt_raw : 31120c16b537SWarner Losh decodedSize = ZSTD_copyRawBlock(op, oend-op, ip, cBlockSize); 31130c16b537SWarner Losh break; 31140c16b537SWarner Losh case bt_rle : 31150c16b537SWarner Losh return ERROR(GENERIC); /* not yet supported */ 31160c16b537SWarner Losh break; 31170c16b537SWarner Losh case bt_end : 31180c16b537SWarner Losh /* end of frame */ 31190c16b537SWarner Losh if (remainingSize) return ERROR(srcSize_wrong); 31200c16b537SWarner Losh break; 31210c16b537SWarner Losh default: 31220c16b537SWarner Losh return ERROR(GENERIC); /* impossible */ 31230c16b537SWarner Losh } 31240c16b537SWarner Losh if (cBlockSize == 0) break; /* bt_end */ 31250c16b537SWarner Losh 31260c16b537SWarner Losh if (ZSTD_isError(decodedSize)) return decodedSize; 31270c16b537SWarner Losh op += decodedSize; 31280c16b537SWarner Losh ip += cBlockSize; 31290c16b537SWarner Losh remainingSize -= cBlockSize; 31300c16b537SWarner Losh } 31310c16b537SWarner Losh 31320c16b537SWarner Losh return op-ostart; 31330c16b537SWarner Losh } 31340c16b537SWarner Losh 31352b9c00cbSConrad Meyer /* ZSTD_errorFrameSizeInfoLegacy() : 31362b9c00cbSConrad Meyer assumes `cSize` and `dBound` are _not_ NULL */ 31372b9c00cbSConrad Meyer static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret) 31382b9c00cbSConrad Meyer { 31392b9c00cbSConrad Meyer *cSize = ret; 31402b9c00cbSConrad Meyer *dBound = ZSTD_CONTENTSIZE_ERROR; 31412b9c00cbSConrad Meyer } 31422b9c00cbSConrad Meyer 31432b9c00cbSConrad Meyer void ZSTDv04_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound) 31440c16b537SWarner Losh { 31450c16b537SWarner Losh const BYTE* ip = (const BYTE*)src; 31460c16b537SWarner Losh size_t remainingSize = srcSize; 31472b9c00cbSConrad Meyer size_t nbBlocks = 0; 31480c16b537SWarner Losh blockProperties_t blockProperties; 31490c16b537SWarner Losh 31500c16b537SWarner Losh /* Frame Header */ 31512b9c00cbSConrad Meyer if (srcSize < ZSTD_frameHeaderSize_min) { 31522b9c00cbSConrad Meyer ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 31532b9c00cbSConrad Meyer return; 31542b9c00cbSConrad Meyer } 31552b9c00cbSConrad Meyer if (MEM_readLE32(src) != ZSTD_MAGICNUMBER) { 31562b9c00cbSConrad Meyer ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown)); 31572b9c00cbSConrad Meyer return; 31582b9c00cbSConrad Meyer } 31590c16b537SWarner Losh ip += ZSTD_frameHeaderSize_min; remainingSize -= ZSTD_frameHeaderSize_min; 31600c16b537SWarner Losh 31610c16b537SWarner Losh /* Loop on each block */ 31620c16b537SWarner Losh while (1) 31630c16b537SWarner Losh { 31640c16b537SWarner Losh size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties); 31652b9c00cbSConrad Meyer if (ZSTD_isError(cBlockSize)) { 31662b9c00cbSConrad Meyer ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize); 31672b9c00cbSConrad Meyer return; 31682b9c00cbSConrad Meyer } 31690c16b537SWarner Losh 31700c16b537SWarner Losh ip += ZSTD_blockHeaderSize; 31710c16b537SWarner Losh remainingSize -= ZSTD_blockHeaderSize; 31722b9c00cbSConrad Meyer if (cBlockSize > remainingSize) { 31732b9c00cbSConrad Meyer ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 31742b9c00cbSConrad Meyer return; 31752b9c00cbSConrad Meyer } 31760c16b537SWarner Losh 31770c16b537SWarner Losh if (cBlockSize == 0) break; /* bt_end */ 31780c16b537SWarner Losh 31790c16b537SWarner Losh ip += cBlockSize; 31800c16b537SWarner Losh remainingSize -= cBlockSize; 31812b9c00cbSConrad Meyer nbBlocks++; 31820c16b537SWarner Losh } 31830c16b537SWarner Losh 31842b9c00cbSConrad Meyer *cSize = ip - (const BYTE*)src; 31852b9c00cbSConrad Meyer *dBound = nbBlocks * BLOCKSIZE; 31860c16b537SWarner Losh } 31870c16b537SWarner Losh 31880c16b537SWarner Losh /* ****************************** 31890c16b537SWarner Losh * Streaming Decompression API 31900c16b537SWarner Losh ********************************/ 31910c16b537SWarner Losh static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx) 31920c16b537SWarner Losh { 31930c16b537SWarner Losh return dctx->expected; 31940c16b537SWarner Losh } 31950c16b537SWarner Losh 31960c16b537SWarner Losh static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 31970c16b537SWarner Losh { 31980c16b537SWarner Losh /* Sanity check */ 31990c16b537SWarner Losh if (srcSize != ctx->expected) return ERROR(srcSize_wrong); 32000c16b537SWarner Losh ZSTD_checkContinuity(ctx, dst); 32010c16b537SWarner Losh 32020c16b537SWarner Losh /* Decompress : frame header; part 1 */ 32030c16b537SWarner Losh switch (ctx->stage) 32040c16b537SWarner Losh { 32050c16b537SWarner Losh case ZSTDds_getFrameHeaderSize : 32060c16b537SWarner Losh /* get frame header size */ 32070c16b537SWarner Losh if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */ 32080c16b537SWarner Losh ctx->headerSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min); 32090c16b537SWarner Losh if (ZSTD_isError(ctx->headerSize)) return ctx->headerSize; 32100c16b537SWarner Losh memcpy(ctx->headerBuffer, src, ZSTD_frameHeaderSize_min); 32110c16b537SWarner Losh if (ctx->headerSize > ZSTD_frameHeaderSize_min) return ERROR(GENERIC); /* impossible */ 32120c16b537SWarner Losh ctx->expected = 0; /* not necessary to copy more */ 32130c16b537SWarner Losh /* fallthrough */ 32140c16b537SWarner Losh case ZSTDds_decodeFrameHeader: 32150c16b537SWarner Losh /* get frame header */ 32160c16b537SWarner Losh { size_t const result = ZSTD_decodeFrameHeader_Part2(ctx, ctx->headerBuffer, ctx->headerSize); 32170c16b537SWarner Losh if (ZSTD_isError(result)) return result; 32180c16b537SWarner Losh ctx->expected = ZSTD_blockHeaderSize; 32190c16b537SWarner Losh ctx->stage = ZSTDds_decodeBlockHeader; 32200c16b537SWarner Losh return 0; 32210c16b537SWarner Losh } 32220c16b537SWarner Losh case ZSTDds_decodeBlockHeader: 32230c16b537SWarner Losh /* Decode block header */ 32240c16b537SWarner Losh { blockProperties_t bp; 32250c16b537SWarner Losh size_t const blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp); 32260c16b537SWarner Losh if (ZSTD_isError(blockSize)) return blockSize; 32270c16b537SWarner Losh if (bp.blockType == bt_end) 32280c16b537SWarner Losh { 32290c16b537SWarner Losh ctx->expected = 0; 32300c16b537SWarner Losh ctx->stage = ZSTDds_getFrameHeaderSize; 32310c16b537SWarner Losh } 32320c16b537SWarner Losh else 32330c16b537SWarner Losh { 32340c16b537SWarner Losh ctx->expected = blockSize; 32350c16b537SWarner Losh ctx->bType = bp.blockType; 32360c16b537SWarner Losh ctx->stage = ZSTDds_decompressBlock; 32370c16b537SWarner Losh } 32380c16b537SWarner Losh return 0; 32390c16b537SWarner Losh } 32400c16b537SWarner Losh case ZSTDds_decompressBlock: 32410c16b537SWarner Losh { 32420c16b537SWarner Losh /* Decompress : block content */ 32430c16b537SWarner Losh size_t rSize; 32440c16b537SWarner Losh switch(ctx->bType) 32450c16b537SWarner Losh { 32460c16b537SWarner Losh case bt_compressed: 32470c16b537SWarner Losh rSize = ZSTD_decompressBlock_internal(ctx, dst, maxDstSize, src, srcSize); 32480c16b537SWarner Losh break; 32490c16b537SWarner Losh case bt_raw : 32500c16b537SWarner Losh rSize = ZSTD_copyRawBlock(dst, maxDstSize, src, srcSize); 32510c16b537SWarner Losh break; 32520c16b537SWarner Losh case bt_rle : 32530c16b537SWarner Losh return ERROR(GENERIC); /* not yet handled */ 32540c16b537SWarner Losh break; 32550c16b537SWarner Losh case bt_end : /* should never happen (filtered at phase 1) */ 32560c16b537SWarner Losh rSize = 0; 32570c16b537SWarner Losh break; 32580c16b537SWarner Losh default: 32590c16b537SWarner Losh return ERROR(GENERIC); 32600c16b537SWarner Losh } 32610c16b537SWarner Losh ctx->stage = ZSTDds_decodeBlockHeader; 32620c16b537SWarner Losh ctx->expected = ZSTD_blockHeaderSize; 32630c16b537SWarner Losh ctx->previousDstEnd = (char*)dst + rSize; 32640c16b537SWarner Losh return rSize; 32650c16b537SWarner Losh } 32660c16b537SWarner Losh default: 32670c16b537SWarner Losh return ERROR(GENERIC); /* impossible */ 32680c16b537SWarner Losh } 32690c16b537SWarner Losh } 32700c16b537SWarner Losh 32710c16b537SWarner Losh 32720c16b537SWarner Losh static void ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* dict, size_t dictSize) 32730c16b537SWarner Losh { 32740c16b537SWarner Losh ctx->dictEnd = ctx->previousDstEnd; 32750c16b537SWarner Losh ctx->vBase = (const char*)dict - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base)); 32760c16b537SWarner Losh ctx->base = dict; 32770c16b537SWarner Losh ctx->previousDstEnd = (const char*)dict + dictSize; 32780c16b537SWarner Losh } 32790c16b537SWarner Losh 32800c16b537SWarner Losh 32810c16b537SWarner Losh 32820c16b537SWarner Losh /* 32830c16b537SWarner Losh Buffered version of Zstd compression library 32840c16b537SWarner Losh Copyright (C) 2015, Yann Collet. 32850c16b537SWarner Losh 32860c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 32870c16b537SWarner Losh 32880c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 32890c16b537SWarner Losh modification, are permitted provided that the following conditions are 32900c16b537SWarner Losh met: 32910c16b537SWarner Losh * Redistributions of source code must retain the above copyright 32920c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 32930c16b537SWarner Losh * Redistributions in binary form must reproduce the above 32940c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 32950c16b537SWarner Losh in the documentation and/or other materials provided with the 32960c16b537SWarner Losh distribution. 32970c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 32980c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 32990c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 33000c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 33010c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 33020c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 33030c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 33040c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33050c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 33060c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 33070c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 33080c16b537SWarner Losh 33090c16b537SWarner Losh You can contact the author at : 33100c16b537SWarner Losh - zstd source repository : https://github.com/Cyan4973/zstd 33110c16b537SWarner Losh - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c 33120c16b537SWarner Losh */ 33130c16b537SWarner Losh 33140c16b537SWarner Losh /* The objects defined into this file should be considered experimental. 33150c16b537SWarner Losh * They are not labelled stable, as their prototype may change in the future. 33160c16b537SWarner Losh * You can use them for tests, provide feedback, or if you can endure risk of future changes. 33170c16b537SWarner Losh */ 33180c16b537SWarner Losh 33190c16b537SWarner Losh /* ************************************* 33200c16b537SWarner Losh * Includes 33210c16b537SWarner Losh ***************************************/ 33220c16b537SWarner Losh #include <stdlib.h> 33230c16b537SWarner Losh 33240c16b537SWarner Losh 33250c16b537SWarner Losh /** ************************************************ 33260c16b537SWarner Losh * Streaming decompression 33270c16b537SWarner Losh * 33280c16b537SWarner Losh * A ZBUFF_DCtx object is required to track streaming operation. 33290c16b537SWarner Losh * Use ZBUFF_createDCtx() and ZBUFF_freeDCtx() to create/release resources. 33300c16b537SWarner Losh * Use ZBUFF_decompressInit() to start a new decompression operation. 33310c16b537SWarner Losh * ZBUFF_DCtx objects can be reused multiple times. 33320c16b537SWarner Losh * 33330c16b537SWarner Losh * Use ZBUFF_decompressContinue() repetitively to consume your input. 33340c16b537SWarner Losh * *srcSizePtr and *maxDstSizePtr can be any size. 33350c16b537SWarner Losh * The function will report how many bytes were read or written by modifying *srcSizePtr and *maxDstSizePtr. 33360c16b537SWarner Losh * Note that it may not consume the entire input, in which case it's up to the caller to call again the function with remaining input. 33370c16b537SWarner Losh * The content of dst will be overwritten (up to *maxDstSizePtr) at each function call, so save its content if it matters or change dst . 33380c16b537SWarner Losh * return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency) 33390c16b537SWarner Losh * or 0 when a frame is completely decoded 33400c16b537SWarner Losh * or an error code, which can be tested using ZBUFF_isError(). 33410c16b537SWarner Losh * 33420c16b537SWarner Losh * Hint : recommended buffer sizes (not compulsory) 33430c16b537SWarner Losh * output : 128 KB block size is the internal unit, it ensures it's always possible to write a full block when it's decoded. 33440c16b537SWarner Losh * input : just follow indications from ZBUFF_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 . 33450c16b537SWarner Losh * **************************************************/ 33460c16b537SWarner Losh 33470c16b537SWarner Losh typedef enum { ZBUFFds_init, ZBUFFds_readHeader, ZBUFFds_loadHeader, ZBUFFds_decodeHeader, 33480c16b537SWarner Losh ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFF_dStage; 33490c16b537SWarner Losh 33500c16b537SWarner Losh /* *** Resource management *** */ 33510c16b537SWarner Losh 33520c16b537SWarner Losh #define ZSTD_frameHeaderSize_max 5 /* too magical, should come from reference */ 33530c16b537SWarner Losh struct ZBUFFv04_DCtx_s { 33540c16b537SWarner Losh ZSTD_DCtx* zc; 33550c16b537SWarner Losh ZSTD_parameters params; 33560c16b537SWarner Losh char* inBuff; 33570c16b537SWarner Losh size_t inBuffSize; 33580c16b537SWarner Losh size_t inPos; 33590c16b537SWarner Losh char* outBuff; 33600c16b537SWarner Losh size_t outBuffSize; 33610c16b537SWarner Losh size_t outStart; 33620c16b537SWarner Losh size_t outEnd; 33630c16b537SWarner Losh size_t hPos; 33640c16b537SWarner Losh const char* dict; 33650c16b537SWarner Losh size_t dictSize; 33660c16b537SWarner Losh ZBUFF_dStage stage; 33670c16b537SWarner Losh unsigned char headerBuffer[ZSTD_frameHeaderSize_max]; 33680c16b537SWarner Losh }; /* typedef'd to ZBUFF_DCtx within "zstd_buffered.h" */ 33690c16b537SWarner Losh 33700c16b537SWarner Losh typedef ZBUFFv04_DCtx ZBUFF_DCtx; 33710c16b537SWarner Losh 33720c16b537SWarner Losh 33730c16b537SWarner Losh static ZBUFF_DCtx* ZBUFF_createDCtx(void) 33740c16b537SWarner Losh { 33750c16b537SWarner Losh ZBUFF_DCtx* zbc = (ZBUFF_DCtx*)malloc(sizeof(ZBUFF_DCtx)); 33760c16b537SWarner Losh if (zbc==NULL) return NULL; 33770c16b537SWarner Losh memset(zbc, 0, sizeof(*zbc)); 33780c16b537SWarner Losh zbc->zc = ZSTD_createDCtx(); 33790c16b537SWarner Losh zbc->stage = ZBUFFds_init; 33800c16b537SWarner Losh return zbc; 33810c16b537SWarner Losh } 33820c16b537SWarner Losh 33830c16b537SWarner Losh static size_t ZBUFF_freeDCtx(ZBUFF_DCtx* zbc) 33840c16b537SWarner Losh { 33850c16b537SWarner Losh if (zbc==NULL) return 0; /* support free on null */ 33860c16b537SWarner Losh ZSTD_freeDCtx(zbc->zc); 33870c16b537SWarner Losh free(zbc->inBuff); 33880c16b537SWarner Losh free(zbc->outBuff); 33890c16b537SWarner Losh free(zbc); 33900c16b537SWarner Losh return 0; 33910c16b537SWarner Losh } 33920c16b537SWarner Losh 33930c16b537SWarner Losh 33940c16b537SWarner Losh /* *** Initialization *** */ 33950c16b537SWarner Losh 33960c16b537SWarner Losh static size_t ZBUFF_decompressInit(ZBUFF_DCtx* zbc) 33970c16b537SWarner Losh { 33980c16b537SWarner Losh zbc->stage = ZBUFFds_readHeader; 33990c16b537SWarner Losh zbc->hPos = zbc->inPos = zbc->outStart = zbc->outEnd = zbc->dictSize = 0; 34000c16b537SWarner Losh return ZSTD_resetDCtx(zbc->zc); 34010c16b537SWarner Losh } 34020c16b537SWarner Losh 34030c16b537SWarner Losh 34040c16b537SWarner Losh static size_t ZBUFF_decompressWithDictionary(ZBUFF_DCtx* zbc, const void* src, size_t srcSize) 34050c16b537SWarner Losh { 34060c16b537SWarner Losh zbc->dict = (const char*)src; 34070c16b537SWarner Losh zbc->dictSize = srcSize; 34080c16b537SWarner Losh return 0; 34090c16b537SWarner Losh } 34100c16b537SWarner Losh 34110c16b537SWarner Losh static size_t ZBUFF_limitCopy(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 34120c16b537SWarner Losh { 34130c16b537SWarner Losh size_t length = MIN(maxDstSize, srcSize); 3414*37f1f268SConrad Meyer if (length > 0) { 34150c16b537SWarner Losh memcpy(dst, src, length); 3416*37f1f268SConrad Meyer } 34170c16b537SWarner Losh return length; 34180c16b537SWarner Losh } 34190c16b537SWarner Losh 34200c16b537SWarner Losh /* *** Decompression *** */ 34210c16b537SWarner Losh 34220c16b537SWarner Losh static size_t ZBUFF_decompressContinue(ZBUFF_DCtx* zbc, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr) 34230c16b537SWarner Losh { 34240c16b537SWarner Losh const char* const istart = (const char*)src; 34250c16b537SWarner Losh const char* ip = istart; 34260c16b537SWarner Losh const char* const iend = istart + *srcSizePtr; 34270c16b537SWarner Losh char* const ostart = (char*)dst; 34280c16b537SWarner Losh char* op = ostart; 34290c16b537SWarner Losh char* const oend = ostart + *maxDstSizePtr; 34300c16b537SWarner Losh U32 notDone = 1; 34310c16b537SWarner Losh 343219fcbaf1SConrad Meyer DEBUGLOG(5, "ZBUFF_decompressContinue"); 34330c16b537SWarner Losh while (notDone) 34340c16b537SWarner Losh { 34350c16b537SWarner Losh switch(zbc->stage) 34360c16b537SWarner Losh { 34370c16b537SWarner Losh 34380c16b537SWarner Losh case ZBUFFds_init : 343919fcbaf1SConrad Meyer DEBUGLOG(5, "ZBUFF_decompressContinue: stage==ZBUFFds_init => ERROR(init_missing)"); 34400c16b537SWarner Losh return ERROR(init_missing); 34410c16b537SWarner Losh 34420c16b537SWarner Losh case ZBUFFds_readHeader : 34430c16b537SWarner Losh /* read header from src */ 34440c16b537SWarner Losh { size_t const headerSize = ZSTD_getFrameParams(&(zbc->params), src, *srcSizePtr); 34450c16b537SWarner Losh if (ZSTD_isError(headerSize)) return headerSize; 34460c16b537SWarner Losh if (headerSize) { 34470c16b537SWarner Losh /* not enough input to decode header : tell how many bytes would be necessary */ 34480c16b537SWarner Losh memcpy(zbc->headerBuffer+zbc->hPos, src, *srcSizePtr); 34490c16b537SWarner Losh zbc->hPos += *srcSizePtr; 34500c16b537SWarner Losh *maxDstSizePtr = 0; 34510c16b537SWarner Losh zbc->stage = ZBUFFds_loadHeader; 34520c16b537SWarner Losh return headerSize - zbc->hPos; 34530c16b537SWarner Losh } 34540c16b537SWarner Losh zbc->stage = ZBUFFds_decodeHeader; 34550c16b537SWarner Losh break; 34560c16b537SWarner Losh } 34570c16b537SWarner Losh 34580c16b537SWarner Losh case ZBUFFds_loadHeader: 34590c16b537SWarner Losh /* complete header from src */ 34600c16b537SWarner Losh { size_t headerSize = ZBUFF_limitCopy( 34610c16b537SWarner Losh zbc->headerBuffer + zbc->hPos, ZSTD_frameHeaderSize_max - zbc->hPos, 34620c16b537SWarner Losh src, *srcSizePtr); 34630c16b537SWarner Losh zbc->hPos += headerSize; 34640c16b537SWarner Losh ip += headerSize; 34650c16b537SWarner Losh headerSize = ZSTD_getFrameParams(&(zbc->params), zbc->headerBuffer, zbc->hPos); 34660c16b537SWarner Losh if (ZSTD_isError(headerSize)) return headerSize; 34670c16b537SWarner Losh if (headerSize) { 34680c16b537SWarner Losh /* not enough input to decode header : tell how many bytes would be necessary */ 34690c16b537SWarner Losh *maxDstSizePtr = 0; 34700c16b537SWarner Losh return headerSize - zbc->hPos; 34710c16b537SWarner Losh } } 34720c16b537SWarner Losh /* intentional fallthrough */ 34730c16b537SWarner Losh 34740c16b537SWarner Losh case ZBUFFds_decodeHeader: 34750c16b537SWarner Losh /* apply header to create / resize buffers */ 34760c16b537SWarner Losh { size_t const neededOutSize = (size_t)1 << zbc->params.windowLog; 34770c16b537SWarner Losh size_t const neededInSize = BLOCKSIZE; /* a block is never > BLOCKSIZE */ 34780c16b537SWarner Losh if (zbc->inBuffSize < neededInSize) { 34790c16b537SWarner Losh free(zbc->inBuff); 34800c16b537SWarner Losh zbc->inBuffSize = neededInSize; 34810c16b537SWarner Losh zbc->inBuff = (char*)malloc(neededInSize); 34820c16b537SWarner Losh if (zbc->inBuff == NULL) return ERROR(memory_allocation); 34830c16b537SWarner Losh } 34840c16b537SWarner Losh if (zbc->outBuffSize < neededOutSize) { 34850c16b537SWarner Losh free(zbc->outBuff); 34860c16b537SWarner Losh zbc->outBuffSize = neededOutSize; 34870c16b537SWarner Losh zbc->outBuff = (char*)malloc(neededOutSize); 34880c16b537SWarner Losh if (zbc->outBuff == NULL) return ERROR(memory_allocation); 34890c16b537SWarner Losh } } 34900c16b537SWarner Losh if (zbc->dictSize) 34910c16b537SWarner Losh ZSTD_decompress_insertDictionary(zbc->zc, zbc->dict, zbc->dictSize); 34920c16b537SWarner Losh if (zbc->hPos) { 34930c16b537SWarner Losh /* some data already loaded into headerBuffer : transfer into inBuff */ 34940c16b537SWarner Losh memcpy(zbc->inBuff, zbc->headerBuffer, zbc->hPos); 34950c16b537SWarner Losh zbc->inPos = zbc->hPos; 34960c16b537SWarner Losh zbc->hPos = 0; 34970c16b537SWarner Losh zbc->stage = ZBUFFds_load; 34980c16b537SWarner Losh break; 34990c16b537SWarner Losh } 35000c16b537SWarner Losh zbc->stage = ZBUFFds_read; 35010c16b537SWarner Losh /* fall-through */ 35020c16b537SWarner Losh case ZBUFFds_read: 35030c16b537SWarner Losh { 35040c16b537SWarner Losh size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc); 35050c16b537SWarner Losh if (neededInSize==0) /* end of frame */ 35060c16b537SWarner Losh { 35070c16b537SWarner Losh zbc->stage = ZBUFFds_init; 35080c16b537SWarner Losh notDone = 0; 35090c16b537SWarner Losh break; 35100c16b537SWarner Losh } 35110c16b537SWarner Losh if ((size_t)(iend-ip) >= neededInSize) 35120c16b537SWarner Losh { 35130c16b537SWarner Losh /* directly decode from src */ 35140c16b537SWarner Losh size_t decodedSize = ZSTD_decompressContinue(zbc->zc, 35150c16b537SWarner Losh zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart, 35160c16b537SWarner Losh ip, neededInSize); 35170c16b537SWarner Losh if (ZSTD_isError(decodedSize)) return decodedSize; 35180c16b537SWarner Losh ip += neededInSize; 35190c16b537SWarner Losh if (!decodedSize) break; /* this was just a header */ 35200c16b537SWarner Losh zbc->outEnd = zbc->outStart + decodedSize; 35210c16b537SWarner Losh zbc->stage = ZBUFFds_flush; 35220c16b537SWarner Losh break; 35230c16b537SWarner Losh } 35240c16b537SWarner Losh if (ip==iend) { notDone = 0; break; } /* no more input */ 35250c16b537SWarner Losh zbc->stage = ZBUFFds_load; 35260c16b537SWarner Losh } 35270c16b537SWarner Losh /* fall-through */ 35280c16b537SWarner Losh case ZBUFFds_load: 35290c16b537SWarner Losh { 35300c16b537SWarner Losh size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc); 35310c16b537SWarner Losh size_t toLoad = neededInSize - zbc->inPos; /* should always be <= remaining space within inBuff */ 35320c16b537SWarner Losh size_t loadedSize; 35330c16b537SWarner Losh if (toLoad > zbc->inBuffSize - zbc->inPos) return ERROR(corruption_detected); /* should never happen */ 35340c16b537SWarner Losh loadedSize = ZBUFF_limitCopy(zbc->inBuff + zbc->inPos, toLoad, ip, iend-ip); 35350c16b537SWarner Losh ip += loadedSize; 35360c16b537SWarner Losh zbc->inPos += loadedSize; 35370c16b537SWarner Losh if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */ 35380c16b537SWarner Losh { 35390c16b537SWarner Losh size_t decodedSize = ZSTD_decompressContinue(zbc->zc, 35400c16b537SWarner Losh zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart, 35410c16b537SWarner Losh zbc->inBuff, neededInSize); 35420c16b537SWarner Losh if (ZSTD_isError(decodedSize)) return decodedSize; 35430c16b537SWarner Losh zbc->inPos = 0; /* input is consumed */ 35440c16b537SWarner Losh if (!decodedSize) { zbc->stage = ZBUFFds_read; break; } /* this was just a header */ 35450c16b537SWarner Losh zbc->outEnd = zbc->outStart + decodedSize; 35460c16b537SWarner Losh zbc->stage = ZBUFFds_flush; 35470c16b537SWarner Losh /* ZBUFFds_flush follows */ 35480c16b537SWarner Losh } 35490c16b537SWarner Losh } 35500c16b537SWarner Losh /* fall-through */ 35510c16b537SWarner Losh case ZBUFFds_flush: 35520c16b537SWarner Losh { 35530c16b537SWarner Losh size_t toFlushSize = zbc->outEnd - zbc->outStart; 35540c16b537SWarner Losh size_t flushedSize = ZBUFF_limitCopy(op, oend-op, zbc->outBuff + zbc->outStart, toFlushSize); 35550c16b537SWarner Losh op += flushedSize; 35560c16b537SWarner Losh zbc->outStart += flushedSize; 35570c16b537SWarner Losh if (flushedSize == toFlushSize) 35580c16b537SWarner Losh { 35590c16b537SWarner Losh zbc->stage = ZBUFFds_read; 35600c16b537SWarner Losh if (zbc->outStart + BLOCKSIZE > zbc->outBuffSize) 35610c16b537SWarner Losh zbc->outStart = zbc->outEnd = 0; 35620c16b537SWarner Losh break; 35630c16b537SWarner Losh } 35640c16b537SWarner Losh /* cannot flush everything */ 35650c16b537SWarner Losh notDone = 0; 35660c16b537SWarner Losh break; 35670c16b537SWarner Losh } 35680c16b537SWarner Losh default: return ERROR(GENERIC); /* impossible */ 35690c16b537SWarner Losh } 35700c16b537SWarner Losh } 35710c16b537SWarner Losh 35720c16b537SWarner Losh *srcSizePtr = ip-istart; 35730c16b537SWarner Losh *maxDstSizePtr = op-ostart; 35740c16b537SWarner Losh 35750c16b537SWarner Losh { 35760c16b537SWarner Losh size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zbc->zc); 35770c16b537SWarner Losh if (nextSrcSizeHint > 3) nextSrcSizeHint+= 3; /* get the next block header while at it */ 35780c16b537SWarner Losh nextSrcSizeHint -= zbc->inPos; /* already loaded*/ 35790c16b537SWarner Losh return nextSrcSizeHint; 35800c16b537SWarner Losh } 35810c16b537SWarner Losh } 35820c16b537SWarner Losh 35830c16b537SWarner Losh 35840c16b537SWarner Losh /* ************************************* 35850c16b537SWarner Losh * Tool functions 35860c16b537SWarner Losh ***************************************/ 35870c16b537SWarner Losh unsigned ZBUFFv04_isError(size_t errorCode) { return ERR_isError(errorCode); } 35880c16b537SWarner Losh const char* ZBUFFv04_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); } 35890c16b537SWarner Losh 35900c16b537SWarner Losh size_t ZBUFFv04_recommendedDInSize() { return BLOCKSIZE + 3; } 35910c16b537SWarner Losh size_t ZBUFFv04_recommendedDOutSize() { return BLOCKSIZE; } 35920c16b537SWarner Losh 35930c16b537SWarner Losh 35940c16b537SWarner Losh 35950c16b537SWarner Losh /*- ========================================================================= -*/ 35960c16b537SWarner Losh 35970c16b537SWarner Losh /* final wrapping stage */ 35980c16b537SWarner Losh 35990c16b537SWarner Losh size_t ZSTDv04_decompressDCtx(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 36000c16b537SWarner Losh { 36010c16b537SWarner Losh return ZSTD_decompress_usingDict(dctx, dst, maxDstSize, src, srcSize, NULL, 0); 36020c16b537SWarner Losh } 36030c16b537SWarner Losh 36040c16b537SWarner Losh size_t ZSTDv04_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 36050c16b537SWarner Losh { 36060c16b537SWarner Losh #if defined(ZSTD_HEAPMODE) && (ZSTD_HEAPMODE==1) 36070c16b537SWarner Losh size_t regenSize; 36080c16b537SWarner Losh ZSTD_DCtx* dctx = ZSTD_createDCtx(); 36090c16b537SWarner Losh if (dctx==NULL) return ERROR(memory_allocation); 36100c16b537SWarner Losh regenSize = ZSTDv04_decompressDCtx(dctx, dst, maxDstSize, src, srcSize); 36110c16b537SWarner Losh ZSTD_freeDCtx(dctx); 36120c16b537SWarner Losh return regenSize; 36130c16b537SWarner Losh #else 36140c16b537SWarner Losh ZSTD_DCtx dctx; 36150c16b537SWarner Losh return ZSTDv04_decompressDCtx(&dctx, dst, maxDstSize, src, srcSize); 36160c16b537SWarner Losh #endif 36170c16b537SWarner Losh } 36180c16b537SWarner Losh 36190c16b537SWarner Losh size_t ZSTDv04_resetDCtx(ZSTDv04_Dctx* dctx) { return ZSTD_resetDCtx(dctx); } 36200c16b537SWarner Losh 36210c16b537SWarner Losh size_t ZSTDv04_nextSrcSizeToDecompress(ZSTDv04_Dctx* dctx) 36220c16b537SWarner Losh { 36230c16b537SWarner Losh return ZSTD_nextSrcSizeToDecompress(dctx); 36240c16b537SWarner Losh } 36250c16b537SWarner Losh 36260c16b537SWarner Losh size_t ZSTDv04_decompressContinue(ZSTDv04_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 36270c16b537SWarner Losh { 36280c16b537SWarner Losh return ZSTD_decompressContinue(dctx, dst, maxDstSize, src, srcSize); 36290c16b537SWarner Losh } 36300c16b537SWarner Losh 36310c16b537SWarner Losh 36320c16b537SWarner Losh 36330c16b537SWarner Losh ZBUFFv04_DCtx* ZBUFFv04_createDCtx(void) { return ZBUFF_createDCtx(); } 36340c16b537SWarner Losh size_t ZBUFFv04_freeDCtx(ZBUFFv04_DCtx* dctx) { return ZBUFF_freeDCtx(dctx); } 36350c16b537SWarner Losh 36360c16b537SWarner Losh size_t ZBUFFv04_decompressInit(ZBUFFv04_DCtx* dctx) { return ZBUFF_decompressInit(dctx); } 36370c16b537SWarner Losh size_t ZBUFFv04_decompressWithDictionary(ZBUFFv04_DCtx* dctx, const void* src, size_t srcSize) 36380c16b537SWarner Losh { return ZBUFF_decompressWithDictionary(dctx, src, srcSize); } 36390c16b537SWarner Losh 36400c16b537SWarner Losh size_t ZBUFFv04_decompressContinue(ZBUFFv04_DCtx* dctx, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr) 36410c16b537SWarner Losh { 364219fcbaf1SConrad Meyer DEBUGLOG(5, "ZBUFFv04_decompressContinue"); 36430c16b537SWarner Losh return ZBUFF_decompressContinue(dctx, dst, maxDstSizePtr, src, srcSizePtr); 36440c16b537SWarner Losh } 36450c16b537SWarner Losh 36460c16b537SWarner Losh ZSTD_DCtx* ZSTDv04_createDCtx(void) { return ZSTD_createDCtx(); } 36470c16b537SWarner Losh size_t ZSTDv04_freeDCtx(ZSTD_DCtx* dctx) { return ZSTD_freeDCtx(dctx); } 3648