zstd_compress_internal.h File Reference

#include "zstd_internal.h"
#include "zstd_cwksp.h"

Include dependency graph for zstd_compress_internal.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	ZSTD_prefixDict_s
struct	ZSTD_localDict
struct	ZSTD_hufCTables_t
struct	ZSTD_fseCTables_t
struct	ZSTD_entropyCTables_t
struct	ZSTD_match_t
struct	ZSTD_optimal_t
struct	optState_t
struct	ZSTD_compressedBlockState_t
struct	ZSTD_window_t
struct	ZSTD_matchState_t
struct	ZSTD_blockState_t
struct	ldmEntry_t
struct	ldmState_t
struct	ldmParams_t
struct	rawSeq
struct	rawSeqStore_t
struct	SeqCollector
struct	ZSTD_CCtx_params_s
struct	ZSTD_CCtx_s
struct	repcodes_s

Macros
#define	kSearchStrength   8
#define	HASH_READ_SIZE   8
#define	ZSTD_DUBT_UNSORTED_MARK
#define	ZSTD_ROLL_HASH_CHAR_OFFSET   10
#define	ZSTD_CURRENT_MAX   ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX))
#define	ZSTD_CHUNKSIZE_MAX

Typedefs
typedef struct ZSTD_prefixDict_s	ZSTD_prefixDict
typedef struct ZSTD_matchState_t	ZSTD_matchState_t
typedef size_t(*	ZSTD_blockCompressor) (ZSTD_matchState_t *bs, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
typedef struct repcodes_s	repcodes_t

Enumerations
enum	ZSTD_compressionStage_e { ZSTDcs_created =0 , ZSTDcs_init , ZSTDcs_ongoing , ZSTDcs_ending }
enum	ZSTD_cStreamStage { zcss_init =0 , zcss_load , zcss_flush }
enum	ZSTD_OptPrice_e { zop_dynamic =0 , zop_predef }
enum	ZSTD_dictTableLoadMethod_e { ZSTD_dtlm_fast , ZSTD_dtlm_full }
enum	ZSTD_dictMode_e { ZSTD_noDict = 0 , ZSTD_extDict = 1 , ZSTD_dictMatchState = 2 }

Functions
ZSTD_blockCompressor	ZSTD_selectBlockCompressor (ZSTD_strategy strat, ZSTD_dictMode_e dictMode)
MEM_STATIC U32	ZSTD_LLcode (U32 litLength)
MEM_STATIC U32	ZSTD_MLcode (U32 mlBase)
MEM_STATIC repcodes_t	ZSTD_updateRep (U32 const rep[3], U32 const offset, U32 const ll0)
MEM_STATIC int	ZSTD_cParam_withinBounds (ZSTD_cParameter cParam, int value)
MEM_STATIC size_t	ZSTD_noCompressBlock (void *dst, size_t dstCapacity, const void *src, size_t srcSize, U32 lastBlock)
MEM_STATIC size_t	ZSTD_rleCompressBlock (void *dst, size_t dstCapacity, BYTE src, size_t srcSize, U32 lastBlock)
MEM_STATIC size_t	ZSTD_minGain (size_t srcSize, ZSTD_strategy strat)
MEM_STATIC int	ZSTD_disableLiteralsCompression (const ZSTD_CCtx_params *cctxParams)
static void	ZSTD_safecopyLiterals (BYTE *op, BYTE const *ip, BYTE const *const iend, BYTE const *ilimit_w)
HINT_INLINE UNUSED_ATTR void	ZSTD_storeSeq (seqStore_t *seqStorePtr, size_t litLength, const BYTE *literals, const BYTE *litLimit, U32 offCode, size_t mlBase)
static unsigned	ZSTD_NbCommonBytes (size_t val)
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 U32	ZSTD_hash3 (U32 u, U32 h)
MEM_STATIC size_t	ZSTD_hash3Ptr (const void *ptr, U32 h)
static U32	ZSTD_hash4 (U32 u, U32 h)
static size_t	ZSTD_hash4Ptr (const void *ptr, U32 h)
static size_t	ZSTD_hash5 (U64 u, U32 h)
static size_t	ZSTD_hash5Ptr (const void *p, U32 h)
static size_t	ZSTD_hash6 (U64 u, U32 h)
static size_t	ZSTD_hash6Ptr (const void *p, U32 h)
static size_t	ZSTD_hash7 (U64 u, U32 h)
static size_t	ZSTD_hash7Ptr (const void *p, U32 h)
static size_t	ZSTD_hash8 (U64 u, U32 h)
static size_t	ZSTD_hash8Ptr (const void *p, U32 h)
MEM_STATIC size_t	ZSTD_hashPtr (const void *p, U32 hBits, U32 mls)
static U64	ZSTD_ipow (U64 base, U64 exponent)
static U64	ZSTD_rollingHash_append (U64 hash, void const *buf, size_t size)
MEM_STATIC U64	ZSTD_rollingHash_compute (void const *buf, size_t size)
MEM_STATIC U64	ZSTD_rollingHash_primePower (U32 length)
MEM_STATIC U64	ZSTD_rollingHash_rotate (U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower)
MEM_STATIC void	ZSTD_window_clear (ZSTD_window_t *window)
MEM_STATIC U32	ZSTD_window_hasExtDict (ZSTD_window_t const window)
MEM_STATIC ZSTD_dictMode_e	ZSTD_matchState_dictMode (const ZSTD_matchState_t *ms)
MEM_STATIC U32	ZSTD_window_needOverflowCorrection (ZSTD_window_t const window, void const *srcEnd)
MEM_STATIC U32	ZSTD_window_correctOverflow (ZSTD_window_t *window, U32 cycleLog, U32 maxDist, void const *src)
MEM_STATIC void	ZSTD_window_enforceMaxDist (ZSTD_window_t *window, const void *blockEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
MEM_STATIC void	ZSTD_checkDictValidity (const ZSTD_window_t *window, const void *blockEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
MEM_STATIC void	ZSTD_window_init (ZSTD_window_t *window)
MEM_STATIC U32	ZSTD_window_update (ZSTD_window_t *window, void const *src, size_t srcSize)
MEM_STATIC U32	ZSTD_getLowestMatchIndex (const ZSTD_matchState_t *ms, U32 current, unsigned windowLog)
MEM_STATIC U32	ZSTD_getLowestPrefixIndex (const ZSTD_matchState_t *ms, U32 current, unsigned windowLog)
size_t	ZSTD_loadCEntropy (ZSTD_compressedBlockState_t *bs, void *workspace, short *offcodeNCount, unsigned *offcodeMaxValue, const void *const dict, size_t dictSize)
void	ZSTD_reset_compressedBlockState (ZSTD_compressedBlockState_t *bs)
ZSTD_compressionParameters	ZSTD_getCParamsFromCCtxParams (const ZSTD_CCtx_params *CCtxParams, U64 srcSizeHint, size_t dictSize)
size_t	ZSTD_initCStream_internal (ZSTD_CStream *zcs, const void *dict, size_t dictSize, const ZSTD_CDict *cdict, const ZSTD_CCtx_params *params, unsigned long long pledgedSrcSize)
void	ZSTD_resetSeqStore (seqStore_t *ssPtr)
ZSTD_compressionParameters	ZSTD_getCParamsFromCDict (const ZSTD_CDict *cdict)
size_t	ZSTD_compressBegin_advanced_internal (ZSTD_CCtx *cctx, const void *dict, size_t dictSize, ZSTD_dictContentType_e dictContentType, ZSTD_dictTableLoadMethod_e dtlm, const ZSTD_CDict *cdict, const ZSTD_CCtx_params *params, unsigned long long pledgedSrcSize)
size_t	ZSTD_compress_advanced_internal (ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize, const ZSTD_CCtx_params *params)
size_t	ZSTD_writeLastEmptyBlock (void *dst, size_t dstCapacity)
size_t	ZSTD_referenceExternalSequences (ZSTD_CCtx *cctx, rawSeq *seq, size_t nbSeq)
U32	ZSTD_cycleLog (U32 hashLog, ZSTD_strategy strat)

Variables
static const U32	prime3bytes = 506832829U
static const U32	prime4bytes = 2654435761U
static const U64	prime5bytes = 889523592379ULL
static const U64	prime6bytes = 227718039650203ULL
static const U64	prime7bytes = 58295818150454627ULL
static const U64	prime8bytes = 0xCF1BBCDCB7A56463ULL

Macro Definition Documentation

HASH_READ_SIZE

#define HASH_READ_SIZE   8

Definition at line 36 of file zstd_compress_internal.h.

kSearchStrength

#define kSearchStrength   8

Definition at line 35 of file zstd_compress_internal.h.

ZSTD_CHUNKSIZE_MAX

#define ZSTD_CHUNKSIZE_MAX

Value:

    ( ((U32)-1)                  /* Maximum ending current index */            \
    - ZSTD_CURRENT_MAX)          /* Maximum beginning lowLimit */

Definition at line 703 of file zstd_compress_internal.h.

ZSTD_CURRENT_MAX

#define ZSTD_CURRENT_MAX   ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX))

Definition at line 701 of file zstd_compress_internal.h.

ZSTD_DUBT_UNSORTED_MARK

#define ZSTD_DUBT_UNSORTED_MARK

Value:

                                       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.
                                       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 mishandled after table re-use with a different strategy.
                                       This constant is required by ZSTD_compressBlock_btlazy2() and ZSTD_reduceTable_internal() */

Definition at line 37 of file zstd_compress_internal.h.

ZSTD_ROLL_HASH_CHAR_OFFSET

#define ZSTD_ROLL_HASH_CHAR_OFFSET   10

Definition at line 650 of file zstd_compress_internal.h.

Typedef Documentation

repcodes_t

typedef struct repcodes_s repcodes_t

ZSTD_blockCompressor

typedef size_t(* ZSTD_blockCompressor) (ZSTD_matchState_t *bs, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)

Definition at line 286 of file zstd_compress_internal.h.

ZSTD_matchState_t

typedef struct ZSTD_matchState_t ZSTD_matchState_t

Definition at line 129 of file zstd_compress_internal.h.

ZSTD_prefixDict

typedef struct ZSTD_prefixDict_s ZSTD_prefixDict

Enumeration Type Documentation

ZSTD_compressionStage_e

enum ZSTD_compressionStage_e

Enumerator
ZSTDcs_created
ZSTDcs_init
ZSTDcs_ongoing
ZSTDcs_ending

Definition at line 43 of file zstd_compress_internal.h.

{ ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;
typedef enum { zcss_init=0, zcss_load, zcss_flush } ZSTD_cStreamStage;
 
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;
 
typedef struct {
    FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)];
    FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)];
    FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)];
    FSE_repeat offcode_repeatMode;
    FSE_repeat matchlength_repeatMode;
    FSE_repeat litlength_repeatMode;
} ZSTD_fseCTables_t;
 
typedef struct {
    ZSTD_hufCTables_t huf;
    ZSTD_fseCTables_t fse;
} ZSTD_entropyCTables_t;
 
