zstd_ldm.c

  1// SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause
  2/*
  3 * Copyright (c) Meta Platforms, Inc. and affiliates.
  4 * All rights reserved.
  5 *
  6 * This source code is licensed under both the BSD-style license (found in the
  7 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
  8 * in the COPYING file in the root directory of this source tree).
  9 * You may select, at your option, one of the above-listed licenses.
 10 */
 11
 12#include "zstd_ldm.h"
 13
 14#include "../common/debug.h"
 15#include <linux/xxhash.h>
 16#include "zstd_fast.h"          /* ZSTD_fillHashTable() */
 17#include "zstd_double_fast.h"   /* ZSTD_fillDoubleHashTable() */
 18#include "zstd_ldm_geartab.h"
 19
 20#define LDM_BUCKET_SIZE_LOG 4
 21#define LDM_MIN_MATCH_LENGTH 64
 22#define LDM_HASH_RLOG 7
 23
 24typedef struct {
 25    U64 rolling;
 26    U64 stopMask;
 27} ldmRollingHashState_t;
 28
 29/* ZSTD_ldm_gear_init():
 30 *
 31 * Initializes the rolling hash state such that it will honor the
 32 * settings in params. */
 33static void ZSTD_ldm_gear_init(ldmRollingHashState_t* state, ldmParams_t const* params)
 34{
 35    unsigned maxBitsInMask = MIN(params->minMatchLength, 64);
 36    unsigned hashRateLog = params->hashRateLog;
 37
 38    state->rolling = ~(U32)0;
 39
 40    /* The choice of the splitting criterion is subject to two conditions:
 41     *   1. it has to trigger on average every 2^(hashRateLog) bytes;
 42     *   2. ideally, it has to depend on a window of minMatchLength bytes.
 43     *
 44     * In the gear hash algorithm, bit n depends on the last n bytes;
 45     * so in order to obtain a good quality splitting criterion it is
 46     * preferable to use bits with high weight.
 47     *
 48     * To match condition 1 we use a mask with hashRateLog bits set
 49     * and, because of the previous remark, we make sure these bits
 50     * have the highest possible weight while still respecting
 51     * condition 2.
 52     */
 53    if (hashRateLog > 0 && hashRateLog <= maxBitsInMask) {
 54        state->stopMask = (((U64)1 << hashRateLog) - 1) << (maxBitsInMask - hashRateLog);
 55    } else {
 56        /* In this degenerate case we simply honor the hash rate. */
 57        state->stopMask = ((U64)1 << hashRateLog) - 1;
 58    }
 59}
 60
 61/* ZSTD_ldm_gear_reset()
 62 * Feeds [data, data + minMatchLength) into the hash without registering any
 63 * splits. This effectively resets the hash state. This is used when skipping
 64 * over data, either at the beginning of a block, or skipping sections.
 65 */
 66static void ZSTD_ldm_gear_reset(ldmRollingHashState_t* state,
 67                                BYTE const* data, size_t minMatchLength)
 68{
 69    U64 hash = state->rolling;
 70    size_t n = 0;
 71
 72#define GEAR_ITER_ONCE() do {                                  \
 73        hash = (hash << 1) + ZSTD_ldm_gearTab[data[n] & 0xff]; \
 74        n += 1;                                                \
 75    } while (0)
 76    while (n + 3 < minMatchLength) {
 77        GEAR_ITER_ONCE();
 78        GEAR_ITER_ONCE();
 79        GEAR_ITER_ONCE();
 80        GEAR_ITER_ONCE();
 81    }
 82    while (n < minMatchLength) {
 83        GEAR_ITER_ONCE();
 84    }
 85#undef GEAR_ITER_ONCE
 86}
 87
 88/* ZSTD_ldm_gear_feed():
 89 *
 90 * Registers in the splits array all the split points found in the first
 91 * size bytes following the data pointer. This function terminates when
 92 * either all the data has been processed or LDM_BATCH_SIZE splits are
 93 * present in the splits array.
 94 *
 95 * Precondition: The splits array must not be full.
 96 * Returns: The number of bytes processed. */
 97static size_t ZSTD_ldm_gear_feed(ldmRollingHashState_t* state,
 98                                 BYTE const* data, size_t size,
 99                                 size_t* splits, unsigned* numSplits)
