GLAST / LAT > DAQ and FSW > FSW > Doxygen Index> LDT / dev > encdec / rhel6-32
#include <LDT/BA.h>
#include <LDT/HUFF.h>
#include <LDT/_HUFF.dox>
#include <LDT/BFU.h>
#include <PBI/Alias.h>
#include <PBI/FFS.ih>
#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
| |
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. |
CVS $Id
The main documentation for this implementation of the huffman encoding and decoding is kept in _HUFF.dox
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.
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 |
References calc_len(), and dprintf.
Referenced by HUFF_buildDense().
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.
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 |
References calc_len(), and dprintf.
Referenced by build(), HUFF_build(), and HUFF_buildSparse().
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.
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
|
assign | Callback routine to assign the code lengths |
References assign_sparse(), dprintf, and heap_construct().
Referenced by HUFF_build(), HUFF_buildDense(), and HUFF_buildSparse().
static __inline unsigned int calc_len | ( | const unsigned int * | parents, | |
int | k | |||
) | [static] |
Calculates the length for the tree starting at parent.
parents | The tree to traverse | |
k | The starting position in the tree |
Referenced by assign_dense(), and assign_sparse().
__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.
References _HUFF_dlist::code, and _HUFF_dlist::list.
Referenced by HUFF_decode(), HUFF_decompressBytes(), HUFF_decompressLongs(), and HUFF_decompressShorts().
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.
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
| |
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. |
References dprintf, and heap_down().
Referenced by build().
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.
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);
References dprintf.
Referenced by heap_construct().
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.
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. |
References dprintf.
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.
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. |
// // 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);
References assign_sparse(), and build().
Referenced by pack_delta_huff().
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.
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. |
References assign_dense(), and build().
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.
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. |
References assign_sparse(), and build().
Referenced by HDE_encodeSS(), and HDE_tableConstructL().
void HUFF_codesPrint | ( | const HUFF_code * | codes, | |
int | ncodes | |||
) |
Prints an ASCII display of the specified codes.
codes | The array of codes to print | |
ncodes | The number of codes to print |
Referenced by HDE_encodeSS(), HDE_tableConstructL(), and pack_delta_huff().
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
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.
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.
dtable | The decoding table | |
src | The source buffer | |
boff | The bit offset into the source buffer |
References _bfu_constructW, _bfu_extractL, decode(), _HUFF_dtable::offsets, _HUFF_dtable::present, and _HUFF_dtable::sym_nmax.
Referenced by unpack_syms().
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.
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 |
References _bfu_construct, _bfu_extractL, _BFU::cur, decode(), dprintf, _HUFF_dtable::offsets, _HUFF_dtable::present, and _HUFF_dtable::sym_nmax.
Referenced by unpack_code_lensN().
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.
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 |
References _bfu_construct, _bfu_extractL, _BFU::cur, decode(), dprintf, _HUFF_dtable::offsets, _HUFF_dtable::present, and _HUFF_dtable::sym_nmax.
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.
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 |
References _bfu_construct, _bfu_extractL, _BFU::cur, decode(), dprintf, _HUFF_dtable::offsets, _HUFF_dtable::present, and _HUFF_dtable::sym_nmax.
Referenced by unpack_syms().
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.
dtable | The decoding table to be built | |
biase | The biase value |
References _HUFF_dlist::code, _HUFF_dtable::list, _HUFF_dlist::list, _HUFF_dtable::offsets, _HUFF_dtable::present, and _HUFF_dtable::sym_nmin.
Referenced by HDD_decodeS(), and HDD_tableDecode().
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.
dtable | The decoding table to be built | |
sym_lens | An array representing the lengths of each symbol | |
nsym_lens | The number of symbol lengths |
References _HUFF_dlist::code, dprintf, _HUFF_dtable::list, _HUFF_dlist::list, _HUFF_dtable::offsets, _HUFF_dtable::present, _HUFF_dtable::sym_cnt, _HUFF_dtable::sym_nmax, and _HUFF_dtable::sym_nmin.
Referenced by HDD_decodeS(), HDD_tableDecode(), and unpack_code_lensN().
void HUFF_dtablePrint | ( | const HUFF_dtable * | dtable | ) |
Provides an ASCII display of the decoding table. This is usually for debugging or diagnostic purposes.
dtable | The decoding table to display |
References _HUFF_dlist::code, _HUFF_dtable::list, _HUFF_dlist::list, ndigits_compute(), _HUFF_dtable::offsets, _HUFF_dtable::present, _HUFF_dtable::sym_cnt, _HUFF_dtable::sym_nmax, and _HUFF_dtable::sym_nmin.
Referenced by HDD_decodeS(), HDD_tableDecode(), and unpack_code_lensN().
int HUFF_dtableSizeof | ( | int | nsymbols | ) |
Returns the size, in bytes, of the decoding table needed for the specified number of symbols.
nsymbols | The number of symbols |
Referenced by HDD_construct(), HDD_sizeof(), and unpack_code_lensN().
int HUFF_size | ( | const HUFF_code * | codes, | |
const unsigned int * | freqs, | |||
int | count | |||
) |
Computes the size, in bits, of the specified encode freqs.
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.
codes | The code table to use | |
freq | The frequency table. |
If valid array is specified as NULL, then only the non-zero elements of freq are considered valid.
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
|
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.
codes | The code table to use | |
freq | The frequency table. |
If valid array is specified as NULL, then only the non-zero elements of freq are considered valid.
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
|
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.
== | 0, No, not a member | |
!= | 0, Yes, is a member |
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.
value | The target value |
Referenced by HUFF_dtablePrint().