mercurial: comparison contrib/python-zstandard/zstd/compress/zstd_compress

equal deleted inserted replaced

-:2da754532dd3
+:69de49c4e39c
 /*-*************************************
 *  Constants
 ***************************************/
 #define kSearchStrength      8
 #define HASH_READ_SIZE       8
-#define ZSTD_DUBT_UNSORTED_MARK 1   /* For btlazy2 strategy, index 1 now means "unsorted".
+#define ZSTD_DUBT_UNSORTED_MARK 1   /* For btlazy2 strategy, index ZSTD_DUBT_UNSORTED_MARK==1 means "unsorted".
 It could be confused for a real successor at index "1", if sorted as larger than its predecessor.
 It's not a big deal though : candidate will just be sorted again.
-Additionnally, candidate position 1 will be lost.
+Additionally, candidate position 1 will be lost.
 But candidate 1 cannot hide a large tree of candidates, so it's a minimal loss.
-The benefit is that ZSTD_DUBT_UNSORTED_MARK cannot be misdhandled after table re-use with a different strategy
+The benefit is that ZSTD_DUBT_UNSORTED_MARK cannot be mishandled after table re-use with a different strategy.
-Constant required by ZSTD_compressBlock_btlazy2() and ZSTD_reduceTable_internal() */
+This constant is required by ZSTD_compressBlock_btlazy2() and ZSTD_reduceTable_internal() */
 /*-*************************************
 *  Context memory management
 ***************************************/
 typedef struct ZSTD_prefixDict_s {
 const void* dict;
 size_t dictSize;
 ZSTD_dictContentType_e dictContentType;
 } ZSTD_prefixDict;
+typedef struct {
+void* dictBuffer;
+void const* dict;
+size_t dictSize;
+ZSTD_dictContentType_e dictContentType;
+ZSTD_CDict* cdict;
+} ZSTD_localDict;
 typedef struct {
 U32 CTable[HUF_CTABLE_SIZE_U32(255)];
 HUF_repeat repeatMode;
 } ZSTD_hufCTables_t;
 U32  litLengthSumBasePrice;  /* to compare to log2(llfreq)  */
 U32  matchLengthSumBasePrice;/* to compare to log2(mlfreq)  */
 U32  offCodeSumBasePrice;    /* to compare to log2(offreq)  */
 ZSTD_OptPrice_e priceType;   /* prices can be determined dynamically, or follow a pre-defined cost structure */
 const ZSTD_entropyCTables_t* symbolCosts;  /* pre-calculated dictionary statistics */
