Welcome to mirror list, hosted at ThFree Co, Russian Federation.

github.com/wolfpld/tracy.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/zstd/dictBuilder/zdict.c
diff options
context:
space:
mode:
Diffstat (limited to 'zstd/dictBuilder/zdict.c')
-rw-r--r--zstd/dictBuilder/zdict.c127
1 files changed, 99 insertions, 28 deletions
diff --git a/zstd/dictBuilder/zdict.c b/zstd/dictBuilder/zdict.c
index 459cbe4d..8b8b381e 100644
--- a/zstd/dictBuilder/zdict.c
+++ b/zstd/dictBuilder/zdict.c
@@ -135,22 +135,32 @@ static unsigned ZDICT_NbCommonBytes (size_t val)
if (MEM_isLittleEndian()) {
if (MEM_64bits()) {
# if defined(_MSC_VER) && defined(_WIN64)
- unsigned long r = 0;
- _BitScanForward64( &r, (U64)val );
- return (unsigned)(r>>3);
+ if (val != 0) {
+ unsigned long r;
+ _BitScanForward64(&r, (U64)val);
+ return (unsigned)(r >> 3);
+ } else {
+ /* Should not reach this code path */
+ __assume(0);
+ }
# elif defined(__GNUC__) && (__GNUC__ >= 3)
- return (__builtin_ctzll((U64)val) >> 3);
+ return (unsigned)(__builtin_ctzll((U64)val) >> 3);
# else
static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 };
return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
# endif
} else { /* 32 bits */
# if defined(_MSC_VER)
- unsigned long r=0;
- _BitScanForward( &r, (U32)val );
- return (unsigned)(r>>3);
+ if (val != 0) {
+ unsigned long r;
+ _BitScanForward(&r, (U32)val);
+ return (unsigned)(r >> 3);
+ } else {
+ /* Should not reach this code path */
+ __assume(0);
+ }
# elif defined(__GNUC__) && (__GNUC__ >= 3)
- return (__builtin_ctz((U32)val) >> 3);
+ return (unsigned)(__builtin_ctz((U32)val) >> 3);
# else
static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };
return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
@@ -159,11 +169,16 @@ static unsigned ZDICT_NbCommonBytes (size_t val)
} else { /* Big Endian CPU */
if (MEM_64bits()) {
# if defined(_MSC_VER) && defined(_WIN64)
- unsigned long r = 0;
- _BitScanReverse64( &r, val );
- return (unsigned)(r>>3);
+ if (val != 0) {
+ unsigned long r;
+ _BitScanReverse64(&r, val);
+ return (unsigned)(r >> 3);
+ } else {
+ /* Should not reach this code path */
+ __assume(0);
+ }
# elif defined(__GNUC__) && (__GNUC__ >= 3)
- return (__builtin_clzll(val) >> 3);
+ return (unsigned)(__builtin_clzll(val) >> 3);
# else
unsigned r;
const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */
@@ -174,11 +189,16 @@ static unsigned ZDICT_NbCommonBytes (size_t val)
# endif
} else { /* 32 bits */
# if defined(_MSC_VER)
- unsigned long r = 0;
- _BitScanReverse( &r, (unsigned long)val );
- return (unsigned)(r>>3);
+ if (val != 0) {
+ unsigned long r;
+ _BitScanReverse(&r, (unsigned long)val);
+ return (unsigned)(r >> 3);
+ } else {
+ /* Should not reach this code path */
+ __assume(0);
+ }
# elif defined(__GNUC__) && (__GNUC__ >= 3)
- return (__builtin_clz((U32)val) >> 3);
+ return (unsigned)(__builtin_clz((U32)val) >> 3);
# else
unsigned r;
if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
@@ -235,7 +255,7 @@ static dictItem ZDICT_analyzePos(
U32 savings[LLIMIT] = {0};
const BYTE* b = (const BYTE*)buffer;
size_t maxLength = LLIMIT;
- size_t pos = suffix[start];
+ size_t pos = (size_t)suffix[start];
U32 end = start;
dictItem solution;
@@ -369,7 +389,7 @@ static dictItem ZDICT_analyzePos(
savings[i] = savings[i-1] + (lengthList[i] * (i-3));
DISPLAYLEVEL(4, "Selected dict at position %u, of length %u : saves %u (ratio: %.2f) \n",
- (unsigned)pos, (unsigned)maxLength, (unsigned)savings[maxLength], (double)savings[maxLength] / maxLength);
+ (unsigned)pos, (unsigned)maxLength, (unsigned)savings[maxLength], (double)savings[maxLength] / (double)maxLength);
solution.pos = (U32)pos;
solution.length = (U32)maxLength;
@@ -379,7 +399,7 @@ static dictItem ZDICT_analyzePos(
{ U32 id;
for (id=start; id<end; id++) {
U32 p, pEnd, length;
- U32 const testedPos = suffix[id];
+ U32 const testedPos = (U32)suffix[id];
if (testedPos == pos)
length = solution.length;
else {
@@ -442,7 +462,7 @@ static U32 ZDICT_tryMerge(dictItem* table, dictItem elt, U32 eltNbToSkip, const
if ((table[u].pos + table[u].length >= elt.pos) && (table[u].pos < elt.pos)) { /* overlap, existing < new */
/* append */
- int const addedLength = (int)eltEnd - (table[u].pos + table[u].length);
+ int const addedLength = (int)eltEnd - (int)(table[u].pos + table[u].length);
table[u].savings += elt.length / 8; /* rough approx bonus */
if (addedLength > 0) { /* otherwise, elt fully included into existing */
table[u].length += addedLength;
@@ -766,6 +786,13 @@ static size_t ZDICT_analyzeEntropy(void* dstBuffer, size_t maxDstSize,
pos += fileSizes[u];
}
+ if (notificationLevel >= 4) {
+ /* writeStats */
+ DISPLAYLEVEL(4, "Offset Code Frequencies : \n");
+ for (u=0; u<=offcodeMax; u++) {
+ DISPLAYLEVEL(4, "%2u :%7u \n", u, offcodeCount[u]);
+ } }
+
/* analyze, build stats, starting with literals */
{ size_t maxNbBits = HUF_buildCTable (hufTable, countLit, 255, huffLog);
if (HUF_isError(maxNbBits)) {
@@ -872,7 +899,7 @@ static size_t ZDICT_analyzeEntropy(void* dstBuffer, size_t maxDstSize,
MEM_writeLE32(dstPtr+8, bestRepOffset[2].offset);
#else
/* at this stage, we don't use the result of "most common first offset",
- as the impact of statistics is not properly evaluated */
+ * as the impact of statistics is not properly evaluated */
MEM_writeLE32(dstPtr+0, repStartValue[0]);
MEM_writeLE32(dstPtr+4, repStartValue[1]);
MEM_writeLE32(dstPtr+8, repStartValue[2]);
@@ -888,6 +915,17 @@ _cleanup:
}
+/**
+ * @returns the maximum repcode value
+ */
+static U32 ZDICT_maxRep(U32 const reps[ZSTD_REP_NUM])
+{
+ U32 maxRep = reps[0];
+ int r;
+ for (r = 1; r < ZSTD_REP_NUM; ++r)
+ maxRep = MAX(maxRep, reps[r]);
+ return maxRep;
+}
size_t ZDICT_finalizeDictionary(void* dictBuffer, size_t dictBufferCapacity,
const void* customDictContent, size_t dictContentSize,
@@ -899,11 +937,13 @@ size_t ZDICT_finalizeDictionary(void* dictBuffer, size_t dictBufferCapacity,
BYTE header[HBUFFSIZE];
int const compressionLevel = (params.compressionLevel == 0) ? ZSTD_CLEVEL_DEFAULT : params.compressionLevel;
U32 const notificationLevel = params.notificationLevel;
+ /* The final dictionary content must be at least as large as the largest repcode */
+ size_t const minContentSize = (size_t)ZDICT_maxRep(repStartValue);
+ size_t paddingSize;
/* check conditions */
DEBUGLOG(4, "ZDICT_finalizeDictionary");
if (dictBufferCapacity < dictContentSize) return ERROR(dstSize_tooSmall);
- if (dictContentSize < ZDICT_CONTENTSIZE_MIN) return ERROR(srcSize_wrong);
if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) return ERROR(dstSize_tooSmall);
/* dictionary header */
@@ -927,12 +967,43 @@ size_t ZDICT_finalizeDictionary(void* dictBuffer, size_t dictBufferCapacity,
hSize += eSize;
}
- /* copy elements in final buffer ; note : src and dst buffer can overlap */
- if (hSize + dictContentSize > dictBufferCapacity) dictContentSize = dictBufferCapacity - hSize;
- { size_t const dictSize = hSize + dictContentSize;
- char* dictEnd = (char*)dictBuffer + dictSize;
- memmove(dictEnd - dictContentSize, customDictContent, dictContentSize);
- memcpy(dictBuffer, header, hSize);
+ /* Shrink the content size if it doesn't fit in the buffer */
+ if (hSize + dictContentSize > dictBufferCapacity) {
+ dictContentSize = dictBufferCapacity - hSize;
+ }
+
+ /* Pad the dictionary content with zeros if it is too small */
+ if (dictContentSize < minContentSize) {
+ RETURN_ERROR_IF(hSize + minContentSize > dictBufferCapacity, dstSize_tooSmall,
+ "dictBufferCapacity too small to fit max repcode");
+ paddingSize = minContentSize - dictContentSize;
+ } else {
+ paddingSize = 0;
+ }
+
+ {
+ size_t const dictSize = hSize + paddingSize + dictContentSize;
+
+ /* The dictionary consists of the header, optional padding, and the content.
+ * The padding comes before the content because the "best" position in the
+ * dictionary is the last byte.
+ */
+ BYTE* const outDictHeader = (BYTE*)dictBuffer;
+ BYTE* const outDictPadding = outDictHeader + hSize;
+ BYTE* const outDictContent = outDictPadding + paddingSize;
+
+ assert(dictSize <= dictBufferCapacity);
+ assert(outDictContent + dictContentSize == (BYTE*)dictBuffer + dictSize);
+
+ /* First copy the customDictContent into its final location.
+ * `customDictContent` and `dictBuffer` may overlap, so we must
+ * do this before any other writes into the output buffer.
+ * Then copy the header & padding into the output buffer.
+ */
+ memmove(outDictContent, customDictContent, dictContentSize);
+ memcpy(outDictHeader, header, hSize);
+ memset(outDictPadding, 0, paddingSize);
+
return dictSize;
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-15 16:05:54 +0300