fse_compress.c File Reference

#include <stdlib.h>
#include <string.h>
#include "compiler.h"
#include "mem.h"
#include "debug.h"
#include "hist.h"
#include "bitstream.h"
#include "fse.h"
#include "error_private.h"
#include <ntifs.h>
#include <ntddk.h>

Include dependency graph for fse_compress.c:

Go to the source code of this file.

Classes
struct	fseWkspMax_t

Macros
#define	FSE_STATIC_LINKING_ONLY
#define	FSE_isError   ERR_isError
#define	FSE_CAT(X, Y)   X##Y
#define	FSE_FUNCTION_NAME(X, Y)   FSE_CAT(X,Y)
#define	FSE_TYPE_NAME(X, Y)   FSE_CAT(X,Y)
#define	FSEC_ALLOC_TAG   0x64455346
#define	FSE_FLUSHBITS(s)   (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))

Functions
size_t	FSE_buildCTable_wksp (FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize)
size_t	FSE_buildCTable (FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
size_t	FSE_NCountWriteBound (unsigned maxSymbolValue, unsigned tableLog)
static size_t	FSE_writeNCount_generic (void *header, size_t headerBufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, unsigned writeIsSafe)
size_t	FSE_writeNCount (void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
FSE_CTable *	FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog)
void	FSE_freeCTable (FSE_CTable *ct)
static unsigned	FSE_minTableLog (size_t srcSize, unsigned maxSymbolValue)
unsigned	FSE_optimalTableLog_internal (unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
unsigned	FSE_optimalTableLog (unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
static size_t	FSE_normalizeM2 (short *norm, U32 tableLog, const unsigned *count, size_t total, U32 maxSymbolValue)
size_t	FSE_normalizeCount (short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t total, unsigned maxSymbolValue)
size_t	FSE_buildCTable_raw (FSE_CTable *ct, unsigned nbBits)
size_t	FSE_buildCTable_rle (FSE_CTable *ct, BYTE symbolValue)
static size_t	FSE_compress_usingCTable_generic (void *dst, size_t dstSize, const void *src, size_t srcSize, const FSE_CTable *ct, const unsigned fast)
size_t	FSE_compress_usingCTable (void *dst, size_t dstSize, const void *src, size_t srcSize, const FSE_CTable *ct)
size_t	FSE_compressBound (size_t size)
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)
size_t	FSE_compress2 (void *dst, size_t dstCapacity, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog)
size_t	FSE_compress (void *dst, size_t dstCapacity, const void *src, size_t srcSize)

Macro Definition Documentation

FSE_CAT

#define FSE_CAT	(		X,
			Y
	)		X##Y

Definition at line 56 of file fse_compress.c.

FSE_FLUSHBITS

#define FSE_FLUSHBITS

(

s

)

(fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))

FSE_FUNCTION_NAME

#define FSE_FUNCTION_NAME	(		X,
			Y
	)		FSE_CAT(X,Y)

Definition at line 57 of file fse_compress.c.

FSE_isError

#define FSE_isError   ERR_isError

Definition at line 35 of file fse_compress.c.

FSE_STATIC_LINKING_ONLY

#define FSE_STATIC_LINKING_ONLY

Definition at line 25 of file fse_compress.c.

FSE_TYPE_NAME

#define FSE_TYPE_NAME	(		X,
			Y
	)		FSE_CAT(X,Y)

Definition at line 58 of file fse_compress.c.

FSEC_ALLOC_TAG

#define FSEC_ALLOC_TAG   0x64455346

Definition at line 60 of file fse_compress.c.

Function Documentation

FSE_buildCTable()

size_t FSE_buildCTable	(	FSE_CTable *	ct,
		const short *	normalizedCounter,
		unsigned	maxSymbolValue,
		unsigned	tableLog
	)

FSE_buildCTable(): Builds ct, which must be already allocated, using FSE_createCTable().

Returns

: 0, or an errorCode, which can be tested using FSE_isError()

Definition at line 175 of file fse_compress.c.

{
    FSE_FUNCTION_TYPE tableSymbol[FSE_MAX_TABLESIZE];   /* memset() is not necessary, even if static analyzer complain about it */
    return FSE_buildCTable_wksp(ct, normalizedCounter, maxSymbolValue, tableLog, tableSymbol, sizeof(tableSymbol));
}

