1 /*
2  * Copyright (c) 2016-2020, 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 "debug.h"
14 #include "zstd_fast.h"          /* ZSTD_fillHashTable() */
15 #include "zstd_double_fast.h"   /* ZSTD_fillDoubleHashTable() */
16 
17 #define LDM_BUCKET_SIZE_LOG 3
18 #define LDM_MIN_MATCH_LENGTH 64
19 #define LDM_HASH_RLOG 7
20 #define LDM_HASH_CHAR_OFFSET 10
21 
ZSTD_ldm_adjustParameters(ldmParams_t * params,ZSTD_compressionParameters const * cParams)22 void ZSTD_ldm_adjustParameters(ldmParams_t* params,
23                                ZSTD_compressionParameters const* cParams)
24 {
25     params->windowLog = cParams->windowLog;
26     ZSTD_STATIC_ASSERT(LDM_BUCKET_SIZE_LOG <= ZSTD_LDM_BUCKETSIZELOG_MAX);
27     DEBUGLOG(4, "ZSTD_ldm_adjustParameters");
28     if (!params->bucketSizeLog) params->bucketSizeLog = LDM_BUCKET_SIZE_LOG;
29     if (!params->minMatchLength) params->minMatchLength = LDM_MIN_MATCH_LENGTH;
30     if (cParams->strategy >= ZSTD_btopt) {
31       /* Get out of the way of the optimal parser */
32       U32 const minMatch = MAX(cParams->targetLength, params->minMatchLength);
33       assert(minMatch >= ZSTD_LDM_MINMATCH_MIN);
34       assert(minMatch <= ZSTD_LDM_MINMATCH_MAX);
35       params->minMatchLength = minMatch;
36     }
37     if (params->hashLog == 0) {
38         params->hashLog = MAX(ZSTD_HASHLOG_MIN, params->windowLog - LDM_HASH_RLOG);
39         assert(params->hashLog <= ZSTD_HASHLOG_MAX);
40     }
41     if (params->hashRateLog == 0) {
42         params->hashRateLog = params->windowLog < params->hashLog
43                                    ? 0
44                                    : params->windowLog - params->hashLog;
45     }
46     params->bucketSizeLog = MIN(params->bucketSizeLog, params->hashLog);
47 }
48 
ZSTD_ldm_getTableSize(ldmParams_t params)49 size_t ZSTD_ldm_getTableSize(ldmParams_t params)
50 {
51     size_t const ldmHSize = ((size_t)1) << params.hashLog;
52     size_t const ldmBucketSizeLog = MIN(params.bucketSizeLog, params.hashLog);
53     size_t const ldmBucketSize = ((size_t)1) << (params.hashLog - ldmBucketSizeLog);
54     size_t const totalSize = ZSTD_cwksp_alloc_size(ldmBucketSize)
55                            + ZSTD_cwksp_alloc_size(ldmHSize * sizeof(ldmEntry_t));
56     return params.enableLdm ? totalSize : 0;
57 }
58 
ZSTD_ldm_getMaxNbSeq(ldmParams_t params,size_t maxChunkSize)59 size_t ZSTD_ldm_getMaxNbSeq(ldmParams_t params, size_t maxChunkSize)
60 {
61     return params.enableLdm ? (maxChunkSize / params.minMatchLength) : 0;
62 }
63 
64 /** ZSTD_ldm_getSmallHash() :
65  *  numBits should be <= 32
66  *  If numBits==0, returns 0.
67  *  @return : the most significant numBits of value. */
ZSTD_ldm_getSmallHash(U64 value,U32 numBits)68 static U32 ZSTD_ldm_getSmallHash(U64 value, U32 numBits)
69 {
70     assert(numBits <= 32);
71     return numBits == 0 ? 0 : (U32)(value >> (64 - numBits));
72 }
73 
74 /** ZSTD_ldm_getChecksum() :
75  *  numBitsToDiscard should be <= 32
76  *  @return : the next most significant 32 bits after numBitsToDiscard */
ZSTD_ldm_getChecksum(U64 hash,U32 numBitsToDiscard)77 static U32 ZSTD_ldm_getChecksum(U64 hash, U32 numBitsToDiscard)
78 {
79     assert(numBitsToDiscard <= 32);
80     return (hash >> (64 - 32 - numBitsToDiscard)) & 0xFFFFFFFF;
81 }
82 
83 /** ZSTD_ldm_getTag() ;
84  *  Given the hash, returns the most significant numTagBits bits
85  *  after (32 + hbits) bits.
86  *
87  *  If there are not enough bits remaining, return the last
88  *  numTagBits bits. */
ZSTD_ldm_getTag(U64 hash,U32 hbits,U32 numTagBits)89 static U32 ZSTD_ldm_getTag(U64 hash, U32 hbits, U32 numTagBits)
90 {
91     assert(numTagBits < 32 && hbits <= 32);
92     if (32 - hbits < numTagBits) {
93         return hash & (((U32)1 << numTagBits) - 1);
94     } else {
95         return (hash >> (32 - hbits - numTagBits)) & (((U32)1 << numTagBits) - 1);
96     }
97 }
98 
99 /** ZSTD_ldm_getBucket() :
100  *  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)101 static ldmEntry_t* ZSTD_ldm_getBucket(
102         ldmState_t* ldmState, size_t hash, ldmParams_t const ldmParams)
103 {
104     return ldmState->hashTable + (hash << ldmParams.bucketSizeLog);
105 }
106 
107 /** ZSTD_ldm_insertEntry() :
108  *  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)109 static void ZSTD_ldm_insertEntry(ldmState_t* ldmState,
110                                  size_t const hash, const ldmEntry_t entry,
111                                  ldmParams_t const ldmParams)
112 {
113     BYTE* const bucketOffsets = ldmState->bucketOffsets;
114     *(ZSTD_ldm_getBucket(ldmState, hash, ldmParams) + bucketOffsets[hash]) = entry;
115     bucketOffsets[hash]++;
116     bucketOffsets[hash] &= ((U32)1 << ldmParams.bucketSizeLog) - 1;
117 }
118 
119 /** ZSTD_ldm_makeEntryAndInsertByTag() :
120  *
121  *  Gets the small hash, checksum, and tag from the rollingHash.
122  *
123  *  If the tag matches (1 << ldmParams.hashRateLog)-1, then
124  *  creates an ldmEntry from the offset, and inserts it into the hash table.
125  *
126  *  hBits is the length of the small hash, which is the most significant hBits
127  *  of rollingHash. The checksum is the next 32 most significant bits, followed
128  *  by ldmParams.hashRateLog bits that make up the tag. */
ZSTD_ldm_makeEntryAndInsertByTag(ldmState_t * ldmState,U64 const rollingHash,U32 const hBits,U32 const offset,ldmParams_t const ldmParams)129 static void ZSTD_ldm_makeEntryAndInsertByTag(ldmState_t* ldmState,
130                                              U64 const rollingHash,
131                                              U32 const hBits,
132                                              U32 const offset,
133                                              ldmParams_t const ldmParams)
134 {
135     U32 const tag = ZSTD_ldm_getTag(rollingHash, hBits, ldmParams.hashRateLog);
136     U32 const tagMask = ((U32)1 << ldmParams.hashRateLog) - 1;
137     if (tag == tagMask) {
138         U32 const hash = ZSTD_ldm_getSmallHash(rollingHash, hBits);
139         U32 const checksum = ZSTD_ldm_getChecksum(rollingHash, hBits);
140         ldmEntry_t entry;
141         entry.offset = offset;
142         entry.checksum = checksum;
143         ZSTD_ldm_insertEntry(ldmState, hash, entry, ldmParams);
144     }
145 }
146 
147 /** ZSTD_ldm_countBackwardsMatch() :
148  *  Returns the number of bytes that match backwards before pIn and pMatch.
149  *
150  *  We count only bytes where pMatch >= pBase and pIn >= pAnchor. */
ZSTD_ldm_countBackwardsMatch(const BYTE * pIn,const BYTE * pAnchor,const BYTE * pMatch,const BYTE * pBase)151 static size_t ZSTD_ldm_countBackwardsMatch(
152             const BYTE* pIn, const BYTE* pAnchor,
153             const BYTE* pMatch, const BYTE* pBase)
154 {
155     size_t matchLength = 0;
156     while (pIn > pAnchor && pMatch > pBase && pIn[-1] == pMatch[-1]) {
157         pIn--;
158         pMatch--;
159         matchLength++;
160     }
161     return matchLength;
162 }
163 
164 /** ZSTD_ldm_fillFastTables() :
165  *
166  *  Fills the relevant tables for the ZSTD_fast and ZSTD_dfast strategies.
167  *  This is similar to ZSTD_loadDictionaryContent.
168  *
169  *  The tables for the other strategies are filled within their
170  *  block compressors. */
ZSTD_ldm_fillFastTables(ZSTD_matchState_t * ms,void const * end)171 static size_t ZSTD_ldm_fillFastTables(ZSTD_matchState_t* ms,
172                                       void const* end)
173 {
174     const BYTE* const iend = (const BYTE*)end;
175 
176     switch(ms->cParams.strategy)
177     {
178     case ZSTD_fast:
179         ZSTD_fillHashTable(ms, iend, ZSTD_dtlm_fast);
180         break;
181 
182     case ZSTD_dfast:
183         ZSTD_fillDoubleHashTable(ms, iend, ZSTD_dtlm_fast);
184         break;
185 
186     case ZSTD_greedy:
187     case ZSTD_lazy:
188     case ZSTD_lazy2:
189     case ZSTD_btlazy2:
190     case ZSTD_btopt:
191     case ZSTD_btultra:
192     case ZSTD_btultra2:
193         break;
194     default:
195         assert(0);  /* not possible : not a valid strategy id */
196     }
197 
198     return 0;
199 }
200 
201 /** ZSTD_ldm_fillLdmHashTable() :
202  *
203  *  Fills hashTable from (lastHashed + 1) to iend (non-inclusive).
204  *  lastHash is the rolling hash that corresponds to lastHashed.
205  *
206  *  Returns the rolling hash corresponding to position iend-1. */
ZSTD_ldm_fillLdmHashTable(ldmState_t * state,U64 lastHash,const BYTE * lastHashed,const BYTE * iend,const BYTE * base,U32 hBits,ldmParams_t const ldmParams)207 static U64 ZSTD_ldm_fillLdmHashTable(ldmState_t* state,
208                                      U64 lastHash, const BYTE* lastHashed,
209                                      const BYTE* iend, const BYTE* base,
210                                      U32 hBits, ldmParams_t const ldmParams)
211 {
212     U64 rollingHash = lastHash;
213     const BYTE* cur = lastHashed + 1;
214 
215     while (cur < iend) {
216         rollingHash = ZSTD_rollingHash_rotate(rollingHash, cur[-1],
217                                               cur[ldmParams.minMatchLength-1],
218                                               state->hashPower);
219         ZSTD_ldm_makeEntryAndInsertByTag(state,
220                                          rollingHash, hBits,
221                                          (U32)(cur - base), ldmParams);
222         ++cur;
223     }
224     return rollingHash;
225 }
226 
ZSTD_ldm_fillHashTable(ldmState_t * state,const BYTE * ip,const BYTE * iend,ldmParams_t const * params)227 void ZSTD_ldm_fillHashTable(
228             ldmState_t* state, const BYTE* ip,
229             const BYTE* iend, ldmParams_t const* params)
230 {
231     DEBUGLOG(5, "ZSTD_ldm_fillHashTable");
232     if ((size_t)(iend - ip) >= params->minMatchLength) {
233         U64 startingHash = ZSTD_rollingHash_compute(ip, params->minMatchLength);
234         ZSTD_ldm_fillLdmHashTable(
235             state, startingHash, ip, iend - params->minMatchLength, state->window.base,
236             params->hashLog - params->bucketSizeLog,
237             *params);
238     }
239 }
240 
241 
242 /** ZSTD_ldm_limitTableUpdate() :
243  *
244  *  Sets cctx->nextToUpdate to a position corresponding closer to anchor
245  *  if it is far way
246  *  (after a long match, only update tables a limited amount). */
ZSTD_ldm_limitTableUpdate(ZSTD_matchState_t * ms,const BYTE * anchor)247 static void ZSTD_ldm_limitTableUpdate(ZSTD_matchState_t* ms, const BYTE* anchor)
248 {
249     U32 const current = (U32)(anchor - ms->window.base);
250     if (current > ms->nextToUpdate + 1024) {
251         ms->nextToUpdate =
252             current - MIN(512, current - ms->nextToUpdate - 1024);
253     }
254 }
255 
ZSTD_ldm_generateSequences_internal(ldmState_t * ldmState,rawSeqStore_t * rawSeqStore,ldmParams_t const * params,void const * src,size_t srcSize)256 static size_t ZSTD_ldm_generateSequences_internal(
257         ldmState_t* ldmState, rawSeqStore_t* rawSeqStore,
258         ldmParams_t const* params, void const* src, size_t srcSize)
259 {
260     /* LDM parameters */
261     int const extDict = ZSTD_window_hasExtDict(ldmState->window);
262     U32 const minMatchLength = params->minMatchLength;
263     U64 const hashPower = ldmState->hashPower;
264     U32 const hBits = params->hashLog - params->bucketSizeLog;
265     U32 const ldmBucketSize = 1U << params->bucketSizeLog;
266     U32 const hashRateLog = params->hashRateLog;
267     U32 const ldmTagMask = (1U << params->hashRateLog) - 1;
268     /* Prefix and extDict parameters */
269     U32 const dictLimit = ldmState->window.dictLimit;
270     U32 const lowestIndex = extDict ? ldmState->window.lowLimit : dictLimit;
271     BYTE const* const base = ldmState->window.base;
272     BYTE const* const dictBase = extDict ? ldmState->window.dictBase : NULL;
273     BYTE const* const dictStart = extDict ? dictBase + lowestIndex : NULL;
274     BYTE const* const dictEnd = extDict ? dictBase + dictLimit : NULL;
275     BYTE const* const lowPrefixPtr = base + dictLimit;
276     /* Input bounds */
277     BYTE const* const istart = (BYTE const*)src;
278     BYTE const* const iend = istart + srcSize;
279     BYTE const* const ilimit = iend - MAX(minMatchLength, HASH_READ_SIZE);
280     /* Input positions */
281     BYTE const* anchor = istart;
282     BYTE const* ip = istart;
283     /* Rolling hash */
284     BYTE const* lastHashed = NULL;
285     U64 rollingHash = 0;
286 
287     while (ip <= ilimit) {
288         size_t mLength;
289         U32 const current = (U32)(ip - base);
290         size_t forwardMatchLength = 0, backwardMatchLength = 0;
291         ldmEntry_t* bestEntry = NULL;
292         if (ip != istart) {
293             rollingHash = ZSTD_rollingHash_rotate(rollingHash, lastHashed[0],
294                                                   lastHashed[minMatchLength],
295                                                   hashPower);
296         } else {
297             rollingHash = ZSTD_rollingHash_compute(ip, minMatchLength);
298         }
299         lastHashed = ip;
300 
301         /* Do not insert and do not look for a match */
302         if (ZSTD_ldm_getTag(rollingHash, hBits, hashRateLog) != ldmTagMask) {
303            ip++;
304            continue;
305         }
306 
307         /* Get the best entry and compute the match lengths */
308         {
309             ldmEntry_t* const bucket =
310                 ZSTD_ldm_getBucket(ldmState,
311                                    ZSTD_ldm_getSmallHash(rollingHash, hBits),
312                                    *params);
313             ldmEntry_t* cur;
314             size_t bestMatchLength = 0;
315             U32 const checksum = ZSTD_ldm_getChecksum(rollingHash, hBits);
316 
317             for (cur = bucket; cur < bucket + ldmBucketSize; ++cur) {
318                 size_t curForwardMatchLength, curBackwardMatchLength,
319                        curTotalMatchLength;
320                 if (cur->checksum != checksum || cur->offset <= lowestIndex) {
321                     continue;
322                 }
323                 if (extDict) {
324                     BYTE const* const curMatchBase =
325                         cur->offset < dictLimit ? dictBase : base;
326                     BYTE const* const pMatch = curMatchBase + cur->offset;
327                     BYTE const* const matchEnd =
328                         cur->offset < dictLimit ? dictEnd : iend;
329                     BYTE const* const lowMatchPtr =
330                         cur->offset < dictLimit ? dictStart : lowPrefixPtr;
331 
332                     curForwardMatchLength = ZSTD_count_2segments(
333                                                 ip, pMatch, iend,
334                                                 matchEnd, lowPrefixPtr);
335                     if (curForwardMatchLength < minMatchLength) {
336                         continue;
337                     }
338                     curBackwardMatchLength =
339                         ZSTD_ldm_countBackwardsMatch(ip, anchor, pMatch,
340                                                      lowMatchPtr);
341                     curTotalMatchLength = curForwardMatchLength +
342                                           curBackwardMatchLength;
343                 } else { /* !extDict */
344                     BYTE const* const pMatch = base + cur->offset;
345                     curForwardMatchLength = ZSTD_count(ip, pMatch, iend);
346                     if (curForwardMatchLength < minMatchLength) {
347                         continue;
348                     }
349                     curBackwardMatchLength =
350                         ZSTD_ldm_countBackwardsMatch(ip, anchor, pMatch,
351                                                      lowPrefixPtr);
352                     curTotalMatchLength = curForwardMatchLength +
353                                           curBackwardMatchLength;
354                 }
355 
356                 if (curTotalMatchLength > bestMatchLength) {
357                     bestMatchLength = curTotalMatchLength;
358                     forwardMatchLength = curForwardMatchLength;
359                     backwardMatchLength = curBackwardMatchLength;
360                     bestEntry = cur;
361                 }
362             }
363         }
364 
365         /* No match found -- continue searching */
366         if (bestEntry == NULL) {
367             ZSTD_ldm_makeEntryAndInsertByTag(ldmState, rollingHash,
368                                              hBits, current,
369                                              *params);
370             ip++;
371             continue;
372         }
373 
374         /* Match found */
375         mLength = forwardMatchLength + backwardMatchLength;
376         ip -= backwardMatchLength;
377 
378         {
379             /* Store the sequence:
380              * ip = current - backwardMatchLength
381              * The match is at (bestEntry->offset - backwardMatchLength)
382              */
383             U32 const matchIndex = bestEntry->offset;
384             U32 const offset = current - matchIndex;
385             rawSeq* const seq = rawSeqStore->seq + rawSeqStore->size;
386 
387             /* Out of sequence storage */
388             if (rawSeqStore->size == rawSeqStore->capacity)
389                 return ERROR(dstSize_tooSmall);
390             seq->litLength = (U32)(ip - anchor);
391             seq->matchLength = (U32)mLength;
392             seq->offset = offset;
393             rawSeqStore->size++;
394         }
395 
396         /* Insert the current entry into the hash table */
397         ZSTD_ldm_makeEntryAndInsertByTag(ldmState, rollingHash, hBits,
398                                          (U32)(lastHashed - base),
399                                          *params);
400 
401         assert(ip + backwardMatchLength == lastHashed);
402 
403         /* Fill the hash table from lastHashed+1 to ip+mLength*/
404         /* Heuristic: don't need to fill the entire table at end of block */
405         if (ip + mLength <= ilimit) {
406             rollingHash = ZSTD_ldm_fillLdmHashTable(
407                               ldmState, rollingHash, lastHashed,
408                               ip + mLength, base, hBits, *params);
409             lastHashed = ip + mLength - 1;
410         }
411         ip += mLength;
412         anchor = ip;
413     }
414     return iend - anchor;
415 }
416 
417 /*! ZSTD_ldm_reduceTable() :
418  *  reduce table indexes by `reducerValue` */
ZSTD_ldm_reduceTable(ldmEntry_t * const table,U32 const size,U32 const reducerValue)419 static void ZSTD_ldm_reduceTable(ldmEntry_t* const table, U32 const size,
420                                  U32 const reducerValue)
421 {
422     U32 u;
423     for (u = 0; u < size; u++) {
424         if (table[u].offset < reducerValue) table[u].offset = 0;
425         else table[u].offset -= reducerValue;
426     }
427 }
428 
ZSTD_ldm_generateSequences(ldmState_t * ldmState,rawSeqStore_t * sequences,ldmParams_t const * params,void const * src,size_t srcSize)429 size_t ZSTD_ldm_generateSequences(
430         ldmState_t* ldmState, rawSeqStore_t* sequences,
431         ldmParams_t const* params, void const* src, size_t srcSize)
432 {
433     U32 const maxDist = 1U << params->windowLog;
434     BYTE const* const istart = (BYTE const*)src;
435     BYTE const* const iend = istart + srcSize;
436     size_t const kMaxChunkSize = 1 << 20;
437     size_t const nbChunks = (srcSize / kMaxChunkSize) + ((srcSize % kMaxChunkSize) != 0);
438     size_t chunk;
439     size_t leftoverSize = 0;
440 
441     assert(ZSTD_CHUNKSIZE_MAX >= kMaxChunkSize);
442     /* Check that ZSTD_window_update() has been called for this chunk prior
443      * to passing it to this function.
444      */
445     assert(ldmState->window.nextSrc >= (BYTE const*)src + srcSize);
446     /* The input could be very large (in zstdmt), so it must be broken up into
447      * chunks to enforce the maximum distance and handle overflow correction.
448      */
449     assert(sequences->pos <= sequences->size);
450     assert(sequences->size <= sequences->capacity);
451     for (chunk = 0; chunk < nbChunks && sequences->size < sequences->capacity; ++chunk) {
452         BYTE const* const chunkStart = istart + chunk * kMaxChunkSize;
453         size_t const remaining = (size_t)(iend - chunkStart);
454         BYTE const *const chunkEnd =
455             (remaining < kMaxChunkSize) ? iend : chunkStart + kMaxChunkSize;
456         size_t const chunkSize = chunkEnd - chunkStart;
457         size_t newLeftoverSize;
458         size_t const prevSize = sequences->size;
459 
460         assert(chunkStart < iend);
461         /* 1. Perform overflow correction if necessary. */
462         if (ZSTD_window_needOverflowCorrection(ldmState->window, chunkEnd)) {
463             U32 const ldmHSize = 1U << params->hashLog;
464             U32 const correction = ZSTD_window_correctOverflow(
465                 &ldmState->window, /* cycleLog */ 0, maxDist, chunkStart);
466             ZSTD_ldm_reduceTable(ldmState->hashTable, ldmHSize, correction);
467             /* invalidate dictionaries on overflow correction */
468             ldmState->loadedDictEnd = 0;
469         }
470         /* 2. We enforce the maximum offset allowed.
471          *
472          * kMaxChunkSize should be small enough that we don't lose too much of
473          * the window through early invalidation.
474          * TODO: * Test the chunk size.
475          *       * Try invalidation after the sequence generation and test the
476          *         the offset against maxDist directly.
477          *
478          * NOTE: Because of dictionaries + sequence splitting we MUST make sure
479          * that any offset used is valid at the END of the sequence, since it may
480          * be split into two sequences. This condition holds when using
481          * ZSTD_window_enforceMaxDist(), but if we move to checking offsets
482          * against maxDist directly, we'll have to carefully handle that case.
483          */
484         ZSTD_window_enforceMaxDist(&ldmState->window, chunkEnd, maxDist, &ldmState->loadedDictEnd, NULL);
485         /* 3. Generate the sequences for the chunk, and get newLeftoverSize. */
486         newLeftoverSize = ZSTD_ldm_generateSequences_internal(
487             ldmState, sequences, params, chunkStart, chunkSize);
488         if (ZSTD_isError(newLeftoverSize))
489             return newLeftoverSize;
490         /* 4. We add the leftover literals from previous iterations to the first
491          *    newly generated sequence, or add the `newLeftoverSize` if none are
492          *    generated.
493          */
494         /* Prepend the leftover literals from the last call */
495         if (prevSize < sequences->size) {
496             sequences->seq[prevSize].litLength += (U32)leftoverSize;
497             leftoverSize = newLeftoverSize;
498         } else {
499             assert(newLeftoverSize == chunkSize);
500             leftoverSize += chunkSize;
501         }
502     }
503     return 0;
504 }
505 
ZSTD_ldm_skipSequences(rawSeqStore_t * rawSeqStore,size_t srcSize,U32 const minMatch)506 void ZSTD_ldm_skipSequences(rawSeqStore_t* rawSeqStore, size_t srcSize, U32 const minMatch) {
507     while (srcSize > 0 && rawSeqStore->pos < rawSeqStore->size) {
508         rawSeq* seq = rawSeqStore->seq + rawSeqStore->pos;
509         if (srcSize <= seq->litLength) {
510             /* Skip past srcSize literals */
511             seq->litLength -= (U32)srcSize;
512             return;
513         }
514         srcSize -= seq->litLength;
515         seq->litLength = 0;
516         if (srcSize < seq->matchLength) {
517             /* Skip past the first srcSize of the match */
518             seq->matchLength -= (U32)srcSize;
519             if (seq->matchLength < minMatch) {
520                 /* The match is too short, omit it */
521                 if (rawSeqStore->pos + 1 < rawSeqStore->size) {
522                     seq[1].litLength += seq[0].matchLength;
523                 }
524                 rawSeqStore->pos++;
525             }
526             return;
527         }
528         srcSize -= seq->matchLength;
529         seq->matchLength = 0;
530         rawSeqStore->pos++;
531     }
532 }
533 
534 /**
535  * If the sequence length is longer than remaining then the sequence is split
536  * between this block and the next.
537  *
538  * Returns the current sequence to handle, or if the rest of the block should
539  * be literals, it returns a sequence with offset == 0.
540  */
maybeSplitSequence(rawSeqStore_t * rawSeqStore,U32 const remaining,U32 const minMatch)541 static rawSeq maybeSplitSequence(rawSeqStore_t* rawSeqStore,
542                                  U32 const remaining, U32 const minMatch)
543 {
544     rawSeq sequence = rawSeqStore->seq[rawSeqStore->pos];
545     assert(sequence.offset > 0);
546     /* Likely: No partial sequence */
547     if (remaining >= sequence.litLength + sequence.matchLength) {
548         rawSeqStore->pos++;
549         return sequence;
550     }
551     /* Cut the sequence short (offset == 0 ==> rest is literals). */
552     if (remaining <= sequence.litLength) {
553         sequence.offset = 0;
554     } else if (remaining < sequence.litLength + sequence.matchLength) {
555         sequence.matchLength = remaining - sequence.litLength;
556         if (sequence.matchLength < minMatch) {
557             sequence.offset = 0;
558         }
559     }
560     /* Skip past `remaining` bytes for the future sequences. */
561     ZSTD_ldm_skipSequences(rawSeqStore, remaining, minMatch);
562     return sequence;
563 }
564 
ZSTD_ldm_blockCompress(rawSeqStore_t * rawSeqStore,ZSTD_matchState_t * ms,seqStore_t * seqStore,U32 rep[ZSTD_REP_NUM],void const * src,size_t srcSize)565 size_t ZSTD_ldm_blockCompress(rawSeqStore_t* rawSeqStore,
566     ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
567     void const* src, size_t srcSize)
568 {
569     const ZSTD_compressionParameters* const cParams = &ms->cParams;
570     unsigned const minMatch = cParams->minMatch;
571     ZSTD_blockCompressor const blockCompressor =
572         ZSTD_selectBlockCompressor(cParams->strategy, ZSTD_matchState_dictMode(ms));
573     /* Input bounds */
574     BYTE const* const istart = (BYTE const*)src;
575     BYTE const* const iend = istart + srcSize;
576     /* Input positions */
577     BYTE const* ip = istart;
578 
579     DEBUGLOG(5, "ZSTD_ldm_blockCompress: srcSize=%zu", srcSize);
580     assert(rawSeqStore->pos <= rawSeqStore->size);
581     assert(rawSeqStore->size <= rawSeqStore->capacity);
582     /* Loop through each sequence and apply the block compressor to the lits */
583     while (rawSeqStore->pos < rawSeqStore->size && ip < iend) {
584         /* maybeSplitSequence updates rawSeqStore->pos */
585         rawSeq const sequence = maybeSplitSequence(rawSeqStore,
586                                                    (U32)(iend - ip), minMatch);
587         int i;
588         /* End signal */
589         if (sequence.offset == 0)
590             break;
591 
592         assert(ip + sequence.litLength + sequence.matchLength <= iend);
593 
594         /* Fill tables for block compressor */
595         ZSTD_ldm_limitTableUpdate(ms, ip);
596         ZSTD_ldm_fillFastTables(ms, ip);
597         /* Run the block compressor */
598         DEBUGLOG(5, "pos %u : calling block compressor on segment of size %u", (unsigned)(ip-istart), sequence.litLength);
599         {
600             size_t const newLitLength =
601                 blockCompressor(ms, seqStore, rep, ip, sequence.litLength);
602             ip += sequence.litLength;
603             /* Update the repcodes */
604             for (i = ZSTD_REP_NUM - 1; i > 0; i--)
605                 rep[i] = rep[i-1];
606             rep[0] = sequence.offset;
607             /* Store the sequence */
608             ZSTD_storeSeq(seqStore, newLitLength, ip - newLitLength, iend,
609                           sequence.offset + ZSTD_REP_MOVE,
610                           sequence.matchLength - MINMATCH);
611             ip += sequence.matchLength;
612         }
613     }
614     /* Fill the tables for the block compressor */
615     ZSTD_ldm_limitTableUpdate(ms, ip);
616     ZSTD_ldm_fillFastTables(ms, ip);
617     /* Compress the last literals */
618     return blockCompressor(ms, seqStore, rep, ip, iend - ip);
619 }
620