/* * 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. */ #include "zstd_compress_internal.h" #include "hist.h" #include "zstd_opt.h" #if !defined(ZSTD_EXCLUDE_BTLAZY2_BLOCK_COMPRESSOR) \ || !defined(ZSTD_EXCLUDE_BTOPT_BLOCK_COMPRESSOR) \ || !defined(ZSTD_EXCLUDE_BTULTRA_BLOCK_COMPRESSOR) #define ZSTD_LITFREQ_ADD … #define ZSTD_MAX_PRICE … #define ZSTD_PREDEF_THRESHOLD … /*-************************************* * Price functions for optimal parser ***************************************/ #if 0 /* approximation at bit level (for tests) */ #define BITCOST_ACCURACY … #define BITCOST_MULTIPLIER … #define WEIGHT … #elif 0 /* fractional bit accuracy (for tests) */ #define BITCOST_ACCURACY … #define BITCOST_MULTIPLIER … #define WEIGHT … #else /* opt==approx, ultra==accurate */ #define BITCOST_ACCURACY … #define BITCOST_MULTIPLIER … #define WEIGHT(stat,opt) … #endif /* ZSTD_bitWeight() : * provide estimated "cost" of a stat in full bits only */ MEM_STATIC U32 ZSTD_bitWeight(U32 stat) { … } /* ZSTD_fracWeight() : * provide fractional-bit "cost" of a stat, * using linear interpolation approximation */ MEM_STATIC U32 ZSTD_fracWeight(U32 rawStat) { … } #if (DEBUGLEVEL>=2) /* debugging function, * @return price in bytes as fractional value * for debug messages only */ MEM_STATIC double ZSTD_fCost(int price) { return (double)price / (BITCOST_MULTIPLIER*8); } #endif static int ZSTD_compressedLiterals(optState_t const* const optPtr) { … } static void ZSTD_setBasePrices(optState_t* optPtr, int optLevel) { … } static U32 sum_u32(const unsigned table[], size_t nbElts) { … } base_directive_e; static U32 ZSTD_downscaleStats(unsigned* table, U32 lastEltIndex, U32 shift, base_directive_e base1) { … } /* ZSTD_scaleStats() : * reduce all elt frequencies in table if sum too large * return the resulting sum of elements */ static U32 ZSTD_scaleStats(unsigned* table, U32 lastEltIndex, U32 logTarget) { … } /* ZSTD_rescaleFreqs() : * if first block (detected by optPtr->litLengthSum == 0) : init statistics * take hints from dictionary if there is one * and init from zero if there is none, * using src for literals stats, and baseline stats for sequence symbols * otherwise downscale existing stats, to be used as seed for next block. */ static void ZSTD_rescaleFreqs(optState_t* const optPtr, const BYTE* const src, size_t const srcSize, int const optLevel) { … } /* ZSTD_rawLiteralsCost() : * price of literals (only) in specified segment (which length can be 0). * does not include price of literalLength symbol */ static U32 ZSTD_rawLiteralsCost(const BYTE* const literals, U32 const litLength, const optState_t* const optPtr, int optLevel) { … } /* ZSTD_litLengthPrice() : * cost of literalLength symbol */ static U32 ZSTD_litLengthPrice(U32 const litLength, const optState_t* const optPtr, int optLevel) { … } /* ZSTD_getMatchPrice() : * Provides the cost of the match part (offset + matchLength) of a sequence. * Must be combined with ZSTD_fullLiteralsCost() to get the full cost of a sequence. * @offBase : sumtype, representing an offset or a repcode, and using numeric representation of ZSTD_storeSeq() * @optLevel: when <2, favors small offset for decompression speed (improved cache efficiency) */ FORCE_INLINE_TEMPLATE U32 ZSTD_getMatchPrice(U32 const offBase, U32 const matchLength, const optState_t* const optPtr, int const optLevel) { … } /* ZSTD_updateStats() : * assumption : literals + litLength <= iend */ static void ZSTD_updateStats(optState_t* const optPtr, U32 litLength, const BYTE* literals, U32 offBase, U32 matchLength) { … } /* ZSTD_readMINMATCH() : * function safe only for comparisons * assumption : memPtr must be at least 4 bytes before end of buffer */ MEM_STATIC U32 ZSTD_readMINMATCH(const void* memPtr, U32 length) { … } /* Update hashTable3 up to ip (excluded) Assumption : always within prefix (i.e. not within extDict) */ static ZSTD_ALLOW_POINTER_OVERFLOW_ATTR U32 ZSTD_insertAndFindFirstIndexHash3 (const ZSTD_matchState_t* ms, U32* nextToUpdate3, const BYTE* const ip) { … } /*-************************************* * Binary Tree search ***************************************/ /** ZSTD_insertBt1() : add one or multiple positions to tree. * @param ip assumed <= iend-8 . * @param target The target of ZSTD_updateTree_internal() - we are filling to this position * @return : nb of positions added */ static ZSTD_ALLOW_POINTER_OVERFLOW_ATTR U32 ZSTD_insertBt1( const ZSTD_matchState_t* ms, const BYTE* const ip, const BYTE* const iend, U32 const target, U32 const mls, const int extDict) { … } FORCE_INLINE_TEMPLATE ZSTD_ALLOW_POINTER_OVERFLOW_ATTR void ZSTD_updateTree_internal( ZSTD_matchState_t* ms, const BYTE* const ip, const BYTE* const iend, const U32 mls, const ZSTD_dictMode_e dictMode) { … } void ZSTD_updateTree(ZSTD_matchState_t* ms, const BYTE* ip, const BYTE* iend) { … } FORCE_INLINE_TEMPLATE ZSTD_ALLOW_POINTER_OVERFLOW_ATTR U32 ZSTD_insertBtAndGetAllMatches ( ZSTD_match_t* matches, /* store result (found matches) in this table (presumed large enough) */ ZSTD_matchState_t* ms, U32* nextToUpdate3, const BYTE* const ip, const BYTE* const iLimit, const ZSTD_dictMode_e dictMode, const U32 rep[ZSTD_REP_NUM], const U32 ll0, /* tells if associated literal length is 0 or not. This value must be 0 or 1 */ const U32 lengthToBeat, const U32 mls /* template */) { … } ZSTD_getAllMatchesFn; FORCE_INLINE_TEMPLATE ZSTD_ALLOW_POINTER_OVERFLOW_ATTR U32 ZSTD_btGetAllMatches_internal( ZSTD_match_t* matches, ZSTD_matchState_t* ms, U32* nextToUpdate3, const BYTE* ip, const BYTE* const iHighLimit, const U32 rep[ZSTD_REP_NUM], U32 const ll0, U32 const lengthToBeat, const ZSTD_dictMode_e dictMode, const U32 mls) { … } #define ZSTD_BT_GET_ALL_MATCHES_FN(dictMode, mls) … #define GEN_ZSTD_BT_GET_ALL_MATCHES_(dictMode, mls) … #define GEN_ZSTD_BT_GET_ALL_MATCHES(dictMode) … GEN_ZSTD_BT_GET_ALL_MATCHES(noDict) GEN_ZSTD_BT_GET_ALL_MATCHES(extDict) GEN_ZSTD_BT_GET_ALL_MATCHES(dictMatchState) #define ZSTD_BT_GET_ALL_MATCHES_ARRAY(dictMode) … static ZSTD_getAllMatchesFn ZSTD_selectBtGetAllMatches(ZSTD_matchState_t const* ms, ZSTD_dictMode_e const dictMode) { … } /************************* * LDM helper functions * *************************/ /* Struct containing info needed to make decision about ldm inclusion */ ZSTD_optLdm_t; /* ZSTD_optLdm_skipRawSeqStoreBytes(): * Moves forward in @rawSeqStore by @nbBytes, * which will update the fields 'pos' and 'posInSequence'. */ static void ZSTD_optLdm_skipRawSeqStoreBytes(rawSeqStore_t* rawSeqStore, size_t nbBytes) { … } /* ZSTD_opt_getNextMatchAndUpdateSeqStore(): * Calculates the beginning and end of the next match in the current block. * Updates 'pos' and 'posInSequence' of the ldmSeqStore. */ static void ZSTD_opt_getNextMatchAndUpdateSeqStore(ZSTD_optLdm_t* optLdm, U32 currPosInBlock, U32 blockBytesRemaining) { … } /* ZSTD_optLdm_maybeAddMatch(): * Adds a match if it's long enough, * based on it's 'matchStartPosInBlock' and 'matchEndPosInBlock', * into 'matches'. Maintains the correct ordering of 'matches'. */ static void ZSTD_optLdm_maybeAddMatch(ZSTD_match_t* matches, U32* nbMatches, const ZSTD_optLdm_t* optLdm, U32 currPosInBlock) { … } /* ZSTD_optLdm_processMatchCandidate(): * Wrapper function to update ldm seq store and call ldm functions as necessary. */ static void ZSTD_optLdm_processMatchCandidate(ZSTD_optLdm_t* optLdm, ZSTD_match_t* matches, U32* nbMatches, U32 currPosInBlock, U32 remainingBytes) { … } /*-******************************* * Optimal parser *********************************/ #if 0 /* debug */ static void listStats(const U32* table, int lastEltID) { int const nbElts = lastEltID + 1; int enb; for (enb=0; enb < nbElts; enb++) { (void)table; /* RAWLOG(2, "%3i:%3i, ", enb, table[enb]); */ RAWLOG(2, "%4i,", table[enb]); } RAWLOG(2, " \n"); } #endif #define LIT_PRICE(_p) … #define LL_PRICE(_l) … #define LL_INCPRICE(_l) … FORCE_INLINE_TEMPLATE ZSTD_ALLOW_POINTER_OVERFLOW_ATTR size_t ZSTD_compressBlock_opt_generic(ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], const void* src, size_t srcSize, const int optLevel, const ZSTD_dictMode_e dictMode) { … } #endif /* build exclusions */ #ifndef ZSTD_EXCLUDE_BTOPT_BLOCK_COMPRESSOR static size_t ZSTD_compressBlock_opt0( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], const void* src, size_t srcSize, const ZSTD_dictMode_e dictMode) { … } #endif #ifndef ZSTD_EXCLUDE_BTULTRA_BLOCK_COMPRESSOR static size_t ZSTD_compressBlock_opt2( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], const void* src, size_t srcSize, const ZSTD_dictMode_e dictMode) { … } #endif #ifndef ZSTD_EXCLUDE_BTOPT_BLOCK_COMPRESSOR size_t ZSTD_compressBlock_btopt( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], const void* src, size_t srcSize) { … } #endif #ifndef ZSTD_EXCLUDE_BTULTRA_BLOCK_COMPRESSOR /* ZSTD_initStats_ultra(): * make a first compression pass, just to seed stats with more accurate starting values. * only works on first block, with no dictionary and no ldm. * this function cannot error out, its narrow contract must be respected. */ static ZSTD_ALLOW_POINTER_OVERFLOW_ATTR void ZSTD_initStats_ultra(ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], const void* src, size_t srcSize) { … } size_t ZSTD_compressBlock_btultra( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], const void* src, size_t srcSize) { … } size_t ZSTD_compressBlock_btultra2( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], const void* src, size_t srcSize) { … } #endif #ifndef ZSTD_EXCLUDE_BTOPT_BLOCK_COMPRESSOR size_t ZSTD_compressBlock_btopt_dictMatchState( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], const void* src, size_t srcSize) { … } size_t ZSTD_compressBlock_btopt_extDict( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], const void* src, size_t srcSize) { … } #endif #ifndef ZSTD_EXCLUDE_BTULTRA_BLOCK_COMPRESSOR size_t ZSTD_compressBlock_btultra_dictMatchState( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], const void* src, size_t srcSize) { … } size_t ZSTD_compressBlock_btultra_extDict( ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], const void* src, size_t srcSize) { … } #endif /* note : no btultra2 variant for extDict nor dictMatchState, * because btultra2 is not meant to work with dictionaries * and is only specific for the first block (no prefix) */
Codebase Browser
chromium