1 /* ****************************************************************** 2 FSE : Finite State Entropy encoder 3 Copyright (C) 2013-2015, 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 <stdio.h> /* printf (debug) */ 41 #include "bitstream.h" 42 #include "compiler.h" 43 #define FSE_STATIC_LINKING_ONLY 44 #include "fse.h" 45 #include "error_private.h" 46 47 48 /* ************************************************************** 49 * Error Management 50 ****************************************************************/ 51 #define FSE_isError ERR_isError 52 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 53 54 55 /* ************************************************************** 56 * Templates 57 ****************************************************************/ 58 /* 59 designed to be included 60 for type-specific functions (template emulation in C) 61 Objective is to write these functions only once, for improved maintenance 62 */ 63 64 /* safety checks */ 65 #ifndef FSE_FUNCTION_EXTENSION 66 # error "FSE_FUNCTION_EXTENSION must be defined" 67 #endif 68 #ifndef FSE_FUNCTION_TYPE 69 # error "FSE_FUNCTION_TYPE must be defined" 70 #endif 71 72 /* Function names */ 73 #define FSE_CAT(X,Y) X##Y 74 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y) 75 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y) 76 77 78 /* Function templates */ 79 80 /* FSE_buildCTable_wksp() : 81 * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`). 82 * wkspSize should be sized to handle worst case situation, which is `1<<max_tableLog * sizeof(FSE_FUNCTION_TYPE)` 83 * workSpace must also be properly aligned with FSE_FUNCTION_TYPE requirements 84 */ 85 size_t FSE_buildCTable_wksp(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize) 86 { 87 U32 const tableSize = 1 << tableLog; 88 U32 const tableMask = tableSize - 1; 89 void* const ptr = ct; 90 U16* const tableU16 = ( (U16*) ptr) + 2; 91 void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableLog ? tableSize>>1 : 1) ; 92 FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT); 93 U32 const step = FSE_TABLESTEP(tableSize); 94 U32 cumul[FSE_MAX_SYMBOL_VALUE+2]; 95 96 FSE_FUNCTION_TYPE* const tableSymbol = (FSE_FUNCTION_TYPE*)workSpace; 97 U32 highThreshold = tableSize-1; 98 99 /* CTable header */ 100 if (((size_t)1 << tableLog) * sizeof(FSE_FUNCTION_TYPE) > wkspSize) return ERROR(tableLog_tooLarge); 101 tableU16[-2] = (U16) tableLog; 102 tableU16[-1] = (U16) maxSymbolValue; 103 104 /* For explanations on how to distribute symbol values over the table : 105 * http://fastcompression.blogspot.fr/2014/02/fse-distributing-symbol-values.html */ 106 107 /* symbol start positions */ 108 { U32 u; 109 cumul[0] = 0; 110 for (u=1; u<=maxSymbolValue+1; u++) { 111 if (normalizedCounter[u-1]==-1) { /* Low proba symbol */ 112 cumul[u] = cumul[u-1] + 1; 113 tableSymbol[highThreshold--] = (FSE_FUNCTION_TYPE)(u-1); 114 } else { 115 cumul[u] = cumul[u-1] + normalizedCounter[u-1]; 116 } } 117 cumul[maxSymbolValue+1] = tableSize+1; 118 } 119 120 /* Spread symbols */ 121 { U32 position = 0; 122 U32 symbol; 123 for (symbol=0; symbol<=maxSymbolValue; symbol++) { 124 int nbOccurences; 125 for (nbOccurences=0; nbOccurences<normalizedCounter[symbol]; nbOccurences++) { 126 tableSymbol[position] = (FSE_FUNCTION_TYPE)symbol; 127 position = (position + step) & tableMask; 128 while (position > highThreshold) position = (position + step) & tableMask; /* Low proba area */ 129 } } 130 131 if (position!=0) return ERROR(GENERIC); /* Must have gone through all positions */ 132 } 133 134 /* Build table */ 135 { U32 u; for (u=0; u<tableSize; u++) { 136 FSE_FUNCTION_TYPE s = tableSymbol[u]; /* note : static analyzer may not understand tableSymbol is properly initialized */ 137 tableU16[cumul[s]++] = (U16) (tableSize+u); /* TableU16 : sorted by symbol order; gives next state value */ 138 } } 139 140 /* Build Symbol Transformation Table */ 141 { unsigned total = 0; 142 unsigned s; 143 for (s=0; s<=maxSymbolValue; s++) { 144 switch (normalizedCounter[s]) 145 { 146 case 0: break; 147 148 case -1: 149 case 1: 150 symbolTT[s].deltaNbBits = (tableLog << 16) - (1<<tableLog); 151 symbolTT[s].deltaFindState = total - 1; 152 total ++; 153 break; 154 default : 155 { 156 U32 const maxBitsOut = tableLog - BIT_highbit32 (normalizedCounter[s]-1); 157 U32 const minStatePlus = normalizedCounter[s] << maxBitsOut; 158 symbolTT[s].deltaNbBits = (maxBitsOut << 16) - minStatePlus; 159 symbolTT[s].deltaFindState = total - normalizedCounter[s]; 160 total += normalizedCounter[s]; 161 } } } } 162 163 return 0; 164 } 165 166 167 size_t FSE_buildCTable(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) 168 { 169 FSE_FUNCTION_TYPE tableSymbol[FSE_MAX_TABLESIZE]; /* memset() is not necessary, even if static analyzer complain about it */ 170 return FSE_buildCTable_wksp(ct, normalizedCounter, maxSymbolValue, tableLog, tableSymbol, sizeof(tableSymbol)); 171 } 172 173 174 175 #ifndef FSE_COMMONDEFS_ONLY 176 177 /*-************************************************************** 178 * FSE NCount encoding-decoding 179 ****************************************************************/ 180 size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog) 181 { 182 size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3; 183 return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */ 184 } 185 186 static size_t FSE_writeNCount_generic (void* header, size_t headerBufferSize, 187 const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, 188 unsigned writeIsSafe) 189 { 190 BYTE* const ostart = (BYTE*) header; 191 BYTE* out = ostart; 192 BYTE* const oend = ostart + headerBufferSize; 193 int nbBits; 194 const int tableSize = 1 << tableLog; 195 int remaining; 196 int threshold; 197 U32 bitStream; 198 int bitCount; 199 unsigned charnum = 0; 200 int previous0 = 0; 201 202 bitStream = 0; 203 bitCount = 0; 204 /* Table Size */ 205 bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount; 206 bitCount += 4; 207 208 /* Init */ 209 remaining = tableSize+1; /* +1 for extra accuracy */ 210 threshold = tableSize; 211 nbBits = tableLog+1; 212 213 while (remaining>1) { /* stops at 1 */ 214 if (previous0) { 215 unsigned start = charnum; 216 while (!normalizedCounter[charnum]) charnum++; 217 while (charnum >= start+24) { 218 start+=24; 219 bitStream += 0xFFFFU << bitCount; 220 if ((!writeIsSafe) && (out > oend-2)) return ERROR(dstSize_tooSmall); /* Buffer overflow */ 221 out[0] = (BYTE) bitStream; 222 out[1] = (BYTE)(bitStream>>8); 223 out+=2; 224 bitStream>>=16; 225 } 226 while (charnum >= start+3) { 227 start+=3; 228 bitStream += 3 << bitCount; 229 bitCount += 2; 230 } 231 bitStream += (charnum-start) << bitCount; 232 bitCount += 2; 233 if (bitCount>16) { 234 if ((!writeIsSafe) && (out > oend - 2)) return ERROR(dstSize_tooSmall); /* Buffer overflow */ 235 out[0] = (BYTE)bitStream; 236 out[1] = (BYTE)(bitStream>>8); 237 out += 2; 238 bitStream >>= 16; 239 bitCount -= 16; 240 } } 241 { int count = normalizedCounter[charnum++]; 242 int const max = (2*threshold-1)-remaining; 243 remaining -= count < 0 ? -count : count; 244 count++; /* +1 for extra accuracy */ 245 if (count>=threshold) count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */ 246 bitStream += count << bitCount; 247 bitCount += nbBits; 248 bitCount -= (count<max); 249 previous0 = (count==1); 250 if (remaining<1) return ERROR(GENERIC); 251 while (remaining<threshold) { nbBits--; threshold>>=1; } 252 } 253 if (bitCount>16) { 254 if ((!writeIsSafe) && (out > oend - 2)) return ERROR(dstSize_tooSmall); /* Buffer overflow */ 255 out[0] = (BYTE)bitStream; 256 out[1] = (BYTE)(bitStream>>8); 257 out += 2; 258 bitStream >>= 16; 259 bitCount -= 16; 260 } } 261 262 /* flush remaining bitStream */ 263 if ((!writeIsSafe) && (out > oend - 2)) return ERROR(dstSize_tooSmall); /* Buffer overflow */ 264 out[0] = (BYTE)bitStream; 265 out[1] = (BYTE)(bitStream>>8); 266 out+= (bitCount+7) /8; 267 268 if (charnum > maxSymbolValue + 1) return ERROR(GENERIC); 269 270 return (out-ostart); 271 } 272 273 274 size_t FSE_writeNCount (void* buffer, size_t bufferSize, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) 275 { 276 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported */ 277 if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported */ 278 279 if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog)) 280 return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0); 281 282 return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1); 283 } 284 285 286 287 /*-************************************************************** 288 * Counting histogram 289 ****************************************************************/ 290 /*! FSE_count_simple 291 This function counts byte values within `src`, and store the histogram into table `count`. 292 It doesn't use any additional memory. 293 But this function is unsafe : it doesn't check that all values within `src` can fit into `count`. 294 For this reason, prefer using a table `count` with 256 elements. 295 @return : count of most numerous element. 296 */ 297 size_t FSE_count_simple(unsigned* count, unsigned* maxSymbolValuePtr, 298 const void* src, size_t srcSize) 299 { 300 const BYTE* ip = (const BYTE*)src; 301 const BYTE* const end = ip + srcSize; 302 unsigned maxSymbolValue = *maxSymbolValuePtr; 303 unsigned max=0; 304 305 memset(count, 0, (maxSymbolValue+1)*sizeof(*count)); 306 if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; } 307 308 while (ip<end) { 309 assert(*ip <= maxSymbolValue); 310 count[*ip++]++; 311 } 312 313 while (!count[maxSymbolValue]) maxSymbolValue--; 314 *maxSymbolValuePtr = maxSymbolValue; 315 316 { U32 s; for (s=0; s<=maxSymbolValue; s++) if (count[s] > max) max = count[s]; } 317 318 return (size_t)max; 319 } 320 321 322 /* FSE_count_parallel_wksp() : 323 * Same as FSE_count_parallel(), but using an externally provided scratch buffer. 324 * `workSpace` size must be a minimum of `1024 * sizeof(unsigned)`. 325 * @return : largest histogram frequency, or an error code (notably when histogram would be larger than *maxSymbolValuePtr). */ 326 static size_t FSE_count_parallel_wksp( 327 unsigned* count, unsigned* maxSymbolValuePtr, 328 const void* source, size_t sourceSize, 329 unsigned checkMax, unsigned* const workSpace) 330 { 331 const BYTE* ip = (const BYTE*)source; 332 const BYTE* const iend = ip+sourceSize; 333 unsigned maxSymbolValue = *maxSymbolValuePtr; 334 unsigned max=0; 335 U32* const Counting1 = workSpace; 336 U32* const Counting2 = Counting1 + 256; 337 U32* const Counting3 = Counting2 + 256; 338 U32* const Counting4 = Counting3 + 256; 339 340 memset(workSpace, 0, 4*256*sizeof(unsigned)); 341 342 /* safety checks */ 343 if (!sourceSize) { 344 memset(count, 0, maxSymbolValue + 1); 345 *maxSymbolValuePtr = 0; 346 return 0; 347 } 348 if (!maxSymbolValue) maxSymbolValue = 255; /* 0 == default */ 349 350 /* by stripes of 16 bytes */ 351 { U32 cached = MEM_read32(ip); ip += 4; 352 while (ip < iend-15) { 353 U32 c = cached; cached = MEM_read32(ip); ip += 4; 354 Counting1[(BYTE) c ]++; 355 Counting2[(BYTE)(c>>8) ]++; 356 Counting3[(BYTE)(c>>16)]++; 357 Counting4[ c>>24 ]++; 358 c = cached; cached = MEM_read32(ip); ip += 4; 359 Counting1[(BYTE) c ]++; 360 Counting2[(BYTE)(c>>8) ]++; 361 Counting3[(BYTE)(c>>16)]++; 362 Counting4[ c>>24 ]++; 363 c = cached; cached = MEM_read32(ip); ip += 4; 364 Counting1[(BYTE) c ]++; 365 Counting2[(BYTE)(c>>8) ]++; 366 Counting3[(BYTE)(c>>16)]++; 367 Counting4[ c>>24 ]++; 368 c = cached; cached = MEM_read32(ip); ip += 4; 369 Counting1[(BYTE) c ]++; 370 Counting2[(BYTE)(c>>8) ]++; 371 Counting3[(BYTE)(c>>16)]++; 372 Counting4[ c>>24 ]++; 373 } 374 ip-=4; 375 } 376 377 /* finish last symbols */ 378 while (ip<iend) Counting1[*ip++]++; 379 380 if (checkMax) { /* verify stats will fit into destination table */ 381 U32 s; for (s=255; s>maxSymbolValue; s--) { 382 Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s]; 383 if (Counting1[s]) return ERROR(maxSymbolValue_tooSmall); 384 } } 385 386 { U32 s; 387 if (maxSymbolValue > 255) maxSymbolValue = 255; 388 for (s=0; s<=maxSymbolValue; s++) { 389 count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s]; 390 if (count[s] > max) max = count[s]; 391 } } 392 393 while (!count[maxSymbolValue]) maxSymbolValue--; 394 *maxSymbolValuePtr = maxSymbolValue; 395 return (size_t)max; 396 } 397 398 /* FSE_countFast_wksp() : 399 * Same as FSE_countFast(), but using an externally provided scratch buffer. 400 * `workSpace` size must be table of >= `1024` unsigned */ 401 size_t FSE_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr, 402 const void* source, size_t sourceSize, 403 unsigned* workSpace) 404 { 405 if (sourceSize < 1500) /* heuristic threshold */ 406 return FSE_count_simple(count, maxSymbolValuePtr, source, sourceSize); 407 return FSE_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, 0, workSpace); 408 } 409 410 /* fast variant (unsafe : won't check if src contains values beyond count[] limit) */ 411 size_t FSE_countFast(unsigned* count, unsigned* maxSymbolValuePtr, 412 const void* source, size_t sourceSize) 413 { 414 unsigned tmpCounters[1024]; 415 return FSE_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, tmpCounters); 416 } 417 418 /* FSE_count_wksp() : 419 * Same as FSE_count(), but using an externally provided scratch buffer. 420 * `workSpace` size must be table of >= `1024` unsigned */ 421 size_t FSE_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr, 422 const void* source, size_t sourceSize, unsigned* workSpace) 423 { 424 if (*maxSymbolValuePtr < 255) 425 return FSE_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, 1, workSpace); 426 *maxSymbolValuePtr = 255; 427 return FSE_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace); 428 } 429 430 size_t FSE_count(unsigned* count, unsigned* maxSymbolValuePtr, 431 const void* src, size_t srcSize) 432 { 433 unsigned tmpCounters[1024]; 434 return FSE_count_wksp(count, maxSymbolValuePtr, src, srcSize, tmpCounters); 435 } 436 437 438 439 /*-************************************************************** 440 * FSE Compression Code 441 ****************************************************************/ 442 /*! FSE_sizeof_CTable() : 443 FSE_CTable is a variable size structure which contains : 444 `U16 tableLog;` 445 `U16 maxSymbolValue;` 446 `U16 nextStateNumber[1 << tableLog];` // This size is variable 447 `FSE_symbolCompressionTransform symbolTT[maxSymbolValue+1];` // This size is variable 448 Allocation is manual (C standard does not support variable-size structures). 449 */ 450 size_t FSE_sizeof_CTable (unsigned maxSymbolValue, unsigned tableLog) 451 { 452 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); 453 return FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32); 454 } 455 456 FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog) 457 { 458 size_t size; 459 if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX; 460 size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32); 461 return (FSE_CTable*)malloc(size); 462 } 463 464 void FSE_freeCTable (FSE_CTable* ct) { free(ct); } 465 466 /* provides the minimum logSize to safely represent a distribution */ 467 static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue) 468 { 469 U32 minBitsSrc = BIT_highbit32((U32)(srcSize - 1)) + 1; 470 U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2; 471 U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols; 472 assert(srcSize > 1); /* Not supported, RLE should be used instead */ 473 return minBits; 474 } 475 476 unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus) 477 { 478 U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus; 479 U32 tableLog = maxTableLog; 480 U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue); 481 assert(srcSize > 1); /* Not supported, RLE should be used instead */ 482 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG; 483 if (maxBitsSrc < tableLog) tableLog = maxBitsSrc; /* Accuracy can be reduced */ 484 if (minBits > tableLog) tableLog = minBits; /* Need a minimum to safely represent all symbol values */ 485 if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG; 486 if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG; 487 return tableLog; 488 } 489 490 unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue) 491 { 492 return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2); 493 } 494 495 496 /* Secondary normalization method. 497 To be used when primary method fails. */ 498 499 static size_t FSE_normalizeM2(short* norm, U32 tableLog, const unsigned* count, size_t total, U32 maxSymbolValue) 500 { 501 short const NOT_YET_ASSIGNED = -2; 502 U32 s; 503 U32 distributed = 0; 504 U32 ToDistribute; 505 506 /* Init */ 507 U32 const lowThreshold = (U32)(total >> tableLog); 508 U32 lowOne = (U32)((total * 3) >> (tableLog + 1)); 509 510 for (s=0; s<=maxSymbolValue; s++) { 511 if (count[s] == 0) { 512 norm[s]=0; 513 continue; 514 } 515 if (count[s] <= lowThreshold) { 516 norm[s] = -1; 517 distributed++; 518 total -= count[s]; 519 continue; 520 } 521 if (count[s] <= lowOne) { 522 norm[s] = 1; 523 distributed++; 524 total -= count[s]; 525 continue; 526 } 527 528 norm[s]=NOT_YET_ASSIGNED; 529 } 530 ToDistribute = (1 << tableLog) - distributed; 531 532 if ((total / ToDistribute) > lowOne) { 533 /* risk of rounding to zero */ 534 lowOne = (U32)((total * 3) / (ToDistribute * 2)); 535 for (s=0; s<=maxSymbolValue; s++) { 536 if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) { 537 norm[s] = 1; 538 distributed++; 539 total -= count[s]; 540 continue; 541 } } 542 ToDistribute = (1 << tableLog) - distributed; 543 } 544 545 if (distributed == maxSymbolValue+1) { 546 /* all values are pretty poor; 547 probably incompressible data (should have already been detected); 548 find max, then give all remaining points to max */ 549 U32 maxV = 0, maxC = 0; 550 for (s=0; s<=maxSymbolValue; s++) 551 if (count[s] > maxC) { maxV=s; maxC=count[s]; } 552 norm[maxV] += (short)ToDistribute; 553 return 0; 554 } 555 556 if (total == 0) { 557 /* all of the symbols were low enough for the lowOne or lowThreshold */ 558 for (s=0; ToDistribute > 0; s = (s+1)%(maxSymbolValue+1)) 559 if (norm[s] > 0) { ToDistribute--; norm[s]++; } 560 return 0; 561 } 562 563 { U64 const vStepLog = 62 - tableLog; 564 U64 const mid = (1ULL << (vStepLog-1)) - 1; 565 U64 const rStep = ((((U64)1<<vStepLog) * ToDistribute) + mid) / total; /* scale on remaining */ 566 U64 tmpTotal = mid; 567 for (s=0; s<=maxSymbolValue; s++) { 568 if (norm[s]==NOT_YET_ASSIGNED) { 569 U64 const end = tmpTotal + (count[s] * rStep); 570 U32 const sStart = (U32)(tmpTotal >> vStepLog); 571 U32 const sEnd = (U32)(end >> vStepLog); 572 U32 const weight = sEnd - sStart; 573 if (weight < 1) 574 return ERROR(GENERIC); 575 norm[s] = (short)weight; 576 tmpTotal = end; 577 } } } 578 579 return 0; 580 } 581 582 583 size_t FSE_normalizeCount (short* normalizedCounter, unsigned tableLog, 584 const unsigned* count, size_t total, 585 unsigned maxSymbolValue) 586 { 587 /* Sanity checks */ 588 if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG; 589 if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported size */ 590 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported size */ 591 if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC); /* Too small tableLog, compression potentially impossible */ 592 593 { static U32 const rtbTable[] = { 0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 }; 594 U64 const scale = 62 - tableLog; 595 U64 const step = ((U64)1<<62) / total; /* <== here, one division ! */ 596 U64 const vStep = 1ULL<<(scale-20); 597 int stillToDistribute = 1<<tableLog; 598 unsigned s; 599 unsigned largest=0; 600 short largestP=0; 601 U32 lowThreshold = (U32)(total >> tableLog); 602 603 for (s=0; s<=maxSymbolValue; s++) { 604 if (count[s] == total) return 0; /* rle special case */ 605 if (count[s] == 0) { normalizedCounter[s]=0; continue; } 606 if (count[s] <= lowThreshold) { 607 normalizedCounter[s] = -1; 608 stillToDistribute--; 609 } else { 610 short proba = (short)((count[s]*step) >> scale); 611 if (proba<8) { 612 U64 restToBeat = vStep * rtbTable[proba]; 613 proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat; 614 } 615 if (proba > largestP) { largestP=proba; largest=s; } 616 normalizedCounter[s] = proba; 617 stillToDistribute -= proba; 618 } } 619 if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) { 620 /* corner case, need another normalization method */ 621 size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue); 622 if (FSE_isError(errorCode)) return errorCode; 623 } 624 else normalizedCounter[largest] += (short)stillToDistribute; 625 } 626 627 #if 0 628 { /* Print Table (debug) */ 629 U32 s; 630 U32 nTotal = 0; 631 for (s=0; s<=maxSymbolValue; s++) 632 printf("%3i: %4i \n", s, normalizedCounter[s]); 633 for (s=0; s<=maxSymbolValue; s++) 634 nTotal += abs(normalizedCounter[s]); 635 if (nTotal != (1U<<tableLog)) 636 printf("Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog); 637 getchar(); 638 } 639 #endif 640 641 return tableLog; 642 } 643 644 645 /* fake FSE_CTable, for raw (uncompressed) input */ 646 size_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits) 647 { 648 const unsigned tableSize = 1 << nbBits; 649 const unsigned tableMask = tableSize - 1; 650 const unsigned maxSymbolValue = tableMask; 651 void* const ptr = ct; 652 U16* const tableU16 = ( (U16*) ptr) + 2; 653 void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableSize>>1); /* assumption : tableLog >= 1 */ 654 FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT); 655 unsigned s; 656 657 /* Sanity checks */ 658 if (nbBits < 1) return ERROR(GENERIC); /* min size */ 659 660 /* header */ 661 tableU16[-2] = (U16) nbBits; 662 tableU16[-1] = (U16) maxSymbolValue; 663 664 /* Build table */ 665 for (s=0; s<tableSize; s++) 666 tableU16[s] = (U16)(tableSize + s); 667 668 /* Build Symbol Transformation Table */ 669 { const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits); 670 for (s=0; s<=maxSymbolValue; s++) { 671 symbolTT[s].deltaNbBits = deltaNbBits; 672 symbolTT[s].deltaFindState = s-1; 673 } } 674 675 return 0; 676 } 677 678 /* fake FSE_CTable, for rle input (always same symbol) */ 679 size_t FSE_buildCTable_rle (FSE_CTable* ct, BYTE symbolValue) 680 { 681 void* ptr = ct; 682 U16* tableU16 = ( (U16*) ptr) + 2; 683 void* FSCTptr = (U32*)ptr + 2; 684 FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr; 685 686 /* header */ 687 tableU16[-2] = (U16) 0; 688 tableU16[-1] = (U16) symbolValue; 689 690 /* Build table */ 691 tableU16[0] = 0; 692 tableU16[1] = 0; /* just in case */ 693 694 /* Build Symbol Transformation Table */ 695 symbolTT[symbolValue].deltaNbBits = 0; 696 symbolTT[symbolValue].deltaFindState = 0; 697 698 return 0; 699 } 700 701 702 static size_t FSE_compress_usingCTable_generic (void* dst, size_t dstSize, 703 const void* src, size_t srcSize, 704 const FSE_CTable* ct, const unsigned fast) 705 { 706 const BYTE* const istart = (const BYTE*) src; 707 const BYTE* const iend = istart + srcSize; 708 const BYTE* ip=iend; 709 710 BIT_CStream_t bitC; 711 FSE_CState_t CState1, CState2; 712 713 /* init */ 714 if (srcSize <= 2) return 0; 715 { size_t const initError = BIT_initCStream(&bitC, dst, dstSize); 716 if (FSE_isError(initError)) return 0; /* not enough space available to write a bitstream */ } 717 718 #define FSE_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s)) 719 720 if (srcSize & 1) { 721 FSE_initCState2(&CState1, ct, *--ip); 722 FSE_initCState2(&CState2, ct, *--ip); 723 FSE_encodeSymbol(&bitC, &CState1, *--ip); 724 FSE_FLUSHBITS(&bitC); 725 } else { 726 FSE_initCState2(&CState2, ct, *--ip); 727 FSE_initCState2(&CState1, ct, *--ip); 728 } 729 730 /* join to mod 4 */ 731 srcSize -= 2; 732 if ((sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) && (srcSize & 2)) { /* test bit 2 */ 733 FSE_encodeSymbol(&bitC, &CState2, *--ip); 734 FSE_encodeSymbol(&bitC, &CState1, *--ip); 735 FSE_FLUSHBITS(&bitC); 736 } 737 738 /* 2 or 4 encoding per loop */ 739 while ( ip>istart ) { 740 741 FSE_encodeSymbol(&bitC, &CState2, *--ip); 742 743 if (sizeof(bitC.bitContainer)*8 < FSE_MAX_TABLELOG*2+7 ) /* this test must be static */ 744 FSE_FLUSHBITS(&bitC); 745 746 FSE_encodeSymbol(&bitC, &CState1, *--ip); 747 748 if (sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) { /* this test must be static */ 749 FSE_encodeSymbol(&bitC, &CState2, *--ip); 750 FSE_encodeSymbol(&bitC, &CState1, *--ip); 751 } 752 753 FSE_FLUSHBITS(&bitC); 754 } 755 756 FSE_flushCState(&bitC, &CState2); 757 FSE_flushCState(&bitC, &CState1); 758 return BIT_closeCStream(&bitC); 759 } 760 761 size_t FSE_compress_usingCTable (void* dst, size_t dstSize, 762 const void* src, size_t srcSize, 763 const FSE_CTable* ct) 764 { 765 unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize)); 766 767 if (fast) 768 return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1); 769 else 770 return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0); 771 } 772 773 774 size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); } 775 776 #define CHECK_V_F(e, f) size_t const e = f; if (ERR_isError(e)) return e 777 #define CHECK_F(f) { CHECK_V_F(_var_err__, f); } 778 779 /* FSE_compress_wksp() : 780 * Same as FSE_compress2(), but using an externally allocated scratch buffer (`workSpace`). 781 * `wkspSize` size must be `(1<<tableLog)`. 782 */ 783 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) 784 { 785 BYTE* const ostart = (BYTE*) dst; 786 BYTE* op = ostart; 787 BYTE* const oend = ostart + dstSize; 788 789 U32 count[FSE_MAX_SYMBOL_VALUE+1]; 790 S16 norm[FSE_MAX_SYMBOL_VALUE+1]; 791 FSE_CTable* CTable = (FSE_CTable*)workSpace; 792 size_t const CTableSize = FSE_CTABLE_SIZE_U32(tableLog, maxSymbolValue); 793 void* scratchBuffer = (void*)(CTable + CTableSize); 794 size_t const scratchBufferSize = wkspSize - (CTableSize * sizeof(FSE_CTable)); 795 796 /* init conditions */ 797 if (wkspSize < FSE_WKSP_SIZE_U32(tableLog, maxSymbolValue)) return ERROR(tableLog_tooLarge); 798 if (srcSize <= 1) return 0; /* Not compressible */ 799 if (!maxSymbolValue) maxSymbolValue = FSE_MAX_SYMBOL_VALUE; 800 if (!tableLog) tableLog = FSE_DEFAULT_TABLELOG; 801 802 /* Scan input and build symbol stats */ 803 { CHECK_V_F(maxCount, FSE_count_wksp(count, &maxSymbolValue, src, srcSize, (unsigned*)scratchBuffer) ); 804 if (maxCount == srcSize) return 1; /* only a single symbol in src : rle */ 805 if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */ 806 if (maxCount < (srcSize >> 7)) return 0; /* Heuristic : not compressible enough */ 807 } 808 809 tableLog = FSE_optimalTableLog(tableLog, srcSize, maxSymbolValue); 810 CHECK_F( FSE_normalizeCount(norm, tableLog, count, srcSize, maxSymbolValue) ); 811 812 /* Write table description header */ 813 { CHECK_V_F(nc_err, FSE_writeNCount(op, oend-op, norm, maxSymbolValue, tableLog) ); 814 op += nc_err; 815 } 816 817 /* Compress */ 818 CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, scratchBufferSize) ); 819 { CHECK_V_F(cSize, FSE_compress_usingCTable(op, oend - op, src, srcSize, CTable) ); 820 if (cSize == 0) return 0; /* not enough space for compressed data */ 821 op += cSize; 822 } 823 824 /* check compressibility */ 825 if ( (size_t)(op-ostart) >= srcSize-1 ) return 0; 826 827 return op-ostart; 828 } 829 830 typedef struct { 831 FSE_CTable CTable_max[FSE_CTABLE_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)]; 832 BYTE scratchBuffer[1 << FSE_MAX_TABLELOG]; 833 } fseWkspMax_t; 834 835 size_t FSE_compress2 (void* dst, size_t dstCapacity, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog) 836 { 837 fseWkspMax_t scratchBuffer; 838 FSE_STATIC_ASSERT(sizeof(scratchBuffer) >= FSE_WKSP_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)); /* compilation failures here means scratchBuffer is not large enough */ 839 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); 840 return FSE_compress_wksp(dst, dstCapacity, src, srcSize, maxSymbolValue, tableLog, &scratchBuffer, sizeof(scratchBuffer)); 841 } 842 843 size_t FSE_compress (void* dst, size_t dstCapacity, const void* src, size_t srcSize) 844 { 845 return FSE_compress2(dst, dstCapacity, src, srcSize, FSE_MAX_SYMBOL_VALUE, FSE_DEFAULT_TABLELOG); 846 } 847 848 849 #endif /* FSE_COMMONDEFS_ONLY */ 850