Include a pre-rendered pdf version

[dirac-spec-errata.git] / arith.tex

\label{arithcoding}

This annex has three parts:
\begin{enumerate}
\item a description of the principles of arithmetic
coding,
\item a specification of the arithmetic decoding
engine used in Dirac, and
\item a description of a compatible arithmetic encoder.
\end{enumerate}

\subsection{Arithmetic coding principles (Informative)}

This section provides an introduction to the principles underlying arithmetic
coding. It briefly describes binary arithmetic coding, that is the coding of binary symbols, 
which is used in Dirac.

Arithmetic coding is an extremely powerful form of entropy coding, which can closely 
approximate the Shannon information limit for given data. Arithmetic encoding consists
 of a state machine that is fed with a sequence of symbols together with an estimate 
of each symbol’s probability. For each input symbol the arithmetic coding engine 
updates its state and output a number of coded bits. The number of output bits 
for each input symbol depends on the internal state and on the current probabilities
 the symbols that are coded, and can range from zero to many bits.

The variable number of coded bits output for each input symbol complicates 
the implementation but is essential to the optimal nature of arithmetic coding. Consider
a binary symbol $b$, with $p(b=\false)=p_0$ and $p(b=\true)=1-p_0$. The entropy of $b$
is the expected number of bits required to encode $b$, and is equal to
\[e(p_0)=p_0\log_2(1/p_0)+(1-p_0)\log_2(1/(1-p_0))\]

If $e(p_0)$ is plotted against $p_0$, it can be seen that if $p_0$ is not equal
to 0.5 exactly, $e(p_0)<1$. This means that an optimal binary entropy encoder
that operates symbol by symbol, cannot produce an output for every symbol.

\subsubsection{Interval division and scaling}
The fundamental idea of arithmetic coding is interval division and scaling. An
arithmetic code can be thought of as a single number lying in an interval 
determined by the sequence of values being coded. For simplicity, this discussion
describes binary arithmetic coding, but larger symbol alphabets can be treated
in an analogous manner.

Let us begin with the interval $[0,1)$, and suppose that we know (or have some 
estimate of) the probability of $\false$, $p_0$. Conceptually we divide the interval
into the intervals $[0,p0)$ and $[p_0,1)$. Suppose we code $\false$ as the
first symbol. In this case the interval is changed to $[0,p_0)$. If we code $\true$,
then the interval is changed to $[p_0,1)$. After coding a number of symbols we 
arrive at an interval $[low,high)$. To code the next symbol we partition this interval
into $[low,low+p_0(high-low))$ and $[low+p_0(high-low),high)$, and if the symbol is
$\false$ we choose the first interval, otherwise the second.

For any integer $N$, this process clearly partitions the interval $[0,1)$ into 
a set of disjoint intervals that correspond to all the input sequences of $N$ bits.
Identifying such a bit sequence is equivalent to choosing a value in the 
corresponding interval, and for an interval width $w$ that in general requires

\[\left\lceil\log_2(1/w)\right\rceil\]
bits. With static probabilities, on average,
\[w=p_0^{Np_0}(1-p_0)^{N(1-p_0)}\]
resulting in 
\[\left\lceil Ne(p_0)\right\rceil\]
being used, demonstrating the near-optimality of arithmetic coding.
Moreover, it is clearly possible to create an adaptive arithmetic code by
changing the estimate of $p_0$ based on previously coded data.

\subsubsection{Finite precision arithmetic}
As it stands, the procedure outlined in the previous section has a number of
drawbacks for practical application. Firstly, it requires unlimited precision
to scale the interval, which is not available in real hardware or software.
Secondly, it only produces an output when all values have been coded. These
problems are addressed by renormalisation and progressive output: periodically rescaling the
interval, and outputting the most significant bits of $low$ and $high$ whenever they agree.

For example, if we know that 
\begin{eqnarray*}
low &=& b0xyz...\\
high & = &b0pqr...
\end{eqnarray*}
 then we can output $0$, since this must prefix any value lying in the interval, 
and shift $low$ and $high$ to get $low=bxyz...$ and $high=bpqr...$.
This has the effect of doubling the interval from 0 ($x\mapsto 2x$). Likewise if 
\begin{eqnarray*}
low &=& b1xyz...\\
high & = &b1pqr...
\end{eqnarray*}
we can output $1$ and shift to get
$low=bxyz...$ and $high=bpqr...$ again: this is equivalent to doubling the interval
from 1 ($x\mapsto 2x-1$).

