39 if (hashTable[hash] == 0) { /* not yet filled */ |
40 if (hashTable[hash] == 0) { /* not yet filled */ |
40 hashTable[hash] = current + p; |
41 hashTable[hash] = current + p; |
41 } } } } |
42 } } } } |
42 } |
43 } |
43 |
44 |
|
45 |
44 FORCE_INLINE_TEMPLATE |
46 FORCE_INLINE_TEMPLATE |
45 size_t ZSTD_compressBlock_fast_generic( |
47 size_t ZSTD_compressBlock_fast_generic( |
46 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
48 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
47 void const* src, size_t srcSize, |
49 void const* src, size_t srcSize, |
48 U32 const mls, ZSTD_dictMode_e const dictMode) |
50 U32 const mls) |
|
51 { |
|
52 const ZSTD_compressionParameters* const cParams = &ms->cParams; |
|
53 U32* const hashTable = ms->hashTable; |
|
54 U32 const hlog = cParams->hashLog; |
|
55 /* support stepSize of 0 */ |
|
56 size_t const stepSize = cParams->targetLength + !(cParams->targetLength) + 1; |
|
57 const BYTE* const base = ms->window.base; |
|
58 const BYTE* const istart = (const BYTE*)src; |
|
59 /* We check ip0 (ip + 0) and ip1 (ip + 1) each loop */ |
|
60 const BYTE* ip0 = istart; |
|
61 const BYTE* ip1; |
|
62 const BYTE* anchor = istart; |
|
63 const U32 endIndex = (U32)((size_t)(istart - base) + srcSize); |
|
64 const U32 maxDistance = 1U << cParams->windowLog; |
|
65 const U32 validStartIndex = ms->window.dictLimit; |
|
66 const U32 prefixStartIndex = (endIndex - validStartIndex > maxDistance) ? endIndex - maxDistance : validStartIndex; |
|
67 const BYTE* const prefixStart = base + prefixStartIndex; |
|
68 const BYTE* const iend = istart + srcSize; |
|
69 const BYTE* const ilimit = iend - HASH_READ_SIZE; |
|
70 U32 offset_1=rep[0], offset_2=rep[1]; |
|
71 U32 offsetSaved = 0; |
|
72 |
|
73 /* init */ |
|
74 DEBUGLOG(5, "ZSTD_compressBlock_fast_generic"); |
|
75 ip0 += (ip0 == prefixStart); |
|
76 ip1 = ip0 + 1; |
|
77 { |
|
78 U32 const maxRep = (U32)(ip0 - prefixStart); |
|
79 if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0; |
|
80 if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0; |
|
81 } |
|
82 |
|
83 /* Main Search Loop */ |
|
84 while (ip1 < ilimit) { /* < instead of <=, because check at ip0+2 */ |
|
85 size_t mLength; |
|
86 BYTE const* ip2 = ip0 + 2; |
|
87 size_t const h0 = ZSTD_hashPtr(ip0, hlog, mls); |
|
88 U32 const val0 = MEM_read32(ip0); |
|
89 size_t const h1 = ZSTD_hashPtr(ip1, hlog, mls); |
|
90 U32 const val1 = MEM_read32(ip1); |
|
91 U32 const current0 = (U32)(ip0-base); |
|
92 U32 const current1 = (U32)(ip1-base); |
|
93 U32 const matchIndex0 = hashTable[h0]; |
|
94 U32 const matchIndex1 = hashTable[h1]; |
|
95 BYTE const* repMatch = ip2-offset_1; |
|
96 const BYTE* match0 = base + matchIndex0; |
|
97 const BYTE* match1 = base + matchIndex1; |
|
98 U32 offcode; |
|
99 hashTable[h0] = current0; /* update hash table */ |
|
100 hashTable[h1] = current1; /* update hash table */ |
|
101 |
|
102 assert(ip0 + 1 == ip1); |
|
103 |
|
104 if ((offset_1 > 0) & (MEM_read32(repMatch) == MEM_read32(ip2))) { |
|
105 mLength = ip2[-1] == repMatch[-1] ? 1 : 0; |
|
106 ip0 = ip2 - mLength; |
|
107 match0 = repMatch - mLength; |
|
108 offcode = 0; |
|
109 goto _match; |
|
110 } |
|
111 if ((matchIndex0 > prefixStartIndex) && MEM_read32(match0) == val0) { |
|
112 /* found a regular match */ |
|
113 goto _offset; |
|
114 } |
|
115 if ((matchIndex1 > prefixStartIndex) && MEM_read32(match1) == val1) { |
|
116 /* found a regular match after one literal */ |
|
117 ip0 = ip1; |
|
118 match0 = match1; |
|
119 goto _offset; |
|
120 } |
|
121 { |
|
122 size_t const step = ((ip0-anchor) >> (kSearchStrength - 1)) + stepSize; |
|
123 assert(step >= 2); |
|
124 ip0 += step; |
|
125 ip1 += step; |
|
126 continue; |
|
127 } |
|
128 _offset: /* Requires: ip0, match0 */ |
|
129 /* Compute the offset code */ |
|
130 offset_2 = offset_1; |
|
131 offset_1 = (U32)(ip0-match0); |
|
132 offcode = offset_1 + ZSTD_REP_MOVE; |
|
133 mLength = 0; |
|
134 /* Count the backwards match length */ |
|
135 while (((ip0>anchor) & (match0>prefixStart)) |
|
136 && (ip0[-1] == match0[-1])) { ip0--; match0--; mLength++; } /* catch up */ |
|
137 |
|
138 _match: /* Requires: ip0, match0, offcode */ |
|
139 /* Count the forward length */ |
|
140 mLength += ZSTD_count(ip0+mLength+4, match0+mLength+4, iend) + 4; |
|
141 ZSTD_storeSeq(seqStore, ip0-anchor, anchor, offcode, mLength-MINMATCH); |
|
142 /* match found */ |
|
143 ip0 += mLength; |
|
144 anchor = ip0; |
|
145 ip1 = ip0 + 1; |
|
146 |
|
147 if (ip0 <= ilimit) { |
|
148 /* Fill Table */ |
|
149 assert(base+current0+2 > istart); /* check base overflow */ |
|
150 hashTable[ZSTD_hashPtr(base+current0+2, hlog, mls)] = current0+2; /* here because current+2 could be > iend-8 */ |
|
151 hashTable[ZSTD_hashPtr(ip0-2, hlog, mls)] = (U32)(ip0-2-base); |
|
152 |
|
153 while ( (ip0 <= ilimit) |
|
154 && ( (offset_2>0) |
|
155 & (MEM_read32(ip0) == MEM_read32(ip0 - offset_2)) )) { |
|
156 /* store sequence */ |
|
157 size_t const rLength = ZSTD_count(ip0+4, ip0+4-offset_2, iend) + 4; |
|
158 U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; /* swap offset_2 <=> offset_1 */ |
|
159 hashTable[ZSTD_hashPtr(ip0, hlog, mls)] = (U32)(ip0-base); |
|
160 ip0 += rLength; |
|
161 ip1 = ip0 + 1; |
|
162 ZSTD_storeSeq(seqStore, 0, anchor, 0, rLength-MINMATCH); |
|
163 anchor = ip0; |
|
164 continue; /* faster when present (confirmed on gcc-8) ... (?) */ |
|
165 } |
|
166 } |
|
167 } |
|
168 |
|
169 /* save reps for next block */ |
|
170 rep[0] = offset_1 ? offset_1 : offsetSaved; |
|
171 rep[1] = offset_2 ? offset_2 : offsetSaved; |
|
172 |
|
173 /* Return the last literals size */ |
|
174 return (size_t)(iend - anchor); |
|
175 } |
|
176 |
|
177 |
|
178 size_t ZSTD_compressBlock_fast( |
|
179 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
|
180 void const* src, size_t srcSize) |
|
181 { |
|
182 ZSTD_compressionParameters const* cParams = &ms->cParams; |
|
183 U32 const mls = cParams->minMatch; |
|
184 assert(ms->dictMatchState == NULL); |
|
185 switch(mls) |
|
186 { |
|
187 default: /* includes case 3 */ |
|
188 case 4 : |
|
189 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 4); |
|
190 case 5 : |
|
191 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 5); |
|
192 case 6 : |
|
193 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 6); |
|
194 case 7 : |
|
195 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 7); |
|
196 } |
|
197 } |
|
198 |
|
199 FORCE_INLINE_TEMPLATE |
|
200 size_t ZSTD_compressBlock_fast_dictMatchState_generic( |
|
201 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
|
202 void const* src, size_t srcSize, U32 const mls) |
49 { |
203 { |
50 const ZSTD_compressionParameters* const cParams = &ms->cParams; |
204 const ZSTD_compressionParameters* const cParams = &ms->cParams; |
51 U32* const hashTable = ms->hashTable; |
205 U32* const hashTable = ms->hashTable; |
52 U32 const hlog = cParams->hashLog; |
206 U32 const hlog = cParams->hashLog; |
53 /* support stepSize of 0 */ |
207 /* support stepSize of 0 */ |
62 const BYTE* const ilimit = iend - HASH_READ_SIZE; |
216 const BYTE* const ilimit = iend - HASH_READ_SIZE; |
63 U32 offset_1=rep[0], offset_2=rep[1]; |
217 U32 offset_1=rep[0], offset_2=rep[1]; |
64 U32 offsetSaved = 0; |
218 U32 offsetSaved = 0; |
65 |
219 |
66 const ZSTD_matchState_t* const dms = ms->dictMatchState; |
220 const ZSTD_matchState_t* const dms = ms->dictMatchState; |
67 const ZSTD_compressionParameters* const dictCParams = |
221 const ZSTD_compressionParameters* const dictCParams = &dms->cParams ; |
68 dictMode == ZSTD_dictMatchState ? |
222 const U32* const dictHashTable = dms->hashTable; |
69 &dms->cParams : NULL; |
223 const U32 dictStartIndex = dms->window.dictLimit; |
70 const U32* const dictHashTable = dictMode == ZSTD_dictMatchState ? |
224 const BYTE* const dictBase = dms->window.base; |
71 dms->hashTable : NULL; |
225 const BYTE* const dictStart = dictBase + dictStartIndex; |
72 const U32 dictStartIndex = dictMode == ZSTD_dictMatchState ? |
226 const BYTE* const dictEnd = dms->window.nextSrc; |
73 dms->window.dictLimit : 0; |
227 const U32 dictIndexDelta = prefixStartIndex - (U32)(dictEnd - dictBase); |
74 const BYTE* const dictBase = dictMode == ZSTD_dictMatchState ? |
|
75 dms->window.base : NULL; |
|
76 const BYTE* const dictStart = dictMode == ZSTD_dictMatchState ? |
|
77 dictBase + dictStartIndex : NULL; |
|
78 const BYTE* const dictEnd = dictMode == ZSTD_dictMatchState ? |
|
79 dms->window.nextSrc : NULL; |
|
80 const U32 dictIndexDelta = dictMode == ZSTD_dictMatchState ? |
|
81 prefixStartIndex - (U32)(dictEnd - dictBase) : |
|
82 0; |
|
83 const U32 dictAndPrefixLength = (U32)(ip - prefixStart + dictEnd - dictStart); |
228 const U32 dictAndPrefixLength = (U32)(ip - prefixStart + dictEnd - dictStart); |
84 const U32 dictHLog = dictMode == ZSTD_dictMatchState ? |
229 const U32 dictHLog = dictCParams->hashLog; |
85 dictCParams->hashLog : hlog; |
230 |
86 |
231 /* if a dictionary is still attached, it necessarily means that |
87 assert(dictMode == ZSTD_noDict || dictMode == ZSTD_dictMatchState); |
232 * it is within window size. So we just check it. */ |
88 |
233 const U32 maxDistance = 1U << cParams->windowLog; |
89 /* otherwise, we would get index underflow when translating a dict index |
234 const U32 endIndex = (U32)((size_t)(ip - base) + srcSize); |
90 * into a local index */ |
235 assert(endIndex - prefixStartIndex <= maxDistance); |
91 assert(dictMode != ZSTD_dictMatchState |
236 (void)maxDistance; (void)endIndex; /* these variables are not used when assert() is disabled */ |
92 || prefixStartIndex >= (U32)(dictEnd - dictBase)); |
237 |
|
238 /* ensure there will be no no underflow |
|
239 * when translating a dict index into a local index */ |
|
240 assert(prefixStartIndex >= (U32)(dictEnd - dictBase)); |
93 |
241 |
94 /* init */ |
242 /* init */ |
|
243 DEBUGLOG(5, "ZSTD_compressBlock_fast_dictMatchState_generic"); |
95 ip += (dictAndPrefixLength == 0); |
244 ip += (dictAndPrefixLength == 0); |
96 if (dictMode == ZSTD_noDict) { |
245 /* dictMatchState repCode checks don't currently handle repCode == 0 |
97 U32 const maxRep = (U32)(ip - prefixStart); |
246 * disabling. */ |
98 if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0; |
247 assert(offset_1 <= dictAndPrefixLength); |
99 if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0; |
248 assert(offset_2 <= dictAndPrefixLength); |
100 } |
|
101 if (dictMode == ZSTD_dictMatchState) { |
|
102 /* dictMatchState repCode checks don't currently handle repCode == 0 |
|
103 * disabling. */ |
|
104 assert(offset_1 <= dictAndPrefixLength); |
|
105 assert(offset_2 <= dictAndPrefixLength); |
|
106 } |
|
107 |
249 |
108 /* Main Search Loop */ |
250 /* Main Search Loop */ |
109 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */ |
251 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */ |
110 size_t mLength; |
252 size_t mLength; |
111 size_t const h = ZSTD_hashPtr(ip, hlog, mls); |
253 size_t const h = ZSTD_hashPtr(ip, hlog, mls); |
112 U32 const current = (U32)(ip-base); |
254 U32 const current = (U32)(ip-base); |
113 U32 const matchIndex = hashTable[h]; |
255 U32 const matchIndex = hashTable[h]; |
114 const BYTE* match = base + matchIndex; |
256 const BYTE* match = base + matchIndex; |
115 const U32 repIndex = current + 1 - offset_1; |
257 const U32 repIndex = current + 1 - offset_1; |
116 const BYTE* repMatch = (dictMode == ZSTD_dictMatchState |
258 const BYTE* repMatch = (repIndex < prefixStartIndex) ? |
117 && repIndex < prefixStartIndex) ? |
|
118 dictBase + (repIndex - dictIndexDelta) : |
259 dictBase + (repIndex - dictIndexDelta) : |
119 base + repIndex; |
260 base + repIndex; |
120 hashTable[h] = current; /* update hash table */ |
261 hashTable[h] = current; /* update hash table */ |
121 |
262 |
122 if ( (dictMode == ZSTD_dictMatchState) |
263 if ( ((U32)((prefixStartIndex-1) - repIndex) >= 3) /* intentional underflow : ensure repIndex isn't overlapping dict + prefix */ |
123 && ((U32)((prefixStartIndex-1) - repIndex) >= 3) /* intentional underflow : ensure repIndex isn't overlapping dict + prefix */ |
|
124 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) { |
264 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) { |
125 const BYTE* const repMatchEnd = repIndex < prefixStartIndex ? dictEnd : iend; |
265 const BYTE* const repMatchEnd = repIndex < prefixStartIndex ? dictEnd : iend; |
126 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixStart) + 4; |
266 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixStart) + 4; |
127 ip++; |
267 ip++; |
128 ZSTD_storeSeq(seqStore, ip-anchor, anchor, 0, mLength-MINMATCH); |
268 ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, 0, mLength-MINMATCH); |
129 } else if ( dictMode == ZSTD_noDict |
|
130 && ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1)))) { |
|
131 mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4; |
|
132 ip++; |
|
133 ZSTD_storeSeq(seqStore, ip-anchor, anchor, 0, mLength-MINMATCH); |
|
134 } else if ( (matchIndex <= prefixStartIndex) ) { |
269 } else if ( (matchIndex <= prefixStartIndex) ) { |
135 if (dictMode == ZSTD_dictMatchState) { |
270 size_t const dictHash = ZSTD_hashPtr(ip, dictHLog, mls); |
136 size_t const dictHash = ZSTD_hashPtr(ip, dictHLog, mls); |
271 U32 const dictMatchIndex = dictHashTable[dictHash]; |
137 U32 const dictMatchIndex = dictHashTable[dictHash]; |
272 const BYTE* dictMatch = dictBase + dictMatchIndex; |
138 const BYTE* dictMatch = dictBase + dictMatchIndex; |
273 if (dictMatchIndex <= dictStartIndex || |
139 if (dictMatchIndex <= dictStartIndex || |
274 MEM_read32(dictMatch) != MEM_read32(ip)) { |
140 MEM_read32(dictMatch) != MEM_read32(ip)) { |
|
141 assert(stepSize >= 1); |
|
142 ip += ((ip-anchor) >> kSearchStrength) + stepSize; |
|
143 continue; |
|
144 } else { |
|
145 /* found a dict match */ |
|
146 U32 const offset = (U32)(current-dictMatchIndex-dictIndexDelta); |
|
147 mLength = ZSTD_count_2segments(ip+4, dictMatch+4, iend, dictEnd, prefixStart) + 4; |
|
148 while (((ip>anchor) & (dictMatch>dictStart)) |
|
149 && (ip[-1] == dictMatch[-1])) { |
|
150 ip--; dictMatch--; mLength++; |
|
151 } /* catch up */ |
|
152 offset_2 = offset_1; |
|
153 offset_1 = offset; |
|
154 ZSTD_storeSeq(seqStore, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH); |
|
155 } |
|
156 } else { |
|
157 assert(stepSize >= 1); |
275 assert(stepSize >= 1); |
158 ip += ((ip-anchor) >> kSearchStrength) + stepSize; |
276 ip += ((ip-anchor) >> kSearchStrength) + stepSize; |
159 continue; |
277 continue; |
|
278 } else { |
|
279 /* found a dict match */ |
|
280 U32 const offset = (U32)(current-dictMatchIndex-dictIndexDelta); |
|
281 mLength = ZSTD_count_2segments(ip+4, dictMatch+4, iend, dictEnd, prefixStart) + 4; |
|
282 while (((ip>anchor) & (dictMatch>dictStart)) |
|
283 && (ip[-1] == dictMatch[-1])) { |
|
284 ip--; dictMatch--; mLength++; |
|
285 } /* catch up */ |
|
286 offset_2 = offset_1; |
|
287 offset_1 = offset; |
|
288 ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH); |
160 } |
289 } |
161 } else if (MEM_read32(match) != MEM_read32(ip)) { |
290 } else if (MEM_read32(match) != MEM_read32(ip)) { |
162 /* it's not a match, and we're not going to check the dictionary */ |
291 /* it's not a match, and we're not going to check the dictionary */ |
163 assert(stepSize >= 1); |
292 assert(stepSize >= 1); |
164 ip += ((ip-anchor) >> kSearchStrength) + stepSize; |
293 ip += ((ip-anchor) >> kSearchStrength) + stepSize; |
183 assert(base+current+2 > istart); /* check base overflow */ |
312 assert(base+current+2 > istart); /* check base overflow */ |
184 hashTable[ZSTD_hashPtr(base+current+2, hlog, mls)] = current+2; /* here because current+2 could be > iend-8 */ |
313 hashTable[ZSTD_hashPtr(base+current+2, hlog, mls)] = current+2; /* here because current+2 could be > iend-8 */ |
185 hashTable[ZSTD_hashPtr(ip-2, hlog, mls)] = (U32)(ip-2-base); |
314 hashTable[ZSTD_hashPtr(ip-2, hlog, mls)] = (U32)(ip-2-base); |
186 |
315 |
187 /* check immediate repcode */ |
316 /* check immediate repcode */ |
188 if (dictMode == ZSTD_dictMatchState) { |
317 while (ip <= ilimit) { |
189 while (ip <= ilimit) { |
318 U32 const current2 = (U32)(ip-base); |
190 U32 const current2 = (U32)(ip-base); |
319 U32 const repIndex2 = current2 - offset_2; |
191 U32 const repIndex2 = current2 - offset_2; |
320 const BYTE* repMatch2 = repIndex2 < prefixStartIndex ? |
192 const BYTE* repMatch2 = repIndex2 < prefixStartIndex ? |
321 dictBase - dictIndexDelta + repIndex2 : |
193 dictBase - dictIndexDelta + repIndex2 : |
322 base + repIndex2; |
194 base + repIndex2; |
323 if ( ((U32)((prefixStartIndex-1) - (U32)repIndex2) >= 3 /* intentional overflow */) |
195 if ( ((U32)((prefixStartIndex-1) - (U32)repIndex2) >= 3 /* intentional overflow */) |
324 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) { |
196 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) { |
325 const BYTE* const repEnd2 = repIndex2 < prefixStartIndex ? dictEnd : iend; |
197 const BYTE* const repEnd2 = repIndex2 < prefixStartIndex ? dictEnd : iend; |
326 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixStart) + 4; |
198 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixStart) + 4; |
327 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */ |
199 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */ |
328 ZSTD_storeSeq(seqStore, 0, anchor, 0, repLength2-MINMATCH); |
200 ZSTD_storeSeq(seqStore, 0, anchor, 0, repLength2-MINMATCH); |
329 hashTable[ZSTD_hashPtr(ip, hlog, mls)] = current2; |
201 hashTable[ZSTD_hashPtr(ip, hlog, mls)] = current2; |
330 ip += repLength2; |
202 ip += repLength2; |
331 anchor = ip; |
203 anchor = ip; |
332 continue; |
204 continue; |
|
205 } |
|
206 break; |
|
207 } |
333 } |
|
334 break; |
208 } |
335 } |
209 |
336 } |
210 if (dictMode == ZSTD_noDict) { |
337 } |
211 while ( (ip <= ilimit) |
|
212 && ( (offset_2>0) |
|
213 & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) { |
|
214 /* store sequence */ |
|
215 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4; |
|
216 U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; /* swap offset_2 <=> offset_1 */ |
|
217 hashTable[ZSTD_hashPtr(ip, hlog, mls)] = (U32)(ip-base); |
|
218 ZSTD_storeSeq(seqStore, 0, anchor, 0, rLength-MINMATCH); |
|
219 ip += rLength; |
|
220 anchor = ip; |
|
221 continue; /* faster when present ... (?) */ |
|
222 } } } } |
|
223 |
338 |
224 /* save reps for next block */ |
339 /* save reps for next block */ |
225 rep[0] = offset_1 ? offset_1 : offsetSaved; |
340 rep[0] = offset_1 ? offset_1 : offsetSaved; |
226 rep[1] = offset_2 ? offset_2 : offsetSaved; |
341 rep[1] = offset_2 ? offset_2 : offsetSaved; |
227 |
342 |
228 /* Return the last literals size */ |
343 /* Return the last literals size */ |
229 return iend - anchor; |
344 return (size_t)(iend - anchor); |
230 } |
|
231 |
|
232 |
|
233 size_t ZSTD_compressBlock_fast( |
|
234 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
|
235 void const* src, size_t srcSize) |
|
236 { |
|
237 ZSTD_compressionParameters const* cParams = &ms->cParams; |
|
238 U32 const mls = cParams->minMatch; |
|
239 assert(ms->dictMatchState == NULL); |
|
240 switch(mls) |
|
241 { |
|
242 default: /* includes case 3 */ |
|
243 case 4 : |
|
244 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 4, ZSTD_noDict); |
|
245 case 5 : |
|
246 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 5, ZSTD_noDict); |
|
247 case 6 : |
|
248 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 6, ZSTD_noDict); |
|
249 case 7 : |
|
250 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 7, ZSTD_noDict); |
|
251 } |
|
252 } |
345 } |
253 |
346 |
254 size_t ZSTD_compressBlock_fast_dictMatchState( |
347 size_t ZSTD_compressBlock_fast_dictMatchState( |
255 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
348 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
256 void const* src, size_t srcSize) |
349 void const* src, size_t srcSize) |
285 const BYTE* const base = ms->window.base; |
378 const BYTE* const base = ms->window.base; |
286 const BYTE* const dictBase = ms->window.dictBase; |
379 const BYTE* const dictBase = ms->window.dictBase; |
287 const BYTE* const istart = (const BYTE*)src; |
380 const BYTE* const istart = (const BYTE*)src; |
288 const BYTE* ip = istart; |
381 const BYTE* ip = istart; |
289 const BYTE* anchor = istart; |
382 const BYTE* anchor = istart; |
290 const U32 dictStartIndex = ms->window.lowLimit; |
383 const U32 endIndex = (U32)((size_t)(istart - base) + srcSize); |
|
384 const U32 lowLimit = ZSTD_getLowestMatchIndex(ms, endIndex, cParams->windowLog); |
|
385 const U32 dictStartIndex = lowLimit; |
291 const BYTE* const dictStart = dictBase + dictStartIndex; |
386 const BYTE* const dictStart = dictBase + dictStartIndex; |
292 const U32 prefixStartIndex = ms->window.dictLimit; |
387 const U32 dictLimit = ms->window.dictLimit; |
|
388 const U32 prefixStartIndex = dictLimit < lowLimit ? lowLimit : dictLimit; |
293 const BYTE* const prefixStart = base + prefixStartIndex; |
389 const BYTE* const prefixStart = base + prefixStartIndex; |
294 const BYTE* const dictEnd = dictBase + prefixStartIndex; |
390 const BYTE* const dictEnd = dictBase + prefixStartIndex; |
295 const BYTE* const iend = istart + srcSize; |
391 const BYTE* const iend = istart + srcSize; |
296 const BYTE* const ilimit = iend - 8; |
392 const BYTE* const ilimit = iend - 8; |
297 U32 offset_1=rep[0], offset_2=rep[1]; |
393 U32 offset_1=rep[0], offset_2=rep[1]; |
|
394 |
|
395 DEBUGLOG(5, "ZSTD_compressBlock_fast_extDict_generic"); |
|
396 |
|
397 /* switch to "regular" variant if extDict is invalidated due to maxDistance */ |
|
398 if (prefixStartIndex == dictStartIndex) |
|
399 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, mls); |
298 |
400 |
299 /* Search Loop */ |
401 /* Search Loop */ |
300 while (ip < ilimit) { /* < instead of <=, because (ip+1) */ |
402 while (ip < ilimit) { /* < instead of <=, because (ip+1) */ |
301 const size_t h = ZSTD_hashPtr(ip, hlog, mls); |
403 const size_t h = ZSTD_hashPtr(ip, hlog, mls); |
302 const U32 matchIndex = hashTable[h]; |
404 const U32 matchIndex = hashTable[h]; |
310 hashTable[h] = current; /* update hash table */ |
412 hashTable[h] = current; /* update hash table */ |
311 assert(offset_1 <= current +1); /* check repIndex */ |
413 assert(offset_1 <= current +1); /* check repIndex */ |
312 |
414 |
313 if ( (((U32)((prefixStartIndex-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > dictStartIndex)) |
415 if ( (((U32)((prefixStartIndex-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > dictStartIndex)) |
314 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) { |
416 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) { |
315 const BYTE* repMatchEnd = repIndex < prefixStartIndex ? dictEnd : iend; |
417 const BYTE* const repMatchEnd = repIndex < prefixStartIndex ? dictEnd : iend; |
316 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixStart) + 4; |
418 mLength = ZSTD_count_2segments(ip+1 +4, repMatch +4, iend, repMatchEnd, prefixStart) + 4; |
317 ip++; |
419 ip++; |
318 ZSTD_storeSeq(seqStore, ip-anchor, anchor, 0, mLength-MINMATCH); |
420 ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, 0, mLength-MINMATCH); |
319 } else { |
421 } else { |
320 if ( (matchIndex < dictStartIndex) || |
422 if ( (matchIndex < dictStartIndex) || |
321 (MEM_read32(match) != MEM_read32(ip)) ) { |
423 (MEM_read32(match) != MEM_read32(ip)) ) { |
322 assert(stepSize >= 1); |
424 assert(stepSize >= 1); |
323 ip += ((ip-anchor) >> kSearchStrength) + stepSize; |
425 ip += ((ip-anchor) >> kSearchStrength) + stepSize; |
324 continue; |
426 continue; |
325 } |
427 } |
326 { const BYTE* matchEnd = matchIndex < prefixStartIndex ? dictEnd : iend; |
428 { const BYTE* const matchEnd = matchIndex < prefixStartIndex ? dictEnd : iend; |
327 const BYTE* lowMatchPtr = matchIndex < prefixStartIndex ? dictStart : prefixStart; |
429 const BYTE* const lowMatchPtr = matchIndex < prefixStartIndex ? dictStart : prefixStart; |
328 U32 offset; |
430 U32 offset; |
329 mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, prefixStart) + 4; |
431 mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, prefixStart) + 4; |
330 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */ |
432 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */ |
331 offset = current - matchIndex; |
433 offset = current - matchIndex; |
332 offset_2 = offset_1; |
434 offset_2 = offset_1; |
333 offset_1 = offset; |
435 offset_1 = offset; |
334 ZSTD_storeSeq(seqStore, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH); |
436 ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH); |
335 } } |
437 } } |
336 |
438 |
337 /* found a match : store it */ |
439 /* found a match : store it */ |
338 ip += mLength; |
440 ip += mLength; |
339 anchor = ip; |
441 anchor = ip; |