typedef struct {
    U32 off;
    U32 len;
} ZSTD_match_t;
 
typedef struct {
    int price;
    U32 off;
    U32 mlen;
    U32 litlen;
    U32 rep[ZSTD_REP_NUM];
} ZSTD_optimal_t;
 
typedef enum { zop_dynamic=0, zop_predef } ZSTD_OptPrice_e;
 
typedef struct {
    /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */
    unsigned* litFreq;           /* table of literals statistics, of size 256 */
    unsigned* litLengthFreq;     /* table of litLength statistics, of size (MaxLL+1) */
    unsigned* matchLengthFreq;   /* table of matchLength statistics, of size (MaxML+1) */
    unsigned* offCodeFreq;       /* table of offCode statistics, of size (MaxOff+1) */
    ZSTD_match_t* matchTable;    /* list of found matches, of size ZSTD_OPT_NUM+1 */
    ZSTD_optimal_t* priceTable;  /* All positions tracked by optimal parser, of size ZSTD_OPT_NUM+1 */
 
    U32  litSum;                 /* nb of literals */
    U32  litLengthSum;           /* nb of litLength codes */
    U32  matchLengthSum;         /* nb of matchLength codes */
    U32  offCodeSum;             /* nb of offset codes */
    U32  litSumBasePrice;        /* to compare to log2(litfreq) */
    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];
} ZSTD_compressedBlockState_t;
 
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 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, 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 hashLog3;           /* dispatch table for matches of len==3 : larger == faster, more memory */
    U32* hashTable;
    U32* hashTable3;
    U32* chainTable;
    optState_t opt;         /* optimal parser state */
    const ZSTD_matchState_t* dictMatchState;
    ZSTD_compressionParameters cParams;
};
 
typedef struct {
    ZSTD_compressedBlockState_t* prevCBlock;
    ZSTD_compressedBlockState_t* nextCBlock;
    ZSTD_matchState_t matchState;
} ZSTD_blockState_t;
 
typedef struct {
    U32 offset;
    U32 checksum;
} ldmEntry_t;
 
typedef struct {
    ZSTD_window_t window;   /* State for the window round buffer management */
    ldmEntry_t* hashTable;
    U32 loadedDictEnd;
    BYTE* bucketOffsets;    /* Next position in bucket to insert entry */
    U64 hashPower;          /* Used to compute the rolling hash.
                             * Depends on ldmParams.minMatchLength */
} ldmState_t;
 
typedef struct {
    U32 enableLdm;          /* 1 if enable long distance matching */
    U32 hashLog;            /* Log size of hashTable */
    U32 bucketSizeLog;      /* Log bucket size for collision resolution, at most 8 */
    U32 minMatchLength;     /* Minimum match length */
    U32 hashRateLog;       /* Log number of entries to skip */
    U32 windowLog;          /* Window log for the LDM */
} ldmParams_t;
 
typedef struct {
    U32 offset;
    U32 litLength;
    U32 matchLength;
} rawSeq;
 
typedef struct {
  rawSeq* seq;     /* The start of the sequences */
  size_t pos;      /* The position where reading stopped. <= size. */
  size_t size;     /* The number of sequences. <= capacity. */
  size_t capacity; /* The capacity starting from `seq` pointer */
} rawSeqStore_t;
 
typedef struct {
    int collectSequences;
    ZSTD_Sequence* seqStart;
    size_t seqIndex;
    size_t maxSequences;
} SeqCollector;
 
struct ZSTD_CCtx_params_s {
    ZSTD_format_e format;
    ZSTD_compressionParameters cParams;
    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 */
    int srcSizeHint;           /* User's best guess of source size.
                                * Hint is not valid when srcSizeHint == 0.
                                * There is no guarantee that hint is close to actual source size */
 
    ZSTD_dictAttachPref_e attachDictPref;
    ZSTD_literalCompressionMode_e literalCompressionMode;
 
    /* Multithreading: used to pass parameters to mtctx */
    int nbWorkers;
    size_t jobSize;
    int overlapLog;
    int rsyncable;
 
    /* Long distance matching parameters */
    ldmParams_t ldmParams;
 
    /* Internal use, for createCCtxParams() and freeCCtxParams() only */
    ZSTD_customMem customMem;
};  /* typedef'd to ZSTD_CCtx_params within "zstd.h" */
 
struct ZSTD_CCtx_s {
    ZSTD_compressionStage_e stage;
    int cParamsChanged;                  /* == 1 if cParams(except wlog) or compression level are changed in requestedParams. Triggers transmission of new params to ZSTDMT (if available) then reset to 0. */
    int bmi2;                            /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
    ZSTD_CCtx_params requestedParams;
    ZSTD_CCtx_params appliedParams;
    U32   dictID;
 
    ZSTD_cwksp workspace; /* manages buffer for dynamic allocations */
    size_t blockSize;
    unsigned long long pledgedSrcSizePlusOne;  /* this way, 0 (default) == unknown */
    unsigned long long consumedSrcSize;
    unsigned long long producedCSize;
    XXH64_state_t xxhState;
    ZSTD_customMem customMem;
    size_t staticSize;
    SeqCollector seqCollector;
    int isFirstBlock;
    int initialized;
 
    seqStore_t seqStore;      /* sequences storage ptrs */
    ldmState_t ldmState;      /* long distance matching state */
    rawSeq* ldmSequences;     /* Storage for the ldm output sequences */
    size_t maxNbLdmSequences;
    rawSeqStore_t externSeqStore; /* Mutable reference to external sequences */
    ZSTD_blockState_t blockState;
    U32* entropyWorkspace;  /* entropy workspace of HUF_WORKSPACE_SIZE bytes */
 
    /* streaming */
    char*  inBuff;
    size_t inBuffSize;
    size_t inToCompress;
    size_t inBuffPos;
    size_t inBuffTarget;
    char*  outBuff;
    size_t outBuffSize;
    size_t outBuffContentSize;
    size_t outBuffFlushedSize;
    ZSTD_cStreamStage streamStage;
    U32    frameEnded;
 
    /* Dictionary */
    ZSTD_localDict localDict;
    const ZSTD_CDict* cdict;
    ZSTD_prefixDict prefixDict;   /* single-usage dictionary */
 
    /* Multi-threading */
#ifdef ZSTD_MULTITHREAD
    ZSTDMT_CCtx* mtctx;
#endif
};
 
typedef enum { ZSTD_dtlm_fast, ZSTD_dtlm_full } ZSTD_dictTableLoadMethod_e;
 
typedef enum { ZSTD_noDict = 0, ZSTD_extDict = 1, ZSTD_dictMatchState = 2 } ZSTD_dictMode_e;
 
 
typedef size_t (*ZSTD_blockCompressor) (
        ZSTD_matchState_t* bs, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
        void const* src, size_t srcSize);
ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode);
 
 
MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
{
    static const BYTE LL_Code[64] = {  0,  1,  2,  3,  4,  5,  6,  7,
                                       8,  9, 10, 11, 12, 13, 14, 15,
                                      16, 16, 17, 17, 18, 18, 19, 19,
                                      20, 20, 20, 20, 21, 21, 21, 21,
                                      22, 22, 22, 22, 22, 22, 22, 22,
                                      23, 23, 23, 23, 23, 23, 23, 23,
                                      24, 24, 24, 24, 24, 24, 24, 24,
                                      24, 24, 24, 24, 24, 24, 24, 24 };
    static const U32 LL_deltaCode = 19;
    return (litLength > 63) ? ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];
}
 
/* ZSTD_MLcode() :
 * note : mlBase = matchLength - MINMATCH;
 *        because it's the format it's stored in seqStore->sequences */
MEM_STATIC U32 ZSTD_MLcode(U32 mlBase)
{
    static const BYTE ML_Code[128] = { 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,
                                      16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
                                      32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
                                      38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
                                      40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
                                      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];
}
 
typedef struct repcodes_s {
    U32 rep[3];
} repcodes_t;
 
MEM_STATIC repcodes_t ZSTD_updateRep(U32 const rep[3], U32 const offset, U32 const ll0)
{
    repcodes_t newReps;
    if (offset >= ZSTD_REP_NUM) {  /* full offset */
        newReps.rep[2] = rep[1];
        newReps.rep[1] = rep[0];
        newReps.rep[0] = offset - ZSTD_REP_MOVE;
    } else {   /* repcode */
        U32 const repCode = offset + ll0;
        if (repCode > 0) {  /* note : if repCode==0, no change */
            U32 const currentOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode];
            newReps.rep[2] = (repCode >= 2) ? rep[1] : rep[2];
            newReps.rep[1] = rep[0];
            newReps.rep[0] = currentOffset;
        } else {   /* repCode == 0 */
            memcpy(&newReps, rep, sizeof(newReps));
        }
    }
    return newReps;
}
 
/* 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_noCompressBlock() :
 * Writes uncompressed block to dst buffer from given src.
 * Returns the size of the block */
MEM_STATIC size_t ZSTD_noCompressBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize, U32 lastBlock)
{
    U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw)<<1) + (U32)(srcSize << 3);
    RETURN_ERROR_IF(srcSize + ZSTD_blockHeaderSize > dstCapacity,
                    dstSize_tooSmall, "dst buf too small for uncompressed block");
    MEM_writeLE24(dst, cBlockHeader24);
    memcpy((BYTE*)dst + ZSTD_blockHeaderSize, src, srcSize);
    return ZSTD_blockHeaderSize + srcSize;
}
 
MEM_STATIC size_t ZSTD_rleCompressBlock (void* dst, size_t dstCapacity, BYTE src, size_t srcSize, U32 lastBlock)
{
    BYTE* const op = (BYTE*)dst;
    U32 const cBlockHeader = lastBlock + (((U32)bt_rle)<<1) + (U32)(srcSize << 3);
    RETURN_ERROR_IF(dstCapacity < 4, dstSize_tooSmall, "");
    MEM_writeLE24(op, cBlockHeader);
    op[3] = src;
    return 4;
}
 
 
/* 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;
}
 
MEM_STATIC int ZSTD_disableLiteralsCompression(const ZSTD_CCtx_params* cctxParams)
{
    switch (cctxParams->literalCompressionMode) {
    case ZSTD_lcm_huffman:
        return 0;
    case ZSTD_lcm_uncompressed:
        return 1;
    default:
        assert(0 /* impossible: pre-validated */);
        /* fall-through */
    case ZSTD_lcm_auto:
        return (cctxParams->cParams.strategy == ZSTD_fast) && (cctxParams->cParams.targetLength > 0);
    }
}
 
static void ZSTD_safecopyLiterals(BYTE* op, BYTE const* ip, BYTE const* const iend, BYTE const* ilimit_w) {
    assert(iend > ilimit_w);
    if (ip <= ilimit_w) {
        ZSTD_wildcopy(op, ip, ilimit_w - ip, ZSTD_no_overlap);
        op += ilimit_w - ip;
        ip = ilimit_w;
    }
    while (ip < iend) *op++ = *ip++;
}
 
