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