zstd_ldm.c File Reference

#include "zstd_ldm.h"
#include "../common/debug.h"
#include "../common/xxhash.h"
#include "zstd_fast.h"
#include "zstd_double_fast.h"
#include "zstd_ldm_geartab.h"

Data Structures
struct	ldmRollingHashState_t

Macros
#define	LDM_BUCKET_SIZE_LOG   3
#define	LDM_MIN_MATCH_LENGTH   64
#define	LDM_HASH_RLOG   7
#define	GEAR_ITER_ONCE()
#define	GEAR_ITER_ONCE()

Functions
void	ZSTD_ldm_adjustParameters (ldmParams_t *params, ZSTD_compressionParameters const *cParams)
size_t	ZSTD_ldm_getTableSize (ldmParams_t params)
size_t	ZSTD_ldm_getMaxNbSeq (ldmParams_t params, size_t maxChunkSize)
void	ZSTD_ldm_fillHashTable (ldmState_t *ldmState, const BYTE *ip, const BYTE *iend, ldmParams_t const *params)
size_t	ZSTD_ldm_generateSequences (ldmState_t *ldmState, rawSeqStore_t *sequences, ldmParams_t const *params, void const *src, size_t srcSize)
void	ZSTD_ldm_skipSequences (rawSeqStore_t *rawSeqStore, size_t srcSize, U32 const minMatch)
void	ZSTD_ldm_skipRawSeqStoreBytes (rawSeqStore_t *rawSeqStore, size_t nbBytes)
size_t	ZSTD_ldm_blockCompress (rawSeqStore_t *rawSeqStore, ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], ZSTD_paramSwitch_e useRowMatchFinder, void const *src, size_t srcSize)

Macro Definition Documentation

GEAR_ITER_ONCE [1/2]

#define GEAR_ITER_ONCE

(

)

Value:

        do {                                  \
        hash = (hash << 1) + ZSTD_ldm_gearTab[data[n] & 0xff]; \
        n += 1;                                                \
    } while (0)

GEAR_ITER_ONCE [2/2]

#define GEAR_ITER_ONCE

(

)

Value:

        do { \
        hash = (hash << 1) + ZSTD_ldm_gearTab[data[n] & 0xff]; \
        n += 1; \
        if (UNLIKELY((hash & mask) == 0)) { \
            splits[*numSplits] = n; \
            *numSplits += 1; \
            if (*numSplits == LDM_BATCH_SIZE) \
                goto done; \
        } \
    } while (0)

LDM_BUCKET_SIZE_LOG

#define LDM_BUCKET_SIZE_LOG   3

LDM_HASH_RLOG

#define LDM_HASH_RLOG   7

LDM_MIN_MATCH_LENGTH

#define LDM_MIN_MATCH_LENGTH   64

Function Documentation

ZSTD_ldm_adjustParameters()

void ZSTD_ldm_adjustParameters	(	ldmParams_t *	params,
		ZSTD_compressionParameters const *	cParams )

ZSTD_ldm_adjustParameters() : If the params->hashRateLog is not set, set it to its default value based on windowLog and params->hashLog.

Ensures that params->bucketSizeLog is <= params->hashLog (setting it to params->hashLog if it is not).

Ensures that the minMatchLength >= targetLength during optimal parsing.

ZSTD_ldm_blockCompress()

size_t ZSTD_ldm_blockCompress	(	rawSeqStore_t *	rawSeqStore,
		ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		ZSTD_paramSwitch_e	useRowMatchFinder,
		void const *	src,
		size_t	srcSize )

ZSTD_ldm_blockCompress():

Compresses a block using the predefined sequences, along with a secondary block compressor. The literals section of every sequence is passed to the secondary block compressor, and those sequences are interspersed with the predefined sequences. Returns the length of the last literals. Updates rawSeqStore.pos to indicate how many sequences have been consumed. rawSeqStore.seq may also be updated to split the last sequence between two blocks.

Returns

The length of the last literals.

NOTE: The source must be at most the maximum block size, but the predefined sequences can be any size, and may be longer than the block. In the case that they are longer than the block, the last sequences may need to be split into two. We handle that case correctly, and update rawSeqStore appropriately. NOTE: This function does not return any errors.

ZSTD_ldm_fillHashTable()

void ZSTD_ldm_fillHashTable	(	ldmState_t *	ldmState,
		const BYTE *	ip,
		const BYTE *	iend,
		ldmParams_t const *	params )

ZSTD_ldm_generateSequences()

size_t ZSTD_ldm_generateSequences	(	ldmState_t *	ldms,
		rawSeqStore_t *	sequences,
		ldmParams_t const *	params,
		void const *	src,
		size_t	srcSize )

ZSTD_ldm_generateSequences():

Generates the sequences using the long distance match finder. Generates long range matching sequences in sequences, which parse a prefix of the source. sequences must be large enough to store every sequence, which can be checked with ZSTD_ldm_getMaxNbSeq().

Returns

0 or an error code.

NOTE: The user must have called ZSTD_window_update() for all of the input they have, even if they pass it to ZSTD_ldm_generateSequences() in chunks. NOTE: This function returns an error if it runs out of space to store sequences.

ZSTD_ldm_getMaxNbSeq()

size_t ZSTD_ldm_getMaxNbSeq	(	ldmParams_t	params,
		size_t	maxChunkSize )

ZSTD_ldm_getSeqSpace() : Return an upper bound on the number of sequences that can be produced by the long distance matcher, or 0 if LDM is disabled.

ZSTD_ldm_getTableSize()

size_t ZSTD_ldm_getTableSize

(

ldmParams_t

params

)

ZSTD_ldm_getTableSize() : Estimate the space needed for long distance matching tables or 0 if LDM is disabled.

ZSTD_ldm_skipRawSeqStoreBytes()

void ZSTD_ldm_skipRawSeqStoreBytes	(	rawSeqStore_t *	rawSeqStore,
		size_t	nbBytes )

ZSTD_ldm_skipSequences()

void ZSTD_ldm_skipSequences	(	rawSeqStore_t *	rawSeqStore,
		size_t	srcSize,
		U32 const	minMatch )

ZSTD_ldm_skipSequences():

Skip past srcSize bytes worth of sequences in rawSeqStore. Avoids emitting matches less than minMatch bytes. Must be called for data that is not passed to ZSTD_ldm_blockCompress().