+ZSTD_literalCompressionMode_e literalCompressionMode;
 } optState_t;
 typedef struct {
 ZSTD_entropyCTables_t entropy;
 U32 rep[ZSTD_REP_NUM];
 typedef struct {
 BYTE const* nextSrc;    /* next block here to continue on current prefix */
 BYTE const* base;       /* All regular indexes relative to this position */
 BYTE const* dictBase;   /* extDict indexes relative to this position */
 U32 dictLimit;          /* below that point, need extDict */
-U32 lowLimit;           /* below that point, no more data */
+U32 lowLimit;           /* below that point, no more valid data */
 } ZSTD_window_t;
 typedef struct ZSTD_matchState_t ZSTD_matchState_t;
 struct ZSTD_matchState_t {
 ZSTD_window_t window;   /* State for window round buffer management */
-U32 loadedDictEnd;      /* index of end of dictionary */
+U32 loadedDictEnd;      /* index of end of dictionary, within context's referential.
+* When loadedDictEnd != 0, a dictionary is in use, and still valid.
+* This relies on a mechanism to set loadedDictEnd=0 when dictionary is no longer within distance.
+* Such mechanism is provided within ZSTD_window_enforceMaxDist() and ZSTD_checkDictValidity().
+* When dict referential is copied into active context (i.e. not attached),
+* loadedDictEnd == dictSize, since referential starts from zero.
+*/
 U32 nextToUpdate;       /* index from which to continue table update */
-U32 nextToUpdate3;      /* index from which to continue table update */
+U32 hashLog3;           /* dispatch table for matches of len==3 : larger == faster, more memory */
-U32 hashLog3;           /* dispatch table : larger == faster, more memory */
 U32* hashTable;
 U32* hashTable3;
 U32* chainTable;
 optState_t opt;         /* optimal parser state */
-const ZSTD_matchState_t * dictMatchState;
+const ZSTD_matchState_t* dictMatchState;
 ZSTD_compressionParameters cParams;
 };
 typedef struct {
 ZSTD_compressedBlockState_t* prevCBlock;
 ZSTD_frameParameters fParams;
 int compressionLevel;
 int forceWindow;           /* force back-references to respect limit of
 * 1<<wLog, even for dictionary */
+size_t targetCBlockSize;   /* Tries to fit compressed block size to be around targetCBlockSize.
+* No target when targetCBlockSize == 0.
+* There is no guarantee on compressed block size */
 ZSTD_dictAttachPref_e attachDictPref;
+ZSTD_literalCompressionMode_e literalCompressionMode;
 /* Multithreading: used to pass parameters to mtctx */
 int nbWorkers;
 size_t jobSize;
 int overlapLog;
 size_t outBuffFlushedSize;
 ZSTD_cStreamStage streamStage;
 U32    frameEnded;
 /* Dictionary */
-ZSTD_CDict* cdictLocal;
+ZSTD_localDict localDict;
 const ZSTD_CDict* cdict;
 ZSTD_prefixDict prefixDict;   /* single-usage dictionary */
 /* Multi-threading */
 #ifdef ZSTD_MULTITHREAD
 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
 static const U32 ML_deltaCode = 36;
 return (mlBase > 127) ? ZSTD_highbit32(mlBase) + ML_deltaCode : ML_Code[mlBase];
+}
+/* ZSTD_cParam_withinBounds:
+* @return 1 if value is within cParam bounds,
+* 0 otherwise */
+MEM_STATIC int ZSTD_cParam_withinBounds(ZSTD_cParameter cParam, int value)
+{
+ZSTD_bounds const bounds = ZSTD_cParam_getBounds(cParam);
+if (ZSTD_isError(bounds.error)) return 0;
+if (value < bounds.lowerBound) return 0;
+if (value > bounds.upperBound) return 0;
+return 1;
+}
+/* ZSTD_minGain() :
+* minimum compression required
+* to generate a compress block or a compressed literals section.
+* note : use same formula for both situations */
+MEM_STATIC size_t ZSTD_minGain(size_t srcSize, ZSTD_strategy strat)
+{
+U32 const minlog = (strat>=ZSTD_btultra) ? (U32)(strat) - 1 : 6;
+ZSTD_STATIC_ASSERT(ZSTD_btultra == 8);
+assert(ZSTD_cParam_withinBounds(ZSTD_c_strategy, strat));
+return (srcSize >> minlog) + 2;
 }
 /*! ZSTD_storeSeq() :
 *  Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
 *  `offsetCode` : distance to match + 3 (values 1-3 are repCodes).
 #endif
 assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq);
 /* copy Literals */
 assert(seqStorePtr->maxNbLit <= 128 KB);
 assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + seqStorePtr->maxNbLit);
-ZSTD_wildcopy(seqStorePtr->lit, literals, litLength);
+ZSTD_wildcopy(seqStorePtr->lit, literals, (ptrdiff_t)litLength, ZSTD_no_overlap);
 seqStorePtr->lit += litLength;
 /* literal Length */
 if (litLength>0xFFFF) {
 assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
 }
 /*-*************************************
 *  Round buffer management
 ***************************************/
