[pcsx_rearmed.git] / deps / libchdr / deps / zstd-1.5.5 / lib / decompress / zstd_decompress_internal.h

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 * All rights reserved.
 *
 * This source code is licensed under both the BSD-style license (found in the
 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
 * in the COPYING file in the root directory of this source tree).
 * You may select, at your option, one of the above-listed licenses.
 */


/* zstd_decompress_internal:
 * objects and definitions shared within lib/decompress modules */

 #ifndef ZSTD_DECOMPRESS_INTERNAL_H
 #define ZSTD_DECOMPRESS_INTERNAL_H


/*-*******************************************************
 *  Dependencies
 *********************************************************/
#include "../common/mem.h"             /* BYTE, U16, U32 */
#include "../common/zstd_internal.h"   /* constants : MaxLL, MaxML, MaxOff, LLFSELog, etc. */


/*-*******************************************************
 *  Constants
 *********************************************************/
static UNUSED_ATTR const U32 LL_base[MaxLL+1] = {
                 0,    1,    2,     3,     4,     5,     6,      7,
                 8,    9,   10,    11,    12,    13,    14,     15,
                16,   18,   20,    22,    24,    28,    32,     40,
                48,   64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
                0x2000, 0x4000, 0x8000, 0x10000 };

static UNUSED_ATTR const U32 OF_base[MaxOff+1] = {
                 0,        1,       1,       5,     0xD,     0x1D,     0x3D,     0x7D,
                 0xFD,   0x1FD,   0x3FD,   0x7FD,   0xFFD,   0x1FFD,   0x3FFD,   0x7FFD,
                 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
                 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD, 0x1FFFFFFD, 0x3FFFFFFD, 0x7FFFFFFD };

static UNUSED_ATTR const U8 OF_bits[MaxOff+1] = {
                     0,  1,  2,  3,  4,  5,  6,  7,
                     8,  9, 10, 11, 12, 13, 14, 15,
                    16, 17, 18, 19, 20, 21, 22, 23,
                    24, 25, 26, 27, 28, 29, 30, 31 };

static UNUSED_ATTR const U32 ML_base[MaxML+1] = {
                     3,  4,  5,    6,     7,     8,     9,    10,
                    11, 12, 13,   14,    15,    16,    17,    18,
                    19, 20, 21,   22,    23,    24,    25,    26,
                    27, 28, 29,   30,    31,    32,    33,    34,
                    35, 37, 39,   41,    43,    47,    51,    59,
                    67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
                    0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };


/*-*******************************************************
 *  Decompression types
 *********************************************************/
 typedef struct {
     U32 fastMode;
     U32 tableLog;
 } ZSTD_seqSymbol_header;

 typedef struct {
     U16  nextState;
     BYTE nbAdditionalBits;
     BYTE nbBits;
     U32  baseValue;
 } ZSTD_seqSymbol;

 #define SEQSYMBOL_TABLE_SIZE(log)   (1 + (1 << (log)))

#define ZSTD_BUILD_FSE_TABLE_WKSP_SIZE (sizeof(S16) * (MaxSeq + 1) + (1u << MaxFSELog) + sizeof(U64))
#define ZSTD_BUILD_FSE_TABLE_WKSP_SIZE_U32 ((ZSTD_BUILD_FSE_TABLE_WKSP_SIZE + sizeof(U32) - 1) / sizeof(U32))
#define ZSTD_HUFFDTABLE_CAPACITY_LOG 12

typedef struct {
    ZSTD_seqSymbol LLTable[SEQSYMBOL_TABLE_SIZE(LLFSELog)];    /* Note : Space reserved for FSE Tables */
    ZSTD_seqSymbol OFTable[SEQSYMBOL_TABLE_SIZE(OffFSELog)];   /* is also used as temporary workspace while building hufTable during DDict creation */
    ZSTD_seqSymbol MLTable[SEQSYMBOL_TABLE_SIZE(MLFSELog)];    /* and therefore must be at least HUF_DECOMPRESS_WORKSPACE_SIZE large */
    HUF_DTable hufTable[HUF_DTABLE_SIZE(ZSTD_HUFFDTABLE_CAPACITY_LOG)];  /* can accommodate HUF_decompress4X */
    U32 rep[ZSTD_REP_NUM];
    U32 workspace[ZSTD_BUILD_FSE_TABLE_WKSP_SIZE_U32];
} ZSTD_entropyDTables_t;

typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
               ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,
               ZSTDds_decompressLastBlock, ZSTDds_checkChecksum,
               ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTD_dStage;

