#include "zstd_compress_internal.h"
#include "zstd_lazy.h"
#include "../common/bits.h"

Macros
#define	kLazySkippingStep 8

#define	NEXT_IN_CHAIN(d, mask)

#define	ZSTD_ROW_HASH_TAG_MASK ((1u << ZSTD_ROW_HASH_TAG_BITS) - 1)

#define	ZSTD_ROW_HASH_MAX_ENTRIES 64 /* absolute maximum number of entries per row, for all configurations */

#define	ZSTD_ROW_HASH_CACHE_MASK (ZSTD_ROW_HASH_CACHE_SIZE - 1)

#define	ZSTD_BT_SEARCH_FN(dictMode, mls)

#define	ZSTD_HC_SEARCH_FN(dictMode, mls)

#define	ZSTD_ROW_SEARCH_FN(dictMode, mls, rowLog)

#define	ZSTD_SEARCH_FN_ATTRS FORCE_NOINLINE

#define	GEN_ZSTD_BT_SEARCH_FN(dictMode, mls)

#define	GEN_ZSTD_HC_SEARCH_FN(dictMode, mls)

#define	GEN_ZSTD_ROW_SEARCH_FN(dictMode, mls, rowLog)

#define	ZSTD_FOR_EACH_ROWLOG(X, dictMode, mls)

#define	ZSTD_FOR_EACH_MLS_ROWLOG(X, dictMode)

#define	ZSTD_FOR_EACH_MLS(X, dictMode)

#define	ZSTD_FOR_EACH_DICT_MODE(X, ...)

#define	GEN_ZSTD_CALL_BT_SEARCH_FN(dictMode, mls)

#define	GEN_ZSTD_CALL_HC_SEARCH_FN(dictMode, mls)

#define	GEN_ZSTD_CALL_ROW_SEARCH_FN(dictMode, mls, rowLog)

#define	ZSTD_SWITCH_MLS(X, dictMode)

#define	ZSTD_SWITCH_ROWLOG(dictMode, mls)

#define	ZSTD_SWITCH_SEARCH_METHOD(dictMode)

Enumerations
enum	searchMethod_e { search_hashChain =0 , search_binaryTree =1 , search_rowHash =2 }

Functions
FORCE_INLINE_TEMPLATE size_t	ZSTD_BtFindBestMatch (ZSTD_matchState_t ms, const BYTE const ip, const BYTE const iLimit, size_t offBasePtr, const U32 mls, const ZSTD_dictMode_e dictMode)

void	ZSTD_dedicatedDictSearch_lazy_loadDictionary (ZSTD_matchState_t ms, const BYTE const ip)

FORCE_INLINE_TEMPLATE size_t	ZSTD_dedicatedDictSearch_lazy_search (size_t offsetPtr, size_t ml, U32 nbAttempts, const ZSTD_matchState_t const dms, const BYTE const ip, const BYTE const iLimit, const BYTE *const prefixStart, const U32 curr, const U32 dictLimit, const size_t ddsIdx)

FORCE_INLINE_TEMPLATE U32	ZSTD_insertAndFindFirstIndex_internal (ZSTD_matchState_t ms, const ZSTD_compressionParameters const cParams, const BYTE *ip, U32 const mls, U32 const lazySkipping)

U32	ZSTD_insertAndFindFirstIndex (ZSTD_matchState_t ms, const BYTE ip)

FORCE_INLINE_TEMPLATE size_t	ZSTD_HcFindBestMatch (ZSTD_matchState_t ms, const BYTE const ip, const BYTE const iLimit, size_t offsetPtr, const U32 mls, const ZSTD_dictMode_e dictMode)

MEM_STATIC U32	ZSTD_VecMask_next (ZSTD_VecMask val)

FORCE_INLINE_TEMPLATE U32	ZSTD_row_nextIndex (BYTE *const tagRow, U32 const rowMask)

MEM_STATIC int	ZSTD_isAligned (void const *ptr, size_t align)

