Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members  

ArithCodec Class Reference

Arithmetic coder/decoder. More...

#include <arithcodec.h>

Inheritance diagram for ArithCodec:

ArithCodecBase List of all members.

Public Methods

 ArithCodec (void)
 A constructor. More...

virtual void arithmeticEncode (FreqValue, FreqValue, FreqValue)
 Main encoding routine. More...

virtual FreqValue arithmeticDecodeTarget (FreqValue)
 Decode the target value using the current total frequency and the coder's state variables. More...

virtual void arithmeticDecode (FreqValue, FreqValue, FreqValue)
 Decode the next input symbol. More...

virtual void startEncode (void)
 Start the encoder. More...

virtual void finishEncode (void)
 Finish encoding. More...

virtual void startDecode (void)
 Start the decoder. More...

virtual void finishDecode (void)
 Finish decoding. More...

virtual void startOutputtingBits (void)
 Initialize the bit output function. More...

virtual void startInputtingBits (void)
 Start the bit input function. More...

virtual void doneOutputtingBits (void)
 Complete outputting bits. More...

virtual void doneInputtingBits (void)
 Complete inputting bits. More...

virtual size_t numberOfOutputBytes (void)
 Return the number of output bytes.


Protected Methods

CodeValue retrieveExcessInputBits (void)
 Read B_BITS beyond valid output (with FRUGAL_BITS). More...


Protected Attributes

CodeValue in_R
 Code range.

CodeValue in_D
 V - L (V offset).

DivValue in_r
 Normalized range.

CodeValue in_V
 Bitsream window.

long numberOfBytes
 Number of input/output bytes.

CodeValue out_L
 Lower bound.

CodeValue out_R
 Code range.

unsigned long outBitsOutstanding
 Follow bit count.

int ignoreFirstBit
 Flag whether to ignore first bit.

int firstMessage
 Flag whether reading first message.

int inBuffer
 Input buffer.

unsigned char inBitPtr
 Input bit pointer.

int inGarbage
 NUmber of bytes read past EOF.

int outBuffer
 Output buffer.

int outBitsToGo
 Output bits in buffer.

Detailed Description

Arithmetic coder/decoder.

The coding routines implemented by this class contain two different methods for doing the required arithmetic. In defs.h you must specify whether to use multiplication and division, or shifts and adds. You can also specify the number of frequency and code bits (F_BITS and B_BITS, respectively) at compile time. Fixing them at compile time gives improved performance, especially for the shift/add version.

Fixing bits: Usually frequency bits and code bits would only be changed for testing, and in a standard implementation might well be fixed at compile time. The advantage here is that the shift/add loop can be unrolled, without need for testing and decrementing a counter variable. The loops are unrolled explicitly by calling an include file unroll.i. The compiler may well be able to unroll the loops automatically when they are written to be detectable (with -funroll-loops in gcc, for example). The aim here was to emphasise what is going on at the machine level, and to ensure similar performance was obtained independent of the C compiler used.

Difference from conventional arithmetic coding: Approximate arithmetic allows a greater frequency range, at expense of compression size. The inefficiency is bounded by the maximum frequency and when B_BITS = 32 and F_BITS = 27, for example, this inefficency is negligible. If the shift/add optimisations are used, the total frequency count, t, must be partially normalised, so that 2^{f - 1} < t <= 2^f, where f is frequency bits, the variable "F_BITS". This partial normalisation applies only to shift/add arithmetic; the original multiplication/division arithmetic will still work correctly with arbitrary values for t).

FRUGAL_BITS option: If you #define FRUGAL_BITS, some bits in the output wil be saved.

Definition at line 90 of file arithcodec.h.

Constructor & Destructor Documentation

ArithCodec::ArithCodec (  void    ) 
 

A constructor.

Initialization steps are performed.

Definition at line 251 of file arithcodec.cpp.