One problem remains: suppose the interval resolutely sits on the fence, straddling
$\dfrac{1}{2}$ whilst getting smaller and smaller, with the most 
significant bits of low and high staying as 0 and 1 respectively. 
In this case, when the straddle is finally resolved, $low$ and $high$ will
both be of the form $b10000...xyz$ or $b01111...pqr$. 

The resolution strategy is to again rescale $low$ and $high$, but this time
double from $\dfrac{1}{2}$ (i.e. $x\mapsto 2x-\dfrac{1}{2}$), and keep a count of the number $k$
of times this is done, as this is the number of carry bits that are
required. When the straddle is resolved as 1, then 1 followed by $k$ zero bits is 
output, otherwise 0 followed by k 1s is output. This ensures that the
output exactly represents the small straddling interval.

A decoder can determine a symbol as soon as it has sufficient bits to distinguish
whether a value lies in one interval or another. If constraints are placed on the
 size of the smallest interval before
renormalisation (for example, by renormalising often enough and by having a fixed
smallest allowable probability), then this can be accomplished within a fixed word width.

\subsubsection{Symbol probability estimation}
\begin{comment}
The effectiveness of arithmetic coding is critically dependent on the accurate estimation of symbol probabilities. This 
might be achieved by counting the number of False symbols, n0, and True symbols, n1, that have previously been 
coded (or decoded), and estimating the probability of zero as: 
p0 = n0/(n0+n1) 
This requires maintaining the values of the two counts, n0 and n1, and performing some arithmetic (including division) 
every time a symbol is coded or decoded, in order to estimate the probability. Usually the values of n0 and n1 are both 
initialized to one for the first symbol, giving an initial probability estimate of 0.5. 
With this method of probability estimation if False is coded the probability becomes  
  p0=n0+1/(n0+n1+1),  
and if True is coded the probability becomes 
   p0=n0/(n0+n1+1).  
In other words:  
?  If False is coded the probability update is: p0 += (1-p0)/(n0+n1+1) 
?  else, if True is coded, the probability update is: p0 -= p0/(n0+n1+1) 
In VC-2 the probability estimate is simplified by assuming an estimate for the total number of symbols coded, t, as a 
function of probability itself. That is: 
n0+n1 ˜ g(p0) 
With this simplifying assumption the probability update process becomes:  
?  If False is coded:  p0 += (1-p0)/( g(p0)+1) 
?  else, if True is coded: p0 -= p0/( g(p0)+1) 
Many choices would be possible for the definition of  ?(p0). For VC-2 g(p0) is given by: 
g(p0) ˜ 2v
  where v=8-4.log2(128.(1-2.abs(p0-0.5)))/7 
With this choice of g(p0), (n0+n1) is assumed to be 16 when p0=0.5 and 256 when p0=1/256 or 255/256. 
Assuming the total number of symbols coded is a function of probability significantly simplifies the implementation. 
The probability update can be achieved with a single arithmetic operation (addition or subtraction) and a pair of 
lookup tables. That is:  
?  If False is coded: p0 += LUT_False[p0]  
?  else, if True is coded: p0 -= LUT_True[p0] 
In the VC-2 arithmetic codec probability is represented as a 16 bit unsigned integer (that is the range [0,65536)   SMPTE xxxx:2007        20/12/2007 
       
Page 119 of 150 pages 
represents the range of probabilities [0,1) ). To reduce the size of the lookup table only the 8 most significant bits of p0 
are used as the index to the lookup table. The definition of LUT_True is: 
LUT_True(prob): 
   lut_input &= 0xFF00 
   if (lut_input >= 0x8000) p0 = lut_input/65536.0 
   else p0 = (lut_input+256)/65536.0 
   v = 8.0-4.0*log2(128.0*(1.0-2.0*abs(p0-0.5)))/7.0 
   t = 2**v 
   return round(lut_input+128)/t+1) 
Here prob is the 16bit representation of probability used in the VC-2 codec, the return value is in the same format. 
The 8 LSBs of prob are ignored allowing the use of a 256 entry lookup table. p0 is calculated using a dead-zone 
quantiser. The lookup table for False symbols is calculated similarly. It turns out that LUT_False is the mirror image 
of LUT_True so the same table can be used for both.  
Note: this pseudocode does not conform to the definitions in section 4 because it contains floating point numbers, 
floating point division and the round function. 
\end{comment}

