ReactOS  0.4.15-dev-985-gd905dd5
zstd_ldm.c File Reference
#include "zstd_ldm.h"
#include "debug.h"
#include "zstd_fast.h"
#include "zstd_double_fast.h"
Include dependency graph for zstd_ldm.c:

Go to the source code of this file.

Macros

#define LDM_BUCKET_SIZE_LOG   3
 
#define LDM_MIN_MATCH_LENGTH   64
 
#define LDM_HASH_RLOG   7
 
#define LDM_HASH_CHAR_OFFSET   10
 

Functions

void ZSTD_ldm_adjustParameters (ldmParams_t *params, ZSTD_compressionParameters const *cParams)
 
size_t ZSTD_ldm_getTableSize (ldmParams_t params)
 
size_t ZSTD_ldm_getMaxNbSeq (ldmParams_t params, size_t maxChunkSize)
 
static U32 ZSTD_ldm_getSmallHash (U64 value, U32 numBits)
 
static U32 ZSTD_ldm_getChecksum (U64 hash, U32 numBitsToDiscard)
 
static U32 ZSTD_ldm_getTag (U64 hash, U32 hbits, U32 numTagBits)
 
static ldmEntry_tZSTD_ldm_getBucket (ldmState_t *ldmState, size_t hash, ldmParams_t const ldmParams)
 
static void ZSTD_ldm_insertEntry (ldmState_t *ldmState, size_t const hash, const ldmEntry_t entry, ldmParams_t const ldmParams)
 
static void ZSTD_ldm_makeEntryAndInsertByTag (ldmState_t *ldmState, U64 const rollingHash, U32 const hBits, U32 const offset, ldmParams_t const ldmParams)
 
static U64 ZSTD_ldm_getRollingHash (const BYTE *buf, U32 len)
 
static U64 ZSTD_ldm_ipow (U64 base, U64 exp)
 
U64 ZSTD_ldm_getHashPower (U32 minMatchLength)
 
static U64 ZSTD_ldm_updateHash (U64 hash, BYTE toRemove, BYTE toAdd, U64 hashPower)
 
static size_t ZSTD_ldm_countBackwardsMatch (const BYTE *pIn, const BYTE *pAnchor, const BYTE *pMatch, const BYTE *pBase)
 
static size_t ZSTD_ldm_fillFastTables (ZSTD_matchState_t *ms, void const *end)
 
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)
 
static void ZSTD_ldm_limitTableUpdate (ZSTD_matchState_t *ms, const BYTE *anchor)
 
static size_t ZSTD_ldm_generateSequences_internal (ldmState_t *ldmState, rawSeqStore_t *rawSeqStore, ldmParams_t const *params, void const *src, size_t srcSize)
 
static void ZSTD_ldm_reduceTable (ldmEntry_t *const table, U32 const size, U32 const reducerValue)
 
size_t ZSTD_ldm_generateSequences (ldmState_t *ldmState, rawSeqStore_t *sequences, ldmParams_t const *params, void const *src, size_t srcSize)
 
void ZSTD_ldm_skipSequences (rawSeqStore_t *rawSeqStore, size_t srcSize, U32 const minMatch)
 
static rawSeq maybeSplitSequence (rawSeqStore_t *rawSeqStore, U32 const remaining, U32 const minMatch)
 
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)
 

Macro Definition Documentation

◆ LDM_BUCKET_SIZE_LOG

#define LDM_BUCKET_SIZE_LOG   3

Definition at line 16 of file zstd_ldm.c.

◆ LDM_HASH_CHAR_OFFSET

#define LDM_HASH_CHAR_OFFSET   10

Definition at line 19 of file zstd_ldm.c.

◆ LDM_HASH_RLOG

#define LDM_HASH_RLOG   7

Definition at line 18 of file zstd_ldm.c.

◆ LDM_MIN_MATCH_LENGTH

#define LDM_MIN_MATCH_LENGTH   64

Definition at line 17 of file zstd_ldm.c.

Function Documentation

◆ maybeSplitSequence()

static rawSeq maybeSplitSequence ( rawSeqStore_t rawSeqStore,
U32 const  remaining,
U32 const  minMatch 
)
static

If the sequence length is longer than remaining then the sequence is split between this block and the next.

Returns the current sequence to handle, or if the rest of the block should be literals, it returns a sequence with offset == 0.

Definition at line 567 of file zstd_ldm.c.

569 {
570  rawSeq sequence = rawSeqStore->seq[rawSeqStore->pos];
571  assert(sequence.offset > 0);
572  /* Likely: No partial sequence */
573  if (remaining >= sequence.litLength + sequence.matchLength) {
574  rawSeqStore->pos++;
575  return sequence;
576  }
577  /* Cut the sequence short (offset == 0 ==> rest is literals). */
578  if (remaining <= sequence.litLength) {
579  sequence.offset = 0;
580  } else if (remaining < sequence.litLength + sequence.matchLength) {
581  sequence.matchLength = remaining - sequence.litLength;
582  if (sequence.matchLength < minMatch) {
583  sequence.offset = 0;
584  }
585  }
586  /* Skip past `remaining` bytes for the future sequences. */
587  ZSTD_ldm_skipSequences(rawSeqStore, remaining, minMatch);
588  return sequence;
589 }
#define assert(x)
Definition: debug.h:53
static struct message * sequence
Definition: subclass.c:46
void ZSTD_ldm_skipSequences(rawSeqStore_t *rawSeqStore, size_t srcSize, U32 const minMatch)
Definition: zstd_ldm.c:532

Referenced by ZSTD_ldm_blockCompress().

◆ ZSTD_ldm_adjustParameters()

void ZSTD_ldm_adjustParameters ( ldmParams_t params,
ZSTD_compressionParameters const cParams 
)

