1 /* ****************************************************************** 2 * FSE : Finite State Entropy encoder 3 * Copyright (c) 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 175 176 177 #ifndef FSE_COMMONDEFS_ONLY 178 179 180 /*-************************************************************** 181 * FSE NCount encoding 182 ****************************************************************/ 183 size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog) 184 { 185 size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3; 186 return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */ 187 } 188 189 static size_t 190 FSE_writeNCount_generic (void* header, size_t headerBufferSize, 191 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, 192 unsigned writeIsSafe) 193 { 194 BYTE* const ostart = (BYTE*) header; 195 BYTE* out = ostart; 196 BYTE* const oend = ostart + headerBufferSize; 197 int nbBits; 198 const int tableSize = 1 << tableLog; 199 int remaining; 200 int threshold; 201 U32 bitStream = 0; 202 int bitCount = 0; 203 unsigned symbol = 0; 204 unsigned const alphabetSize = maxSymbolValue + 1; 205 int previousIs0 = 0; 206 207 /* Table Size */ 208 bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount; 209 bitCount += 4; 210 211 /* Init */ 212 remaining = tableSize+1; /* +1 for extra accuracy */ 213 threshold = tableSize; 214 nbBits = tableLog+1; 215 216 while ((symbol < alphabetSize) && (remaining>1)) { /* stops at 1 */ 217 if (previousIs0) { 218 unsigned start = symbol; 219 while ((symbol < alphabetSize) && !normalizedCounter[symbol]) symbol++; 220 if (symbol == alphabetSize) break; /* incorrect distribution */ 221 while (symbol >= start+24) { 222 start+=24; 223 bitStream += 0xFFFFU << bitCount; 224 if ((!writeIsSafe) && (out > oend-2)) 225 return ERROR(dstSize_tooSmall); /* Buffer overflow */ 226 out[0] = (BYTE) bitStream; 227 out[1] = (BYTE)(bitStream>>8); 228 out+=2; 229 bitStream>>=16; 230 } 231 while (symbol >= start+3) { 232 start+=3; 233 bitStream += 3 << bitCount; 234 bitCount += 2; 235 } 236 bitStream += (symbol-start) << bitCount; 237 bitCount += 2; 238 if (bitCount>16) { 239 if ((!writeIsSafe) && (out > oend - 2)) 240 return ERROR(dstSize_tooSmall); /* Buffer overflow */ 241 out[0] = (BYTE)bitStream; 242 out[1] = (BYTE)(bitStream>>8); 243 out += 2; 244 bitStream >>= 16; 245 bitCount -= 16; 246 } } 247 { int count = normalizedCounter[symbol++]; 248 int const max = (2*threshold-1) - remaining; 249 remaining -= count < 0 ? -count : count; 250 count++; /* +1 for extra accuracy */ 251 if (count>=threshold) 252 count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */ 253 bitStream += count << bitCount; 254 bitCount += nbBits; 255 bitCount -= (count<max); 256 previousIs0 = (count==1); 257 if (remaining<1) return ERROR(GENERIC); 258 while (remaining<threshold) { nbBits--; threshold>>=1; } 259 } 260 if (bitCount>16) { 261 if ((!writeIsSafe) && (out > oend - 2)) 262 return ERROR(dstSize_tooSmall); /* Buffer overflow */ 263 out[0] = (BYTE)bitStream; 264 out[1] = (BYTE)(bitStream>>8); 265 out += 2; 266 bitStream >>= 16; 267 bitCount -= 16; 268 } } 269 270 if (remaining != 1) 271 return ERROR(GENERIC); /* incorrect normalized distribution */ 272 assert(symbol <= alphabetSize); 273 274 /* flush remaining bitStream */ 275 if ((!writeIsSafe) && (out > oend - 2)) 276 return ERROR(dstSize_tooSmall); /* Buffer overflow */ 277 out[0] = (BYTE)bitStream; 278 out[1] = (BYTE)(bitStream>>8); 279 out+= (bitCount+7) /8; 280 281 return (out-ostart); 282 } 283 284 285 size_t FSE_writeNCount (void* buffer, size_t bufferSize, 286 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) 287 { 288 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported */ 289 if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported */ 290 291 if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog)) 292 return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0); 293 294 return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1 /* write in buffer is safe */); 295 } 296 297 298 /*-************************************************************** 299 * FSE Compression Code 300 ****************************************************************/ 301 302 FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog) 303 { 304 size_t size; 305 if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX; 306 size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32); 307 return (FSE_CTable*)ZSTD_malloc(size); 308 } 309 310 void FSE_freeCTable (FSE_CTable* ct) { ZSTD_free(ct); } 311 312 /* provides the minimum logSize to safely represent a distribution */ 313 static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue) 314 { 315 U32 minBitsSrc = BIT_highbit32((U32)(srcSize)) + 1; 316 U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2; 317 U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols; 318 assert(srcSize > 1); /* Not supported, RLE should be used instead */ 319 return minBits; 320 } 321 322 unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus) 323 { 324 U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus; 325 U32 tableLog = maxTableLog; 326 U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue); 327 assert(srcSize > 1); /* Not supported, RLE should be used instead */ 328 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG; 329 if (maxBitsSrc < tableLog) tableLog = maxBitsSrc; /* Accuracy can be reduced */ 330 if (minBits > tableLog) tableLog = minBits; /* Need a minimum to safely represent all symbol values */ 331 if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG; 332 if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG; 333 return tableLog; 334 } 335 336 unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue) 337 { 338 return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2); 339 } 340 341 /* Secondary normalization method. 342 To be used when primary method fails. */ 343 344 static size_t FSE_normalizeM2(short* norm, U32 tableLog, const unsigned* count, size_t total, U32 maxSymbolValue, short lowProbCount) 345 { 346 short const NOT_YET_ASSIGNED = -2; 347 U32 s; 348 U32 distributed = 0; 349 U32 ToDistribute; 350 351 /* Init */ 352 U32 const lowThreshold = (U32)(total >> tableLog); 353 U32 lowOne = (U32)((total * 3) >> (tableLog + 1)); 354 355 for (s=0; s<=maxSymbolValue; s++) { 356 if (count[s] == 0) { 357 norm[s]=0; 358 continue; 359 } 360 if (count[s] <= lowThreshold) { 361 norm[s] = lowProbCount; 362 distributed++; 363 total -= count[s]; 364 continue; 365 } 366 if (count[s] <= lowOne) { 367 norm[s] = 1; 368 distributed++; 369 total -= count[s]; 370 continue; 371 } 372 373 norm[s]=NOT_YET_ASSIGNED; 374 } 375 ToDistribute = (1 << tableLog) - distributed; 376 377 if (ToDistribute == 0) 378 return 0; 379 380 if ((total / ToDistribute) > lowOne) { 381 /* risk of rounding to zero */ 382 lowOne = (U32)((total * 3) / (ToDistribute * 2)); 383 for (s=0; s<=maxSymbolValue; s++) { 384 if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) { 385 norm[s] = 1; 386 distributed++; 387 total -= count[s]; 388 continue; 389 } } 390 ToDistribute = (1 << tableLog) - distributed; 391 } 392 393 if (distributed == maxSymbolValue+1) { 394 /* all values are pretty poor; 395 probably incompressible data (should have already been detected); 396 find max, then give all remaining points to max */ 397 U32 maxV = 0, maxC = 0; 398 for (s=0; s<=maxSymbolValue; s++) 399 if (count[s] > maxC) { maxV=s; maxC=count[s]; } 400 norm[maxV] += (short)ToDistribute; 401 return 0; 402 } 403 404 if (total == 0) { 405 /* all of the symbols were low enough for the lowOne or lowThreshold */ 406 for (s=0; ToDistribute > 0; s = (s+1)%(maxSymbolValue+1)) 407 if (norm[s] > 0) { ToDistribute--; norm[s]++; } 408 return 0; 409 } 410 411 { U64 const vStepLog = 62 - tableLog; 412 U64 const mid = (1ULL << (vStepLog-1)) - 1; 413 U64 const rStep = ZSTD_div64((((U64)1<<vStepLog) * ToDistribute) + mid, (U32)total); /* scale on remaining */ 414 U64 tmpTotal = mid; 415 for (s=0; s<=maxSymbolValue; s++) { 416 if (norm[s]==NOT_YET_ASSIGNED) { 417 U64 const end = tmpTotal + (count[s] * rStep); 418 U32 const sStart = (U32)(tmpTotal >> vStepLog); 419 U32 const sEnd = (U32)(end >> vStepLog); 420 U32 const weight = sEnd - sStart; 421 if (weight < 1) 422 return ERROR(GENERIC); 423 norm[s] = (short)weight; 424 tmpTotal = end; 425 } } } 426 427 return 0; 428 } 429 430 size_t FSE_normalizeCount (short* normalizedCounter, unsigned tableLog, 431 const unsigned* count, size_t total, 432 unsigned maxSymbolValue, unsigned useLowProbCount) 433 { 434 /* Sanity checks */ 435 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG; 436 if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported size */ 437 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported size */ 438 if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC); /* Too small tableLog, compression potentially impossible */ 439 440 { static U32 const rtbTable[] = { 0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 }; 441 short const lowProbCount = useLowProbCount ? -1 : 1; 442 U64 const scale = 62 - tableLog; 443 U64 const step = ZSTD_div64((U64)1<<62, (U32)total); /* <== here, one division ! */ 444 U64 const vStep = 1ULL<<(scale-20); 445 int stillToDistribute = 1<<tableLog; 446 unsigned s; 447 unsigned largest=0; 448 short largestP=0; 449 U32 lowThreshold = (U32)(total >> tableLog); 450 451 for (s=0; s<=maxSymbolValue; s++) { 452 if (count[s] == total) return 0; /* rle special case */ 453 if (count[s] == 0) { normalizedCounter[s]=0; continue; } 454 if (count[s] <= lowThreshold) { 455 normalizedCounter[s] = lowProbCount; 456 stillToDistribute--; 457 } else { 458 short proba = (short)((count[s]*step) >> scale); 459 if (proba<8) { 460 U64 restToBeat = vStep * rtbTable[proba]; 461 proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat; 462 } 463 if (proba > largestP) { largestP=proba; largest=s; } 464 normalizedCounter[s] = proba; 465 stillToDistribute -= proba; 466 } } 467 if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) { 468 /* corner case, need another normalization method */ 469 size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue, lowProbCount); 470 if (FSE_isError(errorCode)) return errorCode; 471 } 472 else normalizedCounter[largest] += (short)stillToDistribute; 473 } 474 475 #if 0 476 { /* Print Table (debug) */ 477 U32 s; 478 U32 nTotal = 0; 479 for (s=0; s<=maxSymbolValue; s++) 480 RAWLOG(2, "%3i: %4i \n", s, normalizedCounter[s]); 481 for (s=0; s<=maxSymbolValue; s++) 482 nTotal += abs(normalizedCounter[s]); 483 if (nTotal != (1U<<tableLog)) 484 RAWLOG(2, "Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog); 485 getchar(); 486 } 487 #endif 488 489 return tableLog; 490 } 491 492 493 /* fake FSE_CTable, for raw (uncompressed) input */ 494 size_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits) 495 { 496 const unsigned tableSize = 1 << nbBits; 497 const unsigned tableMask = tableSize - 1; 498 const unsigned maxSymbolValue = tableMask; 499 void* const ptr = ct; 500 U16* const tableU16 = ( (U16*) ptr) + 2; 501 void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableSize>>1); /* assumption : tableLog >= 1 */ 502 FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT); 503 unsigned s; 504 505 /* Sanity checks */ 506 if (nbBits < 1) return ERROR(GENERIC); /* min size */ 507 508 /* header */ 509 tableU16[-2] = (U16) nbBits; 510 tableU16[-1] = (U16) maxSymbolValue; 511 512 /* Build table */ 513 for (s=0; s<tableSize; s++) 514 tableU16[s] = (U16)(tableSize + s); 515 516 /* Build Symbol Transformation Table */ 517 { const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits); 518 for (s=0; s<=maxSymbolValue; s++) { 519 symbolTT[s].deltaNbBits = deltaNbBits; 520 symbolTT[s].deltaFindState = s-1; 521 } } 522 523 return 0; 524 } 525 526 /* fake FSE_CTable, for rle input (always same symbol) */ 527 size_t FSE_buildCTable_rle (FSE_CTable* ct, BYTE symbolValue) 528 { 529 void* ptr = ct; 530 U16* tableU16 = ( (U16*) ptr) + 2; 531 void* FSCTptr = (U32*)ptr + 2; 532 FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr; 533 534 /* header */ 535 tableU16[-2] = (U16) 0; 536 tableU16[-1] = (U16) symbolValue; 537 538 /* Build table */ 539 tableU16[0] = 0; 540 tableU16[1] = 0; /* just in case */ 541 542 /* Build Symbol Transformation Table */ 543 symbolTT[symbolValue].deltaNbBits = 0; 544 symbolTT[symbolValue].deltaFindState = 0; 545 546 return 0; 547 } 548 549 550 static size_t FSE_compress_usingCTable_generic (void* dst, size_t dstSize, 551 const void* src, size_t srcSize, 552 const FSE_CTable* ct, const unsigned fast) 553 { 554 const BYTE* const istart = (const BYTE*) src; 555 const BYTE* const iend = istart + srcSize; 556 const BYTE* ip=iend; 557 558 BIT_CStream_t bitC; 559 FSE_CState_t CState1, CState2; 560 561 /* init */ 562 if (srcSize <= 2) return 0; 563 { size_t const initError = BIT_initCStream(&bitC, dst, dstSize); 564 if (FSE_isError(initError)) return 0; /* not enough space available to write a bitstream */ } 565 566 #define FSE_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s)) 567 568 if (srcSize & 1) { 569 FSE_initCState2(&CState1, ct, *--ip); 570 FSE_initCState2(&CState2, ct, *--ip); 571 FSE_encodeSymbol(&bitC, &CState1, *--ip); 572 FSE_FLUSHBITS(&bitC); 573 } else { 574 FSE_initCState2(&CState2, ct, *--ip); 575 FSE_initCState2(&CState1, ct, *--ip); 576 } 577 578 /* join to mod 4 */ 579 srcSize -= 2; 580 if ((sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) && (srcSize & 2)) { /* test bit 2 */ 581 FSE_encodeSymbol(&bitC, &CState2, *--ip); 582 FSE_encodeSymbol(&bitC, &CState1, *--ip); 583 FSE_FLUSHBITS(&bitC); 584 } 585 586 /* 2 or 4 encoding per loop */ 587 while ( ip>istart ) { 588 589 FSE_encodeSymbol(&bitC, &CState2, *--ip); 590 591 if (sizeof(bitC.bitContainer)*8 < FSE_MAX_TABLELOG*2+7 ) /* this test must be static */ 592 FSE_FLUSHBITS(&bitC); 593 594 FSE_encodeSymbol(&bitC, &CState1, *--ip); 595 596 if (sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) { /* this test must be static */ 597 FSE_encodeSymbol(&bitC, &CState2, *--ip); 598 FSE_encodeSymbol(&bitC, &CState1, *--ip); 599 } 600 601 FSE_FLUSHBITS(&bitC); 602 } 603 604 FSE_flushCState(&bitC, &CState2); 605 FSE_flushCState(&bitC, &CState1); 606 return BIT_closeCStream(&bitC); 607 } 608 609 size_t FSE_compress_usingCTable (void* dst, size_t dstSize, 610 const void* src, size_t srcSize, 611 const FSE_CTable* ct) 612 { 613 unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize)); 614 615 if (fast) 616 return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1); 617 else 618 return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0); 619 } 620 621 622 size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); } 623 624 625 #endif /* FSE_COMMONDEFS_ONLY */ 626