ReactOS  0.4.15-dev-4570-g4f8bbd1
zstd_ldm.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_ldm.h"
12 
13 #include "debug.h"
14 #include "zstd_fast.h" /* ZSTD_fillHashTable() */
15 #include "zstd_double_fast.h" /* ZSTD_fillDoubleHashTable() */
16 
17 #define LDM_BUCKET_SIZE_LOG 3
18 #define LDM_MIN_MATCH_LENGTH 64
19 #define LDM_HASH_RLOG 7
20 #define LDM_HASH_CHAR_OFFSET 10
21 
23  ZSTD_compressionParameters const* cParams)
24 {
25  params->windowLog = cParams->windowLog;
26  ZSTD_STATIC_ASSERT(LDM_BUCKET_SIZE_LOG <= ZSTD_LDM_BUCKETSIZELOG_MAX);
27  DEBUGLOG(4, "ZSTD_ldm_adjustParameters");
28  if (!params->bucketSizeLog) params->bucketSizeLog = LDM_BUCKET_SIZE_LOG;
29  if (!params->minMatchLength) params->minMatchLength = LDM_MIN_MATCH_LENGTH;
30  if (cParams->strategy >= ZSTD_btopt) {
31  /* Get out of the way of the optimal parser */
32  U32 const minMatch = MAX(cParams->targetLength, params->minMatchLength);
33  assert(minMatch >= ZSTD_LDM_MINMATCH_MIN);
34  assert(minMatch <= ZSTD_LDM_MINMATCH_MAX);
35  params->minMatchLength = minMatch;
36  }
37  if (params->hashLog == 0) {
38  params->hashLog = MAX(ZSTD_HASHLOG_MIN, params->windowLog - LDM_HASH_RLOG);
39  assert(params->hashLog <= ZSTD_HASHLOG_MAX);
40  }
41  if (params->hashRateLog == 0) {
42  params->hashRateLog = params->windowLog < params->hashLog
43  ? 0
44  : params->windowLog - params->hashLog;
45  }
46  params->bucketSizeLog = MIN(params->bucketSizeLog, params->hashLog);
47 }
48 
50 {
51  size_t const ldmHSize = ((size_t)1) << params.hashLog;
52  size_t const ldmBucketSizeLog = MIN(params.bucketSizeLog, params.hashLog);
53  size_t const ldmBucketSize = ((size_t)1) << (params.hashLog - ldmBucketSizeLog);
54  size_t const totalSize = ZSTD_cwksp_alloc_size(ldmBucketSize)
55  + ZSTD_cwksp_alloc_size(ldmHSize * sizeof(ldmEntry_t));
56  return params.enableLdm ? totalSize : 0;
57 }
58 
59 size_t ZSTD_ldm_getMaxNbSeq(ldmParams_t params, size_t maxChunkSize)
60 {
61  return params.enableLdm ? (maxChunkSize / params.minMatchLength) : 0;
62 }
63 
69 {
70  assert(numBits <= 32);
71  return numBits == 0 ? 0 : (U32)(value >> (64 - numBits));
72 }
73 
77 static U32 ZSTD_ldm_getChecksum(U64 hash, U32 numBitsToDiscard)
78 {
79  assert(numBitsToDiscard <= 32);
80  return (hash >> (64 - 32 - numBitsToDiscard)) & 0xFFFFFFFF;
81 }
82 
89 static U32 ZSTD_ldm_getTag(U64 hash, U32 hbits, U32 numTagBits)
90 {
91  assert(numTagBits < 32 && hbits <= 32);
92  if (32 - hbits < numTagBits) {
93  return hash & (((U32)1 << numTagBits) - 1);
94  } else {
95  return (hash >> (32 - hbits - numTagBits)) & (((U32)1 << numTagBits) - 1);
96  }
97 }
98 
102  ldmState_t* ldmState, size_t hash, ldmParams_t const ldmParams)
103 {
104  return ldmState->hashTable + (hash << ldmParams.bucketSizeLog);
105 }
106 
109 static void ZSTD_ldm_insertEntry(ldmState_t* ldmState,
110  size_t const hash, const ldmEntry_t entry,
111  ldmParams_t const ldmParams)
112 {
113  BYTE* const bucketOffsets = ldmState->bucketOffsets;
114  *(ZSTD_ldm_getBucket(ldmState, hash, ldmParams) + bucketOffsets[hash]) = entry;
115  bucketOffsets[hash]++;
116  bucketOffsets[hash] &= ((U32)1 << ldmParams.bucketSizeLog) - 1;
117 }
118 
130  U64 const rollingHash,
131  U32 const hBits,
132  U32 const offset,
133  ldmParams_t const ldmParams)
134 {
135  U32 const tag = ZSTD_ldm_getTag(rollingHash, hBits, ldmParams.hashRateLog);
136  U32 const tagMask = ((U32)1 << ldmParams.hashRateLog) - 1;
137  if (tag == tagMask) {
138  U32 const hash = ZSTD_ldm_getSmallHash(rollingHash, hBits);
139  U32 const checksum = ZSTD_ldm_getChecksum(rollingHash, hBits);
141  entry.offset = offset;
142  entry.checksum = checksum;
143  ZSTD_ldm_insertEntry(ldmState, hash, entry, ldmParams);
144  }
145 }
146 
152  const BYTE* pIn, const BYTE* pAnchor,
153  const BYTE* pMatch, const BYTE* pBase)
154 {
155  size_t matchLength = 0;
156  while (pIn > pAnchor && pMatch > pBase && pIn[-1] == pMatch[-1]) {
157  pIn--;
158  pMatch--;
159  matchLength++;
160  }
161  return matchLength;
162 }
163 
172  void const* end)
173 {
174  const BYTE* const iend = (const BYTE*)end;
175 
176  switch(ms->cParams.strategy)
177  {
178  case ZSTD_fast:
180  break;
181 
182  case ZSTD_dfast:
184  break;
185 
186  case ZSTD_greedy:
187  case ZSTD_lazy:
188  case ZSTD_lazy2:
189  case ZSTD_btlazy2:
190  case ZSTD_btopt:
191  case ZSTD_btultra:
192  case ZSTD_btultra2:
193  break;
194  default:
195  assert(0); /* not possible : not a valid strategy id */
196  }
197 
198  return 0;
199 }
200 
208  U64 lastHash, const BYTE* lastHashed,
209  const BYTE* iend, const BYTE* base,
210  U32 hBits, ldmParams_t const ldmParams)
211 {
212  U64 rollingHash = lastHash;
213  const BYTE* cur = lastHashed + 1;
214 
215  while (cur < iend) {
216  rollingHash = ZSTD_rollingHash_rotate(rollingHash, cur[-1],
217  cur[ldmParams.minMatchLength-1],
218  state->hashPower);
220  rollingHash, hBits,
221  (U32)(cur - base), ldmParams);
222  ++cur;
223  }
224  return rollingHash;
225 }
226 
228  ldmState_t* state, const BYTE* ip,
229  const BYTE* iend, ldmParams_t const* params)
230 {
231  DEBUGLOG(5, "ZSTD_ldm_fillHashTable");
232  if ((size_t)(iend - ip) >= params->minMatchLength) {
233  U64 startingHash = ZSTD_rollingHash_compute(ip, params->minMatchLength);
235  state, startingHash, ip, iend - params->minMatchLength, state->window.base,
236  params->hashLog - params->bucketSizeLog,
237  *params);
238  }
239 }
240 
241 
247 static void ZSTD_ldm_limitTableUpdate(ZSTD_matchState_t* ms, const BYTE* anchor)
248 {
249  U32 const current = (U32)(anchor - ms->window.base);
250  if (current > ms->nextToUpdate + 1024) {
251  ms->nextToUpdate =
252  current - MIN(512, current - ms->nextToUpdate - 1024);
253  }
254 }
255 
257  ldmState_t* ldmState, rawSeqStore_t* rawSeqStore,
258  ldmParams_t const* params, void const* src, size_t srcSize)
259 {
260  /* LDM parameters */
261  int const extDict = ZSTD_window_hasExtDict(ldmState->window);
262  U32 const minMatchLength = params->minMatchLength;
263  U64 const hashPower = ldmState->hashPower;
264  U32 const hBits = params->hashLog - params->bucketSizeLog;
265  U32 const ldmBucketSize = 1U << params->bucketSizeLog;
266  U32 const hashRateLog = params->hashRateLog;
267  U32 const ldmTagMask = (1U << params->hashRateLog) - 1;
268  /* Prefix and extDict parameters */
269  U32 const dictLimit = ldmState->window.dictLimit;
270  U32 const lowestIndex = extDict ? ldmState->window.lowLimit : dictLimit;
271  BYTE const* const base = ldmState->window.base;
272  BYTE const* const dictBase = extDict ? ldmState->window.dictBase : NULL;
273  BYTE const* const dictStart = extDict ? dictBase + lowestIndex : NULL;
274  BYTE const* const dictEnd = extDict ? dictBase + dictLimit : NULL;
275  BYTE const* const lowPrefixPtr = base + dictLimit;
276  /* Input bounds */
277  BYTE const* const istart = (BYTE const*)src;
278  BYTE const* const iend = istart + srcSize;
279  BYTE const* const ilimit = iend - MAX(minMatchLength, HASH_READ_SIZE);
280  /* Input positions */
281  BYTE const* anchor = istart;
282  BYTE const* ip = istart;
283  /* Rolling hash */
284  BYTE const* lastHashed = NULL;
285  U64 rollingHash = 0;
286 
287  while (ip <= ilimit) {
288  size_t mLength;
289  U32 const current = (U32)(ip - base);
290  size_t forwardMatchLength = 0, backwardMatchLength = 0;
291  ldmEntry_t* bestEntry = NULL;
292  if (ip != istart) {
293  rollingHash = ZSTD_rollingHash_rotate(rollingHash, lastHashed[0],
294  lastHashed[minMatchLength],
295  hashPower);
296  } else {
297  rollingHash = ZSTD_rollingHash_compute(ip, minMatchLength);
298  }
299  lastHashed = ip;
300 
301  /* Do not insert and do not look for a match */
302  if (ZSTD_ldm_getTag(rollingHash, hBits, hashRateLog) != ldmTagMask) {
303  ip++;
304  continue;
305  }
306 
307  /* Get the best entry and compute the match lengths */
308  {
309  ldmEntry_t* const bucket =
310  ZSTD_ldm_getBucket(ldmState,
311  ZSTD_ldm_getSmallHash(rollingHash, hBits),
312  *params);
313  ldmEntry_t* cur;
314  size_t bestMatchLength = 0;
315  U32 const checksum = ZSTD_ldm_getChecksum(rollingHash, hBits);
316 
317  for (cur = bucket; cur < bucket + ldmBucketSize; ++cur) {
318  size_t curForwardMatchLength, curBackwardMatchLength,
319  curTotalMatchLength;
320  if (cur->checksum != checksum || cur->offset <= lowestIndex) {
321  continue;
322  }
323  if (extDict) {
324  BYTE const* const curMatchBase =
325  cur->offset < dictLimit ? dictBase : base;
326  BYTE const* const pMatch = curMatchBase + cur->offset;
327  BYTE const* const matchEnd =
328  cur->offset < dictLimit ? dictEnd : iend;
329  BYTE const* const lowMatchPtr =
330  cur->offset < dictLimit ? dictStart : lowPrefixPtr;
331 
332  curForwardMatchLength = ZSTD_count_2segments(
333  ip, pMatch, iend,
334  matchEnd, lowPrefixPtr);
335  if (curForwardMatchLength < minMatchLength) {
336  continue;
337  }
338  curBackwardMatchLength =
339  ZSTD_ldm_countBackwardsMatch(ip, anchor, pMatch,
340  lowMatchPtr);
341  curTotalMatchLength = curForwardMatchLength +
342  curBackwardMatchLength;
343  } else { /* !extDict */
344  BYTE const* const pMatch = base + cur->offset;
345  curForwardMatchLength = ZSTD_count(ip, pMatch, iend);
346  if (curForwardMatchLength < minMatchLength) {
347  continue;
348  }
349  curBackwardMatchLength =
350  ZSTD_ldm_countBackwardsMatch(ip, anchor, pMatch,
351  lowPrefixPtr);
352  curTotalMatchLength = curForwardMatchLength +
353  curBackwardMatchLength;
354  }
355 
356  if (curTotalMatchLength > bestMatchLength) {
357  bestMatchLength = curTotalMatchLength;
358  forwardMatchLength = curForwardMatchLength;
359  backwardMatchLength = curBackwardMatchLength;
360  bestEntry = cur;
361  }
362  }
363  }
364 
365  /* No match found -- continue searching */
366  if (bestEntry == NULL) {
367  ZSTD_ldm_makeEntryAndInsertByTag(ldmState, rollingHash,
368  hBits, current,
369  *params);
370  ip++;
371  continue;
372  }
373 
374  /* Match found */
375  mLength = forwardMatchLength + backwardMatchLength;
376  ip -= backwardMatchLength;
377 
378  {
379  /* Store the sequence:
380  * ip = current - backwardMatchLength
381  * The match is at (bestEntry->offset - backwardMatchLength)
382  */
383  U32 const matchIndex = bestEntry->offset;
384  U32 const offset = current - matchIndex;
385  rawSeq* const seq = rawSeqStore->seq + rawSeqStore->size;
386 
387  /* Out of sequence storage */
388  if (rawSeqStore->size == rawSeqStore->capacity)
389  return ERROR(dstSize_tooSmall);
390  seq->litLength = (U32)(ip - anchor);
391  seq->matchLength = (U32)mLength;
392  seq->offset = offset;
393  rawSeqStore->size++;
394  }
395 
396  /* Insert the current entry into the hash table */
397  ZSTD_ldm_makeEntryAndInsertByTag(ldmState, rollingHash, hBits,
398  (U32)(lastHashed - base),
399  *params);
400 
401  assert(ip + backwardMatchLength == lastHashed);
402 
403  /* Fill the hash table from lastHashed+1 to ip+mLength*/
404  /* Heuristic: don't need to fill the entire table at end of block */
405  if (ip + mLength <= ilimit) {
406  rollingHash = ZSTD_ldm_fillLdmHashTable(
407  ldmState, rollingHash, lastHashed,
408  ip + mLength, base, hBits, *params);
409  lastHashed = ip + mLength - 1;
410  }
411  ip += mLength;
412  anchor = ip;
413  }
414  return iend - anchor;
415 }
416 
419 static void ZSTD_ldm_reduceTable(ldmEntry_t* const table, U32 const size,
420  U32 const reducerValue)
421 {
422  U32 u;
423  for (u = 0; u < size; u++) {
424  if (table[u].offset < reducerValue) table[u].offset = 0;
425  else table[u].offset -= reducerValue;
426  }
427 }
428 
430  ldmState_t* ldmState, rawSeqStore_t* sequences,
431  ldmParams_t const* params, void const* src, size_t srcSize)
432 {
433  U32 const maxDist = 1U << params->windowLog;
434  BYTE const* const istart = (BYTE const*)src;
435  BYTE const* const iend = istart + srcSize;
436  size_t const kMaxChunkSize = 1 << 20;
437  size_t const nbChunks = (srcSize / kMaxChunkSize) + ((srcSize % kMaxChunkSize) != 0);
438  size_t chunk;
439  size_t leftoverSize = 0;
440 
441  assert(ZSTD_CHUNKSIZE_MAX >= kMaxChunkSize);
442  /* Check that ZSTD_window_update() has been called for this chunk prior
443  * to passing it to this function.
444  */
445  assert(ldmState->window.nextSrc >= (BYTE const*)src + srcSize);
446  /* The input could be very large (in zstdmt), so it must be broken up into
447  * chunks to enforce the maximum distance and handle overflow correction.
448  */
449  assert(sequences->pos <= sequences->size);
450  assert(sequences->size <= sequences->capacity);
451  for (chunk = 0; chunk < nbChunks && sequences->size < sequences->capacity; ++chunk) {
452  BYTE const* const chunkStart = istart + chunk * kMaxChunkSize;
453  size_t const remaining = (size_t)(iend - chunkStart);
454  BYTE const *const chunkEnd =
455  (remaining < kMaxChunkSize) ? iend : chunkStart + kMaxChunkSize;
456  size_t const chunkSize = chunkEnd - chunkStart;
457  size_t newLeftoverSize;
458  size_t const prevSize = sequences->size;
459 
460  assert(chunkStart < iend);
461  /* 1. Perform overflow correction if necessary. */
462  if (ZSTD_window_needOverflowCorrection(ldmState->window, chunkEnd)) {
463  U32 const ldmHSize = 1U << params->hashLog;
464  U32 const correction = ZSTD_window_correctOverflow(
465  &ldmState->window, /* cycleLog */ 0, maxDist, chunkStart);
466  ZSTD_ldm_reduceTable(ldmState->hashTable, ldmHSize, correction);
467  /* invalidate dictionaries on overflow correction */
468  ldmState->loadedDictEnd = 0;
469  }
470  /* 2. We enforce the maximum offset allowed.
471  *
472  * kMaxChunkSize should be small enough that we don't lose too much of
473  * the window through early invalidation.
474  * TODO: * Test the chunk size.
475  * * Try invalidation after the sequence generation and test the
476  * the offset against maxDist directly.
477  *
478  * NOTE: Because of dictionaries + sequence splitting we MUST make sure
479  * that any offset used is valid at the END of the sequence, since it may
480  * be split into two sequences. This condition holds when using
481  * ZSTD_window_enforceMaxDist(), but if we move to checking offsets
482  * against maxDist directly, we'll have to carefully handle that case.
483  */
484  ZSTD_window_enforceMaxDist(&ldmState->window, chunkEnd, maxDist, &ldmState->loadedDictEnd, NULL);
485  /* 3. Generate the sequences for the chunk, and get newLeftoverSize. */
486  newLeftoverSize = ZSTD_ldm_generateSequences_internal(
487  ldmState, sequences, params, chunkStart, chunkSize);
488  if (ZSTD_isError(newLeftoverSize))
489  return newLeftoverSize;
490  /* 4. We add the leftover literals from previous iterations to the first
491  * newly generated sequence, or add the `newLeftoverSize` if none are
492  * generated.
493  */
494  /* Prepend the leftover literals from the last call */
495  if (prevSize < sequences->size) {
496  sequences->seq[prevSize].litLength += (U32)leftoverSize;
497  leftoverSize = newLeftoverSize;
498  } else {
499  assert(newLeftoverSize == chunkSize);
500  leftoverSize += chunkSize;
501  }
502  }
503  return 0;
504 }
505 
506 void ZSTD_ldm_skipSequences(rawSeqStore_t* rawSeqStore, size_t srcSize, U32 const minMatch) {
507  while (srcSize > 0 && rawSeqStore->pos < rawSeqStore->size) {
508  rawSeq* seq = rawSeqStore->seq + rawSeqStore->pos;
509  if (srcSize <= seq->litLength) {
510  /* Skip past srcSize literals */
511  seq->litLength -= (U32)srcSize;
512  return;
513  }
514  srcSize -= seq->litLength;
515  seq->litLength = 0;
516  if (srcSize < seq->matchLength) {
517  /* Skip past the first srcSize of the match */
518  seq->matchLength -= (U32)srcSize;
519  if (seq->matchLength < minMatch) {
520  /* The match is too short, omit it */
521  if (rawSeqStore->pos + 1 < rawSeqStore->size) {
522  seq[1].litLength += seq[0].matchLength;
523  }
524  rawSeqStore->pos++;
525  }
526  return;
527  }
528  srcSize -= seq->matchLength;
529  seq->matchLength = 0;
530  rawSeqStore->pos++;
531  }
532 }
533 
542  U32 const remaining, U32 const minMatch)
543 {
544  rawSeq sequence = rawSeqStore->seq[rawSeqStore->pos];
545  assert(sequence.offset > 0);
546  /* Likely: No partial sequence */
547  if (remaining >= sequence.litLength + sequence.matchLength) {
548  rawSeqStore->pos++;
549  return sequence;
550  }
551  /* Cut the sequence short (offset == 0 ==> rest is literals). */
552  if (remaining <= sequence.litLength) {
553  sequence.offset = 0;
554  } else if (remaining < sequence.litLength + sequence.matchLength) {
555  sequence.matchLength = remaining - sequence.litLength;
556  if (sequence.matchLength < minMatch) {
557  sequence.offset = 0;
558  }
559  }
560  /* Skip past `remaining` bytes for the future sequences. */
561  ZSTD_ldm_skipSequences(rawSeqStore, remaining, minMatch);
562  return sequence;
563 }
564 
566  ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
567  void const* src, size_t srcSize)
568 {
569  const ZSTD_compressionParameters* const cParams = &ms->cParams;
570  unsigned const minMatch = cParams->minMatch;
571  ZSTD_blockCompressor const blockCompressor =
573  /* Input bounds */
574  BYTE const* const istart = (BYTE const*)src;
575  BYTE const* const iend = istart + srcSize;
576  /* Input positions */
577  BYTE const* ip = istart;
578 
579  DEBUGLOG(5, "ZSTD_ldm_blockCompress: srcSize=%zu", srcSize);
580  assert(rawSeqStore->pos <= rawSeqStore->size);
581  assert(rawSeqStore->size <= rawSeqStore->capacity);
582  /* Loop through each sequence and apply the block compressor to the lits */
583  while (rawSeqStore->pos < rawSeqStore->size && ip < iend) {
584  /* maybeSplitSequence updates rawSeqStore->pos */
585  rawSeq const sequence = maybeSplitSequence(rawSeqStore,
586  (U32)(iend - ip), minMatch);
587  int i;
588  /* End signal */
589  if (sequence.offset == 0)
590  break;
591 
592  assert(ip + sequence.litLength + sequence.matchLength <= iend);
593 
594  /* Fill tables for block compressor */
597  /* Run the block compressor */
598  DEBUGLOG(5, "pos %u : calling block compressor on segment of size %u", (unsigned)(ip-istart), sequence.litLength);
599  {
600  size_t const newLitLength =
601  blockCompressor(ms, seqStore, rep, ip, sequence.litLength);
602  ip += sequence.litLength;
603  /* Update the repcodes */
604  for (i = ZSTD_REP_NUM - 1; i > 0; i--)
605  rep[i] = rep[i-1];
606  rep[0] = sequence.offset;
607  /* Store the sequence */
608  ZSTD_storeSeq(seqStore, newLitLength, ip - newLitLength, iend,
609  sequence.offset + ZSTD_REP_MOVE,
610  sequence.matchLength - MINMATCH);
611  ip += sequence.matchLength;
612  }
613  }
614  /* Fill the tables for the block compressor */
617  /* Compress the last literals */
618  return blockCompressor(ms, seqStore, rep, ip, iend - ip);
619 }
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 * u
Definition: glfuncs.h:240
Definition: pdh_main.c:93
void ZSTD_ldm_adjustParameters(ldmParams_t *params, ZSTD_compressionParameters const *cParams)
Definition: zstd_ldm.c:22
#define ERROR(name)
Definition: error_private.h:53
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
MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
#define assert(x)
Definition: debug.h:53
Definition: ecma_167.h:138
ldmEntry_t * hashTable
static ldmEntry_t * ZSTD_ldm_getBucket(ldmState_t *ldmState, size_t hash, ldmParams_t const ldmParams)
Definition: zstd_ldm.c:101
MEM_STATIC size_t ZSTD_cwksp_alloc_size(size_t size)
Definition: zstd_cwksp.h:180
MEM_STATIC U64 ZSTD_rollingHash_compute(void const *buf, size_t size)
size_t ZSTD_ldm_blockCompress(rawSeqStore_t *rawSeqStore, ZSTD_matchState_t *ms, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
Definition: zstd_ldm.c:565
static void ZSTD_ldm_reduceTable(ldmEntry_t *const table, U32 const size, U32 const reducerValue)
Definition: zstd_ldm.c:419
#define LDM_MIN_MATCH_LENGTH
Definition: zstd_ldm.c:18
T MIN(T a, T b)
Definition: polytest.cpp:79
#define ZSTD_STATIC_ASSERT(c)
Definition: zstd_internal.h:45
#define DEBUGLOG(l,...)
Definition: debug.h:106
#define ZSTD_isError
Definition: zstd_internal.h:46
size_t ZSTD_ldm_getMaxNbSeq(ldmParams_t params, size_t maxChunkSize)
Definition: zstd_ldm.c:59
GLenum const GLfloat * params
Definition: glext.h:5645
int hash
Definition: main.c:58
MEM_STATIC void ZSTD_window_enforceMaxDist(ZSTD_window_t *window, const void *blockEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
GLuint base
Definition: 3dtext.c:35
int ip[4]
Definition: rtl.c:1176
ZSTD_compressionParameters cParams
ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode)
static U32 ZSTD_ldm_getChecksum(U64 hash, U32 numBitsToDiscard)
Definition: zstd_ldm.c:77
static size_t ZSTD_ldm_generateSequences_internal(ldmState_t *ldmState, rawSeqStore_t *rawSeqStore, ldmParams_t const *params, void const *src, size_t srcSize)
Definition: zstd_ldm.c:256
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
__kernel_size_t size_t
Definition: linux.h:237
void ZSTD_ldm_fillHashTable(ldmState_t *state, const BYTE *ip, const BYTE *iend, ldmParams_t const *params)
Definition: zstd_ldm.c:227
GLsizeiptr size
Definition: glext.h:5919
static void ZSTD_ldm_makeEntryAndInsertByTag(ldmState_t *ldmState, U64 const rollingHash, U32 const hBits, U32 const offset, ldmParams_t const ldmParams)
Definition: zstd_ldm.c:129
Definition: dhcpd.h:61
GLintptr offset
Definition: glext.h:5920
static U32 ZSTD_ldm_getTag(U64 hash, U32 hbits, U32 numTagBits)
Definition: zstd_ldm.c:89
struct task_struct * current
Definition: linux.c:32
size_t ZSTD_ldm_getTableSize(ldmParams_t params)
Definition: zstd_ldm.c:49
static void ZSTD_ldm_insertEntry(ldmState_t *ldmState, size_t const hash, const ldmEntry_t entry, ldmParams_t const ldmParams)
Definition: zstd_ldm.c:109
GLuint GLuint end
Definition: gl.h:1545
MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window, void const *srcEnd)
size_t(* ZSTD_blockCompressor)(ZSTD_matchState_t *bs, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
MEM_STATIC U64 ZSTD_rollingHash_rotate(U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower)
#define HASH_READ_SIZE
static struct message * sequence
Definition: subclass.c:46
static int state
Definition: maze.c:121
uint32_t entry
Definition: isohybrid.c:63
GLenum src
Definition: glext.h:6340
static cab_ULONG checksum(const cab_UBYTE *data, cab_UWORD bytes, cab_ULONG csum)
Definition: fdi.c:353
static rawSeq maybeSplitSequence(rawSeqStore_t *rawSeqStore, U32 const remaining, U32 const minMatch)
Definition: zstd_ldm.c:541
void ZSTD_fillDoubleHashTable(ZSTD_matchState_t *ms, void const *end, ZSTD_dictTableLoadMethod_e dtlm)
unsigned char BYTE
Definition: xxhash.c:193
static struct msg_sequence * sequences[NUM_MSG_SEQUENCES]
Definition: button.c:54
#define LDM_BUCKET_SIZE_LOG
Definition: zstd_ldm.c:17
FxCollectionEntry * cur
MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t *window, U32 cycleLog, U32 maxDist, void const *src)
T MAX(T a, T b)
Definition: polytest.cpp:85
static void ZSTD_ldm_limitTableUpdate(ZSTD_matchState_t *ms, const BYTE *anchor)
Definition: zstd_ldm.c:247
static size_t ZSTD_ldm_fillFastTables(ZSTD_matchState_t *ms, void const *end)
Definition: zstd_ldm.c:171
void ZSTD_fillHashTable(ZSTD_matchState_t *ms, const void *const end, ZSTD_dictTableLoadMethod_e dtlm)
Definition: zstd_fast.c:15
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
unsigned long long U64
Definition: xxhash.c:197
MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms)
static U64 ZSTD_ldm_fillLdmHashTable(ldmState_t *state, U64 lastHash, const BYTE *lastHashed, const BYTE *iend, const BYTE *base, U32 hBits, ldmParams_t const ldmParams)
Definition: zstd_ldm.c:207
#define ZSTD_CHUNKSIZE_MAX
#define NULL
Definition: types.h:112
size_t ZSTD_ldm_generateSequences(ldmState_t *ldmState, rawSeqStore_t *sequences, ldmParams_t const *params, void const *src, size_t srcSize)
Definition: zstd_ldm.c:429
#define MINMATCH
ZSTD_window_t window
static U32 ZSTD_ldm_getSmallHash(U64 value, U32 numBits)
Definition: zstd_ldm.c:68
void ZSTD_ldm_skipSequences(rawSeqStore_t *rawSeqStore, size_t srcSize, U32 const minMatch)
Definition: zstd_ldm.c:506
#define LDM_HASH_RLOG
Definition: zstd_ldm.c:19
Definition: _hash_fun.h:40
unsigned int U32
Definition: xxhash.c:195
#define ZSTD_REP_NUM
static size_t ZSTD_ldm_countBackwardsMatch(const BYTE *pIn, const BYTE *pAnchor, const BYTE *pMatch, const BYTE *pBase)
Definition: zstd_ldm.c:151