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