]>
Commit | Line | Data |
---|---|---|
11fdf7f2 | 1 | /* |
f67539c2 | 2 | * Copyright (c) 2016-2020, Yann Collet, Facebook, Inc. |
11fdf7f2 TL |
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). | |
f67539c2 | 8 | * You may select, at your option, one of the above-listed licenses. |
11fdf7f2 TL |
9 | */ |
10 | ||
11 | #include "zstd_ldm.h" | |
12 | ||
f67539c2 | 13 | #include "../common/debug.h" |
11fdf7f2 TL |
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 | ||
9f95a23c TL |
22 | void ZSTD_ldm_adjustParameters(ldmParams_t* params, |
23 | ZSTD_compressionParameters const* cParams) | |
11fdf7f2 | 24 | { |
9f95a23c | 25 | params->windowLog = cParams->windowLog; |
11fdf7f2 | 26 | ZSTD_STATIC_ASSERT(LDM_BUCKET_SIZE_LOG <= ZSTD_LDM_BUCKETSIZELOG_MAX); |
9f95a23c TL |
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 | } | |
11fdf7f2 | 37 | if (params->hashLog == 0) { |
9f95a23c | 38 | params->hashLog = MAX(ZSTD_HASHLOG_MIN, params->windowLog - LDM_HASH_RLOG); |
11fdf7f2 TL |
39 | assert(params->hashLog <= ZSTD_HASHLOG_MAX); |
40 | } | |
9f95a23c TL |
41 | if (params->hashRateLog == 0) { |
42 | params->hashRateLog = params->windowLog < params->hashLog | |
43 | ? 0 | |
44 | : params->windowLog - params->hashLog; | |
11fdf7f2 TL |
45 | } |
46 | params->bucketSizeLog = MIN(params->bucketSizeLog, params->hashLog); | |
47 | } | |
48 | ||
9f95a23c TL |
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); | |
f67539c2 TL |
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)); | |
9f95a23c TL |
56 | return params.enableLdm ? totalSize : 0; |
57 | } | |
58 | ||
59 | size_t ZSTD_ldm_getMaxNbSeq(ldmParams_t params, size_t maxChunkSize) | |
60 | { | |
61 | return params.enableLdm ? (maxChunkSize / params.minMatchLength) : 0; | |
11fdf7f2 TL |
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. */ | |
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 */ | |
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. */ | |
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. */ | |
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 */ | |
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 | * | |
9f95a23c | 123 | * If the tag matches (1 << ldmParams.hashRateLog)-1, then |
11fdf7f2 TL |
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 | |
9f95a23c | 128 | * by ldmParams.hashRateLog bits that make up the tag. */ |
11fdf7f2 TL |
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 | { | |
9f95a23c TL |
135 | U32 const tag = ZSTD_ldm_getTag(rollingHash, hBits, ldmParams.hashRateLog); |
136 | U32 const tagMask = ((U32)1 << ldmParams.hashRateLog) - 1; | |
11fdf7f2 TL |
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 | ||
11fdf7f2 TL |
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. */ | |
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. */ | |
9f95a23c TL |
171 | static size_t ZSTD_ldm_fillFastTables(ZSTD_matchState_t* ms, |
172 | void const* end) | |
11fdf7f2 TL |
173 | { |
174 | const BYTE* const iend = (const BYTE*)end; | |
11fdf7f2 | 175 | |
9f95a23c | 176 | switch(ms->cParams.strategy) |
11fdf7f2 TL |
177 | { |
178 | case ZSTD_fast: | |
9f95a23c | 179 | ZSTD_fillHashTable(ms, iend, ZSTD_dtlm_fast); |
11fdf7f2 TL |
180 | break; |
181 | ||
182 | case ZSTD_dfast: | |
9f95a23c | 183 | ZSTD_fillDoubleHashTable(ms, iend, ZSTD_dtlm_fast); |
11fdf7f2 TL |
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: | |
9f95a23c | 192 | case ZSTD_btultra2: |
11fdf7f2 TL |
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. */ | |
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) { | |
9f95a23c TL |
216 | rollingHash = ZSTD_rollingHash_rotate(rollingHash, cur[-1], |
217 | cur[ldmParams.minMatchLength-1], | |
218 | state->hashPower); | |
11fdf7f2 TL |
219 | ZSTD_ldm_makeEntryAndInsertByTag(state, |
220 | rollingHash, hBits, | |
221 | (U32)(cur - base), ldmParams); | |
222 | ++cur; | |
223 | } | |
224 | return rollingHash; | |
225 | } | |
226 | ||
f67539c2 TL |
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 | ||
11fdf7f2 TL |
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). */ | |
9f95a23c | 247 | static void ZSTD_ldm_limitTableUpdate(ZSTD_matchState_t* ms, const BYTE* anchor) |
11fdf7f2 | 248 | { |
9f95a23c TL |
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); | |
11fdf7f2 TL |
253 | } |
254 | } | |
255 | ||
9f95a23c TL |
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) | |
11fdf7f2 | 259 | { |
9f95a23c TL |
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; | |
11fdf7f2 | 285 | U64 rollingHash = 0; |
11fdf7f2 | 286 | |
9f95a23c | 287 | while (ip <= ilimit) { |
11fdf7f2 TL |
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) { | |
9f95a23c TL |
293 | rollingHash = ZSTD_rollingHash_rotate(rollingHash, lastHashed[0], |
294 | lastHashed[minMatchLength], | |
295 | hashPower); | |
11fdf7f2 | 296 | } else { |
9f95a23c | 297 | rollingHash = ZSTD_rollingHash_compute(ip, minMatchLength); |
11fdf7f2 TL |
298 | } |
299 | lastHashed = ip; | |
300 | ||
301 | /* Do not insert and do not look for a match */ | |
9f95a23c | 302 | if (ZSTD_ldm_getTag(rollingHash, hBits, hashRateLog) != ldmTagMask) { |
11fdf7f2 TL |
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), | |
9f95a23c | 312 | *params); |
11fdf7f2 TL |
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) { | |
11fdf7f2 TL |
318 | size_t curForwardMatchLength, curBackwardMatchLength, |
319 | curTotalMatchLength; | |
320 | if (cur->checksum != checksum || cur->offset <= lowestIndex) { | |
321 | continue; | |
322 | } | |
9f95a23c TL |
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; | |
11fdf7f2 | 354 | } |
11fdf7f2 TL |
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, | |
9f95a23c | 369 | *params); |
11fdf7f2 TL |
370 | ip++; |
371 | continue; | |
372 | } | |
373 | ||
374 | /* Match found */ | |
375 | mLength = forwardMatchLength + backwardMatchLength; | |
376 | ip -= backwardMatchLength; | |
377 | ||
11fdf7f2 | 378 | { |
9f95a23c TL |
379 | /* Store the sequence: |
380 | * ip = current - backwardMatchLength | |
381 | * The match is at (bestEntry->offset - backwardMatchLength) | |
382 | */ | |
11fdf7f2 | 383 | U32 const matchIndex = bestEntry->offset; |
9f95a23c TL |
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++; | |
11fdf7f2 TL |
394 | } |
395 | ||
396 | /* Insert the current entry into the hash table */ | |
397 | ZSTD_ldm_makeEntryAndInsertByTag(ldmState, rollingHash, hBits, | |
398 | (U32)(lastHashed - base), | |
9f95a23c | 399 | *params); |
11fdf7f2 TL |
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 */ | |
9f95a23c | 405 | if (ip + mLength <= ilimit) { |
11fdf7f2 TL |
406 | rollingHash = ZSTD_ldm_fillLdmHashTable( |
407 | ldmState, rollingHash, lastHashed, | |
9f95a23c | 408 | ip + mLength, base, hBits, *params); |
11fdf7f2 TL |
409 | lastHashed = ip + mLength - 1; |
410 | } | |
411 | ip += mLength; | |
412 | anchor = ip; | |
11fdf7f2 | 413 | } |
9f95a23c | 414 | return iend - anchor; |
11fdf7f2 TL |
415 | } |
416 | ||
9f95a23c TL |
417 | /*! ZSTD_ldm_reduceTable() : |
418 | * reduce table indexes by `reducerValue` */ | |
419 | static void ZSTD_ldm_reduceTable(ldmEntry_t* const table, U32 const size, | |
420 | U32 const reducerValue) | |
11fdf7f2 | 421 | { |
9f95a23c TL |
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 | } | |
11fdf7f2 TL |
427 | } |
428 | ||
9f95a23c TL |
429 | size_t ZSTD_ldm_generateSequences( |
430 | ldmState_t* ldmState, rawSeqStore_t* sequences, | |
431 | ldmParams_t const* params, void const* src, size_t srcSize) | |
11fdf7f2 | 432 | { |
9f95a23c TL |
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( | |
f67539c2 | 465 | &ldmState->window, /* cycleLog */ 0, maxDist, chunkStart); |
9f95a23c | 466 | ZSTD_ldm_reduceTable(ldmState->hashTable, ldmHSize, correction); |
f67539c2 TL |
467 | /* invalidate dictionaries on overflow correction */ |
468 | ldmState->loadedDictEnd = 0; | |
9f95a23c TL |
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. | |
f67539c2 TL |
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. | |
9f95a23c | 483 | */ |
f67539c2 | 484 | ZSTD_window_enforceMaxDist(&ldmState->window, chunkEnd, maxDist, &ldmState->loadedDictEnd, NULL); |
9f95a23c TL |
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; | |
11fdf7f2 | 498 | } else { |
9f95a23c TL |
499 | assert(newLeftoverSize == chunkSize); |
500 | leftoverSize += chunkSize; | |
11fdf7f2 | 501 | } |
9f95a23c TL |
502 | } |
503 | return 0; | |
504 | } | |
11fdf7f2 | 505 | |
9f95a23c TL |
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; | |
11fdf7f2 | 513 | } |
9f95a23c TL |
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; | |
11fdf7f2 | 523 | } |
9f95a23c | 524 | rawSeqStore->pos++; |
11fdf7f2 | 525 | } |
9f95a23c | 526 | return; |
11fdf7f2 | 527 | } |
9f95a23c TL |
528 | srcSize -= seq->matchLength; |
529 | seq->matchLength = 0; | |
530 | rawSeqStore->pos++; | |
531 | } | |
532 | } | |
11fdf7f2 | 533 | |
9f95a23c TL |
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 | */ | |
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; | |
11fdf7f2 | 558 | } |
9f95a23c TL |
559 | } |
560 | /* Skip past `remaining` bytes for the future sequences. */ | |
561 | ZSTD_ldm_skipSequences(rawSeqStore, remaining, minMatch); | |
562 | return sequence; | |
563 | } | |
11fdf7f2 | 564 | |
9f95a23c TL |
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; | |
11fdf7f2 | 591 | |
9f95a23c | 592 | assert(ip + sequence.litLength + sequence.matchLength <= iend); |
11fdf7f2 | 593 | |
9f95a23c TL |
594 | /* Fill tables for block compressor */ |
595 | ZSTD_ldm_limitTableUpdate(ms, ip); | |
596 | ZSTD_ldm_fillFastTables(ms, ip); | |
597 | /* Run the block compressor */ | |
f67539c2 | 598 | DEBUGLOG(5, "pos %u : calling block compressor on segment of size %u", (unsigned)(ip-istart), sequence.litLength); |
9f95a23c TL |
599 | { |
600 | size_t const newLitLength = | |
601 | blockCompressor(ms, seqStore, rep, ip, sequence.litLength); | |
602 | ip += sequence.litLength; | |
603 | /* Update the repcodes */ | |
11fdf7f2 | 604 | for (i = ZSTD_REP_NUM - 1; i > 0; i--) |
9f95a23c TL |
605 | rep[i] = rep[i-1]; |
606 | rep[0] = sequence.offset; | |
607 | /* Store the sequence */ | |
f67539c2 | 608 | ZSTD_storeSeq(seqStore, newLitLength, ip - newLitLength, iend, |
9f95a23c TL |
609 | sequence.offset + ZSTD_REP_MOVE, |
610 | sequence.matchLength - MINMATCH); | |
611 | ip += sequence.matchLength; | |
11fdf7f2 TL |
612 | } |
613 | } | |
9f95a23c TL |
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); | |
11fdf7f2 | 619 | } |