[linux-block.git] / lib / zstd / decompress / zstd_decompress_internal.h

/*
 * Copyright (c) Yann Collet, Facebook, Inc.
 * 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))

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(HufLog)];  /* 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;
    struct xxh64_state 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) */

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