contrib/zstd/lib/dictBuilder/cover.c in extzstd-0.1.1 vs contrib/zstd/lib/dictBuilder/cover.c in extzstd-0.2
- old
+ new
@@ -1,12 +1,13 @@
-/**
+/*
* Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
* All rights reserved.
*
- * This source code is licensed under the BSD-style license found in the
- * LICENSE file in the root directory of this source tree. An additional grant
- * of patent rights can be found in the PATENTS file in the same directory.
+ * 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:
*
@@ -57,12 +58,10 @@
#define LOCALDISPLAYUPDATE(displayLevel, l, ...) \
if (displayLevel >= l) { \
if ((clock() - g_time > refreshRate) || (displayLevel >= 4)) { \
g_time = clock(); \
DISPLAY(__VA_ARGS__); \
- if (displayLevel >= 4) \
- fflush(stdout); \
} \
}
#define DISPLAYUPDATE(l, ...) LOCALDISPLAYUPDATE(g_displayLevel, l, __VA_ARGS__)
static const clock_t refreshRate = CLOCKS_PER_SEC * 15 / 100;
static clock_t g_time = 0;
@@ -234,14 +233,26 @@
* 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) {
- const U32 lhs = *(const U32 *)lp;
- const U32 rhs = *(const U32 *)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_ctx must be set to call this function. A global is required because
* qsort doesn't take an opaque pointer.
@@ -251,10 +262,20 @@
if (result == 0) {
result = lp < rp ? -1 : 1;
}
return result;
}
+/**
+ * Faster version for d <= 8.
+ */
+static int COVER_strict_cmp8(const void *lp, const void *rp) {
+ int result = COVER_cmp8(g_ctx, 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.
*/
@@ -360,11 +381,11 @@
* A segment is a range in the source as well as the score of the segment.
*/
typedef struct {
U32 begin;
U32 end;
- double score;
+ U32 score;
} COVER_segment_t;
/**
* Selects the best segment in an epoch.
* Segments of are scored according to the function:
@@ -376,11 +397,12 @@
*
* Once the dmer d is in the dictionay 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, COVER_params_t parameters) {
+ 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) */
@@ -456,15 +478,20 @@
/**
* Check the validity of the parameters.
* Returns non-zero if the parameters are valid and 0 otherwise.
*/
-static int COVER_checkParameters(COVER_params_t parameters) {
+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;
}
return 1;
@@ -506,11 +533,11 @@
const size_t *samplesSizes, unsigned nbSamples,
unsigned d) {
const BYTE *const samples = (const BYTE *)samplesBuffer;
const size_t totalSamplesSize = COVER_sum(samplesSizes, nbSamples);
/* Checks */
- if (totalSamplesSize < d ||
+ if (totalSamplesSize < MAX(d, sizeof(U64)) ||
totalSamplesSize >= (size_t)COVER_MAX_SAMPLES_SIZE) {
DISPLAYLEVEL(1, "Total samples size is too large, maximum size is %u MB\n",
(COVER_MAX_SAMPLES_SIZE >> 20));
return 0;
}
@@ -520,11 +547,11 @@
(U32)totalSamplesSize);
ctx->samples = samples;
ctx->samplesSizes = samplesSizes;
ctx->nbSamples = nbSamples;
/* Partial suffix array */
- ctx->suffixSize = totalSamplesSize - d + 1;
+ ctx->suffixSize = totalSamplesSize - 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));
@@ -554,22 +581,23 @@
for (i = 0; i < ctx->suffixSize; ++i) {
ctx->suffix[i] = i;
}
/* qsort doesn't take an opaque pointer, so pass as a global */
g_ctx = ctx;
- qsort(ctx->suffix, ctx->suffixSize, sizeof(U32), &COVER_strict_cmp);
+ qsort(ctx->suffix, ctx->suffixSize, sizeof(U32),
+ (ctx->d <= 8 ? &COVER_strict_cmp8 : &COVER_strict_cmp));
}
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, &COVER_cmp,
- &COVER_group);
+ 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 1;
}
@@ -577,11 +605,11 @@
* 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,
- COVER_params_t parameters) {
+ ZDICT_cover_params_t parameters) {
BYTE *const dict = (BYTE *)dictBuffer;
size_t tail = dictBufferCapacity;
/* Divide the data up into epochs of equal size.
* We will select at least one segment from each epoch.
*/
@@ -598,13 +626,17 @@
const U32 epochEnd = epochBegin + epochSize;
size_t segmentSize;
/* Select a segment */
COVER_segment_t segment = COVER_selectSegment(
ctx, freqs, activeDmers, epochBegin, epochEnd, parameters);
- /* Trim the segment if necessary and if it is empty then we are done */
+ /* If the segment covers no dmers, then we are out of content */
+ if (segment.score == 0) {
+ break;
+ }
+ /* 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 == 0) {
+ if (segmentSize < parameters.d) {
break;
}
/* We fill the dictionary from the back to allow the best segments to be
* referenced with the smallest offsets.
*/
@@ -616,31 +648,19 @@
}
DISPLAYLEVEL(2, "\r%79s\r", "");
return tail;
}
-/**
- * Translate from COVER_params_t to ZDICT_params_t required for finalizing the
- * dictionary.
- */
-static ZDICT_params_t COVER_translateParams(COVER_params_t parameters) {
- ZDICT_params_t zdictParams;
- memset(&zdictParams, 0, sizeof(zdictParams));
- zdictParams.notificationLevel = 1;
- zdictParams.dictID = parameters.dictID;
- zdictParams.compressionLevel = parameters.compressionLevel;
- return zdictParams;
-}
-
-ZDICTLIB_API size_t COVER_trainFromBuffer(
+ZDICTLIB_API size_t ZDICT_trainFromBuffer_cover(
void *dictBuffer, size_t dictBufferCapacity, const void *samplesBuffer,
- const size_t *samplesSizes, unsigned nbSamples, COVER_params_t parameters) {
+ const size_t *samplesSizes, unsigned nbSamples,
+ ZDICT_cover_params_t parameters) {
BYTE *const dict = (BYTE *)dictBuffer;
COVER_ctx_t ctx;
COVER_map_t activeDmers;
/* Checks */
- if (!COVER_checkParameters(parameters)) {
+ if (!COVER_checkParameters(parameters, dictBufferCapacity)) {
DISPLAYLEVEL(1, "Cover parameters incorrect\n");
return ERROR(GENERIC);
}
if (nbSamples == 0) {
DISPLAYLEVEL(1, "Cover must have at least one input file\n");
@@ -650,11 +670,11 @@
DISPLAYLEVEL(1, "dictBufferCapacity must be at least %u\n",
ZDICT_DICTSIZE_MIN);
return ERROR(dstSize_tooSmall);
}
/* Initialize global data */
- g_displayLevel = parameters.notificationLevel;
+ g_displayLevel = parameters.zParams.notificationLevel;
/* Initialize context and activeDmers */
if (!COVER_ctx_init(&ctx, samplesBuffer, samplesSizes, nbSamples,
parameters.d)) {
return ERROR(GENERIC);
}
@@ -667,14 +687,13 @@
DISPLAYLEVEL(2, "Building dictionary\n");
{
const size_t tail =
COVER_buildDictionary(&ctx, ctx.freqs, &activeDmers, dictBuffer,
dictBufferCapacity, parameters);
- ZDICT_params_t zdictParams = COVER_translateParams(parameters);
const size_t dictionarySize = ZDICT_finalizeDictionary(
dict, dictBufferCapacity, dict + tail, dictBufferCapacity - tail,
- samplesBuffer, samplesSizes, nbSamples, zdictParams);
+ samplesBuffer, samplesSizes, nbSamples, parameters.zParams);
if (!ZSTD_isError(dictionarySize)) {
DISPLAYLEVEL(2, "Constructed dictionary of size %u\n",
(U32)dictionarySize);
}
COVER_ctx_destroy(&ctx);
@@ -690,28 +709,26 @@
*
* All of the methods except COVER_best_init() are thread safe if zstd is
* compiled with multithreaded support.
*/
typedef struct COVER_best_s {
- pthread_mutex_t mutex;
- pthread_cond_t cond;
+ ZSTD_pthread_mutex_t mutex;
+ ZSTD_pthread_cond_t cond;
size_t liveJobs;
void *dict;
size_t dictSize;
- COVER_params_t parameters;
+ ZDICT_cover_params_t parameters;
size_t compressedSize;
} COVER_best_t;
/**
* Initialize the `COVER_best_t`.
*/
static void COVER_best_init(COVER_best_t *best) {
- if (!best) {
- return;
- }
- pthread_mutex_init(&best->mutex, NULL);
- pthread_cond_init(&best->cond, NULL);
+ 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));
@@ -722,15 +739,15 @@
*/
static void COVER_best_wait(COVER_best_t *best) {
if (!best) {
return;
}
- pthread_mutex_lock(&best->mutex);
+ ZSTD_pthread_mutex_lock(&best->mutex);
while (best->liveJobs != 0) {
- pthread_cond_wait(&best->cond, &best->mutex);
+ ZSTD_pthread_cond_wait(&best->cond, &best->mutex);
}
- pthread_mutex_unlock(&best->mutex);
+ ZSTD_pthread_mutex_unlock(&best->mutex);
}
/**
* Call COVER_best_wait() and then destroy the COVER_best_t.
*/
@@ -740,41 +757,41 @@
}
COVER_best_wait(best);
if (best->dict) {
free(best->dict);
}
- pthread_mutex_destroy(&best->mutex);
- pthread_cond_destroy(&best->cond);
+ ZSTD_pthread_mutex_destroy(&best->mutex);
+ ZSTD_pthread_cond_destroy(&best->cond);
}
/**
* Called when a thread is about to be launched.
* Increments liveJobs.
*/
static void COVER_best_start(COVER_best_t *best) {
if (!best) {
return;
}
- pthread_mutex_lock(&best->mutex);
+ ZSTD_pthread_mutex_lock(&best->mutex);
++best->liveJobs;
- pthread_mutex_unlock(&best->mutex);
+ 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.
*/
static void COVER_best_finish(COVER_best_t *best, size_t compressedSize,
- COVER_params_t parameters, void *dict,
+ ZDICT_cover_params_t parameters, void *dict,
size_t dictSize) {
if (!best) {
return;
}
{
size_t liveJobs;
- pthread_mutex_lock(&best->mutex);
+ 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 */
@@ -793,13 +810,13 @@
memcpy(best->dict, dict, dictSize);
best->dictSize = dictSize;
best->parameters = parameters;
best->compressedSize = compressedSize;
}
- pthread_mutex_unlock(&best->mutex);
+ ZSTD_pthread_mutex_unlock(&best->mutex);
if (liveJobs == 0) {
- pthread_cond_broadcast(&best->cond);
+ ZSTD_pthread_cond_broadcast(&best->cond);
}
}
}
/**
@@ -807,11 +824,11 @@
*/
typedef struct COVER_tryParameters_data_s {
const COVER_ctx_t *ctx;
COVER_best_t *best;
size_t dictBufferCapacity;
- COVER_params_t parameters;
+ ZDICT_cover_params_t parameters;
} COVER_tryParameters_data_t;
/**
* Tries a set of parameters and upates the COVER_best_t with the results.
* This function is thread safe if zstd is compiled with multithreaded support.
@@ -819,11 +836,11 @@
*/
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 COVER_params_t parameters = data->parameters;
+ 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 * const)malloc(dictBufferCapacity);
@@ -840,14 +857,14 @@
memcpy(freqs, ctx->freqs, ctx->suffixSize * sizeof(U32));
/* Build the dictionary */
{
const size_t tail = COVER_buildDictionary(ctx, freqs, &activeDmers, dict,
dictBufferCapacity, parameters);
- const ZDICT_params_t zdictParams = COVER_translateParams(parameters);
dictBufferCapacity = ZDICT_finalizeDictionary(
dict, dictBufferCapacity, dict + tail, dictBufferCapacity - tail,
- ctx->samples, ctx->samplesSizes, (unsigned)ctx->nbSamples, zdictParams);
+ ctx->samples, ctx->samplesSizes, (unsigned)ctx->nbSamples,
+ parameters.zParams);
if (ZDICT_isError(dictBufferCapacity)) {
DISPLAYLEVEL(1, "Failed to finalize dictionary\n");
goto _cleanup;
}
}
@@ -869,17 +886,17 @@
dstCapacity = ZSTD_compressBound(maxSampleSize);
dst = malloc(dstCapacity);
}
/* Create the cctx and cdict */
cctx = ZSTD_createCCtx();
- cdict =
- ZSTD_createCDict(dict, dictBufferCapacity, parameters.compressionLevel);
+ cdict = ZSTD_createCDict(dict, dictBufferCapacity,
+ parameters.zParams.compressionLevel);
if (!dst || !cctx || !cdict) {
goto _compressCleanup;
}
/* Compress each sample and sum their sizes (or error) */
- totalCompressedSize = 0;
+ totalCompressedSize = dictBufferCapacity;
for (i = 0; i < ctx->nbSamples; ++i) {
const size_t size = ZSTD_compress_usingCDict(
cctx, dst, dstCapacity, ctx->samples + ctx->offsets[i],
ctx->samplesSizes[i], cdict);
if (ZSTD_isError(size)) {
@@ -907,28 +924,26 @@
if (freqs) {
free(freqs);
}
}
-ZDICTLIB_API size_t COVER_optimizeTrainFromBuffer(void *dictBuffer,
- size_t dictBufferCapacity,
- const void *samplesBuffer,
- const size_t *samplesSizes,
- unsigned nbSamples,
- COVER_params_t *parameters) {
+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 unsigned kMinD = parameters->d == 0 ? 6 : parameters->d;
- const unsigned kMaxD = parameters->d == 0 ? 16 : parameters->d;
- const unsigned kMinK = parameters->k == 0 ? kMaxD : parameters->k;
- const unsigned kMaxK = parameters->k == 0 ? 2048 : parameters->k;
- const unsigned kSteps = parameters->steps == 0 ? 32 : parameters->steps;
+ 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);
/* Local variables */
- const int displayLevel = parameters->notificationLevel;
+ const int displayLevel = parameters->zParams.notificationLevel;
unsigned iteration = 1;
unsigned d;
unsigned k;
COVER_best_t best;
POOL_ctx *pool = NULL;
@@ -953,11 +968,11 @@
}
}
/* Initialization */
COVER_best_init(&best);
/* Turn down global display level to clean up display at level 2 and below */
- g_displayLevel = parameters->notificationLevel - 1;
+ 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 */
@@ -987,11 +1002,12 @@
data->dictBufferCapacity = dictBufferCapacity;
data->parameters = *parameters;
data->parameters.k = k;
data->parameters.d = d;
data->parameters.steps = kSteps;
+ data->parameters.zParams.notificationLevel = g_displayLevel;
/* Check the parameters */
- if (!COVER_checkParameters(data->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 */