zstd_decompress_internal.h

  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 *********************************************************/
 31static 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
 38static 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
 44static 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
 50static 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
 81typedef 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
 90typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
 91               ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,
 92               ZSTDds_decompressLastBlock, ZSTDds_checkChecksum,
 93               ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTD_dStage;
 94
 95typedef enum { zdss_init=0, zdss_loadHeader,
 96               zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;
 97
 98typedef 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 */
105typedef 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
121typedef 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
127struct 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
206MEM_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) */
222size_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. */
230void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst, size_t dstSize);
231
232
233#endif /* ZSTD_DECOMPRESS_INTERNAL_H */