ZSTD_ldm_adjustParameters() : If the params->hashEveryLog is not set, set it to its default value based on windowLog and params->hashLog.

Ensures that params->bucketSizeLog is <= params->hashLog (setting it to params->hashLog if it is not).

Ensures that the minMatchLength >= targetLength during optimal parsing.

Definition at line 21 of file zstd_ldm.c.

23 {
24  params->windowLog = cParams->windowLog;
25  ZSTD_STATIC_ASSERT(LDM_BUCKET_SIZE_LOG <= ZSTD_LDM_BUCKETSIZELOG_MAX);
26  DEBUGLOG(4, "ZSTD_ldm_adjustParameters");
27  if (!params->bucketSizeLog) params->bucketSizeLog = LDM_BUCKET_SIZE_LOG;
28  if (!params->minMatchLength) params->minMatchLength = LDM_MIN_MATCH_LENGTH;
29  if (cParams->strategy >= ZSTD_btopt) {
30  /* Get out of the way of the optimal parser */
31  U32 const minMatch = MAX(cParams->targetLength, params->minMatchLength);
32  assert(minMatch >= ZSTD_LDM_MINMATCH_MIN);
33  assert(minMatch <= ZSTD_LDM_MINMATCH_MAX);
34  params->minMatchLength = minMatch;
35  }
36  if (params->hashLog == 0) {
37  params->hashLog = MAX(ZSTD_HASHLOG_MIN, params->windowLog - LDM_HASH_RLOG);
38  assert(params->hashLog <= ZSTD_HASHLOG_MAX);
39  }
40  if (params->hashEveryLog == 0) {
41  params->hashEveryLog = params->windowLog < params->hashLog
42  ? 0
43  : params->windowLog - params->hashLog;
44  }
45  params->bucketSizeLog = MIN(params->bucketSizeLog, params->hashLog);
46 }
#define assert(x)
Definition: debug.h:53
#define LDM_MIN_MATCH_LENGTH
Definition: zstd_ldm.c:17
T MIN(T a, T b)
Definition: polytest.cpp:79
#define ZSTD_STATIC_ASSERT(c)
Definition: zstd_internal.h:43
#define DEBUGLOG(l,...)
Definition: debug.h:115
GLenum const GLfloat * params
Definition: glext.h:5645
#define LDM_BUCKET_SIZE_LOG
Definition: zstd_ldm.c:16
T MAX(T a, T b)
Definition: polytest.cpp:85
#define LDM_HASH_RLOG
Definition: zstd_ldm.c:18
unsigned int U32
Definition: xxhash.c:195

Referenced by ZSTD_resetCCtx_internal().

◆ ZSTD_ldm_blockCompress()

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 
)

ZSTD_ldm_blockCompress():

Compresses a block using the predefined sequences, along with a secondary block compressor. The literals section of every sequence is passed to the secondary block compressor, and those sequences are interspersed with the predefined sequences. Returns the length of the last literals. Updates rawSeqStore.pos to indicate how many sequences have been consumed. rawSeqStore.seq may also be updated to split the last sequence between two blocks.

Returns
The length of the last literals.

NOTE: The source must be at most the maximum block size, but the predefined sequences can be any size, and may be longer than the block. In the case that they are longer than the block, the last sequences may need to be split into two. We handle that case correctly, and update rawSeqStore appropriately. NOTE: This function does not return any errors.

Definition at line 591 of file zstd_ldm.c.

594 {
595  const ZSTD_compressionParameters* const cParams = &ms->cParams;
596  unsigned const minMatch = cParams->searchLength;
597  ZSTD_blockCompressor const blockCompressor =
599  /* Input bounds */
600  BYTE const* const istart = (BYTE const*)src;
601  BYTE const* const iend = istart + srcSize;
602  /* Input positions */
603  BYTE const* ip = istart;
604 
605  DEBUGLOG(5, "ZSTD_ldm_blockCompress: srcSize=%zu", srcSize);
606  assert(rawSeqStore->pos <= rawSeqStore->size);
607  assert(rawSeqStore->size <= rawSeqStore->capacity);
608  /* Loop through each sequence and apply the block compressor to the lits */
609  while (rawSeqStore->pos < rawSeqStore->size && ip < iend) {
610  /* maybeSplitSequence updates rawSeqStore->pos */
611  rawSeq const sequence = maybeSplitSequence(rawSeqStore,
612  (U32)(iend - ip), minMatch);
613  int i;
614  /* End signal */
615  if (sequence.offset == 0)
616  break;
617 
618  assert(sequence.offset <= (1U << cParams->windowLog));
619  assert(ip + sequence.litLength + sequence.matchLength <= iend);
620 
621  /* Fill tables for block compressor */
624  /* Run the block compressor */
625  DEBUGLOG(5, "calling block compressor on segment of size %u", sequence.litLength);
626  {
627  size_t const newLitLength =
628  blockCompressor(ms, seqStore, rep, ip, sequence.litLength);
629  ip += sequence.litLength;
630  /* Update the repcodes */
631  for (i = ZSTD_REP_NUM - 1; i > 0; i--)
632  rep[i] = rep[i-1];
633  rep[0] = sequence.offset;
634  /* Store the sequence */
635  ZSTD_storeSeq(seqStore, newLitLength, ip - newLitLength,
636  sequence.offset + ZSTD_REP_MOVE,
637  sequence.matchLength - MINMATCH);
638  ip += sequence.matchLength;
639  }
640  }
641  /* Fill the tables for the block compressor */
644  /* Compress the last literals */
645  return blockCompressor(ms, seqStore, rep, ip, iend - ip);
646 }
#define U(x)
Definition: wordpad.c:45
#define assert(x)
Definition: debug.h:53
#define DEBUGLOG(l,...)
Definition: debug.h:115
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
ZSTD_compressionParameters cParams
ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode)
#define ZSTD_REP_MOVE
Definition: zstd_internal.h:63
Definition: dhcpd.h:61
MEM_STATIC void ZSTD_storeSeq(seqStore_t *seqStorePtr, size_t litLength, const void *literals, U32 offsetCode, size_t mlBase)
size_t(* ZSTD_blockCompressor)(ZSTD_matchState_t *bs, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
static struct message * sequence
Definition: subclass.c:46
GLenum src
Definition: glext.h:6340
static rawSeq maybeSplitSequence(rawSeqStore_t *rawSeqStore, U32 const remaining, U32 const minMatch)
Definition: zstd_ldm.c:567
unsigned char BYTE
Definition: xxhash.c:193
static void ZSTD_ldm_limitTableUpdate(ZSTD_matchState_t *ms, const BYTE *anchor)
Definition: zstd_ldm.c:281
static size_t ZSTD_ldm_fillFastTables(ZSTD_matchState_t *ms, void const *end)
Definition: zstd_ldm.c:220
MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms)
#define MINMATCH
Definition: zstd_internal.h:96
unsigned int U32
Definition: xxhash.c:195
#define ZSTD_REP_NUM
Definition: zstd_internal.h:62