HINT_INLINE UNUSED_ATTR
void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const BYTE* literals, const BYTE* litLimit, U32 offCode, size_t mlBase)
{
    BYTE const* const litLimit_w = litLimit - WILDCOPY_OVERLENGTH;
    BYTE const* const litEnd = literals + litLength;
#if defined(DEBUGLEVEL) && (DEBUGLEVEL >= 6)
    static const BYTE* g_start = NULL;
    if (g_start==NULL) g_start = (const BYTE*)literals;  /* note : index only works for compression within a single segment */
    {   U32 const pos = (U32)((const BYTE*)literals - g_start);
        DEBUGLOG(6, "Cpos%7u :%3u literals, match%4u bytes at offCode%7u",
               pos, (U32)litLength, (U32)mlBase+MINMATCH, (U32)offCode);
    }
#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);
    assert(literals + litLength <= litLimit);
    if (litEnd <= litLimit_w) {
        /* Common case we can use wildcopy.
     * First copy 16 bytes, because literals are likely short.
     */
        assert(WILDCOPY_OVERLENGTH >= 16);
        ZSTD_copy16(seqStorePtr->lit, literals);
        if (litLength > 16) {
            ZSTD_wildcopy(seqStorePtr->lit+16, literals+16, (ptrdiff_t)litLength-16, ZSTD_no_overlap);
        }
    } else {
        ZSTD_safecopyLiterals(seqStorePtr->lit, literals, litEnd, litLimit_w);
    }
    seqStorePtr->lit += litLength;
 
    /* literal Length */
    if (litLength>0xFFFF) {
        assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
        seqStorePtr->longLengthID = 1;
        seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
    }
    seqStorePtr->sequences[0].litLength = (U16)litLength;
 
    /* match offset */
    seqStorePtr->sequences[0].offset = offCode + 1;
 
    /* match Length */
    if (mlBase>0xFFFF) {
        assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
        seqStorePtr->longLengthID = 2;
        seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
    }
    seqStorePtr->sequences[0].matchLength = (U16)mlBase;
 
    seqStorePtr->sequences++;
}
 
 
/*-*************************************
*  Match length counter
***************************************/
static unsigned ZSTD_NbCommonBytes (size_t val)
{
    if (MEM_isLittleEndian()) {
        if (MEM_64bits()) {
#       if defined(_MSC_VER) && defined(_WIN64)
            unsigned long r = 0;
            return _BitScanForward64( &r, (U64)val ) ? (unsigned)(r >> 3) : 0;
#       elif defined(__GNUC__) && (__GNUC__ >= 4)
            return (__builtin_ctzll((U64)val) >> 3);
#       else
            static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
                                                     0, 3, 1, 3, 1, 4, 2, 7,
                                                     0, 2, 3, 6, 1, 5, 3, 5,
                                                     1, 3, 4, 4, 2, 5, 6, 7,
                                                     7, 0, 1, 2, 3, 3, 4, 6,
                                                     2, 6, 5, 5, 3, 4, 5, 6,
                                                     7, 1, 2, 4, 6, 4, 4, 5,
                                                     7, 2, 6, 5, 7, 6, 7, 7 };
            return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
#       endif
        } else { /* 32 bits */
#       if defined(_MSC_VER)
            unsigned long r=0;
            return _BitScanForward( &r, (U32)val ) ? (unsigned)(r >> 3) : 0;
#       elif defined(__GNUC__) && (__GNUC__ >= 3)
            return (__builtin_ctz((U32)val) >> 3);
#       else
            static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
                                                     3, 2, 2, 1, 3, 2, 0, 1,
                                                     3, 3, 1, 2, 2, 2, 2, 0,
                                                     3, 1, 2, 0, 1, 0, 1, 1 };
            return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
#       endif
        }
    } else {  /* Big Endian CPU */
        if (MEM_64bits()) {
#       if defined(_MSC_VER) && defined(_WIN64)
            unsigned long r = 0;
            return _BitScanReverse64( &r, val ) ? (unsigned)(r >> 3) : 0;
#       elif defined(__GNUC__) && (__GNUC__ >= 4)
            return (__builtin_clzll(val) >> 3);
#       else
            unsigned r;
            const unsigned n32 = sizeof(size_t)*4;   /* calculate this way due to compiler complaining in 32-bits mode */
            if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
            if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
            r += (!val);
            return r;
#       endif
        } else { /* 32 bits */
#       if defined(_MSC_VER)
            unsigned long r = 0;
            return _BitScanReverse( &r, (unsigned long)val ) ? (unsigned)(r >> 3) : 0;
#       elif defined(__GNUC__) && (__GNUC__ >= 3)
            return (__builtin_clz((U32)val) >> 3);
#       else
            unsigned r;
            if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
            r += (!val);
            return r;
#       endif
    }   }
}
 
 
MEM_STATIC size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
{
    const BYTE* const pStart = pIn;
    const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
 
    if (pIn < pInLoopLimit) {
        { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
          if (diff) return ZSTD_NbCommonBytes(diff); }
        pIn+=sizeof(size_t); pMatch+=sizeof(size_t);
        while (pIn < pInLoopLimit) {
            size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
            if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
            pIn += ZSTD_NbCommonBytes(diff);
            return (size_t)(pIn - pStart);
    }   }
    if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
    if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
    if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
    return (size_t)(pIn - pStart);
}
 
MEM_STATIC size_t
ZSTD_count_2segments(const BYTE* ip, const BYTE* match,
                     const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
{
    const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
    size_t const matchLength = ZSTD_count(ip, match, vEnd);
    if (match + matchLength != mEnd) return matchLength;
    DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength);
    DEBUGLOG(7, "distance from match beginning to end dictionary = %zi", mEnd - match);
    DEBUGLOG(7, "distance from current pos to end buffer = %zi", iEnd - ip);
    DEBUGLOG(7, "next byte : ip==%02X, istart==%02X", ip[matchLength], *iStart);
    DEBUGLOG(7, "final match length = %zu", matchLength + ZSTD_count(ip+matchLength, iStart, iEnd));
    return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
}
 
 
/*-*************************************
 *  Hashes
 ***************************************/
static const U32 prime3bytes = 506832829U;
static U32    ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes)  >> (32-h) ; }
MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
 
static const U32 prime4bytes = 2654435761U;
static U32    ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
 
static const U64 prime5bytes = 889523592379ULL;
static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u  << (64-40)) * prime5bytes) >> (64-h)) ; }
static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
 
static const U64 prime6bytes = 227718039650203ULL;
static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u  << (64-48)) * prime6bytes) >> (64-h)) ; }
static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
 
static const U64 prime7bytes = 58295818150454627ULL;
static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u  << (64-56)) * prime7bytes) >> (64-h)) ; }
static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
 
static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
 
MEM_STATIC size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
{
    switch(mls)
    {
    default:
    case 4: return ZSTD_hash4Ptr(p, hBits);
    case 5: return ZSTD_hash5Ptr(p, hBits);
    case 6: return ZSTD_hash6Ptr(p, hBits);
    case 7: return ZSTD_hash7Ptr(p, hBits);
    case 8: return ZSTD_hash8Ptr(p, hBits);
    }
}
 
static U64 ZSTD_ipow(U64 base, U64 exponent)
{
    U64 power = 1;
    while (exponent) {
      if (exponent & 1) power *= base;
      exponent >>= 1;
      base *= base;
    }
    return power;
}
 
#define ZSTD_ROLL_HASH_CHAR_OFFSET 10
 
static U64 ZSTD_rollingHash_append(U64 hash, void const* buf, size_t size)
{
    BYTE const* istart = (BYTE const*)buf;
    size_t pos;
    for (pos = 0; pos < size; ++pos) {
        hash *= prime8bytes;
        hash += istart[pos] + ZSTD_ROLL_HASH_CHAR_OFFSET;
    }
    return hash;
}
 
MEM_STATIC U64 ZSTD_rollingHash_compute(void const* buf, size_t size)
{
    return ZSTD_rollingHash_append(0, buf, size);
}
 
MEM_STATIC U64 ZSTD_rollingHash_primePower(U32 length)
{
    return ZSTD_ipow(prime8bytes, length - 1);
}
 
MEM_STATIC U64 ZSTD_rollingHash_rotate(U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower)
{
    hash -= (toRemove + ZSTD_ROLL_HASH_CHAR_OFFSET) * primePower;
    hash *= prime8bytes;
    hash += toAdd + ZSTD_ROLL_HASH_CHAR_OFFSET;
    return hash;
}
 
/*-*************************************
*  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_CURRENT_MAX)          /* Maximum beginning lowLimit */
 
MEM_STATIC void ZSTD_window_clear(ZSTD_window_t* window)
{
    size_t const endT = (size_t)(window->nextSrc - window->base);
    U32 const end = (U32)endT;
 
    window->lowLimit = end;
    window->dictLimit = end;
}
 
MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
{
    return window.lowLimit < window.dictLimit;
}
 
MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms)
{
    return ZSTD_window_hasExtDict(ms->window) ?
        ZSTD_extDict :
        ms->dictMatchState != NULL ?
            ZSTD_dictMatchState :
            ZSTD_noDict;
}
 
MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window,
                                                  void const* srcEnd)
{
    U32 const current = (U32)((BYTE const*)srcEnd - window.base);
    return current > ZSTD_CURRENT_MAX;
}
 
MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t* window, U32 cycleLog,
                                           U32 maxDist, void const* src)
{
    /* preemptive overflow correction:
     * 1. correction is large enough:
     *    lowLimit > (3<<29) ==> current > 3<<29 + 1<<windowLog
     *    1<<windowLog <= newCurrent < 1<<chainLog + 1<<windowLog
     *
     *    current - newCurrent
     *    > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog)
     *    > (3<<29) - (1<<chainLog)
     *    > (3<<29) - (1<<30)             (NOTE: chainLog <= 30)
     *    > 1<<29
     *
     * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow:
     *    After correction, current is less than (1<<chainLog + 1<<windowLog).
     *    In 64-bit mode we are safe, because we have 64-bit ptrdiff_t.
     *    In 32-bit mode we are safe, because (chainLog <= 29), so
     *    ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32.
     * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32:
     *    windowLog <= 31 ==> 3<<29 + 1<<windowLog < 7<<29 < 1<<32.
     */
    U32 const cycleMask = (1U << cycleLog) - 1;
    U32 const current = (U32)((BYTE const*)src - window->base);
    U32 const currentCycle0 = current & cycleMask;
    /* Exclude zero so that newCurrent - maxDist >= 1. */
    U32 const currentCycle1 = currentCycle0 == 0 ? (1U << cycleLog) : currentCycle0;
    U32 const newCurrent = currentCycle1 + maxDist;
    U32 const correction = current - newCurrent;
    assert((maxDist & cycleMask) == 0);
    assert(current > newCurrent);
    /* Loose bound, should be around 1<<29 (see above) */
    assert(correction > 1<<28);
 
    window->base += correction;
    window->dictBase += correction;
    if (window->lowLimit <= correction) window->lowLimit = 1;
    else window->lowLimit -= correction;
    if (window->dictLimit <= correction) window->dictLimit = 1;
    else window->dictLimit -= correction;
 
    /* Ensure we can still reference the full window. */
    assert(newCurrent >= maxDist);
    assert(newCurrent - maxDist >= 1);
    /* Ensure that lowLimit and dictLimit didn't underflow. */
    assert(window->lowLimit <= newCurrent);
    assert(window->dictLimit <= newCurrent);
 
    DEBUGLOG(4, "Correction of 0x%x bytes to lowLimit=0x%x", correction,
             window->lowLimit);
    return correction;
}
 
