| 1 |
/* ****************************************************************** |
| 2 |
* FSE : Finite State Entropy encoder |
| 3 |
* Copyright (c) 2013-2020, Yann Collet, Facebook, Inc. |
| 4 |
* |
| 5 |
* You can contact the author at : |
| 6 |
* - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy |
| 7 |
* - Public forum : https://groups.google.com/forum/#!forum/lz4c |
| 8 |
* |
| 9 |
* This source code is licensed under both the BSD-style license (found in the |
| 10 |
* LICENSE file in the root directory of this source tree) and the GPLv2 (found |
| 11 |
* in the COPYING file in the root directory of this source tree). |
| 12 |
* You may select, at your option, one of the above-listed licenses. |
| 13 |
****************************************************************** */ |
| 14 |
|
| 15 |
/* ************************************************************** |
| 16 |
* Includes |
| 17 |
****************************************************************/ |
| 18 |
#include <stdlib.h> /* malloc, free, qsort */ |
| 19 |
#include <string.h> /* memcpy, memset */ |
| 20 |
#include "../common/compiler.h" |
| 21 |
#include "../common/mem.h" /* U32, U16, etc. */ |
| 22 |
#include "../common/debug.h" /* assert, DEBUGLOG */ |
| 23 |
#include "hist.h" /* HIST_count_wksp */ |
| 24 |
#include "../common/bitstream.h" |
| 25 |
#define FSE_STATIC_LINKING_ONLY |
| 26 |
#include "../common/fse.h" |
| 27 |
#include "../common/error_private.h" |
| 28 |
|
| 29 |
|
| 30 |
/* ************************************************************** |
| 31 |
* Error Management |
| 32 |
****************************************************************/ |
| 33 |
#define FSE_isError ERR_isError |
| 34 |
|
| 35 |
|
| 36 |
/* ************************************************************** |
| 37 |
* Templates |
| 38 |
****************************************************************/ |
| 39 |
/* |
| 40 |
designed to be included |
| 41 |
for type-specific functions (template emulation in C) |
| 42 |
Objective is to write these functions only once, for improved maintenance |
| 43 |
*/ |
| 44 |
|
| 45 |
/* safety checks */ |
| 46 |
#ifndef FSE_FUNCTION_EXTENSION |
| 47 |
# error "FSE_FUNCTION_EXTENSION must be defined" |
| 48 |
#endif |
| 49 |
#ifndef FSE_FUNCTION_TYPE |
| 50 |
# error "FSE_FUNCTION_TYPE must be defined" |
| 51 |
#endif |
| 52 |
|
| 53 |
/* Function names */ |
| 54 |
#define FSE_CAT(X,Y) X##Y |
| 55 |
#define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y) |
| 56 |
#define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y) |
| 57 |
|
| 58 |
|
| 59 |
/* Function templates */ |
| 60 |
|
| 61 |
/* FSE_buildCTable_wksp() : |
| 62 |
* Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`). |
| 63 |
* wkspSize should be sized to handle worst case situation, which is `1<<max_tableLog * sizeof(FSE_FUNCTION_TYPE)` |
| 64 |
* workSpace must also be properly aligned with FSE_FUNCTION_TYPE requirements |
| 65 |
*/ |
| 66 |
size_t FSE_buildCTable_wksp(FSE_CTable* ct, |
| 67 |
const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, |
| 68 |
void* workSpace, size_t wkspSize) |
| 69 |
{ |
| 70 |
U32 const tableSize = 1 << tableLog; |
| 71 |
U32 const tableMask = tableSize - 1; |
| 72 |
void* const ptr = ct; |
| 73 |
U16* const tableU16 = ( (U16*) ptr) + 2; |
| 74 |
void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableLog ? tableSize>>1 : 1) ; |
| 75 |
FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT); |
| 76 |
U32 const step = FSE_TABLESTEP(tableSize); |
| 77 |
U32 cumul[FSE_MAX_SYMBOL_VALUE+2]; |
| 78 |
|
| 79 |
FSE_FUNCTION_TYPE* const tableSymbol = (FSE_FUNCTION_TYPE*)workSpace; |
| 80 |
U32 highThreshold = tableSize-1; |
| 81 |
|
| 82 |
/* CTable header */ |
| 83 |
if (((size_t)1 << tableLog) * sizeof(FSE_FUNCTION_TYPE) > wkspSize) return ERROR(tableLog_tooLarge); |
| 84 |
tableU16[-2] = (U16) tableLog; |
| 85 |
tableU16[-1] = (U16) maxSymbolValue; |
| 86 |
assert(tableLog < 16); /* required for threshold strategy to work */ |
| 87 |
|
| 88 |
/* For explanations on how to distribute symbol values over the table : |
| 89 |
* http://fastcompression.blogspot.fr/2014/02/fse-distributing-symbol-values.html */ |
| 90 |
|
| 91 |
#ifdef __clang_analyzer__ |
| 92 |
memset(tableSymbol, 0, sizeof(*tableSymbol) * tableSize); /* useless initialization, just to keep scan-build happy */ |
| 93 |
#endif |
| 94 |
|
| 95 |
/* symbol start positions */ |
| 96 |
{ U32 u; |
| 97 |
cumul[0] = 0; |
| 98 |
for (u=1; u <= maxSymbolValue+1; u++) { |
| 99 |
if (normalizedCounter[u-1]==-1) { /* Low proba symbol */ |
| 100 |
cumul[u] = cumul[u-1] + 1; |
| 101 |
tableSymbol[highThreshold--] = (FSE_FUNCTION_TYPE)(u-1); |
| 102 |
} else { |
| 103 |
cumul[u] = cumul[u-1] + normalizedCounter[u-1]; |
| 104 |
} } |
| 105 |
cumul[maxSymbolValue+1] = tableSize+1; |
| 106 |
} |
| 107 |
|
| 108 |
/* Spread symbols */ |
| 109 |
{ U32 position = 0; |
| 110 |
U32 symbol; |
| 111 |
for (symbol=0; symbol<=maxSymbolValue; symbol++) { |
| 112 |
int nbOccurrences; |
| 113 |
int const freq = normalizedCounter[symbol]; |
| 114 |
for (nbOccurrences=0; nbOccurrences<freq; nbOccurrences++) { |
| 115 |
tableSymbol[position] = (FSE_FUNCTION_TYPE)symbol; |
| 116 |
position = (position + step) & tableMask; |
| 117 |
while (position > highThreshold) |
| 118 |
position = (position + step) & tableMask; /* Low proba area */ |
| 119 |
} } |
| 120 |
|
| 121 |
assert(position==0); /* Must have initialized all positions */ |
| 122 |
} |
| 123 |
|
| 124 |
/* Build table */ |
| 125 |
{ U32 u; for (u=0; u<tableSize; u++) { |
| 126 |
FSE_FUNCTION_TYPE s = tableSymbol[u]; /* note : static analyzer may not understand tableSymbol is properly initialized */ |
| 127 |
tableU16[cumul[s]++] = (U16) (tableSize+u); /* TableU16 : sorted by symbol order; gives next state value */ |
| 128 |
} } |
| 129 |
|
| 130 |
/* Build Symbol Transformation Table */ |
| 131 |
{ unsigned total = 0; |
| 132 |
unsigned s; |
| 133 |
for (s=0; s<=maxSymbolValue; s++) { |
| 134 |
switch (normalizedCounter[s]) |
| 135 |
{ |
| 136 |
case 0: |
| 137 |
/* filling nonetheless, for compatibility with FSE_getMaxNbBits() */ |
| 138 |
symbolTT[s].deltaNbBits = ((tableLog+1) << 16) - (1<<tableLog); |
| 139 |
break; |
| 140 |
|
| 141 |
case -1: |
| 142 |
case 1: |
| 143 |
symbolTT[s].deltaNbBits = (tableLog << 16) - (1<<tableLog); |
| 144 |
symbolTT[s].deltaFindState = total - 1; |
| 145 |
total ++; |
| 146 |
break; |
| 147 |
default : |
| 148 |
{ |
| 149 |
U32 const maxBitsOut = tableLog - BIT_highbit32 (normalizedCounter[s]-1); |
| 150 |
U32 const minStatePlus = normalizedCounter[s] << maxBitsOut; |
| 151 |
symbolTT[s].deltaNbBits = (maxBitsOut << 16) - minStatePlus; |
| 152 |
symbolTT[s].deltaFindState = total - normalizedCounter[s]; |
| 153 |
total += normalizedCounter[s]; |
| 154 |
} } } } |
| 155 |
|
| 156 |
#if 0 /* debug : symbol costs */ |
| 157 |
DEBUGLOG(5, "\n --- table statistics : "); |
| 158 |
{ U32 symbol; |
| 159 |
for (symbol=0; symbol<=maxSymbolValue; symbol++) { |
| 160 |
DEBUGLOG(5, "%3u: w=%3i, maxBits=%u, fracBits=%.2f", |
| 161 |
symbol, normalizedCounter[symbol], |
| 162 |
FSE_getMaxNbBits(symbolTT, symbol), |
| 163 |
(double)FSE_bitCost(symbolTT, tableLog, symbol, 8) / 256); |
| 164 |
} |
| 165 |
} |
| 166 |
#endif |
| 167 |
|
| 168 |
return 0; |
| 169 |
} |
| 170 |
|
| 171 |
|
| 172 |
size_t FSE_buildCTable(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) |
| 173 |
{ |
| 174 |
FSE_FUNCTION_TYPE tableSymbol[FSE_MAX_TABLESIZE]; /* memset() is not necessary, even if static analyzer complain about it */ |
| 175 |
return FSE_buildCTable_wksp(ct, normalizedCounter, maxSymbolValue, tableLog, tableSymbol, sizeof(tableSymbol)); |
| 176 |
} |
| 177 |
|
| 178 |
|
| 179 |
|
| 180 |
#ifndef FSE_COMMONDEFS_ONLY |
| 181 |
|
| 182 |
|
| 183 |
/*-************************************************************** |
| 184 |
* FSE NCount encoding |
| 185 |
****************************************************************/ |
| 186 |
size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog) |
| 187 |
{ |
| 188 |
size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3; |
| 189 |
return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */ |
| 190 |
} |
| 191 |
|
| 192 |
static size_t |
| 193 |
FSE_writeNCount_generic (void* header, size_t headerBufferSize, |
| 194 |
const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, |
| 195 |
unsigned writeIsSafe) |
| 196 |
{ |
| 197 |
BYTE* const ostart = (BYTE*) header; |
| 198 |
BYTE* out = ostart; |
| 199 |
BYTE* const oend = ostart + headerBufferSize; |
| 200 |
int nbBits; |
| 201 |
const int tableSize = 1 << tableLog; |
| 202 |
int remaining; |
| 203 |
int threshold; |
| 204 |
U32 bitStream = 0; |
| 205 |
int bitCount = 0; |
| 206 |
unsigned symbol = 0; |
| 207 |
unsigned const alphabetSize = maxSymbolValue + 1; |
| 208 |
int previousIs0 = 0; |
| 209 |
|
| 210 |
/* Table Size */ |
| 211 |
bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount; |
| 212 |
bitCount += 4; |
| 213 |
|
| 214 |
/* Init */ |
| 215 |
remaining = tableSize+1; /* +1 for extra accuracy */ |
| 216 |
threshold = tableSize; |
| 217 |
nbBits = tableLog+1; |
| 218 |
|
| 219 |
while ((symbol < alphabetSize) && (remaining>1)) { /* stops at 1 */ |
| 220 |
if (previousIs0) { |
| 221 |
unsigned start = symbol; |
| 222 |
while ((symbol < alphabetSize) && !normalizedCounter[symbol]) symbol++; |
| 223 |
if (symbol == alphabetSize) break; /* incorrect distribution */ |
| 224 |
while (symbol >= start+24) { |
| 225 |
start+=24; |
| 226 |
bitStream += 0xFFFFU << bitCount; |
| 227 |
if ((!writeIsSafe) && (out > oend-2)) |
| 228 |
return ERROR(dstSize_tooSmall); /* Buffer overflow */ |
| 229 |
out[0] = (BYTE) bitStream; |
| 230 |
out[1] = (BYTE)(bitStream>>8); |
| 231 |
out+=2; |
| 232 |
bitStream>>=16; |
| 233 |
} |
| 234 |
while (symbol >= start+3) { |
| 235 |
start+=3; |
| 236 |
bitStream += 3 << bitCount; |
| 237 |
bitCount += 2; |
| 238 |
} |
| 239 |
bitStream += (symbol-start) << bitCount; |
| 240 |
bitCount += 2; |
| 241 |
if (bitCount>16) { |
| 242 |
if ((!writeIsSafe) && (out > oend - 2)) |
| 243 |
return ERROR(dstSize_tooSmall); /* Buffer overflow */ |
| 244 |
out[0] = (BYTE)bitStream; |
| 245 |
out[1] = (BYTE)(bitStream>>8); |
| 246 |
out += 2; |
| 247 |
bitStream >>= 16; |
| 248 |
bitCount -= 16; |
| 249 |
} } |
| 250 |
{ int count = normalizedCounter[symbol++]; |
| 251 |
int const max = (2*threshold-1) - remaining; |
| 252 |
remaining -= count < 0 ? -count : count; |
| 253 |
count++; /* +1 for extra accuracy */ |
| 254 |
if (count>=threshold) |
| 255 |
count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */ |
| 256 |
bitStream += count << bitCount; |
| 257 |
bitCount += nbBits; |
| 258 |
bitCount -= (count<max); |
| 259 |
previousIs0 = (count==1); |
| 260 |
if (remaining<1) return ERROR(GENERIC); |
| 261 |
while (remaining<threshold) { nbBits--; threshold>>=1; } |
| 262 |
} |
| 263 |
if (bitCount>16) { |
| 264 |
if ((!writeIsSafe) && (out > oend - 2)) |
| 265 |
return ERROR(dstSize_tooSmall); /* Buffer overflow */ |
| 266 |
out[0] = (BYTE)bitStream; |
| 267 |
out[1] = (BYTE)(bitStream>>8); |
| 268 |
out += 2; |
| 269 |
bitStream >>= 16; |
| 270 |
bitCount -= 16; |
| 271 |
} } |
| 272 |
|
| 273 |
if (remaining != 1) |
| 274 |
return ERROR(GENERIC); /* incorrect normalized distribution */ |
| 275 |
assert(symbol <= alphabetSize); |
| 276 |
|
| 277 |
/* flush remaining bitStream */ |
| 278 |
if ((!writeIsSafe) && (out > oend - 2)) |
| 279 |
return ERROR(dstSize_tooSmall); /* Buffer overflow */ |
| 280 |
out[0] = (BYTE)bitStream; |
| 281 |
out[1] = (BYTE)(bitStream>>8); |
| 282 |
out+= (bitCount+7) /8; |
| 283 |
|
| 284 |
return (out-ostart); |
| 285 |
} |
| 286 |
|
| 287 |
|
| 288 |
size_t FSE_writeNCount (void* buffer, size_t bufferSize, |
| 289 |
const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) |
| 290 |
{ |
| 291 |
if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported */ |
| 292 |
if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported */ |
| 293 |
|
| 294 |
if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog)) |
| 295 |
return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0); |
| 296 |
|
| 297 |
return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1 /* write in buffer is safe */); |
| 298 |
} |
| 299 |
|
| 300 |
|
| 301 |
/*-************************************************************** |
| 302 |
* FSE Compression Code |
| 303 |
****************************************************************/ |
| 304 |
|
| 305 |
FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog) |
| 306 |
{ |
| 307 |
size_t size; |
| 308 |
if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX; |
| 309 |
size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32); |
| 310 |
return (FSE_CTable*)malloc(size); |
| 311 |
} |
| 312 |
|
| 313 |
void FSE_freeCTable (FSE_CTable* ct) { free(ct); } |
| 314 |
|
| 315 |
/* provides the minimum logSize to safely represent a distribution */ |
| 316 |
static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue) |
| 317 |
{ |
| 318 |
U32 minBitsSrc = BIT_highbit32((U32)(srcSize)) + 1; |
| 319 |
U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2; |
| 320 |
U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols; |
| 321 |
assert(srcSize > 1); /* Not supported, RLE should be used instead */ |
| 322 |
return minBits; |
| 323 |
} |
| 324 |
|
| 325 |
unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus) |
| 326 |
{ |
| 327 |
U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus; |
| 328 |
U32 tableLog = maxTableLog; |
| 329 |
U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue); |
| 330 |
assert(srcSize > 1); /* Not supported, RLE should be used instead */ |
| 331 |
if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG; |
| 332 |
if (maxBitsSrc < tableLog) tableLog = maxBitsSrc; /* Accuracy can be reduced */ |
| 333 |
if (minBits > tableLog) tableLog = minBits; /* Need a minimum to safely represent all symbol values */ |
| 334 |
if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG; |
| 335 |
if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG; |
| 336 |
return tableLog; |
| 337 |
} |
| 338 |
|
| 339 |
unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue) |
| 340 |
{ |
| 341 |
return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2); |
| 342 |
} |
| 343 |
|
| 344 |
|
| 345 |
/* Secondary normalization method. |
| 346 |
To be used when primary method fails. */ |
| 347 |
|
| 348 |
static size_t FSE_normalizeM2(short* norm, U32 tableLog, const unsigned* count, size_t total, U32 maxSymbolValue) |
| 349 |
{ |
| 350 |
short const NOT_YET_ASSIGNED = -2; |
| 351 |
U32 s; |
| 352 |
U32 distributed = 0; |
| 353 |
U32 ToDistribute; |
| 354 |
|
| 355 |
/* Init */ |
| 356 |
U32 const lowThreshold = (U32)(total >> tableLog); |
| 357 |
U32 lowOne = (U32)((total * 3) >> (tableLog + 1)); |
| 358 |
|
| 359 |
for (s=0; s<=maxSymbolValue; s++) { |
| 360 |
if (count[s] == 0) { |
| 361 |
norm[s]=0; |
| 362 |
continue; |
| 363 |
} |
| 364 |
if (count[s] <= lowThreshold) { |
| 365 |
norm[s] = -1; |
| 366 |
distributed++; |
| 367 |
total -= count[s]; |
| 368 |
continue; |
| 369 |
} |
| 370 |
if (count[s] <= lowOne) { |
| 371 |
norm[s] = 1; |
| 372 |
distributed++; |
| 373 |
total -= count[s]; |
| 374 |
continue; |
| 375 |
} |
| 376 |
|
| 377 |
norm[s]=NOT_YET_ASSIGNED; |
| 378 |
} |
| 379 |
ToDistribute = (1 << tableLog) - distributed; |
| 380 |
|
| 381 |
if (ToDistribute == 0) |
| 382 |
return 0; |
| 383 |
|
| 384 |
if ((total / ToDistribute) > lowOne) { |
| 385 |
/* risk of rounding to zero */ |
| 386 |
lowOne = (U32)((total * 3) / (ToDistribute * 2)); |
| 387 |
for (s=0; s<=maxSymbolValue; s++) { |
| 388 |
if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) { |
| 389 |
norm[s] = 1; |
| 390 |
distributed++; |
| 391 |
total -= count[s]; |
| 392 |
continue; |
| 393 |
} } |
| 394 |
ToDistribute = (1 << tableLog) - distributed; |
| 395 |
} |
| 396 |
|
| 397 |
if (distributed == maxSymbolValue+1) { |
| 398 |
/* all values are pretty poor; |
| 399 |
probably incompressible data (should have already been detected); |
| 400 |
find max, then give all remaining points to max */ |
| 401 |
U32 maxV = 0, maxC = 0; |
| 402 |
for (s=0; s<=maxSymbolValue; s++) |
| 403 |
if (count[s] > maxC) { maxV=s; maxC=count[s]; } |
| 404 |
norm[maxV] += (short)ToDistribute; |
| 405 |
return 0; |
| 406 |
} |
| 407 |
|
| 408 |
if (total == 0) { |
| 409 |
/* all of the symbols were low enough for the lowOne or lowThreshold */ |
| 410 |
for (s=0; ToDistribute > 0; s = (s+1)%(maxSymbolValue+1)) |
| 411 |
if (norm[s] > 0) { ToDistribute--; norm[s]++; } |
| 412 |
return 0; |
| 413 |
} |
| 414 |
|
| 415 |
{ U64 const vStepLog = 62 - tableLog; |
| 416 |
U64 const mid = (1ULL << (vStepLog-1)) - 1; |
| 417 |
U64 const rStep = ((((U64)1<<vStepLog) * ToDistribute) + mid) / total; /* scale on remaining */ |
| 418 |
U64 tmpTotal = mid; |
| 419 |
for (s=0; s<=maxSymbolValue; s++) { |
| 420 |
if (norm[s]==NOT_YET_ASSIGNED) { |
| 421 |
U64 const end = tmpTotal + (count[s] * rStep); |
| 422 |
U32 const sStart = (U32)(tmpTotal >> vStepLog); |
| 423 |
U32 const sEnd = (U32)(end >> vStepLog); |
| 424 |
U32 const weight = sEnd - sStart; |
| 425 |
if (weight < 1) |
| 426 |
return ERROR(GENERIC); |
| 427 |
norm[s] = (short)weight; |
| 428 |
tmpTotal = end; |
| 429 |
} } } |
| 430 |
|
| 431 |
return 0; |
| 432 |
} |
| 433 |
|
| 434 |
|
| 435 |
size_t FSE_normalizeCount (short* normalizedCounter, unsigned tableLog, |
| 436 |
const unsigned* count, size_t total, |
| 437 |
unsigned maxSymbolValue) |
| 438 |
{ |
| 439 |
/* Sanity checks */ |
| 440 |
if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG; |
| 441 |
if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported size */ |
| 442 |
if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported size */ |
| 443 |
if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC); /* Too small tableLog, compression potentially impossible */ |
| 444 |
|
| 445 |
{ static U32 const rtbTable[] = { 0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 }; |
| 446 |
U64 const scale = 62 - tableLog; |
| 447 |
U64 const step = ((U64)1<<62) / total; /* <== here, one division ! */ |
| 448 |
U64 const vStep = 1ULL<<(scale-20); |
| 449 |
int stillToDistribute = 1<<tableLog; |
| 450 |
unsigned s; |
| 451 |
unsigned largest=0; |
| 452 |
short largestP=0; |
| 453 |
U32 lowThreshold = (U32)(total >> tableLog); |
| 454 |
|
| 455 |
for (s=0; s<=maxSymbolValue; s++) { |
| 456 |
if (count[s] == total) return 0; /* rle special case */ |
| 457 |
if (count[s] == 0) { normalizedCounter[s]=0; continue; } |
| 458 |
if (count[s] <= lowThreshold) { |
| 459 |
normalizedCounter[s] = -1; |
| 460 |
stillToDistribute--; |
| 461 |
} else { |
| 462 |
short proba = (short)((count[s]*step) >> scale); |
| 463 |
if (proba<8) { |
| 464 |
U64 restToBeat = vStep * rtbTable[proba]; |
| 465 |
proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat; |
| 466 |
} |
| 467 |
if (proba > largestP) { largestP=proba; largest=s; } |
| 468 |
normalizedCounter[s] = proba; |
| 469 |
stillToDistribute -= proba; |
| 470 |
} } |
| 471 |
if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) { |
| 472 |
/* corner case, need another normalization method */ |
| 473 |
size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue); |
| 474 |
if (FSE_isError(errorCode)) return errorCode; |
| 475 |
} |
| 476 |
else normalizedCounter[largest] += (short)stillToDistribute; |
| 477 |
} |
| 478 |
|
| 479 |
#if 0 |
| 480 |
{ /* Print Table (debug) */ |
| 481 |
U32 s; |
| 482 |
U32 nTotal = 0; |
| 483 |
for (s=0; s<=maxSymbolValue; s++) |
| 484 |
RAWLOG(2, "%3i: %4i \n", s, normalizedCounter[s]); |
| 485 |
for (s=0; s<=maxSymbolValue; s++) |
| 486 |
nTotal += abs(normalizedCounter[s]); |
| 487 |
if (nTotal != (1U<<tableLog)) |
| 488 |
RAWLOG(2, "Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog); |
| 489 |
getchar(); |
| 490 |
} |
| 491 |
#endif |
| 492 |
|
| 493 |
return tableLog; |
| 494 |
} |
| 495 |
|
| 496 |
|
| 497 |
/* fake FSE_CTable, for raw (uncompressed) input */ |
| 498 |
size_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits) |
| 499 |
{ |
| 500 |
const unsigned tableSize = 1 << nbBits; |
| 501 |
const unsigned tableMask = tableSize - 1; |
| 502 |
const unsigned maxSymbolValue = tableMask; |
| 503 |
void* const ptr = ct; |
| 504 |
U16* const tableU16 = ( (U16*) ptr) + 2; |
| 505 |
void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableSize>>1); /* assumption : tableLog >= 1 */ |
| 506 |
FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT); |
| 507 |
unsigned s; |
| 508 |
|
| 509 |
/* Sanity checks */ |
| 510 |
if (nbBits < 1) return ERROR(GENERIC); /* min size */ |
| 511 |
|
| 512 |
/* header */ |
| 513 |
tableU16[-2] = (U16) nbBits; |
| 514 |
tableU16[-1] = (U16) maxSymbolValue; |
| 515 |
|
| 516 |
/* Build table */ |
| 517 |
for (s=0; s<tableSize; s++) |
| 518 |
tableU16[s] = (U16)(tableSize + s); |
| 519 |
|
| 520 |
/* Build Symbol Transformation Table */ |
| 521 |
{ const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits); |
| 522 |
for (s=0; s<=maxSymbolValue; s++) { |
| 523 |
symbolTT[s].deltaNbBits = deltaNbBits; |
| 524 |
symbolTT[s].deltaFindState = s-1; |
| 525 |
} } |
| 526 |
|
| 527 |
return 0; |
| 528 |
} |
| 529 |
|
| 530 |
/* fake FSE_CTable, for rle input (always same symbol) */ |
| 531 |
size_t FSE_buildCTable_rle (FSE_CTable* ct, BYTE symbolValue) |
| 532 |
{ |
| 533 |
void* ptr = ct; |
| 534 |
U16* tableU16 = ( (U16*) ptr) + 2; |
| 535 |
void* FSCTptr = (U32*)ptr + 2; |
| 536 |
FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr; |
| 537 |
|
| 538 |
/* header */ |
| 539 |
tableU16[-2] = (U16) 0; |
| 540 |
tableU16[-1] = (U16) symbolValue; |
| 541 |
|
| 542 |
/* Build table */ |
| 543 |
tableU16[0] = 0; |
| 544 |
tableU16[1] = 0; /* just in case */ |
| 545 |
|
| 546 |
/* Build Symbol Transformation Table */ |
| 547 |
symbolTT[symbolValue].deltaNbBits = 0; |
| 548 |
symbolTT[symbolValue].deltaFindState = 0; |
| 549 |
|
| 550 |
return 0; |
| 551 |
} |
| 552 |
|
| 553 |
|
| 554 |
static size_t FSE_compress_usingCTable_generic (void* dst, size_t dstSize, |
| 555 |
const void* src, size_t srcSize, |
| 556 |
const FSE_CTable* ct, const unsigned fast) |
| 557 |
{ |
| 558 |
const BYTE* const istart = (const BYTE*) src; |
| 559 |
const BYTE* const iend = istart + srcSize; |
| 560 |
const BYTE* ip=iend; |
| 561 |
|
| 562 |
BIT_CStream_t bitC; |
| 563 |
FSE_CState_t CState1, CState2; |
| 564 |
|
| 565 |
/* init */ |
| 566 |
if (srcSize <= 2) return 0; |
| 567 |
{ size_t const initError = BIT_initCStream(&bitC, dst, dstSize); |
| 568 |
if (FSE_isError(initError)) return 0; /* not enough space available to write a bitstream */ } |
| 569 |
|
| 570 |
#define FSE_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s)) |
| 571 |
|
| 572 |
if (srcSize & 1) { |
| 573 |
FSE_initCState2(&CState1, ct, *--ip); |
| 574 |
FSE_initCState2(&CState2, ct, *--ip); |
| 575 |
FSE_encodeSymbol(&bitC, &CState1, *--ip); |
| 576 |
FSE_FLUSHBITS(&bitC); |
| 577 |
} else { |
| 578 |
FSE_initCState2(&CState2, ct, *--ip); |
| 579 |
FSE_initCState2(&CState1, ct, *--ip); |
| 580 |
} |
| 581 |
|
| 582 |
/* join to mod 4 */ |
| 583 |
srcSize -= 2; |
| 584 |
if ((sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) && (srcSize & 2)) { /* test bit 2 */ |
| 585 |
FSE_encodeSymbol(&bitC, &CState2, *--ip); |
| 586 |
FSE_encodeSymbol(&bitC, &CState1, *--ip); |
| 587 |
FSE_FLUSHBITS(&bitC); |
| 588 |
} |
| 589 |
|
| 590 |
/* 2 or 4 encoding per loop */ |
| 591 |
while ( ip>istart ) { |
| 592 |
|
| 593 |
FSE_encodeSymbol(&bitC, &CState2, *--ip); |
| 594 |
|
| 595 |
if (sizeof(bitC.bitContainer)*8 < FSE_MAX_TABLELOG*2+7 ) /* this test must be static */ |
| 596 |
FSE_FLUSHBITS(&bitC); |
| 597 |
|
| 598 |
FSE_encodeSymbol(&bitC, &CState1, *--ip); |
| 599 |
|
| 600 |
if (sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) { /* this test must be static */ |
| 601 |
FSE_encodeSymbol(&bitC, &CState2, *--ip); |
| 602 |
FSE_encodeSymbol(&bitC, &CState1, *--ip); |
| 603 |
} |
| 604 |
|
| 605 |
FSE_FLUSHBITS(&bitC); |
| 606 |
} |
| 607 |
|
| 608 |
FSE_flushCState(&bitC, &CState2); |
| 609 |
FSE_flushCState(&bitC, &CState1); |
| 610 |
return BIT_closeCStream(&bitC); |
| 611 |
} |
| 612 |
|
| 613 |
size_t FSE_compress_usingCTable (void* dst, size_t dstSize, |
| 614 |
const void* src, size_t srcSize, |
| 615 |
const FSE_CTable* ct) |
| 616 |
{ |
| 617 |
unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize)); |
| 618 |
|
| 619 |
if (fast) |
| 620 |
return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1); |
| 621 |
else |
| 622 |
return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0); |
| 623 |
} |
| 624 |
|
| 625 |
|
| 626 |
size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); } |
| 627 |
|
| 628 |
/* FSE_compress_wksp() : |
| 629 |
* Same as FSE_compress2(), but using an externally allocated scratch buffer (`workSpace`). |
| 630 |
* `wkspSize` size must be `(1<<tableLog)`. |
| 631 |
*/ |
| 632 |
size_t FSE_compress_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize) |
| 633 |
{ |
| 634 |
BYTE* const ostart = (BYTE*) dst; |
| 635 |
BYTE* op = ostart; |
| 636 |
BYTE* const oend = ostart + dstSize; |
| 637 |
|
| 638 |
unsigned count[FSE_MAX_SYMBOL_VALUE+1]; |
| 639 |
S16 norm[FSE_MAX_SYMBOL_VALUE+1]; |
| 640 |
FSE_CTable* CTable = (FSE_CTable*)workSpace; |
| 641 |
size_t const CTableSize = FSE_CTABLE_SIZE_U32(tableLog, maxSymbolValue); |
| 642 |
void* scratchBuffer = (void*)(CTable + CTableSize); |
| 643 |
size_t const scratchBufferSize = wkspSize - (CTableSize * sizeof(FSE_CTable)); |
| 644 |
|
| 645 |
/* init conditions */ |
| 646 |
if (wkspSize < FSE_WKSP_SIZE_U32(tableLog, maxSymbolValue)) return ERROR(tableLog_tooLarge); |
| 647 |
if (srcSize <= 1) return 0; /* Not compressible */ |
| 648 |
if (!maxSymbolValue) maxSymbolValue = FSE_MAX_SYMBOL_VALUE; |
| 649 |
if (!tableLog) tableLog = FSE_DEFAULT_TABLELOG; |
| 650 |
|
| 651 |
/* Scan input and build symbol stats */ |
| 652 |
{ CHECK_V_F(maxCount, HIST_count_wksp(count, &maxSymbolValue, src, srcSize, scratchBuffer, scratchBufferSize) ); |
| 653 |
if (maxCount == srcSize) return 1; /* only a single symbol in src : rle */ |
| 654 |
if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */ |
| 655 |
if (maxCount < (srcSize >> 7)) return 0; /* Heuristic : not compressible enough */ |
| 656 |
} |
| 657 |
|
| 658 |
tableLog = FSE_optimalTableLog(tableLog, srcSize, maxSymbolValue); |
| 659 |
CHECK_F( FSE_normalizeCount(norm, tableLog, count, srcSize, maxSymbolValue) ); |
| 660 |
|
| 661 |
/* Write table description header */ |
| 662 |
{ CHECK_V_F(nc_err, FSE_writeNCount(op, oend-op, norm, maxSymbolValue, tableLog) ); |
| 663 |
op += nc_err; |
| 664 |
} |
| 665 |
|
| 666 |
/* Compress */ |
| 667 |
CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, scratchBufferSize) ); |
| 668 |
{ CHECK_V_F(cSize, FSE_compress_usingCTable(op, oend - op, src, srcSize, CTable) ); |
| 669 |
if (cSize == 0) return 0; /* not enough space for compressed data */ |
| 670 |
op += cSize; |
| 671 |
} |
| 672 |
|
| 673 |
/* check compressibility */ |
| 674 |
if ( (size_t)(op-ostart) >= srcSize-1 ) return 0; |
| 675 |
|
| 676 |
return op-ostart; |
| 677 |
} |
| 678 |
|
| 679 |
typedef struct { |
| 680 |
FSE_CTable CTable_max[FSE_CTABLE_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)]; |
| 681 |
BYTE scratchBuffer[1 << FSE_MAX_TABLELOG]; |
| 682 |
} fseWkspMax_t; |
| 683 |
|
| 684 |
size_t FSE_compress2 (void* dst, size_t dstCapacity, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog) |
| 685 |
{ |
| 686 |
fseWkspMax_t scratchBuffer; |
| 687 |
DEBUG_STATIC_ASSERT(sizeof(scratchBuffer) >= FSE_WKSP_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)); /* compilation failures here means scratchBuffer is not large enough */ |
| 688 |
if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); |
| 689 |
return FSE_compress_wksp(dst, dstCapacity, src, srcSize, maxSymbolValue, tableLog, &scratchBuffer, sizeof(scratchBuffer)); |
| 690 |
} |
| 691 |
|
| 692 |
size_t FSE_compress (void* dst, size_t dstCapacity, const void* src, size_t srcSize) |
| 693 |
{ |
| 694 |
return FSE_compress2(dst, dstCapacity, src, srcSize, FSE_MAX_SYMBOL_VALUE, FSE_DEFAULT_TABLELOG); |
| 695 |
} |
| 696 |
|
| 697 |
|
| 698 |
#endif /* FSE_COMMONDEFS_ONLY */ |