Referenced by ZSTD_compressBlock_internal().

◆ ZSTD_ldm_countBackwardsMatch()

static size_t ZSTD_ldm_countBackwardsMatch ( const BYTE pIn,
const BYTE pAnchor,
const BYTE pMatch,
const BYTE pBase 
)
static

ZSTD_ldm_countBackwardsMatch() : Returns the number of bytes that match backwards before pIn and pMatch.

We count only bytes where pMatch >= pBase and pIn >= pAnchor.

Definition at line 200 of file zstd_ldm.c.

203 {
204  size_t matchLength = 0;
205  while (pIn > pAnchor && pMatch > pBase && pIn[-1] == pMatch[-1]) {
206  pIn--;
207  pMatch--;
208  matchLength++;
209  }
210  return matchLength;
211 }

Referenced by ZSTD_ldm_generateSequences_internal().

◆ ZSTD_ldm_fillFastTables()

static size_t ZSTD_ldm_fillFastTables ( ZSTD_matchState_t ms,
void const end 
)
static

ZSTD_ldm_fillFastTables() :

Fills the relevant tables for the ZSTD_fast and ZSTD_dfast strategies. This is similar to ZSTD_loadDictionaryContent.

The tables for the other strategies are filled within their block compressors.

Definition at line 220 of file zstd_ldm.c.

222 {
223  const BYTE* const iend = (const BYTE*)end;
224 
225  switch(ms->cParams.strategy)
226  {
227  case ZSTD_fast:
229  break;
230 
231  case ZSTD_dfast:
233  break;
234 
235  case ZSTD_greedy:
236  case ZSTD_lazy:
237  case ZSTD_lazy2:
238  case ZSTD_btlazy2:
239  case ZSTD_btopt:
240  case ZSTD_btultra:
241  break;
242  default:
243  assert(0); /* not possible : not a valid strategy id */
244  }
245 
246  return 0;
247 }
void ZSTD_fillHashTable(ZSTD_matchState_t *ms, void const *end, ZSTD_dictTableLoadMethod_e dtlm)
Definition: zstd_fast.c:15
#define assert(x)
Definition: debug.h:53
GLuint GLuint end
Definition: gl.h:1545
ZSTD_compressionParameters cParams
void ZSTD_fillDoubleHashTable(ZSTD_matchState_t *ms, void const *end, ZSTD_dictTableLoadMethod_e dtlm)
unsigned char BYTE
Definition: xxhash.c:193

Referenced by ZSTD_ldm_blockCompress().

◆ ZSTD_ldm_fillLdmHashTable()

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 
)
static

ZSTD_ldm_fillLdmHashTable() :

Fills hashTable from (lastHashed + 1) to iend (non-inclusive). lastHash is the rolling hash that corresponds to lastHashed.

Returns the rolling hash corresponding to position iend-1.

Definition at line 255 of file zstd_ldm.c.

259 {
260  U64 rollingHash = lastHash;
261  const BYTE* cur = lastHashed + 1;
262 
263  while (cur < iend) {
264  rollingHash = ZSTD_ldm_updateHash(rollingHash, cur[-1],
265  cur[ldmParams.minMatchLength-1],
266  state->hashPower);
268  rollingHash, hBits,
269  (U32)(cur - base), ldmParams);
270  ++cur;
271  }
272  return rollingHash;
273 }
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:128
static int state
Definition: maze.c:121
unsigned char BYTE
Definition: xxhash.c:193
static U64 ZSTD_ldm_updateHash(U64 hash, BYTE toRemove, BYTE toAdd, U64 hashPower)
Definition: zstd_ldm.c:188
unsigned long long U64
Definition: xxhash.c:197
unsigned int U32
Definition: xxhash.c:195

Referenced by ZSTD_ldm_generateSequences_internal().

◆ ZSTD_ldm_generateSequences()

size_t ZSTD_ldm_generateSequences ( ldmState_t ldms,
rawSeqStore_t sequences,
ldmParams_t const params,
void const src,
size_t  srcSize 
)

ZSTD_ldm_generateSequences():

Generates the sequences using the long distance match finder. Generates long range matching sequences in sequences, which parse a prefix of the source. sequences must be large enough to store every sequence, which can be checked with ZSTD_ldm_getMaxNbSeq().

Returns
0 or an error code.

NOTE: The user must have called ZSTD_window_update() for all of the input they have, even if they pass it to ZSTD_ldm_generateSequences() in chunks. NOTE: This function returns an error if it runs out of space to store sequences.

Definition at line 463 of file zstd_ldm.c.

