projects/linux·blob master · refs

746 lines · 28.7 KiB

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}