Parolin 0.7.9 6796
Console (soon DLLs) to do a tar like job
Loading...
Searching...
No Matches
Data Structures | Macros | Typedefs | Enumerations | Functions
huf_compress.c File Reference
#include "../common/zstd_deps.h"
#include "../common/compiler.h"
#include "../common/bitstream.h"
#include "hist.h"
#include "../common/fse.h"
#include "../common/huf.h"
#include "../common/error_private.h"

Data Structures

struct  HUF_CompressWeightsWksp
 
struct  HUF_WriteCTableWksp
 
struct  nodeElt_s
 
struct  rankPos
 
struct  HUF_buildCTable_wksp_tables
 
struct  HUF_CStream_t
 
struct  HUF_compress_tables_t
 

Macros

#define FSE_STATIC_LINKING_ONLY   /* FSE_optimalTableLog_internal */
 
#define HUF_STATIC_LINKING_ONLY
 
#define HUF_isError   ERR_isError
 
#define HUF_STATIC_ASSERT(c)
 
#define HUF_WORKSPACE_MAX_ALIGNMENT   8
 
#define MAX_FSE_TABLELOG_FOR_HUFF_HEADER   6
 
#define RANK_POSITION_TABLE_SIZE   192
 
#define RANK_POSITION_MAX_COUNT_LOG   32
 
#define RANK_POSITION_LOG_BUCKETS_BEGIN   (RANK_POSITION_TABLE_SIZE - 1) - RANK_POSITION_MAX_COUNT_LOG - 1 /* == 158 */
 
#define RANK_POSITION_DISTINCT_COUNT_CUTOFF   RANK_POSITION_LOG_BUCKETS_BEGIN + BIT_highbit32(RANK_POSITION_LOG_BUCKETS_BEGIN) /* == 166 */
 
#define STARTNODE   (HUF_SYMBOLVALUE_MAX+1)
 
#define HUF_BITS_IN_CONTAINER   (sizeof(size_t) * 8)
 
#define SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE   4096
 
#define SUSPECT_INCOMPRESSIBLE_SAMPLE_RATIO   10 /* Must be >= 2 */
 

Typedefs

typedef struct nodeElt_s nodeElt
 
typedef nodeElt huffNodeTable[HUF_CTABLE_WORKSPACE_SIZE_U32]
 

Enumerations

enum  HUF_nbStreams_e { HUF_singleStream , HUF_fourStreams }
 

Functions

