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