mercurial: comparison contrib/python-zstandard/zstd/dictBuilder/zdict.c

equal deleted inserted replaced

-:1ce7a55b09d1
+:b1fb341d8a61
-/**
+/*
 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
 * All rights reserved.
 *
-* This source code is licensed under the BSD-style license found in the
+* This source code is licensed under both the BSD-style license (found in the
-* LICENSE file in the root directory of this source tree. An additional grant
+* LICENSE file in the root directory of this source tree) and the GPLv2 (found
-* of patent rights can be found in the PATENTS file in the same directory.
+* 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
 ****************************************/
+#define MINRATIO 4   /* minimum nb of apparition to be selected in dictionary */
 #define ZDICT_MAX_SAMPLES_SIZE (2000U << 20)
-#define ZDICT_MIN_SAMPLES_SIZE 512
+#define ZDICT_MIN_SAMPLES_SIZE (ZDICT_CONTENTSIZE_MIN * MINRATIO)
 /*-**************************************
 *  Compiler Options
 ****************************************/
 #define DICTLISTSIZE_DEFAULT 10000
 #define NOISELENGTH 32
-#define MINRATIO 4
+static const int g_compressionLevel_default = 3;
-static const int g_compressionLevel_default = 6;
 static const U32 g_selectivity_default = 9;
-static const size_t g_provision_entropySize = 200;
-static const size_t g_min_fast_dictContent = 192;
 /*-*************************************
 *  Console display
 ***************************************/
 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_DICT_MAGIC) return 0;
+if (MEM_readLE32(dictBuffer) != ZSTD_MAGIC_DICTIONARY) return 0;
 return MEM_readLE32((const char*)dictBuffer + 4);
 }
 /*-********************************************************
 *  Dictionary training functions
 **********************************************************/
