zstd/compress/fse_compress.c

0001 /* ******************************************************************
0002  * FSE : Finite State Entropy encoder
0003  * Copyright (c) Yann Collet, Facebook, Inc.
0004  *
0005  *  You can contact the author at :
0006  *  - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
0007  *  - Public forum : https://groups.google.com/forum/#!forum/lz4c
0008  *
0009  * This source code is licensed under both the BSD-style license (found in the
0010  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
0011  * in the COPYING file in the root directory of this source tree).
0012  * You may select, at your option, one of the above-listed licenses.
0013 ****************************************************************** */
0014
0015 /* **************************************************************
0016 *  Includes
0017 ****************************************************************/
0018 #include "../common/compiler.h"
0019 #include "../common/mem.h"        /* U32, U16, etc. */
0020 #include "../common/debug.h"      /* assert, DEBUGLOG */
0021 #include "hist.h"       /* HIST_count_wksp */
0022 #include "../common/bitstream.h"
0023 #define FSE_STATIC_LINKING_ONLY
0024 #include "../common/fse.h"
0025 #include "../common/error_private.h"
0026 #define ZSTD_DEPS_NEED_MALLOC
0027 #define ZSTD_DEPS_NEED_MATH64
0028 #include "../common/zstd_deps.h"  /* ZSTD_malloc, ZSTD_free, ZSTD_memcpy, ZSTD_memset */
0029
0030
0031 /* **************************************************************
0032 *  Error Management
0033 ****************************************************************/
0034 #define FSE_isError ERR_isError
0035
0036
0037 /* **************************************************************
0038 *  Templates
0039 ****************************************************************/
0040 /*
0041   designed to be included
0042   for type-specific functions (template emulation in C)
0043   Objective is to write these functions only once, for improved maintenance
0044 */
0045
0046 /* safety checks */
0047 #ifndef FSE_FUNCTION_EXTENSION
0048 #  error "FSE_FUNCTION_EXTENSION must be defined"
0049 #endif
0050 #ifndef FSE_FUNCTION_TYPE
0051 #  error "FSE_FUNCTION_TYPE must be defined"
0052 #endif
0053
0054 /* Function names */
0055 #define FSE_CAT(X,Y) X##Y
0056 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
0057 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
0058
0059
0060 /* Function templates */
0061
0062 /* FSE_buildCTable_wksp() :
0063  * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`).
0064  * wkspSize should be sized to handle worst case situation, which is `1<<max_tableLog * sizeof(FSE_FUNCTION_TYPE)`
0065  * workSpace must also be properly aligned with FSE_FUNCTION_TYPE requirements
0066  */
0067 size_t FSE_buildCTable_wksp(FSE_CTable* ct,
0068                       const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
0069                             void* workSpace, size_t wkspSize)
0070 {
0071     U32 const tableSize = 1 << tableLog;
0072     U32 const tableMask = tableSize - 1;
0073     void* const ptr = ct;
0074     U16* const tableU16 = ( (U16*) ptr) + 2;
0075     void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableLog ? tableSize>>1 : 1) ;
0076     FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
0077     U32 const step = FSE_TABLESTEP(tableSize);
0078
0079     U32* cumul = (U32*)workSpace;
0080     FSE_FUNCTION_TYPE* tableSymbol = (FSE_FUNCTION_TYPE*)(cumul + (maxSymbolValue + 2));
0081
0082     U32 highThreshold = tableSize-1;
0083
0084     if ((size_t)workSpace & 3) return ERROR(GENERIC); /* Must be 4 byte aligned */
0085     if (FSE_BUILD_CTABLE_WORKSPACE_SIZE(maxSymbolValue, tableLog) > wkspSize) return ERROR(tableLog_tooLarge);
0086     /* CTable header */
0087     tableU16[-2] = (U16) tableLog;
0088     tableU16[-1] = (U16) maxSymbolValue;
0089     assert(tableLog < 16);   /* required for threshold strategy to work */
0090
0091     /* For explanations on how to distribute symbol values over the table :
0092      * http://fastcompression.blogspot.fr/2014/02/fse-distributing-symbol-values.html */
0093
0094      #ifdef __clang_analyzer__
0095      ZSTD_memset(tableSymbol, 0, sizeof(*tableSymbol) * tableSize);   /* useless initialization, just to keep scan-build happy */
0096      #endif
0097
0098     /* symbol start positions */
0099     {   U32 u;
0100         cumul[0] = 0;
0101         for (u=1; u <= maxSymbolValue+1; u++) {
0102             if (normalizedCounter[u-1]==-1) {  /* Low proba symbol */
0103                 cumul[u] = cumul[u-1] + 1;
0104                 tableSymbol[highThreshold--] = (FSE_FUNCTION_TYPE)(u-1);
0105             } else {
0106                 cumul[u] = cumul[u-1] + normalizedCounter[u-1];
0107         }   }
0108         cumul[maxSymbolValue+1] = tableSize+1;
0109     }
0110
0111     /* Spread symbols */
0112     {   U32 position = 0;
0113         U32 symbol;
0114         for (symbol=0; symbol<=maxSymbolValue; symbol++) {
0115             int nbOccurrences;
0116             int const freq = normalizedCounter[symbol];
0117             for (nbOccurrences=0; nbOccurrences<freq; nbOccurrences++) {
0118                 tableSymbol[position] = (FSE_FUNCTION_TYPE)symbol;
0119                 position = (position + step) & tableMask;
0120                 while (position > highThreshold)
0121                     position = (position + step) & tableMask;   /* Low proba area */
0122         }   }
0123
0124         assert(position==0);  /* Must have initialized all positions */
0125     }
0126
0127     /* Build table */
0128     {   U32 u; for (u=0; u<tableSize; u++) {
0129         FSE_FUNCTION_TYPE s = tableSymbol[u];   /* note : static analyzer may not understand tableSymbol is properly initialized */
0130         tableU16[cumul[s]++] = (U16) (tableSize+u);   /* TableU16 : sorted by symbol order; gives next state value */
0131     }   }
0132
0133     /* Build Symbol Transformation Table */
0134     {   unsigned total = 0;
0135         unsigned s;
0136         for (s=0; s<=maxSymbolValue; s++) {
0137             switch (normalizedCounter[s])
0138             {
0139             case  0:
0140                 /* filling nonetheless, for compatibility with FSE_getMaxNbBits() */
0141                 symbolTT[s].deltaNbBits = ((tableLog+1) << 16) - (1<<tableLog);
0142                 break;
0143
0144             case -1:
0145             case  1:
0146                 symbolTT[s].deltaNbBits = (tableLog << 16) - (1<<tableLog);
0147                 symbolTT[s].deltaFindState = total - 1;
0148                 total ++;
0149                 break;
0150             default :
0151                 {
0152                     U32 const maxBitsOut = tableLog - BIT_highbit32 (normalizedCounter[s]-1);
0153                     U32 const minStatePlus = normalizedCounter[s] << maxBitsOut;
0154                     symbolTT[s].deltaNbBits = (maxBitsOut << 16) - minStatePlus;
0155                     symbolTT[s].deltaFindState = total - normalizedCounter[s];
0156                     total +=  normalizedCounter[s];
0157     }   }   }   }
0158
0159 #if 0  /* debug : symbol costs */
0160     DEBUGLOG(5, "\n --- table statistics : ");
0161     {   U32 symbol;
0162         for (symbol=0; symbol<=maxSymbolValue; symbol++) {
0163             DEBUGLOG(5, "%3u: w=%3i,   maxBits=%u, fracBits=%.2f",
0164                 symbol, normalizedCounter[symbol],
0165                 FSE_getMaxNbBits(symbolTT, symbol),
0166                 (double)FSE_bitCost(symbolTT, tableLog, symbol, 8) / 256);
0167         }
0168     }
0169 #endif
0170
0171     return 0;
0172 }
0173
0174
0175
0176
0177 #ifndef FSE_COMMONDEFS_ONLY
0178
0179
0180 /*-**************************************************************
0181 *  FSE NCount encoding
0182 ****************************************************************/
0183 size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
0184 {
0185     size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3;
0186     return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND;  /* maxSymbolValue==0 ? use default */
0187 }
0188
0189 static size_t
0190 FSE_writeNCount_generic (void* header, size_t headerBufferSize,
0191                    const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
0192                          unsigned writeIsSafe)
0193 {
0194     BYTE* const ostart = (BYTE*) header;
0195     BYTE* out = ostart;
0196     BYTE* const oend = ostart + headerBufferSize;
0197     int nbBits;
0198     const int tableSize = 1 << tableLog;
0199     int remaining;
0200     int threshold;
0201     U32 bitStream = 0;
0202     int bitCount = 0;
0203     unsigned symbol = 0;
0204     unsigned const alphabetSize = maxSymbolValue + 1;
0205     int previousIs0 = 0;
0206
0207     /* Table Size */
0208     bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount;
0209     bitCount  += 4;
0210
0211     /* Init */
0212     remaining = tableSize+1;   /* +1 for extra accuracy */
0213     threshold = tableSize;
0214     nbBits = tableLog+1;
0215
0216     while ((symbol < alphabetSize) && (remaining>1)) {  /* stops at 1 */
0217         if (previousIs0) {
0218             unsigned start = symbol;
0219             while ((symbol < alphabetSize) && !normalizedCounter[symbol]) symbol++;
0220             if (symbol == alphabetSize) break;   /* incorrect distribution */
0221             while (symbol >= start+24) {
0222                 start+=24;
0223                 bitStream += 0xFFFFU << bitCount;
0224                 if ((!writeIsSafe) && (out > oend-2))
0225                     return ERROR(dstSize_tooSmall);   /* Buffer overflow */
0226                 out[0] = (BYTE) bitStream;
0227                 out[1] = (BYTE)(bitStream>>8);
0228                 out+=2;
0229                 bitStream>>=16;
0230             }
0231             while (symbol >= start+3) {
0232                 start+=3;
0233                 bitStream += 3 << bitCount;
0234                 bitCount += 2;
0235             }
0236             bitStream += (symbol-start) << bitCount;
0237             bitCount += 2;
0238             if (bitCount>16) {
0239                 if ((!writeIsSafe) && (out > oend - 2))
0240                     return ERROR(dstSize_tooSmall);   /* Buffer overflow */
0241                 out[0] = (BYTE)bitStream;
0242                 out[1] = (BYTE)(bitStream>>8);
0243                 out += 2;
0244                 bitStream >>= 16;
0245                 bitCount -= 16;
0246         }   }
0247         {   int count = normalizedCounter[symbol++];
0248             int const max = (2*threshold-1) - remaining;
0249             remaining -= count < 0 ? -count : count;
0250             count++;   /* +1 for extra accuracy */
0251             if (count>=threshold)
0252                 count += max;   /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */
0253             bitStream += count << bitCount;
0254             bitCount  += nbBits;
0255             bitCount  -= (count<max);
0256             previousIs0  = (count==1);
0257             if (remaining<1) return ERROR(GENERIC);
0258             while (remaining<threshold) { nbBits--; threshold>>=1; }
0259         }
0260         if (bitCount>16) {
0261             if ((!writeIsSafe) && (out > oend - 2))
0262                 return ERROR(dstSize_tooSmall);   /* Buffer overflow */
0263             out[0] = (BYTE)bitStream;
0264             out[1] = (BYTE)(bitStream>>8);
0265             out += 2;
0266             bitStream >>= 16;
0267             bitCount -= 16;
0268     }   }
0269
0270     if (remaining != 1)
0271         return ERROR(GENERIC);  /* incorrect normalized distribution */
0272     assert(symbol <= alphabetSize);
0273
0274     /* flush remaining bitStream */
0275     if ((!writeIsSafe) && (out > oend - 2))
0276         return ERROR(dstSize_tooSmall);   /* Buffer overflow */
0277     out[0] = (BYTE)bitStream;
0278     out[1] = (BYTE)(bitStream>>8);
0279     out+= (bitCount+7) /8;
0280
0281     return (out-ostart);
0282 }
0283
0284
0285 size_t FSE_writeNCount (void* buffer, size_t bufferSize,
0286                   const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
0287 {
0288     if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);   /* Unsupported */
0289     if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC);   /* Unsupported */
0290
0291     if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
0292         return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0);
0293
0294     return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1 /* write in buffer is safe */);
0295 }
0296
0297
0298 /*-**************************************************************
0299 *  FSE Compression Code
0300 ****************************************************************/
0301
0302 FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog)
0303 {
0304     size_t size;
0305     if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
0306     size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32);
0307     return (FSE_CTable*)ZSTD_malloc(size);
0308 }
0309
0310 void FSE_freeCTable (FSE_CTable* ct) { ZSTD_free(ct); }
0311
0312 /* provides the minimum logSize to safely represent a distribution */
0313 static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
0314 {
0315     U32 minBitsSrc = BIT_highbit32((U32)(srcSize)) + 1;
0316     U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2;
0317     U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
0318     assert(srcSize > 1); /* Not supported, RLE should be used instead */
0319     return minBits;
0320 }
0321
0322 unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
0323 {
0324     U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus;
0325     U32 tableLog = maxTableLog;
0326     U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
0327     assert(srcSize > 1); /* Not supported, RLE should be used instead */
0328     if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
0329     if (maxBitsSrc < tableLog) tableLog = maxBitsSrc;   /* Accuracy can be reduced */
0330     if (minBits > tableLog) tableLog = minBits;   /* Need a minimum to safely represent all symbol values */
0331     if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG;
0332     if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG;
0333     return tableLog;
0334 }
0335
0336 unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
0337 {
0338     return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
0339 }
0340
0341 /* Secondary normalization method.
0342    To be used when primary method fails. */
0343
0344 static size_t FSE_normalizeM2(short* norm, U32 tableLog, const unsigned* count, size_t total, U32 maxSymbolValue, short lowProbCount)
0345 {
0346     short const NOT_YET_ASSIGNED = -2;
0347     U32 s;
0348     U32 distributed = 0;
0349     U32 ToDistribute;
0350
0351     /* Init */
0352     U32 const lowThreshold = (U32)(total >> tableLog);
0353     U32 lowOne = (U32)((total * 3) >> (tableLog + 1));
0354
0355     for (s=0; s<=maxSymbolValue; s++) {
0356         if (count[s] == 0) {
0357             norm[s]=0;
0358             continue;
0359         }
0360         if (count[s] <= lowThreshold) {
0361             norm[s] = lowProbCount;
0362             distributed++;
0363             total -= count[s];
0364             continue;
0365         }
0366         if (count[s] <= lowOne) {
0367             norm[s] = 1;
0368             distributed++;
0369             total -= count[s];
0370             continue;
0371         }
0372
0373         norm[s]=NOT_YET_ASSIGNED;
0374     }
0375     ToDistribute = (1 << tableLog) - distributed;
0376
0377     if (ToDistribute == 0)
0378         return 0;
0379
0380     if ((total / ToDistribute) > lowOne) {
0381         /* risk of rounding to zero */
0382         lowOne = (U32)((total * 3) / (ToDistribute * 2));
0383         for (s=0; s<=maxSymbolValue; s++) {
0384             if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) {
0385                 norm[s] = 1;
0386                 distributed++;
0387                 total -= count[s];
0388                 continue;
0389         }   }
0390         ToDistribute = (1 << tableLog) - distributed;
0391     }
0392
0393     if (distributed == maxSymbolValue+1) {
0394         /* all values are pretty poor;
0395            probably incompressible data (should have already been detected);
0396            find max, then give all remaining points to max */
0397         U32 maxV = 0, maxC = 0;
0398         for (s=0; s<=maxSymbolValue; s++)
0399             if (count[s] > maxC) { maxV=s; maxC=count[s]; }
0400         norm[maxV] += (short)ToDistribute;
0401         return 0;
0402     }
0403
0404     if (total == 0) {
0405         /* all of the symbols were low enough for the lowOne or lowThreshold */
0406         for (s=0; ToDistribute > 0; s = (s+1)%(maxSymbolValue+1))
0407             if (norm[s] > 0) { ToDistribute--; norm[s]++; }
0408         return 0;
0409     }
0410
0411     {   U64 const vStepLog = 62 - tableLog;
0412         U64 const mid = (1ULL << (vStepLog-1)) - 1;
0413         U64 const rStep = ZSTD_div64((((U64)1<<vStepLog) * ToDistribute) + mid, (U32)total);   /* scale on remaining */
0414         U64 tmpTotal = mid;
0415         for (s=0; s<=maxSymbolValue; s++) {
0416             if (norm[s]==NOT_YET_ASSIGNED) {
0417                 U64 const end = tmpTotal + (count[s] * rStep);
0418                 U32 const sStart = (U32)(tmpTotal >> vStepLog);
0419                 U32 const sEnd = (U32)(end >> vStepLog);
0420                 U32 const weight = sEnd - sStart;
0421                 if (weight < 1)
0422                     return ERROR(GENERIC);
0423                 norm[s] = (short)weight;
0424                 tmpTotal = end;
0425     }   }   }
0426
0427     return 0;
0428 }
0429
0430 size_t FSE_normalizeCount (short* normalizedCounter, unsigned tableLog,
0431                            const unsigned* count, size_t total,
0432                            unsigned maxSymbolValue, unsigned useLowProbCount)
0433 {
0434     /* Sanity checks */
0435     if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
0436     if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC);   /* Unsupported size */
0437     if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);   /* Unsupported size */
0438     if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC);   /* Too small tableLog, compression potentially impossible */
0439
0440     {   static U32 const rtbTable[] = {     0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
0441         short const lowProbCount = useLowProbCount ? -1 : 1;
0442         U64 const scale = 62 - tableLog;
0443         U64 const step = ZSTD_div64((U64)1<<62, (U32)total);   /* <== here, one division ! */
0444         U64 const vStep = 1ULL<<(scale-20);
0445         int stillToDistribute = 1<<tableLog;
0446         unsigned s;
0447         unsigned largest=0;
0448         short largestP=0;
0449         U32 lowThreshold = (U32)(total >> tableLog);
0450
0451         for (s=0; s<=maxSymbolValue; s++) {
0452             if (count[s] == total) return 0;   /* rle special case */
0453             if (count[s] == 0) { normalizedCounter[s]=0; continue; }
0454             if (count[s] <= lowThreshold) {
0455                 normalizedCounter[s] = lowProbCount;
0456                 stillToDistribute--;
0457             } else {
0458                 short proba = (short)((count[s]*step) >> scale);
0459                 if (proba<8) {
0460                     U64 restToBeat = vStep * rtbTable[proba];
0461                     proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat;
0462                 }
0463                 if (proba > largestP) { largestP=proba; largest=s; }
0464                 normalizedCounter[s] = proba;
0465                 stillToDistribute -= proba;
0466         }   }
0467         if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
0468             /* corner case, need another normalization method */
0469             size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue, lowProbCount);
0470             if (FSE_isError(errorCode)) return errorCode;
0471         }
0472         else normalizedCounter[largest] += (short)stillToDistribute;
0473     }
0474
0475 #if 0
0476     {   /* Print Table (debug) */
0477         U32 s;
0478         U32 nTotal = 0;
0479         for (s=0; s<=maxSymbolValue; s++)
0480             RAWLOG(2, "%3i: %4i \n", s, normalizedCounter[s]);
0481         for (s=0; s<=maxSymbolValue; s++)
0482             nTotal += abs(normalizedCounter[s]);
0483         if (nTotal != (1U<<tableLog))
0484             RAWLOG(2, "Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog);
0485         getchar();
0486     }
0487 #endif
0488
0489     return tableLog;
0490 }
0491
0492
0493 /* fake FSE_CTable, for raw (uncompressed) input */
0494 size_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits)
0495 {
0496     const unsigned tableSize = 1 << nbBits;
0497     const unsigned tableMask = tableSize - 1;
0498     const unsigned maxSymbolValue = tableMask;
0499     void* const ptr = ct;
0500     U16* const tableU16 = ( (U16*) ptr) + 2;
0501     void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableSize>>1);   /* assumption : tableLog >= 1 */
0502     FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
0503     unsigned s;
0504
0505     /* Sanity checks */
0506     if (nbBits < 1) return ERROR(GENERIC);             /* min size */
0507
0508     /* header */
0509     tableU16[-2] = (U16) nbBits;
0510     tableU16[-1] = (U16) maxSymbolValue;
0511
0512     /* Build table */
0513     for (s=0; s<tableSize; s++)
0514         tableU16[s] = (U16)(tableSize + s);
0515
0516     /* Build Symbol Transformation Table */
0517     {   const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits);
0518         for (s=0; s<=maxSymbolValue; s++) {
0519             symbolTT[s].deltaNbBits = deltaNbBits;
0520             symbolTT[s].deltaFindState = s-1;
0521     }   }
0522
0523     return 0;
0524 }
0525
0526 /* fake FSE_CTable, for rle input (always same symbol) */
0527 size_t FSE_buildCTable_rle (FSE_CTable* ct, BYTE symbolValue)
0528 {
0529     void* ptr = ct;
0530     U16* tableU16 = ( (U16*) ptr) + 2;
0531     void* FSCTptr = (U32*)ptr + 2;
0532     FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr;
0533
0534     /* header */
0535     tableU16[-2] = (U16) 0;
0536     tableU16[-1] = (U16) symbolValue;
0537
0538     /* Build table */
0539     tableU16[0] = 0;
0540     tableU16[1] = 0;   /* just in case */
0541
0542     /* Build Symbol Transformation Table */
0543     symbolTT[symbolValue].deltaNbBits = 0;
0544     symbolTT[symbolValue].deltaFindState = 0;
0545
0546     return 0;
0547 }
0548
0549
0550 static size_t FSE_compress_usingCTable_generic (void* dst, size_t dstSize,
0551                            const void* src, size_t srcSize,
0552                            const FSE_CTable* ct, const unsigned fast)
0553 {
0554     const BYTE* const istart = (const BYTE*) src;
0555     const BYTE* const iend = istart + srcSize;
0556     const BYTE* ip=iend;
0557
0558     BIT_CStream_t bitC;
0559     FSE_CState_t CState1, CState2;
0560
0561     /* init */
0562     if (srcSize <= 2) return 0;
0563     { size_t const initError = BIT_initCStream(&bitC, dst, dstSize);
0564       if (FSE_isError(initError)) return 0; /* not enough space available to write a bitstream */ }
0565
0566 #define FSE_FLUSHBITS(s)  (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
0567
0568     if (srcSize & 1) {
0569         FSE_initCState2(&CState1, ct, *--ip);
0570         FSE_initCState2(&CState2, ct, *--ip);
0571         FSE_encodeSymbol(&bitC, &CState1, *--ip);
0572         FSE_FLUSHBITS(&bitC);
0573     } else {
0574         FSE_initCState2(&CState2, ct, *--ip);
0575         FSE_initCState2(&CState1, ct, *--ip);
0576     }
0577
0578     /* join to mod 4 */
0579     srcSize -= 2;
0580     if ((sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) && (srcSize & 2)) {  /* test bit 2 */
0581         FSE_encodeSymbol(&bitC, &CState2, *--ip);
0582         FSE_encodeSymbol(&bitC, &CState1, *--ip);
0583         FSE_FLUSHBITS(&bitC);
0584     }
0585
0586     /* 2 or 4 encoding per loop */
0587     while ( ip>istart ) {
0588
0589         FSE_encodeSymbol(&bitC, &CState2, *--ip);
0590
0591         if (sizeof(bitC.bitContainer)*8 < FSE_MAX_TABLELOG*2+7 )   /* this test must be static */
0592             FSE_FLUSHBITS(&bitC);
0593
0594         FSE_encodeSymbol(&bitC, &CState1, *--ip);
0595
0596         if (sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) {  /* this test must be static */
0597             FSE_encodeSymbol(&bitC, &CState2, *--ip);
0598             FSE_encodeSymbol(&bitC, &CState1, *--ip);
0599         }
0600
0601         FSE_FLUSHBITS(&bitC);
0602     }
0603
0604     FSE_flushCState(&bitC, &CState2);
0605     FSE_flushCState(&bitC, &CState1);
0606     return BIT_closeCStream(&bitC);
0607 }
0608
0609 size_t FSE_compress_usingCTable (void* dst, size_t dstSize,
0610                            const void* src, size_t srcSize,
0611                            const FSE_CTable* ct)
0612 {
0613     unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
0614
0615     if (fast)
0616         return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1);
0617     else
0618         return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0);
0619 }
0620
0621
0622 size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); }
0623
0624
0625 #endif   /* FSE_COMMONDEFS_ONLY */