diff options
author | Ruslan Kovalev <ruslan.a.kovalev@gmail.com> | 2022-02-10 16:46:45 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:46:45 +0300 |
commit | 9123176b341b6f2658cff5132482b8237c1416c8 (patch) | |
tree | 49e222ea1c5804306084bb3ae065bb702625360f /contrib/libs/zstd/lib/dictBuilder/zdict.c | |
parent | 59e19371de37995fcb36beb16cd6ec030af960bc (diff) | |
download | ydb-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.c | 1446 |
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, ¶ms, 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(¶ms, 0, sizeof(params)); + memset(¶ms, 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, ¶ms); -} - -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(¶ms, 0, sizeof(params)); - return ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, dictBufferCapacity, - samplesBuffer, samplesSizes, nbSamples, - params); -} +{ + ZDICT_params_t params; + memset(¶ms, 0, sizeof(params)); + return ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, dictBufferCapacity, + samplesBuffer, samplesSizes, nbSamples, + params); +} |