-static unsigned ZDICT_NbCommonBytes (register size_t val)
+static unsigned ZDICT_NbCommonBytes (size_t val)
 {
 if (MEM_isLittleEndian()) {
 if (MEM_64bits()) {
 #       if defined(_MSC_VER) && defined(_WIN64)
 unsigned long r = 0;
 {
 U32 lengthList[LLIMIT] = {0};
 U32 cumulLength[LLIMIT] = {0};
 U32 savings[LLIMIT] = {0};
 const BYTE* b = (const BYTE*)buffer;
-size_t length;
 size_t maxLength = LLIMIT;
 size_t pos = suffix[start];
 U32 end = start;
 dictItem solution;
 /* 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 u16 = MEM_read16(b+pos+4);
+U16 const pattern16 = MEM_read16(b+pos+4);
-U32 u, e = 6;
+U32 u, patternEnd = 6;
-while (MEM_read16(b+pos+e) == u16) e+=2 ;
+while (MEM_read16(b+pos+patternEnd) == pattern16) patternEnd+=2 ;
-if (b[pos+e] == b[pos+e-1]) e++;
+if (b[pos+patternEnd] == b[pos+patternEnd-1]) patternEnd++;
-for (u=1; u<e; u++)
+for (u=1; u<patternEnd; u++)
 doneMarks[pos+u] = 1;
 return solution;
 }
 /* look forward */
-do {
+{   size_t length;
-end++;
+do {
-length = ZDICT_count(b + pos, b + suffix[end]);
+end++;
-} while (length >=MINMATCHLENGTH);
+length = ZDICT_count(b + pos, b + suffix[end]);
+} while (length >= MINMATCHLENGTH);
+}
 /* look backward */
-do {
+{   size_t length;
-length = ZDICT_count(b + pos, b + *(suffix+start-1));
+do {
-if (length >=MINMATCHLENGTH) start--;
+length = ZDICT_count(b + pos, b + *(suffix+start-1));
-} while(length >= MINMATCHLENGTH);
+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++)
 U32 currentID = refinedStart;
 U32 id;
 U32 selectedCount = 0;
 U32 selectedID = currentID;
 for (id =refinedStart; id < refinedEnd; id++) {
-if (b[ suffix[id] + searchLength] != currentChar) {
+if (b[suffix[id] + searchLength] != currentChar) {
 if (currentCount > selectedCount) {
 selectedCount = currentCount;
 selectedID = currentID;
 }
 currentID = id;
 pos = suffix[refinedStart];
 end = start;
 memset(lengthList, 0, sizeof(lengthList));
 /* look forward */
-do {
+{   size_t length;
-end++;
+do {
-length = ZDICT_count(b + pos, b + suffix[end]);
+end++;
-if (length >= LLIMIT) length = LLIMIT-1;
+length = ZDICT_count(b + pos, b + suffix[end]);
-lengthList[length]++;
+if (length >= LLIMIT) length = LLIMIT-1;
-} while (length >=MINMATCHLENGTH);
+lengthList[length]++;
+} while (length >=MINMATCHLENGTH);
+}
 /* look backward */
-length = MINMATCHLENGTH;
+{   size_t length = MINMATCHLENGTH;
 while ((length >= MINMATCHLENGTH) & (start > 0)) {
-	length = ZDICT_count(b + pos, b + suffix[start - 1]);
+length = ZDICT_count(b + pos, b + suffix[start - 1]);
-	if (length >= LLIMIT) length = LLIMIT - 1;
+if (length >= LLIMIT) length = LLIMIT - 1;
-	lengthList[length]++;
+lengthList[length]++;
-	if (length >= MINMATCHLENGTH) start--;
+if (length >= MINMATCHLENGTH) start--;
+}
 }
 /* largest useful length */
 memset(cumulLength, 0, sizeof(cumulLength));
 cumulLength[maxLength-1] = lengthList[maxLength-1];
 solution.savings = savings[maxLength];
 /* mark positions done */
 {   U32 id;
 for (id=start; id<end; id++) {
-U32 p, pEnd;
+U32 p, pEnd, length;
 U32 const testedPos = suffix[id];
 if (testedPos == pos)
 length = solution.length;
 else {
-length = ZDICT_count(b+pos, b+testedPos);
+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;
 }
-/*! ZDICT_checkMerge
+static int isIncluded(const void* in, const void* container, size_t length)
+{
+const char* const ip = (const char*) in;
+const char* const into = (const char*) container;
+size_t u;
+for (u=0; u<length; u++) {  /* works because end of buffer is a noisy guard band */
+if (ip[u] != into[u]) break;
+}
+return u==length;
+}
+/*! ZDICT_tryMerge() :
 check if dictItem can be merged, do it if possible
 @return : id of destination elt, 0 if not merged
 */
-static U32 ZDICT_checkMerge(dictItem* table, dictItem elt, U32 eltNbToSkip)
+static U32 ZDICT_tryMerge(dictItem* table, dictItem elt, U32 eltNbToSkip, const void* buffer)
 {
 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;
 if ((table[u].pos > elt.pos) && (table[u].pos <= eltEnd)) {  /* overlap, existing > new */
 /* append */
-U32 addedLength = table[u].pos - elt.pos;
+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].savings += elt.length / 8;    /* rough approx bonus */
 elt = table[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 */
-int addedLength = (int)eltEnd - (table[u].pos + table[u].length);
+int const addedLength = (int)eltEnd - (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 */
 }
 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 );
+table[u].pos = elt.pos;
+table[u].savings += (U32)(elt.savings * addedLength / elt.length);
+table[u].length = MIN(elt.length, table[u].length + 1);
+return u;
+}
+}
+}
 return 0;
 }
 static void ZDICT_removeDictItem(dictItem* table, U32 id)
 {
-/* convention : first element is nb of elts */
+/* convention : table[0].pos stores nb of elts */
-U32 const max = table->pos;
+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--;
 }
-static void ZDICT_insertDictItem(dictItem* table, U32 maxSize, dictItem elt)
+static void ZDICT_insertDictItem(dictItem* table, U32 maxSize, dictItem elt, const void* buffer)
 {
 /* merge if possible */
-U32 mergeId = ZDICT_checkMerge(table, elt, 0);
+U32 mergeId = ZDICT_tryMerge(table, elt, 0, buffer);
 if (mergeId) {
 U32 newMerge = 1;
 while (newMerge) {
-newMerge = ZDICT_checkMerge(table, table[mergeId], mergeId);
+newMerge = ZDICT_tryMerge(table, table[mergeId], mergeId, buffer);
 if (newMerge) ZDICT_removeDictItem(table, mergeId);
 mergeId = newMerge;
 }
 return;
 }
 dictSize += dictList[u].length;
 return dictSize;
 }
-static size_t ZDICT_trainBuffer(dictItem* dictList, U32 dictListSize,
+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,
 U32 minRatio, U32 notificationLevel)
 {
 int* const suffix0 = (int*)malloc((bufferSize+2)*sizeof(*suffix0));
 clock_t const refreshRate = CLOCKS_PER_SEC * 3 / 10;
 #   define DISPLAYUPDATE(l, ...) if (notificationLevel>=l) { \
 if (ZDICT_clockSpan(displayClock) > refreshRate)  \
 { displayClock = clock(); DISPLAY(__VA_ARGS__); \
-if (notificationLevel>=4) fflush(stdout); } }
+if (notificationLevel>=4) fflush(stderr); } }
 /* init */
 DISPLAYLEVEL(2, "\r%70s\r", "");   /* clean display line */
 if (!suffix0 || !reverseSuffix || !doneMarks || !filePos) {
 result = ERROR(memory_allocation);
 {   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; }
-ZDICT_insertDictItem(dictList, dictListSize, solution);
+ZDICT_insertDictItem(dictList, dictListSize, solution, buffer);
 cursor += solution.length;
 DISPLAYUPDATE(2, "\r%4.2f %% \r", (double)cursor / bufferSize * 100);
 }   }
 _cleanup:
 }
 typedef struct
 {
-ZSTD_CCtx* ref;
+ZSTD_CCtx* ref;    /* contains reference to dictionary */
-ZSTD_CCtx* zc;
+ZSTD_CCtx* zc;     /* working context */
-void* workPlace;   /* must be ZSTD_BLOCKSIZE_ABSOLUTEMAX allocated */
+void* workPlace;   /* must be ZSTD_BLOCKSIZE_MAX allocated */
 } EStats_ress_t;
 #define MAXREPOFFSET 1024
 static void ZDICT_countEStats(EStats_ress_t esr, ZSTD_parameters params,
 U32* countLit, U32* offsetcodeCount, U32* matchlengthCount, U32* litlengthCount, U32* repOffsets,
-const void* src, size_t srcSize, U32 notificationLevel)
+const void* src, size_t srcSize,
-{
+U32 notificationLevel)
-size_t const blockSizeMax = MIN (ZSTD_BLOCKSIZE_ABSOLUTEMAX, 1 << params.cParams.windowLog);
+{
+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 const errorCode = ZSTD_copyCCtx(esr.zc, esr.ref, 0);
+{   size_t const errorCode = ZSTD_copyCCtx(esr.zc, esr.ref, 0);
 if (ZSTD_isError(errorCode)) { DISPLAYLEVEL(1, "warning : ZSTD_copyCCtx failed \n"); return; }
 }
-cSize = ZSTD_compressBlock(esr.zc, esr.workPlace, ZSTD_BLOCKSIZE_ABSOLUTEMAX, src, srcSize);
+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", (U32)srcSize); return; }
 if (cSize) {  /* if == 0; block is not compressible */
-const seqStore_t* seqStorePtr = ZSTD_getSeqStore(esr.zc);
+const seqStore_t* const seqStorePtr = ZSTD_getSeqStore(esr.zc);
 /* literals stats */
 {   const BYTE* bytePtr;
 for(bytePtr = seqStorePtr->litStart; bytePtr < seqStorePtr->lit; bytePtr++)
 countLit[*bytePtr]++;
 repOffsets[offset1] += 3;
 repOffsets[offset2] += 1;
 }   }   }
 }