+#if (ZSTD_WINDOWLOG_MAX_64 > 31)
+# error "ZSTD_WINDOWLOG_MAX is too large : would overflow ZSTD_CURRENT_MAX"
+#endif
 /* Max current allowed */
 #define ZSTD_CURRENT_MAX ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX))
 /* Maximum chunk size before overflow correction needs to be called again */
 #define ZSTD_CHUNKSIZE_MAX                                                     \
 ( ((U32)-1)                  /* Maximum ending current index */            \
 /**
 * ZSTD_window_enforceMaxDist():
 * Updates lowLimit so that:
 *    (srcEnd - base) - lowLimit == maxDist + loadedDictEnd
 *
-* This allows a simple check that index >= lowLimit to see if index is valid.
+* It ensures index is valid as long as index >= lowLimit.
-* This must be called before a block compression call, with srcEnd as the block
+* This must be called before a block compression call.
-* source end.
 *
-* If loadedDictEndPtr is not NULL, we set it to zero once we update lowLimit.
+* loadedDictEnd is only defined if a dictionary is in use for current compression.
-* This is because dictionaries are allowed to be referenced as long as the last
+* As the name implies, loadedDictEnd represents the index at end of dictionary.
-* byte of the dictionary is in the window, but once they are out of range,
+* The value lies within context's referential, it can be directly compared to blockEndIdx.
-* they cannot be referenced. If loadedDictEndPtr is NULL, we use
-* loadedDictEnd == 0.
 *
-* In normal dict mode, the dict is between lowLimit and dictLimit. In
+* If loadedDictEndPtr is NULL, no dictionary is in use, and we use loadedDictEnd == 0.
-* dictMatchState mode, lowLimit and dictLimit are the same, and the dictionary
+* If loadedDictEndPtr is not NULL, we set it to zero after updating lowLimit.
-* is below them. forceWindow and dictMatchState are therefore incompatible.
+* This is because dictionaries are allowed to be referenced fully
+* as long as the last byte of the dictionary is in the window.
+* Once input has progressed beyond window size, dictionary cannot be referenced anymore.
+*
+* In normal dict mode, the dictionary lies between lowLimit and dictLimit.
+* In dictMatchState mode, lowLimit and dictLimit are the same,
+* and the dictionary is below them.
+* forceWindow and dictMatchState are therefore incompatible.
 */
 MEM_STATIC void
 ZSTD_window_enforceMaxDist(ZSTD_window_t* window,
-void const* srcEnd,
+const void* blockEnd,
-U32 maxDist,
+U32   maxDist,
-U32* loadedDictEndPtr,
+U32*  loadedDictEndPtr,
 const ZSTD_matchState_t** dictMatchStatePtr)
 {
-U32 const blockEndIdx = (U32)((BYTE const*)srcEnd - window->base);
+U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
-U32 loadedDictEnd = (loadedDictEndPtr != NULL) ? *loadedDictEndPtr : 0;
+U32 const loadedDictEnd = (loadedDictEndPtr != NULL) ? *loadedDictEndPtr : 0;
-DEBUGLOG(5, "ZSTD_window_enforceMaxDist: blockEndIdx=%u, maxDist=%u",
+DEBUGLOG(5, "ZSTD_window_enforceMaxDist: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
-(unsigned)blockEndIdx, (unsigned)maxDist);
+(unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd);
+/* - When there is no dictionary : loadedDictEnd == 0.
+In which case, the test (blockEndIdx > maxDist) is merely to avoid
+overflowing next operation `newLowLimit = blockEndIdx - maxDist`.
+- When there is a standard dictionary :
+Index referential is copied from the dictionary,
+which means it starts from 0.
+In which case, loadedDictEnd == dictSize,
+and it makes sense to compare `blockEndIdx > maxDist + dictSize`
+since `blockEndIdx` also starts from zero.
+- When there is an attached dictionary :
+loadedDictEnd is expressed within the referential of the context,
+so it can be directly compared against blockEndIdx.
+*/
 if (blockEndIdx > maxDist + loadedDictEnd) {
 U32 const newLowLimit = blockEndIdx - maxDist;
 if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit;
 if (window->dictLimit < window->lowLimit) {
 DEBUGLOG(5, "Update dictLimit to match lowLimit, from %u to %u",
 (unsigned)window->dictLimit, (unsigned)window->lowLimit);
 window->dictLimit = window->lowLimit;
 }
-if (loadedDictEndPtr)
+/* On reaching window size, dictionaries are invalidated */
+if (loadedDictEndPtr) *loadedDictEndPtr = 0;
+if (dictMatchStatePtr) *dictMatchStatePtr = NULL;
+}
+}
+/* Similar to ZSTD_window_enforceMaxDist(),
+* but only invalidates dictionary
+* when input progresses beyond window size.
+* assumption : loadedDictEndPtr and dictMatchStatePtr are valid (non NULL)
+*              loadedDictEnd uses same referential as window->base
+*              maxDist is the window size */
+MEM_STATIC void
+ZSTD_checkDictValidity(const ZSTD_window_t* window,
+const void* blockEnd,
+U32   maxDist,
+U32*  loadedDictEndPtr,
+const ZSTD_matchState_t** dictMatchStatePtr)
+{
+assert(loadedDictEndPtr != NULL);
+assert(dictMatchStatePtr != NULL);
+{   U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
+U32 const loadedDictEnd = *loadedDictEndPtr;
+DEBUGLOG(5, "ZSTD_checkDictValidity: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
+(unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd);
+assert(blockEndIdx >= loadedDictEnd);
+if (blockEndIdx > loadedDictEnd + maxDist) {
+/* On reaching window size, dictionaries are invalidated.
+* For simplification, if window size is reached anywhere within next block,
+* the dictionary is invalidated for the full block.
+*/
+DEBUGLOG(6, "invalidating dictionary for current block (distance > windowSize)");
 *loadedDictEndPtr = 0;
-if (dictMatchStatePtr)
 *dictMatchStatePtr = NULL;
-}
+} else {
+if (*loadedDictEndPtr != 0) {
+DEBUGLOG(6, "dictionary considered valid for current block");
+}   }   }
 }
 /**
 * ZSTD_window_update():
 * Updates the window by appending [src, src + srcSize) to the window.
 DEBUGLOG(5, "Overlapping extDict and input : new lowLimit = %u", window->lowLimit);
 }
 return contiguous;
 }
+MEM_STATIC U32 ZSTD_getLowestMatchIndex(const ZSTD_matchState_t* ms, U32 current, unsigned windowLog)
+{
+U32    const maxDistance = 1U << windowLog;
+U32    const lowestValid = ms->window.lowLimit;
+U32    const withinWindow = (current - lowestValid > maxDistance) ? current - maxDistance : lowestValid;
+U32    const isDictionary = (ms->loadedDictEnd != 0);
+U32    const matchLowest = isDictionary ? lowestValid : withinWindow;
+return matchLowest;
+}
 /* debug functions */
 #if (DEBUGLEVEL>=2)
 MEM_STATIC double ZSTD_fWeight(U32 rawStat)
 const ZSTD_CDict* cdict,
 ZSTD_CCtx_params  params, unsigned long long pledgedSrcSize);
 void ZSTD_resetSeqStore(seqStore_t* ssPtr);
-/*! ZSTD_compressStream_generic() :
-*  Private use only. To be called from zstdmt_compress.c in single-thread mode. */
-size_t ZSTD_compressStream_generic(ZSTD_CStream* zcs,
-ZSTD_outBuffer* output,
-ZSTD_inBuffer* input,
-ZSTD_EndDirective const flushMode);
 /*! ZSTD_getCParamsFromCDict() :
 *  as the name implies */
 ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict);
 /* ZSTD_compressBegin_advanced_internal() :
 /* ZSTD_writeLastEmptyBlock() :
 * output an empty Block with end-of-frame mark to complete a frame
 * @return : size of data written into `dst` (== ZSTD_blockHeaderSize (defined in zstd_internal.h))
-*           or an error code if `dstCapcity` is too small (<ZSTD_blockHeaderSize)
+*           or an error code if `dstCapacity` is too small (<ZSTD_blockHeaderSize)
 */
 size_t ZSTD_writeLastEmptyBlock(void* dst, size_t dstCapacity);
 /* ZSTD_referenceExternalSequences() :

changeset 42937	69de49c4e39c
parent 42070	675775c33ab6
child 43994	de7838053207