diff options
Diffstat (limited to 'lib/zstd/compress.c')
| -rw-r--r-- | lib/zstd/compress.c | 3485 |
1 files changed, 0 insertions, 3485 deletions
diff --git a/lib/zstd/compress.c b/lib/zstd/compress.c deleted file mode 100644 index b080264ed3ad..000000000000 --- a/lib/zstd/compress.c +++ /dev/null @@ -1,3485 +0,0 @@ -/** - * Copyright (c) 2016-present, Yann Collet, Facebook, Inc. - * All rights reserved. - * - * This source code is licensed under the BSD-style license found in the - * LICENSE file in the root directory of https://github.com/facebook/zstd. - * An additional grant of patent rights can be found in the PATENTS file in the - * same directory. - * - * This program is free software; you can redistribute it and/or modify it under - * the terms of the GNU General Public License version 2 as published by the - * Free Software Foundation. This program is dual-licensed; you may select - * either version 2 of the GNU General Public License ("GPL") or BSD license - * ("BSD"). - */ - -/*-************************************* -* Dependencies -***************************************/ -#include "fse.h" -#include "huf.h" -#include "mem.h" -#include "zstd_internal.h" /* includes zstd.h */ -#include <linux/kernel.h> -#include <linux/module.h> -#include <linux/string.h> /* memset */ - -/*-************************************* -* Constants -***************************************/ -static const U32 g_searchStrength = 8; /* control skip over incompressible data */ -#define HASH_READ_SIZE 8 -typedef enum { ZSTDcs_created = 0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e; - -/*-************************************* -* Helper functions -***************************************/ -size_t ZSTD_compressBound(size_t srcSize) { return FSE_compressBound(srcSize) + 12; } - -/*-************************************* -* Sequence storage -***************************************/ -static void ZSTD_resetSeqStore(seqStore_t *ssPtr) -{ - ssPtr->lit = ssPtr->litStart; - ssPtr->sequences = ssPtr->sequencesStart; - ssPtr->longLengthID = 0; -} - -/*-************************************* -* Context memory management -***************************************/ -struct ZSTD_CCtx_s { - const BYTE *nextSrc; /* next block here to continue on curr prefix */ - const BYTE *base; /* All regular indexes relative to this position */ - const BYTE *dictBase; /* extDict indexes relative to this position */ - U32 dictLimit; /* below that point, need extDict */ - U32 lowLimit; /* below that point, no more data */ - U32 nextToUpdate; /* index from which to continue dictionary update */ - U32 nextToUpdate3; /* index from which to continue dictionary update */ - U32 hashLog3; /* dispatch table : larger == faster, more memory */ - U32 loadedDictEnd; /* index of end of dictionary */ - U32 forceWindow; /* force back-references to respect limit of 1<<wLog, even for dictionary */ - U32 forceRawDict; /* Force loading dictionary in "content-only" mode (no header analysis) */ - ZSTD_compressionStage_e stage; - U32 rep[ZSTD_REP_NUM]; - U32 repToConfirm[ZSTD_REP_NUM]; - U32 dictID; - ZSTD_parameters params; - void *workSpace; - size_t workSpaceSize; - size_t blockSize; - U64 frameContentSize; - struct xxh64_state xxhState; - ZSTD_customMem customMem; - - seqStore_t seqStore; /* sequences storage ptrs */ - U32 *hashTable; - U32 *hashTable3; - U32 *chainTable; - HUF_CElt *hufTable; - U32 flagStaticTables; - HUF_repeat flagStaticHufTable; - FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)]; - FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)]; - FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)]; - unsigned tmpCounters[HUF_COMPRESS_WORKSPACE_SIZE_U32]; -}; - -size_t ZSTD_CCtxWorkspaceBound(ZSTD_compressionParameters cParams) -{ - size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (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 : (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 tableSpace = (chainSize + hSize + h3Size) * sizeof(U32); - size_t const optSpace = - ((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 workspaceSize = tableSpace + (256 * sizeof(U32)) /* huffTable */ + tokenSpace + - (((cParams.strategy == ZSTD_btopt) || (cParams.strategy == ZSTD_btopt2)) ? optSpace : 0); - - return ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_CCtx)) + ZSTD_ALIGN(workspaceSize); -} - -static ZSTD_CCtx *ZSTD_createCCtx_advanced(ZSTD_customMem customMem) -{ - ZSTD_CCtx *cctx; - if (!customMem.customAlloc || !customMem.customFree) - return NULL; - cctx = (ZSTD_CCtx *)ZSTD_malloc(sizeof(ZSTD_CCtx), customMem); - if (!cctx) - return NULL; - memset(cctx, 0, sizeof(ZSTD_CCtx)); - cctx->customMem = customMem; - return cctx; -} - -ZSTD_CCtx *ZSTD_initCCtx(void *workspace, size_t workspaceSize) -{ - ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize); - ZSTD_CCtx *cctx = ZSTD_createCCtx_advanced(stackMem); - if (cctx) { - cctx->workSpace = ZSTD_stackAllocAll(cctx->customMem.opaque, &cctx->workSpaceSize); - } - return cctx; -} - -size_t ZSTD_freeCCtx(ZSTD_CCtx *cctx) -{ - if (cctx == NULL) - return 0; /* support free on NULL */ - ZSTD_free(cctx->workSpace, cctx->customMem); - ZSTD_free(cctx, cctx->customMem); - return 0; /* reserved as a potential error code in the future */ -} - -const seqStore_t *ZSTD_getSeqStore(const ZSTD_CCtx *ctx) /* hidden interface */ { return &(ctx->seqStore); } - -static ZSTD_parameters ZSTD_getParamsFromCCtx(const ZSTD_CCtx *cctx) { return cctx->params; } - -/** ZSTD_checkParams() : - ensure param values remain within authorized range. - @return : 0, or an error code if one value is beyond authorized range */ -size_t ZSTD_checkCParams(ZSTD_compressionParameters cParams) -{ -#define CLAMPCHECK(val, min, max) \ - { \ - if ((val < min) | (val > max)) \ - return ERROR(compressionParameter_unsupported); \ - } - CLAMPCHECK(cParams.windowLog, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX); - CLAMPCHECK(cParams.chainLog, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX); - 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.strategy) > (U32)ZSTD_btopt2) - return ERROR(compressionParameter_unsupported); - return 0; -} - -/** ZSTD_cycleLog() : - * condition for correct operation : hashLog > 1 */ -static U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat) -{ - U32 const btScale = ((U32)strat >= (U32)ZSTD_btlazy2); - return hashLog - btScale; -} - -/** ZSTD_adjustCParams() : - optimize `cPar` for a given input (`srcSize` and `dictSize`). - mostly downsizing to reduce memory consumption and initialization. - Both `srcSize` and `dictSize` are optional (use 0 if unknown), - but if both are 0, no optimization can be done. - Note : cPar is considered validated at this stage. Use ZSTD_checkParams() to ensure that. */ -ZSTD_compressionParameters ZSTD_adjustCParams(ZSTD_compressionParameters cPar, unsigned long long srcSize, size_t dictSize) -{ - if (srcSize + dictSize == 0) - return cPar; /* no size information available : no adjustment */ - - /* resize params, to use less memory when necessary */ - { - U32 const minSrcSize = (srcSize == 0) ? 500 : 0; - U64 const rSize = srcSize + dictSize + minSrcSize; - if (rSize < ((U64)1 << ZSTD_WINDOWLOG_MAX)) { - U32 const srcLog = MAX(ZSTD_HASHLOG_MIN, ZSTD_highbit32((U32)(rSize)-1) + 1); - if (cPar.windowLog > srcLog) - cPar.windowLog = srcLog; - } - } - if (cPar.hashLog > cPar.windowLog) - cPar.hashLog = cPar.windowLog; - { - U32 const cycleLog = ZSTD_cycleLog(cPar.chainLog, cPar.strategy); - if (cycleLog > cPar.windowLog) - cPar.chainLog -= (cycleLog - cPar.windowLog); - } - - if (cPar.windowLog < ZSTD_WINDOWLOG_ABSOLUTEMIN) - cPar.windowLog = ZSTD_WINDOWLOG_ABSOLUTEMIN; /* required for frame header */ - - return cPar; -} - -static U32 ZSTD_equivalentParams(ZSTD_parameters param1, ZSTD_parameters param2) -{ - return (param1.cParams.hashLog == param2.cParams.hashLog) & (param1.cParams.chainLog == param2.cParams.chainLog) & - (param1.cParams.strategy == param2.cParams.strategy) & ((param1.cParams.searchLength == 3) == (param2.cParams.searchLength == 3)); -} - -/*! ZSTD_continueCCtx() : - reuse CCtx without reset (note : requires no dictionary) */ -static size_t ZSTD_continueCCtx(ZSTD_CCtx *cctx, ZSTD_parameters params, U64 frameContentSize) -{ - U32 const end = (U32)(cctx->nextSrc - cctx->base); - cctx->params = params; - cctx->frameContentSize = frameContentSize; - 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->rep[i] = repStartValue[i]; - } - cctx->seqStore.litLengthSum = 0; /* force reset of btopt stats */ - xxh64_reset(&cctx->xxhState, 0); - return 0; -} - -typedef enum { ZSTDcrp_continue, ZSTDcrp_noMemset, ZSTDcrp_fullReset } ZSTD_compResetPolicy_e; - -/*! ZSTD_resetCCtx_advanced() : - note : `params` must be validated */ -static size_t ZSTD_resetCCtx_advanced(ZSTD_CCtx *zc, ZSTD_parameters params, U64 frameContentSize, ZSTD_compResetPolicy_e const crp) -{ - if (crp == ZSTDcrp_continue) - if (ZSTD_equivalentParams(params, zc->params)) { - zc->flagStaticTables = 0; - zc->flagStaticHufTable = HUF_repeat_none; - return ZSTD_continueCCtx(zc, params, frameContentSize); - } - - { - size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (size_t)1 << params.cParams.windowLog); - 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 : (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); - void *ptr; - - /* Check if workSpace is large enough, alloc a new one if needed */ - { - size_t const optSpace = ((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 neededSpace = tableSpace + (256 * sizeof(U32)) /* huffTable */ + tokenSpace + - (((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) ? optSpace : 0); - if (zc->workSpaceSize < neededSpace) { - ZSTD_free(zc->workSpace, zc->customMem); - zc->workSpace = ZSTD_malloc(neededSpace, zc->customMem); - if (zc->workSpace == NULL) - return ERROR(memory_allocation); - zc->workSpaceSize = neededSpace; - } - } - - if (crp != ZSTDcrp_noMemset) - memset(zc->workSpace, 0, tableSpace); /* reset tables only */ - xxh64_reset(&zc->xxhState, 0); - zc->hashLog3 = hashLog3; - zc->hashTable = (U32 *)(zc->workSpace); - zc->chainTable = zc->hashTable + hSize; - zc->hashTable3 = zc->chainTable + chainSize; - ptr = zc->hashTable3 + h3Size; - zc->hufTable = (HUF_CElt *)ptr; - zc->flagStaticTables = 0; - zc->flagStaticHufTable = HUF_repeat_none; - ptr = ((U32 *)ptr) + 256; /* note : HUF_CElt* is incomplete type, size is simulated using U32 */ - - zc->nextToUpdate = 1; - zc->nextSrc = NULL; - zc->base = NULL; - zc->dictBase = NULL; - zc->dictLimit = 0; - zc->lowLimit = 0; - zc->params = params; - zc->blockSize = blockSize; - zc->frameContentSize = frameContentSize; - { - int i; - for (i = 0; i < ZSTD_REP_NUM; i++) - zc->rep[i] = repStartValue[i]; - } - - if ((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) { - zc->seqStore.litFreq = (U32 *)ptr; - zc->seqStore.litLengthFreq = zc->seqStore.litFreq + (1 << Litbits); - zc->seqStore.matchLengthFreq = zc->seqStore.litLengthFreq + (MaxLL + 1); - zc->seqStore.offCodeFreq = zc->seqStore.matchLengthFreq + (MaxML + 1); - ptr = zc->seqStore.offCodeFreq + (MaxOff + 1); - zc->seqStore.matchTable = (ZSTD_match_t *)ptr; - ptr = zc->seqStore.matchTable + ZSTD_OPT_NUM + 1; - zc->seqStore.priceTable = (ZSTD_optimal_t *)ptr; - ptr = zc->seqStore.priceTable + ZSTD_OPT_NUM + 1; - zc->seqStore.litLengthSum = 0; - } - zc->seqStore.sequencesStart = (seqDef *)ptr; - ptr = zc->seqStore.sequencesStart + maxNbSeq; - zc->seqStore.llCode = (BYTE *)ptr; - zc->seqStore.mlCode = zc->seqStore.llCode + maxNbSeq; - zc->seqStore.ofCode = zc->seqStore.mlCode + maxNbSeq; - zc->seqStore.litStart = zc->seqStore.ofCode + maxNbSeq; - - zc->stage = ZSTDcs_init; - zc->dictID = 0; - zc->loadedDictEnd = 0; - - return 0; - } -} - -/* ZSTD_invalidateRepCodes() : - * ensures next compression will not use repcodes from previous block. - * Note : only works with regular variant; - * do not use with extDict variant ! */ -void ZSTD_invalidateRepCodes(ZSTD_CCtx *cctx) -{ - int i; - for (i = 0; i < ZSTD_REP_NUM; i++) - cctx->rep[i] = 0; -} - -/*! ZSTD_copyCCtx() : -* Duplicate an existing context `srcCCtx` into another one `dstCCtx`. -* Only works during stage ZSTDcs_init (i.e. after creation, but before first call to ZSTD_compressContinue()). -* @return : 0, or an error code */ -size_t ZSTD_copyCCtx(ZSTD_CCtx *dstCCtx, const ZSTD_CCtx *srcCCtx, unsigned long long pledgedSrcSize) -{ - if (srcCCtx->stage != ZSTDcs_init) - return ERROR(stage_wrong); - - memcpy(&dstCCtx->customMem, &srcCCtx->customMem, sizeof(ZSTD_customMem)); - { - ZSTD_parameters params = srcCCtx->params; - params.fParams.contentSizeFlag = (pledgedSrcSize > 0); - ZSTD_resetCCtx_advanced(dstCCtx, params, pledgedSrcSize, ZSTDcrp_noMemset); - } - - /* copy tables */ - { - size_t const chainSize = (srcCCtx->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << srcCCtx->params.cParams.chainLog); - size_t const hSize = ((size_t)1) << srcCCtx->params.cParams.hashLog; - size_t const h3Size = (size_t)1 << srcCCtx->hashLog3; - size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32); - memcpy(dstCCtx->workSpace, srcCCtx->workSpace, tableSpace); - } - - /* 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 */ - dstCCtx->flagStaticTables = srcCCtx->flagStaticTables; - dstCCtx->flagStaticHufTable = srcCCtx->flagStaticHufTable; - if (srcCCtx->flagStaticTables) { - memcpy(dstCCtx->litlengthCTable, srcCCtx->litlengthCTable, sizeof(dstCCtx->litlengthCTable)); - memcpy(dstCCtx->matchlengthCTable, srcCCtx->matchlengthCTable, sizeof(dstCCtx->matchlengthCTable)); - memcpy(dstCCtx->offcodeCTable, srcCCtx->offcodeCTable, sizeof(dstCCtx->offcodeCTable)); - } - if (srcCCtx->flagStaticHufTable) { - memcpy(dstCCtx->hufTable, srcCCtx->hufTable, 256 * 4); - } - - return 0; -} - -/*! ZSTD_reduceTable() : -* reduce table indexes by `reducerValue` */ -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_reduceIndex() : -* rescale all indexes to avoid future overflow (indexes are U32) */ -static void ZSTD_reduceIndex(ZSTD_CCtx *zc, const U32 reducerValue) -{ - { - U32 const hSize = 1 << zc->params.cParams.hashLog; - ZSTD_reduceTable(zc->hashTable, hSize, reducerValue); - } - - { - U32 const chainSize = (zc->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << zc->params.cParams.chainLog); - ZSTD_reduceTable(zc->chainTable, chainSize, reducerValue); - } - - { - U32 const h3Size = (zc->hashLog3) ? 1 << zc->hashLog3 : 0; - ZSTD_reduceTable(zc->hashTable3, h3Size, reducerValue); - } -} - -/*-******************************************************* -* Block entropic compression -*********************************************************/ - -/* See doc/zstd_compression_format.md for detailed format description */ - -size_t ZSTD_noCompressBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize) -{ - if (srcSize + ZSTD_blockHeaderSize > dstCapacity) - return ERROR(dstSize_tooSmall); - memcpy((BYTE *)dst + ZSTD_blockHeaderSize, src, srcSize); - ZSTD_writeLE24(dst, (U32)(srcSize << 2) + (U32)bt_raw); - return ZSTD_blockHeaderSize + srcSize; -} - -static size_t ZSTD_noCompressLiterals(void *dst, size_t dstCapacity, const void *src, size_t srcSize) -{ - BYTE *const ostart = (BYTE * const)dst; - U32 const flSize = 1 + (srcSize > 31) + (srcSize > 4095); - - if (srcSize + flSize > dstCapacity) - return ERROR(dstSize_tooSmall); - - switch (flSize) { - case 1: /* 2 - 1 - 5 */ ostart[0] = (BYTE)((U32)set_basic + (srcSize << 3)); break; - case 2: /* 2 - 2 - 12 */ ZSTD_writeLE16(ostart, (U16)((U32)set_basic + (1 << 2) + (srcSize << 4))); break; - default: /*note : should not be necessary : flSize is within {1,2,3} */ - case 3: /* 2 - 2 - 20 */ ZSTD_writeLE32(ostart, (U32)((U32)set_basic + (3 << 2) + (srcSize << 4))); break; - } - - memcpy(ostart + flSize, src, srcSize); - return srcSize + flSize; -} - -static size_t ZSTD_compressRleLiteralsBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize) -{ - BYTE *const ostart = (BYTE * const)dst; - U32 const flSize = 1 + (srcSize > 31) + (srcSize > 4095); - - (void)dstCapacity; /* dstCapacity already guaranteed to be >=4, hence large enough */ - - switch (flSize) { - case 1: /* 2 - 1 - 5 */ ostart[0] = (BYTE)((U32)set_rle + (srcSize << 3)); break; - case 2: /* 2 - 2 - 12 */ ZSTD_writeLE16(ostart, (U16)((U32)set_rle + (1 << 2) + (srcSize << 4))); break; - default: /*note : should not be necessary : flSize is necessarily within {1,2,3} */ - case 3: /* 2 - 2 - 20 */ ZSTD_writeLE32(ostart, (U32)((U32)set_rle + (3 << 2) + (srcSize << 4))); break; - } - - ostart[flSize] = *(const BYTE *)src; - return flSize + 1; -} - -static size_t ZSTD_minGain(size_t srcSize) { return (srcSize >> 6) + 2; } - -static size_t ZSTD_compressLiterals(ZSTD_CCtx *zc, void *dst, size_t dstCapacity, const void *src, size_t srcSize) -{ - size_t const minGain = ZSTD_minGain(srcSize); - size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB); - BYTE *const ostart = (BYTE *)dst; - U32 singleStream = srcSize < 256; - symbolEncodingType_e hType = set_compressed; - size_t cLitSize; - -/* small ? don't even attempt compression (speed opt) */ -#define LITERAL_NOENTROPY 63 - { - size_t const minLitSize = zc->flagStaticHufTable == HUF_repeat_valid ? 6 : LITERAL_NOENTROPY; - 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 = zc->flagStaticHufTable; - int const preferRepeat = zc->params.cParams.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, zc->tmpCounters, - sizeof(zc->tmpCounters), zc->hufTable, &repeat, preferRepeat) - : HUF_compress4X_repeat(ostart + lhSize, dstCapacity - lhSize, src, srcSize, 255, 11, zc->tmpCounters, - sizeof(zc->tmpCounters), zc->hufTable, &repeat, preferRepeat); - if (repeat != HUF_repeat_none) { - hType = set_repeat; - } /* reused the existing table */ - else { - zc->flagStaticHufTable = HUF_repeat_check; - } /* now have a table to reuse */ - } - - if ((cLitSize == 0) | (cLitSize >= srcSize - minGain)) { - zc->flagStaticHufTable = HUF_repeat_none; - return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize); - } - if (cLitSize == 1) { - zc->flagStaticHufTable = HUF_repeat_none; - return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize); - } - - /* Build header */ - switch (lhSize) { - case 3: /* 2 - 2 - 10 - 10 */ - { - U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize << 4) + ((U32)cLitSize << 14); - ZSTD_writeLE24(ostart, lhc); - break; - } - case 4: /* 2 - 2 - 14 - 14 */ - { - U32 const lhc = hType + (2 << 2) + ((U32)srcSize << 4) + ((U32)cLitSize << 18); - ZSTD_writeLE32(ostart, lhc); - break; - } - default: /* should not be necessary, lhSize is only {3,4,5} */ - case 5: /* 2 - 2 - 18 - 18 */ - { - U32 const lhc = hType + (3 << 2) + ((U32)srcSize << 4) + ((U32)cLitSize << 22); - ZSTD_writeLE32(ostart, lhc); - ostart[4] = (BYTE)(cLitSize >> 10); - break; - } - } - return lhSize + cLitSize; -} - -static const BYTE LL_Code[64] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 16, 17, 17, 18, 18, - 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, - 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24}; - -static const BYTE ML_Code[128] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, - 26, 27, 28, 29, 30, 31, 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, - 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, - 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 42, 42, 42, 42, 42, 42, 42, 42, - 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42}; - -void ZSTD_seqToCodes(const seqStore_t *seqStorePtr) -{ - BYTE const LL_deltaCode = 19; - BYTE const ML_deltaCode = 36; - const seqDef *const sequences = seqStorePtr->sequencesStart; - BYTE *const llCodeTable = seqStorePtr->llCode; - BYTE *const ofCodeTable = seqStorePtr->ofCode; - BYTE *const mlCodeTable = seqStorePtr->mlCode; - U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); - U32 u; - for (u = 0; u < nbSeq; u++) { - U32 const llv = sequences[u].litLength; - U32 const mlv = sequences[u].matchLength; - llCodeTable[u] = (llv > 63) ? (BYTE)ZSTD_highbit32(llv) + LL_deltaCode : LL_Code[llv]; - ofCodeTable[u] = (BYTE)ZSTD_highbit32(sequences[u].offset); - mlCodeTable[u] = (mlv > 127) ? (BYTE)ZSTD_highbit32(mlv) + ML_deltaCode : ML_Code[mlv]; - } - if (seqStorePtr->longLengthID == 1) - llCodeTable[seqStorePtr->longLengthPos] = MaxLL; - if (seqStorePtr->longLengthID == 2) - mlCodeTable[seqStorePtr->longLengthPos] = MaxML; -} - -ZSTD_STATIC size_t ZSTD_compressSequences_internal(ZSTD_CCtx *zc, void *dst, size_t dstCapacity) -{ - const int longOffsets = zc->params.cParams.windowLog > STREAM_ACCUMULATOR_MIN; - const seqStore_t *seqStorePtr = &(zc->seqStore); - FSE_CTable *CTable_LitLength = zc->litlengthCTable; - FSE_CTable *CTable_OffsetBits = zc->offcodeCTable; - FSE_CTable *CTable_MatchLength = zc->matchlengthCTable; - U32 LLtype, Offtype, MLtype; /* compressed, raw or rle */ - const seqDef *const sequences = seqStorePtr->sequencesStart; - const BYTE *const ofCodeTable = seqStorePtr->ofCode; - const BYTE *const llCodeTable = seqStorePtr->llCode; - const BYTE *const mlCodeTable = seqStorePtr->mlCode; - BYTE *const ostart = (BYTE *)dst; - BYTE *const oend = ostart + dstCapacity; - BYTE *op = ostart; - size_t const nbSeq = seqStorePtr->sequences - seqStorePtr->sequencesStart; - BYTE *seqHead; - - U32 *count; - S16 *norm; - U32 *workspace; - size_t workspaceSize = sizeof(zc->tmpCounters); - { - size_t spaceUsed32 = 0; - count = (U32 *)zc->tmpCounters + spaceUsed32; - spaceUsed32 += MaxSeq + 1; - norm = (S16 *)((U32 *)zc->tmpCounters + spaceUsed32); - spaceUsed32 += ALIGN(sizeof(S16) * (MaxSeq + 1), sizeof(U32)) >> 2; - - workspace = (U32 *)zc->tmpCounters + spaceUsed32; - workspaceSize -= (spaceUsed32 << 2); - } - - /* Compress literals */ - { - const BYTE *const literals = seqStorePtr->litStart; - size_t const litSize = seqStorePtr->lit - literals; - size_t const cSize = ZSTD_compressLiterals(zc, op, dstCapacity, literals, litSize); - if (ZSTD_isError(cSize)) - return cSize; - op += cSize; - } - - /* Sequences Header */ - if ((oend - op) < 3 /*max nbSeq Size*/ + 1 /*seqHead */) - return ERROR(dstSize_tooSmall); - if (nbSeq < 0x7F) - *op++ = (BYTE)nbSeq; - else if (nbSeq < LONGNBSEQ) - op[0] = (BYTE)((nbSeq >> 8) + 0x80), op[1] = (BYTE)nbSeq, op += 2; - else - op[0] = 0xFF, ZSTD_writeLE16(op + 1, (U16)(nbSeq - LONGNBSEQ)), op += 3; - if (nbSeq == 0) - return op - ostart; - - /* seqHead : flags for FSE encoding type */ - seqHead = op++; - -#define MIN_SEQ_FOR_DYNAMIC_FSE 64 -#define MAX_SEQ_FOR_STATIC_FSE 1000 - - /* convert length/distances into codes */ - ZSTD_seqToCodes(seqStorePtr); - - /* CTable for Literal Lengths */ - { - U32 max = MaxLL; - size_t const mostFrequent = FSE_countFast_wksp(count, &max, llCodeTable, nbSeq, workspace); - if ((mostFrequent == nbSeq) && (nbSeq > 2)) { - *op++ = llCodeTable[0]; - FSE_buildCTable_rle(CTable_LitLength, (BYTE)max); - LLtype = set_rle; - } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) { - LLtype = set_repeat; - } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (LL_defaultNormLog - 1)))) { - FSE_buildCTable_wksp(CTable_LitLength, LL_defaultNorm, MaxLL, LL_defaultNormLog, workspace, workspaceSize); - LLtype = set_basic; - } else { - size_t nbSeq_1 = nbSeq; - const U32 tableLog = FSE_optimalTableLog(LLFSELog, nbSeq, max); - if (count[llCodeTable[nbSeq - 1]] > 1) { - count[llCodeTable[nbSeq - 1]]--; - nbSeq_1--; - } - 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; - op += NCountSize; - } - FSE_buildCTable_wksp(CTable_LitLength, norm, max, tableLog, workspace, workspaceSize); - LLtype = set_compressed; - } - } - - /* CTable for Offsets */ - { - U32 max = MaxOff; - size_t const mostFrequent = FSE_countFast_wksp(count, &max, ofCodeTable, nbSeq, workspace); - if ((mostFrequent == nbSeq) && (nbSeq > 2)) { - *op++ = ofCodeTable[0]; - FSE_buildCTable_rle(CTable_OffsetBits, (BYTE)max); - Offtype = set_rle; - } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) { - Offtype = set_repeat; - } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (OF_defaultNormLog - 1)))) { - FSE_buildCTable_wksp(CTable_OffsetBits, OF_defaultNorm, MaxOff, OF_defaultNormLog, workspace, workspaceSize); - Offtype = set_basic; - } else { - size_t nbSeq_1 = nbSeq; - const U32 tableLog = FSE_optimalTableLog(OffFSELog, nbSeq, max); - if (count[ofCodeTable[nbSeq - 1]] > 1) { - count[ofCodeTable[nbSeq - 1]]--; - nbSeq_1--; - } - 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; - op += NCountSize; - } - FSE_buildCTable_wksp(CTable_OffsetBits, norm, max, tableLog, workspace, workspaceSize); - Offtype = set_compressed; - } - } - - /* CTable for MatchLengths */ - { - U32 max = MaxML; - size_t const mostFrequent = FSE_countFast_wksp(count, &max, mlCodeTable, nbSeq, workspace); - if ((mostFrequent == nbSeq) && (nbSeq > 2)) { - *op++ = *mlCodeTable; - FSE_buildCTable_rle(CTable_MatchLength, (BYTE)max); - MLtype = set_rle; - } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) { - MLtype = set_repeat; - } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (ML_defaultNormLog - 1)))) { - FSE_buildCTable_wksp(CTable_MatchLength, ML_defaultNorm, MaxML, ML_defaultNormLog, workspace, workspaceSize); - MLtype = set_basic; - } else { - size_t nbSeq_1 = nbSeq; - const U32 tableLog = FSE_optimalTableLog(MLFSELog, nbSeq, max); - if (count[mlCodeTable[nbSeq - 1]] > 1) { - count[mlCodeTable[nbSeq - 1]]--; - nbSeq_1--; - } - 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; - op += NCountSize; - } - FSE_buildCTable_wksp(CTable_MatchLength, norm, max, tableLog, workspace, workspaceSize); - MLtype = set_compressed; - } - } - - *seqHead = (BYTE)((LLtype << 6) + (Offtype << 4) + (MLtype << 2)); - zc->flagStaticTables = 0; - - /* Encoding Sequences */ - { - BIT_CStream_t blockStream; - FSE_CState_t stateMatchLength; - FSE_CState_t stateOffsetBits; - FSE_CState_t stateLitLength; - - CHECK_E(BIT_initCStream(&blockStream, op, oend - op), dstSize_tooSmall); /* not enough space remaining */ - - /* first symbols */ - FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq - 1]); - FSE_initCState2(&stateOffsetBits, CTable_OffsetBits, ofCodeTable[nbSeq - 1]); - FSE_initCState2(&stateLitLength, CTable_LitLength, llCodeTable[nbSeq - 1]); - BIT_addBits(&blockStream, sequences[nbSeq - 1].litLength, LL_bits[llCodeTable[nbSeq - 1]]); - if (ZSTD_32bits()) - BIT_flushBits(&blockStream); - BIT_addBits(&blockStream, sequences[nbSeq - 1].matchLength, ML_bits[mlCodeTable[nbSeq - 1]]); - if (ZSTD_32bits()) - BIT_flushBits(&blockStream); - if (longOffsets) { - U32 const ofBits = ofCodeTable[nbSeq - 1]; - int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN - 1); - if (extraBits) { - BIT_addBits(&blockStream, sequences[nbSeq - 1].offset, extraBits); - BIT_flushBits(&blockStream); - } - BIT_addBits(&blockStream, sequences[nbSeq - 1].offset >> extraBits, ofBits - extraBits); - } else { - BIT_addBits(&blockStream, sequences[nbSeq - 1].offset, ofCodeTable[nbSeq - 1]); - } - BIT_flushBits(&blockStream); - - { - size_t n; - for (n = nbSeq - 2; n < nbSeq; n--) { /* intentional underflow */ - BYTE const llCode = llCodeTable[n]; - BYTE const ofCode = ofCodeTable[n]; - BYTE const mlCode = mlCodeTable[n]; - U32 const llBits = LL_bits[llCode]; - U32 const ofBits = ofCode; /* 32b*/ /* 64b*/ - U32 const mlBits = ML_bits[mlCode]; - /* (7)*/ /* (7)*/ - FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode); /* 15 */ /* 15 */ - FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode); /* 24 */ /* 24 */ - if (ZSTD_32bits()) - BIT_flushBits(&blockStream); /* (7)*/ - FSE_encodeSymbol(&blockStream, &stateLitLength, llCode); /* 16 */ /* 33 */ - if (ZSTD_32bits() || (ofBits + mlBits + llBits >= 64 - 7 - (LLFSELog + MLFSELog + OffFSELog))) - BIT_flushBits(&blockStream); /* (7)*/ - BIT_addBits(&blockStream, sequences[n].litLength, llBits); - if (ZSTD_32bits() && ((llBits + mlBits) > 24)) - BIT_flushBits(&blockStream); - BIT_addBits(&blockStream, sequences[n].matchLength, mlBits); - if (ZSTD_32bits()) - BIT_flushBits(&blockStream); /* (7)*/ - if (longOffsets) { - int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN - 1); - if (extraBits) { - BIT_addBits(&blockStream, sequences[n].offset, extraBits); - BIT_flushBits(&blockStream); /* (7)*/ - } - BIT_addBits(&blockStream, sequences[n].offset >> extraBits, ofBits - extraBits); /* 31 */ - } else { - BIT_addBits(&blockStream, sequences[n].offset, ofBits); /* 31 */ - } - BIT_flushBits(&blockStream); /* (7)*/ - } - } - - FSE_flushCState(&blockStream, &stateMatchLength); - FSE_flushCState(&blockStream, &stateOffsetBits); - FSE_flushCState(&blockStream, &stateLitLength); - - { - size_t const streamSize = BIT_closeCStream(&blockStream); - if (streamSize == 0) - return ERROR(dstSize_tooSmall); /* not enough space */ - op += streamSize; - } - } - return op - ostart; -} - -ZSTD_STATIC size_t ZSTD_compressSequences(ZSTD_CCtx *zc, void *dst, size_t dstCapacity, size_t srcSize) -{ - size_t const cSize = ZSTD_compressSequences_internal(zc, dst, dstCapacity); - size_t const minGain = ZSTD_minGain(srcSize); - size_t const maxCSize = srcSize - minGain; - /* 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. - */ - int const uncompressibleError = cSize == ERROR(dstSize_tooSmall) && srcSize <= dstCapacity; - int i; - - if (ZSTD_isError(cSize) && !uncompressibleError) - return cSize; - if (cSize >= maxCSize || uncompressibleError) { - zc->flagStaticHufTable = HUF_repeat_none; - return 0; - } - /* confirm repcodes */ - for (i = 0; i < ZSTD_REP_NUM; i++) - zc->rep[i] = zc->repToConfirm[i]; - return cSize; -} - -/*! ZSTD_storeSeq() : - Store a sequence (literal length, literals, offset code and match length code) into seqStore_t. - `offsetCode` : distance to match, or 0 == repCode. - `matchCode` : matchLength - MINMATCH -*/ -ZSTD_STATIC void ZSTD_storeSeq(seqStore_t *seqStorePtr, size_t litLength, const void *literals, U32 offsetCode, size_t matchCode) -{ - /* copy Literals */ - ZSTD_wildcopy(seqStorePtr->lit, literals, litLength); - seqStorePtr->lit += litLength; - - /* literal Length */ - if (litLength > 0xFFFF) { - seqStorePtr->longLengthID = 1; - seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); - } - seqStorePtr->sequences[0].litLength = (U16)litLength; - - /* match offset */ - seqStorePtr->sequences[0].offset = offsetCode + 1; - - /* match Length */ - if (matchCode > 0xFFFF) { - seqStorePtr->longLengthID = 2; - seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); - } - seqStorePtr->sequences[0].matchLength = (U16)matchCode; - - seqStorePtr->sequences++; -} - -/*-************************************* -* Match length counter -***************************************/ -static unsigned ZSTD_NbCommonBytes(register size_t val) -{ - if (ZSTD_isLittleEndian()) { - if (ZSTD_64bits()) { - return (__builtin_ctzll((U64)val) >> 3); - } else { /* 32 bits */ - return (__builtin_ctz((U32)val) >> 3); - } - } else { /* Big Endian CPU */ - if (ZSTD_64bits()) { - return (__builtin_clzll(val) >> 3); - } else { /* 32 bits */ - return (__builtin_clz((U32)val) >> 3); - } - } -} - -static size_t ZSTD_count(const BYTE *pIn, const BYTE *pMatch, const BYTE *const pInLimit) -{ - const BYTE *const pStart = pIn; - const BYTE *const pInLoopLimit = pInLimit - (sizeof(size_t) - 1); - - while (pIn < pInLoopLimit) { - size_t const diff = ZSTD_readST(pMatch) ^ ZSTD_readST(pIn); - if (!diff) { - pIn += sizeof(size_t); - pMatch += sizeof(size_t); - continue; - } - pIn += ZSTD_NbCommonBytes(diff); - return (size_t)(pIn - pStart); - } - if (ZSTD_64bits()) - if ((pIn < (pInLimit - 3)) && (ZSTD_read32(pMatch) == ZSTD_read32(pIn))) { - pIn += 4; - pMatch += 4; - } - if ((pIn < (pInLimit - 1)) && (ZSTD_read16(pMatch) == ZSTD_read16(pIn))) { - pIn += 2; - pMatch += 2; - } - if ((pIn < pInLimit) && (*pMatch == *pIn)) - pIn++; - return (size_t)(pIn - pStart); -} - -/** ZSTD_count_2segments() : -* can count match length with `ip` & `match` in 2 different segments. -* convention : on reaching mEnd, match count continue starting from iStart -*/ -static size_t ZSTD_count_2segments(const BYTE *ip, const BYTE *match, const BYTE *iEnd, const BYTE *mEnd, const BYTE *iStart) -{ - const BYTE *const vEnd = MIN(ip + (mEnd - match), iEnd); - size_t const matchLength = ZSTD_count(ip, match, vEnd); - if (match + matchLength != mEnd) - return matchLength; - return matchLength + ZSTD_count(ip + matchLength, iStart, iEnd); -} - -/*-************************************* -* Hashes -***************************************/ |