/*
Copyright (c) 2004 Amir Said (said@ieee.org) & William A. Pearlman (pearlw@ecse.rpi.edu)
All rights reserved.

Redistribution and use in source and binary forms, with or without modification, 
are permitted provided that the following conditions are met:

-   Redistributions of source code must retain the above copyright notice, this list 
    of conditions and the following disclaimer. 

-   Redistributions in binary form must reproduce the above copyright notice, this list of 
    conditions and the following disclaimer in the documentation and/or other materials 
    provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY 
EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL 
THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 
OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER 
IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 
IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY 
OF SUCH DAMAGE.
*/

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
//                       ****************************                        -
//                        ARITHMETIC CODING EXAMPLES                         -
//                       ****************************                        -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
// Fast arithmetic coding implementation                                     -
// -> 32-bit variables, 32-bit product, periodic updates, table decoding     -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
// Version 1.00  -  April 25, 2004                                           -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
//                                  WARNING                                  -
//                                 =========                                 -
//                                                                           -
// The only purpose of this program is to demonstrate the basic principles   -
// of arithmetic coding. It is provided as is, without any express or        -
// implied warranty, without even the warranty of fitness for any particular -
// purpose, or that the implementations are correct.                         -
//                                                                           -
// Permission to copy and redistribute this code is hereby granted, provided -
// that this warning and copyright notices are not removed or altered.       -
//                                                                           -
// Copyright (c) 2004 by Amir Said (said@ieee.org) &                         -
//                       William A. Pearlman (pearlw@ecse.rpi.edu)           -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//                                                                           -
// A description of the arithmetic coding method used here is available in   -
//                                                                           -
// Lossless Compression Handbook, ed. K. Sayood                              -
// Chapter 5: Arithmetic Coding (A. Said), pp. 101-152, Academic Press, 2003 -
//                                                                           -
// A. Said, Introduction to Arithetic Coding Theory and Practice             -
// HP Labs report HPL-2004-76  -  http://www.hpl.hp.com/techreports/         -
//                                                                           -
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -


// - - Definitions - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

#ifndef O3DGC_ARITHMETIC_CODEC
#define O3DGC_ARITHMETIC_CODEC

#include <stdio.h>
#include "o3dgcCommon.h"

namespace o3dgc
{
    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    // - - Class definitions - - - - - - - - - - - - - - - - - - - - - - - - - - -

    class Static_Bit_Model                         // static model for binary data
    {
    public:

      Static_Bit_Model(void);

      void set_probability_0(double);             // set probability of symbol '0'

    private:  //  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
      unsigned bit_0_prob;
      friend class Arithmetic_Codec;
    };

    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    class Static_Data_Model                       // static model for general data
    {
    public:

      Static_Data_Model(void);
     ~Static_Data_Model(void);

      unsigned model_symbols(void) { return data_symbols; }

      void set_distribution(unsigned number_of_symbols,
                            const double probability[] = 0);    // 0 means uniform

    private:  //  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
      unsigned * distribution, * decoder_table;
      unsigned data_symbols, last_symbol, table_size, table_shift;
      friend class Arithmetic_Codec;
    };

    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    class Adaptive_Bit_Model                     // adaptive model for binary data
    {
    public:

      Adaptive_Bit_Model(void);         

      void reset(void);                             // reset to equiprobable model

    private:  //  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
      void     update(void);
      unsigned update_cycle, bits_until_update;
      unsigned bit_0_prob, bit_0_count, bit_count;
      friend class Arithmetic_Codec;
    };

    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    class Adaptive_Data_Model                    // adaptive model for binary data
    {
    public:

      Adaptive_Data_Model(void);
      Adaptive_Data_Model(unsigned number_of_symbols);
     ~Adaptive_Data_Model(void);

      unsigned model_symbols(void) { return data_symbols; }

      void reset(void);                             // reset to equiprobable model
      void set_alphabet(unsigned number_of_symbols);

    private:  //  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
      void     update(bool);
      unsigned * distribution, * symbol_count, * decoder_table;
      unsigned total_count, update_cycle, symbols_until_update;
      unsigned data_symbols, last_symbol, table_size, table_shift;
      friend class Arithmetic_Codec;
    };


    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    // - - Encoder and decoder class - - - - - - - - - - - - - - - - - - - - - - -

    // Class with both the arithmetic encoder and decoder.  All compressed data is
    // saved to a memory buffer

    class Arithmetic_Codec
    {
    public:

      Arithmetic_Codec(void);
     ~Arithmetic_Codec(void);
      Arithmetic_Codec(unsigned max_code_bytes,
                       unsigned char * user_buffer = 0);         // 0 = assign new

      unsigned char * buffer(void) { return code_buffer; }

      void set_buffer(unsigned max_code_bytes,
                      unsigned char * user_buffer = 0);          // 0 = assign new

      void     start_encoder(void);
      void     start_decoder(void);
      void     read_from_file(FILE * code_file);  // read code data, start decoder