466 {
467  U32 const maxDist = 1U << params->windowLog;
468  BYTE const* const istart = (BYTE const*)src;
469  BYTE const* const iend = istart + srcSize;
470  size_t const kMaxChunkSize = 1 << 20;
471  size_t const nbChunks = (srcSize / kMaxChunkSize) + ((srcSize % kMaxChunkSize) != 0);
472  size_t chunk;
473  size_t leftoverSize = 0;
474 
475  assert(ZSTD_CHUNKSIZE_MAX >= kMaxChunkSize);
476  /* Check that ZSTD_window_update() has been called for this chunk prior
477  * to passing it to this function.
478  */
479  assert(ldmState->window.nextSrc >= (BYTE const*)src + srcSize);
480  /* The input could be very large (in zstdmt), so it must be broken up into
481  * chunks to enforce the maximmum distance and handle overflow correction.
482  */
483  assert(sequences->pos <= sequences->size);
484  assert(sequences->size <= sequences->capacity);
485  for (chunk = 0; chunk < nbChunks && sequences->size < sequences->capacity; ++chunk) {
486  BYTE const* const chunkStart = istart + chunk * kMaxChunkSize;
487  size_t const remaining = (size_t)(iend - chunkStart);
488  BYTE const *const chunkEnd =
489  (remaining < kMaxChunkSize) ? iend : chunkStart + kMaxChunkSize;
490  size_t const chunkSize = chunkEnd - chunkStart;
491  size_t newLeftoverSize;
492  size_t const prevSize = sequences->size;
493 
494  assert(chunkStart < iend);
495  /* 1. Perform overflow correction if necessary. */
496  if (ZSTD_window_needOverflowCorrection(ldmState->window, chunkEnd)) {
497  U32 const ldmHSize = 1U << params->hashLog;
498  U32 const correction = ZSTD_window_correctOverflow(
499  &ldmState->window, /* cycleLog */ 0, maxDist, src);
500  ZSTD_ldm_reduceTable(ldmState->hashTable, ldmHSize, correction);
501  }
502  /* 2. We enforce the maximum offset allowed.
503  *
504  * kMaxChunkSize should be small enough that we don't lose too much of
505  * the window through early invalidation.
506  * TODO: * Test the chunk size.
507  * * Try invalidation after the sequence generation and test the
508  * the offset against maxDist directly.
509  */
510  ZSTD_window_enforceMaxDist(&ldmState->window, chunkEnd, maxDist, NULL, NULL);
511  /* 3. Generate the sequences for the chunk, and get newLeftoverSize. */
512  newLeftoverSize = ZSTD_ldm_generateSequences_internal(
513  ldmState, sequences, params, chunkStart, chunkSize);
514  if (ZSTD_isError(newLeftoverSize))
515  return newLeftoverSize;
516  /* 4. We add the leftover literals from previous iterations to the first
517  * newly generated sequence, or add the `newLeftoverSize` if none are
518  * generated.
519  */
520  /* Prepend the leftover literals from the last call */
521  if (prevSize < sequences->size) {
522  sequences->seq[prevSize].litLength += (U32)leftoverSize;
523  leftoverSize = newLeftoverSize;
524  } else {
525  assert(newLeftoverSize == chunkSize);
526  leftoverSize += chunkSize;
527  }
528  }
529  return 0;
530 }
#define U(x)
Definition: wordpad.c:45
#define assert(x)
Definition: debug.h:53
ldmEntry_t * hashTable
static void ZSTD_ldm_reduceTable(ldmEntry_t *const table, U32 const size, U32 const reducerValue)
Definition: zstd_ldm.c:453
GLenum const GLfloat * params
Definition: glext.h:5645
smooth NULL
Definition: ftsmooth.c:416
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:290
MEM_STATIC void ZSTD_window_enforceMaxDist(ZSTD_window_t *window, void const *srcEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
__kernel_size_t size_t
Definition: linux.h:237
GLsizeiptr size
Definition: glext.h:5919
MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window, void const *srcEnd)
GLenum src
Definition: glext.h:6340
unsigned char BYTE
Definition: xxhash.c:193
static struct msg_sequence * sequences[NUM_MSG_SEQUENCES]
Definition: button.c:54
MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t *window, U32 cycleLog, U32 maxDist, void const *src)
#define ZSTD_isError
#define ZSTD_CHUNKSIZE_MAX
ZSTD_window_t window
unsigned int U32
Definition: xxhash.c:195

Referenced by ZSTD_compressBlock_internal().

◆ ZSTD_ldm_generateSequences_internal()

static size_t ZSTD_ldm_generateSequences_internal ( ldmState_t ldmState,
rawSeqStore_t rawSeqStore,
ldmParams_t const params,
void const src,
size_t  srcSize 
)
static

Definition at line 290 of file zstd_ldm.c.

