1 /* 2 * Copyright (c) Yann Collet, Facebook, Inc. 3 * All rights reserved. 4 * 5 * This source code is licensed under both the BSD-style license (found in the 6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found 7 * in the COPYING file in the root directory of this source tree). 8 * You may select, at your option, one of the above-listed licenses. 9 */ 10 11 12 /* zstd_decompress_internal: 13 * objects and definitions shared within lib/decompress modules */ 14 15 #ifndef ZSTD_DECOMPRESS_INTERNAL_H 16 #define ZSTD_DECOMPRESS_INTERNAL_H 17 18 19 /*-******************************************************* 20 * Dependencies 21 *********************************************************/ 22 #include "../common/mem.h" /* BYTE, U16, U32 */ 23 #include "../common/zstd_internal.h" /* ZSTD_seqSymbol */ 24 25 26 27 /*-******************************************************* 28 * Constants 29 *********************************************************/ 30 static 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 37 static 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 43 static UNUSED_ATTR const U32 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 49 static 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 types 61 *********************************************************/ 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 79 typedef 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 88 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader, 89 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock, 90 ZSTDds_decompressLastBlock, ZSTDds_checkChecksum, 91 ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTD_dStage; 92 93 typedef enum { zdss_init=0, zdss_loadHeader, 94 zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage; 95 96 typedef 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 */ 103 typedef struct { 104 const ZSTD_DDict** ddictPtrTable; 105 size_t ddictPtrTableSize; 106 size_t ddictPtrCount; 107 } ZSTD_DDictHashSet; 108 109 struct ZSTD_DCtx_s 110 { 111 const ZSTD_seqSymbol* LLTptr; 112 const ZSTD_seqSymbol* MLTptr; 113 const ZSTD_seqSymbol* OFTptr; 114 const HUF_DTable* HUFptr; 115 ZSTD_entropyDTables_t entropy; 116 U32 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32]; /* space needed when building huffman tables */ 117 const void* previousDstEnd; /* detect continuity */ 118 const void* prefixStart; /* start of current segment */ 119 const void* virtualStart; /* virtual start of previous segment if it was just before current one */ 120 const void* dictEnd; /* end of previous segment */ 121 size_t expected; 122 ZSTD_frameHeader fParams; 123 U64 processedCSize; 124 U64 decodedSize; 125 blockType_e bType; /* used in ZSTD_decompressContinue(), store blockType between block header decoding and block decompression stages */ 126 ZSTD_dStage stage; 127 U32 litEntropy; 128 U32 fseEntropy; 129 XXH64_state_t xxhState; 130 size_t headerSize; 131 ZSTD_format_e format; 132 ZSTD_forceIgnoreChecksum_e forceIgnoreChecksum; /* User specified: if == 1, will ignore checksums in compressed frame. Default == 0 */ 133 U32 validateChecksum; /* if == 1, will validate checksum. Is == 1 if (fParams.checksumFlag == 1) and (forceIgnoreChecksum == 0). */ 134 const BYTE* litPtr; 135 ZSTD_customMem customMem; 136 size_t litSize; 137 size_t rleSize; 138 size_t staticSize; 139 int bmi2; /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */ 140 141 /* dictionary */ 142 ZSTD_DDict* ddictLocal; 143 const ZSTD_DDict* ddict; /* set by ZSTD_initDStream_usingDDict(), or ZSTD_DCtx_refDDict() */ 144 U32 dictID; 145 int ddictIsCold; /* if == 1 : dictionary is "new" for working context, and presumed "cold" (not in cpu cache) */ 146 ZSTD_dictUses_e dictUses; 147 ZSTD_DDictHashSet* ddictSet; /* Hash set for multiple ddicts */ 148 ZSTD_refMultipleDDicts_e refMultipleDDicts; /* User specified: if == 1, will allow references to multiple DDicts. Default == 0 (disabled) */ 149 150 /* streaming */ 151 ZSTD_dStreamStage streamStage; 152 char* inBuff; 153 size_t inBuffSize; 154 size_t inPos; 155 size_t maxWindowSize; 156 char* outBuff; 157 size_t outBuffSize; 158 size_t outStart; 159 size_t outEnd; 160 size_t lhSize; 161 void* legacyContext; 162 U32 previousLegacyVersion; 163 U32 legacyVersion; 164 U32 hostageByte; 165 int noForwardProgress; 166 ZSTD_bufferMode_e outBufferMode; 167 ZSTD_outBuffer expectedOutBuffer; 168 169 /* workspace */ 170 BYTE litBuffer[ZSTD_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH]; 171 BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX]; 172 173 size_t oversizedDuration; 174 175 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION 176 void const* dictContentBeginForFuzzing; 177 void const* dictContentEndForFuzzing; 178 #endif 179 180 /* Tracing */ 181 #if ZSTD_TRACE 182 ZSTD_TraceCtx traceCtx; 183 #endif 184 }; /* typedef'd to ZSTD_DCtx within "zstd.h" */ 185 186 187 /*-******************************************************* 188 * Shared internal functions 189 *********************************************************/ 190 191 /*! ZSTD_loadDEntropy() : 192 * dict : must point at beginning of a valid zstd dictionary. 193 * @return : size of dictionary header (size of magic number + dict ID + entropy tables) */ 194 size_t ZSTD_loadDEntropy(ZSTD_entropyDTables_t* entropy, 195 const void* const dict, size_t const dictSize); 196 197 /*! ZSTD_checkContinuity() : 198 * check if next `dst` follows previous position, where decompression ended. 199 * If yes, do nothing (continue on current segment). 200 * If not, classify previous segment as "external dictionary", and start a new segment. 201 * This function cannot fail. */ 202 void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst, size_t dstSize); 203 204 205 #endif /* ZSTD_DECOMPRESS_INTERNAL_H */ 206