\subsection{Arithmetic decoding engine}
\label{arithengine}

This section is a normative specification of the operation of the arithmetic
decoding engine and the processes for using it to extract binary values from coded streams.

The arithmetic decoding engine shall consist of two elements: 
\begin{enumerate}
\item a collection of state variables representing the state of the arithmetic 
decoder (Section~\ref{initarith})
\item a function for extracting binary values from the decoder 
and updating the decoder state (Section~\ref{arithreadbool})
\end{enumerate}

\subsubsection{State and contexts}
\label{stateandcontexts}

The arithmetic decoder state shall consist of the following decoder state variables:

\begin{itemize}
\item $\ALow$, an integer representing the beginning of the current coding interval.
\item $\ARange$, an integer representing the size of the current coding interval.
\item $\ACode$, an integer within the interval from $\ALow$ to $\ALow+\ARange-1$, determined from the encoded bitstream.
\item $\ABitsLeft$, a decrementing count of the number of bits yet to be read in
\item $\AContexts$, a map of all the contexts used in the Dirac decoder.
\end{itemize}

A context $context$ shal be a 16 bit unsigned interger value which encapsulates
the probability of zero symbol in the stream, represented as  such that
\[0<context[prob0]\leq\text{0xFFFF}\]

Contexts shall be accessed by decoding functions via a context label passed to the function.

\subsubsection{Initialisation}
\label{initarith}

At the beginning of the decoding of any data unit, the arithmetic
decoding state shall be initialised as follows:

\begin{pseudo}{initialise\_arithmetic\_decoding}{ctx\_labels}
\bsCODE{\ALow = \text{0x0}}
\bsCODE{\ARange =\text{0xFFFF}}
\bsCODE{\ACode =\text{ 0x0}}
\bsFOR{i=0}{15}
    \bsCODE{\ACode <<= 1}
    \bsCODE{\ACode+= read\_bitb()} 
\bsEND
\bsCODE{init\_context\_probs(ctx\_labels)}
\end{pseudo}

The $init\_context\_probs()$ process shall be defined as follows:

\begin{pseudo}{init\_context\_probs}{ctx\_labels}
\bsFOR{i=0}{\length(ctx\_labels)-1}
  \bsCODE{\AContexts[ctx\_labels[i]]=\text{0x8000}}
\bsEND
\end{pseudo}

\begin{informative}
The value 0x8000 represents 1/2 or equal likelihood for binary values.
\end{informative}

\subsubsection{Data input}
\label{inputarith}

The arithmetic decoding process shall access data in a contiguous block of bytes
whose size is equal to $\ABitsLeft$, this value having been set prior to decoding
the block. The bits in this block shall be sufficient to allow for the
decoding of all coefficients. However, the specification of arithmetic
decoding operations in this section may occasionally cause further bits to be read,
even though they are not required for determining decoded values. For this
reason the bounded-block read function $read\_bitb()$ (Section~\ref{blockreadbit})
shall be used for data access.

Since the length of arithmetically coded data elements is given in bytes within the Dirac
stream, there may be bits left unread when all values have been extracted. These
shall be flushed as described in Section~\ref{blockreadbit}. Since arithmetically coded
blocks are byte-aligned and a whole number of bytes, this aligns data input with the
beginning of the byte after the arithmetically coded data i.e.\ at the end of the
data chunk. $flush\_inputb()$ shall always be called at the end of decoding an
arithmetically coded data element.

\subsubsection{Decoding boolean values}
\label{arithreadbool}

The arithmetic decoding engine is a multi-context, adaptive binary
arithmetic decoder, performing binary renormalisation and producing
binary outputs. For each bit decoded, the semantics of the relevant
calling decoder function shall determine which contexts are passed to the
arithmetic decoding operations. 

This section defines the operation of the $read\_boola()$ function
for extracting a boolean value from the Dirac stream. The function 
shall be defined as follows:

