xref: /linux/lib/zstd/decompress/zstd_decompress_internal.h (revision 7ae9fb1b7ecbb5d85d07857943f677fd1a559b18)
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"   /* constants : MaxLL, MaxML, MaxOff, LLFSELog, etc. */
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 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 
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 #ifndef ZSTD_DECODER_INTERNAL_BUFFER
110 #  define ZSTD_DECODER_INTERNAL_BUFFER  (1 << 16)
111 #endif
112 
113 #define ZSTD_LBMIN 64
114 #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 
119 typedef 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 
125 struct ZSTD_DCtx_s
126 {
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 != 0
156     int bmi2;                     /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
157 #endif
158 
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_PRODUCTION
194     void const* dictContentBeginForFuzzing;
195     void const* dictContentEndForFuzzing;
196 #endif
197 
198     /* Tracing */
199 };  /* typedef'd to ZSTD_DCtx within "zstd.h" */
200 
ZSTD_DCtx_get_bmi2(const struct ZSTD_DCtx_s * dctx)201 MEM_STATIC int ZSTD_DCtx_get_bmi2(const struct ZSTD_DCtx_s *dctx) {
202 #if DYNAMIC_BMI2 != 0
203 	return dctx->bmi2;
204 #else
205     (void)dctx;
206 	return 0;
207 #endif
208 }
209 
210 /*-*******************************************************
211  *  Shared internal functions
212  *********************************************************/
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) */
217 size_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. */
225 void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst, size_t dstSize);
226 
227 
228 #endif /* ZSTD_DECOMPRESS_INTERNAL_H */
229