Scott Baker | e7144bc | 2019-10-01 14:16:47 -0700 | [diff] [blame^] | 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 */ |