293 {
294  /* LDM parameters */
295  int const extDict = ZSTD_window_hasExtDict(ldmState->window);
296  U32 const minMatchLength = params->minMatchLength;
297  U64 const hashPower = ldmState->hashPower;
298  U32 const hBits = params->hashLog - params->bucketSizeLog;
299  U32 const ldmBucketSize = 1U << params->bucketSizeLog;
300  U32 const hashEveryLog = params->hashEveryLog;
301  U32 const ldmTagMask = (1U << params->hashEveryLog) - 1;
302  /* Prefix and extDict parameters */
303  U32 const dictLimit = ldmState->window.dictLimit;
304  U32 const lowestIndex = extDict ? ldmState->window.lowLimit : dictLimit;
305  BYTE const* const base = ldmState->window.base;
306  BYTE const* const dictBase = extDict ? ldmState->window.dictBase : NULL;
307  BYTE const* const dictStart = extDict ? dictBase + lowestIndex : NULL;
308  BYTE const* const dictEnd = extDict ? dictBase + dictLimit : NULL;
309  BYTE const* const lowPrefixPtr = base + dictLimit;
310  /* Input bounds */
311  BYTE const* const istart = (BYTE const*)src;
312  BYTE const* const iend = istart + srcSize;
313  BYTE const* const ilimit = iend - MAX(minMatchLength, HASH_READ_SIZE);
314  /* Input positions */
315  BYTE const* anchor = istart;
316  BYTE const* ip = istart;
317  /* Rolling hash */
318  BYTE const* lastHashed = NULL;
319  U64 rollingHash = 0;
320 
321  while (ip <= ilimit) {
322  size_t mLength;
323  U32 const current = (U32)(ip - base);
324  size_t forwardMatchLength = 0, backwardMatchLength = 0;
325  ldmEntry_t* bestEntry = NULL;
326  if (ip != istart) {
327  rollingHash = ZSTD_ldm_updateHash(rollingHash, lastHashed[0],
328  lastHashed[minMatchLength],
329  hashPower);
330  } else {
331  rollingHash = ZSTD_ldm_getRollingHash(ip, minMatchLength);
332  }
333  lastHashed = ip;
334 
335  /* Do not insert and do not look for a match */
336  if (ZSTD_ldm_getTag(rollingHash, hBits, hashEveryLog) != ldmTagMask) {
337  ip++;
338  continue;
339  }
340 
341  /* Get the best entry and compute the match lengths */
342  {
343  ldmEntry_t* const bucket =
344  ZSTD_ldm_getBucket(ldmState,
345  ZSTD_ldm_getSmallHash(rollingHash, hBits),
346  *params);
347  ldmEntry_t* cur;
348  size_t bestMatchLength = 0;
349  U32 const checksum = ZSTD_ldm_getChecksum(rollingHash, hBits);
350 
351  for (cur = bucket; cur < bucket + ldmBucketSize; ++cur) {
352  size_t curForwardMatchLength, curBackwardMatchLength,
353  curTotalMatchLength;
354  if (cur->checksum != checksum || cur->offset <= lowestIndex) {
355  continue;
356  }
357  if (extDict) {
358  BYTE const* const curMatchBase =
359  cur->offset < dictLimit ? dictBase : base;
360  BYTE const* const pMatch = curMatchBase + cur->offset;
361  BYTE const* const matchEnd =
362  cur->offset < dictLimit ? dictEnd : iend;
363  BYTE const* const lowMatchPtr =
364  cur->offset < dictLimit ? dictStart : lowPrefixPtr;
365 
366  curForwardMatchLength = ZSTD_count_2segments(
367  ip, pMatch, iend,
368  matchEnd, lowPrefixPtr);
369  if (curForwardMatchLength < minMatchLength) {
370  continue;
371  }
372  curBackwardMatchLength =
373  ZSTD_ldm_countBackwardsMatch(ip, anchor, pMatch,
374  lowMatchPtr);
375  curTotalMatchLength = curForwardMatchLength +
376  curBackwardMatchLength;
377  } else { /* !extDict */
378  BYTE const* const pMatch = base + cur->offset;
379  curForwardMatchLength = ZSTD_count(ip, pMatch, iend);
380  if (curForwardMatchLength < minMatchLength) {
381  continue;
382  }
383  curBackwardMatchLength =
384  ZSTD_ldm_countBackwardsMatch(ip, anchor, pMatch,
385  lowPrefixPtr);
386  curTotalMatchLength = curForwardMatchLength +
387  curBackwardMatchLength;
388  }
389 
390  if (curTotalMatchLength > bestMatchLength) {
391  bestMatchLength = curTotalMatchLength;
392  forwardMatchLength = curForwardMatchLength;
393  backwardMatchLength = curBackwardMatchLength;
394  bestEntry = cur;
395  }
396  }
397  }
398 
399  /* No match found -- continue searching */
400  if (bestEntry == NULL) {
401  ZSTD_ldm_makeEntryAndInsertByTag(ldmState, rollingHash,
402  hBits, current,
403  *params);
404  ip++;
405  continue;
406  }
407 
408  /* Match found */
409  mLength = forwardMatchLength + backwardMatchLength;
410  ip -= backwardMatchLength;
411 
412  {
413  /* Store the sequence:
414  * ip = current - backwardMatchLength
415  * The match is at (bestEntry->offset - backwardMatchLength)
416  */
417  U32 const matchIndex = bestEntry->offset;
418  U32 const offset = current - matchIndex;
419  rawSeq* const seq = rawSeqStore->seq + rawSeqStore->size;
420 
421  /* Out of sequence storage */
422  if (rawSeqStore->size == rawSeqStore->capacity)
423  return ERROR(dstSize_tooSmall);
424  seq->litLength = (U32)(ip - anchor);
425  seq->matchLength = (U32)mLength;
426  seq->offset = offset;
427  rawSeqStore->size++;
428  }
429 
430  /* Insert the current entry into the hash table */
431  ZSTD_ldm_makeEntryAndInsertByTag(ldmState, rollingHash, hBits,
432  (U32)(lastHashed - base),
433  *params);
434 
435  assert(ip + backwardMatchLength == lastHashed);
436 
437  /* Fill the hash table from lastHashed+1 to ip+mLength*/
438  /* Heuristic: don't need to fill the entire table at end of block */
439  if (ip + mLength <= ilimit) {
440  rollingHash = ZSTD_ldm_fillLdmHashTable(
441  ldmState, rollingHash, lastHashed,
442  ip + mLength, base, hBits, *params);
443  lastHashed = ip + mLength - 1;
444  }
445  ip += mLength;
446  anchor = ip;
447  }
448  return iend - anchor;
449 }
static U64 ZSTD_ldm_getRollingHash(const BYTE *buf, U32 len)
Definition: zstd_ldm.c:156
#define ERROR(name)
Definition: error_private.h:53
#define U(x)
Definition: wordpad.c:45
GLintptr offset
Definition: glext.h:5920
MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
#define assert(x)
Definition: debug.h:53
static ldmEntry_t * ZSTD_ldm_getBucket(ldmState_t *ldmState, size_t hash, ldmParams_t const ldmParams)
Definition: zstd_ldm.c:100
GLenum const GLfloat * params
Definition: glext.h:5645
GLuint base
Definition: 3dtext.c:35
int ip[4]
Definition: rtl.c:1176
smooth NULL
Definition: ftsmooth.c:416
static U32 ZSTD_ldm_getChecksum(U64 hash, U32 numBitsToDiscard)
Definition: zstd_ldm.c:76
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)
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:128
Definition: dhcpd.h:61
static U32 ZSTD_ldm_getTag(U64 hash, U32 hbits, U32 numTagBits)
Definition: zstd_ldm.c:88
#define HASH_READ_SIZE
GLenum src
Definition: glext.h:6340
static cab_ULONG checksum(const cab_UBYTE *data, cab_UWORD bytes, cab_ULONG csum)
Definition: fdi.c:353
unsigned char BYTE
Definition: xxhash.c:193
static U64 ZSTD_ldm_updateHash(U64 hash, BYTE toRemove, BYTE toAdd, U64 hashPower)
Definition: zstd_ldm.c:188
T MAX(T a, T b)
Definition: polytest.cpp:85
unsigned long long U64
Definition: xxhash.c:197
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:255
ZSTD_window_t window
static U32 ZSTD_ldm_getSmallHash(U64 value, U32 numBits)
Definition: zstd_ldm.c:67
unsigned int U32
Definition: xxhash.c:195
struct task_struct * current
Definition: linux.c:32
static size_t ZSTD_ldm_countBackwardsMatch(const BYTE *pIn, const BYTE *pAnchor, const BYTE *pMatch, const BYTE *pBase)
Definition: zstd_ldm.c:200

