---

GLAST / LAT > DAQ and FSW > FSW > Doxygen Index> LDT / V0-5-0 > encdec / sun-gcc

---

         

---

HUFF.c File Reference

Huffman Encode/Decode, implementation file. More...

#include "LDT/BA.h"
#include "LDT/HUFF.h"
#include "LDT/_HUFF.dox"
#include "LDT/BFU.h"
#include "PBI/Alias.h"
#include "ffs.h"
#include "dprintf.h"
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

Classes
struct	_HUFF_dinfo_bf
struct	_HUFF_dinfo
	The information associate with a list member. More...
struct	_HUFF_dlist
	Structure associated with each symbol length. More...
struct	_HUFF_dtable
	Template of a huffman decoding table. More...
Defines
#define	BA_32
#define	title_bar_print()
Typedefs
typedef int(*	assign_rtn )(HUFF_code *codes, const unsigned int *cnts, const unsigned int *parent, const unsigned int *valid, int cnt)
typedef struct _HUFF_dinfo_bf	HUFF_dinfo_bf
typedef union _HUFF_dinfo	HUFF_dinfo
typedef struct _HUFF_dlist	HUFF_dlist
	Typedef for struct _HUFF_dlist.
typedef struct _HUFF_dtable	HUFF_dtable
Functions
static int	heap_construct (const unsigned int **heap, const unsigned int *freq, const unsigned int *valid, int cnt, unsigned int *freq_max)
	Constructs the heap used to maintain the sorted array of frequency counts.
static __inline void	heap_down (const unsigned int **heap, int n, int k)
	Local implementation to push a new count, indexed by k, on to the heap.
static void	make (const unsigned int **heap, const unsigned int *freqs, int n, unsigned int *counts, int k, unsigned int *parent)
static int	build (HUFF_code *codes, const unsigned int *freq, const unsigned int *valid, int nvalid, unsigned int *wa, assign_rtn assign)
	Constructs the Huffman codes for the specified frequency distribution.
static int	assign_dense (HUFF_code *codes, const unsigned int *counts, const unsigned int *parents, const unsigned int *valid, int cnt)
	Assigns the codes to a dense code array.
static int	assign_sparse (HUFF_code *codes, const unsigned int *counts, const unsigned int *parents, const unsigned int *valid, int cnt)
	Assign the codes to a sparse code array.
int	HUFF_build (HUFF_code *codes, const unsigned int *freq, int cnt, unsigned int *wa)
	Builds the code table directly from the specified frequency array.
int	HUFF_buildDense (HUFF_code *codes, const unsigned int *freq, const unsigned int *valid, int nvalid, unsigned int *wa)
	Builds a dense list, that is the resulting code list is indexed in a space that is dense in the valid element numbering scheme.
int	HUFF_buildSparse (HUFF_code *codes, const unsigned int *freq, const unsigned int *valid, int nvalid, unsigned int *wa)
	Builds a sparse code list. That is the resulting code list is indexed in the same manner as the frequency array. Contrast this with HUFF_buildDense, where the resulting code list is indexed in the same manner as the valid array. Note that because the non-valid elements are not filled in, it is the caller's responsibility to avoid accessing these elements.
static __inline unsigned int	calc_len (const unsigned int *parents, int k)
	Calculates the length for the tree starting at parent.
static __inline void	calc_start_patterns (unsigned int *start, const unsigned int *lengths, unsigned int max)
static __inline HUFF_code	assign_code (unsigned int len, unsigned int *start)
int	HUFF_bcompress (void *out, unsigned int boff, void *max, const HUFF_code *codes, const unsigned char *in, int cnt, int *unencoded)
	Convenience routine to compress a byte stream.
int	HUFF_size (const HUFF_code *codes, const unsigned int *freqs, int count)
	Computes the size, in bits, of the specified encode freqs.
