fse_decompress.c File Reference

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

Include dependency graph for fse_decompress.c:

Go to the source code of this file.

Macros
#define	FSE_STATIC_LINKING_ONLY
#define	FSE_isError   ERR_isError
#define	FSE_STATIC_ASSERT(c)   DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */
#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	FSED_ALLOC_TAG   0x64455346
#define	FSE_GETSYMBOL(statePtr)   fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)

Typedefs
typedef FSE_DTable	DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]

Functions
FSE_DTable *	FSE_createDTable (unsigned tableLog)
void	FSE_freeDTable (FSE_DTable *dt)
size_t	FSE_buildDTable (FSE_DTable *dt, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
size_t	FSE_buildDTable_rle (FSE_DTable *dt, BYTE symbolValue)
size_t	FSE_buildDTable_raw (FSE_DTable *dt, unsigned nbBits)
FORCE_INLINE_TEMPLATE size_t	FSE_decompress_usingDTable_generic (void *dst, size_t maxDstSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt, const unsigned fast)
size_t	FSE_decompress_usingDTable (void *dst, size_t originalSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt)
size_t	FSE_decompress_wksp (void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize, FSE_DTable *workSpace, unsigned maxLog)
size_t	FSE_decompress (void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize)

Macro Definition Documentation

FSE_CAT

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

Definition at line 55 of file fse_decompress.c.

FSE_FUNCTION_NAME

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

Definition at line 56 of file fse_decompress.c.

FSE_GETSYMBOL

#define FSE_GETSYMBOL

(

statePtr

)

fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)

FSE_isError

#define FSE_isError   ERR_isError

Definition at line 33 of file fse_decompress.c.

FSE_STATIC_ASSERT

#define FSE_STATIC_ASSERT

(

c

)

DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */

Definition at line 34 of file fse_decompress.c.

FSE_STATIC_LINKING_ONLY

#define FSE_STATIC_LINKING_ONLY

Definition at line 23 of file fse_decompress.c.

FSE_TYPE_NAME

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

Definition at line 57 of file fse_decompress.c.

FSED_ALLOC_TAG

#define FSED_ALLOC_TAG   0x64455346

Definition at line 59 of file fse_decompress.c.

Typedef Documentation

DTable_max_t

typedef FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]

Definition at line 279 of file fse_decompress.c.

Function Documentation

FSE_buildDTable()

size_t FSE_buildDTable	(	FSE_DTable *	dt,
		const short *	normalizedCounter,
		unsigned	maxSymbolValue,
		unsigned	tableLog
	)

FSE_buildDTable(): Builds 'dt', which must be already allocated, using FSE_createDTable(). return : 0, or an errorCode, which can be tested using FSE_isError()

Definition at line 73 of file fse_decompress.c.

{
    void* const tdPtr = dt+1;   /* because *dt is unsigned, 32-bits aligned on 32-bits */
    FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr);
    U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
 
    U32 const maxSV1 = maxSymbolValue + 1;
    U32 const tableSize = 1 << tableLog;
    U32 highThreshold = tableSize-1;
 
    /* Sanity Checks */
    if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
    if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
 
    /* Init, lay down lowprob symbols */
    {   FSE_DTableHeader DTableH;
        DTableH.tableLog = (U16)tableLog;
        DTableH.fastMode = 1;
        {   S16 const largeLimit= (S16)(1 << (tableLog-1));
            U32 s;
            for (s=0; s<maxSV1; s++) {
                if (normalizedCounter[s]==-1) {
                    tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
                    symbolNext[s] = 1;
                } else {
                    if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
                    symbolNext[s] = normalizedCounter[s];
        }   }   }
        memcpy(dt, &DTableH, sizeof(DTableH));
    }
 
    /* Spread symbols */
    {   U32 const tableMask = tableSize-1;
        U32 const step = FSE_TABLESTEP(tableSize);
        U32 s, position = 0;
        for (s=0; s<maxSV1; s++) {
            int i;
            for (i=0; i<normalizedCounter[s]; i++) {
                tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
                position = (position + step) & tableMask;
                while (position > highThreshold) position = (position + step) & tableMask;   /* lowprob area */
        }   }
        if (position!=0) return ERROR(GENERIC);   /* position must reach all cells once, otherwise normalizedCounter is incorrect */
    }
 
    /* Build Decoding table */
    {   U32 u;
        for (u=0; u<tableSize; u++) {
            FSE_FUNCTION_TYPE const symbol = (FSE_FUNCTION_TYPE)(tableDecode[u].symbol);
            U32 const nextState = symbolNext[symbol]++;
            tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
            tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
    }   }
 
    return 0;
}

