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