int	HUFF_sizeDense (const HUFF_code *codes, const unsigned int *freq, const unsigned int *valid, int nvalid)
	Sizes the given frequency array using the specified code list. the code list is a dense list of the valid members. The valid members are specified either by the non-zero elements in the frequency array or the valid array.
int	HUFF_sizeSparse (const HUFF_code *codes, const unsigned int *freq, const unsigned int *valid, int nvalid)
	Sizes the given frequency array using the specified code list. the code list is a sparse list of the valid members. The valid members are specified either by the non-zero elements in the frequency array or the valid array.
	ALIAS_FNC (unsigned int, HUFF_decompressBytes, HUFF_bdecompress)
int	HUFF_dtableSizeof (int nsymbols)
	Returns the size, in bytes, of the decoding table needed for the specified number of symbols.
void	HUFF_dtableBuild (HUFF_dtable *dtable, const unsigned char *sym_lens, int nsym_lens)
	Construct a decoding table based on the lengths of symbols This constructs the huffman codes in the canonical form.
void	HUFF_dtableBiase (HUFF_dtable *dtable, int biase)
	Biases a previously constructed table by the amount specified. That is, an unbiased symbol value of 0, will be biased to the value specified by biase.
static __inline unsigned int	decode (unsigned int present, unsigned int max, const HUFF_dlist *offsets, unsigned int bs)
	Decodes one symbol from the input bit string.
unsigned int	HUFF_decode (const HUFF_dtable *dtable, const unsigned int *src, unsigned int boff)
	Decodes one symbol from the input bit source.
int	HUFF_decompressBytes (unsigned char *dst, int cnt, const void *src, unsigned int boff, const HUFF_dtable *dtable)
	Convenience routine to decode a bit stream using the specified table into a byte array.
int	HUFF_decompressShorts (unsigned short int *dst, int cnt, const void *src, unsigned int boff, const HUFF_dtable *dtable)
	Convenience routine to decode a bit stream using the specified table into a unsigned short array.
int	HUFF_decompressLongs (unsigned int *dst, int cnt, const void *src, unsigned int boff, const HUFF_dtable *dtable)
	Convenience routine to decode a bit stream using the specified table into a unsigned short array.
static __inline int	is_valid (int idx, const unsigned int *valid, int nvalid)
	Determines whether the index idx is a member of the valid set of indices.
void	HUFF_codesPrint (const HUFF_code *codes, int ncodes)
	Prints an ASCII display of the specified codes.
void	HUFF_codesPrintDense (const HUFF_code *codes, const unsigned int *valid, int nvalid)
	Prints an ASCII display of the specified codes. The codes are assumed to be densely packed in the codes array, in the same order as the valid array and that there are nvalid codes.
void	HUFF_codesPrintSparse (const HUFF_code *codes, const unsigned int *valid, int nvalid)
	Prints an ASCII display of the specified codes. The valid arrays contains the list of indices that will be printed.
static __inline int	ndigits_compute (unsigned int value)
	Calculate the number of decimal digits in value.
void	HUFF_dtablePrint (const HUFF_dtable *dtable)
	Provides an ASCII display of the decoding table. This is usually for debugging or diagnostic purposes.

---

Detailed Description

Huffman Encode/Decode, implementation file.

Author:

JJRussell - russell@slac.stanford.edu

CVS $Id

The main documentation for this implementation of the huffman encoding and decoding is kept in _HUFF.dox

---

Function Documentation

static int assign_dense	(	HUFF_code *	codes,
		const unsigned int *	counts,
		const unsigned int *	parents,
		const unsigned int *	valid,
		int	cnt
	)			[static]

Assigns the codes to a dense code array.

Returns:

The number of elements populated in the code array.

Parameters:

	codes	The code array to be populated
	counts	The sparse array of counts
	parents	The parent array
	valid	The indices of the valid elements
	cnt	The number of elements in the counts array

static int assign_sparse	(	HUFF_code *	codes,
		const unsigned int *	counts,
		const unsigned int *	parents,
		const unsigned int *	valid,
		int	cnt
	)			[static]