FORCE_INLINE_TEMPLATE void	ZSTD_row_prefetch (U32 const hashTable, BYTE const tagTable, U32 const relRow, U32 const rowLog)

FORCE_INLINE_TEMPLATE void	ZSTD_row_fillHashCache (ZSTD_matchState_t ms, const BYTE base, U32 const rowLog, U32 const mls, U32 idx, const BYTE *const iLimit)

FORCE_INLINE_TEMPLATE U32	ZSTD_row_nextCachedHash (U32 cache, U32 const hashTable, BYTE const tagTable, BYTE const base, U32 idx, U32 const hashLog, U32 const rowLog, U32 const mls, U64 const hashSalt)

FORCE_INLINE_TEMPLATE void	ZSTD_row_update_internalImpl (ZSTD_matchState_t *ms, U32 updateStartIdx, U32 const updateEndIdx, U32 const mls, U32 const rowLog, U32 const rowMask, U32 const useCache)

FORCE_INLINE_TEMPLATE void	ZSTD_row_update_internal (ZSTD_matchState_t ms, const BYTE ip, U32 const mls, U32 const rowLog, U32 const rowMask, U32 const useCache)

void	ZSTD_row_update (ZSTD_matchState_t const ms, const BYTE ip)

FORCE_INLINE_TEMPLATE U32	ZSTD_row_matchMaskGroupWidth (const U32 rowEntries)

FORCE_INLINE_TEMPLATE ZSTD_VecMask	ZSTD_row_getMatchMask (const BYTE *const tagRow, const BYTE tag, const U32 headGrouped, const U32 rowEntries)

FORCE_INLINE_TEMPLATE size_t	ZSTD_RowFindBestMatch (ZSTD_matchState_t ms, const BYTE const ip, const BYTE const iLimit, size_t offsetPtr, const U32 mls, const ZSTD_dictMode_e dictMode, const U32 rowLog)

FORCE_INLINE_TEMPLATE size_t	ZSTD_searchMax (ZSTD_matchState_t ms, const BYTE ip, const BYTE iend, size_t offsetPtr, U32 const mls, U32 const rowLog, searchMethod_e const searchMethod, ZSTD_dictMode_e const dictMode)

FORCE_INLINE_TEMPLATE size_t	ZSTD_compressBlock_lazy_generic (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize, const searchMethod_e searchMethod, const U32 depth, ZSTD_dictMode_e const dictMode)

