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 | * Constructs a dictionary using a heuristic based on the following paper: |
13 | * |
14 | * Liao, Petri, Moffat, Wirth |
15 | * Effective Construction of Relative Lempel-Ziv Dictionaries |
16 | * Published in WWW 2016. |
17 | * |
18 | * Adapted from code originally written by @ot (Giuseppe Ottaviano). |
19 | ******************************************************************************/ |
20 | |
21 | /*-************************************* |
22 | * Dependencies |
23 | ***************************************/ |
24 | #include <stdio.h> /* fprintf */ |
25 | #include <stdlib.h> /* malloc, free, qsort */ |
26 | #include <string.h> /* memset */ |
27 | #include <time.h> /* clock */ |
28 | |
29 | #ifndef ZDICT_STATIC_LINKING_ONLY |
30 | # define ZDICT_STATIC_LINKING_ONLY |
31 | #endif |
32 | |
33 | #include "../common/mem.h" /* read */ |
f535537f |
34 | #include "../common/pool.h" /* POOL_ctx */ |
35 | #include "../common/threading.h" /* ZSTD_pthread_mutex_t */ |
648db22b |
36 | #include "../common/zstd_internal.h" /* includes zstd.h */ |
37 | #include "../common/bits.h" /* ZSTD_highbit32 */ |
38 | #include "../zdict.h" |
39 | #include "cover.h" |
40 | |
41 | /*-************************************* |
42 | * Constants |
43 | ***************************************/ |
44 | /** |
45 | * There are 32bit indexes used to ref samples, so limit samples size to 4GB |
46 | * on 64bit builds. |
47 | * For 32bit builds we choose 1 GB. |
48 | * Most 32bit platforms have 2GB user-mode addressable space and we allocate a large |
49 | * contiguous buffer, so 1GB is already a high limit. |
50 | */ |
51 | #define COVER_MAX_SAMPLES_SIZE (sizeof(size_t) == 8 ? ((unsigned)-1) : ((unsigned)1 GB)) |
52 | #define COVER_DEFAULT_SPLITPOINT 1.0 |
53 | |
54 | /*-************************************* |
55 | * Console display |
56 | ***************************************/ |
57 | #ifndef LOCALDISPLAYLEVEL |
58 | static int g_displayLevel = 0; |
59 | #endif |
60 | #undef DISPLAY |
61 | #define DISPLAY(...) \ |
62 | { \ |
63 | fprintf(stderr, __VA_ARGS__); \ |
64 | fflush(stderr); \ |
65 | } |
66 | #undef LOCALDISPLAYLEVEL |
67 | #define LOCALDISPLAYLEVEL(displayLevel, l, ...) \ |
68 | if (displayLevel >= l) { \ |
69 | DISPLAY(__VA_ARGS__); \ |
70 | } /* 0 : no display; 1: errors; 2: default; 3: details; 4: debug */ |
71 | #undef DISPLAYLEVEL |
72 | #define DISPLAYLEVEL(l, ...) LOCALDISPLAYLEVEL(g_displayLevel, l, __VA_ARGS__) |
73 | |
74 | #ifndef LOCALDISPLAYUPDATE |
75 | static const clock_t g_refreshRate = CLOCKS_PER_SEC * 15 / 100; |
76 | static clock_t g_time = 0; |
77 | #endif |
78 | #undef LOCALDISPLAYUPDATE |
79 | #define LOCALDISPLAYUPDATE(displayLevel, l, ...) \ |
80 | if (displayLevel >= l) { \ |
f535537f |
81 | if ((clock() - g_time > g_refreshRate) || (displayLevel >= 4)) { \ |
648db22b |
82 | g_time = clock(); \ |
83 | DISPLAY(__VA_ARGS__); \ |
84 | } \ |
85 | } |
86 | #undef DISPLAYUPDATE |
87 | #define DISPLAYUPDATE(l, ...) LOCALDISPLAYUPDATE(g_displayLevel, l, __VA_ARGS__) |
88 | |
89 | /*-************************************* |
90 | * Hash table |
91 | *************************************** |
92 | * A small specialized hash map for storing activeDmers. |
93 | * The map does not resize, so if it becomes full it will loop forever. |
94 | * Thus, the map must be large enough to store every value. |
95 | * The map implements linear probing and keeps its load less than 0.5. |
96 | */ |
97 | |
98 | #define MAP_EMPTY_VALUE ((U32)-1) |
99 | typedef struct COVER_map_pair_t_s { |
100 | U32 key; |
101 | U32 value; |
102 | } COVER_map_pair_t; |
103 | |
104 | typedef struct COVER_map_s { |
105 | COVER_map_pair_t *data; |
106 | U32 sizeLog; |
107 | U32 size; |
108 | U32 sizeMask; |
109 | } COVER_map_t; |
110 | |
111 | /** |
112 | * Clear the map. |
113 | */ |
114 | static void COVER_map_clear(COVER_map_t *map) { |
115 | memset(map->data, MAP_EMPTY_VALUE, map->size * sizeof(COVER_map_pair_t)); |
116 | } |
117 | |
118 | /** |
119 | * Initializes a map of the given size. |
120 | * Returns 1 on success and 0 on failure. |
121 | * The map must be destroyed with COVER_map_destroy(). |
122 | * The map is only guaranteed to be large enough to hold size elements. |
123 | */ |
124 | static int COVER_map_init(COVER_map_t *map, U32 size) { |
125 | map->sizeLog = ZSTD_highbit32(size) + 2; |
126 | map->size = (U32)1 << map->sizeLog; |
127 | map->sizeMask = map->size - 1; |
128 | map->data = (COVER_map_pair_t *)malloc(map->size * sizeof(COVER_map_pair_t)); |
129 | if (!map->data) { |
130 | map->sizeLog = 0; |
131 | map->size = 0; |
132 | return 0; |
133 | } |
134 | COVER_map_clear(map); |
135 | return 1; |
136 | } |
137 | |
138 | /** |
139 | * Internal hash function |
140 | */ |
141 | static const U32 COVER_prime4bytes = 2654435761U; |
142 | static U32 COVER_map_hash(COVER_map_t *map, U32 key) { |
143 | return (key * COVER_prime4bytes) >> (32 - map->sizeLog); |
144 | } |
145 | |
146 | /** |
147 | * Helper function that returns the index that a key should be placed into. |
148 | */ |
149 | static U32 COVER_map_index(COVER_map_t *map, U32 key) { |
150 | const U32 hash = COVER_map_hash(map, key); |
151 | U32 i; |
152 | for (i = hash;; i = (i + 1) & map->sizeMask) { |
153 | COVER_map_pair_t *pos = &map->data[i]; |
154 | if (pos->value == MAP_EMPTY_VALUE) { |
155 | return i; |
156 | } |
157 | if (pos->key == key) { |
158 | return i; |
159 | } |
160 | } |
161 | } |
162 | |
163 | /** |
164 | * Returns the pointer to the value for key. |
165 | * If key is not in the map, it is inserted and the value is set to 0. |
166 | * The map must not be full. |
167 | */ |
168 | static U32 *COVER_map_at(COVER_map_t *map, U32 key) { |
169 | COVER_map_pair_t *pos = &map->data[COVER_map_index(map, key)]; |
170 | if (pos->value == MAP_EMPTY_VALUE) { |
171 | pos->key = key; |
172 | pos->value = 0; |
173 | } |
174 | return &pos->value; |
175 | } |
176 | |
177 | /** |
178 | * Deletes key from the map if present. |
179 | */ |
180 | static void COVER_map_remove(COVER_map_t *map, U32 key) { |
181 | U32 i = COVER_map_index(map, key); |
182 | COVER_map_pair_t *del = &map->data[i]; |
183 | U32 shift = 1; |
184 | if (del->value == MAP_EMPTY_VALUE) { |
185 | return; |
186 | } |
187 | for (i = (i + 1) & map->sizeMask;; i = (i + 1) & map->sizeMask) { |
188 | COVER_map_pair_t *const pos = &map->data[i]; |
189 | /* If the position is empty we are done */ |
190 | if (pos->value == MAP_EMPTY_VALUE) { |
191 | del->value = MAP_EMPTY_VALUE; |
192 | return; |
193 | } |
194 | /* If pos can be moved to del do so */ |
195 | if (((i - COVER_map_hash(map, pos->key)) & map->sizeMask) >= shift) { |
196 | del->key = pos->key; |
197 | del->value = pos->value; |
198 | del = pos; |
199 | shift = 1; |
200 | } else { |
201 | ++shift; |
202 | } |
203 | } |
204 | } |
205 | |
206 | /** |
207 | * Destroys a map that is inited with COVER_map_init(). |
208 | */ |
209 | static void COVER_map_destroy(COVER_map_t *map) { |
210 | if (map->data) { |
211 | free(map->data); |
212 | } |
213 | map->data = NULL; |
214 | map->size = 0; |
215 | } |
216 | |
217 | /*-************************************* |
218 | * Context |
219 | ***************************************/ |
220 | |
221 | typedef struct { |
222 | const BYTE *samples; |
223 | size_t *offsets; |
224 | const size_t *samplesSizes; |
225 | size_t nbSamples; |
226 | size_t nbTrainSamples; |
227 | size_t nbTestSamples; |
228 | U32 *suffix; |
229 | size_t suffixSize; |
230 | U32 *freqs; |
231 | U32 *dmerAt; |
232 | unsigned d; |
233 | } COVER_ctx_t; |
234 | |
235 | /* We need a global context for qsort... */ |
236 | static COVER_ctx_t *g_coverCtx = NULL; |
237 | |
238 | /*-************************************* |
239 | * Helper functions |
240 | ***************************************/ |
241 | |
242 | /** |
243 | * Returns the sum of the sample sizes. |
244 | */ |
245 | size_t COVER_sum(const size_t *samplesSizes, unsigned nbSamples) { |
246 | size_t sum = 0; |
247 | unsigned i; |
248 | for (i = 0; i < nbSamples; ++i) { |
249 | sum += samplesSizes[i]; |
250 | } |
251 | return sum; |
252 | } |
253 | |
254 | /** |
255 | * Returns -1 if the dmer at lp is less than the dmer at rp. |
256 | * Return 0 if the dmers at lp and rp are equal. |
257 | * Returns 1 if the dmer at lp is greater than the dmer at rp. |
258 | */ |
259 | static int COVER_cmp(COVER_ctx_t *ctx, const void *lp, const void *rp) { |
260 | U32 const lhs = *(U32 const *)lp; |
261 | U32 const rhs = *(U32 const *)rp; |
262 | return memcmp(ctx->samples + lhs, ctx->samples + rhs, ctx->d); |
263 | } |
264 | /** |
265 | * Faster version for d <= 8. |
266 | */ |
267 | static int COVER_cmp8(COVER_ctx_t *ctx, const void *lp, const void *rp) { |
268 | U64 const mask = (ctx->d == 8) ? (U64)-1 : (((U64)1 << (8 * ctx->d)) - 1); |
269 | U64 const lhs = MEM_readLE64(ctx->samples + *(U32 const *)lp) & mask; |
270 | U64 const rhs = MEM_readLE64(ctx->samples + *(U32 const *)rp) & mask; |
271 | if (lhs < rhs) { |
272 | return -1; |
273 | } |
274 | return (lhs > rhs); |
275 | } |
276 | |
277 | /** |
278 | * Same as COVER_cmp() except ties are broken by pointer value |
279 | * NOTE: g_coverCtx must be set to call this function. A global is required because |
280 | * qsort doesn't take an opaque pointer. |
281 | */ |
282 | static int WIN_CDECL COVER_strict_cmp(const void *lp, const void *rp) { |
283 | int result = COVER_cmp(g_coverCtx, lp, rp); |
284 | if (result == 0) { |
285 | result = lp < rp ? -1 : 1; |
286 | } |
287 | return result; |
288 | } |
289 | /** |
290 | * Faster version for d <= 8. |
291 | */ |
292 | static int WIN_CDECL COVER_strict_cmp8(const void *lp, const void *rp) { |
293 | int result = COVER_cmp8(g_coverCtx, lp, rp); |
294 | if (result == 0) { |
295 | result = lp < rp ? -1 : 1; |
296 | } |
297 | return result; |
298 | } |
299 | |
300 | /** |
301 | * Returns the first pointer in [first, last) whose element does not compare |
302 | * less than value. If no such element exists it returns last. |
303 | */ |
f535537f |
304 | static const size_t *COVER_lower_bound(const size_t* first, const size_t* last, |
648db22b |
305 | size_t value) { |
f535537f |
306 | size_t count = (size_t)(last - first); |
307 | assert(last >= first); |
648db22b |
308 | while (count != 0) { |
309 | size_t step = count / 2; |
310 | const size_t *ptr = first; |
311 | ptr += step; |
312 | if (*ptr < value) { |
313 | first = ++ptr; |
314 | count -= step + 1; |
315 | } else { |
316 | count = step; |
317 | } |
318 | } |
319 | return first; |
320 | } |
321 | |
322 | /** |
323 | * Generic groupBy function. |
324 | * Groups an array sorted by cmp into groups with equivalent values. |
325 | * Calls grp for each group. |
326 | */ |
327 | static void |
328 | COVER_groupBy(const void *data, size_t count, size_t size, COVER_ctx_t *ctx, |
329 | int (*cmp)(COVER_ctx_t *, const void *, const void *), |
330 | void (*grp)(COVER_ctx_t *, const void *, const void *)) { |
331 | const BYTE *ptr = (const BYTE *)data; |
332 | size_t num = 0; |
333 | while (num < count) { |
334 | const BYTE *grpEnd = ptr + size; |
335 | ++num; |
336 | while (num < count && cmp(ctx, ptr, grpEnd) == 0) { |
337 | grpEnd += size; |
338 | ++num; |
339 | } |
340 | grp(ctx, ptr, grpEnd); |
341 | ptr = grpEnd; |
342 | } |
343 | } |
344 | |
345 | /*-************************************* |
346 | * Cover functions |
347 | ***************************************/ |
348 | |
349 | /** |
350 | * Called on each group of positions with the same dmer. |
351 | * Counts the frequency of each dmer and saves it in the suffix array. |
352 | * Fills `ctx->dmerAt`. |
353 | */ |
354 | static void COVER_group(COVER_ctx_t *ctx, const void *group, |
355 | const void *groupEnd) { |
356 | /* The group consists of all the positions with the same first d bytes. */ |
357 | const U32 *grpPtr = (const U32 *)group; |
358 | const U32 *grpEnd = (const U32 *)groupEnd; |
359 | /* The dmerId is how we will reference this dmer. |
360 | * This allows us to map the whole dmer space to a much smaller space, the |
361 | * size of the suffix array. |
362 | */ |
363 | const U32 dmerId = (U32)(grpPtr - ctx->suffix); |
364 | /* Count the number of samples this dmer shows up in */ |
365 | U32 freq = 0; |
366 | /* Details */ |
367 | const size_t *curOffsetPtr = ctx->offsets; |
368 | const size_t *offsetsEnd = ctx->offsets + ctx->nbSamples; |
369 | /* Once *grpPtr >= curSampleEnd this occurrence of the dmer is in a |
370 | * different sample than the last. |
371 | */ |
372 | size_t curSampleEnd = ctx->offsets[0]; |
373 | for (; grpPtr != grpEnd; ++grpPtr) { |
374 | /* Save the dmerId for this position so we can get back to it. */ |
375 | ctx->dmerAt[*grpPtr] = dmerId; |
376 | /* Dictionaries only help for the first reference to the dmer. |
377 | * After that zstd can reference the match from the previous reference. |
378 | * So only count each dmer once for each sample it is in. |
379 | */ |
380 | if (*grpPtr < curSampleEnd) { |
381 | continue; |
382 | } |
383 | freq += 1; |
384 | /* Binary search to find the end of the sample *grpPtr is in. |
385 | * In the common case that grpPtr + 1 == grpEnd we can skip the binary |
386 | * search because the loop is over. |
387 | */ |
388 | if (grpPtr + 1 != grpEnd) { |
389 | const size_t *sampleEndPtr = |
390 | COVER_lower_bound(curOffsetPtr, offsetsEnd, *grpPtr); |
391 | curSampleEnd = *sampleEndPtr; |
392 | curOffsetPtr = sampleEndPtr + 1; |
393 | } |
394 | } |
395 | /* At this point we are never going to look at this segment of the suffix |
396 | * array again. We take advantage of this fact to save memory. |
397 | * We store the frequency of the dmer in the first position of the group, |
398 | * which is dmerId. |
399 | */ |
400 | ctx->suffix[dmerId] = freq; |
401 | } |
402 | |
403 | |
404 | /** |
405 | * Selects the best segment in an epoch. |
406 | * Segments of are scored according to the function: |
407 | * |
408 | * Let F(d) be the frequency of dmer d. |
409 | * Let S_i be the dmer at position i of segment S which has length k. |
410 | * |
411 | * Score(S) = F(S_1) + F(S_2) + ... + F(S_{k-d+1}) |
412 | * |
413 | * Once the dmer d is in the dictionary we set F(d) = 0. |
414 | */ |
415 | static COVER_segment_t COVER_selectSegment(const COVER_ctx_t *ctx, U32 *freqs, |
416 | COVER_map_t *activeDmers, U32 begin, |
417 | U32 end, |
418 | ZDICT_cover_params_t parameters) { |
419 | /* Constants */ |
420 | const U32 k = parameters.k; |
421 | const U32 d = parameters.d; |
422 | const U32 dmersInK = k - d + 1; |
423 | /* Try each segment (activeSegment) and save the best (bestSegment) */ |
424 | COVER_segment_t bestSegment = {0, 0, 0}; |
425 | COVER_segment_t activeSegment; |
426 | /* Reset the activeDmers in the segment */ |
427 | COVER_map_clear(activeDmers); |
428 | /* The activeSegment starts at the beginning of the epoch. */ |
429 | activeSegment.begin = begin; |
430 | activeSegment.end = begin; |
431 | activeSegment.score = 0; |
432 | /* Slide the activeSegment through the whole epoch. |
433 | * Save the best segment in bestSegment. |
434 | */ |
435 | while (activeSegment.end < end) { |
436 | /* The dmerId for the dmer at the next position */ |
437 | U32 newDmer = ctx->dmerAt[activeSegment.end]; |
438 | /* The entry in activeDmers for this dmerId */ |
439 | U32 *newDmerOcc = COVER_map_at(activeDmers, newDmer); |
440 | /* If the dmer isn't already present in the segment add its score. */ |
441 | if (*newDmerOcc == 0) { |
442 | /* The paper suggest using the L-0.5 norm, but experiments show that it |
443 | * doesn't help. |
444 | */ |
445 | activeSegment.score += freqs[newDmer]; |
446 | } |
447 | /* Add the dmer to the segment */ |
448 | activeSegment.end += 1; |
449 | *newDmerOcc += 1; |
450 | |
451 | /* If the window is now too large, drop the first position */ |
452 | if (activeSegment.end - activeSegment.begin == dmersInK + 1) { |
453 | U32 delDmer = ctx->dmerAt[activeSegment.begin]; |
454 | U32 *delDmerOcc = COVER_map_at(activeDmers, delDmer); |
455 | activeSegment.begin += 1; |
456 | *delDmerOcc -= 1; |
457 | /* If this is the last occurrence of the dmer, subtract its score */ |
458 | if (*delDmerOcc == 0) { |
459 | COVER_map_remove(activeDmers, delDmer); |
460 | activeSegment.score -= freqs[delDmer]; |
461 | } |
462 | } |
463 | |
464 | /* If this segment is the best so far save it */ |
465 | if (activeSegment.score > bestSegment.score) { |
466 | bestSegment = activeSegment; |
467 | } |
468 | } |
469 | { |
470 | /* Trim off the zero frequency head and tail from the segment. */ |
471 | U32 newBegin = bestSegment.end; |
472 | U32 newEnd = bestSegment.begin; |
473 | U32 pos; |
474 | for (pos = bestSegment.begin; pos != bestSegment.end; ++pos) { |
475 | U32 freq = freqs[ctx->dmerAt[pos]]; |
476 | if (freq != 0) { |
477 | newBegin = MIN(newBegin, pos); |
478 | newEnd = pos + 1; |
479 | } |
480 | } |
481 | bestSegment.begin = newBegin; |
482 | bestSegment.end = newEnd; |
483 | } |
484 | { |
485 | /* Zero out the frequency of each dmer covered by the chosen segment. */ |
486 | U32 pos; |
487 | for (pos = bestSegment.begin; pos != bestSegment.end; ++pos) { |
488 | freqs[ctx->dmerAt[pos]] = 0; |
489 | } |
490 | } |
491 | return bestSegment; |
492 | } |
493 | |
494 | /** |
495 | * Check the validity of the parameters. |
496 | * Returns non-zero if the parameters are valid and 0 otherwise. |
497 | */ |
498 | static int COVER_checkParameters(ZDICT_cover_params_t parameters, |
499 | size_t maxDictSize) { |
500 | /* k and d are required parameters */ |
501 | if (parameters.d == 0 || parameters.k == 0) { |
502 | return 0; |
503 | } |
504 | /* k <= maxDictSize */ |
505 | if (parameters.k > maxDictSize) { |
506 | return 0; |
507 | } |
508 | /* d <= k */ |
509 | if (parameters.d > parameters.k) { |
510 | return 0; |
511 | } |
512 | /* 0 < splitPoint <= 1 */ |
513 | if (parameters.splitPoint <= 0 || parameters.splitPoint > 1){ |
514 | return 0; |
515 | } |
516 | return 1; |
517 | } |
518 | |
519 | /** |
520 | * Clean up a context initialized with `COVER_ctx_init()`. |
521 | */ |
522 | static void COVER_ctx_destroy(COVER_ctx_t *ctx) { |
523 | if (!ctx) { |
524 | return; |
525 | } |
526 | if (ctx->suffix) { |
527 | free(ctx->suffix); |
528 | ctx->suffix = NULL; |
529 | } |
530 | if (ctx->freqs) { |
531 | free(ctx->freqs); |
532 | ctx->freqs = NULL; |
533 | } |
534 | if (ctx->dmerAt) { |
535 | free(ctx->dmerAt); |
536 | ctx->dmerAt = NULL; |
537 | } |
538 | if (ctx->offsets) { |
539 | free(ctx->offsets); |
540 | ctx->offsets = NULL; |
541 | } |
542 | } |
543 | |
544 | /** |
545 | * Prepare a context for dictionary building. |
546 | * The context is only dependent on the parameter `d` and can be used multiple |
547 | * times. |
548 | * Returns 0 on success or error code on error. |
549 | * The context must be destroyed with `COVER_ctx_destroy()`. |
550 | */ |
551 | static size_t COVER_ctx_init(COVER_ctx_t *ctx, const void *samplesBuffer, |
552 | const size_t *samplesSizes, unsigned nbSamples, |
f535537f |
553 | unsigned d, double splitPoint) |
554 | { |
648db22b |
555 | const BYTE *const samples = (const BYTE *)samplesBuffer; |
556 | const size_t totalSamplesSize = COVER_sum(samplesSizes, nbSamples); |
557 | /* Split samples into testing and training sets */ |
558 | const unsigned nbTrainSamples = splitPoint < 1.0 ? (unsigned)((double)nbSamples * splitPoint) : nbSamples; |
559 | const unsigned nbTestSamples = splitPoint < 1.0 ? nbSamples - nbTrainSamples : nbSamples; |
560 | const size_t trainingSamplesSize = splitPoint < 1.0 ? COVER_sum(samplesSizes, nbTrainSamples) : totalSamplesSize; |
561 | const size_t testSamplesSize = splitPoint < 1.0 ? COVER_sum(samplesSizes + nbTrainSamples, nbTestSamples) : totalSamplesSize; |
562 | /* Checks */ |
563 | if (totalSamplesSize < MAX(d, sizeof(U64)) || |
564 | totalSamplesSize >= (size_t)COVER_MAX_SAMPLES_SIZE) { |
565 | DISPLAYLEVEL(1, "Total samples size is too large (%u MB), maximum size is %u MB\n", |
566 | (unsigned)(totalSamplesSize>>20), (COVER_MAX_SAMPLES_SIZE >> 20)); |
567 | return ERROR(srcSize_wrong); |
568 | } |
569 | /* Check if there are at least 5 training samples */ |
570 | if (nbTrainSamples < 5) { |
571 | DISPLAYLEVEL(1, "Total number of training samples is %u and is invalid.", nbTrainSamples); |
572 | return ERROR(srcSize_wrong); |
573 | } |
574 | /* Check if there's testing sample */ |
575 | if (nbTestSamples < 1) { |
576 | DISPLAYLEVEL(1, "Total number of testing samples is %u and is invalid.", nbTestSamples); |
577 | return ERROR(srcSize_wrong); |
578 | } |
579 | /* Zero the context */ |
580 | memset(ctx, 0, sizeof(*ctx)); |
581 | DISPLAYLEVEL(2, "Training on %u samples of total size %u\n", nbTrainSamples, |
582 | (unsigned)trainingSamplesSize); |
583 | DISPLAYLEVEL(2, "Testing on %u samples of total size %u\n", nbTestSamples, |
584 | (unsigned)testSamplesSize); |
585 | ctx->samples = samples; |
586 | ctx->samplesSizes = samplesSizes; |
587 | ctx->nbSamples = nbSamples; |
588 | ctx->nbTrainSamples = nbTrainSamples; |
589 | ctx->nbTestSamples = nbTestSamples; |
590 | /* Partial suffix array */ |
591 | ctx->suffixSize = trainingSamplesSize - MAX(d, sizeof(U64)) + 1; |
592 | ctx->suffix = (U32 *)malloc(ctx->suffixSize * sizeof(U32)); |
593 | /* Maps index to the dmerID */ |
594 | ctx->dmerAt = (U32 *)malloc(ctx->suffixSize * sizeof(U32)); |
595 | /* The offsets of each file */ |
596 | ctx->offsets = (size_t *)malloc((nbSamples + 1) * sizeof(size_t)); |
597 | if (!ctx->suffix || !ctx->dmerAt || !ctx->offsets) { |
598 | DISPLAYLEVEL(1, "Failed to allocate scratch buffers\n"); |
599 | COVER_ctx_destroy(ctx); |
600 | return ERROR(memory_allocation); |
601 | } |
602 | ctx->freqs = NULL; |
603 | ctx->d = d; |
604 | |
605 | /* Fill offsets from the samplesSizes */ |
606 | { |
607 | U32 i; |
608 | ctx->offsets[0] = 0; |
609 | for (i = 1; i <= nbSamples; ++i) { |
610 | ctx->offsets[i] = ctx->offsets[i - 1] + samplesSizes[i - 1]; |
611 | } |
612 | } |
613 | DISPLAYLEVEL(2, "Constructing partial suffix array\n"); |
614 | { |
615 | /* suffix is a partial suffix array. |
616 | * It only sorts suffixes by their first parameters.d bytes. |
617 | * The sort is stable, so each dmer group is sorted by position in input. |
618 | */ |
619 | U32 i; |
620 | for (i = 0; i < ctx->suffixSize; ++i) { |
621 | ctx->suffix[i] = i; |
622 | } |
623 | /* qsort doesn't take an opaque pointer, so pass as a global. |
624 | * On OpenBSD qsort() is not guaranteed to be stable, their mergesort() is. |
625 | */ |
626 | g_coverCtx = ctx; |
627 | #if defined(__OpenBSD__) |
628 | mergesort(ctx->suffix, ctx->suffixSize, sizeof(U32), |
629 | (ctx->d <= 8 ? &COVER_strict_cmp8 : &COVER_strict_cmp)); |
630 | #else |
631 | qsort(ctx->suffix, ctx->suffixSize, sizeof(U32), |
632 | (ctx->d <= 8 ? &COVER_strict_cmp8 : &COVER_strict_cmp)); |
633 | #endif |
634 | } |
635 | DISPLAYLEVEL(2, "Computing frequencies\n"); |
636 | /* For each dmer group (group of positions with the same first d bytes): |
637 | * 1. For each position we set dmerAt[position] = dmerID. The dmerID is |
638 | * (groupBeginPtr - suffix). This allows us to go from position to |
639 | * dmerID so we can look up values in freq. |
640 | * 2. We calculate how many samples the dmer occurs in and save it in |
641 | * freqs[dmerId]. |
642 | */ |
643 | COVER_groupBy(ctx->suffix, ctx->suffixSize, sizeof(U32), ctx, |
644 | (ctx->d <= 8 ? &COVER_cmp8 : &COVER_cmp), &COVER_group); |
645 | ctx->freqs = ctx->suffix; |
646 | ctx->suffix = NULL; |
647 | return 0; |
648 | } |
649 | |
650 | void COVER_warnOnSmallCorpus(size_t maxDictSize, size_t nbDmers, int displayLevel) |
651 | { |
652 | const double ratio = (double)nbDmers / (double)maxDictSize; |
653 | if (ratio >= 10) { |
654 | return; |
655 | } |
656 | LOCALDISPLAYLEVEL(displayLevel, 1, |
657 | "WARNING: The maximum dictionary size %u is too large " |
658 | "compared to the source size %u! " |
659 | "size(source)/size(dictionary) = %f, but it should be >= " |
660 | "10! This may lead to a subpar dictionary! We recommend " |
661 | "training on sources at least 10x, and preferably 100x " |
662 | "the size of the dictionary! \n", (U32)maxDictSize, |
663 | (U32)nbDmers, ratio); |
664 | } |
665 | |
666 | COVER_epoch_info_t COVER_computeEpochs(U32 maxDictSize, |
667 | U32 nbDmers, U32 k, U32 passes) |
668 | { |
669 | const U32 minEpochSize = k * 10; |
670 | COVER_epoch_info_t epochs; |
671 | epochs.num = MAX(1, maxDictSize / k / passes); |
672 | epochs.size = nbDmers / epochs.num; |
673 | if (epochs.size >= minEpochSize) { |
674 | assert(epochs.size * epochs.num <= nbDmers); |
675 | return epochs; |
676 | } |
677 | epochs.size = MIN(minEpochSize, nbDmers); |
678 | epochs.num = nbDmers / epochs.size; |
679 | assert(epochs.size * epochs.num <= nbDmers); |
680 | return epochs; |
681 | } |
682 | |
683 | /** |
684 | * Given the prepared context build the dictionary. |
685 | */ |
686 | static size_t COVER_buildDictionary(const COVER_ctx_t *ctx, U32 *freqs, |
687 | COVER_map_t *activeDmers, void *dictBuffer, |
688 | size_t dictBufferCapacity, |
689 | ZDICT_cover_params_t parameters) { |
690 | BYTE *const dict = (BYTE *)dictBuffer; |
691 | size_t tail = dictBufferCapacity; |
692 | /* Divide the data into epochs. We will select one segment from each epoch. */ |
693 | const COVER_epoch_info_t epochs = COVER_computeEpochs( |
694 | (U32)dictBufferCapacity, (U32)ctx->suffixSize, parameters.k, 4); |
695 | const size_t maxZeroScoreRun = MAX(10, MIN(100, epochs.num >> 3)); |
696 | size_t zeroScoreRun = 0; |
697 | size_t epoch; |
698 | DISPLAYLEVEL(2, "Breaking content into %u epochs of size %u\n", |
699 | (U32)epochs.num, (U32)epochs.size); |
700 | /* Loop through the epochs until there are no more segments or the dictionary |
701 | * is full. |
702 | */ |
703 | for (epoch = 0; tail > 0; epoch = (epoch + 1) % epochs.num) { |
704 | const U32 epochBegin = (U32)(epoch * epochs.size); |
705 | const U32 epochEnd = epochBegin + epochs.size; |
706 | size_t segmentSize; |
707 | /* Select a segment */ |
708 | COVER_segment_t segment = COVER_selectSegment( |
709 | ctx, freqs, activeDmers, epochBegin, epochEnd, parameters); |
710 | /* If the segment covers no dmers, then we are out of content. |
711 | * There may be new content in other epochs, for continue for some time. |
712 | */ |
713 | if (segment.score == 0) { |
714 | if (++zeroScoreRun >= maxZeroScoreRun) { |
715 | break; |
716 | } |
717 | continue; |
718 | } |
719 | zeroScoreRun = 0; |
720 | /* Trim the segment if necessary and if it is too small then we are done */ |
721 | segmentSize = MIN(segment.end - segment.begin + parameters.d - 1, tail); |
722 | if (segmentSize < parameters.d) { |
723 | break; |
724 | } |
725 | /* We fill the dictionary from the back to allow the best segments to be |
726 | * referenced with the smallest offsets. |
727 | */ |
728 | tail -= segmentSize; |
729 | memcpy(dict + tail, ctx->samples + segment.begin, segmentSize); |
730 | DISPLAYUPDATE( |
731 | 2, "\r%u%% ", |
732 | (unsigned)(((dictBufferCapacity - tail) * 100) / dictBufferCapacity)); |
733 | } |
734 | DISPLAYLEVEL(2, "\r%79s\r", ""); |
735 | return tail; |
736 | } |
737 | |
f535537f |
738 | ZDICTLIB_STATIC_API size_t ZDICT_trainFromBuffer_cover( |
648db22b |
739 | void *dictBuffer, size_t dictBufferCapacity, |
740 | const void *samplesBuffer, const size_t *samplesSizes, unsigned nbSamples, |
741 | ZDICT_cover_params_t parameters) |
742 | { |
743 | BYTE* const dict = (BYTE*)dictBuffer; |
744 | COVER_ctx_t ctx; |
745 | COVER_map_t activeDmers; |
746 | parameters.splitPoint = 1.0; |
747 | /* Initialize global data */ |
748 | g_displayLevel = (int)parameters.zParams.notificationLevel; |
749 | /* Checks */ |
750 | if (!COVER_checkParameters(parameters, dictBufferCapacity)) { |
751 | DISPLAYLEVEL(1, "Cover parameters incorrect\n"); |
752 | return ERROR(parameter_outOfBound); |
753 | } |
754 | if (nbSamples == 0) { |
755 | DISPLAYLEVEL(1, "Cover must have at least one input file\n"); |
756 | return ERROR(srcSize_wrong); |
757 | } |
758 | if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) { |
759 | DISPLAYLEVEL(1, "dictBufferCapacity must be at least %u\n", |
760 | ZDICT_DICTSIZE_MIN); |
761 | return ERROR(dstSize_tooSmall); |
762 | } |
763 | /* Initialize context and activeDmers */ |
764 | { |
765 | size_t const initVal = COVER_ctx_init(&ctx, samplesBuffer, samplesSizes, nbSamples, |
766 | parameters.d, parameters.splitPoint); |
767 | if (ZSTD_isError(initVal)) { |
768 | return initVal; |
769 | } |
770 | } |
771 | COVER_warnOnSmallCorpus(dictBufferCapacity, ctx.suffixSize, g_displayLevel); |
772 | if (!COVER_map_init(&activeDmers, parameters.k - parameters.d + 1)) { |
773 | DISPLAYLEVEL(1, "Failed to allocate dmer map: out of memory\n"); |
774 | COVER_ctx_destroy(&ctx); |
775 | return ERROR(memory_allocation); |
776 | } |
777 | |
778 | DISPLAYLEVEL(2, "Building dictionary\n"); |
779 | { |
780 | const size_t tail = |
781 | COVER_buildDictionary(&ctx, ctx.freqs, &activeDmers, dictBuffer, |
782 | dictBufferCapacity, parameters); |
783 | const size_t dictionarySize = ZDICT_finalizeDictionary( |
784 | dict, dictBufferCapacity, dict + tail, dictBufferCapacity - tail, |
785 | samplesBuffer, samplesSizes, nbSamples, parameters.zParams); |
786 | if (!ZSTD_isError(dictionarySize)) { |
787 | DISPLAYLEVEL(2, "Constructed dictionary of size %u\n", |
788 | (unsigned)dictionarySize); |
789 | } |
790 | COVER_ctx_destroy(&ctx); |
791 | COVER_map_destroy(&activeDmers); |
792 | return dictionarySize; |
793 | } |
794 | } |
795 | |
796 | |
797 | |
798 | size_t COVER_checkTotalCompressedSize(const ZDICT_cover_params_t parameters, |
799 | const size_t *samplesSizes, const BYTE *samples, |
800 | size_t *offsets, |
801 | size_t nbTrainSamples, size_t nbSamples, |
802 | BYTE *const dict, size_t dictBufferCapacity) { |
803 | size_t totalCompressedSize = ERROR(GENERIC); |
804 | /* Pointers */ |
805 | ZSTD_CCtx *cctx; |
806 | ZSTD_CDict *cdict; |
807 | void *dst; |
808 | /* Local variables */ |
809 | size_t dstCapacity; |
810 | size_t i; |
811 | /* Allocate dst with enough space to compress the maximum sized sample */ |
812 | { |
813 | size_t maxSampleSize = 0; |
814 | i = parameters.splitPoint < 1.0 ? nbTrainSamples : 0; |
815 | for (; i < nbSamples; ++i) { |
816 | maxSampleSize = MAX(samplesSizes[i], maxSampleSize); |
817 | } |
818 | dstCapacity = ZSTD_compressBound(maxSampleSize); |
819 | dst = malloc(dstCapacity); |
820 | } |
821 | /* Create the cctx and cdict */ |
822 | cctx = ZSTD_createCCtx(); |
823 | cdict = ZSTD_createCDict(dict, dictBufferCapacity, |
824 | parameters.zParams.compressionLevel); |
825 | if (!dst || !cctx || !cdict) { |
826 | goto _compressCleanup; |
827 | } |
828 | /* Compress each sample and sum their sizes (or error) */ |
829 | totalCompressedSize = dictBufferCapacity; |
830 | i = parameters.splitPoint < 1.0 ? nbTrainSamples : 0; |
831 | for (; i < nbSamples; ++i) { |
832 | const size_t size = ZSTD_compress_usingCDict( |
833 | cctx, dst, dstCapacity, samples + offsets[i], |
834 | samplesSizes[i], cdict); |
835 | if (ZSTD_isError(size)) { |
836 | totalCompressedSize = size; |
837 | goto _compressCleanup; |
838 | } |
839 | totalCompressedSize += size; |
840 | } |
841 | _compressCleanup: |
842 | ZSTD_freeCCtx(cctx); |
843 | ZSTD_freeCDict(cdict); |
844 | if (dst) { |
845 | free(dst); |
846 | } |
847 | return totalCompressedSize; |
848 | } |
849 | |
850 | |
851 | /** |
852 | * Initialize the `COVER_best_t`. |
853 | */ |
854 | void COVER_best_init(COVER_best_t *best) { |
855 | if (best==NULL) return; /* compatible with init on NULL */ |
856 | (void)ZSTD_pthread_mutex_init(&best->mutex, NULL); |
857 | (void)ZSTD_pthread_cond_init(&best->cond, NULL); |
858 | best->liveJobs = 0; |
859 | best->dict = NULL; |
860 | best->dictSize = 0; |
861 | best->compressedSize = (size_t)-1; |
862 | memset(&best->parameters, 0, sizeof(best->parameters)); |
863 | } |
864 | |
865 | /** |
866 | * Wait until liveJobs == 0. |
867 | */ |
868 | void COVER_best_wait(COVER_best_t *best) { |
869 | if (!best) { |
870 | return; |
871 | } |
872 | ZSTD_pthread_mutex_lock(&best->mutex); |
873 | while (best->liveJobs != 0) { |
874 | ZSTD_pthread_cond_wait(&best->cond, &best->mutex); |
875 | } |
876 | ZSTD_pthread_mutex_unlock(&best->mutex); |
877 | } |
878 | |
879 | /** |
880 | * Call COVER_best_wait() and then destroy the COVER_best_t. |
881 | */ |
882 | void COVER_best_destroy(COVER_best_t *best) { |
883 | if (!best) { |
884 | return; |
885 | } |
886 | COVER_best_wait(best); |
887 | if (best->dict) { |
888 | free(best->dict); |
889 | } |
890 | ZSTD_pthread_mutex_destroy(&best->mutex); |
891 | ZSTD_pthread_cond_destroy(&best->cond); |
892 | } |
893 | |
894 | /** |
895 | * Called when a thread is about to be launched. |
896 | * Increments liveJobs. |
897 | */ |
898 | void COVER_best_start(COVER_best_t *best) { |
899 | if (!best) { |
900 | return; |
901 | } |
902 | ZSTD_pthread_mutex_lock(&best->mutex); |
903 | ++best->liveJobs; |
904 | ZSTD_pthread_mutex_unlock(&best->mutex); |
905 | } |
906 | |
907 | /** |
908 | * Called when a thread finishes executing, both on error or success. |
909 | * Decrements liveJobs and signals any waiting threads if liveJobs == 0. |
910 | * If this dictionary is the best so far save it and its parameters. |
911 | */ |
f535537f |
912 | void COVER_best_finish(COVER_best_t* best, |
913 | ZDICT_cover_params_t parameters, |
914 | COVER_dictSelection_t selection) |
915 | { |
648db22b |
916 | void* dict = selection.dictContent; |
917 | size_t compressedSize = selection.totalCompressedSize; |
918 | size_t dictSize = selection.dictSize; |
919 | if (!best) { |
920 | return; |
921 | } |
922 | { |
923 | size_t liveJobs; |
924 | ZSTD_pthread_mutex_lock(&best->mutex); |
925 | --best->liveJobs; |
926 | liveJobs = best->liveJobs; |
927 | /* If the new dictionary is better */ |
928 | if (compressedSize < best->compressedSize) { |
929 | /* Allocate space if necessary */ |
930 | if (!best->dict || best->dictSize < dictSize) { |
931 | if (best->dict) { |
932 | free(best->dict); |
933 | } |
934 | best->dict = malloc(dictSize); |
935 | if (!best->dict) { |
936 | best->compressedSize = ERROR(GENERIC); |
937 | best->dictSize = 0; |
938 | ZSTD_pthread_cond_signal(&best->cond); |
939 | ZSTD_pthread_mutex_unlock(&best->mutex); |
940 | return; |
941 | } |
942 | } |
943 | /* Save the dictionary, parameters, and size */ |
944 | if (dict) { |
945 | memcpy(best->dict, dict, dictSize); |
946 | best->dictSize = dictSize; |
947 | best->parameters = parameters; |
948 | best->compressedSize = compressedSize; |
949 | } |
950 | } |
951 | if (liveJobs == 0) { |
952 | ZSTD_pthread_cond_broadcast(&best->cond); |
953 | } |
954 | ZSTD_pthread_mutex_unlock(&best->mutex); |
955 | } |
956 | } |
957 | |
958 | static COVER_dictSelection_t setDictSelection(BYTE* buf, size_t s, size_t csz) |
959 | { |
960 | COVER_dictSelection_t ds; |
961 | ds.dictContent = buf; |
962 | ds.dictSize = s; |
963 | ds.totalCompressedSize = csz; |
964 | return ds; |
965 | } |
966 | |
967 | COVER_dictSelection_t COVER_dictSelectionError(size_t error) { |
968 | return setDictSelection(NULL, 0, error); |
969 | } |
970 | |
971 | unsigned COVER_dictSelectionIsError(COVER_dictSelection_t selection) { |
972 | return (ZSTD_isError(selection.totalCompressedSize) || !selection.dictContent); |
973 | } |
974 | |
975 | void COVER_dictSelectionFree(COVER_dictSelection_t selection){ |
976 | free(selection.dictContent); |
977 | } |
978 | |
979 | COVER_dictSelection_t COVER_selectDict(BYTE* customDictContent, size_t dictBufferCapacity, |
980 | size_t dictContentSize, const BYTE* samplesBuffer, const size_t* samplesSizes, unsigned nbFinalizeSamples, |
981 | size_t nbCheckSamples, size_t nbSamples, ZDICT_cover_params_t params, size_t* offsets, size_t totalCompressedSize) { |
982 | |
983 | size_t largestDict = 0; |
984 | size_t largestCompressed = 0; |
985 | BYTE* customDictContentEnd = customDictContent + dictContentSize; |
986 | |
f535537f |
987 | BYTE* largestDictbuffer = (BYTE*)malloc(dictBufferCapacity); |
988 | BYTE* candidateDictBuffer = (BYTE*)malloc(dictBufferCapacity); |
648db22b |
989 | double regressionTolerance = ((double)params.shrinkDictMaxRegression / 100.0) + 1.00; |
990 | |
991 | if (!largestDictbuffer || !candidateDictBuffer) { |
992 | free(largestDictbuffer); |
993 | free(candidateDictBuffer); |
994 | return COVER_dictSelectionError(dictContentSize); |
995 | } |
996 | |
997 | /* Initial dictionary size and compressed size */ |
998 | memcpy(largestDictbuffer, customDictContent, dictContentSize); |
999 | dictContentSize = ZDICT_finalizeDictionary( |
1000 | largestDictbuffer, dictBufferCapacity, customDictContent, dictContentSize, |
1001 | samplesBuffer, samplesSizes, nbFinalizeSamples, params.zParams); |
1002 | |
1003 | if (ZDICT_isError(dictContentSize)) { |
1004 | free(largestDictbuffer); |
1005 | free(candidateDictBuffer); |
1006 | return COVER_dictSelectionError(dictContentSize); |
1007 | } |
1008 | |
1009 | totalCompressedSize = COVER_checkTotalCompressedSize(params, samplesSizes, |
1010 | samplesBuffer, offsets, |
1011 | nbCheckSamples, nbSamples, |
1012 | largestDictbuffer, dictContentSize); |
1013 | |
1014 | if (ZSTD_isError(totalCompressedSize)) { |
1015 | free(largestDictbuffer); |
1016 | free(candidateDictBuffer); |
1017 | return COVER_dictSelectionError(totalCompressedSize); |
1018 | } |
1019 | |
1020 | if (params.shrinkDict == 0) { |
1021 | free(candidateDictBuffer); |
1022 | return setDictSelection(largestDictbuffer, dictContentSize, totalCompressedSize); |
1023 | } |
1024 | |
1025 | largestDict = dictContentSize; |
1026 | largestCompressed = totalCompressedSize; |
1027 | dictContentSize = ZDICT_DICTSIZE_MIN; |
1028 | |
1029 | /* Largest dict is initially at least ZDICT_DICTSIZE_MIN */ |
1030 | while (dictContentSize < largestDict) { |
1031 | memcpy(candidateDictBuffer, largestDictbuffer, largestDict); |
1032 | dictContentSize = ZDICT_finalizeDictionary( |
1033 | candidateDictBuffer, dictBufferCapacity, customDictContentEnd - dictContentSize, dictContentSize, |
1034 | samplesBuffer, samplesSizes, nbFinalizeSamples, params.zParams); |
1035 | |
1036 | if (ZDICT_isError(dictContentSize)) { |
1037 | free(largestDictbuffer); |
1038 | free(candidateDictBuffer); |
1039 | return COVER_dictSelectionError(dictContentSize); |
1040 | |
1041 | } |
1042 | |
1043 | totalCompressedSize = COVER_checkTotalCompressedSize(params, samplesSizes, |
1044 | samplesBuffer, offsets, |
1045 | nbCheckSamples, nbSamples, |
1046 | candidateDictBuffer, dictContentSize); |
1047 | |
1048 | if (ZSTD_isError(totalCompressedSize)) { |
1049 | free(largestDictbuffer); |
1050 | free(candidateDictBuffer); |
1051 | return COVER_dictSelectionError(totalCompressedSize); |
1052 | } |
1053 | |
1054 | if ((double)totalCompressedSize <= (double)largestCompressed * regressionTolerance) { |
1055 | free(largestDictbuffer); |
1056 | return setDictSelection( candidateDictBuffer, dictContentSize, totalCompressedSize ); |
1057 | } |
1058 | dictContentSize *= 2; |
1059 | } |
1060 | dictContentSize = largestDict; |
1061 | totalCompressedSize = largestCompressed; |
1062 | free(candidateDictBuffer); |
1063 | return setDictSelection( largestDictbuffer, dictContentSize, totalCompressedSize ); |
1064 | } |
1065 | |
1066 | /** |
1067 | * Parameters for COVER_tryParameters(). |
1068 | */ |
1069 | typedef struct COVER_tryParameters_data_s { |
1070 | const COVER_ctx_t *ctx; |
1071 | COVER_best_t *best; |
1072 | size_t dictBufferCapacity; |
1073 | ZDICT_cover_params_t parameters; |
1074 | } COVER_tryParameters_data_t; |
1075 | |
1076 | /** |
1077 | * Tries a set of parameters and updates the COVER_best_t with the results. |
1078 | * This function is thread safe if zstd is compiled with multithreaded support. |
1079 | * It takes its parameters as an *OWNING* opaque pointer to support threading. |
1080 | */ |
1081 | static void COVER_tryParameters(void *opaque) |
1082 | { |
1083 | /* Save parameters as local variables */ |
1084 | COVER_tryParameters_data_t *const data = (COVER_tryParameters_data_t*)opaque; |
1085 | const COVER_ctx_t *const ctx = data->ctx; |
1086 | const ZDICT_cover_params_t parameters = data->parameters; |
1087 | size_t dictBufferCapacity = data->dictBufferCapacity; |
1088 | size_t totalCompressedSize = ERROR(GENERIC); |
1089 | /* Allocate space for hash table, dict, and freqs */ |
1090 | COVER_map_t activeDmers; |
1091 | BYTE* const dict = (BYTE*)malloc(dictBufferCapacity); |
1092 | COVER_dictSelection_t selection = COVER_dictSelectionError(ERROR(GENERIC)); |
1093 | U32* const freqs = (U32*)malloc(ctx->suffixSize * sizeof(U32)); |
1094 | if (!COVER_map_init(&activeDmers, parameters.k - parameters.d + 1)) { |
1095 | DISPLAYLEVEL(1, "Failed to allocate dmer map: out of memory\n"); |
1096 | goto _cleanup; |
1097 | } |
1098 | if (!dict || !freqs) { |
1099 | DISPLAYLEVEL(1, "Failed to allocate buffers: out of memory\n"); |
1100 | goto _cleanup; |
1101 | } |
1102 | /* Copy the frequencies because we need to modify them */ |
1103 | memcpy(freqs, ctx->freqs, ctx->suffixSize * sizeof(U32)); |
1104 | /* Build the dictionary */ |
1105 | { |
1106 | const size_t tail = COVER_buildDictionary(ctx, freqs, &activeDmers, dict, |
1107 | dictBufferCapacity, parameters); |
1108 | selection = COVER_selectDict(dict + tail, dictBufferCapacity, dictBufferCapacity - tail, |
1109 | ctx->samples, ctx->samplesSizes, (unsigned)ctx->nbTrainSamples, ctx->nbTrainSamples, ctx->nbSamples, parameters, ctx->offsets, |
1110 | totalCompressedSize); |
1111 | |
1112 | if (COVER_dictSelectionIsError(selection)) { |
1113 | DISPLAYLEVEL(1, "Failed to select dictionary\n"); |
1114 | goto _cleanup; |
1115 | } |
1116 | } |
1117 | _cleanup: |
1118 | free(dict); |
1119 | COVER_best_finish(data->best, parameters, selection); |
1120 | free(data); |
1121 | COVER_map_destroy(&activeDmers); |
1122 | COVER_dictSelectionFree(selection); |
1123 | free(freqs); |
1124 | } |
1125 | |
f535537f |
1126 | ZDICTLIB_STATIC_API size_t ZDICT_optimizeTrainFromBuffer_cover( |
648db22b |
1127 | void* dictBuffer, size_t dictBufferCapacity, const void* samplesBuffer, |
1128 | const size_t* samplesSizes, unsigned nbSamples, |
1129 | ZDICT_cover_params_t* parameters) |
1130 | { |
1131 | /* constants */ |
1132 | const unsigned nbThreads = parameters->nbThreads; |
1133 | const double splitPoint = |
1134 | parameters->splitPoint <= 0.0 ? COVER_DEFAULT_SPLITPOINT : parameters->splitPoint; |
1135 | const unsigned kMinD = parameters->d == 0 ? 6 : parameters->d; |
1136 | const unsigned kMaxD = parameters->d == 0 ? 8 : parameters->d; |
1137 | const unsigned kMinK = parameters->k == 0 ? 50 : parameters->k; |
1138 | const unsigned kMaxK = parameters->k == 0 ? 2000 : parameters->k; |
1139 | const unsigned kSteps = parameters->steps == 0 ? 40 : parameters->steps; |
1140 | const unsigned kStepSize = MAX((kMaxK - kMinK) / kSteps, 1); |
1141 | const unsigned kIterations = |
1142 | (1 + (kMaxD - kMinD) / 2) * (1 + (kMaxK - kMinK) / kStepSize); |
1143 | const unsigned shrinkDict = 0; |
1144 | /* Local variables */ |
1145 | const int displayLevel = parameters->zParams.notificationLevel; |
1146 | unsigned iteration = 1; |
1147 | unsigned d; |
1148 | unsigned k; |
1149 | COVER_best_t best; |
1150 | POOL_ctx *pool = NULL; |
1151 | int warned = 0; |
1152 | |
1153 | /* Checks */ |
1154 | if (splitPoint <= 0 || splitPoint > 1) { |
1155 | LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect parameters\n"); |
1156 | return ERROR(parameter_outOfBound); |
1157 | } |
1158 | if (kMinK < kMaxD || kMaxK < kMinK) { |
1159 | LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect parameters\n"); |
1160 | return ERROR(parameter_outOfBound); |
1161 | } |
1162 | if (nbSamples == 0) { |
1163 | DISPLAYLEVEL(1, "Cover must have at least one input file\n"); |
1164 | return ERROR(srcSize_wrong); |
1165 | } |
1166 | if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) { |
1167 | DISPLAYLEVEL(1, "dictBufferCapacity must be at least %u\n", |
1168 | ZDICT_DICTSIZE_MIN); |
1169 | return ERROR(dstSize_tooSmall); |
1170 | } |
1171 | if (nbThreads > 1) { |
1172 | pool = POOL_create(nbThreads, 1); |
1173 | if (!pool) { |
1174 | return ERROR(memory_allocation); |
1175 | } |
1176 | } |
1177 | /* Initialization */ |
1178 | COVER_best_init(&best); |
1179 | /* Turn down global display level to clean up display at level 2 and below */ |
1180 | g_displayLevel = displayLevel == 0 ? 0 : displayLevel - 1; |
1181 | /* Loop through d first because each new value needs a new context */ |
1182 | LOCALDISPLAYLEVEL(displayLevel, 2, "Trying %u different sets of parameters\n", |
1183 | kIterations); |
1184 | for (d = kMinD; d <= kMaxD; d += 2) { |
1185 | /* Initialize the context for this value of d */ |
1186 | COVER_ctx_t ctx; |
1187 | LOCALDISPLAYLEVEL(displayLevel, 3, "d=%u\n", d); |
1188 | { |
1189 | const size_t initVal = COVER_ctx_init(&ctx, samplesBuffer, samplesSizes, nbSamples, d, splitPoint); |
1190 | if (ZSTD_isError(initVal)) { |
1191 | LOCALDISPLAYLEVEL(displayLevel, 1, "Failed to initialize context\n"); |
1192 | COVER_best_destroy(&best); |
1193 | POOL_free(pool); |
1194 | return initVal; |
1195 | } |
1196 | } |
1197 | if (!warned) { |
1198 | COVER_warnOnSmallCorpus(dictBufferCapacity, ctx.suffixSize, displayLevel); |
1199 | warned = 1; |
1200 | } |
1201 | /* Loop through k reusing the same context */ |
1202 | for (k = kMinK; k <= kMaxK; k += kStepSize) { |
1203 | /* Prepare the arguments */ |
1204 | COVER_tryParameters_data_t *data = (COVER_tryParameters_data_t *)malloc( |
1205 | sizeof(COVER_tryParameters_data_t)); |
1206 | LOCALDISPLAYLEVEL(displayLevel, 3, "k=%u\n", k); |
1207 | if (!data) { |
1208 | LOCALDISPLAYLEVEL(displayLevel, 1, "Failed to allocate parameters\n"); |
1209 | COVER_best_destroy(&best); |
1210 | COVER_ctx_destroy(&ctx); |
1211 | POOL_free(pool); |
1212 | return ERROR(memory_allocation); |
1213 | } |
1214 | data->ctx = &ctx; |
1215 | data->best = &best; |
1216 | data->dictBufferCapacity = dictBufferCapacity; |
1217 | data->parameters = *parameters; |
1218 | data->parameters.k = k; |
1219 | data->parameters.d = d; |
1220 | data->parameters.splitPoint = splitPoint; |
1221 | data->parameters.steps = kSteps; |
1222 | data->parameters.shrinkDict = shrinkDict; |
1223 | data->parameters.zParams.notificationLevel = g_displayLevel; |
1224 | /* Check the parameters */ |
1225 | if (!COVER_checkParameters(data->parameters, dictBufferCapacity)) { |
1226 | DISPLAYLEVEL(1, "Cover parameters incorrect\n"); |
1227 | free(data); |
1228 | continue; |
1229 | } |
1230 | /* Call the function and pass ownership of data to it */ |
1231 | COVER_best_start(&best); |
1232 | if (pool) { |
1233 | POOL_add(pool, &COVER_tryParameters, data); |
1234 | } else { |
1235 | COVER_tryParameters(data); |
1236 | } |
1237 | /* Print status */ |
1238 | LOCALDISPLAYUPDATE(displayLevel, 2, "\r%u%% ", |
1239 | (unsigned)((iteration * 100) / kIterations)); |
1240 | ++iteration; |
1241 | } |
1242 | COVER_best_wait(&best); |
1243 | COVER_ctx_destroy(&ctx); |
1244 | } |
1245 | LOCALDISPLAYLEVEL(displayLevel, 2, "\r%79s\r", ""); |
1246 | /* Fill the output buffer and parameters with output of the best parameters */ |
1247 | { |
1248 | const size_t dictSize = best.dictSize; |
1249 | if (ZSTD_isError(best.compressedSize)) { |
1250 | const size_t compressedSize = best.compressedSize; |
1251 | COVER_best_destroy(&best); |
1252 | POOL_free(pool); |
1253 | return compressedSize; |
1254 | } |
1255 | *parameters = best.parameters; |
1256 | memcpy(dictBuffer, best.dict, dictSize); |
1257 | COVER_best_destroy(&best); |
1258 | POOL_free(pool); |
1259 | return dictSize; |
1260 | } |
1261 | } |