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 709 of file zstd_compress_internal.h.

ZSTD_CURRENT_MAX

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

Definition at line 707 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 656 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 292 of file zstd_compress_internal.h.

ZSTD_matchState_t

typedef struct ZSTD_matchState_t ZSTD_matchState_t

Definition at line 135 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 49 of file zstd_compress_internal.h.

{ ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;

ZSTD_cStreamStage

enum ZSTD_cStreamStage

Enumerator
zcss_init
zcss_load
zcss_flush

Definition at line 50 of file zstd_compress_internal.h.

{ zcss_init=0, zcss_load, zcss_flush } ZSTD_cStreamStage;

ZSTD_dictMode_e

enum ZSTD_dictMode_e

Enumerator
ZSTD_noDict
ZSTD_extDict
ZSTD_dictMatchState

Definition at line 289 of file zstd_compress_internal.h.

{ ZSTD_noDict = 0, ZSTD_extDict = 1, ZSTD_dictMatchState = 2 } ZSTD_dictMode_e;

ZSTD_dictTableLoadMethod_e

enum ZSTD_dictTableLoadMethod_e

Enumerator
ZSTD_dtlm_fast
ZSTD_dtlm_full

Definition at line 287 of file zstd_compress_internal.h.

{ ZSTD_dtlm_fast, ZSTD_dtlm_full } ZSTD_dictTableLoadMethod_e;

ZSTD_OptPrice_e

enum ZSTD_OptPrice_e

Enumerator
zop_dynamic
zop_predef

Definition at line 98 of file zstd_compress_internal.h.

{ zop_dynamic=0, zop_predef } ZSTD_OptPrice_e;

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 893 of file zstd_compress_internal.h.

{
    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");
    }   }   }
}

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 561 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);
    }   }
    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);
}

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 587 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);
    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);
}

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 357 of file zstd_compress_internal.h.

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

Referenced by ZSTD_minGain(), and 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 402 of file zstd_compress_internal.h.

{
    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);
    }
}

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 976 of file zstd_compress_internal.h.

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

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 989 of file zstd_compress_internal.h.

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

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 606 of file zstd_compress_internal.h.

{ return ((u << (32-24)) * prime3bytes)  >> (32-h) ; }

Referenced by ZSTD_hash3Ptr().

ZSTD_hash3Ptr()

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

Definition at line 607 of file zstd_compress_internal.h.

{ return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */

Referenced by ZSTD_insertAndFindFirstIndexHash3().

ZSTD_hash4()

static U32 ZSTD_hash4 ( U32  u, U32  h  )

static

Definition at line 610 of file zstd_compress_internal.h.

{ return (u * prime4bytes) >> (32-h) ; }

Referenced by ZSTD_hash4Ptr().

ZSTD_hash4Ptr()

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

static

Definition at line 611 of file zstd_compress_internal.h.

{ return ZSTD_hash4(MEM_read32(ptr), h); }

Referenced by ZSTD_hashPtr().

ZSTD_hash5()

static size_t ZSTD_hash5 ( U64  u, U32  h  )

static

Definition at line 614 of file zstd_compress_internal.h.

{ return (size_t)(((u  << (64-40)) * prime5bytes) >> (64-h)) ; }

Referenced by ZSTD_hash5Ptr().

ZSTD_hash5Ptr()

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

static

Definition at line 615 of file zstd_compress_internal.h.

{ return ZSTD_hash5(MEM_readLE64(p), h); }

Referenced by ZSTD_hashPtr().

ZSTD_hash6()

static size_t ZSTD_hash6 ( U64  u, U32  h  )

static

Definition at line 618 of file zstd_compress_internal.h.

{ return (size_t)(((u  << (64-48)) * prime6bytes) >> (64-h)) ; }

Referenced by ZSTD_hash6Ptr().

ZSTD_hash6Ptr()

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

static

Definition at line 619 of file zstd_compress_internal.h.

{ return ZSTD_hash6(MEM_readLE64(p), h); }

Referenced by ZSTD_hashPtr().

ZSTD_hash7()

static size_t ZSTD_hash7 ( U64  u, U32  h  )

static

Definition at line 622 of file zstd_compress_internal.h.

{ return (size_t)(((u  << (64-56)) * prime7bytes) >> (64-h)) ; }

Referenced by ZSTD_hash7Ptr().

ZSTD_hash7Ptr()

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

static

Definition at line 623 of file zstd_compress_internal.h.

{ return ZSTD_hash7(MEM_readLE64(p), h); }

Referenced by ZSTD_hashPtr().

ZSTD_hash8()

static size_t ZSTD_hash8 ( U64  u, U32  h  )

static

Definition at line 626 of file zstd_compress_internal.h.

{ return (size_t)(((u) * prime8bytes) >> (64-h)) ; }

Referenced by ZSTD_hash8Ptr().

ZSTD_hash8Ptr()

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

static

Definition at line 627 of file zstd_compress_internal.h.

{ return ZSTD_hash8(MEM_readLE64(p), h); }

Referenced by ZSTD_hashPtr().

ZSTD_hashPtr()

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

Definition at line 629 of file zstd_compress_internal.h.

{
    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);
    }
}

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 645 of file zstd_compress_internal.h.