Referenced by ZSTD_ldm_generateSequences().

◆ ZSTD_ldm_getBucket()

static ldmEntry_t* ZSTD_ldm_getBucket ( ldmState_t ldmState,
size_t  hash,
ldmParams_t const  ldmParams 
)
static

ZSTD_ldm_getBucket() : Returns a pointer to the start of the bucket associated with hash.

Definition at line 100 of file zstd_ldm.c.

102 {
103  return ldmState->hashTable + (hash << ldmParams.bucketSizeLog);
104 }
ldmEntry_t * hashTable
Definition: _hash_fun.h:40

Referenced by ZSTD_ldm_generateSequences_internal(), and ZSTD_ldm_insertEntry().

◆ ZSTD_ldm_getChecksum()

static U32 ZSTD_ldm_getChecksum ( U64  hash,
U32  numBitsToDiscard 
)
static

ZSTD_ldm_getChecksum() : numBitsToDiscard should be <= 32

Returns
: the next most significant 32 bits after numBitsToDiscard

Definition at line 76 of file zstd_ldm.c.

77 {
78  assert(numBitsToDiscard <= 32);
79  return (hash >> (64 - 32 - numBitsToDiscard)) & 0xFFFFFFFF;
80 }
#define assert(x)
Definition: debug.h:53
Definition: _hash_fun.h:40

Referenced by ZSTD_ldm_generateSequences_internal(), and ZSTD_ldm_makeEntryAndInsertByTag().

◆ ZSTD_ldm_getHashPower()

U64 ZSTD_ldm_getHashPower ( U32  minMatchLength)

ZSTD_ldm_getTableSize() : Return prime8bytes^(minMatchLength-1)

Definition at line 180 of file zstd_ldm.c.

180  {
181  DEBUGLOG(4, "ZSTD_ldm_getHashPower: mml=%u", minMatchLength);
182  assert(minMatchLength >= ZSTD_LDM_MINMATCH_MIN);
183  return ZSTD_ldm_ipow(prime8bytes, minMatchLength - 1);
184 }
#define assert(x)
Definition: debug.h:53
#define DEBUGLOG(l,...)
Definition: debug.h:115
static const U64 prime8bytes
static U64 ZSTD_ldm_ipow(U64 base, U64 exp)
Definition: zstd_ldm.c:169

Referenced by ZSTD_resetCCtx_internal().

◆ ZSTD_ldm_getMaxNbSeq()

size_t ZSTD_ldm_getMaxNbSeq ( ldmParams_t  params,
size_t  maxChunkSize 
)

ZSTD_ldm_getSeqSpace() : Return an upper bound on the number of sequences that can be produced by the long distance matcher, or 0 if LDM is disabled.

Definition at line 58 of file zstd_ldm.c.

59 {
60  return params.enableLdm ? (maxChunkSize / params.minMatchLength) : 0;
61 }
GLenum const GLfloat * params
Definition: glext.h:5645

Referenced by ZSTD_estimateCCtxSize_usingCCtxParams(), and ZSTD_resetCCtx_internal().

◆ ZSTD_ldm_getRollingHash()

static U64 ZSTD_ldm_getRollingHash ( const BYTE buf,
U32  len 
)
static

ZSTD_ldm_getRollingHash() : Get a 64-bit hash using the first len bytes from buf.

Giving bytes s = s_1, s_2, ... s_k, the hash is defined to be H(s) = s_1*(a^(k-1)) + s_2*(a^(k-2)) + ... + s_k*(a^0)

where the constant a is defined to be prime8bytes.

The implementation adds an offset to each byte, so H(s) = (s_1 + HASH_CHAR_OFFSET)*(a^(k-1)) + ...

Definition at line 156 of file zstd_ldm.c.

157 {
158  U64 ret = 0;
159  U32 i;
160  for (i = 0; i < len; i++) {
161  ret *= prime8bytes;
163  }
164  return ret;
165 }
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
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
static const U64 prime8bytes
int ret
GLenum GLsizei len
Definition: glext.h:6722
unsigned long long U64
Definition: xxhash.c:197
#define LDM_HASH_CHAR_OFFSET
Definition: zstd_ldm.c:19
unsigned int U32
Definition: xxhash.c:195

