#include "zstd_ldm.h"
#include "debug.h"
#include "zstd_fast.h"
#include "zstd_double_fast.h"

Include dependency graph for zstd_ldm.c:

Macros
#define	LDM_BUCKET_SIZE_LOG 3

#define	LDM_MIN_MATCH_LENGTH 64

#define	LDM_HASH_RLOG 7

#define	LDM_HASH_CHAR_OFFSET 10

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)

static U32	ZSTD_ldm_getSmallHash (U64 value, U32 numBits)

static U32	ZSTD_ldm_getChecksum (U64 hash, U32 numBitsToDiscard)

static U32	ZSTD_ldm_getTag (U64 hash, U32 hbits, U32 numTagBits)

static ldmEntry_t *	ZSTD_ldm_getBucket (ldmState_t *ldmState, size_t hash, ldmParams_t const ldmParams)

static void	ZSTD_ldm_insertEntry (ldmState_t *ldmState, size_t const hash, const ldmEntry_t entry, ldmParams_t const ldmParams)

static void	ZSTD_ldm_makeEntryAndInsertByTag (ldmState_t *ldmState, U64 const rollingHash, U32 const hBits, U32 const offset, ldmParams_t const ldmParams)

static size_t	ZSTD_ldm_countBackwardsMatch (const BYTE pIn, const BYTE pAnchor, const BYTE pMatch, const BYTE pBase)

static size_t	ZSTD_ldm_fillFastTables (ZSTD_matchState_t ms, void const end)

static U64	ZSTD_ldm_fillLdmHashTable (ldmState_t state, U64 lastHash, const BYTE lastHashed, const BYTE iend, const BYTE base, U32 hBits, ldmParams_t const ldmParams)

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

static void	ZSTD_ldm_limitTableUpdate (ZSTD_matchState_t ms, const BYTE anchor)

static size_t	ZSTD_ldm_generateSequences_internal (ldmState_t ldmState, rawSeqStore_t rawSeqStore, ldmParams_t const params, void const src, size_t srcSize)

static void	ZSTD_ldm_reduceTable (ldmEntry_t *const table, U32 const size, U32 const reducerValue)

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)

static rawSeq	maybeSplitSequence (rawSeqStore_t *rawSeqStore, U32 const remaining, U32 const minMatch)

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

Macro Definition Documentation

◆ LDM_BUCKET_SIZE_LOG

#define LDM_BUCKET_SIZE_LOG 3

Definition at line 17 of file zstd_ldm.c.

◆ LDM_HASH_CHAR_OFFSET

#define LDM_HASH_CHAR_OFFSET 10

Definition at line 20 of file zstd_ldm.c.

◆ LDM_HASH_RLOG

#define LDM_HASH_RLOG 7

Definition at line 19 of file zstd_ldm.c.

◆ LDM_MIN_MATCH_LENGTH

#define LDM_MIN_MATCH_LENGTH 64

Definition at line 18 of file zstd_ldm.c.

Function Documentation

◆ maybeSplitSequence()

static rawSeq maybeSplitSequence	(	rawSeqStore_t *	rawSeqStore,
		U32 const	remaining,
		U32 const	minMatch
	)

static

If the sequence length is longer than remaining then the sequence is split between this block and the next.

Returns the current sequence to handle, or if the rest of the block should be literals, it returns a sequence with offset == 0.

Definition at line 541 of file zstd_ldm.c.

{
    rawSeq sequence = rawSeqStore->seq[rawSeqStore->pos];
    assert(sequence.offset > 0);
    /* Likely: No partial sequence */
    if (remaining >= sequence.litLength + sequence.matchLength) {
        rawSeqStore->pos++;
        return sequence;
    }
    /* Cut the sequence short (offset == 0 ==> rest is literals). */
    if (remaining <= sequence.litLength) {
        sequence.offset = 0;
    } else if (remaining < sequence.litLength + sequence.matchLength) {
        sequence.matchLength = remaining - sequence.litLength;
        if (sequence.matchLength < minMatch) {
            sequence.offset = 0;
        }
    }
    /* Skip past `remaining` bytes for the future sequences. */
    ZSTD_ldm_skipSequences(rawSeqStore, remaining, minMatch);
    return sequence;
}