typedef enum { zdss_init=0, zdss_loadHeader,
               zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;

typedef enum {
    ZSTD_use_indefinitely = -1,  /* Use the dictionary indefinitely */
    ZSTD_dont_use = 0,           /* Do not use the dictionary (if one exists free it) */
    ZSTD_use_once = 1            /* Use the dictionary once and set to ZSTD_dont_use */
} ZSTD_dictUses_e;

/* Hashset for storing references to multiple ZSTD_DDict within ZSTD_DCtx */
typedef struct {
    const ZSTD_DDict** ddictPtrTable;
    size_t ddictPtrTableSize;
    size_t ddictPtrCount;
} ZSTD_DDictHashSet;

#ifndef ZSTD_DECODER_INTERNAL_BUFFER
#  define ZSTD_DECODER_INTERNAL_BUFFER  (1 << 16)
#endif

#define ZSTD_LBMIN 64
#define ZSTD_LBMAX (128 << 10)

/* extra buffer, compensates when dst is not large enough to store litBuffer */
#define ZSTD_LITBUFFEREXTRASIZE  BOUNDED(ZSTD_LBMIN, ZSTD_DECODER_INTERNAL_BUFFER, ZSTD_LBMAX)

typedef enum {
    ZSTD_not_in_dst = 0,  /* Stored entirely within litExtraBuffer */
    ZSTD_in_dst = 1,           /* Stored entirely within dst (in memory after current output write) */
    ZSTD_split = 2            /* Split between litExtraBuffer and dst */
} ZSTD_litLocation_e;

struct ZSTD_DCtx_s
{
    const ZSTD_seqSymbol* LLTptr;
    const ZSTD_seqSymbol* MLTptr;
    const ZSTD_seqSymbol* OFTptr;
    const HUF_DTable* HUFptr;
    ZSTD_entropyDTables_t entropy;
    U32 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];   /* space needed when building huffman tables */
    const void* previousDstEnd;   /* detect continuity */
    const void* prefixStart;      /* start of current segment */
    const void* virtualStart;     /* virtual start of previous segment if it was just before current one */
    const void* dictEnd;          /* end of previous segment */
    size_t expected;
    ZSTD_frameHeader fParams;
    U64 processedCSize;
    U64 decodedSize;
    blockType_e bType;            /* used in ZSTD_decompressContinue(), store blockType between block header decoding and block decompression stages */
    ZSTD_dStage stage;
    U32 litEntropy;
    U32 fseEntropy;
    XXH64_state_t xxhState;
    size_t headerSize;
    ZSTD_format_e format;
    ZSTD_forceIgnoreChecksum_e forceIgnoreChecksum;   /* User specified: if == 1, will ignore checksums in compressed frame. Default == 0 */
    U32 validateChecksum;         /* if == 1, will validate checksum. Is == 1 if (fParams.checksumFlag == 1) and (forceIgnoreChecksum == 0). */
    const BYTE* litPtr;
    ZSTD_customMem customMem;
    size_t litSize;
    size_t rleSize;
    size_t staticSize;
#if DYNAMIC_BMI2 != 0
    int bmi2;                     /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
#endif

    /* dictionary */
    ZSTD_DDict* ddictLocal;
    const ZSTD_DDict* ddict;     /* set by ZSTD_initDStream_usingDDict(), or ZSTD_DCtx_refDDict() */
    U32 dictID;
    int ddictIsCold;             /* if == 1 : dictionary is "new" for working context, and presumed "cold" (not in cpu cache) */
    ZSTD_dictUses_e dictUses;
    ZSTD_DDictHashSet* ddictSet;                    /* Hash set for multiple ddicts */
    ZSTD_refMultipleDDicts_e refMultipleDDicts;     /* User specified: if == 1, will allow references to multiple DDicts. Default == 0 (disabled) */
    int disableHufAsm;

    /* streaming */
    ZSTD_dStreamStage streamStage;
    char*  inBuff;
    size_t inBuffSize;
    size_t inPos;
    size_t maxWindowSize;
    char*  outBuff;
    size_t outBuffSize;
    size_t outStart;
    size_t outEnd;
    size_t lhSize;
#if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)
    void* legacyContext;
    U32 previousLegacyVersion;
    U32 legacyVersion;
#endif
    U32 hostageByte;
    int noForwardProgress;
    ZSTD_bufferMode_e outBufferMode;
    ZSTD_outBuffer expectedOutBuffer;

    /* workspace */
    BYTE* litBuffer;
    const BYTE* litBufferEnd;
    ZSTD_litLocation_e litBufferLocation;
    BYTE litExtraBuffer[ZSTD_LITBUFFEREXTRASIZE + WILDCOPY_OVERLENGTH]; /* literal buffer can be split between storage within dst and within this scratch buffer */
    BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];

    size_t oversizedDuration;

