aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/zstd/lib/dictBuilder/zdict.c
diff options
context:
space:
mode:
authorRuslan Kovalev <ruslan.a.kovalev@gmail.com>2022-02-10 16:46:45 +0300
committerDaniil Cherednik <dcherednik@yandex-team.ru>2022-02-10 16:46:45 +0300
commit9123176b341b6f2658cff5132482b8237c1416c8 (patch)
tree49e222ea1c5804306084bb3ae065bb702625360f /contrib/libs/zstd/lib/dictBuilder/zdict.c
parent59e19371de37995fcb36beb16cd6ec030af960bc (diff)
downloadydb-9123176b341b6f2658cff5132482b8237c1416c8.tar.gz
Restoring authorship annotation for Ruslan Kovalev <ruslan.a.kovalev@gmail.com>. Commit 2 of 2.
Diffstat (limited to 'contrib/libs/zstd/lib/dictBuilder/zdict.c')
-rw-r--r--contrib/libs/zstd/lib/dictBuilder/zdict.c1446
1 files changed, 723 insertions, 723 deletions
diff --git a/contrib/libs/zstd/lib/dictBuilder/zdict.c b/contrib/libs/zstd/lib/dictBuilder/zdict.c
index bbb23bf8b7..587df6b861 100644
--- a/contrib/libs/zstd/lib/dictBuilder/zdict.c
+++ b/contrib/libs/zstd/lib/dictBuilder/zdict.c
@@ -7,40 +7,40 @@
* in the COPYING file in the root directory of this source tree).
* You may select, at your option, one of the above-listed licenses.
*/
-
-
-/*-**************************************
-* Tuning parameters
-****************************************/
+
+
+/*-**************************************
+* Tuning parameters
+****************************************/
#define MINRATIO 4 /* minimum nb of apparition to be selected in dictionary */
-#define ZDICT_MAX_SAMPLES_SIZE (2000U << 20)
+#define ZDICT_MAX_SAMPLES_SIZE (2000U << 20)
#define ZDICT_MIN_SAMPLES_SIZE (ZDICT_CONTENTSIZE_MIN * MINRATIO)
-
-
-/*-**************************************
-* Compiler Options
-****************************************/
-/* Unix Large Files support (>4GB) */
-#define _FILE_OFFSET_BITS 64
-#if (defined(__sun__) && (!defined(__LP64__))) /* Sun Solaris 32-bits requires specific definitions */
+
+
+/*-**************************************
+* Compiler Options
+****************************************/
+/* Unix Large Files support (>4GB) */
+#define _FILE_OFFSET_BITS 64
+#if (defined(__sun__) && (!defined(__LP64__))) /* Sun Solaris 32-bits requires specific definitions */
# ifndef _LARGEFILE_SOURCE
-# define _LARGEFILE_SOURCE
+# define _LARGEFILE_SOURCE
# endif
-#elif ! defined(__LP64__) /* No point defining Large file for 64 bit */
+#elif ! defined(__LP64__) /* No point defining Large file for 64 bit */
# ifndef _LARGEFILE64_SOURCE
-# define _LARGEFILE64_SOURCE
+# define _LARGEFILE64_SOURCE
# endif
-#endif
-
-
-/*-*************************************
-* Dependencies
-***************************************/
-#include <stdlib.h> /* malloc, free */
-#include <string.h> /* memset */
-#include <stdio.h> /* fprintf, fopen, ftello64 */
-#include <time.h> /* clock */
-
+#endif
+
+
+/*-*************************************
+* Dependencies
+***************************************/
+#include <stdlib.h> /* malloc, free */
+#include <string.h> /* memset */
+#include <stdio.h> /* fprintf, fopen, ftello64 */
+#include <time.h> /* clock */
+
#ifndef ZDICT_STATIC_LINKING_ONLY
# define ZDICT_STATIC_LINKING_ONLY
#endif
@@ -53,59 +53,59 @@
#include <contrib/libs/xxhash/xxhash.h> /* XXH64 */
#include "../compress/zstd_compress_internal.h" /* ZSTD_loadCEntropy() */
#include "../zdict.h"
-#include "divsufsort.h"
-
-
-/*-*************************************
-* Constants
-***************************************/
-#define KB *(1 <<10)
-#define MB *(1 <<20)
-#define GB *(1U<<30)
-
+#include "divsufsort.h"
+
+
+/*-*************************************
+* Constants
+***************************************/
+#define KB *(1 <<10)
+#define MB *(1 <<20)
+#define GB *(1U<<30)
+
#define DICTLISTSIZE_DEFAULT 10000
-
-#define NOISELENGTH 32
-
-static const U32 g_selectivity_default = 9;
-
-
-/*-*************************************
-* Console display
-***************************************/
+
+#define NOISELENGTH 32
+
+static const U32 g_selectivity_default = 9;
+
+
+/*-*************************************
+* Console display
+***************************************/
#undef DISPLAY
-#define DISPLAY(...) { fprintf(stderr, __VA_ARGS__); fflush( stderr ); }
+#define DISPLAY(...) { fprintf(stderr, __VA_ARGS__); fflush( stderr ); }
#undef DISPLAYLEVEL
#define DISPLAYLEVEL(l, ...) if (notificationLevel>=l) { DISPLAY(__VA_ARGS__); } /* 0 : no display; 1: errors; 2: default; 3: details; 4: debug */
-
-static clock_t ZDICT_clockSpan(clock_t nPrevious) { return clock() - nPrevious; }
-
+
+static clock_t ZDICT_clockSpan(clock_t nPrevious) { return clock() - nPrevious; }
+
static void ZDICT_printHex(const void* ptr, size_t length)
-{
- const BYTE* const b = (const BYTE*)ptr;
- size_t u;
- for (u=0; u<length; u++) {
- BYTE c = b[u];
- if (c<32 || c>126) c = '.'; /* non-printable char */
+{
+ const BYTE* const b = (const BYTE*)ptr;
+ size_t u;
+ for (u=0; u<length; u++) {
+ BYTE c = b[u];
+ if (c<32 || c>126) c = '.'; /* non-printable char */
DISPLAY("%c", c);
- }
-}
-
-
-/*-********************************************************
-* Helper functions
-**********************************************************/
-unsigned ZDICT_isError(size_t errorCode) { return ERR_isError(errorCode); }
-
-const char* ZDICT_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
-
+ }
+}
+
+
+/*-********************************************************
+* Helper functions
+**********************************************************/
+unsigned ZDICT_isError(size_t errorCode) { return ERR_isError(errorCode); }
+
+const char* ZDICT_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
+
unsigned ZDICT_getDictID(const void* dictBuffer, size_t dictSize)
{
if (dictSize < 8) return 0;
if (MEM_readLE32(dictBuffer) != ZSTD_MAGIC_DICTIONARY) return 0;
return MEM_readLE32((const char*)dictBuffer + 4);
}
-
+
size_t ZDICT_getDictHeaderSize(const void* dictBuffer, size_t dictSize)
{
size_t headerSize;
@@ -127,14 +127,14 @@ size_t ZDICT_getDictHeaderSize(const void* dictBuffer, size_t dictSize)
return headerSize;
}
-/*-********************************************************
-* Dictionary training functions
-**********************************************************/
+/*-********************************************************
+* Dictionary training functions
+**********************************************************/
static unsigned ZDICT_NbCommonBytes (size_t val)
-{
- if (MEM_isLittleEndian()) {
- if (MEM_64bits()) {
-# if defined(_MSC_VER) && defined(_WIN64)
+{
+ if (MEM_isLittleEndian()) {
+ if (MEM_64bits()) {
+# if defined(_MSC_VER) && defined(_WIN64)
if (val != 0) {
unsigned long r;
_BitScanForward64(&r, (U64)val);
@@ -143,14 +143,14 @@ static unsigned ZDICT_NbCommonBytes (size_t val)
/* Should not reach this code path */
__assume(0);
}
-# elif defined(__GNUC__) && (__GNUC__ >= 3)
+# elif defined(__GNUC__) && (__GNUC__ >= 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)
+# 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)
if (val != 0) {
unsigned long r;
_BitScanForward(&r, (U32)val);
@@ -159,16 +159,16 @@ static unsigned ZDICT_NbCommonBytes (size_t val)
/* Should not reach this code path */
__assume(0);
}
-# elif defined(__GNUC__) && (__GNUC__ >= 3)
+# elif defined(__GNUC__) && (__GNUC__ >= 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];
-# endif
- }
- } else { /* Big Endian CPU */
- if (MEM_64bits()) {
-# if defined(_MSC_VER) && defined(_WIN64)
+# else
+ static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };
+ return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
+# endif
+ }
+ } else { /* Big Endian CPU */
+ if (MEM_64bits()) {
+# if defined(_MSC_VER) && defined(_WIN64)
if (val != 0) {
unsigned long r;
_BitScanReverse64(&r, val);
@@ -177,18 +177,18 @@ static unsigned ZDICT_NbCommonBytes (size_t val)
/* Should not reach this code path */
__assume(0);
}
-# elif defined(__GNUC__) && (__GNUC__ >= 3)
+# elif defined(__GNUC__) && (__GNUC__ >= 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 */
- if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
- if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
- r += (!val);
- return r;
-# endif
- } else { /* 32 bits */
-# if defined(_MSC_VER)
+# else
+ unsigned r;
+ const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */
+ if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
+ if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
+ r += (!val);
+ return r;
+# endif
+ } else { /* 32 bits */
+# if defined(_MSC_VER)
if (val != 0) {
unsigned long r;
_BitScanReverse(&r, (unsigned long)val);
@@ -197,156 +197,156 @@ static unsigned ZDICT_NbCommonBytes (size_t val)
/* Should not reach this code path */
__assume(0);
}
-# elif defined(__GNUC__) && (__GNUC__ >= 3)
+# elif defined(__GNUC__) && (__GNUC__ >= 3)
return (unsigned)(__builtin_clz((U32)val) >> 3);
-# else
- unsigned r;
- if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
- r += (!val);
- return r;
-# endif
- } }
-}
-
-
-/*! ZDICT_count() :
- Count the nb of common bytes between 2 pointers.
- Note : this function presumes end of buffer followed by noisy guard band.
-*/
-static size_t ZDICT_count(const void* pIn, const void* pMatch)
-{
- const char* const pStart = (const char*)pIn;
- for (;;) {
- size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
- if (!diff) {
- pIn = (const char*)pIn+sizeof(size_t);
- pMatch = (const char*)pMatch+sizeof(size_t);
- continue;
- }
- pIn = (const char*)pIn+ZDICT_NbCommonBytes(diff);
- return (size_t)((const char*)pIn - pStart);
- }
-}
-
-
-typedef struct {
- U32 pos;
- U32 length;
- U32 savings;
-} dictItem;
-
-static void ZDICT_initDictItem(dictItem* d)
-{
- d->pos = 1;
- d->length = 0;
- d->savings = (U32)(-1);
-}
-
-
-#define LLIMIT 64 /* heuristic determined experimentally */
-#define MINMATCHLENGTH 7 /* heuristic determined experimentally */
-static dictItem ZDICT_analyzePos(
- BYTE* doneMarks,
- const int* suffix, U32 start,
+# else
+ unsigned r;
+ if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
+ r += (!val);
+ return r;
+# endif
+ } }
+}
+
+
+/*! ZDICT_count() :
+ Count the nb of common bytes between 2 pointers.
+ Note : this function presumes end of buffer followed by noisy guard band.
+*/
+static size_t ZDICT_count(const void* pIn, const void* pMatch)
+{
+ const char* const pStart = (const char*)pIn;
+ for (;;) {
+ size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
+ if (!diff) {
+ pIn = (const char*)pIn+sizeof(size_t);
+ pMatch = (const char*)pMatch+sizeof(size_t);
+ continue;
+ }
+ pIn = (const char*)pIn+ZDICT_NbCommonBytes(diff);
+ return (size_t)((const char*)pIn - pStart);
+ }
+}
+
+
+typedef struct {
+ U32 pos;
+ U32 length;
+ U32 savings;
+} dictItem;
+
+static void ZDICT_initDictItem(dictItem* d)
+{
+ d->pos = 1;
+ d->length = 0;
+ d->savings = (U32)(-1);
+}
+
+
+#define LLIMIT 64 /* heuristic determined experimentally */
+#define MINMATCHLENGTH 7 /* heuristic determined experimentally */
+static dictItem ZDICT_analyzePos(
+ BYTE* doneMarks,
+ const int* suffix, U32 start,
const void* buffer, U32 minRatio, U32 notificationLevel)
-{
- U32 lengthList[LLIMIT] = {0};
- U32 cumulLength[LLIMIT] = {0};
- U32 savings[LLIMIT] = {0};
- const BYTE* b = (const BYTE*)buffer;
- size_t maxLength = LLIMIT;
+{
+ U32 lengthList[LLIMIT] = {0};
+ U32 cumulLength[LLIMIT] = {0};
+ U32 savings[LLIMIT] = {0};
+ const BYTE* b = (const BYTE*)buffer;
+ size_t maxLength = LLIMIT;
size_t pos = (size_t)suffix[start];
- U32 end = start;
- dictItem solution;
-
- /* init */
- memset(&solution, 0, sizeof(solution));
- doneMarks[pos] = 1;
-
- /* trivial repetition cases */
- if ( (MEM_read16(b+pos+0) == MEM_read16(b+pos+2))
- ||(MEM_read16(b+pos+1) == MEM_read16(b+pos+3))
- ||(MEM_read16(b+pos+2) == MEM_read16(b+pos+4)) ) {
- /* skip and mark segment */
+ U32 end = start;
+ dictItem solution;
+
+ /* init */
+ memset(&solution, 0, sizeof(solution));
+ doneMarks[pos] = 1;
+
+ /* trivial repetition cases */
+ if ( (MEM_read16(b+pos+0) == MEM_read16(b+pos+2))
+ ||(MEM_read16(b+pos+1) == MEM_read16(b+pos+3))
+ ||(MEM_read16(b+pos+2) == MEM_read16(b+pos+4)) ) {
+ /* skip and mark segment */
U16 const pattern16 = MEM_read16(b+pos+4);
U32 u, patternEnd = 6;
while (MEM_read16(b+pos+patternEnd) == pattern16) patternEnd+=2 ;
if (b[pos+patternEnd] == b[pos+patternEnd-1]) patternEnd++;
for (u=1; u<patternEnd; u++)
- doneMarks[pos+u] = 1;
- return solution;
- }
-
- /* look forward */
+ doneMarks[pos+u] = 1;
+ return solution;
+ }
+
+ /* look forward */
{ size_t length;
do {
end++;
length = ZDICT_count(b + pos, b + suffix[end]);
} while (length >= MINMATCHLENGTH);
}
-
- /* look backward */
+
+ /* look backward */
{ size_t length;
do {
length = ZDICT_count(b + pos, b + *(suffix+start-1));
if (length >=MINMATCHLENGTH) start--;
} while(length >= MINMATCHLENGTH);
}
-
- /* exit if not found a minimum nb of repetitions */
- if (end-start < minRatio) {
- U32 idx;
- for(idx=start; idx<end; idx++)
- doneMarks[suffix[idx]] = 1;
- return solution;
- }
-
- { int i;
+
+ /* exit if not found a minimum nb of repetitions */
+ if (end-start < minRatio) {
+ U32 idx;
+ for(idx=start; idx<end; idx++)
+ doneMarks[suffix[idx]] = 1;
+ return solution;
+ }
+
+ { int i;
U32 mml;
- U32 refinedStart = start;
- U32 refinedEnd = end;
-
- DISPLAYLEVEL(4, "\n");
+ U32 refinedStart = start;
+ U32 refinedEnd = end;
+
+ DISPLAYLEVEL(4, "\n");
DISPLAYLEVEL(4, "found %3u matches of length >= %i at pos %7u ", (unsigned)(end-start), MINMATCHLENGTH, (unsigned)pos);
- DISPLAYLEVEL(4, "\n");
-
+ DISPLAYLEVEL(4, "\n");
+
for (mml = MINMATCHLENGTH ; ; mml++) {
- BYTE currentChar = 0;
- U32 currentCount = 0;
- U32 currentID = refinedStart;
- U32 id;
- U32 selectedCount = 0;
- U32 selectedID = currentID;
- for (id =refinedStart; id < refinedEnd; id++) {
+ BYTE currentChar = 0;
+ U32 currentCount = 0;
+ U32 currentID = refinedStart;
+ U32 id;
+ U32 selectedCount = 0;
+ U32 selectedID = currentID;
+ for (id =refinedStart; id < refinedEnd; id++) {
if (b[suffix[id] + mml] != currentChar) {
- if (currentCount > selectedCount) {
- selectedCount = currentCount;
- selectedID = currentID;
- }
- currentID = id;
+ if (currentCount > selectedCount) {
+ selectedCount = currentCount;
+ selectedID = currentID;
+ }
+ currentID = id;
currentChar = b[ suffix[id] + mml];
- currentCount = 0;
- }
- currentCount ++;
- }
- if (currentCount > selectedCount) { /* for last */
- selectedCount = currentCount;
- selectedID = currentID;
- }
-
- if (selectedCount < minRatio)
- break;
- refinedStart = selectedID;
- refinedEnd = refinedStart + selectedCount;
- }
-
+ currentCount = 0;
+ }
+ currentCount ++;
+ }
+ if (currentCount > selectedCount) { /* for last */
+ selectedCount = currentCount;
+ selectedID = currentID;
+ }
+
+ if (selectedCount < minRatio)
+ break;
+ refinedStart = selectedID;
+ refinedEnd = refinedStart + selectedCount;
+ }
+
/* evaluate gain based on new dict */
- start = refinedStart;
- pos = suffix[refinedStart];
- end = start;
- memset(lengthList, 0, sizeof(lengthList));
-
- /* look forward */
+ start = refinedStart;
+ pos = suffix[refinedStart];
+ end = start;
+ memset(lengthList, 0, sizeof(lengthList));
+
+ /* look forward */
{ size_t length;
do {
end++;
@@ -355,8 +355,8 @@ static dictItem ZDICT_analyzePos(
lengthList[length]++;
} while (length >=MINMATCHLENGTH);
}
-
- /* look backward */
+
+ /* look backward */
{ size_t length = MINMATCHLENGTH;
while ((length >= MINMATCHLENGTH) & (start > 0)) {
length = ZDICT_count(b + pos, b + suffix[start - 1]);
@@ -365,56 +365,56 @@ static dictItem ZDICT_analyzePos(
if (length >= MINMATCHLENGTH) start--;
}
}
-
- /* largest useful length */
- memset(cumulLength, 0, sizeof(cumulLength));
- cumulLength[maxLength-1] = lengthList[maxLength-1];
- for (i=(int)(maxLength-2); i>=0; i--)
- cumulLength[i] = cumulLength[i+1] + lengthList[i];
-
- for (i=LLIMIT-1; i>=MINMATCHLENGTH; i--) if (cumulLength[i]>=minRatio) break;
- maxLength = i;
-
- /* reduce maxLength in case of final into repetitive data */
- { U32 l = (U32)maxLength;
- BYTE const c = b[pos + maxLength-1];
- while (b[pos+l-2]==c) l--;
- maxLength = l;
- }
- if (maxLength < MINMATCHLENGTH) return solution; /* skip : no long-enough solution */
-
- /* calculate savings */
- savings[5] = 0;
- for (i=MINMATCHLENGTH; i<=(int)maxLength; i++)
- savings[i] = savings[i-1] + (lengthList[i] * (i-3));
-
+
+ /* largest useful length */
+ memset(cumulLength, 0, sizeof(cumulLength));
+ cumulLength[maxLength-1] = lengthList[maxLength-1];
+ for (i=(int)(maxLength-2); i>=0; i--)
+ cumulLength[i] = cumulLength[i+1] + lengthList[i];
+
+ for (i=LLIMIT-1; i>=MINMATCHLENGTH; i--) if (cumulLength[i]>=minRatio) break;
+ maxLength = i;
+
+ /* reduce maxLength in case of final into repetitive data */
+ { U32 l = (U32)maxLength;
+ BYTE const c = b[pos + maxLength-1];
+ while (b[pos+l-2]==c) l--;
+ maxLength = l;
+ }
+ if (maxLength < MINMATCHLENGTH) return solution; /* skip : no long-enough solution */
+
+ /* calculate savings */
+ savings[5] = 0;
+ for (i=MINMATCHLENGTH; i<=(int)maxLength; i++)
+ 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] / (double)maxLength);
-
- solution.pos = (U32)pos;
- solution.length = (U32)maxLength;
- solution.savings = savings[maxLength];
-
- /* mark positions done */
- { U32 id;
- for (id=start; id<end; id++) {
+
+ solution.pos = (U32)pos;
+ solution.length = (U32)maxLength;
+ solution.savings = savings[maxLength];
+
+ /* mark positions done */
+ { U32 id;
+ for (id=start; id<end; id++) {
U32 p, pEnd, length;
U32 const testedPos = (U32)suffix[id];
- if (testedPos == pos)
- length = solution.length;
- else {
+ if (testedPos == pos)
+ length = solution.length;
+ else {
length = (U32)ZDICT_count(b+pos, b+testedPos);
- if (length > solution.length) length = solution.length;
- }
- pEnd = (U32)(testedPos + length);
- for (p=testedPos; p<pEnd; p++)
- doneMarks[p] = 1;
- } } }
-
- return solution;
-}
-
-
+ if (length > solution.length) length = solution.length;
+ }
+ pEnd = (U32)(testedPos + length);
+ for (p=testedPos; p<pEnd; p++)
+ doneMarks[p] = 1;
+ } } }
+
+ return solution;
+}
+
+
static int isIncluded(const void* in, const void* container, size_t length)
{
const char* const ip = (const char*) in;
@@ -429,53 +429,53 @@ static int isIncluded(const void* in, const void* container, size_t length)
}
/*! ZDICT_tryMerge() :
- check if dictItem can be merged, do it if possible
- @return : id of destination elt, 0 if not merged
-*/
+ check if dictItem can be merged, do it if possible
+ @return : id of destination elt, 0 if not merged
+*/
static U32 ZDICT_tryMerge(dictItem* table, dictItem elt, U32 eltNbToSkip, const void* buffer)
-{
- const U32 tableSize = table->pos;
+{
+ const U32 tableSize = table->pos;
const U32 eltEnd = elt.pos + elt.length;
const char* const buf = (const char*) buffer;
-
- /* tail overlap */
- U32 u; for (u=1; u<tableSize; u++) {
- if (u==eltNbToSkip) continue;
+
+ /* tail overlap */
+ U32 u; for (u=1; u<tableSize; u++) {
+ if (u==eltNbToSkip) continue;
if ((table[u].pos > elt.pos) && (table[u].pos <= eltEnd)) { /* overlap, existing > new */
- /* append */
+ /* append */
U32 const addedLength = table[u].pos - elt.pos;
- table[u].length += addedLength;
- table[u].pos = elt.pos;
- table[u].savings += elt.savings * addedLength / elt.length; /* rough approx */
+ table[u].length += addedLength;
+ table[u].pos = elt.pos;
+ table[u].savings += elt.savings * addedLength / elt.length; /* rough approx */
table[u].savings += elt.length / 8; /* rough approx bonus */
- elt = table[u];
+ elt = table[u];
/* sort : improve rank */
- while ((u>1) && (table[u-1].savings < elt.savings))
+ while ((u>1) && (table[u-1].savings < elt.savings))
table[u] = table[u-1], u--;
- table[u] = elt;
- return u;
- } }
-
- /* front overlap */
- for (u=1; u<tableSize; u++) {
- if (u==eltNbToSkip) continue;
+ table[u] = elt;
+ return u;
+ } }
+
+ /* front overlap */
+ for (u=1; u<tableSize; u++) {
+ if (u==eltNbToSkip) continue;
if ((table[u].pos + table[u].length >= elt.pos) && (table[u].pos < elt.pos)) { /* overlap, existing < new */
- /* append */
+ /* append */
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;
- table[u].savings += elt.savings * addedLength / elt.length; /* rough approx */
- }
+ table[u].length += addedLength;
+ table[u].savings += elt.savings * addedLength / elt.length; /* rough approx */
+ }
/* sort : improve rank */
- elt = table[u];
- while ((u>1) && (table[u-1].savings < elt.savings))
- table[u] = table[u-1], u--;
- table[u] = elt;
- return u;
+ elt = table[u];
+ while ((u>1) && (table[u-1].savings < elt.savings))
+ table[u] = table[u-1], u--;
+ table[u] = elt;
+ return u;
}
-
+
if (MEM_read64(buf + table[u].pos) == MEM_read64(buf + elt.pos + 1)) {
if (isIncluded(buf + table[u].pos, buf + elt.pos + 1, table[u].length)) {
size_t const addedLength = MAX( (int)elt.length - (int)table[u].length , 1 );
@@ -487,234 +487,234 @@ static U32 ZDICT_tryMerge(dictItem* table, dictItem elt, U32 eltNbToSkip, const
}
}
- return 0;
-}
-
-
-static void ZDICT_removeDictItem(dictItem* table, U32 id)
-{
+ return 0;
+}
+
+
+static void ZDICT_removeDictItem(dictItem* table, U32 id)
+{
/* convention : table[0].pos stores nb of elts */
U32 const max = table[0].pos;
- U32 u;
- if (!id) return; /* protection, should never happen */
- for (u=id; u<max-1; u++)
- table[u] = table[u+1];
- table->pos--;
-}
-
-
+ U32 u;
+ if (!id) return; /* protection, should never happen */
+ for (u=id; u<max-1; u++)
+ table[u] = table[u+1];
+ table->pos--;
+}
+
+
static void ZDICT_insertDictItem(dictItem* table, U32 maxSize, dictItem elt, const void* buffer)
-{
- /* merge if possible */
+{
+ /* merge if possible */
U32 mergeId = ZDICT_tryMerge(table, elt, 0, buffer);
- if (mergeId) {
- U32 newMerge = 1;
- while (newMerge) {
+ if (mergeId) {
+ U32 newMerge = 1;
+ while (newMerge) {
newMerge = ZDICT_tryMerge(table, table[mergeId], mergeId, buffer);
- if (newMerge) ZDICT_removeDictItem(table, mergeId);
- mergeId = newMerge;
- }
- return;
- }
-
- /* insert */
- { U32 current;
- U32 nextElt = table->pos;
- if (nextElt >= maxSize) nextElt = maxSize-1;
- current = nextElt-1;
- while (table[current].savings < elt.savings) {
- table[current+1] = table[current];
- current--;
- }
- table[current+1] = elt;
- table->pos = nextElt+1;
- }
-}
-
-
-static U32 ZDICT_dictSize(const dictItem* dictList)
-{
- U32 u, dictSize = 0;
- for (u=1; u<dictList[0].pos; u++)
- dictSize += dictList[u].length;
- return dictSize;
-}
-
-
+ if (newMerge) ZDICT_removeDictItem(table, mergeId);
+ mergeId = newMerge;
+ }
+ return;
+ }
+
+ /* insert */
+ { U32 current;
+ U32 nextElt = table->pos;
+ if (nextElt >= maxSize) nextElt = maxSize-1;
+ current = nextElt-1;
+ while (table[current].savings < elt.savings) {
+ table[current+1] = table[current];
+ current--;
+ }
+ table[current+1] = elt;
+ table->pos = nextElt+1;
+ }
+}
+
+
+static U32 ZDICT_dictSize(const dictItem* dictList)
+{
+ U32 u, dictSize = 0;
+ for (u=1; u<dictList[0].pos; u++)
+ dictSize += dictList[u].length;
+ return dictSize;
+}
+
+
static size_t ZDICT_trainBuffer_legacy(dictItem* dictList, U32 dictListSize,
- const void* const buffer, size_t bufferSize, /* buffer must end with noisy guard band */
- const size_t* fileSizes, unsigned nbFiles,
+ const void* const buffer, size_t bufferSize, /* buffer must end with noisy guard band */
+ const size_t* fileSizes, unsigned nbFiles,
unsigned minRatio, U32 notificationLevel)
-{
- int* const suffix0 = (int*)malloc((bufferSize+2)*sizeof(*suffix0));
- int* const suffix = suffix0+1;
- U32* reverseSuffix = (U32*)malloc((bufferSize)*sizeof(*reverseSuffix));
- BYTE* doneMarks = (BYTE*)malloc((bufferSize+16)*sizeof(*doneMarks)); /* +16 for overflow security */
- U32* filePos = (U32*)malloc(nbFiles * sizeof(*filePos));
- size_t result = 0;
+{
+ int* const suffix0 = (int*)malloc((bufferSize+2)*sizeof(*suffix0));
+ int* const suffix = suffix0+1;
+ U32* reverseSuffix = (U32*)malloc((bufferSize)*sizeof(*reverseSuffix));
+ BYTE* doneMarks = (BYTE*)malloc((bufferSize+16)*sizeof(*doneMarks)); /* +16 for overflow security */
+ U32* filePos = (U32*)malloc(nbFiles * sizeof(*filePos));
+ size_t result = 0;
clock_t displayClock = 0;
clock_t const refreshRate = CLOCKS_PER_SEC * 3 / 10;
-
+
# undef DISPLAYUPDATE
# define DISPLAYUPDATE(l, ...) if (notificationLevel>=l) { \
if (ZDICT_clockSpan(displayClock) > refreshRate) \
{ displayClock = clock(); DISPLAY(__VA_ARGS__); \
if (notificationLevel>=4) fflush(stderr); } }
- /* init */
- DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
- if (!suffix0 || !reverseSuffix || !doneMarks || !filePos) {
- result = ERROR(memory_allocation);
- goto _cleanup;
- }
- if (minRatio < MINRATIO) minRatio = MINRATIO;
- memset(doneMarks, 0, bufferSize+16);
-
- /* limit sample set size (divsufsort limitation)*/
+ /* init */
+ DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
+ if (!suffix0 || !reverseSuffix || !doneMarks || !filePos) {
+ result = ERROR(memory_allocation);
+ goto _cleanup;
+ }
+ if (minRatio < MINRATIO) minRatio = MINRATIO;
+ memset(doneMarks, 0, bufferSize+16);
+
+ /* limit sample set size (divsufsort limitation)*/
if (bufferSize > ZDICT_MAX_SAMPLES_SIZE) DISPLAYLEVEL(3, "sample set too large : reduced to %u MB ...\n", (unsigned)(ZDICT_MAX_SAMPLES_SIZE>>20));
- while (bufferSize > ZDICT_MAX_SAMPLES_SIZE) bufferSize -= fileSizes[--nbFiles];
-
- /* sort */
+ while (bufferSize > ZDICT_MAX_SAMPLES_SIZE) bufferSize -= fileSizes[--nbFiles];
+
+ /* sort */
DISPLAYLEVEL(2, "sorting %u files of total size %u MB ...\n", nbFiles, (unsigned)(bufferSize>>20));
- { int const divSuftSortResult = divsufsort((const unsigned char*)buffer, suffix, (int)bufferSize, 0);
- if (divSuftSortResult != 0) { result = ERROR(GENERIC); goto _cleanup; }
- }
- suffix[bufferSize] = (int)bufferSize; /* leads into noise */
- suffix0[0] = (int)bufferSize; /* leads into noise */
- /* build reverse suffix sort */
- { size_t pos;
- for (pos=0; pos < bufferSize; pos++)
- reverseSuffix[suffix[pos]] = (U32)pos;
+ { int const divSuftSortResult = divsufsort((const unsigned char*)buffer, suffix, (int)bufferSize, 0);
+ if (divSuftSortResult != 0) { result = ERROR(GENERIC); goto _cleanup; }
+ }
+ suffix[bufferSize] = (int)bufferSize; /* leads into noise */
+ suffix0[0] = (int)bufferSize; /* leads into noise */
+ /* build reverse suffix sort */
+ { size_t pos;
+ for (pos=0; pos < bufferSize; pos++)
+ reverseSuffix[suffix[pos]] = (U32)pos;
/* note filePos tracks borders between samples.
It's not used at this stage, but planned to become useful in a later update */
- filePos[0] = 0;
- for (pos=1; pos<nbFiles; pos++)
- filePos[pos] = (U32)(filePos[pos-1] + fileSizes[pos-1]);
- }
-
- DISPLAYLEVEL(2, "finding patterns ... \n");
- DISPLAYLEVEL(3, "minimum ratio : %u \n", minRatio);
-
- { U32 cursor; for (cursor=0; cursor < bufferSize; ) {
- dictItem solution;
- if (doneMarks[cursor]) { cursor++; continue; }
+ filePos[0] = 0;
+ for (pos=1; pos<nbFiles; pos++)
+ filePos[pos] = (U32)(filePos[pos-1] + fileSizes[pos-1]);
+ }
+
+ DISPLAYLEVEL(2, "finding patterns ... \n");
+ DISPLAYLEVEL(3, "minimum ratio : %u \n", minRatio);
+
+ { U32 cursor; for (cursor=0; cursor < bufferSize; ) {
+ dictItem solution;
+ if (doneMarks[cursor]) { cursor++; continue; }
solution = ZDICT_analyzePos(doneMarks, suffix, reverseSuffix[cursor], buffer, minRatio, notificationLevel);
- if (solution.length==0) { cursor++; continue; }
+ if (solution.length==0) { cursor++; continue; }
ZDICT_insertDictItem(dictList, dictListSize, solution, buffer);
- cursor += solution.length;
- DISPLAYUPDATE(2, "\r%4.2f %% \r", (double)cursor / bufferSize * 100);
- } }
-
-_cleanup:
- free(suffix0);
- free(reverseSuffix);
- free(doneMarks);
- free(filePos);
- return result;
-}
-
-
-static void ZDICT_fillNoise(void* buffer, size_t length)
-{
+ cursor += solution.length;
+ DISPLAYUPDATE(2, "\r%4.2f %% \r", (double)cursor / bufferSize * 100);
+ } }
+
+_cleanup:
+ free(suffix0);
+ free(reverseSuffix);
+ free(doneMarks);
+ free(filePos);
+ return result;
+}
+
+
+static void ZDICT_fillNoise(void* buffer, size_t length)
+{
unsigned const prime1 = 2654435761U;
unsigned const prime2 = 2246822519U;
unsigned acc = prime1;
size_t p=0;
- for (p=0; p<length; p++) {
+ for (p=0; p<length; p++) {
acc *= prime2;
- ((unsigned char*)buffer)[p] = (unsigned char)(acc >> 21);
- }
-}
-
-
-typedef struct
-{
+ ((unsigned char*)buffer)[p] = (unsigned char)(acc >> 21);
+ }
+}
+
+
+typedef struct
+{
ZSTD_CDict* dict; /* dictionary */
ZSTD_CCtx* zc; /* working context */
void* workPlace; /* must be ZSTD_BLOCKSIZE_MAX allocated */
-} EStats_ress_t;
-
-#define MAXREPOFFSET 1024
-
+} EStats_ress_t;
+
+#define MAXREPOFFSET 1024
+
static void ZDICT_countEStats(EStats_ress_t esr, const ZSTD_parameters* params,
unsigned* countLit, unsigned* offsetcodeCount, unsigned* matchlengthCount, unsigned* litlengthCount, U32* repOffsets,
const void* src, size_t srcSize,
U32 notificationLevel)
-{
+{
size_t const blockSizeMax = MIN (ZSTD_BLOCKSIZE_MAX, 1 << params->cParams.windowLog);
- size_t cSize;
-
- if (srcSize > blockSizeMax) srcSize = blockSizeMax; /* protection vs large samples */
+ size_t cSize;
+
+ if (srcSize > blockSizeMax) srcSize = blockSizeMax; /* protection vs large samples */
{ size_t const errorCode = ZSTD_compressBegin_usingCDict(esr.zc, esr.dict);
if (ZSTD_isError(errorCode)) { DISPLAYLEVEL(1, "warning : ZSTD_compressBegin_usingCDict failed \n"); return; }
}
cSize = ZSTD_compressBlock(esr.zc, esr.workPlace, ZSTD_BLOCKSIZE_MAX, src, srcSize);
if (ZSTD_isError(cSize)) { DISPLAYLEVEL(3, "warning : could not compress sample size %u \n", (unsigned)srcSize); return; }
-
- if (cSize) { /* if == 0; block is not compressible */
+
+ if (cSize) { /* if == 0; block is not compressible */
const seqStore_t* const seqStorePtr = ZSTD_getSeqStore(esr.zc);
-
- /* literals stats */
- { const BYTE* bytePtr;
- for(bytePtr = seqStorePtr->litStart; bytePtr < seqStorePtr->lit; bytePtr++)
- countLit[*bytePtr]++;
- }
-
- /* seqStats */
- { U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
- ZSTD_seqToCodes(seqStorePtr);
-
- { const BYTE* codePtr = seqStorePtr->ofCode;
- U32 u;
- for (u=0; u<nbSeq; u++) offsetcodeCount[codePtr[u]]++;
- }
-
- { const BYTE* codePtr = seqStorePtr->mlCode;
- U32 u;
- for (u=0; u<nbSeq; u++) matchlengthCount[codePtr[u]]++;
- }
-
- { const BYTE* codePtr = seqStorePtr->llCode;
- U32 u;
- for (u=0; u<nbSeq; u++) litlengthCount[codePtr[u]]++;
- }
-
- if (nbSeq >= 2) { /* rep offsets */
- const seqDef* const seq = seqStorePtr->sequencesStart;
+
+ /* literals stats */
+ { const BYTE* bytePtr;
+ for(bytePtr = seqStorePtr->litStart; bytePtr < seqStorePtr->lit; bytePtr++)
+ countLit[*bytePtr]++;
+ }
+
+ /* seqStats */
+ { U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
+ ZSTD_seqToCodes(seqStorePtr);
+
+ { const BYTE* codePtr = seqStorePtr->ofCode;
+ U32 u;
+ for (u=0; u<nbSeq; u++) offsetcodeCount[codePtr[u]]++;
+ }
+
+ { const BYTE* codePtr = seqStorePtr->mlCode;
+ U32 u;
+ for (u=0; u<nbSeq; u++) matchlengthCount[codePtr[u]]++;
+ }
+
+ { const BYTE* codePtr = seqStorePtr->llCode;
+ U32 u;
+ for (u=0; u<nbSeq; u++) litlengthCount[codePtr[u]]++;
+ }
+
+ if (nbSeq >= 2) { /* rep offsets */
+ const seqDef* const seq = seqStorePtr->sequencesStart;
U32 offset1 = seq[0].offBase - ZSTD_REP_NUM;
U32 offset2 = seq[1].offBase - ZSTD_REP_NUM;
- if (offset1 >= MAXREPOFFSET) offset1 = 0;
- if (offset2 >= MAXREPOFFSET) offset2 = 0;
- repOffsets[offset1] += 3;
- repOffsets[offset2] += 1;
- } } }
-}
-
-static size_t ZDICT_totalSampleSize(const size_t* fileSizes, unsigned nbFiles)
-{
- size_t total=0;
- unsigned u;
- for (u=0; u<nbFiles; u++) total += fileSizes[u];
- return total;
-}
-
-typedef struct { U32 offset; U32 count; } offsetCount_t;
-
-static void ZDICT_insertSortCount(offsetCount_t table[ZSTD_REP_NUM+1], U32 val, U32 count)
-{
- U32 u;
- table[ZSTD_REP_NUM].offset = val;
- table[ZSTD_REP_NUM].count = count;
- for (u=ZSTD_REP_NUM; u>0; u--) {
- offsetCount_t tmp;
- if (table[u-1].count >= table[u].count) break;
- tmp = table[u-1];
- table[u-1] = table[u];
- table[u] = tmp;
- }
-}
-
+ if (offset1 >= MAXREPOFFSET) offset1 = 0;
+ if (offset2 >= MAXREPOFFSET) offset2 = 0;
+ repOffsets[offset1] += 3;
+ repOffsets[offset2] += 1;
+ } } }
+}
+
+static size_t ZDICT_totalSampleSize(const size_t* fileSizes, unsigned nbFiles)
+{
+ size_t total=0;
+ unsigned u;
+ for (u=0; u<nbFiles; u++) total += fileSizes[u];
+ return total;
+}
+
+typedef struct { U32 offset; U32 count; } offsetCount_t;
+
+static void ZDICT_insertSortCount(offsetCount_t table[ZSTD_REP_NUM+1], U32 val, U32 count)
+{
+ U32 u;
+ table[ZSTD_REP_NUM].offset = val;
+ table[ZSTD_REP_NUM].count = count;
+ for (u=ZSTD_REP_NUM; u>0; u--) {
+ offsetCount_t tmp;
+ if (table[u-1].count >= table[u].count) break;
+ tmp = table[u-1];
+ table[u-1] = table[u];
+ table[u] = tmp;
+ }
+}
+
/* ZDICT_flatLit() :
* rewrite `countLit` to contain a mostly flat but still compressible distribution of literals.
* necessary to avoid generating a non-compressible distribution that HUF_writeCTable() cannot encode.
@@ -727,47 +727,47 @@ static void ZDICT_flatLit(unsigned* countLit)
countLit[253] = 1;
countLit[254] = 1;
}
-
-#define OFFCODE_MAX 30 /* only applicable to first block */
-static size_t ZDICT_analyzeEntropy(void* dstBuffer, size_t maxDstSize,
+
+#define OFFCODE_MAX 30 /* only applicable to first block */
+static size_t ZDICT_analyzeEntropy(void* dstBuffer, size_t maxDstSize,
int compressionLevel,
const void* srcBuffer, const size_t* fileSizes, unsigned nbFiles,
const void* dictBuffer, size_t dictBufferSize,
unsigned notificationLevel)
-{
+{
unsigned countLit[256];
- HUF_CREATE_STATIC_CTABLE(hufTable, 255);
+ HUF_CREATE_STATIC_CTABLE(hufTable, 255);
unsigned offcodeCount[OFFCODE_MAX+1];
- short offcodeNCount[OFFCODE_MAX+1];
- U32 offcodeMax = ZSTD_highbit32((U32)(dictBufferSize + 128 KB));
+ short offcodeNCount[OFFCODE_MAX+1];
+ U32 offcodeMax = ZSTD_highbit32((U32)(dictBufferSize + 128 KB));
unsigned matchLengthCount[MaxML+1];
- short matchLengthNCount[MaxML+1];
+ short matchLengthNCount[MaxML+1];
unsigned litLengthCount[MaxLL+1];
- short litLengthNCount[MaxLL+1];
- U32 repOffset[MAXREPOFFSET];
- offsetCount_t bestRepOffset[ZSTD_REP_NUM+1];
+ short litLengthNCount[MaxLL+1];
+ U32 repOffset[MAXREPOFFSET];
+ offsetCount_t bestRepOffset[ZSTD_REP_NUM+1];
EStats_ress_t esr = { NULL, NULL, NULL };
- ZSTD_parameters params;
- U32 u, huffLog = 11, Offlog = OffFSELog, mlLog = MLFSELog, llLog = LLFSELog, total;
- size_t pos = 0, errorCode;
- size_t eSize = 0;
- size_t const totalSrcSize = ZDICT_totalSampleSize(fileSizes, nbFiles);
+ ZSTD_parameters params;
+ U32 u, huffLog = 11, Offlog = OffFSELog, mlLog = MLFSELog, llLog = LLFSELog, total;
+ size_t pos = 0, errorCode;
+ size_t eSize = 0;
+ size_t const totalSrcSize = ZDICT_totalSampleSize(fileSizes, nbFiles);
size_t const averageSampleSize = totalSrcSize / (nbFiles + !nbFiles);
- BYTE* dstPtr = (BYTE*)dstBuffer;
-
- /* init */
+ BYTE* dstPtr = (BYTE*)dstBuffer;
+
+ /* init */
DEBUGLOG(4, "ZDICT_analyzeEntropy");
if (offcodeMax>OFFCODE_MAX) { eSize = ERROR(dictionaryCreation_failed); goto _cleanup; } /* too large dictionary */
for (u=0; u<256; u++) countLit[u] = 1; /* any character must be described */
for (u=0; u<=offcodeMax; u++) offcodeCount[u] = 1;
for (u=0; u<=MaxML; u++) matchLengthCount[u] = 1;
for (u=0; u<=MaxLL; u++) litLengthCount[u] = 1;
- memset(repOffset, 0, sizeof(repOffset));
- repOffset[1] = repOffset[4] = repOffset[8] = 1;
- memset(bestRepOffset, 0, sizeof(bestRepOffset));
+ memset(repOffset, 0, sizeof(repOffset));
+ repOffset[1] = repOffset[4] = repOffset[8] = 1;
+ memset(bestRepOffset, 0, sizeof(bestRepOffset));
if (compressionLevel==0) compressionLevel = ZSTD_CLEVEL_DEFAULT;
- params = ZSTD_getParams(compressionLevel, averageSampleSize, dictBufferSize);
-
+ params = ZSTD_getParams(compressionLevel, averageSampleSize, dictBufferSize);
+
esr.dict = ZSTD_createCDict_advanced(dictBuffer, dictBufferSize, ZSTD_dlm_byRef, ZSTD_dct_rawContent, params.cParams, ZSTD_defaultCMem);
esr.zc = ZSTD_createCCtx();
esr.workPlace = malloc(ZSTD_BLOCKSIZE_MAX);
@@ -778,14 +778,14 @@ static size_t ZDICT_analyzeEntropy(void* dstBuffer, size_t maxDstSize,
}
/* collect stats on all samples */
- for (u=0; u<nbFiles; u++) {
+ for (u=0; u<nbFiles; u++) {
ZDICT_countEStats(esr, &params,
countLit, offcodeCount, matchLengthCount, litLengthCount, repOffset,
(const char*)srcBuffer + pos, fileSizes[u],
notificationLevel);
- pos += fileSizes[u];
- }
-
+ pos += fileSizes[u];
+ }
+
if (notificationLevel >= 4) {
/* writeStats */
DISPLAYLEVEL(4, "Offset Code Frequencies : \n");
@@ -807,114 +807,114 @@ static size_t ZDICT_analyzeEntropy(void* dstBuffer, size_t maxDstSize,
assert(maxNbBits==9);
}
huffLog = (U32)maxNbBits;
- }
-
- /* looking for most common first offsets */
- { U32 offset;
- for (offset=1; offset<MAXREPOFFSET; offset++)
- ZDICT_insertSortCount(bestRepOffset, offset, repOffset[offset]);
- }
- /* note : the result of this phase should be used to better appreciate the impact on statistics */
-
- total=0; for (u=0; u<=offcodeMax; u++) total+=offcodeCount[u];
+ }
+
+ /* looking for most common first offsets */
+ { U32 offset;
+ for (offset=1; offset<MAXREPOFFSET; offset++)
+ ZDICT_insertSortCount(bestRepOffset, offset, repOffset[offset]);
+ }
+ /* note : the result of this phase should be used to better appreciate the impact on statistics */
+
+ total=0; for (u=0; u<=offcodeMax; u++) total+=offcodeCount[u];
errorCode = FSE_normalizeCount(offcodeNCount, Offlog, offcodeCount, total, offcodeMax, /* useLowProbCount */ 1);
- if (FSE_isError(errorCode)) {
+ if (FSE_isError(errorCode)) {
eSize = errorCode;
DISPLAYLEVEL(1, "FSE_normalizeCount error with offcodeCount \n");
- goto _cleanup;
- }
- Offlog = (U32)errorCode;
-
- total=0; for (u=0; u<=MaxML; u++) total+=matchLengthCount[u];
+ goto _cleanup;
+ }
+ Offlog = (U32)errorCode;
+
+ total=0; for (u=0; u<=MaxML; u++) total+=matchLengthCount[u];
errorCode = FSE_normalizeCount(matchLengthNCount, mlLog, matchLengthCount, total, MaxML, /* useLowProbCount */ 1);
- if (FSE_isError(errorCode)) {
+ if (FSE_isError(errorCode)) {
eSize = errorCode;
DISPLAYLEVEL(1, "FSE_normalizeCount error with matchLengthCount \n");
- goto _cleanup;
- }
- mlLog = (U32)errorCode;
-
- total=0; for (u=0; u<=MaxLL; u++) total+=litLengthCount[u];
+ goto _cleanup;
+ }
+ mlLog = (U32)errorCode;
+
+ total=0; for (u=0; u<=MaxLL; u++) total+=litLengthCount[u];
errorCode = FSE_normalizeCount(litLengthNCount, llLog, litLengthCount, total, MaxLL, /* useLowProbCount */ 1);
- if (FSE_isError(errorCode)) {
+ if (FSE_isError(errorCode)) {
eSize = errorCode;
DISPLAYLEVEL(1, "FSE_normalizeCount error with litLengthCount \n");
- goto _cleanup;
- }
- llLog = (U32)errorCode;
-
- /* write result to buffer */
- { size_t const hhSize = HUF_writeCTable(dstPtr, maxDstSize, hufTable, 255, huffLog);
- if (HUF_isError(hhSize)) {
+ goto _cleanup;
+ }
+ llLog = (U32)errorCode;
+
+ /* write result to buffer */
+ { size_t const hhSize = HUF_writeCTable(dstPtr, maxDstSize, hufTable, 255, huffLog);
+ if (HUF_isError(hhSize)) {
eSize = hhSize;
DISPLAYLEVEL(1, "HUF_writeCTable error \n");
- goto _cleanup;
- }
- dstPtr += hhSize;
- maxDstSize -= hhSize;
- eSize += hhSize;
- }
-
- { size_t const ohSize = FSE_writeNCount(dstPtr, maxDstSize, offcodeNCount, OFFCODE_MAX, Offlog);
- if (FSE_isError(ohSize)) {
+ goto _cleanup;
+ }
+ dstPtr += hhSize;
+ maxDstSize -= hhSize;
+ eSize += hhSize;
+ }
+
+ { size_t const ohSize = FSE_writeNCount(dstPtr, maxDstSize, offcodeNCount, OFFCODE_MAX, Offlog);
+ if (FSE_isError(ohSize)) {
eSize = ohSize;
DISPLAYLEVEL(1, "FSE_writeNCount error with offcodeNCount \n");
- goto _cleanup;
- }
- dstPtr += ohSize;
- maxDstSize -= ohSize;
- eSize += ohSize;
- }
-
- { size_t const mhSize = FSE_writeNCount(dstPtr, maxDstSize, matchLengthNCount, MaxML, mlLog);
- if (FSE_isError(mhSize)) {
+ goto _cleanup;
+ }
+ dstPtr += ohSize;
+ maxDstSize -= ohSize;
+ eSize += ohSize;
+ }
+
+ { size_t const mhSize = FSE_writeNCount(dstPtr, maxDstSize, matchLengthNCount, MaxML, mlLog);
+ if (FSE_isError(mhSize)) {
eSize = mhSize;
DISPLAYLEVEL(1, "FSE_writeNCount error with matchLengthNCount \n");
- goto _cleanup;
- }
- dstPtr += mhSize;
- maxDstSize -= mhSize;
- eSize += mhSize;
- }
-
- { size_t const lhSize = FSE_writeNCount(dstPtr, maxDstSize, litLengthNCount, MaxLL, llLog);
- if (FSE_isError(lhSize)) {
+ goto _cleanup;
+ }
+ dstPtr += mhSize;
+ maxDstSize -= mhSize;
+ eSize += mhSize;
+ }
+
+ { size_t const lhSize = FSE_writeNCount(dstPtr, maxDstSize, litLengthNCount, MaxLL, llLog);
+ if (FSE_isError(lhSize)) {
eSize = lhSize;
DISPLAYLEVEL(1, "FSE_writeNCount error with litlengthNCount \n");
- goto _cleanup;
- }
- dstPtr += lhSize;
- maxDstSize -= lhSize;
- eSize += lhSize;
- }
-
- if (maxDstSize<12) {
+ goto _cleanup;
+ }
+ dstPtr += lhSize;
+ maxDstSize -= lhSize;
+ eSize += lhSize;
+ }
+
+ if (maxDstSize<12) {
eSize = ERROR(dstSize_tooSmall);
DISPLAYLEVEL(1, "not enough space to write RepOffsets \n");
- goto _cleanup;
- }
-# if 0
- MEM_writeLE32(dstPtr+0, bestRepOffset[0].offset);
- MEM_writeLE32(dstPtr+4, bestRepOffset[1].offset);
- MEM_writeLE32(dstPtr+8, bestRepOffset[2].offset);
-#else
- /* at this stage, we don't use the result of "most common first offset",
+ goto _cleanup;
+ }
+# if 0
+ MEM_writeLE32(dstPtr+0, bestRepOffset[0].offset);
+ MEM_writeLE32(dstPtr+4, bestRepOffset[1].offset);
+ 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 */
- MEM_writeLE32(dstPtr+0, repStartValue[0]);
- MEM_writeLE32(dstPtr+4, repStartValue[1]);
- MEM_writeLE32(dstPtr+8, repStartValue[2]);
-#endif
- eSize += 12;
-
-_cleanup:
+ MEM_writeLE32(dstPtr+0, repStartValue[0]);
+ MEM_writeLE32(dstPtr+4, repStartValue[1]);
+ MEM_writeLE32(dstPtr+8, repStartValue[2]);
+#endif
+ eSize += 12;
+
+_cleanup:
ZSTD_freeCDict(esr.dict);
- ZSTD_freeCCtx(esr.zc);
- free(esr.workPlace);
-
- return eSize;
-}
-
-
+ ZSTD_freeCCtx(esr.zc);
+ free(esr.workPlace);
+
+ return eSize;
+}
+
+
/**
* @returns the maximum repcode value
*/
@@ -931,8 +931,8 @@ size_t ZDICT_finalizeDictionary(void* dictBuffer, size_t dictBufferCapacity,
const void* customDictContent, size_t dictContentSize,
const void* samplesBuffer, const size_t* samplesSizes,
unsigned nbSamples, ZDICT_params_t params)
-{
- size_t hSize;
+{
+ size_t hSize;
#define HBUFFSIZE 256 /* should prove large enough for all entropy headers */
BYTE header[HBUFFSIZE];
int const compressionLevel = (params.compressionLevel == 0) ? ZSTD_CLEVEL_DEFAULT : params.compressionLevel;
@@ -940,24 +940,24 @@ size_t ZDICT_finalizeDictionary(void* dictBuffer, size_t dictBufferCapacity,
/* 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 (dictBufferCapacity < ZDICT_DICTSIZE_MIN) return ERROR(dstSize_tooSmall);
- /* dictionary header */
+ /* dictionary header */
MEM_writeLE32(header, ZSTD_MAGIC_DICTIONARY);
{ U64 const randomID = XXH64(customDictContent, dictContentSize, 0);
- U32 const compliantID = (randomID % ((1U<<31)-32768)) + 32768;
- U32 const dictID = params.dictID ? params.dictID : compliantID;
+ U32 const compliantID = (randomID % ((1U<<31)-32768)) + 32768;
+ U32 const dictID = params.dictID ? params.dictID : compliantID;
MEM_writeLE32(header+4, dictID);
- }
- hSize = 8;
-
- /* entropy tables */
- DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
- DISPLAYLEVEL(2, "statistics ... \n");
+ }
+ hSize = 8;
+
+ /* entropy tables */
+ DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
+ DISPLAYLEVEL(2, "statistics ... \n");
{ size_t const eSize = ZDICT_analyzeEntropy(header+hSize, HBUFFSIZE-hSize,
compressionLevel,
samplesBuffer, samplesSizes, nbSamples,
@@ -1022,14 +1022,14 @@ static size_t ZDICT_addEntropyTablesFromBuffer_advanced(
DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
DISPLAYLEVEL(2, "statistics ... \n");
{ size_t const eSize = ZDICT_analyzeEntropy((char*)dictBuffer+hSize, dictBufferCapacity-hSize,
- compressionLevel,
- samplesBuffer, samplesSizes, nbSamples,
+ compressionLevel,
+ samplesBuffer, samplesSizes, nbSamples,
(char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize,
notificationLevel);
if (ZDICT_isError(eSize)) return eSize;
hSize += eSize;
}
-
+
/* add dictionary header (after entropy tables) */
MEM_writeLE32(dictBuffer, ZSTD_MAGIC_DICTIONARY);
{ U64 const randomID = XXH64((char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize, 0);
@@ -1038,44 +1038,44 @@ static size_t ZDICT_addEntropyTablesFromBuffer_advanced(
MEM_writeLE32((char*)dictBuffer+4, dictID);
}
- if (hSize + dictContentSize < dictBufferCapacity)
- memmove((char*)dictBuffer + hSize, (char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize);
- return MIN(dictBufferCapacity, hSize+dictContentSize);
-}
-
+ if (hSize + dictContentSize < dictBufferCapacity)
+ memmove((char*)dictBuffer + hSize, (char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize);
+ return MIN(dictBufferCapacity, hSize+dictContentSize);
+}
+
/*! ZDICT_trainFromBuffer_unsafe_legacy() :
* Warning : `samplesBuffer` must be followed by noisy guard band !!!
-* @return : size of dictionary, or an error code which can be tested with ZDICT_isError()
-*/
+* @return : size of dictionary, or an error code which can be tested with ZDICT_isError()
+*/
static size_t ZDICT_trainFromBuffer_unsafe_legacy(
- void* dictBuffer, size_t maxDictSize,
- const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
+ void* dictBuffer, size_t maxDictSize,
+ const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
ZDICT_legacy_params_t params)
-{
+{
U32 const dictListSize = MAX(MAX(DICTLISTSIZE_DEFAULT, nbSamples), (U32)(maxDictSize/16));
- dictItem* const dictList = (dictItem*)malloc(dictListSize * sizeof(*dictList));
- unsigned const selectivity = params.selectivityLevel == 0 ? g_selectivity_default : params.selectivityLevel;
- unsigned const minRep = (selectivity > 30) ? MINRATIO : nbSamples >> selectivity;
- size_t const targetDictSize = maxDictSize;
- size_t const samplesBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples);
- size_t dictSize = 0;
+ dictItem* const dictList = (dictItem*)malloc(dictListSize * sizeof(*dictList));
+ unsigned const selectivity = params.selectivityLevel == 0 ? g_selectivity_default : params.selectivityLevel;
+ unsigned const minRep = (selectivity > 30) ? MINRATIO : nbSamples >> selectivity;
+ size_t const targetDictSize = maxDictSize;
+ size_t const samplesBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples);
+ size_t dictSize = 0;
U32 const notificationLevel = params.zParams.notificationLevel;
-
- /* checks */
- if (!dictList) return ERROR(memory_allocation);
+
+ /* checks */
+ if (!dictList) return ERROR(memory_allocation);
if (maxDictSize < ZDICT_DICTSIZE_MIN) { free(dictList); return ERROR(dstSize_tooSmall); } /* requested dictionary size is too small */
if (samplesBuffSize < ZDICT_MIN_SAMPLES_SIZE) { free(dictList); return ERROR(dictionaryCreation_failed); } /* not enough source to create dictionary */
-
- /* init */
- ZDICT_initDictItem(dictList);
-
- /* build dictionary */
+
+ /* init */
+ ZDICT_initDictItem(dictList);
+
+ /* build dictionary */
ZDICT_trainBuffer_legacy(dictList, dictListSize,
samplesBuffer, samplesBuffSize,
samplesSizes, nbSamples,
minRep, notificationLevel);
-
- /* display best matches */
+
+ /* display best matches */
if (params.zParams.notificationLevel>= 3) {
unsigned const nb = MIN(25, dictList[0].pos);
unsigned const dictContentSize = ZDICT_dictSize(dictList);
@@ -1090,98 +1090,98 @@ static size_t ZDICT_trainFromBuffer_unsafe_legacy(
free(dictList);
return ERROR(GENERIC); /* should never happen */
}
- DISPLAYLEVEL(3, "%3u:%3u bytes at pos %8u, savings %7u bytes |",
+ DISPLAYLEVEL(3, "%3u:%3u bytes at pos %8u, savings %7u bytes |",
u, length, pos, (unsigned)dictList[u].savings);
ZDICT_printHex((const char*)samplesBuffer+pos, printedLength);
- DISPLAYLEVEL(3, "| \n");
- } }
-
-
- /* create dictionary */
+ DISPLAYLEVEL(3, "| \n");
+ } }
+
+
+ /* create dictionary */
{ unsigned dictContentSize = ZDICT_dictSize(dictList);
if (dictContentSize < ZDICT_CONTENTSIZE_MIN) { free(dictList); return ERROR(dictionaryCreation_failed); } /* dictionary content too small */
if (dictContentSize < targetDictSize/4) {
DISPLAYLEVEL(2, "! warning : selected content significantly smaller than requested (%u < %u) \n", dictContentSize, (unsigned)maxDictSize);
if (samplesBuffSize < 10 * targetDictSize)
DISPLAYLEVEL(2, "! consider increasing the number of samples (total size : %u MB)\n", (unsigned)(samplesBuffSize>>20));
- if (minRep > MINRATIO) {
- DISPLAYLEVEL(2, "! consider increasing selectivity to produce larger dictionary (-s%u) \n", selectivity+1);
- DISPLAYLEVEL(2, "! note : larger dictionaries are not necessarily better, test its efficiency on samples \n");
- }
- }
-
+ if (minRep > MINRATIO) {
+ DISPLAYLEVEL(2, "! consider increasing selectivity to produce larger dictionary (-s%u) \n", selectivity+1);
+ DISPLAYLEVEL(2, "! note : larger dictionaries are not necessarily better, test its efficiency on samples \n");
+ }
+ }
+
if ((dictContentSize > targetDictSize*3) && (nbSamples > 2*MINRATIO) && (selectivity>1)) {
unsigned proposedSelectivity = selectivity-1;
- while ((nbSamples >> proposedSelectivity) <= MINRATIO) { proposedSelectivity--; }
+ while ((nbSamples >> proposedSelectivity) <= MINRATIO) { proposedSelectivity--; }
DISPLAYLEVEL(2, "! note : calculated dictionary significantly larger than requested (%u > %u) \n", dictContentSize, (unsigned)maxDictSize);
DISPLAYLEVEL(2, "! consider increasing dictionary size, or produce denser dictionary (-s%u) \n", proposedSelectivity);
DISPLAYLEVEL(2, "! always test dictionary efficiency on real samples \n");
- }
-
- /* limit dictionary size */
- { U32 const max = dictList->pos; /* convention : nb of useful elts within dictList */
- U32 currentSize = 0;
- U32 n; for (n=1; n<max; n++) {
- currentSize += dictList[n].length;
- if (currentSize > targetDictSize) { currentSize -= dictList[n].length; break; }
- }
- dictList->pos = n;
- dictContentSize = currentSize;
- }
-
- /* build dict content */
- { U32 u;
- BYTE* ptr = (BYTE*)dictBuffer + maxDictSize;
- for (u=1; u<dictList->pos; u++) {
- U32 l = dictList[u].length;
- ptr -= l;
- if (ptr<(BYTE*)dictBuffer) { free(dictList); return ERROR(GENERIC); } /* should not happen */
- memcpy(ptr, (const char*)samplesBuffer+dictList[u].pos, l);
- } }
-
- dictSize = ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, maxDictSize,
- samplesBuffer, samplesSizes, nbSamples,
+ }
+
+ /* limit dictionary size */
+ { U32 const max = dictList->pos; /* convention : nb of useful elts within dictList */
+ U32 currentSize = 0;
+ U32 n; for (n=1; n<max; n++) {
+ currentSize += dictList[n].length;
+ if (currentSize > targetDictSize) { currentSize -= dictList[n].length; break; }
+ }
+ dictList->pos = n;
+ dictContentSize = currentSize;
+ }
+
+ /* build dict content */
+ { U32 u;
+ BYTE* ptr = (BYTE*)dictBuffer + maxDictSize;
+ for (u=1; u<dictList->pos; u++) {
+ U32 l = dictList[u].length;
+ ptr -= l;
+ if (ptr<(BYTE*)dictBuffer) { free(dictList); return ERROR(GENERIC); } /* should not happen */
+ memcpy(ptr, (const char*)samplesBuffer+dictList[u].pos, l);
+ } }
+
+ dictSize = ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, maxDictSize,
+ samplesBuffer, samplesSizes, nbSamples,
params.zParams);
- }
-
- /* clean up */
- free(dictList);
- return dictSize;
-}
-
-
+ }
+
+ /* clean up */
+ free(dictList);
+ return dictSize;
+}
+
+
/* ZDICT_trainFromBuffer_legacy() :
* issue : samplesBuffer need to be followed by a noisy guard band.
* work around : duplicate the buffer, and add the noise */
size_t ZDICT_trainFromBuffer_legacy(void* dictBuffer, size_t dictBufferCapacity,
const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
ZDICT_legacy_params_t params)
-{
- size_t result;
- void* newBuff;
- size_t const sBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples);
+{
+ size_t result;
+ void* newBuff;
+ size_t const sBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples);
if (sBuffSize < ZDICT_MIN_SAMPLES_SIZE) return 0; /* not enough content => no dictionary */
-
- newBuff = malloc(sBuffSize + NOISELENGTH);
- if (!newBuff) return ERROR(memory_allocation);
-
- memcpy(newBuff, samplesBuffer, sBuffSize);
- ZDICT_fillNoise((char*)newBuff + sBuffSize, NOISELENGTH); /* guard band, for end of buffer condition */
-
+
+ newBuff = malloc(sBuffSize + NOISELENGTH);
+ if (!newBuff) return ERROR(memory_allocation);
+
+ memcpy(newBuff, samplesBuffer, sBuffSize);
+ ZDICT_fillNoise((char*)newBuff + sBuffSize, NOISELENGTH); /* guard band, for end of buffer condition */
+
result =
ZDICT_trainFromBuffer_unsafe_legacy(dictBuffer, dictBufferCapacity, newBuff,
samplesSizes, nbSamples, params);
- free(newBuff);
- return result;
-}
-
-
-size_t ZDICT_trainFromBuffer(void* dictBuffer, size_t dictBufferCapacity,
- const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples)
-{
+ free(newBuff);
+ return result;
+}
+
+
+size_t ZDICT_trainFromBuffer(void* dictBuffer, size_t dictBufferCapacity,
+ const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples)
+{
ZDICT_fastCover_params_t params;
DEBUGLOG(3, "ZDICT_trainFromBuffer");
- memset(&params, 0, sizeof(params));
+ memset(&params, 0, sizeof(params));
params.d = 8;
params.steps = 4;
/* Use default level since no compression level information is available */
@@ -1192,14 +1192,14 @@ size_t ZDICT_trainFromBuffer(void* dictBuffer, size_t dictBufferCapacity,
return ZDICT_optimizeTrainFromBuffer_fastCover(dictBuffer, dictBufferCapacity,
samplesBuffer, samplesSizes, nbSamples,
&params);
-}
-
-size_t ZDICT_addEntropyTablesFromBuffer(void* dictBuffer, size_t dictContentSize, size_t dictBufferCapacity,
+}
+
+size_t ZDICT_addEntropyTablesFromBuffer(void* dictBuffer, size_t dictContentSize, size_t dictBufferCapacity,
const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples)
-{
- ZDICT_params_t params;
- memset(&params, 0, sizeof(params));
- return ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, dictBufferCapacity,
- samplesBuffer, samplesSizes, nbSamples,
- params);
-}
+{
+ ZDICT_params_t params;
+ memset(&params, 0, sizeof(params));
+ return ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, dictBufferCapacity,
+ samplesBuffer, samplesSizes, nbSamples,
+ params);
+}