Assign the codes to a sparse code array.

Returns:

The number of elements populated in the code array.

Parameters:

	codes	The code array to be populated
	counts	The sparse array of counts
	parents	The parent array
	valid	If non-zero, the indices of the valid members
	cnt	The number of elements in the counts array

static int build	(	HUFF_code *	codes,
		const unsigned int *	freqs,
		const unsigned int *	valid,
		int	nvalid,
		unsigned int *	wa,
		assign_rtn	assign
	)			[static]

Constructs the Huffman codes for the specified frequency distribution.

Returns:

The number of code elements used in the code array.

Parameters:

	codes	The code table to be populated. The elements acutally populated by the code building routine.
	freqs	The frequency table.
	valid	An array of nvalid elements, giving the indices of the valid elements in the frequency array. This may be specified as NULL, in which case, nvalid gives the number of elements in the frequency table.
	nvalid	The number of entries in the valid table. If valid is specified as NULL, then this value must be the total number elements in the freq array.
	wa	A temporary work area of size with at least HUFF_N_WA(nvalid) elements available. For documentation and planning purposes, this is 2 * number of valid elements, where the number of valid elements is either nvalid, if valid is specified as non-NULL the number of non-0 entries, if valid is specified as NULL.

To keep your code compile-time safe, please use the macros.

Parameters:

assign

Callback routine to assign the code lengths

static __inline unsigned int calc_len	(	const unsigned int *	parents,
		int	k
	)			[static]

Calculates the length for the tree starting at parent.

Returns:

The length of the tree starting at parent

Parameters:

	parents	The tree to traverse
	k	The starting position in the tree

__inline unsigned int decode	(	unsigned int	present,
		unsigned int	max,
		const HUFF_dlist *	offsets,
		unsigned int	bs
	)			[static]

Decodes one symbol from the input bit string.

Returns:

A descriptor of the decoded symbol. This contains the symbol value and the number of bits consumed from the bit string

static int heap_construct	(	const unsigned int **	heap,
		const unsigned int *	freq,
		const unsigned int *	valid,
		int	cnt,
		unsigned int *	freq_max
	)			[static]

Constructs the heap used to maintain the sorted array of frequency counts.

Returns:

The number of valid elements currently on the heap. This is, at most, cnt. The full heap needs one more element to handle the sum of two elements.

