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 */ 34 #include "../common/pool.h" /* POOL_ctx */ 35 #include "../common/threading.h" /* ZSTD_pthread_mutex_t */ 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) { \ 81 if ((clock() - g_time > g_refreshRate) || (displayLevel >= 4)) { \ 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 */ 304 static const size_t *COVER_lower_bound(const size_t* first, const size_t* last, 305 size_t value) { 306 size_t count = (size_t)(last - first); 307 assert(last >= first); 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, 553 unsigned d, double splitPoint) 554 { 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 738 ZDICTLIB_STATIC_API size_t ZDICT_trainFromBuffer_cover( 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 */ 912 void COVER_best_finish(COVER_best_t* best, 913 ZDICT_cover_params_t parameters, 914 COVER_dictSelection_t selection) 915 { 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 987 BYTE* largestDictbuffer = (BYTE*)malloc(dictBufferCapacity); 988 BYTE* candidateDictBuffer = (BYTE*)malloc(dictBufferCapacity); 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 1126 ZDICTLIB_STATIC_API size_t ZDICT_optimizeTrainFromBuffer_cover( 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 } 1262