648db22b |
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 | |
70 | static const U32 g_selectivity_default = 9; |
71 | |
72 | |
73 | /*-************************************* |
74 | * Console display |
75 | ***************************************/ |
76 | #undef DISPLAY |
77 | #define DISPLAY(...) { fprintf(stderr, __VA_ARGS__); fflush( stderr ); } |
78 | #undef DISPLAYLEVEL |
79 | #define DISPLAYLEVEL(l, ...) if (notificationLevel>=l) { DISPLAY(__VA_ARGS__); } /* 0 : no display; 1: errors; 2: default; 3: details; 4: debug */ |
80 | |
81 | static clock_t ZDICT_clockSpan(clock_t nPrevious) { return clock() - nPrevious; } |
82 | |
83 | static 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 | **********************************************************/ |
98 | unsigned ZDICT_isError(size_t errorCode) { return ERR_isError(errorCode); } |
99 | |
100 | const char* ZDICT_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); } |
101 | |
102 | unsigned 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 | |
109 | size_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 | |
114 | { ZSTD_compressedBlockState_t* bs = (ZSTD_compressedBlockState_t*)malloc(sizeof(ZSTD_compressedBlockState_t)); |
115 | U32* wksp = (U32*)malloc(HUF_WORKSPACE_SIZE); |
116 | if (!bs || !wksp) { |
117 | headerSize = ERROR(memory_allocation); |
118 | } else { |
119 | ZSTD_reset_compressedBlockState(bs); |
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 | **********************************************************/ |
133 | /*! ZDICT_count() : |
134 | Count the nb of common bytes between 2 pointers. |
135 | Note : this function presumes end of buffer followed by noisy guard band. |
136 | */ |
137 | static 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 | |
153 | typedef struct { |
154 | U32 pos; |
155 | U32 length; |
156 | U32 savings; |
157 | } dictItem; |
158 | |
159 | static 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 */ |
169 | static 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 | |
339 | static 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 | |
352 | /*! ZDICT_tryMerge() : |
353 | check if dictItem can be merged, do it if possible |
354 | @return : id of destination elt, 0 if not merged |
355 | */ |
356 | static 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 | |
415 | static 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 | |
427 | static 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) { |
447 | table[current+1] = table[current]; |
448 | current--; |
449 | } |
450 | table[current+1] = elt; |
451 | table->pos = nextElt+1; |
452 | } |
453 | } |
454 | |
455 | |
456 | static 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 | |
465 | static 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, ...) if (notificationLevel>=l) { \ |
481 | if (ZDICT_clockSpan(displayClock) > refreshRate) \ |
482 | { displayClock = clock(); DISPLAY(__VA_ARGS__); \ |
483 | if (notificationLevel>=4) fflush(stderr); } } |
484 | |
485 | /* init */ |
486 | DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */ |
487 | if (!suffix0 || !reverseSuffix || !doneMarks || !filePos) { |
488 | result = ERROR(memory_allocation); |
489 | goto _cleanup; |
490 | } |
491 | if (minRatio < MINRATIO) minRatio = MINRATIO; |
492 | memset(doneMarks, 0, bufferSize+16); |
493 | |
494 | /* limit sample set size (divsufsort limitation)*/ |
495 | if (bufferSize > ZDICT_MAX_SAMPLES_SIZE) DISPLAYLEVEL(3, "sample set too large : reduced to %u MB ...\n", (unsigned)(ZDICT_MAX_SAMPLES_SIZE>>20)); |
496 | while (bufferSize > ZDICT_MAX_SAMPLES_SIZE) bufferSize -= fileSizes[--nbFiles]; |
497 | |
498 | /* sort */ |
499 | DISPLAYLEVEL(2, "sorting %u files of total size %u MB ...\n", nbFiles, (unsigned)(bufferSize>>20)); |
500 | { int const divSuftSortResult = divsufsort((const unsigned char*)buffer, suffix, (int)bufferSize, 0); |
501 | if (divSuftSortResult != 0) { result = ERROR(GENERIC); goto _cleanup; } |
502 | } |
503 | suffix[bufferSize] = (int)bufferSize; /* leads into noise */ |
504 | suffix0[0] = (int)bufferSize; /* leads into noise */ |
505 | /* build reverse suffix sort */ |
506 | { size_t pos; |
507 | for (pos=0; pos < bufferSize; pos++) |
508 | reverseSuffix[suffix[pos]] = (U32)pos; |
509 | /* note filePos tracks borders between samples. |
510 | It's not used at this stage, but planned to become useful in a later update */ |
511 | filePos[0] = 0; |
512 | for (pos=1; pos<nbFiles; pos++) |
513 | filePos[pos] = (U32)(filePos[pos-1] + fileSizes[pos-1]); |
514 | } |
515 | |
516 | DISPLAYLEVEL(2, "finding patterns ... \n"); |
517 | DISPLAYLEVEL(3, "minimum ratio : %u \n", minRatio); |
518 | |
519 | { U32 cursor; for (cursor=0; cursor < bufferSize; ) { |
520 | dictItem solution; |
521 | if (doneMarks[cursor]) { cursor++; continue; } |
522 | solution = ZDICT_analyzePos(doneMarks, suffix, reverseSuffix[cursor], buffer, minRatio, notificationLevel); |
523 | if (solution.length==0) { cursor++; continue; } |
524 | ZDICT_insertDictItem(dictList, dictListSize, solution, buffer); |
525 | cursor += solution.length; |
526 | DISPLAYUPDATE(2, "\r%4.2f %% \r", (double)cursor / (double)bufferSize * 100.0); |
527 | } } |
528 | |
529 | _cleanup: |
530 | free(suffix0); |
531 | free(reverseSuffix); |
532 | free(doneMarks); |
533 | free(filePos); |
534 | return result; |
535 | } |
536 | |
537 | |
538 | static void ZDICT_fillNoise(void* buffer, size_t length) |
539 | { |
540 | unsigned const prime1 = 2654435761U; |
541 | unsigned const prime2 = 2246822519U; |
542 | unsigned acc = prime1; |
543 | size_t p=0; |
544 | for (p=0; p<length; p++) { |
545 | acc *= prime2; |
546 | ((unsigned char*)buffer)[p] = (unsigned char)(acc >> 21); |
547 | } |
548 | } |
549 | |
550 | |
551 | typedef struct |
552 | { |
553 | ZSTD_CDict* dict; /* dictionary */ |
554 | ZSTD_CCtx* zc; /* working context */ |
555 | void* workPlace; /* must be ZSTD_BLOCKSIZE_MAX allocated */ |
556 | } EStats_ress_t; |
557 | |
558 | #define MAXREPOFFSET 1024 |
559 | |
560 | static void ZDICT_countEStats(EStats_ress_t esr, const ZSTD_parameters* params, |
561 | unsigned* countLit, unsigned* offsetcodeCount, unsigned* matchlengthCount, unsigned* litlengthCount, U32* repOffsets, |
562 | const void* src, size_t srcSize, |
563 | U32 notificationLevel) |
564 | { |
565 | size_t const blockSizeMax = MIN (ZSTD_BLOCKSIZE_MAX, 1 << params->cParams.windowLog); |
566 | size_t cSize; |
567 | |
568 | if (srcSize > blockSizeMax) srcSize = blockSizeMax; /* protection vs large samples */ |
569 | { size_t const errorCode = ZSTD_compressBegin_usingCDict_deprecated(esr.zc, esr.dict); |
570 | if (ZSTD_isError(errorCode)) { DISPLAYLEVEL(1, "warning : ZSTD_compressBegin_usingCDict failed \n"); return; } |
571 | |
572 | } |
573 | cSize = ZSTD_compressBlock_deprecated(esr.zc, esr.workPlace, ZSTD_BLOCKSIZE_MAX, src, srcSize); |
574 | if (ZSTD_isError(cSize)) { DISPLAYLEVEL(3, "warning : could not compress sample size %u \n", (unsigned)srcSize); return; } |
575 | |
576 | if (cSize) { /* if == 0; block is not compressible */ |
577 | const seqStore_t* const seqStorePtr = ZSTD_getSeqStore(esr.zc); |
578 | |
579 | /* literals stats */ |
580 | { const BYTE* bytePtr; |
581 | for(bytePtr = seqStorePtr->litStart; bytePtr < seqStorePtr->lit; bytePtr++) |
582 | countLit[*bytePtr]++; |
583 | } |
584 | |
585 | /* seqStats */ |
586 | { U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); |
587 | ZSTD_seqToCodes(seqStorePtr); |
588 | |
589 | { const BYTE* codePtr = seqStorePtr->ofCode; |
590 | U32 u; |
591 | for (u=0; u<nbSeq; u++) offsetcodeCount[codePtr[u]]++; |
592 | } |
593 | |
594 | { const BYTE* codePtr = seqStorePtr->mlCode; |
595 | U32 u; |
596 | for (u=0; u<nbSeq; u++) matchlengthCount[codePtr[u]]++; |
597 | } |
598 | |
599 | { const BYTE* codePtr = seqStorePtr->llCode; |
600 | U32 u; |
601 | for (u=0; u<nbSeq; u++) litlengthCount[codePtr[u]]++; |
602 | } |
603 | |
604 | if (nbSeq >= 2) { /* rep offsets */ |
605 | const seqDef* const seq = seqStorePtr->sequencesStart; |
606 | U32 offset1 = seq[0].offBase - ZSTD_REP_NUM; |
607 | U32 offset2 = seq[1].offBase - ZSTD_REP_NUM; |
608 | if (offset1 >= MAXREPOFFSET) offset1 = 0; |
609 | if (offset2 >= MAXREPOFFSET) offset2 = 0; |
610 | repOffsets[offset1] += 3; |
611 | repOffsets[offset2] += 1; |
612 | } } } |
613 | } |
614 | |
615 | static size_t ZDICT_totalSampleSize(const size_t* fileSizes, unsigned nbFiles) |
616 | { |
617 | size_t total=0; |
618 | unsigned u; |
619 | for (u=0; u<nbFiles; u++) total += fileSizes[u]; |
620 | return total; |
621 | } |
622 | |
623 | typedef struct { U32 offset; U32 count; } offsetCount_t; |
624 | |
625 | static void ZDICT_insertSortCount(offsetCount_t table[ZSTD_REP_NUM+1], U32 val, U32 count) |
626 | { |
627 | U32 u; |
628 | table[ZSTD_REP_NUM].offset = val; |
629 | table[ZSTD_REP_NUM].count = count; |
630 | for (u=ZSTD_REP_NUM; u>0; u--) { |
631 | offsetCount_t tmp; |
632 | if (table[u-1].count >= table[u].count) break; |
633 | tmp = table[u-1]; |
634 | table[u-1] = table[u]; |
635 | table[u] = tmp; |
636 | } |
637 | } |
638 | |
639 | /* ZDICT_flatLit() : |
640 | * rewrite `countLit` to contain a mostly flat but still compressible distribution of literals. |
641 | * necessary to avoid generating a non-compressible distribution that HUF_writeCTable() cannot encode. |
642 | */ |
643 | static void ZDICT_flatLit(unsigned* countLit) |
644 | { |
645 | int u; |
646 | for (u=1; u<256; u++) countLit[u] = 2; |
647 | countLit[0] = 4; |
648 | countLit[253] = 1; |
649 | countLit[254] = 1; |
650 | } |
651 | |
652 | #define OFFCODE_MAX 30 /* only applicable to first block */ |
653 | static size_t ZDICT_analyzeEntropy(void* dstBuffer, size_t maxDstSize, |
654 | int compressionLevel, |
655 | const void* srcBuffer, const size_t* fileSizes, unsigned nbFiles, |
656 | const void* dictBuffer, size_t dictBufferSize, |
657 | unsigned notificationLevel) |
658 | { |
659 | unsigned countLit[256]; |
660 | HUF_CREATE_STATIC_CTABLE(hufTable, 255); |
661 | unsigned offcodeCount[OFFCODE_MAX+1]; |
662 | short offcodeNCount[OFFCODE_MAX+1]; |
663 | U32 offcodeMax = ZSTD_highbit32((U32)(dictBufferSize + 128 KB)); |
664 | unsigned matchLengthCount[MaxML+1]; |
665 | short matchLengthNCount[MaxML+1]; |
666 | unsigned litLengthCount[MaxLL+1]; |
667 | short litLengthNCount[MaxLL+1]; |
668 | U32 repOffset[MAXREPOFFSET]; |
669 | offsetCount_t bestRepOffset[ZSTD_REP_NUM+1]; |
670 | EStats_ress_t esr = { NULL, NULL, NULL }; |
671 | ZSTD_parameters params; |
672 | U32 u, huffLog = 11, Offlog = OffFSELog, mlLog = MLFSELog, llLog = LLFSELog, total; |
673 | size_t pos = 0, errorCode; |
674 | size_t eSize = 0; |
675 | size_t const totalSrcSize = ZDICT_totalSampleSize(fileSizes, nbFiles); |
676 | size_t const averageSampleSize = totalSrcSize / (nbFiles + !nbFiles); |
677 | BYTE* dstPtr = (BYTE*)dstBuffer; |
678 | U32 wksp[HUF_CTABLE_WORKSPACE_SIZE_U32]; |
679 | |
680 | /* init */ |
681 | DEBUGLOG(4, "ZDICT_analyzeEntropy"); |
682 | if (offcodeMax>OFFCODE_MAX) { eSize = ERROR(dictionaryCreation_failed); goto _cleanup; } /* too large dictionary */ |
683 | for (u=0; u<256; u++) countLit[u] = 1; /* any character must be described */ |
684 | for (u=0; u<=offcodeMax; u++) offcodeCount[u] = 1; |
685 | for (u=0; u<=MaxML; u++) matchLengthCount[u] = 1; |
686 | for (u=0; u<=MaxLL; u++) litLengthCount[u] = 1; |
687 | memset(repOffset, 0, sizeof(repOffset)); |
688 | repOffset[1] = repOffset[4] = repOffset[8] = 1; |
689 | memset(bestRepOffset, 0, sizeof(bestRepOffset)); |
690 | if (compressionLevel==0) compressionLevel = ZSTD_CLEVEL_DEFAULT; |
691 | params = ZSTD_getParams(compressionLevel, averageSampleSize, dictBufferSize); |
692 | |
693 | esr.dict = ZSTD_createCDict_advanced(dictBuffer, dictBufferSize, ZSTD_dlm_byRef, ZSTD_dct_rawContent, params.cParams, ZSTD_defaultCMem); |
694 | esr.zc = ZSTD_createCCtx(); |
695 | esr.workPlace = malloc(ZSTD_BLOCKSIZE_MAX); |
696 | if (!esr.dict || !esr.zc || !esr.workPlace) { |
697 | eSize = ERROR(memory_allocation); |
698 | DISPLAYLEVEL(1, "Not enough memory \n"); |
699 | goto _cleanup; |
700 | } |
701 | |
702 | /* collect stats on all samples */ |
703 | for (u=0; u<nbFiles; u++) { |
704 | ZDICT_countEStats(esr, ¶ms, |
705 | countLit, offcodeCount, matchLengthCount, litLengthCount, repOffset, |
706 | (const char*)srcBuffer + pos, fileSizes[u], |
707 | notificationLevel); |
708 | pos += fileSizes[u]; |
709 | } |
710 | |
711 | if (notificationLevel >= 4) { |
712 | /* writeStats */ |
713 | DISPLAYLEVEL(4, "Offset Code Frequencies : \n"); |
714 | for (u=0; u<=offcodeMax; u++) { |
715 | DISPLAYLEVEL(4, "%2u :%7u \n", u, offcodeCount[u]); |
716 | } } |
717 | |
718 | /* analyze, build stats, starting with literals */ |
719 | { size_t maxNbBits = HUF_buildCTable_wksp(hufTable, countLit, 255, huffLog, wksp, sizeof(wksp)); |
720 | if (HUF_isError(maxNbBits)) { |
721 | eSize = maxNbBits; |
722 | DISPLAYLEVEL(1, " HUF_buildCTable error \n"); |
723 | goto _cleanup; |
724 | } |
725 | if (maxNbBits==8) { /* not compressible : will fail on HUF_writeCTable() */ |
726 | DISPLAYLEVEL(2, "warning : pathological dataset : literals are not compressible : samples are noisy or too regular \n"); |
727 | ZDICT_flatLit(countLit); /* replace distribution by a fake "mostly flat but still compressible" distribution, that HUF_writeCTable() can encode */ |
728 | maxNbBits = HUF_buildCTable_wksp(hufTable, countLit, 255, huffLog, wksp, sizeof(wksp)); |
729 | assert(maxNbBits==9); |
730 | } |
731 | huffLog = (U32)maxNbBits; |
732 | } |
733 | |
734 | /* looking for most common first offsets */ |
735 | { U32 offset; |
736 | for (offset=1; offset<MAXREPOFFSET; offset++) |
737 | ZDICT_insertSortCount(bestRepOffset, offset, repOffset[offset]); |
738 | } |
739 | /* note : the result of this phase should be used to better appreciate the impact on statistics */ |
740 | |
741 | total=0; for (u=0; u<=offcodeMax; u++) total+=offcodeCount[u]; |
742 | errorCode = FSE_normalizeCount(offcodeNCount, Offlog, offcodeCount, total, offcodeMax, /* useLowProbCount */ 1); |
743 | if (FSE_isError(errorCode)) { |
744 | eSize = errorCode; |
745 | DISPLAYLEVEL(1, "FSE_normalizeCount error with offcodeCount \n"); |
746 | goto _cleanup; |
747 | } |
748 | Offlog = (U32)errorCode; |
749 | |
750 | total=0; for (u=0; u<=MaxML; u++) total+=matchLengthCount[u]; |
751 | errorCode = FSE_normalizeCount(matchLengthNCount, mlLog, matchLengthCount, total, MaxML, /* useLowProbCount */ 1); |
752 | if (FSE_isError(errorCode)) { |
753 | eSize = errorCode; |
754 | DISPLAYLEVEL(1, "FSE_normalizeCount error with matchLengthCount \n"); |
755 | goto _cleanup; |
756 | } |
757 | mlLog = (U32)errorCode; |
758 | |
759 | total=0; for (u=0; u<=MaxLL; u++) total+=litLengthCount[u]; |
760 | errorCode = FSE_normalizeCount(litLengthNCount, llLog, litLengthCount, total, MaxLL, /* useLowProbCount */ 1); |
761 | if (FSE_isError(errorCode)) { |
762 | eSize = errorCode; |
763 | DISPLAYLEVEL(1, "FSE_normalizeCount error with litLengthCount \n"); |
764 | goto _cleanup; |
765 | } |
766 | llLog = (U32)errorCode; |
767 | |
768 | /* write result to buffer */ |
769 | { size_t const hhSize = HUF_writeCTable_wksp(dstPtr, maxDstSize, hufTable, 255, huffLog, wksp, sizeof(wksp)); |
770 | if (HUF_isError(hhSize)) { |
771 | eSize = hhSize; |
772 | DISPLAYLEVEL(1, "HUF_writeCTable error \n"); |
773 | goto _cleanup; |
774 | } |
775 | dstPtr += hhSize; |
776 | maxDstSize -= hhSize; |
777 | eSize += hhSize; |
778 | } |
779 | |
780 | { size_t const ohSize = FSE_writeNCount(dstPtr, maxDstSize, offcodeNCount, OFFCODE_MAX, Offlog); |
781 | if (FSE_isError(ohSize)) { |
782 | eSize = ohSize; |
783 | DISPLAYLEVEL(1, "FSE_writeNCount error with offcodeNCount \n"); |
784 | goto _cleanup; |
785 | } |
786 | dstPtr += ohSize; |
787 | maxDstSize -= ohSize; |
788 | eSize += ohSize; |
789 | } |
790 | |
791 | { size_t const mhSize = FSE_writeNCount(dstPtr, maxDstSize, matchLengthNCount, MaxML, mlLog); |
792 | if (FSE_isError(mhSize)) { |
793 | eSize = mhSize; |
794 | DISPLAYLEVEL(1, "FSE_writeNCount error with matchLengthNCount \n"); |
795 | goto _cleanup; |
796 | } |
797 | dstPtr += mhSize; |
798 | maxDstSize -= mhSize; |
799 | eSize += mhSize; |
800 | } |
801 | |
802 | { size_t const lhSize = FSE_writeNCount(dstPtr, maxDstSize, litLengthNCount, MaxLL, llLog); |
803 | if (FSE_isError(lhSize)) { |
804 | eSize = lhSize; |
805 | DISPLAYLEVEL(1, "FSE_writeNCount error with litlengthNCount \n"); |
806 | goto _cleanup; |
807 | } |
808 | dstPtr += lhSize; |
809 | maxDstSize -= lhSize; |
810 | eSize += lhSize; |
811 | } |
812 | |
813 | if (maxDstSize<12) { |
814 | eSize = ERROR(dstSize_tooSmall); |
815 | DISPLAYLEVEL(1, "not enough space to write RepOffsets \n"); |
816 | goto _cleanup; |
817 | } |
818 | # if 0 |
819 | MEM_writeLE32(dstPtr+0, bestRepOffset[0].offset); |
820 | MEM_writeLE32(dstPtr+4, bestRepOffset[1].offset); |
821 | MEM_writeLE32(dstPtr+8, bestRepOffset[2].offset); |
822 | #else |
823 | /* at this stage, we don't use the result of "most common first offset", |
824 | * as the impact of statistics is not properly evaluated */ |
825 | MEM_writeLE32(dstPtr+0, repStartValue[0]); |
826 | MEM_writeLE32(dstPtr+4, repStartValue[1]); |
827 | MEM_writeLE32(dstPtr+8, repStartValue[2]); |
828 | #endif |
829 | eSize += 12; |
830 | |
831 | _cleanup: |
832 | ZSTD_freeCDict(esr.dict); |
833 | ZSTD_freeCCtx(esr.zc); |
834 | free(esr.workPlace); |
835 | |
836 | return eSize; |
837 | } |
838 | |
839 | |
840 | /** |
841 | * @returns the maximum repcode value |
842 | */ |
843 | static U32 ZDICT_maxRep(U32 const reps[ZSTD_REP_NUM]) |
844 | { |
845 | U32 maxRep = reps[0]; |
846 | int r; |
847 | for (r = 1; r < ZSTD_REP_NUM; ++r) |
848 | maxRep = MAX(maxRep, reps[r]); |
849 | return maxRep; |
850 | } |
851 | |
852 | size_t ZDICT_finalizeDictionary(void* dictBuffer, size_t dictBufferCapacity, |
853 | const void* customDictContent, size_t dictContentSize, |
854 | const void* samplesBuffer, const size_t* samplesSizes, |
855 | unsigned nbSamples, ZDICT_params_t params) |
856 | { |
857 | size_t hSize; |
858 | #define HBUFFSIZE 256 /* should prove large enough for all entropy headers */ |
859 | BYTE header[HBUFFSIZE]; |
860 | int const compressionLevel = (params.compressionLevel == 0) ? ZSTD_CLEVEL_DEFAULT : params.compressionLevel; |
861 | U32 const notificationLevel = params.notificationLevel; |
862 | /* The final dictionary content must be at least as large as the largest repcode */ |
863 | size_t const minContentSize = (size_t)ZDICT_maxRep(repStartValue); |
864 | size_t paddingSize; |
865 | |
866 | /* check conditions */ |
867 | DEBUGLOG(4, "ZDICT_finalizeDictionary"); |
868 | if (dictBufferCapacity < dictContentSize) return ERROR(dstSize_tooSmall); |
869 | if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) return ERROR(dstSize_tooSmall); |
870 | |
871 | /* dictionary header */ |
872 | MEM_writeLE32(header, ZSTD_MAGIC_DICTIONARY); |
873 | { U64 const randomID = XXH64(customDictContent, dictContentSize, 0); |
874 | U32 const compliantID = (randomID % ((1U<<31)-32768)) + 32768; |
875 | U32 const dictID = params.dictID ? params.dictID : compliantID; |
876 | MEM_writeLE32(header+4, dictID); |
877 | } |
878 | hSize = 8; |
879 | |
880 | /* entropy tables */ |
881 | DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */ |
882 | DISPLAYLEVEL(2, "statistics ... \n"); |
883 | { size_t const eSize = ZDICT_analyzeEntropy(header+hSize, HBUFFSIZE-hSize, |
884 | compressionLevel, |
885 | samplesBuffer, samplesSizes, nbSamples, |
886 | customDictContent, dictContentSize, |
887 | notificationLevel); |
888 | if (ZDICT_isError(eSize)) return eSize; |
889 | hSize += eSize; |
890 | } |
891 | |
892 | /* Shrink the content size if it doesn't fit in the buffer */ |
893 | if (hSize + dictContentSize > dictBufferCapacity) { |
894 | dictContentSize = dictBufferCapacity - hSize; |
895 | } |
896 | |
897 | /* Pad the dictionary content with zeros if it is too small */ |
898 | if (dictContentSize < minContentSize) { |
899 | RETURN_ERROR_IF(hSize + minContentSize > dictBufferCapacity, dstSize_tooSmall, |
900 | "dictBufferCapacity too small to fit max repcode"); |
901 | paddingSize = minContentSize - dictContentSize; |
902 | } else { |
903 | paddingSize = 0; |
904 | } |
905 | |
906 | { |
907 | size_t const dictSize = hSize + paddingSize + dictContentSize; |
908 | |
909 | /* The dictionary consists of the header, optional padding, and the content. |
910 | * The padding comes before the content because the "best" position in the |
911 | * dictionary is the last byte. |
912 | */ |
913 | BYTE* const outDictHeader = (BYTE*)dictBuffer; |
914 | BYTE* const outDictPadding = outDictHeader + hSize; |
915 | BYTE* const outDictContent = outDictPadding + paddingSize; |
916 | |
917 | assert(dictSize <= dictBufferCapacity); |
918 | assert(outDictContent + dictContentSize == (BYTE*)dictBuffer + dictSize); |
919 | |
920 | /* First copy the customDictContent into its final location. |
921 | * `customDictContent` and `dictBuffer` may overlap, so we must |
922 | * do this before any other writes into the output buffer. |
923 | * Then copy the header & padding into the output buffer. |
924 | */ |
925 | memmove(outDictContent, customDictContent, dictContentSize); |
926 | memcpy(outDictHeader, header, hSize); |
927 | memset(outDictPadding, 0, paddingSize); |
928 | |
929 | return dictSize; |
930 | } |
931 | } |
932 | |
933 | |
934 | static size_t ZDICT_addEntropyTablesFromBuffer_advanced( |
935 | void* dictBuffer, size_t dictContentSize, size_t dictBufferCapacity, |
936 | const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples, |
937 | ZDICT_params_t params) |
938 | { |
939 | int const compressionLevel = (params.compressionLevel == 0) ? ZSTD_CLEVEL_DEFAULT : params.compressionLevel; |
940 | U32 const notificationLevel = params.notificationLevel; |
941 | size_t hSize = 8; |
942 | |
943 | /* calculate entropy tables */ |
944 | DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */ |
945 | DISPLAYLEVEL(2, "statistics ... \n"); |
946 | { size_t const eSize = ZDICT_analyzeEntropy((char*)dictBuffer+hSize, dictBufferCapacity-hSize, |
947 | compressionLevel, |
948 | samplesBuffer, samplesSizes, nbSamples, |
949 | (char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize, |
950 | notificationLevel); |
951 | if (ZDICT_isError(eSize)) return eSize; |
952 | hSize += eSize; |
953 | } |
954 | |
955 | /* add dictionary header (after entropy tables) */ |
956 | MEM_writeLE32(dictBuffer, ZSTD_MAGIC_DICTIONARY); |
957 | { U64 const randomID = XXH64((char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize, 0); |
958 | U32 const compliantID = (randomID % ((1U<<31)-32768)) + 32768; |
959 | U32 const dictID = params.dictID ? params.dictID : compliantID; |
960 | MEM_writeLE32((char*)dictBuffer+4, dictID); |
961 | } |
962 | |
963 | if (hSize + dictContentSize < dictBufferCapacity) |
964 | memmove((char*)dictBuffer + hSize, (char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize); |
965 | return MIN(dictBufferCapacity, hSize+dictContentSize); |
966 | } |
967 | |
968 | /*! ZDICT_trainFromBuffer_unsafe_legacy() : |
969 | * Warning : `samplesBuffer` must be followed by noisy guard band !!! |
970 | * @return : size of dictionary, or an error code which can be tested with ZDICT_isError() |
971 | */ |
972 | static size_t ZDICT_trainFromBuffer_unsafe_legacy( |
973 | void* dictBuffer, size_t maxDictSize, |
974 | const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples, |
975 | ZDICT_legacy_params_t params) |
976 | { |
977 | U32 const dictListSize = MAX(MAX(DICTLISTSIZE_DEFAULT, nbSamples), (U32)(maxDictSize/16)); |
978 | dictItem* const dictList = (dictItem*)malloc(dictListSize * sizeof(*dictList)); |
979 | unsigned const selectivity = params.selectivityLevel == 0 ? g_selectivity_default : params.selectivityLevel; |
980 | unsigned const minRep = (selectivity > 30) ? MINRATIO : nbSamples >> selectivity; |
981 | size_t const targetDictSize = maxDictSize; |
982 | size_t const samplesBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples); |
983 | size_t dictSize = 0; |
984 | U32 const notificationLevel = params.zParams.notificationLevel; |
985 | |
986 | /* checks */ |
987 | if (!dictList) return ERROR(memory_allocation); |
988 | if (maxDictSize < ZDICT_DICTSIZE_MIN) { free(dictList); return ERROR(dstSize_tooSmall); } /* requested dictionary size is too small */ |
989 | if (samplesBuffSize < ZDICT_MIN_SAMPLES_SIZE) { free(dictList); return ERROR(dictionaryCreation_failed); } /* not enough source to create dictionary */ |
990 | |
991 | /* init */ |
992 | ZDICT_initDictItem(dictList); |
993 | |
994 | /* build dictionary */ |
995 | ZDICT_trainBuffer_legacy(dictList, dictListSize, |
996 | samplesBuffer, samplesBuffSize, |
997 | samplesSizes, nbSamples, |
998 | minRep, notificationLevel); |
999 | |
1000 | /* display best matches */ |
1001 | if (params.zParams.notificationLevel>= 3) { |
1002 | unsigned const nb = MIN(25, dictList[0].pos); |
1003 | unsigned const dictContentSize = ZDICT_dictSize(dictList); |
1004 | unsigned u; |
1005 | DISPLAYLEVEL(3, "\n %u segments found, of total size %u \n", (unsigned)dictList[0].pos-1, dictContentSize); |
1006 | DISPLAYLEVEL(3, "list %u best segments \n", nb-1); |
1007 | for (u=1; u<nb; u++) { |
1008 | unsigned const pos = dictList[u].pos; |
1009 | unsigned const length = dictList[u].length; |
1010 | U32 const printedLength = MIN(40, length); |
1011 | if ((pos > samplesBuffSize) || ((pos + length) > samplesBuffSize)) { |
1012 | free(dictList); |
1013 | return ERROR(GENERIC); /* should never happen */ |
1014 | } |
1015 | DISPLAYLEVEL(3, "%3u:%3u bytes at pos %8u, savings %7u bytes |", |
1016 | u, length, pos, (unsigned)dictList[u].savings); |
1017 | ZDICT_printHex((const char*)samplesBuffer+pos, printedLength); |
1018 | DISPLAYLEVEL(3, "| \n"); |
1019 | } } |
1020 | |
1021 | |
1022 | /* create dictionary */ |
1023 | { unsigned dictContentSize = ZDICT_dictSize(dictList); |
1024 | if (dictContentSize < ZDICT_CONTENTSIZE_MIN) { free(dictList); return ERROR(dictionaryCreation_failed); } /* dictionary content too small */ |
1025 | if (dictContentSize < targetDictSize/4) { |
1026 | DISPLAYLEVEL(2, "! warning : selected content significantly smaller than requested (%u < %u) \n", dictContentSize, (unsigned)maxDictSize); |
1027 | if (samplesBuffSize < 10 * targetDictSize) |
1028 | DISPLAYLEVEL(2, "! consider increasing the number of samples (total size : %u MB)\n", (unsigned)(samplesBuffSize>>20)); |
1029 | if (minRep > MINRATIO) { |
1030 | DISPLAYLEVEL(2, "! consider increasing selectivity to produce larger dictionary (-s%u) \n", selectivity+1); |
1031 | DISPLAYLEVEL(2, "! note : larger dictionaries are not necessarily better, test its efficiency on samples \n"); |
1032 | } |
1033 | } |
1034 | |
1035 | if ((dictContentSize > targetDictSize*3) && (nbSamples > 2*MINRATIO) && (selectivity>1)) { |
1036 | unsigned proposedSelectivity = selectivity-1; |
1037 | while ((nbSamples >> proposedSelectivity) <= MINRATIO) { proposedSelectivity--; } |
1038 | DISPLAYLEVEL(2, "! note : calculated dictionary significantly larger than requested (%u > %u) \n", dictContentSize, (unsigned)maxDictSize); |
1039 | DISPLAYLEVEL(2, "! consider increasing dictionary size, or produce denser dictionary (-s%u) \n", proposedSelectivity); |
1040 | DISPLAYLEVEL(2, "! always test dictionary efficiency on real samples \n"); |
1041 | } |
1042 | |
1043 | /* limit dictionary size */ |
1044 | { U32 const max = dictList->pos; /* convention : nb of useful elts within dictList */ |
1045 | U32 currentSize = 0; |
1046 | U32 n; for (n=1; n<max; n++) { |
1047 | currentSize += dictList[n].length; |
1048 | if (currentSize > targetDictSize) { currentSize -= dictList[n].length; break; } |
1049 | } |
1050 | dictList->pos = n; |
1051 | dictContentSize = currentSize; |
1052 | } |
1053 | |
1054 | /* build dict content */ |
1055 | { U32 u; |
1056 | BYTE* ptr = (BYTE*)dictBuffer + maxDictSize; |
1057 | for (u=1; u<dictList->pos; u++) { |
1058 | U32 l = dictList[u].length; |
1059 | ptr -= l; |
1060 | if (ptr<(BYTE*)dictBuffer) { free(dictList); return ERROR(GENERIC); } /* should not happen */ |
1061 | memcpy(ptr, (const char*)samplesBuffer+dictList[u].pos, l); |
1062 | } } |
1063 | |
1064 | dictSize = ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, maxDictSize, |
1065 | samplesBuffer, samplesSizes, nbSamples, |
1066 | params.zParams); |
1067 | } |
1068 | |
1069 | /* clean up */ |
1070 | free(dictList); |
1071 | return dictSize; |
1072 | } |
1073 | |
1074 | |
1075 | /* ZDICT_trainFromBuffer_legacy() : |
1076 | * issue : samplesBuffer need to be followed by a noisy guard band. |
1077 | * work around : duplicate the buffer, and add the noise */ |
1078 | size_t ZDICT_trainFromBuffer_legacy(void* dictBuffer, size_t dictBufferCapacity, |
1079 | const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples, |
1080 | ZDICT_legacy_params_t params) |
1081 | { |
1082 | size_t result; |
1083 | void* newBuff; |
1084 | size_t const sBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples); |
1085 | if (sBuffSize < ZDICT_MIN_SAMPLES_SIZE) return 0; /* not enough content => no dictionary */ |
1086 | |
1087 | newBuff = malloc(sBuffSize + NOISELENGTH); |
1088 | if (!newBuff) return ERROR(memory_allocation); |
1089 | |
1090 | memcpy(newBuff, samplesBuffer, sBuffSize); |
1091 | ZDICT_fillNoise((char*)newBuff + sBuffSize, NOISELENGTH); /* guard band, for end of buffer condition */ |
1092 | |
1093 | result = |
1094 | ZDICT_trainFromBuffer_unsafe_legacy(dictBuffer, dictBufferCapacity, newBuff, |
1095 | samplesSizes, nbSamples, params); |
1096 | free(newBuff); |
1097 | return result; |
1098 | } |
1099 | |
1100 | |
1101 | size_t ZDICT_trainFromBuffer(void* dictBuffer, size_t dictBufferCapacity, |
1102 | const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples) |
1103 | { |
1104 | ZDICT_fastCover_params_t params; |
1105 | DEBUGLOG(3, "ZDICT_trainFromBuffer"); |
1106 | memset(¶ms, 0, sizeof(params)); |
1107 | params.d = 8; |
1108 | params.steps = 4; |
1109 | /* Use default level since no compression level information is available */ |
1110 | params.zParams.compressionLevel = ZSTD_CLEVEL_DEFAULT; |
1111 | #if defined(DEBUGLEVEL) && (DEBUGLEVEL>=1) |
1112 | params.zParams.notificationLevel = DEBUGLEVEL; |
1113 | #endif |
1114 | return ZDICT_optimizeTrainFromBuffer_fastCover(dictBuffer, dictBufferCapacity, |
1115 | samplesBuffer, samplesSizes, nbSamples, |
1116 | ¶ms); |
1117 | } |
1118 | |
1119 | size_t ZDICT_addEntropyTablesFromBuffer(void* dictBuffer, size_t dictContentSize, size_t dictBufferCapacity, |
1120 | const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples) |
1121 | { |
1122 | ZDICT_params_t params; |
1123 | memset(¶ms, 0, sizeof(params)); |
1124 | return ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, dictBufferCapacity, |
1125 | samplesBuffer, samplesSizes, nbSamples, |
1126 | params); |
1127 | } |