lib/zstd/compress/fse_compress.c

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