229 lines · c
1/*2 * Copyright (c) Yann Collet, Facebook, Inc.3 * All rights reserved.4 *5 * This source code is licensed under both the BSD-style license (found in the6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found7 * in the COPYING file in the root directory of this source tree).8 * You may select, at your option, one of the above-listed licenses.9 */10 11 12/* zstd_decompress_internal:13 * objects and definitions shared within lib/decompress modules */14 15 #ifndef ZSTD_DECOMPRESS_INTERNAL_H16 #define ZSTD_DECOMPRESS_INTERNAL_H17 18 19/*-*******************************************************20 * Dependencies21 *********************************************************/22#include "../common/mem.h" /* BYTE, U16, U32 */23#include "../common/zstd_internal.h" /* constants : MaxLL, MaxML, MaxOff, LLFSELog, etc. */24 25 26 27/*-*******************************************************28 * Constants29 *********************************************************/30static UNUSED_ATTR const U32 LL_base[MaxLL+1] = {31 0, 1, 2, 3, 4, 5, 6, 7,32 8, 9, 10, 11, 12, 13, 14, 15,33 16, 18, 20, 22, 24, 28, 32, 40,34 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,35 0x2000, 0x4000, 0x8000, 0x10000 };36 37static UNUSED_ATTR const U32 OF_base[MaxOff+1] = {38 0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D,39 0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD,40 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,41 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD, 0x1FFFFFFD, 0x3FFFFFFD, 0x7FFFFFFD };42 43static UNUSED_ATTR const U8 OF_bits[MaxOff+1] = {44 0, 1, 2, 3, 4, 5, 6, 7,45 8, 9, 10, 11, 12, 13, 14, 15,46 16, 17, 18, 19, 20, 21, 22, 23,47 24, 25, 26, 27, 28, 29, 30, 31 };48 49static UNUSED_ATTR const U32 ML_base[MaxML+1] = {50 3, 4, 5, 6, 7, 8, 9, 10,51 11, 12, 13, 14, 15, 16, 17, 18,52 19, 20, 21, 22, 23, 24, 25, 26,53 27, 28, 29, 30, 31, 32, 33, 34,54 35, 37, 39, 41, 43, 47, 51, 59,55 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,56 0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };57 58 59/*-*******************************************************60 * Decompression types61 *********************************************************/62 typedef struct {63 U32 fastMode;64 U32 tableLog;65 } ZSTD_seqSymbol_header;66 67 typedef struct {68 U16 nextState;69 BYTE nbAdditionalBits;70 BYTE nbBits;71 U32 baseValue;72 } ZSTD_seqSymbol;73 74 #define SEQSYMBOL_TABLE_SIZE(log) (1 + (1 << (log)))75 76#define ZSTD_BUILD_FSE_TABLE_WKSP_SIZE (sizeof(S16) * (MaxSeq + 1) + (1u << MaxFSELog) + sizeof(U64))77#define ZSTD_BUILD_FSE_TABLE_WKSP_SIZE_U32 ((ZSTD_BUILD_FSE_TABLE_WKSP_SIZE + sizeof(U32) - 1) / sizeof(U32))78 79typedef struct {80 ZSTD_seqSymbol LLTable[SEQSYMBOL_TABLE_SIZE(LLFSELog)]; /* Note : Space reserved for FSE Tables */81 ZSTD_seqSymbol OFTable[SEQSYMBOL_TABLE_SIZE(OffFSELog)]; /* is also used as temporary workspace while building hufTable during DDict creation */82 ZSTD_seqSymbol MLTable[SEQSYMBOL_TABLE_SIZE(MLFSELog)]; /* and therefore must be at least HUF_DECOMPRESS_WORKSPACE_SIZE large */83 HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)]; /* can accommodate HUF_decompress4X */84 U32 rep[ZSTD_REP_NUM];85 U32 workspace[ZSTD_BUILD_FSE_TABLE_WKSP_SIZE_U32];86} ZSTD_entropyDTables_t;87 88typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,89 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,90 ZSTDds_decompressLastBlock, ZSTDds_checkChecksum,91 ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTD_dStage;92 93typedef enum { zdss_init=0, zdss_loadHeader,94 zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;95 96typedef enum {97 ZSTD_use_indefinitely = -1, /* Use the dictionary indefinitely */98 ZSTD_dont_use = 0, /* Do not use the dictionary (if one exists free it) */99 ZSTD_use_once = 1 /* Use the dictionary once and set to ZSTD_dont_use */100} ZSTD_dictUses_e;101 102/* Hashset for storing references to multiple ZSTD_DDict within ZSTD_DCtx */103typedef struct {104 const ZSTD_DDict** ddictPtrTable;105 size_t ddictPtrTableSize;106 size_t ddictPtrCount;107} ZSTD_DDictHashSet;108 109#ifndef ZSTD_DECODER_INTERNAL_BUFFER110# define ZSTD_DECODER_INTERNAL_BUFFER (1 << 16)111#endif112 113#define ZSTD_LBMIN 64114#define ZSTD_LBMAX (128 << 10)115 116/* extra buffer, compensates when dst is not large enough to store litBuffer */117#define ZSTD_LITBUFFEREXTRASIZE BOUNDED(ZSTD_LBMIN, ZSTD_DECODER_INTERNAL_BUFFER, ZSTD_LBMAX)118 119typedef enum {120 ZSTD_not_in_dst = 0, /* Stored entirely within litExtraBuffer */121 ZSTD_in_dst = 1, /* Stored entirely within dst (in memory after current output write) */122 ZSTD_split = 2 /* Split between litExtraBuffer and dst */123} ZSTD_litLocation_e;124 125struct ZSTD_DCtx_s126{127 const ZSTD_seqSymbol* LLTptr;128 const ZSTD_seqSymbol* MLTptr;129 const ZSTD_seqSymbol* OFTptr;130 const HUF_DTable* HUFptr;131 ZSTD_entropyDTables_t entropy;132 U32 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32]; /* space needed when building huffman tables */133 const void* previousDstEnd; /* detect continuity */134 const void* prefixStart; /* start of current segment */135 const void* virtualStart; /* virtual start of previous segment if it was just before current one */136 const void* dictEnd; /* end of previous segment */137 size_t expected;138 ZSTD_frameHeader fParams;139 U64 processedCSize;140 U64 decodedSize;141 blockType_e bType; /* used in ZSTD_decompressContinue(), store blockType between block header decoding and block decompression stages */142 ZSTD_dStage stage;143 U32 litEntropy;144 U32 fseEntropy;145 struct xxh64_state xxhState;146 size_t headerSize;147 ZSTD_format_e format;148 ZSTD_forceIgnoreChecksum_e forceIgnoreChecksum; /* User specified: if == 1, will ignore checksums in compressed frame. Default == 0 */149 U32 validateChecksum; /* if == 1, will validate checksum. Is == 1 if (fParams.checksumFlag == 1) and (forceIgnoreChecksum == 0). */150 const BYTE* litPtr;151 ZSTD_customMem customMem;152 size_t litSize;153 size_t rleSize;154 size_t staticSize;155#if DYNAMIC_BMI2 != 0156 int bmi2; /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */157#endif158 159 /* dictionary */160 ZSTD_DDict* ddictLocal;161 const ZSTD_DDict* ddict; /* set by ZSTD_initDStream_usingDDict(), or ZSTD_DCtx_refDDict() */162 U32 dictID;163 int ddictIsCold; /* if == 1 : dictionary is "new" for working context, and presumed "cold" (not in cpu cache) */164 ZSTD_dictUses_e dictUses;165 ZSTD_DDictHashSet* ddictSet; /* Hash set for multiple ddicts */166 ZSTD_refMultipleDDicts_e refMultipleDDicts; /* User specified: if == 1, will allow references to multiple DDicts. Default == 0 (disabled) */167 168 /* streaming */169 ZSTD_dStreamStage streamStage;170 char* inBuff;171 size_t inBuffSize;172 size_t inPos;173 size_t maxWindowSize;174 char* outBuff;175 size_t outBuffSize;176 size_t outStart;177 size_t outEnd;178 size_t lhSize;179 U32 hostageByte;180 int noForwardProgress;181 ZSTD_bufferMode_e outBufferMode;182 ZSTD_outBuffer expectedOutBuffer;183 184 /* workspace */185 BYTE* litBuffer;186 const BYTE* litBufferEnd;187 ZSTD_litLocation_e litBufferLocation;188 BYTE litExtraBuffer[ZSTD_LITBUFFEREXTRASIZE + WILDCOPY_OVERLENGTH]; /* literal buffer can be split between storage within dst and within this scratch buffer */189 BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];190 191 size_t oversizedDuration;192 193#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION194 void const* dictContentBeginForFuzzing;195 void const* dictContentEndForFuzzing;196#endif197 198 /* Tracing */199}; /* typedef'd to ZSTD_DCtx within "zstd.h" */200 201MEM_STATIC int ZSTD_DCtx_get_bmi2(const struct ZSTD_DCtx_s *dctx) {202#if DYNAMIC_BMI2 != 0203 return dctx->bmi2;204#else205 (void)dctx;206 return 0;207#endif208}209 210/*-*******************************************************211 * Shared internal functions212 *********************************************************/213 214/*! ZSTD_loadDEntropy() :215 * dict : must point at beginning of a valid zstd dictionary.216 * @return : size of dictionary header (size of magic number + dict ID + entropy tables) */217size_t ZSTD_loadDEntropy(ZSTD_entropyDTables_t* entropy,218 const void* const dict, size_t const dictSize);219 220/*! ZSTD_checkContinuity() :221 * check if next `dst` follows previous position, where decompression ended.222 * If yes, do nothing (continue on current segment).223 * If not, classify previous segment as "external dictionary", and start a new segment.224 * This function cannot fail. */225void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst, size_t dstSize);226 227 228#endif /* ZSTD_DECOMPRESS_INTERNAL_H */229