GLAST/LAT > DAQ and FSW > FSW > Doxygen Index > LDT / V0-4-0

Constituent: encdec Tag: rad750

Interface Data Structures File List Data Fields Globals

g » glast » flight » SVC » source » LDT » V0-4-0 » src

HDE.c File Reference

Implementation of the routines to encodes a distribution of symbols using a Huffman encoding technique. Routines are available to encode both the distribution itself and the resulting Huffman table. More...

#include "LDT/HDE.h"
#include "LDT/HUFF.h"
#include "LDT/BFP.h"
#include "LDT/BA.h"
#include "ffs.h"
#include "dprintf.h"
#include "PBS/TMR.h"
#include <string.h>

Include dependency graph for HDE.c:


Classes
struct	_HDE
	The control structure for the HDE facility. More...
struct	_HistLimits_f
	Min and Max indices of a region of the histogram. More...
union	_HistLimits
	Min and Max indices of a region of the histogram as a union between and uninterpretted 32-bit integer and its field representation. More...
struct	_HistCore_f
	Describes the result of the encoding selection process, giving the lower and upper bin limits along with the number of entries outside that region. More...
union	_HistCore
	The histogram core description as a union between an uninterpretted 32-bit representation and its field representation. More...
struct	_CodesSummary_f
	Lays out the structure of the return summary from codes_condition. More...
union	_CodesSummary
	Lays out the structure of the return summary from codes_condition as a union between an uninterpretted 32-bit representation and its field representation. More...
struct	_DeltasSummary_f
	Summarizes the parameters describing the delta code lengths array. More...
union	_DeltasSummary
	Summarizes the parameters describing the delta code lengths array as a union between an uninterpretted 32-bit number and its field representation. More...
Defines
#define	BA_32
#define	NULL ((void *)(0))
#define	_monitor_declare(statements)
#define	_monitor_time(_mon, _idx)
#define	_monitor(_var, val)
#define	monitor_report(_mon)
#define	_CODES(_l0, _c0, _l1, _c1, _l2, _c2)
#define	TOUCH(_adr, _offset)
Typedefs
typedef struct _HDE	HDE
typedef struct _HistLimits_f	HistLimits_f
	Typedef for struct _HistLimits.
typedef union _HistLimits	HistLimits
	Typedef for union _HistLimits.
typedef struct _HistCore_f	HistCore_f
	Typedef for struct _HistCore.
typedef union _HistCore	HistCore
	Typedef for union _HistCode.
typedef struct _CodesSummary_f	CodesSummary_f
	Typedef for struct _CodesStatus_f.
typedef union _CodesSummary	CodesSummary
	Typedef for union _CodesSummary.
typedef struct _DeltasSummary_f	DeltasSummary_f
	Typedef for struct _DeltasSummary_f.
typedef union _DeltasSummary	DeltasSummary
	Typedef for union _DeltasSummary.
Functions
static __inline unsigned int	hist_limits_findL (const unsigned int *hist, int cnt)
	Finds the indices of the smallest and largest non-zero entry in the specified histogram.
static __inline unsigned long long int	hist_selectL (const unsigned int *hist, int nentries, HistLimits limits, int nbins)
	Finds the nbits that encompass the largest number of entries for the specified histogram.
