GLAST/LAT > DAQ and FSW > FSW > Doxygen Index > LDT / V0-3-1

Constituent: encdec     Tag: mv2304

Interface   Data Structures   File List   Data Fields   Globals  
g » glast » flight » SVC » source » LDT » V0-3-1 » LDT

HUFF.h File Reference

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

#include "LDT/BA.h"
#include "PBI/Endianness.h"

Include dependency graph for HUFF.h:

This graph shows which files directly or indirectly include this file:


Data Structures

struct  _HUFF_code
 Structure to contain the Huffman code, both the bit pattern and its length. More...
struct  _HUFF_symbol_bf
 The information associate with a decoded symbol. More...
union  _HUFF_symbol

Defines

#define HUFF_N_WA(_cnt)   (HUFF_N_HEAP(_cnt) + HUFF_N_PARENTS(_cnt))
 Gives the number of elements needed by the temporary wa array based of the number of elements in the frequency table.
#define HUFF_ENCODE(_out, _buffer, _togo, _codes, _sym)
 Macro to encode one symbol using the specified code table.

Typedefs

typedef _HUFF_dtable HUFF_dtable
 Typedef for struct _HUFF_dtable.
typedef _HUFF_code HUFF_code
 Typedef for struct _HUFF_code.
typedef _HUFF_symbol_bf HUFF_symbol_bf
typedef _HUFF_symbol HUFF_symbol

Functions

int HUFF_build (HUFF_code *codes, const unsigned int *freqs, int count, 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.
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.
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 nsymbols)
 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.
void HUFF_dtablePrint (const HUFF_dtable *dtable)
 Provides an ASCII display of the decoding table. This is usually for debugging or diagnostic purposes.
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.
void HUFF_codesPrint (const HUFF_code *codes, int ncodes)
 Prints an ASCII display of the specified codes.

Detailed Description

Huffman Encode/Decode, interface file.

Author:
JJRussell - russell@slac.stanford.edu
CVS $Id

Warning:
In their current state, these routines are not fit for Flight use. They can be used to determine compression factors and, in general, study the properties of Huffman encoding/decoding. However, they malloc all over the place and involve recursive calling techniques, neither of is appropriate for Flight code.

Define Documentation

#define HUFF_ENCODE (  _out,
_buffer,
_togo,
_codes,
_sym   ) 
 

Value:

{                                                         \
    HUFF_code   code = _codes[_sym];                      \
    int          len =  code.len;                         \
    unsigned int pat = code.pat;                          \
    BA_WRITE_R(_out, _buffer, _togo, pat, len);           \
}
Macro to encode one symbol using the specified code table.

Parameters:
_out The output buffer
_buffer The temporary 32-bit staging buffer
_togo The number of bits available in the staging buffer
_codes The list of codes
_sym The symbol/index into the list of codes
This would be much nicer as an inline, but 3 values are potentially modified, _out, _buffer and _togo, possibly making it inefficient since one of more of these values would have to be passed by address.

#define HUFF_N_WA (  _cnt   )     (HUFF_N_HEAP(_cnt) + HUFF_N_PARENTS(_cnt))
 

Gives the number of elements needed by the temporary wa array based of the number of elements in the frequency table.

Returns:
The number of elements needed by the temporary wa array
Parameters:
_cnt The number of elements in the frequency table.

Function Documentation

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

__inline 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.

Generated on Mon Nov 20 04:09:49 2006 by  doxygen 1.4.4