\begin{pseudo}{read\_boola}{context\_label}
\bsCODE{prob\_zero=\AContexts[context\_label]}
\bsCODE{count = \ACode-\ALow}
\bsCODE{range\_times\_prob = (\ARange * prob\_zero)\gg 16}
\bsIF{ count >= range\_times\_prob }
  \bsCODE{value = \true}
  \bsCODE{\ALow +=  range\_times\_prob}
  \bsCODE{\ARange -= range\_time\_prob}
\bsELSE
  \bsCODE{value = \false}
  \bsCODE{\ARange = range\_times\_prob}
\bsEND
\bsCODE{update\_context(\AContexts[context\_label],value)}{\ref{contextupdate}}
\bsWHILE{\ARange<=\text{0x4000}}
    \bsCODE{renormalise()}{\ref{renormalisation}}
\bsEND
\bsRET{value}
\end{pseudo}

\begin{informative}
The function scales the probability of the symbol 0 or $\false$ from the decoding context
so that if this probability were $1$, then the interval would equal that between
 $\ALow$ and 
 \[high=\ALow+\ARange-1\]
and $count$ is set to the normalised cut-off between 0/$\false$ and 1/$\true$ 
within this range.
\end{informative}

\subsubsection{Renormalisation}
\label{renormalisation}

Renormalisation shall be applied to stop the arithmetic decoding 
engine from losing accuracy. Renormalisation shall be
 applied while the range is less than or equal to a quarter of 
 the total available 16-bit range ($\text{0x4000}$). 

Renormalisation shall double the interval and read a bit into the codeword.
The $renormalise()$ function shall be defined as follows:

\begin{pseudo}{renormalise}{}
\bsIF{((\ALow+\ARange-1)\wedge\ALow) >= \text{0x8000}}
    \bsCODE{\ACode \wedge= \text{0x4000}}
    \bsCODE{\ALow \wedge= \text{0x4000}}
\bsEND
\bsCODE{\ALow  <<=  1}
\bsCODE{\ARange  <<=  1}
\bsCODE{\ALow \&= \text{0xFFFF}}
\bsCODE{\ACode <<= 1}
\bsCODE{\ACode+= read\_bitb()}
\bsCODE{\ACode \&= \text{0xFFFF}}
\end{pseudo}

\begin{informative}
For convenience let $low=\ALow$ and $high=\ALow+\ARange-1$ 
represent the upper and lower bounds of the interval. If the
range is $<=\text{0x4000}$ then
one of three possibilities must obtain:
\begin{enumerate}
\item the msbs of $low$ and $high$ are both 0
\item the msbs of $low$ and $high$ are both 1
\item $low=b01...$, $high=b10....$,  and the interval straddles the half-way point 0x8000. 
\end{enumerate}

The  renormalisation
process has the effect that: in case 1, the interval $[low,high]$ is doubled from 0 (i.e. $x\mapsto 2*x$); in case 2 it is doubled from 1 (i.e. $x\mapsto 2*x-1$); and in case 3 it is doubled from 1/2 (i.e. $x\mapsto 2x-0.5$). 
\end{informative}

\subsubsection{Updating contexts}
\label{contextupdate}

Context probabilities shall be updated according to a probability look-up table
$\ALUT$, which supplies a value for decrementing
or incrementing the probability of zero based on the first 
8 bits of its current value, according to Table \ref{table:lut}.

The $update\_context()$ process shall be defined as follows:

\begin{pseudo}{update\_context}{ctx\_prob,value}
\bsIF{value==\true}
    \bsCODE{ctx\_prob -= \ALUT[ctx\_prob \gg 8]}{Table \ref{table:lut}}
\bsELSE
    \bsCODE{ctx\_prob += \ALUT[255-(ctx\_prob \gg 8)]}{Table \ref{table:lut}}
\bsEND
\end{pseudo}

