/* * 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 … #endif /*! * LEGACY_SUPPORT : * if set to 1+, ZSTD_decompress() can decode older formats (v0.1+) */ #ifndef ZSTD_LEGACY_SUPPORT #define ZSTD_LEGACY_SUPPORT … #endif /*! * 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 … #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 … #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 "../common/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 */ #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1) # include "../legacy/zstd_legacy.h" #endif /************************************* * Multiple DDicts Hashset internals * *************************************/ #define DDICT_HASHSET_MAX_LOAD_FACTOR_COUNT_MULT … #define DDICT_HASHSET_MAX_LOAD_FACTOR_SIZE_MULT … #define DDICT_HASHSET_TABLE_BASE_SIZE … #define DDICT_HASHSET_RESIZE_FACTOR … /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /*-************************************************************* * Context management ***************************************************************/ size_t ZSTD_sizeof_DCtx (const ZSTD_DCtx* dctx) { … } size_t ZSTD_estimateDCtxSize(void) { … } static size_t ZSTD_startingInputLength(ZSTD_format_e format) { … } static void ZSTD_DCtx_resetParameters(ZSTD_DCtx* dctx) { … } static void ZSTD_initDCtx_internal(ZSTD_DCtx* dctx) { … } ZSTD_DCtx* ZSTD_initStaticDCtx(void *workspace, size_t workspaceSize) { … } static ZSTD_DCtx* ZSTD_createDCtx_internal(ZSTD_customMem customMem) { … } ZSTD_DCtx* ZSTD_createDCtx_advanced(ZSTD_customMem customMem) { … } ZSTD_DCtx* ZSTD_createDCtx(void) { … } static void ZSTD_clearDict(ZSTD_DCtx* dctx) { … } size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx) { … } /* no longer useful */ void ZSTD_copyDCtx(ZSTD_DCtx* dstDCtx, const ZSTD_DCtx* srcDCtx) { … } /* 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) { … } /*-************************************************************* * 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) { … } /*! 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) { … } /** 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) { … } /** 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) { … } /** 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) { … } /** ZSTD_getFrameHeader() : * decode Frame Header, or require larger `srcSize`. * note : this function does not consume input, it only reads it. * @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(ZSTD_frameHeader* zfhPtr, const void* src, size_t srcSize) { … } /** ZSTD_getFrameContentSize() : * compatible with legacy mode * @return : decompressed size of the single frame pointed to be `src` if known, otherwise * - ZSTD_CONTENTSIZE_UNKNOWN if the size cannot be determined * - ZSTD_CONTENTSIZE_ERROR if an error occurred (e.g. invalid magic number, srcSize too small) */ unsigned long long ZSTD_getFrameContentSize(const void *src, size_t srcSize) { … } static size_t readSkippableFrameSize(void const* src, size_t srcSize) { … } /*! ZSTD_readSkippableFrame() : * Retrieves content of a skippable frame, and writes it to dst buffer. * * The parameter magicVariant will receive the magicVariant that was supplied when the frame was written, * i.e. magicNumber - ZSTD_MAGIC_SKIPPABLE_START. This can be NULL if the caller is not interested * in the magicVariant. * * Returns an error if destination buffer is not large enough, or if this is not a valid skippable frame. * * @return : number of bytes written or a ZSTD error. */ size_t ZSTD_readSkippableFrame(void* dst, size_t dstCapacity, unsigned* magicVariant, /* optional, can be NULL */ const void* src, size_t srcSize) { … } /** ZSTD_findDecompressedSize() : * `srcSize` must be the exact length of some number of ZSTD compressed and/or * skippable frames * note: compatible with legacy mode * @return : decompressed size of the frames contained */ unsigned long long ZSTD_findDecompressedSize(const void* src, size_t srcSize) { … } /** ZSTD_getDecompressedSize() : * compatible with legacy mode * @return : decompressed size if known, 0 otherwise note : 0 can mean any of the following : - frame content is empty - decompressed size field is not present in frame header - frame header unknown / not supported - frame header not complete (`srcSize` too small) */ unsigned long long ZSTD_getDecompressedSize(const void* src, size_t srcSize) { … } /** ZSTD_decodeFrameHeader() : * `headerSize` must be the size provided by ZSTD_frameHeaderSize(). * If multiple DDict references are enabled, also will choose the correct DDict to use. * @return : 0 if success, or an error code, which can be tested using ZSTD_isError() */ static size_t ZSTD_decodeFrameHeader(ZSTD_DCtx* dctx, const void* src, size_t headerSize) { … } static ZSTD_frameSizeInfo ZSTD_errorFrameSizeInfo(size_t ret) { … } static ZSTD_frameSizeInfo ZSTD_findFrameSizeInfo(const void* src, size_t srcSize, ZSTD_format_e format) { … } static size_t ZSTD_findFrameCompressedSize_advanced(const void *src, size_t srcSize, ZSTD_format_e format) { … } /** ZSTD_findFrameCompressedSize() : * See docs in zstd.h * Note: compatible with legacy mode */ size_t ZSTD_findFrameCompressedSize(const void *src, size_t srcSize) { … } /** ZSTD_decompressBound() : * compatible with legacy mode * `src` must point to the start of a ZSTD frame or a skippable frame * `srcSize` must be at least as large as the frame contained * @return : the maximum decompressed size of the compressed source */ unsigned long long ZSTD_decompressBound(const void* src, size_t srcSize) { … } size_t ZSTD_decompressionMargin(void const* src, size_t srcSize) { … } /*-************************************************************* * Frame decoding ***************************************************************/ /** ZSTD_insertBlock() : * insert `src` block into `dctx` history. Useful to track uncompressed blocks. */ size_t ZSTD_insertBlock(ZSTD_DCtx* dctx, const void* blockStart, size_t blockSize) { … } static size_t ZSTD_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize) { … } static size_t ZSTD_setRleBlock(void* dst, size_t dstCapacity, BYTE b, size_t regenSize) { … } static void ZSTD_DCtx_trace_end(ZSTD_DCtx const* dctx, U64 uncompressedSize, U64 compressedSize, unsigned streaming) { … } /*! ZSTD_decompressFrame() : * @dctx must be properly initialized * will update *srcPtr and *srcSizePtr, * to make *srcPtr progress by one frame. */ static size_t ZSTD_decompressFrame(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void** srcPtr, size_t *srcSizePtr) { … } static ZSTD_ALLOW_POINTER_OVERFLOW_ATTR size_t ZSTD_decompressMultiFrame(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, const void* dict, size_t dictSize, const ZSTD_DDict* ddict) { … } size_t ZSTD_decompress_usingDict(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, const void* dict, size_t dictSize) { … } static ZSTD_DDict const* ZSTD_getDDict(ZSTD_DCtx* dctx) { … } size_t ZSTD_decompressDCtx(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize) { … } size_t ZSTD_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize) { … } /*-************************************** * Advanced Streaming Decompression API * Bufferless and synchronous ****************************************/ size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx) { … } /** * Similar to ZSTD_nextSrcSizeToDecompress(), but when a block input can be streamed, we * allow taking a partial block as the input. Currently only raw uncompressed blocks can * be streamed. * * For blocks that can be streamed, this allows us to reduce the latency until we produce * output, and avoid copying the input. * * @param inputSize - The total amount of input that the caller currently has. */ static size_t ZSTD_nextSrcSizeToDecompressWithInputSize(ZSTD_DCtx* dctx, size_t inputSize) { … } ZSTD_nextInputType_e ZSTD_nextInputType(ZSTD_DCtx* dctx) { … } static int ZSTD_isSkipFrame(ZSTD_DCtx* dctx) { … } /** ZSTD_decompressContinue() : * srcSize : must be the exact nb of bytes expected (see ZSTD_nextSrcSizeToDecompress()) * @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity) * or an error code, which can be tested using ZSTD_isError() */ size_t ZSTD_decompressContinue(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize) { … } static size_t ZSTD_refDictContent(ZSTD_DCtx* dctx, const void* dict, size_t dictSize) { … } /*! ZSTD_loadDEntropy() : * dict : must point at beginning of a valid zstd dictionary. * @return : size of entropy tables read */ size_t ZSTD_loadDEntropy(ZSTD_entropyDTables_t* entropy, const void* const dict, size_t const dictSize) { … } static size_t ZSTD_decompress_insertDictionary(ZSTD_DCtx* dctx, const void* dict, size_t dictSize) { … } size_t ZSTD_decompressBegin(ZSTD_DCtx* dctx) { … } size_t ZSTD_decompressBegin_usingDict(ZSTD_DCtx* dctx, const void* dict, size_t dictSize) { … } /* ====== ZSTD_DDict ====== */ size_t ZSTD_decompressBegin_usingDDict(ZSTD_DCtx* dctx, const ZSTD_DDict* ddict) { … } /*! ZSTD_getDictID_fromDict() : * Provides the dictID stored within dictionary. * if @return == 0, the dictionary is not conformant with Zstandard specification. * It can still be loaded, but as a content-only dictionary. */ unsigned ZSTD_getDictID_fromDict(const void* dict, size_t dictSize) { … } /*! ZSTD_getDictID_fromFrame() : * Provides the dictID required to decompress frame stored within `src`. * If @return == 0, the dictID could not be decoded. * This could for one of the following reasons : * - The frame does not require a dictionary (most common case). * - The frame was built with dictID intentionally removed. * Needed dictionary is a hidden piece of information. * Note : this use case also happens when using a non-conformant dictionary. * - `srcSize` is too small, and as a result, frame header could not be decoded. * Note : possible if `srcSize < ZSTD_FRAMEHEADERSIZE_MAX`. * - This is not a Zstandard frame. * When identifying the exact failure cause, it's possible to use * ZSTD_getFrameHeader(), which will provide a more precise error code. */ unsigned ZSTD_getDictID_fromFrame(const void* src, size_t srcSize) { … } /*! ZSTD_decompress_usingDDict() : * Decompression using a pre-digested Dictionary * Use dictionary without significant overhead. */ size_t ZSTD_decompress_usingDDict(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, const ZSTD_DDict* ddict) { … } /*===================================== * Streaming decompression *====================================*/ ZSTD_DStream* ZSTD_createDStream(void) { … } ZSTD_DStream* ZSTD_initStaticDStream(void *workspace, size_t workspaceSize) { … } ZSTD_DStream* ZSTD_createDStream_advanced(ZSTD_customMem customMem) { … } size_t ZSTD_freeDStream(ZSTD_DStream* zds) { … } /* *** Initialization *** */ size_t ZSTD_DStreamInSize(void) { … } size_t ZSTD_DStreamOutSize(void) { … } size_t ZSTD_DCtx_loadDictionary_advanced(ZSTD_DCtx* dctx, const void* dict, size_t dictSize, ZSTD_dictLoadMethod_e dictLoadMethod, ZSTD_dictContentType_e dictContentType) { … } size_t ZSTD_DCtx_loadDictionary_byReference(ZSTD_DCtx* dctx, const void* dict, size_t dictSize) { … } size_t ZSTD_DCtx_loadDictionary(ZSTD_DCtx* dctx, const void* dict, size_t dictSize) { … } size_t ZSTD_DCtx_refPrefix_advanced(ZSTD_DCtx* dctx, const void* prefix, size_t prefixSize, ZSTD_dictContentType_e dictContentType) { … } size_t ZSTD_DCtx_refPrefix(ZSTD_DCtx* dctx, const void* prefix, size_t prefixSize) { … } /* ZSTD_initDStream_usingDict() : * return : expected size, aka ZSTD_startingInputLength(). * this function cannot fail */ size_t ZSTD_initDStream_usingDict(ZSTD_DStream* zds, const void* dict, size_t dictSize) { … } /* note : this variant can't fail */ size_t ZSTD_initDStream(ZSTD_DStream* zds) { … } /* ZSTD_initDStream_usingDDict() : * ddict will just be referenced, and must outlive decompression session * this function cannot fail */ size_t ZSTD_initDStream_usingDDict(ZSTD_DStream* dctx, const ZSTD_DDict* ddict) { … } /* ZSTD_resetDStream() : * return : expected size, aka ZSTD_startingInputLength(). * this function cannot fail */ size_t ZSTD_resetDStream(ZSTD_DStream* dctx) { … } size_t ZSTD_DCtx_refDDict(ZSTD_DCtx* dctx, const ZSTD_DDict* ddict) { … } /* ZSTD_DCtx_setMaxWindowSize() : * note : no direct equivalence in ZSTD_DCtx_setParameter, * since this version sets windowSize, and the other sets windowLog */ size_t ZSTD_DCtx_setMaxWindowSize(ZSTD_DCtx* dctx, size_t maxWindowSize) { … } size_t ZSTD_DCtx_setFormat(ZSTD_DCtx* dctx, ZSTD_format_e format) { … } ZSTD_bounds ZSTD_dParam_getBounds(ZSTD_dParameter dParam) { … } /* ZSTD_dParam_withinBounds: * @return 1 if value is within dParam bounds, * 0 otherwise */ static int ZSTD_dParam_withinBounds(ZSTD_dParameter dParam, int value) { … } #define CHECK_DBOUNDS(p,v) … size_t ZSTD_DCtx_getParameter(ZSTD_DCtx* dctx, ZSTD_dParameter param, int* value) { … } size_t ZSTD_DCtx_setParameter(ZSTD_DCtx* dctx, ZSTD_dParameter dParam, int value) { … } size_t ZSTD_DCtx_reset(ZSTD_DCtx* dctx, ZSTD_ResetDirective reset) { … } size_t ZSTD_sizeof_DStream(const ZSTD_DStream* dctx) { … } static size_t ZSTD_decodingBufferSize_internal(unsigned long long windowSize, unsigned long long frameContentSize, size_t blockSizeMax) { … } size_t ZSTD_decodingBufferSize_min(unsigned long long windowSize, unsigned long long frameContentSize) { … } size_t ZSTD_estimateDStreamSize(size_t windowSize) { … } size_t ZSTD_estimateDStreamSize_fromFrame(const void* src, size_t srcSize) { … } /* ***** Decompression ***** */ static int ZSTD_DCtx_isOverflow(ZSTD_DStream* zds, size_t const neededInBuffSize, size_t const neededOutBuffSize) { … } static void ZSTD_DCtx_updateOversizedDuration(ZSTD_DStream* zds, size_t const neededInBuffSize, size_t const neededOutBuffSize) { … } static int ZSTD_DCtx_isOversizedTooLong(ZSTD_DStream* zds) { … } /* Checks that the output buffer hasn't changed if ZSTD_obm_stable is used. */ static size_t ZSTD_checkOutBuffer(ZSTD_DStream const* zds, ZSTD_outBuffer const* output) { … } /* Calls ZSTD_decompressContinue() with the right parameters for ZSTD_decompressStream() * and updates the stage and the output buffer state. This call is extracted so it can be * used both when reading directly from the ZSTD_inBuffer, and in buffered input mode. * NOTE: You must break after calling this function since the streamStage is modified. */ static size_t ZSTD_decompressContinueStream( ZSTD_DStream* zds, char** op, char* oend, void const* src, size_t srcSize) { … } size_t ZSTD_decompressStream(ZSTD_DStream* zds, ZSTD_outBuffer* output, ZSTD_inBuffer* input) { … } size_t ZSTD_decompressStream_simpleArgs ( ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, size_t* dstPos, const void* src, size_t srcSize, size_t* srcPos) { … }