References firstMessage, ignoreFirstBit, inBitPtr, inBuffer, inGarbage, numberOfBytes, outBitsToGo, outBuffer, and ArithCodecBase::outputDevice.

Member Function Documentation

void ArithCodec::arithmeticDecode (  FreqValue    low,
FreqValue    high,
FreqValue    total
)  [virtual]
 

Decode the next input symbol.

The following code describes this function (The actual code is only written less legibly to improve speed. See the comments in the source code which is essentially the same process.): 

 D -= low * (R / total);        //Adjust current code value
 
 if (high < total)
   R = (high-low) * (R/total);  //Adjust range
 else
   R -= low * (R / total);      //End of range is a special case
 
 DECODE_RENORMALISE;            //Expand code range and input bits

Parameters:
low  Low bound of the subinterval.
high  High bound of the subinterval.
total  The range of the interval.

Implements ArithCodecBase.

Definition at line 1136 of file arithcodec.cpp.

FreqValue ArithCodec::arithmeticDecodeTarget (  FreqValue    total )  [virtual]
 

Decode the target value using the current total frequency and the coder's state variables.

The following code describes this function (The actual code is only written less legibly to improve speed, including storing the ratio in_r = R/total for use by arithmeticDecode()): 

 target = D / (R / total);      //D = V - L.  (Old terminology)
                                //D is the location within the range R
                                //that the code value is located
                                //Dividing by (R / total) translates it
                                //to its correspoding frequency value
                                
 if (target < total)            //The approximate calculations mean the
   return target;               //encoder may have coded outside the
 else                           //valid frequency range (in the excess
   return total - 1;            //code range). This indicates that the
                                //symbol at the end of the frequency
                                //range was coded.  Hence return end of
                                //range (total - 1)

Parameters:
total  Current total frequency.
Returns:
Decoded target.

Implements ArithCodecBase.

Definition at line 666 of file arithcodec.cpp.

void ArithCodec::arithmeticEncode (  FreqValue    low,
FreqValue    high,
FreqValue    total
)  [virtual]
 

Main encoding routine.

The following pseudocode is a concise (but slow due to arithmetic calculations) description of what is calculated in this method. Note that the division is done before the multiplication. This is one of the key points of this version of arithmetic coding. This means that much larger frequency values can be accomodated, but that the integer ratio R / total (code range / frequency range) becomes a worse approximation as the total frequency count is increased. Therefore less than the whole code range will be allocated to the frequency range. The whole code range is used by assigning the symbol at the end of the frequency range (where high == total) this excess code range above and beyond its normal code range. This of course distorts the probabilities slightly, see Moffat's paper for details and compression results. Restricting the total frequency range means that the division and multiplications can be done to low precision with shifts and adds.

The following code describes this function. (The actual code is only written less legibly to improve speed.) 

  L += low * (R / total);                   //Adjust low bound
  
  if (high < total)
    R = (high - low) * (R / total);         //Restrict range
  else                                      //If symbol at end of range.
    R = R - low * (R / total);              //Restrict & allocate excess codelength to it.

  ENCODE_RENORMALISE;                       //Expand code range and output bits
  
  if (bitsOutstanding > MAX_BITS_OUTSTANDING)
    abort();                                //EXTREMELY improbable
                                            //(see comments in the source)

Parameters:
low  Low bound of the subinterval.
high  High bound of the subinterval.
total  Total range of the interval.

Implements ArithCodecBase.

Definition at line 377 of file arithcodec.cpp.

References B_BITS, CodeValue, DivValue, ENCODE_RENORMALISE, F_BITS, FATAL, FreqValue, MAX_BITS_OUTSTANDING, out_L, out_R, and outBitsOutstanding.

void ArithCodec::doneInputtingBits (  void    )  [virtual]
 

Complete inputting bits.

Clear input bit buffer.

Implements ArithCodecBase.

Definition at line 311 of file arithcodec.cpp.

References inBitPtr.