Referenced by ZSTD_ldm_generateSequences_internal().

◆ ZSTD_ldm_getSmallHash()

static U32 ZSTD_ldm_getSmallHash ( U64  value,
U32  numBits 
)
static

ZSTD_ldm_getSmallHash() : numBits should be <= 32 If numBits==0, returns 0.

Returns
: the most significant numBits of value.

Definition at line 67 of file zstd_ldm.c.

68 {
69  assert(numBits <= 32);
70  return numBits == 0 ? 0 : (U32)(value >> (64 - numBits));
71 }
#define assert(x)
Definition: debug.h:53
unsigned int U32
Definition: xxhash.c:195

Referenced by ZSTD_ldm_generateSequences_internal(), and ZSTD_ldm_makeEntryAndInsertByTag().

◆ ZSTD_ldm_getTableSize()

size_t ZSTD_ldm_getTableSize ( ldmParams_t  params)

ZSTD_ldm_getTableSize() : Estimate the space needed for long distance matching tables or 0 if LDM is disabled.

Definition at line 48 of file zstd_ldm.c.

49 {
50  size_t const ldmHSize = ((size_t)1) << params.hashLog;
51  size_t const ldmBucketSizeLog = MIN(params.bucketSizeLog, params.hashLog);
52  size_t const ldmBucketSize =
53  ((size_t)1) << (params.hashLog - ldmBucketSizeLog);
54  size_t const totalSize = ldmBucketSize + ldmHSize * sizeof(ldmEntry_t);
55  return params.enableLdm ? totalSize : 0;
56 }
T MIN(T a, T b)
Definition: polytest.cpp:79
GLenum const GLfloat * params
Definition: glext.h:5645
__kernel_size_t size_t
Definition: linux.h:237

Referenced by ZSTD_estimateCCtxSize_usingCCtxParams(), and ZSTD_resetCCtx_internal().

◆ ZSTD_ldm_getTag()

static U32 ZSTD_ldm_getTag ( U64  hash,
U32  hbits,
U32  numTagBits 
)
static

ZSTD_ldm_getTag() ; Given the hash, returns the most significant numTagBits bits after (32 + hbits) bits.

If there are not enough bits remaining, return the last numTagBits bits.

Definition at line 88 of file zstd_ldm.c.

89 {
90  assert(numTagBits < 32 && hbits <= 32);
91  if (32 - hbits < numTagBits) {
92  return hash & (((U32)1 << numTagBits) - 1);
93  } else {
94  return (hash >> (32 - hbits - numTagBits)) & (((U32)1 << numTagBits) - 1);
95  }
96 }
#define assert(x)
Definition: debug.h:53
Definition: _hash_fun.h:40
unsigned int U32
Definition: xxhash.c:195

Referenced by ZSTD_ldm_generateSequences_internal(), and ZSTD_ldm_makeEntryAndInsertByTag().

◆ ZSTD_ldm_insertEntry()

static void ZSTD_ldm_insertEntry ( ldmState_t ldmState,
size_t const  hash,
const ldmEntry_t  entry,
ldmParams_t const  ldmParams 
)
static

ZSTD_ldm_insertEntry() : Insert the entry with corresponding hash into the hash table

Definition at line 108 of file zstd_ldm.c.

111 {
112  BYTE* const bucketOffsets = ldmState->bucketOffsets;
113  *(ZSTD_ldm_getBucket(ldmState, hash, ldmParams) + bucketOffsets[hash]) = entry;
114  bucketOffsets[hash]++;
115  bucketOffsets[hash] &= ((U32)1 << ldmParams.bucketSizeLog) - 1;
116 }
static ldmEntry_t * ZSTD_ldm_getBucket(ldmState_t *ldmState, size_t hash, ldmParams_t const ldmParams)
Definition: zstd_ldm.c:100
int hash
Definition: main.c:58
uint32_t entry
Definition: isohybrid.c:63
unsigned char BYTE
Definition: xxhash.c:193
Definition: _hash_fun.h:40
unsigned int U32
Definition: xxhash.c:195

Referenced by ZSTD_ldm_makeEntryAndInsertByTag().

◆ ZSTD_ldm_ipow()

static U64 ZSTD_ldm_ipow ( U64  base,
U64  exp 
)
static

ZSTD_ldm_ipow() : Return base^exp.

Definition at line 169 of file zstd_ldm.c.

170 {
171  U64 ret = 1;
172  while (exp) {
173  if (exp & 1) { ret *= base; }
174  exp >>= 1;
175  base *= base;
176  }
177  return ret;
178 }
GLuint base
Definition: 3dtext.c:35
int ret
unsigned long long U64
Definition: xxhash.c:197
DWORD exp
Definition: msg.c:16033

Referenced by ZSTD_ldm_getHashPower().

◆ ZSTD_ldm_limitTableUpdate()

static void ZSTD_ldm_limitTableUpdate ( ZSTD_matchState_t ms,
const BYTE anchor 
)
static

ZSTD_ldm_limitTableUpdate() :

Sets cctx->nextToUpdate to a position corresponding closer to anchor if it is far way (after a long match, only update tables a limited amount).

Definition at line 281 of file zstd_ldm.c.

282 {
283  U32 const current = (U32)(anchor - ms->window.base);
284  if (current > ms->nextToUpdate + 1024) {
285  ms->nextToUpdate =
286  current - MIN(512, current - ms->nextToUpdate - 1024);
287  }
288 }
T MIN(T a, T b)
Definition: polytest.cpp:79
unsigned int U32
Definition: xxhash.c:195
struct task_struct * current
Definition: linux.c:32