#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
    void const* dictContentBeginForFuzzing;
    void const* dictContentEndForFuzzing;
#endif

    /* Tracing */
#if ZSTD_TRACE
    ZSTD_TraceCtx traceCtx;
#endif
};  /* typedef'd to ZSTD_DCtx within "zstd.h" */

MEM_STATIC int ZSTD_DCtx_get_bmi2(const struct ZSTD_DCtx_s *dctx) {
#if DYNAMIC_BMI2 != 0
	return dctx->bmi2;
#else
    (void)dctx;
	return 0;
#endif
}

/*-*******************************************************
 *  Shared internal functions
 *********************************************************/

/*! ZSTD_loadDEntropy() :
 *  dict : must point at beginning of a valid zstd dictionary.
 * @return : size of dictionary header (size of magic number + dict ID + entropy tables) */
size_t ZSTD_loadDEntropy(ZSTD_entropyDTables_t* entropy,
                   const void* const dict, size_t const dictSize);

/*! ZSTD_checkContinuity() :
 *  check if next `dst` follows previous position, where decompression ended.
 *  If yes, do nothing (continue on current segment).
 *  If not, classify previous segment as "external dictionary", and start a new segment.
 *  This function cannot fail. */
void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst, size_t dstSize);


#endif /* ZSTD_DECOMPRESS_INTERNAL_H */
Commit	Line	Data
648db22b	1	/*
	2	* Copyright (c) Meta Platforms, Inc. and affiliates.
	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	#define ZSTD_HUFFDTABLE_CAPACITY_LOG 12
79
80	typedef struct {
81	ZSTD_seqSymbol LLTable[SEQSYMBOL_TABLE_SIZE(LLFSELog)]; /* Note : Space reserved for FSE Tables */
82	ZSTD_seqSymbol OFTable[SEQSYMBOL_TABLE_SIZE(OffFSELog)]; /* is also used as temporary workspace while building hufTable during DDict creation */
83	ZSTD_seqSymbol MLTable[SEQSYMBOL_TABLE_SIZE(MLFSELog)]; /* and therefore must be at least HUF_DECOMPRESS_WORKSPACE_SIZE large */
84	HUF_DTable hufTable[HUF_DTABLE_SIZE(ZSTD_HUFFDTABLE_CAPACITY_LOG)]; /* can accommodate HUF_decompress4X */
85	U32 rep[ZSTD_REP_NUM];
86	U32 workspace[ZSTD_BUILD_FSE_TABLE_WKSP_SIZE_U32];
87	} ZSTD_entropyDTables_t;
88
89	typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
90	ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,
91	ZSTDds_decompressLastBlock, ZSTDds_checkChecksum,
92	ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTD_dStage;
93
94	typedef enum { zdss_init=0, zdss_loadHeader,
95	zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;
96
97	typedef enum {
98	ZSTD_use_indefinitely = -1, /* Use the dictionary indefinitely */
99	ZSTD_dont_use = 0, /* Do not use the dictionary (if one exists free it) */
100	ZSTD_use_once = 1 /* Use the dictionary once and set to ZSTD_dont_use */
101	} ZSTD_dictUses_e;
102
103	/* Hashset for storing references to multiple ZSTD_DDict within ZSTD_DCtx */
104	typedef struct {
105	const ZSTD_DDict** ddictPtrTable;
106	size_t ddictPtrTableSize;
107	size_t ddictPtrCount;
108	} ZSTD_DDictHashSet;
109
110	#ifndef ZSTD_DECODER_INTERNAL_BUFFER
111	# define ZSTD_DECODER_INTERNAL_BUFFER (1 << 16)
112	#endif
113
114	#define ZSTD_LBMIN 64
115	#define ZSTD_LBMAX (128 << 10)
116
117	/* extra buffer, compensates when dst is not large enough to store litBuffer */
118	#define ZSTD_LITBUFFEREXTRASIZE BOUNDED(ZSTD_LBMIN, ZSTD_DECODER_INTERNAL_BUFFER, ZSTD_LBMAX)
119
120	typedef enum {
121	ZSTD_not_in_dst = 0, /* Stored entirely within litExtraBuffer */
122	ZSTD_in_dst = 1, /* Stored entirely within dst (in memory after current output write) */
123	ZSTD_split = 2 /* Split between litExtraBuffer and dst */
124	} ZSTD_litLocation_e;
125
126	struct ZSTD_DCtx_s
127	{
128	const ZSTD_seqSymbol* LLTptr;
129	const ZSTD_seqSymbol* MLTptr;
130	const ZSTD_seqSymbol* OFTptr;
131	const HUF_DTable* HUFptr;
132	ZSTD_entropyDTables_t entropy;
133	U32 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32]; /* space needed when building huffman tables */
134	const void* previousDstEnd; /* detect continuity */
135	const void* prefixStart; /* start of current segment */
136	const void* virtualStart; /* virtual start of previous segment if it was just before current one */
137	const void* dictEnd; /* end of previous segment */
138	size_t expected;
139	ZSTD_frameHeader fParams;
140	U64 processedCSize;
141	U64 decodedSize;
142	blockType_e bType; /* used in ZSTD_decompressContinue(), store blockType between block header decoding and block decompression stages */
143	ZSTD_dStage stage;
144	U32 litEntropy;
145	U32 fseEntropy;
146	XXH64_state_t xxhState;
147	size_t headerSize;
148	ZSTD_format_e format;
149	ZSTD_forceIgnoreChecksum_e forceIgnoreChecksum; /* User specified: if == 1, will ignore checksums in compressed frame. Default == 0 */
150	U32 validateChecksum; /* if == 1, will validate checksum. Is == 1 if (fParams.checksumFlag == 1) and (forceIgnoreChecksum == 0). */
151	const BYTE* litPtr;
152	ZSTD_customMem customMem;
153	size_t litSize;
154	size_t rleSize;
155	size_t staticSize;
156	#if DYNAMIC_BMI2 != 0
157	int bmi2; /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
158	#endif
159
160	/* dictionary */
161	ZSTD_DDict* ddictLocal;
162	const ZSTD_DDict* ddict; /* set by ZSTD_initDStream_usingDDict(), or ZSTD_DCtx_refDDict() */
163	U32 dictID;
164	int ddictIsCold; /* if == 1 : dictionary is "new" for working context, and presumed "cold" (not in cpu cache) */
165	ZSTD_dictUses_e dictUses;
166	ZSTD_DDictHashSet* ddictSet; /* Hash set for multiple ddicts */
167	ZSTD_refMultipleDDicts_e refMultipleDDicts; /* User specified: if == 1, will allow references to multiple DDicts. Default == 0 (disabled) */
168	int disableHufAsm;
169
170	/* streaming */
171	ZSTD_dStreamStage streamStage;
172	char* inBuff;
173	size_t inBuffSize;
174	size_t inPos;
175	size_t maxWindowSize;
176	char* outBuff;
177	size_t outBuffSize;
178	size_t outStart;
179	size_t outEnd;
180	size_t lhSize;
181	#if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)
182	void* legacyContext;
183	U32 previousLegacyVersion;
184	U32 legacyVersion;
185	#endif
186	U32 hostageByte;
187	int noForwardProgress;
188	ZSTD_bufferMode_e outBufferMode;
189	ZSTD_outBuffer expectedOutBuffer;
190
191	/* workspace */
192	BYTE* litBuffer;
193	const BYTE* litBufferEnd;
194	ZSTD_litLocation_e litBufferLocation;
195	BYTE litExtraBuffer[ZSTD_LITBUFFEREXTRASIZE + WILDCOPY_OVERLENGTH]; /* literal buffer can be split between storage within dst and within this scratch buffer */
196	BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];
197
198	size_t oversizedDuration;
199
200	#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
201	void const* dictContentBeginForFuzzing;
202	void const* dictContentEndForFuzzing;
203	#endif
204
205	/* Tracing */
206	#if ZSTD_TRACE
207	ZSTD_TraceCtx traceCtx;
208	#endif
209	}; /* typedef'd to ZSTD_DCtx within "zstd.h" */
210
211	MEM_STATIC int ZSTD_DCtx_get_bmi2(const struct ZSTD_DCtx_s *dctx) {
212	#if DYNAMIC_BMI2 != 0
213	return dctx->bmi2;
214	#else
215	(void)dctx;
216	return 0;
217	#endif
218	}
219
220	/-******************************************************
221	* Shared internal functions
222	*********************************************************/
223
224	/*! ZSTD_loadDEntropy() :
225	* dict : must point at beginning of a valid zstd dictionary.
226	* @return : size of dictionary header (size of magic number + dict ID + entropy tables) */
227	size_t ZSTD_loadDEntropy(ZSTD_entropyDTables_t* entropy,
228	const void* const dict, size_t const dictSize);
229
230	/*! ZSTD_checkContinuity() :
231	* check if next `dst` follows previous position, where decompression ended.
232	* If yes, do nothing (continue on current segment).
233	* If not, classify previous segment as "external dictionary", and start a new segment.
234	* This function cannot fail. */
235	void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst, size_t dstSize);
236
237
238	#endif /* ZSTD_DECOMPRESS_INTERNAL_H */