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