Referenced by FSE_decompress_wksp().

FSE_buildDTable_raw()

size_t FSE_buildDTable_raw	(	FSE_DTable *	dt,
		unsigned	nbBits
	)

Definition at line 154 of file fse_decompress.c.

{
    void* ptr = dt;
    FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
    void* dPtr = dt + 1;
    FSE_decode_t* const dinfo = (FSE_decode_t*)dPtr;
    const unsigned tableSize = 1 << nbBits;
    const unsigned tableMask = tableSize - 1;
    const unsigned maxSV1 = tableMask+1;
    unsigned s;
 
    /* Sanity checks */
    if (nbBits < 1) return ERROR(GENERIC);         /* min size */
 
    /* Build Decoding Table */
    DTableH->tableLog = (U16)nbBits;
    DTableH->fastMode = 1;
    for (s=0; s<maxSV1; s++) {
        dinfo[s].newState = 0;
        dinfo[s].symbol = (BYTE)s;
        dinfo[s].nbBits = (BYTE)nbBits;
    }
 
    return 0;
}

FSE_buildDTable_rle()

size_t FSE_buildDTable_rle	(	FSE_DTable *	dt,
		BYTE	symbolValue
	)

Definition at line 136 of file fse_decompress.c.

{
    void* ptr = dt;
    FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
    void* dPtr = dt + 1;
    FSE_decode_t* const cell = (FSE_decode_t*)dPtr;
 
    DTableH->tableLog = 0;
    DTableH->fastMode = 0;
 
    cell->newState = 0;
    cell->symbol = symbolValue;
    cell->nbBits = 0;
 
    return 0;
}

FSE_createDTable()

FSE_DTable * FSE_createDTable

(

unsigned

tableLog

)

Definition at line 62 of file fse_decompress.c.

{
    if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
    return (FSE_DTable*)ExAllocatePoolWithTag(PagedPool, FSE_DTABLE_SIZE_U32(tableLog) * sizeof (U32), FSED_ALLOC_TAG);
}

FSE_decompress()

size_t FSE_decompress	(	void *	dst,
		size_t	dstCapacity,
		const void *	cSrc,
		size_t	cSrcSize
	)

FSE_decompress(): Decompress FSE data from buffer 'cSrc', of size 'cSrcSize', into already allocated destination buffer 'dst', of size 'dstCapacity'.

Returns

: size of regenerated data (<= maxDstSize), or an error code, which can be tested using FSE_isError() .

Important ** : FSE_decompress() does not decompress non-compressible nor RLE data !!! Why ? : making this distinction requires a header. Header management is intentionally delegated to the user layer, which can better manage special cases.

Definition at line 281 of file fse_decompress.c.

{
    DTable_max_t dt;   /* Static analyzer seems unable to understand this table will be properly initialized later */
    return FSE_decompress_wksp(dst, dstCapacity, cSrc, cSrcSize, dt, FSE_MAX_TABLELOG);
}

FSE_decompress_usingDTable()

size_t FSE_decompress_usingDTable	(	void *	dst,
		size_t	dstCapacity,
		const void *	cSrc,
		size_t	cSrcSize,
		const FSE_DTable *	dt
	)

FSE_decompress_usingDTable(): Decompress compressed source cSrc of size cSrcSize using dt into dst which must be already allocated.

Returns

