Welcome to mirror list, hosted at ThFree Co, Russian Federation.

github.com/wolfpld/tracy.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/zstd
diff options
context:
space:
mode:
authorBartosz Taudul <wolf@nereid.pl>2021-05-15 15:56:38 +0300
committerBartosz Taudul <wolf@nereid.pl>2021-05-15 15:56:38 +0300
commit859b8e419319a89d772bf9a1ac31a5701b4e62da (patch)
treed861f07bde2b1004bda339284e4dff4dbe57beea /zstd
parent959ddc35017d46cbd5d4f67bd086feae1b7e0197 (diff)
Add zstd dict builder.
Diffstat (limited to 'zstd')
-rw-r--r--zstd/dictBuilder/cover.c1246
-rw-r--r--zstd/dictBuilder/cover.h158
-rw-r--r--zstd/dictBuilder/divsufsort.c1913
-rw-r--r--zstd/dictBuilder/divsufsort.h67
-rw-r--r--zstd/dictBuilder/fastcover.c759
-rw-r--r--zstd/dictBuilder/zdict.c1134
-rw-r--r--zstd/zdict.h452
7 files changed, 5729 insertions, 0 deletions
diff --git a/zstd/dictBuilder/cover.c b/zstd/dictBuilder/cover.c
new file mode 100644
index 00000000..8364444d
--- /dev/null
+++ b/zstd/dictBuilder/cover.c
@@ -0,0 +1,1246 @@
+/*
+ * Copyright (c) Yann Collet, Facebook, Inc.
+ * All rights reserved.
+ *
+ * This source code is licensed under both the BSD-style license (found in the
+ * LICENSE file in the root directory of this source tree) and the GPLv2 (found
+ * in the COPYING file in the root directory of this source tree).
+ * You may select, at your option, one of the above-listed licenses.
+ */
+
+/* *****************************************************************************
+ * Constructs a dictionary using a heuristic based on the following paper:
+ *
+ * Liao, Petri, Moffat, Wirth
+ * Effective Construction of Relative Lempel-Ziv Dictionaries
+ * Published in WWW 2016.
+ *
+ * Adapted from code originally written by @ot (Giuseppe Ottaviano).
+ ******************************************************************************/
+
+/*-*************************************
+* Dependencies
+***************************************/
+#include <stdio.h> /* fprintf */
+#include <stdlib.h> /* malloc, free, qsort */
+#include <string.h> /* memset */
+#include <time.h> /* clock */
+
+#ifndef ZDICT_STATIC_LINKING_ONLY
+# define ZDICT_STATIC_LINKING_ONLY
+#endif
+
+#include "../common/mem.h" /* read */
+#include "../common/pool.h"
+#include "../common/threading.h"
+#include "../common/zstd_internal.h" /* includes zstd.h */
+#include "../zdict.h"
+#include "cover.h"
+
+/*-*************************************
+* Constants
+***************************************/
+#define COVER_MAX_SAMPLES_SIZE (sizeof(size_t) == 8 ? ((unsigned)-1) : ((unsigned)1 GB))
+#define COVER_DEFAULT_SPLITPOINT 1.0
+
+/*-*************************************
+* Console display
+***************************************/
+#ifndef LOCALDISPLAYLEVEL
+static int g_displayLevel = 2;
+#endif
+#undef DISPLAY
+#define DISPLAY(...) \
+ { \
+ fprintf(stderr, __VA_ARGS__); \
+ fflush(stderr); \
+ }
+#undef LOCALDISPLAYLEVEL
+#define LOCALDISPLAYLEVEL(displayLevel, l, ...) \
+ if (displayLevel >= l) { \
+ DISPLAY(__VA_ARGS__); \
+ } /* 0 : no display; 1: errors; 2: default; 3: details; 4: debug */
+#undef DISPLAYLEVEL
+#define DISPLAYLEVEL(l, ...) LOCALDISPLAYLEVEL(g_displayLevel, l, __VA_ARGS__)
+
+#ifndef LOCALDISPLAYUPDATE
+static const clock_t g_refreshRate = CLOCKS_PER_SEC * 15 / 100;
+static clock_t g_time = 0;
+#endif
+#undef LOCALDISPLAYUPDATE
+#define LOCALDISPLAYUPDATE(displayLevel, l, ...) \
+ if (displayLevel >= l) { \
+ if ((clock() - g_time > g_refreshRate) || (displayLevel >= 4)) { \
+ g_time = clock(); \
+ DISPLAY(__VA_ARGS__); \
+ } \
+ }
+#undef DISPLAYUPDATE
+#define DISPLAYUPDATE(l, ...) LOCALDISPLAYUPDATE(g_displayLevel, l, __VA_ARGS__)
+
+/*-*************************************
+* Hash table
+***************************************
+* A small specialized hash map for storing activeDmers.
+* The map does not resize, so if it becomes full it will loop forever.
+* Thus, the map must be large enough to store every value.
+* The map implements linear probing and keeps its load less than 0.5.
+*/
+
+#define MAP_EMPTY_VALUE ((U32)-1)
+typedef struct COVER_map_pair_t_s {
+ U32 key;
+ U32 value;
+} COVER_map_pair_t;
+
+typedef struct COVER_map_s {
+ COVER_map_pair_t *data;
+ U32 sizeLog;
+ U32 size;
+ U32 sizeMask;
+} COVER_map_t;
+
+/**
+ * Clear the map.
+ */
+static void COVER_map_clear(COVER_map_t *map) {
+ memset(map->data, MAP_EMPTY_VALUE, map->size * sizeof(COVER_map_pair_t));
+}
+
+/**
+ * Initializes a map of the given size.
+ * Returns 1 on success and 0 on failure.
+ * The map must be destroyed with COVER_map_destroy().
+ * The map is only guaranteed to be large enough to hold size elements.
+ */
+static int COVER_map_init(COVER_map_t *map, U32 size) {
+ map->sizeLog = ZSTD_highbit32(size) + 2;
+ map->size = (U32)1 << map->sizeLog;
+ map->sizeMask = map->size - 1;
+ map->data = (COVER_map_pair_t *)malloc(map->size * sizeof(COVER_map_pair_t));
+ if (!map->data) {
+ map->sizeLog = 0;
+ map->size = 0;
+ return 0;
+ }
+ COVER_map_clear(map);
+ return 1;
+}
+
+/**
+ * Internal hash function
+ */
+static const U32 COVER_prime4bytes = 2654435761U;
+static U32 COVER_map_hash(COVER_map_t *map, U32 key) {
+ return (key * COVER_prime4bytes) >> (32 - map->sizeLog);
+}
+
+/**
+ * Helper function that returns the index that a key should be placed into.
+ */
+static U32 COVER_map_index(COVER_map_t *map, U32 key) {
+ const U32 hash = COVER_map_hash(map, key);
+ U32 i;
+ for (i = hash;; i = (i + 1) & map->sizeMask) {
+ COVER_map_pair_t *pos = &map->data[i];
+ if (pos->value == MAP_EMPTY_VALUE) {
+ return i;
+ }
+ if (pos->key == key) {
+ return i;
+ }
+ }
+}
+
+/**
+ * Returns the pointer to the value for key.
+ * If key is not in the map, it is inserted and the value is set to 0.
+ * The map must not be full.
+ */
+static U32 *COVER_map_at(COVER_map_t *map, U32 key) {
+ COVER_map_pair_t *pos = &map->data[COVER_map_index(map, key)];
+ if (pos->value == MAP_EMPTY_VALUE) {
+ pos->key = key;
+ pos->value = 0;
+ }
+ return &pos->value;
+}
+
+/**
+ * Deletes key from the map if present.
+ */
+static void COVER_map_remove(COVER_map_t *map, U32 key) {
+ U32 i = COVER_map_index(map, key);
+ COVER_map_pair_t *del = &map->data[i];
+ U32 shift = 1;
+ if (del->value == MAP_EMPTY_VALUE) {
+ return;
+ }
+ for (i = (i + 1) & map->sizeMask;; i = (i + 1) & map->sizeMask) {
+ COVER_map_pair_t *const pos = &map->data[i];
+ /* If the position is empty we are done */
+ if (pos->value == MAP_EMPTY_VALUE) {
+ del->value = MAP_EMPTY_VALUE;
+ return;
+ }
+ /* If pos can be moved to del do so */
+ if (((i - COVER_map_hash(map, pos->key)) & map->sizeMask) >= shift) {
+ del->key = pos->key;
+ del->value = pos->value;
+ del = pos;
+ shift = 1;
+ } else {
+ ++shift;
+ }
+ }
+}
+
+/**
+ * Destroys a map that is inited with COVER_map_init().
+ */
+static void COVER_map_destroy(COVER_map_t *map) {
+ if (map->data) {
+ free(map->data);
+ }
+ map->data = NULL;
+ map->size = 0;
+}
+
+/*-*************************************
+* Context
+***************************************/
+
+typedef struct {
+ const BYTE *samples;
+ size_t *offsets;
+ const size_t *samplesSizes;
+ size_t nbSamples;
+ size_t nbTrainSamples;
+ size_t nbTestSamples;
+ U32 *suffix;
+ size_t suffixSize;
+ U32 *freqs;
+ U32 *dmerAt;
+ unsigned d;
+} COVER_ctx_t;
+
+/* We need a global context for qsort... */
+static COVER_ctx_t *g_coverCtx = NULL;
+
+/*-*************************************
+* Helper functions
+***************************************/
+
+/**
+ * Returns the sum of the sample sizes.
+ */
+size_t COVER_sum(const size_t *samplesSizes, unsigned nbSamples) {
+ size_t sum = 0;
+ unsigned i;
+ for (i = 0; i < nbSamples; ++i) {
+ sum += samplesSizes[i];
+ }
+ return sum;
+}
+
+/**
+ * Returns -1 if the dmer at lp is less than the dmer at rp.
+ * Return 0 if the dmers at lp and rp are equal.
+ * Returns 1 if the dmer at lp is greater than the dmer at rp.
+ */
+static int COVER_cmp(COVER_ctx_t *ctx, const void *lp, const void *rp) {
+ U32 const lhs = *(U32 const *)lp;
+ U32 const rhs = *(U32 const *)rp;
+ return memcmp(ctx->samples + lhs, ctx->samples + rhs, ctx->d);
+}
+/**
+ * Faster version for d <= 8.
+ */
+static int COVER_cmp8(COVER_ctx_t *ctx, const void *lp, const void *rp) {
+ U64 const mask = (ctx->d == 8) ? (U64)-1 : (((U64)1 << (8 * ctx->d)) - 1);
+ U64 const lhs = MEM_readLE64(ctx->samples + *(U32 const *)lp) & mask;
+ U64 const rhs = MEM_readLE64(ctx->samples + *(U32 const *)rp) & mask;
+ if (lhs < rhs) {
+ return -1;
+ }
+ return (lhs > rhs);
+}
+
+/**
+ * Same as COVER_cmp() except ties are broken by pointer value
+ * NOTE: g_coverCtx must be set to call this function. A global is required because
+ * qsort doesn't take an opaque pointer.
+ */
+static int WIN_CDECL COVER_strict_cmp(const void *lp, const void *rp) {
+ int result = COVER_cmp(g_coverCtx, lp, rp);
+ if (result == 0) {
+ result = lp < rp ? -1 : 1;
+ }
+ return result;
+}
+/**
+ * Faster version for d <= 8.
+ */
+static int WIN_CDECL COVER_strict_cmp8(const void *lp, const void *rp) {
+ int result = COVER_cmp8(g_coverCtx, lp, rp);
+ if (result == 0) {
+ result = lp < rp ? -1 : 1;
+ }
+ return result;
+}
+
+/**
+ * Returns the first pointer in [first, last) whose element does not compare
+ * less than value. If no such element exists it returns last.
+ */
+static const size_t *COVER_lower_bound(const size_t *first, const size_t *last,
+ size_t value) {
+ size_t count = last - first;
+ while (count != 0) {
+ size_t step = count / 2;
+ const size_t *ptr = first;
+ ptr += step;
+ if (*ptr < value) {
+ first = ++ptr;
+ count -= step + 1;
+ } else {
+ count = step;
+ }
+ }
+ return first;
+}
+
+/**
+ * Generic groupBy function.
+ * Groups an array sorted by cmp into groups with equivalent values.
+ * Calls grp for each group.
+ */
+static void
+COVER_groupBy(const void *data, size_t count, size_t size, COVER_ctx_t *ctx,
+ int (*cmp)(COVER_ctx_t *, const void *, const void *),
+ void (*grp)(COVER_ctx_t *, const void *, const void *)) {
+ const BYTE *ptr = (const BYTE *)data;
+ size_t num = 0;
+ while (num < count) {
+ const BYTE *grpEnd = ptr + size;
+ ++num;
+ while (num < count && cmp(ctx, ptr, grpEnd) == 0) {
+ grpEnd += size;
+ ++num;
+ }
+ grp(ctx, ptr, grpEnd);
+ ptr = grpEnd;
+ }
+}
+
+/*-*************************************
+* Cover functions
+***************************************/
+
+/**
+ * Called on each group of positions with the same dmer.
+ * Counts the frequency of each dmer and saves it in the suffix array.
+ * Fills `ctx->dmerAt`.
+ */
+static void COVER_group(COVER_ctx_t *ctx, const void *group,
+ const void *groupEnd) {
+ /* The group consists of all the positions with the same first d bytes. */
+ const U32 *grpPtr = (const U32 *)group;
+ const U32 *grpEnd = (const U32 *)groupEnd;
+ /* The dmerId is how we will reference this dmer.
+ * This allows us to map the whole dmer space to a much smaller space, the
+ * size of the suffix array.
+ */
+ const U32 dmerId = (U32)(grpPtr - ctx->suffix);
+ /* Count the number of samples this dmer shows up in */
+ U32 freq = 0;
+ /* Details */
+ const size_t *curOffsetPtr = ctx->offsets;
+ const size_t *offsetsEnd = ctx->offsets + ctx->nbSamples;
+ /* Once *grpPtr >= curSampleEnd this occurrence of the dmer is in a
+ * different sample than the last.
+ */
+ size_t curSampleEnd = ctx->offsets[0];
+ for (; grpPtr != grpEnd; ++grpPtr) {
+ /* Save the dmerId for this position so we can get back to it. */
+ ctx->dmerAt[*grpPtr] = dmerId;
+ /* Dictionaries only help for the first reference to the dmer.
+ * After that zstd can reference the match from the previous reference.
+ * So only count each dmer once for each sample it is in.
+ */
+ if (*grpPtr < curSampleEnd) {
+ continue;
+ }
+ freq += 1;
+ /* Binary search to find the end of the sample *grpPtr is in.
+ * In the common case that grpPtr + 1 == grpEnd we can skip the binary
+ * search because the loop is over.
+ */
+ if (grpPtr + 1 != grpEnd) {
+ const size_t *sampleEndPtr =
+ COVER_lower_bound(curOffsetPtr, offsetsEnd, *grpPtr);
+ curSampleEnd = *sampleEndPtr;
+ curOffsetPtr = sampleEndPtr + 1;
+ }
+ }
+ /* At this point we are never going to look at this segment of the suffix
+ * array again. We take advantage of this fact to save memory.
+ * We store the frequency of the dmer in the first position of the group,
+ * which is dmerId.
+ */
+ ctx->suffix[dmerId] = freq;
+}
+
+
+/**
+ * Selects the best segment in an epoch.
+ * Segments of are scored according to the function:
+ *
+ * Let F(d) be the frequency of dmer d.
+ * Let S_i be the dmer at position i of segment S which has length k.
+ *
+ * Score(S) = F(S_1) + F(S_2) + ... + F(S_{k-d+1})
+ *
+ * Once the dmer d is in the dictionary we set F(d) = 0.
+ */
+static COVER_segment_t COVER_selectSegment(const COVER_ctx_t *ctx, U32 *freqs,
+ COVER_map_t *activeDmers, U32 begin,
+ U32 end,
+ ZDICT_cover_params_t parameters) {
+ /* Constants */
+ const U32 k = parameters.k;
+ const U32 d = parameters.d;
+ const U32 dmersInK = k - d + 1;
+ /* Try each segment (activeSegment) and save the best (bestSegment) */
+ COVER_segment_t bestSegment = {0, 0, 0};
+ COVER_segment_t activeSegment;
+ /* Reset the activeDmers in the segment */
+ COVER_map_clear(activeDmers);
+ /* The activeSegment starts at the beginning of the epoch. */
+ activeSegment.begin = begin;
+ activeSegment.end = begin;
+ activeSegment.score = 0;
+ /* Slide the activeSegment through the whole epoch.
+ * Save the best segment in bestSegment.
+ */
+ while (activeSegment.end < end) {
+ /* The dmerId for the dmer at the next position */
+ U32 newDmer = ctx->dmerAt[activeSegment.end];
+ /* The entry in activeDmers for this dmerId */
+ U32 *newDmerOcc = COVER_map_at(activeDmers, newDmer);
+ /* If the dmer isn't already present in the segment add its score. */
+ if (*newDmerOcc == 0) {
+ /* The paper suggest using the L-0.5 norm, but experiments show that it
+ * doesn't help.
+ */
+ activeSegment.score += freqs[newDmer];
+ }
+ /* Add the dmer to the segment */
+ activeSegment.end += 1;
+ *newDmerOcc += 1;
+
+ /* If the window is now too large, drop the first position */
+ if (activeSegment.end - activeSegment.begin == dmersInK + 1) {
+ U32 delDmer = ctx->dmerAt[activeSegment.begin];
+ U32 *delDmerOcc = COVER_map_at(activeDmers, delDmer);
+ activeSegment.begin += 1;
+ *delDmerOcc -= 1;
+ /* If this is the last occurrence of the dmer, subtract its score */
+ if (*delDmerOcc == 0) {
+ COVER_map_remove(activeDmers, delDmer);
+ activeSegment.score -= freqs[delDmer];
+ }
+ }
+
+ /* If this segment is the best so far save it */
+ if (activeSegment.score > bestSegment.score) {
+ bestSegment = activeSegment;
+ }
+ }
+ {
+ /* Trim off the zero frequency head and tail from the segment. */
+ U32 newBegin = bestSegment.end;
+ U32 newEnd = bestSegment.begin;
+ U32 pos;
+ for (pos = bestSegment.begin; pos != bestSegment.end; ++pos) {
+ U32 freq = freqs[ctx->dmerAt[pos]];
+ if (freq != 0) {
+ newBegin = MIN(newBegin, pos);
+ newEnd = pos + 1;
+ }
+ }
+ bestSegment.begin = newBegin;
+ bestSegment.end = newEnd;
+ }
+ {
+ /* Zero out the frequency of each dmer covered by the chosen segment. */
+ U32 pos;
+ for (pos = bestSegment.begin; pos != bestSegment.end; ++pos) {
+ freqs[ctx->dmerAt[pos]] = 0;
+ }
+ }
+ return bestSegment;
+}
+
+/**
+ * Check the validity of the parameters.
+ * Returns non-zero if the parameters are valid and 0 otherwise.
+ */
+static int COVER_checkParameters(ZDICT_cover_params_t parameters,
+ size_t maxDictSize) {
+ /* k and d are required parameters */
+ if (parameters.d == 0 || parameters.k == 0) {
+ return 0;
+ }
+ /* k <= maxDictSize */
+ if (parameters.k > maxDictSize) {
+ return 0;
+ }
+ /* d <= k */
+ if (parameters.d > parameters.k) {
+ return 0;
+ }
+ /* 0 < splitPoint <= 1 */
+ if (parameters.splitPoint <= 0 || parameters.splitPoint > 1){
+ return 0;
+ }
+ return 1;
+}
+
+/**
+ * Clean up a context initialized with `COVER_ctx_init()`.
+ */
+static void COVER_ctx_destroy(COVER_ctx_t *ctx) {
+ if (!ctx) {
+ return;
+ }
+ if (ctx->suffix) {
+ free(ctx->suffix);
+ ctx->suffix = NULL;
+ }
+ if (ctx->freqs) {
+ free(ctx->freqs);
+ ctx->freqs = NULL;
+ }
+ if (ctx->dmerAt) {
+ free(ctx->dmerAt);
+ ctx->dmerAt = NULL;
+ }
+ if (ctx->offsets) {
+ free(ctx->offsets);
+ ctx->offsets = NULL;
+ }
+}
+
+/**
+ * Prepare a context for dictionary building.
+ * The context is only dependent on the parameter `d` and can used multiple
+ * times.
+ * Returns 0 on success or error code on error.
+ * The context must be destroyed with `COVER_ctx_destroy()`.
+ */
+static size_t COVER_ctx_init(COVER_ctx_t *ctx, const void *samplesBuffer,
+ const size_t *samplesSizes, unsigned nbSamples,
+ unsigned d, double splitPoint) {
+ const BYTE *const samples = (const BYTE *)samplesBuffer;
+ const size_t totalSamplesSize = COVER_sum(samplesSizes, nbSamples);
+ /* Split samples into testing and training sets */
+ const unsigned nbTrainSamples = splitPoint < 1.0 ? (unsigned)((double)nbSamples * splitPoint) : nbSamples;
+ const unsigned nbTestSamples = splitPoint < 1.0 ? nbSamples - nbTrainSamples : nbSamples;
+ const size_t trainingSamplesSize = splitPoint < 1.0 ? COVER_sum(samplesSizes, nbTrainSamples) : totalSamplesSize;
+ const size_t testSamplesSize = splitPoint < 1.0 ? COVER_sum(samplesSizes + nbTrainSamples, nbTestSamples) : totalSamplesSize;
+ /* Checks */
+ if (totalSamplesSize < MAX(d, sizeof(U64)) ||
+ totalSamplesSize >= (size_t)COVER_MAX_SAMPLES_SIZE) {
+ DISPLAYLEVEL(1, "Total samples size is too large (%u MB), maximum size is %u MB\n",
+ (unsigned)(totalSamplesSize>>20), (COVER_MAX_SAMPLES_SIZE >> 20));
+ return ERROR(srcSize_wrong);
+ }
+ /* Check if there are at least 5 training samples */
+ if (nbTrainSamples < 5) {
+ DISPLAYLEVEL(1, "Total number of training samples is %u and is invalid.", nbTrainSamples);
+ return ERROR(srcSize_wrong);
+ }
+ /* Check if there's testing sample */
+ if (nbTestSamples < 1) {
+ DISPLAYLEVEL(1, "Total number of testing samples is %u and is invalid.", nbTestSamples);
+ return ERROR(srcSize_wrong);
+ }
+ /* Zero the context */
+ memset(ctx, 0, sizeof(*ctx));
+ DISPLAYLEVEL(2, "Training on %u samples of total size %u\n", nbTrainSamples,
+ (unsigned)trainingSamplesSize);
+ DISPLAYLEVEL(2, "Testing on %u samples of total size %u\n", nbTestSamples,
+ (unsigned)testSamplesSize);
+ ctx->samples = samples;
+ ctx->samplesSizes = samplesSizes;
+ ctx->nbSamples = nbSamples;
+ ctx->nbTrainSamples = nbTrainSamples;
+ ctx->nbTestSamples = nbTestSamples;
+ /* Partial suffix array */
+ ctx->suffixSize = trainingSamplesSize - MAX(d, sizeof(U64)) + 1;
+ ctx->suffix = (U32 *)malloc(ctx->suffixSize * sizeof(U32));
+ /* Maps index to the dmerID */
+ ctx->dmerAt = (U32 *)malloc(ctx->suffixSize * sizeof(U32));
+ /* The offsets of each file */
+ ctx->offsets = (size_t *)malloc((nbSamples + 1) * sizeof(size_t));
+ if (!ctx->suffix || !ctx->dmerAt || !ctx->offsets) {
+ DISPLAYLEVEL(1, "Failed to allocate scratch buffers\n");
+ COVER_ctx_destroy(ctx);
+ return ERROR(memory_allocation);
+ }
+ ctx->freqs = NULL;
+ ctx->d = d;
+
+ /* Fill offsets from the samplesSizes */
+ {
+ U32 i;
+ ctx->offsets[0] = 0;
+ for (i = 1; i <= nbSamples; ++i) {
+ ctx->offsets[i] = ctx->offsets[i - 1] + samplesSizes[i - 1];
+ }
+ }
+ DISPLAYLEVEL(2, "Constructing partial suffix array\n");
+ {
+ /* suffix is a partial suffix array.
+ * It only sorts suffixes by their first parameters.d bytes.
+ * The sort is stable, so each dmer group is sorted by position in input.
+ */
+ U32 i;
+ for (i = 0; i < ctx->suffixSize; ++i) {
+ ctx->suffix[i] = i;
+ }
+ /* qsort doesn't take an opaque pointer, so pass as a global.
+ * On OpenBSD qsort() is not guaranteed to be stable, their mergesort() is.
+ */
+ g_coverCtx = ctx;
+#if defined(__OpenBSD__)
+ mergesort(ctx->suffix, ctx->suffixSize, sizeof(U32),
+ (ctx->d <= 8 ? &COVER_strict_cmp8 : &COVER_strict_cmp));
+#else
+ qsort(ctx->suffix, ctx->suffixSize, sizeof(U32),
+ (ctx->d <= 8 ? &COVER_strict_cmp8 : &COVER_strict_cmp));
+#endif
+ }
+ DISPLAYLEVEL(2, "Computing frequencies\n");
+ /* For each dmer group (group of positions with the same first d bytes):
+ * 1. For each position we set dmerAt[position] = dmerID. The dmerID is
+ * (groupBeginPtr - suffix). This allows us to go from position to
+ * dmerID so we can look up values in freq.
+ * 2. We calculate how many samples the dmer occurs in and save it in
+ * freqs[dmerId].
+ */
+ COVER_groupBy(ctx->suffix, ctx->suffixSize, sizeof(U32), ctx,
+ (ctx->d <= 8 ? &COVER_cmp8 : &COVER_cmp), &COVER_group);
+ ctx->freqs = ctx->suffix;
+ ctx->suffix = NULL;
+ return 0;
+}
+
+void COVER_warnOnSmallCorpus(size_t maxDictSize, size_t nbDmers, int displayLevel)
+{
+ const double ratio = (double)nbDmers / maxDictSize;
+ if (ratio >= 10) {
+ return;
+ }
+ LOCALDISPLAYLEVEL(displayLevel, 1,
+ "WARNING: The maximum dictionary size %u is too large "
+ "compared to the source size %u! "
+ "size(source)/size(dictionary) = %f, but it should be >= "
+ "10! This may lead to a subpar dictionary! We recommend "
+ "training on sources at least 10x, and preferably 100x "
+ "the size of the dictionary! \n", (U32)maxDictSize,
+ (U32)nbDmers, ratio);
+}
+
+COVER_epoch_info_t COVER_computeEpochs(U32 maxDictSize,
+ U32 nbDmers, U32 k, U32 passes)
+{
+ const U32 minEpochSize = k * 10;
+ COVER_epoch_info_t epochs;
+ epochs.num = MAX(1, maxDictSize / k / passes);
+ epochs.size = nbDmers / epochs.num;
+ if (epochs.size >= minEpochSize) {
+ assert(epochs.size * epochs.num <= nbDmers);
+ return epochs;
+ }
+ epochs.size = MIN(minEpochSize, nbDmers);
+ epochs.num = nbDmers / epochs.size;
+ assert(epochs.size * epochs.num <= nbDmers);
+ return epochs;
+}
+
+/**
+ * Given the prepared context build the dictionary.
+ */
+static size_t COVER_buildDictionary(const COVER_ctx_t *ctx, U32 *freqs,
+ COVER_map_t *activeDmers, void *dictBuffer,
+ size_t dictBufferCapacity,
+ ZDICT_cover_params_t parameters) {
+ BYTE *const dict = (BYTE *)dictBuffer;
+ size_t tail = dictBufferCapacity;
+ /* Divide the data into epochs. We will select one segment from each epoch. */
+ const COVER_epoch_info_t epochs = COVER_computeEpochs(
+ (U32)dictBufferCapacity, (U32)ctx->suffixSize, parameters.k, 4);
+ const size_t maxZeroScoreRun = MAX(10, MIN(100, epochs.num >> 3));
+ size_t zeroScoreRun = 0;
+ size_t epoch;
+ DISPLAYLEVEL(2, "Breaking content into %u epochs of size %u\n",
+ (U32)epochs.num, (U32)epochs.size);
+ /* Loop through the epochs until there are no more segments or the dictionary
+ * is full.
+ */
+ for (epoch = 0; tail > 0; epoch = (epoch + 1) % epochs.num) {
+ const U32 epochBegin = (U32)(epoch * epochs.size);
+ const U32 epochEnd = epochBegin + epochs.size;
+ size_t segmentSize;
+ /* Select a segment */
+ COVER_segment_t segment = COVER_selectSegment(
+ ctx, freqs, activeDmers, epochBegin, epochEnd, parameters);
+ /* If the segment covers no dmers, then we are out of content.
+ * There may be new content in other epochs, for continue for some time.
+ */
+ if (segment.score == 0) {
+ if (++zeroScoreRun >= maxZeroScoreRun) {
+ break;
+ }
+ continue;
+ }
+ zeroScoreRun = 0;
+ /* Trim the segment if necessary and if it is too small then we are done */
+ segmentSize = MIN(segment.end - segment.begin + parameters.d - 1, tail);
+ if (segmentSize < parameters.d) {
+ break;
+ }
+ /* We fill the dictionary from the back to allow the best segments to be
+ * referenced with the smallest offsets.
+ */
+ tail -= segmentSize;
+ memcpy(dict + tail, ctx->samples + segment.begin, segmentSize);
+ DISPLAYUPDATE(
+ 2, "\r%u%% ",
+ (unsigned)(((dictBufferCapacity - tail) * 100) / dictBufferCapacity));
+ }
+ DISPLAYLEVEL(2, "\r%79s\r", "");
+ return tail;
+}
+
+ZDICTLIB_API size_t ZDICT_trainFromBuffer_cover(
+ void *dictBuffer, size_t dictBufferCapacity,
+ const void *samplesBuffer, const size_t *samplesSizes, unsigned nbSamples,
+ ZDICT_cover_params_t parameters)
+{
+ BYTE* const dict = (BYTE*)dictBuffer;
+ COVER_ctx_t ctx;
+ COVER_map_t activeDmers;
+ parameters.splitPoint = 1.0;
+ /* Initialize global data */
+ g_displayLevel = parameters.zParams.notificationLevel;
+ /* Checks */
+ if (!COVER_checkParameters(parameters, dictBufferCapacity)) {
+ DISPLAYLEVEL(1, "Cover parameters incorrect\n");
+ return ERROR(parameter_outOfBound);
+ }
+ if (nbSamples == 0) {
+ DISPLAYLEVEL(1, "Cover must have at least one input file\n");
+ return ERROR(srcSize_wrong);
+ }
+ if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) {
+ DISPLAYLEVEL(1, "dictBufferCapacity must be at least %u\n",
+ ZDICT_DICTSIZE_MIN);
+ return ERROR(dstSize_tooSmall);
+ }
+ /* Initialize context and activeDmers */
+ {
+ size_t const initVal = COVER_ctx_init(&ctx, samplesBuffer, samplesSizes, nbSamples,
+ parameters.d, parameters.splitPoint);
+ if (ZSTD_isError(initVal)) {
+ return initVal;
+ }
+ }
+ COVER_warnOnSmallCorpus(dictBufferCapacity, ctx.suffixSize, g_displayLevel);
+ if (!COVER_map_init(&activeDmers, parameters.k - parameters.d + 1)) {
+ DISPLAYLEVEL(1, "Failed to allocate dmer map: out of memory\n");
+ COVER_ctx_destroy(&ctx);
+ return ERROR(memory_allocation);
+ }
+
+ DISPLAYLEVEL(2, "Building dictionary\n");
+ {
+ const size_t tail =
+ COVER_buildDictionary(&ctx, ctx.freqs, &activeDmers, dictBuffer,
+ dictBufferCapacity, parameters);
+ const size_t dictionarySize = ZDICT_finalizeDictionary(
+ dict, dictBufferCapacity, dict + tail, dictBufferCapacity - tail,
+ samplesBuffer, samplesSizes, nbSamples, parameters.zParams);
+ if (!ZSTD_isError(dictionarySize)) {
+ DISPLAYLEVEL(2, "Constructed dictionary of size %u\n",
+ (unsigned)dictionarySize);
+ }
+ COVER_ctx_destroy(&ctx);
+ COVER_map_destroy(&activeDmers);
+ return dictionarySize;
+ }
+}
+
+
+
+size_t COVER_checkTotalCompressedSize(const ZDICT_cover_params_t parameters,
+ const size_t *samplesSizes, const BYTE *samples,
+ size_t *offsets,
+ size_t nbTrainSamples, size_t nbSamples,
+ BYTE *const dict, size_t dictBufferCapacity) {
+ size_t totalCompressedSize = ERROR(GENERIC);
+ /* Pointers */
+ ZSTD_CCtx *cctx;
+ ZSTD_CDict *cdict;
+ void *dst;
+ /* Local variables */
+ size_t dstCapacity;
+ size_t i;
+ /* Allocate dst with enough space to compress the maximum sized sample */
+ {
+ size_t maxSampleSize = 0;
+ i = parameters.splitPoint < 1.0 ? nbTrainSamples : 0;
+ for (; i < nbSamples; ++i) {
+ maxSampleSize = MAX(samplesSizes[i], maxSampleSize);
+ }
+ dstCapacity = ZSTD_compressBound(maxSampleSize);
+ dst = malloc(dstCapacity);
+ }
+ /* Create the cctx and cdict */
+ cctx = ZSTD_createCCtx();
+ cdict = ZSTD_createCDict(dict, dictBufferCapacity,
+ parameters.zParams.compressionLevel);
+ if (!dst || !cctx || !cdict) {
+ goto _compressCleanup;
+ }
+ /* Compress each sample and sum their sizes (or error) */
+ totalCompressedSize = dictBufferCapacity;
+ i = parameters.splitPoint < 1.0 ? nbTrainSamples : 0;
+ for (; i < nbSamples; ++i) {
+ const size_t size = ZSTD_compress_usingCDict(
+ cctx, dst, dstCapacity, samples + offsets[i],
+ samplesSizes[i], cdict);
+ if (ZSTD_isError(size)) {
+ totalCompressedSize = size;
+ goto _compressCleanup;
+ }
+ totalCompressedSize += size;
+ }
+_compressCleanup:
+ ZSTD_freeCCtx(cctx);
+ ZSTD_freeCDict(cdict);
+ if (dst) {
+ free(dst);
+ }
+ return totalCompressedSize;
+}
+
+
+/**
+ * Initialize the `COVER_best_t`.
+ */
+void COVER_best_init(COVER_best_t *best) {
+ if (best==NULL) return; /* compatible with init on NULL */
+ (void)ZSTD_pthread_mutex_init(&best->mutex, NULL);
+ (void)ZSTD_pthread_cond_init(&best->cond, NULL);
+ best->liveJobs = 0;
+ best->dict = NULL;
+ best->dictSize = 0;
+ best->compressedSize = (size_t)-1;
+ memset(&best->parameters, 0, sizeof(best->parameters));
+}
+
+/**
+ * Wait until liveJobs == 0.
+ */
+void COVER_best_wait(COVER_best_t *best) {
+ if (!best) {
+ return;
+ }
+ ZSTD_pthread_mutex_lock(&best->mutex);
+ while (best->liveJobs != 0) {
+ ZSTD_pthread_cond_wait(&best->cond, &best->mutex);
+ }
+ ZSTD_pthread_mutex_unlock(&best->mutex);
+}
+
+/**
+ * Call COVER_best_wait() and then destroy the COVER_best_t.
+ */
+void COVER_best_destroy(COVER_best_t *best) {
+ if (!best) {
+ return;
+ }
+ COVER_best_wait(best);
+ if (best->dict) {
+ free(best->dict);
+ }
+ ZSTD_pthread_mutex_destroy(&best->mutex);
+ ZSTD_pthread_cond_destroy(&best->cond);
+}
+
+/**
+ * Called when a thread is about to be launched.
+ * Increments liveJobs.
+ */
+void COVER_best_start(COVER_best_t *best) {
+ if (!best) {
+ return;
+ }
+ ZSTD_pthread_mutex_lock(&best->mutex);
+ ++best->liveJobs;
+ ZSTD_pthread_mutex_unlock(&best->mutex);
+}
+
+/**
+ * Called when a thread finishes executing, both on error or success.
+ * Decrements liveJobs and signals any waiting threads if liveJobs == 0.
+ * If this dictionary is the best so far save it and its parameters.
+ */
+void COVER_best_finish(COVER_best_t *best, ZDICT_cover_params_t parameters,
+ COVER_dictSelection_t selection) {
+ void* dict = selection.dictContent;
+ size_t compressedSize = selection.totalCompressedSize;
+ size_t dictSize = selection.dictSize;
+ if (!best) {
+ return;
+ }
+ {
+ size_t liveJobs;
+ ZSTD_pthread_mutex_lock(&best->mutex);
+ --best->liveJobs;
+ liveJobs = best->liveJobs;
+ /* If the new dictionary is better */
+ if (compressedSize < best->compressedSize) {
+ /* Allocate space if necessary */
+ if (!best->dict || best->dictSize < dictSize) {
+ if (best->dict) {
+ free(best->dict);
+ }
+ best->dict = malloc(dictSize);
+ if (!best->dict) {
+ best->compressedSize = ERROR(GENERIC);
+ best->dictSize = 0;
+ ZSTD_pthread_cond_signal(&best->cond);
+ ZSTD_pthread_mutex_unlock(&best->mutex);
+ return;
+ }
+ }
+ /* Save the dictionary, parameters, and size */
+ if (dict) {
+ memcpy(best->dict, dict, dictSize);
+ best->dictSize = dictSize;
+ best->parameters = parameters;
+ best->compressedSize = compressedSize;
+ }
+ }
+ if (liveJobs == 0) {
+ ZSTD_pthread_cond_broadcast(&best->cond);
+ }
+ ZSTD_pthread_mutex_unlock(&best->mutex);
+ }
+}
+
+COVER_dictSelection_t COVER_dictSelectionError(size_t error) {
+ COVER_dictSelection_t selection = { NULL, 0, error };
+ return selection;
+}
+
+unsigned COVER_dictSelectionIsError(COVER_dictSelection_t selection) {
+ return (ZSTD_isError(selection.totalCompressedSize) || !selection.dictContent);
+}
+
+void COVER_dictSelectionFree(COVER_dictSelection_t selection){
+ free(selection.dictContent);
+}
+
+COVER_dictSelection_t COVER_selectDict(BYTE* customDictContent, size_t dictBufferCapacity,
+ size_t dictContentSize, const BYTE* samplesBuffer, const size_t* samplesSizes, unsigned nbFinalizeSamples,
+ size_t nbCheckSamples, size_t nbSamples, ZDICT_cover_params_t params, size_t* offsets, size_t totalCompressedSize) {
+
+ size_t largestDict = 0;
+ size_t largestCompressed = 0;
+ BYTE* customDictContentEnd = customDictContent + dictContentSize;
+
+ BYTE * largestDictbuffer = (BYTE *)malloc(dictBufferCapacity);
+ BYTE * candidateDictBuffer = (BYTE *)malloc(dictBufferCapacity);
+ double regressionTolerance = ((double)params.shrinkDictMaxRegression / 100.0) + 1.00;
+
+ if (!largestDictbuffer || !candidateDictBuffer) {
+ free(largestDictbuffer);
+ free(candidateDictBuffer);
+ return COVER_dictSelectionError(dictContentSize);
+ }
+
+ /* Initial dictionary size and compressed size */
+ memcpy(largestDictbuffer, customDictContent, dictContentSize);
+ dictContentSize = ZDICT_finalizeDictionary(
+ largestDictbuffer, dictBufferCapacity, customDictContent, dictContentSize,
+ samplesBuffer, samplesSizes, nbFinalizeSamples, params.zParams);
+
+ if (ZDICT_isError(dictContentSize)) {
+ free(largestDictbuffer);
+ free(candidateDictBuffer);
+ return COVER_dictSelectionError(dictContentSize);
+ }
+
+ totalCompressedSize = COVER_checkTotalCompressedSize(params, samplesSizes,
+ samplesBuffer, offsets,
+ nbCheckSamples, nbSamples,
+ largestDictbuffer, dictContentSize);
+
+ if (ZSTD_isError(totalCompressedSize)) {
+ free(largestDictbuffer);
+ free(candidateDictBuffer);
+ return COVER_dictSelectionError(totalCompressedSize);
+ }
+
+ if (params.shrinkDict == 0) {
+ COVER_dictSelection_t selection = { largestDictbuffer, dictContentSize, totalCompressedSize };
+ free(candidateDictBuffer);
+ return selection;
+ }
+
+ largestDict = dictContentSize;
+ largestCompressed = totalCompressedSize;
+ dictContentSize = ZDICT_DICTSIZE_MIN;
+
+ /* Largest dict is initially at least ZDICT_DICTSIZE_MIN */
+ while (dictContentSize < largestDict) {
+ memcpy(candidateDictBuffer, largestDictbuffer, largestDict);
+ dictContentSize = ZDICT_finalizeDictionary(
+ candidateDictBuffer, dictBufferCapacity, customDictContentEnd - dictContentSize, dictContentSize,
+ samplesBuffer, samplesSizes, nbFinalizeSamples, params.zParams);
+
+ if (ZDICT_isError(dictContentSize)) {
+ free(largestDictbuffer);
+ free(candidateDictBuffer);
+ return COVER_dictSelectionError(dictContentSize);
+
+ }
+
+ totalCompressedSize = COVER_checkTotalCompressedSize(params, samplesSizes,
+ samplesBuffer, offsets,
+ nbCheckSamples, nbSamples,
+ candidateDictBuffer, dictContentSize);
+
+ if (ZSTD_isError(totalCompressedSize)) {
+ free(largestDictbuffer);
+ free(candidateDictBuffer);
+ return COVER_dictSelectionError(totalCompressedSize);
+ }
+
+ if (totalCompressedSize <= largestCompressed * regressionTolerance) {
+ COVER_dictSelection_t selection = { candidateDictBuffer, dictContentSize, totalCompressedSize };
+ free(largestDictbuffer);
+ return selection;
+ }
+ dictContentSize *= 2;
+ }
+ dictContentSize = largestDict;
+ totalCompressedSize = largestCompressed;
+ {
+ COVER_dictSelection_t selection = { largestDictbuffer, dictContentSize, totalCompressedSize };
+ free(candidateDictBuffer);
+ return selection;
+ }
+}
+
+/**
+ * Parameters for COVER_tryParameters().
+ */
+typedef struct COVER_tryParameters_data_s {
+ const COVER_ctx_t *ctx;
+ COVER_best_t *best;
+ size_t dictBufferCapacity;
+ ZDICT_cover_params_t parameters;
+} COVER_tryParameters_data_t;
+
+/**
+ * Tries a set of parameters and updates the COVER_best_t with the results.
+ * This function is thread safe if zstd is compiled with multithreaded support.
+ * It takes its parameters as an *OWNING* opaque pointer to support threading.
+ */
+static void COVER_tryParameters(void *opaque)
+{
+ /* Save parameters as local variables */
+ COVER_tryParameters_data_t *const data = (COVER_tryParameters_data_t*)opaque;
+ const COVER_ctx_t *const ctx = data->ctx;
+ const ZDICT_cover_params_t parameters = data->parameters;
+ size_t dictBufferCapacity = data->dictBufferCapacity;
+ size_t totalCompressedSize = ERROR(GENERIC);
+ /* Allocate space for hash table, dict, and freqs */
+ COVER_map_t activeDmers;
+ BYTE* const dict = (BYTE*)malloc(dictBufferCapacity);
+ COVER_dictSelection_t selection = COVER_dictSelectionError(ERROR(GENERIC));
+ U32* const freqs = (U32*)malloc(ctx->suffixSize * sizeof(U32));
+ if (!COVER_map_init(&activeDmers, parameters.k - parameters.d + 1)) {
+ DISPLAYLEVEL(1, "Failed to allocate dmer map: out of memory\n");
+ goto _cleanup;
+ }
+ if (!dict || !freqs) {
+ DISPLAYLEVEL(1, "Failed to allocate buffers: out of memory\n");
+ goto _cleanup;
+ }
+ /* Copy the frequencies because we need to modify them */
+ memcpy(freqs, ctx->freqs, ctx->suffixSize * sizeof(U32));
+ /* Build the dictionary */
+ {
+ const size_t tail = COVER_buildDictionary(ctx, freqs, &activeDmers, dict,
+ dictBufferCapacity, parameters);
+ selection = COVER_selectDict(dict + tail, dictBufferCapacity, dictBufferCapacity - tail,
+ ctx->samples, ctx->samplesSizes, (unsigned)ctx->nbTrainSamples, ctx->nbTrainSamples, ctx->nbSamples, parameters, ctx->offsets,
+ totalCompressedSize);
+
+ if (COVER_dictSelectionIsError(selection)) {
+ DISPLAYLEVEL(1, "Failed to select dictionary\n");
+ goto _cleanup;
+ }
+ }
+_cleanup:
+ free(dict);
+ COVER_best_finish(data->best, parameters, selection);
+ free(data);
+ COVER_map_destroy(&activeDmers);
+ COVER_dictSelectionFree(selection);
+ free(freqs);
+}
+
+ZDICTLIB_API size_t ZDICT_optimizeTrainFromBuffer_cover(
+ void* dictBuffer, size_t dictBufferCapacity, const void* samplesBuffer,
+ const size_t* samplesSizes, unsigned nbSamples,
+ ZDICT_cover_params_t* parameters)
+{
+ /* constants */
+ const unsigned nbThreads = parameters->nbThreads;
+ const double splitPoint =
+ parameters->splitPoint <= 0.0 ? COVER_DEFAULT_SPLITPOINT : parameters->splitPoint;
+ const unsigned kMinD = parameters->d == 0 ? 6 : parameters->d;
+ const unsigned kMaxD = parameters->d == 0 ? 8 : parameters->d;
+ const unsigned kMinK = parameters->k == 0 ? 50 : parameters->k;
+ const unsigned kMaxK = parameters->k == 0 ? 2000 : parameters->k;
+ const unsigned kSteps = parameters->steps == 0 ? 40 : parameters->steps;
+ const unsigned kStepSize = MAX((kMaxK - kMinK) / kSteps, 1);
+ const unsigned kIterations =
+ (1 + (kMaxD - kMinD) / 2) * (1 + (kMaxK - kMinK) / kStepSize);
+ const unsigned shrinkDict = 0;
+ /* Local variables */
+ const int displayLevel = parameters->zParams.notificationLevel;
+ unsigned iteration = 1;
+ unsigned d;
+ unsigned k;
+ COVER_best_t best;
+ POOL_ctx *pool = NULL;
+ int warned = 0;
+
+ /* Checks */
+ if (splitPoint <= 0 || splitPoint > 1) {
+ LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect parameters\n");
+ return ERROR(parameter_outOfBound);
+ }
+ if (kMinK < kMaxD || kMaxK < kMinK) {
+ LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect parameters\n");
+ return ERROR(parameter_outOfBound);
+ }
+ if (nbSamples == 0) {
+ DISPLAYLEVEL(1, "Cover must have at least one input file\n");
+ return ERROR(srcSize_wrong);
+ }
+ if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) {
+ DISPLAYLEVEL(1, "dictBufferCapacity must be at least %u\n",
+ ZDICT_DICTSIZE_MIN);
+ return ERROR(dstSize_tooSmall);
+ }
+ if (nbThreads > 1) {
+ pool = POOL_create(nbThreads, 1);
+ if (!pool) {
+ return ERROR(memory_allocation);
+ }
+ }
+ /* Initialization */
+ COVER_best_init(&best);
+ /* Turn down global display level to clean up display at level 2 and below */
+ g_displayLevel = displayLevel == 0 ? 0 : displayLevel - 1;
+ /* Loop through d first because each new value needs a new context */
+ LOCALDISPLAYLEVEL(displayLevel, 2, "Trying %u different sets of parameters\n",
+ kIterations);
+ for (d = kMinD; d <= kMaxD; d += 2) {
+ /* Initialize the context for this value of d */
+ COVER_ctx_t ctx;
+ LOCALDISPLAYLEVEL(displayLevel, 3, "d=%u\n", d);
+ {
+ const size_t initVal = COVER_ctx_init(&ctx, samplesBuffer, samplesSizes, nbSamples, d, splitPoint);
+ if (ZSTD_isError(initVal)) {
+ LOCALDISPLAYLEVEL(displayLevel, 1, "Failed to initialize context\n");
+ COVER_best_destroy(&best);
+ POOL_free(pool);
+ return initVal;
+ }
+ }
+ if (!warned) {
+ COVER_warnOnSmallCorpus(dictBufferCapacity, ctx.suffixSize, displayLevel);
+ warned = 1;
+ }
+ /* Loop through k reusing the same context */
+ for (k = kMinK; k <= kMaxK; k += kStepSize) {
+ /* Prepare the arguments */
+ COVER_tryParameters_data_t *data = (COVER_tryParameters_data_t *)malloc(
+ sizeof(COVER_tryParameters_data_t));
+ LOCALDISPLAYLEVEL(displayLevel, 3, "k=%u\n", k);
+ if (!data) {
+ LOCALDISPLAYLEVEL(displayLevel, 1, "Failed to allocate parameters\n");
+ COVER_best_destroy(&best);
+ COVER_ctx_destroy(&ctx);
+ POOL_free(pool);
+ return ERROR(memory_allocation);
+ }
+ data->ctx = &ctx;
+ data->best = &best;
+ data->dictBufferCapacity = dictBufferCapacity;
+ data->parameters = *parameters;
+ data->parameters.k = k;
+ data->parameters.d = d;
+ data->parameters.splitPoint = splitPoint;
+ data->parameters.steps = kSteps;
+ data->parameters.shrinkDict = shrinkDict;
+ data->parameters.zParams.notificationLevel = g_displayLevel;
+ /* Check the parameters */
+ if (!COVER_checkParameters(data->parameters, dictBufferCapacity)) {
+ DISPLAYLEVEL(1, "Cover parameters incorrect\n");
+ free(data);
+ continue;
+ }
+ /* Call the function and pass ownership of data to it */
+ COVER_best_start(&best);
+ if (pool) {
+ POOL_add(pool, &COVER_tryParameters, data);
+ } else {
+ COVER_tryParameters(data);
+ }
+ /* Print status */
+ LOCALDISPLAYUPDATE(displayLevel, 2, "\r%u%% ",
+ (unsigned)((iteration * 100) / kIterations));
+ ++iteration;
+ }
+ COVER_best_wait(&best);
+ COVER_ctx_destroy(&ctx);
+ }
+ LOCALDISPLAYLEVEL(displayLevel, 2, "\r%79s\r", "");
+ /* Fill the output buffer and parameters with output of the best parameters */
+ {
+ const size_t dictSize = best.dictSize;
+ if (ZSTD_isError(best.compressedSize)) {
+ const size_t compressedSize = best.compressedSize;
+ COVER_best_destroy(&best);
+ POOL_free(pool);
+ return compressedSize;
+ }
+ *parameters = best.parameters;
+ memcpy(dictBuffer, best.dict, dictSize);
+ COVER_best_destroy(&best);
+ POOL_free(pool);
+ return dictSize;
+ }
+}
diff --git a/zstd/dictBuilder/cover.h b/zstd/dictBuilder/cover.h
new file mode 100644
index 00000000..1aacdddd
--- /dev/null
+++ b/zstd/dictBuilder/cover.h
@@ -0,0 +1,158 @@
+/*
+ * Copyright (c) Facebook, Inc.
+ * All rights reserved.
+ *
+ * This source code is licensed under both the BSD-style license (found in the
+ * LICENSE file in the root directory of this source tree) and the GPLv2 (found
+ * in the COPYING file in the root directory of this source tree).
+ * You may select, at your option, one of the above-listed licenses.
+ */
+
+#ifndef ZDICT_STATIC_LINKING_ONLY
+# define ZDICT_STATIC_LINKING_ONLY
+#endif
+
+#include <stdio.h> /* fprintf */
+#include <stdlib.h> /* malloc, free, qsort */
+#include <string.h> /* memset */
+#include <time.h> /* clock */
+#include "../common/mem.h" /* read */
+#include "../common/pool.h"
+#include "../common/threading.h"
+#include "../common/zstd_internal.h" /* includes zstd.h */
+#include "../zdict.h"
+
+/**
+ * COVER_best_t is used for two purposes:
+ * 1. Synchronizing threads.
+ * 2. Saving the best parameters and dictionary.
+ *
+ * All of the methods except COVER_best_init() are thread safe if zstd is
+ * compiled with multithreaded support.
+ */
+typedef struct COVER_best_s {
+ ZSTD_pthread_mutex_t mutex;
+ ZSTD_pthread_cond_t cond;
+ size_t liveJobs;
+ void *dict;
+ size_t dictSize;
+ ZDICT_cover_params_t parameters;
+ size_t compressedSize;
+} COVER_best_t;
+
+/**
+ * A segment is a range in the source as well as the score of the segment.
+ */
+typedef struct {
+ U32 begin;
+ U32 end;
+ U32 score;
+} COVER_segment_t;
+
+/**
+ *Number of epochs and size of each epoch.
+ */
+typedef struct {
+ U32 num;
+ U32 size;
+} COVER_epoch_info_t;
+
+/**
+ * Struct used for the dictionary selection function.
+ */
+typedef struct COVER_dictSelection {
+ BYTE* dictContent;
+ size_t dictSize;
+ size_t totalCompressedSize;
+} COVER_dictSelection_t;
+
+/**
+ * Computes the number of epochs and the size of each epoch.
+ * We will make sure that each epoch gets at least 10 * k bytes.
+ *
+ * The COVER algorithms divide the data up into epochs of equal size and
+ * select one segment from each epoch.
+ *
+ * @param maxDictSize The maximum allowed dictionary size.
+ * @param nbDmers The number of dmers we are training on.
+ * @param k The parameter k (segment size).
+ * @param passes The target number of passes over the dmer corpus.
+ * More passes means a better dictionary.
+ */
+COVER_epoch_info_t COVER_computeEpochs(U32 maxDictSize, U32 nbDmers,
+ U32 k, U32 passes);
+
+/**
+ * Warns the user when their corpus is too small.
+ */
+void COVER_warnOnSmallCorpus(size_t maxDictSize, size_t nbDmers, int displayLevel);
+
+/**
+ * Checks total compressed size of a dictionary
+ */
+size_t COVER_checkTotalCompressedSize(const ZDICT_cover_params_t parameters,
+ const size_t *samplesSizes, const BYTE *samples,
+ size_t *offsets,
+ size_t nbTrainSamples, size_t nbSamples,
+ BYTE *const dict, size_t dictBufferCapacity);
+
+/**
+ * Returns the sum of the sample sizes.
+ */
+size_t COVER_sum(const size_t *samplesSizes, unsigned nbSamples) ;
+
+/**
+ * Initialize the `COVER_best_t`.
+ */
+void COVER_best_init(COVER_best_t *best);
+
+/**
+ * Wait until liveJobs == 0.
+ */
+void COVER_best_wait(COVER_best_t *best);
+
+/**
+ * Call COVER_best_wait() and then destroy the COVER_best_t.
+ */
+void COVER_best_destroy(COVER_best_t *best);
+
+/**
+ * Called when a thread is about to be launched.
+ * Increments liveJobs.
+ */
+void COVER_best_start(COVER_best_t *best);
+
+/**
+ * Called when a thread finishes executing, both on error or success.
+ * Decrements liveJobs and signals any waiting threads if liveJobs == 0.
+ * If this dictionary is the best so far save it and its parameters.
+ */
+void COVER_best_finish(COVER_best_t *best, ZDICT_cover_params_t parameters,
+ COVER_dictSelection_t selection);
+/**
+ * Error function for COVER_selectDict function. Checks if the return
+ * value is an error.
+ */
+unsigned COVER_dictSelectionIsError(COVER_dictSelection_t selection);
+
+ /**
+ * Error function for COVER_selectDict function. Returns a struct where
+ * return.totalCompressedSize is a ZSTD error.
+ */
+COVER_dictSelection_t COVER_dictSelectionError(size_t error);
+
+/**
+ * Always call after selectDict is called to free up used memory from
+ * newly created dictionary.
+ */
+void COVER_dictSelectionFree(COVER_dictSelection_t selection);
+
+/**
+ * Called to finalize the dictionary and select one based on whether or not
+ * the shrink-dict flag was enabled. If enabled the dictionary used is the
+ * smallest dictionary within a specified regression of the compressed size
+ * from the largest dictionary.
+ */
+ COVER_dictSelection_t COVER_selectDict(BYTE* customDictContent, size_t dictBufferCapacity,
+ size_t dictContentSize, const BYTE* samplesBuffer, const size_t* samplesSizes, unsigned nbFinalizeSamples,
+ size_t nbCheckSamples, size_t nbSamples, ZDICT_cover_params_t params, size_t* offsets, size_t totalCompressedSize);
diff --git a/zstd/dictBuilder/divsufsort.c b/zstd/dictBuilder/divsufsort.c
new file mode 100644
index 00000000..a2870fb3
--- /dev/null
+++ b/zstd/dictBuilder/divsufsort.c
@@ -0,0 +1,1913 @@
+/*
+ * divsufsort.c for libdivsufsort-lite
+ * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved.
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/*- Compiler specifics -*/
+#ifdef __clang__
+#pragma clang diagnostic ignored "-Wshorten-64-to-32"
+#endif
+
+#if defined(_MSC_VER)
+# pragma warning(disable : 4244)
+# pragma warning(disable : 4127) /* C4127 : Condition expression is constant */
+#endif
+
+
+/*- Dependencies -*/
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "divsufsort.h"
+
+/*- Constants -*/
+#if defined(INLINE)
+# undef INLINE
+#endif
+#if !defined(INLINE)
+# define INLINE __inline
+#endif
+#if defined(ALPHABET_SIZE) && (ALPHABET_SIZE < 1)
+# undef ALPHABET_SIZE
+#endif
+#if !defined(ALPHABET_SIZE)
+# define ALPHABET_SIZE (256)
+#endif
+#define BUCKET_A_SIZE (ALPHABET_SIZE)
+#define BUCKET_B_SIZE (ALPHABET_SIZE * ALPHABET_SIZE)
+#if defined(SS_INSERTIONSORT_THRESHOLD)
+# if SS_INSERTIONSORT_THRESHOLD < 1
+# undef SS_INSERTIONSORT_THRESHOLD
+# define SS_INSERTIONSORT_THRESHOLD (1)
+# endif
+#else
+# define SS_INSERTIONSORT_THRESHOLD (8)
+#endif
+#if defined(SS_BLOCKSIZE)
+# if SS_BLOCKSIZE < 0
+# undef SS_BLOCKSIZE
+# define SS_BLOCKSIZE (0)
+# elif 32768 <= SS_BLOCKSIZE
+# undef SS_BLOCKSIZE
+# define SS_BLOCKSIZE (32767)
+# endif
+#else
+# define SS_BLOCKSIZE (1024)
+#endif
+/* minstacksize = log(SS_BLOCKSIZE) / log(3) * 2 */
+#if SS_BLOCKSIZE == 0
+# define SS_MISORT_STACKSIZE (96)
+#elif SS_BLOCKSIZE <= 4096
+# define SS_MISORT_STACKSIZE (16)
+#else
+# define SS_MISORT_STACKSIZE (24)
+#endif
+#define SS_SMERGE_STACKSIZE (32)
+#define TR_INSERTIONSORT_THRESHOLD (8)
+#define TR_STACKSIZE (64)
+
+
+/*- Macros -*/
+#ifndef SWAP
+# define SWAP(_a, _b) do { t = (_a); (_a) = (_b); (_b) = t; } while(0)
+#endif /* SWAP */
+#ifndef MIN
+# define MIN(_a, _b) (((_a) < (_b)) ? (_a) : (_b))
+#endif /* MIN */
+#ifndef MAX
+# define MAX(_a, _b) (((_a) > (_b)) ? (_a) : (_b))
+#endif /* MAX */
+#define STACK_PUSH(_a, _b, _c, _d)\
+ do {\
+ assert(ssize < STACK_SIZE);\
+ stack[ssize].a = (_a), stack[ssize].b = (_b),\
+ stack[ssize].c = (_c), stack[ssize++].d = (_d);\
+ } while(0)
+#define STACK_PUSH5(_a, _b, _c, _d, _e)\
+ do {\
+ assert(ssize < STACK_SIZE);\
+ stack[ssize].a = (_a), stack[ssize].b = (_b),\
+ stack[ssize].c = (_c), stack[ssize].d = (_d), stack[ssize++].e = (_e);\
+ } while(0)
+#define STACK_POP(_a, _b, _c, _d)\
+ do {\
+ assert(0 <= ssize);\
+ if(ssize == 0) { return; }\
+ (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\
+ (_c) = stack[ssize].c, (_d) = stack[ssize].d;\
+ } while(0)
+#define STACK_POP5(_a, _b, _c, _d, _e)\
+ do {\
+ assert(0 <= ssize);\
+ if(ssize == 0) { return; }\
+ (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\
+ (_c) = stack[ssize].c, (_d) = stack[ssize].d, (_e) = stack[ssize].e;\
+ } while(0)
+#define BUCKET_A(_c0) bucket_A[(_c0)]
+#if ALPHABET_SIZE == 256
+#define BUCKET_B(_c0, _c1) (bucket_B[((_c1) << 8) | (_c0)])
+#define BUCKET_BSTAR(_c0, _c1) (bucket_B[((_c0) << 8) | (_c1)])
+#else
+#define BUCKET_B(_c0, _c1) (bucket_B[(_c1) * ALPHABET_SIZE + (_c0)])
+#define BUCKET_BSTAR(_c0, _c1) (bucket_B[(_c0) * ALPHABET_SIZE + (_c1)])
+#endif
+
+
+/*- Private Functions -*/
+
+static const int lg_table[256]= {
+ -1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
+ 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
+ 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
+ 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
+};
+
+#if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)
+
+static INLINE
+int
+ss_ilg(int n) {
+#if SS_BLOCKSIZE == 0
+ return (n & 0xffff0000) ?
+ ((n & 0xff000000) ?
+ 24 + lg_table[(n >> 24) & 0xff] :
+ 16 + lg_table[(n >> 16) & 0xff]) :
+ ((n & 0x0000ff00) ?
+ 8 + lg_table[(n >> 8) & 0xff] :
+ 0 + lg_table[(n >> 0) & 0xff]);
+#elif SS_BLOCKSIZE < 256
+ return lg_table[n];
+#else
+ return (n & 0xff00) ?
+ 8 + lg_table[(n >> 8) & 0xff] :
+ 0 + lg_table[(n >> 0) & 0xff];
+#endif
+}
+
+#endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */
+
+#if SS_BLOCKSIZE != 0
+
+static const int sqq_table[256] = {
+ 0, 16, 22, 27, 32, 35, 39, 42, 45, 48, 50, 53, 55, 57, 59, 61,
+ 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83, 84, 86, 87, 89,
+ 90, 91, 93, 94, 96, 97, 98, 99, 101, 102, 103, 104, 106, 107, 108, 109,
+110, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126,
+128, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142,
+143, 144, 144, 145, 146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155,
+156, 157, 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168,
+169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178, 179, 180,
+181, 181, 182, 183, 183, 184, 185, 185, 186, 187, 187, 188, 189, 189, 190, 191,
+192, 192, 193, 193, 194, 195, 195, 196, 197, 197, 198, 199, 199, 200, 201, 201,
+202, 203, 203, 204, 204, 205, 206, 206, 207, 208, 208, 209, 209, 210, 211, 211,
+212, 212, 213, 214, 214, 215, 215, 216, 217, 217, 218, 218, 219, 219, 220, 221,
+221, 222, 222, 223, 224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230,
+230, 231, 231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238,
+239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246, 246, 247,
+247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255
+};
+
+static INLINE
+int
+ss_isqrt(int x) {
+ int y, e;
+
+ if(x >= (SS_BLOCKSIZE * SS_BLOCKSIZE)) { return SS_BLOCKSIZE; }
+ e = (x & 0xffff0000) ?
+ ((x & 0xff000000) ?
+ 24 + lg_table[(x >> 24) & 0xff] :
+ 16 + lg_table[(x >> 16) & 0xff]) :
+ ((x & 0x0000ff00) ?
+ 8 + lg_table[(x >> 8) & 0xff] :
+ 0 + lg_table[(x >> 0) & 0xff]);
+
+ if(e >= 16) {
+ y = sqq_table[x >> ((e - 6) - (e & 1))] << ((e >> 1) - 7);
+ if(e >= 24) { y = (y + 1 + x / y) >> 1; }
+ y = (y + 1 + x / y) >> 1;
+ } else if(e >= 8) {
+ y = (sqq_table[x >> ((e - 6) - (e & 1))] >> (7 - (e >> 1))) + 1;
+ } else {
+ return sqq_table[x] >> 4;
+ }
+
+ return (x < (y * y)) ? y - 1 : y;
+}
+
+#endif /* SS_BLOCKSIZE != 0 */
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Compares two suffixes. */
+static INLINE
+int
+ss_compare(const unsigned char *T,
+ const int *p1, const int *p2,
+ int depth) {
+ const unsigned char *U1, *U2, *U1n, *U2n;
+
+ for(U1 = T + depth + *p1,
+ U2 = T + depth + *p2,
+ U1n = T + *(p1 + 1) + 2,
+ U2n = T + *(p2 + 1) + 2;
+ (U1 < U1n) && (U2 < U2n) && (*U1 == *U2);
+ ++U1, ++U2) {
+ }
+
+ return U1 < U1n ?
+ (U2 < U2n ? *U1 - *U2 : 1) :
+ (U2 < U2n ? -1 : 0);
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+#if (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1)
+
+/* Insertionsort for small size groups */
+static
+void
+ss_insertionsort(const unsigned char *T, const int *PA,
+ int *first, int *last, int depth) {
+ int *i, *j;
+ int t;
+ int r;
+
+ for(i = last - 2; first <= i; --i) {
+ for(t = *i, j = i + 1; 0 < (r = ss_compare(T, PA + t, PA + *j, depth));) {
+ do { *(j - 1) = *j; } while((++j < last) && (*j < 0));
+ if(last <= j) { break; }
+ }
+ if(r == 0) { *j = ~*j; }
+ *(j - 1) = t;
+ }
+}
+
+#endif /* (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1) */
+
+
+/*---------------------------------------------------------------------------*/
+
+#if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)
+
+static INLINE
+void
+ss_fixdown(const unsigned char *Td, const int *PA,
+ int *SA, int i, int size) {
+ int j, k;
+ int v;
+ int c, d, e;
+
+ for(v = SA[i], c = Td[PA[v]]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) {
+ d = Td[PA[SA[k = j++]]];
+ if(d < (e = Td[PA[SA[j]]])) { k = j; d = e; }
+ if(d <= c) { break; }
+ }
+ SA[i] = v;
+}
+
+/* Simple top-down heapsort. */
+static
+void
+ss_heapsort(const unsigned char *Td, const int *PA, int *SA, int size) {
+ int i, m;
+ int t;
+
+ m = size;
+ if((size % 2) == 0) {
+ m--;
+ if(Td[PA[SA[m / 2]]] < Td[PA[SA[m]]]) { SWAP(SA[m], SA[m / 2]); }
+ }
+
+ for(i = m / 2 - 1; 0 <= i; --i) { ss_fixdown(Td, PA, SA, i, m); }
+ if((size % 2) == 0) { SWAP(SA[0], SA[m]); ss_fixdown(Td, PA, SA, 0, m); }
+ for(i = m - 1; 0 < i; --i) {
+ t = SA[0], SA[0] = SA[i];
+ ss_fixdown(Td, PA, SA, 0, i);
+ SA[i] = t;
+ }
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Returns the median of three elements. */
+static INLINE
+int *
+ss_median3(const unsigned char *Td, const int *PA,
+ int *v1, int *v2, int *v3) {
+ int *t;
+ if(Td[PA[*v1]] > Td[PA[*v2]]) { SWAP(v1, v2); }
+ if(Td[PA[*v2]] > Td[PA[*v3]]) {
+ if(Td[PA[*v1]] > Td[PA[*v3]]) { return v1; }
+ else { return v3; }
+ }
+ return v2;
+}
+
+/* Returns the median of five elements. */
+static INLINE
+int *
+ss_median5(const unsigned char *Td, const int *PA,
+ int *v1, int *v2, int *v3, int *v4, int *v5) {
+ int *t;
+ if(Td[PA[*v2]] > Td[PA[*v3]]) { SWAP(v2, v3); }
+ if(Td[PA[*v4]] > Td[PA[*v5]]) { SWAP(v4, v5); }
+ if(Td[PA[*v2]] > Td[PA[*v4]]) { SWAP(v2, v4); SWAP(v3, v5); }
+ if(Td[PA[*v1]] > Td[PA[*v3]]) { SWAP(v1, v3); }
+ if(Td[PA[*v1]] > Td[PA[*v4]]) { SWAP(v1, v4); SWAP(v3, v5); }
+ if(Td[PA[*v3]] > Td[PA[*v4]]) { return v4; }
+ return v3;
+}
+
+/* Returns the pivot element. */
+static INLINE
+int *
+ss_pivot(const unsigned char *Td, const int *PA, int *first, int *last) {
+ int *middle;
+ int t;
+
+ t = last - first;
+ middle = first + t / 2;
+
+ if(t <= 512) {
+ if(t <= 32) {
+ return ss_median3(Td, PA, first, middle, last - 1);
+ } else {
+ t >>= 2;
+ return ss_median5(Td, PA, first, first + t, middle, last - 1 - t, last - 1);
+ }
+ }
+ t >>= 3;
+ first = ss_median3(Td, PA, first, first + t, first + (t << 1));
+ middle = ss_median3(Td, PA, middle - t, middle, middle + t);
+ last = ss_median3(Td, PA, last - 1 - (t << 1), last - 1 - t, last - 1);
+ return ss_median3(Td, PA, first, middle, last);
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Binary partition for substrings. */
+static INLINE
+int *
+ss_partition(const int *PA,
+ int *first, int *last, int depth) {
+ int *a, *b;
+ int t;
+ for(a = first - 1, b = last;;) {
+ for(; (++a < b) && ((PA[*a] + depth) >= (PA[*a + 1] + 1));) { *a = ~*a; }
+ for(; (a < --b) && ((PA[*b] + depth) < (PA[*b + 1] + 1));) { }
+ if(b <= a) { break; }
+ t = ~*b;
+ *b = *a;
+ *a = t;
+ }
+ if(first < a) { *first = ~*first; }
+ return a;
+}
+
+/* Multikey introsort for medium size groups. */
+static
+void
+ss_mintrosort(const unsigned char *T, const int *PA,
+ int *first, int *last,
+ int depth) {
+#define STACK_SIZE SS_MISORT_STACKSIZE
+ struct { int *a, *b, c; int d; } stack[STACK_SIZE];
+ const unsigned char *Td;
+ int *a, *b, *c, *d, *e, *f;
+ int s, t;
+ int ssize;
+ int limit;
+ int v, x = 0;
+
+ for(ssize = 0, limit = ss_ilg(last - first);;) {
+
+ if((last - first) <= SS_INSERTIONSORT_THRESHOLD) {
+#if 1 < SS_INSERTIONSORT_THRESHOLD
+ if(1 < (last - first)) { ss_insertionsort(T, PA, first, last, depth); }
+#endif
+ STACK_POP(first, last, depth, limit);
+ continue;
+ }
+
+ Td = T + depth;
+ if(limit-- == 0) { ss_heapsort(Td, PA, first, last - first); }
+ if(limit < 0) {
+ for(a = first + 1, v = Td[PA[*first]]; a < last; ++a) {
+ if((x = Td[PA[*a]]) != v) {
+ if(1 < (a - first)) { break; }
+ v = x;
+ first = a;
+ }
+ }
+ if(Td[PA[*first] - 1] < v) {
+ first = ss_partition(PA, first, a, depth);
+ }
+ if((a - first) <= (last - a)) {
+ if(1 < (a - first)) {
+ STACK_PUSH(a, last, depth, -1);
+ last = a, depth += 1, limit = ss_ilg(a - first);
+ } else {
+ first = a, limit = -1;
+ }
+ } else {
+ if(1 < (last - a)) {
+ STACK_PUSH(first, a, depth + 1, ss_ilg(a - first));
+ first = a, limit = -1;
+ } else {
+ last = a, depth += 1, limit = ss_ilg(a - first);
+ }
+ }
+ continue;
+ }
+
+ /* choose pivot */
+ a = ss_pivot(Td, PA, first, last);
+ v = Td[PA[*a]];
+ SWAP(*first, *a);
+
+ /* partition */
+ for(b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) { }
+ if(((a = b) < last) && (x < v)) {
+ for(; (++b < last) && ((x = Td[PA[*b]]) <= v);) {
+ if(x == v) { SWAP(*b, *a); ++a; }
+ }
+ }
+ for(c = last; (b < --c) && ((x = Td[PA[*c]]) == v);) { }
+ if((b < (d = c)) && (x > v)) {
+ for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
+ if(x == v) { SWAP(*c, *d); --d; }
+ }
+ }
+ for(; b < c;) {
+ SWAP(*b, *c);
+ for(; (++b < c) && ((x = Td[PA[*b]]) <= v);) {
+ if(x == v) { SWAP(*b, *a); ++a; }
+ }
+ for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
+ if(x == v) { SWAP(*c, *d); --d; }
+ }
+ }
+
+ if(a <= d) {
+ c = b - 1;
+
+ if((s = a - first) > (t = b - a)) { s = t; }
+ for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
+ if((s = d - c) > (t = last - d - 1)) { s = t; }
+ for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
+
+ a = first + (b - a), c = last - (d - c);
+ b = (v <= Td[PA[*a] - 1]) ? a : ss_partition(PA, a, c, depth);
+
+ if((a - first) <= (last - c)) {
+ if((last - c) <= (c - b)) {
+ STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
+ STACK_PUSH(c, last, depth, limit);
+ last = a;
+ } else if((a - first) <= (c - b)) {
+ STACK_PUSH(c, last, depth, limit);
+ STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
+ last = a;
+ } else {
+ STACK_PUSH(c, last, depth, limit);
+ STACK_PUSH(first, a, depth, limit);
+ first = b, last = c, depth += 1, limit = ss_ilg(c - b);
+ }
+ } else {
+ if((a - first) <= (c - b)) {
+ STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
+ STACK_PUSH(first, a, depth, limit);
+ first = c;
+ } else if((last - c) <= (c - b)) {
+ STACK_PUSH(first, a, depth, limit);
+ STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
+ first = c;
+ } else {
+ STACK_PUSH(first, a, depth, limit);
+ STACK_PUSH(c, last, depth, limit);
+ first = b, last = c, depth += 1, limit = ss_ilg(c - b);
+ }
+ }
+ } else {
+ limit += 1;
+ if(Td[PA[*first] - 1] < v) {
+ first = ss_partition(PA, first, last, depth);
+ limit = ss_ilg(last - first);
+ }
+ depth += 1;
+ }
+ }
+#undef STACK_SIZE
+}
+
+#endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */
+
+
+/*---------------------------------------------------------------------------*/
+
+#if SS_BLOCKSIZE != 0
+
+static INLINE
+void
+ss_blockswap(int *a, int *b, int n) {
+ int t;
+ for(; 0 < n; --n, ++a, ++b) {
+ t = *a, *a = *b, *b = t;
+ }
+}
+
+static INLINE
+void
+ss_rotate(int *first, int *middle, int *last) {
+ int *a, *b, t;
+ int l, r;
+ l = middle - first, r = last - middle;
+ for(; (0 < l) && (0 < r);) {
+ if(l == r) { ss_blockswap(first, middle, l); break; }
+ if(l < r) {
+ a = last - 1, b = middle - 1;
+ t = *a;
+ do {
+ *a-- = *b, *b-- = *a;
+ if(b < first) {
+ *a = t;
+ last = a;
+ if((r -= l + 1) <= l) { break; }
+ a -= 1, b = middle - 1;
+ t = *a;
+ }
+ } while(1);
+ } else {
+ a = first, b = middle;
+ t = *a;
+ do {
+ *a++ = *b, *b++ = *a;
+ if(last <= b) {
+ *a = t;
+ first = a + 1;
+ if((l -= r + 1) <= r) { break; }
+ a += 1, b = middle;
+ t = *a;
+ }
+ } while(1);
+ }
+ }
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+static
+void
+ss_inplacemerge(const unsigned char *T, const int *PA,
+ int *first, int *middle, int *last,
+ int depth) {
+ const int *p;
+ int *a, *b;
+ int len, half;
+ int q, r;
+ int x;
+
+ for(;;) {
+ if(*(last - 1) < 0) { x = 1; p = PA + ~*(last - 1); }
+ else { x = 0; p = PA + *(last - 1); }
+ for(a = first, len = middle - first, half = len >> 1, r = -1;
+ 0 < len;
+ len = half, half >>= 1) {
+ b = a + half;
+ q = ss_compare(T, PA + ((0 <= *b) ? *b : ~*b), p, depth);
+ if(q < 0) {
+ a = b + 1;
+ half -= (len & 1) ^ 1;
+ } else {
+ r = q;
+ }
+ }
+ if(a < middle) {
+ if(r == 0) { *a = ~*a; }
+ ss_rotate(a, middle, last);
+ last -= middle - a;
+ middle = a;
+ if(first == middle) { break; }
+ }
+ --last;
+ if(x != 0) { while(*--last < 0) { } }
+ if(middle == last) { break; }
+ }
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Merge-forward with internal buffer. */
+static
+void
+ss_mergeforward(const unsigned char *T, const int *PA,
+ int *first, int *middle, int *last,
+ int *buf, int depth) {
+ int *a, *b, *c, *bufend;
+ int t;
+ int r;
+
+ bufend = buf + (middle - first) - 1;
+ ss_blockswap(buf, first, middle - first);
+
+ for(t = *(a = first), b = buf, c = middle;;) {
+ r = ss_compare(T, PA + *b, PA + *c, depth);
+ if(r < 0) {
+ do {
+ *a++ = *b;
+ if(bufend <= b) { *bufend = t; return; }
+ *b++ = *a;
+ } while(*b < 0);
+ } else if(r > 0) {
+ do {
+ *a++ = *c, *c++ = *a;
+ if(last <= c) {
+ while(b < bufend) { *a++ = *b, *b++ = *a; }
+ *a = *b, *b = t;
+ return;
+ }
+ } while(*c < 0);
+ } else {
+ *c = ~*c;
+ do {
+ *a++ = *b;
+ if(bufend <= b) { *bufend = t; return; }
+ *b++ = *a;
+ } while(*b < 0);
+
+ do {
+ *a++ = *c, *c++ = *a;
+ if(last <= c) {
+ while(b < bufend) { *a++ = *b, *b++ = *a; }
+ *a = *b, *b = t;
+ return;
+ }
+ } while(*c < 0);
+ }
+ }
+}
+
+/* Merge-backward with internal buffer. */
+static
+void
+ss_mergebackward(const unsigned char *T, const int *PA,
+ int *first, int *middle, int *last,
+ int *buf, int depth) {
+ const int *p1, *p2;
+ int *a, *b, *c, *bufend;
+ int t;
+ int r;
+ int x;
+
+ bufend = buf + (last - middle) - 1;
+ ss_blockswap(buf, middle, last - middle);
+
+ x = 0;
+ if(*bufend < 0) { p1 = PA + ~*bufend; x |= 1; }
+ else { p1 = PA + *bufend; }
+ if(*(middle - 1) < 0) { p2 = PA + ~*(middle - 1); x |= 2; }
+ else { p2 = PA + *(middle - 1); }
+ for(t = *(a = last - 1), b = bufend, c = middle - 1;;) {
+ r = ss_compare(T, p1, p2, depth);
+ if(0 < r) {
+ if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; }
+ *a-- = *b;
+ if(b <= buf) { *buf = t; break; }
+ *b-- = *a;
+ if(*b < 0) { p1 = PA + ~*b; x |= 1; }
+ else { p1 = PA + *b; }
+ } else if(r < 0) {
+ if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; }
+ *a-- = *c, *c-- = *a;
+ if(c < first) {
+ while(buf < b) { *a-- = *b, *b-- = *a; }
+ *a = *b, *b = t;
+ break;
+ }
+ if(*c < 0) { p2 = PA + ~*c; x |= 2; }
+ else { p2 = PA + *c; }
+ } else {
+ if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; }
+ *a-- = ~*b;
+ if(b <= buf) { *buf = t; break; }
+ *b-- = *a;
+ if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; }
+ *a-- = *c, *c-- = *a;
+ if(c < first) {
+ while(buf < b) { *a-- = *b, *b-- = *a; }
+ *a = *b, *b = t;
+ break;
+ }
+ if(*b < 0) { p1 = PA + ~*b; x |= 1; }
+ else { p1 = PA + *b; }
+ if(*c < 0) { p2 = PA + ~*c; x |= 2; }
+ else { p2 = PA + *c; }
+ }
+ }
+}
+
+/* D&C based merge. */
+static
+void
+ss_swapmerge(const unsigned char *T, const int *PA,
+ int *first, int *middle, int *last,
+ int *buf, int bufsize, int depth) {
+#define STACK_SIZE SS_SMERGE_STACKSIZE
+#define GETIDX(a) ((0 <= (a)) ? (a) : (~(a)))
+#define MERGE_CHECK(a, b, c)\
+ do {\
+ if(((c) & 1) ||\
+ (((c) & 2) && (ss_compare(T, PA + GETIDX(*((a) - 1)), PA + *(a), depth) == 0))) {\
+ *(a) = ~*(a);\
+ }\
+ if(((c) & 4) && ((ss_compare(T, PA + GETIDX(*((b) - 1)), PA + *(b), depth) == 0))) {\
+ *(b) = ~*(b);\
+ }\
+ } while(0)
+ struct { int *a, *b, *c; int d; } stack[STACK_SIZE];
+ int *l, *r, *lm, *rm;
+ int m, len, half;
+ int ssize;
+ int check, next;
+
+ for(check = 0, ssize = 0;;) {
+ if((last - middle) <= bufsize) {
+ if((first < middle) && (middle < last)) {
+ ss_mergebackward(T, PA, first, middle, last, buf, depth);
+ }
+ MERGE_CHECK(first, last, check);
+ STACK_POP(first, middle, last, check);
+ continue;
+ }
+
+ if((middle - first) <= bufsize) {
+ if(first < middle) {
+ ss_mergeforward(T, PA, first, middle, last, buf, depth);
+ }
+ MERGE_CHECK(first, last, check);
+ STACK_POP(first, middle, last, check);
+ continue;
+ }
+
+ for(m = 0, len = MIN(middle - first, last - middle), half = len >> 1;
+ 0 < len;
+ len = half, half >>= 1) {
+ if(ss_compare(T, PA + GETIDX(*(middle + m + half)),
+ PA + GETIDX(*(middle - m - half - 1)), depth) < 0) {
+ m += half + 1;
+ half -= (len & 1) ^ 1;
+ }
+ }
+
+ if(0 < m) {
+ lm = middle - m, rm = middle + m;
+ ss_blockswap(lm, middle, m);
+ l = r = middle, next = 0;
+ if(rm < last) {
+ if(*rm < 0) {
+ *rm = ~*rm;
+ if(first < lm) { for(; *--l < 0;) { } next |= 4; }
+ next |= 1;
+ } else if(first < lm) {
+ for(; *r < 0; ++r) { }
+ next |= 2;
+ }
+ }
+
+ if((l - first) <= (last - r)) {
+ STACK_PUSH(r, rm, last, (next & 3) | (check & 4));
+ middle = lm, last = l, check = (check & 3) | (next & 4);
+ } else {
+ if((next & 2) && (r == middle)) { next ^= 6; }
+ STACK_PUSH(first, lm, l, (check & 3) | (next & 4));
+ first = r, middle = rm, check = (next & 3) | (check & 4);
+ }
+ } else {
+ if(ss_compare(T, PA + GETIDX(*(middle - 1)), PA + *middle, depth) == 0) {
+ *middle = ~*middle;
+ }
+ MERGE_CHECK(first, last, check);
+ STACK_POP(first, middle, last, check);
+ }
+ }
+#undef STACK_SIZE
+}
+
+#endif /* SS_BLOCKSIZE != 0 */
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Substring sort */
+static
+void
+sssort(const unsigned char *T, const int *PA,
+ int *first, int *last,
+ int *buf, int bufsize,
+ int depth, int n, int lastsuffix) {
+ int *a;
+#if SS_BLOCKSIZE != 0
+ int *b, *middle, *curbuf;
+ int j, k, curbufsize, limit;
+#endif
+ int i;
+
+ if(lastsuffix != 0) { ++first; }
+
+#if SS_BLOCKSIZE == 0
+ ss_mintrosort(T, PA, first, last, depth);
+#else
+ if((bufsize < SS_BLOCKSIZE) &&
+ (bufsize < (last - first)) &&
+ (bufsize < (limit = ss_isqrt(last - first)))) {
+ if(SS_BLOCKSIZE < limit) { limit = SS_BLOCKSIZE; }
+ buf = middle = last - limit, bufsize = limit;
+ } else {
+ middle = last, limit = 0;
+ }
+ for(a = first, i = 0; SS_BLOCKSIZE < (middle - a); a += SS_BLOCKSIZE, ++i) {
+#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
+ ss_mintrosort(T, PA, a, a + SS_BLOCKSIZE, depth);
+#elif 1 < SS_BLOCKSIZE
+ ss_insertionsort(T, PA, a, a + SS_BLOCKSIZE, depth);
+#endif
+ curbufsize = last - (a + SS_BLOCKSIZE);
+ curbuf = a + SS_BLOCKSIZE;
+ if(curbufsize <= bufsize) { curbufsize = bufsize, curbuf = buf; }
+ for(b = a, k = SS_BLOCKSIZE, j = i; j & 1; b -= k, k <<= 1, j >>= 1) {
+ ss_swapmerge(T, PA, b - k, b, b + k, curbuf, curbufsize, depth);
+ }
+ }
+#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
+ ss_mintrosort(T, PA, a, middle, depth);
+#elif 1 < SS_BLOCKSIZE
+ ss_insertionsort(T, PA, a, middle, depth);
+#endif
+ for(k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) {
+ if(i & 1) {
+ ss_swapmerge(T, PA, a - k, a, middle, buf, bufsize, depth);
+ a -= k;
+ }
+ }
+ if(limit != 0) {
+#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
+ ss_mintrosort(T, PA, middle, last, depth);
+#elif 1 < SS_BLOCKSIZE
+ ss_insertionsort(T, PA, middle, last, depth);
+#endif
+ ss_inplacemerge(T, PA, first, middle, last, depth);
+ }
+#endif
+
+ if(lastsuffix != 0) {
+ /* Insert last type B* suffix. */
+ int PAi[2]; PAi[0] = PA[*(first - 1)], PAi[1] = n - 2;
+ for(a = first, i = *(first - 1);
+ (a < last) && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth)));
+ ++a) {
+ *(a - 1) = *a;
+ }
+ *(a - 1) = i;
+ }
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+static INLINE
+int
+tr_ilg(int n) {
+ return (n & 0xffff0000) ?
+ ((n & 0xff000000) ?
+ 24 + lg_table[(n >> 24) & 0xff] :
+ 16 + lg_table[(n >> 16) & 0xff]) :
+ ((n & 0x0000ff00) ?
+ 8 + lg_table[(n >> 8) & 0xff] :
+ 0 + lg_table[(n >> 0) & 0xff]);
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Simple insertionsort for small size groups. */
+static
+void
+tr_insertionsort(const int *ISAd, int *first, int *last) {
+ int *a, *b;
+ int t, r;
+
+ for(a = first + 1; a < last; ++a) {
+ for(t = *a, b = a - 1; 0 > (r = ISAd[t] - ISAd[*b]);) {
+ do { *(b + 1) = *b; } while((first <= --b) && (*b < 0));
+ if(b < first) { break; }
+ }
+ if(r == 0) { *b = ~*b; }
+ *(b + 1) = t;
+ }
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+static INLINE
+void
+tr_fixdown(const int *ISAd, int *SA, int i, int size) {
+ int j, k;
+ int v;
+ int c, d, e;
+
+ for(v = SA[i], c = ISAd[v]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) {
+ d = ISAd[SA[k = j++]];
+ if(d < (e = ISAd[SA[j]])) { k = j; d = e; }
+ if(d <= c) { break; }
+ }
+ SA[i] = v;
+}
+
+/* Simple top-down heapsort. */
+static
+void
+tr_heapsort(const int *ISAd, int *SA, int size) {
+ int i, m;
+ int t;
+
+ m = size;
+ if((size % 2) == 0) {
+ m--;
+ if(ISAd[SA[m / 2]] < ISAd[SA[m]]) { SWAP(SA[m], SA[m / 2]); }
+ }
+
+ for(i = m / 2 - 1; 0 <= i; --i) { tr_fixdown(ISAd, SA, i, m); }
+ if((size % 2) == 0) { SWAP(SA[0], SA[m]); tr_fixdown(ISAd, SA, 0, m); }
+ for(i = m - 1; 0 < i; --i) {
+ t = SA[0], SA[0] = SA[i];
+ tr_fixdown(ISAd, SA, 0, i);
+ SA[i] = t;
+ }
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Returns the median of three elements. */
+static INLINE
+int *
+tr_median3(const int *ISAd, int *v1, int *v2, int *v3) {
+ int *t;
+ if(ISAd[*v1] > ISAd[*v2]) { SWAP(v1, v2); }
+ if(ISAd[*v2] > ISAd[*v3]) {
+ if(ISAd[*v1] > ISAd[*v3]) { return v1; }
+ else { return v3; }
+ }
+ return v2;
+}
+
+/* Returns the median of five elements. */
+static INLINE
+int *
+tr_median5(const int *ISAd,
+ int *v1, int *v2, int *v3, int *v4, int *v5) {
+ int *t;
+ if(ISAd[*v2] > ISAd[*v3]) { SWAP(v2, v3); }
+ if(ISAd[*v4] > ISAd[*v5]) { SWAP(v4, v5); }
+ if(ISAd[*v2] > ISAd[*v4]) { SWAP(v2, v4); SWAP(v3, v5); }
+ if(ISAd[*v1] > ISAd[*v3]) { SWAP(v1, v3); }
+ if(ISAd[*v1] > ISAd[*v4]) { SWAP(v1, v4); SWAP(v3, v5); }
+ if(ISAd[*v3] > ISAd[*v4]) { return v4; }
+ return v3;
+}
+
+/* Returns the pivot element. */
+static INLINE
+int *
+tr_pivot(const int *ISAd, int *first, int *last) {
+ int *middle;
+ int t;
+
+ t = last - first;
+ middle = first + t / 2;
+
+ if(t <= 512) {
+ if(t <= 32) {
+ return tr_median3(ISAd, first, middle, last - 1);
+ } else {
+ t >>= 2;
+ return tr_median5(ISAd, first, first + t, middle, last - 1 - t, last - 1);
+ }
+ }
+ t >>= 3;
+ first = tr_median3(ISAd, first, first + t, first + (t << 1));
+ middle = tr_median3(ISAd, middle - t, middle, middle + t);
+ last = tr_median3(ISAd, last - 1 - (t << 1), last - 1 - t, last - 1);
+ return tr_median3(ISAd, first, middle, last);
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+typedef struct _trbudget_t trbudget_t;
+struct _trbudget_t {
+ int chance;
+ int remain;
+ int incval;
+ int count;
+};
+
+static INLINE
+void
+trbudget_init(trbudget_t *budget, int chance, int incval) {
+ budget->chance = chance;
+ budget->remain = budget->incval = incval;
+}
+
+static INLINE
+int
+trbudget_check(trbudget_t *budget, int size) {
+ if(size <= budget->remain) { budget->remain -= size; return 1; }
+ if(budget->chance == 0) { budget->count += size; return 0; }
+ budget->remain += budget->incval - size;
+ budget->chance -= 1;
+ return 1;
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+static INLINE
+void
+tr_partition(const int *ISAd,
+ int *first, int *middle, int *last,
+ int **pa, int **pb, int v) {
+ int *a, *b, *c, *d, *e, *f;
+ int t, s;
+ int x = 0;
+
+ for(b = middle - 1; (++b < last) && ((x = ISAd[*b]) == v);) { }
+ if(((a = b) < last) && (x < v)) {
+ for(; (++b < last) && ((x = ISAd[*b]) <= v);) {
+ if(x == v) { SWAP(*b, *a); ++a; }
+ }
+ }
+ for(c = last; (b < --c) && ((x = ISAd[*c]) == v);) { }
+ if((b < (d = c)) && (x > v)) {
+ for(; (b < --c) && ((x = ISAd[*c]) >= v);) {
+ if(x == v) { SWAP(*c, *d); --d; }
+ }
+ }
+ for(; b < c;) {
+ SWAP(*b, *c);
+ for(; (++b < c) && ((x = ISAd[*b]) <= v);) {
+ if(x == v) { SWAP(*b, *a); ++a; }
+ }
+ for(; (b < --c) && ((x = ISAd[*c]) >= v);) {
+ if(x == v) { SWAP(*c, *d); --d; }
+ }
+ }
+
+ if(a <= d) {
+ c = b - 1;
+ if((s = a - first) > (t = b - a)) { s = t; }
+ for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
+ if((s = d - c) > (t = last - d - 1)) { s = t; }
+ for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
+ first += (b - a), last -= (d - c);
+ }
+ *pa = first, *pb = last;
+}
+
+static
+void
+tr_copy(int *ISA, const int *SA,
+ int *first, int *a, int *b, int *last,
+ int depth) {
+ /* sort suffixes of middle partition
+ by using sorted order of suffixes of left and right partition. */
+ int *c, *d, *e;
+ int s, v;
+
+ v = b - SA - 1;
+ for(c = first, d = a - 1; c <= d; ++c) {
+ if((0 <= (s = *c - depth)) && (ISA[s] == v)) {
+ *++d = s;
+ ISA[s] = d - SA;
+ }
+ }
+ for(c = last - 1, e = d + 1, d = b; e < d; --c) {
+ if((0 <= (s = *c - depth)) && (ISA[s] == v)) {
+ *--d = s;
+ ISA[s] = d - SA;
+ }
+ }
+}
+
+static
+void
+tr_partialcopy(int *ISA, const int *SA,
+ int *first, int *a, int *b, int *last,
+ int depth) {
+ int *c, *d, *e;
+ int s, v;
+ int rank, lastrank, newrank = -1;
+
+ v = b - SA - 1;
+ lastrank = -1;
+ for(c = first, d = a - 1; c <= d; ++c) {
+ if((0 <= (s = *c - depth)) && (ISA[s] == v)) {
+ *++d = s;
+ rank = ISA[s + depth];
+ if(lastrank != rank) { lastrank = rank; newrank = d - SA; }
+ ISA[s] = newrank;
+ }
+ }
+
+ lastrank = -1;
+ for(e = d; first <= e; --e) {
+ rank = ISA[*e];
+ if(lastrank != rank) { lastrank = rank; newrank = e - SA; }
+ if(newrank != rank) { ISA[*e] = newrank; }
+ }
+
+ lastrank = -1;
+ for(c = last - 1, e = d + 1, d = b; e < d; --c) {
+ if((0 <= (s = *c - depth)) && (ISA[s] == v)) {
+ *--d = s;
+ rank = ISA[s + depth];
+ if(lastrank != rank) { lastrank = rank; newrank = d - SA; }
+ ISA[s] = newrank;
+ }
+ }
+}
+
+static
+void
+tr_introsort(int *ISA, const int *ISAd,
+ int *SA, int *first, int *last,
+ trbudget_t *budget) {
+#define STACK_SIZE TR_STACKSIZE
+ struct { const int *a; int *b, *c; int d, e; }stack[STACK_SIZE];
+ int *a, *b, *c;
+ int t;
+ int v, x = 0;
+ int incr = ISAd - ISA;
+ int limit, next;
+ int ssize, trlink = -1;
+
+ for(ssize = 0, limit = tr_ilg(last - first);;) {
+
+ if(limit < 0) {
+ if(limit == -1) {
+ /* tandem repeat partition */
+ tr_partition(ISAd - incr, first, first, last, &a, &b, last - SA - 1);
+
+ /* update ranks */
+ if(a < last) {
+ for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; }
+ }
+ if(b < last) {
+ for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; }
+ }
+
+ /* push */
+ if(1 < (b - a)) {
+ STACK_PUSH5(NULL, a, b, 0, 0);
+ STACK_PUSH5(ISAd - incr, first, last, -2, trlink);
+ trlink = ssize - 2;
+ }
+ if((a - first) <= (last - b)) {
+ if(1 < (a - first)) {
+ STACK_PUSH5(ISAd, b, last, tr_ilg(last - b), trlink);
+ last = a, limit = tr_ilg(a - first);
+ } else if(1 < (last - b)) {
+ first = b, limit = tr_ilg(last - b);
+ } else {
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ } else {
+ if(1 < (last - b)) {
+ STACK_PUSH5(ISAd, first, a, tr_ilg(a - first), trlink);
+ first = b, limit = tr_ilg(last - b);
+ } else if(1 < (a - first)) {
+ last = a, limit = tr_ilg(a - first);
+ } else {
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ }
+ } else if(limit == -2) {
+ /* tandem repeat copy */
+ a = stack[--ssize].b, b = stack[ssize].c;
+ if(stack[ssize].d == 0) {
+ tr_copy(ISA, SA, first, a, b, last, ISAd - ISA);
+ } else {
+ if(0 <= trlink) { stack[trlink].d = -1; }
+ tr_partialcopy(ISA, SA, first, a, b, last, ISAd - ISA);
+ }
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ } else {
+ /* sorted partition */
+ if(0 <= *first) {
+ a = first;
+ do { ISA[*a] = a - SA; } while((++a < last) && (0 <= *a));
+ first = a;
+ }
+ if(first < last) {
+ a = first; do { *a = ~*a; } while(*++a < 0);
+ next = (ISA[*a] != ISAd[*a]) ? tr_ilg(a - first + 1) : -1;
+ if(++a < last) { for(b = first, v = a - SA - 1; b < a; ++b) { ISA[*b] = v; } }
+
+ /* push */
+ if(trbudget_check(budget, a - first)) {
+ if((a - first) <= (last - a)) {
+ STACK_PUSH5(ISAd, a, last, -3, trlink);
+ ISAd += incr, last = a, limit = next;
+ } else {
+ if(1 < (last - a)) {
+ STACK_PUSH5(ISAd + incr, first, a, next, trlink);
+ first = a, limit = -3;
+ } else {
+ ISAd += incr, last = a, limit = next;
+ }
+ }
+ } else {
+ if(0 <= trlink) { stack[trlink].d = -1; }
+ if(1 < (last - a)) {
+ first = a, limit = -3;
+ } else {
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ }
+ } else {
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ }
+ continue;
+ }
+
+ if((last - first) <= TR_INSERTIONSORT_THRESHOLD) {
+ tr_insertionsort(ISAd, first, last);
+ limit = -3;
+ continue;
+ }
+
+ if(limit-- == 0) {
+ tr_heapsort(ISAd, first, last - first);
+ for(a = last - 1; first < a; a = b) {
+ for(x = ISAd[*a], b = a - 1; (first <= b) && (ISAd[*b] == x); --b) { *b = ~*b; }
+ }
+ limit = -3;
+ continue;
+ }
+
+ /* choose pivot */
+ a = tr_pivot(ISAd, first, last);
+ SWAP(*first, *a);
+ v = ISAd[*first];
+
+ /* partition */
+ tr_partition(ISAd, first, first + 1, last, &a, &b, v);
+ if((last - first) != (b - a)) {
+ next = (ISA[*a] != v) ? tr_ilg(b - a) : -1;
+
+ /* update ranks */
+ for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; }
+ if(b < last) { for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; } }
+
+ /* push */
+ if((1 < (b - a)) && (trbudget_check(budget, b - a))) {
+ if((a - first) <= (last - b)) {
+ if((last - b) <= (b - a)) {
+ if(1 < (a - first)) {
+ STACK_PUSH5(ISAd + incr, a, b, next, trlink);
+ STACK_PUSH5(ISAd, b, last, limit, trlink);
+ last = a;
+ } else if(1 < (last - b)) {
+ STACK_PUSH5(ISAd + incr, a, b, next, trlink);
+ first = b;
+ } else {
+ ISAd += incr, first = a, last = b, limit = next;
+ }
+ } else if((a - first) <= (b - a)) {
+ if(1 < (a - first)) {
+ STACK_PUSH5(ISAd, b, last, limit, trlink);
+ STACK_PUSH5(ISAd + incr, a, b, next, trlink);
+ last = a;
+ } else {
+ STACK_PUSH5(ISAd, b, last, limit, trlink);
+ ISAd += incr, first = a, last = b, limit = next;
+ }
+ } else {
+ STACK_PUSH5(ISAd, b, last, limit, trlink);
+ STACK_PUSH5(ISAd, first, a, limit, trlink);
+ ISAd += incr, first = a, last = b, limit = next;
+ }
+ } else {
+ if((a - first) <= (b - a)) {
+ if(1 < (last - b)) {
+ STACK_PUSH5(ISAd + incr, a, b, next, trlink);
+ STACK_PUSH5(ISAd, first, a, limit, trlink);
+ first = b;
+ } else if(1 < (a - first)) {
+ STACK_PUSH5(ISAd + incr, a, b, next, trlink);
+ last = a;
+ } else {
+ ISAd += incr, first = a, last = b, limit = next;
+ }
+ } else if((last - b) <= (b - a)) {
+ if(1 < (last - b)) {
+ STACK_PUSH5(ISAd, first, a, limit, trlink);
+ STACK_PUSH5(ISAd + incr, a, b, next, trlink);
+ first = b;
+ } else {
+ STACK_PUSH5(ISAd, first, a, limit, trlink);
+ ISAd += incr, first = a, last = b, limit = next;
+ }
+ } else {
+ STACK_PUSH5(ISAd, first, a, limit, trlink);
+ STACK_PUSH5(ISAd, b, last, limit, trlink);
+ ISAd += incr, first = a, last = b, limit = next;
+ }
+ }
+ } else {
+ if((1 < (b - a)) && (0 <= trlink)) { stack[trlink].d = -1; }
+ if((a - first) <= (last - b)) {
+ if(1 < (a - first)) {
+ STACK_PUSH5(ISAd, b, last, limit, trlink);
+ last = a;
+ } else if(1 < (last - b)) {
+ first = b;
+ } else {
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ } else {
+ if(1 < (last - b)) {
+ STACK_PUSH5(ISAd, first, a, limit, trlink);
+ first = b;
+ } else if(1 < (a - first)) {
+ last = a;
+ } else {
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ }
+ }
+ } else {
+ if(trbudget_check(budget, last - first)) {
+ limit = tr_ilg(last - first), ISAd += incr;
+ } else {
+ if(0 <= trlink) { stack[trlink].d = -1; }
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ }
+ }
+#undef STACK_SIZE
+}
+
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Tandem repeat sort */
+static
+void
+trsort(int *ISA, int *SA, int n, int depth) {
+ int *ISAd;
+ int *first, *last;
+ trbudget_t budget;
+ int t, skip, unsorted;
+
+ trbudget_init(&budget, tr_ilg(n) * 2 / 3, n);
+/* trbudget_init(&budget, tr_ilg(n) * 3 / 4, n); */
+ for(ISAd = ISA + depth; -n < *SA; ISAd += ISAd - ISA) {
+ first = SA;
+ skip = 0;
+ unsorted = 0;
+ do {
+ if((t = *first) < 0) { first -= t; skip += t; }
+ else {
+ if(skip != 0) { *(first + skip) = skip; skip = 0; }
+ last = SA + ISA[t] + 1;
+ if(1 < (last - first)) {
+ budget.count = 0;
+ tr_introsort(ISA, ISAd, SA, first, last, &budget);
+ if(budget.count != 0) { unsorted += budget.count; }
+ else { skip = first - last; }
+ } else if((last - first) == 1) {
+ skip = -1;
+ }
+ first = last;
+ }
+ } while(first < (SA + n));
+ if(skip != 0) { *(first + skip) = skip; }
+ if(unsorted == 0) { break; }
+ }
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Sorts suffixes of type B*. */
+static
+int
+sort_typeBstar(const unsigned char *T, int *SA,
+ int *bucket_A, int *bucket_B,
+ int n, int openMP) {
+ int *PAb, *ISAb, *buf;
+#ifdef LIBBSC_OPENMP
+ int *curbuf;
+ int l;
+#endif
+ int i, j, k, t, m, bufsize;
+ int c0, c1;
+#ifdef LIBBSC_OPENMP
+ int d0, d1;
+#endif
+ (void)openMP;
+
+ /* Initialize bucket arrays. */
+ for(i = 0; i < BUCKET_A_SIZE; ++i) { bucket_A[i] = 0; }
+ for(i = 0; i < BUCKET_B_SIZE; ++i) { bucket_B[i] = 0; }
+
+ /* Count the number of occurrences of the first one or two characters of each
+ type A, B and B* suffix. Moreover, store the beginning position of all
+ type B* suffixes into the array SA. */
+ for(i = n - 1, m = n, c0 = T[n - 1]; 0 <= i;) {
+ /* type A suffix. */
+ do { ++BUCKET_A(c1 = c0); } while((0 <= --i) && ((c0 = T[i]) >= c1));
+ if(0 <= i) {
+ /* type B* suffix. */
+ ++BUCKET_BSTAR(c0, c1);
+ SA[--m] = i;
+ /* type B suffix. */
+ for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) {
+ ++BUCKET_B(c0, c1);
+ }
+ }
+ }
+ m = n - m;
+/*
+note:
+ A type B* suffix is lexicographically smaller than a type B suffix that
+ begins with the same first two characters.
+*/
+
+ /* Calculate the index of start/end point of each bucket. */
+ for(c0 = 0, i = 0, j = 0; c0 < ALPHABET_SIZE; ++c0) {
+ t = i + BUCKET_A(c0);
+ BUCKET_A(c0) = i + j; /* start point */
+ i = t + BUCKET_B(c0, c0);
+ for(c1 = c0 + 1; c1 < ALPHABET_SIZE; ++c1) {
+ j += BUCKET_BSTAR(c0, c1);
+ BUCKET_BSTAR(c0, c1) = j; /* end point */
+ i += BUCKET_B(c0, c1);
+ }
+ }
+
+ if(0 < m) {
+ /* Sort the type B* suffixes by their first two characters. */
+ PAb = SA + n - m; ISAb = SA + m;
+ for(i = m - 2; 0 <= i; --i) {
+ t = PAb[i], c0 = T[t], c1 = T[t + 1];
+ SA[--BUCKET_BSTAR(c0, c1)] = i;
+ }
+ t = PAb[m - 1], c0 = T[t], c1 = T[t + 1];
+ SA[--BUCKET_BSTAR(c0, c1)] = m - 1;
+
+ /* Sort the type B* substrings using sssort. */
+#ifdef LIBBSC_OPENMP
+ if (openMP)
+ {
+ buf = SA + m;
+ c0 = ALPHABET_SIZE - 2, c1 = ALPHABET_SIZE - 1, j = m;
+#pragma omp parallel default(shared) private(bufsize, curbuf, k, l, d0, d1)
+ {
+ bufsize = (n - (2 * m)) / omp_get_num_threads();
+ curbuf = buf + omp_get_thread_num() * bufsize;
+ k = 0;
+ for(;;) {
+ #pragma omp critical(sssort_lock)
+ {
+ if(0 < (l = j)) {
+ d0 = c0, d1 = c1;
+ do {
+ k = BUCKET_BSTAR(d0, d1);
+ if(--d1 <= d0) {
+ d1 = ALPHABET_SIZE - 1;
+ if(--d0 < 0) { break; }
+ }
+ } while(((l - k) <= 1) && (0 < (l = k)));
+ c0 = d0, c1 = d1, j = k;
+ }
+ }
+ if(l == 0) { break; }
+ sssort(T, PAb, SA + k, SA + l,
+ curbuf, bufsize, 2, n, *(SA + k) == (m - 1));
+ }
+ }
+ }
+ else
+ {
+ buf = SA + m, bufsize = n - (2 * m);
+ for(c0 = ALPHABET_SIZE - 2, j = m; 0 < j; --c0) {
+ for(c1 = ALPHABET_SIZE - 1; c0 < c1; j = i, --c1) {
+ i = BUCKET_BSTAR(c0, c1);
+ if(1 < (j - i)) {
+ sssort(T, PAb, SA + i, SA + j,
+ buf, bufsize, 2, n, *(SA + i) == (m - 1));
+ }
+ }
+ }
+ }
+#else
+ buf = SA + m, bufsize = n - (2 * m);
+ for(c0 = ALPHABET_SIZE - 2, j = m; 0 < j; --c0) {
+ for(c1 = ALPHABET_SIZE - 1; c0 < c1; j = i, --c1) {
+ i = BUCKET_BSTAR(c0, c1);
+ if(1 < (j - i)) {
+ sssort(T, PAb, SA + i, SA + j,
+ buf, bufsize, 2, n, *(SA + i) == (m - 1));
+ }
+ }
+ }
+#endif
+
+ /* Compute ranks of type B* substrings. */
+ for(i = m - 1; 0 <= i; --i) {
+ if(0 <= SA[i]) {
+ j = i;
+ do { ISAb[SA[i]] = i; } while((0 <= --i) && (0 <= SA[i]));
+ SA[i + 1] = i - j;
+ if(i <= 0) { break; }
+ }
+ j = i;
+ do { ISAb[SA[i] = ~SA[i]] = j; } while(SA[--i] < 0);
+ ISAb[SA[i]] = j;
+ }
+
+ /* Construct the inverse suffix array of type B* suffixes using trsort. */
+ trsort(ISAb, SA, m, 1);
+
+ /* Set the sorted order of type B* suffixes. */
+ for(i = n - 1, j = m, c0 = T[n - 1]; 0 <= i;) {
+ for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) >= c1); --i, c1 = c0) { }
+ if(0 <= i) {
+ t = i;
+ for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) { }
+ SA[ISAb[--j]] = ((t == 0) || (1 < (t - i))) ? t : ~t;
+ }
+ }
+
+ /* Calculate the index of start/end point of each bucket. */
+ BUCKET_B(ALPHABET_SIZE - 1, ALPHABET_SIZE - 1) = n; /* end point */
+ for(c0 = ALPHABET_SIZE - 2, k = m - 1; 0 <= c0; --c0) {
+ i = BUCKET_A(c0 + 1) - 1;
+ for(c1 = ALPHABET_SIZE - 1; c0 < c1; --c1) {
+ t = i - BUCKET_B(c0, c1);
+ BUCKET_B(c0, c1) = i; /* end point */
+
+ /* Move all type B* suffixes to the correct position. */
+ for(i = t, j = BUCKET_BSTAR(c0, c1);
+ j <= k;
+ --i, --k) { SA[i] = SA[k]; }
+ }
+ BUCKET_BSTAR(c0, c0 + 1) = i - BUCKET_B(c0, c0) + 1; /* start point */
+ BUCKET_B(c0, c0) = i; /* end point */
+ }
+ }
+
+ return m;
+}
+
+/* Constructs the suffix array by using the sorted order of type B* suffixes. */
+static
+void
+construct_SA(const unsigned char *T, int *SA,
+ int *bucket_A, int *bucket_B,
+ int n, int m) {
+ int *i, *j, *k;
+ int s;
+ int c0, c1, c2;
+
+ if(0 < m) {
+ /* Construct the sorted order of type B suffixes by using
+ the sorted order of type B* suffixes. */
+ for(c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) {
+ /* Scan the suffix array from right to left. */
+ for(i = SA + BUCKET_BSTAR(c1, c1 + 1),
+ j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1;
+ i <= j;
+ --j) {
+ if(0 < (s = *j)) {
+ assert(T[s] == c1);
+ assert(((s + 1) < n) && (T[s] <= T[s + 1]));
+ assert(T[s - 1] <= T[s]);
+ *j = ~s;
+ c0 = T[--s];
+ if((0 < s) && (T[s - 1] > c0)) { s = ~s; }
+ if(c0 != c2) {
+ if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; }
+ k = SA + BUCKET_B(c2 = c0, c1);
+ }
+ assert(k < j); assert(k != NULL);
+ *k-- = s;
+ } else {
+ assert(((s == 0) && (T[s] == c1)) || (s < 0));
+ *j = ~s;
+ }
+ }
+ }
+ }
+
+ /* Construct the suffix array by using
+ the sorted order of type B suffixes. */
+ k = SA + BUCKET_A(c2 = T[n - 1]);
+ *k++ = (T[n - 2] < c2) ? ~(n - 1) : (n - 1);
+ /* Scan the suffix array from left to right. */
+ for(i = SA, j = SA + n; i < j; ++i) {
+ if(0 < (s = *i)) {
+ assert(T[s - 1] >= T[s]);
+ c0 = T[--s];
+ if((s == 0) || (T[s - 1] < c0)) { s = ~s; }
+ if(c0 != c2) {
+ BUCKET_A(c2) = k - SA;
+ k = SA + BUCKET_A(c2 = c0);
+ }
+ assert(i < k);
+ *k++ = s;
+ } else {
+ assert(s < 0);
+ *i = ~s;
+ }
+ }
+}
+
+/* Constructs the burrows-wheeler transformed string directly
+ by using the sorted order of type B* suffixes. */
+static
+int
+construct_BWT(const unsigned char *T, int *SA,
+ int *bucket_A, int *bucket_B,
+ int n, int m) {
+ int *i, *j, *k, *orig;
+ int s;
+ int c0, c1, c2;
+
+ if(0 < m) {
+ /* Construct the sorted order of type B suffixes by using
+ the sorted order of type B* suffixes. */
+ for(c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) {
+ /* Scan the suffix array from right to left. */
+ for(i = SA + BUCKET_BSTAR(c1, c1 + 1),
+ j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1;
+ i <= j;
+ --j) {
+ if(0 < (s = *j)) {
+ assert(T[s] == c1);
+ assert(((s + 1) < n) && (T[s] <= T[s + 1]));
+ assert(T[s - 1] <= T[s]);
+ c0 = T[--s];
+ *j = ~((int)c0);
+ if((0 < s) && (T[s - 1] > c0)) { s = ~s; }
+ if(c0 != c2) {
+ if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; }
+ k = SA + BUCKET_B(c2 = c0, c1);
+ }
+ assert(k < j); assert(k != NULL);
+ *k-- = s;
+ } else if(s != 0) {
+ *j = ~s;
+#ifndef NDEBUG
+ } else {
+ assert(T[s] == c1);
+#endif
+ }
+ }
+ }
+ }
+
+ /* Construct the BWTed string by using
+ the sorted order of type B suffixes. */
+ k = SA + BUCKET_A(c2 = T[n - 1]);
+ *k++ = (T[n - 2] < c2) ? ~((int)T[n - 2]) : (n - 1);
+ /* Scan the suffix array from left to right. */
+ for(i = SA, j = SA + n, orig = SA; i < j; ++i) {
+ if(0 < (s = *i)) {
+ assert(T[s - 1] >= T[s]);
+ c0 = T[--s];
+ *i = c0;
+ if((0 < s) && (T[s - 1] < c0)) { s = ~((int)T[s - 1]); }
+ if(c0 != c2) {
+ BUCKET_A(c2) = k - SA;
+ k = SA + BUCKET_A(c2 = c0);
+ }
+ assert(i < k);
+ *k++ = s;
+ } else if(s != 0) {
+ *i = ~s;
+ } else {
+ orig = i;
+ }
+ }
+
+ return orig - SA;
+}
+
+/* Constructs the burrows-wheeler transformed string directly
+ by using the sorted order of type B* suffixes. */
+static
+int
+construct_BWT_indexes(const unsigned char *T, int *SA,
+ int *bucket_A, int *bucket_B,
+ int n, int m,
+ unsigned char * num_indexes, int * indexes) {
+ int *i, *j, *k, *orig;
+ int s;
+ int c0, c1, c2;
+
+ int mod = n / 8;
+ {
+ mod |= mod >> 1; mod |= mod >> 2;
+ mod |= mod >> 4; mod |= mod >> 8;
+ mod |= mod >> 16; mod >>= 1;
+
+ *num_indexes = (unsigned char)((n - 1) / (mod + 1));
+ }
+
+ if(0 < m) {
+ /* Construct the sorted order of type B suffixes by using
+ the sorted order of type B* suffixes. */
+ for(c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) {
+ /* Scan the suffix array from right to left. */
+ for(i = SA + BUCKET_BSTAR(c1, c1 + 1),
+ j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1;
+ i <= j;
+ --j) {
+ if(0 < (s = *j)) {
+ assert(T[s] == c1);
+ assert(((s + 1) < n) && (T[s] <= T[s + 1]));
+ assert(T[s - 1] <= T[s]);
+
+ if ((s & mod) == 0) indexes[s / (mod + 1) - 1] = j - SA;
+
+ c0 = T[--s];
+ *j = ~((int)c0);
+ if((0 < s) && (T[s - 1] > c0)) { s = ~s; }
+ if(c0 != c2) {
+ if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; }
+ k = SA + BUCKET_B(c2 = c0, c1);
+ }
+ assert(k < j); assert(k != NULL);
+ *k-- = s;
+ } else if(s != 0) {
+ *j = ~s;
+#ifndef NDEBUG
+ } else {
+ assert(T[s] == c1);
+#endif
+ }
+ }
+ }
+ }
+
+ /* Construct the BWTed string by using
+ the sorted order of type B suffixes. */
+ k = SA + BUCKET_A(c2 = T[n - 1]);
+ if (T[n - 2] < c2) {
+ if (((n - 1) & mod) == 0) indexes[(n - 1) / (mod + 1) - 1] = k - SA;
+ *k++ = ~((int)T[n - 2]);
+ }
+ else {
+ *k++ = n - 1;
+ }
+
+ /* Scan the suffix array from left to right. */
+ for(i = SA, j = SA + n, orig = SA; i < j; ++i) {
+ if(0 < (s = *i)) {
+ assert(T[s - 1] >= T[s]);
+
+ if ((s & mod) == 0) indexes[s / (mod + 1) - 1] = i - SA;
+
+ c0 = T[--s];
+ *i = c0;
+ if(c0 != c2) {
+ BUCKET_A(c2) = k - SA;
+ k = SA + BUCKET_A(c2 = c0);
+ }
+ assert(i < k);
+ if((0 < s) && (T[s - 1] < c0)) {
+ if ((s & mod) == 0) indexes[s / (mod + 1) - 1] = k - SA;
+ *k++ = ~((int)T[s - 1]);
+ } else
+ *k++ = s;
+ } else if(s != 0) {
+ *i = ~s;
+ } else {
+ orig = i;
+ }
+ }
+
+ return orig - SA;
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+/*- Function -*/
+
+int
+divsufsort(const unsigned char *T, int *SA, int n, int openMP) {
+ int *bucket_A, *bucket_B;
+ int m;
+ int err = 0;
+
+ /* Check arguments. */
+ if((T == NULL) || (SA == NULL) || (n < 0)) { return -1; }
+ else if(n == 0) { return 0; }
+ else if(n == 1) { SA[0] = 0; return 0; }
+ else if(n == 2) { m = (T[0] < T[1]); SA[m ^ 1] = 0, SA[m] = 1; return 0; }
+
+ bucket_A = (int *)malloc(BUCKET_A_SIZE * sizeof(int));
+ bucket_B = (int *)malloc(BUCKET_B_SIZE * sizeof(int));
+
+ /* Suffixsort. */
+ if((bucket_A != NULL) && (bucket_B != NULL)) {
+ m = sort_typeBstar(T, SA, bucket_A, bucket_B, n, openMP);
+ construct_SA(T, SA, bucket_A, bucket_B, n, m);
+ } else {
+ err = -2;
+ }
+
+ free(bucket_B);
+ free(bucket_A);
+
+ return err;
+}
+
+int
+divbwt(const unsigned char *T, unsigned char *U, int *A, int n, unsigned char * num_indexes, int * indexes, int openMP) {
+ int *B;
+ int *bucket_A, *bucket_B;
+ int m, pidx, i;
+
+ /* Check arguments. */
+ if((T == NULL) || (U == NULL) || (n < 0)) { return -1; }
+ else if(n <= 1) { if(n == 1) { U[0] = T[0]; } return n; }
+
+ if((B = A) == NULL) { B = (int *)malloc((size_t)(n + 1) * sizeof(int)); }
+ bucket_A = (int *)malloc(BUCKET_A_SIZE * sizeof(int));
+ bucket_B = (int *)malloc(BUCKET_B_SIZE * sizeof(int));
+
+ /* Burrows-Wheeler Transform. */
+ if((B != NULL) && (bucket_A != NULL) && (bucket_B != NULL)) {
+ m = sort_typeBstar(T, B, bucket_A, bucket_B, n, openMP);
+
+ if (num_indexes == NULL || indexes == NULL) {
+ pidx = construct_BWT(T, B, bucket_A, bucket_B, n, m);
+ } else {
+ pidx = construct_BWT_indexes(T, B, bucket_A, bucket_B, n, m, num_indexes, indexes);
+ }
+
+ /* Copy to output string. */
+ U[0] = T[n - 1];
+ for(i = 0; i < pidx; ++i) { U[i + 1] = (unsigned char)B[i]; }
+ for(i += 1; i < n; ++i) { U[i] = (unsigned char)B[i]; }
+ pidx += 1;
+ } else {
+ pidx = -2;
+ }
+
+ free(bucket_B);
+ free(bucket_A);
+ if(A == NULL) { free(B); }
+
+ return pidx;
+}
diff --git a/zstd/dictBuilder/divsufsort.h b/zstd/dictBuilder/divsufsort.h
new file mode 100644
index 00000000..5440994a
--- /dev/null
+++ b/zstd/dictBuilder/divsufsort.h
@@ -0,0 +1,67 @@
+/*
+ * divsufsort.h for libdivsufsort-lite
+ * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved.
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+#ifndef _DIVSUFSORT_H
+#define _DIVSUFSORT_H 1
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+
+/*- Prototypes -*/
+
+/**
+ * Constructs the suffix array of a given string.
+ * @param T [0..n-1] The input string.
+ * @param SA [0..n-1] The output array of suffixes.
+ * @param n The length of the given string.
+ * @param openMP enables OpenMP optimization.
+ * @return 0 if no error occurred, -1 or -2 otherwise.
+ */
+int
+divsufsort(const unsigned char *T, int *SA, int n, int openMP);
+
+/**
+ * Constructs the burrows-wheeler transformed string of a given string.
+ * @param T [0..n-1] The input string.
+ * @param U [0..n-1] The output string. (can be T)
+ * @param A [0..n-1] The temporary array. (can be NULL)
+ * @param n The length of the given string.
+ * @param num_indexes The length of secondary indexes array. (can be NULL)
+ * @param indexes The secondary indexes array. (can be NULL)
+ * @param openMP enables OpenMP optimization.
+ * @return The primary index if no error occurred, -1 or -2 otherwise.
+ */
+int
+divbwt(const unsigned char *T, unsigned char *U, int *A, int n, unsigned char * num_indexes, int * indexes, int openMP);
+
+
+#ifdef __cplusplus
+} /* extern "C" */
+#endif /* __cplusplus */
+
+#endif /* _DIVSUFSORT_H */
diff --git a/zstd/dictBuilder/fastcover.c b/zstd/dictBuilder/fastcover.c
new file mode 100644
index 00000000..ed789f92
--- /dev/null
+++ b/zstd/dictBuilder/fastcover.c
@@ -0,0 +1,759 @@
+/*
+ * Copyright (c) Facebook, Inc.
+ * All rights reserved.
+ *
+ * This source code is licensed under both the BSD-style license (found in the
+ * LICENSE file in the root directory of this source tree) and the GPLv2 (found
+ * in the COPYING file in the root directory of this source tree).
+ * You may select, at your option, one of the above-listed licenses.
+ */
+
+/*-*************************************
+* Dependencies
+***************************************/
+#include <stdio.h> /* fprintf */
+#include <stdlib.h> /* malloc, free, qsort */
+#include <string.h> /* memset */
+#include <time.h> /* clock */
+
+#ifndef ZDICT_STATIC_LINKING_ONLY
+# define ZDICT_STATIC_LINKING_ONLY
+#endif
+
+#include "../common/mem.h" /* read */
+#include "../common/pool.h"
+#include "../common/threading.h"
+#include "../common/zstd_internal.h" /* includes zstd.h */
+#include "../compress/zstd_compress_internal.h" /* ZSTD_hash*() */
+#include "../zdict.h"
+#include "cover.h"
+
+
+/*-*************************************
+* Constants
+***************************************/
+#define FASTCOVER_MAX_SAMPLES_SIZE (sizeof(size_t) == 8 ? ((unsigned)-1) : ((unsigned)1 GB))
+#define FASTCOVER_MAX_F 31
+#define FASTCOVER_MAX_ACCEL 10
+#define FASTCOVER_DEFAULT_SPLITPOINT 0.75
+#define DEFAULT_F 20
+#define DEFAULT_ACCEL 1
+
+
+/*-*************************************
+* Console display
+***************************************/
+#ifndef LOCALDISPLAYLEVEL
+static int g_displayLevel = 2;
+#endif
+#undef DISPLAY
+#define DISPLAY(...) \
+ { \
+ fprintf(stderr, __VA_ARGS__); \
+ fflush(stderr); \
+ }
+#undef LOCALDISPLAYLEVEL
+#define LOCALDISPLAYLEVEL(displayLevel, l, ...) \
+ if (displayLevel >= l) { \
+ DISPLAY(__VA_ARGS__); \
+ } /* 0 : no display; 1: errors; 2: default; 3: details; 4: debug */
+#undef DISPLAYLEVEL
+#define DISPLAYLEVEL(l, ...) LOCALDISPLAYLEVEL(g_displayLevel, l, __VA_ARGS__)
+
+#ifndef LOCALDISPLAYUPDATE
+static const clock_t g_refreshRate = CLOCKS_PER_SEC * 15 / 100;
+static clock_t g_time = 0;
+#endif
+#undef LOCALDISPLAYUPDATE
+#define LOCALDISPLAYUPDATE(displayLevel, l, ...) \
+ if (displayLevel >= l) { \
+ if ((clock() - g_time > g_refreshRate) || (displayLevel >= 4)) { \
+ g_time = clock(); \
+ DISPLAY(__VA_ARGS__); \
+ } \
+ }
+#undef DISPLAYUPDATE
+#define DISPLAYUPDATE(l, ...) LOCALDISPLAYUPDATE(g_displayLevel, l, __VA_ARGS__)
+
+
+/*-*************************************
+* Hash Functions
+***************************************/
+/**
+ * Hash the d-byte value pointed to by p and mod 2^f into the frequency vector
+ */
+static size_t FASTCOVER_hashPtrToIndex(const void* p, U32 f, unsigned d) {
+ if (d == 6) {
+ return ZSTD_hash6Ptr(p, f);
+ }
+ return ZSTD_hash8Ptr(p, f);
+}
+
+
+/*-*************************************
+* Acceleration
+***************************************/
+typedef struct {
+ unsigned finalize; /* Percentage of training samples used for ZDICT_finalizeDictionary */
+ unsigned skip; /* Number of dmer skipped between each dmer counted in computeFrequency */
+} FASTCOVER_accel_t;
+
+
+static const FASTCOVER_accel_t FASTCOVER_defaultAccelParameters[FASTCOVER_MAX_ACCEL+1] = {
+ { 100, 0 }, /* accel = 0, should not happen because accel = 0 defaults to accel = 1 */
+ { 100, 0 }, /* accel = 1 */
+ { 50, 1 }, /* accel = 2 */
+ { 34, 2 }, /* accel = 3 */
+ { 25, 3 }, /* accel = 4 */
+ { 20, 4 }, /* accel = 5 */
+ { 17, 5 }, /* accel = 6 */
+ { 14, 6 }, /* accel = 7 */
+ { 13, 7 }, /* accel = 8 */
+ { 11, 8 }, /* accel = 9 */
+ { 10, 9 }, /* accel = 10 */
+};
+
+
+/*-*************************************
+* Context
+***************************************/
+typedef struct {
+ const BYTE *samples;
+ size_t *offsets;
+ const size_t *samplesSizes;
+ size_t nbSamples;
+ size_t nbTrainSamples;
+ size_t nbTestSamples;
+ size_t nbDmers;
+ U32 *freqs;
+ unsigned d;
+ unsigned f;
+ FASTCOVER_accel_t accelParams;
+} FASTCOVER_ctx_t;
+
+
+/*-*************************************
+* Helper functions
+***************************************/
+/**
+ * Selects the best segment in an epoch.
+ * Segments of are scored according to the function:
+ *
+ * Let F(d) be the frequency of all dmers with hash value d.
+ * Let S_i be hash value of the dmer at position i of segment S which has length k.
+ *
+ * Score(S) = F(S_1) + F(S_2) + ... + F(S_{k-d+1})
+ *
+ * Once the dmer with hash value d is in the dictionary we set F(d) = 0.
+ */
+static COVER_segment_t FASTCOVER_selectSegment(const FASTCOVER_ctx_t *ctx,
+ U32 *freqs, U32 begin, U32 end,
+ ZDICT_cover_params_t parameters,
+ U16* segmentFreqs) {
+ /* Constants */
+ const U32 k = parameters.k;
+ const U32 d = parameters.d;
+ const U32 f = ctx->f;
+ const U32 dmersInK = k - d + 1;
+
+ /* Try each segment (activeSegment) and save the best (bestSegment) */
+ COVER_segment_t bestSegment = {0, 0, 0};
+ COVER_segment_t activeSegment;
+
+ /* Reset the activeDmers in the segment */
+ /* The activeSegment starts at the beginning of the epoch. */
+ activeSegment.begin = begin;
+ activeSegment.end = begin;
+ activeSegment.score = 0;
+
+ /* Slide the activeSegment through the whole epoch.
+ * Save the best segment in bestSegment.
+ */
+ while (activeSegment.end < end) {
+ /* Get hash value of current dmer */
+ const size_t idx = FASTCOVER_hashPtrToIndex(ctx->samples + activeSegment.end, f, d);
+
+ /* Add frequency of this index to score if this is the first occurrence of index in active segment */
+ if (segmentFreqs[idx] == 0) {
+ activeSegment.score += freqs[idx];
+ }
+ /* Increment end of segment and segmentFreqs*/
+ activeSegment.end += 1;
+ segmentFreqs[idx] += 1;
+ /* If the window is now too large, drop the first position */
+ if (activeSegment.end - activeSegment.begin == dmersInK + 1) {
+ /* Get hash value of the dmer to be eliminated from active segment */
+ const size_t delIndex = FASTCOVER_hashPtrToIndex(ctx->samples + activeSegment.begin, f, d);
+ segmentFreqs[delIndex] -= 1;
+ /* Subtract frequency of this index from score if this is the last occurrence of this index in active segment */
+ if (segmentFreqs[delIndex] == 0) {
+ activeSegment.score -= freqs[delIndex];
+ }
+ /* Increment start of segment */
+ activeSegment.begin += 1;
+ }
+
+ /* If this segment is the best so far save it */
+ if (activeSegment.score > bestSegment.score) {
+ bestSegment = activeSegment;
+ }
+ }
+
+ /* Zero out rest of segmentFreqs array */
+ while (activeSegment.begin < end) {
+ const size_t delIndex = FASTCOVER_hashPtrToIndex(ctx->samples + activeSegment.begin, f, d);
+ segmentFreqs[delIndex] -= 1;
+ activeSegment.begin += 1;
+ }
+
+ {
+ /* Zero the frequency of hash value of each dmer covered by the chosen segment. */
+ U32 pos;
+ for (pos = bestSegment.begin; pos != bestSegment.end; ++pos) {
+ const size_t i = FASTCOVER_hashPtrToIndex(ctx->samples + pos, f, d);
+ freqs[i] = 0;
+ }
+ }
+
+ return bestSegment;
+}
+
+
+static int FASTCOVER_checkParameters(ZDICT_cover_params_t parameters,
+ size_t maxDictSize, unsigned f,
+ unsigned accel) {
+ /* k, d, and f are required parameters */
+ if (parameters.d == 0 || parameters.k == 0) {
+ return 0;
+ }
+ /* d has to be 6 or 8 */
+ if (parameters.d != 6 && parameters.d != 8) {
+ return 0;
+ }
+ /* k <= maxDictSize */
+ if (parameters.k > maxDictSize) {
+ return 0;
+ }
+ /* d <= k */
+ if (parameters.d > parameters.k) {
+ return 0;
+ }
+ /* 0 < f <= FASTCOVER_MAX_F*/
+ if (f > FASTCOVER_MAX_F || f == 0) {
+ return 0;
+ }
+ /* 0 < splitPoint <= 1 */
+ if (parameters.splitPoint <= 0 || parameters.splitPoint > 1) {
+ return 0;
+ }
+ /* 0 < accel <= 10 */
+ if (accel > 10 || accel == 0) {
+ return 0;
+ }
+ return 1;
+}
+
+
+/**
+ * Clean up a context initialized with `FASTCOVER_ctx_init()`.
+ */
+static void
+FASTCOVER_ctx_destroy(FASTCOVER_ctx_t* ctx)
+{
+ if (!ctx) return;
+
+ free(ctx->freqs);
+ ctx->freqs = NULL;
+
+ free(ctx->offsets);
+ ctx->offsets = NULL;
+}
+
+
+/**
+ * Calculate for frequency of hash value of each dmer in ctx->samples
+ */
+static void
+FASTCOVER_computeFrequency(U32* freqs, const FASTCOVER_ctx_t* ctx)
+{
+ const unsigned f = ctx->f;
+ const unsigned d = ctx->d;
+ const unsigned skip = ctx->accelParams.skip;
+ const unsigned readLength = MAX(d, 8);
+ size_t i;
+ assert(ctx->nbTrainSamples >= 5);
+ assert(ctx->nbTrainSamples <= ctx->nbSamples);
+ for (i = 0; i < ctx->nbTrainSamples; i++) {
+ size_t start = ctx->offsets[i]; /* start of current dmer */
+ size_t const currSampleEnd = ctx->offsets[i+1];
+ while (start + readLength <= currSampleEnd) {
+ const size_t dmerIndex = FASTCOVER_hashPtrToIndex(ctx->samples + start, f, d);
+ freqs[dmerIndex]++;
+ start = start + skip + 1;
+ }
+ }
+}
+
+
+/**
+ * Prepare a context for dictionary building.
+ * The context is only dependent on the parameter `d` and can used multiple
+ * times.
+ * Returns 0 on success or error code on error.
+ * The context must be destroyed with `FASTCOVER_ctx_destroy()`.
+ */
+static size_t
+FASTCOVER_ctx_init(FASTCOVER_ctx_t* ctx,
+ const void* samplesBuffer,
+ const size_t* samplesSizes, unsigned nbSamples,
+ unsigned d, double splitPoint, unsigned f,
+ FASTCOVER_accel_t accelParams)
+{
+ const BYTE* const samples = (const BYTE*)samplesBuffer;
+ const size_t totalSamplesSize = COVER_sum(samplesSizes, nbSamples);
+ /* Split samples into testing and training sets */
+ const unsigned nbTrainSamples = splitPoint < 1.0 ? (unsigned)((double)nbSamples * splitPoint) : nbSamples;
+ const unsigned nbTestSamples = splitPoint < 1.0 ? nbSamples - nbTrainSamples : nbSamples;
+ const size_t trainingSamplesSize = splitPoint < 1.0 ? COVER_sum(samplesSizes, nbTrainSamples) : totalSamplesSize;
+ const size_t testSamplesSize = splitPoint < 1.0 ? COVER_sum(samplesSizes + nbTrainSamples, nbTestSamples) : totalSamplesSize;
+
+ /* Checks */
+ if (totalSamplesSize < MAX(d, sizeof(U64)) ||
+ totalSamplesSize >= (size_t)FASTCOVER_MAX_SAMPLES_SIZE) {
+ DISPLAYLEVEL(1, "Total samples size is too large (%u MB), maximum size is %u MB\n",
+ (unsigned)(totalSamplesSize >> 20), (FASTCOVER_MAX_SAMPLES_SIZE >> 20));
+ return ERROR(srcSize_wrong);
+ }
+
+ /* Check if there are at least 5 training samples */
+ if (nbTrainSamples < 5) {
+ DISPLAYLEVEL(1, "Total number of training samples is %u and is invalid\n", nbTrainSamples);
+ return ERROR(srcSize_wrong);
+ }
+
+ /* Check if there's testing sample */
+ if (nbTestSamples < 1) {
+ DISPLAYLEVEL(1, "Total number of testing samples is %u and is invalid.\n", nbTestSamples);
+ return ERROR(srcSize_wrong);
+ }
+
+ /* Zero the context */
+ memset(ctx, 0, sizeof(*ctx));
+ DISPLAYLEVEL(2, "Training on %u samples of total size %u\n", nbTrainSamples,
+ (unsigned)trainingSamplesSize);
+ DISPLAYLEVEL(2, "Testing on %u samples of total size %u\n", nbTestSamples,
+ (unsigned)testSamplesSize);
+
+ ctx->samples = samples;
+ ctx->samplesSizes = samplesSizes;
+ ctx->nbSamples = nbSamples;
+ ctx->nbTrainSamples = nbTrainSamples;
+ ctx->nbTestSamples = nbTestSamples;
+ ctx->nbDmers = trainingSamplesSize - MAX(d, sizeof(U64)) + 1;
+ ctx->d = d;
+ ctx->f = f;
+ ctx->accelParams = accelParams;
+
+ /* The offsets of each file */
+ ctx->offsets = (size_t*)calloc((nbSamples + 1), sizeof(size_t));
+ if (ctx->offsets == NULL) {
+ DISPLAYLEVEL(1, "Failed to allocate scratch buffers \n");
+ FASTCOVER_ctx_destroy(ctx);
+ return ERROR(memory_allocation);
+ }
+
+ /* Fill offsets from the samplesSizes */
+ { U32 i;
+ ctx->offsets[0] = 0;
+ assert(nbSamples >= 5);
+ for (i = 1; i <= nbSamples; ++i) {
+ ctx->offsets[i] = ctx->offsets[i - 1] + samplesSizes[i - 1];
+ }
+ }
+
+ /* Initialize frequency array of size 2^f */
+ ctx->freqs = (U32*)calloc(((U64)1 << f), sizeof(U32));
+ if (ctx->freqs == NULL) {
+ DISPLAYLEVEL(1, "Failed to allocate frequency table \n");
+ FASTCOVER_ctx_destroy(ctx);
+ return ERROR(memory_allocation);
+ }
+
+ DISPLAYLEVEL(2, "Computing frequencies\n");
+ FASTCOVER_computeFrequency(ctx->freqs, ctx);
+
+ return 0;
+}
+
+
+/**
+ * Given the prepared context build the dictionary.
+ */
+static size_t
+FASTCOVER_buildDictionary(const FASTCOVER_ctx_t* ctx,
+ U32* freqs,
+ void* dictBuffer, size_t dictBufferCapacity,
+ ZDICT_cover_params_t parameters,
+ U16* segmentFreqs)
+{
+ BYTE *const dict = (BYTE *)dictBuffer;
+ size_t tail = dictBufferCapacity;
+ /* Divide the data into epochs. We will select one segment from each epoch. */
+ const COVER_epoch_info_t epochs = COVER_computeEpochs(
+ (U32)dictBufferCapacity, (U32)ctx->nbDmers, parameters.k, 1);
+ const size_t maxZeroScoreRun = 10;
+ size_t zeroScoreRun = 0;
+ size_t epoch;
+ DISPLAYLEVEL(2, "Breaking content into %u epochs of size %u\n",
+ (U32)epochs.num, (U32)epochs.size);
+ /* Loop through the epochs until there are no more segments or the dictionary
+ * is full.
+ */
+ for (epoch = 0; tail > 0; epoch = (epoch + 1) % epochs.num) {
+ const U32 epochBegin = (U32)(epoch * epochs.size);
+ const U32 epochEnd = epochBegin + epochs.size;
+ size_t segmentSize;
+ /* Select a segment */
+ COVER_segment_t segment = FASTCOVER_selectSegment(
+ ctx, freqs, epochBegin, epochEnd, parameters, segmentFreqs);
+
+ /* If the segment covers no dmers, then we are out of content.
+ * There may be new content in other epochs, for continue for some time.
+ */
+ if (segment.score == 0) {
+ if (++zeroScoreRun >= maxZeroScoreRun) {
+ break;
+ }
+ continue;
+ }
+ zeroScoreRun = 0;
+
+ /* Trim the segment if necessary and if it is too small then we are done */
+ segmentSize = MIN(segment.end - segment.begin + parameters.d - 1, tail);
+ if (segmentSize < parameters.d) {
+ break;
+ }
+
+ /* We fill the dictionary from the back to allow the best segments to be
+ * referenced with the smallest offsets.
+ */
+ tail -= segmentSize;
+ memcpy(dict + tail, ctx->samples + segment.begin, segmentSize);
+ DISPLAYUPDATE(
+ 2, "\r%u%% ",
+ (unsigned)(((dictBufferCapacity - tail) * 100) / dictBufferCapacity));
+ }
+ DISPLAYLEVEL(2, "\r%79s\r", "");
+ return tail;
+}
+
+/**
+ * Parameters for FASTCOVER_tryParameters().
+ */
+typedef struct FASTCOVER_tryParameters_data_s {
+ const FASTCOVER_ctx_t* ctx;
+ COVER_best_t* best;
+ size_t dictBufferCapacity;
+ ZDICT_cover_params_t parameters;
+} FASTCOVER_tryParameters_data_t;
+
+
+/**
+ * Tries a set of parameters and updates the COVER_best_t with the results.
+ * This function is thread safe if zstd is compiled with multithreaded support.
+ * It takes its parameters as an *OWNING* opaque pointer to support threading.
+ */
+static void FASTCOVER_tryParameters(void* opaque)
+{
+ /* Save parameters as local variables */
+ FASTCOVER_tryParameters_data_t *const data = (FASTCOVER_tryParameters_data_t*)opaque;
+ const FASTCOVER_ctx_t *const ctx = data->ctx;
+ const ZDICT_cover_params_t parameters = data->parameters;
+ size_t dictBufferCapacity = data->dictBufferCapacity;
+ size_t totalCompressedSize = ERROR(GENERIC);
+ /* Initialize array to keep track of frequency of dmer within activeSegment */
+ U16* segmentFreqs = (U16*)calloc(((U64)1 << ctx->f), sizeof(U16));
+ /* Allocate space for hash table, dict, and freqs */
+ BYTE *const dict = (BYTE*)malloc(dictBufferCapacity);
+ COVER_dictSelection_t selection = COVER_dictSelectionError(ERROR(GENERIC));
+ U32* freqs = (U32*) malloc(((U64)1 << ctx->f) * sizeof(U32));
+ if (!segmentFreqs || !dict || !freqs) {
+ DISPLAYLEVEL(1, "Failed to allocate buffers: out of memory\n");
+ goto _cleanup;
+ }
+ /* Copy the frequencies because we need to modify them */
+ memcpy(freqs, ctx->freqs, ((U64)1 << ctx->f) * sizeof(U32));
+ /* Build the dictionary */
+ { const size_t tail = FASTCOVER_buildDictionary(ctx, freqs, dict, dictBufferCapacity,
+ parameters, segmentFreqs);
+
+ const unsigned nbFinalizeSamples = (unsigned)(ctx->nbTrainSamples * ctx->accelParams.finalize / 100);
+ selection = COVER_selectDict(dict + tail, dictBufferCapacity, dictBufferCapacity - tail,
+ ctx->samples, ctx->samplesSizes, nbFinalizeSamples, ctx->nbTrainSamples, ctx->nbSamples, parameters, ctx->offsets,
+ totalCompressedSize);
+
+ if (COVER_dictSelectionIsError(selection)) {
+ DISPLAYLEVEL(1, "Failed to select dictionary\n");
+ goto _cleanup;
+ }
+ }
+_cleanup:
+ free(dict);
+ COVER_best_finish(data->best, parameters, selection);
+ free(data);
+ free(segmentFreqs);
+ COVER_dictSelectionFree(selection);
+ free(freqs);
+}
+
+
+static void
+FASTCOVER_convertToCoverParams(ZDICT_fastCover_params_t fastCoverParams,
+ ZDICT_cover_params_t* coverParams)
+{
+ coverParams->k = fastCoverParams.k;
+ coverParams->d = fastCoverParams.d;
+ coverParams->steps = fastCoverParams.steps;
+ coverParams->nbThreads = fastCoverParams.nbThreads;
+ coverParams->splitPoint = fastCoverParams.splitPoint;
+ coverParams->zParams = fastCoverParams.zParams;
+ coverParams->shrinkDict = fastCoverParams.shrinkDict;
+}
+
+
+static void
+FASTCOVER_convertToFastCoverParams(ZDICT_cover_params_t coverParams,
+ ZDICT_fastCover_params_t* fastCoverParams,
+ unsigned f, unsigned accel)
+{
+ fastCoverParams->k = coverParams.k;
+ fastCoverParams->d = coverParams.d;
+ fastCoverParams->steps = coverParams.steps;
+ fastCoverParams->nbThreads = coverParams.nbThreads;
+ fastCoverParams->splitPoint = coverParams.splitPoint;
+ fastCoverParams->f = f;
+ fastCoverParams->accel = accel;
+ fastCoverParams->zParams = coverParams.zParams;
+ fastCoverParams->shrinkDict = coverParams.shrinkDict;
+}
+
+
+ZDICTLIB_API size_t
+ZDICT_trainFromBuffer_fastCover(void* dictBuffer, size_t dictBufferCapacity,
+ const void* samplesBuffer,
+ const size_t* samplesSizes, unsigned nbSamples,
+ ZDICT_fastCover_params_t parameters)
+{
+ BYTE* const dict = (BYTE*)dictBuffer;
+ FASTCOVER_ctx_t ctx;
+ ZDICT_cover_params_t coverParams;
+ FASTCOVER_accel_t accelParams;
+ /* Initialize global data */
+ g_displayLevel = parameters.zParams.notificationLevel;
+ /* Assign splitPoint and f if not provided */
+ parameters.splitPoint = 1.0;
+ parameters.f = parameters.f == 0 ? DEFAULT_F : parameters.f;
+ parameters.accel = parameters.accel == 0 ? DEFAULT_ACCEL : parameters.accel;
+ /* Convert to cover parameter */
+ memset(&coverParams, 0 , sizeof(coverParams));
+ FASTCOVER_convertToCoverParams(parameters, &coverParams);
+ /* Checks */
+ if (!FASTCOVER_checkParameters(coverParams, dictBufferCapacity, parameters.f,
+ parameters.accel)) {
+ DISPLAYLEVEL(1, "FASTCOVER parameters incorrect\n");
+ return ERROR(parameter_outOfBound);
+ }
+ if (nbSamples == 0) {
+ DISPLAYLEVEL(1, "FASTCOVER must have at least one input file\n");
+ return ERROR(srcSize_wrong);
+ }
+ if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) {
+ DISPLAYLEVEL(1, "dictBufferCapacity must be at least %u\n",
+ ZDICT_DICTSIZE_MIN);
+ return ERROR(dstSize_tooSmall);
+ }
+ /* Assign corresponding FASTCOVER_accel_t to accelParams*/
+ accelParams = FASTCOVER_defaultAccelParameters[parameters.accel];
+ /* Initialize context */
+ {
+ size_t const initVal = FASTCOVER_ctx_init(&ctx, samplesBuffer, samplesSizes, nbSamples,
+ coverParams.d, parameters.splitPoint, parameters.f,
+ accelParams);
+ if (ZSTD_isError(initVal)) {
+ DISPLAYLEVEL(1, "Failed to initialize context\n");
+ return initVal;
+ }
+ }
+ COVER_warnOnSmallCorpus(dictBufferCapacity, ctx.nbDmers, g_displayLevel);
+ /* Build the dictionary */
+ DISPLAYLEVEL(2, "Building dictionary\n");
+ {
+ /* Initialize array to keep track of frequency of dmer within activeSegment */
+ U16* segmentFreqs = (U16 *)calloc(((U64)1 << parameters.f), sizeof(U16));
+ const size_t tail = FASTCOVER_buildDictionary(&ctx, ctx.freqs, dictBuffer,
+ dictBufferCapacity, coverParams, segmentFreqs);
+ const unsigned nbFinalizeSamples = (unsigned)(ctx.nbTrainSamples * ctx.accelParams.finalize / 100);
+ const size_t dictionarySize = ZDICT_finalizeDictionary(
+ dict, dictBufferCapacity, dict + tail, dictBufferCapacity - tail,
+ samplesBuffer, samplesSizes, nbFinalizeSamples, coverParams.zParams);
+ if (!ZSTD_isError(dictionarySize)) {
+ DISPLAYLEVEL(2, "Constructed dictionary of size %u\n",
+ (unsigned)dictionarySize);
+ }
+ FASTCOVER_ctx_destroy(&ctx);
+ free(segmentFreqs);
+ return dictionarySize;
+ }
+}
+
+
+ZDICTLIB_API size_t
+ZDICT_optimizeTrainFromBuffer_fastCover(
+ void* dictBuffer, size_t dictBufferCapacity,
+ const void* samplesBuffer,
+ const size_t* samplesSizes, unsigned nbSamples,
+ ZDICT_fastCover_params_t* parameters)
+{
+ ZDICT_cover_params_t coverParams;
+ FASTCOVER_accel_t accelParams;
+ /* constants */
+ const unsigned nbThreads = parameters->nbThreads;
+ const double splitPoint =
+ parameters->splitPoint <= 0.0 ? FASTCOVER_DEFAULT_SPLITPOINT : parameters->splitPoint;
+ const unsigned kMinD = parameters->d == 0 ? 6 : parameters->d;
+ const unsigned kMaxD = parameters->d == 0 ? 8 : parameters->d;
+ const unsigned kMinK = parameters->k == 0 ? 50 : parameters->k;
+ const unsigned kMaxK = parameters->k == 0 ? 2000 : parameters->k;
+ const unsigned kSteps = parameters->steps == 0 ? 40 : parameters->steps;
+ const unsigned kStepSize = MAX((kMaxK - kMinK) / kSteps, 1);
+ const unsigned kIterations =
+ (1 + (kMaxD - kMinD) / 2) * (1 + (kMaxK - kMinK) / kStepSize);
+ const unsigned f = parameters->f == 0 ? DEFAULT_F : parameters->f;
+ const unsigned accel = parameters->accel == 0 ? DEFAULT_ACCEL : parameters->accel;
+ const unsigned shrinkDict = 0;
+ /* Local variables */
+ const int displayLevel = parameters->zParams.notificationLevel;
+ unsigned iteration = 1;
+ unsigned d;
+ unsigned k;
+ COVER_best_t best;
+ POOL_ctx *pool = NULL;
+ int warned = 0;
+ /* Checks */
+ if (splitPoint <= 0 || splitPoint > 1) {
+ LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect splitPoint\n");
+ return ERROR(parameter_outOfBound);
+ }
+ if (accel == 0 || accel > FASTCOVER_MAX_ACCEL) {
+ LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect accel\n");
+ return ERROR(parameter_outOfBound);
+ }
+ if (kMinK < kMaxD || kMaxK < kMinK) {
+ LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect k\n");
+ return ERROR(parameter_outOfBound);
+ }
+ if (nbSamples == 0) {
+ LOCALDISPLAYLEVEL(displayLevel, 1, "FASTCOVER must have at least one input file\n");
+ return ERROR(srcSize_wrong);
+ }
+ if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) {
+ LOCALDISPLAYLEVEL(displayLevel, 1, "dictBufferCapacity must be at least %u\n",
+ ZDICT_DICTSIZE_MIN);
+ return ERROR(dstSize_tooSmall);
+ }
+ if (nbThreads > 1) {
+ pool = POOL_create(nbThreads, 1);
+ if (!pool) {
+ return ERROR(memory_allocation);
+ }
+ }
+ /* Initialization */
+ COVER_best_init(&best);
+ memset(&coverParams, 0 , sizeof(coverParams));
+ FASTCOVER_convertToCoverParams(*parameters, &coverParams);
+ accelParams = FASTCOVER_defaultAccelParameters[accel];
+ /* Turn down global display level to clean up display at level 2 and below */
+ g_displayLevel = displayLevel == 0 ? 0 : displayLevel - 1;
+ /* Loop through d first because each new value needs a new context */
+ LOCALDISPLAYLEVEL(displayLevel, 2, "Trying %u different sets of parameters\n",
+ kIterations);
+ for (d = kMinD; d <= kMaxD; d += 2) {
+ /* Initialize the context for this value of d */
+ FASTCOVER_ctx_t ctx;
+ LOCALDISPLAYLEVEL(displayLevel, 3, "d=%u\n", d);
+ {
+ size_t const initVal = FASTCOVER_ctx_init(&ctx, samplesBuffer, samplesSizes, nbSamples, d, splitPoint, f, accelParams);
+ if (ZSTD_isError(initVal)) {
+ LOCALDISPLAYLEVEL(displayLevel, 1, "Failed to initialize context\n");
+ COVER_best_destroy(&best);
+ POOL_free(pool);
+ return initVal;
+ }
+ }
+ if (!warned) {
+ COVER_warnOnSmallCorpus(dictBufferCapacity, ctx.nbDmers, displayLevel);
+ warned = 1;
+ }
+ /* Loop through k reusing the same context */
+ for (k = kMinK; k <= kMaxK; k += kStepSize) {
+ /* Prepare the arguments */
+ FASTCOVER_tryParameters_data_t *data = (FASTCOVER_tryParameters_data_t *)malloc(
+ sizeof(FASTCOVER_tryParameters_data_t));
+ LOCALDISPLAYLEVEL(displayLevel, 3, "k=%u\n", k);
+ if (!data) {
+ LOCALDISPLAYLEVEL(displayLevel, 1, "Failed to allocate parameters\n");
+ COVER_best_destroy(&best);
+ FASTCOVER_ctx_destroy(&ctx);
+ POOL_free(pool);
+ return ERROR(memory_allocation);
+ }
+ data->ctx = &ctx;
+ data->best = &best;
+ data->dictBufferCapacity = dictBufferCapacity;
+ data->parameters = coverParams;
+ data->parameters.k = k;
+ data->parameters.d = d;
+ data->parameters.splitPoint = splitPoint;
+ data->parameters.steps = kSteps;
+ data->parameters.shrinkDict = shrinkDict;
+ data->parameters.zParams.notificationLevel = g_displayLevel;
+ /* Check the parameters */
+ if (!FASTCOVER_checkParameters(data->parameters, dictBufferCapacity,
+ data->ctx->f, accel)) {
+ DISPLAYLEVEL(1, "FASTCOVER parameters incorrect\n");
+ free(data);
+ continue;
+ }
+ /* Call the function and pass ownership of data to it */
+ COVER_best_start(&best);
+ if (pool) {
+ POOL_add(pool, &FASTCOVER_tryParameters, data);
+ } else {
+ FASTCOVER_tryParameters(data);
+ }
+ /* Print status */
+ LOCALDISPLAYUPDATE(displayLevel, 2, "\r%u%% ",
+ (unsigned)((iteration * 100) / kIterations));
+ ++iteration;
+ }
+ COVER_best_wait(&best);
+ FASTCOVER_ctx_destroy(&ctx);
+ }
+ LOCALDISPLAYLEVEL(displayLevel, 2, "\r%79s\r", "");
+ /* Fill the output buffer and parameters with output of the best parameters */
+ {
+ const size_t dictSize = best.dictSize;
+ if (ZSTD_isError(best.compressedSize)) {
+ const size_t compressedSize = best.compressedSize;
+ COVER_best_destroy(&best);
+ POOL_free(pool);
+ return compressedSize;
+ }
+ FASTCOVER_convertToFastCoverParams(best.parameters, parameters, f, accel);
+ memcpy(dictBuffer, best.dict, dictSize);
+ COVER_best_destroy(&best);
+ POOL_free(pool);
+ return dictSize;
+ }
+
+}
diff --git a/zstd/dictBuilder/zdict.c b/zstd/dictBuilder/zdict.c
new file mode 100644
index 00000000..459cbe4d
--- /dev/null
+++ b/zstd/dictBuilder/zdict.c
@@ -0,0 +1,1134 @@
+/*
+ * Copyright (c) Yann Collet, Facebook, Inc.
+ * All rights reserved.
+ *
+ * This source code is licensed under both the BSD-style license (found in the
+ * LICENSE file in the root directory of this source tree) and the GPLv2 (found
+ * in the COPYING file in the root directory of this source tree).
+ * You may select, at your option, one of the above-listed licenses.
+ */
+
+
+/*-**************************************
+* Tuning parameters
+****************************************/
+#define MINRATIO 4 /* minimum nb of apparition to be selected in dictionary */
+#define ZDICT_MAX_SAMPLES_SIZE (2000U << 20)
+#define ZDICT_MIN_SAMPLES_SIZE (ZDICT_CONTENTSIZE_MIN * MINRATIO)
+
+
+/*-**************************************
+* Compiler Options
+****************************************/
+/* Unix Large Files support (>4GB) */
+#define _FILE_OFFSET_BITS 64
+#if (defined(__sun__) && (!defined(__LP64__))) /* Sun Solaris 32-bits requires specific definitions */
+# ifndef _LARGEFILE_SOURCE
+# define _LARGEFILE_SOURCE
+# endif
+#elif ! defined(__LP64__) /* No point defining Large file for 64 bit */
+# ifndef _LARGEFILE64_SOURCE
+# define _LARGEFILE64_SOURCE
+# endif
+#endif
+
+
+/*-*************************************
+* Dependencies
+***************************************/
+#include <stdlib.h> /* malloc, free */
+#include <string.h> /* memset */
+#include <stdio.h> /* fprintf, fopen, ftello64 */
+#include <time.h> /* clock */
+
+#ifndef ZDICT_STATIC_LINKING_ONLY
+# define ZDICT_STATIC_LINKING_ONLY
+#endif
+#define HUF_STATIC_LINKING_ONLY
+
+#include "../common/mem.h" /* read */
+#include "../common/fse.h" /* FSE_normalizeCount, FSE_writeNCount */
+#include "../common/huf.h" /* HUF_buildCTable, HUF_writeCTable */
+#include "../common/zstd_internal.h" /* includes zstd.h */
+#include "../common/xxhash.h" /* XXH64 */
+#include "../compress/zstd_compress_internal.h" /* ZSTD_loadCEntropy() */
+#include "../zdict.h"
+#include "divsufsort.h"
+
+
+/*-*************************************
+* Constants
+***************************************/
+#define KB *(1 <<10)
+#define MB *(1 <<20)
+#define GB *(1U<<30)
+
+#define DICTLISTSIZE_DEFAULT 10000
+
+#define NOISELENGTH 32
+
+static const U32 g_selectivity_default = 9;
+
+
+/*-*************************************
+* Console display
+***************************************/
+#undef DISPLAY
+#define DISPLAY(...) { fprintf(stderr, __VA_ARGS__); fflush( stderr ); }
+#undef DISPLAYLEVEL
+#define DISPLAYLEVEL(l, ...) if (notificationLevel>=l) { DISPLAY(__VA_ARGS__); } /* 0 : no display; 1: errors; 2: default; 3: details; 4: debug */
+
+static clock_t ZDICT_clockSpan(clock_t nPrevious) { return clock() - nPrevious; }
+
+static void ZDICT_printHex(const void* ptr, size_t length)
+{
+ const BYTE* const b = (const BYTE*)ptr;
+ size_t u;
+ for (u=0; u<length; u++) {
+ BYTE c = b[u];
+ if (c<32 || c>126) c = '.'; /* non-printable char */
+ DISPLAY("%c", c);
+ }
+}
+
+
+/*-********************************************************
+* Helper functions
+**********************************************************/
+unsigned ZDICT_isError(size_t errorCode) { return ERR_isError(errorCode); }
+
+const char* ZDICT_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
+
+unsigned ZDICT_getDictID(const void* dictBuffer, size_t dictSize)
+{
+ if (dictSize < 8) return 0;
+ if (MEM_readLE32(dictBuffer) != ZSTD_MAGIC_DICTIONARY) return 0;
+ return MEM_readLE32((const char*)dictBuffer + 4);
+}
+
+size_t ZDICT_getDictHeaderSize(const void* dictBuffer, size_t dictSize)
+{
+ size_t headerSize;
+ if (dictSize <= 8 || MEM_readLE32(dictBuffer) != ZSTD_MAGIC_DICTIONARY) return ERROR(dictionary_corrupted);
+
+ { ZSTD_compressedBlockState_t* bs = (ZSTD_compressedBlockState_t*)malloc(sizeof(ZSTD_compressedBlockState_t));
+ U32* wksp = (U32*)malloc(HUF_WORKSPACE_SIZE);
+ if (!bs || !wksp) {
+ headerSize = ERROR(memory_allocation);
+ } else {
+ ZSTD_reset_compressedBlockState(bs);
+ headerSize = ZSTD_loadCEntropy(bs, wksp, dictBuffer, dictSize);
+ }
+
+ free(bs);
+ free(wksp);
+ }
+
+ return headerSize;
+}
+
+/*-********************************************************
+* Dictionary training functions
+**********************************************************/
+static unsigned ZDICT_NbCommonBytes (size_t val)
+{
+ if (MEM_isLittleEndian()) {
+ if (MEM_64bits()) {
+# if defined(_MSC_VER) && defined(_WIN64)
+ unsigned long r = 0;
+ _BitScanForward64( &r, (U64)val );
+ return (unsigned)(r>>3);
+# elif defined(__GNUC__) && (__GNUC__ >= 3)
+ return (__builtin_ctzll((U64)val) >> 3);
+# else
+ static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 };
+ return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
+# endif
+ } else { /* 32 bits */
+# if defined(_MSC_VER)
+ unsigned long r=0;
+ _BitScanForward( &r, (U32)val );
+ return (unsigned)(r>>3);
+# elif defined(__GNUC__) && (__GNUC__ >= 3)
+ return (__builtin_ctz((U32)val) >> 3);
+# else
+ static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };
+ return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
+# endif
+ }
+ } else { /* Big Endian CPU */
+ if (MEM_64bits()) {
+# if defined(_MSC_VER) && defined(_WIN64)
+ unsigned long r = 0;
+ _BitScanReverse64( &r, val );
+ return (unsigned)(r>>3);
+# elif defined(__GNUC__) && (__GNUC__ >= 3)
+ return (__builtin_clzll(val) >> 3);
+# else
+ unsigned r;
+ const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */
+ if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
+ if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
+ r += (!val);
+ return r;
+# endif
+ } else { /* 32 bits */
+# if defined(_MSC_VER)
+ unsigned long r = 0;
+ _BitScanReverse( &r, (unsigned long)val );
+ return (unsigned)(r>>3);
+# elif defined(__GNUC__) && (__GNUC__ >= 3)
+ return (__builtin_clz((U32)val) >> 3);
+# else
+ unsigned r;
+ if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
+ r += (!val);
+ return r;
+# endif
+ } }
+}
+
+
+/*! ZDICT_count() :
+ Count the nb of common bytes between 2 pointers.
+ Note : this function presumes end of buffer followed by noisy guard band.
+*/
+static size_t ZDICT_count(const void* pIn, const void* pMatch)
+{
+ const char* const pStart = (const char*)pIn;
+ for (;;) {
+ size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
+ if (!diff) {
+ pIn = (const char*)pIn+sizeof(size_t);
+ pMatch = (const char*)pMatch+sizeof(size_t);
+ continue;
+ }
+ pIn = (const char*)pIn+ZDICT_NbCommonBytes(diff);
+ return (size_t)((const char*)pIn - pStart);
+ }
+}
+
+
+typedef struct {
+ U32 pos;
+ U32 length;
+ U32 savings;
+} dictItem;
+
+static void ZDICT_initDictItem(dictItem* d)
+{
+ d->pos = 1;
+ d->length = 0;
+ d->savings = (U32)(-1);
+}
+
+
+#define LLIMIT 64 /* heuristic determined experimentally */
+#define MINMATCHLENGTH 7 /* heuristic determined experimentally */
+static dictItem ZDICT_analyzePos(
+ BYTE* doneMarks,
+ const int* suffix, U32 start,
+ const void* buffer, U32 minRatio, U32 notificationLevel)
+{
+ U32 lengthList[LLIMIT] = {0};
+ U32 cumulLength[LLIMIT] = {0};
+ U32 savings[LLIMIT] = {0};
+ const BYTE* b = (const BYTE*)buffer;
+ size_t maxLength = LLIMIT;
+ size_t pos = suffix[start];
+ U32 end = start;
+ dictItem solution;
+
+ /* init */
+ memset(&solution, 0, sizeof(solution));
+ doneMarks[pos] = 1;
+
+ /* trivial repetition cases */
+ if ( (MEM_read16(b+pos+0) == MEM_read16(b+pos+2))
+ ||(MEM_read16(b+pos+1) == MEM_read16(b+pos+3))
+ ||(MEM_read16(b+pos+2) == MEM_read16(b+pos+4)) ) {
+ /* skip and mark segment */
+ U16 const pattern16 = MEM_read16(b+pos+4);
+ U32 u, patternEnd = 6;
+ while (MEM_read16(b+pos+patternEnd) == pattern16) patternEnd+=2 ;
+ if (b[pos+patternEnd] == b[pos+patternEnd-1]) patternEnd++;
+ for (u=1; u<patternEnd; u++)
+ doneMarks[pos+u] = 1;
+ return solution;
+ }
+
+ /* look forward */
+ { size_t length;
+ do {
+ end++;
+ length = ZDICT_count(b + pos, b + suffix[end]);
+ } while (length >= MINMATCHLENGTH);
+ }
+
+ /* look backward */
+ { size_t length;
+ do {
+ length = ZDICT_count(b + pos, b + *(suffix+start-1));
+ if (length >=MINMATCHLENGTH) start--;
+ } while(length >= MINMATCHLENGTH);
+ }
+
+ /* exit if not found a minimum nb of repetitions */
+ if (end-start < minRatio) {
+ U32 idx;
+ for(idx=start; idx<end; idx++)
+ doneMarks[suffix[idx]] = 1;
+ return solution;
+ }
+
+ { int i;
+ U32 mml;
+ U32 refinedStart = start;
+ U32 refinedEnd = end;
+
+ DISPLAYLEVEL(4, "\n");
+ DISPLAYLEVEL(4, "found %3u matches of length >= %i at pos %7u ", (unsigned)(end-start), MINMATCHLENGTH, (unsigned)pos);
+ DISPLAYLEVEL(4, "\n");
+
+ for (mml = MINMATCHLENGTH ; ; mml++) {
+ BYTE currentChar = 0;
+ U32 currentCount = 0;
+ U32 currentID = refinedStart;
+ U32 id;
+ U32 selectedCount = 0;
+ U32 selectedID = currentID;
+ for (id =refinedStart; id < refinedEnd; id++) {
+ if (b[suffix[id] + mml] != currentChar) {
+ if (currentCount > selectedCount) {
+ selectedCount = currentCount;
+ selectedID = currentID;
+ }
+ currentID = id;
+ currentChar = b[ suffix[id] + mml];
+ currentCount = 0;
+ }
+ currentCount ++;
+ }
+ if (currentCount > selectedCount) { /* for last */
+ selectedCount = currentCount;
+ selectedID = currentID;
+ }
+
+ if (selectedCount < minRatio)
+ break;
+ refinedStart = selectedID;
+ refinedEnd = refinedStart + selectedCount;
+ }
+
+ /* evaluate gain based on new dict */
+ start = refinedStart;
+ pos = suffix[refinedStart];
+ end = start;
+ memset(lengthList, 0, sizeof(lengthList));
+
+ /* look forward */
+ { size_t length;
+ do {
+ end++;
+ length = ZDICT_count(b + pos, b + suffix[end]);
+ if (length >= LLIMIT) length = LLIMIT-1;
+ lengthList[length]++;
+ } while (length >=MINMATCHLENGTH);
+ }
+
+ /* look backward */
+ { size_t length = MINMATCHLENGTH;
+ while ((length >= MINMATCHLENGTH) & (start > 0)) {
+ length = ZDICT_count(b + pos, b + suffix[start - 1]);
+ if (length >= LLIMIT) length = LLIMIT - 1;
+ lengthList[length]++;
+ if (length >= MINMATCHLENGTH) start--;
+ }
+ }
+
+ /* largest useful length */
+ memset(cumulLength, 0, sizeof(cumulLength));
+ cumulLength[maxLength-1] = lengthList[maxLength-1];
+ for (i=(int)(maxLength-2); i>=0; i--)
+ cumulLength[i] = cumulLength[i+1] + lengthList[i];
+
+ for (i=LLIMIT-1; i>=MINMATCHLENGTH; i--) if (cumulLength[i]>=minRatio) break;
+ maxLength = i;
+
+ /* reduce maxLength in case of final into repetitive data */
+ { U32 l = (U32)maxLength;
+ BYTE const c = b[pos + maxLength-1];
+ while (b[pos+l-2]==c) l--;
+ maxLength = l;
+ }
+ if (maxLength < MINMATCHLENGTH) return solution; /* skip : no long-enough solution */
+
+ /* calculate savings */
+ savings[5] = 0;
+ for (i=MINMATCHLENGTH; i<=(int)maxLength; i++)
+ savings[i] = savings[i-1] + (lengthList[i] * (i-3));
+
+ DISPLAYLEVEL(4, "Selected dict at position %u, of length %u : saves %u (ratio: %.2f) \n",
+ (unsigned)pos, (unsigned)maxLength, (unsigned)savings[maxLength], (double)savings[maxLength] / maxLength);
+
+ solution.pos = (U32)pos;
+ solution.length = (U32)maxLength;
+ solution.savings = savings[maxLength];
+
+ /* mark positions done */
+ { U32 id;
+ for (id=start; id<end; id++) {
+ U32 p, pEnd, length;
+ U32 const testedPos = suffix[id];
+ if (testedPos == pos)
+ length = solution.length;
+ else {
+ length = (U32)ZDICT_count(b+pos, b+testedPos);
+ if (length > solution.length) length = solution.length;
+ }
+ pEnd = (U32)(testedPos + length);
+ for (p=testedPos; p<pEnd; p++)
+ doneMarks[p] = 1;
+ } } }
+
+ return solution;
+}
+
+
+static int isIncluded(const void* in, const void* container, size_t length)
+{
+ const char* const ip = (const char*) in;
+ const char* const into = (const char*) container;
+ size_t u;
+
+ for (u=0; u<length; u++) { /* works because end of buffer is a noisy guard band */
+ if (ip[u] != into[u]) break;
+ }
+
+ return u==length;
+}
+
+/*! ZDICT_tryMerge() :
+ check if dictItem can be merged, do it if possible
+ @return : id of destination elt, 0 if not merged
+*/
+static U32 ZDICT_tryMerge(dictItem* table, dictItem elt, U32 eltNbToSkip, const void* buffer)
+{
+ const U32 tableSize = table->pos;
+ const U32 eltEnd = elt.pos + elt.length;
+ const char* const buf = (const char*) buffer;
+
+ /* tail overlap */
+ U32 u; for (u=1; u<tableSize; u++) {
+ if (u==eltNbToSkip) continue;
+ if ((table[u].pos > elt.pos) && (table[u].pos <= eltEnd)) { /* overlap, existing > new */
+ /* append */
+ U32 const addedLength = table[u].pos - elt.pos;
+ table[u].length += addedLength;
+ table[u].pos = elt.pos;
+ table[u].savings += elt.savings * addedLength / elt.length; /* rough approx */
+ table[u].savings += elt.length / 8; /* rough approx bonus */
+ elt = table[u];
+ /* sort : improve rank */
+ while ((u>1) && (table[u-1].savings < elt.savings))
+ table[u] = table[u-1], u--;
+ table[u] = elt;
+ return u;
+ } }
+
+ /* front overlap */
+ for (u=1; u<tableSize; u++) {
+ if (u==eltNbToSkip) continue;
+
+ if ((table[u].pos + table[u].length >= elt.pos) && (table[u].pos < elt.pos)) { /* overlap, existing < new */
+ /* append */
+ int const addedLength = (int)eltEnd - (table[u].pos + table[u].length);
+ table[u].savings += elt.length / 8; /* rough approx bonus */
+ if (addedLength > 0) { /* otherwise, elt fully included into existing */
+ table[u].length += addedLength;
+ table[u].savings += elt.savings * addedLength / elt.length; /* rough approx */
+ }
+ /* sort : improve rank */
+ elt = table[u];
+ while ((u>1) && (table[u-1].savings < elt.savings))
+ table[u] = table[u-1], u--;
+ table[u] = elt;
+ return u;
+ }
+
+ if (MEM_read64(buf + table[u].pos) == MEM_read64(buf + elt.pos + 1)) {
+ if (isIncluded(buf + table[u].pos, buf + elt.pos + 1, table[u].length)) {
+ size_t const addedLength = MAX( (int)elt.length - (int)table[u].length , 1 );
+ table[u].pos = elt.pos;
+ table[u].savings += (U32)(elt.savings * addedLength / elt.length);
+ table[u].length = MIN(elt.length, table[u].length + 1);
+ return u;
+ }
+ }
+ }
+
+ return 0;
+}
+
+
+static void ZDICT_removeDictItem(dictItem* table, U32 id)
+{
+ /* convention : table[0].pos stores nb of elts */
+ U32 const max = table[0].pos;
+ U32 u;
+ if (!id) return; /* protection, should never happen */
+ for (u=id; u<max-1; u++)
+ table[u] = table[u+1];
+ table->pos--;
+}
+
+
+static void ZDICT_insertDictItem(dictItem* table, U32 maxSize, dictItem elt, const void* buffer)
+{
+ /* merge if possible */
+ U32 mergeId = ZDICT_tryMerge(table, elt, 0, buffer);
+ if (mergeId) {
+ U32 newMerge = 1;
+ while (newMerge) {
+ newMerge = ZDICT_tryMerge(table, table[mergeId], mergeId, buffer);
+ if (newMerge) ZDICT_removeDictItem(table, mergeId);
+ mergeId = newMerge;
+ }
+ return;
+ }
+
+ /* insert */
+ { U32 current;
+ U32 nextElt = table->pos;
+ if (nextElt >= maxSize) nextElt = maxSize-1;
+ current = nextElt-1;
+ while (table[current].savings < elt.savings) {
+ table[current+1] = table[current];
+ current--;
+ }
+ table[current+1] = elt;
+ table->pos = nextElt+1;
+ }
+}
+
+
+static U32 ZDICT_dictSize(const dictItem* dictList)
+{
+ U32 u, dictSize = 0;
+ for (u=1; u<dictList[0].pos; u++)
+ dictSize += dictList[u].length;
+ return dictSize;
+}
+
+
+static size_t ZDICT_trainBuffer_legacy(dictItem* dictList, U32 dictListSize,
+ const void* const buffer, size_t bufferSize, /* buffer must end with noisy guard band */
+ const size_t* fileSizes, unsigned nbFiles,
+ unsigned minRatio, U32 notificationLevel)
+{
+ int* const suffix0 = (int*)malloc((bufferSize+2)*sizeof(*suffix0));
+ int* const suffix = suffix0+1;
+ U32* reverseSuffix = (U32*)malloc((bufferSize)*sizeof(*reverseSuffix));
+ BYTE* doneMarks = (BYTE*)malloc((bufferSize+16)*sizeof(*doneMarks)); /* +16 for overflow security */
+ U32* filePos = (U32*)malloc(nbFiles * sizeof(*filePos));
+ size_t result = 0;
+ clock_t displayClock = 0;
+ clock_t const refreshRate = CLOCKS_PER_SEC * 3 / 10;
+
+# undef DISPLAYUPDATE
+# define DISPLAYUPDATE(l, ...) if (notificationLevel>=l) { \
+ if (ZDICT_clockSpan(displayClock) > refreshRate) \
+ { displayClock = clock(); DISPLAY(__VA_ARGS__); \
+ if (notificationLevel>=4) fflush(stderr); } }
+
+ /* init */
+ DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
+ if (!suffix0 || !reverseSuffix || !doneMarks || !filePos) {
+ result = ERROR(memory_allocation);
+ goto _cleanup;
+ }
+ if (minRatio < MINRATIO) minRatio = MINRATIO;
+ memset(doneMarks, 0, bufferSize+16);
+
+ /* limit sample set size (divsufsort limitation)*/
+ if (bufferSize > ZDICT_MAX_SAMPLES_SIZE) DISPLAYLEVEL(3, "sample set too large : reduced to %u MB ...\n", (unsigned)(ZDICT_MAX_SAMPLES_SIZE>>20));
+ while (bufferSize > ZDICT_MAX_SAMPLES_SIZE) bufferSize -= fileSizes[--nbFiles];
+
+ /* sort */
+ DISPLAYLEVEL(2, "sorting %u files of total size %u MB ...\n", nbFiles, (unsigned)(bufferSize>>20));
+ { int const divSuftSortResult = divsufsort((const unsigned char*)buffer, suffix, (int)bufferSize, 0);
+ if (divSuftSortResult != 0) { result = ERROR(GENERIC); goto _cleanup; }
+ }
+ suffix[bufferSize] = (int)bufferSize; /* leads into noise */
+ suffix0[0] = (int)bufferSize; /* leads into noise */
+ /* build reverse suffix sort */
+ { size_t pos;
+ for (pos=0; pos < bufferSize; pos++)
+ reverseSuffix[suffix[pos]] = (U32)pos;
+ /* note filePos tracks borders between samples.
+ It's not used at this stage, but planned to become useful in a later update */
+ filePos[0] = 0;
+ for (pos=1; pos<nbFiles; pos++)
+ filePos[pos] = (U32)(filePos[pos-1] + fileSizes[pos-1]);
+ }
+
+ DISPLAYLEVEL(2, "finding patterns ... \n");
+ DISPLAYLEVEL(3, "minimum ratio : %u \n", minRatio);
+
+ { U32 cursor; for (cursor=0; cursor < bufferSize; ) {
+ dictItem solution;
+ if (doneMarks[cursor]) { cursor++; continue; }
+ solution = ZDICT_analyzePos(doneMarks, suffix, reverseSuffix[cursor], buffer, minRatio, notificationLevel);
+ if (solution.length==0) { cursor++; continue; }
+ ZDICT_insertDictItem(dictList, dictListSize, solution, buffer);
+ cursor += solution.length;
+ DISPLAYUPDATE(2, "\r%4.2f %% \r", (double)cursor / bufferSize * 100);
+ } }
+
+_cleanup:
+ free(suffix0);
+ free(reverseSuffix);
+ free(doneMarks);
+ free(filePos);
+ return result;
+}
+
+
+static void ZDICT_fillNoise(void* buffer, size_t length)
+{
+ unsigned const prime1 = 2654435761U;
+ unsigned const prime2 = 2246822519U;
+ unsigned acc = prime1;
+ size_t p=0;
+ for (p=0; p<length; p++) {
+ acc *= prime2;
+ ((unsigned char*)buffer)[p] = (unsigned char)(acc >> 21);
+ }
+}
+
+
+typedef struct
+{
+ ZSTD_CDict* dict; /* dictionary */
+ ZSTD_CCtx* zc; /* working context */
+ void* workPlace; /* must be ZSTD_BLOCKSIZE_MAX allocated */
+} EStats_ress_t;
+
+#define MAXREPOFFSET 1024
+
+static void ZDICT_countEStats(EStats_ress_t esr, const ZSTD_parameters* params,
+ unsigned* countLit, unsigned* offsetcodeCount, unsigned* matchlengthCount, unsigned* litlengthCount, U32* repOffsets,
+ const void* src, size_t srcSize,
+ U32 notificationLevel)
+{
+ size_t const blockSizeMax = MIN (ZSTD_BLOCKSIZE_MAX, 1 << params->cParams.windowLog);
+ size_t cSize;
+
+ if (srcSize > blockSizeMax) srcSize = blockSizeMax; /* protection vs large samples */
+ { size_t const errorCode = ZSTD_compressBegin_usingCDict(esr.zc, esr.dict);
+ if (ZSTD_isError(errorCode)) { DISPLAYLEVEL(1, "warning : ZSTD_compressBegin_usingCDict failed \n"); return; }
+
+ }
+ cSize = ZSTD_compressBlock(esr.zc, esr.workPlace, ZSTD_BLOCKSIZE_MAX, src, srcSize);
+ if (ZSTD_isError(cSize)) { DISPLAYLEVEL(3, "warning : could not compress sample size %u \n", (unsigned)srcSize); return; }
+
+ if (cSize) { /* if == 0; block is not compressible */
+ const seqStore_t* const seqStorePtr = ZSTD_getSeqStore(esr.zc);
+
+ /* literals stats */
+ { const BYTE* bytePtr;
+ for(bytePtr = seqStorePtr->litStart; bytePtr < seqStorePtr->lit; bytePtr++)
+ countLit[*bytePtr]++;
+ }
+
+ /* seqStats */
+ { U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
+ ZSTD_seqToCodes(seqStorePtr);
+
+ { const BYTE* codePtr = seqStorePtr->ofCode;
+ U32 u;
+ for (u=0; u<nbSeq; u++) offsetcodeCount[codePtr[u]]++;
+ }
+
+ { const BYTE* codePtr = seqStorePtr->mlCode;
+ U32 u;
+ for (u=0; u<nbSeq; u++) matchlengthCount[codePtr[u]]++;
+ }
+
+ { const BYTE* codePtr = seqStorePtr->llCode;
+ U32 u;
+ for (u=0; u<nbSeq; u++) litlengthCount[codePtr[u]]++;
+ }
+
+ if (nbSeq >= 2) { /* rep offsets */
+ const seqDef* const seq = seqStorePtr->sequencesStart;
+ U32 offset1 = seq[0].offset - 3;
+ U32 offset2 = seq[1].offset - 3;
+ if (offset1 >= MAXREPOFFSET) offset1 = 0;
+ if (offset2 >= MAXREPOFFSET) offset2 = 0;
+ repOffsets[offset1] += 3;
+ repOffsets[offset2] += 1;
+ } } }
+}
+
+static size_t ZDICT_totalSampleSize(const size_t* fileSizes, unsigned nbFiles)
+{
+ size_t total=0;
+ unsigned u;
+ for (u=0; u<nbFiles; u++) total += fileSizes[u];
+ return total;
+}
+
+typedef struct { U32 offset; U32 count; } offsetCount_t;
+
+static void ZDICT_insertSortCount(offsetCount_t table[ZSTD_REP_NUM+1], U32 val, U32 count)
+{
+ U32 u;
+ table[ZSTD_REP_NUM].offset = val;
+ table[ZSTD_REP_NUM].count = count;
+ for (u=ZSTD_REP_NUM; u>0; u--) {
+ offsetCount_t tmp;
+ if (table[u-1].count >= table[u].count) break;
+ tmp = table[u-1];
+ table[u-1] = table[u];
+ table[u] = tmp;
+ }
+}
+
+/* ZDICT_flatLit() :
+ * rewrite `countLit` to contain a mostly flat but still compressible distribution of literals.
+ * necessary to avoid generating a non-compressible distribution that HUF_writeCTable() cannot encode.
+ */
+static void ZDICT_flatLit(unsigned* countLit)
+{
+ int u;
+ for (u=1; u<256; u++) countLit[u] = 2;
+ countLit[0] = 4;
+ countLit[253] = 1;
+ countLit[254] = 1;
+}
+
+#define OFFCODE_MAX 30 /* only applicable to first block */
+static size_t ZDICT_analyzeEntropy(void* dstBuffer, size_t maxDstSize,
+ int compressionLevel,
+ const void* srcBuffer, const size_t* fileSizes, unsigned nbFiles,
+ const void* dictBuffer, size_t dictBufferSize,
+ unsigned notificationLevel)
+{
+ unsigned countLit[256];
+ HUF_CREATE_STATIC_CTABLE(hufTable, 255);
+ unsigned offcodeCount[OFFCODE_MAX+1];
+ short offcodeNCount[OFFCODE_MAX+1];
+ U32 offcodeMax = ZSTD_highbit32((U32)(dictBufferSize + 128 KB));
+ unsigned matchLengthCount[MaxML+1];
+ short matchLengthNCount[MaxML+1];
+ unsigned litLengthCount[MaxLL+1];
+ short litLengthNCount[MaxLL+1];
+ U32 repOffset[MAXREPOFFSET];
+ offsetCount_t bestRepOffset[ZSTD_REP_NUM+1];
+ EStats_ress_t esr = { NULL, NULL, NULL };
+ ZSTD_parameters params;
+ U32 u, huffLog = 11, Offlog = OffFSELog, mlLog = MLFSELog, llLog = LLFSELog, total;
+ size_t pos = 0, errorCode;
+ size_t eSize = 0;
+ size_t const totalSrcSize = ZDICT_totalSampleSize(fileSizes, nbFiles);
+ size_t const averageSampleSize = totalSrcSize / (nbFiles + !nbFiles);
+ BYTE* dstPtr = (BYTE*)dstBuffer;
+
+ /* init */
+ DEBUGLOG(4, "ZDICT_analyzeEntropy");
+ if (offcodeMax>OFFCODE_MAX) { eSize = ERROR(dictionaryCreation_failed); goto _cleanup; } /* too large dictionary */
+ for (u=0; u<256; u++) countLit[u] = 1; /* any character must be described */
+ for (u=0; u<=offcodeMax; u++) offcodeCount[u] = 1;
+ for (u=0; u<=MaxML; u++) matchLengthCount[u] = 1;
+ for (u=0; u<=MaxLL; u++) litLengthCount[u] = 1;
+ memset(repOffset, 0, sizeof(repOffset));
+ repOffset[1] = repOffset[4] = repOffset[8] = 1;
+ memset(bestRepOffset, 0, sizeof(bestRepOffset));
+ if (compressionLevel==0) compressionLevel = ZSTD_CLEVEL_DEFAULT;
+ params = ZSTD_getParams(compressionLevel, averageSampleSize, dictBufferSize);
+
+ esr.dict = ZSTD_createCDict_advanced(dictBuffer, dictBufferSize, ZSTD_dlm_byRef, ZSTD_dct_rawContent, params.cParams, ZSTD_defaultCMem);
+ esr.zc = ZSTD_createCCtx();
+ esr.workPlace = malloc(ZSTD_BLOCKSIZE_MAX);
+ if (!esr.dict || !esr.zc || !esr.workPlace) {
+ eSize = ERROR(memory_allocation);
+ DISPLAYLEVEL(1, "Not enough memory \n");
+ goto _cleanup;
+ }
+
+ /* collect stats on all samples */
+ for (u=0; u<nbFiles; u++) {
+ ZDICT_countEStats(esr, &params,
+ countLit, offcodeCount, matchLengthCount, litLengthCount, repOffset,
+ (const char*)srcBuffer + pos, fileSizes[u],
+ notificationLevel);
+ pos += fileSizes[u];
+ }
+
+ /* analyze, build stats, starting with literals */
+ { size_t maxNbBits = HUF_buildCTable (hufTable, countLit, 255, huffLog);
+ if (HUF_isError(maxNbBits)) {
+ eSize = maxNbBits;
+ DISPLAYLEVEL(1, " HUF_buildCTable error \n");
+ goto _cleanup;
+ }
+ if (maxNbBits==8) { /* not compressible : will fail on HUF_writeCTable() */
+ DISPLAYLEVEL(2, "warning : pathological dataset : literals are not compressible : samples are noisy or too regular \n");
+ ZDICT_flatLit(countLit); /* replace distribution by a fake "mostly flat but still compressible" distribution, that HUF_writeCTable() can encode */
+ maxNbBits = HUF_buildCTable (hufTable, countLit, 255, huffLog);
+ assert(maxNbBits==9);
+ }
+ huffLog = (U32)maxNbBits;
+ }
+
+ /* looking for most common first offsets */
+ { U32 offset;
+ for (offset=1; offset<MAXREPOFFSET; offset++)
+ ZDICT_insertSortCount(bestRepOffset, offset, repOffset[offset]);
+ }
+ /* note : the result of this phase should be used to better appreciate the impact on statistics */
+
+ total=0; for (u=0; u<=offcodeMax; u++) total+=offcodeCount[u];
+ errorCode = FSE_normalizeCount(offcodeNCount, Offlog, offcodeCount, total, offcodeMax, /* useLowProbCount */ 1);
+ if (FSE_isError(errorCode)) {
+ eSize = errorCode;
+ DISPLAYLEVEL(1, "FSE_normalizeCount error with offcodeCount \n");
+ goto _cleanup;
+ }
+ Offlog = (U32)errorCode;
+
+ total=0; for (u=0; u<=MaxML; u++) total+=matchLengthCount[u];
+ errorCode = FSE_normalizeCount(matchLengthNCount, mlLog, matchLengthCount, total, MaxML, /* useLowProbCount */ 1);
+ if (FSE_isError(errorCode)) {
+ eSize = errorCode;
+ DISPLAYLEVEL(1, "FSE_normalizeCount error with matchLengthCount \n");
+ goto _cleanup;
+ }
+ mlLog = (U32)errorCode;
+
+ total=0; for (u=0; u<=MaxLL; u++) total+=litLengthCount[u];
+ errorCode = FSE_normalizeCount(litLengthNCount, llLog, litLengthCount, total, MaxLL, /* useLowProbCount */ 1);
+ if (FSE_isError(errorCode)) {
+ eSize = errorCode;
+ DISPLAYLEVEL(1, "FSE_normalizeCount error with litLengthCount \n");
+ goto _cleanup;
+ }
+ llLog = (U32)errorCode;
+
+ /* write result to buffer */
+ { size_t const hhSize = HUF_writeCTable(dstPtr, maxDstSize, hufTable, 255, huffLog);
+ if (HUF_isError(hhSize)) {
+ eSize = hhSize;
+ DISPLAYLEVEL(1, "HUF_writeCTable error \n");
+ goto _cleanup;
+ }
+ dstPtr += hhSize;
+ maxDstSize -= hhSize;
+ eSize += hhSize;
+ }
+
+ { size_t const ohSize = FSE_writeNCount(dstPtr, maxDstSize, offcodeNCount, OFFCODE_MAX, Offlog);
+ if (FSE_isError(ohSize)) {
+ eSize = ohSize;
+ DISPLAYLEVEL(1, "FSE_writeNCount error with offcodeNCount \n");
+ goto _cleanup;
+ }
+ dstPtr += ohSize;
+ maxDstSize -= ohSize;
+ eSize += ohSize;
+ }
+
+ { size_t const mhSize = FSE_writeNCount(dstPtr, maxDstSize, matchLengthNCount, MaxML, mlLog);
+ if (FSE_isError(mhSize)) {
+ eSize = mhSize;
+ DISPLAYLEVEL(1, "FSE_writeNCount error with matchLengthNCount \n");
+ goto _cleanup;
+ }
+ dstPtr += mhSize;
+ maxDstSize -= mhSize;
+ eSize += mhSize;
+ }
+
+ { size_t const lhSize = FSE_writeNCount(dstPtr, maxDstSize, litLengthNCount, MaxLL, llLog);
+ if (FSE_isError(lhSize)) {
+ eSize = lhSize;
+ DISPLAYLEVEL(1, "FSE_writeNCount error with litlengthNCount \n");
+ goto _cleanup;
+ }
+ dstPtr += lhSize;
+ maxDstSize -= lhSize;
+ eSize += lhSize;
+ }
+
+ if (maxDstSize<12) {
+ eSize = ERROR(dstSize_tooSmall);
+ DISPLAYLEVEL(1, "not enough space to write RepOffsets \n");
+ goto _cleanup;
+ }
+# if 0
+ MEM_writeLE32(dstPtr+0, bestRepOffset[0].offset);
+ MEM_writeLE32(dstPtr+4, bestRepOffset[1].offset);
+ MEM_writeLE32(dstPtr+8, bestRepOffset[2].offset);
+#else
+ /* at this stage, we don't use the result of "most common first offset",
+ as the impact of statistics is not properly evaluated */
+ MEM_writeLE32(dstPtr+0, repStartValue[0]);
+ MEM_writeLE32(dstPtr+4, repStartValue[1]);
+ MEM_writeLE32(dstPtr+8, repStartValue[2]);
+#endif
+ eSize += 12;
+
+_cleanup:
+ ZSTD_freeCDict(esr.dict);
+ ZSTD_freeCCtx(esr.zc);
+ free(esr.workPlace);
+
+ return eSize;
+}
+
+
+
+size_t ZDICT_finalizeDictionary(void* dictBuffer, size_t dictBufferCapacity,
+ const void* customDictContent, size_t dictContentSize,
+ const void* samplesBuffer, const size_t* samplesSizes,
+ unsigned nbSamples, ZDICT_params_t params)
+{
+ size_t hSize;
+#define HBUFFSIZE 256 /* should prove large enough for all entropy headers */
+ BYTE header[HBUFFSIZE];
+ int const compressionLevel = (params.compressionLevel == 0) ? ZSTD_CLEVEL_DEFAULT : params.compressionLevel;
+ U32 const notificationLevel = params.notificationLevel;
+
+ /* check conditions */
+ DEBUGLOG(4, "ZDICT_finalizeDictionary");
+ if (dictBufferCapacity < dictContentSize) return ERROR(dstSize_tooSmall);
+ if (dictContentSize < ZDICT_CONTENTSIZE_MIN) return ERROR(srcSize_wrong);
+ if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) return ERROR(dstSize_tooSmall);
+
+ /* dictionary header */
+ MEM_writeLE32(header, ZSTD_MAGIC_DICTIONARY);
+ { U64 const randomID = XXH64(customDictContent, dictContentSize, 0);
+ U32 const compliantID = (randomID % ((1U<<31)-32768)) + 32768;
+ U32 const dictID = params.dictID ? params.dictID : compliantID;
+ MEM_writeLE32(header+4, dictID);
+ }
+ hSize = 8;
+
+ /* entropy tables */
+ DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
+ DISPLAYLEVEL(2, "statistics ... \n");
+ { size_t const eSize = ZDICT_analyzeEntropy(header+hSize, HBUFFSIZE-hSize,
+ compressionLevel,
+ samplesBuffer, samplesSizes, nbSamples,
+ customDictContent, dictContentSize,
+ notificationLevel);
+ if (ZDICT_isError(eSize)) return eSize;
+ hSize += eSize;
+ }
+
+ /* copy elements in final buffer ; note : src and dst buffer can overlap */
+ if (hSize + dictContentSize > dictBufferCapacity) dictContentSize = dictBufferCapacity - hSize;
+ { size_t const dictSize = hSize + dictContentSize;
+ char* dictEnd = (char*)dictBuffer + dictSize;
+ memmove(dictEnd - dictContentSize, customDictContent, dictContentSize);
+ memcpy(dictBuffer, header, hSize);
+ return dictSize;
+ }
+}
+
+
+static size_t ZDICT_addEntropyTablesFromBuffer_advanced(
+ void* dictBuffer, size_t dictContentSize, size_t dictBufferCapacity,
+ const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
+ ZDICT_params_t params)
+{
+ int const compressionLevel = (params.compressionLevel == 0) ? ZSTD_CLEVEL_DEFAULT : params.compressionLevel;
+ U32 const notificationLevel = params.notificationLevel;
+ size_t hSize = 8;
+
+ /* calculate entropy tables */
+ DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */
+ DISPLAYLEVEL(2, "statistics ... \n");
+ { size_t const eSize = ZDICT_analyzeEntropy((char*)dictBuffer+hSize, dictBufferCapacity-hSize,
+ compressionLevel,
+ samplesBuffer, samplesSizes, nbSamples,
+ (char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize,
+ notificationLevel);
+ if (ZDICT_isError(eSize)) return eSize;
+ hSize += eSize;
+ }
+
+ /* add dictionary header (after entropy tables) */
+ MEM_writeLE32(dictBuffer, ZSTD_MAGIC_DICTIONARY);
+ { U64 const randomID = XXH64((char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize, 0);
+ U32 const compliantID = (randomID % ((1U<<31)-32768)) + 32768;
+ U32 const dictID = params.dictID ? params.dictID : compliantID;
+ MEM_writeLE32((char*)dictBuffer+4, dictID);
+ }
+
+ if (hSize + dictContentSize < dictBufferCapacity)
+ memmove((char*)dictBuffer + hSize, (char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize);
+ return MIN(dictBufferCapacity, hSize+dictContentSize);
+}
+
+/*! ZDICT_trainFromBuffer_unsafe_legacy() :
+* Warning : `samplesBuffer` must be followed by noisy guard band !!!
+* @return : size of dictionary, or an error code which can be tested with ZDICT_isError()
+*/
+static size_t ZDICT_trainFromBuffer_unsafe_legacy(
+ void* dictBuffer, size_t maxDictSize,
+ const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
+ ZDICT_legacy_params_t params)
+{
+ U32 const dictListSize = MAX(MAX(DICTLISTSIZE_DEFAULT, nbSamples), (U32)(maxDictSize/16));
+ dictItem* const dictList = (dictItem*)malloc(dictListSize * sizeof(*dictList));
+ unsigned const selectivity = params.selectivityLevel == 0 ? g_selectivity_default : params.selectivityLevel;
+ unsigned const minRep = (selectivity > 30) ? MINRATIO : nbSamples >> selectivity;
+ size_t const targetDictSize = maxDictSize;
+ size_t const samplesBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples);
+ size_t dictSize = 0;
+ U32 const notificationLevel = params.zParams.notificationLevel;
+
+ /* checks */
+ if (!dictList) return ERROR(memory_allocation);
+ if (maxDictSize < ZDICT_DICTSIZE_MIN) { free(dictList); return ERROR(dstSize_tooSmall); } /* requested dictionary size is too small */
+ if (samplesBuffSize < ZDICT_MIN_SAMPLES_SIZE) { free(dictList); return ERROR(dictionaryCreation_failed); } /* not enough source to create dictionary */
+
+ /* init */
+ ZDICT_initDictItem(dictList);
+
+ /* build dictionary */
+ ZDICT_trainBuffer_legacy(dictList, dictListSize,
+ samplesBuffer, samplesBuffSize,
+ samplesSizes, nbSamples,
+ minRep, notificationLevel);
+
+ /* display best matches */
+ if (params.zParams.notificationLevel>= 3) {
+ unsigned const nb = MIN(25, dictList[0].pos);
+ unsigned const dictContentSize = ZDICT_dictSize(dictList);
+ unsigned u;
+ DISPLAYLEVEL(3, "\n %u segments found, of total size %u \n", (unsigned)dictList[0].pos-1, dictContentSize);
+ DISPLAYLEVEL(3, "list %u best segments \n", nb-1);
+ for (u=1; u<nb; u++) {
+ unsigned const pos = dictList[u].pos;
+ unsigned const length = dictList[u].length;
+ U32 const printedLength = MIN(40, length);
+ if ((pos > samplesBuffSize) || ((pos + length) > samplesBuffSize)) {
+ free(dictList);
+ return ERROR(GENERIC); /* should never happen */
+ }
+ DISPLAYLEVEL(3, "%3u:%3u bytes at pos %8u, savings %7u bytes |",
+ u, length, pos, (unsigned)dictList[u].savings);
+ ZDICT_printHex((const char*)samplesBuffer+pos, printedLength);
+ DISPLAYLEVEL(3, "| \n");
+ } }
+
+
+ /* create dictionary */
+ { unsigned dictContentSize = ZDICT_dictSize(dictList);
+ if (dictContentSize < ZDICT_CONTENTSIZE_MIN) { free(dictList); return ERROR(dictionaryCreation_failed); } /* dictionary content too small */
+ if (dictContentSize < targetDictSize/4) {
+ DISPLAYLEVEL(2, "! warning : selected content significantly smaller than requested (%u < %u) \n", dictContentSize, (unsigned)maxDictSize);
+ if (samplesBuffSize < 10 * targetDictSize)
+ DISPLAYLEVEL(2, "! consider increasing the number of samples (total size : %u MB)\n", (unsigned)(samplesBuffSize>>20));
+ if (minRep > MINRATIO) {
+ DISPLAYLEVEL(2, "! consider increasing selectivity to produce larger dictionary (-s%u) \n", selectivity+1);
+ DISPLAYLEVEL(2, "! note : larger dictionaries are not necessarily better, test its efficiency on samples \n");
+ }
+ }
+
+ if ((dictContentSize > targetDictSize*3) && (nbSamples > 2*MINRATIO) && (selectivity>1)) {
+ unsigned proposedSelectivity = selectivity-1;
+ while ((nbSamples >> proposedSelectivity) <= MINRATIO) { proposedSelectivity--; }
+ DISPLAYLEVEL(2, "! note : calculated dictionary significantly larger than requested (%u > %u) \n", dictContentSize, (unsigned)maxDictSize);
+ DISPLAYLEVEL(2, "! consider increasing dictionary size, or produce denser dictionary (-s%u) \n", proposedSelectivity);
+ DISPLAYLEVEL(2, "! always test dictionary efficiency on real samples \n");
+ }
+
+ /* limit dictionary size */
+ { U32 const max = dictList->pos; /* convention : nb of useful elts within dictList */
+ U32 currentSize = 0;
+ U32 n; for (n=1; n<max; n++) {
+ currentSize += dictList[n].length;
+ if (currentSize > targetDictSize) { currentSize -= dictList[n].length; break; }
+ }
+ dictList->pos = n;
+ dictContentSize = currentSize;
+ }
+
+ /* build dict content */
+ { U32 u;
+ BYTE* ptr = (BYTE*)dictBuffer + maxDictSize;
+ for (u=1; u<dictList->pos; u++) {
+ U32 l = dictList[u].length;
+ ptr -= l;
+ if (ptr<(BYTE*)dictBuffer) { free(dictList); return ERROR(GENERIC); } /* should not happen */
+ memcpy(ptr, (const char*)samplesBuffer+dictList[u].pos, l);
+ } }
+
+ dictSize = ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, maxDictSize,
+ samplesBuffer, samplesSizes, nbSamples,
+ params.zParams);
+ }
+
+ /* clean up */
+ free(dictList);
+ return dictSize;
+}
+
+
+/* ZDICT_trainFromBuffer_legacy() :
+ * issue : samplesBuffer need to be followed by a noisy guard band.
+ * work around : duplicate the buffer, and add the noise */
+size_t ZDICT_trainFromBuffer_legacy(void* dictBuffer, size_t dictBufferCapacity,
+ const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
+ ZDICT_legacy_params_t params)
+{
+ size_t result;
+ void* newBuff;
+ size_t const sBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples);
+ if (sBuffSize < ZDICT_MIN_SAMPLES_SIZE) return 0; /* not enough content => no dictionary */
+
+ newBuff = malloc(sBuffSize + NOISELENGTH);
+ if (!newBuff) return ERROR(memory_allocation);
+
+ memcpy(newBuff, samplesBuffer, sBuffSize);
+ ZDICT_fillNoise((char*)newBuff + sBuffSize, NOISELENGTH); /* guard band, for end of buffer condition */
+
+ result =
+ ZDICT_trainFromBuffer_unsafe_legacy(dictBuffer, dictBufferCapacity, newBuff,
+ samplesSizes, nbSamples, params);
+ free(newBuff);
+ return result;
+}
+
+
+size_t ZDICT_trainFromBuffer(void* dictBuffer, size_t dictBufferCapacity,
+ const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples)
+{
+ ZDICT_fastCover_params_t params;
+ DEBUGLOG(3, "ZDICT_trainFromBuffer");
+ memset(&params, 0, sizeof(params));
+ params.d = 8;
+ params.steps = 4;
+ /* Use default level since no compression level information is available */
+ params.zParams.compressionLevel = ZSTD_CLEVEL_DEFAULT;
+#if defined(DEBUGLEVEL) && (DEBUGLEVEL>=1)
+ params.zParams.notificationLevel = DEBUGLEVEL;
+#endif
+ return ZDICT_optimizeTrainFromBuffer_fastCover(dictBuffer, dictBufferCapacity,
+ samplesBuffer, samplesSizes, nbSamples,
+ &params);
+}
+
+size_t ZDICT_addEntropyTablesFromBuffer(void* dictBuffer, size_t dictContentSize, size_t dictBufferCapacity,
+ const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples)
+{
+ ZDICT_params_t params;
+ memset(&params, 0, sizeof(params));
+ return ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, dictBufferCapacity,
+ samplesBuffer, samplesSizes, nbSamples,
+ params);
+}
diff --git a/zstd/zdict.h b/zstd/zdict.h
new file mode 100644
index 00000000..75b05dbf
--- /dev/null
+++ b/zstd/zdict.h
@@ -0,0 +1,452 @@
+/*
+ * Copyright (c) Yann Collet, Facebook, Inc.
+ * All rights reserved.
+ *
+ * This source code is licensed under both the BSD-style license (found in the
+ * LICENSE file in the root directory of this source tree) and the GPLv2 (found
+ * in the COPYING file in the root directory of this source tree).
+ * You may select, at your option, one of the above-listed licenses.
+ */
+
+#ifndef DICTBUILDER_H_001
+#define DICTBUILDER_H_001
+
+#if defined (__cplusplus)
+extern "C" {
+#endif
+
+
+/*====== Dependencies ======*/
+#include <stddef.h> /* size_t */
+
+
+/* ===== ZDICTLIB_API : control library symbols visibility ===== */
+#ifndef ZDICTLIB_VISIBILITY
+# if defined(__GNUC__) && (__GNUC__ >= 4)
+# define ZDICTLIB_VISIBILITY __attribute__ ((visibility ("default")))
+# else
+# define ZDICTLIB_VISIBILITY
+# endif
+#endif
+#if defined(ZSTD_DLL_EXPORT) && (ZSTD_DLL_EXPORT==1)
+# define ZDICTLIB_API __declspec(dllexport) ZDICTLIB_VISIBILITY
+#elif defined(ZSTD_DLL_IMPORT) && (ZSTD_DLL_IMPORT==1)
+# define ZDICTLIB_API __declspec(dllimport) ZDICTLIB_VISIBILITY /* It isn't required but allows to generate better code, saving a function pointer load from the IAT and an indirect jump.*/
+#else
+# define ZDICTLIB_API ZDICTLIB_VISIBILITY
+#endif
+
+/*******************************************************************************
+ * Zstd dictionary builder
+ *
+ * FAQ
+ * ===
+ * Why should I use a dictionary?
+ * ------------------------------
+ *
+ * Zstd can use dictionaries to improve compression ratio of small data.
+ * Traditionally small files don't compress well because there is very little
+ * repetion in a single sample, since it is small. But, if you are compressing
+ * many similar files, like a bunch of JSON records that share the same
+ * structure, you can train a dictionary on ahead of time on some samples of
+ * these files. Then, zstd can use the dictionary to find repetitions that are
+ * present across samples. This can vastly improve compression ratio.
+ *
+ * When is a dictionary useful?
+ * ----------------------------
+ *
+ * Dictionaries are useful when compressing many small files that are similar.
+ * The larger a file is, the less benefit a dictionary will have. Generally,
+ * we don't expect dictionary compression to be effective past 100KB. And the
+ * smaller a file is, the more we would expect the dictionary to help.
+ *
+ * How do I use a dictionary?
+ * --------------------------
+ *
+ * Simply pass the dictionary to the zstd compressor with
+ * `ZSTD_CCtx_loadDictionary()`. The same dictionary must then be passed to
+ * the decompressor, using `ZSTD_DCtx_loadDictionary()`. There are other
+ * more advanced functions that allow selecting some options, see zstd.h for
+ * complete documentation.
+ *
+ * What is a zstd dictionary?
+ * --------------------------
+ *
+ * A zstd dictionary has two pieces: Its header, and its content. The header
+ * contains a magic number, the dictionary ID, and entropy tables. These
+ * entropy tables allow zstd to save on header costs in the compressed file,
+ * which really matters for small data. The content is just bytes, which are
+ * repeated content that is common across many samples.
+ *
+ * What is a raw content dictionary?
+ * ---------------------------------
+ *
+ * A raw content dictionary is just bytes. It doesn't have a zstd dictionary
+ * header, a dictionary ID, or entropy tables. Any buffer is a valid raw
+ * content dictionary.
+ *
+ * How do I train a dictionary?
+ * ----------------------------
+ *
+ * Gather samples from your use case. These samples should be similar to each
+ * other. If you have several use cases, you could try to train one dictionary
+ * per use case.
+ *
+ * Pass those samples to `ZDICT_trainFromBuffer()` and that will train your
+ * dictionary. There are a few advanced versions of this function, but this
+ * is a great starting point. If you want to further tune your dictionary
+ * you could try `ZDICT_optimizeTrainFromBuffer_cover()`. If that is too slow
+ * you can try `ZDICT_optimizeTrainFromBuffer_fastCover()`.
+ *
+ * If the dictionary training function fails, that is likely because you
+ * either passed too few samples, or a dictionary would not be effective
+ * for your data. Look at the messages that the dictionary trainer printed,
+ * if it doesn't say too few samples, then a dictionary would not be effective.
+ *
+ * How large should my dictionary be?
+ * ----------------------------------
+ *
+ * A reasonable dictionary size, the `dictBufferCapacity`, is about 100KB.
+ * The zstd CLI defaults to a 110KB dictionary. You likely don't need a
+ * dictionary larger than that. But, most use cases can get away with a
+ * smaller dictionary. The advanced dictionary builders can automatically
+ * shrink the dictionary for you, and select a the smallest size that
+ * doesn't hurt compression ratio too much. See the `shrinkDict` parameter.
+ * A smaller dictionary can save memory, and potentially speed up
+ * compression.
+ *
+ * How many samples should I provide to the dictionary builder?
+ * ------------------------------------------------------------
+ *
+ * We generally recommend passing ~100x the size of the dictionary
+ * in samples. A few thousand should suffice. Having too few samples
+ * can hurt the dictionaries effectiveness. Having more samples will
+ * only improve the dictionaries effectiveness. But having too many
+ * samples can slow down the dictionary builder.
+ *
+ * How do I determine if a dictionary will be effective?
+ * -----------------------------------------------------
+ *
+ * Simply train a dictionary and try it out. You can use zstd's built in
+ * benchmarking tool to test the dictionary effectiveness.
+ *
+ * # Benchmark levels 1-3 without a dictionary
+ * zstd -b1e3 -r /path/to/my/files
+ * # Benchmark levels 1-3 with a dictioanry
+ * zstd -b1e3 -r /path/to/my/files -D /path/to/my/dictionary
+ *
+ * When should I retrain a dictionary?
+ * -----------------------------------
+ *
+ * You should retrain a dictionary when its effectiveness drops. Dictionary
+ * effectiveness drops as the data you are compressing changes. Generally, we do
+ * expect dictionaries to "decay" over time, as your data changes, but the rate
+ * at which they decay depends on your use case. Internally, we regularly
+ * retrain dictionaries, and if the new dictionary performs significantly
+ * better than the old dictionary, we will ship the new dictionary.
+ *
+ * I have a raw content dictionary, how do I turn it into a zstd dictionary?
+ * -------------------------------------------------------------------------
+ *
+ * If you have a raw content dictionary, e.g. by manually constructing it, or
+ * using a third-party dictionary builder, you can turn it into a zstd
+ * dictionary by using `ZDICT_finalizeDictionary()`. You'll also have to
+ * provide some samples of the data. It will add the zstd header to the
+ * raw content, which contains a dictionary ID and entropy tables, which
+ * will improve compression ratio, and allow zstd to write the dictionary ID
+ * into the frame, if you so choose.
+ *
+ * Do I have to use zstd's dictionary builder?
+ * -------------------------------------------
+ *
+ * No! You can construct dictionary content however you please, it is just
+ * bytes. It will always be valid as a raw content dictionary. If you want
+ * a zstd dictionary, which can improve compression ratio, use
+ * `ZDICT_finalizeDictionary()`.
+ *
+ * What is the attack surface of a zstd dictionary?
+ * ------------------------------------------------
+ *
+ * Zstd is heavily fuzz tested, including loading fuzzed dictionaries, so
+ * zstd should never crash, or access out-of-bounds memory no matter what
+ * the dictionary is. However, if an attacker can control the dictionary
+ * during decompression, they can cause zstd to generate arbitrary bytes,
+ * just like if they controlled the compressed data.
+ *
+ ******************************************************************************/
+
+
+/*! ZDICT_trainFromBuffer():
+ * Train a dictionary from an array of samples.
+ * Redirect towards ZDICT_optimizeTrainFromBuffer_fastCover() single-threaded, with d=8, steps=4,
+ * f=20, and accel=1.
+ * Samples must be stored concatenated in a single flat buffer `samplesBuffer`,
+ * supplied with an array of sizes `samplesSizes`, providing the size of each sample, in order.
+ * The resulting dictionary will be saved into `dictBuffer`.
+ * @return: size of dictionary stored into `dictBuffer` (<= `dictBufferCapacity`)
+ * or an error code, which can be tested with ZDICT_isError().
+ * Note: Dictionary training will fail if there are not enough samples to construct a
+ * dictionary, or if most of the samples are too small (< 8 bytes being the lower limit).
+ * If dictionary training fails, you should use zstd without a dictionary, as the dictionary
+ * would've been ineffective anyways. If you believe your samples would benefit from a dictionary
+ * please open an issue with details, and we can look into it.
+ * Note: ZDICT_trainFromBuffer()'s memory usage is about 6 MB.
+ * Tips: In general, a reasonable dictionary has a size of ~ 100 KB.
+ * It's possible to select smaller or larger size, just by specifying `dictBufferCapacity`.
+ * In general, it's recommended to provide a few thousands samples, though this can vary a lot.
+ * It's recommended that total size of all samples be about ~x100 times the target size of dictionary.
+ */
+ZDICTLIB_API size_t ZDICT_trainFromBuffer(void* dictBuffer, size_t dictBufferCapacity,
+ const void* samplesBuffer,
+ const size_t* samplesSizes, unsigned nbSamples);
+
+typedef struct {
+ int compressionLevel; /*< optimize for a specific zstd compression level; 0 means default */
+ unsigned notificationLevel; /*< Write log to stderr; 0 = none (default); 1 = errors; 2 = progression; 3 = details; 4 = debug; */
+ unsigned dictID; /*< force dictID value; 0 means auto mode (32-bits random value)
+ * NOTE: The zstd format reserves some dictionary IDs for future use.
+ * You may use them in private settings, but be warned that they
+ * may be used by zstd in a public dictionary registry in the future.
+ * These dictionary IDs are:
+ * - low range : <= 32767
+ * - high range : >= (2^31)
+ */
+} ZDICT_params_t;
+
+/*! ZDICT_finalizeDictionary():
+ * Given a custom content as a basis for dictionary, and a set of samples,
+ * finalize dictionary by adding headers and statistics according to the zstd
+ * dictionary format.
+ *
+ * Samples must be stored concatenated in a flat buffer `samplesBuffer`,
+ * supplied with an array of sizes `samplesSizes`, providing the size of each
+ * sample in order. The samples are used to construct the statistics, so they
+ * should be representative of what you will compress with this dictionary.
+ *
+ * The compression level can be set in `parameters`. You should pass the
+ * compression level you expect to use in production. The statistics for each
+ * compression level differ, so tuning the dictionary for the compression level
+ * can help quite a bit.
+ *
+ * You can set an explicit dictionary ID in `parameters`, or allow us to pick
+ * a random dictionary ID for you, but we can't guarantee no collisions.
+ *
+ * The dstDictBuffer and the dictContent may overlap, and the content will be
+ * appended to the end of the header. If the header + the content doesn't fit in
+ * maxDictSize the beginning of the content is truncated to make room, since it
+ * is presumed that the most profitable content is at the end of the dictionary,
+ * since that is the cheapest to reference.
+ *
+ * `dictContentSize` must be >= ZDICT_CONTENTSIZE_MIN bytes.
+ * `maxDictSize` must be >= max(dictContentSize, ZSTD_DICTSIZE_MIN).
+ *
+ * @return: size of dictionary stored into `dstDictBuffer` (<= `maxDictSize`),
+ * or an error code, which can be tested by ZDICT_isError().
+ * Note: ZDICT_finalizeDictionary() will push notifications into stderr if
+ * instructed to, using notificationLevel>0.
+ * NOTE: This function currently may fail in several edge cases including:
+ * * Not enough samples
+ * * Samples are uncompressible
+ * * Samples are all exactly the same
+ */
+ZDICTLIB_API size_t ZDICT_finalizeDictionary(void* dstDictBuffer, size_t maxDictSize,
+ const void* dictContent, size_t dictContentSize,
+ const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
+ ZDICT_params_t parameters);
+
+
+/*====== Helper functions ======*/
+ZDICTLIB_API unsigned ZDICT_getDictID(const void* dictBuffer, size_t dictSize); /**< extracts dictID; @return zero if error (not a valid dictionary) */
+ZDICTLIB_API size_t ZDICT_getDictHeaderSize(const void* dictBuffer, size_t dictSize); /* returns dict header size; returns a ZSTD error code on failure */
+ZDICTLIB_API unsigned ZDICT_isError(size_t errorCode);
+ZDICTLIB_API const char* ZDICT_getErrorName(size_t errorCode);
+
+
+
+#ifdef ZDICT_STATIC_LINKING_ONLY
+
+/* ====================================================================================
+ * The definitions in this section are considered experimental.
+ * They should never be used with a dynamic library, as they may change in the future.
+ * They are provided for advanced usages.
+ * Use them only in association with static linking.
+ * ==================================================================================== */
+
+#define ZDICT_CONTENTSIZE_MIN 128
+#define ZDICT_DICTSIZE_MIN 256
+
+/*! ZDICT_cover_params_t:
+ * k and d are the only required parameters.
+ * For others, value 0 means default.
+ */
+typedef struct {
+ unsigned k; /* Segment size : constraint: 0 < k : Reasonable range [16, 2048+] */
+ unsigned d; /* dmer size : constraint: 0 < d <= k : Reasonable range [6, 16] */
+ unsigned steps; /* Number of steps : Only used for optimization : 0 means default (40) : Higher means more parameters checked */
+ unsigned nbThreads; /* Number of threads : constraint: 0 < nbThreads : 1 means single-threaded : Only used for optimization : Ignored if ZSTD_MULTITHREAD is not defined */
+ double splitPoint; /* Percentage of samples used for training: Only used for optimization : the first nbSamples * splitPoint samples will be used to training, the last nbSamples * (1 - splitPoint) samples will be used for testing, 0 means default (1.0), 1.0 when all samples are used for both training and testing */
+ unsigned shrinkDict; /* Train dictionaries to shrink in size starting from the minimum size and selects the smallest dictionary that is shrinkDictMaxRegression% worse than the largest dictionary. 0 means no shrinking and 1 means shrinking */
+ unsigned shrinkDictMaxRegression; /* Sets shrinkDictMaxRegression so that a smaller dictionary can be at worse shrinkDictMaxRegression% worse than the max dict size dictionary. */
+ ZDICT_params_t zParams;
+} ZDICT_cover_params_t;
+
+typedef struct {
+ unsigned k; /* Segment size : constraint: 0 < k : Reasonable range [16, 2048+] */
+ unsigned d; /* dmer size : constraint: 0 < d <= k : Reasonable range [6, 16] */
+ unsigned f; /* log of size of frequency array : constraint: 0 < f <= 31 : 1 means default(20)*/
+ unsigned steps; /* Number of steps : Only used for optimization : 0 means default (40) : Higher means more parameters checked */
+ unsigned nbThreads; /* Number of threads : constraint: 0 < nbThreads : 1 means single-threaded : Only used for optimization : Ignored if ZSTD_MULTITHREAD is not defined */
+ double splitPoint; /* Percentage of samples used for training: Only used for optimization : the first nbSamples * splitPoint samples will be used to training, the last nbSamples * (1 - splitPoint) samples will be used for testing, 0 means default (0.75), 1.0 when all samples are used for both training and testing */
+ unsigned accel; /* Acceleration level: constraint: 0 < accel <= 10, higher means faster and less accurate, 0 means default(1) */
+ unsigned shrinkDict; /* Train dictionaries to shrink in size starting from the minimum size and selects the smallest dictionary that is shrinkDictMaxRegression% worse than the largest dictionary. 0 means no shrinking and 1 means shrinking */
+ unsigned shrinkDictMaxRegression; /* Sets shrinkDictMaxRegression so that a smaller dictionary can be at worse shrinkDictMaxRegression% worse than the max dict size dictionary. */
+
+ ZDICT_params_t zParams;
+} ZDICT_fastCover_params_t;
+
+/*! ZDICT_trainFromBuffer_cover():
+ * Train a dictionary from an array of samples using the COVER algorithm.
+ * Samples must be stored concatenated in a single flat buffer `samplesBuffer`,
+ * supplied with an array of sizes `samplesSizes`, providing the size of each sample, in order.
+ * The resulting dictionary will be saved into `dictBuffer`.
+ * @return: size of dictionary stored into `dictBuffer` (<= `dictBufferCapacity`)
+ * or an error code, which can be tested with ZDICT_isError().
+ * See ZDICT_trainFromBuffer() for details on failure modes.
+ * Note: ZDICT_trainFromBuffer_cover() requires about 9 bytes of memory for each input byte.
+ * Tips: In general, a reasonable dictionary has a size of ~ 100 KB.
+ * It's possible to select smaller or larger size, just by specifying `dictBufferCapacity`.
+ * In general, it's recommended to provide a few thousands samples, though this can vary a lot.
+ * It's recommended that total size of all samples be about ~x100 times the target size of dictionary.
+ */
+ZDICTLIB_API size_t ZDICT_trainFromBuffer_cover(
+ void *dictBuffer, size_t dictBufferCapacity,
+ const void *samplesBuffer, const size_t *samplesSizes, unsigned nbSamples,
+ ZDICT_cover_params_t parameters);
+
+/*! ZDICT_optimizeTrainFromBuffer_cover():
+ * The same requirements as above hold for all the parameters except `parameters`.
+ * This function tries many parameter combinations and picks the best parameters.
+ * `*parameters` is filled with the best parameters found,
+ * dictionary constructed with those parameters is stored in `dictBuffer`.
+ *
+ * All of the parameters d, k, steps are optional.
+ * If d is non-zero then we don't check multiple values of d, otherwise we check d = {6, 8}.
+ * if steps is zero it defaults to its default value.
+ * If k is non-zero then we don't check multiple values of k, otherwise we check steps values in [50, 2000].
+ *
+ * @return: size of dictionary stored into `dictBuffer` (<= `dictBufferCapacity`)
+ * or an error code, which can be tested with ZDICT_isError().
+ * On success `*parameters` contains the parameters selected.
+ * See ZDICT_trainFromBuffer() for details on failure modes.
+ * Note: ZDICT_optimizeTrainFromBuffer_cover() requires about 8 bytes of memory for each input byte and additionally another 5 bytes of memory for each byte of memory for each thread.
+ */
+ZDICTLIB_API size_t ZDICT_optimizeTrainFromBuffer_cover(
+ void* dictBuffer, size_t dictBufferCapacity,
+ const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
+ ZDICT_cover_params_t* parameters);
+
+/*! ZDICT_trainFromBuffer_fastCover():
+ * Train a dictionary from an array of samples using a modified version of COVER algorithm.
+ * Samples must be stored concatenated in a single flat buffer `samplesBuffer`,
+ * supplied with an array of sizes `samplesSizes`, providing the size of each sample, in order.
+ * d and k are required.
+ * All other parameters are optional, will use default values if not provided
+ * The resulting dictionary will be saved into `dictBuffer`.
+ * @return: size of dictionary stored into `dictBuffer` (<= `dictBufferCapacity`)
+ * or an error code, which can be tested with ZDICT_isError().
+ * See ZDICT_trainFromBuffer() for details on failure modes.
+ * Note: ZDICT_trainFromBuffer_fastCover() requires 6 * 2^f bytes of memory.
+ * Tips: In general, a reasonable dictionary has a size of ~ 100 KB.
+ * It's possible to select smaller or larger size, just by specifying `dictBufferCapacity`.
+ * In general, it's recommended to provide a few thousands samples, though this can vary a lot.
+ * It's recommended that total size of all samples be about ~x100 times the target size of dictionary.
+ */
+ZDICTLIB_API size_t ZDICT_trainFromBuffer_fastCover(void *dictBuffer,
+ size_t dictBufferCapacity, const void *samplesBuffer,
+ const size_t *samplesSizes, unsigned nbSamples,
+ ZDICT_fastCover_params_t parameters);
+
+/*! ZDICT_optimizeTrainFromBuffer_fastCover():
+ * The same requirements as above hold for all the parameters except `parameters`.
+ * This function tries many parameter combinations (specifically, k and d combinations)
+ * and picks the best parameters. `*parameters` is filled with the best parameters found,
+ * dictionary constructed with those parameters is stored in `dictBuffer`.
+ * All of the parameters d, k, steps, f, and accel are optional.
+ * If d is non-zero then we don't check multiple values of d, otherwise we check d = {6, 8}.
+ * if steps is zero it defaults to its default value.
+ * If k is non-zero then we don't check multiple values of k, otherwise we check steps values in [50, 2000].
+ * If f is zero, default value of 20 is used.
+ * If accel is zero, default value of 1 is used.
+ *
+ * @return: size of dictionary stored into `dictBuffer` (<= `dictBufferCapacity`)
+ * or an error code, which can be tested with ZDICT_isError().
+ * On success `*parameters` contains the parameters selected.
+ * See ZDICT_trainFromBuffer() for details on failure modes.
+ * Note: ZDICT_optimizeTrainFromBuffer_fastCover() requires about 6 * 2^f bytes of memory for each thread.
+ */
+ZDICTLIB_API size_t ZDICT_optimizeTrainFromBuffer_fastCover(void* dictBuffer,
+ size_t dictBufferCapacity, const void* samplesBuffer,
+ const size_t* samplesSizes, unsigned nbSamples,
+ ZDICT_fastCover_params_t* parameters);
+
+typedef struct {
+ unsigned selectivityLevel; /* 0 means default; larger => select more => larger dictionary */
+ ZDICT_params_t zParams;
+} ZDICT_legacy_params_t;
+
+/*! ZDICT_trainFromBuffer_legacy():
+ * Train a dictionary from an array of samples.
+ * Samples must be stored concatenated in a single flat buffer `samplesBuffer`,
+ * supplied with an array of sizes `samplesSizes`, providing the size of each sample, in order.
+ * The resulting dictionary will be saved into `dictBuffer`.
+ * `parameters` is optional and can be provided with values set to 0 to mean "default".
+ * @return: size of dictionary stored into `dictBuffer` (<= `dictBufferCapacity`)
+ * or an error code, which can be tested with ZDICT_isError().
+ * See ZDICT_trainFromBuffer() for details on failure modes.
+ * Tips: In general, a reasonable dictionary has a size of ~ 100 KB.
+ * It's possible to select smaller or larger size, just by specifying `dictBufferCapacity`.
+ * In general, it's recommended to provide a few thousands samples, though this can vary a lot.
+ * It's recommended that total size of all samples be about ~x100 times the target size of dictionary.
+ * Note: ZDICT_trainFromBuffer_legacy() will send notifications into stderr if instructed to, using notificationLevel>0.
+ */
+ZDICTLIB_API size_t ZDICT_trainFromBuffer_legacy(
+ void* dictBuffer, size_t dictBufferCapacity,
+ const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples,
+ ZDICT_legacy_params_t parameters);
+
+
+/* Deprecation warnings */
+/* It is generally possible to disable deprecation warnings from compiler,
+ for example with -Wno-deprecated-declarations for gcc
+ or _CRT_SECURE_NO_WARNINGS in Visual.
+ Otherwise, it's also possible to manually define ZDICT_DISABLE_DEPRECATE_WARNINGS */
+#ifdef ZDICT_DISABLE_DEPRECATE_WARNINGS
+# define ZDICT_DEPRECATED(message) ZDICTLIB_API /* disable deprecation warnings */
+#else
+# define ZDICT_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
+# if defined (__cplusplus) && (__cplusplus >= 201402) /* C++14 or greater */
+# define ZDICT_DEPRECATED(message) [[deprecated(message)]] ZDICTLIB_API
+# elif defined(__clang__) || (ZDICT_GCC_VERSION >= 405)
+# define ZDICT_DEPRECATED(message) ZDICTLIB_API __attribute__((deprecated(message)))
+# elif (ZDICT_GCC_VERSION >= 301)
+# define ZDICT_DEPRECATED(message) ZDICTLIB_API __attribute__((deprecated))
+# elif defined(_MSC_VER)
+# define ZDICT_DEPRECATED(message) ZDICTLIB_API __declspec(deprecated(message))
+# else
+# pragma message("WARNING: You need to implement ZDICT_DEPRECATED for this compiler")
+# define ZDICT_DEPRECATED(message) ZDICTLIB_API
+# endif
+#endif /* ZDICT_DISABLE_DEPRECATE_WARNINGS */
+
+ZDICT_DEPRECATED("use ZDICT_finalizeDictionary() instead")
+size_t ZDICT_addEntropyTablesFromBuffer(void* dictBuffer, size_t dictContentSize, size_t dictBufferCapacity,
+ const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples);
+
+
+#endif /* ZDICT_STATIC_LINKING_ONLY */
+
+#if defined (__cplusplus)
+}
+#endif
+
+#endif /* DICTBUILDER_H_001 */
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-17 19:43:30 +0300