Mercurial > hg
comparison contrib/python-zstandard/zstd/compress/zstd_fast.c @ 42937:69de49c4e39c
zstandard: vendor python-zstandard 0.12
The upstream source distribution from PyPI was extracted. Unwanted
files were removed.
The clang-format ignore list was updated to reflect the new source
of files.
test-repo-compengines.t was updated to reflect a change in behavior
of the zstd library.
The project contains a vendored copy of zstandard 1.4.3. The old
version was 1.3.8. This should result in some minor performance wins.
# no-check-commit because 3rd party code has different style guidelines
Differential Revision: https://phab.mercurial-scm.org/D6858
author | Gregory Szorc <gregory.szorc@gmail.com> |
---|---|
date | Sun, 15 Sep 2019 20:04:00 -0700 |
parents | 675775c33ab6 |
children | de7838053207 |
comparison
equal
deleted
inserted
replaced
42936:2da754532dd3 | 42937:69de49c4e39c |
---|---|
11 #include "zstd_compress_internal.h" | 11 #include "zstd_compress_internal.h" |
12 #include "zstd_fast.h" | 12 #include "zstd_fast.h" |
13 | 13 |
14 | 14 |
15 void ZSTD_fillHashTable(ZSTD_matchState_t* ms, | 15 void ZSTD_fillHashTable(ZSTD_matchState_t* ms, |
16 void const* end, ZSTD_dictTableLoadMethod_e dtlm) | 16 const void* const end, |
17 ZSTD_dictTableLoadMethod_e dtlm) | |
17 { | 18 { |
18 const ZSTD_compressionParameters* const cParams = &ms->cParams; | 19 const ZSTD_compressionParameters* const cParams = &ms->cParams; |
19 U32* const hashTable = ms->hashTable; | 20 U32* const hashTable = ms->hashTable; |
20 U32 const hBits = cParams->hashLog; | 21 U32 const hBits = cParams->hashLog; |
21 U32 const mls = cParams->minMatch; | 22 U32 const mls = cParams->minMatch; |
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; |
169 mLength = ZSTD_count(ip+4, match+4, iend) + 4; | 298 mLength = ZSTD_count(ip+4, match+4, iend) + 4; |
170 while (((ip>anchor) & (match>prefixStart)) | 299 while (((ip>anchor) & (match>prefixStart)) |
171 && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */ | 300 && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */ |
172 offset_2 = offset_1; | 301 offset_2 = offset_1; |
173 offset_1 = offset; | 302 offset_1 = offset; |
174 ZSTD_storeSeq(seqStore, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH); | 303 ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH); |
175 } | 304 } |
176 | 305 |
177 /* match found */ | 306 /* match found */ |
178 ip += mLength; | 307 ip += mLength; |
179 anchor = ip; | 308 anchor = ip; |
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) |
260 assert(ms->dictMatchState != NULL); | 353 assert(ms->dictMatchState != NULL); |
261 switch(mls) | 354 switch(mls) |
262 { | 355 { |
263 default: /* includes case 3 */ | 356 default: /* includes case 3 */ |
264 case 4 : | 357 case 4 : |
265 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 4, ZSTD_dictMatchState); | 358 return ZSTD_compressBlock_fast_dictMatchState_generic(ms, seqStore, rep, src, srcSize, 4); |
266 case 5 : | 359 case 5 : |
267 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 5, ZSTD_dictMatchState); | 360 return ZSTD_compressBlock_fast_dictMatchState_generic(ms, seqStore, rep, src, srcSize, 5); |
268 case 6 : | 361 case 6 : |
269 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 6, ZSTD_dictMatchState); | 362 return ZSTD_compressBlock_fast_dictMatchState_generic(ms, seqStore, rep, src, srcSize, 6); |
270 case 7 : | 363 case 7 : |
271 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 7, ZSTD_dictMatchState); | 364 return ZSTD_compressBlock_fast_dictMatchState_generic(ms, seqStore, rep, src, srcSize, 7); |
272 } | 365 } |
273 } | 366 } |
274 | 367 |
275 | 368 |
276 static size_t ZSTD_compressBlock_fast_extDict_generic( | 369 static size_t ZSTD_compressBlock_fast_extDict_generic( |
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; |
349 const BYTE* repMatch2 = repIndex2 < prefixStartIndex ? dictBase + repIndex2 : base + repIndex2; | 451 const BYTE* repMatch2 = repIndex2 < prefixStartIndex ? dictBase + repIndex2 : base + repIndex2; |
350 if ( (((U32)((prefixStartIndex-1) - repIndex2) >= 3) & (repIndex2 > dictStartIndex)) /* intentional overflow */ | 452 if ( (((U32)((prefixStartIndex-1) - repIndex2) >= 3) & (repIndex2 > dictStartIndex)) /* intentional overflow */ |
351 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) { | 453 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) { |
352 const BYTE* const repEnd2 = repIndex2 < prefixStartIndex ? dictEnd : iend; | 454 const BYTE* const repEnd2 = repIndex2 < prefixStartIndex ? dictEnd : iend; |
353 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixStart) + 4; | 455 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixStart) + 4; |
354 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */ | 456 U32 const tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */ |
355 ZSTD_storeSeq(seqStore, 0, anchor, 0, repLength2-MINMATCH); | 457 ZSTD_storeSeq(seqStore, 0, anchor, 0, repLength2-MINMATCH); |
356 hashTable[ZSTD_hashPtr(ip, hlog, mls)] = current2; | 458 hashTable[ZSTD_hashPtr(ip, hlog, mls)] = current2; |
357 ip += repLength2; | 459 ip += repLength2; |
358 anchor = ip; | 460 anchor = ip; |
359 continue; | 461 continue; |
364 /* save reps for next block */ | 466 /* save reps for next block */ |
365 rep[0] = offset_1; | 467 rep[0] = offset_1; |
366 rep[1] = offset_2; | 468 rep[1] = offset_2; |
367 | 469 |
368 /* Return the last literals size */ | 470 /* Return the last literals size */ |
369 return iend - anchor; | 471 return (size_t)(iend - anchor); |
370 } | 472 } |
371 | 473 |
372 | 474 |
373 size_t ZSTD_compressBlock_fast_extDict( | 475 size_t ZSTD_compressBlock_fast_extDict( |
374 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], | 476 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |