zstd/decompress/zstd_decompress_internal.h

0001 /*
0002  * Copyright (c) Yann Collet, Facebook, Inc.
0003  * All rights reserved.
0004  *
0005  * This source code is licensed under both the BSD-style license (found in the
0006  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
0007  * in the COPYING file in the root directory of this source tree).
0008  * You may select, at your option, one of the above-listed licenses.
0009  */
0010
0011
0012 /* zstd_decompress_internal:
0013  * objects and definitions shared within lib/decompress modules */
0014
0015  #ifndef ZSTD_DECOMPRESS_INTERNAL_H
0016  #define ZSTD_DECOMPRESS_INTERNAL_H
0017
0018
0019 /*-*******************************************************
0020  *  Dependencies
0021  *********************************************************/
0022 #include "../common/mem.h"             /* BYTE, U16, U32 */
0023 #include "../common/zstd_internal.h"   /* ZSTD_seqSymbol */
0024
0025
0026
0027 /*-*******************************************************
0028  *  Constants
0029  *********************************************************/
0030 static UNUSED_ATTR const U32 LL_base[MaxLL+1] = {
0031                  0,    1,    2,     3,     4,     5,     6,      7,
0032                  8,    9,   10,    11,    12,    13,    14,     15,
0033                 16,   18,   20,    22,    24,    28,    32,     40,
0034                 48,   64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
0035                 0x2000, 0x4000, 0x8000, 0x10000 };
0036
0037 static UNUSED_ATTR const U32 OF_base[MaxOff+1] = {
0038                  0,        1,       1,       5,     0xD,     0x1D,     0x3D,     0x7D,
0039                  0xFD,   0x1FD,   0x3FD,   0x7FD,   0xFFD,   0x1FFD,   0x3FFD,   0x7FFD,
0040                  0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
0041                  0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD, 0x1FFFFFFD, 0x3FFFFFFD, 0x7FFFFFFD };
0042
0043 static UNUSED_ATTR const U32 OF_bits[MaxOff+1] = {
0044                      0,  1,  2,  3,  4,  5,  6,  7,
0045                      8,  9, 10, 11, 12, 13, 14, 15,
0046                     16, 17, 18, 19, 20, 21, 22, 23,
0047                     24, 25, 26, 27, 28, 29, 30, 31 };
0048
0049 static UNUSED_ATTR const U32 ML_base[MaxML+1] = {
0050                      3,  4,  5,    6,     7,     8,     9,    10,
0051                     11, 12, 13,   14,    15,    16,    17,    18,
0052                     19, 20, 21,   22,    23,    24,    25,    26,
0053                     27, 28, 29,   30,    31,    32,    33,    34,
0054                     35, 37, 39,   41,    43,    47,    51,    59,
0055                     67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
0056                     0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
0057
0058
0059 /*-*******************************************************
0060  *  Decompression types
0061  *********************************************************/
0062  typedef struct {
0063      U32 fastMode;
0064      U32 tableLog;
0065  } ZSTD_seqSymbol_header;
0066
0067  typedef struct {
0068      U16  nextState;
0069      BYTE nbAdditionalBits;
0070      BYTE nbBits;
0071      U32  baseValue;
0072  } ZSTD_seqSymbol;
0073
0074  #define SEQSYMBOL_TABLE_SIZE(log)   (1 + (1 << (log)))
0075
0076 #define ZSTD_BUILD_FSE_TABLE_WKSP_SIZE (sizeof(S16) * (MaxSeq + 1) + (1u << MaxFSELog) + sizeof(U64))
0077 #define ZSTD_BUILD_FSE_TABLE_WKSP_SIZE_U32 ((ZSTD_BUILD_FSE_TABLE_WKSP_SIZE + sizeof(U32) - 1) / sizeof(U32))
0078
0079 typedef struct {
0080     ZSTD_seqSymbol LLTable[SEQSYMBOL_TABLE_SIZE(LLFSELog)];    /* Note : Space reserved for FSE Tables */
0081     ZSTD_seqSymbol OFTable[SEQSYMBOL_TABLE_SIZE(OffFSELog)];   /* is also used as temporary workspace while building hufTable during DDict creation */
0082     ZSTD_seqSymbol MLTable[SEQSYMBOL_TABLE_SIZE(MLFSELog)];    /* and therefore must be at least HUF_DECOMPRESS_WORKSPACE_SIZE large */
0083     HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)];  /* can accommodate HUF_decompress4X */
0084     U32 rep[ZSTD_REP_NUM];
0085     U32 workspace[ZSTD_BUILD_FSE_TABLE_WKSP_SIZE_U32];
0086 } ZSTD_entropyDTables_t;
0087
0088 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
0089                ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,
0090                ZSTDds_decompressLastBlock, ZSTDds_checkChecksum,
0091                ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTD_dStage;
0092
0093 typedef enum { zdss_init=0, zdss_loadHeader,
0094                zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;
0095
0096 typedef enum {
0097     ZSTD_use_indefinitely = -1,  /* Use the dictionary indefinitely */
0098     ZSTD_dont_use = 0,           /* Do not use the dictionary (if one exists free it) */
0099     ZSTD_use_once = 1            /* Use the dictionary once and set to ZSTD_dont_use */
0100 } ZSTD_dictUses_e;
0101
0102 /* Hashset for storing references to multiple ZSTD_DDict within ZSTD_DCtx */
0103 typedef struct {
0104     const ZSTD_DDict** ddictPtrTable;
0105     size_t ddictPtrTableSize;
0106     size_t ddictPtrCount;
0107 } ZSTD_DDictHashSet;
0108
0109 struct ZSTD_DCtx_s
0110 {
0111     const ZSTD_seqSymbol* LLTptr;
0112     const ZSTD_seqSymbol* MLTptr;
0113     const ZSTD_seqSymbol* OFTptr;
0114     const HUF_DTable* HUFptr;
0115     ZSTD_entropyDTables_t entropy;
0116     U32 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];   /* space needed when building huffman tables */
0117     const void* previousDstEnd;   /* detect continuity */
0118     const void* prefixStart;      /* start of current segment */
0119     const void* virtualStart;     /* virtual start of previous segment if it was just before current one */
0120     const void* dictEnd;          /* end of previous segment */
0121     size_t expected;
0122     ZSTD_frameHeader fParams;
0123     U64 processedCSize;
0124     U64 decodedSize;
0125     blockType_e bType;            /* used in ZSTD_decompressContinue(), store blockType between block header decoding and block decompression stages */
0126     ZSTD_dStage stage;
0127     U32 litEntropy;
0128     U32 fseEntropy;
0129     struct xxh64_state xxhState;
0130     size_t headerSize;
0131     ZSTD_format_e format;
0132     ZSTD_forceIgnoreChecksum_e forceIgnoreChecksum;   /* User specified: if == 1, will ignore checksums in compressed frame. Default == 0 */
0133     U32 validateChecksum;         /* if == 1, will validate checksum. Is == 1 if (fParams.checksumFlag == 1) and (forceIgnoreChecksum == 0). */
0134     const BYTE* litPtr;
0135     ZSTD_customMem customMem;
0136     size_t litSize;
0137     size_t rleSize;
0138     size_t staticSize;
0139     int bmi2;                     /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
0140
0141     /* dictionary */
0142     ZSTD_DDict* ddictLocal;
0143     const ZSTD_DDict* ddict;     /* set by ZSTD_initDStream_usingDDict(), or ZSTD_DCtx_refDDict() */
0144     U32 dictID;
0145     int ddictIsCold;             /* if == 1 : dictionary is "new" for working context, and presumed "cold" (not in cpu cache) */
0146     ZSTD_dictUses_e dictUses;
0147     ZSTD_DDictHashSet* ddictSet;                    /* Hash set for multiple ddicts */
0148     ZSTD_refMultipleDDicts_e refMultipleDDicts;     /* User specified: if == 1, will allow references to multiple DDicts. Default == 0 (disabled) */
0149
0150     /* streaming */
0151     ZSTD_dStreamStage streamStage;
0152     char*  inBuff;
0153     size_t inBuffSize;
0154     size_t inPos;
0155     size_t maxWindowSize;
0156     char*  outBuff;
0157     size_t outBuffSize;
0158     size_t outStart;
0159     size_t outEnd;
0160     size_t lhSize;
0161     void* legacyContext;
0162     U32 previousLegacyVersion;
0163     U32 legacyVersion;
0164     U32 hostageByte;
0165     int noForwardProgress;
0166     ZSTD_bufferMode_e outBufferMode;
0167     ZSTD_outBuffer expectedOutBuffer;
0168
0169     /* workspace */
0170     BYTE litBuffer[ZSTD_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH];
0171     BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];
0172
0173     size_t oversizedDuration;
0174
0175 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
0176     void const* dictContentBeginForFuzzing;
0177     void const* dictContentEndForFuzzing;
0178 #endif
0179
0180     /* Tracing */
0181 };  /* typedef'd to ZSTD_DCtx within "zstd.h" */
0182
0183
0184 /*-*******************************************************
0185  *  Shared internal functions
0186  *********************************************************/
0187
0188 /*! ZSTD_loadDEntropy() :
0189  *  dict : must point at beginning of a valid zstd dictionary.
0190  * @return : size of dictionary header (size of magic number + dict ID + entropy tables) */
0191 size_t ZSTD_loadDEntropy(ZSTD_entropyDTables_t* entropy,
0192                    const void* const dict, size_t const dictSize);
0193
0194 /*! ZSTD_checkContinuity() :
0195  *  check if next `dst` follows previous position, where decompression ended.
0196  *  If yes, do nothing (continue on current segment).
0197  *  If not, classify previous segment as "external dictionary", and start a new segment.
0198  *  This function cannot fail. */
0199 void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst, size_t dstSize);
0200
0201
0202 #endif /* ZSTD_DECOMPRESS_INTERNAL_H */