Referenced by ZSTD_ldm_blockCompress().

◆ 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.

Definition at line 22 of file zstd_ldm.c.

{
    params->windowLog = cParams->windowLog;
    ZSTD_STATIC_ASSERT(LDM_BUCKET_SIZE_LOG <= ZSTD_LDM_BUCKETSIZELOG_MAX);
    DEBUGLOG(4, "ZSTD_ldm_adjustParameters");
    if (!params->bucketSizeLog) params->bucketSizeLog = LDM_BUCKET_SIZE_LOG;
    if (!params->minMatchLength) params->minMatchLength = LDM_MIN_MATCH_LENGTH;
    if (cParams->strategy >= ZSTD_btopt) {
      /* Get out of the way of the optimal parser */
      U32 const minMatch = MAX(cParams->targetLength, params->minMatchLength);
      assert(minMatch >= ZSTD_LDM_MINMATCH_MIN);
      assert(minMatch <= ZSTD_LDM_MINMATCH_MAX);
      params->minMatchLength = minMatch;
    }
    if (params->hashLog == 0) {
        params->hashLog = MAX(ZSTD_HASHLOG_MIN, params->windowLog - LDM_HASH_RLOG);
        assert(params->hashLog <= ZSTD_HASHLOG_MAX);
    }
    if (params->hashRateLog == 0) {
        params->hashRateLog = params->windowLog < params->hashLog
                                   ? 0
                                   : params->windowLog - params->hashLog;
    }
    params->bucketSizeLog = MIN(params->bucketSizeLog, params->hashLog);
}

Referenced by ZSTD_resetCCtx_internal().

◆ ZSTD_ldm_blockCompress()

