OSCL-LXR linux-6.0.1/​lib/​zstd/​compress/​zstd_ldm.c	Source navigation Diff markup Identifier search General search
	Version: linux-6.0.1 spark-3.0.0 hadoop-3.2.0-src hadoop-3.3.0-src spark-2.4.7 linux-4.15.13 hadoop-2.7.4-src Revert   Change

 /*
  * Copyright (c) Yann Collet, Facebook, Inc.
  * All rights reserved.
  *
  * This source code is licensed under both the BSD-style license (found in the
  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
  * in the COPYING file in the root directory of this source tree).
  * You may select, at your option, one of the above-listed licenses.
  */
 
 #include "zstd_ldm.h"
 
 #include "../common/debug.h"
 #include <linux/xxhash.h>
 #include "zstd_fast.h"          /* ZSTD_fillHashTable() */
 #include "zstd_double_fast.h"   /* ZSTD_fillDoubleHashTable() */
 #include "zstd_ldm_geartab.h"
 
 #define LDM_BUCKET_SIZE_LOG 3
 #define LDM_MIN_MATCH_LENGTH 64
 #define LDM_HASH_RLOG 7
 
 typedef struct {
     U64 rolling;
     U64 stopMask;
 } ldmRollingHashState_t;
 
 /* ZSTD_ldm_gear_init():
  *
  * Initializes the rolling hash state such that it will honor the
  * settings in params. */
 static void ZSTD_ldm_gear_init(ldmRollingHashState_t* state, ldmParams_t const* params)
 {
     unsigned maxBitsInMask = MIN(params->minMatchLength, 64);
     unsigned hashRateLog = params->hashRateLog;
 
     state->rolling = ~(U32)0;
 
     /* The choice of the splitting criterion is subject to two conditions:
      *   1. it has to trigger on average every 2^(hashRateLog) bytes;
      *   2. ideally, it has to depend on a window of minMatchLength bytes.
      *
      * In the gear hash algorithm, bit n depends on the last n bytes;
      * so in order to obtain a good quality splitting criterion it is
      * preferable to use bits with high weight.
      *
      * To match condition 1 we use a mask with hashRateLog bits set
      * and, because of the previous remark, we make sure these bits
      * have the highest possible weight while still respecting
      * condition 2.
      */
     if (hashRateLog > 0 && hashRateLog <= maxBitsInMask) {
         state->stopMask = (((U64)1 << hashRateLog) - 1) << (maxBitsInMask - hashRateLog);
     } else {
         /* In this degenerate case we simply honor the hash rate. */
         state->stopMask = ((U64)1 << hashRateLog) - 1;
     }
 }
 
 /* ZSTD_ldm_gear_feed():
  *
  * Registers in the splits array all the split points found in the first
  * size bytes following the data pointer. This function terminates when
  * either all the data has been processed or LDM_BATCH_SIZE splits are
  * present in the splits array.
  *
  * Precondition: The splits array must not be full.
  * Returns: The number of bytes processed. */
 static size_t ZSTD_ldm_gear_feed(ldmRollingHashState_t* state,
                                  BYTE const* data, size_t size,
                                  size_t* splits, unsigned* numSplits)
 {
     size_t n;
     U64 hash, mask;
 
     hash = state->rolling;
     mask = state->stopMask;
     n = 0;
 
 #define GEAR_ITER_ONCE() do { \
         hash = (hash << 1) + ZSTD_ldm_gearTab[data[n] & 0xff]; \
         n += 1; \
         if (UNLIKELY((hash & mask) == 0)) { \
             splits[*numSplits] = n; \
             *numSplits += 1; \
             if (*numSplits == LDM_BATCH_SIZE) \
                 goto done; \
         } \
     } while (0)
 
     while (n + 3 < size) {
         GEAR_ITER_ONCE();
         GEAR_ITER_ONCE();
         GEAR_ITER_ONCE();
         GEAR_ITER_ONCE();
     }
     while (n < size) {
         GEAR_ITER_ONCE();
     }
 
 #undef GEAR_ITER_ONCE
 
 done:
     state->rolling = hash;
     return n;
 }
 
 void ZSTD_ldm_adjustParameters(ldmParams_t* params,
                                ZSTD_compressionParameters const* cParams)
 {
     params->windowLog = cParams->windowLog;
     ZSTD_STATIC_ASSERT(LDM_BUCKET_SIZE_LOG <= ZSTD_LDM_BUCKETSIZELOG_MAX);
     DEBUGLOG(4, "ZSTD_ldm_adjustParameters");
     if (!params->bucketSizeLog) params->bucketSizeLog = LDM_BUCKET_SIZE_LOG;
     if (!params->minMatchLength) params->minMatchLength = LDM_MIN_MATCH_LENGTH;
     if (params->hashLog == 0) {
         params->hashLog = MAX(ZSTD_HASHLOG_MIN, params->windowLog - LDM_HASH_RLOG);
         assert(params->hashLog <= ZSTD_HASHLOG_MAX);
     }
     if (params->hashRateLog == 0) {
         params->hashRateLog = params->windowLog < params->hashLog
                                    ? 0
                                    : params->windowLog - params->hashLog;
     }
     params->bucketSizeLog = MIN(params->bucketSizeLog, params->hashLog);
 }
 
 size_t ZSTD_ldm_getTableSize(ldmParams_t params)
 {
     size_t const ldmHSize = ((size_t)1) << params.hashLog;
     size_t const ldmBucketSizeLog = MIN(params.bucketSizeLog, params.hashLog);
     size_t const ldmBucketSize = ((size_t)1) << (params.hashLog - ldmBucketSizeLog);
     size_t const totalSize = ZSTD_cwksp_alloc_size(ldmBucketSize)
                            + ZSTD_cwksp_alloc_size(ldmHSize * sizeof(ldmEntry_t));
     return params.enableLdm ? totalSize : 0;
 }
 
 size_t ZSTD_ldm_getMaxNbSeq(ldmParams_t params, size_t maxChunkSize)
 {
     return params.enableLdm ? (maxChunkSize / params.minMatchLength) : 0;
 }
 
 /* ZSTD_ldm_getBucket() :
  *  Returns a pointer to the start of the bucket associated with hash. */
 static ldmEntry_t* ZSTD_ldm_getBucket(
         ldmState_t* ldmState, size_t hash, ldmParams_t const ldmParams)
 {
     return ldmState->hashTable + (hash << ldmParams.bucketSizeLog);
 }
 
 /* ZSTD_ldm_insertEntry() :
  *  Insert the entry with corresponding hash into the hash table */
 static void ZSTD_ldm_insertEntry(ldmState_t* ldmState,
                                  size_t const hash, const ldmEntry_t entry,
                                  ldmParams_t const ldmParams)
 {
     BYTE* const pOffset = ldmState->bucketOffsets + hash;
     unsigned const offset = *pOffset;
 
     *(ZSTD_ldm_getBucket(ldmState, hash, ldmParams) + offset) = entry;
     *pOffset = (BYTE)((offset + 1) & ((1u << ldmParams.bucketSizeLog) - 1));
 
 }
 
 /* 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. */
 static size_t ZSTD_ldm_countBackwardsMatch(
             const BYTE* pIn, const BYTE* pAnchor,
             const BYTE* pMatch, const BYTE* pMatchBase)
 {
     size_t matchLength = 0;
     while (pIn > pAnchor && pMatch > pMatchBase && pIn[-1] == pMatch[-1]) {
         pIn--;
         pMatch--;
         matchLength++;
     }
     return matchLength;
 }
 
 /* ZSTD_ldm_countBackwardsMatch_2segments() :
  *  Returns the number of bytes that match backwards from pMatch,
  *  even with the backwards match spanning 2 different segments.
  *
  *  On reaching `pMatchBase`, start counting from mEnd */
 static size_t ZSTD_ldm_countBackwardsMatch_2segments(
                     const BYTE* pIn, const BYTE* pAnchor,
                     const BYTE* pMatch, const BYTE* pMatchBase,
                     const BYTE* pExtDictStart, const BYTE* pExtDictEnd)
 {
     size_t matchLength = ZSTD_ldm_countBackwardsMatch(pIn, pAnchor, pMatch, pMatchBase);
     if (pMatch - matchLength != pMatchBase || pMatchBase == pExtDictStart) {
         /* If backwards match is entirely in the extDict or prefix, immediately return */
         return matchLength;
     }
     DEBUGLOG(7, "ZSTD_ldm_countBackwardsMatch_2segments: found 2-parts backwards match (length in prefix==%zu)", matchLength);
     matchLength += ZSTD_ldm_countBackwardsMatch(pIn - matchLength, pAnchor, pExtDictEnd, pExtDictStart);
     DEBUGLOG(7, "final backwards match length = %zu", matchLength);
     return matchLength;
 }
 
 /* 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. */
 static size_t ZSTD_ldm_fillFastTables(ZSTD_matchState_t* ms,
                                       void const* end)
 {
     const BYTE* const iend = (const BYTE*)end;
 
     switch(ms->cParams.strategy)
     {
     case ZSTD_fast:
         ZSTD_fillHashTable(ms, iend, ZSTD_dtlm_fast);
         break;
 
     case ZSTD_dfast:
         ZSTD_fillDoubleHashTable(ms, iend, ZSTD_dtlm_fast);
         break;
 
     case ZSTD_greedy:
     case ZSTD_lazy:
     case ZSTD_lazy2:
     case ZSTD_btlazy2:
     case ZSTD_btopt:
     case ZSTD_btultra:
     case ZSTD_btultra2:
         break;
     default:
         assert(0);  /* not possible : not a valid strategy id */
     }
 
     return 0;
 }
 
 void ZSTD_ldm_fillHashTable(
             ldmState_t* ldmState, const BYTE* ip,
             const BYTE* iend, ldmParams_t const* params)
 {
     U32 const minMatchLength = params->minMatchLength;
     U32 const hBits = params->hashLog - params->bucketSizeLog;
     BYTE const* const base = ldmState->window.base;
     BYTE const* const istart = ip;
     ldmRollingHashState_t hashState;
     size_t* const splits = ldmState->splitIndices;
     unsigned numSplits;
 
     DEBUGLOG(5, "ZSTD_ldm_fillHashTable");
 
     ZSTD_ldm_gear_init(&hashState, params);
     while (ip < iend) {
         size_t hashed;
         unsigned n;
         
         numSplits = 0;
         hashed = ZSTD_ldm_gear_feed(&hashState, ip, iend - ip, splits, &numSplits);
 
         for (n = 0; n < numSplits; n++) {
             if (ip + splits[n] >= istart + minMatchLength) {
                 BYTE const* const split = ip + splits[n] - minMatchLength;
                 U64 const xxhash = xxh64(split, minMatchLength, 0);
                 U32 const hash = (U32)(xxhash & (((U32)1 << hBits) - 1));
                 ldmEntry_t entry;
 
                 entry.offset = (U32)(split - base);
                 entry.checksum = (U32)(xxhash >> 32);
                 ZSTD_ldm_insertEntry(ldmState, hash, entry, *params);
             }
         }
 
         ip += hashed;
     }
 }
 
 
 /* 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). */
 static void ZSTD_ldm_limitTableUpdate(ZSTD_matchState_t* ms, const BYTE* anchor)
 {
     U32 const curr = (U32)(anchor - ms->window.base);
     if (curr > ms->nextToUpdate + 1024) {
         ms->nextToUpdate =
             curr - MIN(512, curr - ms->nextToUpdate - 1024);
     }
 }
 
 static size_t ZSTD_ldm_generateSequences_internal(
         ldmState_t* ldmState, rawSeqStore_t* rawSeqStore,
         ldmParams_t const* params, void const* src, size_t srcSize)
 {
     /* LDM parameters */
     int const extDict = ZSTD_window_hasExtDict(ldmState->window);
     U32 const minMatchLength = params->minMatchLength;
     U32 const entsPerBucket = 1U << params->bucketSizeLog;
     U32 const hBits = params->hashLog - params->bucketSizeLog;
     /* Prefix and extDict parameters */
     U32 const dictLimit = ldmState->window.dictLimit;
     U32 const lowestIndex = extDict ? ldmState->window.lowLimit : dictLimit;
     BYTE const* const base = ldmState->window.base;
     BYTE const* const dictBase = extDict ? ldmState->window.dictBase : NULL;
     BYTE const* const dictStart = extDict ? dictBase + lowestIndex : NULL;
     BYTE const* const dictEnd = extDict ? dictBase + dictLimit : NULL;
     BYTE const* const lowPrefixPtr = base + dictLimit;
     /* Input bounds */
     BYTE const* const istart = (BYTE const*)src;
     BYTE const* const iend = istart + srcSize;
     BYTE const* const ilimit = iend - HASH_READ_SIZE;
     /* Input positions */
     BYTE const* anchor = istart;
     BYTE const* ip = istart;
     /* Rolling hash state */
     ldmRollingHashState_t hashState;
     /* Arrays for staged-processing */
     size_t* const splits = ldmState->splitIndices;
     ldmMatchCandidate_t* const candidates = ldmState->matchCandidates;
     unsigned numSplits;
 
     if (srcSize < minMatchLength)
         return iend - anchor;
 
     /* Initialize the rolling hash state with the first minMatchLength bytes */
     ZSTD_ldm_gear_init(&hashState, params);
     {
         size_t n = 0;
 
         while (n < minMatchLength) {
             numSplits = 0;
             n += ZSTD_ldm_gear_feed(&hashState, ip + n, minMatchLength - n,
                                     splits, &numSplits);
         }
         ip += minMatchLength;
     }
 
     while (ip < ilimit) {
         size_t hashed;
         unsigned n;
 
         numSplits = 0;
         hashed = ZSTD_ldm_gear_feed(&hashState, ip, ilimit - ip,
                                     splits, &numSplits);
 
         for (n = 0; n < numSplits; n++) {
             BYTE const* const split = ip + splits[n] - minMatchLength;
             U64 const xxhash = xxh64(split, minMatchLength, 0);
             U32 const hash = (U32)(xxhash & (((U32)1 << hBits) - 1));
 
             candidates[n].split = split;
             candidates[n].hash = hash;
             candidates[n].checksum = (U32)(xxhash >> 32);
             candidates[n].bucket = ZSTD_ldm_getBucket(ldmState, hash, *params);
             PREFETCH_L1(candidates[n].bucket);
         }
 
         for (n = 0; n < numSplits; n++) {
             size_t forwardMatchLength = 0, backwardMatchLength = 0,
                    bestMatchLength = 0, mLength;
             BYTE const* const split = candidates[n].split;
             U32 const checksum = candidates[n].checksum;
             U32 const hash = candidates[n].hash;
             ldmEntry_t* const bucket = candidates[n].bucket;
             ldmEntry_t const* cur;
             ldmEntry_t const* bestEntry = NULL;
             ldmEntry_t newEntry;
 
             newEntry.offset = (U32)(split - base);
             newEntry.checksum = checksum;
 
             /* If a split point would generate a sequence overlapping with
              * the previous one, we merely register it in the hash table and
              * move on */
             if (split < anchor) {
                 ZSTD_ldm_insertEntry(ldmState, hash, newEntry, *params);
                 continue;
             }
 
             for (cur = bucket; cur < bucket + entsPerBucket; cur++) {
                 size_t curForwardMatchLength, curBackwardMatchLength,
                        curTotalMatchLength;
                 if (cur->checksum != checksum || cur->offset <= lowestIndex) {
                     continue;
                 }
                 if (extDict) {
                     BYTE const* const curMatchBase =
                         cur->offset < dictLimit ? dictBase : base;
                     BYTE const* const pMatch = curMatchBase + cur->offset;
                     BYTE const* const matchEnd =
                         cur->offset < dictLimit ? dictEnd : iend;
                     BYTE const* const lowMatchPtr =
                         cur->offset < dictLimit ? dictStart : lowPrefixPtr;
                     curForwardMatchLength =
                         ZSTD_count_2segments(split, pMatch, iend, matchEnd, lowPrefixPtr);
                     if (curForwardMatchLength < minMatchLength) {
                         continue;
                     }
                     curBackwardMatchLength = ZSTD_ldm_countBackwardsMatch_2segments(
                             split, anchor, pMatch, lowMatchPtr, dictStart, dictEnd);
                 } else { /* !extDict */
                     BYTE const* const pMatch = base + cur->offset;
                     curForwardMatchLength = ZSTD_count(split, pMatch, iend);
                     if (curForwardMatchLength < minMatchLength) {
                         continue;
                     }
                     curBackwardMatchLength =
                         ZSTD_ldm_countBackwardsMatch(split, anchor, pMatch, lowPrefixPtr);
                 }
                 curTotalMatchLength = curForwardMatchLength + curBackwardMatchLength;
 
                 if (curTotalMatchLength > bestMatchLength) {
                     bestMatchLength = curTotalMatchLength;
                     forwardMatchLength = curForwardMatchLength;
                     backwardMatchLength = curBackwardMatchLength;
                     bestEntry = cur;
                 }
             }
 
             /* No match found -- insert an entry into the hash table
              * and process the next candidate match */
             if (bestEntry == NULL) {
                 ZSTD_ldm_insertEntry(ldmState, hash, newEntry, *params);
                 continue;
             }
 
             /* Match found */
             mLength = forwardMatchLength + backwardMatchLength;
             {
                 U32 const offset = (U32)(split - base) - bestEntry->offset;
                 rawSeq* const seq = rawSeqStore->seq + rawSeqStore->size;
 
                 /* Out of sequence storage */
                 if (rawSeqStore->size == rawSeqStore->capacity)
                     return ERROR(dstSize_tooSmall);
                 seq->litLength = (U32)(split - backwardMatchLength - anchor);
                 seq->matchLength = (U32)mLength;
                 seq->offset = offset;
                 rawSeqStore->size++;
             }
 
             /* Insert the current entry into the hash table --- it must be
              * done after the previous block to avoid clobbering bestEntry */
             ZSTD_ldm_insertEntry(ldmState, hash, newEntry, *params);
 
             anchor = split + forwardMatchLength;
         }
 
         ip += hashed;
     }
 
     return iend - anchor;
 }
 
 /*! ZSTD_ldm_reduceTable() :
  *  reduce table indexes by `reducerValue` */
 static void ZSTD_ldm_reduceTable(ldmEntry_t* const table, U32 const size,
                                  U32 const reducerValue)
 {
     U32 u;
     for (u = 0; u < size; u++) {
         if (table[u].offset < reducerValue) table[u].offset = 0;
         else table[u].offset -= reducerValue;
     }
 }
 
 size_t ZSTD_ldm_generateSequences(
         ldmState_t* ldmState, rawSeqStore_t* sequences,
         ldmParams_t const* params, void const* src, size_t srcSize)
 {
     U32 const maxDist = 1U << params->windowLog;
     BYTE const* const istart = (BYTE const*)src;
     BYTE const* const iend = istart + srcSize;
     size_t const kMaxChunkSize = 1 << 20;
     size_t const nbChunks = (srcSize / kMaxChunkSize) + ((srcSize % kMaxChunkSize) != 0);
     size_t chunk;
     size_t leftoverSize = 0;
 
     assert(ZSTD_CHUNKSIZE_MAX >= kMaxChunkSize);
     /* Check that ZSTD_window_update() has been called for this chunk prior
      * to passing it to this function.
      */
     assert(ldmState->window.nextSrc >= (BYTE const*)src + srcSize);
     /* The input could be very large (in zstdmt), so it must be broken up into
      * chunks to enforce the maximum distance and handle overflow correction.
      */
     assert(sequences->pos <= sequences->size);
     assert(sequences->size <= sequences->capacity);
     for (chunk = 0; chunk < nbChunks && sequences->size < sequences->capacity; ++chunk) {
         BYTE const* const chunkStart = istart + chunk * kMaxChunkSize;
         size_t const remaining = (size_t)(iend - chunkStart);
         BYTE const *const chunkEnd =
             (remaining < kMaxChunkSize) ? iend : chunkStart + kMaxChunkSize;
         size_t const chunkSize = chunkEnd - chunkStart;
         size_t newLeftoverSize;
         size_t const prevSize = sequences->size;
 
         assert(chunkStart < iend);
         /* 1. Perform overflow correction if necessary. */
         if (ZSTD_window_needOverflowCorrection(ldmState->window, chunkEnd)) {
             U32 const ldmHSize = 1U << params->hashLog;
             U32 const correction = ZSTD_window_correctOverflow(
                 &ldmState->window, /* cycleLog */ 0, maxDist, chunkStart);
             ZSTD_ldm_reduceTable(ldmState->hashTable, ldmHSize, correction);
             /* invalidate dictionaries on overflow correction */
             ldmState->loadedDictEnd = 0;
         }
         /* 2. We enforce the maximum offset allowed.
          *
          * kMaxChunkSize should be small enough that we don't lose too much of
          * the window through early invalidation.
          * TODO: * Test the chunk size.
          *       * Try invalidation after the sequence generation and test the
          *         the offset against maxDist directly.
          *
          * NOTE: Because of dictionaries + sequence splitting we MUST make sure
          * that any offset used is valid at the END of the sequence, since it may
          * be split into two sequences. This condition holds when using
          * ZSTD_window_enforceMaxDist(), but if we move to checking offsets
          * against maxDist directly, we'll have to carefully handle that case.
          */
         ZSTD_window_enforceMaxDist(&ldmState->window, chunkEnd, maxDist, &ldmState->loadedDictEnd, NULL);
         /* 3. Generate the sequences for the chunk, and get newLeftoverSize. */
         newLeftoverSize = ZSTD_ldm_generateSequences_internal(
             ldmState, sequences, params, chunkStart, chunkSize);
         if (ZSTD_isError(newLeftoverSize))
             return newLeftoverSize;
         /* 4. We add the leftover literals from previous iterations to the first
          *    newly generated sequence, or add the `newLeftoverSize` if none are
          *    generated.
          */
         /* Prepend the leftover literals from the last call */
         if (prevSize < sequences->size) {
             sequences->seq[prevSize].litLength += (U32)leftoverSize;
             leftoverSize = newLeftoverSize;
         } else {
             assert(newLeftoverSize == chunkSize);
             leftoverSize += chunkSize;
         }
     }
     return 0;
 }
 
 void ZSTD_ldm_skipSequences(rawSeqStore_t* rawSeqStore, size_t srcSize, U32 const minMatch) {
     while (srcSize > 0 && rawSeqStore->pos < rawSeqStore->size) {
         rawSeq* seq = rawSeqStore->seq + rawSeqStore->pos;
         if (srcSize <= seq->litLength) {
             /* Skip past srcSize literals */
             seq->litLength -= (U32)srcSize;
             return;
         }
         srcSize -= seq->litLength;
         seq->litLength = 0;
         if (srcSize < seq->matchLength) {
             /* Skip past the first srcSize of the match */
             seq->matchLength -= (U32)srcSize;
             if (seq->matchLength < minMatch) {
                 /* The match is too short, omit it */
                 if (rawSeqStore->pos + 1 < rawSeqStore->size) {
                     seq[1].litLength += seq[0].matchLength;
                 }
                 rawSeqStore->pos++;
             }
             return;
         }
         srcSize -= seq->matchLength;
         seq->matchLength = 0;
         rawSeqStore->pos++;
     }
 }
 
 /*
  * 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.
  */
 static rawSeq maybeSplitSequence(rawSeqStore_t* rawSeqStore,
                                  U32 const remaining, U32 const minMatch)
 {
     rawSeq sequence = rawSeqStore->seq[rawSeqStore->pos];
     assert(sequence.offset > 0);
     /* Likely: No partial sequence */
     if (remaining >= sequence.litLength + sequence.matchLength) {
         rawSeqStore->pos++;
         return sequence;
     }
     /* Cut the sequence short (offset == 0 ==> rest is literals). */
     if (remaining <= sequence.litLength) {
         sequence.offset = 0;
     } else if (remaining < sequence.litLength + sequence.matchLength) {
         sequence.matchLength = remaining - sequence.litLength;
         if (sequence.matchLength < minMatch) {
             sequence.offset = 0;
         }
     }
     /* Skip past `remaining` bytes for the future sequences. */
     ZSTD_ldm_skipSequences(rawSeqStore, remaining, minMatch);
     return sequence;
 }
 
 void ZSTD_ldm_skipRawSeqStoreBytes(rawSeqStore_t* rawSeqStore, size_t nbBytes) {
     U32 currPos = (U32)(rawSeqStore->posInSequence + nbBytes);
     while (currPos && rawSeqStore->pos < rawSeqStore->size) {
         rawSeq currSeq = rawSeqStore->seq[rawSeqStore->pos];
         if (currPos >= currSeq.litLength + currSeq.matchLength) {
             currPos -= currSeq.litLength + currSeq.matchLength;
             rawSeqStore->pos++;
         } else {
             rawSeqStore->posInSequence = currPos;
             break;
         }
     }
     if (currPos == 0 || rawSeqStore->pos == rawSeqStore->size) {
         rawSeqStore->posInSequence = 0;
     }
 }
 
 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)
 {
     const ZSTD_compressionParameters* const cParams = &ms->cParams;
     unsigned const minMatch = cParams->minMatch;
     ZSTD_blockCompressor const blockCompressor =
         ZSTD_selectBlockCompressor(cParams->strategy, ZSTD_matchState_dictMode(ms));
     /* Input bounds */
     BYTE const* const istart = (BYTE const*)src;
     BYTE const* const iend = istart + srcSize;
     /* Input positions */
     BYTE const* ip = istart;
 
     DEBUGLOG(5, "ZSTD_ldm_blockCompress: srcSize=%zu", srcSize);
     /* If using opt parser, use LDMs only as candidates rather than always accepting them */
     if (cParams->strategy >= ZSTD_btopt) {
         size_t lastLLSize;
         ms->ldmSeqStore = rawSeqStore;
         lastLLSize = blockCompressor(ms, seqStore, rep, src, srcSize);
         ZSTD_ldm_skipRawSeqStoreBytes(rawSeqStore, srcSize);
         return lastLLSize;
     }
 
     assert(rawSeqStore->pos <= rawSeqStore->size);
     assert(rawSeqStore->size <= rawSeqStore->capacity);
     /* Loop through each sequence and apply the block compressor to the literals */
     while (rawSeqStore->pos < rawSeqStore->size && ip < iend) {
         /* maybeSplitSequence updates rawSeqStore->pos */
         rawSeq const sequence = maybeSplitSequence(rawSeqStore,
                                                    (U32)(iend - ip), minMatch);
         int i;
         /* End signal */
         if (sequence.offset == 0)
             break;
 
         assert(ip + sequence.litLength + sequence.matchLength <= iend);
 
         /* Fill tables for block compressor */
         ZSTD_ldm_limitTableUpdate(ms, ip);
         ZSTD_ldm_fillFastTables(ms, ip);
         /* Run the block compressor */
         DEBUGLOG(5, "pos %u : calling block compressor on segment of size %u", (unsigned)(ip-istart), sequence.litLength);
         {
             size_t const newLitLength =
                 blockCompressor(ms, seqStore, rep, ip, sequence.litLength);
             ip += sequence.litLength;
             /* Update the repcodes */
             for (i = ZSTD_REP_NUM - 1; i > 0; i--)
                 rep[i] = rep[i-1];
             rep[0] = sequence.offset;
             /* Store the sequence */
             ZSTD_storeSeq(seqStore, newLitLength, ip - newLitLength, iend,
                           sequence.offset + ZSTD_REP_MOVE,
                           sequence.matchLength - MINMATCH);
             ip += sequence.matchLength;
         }
     }
     /* Fill the tables for the block compressor */
     ZSTD_ldm_limitTableUpdate(ms, ip);
     ZSTD_ldm_fillFastTables(ms, ip);
     /* Compress the last literals */
     return blockCompressor(ms, seqStore, rep, ip, iend - ip);
 }

This page was automatically generated by the 2.1.0 LXR engine. The LXR team