\hypertarget{BTE_8h}{ \section{BTE.h File Reference} \label{BTE_8h}\index{BTE.h@{BTE.h}} } Binary Tree Encoding interface file. \subsection*{Classes} \begin{CompactItemize} \item struct \hyperlink{struct__BTE__compressed}{\_\-BTE\_\-compressed} \begin{CompactList}\small\item\em Combines the compressed word, its encoding scheme and its size in bits in one structure. \item\end{CompactList}\end{CompactItemize} \subsection*{Typedefs} \begin{CompactItemize} \item typedef struct \hyperlink{struct__BTE__compressed}{\_\-BTE\_\-compressed} \hyperlink{BTE_8h_76efb62e29dd1a374e02f4e1f26d031a}{BTE\_\-compressed} \begin{CompactList}\small\item\em Typedef for struct \hyperlink{struct__BTE__compressed}{\_\-BTE\_\-compressed}. \item\end{CompactList}\end{CompactItemize} \subsection*{Functions} \begin{CompactItemize} \item \hyperlink{struct__BTE__compressed}{BTE\_\-compressed} \hyperlink{BTE_8h_45f1c0f2339efa2adfe3612254f8812e}{BTE\_\-wordCompress} (unsigned int w) \begin{CompactList}\small\item\em Computes and returns the compressed word plus its size, in bits, plus the encoding scheme used. \item\end{CompactList}\item unsigned int \hyperlink{BTE_8h_ee361d5b1b046d67280a7b8fb498f4f0}{BTE\_\-wordEncode} (unsigned int w, unsigned int pattern, unsigned int scheme\_\-size) \begin{CompactList}\small\item\em 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. \item\end{CompactList}\item unsigned int \hyperlink{BTE_8h_de8031ce512968e844ddd570243f07d4}{BTE\_\-wordPattern} (unsigned int w) \begin{CompactList}\small\item\em Prepares a pattern word which includes all but the lowest level of the binary tree. \item\end{CompactList}\item unsigned int \hyperlink{BTE_8h_a430a760f3641441233df50946c0b4d0}{BTE\_\-wordSize} (unsigned int w, unsigned int pattern, unsigned int scheme) \begin{CompactList}\small\item\em Computes the size using of the specified encoding schemes. \item\end{CompactList}\item unsigned int \hyperlink{BTE_8h_252b86cba4395c153145a02591f209b9}{BTE\_\-wordSchemeSize} (unsigned int w, unsigned int pattern) \begin{CompactList}\small\item\em Computes the optimal encoding scheme and size using of the 4 possible encoding schemes. \item\end{CompactList}\item unsigned int \hyperlink{BTE_8h_4a9cc5118fb84aa93d0a2dbdb74527e9}{BTE\_\-wordSizes} (unsigned int w, unsigned int pattern) \begin{CompactList}\small\item\em Computes the bit size of the encoded word using each of the 4 possible encoding schemes. \item\end{CompactList}\item \hyperlink{struct__BTE__compressed}{BTE\_\-compressed} \hyperlink{BTE_8h_d92bfd5981ece1f73fe9a3f8b8983a0a}{BTE\_\-shortCompress} (unsigned short int w) \begin{CompactList}\small\item\em Computes and returns the compressed short word plus its size, in bits,plus the encoding scheme used. \item\end{CompactList}\item unsigned int \hyperlink{BTE_8h_f778a6799e1a2d50dde4b22810a4a567}{BTE\_\-shortEncode} (unsigned short int w, unsigned int pattern, unsigned int scheme\_\-size) \begin{CompactList}\small\item\em 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. \item\end{CompactList}\item unsigned int \hyperlink{BTE_8h_6bc79bf7bdf73157d6f556a5b2cbb9f6}{BTE\_\-shortPattern} (unsigned short int w) \begin{CompactList}\small\item\em Prepares a pattern word which includes all but the lowest level of the binary tree. \item\end{CompactList}\item unsigned int \hyperlink{BTE_8h_8212151a1c18ec1ac702de347895ab6b}{BTE\_\-shortSize} (unsigned short int w, unsigned int pattern, unsigned int scheme) \begin{CompactList}\small\item\em Computes the size using of the specified encoding schemes. \item\end{CompactList}\item \hypertarget{BTE_8h_9de37257d575fb1dc0210549e70740f9}{ unsigned int \textbf{BTE\_\-shortSchemeSize} (unsigned short w, unsigned int pattern)} \label{BTE_8h_9de37257d575fb1dc0210549e70740f9} \item unsigned int \hyperlink{BTE_8h_ae60f396d8e2a4bb11cc6cbcc52f3b57}{BTE\_\-shortSizes} (unsigned short int w, unsigned int pattern) \begin{CompactList}\small\item\em Computes the bit size of the encoded word using each of the 4 possible encoding schemes. \item\end{CompactList}\item static \_\-\_\-inline int \hyperlink{BTE_8h_31917c0a114b7ee84b8b804666fc06fe}{BTE\_\-size} (unsigned int scheme\_\-size) \begin{CompactList}\small\item\em Extracts the size, in bits, from the scheme/size word. \item\end{CompactList}\item static \_\-\_\-inline int \hyperlink{BTE_8h_8cfe3b26233cc32cd825be8d45790108}{BTE\_\-scheme} (unsigned int scheme\_\-size) \begin{CompactList}\small\item\em Extracts the encoding scheme, from the scheme/size word. \item\end{CompactList}\end{CompactItemize} \subsection{Detailed Description} Binary Tree Encoding interface file. \begin{Desc} \item[Author:]JJRussell - \href{mailto:russell@slac.stanford.edu}{\tt russell@slac.stanford.edu}\end{Desc} \footnotesize\begin{verbatim} CVS $Id: BTE.h,v 1.3 2009/04/29 23:06:40 russell Exp $ \end{verbatim} \normalsize Interface specification for routines to encode bit strings using a binary tree. \subsection{Typedef Documentation} \hypertarget{BTE_8h_76efb62e29dd1a374e02f4e1f26d031a}{ \index{BTE.h@{BTE.h}!BTE\_\-compressed@{BTE\_\-compressed}} \index{BTE\_\-compressed@{BTE\_\-compressed}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-compressed}]{\setlength{\rightskip}{0pt plus 5cm}{\bf BTE\_\-compressed}}} \label{BTE_8h_76efb62e29dd1a374e02f4e1f26d031a} Typedef for struct \hyperlink{struct__BTE__compressed}{\_\-BTE\_\-compressed}. \begin{Desc} \item[]This is the return value of the convenience function BTE\_\-wordCompress. \end{Desc} \subsection{Function Documentation} \hypertarget{BTE_8h_8cfe3b26233cc32cd825be8d45790108}{ \index{BTE.h@{BTE.h}!BTE\_\-scheme@{BTE\_\-scheme}} \index{BTE\_\-scheme@{BTE\_\-scheme}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-scheme}]{\setlength{\rightskip}{0pt plus 5cm}static \_\-\_\-inline int BTE\_\-scheme (unsigned int {\em schemeSize})\hspace{0.3cm}{\tt \mbox{[}static\mbox{]}}}} \label{BTE_8h_8cfe3b26233cc32cd825be8d45790108} Extracts the encoding scheme, from the scheme/size word. \begin{Desc} \item[Returns:]The encoding scheme to be used\end{Desc} \begin{Desc} \item[Parameters:] \begin{description} \item[{\em schemeSize}]The word containing the packed scheme and size fields. This is returned by BTE\_\-wordSchemeSize \end{description} \end{Desc} \hypertarget{BTE_8h_d92bfd5981ece1f73fe9a3f8b8983a0a}{ \index{BTE.h@{BTE.h}!BTE\_\-shortCompress@{BTE\_\-shortCompress}} \index{BTE\_\-shortCompress@{BTE\_\-shortCompress}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-shortCompress}]{\setlength{\rightskip}{0pt plus 5cm}{\bf BTE\_\-compressed} BTE\_\-shortCompress (unsigned short int {\em w})}} \label{BTE_8h_d92bfd5981ece1f73fe9a3f8b8983a0a} Computes and returns the compressed short word plus its size, in bits,plus the encoding scheme used. \begin{Desc} \item[Returns:]A BTE\_\-compressed structure containing the compressed word plus its size, in bits, plus the encoding scheme used\end{Desc} \begin{Desc} \item[Parameters:] \begin{description} \item[{\em w}]The short word to compress\end{description} \end{Desc} \begin{Desc} \item[]This is a convenience routine combining the\begin{itemize} \item BTE\_\-shortPattern\item BTE\_\-shortSchemeSize\item BTE\_\-shortEncode\end{itemize} \end{Desc} \begin{Desc} \item[]While this routine is convenient, it does so at some cost. Each word is encoded according to the optimal scheme. This means the caller must make sure the encoding scheme is encoded along with each compressed word. The encoding of the encoding scheme itself costs some number of bits.\end{Desc} \begin{Desc} \item[]For a collection of words to encode, it may be more optimal to pick a fixed scheme. The fixed scheme may be based on some apriori knowledge (one just picks a scheme) or one computes the size of the collection for each of the 4 schemes, then uses the scheme giving the smallest total size of the whole collection, to encode the whole collection. \end{Desc} References BTE\_\-shortEncode(), BTE\_\-shortPattern(), BTE\_\-shortSchemeSize(), \_\-BTE\_\-compressed::scheme\_\-size, and \_\-BTE\_\-compressed::word.\hypertarget{BTE_8h_f778a6799e1a2d50dde4b22810a4a567}{ \index{BTE.h@{BTE.h}!BTE\_\-shortEncode@{BTE\_\-shortEncode}} \index{BTE\_\-shortEncode@{BTE\_\-shortEncode}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-shortEncode}]{\setlength{\rightskip}{0pt plus 5cm}unsigned int BTE\_\-shortEncode (unsigned short int {\em w}, \/ unsigned int {\em pattern}, \/ unsigned int {\em scheme\_\-size})}} \label{BTE_8h_f778a6799e1a2d50dde4b22810a4a567} 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. \begin{Desc} \item[Parameters:] \begin{description} \item[{\em w}]The original 16-bit word that is to be encoded \item[{\em pattern}]The higher level binary tree pattern word. This is generally computed by calling BTE\_\-shortPrepare(). \item[{\em 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\end{description} \end{Desc} \begin{itemize} \item 0, no encoding, just return w,\item 1, encode using 01 = 0, 10 = 10, 11 = 11\item 2, encode using 01 = 10, 10 = 0, 11 = 11\item 3, encode using 01 = 10, 10 = 11, 11 = 0\end{itemize} \begin{Desc} \item[Why is there an encoding scheme]The node of the binary encoding is a 2 bit number, indicating whether the left/right neighors are non-empty. However, to get to a node {\em on\/} of the left or right neighbors {\em must\/} be non-empty. Therefore there are really only 3 states, {\em i.e\/}. only the states 01, 10 and 11 must be represented, 00, being impossible. These three states can be represented by the following bit strings\end{Desc} \begin{itemize} \item 0\item 10\item 11\end{itemize} 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, {\em 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().\hypertarget{BTE_8h_6bc79bf7bdf73157d6f556a5b2cbb9f6}{ \index{BTE.h@{BTE.h}!BTE\_\-shortPattern@{BTE\_\-shortPattern}} \index{BTE\_\-shortPattern@{BTE\_\-shortPattern}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-shortPattern}]{\setlength{\rightskip}{0pt plus 5cm}unsigned int BTE\_\-shortPattern (unsigned short int {\em w})}} \label{BTE_8h_6bc79bf7bdf73157d6f556a5b2cbb9f6} Prepares a pattern word which includes all but the lowest level of the binary tree. \begin{Desc} \item[Parameters:] \begin{description} \item[{\em w}]The short word to encode \end{description} \end{Desc} \begin{Desc} \item[Returns:]The pattern word\end{Desc} A 16 bit word expressed as a binary tree takes a maximum of 31 bits to encode. This tree looks like \footnotesize\begin{verbatim} +---------- 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 \end{verbatim} \normalsize 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 \footnotesize\begin{verbatim} 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 \end{verbatim} \normalsize The levels are \footnotesize\begin{verbatim} l0 1 L1 1 1 L2 10 01 L3 1000 0001 L4 10000000 00000001 \end{verbatim} \normalsize Which, ignoring the lowest level, l5, is the pattern. \footnotesize\begin{verbatim} 1 11 1001 10000001 1000000000000001 0111 1001 1000 0001 1000 0000 0000 0001 = 0x79818001 \end{verbatim} \normalsize 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().\hypertarget{BTE_8h_8212151a1c18ec1ac702de347895ab6b}{ \index{BTE.h@{BTE.h}!BTE\_\-shortSize@{BTE\_\-shortSize}} \index{BTE\_\-shortSize@{BTE\_\-shortSize}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-shortSize}]{\setlength{\rightskip}{0pt plus 5cm}unsigned int BTE\_\-shortSize (unsigned short int {\em w}, \/ unsigned int {\em pattern}, \/ unsigned int {\em scheme})}} \label{BTE_8h_8212151a1c18ec1ac702de347895ab6b} Computes the size using of the specified encoding schemes. \begin{Desc} \item[Returns:]A packed word containing the encoding scheme and its size in bits. The upper 16 bits are the scheme number and the lower 16 bits is the size in bits.\end{Desc} \begin{Desc} \item[Parameters:] \begin{description} \item[{\em w}]The original short word (the lowest level of the tree \item[{\em pattern}]The pattern word (the higher levels of the tree \item[{\em scheme}]The encoding scheme to use\end{description} \end{Desc} The schemes are 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\_\-shortCnts().\hypertarget{BTE_8h_ae60f396d8e2a4bb11cc6cbcc52f3b57}{ \index{BTE.h@{BTE.h}!BTE\_\-shortSizes@{BTE\_\-shortSizes}} \index{BTE\_\-shortSizes@{BTE\_\-shortSizes}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-shortSizes}]{\setlength{\rightskip}{0pt plus 5cm}unsigned int BTE\_\-shortSizes (unsigned short int {\em w}, \/ unsigned int {\em pattern})}} \label{BTE_8h_ae60f396d8e2a4bb11cc6cbcc52f3b57} Computes the bit size of the encoded word using each of the 4 possible encoding schemes. \begin{Desc} \item[Returns:]The 4 sizes packed a byte each into a 32-bit word with scheme 0 packed into the least signficant byte, scheme 1 into the next least signficant byte, etc.\end{Desc} \begin{Desc} \item[Parameters:] \begin{description} \item[{\em w}]The original short word (the lowest level of the tree \item[{\em pattern}]The pattern word (the higher levels of the tree\end{description} \end{Desc} The encoding size of using each of the 4 possible encoding schemes is found. The sizes are packed into the 32-bit return value, a byte/size with scheme 0 in the least significant byte. The scheme identifiers are 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().\hypertarget{BTE_8h_31917c0a114b7ee84b8b804666fc06fe}{ \index{BTE.h@{BTE.h}!BTE\_\-size@{BTE\_\-size}} \index{BTE\_\-size@{BTE\_\-size}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-size}]{\setlength{\rightskip}{0pt plus 5cm}static \_\-\_\-inline int BTE\_\-size (unsigned int {\em schemeSize})\hspace{0.3cm}{\tt \mbox{[}static\mbox{]}}}} \label{BTE_8h_31917c0a114b7ee84b8b804666fc06fe} Extracts the size, in bits, from the scheme/size word. \begin{Desc} \item[Returns:]The size field\end{Desc} \begin{Desc} \item[Parameters:] \begin{description} \item[{\em schemeSize}]The word containing the packed scheme and size fields. This is returned by BTE\_\-wordSchemeSize \end{description} \end{Desc} \hypertarget{BTE_8h_45f1c0f2339efa2adfe3612254f8812e}{ \index{BTE.h@{BTE.h}!BTE\_\-wordCompress@{BTE\_\-wordCompress}} \index{BTE\_\-wordCompress@{BTE\_\-wordCompress}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-wordCompress}]{\setlength{\rightskip}{0pt plus 5cm}{\bf BTE\_\-compressed} BTE\_\-wordCompress (unsigned int {\em w})}} \label{BTE_8h_45f1c0f2339efa2adfe3612254f8812e} Computes and returns the compressed word plus its size, in bits, plus the encoding scheme used. \begin{Desc} \item[Returns:]A BTE\_\-compressed structure containing the compressed word plus its size, in bits, plus the encoding scheme used\end{Desc} \begin{Desc} \item[Parameters:] \begin{description} \item[{\em w}]The word to compress\end{description} \end{Desc} \begin{Desc} \item[]This is a convenience routine combining the\begin{itemize} \item BTE\_\-wordPattern\item BTE\_\-wordSchemeSize\item BTE\_\-wordEncode\end{itemize} \end{Desc} \begin{Desc} \item[]While this routine is convenient, it does so at some cost. Each word is encoded according to the optimal scheme. This means the caller must make sure the encoding scheme is encoded along with each compressed word. The encoding of the encoding scheme itself costs some number of bits.\end{Desc} \begin{Desc} \item[]For a collection of words to encode, it may be more optimal to pick a fixed scheme. The fixed scheme may be based on some apriori knowledge (one just picks a scheme) or one computes the size of the collection for each of the 4 schemes, then uses the scheme giving the smallest total size of the whole collection, to encode the whole collection. \end{Desc} References BTE\_\-wordEncode(), BTE\_\-wordPattern(), BTE\_\-wordSchemeSize(), \_\-BTE\_\-compressed::scheme\_\-size, and \_\-BTE\_\-compressed::word.\hypertarget{BTE_8h_ee361d5b1b046d67280a7b8fb498f4f0}{ \index{BTE.h@{BTE.h}!BTE\_\-wordEncode@{BTE\_\-wordEncode}} \index{BTE\_\-wordEncode@{BTE\_\-wordEncode}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-wordEncode}]{\setlength{\rightskip}{0pt plus 5cm}unsigned int BTE\_\-wordEncode (unsigned int {\em w}, \/ unsigned int {\em pattern}, \/ unsigned int {\em scheme\_\-size})}} \label{BTE_8h_ee361d5b1b046d67280a7b8fb498f4f0} 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. \begin{Desc} \item[Parameters:] \begin{description} \item[{\em w}]The original 32-bit word that is to be encoded \item[{\em pattern}]The higher level binary tree pattern word. This is generally computed by calling BTE\_\-wordPrepare(). \item[{\em 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\end{description} \end{Desc} \begin{itemize} \item 0, no encoding, just return w,\item 1, encode using 01 = 0, 10 = 10, 11 = 11\item 2, encode using 01 = 10, 10 = 0, 11 = 11\item 3, encode using 01 = 10, 10 = 11, 11 = 0\end{itemize} \begin{Desc} \item[Why is there an encoding scheme]The node of the binary encoding is a 2 bit number, indicating whether the left/right neighors are non-mpty. However, to get to a node {\em on\/} of the left or right neighbors {\em must\/} be non-empty. Therefore there are really only 3 states, {\em i.e\/}. only the states 01, 10 and 11 must be represented, 00, being impossible. These three states can be represented by the following bit strings\end{Desc} \begin{itemize} \item 0\item 10\item 11\end{itemize} 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, {\em 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().\hypertarget{BTE_8h_de8031ce512968e844ddd570243f07d4}{ \index{BTE.h@{BTE.h}!BTE\_\-wordPattern@{BTE\_\-wordPattern}} \index{BTE\_\-wordPattern@{BTE\_\-wordPattern}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-wordPattern}]{\setlength{\rightskip}{0pt plus 5cm}unsigned int BTE\_\-wordPattern (unsigned int {\em w})}} \label{BTE_8h_de8031ce512968e844ddd570243f07d4} Prepares a pattern word which includes all but the lowest level of the binary tree. \begin{Desc} \item[Parameters:] \begin{description} \item[{\em w}]The word to encode \end{description} \end{Desc} \begin{Desc} \item[Returns:]The pattern word\end{Desc} A 32 bit word express as a binary tree takes a maximum of 63 bits to encode. This tree looks like \footnotesize\begin{verbatim} +---------- 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 \end{verbatim} \normalsize 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 \footnotesize\begin{verbatim} 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 \end{verbatim} \normalsize The levels are \footnotesize\begin{verbatim} l0 1 L1 1 1 L2 01 10 L3 0001 0100 L4 00000001 01000000 L5 0000000000000001 0001000000000000 \end{verbatim} \normalsize Which, ignoring the lowest level, l5, is the pattern. \footnotesize\begin{verbatim} 0 1 11 0110 00010100 0000000101000000 = 0x76180140 \end{verbatim} \normalsize 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().\hypertarget{BTE_8h_252b86cba4395c153145a02591f209b9}{ \index{BTE.h@{BTE.h}!BTE\_\-wordSchemeSize@{BTE\_\-wordSchemeSize}} \index{BTE\_\-wordSchemeSize@{BTE\_\-wordSchemeSize}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-wordSchemeSize}]{\setlength{\rightskip}{0pt plus 5cm}unsigned int BTE\_\-wordSchemeSize (unsigned int {\em w}, \/ unsigned int {\em pattern})}} \label{BTE_8h_252b86cba4395c153145a02591f209b9} Computes the optimal encoding scheme and size using of the 4 possible encoding schemes. \begin{Desc} \item[Returns:]A packed word containing the optimal encoding scheme and its size in bits. The upper 16 bits are the scheme number and the lower 16 bits is the size in bits.\end{Desc} \begin{Desc} \item[Parameters:] \begin{description} \item[{\em w}]The original word (the lowest level of the tree \item[{\em pattern}]The pattern word (the higher levels of the tree\end{description} \end{Desc} The encoding size of using each of the 4 possible encoding schemes is found. The smallest size and its corresponding scheme identifier are returned. The scheme identifiers are 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().\hypertarget{BTE_8h_a430a760f3641441233df50946c0b4d0}{ \index{BTE.h@{BTE.h}!BTE\_\-wordSize@{BTE\_\-wordSize}} \index{BTE\_\-wordSize@{BTE\_\-wordSize}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-wordSize}]{\setlength{\rightskip}{0pt plus 5cm}unsigned int BTE\_\-wordSize (unsigned int {\em w}, \/ unsigned int {\em pattern}, \/ unsigned int {\em scheme})}} \label{BTE_8h_a430a760f3641441233df50946c0b4d0} Computes the size using of the specified encoding schemes. \begin{Desc} \item[Returns:]A packed word containing the encoding scheme and its size in bits. The upper 16 bits are the scheme number and the lower 16 bits is the size in bits.\end{Desc} \begin{Desc} \item[Parameters:] \begin{description} \item[{\em w}]The original word (the lowest level of the tree \item[{\em pattern}]The pattern word (the higher levels of the tree \item[{\em scheme}]The encoding scheme to use\end{description} \end{Desc} The schems are 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\_\-wordCnts().\hypertarget{BTE_8h_4a9cc5118fb84aa93d0a2dbdb74527e9}{ \index{BTE.h@{BTE.h}!BTE\_\-wordSizes@{BTE\_\-wordSizes}} \index{BTE\_\-wordSizes@{BTE\_\-wordSizes}!BTE.h@{BTE.h}} \subsubsection[{BTE\_\-wordSizes}]{\setlength{\rightskip}{0pt plus 5cm}unsigned int BTE\_\-wordSizes (unsigned int {\em w}, \/ unsigned int {\em pattern})}} \label{BTE_8h_4a9cc5118fb84aa93d0a2dbdb74527e9} Computes the bit size of the encoded word using each of the 4 possible encoding schemes. \begin{Desc} \item[Returns:]The 4 sizes packed a byte each into a 32-bit word with scheme 0 packed into the least signficant byte, scheme 1 into the next least signficant byte, etc.\end{Desc} \begin{Desc} \item[Parameters:] \begin{description} \item[{\em w}]The original word (the lowest level of the tree \item[{\em pattern}]The pattern word (the higher levels of the tree\end{description} \end{Desc} The encoding size of using each of the 4 possible encoding schemes is found. The sizes are packed into the 32-bit return value, a byte/size with scheme 0 in the least significant byte. The scheme identifiers are 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().