2 * Copyright (c) 2018-2020, Facebook, Inc.
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.
11 /*-*************************************
13 ***************************************/
14 #include <stdio.h> /* fprintf */
15 #include <stdlib.h> /* malloc, free, qsort */
16 #include <string.h> /* memset */
17 #include <time.h> /* clock */
19 #include "../common/mem.h" /* read */
20 #include "../common/pool.h"
21 #include "../common/threading.h"
23 #include "../common/zstd_internal.h" /* includes zstd.h */
24 #ifndef ZDICT_STATIC_LINKING_ONLY
25 #define ZDICT_STATIC_LINKING_ONLY
30 /*-*************************************
32 ***************************************/
33 #define FASTCOVER_MAX_SAMPLES_SIZE (sizeof(size_t) == 8 ? ((unsigned)-1) : ((unsigned)1 GB))
34 #define FASTCOVER_MAX_F 31
35 #define FASTCOVER_MAX_ACCEL 10
36 #define DEFAULT_SPLITPOINT 0.75
38 #define DEFAULT_ACCEL 1
41 /*-*************************************
43 ***************************************/
44 static int g_displayLevel = 2;
45 #define DISPLAY(...) \
47 fprintf(stderr, __VA_ARGS__); \
50 #define LOCALDISPLAYLEVEL(displayLevel, l, ...) \
51 if (displayLevel >= l) { \
52 DISPLAY(__VA_ARGS__); \
53 } /* 0 : no display; 1: errors; 2: default; 3: details; 4: debug */
54 #define DISPLAYLEVEL(l, ...) LOCALDISPLAYLEVEL(g_displayLevel, l, __VA_ARGS__)
56 #define LOCALDISPLAYUPDATE(displayLevel, l, ...) \
57 if (displayLevel >= l) { \
58 if ((clock() - g_time > refreshRate) || (displayLevel >= 4)) { \
60 DISPLAY(__VA_ARGS__); \
63 #define DISPLAYUPDATE(l, ...) LOCALDISPLAYUPDATE(g_displayLevel, l, __VA_ARGS__)
64 static const clock_t refreshRate = CLOCKS_PER_SEC * 15 / 100;
65 static clock_t g_time = 0;
68 /*-*************************************
70 ***************************************/
71 static const U64 prime6bytes = 227718039650203ULL;
72 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; }
73 static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
75 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
76 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
77 static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
81 * Hash the d-byte value pointed to by p and mod 2^f
83 static size_t FASTCOVER_hashPtrToIndex(const void* p, U32 h, unsigned d) {
85 return ZSTD_hash6Ptr(p, h) & ((1 << h) - 1);
87 return ZSTD_hash8Ptr(p, h) & ((1 << h) - 1);
91 /*-*************************************
93 ***************************************/
95 unsigned finalize; /* Percentage of training samples used for ZDICT_finalizeDictionary */
96 unsigned skip; /* Number of dmer skipped between each dmer counted in computeFrequency */
100 static const FASTCOVER_accel_t FASTCOVER_defaultAccelParameters[FASTCOVER_MAX_ACCEL+1] = {
101 { 100, 0 }, /* accel = 0, should not happen because accel = 0 defaults to accel = 1 */
102 { 100, 0 }, /* accel = 1 */
103 { 50, 1 }, /* accel = 2 */
104 { 34, 2 }, /* accel = 3 */
105 { 25, 3 }, /* accel = 4 */
106 { 20, 4 }, /* accel = 5 */
107 { 17, 5 }, /* accel = 6 */
108 { 14, 6 }, /* accel = 7 */
109 { 13, 7 }, /* accel = 8 */
110 { 11, 8 }, /* accel = 9 */
111 { 10, 9 }, /* accel = 10 */
115 /*-*************************************
117 ***************************************/
121 const size_t *samplesSizes;
123 size_t nbTrainSamples;
124 size_t nbTestSamples;
129 FASTCOVER_accel_t accelParams;
133 /*-*************************************
135 ***************************************/
137 * Selects the best segment in an epoch.
138 * Segments of are scored according to the function:
140 * Let F(d) be the frequency of all dmers with hash value d.
141 * Let S_i be hash value of the dmer at position i of segment S which has length k.
143 * Score(S) = F(S_1) + F(S_2) + ... + F(S_{k-d+1})
145 * Once the dmer with hash value d is in the dictionary we set F(d) = 0.
147 static COVER_segment_t FASTCOVER_selectSegment(const FASTCOVER_ctx_t *ctx,
148 U32 *freqs, U32 begin, U32 end,
149 ZDICT_cover_params_t parameters,
152 const U32 k = parameters.k;
153 const U32 d = parameters.d;
154 const U32 f = ctx->f;
155 const U32 dmersInK = k - d + 1;
157 /* Try each segment (activeSegment) and save the best (bestSegment) */
158 COVER_segment_t bestSegment = {0, 0, 0};
159 COVER_segment_t activeSegment;
161 /* Reset the activeDmers in the segment */
162 /* The activeSegment starts at the beginning of the epoch. */
163 activeSegment.begin = begin;
164 activeSegment.end = begin;
165 activeSegment.score = 0;
167 /* Slide the activeSegment through the whole epoch.
168 * Save the best segment in bestSegment.
170 while (activeSegment.end < end) {
171 /* Get hash value of current dmer */
172 const size_t idx = FASTCOVER_hashPtrToIndex(ctx->samples + activeSegment.end, f, d);
174 /* Add frequency of this index to score if this is the first occurrence of index in active segment */
175 if (segmentFreqs[idx] == 0) {
176 activeSegment.score += freqs[idx];
178 /* Increment end of segment and segmentFreqs*/
179 activeSegment.end += 1;
180 segmentFreqs[idx] += 1;
181 /* If the window is now too large, drop the first position */
182 if (activeSegment.end - activeSegment.begin == dmersInK + 1) {
183 /* Get hash value of the dmer to be eliminated from active segment */
184 const size_t delIndex = FASTCOVER_hashPtrToIndex(ctx->samples + activeSegment.begin, f, d);
185 segmentFreqs[delIndex] -= 1;
186 /* Subtract frequency of this index from score if this is the last occurrence of this index in active segment */
187 if (segmentFreqs[delIndex] == 0) {
188 activeSegment.score -= freqs[delIndex];
190 /* Increment start of segment */
191 activeSegment.begin += 1;
194 /* If this segment is the best so far save it */
195 if (activeSegment.score > bestSegment.score) {
196 bestSegment = activeSegment;
200 /* Zero out rest of segmentFreqs array */
201 while (activeSegment.begin < end) {
202 const size_t delIndex = FASTCOVER_hashPtrToIndex(ctx->samples + activeSegment.begin, f, d);
203 segmentFreqs[delIndex] -= 1;
204 activeSegment.begin += 1;
208 /* Zero the frequency of hash value of each dmer covered by the chosen segment. */
210 for (pos = bestSegment.begin; pos != bestSegment.end; ++pos) {
211 const size_t i = FASTCOVER_hashPtrToIndex(ctx->samples + pos, f, d);
220 static int FASTCOVER_checkParameters(ZDICT_cover_params_t parameters,
221 size_t maxDictSize, unsigned f,
223 /* k, d, and f are required parameters */
224 if (parameters.d == 0 || parameters.k == 0) {
227 /* d has to be 6 or 8 */
228 if (parameters.d != 6 && parameters.d != 8) {
231 /* k <= maxDictSize */
232 if (parameters.k > maxDictSize) {
236 if (parameters.d > parameters.k) {
239 /* 0 < f <= FASTCOVER_MAX_F*/
240 if (f > FASTCOVER_MAX_F || f == 0) {
243 /* 0 < splitPoint <= 1 */
244 if (parameters.splitPoint <= 0 || parameters.splitPoint > 1) {
247 /* 0 < accel <= 10 */
248 if (accel > 10 || accel == 0) {
256 * Clean up a context initialized with `FASTCOVER_ctx_init()`.
259 FASTCOVER_ctx_destroy(FASTCOVER_ctx_t* ctx)
272 * Calculate for frequency of hash value of each dmer in ctx->samples
275 FASTCOVER_computeFrequency(U32* freqs, const FASTCOVER_ctx_t* ctx)
277 const unsigned f = ctx->f;
278 const unsigned d = ctx->d;
279 const unsigned skip = ctx->accelParams.skip;
280 const unsigned readLength = MAX(d, 8);
282 assert(ctx->nbTrainSamples >= 5);
283 assert(ctx->nbTrainSamples <= ctx->nbSamples);
284 for (i = 0; i < ctx->nbTrainSamples; i++) {
285 size_t start = ctx->offsets[i]; /* start of current dmer */
286 size_t const currSampleEnd = ctx->offsets[i+1];
287 while (start + readLength <= currSampleEnd) {
288 const size_t dmerIndex = FASTCOVER_hashPtrToIndex(ctx->samples + start, f, d);
290 start = start + skip + 1;
297 * Prepare a context for dictionary building.
298 * The context is only dependent on the parameter `d` and can used multiple
300 * Returns 0 on success or error code on error.
301 * The context must be destroyed with `FASTCOVER_ctx_destroy()`.
304 FASTCOVER_ctx_init(FASTCOVER_ctx_t* ctx,
305 const void* samplesBuffer,
306 const size_t* samplesSizes, unsigned nbSamples,
307 unsigned d, double splitPoint, unsigned f,
308 FASTCOVER_accel_t accelParams)
310 const BYTE* const samples = (const BYTE*)samplesBuffer;
311 const size_t totalSamplesSize = COVER_sum(samplesSizes, nbSamples);
312 /* Split samples into testing and training sets */
313 const unsigned nbTrainSamples = splitPoint < 1.0 ? (unsigned)((double)nbSamples * splitPoint) : nbSamples;
314 const unsigned nbTestSamples = splitPoint < 1.0 ? nbSamples - nbTrainSamples : nbSamples;
315 const size_t trainingSamplesSize = splitPoint < 1.0 ? COVER_sum(samplesSizes, nbTrainSamples) : totalSamplesSize;
316 const size_t testSamplesSize = splitPoint < 1.0 ? COVER_sum(samplesSizes + nbTrainSamples, nbTestSamples) : totalSamplesSize;
319 if (totalSamplesSize < MAX(d, sizeof(U64)) ||
320 totalSamplesSize >= (size_t)FASTCOVER_MAX_SAMPLES_SIZE) {
321 DISPLAYLEVEL(1, "Total samples size is too large (%u MB), maximum size is %u MB\n",
322 (unsigned)(totalSamplesSize >> 20), (FASTCOVER_MAX_SAMPLES_SIZE >> 20));
323 return ERROR(srcSize_wrong);
326 /* Check if there are at least 5 training samples */
327 if (nbTrainSamples < 5) {
328 DISPLAYLEVEL(1, "Total number of training samples is %u and is invalid\n", nbTrainSamples);
329 return ERROR(srcSize_wrong);
332 /* Check if there's testing sample */
333 if (nbTestSamples < 1) {
334 DISPLAYLEVEL(1, "Total number of testing samples is %u and is invalid.\n", nbTestSamples);
335 return ERROR(srcSize_wrong);
338 /* Zero the context */
339 memset(ctx, 0, sizeof(*ctx));
340 DISPLAYLEVEL(2, "Training on %u samples of total size %u\n", nbTrainSamples,
341 (unsigned)trainingSamplesSize);
342 DISPLAYLEVEL(2, "Testing on %u samples of total size %u\n", nbTestSamples,
343 (unsigned)testSamplesSize);
345 ctx->samples = samples;
346 ctx->samplesSizes = samplesSizes;
347 ctx->nbSamples = nbSamples;
348 ctx->nbTrainSamples = nbTrainSamples;
349 ctx->nbTestSamples = nbTestSamples;
350 ctx->nbDmers = trainingSamplesSize - MAX(d, sizeof(U64)) + 1;
353 ctx->accelParams = accelParams;
355 /* The offsets of each file */
356 ctx->offsets = (size_t*)calloc((nbSamples + 1), sizeof(size_t));
357 if (ctx->offsets == NULL) {
358 DISPLAYLEVEL(1, "Failed to allocate scratch buffers \n");
359 FASTCOVER_ctx_destroy(ctx);
360 return ERROR(memory_allocation);
363 /* Fill offsets from the samplesSizes */
366 assert(nbSamples >= 5);
367 for (i = 1; i <= nbSamples; ++i) {
368 ctx->offsets[i] = ctx->offsets[i - 1] + samplesSizes[i - 1];
372 /* Initialize frequency array of size 2^f */
373 ctx->freqs = (U32*)calloc(((U64)1 << f), sizeof(U32));
374 if (ctx->freqs == NULL) {
375 DISPLAYLEVEL(1, "Failed to allocate frequency table \n");
376 FASTCOVER_ctx_destroy(ctx);
377 return ERROR(memory_allocation);
380 DISPLAYLEVEL(2, "Computing frequencies\n");
381 FASTCOVER_computeFrequency(ctx->freqs, ctx);
388 * Given the prepared context build the dictionary.
391 FASTCOVER_buildDictionary(const FASTCOVER_ctx_t* ctx,
393 void* dictBuffer, size_t dictBufferCapacity,
394 ZDICT_cover_params_t parameters,
397 BYTE *const dict = (BYTE *)dictBuffer;
398 size_t tail = dictBufferCapacity;
399 /* Divide the data into epochs. We will select one segment from each epoch. */
400 const COVER_epoch_info_t epochs = COVER_computeEpochs(
401 (U32)dictBufferCapacity, (U32)ctx->nbDmers, parameters.k, 1);
402 const size_t maxZeroScoreRun = 10;
403 size_t zeroScoreRun = 0;
405 DISPLAYLEVEL(2, "Breaking content into %u epochs of size %u\n",
406 (U32)epochs.num, (U32)epochs.size);
407 /* Loop through the epochs until there are no more segments or the dictionary
410 for (epoch = 0; tail > 0; epoch = (epoch + 1) % epochs.num) {
411 const U32 epochBegin = (U32)(epoch * epochs.size);
412 const U32 epochEnd = epochBegin + epochs.size;
414 /* Select a segment */
415 COVER_segment_t segment = FASTCOVER_selectSegment(
416 ctx, freqs, epochBegin, epochEnd, parameters, segmentFreqs);
418 /* If the segment covers no dmers, then we are out of content.
419 * There may be new content in other epochs, for continue for some time.
421 if (segment.score == 0) {
422 if (++zeroScoreRun >= maxZeroScoreRun) {
429 /* Trim the segment if necessary and if it is too small then we are done */
430 segmentSize = MIN(segment.end - segment.begin + parameters.d - 1, tail);
431 if (segmentSize < parameters.d) {
435 /* We fill the dictionary from the back to allow the best segments to be
436 * referenced with the smallest offsets.
439 memcpy(dict + tail, ctx->samples + segment.begin, segmentSize);
442 (unsigned)(((dictBufferCapacity - tail) * 100) / dictBufferCapacity));
444 DISPLAYLEVEL(2, "\r%79s\r", "");
449 * Parameters for FASTCOVER_tryParameters().
451 typedef struct FASTCOVER_tryParameters_data_s {
452 const FASTCOVER_ctx_t* ctx;
454 size_t dictBufferCapacity;
455 ZDICT_cover_params_t parameters;
456 } FASTCOVER_tryParameters_data_t;
460 * Tries a set of parameters and updates the COVER_best_t with the results.
461 * This function is thread safe if zstd is compiled with multithreaded support.
462 * It takes its parameters as an *OWNING* opaque pointer to support threading.
464 static void FASTCOVER_tryParameters(void *opaque)
466 /* Save parameters as local variables */
467 FASTCOVER_tryParameters_data_t *const data = (FASTCOVER_tryParameters_data_t *)opaque;
468 const FASTCOVER_ctx_t *const ctx = data->ctx;
469 const ZDICT_cover_params_t parameters = data->parameters;
470 size_t dictBufferCapacity = data->dictBufferCapacity;
471 size_t totalCompressedSize = ERROR(GENERIC);
472 /* Initialize array to keep track of frequency of dmer within activeSegment */
473 U16* segmentFreqs = (U16 *)calloc(((U64)1 << ctx->f), sizeof(U16));
474 /* Allocate space for hash table, dict, and freqs */
475 BYTE *const dict = (BYTE * const)malloc(dictBufferCapacity);
476 COVER_dictSelection_t selection = COVER_dictSelectionError(ERROR(GENERIC));
477 U32 *freqs = (U32*) malloc(((U64)1 << ctx->f) * sizeof(U32));
478 if (!segmentFreqs || !dict || !freqs) {
479 DISPLAYLEVEL(1, "Failed to allocate buffers: out of memory\n");
482 /* Copy the frequencies because we need to modify them */
483 memcpy(freqs, ctx->freqs, ((U64)1 << ctx->f) * sizeof(U32));
484 /* Build the dictionary */
485 { const size_t tail = FASTCOVER_buildDictionary(ctx, freqs, dict, dictBufferCapacity,
486 parameters, segmentFreqs);
488 const unsigned nbFinalizeSamples = (unsigned)(ctx->nbTrainSamples * ctx->accelParams.finalize / 100);
489 selection = COVER_selectDict(dict + tail, dictBufferCapacity - tail,
490 ctx->samples, ctx->samplesSizes, nbFinalizeSamples, ctx->nbTrainSamples, ctx->nbSamples, parameters, ctx->offsets,
491 totalCompressedSize);
493 if (COVER_dictSelectionIsError(selection)) {
494 DISPLAYLEVEL(1, "Failed to select dictionary\n");
500 COVER_best_finish(data->best, parameters, selection);
503 COVER_dictSelectionFree(selection);
509 FASTCOVER_convertToCoverParams(ZDICT_fastCover_params_t fastCoverParams,
510 ZDICT_cover_params_t* coverParams)
512 coverParams->k = fastCoverParams.k;
513 coverParams->d = fastCoverParams.d;
514 coverParams->steps = fastCoverParams.steps;
515 coverParams->nbThreads = fastCoverParams.nbThreads;
516 coverParams->splitPoint = fastCoverParams.splitPoint;
517 coverParams->zParams = fastCoverParams.zParams;
518 coverParams->shrinkDict = fastCoverParams.shrinkDict;
523 FASTCOVER_convertToFastCoverParams(ZDICT_cover_params_t coverParams,
524 ZDICT_fastCover_params_t* fastCoverParams,
525 unsigned f, unsigned accel)
527 fastCoverParams->k = coverParams.k;
528 fastCoverParams->d = coverParams.d;
529 fastCoverParams->steps = coverParams.steps;
530 fastCoverParams->nbThreads = coverParams.nbThreads;
531 fastCoverParams->splitPoint = coverParams.splitPoint;
532 fastCoverParams->f = f;
533 fastCoverParams->accel = accel;
534 fastCoverParams->zParams = coverParams.zParams;
535 fastCoverParams->shrinkDict = coverParams.shrinkDict;
540 ZDICT_trainFromBuffer_fastCover(void* dictBuffer, size_t dictBufferCapacity,
541 const void* samplesBuffer,
542 const size_t* samplesSizes, unsigned nbSamples,
543 ZDICT_fastCover_params_t parameters)
545 BYTE* const dict = (BYTE*)dictBuffer;
547 ZDICT_cover_params_t coverParams;
548 FASTCOVER_accel_t accelParams;
549 /* Initialize global data */
550 g_displayLevel = parameters.zParams.notificationLevel;
551 /* Assign splitPoint and f if not provided */
552 parameters.splitPoint = 1.0;
553 parameters.f = parameters.f == 0 ? DEFAULT_F : parameters.f;
554 parameters.accel = parameters.accel == 0 ? DEFAULT_ACCEL : parameters.accel;
555 /* Convert to cover parameter */
556 memset(&coverParams, 0 , sizeof(coverParams));
557 FASTCOVER_convertToCoverParams(parameters, &coverParams);
559 if (!FASTCOVER_checkParameters(coverParams, dictBufferCapacity, parameters.f,
561 DISPLAYLEVEL(1, "FASTCOVER parameters incorrect\n");
562 return ERROR(parameter_outOfBound);
564 if (nbSamples == 0) {
565 DISPLAYLEVEL(1, "FASTCOVER must have at least one input file\n");
566 return ERROR(srcSize_wrong);
568 if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) {
569 DISPLAYLEVEL(1, "dictBufferCapacity must be at least %u\n",
571 return ERROR(dstSize_tooSmall);
573 /* Assign corresponding FASTCOVER_accel_t to accelParams*/
574 accelParams = FASTCOVER_defaultAccelParameters[parameters.accel];
575 /* Initialize context */
577 size_t const initVal = FASTCOVER_ctx_init(&ctx, samplesBuffer, samplesSizes, nbSamples,
578 coverParams.d, parameters.splitPoint, parameters.f,
580 if (ZSTD_isError(initVal)) {
581 DISPLAYLEVEL(1, "Failed to initialize context\n");
585 COVER_warnOnSmallCorpus(dictBufferCapacity, ctx.nbDmers, g_displayLevel);
586 /* Build the dictionary */
587 DISPLAYLEVEL(2, "Building dictionary\n");
589 /* Initialize array to keep track of frequency of dmer within activeSegment */
590 U16* segmentFreqs = (U16 *)calloc(((U64)1 << parameters.f), sizeof(U16));
591 const size_t tail = FASTCOVER_buildDictionary(&ctx, ctx.freqs, dictBuffer,
592 dictBufferCapacity, coverParams, segmentFreqs);
593 const unsigned nbFinalizeSamples = (unsigned)(ctx.nbTrainSamples * ctx.accelParams.finalize / 100);
594 const size_t dictionarySize = ZDICT_finalizeDictionary(
595 dict, dictBufferCapacity, dict + tail, dictBufferCapacity - tail,
596 samplesBuffer, samplesSizes, nbFinalizeSamples, coverParams.zParams);
597 if (!ZSTD_isError(dictionarySize)) {
598 DISPLAYLEVEL(2, "Constructed dictionary of size %u\n",
599 (unsigned)dictionarySize);
601 FASTCOVER_ctx_destroy(&ctx);
603 return dictionarySize;
609 ZDICT_optimizeTrainFromBuffer_fastCover(
610 void* dictBuffer, size_t dictBufferCapacity,
611 const void* samplesBuffer,
612 const size_t* samplesSizes, unsigned nbSamples,
613 ZDICT_fastCover_params_t* parameters)
615 ZDICT_cover_params_t coverParams;
616 FASTCOVER_accel_t accelParams;
618 const unsigned nbThreads = parameters->nbThreads;
619 const double splitPoint =
620 parameters->splitPoint <= 0.0 ? DEFAULT_SPLITPOINT : parameters->splitPoint;
621 const unsigned kMinD = parameters->d == 0 ? 6 : parameters->d;
622 const unsigned kMaxD = parameters->d == 0 ? 8 : parameters->d;
623 const unsigned kMinK = parameters->k == 0 ? 50 : parameters->k;
624 const unsigned kMaxK = parameters->k == 0 ? 2000 : parameters->k;
625 const unsigned kSteps = parameters->steps == 0 ? 40 : parameters->steps;
626 const unsigned kStepSize = MAX((kMaxK - kMinK) / kSteps, 1);
627 const unsigned kIterations =
628 (1 + (kMaxD - kMinD) / 2) * (1 + (kMaxK - kMinK) / kStepSize);
629 const unsigned f = parameters->f == 0 ? DEFAULT_F : parameters->f;
630 const unsigned accel = parameters->accel == 0 ? DEFAULT_ACCEL : parameters->accel;
631 const unsigned shrinkDict = 0;
632 /* Local variables */
633 const int displayLevel = parameters->zParams.notificationLevel;
634 unsigned iteration = 1;
638 POOL_ctx *pool = NULL;
641 if (splitPoint <= 0 || splitPoint > 1) {
642 LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect splitPoint\n");
643 return ERROR(parameter_outOfBound);
645 if (accel == 0 || accel > FASTCOVER_MAX_ACCEL) {
646 LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect accel\n");
647 return ERROR(parameter_outOfBound);
649 if (kMinK < kMaxD || kMaxK < kMinK) {
650 LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect k\n");
651 return ERROR(parameter_outOfBound);
653 if (nbSamples == 0) {
654 LOCALDISPLAYLEVEL(displayLevel, 1, "FASTCOVER must have at least one input file\n");
655 return ERROR(srcSize_wrong);
657 if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) {
658 LOCALDISPLAYLEVEL(displayLevel, 1, "dictBufferCapacity must be at least %u\n",
660 return ERROR(dstSize_tooSmall);
663 pool = POOL_create(nbThreads, 1);
665 return ERROR(memory_allocation);
669 COVER_best_init(&best);
670 memset(&coverParams, 0 , sizeof(coverParams));
671 FASTCOVER_convertToCoverParams(*parameters, &coverParams);
672 accelParams = FASTCOVER_defaultAccelParameters[accel];
673 /* Turn down global display level to clean up display at level 2 and below */
674 g_displayLevel = displayLevel == 0 ? 0 : displayLevel - 1;
675 /* Loop through d first because each new value needs a new context */
676 LOCALDISPLAYLEVEL(displayLevel, 2, "Trying %u different sets of parameters\n",
678 for (d = kMinD; d <= kMaxD; d += 2) {
679 /* Initialize the context for this value of d */
681 LOCALDISPLAYLEVEL(displayLevel, 3, "d=%u\n", d);
683 size_t const initVal = FASTCOVER_ctx_init(&ctx, samplesBuffer, samplesSizes, nbSamples, d, splitPoint, f, accelParams);
684 if (ZSTD_isError(initVal)) {
685 LOCALDISPLAYLEVEL(displayLevel, 1, "Failed to initialize context\n");
686 COVER_best_destroy(&best);
692 COVER_warnOnSmallCorpus(dictBufferCapacity, ctx.nbDmers, displayLevel);
695 /* Loop through k reusing the same context */
696 for (k = kMinK; k <= kMaxK; k += kStepSize) {
697 /* Prepare the arguments */
698 FASTCOVER_tryParameters_data_t *data = (FASTCOVER_tryParameters_data_t *)malloc(
699 sizeof(FASTCOVER_tryParameters_data_t));
700 LOCALDISPLAYLEVEL(displayLevel, 3, "k=%u\n", k);
702 LOCALDISPLAYLEVEL(displayLevel, 1, "Failed to allocate parameters\n");
703 COVER_best_destroy(&best);
704 FASTCOVER_ctx_destroy(&ctx);
706 return ERROR(memory_allocation);
710 data->dictBufferCapacity = dictBufferCapacity;
711 data->parameters = coverParams;
712 data->parameters.k = k;
713 data->parameters.d = d;
714 data->parameters.splitPoint = splitPoint;
715 data->parameters.steps = kSteps;
716 data->parameters.shrinkDict = shrinkDict;
717 data->parameters.zParams.notificationLevel = g_displayLevel;
718 /* Check the parameters */
719 if (!FASTCOVER_checkParameters(data->parameters, dictBufferCapacity,
720 data->ctx->f, accel)) {
721 DISPLAYLEVEL(1, "FASTCOVER parameters incorrect\n");
725 /* Call the function and pass ownership of data to it */
726 COVER_best_start(&best);
728 POOL_add(pool, &FASTCOVER_tryParameters, data);
730 FASTCOVER_tryParameters(data);
733 LOCALDISPLAYUPDATE(displayLevel, 2, "\r%u%% ",
734 (unsigned)((iteration * 100) / kIterations));
737 COVER_best_wait(&best);
738 FASTCOVER_ctx_destroy(&ctx);
740 LOCALDISPLAYLEVEL(displayLevel, 2, "\r%79s\r", "");
741 /* Fill the output buffer and parameters with output of the best parameters */
743 const size_t dictSize = best.dictSize;
744 if (ZSTD_isError(best.compressedSize)) {
745 const size_t compressedSize = best.compressedSize;
746 COVER_best_destroy(&best);
748 return compressedSize;
750 FASTCOVER_convertToFastCoverParams(best.parameters, parameters, f, accel);
751 memcpy(dictBuffer, best.dict, dictSize);
752 COVER_best_destroy(&best);