---

arithcodec.cpp

Go to the documentation of this file.

/***************************************************************************
    arithcodec.cpp  -  Definitions of ArithCodec methods
                             -------------------
    begin                : June 21 2002
    copyright            : (C) 2003 by Vojtìch Toman
    email                : vtoman@lit.cz
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

/* Based on code by:                                                       */

/***************************************************************************
Authors:        John Carpinelli   (johnfc@ecr.mu.oz.au)
                Wayne Salamonsen  (wbs@mundil.cs.mu.oz.au)
                Lang Stuiver      (langs@cs.mu.oz.au)
                Radford Neal      (radford@ai.toronto.edu)

Purpose:        Data compression using a revised arithmetic coding method.

Based on:       A. Moffat, R. Neal, I.H. Witten, "Arithmetic Coding Revisted",
                Proc. IEEE Data Compression Conference, Snowbird, Utah, 
                March 1995.

                Low-Precision Arithmetic Coding Implementation by 
                Radford M. Neal



Copyright 1995 John Carpinelli and Wayne Salamonsen, All Rights Reserved.
Copyright 1996 Lang Stuiver, All Rights Reserved.

These programs are supplied free of charge for research purposes only,
and may not sold or incorporated into any commercial product.  There is
ABSOLUTELY NO WARRANTY of any sort, nor any undertaking that they are
fit for ANY PURPOSE WHATSOEVER.  Use them at your own risk.  If you do
happen to find a bug, or have modifications to suggest, please report
the same to Alistair Moffat, alistair@cs.mu.oz.au.  The copyright
notice above and this statement of conditions must remain an integral
part of each and every copy made of these files.
****************************************************************************/


#ifdef __GNUG__
#pragma implementation
#endif

#include "arithcodec.h"


#define OUTPUT_BIT(b)                   \
{                                       \
  outBuffer <<= 1;                      \
  if (b)                                \
    outBuffer |= 1;                     \
  outBitsToGo--;                        \
  if (outBitsToGo == 0)                 \
    {                                   \
      outputDevice->putChar(outBuffer); \
      numberOfBytes++;                  \
      outBitsToGo = BYTE_SIZE;          \
      outBuffer = 0;                    \
    }                                   \
}                                               



#define UNGET_BIT(b)                    \
{                                       \
  inBitPtr <<= 1;                       \
                                        \
  if (inBitPtr == 0)                    \
    inBitPtr = 1;                       \
                                        \
  /* Only keep bits still to be read */ \
  inBuffer = inBuffer & (inBitPtr - 1); \
  if (b)                                \
    /* Replace bit */                   \
    inBuffer |= inBitPtr;               \
}



#define ADD_NEXT_INPUT_BIT(v, garbageBits)                              \
{                                                                       \
  if (inBitPtr == 0)                                                    \
    {                                                                   \
      if (inputDevice->getChar(&inBuffer) == EndOfFile)                 \
        {                                                               \
          inGarbage++;                                                  \
          if ((FreqValue)((inGarbage-1)*8) >= garbageBits)              \
            FATAL("Bad input file - attempted read past end of file."); \
        }                                                               \
      inBitPtr = (1<<(BYTE_SIZE-1));                                    \
    }                                                                   \
    v <<= 1;                                                            \
                                                                        \
  if (inBuffer & inBitPtr)                                              \
    v++;                                                                \
                                                                        \
  inBitPtr >>= 1;                                                       \
}



#define ORIG_BIT_PLUS_FOLLOW(b)         \
{                                       \
  OUTPUT_BIT(b);                        \
                                        \
  while (outBitsOutstanding > 0)        \
    {                                   \
      OUTPUT_BIT(!b);                   \
      outBitsOutstanding--;             \
    }                                   \
}


#ifdef FRUGAL_BITS

# define BIT_PLUS_FOLLOW(x)                     \
   {                                            \
     if (ignoreFirstBit)                        \
       ignoreFirstBit = 0;                      \
     else                                       \
       ORIG_BIT_PLUS_FOLLOW(x);                 \
   }

