16 #define LDM_BUCKET_SIZE_LOG 3 17 #define LDM_MIN_MATCH_LENGTH 64 18 #define LDM_HASH_RLOG 7 19 #define LDM_HASH_CHAR_OFFSET 10 22 ZSTD_compressionParameters
const* cParams)
24 params->windowLog = cParams->windowLog;
26 DEBUGLOG(4,
"ZSTD_ldm_adjustParameters");
29 if (cParams->strategy >= ZSTD_btopt) {
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;
36 if (
params->hashLog == 0) {
40 if (
params->hashEveryLog == 0) {
51 size_t const ldmBucketSizeLog =
MIN(
params.bucketSizeLog,
params.hashLog);
52 size_t const ldmBucketSize =
54 size_t const totalSize = ldmBucketSize + ldmHSize *
sizeof(
ldmEntry_t);
55 return params.enableLdm ? totalSize : 0;
60 return params.enableLdm ? (maxChunkSize /
params.minMatchLength) : 0;
70 return numBits == 0 ? 0 : (
U32)(
value >> (64 - numBits));
78 assert(numBitsToDiscard <= 32);
79 return (
hash >> (64 - 32 - numBitsToDiscard)) & 0xFFFFFFFF;
90 assert(numTagBits < 32 && hbits <= 32);
91 if (32 - hbits < numTagBits) {
92 return hash & (((
U32)1 << numTagBits) - 1);
94 return (
hash >> (32 - hbits - numTagBits)) & (((
U32)1 << numTagBits) - 1);
114 bucketOffsets[
hash]++;
129 U64 const rollingHash,
136 if (
tag == tagMask) {
160 for (
i = 0;
i <
len;
i++) {
181 DEBUGLOG(4,
"ZSTD_ldm_getHashPower: mml=%u", minMatchLength);
182 assert(minMatchLength >= ZSTD_LDM_MINMATCH_MIN);
201 const BYTE* pIn,
const BYTE* pAnchor,
202 const BYTE* pMatch,
const BYTE* pBase)
204 size_t matchLength = 0;
205 while (pIn > pAnchor && pMatch > pBase && pIn[-1] == pMatch[-1]) {
256 U64 lastHash,
const BYTE* lastHashed,
260 U64 rollingHash = lastHash;
261 const BYTE*
cur = lastHashed + 1;
296 U32 const minMatchLength =
params->minMatchLength;
299 U32 const ldmBucketSize = 1
U <<
params->bucketSizeLog;
300 U32 const hashEveryLog =
params->hashEveryLog;
301 U32 const ldmTagMask = (1
U <<
params->hashEveryLog) - 1;
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;
312 BYTE const*
const iend = istart + srcSize;
315 BYTE const* anchor = istart;
321 while (
ip <= ilimit) {
324 size_t forwardMatchLength = 0, backwardMatchLength = 0;
328 lastHashed[minMatchLength],
348 size_t bestMatchLength = 0;
351 for (
cur = bucket;
cur < bucket + ldmBucketSize; ++
cur) {
352 size_t curForwardMatchLength, curBackwardMatchLength,
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;
368 matchEnd, lowPrefixPtr);
369 if (curForwardMatchLength < minMatchLength) {
372 curBackwardMatchLength =
375 curTotalMatchLength = curForwardMatchLength +
376 curBackwardMatchLength;
380 if (curForwardMatchLength < minMatchLength) {
383 curBackwardMatchLength =
386 curTotalMatchLength = curForwardMatchLength +
387 curBackwardMatchLength;
390 if (curTotalMatchLength > bestMatchLength) {
391 bestMatchLength = curTotalMatchLength;
392 forwardMatchLength = curForwardMatchLength;
393 backwardMatchLength = curBackwardMatchLength;
400 if (bestEntry ==
NULL) {
409 mLength = forwardMatchLength + backwardMatchLength;
410 ip -= backwardMatchLength;
417 U32 const matchIndex = bestEntry->
offset;
423 return ERROR(dstSize_tooSmall);
435 assert(
ip + backwardMatchLength == lastHashed);
439 if (
ip + mLength <= ilimit) {
441 ldmState, rollingHash, lastHashed,
443 lastHashed =
ip + mLength - 1;
448 return iend - anchor;
454 U32 const reducerValue)
459 else table[
u].offset -= reducerValue;
469 BYTE const*
const iend = istart + srcSize;
470 size_t const kMaxChunkSize = 1 << 20;
471 size_t const nbChunks = (srcSize / kMaxChunkSize) + ((srcSize % kMaxChunkSize) != 0);
473 size_t leftoverSize = 0;
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;
494 assert(chunkStart < iend);
515 return newLeftoverSize;
521 if (prevSize < sequences->
size) {
522 sequences->seq[prevSize].litLength += (
U32)leftoverSize;
523 leftoverSize = newLeftoverSize;
525 assert(newLeftoverSize == chunkSize);
526 leftoverSize += chunkSize;
533 while (srcSize > 0 && rawSeqStore->
pos < rawSeqStore->
size) {
535 if (srcSize <= seq->litLength) {
542 if (srcSize < seq->matchLength) {
547 if (rawSeqStore->
pos + 1 < rawSeqStore->
size) {
568 U32 const remaining,
U32 const minMatch)
578 if (remaining <=
sequence.litLength) {
582 if (
sequence.matchLength < minMatch) {
593 void const*
src,
size_t srcSize)
595 const ZSTD_compressionParameters*
const cParams = &ms->
cParams;
596 unsigned const minMatch = cParams->searchLength;
601 BYTE const*
const iend = istart + srcSize;
605 DEBUGLOG(5,
"ZSTD_ldm_blockCompress: srcSize=%zu", srcSize);
609 while (rawSeqStore->
pos < rawSeqStore->
size &&
ip < iend) {
612 (
U32)(iend -
ip), minMatch);
625 DEBUGLOG(5,
"calling block compressor on segment of size %u",
sequence.litLength);
627 size_t const newLitLength =
628 blockCompressor(ms, seqStore, rep,
ip,
sequence.litLength);
645 return blockCompressor(ms, seqStore, rep,
ip, iend -
ip);
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
static U64 ZSTD_ldm_getRollingHash(const BYTE *buf, U32 len)
void ZSTD_fillHashTable(ZSTD_matchState_t *ms, void const *end, ZSTD_dictTableLoadMethod_e dtlm)
void ZSTD_ldm_adjustParameters(ldmParams_t *params, ZSTD_compressionParameters const *cParams)
MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
static ldmEntry_t * ZSTD_ldm_getBucket(ldmState_t *ldmState, size_t hash, ldmParams_t const ldmParams)
U64 ZSTD_ldm_getHashPower(U32 minMatchLength)
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)
static void ZSTD_ldm_reduceTable(ldmEntry_t *const table, U32 const size, U32 const reducerValue)
#define LDM_MIN_MATCH_LENGTH
#define ZSTD_STATIC_ASSERT(c)
GLenum GLuint GLenum GLsizei const GLchar * buf
size_t ZSTD_ldm_getMaxNbSeq(ldmParams_t params, size_t maxChunkSize)
GLenum const GLfloat * params
ZSTD_compressionParameters cParams
ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode)
static U32 ZSTD_ldm_getChecksum(U64 hash, U32 numBitsToDiscard)
static size_t ZSTD_ldm_generateSequences_internal(ldmState_t *ldmState, rawSeqStore_t *rawSeqStore, ldmParams_t const *params, void const *src, size_t srcSize)
MEM_STATIC size_t ZSTD_count(const BYTE *pIn, const BYTE *pMatch, const BYTE *const pInLimit)
MEM_STATIC void ZSTD_window_enforceMaxDist(ZSTD_window_t *window, void const *srcEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
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)
MEM_STATIC void ZSTD_storeSeq(seqStore_t *seqStorePtr, size_t litLength, const void *literals, U32 offsetCode, size_t mlBase)
static const U64 prime8bytes
static U32 ZSTD_ldm_getTag(U64 hash, U32 hbits, U32 numTagBits)
static U64 ZSTD_ldm_ipow(U64 base, U64 exp)
size_t ZSTD_ldm_getTableSize(ldmParams_t params)
static void ZSTD_ldm_insertEntry(ldmState_t *ldmState, size_t const hash, const ldmEntry_t entry, ldmParams_t const ldmParams)
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)
static struct message * sequence
static cab_ULONG checksum(const cab_UBYTE *data, cab_UWORD bytes, cab_ULONG csum)
static rawSeq maybeSplitSequence(rawSeqStore_t *rawSeqStore, U32 const remaining, U32 const minMatch)
void ZSTD_fillDoubleHashTable(ZSTD_matchState_t *ms, void const *end, ZSTD_dictTableLoadMethod_e dtlm)
static U64 ZSTD_ldm_updateHash(U64 hash, BYTE toRemove, BYTE toAdd, U64 hashPower)
#define LDM_BUCKET_SIZE_LOG
MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t *window, U32 cycleLog, U32 maxDist, void const *src)
static void ZSTD_ldm_limitTableUpdate(ZSTD_matchState_t *ms, const BYTE *anchor)
static size_t ZSTD_ldm_fillFastTables(ZSTD_matchState_t *ms, void const *end)
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
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)
#define ZSTD_CHUNKSIZE_MAX
#define LDM_HASH_CHAR_OFFSET
size_t ZSTD_ldm_generateSequences(ldmState_t *ldmState, rawSeqStore_t *sequences, ldmParams_t const *params, void const *src, size_t srcSize)
static U32 ZSTD_ldm_getSmallHash(U64 value, U32 numBits)
void ZSTD_ldm_skipSequences(rawSeqStore_t *rawSeqStore, size_t srcSize, U32 const minMatch)
struct task_struct * current
static size_t ZSTD_ldm_countBackwardsMatch(const BYTE *pIn, const BYTE *pAnchor, const BYTE *pMatch, const BYTE *pBase)