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