From d051cd5b430e60e8ea8edc89ff1f73844378c3ff Mon Sep 17 00:00:00 2001 From: Nick Terrell Date: Thu, 2 Mar 2017 16:38:07 -0800 Subject: [PATCH] Use workspace for count and CTable --- lib/common/huf.h | 12 ++++++++---- lib/compress/huf_compress.c | 19 ++++++++++++++----- lib/compress/zstd_compress.c | 2 +- 3 files changed, 23 insertions(+), 10 deletions(-) diff --git a/lib/common/huf.h b/lib/common/huf.h index 89a226ea0..1315f1190 100644 --- a/lib/common/huf.h +++ b/lib/common/huf.h @@ -91,7 +91,7 @@ size_t HUF_compress2 (void* dst, size_t dstSize, const void* src, size_t srcSize /** HUF_compress4X_wksp() : * Same as HUF_compress2(), but uses externally allocated `workSpace`, which must be a table of >= 1024 unsigned */ -size_t HUF_compress4X_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); /**< `workSpace` must be a table of at least 1024 unsigned */ +size_t HUF_compress4X_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); /**< `workSpace` must be a table of at least HUF_WORKSPACE_SIZE_U32 unsigned */ @@ -133,6 +133,10 @@ typedef U32 HUF_DTable; #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \ HUF_DTable DTable[HUF_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog) * 0x01000001) } +/* The workspace must have alignment at least 4 and be at least this large */ +#define HUF_WORKSPACE_SIZE (6 << 10) +#define HUF_WORKSPACE_SIZE_U32 (HUF_WORKSPACE_SIZE / sizeof(U32)) + /* **************************************** * Advanced decompression functions @@ -177,7 +181,7 @@ typedef enum { * Same as HUF_compress4X_wksp(), but considers using hufTable if *repeat != HUF_repeat_none. * If it uses hufTable it does not modify hufTable or repeat. * If it doesn't, it sets *repeat = HUF_repeat_none, and it sets hufTable to the table used. */ -size_t HUF_compress4X_repeat(void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize, HUF_CElt* hufTable, HUF_repeat* repeat); /**< `workSpace` must be a table of at least 1024 unsigned */ +size_t HUF_compress4X_repeat(void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize, HUF_CElt* hufTable, HUF_repeat* repeat); /**< `workSpace` must be a table of at least HUF_WORKSPACE_SIZE_U32 unsigned */ /** HUF_buildCTable_wksp() : * Same as HUF_buildCTable(), but using externally allocated scratch buffer. @@ -224,13 +228,13 @@ size_t HUF_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* c /* single stream variants */ size_t HUF_compress1X (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog); -size_t HUF_compress1X_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); /**< `workSpace` must be a table of at least 1024 unsigned */ +size_t HUF_compress1X_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); /**< `workSpace` must be a table of at least HUF_WORKSPACE_SIZE_U32 unsigned */ size_t HUF_compress1X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable); /** HUF_compress1X_repeat() : * Same as HUF_compress1X_wksp(), but considers using hufTable if *repeat != HUF_repeat_none. * If it uses hufTable it does not modify hufTable or repeat. * If it doesn't, it sets *repeat = HUF_repeat_none, and it sets hufTable to the table used. */ -size_t HUF_compress1X_repeat(void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize, HUF_CElt* hufTable, HUF_repeat* repeat); /**< `workSpace` must be a table of at least 1024 unsigned */ +size_t HUF_compress1X_repeat(void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize, HUF_CElt* hufTable, HUF_repeat* repeat); /**< `workSpace` must be a table of at least HUF_WORKSPACE_SIZE_U32 unsigned */ size_t HUF_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ size_t HUF_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */ diff --git a/lib/compress/huf_compress.c b/lib/compress/huf_compress.c index 8b914cbc6..d103c3b22 100644 --- a/lib/compress/huf_compress.c +++ b/lib/compress/huf_compress.c @@ -558,11 +558,13 @@ static size_t HUF_compress_internal ( BYTE* const oend = ostart + dstSize; BYTE* op = ostart; - U32 count[HUF_SYMBOLVALUE_MAX+1]; - HUF_CElt CTable[HUF_SYMBOLVALUE_MAX+1]; + U32* count; + size_t const countSize = sizeof(U32) * (HUF_SYMBOLVALUE_MAX + 1); + HUF_CElt* CTable; + size_t const CTableSize = sizeof(HUF_CElt) * (HUF_SYMBOLVALUE_MAX + 1); /* checks & inits */ - if (wkspSize < sizeof(huffNodeTable)) return ERROR(GENERIC); + if (wkspSize < sizeof(huffNodeTable) + countSize + CTableSize) return ERROR(GENERIC); if (!srcSize) return 0; /* Uncompressed (note : 1 means rle, so first byte must be correct) */ if (!dstSize) return 0; /* cannot fit within dst budget */ if (srcSize > HUF_BLOCKSIZE_MAX) return ERROR(srcSize_wrong); /* current block size limit */ @@ -570,6 +572,13 @@ static size_t HUF_compress_internal ( if (!maxSymbolValue) maxSymbolValue = HUF_SYMBOLVALUE_MAX; if (!huffLog) huffLog = HUF_TABLELOG_DEFAULT; + count = (U32*)workSpace; + workSpace = (BYTE*)workSpace + countSize; + wkspSize -= countSize; + CTable = (HUF_CElt*)workSpace; + workSpace = (BYTE*)workSpace + CTableSize; + wkspSize -= CTableSize; + /* Heuristic : If we don't need to check the validity of the old table use the old table for small inputs */ if (srcSize <= 1024 && repeat && *repeat == HUF_repeat_valid) { return HUF_compressCTable_internal(ostart, op, oend, src, srcSize, singleStream, oldHufTable); @@ -595,7 +604,7 @@ static size_t HUF_compress_internal ( { CHECK_V_F(maxBits, HUF_buildCTable_wksp (CTable, count, maxSymbolValue, huffLog, workSpace, wkspSize) ); huffLog = (U32)maxBits; /* Zero the unused symbols so we can check it for validity */ - memset(CTable + maxSymbolValue + 1, 0, sizeof(CTable) - (maxSymbolValue + 1) * sizeof(HUF_CElt)); + memset(CTable + maxSymbolValue + 1, 0, CTableSize - (maxSymbolValue + 1) * sizeof(HUF_CElt)); } /* Write table description header */ @@ -612,7 +621,7 @@ static size_t HUF_compress_internal ( if (hSize + 12ul >= srcSize) { return 0; } op += hSize; if (repeat) { *repeat = HUF_repeat_none; } - if (oldHufTable) { memcpy(oldHufTable, CTable, sizeof(CTable)); } /* Save the new table */ + if (oldHufTable) { memcpy(oldHufTable, CTable, CTableSize); } /* Save the new table */ } return HUF_compressCTable_internal(ostart, op, oend, src, srcSize, singleStream, CTable); } diff --git a/lib/compress/zstd_compress.c b/lib/compress/zstd_compress.c index 538cb685c..a77d674b2 100644 --- a/lib/compress/zstd_compress.c +++ b/lib/compress/zstd_compress.c @@ -85,7 +85,7 @@ struct ZSTD_CCtx_s { 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[1024]; + unsigned tmpCounters[HUF_WORKSPACE_SIZE_U32]; }; ZSTD_CCtx* ZSTD_createCCtx(void) -- 2.47.2