#else

# define BIT_PLUS_FOLLOW(x)             ORIG_BIT_PLUS_FOLLOW(x)

#endif

#define ENCODE_RENORMALISE              \
{                                       \
  while (out_R <= Quarter)              \
    {                                   \
      if (out_L >= Half)                \
        {                               \
          BIT_PLUS_FOLLOW(1);           \
          out_L -= Half;                \
        }                               \
      else                              \
        if (out_L+out_R <= Half)        \
          {                             \
            BIT_PLUS_FOLLOW(0);         \
          }                             \
        else                            \
          {                             \
            outBitsOutstanding++;       \
            out_L -= Quarter;           \
          }                             \
      out_L <<= 1;                      \
      out_R <<= 1;                      \
  }                                     \
}


#ifdef FRUGAL_BITS

# define DECODE_RENORMALISE                     \
   {                                            \
     while (in_R <= Quarter)                    \
       {                                        \
         in_R <<= 1;                            \
         in_V <<= 1;                            \
         ADD_NEXT_INPUT_BIT(in_D,B_BITS);       \
         if (in_D & 1)                          \
           in_V++;                              \
       }                                        \
   }

#else

# define DECODE_RENORMALISE             \
   {                                    \
     while (in_R <= Quarter)            \
       {                                \
         in_R <<= 1;                    \
         ADD_NEXT_INPUT_BIT(in_D,0);    \
       }                                \
   }

#endif



ArithCodec::ArithCodec(void)
  : ArithCodecBase()
{
  outputDevice = 0;


#ifdef FRUGAL_BITS
  ignoreFirstBit = 1;
  firstMessage = 1;
#endif

  numberOfBytes = 0;    //number of output bytes

  inBuffer = 0;         //I/O buffer
  inBitPtr = 0;         //bits left in buffer
  inGarbage = 0;        //bytes read beyond eof
  
  outBuffer = 0;        //I/O buffer
  outBitsToGo = 0;      //bits to fill buffer
}




void ArithCodec::startOutputtingBits(void)
{
  outBuffer = 0;
  outBitsToGo = BYTE_SIZE;
}

void ArithCodec::startInputtingBits(void)
{
  inGarbage = 0;        //Number of bytes read past end of file
  inBitPtr = 0;         //No valid bits yet in input buffer
}



void ArithCodec::doneOutputtingBits(void)
{
  if (outBitsToGo != BYTE_SIZE)
    {
      outputDevice->putChar(outBuffer << outBitsToGo);
      numberOfBytes++;
    }
  outBitsToGo = BYTE_SIZE;
}

void ArithCodec::doneInputtingBits(void)
{
  inBitPtr = 0;         //"Wipe" buffer (in case more input follows)
}



//  /*!
//    Sets output device for the encoder.

//    \param od Output device.
//   */
//  void ArithCodec::setOutputDevice(IODevice *od)
//  {
//    if (outputDevice)
//      {
//        WRN("ArithCodec: Output device already specified, ommiting new.");
//      }
//    else
//      outputDevice = od;
//  }



//  /*!
//    Sets input device for the decoder.

//    \param id Input device.
//   */
//  void ArithCodec::setInputDevice(IODevice *id)
//  {
//    if (inputDevice)
//      {
//        WRN("ArithCodec: Input device already specified, ommiting new.");
//      }
//    else
//      inputDevice = id;
//  }