The lookup table used for updating context probabilities shall be as defined in 
Table \ref{table:lut}. below. The lookup table entries are arranged in raster scan order with
rows of thirteen entries. The entry corresponding to index zero is in the
top left hand corner, the index increments by one from left to right and by 
thirteen from top to bottom, the entry corresponding to index 255 is on the right hand 
side of the last row. 
\begin{table}[!ht]
\centering
\begin{tabular}{|cccccccc|}
\hline
\multicolumn{8}{|c|}{{\bf \ALUT[] (indexes 0 to 255)}} \\
\hline
             0,&    2,&    5,&    8,&   11,&   15,&   20,&   24,\\
            29,&   35,&   41,&   47,&   53,&   60,&   67,&   74,\\
            82,&   89,&   97,&  106,&  114,&  123,&  132,&  141,\\
           150,&  160,&  170,&  180,&  190,&  201,&  211,&  222,\\
           233,&  244,&  256,&  267,&  279,&  291,&  303,&  315,\\
           327,&  340,&  353,&  366,&  379,&  392,&  405,&  419,\\
           433,&  447,&  461,&  475,&  489,&  504,&  518,&  533,\\
           548,&  563,&  578,&  593,&  609,&  624,&  640,&  656,\\
           672,&  688,&  705,&  721,&  738,&  754,&  771,&  788,\\
           805,&  822,&  840,&  857,&  875,&  892,&  910,&  928,\\
           946,&  964,&  983,& 1001,& 1020,& 1038,& 1057,& 1076,\\
          1095,& 1114,& 1133,& 1153,& 1172,& 1192,& 1211,& 1231,\\
          1251,& 1271,& 1291,& 1311,& 1332,& 1352,& 1373,& 1393,\\
          1414,& 1435,& 1456,& 1477,& 1498,& 1520,& 1541,& 1562,\\
          1584,& 1606,& 1628,& 1649,& 1671,& 1694,& 1716,& 1738,\\
          1760,& 1783,& 1806,& 1828,& 1851,& 1874,& 1897,& 1920,\\
          1935,& 1942,& 1949,& 1955,& 1961,& 1968,& 1974,& 1980,\\
          1985,& 1991,& 1996,& 2001,& 2006,& 2011,& 2016,& 2021,\\
          2025,& 2029,& 2033,& 2037,& 2040,& 2044,& 2047,& 2050,\\
          2053,& 2056,& 2058,& 2061,& 2063,& 2065,& 2066,& 2068,\\
          2069,& 2070,& 2071,& 2072,& 2072,& 2072,& 2072,& 2072,\\
          2072,& 2071,& 2070,& 2069,& 2068,& 2066,& 2065,& 2063,\\
          2060,& 2058,& 2055,& 2052,& 2049,& 2045,& 2042,& 2038,\\
          2033,& 2029,& 2024,& 2019,& 2013,& 2008,& 2002,& 1996,\\
          1989,& 1982,& 1975,& 1968,& 1960,& 1952,& 1943,& 1934,\\
          1925,& 1916,& 1906,& 1896,& 1885,& 1874,& 1863,& 1851,\\
          1839,& 1827,& 1814,& 1800,& 1786,& 1772,& 1757,& 1742,\\
          1727,& 1710,& 1694,& 1676,& 1659,& 1640,& 1622,& 1602,\\
          1582,& 1561,& 1540,& 1518,& 1495,& 1471,& 1447,& 1422,\\
          1396,& 1369,& 1341,& 1312,& 1282,& 1251,& 1219,& 1186,\\
          1151,& 1114,& 1077,& 1037,&  995,&  952,&  906,&  857,\\
           805,&  750,&  690,&  625,&  553,&  471,&  376,&  255\\
\hline
\end{tabular}
\caption{Look-up table for context probability adaptation}
\label{table:lut}
\end{table}

\subsubsection{Efficient implementation (Informative)}
\label{arithdecopts}
The decoding operations defined in the preceding sections correspond closely
to the descriptions of arithmetic coding principles contained in the academic
literature. More efficient implementations are certainly possible, both for
hardware and software. This section describes some simple techniques.

\paragraph{Change of variables}$\ $\newline
There is in fact no need for the decoder to keep track of both $\ALow$ and
$\ACode$, since the test is made against the difference of these values, i.e.
be defined as:
\[\ACodeMinusLow = \ACode-\ALow\]

So only this difference variable need be tracked. Since $\ALow$ is initialised
to zero, $\ACodeMinusLow$ is initialised just like $\ACode$. The $read\_boola$ 
then is re-written as:

\begin{pseudo}{read\_boola}{context\_label}
\bsCODE{prob\_zero=\AContexts[context\_label]}
\bsCODE{range\_times\_prob = (\ARange * prob\_zero)\gg 16}
\bsIF{ \ACodeMinusLow >= range\_times\_prob }
  \bsCODE{value = \true}
  \bsCODE{\ACodeMinusLow -=  range\_times\_prob}
  \bsCODE{\ARange -= range\_time\_prob}
