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