void ArithCodec::arithmeticEncode(FreqValue low, FreqValue high, FreqValue total)
{ 
  CodeValue temp; 

#ifdef MULT_DIV
  {
    DivValue out_r;                     
    out_r = out_R/total;        //Calc range:freq ratio
    temp = out_r*low;           //Calc low increment
    out_L += temp;              //Increase L
    if (high < total)
      out_R = out_r*(high-low); //Restrict R
    else
      out_R -= temp;            //If at end of freq range

    //Give symbol excess code range
  }
#else
  {
    CodeValue A, M;             //A = numerator, M = denominator
    CodeValue temp2;

    
    //calculate r = R/total, temp = r*low and temp2 = r*high
    //using shifts and adds  (r need not be stored as it is implicit in the loop)

    A = out_R;
    temp = 0;
    temp2 = 0;

    M = total << (B_BITS - F_BITS - 1);
    if (A >= M) { A -= M; temp += low; temp2 += high; }

#define UNROLL_NUM      B_BITS - F_BITS - 1
#define UNROLL_CODE                             \
    A <<= 1; temp <<= 1; temp2 <<= 1;           \
    if (A >= M)                                 \
      {                                         \
        A -= M; temp += low; temp2 += high;     \
      }

#include "unroll.h"             //unroll the above code

    out_L += temp;
    if (high < total)
      out_R = temp2 - temp;
    else
      out_R -= temp;
  }
#endif

  ENCODE_RENORMALISE;

  if (outBitsOutstanding > MAX_BITS_OUTSTANDING)
    //For MAX_BITS_OUTSTANDING to be exceeded is extremely improbable, but
    //it is possible. For this to occur the COMPRESSED file would need to
    //contain a sequence MAX_BITS_OUTSTANDING bits long (eg: 2^31 bits, or
    //256 megabytes) of all 1 bits or all 0 bits. This possibility is
    //extremely remote (especially with an adaptive model), and can only
    //occur if the compressed file is greater than MAX_BITS_OUTSTANDING
    //long. Assuming the compressed file is effectively random,
    //the probability for any 256 megabyte section causing an overflow
    //would be 1 in 2^(2^31). This is a number approximately 600 million
    //digits long (decimal).
    FATAL("Bits_outstanding limit reached - File too large!");
}



FreqValue ArithCodec::arithmeticDecodeTarget(FreqValue total)
{
  FreqValue target;
    
#ifdef MULT_DIV
  in_r = in_R/total;
  target = (in_D)/in_r;
#else 
  {     
    CodeValue A, M;     //A = numerator, M = denominator

    //divide r = R/total using shifts and adds
    A = in_R;
    in_r = 0;

    M = total << ( B_BITS - F_BITS - 1 );
    if (A >= M) { A -= M; in_r++; }

#define UNROLL_NUM      B_BITS - F_BITS - 1
#define UNROLL_CODE                     \
    A <<= 1; in_r <<= 1;                \
    if (A >= M)                         \
      {                                 \
        A -= M; in_r++;                 \
      }

#include "unroll.h"

    A = in_D;
    target = 0;
    if (in_r < (1 << (B_BITS - F_BITS - 1)))
      { M = in_r << F_BITS; 
      if (A >= M) { A -= M; target++; } 
      A <<= 1; target <<= 1;            
      }
    else
      {
        M = in_r << (F_BITS - 1);
      }

    if (A >= M) { A -= M; target++; }


#define UNROLL_NUM      F_BITS - 1
#define UNROLL_CODE                     \
    A <<= 1; target <<= 1;              \
    if (A >= M)                         \
      {                                 \
        A -= M; target++;               \
      } 

#include "unroll.h"

  }
#endif //shifts vs multiply

  return (target >= total ? total-1 : target);
}



void ArithCodec::arithmeticDecode(FreqValue low, FreqValue high, FreqValue total)
{     
  CodeValue temp;

#ifdef MULT_DIV
  //assume r has been set by decode_target
  temp = in_r*low;
  in_D -= temp;
  if (high < total)
    in_R = in_r*(high-low);
  else
    in_R -= temp;
#else
  {
    CodeValue temp2, M;
    
    //calculate r*low and r*high using shifts and adds
    temp = 0;
    temp2 = 0;

    M = in_r << F_BITS;

    if (M & Half) { temp += low; temp2 += high; }

#define UNROLL_NUM  B_BITS - F_BITS - 1
#define UNROLL_CODE                             \
    M <<= 1; temp <<= 1; temp2 <<= 1;           \
    if (M & Half)                               \
      {                                         \
        temp += low; temp2 += high;             \
      }

#include "unroll.h"


    in_D -= temp;
    if (high < total)
      in_R = temp2 - temp;
    else
      in_R -= temp;
  }
#endif //shifts vs multiply

  DECODE_RENORMALISE;
}



