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