// SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause/* * 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. */ /* **************************************************************** Tuning parameters*****************************************************************//*! * HEAPMODE : * Select how default decompression function ZSTD_decompress() allocates its context, * on stack (0), or into heap (1, default; requires malloc()). * Note that functions with explicit context such as ZSTD_decompressDCtx() are unaffected. */#ifndef ZSTD_HEAPMODE# define ZSTD_HEAPMODE 1#endif /*!* LEGACY_SUPPORT :* if set to 1+, ZSTD_decompress() can decode older formats (v0.1+)*/ /*! * MAXWINDOWSIZE_DEFAULT : * maximum window size accepted by DStream __by default__. * Frames requiring more memory will be rejected. * It's possible to set a different limit using ZSTD_DCtx_setMaxWindowSize(). */#ifndef ZSTD_MAXWINDOWSIZE_DEFAULT# define ZSTD_MAXWINDOWSIZE_DEFAULT (((U32)1 << ZSTD_WINDOWLOG_LIMIT_DEFAULT) + 1)#endif /*! * NO_FORWARD_PROGRESS_MAX : * maximum allowed nb of calls to ZSTD_decompressStream() * without any forward progress * (defined as: no byte read from input, and no byte flushed to output) * before triggering an error. */#ifndef ZSTD_NO_FORWARD_PROGRESS_MAX# define ZSTD_NO_FORWARD_PROGRESS_MAX 16#endif /*-******************************************************** Dependencies*********************************************************/#include "../common/zstd_deps.h" /* ZSTD_memcpy, ZSTD_memmove, ZSTD_memset */#include "../common/allocations.h" /* ZSTD_customMalloc, ZSTD_customCalloc, ZSTD_customFree */#include "../common/error_private.h"#include "../common/zstd_internal.h" /* blockProperties_t */#include "../common/mem.h" /* low level memory routines */#include "../common/bits.h" /* ZSTD_highbit32 */#define FSE_STATIC_LINKING_ONLY#include "../common/fse.h"#include "../common/huf.h"#include <linux/xxhash.h> /* xxh64_reset, xxh64_update, xxh64_digest, XXH64 */#include "zstd_decompress_internal.h" /* ZSTD_DCtx */#include "zstd_ddict.h" /* ZSTD_DDictDictContent */#include "zstd_decompress_block.h" /* ZSTD_decompressBlock_internal */ /* *********************************** * Multiple DDicts Hashset internals * *************************************/ #define DDICT_HASHSET_MAX_LOAD_FACTOR_COUNT_MULT 4#define DDICT_HASHSET_MAX_LOAD_FACTOR_SIZE_MULT 3 /* These two constants represent SIZE_MULT/COUNT_MULT load factor without using a float. * Currently, that means a 0.75 load factor. * So, if count * COUNT_MULT / size * SIZE_MULT != 0, then we've exceeded * the load factor of the ddict hash set. */ #define DDICT_HASHSET_TABLE_BASE_SIZE 64#define DDICT_HASHSET_RESIZE_FACTOR 2 /* Hash function to determine starting position of dict insertion within the table * Returns an index between [0, hashSet->ddictPtrTableSize] */static size_t ZSTD_DDictHashSet_getIndex(const ZSTD_DDictHashSet* hashSet, U32 dictID) { const U64 hash = xxh64(&dictID, sizeof(U32), 0); /* DDict ptr table size is a multiple of 2, use size - 1 as mask to get index within [0, hashSet->ddictPtrTableSize) */ return hash & (hashSet->ddictPtrTableSize - 1);} /* Adds DDict to a hashset without resizing it. * If inserting a DDict with a dictID that already exists in the set, replaces the one in the set. * Returns 0 if successful, or a zstd error code if something went wrong. */static size_t ZSTD_DDictHashSet_emplaceDDict(ZSTD_DDictHashSet* hashSet, const ZSTD_DDict* ddict) { const U32 dictID = ZSTD_getDictID_fromDDict(ddict); size_t idx = ZSTD_DDictHashSet_getIndex(hashSet, dictID); const size_t idxRangeMask = hashSet->ddictPtrTableSize - 1; RETURN_ERROR_IF(hashSet->ddictPtrCount == hashSet->ddictPtrTableSize, GENERIC, "Hash set is full!"); DEBUGLOG(4, "Hashed index: for dictID: %u is %zu", dictID, idx); while (hashSet->ddictPtrTable[idx] != NULL) { /* Replace existing ddict if inserting ddict with same dictID */ if (ZSTD_getDictID_fromDDict(hashSet->ddictPtrTable[idx]) == dictID) { DEBUGLOG(4, "DictID already exists, replacing rather than adding"); hashSet->ddictPtrTable[idx] = ddict; return 0; } idx &= idxRangeMask; idx++; } DEBUGLOG(4, "Final idx after probing for dictID %u is: %zu", dictID, idx); hashSet->ddictPtrTable[idx] = ddict; hashSet->ddictPtrCount++; return 0;} /* Expands hash table by factor of DDICT_HASHSET_RESIZE_FACTOR and * rehashes all values, allocates new table, frees old table. * Returns 0 on success, otherwise a zstd error code. */static size_t ZSTD_DDictHashSet_expand(ZSTD_DDictHashSet* hashSet, ZSTD_customMem customMem) { size_t newTableSize = hashSet->ddictPtrTableSize * DDICT_HASHSET_RESIZE_FACTOR; const ZSTD_DDict** newTable = (const ZSTD_DDict**)ZSTD_customCalloc(sizeof(ZSTD_DDict*) * newTableSize, customMem); const ZSTD_DDict** oldTable = hashSet->ddictPtrTable; size_t oldTableSize = hashSet->ddictPtrTableSize; size_t i; DEBUGLOG(4, "Expanding DDict hash table! Old size: %zu new size: %zu", oldTableSize, newTableSize); RETURN_ERROR_IF(!newTable, memory_allocation, "Expanded hashset allocation failed!"); hashSet->ddictPtrTable = newTable; hashSet->ddictPtrTableSize = newTableSize; hashSet->ddictPtrCount = 0; for (i = 0; i < oldTableSize; ++i) { if (oldTable[i] != NULL) { FORWARD_IF_ERROR(ZSTD_DDictHashSet_emplaceDDict(hashSet, oldTable[i]), ""); } } ZSTD_customFree((void*)oldTable, customMem); DEBUGLOG(4, "Finished re-hash"); return 0;} /* Fetches a DDict with the given dictID * Returns the ZSTD_DDict* with the requested dictID. If it doesn't exist, then returns NULL. */static const ZSTD_DDict* ZSTD_DDictHashSet_getDDict(ZSTD_DDictHashSet* hashSet, U32 dictID) { size_t idx = ZSTD_DDictHashSet_getIndex(hashSet, dictID); const size_t idxRangeMask = hashSet->ddictPtrTableSize - 1; DEBUGLOG(4, "Hashed index: for dictID: %u is %zu", dictID, idx); for (;;) { size_t currDictID = ZSTD_getDictID_fromDDict(hashSet->ddictPtrTable[idx]); if (currDictID == dictID || currDictID == 0) { /* currDictID == 0 implies a NULL ddict entry */ break; } else { idx &= idxRangeMask; /* Goes to start of table when we reach the end */ idx++; } } DEBUGLOG(4, "Final idx after probing for dictID %u is: %zu", dictID, idx); return hashSet->ddictPtrTable[idx];} /* Allocates space for and returns a ddict hash set * The hash set's ZSTD_DDict* table has all values automatically set to NULL to begin with. * Returns NULL if allocation failed. */static ZSTD_DDictHashSet* ZSTD_createDDictHashSet(ZSTD_customMem customMem) { ZSTD_DDictHashSet* ret = (ZSTD_DDictHashSet*)ZSTD_customMalloc(sizeof(ZSTD_DDictHashSet), customMem); DEBUGLOG(4, "Allocating new hash set"); if (!ret) return NULL; ret->ddictPtrTable = (const ZSTD_DDict**)ZSTD_customCalloc(DDICT_HASHSET_TABLE_BASE_SIZE * sizeof(ZSTD_DDict*), customMem); if (!ret->ddictPtrTable) { ZSTD_customFree(ret, customMem); return NULL; } ret->ddictPtrTableSize = DDICT_HASHSET_TABLE_BASE_SIZE; ret->ddictPtrCount = 0; return ret;} /* Frees the table of ZSTD_DDict* within a hashset, then frees the hashset itself. * Note: The ZSTD_DDict* within the table are NOT freed. */static void ZSTD_freeDDictHashSet(ZSTD_DDictHashSet* hashSet, ZSTD_customMem customMem) { DEBUGLOG(4, "Freeing ddict hash set"); if (hashSet && hashSet->ddictPtrTable) { ZSTD_customFree((void*)hashSet->ddictPtrTable, customMem); } if (hashSet) { ZSTD_customFree(hashSet, customMem); }} /* Public function: Adds a DDict into the ZSTD_DDictHashSet, possibly triggering a resize of the hash set. * Returns 0 on success, or a ZSTD error. */static size_t ZSTD_DDictHashSet_addDDict(ZSTD_DDictHashSet* hashSet, const ZSTD_DDict* ddict, ZSTD_customMem customMem) { DEBUGLOG(4, "Adding dict ID: %u to hashset with - Count: %zu Tablesize: %zu", ZSTD_getDictID_fromDDict(ddict), hashSet->ddictPtrCount, hashSet->ddictPtrTableSize); if (hashSet->ddictPtrCount * DDICT_HASHSET_MAX_LOAD_FACTOR_COUNT_MULT / hashSet->ddictPtrTableSize * DDICT_HASHSET_MAX_LOAD_FACTOR_SIZE_MULT != 0) { FORWARD_IF_ERROR(ZSTD_DDictHashSet_expand(hashSet, customMem), ""); } FORWARD_IF_ERROR(ZSTD_DDictHashSet_emplaceDDict(hashSet, ddict), ""); return 0;} /*-************************************************************** Context management***************************************************************/size_t ZSTD_sizeof_DCtx (const ZSTD_DCtx* dctx){ if (dctx==NULL) return 0; /* support sizeof NULL */ return sizeof(*dctx) + ZSTD_sizeof_DDict(dctx->ddictLocal) + dctx->inBuffSize + dctx->outBuffSize;} size_t ZSTD_estimateDCtxSize(void) { return sizeof(ZSTD_DCtx); } static size_t ZSTD_startingInputLength(ZSTD_format_e format){ size_t const startingInputLength = ZSTD_FRAMEHEADERSIZE_PREFIX(format); /* only supports formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless */ assert( (format == ZSTD_f_zstd1) || (format == ZSTD_f_zstd1_magicless) ); return startingInputLength;} static void ZSTD_DCtx_resetParameters(ZSTD_DCtx* dctx){ assert(dctx->streamStage == zdss_init); dctx->format = ZSTD_f_zstd1; dctx->maxWindowSize = ZSTD_MAXWINDOWSIZE_DEFAULT; dctx->outBufferMode = ZSTD_bm_buffered; dctx->forceIgnoreChecksum = ZSTD_d_validateChecksum; dctx->refMultipleDDicts = ZSTD_rmd_refSingleDDict; dctx->disableHufAsm = 0; dctx->maxBlockSizeParam = 0;} static void ZSTD_initDCtx_internal(ZSTD_DCtx* dctx){ dctx->staticSize = 0; dctx->ddict = NULL; dctx->ddictLocal = NULL; dctx->dictEnd = NULL; dctx->ddictIsCold = 0; dctx->dictUses = ZSTD_dont_use; dctx->inBuff = NULL; dctx->inBuffSize = 0; dctx->outBuffSize = 0; dctx->streamStage = zdss_init; dctx->noForwardProgress = 0; dctx->oversizedDuration = 0; dctx->isFrameDecompression = 1;#if DYNAMIC_BMI2 dctx->bmi2 = ZSTD_cpuSupportsBmi2();#endif dctx->ddictSet = NULL; ZSTD_DCtx_resetParameters(dctx);#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION dctx->dictContentEndForFuzzing = NULL;#endif} ZSTD_DCtx* ZSTD_initStaticDCtx(void *workspace, size_t workspaceSize){ ZSTD_DCtx* const dctx = (ZSTD_DCtx*) workspace; if ((size_t)workspace & 7) return NULL; /* 8-aligned */ if (workspaceSize < sizeof(ZSTD_DCtx)) return NULL; /* minimum size */ ZSTD_initDCtx_internal(dctx); dctx->staticSize = workspaceSize; dctx->inBuff = (char*)(dctx+1); return dctx;} static ZSTD_DCtx* ZSTD_createDCtx_internal(ZSTD_customMem customMem) { if ((!customMem.customAlloc) ^ (!customMem.customFree)) return NULL; { ZSTD_DCtx* const dctx = (ZSTD_DCtx*)ZSTD_customMalloc(sizeof(*dctx), customMem); if (!dctx) return NULL; dctx->customMem = customMem; ZSTD_initDCtx_internal(dctx); return dctx; }} ZSTD_DCtx* ZSTD_createDCtx_advanced(ZSTD_customMem customMem){ return ZSTD_createDCtx_internal(customMem);} ZSTD_DCtx* ZSTD_createDCtx(void){ DEBUGLOG(3, "ZSTD_createDCtx"); return ZSTD_createDCtx_internal(ZSTD_defaultCMem);} static void ZSTD_clearDict(ZSTD_DCtx* dctx){ ZSTD_freeDDict(dctx->ddictLocal); dctx->ddictLocal = NULL; dctx->ddict = NULL; dctx->dictUses = ZSTD_dont_use;} size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx){ if (dctx==NULL) return 0; /* support free on NULL */ RETURN_ERROR_IF(dctx->staticSize, memory_allocation, "not compatible with static DCtx"); { ZSTD_customMem const cMem = dctx->customMem; ZSTD_clearDict(dctx); ZSTD_customFree(dctx->inBuff, cMem); dctx->inBuff = NULL; if (dctx->ddictSet) { ZSTD_freeDDictHashSet(dctx->ddictSet, cMem); dctx->ddictSet = NULL; } ZSTD_customFree(dctx, cMem); return 0; }} /* no longer useful */void ZSTD_copyDCtx(ZSTD_DCtx* dstDCtx, const ZSTD_DCtx* srcDCtx){ size_t const toCopy = (size_t)((char*)(&dstDCtx->inBuff) - (char*)dstDCtx); ZSTD_memcpy(dstDCtx, srcDCtx, toCopy); /* no need to copy workspace */} /* Given a dctx with a digested frame params, re-selects the correct ZSTD_DDict based on * the requested dict ID from the frame. If there exists a reference to the correct ZSTD_DDict, then * accordingly sets the ddict to be used to decompress the frame. * * If no DDict is found, then no action is taken, and the ZSTD_DCtx::ddict remains as-is. * * ZSTD_d_refMultipleDDicts must be enabled for this function to be called. */static void ZSTD_DCtx_selectFrameDDict(ZSTD_DCtx* dctx) { assert(dctx->refMultipleDDicts && dctx->ddictSet); DEBUGLOG(4, "Adjusting DDict based on requested dict ID from frame"); if (dctx->ddict) { const ZSTD_DDict* frameDDict = ZSTD_DDictHashSet_getDDict(dctx->ddictSet, dctx->fParams.dictID); if (frameDDict) { DEBUGLOG(4, "DDict found!"); ZSTD_clearDict(dctx); dctx->dictID = dctx->fParams.dictID; dctx->ddict = frameDDict; dctx->dictUses = ZSTD_use_indefinitely; } }} /*-************************************************************* * Frame header decoding ***************************************************************/ /*! ZSTD_isFrame() : * Tells if the content of `buffer` starts with a valid Frame Identifier. * Note : Frame Identifier is 4 bytes. If `size < 4`, @return will always be 0. * Note 2 : Legacy Frame Identifiers are considered valid only if Legacy Support is enabled. * Note 3 : Skippable Frame Identifiers are considered valid. */unsigned ZSTD_isFrame(const void* buffer, size_t size){ if (size < ZSTD_FRAMEIDSIZE) return 0; { U32 const magic = MEM_readLE32(buffer); if (magic == ZSTD_MAGICNUMBER) return 1; if ((magic & ZSTD_MAGIC_SKIPPABLE_MASK) == ZSTD_MAGIC_SKIPPABLE_START) return 1; } return 0;} /*! ZSTD_isSkippableFrame() : * Tells if the content of `buffer` starts with a valid Frame Identifier for a skippable frame. * Note : Frame Identifier is 4 bytes. If `size < 4`, @return will always be 0. */unsigned ZSTD_isSkippableFrame(const void* buffer, size_t size){ if (size < ZSTD_FRAMEIDSIZE) return 0; { U32 const magic = MEM_readLE32(buffer); if ((magic & ZSTD_MAGIC_SKIPPABLE_MASK) == ZSTD_MAGIC_SKIPPABLE_START) return 1; } return 0;} /* ZSTD_frameHeaderSize_internal() : * srcSize must be large enough to reach header size fields. * note : only works for formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless. * @return : size of the Frame Header * or an error code, which can be tested with ZSTD_isError() */static size_t ZSTD_frameHeaderSize_internal(const void* src, size_t srcSize, ZSTD_format_e format){ size_t const minInputSize = ZSTD_startingInputLength(format); RETURN_ERROR_IF(srcSize < minInputSize, srcSize_wrong, ""); { BYTE const fhd = ((const BYTE*)src)[minInputSize-1]; U32 const dictID= fhd & 3; U32 const singleSegment = (fhd >> 5) & 1; U32 const fcsId = fhd >> 6; return minInputSize + !singleSegment + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId] + (singleSegment && !fcsId); }} /* ZSTD_frameHeaderSize() : * srcSize must be >= ZSTD_frameHeaderSize_prefix. * @return : size of the Frame Header, * or an error code (if srcSize is too small) */size_t ZSTD_frameHeaderSize(const void* src, size_t srcSize){ return ZSTD_frameHeaderSize_internal(src, srcSize, ZSTD_f_zstd1);} /* ZSTD_getFrameHeader_advanced() : * decode Frame Header, or require larger `srcSize`. * note : only works for formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless * @return : 0, `zfhPtr` is correctly filled, * >0, `srcSize` is too small, value is wanted `srcSize` amount,** or an error code, which can be tested using ZSTD_isError() */size_t ZSTD_getFrameHeader_advanced(ZSTD_FrameHeader* zfhPtr, const void* src, size_t srcSize, ZSTD_format_e format){ const BYTE* ip = (const BYTE*)src; size_t const minInputSize = ZSTD_startingInputLength(format); DEBUGLOG(5, "ZSTD_getFrameHeader_advanced: minInputSize = %zu, srcSize = %zu", minInputSize, srcSize); if (srcSize > 0) { /* note : technically could be considered an assert(), since it's an invalid entry */ RETURN_ERROR_IF(src==NULL, GENERIC, "invalid parameter : src==NULL, but srcSize>0"); } if (srcSize < minInputSize) { if (srcSize > 0 && format != ZSTD_f_zstd1_magicless) { /* when receiving less than @minInputSize bytes, * control these bytes at least correspond to a supported magic number * in order to error out early if they don't. **/ size_t const toCopy = MIN(4, srcSize); unsigned char hbuf[4]; MEM_writeLE32(hbuf, ZSTD_MAGICNUMBER); assert(src != NULL); ZSTD_memcpy(hbuf, src, toCopy); if ( MEM_readLE32(hbuf) != ZSTD_MAGICNUMBER ) { /* not a zstd frame : let's check if it's a skippable frame */ MEM_writeLE32(hbuf, ZSTD_MAGIC_SKIPPABLE_START); ZSTD_memcpy(hbuf, src, toCopy); if ((MEM_readLE32(hbuf) & ZSTD_MAGIC_SKIPPABLE_MASK) != ZSTD_MAGIC_SKIPPABLE_START) { RETURN_ERROR(prefix_unknown, "first bytes don't correspond to any supported magic number"); } } } return minInputSize; } ZSTD_memset(zfhPtr, 0, sizeof(*zfhPtr)); /* not strictly necessary, but static analyzers may not understand that zfhPtr will be read only if return value is zero, since they are 2 different signals */ if ( (format != ZSTD_f_zstd1_magicless) && (MEM_readLE32(src) != ZSTD_MAGICNUMBER) ) { if ((MEM_readLE32(src) & ZSTD_MAGIC_SKIPPABLE_MASK) == ZSTD_MAGIC_SKIPPABLE_START) { /* skippable frame */ if (srcSize < ZSTD_SKIPPABLEHEADERSIZE) return ZSTD_SKIPPABLEHEADERSIZE; /* magic number + frame length */ ZSTD_memset(zfhPtr, 0, sizeof(*zfhPtr)); zfhPtr->frameType = ZSTD_skippableFrame; zfhPtr->dictID = MEM_readLE32(src) - ZSTD_MAGIC_SKIPPABLE_START; zfhPtr->headerSize = ZSTD_SKIPPABLEHEADERSIZE; zfhPtr->frameContentSize = MEM_readLE32((const char *)src + ZSTD_FRAMEIDSIZE); return 0; } RETURN_ERROR(prefix_unknown, ""); } /* ensure there is enough `srcSize` to fully read/decode frame header */ { size_t const fhsize = ZSTD_frameHeaderSize_internal(src, srcSize, format); if (srcSize < fhsize) return fhsize; zfhPtr->headerSize = (U32)fhsize; } { BYTE const fhdByte = ip[minInputSize-1]; size_t pos = minInputSize; U32 const dictIDSizeCode = fhdByte&3; U32 const checksumFlag = (fhdByte>>2)&1; U32 const singleSegment = (fhdByte>>5)&1; U32 const fcsID = fhdByte>>6; U64 windowSize = 0; U32 dictID = 0; U64 frameContentSize = ZSTD_CONTENTSIZE_UNKNOWN; RETURN_ERROR_IF((fhdByte & 0x08) != 0, frameParameter_unsupported, "reserved bits, must be zero"); if (!singleSegment) { BYTE const wlByte = ip[pos++]; U32 const windowLog = (wlByte >> 3) + ZSTD_WINDOWLOG_ABSOLUTEMIN;Lines 1–500 of 2303. Load more
// SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause /* * 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. */ /* *************************************************************** * Tuning parameters *****************************************************************/ /*! * HEAPMODE : * Select how default decompression function ZSTD_decompress() allocates its context, * on stack (0), or into heap (1, default; requires malloc()). * Note that functions with explicit context such as ZSTD_decompressDCtx() are unaffected. */ #ifndef ZSTD_HEAPMODE # define ZSTD_HEAPMODE 1 #endif /*! * LEGACY_SUPPORT : * if set to 1+, ZSTD_decompress() can decode older formats (v0.1+) */ /*! * MAXWINDOWSIZE_DEFAULT : * maximum window size accepted by DStream __by default__. * Frames requiring more memory will be rejected. * It's possible to set a different limit using ZSTD_DCtx_setMaxWindowSize(). */ #ifndef ZSTD_MAXWINDOWSIZE_DEFAULT # define ZSTD_MAXWINDOWSIZE_DEFAULT (((U32)1 << ZSTD_WINDOWLOG_LIMIT_DEFAULT) + 1) #endif /*! * NO_FORWARD_PROGRESS_MAX : * maximum allowed nb of calls to ZSTD_decompressStream() * without any forward progress * (defined as: no byte read from input, and no byte flushed to output) * before triggering an error. */ #ifndef ZSTD_NO_FORWARD_PROGRESS_MAX # define ZSTD_NO_FORWARD_PROGRESS_MAX 16 #endif /*-******************************************************* * Dependencies *********************************************************/ #include "../common/zstd_deps.h" /* ZSTD_memcpy, ZSTD_memmove, ZSTD_memset */ #include "../common/allocations.h" /* ZSTD_customMalloc, ZSTD_customCalloc, ZSTD_customFree */ #include "../common/error_private.h" #include "../common/zstd_internal.h" /* blockProperties_t */ #include "../common/mem.h" /* low level memory routines */ #include "../common/bits.h" /* ZSTD_highbit32 */ #define FSE_STATIC_LINKING_ONLY #include "../common/fse.h" #include "../common/huf.h" #include <linux/xxhash.h> /* xxh64_reset, xxh64_update, xxh64_digest, XXH64 */ #include "zstd_decompress_internal.h" /* ZSTD_DCtx */ #include "zstd_ddict.h" /* ZSTD_DDictDictContent */ #include "zstd_decompress_block.h" /* ZSTD_decompressBlock_internal */ /* *********************************** * Multiple DDicts Hashset internals * *************************************/ #define DDICT_HASHSET_MAX_LOAD_FACTOR_COUNT_MULT 4 #define DDICT_HASHSET_MAX_LOAD_FACTOR_SIZE_MULT 3 /* These two constants represent SIZE_MULT/COUNT_MULT load factor without using a float. * Currently, that means a 0.75 load factor. * So, if count * COUNT_MULT / size * SIZE_MULT != 0, then we've exceeded * the load factor of the ddict hash set. */ #define DDICT_HASHSET_TABLE_BASE_SIZE 64 #define DDICT_HASHSET_RESIZE_FACTOR 2 /* Hash function to determine starting position of dict insertion within the table * Returns an index between [0, hashSet->ddictPtrTableSize] */ static size_t ZSTD_DDictHashSet_getIndex(const ZSTD_DDictHashSet* hashSet, U32 dictID) { const U64 hash = xxh64(&dictID, sizeof(U32), 0); /* DDict ptr table size is a multiple of 2, use size - 1 as mask to get index within [0, hashSet->ddictPtrTableSize) */ return hash & (hashSet->ddictPtrTableSize - 1); } /* Adds DDict to a hashset without resizing it. * If inserting a DDict with a dictID that already exists in the set, replaces the one in the set. * Returns 0 if successful, or a zstd error code if something went wrong. */ static size_t ZSTD_DDictHashSet_emplaceDDict(ZSTD_DDictHashSet* hashSet, const ZSTD_DDict* ddict) { const U32 dictID = ZSTD_getDictID_fromDDict(ddict); size_t idx = ZSTD_DDictHashSet_getIndex(hashSet, dictID); const size_t idxRangeMask = hashSet->ddictPtrTableSize - 1; RETURN_ERROR_IF(hashSet->ddictPtrCount == hashSet->ddictPtrTableSize, GENERIC, "Hash set is full!"); DEBUGLOG(4, "Hashed index: for dictID: %u is %zu", dictID, idx); while (hashSet->ddictPtrTable[idx] != NULL) { /* Replace existing ddict if inserting ddict with same dictID */ if (ZSTD_getDictID_fromDDict(hashSet->ddictPtrTable[idx]) == dictID) { DEBUGLOG(4, "DictID already exists, replacing rather than adding"); hashSet->ddictPtrTable[idx] = ddict; return 0; } idx &= idxRangeMask; idx++; } DEBUGLOG(4, "Final idx after probing for dictID %u is: %zu", dictID, idx); hashSet->ddictPtrTable[idx] = ddict; hashSet->ddictPtrCount++; return 0; } /* Expands hash table by factor of DDICT_HASHSET_RESIZE_FACTOR and * rehashes all values, allocates new table, frees old table. * Returns 0 on success, otherwise a zstd error code. */ static size_t ZSTD_DDictHashSet_expand(ZSTD_DDictHashSet* hashSet, ZSTD_customMem customMem) { size_t newTableSize = hashSet->ddictPtrTableSize * DDICT_HASHSET_RESIZE_FACTOR; const ZSTD_DDict** newTable = (const ZSTD_DDict**)ZSTD_customCalloc(sizeof(ZSTD_DDict*) * newTableSize, customMem); const ZSTD_DDict** oldTable = hashSet->ddictPtrTable; size_t oldTableSize = hashSet->ddictPtrTableSize; size_t i; DEBUGLOG(4, "Expanding DDict hash table! Old size: %zu new size: %zu", oldTableSize, newTableSize); RETURN_ERROR_IF(!newTable, memory_allocation, "Expanded hashset allocation failed!"); hashSet->ddictPtrTable = newTable; hashSet->ddictPtrTableSize = newTableSize; hashSet->ddictPtrCount = 0; for (i = 0; i < oldTableSize; ++i) { if (oldTable[i] != NULL) { FORWARD_IF_ERROR(ZSTD_DDictHashSet_emplaceDDict(hashSet, oldTable[i]), ""); } } ZSTD_customFree((void*)oldTable, customMem); DEBUGLOG(4, "Finished re-hash"); return 0; } /* Fetches a DDict with the given dictID * Returns the ZSTD_DDict* with the requested dictID. If it doesn't exist, then returns NULL. */ static const ZSTD_DDict* ZSTD_DDictHashSet_getDDict(ZSTD_DDictHashSet* hashSet, U32 dictID) { size_t idx = ZSTD_DDictHashSet_getIndex(hashSet, dictID); const size_t idxRangeMask = hashSet->ddictPtrTableSize - 1; DEBUGLOG(4, "Hashed index: for dictID: %u is %zu", dictID, idx); for (;;) { size_t currDictID = ZSTD_getDictID_fromDDict(hashSet->ddictPtrTable[idx]); if (currDictID == dictID || currDictID == 0) { /* currDictID == 0 implies a NULL ddict entry */ break; } else { idx &= idxRangeMask; /* Goes to start of table when we reach the end */ idx++; } } DEBUGLOG(4, "Final idx after probing for dictID %u is: %zu", dictID, idx); return hashSet->ddictPtrTable[idx]; } /* Allocates space for and returns a ddict hash set * The hash set's ZSTD_DDict* table has all values automatically set to NULL to begin with. * Returns NULL if allocation failed. */ static ZSTD_DDictHashSet* ZSTD_createDDictHashSet(ZSTD_customMem customMem) { ZSTD_DDictHashSet* ret = (ZSTD_DDictHashSet*)ZSTD_customMalloc(sizeof(ZSTD_DDictHashSet), customMem); DEBUGLOG(4, "Allocating new hash set"); if (!ret) return NULL; ret->ddictPtrTable = (const ZSTD_DDict**)ZSTD_customCalloc(DDICT_HASHSET_TABLE_BASE_SIZE * sizeof(ZSTD_DDict*), customMem); if (!ret->ddictPtrTable) { ZSTD_customFree(ret, customMem); return NULL; } ret->ddictPtrTableSize = DDICT_HASHSET_TABLE_BASE_SIZE; ret->ddictPtrCount = 0; return ret; } /* Frees the table of ZSTD_DDict* within a hashset, then frees the hashset itself. * Note: The ZSTD_DDict* within the table are NOT freed. */ static void ZSTD_freeDDictHashSet(ZSTD_DDictHashSet* hashSet, ZSTD_customMem customMem) { DEBUGLOG(4, "Freeing ddict hash set"); if (hashSet && hashSet->ddictPtrTable) { ZSTD_customFree((void*)hashSet->ddictPtrTable, customMem); } if (hashSet) { ZSTD_customFree(hashSet, customMem); } } /* Public function: Adds a DDict into the ZSTD_DDictHashSet, possibly triggering a resize of the hash set. * Returns 0 on success, or a ZSTD error. */ static size_t ZSTD_DDictHashSet_addDDict(ZSTD_DDictHashSet* hashSet, const ZSTD_DDict* ddict, ZSTD_customMem customMem) { DEBUGLOG(4, "Adding dict ID: %u to hashset with - Count: %zu Tablesize: %zu", ZSTD_getDictID_fromDDict(ddict), hashSet->ddictPtrCount, hashSet->ddictPtrTableSize); if (hashSet->ddictPtrCount * DDICT_HASHSET_MAX_LOAD_FACTOR_COUNT_MULT / hashSet->ddictPtrTableSize * DDICT_HASHSET_MAX_LOAD_FACTOR_SIZE_MULT != 0) { FORWARD_IF_ERROR(ZSTD_DDictHashSet_expand(hashSet, customMem), ""); } FORWARD_IF_ERROR(ZSTD_DDictHashSet_emplaceDDict(hashSet, ddict), ""); return 0; } /*-************************************************************* * Context management ***************************************************************/ size_t ZSTD_sizeof_DCtx (const ZSTD_DCtx* dctx) { if (dctx==NULL) return 0; /* support sizeof NULL */ return sizeof(*dctx) + ZSTD_sizeof_DDict(dctx->ddictLocal) + dctx->inBuffSize + dctx->outBuffSize; } size_t ZSTD_estimateDCtxSize(void) { return sizeof(ZSTD_DCtx); } static size_t ZSTD_startingInputLength(ZSTD_format_e format) { size_t const startingInputLength = ZSTD_FRAMEHEADERSIZE_PREFIX(format); /* only supports formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless */ assert( (format == ZSTD_f_zstd1) || (format == ZSTD_f_zstd1_magicless) ); return startingInputLength; } static void ZSTD_DCtx_resetParameters(ZSTD_DCtx* dctx) { assert(dctx->streamStage == zdss_init); dctx->format = ZSTD_f_zstd1; dctx->maxWindowSize = ZSTD_MAXWINDOWSIZE_DEFAULT; dctx->outBufferMode = ZSTD_bm_buffered; dctx->forceIgnoreChecksum = ZSTD_d_validateChecksum; dctx->refMultipleDDicts = ZSTD_rmd_refSingleDDict; dctx->disableHufAsm = 0; dctx->maxBlockSizeParam = 0; } static void ZSTD_initDCtx_internal(ZSTD_DCtx* dctx) { dctx->staticSize = 0; dctx->ddict = NULL; dctx->ddictLocal = NULL; dctx->dictEnd = NULL; dctx->ddictIsCold = 0; dctx->dictUses = ZSTD_dont_use; dctx->inBuff = NULL; dctx->inBuffSize = 0; dctx->outBuffSize = 0; dctx->streamStage = zdss_init; dctx->noForwardProgress = 0; dctx->oversizedDuration = 0; dctx->isFrameDecompression = 1; #if DYNAMIC_BMI2 dctx->bmi2 = ZSTD_cpuSupportsBmi2(); #endif dctx->ddictSet = NULL; ZSTD_DCtx_resetParameters(dctx); #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION dctx->dictContentEndForFuzzing = NULL; #endif } ZSTD_DCtx* ZSTD_initStaticDCtx(void *workspace, size_t workspaceSize) { ZSTD_DCtx* const dctx = (ZSTD_DCtx*) workspace; if ((size_t)workspace & 7) return NULL; /* 8-aligned */ if (workspaceSize < sizeof(ZSTD_DCtx)) return NULL; /* minimum size */ ZSTD_initDCtx_internal(dctx); dctx->staticSize = workspaceSize; dctx->inBuff = (char*)(dctx+1); return dctx; } static ZSTD_DCtx* ZSTD_createDCtx_internal(ZSTD_customMem customMem) { if ((!customMem.customAlloc) ^ (!customMem.customFree)) return NULL; { ZSTD_DCtx* const dctx = (ZSTD_DCtx*)ZSTD_customMalloc(sizeof(*dctx), customMem); if (!dctx) return NULL; dctx->customMem = customMem; ZSTD_initDCtx_internal(dctx); return dctx; } } ZSTD_DCtx* ZSTD_createDCtx_advanced(ZSTD_customMem customMem) { return ZSTD_createDCtx_internal(customMem); } ZSTD_DCtx* ZSTD_createDCtx(void) { DEBUGLOG(3, "ZSTD_createDCtx"); return ZSTD_createDCtx_internal(ZSTD_defaultCMem); } static void ZSTD_clearDict(ZSTD_DCtx* dctx) { ZSTD_freeDDict(dctx->ddictLocal); dctx->ddictLocal = NULL; dctx->ddict = NULL; dctx->dictUses = ZSTD_dont_use; } size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx) { if (dctx==NULL) return 0; /* support free on NULL */ RETURN_ERROR_IF(dctx->staticSize, memory_allocation, "not compatible with static DCtx"); { ZSTD_customMem const cMem = dctx->customMem; ZSTD_clearDict(dctx); ZSTD_customFree(dctx->inBuff, cMem); dctx->inBuff = NULL; if (dctx->ddictSet) { ZSTD_freeDDictHashSet(dctx->ddictSet, cMem); dctx->ddictSet = NULL; } ZSTD_customFree(dctx, cMem); return 0; } } /* no longer useful */ void ZSTD_copyDCtx(ZSTD_DCtx* dstDCtx, const ZSTD_DCtx* srcDCtx) { size_t const toCopy = (size_t)((char*)(&dstDCtx->inBuff) - (char*)dstDCtx); ZSTD_memcpy(dstDCtx, srcDCtx, toCopy); /* no need to copy workspace */ } /* Given a dctx with a digested frame params, re-selects the correct ZSTD_DDict based on * the requested dict ID from the frame. If there exists a reference to the correct ZSTD_DDict, then * accordingly sets the ddict to be used to decompress the frame. * * If no DDict is found, then no action is taken, and the ZSTD_DCtx::ddict remains as-is. * * ZSTD_d_refMultipleDDicts must be enabled for this function to be called. */ static void ZSTD_DCtx_selectFrameDDict(ZSTD_DCtx* dctx) { assert(dctx->refMultipleDDicts && dctx->ddictSet); DEBUGLOG(4, "Adjusting DDict based on requested dict ID from frame"); if (dctx->ddict) { const ZSTD_DDict* frameDDict = ZSTD_DDictHashSet_getDDict(dctx->ddictSet, dctx->fParams.dictID); if (frameDDict) { DEBUGLOG(4, "DDict found!"); ZSTD_clearDict(dctx); dctx->dictID = dctx->fParams.dictID; dctx->ddict = frameDDict; dctx->dictUses = ZSTD_use_indefinitely; } } } /*-************************************************************* * Frame header decoding ***************************************************************/ /*! ZSTD_isFrame() : * Tells if the content of `buffer` starts with a valid Frame Identifier. * Note : Frame Identifier is 4 bytes. If `size < 4`, @return will always be 0. * Note 2 : Legacy Frame Identifiers are considered valid only if Legacy Support is enabled. * Note 3 : Skippable Frame Identifiers are considered valid. */ unsigned ZSTD_isFrame(const void* buffer, size_t size) { if (size < ZSTD_FRAMEIDSIZE) return 0; { U32 const magic = MEM_readLE32(buffer); if (magic == ZSTD_MAGICNUMBER) return 1; if ((magic & ZSTD_MAGIC_SKIPPABLE_MASK) == ZSTD_MAGIC_SKIPPABLE_START) return 1; } return 0; } /*! ZSTD_isSkippableFrame() : * Tells if the content of `buffer` starts with a valid Frame Identifier for a skippable frame. * Note : Frame Identifier is 4 bytes. If `size < 4`, @return will always be 0. */ unsigned ZSTD_isSkippableFrame(const void* buffer, size_t size) { if (size < ZSTD_FRAMEIDSIZE) return 0; { U32 const magic = MEM_readLE32(buffer); if ((magic & ZSTD_MAGIC_SKIPPABLE_MASK) == ZSTD_MAGIC_SKIPPABLE_START) return 1; } return 0; } /* ZSTD_frameHeaderSize_internal() : * srcSize must be large enough to reach header size fields. * note : only works for formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless. * @return : size of the Frame Header * or an error code, which can be tested with ZSTD_isError() */ static size_t ZSTD_frameHeaderSize_internal(const void* src, size_t srcSize, ZSTD_format_e format) { size_t const minInputSize = ZSTD_startingInputLength(format); RETURN_ERROR_IF(srcSize < minInputSize, srcSize_wrong, ""); { BYTE const fhd = ((const BYTE*)src)[minInputSize-1]; U32 const dictID= fhd & 3; U32 const singleSegment = (fhd >> 5) & 1; U32 const fcsId = fhd >> 6; return minInputSize + !singleSegment + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId] + (singleSegment && !fcsId); } } /* ZSTD_frameHeaderSize() : * srcSize must be >= ZSTD_frameHeaderSize_prefix. * @return : size of the Frame Header, * or an error code (if srcSize is too small) */ size_t ZSTD_frameHeaderSize(const void* src, size_t srcSize) { return ZSTD_frameHeaderSize_internal(src, srcSize, ZSTD_f_zstd1); } /* ZSTD_getFrameHeader_advanced() : * decode Frame Header, or require larger `srcSize`. * note : only works for formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless * @return : 0, `zfhPtr` is correctly filled, * >0, `srcSize` is too small, value is wanted `srcSize` amount, ** or an error code, which can be tested using ZSTD_isError() */ size_t ZSTD_getFrameHeader_advanced(ZSTD_FrameHeader* zfhPtr, const void* src, size_t srcSize, ZSTD_format_e format) { const BYTE* ip = (const BYTE*)src; size_t const minInputSize = ZSTD_startingInputLength(format); DEBUGLOG(5, "ZSTD_getFrameHeader_advanced: minInputSize = %zu, srcSize = %zu", minInputSize, srcSize); if (srcSize > 0) { /* note : technically could be considered an assert(), since it's an invalid entry */ RETURN_ERROR_IF(src==NULL, GENERIC, "invalid parameter : src==NULL, but srcSize>0"); } if (srcSize < minInputSize) { if (srcSize > 0 && format != ZSTD_f_zstd1_magicless) { /* when receiving less than @minInputSize bytes, * control these bytes at least correspond to a supported magic number * in order to error out early if they don't. **/ size_t const toCopy = MIN(4, srcSize); unsigned char hbuf[4]; MEM_writeLE32(hbuf, ZSTD_MAGICNUMBER); assert(src != NULL); ZSTD_memcpy(hbuf, src, toCopy); if ( MEM_readLE32(hbuf) != ZSTD_MAGICNUMBER ) { /* not a zstd frame : let's check if it's a skippable frame */ MEM_writeLE32(hbuf, ZSTD_MAGIC_SKIPPABLE_START); ZSTD_memcpy(hbuf, src, toCopy); if ((MEM_readLE32(hbuf) & ZSTD_MAGIC_SKIPPABLE_MASK) != ZSTD_MAGIC_SKIPPABLE_START) { RETURN_ERROR(prefix_unknown, "first bytes don't correspond to any supported magic number"); } } } return minInputSize; } ZSTD_memset(zfhPtr, 0, sizeof(*zfhPtr)); /* not strictly necessary, but static analyzers may not understand that zfhPtr will be read only if return value is zero, since they are 2 different signals */ if ( (format != ZSTD_f_zstd1_magicless) && (MEM_readLE32(src) != ZSTD_MAGICNUMBER) ) { if ((MEM_readLE32(src) & ZSTD_MAGIC_SKIPPABLE_MASK) == ZSTD_MAGIC_SKIPPABLE_START) { /* skippable frame */ if (srcSize < ZSTD_SKIPPABLEHEADERSIZE) return ZSTD_SKIPPABLEHEADERSIZE; /* magic number + frame length */ ZSTD_memset(zfhPtr, 0, sizeof(*zfhPtr)); zfhPtr->frameType = ZSTD_skippableFrame; zfhPtr->dictID = MEM_readLE32(src) - ZSTD_MAGIC_SKIPPABLE_START; zfhPtr->headerSize = ZSTD_SKIPPABLEHEADERSIZE; zfhPtr->frameContentSize = MEM_readLE32((const char *)src + ZSTD_FRAMEIDSIZE); return 0; } RETURN_ERROR(prefix_unknown, ""); } /* ensure there is enough `srcSize` to fully read/decode frame header */ { size_t const fhsize = ZSTD_frameHeaderSize_internal(src, srcSize, format); if (srcSize < fhsize) return fhsize; zfhPtr->headerSize = (U32)fhsize; } { BYTE const fhdByte = ip[minInputSize-1]; size_t pos = minInputSize; U32 const dictIDSizeCode = fhdByte&3; U32 const checksumFlag = (fhdByte>>2)&1; U32 const singleSegment = (fhdByte>>5)&1; U32 const fcsID = fhdByte>>6; U64 windowSize = 0; U32 dictID = 0; U64 frameContentSize = ZSTD_CONTENTSIZE_UNKNOWN; RETURN_ERROR_IF((fhdByte & 0x08) != 0, frameParameter_unsupported, "reserved bits, must be zero"); if (!singleSegment) { BYTE const wlByte = ip[pos++]; U32 const windowLog = (wlByte >> 3) + ZSTD_WINDOWLOG_ABSOLUTEMIN;