MEM_STATIC void
ZSTD_window_enforceMaxDist(ZSTD_window_t* window,
                     const void* blockEnd,
                           U32   maxDist,
                           U32*  loadedDictEndPtr,
                     const ZSTD_matchState_t** dictMatchStatePtr)
{
    U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
    U32 const loadedDictEnd = (loadedDictEndPtr != NULL) ? *loadedDictEndPtr : 0;
    DEBUGLOG(5, "ZSTD_window_enforceMaxDist: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
                (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;
        }
        /* 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;
            *dictMatchStatePtr = NULL;
        } else {
            if (*loadedDictEndPtr != 0) {
                DEBUGLOG(6, "dictionary considered valid for current block");
    }   }   }
}
 
MEM_STATIC void ZSTD_window_init(ZSTD_window_t* window) {
    memset(window, 0, sizeof(*window));
    window->base = (BYTE const*)"";
    window->dictBase = (BYTE const*)"";
    window->dictLimit = 1;    /* start from 1, so that 1st position is valid */
    window->lowLimit = 1;     /* it ensures first and later CCtx usages compress the same */
    window->nextSrc = window->base + 1;   /* see issue #1241 */
}
 
MEM_STATIC U32 ZSTD_window_update(ZSTD_window_t* window,
                                  void const* src, size_t srcSize)
{
    BYTE const* const ip = (BYTE const*)src;
    U32 contiguous = 1;
    DEBUGLOG(5, "ZSTD_window_update");
    if (srcSize == 0)
        return contiguous;
    assert(window->base != NULL);
    assert(window->dictBase != NULL);
    /* Check if blocks follow each other */
    if (src != window->nextSrc) {
        /* not contiguous */
        size_t const distanceFromBase = (size_t)(window->nextSrc - window->base);
        DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit);
        window->lowLimit = window->dictLimit;
        assert(distanceFromBase == (size_t)(U32)distanceFromBase);  /* should never overflow */
        window->dictLimit = (U32)distanceFromBase;
        window->dictBase = window->base;
        window->base = ip - distanceFromBase;
        /* ms->nextToUpdate = window->dictLimit; */
        if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit;   /* too small extDict */
        contiguous = 0;
    }
    window->nextSrc = ip + srcSize;
    /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
    if ( (ip+srcSize > window->dictBase + window->lowLimit)
       & (ip < window->dictBase + window->dictLimit)) {
        ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase;
        U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)window->dictLimit) ? window->dictLimit : (U32)highInputIdx;
        window->lowLimit = lowLimitMax;
        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;
}
 
MEM_STATIC U32 ZSTD_getLowestPrefixIndex(const ZSTD_matchState_t* ms, U32 current, unsigned windowLog)
{
    U32    const maxDistance = 1U << windowLog;
    U32    const lowestValid = ms->window.dictLimit;
    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)
{
    U32 const fp_accuracy = 8;
    U32 const fp_multiplier = (1 << fp_accuracy);
    U32 const newStat = rawStat + 1;
    U32 const hb = ZSTD_highbit32(newStat);
    U32 const BWeight = hb * fp_multiplier;
    U32 const FWeight = (newStat << fp_accuracy) >> hb;
    U32 const weight = BWeight + FWeight;
    assert(hb + fp_accuracy < 31);
    return (double)weight / fp_multiplier;
}
 
/* display a table content,
 * listing each element, its frequency, and its predicted bit cost */
MEM_STATIC void ZSTD_debugTable(const U32* table, U32 max)
{
    unsigned u, sum;
    for (u=0, sum=0; u<=max; u++) sum += table[u];
    DEBUGLOG(2, "total nb elts: %u", sum);
    for (u=0; u<=max; u++) {
        DEBUGLOG(2, "%2u: %5u  (%.2f)",
                u, table[u], ZSTD_fWeight(sum) - ZSTD_fWeight(table[u]) );
    }
}
 
#endif
 
 
#if defined (__cplusplus)
}
#endif
 
/* ===============================================================
 * Shared internal declarations
 * These prototypes may be called from sources not in lib/compress
 * =============================================================== */
 
/* ZSTD_loadCEntropy() :
 * dict : must point at beginning of a valid zstd dictionary.
 * return : size of dictionary header (size of magic number + dict ID + entropy tables)
 * assumptions : magic number supposed already checked
 *               and dictSize >= 8 */
size_t ZSTD_loadCEntropy(ZSTD_compressedBlockState_t* bs, void* workspace,
                         short* offcodeNCount, unsigned* offcodeMaxValue,
                         const void* const dict, size_t dictSize);
 
void ZSTD_reset_compressedBlockState(ZSTD_compressedBlockState_t* bs);
 
/* ==============================================================
 * Private declarations
 * These prototypes shall only be called from within lib/compress
 * ============================================================== */
 
/* ZSTD_getCParamsFromCCtxParams() :
 * cParams are built depending on compressionLevel, src size hints,
 * LDM and manually set compression parameters.
 * Note: srcSizeHint == 0 means 0!
 */
ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams(
        const ZSTD_CCtx_params* CCtxParams, U64 srcSizeHint, size_t dictSize);
 
size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs,
                     const void* dict, size_t dictSize,
                     const ZSTD_CDict* cdict,
                     const ZSTD_CCtx_params* params, unsigned long long pledgedSrcSize);
 
void ZSTD_resetSeqStore(seqStore_t* ssPtr);
 
ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict);
 
/* ZSTD_compressBegin_advanced_internal() :
 * Private use only. To be called from zstdmt_compress.c. */
size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx* cctx,
                                    const void* dict, size_t dictSize,
                                    ZSTD_dictContentType_e dictContentType,
                                    ZSTD_dictTableLoadMethod_e dtlm,
                                    const ZSTD_CDict* cdict,
                                    const ZSTD_CCtx_params* params,
                                    unsigned long long pledgedSrcSize);
 
/* ZSTD_compress_advanced_internal() :
 * Private use only. To be called from zstdmt_compress.c. */
size_t ZSTD_compress_advanced_internal(ZSTD_CCtx* cctx,
                                       void* dst, size_t dstCapacity,
                                 const void* src, size_t srcSize,
                                 const void* dict,size_t dictSize,
                                 const ZSTD_CCtx_params* params);
 
 
/* 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 `dstCapacity` is too small (<ZSTD_blockHeaderSize)
 */
size_t ZSTD_writeLastEmptyBlock(void* dst, size_t dstCapacity);
 
 
/* ZSTD_referenceExternalSequences() :
 * Must be called before starting a compression operation.
 * seqs must parse a prefix of the source.
 * This cannot be used when long range matching is enabled.
 * Zstd will use these sequences, and pass the literals to a secondary block
 * compressor.
 * @return : An error code on failure.
 * NOTE: seqs are not verified! Invalid sequences can cause out-of-bounds memory
 * access and data corruption.
 */
size_t ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq);
 
U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat);
 
#endif /* ZSTD_COMPRESS_H */

ZSTD_cStreamStage

enum ZSTD_cStreamStage

Enumerator
zcss_init
zcss_load
zcss_flush

Definition at line 44 of file zstd_compress_internal.h.

ZSTD_dictMode_e

enum ZSTD_dictMode_e

Enumerator
ZSTD_noDict
ZSTD_extDict
ZSTD_dictMatchState

Definition at line 283 of file zstd_compress_internal.h.

ZSTD_dictTableLoadMethod_e

enum ZSTD_dictTableLoadMethod_e

Enumerator
ZSTD_dtlm_fast
ZSTD_dtlm_full

Definition at line 281 of file zstd_compress_internal.h.

ZSTD_OptPrice_e

enum ZSTD_OptPrice_e

Enumerator
zop_dynamic
zop_predef

Definition at line 92 of file zstd_compress_internal.h.

Function Documentation

ZSTD_checkDictValidity()

MEM_STATIC void ZSTD_checkDictValidity	(	const ZSTD_window_t *	window,
		const void *	blockEnd,
		U32	maxDist,
		U32 *	loadedDictEndPtr,
		const ZSTD_matchState_t **	dictMatchStatePtr
	)

Definition at line 887 of file zstd_compress_internal.h.

              : 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;

Referenced by ZSTD_compress_frameChunk().

ZSTD_compress_advanced_internal()

size_t ZSTD_compress_advanced_internal	(	ZSTD_CCtx *	cctx,
		void *	dst,
		size_t	dstCapacity,
		const void *	src,
		size_t	srcSize,
		const void *	dict,
		size_t	dictSize,
		const ZSTD_CCtx_params *	params
	)

Definition at line 3270 of file zstd_compress.c.

{
    DEBUGLOG(4, "ZSTD_compress_advanced_internal (srcSize:%u)", (unsigned)srcSize);
    FORWARD_IF_ERROR( ZSTD_compressBegin_internal(cctx,
                         dict, dictSize, ZSTD_dct_auto, ZSTD_dtlm_fast, NULL,
                         params, srcSize, ZSTDb_not_buffered) , "");
    return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize);
}

Referenced by ZSTD_compress_internal(), and ZSTD_compress_usingDict().

ZSTD_compressBegin_advanced_internal()

size_t ZSTD_compressBegin_advanced_internal	(	ZSTD_CCtx *	cctx,
		const void *	dict,
		size_t	dictSize,
		ZSTD_dictContentType_e	dictContentType,
		ZSTD_dictTableLoadMethod_e	dtlm,
		const ZSTD_CDict *	cdict,
		const ZSTD_CCtx_params *	params,
		unsigned long long	pledgedSrcSize
	)

Definition at line 3122 of file zstd_compress.c.

{
    DEBUGLOG(4, "ZSTD_compressBegin_advanced_internal: wlog=%u", params->cParams.windowLog);
    /* compression parameters verification and optimization */
    FORWARD_IF_ERROR( ZSTD_checkCParams(params->cParams) , "");
    return ZSTD_compressBegin_internal(cctx,
                                       dict, dictSize, dictContentType, dtlm,
                                       cdict,
                                       params, pledgedSrcSize,
                                       ZSTDb_not_buffered);
}

Referenced by ZSTD_compressBegin_advanced().

ZSTD_count()

