#ifndef __ARICACM_H_
#define __ARICACM_H_

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
/* $Copyright Issue
 * ----------------
 * Most of the code on arithemtic coding are modified from 
 * I.H. Witten, R.M. Neal, and J.G. Cleary, "Arithmetic coding for data
 * compression," Communnication ACM, vol 30, pp. 520-540, June 1987.
 *
 * The statistical table is implemented using Binary Index Tree as described in
 * P. M. Fenwick, "A new data structure for cumulative frequency tables,"
 * Softw. Pract. Exper. 24, 3 (Mar. 1994), 327-336.
 *
 * The idea of having the arithemetic coder to read/write bits directly was
 * from G. Davis code in "Wavelet Compression Construction Kit". His code
 * can only do write but has problem with synchronisation when doing read.
 * I fixed that with a virtual table approach.
 *
 * Mow-Song, Ng 2/9/2002
 * msng@mmu.edu.my
 * http://www.pesona.mmu.edu.my/~msng
 * 
 * I do not claim copyright to the code, but if you use them or modify them,
 * please drop me a mail.
 *
 */
/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
/* 
 * $LOG
 * ----
 * Data: 07-06-2002
 * - First version
 *
 * Date: 07-07-2002
 * - Added BasicCoder
 * - Some code shifting to arrange things better
 *
 * Date: 11-07-2002
 * - Added functions for writing arbitrary size code (up to 32 bits for 
 *	  one read/write)
 *
 * Date: 21-07-2002
 * - Modify the Context module. Now the maximum count is explicitly specified 
 *   by user.
 *
 * Date: 23-07-2002
 * - Fixed a bug in the count of number of bits outputed in the encoder
 *
 * Date: 24-07-2002
 * - Added nBitsInput to the arithmetic decoder
 *
 * Date: 15-08-2002
 * - Added BasicEscapeCoder
 * - Fixed some memory leak (pointers)
 *
 * Date: 16-08-2002
 * - Remove EntropyEncoderAdaptive & EntropyEncoderEscape
 * - Modified excape context behavior. Now we have an increasing decreament 
 *   size.
 *
 * $TODO
 * -----
 * - Check the escape coder, some how the performance is not as good as expected.
 *  + Checked! It seems that we have to tune the increment rate for a symbol and 
 *    the decrement rate of the escape symbol to obtain good results.
 *
 * - To extend BasicCoder to BasicEscapeCoder, which has an escape cotext in it
 *  + Done!
 * 
 * - Handle the EOF flag in the decoder.
 *
 * - Provide a threshold for the escape context. If the novel symbols count drop
 *   below a certain value, we do not use escape context at all.
 *   
 * - Order-1 coder (most likely not, the memory requirement is too high!)
 * 
 * - Upgrade to 27 bits!
 *
 */
/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/

/*----------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------*/	
#include <stdlib.h>
#include <stdio.h>
#include "bitio.h"
#include "global.h"
#include "memchk.h"

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
#define CodeValueBits 16            
#define TopValue (((int)1<<CodeValueBits)-1)      
#define FirstQtr (TopValue/4+1)   
#define Half	  (2*FirstQtr)     
#define ThirdQtr (3*FirstQtr)     

/*----------------------------------------------------------------------------*/	
#define DefaultMaxFrequency 16383			

/*----------------------------------------------------------------------------*/	
typedef struct ContextStruct{
	int nSymbols;	
	int *Tree;	
	int p2half;
   int TotalFreq;
	int MaxCount;
} Context;

Context *ContextAlloc(void);
void ContextDealloc(Context *context);
int ContextInitialize(Context *context, int nSymbols, int MaxCount, int set);
int ContextGetCumul(Context *context, int Ix);
void ContextPutValue(Context *context, int val, int ix);
int ContextGetProb(Context *context, int ix);
void ContextScaleDown(Context *context);
int ContextGetSymbol(Context *context, int cumFreq);
void ContextUpdate(Context *context, int val, int ix);
double ContextGetCost(Context *context, int symbol);
void ContextPrintTable(Context *context, FILE *fp);

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
typedef struct ArithEncoderStruct{
	int low;
	int high;
	int range;
	int BitsToFollow;
	BIT_FILE *bs;
	int nBitsOutput;
} ArithEncoder;

ArithEncoder *ArithEncoderAlloc(BIT_FILE *bs);
void ArithEncoderDealloc(ArithEncoder *encoder);
void ArithEncoderStart(ArithEncoder *encoder);
void ArithEncoderEncode(ArithEncoder *encoder, int countLeft, int count, 
								int countTotal);