-/*
-static size_t ZDICT_maxSampleSize(const size_t* fileSizes, unsigned nbFiles)
-{
-unsigned u;
-size_t max=0;
-for (u=0; u<nbFiles; u++)
-if (max < fileSizes[u]) max = fileSizes[u];
-return max;
-}
-*/
 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];
 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.
+*/
+static void ZDICT_flatLit(U32* countLit)
+{
+int u;
+for (u=1; u<256; u++) countLit[u] = 2;
+countLit[0]   = 4;
+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,
 unsigned compressionLevel,
 const void*  srcBuffer, const size_t* fileSizes, unsigned nbFiles,
 size_t const totalSrcSize = ZDICT_totalSampleSize(fileSizes, nbFiles);
 size_t const averageSampleSize = totalSrcSize / (nbFiles + !nbFiles);
 BYTE* dstPtr = (BYTE*)dstBuffer;
 /* init */
+DEBUGLOG(4, "ZDICT_analyzeEntropy");
 esr.ref = ZSTD_createCCtx();
 esr.zc = ZSTD_createCCtx();
-esr.workPlace = malloc(ZSTD_BLOCKSIZE_ABSOLUTEMAX);
+esr.workPlace = malloc(ZSTD_BLOCKSIZE_MAX);
 if (!esr.ref || !esr.zc || !esr.workPlace) {
 eSize = ERROR(memory_allocation);
 DISPLAYLEVEL(1, "Not enough memory \n");
 goto _cleanup;
 }
-if (offcodeMax>OFFCODE_MAX) { eSize = ERROR(dictionary_wrong); goto _cleanup; }   /* too large dictionary */
+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<256; u++) countLit[u] = 1;   /* any character must be described */
-for (u=0; u<=offcodeMax; u++) offcodeCount[u]=1;
+for (u=0; u<=offcodeMax; u++) offcodeCount[u] = 1;
-for (u=0; u<=MaxML; u++) matchLengthCount[u]=1;
+for (u=0; u<=MaxML; u++) matchLengthCount[u] = 1;
-for (u=0; u<=MaxLL; u++) litLengthCount[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));
-if (compressionLevel==0) compressionLevel=g_compressionLevel_default;
+if (compressionLevel<=0) compressionLevel = g_compressionLevel_default;
 params = ZSTD_getParams(compressionLevel, averageSampleSize, dictBufferSize);
 {   size_t const beginResult = ZSTD_compressBegin_advanced(esr.ref, dictBuffer, dictBufferSize, params, 0);
 if (ZSTD_isError(beginResult)) {
+DISPLAYLEVEL(1, "error : ZSTD_compressBegin_advanced() failed : %s \n", ZSTD_getErrorName(beginResult));
 eSize = ERROR(GENERIC);
-DISPLAYLEVEL(1, "error : ZSTD_compressBegin_advanced failed \n");
 goto _cleanup;
 }   }
