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