{
    U64 power = 1;
    while (exponent) {
      if (exponent & 1) power *= base;
      exponent >>= 1;
      base *= base;
    }
    return power;
}

Referenced by ZSTD_rollingHash_primePower().

ZSTD_LLcode()

MEM_STATIC U32 ZSTD_LLcode

(

U32

litLength

)

Definition at line 298 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,
                                      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];
}

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 740 of file zstd_compress_internal.h.

{
    return ZSTD_window_hasExtDict(ms->window) ?
        ZSTD_extDict :
        ms->dictMatchState != NULL ?
            ZSTD_dictMatchState :
            ZSTD_noDict;
}

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 394 of file zstd_compress_internal.h.

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

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

ZSTD_MLcode()

MEM_STATIC U32 ZSTD_MLcode

(

U32

mlBase

)

Definition at line 315 of file zstd_compress_internal.h.

{
    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];
}

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

ZSTD_NbCommonBytes()

static unsigned ZSTD_NbCommonBytes ( size_t  val )

static

Definition at line 496 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;
            if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
            r += (!val);
            return r;
#       endif
    }   }
}

Referenced by ZSTD_count().

ZSTD_noCompressBlock()

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

Definition at line 369 of file zstd_compress_internal.h.

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

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 379 of file zstd_compress_internal.h.

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

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 661 of file zstd_compress_internal.h.

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

Referenced by ZSTD_rollingHash_compute().

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 675 of file zstd_compress_internal.h.

{
    return ZSTD_rollingHash_append(0, buf, size);
}

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 684 of file zstd_compress_internal.h.

{
    return ZSTD_ipow(prime8bytes, length - 1);
}

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 692 of file zstd_compress_internal.h.

{
    hash -= (toRemove + ZSTD_ROLL_HASH_CHAR_OFFSET) * primePower;
    hash *= prime8bytes;
    hash += toAdd + ZSTD_ROLL_HASH_CHAR_OFFSET;
    return hash;
}

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 422 of file zstd_compress_internal.h.

                                                                                                          {
    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++;
}

Referenced by ZSTD_storeSeq().

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 439 of file zstd_compress_internal.h.

{
    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++;
}

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 333 of file zstd_compress_internal.h.

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

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 717 of file zstd_compress_internal.h.

{
    size_t const endT = (size_t)(window->nextSrc - window->base);
    U32 const end = (U32)endT;

    window->lowLimit = end;
    window->dictLimit = end;
}

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 771 of file zstd_compress_internal.h.

{
    /* 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;
}

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 848 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;
        }
        /* On reaching window size, dictionaries are invalidated */
        if (loadedDictEndPtr) *loadedDictEndPtr = 0;
        if (dictMatchStatePtr) *dictMatchStatePtr = NULL;
    }
}

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 730 of file zstd_compress_internal.h.

{
    return window.lowLimit < window.dictLimit;
}

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 921 of file zstd_compress_internal.h.

                                                        {
    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 */
}

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 754 of file zstd_compress_internal.h.

{
    U32 const current = (U32)((BYTE const*)srcEnd - window.base);
    return current > ZSTD_CURRENT_MAX;
}

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 937 of file zstd_compress_internal.h.

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

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 605 of file zstd_compress_internal.h.

Referenced by ZSTD_hash3().

prime4bytes

const U32 prime4bytes = 2654435761U

static

Definition at line 609 of file zstd_compress_internal.h.

Referenced by ZSTD_hash4().

prime5bytes

const U64 prime5bytes = 889523592379ULL

static

Definition at line 613 of file zstd_compress_internal.h.

Referenced by ZSTD_hash5().

prime6bytes

const U64 prime6bytes = 227718039650203ULL

static

Definition at line 617 of file zstd_compress_internal.h.

Referenced by ZSTD_hash6().

prime7bytes

const U64 prime7bytes = 58295818150454627ULL

static

Definition at line 621 of file zstd_compress_internal.h.

Referenced by ZSTD_hash7().

prime8bytes

const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL

static

Definition at line 625 of file zstd_compress_internal.h.

Referenced by ZSTD_hash8(), ZSTD_rollingHash_append(), ZSTD_rollingHash_primePower(), and ZSTD_rollingHash_rotate().