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