void ArithCodec::startEncode(void)
{
  out_L = 0;                    //Set initial coding range to
  out_R = Half;                 //[0,Half)
  outBitsOutstanding = 0;
#ifdef FRUGAL_BITS
  ignoreFirstBit = 1;           //Don't ouput the leading 0
#endif
}



#ifdef FRUGAL_BITS

void ArithCodec::finishEncode(void)
{
  unsigned int nbits, i;
  CodeValue roundup, bits, value;

  bits = 0;
  nbits = 0;

  for (nbits = 1; nbits <= B_BITS; nbits++)
    {
      roundup = (1 << (B_BITS - nbits)) - 1;
      bits = (out_L + roundup) >> (B_BITS - nbits);
      value = bits << (B_BITS - nbits);
      if (out_L <= value && value + roundup <= (out_L + (out_R - 1)) )
        break;
    }
  for (i = 1; i <= nbits; i++)
    //output the nbits integer bits
    BIT_PLUS_FOLLOW(((bits >> (nbits-i)) & 1));
}
#else


void ArithCodec::finishEncode(void)
{
  int nbits, i;
  CodeValue bits;
  
  nbits = B_BITS;
  bits  = out_L;
  for (i = 1; i <= nbits; i++)
    //output the nbits integer bits
    BIT_PLUS_FOLLOW(((bits >> (nbits-i)) & 1));
}
#endif


void ArithCodec::startDecode(void)
{
  unsigned int i;
  
  in_D = 0;             //Initial offset in range is 0
  in_R = Half;          //Range = Half
  
#ifdef FRUGAL_BITS
  {
    
    if (firstMessage)
      {
        for (i = 0; i < B_BITS-1; i++)
          ADD_NEXT_INPUT_BIT(in_D, B_BITS);
      }
    else
      {
        in_D = retrieveExcessInputBits();
        UNGET_BIT(in_D & 1);
        in_D >>=1;
      }
    
    firstMessage = 0;
    in_V = in_D;
  }
#else
  for (i = 0; i<B_BITS; i++)    //Fill D
    ADD_NEXT_INPUT_BIT(in_D, 0);
#endif

  if (in_D >= Half)
    FATAL("Corrupt input file.");
}

#ifdef FRUGAL_BITS

void ArithCodec::finishDecode(void)
{
  unsigned int nbits, i;
  CodeValue roundup, bits, value;
  CodeValue in_L;
  
  //This gets us either the real L, or L + Half.  Either way, we can work
  //out the number of bit emitted by the encoder
  in_L = (in_V & (Half-1))+ Half - in_D;
  
  for (nbits = 1; nbits <= B_BITS; nbits++)
    {
      roundup = (1 << (B_BITS - nbits)) - 1;
      bits = (in_L + roundup) >> (B_BITS - nbits);
      value = bits << (B_BITS - nbits);
      if (in_L <= value && value + roundup <= (in_L + (in_R - 1)) )
        break;
    }

  //No bits to consume
  if (nbits > B_BITS)
    return;
  else
    for (i = 1; i <= nbits; i++)
      {
        ADD_NEXT_INPUT_BIT(in_V, B_BITS);
      }
}

CodeValue ArithCodec::retrieveExcessInputBits(void)
{
  return (in_V & (Half + (Half-1)) );
}

#else

void ArithCodec::finishDecode(void)
{
  //No action
}
#endif

size_t ArithCodec::numberOfOutputBytes(void)
{
  return numberOfBytes;
}

---