FSE_buildCTable_raw()

size_t FSE_buildCTable_raw	(	FSE_CTable *	ct,
		unsigned	nbBits
	)

Definition at line 501 of file fse_compress.c.

{
    const unsigned tableSize = 1 << nbBits;
    const unsigned tableMask = tableSize - 1;
    const unsigned maxSymbolValue = tableMask;
    void* const ptr = ct;
    U16* const tableU16 = ( (U16*) ptr) + 2;
    void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableSize>>1);   /* assumption : tableLog >= 1 */
    FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
    unsigned s;
 
    /* Sanity checks */
    if (nbBits < 1) return ERROR(GENERIC);             /* min size */
 
    /* header */
    tableU16[-2] = (U16) nbBits;
    tableU16[-1] = (U16) maxSymbolValue;
 
    /* Build table */
    for (s=0; s<tableSize; s++)
        tableU16[s] = (U16)(tableSize + s);
 
    /* Build Symbol Transformation Table */
    {   const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits);
        for (s=0; s<=maxSymbolValue; s++) {
            symbolTT[s].deltaNbBits = deltaNbBits;
            symbolTT[s].deltaFindState = s-1;
    }   }
 
    return 0;
}

FSE_buildCTable_rle()

size_t FSE_buildCTable_rle	(	FSE_CTable *	ct,
		BYTE	symbolValue
	)

Definition at line 534 of file fse_compress.c.

{
    void* ptr = ct;
    U16* tableU16 = ( (U16*) ptr) + 2;
    void* FSCTptr = (U32*)ptr + 2;
    FSE_symbolCompressionTransform* symbolTT = (FSE_symbolCompressionTransform*) FSCTptr;
 
    /* header */
    tableU16[-2] = (U16) 0;
    tableU16[-1] = (U16) symbolValue;
 
    /* Build table */
    tableU16[0] = 0;
    tableU16[1] = 0;   /* just in case */
 
    /* Build Symbol Transformation Table */
    symbolTT[symbolValue].deltaNbBits = 0;
    symbolTT[symbolValue].deltaFindState = 0;
 
    return 0;
}

Referenced by ZSTD_buildCTable().

FSE_buildCTable_wksp()

size_t FSE_buildCTable_wksp	(	FSE_CTable *	ct,
		const short *	normalizedCounter,
		unsigned	maxSymbolValue,
		unsigned	tableLog,
		void *	workSpace,
		size_t	wkspSize
	)

Definition at line 69 of file fse_compress.c.