Referenced by ZSTD_ldm_blockCompress().

◆ ZSTD_ldm_makeEntryAndInsertByTag()

static void ZSTD_ldm_makeEntryAndInsertByTag ( ldmState_t ldmState,
U64 const  rollingHash,
U32 const  hBits,
U32 const  offset,
ldmParams_t const  ldmParams 
)
static

ZSTD_ldm_makeEntryAndInsertByTag() :

Gets the small hash, checksum, and tag from the rollingHash.

If the tag matches (1 << ldmParams.hashEveryLog)-1, then creates an ldmEntry from the offset, and inserts it into the hash table.

hBits is the length of the small hash, which is the most significant hBits of rollingHash. The checksum is the next 32 most significant bits, followed by ldmParams.hashEveryLog bits that make up the tag.

Definition at line 128 of file zstd_ldm.c.

133 {
134  U32 const tag = ZSTD_ldm_getTag(rollingHash, hBits, ldmParams.hashEveryLog);
135  U32 const tagMask = ((U32)1 << ldmParams.hashEveryLog) - 1;
136  if (tag == tagMask) {
137  U32 const hash = ZSTD_ldm_getSmallHash(rollingHash, hBits);
138  U32 const checksum = ZSTD_ldm_getChecksum(rollingHash, hBits);
140  entry.offset = offset;
141  entry.checksum = checksum;
142  ZSTD_ldm_insertEntry(ldmState, hash, entry, ldmParams);
143  }
144 }
GLintptr offset
Definition: glext.h:5920
Definition: ecma_167.h:138
static U32 ZSTD_ldm_getChecksum(U64 hash, U32 numBitsToDiscard)
Definition: zstd_ldm.c:76
static U32 ZSTD_ldm_getTag(U64 hash, U32 hbits, U32 numTagBits)
Definition: zstd_ldm.c:88
static void ZSTD_ldm_insertEntry(ldmState_t *ldmState, size_t const hash, const ldmEntry_t entry, ldmParams_t const ldmParams)
Definition: zstd_ldm.c:108
uint32_t entry
Definition: isohybrid.c:63
static cab_ULONG checksum(const cab_UBYTE *data, cab_UWORD bytes, cab_ULONG csum)
Definition: fdi.c:353
static U32 ZSTD_ldm_getSmallHash(U64 value, U32 numBits)
Definition: zstd_ldm.c:67
Definition: _hash_fun.h:40
unsigned int U32
Definition: xxhash.c:195

Referenced by ZSTD_ldm_fillLdmHashTable(), and ZSTD_ldm_generateSequences_internal().

◆ ZSTD_ldm_reduceTable()

static void ZSTD_ldm_reduceTable ( ldmEntry_t *const  table,
U32 const  size,
U32 const  reducerValue 
)
static

ZSTD_ldm_reduceTable() : reduce table indexes by reducerValue

Definition at line 453 of file zstd_ldm.c.

455 {
456  U32 u;
457  for (u = 0; u < size; u++) {
458  if (table[u].offset < reducerValue) table[u].offset = 0;
459  else table[u].offset -= reducerValue;
460  }
461 }
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
GLintptr offset
Definition: glext.h:5920
GLsizeiptr size
Definition: glext.h:5919
unsigned int U32
Definition: xxhash.c:195

Referenced by ZSTD_ldm_generateSequences().

◆ ZSTD_ldm_skipSequences()

void ZSTD_ldm_skipSequences ( rawSeqStore_t rawSeqStore,
size_t  srcSize,
U32 const  minMatch 
)

ZSTD_ldm_skipSequences():

Skip past srcSize bytes worth of sequences in rawSeqStore. Avoids emitting matches less than minMatch bytes. Must be called for data with is not passed to ZSTD_ldm_blockCompress().

Definition at line 532 of file zstd_ldm.c.

532  {
533  while (srcSize > 0 && rawSeqStore->pos < rawSeqStore->size) {
534  rawSeq* seq = rawSeqStore->seq + rawSeqStore->pos;
535  if (srcSize <= seq->litLength) {
536  /* Skip past srcSize literals */
537  seq->litLength -= (U32)srcSize;
538  return;
539  }
540  srcSize -= seq->litLength;
541  seq->litLength = 0;
542  if (srcSize < seq->matchLength) {
543  /* Skip past the first srcSize of the match */
544  seq->matchLength -= (U32)srcSize;
545  if (seq->matchLength < minMatch) {
546  /* The match is too short, omit it */
547  if (rawSeqStore->pos + 1 < rawSeqStore->size) {
548  seq[1].litLength += seq[0].matchLength;
549  }
550  rawSeqStore->pos++;
551  }
552  return;
553  }
554  srcSize -= seq->matchLength;
555  seq->matchLength = 0;
556  rawSeqStore->pos++;
557  }
558 }
unsigned int U32
Definition: xxhash.c:195

Referenced by maybeSplitSequence(), and ZSTD_compressBlock_internal().

◆ ZSTD_ldm_updateHash()

static U64 ZSTD_ldm_updateHash ( U64  hash,
BYTE  toRemove,
BYTE  toAdd,
U64  hashPower 
)
static

ZSTD_ldm_updateHash() : Updates hash by removing toRemove and adding toAdd.

Definition at line 188 of file zstd_ldm.c.

189 {
190  hash -= ((toRemove + LDM_HASH_CHAR_OFFSET) * hashPower);
191  hash *= prime8bytes;
192  hash += toAdd + LDM_HASH_CHAR_OFFSET;
193  return hash;
194 }
int hash
Definition: main.c:58
static const U64 prime8bytes
#define LDM_HASH_CHAR_OFFSET
Definition: zstd_ldm.c:19
Definition: _hash_fun.h:40

Referenced by ZSTD_ldm_fillLdmHashTable(), and ZSTD_ldm_generateSequences_internal().