size_t	ZSTD_compressBlock_btlazy2 (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy2 (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_greedy (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_btlazy2_dictMatchState (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy2_dictMatchState (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy_dictMatchState (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_greedy_dictMatchState (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy2_dedicatedDictSearch (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy_dedicatedDictSearch (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_greedy_dedicatedDictSearch (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy2_row (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy_row (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_greedy_row (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy2_dictMatchState_row (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy_dictMatchState_row (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_greedy_dictMatchState_row (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy2_dedicatedDictSearch_row (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy_dedicatedDictSearch_row (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_greedy_dedicatedDictSearch_row (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

FORCE_INLINE_TEMPLATE size_t	ZSTD_compressBlock_lazy_extDict_generic (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], const void *src, size_t srcSize, const searchMethod_e searchMethod, const U32 depth)

size_t	ZSTD_compressBlock_greedy_extDict (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy_extDict (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy2_extDict (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_btlazy2_extDict (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_greedy_extDict_row (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy_extDict_row (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

size_t	ZSTD_compressBlock_lazy2_extDict_row (ZSTD_matchState_t ms, seqStore_t seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

Macro Definition Documentation

◆ GEN_ZSTD_BT_SEARCH_FN

#define GEN_ZSTD_BT_SEARCH_FN	(		dictMode,
			mls )

Value:

    ZSTD_SEARCH_FN_ATTRS size_t ZSTD_BT_SEARCH_FN(dictMode, mls)(                      \
            ZSTD_matchState_t* ms,                                                     \
            const BYTE* ip, const BYTE* const iLimit,                                  \
            size_t* offBasePtr)                                                        \
    {                                                                                  \
        assert(MAX(4, MIN(6, ms->cParams.minMatch)) == mls);                           \
        return ZSTD_BtFindBestMatch(ms, ip, iLimit, offBasePtr, mls, ZSTD_##dictMode); \
    }                                                                                  \

◆ GEN_ZSTD_CALL_BT_SEARCH_FN

#define GEN_ZSTD_CALL_BT_SEARCH_FN	(		dictMode,
			mls )

Value:

case mls: \

return ZSTD_BT_SEARCH_FN(dictMode, mls)(ms, ip, iend, offsetPtr);

◆ GEN_ZSTD_CALL_HC_SEARCH_FN

#define GEN_ZSTD_CALL_HC_SEARCH_FN	(		dictMode,
			mls )

Value:

case mls: \

return ZSTD_HC_SEARCH_FN(dictMode, mls)(ms, ip, iend, offsetPtr);

ZSTD_HC_SEARCH_FN

#define ZSTD_HC_SEARCH_FN(dictMode, mls)

Definition zstd_lazy.c:1338

◆ GEN_ZSTD_CALL_ROW_SEARCH_FN

#define GEN_ZSTD_CALL_ROW_SEARCH_FN	(	dictMode,
		mls,
		rowLog )

Value:

case rowLog: \

return ZSTD_ROW_SEARCH_FN(dictMode, mls, rowLog)(ms, ip, iend, offsetPtr);

ZSTD_ROW_SEARCH_FN

#define ZSTD_ROW_SEARCH_FN(dictMode, mls, rowLog)

Definition zstd_lazy.c:1339

◆ GEN_ZSTD_HC_SEARCH_FN

#define GEN_ZSTD_HC_SEARCH_FN	(		dictMode,
			mls )

Value:

    ZSTD_SEARCH_FN_ATTRS size_t ZSTD_HC_SEARCH_FN(dictMode, mls)(                     \
            ZSTD_matchState_t* ms,                                                    \
            const BYTE* ip, const BYTE* const iLimit,                                 \
            size_t* offsetPtr)                                                        \
    {                                                                                 \
        assert(MAX(4, MIN(6, ms->cParams.minMatch)) == mls);                          \
        return ZSTD_HcFindBestMatch(ms, ip, iLimit, offsetPtr, mls, ZSTD_##dictMode); \
    }                                                                                 \

◆ GEN_ZSTD_ROW_SEARCH_FN

#define GEN_ZSTD_ROW_SEARCH_FN	(	dictMode,
		mls,
		rowLog )

Value:

    ZSTD_SEARCH_FN_ATTRS size_t ZSTD_ROW_SEARCH_FN(dictMode, mls, rowLog)(                     \
            ZSTD_matchState_t* ms,                                                             \
            const BYTE* ip, const BYTE* const iLimit,                                          \
            size_t* offsetPtr)                                                                 \
    {                                                                                          \
        assert(MAX(4, MIN(6, ms->cParams.minMatch)) == mls);                                   \
        assert(MAX(4, MIN(6, ms->cParams.searchLog)) == rowLog);                               \
        return ZSTD_RowFindBestMatch(ms, ip, iLimit, offsetPtr, mls, ZSTD_##dictMode, rowLog); \
    }                                                                                          \

◆ kLazySkippingStep

#define kLazySkippingStep 8

◆ NEXT_IN_CHAIN

#define NEXT_IN_CHAIN	(		d,
			mask )

Value:

chainTable[(d) & (mask)]

d

#define d(i)

Definition sha256.c:44

◆ ZSTD_BT_SEARCH_FN

#define ZSTD_BT_SEARCH_FN	(		dictMode,
			mls )

Value:

ZSTD_BtFindBestMatch_##dictMode##_##mls

_

#define _(msgid)

Definition getopt.c:49

Generate search functions templated on (dictMode, mls, rowLog). These functions are outlined for code size & compilation time. ZSTD_searchMax() dispatches to the correct implementation function.

TODO: The start of the search function involves loading and calculating a bunch of constants from the ZSTD_matchState_t. These computations could be done in an initialization function, and saved somewhere in the match state. Then we could pass a pointer to the saved state instead of the match state, and avoid duplicate computations.

TODO: Move the match re-winding into searchMax. This improves compression ratio, and unlocks further simplifications with the next TODO.

TODO: Try moving the repcode search into searchMax. After the re-winding and repcode search are in searchMax, there is no more logic in the match finder loop that requires knowledge about the dictMode. So we should be able to avoid force inlining it, and we can join the extDict loop with the single segment loop. It should go in searchMax instead of its own function to avoid having multiple virtual function calls per search.

◆ ZSTD_FOR_EACH_DICT_MODE

#define ZSTD_FOR_EACH_DICT_MODE	(		X,
			... )

Value:

    X(__VA_ARGS__, noDict)              \
    X(__VA_ARGS__, extDict)             \
    X(__VA_ARGS__, dictMatchState)      \
    X(__VA_ARGS__, dedicatedDictSearch)

◆ ZSTD_FOR_EACH_MLS

#define ZSTD_FOR_EACH_MLS	(		X,
			dictMode )

Value:

    X(dictMode, 4)                     \
    X(dictMode, 5)                     \
    X(dictMode, 6)

◆ ZSTD_FOR_EACH_MLS_ROWLOG

#define ZSTD_FOR_EACH_MLS_ROWLOG	(		X,
			dictMode )

Value:

    ZSTD_FOR_EACH_ROWLOG(X, dictMode, 4)      \
    ZSTD_FOR_EACH_ROWLOG(X, dictMode, 5)      \
    ZSTD_FOR_EACH_ROWLOG(X, dictMode, 6)

◆ ZSTD_FOR_EACH_ROWLOG

#define ZSTD_FOR_EACH_ROWLOG	(	X,
		dictMode,
		mls )

Value:

    X(dictMode, mls, 4)                        \
    X(dictMode, mls, 5)                        \
    X(dictMode, mls, 6)

◆ ZSTD_HC_SEARCH_FN

#define ZSTD_HC_SEARCH_FN	(		dictMode,
			mls )

Value:

ZSTD_HcFindBestMatch_##dictMode##_##mls

◆ ZSTD_ROW_HASH_CACHE_MASK

#define ZSTD_ROW_HASH_CACHE_MASK (ZSTD_ROW_HASH_CACHE_SIZE - 1)

◆ ZSTD_ROW_HASH_MAX_ENTRIES

#define ZSTD_ROW_HASH_MAX_ENTRIES 64 /* absolute maximum number of entries per row, for all configurations */

◆ ZSTD_ROW_HASH_TAG_MASK

#define ZSTD_ROW_HASH_TAG_MASK ((1u << ZSTD_ROW_HASH_TAG_BITS) - 1)

◆ ZSTD_ROW_SEARCH_FN

#define ZSTD_ROW_SEARCH_FN	(	dictMode,
		mls,
		rowLog )

Value:

ZSTD_RowFindBestMatch_##dictMode##_##mls##_##rowLog

◆ ZSTD_SEARCH_FN_ATTRS

#define ZSTD_SEARCH_FN_ATTRS FORCE_NOINLINE

◆ ZSTD_SWITCH_MLS

#define ZSTD_SWITCH_MLS	(		X,
			dictMode )

Value:

    switch (mls) {                     \
        ZSTD_FOR_EACH_MLS(X, dictMode) \
    }

◆ ZSTD_SWITCH_ROWLOG

#define ZSTD_SWITCH_ROWLOG	(		dictMode,
			mls )

Value:

    case mls:                                                                \
        switch (rowLog) {                                                    \
            ZSTD_FOR_EACH_ROWLOG(GEN_ZSTD_CALL_ROW_SEARCH_FN, dictMode, mls) \
        }                                                                    \
        ZSTD_UNREACHABLE;                                                    \
        break;

◆ ZSTD_SWITCH_SEARCH_METHOD

#define ZSTD_SWITCH_SEARCH_METHOD ( dictMode )

Value:

    switch (searchMethod) {                                       \
        case search_hashChain:                                    \
            ZSTD_SWITCH_MLS(GEN_ZSTD_CALL_HC_SEARCH_FN, dictMode) \
            break;                                                \
        case search_binaryTree:                                   \
            ZSTD_SWITCH_MLS(GEN_ZSTD_CALL_BT_SEARCH_FN, dictMode) \
            break;                                                \
        case search_rowHash:                                      \
            ZSTD_SWITCH_MLS(ZSTD_SWITCH_ROWLOG, dictMode)         \
            break;                                                \
    }                                                             \
    ZSTD_UNREACHABLE;

Enumeration Type Documentation

◆ searchMethod_e

enum searchMethod_e

Enumerator
search_hashChain
search_binaryTree
search_rowHash

Function Documentation

◆ ZSTD_BtFindBestMatch()

FORCE_INLINE_TEMPLATE size_t ZSTD_BtFindBestMatch	(	ZSTD_matchState_t *	ms,
		const BYTE *const	ip,
		const BYTE *const	iLimit,
		size_t *	offBasePtr,
		const U32	mls,
		const ZSTD_dictMode_e	dictMode )

ZSTD_BtFindBestMatch() : Tree updater, providing best match

◆ ZSTD_compressBlock_btlazy2()

size_t ZSTD_compressBlock_btlazy2	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

used in ZSTD_reduceIndex(). preemptively increase value of ZSTD_DUBT_UNSORTED_MARK

◆ ZSTD_compressBlock_btlazy2_dictMatchState()

size_t ZSTD_compressBlock_btlazy2_dictMatchState	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_btlazy2_extDict()

size_t ZSTD_compressBlock_btlazy2_extDict	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_greedy()

size_t ZSTD_compressBlock_greedy	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

used in ZSTD_reduceIndex(). preemptively increase value of ZSTD_DUBT_UNSORTED_MARK

◆ ZSTD_compressBlock_greedy_dedicatedDictSearch()

size_t ZSTD_compressBlock_greedy_dedicatedDictSearch	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_greedy_dedicatedDictSearch_row()

size_t ZSTD_compressBlock_greedy_dedicatedDictSearch_row	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_greedy_dictMatchState()

size_t ZSTD_compressBlock_greedy_dictMatchState	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_greedy_dictMatchState_row()

size_t ZSTD_compressBlock_greedy_dictMatchState_row	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_greedy_extDict()

size_t ZSTD_compressBlock_greedy_extDict	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_greedy_extDict_row()

size_t ZSTD_compressBlock_greedy_extDict_row	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_greedy_row()

size_t ZSTD_compressBlock_greedy_row	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy()

size_t ZSTD_compressBlock_lazy	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy2()

size_t ZSTD_compressBlock_lazy2	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy2_dedicatedDictSearch()

size_t ZSTD_compressBlock_lazy2_dedicatedDictSearch	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy2_dedicatedDictSearch_row()

size_t ZSTD_compressBlock_lazy2_dedicatedDictSearch_row	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy2_dictMatchState()

size_t ZSTD_compressBlock_lazy2_dictMatchState	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy2_dictMatchState_row()

size_t ZSTD_compressBlock_lazy2_dictMatchState_row	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy2_extDict()

size_t ZSTD_compressBlock_lazy2_extDict	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy2_extDict_row()

size_t ZSTD_compressBlock_lazy2_extDict_row	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy2_row()

size_t ZSTD_compressBlock_lazy2_row	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy_dedicatedDictSearch()

size_t ZSTD_compressBlock_lazy_dedicatedDictSearch	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy_dedicatedDictSearch_row()

size_t ZSTD_compressBlock_lazy_dedicatedDictSearch_row	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy_dictMatchState()

size_t ZSTD_compressBlock_lazy_dictMatchState	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy_dictMatchState_row()

size_t ZSTD_compressBlock_lazy_dictMatchState_row	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy_extDict()

size_t ZSTD_compressBlock_lazy_extDict	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy_extDict_generic()

FORCE_INLINE_TEMPLATE size_t ZSTD_compressBlock_lazy_extDict_generic	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		const void *	src,
		size_t	srcSize,
		const searchMethod_e	searchMethod,
		const U32	depth )

◆ ZSTD_compressBlock_lazy_extDict_row()

size_t ZSTD_compressBlock_lazy_extDict_row	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_compressBlock_lazy_generic()

FORCE_INLINE_TEMPLATE size_t ZSTD_compressBlock_lazy_generic	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		const void *	src,
		size_t	srcSize,
		const searchMethod_e	searchMethod,
		const U32	depth,
		ZSTD_dictMode_e const	dictMode )

◆ ZSTD_compressBlock_lazy_row()

size_t ZSTD_compressBlock_lazy_row	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize )

◆ ZSTD_dedicatedDictSearch_lazy_loadDictionary()

void ZSTD_dedicatedDictSearch_lazy_loadDictionary	(	ZSTD_matchState_t *	ms,
		const BYTE *const	ip )

◆ ZSTD_dedicatedDictSearch_lazy_search()

FORCE_INLINE_TEMPLATE size_t ZSTD_dedicatedDictSearch_lazy_search	(	size_t *	offsetPtr,
		size_t	ml,
		U32	nbAttempts,
		const ZSTD_matchState_t *const	dms,
		const BYTE *const	ip,
		const BYTE *const	iLimit,
		const BYTE *const	prefixStart,
		const U32	curr,
		const U32	dictLimit,
		const size_t	ddsIdx )

◆ ZSTD_HcFindBestMatch()

FORCE_INLINE_TEMPLATE size_t ZSTD_HcFindBestMatch	(	ZSTD_matchState_t *	ms,
		const BYTE *const	ip,
		const BYTE *const	iLimit,
		size_t *	offsetPtr,
		const U32	mls,
		const ZSTD_dictMode_e	dictMode )

◆ ZSTD_insertAndFindFirstIndex()

U32 ZSTD_insertAndFindFirstIndex	(	ZSTD_matchState_t *	ms,
		const BYTE *	ip )

◆ ZSTD_insertAndFindFirstIndex_internal()

FORCE_INLINE_TEMPLATE U32 ZSTD_insertAndFindFirstIndex_internal	(	ZSTD_matchState_t *	ms,
		const ZSTD_compressionParameters *const	cParams,
		const BYTE *	ip,
		U32 const	mls,
		U32 const	lazySkipping )

◆ ZSTD_isAligned()

MEM_STATIC int ZSTD_isAligned	(	void const *	ptr,
		size_t	align )

◆ ZSTD_row_fillHashCache()

FORCE_INLINE_TEMPLATE void ZSTD_row_fillHashCache	(	ZSTD_matchState_t *	ms,
		const BYTE *	base,
		U32 const	rowLog,
		U32 const	mls,
		U32	idx,
		const BYTE *const	iLimit )

◆ ZSTD_row_getMatchMask()

FORCE_INLINE_TEMPLATE ZSTD_VecMask ZSTD_row_getMatchMask	(	const BYTE *const	tagRow,
		const BYTE	tag,
		const U32	headGrouped,
		const U32	rowEntries )

◆ ZSTD_row_matchMaskGroupWidth()

FORCE_INLINE_TEMPLATE U32 ZSTD_row_matchMaskGroupWidth ( const U32 rowEntries )

◆ ZSTD_row_nextCachedHash()

FORCE_INLINE_TEMPLATE U32 ZSTD_row_nextCachedHash	(	U32 *	cache,
		U32 const *	hashTable,
		BYTE const *	tagTable,
		BYTE const *	base,
		U32	idx,
		U32 const	hashLog,
		U32 const	rowLog,
		U32 const	mls,
		U64 const	hashSalt )

◆ ZSTD_row_nextIndex()

FORCE_INLINE_TEMPLATE U32 ZSTD_row_nextIndex	(	BYTE *const	tagRow,
		U32 const	rowMask )

◆ ZSTD_row_prefetch()

FORCE_INLINE_TEMPLATE void ZSTD_row_prefetch	(	U32 const *	hashTable,
		BYTE const *	tagTable,
		U32 const	relRow,
		U32 const	rowLog )

◆ ZSTD_row_update()

void ZSTD_row_update	(	ZSTD_matchState_t *const	ms,
		const BYTE *	ip )

◆ ZSTD_row_update_internal()

FORCE_INLINE_TEMPLATE void ZSTD_row_update_internal	(	ZSTD_matchState_t *	ms,
		const BYTE *	ip,
		U32 const	mls,
		U32 const	rowLog,
		U32 const	rowMask,
		U32 const	useCache )

◆ ZSTD_row_update_internalImpl()

FORCE_INLINE_TEMPLATE void ZSTD_row_update_internalImpl	(	ZSTD_matchState_t *	ms,
		U32	updateStartIdx,
		U32 const	updateEndIdx,
		U32 const	mls,
		U32 const	rowLog,
		U32 const	rowMask,
		U32 const	useCache )

◆ ZSTD_RowFindBestMatch()

FORCE_INLINE_TEMPLATE size_t ZSTD_RowFindBestMatch	(	ZSTD_matchState_t *	ms,
		const BYTE *const	ip,
		const BYTE *const	iLimit,
		size_t *	offsetPtr,
		const U32	mls,
		const ZSTD_dictMode_e	dictMode,
		const U32	rowLog )

◆ ZSTD_searchMax()

FORCE_INLINE_TEMPLATE size_t ZSTD_searchMax	(	ZSTD_matchState_t *	ms,
		const BYTE *	ip,
		const BYTE *	iend,
		size_t *	offsetPtr,
		U32 const	mls,
		U32 const	rowLog,
		searchMethod_e const	searchMethod,
		ZSTD_dictMode_e const	dictMode )

Searches for the longest match at ip. Dispatches to the correct implementation function based on the (searchMethod, dictMode, mls, rowLog). We use switch statements here instead of using an indirect function call through a function pointer because after Spectre and Meltdown mitigations, indirect function calls can be very costly, especially in the kernel.

NOTE: dictMode and searchMethod should be templated, so those switch statements should be optimized out. Only the mls & rowLog switches should be left.

Parameters

	ms	The match state.
	ip	The position to search at.
	iend	The end of the input data.
[out]	offsetPtr	Stores the match offset into this pointer.
	mls	The minimum search length, in the range [4, 6].
	rowLog	The row log (if applicable), in the range [4, 6].
	searchMethod	The search method to use (templated).
	dictMode	The dictMode (templated).

Returns: The length of the longest match found, or < mls if no match is found. If a match is found its offset is stored in offsetPtr.

◆ ZSTD_VecMask_next()

MEM_STATIC U32 ZSTD_VecMask_next ( ZSTD_VecMask val )

Macros

Enumerations

Functions

Macro Definition Documentation

◆ GEN_ZSTD_BT_SEARCH_FN

◆ GEN_ZSTD_CALL_BT_SEARCH_FN

◆ GEN_ZSTD_CALL_HC_SEARCH_FN

◆ GEN_ZSTD_CALL_ROW_SEARCH_FN

◆ GEN_ZSTD_HC_SEARCH_FN

◆ GEN_ZSTD_ROW_SEARCH_FN

◆ kLazySkippingStep

◆ NEXT_IN_CHAIN

◆ ZSTD_BT_SEARCH_FN

◆ ZSTD_FOR_EACH_DICT_MODE

◆ ZSTD_FOR_EACH_MLS

◆ ZSTD_FOR_EACH_MLS_ROWLOG

◆ ZSTD_FOR_EACH_ROWLOG

◆ ZSTD_HC_SEARCH_FN

◆ ZSTD_ROW_HASH_CACHE_MASK

◆ ZSTD_ROW_HASH_MAX_ENTRIES

◆ ZSTD_ROW_HASH_TAG_MASK

◆ ZSTD_ROW_SEARCH_FN

◆ ZSTD_SEARCH_FN_ATTRS

◆ ZSTD_SWITCH_MLS

◆ ZSTD_SWITCH_ROWLOG

◆ ZSTD_SWITCH_SEARCH_METHOD

Enumeration Type Documentation

◆ searchMethod_e

Function Documentation

◆ ZSTD_BtFindBestMatch()

◆ ZSTD_compressBlock_btlazy2()

◆ ZSTD_compressBlock_btlazy2_dictMatchState()

◆ ZSTD_compressBlock_btlazy2_extDict()

◆ ZSTD_compressBlock_greedy()

◆ ZSTD_compressBlock_greedy_dedicatedDictSearch()

◆ ZSTD_compressBlock_greedy_dedicatedDictSearch_row()

◆ ZSTD_compressBlock_greedy_dictMatchState()

◆ ZSTD_compressBlock_greedy_dictMatchState_row()

◆ ZSTD_compressBlock_greedy_extDict()

◆ ZSTD_compressBlock_greedy_extDict_row()

◆ ZSTD_compressBlock_greedy_row()

◆ ZSTD_compressBlock_lazy()

◆ ZSTD_compressBlock_lazy2()

◆ ZSTD_compressBlock_lazy2_dedicatedDictSearch()

◆ ZSTD_compressBlock_lazy2_dedicatedDictSearch_row()

◆ ZSTD_compressBlock_lazy2_dictMatchState()

◆ ZSTD_compressBlock_lazy2_dictMatchState_row()

◆ ZSTD_compressBlock_lazy2_extDict()

◆ ZSTD_compressBlock_lazy2_extDict_row()

◆ ZSTD_compressBlock_lazy2_row()

◆ ZSTD_compressBlock_lazy_dedicatedDictSearch()

◆ ZSTD_compressBlock_lazy_dedicatedDictSearch_row()

◆ ZSTD_compressBlock_lazy_dictMatchState()

◆ ZSTD_compressBlock_lazy_dictMatchState_row()

◆ ZSTD_compressBlock_lazy_extDict()

◆ ZSTD_compressBlock_lazy_extDict_generic()

◆ ZSTD_compressBlock_lazy_extDict_row()

◆ ZSTD_compressBlock_lazy_generic()

◆ ZSTD_compressBlock_lazy_row()

◆ ZSTD_dedicatedDictSearch_lazy_loadDictionary()

◆ ZSTD_dedicatedDictSearch_lazy_search()

◆ ZSTD_HcFindBestMatch()

◆ ZSTD_insertAndFindFirstIndex()

◆ ZSTD_insertAndFindFirstIndex_internal()

◆ ZSTD_isAligned()

◆ ZSTD_row_fillHashCache()

◆ ZSTD_row_getMatchMask()

◆ ZSTD_row_matchMaskGroupWidth()

◆ ZSTD_row_nextCachedHash()

◆ ZSTD_row_nextIndex()

◆ ZSTD_row_prefetch()

◆ ZSTD_row_update()

◆ ZSTD_row_update_internal()

◆ ZSTD_row_update_internalImpl()

◆ ZSTD_RowFindBestMatch()

◆ ZSTD_searchMax()

◆ ZSTD_VecMask_next()