size_t ZSTD_ldm_blockCompress	(	rawSeqStore_t *	rawSeqStore,
		ZSTD_matchState_t *	ms,
		seqStore_t *	seqStore,
		U32	rep[ZSTD_REP_NUM],
		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.

Definition at line 565 of file zstd_ldm.c.

{
    const ZSTD_compressionParameters* const cParams = &ms->cParams;
    unsigned const minMatch = cParams->minMatch;
    ZSTD_blockCompressor const blockCompressor =
        ZSTD_selectBlockCompressor(cParams->strategy, ZSTD_matchState_dictMode(ms));
    /* Input bounds */
    BYTE const* const istart = (BYTE const*)src;
    BYTE const* const iend = istart + srcSize;
    /* Input positions */
    BYTE const* ip = istart;
 
    DEBUGLOG(5, "ZSTD_ldm_blockCompress: srcSize=%zu", srcSize);
    assert(rawSeqStore->pos <= rawSeqStore->size);
    assert(rawSeqStore->size <= rawSeqStore->capacity);
    /* Loop through each sequence and apply the block compressor to the lits */
    while (rawSeqStore->pos < rawSeqStore->size && ip < iend) {
        /* maybeSplitSequence updates rawSeqStore->pos */
        rawSeq const sequence = maybeSplitSequence(rawSeqStore,
                                                   (U32)(iend - ip), minMatch);
        int i;
        /* End signal */
        if (sequence.offset == 0)
            break;
 
        assert(ip + sequence.litLength + sequence.matchLength <= iend);
 
        /* Fill tables for block compressor */
        ZSTD_ldm_limitTableUpdate(ms, ip);
        ZSTD_ldm_fillFastTables(ms, ip);
        /* Run the block compressor */
        DEBUGLOG(5, "pos %u : calling block compressor on segment of size %u", (unsigned)(ip-istart), sequence.litLength);
        {
            size_t const newLitLength =
                blockCompressor(ms, seqStore, rep, ip, sequence.litLength);
            ip += sequence.litLength;
            /* Update the repcodes */
            for (i = ZSTD_REP_NUM - 1; i > 0; i--)
                rep[i] = rep[i-1];
            rep[0] = sequence.offset;
            /* Store the sequence */
            ZSTD_storeSeq(seqStore, newLitLength, ip - newLitLength, iend,
                          sequence.offset + ZSTD_REP_MOVE,
                          sequence.matchLength - MINMATCH);
            ip += sequence.matchLength;
        }
    }
    /* Fill the tables for the block compressor */
    ZSTD_ldm_limitTableUpdate(ms, ip);
    ZSTD_ldm_fillFastTables(ms, ip);
    /* Compress the last literals */
    return blockCompressor(ms, seqStore, rep, ip, iend - ip);
}

Referenced by ZSTD_buildSeqStore().

◆ ZSTD_ldm_countBackwardsMatch()

static size_t ZSTD_ldm_countBackwardsMatch	(	const BYTE *	pIn,
		const BYTE *	pAnchor,
		const BYTE *	pMatch,
		const BYTE *	pBase
	)

static

ZSTD_ldm_countBackwardsMatch() : Returns the number of bytes that match backwards before pIn and pMatch.

We count only bytes where pMatch >= pBase and pIn >= pAnchor.

Definition at line 151 of file zstd_ldm.c.

{
    size_t matchLength = 0;
    while (pIn > pAnchor && pMatch > pBase && pIn[-1] == pMatch[-1]) {
        pIn--;
        pMatch--;
        matchLength++;
    }
    return matchLength;
}

Referenced by ZSTD_ldm_generateSequences_internal().

◆ ZSTD_ldm_fillFastTables()

static size_t ZSTD_ldm_fillFastTables	(	ZSTD_matchState_t *	ms,
		void const *	end
	)

static

ZSTD_ldm_fillFastTables() :

Fills the relevant tables for the ZSTD_fast and ZSTD_dfast strategies. This is similar to ZSTD_loadDictionaryContent.

The tables for the other strategies are filled within their block compressors.

Definition at line 171 of file zstd_ldm.c.

{
    const BYTE* const iend = (const BYTE*)end;
 
    switch(ms->cParams.strategy)
    {
    case ZSTD_fast:
        ZSTD_fillHashTable(ms, iend, ZSTD_dtlm_fast);
        break;
 
    case ZSTD_dfast:
        ZSTD_fillDoubleHashTable(ms, iend, ZSTD_dtlm_fast);
        break;
 
    case ZSTD_greedy:
    case ZSTD_lazy:
    case ZSTD_lazy2:
    case ZSTD_btlazy2:
    case ZSTD_btopt:
    case ZSTD_btultra:
    case ZSTD_btultra2:
        break;
    default:
        assert(0);  /* not possible : not a valid strategy id */
    }
 
    return 0;
}

Referenced by ZSTD_ldm_blockCompress().

◆ ZSTD_ldm_fillHashTable()

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

Definition at line 227 of file zstd_ldm.c.

{
    DEBUGLOG(5, "ZSTD_ldm_fillHashTable");
    if ((size_t)(iend - ip) >= params->minMatchLength) {
        U64 startingHash = ZSTD_rollingHash_compute(ip, params->minMatchLength);
        ZSTD_ldm_fillLdmHashTable(
            state, startingHash, ip, iend - params->minMatchLength, state->window.base,
            params->hashLog - params->bucketSizeLog,
            *params);
    }
}

Referenced by ZSTD_loadDictionaryContent().

◆ ZSTD_ldm_fillLdmHashTable()

static U64 ZSTD_ldm_fillLdmHashTable	(	ldmState_t *	state,
		U64	lastHash,
		const BYTE *	lastHashed,
		const BYTE *	iend,
		const BYTE *	base,
		U32	hBits,
		ldmParams_t const	ldmParams
	)

static

ZSTD_ldm_fillLdmHashTable() :

Fills hashTable from (lastHashed + 1) to iend (non-inclusive). lastHash is the rolling hash that corresponds to lastHashed.

Returns the rolling hash corresponding to position iend-1.

Definition at line 207 of file zstd_ldm.c.

{
    U64 rollingHash = lastHash;
    const BYTE* cur = lastHashed + 1;
 
    while (cur < iend) {
        rollingHash = ZSTD_rollingHash_rotate(rollingHash, cur[-1],
                                              cur[ldmParams.minMatchLength-1],
                                              state->hashPower);
        ZSTD_ldm_makeEntryAndInsertByTag(state,
                                         rollingHash, hBits,
                                         (U32)(cur - base), ldmParams);
        ++cur;
    }
    return rollingHash;
}

Referenced by ZSTD_ldm_fillHashTable(), and ZSTD_ldm_generateSequences_internal().

◆ 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.

Definition at line 429 of file zstd_ldm.c.

{
    U32 const maxDist = 1U << params->windowLog;
    BYTE const* const istart = (BYTE const*)src;
    BYTE const* const iend = istart + srcSize;
    size_t const kMaxChunkSize = 1 << 20;
    size_t const nbChunks = (srcSize / kMaxChunkSize) + ((srcSize % kMaxChunkSize) != 0);
    size_t chunk;
    size_t leftoverSize = 0;
 
    assert(ZSTD_CHUNKSIZE_MAX >= kMaxChunkSize);
    /* Check that ZSTD_window_update() has been called for this chunk prior
     * to passing it to this function.
     */
    assert(ldmState->window.nextSrc >= (BYTE const*)src + srcSize);
    /* The input could be very large (in zstdmt), so it must be broken up into
     * chunks to enforce the maximum distance and handle overflow correction.
     */
    assert(sequences->pos <= sequences->size);
    assert(sequences->size <= sequences->capacity);
    for (chunk = 0; chunk < nbChunks && sequences->size < sequences->capacity; ++chunk) {
        BYTE const* const chunkStart = istart + chunk * kMaxChunkSize;
        size_t const remaining = (size_t)(iend - chunkStart);
        BYTE const *const chunkEnd =
            (remaining < kMaxChunkSize) ? iend : chunkStart + kMaxChunkSize;
        size_t const chunkSize = chunkEnd - chunkStart;
        size_t newLeftoverSize;
        size_t const prevSize = sequences->size;
 
        assert(chunkStart < iend);
        /* 1. Perform overflow correction if necessary. */
        if (ZSTD_window_needOverflowCorrection(ldmState->window, chunkEnd)) {
            U32 const ldmHSize = 1U << params->hashLog;
            U32 const correction = ZSTD_window_correctOverflow(
                &ldmState->window, /* cycleLog */ 0, maxDist, chunkStart);
            ZSTD_ldm_reduceTable(ldmState->hashTable, ldmHSize, correction);
            /* invalidate dictionaries on overflow correction */
            ldmState->loadedDictEnd = 0;
        }
        /* 2. We enforce the maximum offset allowed.
         *
         * kMaxChunkSize should be small enough that we don't lose too much of
         * the window through early invalidation.
         * TODO: * Test the chunk size.
         *       * Try invalidation after the sequence generation and test the
         *         the offset against maxDist directly.
         *
         * NOTE: Because of dictionaries + sequence splitting we MUST make sure
         * that any offset used is valid at the END of the sequence, since it may
         * be split into two sequences. This condition holds when using
         * ZSTD_window_enforceMaxDist(), but if we move to checking offsets
         * against maxDist directly, we'll have to carefully handle that case.
         */
        ZSTD_window_enforceMaxDist(&ldmState->window, chunkEnd, maxDist, &ldmState->loadedDictEnd, NULL);
        /* 3. Generate the sequences for the chunk, and get newLeftoverSize. */
        newLeftoverSize = ZSTD_ldm_generateSequences_internal(
            ldmState, sequences, params, chunkStart, chunkSize);
        if (ZSTD_isError(newLeftoverSize))
            return newLeftoverSize;
        /* 4. We add the leftover literals from previous iterations to the first
         *    newly generated sequence, or add the `newLeftoverSize` if none are
         *    generated.
         */
        /* Prepend the leftover literals from the last call */
        if (prevSize < sequences->size) {
            sequences->seq[prevSize].litLength += (U32)leftoverSize;
            leftoverSize = newLeftoverSize;
        } else {
            assert(newLeftoverSize == chunkSize);
            leftoverSize += chunkSize;
        }
    }
    return 0;
}

Referenced by ZSTD_buildSeqStore().

◆ ZSTD_ldm_generateSequences_internal()

static size_t ZSTD_ldm_generateSequences_internal	(	ldmState_t *	ldmState,
		rawSeqStore_t *	rawSeqStore,
		ldmParams_t const *	params,
		void const *	src,
		size_t	srcSize
	)

static

Definition at line 256 of file zstd_ldm.c.

{
    /* LDM parameters */
    int const extDict = ZSTD_window_hasExtDict(ldmState->window);
    U32 const minMatchLength = params->minMatchLength;
    U64 const hashPower = ldmState->hashPower;
    U32 const hBits = params->hashLog - params->bucketSizeLog;
    U32 const ldmBucketSize = 1U << params->bucketSizeLog;
    U32 const hashRateLog = params->hashRateLog;
    U32 const ldmTagMask = (1U << params->hashRateLog) - 1;
    /* Prefix and extDict parameters */
    U32 const dictLimit = ldmState->window.dictLimit;
    U32 const lowestIndex = extDict ? ldmState->window.lowLimit : dictLimit;
    BYTE const* const base = ldmState->window.base;
    BYTE const* const dictBase = extDict ? ldmState->window.dictBase : NULL;
    BYTE const* const dictStart = extDict ? dictBase + lowestIndex : NULL;
    BYTE const* const dictEnd = extDict ? dictBase + dictLimit : NULL;
    BYTE const* const lowPrefixPtr = base + dictLimit;
    /* Input bounds */
    BYTE const* const istart = (BYTE const*)src;
    BYTE const* const iend = istart + srcSize;
    BYTE const* const ilimit = iend - MAX(minMatchLength, HASH_READ_SIZE);
    /* Input positions */
    BYTE const* anchor = istart;
    BYTE const* ip = istart;
    /* Rolling hash */
    BYTE const* lastHashed = NULL;
    U64 rollingHash = 0;
 
    while (ip <= ilimit) {
        size_t mLength;
        U32 const current = (U32)(ip - base);
        size_t forwardMatchLength = 0, backwardMatchLength = 0;
        ldmEntry_t* bestEntry = NULL;
        if (ip != istart) {
            rollingHash = ZSTD_rollingHash_rotate(rollingHash, lastHashed[0],
                                                  lastHashed[minMatchLength],
                                                  hashPower);
        } else {
            rollingHash = ZSTD_rollingHash_compute(ip, minMatchLength);
        }
        lastHashed = ip;
 
        /* Do not insert and do not look for a match */
        if (ZSTD_ldm_getTag(rollingHash, hBits, hashRateLog) != ldmTagMask) {
           ip++;
           continue;
        }
 
        /* Get the best entry and compute the match lengths */
        {
            ldmEntry_t* const bucket =
                ZSTD_ldm_getBucket(ldmState,
                                   ZSTD_ldm_getSmallHash(rollingHash, hBits),
                                   *params);
            ldmEntry_t* cur;
            size_t bestMatchLength = 0;
            U32 const checksum = ZSTD_ldm_getChecksum(rollingHash, hBits);
 
            for (cur = bucket; cur < bucket + ldmBucketSize; ++cur) {
                size_t curForwardMatchLength, curBackwardMatchLength,
                       curTotalMatchLength;
                if (cur->checksum != checksum || cur->offset <= lowestIndex) {
                    continue;
                }
                if (extDict) {
                    BYTE const* const curMatchBase =
                        cur->offset < dictLimit ? dictBase : base;
                    BYTE const* const pMatch = curMatchBase + cur->offset;
                    BYTE const* const matchEnd =
                        cur->offset < dictLimit ? dictEnd : iend;
                    BYTE const* const lowMatchPtr =
                        cur->offset < dictLimit ? dictStart : lowPrefixPtr;
 
                    curForwardMatchLength = ZSTD_count_2segments(
                                                ip, pMatch, iend,
                                                matchEnd, lowPrefixPtr);
                    if (curForwardMatchLength < minMatchLength) {
                        continue;
                    }
                    curBackwardMatchLength =
                        ZSTD_ldm_countBackwardsMatch(ip, anchor, pMatch,
                                                     lowMatchPtr);
                    curTotalMatchLength = curForwardMatchLength +
                                          curBackwardMatchLength;
                } else { /* !extDict */
                    BYTE const* const pMatch = base + cur->offset;
                    curForwardMatchLength = ZSTD_count(ip, pMatch, iend);
                    if (curForwardMatchLength < minMatchLength) {
                        continue;
                    }
                    curBackwardMatchLength =
                        ZSTD_ldm_countBackwardsMatch(ip, anchor, pMatch,
                                                     lowPrefixPtr);
                    curTotalMatchLength = curForwardMatchLength +
                                          curBackwardMatchLength;
                }
 
                if (curTotalMatchLength > bestMatchLength) {
                    bestMatchLength = curTotalMatchLength;
                    forwardMatchLength = curForwardMatchLength;
                    backwardMatchLength = curBackwardMatchLength;
                    bestEntry = cur;
                }
            }
        }
 
        /* No match found -- continue searching */
        if (bestEntry == NULL) {
            ZSTD_ldm_makeEntryAndInsertByTag(ldmState, rollingHash,
                                             hBits, current,
                                             *params);
            ip++;
            continue;
        }
 
        /* Match found */
        mLength = forwardMatchLength + backwardMatchLength;
        ip -= backwardMatchLength;
 
        {
            /* Store the sequence:
             * ip = current - backwardMatchLength
             * The match is at (bestEntry->offset - backwardMatchLength)
             */
            U32 const matchIndex = bestEntry->offset;
            U32 const offset = current - matchIndex;
            rawSeq* const seq = rawSeqStore->seq + rawSeqStore->size;
 
            /* Out of sequence storage */
            if (rawSeqStore->size == rawSeqStore->capacity)
                return ERROR(dstSize_tooSmall);
            seq->litLength = (U32)(ip - anchor);
            seq->matchLength = (U32)mLength;
            seq->offset = offset;
            rawSeqStore->size++;
        }
 
        /* Insert the current entry into the hash table */
        ZSTD_ldm_makeEntryAndInsertByTag(ldmState, rollingHash, hBits,
                                         (U32)(lastHashed - base),
                                         *params);
 
        assert(ip + backwardMatchLength == lastHashed);
 
        /* Fill the hash table from lastHashed+1 to ip+mLength*/
        /* Heuristic: don't need to fill the entire table at end of block */
        if (ip + mLength <= ilimit) {
            rollingHash = ZSTD_ldm_fillLdmHashTable(
                              ldmState, rollingHash, lastHashed,
                              ip + mLength, base, hBits, *params);
            lastHashed = ip + mLength - 1;
        }
        ip += mLength;
        anchor = ip;
    }
    return iend - anchor;
}

Referenced by ZSTD_ldm_generateSequences().

◆ ZSTD_ldm_getBucket()

static ldmEntry_t * ZSTD_ldm_getBucket	(	ldmState_t *	ldmState,
		size_t	hash,
		ldmParams_t const	ldmParams
	)

static

ZSTD_ldm_getBucket() : Returns a pointer to the start of the bucket associated with hash.

Definition at line 101 of file zstd_ldm.c.

{
    return ldmState->hashTable + (hash << ldmParams.bucketSizeLog);
}

Referenced by ZSTD_ldm_generateSequences_internal(), and ZSTD_ldm_insertEntry().

◆ ZSTD_ldm_getChecksum()

static U32 ZSTD_ldm_getChecksum	(	U64	hash,
		U32	numBitsToDiscard
	)

static

ZSTD_ldm_getChecksum() : numBitsToDiscard should be <= 32

Returns: : the next most significant 32 bits after numBitsToDiscard

Definition at line 77 of file zstd_ldm.c.

{
    assert(numBitsToDiscard <= 32);
    return (hash >> (64 - 32 - numBitsToDiscard)) & 0xFFFFFFFF;
}

Referenced by ZSTD_ldm_generateSequences_internal(), and ZSTD_ldm_makeEntryAndInsertByTag().

◆ 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.

Definition at line 59 of file zstd_ldm.c.

{
    return params.enableLdm ? (maxChunkSize / params.minMatchLength) : 0;
}

Referenced by ZSTD_estimateCCtxSize_usingCCtxParams(), and ZSTD_resetCCtx_internal().

◆ ZSTD_ldm_getSmallHash()

static U32 ZSTD_ldm_getSmallHash	(	U64	value,
		U32	numBits
	)

static

ZSTD_ldm_getSmallHash() : numBits should be <= 32 If numBits==0, returns 0.

Returns: : the most significant numBits of value.

Definition at line 68 of file zstd_ldm.c.

{
    assert(numBits <= 32);
    return numBits == 0 ? 0 : (U32)(value >> (64 - numBits));
}

Referenced by ZSTD_ldm_generateSequences_internal(), and ZSTD_ldm_makeEntryAndInsertByTag().

◆ 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.

Definition at line 49 of file zstd_ldm.c.

{
    size_t const ldmHSize = ((size_t)1) << params.hashLog;
    size_t const ldmBucketSizeLog = MIN(params.bucketSizeLog, params.hashLog);
    size_t const ldmBucketSize = ((size_t)1) << (params.hashLog - ldmBucketSizeLog);
    size_t const totalSize = ZSTD_cwksp_alloc_size(ldmBucketSize)
                           + ZSTD_cwksp_alloc_size(ldmHSize * sizeof(ldmEntry_t));
    return params.enableLdm ? totalSize : 0;
}

Referenced by ZSTD_estimateCCtxSize_usingCCtxParams(), and ZSTD_resetCCtx_internal().

◆ ZSTD_ldm_getTag()

static U32 ZSTD_ldm_getTag	(	U64	hash,
		U32	hbits,
		U32	numTagBits
	)

static

ZSTD_ldm_getTag() ; Given the hash, returns the most significant numTagBits bits after (32 + hbits) bits.

If there are not enough bits remaining, return the last numTagBits bits.

Definition at line 89 of file zstd_ldm.c.

{
    assert(numTagBits < 32 && hbits <= 32);
    if (32 - hbits < numTagBits) {
        return hash & (((U32)1 << numTagBits) - 1);
    } else {
        return (hash >> (32 - hbits - numTagBits)) & (((U32)1 << numTagBits) - 1);
    }
}

Referenced by ZSTD_ldm_generateSequences_internal(), and ZSTD_ldm_makeEntryAndInsertByTag().

◆ ZSTD_ldm_insertEntry()

static void ZSTD_ldm_insertEntry	(	ldmState_t *	ldmState,
		size_t const	hash,
		const ldmEntry_t	entry,
		ldmParams_t const	ldmParams
	)

static

ZSTD_ldm_insertEntry() : Insert the entry with corresponding hash into the hash table

Definition at line 109 of file zstd_ldm.c.

{
    BYTE* const bucketOffsets = ldmState->bucketOffsets;
    *(ZSTD_ldm_getBucket(ldmState, hash, ldmParams) + bucketOffsets[hash]) = entry;
    bucketOffsets[hash]++;
    bucketOffsets[hash] &= ((U32)1 << ldmParams.bucketSizeLog) - 1;
}

Referenced by ZSTD_ldm_makeEntryAndInsertByTag().

◆ ZSTD_ldm_limitTableUpdate()

static void ZSTD_ldm_limitTableUpdate	(	ZSTD_matchState_t *	ms,
		const BYTE *	anchor
	)

static

ZSTD_ldm_limitTableUpdate() :

Sets cctx->nextToUpdate to a position corresponding closer to anchor if it is far way (after a long match, only update tables a limited amount).

Definition at line 247 of file zstd_ldm.c.

{
    U32 const current = (U32)(anchor - ms->window.base);
    if (current > ms->nextToUpdate + 1024) {
        ms->nextToUpdate =
            current - MIN(512, current - ms->nextToUpdate - 1024);
    }
}

Referenced by ZSTD_ldm_blockCompress().

◆ ZSTD_ldm_makeEntryAndInsertByTag()

static void ZSTD_ldm_makeEntryAndInsertByTag	(	ldmState_t *	ldmState,
		U64 const	rollingHash,
		U32 const	hBits,
		U32 const	offset,
		ldmParams_t const	ldmParams
	)

static

ZSTD_ldm_makeEntryAndInsertByTag() :

Gets the small hash, checksum, and tag from the rollingHash.

If the tag matches (1 << ldmParams.hashRateLog)-1, then creates an ldmEntry from the offset, and inserts it into the hash table.

hBits is the length of the small hash, which is the most significant hBits of rollingHash. The checksum is the next 32 most significant bits, followed by ldmParams.hashRateLog bits that make up the tag.

Definition at line 129 of file zstd_ldm.c.

{
    U32 const tag = ZSTD_ldm_getTag(rollingHash, hBits, ldmParams.hashRateLog);
    U32 const tagMask = ((U32)1 << ldmParams.hashRateLog) - 1;
    if (tag == tagMask) {
        U32 const hash = ZSTD_ldm_getSmallHash(rollingHash, hBits);
        U32 const checksum = ZSTD_ldm_getChecksum(rollingHash, hBits);
        ldmEntry_t entry;
        entry.offset = offset;
        entry.checksum = checksum;
        ZSTD_ldm_insertEntry(ldmState, hash, entry, ldmParams);
    }
}

Referenced by ZSTD_ldm_fillLdmHashTable(), and ZSTD_ldm_generateSequences_internal().

◆ ZSTD_ldm_reduceTable()

static void ZSTD_ldm_reduceTable	(	ldmEntry_t *const	table,
		U32 const	size,
		U32 const	reducerValue
	)

static

ZSTD_ldm_reduceTable() : reduce table indexes by reducerValue

Definition at line 419 of file zstd_ldm.c.

{
    U32 u;
    for (u = 0; u < size; u++) {
        if (table[u].offset < reducerValue) table[u].offset = 0;
        else table[u].offset -= reducerValue;
    }
}

Referenced by ZSTD_ldm_generateSequences().

◆ 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 with is not passed to ZSTD_ldm_blockCompress().

Definition at line 506 of file zstd_ldm.c.

                                                                                            {
    while (srcSize > 0 && rawSeqStore->pos < rawSeqStore->size) {
        rawSeq* seq = rawSeqStore->seq + rawSeqStore->pos;
        if (srcSize <= seq->litLength) {
            /* Skip past srcSize literals */
            seq->litLength -= (U32)srcSize;
            return;
        }
        srcSize -= seq->litLength;
        seq->litLength = 0;
        if (srcSize < seq->matchLength) {
            /* Skip past the first srcSize of the match */
            seq->matchLength -= (U32)srcSize;
            if (seq->matchLength < minMatch) {
                /* The match is too short, omit it */
                if (rawSeqStore->pos + 1 < rawSeqStore->size) {
                    seq[1].litLength += seq[0].matchLength;
                }
                rawSeqStore->pos++;
            }
            return;
        }
        srcSize -= seq->matchLength;
        seq->matchLength = 0;
        rawSeqStore->pos++;
    }
}

Referenced by maybeSplitSequence(), and ZSTD_buildSeqStore().

Macros

Functions

Macro Definition Documentation

◆ LDM_BUCKET_SIZE_LOG

◆ LDM_HASH_CHAR_OFFSET

◆ LDM_HASH_RLOG

◆ LDM_MIN_MATCH_LENGTH

Function Documentation

◆ maybeSplitSequence()

◆ ZSTD_ldm_adjustParameters()

◆ ZSTD_ldm_blockCompress()

◆ ZSTD_ldm_countBackwardsMatch()

◆ ZSTD_ldm_fillFastTables()

◆ ZSTD_ldm_fillHashTable()

◆ ZSTD_ldm_fillLdmHashTable()

◆ ZSTD_ldm_generateSequences()

◆ ZSTD_ldm_generateSequences_internal()

◆ ZSTD_ldm_getBucket()

◆ ZSTD_ldm_getChecksum()

◆ ZSTD_ldm_getMaxNbSeq()

◆ ZSTD_ldm_getSmallHash()

◆ ZSTD_ldm_getTableSize()

◆ ZSTD_ldm_getTag()

◆ ZSTD_ldm_insertEntry()

◆ ZSTD_ldm_limitTableUpdate()

◆ ZSTD_ldm_makeEntryAndInsertByTag()

◆ ZSTD_ldm_reduceTable()

◆ ZSTD_ldm_skipSequences()