GLAST/LAT > DAQ and FSW > FSW > Doxygen Index > LDT / V0-3-2
Constituent: encdec     Tag: mv2304
#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>
Include dependency graph for HUFF.c:
Data Structures | |
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 | 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 _HUFF_dinfo_bf | HUFF_dinfo_bf |
typedef _HUFF_dinfo | HUFF_dinfo |
typedef _HUFF_dlist | HUFF_dlist |
Typedef for struct _HUFF_dlist. | |
typedef _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
|
Assigns the codes to a dense code array.
|
|
Assign the codes to a sparse code array.
|
|
Constructs the Huffman codes for the specified frequency distribution.
|
|
Calculates the length for the tree starting at parent.
|
|
Decodes one symbol from the input bit string.
|
|
Constructs the heap used to maintain the sorted array of frequency counts.
|
|
Local implementation to push a new count, indexed by k, on to 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); |
|
Convenience routine to compress a byte stream.
|
|
Builds the code table directly from the specified frequency array.
// // 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); |
|
Builds a dense list, that is the resulting code list is indexed in a space that is dense in the valid element numbering scheme.
|
|
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.
|
|
Prints an ASCII display of the specified codes.
|
|
Prints an ASCII display of the specified codes. The codes are assumed to be
|
|
Prints an ASCII display of the specified codes. The valid arrays contains the list of indices that will be printed.
|
|
Decodes one symbol from the input bit source.
|
|
Convenience routine to decode a bit stream using the specified table into a byte array.
|
|
Convenience routine to decode a bit stream using the specified table into a unsigned short array.
|
|
Convenience routine to decode a bit stream using the specified table into a unsigned short array.
|
|
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.
|
|
Construct a decoding table based on the lengths of symbols This constructs the huffman codes in the canonical form.
|
|
Provides an ASCII display of the decoding table. This is usually for debugging or diagnostic purposes.
|
|
Returns the size, in bytes, of the decoding table needed for the specified number of symbols.
|
|
Computes the size, in bits, of the specified encode freqs.
|
|
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.
If valid array is specified as NULL, then only the non-zero elements of freq are considered valid.
|
|
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.
If valid array is specified as NULL, then only the non-zero elements of freq are considered valid.
|
|
Determines whether the index idx is a member of the valid set of indices.
|
|
Calculate the number of decimal digits in value.
|