10c16b537SWarner Losh /* 237f1f268SConrad 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 120c16b537SWarner Losh #include <stddef.h> /* size_t, ptrdiff_t */ 130c16b537SWarner Losh #include "zstd_v03.h" 1437f1f268SConrad Meyer #include "../common/error_private.h" 150c16b537SWarner Losh 160c16b537SWarner Losh 170c16b537SWarner Losh /****************************************** 180c16b537SWarner Losh * Compiler-specific 190c16b537SWarner Losh ******************************************/ 200c16b537SWarner Losh #if defined(_MSC_VER) /* Visual Studio */ 210c16b537SWarner Losh # include <stdlib.h> /* _byteswap_ulong */ 220c16b537SWarner Losh # include <intrin.h> /* _byteswap_* */ 230c16b537SWarner Losh #endif 240c16b537SWarner Losh 250c16b537SWarner Losh 260c16b537SWarner Losh 270c16b537SWarner Losh /* ****************************************************************** 280c16b537SWarner Losh mem.h 290c16b537SWarner Losh low-level memory access routines 300c16b537SWarner Losh Copyright (C) 2013-2015, Yann Collet. 310c16b537SWarner Losh 320c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 330c16b537SWarner Losh 340c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 350c16b537SWarner Losh modification, are permitted provided that the following conditions are 360c16b537SWarner Losh met: 370c16b537SWarner Losh 380c16b537SWarner Losh * Redistributions of source code must retain the above copyright 390c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 400c16b537SWarner Losh * Redistributions in binary form must reproduce the above 410c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 420c16b537SWarner Losh in the documentation and/or other materials provided with the 430c16b537SWarner Losh distribution. 440c16b537SWarner Losh 450c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 460c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 470c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 480c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 490c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 500c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 510c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 520c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 530c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 540c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 550c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 560c16b537SWarner Losh 570c16b537SWarner Losh You can contact the author at : 580c16b537SWarner Losh - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy 590c16b537SWarner Losh - Public forum : https://groups.google.com/forum/#!forum/lz4c 600c16b537SWarner Losh ****************************************************************** */ 610c16b537SWarner Losh #ifndef MEM_H_MODULE 620c16b537SWarner Losh #define MEM_H_MODULE 630c16b537SWarner Losh 640c16b537SWarner Losh #if defined (__cplusplus) 650c16b537SWarner Losh extern "C" { 660c16b537SWarner Losh #endif 670c16b537SWarner Losh 680c16b537SWarner Losh /****************************************** 690c16b537SWarner Losh * Includes 700c16b537SWarner Losh ******************************************/ 710c16b537SWarner Losh #include <stddef.h> /* size_t, ptrdiff_t */ 720c16b537SWarner Losh #include <string.h> /* memcpy */ 730c16b537SWarner Losh 740c16b537SWarner Losh 750c16b537SWarner Losh /****************************************** 760c16b537SWarner Losh * Compiler-specific 770c16b537SWarner Losh ******************************************/ 780c16b537SWarner Losh #if defined(__GNUC__) 790c16b537SWarner Losh # define MEM_STATIC static __attribute__((unused)) 800c16b537SWarner Losh #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 810c16b537SWarner Losh # define MEM_STATIC static inline 820c16b537SWarner Losh #elif defined(_MSC_VER) 830c16b537SWarner Losh # define MEM_STATIC static __inline 840c16b537SWarner Losh #else 850c16b537SWarner Losh # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */ 860c16b537SWarner Losh #endif 870c16b537SWarner Losh 880c16b537SWarner Losh 890c16b537SWarner Losh /**************************************************************** 900c16b537SWarner Losh * Basic Types 910c16b537SWarner Losh *****************************************************************/ 920c16b537SWarner Losh #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 930c16b537SWarner Losh # include <stdint.h> 940c16b537SWarner Losh typedef uint8_t BYTE; 950c16b537SWarner Losh typedef uint16_t U16; 960c16b537SWarner Losh typedef int16_t S16; 970c16b537SWarner Losh typedef uint32_t U32; 980c16b537SWarner Losh typedef int32_t S32; 990c16b537SWarner Losh typedef uint64_t U64; 1000c16b537SWarner Losh typedef int64_t S64; 1010c16b537SWarner Losh #else 1020c16b537SWarner Losh typedef unsigned char BYTE; 1030c16b537SWarner Losh typedef unsigned short U16; 1040c16b537SWarner Losh typedef signed short S16; 1050c16b537SWarner Losh typedef unsigned int U32; 1060c16b537SWarner Losh typedef signed int S32; 1070c16b537SWarner Losh typedef unsigned long long U64; 1080c16b537SWarner Losh typedef signed long long S64; 1090c16b537SWarner Losh #endif 1100c16b537SWarner Losh 1110c16b537SWarner Losh 1120c16b537SWarner Losh /**************************************************************** 1130c16b537SWarner Losh * Memory I/O 1140c16b537SWarner Losh *****************************************************************/ 1150c16b537SWarner Losh /* MEM_FORCE_MEMORY_ACCESS 1160c16b537SWarner Losh * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable. 1170c16b537SWarner Losh * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal. 1180c16b537SWarner Losh * The below switch allow to select different access method for improved performance. 1190c16b537SWarner Losh * Method 0 (default) : use `memcpy()`. Safe and portable. 1200c16b537SWarner Losh * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable). 1210c16b537SWarner Losh * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`. 1220c16b537SWarner Losh * Method 2 : direct access. This method is portable but violate C standard. 1230c16b537SWarner Losh * It can generate buggy code on targets generating assembly depending on alignment. 1240c16b537SWarner Losh * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6) 1250c16b537SWarner Losh * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details. 1260c16b537SWarner Losh * Prefer these methods in priority order (0 > 1 > 2) 1270c16b537SWarner Losh */ 1280c16b537SWarner Losh #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */ 1290c16b537SWarner 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__) ) 1300c16b537SWarner Losh # define MEM_FORCE_MEMORY_ACCESS 2 1310c16b537SWarner Losh # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \ 1320c16b537SWarner Losh (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) )) 1330c16b537SWarner Losh # define MEM_FORCE_MEMORY_ACCESS 1 1340c16b537SWarner Losh # endif 1350c16b537SWarner Losh #endif 1360c16b537SWarner Losh 1370c16b537SWarner Losh MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; } 1380c16b537SWarner Losh MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; } 1390c16b537SWarner Losh 1400c16b537SWarner Losh MEM_STATIC unsigned MEM_isLittleEndian(void) 1410c16b537SWarner Losh { 1420c16b537SWarner Losh const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ 1430c16b537SWarner Losh return one.c[0]; 1440c16b537SWarner Losh } 1450c16b537SWarner Losh 1460c16b537SWarner Losh #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2) 1470c16b537SWarner Losh 1480c16b537SWarner Losh /* violates C standard on structure alignment. 1490c16b537SWarner Losh Only use if no other choice to achieve best performance on target platform */ 1500c16b537SWarner Losh MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; } 1510c16b537SWarner Losh MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; } 1520c16b537SWarner Losh MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; } 1530c16b537SWarner Losh 1540c16b537SWarner Losh MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; } 1550c16b537SWarner Losh 1560c16b537SWarner Losh #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1) 1570c16b537SWarner Losh 1580c16b537SWarner Losh /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ 1590c16b537SWarner Losh /* currently only defined for gcc and icc */ 1600c16b537SWarner Losh typedef union { U16 u16; U32 u32; U64 u64; } __attribute__((packed)) unalign; 1610c16b537SWarner Losh 1620c16b537SWarner Losh MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; } 1630c16b537SWarner Losh MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } 1640c16b537SWarner Losh MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; } 1650c16b537SWarner Losh 1660c16b537SWarner Losh MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; } 1670c16b537SWarner Losh 1680c16b537SWarner Losh #else 1690c16b537SWarner Losh 1700c16b537SWarner Losh /* default method, safe and standard. 1710c16b537SWarner Losh can sometimes prove slower */ 1720c16b537SWarner Losh 1730c16b537SWarner Losh MEM_STATIC U16 MEM_read16(const void* memPtr) 1740c16b537SWarner Losh { 1750c16b537SWarner Losh U16 val; memcpy(&val, memPtr, sizeof(val)); return val; 1760c16b537SWarner Losh } 1770c16b537SWarner Losh 1780c16b537SWarner Losh MEM_STATIC U32 MEM_read32(const void* memPtr) 1790c16b537SWarner Losh { 1800c16b537SWarner Losh U32 val; memcpy(&val, memPtr, sizeof(val)); return val; 1810c16b537SWarner Losh } 1820c16b537SWarner Losh 1830c16b537SWarner Losh MEM_STATIC U64 MEM_read64(const void* memPtr) 1840c16b537SWarner Losh { 1850c16b537SWarner Losh U64 val; memcpy(&val, memPtr, sizeof(val)); return val; 1860c16b537SWarner Losh } 1870c16b537SWarner Losh 1880c16b537SWarner Losh MEM_STATIC void MEM_write16(void* memPtr, U16 value) 1890c16b537SWarner Losh { 1900c16b537SWarner Losh memcpy(memPtr, &value, sizeof(value)); 1910c16b537SWarner Losh } 1920c16b537SWarner Losh 1930c16b537SWarner Losh 19437f1f268SConrad Meyer #endif /* MEM_FORCE_MEMORY_ACCESS */ 1950c16b537SWarner Losh 1960c16b537SWarner Losh 1970c16b537SWarner Losh MEM_STATIC U16 MEM_readLE16(const void* memPtr) 1980c16b537SWarner Losh { 1990c16b537SWarner Losh if (MEM_isLittleEndian()) 2000c16b537SWarner Losh return MEM_read16(memPtr); 2010c16b537SWarner Losh else 2020c16b537SWarner Losh { 2030c16b537SWarner Losh const BYTE* p = (const BYTE*)memPtr; 2040c16b537SWarner Losh return (U16)(p[0] + (p[1]<<8)); 2050c16b537SWarner Losh } 2060c16b537SWarner Losh } 2070c16b537SWarner Losh 2080c16b537SWarner Losh MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val) 2090c16b537SWarner Losh { 2100c16b537SWarner Losh if (MEM_isLittleEndian()) 2110c16b537SWarner Losh { 2120c16b537SWarner Losh MEM_write16(memPtr, val); 2130c16b537SWarner Losh } 2140c16b537SWarner Losh else 2150c16b537SWarner Losh { 2160c16b537SWarner Losh BYTE* p = (BYTE*)memPtr; 2170c16b537SWarner Losh p[0] = (BYTE)val; 2180c16b537SWarner Losh p[1] = (BYTE)(val>>8); 2190c16b537SWarner Losh } 2200c16b537SWarner Losh } 2210c16b537SWarner Losh 2224d3f1eafSConrad Meyer MEM_STATIC U32 MEM_readLE24(const void* memPtr) 2234d3f1eafSConrad Meyer { 2244d3f1eafSConrad Meyer return MEM_readLE16(memPtr) + (((const BYTE*)memPtr)[2] << 16); 2254d3f1eafSConrad Meyer } 2264d3f1eafSConrad Meyer 2270c16b537SWarner Losh MEM_STATIC U32 MEM_readLE32(const void* memPtr) 2280c16b537SWarner Losh { 2290c16b537SWarner Losh if (MEM_isLittleEndian()) 2300c16b537SWarner Losh return MEM_read32(memPtr); 2310c16b537SWarner Losh else 2320c16b537SWarner Losh { 2330c16b537SWarner Losh const BYTE* p = (const BYTE*)memPtr; 2340c16b537SWarner Losh return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24)); 2350c16b537SWarner Losh } 2360c16b537SWarner Losh } 2370c16b537SWarner Losh 2380c16b537SWarner Losh MEM_STATIC U64 MEM_readLE64(const void* memPtr) 2390c16b537SWarner Losh { 2400c16b537SWarner Losh if (MEM_isLittleEndian()) 2410c16b537SWarner Losh return MEM_read64(memPtr); 2420c16b537SWarner Losh else 2430c16b537SWarner Losh { 2440c16b537SWarner Losh const BYTE* p = (const BYTE*)memPtr; 2450c16b537SWarner Losh return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24) 2460c16b537SWarner Losh + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56)); 2470c16b537SWarner Losh } 2480c16b537SWarner Losh } 2490c16b537SWarner Losh 2500c16b537SWarner Losh 2510c16b537SWarner Losh MEM_STATIC size_t MEM_readLEST(const void* memPtr) 2520c16b537SWarner Losh { 2530c16b537SWarner Losh if (MEM_32bits()) 2540c16b537SWarner Losh return (size_t)MEM_readLE32(memPtr); 2550c16b537SWarner Losh else 2560c16b537SWarner Losh return (size_t)MEM_readLE64(memPtr); 2570c16b537SWarner Losh } 2580c16b537SWarner Losh 2590c16b537SWarner Losh 2600c16b537SWarner Losh #if defined (__cplusplus) 2610c16b537SWarner Losh } 2620c16b537SWarner Losh #endif 2630c16b537SWarner Losh 2640c16b537SWarner Losh #endif /* MEM_H_MODULE */ 2650c16b537SWarner Losh 2660c16b537SWarner Losh 2670c16b537SWarner Losh /* ****************************************************************** 2680c16b537SWarner Losh bitstream 2690c16b537SWarner Losh Part of NewGen Entropy library 2700c16b537SWarner Losh header file (to include) 2710c16b537SWarner Losh Copyright (C) 2013-2015, Yann Collet. 2720c16b537SWarner Losh 2730c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 2740c16b537SWarner Losh 2750c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 2760c16b537SWarner Losh modification, are permitted provided that the following conditions are 2770c16b537SWarner Losh met: 2780c16b537SWarner Losh 2790c16b537SWarner Losh * Redistributions of source code must retain the above copyright 2800c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 2810c16b537SWarner Losh * Redistributions in binary form must reproduce the above 2820c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 2830c16b537SWarner Losh in the documentation and/or other materials provided with the 2840c16b537SWarner Losh distribution. 2850c16b537SWarner Losh 2860c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2870c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2880c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2890c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2900c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2910c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2920c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2930c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2940c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2950c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2960c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2970c16b537SWarner Losh 2980c16b537SWarner Losh You can contact the author at : 2990c16b537SWarner Losh - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 3000c16b537SWarner Losh - Public forum : https://groups.google.com/forum/#!forum/lz4c 3010c16b537SWarner Losh ****************************************************************** */ 3020c16b537SWarner Losh #ifndef BITSTREAM_H_MODULE 3030c16b537SWarner Losh #define BITSTREAM_H_MODULE 3040c16b537SWarner Losh 3050c16b537SWarner Losh #if defined (__cplusplus) 3060c16b537SWarner Losh extern "C" { 3070c16b537SWarner Losh #endif 3080c16b537SWarner Losh 3090c16b537SWarner Losh 3100c16b537SWarner Losh /* 3110c16b537SWarner Losh * This API consists of small unitary functions, which highly benefit from being inlined. 3120c16b537SWarner Losh * Since link-time-optimization is not available for all compilers, 3130c16b537SWarner Losh * these functions are defined into a .h to be included. 3140c16b537SWarner Losh */ 3150c16b537SWarner Losh 3160c16b537SWarner Losh 3170c16b537SWarner Losh /********************************************** 3180c16b537SWarner Losh * bitStream decompression API (read backward) 3190c16b537SWarner Losh **********************************************/ 3200c16b537SWarner Losh typedef struct 3210c16b537SWarner Losh { 3220c16b537SWarner Losh size_t bitContainer; 3230c16b537SWarner Losh unsigned bitsConsumed; 3240c16b537SWarner Losh const char* ptr; 3250c16b537SWarner Losh const char* start; 3260c16b537SWarner Losh } BIT_DStream_t; 3270c16b537SWarner Losh 3280c16b537SWarner Losh typedef enum { BIT_DStream_unfinished = 0, 3290c16b537SWarner Losh BIT_DStream_endOfBuffer = 1, 3300c16b537SWarner Losh BIT_DStream_completed = 2, 3310c16b537SWarner Losh BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */ 3320c16b537SWarner Losh /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */ 3330c16b537SWarner Losh 3340c16b537SWarner Losh MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize); 3350c16b537SWarner Losh MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits); 3360c16b537SWarner Losh MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD); 3370c16b537SWarner Losh MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD); 3380c16b537SWarner Losh 3390c16b537SWarner Losh 3400c16b537SWarner Losh 3410c16b537SWarner Losh /****************************************** 3420c16b537SWarner Losh * unsafe API 3430c16b537SWarner Losh ******************************************/ 3440c16b537SWarner Losh MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits); 3450c16b537SWarner Losh /* faster, but works only if nbBits >= 1 */ 3460c16b537SWarner Losh 3470c16b537SWarner Losh 3480c16b537SWarner Losh 3490c16b537SWarner Losh /**************************************************************** 3500c16b537SWarner Losh * Helper functions 3510c16b537SWarner Losh ****************************************************************/ 352052d3c12SConrad Meyer MEM_STATIC unsigned BIT_highbit32 (U32 val) 3530c16b537SWarner Losh { 3540c16b537SWarner Losh # if defined(_MSC_VER) /* Visual */ 3550c16b537SWarner Losh unsigned long r=0; 3560c16b537SWarner Losh _BitScanReverse ( &r, val ); 3570c16b537SWarner Losh return (unsigned) r; 3580c16b537SWarner Losh # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */ 3599cbefe25SConrad Meyer return __builtin_clz (val) ^ 31; 3600c16b537SWarner Losh # else /* Software version */ 3610c16b537SWarner 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 }; 3620c16b537SWarner Losh U32 v = val; 3630c16b537SWarner Losh unsigned r; 3640c16b537SWarner Losh v |= v >> 1; 3650c16b537SWarner Losh v |= v >> 2; 3660c16b537SWarner Losh v |= v >> 4; 3670c16b537SWarner Losh v |= v >> 8; 3680c16b537SWarner Losh v |= v >> 16; 3690c16b537SWarner Losh r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27]; 3700c16b537SWarner Losh return r; 3710c16b537SWarner Losh # endif 3720c16b537SWarner Losh } 3730c16b537SWarner Losh 3740c16b537SWarner Losh 3750c16b537SWarner Losh 3760c16b537SWarner Losh /********************************************************** 3770c16b537SWarner Losh * bitStream decoding 3780c16b537SWarner Losh **********************************************************/ 3790c16b537SWarner Losh 3800c16b537SWarner Losh /*!BIT_initDStream 3810c16b537SWarner Losh * Initialize a BIT_DStream_t. 3820c16b537SWarner Losh * @bitD : a pointer to an already allocated BIT_DStream_t structure 3830c16b537SWarner Losh * @srcBuffer must point at the beginning of a bitStream 3840c16b537SWarner Losh * @srcSize must be the exact size of the bitStream 3850c16b537SWarner Losh * @result : size of stream (== srcSize) or an errorCode if a problem is detected 3860c16b537SWarner Losh */ 3870c16b537SWarner Losh MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize) 3880c16b537SWarner Losh { 3890c16b537SWarner Losh if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); } 3900c16b537SWarner Losh 3910c16b537SWarner Losh if (srcSize >= sizeof(size_t)) /* normal case */ 3920c16b537SWarner Losh { 3930c16b537SWarner Losh U32 contain32; 3940c16b537SWarner Losh bitD->start = (const char*)srcBuffer; 3950c16b537SWarner Losh bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t); 3960c16b537SWarner Losh bitD->bitContainer = MEM_readLEST(bitD->ptr); 3970c16b537SWarner Losh contain32 = ((const BYTE*)srcBuffer)[srcSize-1]; 3980c16b537SWarner Losh if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */ 3990c16b537SWarner Losh bitD->bitsConsumed = 8 - BIT_highbit32(contain32); 4000c16b537SWarner Losh } 4010c16b537SWarner Losh else 4020c16b537SWarner Losh { 4030c16b537SWarner Losh U32 contain32; 4040c16b537SWarner Losh bitD->start = (const char*)srcBuffer; 4050c16b537SWarner Losh bitD->ptr = bitD->start; 4060c16b537SWarner Losh bitD->bitContainer = *(const BYTE*)(bitD->start); 4070c16b537SWarner Losh switch(srcSize) 4080c16b537SWarner Losh { 4090c16b537SWarner Losh case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16); 4100f743729SConrad Meyer /* fallthrough */ 4110c16b537SWarner Losh case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24); 4120f743729SConrad Meyer /* fallthrough */ 4130c16b537SWarner Losh case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32); 4140f743729SConrad Meyer /* fallthrough */ 4150c16b537SWarner Losh case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24; 4160f743729SConrad Meyer /* fallthrough */ 4170c16b537SWarner Losh case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16; 4180f743729SConrad Meyer /* fallthrough */ 4190c16b537SWarner Losh case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8; 4200f743729SConrad Meyer /* fallthrough */ 4210c16b537SWarner Losh default:; 4220c16b537SWarner Losh } 4230c16b537SWarner Losh contain32 = ((const BYTE*)srcBuffer)[srcSize-1]; 4240c16b537SWarner Losh if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */ 4250c16b537SWarner Losh bitD->bitsConsumed = 8 - BIT_highbit32(contain32); 4260c16b537SWarner Losh bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8; 4270c16b537SWarner Losh } 4280c16b537SWarner Losh 4290c16b537SWarner Losh return srcSize; 4300c16b537SWarner Losh } 4310c16b537SWarner Losh MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits) 4320c16b537SWarner Losh { 4330c16b537SWarner Losh const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1; 4340c16b537SWarner Losh return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask); 4350c16b537SWarner Losh } 4360c16b537SWarner Losh 4370c16b537SWarner Losh /*! BIT_lookBitsFast : 4380c16b537SWarner Losh * unsafe version; only works only if nbBits >= 1 */ 4390c16b537SWarner Losh MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits) 4400c16b537SWarner Losh { 4410c16b537SWarner Losh const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1; 4420c16b537SWarner Losh return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask); 4430c16b537SWarner Losh } 4440c16b537SWarner Losh 4450c16b537SWarner Losh MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits) 4460c16b537SWarner Losh { 4470c16b537SWarner Losh bitD->bitsConsumed += nbBits; 4480c16b537SWarner Losh } 4490c16b537SWarner Losh 4500c16b537SWarner Losh MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits) 4510c16b537SWarner Losh { 4520c16b537SWarner Losh size_t value = BIT_lookBits(bitD, nbBits); 4530c16b537SWarner Losh BIT_skipBits(bitD, nbBits); 4540c16b537SWarner Losh return value; 4550c16b537SWarner Losh } 4560c16b537SWarner Losh 4570c16b537SWarner Losh /*!BIT_readBitsFast : 4580c16b537SWarner Losh * unsafe version; only works only if nbBits >= 1 */ 4590c16b537SWarner Losh MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits) 4600c16b537SWarner Losh { 4610c16b537SWarner Losh size_t value = BIT_lookBitsFast(bitD, nbBits); 4620c16b537SWarner Losh BIT_skipBits(bitD, nbBits); 4630c16b537SWarner Losh return value; 4640c16b537SWarner Losh } 4650c16b537SWarner Losh 4660c16b537SWarner Losh MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD) 4670c16b537SWarner Losh { 4680c16b537SWarner Losh if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */ 4690c16b537SWarner Losh return BIT_DStream_overflow; 4700c16b537SWarner Losh 4710c16b537SWarner Losh if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) 4720c16b537SWarner Losh { 4730c16b537SWarner Losh bitD->ptr -= bitD->bitsConsumed >> 3; 4740c16b537SWarner Losh bitD->bitsConsumed &= 7; 4750c16b537SWarner Losh bitD->bitContainer = MEM_readLEST(bitD->ptr); 4760c16b537SWarner Losh return BIT_DStream_unfinished; 4770c16b537SWarner Losh } 4780c16b537SWarner Losh if (bitD->ptr == bitD->start) 4790c16b537SWarner Losh { 4800c16b537SWarner Losh if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer; 4810c16b537SWarner Losh return BIT_DStream_completed; 4820c16b537SWarner Losh } 4830c16b537SWarner Losh { 4840c16b537SWarner Losh U32 nbBytes = bitD->bitsConsumed >> 3; 4850c16b537SWarner Losh BIT_DStream_status result = BIT_DStream_unfinished; 4860c16b537SWarner Losh if (bitD->ptr - nbBytes < bitD->start) 4870c16b537SWarner Losh { 4880c16b537SWarner Losh nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */ 4890c16b537SWarner Losh result = BIT_DStream_endOfBuffer; 4900c16b537SWarner Losh } 4910c16b537SWarner Losh bitD->ptr -= nbBytes; 4920c16b537SWarner Losh bitD->bitsConsumed -= nbBytes*8; 4930c16b537SWarner Losh bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */ 4940c16b537SWarner Losh return result; 4950c16b537SWarner Losh } 4960c16b537SWarner Losh } 4970c16b537SWarner Losh 4980c16b537SWarner Losh /*! BIT_endOfDStream 4990c16b537SWarner Losh * @return Tells if DStream has reached its exact end 5000c16b537SWarner Losh */ 5010c16b537SWarner Losh MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream) 5020c16b537SWarner Losh { 5030c16b537SWarner Losh return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8)); 5040c16b537SWarner Losh } 5050c16b537SWarner Losh 5060c16b537SWarner Losh #if defined (__cplusplus) 5070c16b537SWarner Losh } 5080c16b537SWarner Losh #endif 5090c16b537SWarner Losh 5100c16b537SWarner Losh #endif /* BITSTREAM_H_MODULE */ 5110c16b537SWarner Losh /* ****************************************************************** 5120c16b537SWarner Losh Error codes and messages 5130c16b537SWarner Losh Copyright (C) 2013-2015, Yann Collet 5140c16b537SWarner Losh 5150c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 5160c16b537SWarner Losh 5170c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 5180c16b537SWarner Losh modification, are permitted provided that the following conditions are 5190c16b537SWarner Losh met: 5200c16b537SWarner Losh 5210c16b537SWarner Losh * Redistributions of source code must retain the above copyright 5220c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 5230c16b537SWarner Losh * Redistributions in binary form must reproduce the above 5240c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 5250c16b537SWarner Losh in the documentation and/or other materials provided with the 5260c16b537SWarner Losh distribution. 5270c16b537SWarner Losh 5280c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 5290c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 5300c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 5310c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 5320c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 5330c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 5340c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 5350c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 5360c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 5370c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 5380c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 5390c16b537SWarner Losh 5400c16b537SWarner Losh You can contact the author at : 5410c16b537SWarner Losh - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 5420c16b537SWarner Losh - Public forum : https://groups.google.com/forum/#!forum/lz4c 5430c16b537SWarner Losh ****************************************************************** */ 5440c16b537SWarner Losh #ifndef ERROR_H_MODULE 5450c16b537SWarner Losh #define ERROR_H_MODULE 5460c16b537SWarner Losh 5470c16b537SWarner Losh #if defined (__cplusplus) 5480c16b537SWarner Losh extern "C" { 5490c16b537SWarner Losh #endif 5500c16b537SWarner Losh 5510c16b537SWarner Losh 5520c16b537SWarner Losh /****************************************** 5530c16b537SWarner Losh * Compiler-specific 5540c16b537SWarner Losh ******************************************/ 5550c16b537SWarner Losh #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 5560c16b537SWarner Losh # define ERR_STATIC static inline 5570c16b537SWarner Losh #elif defined(_MSC_VER) 5580c16b537SWarner Losh # define ERR_STATIC static __inline 5590c16b537SWarner Losh #elif defined(__GNUC__) 5600c16b537SWarner Losh # define ERR_STATIC static __attribute__((unused)) 5610c16b537SWarner Losh #else 5620c16b537SWarner Losh # define ERR_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */ 5630c16b537SWarner Losh #endif 5640c16b537SWarner Losh 5650c16b537SWarner Losh 5660c16b537SWarner Losh /****************************************** 5670c16b537SWarner Losh * Error Management 5680c16b537SWarner Losh ******************************************/ 5690c16b537SWarner Losh #define PREFIX(name) ZSTD_error_##name 5700c16b537SWarner Losh 5710c16b537SWarner Losh #define ERROR(name) (size_t)-PREFIX(name) 5720c16b537SWarner Losh 5730c16b537SWarner Losh #define ERROR_LIST(ITEM) \ 5740c16b537SWarner Losh ITEM(PREFIX(No_Error)) ITEM(PREFIX(GENERIC)) \ 5750c16b537SWarner Losh ITEM(PREFIX(dstSize_tooSmall)) ITEM(PREFIX(srcSize_wrong)) \ 5760c16b537SWarner Losh ITEM(PREFIX(prefix_unknown)) ITEM(PREFIX(corruption_detected)) \ 5770c16b537SWarner Losh ITEM(PREFIX(tableLog_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooSmall)) \ 5780c16b537SWarner Losh ITEM(PREFIX(maxCode)) 5790c16b537SWarner Losh 5800c16b537SWarner Losh #define ERROR_GENERATE_ENUM(ENUM) ENUM, 5810c16b537SWarner Losh typedef enum { ERROR_LIST(ERROR_GENERATE_ENUM) } ERR_codes; /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */ 5820c16b537SWarner Losh 5830c16b537SWarner Losh #define ERROR_CONVERTTOSTRING(STRING) #STRING, 5840c16b537SWarner Losh #define ERROR_GENERATE_STRING(EXPR) ERROR_CONVERTTOSTRING(EXPR) 5850c16b537SWarner Losh static const char* ERR_strings[] = { ERROR_LIST(ERROR_GENERATE_STRING) }; 5860c16b537SWarner Losh 5870c16b537SWarner Losh ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); } 5880c16b537SWarner Losh 5890c16b537SWarner Losh ERR_STATIC const char* ERR_getErrorName(size_t code) 5900c16b537SWarner Losh { 5910c16b537SWarner Losh static const char* codeError = "Unspecified error code"; 5920c16b537SWarner Losh if (ERR_isError(code)) return ERR_strings[-(int)(code)]; 5930c16b537SWarner Losh return codeError; 5940c16b537SWarner Losh } 5950c16b537SWarner Losh 5960c16b537SWarner Losh 5970c16b537SWarner Losh #if defined (__cplusplus) 5980c16b537SWarner Losh } 5990c16b537SWarner Losh #endif 6000c16b537SWarner Losh 6010c16b537SWarner Losh #endif /* ERROR_H_MODULE */ 6020c16b537SWarner Losh /* 6030c16b537SWarner Losh Constructor and Destructor of type FSE_CTable 6040c16b537SWarner Losh Note that its size depends on 'tableLog' and 'maxSymbolValue' */ 6050c16b537SWarner Losh typedef unsigned FSE_CTable; /* don't allocate that. It's just a way to be more restrictive than void* */ 6060c16b537SWarner Losh typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */ 6070c16b537SWarner Losh 6080c16b537SWarner Losh 6090c16b537SWarner Losh /* ****************************************************************** 6100c16b537SWarner Losh FSE : Finite State Entropy coder 6110c16b537SWarner Losh header file for static linking (only) 6120c16b537SWarner Losh Copyright (C) 2013-2015, Yann Collet 6130c16b537SWarner Losh 6140c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 6150c16b537SWarner Losh 6160c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 6170c16b537SWarner Losh modification, are permitted provided that the following conditions are 6180c16b537SWarner Losh met: 6190c16b537SWarner Losh 6200c16b537SWarner Losh * Redistributions of source code must retain the above copyright 6210c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 6220c16b537SWarner Losh * Redistributions in binary form must reproduce the above 6230c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 6240c16b537SWarner Losh in the documentation and/or other materials provided with the 6250c16b537SWarner Losh distribution. 6260c16b537SWarner Losh 6270c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 6280c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 6290c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 6300c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 6310c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 6320c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 6330c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 6340c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 6350c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 6360c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 6370c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 6380c16b537SWarner Losh 6390c16b537SWarner Losh You can contact the author at : 6400c16b537SWarner Losh - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 6410c16b537SWarner Losh - Public forum : https://groups.google.com/forum/#!forum/lz4c 6420c16b537SWarner Losh ****************************************************************** */ 6430c16b537SWarner Losh #if defined (__cplusplus) 6440c16b537SWarner Losh extern "C" { 6450c16b537SWarner Losh #endif 6460c16b537SWarner Losh 6470c16b537SWarner Losh 6480c16b537SWarner Losh /****************************************** 6490c16b537SWarner Losh * Static allocation 6500c16b537SWarner Losh ******************************************/ 6510c16b537SWarner Losh /* FSE buffer bounds */ 6520c16b537SWarner Losh #define FSE_NCOUNTBOUND 512 6530c16b537SWarner Losh #define FSE_BLOCKBOUND(size) (size + (size>>7)) 6540c16b537SWarner Losh #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ 6550c16b537SWarner Losh 6560c16b537SWarner Losh /* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */ 6570c16b537SWarner Losh #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2)) 6580c16b537SWarner Losh #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog)) 6590c16b537SWarner Losh 6600c16b537SWarner Losh 6610c16b537SWarner Losh /****************************************** 6620c16b537SWarner Losh * FSE advanced API 6630c16b537SWarner Losh ******************************************/ 6640c16b537SWarner Losh static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits); 6650c16b537SWarner Losh /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */ 6660c16b537SWarner Losh 6670c16b537SWarner Losh static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue); 6680c16b537SWarner Losh /* build a fake FSE_DTable, designed to always generate the same symbolValue */ 6690c16b537SWarner Losh 6700c16b537SWarner Losh 6710c16b537SWarner Losh /****************************************** 6720c16b537SWarner Losh * FSE symbol decompression API 6730c16b537SWarner Losh ******************************************/ 6740c16b537SWarner Losh typedef struct 6750c16b537SWarner Losh { 6760c16b537SWarner Losh size_t state; 6770c16b537SWarner Losh const void* table; /* precise table may vary, depending on U16 */ 6780c16b537SWarner Losh } FSE_DState_t; 6790c16b537SWarner Losh 6800c16b537SWarner Losh 6810c16b537SWarner Losh static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt); 6820c16b537SWarner Losh 6830c16b537SWarner Losh static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD); 6840c16b537SWarner Losh 6850c16b537SWarner Losh static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr); 6860c16b537SWarner Losh 6870c16b537SWarner Losh 6880c16b537SWarner Losh /****************************************** 6890c16b537SWarner Losh * FSE unsafe API 6900c16b537SWarner Losh ******************************************/ 6910c16b537SWarner Losh static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD); 6920c16b537SWarner Losh /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */ 6930c16b537SWarner Losh 6940c16b537SWarner Losh 6950c16b537SWarner Losh /****************************************** 6960c16b537SWarner Losh * Implementation of inline functions 6970c16b537SWarner Losh ******************************************/ 6980c16b537SWarner Losh 6990c16b537SWarner Losh /* decompression */ 7000c16b537SWarner Losh 7010c16b537SWarner Losh typedef struct { 7020c16b537SWarner Losh U16 tableLog; 7030c16b537SWarner Losh U16 fastMode; 7040c16b537SWarner Losh } FSE_DTableHeader; /* sizeof U32 */ 7050c16b537SWarner Losh 7060c16b537SWarner Losh typedef struct 7070c16b537SWarner Losh { 7080c16b537SWarner Losh unsigned short newState; 7090c16b537SWarner Losh unsigned char symbol; 7100c16b537SWarner Losh unsigned char nbBits; 7110c16b537SWarner Losh } FSE_decode_t; /* size == U32 */ 7120c16b537SWarner Losh 7130c16b537SWarner Losh MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt) 7140c16b537SWarner Losh { 7150c16b537SWarner Losh FSE_DTableHeader DTableH; 7160c16b537SWarner Losh memcpy(&DTableH, dt, sizeof(DTableH)); 7170c16b537SWarner Losh DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog); 7180c16b537SWarner Losh BIT_reloadDStream(bitD); 7190c16b537SWarner Losh DStatePtr->table = dt + 1; 7200c16b537SWarner Losh } 7210c16b537SWarner Losh 7220c16b537SWarner Losh MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) 7230c16b537SWarner Losh { 7240c16b537SWarner Losh const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 7250c16b537SWarner Losh const U32 nbBits = DInfo.nbBits; 7260c16b537SWarner Losh BYTE symbol = DInfo.symbol; 7270c16b537SWarner Losh size_t lowBits = BIT_readBits(bitD, nbBits); 7280c16b537SWarner Losh 7290c16b537SWarner Losh DStatePtr->state = DInfo.newState + lowBits; 7300c16b537SWarner Losh return symbol; 7310c16b537SWarner Losh } 7320c16b537SWarner Losh 7330c16b537SWarner Losh MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) 7340c16b537SWarner Losh { 7350c16b537SWarner Losh const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 7360c16b537SWarner Losh const U32 nbBits = DInfo.nbBits; 7370c16b537SWarner Losh BYTE symbol = DInfo.symbol; 7380c16b537SWarner Losh size_t lowBits = BIT_readBitsFast(bitD, nbBits); 7390c16b537SWarner Losh 7400c16b537SWarner Losh DStatePtr->state = DInfo.newState + lowBits; 7410c16b537SWarner Losh return symbol; 7420c16b537SWarner Losh } 7430c16b537SWarner Losh 7440c16b537SWarner Losh MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr) 7450c16b537SWarner Losh { 7460c16b537SWarner Losh return DStatePtr->state == 0; 7470c16b537SWarner Losh } 7480c16b537SWarner Losh 7490c16b537SWarner Losh 7500c16b537SWarner Losh #if defined (__cplusplus) 7510c16b537SWarner Losh } 7520c16b537SWarner Losh #endif 7530c16b537SWarner Losh /* ****************************************************************** 7540c16b537SWarner Losh Huff0 : Huffman coder, part of New Generation Entropy library 7550c16b537SWarner Losh header file for static linking (only) 7560c16b537SWarner Losh Copyright (C) 2013-2015, Yann Collet 7570c16b537SWarner Losh 7580c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 7590c16b537SWarner Losh 7600c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 7610c16b537SWarner Losh modification, are permitted provided that the following conditions are 7620c16b537SWarner Losh met: 7630c16b537SWarner Losh 7640c16b537SWarner Losh * Redistributions of source code must retain the above copyright 7650c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 7660c16b537SWarner Losh * Redistributions in binary form must reproduce the above 7670c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 7680c16b537SWarner Losh in the documentation and/or other materials provided with the 7690c16b537SWarner Losh distribution. 7700c16b537SWarner Losh 7710c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 7720c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 7730c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 7740c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 7750c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 7760c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 7770c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 7780c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 7790c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 7800c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 7810c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 7820c16b537SWarner Losh 7830c16b537SWarner Losh You can contact the author at : 7840c16b537SWarner Losh - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 7850c16b537SWarner Losh - Public forum : https://groups.google.com/forum/#!forum/lz4c 7860c16b537SWarner Losh ****************************************************************** */ 7870c16b537SWarner Losh 7880c16b537SWarner Losh #if defined (__cplusplus) 7890c16b537SWarner Losh extern "C" { 7900c16b537SWarner Losh #endif 7910c16b537SWarner Losh 7920c16b537SWarner Losh /****************************************** 7930c16b537SWarner Losh * Static allocation macros 7940c16b537SWarner Losh ******************************************/ 7950c16b537SWarner Losh /* Huff0 buffer bounds */ 7960c16b537SWarner Losh #define HUF_CTABLEBOUND 129 7970c16b537SWarner Losh #define HUF_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */ 7980c16b537SWarner Losh #define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ 7990c16b537SWarner Losh 8000c16b537SWarner Losh /* static allocation of Huff0's DTable */ 8010c16b537SWarner Losh #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */ 8020c16b537SWarner Losh #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \ 8030c16b537SWarner Losh unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 8040c16b537SWarner Losh #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \ 8050c16b537SWarner Losh unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog } 8060c16b537SWarner Losh #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \ 8070c16b537SWarner Losh unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog } 8080c16b537SWarner Losh 8090c16b537SWarner Losh 8100c16b537SWarner Losh /****************************************** 8110c16b537SWarner Losh * Advanced functions 8120c16b537SWarner Losh ******************************************/ 8130c16b537SWarner Losh static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ 8140c16b537SWarner Losh static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */ 8150c16b537SWarner Losh 8160c16b537SWarner Losh 8170c16b537SWarner Losh #if defined (__cplusplus) 8180c16b537SWarner Losh } 8190c16b537SWarner Losh #endif 8200c16b537SWarner Losh 8210c16b537SWarner Losh /* 8220c16b537SWarner Losh zstd - standard compression library 8230c16b537SWarner Losh Header File 8240c16b537SWarner Losh Copyright (C) 2014-2015, Yann Collet. 8250c16b537SWarner Losh 8260c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 8270c16b537SWarner Losh 8280c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 8290c16b537SWarner Losh modification, are permitted provided that the following conditions are 8300c16b537SWarner Losh met: 8310c16b537SWarner Losh * Redistributions of source code must retain the above copyright 8320c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 8330c16b537SWarner Losh * Redistributions in binary form must reproduce the above 8340c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 8350c16b537SWarner Losh in the documentation and/or other materials provided with the 8360c16b537SWarner Losh distribution. 8370c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 8380c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 8390c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 8400c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 8410c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 8420c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 8430c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 8440c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 8450c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 8460c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 8470c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 8480c16b537SWarner Losh 8490c16b537SWarner Losh You can contact the author at : 8500c16b537SWarner Losh - zstd source repository : https://github.com/Cyan4973/zstd 8510c16b537SWarner Losh - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c 8520c16b537SWarner Losh */ 8530c16b537SWarner Losh 8540c16b537SWarner Losh #if defined (__cplusplus) 8550c16b537SWarner Losh extern "C" { 8560c16b537SWarner Losh #endif 8570c16b537SWarner Losh 8580c16b537SWarner Losh /* ************************************* 8590c16b537SWarner Losh * Includes 8600c16b537SWarner Losh ***************************************/ 8610c16b537SWarner Losh #include <stddef.h> /* size_t */ 8620c16b537SWarner Losh 8630c16b537SWarner Losh 8640c16b537SWarner Losh /* ************************************* 8650c16b537SWarner Losh * Version 8660c16b537SWarner Losh ***************************************/ 8670c16b537SWarner Losh #define ZSTD_VERSION_MAJOR 0 /* for breaking interface changes */ 8680c16b537SWarner Losh #define ZSTD_VERSION_MINOR 2 /* for new (non-breaking) interface capabilities */ 8690c16b537SWarner Losh #define ZSTD_VERSION_RELEASE 2 /* for tweaks, bug-fixes, or development */ 8700c16b537SWarner Losh #define ZSTD_VERSION_NUMBER (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE) 8710c16b537SWarner Losh 8720c16b537SWarner Losh 8730c16b537SWarner Losh /* ************************************* 8740c16b537SWarner Losh * Advanced functions 8750c16b537SWarner Losh ***************************************/ 8760c16b537SWarner Losh typedef struct ZSTD_CCtx_s ZSTD_CCtx; /* incomplete type */ 8770c16b537SWarner Losh 8780c16b537SWarner Losh #if defined (__cplusplus) 8790c16b537SWarner Losh } 8800c16b537SWarner Losh #endif 8810c16b537SWarner Losh /* 8820c16b537SWarner Losh zstd - standard compression library 8830c16b537SWarner Losh Header File for static linking only 8840c16b537SWarner Losh Copyright (C) 2014-2015, Yann Collet. 8850c16b537SWarner Losh 8860c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 8870c16b537SWarner Losh 8880c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 8890c16b537SWarner Losh modification, are permitted provided that the following conditions are 8900c16b537SWarner Losh met: 8910c16b537SWarner Losh * Redistributions of source code must retain the above copyright 8920c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 8930c16b537SWarner Losh * Redistributions in binary form must reproduce the above 8940c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 8950c16b537SWarner Losh in the documentation and/or other materials provided with the 8960c16b537SWarner Losh distribution. 8970c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 8980c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 8990c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 9000c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 9010c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 9020c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 9030c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 9040c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 9050c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 9060c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 9070c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 9080c16b537SWarner Losh 9090c16b537SWarner Losh You can contact the author at : 9100c16b537SWarner Losh - zstd source repository : https://github.com/Cyan4973/zstd 9110c16b537SWarner Losh - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c 9120c16b537SWarner Losh */ 9130c16b537SWarner Losh 9140c16b537SWarner Losh /* The objects defined into this file should be considered experimental. 9150c16b537SWarner Losh * They are not labelled stable, as their prototype may change in the future. 9160c16b537SWarner Losh * You can use them for tests, provide feedback, or if you can endure risk of future changes. 9170c16b537SWarner Losh */ 9180c16b537SWarner Losh 9190c16b537SWarner Losh #if defined (__cplusplus) 9200c16b537SWarner Losh extern "C" { 9210c16b537SWarner Losh #endif 9220c16b537SWarner Losh 9230c16b537SWarner Losh /* ************************************* 9240c16b537SWarner Losh * Streaming functions 9250c16b537SWarner Losh ***************************************/ 9260c16b537SWarner Losh 9270c16b537SWarner Losh typedef struct ZSTD_DCtx_s ZSTD_DCtx; 9280c16b537SWarner Losh 9290c16b537SWarner Losh /* 9300c16b537SWarner Losh Use above functions alternatively. 9310c16b537SWarner Losh ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue(). 9320c16b537SWarner Losh ZSTD_decompressContinue() will use previous data blocks to improve compression if they are located prior to current block. 9330c16b537SWarner Losh Result is the number of bytes regenerated within 'dst'. 9340c16b537SWarner Losh It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header. 9350c16b537SWarner Losh */ 9360c16b537SWarner Losh 9370c16b537SWarner Losh /* ************************************* 9380c16b537SWarner Losh * Prefix - version detection 9390c16b537SWarner Losh ***************************************/ 9400c16b537SWarner Losh #define ZSTD_magicNumber 0xFD2FB523 /* v0.3 */ 9410c16b537SWarner Losh 9420c16b537SWarner Losh 9430c16b537SWarner Losh #if defined (__cplusplus) 9440c16b537SWarner Losh } 9450c16b537SWarner Losh #endif 9460c16b537SWarner Losh /* ****************************************************************** 9470c16b537SWarner Losh FSE : Finite State Entropy coder 9480c16b537SWarner Losh Copyright (C) 2013-2015, Yann Collet. 9490c16b537SWarner Losh 9500c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 9510c16b537SWarner Losh 9520c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 9530c16b537SWarner Losh modification, are permitted provided that the following conditions are 9540c16b537SWarner Losh met: 9550c16b537SWarner Losh 9560c16b537SWarner Losh * Redistributions of source code must retain the above copyright 9570c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 9580c16b537SWarner Losh * Redistributions in binary form must reproduce the above 9590c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 9600c16b537SWarner Losh in the documentation and/or other materials provided with the 9610c16b537SWarner Losh distribution. 9620c16b537SWarner Losh 9630c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 9640c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 9650c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 9660c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 9670c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 9680c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 9690c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 9700c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 9710c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 9720c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 9730c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 9740c16b537SWarner Losh 9750c16b537SWarner Losh You can contact the author at : 9760c16b537SWarner Losh - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy 9770c16b537SWarner Losh - Public forum : https://groups.google.com/forum/#!forum/lz4c 9780c16b537SWarner Losh ****************************************************************** */ 9790c16b537SWarner Losh 9800c16b537SWarner Losh #ifndef FSE_COMMONDEFS_ONLY 9810c16b537SWarner Losh 9820c16b537SWarner Losh /**************************************************************** 9830c16b537SWarner Losh * Tuning parameters 9840c16b537SWarner Losh ****************************************************************/ 9850c16b537SWarner Losh /* MEMORY_USAGE : 9860c16b537SWarner Losh * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) 9870c16b537SWarner Losh * Increasing memory usage improves compression ratio 9880c16b537SWarner Losh * Reduced memory usage can improve speed, due to cache effect 9890c16b537SWarner Losh * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */ 9900c16b537SWarner Losh #define FSE_MAX_MEMORY_USAGE 14 9910c16b537SWarner Losh #define FSE_DEFAULT_MEMORY_USAGE 13 9920c16b537SWarner Losh 9930c16b537SWarner Losh /* FSE_MAX_SYMBOL_VALUE : 9940c16b537SWarner Losh * Maximum symbol value authorized. 9950c16b537SWarner Losh * Required for proper stack allocation */ 9960c16b537SWarner Losh #define FSE_MAX_SYMBOL_VALUE 255 9970c16b537SWarner Losh 9980c16b537SWarner Losh 9990c16b537SWarner Losh /**************************************************************** 10000c16b537SWarner Losh * template functions type & suffix 10010c16b537SWarner Losh ****************************************************************/ 10020c16b537SWarner Losh #define FSE_FUNCTION_TYPE BYTE 10030c16b537SWarner Losh #define FSE_FUNCTION_EXTENSION 10040c16b537SWarner Losh 10050c16b537SWarner Losh 10060c16b537SWarner Losh /**************************************************************** 10070c16b537SWarner Losh * Byte symbol type 10080c16b537SWarner Losh ****************************************************************/ 10090c16b537SWarner Losh #endif /* !FSE_COMMONDEFS_ONLY */ 10100c16b537SWarner Losh 10110c16b537SWarner Losh 10120c16b537SWarner Losh /**************************************************************** 10130c16b537SWarner Losh * Compiler specifics 10140c16b537SWarner Losh ****************************************************************/ 10150c16b537SWarner Losh #ifdef _MSC_VER /* Visual Studio */ 10160c16b537SWarner Losh # define FORCE_INLINE static __forceinline 10170c16b537SWarner Losh # include <intrin.h> /* For Visual 2005 */ 10180c16b537SWarner Losh # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 10190c16b537SWarner Losh # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */ 10200c16b537SWarner Losh #else 10210c16b537SWarner Losh # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 10220c16b537SWarner Losh # ifdef __GNUC__ 10230c16b537SWarner Losh # define FORCE_INLINE static inline __attribute__((always_inline)) 10240c16b537SWarner Losh # else 10250c16b537SWarner Losh # define FORCE_INLINE static inline 10260c16b537SWarner Losh # endif 10270c16b537SWarner Losh # else 10280c16b537SWarner Losh # define FORCE_INLINE static 10290c16b537SWarner Losh # endif /* __STDC_VERSION__ */ 10300c16b537SWarner Losh #endif 10310c16b537SWarner Losh 10320c16b537SWarner Losh 10330c16b537SWarner Losh /**************************************************************** 10340c16b537SWarner Losh * Includes 10350c16b537SWarner Losh ****************************************************************/ 10360c16b537SWarner Losh #include <stdlib.h> /* malloc, free, qsort */ 10370c16b537SWarner Losh #include <string.h> /* memcpy, memset */ 10380c16b537SWarner Losh #include <stdio.h> /* printf (debug) */ 10390c16b537SWarner Losh 10400c16b537SWarner Losh /**************************************************************** 10410c16b537SWarner Losh * Constants 10420c16b537SWarner Losh *****************************************************************/ 10430c16b537SWarner Losh #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2) 10440c16b537SWarner Losh #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG) 10450c16b537SWarner Losh #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1) 10460c16b537SWarner Losh #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2) 10470c16b537SWarner Losh #define FSE_MIN_TABLELOG 5 10480c16b537SWarner Losh 10490c16b537SWarner Losh #define FSE_TABLELOG_ABSOLUTE_MAX 15 10500c16b537SWarner Losh #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX 10510c16b537SWarner Losh #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported" 10520c16b537SWarner Losh #endif 10530c16b537SWarner Losh 10540c16b537SWarner Losh 10550c16b537SWarner Losh /**************************************************************** 10560c16b537SWarner Losh * Error Management 10570c16b537SWarner Losh ****************************************************************/ 10580c16b537SWarner Losh #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 10590c16b537SWarner Losh 10600c16b537SWarner Losh 10610c16b537SWarner Losh /**************************************************************** 10620c16b537SWarner Losh * Complex types 10630c16b537SWarner Losh ****************************************************************/ 10640c16b537SWarner Losh typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]; 10650c16b537SWarner Losh 10660c16b537SWarner Losh 10670c16b537SWarner Losh /**************************************************************** 10680c16b537SWarner Losh * Templates 10690c16b537SWarner Losh ****************************************************************/ 10700c16b537SWarner Losh /* 10710c16b537SWarner Losh designed to be included 10720c16b537SWarner Losh for type-specific functions (template emulation in C) 10730c16b537SWarner Losh Objective is to write these functions only once, for improved maintenance 10740c16b537SWarner Losh */ 10750c16b537SWarner Losh 10760c16b537SWarner Losh /* safety checks */ 10770c16b537SWarner Losh #ifndef FSE_FUNCTION_EXTENSION 10780c16b537SWarner Losh # error "FSE_FUNCTION_EXTENSION must be defined" 10790c16b537SWarner Losh #endif 10800c16b537SWarner Losh #ifndef FSE_FUNCTION_TYPE 10810c16b537SWarner Losh # error "FSE_FUNCTION_TYPE must be defined" 10820c16b537SWarner Losh #endif 10830c16b537SWarner Losh 10840c16b537SWarner Losh /* Function names */ 10850c16b537SWarner Losh #define FSE_CAT(X,Y) X##Y 10860c16b537SWarner Losh #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y) 10870c16b537SWarner Losh #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y) 10880c16b537SWarner Losh 10890c16b537SWarner Losh 10900c16b537SWarner Losh /* Function templates */ 10910c16b537SWarner Losh 10920c16b537SWarner Losh #define FSE_DECODE_TYPE FSE_decode_t 10930c16b537SWarner Losh 10940c16b537SWarner Losh static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; } 10950c16b537SWarner Losh 10960c16b537SWarner Losh static size_t FSE_buildDTable 10970c16b537SWarner Losh (FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) 10980c16b537SWarner Losh { 10990c16b537SWarner Losh void* ptr = dt+1; 11000c16b537SWarner Losh FSE_DTableHeader DTableH; 11010c16b537SWarner Losh FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)ptr; 11020c16b537SWarner Losh const U32 tableSize = 1 << tableLog; 11030c16b537SWarner Losh const U32 tableMask = tableSize-1; 11040c16b537SWarner Losh const U32 step = FSE_tableStep(tableSize); 11050c16b537SWarner Losh U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1]; 11060c16b537SWarner Losh U32 position = 0; 11070c16b537SWarner Losh U32 highThreshold = tableSize-1; 11080c16b537SWarner Losh const S16 largeLimit= (S16)(1 << (tableLog-1)); 11090c16b537SWarner Losh U32 noLarge = 1; 11100c16b537SWarner Losh U32 s; 11110c16b537SWarner Losh 11120c16b537SWarner Losh /* Sanity Checks */ 11130c16b537SWarner Losh if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge); 11140c16b537SWarner Losh if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); 11150c16b537SWarner Losh 11160c16b537SWarner Losh /* Init, lay down lowprob symbols */ 11170c16b537SWarner Losh DTableH.tableLog = (U16)tableLog; 11180c16b537SWarner Losh for (s=0; s<=maxSymbolValue; s++) 11190c16b537SWarner Losh { 11200c16b537SWarner Losh if (normalizedCounter[s]==-1) 11210c16b537SWarner Losh { 11220c16b537SWarner Losh tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s; 11230c16b537SWarner Losh symbolNext[s] = 1; 11240c16b537SWarner Losh } 11250c16b537SWarner Losh else 11260c16b537SWarner Losh { 11270c16b537SWarner Losh if (normalizedCounter[s] >= largeLimit) noLarge=0; 11280c16b537SWarner Losh symbolNext[s] = normalizedCounter[s]; 11290c16b537SWarner Losh } 11300c16b537SWarner Losh } 11310c16b537SWarner Losh 11320c16b537SWarner Losh /* Spread symbols */ 11330c16b537SWarner Losh for (s=0; s<=maxSymbolValue; s++) 11340c16b537SWarner Losh { 11350c16b537SWarner Losh int i; 11360c16b537SWarner Losh for (i=0; i<normalizedCounter[s]; i++) 11370c16b537SWarner Losh { 11380c16b537SWarner Losh tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s; 11390c16b537SWarner Losh position = (position + step) & tableMask; 11400c16b537SWarner Losh while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */ 11410c16b537SWarner Losh } 11420c16b537SWarner Losh } 11430c16b537SWarner Losh 11440c16b537SWarner Losh if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ 11450c16b537SWarner Losh 11460c16b537SWarner Losh /* Build Decoding table */ 11470c16b537SWarner Losh { 11480c16b537SWarner Losh U32 i; 11490c16b537SWarner Losh for (i=0; i<tableSize; i++) 11500c16b537SWarner Losh { 11510c16b537SWarner Losh FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol); 11520c16b537SWarner Losh U16 nextState = symbolNext[symbol]++; 11530c16b537SWarner Losh tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) ); 11540c16b537SWarner Losh tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize); 11550c16b537SWarner Losh } 11560c16b537SWarner Losh } 11570c16b537SWarner Losh 11580c16b537SWarner Losh DTableH.fastMode = (U16)noLarge; 11590c16b537SWarner Losh memcpy(dt, &DTableH, sizeof(DTableH)); 11600c16b537SWarner Losh return 0; 11610c16b537SWarner Losh } 11620c16b537SWarner Losh 11630c16b537SWarner Losh 11640c16b537SWarner Losh #ifndef FSE_COMMONDEFS_ONLY 11650c16b537SWarner Losh /****************************************** 11660c16b537SWarner Losh * FSE helper functions 11670c16b537SWarner Losh ******************************************/ 11680c16b537SWarner Losh static unsigned FSE_isError(size_t code) { return ERR_isError(code); } 11690c16b537SWarner Losh 11700c16b537SWarner Losh 11710c16b537SWarner Losh /**************************************************************** 11720c16b537SWarner Losh * FSE NCount encoding-decoding 11730c16b537SWarner Losh ****************************************************************/ 11740c16b537SWarner Losh static short FSE_abs(short a) 11750c16b537SWarner Losh { 11760c16b537SWarner Losh return a<0 ? -a : a; 11770c16b537SWarner Losh } 11780c16b537SWarner Losh 11790c16b537SWarner Losh static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr, 11800c16b537SWarner Losh const void* headerBuffer, size_t hbSize) 11810c16b537SWarner Losh { 11820c16b537SWarner Losh const BYTE* const istart = (const BYTE*) headerBuffer; 11830c16b537SWarner Losh const BYTE* const iend = istart + hbSize; 11840c16b537SWarner Losh const BYTE* ip = istart; 11850c16b537SWarner Losh int nbBits; 11860c16b537SWarner Losh int remaining; 11870c16b537SWarner Losh int threshold; 11880c16b537SWarner Losh U32 bitStream; 11890c16b537SWarner Losh int bitCount; 11900c16b537SWarner Losh unsigned charnum = 0; 11910c16b537SWarner Losh int previous0 = 0; 11920c16b537SWarner Losh 11930c16b537SWarner Losh if (hbSize < 4) return ERROR(srcSize_wrong); 11940c16b537SWarner Losh bitStream = MEM_readLE32(ip); 11950c16b537SWarner Losh nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */ 11960c16b537SWarner Losh if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge); 11970c16b537SWarner Losh bitStream >>= 4; 11980c16b537SWarner Losh bitCount = 4; 11990c16b537SWarner Losh *tableLogPtr = nbBits; 12000c16b537SWarner Losh remaining = (1<<nbBits)+1; 12010c16b537SWarner Losh threshold = 1<<nbBits; 12020c16b537SWarner Losh nbBits++; 12030c16b537SWarner Losh 12040c16b537SWarner Losh while ((remaining>1) && (charnum<=*maxSVPtr)) 12050c16b537SWarner Losh { 12060c16b537SWarner Losh if (previous0) 12070c16b537SWarner Losh { 12080c16b537SWarner Losh unsigned n0 = charnum; 12090c16b537SWarner Losh while ((bitStream & 0xFFFF) == 0xFFFF) 12100c16b537SWarner Losh { 12110c16b537SWarner Losh n0+=24; 12120c16b537SWarner Losh if (ip < iend-5) 12130c16b537SWarner Losh { 12140c16b537SWarner Losh ip+=2; 12150c16b537SWarner Losh bitStream = MEM_readLE32(ip) >> bitCount; 12160c16b537SWarner Losh } 12170c16b537SWarner Losh else 12180c16b537SWarner Losh { 12190c16b537SWarner Losh bitStream >>= 16; 12200c16b537SWarner Losh bitCount+=16; 12210c16b537SWarner Losh } 12220c16b537SWarner Losh } 12230c16b537SWarner Losh while ((bitStream & 3) == 3) 12240c16b537SWarner Losh { 12250c16b537SWarner Losh n0+=3; 12260c16b537SWarner Losh bitStream>>=2; 12270c16b537SWarner Losh bitCount+=2; 12280c16b537SWarner Losh } 12290c16b537SWarner Losh n0 += bitStream & 3; 12300c16b537SWarner Losh bitCount += 2; 12310c16b537SWarner Losh if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall); 12320c16b537SWarner Losh while (charnum < n0) normalizedCounter[charnum++] = 0; 12330c16b537SWarner Losh if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) 12340c16b537SWarner Losh { 12350c16b537SWarner Losh ip += bitCount>>3; 12360c16b537SWarner Losh bitCount &= 7; 12370c16b537SWarner Losh bitStream = MEM_readLE32(ip) >> bitCount; 12380c16b537SWarner Losh } 12390c16b537SWarner Losh else 12400c16b537SWarner Losh bitStream >>= 2; 12410c16b537SWarner Losh } 12420c16b537SWarner Losh { 12430c16b537SWarner Losh const short max = (short)((2*threshold-1)-remaining); 12440c16b537SWarner Losh short count; 12450c16b537SWarner Losh 12460c16b537SWarner Losh if ((bitStream & (threshold-1)) < (U32)max) 12470c16b537SWarner Losh { 12480c16b537SWarner Losh count = (short)(bitStream & (threshold-1)); 12490c16b537SWarner Losh bitCount += nbBits-1; 12500c16b537SWarner Losh } 12510c16b537SWarner Losh else 12520c16b537SWarner Losh { 12530c16b537SWarner Losh count = (short)(bitStream & (2*threshold-1)); 12540c16b537SWarner Losh if (count >= threshold) count -= max; 12550c16b537SWarner Losh bitCount += nbBits; 12560c16b537SWarner Losh } 12570c16b537SWarner Losh 12580c16b537SWarner Losh count--; /* extra accuracy */ 12590c16b537SWarner Losh remaining -= FSE_abs(count); 12600c16b537SWarner Losh normalizedCounter[charnum++] = count; 12610c16b537SWarner Losh previous0 = !count; 12620c16b537SWarner Losh while (remaining < threshold) 12630c16b537SWarner Losh { 12640c16b537SWarner Losh nbBits--; 12650c16b537SWarner Losh threshold >>= 1; 12660c16b537SWarner Losh } 12670c16b537SWarner Losh 12680c16b537SWarner Losh { 12690c16b537SWarner Losh if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) 12700c16b537SWarner Losh { 12710c16b537SWarner Losh ip += bitCount>>3; 12720c16b537SWarner Losh bitCount &= 7; 12730c16b537SWarner Losh } 12740c16b537SWarner Losh else 12750c16b537SWarner Losh { 12760c16b537SWarner Losh bitCount -= (int)(8 * (iend - 4 - ip)); 12770c16b537SWarner Losh ip = iend - 4; 12780c16b537SWarner Losh } 12790c16b537SWarner Losh bitStream = MEM_readLE32(ip) >> (bitCount & 31); 12800c16b537SWarner Losh } 12810c16b537SWarner Losh } 12820c16b537SWarner Losh } 12830c16b537SWarner Losh if (remaining != 1) return ERROR(GENERIC); 12840c16b537SWarner Losh *maxSVPtr = charnum-1; 12850c16b537SWarner Losh 12860c16b537SWarner Losh ip += (bitCount+7)>>3; 12870c16b537SWarner Losh if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong); 12880c16b537SWarner Losh return ip-istart; 12890c16b537SWarner Losh } 12900c16b537SWarner Losh 12910c16b537SWarner Losh 12920c16b537SWarner Losh /********************************************************* 12930c16b537SWarner Losh * Decompression (Byte symbols) 12940c16b537SWarner Losh *********************************************************/ 12950c16b537SWarner Losh static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue) 12960c16b537SWarner Losh { 12970c16b537SWarner Losh void* ptr = dt; 12980c16b537SWarner Losh FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 12990c16b537SWarner Losh FSE_decode_t* const cell = (FSE_decode_t*)(ptr) + 1; 13000c16b537SWarner Losh 13010c16b537SWarner Losh DTableH->tableLog = 0; 13020c16b537SWarner Losh DTableH->fastMode = 0; 13030c16b537SWarner Losh 13040c16b537SWarner Losh cell->newState = 0; 13050c16b537SWarner Losh cell->symbol = symbolValue; 13060c16b537SWarner Losh cell->nbBits = 0; 13070c16b537SWarner Losh 13080c16b537SWarner Losh return 0; 13090c16b537SWarner Losh } 13100c16b537SWarner Losh 13110c16b537SWarner Losh 13120c16b537SWarner Losh static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits) 13130c16b537SWarner Losh { 13140c16b537SWarner Losh void* ptr = dt; 13150c16b537SWarner Losh FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 13160c16b537SWarner Losh FSE_decode_t* const dinfo = (FSE_decode_t*)(ptr) + 1; 13170c16b537SWarner Losh const unsigned tableSize = 1 << nbBits; 13180c16b537SWarner Losh const unsigned tableMask = tableSize - 1; 13190c16b537SWarner Losh const unsigned maxSymbolValue = tableMask; 13200c16b537SWarner Losh unsigned s; 13210c16b537SWarner Losh 13220c16b537SWarner Losh /* Sanity checks */ 13230c16b537SWarner Losh if (nbBits < 1) return ERROR(GENERIC); /* min size */ 13240c16b537SWarner Losh 13250c16b537SWarner Losh /* Build Decoding Table */ 13260c16b537SWarner Losh DTableH->tableLog = (U16)nbBits; 13270c16b537SWarner Losh DTableH->fastMode = 1; 13280c16b537SWarner Losh for (s=0; s<=maxSymbolValue; s++) 13290c16b537SWarner Losh { 13300c16b537SWarner Losh dinfo[s].newState = 0; 13310c16b537SWarner Losh dinfo[s].symbol = (BYTE)s; 13320c16b537SWarner Losh dinfo[s].nbBits = (BYTE)nbBits; 13330c16b537SWarner Losh } 13340c16b537SWarner Losh 13350c16b537SWarner Losh return 0; 13360c16b537SWarner Losh } 13370c16b537SWarner Losh 13380c16b537SWarner Losh FORCE_INLINE size_t FSE_decompress_usingDTable_generic( 13390c16b537SWarner Losh void* dst, size_t maxDstSize, 13400c16b537SWarner Losh const void* cSrc, size_t cSrcSize, 13410c16b537SWarner Losh const FSE_DTable* dt, const unsigned fast) 13420c16b537SWarner Losh { 13430c16b537SWarner Losh BYTE* const ostart = (BYTE*) dst; 13440c16b537SWarner Losh BYTE* op = ostart; 13450c16b537SWarner Losh BYTE* const omax = op + maxDstSize; 13460c16b537SWarner Losh BYTE* const olimit = omax-3; 13470c16b537SWarner Losh 13480c16b537SWarner Losh BIT_DStream_t bitD; 13490c16b537SWarner Losh FSE_DState_t state1; 13500c16b537SWarner Losh FSE_DState_t state2; 13510c16b537SWarner Losh size_t errorCode; 13520c16b537SWarner Losh 13530c16b537SWarner Losh /* Init */ 13540c16b537SWarner Losh errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */ 13550c16b537SWarner Losh if (FSE_isError(errorCode)) return errorCode; 13560c16b537SWarner Losh 13570c16b537SWarner Losh FSE_initDState(&state1, &bitD, dt); 13580c16b537SWarner Losh FSE_initDState(&state2, &bitD, dt); 13590c16b537SWarner Losh 13600c16b537SWarner Losh #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD) 13610c16b537SWarner Losh 13620c16b537SWarner Losh /* 4 symbols per loop */ 13630c16b537SWarner Losh for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4) 13640c16b537SWarner Losh { 13650c16b537SWarner Losh op[0] = FSE_GETSYMBOL(&state1); 13660c16b537SWarner Losh 13670c16b537SWarner Losh if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 13680c16b537SWarner Losh BIT_reloadDStream(&bitD); 13690c16b537SWarner Losh 13700c16b537SWarner Losh op[1] = FSE_GETSYMBOL(&state2); 13710c16b537SWarner Losh 13720c16b537SWarner Losh if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 13730c16b537SWarner Losh { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } } 13740c16b537SWarner Losh 13750c16b537SWarner Losh op[2] = FSE_GETSYMBOL(&state1); 13760c16b537SWarner Losh 13770c16b537SWarner Losh if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 13780c16b537SWarner Losh BIT_reloadDStream(&bitD); 13790c16b537SWarner Losh 13800c16b537SWarner Losh op[3] = FSE_GETSYMBOL(&state2); 13810c16b537SWarner Losh } 13820c16b537SWarner Losh 13830c16b537SWarner Losh /* tail */ 13840c16b537SWarner Losh /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */ 13850c16b537SWarner Losh while (1) 13860c16b537SWarner Losh { 13870c16b537SWarner Losh if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) ) 13880c16b537SWarner Losh break; 13890c16b537SWarner Losh 13900c16b537SWarner Losh *op++ = FSE_GETSYMBOL(&state1); 13910c16b537SWarner Losh 13920c16b537SWarner Losh if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) ) 13930c16b537SWarner Losh break; 13940c16b537SWarner Losh 13950c16b537SWarner Losh *op++ = FSE_GETSYMBOL(&state2); 13960c16b537SWarner Losh } 13970c16b537SWarner Losh 13980c16b537SWarner Losh /* end ? */ 13990c16b537SWarner Losh if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2)) 14000c16b537SWarner Losh return op-ostart; 14010c16b537SWarner Losh 14020c16b537SWarner Losh if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */ 14030c16b537SWarner Losh 14040c16b537SWarner Losh return ERROR(corruption_detected); 14050c16b537SWarner Losh } 14060c16b537SWarner Losh 14070c16b537SWarner Losh 14080c16b537SWarner Losh static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize, 14090c16b537SWarner Losh const void* cSrc, size_t cSrcSize, 14100c16b537SWarner Losh const FSE_DTable* dt) 14110c16b537SWarner Losh { 14120c16b537SWarner Losh FSE_DTableHeader DTableH; 14130c16b537SWarner Losh memcpy(&DTableH, dt, sizeof(DTableH)); 14140c16b537SWarner Losh 14150c16b537SWarner Losh /* select fast mode (static) */ 14160c16b537SWarner Losh if (DTableH.fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1); 14170c16b537SWarner Losh return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0); 14180c16b537SWarner Losh } 14190c16b537SWarner Losh 14200c16b537SWarner Losh 14210c16b537SWarner Losh static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize) 14220c16b537SWarner Losh { 14230c16b537SWarner Losh const BYTE* const istart = (const BYTE*)cSrc; 14240c16b537SWarner Losh const BYTE* ip = istart; 14250c16b537SWarner Losh short counting[FSE_MAX_SYMBOL_VALUE+1]; 14260c16b537SWarner Losh DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */ 14270c16b537SWarner Losh unsigned tableLog; 14280c16b537SWarner Losh unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE; 14290c16b537SWarner Losh size_t errorCode; 14300c16b537SWarner Losh 14310c16b537SWarner Losh if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */ 14320c16b537SWarner Losh 14330c16b537SWarner Losh /* normal FSE decoding mode */ 14340c16b537SWarner Losh errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize); 14350c16b537SWarner Losh if (FSE_isError(errorCode)) return errorCode; 14360c16b537SWarner Losh if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */ 14370c16b537SWarner Losh ip += errorCode; 14380c16b537SWarner Losh cSrcSize -= errorCode; 14390c16b537SWarner Losh 14400c16b537SWarner Losh errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog); 14410c16b537SWarner Losh if (FSE_isError(errorCode)) return errorCode; 14420c16b537SWarner Losh 14430c16b537SWarner Losh /* always return, even if it is an error code */ 14440c16b537SWarner Losh return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); 14450c16b537SWarner Losh } 14460c16b537SWarner Losh 14470c16b537SWarner Losh 14480c16b537SWarner Losh 14490c16b537SWarner Losh #endif /* FSE_COMMONDEFS_ONLY */ 14500c16b537SWarner Losh /* ****************************************************************** 14510c16b537SWarner Losh Huff0 : Huffman coder, part of New Generation Entropy library 14520c16b537SWarner Losh Copyright (C) 2013-2015, Yann Collet. 14530c16b537SWarner Losh 14540c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 14550c16b537SWarner Losh 14560c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 14570c16b537SWarner Losh modification, are permitted provided that the following conditions are 14580c16b537SWarner Losh met: 14590c16b537SWarner Losh 14600c16b537SWarner Losh * Redistributions of source code must retain the above copyright 14610c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 14620c16b537SWarner Losh * Redistributions in binary form must reproduce the above 14630c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 14640c16b537SWarner Losh in the documentation and/or other materials provided with the 14650c16b537SWarner Losh distribution. 14660c16b537SWarner Losh 14670c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 14680c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 14690c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 14700c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 14710c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 14720c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 14730c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 14740c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 14750c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 14760c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 14770c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 14780c16b537SWarner Losh 14790c16b537SWarner Losh You can contact the author at : 14800c16b537SWarner Losh - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy 14810c16b537SWarner Losh - Public forum : https://groups.google.com/forum/#!forum/lz4c 14820c16b537SWarner Losh ****************************************************************** */ 14830c16b537SWarner Losh 14840c16b537SWarner Losh /**************************************************************** 14850c16b537SWarner Losh * Compiler specifics 14860c16b537SWarner Losh ****************************************************************/ 14870c16b537SWarner Losh #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 14880c16b537SWarner Losh /* inline is defined */ 14890c16b537SWarner Losh #elif defined(_MSC_VER) 14900c16b537SWarner Losh # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 14910c16b537SWarner Losh # define inline __inline 14920c16b537SWarner Losh #else 14930c16b537SWarner Losh # define inline /* disable inline */ 14940c16b537SWarner Losh #endif 14950c16b537SWarner Losh 14960c16b537SWarner Losh 14970c16b537SWarner Losh /**************************************************************** 14980c16b537SWarner Losh * Includes 14990c16b537SWarner Losh ****************************************************************/ 15000c16b537SWarner Losh #include <stdlib.h> /* malloc, free, qsort */ 15010c16b537SWarner Losh #include <string.h> /* memcpy, memset */ 15020c16b537SWarner Losh #include <stdio.h> /* printf (debug) */ 15030c16b537SWarner Losh 15040c16b537SWarner Losh /**************************************************************** 15050c16b537SWarner Losh * Error Management 15060c16b537SWarner Losh ****************************************************************/ 15070c16b537SWarner Losh #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 15080c16b537SWarner Losh 15090c16b537SWarner Losh 15100c16b537SWarner Losh /****************************************** 15110c16b537SWarner Losh * Helper functions 15120c16b537SWarner Losh ******************************************/ 15130c16b537SWarner Losh static unsigned HUF_isError(size_t code) { return ERR_isError(code); } 15140c16b537SWarner Losh 15150c16b537SWarner Losh #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */ 15160c16b537SWarner Losh #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */ 15170c16b537SWarner Losh #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */ 15180c16b537SWarner Losh #define HUF_MAX_SYMBOL_VALUE 255 15190c16b537SWarner Losh #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG) 15200c16b537SWarner Losh # error "HUF_MAX_TABLELOG is too large !" 15210c16b537SWarner Losh #endif 15220c16b537SWarner Losh 15230c16b537SWarner Losh 15240c16b537SWarner Losh 15250c16b537SWarner Losh /********************************************************* 15260c16b537SWarner Losh * Huff0 : Huffman block decompression 15270c16b537SWarner Losh *********************************************************/ 15280c16b537SWarner Losh typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */ 15290c16b537SWarner Losh 15300c16b537SWarner Losh typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */ 15310c16b537SWarner Losh 15320c16b537SWarner Losh typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t; 15330c16b537SWarner Losh 15340c16b537SWarner Losh /*! HUF_readStats 15350c16b537SWarner Losh Read compact Huffman tree, saved by HUF_writeCTable 15360c16b537SWarner Losh @huffWeight : destination buffer 15370c16b537SWarner Losh @return : size read from `src` 15380c16b537SWarner Losh */ 15390c16b537SWarner Losh static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats, 15400c16b537SWarner Losh U32* nbSymbolsPtr, U32* tableLogPtr, 15410c16b537SWarner Losh const void* src, size_t srcSize) 15420c16b537SWarner Losh { 15430c16b537SWarner Losh U32 weightTotal; 15440c16b537SWarner Losh U32 tableLog; 15450c16b537SWarner Losh const BYTE* ip = (const BYTE*) src; 15460c16b537SWarner Losh size_t iSize; 15470c16b537SWarner Losh size_t oSize; 15480c16b537SWarner Losh U32 n; 15490c16b537SWarner Losh 15500c16b537SWarner Losh if (!srcSize) return ERROR(srcSize_wrong); 15510c16b537SWarner Losh iSize = ip[0]; 15520c16b537SWarner Losh //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */ 15530c16b537SWarner Losh 15540c16b537SWarner Losh if (iSize >= 128) /* special header */ 15550c16b537SWarner Losh { 15560c16b537SWarner Losh if (iSize >= (242)) /* RLE */ 15570c16b537SWarner Losh { 15580c16b537SWarner Losh static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 }; 15590c16b537SWarner Losh oSize = l[iSize-242]; 15600c16b537SWarner Losh memset(huffWeight, 1, hwSize); 15610c16b537SWarner Losh iSize = 0; 15620c16b537SWarner Losh } 15630c16b537SWarner Losh else /* Incompressible */ 15640c16b537SWarner Losh { 15650c16b537SWarner Losh oSize = iSize - 127; 15660c16b537SWarner Losh iSize = ((oSize+1)/2); 15670c16b537SWarner Losh if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 15680c16b537SWarner Losh if (oSize >= hwSize) return ERROR(corruption_detected); 15690c16b537SWarner Losh ip += 1; 15700c16b537SWarner Losh for (n=0; n<oSize; n+=2) 15710c16b537SWarner Losh { 15720c16b537SWarner Losh huffWeight[n] = ip[n/2] >> 4; 15730c16b537SWarner Losh huffWeight[n+1] = ip[n/2] & 15; 15740c16b537SWarner Losh } 15750c16b537SWarner Losh } 15760c16b537SWarner Losh } 15770c16b537SWarner Losh else /* header compressed with FSE (normal case) */ 15780c16b537SWarner Losh { 15790c16b537SWarner Losh if (iSize+1 > srcSize) return ERROR(srcSize_wrong); 15800c16b537SWarner Losh oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */ 15810c16b537SWarner Losh if (FSE_isError(oSize)) return oSize; 15820c16b537SWarner Losh } 15830c16b537SWarner Losh 15840c16b537SWarner Losh /* collect weight stats */ 15850c16b537SWarner Losh memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32)); 15860c16b537SWarner Losh weightTotal = 0; 15870c16b537SWarner Losh for (n=0; n<oSize; n++) 15880c16b537SWarner Losh { 15890c16b537SWarner Losh if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 15900c16b537SWarner Losh rankStats[huffWeight[n]]++; 15910c16b537SWarner Losh weightTotal += (1 << huffWeight[n]) >> 1; 15920c16b537SWarner Losh } 15930c16b537SWarner Losh if (weightTotal == 0) return ERROR(corruption_detected); 15940c16b537SWarner Losh 15950c16b537SWarner Losh /* get last non-null symbol weight (implied, total must be 2^n) */ 15960c16b537SWarner Losh tableLog = BIT_highbit32(weightTotal) + 1; 15970c16b537SWarner Losh if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); 15980c16b537SWarner Losh { 15990c16b537SWarner Losh U32 total = 1 << tableLog; 16000c16b537SWarner Losh U32 rest = total - weightTotal; 16010c16b537SWarner Losh U32 verif = 1 << BIT_highbit32(rest); 16020c16b537SWarner Losh U32 lastWeight = BIT_highbit32(rest) + 1; 16030c16b537SWarner Losh if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */ 16040c16b537SWarner Losh huffWeight[oSize] = (BYTE)lastWeight; 16050c16b537SWarner Losh rankStats[lastWeight]++; 16060c16b537SWarner Losh } 16070c16b537SWarner Losh 16080c16b537SWarner Losh /* check tree construction validity */ 16090c16b537SWarner Losh if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */ 16100c16b537SWarner Losh 16110c16b537SWarner Losh /* results */ 16120c16b537SWarner Losh *nbSymbolsPtr = (U32)(oSize+1); 16130c16b537SWarner Losh *tableLogPtr = tableLog; 16140c16b537SWarner Losh return iSize+1; 16150c16b537SWarner Losh } 16160c16b537SWarner Losh 16170c16b537SWarner Losh 16180c16b537SWarner Losh /**************************/ 16190c16b537SWarner Losh /* single-symbol decoding */ 16200c16b537SWarner Losh /**************************/ 16210c16b537SWarner Losh 16220c16b537SWarner Losh static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize) 16230c16b537SWarner Losh { 16240c16b537SWarner Losh BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1]; 16250c16b537SWarner Losh U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */ 16260c16b537SWarner Losh U32 tableLog = 0; 16270c16b537SWarner Losh const BYTE* ip = (const BYTE*) src; 16280c16b537SWarner Losh size_t iSize = ip[0]; 16290c16b537SWarner Losh U32 nbSymbols = 0; 16300c16b537SWarner Losh U32 n; 16310c16b537SWarner Losh U32 nextRankStart; 16320c16b537SWarner Losh void* ptr = DTable+1; 16330c16b537SWarner Losh HUF_DEltX2* const dt = (HUF_DEltX2*)(ptr); 16340c16b537SWarner Losh 16350c16b537SWarner Losh HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */ 16360c16b537SWarner Losh //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */ 16370c16b537SWarner Losh 16380c16b537SWarner Losh iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize); 16390c16b537SWarner Losh if (HUF_isError(iSize)) return iSize; 16400c16b537SWarner Losh 16410c16b537SWarner Losh /* check result */ 16420c16b537SWarner Losh if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */ 16430c16b537SWarner Losh DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */ 16440c16b537SWarner Losh 16450c16b537SWarner Losh /* Prepare ranks */ 16460c16b537SWarner Losh nextRankStart = 0; 16470c16b537SWarner Losh for (n=1; n<=tableLog; n++) 16480c16b537SWarner Losh { 16490c16b537SWarner Losh U32 current = nextRankStart; 16500c16b537SWarner Losh nextRankStart += (rankVal[n] << (n-1)); 16510c16b537SWarner Losh rankVal[n] = current; 16520c16b537SWarner Losh } 16530c16b537SWarner Losh 16540c16b537SWarner Losh /* fill DTable */ 16550c16b537SWarner Losh for (n=0; n<nbSymbols; n++) 16560c16b537SWarner Losh { 16570c16b537SWarner Losh const U32 w = huffWeight[n]; 16580c16b537SWarner Losh const U32 length = (1 << w) >> 1; 16590c16b537SWarner Losh U32 i; 16600c16b537SWarner Losh HUF_DEltX2 D; 16610c16b537SWarner Losh D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w); 16620c16b537SWarner Losh for (i = rankVal[w]; i < rankVal[w] + length; i++) 16630c16b537SWarner Losh dt[i] = D; 16640c16b537SWarner Losh rankVal[w] += length; 16650c16b537SWarner Losh } 16660c16b537SWarner Losh 16670c16b537SWarner Losh return iSize; 16680c16b537SWarner Losh } 16690c16b537SWarner Losh 16700c16b537SWarner Losh static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog) 16710c16b537SWarner Losh { 16720c16b537SWarner Losh const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */ 16730c16b537SWarner Losh const BYTE c = dt[val].byte; 16740c16b537SWarner Losh BIT_skipBits(Dstream, dt[val].nbBits); 16750c16b537SWarner Losh return c; 16760c16b537SWarner Losh } 16770c16b537SWarner Losh 16780c16b537SWarner Losh #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \ 16790c16b537SWarner Losh *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog) 16800c16b537SWarner Losh 16810c16b537SWarner Losh #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \ 16820c16b537SWarner Losh if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \ 16830c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 16840c16b537SWarner Losh 16850c16b537SWarner Losh #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \ 16860c16b537SWarner Losh if (MEM_64bits()) \ 16870c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) 16880c16b537SWarner Losh 16890c16b537SWarner 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) 16900c16b537SWarner Losh { 16910c16b537SWarner Losh BYTE* const pStart = p; 16920c16b537SWarner Losh 16930c16b537SWarner Losh /* up to 4 symbols at a time */ 16940c16b537SWarner Losh while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4)) 16950c16b537SWarner Losh { 16960c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(p, bitDPtr); 16970c16b537SWarner Losh HUF_DECODE_SYMBOLX2_1(p, bitDPtr); 16980c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(p, bitDPtr); 16990c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(p, bitDPtr); 17000c16b537SWarner Losh } 17010c16b537SWarner Losh 17020c16b537SWarner Losh /* closer to the end */ 17030c16b537SWarner Losh while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd)) 17040c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(p, bitDPtr); 17050c16b537SWarner Losh 17060c16b537SWarner Losh /* no more data to retrieve from bitstream, hence no need to reload */ 17070c16b537SWarner Losh while (p < pEnd) 17080c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(p, bitDPtr); 17090c16b537SWarner Losh 17100c16b537SWarner Losh return pEnd-pStart; 17110c16b537SWarner Losh } 17120c16b537SWarner Losh 17130c16b537SWarner Losh 17140c16b537SWarner Losh static size_t HUF_decompress4X2_usingDTable( 17150c16b537SWarner Losh void* dst, size_t dstSize, 17160c16b537SWarner Losh const void* cSrc, size_t cSrcSize, 17170c16b537SWarner Losh const U16* DTable) 17180c16b537SWarner Losh { 17190c16b537SWarner Losh if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 17200c16b537SWarner Losh 17210c16b537SWarner Losh { 17220c16b537SWarner Losh const BYTE* const istart = (const BYTE*) cSrc; 17230c16b537SWarner Losh BYTE* const ostart = (BYTE*) dst; 17240c16b537SWarner Losh BYTE* const oend = ostart + dstSize; 17250c16b537SWarner Losh 17260c16b537SWarner Losh const void* ptr = DTable; 17270c16b537SWarner Losh const HUF_DEltX2* const dt = ((const HUF_DEltX2*)ptr) +1; 17280c16b537SWarner Losh const U32 dtLog = DTable[0]; 17290c16b537SWarner Losh size_t errorCode; 17300c16b537SWarner Losh 17310c16b537SWarner Losh /* Init */ 17320c16b537SWarner Losh BIT_DStream_t bitD1; 17330c16b537SWarner Losh BIT_DStream_t bitD2; 17340c16b537SWarner Losh BIT_DStream_t bitD3; 17350c16b537SWarner Losh BIT_DStream_t bitD4; 17360c16b537SWarner Losh const size_t length1 = MEM_readLE16(istart); 17370c16b537SWarner Losh const size_t length2 = MEM_readLE16(istart+2); 17380c16b537SWarner Losh const size_t length3 = MEM_readLE16(istart+4); 17390c16b537SWarner Losh size_t length4; 17400c16b537SWarner Losh const BYTE* const istart1 = istart + 6; /* jumpTable */ 17410c16b537SWarner Losh const BYTE* const istart2 = istart1 + length1; 17420c16b537SWarner Losh const BYTE* const istart3 = istart2 + length2; 17430c16b537SWarner Losh const BYTE* const istart4 = istart3 + length3; 17440c16b537SWarner Losh const size_t segmentSize = (dstSize+3) / 4; 17450c16b537SWarner Losh BYTE* const opStart2 = ostart + segmentSize; 17460c16b537SWarner Losh BYTE* const opStart3 = opStart2 + segmentSize; 17470c16b537SWarner Losh BYTE* const opStart4 = opStart3 + segmentSize; 17480c16b537SWarner Losh BYTE* op1 = ostart; 17490c16b537SWarner Losh BYTE* op2 = opStart2; 17500c16b537SWarner Losh BYTE* op3 = opStart3; 17510c16b537SWarner Losh BYTE* op4 = opStart4; 17520c16b537SWarner Losh U32 endSignal; 17530c16b537SWarner Losh 17540c16b537SWarner Losh length4 = cSrcSize - (length1 + length2 + length3 + 6); 17550c16b537SWarner Losh if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 17560c16b537SWarner Losh errorCode = BIT_initDStream(&bitD1, istart1, length1); 17570c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 17580c16b537SWarner Losh errorCode = BIT_initDStream(&bitD2, istart2, length2); 17590c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 17600c16b537SWarner Losh errorCode = BIT_initDStream(&bitD3, istart3, length3); 17610c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 17620c16b537SWarner Losh errorCode = BIT_initDStream(&bitD4, istart4, length4); 17630c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 17640c16b537SWarner Losh 17650c16b537SWarner Losh /* 16-32 symbols per loop (4-8 symbols per stream) */ 17660c16b537SWarner Losh endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 17670c16b537SWarner Losh for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; ) 17680c16b537SWarner Losh { 17690c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op1, &bitD1); 17700c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op2, &bitD2); 17710c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op3, &bitD3); 17720c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op4, &bitD4); 17730c16b537SWarner Losh HUF_DECODE_SYMBOLX2_1(op1, &bitD1); 17740c16b537SWarner Losh HUF_DECODE_SYMBOLX2_1(op2, &bitD2); 17750c16b537SWarner Losh HUF_DECODE_SYMBOLX2_1(op3, &bitD3); 17760c16b537SWarner Losh HUF_DECODE_SYMBOLX2_1(op4, &bitD4); 17770c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op1, &bitD1); 17780c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op2, &bitD2); 17790c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op3, &bitD3); 17800c16b537SWarner Losh HUF_DECODE_SYMBOLX2_2(op4, &bitD4); 17810c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(op1, &bitD1); 17820c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(op2, &bitD2); 17830c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(op3, &bitD3); 17840c16b537SWarner Losh HUF_DECODE_SYMBOLX2_0(op4, &bitD4); 17850c16b537SWarner Losh 17860c16b537SWarner Losh endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 17870c16b537SWarner Losh } 17880c16b537SWarner Losh 17890c16b537SWarner Losh /* check corruption */ 17900c16b537SWarner Losh if (op1 > opStart2) return ERROR(corruption_detected); 17910c16b537SWarner Losh if (op2 > opStart3) return ERROR(corruption_detected); 17920c16b537SWarner Losh if (op3 > opStart4) return ERROR(corruption_detected); 17930c16b537SWarner Losh /* note : op4 supposed already verified within main loop */ 17940c16b537SWarner Losh 17950c16b537SWarner Losh /* finish bitStreams one by one */ 17960c16b537SWarner Losh HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog); 17970c16b537SWarner Losh HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog); 17980c16b537SWarner Losh HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog); 17990c16b537SWarner Losh HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog); 18000c16b537SWarner Losh 18010c16b537SWarner Losh /* check */ 18020c16b537SWarner Losh endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4); 18030c16b537SWarner Losh if (!endSignal) return ERROR(corruption_detected); 18040c16b537SWarner Losh 18050c16b537SWarner Losh /* decoded size */ 18060c16b537SWarner Losh return dstSize; 18070c16b537SWarner Losh } 18080c16b537SWarner Losh } 18090c16b537SWarner Losh 18100c16b537SWarner Losh 18110c16b537SWarner Losh static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 18120c16b537SWarner Losh { 18130c16b537SWarner Losh HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG); 18140c16b537SWarner Losh const BYTE* ip = (const BYTE*) cSrc; 18150c16b537SWarner Losh size_t errorCode; 18160c16b537SWarner Losh 18170c16b537SWarner Losh errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize); 18180c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 18190c16b537SWarner Losh if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); 18200c16b537SWarner Losh ip += errorCode; 18210c16b537SWarner Losh cSrcSize -= errorCode; 18220c16b537SWarner Losh 18230c16b537SWarner Losh return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 18240c16b537SWarner Losh } 18250c16b537SWarner Losh 18260c16b537SWarner Losh 18270c16b537SWarner Losh /***************************/ 18280c16b537SWarner Losh /* double-symbols decoding */ 18290c16b537SWarner Losh /***************************/ 18300c16b537SWarner Losh 18310c16b537SWarner Losh static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed, 18320c16b537SWarner Losh const U32* rankValOrigin, const int minWeight, 18330c16b537SWarner Losh const sortedSymbol_t* sortedSymbols, const U32 sortedListSize, 18340c16b537SWarner Losh U32 nbBitsBaseline, U16 baseSeq) 18350c16b537SWarner Losh { 18360c16b537SWarner Losh HUF_DEltX4 DElt; 18370c16b537SWarner Losh U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; 18380c16b537SWarner Losh U32 s; 18390c16b537SWarner Losh 18400c16b537SWarner Losh /* get pre-calculated rankVal */ 18410c16b537SWarner Losh memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 18420c16b537SWarner Losh 18430c16b537SWarner Losh /* fill skipped values */ 18440c16b537SWarner Losh if (minWeight>1) 18450c16b537SWarner Losh { 18460c16b537SWarner Losh U32 i, skipSize = rankVal[minWeight]; 18470c16b537SWarner Losh MEM_writeLE16(&(DElt.sequence), baseSeq); 18480c16b537SWarner Losh DElt.nbBits = (BYTE)(consumed); 18490c16b537SWarner Losh DElt.length = 1; 18500c16b537SWarner Losh for (i = 0; i < skipSize; i++) 18510c16b537SWarner Losh DTable[i] = DElt; 18520c16b537SWarner Losh } 18530c16b537SWarner Losh 18540c16b537SWarner Losh /* fill DTable */ 18550c16b537SWarner Losh for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */ 18560c16b537SWarner Losh { 18570c16b537SWarner Losh const U32 symbol = sortedSymbols[s].symbol; 18580c16b537SWarner Losh const U32 weight = sortedSymbols[s].weight; 18590c16b537SWarner Losh const U32 nbBits = nbBitsBaseline - weight; 18600c16b537SWarner Losh const U32 length = 1 << (sizeLog-nbBits); 18610c16b537SWarner Losh const U32 start = rankVal[weight]; 18620c16b537SWarner Losh U32 i = start; 18630c16b537SWarner Losh const U32 end = start + length; 18640c16b537SWarner Losh 18650c16b537SWarner Losh MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8))); 18660c16b537SWarner Losh DElt.nbBits = (BYTE)(nbBits + consumed); 18670c16b537SWarner Losh DElt.length = 2; 18680c16b537SWarner Losh do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */ 18690c16b537SWarner Losh 18700c16b537SWarner Losh rankVal[weight] += length; 18710c16b537SWarner Losh } 18720c16b537SWarner Losh } 18730c16b537SWarner Losh 18740c16b537SWarner Losh typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1]; 18750c16b537SWarner Losh 18760c16b537SWarner Losh static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog, 18770c16b537SWarner Losh const sortedSymbol_t* sortedList, const U32 sortedListSize, 18780c16b537SWarner Losh const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight, 18790c16b537SWarner Losh const U32 nbBitsBaseline) 18800c16b537SWarner Losh { 18810c16b537SWarner Losh U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; 18820c16b537SWarner Losh const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */ 18830c16b537SWarner Losh const U32 minBits = nbBitsBaseline - maxWeight; 18840c16b537SWarner Losh U32 s; 18850c16b537SWarner Losh 18860c16b537SWarner Losh memcpy(rankVal, rankValOrigin, sizeof(rankVal)); 18870c16b537SWarner Losh 18880c16b537SWarner Losh /* fill DTable */ 18890c16b537SWarner Losh for (s=0; s<sortedListSize; s++) 18900c16b537SWarner Losh { 18910c16b537SWarner Losh const U16 symbol = sortedList[s].symbol; 18920c16b537SWarner Losh const U32 weight = sortedList[s].weight; 18930c16b537SWarner Losh const U32 nbBits = nbBitsBaseline - weight; 18940c16b537SWarner Losh const U32 start = rankVal[weight]; 18950c16b537SWarner Losh const U32 length = 1 << (targetLog-nbBits); 18960c16b537SWarner Losh 18970c16b537SWarner Losh if (targetLog-nbBits >= minBits) /* enough room for a second symbol */ 18980c16b537SWarner Losh { 18990c16b537SWarner Losh U32 sortedRank; 19000c16b537SWarner Losh int minWeight = nbBits + scaleLog; 19010c16b537SWarner Losh if (minWeight < 1) minWeight = 1; 19020c16b537SWarner Losh sortedRank = rankStart[minWeight]; 19030c16b537SWarner Losh HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits, 19040c16b537SWarner Losh rankValOrigin[nbBits], minWeight, 19050c16b537SWarner Losh sortedList+sortedRank, sortedListSize-sortedRank, 19060c16b537SWarner Losh nbBitsBaseline, symbol); 19070c16b537SWarner Losh } 19080c16b537SWarner Losh else 19090c16b537SWarner Losh { 19100c16b537SWarner Losh U32 i; 19110c16b537SWarner Losh const U32 end = start + length; 19120c16b537SWarner Losh HUF_DEltX4 DElt; 19130c16b537SWarner Losh 19140c16b537SWarner Losh MEM_writeLE16(&(DElt.sequence), symbol); 19150c16b537SWarner Losh DElt.nbBits = (BYTE)(nbBits); 19160c16b537SWarner Losh DElt.length = 1; 19170c16b537SWarner Losh for (i = start; i < end; i++) 19180c16b537SWarner Losh DTable[i] = DElt; 19190c16b537SWarner Losh } 19200c16b537SWarner Losh rankVal[weight] += length; 19210c16b537SWarner Losh } 19220c16b537SWarner Losh } 19230c16b537SWarner Losh 19240c16b537SWarner Losh static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize) 19250c16b537SWarner Losh { 19260c16b537SWarner Losh BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1]; 19270c16b537SWarner Losh sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1]; 19280c16b537SWarner Losh U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 }; 19290c16b537SWarner Losh U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 }; 19300c16b537SWarner Losh U32* const rankStart = rankStart0+1; 19310c16b537SWarner Losh rankVal_t rankVal; 19320c16b537SWarner Losh U32 tableLog, maxW, sizeOfSort, nbSymbols; 19330c16b537SWarner Losh const U32 memLog = DTable[0]; 19340c16b537SWarner Losh const BYTE* ip = (const BYTE*) src; 19350c16b537SWarner Losh size_t iSize = ip[0]; 19360c16b537SWarner Losh void* ptr = DTable; 19370c16b537SWarner Losh HUF_DEltX4* const dt = ((HUF_DEltX4*)ptr) + 1; 19380c16b537SWarner Losh 19390c16b537SWarner Losh HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */ 19400c16b537SWarner Losh if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge); 19410c16b537SWarner Losh //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */ 19420c16b537SWarner Losh 19430c16b537SWarner Losh iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize); 19440c16b537SWarner Losh if (HUF_isError(iSize)) return iSize; 19450c16b537SWarner Losh 19460c16b537SWarner Losh /* check result */ 19470c16b537SWarner Losh if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */ 19480c16b537SWarner Losh 19490c16b537SWarner Losh /* find maxWeight */ 19500c16b537SWarner Losh for (maxW = tableLog; rankStats[maxW]==0; maxW--) 19510c16b537SWarner Losh { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */ 19520c16b537SWarner Losh 19530c16b537SWarner Losh /* Get start index of each weight */ 19540c16b537SWarner Losh { 19550c16b537SWarner Losh U32 w, nextRankStart = 0; 19560c16b537SWarner Losh for (w=1; w<=maxW; w++) 19570c16b537SWarner Losh { 19580c16b537SWarner Losh U32 current = nextRankStart; 19590c16b537SWarner Losh nextRankStart += rankStats[w]; 19600c16b537SWarner Losh rankStart[w] = current; 19610c16b537SWarner Losh } 19620c16b537SWarner Losh rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/ 19630c16b537SWarner Losh sizeOfSort = nextRankStart; 19640c16b537SWarner Losh } 19650c16b537SWarner Losh 19660c16b537SWarner Losh /* sort symbols by weight */ 19670c16b537SWarner Losh { 19680c16b537SWarner Losh U32 s; 19690c16b537SWarner Losh for (s=0; s<nbSymbols; s++) 19700c16b537SWarner Losh { 19710c16b537SWarner Losh U32 w = weightList[s]; 19720c16b537SWarner Losh U32 r = rankStart[w]++; 19730c16b537SWarner Losh sortedSymbol[r].symbol = (BYTE)s; 19740c16b537SWarner Losh sortedSymbol[r].weight = (BYTE)w; 19750c16b537SWarner Losh } 19760c16b537SWarner Losh rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */ 19770c16b537SWarner Losh } 19780c16b537SWarner Losh 19790c16b537SWarner Losh /* Build rankVal */ 19800c16b537SWarner Losh { 19810c16b537SWarner Losh const U32 minBits = tableLog+1 - maxW; 19820c16b537SWarner Losh U32 nextRankVal = 0; 19830c16b537SWarner Losh U32 w, consumed; 19840c16b537SWarner Losh const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */ 19850c16b537SWarner Losh U32* rankVal0 = rankVal[0]; 19860c16b537SWarner Losh for (w=1; w<=maxW; w++) 19870c16b537SWarner Losh { 19880c16b537SWarner Losh U32 current = nextRankVal; 19890c16b537SWarner Losh nextRankVal += rankStats[w] << (w+rescale); 19900c16b537SWarner Losh rankVal0[w] = current; 19910c16b537SWarner Losh } 19920c16b537SWarner Losh for (consumed = minBits; consumed <= memLog - minBits; consumed++) 19930c16b537SWarner Losh { 19940c16b537SWarner Losh U32* rankValPtr = rankVal[consumed]; 19950c16b537SWarner Losh for (w = 1; w <= maxW; w++) 19960c16b537SWarner Losh { 19970c16b537SWarner Losh rankValPtr[w] = rankVal0[w] >> consumed; 19980c16b537SWarner Losh } 19990c16b537SWarner Losh } 20000c16b537SWarner Losh } 20010c16b537SWarner Losh 20020c16b537SWarner Losh HUF_fillDTableX4(dt, memLog, 20030c16b537SWarner Losh sortedSymbol, sizeOfSort, 20040c16b537SWarner Losh rankStart0, rankVal, maxW, 20050c16b537SWarner Losh tableLog+1); 20060c16b537SWarner Losh 20070c16b537SWarner Losh return iSize; 20080c16b537SWarner Losh } 20090c16b537SWarner Losh 20100c16b537SWarner Losh 20110c16b537SWarner Losh static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog) 20120c16b537SWarner Losh { 20130c16b537SWarner Losh const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 20140c16b537SWarner Losh memcpy(op, dt+val, 2); 20150c16b537SWarner Losh BIT_skipBits(DStream, dt[val].nbBits); 20160c16b537SWarner Losh return dt[val].length; 20170c16b537SWarner Losh } 20180c16b537SWarner Losh 20190c16b537SWarner Losh static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog) 20200c16b537SWarner Losh { 20210c16b537SWarner Losh const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ 20220c16b537SWarner Losh memcpy(op, dt+val, 1); 20230c16b537SWarner Losh if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits); 20240c16b537SWarner Losh else 20250c16b537SWarner Losh { 20260c16b537SWarner Losh if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) 20270c16b537SWarner Losh { 20280c16b537SWarner Losh BIT_skipBits(DStream, dt[val].nbBits); 20290c16b537SWarner Losh if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8)) 20300c16b537SWarner 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 */ 20310c16b537SWarner Losh } 20320c16b537SWarner Losh } 20330c16b537SWarner Losh return 1; 20340c16b537SWarner Losh } 20350c16b537SWarner Losh 20360c16b537SWarner Losh 20370c16b537SWarner Losh #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \ 20380c16b537SWarner Losh ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 20390c16b537SWarner Losh 20400c16b537SWarner Losh #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \ 20410c16b537SWarner Losh if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \ 20420c16b537SWarner Losh ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 20430c16b537SWarner Losh 20440c16b537SWarner Losh #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \ 20450c16b537SWarner Losh if (MEM_64bits()) \ 20460c16b537SWarner Losh ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) 20470c16b537SWarner Losh 20480c16b537SWarner Losh static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog) 20490c16b537SWarner Losh { 20500c16b537SWarner Losh BYTE* const pStart = p; 20510c16b537SWarner Losh 20520c16b537SWarner Losh /* up to 8 symbols at a time */ 20530c16b537SWarner Losh while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7)) 20540c16b537SWarner Losh { 20550c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(p, bitDPtr); 20560c16b537SWarner Losh HUF_DECODE_SYMBOLX4_1(p, bitDPtr); 20570c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(p, bitDPtr); 20580c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(p, bitDPtr); 20590c16b537SWarner Losh } 20600c16b537SWarner Losh 20610c16b537SWarner Losh /* closer to the end */ 20620c16b537SWarner Losh while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2)) 20630c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(p, bitDPtr); 20640c16b537SWarner Losh 20650c16b537SWarner Losh while (p <= pEnd-2) 20660c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */ 20670c16b537SWarner Losh 20680c16b537SWarner Losh if (p < pEnd) 20690c16b537SWarner Losh p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog); 20700c16b537SWarner Losh 20710c16b537SWarner Losh return p-pStart; 20720c16b537SWarner Losh } 20730c16b537SWarner Losh 20740c16b537SWarner Losh 20750c16b537SWarner Losh 20760c16b537SWarner Losh static size_t HUF_decompress4X4_usingDTable( 20770c16b537SWarner Losh void* dst, size_t dstSize, 20780c16b537SWarner Losh const void* cSrc, size_t cSrcSize, 20790c16b537SWarner Losh const U32* DTable) 20800c16b537SWarner Losh { 20810c16b537SWarner Losh if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ 20820c16b537SWarner Losh 20830c16b537SWarner Losh { 20840c16b537SWarner Losh const BYTE* const istart = (const BYTE*) cSrc; 20850c16b537SWarner Losh BYTE* const ostart = (BYTE*) dst; 20860c16b537SWarner Losh BYTE* const oend = ostart + dstSize; 20870c16b537SWarner Losh 20880c16b537SWarner Losh const void* ptr = DTable; 20890c16b537SWarner Losh const HUF_DEltX4* const dt = ((const HUF_DEltX4*)ptr) +1; 20900c16b537SWarner Losh const U32 dtLog = DTable[0]; 20910c16b537SWarner Losh size_t errorCode; 20920c16b537SWarner Losh 20930c16b537SWarner Losh /* Init */ 20940c16b537SWarner Losh BIT_DStream_t bitD1; 20950c16b537SWarner Losh BIT_DStream_t bitD2; 20960c16b537SWarner Losh BIT_DStream_t bitD3; 20970c16b537SWarner Losh BIT_DStream_t bitD4; 20980c16b537SWarner Losh const size_t length1 = MEM_readLE16(istart); 20990c16b537SWarner Losh const size_t length2 = MEM_readLE16(istart+2); 21000c16b537SWarner Losh const size_t length3 = MEM_readLE16(istart+4); 21010c16b537SWarner Losh size_t length4; 21020c16b537SWarner Losh const BYTE* const istart1 = istart + 6; /* jumpTable */ 21030c16b537SWarner Losh const BYTE* const istart2 = istart1 + length1; 21040c16b537SWarner Losh const BYTE* const istart3 = istart2 + length2; 21050c16b537SWarner Losh const BYTE* const istart4 = istart3 + length3; 21060c16b537SWarner Losh const size_t segmentSize = (dstSize+3) / 4; 21070c16b537SWarner Losh BYTE* const opStart2 = ostart + segmentSize; 21080c16b537SWarner Losh BYTE* const opStart3 = opStart2 + segmentSize; 21090c16b537SWarner Losh BYTE* const opStart4 = opStart3 + segmentSize; 21100c16b537SWarner Losh BYTE* op1 = ostart; 21110c16b537SWarner Losh BYTE* op2 = opStart2; 21120c16b537SWarner Losh BYTE* op3 = opStart3; 21130c16b537SWarner Losh BYTE* op4 = opStart4; 21140c16b537SWarner Losh U32 endSignal; 21150c16b537SWarner Losh 21160c16b537SWarner Losh length4 = cSrcSize - (length1 + length2 + length3 + 6); 21170c16b537SWarner Losh if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ 21180c16b537SWarner Losh errorCode = BIT_initDStream(&bitD1, istart1, length1); 21190c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 21200c16b537SWarner Losh errorCode = BIT_initDStream(&bitD2, istart2, length2); 21210c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 21220c16b537SWarner Losh errorCode = BIT_initDStream(&bitD3, istart3, length3); 21230c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 21240c16b537SWarner Losh errorCode = BIT_initDStream(&bitD4, istart4, length4); 21250c16b537SWarner Losh if (HUF_isError(errorCode)) return errorCode; 21260c16b537SWarner Losh 21270c16b537SWarner Losh /* 16-32 symbols per loop (4-8 symbols per stream) */ 21280c16b537SWarner Losh endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 21290c16b537SWarner Losh for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; ) 21300c16b537SWarner Losh { 21310c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op1, &bitD1); 21320c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op2, &bitD2); 21330c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op3, &bitD3); 21340c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op4, &bitD4); 21350c16b537SWarner Losh HUF_DECODE_SYMBOLX4_1(op1, &bitD1); 21360c16b537SWarner Losh HUF_DECODE_SYMBOLX4_1(op2, &bitD2); 21370c16b537SWarner Losh HUF_DECODE_SYMBOLX4_1(op3, &bitD3); 21380c16b537SWarner Losh HUF_DECODE_SYMBOLX4_1(op4, &bitD4); 21390c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op1, &bitD1); 21400c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op2, &bitD2); 21410c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op3, &bitD3); 21420c16b537SWarner Losh HUF_DECODE_SYMBOLX4_2(op4, &bitD4); 21430c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(op1, &bitD1); 21440c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(op2, &bitD2); 21450c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(op3, &bitD3); 21460c16b537SWarner Losh HUF_DECODE_SYMBOLX4_0(op4, &bitD4); 21470c16b537SWarner Losh 21480c16b537SWarner Losh endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4); 21490c16b537SWarner Losh } 21500c16b537SWarner Losh 21510c16b537SWarner Losh /* check corruption */ 21520c16b537SWarner Losh if (op1 > opStart2) return ERROR(corruption_detected); 21530c16b537SWarner Losh if (op2 > opStart3) return ERROR(corruption_detected); 21540c16b537SWarner Losh if (op3 > opStart4) return ERROR(corruption_detected); 21550c16b537SWarner Losh /* note : op4 supposed already verified within main loop */ 21560c16b537SWarner Losh 21570c16b537SWarner Losh /* finish bitStreams one by one */ 21580c16b537SWarner Losh HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog); 21590c16b537SWarner Losh HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog); 21600c16b537SWarner Losh HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog); 21610c16b537SWarner Losh HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog); 21620c16b537SWarner Losh 21630c16b537SWarner Losh /* check */ 21640c16b537SWarner Losh endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4); 21650c16b537SWarner Losh if (!endSignal) return ERROR(corruption_detected); 21660c16b537SWarner Losh 21670c16b537SWarner Losh /* decoded size */ 21680c16b537SWarner Losh return dstSize; 21690c16b537SWarner Losh } 21700c16b537SWarner Losh } 21710c16b537SWarner Losh 21720c16b537SWarner Losh 21730c16b537SWarner Losh static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 21740c16b537SWarner Losh { 21750c16b537SWarner Losh HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG); 21760c16b537SWarner Losh const BYTE* ip = (const BYTE*) cSrc; 21770c16b537SWarner Losh 21780c16b537SWarner Losh size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize); 21790c16b537SWarner Losh if (HUF_isError(hSize)) return hSize; 21800c16b537SWarner Losh if (hSize >= cSrcSize) return ERROR(srcSize_wrong); 21810c16b537SWarner Losh ip += hSize; 21820c16b537SWarner Losh cSrcSize -= hSize; 21830c16b537SWarner Losh 21840c16b537SWarner Losh return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable); 21850c16b537SWarner Losh } 21860c16b537SWarner Losh 21870c16b537SWarner Losh 21880c16b537SWarner Losh /**********************************/ 21890c16b537SWarner Losh /* Generic decompression selector */ 21900c16b537SWarner Losh /**********************************/ 21910c16b537SWarner Losh 21920c16b537SWarner Losh typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t; 21930c16b537SWarner Losh static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] = 21940c16b537SWarner Losh { 21950c16b537SWarner Losh /* single, double, quad */ 21960c16b537SWarner Losh {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */ 21970c16b537SWarner Losh {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */ 21980c16b537SWarner Losh {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */ 21990c16b537SWarner Losh {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */ 22000c16b537SWarner Losh {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */ 22010c16b537SWarner Losh {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */ 22020c16b537SWarner Losh {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */ 22030c16b537SWarner Losh {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */ 22040c16b537SWarner Losh {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */ 22050c16b537SWarner Losh {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */ 22060c16b537SWarner Losh {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */ 22070c16b537SWarner Losh {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */ 22080c16b537SWarner Losh {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */ 22090c16b537SWarner Losh {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */ 22100c16b537SWarner Losh {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */ 22110c16b537SWarner Losh {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */ 22120c16b537SWarner Losh }; 22130c16b537SWarner Losh 22140c16b537SWarner Losh typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); 22150c16b537SWarner Losh 22160c16b537SWarner Losh static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) 22170c16b537SWarner Losh { 22180c16b537SWarner Losh static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL }; 22190c16b537SWarner Losh /* estimate decompression time */ 22200c16b537SWarner Losh U32 Q; 22210c16b537SWarner Losh const U32 D256 = (U32)(dstSize >> 8); 22220c16b537SWarner Losh U32 Dtime[3]; 22230c16b537SWarner Losh U32 algoNb = 0; 22240c16b537SWarner Losh int n; 22250c16b537SWarner Losh 22260c16b537SWarner Losh /* validation checks */ 22270c16b537SWarner Losh if (dstSize == 0) return ERROR(dstSize_tooSmall); 22280c16b537SWarner Losh if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */ 22290c16b537SWarner Losh if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */ 22300c16b537SWarner Losh if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */ 22310c16b537SWarner Losh 22320c16b537SWarner Losh /* decoder timing evaluation */ 22330c16b537SWarner Losh Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */ 22340c16b537SWarner Losh for (n=0; n<3; n++) 22350c16b537SWarner Losh Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256); 22360c16b537SWarner Losh 22370c16b537SWarner Losh Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */ 22380c16b537SWarner Losh 22390c16b537SWarner Losh if (Dtime[1] < Dtime[0]) algoNb = 1; 22400c16b537SWarner Losh 22410c16b537SWarner Losh return decompress[algoNb](dst, dstSize, cSrc, cSrcSize); 22420c16b537SWarner Losh 22430c16b537SWarner Losh //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */ 22440c16b537SWarner Losh //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */ 22450c16b537SWarner Losh //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */ 22460c16b537SWarner Losh } 22470c16b537SWarner Losh /* 22480c16b537SWarner Losh zstd - standard compression library 22490c16b537SWarner Losh Copyright (C) 2014-2015, Yann Collet. 22500c16b537SWarner Losh 22510c16b537SWarner Losh BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 22520c16b537SWarner Losh 22530c16b537SWarner Losh Redistribution and use in source and binary forms, with or without 22540c16b537SWarner Losh modification, are permitted provided that the following conditions are 22550c16b537SWarner Losh met: 22560c16b537SWarner Losh * Redistributions of source code must retain the above copyright 22570c16b537SWarner Losh notice, this list of conditions and the following disclaimer. 22580c16b537SWarner Losh * Redistributions in binary form must reproduce the above 22590c16b537SWarner Losh copyright notice, this list of conditions and the following disclaimer 22600c16b537SWarner Losh in the documentation and/or other materials provided with the 22610c16b537SWarner Losh distribution. 22620c16b537SWarner Losh THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22630c16b537SWarner Losh "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 22640c16b537SWarner Losh LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22650c16b537SWarner Losh A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22660c16b537SWarner Losh OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 22670c16b537SWarner Losh SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22680c16b537SWarner Losh LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22690c16b537SWarner Losh DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22700c16b537SWarner Losh THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22710c16b537SWarner Losh (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 22720c16b537SWarner Losh OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 22730c16b537SWarner Losh 22740c16b537SWarner Losh You can contact the author at : 22750c16b537SWarner Losh - zstd source repository : https://github.com/Cyan4973/zstd 22760c16b537SWarner Losh - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c 22770c16b537SWarner Losh */ 22780c16b537SWarner Losh 22790c16b537SWarner Losh /* *************************************************************** 22800c16b537SWarner Losh * Tuning parameters 22810c16b537SWarner Losh *****************************************************************/ 22820c16b537SWarner Losh /*! 22830c16b537SWarner Losh * MEMORY_USAGE : 22840c16b537SWarner Losh * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) 22850c16b537SWarner Losh * Increasing memory usage improves compression ratio 22860c16b537SWarner Losh * Reduced memory usage can improve speed, due to cache effect 22870c16b537SWarner Losh */ 22880c16b537SWarner Losh #define ZSTD_MEMORY_USAGE 17 22890c16b537SWarner Losh 22900c16b537SWarner Losh /*! 22910c16b537SWarner Losh * HEAPMODE : 22920c16b537SWarner Losh * Select how default compression functions will allocate memory for their hash table, 22930c16b537SWarner Losh * in memory stack (0, fastest), or in memory heap (1, requires malloc()) 22940c16b537SWarner Losh * Note that compression context is fairly large, as a consequence heap memory is recommended. 22950c16b537SWarner Losh */ 22960c16b537SWarner Losh #ifndef ZSTD_HEAPMODE 22970c16b537SWarner Losh # define ZSTD_HEAPMODE 1 22980c16b537SWarner Losh #endif /* ZSTD_HEAPMODE */ 22990c16b537SWarner Losh 23000c16b537SWarner Losh /*! 23010c16b537SWarner Losh * LEGACY_SUPPORT : 23020c16b537SWarner Losh * decompressor can decode older formats (starting from Zstd 0.1+) 23030c16b537SWarner Losh */ 23040c16b537SWarner Losh #ifndef ZSTD_LEGACY_SUPPORT 23050c16b537SWarner Losh # define ZSTD_LEGACY_SUPPORT 1 23060c16b537SWarner Losh #endif 23070c16b537SWarner Losh 23080c16b537SWarner Losh 23090c16b537SWarner Losh /* ******************************************************* 23100c16b537SWarner Losh * Includes 23110c16b537SWarner Losh *********************************************************/ 23120c16b537SWarner Losh #include <stdlib.h> /* calloc */ 23130c16b537SWarner Losh #include <string.h> /* memcpy, memmove */ 23140c16b537SWarner Losh #include <stdio.h> /* debug : printf */ 23150c16b537SWarner Losh 23160c16b537SWarner Losh 23170c16b537SWarner Losh /* ******************************************************* 23180c16b537SWarner Losh * Compiler specifics 23190c16b537SWarner Losh *********************************************************/ 23200c16b537SWarner Losh #ifdef __AVX2__ 23210c16b537SWarner Losh # include <immintrin.h> /* AVX2 intrinsics */ 23220c16b537SWarner Losh #endif 23230c16b537SWarner Losh 23240c16b537SWarner Losh #ifdef _MSC_VER /* Visual Studio */ 23250c16b537SWarner Losh # include <intrin.h> /* For Visual 2005 */ 23260c16b537SWarner Losh # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 23270c16b537SWarner Losh # pragma warning(disable : 4324) /* disable: C4324: padded structure */ 23280c16b537SWarner Losh #else 23290c16b537SWarner Losh # define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) 23300c16b537SWarner Losh #endif 23310c16b537SWarner Losh 23320c16b537SWarner Losh 23330c16b537SWarner Losh /* ******************************************************* 23340c16b537SWarner Losh * Constants 23350c16b537SWarner Losh *********************************************************/ 23360c16b537SWarner Losh #define HASH_LOG (ZSTD_MEMORY_USAGE - 2) 23370c16b537SWarner Losh #define HASH_TABLESIZE (1 << HASH_LOG) 23380c16b537SWarner Losh #define HASH_MASK (HASH_TABLESIZE - 1) 23390c16b537SWarner Losh 23400c16b537SWarner Losh #define KNUTH 2654435761 23410c16b537SWarner Losh 23420c16b537SWarner Losh #define BIT7 128 23430c16b537SWarner Losh #define BIT6 64 23440c16b537SWarner Losh #define BIT5 32 23450c16b537SWarner Losh #define BIT4 16 23460c16b537SWarner Losh #define BIT1 2 23470c16b537SWarner Losh #define BIT0 1 23480c16b537SWarner Losh 23490c16b537SWarner Losh #define KB *(1 <<10) 23500c16b537SWarner Losh #define MB *(1 <<20) 23510c16b537SWarner Losh #define GB *(1U<<30) 23520c16b537SWarner Losh 23530c16b537SWarner Losh #define BLOCKSIZE (128 KB) /* define, for static allocation */ 23540c16b537SWarner Losh #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/) 23550c16b537SWarner Losh #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE) 23560c16b537SWarner Losh #define IS_RAW BIT0 23570c16b537SWarner Losh #define IS_RLE BIT1 23580c16b537SWarner Losh 23590c16b537SWarner Losh #define WORKPLACESIZE (BLOCKSIZE*3) 23600c16b537SWarner Losh #define MINMATCH 4 23610c16b537SWarner Losh #define MLbits 7 23620c16b537SWarner Losh #define LLbits 6 23630c16b537SWarner Losh #define Offbits 5 23640c16b537SWarner Losh #define MaxML ((1<<MLbits )-1) 23650c16b537SWarner Losh #define MaxLL ((1<<LLbits )-1) 23660c16b537SWarner Losh #define MaxOff 31 23670c16b537SWarner Losh #define LitFSELog 11 23680c16b537SWarner Losh #define MLFSELog 10 23690c16b537SWarner Losh #define LLFSELog 10 23700c16b537SWarner Losh #define OffFSELog 9 23710c16b537SWarner Losh #define MAX(a,b) ((a)<(b)?(b):(a)) 23720c16b537SWarner Losh #define MaxSeq MAX(MaxLL, MaxML) 23730c16b537SWarner Losh 23740c16b537SWarner Losh #define LITERAL_NOENTROPY 63 23750c16b537SWarner Losh #define COMMAND_NOENTROPY 7 /* to remove */ 23760c16b537SWarner Losh 23772b9c00cbSConrad Meyer #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2) 23782b9c00cbSConrad Meyer 23790c16b537SWarner Losh static const size_t ZSTD_blockHeaderSize = 3; 23800c16b537SWarner Losh static const size_t ZSTD_frameHeaderSize = 4; 23810c16b537SWarner Losh 23820c16b537SWarner Losh 23830c16b537SWarner Losh /* ******************************************************* 23840c16b537SWarner Losh * Memory operations 23850c16b537SWarner Losh **********************************************************/ 23860c16b537SWarner Losh static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); } 23870c16b537SWarner Losh 23880c16b537SWarner Losh static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); } 23890c16b537SWarner Losh 23900c16b537SWarner Losh #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; } 23910c16b537SWarner Losh 23920c16b537SWarner Losh /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */ 23930c16b537SWarner Losh static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length) 23940c16b537SWarner Losh { 23950c16b537SWarner Losh const BYTE* ip = (const BYTE*)src; 23960c16b537SWarner Losh BYTE* op = (BYTE*)dst; 23970c16b537SWarner Losh BYTE* const oend = op + length; 23980c16b537SWarner Losh do COPY8(op, ip) while (op < oend); 23990c16b537SWarner Losh } 24000c16b537SWarner Losh 24010c16b537SWarner Losh 24020c16b537SWarner Losh /* ************************************** 24030c16b537SWarner Losh * Local structures 24040c16b537SWarner Losh ****************************************/ 24050c16b537SWarner Losh typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t; 24060c16b537SWarner Losh 24070c16b537SWarner Losh typedef struct 24080c16b537SWarner Losh { 24090c16b537SWarner Losh blockType_t blockType; 24100c16b537SWarner Losh U32 origSize; 24110c16b537SWarner Losh } blockProperties_t; 24120c16b537SWarner Losh 24130c16b537SWarner Losh typedef struct { 24140c16b537SWarner Losh void* buffer; 24150c16b537SWarner Losh U32* offsetStart; 24160c16b537SWarner Losh U32* offset; 24170c16b537SWarner Losh BYTE* offCodeStart; 24180c16b537SWarner Losh BYTE* offCode; 24190c16b537SWarner Losh BYTE* litStart; 24200c16b537SWarner Losh BYTE* lit; 24210c16b537SWarner Losh BYTE* litLengthStart; 24220c16b537SWarner Losh BYTE* litLength; 24230c16b537SWarner Losh BYTE* matchLengthStart; 24240c16b537SWarner Losh BYTE* matchLength; 24250c16b537SWarner Losh BYTE* dumpsStart; 24260c16b537SWarner Losh BYTE* dumps; 24270c16b537SWarner Losh } seqStore_t; 24280c16b537SWarner Losh 24290c16b537SWarner Losh 24300c16b537SWarner Losh /* ************************************* 24310c16b537SWarner Losh * Error Management 24320c16b537SWarner Losh ***************************************/ 24330c16b537SWarner Losh /*! ZSTD_isError 24340c16b537SWarner Losh * tells if a return value is an error code */ 24350c16b537SWarner Losh static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); } 24360c16b537SWarner Losh 24370c16b537SWarner Losh 24380c16b537SWarner Losh 24390c16b537SWarner Losh /* ************************************************************* 24400c16b537SWarner Losh * Decompression section 24410c16b537SWarner Losh ***************************************************************/ 24420c16b537SWarner Losh struct ZSTD_DCtx_s 24430c16b537SWarner Losh { 24440c16b537SWarner Losh U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)]; 24450c16b537SWarner Losh U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)]; 24460c16b537SWarner Losh U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)]; 24470c16b537SWarner Losh void* previousDstEnd; 24480c16b537SWarner Losh void* base; 24490c16b537SWarner Losh size_t expected; 24500c16b537SWarner Losh blockType_t bType; 24510c16b537SWarner Losh U32 phase; 24520c16b537SWarner Losh const BYTE* litPtr; 24530c16b537SWarner Losh size_t litSize; 24540c16b537SWarner Losh BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */]; 24550c16b537SWarner Losh }; /* typedef'd to ZSTD_Dctx within "zstd_static.h" */ 24560c16b537SWarner Losh 24570c16b537SWarner Losh 24580c16b537SWarner Losh static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr) 24590c16b537SWarner Losh { 24600c16b537SWarner Losh const BYTE* const in = (const BYTE* const)src; 24610c16b537SWarner Losh BYTE headerFlags; 24620c16b537SWarner Losh U32 cSize; 24630c16b537SWarner Losh 24640c16b537SWarner Losh if (srcSize < 3) return ERROR(srcSize_wrong); 24650c16b537SWarner Losh 24660c16b537SWarner Losh headerFlags = *in; 24670c16b537SWarner Losh cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16); 24680c16b537SWarner Losh 24690c16b537SWarner Losh bpPtr->blockType = (blockType_t)(headerFlags >> 6); 24700c16b537SWarner Losh bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0; 24710c16b537SWarner Losh 24720c16b537SWarner Losh if (bpPtr->blockType == bt_end) return 0; 24730c16b537SWarner Losh if (bpPtr->blockType == bt_rle) return 1; 24740c16b537SWarner Losh return cSize; 24750c16b537SWarner Losh } 24760c16b537SWarner Losh 24770c16b537SWarner Losh static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 24780c16b537SWarner Losh { 24790c16b537SWarner Losh if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall); 248037f1f268SConrad Meyer if (srcSize > 0) { 24810c16b537SWarner Losh memcpy(dst, src, srcSize); 248237f1f268SConrad Meyer } 24830c16b537SWarner Losh return srcSize; 24840c16b537SWarner Losh } 24850c16b537SWarner Losh 24860c16b537SWarner Losh 24870c16b537SWarner Losh /** ZSTD_decompressLiterals 24880c16b537SWarner Losh @return : nb of bytes read from src, or an error code*/ 24890c16b537SWarner Losh static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr, 24900c16b537SWarner Losh const void* src, size_t srcSize) 24910c16b537SWarner Losh { 24920c16b537SWarner Losh const BYTE* ip = (const BYTE*)src; 24930c16b537SWarner Losh 24940c16b537SWarner Losh const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 24950c16b537SWarner Losh const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 24960c16b537SWarner Losh 24970c16b537SWarner Losh if (litSize > *maxDstSizePtr) return ERROR(corruption_detected); 24980c16b537SWarner Losh if (litCSize + 5 > srcSize) return ERROR(corruption_detected); 24990c16b537SWarner Losh 25000c16b537SWarner Losh if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected); 25010c16b537SWarner Losh 25020c16b537SWarner Losh *maxDstSizePtr = litSize; 25030c16b537SWarner Losh return litCSize + 5; 25040c16b537SWarner Losh } 25050c16b537SWarner Losh 25060c16b537SWarner Losh 25070c16b537SWarner Losh /** ZSTD_decodeLiteralsBlock 25080c16b537SWarner Losh @return : nb of bytes read from src (< srcSize )*/ 25090c16b537SWarner Losh static size_t ZSTD_decodeLiteralsBlock(void* ctx, 25100c16b537SWarner Losh const void* src, size_t srcSize) 25110c16b537SWarner Losh { 25120c16b537SWarner Losh ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx; 25130c16b537SWarner Losh const BYTE* const istart = (const BYTE* const)src; 25140c16b537SWarner Losh 25150c16b537SWarner Losh /* any compressed block with literals segment must be at least this size */ 25160c16b537SWarner Losh if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected); 25170c16b537SWarner Losh 25180c16b537SWarner Losh switch(*istart & 3) 25190c16b537SWarner Losh { 25200c16b537SWarner Losh default: 25210c16b537SWarner Losh case 0: 25220c16b537SWarner Losh { 25230c16b537SWarner Losh size_t litSize = BLOCKSIZE; 25240c16b537SWarner Losh const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize); 25250c16b537SWarner Losh dctx->litPtr = dctx->litBuffer; 25260c16b537SWarner Losh dctx->litSize = litSize; 25270c16b537SWarner Losh memset(dctx->litBuffer + dctx->litSize, 0, 8); 25280c16b537SWarner Losh return readSize; /* works if it's an error too */ 25290c16b537SWarner Losh } 25300c16b537SWarner Losh case IS_RAW: 25310c16b537SWarner Losh { 25320c16b537SWarner Losh const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 25330c16b537SWarner Losh if (litSize > srcSize-11) /* risk of reading too far with wildcopy */ 25340c16b537SWarner Losh { 25359cbefe25SConrad Meyer if (litSize > BLOCKSIZE) return ERROR(corruption_detected); 25360c16b537SWarner Losh if (litSize > srcSize-3) return ERROR(corruption_detected); 25370c16b537SWarner Losh memcpy(dctx->litBuffer, istart, litSize); 25380c16b537SWarner Losh dctx->litPtr = dctx->litBuffer; 25390c16b537SWarner Losh dctx->litSize = litSize; 25400c16b537SWarner Losh memset(dctx->litBuffer + dctx->litSize, 0, 8); 25410c16b537SWarner Losh return litSize+3; 25420c16b537SWarner Losh } 25430c16b537SWarner Losh /* direct reference into compressed stream */ 25440c16b537SWarner Losh dctx->litPtr = istart+3; 25450c16b537SWarner Losh dctx->litSize = litSize; 25460c16b537SWarner Losh return litSize+3; 25470c16b537SWarner Losh } 25480c16b537SWarner Losh case IS_RLE: 25490c16b537SWarner Losh { 25500c16b537SWarner Losh const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ 25510c16b537SWarner Losh if (litSize > BLOCKSIZE) return ERROR(corruption_detected); 25520c16b537SWarner Losh memset(dctx->litBuffer, istart[3], litSize + 8); 25530c16b537SWarner Losh dctx->litPtr = dctx->litBuffer; 25540c16b537SWarner Losh dctx->litSize = litSize; 25550c16b537SWarner Losh return 4; 25560c16b537SWarner Losh } 25570c16b537SWarner Losh } 25580c16b537SWarner Losh } 25590c16b537SWarner Losh 25600c16b537SWarner Losh 25610c16b537SWarner Losh static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr, 25620c16b537SWarner Losh FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb, 25630c16b537SWarner Losh const void* src, size_t srcSize) 25640c16b537SWarner Losh { 25650c16b537SWarner Losh const BYTE* const istart = (const BYTE* const)src; 25660c16b537SWarner Losh const BYTE* ip = istart; 25670c16b537SWarner Losh const BYTE* const iend = istart + srcSize; 25680c16b537SWarner Losh U32 LLtype, Offtype, MLtype; 25690c16b537SWarner Losh U32 LLlog, Offlog, MLlog; 25700c16b537SWarner Losh size_t dumpsLength; 25710c16b537SWarner Losh 25720c16b537SWarner Losh /* check */ 25730c16b537SWarner Losh if (srcSize < 5) return ERROR(srcSize_wrong); 25740c16b537SWarner Losh 25750c16b537SWarner Losh /* SeqHead */ 25760c16b537SWarner Losh *nbSeq = MEM_readLE16(ip); ip+=2; 25770c16b537SWarner Losh LLtype = *ip >> 6; 25780c16b537SWarner Losh Offtype = (*ip >> 4) & 3; 25790c16b537SWarner Losh MLtype = (*ip >> 2) & 3; 25800c16b537SWarner Losh if (*ip & 2) 25810c16b537SWarner Losh { 25820c16b537SWarner Losh dumpsLength = ip[2]; 25830c16b537SWarner Losh dumpsLength += ip[1] << 8; 25840c16b537SWarner Losh ip += 3; 25850c16b537SWarner Losh } 25860c16b537SWarner Losh else 25870c16b537SWarner Losh { 25880c16b537SWarner Losh dumpsLength = ip[1]; 25890c16b537SWarner Losh dumpsLength += (ip[0] & 1) << 8; 25900c16b537SWarner Losh ip += 2; 25910c16b537SWarner Losh } 25920c16b537SWarner Losh *dumpsPtr = ip; 25930c16b537SWarner Losh ip += dumpsLength; 25940c16b537SWarner Losh *dumpsLengthPtr = dumpsLength; 25950c16b537SWarner Losh 25960c16b537SWarner Losh /* check */ 25970c16b537SWarner Losh if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */ 25980c16b537SWarner Losh 25990c16b537SWarner Losh /* sequences */ 26000c16b537SWarner Losh { 26010c16b537SWarner Losh S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL and MaxOff */ 26020c16b537SWarner Losh size_t headerSize; 26030c16b537SWarner Losh 26040c16b537SWarner Losh /* Build DTables */ 26050c16b537SWarner Losh switch(LLtype) 26060c16b537SWarner Losh { 26070c16b537SWarner Losh case bt_rle : 26080c16b537SWarner Losh LLlog = 0; 26090c16b537SWarner Losh FSE_buildDTable_rle(DTableLL, *ip++); break; 26100c16b537SWarner Losh case bt_raw : 26110c16b537SWarner Losh LLlog = LLbits; 26120c16b537SWarner Losh FSE_buildDTable_raw(DTableLL, LLbits); break; 26130c16b537SWarner Losh default : 26140c16b537SWarner Losh { U32 max = MaxLL; 26150c16b537SWarner Losh headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip); 26160c16b537SWarner Losh if (FSE_isError(headerSize)) return ERROR(GENERIC); 26170c16b537SWarner Losh if (LLlog > LLFSELog) return ERROR(corruption_detected); 26180c16b537SWarner Losh ip += headerSize; 26190c16b537SWarner Losh FSE_buildDTable(DTableLL, norm, max, LLlog); 26200c16b537SWarner Losh } } 26210c16b537SWarner Losh 26220c16b537SWarner Losh switch(Offtype) 26230c16b537SWarner Losh { 26240c16b537SWarner Losh case bt_rle : 26250c16b537SWarner Losh Offlog = 0; 26260c16b537SWarner Losh if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 26270c16b537SWarner Losh FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */ 26280c16b537SWarner Losh break; 26290c16b537SWarner Losh case bt_raw : 26300c16b537SWarner Losh Offlog = Offbits; 26310c16b537SWarner Losh FSE_buildDTable_raw(DTableOffb, Offbits); break; 26320c16b537SWarner Losh default : 26330c16b537SWarner Losh { U32 max = MaxOff; 26340c16b537SWarner Losh headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip); 26350c16b537SWarner Losh if (FSE_isError(headerSize)) return ERROR(GENERIC); 26360c16b537SWarner Losh if (Offlog > OffFSELog) return ERROR(corruption_detected); 26370c16b537SWarner Losh ip += headerSize; 26380c16b537SWarner Losh FSE_buildDTable(DTableOffb, norm, max, Offlog); 26390c16b537SWarner Losh } } 26400c16b537SWarner Losh 26410c16b537SWarner Losh switch(MLtype) 26420c16b537SWarner Losh { 26430c16b537SWarner Losh case bt_rle : 26440c16b537SWarner Losh MLlog = 0; 26450c16b537SWarner Losh if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 26460c16b537SWarner Losh FSE_buildDTable_rle(DTableML, *ip++); break; 26470c16b537SWarner Losh case bt_raw : 26480c16b537SWarner Losh MLlog = MLbits; 26490c16b537SWarner Losh FSE_buildDTable_raw(DTableML, MLbits); break; 26500c16b537SWarner Losh default : 26510c16b537SWarner Losh { U32 max = MaxML; 26520c16b537SWarner Losh headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip); 26530c16b537SWarner Losh if (FSE_isError(headerSize)) return ERROR(GENERIC); 26540c16b537SWarner Losh if (MLlog > MLFSELog) return ERROR(corruption_detected); 26550c16b537SWarner Losh ip += headerSize; 26560c16b537SWarner Losh FSE_buildDTable(DTableML, norm, max, MLlog); 26570c16b537SWarner Losh } } } 26580c16b537SWarner Losh 26590c16b537SWarner Losh return ip-istart; 26600c16b537SWarner Losh } 26610c16b537SWarner Losh 26620c16b537SWarner Losh 26630c16b537SWarner Losh typedef struct { 26640c16b537SWarner Losh size_t litLength; 26650c16b537SWarner Losh size_t offset; 26660c16b537SWarner Losh size_t matchLength; 26670c16b537SWarner Losh } seq_t; 26680c16b537SWarner Losh 26690c16b537SWarner Losh typedef struct { 26700c16b537SWarner Losh BIT_DStream_t DStream; 26710c16b537SWarner Losh FSE_DState_t stateLL; 26720c16b537SWarner Losh FSE_DState_t stateOffb; 26730c16b537SWarner Losh FSE_DState_t stateML; 26740c16b537SWarner Losh size_t prevOffset; 26750c16b537SWarner Losh const BYTE* dumps; 26760c16b537SWarner Losh const BYTE* dumpsEnd; 26770c16b537SWarner Losh } seqState_t; 26780c16b537SWarner Losh 26790c16b537SWarner Losh 26800c16b537SWarner Losh static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState) 26810c16b537SWarner Losh { 26820c16b537SWarner Losh size_t litLength; 26830c16b537SWarner Losh size_t prevOffset; 26840c16b537SWarner Losh size_t offset; 26850c16b537SWarner Losh size_t matchLength; 26860c16b537SWarner Losh const BYTE* dumps = seqState->dumps; 26870c16b537SWarner Losh const BYTE* const de = seqState->dumpsEnd; 26880c16b537SWarner Losh 26890c16b537SWarner Losh /* Literal length */ 26900c16b537SWarner Losh litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream)); 26910c16b537SWarner Losh prevOffset = litLength ? seq->offset : seqState->prevOffset; 26920c16b537SWarner Losh seqState->prevOffset = seq->offset; 26930c16b537SWarner Losh if (litLength == MaxLL) 26940c16b537SWarner Losh { 26954d3f1eafSConrad Meyer const U32 add = dumps<de ? *dumps++ : 0; 26960c16b537SWarner Losh if (add < 255) litLength += add; 26974d3f1eafSConrad Meyer else if (dumps + 3 <= de) 26980c16b537SWarner Losh { 26994d3f1eafSConrad Meyer litLength = MEM_readLE24(dumps); 27000c16b537SWarner Losh dumps += 3; 27010c16b537SWarner Losh } 27020c16b537SWarner Losh if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */ 27030c16b537SWarner Losh } 27040c16b537SWarner Losh 27050c16b537SWarner Losh /* Offset */ 27060c16b537SWarner Losh { 27070c16b537SWarner Losh static const size_t offsetPrefix[MaxOff+1] = { /* note : size_t faster than U32 */ 27080c16b537SWarner Losh 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256, 27090c16b537SWarner Losh 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 27100c16b537SWarner Losh 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 }; 27110c16b537SWarner Losh U32 offsetCode, nbBits; 27120c16b537SWarner Losh offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */ 27130c16b537SWarner Losh if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream)); 27140c16b537SWarner Losh nbBits = offsetCode - 1; 27150c16b537SWarner Losh if (offsetCode==0) nbBits = 0; /* cmove */ 27160c16b537SWarner Losh offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits); 27170c16b537SWarner Losh if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream)); 27180c16b537SWarner Losh if (offsetCode==0) offset = prevOffset; /* cmove */ 27190c16b537SWarner Losh } 27200c16b537SWarner Losh 27210c16b537SWarner Losh /* MatchLength */ 27220c16b537SWarner Losh matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream)); 27230c16b537SWarner Losh if (matchLength == MaxML) 27240c16b537SWarner Losh { 27254d3f1eafSConrad Meyer const U32 add = dumps<de ? *dumps++ : 0; 27260c16b537SWarner Losh if (add < 255) matchLength += add; 27274d3f1eafSConrad Meyer else if (dumps + 3 <= de) 27280c16b537SWarner Losh { 27294d3f1eafSConrad Meyer matchLength = MEM_readLE24(dumps); 27300c16b537SWarner Losh dumps += 3; 27310c16b537SWarner Losh } 27320c16b537SWarner Losh if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */ 27330c16b537SWarner Losh } 27340c16b537SWarner Losh matchLength += MINMATCH; 27350c16b537SWarner Losh 27360c16b537SWarner Losh /* save result */ 27370c16b537SWarner Losh seq->litLength = litLength; 27380c16b537SWarner Losh seq->offset = offset; 27390c16b537SWarner Losh seq->matchLength = matchLength; 27400c16b537SWarner Losh seqState->dumps = dumps; 27410c16b537SWarner Losh } 27420c16b537SWarner Losh 27430c16b537SWarner Losh 27440c16b537SWarner Losh static size_t ZSTD_execSequence(BYTE* op, 27450c16b537SWarner Losh seq_t sequence, 27460c16b537SWarner Losh const BYTE** litPtr, const BYTE* const litLimit, 27470c16b537SWarner Losh BYTE* const base, BYTE* const oend) 27480c16b537SWarner Losh { 27490c16b537SWarner Losh static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */ 27502b9c00cbSConrad Meyer static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11}; /* subtracted */ 27510c16b537SWarner Losh const BYTE* const ostart = op; 27520c16b537SWarner Losh BYTE* const oLitEnd = op + sequence.litLength; 27530c16b537SWarner Losh BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength; /* risk : address space overflow (32-bits) */ 27540c16b537SWarner Losh BYTE* const oend_8 = oend-8; 27550c16b537SWarner Losh const BYTE* const litEnd = *litPtr + sequence.litLength; 27560c16b537SWarner Losh 27570c16b537SWarner Losh /* checks */ 27580c16b537SWarner Losh if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */ 27590c16b537SWarner Losh if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */ 27600c16b537SWarner Losh if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */ 27610c16b537SWarner Losh 27620c16b537SWarner Losh /* copy Literals */ 27630c16b537SWarner Losh ZSTD_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */ 27640c16b537SWarner Losh op = oLitEnd; 27650c16b537SWarner Losh *litPtr = litEnd; /* update for next sequence */ 27660c16b537SWarner Losh 27670c16b537SWarner Losh /* copy Match */ 27680c16b537SWarner Losh { 27690c16b537SWarner Losh const BYTE* match = op - sequence.offset; 27700c16b537SWarner Losh 27710c16b537SWarner Losh /* check */ 27720c16b537SWarner Losh if (sequence.offset > (size_t)op) return ERROR(corruption_detected); /* address space overflow test (this test seems kept by clang optimizer) */ 27730c16b537SWarner Losh //if (match > op) return ERROR(corruption_detected); /* address space overflow test (is clang optimizer removing this test ?) */ 27740c16b537SWarner Losh if (match < base) return ERROR(corruption_detected); 27750c16b537SWarner Losh 27760c16b537SWarner Losh /* close range match, overlap */ 27770c16b537SWarner Losh if (sequence.offset < 8) 27780c16b537SWarner Losh { 27790c16b537SWarner Losh const int dec64 = dec64table[sequence.offset]; 27800c16b537SWarner Losh op[0] = match[0]; 27810c16b537SWarner Losh op[1] = match[1]; 27820c16b537SWarner Losh op[2] = match[2]; 27830c16b537SWarner Losh op[3] = match[3]; 27840c16b537SWarner Losh match += dec32table[sequence.offset]; 27850c16b537SWarner Losh ZSTD_copy4(op+4, match); 27860c16b537SWarner Losh match -= dec64; 27870c16b537SWarner Losh } 27880c16b537SWarner Losh else 27890c16b537SWarner Losh { 27900c16b537SWarner Losh ZSTD_copy8(op, match); 27910c16b537SWarner Losh } 27920c16b537SWarner Losh op += 8; match += 8; 27930c16b537SWarner Losh 27940c16b537SWarner Losh if (oMatchEnd > oend-(16-MINMATCH)) 27950c16b537SWarner Losh { 27960c16b537SWarner Losh if (op < oend_8) 27970c16b537SWarner Losh { 27980c16b537SWarner Losh ZSTD_wildcopy(op, match, oend_8 - op); 27990c16b537SWarner Losh match += oend_8 - op; 28000c16b537SWarner Losh op = oend_8; 28010c16b537SWarner Losh } 28020c16b537SWarner Losh while (op < oMatchEnd) *op++ = *match++; 28030c16b537SWarner Losh } 28040c16b537SWarner Losh else 28050c16b537SWarner Losh { 28060c16b537SWarner Losh ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */ 28070c16b537SWarner Losh } 28080c16b537SWarner Losh } 28090c16b537SWarner Losh 28100c16b537SWarner Losh return oMatchEnd - ostart; 28110c16b537SWarner Losh } 28120c16b537SWarner Losh 28130c16b537SWarner Losh static size_t ZSTD_decompressSequences( 28140c16b537SWarner Losh void* ctx, 28150c16b537SWarner Losh void* dst, size_t maxDstSize, 28160c16b537SWarner Losh const void* seqStart, size_t seqSize) 28170c16b537SWarner Losh { 28180c16b537SWarner Losh ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx; 28190c16b537SWarner Losh const BYTE* ip = (const BYTE*)seqStart; 28200c16b537SWarner Losh const BYTE* const iend = ip + seqSize; 28210c16b537SWarner Losh BYTE* const ostart = (BYTE* const)dst; 28220c16b537SWarner Losh BYTE* op = ostart; 28230c16b537SWarner Losh BYTE* const oend = ostart + maxDstSize; 28240c16b537SWarner Losh size_t errorCode, dumpsLength; 28250c16b537SWarner Losh const BYTE* litPtr = dctx->litPtr; 28260c16b537SWarner Losh const BYTE* const litEnd = litPtr + dctx->litSize; 28270c16b537SWarner Losh int nbSeq; 28280c16b537SWarner Losh const BYTE* dumps; 28290c16b537SWarner Losh U32* DTableLL = dctx->LLTable; 28300c16b537SWarner Losh U32* DTableML = dctx->MLTable; 28310c16b537SWarner Losh U32* DTableOffb = dctx->OffTable; 28320c16b537SWarner Losh BYTE* const base = (BYTE*) (dctx->base); 28330c16b537SWarner Losh 28340c16b537SWarner Losh /* Build Decoding Tables */ 28350c16b537SWarner Losh errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength, 28360c16b537SWarner Losh DTableLL, DTableML, DTableOffb, 28370c16b537SWarner Losh ip, iend-ip); 28380c16b537SWarner Losh if (ZSTD_isError(errorCode)) return errorCode; 28390c16b537SWarner Losh ip += errorCode; 28400c16b537SWarner Losh 28410c16b537SWarner Losh /* Regen sequences */ 28420c16b537SWarner Losh { 28430c16b537SWarner Losh seq_t sequence; 28440c16b537SWarner Losh seqState_t seqState; 28450c16b537SWarner Losh 28460c16b537SWarner Losh memset(&sequence, 0, sizeof(sequence)); 28470c16b537SWarner Losh seqState.dumps = dumps; 28480c16b537SWarner Losh seqState.dumpsEnd = dumps + dumpsLength; 28490c16b537SWarner Losh seqState.prevOffset = sequence.offset = 4; 28500c16b537SWarner Losh errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip); 28510c16b537SWarner Losh if (ERR_isError(errorCode)) return ERROR(corruption_detected); 28520c16b537SWarner Losh FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL); 28530c16b537SWarner Losh FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb); 28540c16b537SWarner Losh FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML); 28550c16b537SWarner Losh 28560c16b537SWarner Losh for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; ) 28570c16b537SWarner Losh { 28580c16b537SWarner Losh size_t oneSeqSize; 28590c16b537SWarner Losh nbSeq--; 28600c16b537SWarner Losh ZSTD_decodeSequence(&sequence, &seqState); 28610c16b537SWarner Losh oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend); 28620c16b537SWarner Losh if (ZSTD_isError(oneSeqSize)) return oneSeqSize; 28630c16b537SWarner Losh op += oneSeqSize; 28640c16b537SWarner Losh } 28650c16b537SWarner Losh 28660c16b537SWarner Losh /* check if reached exact end */ 28670c16b537SWarner Losh if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* requested too much : data is corrupted */ 28680c16b537SWarner Losh if (nbSeq<0) return ERROR(corruption_detected); /* requested too many sequences : data is corrupted */ 28690c16b537SWarner Losh 28700c16b537SWarner Losh /* last literal segment */ 28710c16b537SWarner Losh { 28720c16b537SWarner Losh size_t lastLLSize = litEnd - litPtr; 28730c16b537SWarner Losh if (litPtr > litEnd) return ERROR(corruption_detected); 28740c16b537SWarner Losh if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall); 287537f1f268SConrad Meyer if (lastLLSize > 0) { 28760c16b537SWarner Losh if (op != litPtr) memmove(op, litPtr, lastLLSize); 28770c16b537SWarner Losh op += lastLLSize; 28780c16b537SWarner Losh } 28790c16b537SWarner Losh } 288037f1f268SConrad Meyer } 28810c16b537SWarner Losh 28820c16b537SWarner Losh return op-ostart; 28830c16b537SWarner Losh } 28840c16b537SWarner Losh 28850c16b537SWarner Losh 28860c16b537SWarner Losh static size_t ZSTD_decompressBlock( 28870c16b537SWarner Losh void* ctx, 28880c16b537SWarner Losh void* dst, size_t maxDstSize, 28890c16b537SWarner Losh const void* src, size_t srcSize) 28900c16b537SWarner Losh { 28910c16b537SWarner Losh /* blockType == blockCompressed */ 28920c16b537SWarner Losh const BYTE* ip = (const BYTE*)src; 28930c16b537SWarner Losh 28940c16b537SWarner Losh /* Decode literals sub-block */ 28950c16b537SWarner Losh size_t litCSize = ZSTD_decodeLiteralsBlock(ctx, src, srcSize); 28960c16b537SWarner Losh if (ZSTD_isError(litCSize)) return litCSize; 28970c16b537SWarner Losh ip += litCSize; 28980c16b537SWarner Losh srcSize -= litCSize; 28990c16b537SWarner Losh 29000c16b537SWarner Losh return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize); 29010c16b537SWarner Losh } 29020c16b537SWarner Losh 29030c16b537SWarner Losh 29040c16b537SWarner Losh static size_t ZSTD_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 29050c16b537SWarner Losh { 29060c16b537SWarner Losh const BYTE* ip = (const BYTE*)src; 29070c16b537SWarner Losh const BYTE* iend = ip + srcSize; 29080c16b537SWarner Losh BYTE* const ostart = (BYTE* const)dst; 29090c16b537SWarner Losh BYTE* op = ostart; 29100c16b537SWarner Losh BYTE* const oend = ostart + maxDstSize; 29110c16b537SWarner Losh size_t remainingSize = srcSize; 29120c16b537SWarner Losh U32 magicNumber; 29130c16b537SWarner Losh blockProperties_t blockProperties; 29140c16b537SWarner Losh 29150c16b537SWarner Losh /* Frame Header */ 29160c16b537SWarner Losh if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong); 29170c16b537SWarner Losh magicNumber = MEM_readLE32(src); 29180c16b537SWarner Losh if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown); 29190c16b537SWarner Losh ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize; 29200c16b537SWarner Losh 29210c16b537SWarner Losh /* Loop on each block */ 29220c16b537SWarner Losh while (1) 29230c16b537SWarner Losh { 29240c16b537SWarner Losh size_t decodedSize=0; 29250c16b537SWarner Losh size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties); 29260c16b537SWarner Losh if (ZSTD_isError(cBlockSize)) return cBlockSize; 29270c16b537SWarner Losh 29280c16b537SWarner Losh ip += ZSTD_blockHeaderSize; 29290c16b537SWarner Losh remainingSize -= ZSTD_blockHeaderSize; 29300c16b537SWarner Losh if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); 29310c16b537SWarner Losh 29320c16b537SWarner Losh switch(blockProperties.blockType) 29330c16b537SWarner Losh { 29340c16b537SWarner Losh case bt_compressed: 29350c16b537SWarner Losh decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize); 29360c16b537SWarner Losh break; 29370c16b537SWarner Losh case bt_raw : 29380c16b537SWarner Losh decodedSize = ZSTD_copyUncompressedBlock(op, oend-op, ip, cBlockSize); 29390c16b537SWarner Losh break; 29400c16b537SWarner Losh case bt_rle : 29410c16b537SWarner Losh return ERROR(GENERIC); /* not yet supported */ 29420c16b537SWarner Losh break; 29430c16b537SWarner Losh case bt_end : 29440c16b537SWarner Losh /* end of frame */ 29450c16b537SWarner Losh if (remainingSize) return ERROR(srcSize_wrong); 29460c16b537SWarner Losh break; 29470c16b537SWarner Losh default: 29480c16b537SWarner Losh return ERROR(GENERIC); /* impossible */ 29490c16b537SWarner Losh } 29500c16b537SWarner Losh if (cBlockSize == 0) break; /* bt_end */ 29510c16b537SWarner Losh 29520c16b537SWarner Losh if (ZSTD_isError(decodedSize)) return decodedSize; 29530c16b537SWarner Losh op += decodedSize; 29540c16b537SWarner Losh ip += cBlockSize; 29550c16b537SWarner Losh remainingSize -= cBlockSize; 29560c16b537SWarner Losh } 29570c16b537SWarner Losh 29580c16b537SWarner Losh return op-ostart; 29590c16b537SWarner Losh } 29600c16b537SWarner Losh 29610c16b537SWarner Losh static size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 29620c16b537SWarner Losh { 29630c16b537SWarner Losh ZSTD_DCtx ctx; 29640c16b537SWarner Losh ctx.base = dst; 29650c16b537SWarner Losh return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize); 29660c16b537SWarner Losh } 29670c16b537SWarner Losh 29682b9c00cbSConrad Meyer /* ZSTD_errorFrameSizeInfoLegacy() : 29692b9c00cbSConrad Meyer assumes `cSize` and `dBound` are _not_ NULL */ 29702b9c00cbSConrad Meyer MEM_STATIC void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret) 29712b9c00cbSConrad Meyer { 29722b9c00cbSConrad Meyer *cSize = ret; 29732b9c00cbSConrad Meyer *dBound = ZSTD_CONTENTSIZE_ERROR; 29742b9c00cbSConrad Meyer } 29752b9c00cbSConrad Meyer 29762b9c00cbSConrad Meyer void ZSTDv03_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound) 29770c16b537SWarner Losh { 29780c16b537SWarner Losh const BYTE* ip = (const BYTE*)src; 29790c16b537SWarner Losh size_t remainingSize = srcSize; 29802b9c00cbSConrad Meyer size_t nbBlocks = 0; 29810c16b537SWarner Losh U32 magicNumber; 29820c16b537SWarner Losh blockProperties_t blockProperties; 29830c16b537SWarner Losh 29840c16b537SWarner Losh /* Frame Header */ 29852b9c00cbSConrad Meyer if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) { 29862b9c00cbSConrad Meyer ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 29872b9c00cbSConrad Meyer return; 29882b9c00cbSConrad Meyer } 29890c16b537SWarner Losh magicNumber = MEM_readLE32(src); 29902b9c00cbSConrad Meyer if (magicNumber != ZSTD_magicNumber) { 29912b9c00cbSConrad Meyer ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown)); 29922b9c00cbSConrad Meyer return; 29932b9c00cbSConrad Meyer } 29940c16b537SWarner Losh ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize; 29950c16b537SWarner Losh 29960c16b537SWarner Losh /* Loop on each block */ 29970c16b537SWarner Losh while (1) 29980c16b537SWarner Losh { 29990c16b537SWarner Losh size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties); 30002b9c00cbSConrad Meyer if (ZSTD_isError(cBlockSize)) { 30012b9c00cbSConrad Meyer ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize); 30022b9c00cbSConrad Meyer return; 30032b9c00cbSConrad Meyer } 30040c16b537SWarner Losh 30050c16b537SWarner Losh ip += ZSTD_blockHeaderSize; 30060c16b537SWarner Losh remainingSize -= ZSTD_blockHeaderSize; 30072b9c00cbSConrad Meyer if (cBlockSize > remainingSize) { 30082b9c00cbSConrad Meyer ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 30092b9c00cbSConrad Meyer return; 30102b9c00cbSConrad Meyer } 30110c16b537SWarner Losh 30120c16b537SWarner Losh if (cBlockSize == 0) break; /* bt_end */ 30130c16b537SWarner Losh 30140c16b537SWarner Losh ip += cBlockSize; 30150c16b537SWarner Losh remainingSize -= cBlockSize; 30162b9c00cbSConrad Meyer nbBlocks++; 30170c16b537SWarner Losh } 30180c16b537SWarner Losh 30192b9c00cbSConrad Meyer *cSize = ip - (const BYTE*)src; 30202b9c00cbSConrad Meyer *dBound = nbBlocks * BLOCKSIZE; 30210c16b537SWarner Losh } 30220c16b537SWarner Losh 30230c16b537SWarner Losh 30240c16b537SWarner Losh /******************************* 30250c16b537SWarner Losh * Streaming Decompression API 30260c16b537SWarner Losh *******************************/ 30270c16b537SWarner Losh 30280c16b537SWarner Losh static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx) 30290c16b537SWarner Losh { 30300c16b537SWarner Losh dctx->expected = ZSTD_frameHeaderSize; 30310c16b537SWarner Losh dctx->phase = 0; 30320c16b537SWarner Losh dctx->previousDstEnd = NULL; 30330c16b537SWarner Losh dctx->base = NULL; 30340c16b537SWarner Losh return 0; 30350c16b537SWarner Losh } 30360c16b537SWarner Losh 30370c16b537SWarner Losh static ZSTD_DCtx* ZSTD_createDCtx(void) 30380c16b537SWarner Losh { 30390c16b537SWarner Losh ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx)); 30400c16b537SWarner Losh if (dctx==NULL) return NULL; 30410c16b537SWarner Losh ZSTD_resetDCtx(dctx); 30420c16b537SWarner Losh return dctx; 30430c16b537SWarner Losh } 30440c16b537SWarner Losh 30450c16b537SWarner Losh static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx) 30460c16b537SWarner Losh { 30470c16b537SWarner Losh free(dctx); 30480c16b537SWarner Losh return 0; 30490c16b537SWarner Losh } 30500c16b537SWarner Losh 30510c16b537SWarner Losh static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx) 30520c16b537SWarner Losh { 30530c16b537SWarner Losh return dctx->expected; 30540c16b537SWarner Losh } 30550c16b537SWarner Losh 30560c16b537SWarner Losh static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 30570c16b537SWarner Losh { 30580c16b537SWarner Losh /* Sanity check */ 30590c16b537SWarner Losh if (srcSize != ctx->expected) return ERROR(srcSize_wrong); 30600c16b537SWarner Losh if (dst != ctx->previousDstEnd) /* not contiguous */ 30610c16b537SWarner Losh ctx->base = dst; 30620c16b537SWarner Losh 30630c16b537SWarner Losh /* Decompress : frame header */ 30640c16b537SWarner Losh if (ctx->phase == 0) 30650c16b537SWarner Losh { 30660c16b537SWarner Losh /* Check frame magic header */ 30670c16b537SWarner Losh U32 magicNumber = MEM_readLE32(src); 30680c16b537SWarner Losh if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown); 30690c16b537SWarner Losh ctx->phase = 1; 30700c16b537SWarner Losh ctx->expected = ZSTD_blockHeaderSize; 30710c16b537SWarner Losh return 0; 30720c16b537SWarner Losh } 30730c16b537SWarner Losh 30740c16b537SWarner Losh /* Decompress : block header */ 30750c16b537SWarner Losh if (ctx->phase == 1) 30760c16b537SWarner Losh { 30770c16b537SWarner Losh blockProperties_t bp; 30780c16b537SWarner Losh size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp); 30790c16b537SWarner Losh if (ZSTD_isError(blockSize)) return blockSize; 30800c16b537SWarner Losh if (bp.blockType == bt_end) 30810c16b537SWarner Losh { 30820c16b537SWarner Losh ctx->expected = 0; 30830c16b537SWarner Losh ctx->phase = 0; 30840c16b537SWarner Losh } 30850c16b537SWarner Losh else 30860c16b537SWarner Losh { 30870c16b537SWarner Losh ctx->expected = blockSize; 30880c16b537SWarner Losh ctx->bType = bp.blockType; 30890c16b537SWarner Losh ctx->phase = 2; 30900c16b537SWarner Losh } 30910c16b537SWarner Losh 30920c16b537SWarner Losh return 0; 30930c16b537SWarner Losh } 30940c16b537SWarner Losh 30950c16b537SWarner Losh /* Decompress : block content */ 30960c16b537SWarner Losh { 30970c16b537SWarner Losh size_t rSize; 30980c16b537SWarner Losh switch(ctx->bType) 30990c16b537SWarner Losh { 31000c16b537SWarner Losh case bt_compressed: 31010c16b537SWarner Losh rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize); 31020c16b537SWarner Losh break; 31030c16b537SWarner Losh case bt_raw : 31040c16b537SWarner Losh rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize); 31050c16b537SWarner Losh break; 31060c16b537SWarner Losh case bt_rle : 31070c16b537SWarner Losh return ERROR(GENERIC); /* not yet handled */ 31080c16b537SWarner Losh break; 31090c16b537SWarner Losh case bt_end : /* should never happen (filtered at phase 1) */ 31100c16b537SWarner Losh rSize = 0; 31110c16b537SWarner Losh break; 31120c16b537SWarner Losh default: 31130c16b537SWarner Losh return ERROR(GENERIC); 31140c16b537SWarner Losh } 31150c16b537SWarner Losh ctx->phase = 1; 31160c16b537SWarner Losh ctx->expected = ZSTD_blockHeaderSize; 31170c16b537SWarner Losh ctx->previousDstEnd = (void*)( ((char*)dst) + rSize); 31180c16b537SWarner Losh return rSize; 31190c16b537SWarner Losh } 31200c16b537SWarner Losh 31210c16b537SWarner Losh } 31220c16b537SWarner Losh 31230c16b537SWarner Losh 31240c16b537SWarner Losh /* wrapper layer */ 31250c16b537SWarner Losh 31260c16b537SWarner Losh unsigned ZSTDv03_isError(size_t code) 31270c16b537SWarner Losh { 31280c16b537SWarner Losh return ZSTD_isError(code); 31290c16b537SWarner Losh } 31300c16b537SWarner Losh 31310c16b537SWarner Losh size_t ZSTDv03_decompress( void* dst, size_t maxOriginalSize, 31320c16b537SWarner Losh const void* src, size_t compressedSize) 31330c16b537SWarner Losh { 31340c16b537SWarner Losh return ZSTD_decompress(dst, maxOriginalSize, src, compressedSize); 31350c16b537SWarner Losh } 31360c16b537SWarner Losh 31370c16b537SWarner Losh ZSTDv03_Dctx* ZSTDv03_createDCtx(void) 31380c16b537SWarner Losh { 31390c16b537SWarner Losh return (ZSTDv03_Dctx*)ZSTD_createDCtx(); 31400c16b537SWarner Losh } 31410c16b537SWarner Losh 31420c16b537SWarner Losh size_t ZSTDv03_freeDCtx(ZSTDv03_Dctx* dctx) 31430c16b537SWarner Losh { 31440c16b537SWarner Losh return ZSTD_freeDCtx((ZSTD_DCtx*)dctx); 31450c16b537SWarner Losh } 31460c16b537SWarner Losh 31470c16b537SWarner Losh size_t ZSTDv03_resetDCtx(ZSTDv03_Dctx* dctx) 31480c16b537SWarner Losh { 31490c16b537SWarner Losh return ZSTD_resetDCtx((ZSTD_DCtx*)dctx); 31500c16b537SWarner Losh } 31510c16b537SWarner Losh 31520c16b537SWarner Losh size_t ZSTDv03_nextSrcSizeToDecompress(ZSTDv03_Dctx* dctx) 31530c16b537SWarner Losh { 31540c16b537SWarner Losh return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx*)dctx); 31550c16b537SWarner Losh } 31560c16b537SWarner Losh 31570c16b537SWarner Losh size_t ZSTDv03_decompressContinue(ZSTDv03_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 31580c16b537SWarner Losh { 31590c16b537SWarner Losh return ZSTD_decompressContinue((ZSTD_DCtx*)dctx, dst, maxDstSize, src, srcSize); 31600c16b537SWarner Losh } 3161