-/* collect stats on all files */
+/* collect stats on all samples */
 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];
 }
-/* analyze */
+/* analyze, build stats, starting with literals */
-errorCode = HUF_buildCTable (hufTable, countLit, 255, huffLog);
+{   size_t maxNbBits = HUF_buildCTable (hufTable, countLit, 255, huffLog);
-if (HUF_isError(errorCode)) {
+if (HUF_isError(maxNbBits)) {
 eSize = ERROR(GENERIC);
-DISPLAYLEVEL(1, "HUF_buildCTable error \n");
+DISPLAYLEVEL(1, " HUF_buildCTable error \n");
 goto _cleanup;
 }
-huffLog = (U32)errorCode;
+if (maxNbBits==8) {  /* not compressible : will fail on HUF_writeCTable() */
+DISPLAYLEVEL(2, "warning : pathological dataset : literals are not compressible : samples are noisy or too regular \n");
+ZDICT_flatLit(countLit);  /* replace distribution by a fake "mostly flat but still compressible" distribution, that HUF_writeCTable() can encode */
+maxNbBits = HUF_buildCTable (hufTable, countLit, 255, huffLog);
+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]);
 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
-//dstPtr += 12;
 eSize += 12;
 _cleanup:
 ZSTD_freeCCtx(esr.ref);
 ZSTD_freeCCtx(esr.zc);
 const void* customDictContent, size_t dictContentSize,
 const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
 ZDICT_params_t params)
 {
 size_t hSize;
-#define HBUFFSIZE 256
+#define HBUFFSIZE 256   /* should prove large enough for all entropy headers */
 BYTE header[HBUFFSIZE];
 int const compressionLevel = (params.compressionLevel <= 0) ? g_compressionLevel_default : params.compressionLevel;
 U32 const notificationLevel = params.notificationLevel;
 /* check conditions */
+DEBUGLOG(4, "ZDICT_finalizeDictionary");
 if (dictBufferCapacity < dictContentSize) return ERROR(dstSize_tooSmall);
 if (dictContentSize < ZDICT_CONTENTSIZE_MIN) return ERROR(srcSize_wrong);
 if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) return ERROR(dstSize_tooSmall);
 /* dictionary header */