\bsELSE
  \bsCODE{value = \false}
  \bsCODE{\ARange = range\_times\_prob}
\bsEND
\bsCODE{update\_context(\AContexts[context\_index],value)}{\ref{contextupdate}}
\bsWHILE{\ARange<=\text{0x4000}}
    \bsCODE{renormalise()}{\ref{renormalisation}}
\bsEND
\bsRET{value}
\end{pseudo}

The $renormalise()$ function is very greatly simplified, since all the masking
and bit-twiddling is eliminated to leave:

\begin{pseudo}{renormalise}{}
\bsCODE{\ACodeMinusLow  <<=  1}
\bsCODE{\ARange  <<=  1}
\bsCODE{\ACodeMinusLow+= read\_bitb()}
\end{pseudo}

\paragraph{Bytewise operation}$\ $\newline
Accessing data bit by bit is also inefficient, so it is useful to look ahead and
read in bytes into $\ACodeMinusLow$ or $\ACode$ in advance. So, for example,
$\ACodeMinusLow$ could be initialised to the first 4 bytes of the bitstream
and $\ARange$ initialised to 0xFFFF0000, and all calulations shifted up by 16 bits.
Then $read\_boola$ can be re-written as:

\begin{pseudo}{read\_boola}{context\_label}
\bsCODE{prob\_zero=\AContexts[context\_label]}
\bsCODE{range\_times\_prob = ((\ARange\gg16) * prob\_zero) \& \text{0xFFFF0000}}
\bsIF{ \ACodeMinusLow >= range\_times\_prob }
  \bsCODE{value = \true}
  \bsCODE{\ACodeMinusLow -=  range\_times\_prob}
  \bsCODE{\ARange -= range\_time\_prob}
\bsELSE
  \bsCODE{value = \false}
  \bsCODE{\ARange = range\_times\_prob}
\bsEND
\bsCODE{update\_context(\AContexts[context\_index],value)}
\bsWHILE{\ARange<=\text{0x40000000}}
    \bsCODE{renormalise()}
\bsEND
\bsRET{value}
\end{pseudo}

and the renormalisation loop uses a counter, starting at 16, to input bits in 2-byte
chunks:

\begin{pseudo}{renormalise}{}
\bsCODE{\ACodeMinusLow  <<=  1}
\bsCODE{\ARange  <<=  1}
\bsCODE{\ACounter -= 1}
\bsIF{\ACounter == 0 }
  \bsCODE{\ACodeMinusLow+= read\_uint\_lit(2)}
  \bsCODE{\ACounter = 16}
\bsEND
\end{pseudo}

\paragraph{Look-up table}$\ $\newline
In software it makes sense to use a modified probability LUT containing 512 elements, in
which each even element is the negative increment to $prob\_zero$ if 0 is coded, and each
odd element is the positive increment to $prob\_zero$ is 1 is coded. This means that access
to the LUT will always be in a very local area whatever value is coded, whereas the basic
structure will require either position $p$ or $255-p$ to be accessed depending on the value.

\subsection{Arithmetic encoding (Informative)}

This document only normatively defines the decoding of arithmetic coded data. 
However whilst it is clearly vital that an encoding process matches the decoding
process, it is not entirely straightforward to derive an implementation of the
encoder by only looking only at the decoder specification. Therefore this
informative section describes a possible implementation for an
arithmetic encoder that will produce output that is decodeable by
the Dirac arithmetic decoder. This section is best read in conjunction with
Annex \ref{arithengine}.

\subsubsection{Encoder variables}

An arithmetic encoder requires the following unsigned integer variables, or
some mathematically equivalent set:
\begin{itemize}
\item $low$, a value indicating the bottom of the encoding interval,
\item $range$, a value indicating the width of the encoding interval,
\item $carry$, a value tracking the number of unresolved ``straddle" conditions
(described below), and
\item a set of 16-bit probability context probabilities, as described in Annex~\ref{arithdecoding}.
\end{itemize}

The process for updating context probabilities, used for coding values,  
is described in Annex \ref{contextupdate}

A Dirac binary arithmetic encoder implementation codes a set of data in three stages:
\begin{enumerate}
\item initialisation,
\item processing of all values, and 
\item flushing.
\end{enumerate}

\subsubsection{Initialisation}