{
    U32 const tableSize = 1 << tableLog;
    U32 const tableMask = tableSize - 1;
    void* const ptr = ct;
    U16* const tableU16 = ( (U16*) ptr) + 2;
    void* const FSCT = ((U32*)ptr) + 1 /* header */ + (tableLog ? tableSize>>1 : 1) ;
    FSE_symbolCompressionTransform* const symbolTT = (FSE_symbolCompressionTransform*) (FSCT);
    U32 const step = FSE_TABLESTEP(tableSize);
    U32 cumul[FSE_MAX_SYMBOL_VALUE+2];
 
    FSE_FUNCTION_TYPE* const tableSymbol = (FSE_FUNCTION_TYPE*)workSpace;
    U32 highThreshold = tableSize-1;
 
    /* CTable header */
    if (((size_t)1 << tableLog) * sizeof(FSE_FUNCTION_TYPE) > wkspSize) return ERROR(tableLog_tooLarge);
    tableU16[-2] = (U16) tableLog;
    tableU16[-1] = (U16) maxSymbolValue;
    assert(tableLog < 16);   /* required for threshold strategy to work */
 
    /* For explanations on how to distribute symbol values over the table :
     * http://fastcompression.blogspot.fr/2014/02/fse-distributing-symbol-values.html */
 
     #ifdef __clang_analyzer__
     memset(tableSymbol, 0, sizeof(*tableSymbol) * tableSize);   /* useless initialization, just to keep scan-build happy */
     #endif
 
    /* symbol start positions */
    {   U32 u;
        cumul[0] = 0;
        for (u=1; u <= maxSymbolValue+1; u++) {
            if (normalizedCounter[u-1]==-1) {  /* Low proba symbol */
                cumul[u] = cumul[u-1] + 1;
                tableSymbol[highThreshold--] = (FSE_FUNCTION_TYPE)(u-1);
            } else {
                cumul[u] = cumul[u-1] + normalizedCounter[u-1];
        }   }
        cumul[maxSymbolValue+1] = tableSize+1;
    }
 
    /* Spread symbols */
    {   U32 position = 0;
        U32 symbol;
        for (symbol=0; symbol<=maxSymbolValue; symbol++) {
            int nbOccurrences;
            int const freq = normalizedCounter[symbol];
            for (nbOccurrences=0; nbOccurrences<freq; nbOccurrences++) {
                tableSymbol[position] = (FSE_FUNCTION_TYPE)symbol;
                position = (position + step) & tableMask;
                while (position > highThreshold)
                    position = (position + step) & tableMask;   /* Low proba area */
        }   }
 
        assert(position==0);  /* Must have initialized all positions */
    }
 
    /* Build table */
    {   U32 u; for (u=0; u<tableSize; u++) {
        FSE_FUNCTION_TYPE s = tableSymbol[u];   /* note : static analyzer may not understand tableSymbol is properly initialized */
        tableU16[cumul[s]++] = (U16) (tableSize+u);   /* TableU16 : sorted by symbol order; gives next state value */
    }   }
 
    /* Build Symbol Transformation Table */
    {   unsigned total = 0;
        unsigned s;
        for (s=0; s<=maxSymbolValue; s++) {
            switch (normalizedCounter[s])
            {
            case  0:
                /* filling nonetheless, for compatibility with FSE_getMaxNbBits() */
                symbolTT[s].deltaNbBits = ((tableLog+1) << 16) - (1<<tableLog);
                break;
 
            case -1:
            case  1:
                symbolTT[s].deltaNbBits = (tableLog << 16) - (1<<tableLog);
                symbolTT[s].deltaFindState = total - 1;
                total ++;
                break;
            default :
                {
                    U32 const maxBitsOut = tableLog - BIT_highbit32 (normalizedCounter[s]-1);
                    U32 const minStatePlus = normalizedCounter[s] << maxBitsOut;
                    symbolTT[s].deltaNbBits = (maxBitsOut << 16) - minStatePlus;
                    symbolTT[s].deltaFindState = total - normalizedCounter[s];
                    total +=  normalizedCounter[s];
    }   }   }   }
 
#if 0  /* debug : symbol costs */
    DEBUGLOG(5, "\n --- table statistics : ");
    {   U32 symbol;
        for (symbol=0; symbol<=maxSymbolValue; symbol++) {
            DEBUGLOG(5, "%3u: w=%3i,   maxBits=%u, fracBits=%.2f",
                symbol, normalizedCounter[symbol],
                FSE_getMaxNbBits(symbolTT, symbol),
                (double)FSE_bitCost(symbolTT, tableLog, symbol, 8) / 256);
        }
    }
#endif
 
    return 0;
}

Referenced by FSE_buildCTable(), FSE_compress_wksp(), HUF_compressWeights(), ZSTD_buildCTable(), and ZSTD_loadCEntropy().

FSE_compress()

size_t FSE_compress	(	void *	dst,
		size_t	dstCapacity,
		const void *	src,
		size_t	srcSize
	)

FSE_compress() : Compress content of buffer 'src', of size 'srcSize', into destination buffer 'dst'. 'dst' buffer must be already allocated. Compression runs faster is dstCapacity >= FSE_compressBound(srcSize).

Returns

: size of compressed data (<= dstCapacity). Special values : if return == 0, srcData is not compressible => Nothing is stored within dst !!! if return == 1, srcData is a single byte symbol * srcSize times. Use RLE compression instead. if FSE_isError(return), compression failed (more details using FSE_getErrorName())

Definition at line 695 of file fse_compress.c.

{
    return FSE_compress2(dst, dstCapacity, src, srcSize, FSE_MAX_SYMBOL_VALUE, FSE_DEFAULT_TABLELOG);
}

FSE_compress2()

size_t FSE_compress2	(	void *	dst,
		size_t	dstSize,
		const void *	src,
		size_t	srcSize,
		unsigned	maxSymbolValue,
		unsigned	tableLog
	)

