| 1 |
/* |
| 2 |
* Copyright (c) 2016-2020, Yann Collet, Facebook, Inc. |
| 3 |
* All rights reserved. |
| 4 |
* |
| 5 |
* This source code is licensed under both the BSD-style license (found in the |
| 6 |
* LICENSE file in the root directory of this source tree) and the GPLv2 (found |
| 7 |
* in the COPYING file in the root directory of this source tree). |
| 8 |
* You may select, at your option, one of the above-listed licenses. |
| 9 |
*/ |
| 10 |
|
| 11 |
|
| 12 |
/*-************************************** |
| 13 |
* Tuning parameters |
| 14 |
****************************************/ |
| 15 |
#define MINRATIO 4 /* minimum nb of apparition to be selected in dictionary */ |
| 16 |
#define ZDICT_MAX_SAMPLES_SIZE (2000U << 20) |
| 17 |
#define ZDICT_MIN_SAMPLES_SIZE (ZDICT_CONTENTSIZE_MIN * MINRATIO) |
| 18 |
|
| 19 |
|
| 20 |
/*-************************************** |
| 21 |
* Compiler Options |
| 22 |
****************************************/ |
| 23 |
/* Unix Large Files support (>4GB) */ |
| 24 |
#define _FILE_OFFSET_BITS 64 |
| 25 |
#if (defined(__sun__) && (!defined(__LP64__))) /* Sun Solaris 32-bits requires specific definitions */ |
| 26 |
# define _LARGEFILE_SOURCE |
| 27 |
#elif ! defined(__LP64__) /* No point defining Large file for 64 bit */ |
| 28 |
# define _LARGEFILE64_SOURCE |
| 29 |
#endif |
| 30 |
|
| 31 |
|
| 32 |
/*-************************************* |
| 33 |
* Dependencies |
| 34 |
***************************************/ |
| 35 |
#include <stdlib.h> /* malloc, free */ |
| 36 |
#include <string.h> /* memset */ |
| 37 |
#include <stdio.h> /* fprintf, fopen, ftello64 */ |
| 38 |
#include <time.h> /* clock */ |
| 39 |
|
| 40 |
#include "../common/mem.h" /* read */ |
| 41 |
#include "../common/fse.h" /* FSE_normalizeCount, FSE_writeNCount */ |
| 42 |
#define HUF_STATIC_LINKING_ONLY |
| 43 |
#include "../common/huf.h" /* HUF_buildCTable, HUF_writeCTable */ |
| 44 |
#include "../common/zstd_internal.h" /* includes zstd.h */ |
| 45 |
#include "../common/xxhash.h" /* XXH64 */ |
| 46 |
#include "divsufsort.h" |
| 47 |
#ifndef ZDICT_STATIC_LINKING_ONLY |
| 48 |
# define ZDICT_STATIC_LINKING_ONLY |
| 49 |
#endif |
| 50 |
#include "zdict.h" |
| 51 |
#include "../compress/zstd_compress_internal.h" /* ZSTD_loadCEntropy() */ |
| 52 |
|
| 53 |
|
| 54 |
/*-************************************* |
| 55 |
* Constants |
| 56 |
***************************************/ |
| 57 |
#define KB *(1 <<10) |
| 58 |
#define MB *(1 <<20) |
| 59 |
#define GB *(1U<<30) |
| 60 |
|
| 61 |
#define DICTLISTSIZE_DEFAULT 10000 |
| 62 |
|
| 63 |
#define NOISELENGTH 32 |
| 64 |
|
| 65 |
static const int g_compressionLevel_default = 3; |
| 66 |
static const U32 g_selectivity_default = 9; |
| 67 |
|
| 68 |
|
| 69 |
/*-************************************* |
| 70 |
* Console display |
| 71 |
***************************************/ |
| 72 |
#define DISPLAY(...) { fprintf(stderr, __VA_ARGS__); fflush( stderr ); } |
| 73 |
#define DISPLAYLEVEL(l, ...) if (notificationLevel>=l) { DISPLAY(__VA_ARGS__); } /* 0 : no display; 1: errors; 2: default; 3: details; 4: debug */ |
| 74 |
|
| 75 |
static clock_t ZDICT_clockSpan(clock_t nPrevious) { return clock() - nPrevious; } |
| 76 |
|
| 77 |
static void ZDICT_printHex(const void* ptr, size_t length) |
| 78 |
{ |
| 79 |
const BYTE* const b = (const BYTE*)ptr; |
| 80 |
size_t u; |
| 81 |
for (u=0; u<length; u++) { |
| 82 |
BYTE c = b[u]; |
| 83 |
if (c<32 || c>126) c = '.'; /* non-printable char */ |
| 84 |
DISPLAY("%c", c); |
| 85 |
} |
| 86 |
} |
| 87 |
|
| 88 |
|
| 89 |
/*-******************************************************** |
| 90 |
* Helper functions |
| 91 |
**********************************************************/ |
| 92 |
unsigned ZDICT_isError(size_t errorCode) { return ERR_isError(errorCode); } |
| 93 |
|
| 94 |
const char* ZDICT_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); } |
| 95 |
|
| 96 |
unsigned ZDICT_getDictID(const void* dictBuffer, size_t dictSize) |
| 97 |
{ |
| 98 |
if (dictSize < 8) return 0; |
| 99 |
if (MEM_readLE32(dictBuffer) != ZSTD_MAGIC_DICTIONARY) return 0; |
| 100 |
return MEM_readLE32((const char*)dictBuffer + 4); |
| 101 |
} |
| 102 |
|
| 103 |
size_t ZDICT_getDictHeaderSize(const void* dictBuffer, size_t dictSize) |
| 104 |
{ |
| 105 |
size_t headerSize; |
| 106 |
if (dictSize <= 8 || MEM_readLE32(dictBuffer) != ZSTD_MAGIC_DICTIONARY) return ERROR(dictionary_corrupted); |
| 107 |
|
| 108 |
{ unsigned offcodeMaxValue = MaxOff; |
| 109 |
ZSTD_compressedBlockState_t* bs = (ZSTD_compressedBlockState_t*)malloc(sizeof(ZSTD_compressedBlockState_t)); |
| 110 |
U32* wksp = (U32*)malloc(HUF_WORKSPACE_SIZE); |
| 111 |
short* offcodeNCount = (short*)malloc((MaxOff+1)*sizeof(short)); |
| 112 |
if (!bs || !wksp || !offcodeNCount) { |
| 113 |
headerSize = ERROR(memory_allocation); |
| 114 |
} else { |
| 115 |
ZSTD_reset_compressedBlockState(bs); |
| 116 |
headerSize = ZSTD_loadCEntropy(bs, wksp, offcodeNCount, &offcodeMaxValue, dictBuffer, dictSize); |
| 117 |
} |
| 118 |
|
| 119 |
free(bs); |
| 120 |
free(wksp); |
| 121 |
free(offcodeNCount); |
| 122 |
} |
| 123 |
|
| 124 |
return headerSize; |
| 125 |
} |
| 126 |
|
| 127 |
/*-******************************************************** |
| 128 |
* Dictionary training functions |
| 129 |
**********************************************************/ |
| 130 |
static unsigned ZDICT_NbCommonBytes (size_t val) |
| 131 |
{ |
| 132 |
if (MEM_isLittleEndian()) { |
| 133 |
if (MEM_64bits()) { |
| 134 |
# if defined(_MSC_VER) && defined(_WIN64) |
| 135 |
unsigned long r = 0; |
| 136 |
_BitScanForward64( &r, (U64)val ); |
| 137 |
return (unsigned)(r>>3); |
| 138 |
# elif defined(__GNUC__) && (__GNUC__ >= 3) |
| 139 |
return (__builtin_ctzll((U64)val) >> 3); |
| 140 |
# else |
| 141 |
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 }; |
| 142 |
return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58]; |
| 143 |
# endif |
| 144 |
} else { /* 32 bits */ |
| 145 |
# if defined(_MSC_VER) |
| 146 |
unsigned long r=0; |
| 147 |
_BitScanForward( &r, (U32)val ); |
| 148 |
return (unsigned)(r>>3); |
| 149 |
# elif defined(__GNUC__) && (__GNUC__ >= 3) |
| 150 |
return (__builtin_ctz((U32)val) >> 3); |
| 151 |
# else |
| 152 |
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 }; |
| 153 |
return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27]; |
| 154 |
# endif |
| 155 |
} |
| 156 |
} else { /* Big Endian CPU */ |
| 157 |
if (MEM_64bits()) { |
| 158 |
# if defined(_MSC_VER) && defined(_WIN64) |
| 159 |
unsigned long r = 0; |
| 160 |
_BitScanReverse64( &r, val ); |
| 161 |
return (unsigned)(r>>3); |
| 162 |
# elif defined(__GNUC__) && (__GNUC__ >= 3) |
| 163 |
return (__builtin_clzll(val) >> 3); |
| 164 |
# else |
| 165 |
unsigned r; |
| 166 |
const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */ |
| 167 |
if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; } |
| 168 |
if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } |
| 169 |
r += (!val); |
| 170 |
return r; |
| 171 |
# endif |
| 172 |
} else { /* 32 bits */ |
| 173 |
# if defined(_MSC_VER) |
| 174 |
unsigned long r = 0; |
| 175 |
_BitScanReverse( &r, (unsigned long)val ); |
| 176 |
return (unsigned)(r>>3); |
| 177 |
# elif defined(__GNUC__) && (__GNUC__ >= 3) |
| 178 |
return (__builtin_clz((U32)val) >> 3); |
| 179 |
# else |
| 180 |
unsigned r; |
| 181 |
if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; } |
| 182 |
r += (!val); |
| 183 |
return r; |
| 184 |
# endif |
| 185 |
} } |
| 186 |
} |
| 187 |
|
| 188 |
|
| 189 |
/*! ZDICT_count() : |
| 190 |
Count the nb of common bytes between 2 pointers. |
| 191 |
Note : this function presumes end of buffer followed by noisy guard band. |
| 192 |
*/ |
| 193 |
static size_t ZDICT_count(const void* pIn, const void* pMatch) |
| 194 |
{ |
| 195 |
const char* const pStart = (const char*)pIn; |
| 196 |
for (;;) { |
| 197 |
size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn); |
| 198 |
if (!diff) { |
| 199 |
pIn = (const char*)pIn+sizeof(size_t); |
| 200 |
pMatch = (const char*)pMatch+sizeof(size_t); |
| 201 |
continue; |
| 202 |
} |
| 203 |
pIn = (const char*)pIn+ZDICT_NbCommonBytes(diff); |
| 204 |
return (size_t)((const char*)pIn - pStart); |
| 205 |
} |
| 206 |
} |
| 207 |
|
| 208 |
|
| 209 |
typedef struct { |
| 210 |
U32 pos; |
| 211 |
U32 length; |
| 212 |
U32 savings; |
| 213 |
} dictItem; |
| 214 |
|
| 215 |
static void ZDICT_initDictItem(dictItem* d) |
| 216 |
{ |
| 217 |
d->pos = 1; |
| 218 |
d->length = 0; |
| 219 |
d->savings = (U32)(-1); |
| 220 |
} |
| 221 |
|
| 222 |
|
| 223 |
#define LLIMIT 64 /* heuristic determined experimentally */ |
| 224 |
#define MINMATCHLENGTH 7 /* heuristic determined experimentally */ |
| 225 |
static dictItem ZDICT_analyzePos( |
| 226 |
BYTE* doneMarks, |
| 227 |
const int* suffix, U32 start, |
| 228 |
const void* buffer, U32 minRatio, U32 notificationLevel) |
| 229 |
{ |
| 230 |
U32 lengthList[LLIMIT] = {0}; |
| 231 |
U32 cumulLength[LLIMIT] = {0}; |
| 232 |
U32 savings[LLIMIT] = {0}; |
| 233 |
const BYTE* b = (const BYTE*)buffer; |
| 234 |
size_t maxLength = LLIMIT; |
| 235 |
size_t pos = suffix[start]; |
| 236 |
U32 end = start; |
| 237 |
dictItem solution; |
| 238 |
|
| 239 |
/* init */ |
| 240 |
memset(&solution, 0, sizeof(solution)); |
| 241 |
doneMarks[pos] = 1; |
| 242 |
|
| 243 |
/* trivial repetition cases */ |
| 244 |
if ( (MEM_read16(b+pos+0) == MEM_read16(b+pos+2)) |
| 245 |
||(MEM_read16(b+pos+1) == MEM_read16(b+pos+3)) |
| 246 |
||(MEM_read16(b+pos+2) == MEM_read16(b+pos+4)) ) { |
| 247 |
/* skip and mark segment */ |
| 248 |
U16 const pattern16 = MEM_read16(b+pos+4); |
| 249 |
U32 u, patternEnd = 6; |
| 250 |
while (MEM_read16(b+pos+patternEnd) == pattern16) patternEnd+=2 ; |
| 251 |
if (b[pos+patternEnd] == b[pos+patternEnd-1]) patternEnd++; |
| 252 |
for (u=1; u<patternEnd; u++) |
| 253 |
doneMarks[pos+u] = 1; |
| 254 |
return solution; |
| 255 |
} |
| 256 |
|
| 257 |
/* look forward */ |
| 258 |
{ size_t length; |
| 259 |
do { |
| 260 |
end++; |
| 261 |
length = ZDICT_count(b + pos, b + suffix[end]); |
| 262 |
} while (length >= MINMATCHLENGTH); |
| 263 |
} |
| 264 |
|
| 265 |
/* look backward */ |
| 266 |
{ size_t length; |
| 267 |
do { |
| 268 |
length = ZDICT_count(b + pos, b + *(suffix+start-1)); |
| 269 |
if (length >=MINMATCHLENGTH) start--; |
| 270 |
} while(length >= MINMATCHLENGTH); |
| 271 |
} |
| 272 |
|
| 273 |
/* exit if not found a minimum nb of repetitions */ |
| 274 |
if (end-start < minRatio) { |
| 275 |
U32 idx; |
| 276 |
for(idx=start; idx<end; idx++) |
| 277 |
doneMarks[suffix[idx]] = 1; |
| 278 |
return solution; |
| 279 |
} |
| 280 |
|
| 281 |
{ int i; |
| 282 |
U32 mml; |
| 283 |
U32 refinedStart = start; |
| 284 |
U32 refinedEnd = end; |
| 285 |
|
| 286 |
DISPLAYLEVEL(4, "\n"); |
| 287 |
DISPLAYLEVEL(4, "found %3u matches of length >= %i at pos %7u ", (unsigned)(end-start), MINMATCHLENGTH, (unsigned)pos); |
| 288 |
DISPLAYLEVEL(4, "\n"); |
| 289 |
|
| 290 |
for (mml = MINMATCHLENGTH ; ; mml++) { |
| 291 |
BYTE currentChar = 0; |
| 292 |
U32 currentCount = 0; |
| 293 |
U32 currentID = refinedStart; |
| 294 |
U32 id; |
| 295 |
U32 selectedCount = 0; |
| 296 |
U32 selectedID = currentID; |
| 297 |
for (id =refinedStart; id < refinedEnd; id++) { |
| 298 |
if (b[suffix[id] + mml] != currentChar) { |
| 299 |
if (currentCount > selectedCount) { |
| 300 |
selectedCount = currentCount; |
| 301 |
selectedID = currentID; |
| 302 |
} |
| 303 |
currentID = id; |
| 304 |
currentChar = b[ suffix[id] + mml]; |
| 305 |
currentCount = 0; |
| 306 |
} |
| 307 |
currentCount ++; |
| 308 |
} |
| 309 |
if (currentCount > selectedCount) { /* for last */ |
| 310 |
selectedCount = currentCount; |
| 311 |
selectedID = currentID; |
| 312 |
} |
| 313 |
|
| 314 |
if (selectedCount < minRatio) |
| 315 |
break; |
| 316 |
refinedStart = selectedID; |
| 317 |
refinedEnd = refinedStart + selectedCount; |
| 318 |
} |
| 319 |
|
| 320 |
/* evaluate gain based on new dict */ |
| 321 |
start = refinedStart; |
| 322 |
pos = suffix[refinedStart]; |
| 323 |
end = start; |
| 324 |
memset(lengthList, 0, sizeof(lengthList)); |
| 325 |
|
| 326 |
/* look forward */ |
| 327 |
{ size_t length; |
| 328 |
do { |
| 329 |
end++; |
| 330 |
length = ZDICT_count(b + pos, b + suffix[end]); |
| 331 |
if (length >= LLIMIT) length = LLIMIT-1; |
| 332 |
lengthList[length]++; |
| 333 |
} while (length >=MINMATCHLENGTH); |
| 334 |
} |
| 335 |
|
| 336 |
/* look backward */ |
| 337 |
{ size_t length = MINMATCHLENGTH; |
| 338 |
while ((length >= MINMATCHLENGTH) & (start > 0)) { |
| 339 |
length = ZDICT_count(b + pos, b + suffix[start - 1]); |
| 340 |
if (length >= LLIMIT) length = LLIMIT - 1; |
| 341 |
lengthList[length]++; |
| 342 |
if (length >= MINMATCHLENGTH) start--; |
| 343 |
} |
| 344 |
} |
| 345 |
|
| 346 |
/* largest useful length */ |
| 347 |
memset(cumulLength, 0, sizeof(cumulLength)); |
| 348 |
cumulLength[maxLength-1] = lengthList[maxLength-1]; |
| 349 |
for (i=(int)(maxLength-2); i>=0; i--) |
| 350 |
cumulLength[i] = cumulLength[i+1] + lengthList[i]; |
| 351 |
|
| 352 |
for (i=LLIMIT-1; i>=MINMATCHLENGTH; i--) if (cumulLength[i]>=minRatio) break; |
| 353 |
maxLength = i; |
| 354 |
|
| 355 |
/* reduce maxLength in case of final into repetitive data */ |
| 356 |
{ U32 l = (U32)maxLength; |
| 357 |
BYTE const c = b[pos + maxLength-1]; |
| 358 |
while (b[pos+l-2]==c) l--; |
| 359 |
maxLength = l; |
| 360 |
} |
| 361 |
if (maxLength < MINMATCHLENGTH) return solution; /* skip : no long-enough solution */ |
| 362 |
|
| 363 |
/* calculate savings */ |
| 364 |
savings[5] = 0; |
| 365 |
for (i=MINMATCHLENGTH; i<=(int)maxLength; i++) |
| 366 |
savings[i] = savings[i-1] + (lengthList[i] * (i-3)); |
| 367 |
|
| 368 |
DISPLAYLEVEL(4, "Selected dict at position %u, of length %u : saves %u (ratio: %.2f) \n", |
| 369 |
(unsigned)pos, (unsigned)maxLength, (unsigned)savings[maxLength], (double)savings[maxLength] / maxLength); |
| 370 |
|
| 371 |
solution.pos = (U32)pos; |
| 372 |
solution.length = (U32)maxLength; |
| 373 |
solution.savings = savings[maxLength]; |
| 374 |
|
| 375 |
/* mark positions done */ |
| 376 |
{ U32 id; |
| 377 |
for (id=start; id<end; id++) { |
| 378 |
U32 p, pEnd, length; |
| 379 |
U32 const testedPos = suffix[id]; |
| 380 |
if (testedPos == pos) |
| 381 |
length = solution.length; |
| 382 |
else { |
| 383 |
length = (U32)ZDICT_count(b+pos, b+testedPos); |
| 384 |
if (length > solution.length) length = solution.length; |
| 385 |
} |
| 386 |
pEnd = (U32)(testedPos + length); |
| 387 |
for (p=testedPos; p<pEnd; p++) |
| 388 |
doneMarks[p] = 1; |
| 389 |
} } } |
| 390 |
|
| 391 |
return solution; |
| 392 |
} |
| 393 |
|
| 394 |
|
| 395 |
static int isIncluded(const void* in, const void* container, size_t length) |
| 396 |
{ |
| 397 |
const char* const ip = (const char*) in; |
| 398 |
const char* const into = (const char*) container; |
| 399 |
size_t u; |
| 400 |
|
| 401 |
for (u=0; u<length; u++) { /* works because end of buffer is a noisy guard band */ |
| 402 |
if (ip[u] != into[u]) break; |
| 403 |
} |
| 404 |
|
| 405 |
return u==length; |
| 406 |
} |
| 407 |
|
| 408 |
/*! ZDICT_tryMerge() : |
| 409 |
check if dictItem can be merged, do it if possible |
| 410 |
@return : id of destination elt, 0 if not merged |
| 411 |
*/ |
| 412 |
static U32 ZDICT_tryMerge(dictItem* table, dictItem elt, U32 eltNbToSkip, const void* buffer) |
| 413 |
{ |
| 414 |
const U32 tableSize = table->pos; |
| 415 |
const U32 eltEnd = elt.pos + elt.length; |
| 416 |
const char* const buf = (const char*) buffer; |
| 417 |
|
| 418 |
/* tail overlap */ |
| 419 |
U32 u; for (u=1; u<tableSize; u++) { |
| 420 |
if (u==eltNbToSkip) continue; |
| 421 |
if ((table[u].pos > elt.pos) && (table[u].pos <= eltEnd)) { /* overlap, existing > new */ |
| 422 |
/* append */ |
| 423 |
U32 const addedLength = table[u].pos - elt.pos; |
| 424 |
table[u].length += addedLength; |
| 425 |
table[u].pos = elt.pos; |
| 426 |
table[u].savings += elt.savings * addedLength / elt.length; /* rough approx */ |
| 427 |
table[u].savings += elt.length / 8; /* rough approx bonus */ |
| 428 |
elt = table[u]; |
| 429 |
/* sort : improve rank */ |
| 430 |
while ((u>1) && (table[u-1].savings < elt.savings)) |
| 431 |
table[u] = table[u-1], u--; |
| 432 |
table[u] = elt; |
| 433 |
return u; |
| 434 |
} } |
| 435 |
|
| 436 |
/* front overlap */ |
| 437 |
for (u=1; u<tableSize; u++) { |
| 438 |
if (u==eltNbToSkip) continue; |
| 439 |
|
| 440 |
if ((table[u].pos + table[u].length >= elt.pos) && (table[u].pos < elt.pos)) { /* overlap, existing < new */ |
| 441 |
/* append */ |
| 442 |
int const addedLength = (int)eltEnd - (table[u].pos + table[u].length); |
| 443 |
table[u].savings += elt.length / 8; /* rough approx bonus */ |
| 444 |
if (addedLength > 0) { /* otherwise, elt fully included into existing */ |
| 445 |
table[u].length += addedLength; |
| 446 |
table[u].savings += elt.savings * addedLength / elt.length; /* rough approx */ |
| 447 |
} |
| 448 |
/* sort : improve rank */ |
| 449 |
elt = table[u]; |
| 450 |
while ((u>1) && (table[u-1].savings < elt.savings)) |
| 451 |
table[u] = table[u-1], u--; |
| 452 |
table[u] = elt; |
| 453 |
return u; |
| 454 |
} |
| 455 |
|
| 456 |
if (MEM_read64(buf + table[u].pos) == MEM_read64(buf + elt.pos + 1)) { |
| 457 |
if (isIncluded(buf + table[u].pos, buf + elt.pos + 1, table[u].length)) { |
| 458 |
size_t const addedLength = MAX( (int)elt.length - (int)table[u].length , 1 ); |
| 459 |
table[u].pos = elt.pos; |
| 460 |
table[u].savings += (U32)(elt.savings * addedLength / elt.length); |
| 461 |
table[u].length = MIN(elt.length, table[u].length + 1); |
| 462 |
return u; |
| 463 |
} |
| 464 |
} |
| 465 |
} |
| 466 |
|
| 467 |
return 0; |
| 468 |
} |
| 469 |
|
| 470 |
|
| 471 |
static void ZDICT_removeDictItem(dictItem* table, U32 id) |
| 472 |
{ |
| 473 |
/* convention : table[0].pos stores nb of elts */ |
| 474 |
U32 const max = table[0].pos; |
| 475 |
U32 u; |
| 476 |
if (!id) return; /* protection, should never happen */ |
| 477 |
for (u=id; u<max-1; u++) |
| 478 |
table[u] = table[u+1]; |
| 479 |
table->pos--; |
| 480 |
} |
| 481 |
|
| 482 |
|
| 483 |
static void ZDICT_insertDictItem(dictItem* table, U32 maxSize, dictItem elt, const void* buffer) |
| 484 |
{ |
| 485 |
/* merge if possible */ |
| 486 |
U32 mergeId = ZDICT_tryMerge(table, elt, 0, buffer); |
| 487 |
if (mergeId) { |
| 488 |
U32 newMerge = 1; |
| 489 |
while (newMerge) { |
| 490 |
newMerge = ZDICT_tryMerge(table, table[mergeId], mergeId, buffer); |
| 491 |
if (newMerge) ZDICT_removeDictItem(table, mergeId); |
| 492 |
mergeId = newMerge; |
| 493 |
} |
| 494 |
return; |
| 495 |
} |
| 496 |
|
| 497 |
/* insert */ |
| 498 |
{ U32 current; |
| 499 |
U32 nextElt = table->pos; |
| 500 |
if (nextElt >= maxSize) nextElt = maxSize-1; |
| 501 |
current = nextElt-1; |
| 502 |
while (table[current].savings < elt.savings) { |
| 503 |
table[current+1] = table[current]; |
| 504 |
current--; |
| 505 |
} |
| 506 |
table[current+1] = elt; |
| 507 |
table->pos = nextElt+1; |
| 508 |
} |
| 509 |
} |
| 510 |
|
| 511 |
|
| 512 |
static U32 ZDICT_dictSize(const dictItem* dictList) |
| 513 |
{ |
| 514 |
U32 u, dictSize = 0; |
| 515 |
for (u=1; u<dictList[0].pos; u++) |
| 516 |
dictSize += dictList[u].length; |
| 517 |
return dictSize; |
| 518 |
} |
| 519 |
|
| 520 |
|
| 521 |
static size_t ZDICT_trainBuffer_legacy(dictItem* dictList, U32 dictListSize, |
| 522 |
const void* const buffer, size_t bufferSize, /* buffer must end with noisy guard band */ |
| 523 |
const size_t* fileSizes, unsigned nbFiles, |
| 524 |
unsigned minRatio, U32 notificationLevel) |
| 525 |
{ |
| 526 |
int* const suffix0 = (int*)malloc((bufferSize+2)*sizeof(*suffix0)); |
| 527 |
int* const suffix = suffix0+1; |
| 528 |
U32* reverseSuffix = (U32*)malloc((bufferSize)*sizeof(*reverseSuffix)); |
| 529 |
BYTE* doneMarks = (BYTE*)malloc((bufferSize+16)*sizeof(*doneMarks)); /* +16 for overflow security */ |
| 530 |
U32* filePos = (U32*)malloc(nbFiles * sizeof(*filePos)); |
| 531 |
size_t result = 0; |
| 532 |
clock_t displayClock = 0; |
| 533 |
clock_t const refreshRate = CLOCKS_PER_SEC * 3 / 10; |
| 534 |
|
| 535 |
# define DISPLAYUPDATE(l, ...) if (notificationLevel>=l) { \ |
| 536 |
if (ZDICT_clockSpan(displayClock) > refreshRate) \ |
| 537 |
{ displayClock = clock(); DISPLAY(__VA_ARGS__); \ |
| 538 |
if (notificationLevel>=4) fflush(stderr); } } |
| 539 |
|
| 540 |
/* init */ |
| 541 |
DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */ |
| 542 |
if (!suffix0 || !reverseSuffix || !doneMarks || !filePos) { |
| 543 |
result = ERROR(memory_allocation); |
| 544 |
goto _cleanup; |
| 545 |
} |
| 546 |
if (minRatio < MINRATIO) minRatio = MINRATIO; |
| 547 |
memset(doneMarks, 0, bufferSize+16); |
| 548 |
|
| 549 |
/* limit sample set size (divsufsort limitation)*/ |
| 550 |
if (bufferSize > ZDICT_MAX_SAMPLES_SIZE) DISPLAYLEVEL(3, "sample set too large : reduced to %u MB ...\n", (unsigned)(ZDICT_MAX_SAMPLES_SIZE>>20)); |
| 551 |
while (bufferSize > ZDICT_MAX_SAMPLES_SIZE) bufferSize -= fileSizes[--nbFiles]; |
| 552 |
|
| 553 |
/* sort */ |
| 554 |
DISPLAYLEVEL(2, "sorting %u files of total size %u MB ...\n", nbFiles, (unsigned)(bufferSize>>20)); |
| 555 |
{ int const divSuftSortResult = divsufsort((const unsigned char*)buffer, suffix, (int)bufferSize, 0); |
| 556 |
if (divSuftSortResult != 0) { result = ERROR(GENERIC); goto _cleanup; } |
| 557 |
} |
| 558 |
suffix[bufferSize] = (int)bufferSize; /* leads into noise */ |
| 559 |
suffix0[0] = (int)bufferSize; /* leads into noise */ |
| 560 |
/* build reverse suffix sort */ |
| 561 |
{ size_t pos; |
| 562 |
for (pos=0; pos < bufferSize; pos++) |
| 563 |
reverseSuffix[suffix[pos]] = (U32)pos; |
| 564 |
/* note filePos tracks borders between samples. |
| 565 |
It's not used at this stage, but planned to become useful in a later update */ |
| 566 |
filePos[0] = 0; |
| 567 |
for (pos=1; pos<nbFiles; pos++) |
| 568 |
filePos[pos] = (U32)(filePos[pos-1] + fileSizes[pos-1]); |
| 569 |
} |
| 570 |
|
| 571 |
DISPLAYLEVEL(2, "finding patterns ... \n"); |
| 572 |
DISPLAYLEVEL(3, "minimum ratio : %u \n", minRatio); |
| 573 |
|
| 574 |
{ U32 cursor; for (cursor=0; cursor < bufferSize; ) { |
| 575 |
dictItem solution; |
| 576 |
if (doneMarks[cursor]) { cursor++; continue; } |
| 577 |
solution = ZDICT_analyzePos(doneMarks, suffix, reverseSuffix[cursor], buffer, minRatio, notificationLevel); |
| 578 |
if (solution.length==0) { cursor++; continue; } |
| 579 |
ZDICT_insertDictItem(dictList, dictListSize, solution, buffer); |
| 580 |
cursor += solution.length; |
| 581 |
DISPLAYUPDATE(2, "\r%4.2f %% \r", (double)cursor / bufferSize * 100); |
| 582 |
} } |
| 583 |
|
| 584 |
_cleanup: |
| 585 |
free(suffix0); |
| 586 |
free(reverseSuffix); |
| 587 |
free(doneMarks); |
| 588 |
free(filePos); |
| 589 |
return result; |
| 590 |
} |
| 591 |
|
| 592 |
|
| 593 |
static void ZDICT_fillNoise(void* buffer, size_t length) |
| 594 |
{ |
| 595 |
unsigned const prime1 = 2654435761U; |
| 596 |
unsigned const prime2 = 2246822519U; |
| 597 |
unsigned acc = prime1; |
| 598 |
size_t p=0; |
| 599 |
for (p=0; p<length; p++) { |
| 600 |
acc *= prime2; |
| 601 |
((unsigned char*)buffer)[p] = (unsigned char)(acc >> 21); |
| 602 |
} |
| 603 |
} |
| 604 |
|
| 605 |
|
| 606 |
typedef struct |
| 607 |
{ |
| 608 |
ZSTD_CDict* dict; /* dictionary */ |
| 609 |
ZSTD_CCtx* zc; /* working context */ |
| 610 |
void* workPlace; /* must be ZSTD_BLOCKSIZE_MAX allocated */ |
| 611 |
} EStats_ress_t; |
| 612 |
|
| 613 |
#define MAXREPOFFSET 1024 |
| 614 |
|
| 615 |
static void ZDICT_countEStats(EStats_ress_t esr, const ZSTD_parameters* params, |
| 616 |
unsigned* countLit, unsigned* offsetcodeCount, unsigned* matchlengthCount, unsigned* litlengthCount, U32* repOffsets, |
| 617 |
const void* src, size_t srcSize, |
| 618 |
U32 notificationLevel) |
| 619 |
{ |
| 620 |
size_t const blockSizeMax = MIN (ZSTD_BLOCKSIZE_MAX, 1 << params->cParams.windowLog); |
| 621 |
size_t cSize; |
| 622 |
|
| 623 |
if (srcSize > blockSizeMax) srcSize = blockSizeMax; /* protection vs large samples */ |
| 624 |
{ size_t const errorCode = ZSTD_compressBegin_usingCDict(esr.zc, esr.dict); |
| 625 |
if (ZSTD_isError(errorCode)) { DISPLAYLEVEL(1, "warning : ZSTD_compressBegin_usingCDict failed \n"); return; } |
| 626 |
|
| 627 |
} |
| 628 |
cSize = ZSTD_compressBlock(esr.zc, esr.workPlace, ZSTD_BLOCKSIZE_MAX, src, srcSize); |
| 629 |
if (ZSTD_isError(cSize)) { DISPLAYLEVEL(3, "warning : could not compress sample size %u \n", (unsigned)srcSize); return; } |
| 630 |
|
| 631 |
if (cSize) { /* if == 0; block is not compressible */ |
| 632 |
const seqStore_t* const seqStorePtr = ZSTD_getSeqStore(esr.zc); |
| 633 |
|
| 634 |
/* literals stats */ |
| 635 |
{ const BYTE* bytePtr; |
| 636 |
for(bytePtr = seqStorePtr->litStart; bytePtr < seqStorePtr->lit; bytePtr++) |
| 637 |
countLit[*bytePtr]++; |
| 638 |
} |
| 639 |
|
| 640 |
/* seqStats */ |
| 641 |
{ U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); |
| 642 |
ZSTD_seqToCodes(seqStorePtr); |
| 643 |
|
| 644 |
{ const BYTE* codePtr = seqStorePtr->ofCode; |
| 645 |
U32 u; |
| 646 |
for (u=0; u<nbSeq; u++) offsetcodeCount[codePtr[u]]++; |
| 647 |
} |
| 648 |
|
| 649 |
{ const BYTE* codePtr = seqStorePtr->mlCode; |
| 650 |
U32 u; |
| 651 |
for (u=0; u<nbSeq; u++) matchlengthCount[codePtr[u]]++; |
| 652 |
} |
| 653 |
|
| 654 |
{ const BYTE* codePtr = seqStorePtr->llCode; |
| 655 |
U32 u; |
| 656 |
for (u=0; u<nbSeq; u++) litlengthCount[codePtr[u]]++; |
| 657 |
} |
| 658 |
|
| 659 |
if (nbSeq >= 2) { /* rep offsets */ |
| 660 |
const seqDef* const seq = seqStorePtr->sequencesStart; |
| 661 |
U32 offset1 = seq[0].offset - 3; |
| 662 |
U32 offset2 = seq[1].offset - 3; |
| 663 |
if (offset1 >= MAXREPOFFSET) offset1 = 0; |
| 664 |
if (offset2 >= MAXREPOFFSET) offset2 = 0; |
| 665 |
repOffsets[offset1] += 3; |
| 666 |
repOffsets[offset2] += 1; |
| 667 |
} } } |
| 668 |
} |
| 669 |
|
| 670 |
static size_t ZDICT_totalSampleSize(const size_t* fileSizes, unsigned nbFiles) |
| 671 |
{ |
| 672 |
size_t total=0; |
| 673 |
unsigned u; |
| 674 |
for (u=0; u<nbFiles; u++) total += fileSizes[u]; |
| 675 |
return total; |
| 676 |
} |
| 677 |
|
| 678 |
typedef struct { U32 offset; U32 count; } offsetCount_t; |
| 679 |
|
| 680 |
static void ZDICT_insertSortCount(offsetCount_t table[ZSTD_REP_NUM+1], U32 val, U32 count) |
| 681 |
{ |
| 682 |
U32 u; |
| 683 |
table[ZSTD_REP_NUM].offset = val; |
| 684 |
table[ZSTD_REP_NUM].count = count; |
| 685 |
for (u=ZSTD_REP_NUM; u>0; u--) { |
| 686 |
offsetCount_t tmp; |
| 687 |
if (table[u-1].count >= table[u].count) break; |
| 688 |
tmp = table[u-1]; |
| 689 |
table[u-1] = table[u]; |
| 690 |
table[u] = tmp; |
| 691 |
} |
| 692 |
} |
| 693 |
|
| 694 |
/* ZDICT_flatLit() : |
| 695 |
* rewrite `countLit` to contain a mostly flat but still compressible distribution of literals. |
| 696 |
* necessary to avoid generating a non-compressible distribution that HUF_writeCTable() cannot encode. |
| 697 |
*/ |
| 698 |
static void ZDICT_flatLit(unsigned* countLit) |
| 699 |
{ |
| 700 |
int u; |
| 701 |
for (u=1; u<256; u++) countLit[u] = 2; |
| 702 |
countLit[0] = 4; |
| 703 |
countLit[253] = 1; |
| 704 |
countLit[254] = 1; |
| 705 |
} |
| 706 |
|
| 707 |
#define OFFCODE_MAX 30 /* only applicable to first block */ |
| 708 |
static size_t ZDICT_analyzeEntropy(void* dstBuffer, size_t maxDstSize, |
| 709 |
unsigned compressionLevel, |
| 710 |
const void* srcBuffer, const size_t* fileSizes, unsigned nbFiles, |
| 711 |
const void* dictBuffer, size_t dictBufferSize, |
| 712 |
unsigned notificationLevel) |
| 713 |
{ |
| 714 |
unsigned countLit[256]; |
| 715 |
HUF_CREATE_STATIC_CTABLE(hufTable, 255); |
| 716 |
unsigned offcodeCount[OFFCODE_MAX+1]; |
| 717 |
short offcodeNCount[OFFCODE_MAX+1]; |
| 718 |
U32 offcodeMax = ZSTD_highbit32((U32)(dictBufferSize + 128 KB)); |
| 719 |
unsigned matchLengthCount[MaxML+1]; |
| 720 |
short matchLengthNCount[MaxML+1]; |
| 721 |
unsigned litLengthCount[MaxLL+1]; |
| 722 |
short litLengthNCount[MaxLL+1]; |
| 723 |
U32 repOffset[MAXREPOFFSET]; |
| 724 |
offsetCount_t bestRepOffset[ZSTD_REP_NUM+1]; |
| 725 |
EStats_ress_t esr = { NULL, NULL, NULL }; |
| 726 |
ZSTD_parameters params; |
| 727 |
U32 u, huffLog = 11, Offlog = OffFSELog, mlLog = MLFSELog, llLog = LLFSELog, total; |
| 728 |
size_t pos = 0, errorCode; |
| 729 |
size_t eSize = 0; |
| 730 |
size_t const totalSrcSize = ZDICT_totalSampleSize(fileSizes, nbFiles); |
| 731 |
size_t const averageSampleSize = totalSrcSize / (nbFiles + !nbFiles); |
| 732 |
BYTE* dstPtr = (BYTE*)dstBuffer; |
| 733 |
|
| 734 |
/* init */ |
| 735 |
DEBUGLOG(4, "ZDICT_analyzeEntropy"); |
| 736 |
if (offcodeMax>OFFCODE_MAX) { eSize = ERROR(dictionaryCreation_failed); goto _cleanup; } /* too large dictionary */ |
| 737 |
for (u=0; u<256; u++) countLit[u] = 1; /* any character must be described */ |
| 738 |
for (u=0; u<=offcodeMax; u++) offcodeCount[u] = 1; |
| 739 |
for (u=0; u<=MaxML; u++) matchLengthCount[u] = 1; |
| 740 |
for (u=0; u<=MaxLL; u++) litLengthCount[u] = 1; |
| 741 |
memset(repOffset, 0, sizeof(repOffset)); |
| 742 |
repOffset[1] = repOffset[4] = repOffset[8] = 1; |
| 743 |
memset(bestRepOffset, 0, sizeof(bestRepOffset)); |
| 744 |
if (compressionLevel==0) compressionLevel = g_compressionLevel_default; |
| 745 |
params = ZSTD_getParams(compressionLevel, averageSampleSize, dictBufferSize); |
| 746 |
|
| 747 |
esr.dict = ZSTD_createCDict_advanced(dictBuffer, dictBufferSize, ZSTD_dlm_byRef, ZSTD_dct_rawContent, params.cParams, ZSTD_defaultCMem); |
| 748 |
esr.zc = ZSTD_createCCtx(); |
| 749 |
esr.workPlace = malloc(ZSTD_BLOCKSIZE_MAX); |
| 750 |
if (!esr.dict || !esr.zc || !esr.workPlace) { |
| 751 |
eSize = ERROR(memory_allocation); |
| 752 |
DISPLAYLEVEL(1, "Not enough memory \n"); |
| 753 |
goto _cleanup; |
| 754 |
} |
| 755 |
|
| 756 |
/* collect stats on all samples */ |
| 757 |
for (u=0; u<nbFiles; u++) { |
| 758 |
ZDICT_countEStats(esr, ¶ms, |
| 759 |
countLit, offcodeCount, matchLengthCount, litLengthCount, repOffset, |
| 760 |
(const char*)srcBuffer + pos, fileSizes[u], |
| 761 |
notificationLevel); |
| 762 |
pos += fileSizes[u]; |
| 763 |
} |
| 764 |
|
| 765 |
/* analyze, build stats, starting with literals */ |
| 766 |
{ size_t maxNbBits = HUF_buildCTable (hufTable, countLit, 255, huffLog); |
| 767 |
if (HUF_isError(maxNbBits)) { |
| 768 |
eSize = maxNbBits; |
| 769 |
DISPLAYLEVEL(1, " HUF_buildCTable error \n"); |
| 770 |
goto _cleanup; |
| 771 |
} |
| 772 |
if (maxNbBits==8) { /* not compressible : will fail on HUF_writeCTable() */ |
| 773 |
DISPLAYLEVEL(2, "warning : pathological dataset : literals are not compressible : samples are noisy or too regular \n"); |
| 774 |
ZDICT_flatLit(countLit); /* replace distribution by a fake "mostly flat but still compressible" distribution, that HUF_writeCTable() can encode */ |
| 775 |
maxNbBits = HUF_buildCTable (hufTable, countLit, 255, huffLog); |
| 776 |
assert(maxNbBits==9); |
| 777 |
} |
| 778 |
huffLog = (U32)maxNbBits; |
| 779 |
} |
| 780 |
|
| 781 |
/* looking for most common first offsets */ |
| 782 |
{ U32 offset; |
| 783 |
for (offset=1; offset<MAXREPOFFSET; offset++) |
| 784 |
ZDICT_insertSortCount(bestRepOffset, offset, repOffset[offset]); |
| 785 |
} |
| 786 |
/* note : the result of this phase should be used to better appreciate the impact on statistics */ |
| 787 |
|
| 788 |
total=0; for (u=0; u<=offcodeMax; u++) total+=offcodeCount[u]; |
| 789 |
errorCode = FSE_normalizeCount(offcodeNCount, Offlog, offcodeCount, total, offcodeMax); |
| 790 |
if (FSE_isError(errorCode)) { |
| 791 |
eSize = errorCode; |
| 792 |
DISPLAYLEVEL(1, "FSE_normalizeCount error with offcodeCount \n"); |
| 793 |
goto _cleanup; |
| 794 |
} |
| 795 |
Offlog = (U32)errorCode; |
| 796 |
|
| 797 |
total=0; for (u=0; u<=MaxML; u++) total+=matchLengthCount[u]; |
| 798 |
errorCode = FSE_normalizeCount(matchLengthNCount, mlLog, matchLengthCount, total, MaxML); |
| 799 |
if (FSE_isError(errorCode)) { |
| 800 |
eSize = errorCode; |
| 801 |
DISPLAYLEVEL(1, "FSE_normalizeCount error with matchLengthCount \n"); |
| 802 |
goto _cleanup; |
| 803 |
} |
| 804 |
mlLog = (U32)errorCode; |
| 805 |
|
| 806 |
total=0; for (u=0; u<=MaxLL; u++) total+=litLengthCount[u]; |
| 807 |
errorCode = FSE_normalizeCount(litLengthNCount, llLog, litLengthCount, total, MaxLL); |
| 808 |
if (FSE_isError(errorCode)) { |
| 809 |
eSize = errorCode; |
| 810 |
DISPLAYLEVEL(1, "FSE_normalizeCount error with litLengthCount \n"); |
| 811 |
goto _cleanup; |
| 812 |
} |
| 813 |
llLog = (U32)errorCode; |
| 814 |
|
| 815 |
/* write result to buffer */ |
| 816 |
{ size_t const hhSize = HUF_writeCTable(dstPtr, maxDstSize, hufTable, 255, huffLog); |
| 817 |
if (HUF_isError(hhSize)) { |
| 818 |
eSize = hhSize; |
| 819 |
DISPLAYLEVEL(1, "HUF_writeCTable error \n"); |
| 820 |
goto _cleanup; |
| 821 |
} |
| 822 |
dstPtr += hhSize; |
| 823 |
maxDstSize -= hhSize; |
| 824 |
eSize += hhSize; |
| 825 |
} |
| 826 |
|
| 827 |
{ size_t const ohSize = FSE_writeNCount(dstPtr, maxDstSize, offcodeNCount, OFFCODE_MAX, Offlog); |
| 828 |
if (FSE_isError(ohSize)) { |
| 829 |
eSize = ohSize; |
| 830 |
DISPLAYLEVEL(1, "FSE_writeNCount error with offcodeNCount \n"); |
| 831 |
goto _cleanup; |
| 832 |
} |
| 833 |
dstPtr += ohSize; |
| 834 |
maxDstSize -= ohSize; |
| 835 |
eSize += ohSize; |
| 836 |
} |
| 837 |
|
| 838 |
{ size_t const mhSize = FSE_writeNCount(dstPtr, maxDstSize, matchLengthNCount, MaxML, mlLog); |
| 839 |
if (FSE_isError(mhSize)) { |
| 840 |
eSize = mhSize; |
| 841 |
DISPLAYLEVEL(1, "FSE_writeNCount error with matchLengthNCount \n"); |
| 842 |
goto _cleanup; |
| 843 |
} |
| 844 |
dstPtr += mhSize; |
| 845 |
maxDstSize -= mhSize; |
| 846 |
eSize += mhSize; |
| 847 |
} |
| 848 |
|
| 849 |
{ size_t const lhSize = FSE_writeNCount(dstPtr, maxDstSize, litLengthNCount, MaxLL, llLog); |
| 850 |
if (FSE_isError(lhSize)) { |
| 851 |
eSize = lhSize; |
| 852 |
DISPLAYLEVEL(1, "FSE_writeNCount error with litlengthNCount \n"); |
| 853 |
goto _cleanup; |
| 854 |
} |
| 855 |
dstPtr += lhSize; |
| 856 |
maxDstSize -= lhSize; |
| 857 |
eSize += lhSize; |
| 858 |
} |
| 859 |
|
| 860 |
if (maxDstSize<12) { |
| 861 |
eSize = ERROR(dstSize_tooSmall); |
| 862 |
DISPLAYLEVEL(1, "not enough space to write RepOffsets \n"); |
| 863 |
goto _cleanup; |
| 864 |
} |
| 865 |
# if 0 |
| 866 |
MEM_writeLE32(dstPtr+0, bestRepOffset[0].offset); |
| 867 |
MEM_writeLE32(dstPtr+4, bestRepOffset[1].offset); |
| 868 |
MEM_writeLE32(dstPtr+8, bestRepOffset[2].offset); |
| 869 |
#else |
| 870 |
/* at this stage, we don't use the result of "most common first offset", |
| 871 |
as the impact of statistics is not properly evaluated */ |
| 872 |
MEM_writeLE32(dstPtr+0, repStartValue[0]); |
| 873 |
MEM_writeLE32(dstPtr+4, repStartValue[1]); |
| 874 |
MEM_writeLE32(dstPtr+8, repStartValue[2]); |
| 875 |
#endif |
| 876 |
eSize += 12; |
| 877 |
|
| 878 |
_cleanup: |
| 879 |
ZSTD_freeCDict(esr.dict); |
| 880 |
ZSTD_freeCCtx(esr.zc); |
| 881 |
free(esr.workPlace); |
| 882 |
|
| 883 |
return eSize; |
| 884 |
} |
| 885 |
|
| 886 |
|
| 887 |
|
| 888 |
size_t ZDICT_finalizeDictionary(void* dictBuffer, size_t dictBufferCapacity, |
| 889 |
const void* customDictContent, size_t dictContentSize, |
| 890 |
const void* samplesBuffer, const size_t* samplesSizes, |
| 891 |
unsigned nbSamples, ZDICT_params_t params) |
| 892 |
{ |
| 893 |
size_t hSize; |
| 894 |
#define HBUFFSIZE 256 /* should prove large enough for all entropy headers */ |
| 895 |
BYTE header[HBUFFSIZE]; |
| 896 |
int const compressionLevel = (params.compressionLevel == 0) ? g_compressionLevel_default : params.compressionLevel; |
| 897 |
U32 const notificationLevel = params.notificationLevel; |
| 898 |
|
| 899 |
/* check conditions */ |
| 900 |
DEBUGLOG(4, "ZDICT_finalizeDictionary"); |
| 901 |
if (dictBufferCapacity < dictContentSize) return ERROR(dstSize_tooSmall); |
| 902 |
if (dictContentSize < ZDICT_CONTENTSIZE_MIN) return ERROR(srcSize_wrong); |
| 903 |
if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) return ERROR(dstSize_tooSmall); |
| 904 |
|
| 905 |
/* dictionary header */ |
| 906 |
MEM_writeLE32(header, ZSTD_MAGIC_DICTIONARY); |
| 907 |
{ U64 const randomID = XXH64(customDictContent, dictContentSize, 0); |
| 908 |
U32 const compliantID = (randomID % ((1U<<31)-32768)) + 32768; |
| 909 |
U32 const dictID = params.dictID ? params.dictID : compliantID; |
| 910 |
MEM_writeLE32(header+4, dictID); |
| 911 |
} |
| 912 |
hSize = 8; |
| 913 |
|
| 914 |
/* entropy tables */ |
| 915 |
DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */ |
| 916 |
DISPLAYLEVEL(2, "statistics ... \n"); |
| 917 |
{ size_t const eSize = ZDICT_analyzeEntropy(header+hSize, HBUFFSIZE-hSize, |
| 918 |
compressionLevel, |
| 919 |
samplesBuffer, samplesSizes, nbSamples, |
| 920 |
customDictContent, dictContentSize, |
| 921 |
notificationLevel); |
| 922 |
if (ZDICT_isError(eSize)) return eSize; |
| 923 |
hSize += eSize; |
| 924 |
} |
| 925 |
|
| 926 |
/* copy elements in final buffer ; note : src and dst buffer can overlap */ |
| 927 |
if (hSize + dictContentSize > dictBufferCapacity) dictContentSize = dictBufferCapacity - hSize; |
| 928 |
{ size_t const dictSize = hSize + dictContentSize; |
| 929 |
char* dictEnd = (char*)dictBuffer + dictSize; |
| 930 |
memmove(dictEnd - dictContentSize, customDictContent, dictContentSize); |
| 931 |
memcpy(dictBuffer, header, hSize); |
| 932 |
return dictSize; |
| 933 |
} |
| 934 |
} |
| 935 |
|
| 936 |
|
| 937 |
static size_t ZDICT_addEntropyTablesFromBuffer_advanced( |
| 938 |
void* dictBuffer, size_t dictContentSize, size_t dictBufferCapacity, |
| 939 |
const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples, |
| 940 |
ZDICT_params_t params) |
| 941 |
{ |
| 942 |
int const compressionLevel = (params.compressionLevel == 0) ? g_compressionLevel_default : params.compressionLevel; |
| 943 |
U32 const notificationLevel = params.notificationLevel; |
| 944 |
size_t hSize = 8; |
| 945 |
|
| 946 |
/* calculate entropy tables */ |
| 947 |
DISPLAYLEVEL(2, "\r%70s\r", ""); /* clean display line */ |
| 948 |
DISPLAYLEVEL(2, "statistics ... \n"); |
| 949 |
{ size_t const eSize = ZDICT_analyzeEntropy((char*)dictBuffer+hSize, dictBufferCapacity-hSize, |
| 950 |
compressionLevel, |
| 951 |
samplesBuffer, samplesSizes, nbSamples, |
| 952 |
(char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize, |
| 953 |
notificationLevel); |
| 954 |
if (ZDICT_isError(eSize)) return eSize; |
| 955 |
hSize += eSize; |
| 956 |
} |
| 957 |
|
| 958 |
/* add dictionary header (after entropy tables) */ |
| 959 |
MEM_writeLE32(dictBuffer, ZSTD_MAGIC_DICTIONARY); |
| 960 |
{ U64 const randomID = XXH64((char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize, 0); |
| 961 |
U32 const compliantID = (randomID % ((1U<<31)-32768)) + 32768; |
| 962 |
U32 const dictID = params.dictID ? params.dictID : compliantID; |
| 963 |
MEM_writeLE32((char*)dictBuffer+4, dictID); |
| 964 |
} |
| 965 |
|
| 966 |
if (hSize + dictContentSize < dictBufferCapacity) |
| 967 |
memmove((char*)dictBuffer + hSize, (char*)dictBuffer + dictBufferCapacity - dictContentSize, dictContentSize); |
| 968 |
return MIN(dictBufferCapacity, hSize+dictContentSize); |
| 969 |
} |
| 970 |
|
| 971 |
/* Hidden declaration for dbio.c */ |
| 972 |
size_t ZDICT_trainFromBuffer_unsafe_legacy( |
| 973 |
void* dictBuffer, size_t maxDictSize, |
| 974 |
const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples, |
| 975 |
ZDICT_legacy_params_t params); |
| 976 |
/*! ZDICT_trainFromBuffer_unsafe_legacy() : |
| 977 |
* Warning : `samplesBuffer` must be followed by noisy guard band. |
| 978 |
* @return : size of dictionary, or an error code which can be tested with ZDICT_isError() |
| 979 |
*/ |
| 980 |
size_t ZDICT_trainFromBuffer_unsafe_legacy( |
| 981 |
void* dictBuffer, size_t maxDictSize, |
| 982 |
const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples, |
| 983 |
ZDICT_legacy_params_t params) |
| 984 |
{ |
| 985 |
U32 const dictListSize = MAX(MAX(DICTLISTSIZE_DEFAULT, nbSamples), (U32)(maxDictSize/16)); |
| 986 |
dictItem* const dictList = (dictItem*)malloc(dictListSize * sizeof(*dictList)); |
| 987 |
unsigned const selectivity = params.selectivityLevel == 0 ? g_selectivity_default : params.selectivityLevel; |
| 988 |
unsigned const minRep = (selectivity > 30) ? MINRATIO : nbSamples >> selectivity; |
| 989 |
size_t const targetDictSize = maxDictSize; |
| 990 |
size_t const samplesBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples); |
| 991 |
size_t dictSize = 0; |
| 992 |
U32 const notificationLevel = params.zParams.notificationLevel; |
| 993 |
|
| 994 |
/* checks */ |
| 995 |
if (!dictList) return ERROR(memory_allocation); |
| 996 |
if (maxDictSize < ZDICT_DICTSIZE_MIN) { free(dictList); return ERROR(dstSize_tooSmall); } /* requested dictionary size is too small */ |
| 997 |
if (samplesBuffSize < ZDICT_MIN_SAMPLES_SIZE) { free(dictList); return ERROR(dictionaryCreation_failed); } /* not enough source to create dictionary */ |
| 998 |
|
| 999 |
/* init */ |
| 1000 |
ZDICT_initDictItem(dictList); |
| 1001 |
|
| 1002 |
/* build dictionary */ |
| 1003 |
ZDICT_trainBuffer_legacy(dictList, dictListSize, |
| 1004 |
samplesBuffer, samplesBuffSize, |
| 1005 |
samplesSizes, nbSamples, |
| 1006 |
minRep, notificationLevel); |
| 1007 |
|
| 1008 |
/* display best matches */ |
| 1009 |
if (params.zParams.notificationLevel>= 3) { |
| 1010 |
unsigned const nb = MIN(25, dictList[0].pos); |
| 1011 |
unsigned const dictContentSize = ZDICT_dictSize(dictList); |
| 1012 |
unsigned u; |
| 1013 |
DISPLAYLEVEL(3, "\n %u segments found, of total size %u \n", (unsigned)dictList[0].pos-1, dictContentSize); |
| 1014 |
DISPLAYLEVEL(3, "list %u best segments \n", nb-1); |
| 1015 |
for (u=1; u<nb; u++) { |
| 1016 |
unsigned const pos = dictList[u].pos; |
| 1017 |
unsigned const length = dictList[u].length; |
| 1018 |
U32 const printedLength = MIN(40, length); |
| 1019 |
if ((pos > samplesBuffSize) || ((pos + length) > samplesBuffSize)) { |
| 1020 |
free(dictList); |
| 1021 |
return ERROR(GENERIC); /* should never happen */ |
| 1022 |
} |
| 1023 |
DISPLAYLEVEL(3, "%3u:%3u bytes at pos %8u, savings %7u bytes |", |
| 1024 |
u, length, pos, (unsigned)dictList[u].savings); |
| 1025 |
ZDICT_printHex((const char*)samplesBuffer+pos, printedLength); |
| 1026 |
DISPLAYLEVEL(3, "| \n"); |
| 1027 |
} } |
| 1028 |
|
| 1029 |
|
| 1030 |
/* create dictionary */ |
| 1031 |
{ unsigned dictContentSize = ZDICT_dictSize(dictList); |
| 1032 |
if (dictContentSize < ZDICT_CONTENTSIZE_MIN) { free(dictList); return ERROR(dictionaryCreation_failed); } /* dictionary content too small */ |
| 1033 |
if (dictContentSize < targetDictSize/4) { |
| 1034 |
DISPLAYLEVEL(2, "! warning : selected content significantly smaller than requested (%u < %u) \n", dictContentSize, (unsigned)maxDictSize); |
| 1035 |
if (samplesBuffSize < 10 * targetDictSize) |
| 1036 |
DISPLAYLEVEL(2, "! consider increasing the number of samples (total size : %u MB)\n", (unsigned)(samplesBuffSize>>20)); |
| 1037 |
if (minRep > MINRATIO) { |
| 1038 |
DISPLAYLEVEL(2, "! consider increasing selectivity to produce larger dictionary (-s%u) \n", selectivity+1); |
| 1039 |
DISPLAYLEVEL(2, "! note : larger dictionaries are not necessarily better, test its efficiency on samples \n"); |
| 1040 |
} |
| 1041 |
} |
| 1042 |
|
| 1043 |
if ((dictContentSize > targetDictSize*3) && (nbSamples > 2*MINRATIO) && (selectivity>1)) { |
| 1044 |
unsigned proposedSelectivity = selectivity-1; |
| 1045 |
while ((nbSamples >> proposedSelectivity) <= MINRATIO) { proposedSelectivity--; } |
| 1046 |
DISPLAYLEVEL(2, "! note : calculated dictionary significantly larger than requested (%u > %u) \n", dictContentSize, (unsigned)maxDictSize); |
| 1047 |
DISPLAYLEVEL(2, "! consider increasing dictionary size, or produce denser dictionary (-s%u) \n", proposedSelectivity); |
| 1048 |
DISPLAYLEVEL(2, "! always test dictionary efficiency on real samples \n"); |
| 1049 |
} |
| 1050 |
|
| 1051 |
/* limit dictionary size */ |
| 1052 |
{ U32 const max = dictList->pos; /* convention : nb of useful elts within dictList */ |
| 1053 |
U32 currentSize = 0; |
| 1054 |
U32 n; for (n=1; n<max; n++) { |
| 1055 |
currentSize += dictList[n].length; |
| 1056 |
if (currentSize > targetDictSize) { currentSize -= dictList[n].length; break; } |
| 1057 |
} |
| 1058 |
dictList->pos = n; |
| 1059 |
dictContentSize = currentSize; |
| 1060 |
} |
| 1061 |
|
| 1062 |
/* build dict content */ |
| 1063 |
{ U32 u; |
| 1064 |
BYTE* ptr = (BYTE*)dictBuffer + maxDictSize; |
| 1065 |
for (u=1; u<dictList->pos; u++) { |
| 1066 |
U32 l = dictList[u].length; |
| 1067 |
ptr -= l; |
| 1068 |
if (ptr<(BYTE*)dictBuffer) { free(dictList); return ERROR(GENERIC); } /* should not happen */ |
| 1069 |
memcpy(ptr, (const char*)samplesBuffer+dictList[u].pos, l); |
| 1070 |
} } |
| 1071 |
|
| 1072 |
dictSize = ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, maxDictSize, |
| 1073 |
samplesBuffer, samplesSizes, nbSamples, |
| 1074 |
params.zParams); |
| 1075 |
} |
| 1076 |
|
| 1077 |
/* clean up */ |
| 1078 |
free(dictList); |
| 1079 |
return dictSize; |
| 1080 |
} |
| 1081 |
|
| 1082 |
|
| 1083 |
/* ZDICT_trainFromBuffer_legacy() : |
| 1084 |
* issue : samplesBuffer need to be followed by a noisy guard band. |
| 1085 |
* work around : duplicate the buffer, and add the noise */ |
| 1086 |
size_t ZDICT_trainFromBuffer_legacy(void* dictBuffer, size_t dictBufferCapacity, |
| 1087 |
const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples, |
| 1088 |
ZDICT_legacy_params_t params) |
| 1089 |
{ |
| 1090 |
size_t result; |
| 1091 |
void* newBuff; |
| 1092 |
size_t const sBuffSize = ZDICT_totalSampleSize(samplesSizes, nbSamples); |
| 1093 |
if (sBuffSize < ZDICT_MIN_SAMPLES_SIZE) return 0; /* not enough content => no dictionary */ |
| 1094 |
|
| 1095 |
newBuff = malloc(sBuffSize + NOISELENGTH); |
| 1096 |
if (!newBuff) return ERROR(memory_allocation); |
| 1097 |
|
| 1098 |
memcpy(newBuff, samplesBuffer, sBuffSize); |
| 1099 |
ZDICT_fillNoise((char*)newBuff + sBuffSize, NOISELENGTH); /* guard band, for end of buffer condition */ |
| 1100 |
|
| 1101 |
result = |
| 1102 |
ZDICT_trainFromBuffer_unsafe_legacy(dictBuffer, dictBufferCapacity, newBuff, |
| 1103 |
samplesSizes, nbSamples, params); |
| 1104 |
free(newBuff); |
| 1105 |
return result; |
| 1106 |
} |
| 1107 |
|
| 1108 |
|
| 1109 |
size_t ZDICT_trainFromBuffer(void* dictBuffer, size_t dictBufferCapacity, |
| 1110 |
const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples) |
| 1111 |
{ |
| 1112 |
ZDICT_fastCover_params_t params; |
| 1113 |
DEBUGLOG(3, "ZDICT_trainFromBuffer"); |
| 1114 |
memset(¶ms, 0, sizeof(params)); |
| 1115 |
params.d = 8; |
| 1116 |
params.steps = 4; |
| 1117 |
/* Default to level 6 since no compression level information is available */ |
| 1118 |
params.zParams.compressionLevel = 3; |
| 1119 |
#if defined(DEBUGLEVEL) && (DEBUGLEVEL>=1) |
| 1120 |
params.zParams.notificationLevel = DEBUGLEVEL; |
| 1121 |
#endif |
| 1122 |
return ZDICT_optimizeTrainFromBuffer_fastCover(dictBuffer, dictBufferCapacity, |
| 1123 |
samplesBuffer, samplesSizes, nbSamples, |
| 1124 |
¶ms); |
| 1125 |
} |
| 1126 |
|
| 1127 |
size_t ZDICT_addEntropyTablesFromBuffer(void* dictBuffer, size_t dictContentSize, size_t dictBufferCapacity, |
| 1128 |
const void* samplesBuffer, const size_t* samplesSizes, unsigned nbSamples) |
| 1129 |
{ |
| 1130 |
ZDICT_params_t params; |
| 1131 |
memset(¶ms, 0, sizeof(params)); |
| 1132 |
return ZDICT_addEntropyTablesFromBuffer_advanced(dictBuffer, dictContentSize, dictBufferCapacity, |
| 1133 |
samplesBuffer, samplesSizes, nbSamples, |
| 1134 |
params); |
| 1135 |
} |