ReactOS 0.4.15-dev-7654-g6bc40d3
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
59size_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
77static U32 ZSTD_ldm_getChecksum(U64 hash, U32 numBitsToDiscard)
78{
79 assert(numBitsToDiscard <= 32);
80 return (hash >> (64 - 32 - numBitsToDiscard)) & 0xFFFFFFFF;
81}
82
89static 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
109static 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
247static 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);
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
419static 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
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
506void 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}
static struct recvd_message * sequence
Definition: SystemMenu.c:63
static int state
Definition: maze.c:121
#define MIN(x, y)
Definition: rdesktop.h:171
#define MAX(x, y)
Definition: rdesktop.h:175
#define NULL
Definition: types.h:112
static cab_ULONG checksum(const cab_UBYTE *data, cab_UWORD bytes, cab_ULONG csum)
Definition: fdi.c:353
#define assert(x)
Definition: debug.h:53
#define DEBUGLOG(l,...)
Definition: debug.h:106
__kernel_size_t size_t
Definition: linux.h:237
#define ERROR(name)
Definition: error_private.h:53
FxCollectionEntry * cur
GLuint GLuint end
Definition: gl.h:1545
GLsizeiptr size
Definition: glext.h:5919
GLenum src
Definition: glext.h:6340
GLenum const GLfloat * params
Definition: glext.h:5645
GLintptr offset
Definition: glext.h:5920
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
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
uint32_t entry
Definition: isohybrid.c:63
struct task_struct * current
Definition: linux.c:32
static struct msg_sequence * sequences[NUM_MSG_SEQUENCES]
Definition: button.c:54
ZSTD_compressionParameters cParams
Definition: _hash_fun.h:40
Definition: dhcpd.h:62
ZSTD_window_t window
ldmEntry_t * hashTable
Definition: ecma_167.h:138
Definition: pdh_main.c:94
unsigned long long U64
Definition: xxhash.c:197
unsigned char BYTE
Definition: xxhash.c:193
unsigned int U32
Definition: xxhash.c:195
@ ZSTD_btlazy2
Definition: zstd.h:256
@ ZSTD_lazy
Definition: zstd.h:254
@ ZSTD_btultra
Definition: zstd.h:258
@ ZSTD_greedy
Definition: zstd.h:253
@ ZSTD_dfast
Definition: zstd.h:252
@ ZSTD_fast
Definition: zstd.h:251
@ ZSTD_lazy2
Definition: zstd.h:255
@ ZSTD_btopt
Definition: zstd.h:257
@ ZSTD_btultra2
Definition: zstd.h:259
ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode)
MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms)
MEM_STATIC U64 ZSTD_rollingHash_compute(void const *buf, size_t size)
MEM_STATIC U64 ZSTD_rollingHash_rotate(U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower)
MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window, void const *srcEnd)
MEM_STATIC size_t ZSTD_count_2segments(const BYTE *ip, const BYTE *match, const BYTE *iEnd, const BYTE *mEnd, const BYTE *iStart)
#define ZSTD_CHUNKSIZE_MAX
MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
MEM_STATIC size_t ZSTD_count(const BYTE *pIn, const BYTE *pMatch, const BYTE *const pInLimit)
size_t(* ZSTD_blockCompressor)(ZSTD_matchState_t *bs, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
MEM_STATIC void ZSTD_window_enforceMaxDist(ZSTD_window_t *window, const void *blockEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
HINT_INLINE UNUSED_ATTR void ZSTD_storeSeq(seqStore_t *seqStorePtr, size_t litLength, const BYTE *literals, const BYTE *litLimit, U32 offCode, size_t mlBase)
@ ZSTD_dtlm_fast
MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t *window, U32 cycleLog, U32 maxDist, void const *src)
#define HASH_READ_SIZE
MEM_STATIC size_t ZSTD_cwksp_alloc_size(size_t size)
Definition: zstd_cwksp.h:180
void ZSTD_fillDoubleHashTable(ZSTD_matchState_t *ms, void const *end, ZSTD_dictTableLoadMethod_e dtlm)
void ZSTD_fillHashTable(ZSTD_matchState_t *ms, const void *const end, ZSTD_dictTableLoadMethod_e dtlm)
Definition: zstd_fast.c:15
#define MINMATCH
#define ZSTD_REP_MOVE
#define ZSTD_isError
Definition: zstd_internal.h:46
#define ZSTD_STATIC_ASSERT(c)
Definition: zstd_internal.h:45
#define ZSTD_REP_NUM
static U32 ZSTD_ldm_getChecksum(U64 hash, U32 numBitsToDiscard)
Definition: zstd_ldm.c:77
void ZSTD_ldm_fillHashTable(ldmState_t *state, const BYTE *ip, const BYTE *iend, ldmParams_t const *params)
Definition: zstd_ldm.c:227
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
static ldmEntry_t * ZSTD_ldm_getBucket(ldmState_t *ldmState, size_t hash, ldmParams_t const ldmParams)
Definition: zstd_ldm.c:101
static void ZSTD_ldm_reduceTable(ldmEntry_t *const table, U32 const size, U32 const reducerValue)
Definition: zstd_ldm.c:419
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
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
void ZSTD_ldm_skipSequences(rawSeqStore_t *rawSeqStore, size_t srcSize, U32 const minMatch)
Definition: zstd_ldm.c:506
void ZSTD_ldm_adjustParameters(ldmParams_t *params, ZSTD_compressionParameters const *cParams)
Definition: zstd_ldm.c:22
#define LDM_BUCKET_SIZE_LOG
Definition: zstd_ldm.c:17
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 size_t ZSTD_ldm_fillFastTables(ZSTD_matchState_t *ms, void const *end)
Definition: zstd_ldm.c:171
#define LDM_HASH_RLOG
Definition: zstd_ldm.c:19
size_t ZSTD_ldm_getMaxNbSeq(ldmParams_t params, size_t maxChunkSize)
Definition: zstd_ldm.c:59
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
static rawSeq maybeSplitSequence(rawSeqStore_t *rawSeqStore, U32 const remaining, U32 const minMatch)
Definition: zstd_ldm.c:541
#define LDM_MIN_MATCH_LENGTH
Definition: zstd_ldm.c:18
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
static size_t ZSTD_ldm_countBackwardsMatch(const BYTE *pIn, const BYTE *pAnchor, const BYTE *pMatch, const BYTE *pBase)
Definition: zstd_ldm.c:151
static void ZSTD_ldm_limitTableUpdate(ZSTD_matchState_t *ms, const BYTE *anchor)
Definition: zstd_ldm.c:247
static U32 ZSTD_ldm_getTag(U64 hash, U32 hbits, U32 numTagBits)
Definition: zstd_ldm.c:89
static U32 ZSTD_ldm_getSmallHash(U64 value, U32 numBits)
Definition: zstd_ldm.c:68
size_t ZSTD_ldm_getTableSize(ldmParams_t params)
Definition: zstd_ldm.c:49