-MEM_writeLE32(header, ZSTD_DICT_MAGIC);
+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;
 MEM_writeLE32(header+4, dictID);
 }
 size_t ZDICT_addEntropyTablesFromBuffer_advanced(void* dictBuffer, size_t dictContentSize, size_t dictBufferCapacity,
 const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
 ZDICT_params_t params)
 {
-size_t hSize;
 int const compressionLevel = (params.compressionLevel <= 0) ? g_compressionLevel_default : params.compressionLevel;
 U32 const notificationLevel = params.notificationLevel;
+size_t hSize = 8;
-/* dictionary header */
-MEM_writeLE32(dictBuffer, ZSTD_DICT_MAGIC);
+/* calculate entropy tables */
-{   U64 const randomID = XXH64((char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize, 0);
-U32 const compliantID = (randomID % ((1U<<31)-32768)) + 32768;
-U32 const dictID = params.dictID ? params.dictID : compliantID;
-MEM_writeLE32((char*)dictBuffer+4, dictID);
-}
-hSize = 8;
-/* entropy tables */
 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,
 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);
+U32 const compliantID = (randomID % ((1U<<31)-32768)) + 32768;
+U32 const dictID = params.dictID ? params.dictID : compliantID;
+MEM_writeLE32((char*)dictBuffer+4, dictID);
+}
 if (hSize + dictContentSize < dictBufferCapacity)
 memmove((char*)dictBuffer + hSize, (char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize);
 return MIN(dictBufferCapacity, hSize+dictContentSize);
 }
-/*! ZDICT_trainFromBuffer_unsafe() :
+/*! 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()
 */
-size_t ZDICT_trainFromBuffer_unsafe(
+size_t ZDICT_trainFromBuffer_unsafe_legacy(
 void* dictBuffer, size_t maxDictSize,
 const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
-ZDICT_params_t params)
+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;
-U32 const notificationLevel = params.notificationLevel;
+U32 const notificationLevel = params.zParams.notificationLevel;
 /* checks */
 if (!dictList) return ERROR(memory_allocation);
-if (maxDictSize <= g_provision_entropySize + g_min_fast_dictContent) { free(dictList); return ERROR(dstSize_tooSmall); }
+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 0; }   /* not enough source to create dictionary */
+if (samplesBuffSize < ZDICT_MIN_SAMPLES_SIZE) { free(dictList); return ERROR(dictionaryCreation_failed); }   /* not enough source to create dictionary */
 /* init */
 ZDICT_initDictItem(dictList);
 /* build dictionary */
