zstd_fast.c File Reference

#include "zstd_compress_internal.h"
#include "zstd_fast.h"

Include dependency graph for zstd_fast.c:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	ZSTD_GEN_FAST_FN(dictMode, mls, step)

Functions
void	ZSTD_fillHashTable (ZSTD_matchState_t *ms, const void *const end, ZSTD_dictTableLoadMethod_e dtlm, ZSTD_tableFillPurpose_e tfp)
FORCE_INLINE_TEMPLATE ZSTD_ALLOW_POINTER_OVERFLOW_ATTR size_t	ZSTD_compressBlock_fast_noDict_generic (ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize, U32 const mls, U32 const hasStep)
size_t	ZSTD_compressBlock_fast (ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
FORCE_INLINE_TEMPLATE ZSTD_ALLOW_POINTER_OVERFLOW_ATTR size_t	ZSTD_compressBlock_fast_dictMatchState_generic (ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize, U32 const mls, U32 const hasStep)
size_t	ZSTD_compressBlock_fast_dictMatchState (ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
size_t	ZSTD_compressBlock_fast_extDict (ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

Macro Definition Documentation

ZSTD_GEN_FAST_FN

#define ZSTD_GEN_FAST_FN	(		dictMode,
			mls,
			step
	)

Value:

    static size_t ZSTD_compressBlock_fast_##dictMode##_##mls##_##step(                                      \
            ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],                    \
            void const* src, size_t srcSize)                                                       \
    {                                                                                              \
        return ZSTD_compressBlock_fast_##dictMode##_generic(ms, seqStore, rep, src, srcSize, mls, step); \
    }

Definition at line 409 of file zstd_fast.c.

Function Documentation

ZSTD_compressBlock_fast()

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

Definition at line 427 of file zstd_fast.c.

Here is the caller graph for this function:

ZSTD_compressBlock_fast_dictMatchState()

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

Definition at line 669 of file zstd_fast.c.

Here is the caller graph for this function:

ZSTD_compressBlock_fast_dictMatchState_generic()

FORCE_INLINE_TEMPLATE ZSTD_ALLOW_POINTER_OVERFLOW_ATTR size_t ZSTD_compressBlock_fast_dictMatchState_generic	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize,
		U32 const	mls,
		U32 const	hasStep
	)

Definition at line 465 of file zstd_fast.c.

Here is the call graph for this function:

ZSTD_compressBlock_fast_extDict()

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

Definition at line 950 of file zstd_fast.c.

Here is the caller graph for this function:

ZSTD_compressBlock_fast_noDict_generic()

FORCE_INLINE_TEMPLATE ZSTD_ALLOW_POINTER_OVERFLOW_ATTR size_t ZSTD_compressBlock_fast_noDict_generic	(	ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		void const *	src,
		size_t	srcSize,
		U32 const	mls,
		U32 const	hasStep
	)

If you squint hard enough (and ignore repcodes), the search operation at any given position is broken into 4 stages:

1. Hash (map position to hash value via input read)
2. Lookup (map hash val to index via hashtable read)
3. Load (map index to value at that position via input read)
4. Compare

Each of these steps involves a memory read at an address which is computed from the previous step. This means these steps must be sequenced and their latencies are cumulative.

Rather than do 1->2->3->4 sequentially for a single position before moving onto the next, this implementation interleaves these operations across the next few positions:

R = Repcode Read & Compare H = Hash T = Table Lookup M = Match Read & Compare

Pos | Time --> -—+----------------— N | ... M N+1 | ... TM N+2 | R H T M N+3 | H TM N+4 | R H T M N+5 | H ... N+6 | R ...

This is very much analogous to the pipelining of execution in a CPU. And just like a CPU, we have to dump the pipeline when we find a match (i.e., take a branch).

When this happens, we throw away our current state, and do the following prep to re-enter the loop:

Pos | Time --> -—+----------------— N | H T N+1 | H

This is also the work we do at the beginning to enter the loop initially.

Definition at line 148 of file zstd_fast.c.

Here is the call graph for this function:

ZSTD_fillHashTable()

void ZSTD_fillHashTable	(	ZSTD_matchState_t *	ms,
		const void *const	end,
		ZSTD_dictTableLoadMethod_e	dtlm,
		ZSTD_tableFillPurpose_e	tfp
	)

Definition at line 87 of file zstd_fast.c.