| 1 |
/* |
| 2 |
* Copyright (c) 2016-2020, 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 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 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 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 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 |
typedef struct { |
| 77 |
ZSTD_seqSymbol LLTable[SEQSYMBOL_TABLE_SIZE(LLFSELog)]; /* Note : Space reserved for FSE Tables */ |
| 78 |
ZSTD_seqSymbol OFTable[SEQSYMBOL_TABLE_SIZE(OffFSELog)]; /* is also used as temporary workspace while building hufTable during DDict creation */ |
| 79 |
ZSTD_seqSymbol MLTable[SEQSYMBOL_TABLE_SIZE(MLFSELog)]; /* and therefore must be at least HUF_DECOMPRESS_WORKSPACE_SIZE large */ |
| 80 |
HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)]; /* can accommodate HUF_decompress4X */ |
| 81 |
U32 rep[ZSTD_REP_NUM]; |
| 82 |
} ZSTD_entropyDTables_t; |
| 83 |
|
| 84 |
typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader, |
| 85 |
ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock, |
| 86 |
ZSTDds_decompressLastBlock, ZSTDds_checkChecksum, |
| 87 |
ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTD_dStage; |
| 88 |
|
| 89 |
typedef enum { zdss_init=0, zdss_loadHeader, |
| 90 |
zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage; |
| 91 |
|
| 92 |
typedef enum { |
| 93 |
ZSTD_use_indefinitely = -1, /* Use the dictionary indefinitely */ |
| 94 |
ZSTD_dont_use = 0, /* Do not use the dictionary (if one exists free it) */ |
| 95 |
ZSTD_use_once = 1 /* Use the dictionary once and set to ZSTD_dont_use */ |
| 96 |
} ZSTD_dictUses_e; |
| 97 |
|
| 98 |
typedef enum { |
| 99 |
ZSTD_obm_buffered = 0, /* Buffer the output */ |
| 100 |
ZSTD_obm_stable = 1 /* ZSTD_outBuffer is stable */ |
| 101 |
} ZSTD_outBufferMode_e; |
| 102 |
|
| 103 |
struct ZSTD_DCtx_s |
| 104 |
{ |
| 105 |
const ZSTD_seqSymbol* LLTptr; |
| 106 |
const ZSTD_seqSymbol* MLTptr; |
| 107 |
const ZSTD_seqSymbol* OFTptr; |
| 108 |
const HUF_DTable* HUFptr; |
| 109 |
ZSTD_entropyDTables_t entropy; |
| 110 |
U32 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32]; /* space needed when building huffman tables */ |
| 111 |
const void* previousDstEnd; /* detect continuity */ |
| 112 |
const void* prefixStart; /* start of current segment */ |
| 113 |
const void* virtualStart; /* virtual start of previous segment if it was just before current one */ |
| 114 |
const void* dictEnd; /* end of previous segment */ |
| 115 |
size_t expected; |
| 116 |
ZSTD_frameHeader fParams; |
| 117 |
U64 decodedSize; |
| 118 |
blockType_e bType; /* used in ZSTD_decompressContinue(), store blockType between block header decoding and block decompression stages */ |
| 119 |
ZSTD_dStage stage; |
| 120 |
U32 litEntropy; |
| 121 |
U32 fseEntropy; |
| 122 |
XXH64_state_t xxhState; |
| 123 |
size_t headerSize; |
| 124 |
ZSTD_format_e format; |
| 125 |
const BYTE* litPtr; |
| 126 |
ZSTD_customMem customMem; |
| 127 |
size_t litSize; |
| 128 |
size_t rleSize; |
| 129 |
size_t staticSize; |
| 130 |
int bmi2; /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */ |
| 131 |
|
| 132 |
/* dictionary */ |
| 133 |
ZSTD_DDict* ddictLocal; |
| 134 |
const ZSTD_DDict* ddict; /* set by ZSTD_initDStream_usingDDict(), or ZSTD_DCtx_refDDict() */ |
| 135 |
U32 dictID; |
| 136 |
int ddictIsCold; /* if == 1 : dictionary is "new" for working context, and presumed "cold" (not in cpu cache) */ |
| 137 |
ZSTD_dictUses_e dictUses; |
| 138 |
|
| 139 |
/* streaming */ |
| 140 |
ZSTD_dStreamStage streamStage; |
| 141 |
char* inBuff; |
| 142 |
size_t inBuffSize; |
| 143 |
size_t inPos; |
| 144 |
size_t maxWindowSize; |
| 145 |
char* outBuff; |
| 146 |
size_t outBuffSize; |
| 147 |
size_t outStart; |
| 148 |
size_t outEnd; |
| 149 |
size_t lhSize; |
| 150 |
void* legacyContext; |
| 151 |
U32 previousLegacyVersion; |
| 152 |
U32 legacyVersion; |
| 153 |
U32 hostageByte; |
| 154 |
int noForwardProgress; |
| 155 |
ZSTD_outBufferMode_e outBufferMode; |
| 156 |
ZSTD_outBuffer expectedOutBuffer; |
| 157 |
|
| 158 |
/* workspace */ |
| 159 |
BYTE litBuffer[ZSTD_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH]; |
| 160 |
BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX]; |
| 161 |
|
| 162 |
size_t oversizedDuration; |
| 163 |
|
| 164 |
#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION |
| 165 |
void const* dictContentBeginForFuzzing; |
| 166 |
void const* dictContentEndForFuzzing; |
| 167 |
#endif |
| 168 |
}; /* typedef'd to ZSTD_DCtx within "zstd.h" */ |
| 169 |
|
| 170 |
|
| 171 |
/*-******************************************************* |
| 172 |
* Shared internal functions |
| 173 |
*********************************************************/ |
| 174 |
|
| 175 |
/*! ZSTD_loadDEntropy() : |
| 176 |
* dict : must point at beginning of a valid zstd dictionary. |
| 177 |
* @return : size of dictionary header (size of magic number + dict ID + entropy tables) */ |
| 178 |
size_t ZSTD_loadDEntropy(ZSTD_entropyDTables_t* entropy, |
| 179 |
const void* const dict, size_t const dictSize); |
| 180 |
|
| 181 |
/*! ZSTD_checkContinuity() : |
| 182 |
* check if next `dst` follows previous position, where decompression ended. |
| 183 |
* If yes, do nothing (continue on current segment). |
| 184 |
* If not, classify previous segment as "external dictionary", and start a new segment. |
| 185 |
* This function cannot fail. */ |
| 186 |
void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst); |
| 187 |
|
| 188 |
|
| 189 |
#endif /* ZSTD_DECOMPRESS_INTERNAL_H */ |