Initialisation of the arithmetic encoder is very simple -- the internal variables are
set as:
\begin{eqnarray*}
low&=&\text{0x0} \\
range&=&\text{0xFFFF} \\
carry&=&0
\end{eqnarray*}

With 16 bit accuracy, 0xFFFF corresponds to an interval width value of (almost) 1. All
context probabilities are initialised to probability $1/2$ (0x8000).

\subsubsection{Encoding binary values}
\label{arithwritebool}
The encoding process for a binary value must precisely mirror
that for the decoding process (Annex \ref{arithreadbool}). In
particular the interval variables $low$ and $range$ must be
updated in the same way.

Coding a boolean value consists of three sub-stages (in order): 
\begin{enumerate}
\item scaling the interval $[low,low+range)$,
\item updating contexts, and
\item renormalising and outputting data.
\end{enumerate}

\paragraph{Scaling the interval}$\ $\newline
The integer interval $[low,low+range)$ represents the real interval
\[[l,h)=[low/2^{16},(low+range)/2^{16})\]
 In a given context with label $label$, the probability of zero can be extracted as 
\[prob\_zero=\AContexts[label]\]

If $0$ is to be encoded, the real interval $[l,h)$ should be rescaled so that $l$ is unchanged and the width $r=h-l=range/2^{16}$ is scaled to $r*p_0$ where $p_0=prob\_zero/2^{16}$.

This operation is approximated by setting
\[range=(range*prob\_zero)\gg 16\]

If 1 is to be encoded, $[l,h)$ should be rescaled so that $h$ is
unchanged and $r$ is scaled to $(1-p0)*r$. This operation is
approximated by setting
\begin{eqnarray*}
low &+= & (range*prob\_zero)\gg 16 \\
range & -= & (range*prob\_zero)\gg 16
\end{eqnarray*}

\paragraph{Updating contexts}$\ $\newline
Contexts are updated in exactly the same way as the 
decoder (Annex \ref{contextupdate}).

\paragraph{Renormalisation and output}$\ $\newline
Renormalisation must cause $low$ and $range$ to be modified exactly
as in the decoder (Annex \ref{renormalisation}). In addition, 
during renormalisation bits are output when $low$ and $low+range$ 
agree in their msbs, taking into account carries accumulated when a
straddle condition is accumulated. 

In pseudocode, this is as follows:

\begin{pseudo*}
\bsWHILE{range<=\text{0x4000}}
    \bsIF{((low+range-1)\wedge low)>=\text{0x8000}}
        \bsCODE{low \wedge= \text{0x4000}}
        \bsCODE{carry+=1}
    \bsELSE
        \bsCODE{write\_bit( low\&\text{0x8000} )}
        \bsWHILE{ carry>0}
            \bsCODE{write\_bit( !low\&\text{0x8000} )}
            \bsCODE{carry -= 1}
        \bsEND
    \bsEND
    \bsCODE{low  <<=  1}
    \bsCODE{range  <<=  1}
    \bsCODE{low \&= \text{0xFFFF}}
\bsEND
\end{pseudo*}

\paragraph{Flushing the encoder}$\ $\newline
After encoding, there may still be insufficient bits for a decoder
to determine the final few encoded symbols, partly because further 
renormalisation is required -- for example, msbs may agree but the range
may still be larger than 0x4000) -- and partly because there may be 
unresolved carries.

A four-stage process will adequately flush the encoder:
\begin{enumerate}
\item output remaining resolved msbs,
\item resolve remaining straddle conditions,
\item flush carry bits, and
\item byte align the output with padding bits.
\end{enumerate}

The remaining msbs are output as follows:

\begin{pseudo*}
\bsWHILE{(low+range-1)\wedge low<\text{0x8000}}
    \bsCODE{write\_bit( low\&\text{0x8000} !=\text{0x0} )}
    \bsWHILE{ carry>0}
        \bsCODE{write\_bit( (low\&\text{0x8000})==\text{0x0} )}
        \bsCODE{carry -= 1}
    \bsEND
    \bsCODE{low  <<=  1}
    \bsCODE{low \&= \text{0xFFFF}}
    \bsCODE{range  <<=  1}
\bsEND
\end{pseudo*}

Remaining straddles can then be resolved by:

\begin{pseudo*}
\bsWHILE{ (low \& \text{0x4000}) \text{ and } (((low+range-1) \& \text{0x4000})!=\text{0x0})}
    \bsCODE{carry+=1}
    \bsCODE{low \wedge= \text{0x4000}}
    \bsCODE{low  <<=  1}
    \bsCODE{range  <<=  1}
    \bsCODE{low \&= \text{0xFFFF}}
\bsEND
\end{pseudo*}

Carry bits can be discharged by picking a resolution of
the final straddles:

\begin{pseudo*}
\bsCODE{write\_bit(low \& \text{0x4000}!=\text{0x0})}
\bsFOR{c=0}{carry}
    \bsCODE{write\_bit((low \& \text{0x4000})==\text{0x0})}
\bsEND
\end{pseudo*}

Finally, 0-7 padding bits are added to the encoded output to make
a whole number of bytes. These are not necessary for decoding, but
for stream compliance.

\subsection{Efficient implementation}

Some similar techniques to those described in Section~\ref{arithdecopts} can be
used in the encoder to speed up operation. 

\paragraph{Bytewise operation}$\ $\newline
It is not necessary to output bits one by one. Instead, $low$ may be allowed to
accumulate bits at the lower end and output them when a byte has accumulated. If the
last bit determined was a 1, this 1 must be carried to the previous byte, so
renormalisation becomes:

\begin{pseudo*}
\bsWHILE{range<=\text{0x4000}}
    \bsCODE{low  \ll=  1}
    \bsCODE{range  \ll=  1}
    \bsCODE{counter -= 1}
    \bsIF{counter==0}
      \bsIF{low<=1\ll 24 \text{ and } low+range> 1\ll24}
        \bsCODE{carry+=1}
      \bsELSE
        \bsIF{low<1\ll 24}
            \bsWHILE{carry}
              \bsCODE{data[pos]=\text{0xFF}}
              \bsCODE{carry -= 1}
              \bsCODE{pos += 1}
            \bsEND
        \bsELSE
            \bsCODE{data[pos-1] += 1}
            \bsWHILE{carry}
              \bsCODE{data[pos]=\text{0x00}}
              \bsCODE{carry -= 1}
              \bsCODE{pos += 1}
            \bsEND
        \bsEND
        \bsCODE{data[pos](low\gg16}
        \bsCODE{pos += 1}
        \bsCODE{low \&= \text{0xFFFF}}
      \bsEND
      \bsCODE{counter=8}
    \bsEND
\bsEND
\end{pseudo*}

\paragraph{Overlap and add}$\ $\newline
Renormalisation can be simplified still further by observing that carries occur if and only
if the top byte of $low$ becomes 0xFF. In this case a carried 1 would propagate up multiple
bytes, turning 0xFFs into 0x00s. So it is possible to store the top two bytes of $low$ (i.e.
bit 24 containing the carry bit and the next byte) and do an overlap and add at the end to correctly 
propagate values back to the beginning. I.e. renormalisation becomes:

\begin{pseudo*}
\bsWHILE{range<=\text{0x4000}}
    \bsCODE{low  \ll=  1}
    \bsCODE{range  \ll=  1}
    \bsCODE{counter -= 1}
    \bsIF{counter==0}
      \bsCODE{low\_list[pos] = low\gg16}
      \bsCODE{pos+=1}
      \bsCODE{counter=8}
      \bsCODE{low \&= \text{0xFFFF}}
    \bsEND
\bsEND
\end{pseudo*}

At the end of coding all values, a flush function will complete $low\_list$ for remaining values
and perform the overlap and add:

\begin{pseudo*}
\bsCODE{low += 1}
\bsCODE{low \ll= counter}
\bsCODE{low\_list[pos] = (low \gg 16)\&\text{0xFFFF}}
\bsCODE{pos += 1}
\bsCODE{low\_list[pos] = (low \gg 8)\&\text{0xFFFF}}
\bsCODE{pos += 1}
\bsCODE{data[pos-1] = low\_list[pos-1] \& \text{0xFF}}
\bsCODE{data[pos-2] = low\_list[pos-2] \& \text{0xFF}}
\bsFOR{i=0}{pos-3}
  \bsCODE{low\_list[pos-3-i] += low\_list[pos-2-i]\gg8}
  \bsCODE{data[pos-3-i] = low\_list[pos-3-i]\&\text{0xFF}}
\bsEND
\end{pseudo*}