ReactOS 0.4.16-dev-122-g325d74c
zstd_ldm.h File Reference
#include "zstd_compress_internal.h"
#include "zstd.h"
Include dependency graph for zstd_ldm.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define ZSTD_LDM_DEFAULT_WINDOW_LOG   ZSTD_WINDOWLOG_LIMIT_DEFAULT
 

Functions

void ZSTD_ldm_fillHashTable (ldmState_t *state, const BYTE *ip, const BYTE *iend, ldmParams_t const *params)
 
size_t ZSTD_ldm_generateSequences (ldmState_t *ldms, rawSeqStore_t *sequences, ldmParams_t const *params, void const *src, size_t srcSize)
 
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)
 
void ZSTD_ldm_skipSequences (rawSeqStore_t *rawSeqStore, size_t srcSize, U32 const minMatch)
 
size_t ZSTD_ldm_getTableSize (ldmParams_t params)
 
size_t ZSTD_ldm_getMaxNbSeq (ldmParams_t params, size_t maxChunkSize)
 
void ZSTD_ldm_adjustParameters (ldmParams_t *params, ZSTD_compressionParameters const *cParams)
 

Macro Definition Documentation

◆ ZSTD_LDM_DEFAULT_WINDOW_LOG

#define ZSTD_LDM_DEFAULT_WINDOW_LOG   ZSTD_WINDOWLOG_LIMIT_DEFAULT

Definition at line 25 of file zstd_ldm.h.

Function Documentation

◆ ZSTD_ldm_adjustParameters()

void ZSTD_ldm_adjustParameters ( ldmParams_t params,
ZSTD_compressionParameters const cParams 
)

ZSTD_ldm_adjustParameters() : If the params->hashRateLog 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 22 of file zstd_ldm.c.

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}
#define MIN(x, y)
Definition: rdesktop.h:171
#define MAX(x, y)
Definition: rdesktop.h:175
#define assert(x)
Definition: debug.h:53
#define DEBUGLOG(l,...)
Definition: debug.h:106
GLenum const GLfloat * params
Definition: glext.h:5645
unsigned int U32
Definition: xxhash.c:195
@ ZSTD_btopt
Definition: zstd.h:257
#define ZSTD_STATIC_ASSERT(c)
Definition: zstd_internal.h:45
#define LDM_BUCKET_SIZE_LOG
Definition: zstd_ldm.c:17
#define LDM_HASH_RLOG
Definition: zstd_ldm.c:19
#define LDM_MIN_MATCH_LENGTH
Definition: zstd_ldm.c:18

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 565 of file zstd_ldm.c.

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
GLenum src
Definition: glext.h:6340
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
Definition: dhcpd.h:62
unsigned char BYTE
Definition: xxhash.c:193
ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode)
MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms)
size_t(* ZSTD_blockCompressor)(ZSTD_matchState_t *bs, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
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 MINMATCH
#define ZSTD_REP_MOVE
#define ZSTD_REP_NUM
static size_t ZSTD_ldm_fillFastTables(ZSTD_matchState_t *ms, void const *end)
Definition: zstd_ldm.c:171
static rawSeq maybeSplitSequence(rawSeqStore_t *rawSeqStore, U32 const remaining, U32 const minMatch)
Definition: zstd_ldm.c:541
static void ZSTD_ldm_limitTableUpdate(ZSTD_matchState_t *ms, const BYTE *anchor)
Definition: zstd_ldm.c:247

Referenced by ZSTD_buildSeqStore().

◆ ZSTD_ldm_fillHashTable()

void ZSTD_ldm_fillHashTable ( ldmState_t state,
const BYTE ip,
const BYTE iend,
ldmParams_t const params 
)

Definition at line 227 of file zstd_ldm.c.

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}
static int state
Definition: maze.c:121
unsigned long long U64
Definition: xxhash.c:197
MEM_STATIC U64 ZSTD_rollingHash_compute(void const *buf, size_t size)
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

Referenced by ZSTD_loadDictionaryContent().

◆ 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 429 of file zstd_ldm.c.

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}
#define NULL
Definition: types.h:112
__kernel_size_t size_t
Definition: linux.h:237
GLsizeiptr size
Definition: glext.h:5919
static struct msg_sequence * sequences[NUM_MSG_SEQUENCES]
Definition: button.c:54
MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window, void const *srcEnd)
#define ZSTD_CHUNKSIZE_MAX
MEM_STATIC void ZSTD_window_enforceMaxDist(ZSTD_window_t *window, const void *blockEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t *window, U32 cycleLog, U32 maxDist, void const *src)
#define ZSTD_isError
Definition: zstd_internal.h:46
static void ZSTD_ldm_reduceTable(ldmEntry_t *const table, U32 const size, U32 const reducerValue)
Definition: zstd_ldm.c:419
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

Referenced by ZSTD_buildSeqStore().

◆ 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 59 of file zstd_ldm.c.

60{
61 return params.enableLdm ? (maxChunkSize / params.minMatchLength) : 0;
62}

Referenced by ZSTD_estimateCCtxSize_usingCCtxParams(), and ZSTD_resetCCtx_internal().

◆ 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 49 of file zstd_ldm.c.

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}
MEM_STATIC size_t ZSTD_cwksp_alloc_size(size_t size)
Definition: zstd_cwksp.h:180

Referenced by ZSTD_estimateCCtxSize_usingCCtxParams(), and ZSTD_resetCCtx_internal().

◆ 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 506 of file zstd_ldm.c.

506 {
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}

Referenced by maybeSplitSequence(), and ZSTD_buildSeqStore().