Project Alice
Loading...
Searching...
No Matches
zdict.c
Go to the documentation of this file.
1/*
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
3 * All rights reserved.
4 *
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
9 */
10
11
12/*-**************************************
13* Tuning parameters
14****************************************/
15#define MINRATIO 4 /* minimum nb of apparition to be selected in dictionary */
16#define ZDICT_MAX_SAMPLES_SIZE (2000U << 20)
17#define ZDICT_MIN_SAMPLES_SIZE (ZDICT_CONTENTSIZE_MIN * MINRATIO)
18
19
20/*-**************************************
21* Compiler Options
22****************************************/
23/* Unix Large Files support (>4GB) */
24#define _FILE_OFFSET_BITS 64
25#if (defined(__sun__) && (!defined(__LP64__))) /* Sun Solaris 32-bits requires specific definitions */
26# ifndef _LARGEFILE_SOURCE
27# define _LARGEFILE_SOURCE
28# endif
29#elif ! defined(__LP64__) /* No point defining Large file for 64 bit */
30# ifndef _LARGEFILE64_SOURCE
31# define _LARGEFILE64_SOURCE
32# endif
33#endif
34
35
36/*-*************************************
37* Dependencies
38***************************************/
39#include <stdlib.h> /* malloc, free */
40#include <string.h> /* memset */
41#include <stdio.h> /* fprintf, fopen, ftello64 */
42#include <time.h> /* clock */
43
44#ifndef ZDICT_STATIC_LINKING_ONLY
45# define ZDICT_STATIC_LINKING_ONLY
46#endif
47
48#include "../common/mem.h" /* read */
49#include "../common/fse.h" /* FSE_normalizeCount, FSE_writeNCount */
50#include "../common/huf.h" /* HUF_buildCTable, HUF_writeCTable */
51#include "../common/zstd_internal.h" /* includes zstd.h */
52#include "../common/xxhash.h" /* XXH64 */
53#include "../compress/zstd_compress_internal.h" /* ZSTD_loadCEntropy() */
54#include "../zdict.h"
55#include "divsufsort.h"
56#include "../common/bits.h" /* ZSTD_NbCommonBytes */
57
58
59/*-*************************************
60* Constants
61***************************************/
62#define KB *(1 <<10)
63#define MB *(1 <<20)
64#define GB *(1U<<30)
65
66#define DICTLISTSIZE_DEFAULT 10000
67
68#define NOISELENGTH 32
69
70static const U32 g_selectivity_default = 9;
71
72
73/*-*************************************
74* Console display
75***************************************/
76#undef DISPLAY
77#define DISPLAY(...) do { fprintf(stderr, __VA_ARGS__); fflush( stderr ); } while (0)
78#undef DISPLAYLEVEL
79#define DISPLAYLEVEL(l, ...) do { if (notificationLevel>=l) { DISPLAY(__VA_ARGS__); } } while (0) /* 0 : no display; 1: errors; 2: default; 3: details; 4: debug */
80
81static clock_t ZDICT_clockSpan(clock_t nPrevious) { return clock() - nPrevious; }
82
83static void ZDICT_printHex(const void* ptr, size_t length)
84{
85 const BYTE* const b = (const BYTE*)ptr;
86 size_t u;
87 for (u=0; u<length; u++) {
88 BYTE c = b[u];
89 if (c<32 || c>126) c = '.'; /* non-printable char */
90 DISPLAY("%c", c);
91 }
92}
93
94
95/*-********************************************************
96* Helper functions
97**********************************************************/
98unsigned ZDICT_isError(size_t errorCode) { return ERR_isError(errorCode); }
99
100const char* ZDICT_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
101
102unsigned ZDICT_getDictID(const void* dictBuffer, size_t dictSize)
103{
104 if (dictSize < 8) return 0;
105 if (MEM_readLE32(dictBuffer) != ZSTD_MAGIC_DICTIONARY) return 0;
106 return MEM_readLE32((const char*)dictBuffer + 4);
107}
108
109size_t ZDICT_getDictHeaderSize(const void* dictBuffer, size_t dictSize)
110{
111 size_t headerSize;
112 if (dictSize <= 8 || MEM_readLE32(dictBuffer) != ZSTD_MAGIC_DICTIONARY) return ERROR(dictionary_corrupted);
113
115 U32* wksp = (U32*)malloc(HUF_WORKSPACE_SIZE);
116 if (!bs || !wksp) {
117 headerSize = ERROR(memory_allocation);
118 } else {
120 headerSize = ZSTD_loadCEntropy(bs, wksp, dictBuffer, dictSize);
121 }
122
123 free(bs);
124 free(wksp);
125 }
126
127 return headerSize;
128}
129
130/*-********************************************************
131* Dictionary training functions
132**********************************************************/
137static size_t ZDICT_count(const void* pIn, const void* pMatch)
138{
139 const char* const pStart = (const char*)pIn;
140 for (;;) {
141 size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
142 if (!diff) {
143 pIn = (const char*)pIn+sizeof(size_t);
144 pMatch = (const char*)pMatch+sizeof(size_t);
145 continue;
146 }
147 pIn = (const char*)pIn+ZSTD_NbCommonBytes(diff);
148 return (size_t)((const char*)pIn - pStart);
149 }
150}
151
152
153typedef struct {
157} dictItem;
158
159static void ZDICT_initDictItem(dictItem* d)
160{
161 d->pos = 1;
162 d->length = 0;
163 d->savings = (U32)(-1);
164}
165
166
167#define LLIMIT 64 /* heuristic determined experimentally */
168#define MINMATCHLENGTH 7 /* heuristic determined experimentally */
169static dictItem ZDICT_analyzePos(
170 BYTE* doneMarks,
171 const int* suffix, U32 start,
172 const void* buffer, U32 minRatio, U32 notificationLevel)
173{
174 U32 lengthList[LLIMIT] = {0};
175 U32 cumulLength[LLIMIT] = {0};
176 U32 savings[LLIMIT] = {0};
177 const BYTE* b = (const BYTE*)buffer;
178 size_t maxLength = LLIMIT;
179 size_t pos = (size_t)suffix[start];
180 U32 end = start;
181 dictItem solution;
182
183 /* init */
184 memset(&solution, 0, sizeof(solution));
185 doneMarks[pos] = 1;
186
187 /* trivial repetition cases */
188 if ( (MEM_read16(b+pos+0) == MEM_read16(b+pos+2))
189 ||(MEM_read16(b+pos+1) == MEM_read16(b+pos+3))
190 ||(MEM_read16(b+pos+2) == MEM_read16(b+pos+4)) ) {
191 /* skip and mark segment */
192 U16 const pattern16 = MEM_read16(b+pos+4);
193 U32 u, patternEnd = 6;
194 while (MEM_read16(b+pos+patternEnd) == pattern16) patternEnd+=2 ;
195 if (b[pos+patternEnd] == b[pos+patternEnd-1]) patternEnd++;
196 for (u=1; u<patternEnd; u++)
197 doneMarks[pos+u] = 1;
198 return solution;
199 }
200
201 /* look forward */
202 { size_t length;
203 do {
204 end++;
205 length = ZDICT_count(b + pos, b + suffix[end]);
206 } while (length >= MINMATCHLENGTH);
207 }
208
209 /* look backward */
210 { size_t length;
211 do {
212 length = ZDICT_count(b + pos, b + *(suffix+start-1));
213 if (length >=MINMATCHLENGTH) start--;
214 } while(length >= MINMATCHLENGTH);
215 }
216
217 /* exit if not found a minimum nb of repetitions */
218 if (end-start < minRatio) {
219 U32 idx;
220 for(idx=start; idx<end; idx++)
221 doneMarks[suffix[idx]] = 1;
222 return solution;
223 }
224
225 { int i;
226 U32 mml;
227 U32 refinedStart = start;
228 U32 refinedEnd = end;
229
230 DISPLAYLEVEL(4, "\n");
231 DISPLAYLEVEL(4, "found %3u matches of length >= %i at pos %7u ", (unsigned)(end-start), MINMATCHLENGTH, (unsigned)pos);
232 DISPLAYLEVEL(4, "\n");
233
234 for (mml = MINMATCHLENGTH ; ; mml++) {
235 BYTE currentChar = 0;
236 U32 currentCount = 0;
237 U32 currentID = refinedStart;
238 U32 id;
239 U32 selectedCount = 0;
240 U32 selectedID = currentID;
241 for (id =refinedStart; id < refinedEnd; id++) {
242 if (b[suffix[id] + mml] != currentChar) {
243 if (currentCount > selectedCount) {
244 selectedCount = currentCount;
245 selectedID = currentID;
246 }
247 currentID = id;
248 currentChar = b[ suffix[id] + mml];
249 currentCount = 0;
250 }
251 currentCount ++;
252 }
253 if (currentCount > selectedCount) { /* for last */
254 selectedCount = currentCount;
255 selectedID = currentID;
256 }
257
258 if (selectedCount < minRatio)
259 break;
260 refinedStart = selectedID;
261 refinedEnd = refinedStart + selectedCount;
262 }
263
264 /* evaluate gain based on new dict */
265 start = refinedStart;
266 pos = suffix[refinedStart];
267 end = start;
268 memset(lengthList, 0, sizeof(lengthList));
269
270 /* look forward */
271 { size_t length;
272 do {
273 end++;
274 length = ZDICT_count(b + pos, b + suffix[end]);
275 if (length >= LLIMIT) length = LLIMIT-1;
276 lengthList[length]++;
277 } while (length >=MINMATCHLENGTH);
278 }
279
280 /* look backward */
281 { size_t length = MINMATCHLENGTH;
282 while ((length >= MINMATCHLENGTH) & (start > 0)) {
283 length = ZDICT_count(b + pos, b + suffix[start - 1]);
284 if (length >= LLIMIT) length = LLIMIT - 1;
285 lengthList[length]++;
286 if (length >= MINMATCHLENGTH) start--;
287 }
288 }
289
290 /* largest useful length */
291 memset(cumulLength, 0, sizeof(cumulLength));
292 cumulLength[maxLength-1] = lengthList[maxLength-1];
293 for (i=(int)(maxLength-2); i>=0; i--)
294 cumulLength[i] = cumulLength[i+1] + lengthList[i];
295
296 for (i=LLIMIT-1; i>=MINMATCHLENGTH; i--) if (cumulLength[i]>=minRatio) break;
297 maxLength = i;
298
299 /* reduce maxLength in case of final into repetitive data */
300 { U32 l = (U32)maxLength;
301 BYTE const c = b[pos + maxLength-1];
302 while (b[pos+l-2]==c) l--;
303 maxLength = l;
304 }
305 if (maxLength < MINMATCHLENGTH) return solution; /* skip : no long-enough solution */
306
307 /* calculate savings */
308 savings[5] = 0;
309 for (i=MINMATCHLENGTH; i<=(int)maxLength; i++)
310 savings[i] = savings[i-1] + (lengthList[i] * (i-3));
311
312 DISPLAYLEVEL(4, "Selected dict at position %u, of length %u : saves %u (ratio: %.2f) \n",
313 (unsigned)pos, (unsigned)maxLength, (unsigned)savings[maxLength], (double)savings[maxLength] / (double)maxLength);
314
315 solution.pos = (U32)pos;
316 solution.length = (U32)maxLength;
317 solution.savings = savings[maxLength];
318
319 /* mark positions done */
320 { U32 id;
321 for (id=start; id<end; id++) {
322 U32 p, pEnd, length;
323 U32 const testedPos = (U32)suffix[id];
324 if (testedPos == pos)
325 length = solution.length;
326 else {
327 length = (U32)ZDICT_count(b+pos, b+testedPos);
328 if (length > solution.length) length = solution.length;
329 }
330 pEnd = (U32)(testedPos + length);
331 for (p=testedPos; p<pEnd; p++)
332 doneMarks[p] = 1;
333 } } }
334
335 return solution;
336}
337
338
339static int isIncluded(const void* in, const void* container, size_t length)
340{
341 const char* const ip = (const char*) in;
342 const char* const into = (const char*) container;
343 size_t u;
344
345 for (u=0; u<length; u++) { /* works because end of buffer is a noisy guard band */
346 if (ip[u] != into[u]) break;
347 }
348
349 return u==length;
350}
351
356static U32 ZDICT_tryMerge(dictItem* table, dictItem elt, U32 eltNbToSkip, const void* buffer)
357{
358 const U32 tableSize = table->pos;
359 const U32 eltEnd = elt.pos + elt.length;
360 const char* const buf = (const char*) buffer;
361
362 /* tail overlap */
363 U32 u; for (u=1; u<tableSize; u++) {
364 if (u==eltNbToSkip) continue;
365 if ((table[u].pos > elt.pos) && (table[u].pos <= eltEnd)) { /* overlap, existing > new */
366 /* append */
367 U32 const addedLength = table[u].pos - elt.pos;
368 table[u].length += addedLength;
369 table[u].pos = elt.pos;
370 table[u].savings += elt.savings * addedLength / elt.length; /* rough approx */
371 table[u].savings += elt.length / 8; /* rough approx bonus */
372 elt = table[u];
373 /* sort : improve rank */
374 while ((u>1) && (table[u-1].savings < elt.savings))
375 table[u] = table[u-1], u--;
376 table[u] = elt;
377 return u;
378 } }
379
380 /* front overlap */
381 for (u=1; u<tableSize; u++) {
382 if (u==eltNbToSkip) continue;
383
384 if ((table[u].pos + table[u].length >= elt.pos) && (table[u].pos < elt.pos)) { /* overlap, existing < new */
385 /* append */
386 int const addedLength = (int)eltEnd - (int)(table[u].pos + table[u].length);
387 table[u].savings += elt.length / 8; /* rough approx bonus */
388 if (addedLength > 0) { /* otherwise, elt fully included into existing */
389 table[u].length += addedLength;
390 table[u].savings += elt.savings * addedLength / elt.length; /* rough approx */
391 }
392 /* sort : improve rank */
393 elt = table[u];
394 while ((u>1) && (table[u-1].savings < elt.savings))
395 table[u] = table[u-1], u--;
396 table[u] = elt;
397 return u;
398 }
399
400 if (MEM_read64(buf + table[u].pos) == MEM_read64(buf + elt.pos + 1)) {
401 if (isIncluded(buf + table[u].pos, buf + elt.pos + 1, table[u].length)) {
402 size_t const addedLength = MAX( (int)elt.length - (int)table[u].length , 1 );
403 table[u].pos = elt.pos;
404 table[u].savings += (U32)(elt.savings * addedLength / elt.length);
405 table[u].length = MIN(elt.length, table[u].length + 1);
406 return u;
407 }
408 }
409 }
410
411 return 0;
412}
413
414
415static void ZDICT_removeDictItem(dictItem* table, U32 id)
416{
417 /* convention : table[0].pos stores nb of elts */
418 U32 const max = table[0].pos;
419 U32 u;
420 if (!id) return; /* protection, should never happen */
421 for (u=id; u<max-1; u++)
422 table[u] = table[u+1];
423 table->pos--;
424}
425
426
427static void ZDICT_insertDictItem(dictItem* table, U32 maxSize, dictItem elt, const void* buffer)
428{
429 /* merge if possible */
430 U32 mergeId = ZDICT_tryMerge(table, elt, 0, buffer);
431 if (mergeId) {
432 U32 newMerge = 1;
433 while (newMerge) {
434 newMerge = ZDICT_tryMerge(table, table[mergeId], mergeId, buffer);
435 if (newMerge) ZDICT_removeDictItem(table, mergeId);
436 mergeId = newMerge;
437 }
438 return;
439 }
440
441 /* insert */
442 { U32 current;
443 U32 nextElt = table->pos;
444 if (nextElt >= maxSize) nextElt = maxSize-1;
445 current = nextElt-1;
446 while (table[current].savings < elt.savings) {
448 current--;
449 }
450 table[current+1] = elt;
451 table->pos = nextElt+1;
452 }
453}
454
455
456static U32 ZDICT_dictSize(const dictItem* dictList)
457{
458 U32 u, dictSize = 0;
459 for (u=1; u<dictList[0].pos; u++)
460 dictSize += dictList[u].length;
461 return dictSize;
462}
463
464
465static size_t ZDICT_trainBuffer_legacy(dictItem* dictList, U32 dictListSize,
466 const void* const buffer, size_t bufferSize, /* buffer must end with noisy guard band */
467 const size_t* fileSizes, unsigned nbFiles,
468 unsigned minRatio, U32 notificationLevel)
469{
470 int* const suffix0 = (int*)malloc((bufferSize+2)*sizeof(*suffix0));
471 int* const suffix = suffix0+1;
472 U32* reverseSuffix = (U32*)malloc((bufferSize)*sizeof(*reverseSuffix));
473 BYTE* doneMarks = (BYTE*)malloc((bufferSize+16)*sizeof(*doneMarks)); /* +16 for overflow security */
474 U32* filePos = (U32*)malloc(nbFiles * sizeof(*filePos));
475 size_t result = 0;
476 clock_t displayClock = 0;
477 clock_t const refreshRate = CLOCKS_PER_SEC * 3 / 10;
478
479# undef DISPLAYUPDATE
480# define DISPLAYUPDATE(l, ...) \
481 do { \
482 if (notificationLevel>=l) { \
483 if (ZDICT_clockSpan(displayClock) > refreshRate) { \
484 displayClock = clock(); \
485 DISPLAY(__VA_ARGS__); \
486 } \
487 if (notificationLevel>=4) fflush(stderr); \
488 } \
489 } while (0)
490
491 /* init */
492 DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
493 if (!suffix0 || !reverseSuffix || !doneMarks || !filePos) {
494 result = ERROR(memory_allocation);
495 goto _cleanup;
496 }
497 if (minRatio < MINRATIO) minRatio = MINRATIO;
498 memset(doneMarks, 0, bufferSize+16);
499
500 /* limit sample set size (divsufsort limitation)*/
501 if (bufferSize > ZDICT_MAX_SAMPLES_SIZE) DISPLAYLEVEL(3, "sample set too large : reduced to %u MB ...\n", (unsigned)(ZDICT_MAX_SAMPLES_SIZE>>20));
502 while (bufferSize > ZDICT_MAX_SAMPLES_SIZE) bufferSize -= fileSizes[--nbFiles];
503
504 /* sort */
505 DISPLAYLEVEL(2, "sorting %u files of total size %u MB ...\n", nbFiles, (unsigned)(bufferSize>>20));
506 { int const divSuftSortResult = divsufsort((const unsigned char*)buffer, suffix, (int)bufferSize, 0);
507 if (divSuftSortResult != 0) { result = ERROR(GENERIC); goto _cleanup; }
508 }
509 suffix[bufferSize] = (int)bufferSize; /* leads into noise */
510 suffix0[0] = (int)bufferSize; /* leads into noise */
511 /* build reverse suffix sort */
512 { size_t pos;
513 for (pos=0; pos < bufferSize; pos++)
514 reverseSuffix[suffix[pos]] = (U32)pos;
515 /* note filePos tracks borders between samples.
516 It's not used at this stage, but planned to become useful in a later update */
517 filePos[0] = 0;
518 for (pos=1; pos<nbFiles; pos++)
519 filePos[pos] = (U32)(filePos[pos-1] + fileSizes[pos-1]);
520 }
521
522 DISPLAYLEVEL(2, "finding patterns ... \n");
523 DISPLAYLEVEL(3, "minimum ratio : %u \n", minRatio);
524
525 { U32 cursor; for (cursor=0; cursor < bufferSize; ) {
526 dictItem solution;
527 if (doneMarks[cursor]) { cursor++; continue; }
528 solution = ZDICT_analyzePos(doneMarks, suffix, reverseSuffix[cursor], buffer, minRatio, notificationLevel);
529 if (solution.length==0) { cursor++; continue; }
530 ZDICT_insertDictItem(dictList, dictListSize, solution, buffer);
531 cursor += solution.length;
532 DISPLAYUPDATE(2, "\r%4.2f %% \r", (double)cursor / (double)bufferSize * 100.0);
533 } }
534
535_cleanup:
536 free(suffix0);
537 free(reverseSuffix);
538 free(doneMarks);
539 free(filePos);
540 return result;
541}
542
543
544static void ZDICT_fillNoise(void* buffer, size_t length)
545{
546 unsigned const prime1 = 2654435761U;
547 unsigned const prime2 = 2246822519U;
548 unsigned acc = prime1;
549 size_t p=0;
550 for (p=0; p<length; p++) {
551 acc *= prime2;
552 ((unsigned char*)buffer)[p] = (unsigned char)(acc >> 21);
553 }
554}
555
556
557typedef struct
558{
559 ZSTD_CDict* dict; /* dictionary */
560 ZSTD_CCtx* zc; /* working context */
561 void* workPlace; /* must be ZSTD_BLOCKSIZE_MAX allocated */
563
564#define MAXREPOFFSET 1024
565
566static void ZDICT_countEStats(EStats_ress_t esr, const ZSTD_parameters* params,
567 unsigned* countLit, unsigned* offsetcodeCount, unsigned* matchlengthCount, unsigned* litlengthCount, U32* repOffsets,
568 const void* src, size_t srcSize,
569 U32 notificationLevel)
570{
571 size_t const blockSizeMax = MIN (ZSTD_BLOCKSIZE_MAX, 1 << params->cParams.windowLog);
572 size_t cSize;
573
574 if (srcSize > blockSizeMax) srcSize = blockSizeMax; /* protection vs large samples */
575 { size_t const errorCode = ZSTD_compressBegin_usingCDict_deprecated(esr.zc, esr.dict);
576 if (ZSTD_isError(errorCode)) { DISPLAYLEVEL(1, "warning : ZSTD_compressBegin_usingCDict failed \n"); return; }
577
578 }
579 cSize = ZSTD_compressBlock_deprecated(esr.zc, esr.workPlace, ZSTD_BLOCKSIZE_MAX, src, srcSize);
580 if (ZSTD_isError(cSize)) { DISPLAYLEVEL(3, "warning : could not compress sample size %u \n", (unsigned)srcSize); return; }
581
582 if (cSize) { /* if == 0; block is not compressible */
583 const seqStore_t* const seqStorePtr = ZSTD_getSeqStore(esr.zc);
584
585 /* literals stats */
586 { const BYTE* bytePtr;
587 for(bytePtr = seqStorePtr->litStart; bytePtr < seqStorePtr->lit; bytePtr++)
588 countLit[*bytePtr]++;
589 }
590
591 /* seqStats */
592 { U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
593 ZSTD_seqToCodes(seqStorePtr);
594
595 { const BYTE* codePtr = seqStorePtr->ofCode;
596 U32 u;
597 for (u=0; u<nbSeq; u++) offsetcodeCount[codePtr[u]]++;
598 }
599
600 { const BYTE* codePtr = seqStorePtr->mlCode;
601 U32 u;
602 for (u=0; u<nbSeq; u++) matchlengthCount[codePtr[u]]++;
603 }
604
605 { const BYTE* codePtr = seqStorePtr->llCode;
606 U32 u;
607 for (u=0; u<nbSeq; u++) litlengthCount[codePtr[u]]++;
608 }
609
610 if (nbSeq >= 2) { /* rep offsets */
611 const seqDef* const seq = seqStorePtr->sequencesStart;
612 U32 offset1 = seq[0].offBase - ZSTD_REP_NUM;
613 U32 offset2 = seq[1].offBase - ZSTD_REP_NUM;
614 if (offset1 >= MAXREPOFFSET) offset1 = 0;
615 if (offset2 >= MAXREPOFFSET) offset2 = 0;
616 repOffsets[offset1] += 3;
617 repOffsets[offset2] += 1;
618 } } }
619}
620
621static size_t ZDICT_totalSampleSize(const size_t* fileSizes, unsigned nbFiles)
622{
623 size_t total=0;
624 unsigned u;
625 for (u=0; u<nbFiles; u++) total += fileSizes[u];
626 return total;
627}
628
629typedef struct { U32 offset; U32 count; } offsetCount_t;
630
631static void ZDICT_insertSortCount(offsetCount_t table[ZSTD_REP_NUM+1], U32 val, U32 count)
632{
633 U32 u;
634 table[ZSTD_REP_NUM].offset = val;
635 table[ZSTD_REP_NUM].count = count;
636 for (u=ZSTD_REP_NUM; u>0; u--) {
637 offsetCount_t tmp;
638 if (table[u-1].count >= table[u].count) break;
639 tmp = table[u-1];
640 table[u-1] = table[u];
641 table[u] = tmp;
642 }
643}
644
645/* ZDICT_flatLit() :
646 * rewrite `countLit` to contain a mostly flat but still compressible distribution of literals.
647 * necessary to avoid generating a non-compressible distribution that HUF_writeCTable() cannot encode.
648 */
649static void ZDICT_flatLit(unsigned* countLit)
650{
651 int u;
652 for (u=1; u<256; u++) countLit[u] = 2;
653 countLit[0] = 4;
654 countLit[253] = 1;
655 countLit[254] = 1;
656}
657
658#define OFFCODE_MAX 30 /* only applicable to first block */
659static size_t ZDICT_analyzeEntropy(void* dstBuffer, size_t maxDstSize,
660 int compressionLevel,
661 const void* srcBuffer, const size_t* fileSizes, unsigned nbFiles,
662 const void* dictBuffer, size_t dictBufferSize,
663 unsigned notificationLevel)
664{
665 unsigned countLit[256];
666 HUF_CREATE_STATIC_CTABLE(hufTable, 255);
667 unsigned offcodeCount[OFFCODE_MAX+1];
668 short offcodeNCount[OFFCODE_MAX+1];
669 U32 offcodeMax = ZSTD_highbit32((U32)(dictBufferSize + 128 KB));
670 unsigned matchLengthCount[MaxML+1];
671 short matchLengthNCount[MaxML+1];
672 unsigned litLengthCount[MaxLL+1];
673 short litLengthNCount[MaxLL+1];
674 U32 repOffset[MAXREPOFFSET];
675 offsetCount_t bestRepOffset[ZSTD_REP_NUM+1];
676 EStats_ress_t esr = { NULL, NULL, NULL };
677 ZSTD_parameters params;
678 U32 u, huffLog = 11, Offlog = OffFSELog, mlLog = MLFSELog, llLog = LLFSELog, total;
679 size_t pos = 0, errorCode;
680 size_t eSize = 0;
681 size_t const totalSrcSize = ZDICT_totalSampleSize(fileSizes, nbFiles);
682 size_t const averageSampleSize = totalSrcSize / (nbFiles + !nbFiles);
683 BYTE* dstPtr = (BYTE*)dstBuffer;
685
686 /* init */
687 DEBUGLOG(4, "ZDICT_analyzeEntropy");
688 if (offcodeMax>OFFCODE_MAX) { eSize = ERROR(dictionaryCreation_failed); goto _cleanup; } /* too large dictionary */
689 for (u=0; u<256; u++) countLit[u] = 1; /* any character must be described */
690 for (u=0; u<=offcodeMax; u++) offcodeCount[u] = 1;
691 for (u=0; u<=MaxML; u++) matchLengthCount[u] = 1;
692 for (u=0; u<=MaxLL; u++) litLengthCount[u] = 1;
693 memset(repOffset, 0, sizeof(repOffset));
694 repOffset[1] = repOffset[4] = repOffset[8] = 1;
695 memset(bestRepOffset, 0, sizeof(bestRepOffset));
696 if (compressionLevel==0) compressionLevel = ZSTD_CLEVEL_DEFAULT;
697 params = ZSTD_getParams(compressionLevel, averageSampleSize, dictBufferSize);
698
699 esr.dict = ZSTD_createCDict_advanced(dictBuffer, dictBufferSize, ZSTD_dlm_byRef, ZSTD_dct_rawContent, params.cParams, ZSTD_defaultCMem);
700 esr.zc = ZSTD_createCCtx();
701 esr.workPlace = malloc(ZSTD_BLOCKSIZE_MAX);
702 if (!esr.dict || !esr.zc || !esr.workPlace) {
703 eSize = ERROR(memory_allocation);
704 DISPLAYLEVEL(1, "Not enough memory \n");
705 goto _cleanup;
706 }
707
708 /* collect stats on all samples */
709 for (u=0; u<nbFiles; u++) {
710 ZDICT_countEStats(esr, &params,
711 countLit, offcodeCount, matchLengthCount, litLengthCount, repOffset,
712 (const char*)srcBuffer + pos, fileSizes[u],
713 notificationLevel);
714 pos += fileSizes[u];
715 }
716
717 if (notificationLevel >= 4) {
718 /* writeStats */
719 DISPLAYLEVEL(4, "Offset Code Frequencies : \n");
720 for (u=0; u<=offcodeMax; u++) {
721 DISPLAYLEVEL(4, "%2u :%7u \n", u, offcodeCount[u]);
722 } }
723
724 /* analyze, build stats, starting with literals */
725 { size_t maxNbBits = HUF_buildCTable_wksp(hufTable, countLit, 255, huffLog, wksp, sizeof(wksp));
726 if (HUF_isError(maxNbBits)) {
727 eSize = maxNbBits;
728 DISPLAYLEVEL(1, " HUF_buildCTable error \n");
729 goto _cleanup;
730 }
731 if (maxNbBits==8) { /* not compressible : will fail on HUF_writeCTable() */
732 DISPLAYLEVEL(2, "warning : pathological dataset : literals are not compressible : samples are noisy or too regular \n");
733 ZDICT_flatLit(countLit); /* replace distribution by a fake "mostly flat but still compressible" distribution, that HUF_writeCTable() can encode */
734 maxNbBits = HUF_buildCTable_wksp(hufTable, countLit, 255, huffLog, wksp, sizeof(wksp));
735 assert(maxNbBits==9);
736 }
737 huffLog = (U32)maxNbBits;
738 }
739
740 /* looking for most common first offsets */
741 { U32 offset;
742 for (offset=1; offset<MAXREPOFFSET; offset++)
743 ZDICT_insertSortCount(bestRepOffset, offset, repOffset[offset]);
744 }
745 /* note : the result of this phase should be used to better appreciate the impact on statistics */
746
747 total=0; for (u=0; u<=offcodeMax; u++) total+=offcodeCount[u];
748 errorCode = FSE_normalizeCount(offcodeNCount, Offlog, offcodeCount, total, offcodeMax, /* useLowProbCount */ 1);
749 if (FSE_isError(errorCode)) {
750 eSize = errorCode;
751 DISPLAYLEVEL(1, "FSE_normalizeCount error with offcodeCount \n");
752 goto _cleanup;
753 }
754 Offlog = (U32)errorCode;
755
756 total=0; for (u=0; u<=MaxML; u++) total+=matchLengthCount[u];
757 errorCode = FSE_normalizeCount(matchLengthNCount, mlLog, matchLengthCount, total, MaxML, /* useLowProbCount */ 1);
758 if (FSE_isError(errorCode)) {
759 eSize = errorCode;
760 DISPLAYLEVEL(1, "FSE_normalizeCount error with matchLengthCount \n");
761 goto _cleanup;
762 }
763 mlLog = (U32)errorCode;
764
765 total=0; for (u=0; u<=MaxLL; u++) total+=litLengthCount[u];
766 errorCode = FSE_normalizeCount(litLengthNCount, llLog, litLengthCount, total, MaxLL, /* useLowProbCount */ 1);
767 if (FSE_isError(errorCode)) {
768 eSize = errorCode;
769 DISPLAYLEVEL(1, "FSE_normalizeCount error with litLengthCount \n");
770 goto _cleanup;
771 }
772 llLog = (U32)errorCode;
773
774 /* write result to buffer */
775 { size_t const hhSize = HUF_writeCTable_wksp(dstPtr, maxDstSize, hufTable, 255, huffLog, wksp, sizeof(wksp));
776 if (HUF_isError(hhSize)) {
777 eSize = hhSize;
778 DISPLAYLEVEL(1, "HUF_writeCTable error \n");
779 goto _cleanup;
780 }
781 dstPtr += hhSize;
782 maxDstSize -= hhSize;
783 eSize += hhSize;
784 }
785
786 { size_t const ohSize = FSE_writeNCount(dstPtr, maxDstSize, offcodeNCount, OFFCODE_MAX, Offlog);
787 if (FSE_isError(ohSize)) {
788 eSize = ohSize;
789 DISPLAYLEVEL(1, "FSE_writeNCount error with offcodeNCount \n");
790 goto _cleanup;
791 }
792 dstPtr += ohSize;
793 maxDstSize -= ohSize;
794 eSize += ohSize;
795 }
796
797 { size_t const mhSize = FSE_writeNCount(dstPtr, maxDstSize, matchLengthNCount, MaxML, mlLog);
798 if (FSE_isError(mhSize)) {
799 eSize = mhSize;
800 DISPLAYLEVEL(1, "FSE_writeNCount error with matchLengthNCount \n");
801 goto _cleanup;
802 }
803 dstPtr += mhSize;
804 maxDstSize -= mhSize;
805 eSize += mhSize;
806 }
807
808 { size_t const lhSize = FSE_writeNCount(dstPtr, maxDstSize, litLengthNCount, MaxLL, llLog);
809 if (FSE_isError(lhSize)) {
810 eSize = lhSize;
811 DISPLAYLEVEL(1, "FSE_writeNCount error with litlengthNCount \n");
812 goto _cleanup;
813 }
814 dstPtr += lhSize;
815 maxDstSize -= lhSize;
816 eSize += lhSize;
817 }
818
819 if (maxDstSize<12) {
820 eSize = ERROR(dstSize_tooSmall);
821 DISPLAYLEVEL(1, "not enough space to write RepOffsets \n");
822 goto _cleanup;
823 }
824# if 0
825 MEM_writeLE32(dstPtr+0, bestRepOffset[0].offset);
826 MEM_writeLE32(dstPtr+4, bestRepOffset[1].offset);
827 MEM_writeLE32(dstPtr+8, bestRepOffset[2].offset);
828#else
829 /* at this stage, we don't use the result of "most common first offset",
830 * as the impact of statistics is not properly evaluated */
831 MEM_writeLE32(dstPtr+0, repStartValue[0]);
832 MEM_writeLE32(dstPtr+4, repStartValue[1]);
833 MEM_writeLE32(dstPtr+8, repStartValue[2]);
834#endif
835 eSize += 12;
836
837_cleanup:
838 ZSTD_freeCDict(esr.dict);
839 ZSTD_freeCCtx(esr.zc);
840 free(esr.workPlace);
841
842 return eSize;
843}
844
845
849static U32 ZDICT_maxRep(U32 const reps[ZSTD_REP_NUM])
850{
851 U32 maxRep = reps[0];
852 int r;
853 for (r = 1; r < ZSTD_REP_NUM; ++r)
854 maxRep = MAX(maxRep, reps[r]);
855 return maxRep;
856}
857
858size_t ZDICT_finalizeDictionary(void* dictBuffer, size_t dictBufferCapacity,
859 const void* customDictContent, size_t dictContentSize,
860 const void* samplesBuffer, const size_t* samplesSizes,
861 unsigned nbSamples, ZDICT_params_t params)
862{
863 size_t hSize;
864#define HBUFFSIZE 256 /* should prove large enough for all entropy headers */
865 BYTE header[HBUFFSIZE];
866 int const compressionLevel = (params.compressionLevel == 0) ? ZSTD_CLEVEL_DEFAULT : params.compressionLevel;
867 U32 const notificationLevel = params.notificationLevel;
868 /* The final dictionary content must be at least as large as the largest repcode */
869 size_t const minContentSize = (size_t)ZDICT_maxRep(repStartValue);
870 size_t paddingSize;
871
872 /* check conditions */
873 DEBUGLOG(4, "ZDICT_finalizeDictionary");
874 if (dictBufferCapacity < dictContentSize) return ERROR(dstSize_tooSmall);
875 if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) return ERROR(dstSize_tooSmall);
876
877 /* dictionary header */
879 { U64 const randomID = XXH64(customDictContent, dictContentSize, 0);
880 U32 const compliantID = (randomID % ((1U<<31)-32768)) + 32768;
881 U32 const dictID = params.dictID ? params.dictID : compliantID;
882 MEM_writeLE32(header+4, dictID);
883 }
884 hSize = 8;
885
886 /* entropy tables */
887 DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
888 DISPLAYLEVEL(2, "statistics ... \n");
889 { size_t const eSize = ZDICT_analyzeEntropy(header+hSize, HBUFFSIZE-hSize,
890 compressionLevel,
891 samplesBuffer, samplesSizes, nbSamples,
892 customDictContent, dictContentSize,
893 notificationLevel);
894 if (ZDICT_isError(eSize)) return eSize;
895 hSize += eSize;
896 }
897
898 /* Shrink the content size if it doesn't fit in the buffer */
899 if (hSize + dictContentSize > dictBufferCapacity) {
900 dictContentSize = dictBufferCapacity - hSize;
901 }
902
903 /* Pad the dictionary content with zeros if it is too small */
904 if (dictContentSize < minContentSize) {
905 RETURN_ERROR_IF(hSize + minContentSize > dictBufferCapacity, dstSize_tooSmall,
906 "dictBufferCapacity too small to fit max repcode");
907 paddingSize = minContentSize - dictContentSize;
908 } else {
909 paddingSize = 0;
910 }
911
912 {
913 size_t const dictSize = hSize + paddingSize + dictContentSize;
914
915 /* The dictionary consists of the header, optional padding, and the content.
916 * The padding comes before the content because the "best" position in the
917 * dictionary is the last byte.
918 */
919 BYTE* const outDictHeader = (BYTE*)dictBuffer;
920 BYTE* const outDictPadding = outDictHeader + hSize;
921 BYTE* const outDictContent = outDictPadding + paddingSize;
922
923 assert(dictSize <= dictBufferCapacity);
924 assert(outDictContent + dictContentSize == (BYTE*)dictBuffer + dictSize);
925
926 /* First copy the customDictContent into its final location.
927 * `customDictContent` and `dictBuffer` may overlap, so we must
928 * do this before any other writes into the output buffer.
929 * Then copy the header & padding into the output buffer.
930 */
931 memmove(outDictContent, customDictContent, dictContentSize);
932 memcpy(outDictHeader, header, hSize);
933 memset(outDictPadding, 0, paddingSize);
934
935 return dictSize;
936 }
937}
938
939
940static size_t ZDICT_addEntropyTablesFromBuffer_advanced(
941 void* dictBuffer, size_t dictContentSize, size_t dictBufferCapacity,
942 const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
943 ZDICT_params_t params)
944{
945 int const compressionLevel = (params.compressionLevel == 0) ? ZSTD_CLEVEL_DEFAULT : params.compressionLevel;
946 U32 const notificationLevel = params.notificationLevel;
947 size_t hSize = 8;
948
949 /* calculate entropy tables */
950 DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
951 DISPLAYLEVEL(2, "statistics ... \n");
952 { size_t const eSize = ZDICT_analyzeEntropy((char*)dictBuffer+hSize, dictBufferCapacity-hSize,
953 compressionLevel,
954 samplesBuffer, samplesSizes, nbSamples,
955 (char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize,
956 notificationLevel);
957 if (ZDICT_isError(eSize)) return eSize;
958 hSize += eSize;
959 }
960
961 /* add dictionary header (after entropy tables) */
963 { U64 const randomID = XXH64((char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize, 0);
964 U32 const compliantID = (randomID % ((1U<<31)-32768)) + 32768;
965 U32 const dictID = params.dictID ? params.dictID : compliantID;
966 MEM_writeLE32((char*)dictBuffer+4, dictID);
967 }
968
969 if (hSize + dictContentSize < dictBufferCapacity)
970 memmove((char*)dictBuffer + hSize, (char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize);
971 return MIN(dictBufferCapacity, hSize+dictContentSize);
972}
973
978static size_t ZDICT_trainFromBuffer_unsafe_legacy(
979 void* dictBuffer, size_t maxDictSize,
980 const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
981 ZDICT_legacy_params_t params)
982{
983 U32 const dictListSize = MAX(MAX(DICTLISTSIZE_DEFAULT, nbSamples), (U32)(maxDictSize/16));
984 dictItem* const dictList = (dictItem*)malloc(dictListSize * sizeof(*dictList));
985 unsigned const selectivity = params.selectivityLevel == 0 ? g_selectivity_default : params.selectivityLevel;
986 unsigned const minRep = (selectivity > 30) ? MINRATIO : nbSamples >> selectivity;
987 size_t const targetDictSize = maxDictSize;
988 size_t const samplesBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples);
989 size_t dictSize = 0;
990 U32 const notificationLevel = params.zParams.notificationLevel;
991
992 /* checks */
993 if (!dictList) return ERROR(memory_allocation);
994 if (maxDictSize < ZDICT_DICTSIZE_MIN) { free(dictList); return ERROR(dstSize_tooSmall); } /* requested dictionary size is too small */
995 if (samplesBuffSize < ZDICT_MIN_SAMPLES_SIZE) { free(dictList); return ERROR(dictionaryCreation_failed); } /* not enough source to create dictionary */
996
997 /* init */
998 ZDICT_initDictItem(dictList);
999
1000 /* build dictionary */
1001 ZDICT_trainBuffer_legacy(dictList, dictListSize,
1002 samplesBuffer, samplesBuffSize,
1003 samplesSizes, nbSamples,
1004 minRep, notificationLevel);
1005
1006 /* display best matches */
1007 if (params.zParams.notificationLevel>= 3) {
1008 unsigned const nb = MIN(25, dictList[0].pos);
1009 unsigned const dictContentSize = ZDICT_dictSize(dictList);
1010 unsigned u;
1011 DISPLAYLEVEL(3, "\n %u segments found, of total size %u \n", (unsigned)dictList[0].pos-1, dictContentSize);
1012 DISPLAYLEVEL(3, "list %u best segments \n", nb-1);
1013 for (u=1; u<nb; u++) {
1014 unsigned const pos = dictList[u].pos;
1015 unsigned const length = dictList[u].length;
1016 U32 const printedLength = MIN(40, length);
1017 if ((pos > samplesBuffSize) || ((pos + length) > samplesBuffSize)) {
1018 free(dictList);
1019 return ERROR(GENERIC); /* should never happen */
1020 }
1021 DISPLAYLEVEL(3, "%3u:%3u bytes at pos %8u, savings %7u bytes |",
1022 u, length, pos, (unsigned)dictList[u].savings);
1023 ZDICT_printHex((const char*)samplesBuffer+pos, printedLength);
1024 DISPLAYLEVEL(3, "| \n");
1025 } }
1026
1027
1028 /* create dictionary */
1029 { unsigned dictContentSize = ZDICT_dictSize(dictList);
1030 if (dictContentSize < ZDICT_CONTENTSIZE_MIN) { free(dictList); return ERROR(dictionaryCreation_failed); } /* dictionary content too small */
1031 if (dictContentSize < targetDictSize/4) {
1032 DISPLAYLEVEL(2, "! warning : selected content significantly smaller than requested (%u < %u) \n", dictContentSize, (unsigned)maxDictSize);
1033 if (samplesBuffSize < 10 * targetDictSize)
1034 DISPLAYLEVEL(2, "! consider increasing the number of samples (total size : %u MB)\n", (unsigned)(samplesBuffSize>>20));
1035 if (minRep > MINRATIO) {
1036 DISPLAYLEVEL(2, "! consider increasing selectivity to produce larger dictionary (-s%u) \n", selectivity+1);
1037 DISPLAYLEVEL(2, "! note : larger dictionaries are not necessarily better, test its efficiency on samples \n");
1038 }
1039 }
1040
1041 if ((dictContentSize > targetDictSize*3) && (nbSamples > 2*MINRATIO) && (selectivity>1)) {
1042 unsigned proposedSelectivity = selectivity-1;
1043 while ((nbSamples >> proposedSelectivity) <= MINRATIO) { proposedSelectivity--; }
1044 DISPLAYLEVEL(2, "! note : calculated dictionary significantly larger than requested (%u > %u) \n", dictContentSize, (unsigned)maxDictSize);
1045 DISPLAYLEVEL(2, "! consider increasing dictionary size, or produce denser dictionary (-s%u) \n", proposedSelectivity);
1046 DISPLAYLEVEL(2, "! always test dictionary efficiency on real samples \n");
1047 }
1048
1049 /* limit dictionary size */
1050 { U32 const max = dictList->pos; /* convention : nb of useful elts within dictList */
1051 U32 currentSize = 0;
1052 U32 n; for (n=1; n<max; n++) {
1053 currentSize += dictList[n].length;
1054 if (currentSize > targetDictSize) { currentSize -= dictList[n].length; break; }
1055 }
1056 dictList->pos = n;
1057 dictContentSize = currentSize;
1058 }
1059
1060 /* build dict content */
1061 { U32 u;
1062 BYTE* ptr = (BYTE*)dictBuffer + maxDictSize;
1063 for (u=1; u<dictList->pos; u++) {
1064 U32 l = dictList[u].length;
1065 ptr -= l;
1066 if (ptr<(BYTE*)dictBuffer) { free(dictList); return ERROR(GENERIC); } /* should not happen */
1067 memcpy(ptr, (const char*)samplesBuffer+dictList[u].pos, l);
1068 } }
1069
1070 dictSize = ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, maxDictSize,
1071 samplesBuffer, samplesSizes, nbSamples,
1072 params.zParams);
1073 }
1074
1075 /* clean up */
1076 free(dictList);
1077 return dictSize;
1078}
1079
1080
1081/* ZDICT_trainFromBuffer_legacy() :
1082 * issue : samplesBuffer need to be followed by a noisy guard band.
1083 * work around : duplicate the buffer, and add the noise */
1084size_t ZDICT_trainFromBuffer_legacy(void* dictBuffer, size_t dictBufferCapacity,
1085 const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
1086 ZDICT_legacy_params_t params)
1087{
1088 size_t result;
1089 void* newBuff;
1090 size_t const sBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples);
1091 if (sBuffSize < ZDICT_MIN_SAMPLES_SIZE) return 0; /* not enough content => no dictionary */
1092
1093 newBuff = malloc(sBuffSize + NOISELENGTH);
1094 if (!newBuff) return ERROR(memory_allocation);
1095
1096 memcpy(newBuff, samplesBuffer, sBuffSize);
1097 ZDICT_fillNoise((char*)newBuff + sBuffSize, NOISELENGTH); /* guard band, for end of buffer condition */
1098
1099 result =
1100 ZDICT_trainFromBuffer_unsafe_legacy(dictBuffer, dictBufferCapacity, newBuff,
1101 samplesSizes, nbSamples, params);
1102 free(newBuff);
1103 return result;
1104}
1105
1106
1107size_t ZDICT_trainFromBuffer(void* dictBuffer, size_t dictBufferCapacity,
1108 const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples)
1109{
1110 ZDICT_fastCover_params_t params;
1111 DEBUGLOG(3, "ZDICT_trainFromBuffer");
1112 memset(&params, 0, sizeof(params));
1113 params.d = 8;
1114 params.steps = 4;
1115 /* Use default level since no compression level information is available */
1116 params.zParams.compressionLevel = ZSTD_CLEVEL_DEFAULT;
1117#if defined(DEBUGLEVEL) && (DEBUGLEVEL>=1)
1118 params.zParams.notificationLevel = DEBUGLEVEL;
1119#endif
1120 return ZDICT_optimizeTrainFromBuffer_fastCover(dictBuffer, dictBufferCapacity,
1121 samplesBuffer, samplesSizes, nbSamples,
1122 &params);
1123}
1124
1125size_t ZDICT_addEntropyTablesFromBuffer(void* dictBuffer, size_t dictContentSize, size_t dictBufferCapacity,
1126 const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples)
1127{
1128 ZDICT_params_t params;
1129 memset(&params, 0, sizeof(params));
1130 return ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, dictBufferCapacity,
1131 samplesBuffer, samplesSizes, nbSamples,
1132 params);
1133}
MEM_STATIC unsigned ZSTD_NbCommonBytes(size_t val)
Definition: bits.h:152
MEM_STATIC unsigned ZSTD_highbit32(U32 val)
Definition: bits.h:169
#define DEBUGLOG(l,...)
Definition: debug.h:108
#define DEBUGLEVEL
Definition: debug.h:50
#define assert(condition)
Definition: debug.h:74
int divsufsort(const unsigned char *T, int *SA, int n, int openMP)
Definition: divsufsort.c:1847
#define ERROR(name)
Definition: error_private.h:55
ERR_STATIC unsigned ERR_isError(size_t code)
Definition: error_private.h:58
#define RETURN_ERROR_IF(cond, err,...)
ERR_STATIC const char * ERR_getErrorName(size_t code)
Definition: error_private.h:78
ZDICTLIB_STATIC_API size_t ZDICT_optimizeTrainFromBuffer_fastCover(void *dictBuffer, size_t dictBufferCapacity, const void *samplesBuffer, const size_t *samplesSizes, unsigned nbSamples, ZDICT_fastCover_params_t *parameters)
Definition: fastcover.c:618
FSE_PUBLIC_API size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:330
FSE_PUBLIC_API size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t srcSize, unsigned maxSymbolValue, unsigned useLowProbCount)
Definition: fse_compress.c:465
#define FSE_isError
#define XXH64
Definition: xxhash.h:460
#define HUF_CTABLE_WORKSPACE_SIZE_U32
Definition: huf.h:166
size_t HUF_writeCTable_wksp(void *dst, size_t maxDstSize, const HUF_CElt *CTable, unsigned maxSymbolValue, unsigned huffLog, void *workspace, size_t workspaceSize)
Definition: huf_compress.c:248
#define HUF_WORKSPACE_SIZE
Definition: huf.h:38
#define HUF_CREATE_STATIC_CTABLE(name, maxSymbolValue)
Definition: huf.h:65
size_t HUF_buildCTable_wksp(HUF_CElt *tree, const unsigned *count, U32 maxSymbolValue, U32 maxNbBits, void *workSpace, size_t wkspSize)
Definition: huf_compress.c:756
unsigned long long U64
Definition: mem.h:73
MEM_STATIC U16 MEM_read16(const void *memPtr)
Definition: mem.h:197
MEM_STATIC size_t MEM_readST(const void *memPtr)
Definition: mem.h:212
unsigned char BYTE
Definition: mem.h:58
MEM_STATIC void MEM_writeLE32(void *memPtr, U32 val32)
Definition: mem.h:328
unsigned int U32
Definition: mem.h:69
unsigned short U16
Definition: mem.h:64
MEM_STATIC U32 MEM_readLE32(const void *memPtr)
Definition: mem.h:320
MEM_STATIC U64 MEM_read64(const void *memPtr)
Definition: mem.h:207
constexpr dcon::demographics_key total(0)
Definition: table.hpp:10
#define MIN(a, b)
#define MAX(a, b)
ZSTD_CCtx * zc
Definition: zdict.c:560
ZSTD_CDict * dict
Definition: zdict.c:559
void * workPlace
Definition: zdict.c:561
int compressionLevel
Definition: zdict.h:215
unsigned dictID
Definition: zdict.h:217
unsigned notificationLevel
Definition: zdict.h:216
U32 length
Definition: zdict.c:155
U32 pos
Definition: zdict.c:154
U32 savings
Definition: zdict.c:156
U32 count
Definition: zdict.c:629
BYTE * litStart
BYTE * ofCode
BYTE * llCode
seqDef * sequencesStart
BYTE * mlCode
seqDef * sequences
size_t ZDICT_trainFromBuffer_legacy(void *dictBuffer, size_t dictBufferCapacity, const void *samplesBuffer, const size_t *samplesSizes, unsigned nbSamples, ZDICT_legacy_params_t params)
Definition: zdict.c:1084
#define HBUFFSIZE
#define ZDICT_MAX_SAMPLES_SIZE
Definition: zdict.c:16
#define KB
Definition: zdict.c:62
#define DISPLAYUPDATE(l,...)
#define DISPLAY(...)
Definition: zdict.c:77
#define MINMATCHLENGTH
Definition: zdict.c:168
unsigned ZDICT_getDictID(const void *dictBuffer, size_t dictSize)
Definition: zdict.c:102
size_t ZDICT_trainFromBuffer(void *dictBuffer, size_t dictBufferCapacity, const void *samplesBuffer, const size_t *samplesSizes, unsigned nbSamples)
Definition: zdict.c:1107
#define LLIMIT
Definition: zdict.c:167
#define DISPLAYLEVEL(l,...)
Definition: zdict.c:79
#define NOISELENGTH
Definition: zdict.c:68
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)
Definition: zdict.c:858
const char * ZDICT_getErrorName(size_t errorCode)
Definition: zdict.c:100
#define OFFCODE_MAX
Definition: zdict.c:658
#define MINRATIO
Definition: zdict.c:15
#define MAXREPOFFSET
Definition: zdict.c:564
size_t ZDICT_addEntropyTablesFromBuffer(void *dictBuffer, size_t dictContentSize, size_t dictBufferCapacity, const void *samplesBuffer, const size_t *samplesSizes, unsigned nbSamples)
Definition: zdict.c:1125
unsigned ZDICT_isError(size_t errorCode)
Definition: zdict.c:98
size_t ZDICT_getDictHeaderSize(const void *dictBuffer, size_t dictSize)
Definition: zdict.c:109
#define ZDICT_MIN_SAMPLES_SIZE
Definition: zdict.c:17
#define DICTLISTSIZE_DEFAULT
Definition: zdict.c:66
#define ZSTD_MAGIC_DICTIONARY
Definition: zstd.h:138
#define ZSTD_CLEVEL_DEFAULT
Definition: zstd.h:129
#define ZSTD_BLOCKSIZE_MAX
Definition: zstd.h:143
ZSTD_CCtx * ZSTD_createCCtx(void)
Definition: zstd_compress.c:96
size_t ZSTD_freeCCtx(ZSTD_CCtx *cctx)
size_t ZSTD_compressBlock_deprecated(ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
size_t ZSTD_loadCEntropy(ZSTD_compressedBlockState_t *bs, void *workspace, const void *const dict, size_t dictSize)
size_t ZSTD_freeCDict(ZSTD_CDict *cdict)
size_t ZSTD_compressBegin_usingCDict_deprecated(ZSTD_CCtx *cctx, const ZSTD_CDict *cdict)
void ZSTD_reset_compressedBlockState(ZSTD_compressedBlockState_t *bs)
ZSTD_CDict * ZSTD_createCDict_advanced(const void *dictBuffer, size_t dictSize, ZSTD_dictLoadMethod_e dictLoadMethod, ZSTD_dictContentType_e dictContentType, ZSTD_compressionParameters cParams, ZSTD_customMem customMem)
ZSTD_parameters ZSTD_getParams(int compressionLevel, unsigned long long srcSizeHint, size_t dictSize)
#define MaxLL
int ZSTD_seqToCodes(const seqStore_t *seqStorePtr)
#define MaxML
#define ZSTD_isError
Definition: zstd_internal.h:48
#define MLFSELog
#define LLFSELog
#define HUF_isError
Definition: zstd_internal.h:50
const seqStore_t * ZSTD_getSeqStore(const ZSTD_CCtx *ctx)
#define ZSTD_REP_NUM
Definition: zstd_internal.h:68
#define OffFSELog