      unsigned stop_encoder(void);                 // returns number of bytes used
      unsigned write_to_file(FILE * code_file);   // stop encoder, write code data
      void     stop_decoder(void);

      void     put_bit(unsigned bit);
      unsigned get_bit(void);

      void     put_bits(unsigned data, unsigned number_of_bits);
      unsigned get_bits(unsigned number_of_bits);

      void     encode(unsigned bit,
                      Static_Bit_Model &);
      unsigned decode(Static_Bit_Model &);

      void     encode(unsigned data,
                      Static_Data_Model &);
      unsigned decode(Static_Data_Model &);

      void     encode(unsigned bit,
                      Adaptive_Bit_Model &);
      unsigned decode(Adaptive_Bit_Model &);

      void     encode(unsigned data,
                      Adaptive_Data_Model &);
      unsigned decode(Adaptive_Data_Model &);

//   This section was added by K. Mammou
      void     ExpGolombEncode(unsigned int symbol, 
                               int k,
                               Static_Bit_Model & bModel0,
                               Adaptive_Bit_Model & bModel1)
               {
                   while(1)
                   {
                       if (symbol >= (unsigned int)(1<<k))
                       {
                           encode(1, bModel1);
                           symbol = symbol - (1<<k);
                           k++;
                       }
                       else
                       {
                           encode(0, bModel1); // now terminated zero of unary part
                           while (k--) // next binary part
                           {
                               encode((signed short)((symbol>>k)&1), bModel0);
                           }
                           break;
                       }
                   }
               }


    unsigned   ExpGolombDecode(int k,
                               Static_Bit_Model & bModel0,
                               Adaptive_Bit_Model & bModel1)
               {
                   unsigned int l;
                   int symbol = 0;
                   int binary_symbol = 0;
                   do
                   {
                       l=decode(bModel1);
                       if (l==1)
                       {
                           symbol += (1<<k);
                           k++;
                        }
                   }
                   while (l!=0);
                   while (k--)                             //next binary part
                   if (decode(bModel0)==1)
                   {
                       binary_symbol |= (1<<k);
                   }
                   return (unsigned int) (symbol+binary_symbol);
                }
//----------------------------------------------------------

    private:  //  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
      void propagate_carry(void);
      void renorm_enc_interval(void);
      void renorm_dec_interval(void);
      unsigned char * code_buffer, * new_buffer, * ac_pointer;
      unsigned base, value, length;                     // arithmetic coding state
      unsigned buffer_size, mode;     // mode: 0 = undef, 1 = encoder, 2 = decoder
    };
    inline long DecodeIntACEGC(Arithmetic_Codec & acd,
                               Adaptive_Data_Model & mModelValues,
                               Static_Bit_Model & bModel0,
                               Adaptive_Bit_Model & bModel1,
                               const unsigned long exp_k,
                               const unsigned long M)
    {
        unsigned long uiValue = acd.decode(mModelValues);
        if (uiValue == M) 
        {
            uiValue += acd.ExpGolombDecode(exp_k, bModel0, bModel1);
        }
        return UIntToInt(uiValue);
    }
    inline unsigned long DecodeUIntACEGC(Arithmetic_Codec & acd,
                                         Adaptive_Data_Model & mModelValues,
                                         Static_Bit_Model & bModel0,
                                         Adaptive_Bit_Model & bModel1,
                                         const unsigned long exp_k,
                                         const unsigned long M)
    {
        unsigned long uiValue = acd.decode(mModelValues);
        if (uiValue == M) 
        {
            uiValue += acd.ExpGolombDecode(exp_k, bModel0, bModel1);
        }
        return uiValue;
    }

    inline void EncodeIntACEGC(long predResidual, 
                               Arithmetic_Codec & ace,
                               Adaptive_Data_Model & mModelValues,
                               Static_Bit_Model & bModel0,
                               Adaptive_Bit_Model & bModel1,
                               const unsigned long M)
    {
        unsigned long uiValue = IntToUInt(predResidual);
        if (uiValue < M) 
        {
            ace.encode(uiValue, mModelValues);
        }
        else 
        {
            ace.encode(M, mModelValues);
            ace.ExpGolombEncode(uiValue-M, 0, bModel0, bModel1);
        }
    }
    inline void EncodeUIntACEGC(long predResidual, 
                                Arithmetic_Codec & ace,
                                Adaptive_Data_Model & mModelValues,
                                Static_Bit_Model & bModel0,
                                Adaptive_Bit_Model & bModel1,
                                const unsigned long M)
    {
        unsigned long uiValue = (unsigned long) predResidual;
        if (uiValue < M) 
        {
            ace.encode(uiValue, mModelValues);
        }
        else 
        {
            ace.encode(M, mModelValues);
            ace.ExpGolombEncode(uiValue-M, 0, bModel0, bModel1);
        }
    }

}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#endif