: size of regenerated data (necessarily <= dstCapacity), or an errorCode, which can be tested using FSE_isError()

Definition at line 243 of file fse_decompress.c.

{
    const void* ptr = dt;
    const FSE_DTableHeader* DTableH = (const FSE_DTableHeader*)ptr;
    const U32 fastMode = DTableH->fastMode;
 
    /* select fast mode (static) */
    if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
    return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
}

Referenced by FSE_decompress_wksp().

FSE_decompress_usingDTable_generic()

FORCE_INLINE_TEMPLATE size_t FSE_decompress_usingDTable_generic	(	void *	dst,
		size_t	maxDstSize,
		const void *	cSrc,
		size_t	cSrcSize,
		const FSE_DTable *	dt,
		const unsigned	fast
	)

Definition at line 180 of file fse_decompress.c.

{
    BYTE* const ostart = (BYTE*) dst;
    BYTE* op = ostart;
    BYTE* const omax = op + maxDstSize;
    BYTE* const olimit = omax-3;
 
    BIT_DStream_t bitD;
    FSE_DState_t state1;
    FSE_DState_t state2;
 
    /* Init */
    CHECK_F(BIT_initDStream(&bitD, cSrc, cSrcSize));
 
    FSE_initDState(&state1, &bitD, dt);
    FSE_initDState(&state2, &bitD, dt);
 
#define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
 
    /* 4 symbols per loop */
    for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) & (op<olimit) ; op+=4) {
        op[0] = FSE_GETSYMBOL(&state1);
 
        if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
            BIT_reloadDStream(&bitD);
 
        op[1] = FSE_GETSYMBOL(&state2);
 
        if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
            { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
 
        op[2] = FSE_GETSYMBOL(&state1);
 
        if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
            BIT_reloadDStream(&bitD);
 
        op[3] = FSE_GETSYMBOL(&state2);
    }
 
    /* tail */
    /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
    while (1) {
        if (op>(omax-2)) return ERROR(dstSize_tooSmall);
        *op++ = FSE_GETSYMBOL(&state1);
        if (BIT_reloadDStream(&bitD)==BIT_DStream_overflow) {
            *op++ = FSE_GETSYMBOL(&state2);
            break;
        }
 
        if (op>(omax-2)) return ERROR(dstSize_tooSmall);
        *op++ = FSE_GETSYMBOL(&state2);
        if (BIT_reloadDStream(&bitD)==BIT_DStream_overflow) {
            *op++ = FSE_GETSYMBOL(&state1);
            break;
    }   }
 
    return op-ostart;
}

Referenced by FSE_decompress_usingDTable().

FSE_decompress_wksp()

size_t FSE_decompress_wksp	(	void *	dst,
		size_t	dstCapacity,
		const void *	cSrc,
		size_t	cSrcSize,
		FSE_DTable *	workSpace,
		unsigned	maxLog
	)

Definition at line 257 of file fse_decompress.c.

{
    const BYTE* const istart = (const BYTE*)cSrc;
    const BYTE* ip = istart;
    short counting[FSE_MAX_SYMBOL_VALUE+1];
    unsigned tableLog;
    unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
 
    /* normal FSE decoding mode */
    size_t const NCountLength = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
    if (FSE_isError(NCountLength)) return NCountLength;
    /* if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); */  /* too small input size; supposed to be already checked in NCountLength, only remaining case : NCountLength==cSrcSize */
    if (tableLog > maxLog) return ERROR(tableLog_tooLarge);
    ip += NCountLength;
    cSrcSize -= NCountLength;
 
    CHECK_F( FSE_buildDTable (workSpace, counting, maxSymbolValue, tableLog) );
 
    return FSE_decompress_usingDTable (dst, dstCapacity, ip, cSrcSize, workSpace);   /* always return, even if it is an error code */
}

Referenced by FSE_decompress(), and HUF_readStats().

FSE_freeDTable()

void FSE_freeDTable

(

FSE_DTable *

dt

)

Definition at line 68 of file fse_decompress.c.

{
    ExFreePool(dt);
}