FSE_compress2() : Same as FSE_compress(), but allows the selection of 'maxSymbolValue' and 'tableLog' Both parameters can be defined as '0' to mean : use default value

Returns

: size of compressed data Special values : if return == 0, srcData is not compressible => Nothing is stored within cSrc !!! if return == 1, srcData is a single byte symbol * srcSize times. Use RLE compression. if FSE_isError(return), it's an error code.

Definition at line 687 of file fse_compress.c.

{
    fseWkspMax_t scratchBuffer;
    DEBUG_STATIC_ASSERT(sizeof(scratchBuffer) >= FSE_WKSP_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE));   /* compilation failures here means scratchBuffer is not large enough */
    if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
    return FSE_compress_wksp(dst, dstCapacity, src, srcSize, maxSymbolValue, tableLog, &scratchBuffer, sizeof(scratchBuffer));
}

Referenced by FSE_compress().

FSE_compress_usingCTable()

size_t FSE_compress_usingCTable	(	void *	dst,
		size_t	dstCapacity,
		const void *	src,
		size_t	srcSize,
		const FSE_CTable *	ct
	)

FSE_compress_usingCTable(): Compress src using ct into dst which must be already allocated.

Returns

: size of compressed data (<= dstCapacity), or 0 if compressed data could not fit into dst, or an errorCode, which can be tested using FSE_isError()

Definition at line 616 of file fse_compress.c.

{
    unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
 
    if (fast)
        return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1);
    else
        return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0);
}

Referenced by FSE_compress_wksp(), and HUF_compressWeights().

FSE_compress_usingCTable_generic()

static size_t FSE_compress_usingCTable_generic ( void *  dst, size_t  dstSize, const void *  src, size_t  srcSize, const FSE_CTable *  ct, const unsigned  fast  )

static

Definition at line 557 of file fse_compress.c.

{
    const BYTE* const istart = (const BYTE*) src;
    const BYTE* const iend = istart + srcSize;
    const BYTE* ip=iend;
 
    BIT_CStream_t bitC;
    FSE_CState_t CState1, CState2;
 
    /* init */
    if (srcSize <= 2) return 0;
    { size_t const initError = BIT_initCStream(&bitC, dst, dstSize);
      if (FSE_isError(initError)) return 0; /* not enough space available to write a bitstream */ }
 
#define FSE_FLUSHBITS(s)  (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
 
    if (srcSize & 1) {
        FSE_initCState2(&CState1, ct, *--ip);
        FSE_initCState2(&CState2, ct, *--ip);
        FSE_encodeSymbol(&bitC, &CState1, *--ip);
        FSE_FLUSHBITS(&bitC);
    } else {
        FSE_initCState2(&CState2, ct, *--ip);
        FSE_initCState2(&CState1, ct, *--ip);
    }
 
    /* join to mod 4 */
    srcSize -= 2;
    if ((sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) && (srcSize & 2)) {  /* test bit 2 */
        FSE_encodeSymbol(&bitC, &CState2, *--ip);
        FSE_encodeSymbol(&bitC, &CState1, *--ip);
        FSE_FLUSHBITS(&bitC);
    }
 
    /* 2 or 4 encoding per loop */
    while ( ip>istart ) {
 
        FSE_encodeSymbol(&bitC, &CState2, *--ip);
 
        if (sizeof(bitC.bitContainer)*8 < FSE_MAX_TABLELOG*2+7 )   /* this test must be static */
            FSE_FLUSHBITS(&bitC);
 
        FSE_encodeSymbol(&bitC, &CState1, *--ip);
 
        if (sizeof(bitC.bitContainer)*8 > FSE_MAX_TABLELOG*4+7 ) {  /* this test must be static */
            FSE_encodeSymbol(&bitC, &CState2, *--ip);
            FSE_encodeSymbol(&bitC, &CState1, *--ip);
        }
 
        FSE_FLUSHBITS(&bitC);
    }
 
    FSE_flushCState(&bitC, &CState2);
    FSE_flushCState(&bitC, &CState1);
    return BIT_closeCStream(&bitC);
}

Referenced by FSE_compress_usingCTable().

FSE_compress_wksp()

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
	)

Definition at line 635 of file fse_compress.c.

