Mercurial > public > mercurial-scm > hg

comparison contrib/python-zstandard/zstd/compress/zstd_fast.c @ 40121:73fef626dae3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
zstandard: vendor python-zstandard 0.10.1 This was just released. 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. setup.py was updated to pass a new argument to python-zstandard's function for returning an Extension instance. Upstream had to change to use relative paths because Python 3.7's packaging doesn't seem to like absolute paths when defining sources, includes, etc. The default relative path calculation is relative to setup_zstd.py which is different from the directory of Mercurial's setup.py. The project contains a vendored copy of zstandard 1.3.6. The old version was 1.3.4. The API should be backwards compatible and nothing in core should need adjusted. However, there is a new "chunker" API that we may find useful in places where we want to emit compressed chunks of a fixed size. There are a pair of bug fixes in 0.10.0 with regards to compressobj() and decompressobj() when block flushing is used. I actually found these bugs when introducing these APIs in Mercurial! But existing Mercurial code is not affected because we don't perform block flushing. # no-check-commit because 3rd party code has different style guidelines Differential Revision: https://phab.mercurial-scm.org/D4911
author Gregory Szorc <gregory.szorc@gmail.com>
date Mon, 08 Oct 2018 16:27:40 -0700
parents b1fb341d8a61
children 675775c33ab6
comparison
equal deleted inserted replaced
40120:89742f1fa6cb 40121:73fef626dae3
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 ZSTD_compressionParameters const* cParams, 16 void const* end, ZSTD_dictTableLoadMethod_e dtlm)
17 void const* end) 17 {
18 { 18 const ZSTD_compressionParameters* const cParams = &ms->cParams;
19 U32* const hashTable = ms->hashTable; 19 U32* const hashTable = ms->hashTable;
20 U32 const hBits = cParams->hashLog; 20 U32 const hBits = cParams->hashLog;
21 U32 const mls = cParams->searchLength; 21 U32 const mls = cParams->searchLength;
22 const BYTE* const base = ms->window.base; 22 const BYTE* const base = ms->window.base;
23 const BYTE* ip = base + ms->nextToUpdate; 23 const BYTE* ip = base + ms->nextToUpdate;
32 U32 i; 32 U32 i;
33 for (i = 0; i < fastHashFillStep; ++i) { 33 for (i = 0; i < fastHashFillStep; ++i) {
34 size_t const hash = ZSTD_hashPtr(ip + i, hBits, mls); 34 size_t const hash = ZSTD_hashPtr(ip + i, hBits, mls);
35 if (i == 0 || hashTable[hash] == 0) 35 if (i == 0 || hashTable[hash] == 0)
36 hashTable[hash] = current + i; 36 hashTable[hash] = current + i;
37 /* Only load extra positions for ZSTD_dtlm_full */
38 if (dtlm == ZSTD_dtlm_fast)
39 break;
37 } 40 }
38 } 41 }
39 } 42 }
40 43
41 FORCE_INLINE_TEMPLATE 44 FORCE_INLINE_TEMPLATE
42 size_t ZSTD_compressBlock_fast_generic( 45 size_t ZSTD_compressBlock_fast_generic(
43 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 46 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
44 void const* src, size_t srcSize, 47 void const* src, size_t srcSize,
45 U32 const hlog, U32 const stepSize, U32 const mls) 48 U32 const mls, ZSTD_dictMode_e const dictMode)
46 { 49 {
50 const ZSTD_compressionParameters* const cParams = &ms->cParams;
47 U32* const hashTable = ms->hashTable; 51 U32* const hashTable = ms->hashTable;
52 U32 const hlog = cParams->hashLog;
53 /* support stepSize of 0 */
54 U32 const stepSize = cParams->targetLength + !(cParams->targetLength);
48 const BYTE* const base = ms->window.base; 55 const BYTE* const base = ms->window.base;
49 const BYTE* const istart = (const BYTE*)src; 56 const BYTE* const istart = (const BYTE*)src;
50 const BYTE* ip = istart; 57 const BYTE* ip = istart;
51 const BYTE* anchor = istart; 58 const BYTE* anchor = istart;
52 const U32 lowestIndex = ms->window.dictLimit; 59 const U32 prefixStartIndex = ms->window.dictLimit;
53 const BYTE* const lowest = base + lowestIndex; 60 const BYTE* const prefixStart = base + prefixStartIndex;
54 const BYTE* const iend = istart + srcSize; 61 const BYTE* const iend = istart + srcSize;
55 const BYTE* const ilimit = iend - HASH_READ_SIZE; 62 const BYTE* const ilimit = iend - HASH_READ_SIZE;
56 U32 offset_1=rep[0], offset_2=rep[1]; 63 U32 offset_1=rep[0], offset_2=rep[1];
57 U32 offsetSaved = 0; 64 U32 offsetSaved = 0;
58 65
66 const ZSTD_matchState_t* const dms = ms->dictMatchState;
67 const ZSTD_compressionParameters* const dictCParams =
68 dictMode == ZSTD_dictMatchState ?
69 &dms->cParams : NULL;
70 const U32* const dictHashTable = dictMode == ZSTD_dictMatchState ?
71 dms->hashTable : NULL;
72 const U32 dictStartIndex = dictMode == ZSTD_dictMatchState ?
73 dms->window.dictLimit : 0;
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);
84 const U32 dictHLog = dictMode == ZSTD_dictMatchState ?
85 dictCParams->hashLog : hlog;
86
87 assert(dictMode == ZSTD_noDict || dictMode == ZSTD_dictMatchState);
88
89 /* otherwise, we would get index underflow when translating a dict index
90 * into a local index */
91 assert(dictMode != ZSTD_dictMatchState
92 || prefixStartIndex >= (U32)(dictEnd - dictBase));
93
59 /* init */ 94 /* init */
60 ip += (ip==lowest); 95 ip += (dictAndPrefixLength == 0);
61 { U32 const maxRep = (U32)(ip-lowest); 96 if (dictMode == ZSTD_noDict) {
97 U32 const maxRep = (U32)(ip - prefixStart);
62 if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0; 98 if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;
63 if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0; 99 if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;
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);
64 } 106 }
65 107
66 /* Main Search Loop */ 108 /* Main Search Loop */
67 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */ 109 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */
68 size_t mLength; 110 size_t mLength;
69 size_t const h = ZSTD_hashPtr(ip, hlog, mls); 111 size_t const h = ZSTD_hashPtr(ip, hlog, mls);
70 U32 const current = (U32)(ip-base); 112 U32 const current = (U32)(ip-base);
71 U32 const matchIndex = hashTable[h]; 113 U32 const matchIndex = hashTable[h];
72 const BYTE* match = base + matchIndex; 114 const BYTE* match = base + matchIndex;
115 const U32 repIndex = current + 1 - offset_1;
116 const BYTE* repMatch = (dictMode == ZSTD_dictMatchState
117 && repIndex < prefixStartIndex) ?
118 dictBase + (repIndex - dictIndexDelta) :
119 base + repIndex;
73 hashTable[h] = current; /* update hash table */ 120 hashTable[h] = current; /* update hash table */
74 121
75 if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) { 122 if ( (dictMode == ZSTD_dictMatchState)
123 && ((U32)((prefixStartIndex-1) - repIndex) >= 3) /* intentional underflow : ensure repIndex isn't overlapping dict + prefix */
124 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
125 const BYTE* const repMatchEnd = repIndex < prefixStartIndex ? dictEnd : iend;
126 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixStart) + 4;
127 ip++;
128 ZSTD_storeSeq(seqStore, 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)))) {
76 mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4; 131 mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
77 ip++; 132 ip++;
78 ZSTD_storeSeq(seqStore, ip-anchor, anchor, 0, mLength-MINMATCH); 133 ZSTD_storeSeq(seqStore, ip-anchor, anchor, 0, mLength-MINMATCH);
79 } else { 134 } else if ( (matchIndex <= prefixStartIndex) ) {
80 if ( (matchIndex <= lowestIndex) 135 if (dictMode == ZSTD_dictMatchState) {
81 || (MEM_read32(match) != MEM_read32(ip)) ) { 136 size_t const dictHash = ZSTD_hashPtr(ip, dictHLog, mls);
137 U32 const dictMatchIndex = dictHashTable[dictHash];
138 const BYTE* dictMatch = dictBase + dictMatchIndex;
139 if (dictMatchIndex <= dictStartIndex ||
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 {
82 assert(stepSize >= 1); 157 assert(stepSize >= 1);
83 ip += ((ip-anchor) >> kSearchStrength) + stepSize; 158 ip += ((ip-anchor) >> kSearchStrength) + stepSize;
84 continue; 159 continue;
85 } 160 }
161 } else if (MEM_read32(match) != MEM_read32(ip)) {
162 /* it's not a match, and we're not going to check the dictionary */
163 assert(stepSize >= 1);
164 ip += ((ip-anchor) >> kSearchStrength) + stepSize;
165 continue;
166 } else {
167 /* found a regular match */
168 U32 const offset = (U32)(ip-match);
86 mLength = ZSTD_count(ip+4, match+4, iend) + 4; 169 mLength = ZSTD_count(ip+4, match+4, iend) + 4;
87 { U32 const offset = (U32)(ip-match); 170 while (((ip>anchor) & (match>prefixStart))
88 while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */ 171 && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
89 offset_2 = offset_1; 172 offset_2 = offset_1;
90 offset_1 = offset; 173 offset_1 = offset;
91 ZSTD_storeSeq(seqStore, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH); 174 ZSTD_storeSeq(seqStore, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
92 } } 175 }
93 176
94 /* match found */ 177 /* match found */
95 ip += mLength; 178 ip += mLength;
96 anchor = ip; 179 anchor = ip;
97 180
98 if (ip <= ilimit) { 181 if (ip <= ilimit) {
99 /* Fill Table */ 182 /* Fill Table */
183 assert(base+current+2 > istart); /* check base overflow */
100 hashTable[ZSTD_hashPtr(base+current+2, hlog, mls)] = current+2; /* here because current+2 could be > iend-8 */ 184 hashTable[ZSTD_hashPtr(base+current+2, hlog, mls)] = current+2; /* here because current+2 could be > iend-8 */
101 hashTable[ZSTD_hashPtr(ip-2, hlog, mls)] = (U32)(ip-2-base); 185 hashTable[ZSTD_hashPtr(ip-2, hlog, mls)] = (U32)(ip-2-base);
186
102 /* check immediate repcode */ 187 /* check immediate repcode */
103 while ( (ip <= ilimit) 188 if (dictMode == ZSTD_dictMatchState) {
104 && ( (offset_2>0) 189 while (ip <= ilimit) {
105 & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) { 190 U32 const current2 = (U32)(ip-base);
106 /* store sequence */ 191 U32 const repIndex2 = current2 - offset_2;
107 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4; 192 const BYTE* repMatch2 = repIndex2 < prefixStartIndex ?
108 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; } /* swap offset_2 <=> offset_1 */ 193 dictBase - dictIndexDelta + repIndex2 :
109 hashTable[ZSTD_hashPtr(ip, hlog, mls)] = (U32)(ip-base); 194 base + repIndex2;
110 ZSTD_storeSeq(seqStore, 0, anchor, 0, rLength-MINMATCH); 195 if ( ((U32)((prefixStartIndex-1) - (U32)repIndex2) >= 3 /* intentional overflow */)
111 ip += rLength; 196 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
112 anchor = ip; 197 const BYTE* const repEnd2 = repIndex2 < prefixStartIndex ? dictEnd : iend;
113 continue; /* faster when present ... (?) */ 198 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixStart) + 4;
114 } } } 199 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */
200 ZSTD_storeSeq(seqStore, 0, anchor, 0, repLength2-MINMATCH);
201 hashTable[ZSTD_hashPtr(ip, hlog, mls)] = current2;
202 ip += repLength2;
203 anchor = ip;
204 continue;
205 }
206 break;
207 }
208 }
209
210 if (dictMode == ZSTD_noDict) {
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 } } } }
115 223
116 /* save reps for next block */ 224 /* save reps for next block */
117 rep[0] = offset_1 ? offset_1 : offsetSaved; 225 rep[0] = offset_1 ? offset_1 : offsetSaved;
118 rep[1] = offset_2 ? offset_2 : offsetSaved; 226 rep[1] = offset_2 ? offset_2 : offsetSaved;
119 227
122 } 230 }
123 231
124 232
125 size_t ZSTD_compressBlock_fast( 233 size_t ZSTD_compressBlock_fast(
126 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 234 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
127 ZSTD_compressionParameters const* cParams, void const* src, size_t srcSize) 235 void const* src, size_t srcSize)
128 { 236 {
129 U32 const hlog = cParams->hashLog; 237 ZSTD_compressionParameters const* cParams = &ms->cParams;
130 U32 const mls = cParams->searchLength; 238 U32 const mls = cParams->searchLength;
131 U32 const stepSize = cParams->targetLength; 239 assert(ms->dictMatchState == NULL);
132 switch(mls) 240 switch(mls)
133 { 241 {
134 default: /* includes case 3 */ 242 default: /* includes case 3 */
135 case 4 : 243 case 4 :
136 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, hlog, stepSize, 4); 244 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 4, ZSTD_noDict);
137 case 5 : 245 case 5 :
138 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, hlog, stepSize, 5); 246 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 5, ZSTD_noDict);
139 case 6 : 247 case 6 :
140 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, hlog, stepSize, 6); 248 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 6, ZSTD_noDict);
141 case 7 : 249 case 7 :
142 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, hlog, stepSize, 7); 250 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 7, ZSTD_noDict);
251 }
252 }
253
254 size_t ZSTD_compressBlock_fast_dictMatchState(
255 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
256 void const* src, size_t srcSize)
257 {
258 ZSTD_compressionParameters const* cParams = &ms->cParams;
259 U32 const mls = cParams->searchLength;
260 assert(ms->dictMatchState != NULL);
261 switch(mls)
262 {
263 default: /* includes case 3 */
264 case 4 :
265 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 4, ZSTD_dictMatchState);
266 case 5 :
267 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 5, ZSTD_dictMatchState);
268 case 6 :
269 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 6, ZSTD_dictMatchState);
270 case 7 :
271 return ZSTD_compressBlock_fast_generic(ms, seqStore, rep, src, srcSize, 7, ZSTD_dictMatchState);
143 } 272 }
144 } 273 }
145 274
146 275
147 static size_t ZSTD_compressBlock_fast_extDict_generic( 276 static size_t ZSTD_compressBlock_fast_extDict_generic(
148 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 277 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
149 void const* src, size_t srcSize, 278 void const* src, size_t srcSize, U32 const mls)
150 U32 const hlog, U32 const stepSize, U32 const mls) 279 {
151 { 280 const ZSTD_compressionParameters* const cParams = &ms->cParams;
152 U32* hashTable = ms->hashTable; 281 U32* const hashTable = ms->hashTable;
282 U32 const hlog = cParams->hashLog;
283 /* support stepSize of 0 */
284 U32 const stepSize = cParams->targetLength + !(cParams->targetLength);
153 const BYTE* const base = ms->window.base; 285 const BYTE* const base = ms->window.base;
154 const BYTE* const dictBase = ms->window.dictBase; 286 const BYTE* const dictBase = ms->window.dictBase;
155 const BYTE* const istart = (const BYTE*)src; 287 const BYTE* const istart = (const BYTE*)src;
156 const BYTE* ip = istart; 288 const BYTE* ip = istart;
157 const BYTE* anchor = istart; 289 const BYTE* anchor = istart;
158 const U32 lowestIndex = ms->window.lowLimit; 290 const U32 dictStartIndex = ms->window.lowLimit;
159 const BYTE* const dictStart = dictBase + lowestIndex; 291 const BYTE* const dictStart = dictBase + dictStartIndex;
160 const U32 dictLimit = ms->window.dictLimit; 292 const U32 prefixStartIndex = ms->window.dictLimit;
161 const BYTE* const lowPrefixPtr = base + dictLimit; 293 const BYTE* const prefixStart = base + prefixStartIndex;
162 const BYTE* const dictEnd = dictBase + dictLimit; 294 const BYTE* const dictEnd = dictBase + prefixStartIndex;
163 const BYTE* const iend = istart + srcSize; 295 const BYTE* const iend = istart + srcSize;
164 const BYTE* const ilimit = iend - 8; 296 const BYTE* const ilimit = iend - 8;
165 U32 offset_1=rep[0], offset_2=rep[1]; 297 U32 offset_1=rep[0], offset_2=rep[1];
166 298
167 /* Search Loop */ 299 /* Search Loop */
168 while (ip < ilimit) { /* < instead of <=, because (ip+1) */ 300 while (ip < ilimit) { /* < instead of <=, because (ip+1) */
169 const size_t h = ZSTD_hashPtr(ip, hlog, mls); 301 const size_t h = ZSTD_hashPtr(ip, hlog, mls);
170 const U32 matchIndex = hashTable[h]; 302 const U32 matchIndex = hashTable[h];
171 const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base; 303 const BYTE* const matchBase = matchIndex < prefixStartIndex ? dictBase : base;
172 const BYTE* match = matchBase + matchIndex; 304 const BYTE* match = matchBase + matchIndex;
173 const U32 current = (U32)(ip-base); 305 const U32 current = (U32)(ip-base);
174 const U32 repIndex = current + 1 - offset_1; /* offset_1 expected <= current +1 */ 306 const U32 repIndex = current + 1 - offset_1;
175 const BYTE* repBase = repIndex < dictLimit ? dictBase : base; 307 const BYTE* const repBase = repIndex < prefixStartIndex ? dictBase : base;
176 const BYTE* repMatch = repBase + repIndex; 308 const BYTE* const repMatch = repBase + repIndex;
177 size_t mLength; 309 size_t mLength;
178 hashTable[h] = current; /* update hash table */ 310 hashTable[h] = current; /* update hash table */
179 311 assert(offset_1 <= current +1); /* check repIndex */
180 if ( (((U32)((dictLimit-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex)) 312
313 if ( (((U32)((prefixStartIndex-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > dictStartIndex))
181 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) { 314 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
182 const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend; 315 const BYTE* repMatchEnd = repIndex < prefixStartIndex ? dictEnd : iend;
183 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, lowPrefixPtr) + 4; 316 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixStart) + 4;
184 ip++; 317 ip++;
185 ZSTD_storeSeq(seqStore, ip-anchor, anchor, 0, mLength-MINMATCH); 318 ZSTD_storeSeq(seqStore, ip-anchor, anchor, 0, mLength-MINMATCH);
186 } else { 319 } else {
187 if ( (matchIndex < lowestIndex) || 320 if ( (matchIndex < dictStartIndex) ||
188 (MEM_read32(match) != MEM_read32(ip)) ) { 321 (MEM_read32(match) != MEM_read32(ip)) ) {
189 assert(stepSize >= 1); 322 assert(stepSize >= 1);
190 ip += ((ip-anchor) >> kSearchStrength) + stepSize; 323 ip += ((ip-anchor) >> kSearchStrength) + stepSize;
191 continue; 324 continue;
192 } 325 }
193 { const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend; 326 { const BYTE* matchEnd = matchIndex < prefixStartIndex ? dictEnd : iend;
194 const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr; 327 const BYTE* lowMatchPtr = matchIndex < prefixStartIndex ? dictStart : prefixStart;
195 U32 offset; 328 U32 offset;
196 mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, lowPrefixPtr) + 4; 329 mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, prefixStart) + 4;
197 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */ 330 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
198 offset = current - matchIndex; 331 offset = current - matchIndex;
199 offset_2 = offset_1; 332 offset_2 = offset_1;
200 offset_1 = offset; 333 offset_1 = offset;
201 ZSTD_storeSeq(seqStore, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH); 334 ZSTD_storeSeq(seqStore, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
211 hashTable[ZSTD_hashPtr(ip-2, hlog, mls)] = (U32)(ip-2-base); 344 hashTable[ZSTD_hashPtr(ip-2, hlog, mls)] = (U32)(ip-2-base);
212 /* check immediate repcode */ 345 /* check immediate repcode */
213 while (ip <= ilimit) { 346 while (ip <= ilimit) {
214 U32 const current2 = (U32)(ip-base); 347 U32 const current2 = (U32)(ip-base);
215 U32 const repIndex2 = current2 - offset_2; 348 U32 const repIndex2 = current2 - offset_2;
216 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2; 349 const BYTE* repMatch2 = repIndex2 < prefixStartIndex ? dictBase + repIndex2 : base + repIndex2;
217 if ( (((U32)((dictLimit-1) - repIndex2) >= 3) & (repIndex2 > lowestIndex)) /* intentional overflow */ 350 if ( (((U32)((prefixStartIndex-1) - repIndex2) >= 3) & (repIndex2 > dictStartIndex)) /* intentional overflow */
218 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) { 351 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
219 const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend; 352 const BYTE* const repEnd2 = repIndex2 < prefixStartIndex ? dictEnd : iend;
220 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, lowPrefixPtr) + 4; 353 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixStart) + 4;
221 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */ 354 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */
222 ZSTD_storeSeq(seqStore, 0, anchor, 0, repLength2-MINMATCH); 355 ZSTD_storeSeq(seqStore, 0, anchor, 0, repLength2-MINMATCH);
223 hashTable[ZSTD_hashPtr(ip, hlog, mls)] = current2; 356 hashTable[ZSTD_hashPtr(ip, hlog, mls)] = current2;
224 ip += repLength2; 357 ip += repLength2;
225 anchor = ip; 358 anchor = ip;
237 } 370 }
238 371
239 372
240 size_t ZSTD_compressBlock_fast_extDict( 373 size_t ZSTD_compressBlock_fast_extDict(
241 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 374 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
242 ZSTD_compressionParameters const* cParams, void const* src, size_t srcSize) 375 void const* src, size_t srcSize)
243 { 376 {
244 U32 const hlog = cParams->hashLog; 377 ZSTD_compressionParameters const* cParams = &ms->cParams;
245 U32 const mls = cParams->searchLength; 378 U32 const mls = cParams->searchLength;
246 U32 const stepSize = cParams->targetLength;
247 switch(mls) 379 switch(mls)
248 { 380 {
249 default: /* includes case 3 */ 381 default: /* includes case 3 */
250 case 4 : 382 case 4 :
251 return ZSTD_compressBlock_fast_extDict_generic(ms, seqStore, rep, src, srcSize, hlog, stepSize, 4); 383 return ZSTD_compressBlock_fast_extDict_generic(ms, seqStore, rep, src, srcSize, 4);
252 case 5 : 384 case 5 :
253 return ZSTD_compressBlock_fast_extDict_generic(ms, seqStore, rep, src, srcSize, hlog, stepSize, 5); 385 return ZSTD_compressBlock_fast_extDict_generic(ms, seqStore, rep, src, srcSize, 5);
254 case 6 : 386 case 6 :
255 return ZSTD_compressBlock_fast_extDict_generic(ms, seqStore, rep, src, srcSize, hlog, stepSize, 6); 387 return ZSTD_compressBlock_fast_extDict_generic(ms, seqStore, rep, src, srcSize, 6);
256 case 7 : 388 case 7 :
257 return ZSTD_compressBlock_fast_extDict_generic(ms, seqStore, rep, src, srcSize, hlog, stepSize, 7); 389 return ZSTD_compressBlock_fast_extDict_generic(ms, seqStore, rep, src, srcSize, 7);
258 } 390 }
259 } 391 }