Referenced by XmlCodec::decode.

void ArithCodec::doneOutputtingBits (  void    )  [virtual]
 

Complete outputting bits.

Output remaining bits.

Implements ArithCodecBase.

Definition at line 298 of file arithcodec.cpp.

References BYTE_SIZE, numberOfBytes, outBitsToGo, outBuffer, ArithCodecBase::outputDevice, and IODevice::putChar.

Referenced by XmlCodec::encode, and XmlCodec::encodePush.

void ArithCodec::finishDecode (  void    )  [virtual]
 

Finish decoding.

Finish decoding by consuming the disambiguating bits generated by finishEncode (either 1, 2 or 3). Calculated as for finishEncode(). This will mean the coder will have read exactly B_BITS past end of valid coding output (these bits can be retrived with a call to retrieveExcessInputBits()).

See also:
finishEncode(), retrieveExcessInputBits()

Implements ArithCodecBase.

Definition at line 1488 of file arithcodec.cpp.

Referenced by XmlCodec::decode.

void ArithCodec::finishEncode (  void    )  [virtual]
 

Finish encoding.

Encoding is finished by outputting follow bits and one to three further bits to make the last symbol unambiguous.

Calculate the number of bits required: value = L rounded to "nbits" of precision (followed by zeros). value + roundup = L rounded to "nbits" of precision (followed by ones). Loop, increasing "nbits" until both the above values fall within [L,L+R), then output these "nbits" of L

Implements ArithCodecBase.

Definition at line 1400 of file arithcodec.cpp.

Referenced by XmlCodec::encode, and XmlCodec::encodePush.

CodeValue ArithCodec::retrieveExcessInputBits (  void    )  [protected]
 

Read B_BITS beyond valid output (with FRUGAL_BITS).

With FRUGAL_BITS defined, B_BITS beyond valid coding output are read. It is these excess bits that are returned by calling this function.

Returns:
Excess bits.

Definition at line 1522 of file arithcodec.cpp.

void ArithCodec::startDecode (  void    )  [virtual]
 

Start the decoder.

Fills the decode value in_D from the bitstream. If FRUGAL_BITS is defined only the first call reads in_D from the bitstream. Subsequent calls will assume the excess bits that had been read but not used (sitting in in_V) are the start of the next coding message, and it will put these into in_D. (It also initializes in_V to the start of the bitstream.)

FRUGAL_BITS also means that the first bit (0) was not output, so only take B_BITS-1 from the input stream. Since there are B_BITS "read-ahead" in the buffer, on second and subsequent calls retrieveExcessInputBits() is used and the last bit must be placed back into the input stream.

See also:
retrieveExcessInputBits()

Implements ArithCodecBase.

Definition at line 1448 of file arithcodec.cpp.

Referenced by XmlCodec::decode.

void ArithCodec::startEncode (  void    )  [virtual]
 

Start the encoder.

With FRUGAL_BITS, ensure first bit (always 0) not actually output.

Implements ArithCodecBase.

Definition at line 1382 of file arithcodec.cpp.

Referenced by XmlCodec::encode, and XmlCodec::initializePushCoder.

void ArithCodec::startInputtingBits (  void    )  [virtual]
 

Start the bit input function.

Variables related to bit input are initialized.

Implements ArithCodecBase.

Definition at line 287 of file arithcodec.cpp.

References inBitPtr, and inGarbage.

Referenced by XmlCodec::decode.

void ArithCodec::startOutputtingBits (  void    )  [virtual]
 

Initialize the bit output function.

Variables related to bit output are intialised.

Implements ArithCodecBase.

Definition at line 278 of file arithcodec.cpp.

References BYTE_SIZE, outBitsToGo, and outBuffer.

Referenced by XmlCodec::encode, and XmlCodec::initializePushCoder.

The documentation for this class was generated from the following files:
Generated on Wed Feb 5 10:43:04 2003 for Exalt by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002