{
    BYTE* const ostart = (BYTE*) dst;
    BYTE* op = ostart;
    BYTE* const oend = ostart + dstSize;
 
    unsigned count[FSE_MAX_SYMBOL_VALUE+1];
    S16   norm[FSE_MAX_SYMBOL_VALUE+1];
    FSE_CTable* CTable = (FSE_CTable*)workSpace;
    size_t const CTableSize = FSE_CTABLE_SIZE_U32(tableLog, maxSymbolValue);
    void* scratchBuffer = (void*)(CTable + CTableSize);
    size_t const scratchBufferSize = wkspSize - (CTableSize * sizeof(FSE_CTable));
 
    /* init conditions */
    if (wkspSize < FSE_WKSP_SIZE_U32(tableLog, maxSymbolValue)) return ERROR(tableLog_tooLarge);
    if (srcSize <= 1) return 0;  /* Not compressible */
    if (!maxSymbolValue) maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
    if (!tableLog) tableLog = FSE_DEFAULT_TABLELOG;
 
    /* Scan input and build symbol stats */
    {   CHECK_V_F(maxCount, HIST_count_wksp(count, &maxSymbolValue, src, srcSize, scratchBuffer, scratchBufferSize) );
        if (maxCount == srcSize) return 1;   /* only a single symbol in src : rle */
        if (maxCount == 1) return 0;         /* each symbol present maximum once => not compressible */
        if (maxCount < (srcSize >> 7)) return 0;   /* Heuristic : not compressible enough */
    }
 
    tableLog = FSE_optimalTableLog(tableLog, srcSize, maxSymbolValue);
    CHECK_F( FSE_normalizeCount(norm, tableLog, count, srcSize, maxSymbolValue) );
 
    /* Write table description header */
    {   CHECK_V_F(nc_err, FSE_writeNCount(op, oend-op, norm, maxSymbolValue, tableLog) );
        op += nc_err;
    }
 
    /* Compress */
    CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, scratchBufferSize) );
    {   CHECK_V_F(cSize, FSE_compress_usingCTable(op, oend - op, src, srcSize, CTable) );
        if (cSize == 0) return 0;   /* not enough space for compressed data */
        op += cSize;
    }
 
    /* check compressibility */
    if ( (size_t)(op-ostart) >= srcSize-1 ) return 0;
 
    return op-ostart;
}

Referenced by FSE_compress2().

FSE_compressBound()

size_t FSE_compressBound

(

size_t

size

)

Definition at line 629 of file fse_compress.c.

{ return FSE_COMPRESSBOUND(size); }

FSE_createCTable()

FSE_CTable * FSE_createCTable	(	unsigned	maxSymbolValue,
		unsigned	tableLog
	)

Definition at line 308 of file fse_compress.c.

{
    size_t size;
    if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
    size = FSE_CTABLE_SIZE_U32 (tableLog, maxSymbolValue) * sizeof(U32);
    return (FSE_CTable*)ExAllocatePoolWithTag(PagedPool, size, FSEC_ALLOC_TAG);
}

FSE_freeCTable()

void FSE_freeCTable

(

FSE_CTable *

ct

)

Definition at line 316 of file fse_compress.c.

{ ExFreePool(ct); }

FSE_minTableLog()

static unsigned FSE_minTableLog ( size_t  srcSize, unsigned  maxSymbolValue  )

static

Definition at line 319 of file fse_compress.c.

{
    U32 minBitsSrc = BIT_highbit32((U32)(srcSize)) + 1;
    U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2;
    U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
    assert(srcSize > 1); /* Not supported, RLE should be used instead */
    return minBits;
}

Referenced by FSE_normalizeCount(), and FSE_optimalTableLog_internal().

FSE_NCountWriteBound()

size_t FSE_NCountWriteBound	(	unsigned	maxSymbolValue,
		unsigned	tableLog
	)

FSE_NCountWriteBound(): Provides the maximum possible size of an FSE normalized table, given 'maxSymbolValue' and 'tableLog'. Typically useful for allocation purpose.

Definition at line 189 of file fse_compress.c.

{
    size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog) >> 3) + 3;
    return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND;  /* maxSymbolValue==0 ? use default */
}

Referenced by FSE_writeNCount().

FSE_normalizeCount()

