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