diff options
Diffstat (limited to 'thirdparty/zstd/compress/zstd_compress.c')
| -rw-r--r-- | thirdparty/zstd/compress/zstd_compress.c | 1617 |
1 files changed, 973 insertions, 644 deletions
diff --git a/thirdparty/zstd/compress/zstd_compress.c b/thirdparty/zstd/compress/zstd_compress.c index 8d1629246d..2aa26da4cd 100644 --- a/thirdparty/zstd/compress/zstd_compress.c +++ b/thirdparty/zstd/compress/zstd_compress.c @@ -21,6 +21,7 @@ * Dependencies ***************************************/ #include <string.h> /* memset */ +#include "cpu.h" #include "mem.h" #define FSE_STATIC_LINKING_ONLY /* FSE_encodeSymbol */ #include "fse.h" @@ -49,7 +50,13 @@ struct ZSTD_CDict_s { void* dictBuffer; const void* dictContent; size_t dictContentSize; - ZSTD_CCtx* refContext; + void* workspace; + size_t workspaceSize; + ZSTD_matchState_t matchState; + ZSTD_compressedBlockState_t cBlockState; + ZSTD_compressionParameters cParams; + ZSTD_customMem customMem; + U32 dictID; }; /* typedef'd to ZSTD_CDict within "zstd.h" */ ZSTD_CCtx* ZSTD_createCCtx(void) @@ -59,18 +66,17 @@ ZSTD_CCtx* ZSTD_createCCtx(void) ZSTD_CCtx* ZSTD_createCCtx_advanced(ZSTD_customMem customMem) { - ZSTD_CCtx* cctx; - - if (!customMem.customAlloc ^ !customMem.customFree) return NULL; - - cctx = (ZSTD_CCtx*) ZSTD_calloc(sizeof(ZSTD_CCtx), customMem); - if (!cctx) return NULL; - cctx->customMem = customMem; - cctx->requestedParams.compressionLevel = ZSTD_CLEVEL_DEFAULT; - cctx->requestedParams.fParams.contentSizeFlag = 1; ZSTD_STATIC_ASSERT(zcss_init==0); ZSTD_STATIC_ASSERT(ZSTD_CONTENTSIZE_UNKNOWN==(0ULL - 1)); - return cctx; + if (!customMem.customAlloc ^ !customMem.customFree) return NULL; + { ZSTD_CCtx* const cctx = (ZSTD_CCtx*)ZSTD_calloc(sizeof(ZSTD_CCtx), customMem); + if (!cctx) return NULL; + cctx->customMem = customMem; + cctx->requestedParams.compressionLevel = ZSTD_CLEVEL_DEFAULT; + cctx->requestedParams.fParams.contentSizeFlag = 1; + cctx->bmi2 = ZSTD_cpuid_bmi2(ZSTD_cpuid()); + return cctx; + } } ZSTD_CCtx* ZSTD_initStaticCCtx(void *workspace, size_t workspaceSize) @@ -83,11 +89,16 @@ ZSTD_CCtx* ZSTD_initStaticCCtx(void *workspace, size_t workspaceSize) cctx->workSpace = (void*)(cctx+1); cctx->workSpaceSize = workspaceSize - sizeof(ZSTD_CCtx); - /* entropy space (never moves) */ - if (cctx->workSpaceSize < sizeof(ZSTD_entropyCTables_t)) return NULL; + /* statically sized space. entropyWorkspace never moves (but prev/next block swap places) */ + if (cctx->workSpaceSize < HUF_WORKSPACE_SIZE + 2 * sizeof(ZSTD_compressedBlockState_t)) return NULL; assert(((size_t)cctx->workSpace & (sizeof(void*)-1)) == 0); /* ensure correct alignment */ - cctx->entropy = (ZSTD_entropyCTables_t*)cctx->workSpace; - + cctx->blockState.prevCBlock = (ZSTD_compressedBlockState_t*)cctx->workSpace; + cctx->blockState.nextCBlock = cctx->blockState.prevCBlock + 1; + { + void* const ptr = cctx->blockState.nextCBlock + 1; + cctx->entropyWorkspace = (U32*)ptr; + } + cctx->bmi2 = ZSTD_cpuid_bmi2(ZSTD_cpuid()); return cctx; } @@ -95,13 +106,10 @@ size_t ZSTD_freeCCtx(ZSTD_CCtx* cctx) { if (cctx==NULL) return 0; /* support free on NULL */ if (cctx->staticSize) return ERROR(memory_allocation); /* not compatible with static CCtx */ - ZSTD_free(cctx->workSpace, cctx->customMem); - cctx->workSpace = NULL; - ZSTD_freeCDict(cctx->cdictLocal); - cctx->cdictLocal = NULL; + ZSTD_free(cctx->workSpace, cctx->customMem); cctx->workSpace = NULL; + ZSTD_freeCDict(cctx->cdictLocal); cctx->cdictLocal = NULL; #ifdef ZSTD_MULTITHREAD - ZSTDMT_freeCCtx(cctx->mtctx); - cctx->mtctx = NULL; + ZSTDMT_freeCCtx(cctx->mtctx); cctx->mtctx = NULL; #endif ZSTD_free(cctx, cctx->customMem); return 0; /* reserved as a potential error code in the future */ @@ -122,10 +130,6 @@ static size_t ZSTD_sizeof_mtctx(const ZSTD_CCtx* cctx) size_t ZSTD_sizeof_CCtx(const ZSTD_CCtx* cctx) { if (cctx==NULL) return 0; /* support sizeof on NULL */ - DEBUGLOG(3, "sizeof(*cctx) : %u", (U32)sizeof(*cctx)); - DEBUGLOG(3, "workSpaceSize (including streaming buffers): %u", (U32)cctx->workSpaceSize); - DEBUGLOG(3, "inner cdict : %u", (U32)ZSTD_sizeof_CDict(cctx->cdictLocal)); - DEBUGLOG(3, "inner MTCTX : %u", (U32)ZSTD_sizeof_mtctx(cctx)); return sizeof(*cctx) + cctx->workSpaceSize + ZSTD_sizeof_CDict(cctx->cdictLocal) + ZSTD_sizeof_mtctx(cctx); @@ -139,37 +143,19 @@ size_t ZSTD_sizeof_CStream(const ZSTD_CStream* zcs) /* private API call, for dictBuilder only */ const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx) { return &(ctx->seqStore); } -#define ZSTD_CLEVEL_CUSTOM 999 - -static ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams( - ZSTD_CCtx_params CCtxParams, U64 srcSizeHint, size_t dictSize) -{ - DEBUGLOG(4, "ZSTD_getCParamsFromCCtxParams: srcSize = %u, dictSize = %u", - (U32)srcSizeHint, (U32)dictSize); - return (CCtxParams.compressionLevel == ZSTD_CLEVEL_CUSTOM) ? - CCtxParams.cParams : - ZSTD_getCParams(CCtxParams.compressionLevel, srcSizeHint, dictSize); -} - -static void ZSTD_cLevelToCCtxParams_srcSize(ZSTD_CCtx_params* CCtxParams, U64 srcSize) -{ - DEBUGLOG(4, "ZSTD_cLevelToCCtxParams_srcSize: srcSize = %u", - (U32)srcSize); - CCtxParams->cParams = ZSTD_getCParamsFromCCtxParams(*CCtxParams, srcSize, 0); - CCtxParams->compressionLevel = ZSTD_CLEVEL_CUSTOM; -} - -static void ZSTD_cLevelToCParams(ZSTD_CCtx* cctx) -{ - DEBUGLOG(4, "ZSTD_cLevelToCParams: level=%i", cctx->requestedParams.compressionLevel); - ZSTD_cLevelToCCtxParams_srcSize( - &cctx->requestedParams, cctx->pledgedSrcSizePlusOne-1); -} - -static void ZSTD_cLevelToCCtxParams(ZSTD_CCtx_params* CCtxParams) -{ - DEBUGLOG(4, "ZSTD_cLevelToCCtxParams"); - ZSTD_cLevelToCCtxParams_srcSize(CCtxParams, ZSTD_CONTENTSIZE_UNKNOWN); +ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams( + const ZSTD_CCtx_params* CCtxParams, U64 srcSizeHint, size_t dictSize) +{ + ZSTD_compressionParameters cParams = ZSTD_getCParams(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.searchLength) cParams.searchLength = CCtxParams->cParams.searchLength; + if (CCtxParams->cParams.targetLength) cParams.targetLength = CCtxParams->cParams.targetLength; + if (CCtxParams->cParams.strategy) cParams.strategy = CCtxParams->cParams.strategy; + return cParams; } static ZSTD_CCtx_params ZSTD_makeCCtxParamsFromCParams( @@ -178,7 +164,9 @@ static ZSTD_CCtx_params ZSTD_makeCCtxParamsFromCParams( ZSTD_CCtx_params cctxParams; memset(&cctxParams, 0, sizeof(cctxParams)); cctxParams.cParams = cParams; - cctxParams.compressionLevel = ZSTD_CLEVEL_CUSTOM; + cctxParams.compressionLevel = ZSTD_CLEVEL_DEFAULT; /* should not matter, as all cParams are presumed properly defined */ + assert(!ZSTD_checkCParams(cParams)); + cctxParams.fParams.contentSizeFlag = 1; return cctxParams; } @@ -192,6 +180,7 @@ static ZSTD_CCtx_params* ZSTD_createCCtxParams_advanced( if (!params) { return NULL; } params->customMem = customMem; params->compressionLevel = ZSTD_CLEVEL_DEFAULT; + params->fParams.contentSizeFlag = 1; return params; } @@ -207,36 +196,41 @@ size_t ZSTD_freeCCtxParams(ZSTD_CCtx_params* params) return 0; } -size_t ZSTD_resetCCtxParams(ZSTD_CCtx_params* params) +size_t ZSTD_CCtxParams_reset(ZSTD_CCtx_params* params) { - return ZSTD_initCCtxParams(params, ZSTD_CLEVEL_DEFAULT); + return ZSTD_CCtxParams_init(params, ZSTD_CLEVEL_DEFAULT); } -size_t ZSTD_initCCtxParams(ZSTD_CCtx_params* cctxParams, int compressionLevel) { +size_t ZSTD_CCtxParams_init(ZSTD_CCtx_params* cctxParams, int compressionLevel) { if (!cctxParams) { return ERROR(GENERIC); } memset(cctxParams, 0, sizeof(*cctxParams)); cctxParams->compressionLevel = compressionLevel; + cctxParams->fParams.contentSizeFlag = 1; return 0; } -size_t ZSTD_initCCtxParams_advanced(ZSTD_CCtx_params* cctxParams, ZSTD_parameters params) +size_t ZSTD_CCtxParams_init_advanced(ZSTD_CCtx_params* cctxParams, ZSTD_parameters params) { if (!cctxParams) { return ERROR(GENERIC); } CHECK_F( ZSTD_checkCParams(params.cParams) ); memset(cctxParams, 0, sizeof(*cctxParams)); cctxParams->cParams = params.cParams; cctxParams->fParams = params.fParams; - cctxParams->compressionLevel = ZSTD_CLEVEL_CUSTOM; + cctxParams->compressionLevel = ZSTD_CLEVEL_DEFAULT; /* should not matter, as all cParams are presumed properly defined */ + assert(!ZSTD_checkCParams(params.cParams)); return 0; } +/* ZSTD_assignParamsToCCtxParams() : + * params is presumed valid at this stage */ static ZSTD_CCtx_params ZSTD_assignParamsToCCtxParams( ZSTD_CCtx_params cctxParams, ZSTD_parameters params) { ZSTD_CCtx_params ret = cctxParams; ret.cParams = params.cParams; ret.fParams = params.fParams; - ret.compressionLevel = ZSTD_CLEVEL_CUSTOM; + ret.compressionLevel = ZSTD_CLEVEL_DEFAULT; /* should not matter, as all cParams are presumed properly defined */ + assert(!ZSTD_checkCParams(params.cParams)); return ret; } @@ -245,10 +239,49 @@ static ZSTD_CCtx_params ZSTD_assignParamsToCCtxParams( return ERROR(parameter_outOfBound); \ } } + +static int ZSTD_isUpdateAuthorized(ZSTD_cParameter param) +{ + switch(param) + { + case ZSTD_p_compressionLevel: + case ZSTD_p_hashLog: + case ZSTD_p_chainLog: + case ZSTD_p_searchLog: + case ZSTD_p_minMatch: + case ZSTD_p_targetLength: + case ZSTD_p_compressionStrategy: + case ZSTD_p_compressLiterals: + return 1; + + case ZSTD_p_format: + case ZSTD_p_windowLog: + case ZSTD_p_contentSizeFlag: + case ZSTD_p_checksumFlag: + case ZSTD_p_dictIDFlag: + case ZSTD_p_forceMaxWindow : + case ZSTD_p_nbWorkers: + case ZSTD_p_jobSize: + case ZSTD_p_overlapSizeLog: + case ZSTD_p_enableLongDistanceMatching: + case ZSTD_p_ldmHashLog: + case ZSTD_p_ldmMinMatch: + case ZSTD_p_ldmBucketSizeLog: + case ZSTD_p_ldmHashEveryLog: + default: + return 0; + } +} + size_t ZSTD_CCtx_setParameter(ZSTD_CCtx* cctx, ZSTD_cParameter param, unsigned value) { DEBUGLOG(4, "ZSTD_CCtx_setParameter (%u, %u)", (U32)param, value); - if (cctx->streamStage != zcss_init) return ERROR(stage_wrong); + if (cctx->streamStage != zcss_init) { + if (ZSTD_isUpdateAuthorized(param)) { + cctx->cParamsChanged = 1; + } else { + return ERROR(stage_wrong); + } } switch(param) { @@ -267,9 +300,9 @@ size_t ZSTD_CCtx_setParameter(ZSTD_CCtx* cctx, ZSTD_cParameter param, unsigned v case ZSTD_p_targetLength: case ZSTD_p_compressionStrategy: if (cctx->cdict) return ERROR(stage_wrong); - if (value>0) ZSTD_cLevelToCParams(cctx); /* Can optimize if srcSize is known */ return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value); + case ZSTD_p_compressLiterals: case ZSTD_p_contentSizeFlag: case ZSTD_p_checksumFlag: case ZSTD_p_dictIDFlag: @@ -280,23 +313,17 @@ size_t ZSTD_CCtx_setParameter(ZSTD_CCtx* cctx, ZSTD_cParameter param, unsigned v * default : 0 when using a CDict, 1 when using a Prefix */ return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value); - case ZSTD_p_nbThreads: - if ((value > 1) && cctx->staticSize) { + case ZSTD_p_nbWorkers: + if ((value>0) && cctx->staticSize) { return ERROR(parameter_unsupported); /* MT not compatible with static alloc */ } return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value); case ZSTD_p_jobSize: - return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value); - case ZSTD_p_overlapSizeLog: return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value); case ZSTD_p_enableLongDistanceMatching: - if (cctx->cdict) return ERROR(stage_wrong); - if (value>0) ZSTD_cLevelToCParams(cctx); - return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value); - case ZSTD_p_ldmHashLog: case ZSTD_p_ldmMinMatch: case ZSTD_p_ldmBucketSizeLog: @@ -320,69 +347,62 @@ size_t ZSTD_CCtxParam_setParameter( CCtxParams->format = (ZSTD_format_e)value; return (size_t)CCtxParams->format; - case ZSTD_p_compressionLevel : - if ((int)value > ZSTD_maxCLevel()) value = ZSTD_maxCLevel(); - if (value) /* 0 : does not change current level */ - CCtxParams->compressionLevel = value; - return CCtxParams->compressionLevel; + case ZSTD_p_compressionLevel : { + int cLevel = (int)value; /* cast expected to restore negative sign */ + if (cLevel > ZSTD_maxCLevel()) cLevel = ZSTD_maxCLevel(); + if (cLevel) { /* 0 : does not change current level */ + CCtxParams->disableLiteralCompression = (cLevel<0); /* negative levels disable huffman */ + CCtxParams->compressionLevel = cLevel; + } + if (CCtxParams->compressionLevel >= 0) return CCtxParams->compressionLevel; + return 0; /* return type (size_t) cannot represent negative values */ + } case ZSTD_p_windowLog : - DEBUGLOG(4, "ZSTD_CCtxParam_setParameter: set windowLog=%u", value); - if (value) { /* 0 : does not change current windowLog */ + if (value>0) /* 0 => use default */ CLAMPCHECK(value, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX); - ZSTD_cLevelToCCtxParams(CCtxParams); - CCtxParams->cParams.windowLog = value; - } + CCtxParams->cParams.windowLog = value; return CCtxParams->cParams.windowLog; case ZSTD_p_hashLog : - if (value) { /* 0 : does not change current hashLog */ + if (value>0) /* 0 => use default */ CLAMPCHECK(value, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX); - ZSTD_cLevelToCCtxParams(CCtxParams); - CCtxParams->cParams.hashLog = value; - } + CCtxParams->cParams.hashLog = value; return CCtxParams->cParams.hashLog; case ZSTD_p_chainLog : - if (value) { /* 0 : does not change current chainLog */ + if (value>0) /* 0 => use default */ CLAMPCHECK(value, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX); - ZSTD_cLevelToCCtxParams(CCtxParams); - CCtxParams->cParams.chainLog = value; - } + CCtxParams->cParams.chainLog = value; return CCtxParams->cParams.chainLog; case ZSTD_p_searchLog : - if (value) { /* 0 : does not change current searchLog */ + if (value>0) /* 0 => use default */ CLAMPCHECK(value, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX); - ZSTD_cLevelToCCtxParams(CCtxParams); - CCtxParams->cParams.searchLog = value; - } + CCtxParams->cParams.searchLog = value; return value; case ZSTD_p_minMatch : - if (value) { /* 0 : does not change current minMatch length */ + if (value>0) /* 0 => use default */ CLAMPCHECK(value, ZSTD_SEARCHLENGTH_MIN, ZSTD_SEARCHLENGTH_MAX); - ZSTD_cLevelToCCtxParams(CCtxParams); - CCtxParams->cParams.searchLength = value; - } + CCtxParams->cParams.searchLength = value; return CCtxParams->cParams.searchLength; case ZSTD_p_targetLength : - if (value) { /* 0 : does not change current sufficient_len */ - CLAMPCHECK(value, ZSTD_TARGETLENGTH_MIN, ZSTD_TARGETLENGTH_MAX); - ZSTD_cLevelToCCtxParams(CCtxParams); - CCtxParams->cParams.targetLength = value; - } + /* all values are valid. 0 => use default */ + CCtxParams->cParams.targetLength = value; return CCtxParams->cParams.targetLength; case ZSTD_p_compressionStrategy : - if (value) { /* 0 : does not change currentstrategy */ + if (value>0) /* 0 => use default */ CLAMPCHECK(value, (unsigned)ZSTD_fast, (unsigned)ZSTD_btultra); - ZSTD_cLevelToCCtxParams(CCtxParams); - CCtxParams->cParams.strategy = (ZSTD_strategy)value; - } + CCtxParams->cParams.strategy = (ZSTD_strategy)value; return (size_t)CCtxParams->cParams.strategy; + case ZSTD_p_compressLiterals: + CCtxParams->disableLiteralCompression = !value; + return !CCtxParams->disableLiteralCompression; + case ZSTD_p_contentSizeFlag : /* Content size written in frame header _when known_ (default:1) */ DEBUGLOG(4, "set content size flag = %u", (value>0)); @@ -396,27 +416,25 @@ size_t ZSTD_CCtxParam_setParameter( case ZSTD_p_dictIDFlag : /* When applicable, dictionary's dictID is provided in frame header (default:1) */ DEBUGLOG(4, "set dictIDFlag = %u", (value>0)); - CCtxParams->fParams.noDictIDFlag = (value == 0); + CCtxParams->fParams.noDictIDFlag = !value; return !CCtxParams->fParams.noDictIDFlag; case ZSTD_p_forceMaxWindow : CCtxParams->forceWindow = (value > 0); return CCtxParams->forceWindow; - case ZSTD_p_nbThreads : - if (value == 0) return CCtxParams->nbThreads; + case ZSTD_p_nbWorkers : #ifndef ZSTD_MULTITHREAD - if (value > 1) return ERROR(parameter_unsupported); - return 1; + if (value>0) return ERROR(parameter_unsupported); + return 0; #else - return ZSTDMT_CCtxParam_setNbThreads(CCtxParams, value); + return ZSTDMT_CCtxParam_setNbWorkers(CCtxParams, value); #endif case ZSTD_p_jobSize : #ifndef ZSTD_MULTITHREAD return ERROR(parameter_unsupported); #else - if (CCtxParams->nbThreads <= 1) return ERROR(parameter_unsupported); return ZSTDMT_CCtxParam_setMTCtxParameter(CCtxParams, ZSTDMT_p_jobSize, value); #endif @@ -424,44 +442,36 @@ size_t ZSTD_CCtxParam_setParameter( #ifndef ZSTD_MULTITHREAD return ERROR(parameter_unsupported); #else - if (CCtxParams->nbThreads <= 1) return ERROR(parameter_unsupported); return ZSTDMT_CCtxParam_setMTCtxParameter(CCtxParams, ZSTDMT_p_overlapSectionLog, value); #endif case ZSTD_p_enableLongDistanceMatching : - if (value) { - ZSTD_cLevelToCCtxParams(CCtxParams); - CCtxParams->cParams.windowLog = ZSTD_LDM_DEFAULT_WINDOW_LOG; - } - return ZSTD_ldm_initializeParameters(&CCtxParams->ldmParams, value); + CCtxParams->ldmParams.enableLdm = (value>0); + return CCtxParams->ldmParams.enableLdm; case ZSTD_p_ldmHashLog : - if (value) { /* 0 : does not change current ldmHashLog */ + if (value>0) /* 0 ==> auto */ CLAMPCHECK(value, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX); - CCtxParams->ldmParams.hashLog = value; - } + CCtxParams->ldmParams.hashLog = value; return CCtxParams->ldmParams.hashLog; case ZSTD_p_ldmMinMatch : - if (value) { /* 0 : does not change current ldmMinMatch */ + if (value>0) /* 0 ==> default */ CLAMPCHECK(value, ZSTD_LDM_MINMATCH_MIN, ZSTD_LDM_MINMATCH_MAX); - CCtxParams->ldmParams.minMatchLength = value; - } + CCtxParams->ldmParams.minMatchLength = value; return CCtxParams->ldmParams.minMatchLength; case ZSTD_p_ldmBucketSizeLog : - if (value > ZSTD_LDM_BUCKETSIZELOG_MAX) { + if (value > ZSTD_LDM_BUCKETSIZELOG_MAX) return ERROR(parameter_outOfBound); - } CCtxParams->ldmParams.bucketSizeLog = value; - return value; + return CCtxParams->ldmParams.bucketSizeLog; case ZSTD_p_ldmHashEveryLog : - if (value > ZSTD_WINDOWLOG_MAX - ZSTD_HASHLOG_MIN) { + if (value > ZSTD_WINDOWLOG_MAX - ZSTD_HASHLOG_MIN) return ERROR(parameter_outOfBound); - } CCtxParams->ldmParams.hashEveryLog = value; - return value; + return CCtxParams->ldmParams.hashEveryLog; default: return ERROR(parameter_unsupported); } @@ -470,6 +480,9 @@ size_t ZSTD_CCtxParam_setParameter( /** ZSTD_CCtx_setParametersUsingCCtxParams() : * just applies `params` into `cctx` * no action is performed, parameters are merely stored. + * If ZSTDMT is enabled, parameters are pushed to cctx->mtctx. + * This is possible even if a compression is ongoing. + * In which case, new parameters will be applied on the fly, starting with next compression job. */ size_t ZSTD_CCtx_setParametersUsingCCtxParams( ZSTD_CCtx* cctx, const ZSTD_CCtx_params* params) @@ -478,7 +491,6 @@ size_t ZSTD_CCtx_setParametersUsingCCtxParams( if (cctx->cdict) return ERROR(stage_wrong); cctx->requestedParams = *params; - return 0; } @@ -492,7 +504,7 @@ ZSTDLIB_API size_t ZSTD_CCtx_setPledgedSrcSize(ZSTD_CCtx* cctx, unsigned long lo size_t ZSTD_CCtx_loadDictionary_advanced( ZSTD_CCtx* cctx, const void* dict, size_t dictSize, - ZSTD_dictLoadMethod_e dictLoadMethod, ZSTD_dictMode_e dictMode) + ZSTD_dictLoadMethod_e dictLoadMethod, ZSTD_dictContentType_e dictContentType) { if (cctx->streamStage != zcss_init) return ERROR(stage_wrong); if (cctx->staticSize) return ERROR(memory_allocation); /* no malloc for static CCtx */ @@ -503,10 +515,10 @@ size_t ZSTD_CCtx_loadDictionary_advanced( cctx->cdict = NULL; } else { ZSTD_compressionParameters const cParams = - ZSTD_getCParamsFromCCtxParams(cctx->requestedParams, cctx->pledgedSrcSizePlusOne-1, dictSize); + ZSTD_getCParamsFromCCtxParams(&cctx->requestedParams, cctx->pledgedSrcSizePlusOne-1, dictSize); cctx->cdictLocal = ZSTD_createCDict_advanced( dict, dictSize, - dictLoadMethod, dictMode, + dictLoadMethod, dictContentType, cParams, cctx->customMem); cctx->cdict = cctx->cdictLocal; if (cctx->cdictLocal == NULL) @@ -519,13 +531,13 @@ ZSTDLIB_API size_t ZSTD_CCtx_loadDictionary_byReference( ZSTD_CCtx* cctx, const void* dict, size_t dictSize) { return ZSTD_CCtx_loadDictionary_advanced( - cctx, dict, dictSize, ZSTD_dlm_byRef, ZSTD_dm_auto); + cctx, dict, dictSize, ZSTD_dlm_byRef, ZSTD_dct_auto); } ZSTDLIB_API size_t ZSTD_CCtx_loadDictionary(ZSTD_CCtx* cctx, const void* dict, size_t dictSize) { return ZSTD_CCtx_loadDictionary_advanced( - cctx, dict, dictSize, ZSTD_dlm_byCopy, ZSTD_dm_auto); + cctx, dict, dictSize, ZSTD_dlm_byCopy, ZSTD_dct_auto); } @@ -539,17 +551,17 @@ size_t ZSTD_CCtx_refCDict(ZSTD_CCtx* cctx, const ZSTD_CDict* cdict) size_t ZSTD_CCtx_refPrefix(ZSTD_CCtx* cctx, const void* prefix, size_t prefixSize) { - return ZSTD_CCtx_refPrefix_advanced(cctx, prefix, prefixSize, ZSTD_dm_rawContent); + return ZSTD_CCtx_refPrefix_advanced(cctx, prefix, prefixSize, ZSTD_dct_rawContent); } size_t ZSTD_CCtx_refPrefix_advanced( - ZSTD_CCtx* cctx, const void* prefix, size_t prefixSize, ZSTD_dictMode_e dictMode) + ZSTD_CCtx* cctx, const void* prefix, size_t prefixSize, ZSTD_dictContentType_e dictContentType) { if (cctx->streamStage != zcss_init) return ERROR(stage_wrong); cctx->cdict = NULL; /* prefix discards any prior cdict */ cctx->prefixDict.dict = prefix; cctx->prefixDict.dictSize = prefixSize; - cctx->prefixDict.dictMode = dictMode; + cctx->prefixDict.dictContentType = dictContentType; return 0; } @@ -577,7 +589,8 @@ size_t ZSTD_checkCParams(ZSTD_compressionParameters cParams) CLAMPCHECK(cParams.hashLog, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX); CLAMPCHECK(cParams.searchLog, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX); CLAMPCHECK(cParams.searchLength, ZSTD_SEARCHLENGTH_MIN, ZSTD_SEARCHLENGTH_MAX); - CLAMPCHECK(cParams.targetLength, ZSTD_TARGETLENGTH_MIN, ZSTD_TARGETLENGTH_MAX); + if ((U32)(cParams.targetLength) < ZSTD_TARGETLENGTH_MIN) + return ERROR(parameter_unsupported); if ((U32)(cParams.strategy) > (U32)ZSTD_btultra) return ERROR(parameter_unsupported); return 0; @@ -597,7 +610,7 @@ static ZSTD_compressionParameters ZSTD_clampCParams(ZSTD_compressionParameters c CLAMP(cParams.hashLog, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX); CLAMP(cParams.searchLog, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX); CLAMP(cParams.searchLength, ZSTD_SEARCHLENGTH_MIN, ZSTD_SEARCHLENGTH_MAX); - CLAMP(cParams.targetLength, ZSTD_TARGETLENGTH_MIN, ZSTD_TARGETLENGTH_MAX); + if ((U32)(cParams.targetLength) < ZSTD_TARGETLENGTH_MIN) cParams.targetLength = ZSTD_TARGETLENGTH_MIN; if ((U32)(cParams.strategy) > (U32)ZSTD_btultra) cParams.strategy = ZSTD_btultra; return cParams; } @@ -653,36 +666,43 @@ ZSTD_compressionParameters ZSTD_adjustCParams(ZSTD_compressionParameters cPar, u return ZSTD_adjustCParams_internal(cPar, srcSize, dictSize); } +static size_t ZSTD_sizeof_matchState(ZSTD_compressionParameters const* cParams, const U32 forCCtx) +{ + size_t const chainSize = (cParams->strategy == ZSTD_fast) ? 0 : ((size_t)1 << cParams->chainLog); + size_t const hSize = ((size_t)1) << cParams->hashLog; + U32 const hashLog3 = (forCCtx && cParams->searchLength==3) ? MIN(ZSTD_HASHLOG3_MAX, cParams->windowLog) : 0; + size_t const h3Size = ((size_t)1) << hashLog3; + size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32); + size_t const optPotentialSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits)) * sizeof(U32) + + (ZSTD_OPT_NUM+1) * (sizeof(ZSTD_match_t)+sizeof(ZSTD_optimal_t)); + size_t const optSpace = (forCCtx && ((cParams->strategy == ZSTD_btopt) || + (cParams->strategy == ZSTD_btultra))) + ? optPotentialSpace + : 0; + DEBUGLOG(4, "chainSize: %u - hSize: %u - h3Size: %u", + (U32)chainSize, (U32)hSize, (U32)h3Size); + return tableSpace + optSpace; +} + size_t ZSTD_estimateCCtxSize_usingCCtxParams(const ZSTD_CCtx_params* params) { /* Estimate CCtx size is supported for single-threaded compression only. */ - if (params->nbThreads > 1) { return ERROR(GENERIC); } + if (params->nbWorkers > 0) { return ERROR(GENERIC); } { ZSTD_compressionParameters const cParams = - ZSTD_getCParamsFromCCtxParams(*params, 0, 0); + ZSTD_getCParamsFromCCtxParams(params, 0, 0); size_t const blockSize = MIN(ZSTD_BLOCKSIZE_MAX, (size_t)1 << cParams.windowLog); U32 const divider = (cParams.searchLength==3) ? 3 : 4; size_t const maxNbSeq = blockSize / divider; size_t const tokenSpace = blockSize + 11*maxNbSeq; - size_t const chainSize = - (cParams.strategy == ZSTD_fast) ? 0 : ((size_t)1 << cParams.chainLog); - size_t const hSize = ((size_t)1) << cParams.hashLog; - U32 const hashLog3 = (cParams.searchLength>3) ? - 0 : MIN(ZSTD_HASHLOG3_MAX, cParams.windowLog); - size_t const h3Size = ((size_t)1) << hashLog3; - size_t const entropySpace = sizeof(ZSTD_entropyCTables_t); - size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32); + size_t const entropySpace = HUF_WORKSPACE_SIZE; + size_t const blockStateSpace = 2 * sizeof(ZSTD_compressedBlockState_t); + size_t const matchStateSize = ZSTD_sizeof_matchState(&cParams, /* forCCtx */ 1); - size_t const optBudget = - ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits))*sizeof(U32) - + (ZSTD_OPT_NUM+1)*(sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t)); - size_t const optSpace = ((cParams.strategy == ZSTD_btopt) || (cParams.strategy == ZSTD_btultra)) ? optBudget : 0; + size_t const ldmSpace = ZSTD_ldm_getTableSize(params->ldmParams); + size_t const ldmSeqSpace = ZSTD_ldm_getMaxNbSeq(params->ldmParams, blockSize) * sizeof(rawSeq); - size_t const ldmSpace = params->ldmParams.enableLdm ? - ZSTD_ldm_getTableSize(params->ldmParams.hashLog, - params->ldmParams.bucketSizeLog) : 0; - - size_t const neededSpace = entropySpace + tableSpace + tokenSpace + - optSpace + ldmSpace; + size_t const neededSpace = entropySpace + blockStateSpace + tokenSpace + + matchStateSize + ldmSpace + ldmSeqSpace; DEBUGLOG(5, "sizeof(ZSTD_CCtx) : %u", (U32)sizeof(ZSTD_CCtx)); DEBUGLOG(5, "estimate workSpace : %u", (U32)neededSpace); @@ -696,15 +716,26 @@ size_t ZSTD_estimateCCtxSize_usingCParams(ZSTD_compressionParameters cParams) return ZSTD_estimateCCtxSize_usingCCtxParams(¶ms); } -size_t ZSTD_estimateCCtxSize(int compressionLevel) +static size_t ZSTD_estimateCCtxSize_internal(int compressionLevel) { ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, 0, 0); return ZSTD_estimateCCtxSize_usingCParams(cParams); } +size_t ZSTD_estimateCCtxSize(int compressionLevel) +{ + int level; + size_t memBudget = 0; + for (level=1; level<=compressionLevel; level++) { + size_t const newMB = ZSTD_estimateCCtxSize_internal(level); + if (newMB > memBudget) memBudget = newMB; + } + return memBudget; +} + size_t ZSTD_estimateCStreamSize_usingCCtxParams(const ZSTD_CCtx_params* params) { - if (params->nbThreads > 1) { return ERROR(GENERIC); } + if (params->nbWorkers > 0) { return ERROR(GENERIC); } { size_t const CCtxSize = ZSTD_estimateCCtxSize_usingCCtxParams(params); size_t const blockSize = MIN(ZSTD_BLOCKSIZE_MAX, (size_t)1 << params->cParams.windowLog); size_t const inBuffSize = ((size_t)1 << params->cParams.windowLog) + blockSize; @@ -721,11 +752,44 @@ size_t ZSTD_estimateCStreamSize_usingCParams(ZSTD_compressionParameters cParams) return ZSTD_estimateCStreamSize_usingCCtxParams(¶ms); } -size_t ZSTD_estimateCStreamSize(int compressionLevel) { +static size_t ZSTD_estimateCStreamSize_internal(int compressionLevel) { ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, 0, 0); return ZSTD_estimateCStreamSize_usingCParams(cParams); } +size_t ZSTD_estimateCStreamSize(int compressionLevel) { + int level; + size_t memBudget = 0; + for (level=1; level<=compressionLevel; level++) { + size_t const newMB = ZSTD_estimateCStreamSize_internal(level); + if (newMB > memBudget) memBudget = newMB; + } + return memBudget; +} + +/* ZSTD_getFrameProgression(): + * tells how much data has been consumed (input) and produced (output) for current frame. + * able to count progression inside worker threads (non-blocking mode). + */ +ZSTD_frameProgression ZSTD_getFrameProgression(const ZSTD_CCtx* cctx) +{ +#ifdef ZSTD_MULTITHREAD + if (cctx->appliedParams.nbWorkers > 0) { + return ZSTDMT_getFrameProgression(cctx->mtctx); + } +#endif + { ZSTD_frameProgression fp; + size_t const buffered = (cctx->inBuff == NULL) ? 0 : + cctx->inBuffPos - cctx->inToCompress; + if (buffered) assert(cctx->inBuffPos >= cctx->inToCompress); + assert(buffered <= ZSTD_BLOCKSIZE_MAX); + fp.ingested = cctx->consumedSrcSize + buffered; + fp.consumed = cctx->consumedSrcSize; + fp.produced = cctx->producedCSize; + return fp; +} } + + static U32 ZSTD_equivalentCParams(ZSTD_compressionParameters cParams1, ZSTD_compressionParameters cParams2) { @@ -761,9 +825,9 @@ static U32 ZSTD_sufficientBuff(size_t bufferSize1, size_t blockSize1, size_t const windowSize2 = MAX(1, (size_t)MIN(((U64)1 << cParams2.windowLog), pledgedSrcSize)); size_t const blockSize2 = MIN(ZSTD_BLOCKSIZE_MAX, windowSize2); size_t const neededBufferSize2 = (buffPol2==ZSTDb_buffered) ? windowSize2 + blockSize2 : 0; - DEBUGLOG(4, "ZSTD_sufficientBuff: windowSize2=%u from wlog=%u", + DEBUGLOG(4, "ZSTD_sufficientBuff: is windowSize2=%u <= wlog1=%u", (U32)windowSize2, cParams2.windowLog); - DEBUGLOG(4, "ZSTD_sufficientBuff: blockSize2 %u <=? blockSize1 %u", + DEBUGLOG(4, "ZSTD_sufficientBuff: is blockSize2=%u <= blockSize1=%u", (U32)blockSize2, (U32)blockSize1); return (blockSize2 <= blockSize1) /* seqStore space depends on blockSize */ & (neededBufferSize2 <= bufferSize1); @@ -782,37 +846,101 @@ static U32 ZSTD_equivalentParams(ZSTD_CCtx_params params1, ZSTD_sufficientBuff(buffSize1, blockSize1, buffPol2, params2.cParams, pledgedSrcSize); } +static void ZSTD_reset_compressedBlockState(ZSTD_compressedBlockState_t* bs) +{ + int i; + for (i = 0; i < ZSTD_REP_NUM; ++i) + bs->rep[i] = repStartValue[i]; + bs->entropy.hufCTable_repeatMode = HUF_repeat_none; + bs->entropy.offcode_repeatMode = FSE_repeat_none; + bs->entropy.matchlength_repeatMode = FSE_repeat_none; + bs->entropy.litlength_repeatMode = FSE_repeat_none; +} + +/*! ZSTD_invalidateMatchState() + * Invalidate all the matches in the match finder tables. + * Requires nextSrc and base to be set (can be NULL). + */ +static void ZSTD_invalidateMatchState(ZSTD_matchState_t* ms) +{ + ZSTD_window_clear(&ms->window); + + ms->nextToUpdate = ms->window.dictLimit + 1; + ms->loadedDictEnd = 0; + ms->opt.litLengthSum = 0; /* force reset of btopt stats */ +} + /*! ZSTD_continueCCtx() : * reuse CCtx without reset (note : requires no dictionary) */ static size_t ZSTD_continueCCtx(ZSTD_CCtx* cctx, ZSTD_CCtx_params params, U64 pledgedSrcSize) { - U32 const end = (U32)(cctx->nextSrc - cctx->base); size_t const windowSize = MAX(1, (size_t)MIN(((U64)1 << params.cParams.windowLog), pledgedSrcSize)); size_t const blockSize = MIN(ZSTD_BLOCKSIZE_MAX, windowSize); - DEBUGLOG(4, "ZSTD_continueCCtx"); + DEBUGLOG(4, "ZSTD_continueCCtx: re-use context in place"); cctx->blockSize = blockSize; /* previous block size could be different even for same windowLog, due to pledgedSrcSize */ cctx->appliedParams = params; cctx->pledgedSrcSizePlusOne = pledgedSrcSize+1; cctx->consumedSrcSize = 0; + cctx->producedCSize = 0; if (pledgedSrcSize == ZSTD_CONTENTSIZE_UNKNOWN) cctx->appliedParams.fParams.contentSizeFlag = 0; DEBUGLOG(4, "pledged content size : %u ; flag : %u", (U32)pledgedSrcSize, cctx->appliedParams.fParams.contentSizeFlag); - cctx->lowLimit = end; - cctx->dictLimit = end; - cctx->nextToUpdate = end+1; cctx->stage = ZSTDcs_init; cctx->dictID = 0; - cctx->loadedDictEnd = 0; - { int i; for (i=0; i<ZSTD_REP_NUM; i++) cctx->seqStore.rep[i] = repStartValue[i]; } - cctx->optState.litLengthSum = 0; /* force reset of btopt stats */ + if (params.ldmParams.enableLdm) + ZSTD_window_clear(&cctx->ldmState.window); + ZSTD_referenceExternalSequences(cctx, NULL, 0); + ZSTD_invalidateMatchState(&cctx->blockState.matchState); + ZSTD_reset_compressedBlockState(cctx->blockState.prevCBlock); XXH64_reset(&cctx->xxhState, 0); return 0; } typedef enum { ZSTDcrp_continue, ZSTDcrp_noMemset } ZSTD_compResetPolicy_e; +static void* ZSTD_reset_matchState(ZSTD_matchState_t* ms, void* ptr, ZSTD_compressionParameters const* cParams, ZSTD_compResetPolicy_e const crp, U32 const forCCtx) +{ + size_t const chainSize = (cParams->strategy == ZSTD_fast) ? 0 : ((size_t)1 << cParams->chainLog); + size_t const hSize = ((size_t)1) << cParams->hashLog; + U32 const hashLog3 = (forCCtx && cParams->searchLength==3) ? MIN(ZSTD_HASHLOG3_MAX, cParams->windowLog) : 0; + size_t const h3Size = ((size_t)1) << hashLog3; + size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32); + + assert(((size_t)ptr & 3) == 0); + + ms->hashLog3 = hashLog3; + memset(&ms->window, 0, sizeof(ms->window)); + ZSTD_invalidateMatchState(ms); + + /* opt parser space */ + if (forCCtx && ((cParams->strategy == ZSTD_btopt) | (cParams->strategy == ZSTD_btultra))) { + DEBUGLOG(4, "reserving optimal parser space"); + ms->opt.litFreq = (U32*)ptr; + ms->opt.litLengthFreq = ms->opt.litFreq + (1<<Litbits); + ms->opt.matchLengthFreq = ms->opt.litLengthFreq + (MaxLL+1); + ms->opt.offCodeFreq = ms->opt.matchLengthFreq + (MaxML+1); + ptr = ms->opt.offCodeFreq + (MaxOff+1); + ms->opt.matchTable = (ZSTD_match_t*)ptr; + ptr = ms->opt.matchTable + ZSTD_OPT_NUM+1; + ms->opt.priceTable = (ZSTD_optimal_t*)ptr; + ptr = ms->opt.priceTable + ZSTD_OPT_NUM+1; + } + + /* table Space */ + DEBUGLOG(4, "reset table : %u", crp!=ZSTDcrp_noMemset); + assert(((size_t)ptr & 3) == 0); /* ensure ptr is properly aligned */ + if (crp!=ZSTDcrp_noMemset) memset(ptr, 0, tableSpace); /* reset tables only */ + ms->hashTable = (U32*)(ptr); + ms->chainTable = ms->hashTable + hSize; + ms->hashTable3 = ms->chainTable + chainSize; + ptr = ms->hashTable3 + h3Size; + + assert(((size_t)ptr & 3) == 0); + return ptr; +} + /*! ZSTD_resetCCtx_internal() : note : `params` are assumed fully validated at this stage */ static size_t ZSTD_resetCCtx_internal(ZSTD_CCtx* zc, @@ -830,19 +958,14 @@ static size_t ZSTD_resetCCtx_internal(ZSTD_CCtx* zc, zbuff, pledgedSrcSize)) { DEBUGLOG(4, "ZSTD_equivalentParams()==1 -> continue mode (wLog1=%u, blockSize1=%u)", zc->appliedParams.cParams.windowLog, (U32)zc->blockSize); - assert(!(params.ldmParams.enableLdm && - params.ldmParams.hashEveryLog == ZSTD_LDM_HASHEVERYLOG_NOTSET)); - zc->entropy->hufCTable_repeatMode = HUF_repeat_none; - zc->entropy->offcode_repeatMode = FSE_repeat_none; - zc->entropy->matchlength_repeatMode = FSE_repeat_none; - zc->entropy->litlength_repeatMode = FSE_repeat_none; return ZSTD_continueCCtx(zc, params, pledgedSrcSize); } } DEBUGLOG(4, "ZSTD_equivalentParams()==0 -> reset CCtx"); if (params.ldmParams.enableLdm) { /* Adjust long distance matching parameters */ - ZSTD_ldm_adjustParameters(¶ms.ldmParams, params.cParams.windowLog); + params.ldmParams.windowLog = params.cParams.windowLog; + ZSTD_ldm_adjustParameters(¶ms.ldmParams, ¶ms.cParams); assert(params.ldmParams.hashLog >= params.ldmParams.bucketSizeLog); assert(params.ldmParams.hashEveryLog < 32); zc->ldmState.hashPower = @@ -854,34 +977,25 @@ static size_t ZSTD_resetCCtx_internal(ZSTD_CCtx* zc, U32 const divider = (params.cParams.searchLength==3) ? 3 : 4; size_t const maxNbSeq = blockSize / divider; size_t const tokenSpace = blockSize + 11*maxNbSeq; - size_t const chainSize = (params.cParams.strategy == ZSTD_fast) ? - 0 : ((size_t)1 << params.cParams.chainLog); - size_t const hSize = ((size_t)1) << params.cParams.hashLog; - U32 const hashLog3 = (params.cParams.searchLength>3) ? - 0 : MIN(ZSTD_HASHLOG3_MAX, params.cParams.windowLog); - size_t const h3Size = ((size_t)1) << hashLog3; - size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32); size_t const buffOutSize = (zbuff==ZSTDb_buffered) ? ZSTD_compressBound(blockSize)+1 : 0; size_t const buffInSize = (zbuff==ZSTDb_buffered) ? windowSize + blockSize : 0; + size_t const matchStateSize = ZSTD_sizeof_matchState(¶ms.cParams, /* forCCtx */ 1); + size_t const maxNbLdmSeq = ZSTD_ldm_getMaxNbSeq(params.ldmParams, blockSize); void* ptr; /* Check if workSpace is large enough, alloc a new one if needed */ - { size_t const entropySpace = sizeof(ZSTD_entropyCTables_t); - size_t const optPotentialSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits)) * sizeof(U32) - + (ZSTD_OPT_NUM+1) * (sizeof(ZSTD_match_t)+sizeof(ZSTD_optimal_t)); - size_t const optSpace = ( (params.cParams.strategy == ZSTD_btopt) - || (params.cParams.strategy == ZSTD_btultra)) ? - optPotentialSpace : 0; + { size_t const entropySpace = HUF_WORKSPACE_SIZE; + size_t const blockStateSpace = 2 * sizeof(ZSTD_compressedBlockState_t); size_t const bufferSpace = buffInSize + buffOutSize; - size_t const ldmSpace = params.ldmParams.enableLdm - ? ZSTD_ldm_getTableSize(params.ldmParams.hashLog, params.ldmParams.bucketSizeLog) - : 0; - size_t const neededSpace = entropySpace + optSpace + ldmSpace + - tableSpace + tokenSpace + bufferSpace; - DEBUGLOG(4, "Need %uKB workspace, including %uKB for tables, and %uKB for buffers", - (U32)(neededSpace>>10), (U32)(tableSpace>>10), (U32)(bufferSpace>>10)); - DEBUGLOG(4, "chainSize: %u - hSize: %u - h3Size: %u - windowSize: %u - blockSize: %u", - (U32)chainSize, (U32)hSize, (U32)h3Size, (U32)windowSize, (U32)blockSize); + size_t const ldmSpace = ZSTD_ldm_getTableSize(params.ldmParams); + size_t const ldmSeqSpace = maxNbLdmSeq * sizeof(rawSeq); + + size_t const neededSpace = entropySpace + blockStateSpace + ldmSpace + + ldmSeqSpace + matchStateSize + tokenSpace + + bufferSpace; + DEBUGLOG(4, "Need %uKB workspace, including %uKB for match state, and %uKB for buffers", + (U32)(neededSpace>>10), (U32)(matchStateSize>>10), (U32)(bufferSpace>>10)); + DEBUGLOG(4, "windowSize: %u - blockSize: %u", (U32)windowSize, (U32)blockSize); if (zc->workSpaceSize < neededSpace) { /* too small : resize */ DEBUGLOG(4, "Need to update workSpaceSize from %uK to %uK", @@ -897,16 +1011,20 @@ static size_t ZSTD_resetCCtx_internal(ZSTD_CCtx* zc, zc->workSpaceSize = neededSpace; ptr = zc->workSpace; - /* entropy space */ + /* Statically sized space. entropyWorkspace never moves (but prev/next block swap places) */ assert(((size_t)zc->workSpace & 3) == 0); /* ensure correct alignment */ - assert(zc->workSpaceSize >= sizeof(ZSTD_entropyCTables_t)); - zc->entropy = (ZSTD_entropyCTables_t*)zc->workSpace; + assert(zc->workSpaceSize >= 2 * sizeof(ZSTD_compressedBlockState_t)); + zc->blockState.prevCBlock = (ZSTD_compressedBlockState_t*)zc->workSpace; + zc->blockState.nextCBlock = zc->blockState.prevCBlock + 1; + ptr = zc->blockState.nextCBlock + 1; + zc->entropyWorkspace = (U32*)ptr; } } /* init params */ zc->appliedParams = params; zc->pledgedSrcSizePlusOne = pledgedSrcSize+1; zc->consumedSrcSize = 0; + zc->producedCSize = 0; if (pledgedSrcSize == ZSTD_CONTENTSIZE_UNKNOWN) zc->appliedParams.fParams.contentSizeFlag = 0; DEBUGLOG(4, "pledged content size : %u ; flag : %u", @@ -916,37 +1034,10 @@ static size_t ZSTD_resetCCtx_internal(ZSTD_CCtx* zc, XXH64_reset(&zc->xxhState, 0); zc->stage = ZSTDcs_init; zc->dictID = 0; - zc->loadedDictEnd = 0; - zc->entropy->hufCTable_repeatMode = HUF_repeat_none; - zc->entropy->offcode_repeatMode = FSE_repeat_none; - zc->entropy->matchlength_repeatMode = FSE_repeat_none; - zc->entropy->litlength_repeatMode = FSE_repeat_none; - zc->nextToUpdate = 1; - zc->nextSrc = NULL; - zc->base = NULL; - zc->dictBase = NULL; - zc->dictLimit = 0; - zc->lowLimit = 0; - { int i; for (i=0; i<ZSTD_REP_NUM; i++) zc->seqStore.rep[i] = repStartValue[i]; } - zc->hashLog3 = hashLog3; - zc->optState.litLengthSum = 0; - - ptr = zc->entropy + 1; - - /* opt parser space */ - if ((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btultra)) { - DEBUGLOG(4, "reserving optimal parser space"); - assert(((size_t)ptr & 3) == 0); /* ensure ptr is properly aligned */ - zc->optState.litFreq = (U32*)ptr; - zc->optState.litLengthFreq = zc->optState.litFreq + (1<<Litbits); - zc->optState.matchLengthFreq = zc->optState.litLengthFreq + (MaxLL+1); - zc->optState.offCodeFreq = zc->optState.matchLengthFreq + (MaxML+1); - ptr = zc->optState.offCodeFreq + (MaxOff+1); - zc->optState.matchTable = (ZSTD_match_t*)ptr; - ptr = zc->optState.matchTable + ZSTD_OPT_NUM+1; - zc->optState.priceTable = (ZSTD_optimal_t*)ptr; - ptr = zc->optState.priceTable + ZSTD_OPT_NUM+1; - } + + ZSTD_reset_compressedBlockState(zc->blockState.prevCBlock); + + ptr = zc->entropyWorkspace + HUF_WORKSPACE_SIZE_U32; /* ldm hash table */ /* initialize bucketOffsets table later for pointer alignment */ @@ -956,16 +1047,15 @@ static size_t ZSTD_resetCCtx_internal(ZSTD_CCtx* zc, assert(((size_t)ptr & 3) == 0); /* ensure ptr is properly aligned */ zc->ldmState.hashTable = (ldmEntry_t*)ptr; ptr = zc->ldmState.hashTable + ldmHSize; + zc->ldmSequences = (rawSeq*)ptr; + ptr = zc->ldmSequences + maxNbLdmSeq; + zc->maxNbLdmSequences = maxNbLdmSeq; + + memset(&zc->ldmState.window, 0, sizeof(zc->ldmState.window)); } + assert(((size_t)ptr & 3) == 0); /* ensure ptr is properly aligned */ - /* table Space */ - DEBUGLOG(4, "reset table : %u", crp!=ZSTDcrp_noMemset); - if (crp!=ZSTDcrp_noMemset) memset(ptr, 0, tableSpace); /* reset tables only */ - assert(((size_t)ptr & 3) == 0); /* ensure ptr is properly aligned */ - zc->hashTable = (U32*)(ptr); - zc->chainTable = zc->hashTable + hSize; - zc->hashTable3 = zc->chainTable + chainSize; - ptr = zc->hashTable3 + h3Size; + ptr = ZSTD_reset_matchState(&zc->blockState.matchState, ptr, ¶ms.cParams, crp, /* forCCtx */ 1); /* sequences storage */ zc->seqStore.sequencesStart = (seqDef*)ptr; @@ -984,7 +1074,9 @@ static size_t ZSTD_resetCCtx_internal(ZSTD_CCtx* zc, memset(ptr, 0, ldmBucketSize); zc->ldmState.bucketOffsets = (BYTE*)ptr; ptr = zc->ldmState.bucketOffsets + ldmBucketSize; + ZSTD_window_clear(&zc->ldmState.window); } + ZSTD_referenceExternalSequences(zc, NULL, 0); /* buffers */ zc->inBuffSize = buffInSize; @@ -1002,9 +1094,61 @@ static size_t ZSTD_resetCCtx_internal(ZSTD_CCtx* zc, * do not use with extDict variant ! */ void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx) { int i; - for (i=0; i<ZSTD_REP_NUM; i++) cctx->seqStore.rep[i] = 0; + for (i=0; i<ZSTD_REP_NUM; i++) cctx->blockState.prevCBlock->rep[i] = 0; + assert(!ZSTD_window_hasExtDict(cctx->blockState.matchState.window)); } +static size_t ZSTD_resetCCtx_usingCDict(ZSTD_CCtx* cctx, + const ZSTD_CDict* cdict, + unsigned windowLog, + ZSTD_frameParameters fParams, + U64 pledgedSrcSize, + ZSTD_buffered_policy_e zbuff) +{ + { ZSTD_CCtx_params params = cctx->requestedParams; + /* Copy only compression parameters related to tables. */ + params.cParams = cdict->cParams; + if (windowLog) params.cParams.windowLog = windowLog; + params.fParams = fParams; + ZSTD_resetCCtx_internal(cctx, params, pledgedSrcSize, + ZSTDcrp_noMemset, zbuff); + assert(cctx->appliedParams.cParams.strategy == cdict->cParams.strategy); + assert(cctx->appliedParams.cParams.hashLog == cdict->cParams.hashLog); + assert(cctx->appliedParams.cParams.chainLog == cdict->cParams.chainLog); + } + + /* copy tables */ + { size_t const chainSize = (cdict->cParams.strategy == ZSTD_fast) ? 0 : ((size_t)1 << cdict->cParams.chainLog); + size_t const hSize = (size_t)1 << cdict->cParams.hashLog; + size_t const tableSpace = (chainSize + hSize) * sizeof(U32); + assert((U32*)cctx->blockState.matchState.chainTable == (U32*)cctx->blockState.matchState.hashTable + hSize); /* chainTable must follow hashTable */ + assert((U32*)cctx->blockState.matchState.hashTable3 == (U32*)cctx->blockState.matchState.chainTable + chainSize); + assert((U32*)cdict->matchState.chainTable == (U32*)cdict->matchState.hashTable + hSize); /* chainTable must follow hashTable */ + assert((U32*)cdict->matchState.hashTable3 == (U32*)cdict->matchState.chainTable + chainSize); + memcpy(cctx->blockState.matchState.hashTable, cdict->matchState.hashTable, tableSpace); /* presumes all tables follow each other */ + } + /* Zero the hashTable3, since the cdict never fills it */ + { size_t const h3Size = (size_t)1 << cctx->blockState.matchState.hashLog3; + assert(cdict->matchState.hashLog3 == 0); + memset(cctx->blockState.matchState.hashTable3, 0, h3Size * sizeof(U32)); + } + + /* copy dictionary offsets */ + { + ZSTD_matchState_t const* srcMatchState = &cdict->matchState; + ZSTD_matchState_t* dstMatchState = &cctx->blockState.matchState; + dstMatchState->window = srcMatchState->window; + dstMatchState->nextToUpdate = srcMatchState->nextToUpdate; + dstMatchState->nextToUpdate3= srcMatchState->nextToUpdate3; + dstMatchState->loadedDictEnd= srcMatchState->loadedDictEnd; + } + cctx->dictID = cdict->dictID; + + /* copy block state */ + memcpy(cctx->blockState.prevCBlock, &cdict->cBlockState, sizeof(cdict->cBlockState)); + + return 0; +} /*! ZSTD_copyCCtx_internal() : * Duplicate an existing context `srcCCtx` into another one `dstCCtx`. @@ -1015,7 +1159,6 @@ void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx) { * @return : 0, or an error code */ static size_t ZSTD_copyCCtx_internal(ZSTD_CCtx* dstCCtx, const ZSTD_CCtx* srcCCtx, - unsigned windowLog, ZSTD_frameParameters fParams, U64 pledgedSrcSize, ZSTD_buffered_policy_e zbuff) @@ -1027,41 +1170,39 @@ static size_t ZSTD_copyCCtx_internal(ZSTD_CCtx* dstCCtx, { ZSTD_CCtx_params params = dstCCtx->requestedParams; /* Copy only compression parameters related to tables. */ params.cParams = srcCCtx->appliedParams.cParams; - if (windowLog) params.cParams.windowLog = windowLog; params.fParams = fParams; ZSTD_resetCCtx_internal(dstCCtx, params, pledgedSrcSize, ZSTDcrp_noMemset, zbuff); + assert(dstCCtx->appliedParams.cParams.windowLog == srcCCtx->appliedParams.cParams.windowLog); + assert(dstCCtx->appliedParams.cParams.strategy == srcCCtx->appliedParams.cParams.strategy); + assert(dstCCtx->appliedParams.cParams.hashLog == srcCCtx->appliedParams.cParams.hashLog); + assert(dstCCtx->appliedParams.cParams.chainLog == srcCCtx->appliedParams.cParams.chainLog); + assert(dstCCtx->blockState.matchState.hashLog3 == srcCCtx->blockState.matchState.hashLog3); } /* copy tables */ { size_t const chainSize = (srcCCtx->appliedParams.cParams.strategy == ZSTD_fast) ? 0 : ((size_t)1 << srcCCtx->appliedParams.cParams.chainLog); size_t const hSize = (size_t)1 << srcCCtx->appliedParams.cParams.hashLog; - size_t const h3Size = (size_t)1 << srcCCtx->hashLog3; + size_t const h3Size = (size_t)1 << srcCCtx->blockState.matchState.hashLog3; size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32); - assert((U32*)dstCCtx->chainTable == (U32*)dstCCtx->hashTable + hSize); /* chainTable must follow hashTable */ - assert((U32*)dstCCtx->hashTable3 == (U32*)dstCCtx->chainTable + chainSize); - memcpy(dstCCtx->hashTable, srcCCtx->hashTable, tableSpace); /* presumes all tables follow each other */ + assert((U32*)dstCCtx->blockState.matchState.chainTable == (U32*)dstCCtx->blockState.matchState.hashTable + hSize); /* chainTable must follow hashTable */ + assert((U32*)dstCCtx->blockState.matchState.hashTable3 == (U32*)dstCCtx->blockState.matchState.chainTable + chainSize); + memcpy(dstCCtx->blockState.matchState.hashTable, srcCCtx->blockState.matchState.hashTable, tableSpace); /* presumes all tables follow each other */ } /* copy dictionary offsets */ - dstCCtx->nextToUpdate = srcCCtx->nextToUpdate; - dstCCtx->nextToUpdate3= srcCCtx->nextToUpdate3; - dstCCtx->nextSrc = srcCCtx->nextSrc; - dstCCtx->base = srcCCtx->base; - dstCCtx->dictBase = srcCCtx->dictBase; - dstCCtx->dictLimit = srcCCtx->dictLimit; - dstCCtx->lowLimit = srcCCtx->lowLimit; - dstCCtx->loadedDictEnd= srcCCtx->loadedDictEnd; - dstCCtx->dictID = srcCCtx->dictID; - - /* copy entropy tables */ - memcpy(dstCCtx->entropy, srcCCtx->entropy, sizeof(ZSTD_entropyCTables_t)); - /* copy repcodes */ { - int i; - for (i = 0; i < ZSTD_REP_NUM; ++i) - dstCCtx->seqStore.rep[i] = srcCCtx->seqStore.rep[i]; + ZSTD_matchState_t const* srcMatchState = &srcCCtx->blockState.matchState; + ZSTD_matchState_t* dstMatchState = &dstCCtx->blockState.matchState; + dstMatchState->window = srcMatchState->window; + dstMatchState->nextToUpdate = srcMatchState->nextToUpdate; + dstMatchState->nextToUpdate3= srcMatchState->nextToUpdate3; + dstMatchState->loadedDictEnd= srcMatchState->loadedDictEnd; } + dstCCtx->dictID = srcCCtx->dictID; + + /* copy block state */ + memcpy(dstCCtx->blockState.prevCBlock, srcCCtx->blockState.prevCBlock, sizeof(*srcCCtx->blockState.prevCBlock)); return 0; } @@ -1080,51 +1221,69 @@ size_t ZSTD_copyCCtx(ZSTD_CCtx* dstCCtx, const ZSTD_CCtx* srcCCtx, unsigned long fParams.contentSizeFlag = (pledgedSrcSize != ZSTD_CONTENTSIZE_UNKNOWN); return ZSTD_copyCCtx_internal(dstCCtx, srcCCtx, - 0 /*windowLog from srcCCtx*/, fParams, pledgedSrcSize, + fParams, pledgedSrcSize, zbuff); } +#define ZSTD_ROWSIZE 16 /*! ZSTD_reduceTable() : - * reduce table indexes by `reducerValue` */ -static void ZSTD_reduceTable (U32* const table, U32 const size, U32 const reducerValue) + * reduce table indexes by `reducerValue`, or squash to zero. + * PreserveMark preserves "unsorted mark" for btlazy2 strategy. + * It must be set to a clear 0/1 value, to remove branch during inlining. + * Presume table size is a multiple of ZSTD_ROWSIZE + * to help auto-vectorization */ +FORCE_INLINE_TEMPLATE void +ZSTD_reduceTable_internal (U32* const table, U32 const size, U32 const reducerValue, int const preserveMark) +{ + int const nbRows = (int)size / ZSTD_ROWSIZE; + int cellNb = 0; + int rowNb; + assert((size & (ZSTD_ROWSIZE-1)) == 0); /* multiple of ZSTD_ROWSIZE */ + assert(size < (1U<<31)); /* can be casted to int */ + for (rowNb=0 ; rowNb < nbRows ; rowNb++) { + int column; + for (column=0; column<ZSTD_ROWSIZE; column++) { + if (preserveMark) { + U32 const adder = (table[cellNb] == ZSTD_DUBT_UNSORTED_MARK) ? reducerValue : 0; + table[cellNb] += adder; + } + if (table[cellNb] < reducerValue) table[cellNb] = 0; + else table[cellNb] -= reducerValue; + cellNb++; + } } +} + +static void ZSTD_reduceTable(U32* const table, U32 const size, U32 const reducerValue) { - U32 u; - for (u=0 ; u < size ; u++) { - if (table[u] < reducerValue) table[u] = 0; - else table[u] -= reducerValue; - } + ZSTD_reduceTable_internal(table, size, reducerValue, 0); } -/*! ZSTD_ldm_reduceTable() : - * reduce table indexes by `reducerValue` */ -static void ZSTD_ldm_reduceTable(ldmEntry_t* const table, U32 const size, - U32 const reducerValue) +static void ZSTD_reduceTable_btlazy2(U32* const table, U32 const size, U32 const reducerValue) { - U32 u; - for (u = 0; u < size; u++) { - if (table[u].offset < reducerValue) table[u].offset = 0; - else table[u].offset -= reducerValue; - } + ZSTD_reduceTable_internal(table, size, reducerValue, 1); } /*! ZSTD_reduceIndex() : * rescale all indexes to avoid future overflow (indexes are U32) */ static void ZSTD_reduceIndex (ZSTD_CCtx* zc, const U32 reducerValue) { - { U32 const hSize = (U32)1 << zc->appliedParams.cParams.hashLog; - ZSTD_reduceTable(zc->hashTable, hSize, reducerValue); } - - { U32 const chainSize = (zc->appliedParams.cParams.strategy == ZSTD_fast) ? 0 : ((U32)1 << zc->appliedParams.cParams.chainLog); - ZSTD_reduceTable(zc->chainTable, chainSize, reducerValue); } + ZSTD_matchState_t* const ms = &zc->blockState.matchState; + { U32 const hSize = (U32)1 << zc->appliedParams.cParams.hashLog; + ZSTD_reduceTable(ms->hashTable, hSize, reducerValue); + } - { U32 const h3Size = (zc->hashLog3) ? (U32)1 << zc->hashLog3 : 0; - ZSTD_reduceTable(zc->hashTable3, h3Size, reducerValue); } + if (zc->appliedParams.cParams.strategy != ZSTD_fast) { + U32 const chainSize = (U32)1 << zc->appliedParams.cParams.chainLog; + if (zc->appliedParams.cParams.strategy == ZSTD_btlazy2) + ZSTD_reduceTable_btlazy2(ms->chainTable, chainSize, reducerValue); + else + ZSTD_reduceTable(ms->chainTable, chainSize, reducerValue); + } - { if (zc->appliedParams.ldmParams.enableLdm) { - U32 const ldmHSize = (U32)1 << zc->appliedParams.ldmParams.hashLog; - ZSTD_ldm_reduceTable(zc->ldmState.hashTable, ldmHSize, reducerValue); - } + if (ms->hashLog3) { + U32 const h3Size = (U32)1 << ms->hashLog3; + ZSTD_reduceTable(ms->hashTable3, h3Size, reducerValue); } } @@ -1199,10 +1358,12 @@ static size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t dstCapacity, cons static size_t ZSTD_minGain(size_t srcSize) { return (srcSize >> 6) + 2; } -static size_t ZSTD_compressLiterals (ZSTD_entropyCTables_t * entropy, - ZSTD_strategy strategy, +static size_t ZSTD_compressLiterals (ZSTD_entropyCTables_t const* prevEntropy, + ZSTD_entropyCTables_t* nextEntropy, + ZSTD_strategy strategy, int disableLiteralCompression, void* dst, size_t dstCapacity, - const void* src, size_t srcSize) + const void* src, size_t srcSize, + U32* workspace, const int bmi2) { size_t const minGain = ZSTD_minGain(srcSize); size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB); @@ -1211,34 +1372,51 @@ static size_t ZSTD_compressLiterals (ZSTD_entropyCTables_t * entropy, symbolEncodingType_e hType = set_compressed; size_t cLitSize; + DEBUGLOG(5,"ZSTD_compressLiterals (disableLiteralCompression=%i)", + disableLiteralCompression); + + /* Prepare nextEntropy assuming reusing the existing table */ + nextEntropy->hufCTable_repeatMode = prevEntropy->hufCTable_repeatMode; + memcpy(nextEntropy->hufCTable, prevEntropy->hufCTable, + sizeof(prevEntropy->hufCTable)); + + if (disableLiteralCompression) + return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize); /* small ? don't even attempt compression (speed opt) */ -# define LITERAL_NOENTROPY 63 - { size_t const minLitSize = entropy->hufCTable_repeatMode == HUF_repeat_valid ? 6 : LITERAL_NOENTROPY; +# define COMPRESS_LITERALS_SIZE_MIN 63 + { size_t const minLitSize = (prevEntropy->hufCTable_repeatMode == HUF_repeat_valid) ? 6 : COMPRESS_LITERALS_SIZE_MIN; if (srcSize <= minLitSize) return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize); } if (dstCapacity < lhSize+1) return ERROR(dstSize_tooSmall); /* not enough space for compression */ - { HUF_repeat repeat = entropy->hufCTable_repeatMode; + { HUF_repeat repeat = prevEntropy->hufCTable_repeatMode; int const preferRepeat = strategy < ZSTD_lazy ? srcSize <= 1024 : 0; if (repeat == HUF_repeat_valid && lhSize == 3) singleStream = 1; cLitSize = singleStream ? HUF_compress1X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11, - entropy->workspace, sizeof(entropy->workspace), (HUF_CElt*)entropy->hufCTable, &repeat, preferRepeat) + workspace, HUF_WORKSPACE_SIZE, (HUF_CElt*)nextEntropy->hufCTable, &repeat, preferRepeat, bmi2) : HUF_compress4X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11, - entropy->workspace, sizeof(entropy->workspace), (HUF_CElt*)entropy->hufCTable, &repeat, preferRepeat); - if (repeat != HUF_repeat_none) { hType = set_repeat; } /* reused the existing table */ - else { entropy->hufCTable_repeatMode = HUF_repeat_check; } /* now have a table to reuse */ + workspace, HUF_WORKSPACE_SIZE, (HUF_CElt*)nextEntropy->hufCTable, &repeat, preferRepeat, bmi2); + if (repeat != HUF_repeat_none) { + /* reused the existing table */ + hType = set_repeat; + } } if ((cLitSize==0) | (cLitSize >= srcSize - minGain) | ERR_isError(cLitSize)) { - entropy->hufCTable_repeatMode = HUF_repeat_none; + memcpy(nextEntropy->hufCTable, prevEntropy->hufCTable, sizeof(prevEntropy->hufCTable)); return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize); } if (cLitSize==1) { - entropy->hufCTable_repeatMode = HUF_repeat_none; + memcpy(nextEntropy->hufCTable, prevEntropy->hufCTable, sizeof(prevEntropy->hufCTable)); return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize); } + if (hType == set_compressed) { + /* using a newly constructed table */ + nextEntropy->hufCTable_repeatMode = HUF_repeat_check; + } + /* Build header */ switch(lhSize) { @@ -1332,10 +1510,11 @@ symbolEncodingType_e ZSTD_selectEncodingType( MEM_STATIC size_t ZSTD_buildCTable(void* dst, size_t dstCapacity, - FSE_CTable* CTable, U32 FSELog, symbolEncodingType_e type, + FSE_CTable* nextCTable, U32 FSELog, symbolEncodingType_e type, U32* count, U32 max, BYTE const* codeTable, size_t nbSeq, S16 const* defaultNorm, U32 defaultNormLog, U32 defaultMax, + FSE_CTable const* prevCTable, size_t prevCTableSize, void* workspace, size_t workspaceSize) { BYTE* op = (BYTE*)dst; @@ -1344,12 +1523,13 @@ size_t ZSTD_buildCTable(void* dst, size_t dstCapacity, switch (type) { case set_rle: *op = codeTable[0]; - CHECK_F(FSE_buildCTable_rle(CTable, (BYTE)max)); + CHECK_F(FSE_buildCTable_rle(nextCTable, (BYTE)max)); return 1; case set_repeat: + memcpy(nextCTable, prevCTable, prevCTableSize); return 0; case set_basic: - CHECK_F(FSE_buildCTable_wksp(CTable, defaultNorm, defaultMax, defaultNormLog, workspace, workspaceSize)); /* note : could be pre-calculated */ + CHECK_F(FSE_buildCTable_wksp(nextCTable, defaultNorm, defaultMax, defaultNormLog, workspace, workspaceSize)); /* note : could be pre-calculated */ return 0; case set_compressed: { S16 norm[MaxSeq + 1]; @@ -1363,7 +1543,7 @@ size_t ZSTD_buildCTable(void* dst, size_t dstCapacity, CHECK_F(FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max)); { size_t const NCountSize = FSE_writeNCount(op, oend - op, norm, max, tableLog); /* overflow protected */ if (FSE_isError(NCountSize)) return NCountSize; - CHECK_F(FSE_buildCTable_wksp(CTable, norm, max, tableLog, workspace, workspaceSize)); + CHECK_F(FSE_buildCTable_wksp(nextCTable, norm, max, tableLog, workspace, workspaceSize)); return NCountSize; } } @@ -1371,8 +1551,8 @@ size_t ZSTD_buildCTable(void* dst, size_t dstCapacity, } } -MEM_STATIC -size_t ZSTD_encodeSequences( +FORCE_INLINE_TEMPLATE size_t +ZSTD_encodeSequences_body( void* dst, size_t dstCapacity, FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable, FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable, @@ -1419,7 +1599,8 @@ size_t ZSTD_encodeSequences( DEBUGLOG(6, "encoding: litlen:%2u - matchlen:%2u - offCode:%7u", sequences[n].litLength, sequences[n].matchLength + MINMATCH, - sequences[n].offset); /* 32b*/ /* 64b*/ + sequences[n].offset); + /* 32b*/ /* 64b*/ /* (7)*/ /* (7)*/ FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode); /* 15 */ /* 15 */ FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode); /* 24 */ /* 24 */ @@ -1445,8 +1626,11 @@ size_t ZSTD_encodeSequences( BIT_flushBits(&blockStream); /* (7)*/ } } + DEBUGLOG(6, "ZSTD_encodeSequences: flushing ML state with %u bits", stateMatchLength.stateLog); FSE_flushCState(&blockStream, &stateMatchLength); + DEBUGLOG(6, "ZSTD_encodeSequences: flushing Off state with %u bits", stateOffsetBits.stateLog); FSE_flushCState(&blockStream, &stateOffsetBits); + DEBUGLOG(6, "ZSTD_encodeSequences: flushing LL state with %u bits", stateLitLength.stateLog); FSE_flushCState(&blockStream, &stateLitLength); { size_t const streamSize = BIT_closeCStream(&blockStream); @@ -1455,16 +1639,77 @@ size_t ZSTD_encodeSequences( } } +static size_t +ZSTD_encodeSequences_default( + void* dst, size_t dstCapacity, + FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable, + FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable, + FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable, + seqDef const* sequences, size_t nbSeq, int longOffsets) +{ + return ZSTD_encodeSequences_body(dst, dstCapacity, + CTable_MatchLength, mlCodeTable, + CTable_OffsetBits, ofCodeTable, + CTable_LitLength, llCodeTable, + sequences, nbSeq, longOffsets); +} + + +#if DYNAMIC_BMI2 + +static TARGET_ATTRIBUTE("bmi2") size_t +ZSTD_encodeSequences_bmi2( + void* dst, size_t dstCapacity, + FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable, + FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable, + FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable, + seqDef const* sequences, size_t nbSeq, int longOffsets) +{ + return ZSTD_encodeSequences_body(dst, dstCapacity, + CTable_MatchLength, mlCodeTable, + CTable_OffsetBits, ofCodeTable, + CTable_LitLength, llCodeTable, + sequences, nbSeq, longOffsets); +} + +#endif + +size_t ZSTD_encodeSequences( + void* dst, size_t dstCapacity, + FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable, + FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable, + FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable, + seqDef const* sequences, size_t nbSeq, int longOffsets, int bmi2) +{ +#if DYNAMIC_BMI2 + if (bmi2) { + return ZSTD_encodeSequences_bmi2(dst, dstCapacity, + CTable_MatchLength, mlCodeTable, + CTable_OffsetBits, ofCodeTable, + CTable_LitLength, llCodeTable, + sequences, nbSeq, longOffsets); + } +#endif + (void)bmi2; + return ZSTD_encodeSequences_default(dst, dstCapacity, + CTable_MatchLength, mlCodeTable, + CTable_OffsetBits, ofCodeTable, + CTable_LitLength, llCodeTable, + sequences, nbSeq, longOffsets); +} + MEM_STATIC size_t ZSTD_compressSequences_internal(seqStore_t* seqStorePtr, - ZSTD_entropyCTables_t* entropy, - ZSTD_compressionParameters const* cParams, - void* dst, size_t dstCapacity) + ZSTD_entropyCTables_t const* prevEntropy, + ZSTD_entropyCTables_t* nextEntropy, + ZSTD_CCtx_params const* cctxParams, + void* dst, size_t dstCapacity, U32* workspace, + const int bmi2) { - const int longOffsets = cParams->windowLog > STREAM_ACCUMULATOR_MIN; + const int longOffsets = cctxParams->cParams.windowLog > STREAM_ACCUMULATOR_MIN; U32 count[MaxSeq+1]; - FSE_CTable* CTable_LitLength = entropy->litlengthCTable; - FSE_CTable* CTable_OffsetBits = entropy->offcodeCTable; - FSE_CTable* CTable_MatchLength = entropy->matchlengthCTable; + FSE_CTable* CTable_LitLength = nextEntropy->litlengthCTable; + FSE_CTable* CTable_OffsetBits = nextEntropy->offcodeCTable; + FSE_CTable* CTable_MatchLength = nextEntropy->matchlengthCTable; U32 LLtype, Offtype, MLtype; /* compressed, raw or rle */ const seqDef* const sequences = seqStorePtr->sequencesStart; const BYTE* const ofCodeTable = seqStorePtr->ofCode; @@ -1476,13 +1721,17 @@ MEM_STATIC size_t ZSTD_compressSequences_internal(seqStore_t* seqStorePtr, size_t const nbSeq = seqStorePtr->sequences - seqStorePtr->sequencesStart; BYTE* seqHead; - ZSTD_STATIC_ASSERT(sizeof(entropy->workspace) >= (1<<MAX(MLFSELog,LLFSELog))); + ZSTD_STATIC_ASSERT(HUF_WORKSPACE_SIZE >= (1<<MAX(MLFSELog,LLFSELog))); /* Compress literals */ { const BYTE* const literals = seqStorePtr->litStart; size_t const litSize = seqStorePtr->lit - literals; size_t const cSize = ZSTD_compressLiterals( - entropy, cParams->strategy, op, dstCapacity, literals, litSize); + prevEntropy, nextEntropy, + cctxParams->cParams.strategy, cctxParams->disableLiteralCompression, + op, dstCapacity, + literals, litSize, + workspace, bmi2); if (ZSTD_isError(cSize)) return cSize; assert(cSize <= dstCapacity); @@ -1497,7 +1746,15 @@ MEM_STATIC size_t ZSTD_compressSequences_internal(seqStore_t* seqStorePtr, op[0] = (BYTE)((nbSeq>>8) + 0x80), op[1] = (BYTE)nbSeq, op+=2; else op[0]=0xFF, MEM_writeLE16(op+1, (U16)(nbSeq - LONGNBSEQ)), op+=3; - if (nbSeq==0) return op - ostart; + if (nbSeq==0) { + memcpy(nextEntropy->litlengthCTable, prevEntropy->litlengthCTable, sizeof(prevEntropy->litlengthCTable)); + nextEntropy->litlength_repeatMode = prevEntropy->litlength_repeatMode; + memcpy(nextEntropy->offcodeCTable, prevEntropy->offcodeCTable, sizeof(prevEntropy->offcodeCTable)); + nextEntropy->offcode_repeatMode = prevEntropy->offcode_repeatMode; + memcpy(nextEntropy->matchlengthCTable, prevEntropy->matchlengthCTable, sizeof(prevEntropy->matchlengthCTable)); + nextEntropy->matchlength_repeatMode = prevEntropy->matchlength_repeatMode; + return op - ostart; + } /* seqHead : flags for FSE encoding type */ seqHead = op++; @@ -1506,36 +1763,42 @@ MEM_STATIC size_t ZSTD_compressSequences_internal(seqStore_t* seqStorePtr, ZSTD_seqToCodes(seqStorePtr); /* build CTable for Literal Lengths */ { U32 max = MaxLL; - size_t const mostFrequent = FSE_countFast_wksp(count, &max, llCodeTable, nbSeq, entropy->workspace); + size_t const mostFrequent = FSE_countFast_wksp(count, &max, llCodeTable, nbSeq, workspace); DEBUGLOG(5, "Building LL table"); - LLtype = ZSTD_selectEncodingType(&entropy->litlength_repeatMode, mostFrequent, nbSeq, LL_defaultNormLog, ZSTD_defaultAllowed); + nextEntropy->litlength_repeatMode = prevEntropy->litlength_repeatMode; + LLtype = ZSTD_selectEncodingType(&nextEntropy->litlength_repeatMode, mostFrequent, nbSeq, LL_defaultNormLog, ZSTD_defaultAllowed); { size_t const countSize = ZSTD_buildCTable(op, oend - op, CTable_LitLength, LLFSELog, (symbolEncodingType_e)LLtype, count, max, llCodeTable, nbSeq, LL_defaultNorm, LL_defaultNormLog, MaxLL, - entropy->workspace, sizeof(entropy->workspace)); + prevEntropy->litlengthCTable, sizeof(prevEntropy->litlengthCTable), + workspace, HUF_WORKSPACE_SIZE); if (ZSTD_isError(countSize)) return countSize; op += countSize; } } /* build CTable for Offsets */ { U32 max = MaxOff; - size_t const mostFrequent = FSE_countFast_wksp(count, &max, ofCodeTable, nbSeq, entropy->workspace); + size_t const mostFrequent = FSE_countFast_wksp(count, &max, ofCodeTable, nbSeq, workspace); /* We can only use the basic table if max <= DefaultMaxOff, otherwise the offsets are too large */ ZSTD_defaultPolicy_e const defaultPolicy = (max <= DefaultMaxOff) ? ZSTD_defaultAllowed : ZSTD_defaultDisallowed; DEBUGLOG(5, "Building OF table"); - Offtype = ZSTD_selectEncodingType(&entropy->offcode_repeatMode, mostFrequent, nbSeq, OF_defaultNormLog, defaultPolicy); + nextEntropy->offcode_repeatMode = prevEntropy->offcode_repeatMode; + Offtype = ZSTD_selectEncodingType(&nextEntropy->offcode_repeatMode, mostFrequent, nbSeq, OF_defaultNormLog, defaultPolicy); { size_t const countSize = ZSTD_buildCTable(op, oend - op, CTable_OffsetBits, OffFSELog, (symbolEncodingType_e)Offtype, count, max, ofCodeTable, nbSeq, OF_defaultNorm, OF_defaultNormLog, DefaultMaxOff, - entropy->workspace, sizeof(entropy->workspace)); + prevEntropy->offcodeCTable, sizeof(prevEntropy->offcodeCTable), + workspace, HUF_WORKSPACE_SIZE); if (ZSTD_isError(countSize)) return countSize; op += countSize; } } /* build CTable for MatchLengths */ { U32 max = MaxML; - size_t const mostFrequent = FSE_countFast_wksp(count, &max, mlCodeTable, nbSeq, entropy->workspace); + size_t const mostFrequent = FSE_countFast_wksp(count, &max, mlCodeTable, nbSeq, workspace); DEBUGLOG(5, "Building ML table"); - MLtype = ZSTD_selectEncodingType(&entropy->matchlength_repeatMode, mostFrequent, nbSeq, ML_defaultNormLog, ZSTD_defaultAllowed); + nextEntropy->matchlength_repeatMode = prevEntropy->matchlength_repeatMode; + MLtype = ZSTD_selectEncodingType(&nextEntropy->matchlength_repeatMode, mostFrequent, nbSeq, ML_defaultNormLog, ZSTD_defaultAllowed); { size_t const countSize = ZSTD_buildCTable(op, oend - op, CTable_MatchLength, MLFSELog, (symbolEncodingType_e)MLtype, count, max, mlCodeTable, nbSeq, ML_defaultNorm, ML_defaultNormLog, MaxML, - entropy->workspace, sizeof(entropy->workspace)); + prevEntropy->matchlengthCTable, sizeof(prevEntropy->matchlengthCTable), + workspace, HUF_WORKSPACE_SIZE); if (ZSTD_isError(countSize)) return countSize; op += countSize; } } @@ -1548,7 +1811,7 @@ MEM_STATIC size_t ZSTD_compressSequences_internal(seqStore_t* seqStorePtr, CTable_OffsetBits, ofCodeTable, CTable_LitLength, llCodeTable, sequences, nbSeq, - longOffsets); + longOffsets, bmi2); if (ZSTD_isError(bitstreamSize)) return bitstreamSize; op += bitstreamSize; } @@ -1557,48 +1820,40 @@ MEM_STATIC size_t ZSTD_compressSequences_internal(seqStore_t* seqStorePtr, } MEM_STATIC size_t ZSTD_compressSequences(seqStore_t* seqStorePtr, - ZSTD_entropyCTables_t* entropy, - ZSTD_compressionParameters const* cParams, + ZSTD_entropyCTables_t const* prevEntropy, + ZSTD_entropyCTables_t* nextEntropy, + ZSTD_CCtx_params const* cctxParams, void* dst, size_t dstCapacity, - size_t srcSize) + size_t srcSize, U32* workspace, int bmi2) { - size_t const cSize = ZSTD_compressSequences_internal(seqStorePtr, entropy, cParams, - dst, dstCapacity); - /* If the srcSize <= dstCapacity, then there is enough space to write a - * raw uncompressed block. Since we ran out of space, the block must not - * be compressible, so fall back to a raw uncompressed block. + size_t const cSize = ZSTD_compressSequences_internal( + seqStorePtr, prevEntropy, nextEntropy, cctxParams, dst, dstCapacity, + workspace, bmi2); + /* When srcSize <= dstCapacity, there is enough space to write a raw uncompressed block. + * Since we ran out of space, block must be not compressible, so fall back to raw uncompressed block. */ - int const uncompressibleError = (cSize == ERROR(dstSize_tooSmall)) && (srcSize <= dstCapacity); - if (ZSTD_isError(cSize) && !uncompressibleError) - return cSize; + if ((cSize == ERROR(dstSize_tooSmall)) & (srcSize <= dstCapacity)) + return 0; /* block not compressed */ + if (ZSTD_isError(cSize)) return cSize; + + /* Check compressibility */ + { size_t const maxCSize = srcSize - ZSTD_minGain(srcSize); /* note : fixed formula, maybe should depend on compression level, or strategy */ + if (cSize >= maxCSize) return 0; /* block not compressed */ + } + /* We check that dictionaries have offset codes available for the first * block. After the first block, the offcode table might not have large * enough codes to represent the offsets in the data. */ - if (entropy->offcode_repeatMode == FSE_repeat_valid) - entropy->offcode_repeatMode = FSE_repeat_check; - - /* Check compressibility */ - { size_t const minGain = ZSTD_minGain(srcSize); /* note : fixed formula, maybe should depend on compression level, or strategy */ - size_t const maxCSize = srcSize - minGain; - if (cSize >= maxCSize || uncompressibleError) { - entropy->hufCTable_repeatMode = HUF_repeat_none; - entropy->offcode_repeatMode = FSE_repeat_none; - entropy->matchlength_repeatMode = FSE_repeat_none; - entropy->litlength_repeatMode = FSE_repeat_none; - return 0; /* block not compressed */ - } } - assert(!ZSTD_isError(cSize)); + if (nextEntropy->offcode_repeatMode == FSE_repeat_valid) + nextEntropy->offcode_repeatMode = FSE_repeat_check; - /* block is compressed => confirm repcodes in history */ - { int i; for (i=0; i<ZSTD_REP_NUM; i++) seqStorePtr->rep[i] = seqStorePtr->repToConfirm[i]; } return cSize; } /* ZSTD_selectBlockCompressor() : * Not static, but internal use only (used by long distance matcher) * assumption : strat is a valid strategy */ -typedef size_t (*ZSTD_blockCompressor) (ZSTD_CCtx* ctx, const void* src, size_t srcSize); ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, int extDict) { static const ZSTD_blockCompressor blockCompressor[2][(unsigned)ZSTD_btultra+1] = { @@ -1632,32 +1887,83 @@ static void ZSTD_resetSeqStore(seqStore_t* ssPtr) ssPtr->longLengthID = 0; } -static size_t ZSTD_compressBlock_internal(ZSTD_CCtx* zc, void* dst, size_t dstCapacity, const void* src, size_t srcSize) +static size_t ZSTD_compressBlock_internal(ZSTD_CCtx* zc, + void* dst, size_t dstCapacity, + const void* src, size_t srcSize) { - DEBUGLOG(5, "ZSTD_compressBlock_internal : dstCapacity = %u", (U32)dstCapacity); - if (srcSize < MIN_CBLOCK_SIZE+ZSTD_blockHeaderSize+1) + ZSTD_matchState_t* const ms = &zc->blockState.matchState; + DEBUGLOG(5, "ZSTD_compressBlock_internal (dstCapacity=%u, dictLimit=%u, nextToUpdate=%u)", + (U32)dstCapacity, ms->window.dictLimit, ms->nextToUpdate); + if (srcSize < MIN_CBLOCK_SIZE+ZSTD_blockHeaderSize+1) { + ZSTD_ldm_skipSequences(&zc->externSeqStore, srcSize, zc->appliedParams.cParams.searchLength); return 0; /* don't even attempt compression below a certain srcSize */ + } ZSTD_resetSeqStore(&(zc->seqStore)); /* limited update after a very long match */ - { const BYTE* const base = zc->base; + { const BYTE* const base = ms->window.base; const BYTE* const istart = (const BYTE*)src; const U32 current = (U32)(istart-base); - if (current > zc->nextToUpdate + 384) - zc->nextToUpdate = current - MIN(192, (U32)(current - zc->nextToUpdate - 384)); + if (current > ms->nextToUpdate + 384) + ms->nextToUpdate = current - MIN(192, (U32)(current - ms->nextToUpdate - 384)); } - /* find and store sequences */ - { U32 const extDict = zc->lowLimit < zc->dictLimit; - const ZSTD_blockCompressor blockCompressor = - zc->appliedParams.ldmParams.enableLdm - ? (extDict ? ZSTD_compressBlock_ldm_extDict : ZSTD_compressBlock_ldm) - : ZSTD_selectBlockCompressor(zc->appliedParams.cParams.strategy, extDict); - size_t const lastLLSize = blockCompressor(zc, src, srcSize); - const BYTE* const anchor = (const BYTE*)src + srcSize - lastLLSize; - ZSTD_storeLastLiterals(&zc->seqStore, anchor, lastLLSize); + + /* select and store sequences */ + { U32 const extDict = ZSTD_window_hasExtDict(ms->window); + size_t lastLLSize; + { int i; + for (i = 0; i < ZSTD_REP_NUM; ++i) + zc->blockState.nextCBlock->rep[i] = zc->blockState.prevCBlock->rep[i]; + } + if (zc->externSeqStore.pos < zc->externSeqStore.size) { + assert(!zc->appliedParams.ldmParams.enableLdm); + /* Updates ldmSeqStore.pos */ + lastLLSize = + ZSTD_ldm_blockCompress(&zc->externSeqStore, + ms, &zc->seqStore, + zc->blockState.nextCBlock->rep, + &zc->appliedParams.cParams, + src, srcSize, extDict); + assert(zc->externSeqStore.pos <= zc->externSeqStore.size); + } else if (zc->appliedParams.ldmParams.enableLdm) { + rawSeqStore_t ldmSeqStore = {NULL, 0, 0, 0}; + + ldmSeqStore.seq = zc->ldmSequences; + ldmSeqStore.capacity = zc->maxNbLdmSequences; + /* Updates ldmSeqStore.size */ + CHECK_F(ZSTD_ldm_generateSequences(&zc->ldmState, &ldmSeqStore, + &zc->appliedParams.ldmParams, + src, srcSize)); + /* Updates ldmSeqStore.pos */ + lastLLSize = + ZSTD_ldm_blockCompress(&ldmSeqStore, + ms, &zc->seqStore, + zc->blockState.nextCBlock->rep, + &zc->appliedParams.cParams, + src, srcSize, extDict); + assert(ldmSeqStore.pos == ldmSeqStore.size); + } else { /* not long range mode */ + ZSTD_blockCompressor const blockCompressor = ZSTD_selectBlockCompressor(zc->appliedParams.cParams.strategy, extDict); + lastLLSize = blockCompressor(ms, &zc->seqStore, zc->blockState.nextCBlock->rep, &zc->appliedParams.cParams, src, srcSize); + } + { const BYTE* const lastLiterals = (const BYTE*)src + srcSize - lastLLSize; + ZSTD_storeLastLiterals(&zc->seqStore, lastLiterals, lastLLSize); + } } + + /* encode sequences and literals */ + { size_t const cSize = ZSTD_compressSequences(&zc->seqStore, + &zc->blockState.prevCBlock->entropy, &zc->blockState.nextCBlock->entropy, + &zc->appliedParams, + dst, dstCapacity, + srcSize, zc->entropyWorkspace, zc->bmi2); + if (ZSTD_isError(cSize) || cSize == 0) return cSize; + /* confirm repcodes and entropy tables */ + { ZSTD_compressedBlockState_t* const tmp = zc->blockState.prevCBlock; + zc->blockState.prevCBlock = zc->blockState.nextCBlock; + zc->blockState.nextCBlock = tmp; + } + return cSize; } - /* encode */ - return ZSTD_compressSequences(&zc->seqStore, zc->entropy, &zc->appliedParams.cParams, dst, dstCapacity, srcSize); } @@ -1686,54 +1992,27 @@ static size_t ZSTD_compress_frameChunk (ZSTD_CCtx* cctx, XXH64_update(&cctx->xxhState, src, srcSize); while (remaining) { + ZSTD_matchState_t* const ms = &cctx->blockState.matchState; U32 const lastBlock = lastFrameChunk & (blockSize >= remaining); if (dstCapacity < ZSTD_blockHeaderSize + MIN_CBLOCK_SIZE) return ERROR(dstSize_tooSmall); /* not enough space to store compressed block */ if (remaining < blockSize) blockSize = remaining; - /* preemptive overflow correction: - * 1. correction is large enough: - * lowLimit > (3<<29) ==> current > 3<<29 + 1<<windowLog - blockSize - * 1<<windowLog <= newCurrent < 1<<chainLog + 1<<windowLog - * - * current - newCurrent - * > (3<<29 + 1<<windowLog - blockSize) - (1<<windowLog + 1<<chainLog) - * > (3<<29 - blockSize) - (1<<chainLog) - * > (3<<29 - blockSize) - (1<<30) (NOTE: chainLog <= 30) - * > 1<<29 - 1<<17 - * - * 2. (ip+blockSize - cctx->base) doesn't overflow: - * In 32 bit mode we limit windowLog to 30 so we don't get - * differences larger than 1<<31-1. - * 3. cctx->lowLimit < 1<<32: - * windowLog <= 31 ==> 3<<29 + 1<<windowLog < 7<<29 < 1<<32. - */ - if (cctx->lowLimit > (3U<<29)) { - U32 const cycleMask = ((U32)1 << ZSTD_cycleLog(cctx->appliedParams.cParams.chainLog, cctx->appliedParams.cParams.strategy)) - 1; - U32 const current = (U32)(ip - cctx->base); - U32 const newCurrent = (current & cycleMask) + ((U32)1 << cctx->appliedParams.cParams.windowLog); - U32 const correction = current - newCurrent; + if (ZSTD_window_needOverflowCorrection(ms->window, ip + blockSize)) { + U32 const cycleLog = ZSTD_cycleLog(cctx->appliedParams.cParams.chainLog, cctx->appliedParams.cParams.strategy); + U32 const correction = ZSTD_window_correctOverflow(&ms->window, cycleLog, maxDist, ip); ZSTD_STATIC_ASSERT(ZSTD_CHAINLOG_MAX <= 30); ZSTD_STATIC_ASSERT(ZSTD_WINDOWLOG_MAX_32 <= 30); ZSTD_STATIC_ASSERT(ZSTD_WINDOWLOG_MAX <= 31); - assert(current > newCurrent); - assert(correction > 1<<28); /* Loose bound, should be about 1<<29 */ + ZSTD_reduceIndex(cctx, correction); - cctx->base += correction; - cctx->dictBase += correction; - cctx->lowLimit -= correction; - cctx->dictLimit -= correction; - if (cctx->nextToUpdate < correction) cctx->nextToUpdate = 0; - else cctx->nextToUpdate -= correction; - DEBUGLOG(4, "Correction of 0x%x bytes to lowLimit=0x%x\n", correction, cctx->lowLimit); - } - /* enforce maxDist */ - if ((U32)(ip+blockSize - cctx->base) > cctx->loadedDictEnd + maxDist) { - U32 const newLowLimit = (U32)(ip+blockSize - cctx->base) - maxDist; - if (cctx->lowLimit < newLowLimit) cctx->lowLimit = newLowLimit; - if (cctx->dictLimit < cctx->lowLimit) cctx->dictLimit = cctx->lowLimit; + if (ms->nextToUpdate < correction) ms->nextToUpdate = 0; + else ms->nextToUpdate -= correction; + ms->loadedDictEnd = 0; } + ZSTD_window_enforceMaxDist(&ms->window, ip + blockSize, maxDist, &ms->loadedDictEnd); + if (ms->nextToUpdate < ms->window.lowLimit) ms->nextToUpdate = ms->window.lowLimit; { size_t cSize = ZSTD_compressBlock_internal(cctx, op+ZSTD_blockHeaderSize, dstCapacity-ZSTD_blockHeaderSize, @@ -1810,16 +2089,44 @@ static size_t ZSTD_writeFrameHeader(void* dst, size_t dstCapacity, return pos; } +/* ZSTD_writeLastEmptyBlock() : + * output an empty Block with end-of-frame mark to complete a frame + * @return : size of data written into `dst` (== ZSTD_blockHeaderSize (defined in zstd_internal.h)) + * or an error code if `dstCapcity` is too small (<ZSTD_blockHeaderSize) + */ +size_t ZSTD_writeLastEmptyBlock(void* dst, size_t dstCapacity) +{ + if (dstCapacity < ZSTD_blockHeaderSize) return ERROR(dstSize_tooSmall); + { U32 const cBlockHeader24 = 1 /*lastBlock*/ + (((U32)bt_raw)<<1); /* 0 size */ + MEM_writeLE24(dst, cBlockHeader24); + return ZSTD_blockHeaderSize; + } +} + +size_t ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq) +{ + if (cctx->stage != ZSTDcs_init) + return ERROR(stage_wrong); + if (cctx->appliedParams.ldmParams.enableLdm) + return ERROR(parameter_unsupported); + cctx->externSeqStore.seq = seq; + cctx->externSeqStore.size = nbSeq; + cctx->externSeqStore.capacity = nbSeq; + cctx->externSeqStore.pos = 0; + return 0; +} + static size_t ZSTD_compressContinue_internal (ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, U32 frame, U32 lastFrameChunk) { - const BYTE* const ip = (const BYTE*) src; + ZSTD_matchState_t* ms = &cctx->blockState.matchState; size_t fhSize = 0; - DEBUGLOG(5, "ZSTD_compressContinue_internal, stage: %u", cctx->stage); + DEBUGLOG(5, "ZSTD_compressContinue_internal, stage: %u, srcSize: %u", + cctx->stage, (U32)srcSize); if (cctx->stage==ZSTDcs_created) return ERROR(stage_wrong); /* missing init (ZSTD_compressBegin) */ if (frame && (cctx->stage==ZSTDcs_init)) { @@ -1833,26 +2140,11 @@ static size_t ZSTD_compressContinue_internal (ZSTD_CCtx* cctx, if (!srcSize) return fhSize; /* do not generate an empty block if no input */ - /* Check if blocks follow each other */ - if (src != cctx->nextSrc) { - /* not contiguous */ - size_t const distanceFromBase = (size_t)(cctx->nextSrc - cctx->base); - cctx->lowLimit = cctx->dictLimit; - assert(distanceFromBase == (size_t)(U32)distanceFromBase); /* should never overflow */ - cctx->dictLimit = (U32)distanceFromBase; - cctx->dictBase = cctx->base; - cctx->base = ip - distanceFromBase; - cctx->nextToUpdate = cctx->dictLimit; - if (cctx->dictLimit - cctx->lowLimit < HASH_READ_SIZE) cctx->lowLimit = cctx->dictLimit; /* too small extDict */ - } - cctx->nextSrc = ip + srcSize; - - /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */ - if ((ip+srcSize > cctx->dictBase + cctx->lowLimit) & (ip < cctx->dictBase + cctx->dictLimit)) { - ptrdiff_t const highInputIdx = (ip + srcSize) - cctx->dictBase; - U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)cctx->dictLimit) ? cctx->dictLimit : (U32)highInputIdx; - cctx->lowLimit = lowLimitMax; + if (!ZSTD_window_update(&ms->window, src, srcSize)) { + ms->nextToUpdate = ms->window.dictLimit; } + if (cctx->appliedParams.ldmParams.enableLdm) + ZSTD_window_update(&cctx->ldmState.window, src, srcSize); DEBUGLOG(5, "ZSTD_compressContinue_internal (blockSize=%u)", (U32)cctx->blockSize); { size_t const cSize = frame ? @@ -1860,6 +2152,14 @@ static size_t ZSTD_compressContinue_internal (ZSTD_CCtx* cctx, ZSTD_compressBlock_internal (cctx, dst, dstCapacity, src, srcSize); if (ZSTD_isError(cSize)) return cSize; cctx->consumedSrcSize += srcSize; + cctx->producedCSize += (cSize + fhSize); + if (cctx->appliedParams.fParams.contentSizeFlag) { /* control src size */ + if (cctx->consumedSrcSize+1 > cctx->pledgedSrcSizePlusOne) { + DEBUGLOG(4, "error : pledgedSrcSize = %u, while realSrcSize >= %u", + (U32)cctx->pledgedSrcSizePlusOne-1, (U32)cctx->consumedSrcSize); + return ERROR(srcSize_wrong); + } + } return cSize + fhSize; } } @@ -1868,14 +2168,15 @@ size_t ZSTD_compressContinue (ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize) { + DEBUGLOG(5, "ZSTD_compressContinue (srcSize=%u)", (U32)srcSize); return ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 1 /* frame mode */, 0 /* last chunk */); } size_t ZSTD_getBlockSize(const ZSTD_CCtx* cctx) { - ZSTD_compressionParameters const cParams = - ZSTD_getCParamsFromCCtxParams(cctx->appliedParams, 0, 0); + ZSTD_compressionParameters const cParams = cctx->appliedParams.cParams; + assert(!ZSTD_checkCParams(cParams)); return MIN (ZSTD_BLOCKSIZE_MAX, (U32)1 << cParams.windowLog); } @@ -1889,50 +2190,45 @@ size_t ZSTD_compressBlock(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const /*! ZSTD_loadDictionaryContent() : * @return : 0, or an error code */ -static size_t ZSTD_loadDictionaryContent(ZSTD_CCtx* zc, const void* src, size_t srcSize) +static size_t ZSTD_loadDictionaryContent(ZSTD_matchState_t* ms, ZSTD_CCtx_params const* params, const void* src, size_t srcSize) { const BYTE* const ip = (const BYTE*) src; const BYTE* const iend = ip + srcSize; + ZSTD_compressionParameters const* cParams = ¶ms->cParams; - /* input becomes current prefix */ - zc->lowLimit = zc->dictLimit; - zc->dictLimit = (U32)(zc->nextSrc - zc->base); - zc->dictBase = zc->base; - zc->base = ip - zc->dictLimit; - zc->nextToUpdate = zc->dictLimit; - zc->loadedDictEnd = zc->appliedParams.forceWindow ? 0 : (U32)(iend - zc->base); + ZSTD_window_update(&ms->window, src, srcSize); + ms->loadedDictEnd = params->forceWindow ? 0 : (U32)(iend - ms->window.base); - zc->nextSrc = iend; if (srcSize <= HASH_READ_SIZE) return 0; - switch(zc->appliedParams.cParams.strategy) + switch(params->cParams.strategy) { case ZSTD_fast: - ZSTD_fillHashTable (zc, iend, zc->appliedParams.cParams.searchLength); + ZSTD_fillHashTable(ms, cParams, iend); break; case ZSTD_dfast: - ZSTD_fillDoubleHashTable (zc, iend, zc->appliedParams.cParams.searchLength); + ZSTD_fillDoubleHashTable(ms, cParams, iend); break; case ZSTD_greedy: case ZSTD_lazy: case ZSTD_lazy2: if (srcSize >= HASH_READ_SIZE) - ZSTD_insertAndFindFirstIndex(zc, iend-HASH_READ_SIZE, zc->appliedParams.cParams.searchLength); + ZSTD_insertAndFindFirstIndex(ms, cParams, iend-HASH_READ_SIZE); break; - case ZSTD_btlazy2: + case ZSTD_btlazy2: /* we want the dictionary table fully sorted */ case ZSTD_btopt: case ZSTD_btultra: if (srcSize >= HASH_READ_SIZE) - ZSTD_updateTree(zc, iend-HASH_READ_SIZE, iend, (U32)1 << zc->appliedParams.cParams.searchLog, zc->appliedParams.cParams.searchLength); + ZSTD_updateTree(ms, cParams, iend-HASH_READ_SIZE, iend); break; default: assert(0); /* not possible : not a valid strategy id */ } - zc->nextToUpdate = (U32)(iend - zc->base); + ms->nextToUpdate = (U32)(iend - ms->window.base); return 0; } @@ -1956,25 +2252,26 @@ static size_t ZSTD_checkDictNCount(short* normalizedCounter, unsigned dictMaxSym * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#dictionary-format */ /*! ZSTD_loadZstdDictionary() : - * @return : 0, or an error code + * @return : dictID, or an error code * assumptions : magic number supposed already checked * dictSize supposed > 8 */ -static size_t ZSTD_loadZstdDictionary(ZSTD_CCtx* cctx, const void* dict, size_t dictSize) +static size_t ZSTD_loadZstdDictionary(ZSTD_compressedBlockState_t* bs, ZSTD_matchState_t* ms, ZSTD_CCtx_params const* params, const void* dict, size_t dictSize, void* workspace) { const BYTE* dictPtr = (const BYTE*)dict; const BYTE* const dictEnd = dictPtr + dictSize; short offcodeNCount[MaxOff+1]; unsigned offcodeMaxValue = MaxOff; + size_t dictID; - ZSTD_STATIC_ASSERT(sizeof(cctx->entropy->workspace) >= (1<<MAX(MLFSELog,LLFSELog))); + ZSTD_STATIC_ASSERT(HUF_WORKSPACE_SIZE >= (1<<MAX(MLFSELog,LLFSELog))); dictPtr += 4; /* skip magic number */ - cctx->dictID = cctx->appliedParams.fParams.noDictIDFlag ? 0 : MEM_readLE32(dictPtr); + dictID = params->fParams.noDictIDFlag ? 0 : MEM_readLE32(dictPtr); dictPtr += 4; { unsigned maxSymbolValue = 255; - size_t const hufHeaderSize = HUF_readCTable((HUF_CElt*)cctx->entropy->hufCTable, &maxSymbolValue, dictPtr, dictEnd-dictPtr); + size_t const hufHeaderSize = HUF_readCTable((HUF_CElt*)bs->entropy.hufCTable, &maxSymbolValue, dictPtr, dictEnd-dictPtr); if (HUF_isError(hufHeaderSize)) return ERROR(dictionary_corrupted); if (maxSymbolValue < 255) return ERROR(dictionary_corrupted); dictPtr += hufHeaderSize; @@ -1985,7 +2282,7 @@ static size_t ZSTD_loadZstdDictionary(ZSTD_CCtx* cctx, const void* dict, size_t if (FSE_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted); if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted); /* Defer checking offcodeMaxValue because we need to know the size of the dictionary content */ - CHECK_E( FSE_buildCTable_wksp(cctx->entropy->offcodeCTable, offcodeNCount, offcodeMaxValue, offcodeLog, cctx->entropy->workspace, sizeof(cctx->entropy->workspace)), + CHECK_E( FSE_buildCTable_wksp(bs->entropy.offcodeCTable, offcodeNCount, offcodeMaxValue, offcodeLog, workspace, HUF_WORKSPACE_SIZE), dictionary_corrupted); dictPtr += offcodeHeaderSize; } @@ -1997,7 +2294,7 @@ static size_t ZSTD_loadZstdDictionary(ZSTD_CCtx* cctx, const void* dict, size_t if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted); /* Every match length code must have non-zero probability */ CHECK_F( ZSTD_checkDictNCount(matchlengthNCount, matchlengthMaxValue, MaxML)); - CHECK_E( FSE_buildCTable_wksp(cctx->entropy->matchlengthCTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog, cctx->entropy->workspace, sizeof(cctx->entropy->workspace)), + CHECK_E( FSE_buildCTable_wksp(bs->entropy.matchlengthCTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog, workspace, HUF_WORKSPACE_SIZE), dictionary_corrupted); dictPtr += matchlengthHeaderSize; } @@ -2009,15 +2306,15 @@ static size_t ZSTD_loadZstdDictionary(ZSTD_CCtx* cctx, const void* dict, size_t if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted); /* Every literal length code must have non-zero probability */ CHECK_F( ZSTD_checkDictNCount(litlengthNCount, litlengthMaxValue, MaxLL)); - CHECK_E( FSE_buildCTable_wksp(cctx->entropy->litlengthCTable, litlengthNCount, litlengthMaxValue, litlengthLog, cctx->entropy->workspace, sizeof(cctx->entropy->workspace)), + CHECK_E( FSE_buildCTable_wksp(bs->entropy.litlengthCTable, litlengthNCount, litlengthMaxValue, litlengthLog, workspace, HUF_WORKSPACE_SIZE), dictionary_corrupted); dictPtr += litlengthHeaderSize; } if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted); - cctx->seqStore.rep[0] = MEM_readLE32(dictPtr+0); - cctx->seqStore.rep[1] = MEM_readLE32(dictPtr+4); - cctx->seqStore.rep[2] = MEM_readLE32(dictPtr+8); + bs->rep[0] = MEM_readLE32(dictPtr+0); + bs->rep[1] = MEM_readLE32(dictPtr+4); + bs->rep[2] = MEM_readLE32(dictPtr+8); dictPtr += 12; { size_t const dictContentSize = (size_t)(dictEnd - dictPtr); @@ -2031,50 +2328,55 @@ static size_t ZSTD_loadZstdDictionary(ZSTD_CCtx* cctx, const void* dict, size_t /* All repCodes must be <= dictContentSize and != 0*/ { U32 u; for (u=0; u<3; u++) { - if (cctx->seqStore.rep[u] == 0) return ERROR(dictionary_corrupted); - if (cctx->seqStore.rep[u] > dictContentSize) return ERROR(dictionary_corrupted); + if (bs->rep[u] == 0) return ERROR(dictionary_corrupted); + if (bs->rep[u] > dictContentSize) return ERROR(dictionary_corrupted); } } - cctx->entropy->hufCTable_repeatMode = HUF_repeat_valid; - cctx->entropy->offcode_repeatMode = FSE_repeat_valid; - cctx->entropy->matchlength_repeatMode = FSE_repeat_valid; - cctx->entropy->litlength_repeatMode = FSE_repeat_valid; - return ZSTD_loadDictionaryContent(cctx, dictPtr, dictContentSize); + bs->entropy.hufCTable_repeatMode = HUF_repeat_valid; + bs->entropy.offcode_repeatMode = FSE_repeat_valid; + bs->entropy.matchlength_repeatMode = FSE_repeat_valid; + bs->entropy.litlength_repeatMode = FSE_repeat_valid; + CHECK_F(ZSTD_loadDictionaryContent(ms, params, dictPtr, dictContentSize)); + return dictID; } } /** ZSTD_compress_insertDictionary() : -* @return : 0, or an error code */ -static size_t ZSTD_compress_insertDictionary(ZSTD_CCtx* cctx, +* @return : dictID, or an error code */ +static size_t ZSTD_compress_insertDictionary(ZSTD_compressedBlockState_t* bs, ZSTD_matchState_t* ms, + ZSTD_CCtx_params const* params, const void* dict, size_t dictSize, - ZSTD_dictMode_e dictMode) + ZSTD_dictContentType_e dictContentType, + void* workspace) { DEBUGLOG(4, "ZSTD_compress_insertDictionary (dictSize=%u)", (U32)dictSize); if ((dict==NULL) || (dictSize<=8)) return 0; + ZSTD_reset_compressedBlockState(bs); + /* dict restricted modes */ - if (dictMode==ZSTD_dm_rawContent) - return ZSTD_loadDictionaryContent(cctx, dict, dictSize); + if (dictContentType == ZSTD_dct_rawContent) + return ZSTD_loadDictionaryContent(ms, params, dict, dictSize); if (MEM_readLE32(dict) != ZSTD_MAGIC_DICTIONARY) { - if (dictMode == ZSTD_dm_auto) { + if (dictContentType == ZSTD_dct_auto) { DEBUGLOG(4, "raw content dictionary detected"); - return ZSTD_loadDictionaryContent(cctx, dict, dictSize); + return ZSTD_loadDictionaryContent(ms, params, dict, dictSize); } - if (dictMode == ZSTD_dm_fullDict) + if (dictContentType == ZSTD_dct_fullDict) return ERROR(dictionary_wrong); assert(0); /* impossible */ } /* dict as full zstd dictionary */ - return ZSTD_loadZstdDictionary(cctx, dict, dictSize); + return ZSTD_loadZstdDictionary(bs, ms, params, dict, dictSize, workspace); } /*! ZSTD_compressBegin_internal() : * @return : 0, or an error code */ size_t ZSTD_compressBegin_internal(ZSTD_CCtx* cctx, const void* dict, size_t dictSize, - ZSTD_dictMode_e dictMode, + ZSTD_dictContentType_e dictContentType, const ZSTD_CDict* cdict, ZSTD_CCtx_params params, U64 pledgedSrcSize, ZSTD_buffered_policy_e zbuff) @@ -2086,19 +2388,26 @@ size_t ZSTD_compressBegin_internal(ZSTD_CCtx* cctx, if (cdict && cdict->dictContentSize>0) { cctx->requestedParams = params; - return ZSTD_copyCCtx_internal(cctx, cdict->refContext, - params.cParams.windowLog, params.fParams, pledgedSrcSize, - zbuff); + return ZSTD_resetCCtx_usingCDict(cctx, cdict, params.cParams.windowLog, + params.fParams, pledgedSrcSize, zbuff); } CHECK_F( ZSTD_resetCCtx_internal(cctx, params, pledgedSrcSize, ZSTDcrp_continue, zbuff) ); - return ZSTD_compress_insertDictionary(cctx, dict, dictSize, dictMode); + { + size_t const dictID = ZSTD_compress_insertDictionary( + cctx->blockState.prevCBlock, &cctx->blockState.matchState, + ¶ms, dict, dictSize, dictContentType, cctx->entropyWorkspace); + if (ZSTD_isError(dictID)) return dictID; + assert(dictID <= (size_t)(U32)-1); + cctx->dictID = (U32)dictID; + } + return 0; } size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx* cctx, const void* dict, size_t dictSize, - ZSTD_dictMode_e dictMode, + ZSTD_dictContentType_e dictContentType, const ZSTD_CDict* cdict, ZSTD_CCtx_params params, unsigned long long pledgedSrcSize) @@ -2107,7 +2416,7 @@ size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx* cctx, /* compression parameters verification and optimization */ CHECK_F( ZSTD_checkCParams(params.cParams) ); return ZSTD_compressBegin_internal(cctx, - dict, dictSize, dictMode, + dict, dictSize, dictContentType, cdict, params, pledgedSrcSize, ZSTDb_not_buffered); @@ -2122,18 +2431,18 @@ size_t ZSTD_compressBegin_advanced(ZSTD_CCtx* cctx, ZSTD_CCtx_params const cctxParams = ZSTD_assignParamsToCCtxParams(cctx->requestedParams, params); return ZSTD_compressBegin_advanced_internal(cctx, - dict, dictSize, ZSTD_dm_auto, + dict, dictSize, ZSTD_dct_auto, NULL /*cdict*/, cctxParams, pledgedSrcSize); } size_t ZSTD_compressBegin_usingDict(ZSTD_CCtx* cctx, const void* dict, size_t dictSize, int compressionLevel) { - ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, dictSize); + ZSTD_parameters const params = ZSTD_getParams(compressionLevel, ZSTD_CONTENTSIZE_UNKNOWN, dictSize); ZSTD_CCtx_params const cctxParams = ZSTD_assignParamsToCCtxParams(cctx->requestedParams, params); - DEBUGLOG(4, "ZSTD_compressBegin_usingDict"); - return ZSTD_compressBegin_internal(cctx, dict, dictSize, ZSTD_dm_auto, NULL, + DEBUGLOG(4, "ZSTD_compressBegin_usingDict (dictSize=%u)", (U32)dictSize); + return ZSTD_compressBegin_internal(cctx, dict, dictSize, ZSTD_dct_auto, NULL, cctxParams, ZSTD_CONTENTSIZE_UNKNOWN, ZSTDb_not_buffered); } @@ -2152,7 +2461,7 @@ static size_t ZSTD_writeEpilogue(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity) BYTE* op = ostart; size_t fhSize = 0; - DEBUGLOG(5, "ZSTD_writeEpilogue"); + DEBUGLOG(4, "ZSTD_writeEpilogue"); if (cctx->stage == ZSTDcs_created) return ERROR(stage_wrong); /* init missing */ /* special case : empty frame */ @@ -2176,6 +2485,7 @@ static size_t ZSTD_writeEpilogue(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity) if (cctx->appliedParams.fParams.checksumFlag) { U32 const checksum = (U32) XXH64_digest(&cctx->xxhState); if (dstCapacity<4) return ERROR(dstSize_tooSmall); + DEBUGLOG(4, "ZSTD_writeEpilogue: write checksum : %08X", checksum); MEM_writeLE32(op, checksum); op += 4; } @@ -2184,7 +2494,6 @@ static size_t ZSTD_writeEpilogue(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity) return op-ostart; } - size_t ZSTD_compressEnd (ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize) @@ -2242,25 +2551,27 @@ size_t ZSTD_compress_advanced_internal( const void* dict,size_t dictSize, ZSTD_CCtx_params params) { - DEBUGLOG(4, "ZSTD_compress_advanced_internal"); - CHECK_F( ZSTD_compressBegin_internal(cctx, dict, dictSize, ZSTD_dm_auto, NULL, + DEBUGLOG(4, "ZSTD_compress_advanced_internal (srcSize:%u)", + (U32)srcSize); + CHECK_F( ZSTD_compressBegin_internal(cctx, dict, dictSize, ZSTD_dct_auto, NULL, params, srcSize, ZSTDb_not_buffered) ); return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize); } -size_t ZSTD_compress_usingDict(ZSTD_CCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, +size_t ZSTD_compress_usingDict(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, const void* dict, size_t dictSize, int compressionLevel) { - ZSTD_parameters params = ZSTD_getParams(compressionLevel, srcSize ? srcSize : 1, dict ? dictSize : 0); - params.fParams.contentSizeFlag = 1; - DEBUGLOG(4, "ZSTD_compress_usingDict (level=%i, srcSize=%u, dictSize=%u)", - compressionLevel, (U32)srcSize, (U32)dictSize); - return ZSTD_compress_internal(ctx, dst, dstCapacity, src, srcSize, dict, dictSize, params); + ZSTD_parameters const params = ZSTD_getParams(compressionLevel, srcSize ? srcSize : 1, dict ? dictSize : 0); + ZSTD_CCtx_params cctxParams = ZSTD_assignParamsToCCtxParams(cctx->requestedParams, params); + assert(params.fParams.contentSizeFlag == 1); + ZSTD_CCtxParam_setParameter(&cctxParams, ZSTD_p_compressLiterals, compressionLevel>=0); + return ZSTD_compress_advanced_internal(cctx, dst, dstCapacity, src, srcSize, dict, dictSize, cctxParams); } -size_t ZSTD_compressCCtx (ZSTD_CCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, int compressionLevel) +size_t ZSTD_compressCCtx (ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, int compressionLevel) { - return ZSTD_compress_usingDict(ctx, dst, dstCapacity, src, srcSize, NULL, 0, compressionLevel); + DEBUGLOG(4, "ZSTD_compressCCtx (srcSize=%u)", (U32)srcSize); + return ZSTD_compress_usingDict(cctx, dst, dstCapacity, src, srcSize, NULL, 0, compressionLevel); } size_t ZSTD_compress(void* dst, size_t dstCapacity, const void* src, size_t srcSize, int compressionLevel) @@ -2284,9 +2595,7 @@ size_t ZSTD_estimateCDictSize_advanced( ZSTD_dictLoadMethod_e dictLoadMethod) { DEBUGLOG(5, "sizeof(ZSTD_CDict) : %u", (U32)sizeof(ZSTD_CDict)); - DEBUGLOG(5, "CCtx estimate : %u", - (U32)ZSTD_estimateCCtxSize_usingCParams(cParams)); - return sizeof(ZSTD_CDict) + ZSTD_estimateCCtxSize_usingCParams(cParams) + return sizeof(ZSTD_CDict) + HUF_WORKSPACE_SIZE + ZSTD_sizeof_matchState(&cParams, /* forCCtx */ 0) + (dictLoadMethod == ZSTD_dlm_byRef ? 0 : dictSize); } @@ -2300,23 +2609,24 @@ size_t ZSTD_sizeof_CDict(const ZSTD_CDict* cdict) { if (cdict==NULL) return 0; /* support sizeof on NULL */ DEBUGLOG(5, "sizeof(*cdict) : %u", (U32)sizeof(*cdict)); - DEBUGLOG(5, "ZSTD_sizeof_CCtx : %u", (U32)ZSTD_sizeof_CCtx(cdict->refContext)); - return ZSTD_sizeof_CCtx(cdict->refContext) + (cdict->dictBuffer ? cdict->dictContentSize : 0) + sizeof(*cdict); + return cdict->workspaceSize + (cdict->dictBuffer ? cdict->dictContentSize : 0) + sizeof(*cdict); } static size_t ZSTD_initCDict_internal( ZSTD_CDict* cdict, const void* dictBuffer, size_t dictSize, ZSTD_dictLoadMethod_e dictLoadMethod, - ZSTD_dictMode_e dictMode, + ZSTD_dictContentType_e dictContentType, ZSTD_compressionParameters cParams) { - DEBUGLOG(3, "ZSTD_initCDict_internal, mode %u", (U32)dictMode); + DEBUGLOG(3, "ZSTD_initCDict_internal, dictContentType %u", (U32)dictContentType); + assert(!ZSTD_checkCParams(cParams)); + cdict->cParams = cParams; if ((dictLoadMethod == ZSTD_dlm_byRef) || (!dictBuffer) || (!dictSize)) { cdict->dictBuffer = NULL; cdict->dictContent = dictBuffer; } else { - void* const internalBuffer = ZSTD_malloc(dictSize, cdict->refContext->customMem); + void* const internalBuffer = ZSTD_malloc(dictSize, cdict->customMem); cdict->dictBuffer = internalBuffer; cdict->dictContent = internalBuffer; if (!internalBuffer) return ERROR(memory_allocation); @@ -2324,13 +2634,31 @@ static size_t ZSTD_initCDict_internal( } cdict->dictContentSize = dictSize; - { ZSTD_CCtx_params cctxParams = cdict->refContext->requestedParams; - cctxParams.cParams = cParams; - CHECK_F( ZSTD_compressBegin_internal(cdict->refContext, - cdict->dictContent, dictSize, dictMode, - NULL, - cctxParams, ZSTD_CONTENTSIZE_UNKNOWN, - ZSTDb_not_buffered) ); + /* Reset the state to no dictionary */ + ZSTD_reset_compressedBlockState(&cdict->cBlockState); + { void* const end = ZSTD_reset_matchState( + &cdict->matchState, + (U32*)cdict->workspace + HUF_WORKSPACE_SIZE_U32, + &cParams, ZSTDcrp_continue, /* forCCtx */ 0); + assert(end == (char*)cdict->workspace + cdict->workspaceSize); + (void)end; + } + /* (Maybe) load the dictionary + * Skips loading the dictionary if it is <= 8 bytes. + */ + { ZSTD_CCtx_params params; + memset(¶ms, 0, sizeof(params)); + params.compressionLevel = ZSTD_CLEVEL_DEFAULT; + params.fParams.contentSizeFlag = 1; + params.cParams = cParams; + { size_t const dictID = ZSTD_compress_insertDictionary( + &cdict->cBlockState, &cdict->matchState, ¶ms, + cdict->dictContent, cdict->dictContentSize, + dictContentType, cdict->workspace); + if (ZSTD_isError(dictID)) return dictID; + assert(dictID <= (size_t)(U32)-1); + cdict->dictID = (U32)dictID; + } } return 0; @@ -2338,24 +2666,27 @@ static size_t ZSTD_initCDict_internal( ZSTD_CDict* ZSTD_createCDict_advanced(const void* dictBuffer, size_t dictSize, ZSTD_dictLoadMethod_e dictLoadMethod, - ZSTD_dictMode_e dictMode, + ZSTD_dictContentType_e dictContentType, ZSTD_compressionParameters cParams, ZSTD_customMem customMem) { - DEBUGLOG(3, "ZSTD_createCDict_advanced, mode %u", (U32)dictMode); + DEBUGLOG(3, "ZSTD_createCDict_advanced, mode %u", (U32)dictContentType); if (!customMem.customAlloc ^ !customMem.customFree) return NULL; { ZSTD_CDict* const cdict = (ZSTD_CDict*)ZSTD_malloc(sizeof(ZSTD_CDict), customMem); - ZSTD_CCtx* const cctx = ZSTD_createCCtx_advanced(customMem); + size_t const workspaceSize = HUF_WORKSPACE_SIZE + ZSTD_sizeof_matchState(&cParams, /* forCCtx */ 0); + void* const workspace = ZSTD_malloc(workspaceSize, customMem); - if (!cdict || !cctx) { + if (!cdict || !workspace) { ZSTD_free(cdict, customMem); - ZSTD_freeCCtx(cctx); + ZSTD_free(workspace, customMem); return NULL; } - cdict->refContext = cctx; + cdict->customMem = customMem; + cdict->workspace = workspace; + cdict->workspaceSize = workspaceSize; if (ZSTD_isError( ZSTD_initCDict_internal(cdict, dictBuffer, dictSize, - dictLoadMethod, dictMode, + dictLoadMethod, dictContentType, cParams) )) { ZSTD_freeCDict(cdict); return NULL; @@ -2369,7 +2700,7 @@ ZSTD_CDict* ZSTD_createCDict(const void* dict, size_t dictSize, int compressionL { ZSTD_compressionParameters cParams = ZSTD_getCParams(compressionLevel, 0, dictSize); return ZSTD_createCDict_advanced(dict, dictSize, - ZSTD_dlm_byCopy, ZSTD_dm_auto, + ZSTD_dlm_byCopy, ZSTD_dct_auto, cParams, ZSTD_defaultCMem); } @@ -2377,15 +2708,15 @@ ZSTD_CDict* ZSTD_createCDict_byReference(const void* dict, size_t dictSize, int { ZSTD_compressionParameters cParams = ZSTD_getCParams(compressionLevel, 0, dictSize); return ZSTD_createCDict_advanced(dict, dictSize, - ZSTD_dlm_byRef, ZSTD_dm_auto, + ZSTD_dlm_byRef, ZSTD_dct_auto, cParams, ZSTD_defaultCMem); } size_t ZSTD_freeCDict(ZSTD_CDict* cdict) { if (cdict==NULL) return 0; /* support free on NULL */ - { ZSTD_customMem const cMem = cdict->refContext->customMem; - ZSTD_freeCCtx(cdict->refContext); + { ZSTD_customMem const cMem = cdict->customMem; + ZSTD_free(cdict->workspace, cMem); ZSTD_free(cdict->dictBuffer, cMem); ZSTD_free(cdict, cMem); return 0; @@ -2405,18 +2736,18 @@ size_t ZSTD_freeCDict(ZSTD_CDict* cdict) * Note : there is no corresponding "free" function. * Since workspace was allocated externally, it must be freed externally. */ -ZSTD_CDict* ZSTD_initStaticCDict(void* workspace, size_t workspaceSize, +const ZSTD_CDict* ZSTD_initStaticCDict( + void* workspace, size_t workspaceSize, const void* dict, size_t dictSize, ZSTD_dictLoadMethod_e dictLoadMethod, - ZSTD_dictMode_e dictMode, + ZSTD_dictContentType_e dictContentType, ZSTD_compressionParameters cParams) { - size_t const cctxSize = ZSTD_estimateCCtxSize_usingCParams(cParams); + size_t const matchStateSize = ZSTD_sizeof_matchState(&cParams, /* forCCtx */ 0); size_t const neededSize = sizeof(ZSTD_CDict) + (dictLoadMethod == ZSTD_dlm_byRef ? 0 : dictSize) - + cctxSize; + + HUF_WORKSPACE_SIZE + matchStateSize; ZSTD_CDict* const cdict = (ZSTD_CDict*) workspace; void* ptr; - DEBUGLOG(4, "(size_t)workspace & 7 : %u", (U32)(size_t)workspace & 7); if ((size_t)workspace & 7) return NULL; /* 8-aligned */ DEBUGLOG(4, "(workspaceSize < neededSize) : (%u < %u) => %u", (U32)workspaceSize, (U32)neededSize, (U32)(workspaceSize < neededSize)); @@ -2429,19 +2760,22 @@ ZSTD_CDict* ZSTD_initStaticCDict(void* workspace, size_t workspaceSize, } else { ptr = cdict+1; } - cdict->refContext = ZSTD_initStaticCCtx(ptr, cctxSize); + cdict->workspace = ptr; + cdict->workspaceSize = HUF_WORKSPACE_SIZE + matchStateSize; if (ZSTD_isError( ZSTD_initCDict_internal(cdict, dict, dictSize, - ZSTD_dlm_byRef, dictMode, + ZSTD_dlm_byRef, dictContentType, cParams) )) return NULL; return cdict; } -ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict) { - return cdict->refContext->appliedParams.cParams; +ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict) +{ + assert(cdict != NULL); + return cdict->cParams; } /* ZSTD_compressBegin_usingCDict_advanced() : @@ -2454,9 +2788,18 @@ size_t ZSTD_compressBegin_usingCDict_advanced( if (cdict==NULL) return ERROR(dictionary_wrong); { ZSTD_CCtx_params params = cctx->requestedParams; params.cParams = ZSTD_getCParamsFromCDict(cdict); + /* Increase window log to fit the entire dictionary and source if the + * source size is known. Limit the increase to 19, which is the + * window log for compression level 1 with the largest source size. + */ + if (pledgedSrcSize != ZSTD_CONTENTSIZE_UNKNOWN) { + U32 const limitedSrcSize = (U32)MIN(pledgedSrcSize, 1U << 19); + U32 const limitedSrcLog = limitedSrcSize > 1 ? ZSTD_highbit32(limitedSrcSize - 1) + 1 : 1; + params.cParams.windowLog = MAX(params.cParams.windowLog, limitedSrcLog); + } params.fParams = fParams; return ZSTD_compressBegin_internal(cctx, - NULL, 0, ZSTD_dm_auto, + NULL, 0, ZSTD_dct_auto, cdict, params, pledgedSrcSize, ZSTDb_not_buffered); @@ -2534,29 +2877,30 @@ size_t ZSTD_CStreamOutSize(void) return ZSTD_compressBound(ZSTD_BLOCKSIZE_MAX) + ZSTD_blockHeaderSize + 4 /* 32-bits hash */ ; } -static size_t ZSTD_resetCStream_internal(ZSTD_CStream* zcs, - const void* const dict, size_t const dictSize, ZSTD_dictMode_e const dictMode, +static size_t ZSTD_resetCStream_internal(ZSTD_CStream* cctx, + const void* const dict, size_t const dictSize, ZSTD_dictContentType_e const dictContentType, const ZSTD_CDict* const cdict, ZSTD_CCtx_params const params, unsigned long long const pledgedSrcSize) { - DEBUGLOG(4, "ZSTD_resetCStream_internal"); + DEBUGLOG(4, "ZSTD_resetCStream_internal (disableLiteralCompression=%i)", + params.disableLiteralCompression); /* params are supposed to be fully validated at this point */ assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams))); assert(!((dict) && (cdict))); /* either dict or cdict, not both */ - CHECK_F( ZSTD_compressBegin_internal(zcs, - dict, dictSize, dictMode, + CHECK_F( ZSTD_compressBegin_internal(cctx, + dict, dictSize, dictContentType, cdict, params, pledgedSrcSize, ZSTDb_buffered) ); - zcs->inToCompress = 0; - zcs->inBuffPos = 0; - zcs->inBuffTarget = zcs->blockSize - + (zcs->blockSize == pledgedSrcSize); /* for small input: avoid automatic flush on reaching end of block, since it would require to add a 3-bytes null block to end frame */ - zcs->outBuffContentSize = zcs->outBuffFlushedSize = 0; - zcs->streamStage = zcss_load; - zcs->frameEnded = 0; + cctx->inToCompress = 0; + cctx->inBuffPos = 0; + cctx->inBuffTarget = cctx->blockSize + + (cctx->blockSize == pledgedSrcSize); /* for small input: avoid automatic flush on reaching end of block, since it would require to add a 3-bytes null block to end frame */ + cctx->outBuffContentSize = cctx->outBuffFlushedSize = 0; + cctx->streamStage = zcss_load; + cctx->frameEnded = 0; return 0; /* ready to go */ } @@ -2568,8 +2912,8 @@ size_t ZSTD_resetCStream(ZSTD_CStream* zcs, unsigned long long pledgedSrcSize) DEBUGLOG(4, "ZSTD_resetCStream: pledgedSrcSize = %u", (U32)pledgedSrcSize); if (pledgedSrcSize==0) pledgedSrcSize = ZSTD_CONTENTSIZE_UNKNOWN; params.fParams.contentSizeFlag = 1; - params.cParams = ZSTD_getCParamsFromCCtxParams(params, pledgedSrcSize, 0); - return ZSTD_resetCStream_internal(zcs, NULL, 0, ZSTD_dm_auto, zcs->cdict, params, pledgedSrcSize); + params.cParams = ZSTD_getCParamsFromCCtxParams(¶ms, pledgedSrcSize, 0); + return ZSTD_resetCStream_internal(zcs, NULL, 0, ZSTD_dct_auto, zcs->cdict, params, pledgedSrcSize); } /*! ZSTD_initCStream_internal() : @@ -2592,7 +2936,7 @@ size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs, } ZSTD_freeCDict(zcs->cdictLocal); zcs->cdictLocal = ZSTD_createCDict_advanced(dict, dictSize, - ZSTD_dlm_byCopy, ZSTD_dm_auto, + ZSTD_dlm_byCopy, ZSTD_dct_auto, params.cParams, zcs->customMem); zcs->cdict = zcs->cdictLocal; if (zcs->cdictLocal == NULL) return ERROR(memory_allocation); @@ -2605,10 +2949,7 @@ size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs, zcs->cdict = cdict; } - params.compressionLevel = ZSTD_CLEVEL_CUSTOM; /* enforce usage of cParams, instead of a dynamic derivation from cLevel (but does that happen ?) */ - zcs->requestedParams = params; - - return ZSTD_resetCStream_internal(zcs, NULL, 0, ZSTD_dm_auto, zcs->cdict, params, pledgedSrcSize); + return ZSTD_resetCStream_internal(zcs, NULL, 0, ZSTD_dct_auto, zcs->cdict, params, pledgedSrcSize); } /* ZSTD_initCStream_usingCDict_advanced() : @@ -2637,20 +2978,22 @@ size_t ZSTD_initCStream_usingCDict(ZSTD_CStream* zcs, const ZSTD_CDict* cdict) return ZSTD_initCStream_usingCDict_advanced(zcs, cdict, fParams, ZSTD_CONTENTSIZE_UNKNOWN); /* note : will check that cdict != NULL */ } + /* ZSTD_initCStream_advanced() : - * pledgedSrcSize must be correct. + * pledgedSrcSize must be exact. * if srcSize is not known at init time, use value ZSTD_CONTENTSIZE_UNKNOWN. * dict is loaded with default parameters ZSTD_dm_auto and ZSTD_dlm_byCopy. */ size_t ZSTD_initCStream_advanced(ZSTD_CStream* zcs, const void* dict, size_t dictSize, ZSTD_parameters params, unsigned long long pledgedSrcSize) { - ZSTD_CCtx_params const cctxParams = ZSTD_assignParamsToCCtxParams(zcs->requestedParams, params); DEBUGLOG(4, "ZSTD_initCStream_advanced: pledgedSrcSize=%u, flag=%u", (U32)pledgedSrcSize, params.fParams.contentSizeFlag); CHECK_F( ZSTD_checkCParams(params.cParams) ); if ((pledgedSrcSize==0) && (params.fParams.contentSizeFlag==0)) pledgedSrcSize = ZSTD_CONTENTSIZE_UNKNOWN; /* for compatibility with older programs relying on this behavior. Users should now specify ZSTD_CONTENTSIZE_UNKNOWN. This line will be removed in the future. */ - return ZSTD_initCStream_internal(zcs, dict, dictSize, NULL /*cdict*/, cctxParams, pledgedSrcSize); + { ZSTD_CCtx_params const cctxParams = ZSTD_assignParamsToCCtxParams(zcs->requestedParams, params); + return ZSTD_initCStream_internal(zcs, dict, dictSize, NULL /*cdict*/, cctxParams, pledgedSrcSize); + } } size_t ZSTD_initCStream_usingDict(ZSTD_CStream* zcs, const void* dict, size_t dictSize, int compressionLevel) @@ -2687,7 +3030,7 @@ MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, /** ZSTD_compressStream_generic(): * internal function for all *compressStream*() variants and *compress_generic() - * non-static, because can be called from zstdmt.c + * non-static, because can be called from zstdmt_compress.c * @return : hint size for next input */ size_t ZSTD_compressStream_generic(ZSTD_CStream* zcs, ZSTD_outBuffer* output, @@ -2862,46 +3205,56 @@ size_t ZSTD_compress_generic (ZSTD_CCtx* cctx, DEBUGLOG(4, "ZSTD_compress_generic : transparent init stage"); if (endOp == ZSTD_e_end) cctx->pledgedSrcSizePlusOne = input->size + 1; /* auto-fix pledgedSrcSize */ params.cParams = ZSTD_getCParamsFromCCtxParams( - cctx->requestedParams, cctx->pledgedSrcSizePlusOne-1, 0 /*dictSize*/); + &cctx->requestedParams, cctx->pledgedSrcSizePlusOne-1, 0 /*dictSize*/); #ifdef ZSTD_MULTITHREAD - if ((cctx->pledgedSrcSizePlusOne-1) <= ZSTDMT_JOBSIZE_MIN) - params.nbThreads = 1; /* do not invoke multi-threading when src size is too small */ - if (params.nbThreads > 1) { - if (cctx->mtctx == NULL || (params.nbThreads != ZSTDMT_getNbThreads(cctx->mtctx))) { - DEBUGLOG(4, "ZSTD_compress_generic: creating new mtctx for nbThreads=%u (previous: %u)", - params.nbThreads, ZSTDMT_getNbThreads(cctx->mtctx)); + if ((cctx->pledgedSrcSizePlusOne-1) <= ZSTDMT_JOBSIZE_MIN) { + params.nbWorkers = 0; /* do not invoke multi-threading when src size is too small */ + } + if (params.nbWorkers > 0) { + /* mt context creation */ + if (cctx->mtctx == NULL || (params.nbWorkers != ZSTDMT_getNbWorkers(cctx->mtctx))) { + DEBUGLOG(4, "ZSTD_compress_generic: creating new mtctx for nbWorkers=%u", + params.nbWorkers); + if (cctx->mtctx != NULL) + DEBUGLOG(4, "ZSTD_compress_generic: previous nbWorkers was %u", + ZSTDMT_getNbWorkers(cctx->mtctx)); ZSTDMT_freeCCtx(cctx->mtctx); - cctx->mtctx = ZSTDMT_createCCtx_advanced(params.nbThreads, cctx->customMem); + cctx->mtctx = ZSTDMT_createCCtx_advanced(params.nbWorkers, cctx->customMem); if (cctx->mtctx == NULL) return ERROR(memory_allocation); } - DEBUGLOG(4, "call ZSTDMT_initCStream_internal as nbThreads=%u", params.nbThreads); + /* mt compression */ + DEBUGLOG(4, "call ZSTDMT_initCStream_internal as nbWorkers=%u", params.nbWorkers); CHECK_F( ZSTDMT_initCStream_internal( cctx->mtctx, - prefixDict.dict, prefixDict.dictSize, ZSTD_dm_rawContent, + prefixDict.dict, prefixDict.dictSize, ZSTD_dct_rawContent, cctx->cdict, params, cctx->pledgedSrcSizePlusOne-1) ); cctx->streamStage = zcss_load; - cctx->appliedParams.nbThreads = params.nbThreads; + cctx->appliedParams.nbWorkers = params.nbWorkers; } else #endif - { CHECK_F( ZSTD_resetCStream_internal( - cctx, prefixDict.dict, prefixDict.dictSize, - prefixDict.dictMode, cctx->cdict, params, - cctx->pledgedSrcSizePlusOne-1) ); + { CHECK_F( ZSTD_resetCStream_internal(cctx, + prefixDict.dict, prefixDict.dictSize, prefixDict.dictContentType, + cctx->cdict, + params, cctx->pledgedSrcSizePlusOne-1) ); assert(cctx->streamStage == zcss_load); - assert(cctx->appliedParams.nbThreads <= 1); + assert(cctx->appliedParams.nbWorkers == 0); } } /* compression stage */ #ifdef ZSTD_MULTITHREAD - if (cctx->appliedParams.nbThreads > 1) { - size_t const flushMin = ZSTDMT_compressStream_generic(cctx->mtctx, output, input, endOp); - if ( ZSTD_isError(flushMin) - || (endOp == ZSTD_e_end && flushMin == 0) ) { /* compression completed */ - ZSTD_startNewCompression(cctx); + if (cctx->appliedParams.nbWorkers > 0) { + if (cctx->cParamsChanged) { + ZSTDMT_updateCParams_whileCompressing(cctx->mtctx, &cctx->requestedParams); + cctx->cParamsChanged = 0; } - return flushMin; - } + { size_t const flushMin = ZSTDMT_compressStream_generic(cctx->mtctx, output, input, endOp); + if ( ZSTD_isError(flushMin) + || (endOp == ZSTD_e_end && flushMin == 0) ) { /* compression completed */ + ZSTD_startNewCompression(cctx); + } + return flushMin; + } } #endif CHECK_F( ZSTD_compressStream_generic(cctx, output, input, endOp) ); DEBUGLOG(5, "completed ZSTD_compress_generic"); @@ -2927,7 +3280,7 @@ size_t ZSTD_compress_generic_simpleArgs ( /*====== Finalize ======*/ /*! ZSTD_flushStream() : -* @return : amount of data remaining to flush */ + * @return : amount of data remaining to flush */ size_t ZSTD_flushStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output) { ZSTD_inBuffer input = { NULL, 0, 0 }; @@ -2959,11 +3312,11 @@ int ZSTD_maxCLevel(void) { return ZSTD_MAX_CLEVEL; } static const ZSTD_compressionParameters ZSTD_defaultCParameters[4][ZSTD_MAX_CLEVEL+1] = { { /* "default" - guarantees a monotonically increasing memory budget */ /* W, C, H, S, L, TL, strat */ - { 18, 12, 12, 1, 7, 16, ZSTD_fast }, /* level 0 - never used */ - { 19, 13, 14, 1, 7, 16, ZSTD_fast }, /* level 1 */ - { 19, 15, 16, 1, 6, 16, ZSTD_fast }, /* level 2 */ - { 20, 16, 17, 1, 5, 16, ZSTD_dfast }, /* level 3 */ - { 20, 17, 18, 1, 5, 16, ZSTD_dfast }, /* level 4 */ + { 19, 12, 13, 1, 6, 1, ZSTD_fast }, /* base for negative levels */ + { 19, 13, 14, 1, 7, 1, ZSTD_fast }, /* level 1 */ + { 19, 15, 16, 1, 6, 1, ZSTD_fast }, /* level 2 */ + { 20, 16, 17, 1, 5, 8, ZSTD_dfast }, /* level 3 */ + { 20, 17, 18, 1, 5, 8, ZSTD_dfast }, /* level 4 */ { 20, 17, 18, 2, 5, 16, ZSTD_greedy }, /* level 5 */ { 21, 17, 19, 2, 5, 16, ZSTD_lazy }, /* level 6 */ { 21, 18, 19, 3, 5, 16, ZSTD_lazy }, /* level 7 */ @@ -2972,9 +3325,9 @@ static const ZSTD_compressionParameters ZSTD_defaultCParameters[4][ZSTD_MAX_CLEV { 21, 19, 21, 4, 5, 16, ZSTD_lazy2 }, /* level 10 */ { 22, 20, 22, 4, 5, 16, ZSTD_lazy2 }, /* level 11 */ { 22, 20, 22, 5, 5, 16, ZSTD_lazy2 }, /* level 12 */ - { 22, 21, 22, 5, 5, 16, ZSTD_lazy2 }, /* level 13 */ - { 22, 21, 22, 6, 5, 16, ZSTD_lazy2 }, /* level 14 */ - { 22, 21, 22, 4, 5, 16, ZSTD_btlazy2 }, /* level 15 */ + { 22, 21, 22, 4, 5, 32, ZSTD_btlazy2 }, /* level 13 */ + { 22, 21, 22, 5, 5, 32, ZSTD_btlazy2 }, /* level 14 */ + { 22, 22, 22, 6, 5, 32, ZSTD_btlazy2 }, /* level 15 */ { 22, 21, 22, 4, 5, 48, ZSTD_btopt }, /* level 16 */ { 23, 22, 22, 4, 4, 48, ZSTD_btopt }, /* level 17 */ { 23, 22, 22, 5, 3, 64, ZSTD_btopt }, /* level 18 */ @@ -2985,8 +3338,8 @@ static const ZSTD_compressionParameters ZSTD_defaultCParameters[4][ZSTD_MAX_CLEV }, { /* for srcSize <= 256 KB */ /* W, C, H, S, L, T, strat */ - { 0, 0, 0, 0, 0, 0, ZSTD_fast }, /* level 0 - not used */ - { 18, 13, 14, 1, 6, 8, ZSTD_fast }, /* level 1 */ + { 18, 12, 13, 1, 5, 1, ZSTD_fast }, /* base for negative levels */ + { 18, 13, 14, 1, 6, 1, ZSTD_fast }, /* level 1 */ { 18, 14, 13, 1, 5, 8, ZSTD_dfast }, /* level 2 */ { 18, 16, 15, 1, 5, 8, ZSTD_dfast }, /* level 3 */ { 18, 15, 17, 1, 5, 8, ZSTD_greedy }, /* level 4.*/ @@ -2997,8 +3350,8 @@ static const ZSTD_compressionParameters ZSTD_defaultCParameters[4][ZSTD_MAX_CLEV { 18, 17, 17, 5, 4, 8, ZSTD_lazy2 }, /* level 9 */ { 18, 17, 17, 6, 4, 8, ZSTD_lazy2 }, /* level 10 */ { 18, 18, 17, 6, 4, 8, ZSTD_lazy2 }, /* level 11.*/ - { 18, 18, 17, 7, 4, 8, ZSTD_lazy2 }, /* level 12.*/ - { 18, 19, 17, 6, 4, 8, ZSTD_btlazy2 }, /* level 13 */ + { 18, 18, 17, 5, 4, 8, ZSTD_btlazy2 }, /* level 12.*/ + { 18, 19, 17, 7, 4, 8, ZSTD_btlazy2 }, /* level 13 */ { 18, 18, 18, 4, 4, 16, ZSTD_btopt }, /* level 14.*/ { 18, 18, 18, 4, 3, 16, ZSTD_btopt }, /* level 15.*/ { 18, 19, 18, 6, 3, 32, ZSTD_btopt }, /* level 16.*/ @@ -3011,9 +3364,9 @@ static const ZSTD_compressionParameters ZSTD_defaultCParameters[4][ZSTD_MAX_CLEV }, { /* for srcSize <= 128 KB */ /* W, C, H, S, L, T, strat */ - { 17, 12, 12, 1, 7, 8, ZSTD_fast }, /* level 0 - not used */ - { 17, 12, 13, 1, 6, 8, ZSTD_fast }, /* level 1 */ - { 17, 13, 16, 1, 5, 8, ZSTD_fast }, /* level 2 */ + { 17, 12, 12, 1, 5, 1, ZSTD_fast }, /* level 0 - not used */ + { 17, 12, 13, 1, 6, 1, ZSTD_fast }, /* level 1 */ + { 17, 13, 16, 1, 5, 1, ZSTD_fast }, /* level 2 */ { 17, 16, 16, 2, 5, 8, ZSTD_dfast }, /* level 3 */ { 17, 13, 15, 3, 4, 8, ZSTD_greedy }, /* level 4 */ { 17, 15, 17, 4, 4, 8, ZSTD_greedy }, /* level 5 */ @@ -3037,9 +3390,9 @@ static const ZSTD_compressionParameters ZSTD_defaultCParameters[4][ZSTD_MAX_CLEV }, { /* for srcSize <= 16 KB */ /* W, C, H, S, L, T, strat */ - { 14, 12, 12, 1, 7, 6, ZSTD_fast }, /* level 0 - not used */ - { 14, 14, 14, 1, 6, 6, ZSTD_fast }, /* level 1 */ - { 14, 14, 14, 1, 4, 6, ZSTD_fast }, /* level 2 */ + { 14, 12, 13, 1, 5, 1, ZSTD_fast }, /* base for negative levels */ + { 14, 14, 14, 1, 6, 1, ZSTD_fast }, /* level 1 */ + { 14, 14, 14, 1, 4, 1, ZSTD_fast }, /* level 2 */ { 14, 14, 14, 1, 4, 6, ZSTD_dfast }, /* level 3.*/ { 14, 14, 14, 4, 4, 6, ZSTD_greedy }, /* level 4.*/ { 14, 14, 14, 3, 4, 6, ZSTD_lazy }, /* level 5.*/ @@ -3063,47 +3416,22 @@ static const ZSTD_compressionParameters ZSTD_defaultCParameters[4][ZSTD_MAX_CLEV }, }; -#if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=1) -/* This function just controls - * the monotonic memory budget increase of ZSTD_defaultCParameters[0]. - * Run once, on first ZSTD_getCParams() usage, if ZSTD_DEBUG is enabled - */ -MEM_STATIC void ZSTD_check_compressionLevel_monotonicIncrease_memoryBudget(void) -{ - int level; - for (level=1; level<ZSTD_maxCLevel(); level++) { - ZSTD_compressionParameters const c1 = ZSTD_defaultCParameters[0][level]; - ZSTD_compressionParameters const c2 = ZSTD_defaultCParameters[0][level+1]; - assert(c1.windowLog <= c2.windowLog); -# define ZSTD_TABLECOST(h,c) ((1<<(h)) + (1<<(c))) - assert(ZSTD_TABLECOST(c1.hashLog, c1.chainLog) <= ZSTD_TABLECOST(c2.hashLog, c2.chainLog)); - } -} -#endif - /*! ZSTD_getCParams() : -* @return ZSTD_compressionParameters structure for a selected compression level, `srcSize` and `dictSize`. +* @return ZSTD_compressionParameters structure for a selected compression level, srcSize and dictSize. * Size values are optional, provide 0 if not known or unused */ ZSTD_compressionParameters ZSTD_getCParams(int compressionLevel, unsigned long long srcSizeHint, size_t dictSize) { size_t const addedSize = srcSizeHint ? 0 : 500; U64 const rSize = srcSizeHint+dictSize ? srcSizeHint+dictSize+addedSize : (U64)-1; U32 const tableID = (rSize <= 256 KB) + (rSize <= 128 KB) + (rSize <= 16 KB); /* intentional underflow for srcSizeHint == 0 */ - -#if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=1) - static int g_monotonicTest = 1; - if (g_monotonicTest) { - ZSTD_check_compressionLevel_monotonicIncrease_memoryBudget(); - g_monotonicTest=0; - } -#endif - - DEBUGLOG(4, "ZSTD_getCParams: cLevel=%i, srcSize=%u, dictSize=%u => table %u", - compressionLevel, (U32)srcSizeHint, (U32)dictSize, tableID); - if (compressionLevel <= 0) compressionLevel = ZSTD_CLEVEL_DEFAULT; /* 0 == default; no negative compressionLevel yet */ - if (compressionLevel > ZSTD_MAX_CLEVEL) compressionLevel = ZSTD_MAX_CLEVEL; - { ZSTD_compressionParameters const cp = ZSTD_defaultCParameters[tableID][compressionLevel]; - return ZSTD_adjustCParams_internal(cp, srcSizeHint, dictSize); } + int row = compressionLevel; + DEBUGLOG(5, "ZSTD_getCParams (cLevel=%i)", compressionLevel); + if (compressionLevel == 0) row = ZSTD_CLEVEL_DEFAULT; /* 0 == default */ + if (compressionLevel < 0) row = 0; /* entry 0 is baseline for fast mode */ + if (compressionLevel > ZSTD_MAX_CLEVEL) row = ZSTD_MAX_CLEVEL; + { ZSTD_compressionParameters cp = ZSTD_defaultCParameters[tableID][row]; + if (compressionLevel < 0) cp.targetLength = (unsigned)(-compressionLevel); /* acceleration factor */ + return ZSTD_adjustCParams_internal(cp, srcSizeHint, dictSize); } } @@ -3113,6 +3441,7 @@ ZSTD_compressionParameters ZSTD_getCParams(int compressionLevel, unsigned long l ZSTD_parameters ZSTD_getParams(int compressionLevel, unsigned long long srcSizeHint, size_t dictSize) { ZSTD_parameters params; ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, srcSizeHint, dictSize); + DEBUGLOG(5, "ZSTD_getParams (cLevel=%i)", compressionLevel); memset(¶ms, 0, sizeof(params)); params.cParams = cParams; params.fParams.contentSizeFlag = 1; |