size_t FSE_normalizeCount	(	short *	normalizedCounter,
		unsigned	tableLog,
		const unsigned *	count,
		size_t	srcSize,
		unsigned	maxSymbolValue
	)

FSE_normalizeCount(): normalize counts so that sum(count[]) == Power_of_2 (2^tableLog) 'normalizedCounter' is a table of short, of minimum size (maxSymbolValue+1).

Returns

: tableLog, or an errorCode, which can be tested using FSE_isError()

Definition at line 438 of file fse_compress.c.

{
    /* Sanity checks */
    if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
    if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC);   /* Unsupported size */
    if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);   /* Unsupported size */
    if (tableLog < FSE_minTableLog(total, maxSymbolValue)) return ERROR(GENERIC);   /* Too small tableLog, compression potentially impossible */
 
    {   static U32 const rtbTable[] = {     0, 473195, 504333, 520860, 550000, 700000, 750000, 830000 };
        U64 const scale = 62 - tableLog;
        U64 const step = ((U64)1<<62) / total;   /* <== here, one division ! */
        U64 const vStep = 1ULL<<(scale-20);
        int stillToDistribute = 1<<tableLog;
        unsigned s;
        unsigned largest=0;
        short largestP=0;
        U32 lowThreshold = (U32)(total >> tableLog);
 
        for (s=0; s<=maxSymbolValue; s++) {
            if (count[s] == total) return 0;   /* rle special case */
            if (count[s] == 0) { normalizedCounter[s]=0; continue; }
            if (count[s] <= lowThreshold) {
                normalizedCounter[s] = -1;
                stillToDistribute--;
            } else {
                short proba = (short)((count[s]*step) >> scale);
                if (proba<8) {
                    U64 restToBeat = vStep * rtbTable[proba];
                    proba += (count[s]*step) - ((U64)proba<<scale) > restToBeat;
                }
                if (proba > largestP) { largestP=proba; largest=s; }
                normalizedCounter[s] = proba;
                stillToDistribute -= proba;
        }   }
        if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
            /* corner case, need another normalization method */
            size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue);
            if (FSE_isError(errorCode)) return errorCode;
        }
        else normalizedCounter[largest] += (short)stillToDistribute;
    }
 
#if 0
    {   /* Print Table (debug) */
        U32 s;
        U32 nTotal = 0;
        for (s=0; s<=maxSymbolValue; s++)
            RAWLOG(2, "%3i: %4i \n", s, normalizedCounter[s]);
        for (s=0; s<=maxSymbolValue; s++)
            nTotal += abs(normalizedCounter[s]);
        if (nTotal != (1U<<tableLog))
            RAWLOG(2, "Warning !!! Total == %u != %u !!!", nTotal, 1U<<tableLog);
        getchar();
    }
#endif
 
    return tableLog;
}

Referenced by FSE_compress_wksp(), HUF_compressWeights(), ZSTD_buildCTable(), and ZSTD_NCountCost().

FSE_normalizeM2()

static size_t FSE_normalizeM2 ( short *  norm, U32  tableLog, const unsigned *  count, size_t  total, U32  maxSymbolValue  )

static

Definition at line 351 of file fse_compress.c.