void ArithEncoderBitPlusFollow(ArithEncoder *encoder, int bit);
void ArithEncoderDone(ArithEncoder *encoder);
int  ArithEncoderNBitsOutput(ArithEncoder *encoder);

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
typedef struct ArithDecoderStruct {
	int low;
	int high;
	int range;
	int value;
	BIT_FILE *bs;
	int nBitsInput;
	int eof;
} ArithDecoder;

ArithDecoder *ArithDecoderAlloc(BIT_FILE *bs);
void ArithDecoderDealloc(ArithDecoder *decoder);
void ArithDecoderStart(ArithDecoder *decoder);
void ArithDecoderDecode(ArithDecoder *decoder, int countLeft, int count, 
								int countTotal );
int  ArithDecoderNBitsInput(ArithDecoder *decoder);


/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
/* Note that the in the previous version, we have EntropyEncoderAdaptive and
 * EntropyEncoderEscape. They are tied to a fixed arithmetic coder. This 
 * prevents us from having just a single bit stream. The only way then is to 
 * arithmetic coded each data sets and then combine them into a single stream. 
 * The BasicCoder and BasicEscapeCoder requires a pointer to the arithemtic 
 * coder. Several coder can use the samearithmetic coder and produce a single 
 * bit streams. Conceptually, I see that the arithmetic coder does not perform 
 * compression/decompression, but just keeping track of the large floating 
 * number (which is about the same as the product of entropy from every 
 * symbols in the data set.
 *
 */

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
/* Refer to Davis 
 * The BasicCoder has a pointer to the context. The write operation requires 
 * a pointer to arithemetic coder. By freeing the coder from the arithmetic 
 * coder, we can use an arithmetic coder for several BasicCoder.
 */
typedef struct BasicCoderStruct{
	int nSymbols;
	int EndOfStreamSymbol;
	Context *context;
} BasicCoder;

BasicCoder *BasicCoderAlloc(int nSymbols, int MaxCount);

void BasicCoderDealloc(BasicCoder *coder);

double BasicCoderEncode(BasicCoder *coder, ArithEncoder *encoder, int symbol, 
								Boolean update);

int BasicCoderDecode(BasicCoder *coder, ArithDecoder *decoder, Boolean update);

void BasicCoderReset(BasicCoder *coder);

double BasicCoderGetCost(BasicCoder *coder, int symbol, Boolean update);

void BasicCoderSetNSymbols(BasicCoder *coder, int nSymbols, int MaxCount);

/*----------------------------------------------------------------------------*/	
/* 
 * The WriteNBits and ReadNBits functions are part of BasicCoder, but do not use
 * the data member of the module. This implementation allows read/write of symbols
 * and arbitrary bits value at any time without synchronisation problem.
 *
 */
void BasicCoderWriteNBits(ArithEncoder *encoder, int val, int nbits);
int BasicCoderReadNBits(ArithDecoder *decoder, int nbits);

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
/* BasicCoder with an escape context.
 */
typedef struct BasicEscapeCoderStruct{
	int nSymbols;
	int EndOfStreamSymbol, EscapeSymbol;
	char *NovelSymbol;
	Context *context;
	Context *escape;
	int EscapeDecreament;
	int EscapeDecreamentStart;
	int Thres;
	int nNovelSymbols;
} BasicEscapeCoder;

BasicEscapeCoder *BasicEscapeCoderAlloc(int nSymbols, int MaxCount, 
													 int EscapeDecreamentStart, int Thres);

void BasicEscapeCoderDealloc(BasicEscapeCoder *coder);

double BasicEscapeCoderEncode(BasicEscapeCoder *coder, ArithEncoder *encoder, 
										int symbol, Boolean update);

int BasicEscapeCoderDecode(BasicEscapeCoder *coder, ArithDecoder *decoder, 
									Boolean update);

void BasicEscapeCoderReset(BasicEscapeCoder *coder);

double BasicEscapeCoderGetCost(BasicEscapeCoder *coder, int symbol, 
										 Boolean update);

void BasicEscapeCoderSetNSymbols(BasicEscapeCoder *coder, int nSymbols, 
											int MaxCount, int EscapeDecreamentStart, 
											int Thres);

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
/* same as BasicCoderWriteNBits and BasicCoderReadNBits - should be used
 * from now on to streamlined the name.
 */
void CoderWriteNBits(ArithEncoder *encoder, int val, int nbits);
int CoderReadNBits(ArithDecoder *decoder, int nbits);

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	
void CoderWarning(char *fmt, ...);
void CoderError(char *fmt, ...);

/*----------------------------------------------------------------------------*/	
/*----------------------------------------------------------------------------*/	

#endif