static __inline int	hist_copyL (unsigned int dst, const unsigned int src, int min, int max)
	Copies the core of the histogram (i.e. from the first non-zero element to the last non-zero element.
static __inline unsigned int	hist_limits_find (const unsigned short int *hist, int cnt)
	Finds the indices of the smallest and largest non-zero entry in the specified histogram.
static __inline unsigned long long int	hist_select (const unsigned short int *hist, int nentries, HistLimits limits, int nbins)
	Finds the nbits that encompass the largest number of entries for the specified histogram.
static __inline int	hist_copy (unsigned int dst, const unsigned short int src, int min, int max)
	Copies the core of the histogram (i.e. from the first non-zero element to the last non-zero element.
static __inline unsigned int	huff_table_encode (unsigned int buf, unsigned int pos, CodesSummary cs, const HUFF_code codes, const unsigned int freq, signed char deltas, int min, int max, unsigned int nunderflow, unsigned int noverflow)
	Encodes the Huffman encoding table.
static __inline unsigned int	huff_symbols_encode (unsigned int buf, unsigned int pos, const HUFF_code codes, int min, int max, unsigned int nunderflow, unsigned int noverflow, int xsymbols, const short int *symbols, int nsymbols)
	Encodes the pedestal subtracted ADC values using the specified Huffman codes.
static __inline unsigned int	direct_symbols_encode (HDE hde, unsigned int buf, unsigned int pos, int min, int nbits, const short int *symbols, int nsymbols)
	Encodes the specified symbols symbols using the specified histogram of frequencies. Both the symbols and the histogram are presented as 16-bit values.
static __inline unsigned int	codes_condition (HUFF_code codes, const unsigned int freq, int ncodes)
	Conditions the code array by setting the code lengths of non-existent codes to the maximum code length + 1.
static __inline unsigned int	form_deltas (signed char deltas, const HUFF_code codes, int ncodes, int nseed, int seed)
	Forms the array code lengths deltas.
static __inline void	hist_deltas (unsigned int hist, int min, int nbins, const signed char deltas, int ndeltas)
	Histograms the delta distribution.
static __inline unsigned int	pack_short (unsigned int *buf, unsigned int pos, short int val)
	Packs the number of bits needed to contain the short integer and its value.
static __inline unsigned int	pack_seed_min_max (unsigned int *buf, unsigned int pos, int seed, int min, int max)
static __inline unsigned int	pack_delta1 (unsigned int buf, unsigned int pos, const signed char deltas, int ndeltas, int min, int max_means_0)
	High efficiency routine to handle the case when all the deltas are 0 or 1.
static __inline unsigned int	pack_delta2 (unsigned int buf, unsigned int pos, const signed char deltas, int ndeltas, int min, int max_means_0)
	High efficiency routine to handle the case when all the delta range is only 2 (3 values).
static __inline unsigned int	pack_delta_huff (unsigned int buf, unsigned int pos, const signed char deltas, int cnt, int min, int max, int max_means_0)
	Packs the delta code lengths as a huffman table.
	declare (static void print_nbits(const int *f, int cnt, int tot))
unsigned int	HDE_sizeof (unsigned int nhuff)
	Returns the size, in bytes, for a handle to hold a Huffman distribution of huffman_bins.
void *	HDE_construct (HDE *hde, unsigned int nhuff)
	Constructs (initializes) the specified HDE structure.
void	HDE_tableConstructL (HDE hde, unsigned int nhuff, const unsigned int hist, int nbins, int nentries)
	Constructs HDE Huffman Table associated with the specified distribution.
unsigned int	HDE_tableEncode (HDE hde, unsigned int buf, unsigned int pos)
	Encodes a previously constructed table.
unsigned int	HDE_symbolsEncodeS (HDE hde, unsigned int buf, unsigned int pos, const unsigned short int *symbols, int nsymbols)
	Encodes the set of symbols using the encoding information in hde. This encoding information must have been previously setup using HDE_encodeTable.
unsigned int	HDE_encodeSS (HDE hde, unsigned int buf, unsigned int pos, unsigned int nhuff, const unsigned short int hist, int nbins, const short int symbols, int nsymbols)
	Encodes the specified symbols symbols using the specified histogram of frequencies. Both the symbols and the histogram are presented as 16-bit values.
const HDE_assay *	HDE_assayLocate (const HDE *hde)
	Returns a pointer to the publically defined piece of this structure. This can be a one-time call, i.e. for any given HDE structure, this routine always returns the same value.
void	HDE_histClearL (const HDE hde, unsigned int hist)
	Clears the histogram using the active bin range stored in the HDE_assay block of the HDE structure.
void	HDE_histClearS (const HDE hde, unsigned short int hist)
	Clears the histogram using the active bin range stored in the HDE_assay block of the HDE structure.

Detailed Description

Implementation of the routines to encodes a distribution of symbols using a Huffman encoding technique. Routines are available to encode both the distribution itself and the resulting Huffman table.

Author:: JJRussell - russell@slac.stanford.edu


   CVS $Id: HDE.c,v 1.8 2009/06/19 02:02:06 russell Exp $

Define Documentation

#define _CODES	(	_l0,
		_c0,
		_l1,
		_c1,
		_l2,
		_c2	)

Value:

(                                         \
      (((_c2 << 2) | _l2) << 8) |             \
      (((_c1 << 2) | _l1) << 4) |             \
      (((_c0 << 2) | _l0) << 0)               \
    )

Function Documentation

static __inline unsigned int codes_condition	(	HUFF_code *	codes,
		const unsigned int *	freq,
		int	ncodes
	)			`[static]`

Conditions the code array by setting the code lengths of non-existent codes to the maximum code length + 1.

Returns:: A packed value with the minimum code length in the low 8-bits

Parameters:

	codes	The codes to condition
	freq	The frequency distribution. Elements with 0 entries have their corresponding codes 'conditioned'
	ncodes	The number of codes and also, by definition, the number elements in freq.

static __inline unsigned int direct_symbols_encode	(	HDE *	hde,
		unsigned int *	buf,
		unsigned int	pos,
		int	min,
		int	nbits,
		const short int *	symbols,
		int	nsymbols
	)			`[static]`

Encodes the specified symbols symbols using the specified histogram of frequencies. Both the symbols and the histogram are presented as 16-bit values.

Returns:: The updated bit write position

Parameters:

	hde	The HDE control structure
	buf	The output buffer address
	pos	The current write bit offset
	min	The value of the smallest symbol
	nbits	The number of bits needed to encode the widest symbol
	symbols	The array of symbols
	nsymbols	The number of symbols

static __inline unsigned int form_deltas	(	signed char *	deltas,
		const HUFF_code *	codes,
		int	ncodes,
		int	nseed,
		int	seed
	)			`[static]`

Forms the array code lengths deltas.

Returns:: A summary description, giving the min, max and seed values

Parameters:

	deltas	The array of deltas to be filled out
	codes	The HUFF_man code array to be differinated
	ncodes	The number of codes in codes
	nseed	The seed bin
	seed	The seed value

const HDE_assay* HDE_assayLocate ( const HDE * hde )

Returns a pointer to the publically defined piece of this structure. This can be a one-time call, i.e. for any given HDE structure, this routine always returns the same value.

Returns:: Pointer to the HDE_assay structure

Parameters:

hde

The HDE control structure

The information returned is mainly of diagnostic use. However, knowing the min and max bin entry allows one to efficiently clear a previously used histogram.

void* HDE_construct	(	HDE *	hde,
		unsigned int	nhuff
	)

Constructs (initializes) the specified HDE structure.

Returns:: The next address after this structure.

Parameters:

	hde	The HDE control structure to construct
	nhuff	The maximum number of Huffman encoding bins that this control structure is meant to support.

The size of this structure should be acquired by a call to HDE_sizeof. The parameter huffman_nbins must be the same in the call to HDE_sizeof and HDE_construct.

unsigned int HDE_encodeSS	(	HDE *	hde,
		unsigned int *	buf,
		unsigned int	pos,
		unsigned int	nhuff,
		const unsigned short int *	hist,
		int	nbins,
		const short int *	symbols,
		int	nsymbols
	)

Encodes the specified symbols symbols using the specified histogram of frequencies. Both the symbols and the histogram are presented as 16-bit values.

Returns:: The updated bit write position

Parameters:

	hde	The HDE control structure
	buf	The output buffer address
	pos	The current write bit offset
	nhuff	Provides a means to limit the size of the huffman encoding region to a region that is smaller than what was specified during the HDE construction (i.e. the nhuff parameter) The construction value is used, if this value is 0 or larger.
	hist	The frequency histogram. The histogram is such that it extends -/+ nbins from this pointer. That is, this is the center of the histogram.
	nbins	The half width of the histogram
	symbols	The array of symbols
	nsymbols	The number of symbols

void HDE_histClearL	(	const HDE *	hde,
		unsigned int *	hist
	)

Clears the histogram using the active bin range stored in the HDE_assay block of the HDE structure.

Parameters:

	hde	The HDE control handle
	hist	The histogram to clear

This routine must be called after HDE_encodeSS has been called, since it is that routine that sets up the HDE_assay block

void HDE_histClearS	(	const HDE *	hde,
		unsigned short int *	hist
	)

Clears the histogram using the active bin range stored in the HDE_assay block of the HDE structure.

Parameters:

	hde	The HDE control handle
	hist	The histogram to clear

This routine must be called after HDE_encodeSS has been called, since it is that routine that sets up the HDE_assay block

unsigned int HDE_sizeof ( unsigned int nhuff )

Returns the size, in bytes, for a handle to hold a Huffman distribution of huffman_bins.

Parameters:

nhuff

The maximum size of the Huffman encoding area Suggested values are small powers of 2 like 32, 64, 128. Note also up to 3 bins may be used to hold describe the underflow, overflow and exception areas. Currently these 3 are mapped into 1 bin, but this may change in a future implementation

For the most part, this only provides a working area. On host-based workstations with expandable stacks, this memory would go on the stack, but, it is too large to do this for embedded systems.

unsigned int HDE_symbolsEncodeS	(	HDE *	hde,
		unsigned int *	buf,
		unsigned int	pos,
		const unsigned short int *	symbols,
		int	nsymbols
	)

Encodes the set of symbols using the encoding information in hde. This encoding information must have been previously setup using HDE_encodeTable.

Returns:: The updated bit write position

Parameters:

	hde	The HDE control structure
	symbols	The array of symbols
	nsymbols	The number of symbols
	buf	The output buffer address
	pos	The current write bit offset

void HDE_tableConstructL	(	HDE *	hde,
		unsigned int	nhuff,
		const unsigned int *	hist,
		int	nbins,
		int	nentries
	)

Constructs HDE Huffman Table associated with the specified distribution.

Returns:: The updated bit write position

Parameters:

	hde	The HDE control structure
	nhuff	Provides a means to limit the size of the huffman encoding region to a region that is smaller than what was specified during the HDE construction (i.e. the nhuff parameter) The construction value is used, if this value is 0 or larger.
	hist	The frequency histogram. The histogram is such that it extends -/+ nbins from this pointer. That is, this is the center of the histogram.
	nbins	The half width of the histogram
	nentries	The number of entries in the histogram

unsigned int HDE_tableEncode	(	HDE *	hde,
		unsigned int *	buf,
		unsigned int	pos
	)

Encodes a previously constructed table.

Returns:: The updated bit write position

Parameters:

	hde	The HDE control structure
	buf	The output buffer address
	pos	The current write bit offset

static __inline int hist_copy	(	unsigned int *	dst,
		const unsigned short int *	src,
		int	min,
		int	max
	)			`[static]`

Copies the core of the histogram (i.e. from the first non-zero element to the last non-zero element.

Parameters:

	dst	The destination histogram
	src	The source histogram
	min	The first non-zero histogram bin
	max	The last non-zero histogram bin

This routine exists solely because the HUFF build routines only take an integer (not a short integer) frequency distribution.

static __inline int hist_copyL	(	unsigned int *	dst,
		const unsigned int *	src,
		int	min,
		int	max
	)			`[static]`

Copies the core of the histogram (i.e. from the first non-zero element to the last non-zero element.

Parameters:

	dst	The destination histogram
	src	The source histogram
	min	The first non-zero histogram bin
	max	The last non-zero histogram bin

static __inline void hist_deltas	(	unsigned int *	hist,
		int	min,
		int	nbins,
		const signed char *	deltas,
		int	ndeltas
	)			`[static]`

Histograms the delta distribution.

Parameters:

	hist	The resulting histogram
	min	The minimum bin number
	nbins	The number of bins in the histogram
	deltas	The deltas to histogram
	ndeltas	The number of deltas to histogram

static __inline unsigned int hist_limits_find	(	const unsigned short int *	hist,
		int	cnt
	)			`[static]`

Finds the indices of the smallest and largest non-zero entry in the specified histogram.

Parameters:

	hist	The target histogram
	cnt	The total number of entries in the histogram

static __inline unsigned int hist_limits_findL	(	const unsigned int *	hist,
		int	cnt
	)			`[static]`

Finds the indices of the smallest and largest non-zero entry in the specified histogram.

Parameters:

	hist	The target histogram
	cnt	The total number of entries in the histogram

static __inline unsigned long long int hist_select	(	const unsigned short int *	hist,
		int	nentries,
		HistLimits	limits,
		int	nbins
	)			`[static]`

Finds the nbits that encompass the largest number of entries for the specified histogram.

Parameters:

	hist	The target histogram
	nentries	The total number of entries described by the limits
	limits	The lower and upper bins of the histogram. These are the first and last bins with data
	nbins	The width to select.

static __inline unsigned long long int hist_selectL	(	const unsigned int *	hist,
		int	nentries,
		HistLimits	limits,
		int	nbins
	)			`[static]`

Finds the nbits that encompass the largest number of entries for the specified histogram.

Parameters:

	hist	The target histogram
	nentries	The total number of entries described by the limits
	limits	The lower and upper bins of the histogram. These are the first and last bins with data
	nbins	The width to select.

static __inline unsigned int huff_symbols_encode	(	unsigned int *	buf,
		unsigned int	pos,
		const HUFF_code *	codes,
		int	min,
		int	max,
		unsigned int	nunderflow,
		unsigned int	noverflow,
		int	xsymbols,
		const short int *	symbols,
		int	nsymbols
	)			`[static]`

Encodes the pedestal subtracted ADC values using the specified Huffman codes.

Returns:: The updated write bit position

Parameters:

	buf	The output buffer
	pos	The position of the next bit to fill
	codes	The Huffman codes
	min	The minimum symbol value for Huffman encoding
	max	The maximum symbol value for Huffman encoding If 'p
	nunderflow	The size of the underflow region
	noverflow	The size of the overflow region
	xsymbols	The number of symbols in the under/over flow regions
	symbols	The symbols to encode
	nsymbols	The number of symbols to encode

static __inline unsigned int huff_table_encode	(	unsigned int *	buf,
		unsigned int	pos,
		CodesSummary	cs,
		const HUFF_code *	codes,
		const unsigned int *	freq,
		signed char *	deltas,
		int	min,
		int	max,
		unsigned int	under,
		unsigned int	over
	)			`[static]`

Encodes the Huffman encoding table.

Returns:: The updated write bit position

Parameters:

	buf	The output buffer
	pos	The position of the next bit to fill
	cs	The code summary status
	codes	The Huffman codes
	freq	The frequency distribution. This is used to determine valid members.
	deltas	Scratch area for the code length deltas
	min	The minimum code index
	max	The maximum code index
	under	The number of bins in the underflow region
	over	The number of bins in the overflow region

static __inline unsigned int pack_delta1	(	unsigned int *	buf,
		unsigned int	pos,
		const signed char *	deltas,
		int	ndeltas,
		int	min,
		int	max_means_0
	)			`[static]`

High efficiency routine to handle the case when all the deltas are 0 or 1.

Returns:: The updated write bit position

Parameters:

	buf	The output buffer
	pos	The position of the next bit to fill
	deltas	The deltas, by defintion, these must be 0 or 1
	ndeltas	The number of deltas
	min	The minimum value
	max_means_0	If true, when the original code lengths restored from the deltas, the maximum code length really means 0

static __inline unsigned int pack_delta2	(	unsigned int *	buf,
		unsigned int	pos,
		const signed char *	deltas,
		int	ndeltas,
		int	min,
		int	max_means_0
	)			`[static]`

High efficiency routine to handle the case when all the delta range is only 2 (3 values).

Returns:: The updated write bit position

Parameters:

	buf	The output buffer
	pos	The position of the next bit to fill
	deltas	The deltas, must have a range of only 2
	ndeltas	The number of deltas
	min	The minimum value
	max_means_0	If true, when the original code lengths restored from the deltas, the maximum code length really means 0

Need just 1 or 2 bits of information to define this packing scheme

1 bit indicating that 0 is not the maximum occuring bin, and if so, another bits indicating which of the other two is the maximum occurring bin.

In practice here are the assignments

If max is Bin0 Bin1 Bin2 Len:Code Len:Code Lne:Code Min == -1 2,3 1,0 2,2 Min != -1 1:0 2,2 2,3

static __inline unsigned int pack_delta_huff	(	unsigned int *	buf,
		unsigned int	pos,
		const signed char *	deltas,
		int	ndeltas,
		int	min,
		int	max,
		int	max_means_0
	)			`[static]`

Packs the delta code lengths as a huffman table.

Returns:: The updated write bit position

Parameters:

	buf	The output buffer
	pos	The position of the next bit to fill
	deltas	The deltas to pack
	ndeltas	The number of deltas to pack
	min	The minimum delta value
	max	The maximum delta value
	max_means_0	If true, when the original code lengths restored from the deltas, the maximum code length really means 0

static __inline unsigned int pack_seed_min_max	(	unsigned int *	buf,
		unsigned int	pos,
		int	seed,
		int	min,
		int	max
	)			`[static]`

Returns:: The updated write bit position

Parameters:

	buf	The output buffer
	pos	The position of the next bit to fill
	seed	The seed value
	min	The minimum delta value
	max	The maximum delta value

Wish to make an optimization when all three values are small, as they are likely to be (usually 3 bits or less). A code giving the number of bits each is pack in is output. This code is

0 for 2 bits
1 for 3 bits
2 for 4 bits
3 for 6 bits

static __inline unsigned int pack_short	(	unsigned int *	buf,
		unsigned int	pos,
		short int	val
	)			`[static]`

Packs the number of bits needed to contain the short integer and its value.

Returns:: The update bit write position

Parameters:

	buf	The output buffer
	pos	The position of the next bit to fill
	val	The value to pack

Generated on Fri Jun 19 01:48:11 2009 by

1.5.3

HDE.c File Reference

Classes

Defines

Typedefs

Functions

Detailed Description

Define Documentation

Function Documentation