100{
101    size_t n;
102    U64 hash, mask;
103
104    hash = state->rolling;
105    mask = state->stopMask;
106    n = 0;
107
108#define GEAR_ITER_ONCE() do { \
109        hash = (hash << 1) + ZSTD_ldm_gearTab[data[n] & 0xff]; \
110        n += 1; \
111        if (UNLIKELY((hash & mask) == 0)) { \
112            splits[*numSplits] = n; \
113            *numSplits += 1; \
114            if (*numSplits == LDM_BATCH_SIZE) \
115                goto done; \
116        } \
117    } while (0)
118
119    while (n + 3 < size) {
120        GEAR_ITER_ONCE();
121        GEAR_ITER_ONCE();
122        GEAR_ITER_ONCE();
123        GEAR_ITER_ONCE();
124    }
125    while (n < size) {
126        GEAR_ITER_ONCE();
127    }
128
129#undef GEAR_ITER_ONCE
130
131done:
132    state->rolling = hash;
133    return n;
134}
135
136void ZSTD_ldm_adjustParameters(ldmParams_t* params,
137                        const ZSTD_compressionParameters* cParams)
138{
139    params->windowLog = cParams->windowLog;
140    ZSTD_STATIC_ASSERT(LDM_BUCKET_SIZE_LOG <= ZSTD_LDM_BUCKETSIZELOG_MAX);
141    DEBUGLOG(4, "ZSTD_ldm_adjustParameters");
142    if (params->hashRateLog == 0) {
143        if (params->hashLog > 0) {
144            /* if params->hashLog is set, derive hashRateLog from it */
145            assert(params->hashLog <= ZSTD_HASHLOG_MAX);
146            if (params->windowLog > params->hashLog) {
147                params->hashRateLog = params->windowLog - params->hashLog;
148            }
149        } else {
150            assert(1 <= (int)cParams->strategy && (int)cParams->strategy <= 9);
151            /* mapping from [fast, rate7] to [btultra2, rate4] */
152            params->hashRateLog = 7 - (cParams->strategy/3);
153        }
154    }
155    if (params->hashLog == 0) {
156        params->hashLog = BOUNDED(ZSTD_HASHLOG_MIN, params->windowLog - params->hashRateLog, ZSTD_HASHLOG_MAX);
157    }
158    if (params->minMatchLength == 0) {
159        params->minMatchLength = LDM_MIN_MATCH_LENGTH;
160        if (cParams->strategy >= ZSTD_btultra)
161            params->minMatchLength /= 2;
162    }
163    if (params->bucketSizeLog==0) {
164        assert(1 <= (int)cParams->strategy && (int)cParams->strategy <= 9);
165        params->bucketSizeLog = BOUNDED(LDM_BUCKET_SIZE_LOG, (U32)cParams->strategy, ZSTD_LDM_BUCKETSIZELOG_MAX);
166    }
167    params->bucketSizeLog = MIN(params->bucketSizeLog, params->hashLog);
168}
169
170size_t ZSTD_ldm_getTableSize(ldmParams_t params)
171{
172    size_t const ldmHSize = ((size_t)1) << params.hashLog;
173    size_t const ldmBucketSizeLog = MIN(params.bucketSizeLog, params.hashLog);
174    size_t const ldmBucketSize = ((size_t)1) << (params.hashLog - ldmBucketSizeLog);
175    size_t const totalSize = ZSTD_cwksp_alloc_size(ldmBucketSize)
176                           + ZSTD_cwksp_alloc_size(ldmHSize * sizeof(ldmEntry_t));
177    return params.enableLdm == ZSTD_ps_enable ? totalSize : 0;
178}
179
180size_t ZSTD_ldm_getMaxNbSeq(ldmParams_t params, size_t maxChunkSize)
181{
182    return params.enableLdm == ZSTD_ps_enable ? (maxChunkSize / params.minMatchLength) : 0;
183}
184
185/* ZSTD_ldm_getBucket() :
186 *  Returns a pointer to the start of the bucket associated with hash. */
187static ldmEntry_t* ZSTD_ldm_getBucket(
188        const ldmState_t* ldmState, size_t hash, U32 const bucketSizeLog)
189{
190    return ldmState->hashTable + (hash << bucketSizeLog);
191}
192
193/* ZSTD_ldm_insertEntry() :
194 *  Insert the entry with corresponding hash into the hash table */
195static void ZSTD_ldm_insertEntry(ldmState_t* ldmState,
196                                 size_t const hash, const ldmEntry_t entry,
197                                 U32 const bucketSizeLog)
198{
199    BYTE* const pOffset = ldmState->bucketOffsets + hash;
200    unsigned const offset = *pOffset;
201
202    *(ZSTD_ldm_getBucket(ldmState, hash, bucketSizeLog) + offset) = entry;
203    *pOffset = (BYTE)((offset + 1) & ((1u << bucketSizeLog) - 1));
204
205}
206
207/* ZSTD_ldm_countBackwardsMatch() :
208 *  Returns the number of bytes that match backwards before pIn and pMatch.
209 *
210 *  We count only bytes where pMatch >= pBase and pIn >= pAnchor. */
211static size_t ZSTD_ldm_countBackwardsMatch(
212            const BYTE* pIn, const BYTE* pAnchor,
213            const BYTE* pMatch, const BYTE* pMatchBase)
214{
215    size_t matchLength = 0;
216    while (pIn > pAnchor && pMatch > pMatchBase && pIn[-1] == pMatch[-1]) {
217        pIn--;
218        pMatch--;
219        matchLength++;
220    }
221    return matchLength;
222}
223
224/* ZSTD_ldm_countBackwardsMatch_2segments() :
225 *  Returns the number of bytes that match backwards from pMatch,
226 *  even with the backwards match spanning 2 different segments.
227 *
228 *  On reaching `pMatchBase`, start counting from mEnd */
229static size_t ZSTD_ldm_countBackwardsMatch_2segments(
230                    const BYTE* pIn, const BYTE* pAnchor,
231                    const BYTE* pMatch, const BYTE* pMatchBase,
232                    const BYTE* pExtDictStart, const BYTE* pExtDictEnd)
233{
234    size_t matchLength = ZSTD_ldm_countBackwardsMatch(pIn, pAnchor, pMatch, pMatchBase);
235    if (pMatch - matchLength != pMatchBase || pMatchBase == pExtDictStart) {
236        /* If backwards match is entirely in the extDict or prefix, immediately return */
237        return matchLength;
238    }
239    DEBUGLOG(7, "ZSTD_ldm_countBackwardsMatch_2segments: found 2-parts backwards match (length in prefix==%zu)", matchLength);
240    matchLength += ZSTD_ldm_countBackwardsMatch(pIn - matchLength, pAnchor, pExtDictEnd, pExtDictStart);
241    DEBUGLOG(7, "final backwards match length = %zu", matchLength);
242    return matchLength;
243}
244
245/* ZSTD_ldm_fillFastTables() :
246 *
247 *  Fills the relevant tables for the ZSTD_fast and ZSTD_dfast strategies.
248 *  This is similar to ZSTD_loadDictionaryContent.
249 *
250 *  The tables for the other strategies are filled within their
251 *  block compressors. */
252static size_t ZSTD_ldm_fillFastTables(ZSTD_MatchState_t* ms,
253                                      void const* end)
254{
255    const BYTE* const iend = (const BYTE*)end;
256
257    switch(ms->cParams.strategy)
258    {
259    case ZSTD_fast:
260        ZSTD_fillHashTable(ms, iend, ZSTD_dtlm_fast, ZSTD_tfp_forCCtx);
261        break;
262
263    case ZSTD_dfast:
264#ifndef ZSTD_EXCLUDE_DFAST_BLOCK_COMPRESSOR
265        ZSTD_fillDoubleHashTable(ms, iend, ZSTD_dtlm_fast, ZSTD_tfp_forCCtx);
266#else
267        assert(0); /* shouldn't be called: cparams should've been adjusted. */
268#endif
269        break;
270
271    case ZSTD_greedy:
272    case ZSTD_lazy:
273    case ZSTD_lazy2:
274    case ZSTD_btlazy2:
275    case ZSTD_btopt:
276    case ZSTD_btultra:
277    case ZSTD_btultra2:
278        break;
279    default:
280        assert(0);  /* not possible : not a valid strategy id */
281    }
282
283    return 0;
284}
285
286void ZSTD_ldm_fillHashTable(
287            ldmState_t* ldmState, const BYTE* ip,
288            const BYTE* iend, ldmParams_t const* params)
289{
290    U32 const minMatchLength = params->minMatchLength;
291    U32 const bucketSizeLog = params->bucketSizeLog;
292    U32 const hBits = params->hashLog - bucketSizeLog;
293    BYTE const* const base = ldmState->window.base;
294    BYTE const* const istart = ip;
295    ldmRollingHashState_t hashState;
296    size_t* const splits = ldmState->splitIndices;
297    unsigned numSplits;
298
299    DEBUGLOG(5, "ZSTD_ldm_fillHashTable");
300
301    ZSTD_ldm_gear_init(&hashState, params);
302    while (ip < iend) {
303        size_t hashed;
304        unsigned n;
305
306        numSplits = 0;
307        hashed = ZSTD_ldm_gear_feed(&hashState, ip, (size_t)(iend - ip), splits, &numSplits);
308
309        for (n = 0; n < numSplits; n++) {
310            if (ip + splits[n] >= istart + minMatchLength) {
311                BYTE const* const split = ip + splits[n] - minMatchLength;
312                U64 const xxhash = xxh64(split, minMatchLength, 0);
313                U32 const hash = (U32)(xxhash & (((U32)1 << hBits) - 1));
314                ldmEntry_t entry;
315
316                entry.offset = (U32)(split - base);
317                entry.checksum = (U32)(xxhash >> 32);
318                ZSTD_ldm_insertEntry(ldmState, hash, entry, params->bucketSizeLog);
319            }
320        }
321
322        ip += hashed;
323    }
324}
325
326
327/* ZSTD_ldm_limitTableUpdate() :
328 *
329 *  Sets cctx->nextToUpdate to a position corresponding closer to anchor
330 *  if it is far way
331 *  (after a long match, only update tables a limited amount). */
332static void ZSTD_ldm_limitTableUpdate(ZSTD_MatchState_t* ms, const BYTE* anchor)
333{
334    U32 const curr = (U32)(anchor - ms->window.base);
335    if (curr > ms->nextToUpdate + 1024) {
336        ms->nextToUpdate =
337            curr - MIN(512, curr - ms->nextToUpdate - 1024);
338    }
339}
340
341static
342ZSTD_ALLOW_POINTER_OVERFLOW_ATTR
343size_t ZSTD_ldm_generateSequences_internal(
344        ldmState_t* ldmState, RawSeqStore_t* rawSeqStore,
345        ldmParams_t const* params, void const* src, size_t srcSize)
346{
347    /* LDM parameters */
348    int const extDict = ZSTD_window_hasExtDict(ldmState->window);
349    U32 const minMatchLength = params->minMatchLength;
350    U32 const entsPerBucket = 1U << params->bucketSizeLog;
351    U32 const hBits = params->hashLog - params->bucketSizeLog;
352    /* Prefix and extDict parameters */
353    U32 const dictLimit = ldmState->window.dictLimit;
354    U32 const lowestIndex = extDict ? ldmState->window.lowLimit : dictLimit;
355    BYTE const* const base = ldmState->window.base;
356    BYTE const* const dictBase = extDict ? ldmState->window.dictBase : NULL;
357    BYTE const* const dictStart = extDict ? dictBase + lowestIndex : NULL;
358    BYTE const* const dictEnd = extDict ? dictBase + dictLimit : NULL;
359    BYTE const* const lowPrefixPtr = base + dictLimit;
360    /* Input bounds */
361    BYTE const* const istart = (BYTE const*)src;
362    BYTE const* const iend = istart + srcSize;
363    BYTE const* const ilimit = iend - HASH_READ_SIZE;
364    /* Input positions */
365    BYTE const* anchor = istart;
366    BYTE const* ip = istart;
367    /* Rolling hash state */
368    ldmRollingHashState_t hashState;
369    /* Arrays for staged-processing */
370    size_t* const splits = ldmState->splitIndices;
371    ldmMatchCandidate_t* const candidates = ldmState->matchCandidates;
372    unsigned numSplits;
373
374    if (srcSize < minMatchLength)
375        return iend - anchor;
376
377    /* Initialize the rolling hash state with the first minMatchLength bytes */
378    ZSTD_ldm_gear_init(&hashState, params);
379    ZSTD_ldm_gear_reset(&hashState, ip, minMatchLength);
380    ip += minMatchLength;
381
382    while (ip < ilimit) {
383        size_t hashed;
384        unsigned n;
385
386        numSplits = 0;
387        hashed = ZSTD_ldm_gear_feed(&hashState, ip, ilimit - ip,
388                                    splits, &numSplits);
389
390        for (n = 0; n < numSplits; n++) {
391            BYTE const* const split = ip + splits[n] - minMatchLength;
392            U64 const xxhash = xxh64(split, minMatchLength, 0);
393            U32 const hash = (U32)(xxhash & (((U32)1 << hBits) - 1));
394
395            candidates[n].split = split;
396            candidates[n].hash = hash;
397            candidates[n].checksum = (U32)(xxhash >> 32);
398            candidates[n].bucket = ZSTD_ldm_getBucket(ldmState, hash, params->bucketSizeLog);
399            PREFETCH_L1(candidates[n].bucket);
400        }
401
402        for (n = 0; n < numSplits; n++) {
403            size_t forwardMatchLength = 0, backwardMatchLength = 0,
404                   bestMatchLength = 0, mLength;
405            U32 offset;
406            BYTE const* const split = candidates[n].split;
407            U32 const checksum = candidates[n].checksum;
408            U32 const hash = candidates[n].hash;
409            ldmEntry_t* const bucket = candidates[n].bucket;
410            ldmEntry_t const* cur;
411            ldmEntry_t const* bestEntry = NULL;
412            ldmEntry_t newEntry;
413
414            newEntry.offset = (U32)(split - base);
415            newEntry.checksum = checksum;
416
417            /* If a split point would generate a sequence overlapping with
418             * the previous one, we merely register it in the hash table and
419             * move on */
420            if (split < anchor) {
421                ZSTD_ldm_insertEntry(ldmState, hash, newEntry, params->bucketSizeLog);
422                continue;
423            }
424
425            for (cur = bucket; cur < bucket + entsPerBucket; cur++) {
426                size_t curForwardMatchLength, curBackwardMatchLength,
427                       curTotalMatchLength;
428                if (cur->checksum != checksum || cur->offset <= lowestIndex) {
429                    continue;
430                }
431                if (extDict) {
432                    BYTE const* const curMatchBase =
433                        cur->offset < dictLimit ? dictBase : base;
434                    BYTE const* const pMatch = curMatchBase + cur->offset;
435                    BYTE const* const matchEnd =
436                        cur->offset < dictLimit ? dictEnd : iend;
437                    BYTE const* const lowMatchPtr =
438                        cur->offset < dictLimit ? dictStart : lowPrefixPtr;
439                    curForwardMatchLength =
440                        ZSTD_count_2segments(split, pMatch, iend, matchEnd, lowPrefixPtr);
441                    if (curForwardMatchLength < minMatchLength) {
442                        continue;
443                    }
444                    curBackwardMatchLength = ZSTD_ldm_countBackwardsMatch_2segments(
445                            split, anchor, pMatch, lowMatchPtr, dictStart, dictEnd);
446                } else { /* !extDict */
447                    BYTE const* const pMatch = base + cur->offset;
448                    curForwardMatchLength = ZSTD_count(split, pMatch, iend);
449                    if (curForwardMatchLength < minMatchLength) {
450                        continue;
451                    }
452                    curBackwardMatchLength =
453                        ZSTD_ldm_countBackwardsMatch(split, anchor, pMatch, lowPrefixPtr);
454                }
455                curTotalMatchLength = curForwardMatchLength + curBackwardMatchLength;
456
457                if (curTotalMatchLength > bestMatchLength) {
458                    bestMatchLength = curTotalMatchLength;
459                    forwardMatchLength = curForwardMatchLength;
460                    backwardMatchLength = curBackwardMatchLength;
461                    bestEntry = cur;
462                }
463            }
464
465            /* No match found -- insert an entry into the hash table
466             * and process the next candidate match */
467            if (bestEntry == NULL) {
468                ZSTD_ldm_insertEntry(ldmState, hash, newEntry, params->bucketSizeLog);
469                continue;
470            }
471
472            /* Match found */
473            offset = (U32)(split - base) - bestEntry->offset;
474            mLength = forwardMatchLength + backwardMatchLength;
475            {
476                rawSeq* const seq = rawSeqStore->seq + rawSeqStore->size;
477
478                /* Out of sequence storage */
479                if (rawSeqStore->size == rawSeqStore->capacity)
480                    return ERROR(dstSize_tooSmall);
481                seq->litLength = (U32)(split - backwardMatchLength - anchor);
482                seq->matchLength = (U32)mLength;
483                seq->offset = offset;
484                rawSeqStore->size++;
485            }
486
487            /* Insert the current entry into the hash table --- it must be
488             * done after the previous block to avoid clobbering bestEntry */
489            ZSTD_ldm_insertEntry(ldmState, hash, newEntry, params->bucketSizeLog);
490
491            anchor = split + forwardMatchLength;
492
493            /* If we find a match that ends after the data that we've hashed
494             * then we have a repeating, overlapping, pattern. E.g. all zeros.
495             * If one repetition of the pattern matches our `stopMask` then all
496             * repetitions will. We don't need to insert them all into out table,
497             * only the first one. So skip over overlapping matches.
498             * This is a major speed boost (20x) for compressing a single byte
499             * repeated, when that byte ends up in the table.
500             */
501            if (anchor > ip + hashed) {
502                ZSTD_ldm_gear_reset(&hashState, anchor - minMatchLength, minMatchLength);
503                /* Continue the outer loop at anchor (ip + hashed == anchor). */
504                ip = anchor - hashed;
505                break;
506            }
507        }
508
509        ip += hashed;
510    }
511
512    return iend - anchor;
513}
514
515/*! ZSTD_ldm_reduceTable() :
516 *  reduce table indexes by `reducerValue` */
517static void ZSTD_ldm_reduceTable(ldmEntry_t* const table, U32 const size,
518                                 U32 const reducerValue)
519{
520    U32 u;
521    for (u = 0; u < size; u++) {
522        if (table[u].offset < reducerValue) table[u].offset = 0;
523        else table[u].offset -= reducerValue;
524    }
525}
526
527size_t ZSTD_ldm_generateSequences(
528        ldmState_t* ldmState, RawSeqStore_t* sequences,
529        ldmParams_t const* params, void const* src, size_t srcSize)
530{
531    U32 const maxDist = 1U << params->windowLog;
532    BYTE const* const istart = (BYTE const*)src;
533    BYTE const* const iend = istart + srcSize;
534    size_t const kMaxChunkSize = 1 << 20;
535    size_t const nbChunks = (srcSize / kMaxChunkSize) + ((srcSize % kMaxChunkSize) != 0);
536    size_t chunk;
537    size_t leftoverSize = 0;
538
539    assert(ZSTD_CHUNKSIZE_MAX >= kMaxChunkSize);
540    /* Check that ZSTD_window_update() has been called for this chunk prior
541     * to passing it to this function.
542     */
543    assert(ldmState->window.nextSrc >= (BYTE const*)src + srcSize);
544    /* The input could be very large (in zstdmt), so it must be broken up into
545     * chunks to enforce the maximum distance and handle overflow correction.
546     */
547    assert(sequences->pos <= sequences->size);
548    assert(sequences->size <= sequences->capacity);
549    for (chunk = 0; chunk < nbChunks && sequences->size < sequences->capacity; ++chunk) {
550        BYTE const* const chunkStart = istart + chunk * kMaxChunkSize;
551        size_t const remaining = (size_t)(iend - chunkStart);
552        BYTE const *const chunkEnd =
553            (remaining < kMaxChunkSize) ? iend : chunkStart + kMaxChunkSize;
554        size_t const chunkSize = chunkEnd - chunkStart;
555        size_t newLeftoverSize;
556        size_t const prevSize = sequences->size;
557
558        assert(chunkStart < iend);
559        /* 1. Perform overflow correction if necessary. */
560        if (ZSTD_window_needOverflowCorrection(ldmState->window, 0, maxDist, ldmState->loadedDictEnd, chunkStart, chunkEnd)) {
561            U32 const ldmHSize = 1U << params->hashLog;
562            U32 const correction = ZSTD_window_correctOverflow(
563                &ldmState->window, /* cycleLog */ 0, maxDist, chunkStart);
564            ZSTD_ldm_reduceTable(ldmState->hashTable, ldmHSize, correction);
565            /* invalidate dictionaries on overflow correction */
566            ldmState->loadedDictEnd = 0;
567        }
568        /* 2. We enforce the maximum offset allowed.
569         *
570         * kMaxChunkSize should be small enough that we don't lose too much of
571         * the window through early invalidation.
572         * TODO: * Test the chunk size.
573         *       * Try invalidation after the sequence generation and test the
574         *         offset against maxDist directly.
575         *
576         * NOTE: Because of dictionaries + sequence splitting we MUST make sure
577         * that any offset used is valid at the END of the sequence, since it may
578         * be split into two sequences. This condition holds when using
579         * ZSTD_window_enforceMaxDist(), but if we move to checking offsets
580         * against maxDist directly, we'll have to carefully handle that case.
581         */
582        ZSTD_window_enforceMaxDist(&ldmState->window, chunkEnd, maxDist, &ldmState->loadedDictEnd, NULL);
583        /* 3. Generate the sequences for the chunk, and get newLeftoverSize. */
584        newLeftoverSize = ZSTD_ldm_generateSequences_internal(
585            ldmState, sequences, params, chunkStart, chunkSize);
586        if (ZSTD_isError(newLeftoverSize))
587            return newLeftoverSize;
588        /* 4. We add the leftover literals from previous iterations to the first
589         *    newly generated sequence, or add the `newLeftoverSize` if none are
590         *    generated.
591         */
592        /* Prepend the leftover literals from the last call */
593        if (prevSize < sequences->size) {
594            sequences->seq[prevSize].litLength += (U32)leftoverSize;
595            leftoverSize = newLeftoverSize;
596        } else {
597            assert(newLeftoverSize == chunkSize);
598            leftoverSize += chunkSize;
599        }
600    }
601    return 0;
602}
603
604void
605ZSTD_ldm_skipSequences(RawSeqStore_t* rawSeqStore, size_t srcSize, U32 const minMatch)
606{
607    while (srcSize > 0 && rawSeqStore->pos < rawSeqStore->size) {
608        rawSeq* seq = rawSeqStore->seq + rawSeqStore->pos;
609        if (srcSize <= seq->litLength) {
610            /* Skip past srcSize literals */
611            seq->litLength -= (U32)srcSize;
612            return;
613        }
614        srcSize -= seq->litLength;
615        seq->litLength = 0;
616        if (srcSize < seq->matchLength) {
617            /* Skip past the first srcSize of the match */
618            seq->matchLength -= (U32)srcSize;
619            if (seq->matchLength < minMatch) {
620                /* The match is too short, omit it */
621                if (rawSeqStore->pos + 1 < rawSeqStore->size) {
622                    seq[1].litLength += seq[0].matchLength;
623                }
624                rawSeqStore->pos++;
625            }
626            return;
627        }
628        srcSize -= seq->matchLength;
629        seq->matchLength = 0;
630        rawSeqStore->pos++;
631    }
632}
633
634/*
635 * If the sequence length is longer than remaining then the sequence is split
636 * between this block and the next.
637 *
638 * Returns the current sequence to handle, or if the rest of the block should
639 * be literals, it returns a sequence with offset == 0.
640 */
641static rawSeq maybeSplitSequence(RawSeqStore_t* rawSeqStore,
642                                 U32 const remaining, U32 const minMatch)
643{
644    rawSeq sequence = rawSeqStore->seq[rawSeqStore->pos];
645    assert(sequence.offset > 0);
646    /* Likely: No partial sequence */
647    if (remaining >= sequence.litLength + sequence.matchLength) {
648        rawSeqStore->pos++;
649        return sequence;
650    }
651    /* Cut the sequence short (offset == 0 ==> rest is literals). */
652    if (remaining <= sequence.litLength) {
653        sequence.offset = 0;
654    } else if (remaining < sequence.litLength + sequence.matchLength) {
655        sequence.matchLength = remaining - sequence.litLength;
656        if (sequence.matchLength < minMatch) {
657            sequence.offset = 0;
658        }
659    }
660    /* Skip past `remaining` bytes for the future sequences. */
661    ZSTD_ldm_skipSequences(rawSeqStore, remaining, minMatch);
662    return sequence;
663}
664
665void ZSTD_ldm_skipRawSeqStoreBytes(RawSeqStore_t* rawSeqStore, size_t nbBytes) {
666    U32 currPos = (U32)(rawSeqStore->posInSequence + nbBytes);
667    while (currPos && rawSeqStore->pos < rawSeqStore->size) {
668        rawSeq currSeq = rawSeqStore->seq[rawSeqStore->pos];
669        if (currPos >= currSeq.litLength + currSeq.matchLength) {
670            currPos -= currSeq.litLength + currSeq.matchLength;
671            rawSeqStore->pos++;
672        } else {
673            rawSeqStore->posInSequence = currPos;
674            break;
675        }
676    }
677    if (currPos == 0 || rawSeqStore->pos == rawSeqStore->size) {
678        rawSeqStore->posInSequence = 0;
679    }
680}
681
682size_t ZSTD_ldm_blockCompress(RawSeqStore_t* rawSeqStore,
683    ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
684    ZSTD_ParamSwitch_e useRowMatchFinder,
685    void const* src, size_t srcSize)
686{
687    const ZSTD_compressionParameters* const cParams = &ms->cParams;
688    unsigned const minMatch = cParams->minMatch;
689    ZSTD_BlockCompressor_f const blockCompressor =
690        ZSTD_selectBlockCompressor(cParams->strategy, useRowMatchFinder, ZSTD_matchState_dictMode(ms));
691    /* Input bounds */
692    BYTE const* const istart = (BYTE const*)src;
693    BYTE const* const iend = istart + srcSize;
694    /* Input positions */
695    BYTE const* ip = istart;
696
697    DEBUGLOG(5, "ZSTD_ldm_blockCompress: srcSize=%zu", srcSize);
698    /* If using opt parser, use LDMs only as candidates rather than always accepting them */
699    if (cParams->strategy >= ZSTD_btopt) {
700        size_t lastLLSize;
701        ms->ldmSeqStore = rawSeqStore;
702        lastLLSize = blockCompressor(ms, seqStore, rep, src, srcSize);
703        ZSTD_ldm_skipRawSeqStoreBytes(rawSeqStore, srcSize);
704        return lastLLSize;
705    }
706
707    assert(rawSeqStore->pos <= rawSeqStore->size);
708    assert(rawSeqStore->size <= rawSeqStore->capacity);
709    /* Loop through each sequence and apply the block compressor to the literals */
710    while (rawSeqStore->pos < rawSeqStore->size && ip < iend) {
711        /* maybeSplitSequence updates rawSeqStore->pos */
712        rawSeq const sequence = maybeSplitSequence(rawSeqStore,
713                                                   (U32)(iend - ip), minMatch);
714        /* End signal */
715        if (sequence.offset == 0)
716            break;
717
718        assert(ip + sequence.litLength + sequence.matchLength <= iend);
719
720        /* Fill tables for block compressor */
721        ZSTD_ldm_limitTableUpdate(ms, ip);
722        ZSTD_ldm_fillFastTables(ms, ip);
723        /* Run the block compressor */
724        DEBUGLOG(5, "pos %u : calling block compressor on segment of size %u", (unsigned)(ip-istart), sequence.litLength);
725        {
726            int i;
727            size_t const newLitLength =
728                blockCompressor(ms, seqStore, rep, ip, sequence.litLength);
729            ip += sequence.litLength;
730            /* Update the repcodes */
731            for (i = ZSTD_REP_NUM - 1; i > 0; i--)
732                rep[i] = rep[i-1];
733            rep[0] = sequence.offset;
734            /* Store the sequence */
735            ZSTD_storeSeq(seqStore, newLitLength, ip - newLitLength, iend,
736                          OFFSET_TO_OFFBASE(sequence.offset),
737                          sequence.matchLength);
738            ip += sequence.matchLength;
739        }
740    }
741    /* Fill the tables for the block compressor */
742    ZSTD_ldm_limitTableUpdate(ms, ip);
743    ZSTD_ldm_fillFastTables(ms, ip);
744    /* Compress the last literals */
745    return blockCompressor(ms, seqStore, rep, ip, iend - ip);
746}