Parameters:

	heap	The storage for the indirect heap
	freq	The frequency distribution
	valid	The array of valid entries (optional, may be specified as NULL, in which case only non-zero entries will be treated as valid
	cnt	The count number of If valid is NULL, the number of entries in the the frequency array, freq If valid is non-NULL, the number of entries in the valid array, valid.
	freq_max	Returned as the pointer to the element holding the last frequency entry. This is used to distinguish elements in the heap that are from the original frequency distribution from the derived distribution when combining entries.

static __inline void heap_down	(	const unsigned int **	heap,
		int	n,
		int	k
	)			[static]

Local implementation to push a new count, indexed by k, on to the heap.

Parameters:

	heap	The target heap
	n	The current size of the heap
	k	The index of the count to push on the heap

printf ("heapj0[%3u] = %8u, cnts = %8u\n", j, hj, cj);

printf ("heapj1[%3u] = %8u, cnts = %8u\n", j+1, hj1, cj1);

printf ("heapk0[%3u] = %8u, cnts = %8u DONE\n", j, hj);

int HUFF_bcompress	(	void *	out,
		unsigned int	boff,
		void *	max,
		const HUFF_code *	codes,
		const unsigned char *	in,
		int	cnt,
		int *	unencoded
	)

Convenience routine to compress a byte stream.

Returns:

The number of bits needed to encoded the byte stream. If negative the all the symbols could not be encoded and unencoded should be checked for the count of those symbols not encoded. This number will represent negative the number of bits used to encode the symbols that would fit.

Parameters:

	out	The output buffer
	boff	The current bit offset
	max	The maximum output address (actually 1 byte past it)
	codes	The array of codes
	in	The input buffer of symbols.
	cnt	The number of input symbols.
	unencoded	The number of input symbols left to encode. If successful this will be 0.

int HUFF_build	(	HUFF_code *	codes,
		const unsigned int *	freq,
		int	cnt,
		unsigned int *	wa
	)

Builds the code table directly from the specified frequency array.

Returns:

The number of valid codes. If this number <= 1, no valid code array exist. This happens if the input distribution has only 0 or 1 valid entries. Such a distribution has 0 entropy, and, therefore, needs no bits to encode.

Parameters:

	codes	The code table to be populated.
	freq	The frequency table.
	cnt	The number of entries in the frequency table and, by implication, the code table.
	wa	A temporary work area of size with at least HUFF_N_WA(nvalid) elements available where nvalid is the number of non-zero entries in the frequency table. For documentation and planning purposes, this is 2 * nvalid elements. To keep your code compile-time safe, please use the macro.

Note:

Any 0 count elements in the frequency table will be considered to be invalid. While the code array will be dimensioned from 0 ot cnt, only those elements that correspond to non-zero elements in the frequency table will have valid entries. If the user wishes to fill these code values with 0, he may do so, but only after the codes have been filled in. (This routine reserves the right to use the code array as a temporary working area in order to decrease memory requirements.

If one has an array that gives the valid elements, consider using HUFF_buildSparse. If has a reverse lookup table, (i.e. an array that gives an index that is dense in the valid element number space, consider using HUFF_buildDense. This will produce a table that number in the dense space of only valid elements. Doing this can save a lookup during the encoding process.

Typical usage would be

  //
  // If some elements of the frequency array are 0, the working area
  // may be dimensioned smaller, however, by specifying the maximum 
  // possible, one can do this a compile-time, avoiding run-time 
  // allocations.
  //
  int        freq[30];
  HUFF_code codes[30];
  int          wa[HUFF_N_WA(30)];

  accumulate (freqs, ....);
  dcnt = HUFF_build (codes, freq, 30, wa);

int HUFF_buildDense	(	HUFF_code *	codes,
		const unsigned int *	freq,
		const unsigned int *	valid,
		int	nvalid,
		unsigned int *	wa
	)

Builds a dense list, that is the resulting code list is indexed in a space that is dense in the valid element numbering scheme.

Returns:

The number of elements populated in the code array. If valid

• NULL, then 0 count elements in the frequency array are considered invalid, and the count of non-0 frequency elements is returned.
• non-NULL, then the return value will be nvalid.

Parameters:

	codes	The code table to be populated.
	freq	The frequency table. This area generally contains the number of elements specified by nvalid or the largest index in valid.
	valid	An array of nvalid elements, giving the indices of the valid elements in the frequency array. If this is specified as NULL, although no storage is actually used, this routine's behaviour is as if this array contained indices to only the non-zero elements. Note that, if specified, no element of valid may reference a 0 count element in the frequency table.
	nvalid	The number of entries in the valid table. If valid if specified as NULL, then this is taken to be the number values in the frequency table.
	wa	A temporary work area of size with at least HUFF_N_WA(nvalid) elements available. For documentation and planning purposes, this is 2 * nvalid elements. To keep your code compile-time safe, please use the macros.

See the examples in HUFF_build, which are identical with the exception of adding the valid array argument.

int HUFF_buildSparse	(	HUFF_code *	codes,
		const unsigned int *	freq,
		const unsigned int *	valid,
		int	nvalid,
		unsigned int *	wa
	)

Builds a sparse code list. That is the resulting code list is indexed in the same manner as the frequency array. Contrast this with HUFF_buildDense, where the resulting code list is indexed in the same manner as the valid array. Note that because the non-valid elements are not filled in, it is the caller's responsibility to avoid accessing these elements.

Returns:

The number of valid elements in the code array. If valid is specified as

• NULL, then this is the number of non-zero elements in the frequency array.
• non-NULL, then this is nvalid.

Parameters:

	codes	The code table to be populated. Only those elements indexed by the valid table are populated.
	freq	The frequency table. This array must contains the number of elements specified by nvalid or, if valid is non-NULL, the largest index in valid.
	valid	An array of nvalid elements, giving the indices of the valid elements in the frequency array. If this is specified as NULL, although no storage is actually used, this routine's behaviour is as if this array contained indices to only the non-zero elements.
	nvalid	The number of entries in the valid table. If valid is specified as NULL, then this value must be the total number elements in the freq array.
	wa	A temporary work area of size with at least HUFF_N_WA(nvalid) elements available. For documentation and planning purposes, this is 2 *nvalid elements. To keep your code compile-time safe, please use the macros.

See the examples in HUFF_build, which are identical with the exception of adding the valid array argument

void HUFF_codesPrint	(	const HUFF_code *	codes,
		int	ncodes
	)

Prints an ASCII display of the specified codes.

Parameters:

	codes	The array of codes to print
	ncodes	The number of codes to print

void HUFF_codesPrintDense	(	const HUFF_code *	codes,
		const unsigned int *	valid,
		int	nvalid
	)

Prints an ASCII display of the specified codes. The codes are assumed to be

1. densely packed in the codes array,
2. in the same order as the valid array and
3. that there are nvalid codes.

Parameters:

	codes	The array of codes to print
	valid	The array of valid indices
	nvalid	The number of codes to print

void HUFF_codesPrintSparse	(	const HUFF_code *	codes,
		const unsigned int *	valid,
		int	nvalid
	)

Prints an ASCII display of the specified codes. The valid arrays contains the list of indices that will be printed.

Parameters:

	codes	The array of codes to print
	valid	List of valid codes
	nvalid	the nubmer of valid indices

unsigned int HUFF_decode	(	const HUFF_dtable *	dtable,
		const unsigned int *	src,
		unsigned int	boff
	)

Decodes one symbol from the input bit source.

Returns:

A descriptor of the decoded symbol consisting of the value and the number of bits consumed from the bit string

Parameters:

	dtable	The decoding table
	src	The source buffer
	boff	The bit offset into the source buffer

int HUFF_decompressBytes	(	unsigned char *	dst,
		int	cnt,
		const void *	src,
		unsigned int	boff,
		const HUFF_dtable *	dtable
	)

Convenience routine to decode a bit stream using the specified table into a byte array.

Returns:

The number of bits that were decoded

Parameters:

	dst	The destination/output buffer
	cnt	The number of symbols to decode
	src	The encoded source/input buffer
	boff	The bit offset to start at in the input buffer
	dtable	The decoding table

int HUFF_decompressLongs	(	unsigned int *	dst,
		int	cnt,
		const void *	src,
		unsigned int	boff,
		const HUFF_dtable *	dtable
	)

Convenience routine to decode a bit stream using the specified table into a unsigned short array.

Returns:

The number of bits that were decoded

Parameters:

	dst	The destination/output buffer
	cnt	The number of symbols to decode
	src	The encoded source/input buffer
	boff	The bit offset to start at in the input buffer
	dtable	The decoding table

int HUFF_decompressShorts	(	unsigned short int *	dst,
		int	cnt,
		const void *	src,
		unsigned int	boff,
		const HUFF_dtable *	dtable
	)

Convenience routine to decode a bit stream using the specified table into a unsigned short array.

Returns:

The number of bits that were decoded

Parameters:

	dst	The destination/output buffer
	cnt	The number of symbols to decode
	src	The encoded source/input buffer
	boff	The bit offset to start at in the input buffer
	dtable	The decoding table

void HUFF_dtableBiase	(	HUFF_dtable *	dtable,
		int	biase
	)

Biases a previously constructed table by the amount specified. That is, an unbiased symbol value of 0, will be biased to the value specified by biase.

Parameters:

	dtable	The decoding table to be built
	biase	The biase value

It is fairly common that the original symbols where encoded into a space from [0, nsymbols) from an original space [biase, nsymbols+biase). This routine allows the caller to reapply that biase so that the returned symbol value is in the original space, without looping over all the decoded symbols and reapplying the biase.

void HUFF_dtableBuild	(	HUFF_dtable *	dtable,
		const unsigned char *	sym_lens,
		int	nsym_lens
	)

Construct a decoding table based on the lengths of symbols This constructs the huffman codes in the canonical form.

Parameters:

	dtable	The decoding table to be built
	sym_lens	An array representing the lengths of each symbol
	nsym_lens	The number of symbol lengths

void HUFF_dtablePrint

(

const HUFF_dtable *

dtable

)

Provides an ASCII display of the decoding table. This is usually for debugging or diagnostic purposes.

Parameters:

dtable

The decoding table to display

int HUFF_dtableSizeof

(

int

nsymbols

)

Returns the size, in bytes, of the decoding table needed for the specified number of symbols.

Returns:

The size, in bytes, of the decoding table needed for the specified number of symbols

Parameters:

nsymbols

The number of symbols

int HUFF_size	(	const HUFF_code *	codes,
		const unsigned int *	freqs,
		int	count
	)

Computes the size, in bits, of the specified encode freqs.

Returns:

The size in bits.

Parameters:

	codes	The code table, must be count in length
	freqs	The frequency distribution, must be count in length
	count	The number of elements in the frequency distribution and the code table.

int HUFF_sizeDense	(	const HUFF_code *	codes,
		const unsigned int *	freq,
		const unsigned int *	valid,
		int	nvalid
	)

Sizes the given frequency array using the specified code list. the code list is a dense list of the valid members. The valid members are specified either by the non-zero elements in the frequency array or the valid array.

Returns:

The size, in bits, of the encoded distribution

Parameters:

	codes	The code table to use
	freq	The frequency table.

If valid array is non-zero, then this array is indexed by the validity array

If valid array is specified as NULL, then only the non-zero elements of freq are considered valid.

Parameters:

	valid	An array of nvalid elements, giving the indices of the valid elements in the frequency array. This may be specified as NULL, in which case, only the non-zero elements of freq are considered valid and nvalid gives the length, not of the validity array, but of the frequency distribution.
	nvalid	If valid is Non-NULL, then this is the number of entries in the valid array. NULL, then this is the number of elements in the frequency array.

int HUFF_sizeSparse	(	const HUFF_code *	codes,
		const unsigned int *	freq,
		const unsigned int *	valid,
		int	nvalid
	)

Sizes the given frequency array using the specified code list. the code list is a sparse list of the valid members. The valid members are specified either by the non-zero elements in the frequency array or the valid array.

Returns:

The size, in bits, of the encoded distribution

Parameters:

	codes	The code table to use
	freq	The frequency table.

If valid array is non-zero, then this array is indexed by the validity array

If valid array is specified as NULL, then only the non-zero elements of freq are considered valid.

Parameters:

	valid	An array of nvalid elements, giving the indices of the valid elements in the frequency array. This may be specified as NULL, in which case, only the non-zero elements of freq are considered valid and nvalid gives the length, not of the validity array, but of the frequency distribution.
	nvalid	If valid is Non-NULL, then this is the number of entries in the valid array. NULL, then this is the number of elements in the frequency array.

static __inline int is_valid	(	int	idx,
		const unsigned int *	valid,
		int	nvalid
	)			[static]

Determines whether the index idx is a member of the valid set of indices.

Return values:

	==	0, No, not a member
	!=	0, Yes, is a member

Parameters:

	idx	The index being checked
	valid	The array of valid indices
	nvalid	The number of valid indices

static __inline int ndigits_compute

(

unsigned int

value

)

[static]

Calculate the number of decimal digits in value.

Returns:

The number of decimal digits in value

Parameters:

value

The target value

---