-ZDICT_trainBuffer(dictList, dictListSize,
+ZDICT_trainBuffer_legacy(dictList, dictListSize,
 samplesBuffer, samplesBuffSize,
 samplesSizes, nbSamples,
 minRep, notificationLevel);
 /* display best matches */
-if (params.notificationLevel>= 3) {
+if (params.zParams.notificationLevel>= 3) {
 U32 const nb = MIN(25, dictList[0].pos);
 U32 const dictContentSize = ZDICT_dictSize(dictList);
 U32 u;
 DISPLAYLEVEL(3, "\n %u segments found, of total size %u \n", dictList[0].pos-1, dictContentSize);
 DISPLAYLEVEL(3, "list %u best segments \n", nb-1);
 }   }
 /* create dictionary */
 {   U32 dictContentSize = ZDICT_dictSize(dictList);
-if (dictContentSize < targetDictSize/3) {
+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, (U32)maxDictSize);
+if (samplesBuffSize < 10 * targetDictSize)
+DISPLAYLEVEL(2, "!  consider increasing the number of samples (total size : %u MB)\n", (U32)(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 (samplesBuffSize < 10 * targetDictSize)
-DISPLAYLEVEL(2, "!  consider increasing the number of samples (total size : %u MB)\n", (U32)(samplesBuffSize>>20));
 }
 if ((dictContentSize > targetDictSize*3) && (nbSamples > 2*MINRATIO) && (selectivity>1)) {
 U32 proposedSelectivity = selectivity-1;
 while ((nbSamples >> proposedSelectivity) <= MINRATIO) { proposedSelectivity--; }
 DISPLAYLEVEL(2, "!  note : calculated dictionary significantly larger than requested (%u > %u) \n", dictContentSize, (U32)maxDictSize);
 DISPLAYLEVEL(2, "!  consider increasing dictionary size, or produce denser dictionary (-s%u) \n", proposedSelectivity);
-DISPLAYLEVEL(2, "!  always test dictionary efficiency on samples \n");
+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;
 memcpy(ptr, (const char*)samplesBuffer+dictList[u].pos, l);
 }   }
 dictSize = ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, maxDictSize,
 samplesBuffer, samplesSizes, nbSamples,
-params);
+params.zParams);
 }
 /* clean up */
 free(dictList);
 return dictSize;
 }
-/* issue : samplesBuffer need to be followed by a noisy guard band.
+/* ZDICT_trainFromBuffer_legacy() :
-*  work around : duplicate the buffer, and add the noise */
+* issue : samplesBuffer need to be followed by a noisy guard band.
-size_t ZDICT_trainFromBuffer_advanced(void* dictBuffer, size_t dictBufferCapacity,
+* work around : duplicate the buffer, and add the noise */
-const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
+size_t ZDICT_trainFromBuffer_legacy(void* dictBuffer, size_t dictBufferCapacity,
-ZDICT_params_t params)
+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);
 if (sBuffSize < ZDICT_MIN_SAMPLES_SIZE) return 0;   /* not enough content => no dictionary */
 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(
+result =
-dictBuffer, dictBufferCapacity,
+ZDICT_trainFromBuffer_unsafe_legacy(dictBuffer, dictBufferCapacity, newBuff,
-newBuff, samplesSizes, nbSamples,
+samplesSizes, nbSamples, params);
-params);
 free(newBuff);
 return result;
 }
 size_t ZDICT_trainFromBuffer(void* dictBuffer, size_t dictBufferCapacity,
 const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples)
 {
-ZDICT_params_t params;
+ZDICT_cover_params_t params;
+DEBUGLOG(3, "ZDICT_trainFromBuffer");
 memset(&params, 0, sizeof(params));
-return ZDICT_trainFromBuffer_advanced(dictBuffer, dictBufferCapacity,
+params.d = 8;
-samplesBuffer, samplesSizes, nbSamples,
+params.steps = 4;
-params);
+/* Default to level 6 since no compression level information is available */
+params.zParams.compressionLevel = 6;
+#if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=1)
+params.zParams.notificationLevel = ZSTD_DEBUG;
+#endif
+return ZDICT_optimizeTrainFromBuffer_cover(dictBuffer, dictBufferCapacity,
+samplesBuffer, samplesSizes, nbSamples,
+&params);
 }
 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,

changeset 37495	b1fb341d8a61
parent 30895	c32454d69b85
child 40121	73fef626dae3