MEM_STATIC size_t ZSTD_count	(	const BYTE *	pIn,
		const BYTE *	pMatch,
		const BYTE *const	pInLimit
	)

Definition at line 555 of file zstd_compress_internal.h.

{
    const BYTE* const pStart = pIn;
    const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
 
    if (pIn < pInLoopLimit) {
        { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
          if (diff) return ZSTD_NbCommonBytes(diff); }
        pIn+=sizeof(size_t); pMatch+=sizeof(size_t);
        while (pIn < pInLoopLimit) {
            size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
            if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
            pIn += ZSTD_NbCommonBytes(diff);
            return (size_t)(pIn - pStart);

Referenced by ZSTD_compressBlock_doubleFast_generic(), ZSTD_compressBlock_fast_dictMatchState_generic(), ZSTD_compressBlock_fast_generic(), ZSTD_compressBlock_lazy_generic(), ZSTD_count_2segments(), ZSTD_DUBT_findBestMatch(), ZSTD_HcFindBestMatch_generic(), ZSTD_insertBt1(), ZSTD_insertBtAndGetAllMatches(), ZSTD_insertDUBT1(), and ZSTD_ldm_generateSequences_internal().

ZSTD_count_2segments()

MEM_STATIC size_t ZSTD_count_2segments	(	const BYTE *	ip,
		const BYTE *	match,
		const BYTE *	iEnd,
		const BYTE *	mEnd,
		const BYTE *	iStart
	)

ZSTD_count_2segments() : can count match length with ip & match in 2 different segments. convention : on reaching mEnd, match count continue starting from iStart

Definition at line 581 of file zstd_compress_internal.h.

{
    const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
    size_t const matchLength = ZSTD_count(ip, match, vEnd);
    if (match + matchLength != mEnd) return matchLength;
    DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength);

Referenced by ZSTD_compressBlock_doubleFast_extDict_generic(), ZSTD_compressBlock_doubleFast_generic(), ZSTD_compressBlock_fast_dictMatchState_generic(), ZSTD_compressBlock_fast_extDict_generic(), ZSTD_compressBlock_lazy_extDict_generic(), ZSTD_compressBlock_lazy_generic(), ZSTD_DUBT_findBestMatch(), ZSTD_DUBT_findBetterDictMatch(), ZSTD_HcFindBestMatch_generic(), ZSTD_insertBt1(), ZSTD_insertBtAndGetAllMatches(), ZSTD_insertDUBT1(), and ZSTD_ldm_generateSequences_internal().

ZSTD_cParam_withinBounds()

MEM_STATIC int ZSTD_cParam_withinBounds	(	ZSTD_cParameter	cParam,
		int	value
	)

Definition at line 351 of file zstd_compress_internal.h.

{

Referenced by ZSTD_selectBlockCompressor().

ZSTD_cycleLog()

U32 ZSTD_cycleLog	(	U32	hashLog,
		ZSTD_strategy	strat
	)

ZSTD_cycleLog() : condition for correct operation : hashLog > 1

Definition at line 1019 of file zstd_compress.c.

{
    U32 const btScale = ((U32)strat >= (U32)ZSTD_btlazy2);
    return hashLog - btScale;
}

Referenced by ZSTD_adjustCParams_internal(), and ZSTD_overflowCorrectIfNeeded().

ZSTD_disableLiteralsCompression()

MEM_STATIC int ZSTD_disableLiteralsCompression

(

const ZSTD_CCtx_params *

cctxParams

)

Definition at line 396 of file zstd_compress_internal.h.

                                                                : 6;
    ZSTD_STATIC_ASSERT(ZSTD_btultra == 8);
    assert(ZSTD_cParam_withinBounds(ZSTD_c_strategy, strat));
    return (srcSize >> minlog) + 2;
}
 
MEM_STATIC int ZSTD_disableLiteralsCompression(const ZSTD_CCtx_params* cctxParams)
{
    switch (cctxParams->literalCompressionMode) {
    case ZSTD_lcm_huffman:
        return 0;
    case ZSTD_lcm_uncompressed:
        return 1;
    default:

Referenced by ZSTD_buildSuperBlockEntropy(), and ZSTD_compressSequences_internal().

ZSTD_getCParamsFromCCtxParams()

ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams	(	const ZSTD_CCtx_params *	CCtxParams,
		U64	srcSizeHint,
		size_t	dictSize
	)

Definition at line 1077 of file zstd_compress.c.

{
    ZSTD_compressionParameters cParams;
    if (srcSizeHint == ZSTD_CONTENTSIZE_UNKNOWN && CCtxParams->srcSizeHint > 0) {
      srcSizeHint = CCtxParams->srcSizeHint;
    }
    cParams = ZSTD_getCParams_internal(CCtxParams->compressionLevel, srcSizeHint, dictSize);
    if (CCtxParams->ldmParams.enableLdm) cParams.windowLog = ZSTD_LDM_DEFAULT_WINDOW_LOG;
    if (CCtxParams->cParams.windowLog) cParams.windowLog = CCtxParams->cParams.windowLog;
    if (CCtxParams->cParams.hashLog) cParams.hashLog = CCtxParams->cParams.hashLog;
    if (CCtxParams->cParams.chainLog) cParams.chainLog = CCtxParams->cParams.chainLog;
    if (CCtxParams->cParams.searchLog) cParams.searchLog = CCtxParams->cParams.searchLog;
    if (CCtxParams->cParams.minMatch) cParams.minMatch = CCtxParams->cParams.minMatch;
    if (CCtxParams->cParams.targetLength) cParams.targetLength = CCtxParams->cParams.targetLength;
    if (CCtxParams->cParams.strategy) cParams.strategy = CCtxParams->cParams.strategy;
    assert(!ZSTD_checkCParams(cParams));
    /* srcSizeHint == 0 means 0 */
    return ZSTD_adjustCParams_internal(cParams, srcSizeHint, dictSize);
}

Referenced by ZSTD_compressStream2(), ZSTD_estimateCCtxSize_usingCCtxParams(), ZSTD_estimateCStreamSize_usingCCtxParams(), ZSTD_initLocalDict(), and ZSTD_resetCStream_internal().

ZSTD_getCParamsFromCDict()

ZSTD_compressionParameters ZSTD_getCParamsFromCDict

(

const ZSTD_CDict *

cdict

)

ZSTD_getCParamsFromCDict() : as the name implies

Definition at line 3530 of file zstd_compress.c.

{
    assert(cdict != NULL);
    return cdict->matchState.cParams;
}

Referenced by ZSTD_compressBegin_usingCDict_advanced().

ZSTD_getLowestMatchIndex()

MEM_STATIC U32 ZSTD_getLowestMatchIndex	(	const ZSTD_matchState_t *	ms,
		U32	current,
		unsigned	windowLog
	)

Returns the lowest allowed match index. It may either be in the ext-dict or the prefix.

Definition at line 970 of file zstd_compress_internal.h.

{
    U32    const maxDistance = 1U << windowLog;

Referenced by ZSTD_compressBlock_doubleFast_extDict_generic(), ZSTD_compressBlock_fast_extDict_generic(), ZSTD_compressBlock_lazy_extDict_generic(), ZSTD_DUBT_findBestMatch(), and ZSTD_insertBtAndGetAllMatches().

ZSTD_getLowestPrefixIndex()

MEM_STATIC U32 ZSTD_getLowestPrefixIndex	(	const ZSTD_matchState_t *	ms,
		U32	current,
		unsigned	windowLog
	)

Returns the lowest allowed match index in the prefix.

Definition at line 983 of file zstd_compress_internal.h.

{
    U32    const maxDistance = 1U << windowLog;

Referenced by ZSTD_compressBlock_doubleFast_generic(), ZSTD_compressBlock_fast_generic(), and ZSTD_compressBlock_lazy_generic().

ZSTD_hash3()

static U32 ZSTD_hash3 ( U32  u, U32  h  )

static

Definition at line 600 of file zstd_compress_internal.h.

ZSTD_hash3Ptr()

MEM_STATIC size_t ZSTD_hash3Ptr	(	const void *	ptr,
		U32	h
	)

Definition at line 601 of file zstd_compress_internal.h.

Referenced by ZSTD_insertAndFindFirstIndexHash3().

ZSTD_hash4()

static U32 ZSTD_hash4 ( U32  u, U32  h  )

static

Definition at line 604 of file zstd_compress_internal.h.

ZSTD_hash4Ptr()

static size_t ZSTD_hash4Ptr ( const void *  ptr, U32  h  )

static

Definition at line 605 of file zstd_compress_internal.h.

ZSTD_hash5()

static size_t ZSTD_hash5 ( U64  u, U32  h  )

static

Definition at line 608 of file zstd_compress_internal.h.

ZSTD_hash5Ptr()

static size_t ZSTD_hash5Ptr ( const void *  p, U32  h  )

static

Definition at line 609 of file zstd_compress_internal.h.

ZSTD_hash6()

static size_t ZSTD_hash6 ( U64  u, U32  h  )

static

Definition at line 612 of file zstd_compress_internal.h.

ZSTD_hash6Ptr()

static size_t ZSTD_hash6Ptr ( const void *  p, U32  h  )

static

Definition at line 613 of file zstd_compress_internal.h.

ZSTD_hash7()

static size_t ZSTD_hash7 ( U64  u, U32  h  )

static

Definition at line 616 of file zstd_compress_internal.h.

Referenced by ZSTD_hashPtr().

ZSTD_hash7Ptr()

static size_t ZSTD_hash7Ptr ( const void *  p, U32  h  )

static

Definition at line 617 of file zstd_compress_internal.h.

ZSTD_hash8()

static size_t ZSTD_hash8 ( U64  u, U32  h  )

static

Definition at line 620 of file zstd_compress_internal.h.

ZSTD_hash8Ptr()

static size_t ZSTD_hash8Ptr ( const void *  p, U32  h  )

static

Definition at line 621 of file zstd_compress_internal.h.

ZSTD_hashPtr()

MEM_STATIC size_t ZSTD_hashPtr	(	const void *	p,
		U32	hBits,
		U32	mls
	)

Definition at line 623 of file zstd_compress_internal.h.

                                                  { return ZSTD_hash7(MEM_readLE64(p), h); }
 
static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
 
MEM_STATIC size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
{
    switch(mls)
    {
    default:
    case 4: return ZSTD_hash4Ptr(p, hBits);

Referenced by ZSTD_compressBlock_doubleFast_extDict_generic(), ZSTD_compressBlock_doubleFast_generic(), ZSTD_compressBlock_fast_dictMatchState_generic(), ZSTD_compressBlock_fast_extDict_generic(), ZSTD_compressBlock_fast_generic(), ZSTD_DUBT_findBestMatch(), ZSTD_DUBT_findBetterDictMatch(), ZSTD_fillDoubleHashTable(), ZSTD_fillHashTable(), ZSTD_HcFindBestMatch_generic(), ZSTD_insertAndFindFirstIndex_internal(), ZSTD_insertBt1(), ZSTD_insertBtAndGetAllMatches(), and ZSTD_updateDUBT().

ZSTD_initCStream_internal()

size_t ZSTD_initCStream_internal	(	ZSTD_CStream *	zcs,
		const void *	dict,
		size_t	dictSize,
		const ZSTD_CDict *	cdict,
		const ZSTD_CCtx_params *	params,
		unsigned long long	pledgedSrcSize
	)

ZSTD_initCStream_internal() : Private use only. Init streaming operation. expects params to be valid. must receive dict, or cdict, or none, but not both.

Returns

: 0, or an error code

ZSTD_initCStream_internal() : Note : for lib/compress only. Used by zstdmt_compress.c. Assumption 1 : params are valid Assumption 2 : either dict, or cdict, is defined, not both

Definition at line 3690 of file zstd_compress.c.

{
    DEBUGLOG(4, "ZSTD_initCStream_internal");
    FORWARD_IF_ERROR( ZSTD_CCtx_reset(zcs, ZSTD_reset_session_only) , "");
    FORWARD_IF_ERROR( ZSTD_CCtx_setPledgedSrcSize(zcs, pledgedSrcSize) , "");
    assert(!ZSTD_isError(ZSTD_checkCParams(params->cParams)));
    zcs->requestedParams = *params;
    assert(!((dict) && (cdict)));  /* either dict or cdict, not both */
    if (dict) {
        FORWARD_IF_ERROR( ZSTD_CCtx_loadDictionary(zcs, dict, dictSize) , "");
    } else {
        /* Dictionary is cleared if !cdict */
        FORWARD_IF_ERROR( ZSTD_CCtx_refCDict(zcs, cdict) , "");
    }
    return 0;
}

ZSTD_ipow()

static U64 ZSTD_ipow ( U64  base, U64  exponent  )

static

ZSTD_ipow() : Return base^exponent.

Definition at line 639 of file zstd_compress_internal.h.

{
    U64 power = 1;
    while (exponent) {

ZSTD_LLcode()

MEM_STATIC U32 ZSTD_LLcode

(

U32

litLength

)

Definition at line 292 of file zstd_compress_internal.h.

{
    static const BYTE LL_Code[64] = {  0,  1,  2,  3,  4,  5,  6,  7,
                                       8,  9, 10, 11, 12, 13, 14, 15,
                                      16, 16, 17, 17, 18, 18, 19, 19,
                                      20, 20, 20, 20, 21, 21, 21, 21,
                                      22, 22, 22, 22, 22, 22, 22, 22,

Referenced by ZSTD_litLengthPrice(), ZSTD_seqToCodes(), and ZSTD_updateStats().

ZSTD_loadCEntropy()

size_t ZSTD_loadCEntropy	(	ZSTD_compressedBlockState_t *	bs,
		void *	workspace,
		short *	offcodeNCount,
		unsigned *	offcodeMaxValue,
		const void *const	dict,
		size_t	dictSize
	)

Definition at line 2902 of file zstd_compress.c.

{
    const BYTE* dictPtr = (const BYTE*)dict;    /* skip magic num and dict ID */
    const BYTE* const dictEnd = dictPtr + dictSize;
    dictPtr += 8;
    bs->entropy.huf.repeatMode = HUF_repeat_check;
 
    {   unsigned maxSymbolValue = 255;
        unsigned hasZeroWeights = 1;
        size_t const hufHeaderSize = HUF_readCTable((HUF_CElt*)bs->entropy.huf.CTable, &maxSymbolValue, dictPtr,
            dictEnd-dictPtr, &hasZeroWeights);
 
        /* We only set the loaded table as valid if it contains all non-zero
         * weights. Otherwise, we set it to check */
        if (!hasZeroWeights)
            bs->entropy.huf.repeatMode = HUF_repeat_valid;
 
        RETURN_ERROR_IF(HUF_isError(hufHeaderSize), dictionary_corrupted, "");
        RETURN_ERROR_IF(maxSymbolValue < 255, dictionary_corrupted, "");
        dictPtr += hufHeaderSize;
    }
 
    {   unsigned offcodeLog;
        size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
        RETURN_ERROR_IF(FSE_isError(offcodeHeaderSize), dictionary_corrupted, "");
        RETURN_ERROR_IF(offcodeLog > OffFSELog, dictionary_corrupted, "");
        /* Defer checking offcodeMaxValue because we need to know the size of the dictionary content */
        /* fill all offset symbols to avoid garbage at end of table */
        RETURN_ERROR_IF(FSE_isError(FSE_buildCTable_wksp(
                bs->entropy.fse.offcodeCTable,
                offcodeNCount, MaxOff, offcodeLog,
                workspace, HUF_WORKSPACE_SIZE)),
            dictionary_corrupted, "");
        dictPtr += offcodeHeaderSize;
    }
 
    {   short matchlengthNCount[MaxML+1];
        unsigned matchlengthMaxValue = MaxML, matchlengthLog;
        size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
        RETURN_ERROR_IF(FSE_isError(matchlengthHeaderSize), dictionary_corrupted, "");
        RETURN_ERROR_IF(matchlengthLog > MLFSELog, dictionary_corrupted, "");
        /* Every match length code must have non-zero probability */
        FORWARD_IF_ERROR( ZSTD_checkDictNCount(matchlengthNCount, matchlengthMaxValue, MaxML), "");
        RETURN_ERROR_IF(FSE_isError(FSE_buildCTable_wksp(
                bs->entropy.fse.matchlengthCTable,
                matchlengthNCount, matchlengthMaxValue, matchlengthLog,
                workspace, HUF_WORKSPACE_SIZE)),
            dictionary_corrupted, "");
        dictPtr += matchlengthHeaderSize;
    }
 
    {   short litlengthNCount[MaxLL+1];
        unsigned litlengthMaxValue = MaxLL, litlengthLog;
        size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
        RETURN_ERROR_IF(FSE_isError(litlengthHeaderSize), dictionary_corrupted, "");
        RETURN_ERROR_IF(litlengthLog > LLFSELog, dictionary_corrupted, "");
        /* Every literal length code must have non-zero probability */
        FORWARD_IF_ERROR( ZSTD_checkDictNCount(litlengthNCount, litlengthMaxValue, MaxLL), "");
        RETURN_ERROR_IF(FSE_isError(FSE_buildCTable_wksp(
                bs->entropy.fse.litlengthCTable,
                litlengthNCount, litlengthMaxValue, litlengthLog,
                workspace, HUF_WORKSPACE_SIZE)),
            dictionary_corrupted, "");
        dictPtr += litlengthHeaderSize;
    }
 
    RETURN_ERROR_IF(dictPtr+12 > dictEnd, dictionary_corrupted, "");
    bs->rep[0] = MEM_readLE32(dictPtr+0);
    bs->rep[1] = MEM_readLE32(dictPtr+4);
    bs->rep[2] = MEM_readLE32(dictPtr+8);
    dictPtr += 12;
 
    return dictPtr - (const BYTE*)dict;
}

Referenced by ZSTD_loadZstdDictionary().

ZSTD_matchState_dictMode()

MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode

(

const ZSTD_matchState_t *

ms

)

ZSTD_matchState_dictMode(): Inspects the provided matchState and figures out what dictMode should be passed to the compressor.

Definition at line 734 of file zstd_compress_internal.h.

{

Referenced by ZSTD_buildSeqStore(), and ZSTD_ldm_blockCompress().

ZSTD_minGain()

MEM_STATIC size_t ZSTD_minGain	(	size_t	srcSize,
		ZSTD_strategy	strat
	)

Definition at line 388 of file zstd_compress_internal.h.

Referenced by ZSTD_compressBlock_targetCBlockSize_body(), ZSTD_compressLiterals(), and ZSTD_compressSequences().

ZSTD_MLcode()

MEM_STATIC U32 ZSTD_MLcode

(

U32

mlBase

)

Definition at line 309 of file zstd_compress_internal.h.

                                                                       : LL_Code[litLength];
}
 
/* ZSTD_MLcode() :
 * note : mlBase = matchLength - MINMATCH;
 *        because it's the format it's stored in seqStore->sequences */
MEM_STATIC U32 ZSTD_MLcode(U32 mlBase)
{
    static const BYTE ML_Code[128] = { 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,
                                      16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
                                      32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
                                      38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
                                      40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,

Referenced by ZSTD_getMatchPrice(), ZSTD_seqToCodes(), and ZSTD_updateStats().

ZSTD_NbCommonBytes()

static unsigned ZSTD_NbCommonBytes ( size_t  val )

static

Definition at line 490 of file zstd_compress_internal.h.

{
    if (MEM_isLittleEndian()) {
        if (MEM_64bits()) {
#       if defined(_MSC_VER) && defined(_WIN64)
            unsigned long r = 0;
            return _BitScanForward64( &r, (U64)val ) ? (unsigned)(r >> 3) : 0;
#       elif defined(__GNUC__) && (__GNUC__ >= 4)
            return (__builtin_ctzll((U64)val) >> 3);
#       else
            static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
                                                     0, 3, 1, 3, 1, 4, 2, 7,
                                                     0, 2, 3, 6, 1, 5, 3, 5,
                                                     1, 3, 4, 4, 2, 5, 6, 7,
                                                     7, 0, 1, 2, 3, 3, 4, 6,
                                                     2, 6, 5, 5, 3, 4, 5, 6,
                                                     7, 1, 2, 4, 6, 4, 4, 5,
                                                     7, 2, 6, 5, 7, 6, 7, 7 };
            return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
#       endif
        } else { /* 32 bits */
#       if defined(_MSC_VER)
            unsigned long r=0;
            return _BitScanForward( &r, (U32)val ) ? (unsigned)(r >> 3) : 0;
#       elif defined(__GNUC__) && (__GNUC__ >= 3)
            return (__builtin_ctz((U32)val) >> 3);
#       else
            static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
                                                     3, 2, 2, 1, 3, 2, 0, 1,
                                                     3, 3, 1, 2, 2, 2, 2, 0,
                                                     3, 1, 2, 0, 1, 0, 1, 1 };
            return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
#       endif
        }
    } else {  /* Big Endian CPU */
        if (MEM_64bits()) {
#       if defined(_MSC_VER) && defined(_WIN64)
            unsigned long r = 0;
            return _BitScanReverse64( &r, val ) ? (unsigned)(r >> 3) : 0;
#       elif defined(__GNUC__) && (__GNUC__ >= 4)
            return (__builtin_clzll(val) >> 3);
#       else
            unsigned r;
            const unsigned n32 = sizeof(size_t)*4;   /* calculate this way due to compiler complaining in 32-bits mode */
            if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
            if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
            r += (!val);
            return r;
#       endif
        } else { /* 32 bits */
#       if defined(_MSC_VER)
            unsigned long r = 0;
            return _BitScanReverse( &r, (unsigned long)val ) ? (unsigned)(r >> 3) : 0;
#       elif defined(__GNUC__) && (__GNUC__ >= 3)
            return (__builtin_clz((U32)val) >> 3);
#       else
            unsigned r;

ZSTD_noCompressBlock()

MEM_STATIC size_t ZSTD_noCompressBlock	(	void *	dst,
		size_t	dstCapacity,
		const void *	src,
		size_t	srcSize,
		U32	lastBlock
	)

Definition at line 363 of file zstd_compress_internal.h.

{
    U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw)<<1) + (U32)(srcSize << 3);

Referenced by ZSTD_compress_frameChunk(), ZSTD_compressBlock_targetCBlockSize_body(), and ZSTD_compressSubBlock_multi().

ZSTD_referenceExternalSequences()

size_t ZSTD_referenceExternalSequences	(	ZSTD_CCtx *	cctx,
		rawSeq *	seq,
		size_t	nbSeq
	)

Definition at line 2717 of file zstd_compress.c.

{
    RETURN_ERROR_IF(cctx->stage != ZSTDcs_init, stage_wrong,
                    "wrong cctx stage");
    RETURN_ERROR_IF(cctx->appliedParams.ldmParams.enableLdm,
                    parameter_unsupported,
                    "incompatible with ldm");
    cctx->externSeqStore.seq = seq;
    cctx->externSeqStore.size = nbSeq;
    cctx->externSeqStore.capacity = nbSeq;
    cctx->externSeqStore.pos = 0;
    return 0;
}

Referenced by ZSTD_resetCCtx_internal().

ZSTD_reset_compressedBlockState()

void ZSTD_reset_compressedBlockState

(

ZSTD_compressedBlockState_t *

bs

)

Definition at line 1282 of file zstd_compress.c.

{
    int i;
    for (i = 0; i < ZSTD_REP_NUM; ++i)
        bs->rep[i] = repStartValue[i];
    bs->entropy.huf.repeatMode = HUF_repeat_none;
    bs->entropy.fse.offcode_repeatMode = FSE_repeat_none;
    bs->entropy.fse.matchlength_repeatMode = FSE_repeat_none;
    bs->entropy.fse.litlength_repeatMode = FSE_repeat_none;
}

Referenced by ZSTD_compress_insertDictionary(), ZSTD_initCDict_internal(), and ZSTD_resetCCtx_internal().

ZSTD_resetSeqStore()

void ZSTD_resetSeqStore

(

seqStore_t *

ssPtr

)

Definition at line 2233 of file zstd_compress.c.

{
    ssPtr->lit = ssPtr->litStart;
    ssPtr->sequences = ssPtr->sequencesStart;
    ssPtr->longLengthID = 0;
}

Referenced by ZSTD_buildSeqStore(), and ZSTD_initStats_ultra().

ZSTD_rleCompressBlock()

MEM_STATIC size_t ZSTD_rleCompressBlock	(	void *	dst,
		size_t	dstCapacity,
		BYTE	src,
		size_t	srcSize,
		U32	lastBlock
	)

Definition at line 373 of file zstd_compress_internal.h.

{
    BYTE* const op = (BYTE*)dst;

Referenced by ZSTD_compressBlock_targetCBlockSize_body().

ZSTD_rollingHash_append()

static U64 ZSTD_rollingHash_append ( U64  hash, void const *  buf, size_t  size  )

static

ZSTD_rollingHash_append() : Add the buffer to the hash value.

Definition at line 655 of file zstd_compress_internal.h.

{
    BYTE const* istart = (BYTE const*)buf;
    size_t pos;

ZSTD_rollingHash_compute()

MEM_STATIC U64 ZSTD_rollingHash_compute	(	void const *	buf,
		size_t	size
	)

ZSTD_rollingHash_compute() : Compute the rolling hash value of the buffer.

Definition at line 669 of file zstd_compress_internal.h.

Referenced by ZSTD_ldm_fillHashTable(), and ZSTD_ldm_generateSequences_internal().

ZSTD_rollingHash_primePower()

MEM_STATIC U64 ZSTD_rollingHash_primePower

(

U32

length

)

ZSTD_rollingHash_primePower() : Compute the primePower to be passed to ZSTD_rollingHash_rotate() for a hash over a window of length bytes.

Definition at line 678 of file zstd_compress_internal.h.

Referenced by ZSTD_resetCCtx_internal().

ZSTD_rollingHash_rotate()

MEM_STATIC U64 ZSTD_rollingHash_rotate	(	U64	hash,
		BYTE	toRemove,
		BYTE	toAdd,
		U64	primePower
	)

ZSTD_rollingHash_rotate() : Rotate the rolling hash by one byte.

Definition at line 686 of file zstd_compress_internal.h.

Referenced by ZSTD_ldm_fillLdmHashTable(), and ZSTD_ldm_generateSequences_internal().

ZSTD_safecopyLiterals()

static void ZSTD_safecopyLiterals ( BYTE *  op, BYTE const *  ip, BYTE const *const  iend, BYTE const *  ilimit_w  )

static

ZSTD_safecopyLiterals() : memcpy() function that won't read beyond more than WILDCOPY_OVERLENGTH bytes past ilimit_w. Only called when the sequence ends past ilimit_w, so it only needs to be optimized for single large copies.

Definition at line 416 of file zstd_compress_internal.h.

                                                                                                          {
    assert(iend > ilimit_w);
    if (ip <= ilimit_w) {

ZSTD_selectBlockCompressor()

ZSTD_blockCompressor ZSTD_selectBlockCompressor	(	ZSTD_strategy	strat,
		ZSTD_dictMode_e	dictMode
	)

Definition at line 2183 of file zstd_compress.c.

{
    static const ZSTD_blockCompressor blockCompressor[3][ZSTD_STRATEGY_MAX+1] = {
        { ZSTD_compressBlock_fast  /* default for 0 */,
          ZSTD_compressBlock_fast,
          ZSTD_compressBlock_doubleFast,
          ZSTD_compressBlock_greedy,
          ZSTD_compressBlock_lazy,
          ZSTD_compressBlock_lazy2,
          ZSTD_compressBlock_btlazy2,
          ZSTD_compressBlock_btopt,
          ZSTD_compressBlock_btultra,
          ZSTD_compressBlock_btultra2 },
        { ZSTD_compressBlock_fast_extDict  /* default for 0 */,
          ZSTD_compressBlock_fast_extDict,
          ZSTD_compressBlock_doubleFast_extDict,
          ZSTD_compressBlock_greedy_extDict,
          ZSTD_compressBlock_lazy_extDict,
          ZSTD_compressBlock_lazy2_extDict,
          ZSTD_compressBlock_btlazy2_extDict,
          ZSTD_compressBlock_btopt_extDict,
          ZSTD_compressBlock_btultra_extDict,
          ZSTD_compressBlock_btultra_extDict },
        { ZSTD_compressBlock_fast_dictMatchState  /* default for 0 */,
          ZSTD_compressBlock_fast_dictMatchState,
          ZSTD_compressBlock_doubleFast_dictMatchState,
          ZSTD_compressBlock_greedy_dictMatchState,
          ZSTD_compressBlock_lazy_dictMatchState,
          ZSTD_compressBlock_lazy2_dictMatchState,
          ZSTD_compressBlock_btlazy2_dictMatchState,
          ZSTD_compressBlock_btopt_dictMatchState,
          ZSTD_compressBlock_btultra_dictMatchState,
          ZSTD_compressBlock_btultra_dictMatchState }
    };
    ZSTD_blockCompressor selectedCompressor;
    ZSTD_STATIC_ASSERT((unsigned)ZSTD_fast == 1);
 
    assert(ZSTD_cParam_withinBounds(ZSTD_c_strategy, strat));
    selectedCompressor = blockCompressor[(int)dictMode][(int)strat];
    assert(selectedCompressor != NULL);
    return selectedCompressor;
}

Referenced by ZSTD_buildSeqStore(), and ZSTD_ldm_blockCompress().

ZSTD_storeSeq()

HINT_INLINE UNUSED_ATTR void ZSTD_storeSeq	(	seqStore_t *	seqStorePtr,
		size_t	litLength,
		const BYTE *	literals,
		const BYTE *	litLimit,
		U32	offCode,
		size_t	mlBase
	)

ZSTD_storeSeq() : Store a sequence (litlen, litPtr, offCode and mlBase) into seqStore_t. offCode : distance to match + ZSTD_REP_MOVE (values <= ZSTD_REP_MOVE are repCodes). mlBase : matchLength - MINMATCH Allowed to overread literals up to litLimit.

Definition at line 433 of file zstd_compress_internal.h.

              : distance to match + ZSTD_REP_MOVE (values <= ZSTD_REP_MOVE are repCodes).
 *  `mlBase` : matchLength - MINMATCH
 *  Allowed to overread literals up to litLimit.
*/
HINT_INLINE UNUSED_ATTR
void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const BYTE* literals, const BYTE* litLimit, U32 offCode, size_t mlBase)
{
    BYTE const* const litLimit_w = litLimit - WILDCOPY_OVERLENGTH;
    BYTE const* const litEnd = literals + litLength;
#if defined(DEBUGLEVEL) && (DEBUGLEVEL >= 6)
    static const BYTE* g_start = NULL;
    if (g_start==NULL) g_start = (const BYTE*)literals;  /* note : index only works for compression within a single segment */
    {   U32 const pos = (U32)((const BYTE*)literals - g_start);
        DEBUGLOG(6, "Cpos%7u :%3u literals, match%4u bytes at offCode%7u",
               pos, (U32)litLength, (U32)mlBase+MINMATCH, (U32)offCode);
    }
#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);
    assert(literals + litLength <= litLimit);
    if (litEnd <= litLimit_w) {
        /* Common case we can use wildcopy.
     * First copy 16 bytes, because literals are likely short.
     */
        assert(WILDCOPY_OVERLENGTH >= 16);
        ZSTD_copy16(seqStorePtr->lit, literals);
        if (litLength > 16) {
            ZSTD_wildcopy(seqStorePtr->lit+16, literals+16, (ptrdiff_t)litLength-16, ZSTD_no_overlap);
        }
    } else {
        ZSTD_safecopyLiterals(seqStorePtr->lit, literals, litEnd, litLimit_w);
    }
    seqStorePtr->lit += litLength;
 
    /* literal Length */
    if (litLength>0xFFFF) {
        assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
        seqStorePtr->longLengthID = 1;
        seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
    }
    seqStorePtr->sequences[0].litLength = (U16)litLength;
 
    /* match offset */
    seqStorePtr->sequences[0].offset = offCode + 1;
 
    /* match Length */
    if (mlBase>0xFFFF) {
        assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
        seqStorePtr->longLengthID = 2;

Referenced by ZSTD_compressBlock_doubleFast_extDict_generic(), ZSTD_compressBlock_doubleFast_generic(), ZSTD_compressBlock_fast_dictMatchState_generic(), ZSTD_compressBlock_fast_extDict_generic(), ZSTD_compressBlock_fast_generic(), ZSTD_compressBlock_lazy_extDict_generic(), ZSTD_compressBlock_lazy_generic(), ZSTD_compressBlock_opt_generic(), and ZSTD_ldm_blockCompress().

ZSTD_updateRep()

MEM_STATIC repcodes_t ZSTD_updateRep	(	U32 const	rep[3],
		U32 const	offset,
		U32 const	ll0
	)

Definition at line 327 of file zstd_compress_internal.h.

                          {
    U32 rep[3];
} repcodes_t;
 
MEM_STATIC repcodes_t ZSTD_updateRep(U32 const rep[3], U32 const offset, U32 const ll0)
{
    repcodes_t newReps;
    if (offset >= ZSTD_REP_NUM) {  /* full offset */
        newReps.rep[2] = rep[1];
        newReps.rep[1] = rep[0];
        newReps.rep[0] = offset - ZSTD_REP_MOVE;
    } else {   /* repcode */
        U32 const repCode = offset + ll0;
        if (repCode > 0) {  /* note : if repCode==0, no change */
            U32 const currentOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode];
            newReps.rep[2] = (repCode >= 2) ? rep[1] : rep[2];
            newReps.rep[1] = rep[0];
            newReps.rep[0] = currentOffset;

Referenced by ZSTD_compressBlock_opt_generic(), and ZSTD_compressSubBlock_multi().

ZSTD_window_clear()

MEM_STATIC void ZSTD_window_clear

(

ZSTD_window_t *

window

)

ZSTD_window_clear(): Clears the window containing the history by simply setting it to empty.

Definition at line 711 of file zstd_compress_internal.h.

{

Referenced by ZSTD_invalidateMatchState(), ZSTD_resetCCtx_byAttachingCDict(), and ZSTD_resetCCtx_internal().

ZSTD_window_correctOverflow()

MEM_STATIC U32 ZSTD_window_correctOverflow	(	ZSTD_window_t *	window,
		U32	cycleLog,
		U32	maxDist,
		void const *	src
	)

ZSTD_window_correctOverflow(): Reduces the indices to protect from index overflow. Returns the correction made to the indices, which must be applied to every stored index.

The least significant cycleLog bits of the indices must remain the same, which may be 0. Every index up to maxDist in the past must be valid. NOTE: (maxDist & cycleMask) must be zero.

Definition at line 765 of file zstd_compress_internal.h.

       : (maxDist & cycleMask) must be zero.
 */
MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t* window, U32 cycleLog,
                                           U32 maxDist, void const* src)
{
    /* preemptive overflow correction:
     * 1. correction is large enough:
     *    lowLimit > (3<<29) ==> current > 3<<29 + 1<<windowLog
     *    1<<windowLog <= newCurrent < 1<<chainLog + 1<<windowLog
     *
     *    current - newCurrent
     *    > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog)
     *    > (3<<29) - (1<<chainLog)
     *    > (3<<29) - (1<<30)             (NOTE: chainLog <= 30)
     *    > 1<<29
     *
     * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow:
     *    After correction, current is less than (1<<chainLog + 1<<windowLog).
     *    In 64-bit mode we are safe, because we have 64-bit ptrdiff_t.
     *    In 32-bit mode we are safe, because (chainLog <= 29), so
     *    ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32.
     * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32:
     *    windowLog <= 31 ==> 3<<29 + 1<<windowLog < 7<<29 < 1<<32.
     */
    U32 const cycleMask = (1U << cycleLog) - 1;
    U32 const current = (U32)((BYTE const*)src - window->base);
    U32 const currentCycle0 = current & cycleMask;
    /* Exclude zero so that newCurrent - maxDist >= 1. */
    U32 const currentCycle1 = currentCycle0 == 0 ? (1U << cycleLog) : currentCycle0;
    U32 const newCurrent = currentCycle1 + maxDist;
    U32 const correction = current - newCurrent;
    assert((maxDist & cycleMask) == 0);
    assert(current > newCurrent);
    /* Loose bound, should be around 1<<29 (see above) */
    assert(correction > 1<<28);
 
    window->base += correction;
    window->dictBase += correction;
    if (window->lowLimit <= correction) window->lowLimit = 1;
    else window->lowLimit -= correction;
    if (window->dictLimit <= correction) window->dictLimit = 1;
    else window->dictLimit -= correction;
 
    /* Ensure we can still reference the full window. */
    assert(newCurrent >= maxDist);
    assert(newCurrent - maxDist >= 1);
    /* Ensure that lowLimit and dictLimit didn't underflow. */
    assert(window->lowLimit <= newCurrent);

Referenced by ZSTD_ldm_generateSequences(), and ZSTD_overflowCorrectIfNeeded().

ZSTD_window_enforceMaxDist()

MEM_STATIC void ZSTD_window_enforceMaxDist	(	ZSTD_window_t *	window,
		const void *	blockEnd,
		U32	maxDist,
		U32 *	loadedDictEndPtr,
		const ZSTD_matchState_t **	dictMatchStatePtr
	)

ZSTD_window_enforceMaxDist(): Updates lowLimit so that: (srcEnd - base) - lowLimit == maxDist + loadedDictEnd

It ensures index is valid as long as index >= lowLimit. This must be called before a block compression call.

loadedDictEnd is only defined if a dictionary is in use for current compression. As the name implies, loadedDictEnd represents the index at end of dictionary. The value lies within context's referential, it can be directly compared to blockEndIdx.

If loadedDictEndPtr is NULL, no dictionary is in use, and we use loadedDictEnd == 0. If loadedDictEndPtr is not NULL, we set it to zero after updating lowLimit. 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.

Definition at line 842 of file zstd_compress_internal.h.

{
    U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
    U32 const loadedDictEnd = (loadedDictEndPtr != NULL) ? *loadedDictEndPtr : 0;
    DEBUGLOG(5, "ZSTD_window_enforceMaxDist: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
                (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;

Referenced by ZSTD_ldm_generateSequences().

ZSTD_window_hasExtDict()

MEM_STATIC U32 ZSTD_window_hasExtDict

(

ZSTD_window_t const

window

)

ZSTD_window_hasExtDict(): Returns non-zero if the window has a non-empty extDict.

Definition at line 724 of file zstd_compress_internal.h.

Referenced by ZSTD_invalidateRepCodes(), ZSTD_ldm_generateSequences_internal(), and ZSTD_matchState_dictMode().

ZSTD_window_init()

MEM_STATIC void ZSTD_window_init

(

ZSTD_window_t *

window

)

Definition at line 915 of file zstd_compress_internal.h.

               {
            if (*loadedDictEndPtr != 0) {
                DEBUGLOG(6, "dictionary considered valid for current block");
    }   }   }
}
 
MEM_STATIC void ZSTD_window_init(ZSTD_window_t* window) {
    memset(window, 0, sizeof(*window));

Referenced by ZSTD_reset_matchState(), and ZSTD_resetCCtx_internal().

ZSTD_window_needOverflowCorrection()

MEM_STATIC U32 ZSTD_window_needOverflowCorrection	(	ZSTD_window_t const	window,
		void const *	srcEnd
	)

ZSTD_window_needOverflowCorrection(): Returns non-zero if the indices are getting too large and need overflow protection.

Definition at line 748 of file zstd_compress_internal.h.

Referenced by ZSTD_ldm_generateSequences(), and ZSTD_overflowCorrectIfNeeded().

ZSTD_window_update()

MEM_STATIC U32 ZSTD_window_update	(	ZSTD_window_t *	window,
		void const *	src,
		size_t	srcSize
	)

ZSTD_window_update(): Updates the window by appending [src, src + srcSize) to the window. If it is not contiguous, the current prefix becomes the extDict, and we forget about the extDict. Handles overlap of the prefix and extDict. Returns non-zero if the segment is contiguous.

Definition at line 931 of file zstd_compress_internal.h.

                       :
 * Updates the window by appending [src, src + srcSize) to the window.
 * If it is not contiguous, the current prefix becomes the extDict, and we
 * forget about the extDict. Handles overlap of the prefix and extDict.
 * Returns non-zero if the segment is contiguous.
 */
MEM_STATIC U32 ZSTD_window_update(ZSTD_window_t* window,
                                  void const* src, size_t srcSize)
{
    BYTE const* const ip = (BYTE const*)src;
    U32 contiguous = 1;
    DEBUGLOG(5, "ZSTD_window_update");
    if (srcSize == 0)
        return contiguous;
    assert(window->base != NULL);
    assert(window->dictBase != NULL);
    /* Check if blocks follow each other */
    if (src != window->nextSrc) {
        /* not contiguous */
        size_t const distanceFromBase = (size_t)(window->nextSrc - window->base);
        DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit);
        window->lowLimit = window->dictLimit;
        assert(distanceFromBase == (size_t)(U32)distanceFromBase);  /* should never overflow */
        window->dictLimit = (U32)distanceFromBase;
        window->dictBase = window->base;
        window->base = ip - distanceFromBase;
        /* ms->nextToUpdate = window->dictLimit; */
        if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit;   /* too small extDict */
        contiguous = 0;
    }
    window->nextSrc = ip + srcSize;
    /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
    if ( (ip+srcSize > window->dictBase + window->lowLimit)
       & (ip < window->dictBase + window->dictLimit)) {
        ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase;

Referenced by ZSTD_compressContinue_internal(), and ZSTD_loadDictionaryContent().

ZSTD_writeLastEmptyBlock()

size_t ZSTD_writeLastEmptyBlock	(	void *	dst,
		size_t	dstCapacity
	)

Definition at line 2707 of file zstd_compress.c.

{
    RETURN_ERROR_IF(dstCapacity < ZSTD_blockHeaderSize, dstSize_tooSmall,
                    "dst buf is too small to write frame trailer empty block.");
    {   U32 const cBlockHeader24 = 1 /*lastBlock*/ + (((U32)bt_raw)<<1);  /* 0 size */
        MEM_writeLE24(dst, cBlockHeader24);
        return ZSTD_blockHeaderSize;
    }
}

Variable Documentation

prime3bytes

const U32 prime3bytes = 506832829U

static

Definition at line 599 of file zstd_compress_internal.h.

Referenced by ZSTD_hash4Ptr().

prime4bytes

const U32 prime4bytes = 2654435761U

static

Definition at line 603 of file zstd_compress_internal.h.

Referenced by ZSTD_hash5Ptr().

prime5bytes

const U64 prime5bytes = 889523592379ULL

static

Definition at line 607 of file zstd_compress_internal.h.

Referenced by ZSTD_hash6Ptr().

prime6bytes

const U64 prime6bytes = 227718039650203ULL

static

Definition at line 611 of file zstd_compress_internal.h.

Referenced by ZSTD_hash7Ptr().

prime7bytes

const U64 prime7bytes = 58295818150454627ULL

static

Definition at line 615 of file zstd_compress_internal.h.

Referenced by ZSTD_hash8Ptr().

prime8bytes

const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL

static

Definition at line 619 of file zstd_compress_internal.h.

Referenced by ZSTD_rollingHash_append().