GLAST / LAT > DAQ and FSW > FSW > Doxygen Index> LDT / dev > encdec / rhel6-32
#include <LDT/BTE.h>
Functions | |
static __inline unsigned int | encode (unsigned int e, unsigned int w, unsigned int p1, unsigned int p3) |
Encodes the input word w into the output word e. | |
unsigned int __inline | BTE_wordCnts (unsigned int w, unsigned int pattern) |
Returns a packed 32-bit word, where each byte represents the count of the how times each of the 4 possible node values occurs. | |
unsigned int | BTE_wordEncode (unsigned int w, unsigned int pattern, unsigned int scheme_size) |
Encodes the original word and its higher level binary tree pattern returning a 32 bit output word. The algorithm is such that at most 32 bits are used, not counting the bits needed to encode the scheme. | |
unsigned int | BTE_wordPattern (unsigned int w) |
Prepares a pattern word which includes all but the lowest level of the binary tree. | |
unsigned int __inline | BTE_wordSizes (unsigned int w, unsigned int pattern) |
Computes the bit size of the encoded word using each of the 4 possible encoding schemes. | |
unsigned int | BTE_wordSchemeSize (unsigned int w, unsigned int pattern) |
Computes the optimal encoding scheme and size using of the 4 possible encoding schemes. | |
unsigned int | BTE_wordSize (unsigned int w, unsigned int pattern, unsigned int scheme) |
Computes the size using of the specified encoding schemes. | |
BTE_compressed | BTE_wordCompress (unsigned int w) |
Computes and returns the compressed word plus its size, in bits, plus the encoding scheme used. | |
unsigned int __inline | BTE_shortCnts (unsigned short int w, unsigned int pattern) |
Returns a packed 32-bit word, where each byte represents the count of the how times each of the 4 possible node values occurs. | |
unsigned int | BTE_shortEncode (unsigned short int w, unsigned int pattern, unsigned int scheme_size) |
Encodes the original word and its higher level binary tree pattern returning a 16 (only 14 used) bit output word. The algorithm is such that at most 16 bits are used, not counting the bits needed to encode the scheme. | |
unsigned int | BTE_shortPattern (unsigned short int w) |
Prepares a pattern word which includes all but the lowest level of the binary tree. | |
unsigned int __inline | BTE_shortSizes (unsigned short int w, unsigned int pattern) |
Computes the bit size of the encoded word using each of the 4 possible encoding schemes. | |
unsigned int | BTE_shortSchemeSize (unsigned short int w, unsigned int pattern) |
Computes the optimal encoding scheme and size using of the 4 possible encoding schemes. | |
unsigned int | BTE_shortSize (unsigned short int w, unsigned int pattern, unsigned int scheme) |
Computes the size using of the specified encoding schemes. | |
BTE_compressed | BTE_shortCompress (unsigned short int w) |
Computes and returns the compressed short word plus its size, in bits,plus the encoding scheme used. |
Routines to encode bit strings using a binary tree
CVS $Id: BTE.c,v 1.5 2011/03/25 23:57:13 russell Exp $
EXAMPLE The following shard of code shows how one ties these routines together to encode a 32 bit word, word.
unsigned int pattern = BTE_wordPatten (word); unsigned int scheme_size = BTE_wordSchemeSize (word, pattern); unsigned int encoded = BTE_wordEncode (word, pattern, scheme);
unsigned int BTE_shortCnts | ( | unsigned short int | w, | |
unsigned int | pattern | |||
) |
Returns a packed 32-bit word, where each byte represents the count of the how times each of the 4 possible node values occurs.
w | The word being encoded | |
pattern | The precompiled pattern word |
Referenced by BTE_shortSize(), and BTE_shortSizes().
BTE_compressed BTE_shortCompress | ( | unsigned short int | w | ) |
Computes and returns the compressed short word plus its size, in bits,plus the encoding scheme used.
w | The short word to compress |
References BTE_shortEncode(), BTE_shortPattern(), BTE_shortSchemeSize(), _BTE_compressed::scheme_size, and _BTE_compressed::word.
unsigned int BTE_shortEncode | ( | unsigned short int | w, | |
unsigned int | pattern, | |||
unsigned int | scheme_size | |||
) |
Encodes the original word and its higher level binary tree pattern returning a 16 (only 14 used) bit output word. The algorithm is such that at most 16 bits are used, not counting the bits needed to encode the scheme.
w | The original 16-bit word that is to be encoded | |
pattern | The higher level binary tree pattern word. This is generally computed by calling BTE_shortPrepare(). | |
scheme_size | The encoding scheme to be used. This is generally computed by BTE_shortSchemeSize (), but can be determined by other means. The scheme is one of |
Without resorting to statistical encoding methods one can pick the the state occuring most of the time to be represented by the symbol with only 1 bit, i.e. 0.
Of course, to properly decode the encoded word, one needs the symbol. The user is free to carry the which encoding is to be used by any means he wishes. An extreme example would be to use a fixed scheme for all the symbols. One might compute the size of a collection of symbols using all each scheme, then pick the one that gives the smallest size.
References encode().
Referenced by BTE_shortCompress().
unsigned int BTE_shortPattern | ( | unsigned short int | w | ) |
Prepares a pattern word which includes all but the lowest level of the binary tree.
w | The short word to encode |
+---------- x ----------+ half = 1 bit | | +---- x ----+ +---- x ----+ byte = 2 bits | | | | +- x -+ +- x -+ +- x -+ +- x -+ nibble = 4 bits | | | | | | | | x x x x x x x x 2 bit = 8 bits / \ / \ / \ / \ / \ / \ / \ / \ x x x x x x x x x x x x x x x x 1 bit = 16 bits -- 31 bits
This pattern word is arranged by levels from the highest levels in the most significant bits to the lowest levels. Note that the lowest level of the tree is original 16 bit word.
Here is an example of tree for w = 0x8001
1 L0 | 1--------------+----------------1 L1 | | 1-------+-------0 0-------+-------1 L2 | | | | 1---+---0 0---+---0 0---+---0 0---+---1 L3 | | | | | | | | 1-+-0 0-+-0 0-+-0 0-+-0 0-+-0 0-+-0 0-+-0 0-+-1 L4
l0 1 L1 1 1 L2 10 01 L3 1000 0001 L4 10000000 00000001
Which, ignoring the lowest level, l5, is the pattern.
1 11 1001 10000001 1000000000000001 0111 1001 1000 0001 1000 0000 0000 0001 = 0x79818001
Note, by convention, the highest level of the tree is ignored, so that only the upper 14 bits are used. This is beccause the upper bit only indicates whether the word is 0 or non-zero, something the user can easily determine.
Referenced by BTE_shortCompress().
unsigned int BTE_shortSchemeSize | ( | unsigned short int | w, | |
unsigned int | pattern | |||
) |
Computes the optimal encoding scheme and size using of the 4 possible encoding schemes.
w | The original short word (the lowest level of the tree | |
pattern | The pattern word (the higher levels of the tree |
0: Just use the original 32 bit number 1: Use the scheme that assigns the 01 pattern the value 0 2: Use the scheme that assigns the 10 pattern the value 0 3: Use the scheme that assigns the 11 pattern the value 0
References BTE_shortSizes().
Referenced by BTE_shortCompress().
unsigned int BTE_shortSize | ( | unsigned short int | w, | |
unsigned int | pattern, | |||
unsigned int | scheme | |||
) |
Computes the size using of the specified encoding schemes.
w | The original short word (the lowest level of the tree | |
pattern | The pattern word (the higher levels of the tree | |
scheme | The encoding scheme to use |
References BTE_shortCnts().
unsigned int BTE_shortSizes | ( | unsigned short int | w, | |
unsigned int | pattern | |||
) |
Computes the bit size of the encoded word using each of the 4 possible encoding schemes.
w | The original short word (the lowest level of the tree | |
pattern | The pattern word (the higher levels of the tree |
0: Use the original 16-bit number (implies low byte = 16) 1: Use the scheme that assigns the 01 pattern the value 0 2: Use the scheme that assigns the 10 pattern the value 0 3: Use the scheme that assigns the 11 pattern the value 0
References BTE_shortCnts().
Referenced by BTE_shortSchemeSize().
unsigned int BTE_wordCnts | ( | unsigned int | w, | |
unsigned int | pattern | |||
) |
Returns a packed 32-bit word, where each byte represents the count of the how times each of the 4 possible node values occurs.
w | The word being encoded | |
pattern | The precompiled pattern word |
Referenced by BTE_wordSize(), and BTE_wordSizes().
BTE_compressed BTE_wordCompress | ( | unsigned int | w | ) |
Computes and returns the compressed word plus its size, in bits, plus the encoding scheme used.
w | The word to compress |
References BTE_wordEncode(), BTE_wordPattern(), BTE_wordSchemeSize(), _BTE_compressed::scheme_size, and _BTE_compressed::word.
unsigned int BTE_wordEncode | ( | unsigned int | w, | |
unsigned int | pattern, | |||
unsigned int | scheme_size | |||
) |
Encodes the original word and its higher level binary tree pattern returning a 32 bit output word. The algorithm is such that at most 32 bits are used, not counting the bits needed to encode the scheme.
w | The original 32-bit word that is to be encoded | |
pattern | The higher level binary tree pattern word. This is generally computed by calling BTE_wordPrepare(). | |
scheme_size | The encoding scheme to be used. This is generally computed by BTE_wordSchemeSize (), but can be determined by other means. The scheme is one of |
Without resorting to statistical encoding methods one can pick the the state occuring most of the time to be represented by the symbol with only 1 bit, i.e. 0.
Of course, to properly decode the encoded word, one needs the symbol. The user is free to carry the which encoding is to be used by any means he wishes. An extreme example would be to use a fixed scheme for all the symbols. One might compute the size of a collection of symbols using all each scheme, then pick the one that gives the smallest size.
References encode().
Referenced by BTE_wordCompress().
unsigned int BTE_wordPattern | ( | unsigned int | w | ) |
Prepares a pattern word which includes all but the lowest level of the binary tree.
w | The word to encode |
+---------- x ----------+ word = 1 bit | | +---- x ----+ +---- x ----+ half = 2 bits | | | | +- x -+ +- x -+ +- x -+ +- x -+ byte = 4 bits | | | | | | | | x x x x x x x x nibble = 8 bits / \ / \ / \ / \ / \ / \ / \ / \ x x x x x x x x x x x x x x x x 2 bit = 16 bits ab cd ef gh ij kl mn op qr st uv wx yz AB CD EF 1 bit = 32 bits -- 63 bits
This pattern word is arranged by levels from the highest levels in the most significant bits to the lowest levels. Note that the lowest level of the tree is original 32 bit word.
Here is an example of tree for w = 0x00011000
1 L0 | 1--------------+----------------1 L1 | | 0-------+-------1 1-------+-------0 L2 | | | | 0---+---0 0---+---1 1---+---0 0---+---0 L3 | | | | | | | | 0-+-0 0-+-0 0-+-0 0-+-1 0-+-1 0-+-0 0-+-0 0-+-0 L4 00 00 00 00 00 00 00 01 00 01 00 00 00 00 00 00 L5
l0 1 L1 1 1 L2 01 10 L3 0001 0100 L4 00000001 01000000 L5 0000000000000001 0001000000000000
Which, ignoring the lowest level, l5, is the pattern.
0 1 11 0110 00010100 0000000101000000 = 0x76180140
Note, by convention, the highest level of the tree is ignored, so that only the upper 30 bits are used. This is beccause the upper bit only indicates whether the word is 0 or non-zero, something the user can easily determine.
Referenced by BTE_wordCompress().
unsigned int BTE_wordSchemeSize | ( | unsigned int | w, | |
unsigned int | pattern | |||
) |
Computes the optimal encoding scheme and size using of the 4 possible encoding schemes.
w | The original word (the lowest level of the tree | |
pattern | The pattern word (the higher levels of the tree |
0: Just use the original 32 bit number 1: Use the scheme that assignes the 01 pattern the value 0 2: Use the scheme that assignes the 10 pattern the value 0 3: Use the scheme that assignes the 11 pattern the value 0
References BTE_wordSizes().
Referenced by BTE_wordCompress().
unsigned int BTE_wordSize | ( | unsigned int | w, | |
unsigned int | pattern, | |||
unsigned int | scheme | |||
) |
Computes the size using of the specified encoding schemes.
w | The original word (the lowest level of the tree | |
pattern | The pattern word (the higher levels of the tree | |
scheme | The encoding scheme to use |
References BTE_wordCnts().
unsigned int BTE_wordSizes | ( | unsigned int | w, | |
unsigned int | pattern | |||
) |
Computes the bit size of the encoded word using each of the 4 possible encoding schemes.
w | The original word (the lowest level of the tree | |
pattern | The pattern word (the higher levels of the tree |
0: Use the original 32-bit number (implies low byte = 32) 1: Use the scheme that assigns the 01 pattern the value 0 2: Use the scheme that assigns the 10 pattern the value 0 3: Use the scheme that assigns the 11 pattern the value 0
References BTE_wordCnts().
Referenced by BTE_wordSchemeSize().
static unsigned int encode | ( | unsigned int | e, | |
unsigned int | w, | |||
unsigned int | p1, | |||
unsigned int | p3 | |||
) | [static] |
Encodes the input word w into the output word e.
e | The current encoded word | |
w | The new set of 32 bits to add | |
p1 | The pattern to associate with the encoding pattern 0 | |
p3 | The pattern to associate with the encoding pattern 3 |
Referenced by APE_bencode(), APE_sencode(), BTE_shortEncode(), and BTE_wordEncode().