\hypertarget{APM_8c}{
\section{APM.c File Reference}
\label{APM_8c}\index{APM.c@{APM.c}}
}
This builds the modeling table for the Arithmetic Encoder. 

{\tt \#include \char`\"{}LDT/APM.h\char`\"{}}\par
{\tt \#include \char`\"{}APC.h\char`\"{}}\par


Include dependency graph for APM.c:\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=103pt]{APM_8c__incl}
\end{center}
\end{figure}
\subsection*{Functions}
\begin{CompactItemize}
\item 
unsigned int \hyperlink{APM_8c_a0}{APM\_\-build} (unsigned int $\ast$table, const unsigned int $\ast$f, int cnt)
\begin{CompactList}\small\item\em Creates an appropriately scaled probability table based on the the frequency distribution, {\em f\/}. \item\end{CompactList}\end{CompactItemize}


\subsection{Detailed Description}
This builds the modeling table for the Arithmetic Encoder. 

\begin{Desc}
\item[Author:]JJRussell - \href{mailto:russell@slac.stanford.edu}{\tt russell@slac.stanford.edu}\end{Desc}


\footnotesize\begin{verbatim}   CVS $Id: APM.c,v 1.2 2006/01/24 00:20:24 russell Exp $
\end{verbatim}
\normalsize


The modeling table is the template used to encode symbols. From an organizational viewpoint, it can be used by both the {\em encoding\/} side and the {\em decoding\/} side.

Both sides must agree on how a frequency distribution of symbols is transformed into a modeling table. There are two ways this can be accomplished.\begin{enumerate}
\item The encoder writes the modeling table with the data.\item The encoder writes the original frequency distribution and, amd the decoder, agrees to use the same rules to transform the frequency table to a modeling table\end{enumerate}


The minimum transformation would be to simple replace the frequency distribution with the cumulative sum of the frequencies. This scheme has two deficiencies

\begin{enumerate}
\item If the frequency distribution contains symbols with 0 probability of occuring {\em and\/} such symbols appear in an encoding stream, the will effectively be ignored.\item Since the cumulative sum of an arbitrary frequency distribution is itself an arbitrary number {\em and\/} the sum is used in a two divisions during the symbol encoding process, the model table is arbirtrarily renormalized such that the sum of the frequencies is precisely a power of 2, thus allowing the division to be replaced by a shift.\end{enumerate}


In addressing the first, if the user truly means that a particular symbol has 0 probability of occurring, it should be removed from the frequency table, and some lookup or translation mechanism should be used to translate the original symbol into the symbol to be encoded. This process is a straight-forward and precise prescription.

The second issue is not as straight-forward and precise. Given the limits of integer arthimetic, there are many ways an input frequency distribution can be scaled to sum to a power of 2. Therefore the routine APM\_\-build, by necessity, uses a particular scheme. This scheme was chosen because it is relatively fast in doing the transformation and can be easily shown to converge.

Another point of interest on the building of this table, is that it is not normalized to an arbitrary power of 2, but rather to that power of 2 that, after performing a 32-bit x 32-bit multiple, forces the significant digits to all be in the upper 32-bits. On the PPC, this allows the scaling and division to be replaced by one instruction, the multiple high unsigned word.

\subsection{Function Documentation}
\hypertarget{APM_8c_a0}{
\index{APM.c@{APM.c}!APM_build@{APM\_\-build}}
\index{APM_build@{APM\_\-build}!APM.c@{APM.c}}
\subsubsection[APM\_\-build]{\setlength{\rightskip}{0pt plus 5cm}unsigned int APM\_\-build (unsigned int $\ast$ {\em table}, const unsigned int $\ast$ {\em f}, int {\em cnt})}}
\label{APM_8c_a0}


Creates an appropriately scaled probability table based on the the frequency distribution, {\em f\/}. 

\begin{Desc}
\item[Returns:]The sum of the frequency distribution (not all that interesting)\end{Desc}
\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em table}]The table to be filled out. This must be an array of {\em cnt\/} + 2 values. The first entry is used to hold the number of entries in the table for integrity purposes, and the other extra entry is to hold the sum of the frequencies. \item[{\em f}]The frequency distribution of the symbols. There must be one entry, indexed by the symbol value, for each symbol \item[{\em cnt}]The number of entries (or the number of symbols, they are equivalent) in {\em f\/}.\end{description}
\end{Desc}
As a performance hint, symbols that have 0 probability of occurring should not be present in the frequency distribution. In this case, one should define a lookup table mapping only the non-zero values.

If symbols with a frequency of 0 appear in the input, this code will interpret such symbols as having a small, but finite, possibly of being present in an encoding scheme. Such symbols will be set to the lowest value probability, ensuring that they will get encoded.