unsigned HUF_optimalTableLog (unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
 
size_t HUF_writeCTable_wksp (void *dst, size_t maxDstSize, const HUF_CElt *CTable, unsigned maxSymbolValue, unsigned huffLog, void *workspace, size_t workspaceSize)
 
size_t HUF_writeCTable (void *dst, size_t maxDstSize, const HUF_CElt *CTable, unsigned maxSymbolValue, unsigned huffLog)
 
size_t HUF_readCTable (HUF_CElt *CTable, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize, unsigned *hasZeroWeights)
 
U32 HUF_getNbBitsFromCTable (HUF_CElt const *CTable, U32 symbolValue)
 
MEM_STATIC int HUF_isSorted (nodeElt huffNode[], U32 const maxSymbolValue1)
 
HINT_INLINE void HUF_insertionSort (nodeElt huffNode[], int const low, int const high)
 
size_t HUF_buildCTable_wksp (HUF_CElt *CTable, const unsigned *count, U32 maxSymbolValue, U32 maxNbBits, void *workSpace, size_t wkspSize)
 
size_t HUF_estimateCompressedSize (const HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
 
int HUF_validateCTable (const HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
 
size_t HUF_compressBound (size_t size)
 
FORCE_INLINE_TEMPLATE void HUF_addBits (HUF_CStream_t *bitC, HUF_CElt elt, int idx, int kFast)
 
FORCE_INLINE_TEMPLATE void HUF_zeroIndex1 (HUF_CStream_t *bitC)
 
FORCE_INLINE_TEMPLATE void HUF_mergeIndex1 (HUF_CStream_t *bitC)
 
FORCE_INLINE_TEMPLATE void HUF_flushBits (HUF_CStream_t *bitC, int kFast)
 
FORCE_INLINE_TEMPLATE void HUF_encodeSymbol (HUF_CStream_t *bitCPtr, U32 symbol, const HUF_CElt *CTable, int idx, int fast)
 
FORCE_INLINE_TEMPLATE void HUF_compress1X_usingCTable_internal_body_loop (HUF_CStream_t *bitC, const BYTE *ip, size_t srcSize, const HUF_CElt *ct, int kUnroll, int kFastFlush, int kLastFast)
 
FORCE_INLINE_TEMPLATE size_t HUF_compress1X_usingCTable_internal_body (void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable)
 
size_t HUF_compress1X_usingCTable (void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable)
 
size_t HUF_compress1X_usingCTable_bmi2 (void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, int bmi2)
 
size_t HUF_compress4X_usingCTable (void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable)
 
size_t HUF_compress4X_usingCTable_bmi2 (void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, int bmi2)
 
size_t HUF_compress1X_wksp (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize)
 
size_t HUF_compress1X_repeat (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize, HUF_CElt *hufTable, HUF_repeat *repeat, int preferRepeat, int bmi2, unsigned suspectUncompressible)
 
size_t HUF_compress4X_wksp (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize)
 
size_t HUF_compress4X_repeat (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize, HUF_CElt *hufTable, HUF_repeat *repeat, int preferRepeat, int bmi2, unsigned suspectUncompressible)
 
size_t HUF_buildCTable (HUF_CElt *tree, const unsigned *count, unsigned maxSymbolValue, unsigned maxNbBits)
 
size_t HUF_compress1X (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog)
 
size_t HUF_compress2 (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog)
 
size_t HUF_compress (void *dst, size_t maxDstSize, const void *src, size_t srcSize)
 

Macro Definition Documentation

◆ FSE_STATIC_LINKING_ONLY

#define FSE_STATIC_LINKING_ONLY   /* FSE_optimalTableLog_internal */

◆ HUF_BITS_IN_CONTAINER

#define HUF_BITS_IN_CONTAINER   (sizeof(size_t) * 8)

HUF_CStream_t: Huffman uses its own BIT_CStream_t implementation. There are three major differences from BIT_CStream_t:

  1. HUF_addBits() takes a HUF_CElt (size_t) which is the pair (nbBits, value) in the format: format:
    • Bits [0, 4) = nbBits
    • Bits [4, 64 - nbBits) = 0
    • Bits [64 - nbBits, 64) = value
  2. The bitContainer is built from the upper bits and right shifted. E.g. to add a new value of N bits you right shift the bitContainer by N, then or in the new value into the N upper bits.
  3. The bitstream has two bit containers. You can add bits to the second container and merge them into the first container.

◆ HUF_isError

#define HUF_isError   ERR_isError

◆ HUF_STATIC_ASSERT

#define HUF_STATIC_ASSERT ( c)
Value:
DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */
c
#define c(i)
Definition sha256.c:43
DEBUG_STATIC_ASSERT
#define DEBUG_STATIC_ASSERT(c)
Definition debug.h:43

◆ HUF_STATIC_LINKING_ONLY

#define HUF_STATIC_LINKING_ONLY

◆ HUF_WORKSPACE_MAX_ALIGNMENT

#define HUF_WORKSPACE_MAX_ALIGNMENT   8

◆ MAX_FSE_TABLELOG_FOR_HUFF_HEADER

#define MAX_FSE_TABLELOG_FOR_HUFF_HEADER   6

◆ RANK_POSITION_DISTINCT_COUNT_CUTOFF

#define RANK_POSITION_DISTINCT_COUNT_CUTOFF   RANK_POSITION_LOG_BUCKETS_BEGIN + BIT_highbit32(RANK_POSITION_LOG_BUCKETS_BEGIN) /* == 166 */

◆ RANK_POSITION_LOG_BUCKETS_BEGIN

#define RANK_POSITION_LOG_BUCKETS_BEGIN   (RANK_POSITION_TABLE_SIZE - 1) - RANK_POSITION_MAX_COUNT_LOG - 1 /* == 158 */

◆ RANK_POSITION_MAX_COUNT_LOG

#define RANK_POSITION_MAX_COUNT_LOG   32

◆ RANK_POSITION_TABLE_SIZE

#define RANK_POSITION_TABLE_SIZE   192

◆ STARTNODE

#define STARTNODE   (HUF_SYMBOLVALUE_MAX+1)

HUF_buildCTable_wksp() : Same as HUF_buildCTable(), but using externally allocated scratch buffer. workSpace must be aligned on 4-bytes boundaries, and be at least as large as sizeof(HUF_buildCTable_wksp_tables).

◆ SUSPECT_INCOMPRESSIBLE_SAMPLE_RATIO

#define SUSPECT_INCOMPRESSIBLE_SAMPLE_RATIO   10 /* Must be >= 2 */

◆ SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE

#define SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE   4096

Typedef Documentation

◆ huffNodeTable

typedef nodeElt huffNodeTable[2 *(HUF_SYMBOLVALUE_MAX+1)]

◆ nodeElt

typedef struct nodeElt_s nodeElt

Enumeration Type Documentation

◆ HUF_nbStreams_e

enum HUF_nbStreams_e
Enumerator
HUF_singleStream 
HUF_fourStreams 

Function Documentation

◆ HUF_addBits()

FORCE_INLINE_TEMPLATE void HUF_addBits ( HUF_CStream_t * bitC,
HUF_CElt elt,
int idx,
int kFast )

HUF_addBits(): Adds the symbol stored in HUF_CElt elt to the bitstream.

Parameters
eltThe element we're adding. This is a (nbBits, value) pair. See the HUF_CStream_t docs for the format.
idxInsert into the bitstream at this idx.
kFastThis is a template parameter. If the bitstream is guaranteed to have at least 4 unused bits after this call it may be 1, otherwise it must be 0. HUF_addBits() is faster when fast is set.

◆ HUF_buildCTable()

size_t HUF_buildCTable ( HUF_CElt * tree,
const unsigned * count,
unsigned maxSymbolValue,
unsigned maxNbBits )

HUF_buildCTable() :

Returns
: maxNbBits Note : count is used before tree is written, so they can safely overlap

◆ HUF_buildCTable_wksp()

size_t HUF_buildCTable_wksp ( HUF_CElt * CTable,
const unsigned * count,
U32 maxSymbolValue,
U32 maxNbBits,
void * workSpace,
size_t wkspSize )

◆ HUF_compress()

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

HUF_compress() : Compress content from buffer 'src', of size 'srcSize', into buffer 'dst'. 'dst' buffer must be already allocated. Compression runs faster if dstCapacity >= HUF_compressBound(srcSize). srcSize must be <= HUF_BLOCKSIZE_MAX == 128 KB.

Returns
: size of compressed data (<= dstCapacity). Special values : if return == 0, srcData is not compressible => Nothing is stored within dst !!! if HUF_isError(return), compression failed (more details using HUF_getErrorName())

◆ HUF_compress1X()

size_t HUF_compress1X ( void * dst,
size_t dstSize,
const void * src,
size_t srcSize,
unsigned maxSymbolValue,
unsigned huffLog )

◆ HUF_compress1X_repeat()

size_t HUF_compress1X_repeat ( void * dst,
size_t dstSize,
const void * src,
size_t srcSize,
unsigned maxSymbolValue,
unsigned huffLog,
void * workSpace,
size_t wkspSize,
HUF_CElt * hufTable,
HUF_repeat * repeat,
int preferRepeat,
int bmi2,
unsigned suspectUncompressible )

◆ HUF_compress1X_usingCTable()

size_t HUF_compress1X_usingCTable ( void * dst,
size_t dstSize,
const void * src,
size_t srcSize,
const HUF_CElt * CTable )

◆ HUF_compress1X_usingCTable_bmi2()

size_t HUF_compress1X_usingCTable_bmi2 ( void * dst,
size_t dstSize,
const void * src,
size_t srcSize,
const HUF_CElt * CTable,
int bmi2 )

◆ HUF_compress1X_usingCTable_internal_body()

FORCE_INLINE_TEMPLATE size_t HUF_compress1X_usingCTable_internal_body ( void * dst,
size_t dstSize,
const void * src,
size_t srcSize,
const HUF_CElt * CTable )

◆ HUF_compress1X_usingCTable_internal_body_loop()

FORCE_INLINE_TEMPLATE void HUF_compress1X_usingCTable_internal_body_loop ( HUF_CStream_t * bitC,
const BYTE * ip,
size_t srcSize,
const HUF_CElt * ct,
int kUnroll,
int kFastFlush,
int kLastFast )

◆ HUF_compress1X_wksp()

size_t HUF_compress1X_wksp ( void * dst,
size_t dstSize,
const void * src,
size_t srcSize,
unsigned maxSymbolValue,
unsigned huffLog,
void * workSpace,
size_t wkspSize )

◆ HUF_compress2()

size_t HUF_compress2 ( void * dst,
size_t dstCapacity,
const void * src,
size_t srcSize,
unsigned maxSymbolValue,
unsigned tableLog )

HUF_compress2() : Same as HUF_compress(), but offers control over maxSymbolValue and tableLog. maxSymbolValue must be <= HUF_SYMBOLVALUE_MAX . tableLog must be <= HUF_TABLELOG_MAX .

◆ HUF_compress4X_repeat()

size_t HUF_compress4X_repeat ( void * dst,
size_t dstSize,
const void * src,
size_t srcSize,
unsigned maxSymbolValue,
unsigned huffLog,
void * workSpace,
size_t wkspSize,
HUF_CElt * hufTable,
HUF_repeat * repeat,
int preferRepeat,
int bmi2,
unsigned suspectUncompressible )

◆ HUF_compress4X_usingCTable()

size_t HUF_compress4X_usingCTable ( void * dst,
size_t dstSize,
const void * src,
size_t srcSize,
const HUF_CElt * CTable )

◆ HUF_compress4X_usingCTable_bmi2()

size_t HUF_compress4X_usingCTable_bmi2 ( void * dst,
size_t dstSize,
const void * src,
size_t srcSize,
const HUF_CElt * CTable,
int bmi2 )

◆ HUF_compress4X_wksp()

size_t HUF_compress4X_wksp ( void * dst,
size_t dstSize,
const void * src,
size_t srcSize,
unsigned maxSymbolValue,
unsigned huffLog,
void * workSpace,
size_t wkspSize )

◆ HUF_compressBound()

size_t HUF_compressBound ( size_t size)

maximum compressed size (worst case)

◆ HUF_encodeSymbol()

FORCE_INLINE_TEMPLATE void HUF_encodeSymbol ( HUF_CStream_t * bitCPtr,
U32 symbol,
const HUF_CElt * CTable,
int idx,
int fast )

◆ HUF_estimateCompressedSize()

size_t HUF_estimateCompressedSize ( const HUF_CElt * CTable,
const unsigned * count,
unsigned maxSymbolValue )

◆ HUF_flushBits()

FORCE_INLINE_TEMPLATE void HUF_flushBits ( HUF_CStream_t * bitC,
int kFast )

HUF_flushBits() : Flushes the bits in the bit container @ index 0.

Postcondition
bitPos will be < 8.
Parameters
kFastIf kFast is set then we must know a-priori that the bit container will not overflow.

◆ HUF_getNbBitsFromCTable()

U32 HUF_getNbBitsFromCTable ( const HUF_CElt * symbolTable,
U32 symbolValue )

HUF_getNbBitsFromCTable() : Read nbBits from CTable symbolTable, for symbol symbolValue presumed <= HUF_SYMBOLVALUE_MAX Note 1 : is not inlined, as HUF_CElt definition is private

◆ HUF_insertionSort()

HINT_INLINE void HUF_insertionSort ( nodeElt huffNode[],
int const low,
int const high )

◆ HUF_isSorted()

MEM_STATIC int HUF_isSorted ( nodeElt huffNode[],
U32 const maxSymbolValue1 )

◆ HUF_mergeIndex1()

FORCE_INLINE_TEMPLATE void HUF_mergeIndex1 ( HUF_CStream_t * bitC)

HUF_mergeIndex1() : Merges the bit container @ index 1 into the bit container @ index 0 and zeros the bit container @ index 1.

◆ HUF_optimalTableLog()

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

◆ HUF_readCTable()

size_t HUF_readCTable ( HUF_CElt * CTable,
unsigned * maxSymbolValuePtr,
const void * src,
size_t srcSize,
unsigned * hasZeroWeights )

HUF_readCTable() : Loading a CTable saved with HUF_writeCTable()

◆ HUF_validateCTable()

int HUF_validateCTable ( const HUF_CElt * CTable,
const unsigned * count,
unsigned maxSymbolValue )

◆ HUF_writeCTable()

size_t HUF_writeCTable ( void * dst,
size_t maxDstSize,
const HUF_CElt * CTable,
unsigned maxSymbolValue,
unsigned huffLog )

HUF_writeCTable() : CTable : Huffman tree to save, using huf representation.

Returns
: size of saved CTable

◆ HUF_writeCTable_wksp()

size_t HUF_writeCTable_wksp ( void * dst,
size_t maxDstSize,
const HUF_CElt * CTable,
unsigned maxSymbolValue,
unsigned huffLog,
void * workspace,
size_t workspaceSize )

◆ HUF_zeroIndex1()

FORCE_INLINE_TEMPLATE void HUF_zeroIndex1 ( HUF_CStream_t * bitC)
Generated by doxygen 1.12.0