arith-encoder.tex

   1 This appendix provides three things:
   2 \begin{itemize}
   3 \item a description of the principles of arithmetic
   4 coding
   5 \item a specification of the arithmetic decoding
   6 engine used in Dirac
   7 \item a description of a compatible arithmetic encoder
   8 \end{itemize}
   9
  10 \begin{informative*}
  11 \subsection{Arithmetic coding principles (INFORMATIVE)}
  12
  13 This section provides an introduction to the principles underlying arithmetic
  14 coding. Since arithmetic coding is very extensively described in published literature,
  15 this section is necessarily brief: for more information, Alasdair Moffat's
  16 article ''Arithmetic coding revisited'' is recommended.
  17
  18 Arithmetic coding is extremely powerful and can approach the Shannon information
  19 limit for given data. Arithmetic encoding consists of an asynchronous state machine,
  20 in which data
  21 is fed to an arithmetic encoding engine, together with an estimate of its
  22 probability, and the encoder outputs bits. It is asynchronous because data
  23 input does not trigger any output directly, but changes the state of the
  24 engine. When a certain state is reached a variable amount of output is produced.
  25
  26 This asynchronous nature makes arithmetic coding trickier to implement
  27 than Variable-Length Codes (VLCs) but is essential to its optimal nature. Consider
  28 a binary symbol $b$, with $p(b=0)=p_0$ and $p(b=1)=1-p_0$. The entropy of $b$
  29 is the expected number of bits required to encode $b$, and is equal to
  30 \[e(p_0)=p_0\log_2(1/p_0)+(1-p_0)\log(1/(1-p_0))\]
  31
  32 If $e(p_0)$ is plotted against $p_0$, it can be seen that if $p_0$ is not equal
  33 to 0.5 exactly, $e(p_0)<1$. This means that an optimal binary entropy encoder
  34 that operates symbol by symbol, cannot produce an output for every symbol - i.e.
  35 it must operate asynchronously.
  36
  37 \subsubsection{Interval division and scaling}
  38 The fundamental idea of arithmetic coding is interval division and scaling. An
  39 arithmetic code can be thought of as a single number lying in an interval
  40 determined by the sequence of values being coded. For simplicity, this discussion
  41 describes binary arithmetic coding, but larger symbol alphabets can be treated
  42 in an analogous manner.
  43 [TBC]
  44
  45 \subsubsection{Finite precision arithmetic}
  46
  47 \subsection{Arithmetic encoding (INFORMATIVE)}
  48 \end{informative*}
  49
  50 This document only specifies the decoding of arithmetic coded data.
  51 However whilst it is clearly vital that an encoding process matches the decoding
  52 process, it is not straightforward to derive an implementation of the
  53 encoder by only looking only at the decoder specification. Therefore this
  54 informative section describes a possible implementation for an
  55 arithmetic encoding engine that will produce output decodeable by
  56 the Dirac arithmetic decoding engine.
  57
  58 \subsubsection{Encoder variables}
  59
  60 An arithmetic encoder would require the following integer variables:
  61
  62 \begin{itemize}
  63 \item $\text{low}$, a value indicating the bottom of the encoding interval
  64 \item $\text{high}$, a value indicating the top of the encoding interval
  65 \item $\text{underflow}$, a value tracking the number of unresolved ``straddle" conditions
  66 (described below)
  67 \end{itemize}
  68
  69 A Dirac binary arithmetic encoder implementation will code a set of data in three stages:
  70
  71 \begin{enumerate}
  72 \item Initialisation
  73 \item Processing of all values
  74 \item Flushing
  75 \end{enumerate}
  76
  77 \subsubsection{Initialisation}
  78
  79 Initialisation of the arithmetic encoder is very simple -- the internal variables are
  80 set as:
  81
  82 \begin{eqnarray*}
  83 \text{low}&=&\text{0x0} \\
  84 \text{high}&=&\text{0xFFFF} \\
  85 \text{underflow}&=&0
  86 \end{eqnarray*}
  87
  88 (Note that although the arithmetic decoder initialises $\AHigh$ to be 0x0000 in decoding the first
  89 value, $shift\_all\_bits()$ is called which will set $\AHigh$ to 0xFFFF and $\ACode$ to the first
  90 16 bits in the stream.)
  91
  92 \subsubsection{Processing of binary values}
  93 \begin{comment}
  94 The arithmetic coding processBits are encoded one at a time based on an estimated probability
  95 embodied in a ``context''. As with decoding, the context simply relates to
  96 counts of the number of zeros or ones that have been previously encoded.
  97
  98 A possible algorithm for encoding a single bit, given a context, is:
  99
 100 Encode Binary Arithmetic Coded Bit
 101 \begin{verbatim}
 102 write_ba(symbol, context):
 103     while ( ((high&0x4000)==0x0) and
 104            ((low&0x4000)==0x4000) ):
 105         code ^= 0x4000
 106         high ^= 0x4000
 107         low ^= 0x4000
 108         shift_bit_out()
 109     weight = context[0] + context[1]
 110     scaler = (0x10000+weight//2)//weight
 111
 112     probability0 = context[0]*scaler
 113     range = high-low+1
 114     range_x_prob = (range * probability0)>>16
 115     if ( symbol )
 116         context[1] += 1
 117         low = low + range_x_prob
 118     else
 119         context[0] += 1
 120         high = low  + range_x_prob - 1
 121     if ( (context[0] + context[1]) > 255 ):
 122         #Halve counts in the context
 123         context[0] >> 1
 124         context[0] += 1
 125         context[1] >> 1
 126         context[1] += 1
 127     while (((high&0x8000)==0x0) and ((low&0x8000)==0x0)):
 128         output_bits()
 129         shift_bit_out()
 130 \end{verbatim}
 131
 132 Shift Bit Out
 133 \begin{verbatim}
 134 shift_bit_out():
 135     high << 1
 136     high &= 0xFFFF
 137     high += 1
 138     low << 1
 139     low &= 0xFFFF
 140 \end{verbatim}
 141
 142 Output Bits
 143 \begin{verbatim}
 144 output_bits():
 145     write_bit( (high&0x8000)==0x8000 )
 146     while ( underflow > 0 ):
 147         write_bit( high&0x8000)==0x0 )
 148         underflow -= 1
 149 \end{verbatim}
 150
 151 Flush Encoder
 152 \begin{verbatim}
 153 flush_encoder():
 154
 155     write_bit( (high&0x4000)==0x4000 )
 156     while ( underflow >= 0 ):
 157         write_bit( high&0x4000)==0x0 )
 158         underflow -= 1
 159 \end{verbatim}
 160
 161 Where the ``write\_bit(bit)'' function outputs a single bit.
 162 \end{comment}
 163
 164
 165 \subsection{Arithmetic decoding engine}
 166
 167 This section is a normative specification of the operation of the arithmetic
 168 decoding engine.
 169
 170 \label{arithdecodingengine}
 171
 172 This section specifies the arithmetic decoding engine and
 173 processes for using it to extract data from coded streams.
 174
 175 The arithmetic decoding engine consists of two elements:
 176
 177 \begin{itemize}
 178 \item a collection of state variables representing the state of the arithmetic
 179 decoder (Section \ref{initarith})
 180 \item a function for extracting binary values from the decoder
 181 and updating the decoder state (Section \ref{extractarith})
 182 \end{itemize}
 183
 184 \subsubsection{State and contexts}
 185 \label{arithcontexts}
 186
 187 The arithmetic decoder state consists of the following decoder state variables:
 188
 189 \begin{itemize}
 190 \item $\ALow$, an integer representing the beginning of the current coding interval
 191 \item $\ARange$, an integer representing the size of the current coding interval
 192 \item $\ACode$, an integer within the interval from $\ALow$ to $\AHigh$, determined from the encoded bitstream
 193 \item $\ABitsLeft$, a decrementing count of the number of bits yet to be read in
 194 \item $\AContexts$, a map of all the contexts used in the Dirac decoder
 195 \end{itemize}
 196
 197 A context $context$ is an integer array with a single value which encapsulates
 198 the probability of zero in that context represented as a 16 bit number, such that
 199 \[0<context[prob0]<\text{0xFFFF}\]
 200
 201 Contexts are accessed by decoding functions via the indices defined in Section \ref{contextindices}.
 202
 203 \subsubsection{Initialisation}
 204 \label{initarith}
 205
 206 At the beginning of the decoding of any data unit, the arithmetic
 207 decoding state is initialised as follows:
 208
 209 \begin{pseudo}{initialise\_arithmetic\_decoding}{block\_data\_length}
 210 \bsCODE{\ABitsLeft=8*block\_data\_length}
 211 \bsCODE{\ALow = \text{0x0}}
 212 \bsCODE{\ARange =\text{0x10000}}
 213 \bsCODE{\ACode =\text{ 0x0}}
 214 \bsFOR{i=0}{15}
 215     \bsCODE{\ACode <<= 1}
 216     \bsCODE{\ACode+= read\_bitb()}
 217 \bsEND
 218 \bsCODE{init\_contexts()}
 219 \end{pseudo}
 220
 221 Contexts are initialised by the $init\_contexts()$ function as follows:
 222
 223 \begin{pseudo}{init\_contexts}{}
 224 \bsFOR{i=0}{length(\AContexts)-1}
 225   \bsCODE{\AContexts[i][prob0]=0x8000}
 226 \bsEND
 227 \end{pseudo}
 228
 229 \subsubsection{Data input}
 230 \label{inputarith}
 231
 232 The arithmetic decoding process accesses data in a contiguous block of bytes
 233 whose size is set on initialisation (Section \ref{initarith}). The bits in this
 234 block are sufficient to allow for the
 235 decoding of all coefficients. However, the specification of arithmetic
 236 decoding operations in this section may occasionally cause further bits to be read,
 237 even though they are not required for determining decoded values. For this
 238 reason the bounded-block read function $read\_bitb()$ (Section \ref{blockreadbit}) is
 239 used for data access.
 240
 241 Since the length of arithmetically coded data elements is given in bytes within the Dirac
 242 stream, there may be bits left unread when all values have been extracted. These
 243 are flushed as desribed in Section \ref{blockreadbit}. Since arithmetically coded blocks
 244 are byte-aligned and a whole number of bytes, this aligns data input with the beginning of the byte
 245 after the arithmetically coded data i.e. at the end of the
 246 data chunk. $flush\_inputb()$ is always called at the end of decoding an arithmetically encoded
 247 data element.
 248
 249 \begin{informative}
 250 The Dirac arithmetic decoding engine uses 16 bit words, and so if all coefficients are
 251 coded no more than 16 additional bits should be read beyond the end of the block. Hence it
 252 would seem sufficient to read in the entire block of data and pad the end with two bytes of value 0xFF,
 253 to avoid a branch condition on inputting data
 254 However, an arithmetically encoded block may end with a string of 1s, which an encoder could
 255 conceivably strip out to save bits, in the knowledge that $read\_bitb()$ will re-insert them. Terminating
 256 strings of 1s can occur (but not exclusively) in coding many zero wavelet subband coefficients at the end
 257 of a subband. So a larger number of pad bytes may be required in practice.
 258 \end{informative}
 259
 260 \subsubsection{Decoding boolean values}
 261 \label{arithreadbool}
 262
 263 The arithmetic decoding engine is a multi-context, adaptive binary
 264 arithmetic decoder, performing binary renormalisation and producing
 265 binary outputs. For each bit decoded, the semantics of the relevant
 266 calling decoder function determine which contexts are passed to the
 267 arithmetic decoding operations.
 268
 269 This section specifies the operation of the $read\_boola()$ function
 270 for extracting a boolean value from the Dirac stream. The overall decoding
 271 process for extracting a symbol is as defined by the following
 272 pseudocode:
 273
 274 \begin{pseudo}{read\_boola}{context\_index}
 275 \bsCODE{context=\AContexts[context\_index]}
 276 \bsCODE{count = \ACode-\ALow+1}
 277 \bsCODE{range\_times\_prob = (\ARange * context[prob0])\gg 16}
 278 \bsIF{ count > range\_times\_prob }
 279   \bsCODE{value = \true}
 280   \bsCODE{\ALow +=  range\_times\_prob}
 281   \bsCODE{\ARange -= range\_time\_prob}
 282 \bsELSE
 283   \bsCODE{value = \false}
 284   \bsCODE{\ARange = range\_times\_prob}
 285 \bsEND
 286 \bsCODE{update\_context(\AContexts[context\_index],value)}
 287 \bsWHILE{\ARange<=\text{0x4000}}
 288     \bsCODE{renormalise()}{\ref{renormalisation}}
 289 \bsEND
 290 \bsRET(value)
 291 \end{pseudo}
 292
 293 \begin{informative}
 294 The function scales the probability of the symbol $0$ from the decoding context
 295 so that if this probability were $1$, then the interval would equal that between
 296  $\ALow$ and
 297  \[high=\ALow+\ARange-1\]
 298 and $count$ is set to the normalised cut-off between 0 and 1 within this range.
 299 \end{informative}
 300
 301 \subsubsection{Renormalisation}
 302 \label{renormalisation}
 303
 304 Renormalisation is applied to stop the arithmetic decoding
 305 engine from losing accuracy: the range must not get too small,
 306  in order that 0 and 1 may be distinguished. Renormalisation is
 307  applied while the range is less than or equal to a quarter of
 308  the total available 16-bit range ($\text{0x4000}$).
 309
 310 For convenience let $low=\ALow$ and $high=\ALow+\ARange-1$
 311 represent the upper and lower bounds of the interval. If the
 312 range is $<=\text{0x4000}$ then
 313 one of three possibilities must obtain:
 314 \begin{enumerate}
 315 \item the msbs of $low$ and $high$ are both 0
 316 \item the msbs of $low$ and $high$ are both 1
 317 \item $low=b01...$, $high=b10....$,  and the interval straddles the half-way point 0x8000.
 318 \end{enumerate}
 319
 320 Renormalisation doubles the interval and reads a bit into the codeword
 321 as follows:
 322
 323 \begin{pseudo}{renormalise}{}
 324 \bsIF{(\ALow+\ARange-1)^\ALow>=\text{0x8000}}
 325     \bsCODE{\ACode ^= \text{0x4000}}
 326     \bsCODE{\ALow ^= \text{0x4000}}
 327 \bsEND
 328 \bsCODE{\ALow  <<=  1}
 329 \bsCODE{\ARange  <<=  1}
 330 \bsCODE{\ALow \&= \text{0xFFFF}}
 331 \bsCODE{\ACode <<= 1}
 332 \bsCODE{\ACode+= read\_bitb()}
 333 \bsCODE{\ACode \&= \text{0xFFFF}}
 334 \end{pseudo}
 335
 336 The second bit is flipped if there is a straddle condition (case 3). The renormalisation
 337 process has the effect that: in case 1, the interval $[low,high]$ is doubled from 0 ($x\mapsto 2*x$);
 338 in case 2 it is doubled from 1 ($x\mapsto 2*x-1$); and in case 3 it is doubled from 1/2 ($x\mapsto 2x-0.5$).
 339
 340 \begin{informative}
 341 Note that if 16-bit words (unsigned shorts) are used for decoder state variables $\ALow$,
 342  and $\ACode$ then there is no need for {\&}-ing with 0xFFFF. However, the
 343 operations specified here are defined in terms of integers, since intermediate calculations
 344  require higher dynamic range. In software, the efficiency of using short word lengths may
 345 or may not be offset by the requirement to cast to other data types for these calculations.
 346 \end{informative}
 347
 348 \begin{comment}
 349 \subsection{Alternative arithmetic decoding engines}
 350
 351 to
 352 16 consisting of three positive values:
 353 \begin{itemize}
 354 \item $context[count0]$ is a count of the number of zeroes
 355 \item $context[count1]$ is a count of the number of ones
 356 \item $context[prob0]$ is an estimate of the probability of zero to 16 bit accuracy
 357 \end{itemize}
 358
 359 Contexts are accessed by decoding functions
 360 via the indices defined in Section \ref{contextindices}.
 361
 362 Although counts are updated with each symbol decoded, the probability is only updated occasionally, as it is computationally
 363 expensive (see Section \ref{rescalecontext} below).
 364
 365 \subsubsection{Rescaling contexts and probabilities}
 366 \label{rescalecontext}
 367
 368 Contexts maintain counts to 8 bit accuracy, and contexts are rescaled when the total count (count0+count1) reaches 256. In addtion, prob0 is recalculated every
 369 8 symbols in each context. A context is rescaled by halving the counts of $0$ and $1$.
 370
 371 \begin{pseudo}{update\_context}{context,value}
 372 \bsIF{value==\true}
 373     \bsCODE{context[count1] += 1}
 374 \bsELSE
 375     \bsCODE{context[count0] += 1}
 376 \bsEND
 377 \bsIF( (context[count0]+context[count1])\%8==0)
 378     \bsIF{context[0]+context[1]== 256}
 379       \bsCODE{context[0] += 1}
 380       \bsCODE{context[0] \gg= 1}
 381       \bsCODE{context[1] += 1}
 382       \bsCODE{context[1] \gg= 1}
 383     \bsEND
 384     \bsCODE{calc\_prob0(context)}
 385 \bsEND
 386 \end{pseudo}
 387
 388 The probability of zero is recalculated to approximate
 389 \[ \frac{context[count0]*2^{16}}{context[count0]+context[count1]}\]
 390 to 16 bit accuracy:
 391
 392 \begin{pseudo}{calc\_prob0}{context}
 393 \bsCODE{weight = context[count0]+context[count1]}
 394 \bsCODE{inverse\_weight=(2^{16}+(weight//2))//weight}
 395 \bsCODE{context[prob0]=context[count0]*inverse\_weight}
 396 \end{pseudo}
 397
 398 \begin{informative}
 399 Note that since $context[count0]<weight$, $context[prob0]$ is always a 16 bit unsigned quantity.
 400 The inverse weight may easily be stored within a look-up table.
 401 \end{informative}
 402
 403 \subsection{Initialisation}
 404 \label{initarith}
 405
 406 At the beginning of the decoding of any data unit, the arithmetic
 407 decoding state is initialised as follows:
 408
 409 \begin{pseudo}{initialise\_arithmetic\_decoding}{block\_data\_length}
 410 \bsCODE{\ABitsLeft=8*block\_data\_length}
 411 \bsCODE{\ALow = \text{0x0}}
 412 \bsCODE{\ARange =\text{0x10000}}
 413 \bsCODE{\ACode =\text{ 0x0}}
 414 \bsFOR{i=0}{15}
 415     \bsCODE{\ACode <<= 1}
 416     \bsCODE{\ACode+= read\_bitb()}
 417 \bsEND
 418 \bsCODE{init\_contexts()}
 419 \end{pseudo}
 420
 421 Contexts are initialised by the $init\_contexts()$ function as follows:
 422
 423 \begin{pseudo}{init\_contexts}{}
 424 \bsFOR{i=0}{length(\AContexts)-1}
 425   \bsCODE{\AContexts[i][count0]=1}
 426   \bsCODE{\AContexts[i][count1]=1}
 427   \bsCODE{\AContexts[i][prob0]=0x8000}
 428 \bsEND
 429 \end{pseudo}
 430
 431 \subsection{Data input}
 432 \label{inputarith}
 433
 434 The arithmetic decoding process accesses data in a contiguous block of bytes
 435 whose size is set on initialisation (Section \ref{initarith}). The bits in this
 436 block are sufficient to allow for the
 437 decoding of all coefficients. However, the specification of arithmetic
 438 decoding operations in this section may occasionally cause further bits to be read,
 439 even though they are not required for determining decoded values. For this
 440 reason the bounded-block read function $read\_bitb()$ (Section \ref{blockreadbit}) is
 441 used for data access.
 442
 443 Since the length of arithmetically coded data elements is given in bytes within the Dirac
 444 stream, there may be bits left unread when all values have been extracted. These
 445 are flushed as desribed in Section \ref{blockreadbit}. Since arithmetically coded blocks
 446 are byte-aligned and a whole number of bytes, this aligns data input with the beginning of the byte
 447 after the arithmetically coded data i.e. at the end of the
 448 data chunk. $flush\_inputb()$ is always called at the end of decoding an arithmetically encoded
 449 data element.
 450
 451 \begin{informative}
 452 The Dirac arithmetic decoding engine uses 16 bit words, and so if all coefficients are
 453 coded no more than 16 additional bits should be read beyond the end of the block. Hence it
 454 would seem sufficient to read in the entire block of data and pad the end with two bytes of value 0xFF,
 455 to avoid a branch condition on inputting data
 456 However, an arithmetically encoded block may end with a string of 1s, which an encoder could
 457 conceivably strip out to save bits, in the knowledge that $read\_bitb()$ will re-insert them. Terminating
 458 strings of 1s can occur (but not exclusively) in coding many zero wavelet subband coefficients at the end
 459 of a subband. So a much larger number of pad bytes may be required in practice.
 460 \end{informative}
 461
 462 \subsection{Decoder functions}
 463 \label{extractarith}
 464 The arithmetic decoding engine is a multi-context, adaptive binary
 465 arithmetic decoder, performing binary renormalisation and producing
 466 binary outputs. For each bit decoded, the semantics of the relevant
 467 calling decoder function determine which contexts are passed to the
 468 arithmetic decoding operations.
 469
 470 \subsubsection{Decoding boolean values}
 471
 472 \label{arithreadbool}
 473
 474 This section specifies the operation of the $read\_boola()$ function
 475 for extracting a boolean value from the Dirac stream. The overall decoding
 476 process is defined for extracting a symbol is as defined by the following
 477 pseudocode:
 478
 479 \begin{pseudo}{read\_boola}{context\_index}
 480 \bsCODE{context=\AContexts[context\_index]}
 481 \bsCODE{count = \ACode-\ALow+1}
 482 \bsCODE{range\_times\_prob = (\ARange * context[prob0])\gg 16}
 483 \bsIF{ count > range\_times\_prob }
 484   \bsCODE{value = \true}
 485   \bsCODE{\ALow +=  range\_times\_prob}
 486   \bsCODE{\ARange -= range\_time\_prob}
 487 \bsELSE
 488   \bsCODE{value = \false}
 489   \bsCODE{\ARange = range\_times\_prob}
 490 \bsEND
 491 \bsCODE{update\_context(\AContexts[context\_index],value)}
 492 \bsCODE{renormalise()}{\ref{renormalisation}}
 493 \bsEND
 494 \bsRET(value)
 495 \end{pseudo}
 496
 497 \begin{informative}
 498 [Describe what's going on here]
 499 \end{informative}
 500
 501 \subsubsection{Renormalisation}
 502 \label{renormalisation}
 503
 504 Renormalisation is applied to stop the arithmetic decoding engine from losing accuracy: the range
 505 must not get too small to allow 0 and 1 to be distinguished. Renormalisation is applied while the
 506 range is less than or equal to a quarter of the total available 16-bit  range:
 507
 508 \begin{pseudo}{renormalise}{}
 509 \bsWHILE{\ARange<=\text{0x4000}}
 510     \bsIF{(\ALow+\ARange-1)^\ALow>=\text{0x8000}}
 511         \bsCODE{resolve\_straddle()}
 512     \bsEND
 513     \bsCODE{shift\_bits()}
 514 \bsEND
 515 \end{pseudo}
 516
 517 \begin{informative}
 518 Let the bottom of the arithmetic coding interval is represented by $low=\ALow$ and the top by $high=\ALow+\ARange-1$.
 519 When the range is one quarter or less of the original range ($2^{16}$), then one of three possibilities occurs:
 520 \begin{enumerate}
 521 \item the top bits of $low$ and $high$ are both 0
 522 \item the top bits of $low$ and $high$ are both 1
 523 \item $low=b01...$, $high=b10....$,  and the interval straddles the half-way point 0x8000.
 524 \end{enumerate}
 525
 526 In all of these cases the interval can be doubled in size to increase accuracy. In the first case, it is doubled from zero ($x\mapsto 2*x$);
 527 in the second it is doubled from 1 ($x\mapsto 2*x-1$); and in the third it is doubled from 1/2 ($x\mapsto 2x-0.5$).
 528
 529 \end{informative}
 530
 531 \begin{pseudo}{resolve\_staddle}{}
 532 \bsCODE{\ACode ^= \text{0x4000}}
 533 \bsCODE{\ALow ^= \text{0x4000}}
 534 \end{pseudo}
 535
 536 \begin{pseudo}{shift\_bits}{}
 537 \bsCODE{\ALow  <<=  1}
 538 \bsCODE{\ARange  <<=  1}
 539 \bsCODE{\ALow \&= \text{0xFFFF}}
 540 \bsCODE{\ACode <<= 1}
 541 \bsCODE{\ACode+= read\_bitb()}
 542 \bsCODE{\ACode \&= \text{0xFFFF}}
 543 \end{pseudo}
 544
 545 \begin{comment}
 546
 547 \begin{informative}
 548 The function scales the probability of the symbol $0$ from the decoding context
 549 so that if this probability were $1$, then the interval would equal that between
 550  $\ALow$ and $\AHigh$. If $\ACode$ is greater than this cut-off, then 1 ($\true$) has
 551 been encoded, else 0 ($\false$) has.
 552 \end{informative}
 553
 554 \subsubsection{Shifting bits in}
 555
 556 \label{arithshiftin}
 557
 558 This section defines the operation of the $shift\_bit\_in()$
 559 and $shift\_all\_bits()$ functions
 560 for reading bits into the arithmetic decoding state variables.
 561
 562 \begin{pseudo}{shift\_bit\_in}{}
 563 \bsCODE{\AHigh \ll= 1}
 564 \bsCODE{\AHigh \&= \text{0xFFFF}}
 565 \bsCODE{\AHigh += 1}
 566 \bsCODE{\ALow \ll= 1}
 567 \bsCODE{\ALow \&= \text{0xFFFF}}
 568 \bsCODE{\ACode \ll= 1}
 569 \bsCODE{\ACode \&= \text{0xFFFF}}
 570 \bsCODE{\ACode += read\_bitb()}{\ref{blockreadbit}}
 571 \end{pseudo}
 572
 573 $shift\_all\_bits()$ expands the interval between $\ALow$ and $\AHigh$
 574 until the msbs (bit 15) differ and the interval no longer
 575 straddles the half-way point 0x8000.
 576
 577 \begin{pseudo}{shift\_all\_bits}{}
 578 \bsWHILE{ \AHigh\&\text{0x8000})==\text{0x0} \text{ and } (\ALow\&\text{0x8000})==\text{0x0}}
 579   \bsCODE{shift\_bit\_in()}
 580 \bsEND
 581 \bsWHILE{ (\AHigh\&\text{0x4000})==\text{0x0} \text{ and } (\ALow\&\text{0x4000})==\text{0x4000} }
 582   \bsCODE{\ACode \wedge= \text{0x4000}}
 583   \bsCODE{\AHigh \wedge= \text{0x4000}}
 584   \bsCODE{\ALow \wedge= \text{0x4000}}
 585   \bsCODE{shift\_bit\_in()}
 586 \bsEND
 587 \end{pseudo}
 588
 589 \begin{informative}
 590 Note that if 16-bit words (unsigned shorts) are used for decoder state variables $\ALow$,
 591  $\AHigh$ and $\ACode$ then there is no need for {\&}-ing with 0xFFFF. However, the
 592 operations specified here are defined in terms of integers, since intermediate calculations
 593  require higher dynamic range. In software, the efficiency of using short word lengths may
 594 or may not be offset by the requirement to cast to other data types for these calculations.
 595 \end{informative}
 596
 597
 598
 599 \end{comment}