{
    short const NOT_YET_ASSIGNED = -2;
    U32 s;
    U32 distributed = 0;
    U32 ToDistribute;
 
    /* Init */
    U32 const lowThreshold = (U32)(total >> tableLog);
    U32 lowOne = (U32)((total * 3) >> (tableLog + 1));
 
    for (s=0; s<=maxSymbolValue; s++) {
        if (count[s] == 0) {
            norm[s]=0;
            continue;
        }
        if (count[s] <= lowThreshold) {
            norm[s] = -1;
            distributed++;
            total -= count[s];
            continue;
        }
        if (count[s] <= lowOne) {
            norm[s] = 1;
            distributed++;
            total -= count[s];
            continue;
        }
 
        norm[s]=NOT_YET_ASSIGNED;
    }
    ToDistribute = (1 << tableLog) - distributed;
 
    if (ToDistribute == 0)
        return 0;
 
    if ((total / ToDistribute) > lowOne) {
        /* risk of rounding to zero */
        lowOne = (U32)((total * 3) / (ToDistribute * 2));
        for (s=0; s<=maxSymbolValue; s++) {
            if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) {
                norm[s] = 1;
                distributed++;
                total -= count[s];
                continue;
        }   }
        ToDistribute = (1 << tableLog) - distributed;
    }
 
    if (distributed == maxSymbolValue+1) {
        /* all values are pretty poor;
           probably incompressible data (should have already been detected);
           find max, then give all remaining points to max */
        U32 maxV = 0, maxC = 0;
        for (s=0; s<=maxSymbolValue; s++)
            if (count[s] > maxC) { maxV=s; maxC=count[s]; }
        norm[maxV] += (short)ToDistribute;
        return 0;
    }
 
    if (total == 0) {
        /* all of the symbols were low enough for the lowOne or lowThreshold */
        for (s=0; ToDistribute > 0; s = (s+1)%(maxSymbolValue+1))
            if (norm[s] > 0) { ToDistribute--; norm[s]++; }
        return 0;
    }
 
    {   U64 const vStepLog = 62 - tableLog;
        U64 const mid = (1ULL << (vStepLog-1)) - 1;
        U64 const rStep = ((((U64)1<<vStepLog) * ToDistribute) + mid) / total;   /* scale on remaining */
        U64 tmpTotal = mid;
        for (s=0; s<=maxSymbolValue; s++) {
            if (norm[s]==NOT_YET_ASSIGNED) {
                U64 const end = tmpTotal + (count[s] * rStep);
                U32 const sStart = (U32)(tmpTotal >> vStepLog);
                U32 const sEnd = (U32)(end >> vStepLog);
                U32 const weight = sEnd - sStart;
                if (weight < 1)
                    return ERROR(GENERIC);
                norm[s] = (short)weight;
                tmpTotal = end;
    }   }   }
 
    return 0;
}

Referenced by FSE_normalizeCount().

FSE_optimalTableLog()

unsigned FSE_optimalTableLog	(	unsigned	maxTableLog,
		size_t	srcSize,
		unsigned	maxSymbolValue
	)

FSE_compress() does the following:

1. count symbol occurrence from source[] into table count[] (see hist.h)
2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog)
3. save normalized counters to memory buffer using writeNCount()
4. build encoding table 'CTable' from normalized counters
5. encode the data stream using encoding table 'CTable'

FSE_decompress() does the following:

1. read normalized counters with readNCount()
2. build decoding table 'DTable' from normalized counters
3. decode the data stream using decoding table 'DTable'

The following API allows targeting specific sub-functions for advanced tasks. For example, it's possible to compress several blocks using the same 'CTable', or to save and provide normalized distribution using external method.

FSE_optimalTableLog(): dynamically downsize 'tableLog' when conditions are met. It saves CPU time, by using smaller tables, while preserving or even improving compression ratio.

Returns

: recommended tableLog (necessarily <= 'maxTableLog')

Definition at line 342 of file fse_compress.c.

{
    return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
}

Referenced by FSE_compress_wksp(), HUF_compressWeights(), ZSTD_buildCTable(), and ZSTD_NCountCost().

FSE_optimalTableLog_internal()

unsigned FSE_optimalTableLog_internal	(	unsigned	maxTableLog,
		size_t	srcSize,
		unsigned	maxSymbolValue,
		unsigned	minus
	)

Definition at line 328 of file fse_compress.c.

{
    U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus;
    U32 tableLog = maxTableLog;
    U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
    assert(srcSize > 1); /* Not supported, RLE should be used instead */
    if (tableLog==0) tableLog = FSE_DEFAULT_TABLELOG;
    if (maxBitsSrc < tableLog) tableLog = maxBitsSrc;   /* Accuracy can be reduced */
    if (minBits > tableLog) tableLog = minBits;   /* Need a minimum to safely represent all symbol values */
    if (tableLog < FSE_MIN_TABLELOG) tableLog = FSE_MIN_TABLELOG;
    if (tableLog > FSE_MAX_TABLELOG) tableLog = FSE_MAX_TABLELOG;
    return tableLog;
}

Referenced by FSE_optimalTableLog(), and HUF_optimalTableLog().

FSE_writeNCount()

size_t FSE_writeNCount	(	void *	buffer,
		size_t	bufferSize,
		const short *	normalizedCounter,
		unsigned	maxSymbolValue,
		unsigned	tableLog
	)

