ReactOS  0.4.15-dev-4927-gfe8f806
zstd_double_fast.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016-2020, Yann Collet, Facebook, Inc.
3  * All rights reserved.
4  *
5  * This source code is licensed under both the BSD-style license (found in the
6  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7  * in the COPYING file in the root directory of this source tree).
8  * You may select, at your option, one of the above-listed licenses.
9  */
10 
11 #include "zstd_compress_internal.h"
12 #include "zstd_double_fast.h"
13 
14 
16  void const* end, ZSTD_dictTableLoadMethod_e dtlm)
17 {
18  const ZSTD_compressionParameters* const cParams = &ms->cParams;
19  U32* const hashLarge = ms->hashTable;
20  U32 const hBitsL = cParams->hashLog;
21  U32 const mls = cParams->minMatch;
22  U32* const hashSmall = ms->chainTable;
23  U32 const hBitsS = cParams->chainLog;
24  const BYTE* const base = ms->window.base;
25  const BYTE* ip = base + ms->nextToUpdate;
26  const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;
27  const U32 fastHashFillStep = 3;
28 
29  /* Always insert every fastHashFillStep position into the hash tables.
30  * Insert the other positions into the large hash table if their entry
31  * is empty.
32  */
33  for (; ip + fastHashFillStep - 1 <= iend; ip += fastHashFillStep) {
34  U32 const current = (U32)(ip - base);
35  U32 i;
36  for (i = 0; i < fastHashFillStep; ++i) {
37  size_t const smHash = ZSTD_hashPtr(ip + i, hBitsS, mls);
38  size_t const lgHash = ZSTD_hashPtr(ip + i, hBitsL, 8);
39  if (i == 0)
40  hashSmall[smHash] = current + i;
41  if (i == 0 || hashLarge[lgHash] == 0)
42  hashLarge[lgHash] = current + i;
43  /* Only load extra positions for ZSTD_dtlm_full */
44  if (dtlm == ZSTD_dtlm_fast)
45  break;
46  } }
47 }
48 
49 
52  ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
53  void const* src, size_t srcSize,
54  U32 const mls /* template */, ZSTD_dictMode_e const dictMode)
55 {
56  ZSTD_compressionParameters const* cParams = &ms->cParams;
57  U32* const hashLong = ms->hashTable;
58  const U32 hBitsL = cParams->hashLog;
59  U32* const hashSmall = ms->chainTable;
60  const U32 hBitsS = cParams->chainLog;
61  const BYTE* const base = ms->window.base;
62  const BYTE* const istart = (const BYTE*)src;
63  const BYTE* ip = istart;
64  const BYTE* anchor = istart;
65  const U32 endIndex = (U32)((size_t)(istart - base) + srcSize);
66  /* presumes that, if there is a dictionary, it must be using Attach mode */
67  const U32 prefixLowestIndex = ZSTD_getLowestPrefixIndex(ms, endIndex, cParams->windowLog);
68  const BYTE* const prefixLowest = base + prefixLowestIndex;
69  const BYTE* const iend = istart + srcSize;
70  const BYTE* const ilimit = iend - HASH_READ_SIZE;
71  U32 offset_1=rep[0], offset_2=rep[1];
72  U32 offsetSaved = 0;
73 
74  const ZSTD_matchState_t* const dms = ms->dictMatchState;
75  const ZSTD_compressionParameters* const dictCParams =
76  dictMode == ZSTD_dictMatchState ?
77  &dms->cParams : NULL;
78  const U32* const dictHashLong = dictMode == ZSTD_dictMatchState ?
79  dms->hashTable : NULL;
80  const U32* const dictHashSmall = dictMode == ZSTD_dictMatchState ?
81  dms->chainTable : NULL;
82  const U32 dictStartIndex = dictMode == ZSTD_dictMatchState ?
83  dms->window.dictLimit : 0;
84  const BYTE* const dictBase = dictMode == ZSTD_dictMatchState ?
85  dms->window.base : NULL;
86  const BYTE* const dictStart = dictMode == ZSTD_dictMatchState ?
87  dictBase + dictStartIndex : NULL;
88  const BYTE* const dictEnd = dictMode == ZSTD_dictMatchState ?
89  dms->window.nextSrc : NULL;
90  const U32 dictIndexDelta = dictMode == ZSTD_dictMatchState ?
91  prefixLowestIndex - (U32)(dictEnd - dictBase) :
92  0;
93  const U32 dictHBitsL = dictMode == ZSTD_dictMatchState ?
94  dictCParams->hashLog : hBitsL;
95  const U32 dictHBitsS = dictMode == ZSTD_dictMatchState ?
96  dictCParams->chainLog : hBitsS;
97  const U32 dictAndPrefixLength = (U32)((ip - prefixLowest) + (dictEnd - dictStart));
98 
99  DEBUGLOG(5, "ZSTD_compressBlock_doubleFast_generic");
100 
101  assert(dictMode == ZSTD_noDict || dictMode == ZSTD_dictMatchState);
102 
103  /* if a dictionary is attached, it must be within window range */
104  if (dictMode == ZSTD_dictMatchState) {
105  assert(ms->window.dictLimit + (1U << cParams->windowLog) >= endIndex);
106  }
107 
108  /* init */
109  ip += (dictAndPrefixLength == 0);
110  if (dictMode == ZSTD_noDict) {
111  U32 const current = (U32)(ip - base);
112  U32 const windowLow = ZSTD_getLowestPrefixIndex(ms, current, cParams->windowLog);
113  U32 const maxRep = current - windowLow;
114  if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;
115  if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;
116  }
117  if (dictMode == ZSTD_dictMatchState) {
118  /* dictMatchState repCode checks don't currently handle repCode == 0
119  * disabling. */
120  assert(offset_1 <= dictAndPrefixLength);
121  assert(offset_2 <= dictAndPrefixLength);
122  }
123 
124  /* Main Search Loop */
125  while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */
126  size_t mLength;
127  U32 offset;
128  size_t const h2 = ZSTD_hashPtr(ip, hBitsL, 8);
129  size_t const h = ZSTD_hashPtr(ip, hBitsS, mls);
130  size_t const dictHL = ZSTD_hashPtr(ip, dictHBitsL, 8);
131  size_t const dictHS = ZSTD_hashPtr(ip, dictHBitsS, mls);
132  U32 const current = (U32)(ip-base);
133  U32 const matchIndexL = hashLong[h2];
134  U32 matchIndexS = hashSmall[h];
135  const BYTE* matchLong = base + matchIndexL;
136  const BYTE* match = base + matchIndexS;
137  const U32 repIndex = current + 1 - offset_1;
138  const BYTE* repMatch = (dictMode == ZSTD_dictMatchState
139  && repIndex < prefixLowestIndex) ?
140  dictBase + (repIndex - dictIndexDelta) :
141  base + repIndex;
142  hashLong[h2] = hashSmall[h] = current; /* update hash tables */
143 
144  /* check dictMatchState repcode */
145  if (dictMode == ZSTD_dictMatchState
146  && ((U32)((prefixLowestIndex-1) - repIndex) >= 3 /* intentional underflow */)
147  && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
148  const BYTE* repMatchEnd = repIndex < prefixLowestIndex ? dictEnd : iend;
149  mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixLowest) + 4;
150  ip++;
151  ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, 0, mLength-MINMATCH);
152  goto _match_stored;
153  }
154 
155  /* check noDict repcode */
156  if ( dictMode == ZSTD_noDict
157  && ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1)))) {
158  mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
159  ip++;
160  ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, 0, mLength-MINMATCH);
161  goto _match_stored;
162  }
163 
164  if (matchIndexL > prefixLowestIndex) {
165  /* check prefix long match */
166  if (MEM_read64(matchLong) == MEM_read64(ip)) {
167  mLength = ZSTD_count(ip+8, matchLong+8, iend) + 8;
168  offset = (U32)(ip-matchLong);
169  while (((ip>anchor) & (matchLong>prefixLowest)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */
170  goto _match_found;
171  }
172  } else if (dictMode == ZSTD_dictMatchState) {
173  /* check dictMatchState long match */
174  U32 const dictMatchIndexL = dictHashLong[dictHL];
175  const BYTE* dictMatchL = dictBase + dictMatchIndexL;
176  assert(dictMatchL < dictEnd);
177 
178  if (dictMatchL > dictStart && MEM_read64(dictMatchL) == MEM_read64(ip)) {
179  mLength = ZSTD_count_2segments(ip+8, dictMatchL+8, iend, dictEnd, prefixLowest) + 8;
180  offset = (U32)(current - dictMatchIndexL - dictIndexDelta);
181  while (((ip>anchor) & (dictMatchL>dictStart)) && (ip[-1] == dictMatchL[-1])) { ip--; dictMatchL--; mLength++; } /* catch up */
182  goto _match_found;
183  } }
184 
185  if (matchIndexS > prefixLowestIndex) {
186  /* check prefix short match */
187  if (MEM_read32(match) == MEM_read32(ip)) {
188  goto _search_next_long;
189  }
190  } else if (dictMode == ZSTD_dictMatchState) {
191  /* check dictMatchState short match */
192  U32 const dictMatchIndexS = dictHashSmall[dictHS];
193  match = dictBase + dictMatchIndexS;
194  matchIndexS = dictMatchIndexS + dictIndexDelta;
195 
196  if (match > dictStart && MEM_read32(match) == MEM_read32(ip)) {
197  goto _search_next_long;
198  } }
199 
200  ip += ((ip-anchor) >> kSearchStrength) + 1;
201 #if defined(__aarch64__)
202  PREFETCH_L1(ip+256);
203 #endif
204  continue;
205 
206 _search_next_long:
207 
208  { size_t const hl3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
209  size_t const dictHLNext = ZSTD_hashPtr(ip+1, dictHBitsL, 8);
210  U32 const matchIndexL3 = hashLong[hl3];
211  const BYTE* matchL3 = base + matchIndexL3;
212  hashLong[hl3] = current + 1;
213 
214  /* check prefix long +1 match */
215  if (matchIndexL3 > prefixLowestIndex) {
216  if (MEM_read64(matchL3) == MEM_read64(ip+1)) {
217  mLength = ZSTD_count(ip+9, matchL3+8, iend) + 8;
218  ip++;
219  offset = (U32)(ip-matchL3);
220  while (((ip>anchor) & (matchL3>prefixLowest)) && (ip[-1] == matchL3[-1])) { ip--; matchL3--; mLength++; } /* catch up */
221  goto _match_found;
222  }
223  } else if (dictMode == ZSTD_dictMatchState) {
224  /* check dict long +1 match */
225  U32 const dictMatchIndexL3 = dictHashLong[dictHLNext];
226  const BYTE* dictMatchL3 = dictBase + dictMatchIndexL3;
227  assert(dictMatchL3 < dictEnd);
228  if (dictMatchL3 > dictStart && MEM_read64(dictMatchL3) == MEM_read64(ip+1)) {
229  mLength = ZSTD_count_2segments(ip+1+8, dictMatchL3+8, iend, dictEnd, prefixLowest) + 8;
230  ip++;
231  offset = (U32)(current + 1 - dictMatchIndexL3 - dictIndexDelta);
232  while (((ip>anchor) & (dictMatchL3>dictStart)) && (ip[-1] == dictMatchL3[-1])) { ip--; dictMatchL3--; mLength++; } /* catch up */
233  goto _match_found;
234  } } }
235 
236  /* if no long +1 match, explore the short match we found */
237  if (dictMode == ZSTD_dictMatchState && matchIndexS < prefixLowestIndex) {
238  mLength = ZSTD_count_2segments(ip+4, match+4, iend, dictEnd, prefixLowest) + 4;
239  offset = (U32)(current - matchIndexS);
240  while (((ip>anchor) & (match>dictStart)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
241  } else {
242  mLength = ZSTD_count(ip+4, match+4, iend) + 4;
243  offset = (U32)(ip - match);
244  while (((ip>anchor) & (match>prefixLowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
245  }
246 
247  /* fall-through */
248 
249 _match_found:
250  offset_2 = offset_1;
251  offset_1 = offset;
252 
253  ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
254 
255 _match_stored:
256  /* match found */
257  ip += mLength;
258  anchor = ip;
259 
260  if (ip <= ilimit) {
261  /* Complementary insertion */
262  /* done after iLimit test, as candidates could be > iend-8 */
263  { U32 const indexToInsert = current+2;
264  hashLong[ZSTD_hashPtr(base+indexToInsert, hBitsL, 8)] = indexToInsert;
265  hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base);
266  hashSmall[ZSTD_hashPtr(base+indexToInsert, hBitsS, mls)] = indexToInsert;
267  hashSmall[ZSTD_hashPtr(ip-1, hBitsS, mls)] = (U32)(ip-1-base);
268  }
269 
270  /* check immediate repcode */
271  if (dictMode == ZSTD_dictMatchState) {
272  while (ip <= ilimit) {
273  U32 const current2 = (U32)(ip-base);
274  U32 const repIndex2 = current2 - offset_2;
275  const BYTE* repMatch2 = dictMode == ZSTD_dictMatchState
276  && repIndex2 < prefixLowestIndex ?
277  dictBase + repIndex2 - dictIndexDelta :
278  base + repIndex2;
279  if ( ((U32)((prefixLowestIndex-1) - (U32)repIndex2) >= 3 /* intentional overflow */)
280  && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
281  const BYTE* const repEnd2 = repIndex2 < prefixLowestIndex ? dictEnd : iend;
282  size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixLowest) + 4;
283  U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */
284  ZSTD_storeSeq(seqStore, 0, anchor, iend, 0, repLength2-MINMATCH);
285  hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2;
286  hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2;
287  ip += repLength2;
288  anchor = ip;
289  continue;
290  }
291  break;
292  } }
293 
294  if (dictMode == ZSTD_noDict) {
295  while ( (ip <= ilimit)
296  && ( (offset_2>0)
297  & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
298  /* store sequence */
299  size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
300  U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; /* swap offset_2 <=> offset_1 */
301  hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip-base);
302  hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip-base);
303  ZSTD_storeSeq(seqStore, 0, anchor, iend, 0, rLength-MINMATCH);
304  ip += rLength;
305  anchor = ip;
306  continue; /* faster when present ... (?) */
307  } } }
308  } /* while (ip < ilimit) */
309 
310  /* save reps for next block */
311  rep[0] = offset_1 ? offset_1 : offsetSaved;
312  rep[1] = offset_2 ? offset_2 : offsetSaved;
313 
314  /* Return the last literals size */
315  return (size_t)(iend - anchor);
316 }
317 
318 
320  ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
321  void const* src, size_t srcSize)
322 {
323  const U32 mls = ms->cParams.minMatch;
324  switch(mls)
325  {
326  default: /* includes case 3 */
327  case 4 :
328  return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 4, ZSTD_noDict);
329  case 5 :
330  return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 5, ZSTD_noDict);
331  case 6 :
332  return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 6, ZSTD_noDict);
333  case 7 :
334  return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 7, ZSTD_noDict);
335  }
336 }
337 
338 
340  ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
341  void const* src, size_t srcSize)
342 {
343  const U32 mls = ms->cParams.minMatch;
344  switch(mls)
345  {
346  default: /* includes case 3 */
347  case 4 :
348  return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 4, ZSTD_dictMatchState);
349  case 5 :
350  return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 5, ZSTD_dictMatchState);
351  case 6 :
352  return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 6, ZSTD_dictMatchState);
353  case 7 :
354  return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 7, ZSTD_dictMatchState);
355  }
356 }
357 
358 
360  ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
361  void const* src, size_t srcSize,
362  U32 const mls /* template */)
363 {
364  ZSTD_compressionParameters const* cParams = &ms->cParams;
365  U32* const hashLong = ms->hashTable;
366  U32 const hBitsL = cParams->hashLog;
367  U32* const hashSmall = ms->chainTable;
368  U32 const hBitsS = cParams->chainLog;
369  const BYTE* const istart = (const BYTE*)src;
370  const BYTE* ip = istart;
371  const BYTE* anchor = istart;
372  const BYTE* const iend = istart + srcSize;
373  const BYTE* const ilimit = iend - 8;
374  const BYTE* const base = ms->window.base;
375  const U32 endIndex = (U32)((size_t)(istart - base) + srcSize);
376  const U32 lowLimit = ZSTD_getLowestMatchIndex(ms, endIndex, cParams->windowLog);
377  const U32 dictStartIndex = lowLimit;
378  const U32 dictLimit = ms->window.dictLimit;
379  const U32 prefixStartIndex = (dictLimit > lowLimit) ? dictLimit : lowLimit;
380  const BYTE* const prefixStart = base + prefixStartIndex;
381  const BYTE* const dictBase = ms->window.dictBase;
382  const BYTE* const dictStart = dictBase + dictStartIndex;
383  const BYTE* const dictEnd = dictBase + prefixStartIndex;
384  U32 offset_1=rep[0], offset_2=rep[1];
385 
386  DEBUGLOG(5, "ZSTD_compressBlock_doubleFast_extDict_generic (srcSize=%zu)", srcSize);
387 
388  /* if extDict is invalidated due to maxDistance, switch to "regular" variant */
389  if (prefixStartIndex == dictStartIndex)
390  return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, mls, ZSTD_noDict);
391 
392  /* Search Loop */
393  while (ip < ilimit) { /* < instead of <=, because (ip+1) */
394  const size_t hSmall = ZSTD_hashPtr(ip, hBitsS, mls);
395  const U32 matchIndex = hashSmall[hSmall];
396  const BYTE* const matchBase = matchIndex < prefixStartIndex ? dictBase : base;
397  const BYTE* match = matchBase + matchIndex;
398 
399  const size_t hLong = ZSTD_hashPtr(ip, hBitsL, 8);
400  const U32 matchLongIndex = hashLong[hLong];
401  const BYTE* const matchLongBase = matchLongIndex < prefixStartIndex ? dictBase : base;
402  const BYTE* matchLong = matchLongBase + matchLongIndex;
403 
404  const U32 current = (U32)(ip-base);
405  const U32 repIndex = current + 1 - offset_1; /* offset_1 expected <= current +1 */
406  const BYTE* const repBase = repIndex < prefixStartIndex ? dictBase : base;
407  const BYTE* const repMatch = repBase + repIndex;
408  size_t mLength;
409  hashSmall[hSmall] = hashLong[hLong] = current; /* update hash table */
410 
411  if ((((U32)((prefixStartIndex-1) - repIndex) >= 3) /* intentional underflow : ensure repIndex doesn't overlap dict + prefix */
412  & (repIndex > dictStartIndex))
413  && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
414  const BYTE* repMatchEnd = repIndex < prefixStartIndex ? dictEnd : iend;
415  mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixStart) + 4;
416  ip++;
417  ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, 0, mLength-MINMATCH);
418  } else {
419  if ((matchLongIndex > dictStartIndex) && (MEM_read64(matchLong) == MEM_read64(ip))) {
420  const BYTE* const matchEnd = matchLongIndex < prefixStartIndex ? dictEnd : iend;
421  const BYTE* const lowMatchPtr = matchLongIndex < prefixStartIndex ? dictStart : prefixStart;
422  U32 offset;
423  mLength = ZSTD_count_2segments(ip+8, matchLong+8, iend, matchEnd, prefixStart) + 8;
424  offset = current - matchLongIndex;
425  while (((ip>anchor) & (matchLong>lowMatchPtr)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */
426  offset_2 = offset_1;
427  offset_1 = offset;
428  ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
429 
430  } else if ((matchIndex > dictStartIndex) && (MEM_read32(match) == MEM_read32(ip))) {
431  size_t const h3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
432  U32 const matchIndex3 = hashLong[h3];
433  const BYTE* const match3Base = matchIndex3 < prefixStartIndex ? dictBase : base;
434  const BYTE* match3 = match3Base + matchIndex3;
435  U32 offset;
436  hashLong[h3] = current + 1;
437  if ( (matchIndex3 > dictStartIndex) && (MEM_read64(match3) == MEM_read64(ip+1)) ) {
438  const BYTE* const matchEnd = matchIndex3 < prefixStartIndex ? dictEnd : iend;
439  const BYTE* const lowMatchPtr = matchIndex3 < prefixStartIndex ? dictStart : prefixStart;
440  mLength = ZSTD_count_2segments(ip+9, match3+8, iend, matchEnd, prefixStart) + 8;
441  ip++;
442  offset = current+1 - matchIndex3;
443  while (((ip>anchor) & (match3>lowMatchPtr)) && (ip[-1] == match3[-1])) { ip--; match3--; mLength++; } /* catch up */
444  } else {
445  const BYTE* const matchEnd = matchIndex < prefixStartIndex ? dictEnd : iend;
446  const BYTE* const lowMatchPtr = matchIndex < prefixStartIndex ? dictStart : prefixStart;
447  mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, prefixStart) + 4;
448  offset = current - matchIndex;
449  while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
450  }
451  offset_2 = offset_1;
452  offset_1 = offset;
453  ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
454 
455  } else {
456  ip += ((ip-anchor) >> kSearchStrength) + 1;
457  continue;
458  } }
459 
460  /* move to next sequence start */
461  ip += mLength;
462  anchor = ip;
463 
464  if (ip <= ilimit) {
465  /* Complementary insertion */
466  /* done after iLimit test, as candidates could be > iend-8 */
467  { U32 const indexToInsert = current+2;
468  hashLong[ZSTD_hashPtr(base+indexToInsert, hBitsL, 8)] = indexToInsert;
469  hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base);
470  hashSmall[ZSTD_hashPtr(base+indexToInsert, hBitsS, mls)] = indexToInsert;
471  hashSmall[ZSTD_hashPtr(ip-1, hBitsS, mls)] = (U32)(ip-1-base);
472  }
473 
474  /* check immediate repcode */
475  while (ip <= ilimit) {
476  U32 const current2 = (U32)(ip-base);
477  U32 const repIndex2 = current2 - offset_2;
478  const BYTE* repMatch2 = repIndex2 < prefixStartIndex ? dictBase + repIndex2 : base + repIndex2;
479  if ( (((U32)((prefixStartIndex-1) - repIndex2) >= 3) /* intentional overflow : ensure repIndex2 doesn't overlap dict + prefix */
480  & (repIndex2 > dictStartIndex))
481  && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
482  const BYTE* const repEnd2 = repIndex2 < prefixStartIndex ? dictEnd : iend;
483  size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixStart) + 4;
484  U32 const tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */
485  ZSTD_storeSeq(seqStore, 0, anchor, iend, 0, repLength2-MINMATCH);
486  hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2;
487  hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2;
488  ip += repLength2;
489  anchor = ip;
490  continue;
491  }
492  break;
493  } } }
494 
495  /* save reps for next block */
496  rep[0] = offset_1;
497  rep[1] = offset_2;
498 
499  /* Return the last literals size */
500  return (size_t)(iend - anchor);
501 }
502 
503 
505  ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
506  void const* src, size_t srcSize)
507 {
508  U32 const mls = ms->cParams.minMatch;
509  switch(mls)
510  {
511  default: /* includes case 3 */
512  case 4 :
513  return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, src, srcSize, 4);
514  case 5 :
515  return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, src, srcSize, 5);
516  case 6 :
517  return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, src, srcSize, 6);
518  case 7 :
519  return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, src, srcSize, 7);
520  }
521 }
#define kSearchStrength
Definition: match.c:28
HINT_INLINE UNUSED_ATTR void ZSTD_storeSeq(seqStore_t *seqStorePtr, size_t litLength, const BYTE *literals, const BYTE *litLimit, U32 offCode, size_t mlBase)
#define U(x)
Definition: wordpad.c:45
#define assert(x)
Definition: debug.h:53
size_t ZSTD_compressBlock_doubleFast_extDict(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
void mls(int argc, const char *argv[])
Definition: cmds.c:1168
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
MEM_STATIC U64 MEM_read64(const void *memPtr)
Definition: mem.h:247
#define DEBUGLOG(l,...)
Definition: debug.h:106
MEM_STATIC U32 ZSTD_getLowestMatchIndex(const ZSTD_matchState_t *ms, U32 current, unsigned windowLog)
GLuint base
Definition: 3dtext.c:35
int ip[4]
Definition: rtl.c:1176
ZSTD_compressionParameters cParams
MEM_STATIC size_t ZSTD_count(const BYTE *pIn, const BYTE *pMatch, const BYTE *const pInLimit)
MEM_STATIC size_t ZSTD_count_2segments(const BYTE *ip, const BYTE *match, const BYTE *iEnd, const BYTE *mEnd, const BYTE *iStart)
#define ZSTD_REP_MOVE
MEM_STATIC U32 ZSTD_getLowestPrefixIndex(const ZSTD_matchState_t *ms, U32 current, unsigned windowLog)
Definition: dhcpd.h:61
const ZSTD_matchState_t * dictMatchState
GLintptr offset
Definition: glext.h:5920
struct task_struct * current
Definition: linux.c:32
size_t ZSTD_compressBlock_doubleFast_dictMatchState(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
GLuint GLuint end
Definition: gl.h:1545
MEM_STATIC U32 MEM_read32(const void *memPtr)
Definition: mem.h:242
#define HASH_READ_SIZE
GLenum src
Definition: glext.h:6340
FORCE_INLINE_TEMPLATE size_t ZSTD_compressBlock_doubleFast_generic(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize, U32 const mls, ZSTD_dictMode_e const dictMode)
void ZSTD_fillDoubleHashTable(ZSTD_matchState_t *ms, void const *end, ZSTD_dictTableLoadMethod_e dtlm)
unsigned char BYTE
Definition: xxhash.c:193
ZSTD_dictTableLoadMethod_e
#define PREFETCH_L1(ptr)
Definition: compiler.h:124
MEM_STATIC size_t ZSTD_hashPtr(const void *p, U32 hBits, U32 mls)
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define NULL
Definition: types.h:112
#define MINMATCH
size_t ZSTD_compressBlock_doubleFast(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
static size_t ZSTD_compressBlock_doubleFast_extDict_generic(ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize, U32 const mls)
unsigned int U32
Definition: xxhash.c:195
#define ZSTD_REP_NUM
#define FORCE_INLINE_TEMPLATE
Definition: xxhash.c:172