FSE_writeNCount(): Compactly save 'normalizedCounter' into 'buffer'.

Returns

: size of the compressed table, or an errorCode, which can be tested using FSE_isError().

Definition at line 291 of file fse_compress.c.

{
    if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);   /* Unsupported */
    if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC);   /* Unsupported */
 
    if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
        return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0);
 
    return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1 /* write in buffer is safe */);
}

Referenced by FSE_compress_wksp(), HUF_compressWeights(), ZSTD_buildCTable(), and ZSTD_NCountCost().

FSE_writeNCount_generic()

static size_t FSE_writeNCount_generic ( void *  header, size_t  headerBufferSize, const short *  normalizedCounter, unsigned  maxSymbolValue, unsigned  tableLog, unsigned  writeIsSafe  )

static

Definition at line 196 of file fse_compress.c.

{
    BYTE* const ostart = (BYTE*) header;
    BYTE* out = ostart;
    BYTE* const oend = ostart + headerBufferSize;
    int nbBits;
    const int tableSize = 1 << tableLog;
    int remaining;
    int threshold;
    U32 bitStream = 0;
    int bitCount = 0;
    unsigned symbol = 0;
    unsigned const alphabetSize = maxSymbolValue + 1;
    int previousIs0 = 0;
 
    /* Table Size */
    bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount;
    bitCount  += 4;
 
    /* Init */
    remaining = tableSize+1;   /* +1 for extra accuracy */
    threshold = tableSize;
    nbBits = tableLog+1;
 
    while ((symbol < alphabetSize) && (remaining>1)) {  /* stops at 1 */
        if (previousIs0) {
            unsigned start = symbol;
            while ((symbol < alphabetSize) && !normalizedCounter[symbol]) symbol++;
            if (symbol == alphabetSize) break;   /* incorrect distribution */
            while (symbol >= start+24) {
                start+=24;
                bitStream += 0xFFFFU << bitCount;
                if ((!writeIsSafe) && (out > oend-2))
                    return ERROR(dstSize_tooSmall);   /* Buffer overflow */
                out[0] = (BYTE) bitStream;
                out[1] = (BYTE)(bitStream>>8);
                out+=2;
                bitStream>>=16;
            }
            while (symbol >= start+3) {
                start+=3;
                bitStream += 3 << bitCount;
                bitCount += 2;
            }
            bitStream += (symbol-start) << bitCount;
            bitCount += 2;
            if (bitCount>16) {
                if ((!writeIsSafe) && (out > oend - 2))
                    return ERROR(dstSize_tooSmall);   /* Buffer overflow */
                out[0] = (BYTE)bitStream;
                out[1] = (BYTE)(bitStream>>8);
                out += 2;
                bitStream >>= 16;
                bitCount -= 16;
        }   }
        {   int count = normalizedCounter[symbol++];
            int const max = (2*threshold-1) - remaining;
            remaining -= count < 0 ? -count : count;
            count++;   /* +1 for extra accuracy */
            if (count>=threshold)
                count += max;   /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */
            bitStream += count << bitCount;
            bitCount  += nbBits;
            bitCount  -= (count<max);
            previousIs0  = (count==1);
            if (remaining<1) return ERROR(GENERIC);
            while (remaining<threshold) { nbBits--; threshold>>=1; }
        }
        if (bitCount>16) {
            if ((!writeIsSafe) && (out > oend - 2))
                return ERROR(dstSize_tooSmall);   /* Buffer overflow */
            out[0] = (BYTE)bitStream;
            out[1] = (BYTE)(bitStream>>8);
            out += 2;
            bitStream >>= 16;
            bitCount -= 16;
    }   }
 
    if (remaining != 1)
        return ERROR(GENERIC);  /* incorrect normalized distribution */
    assert(symbol <= alphabetSize);
 
    /* flush remaining bitStream */
    if ((!writeIsSafe) && (out > oend - 2))
        return ERROR(dstSize_tooSmall);   /* Buffer overflow */
    out[0] = (BYTE)bitStream;
    out[1] = (BYTE)(bitStream>>8);
    out+= (bitCount+7) /8;
 
    return (out-ostart);
}

Referenced by FSE_writeNCount().