/*
 * Multiplication Free ARithmetic Code
 * (c) 1993, 1999, M.Zakharov
 * Description:
 *       http://tnet.sochi.net/~maxime/doc/mfarc.ps.gz (in Russian)
 *       http://tnet.sochi.net/~maxime/doc/mfarc.txt (in English)
 *  Permission is granted to use this code for educational or research
 *  purposes only.
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <io.h>
#include <time.h>
#include <unistd.h>

#define IOBufSize 	(8*1024)
#define N_Char 		(256)
#define PAUSE 		(102400)
#define MaxQ		(0x7fff)

FILE		*in, *out;
unsigned char   Buffer;
unsigned char   MFARC_Mask = 128,
		MFARC_Word=0;

unsigned long	C, OC;

struct {
        unsigned long A,Q;
} Node[N_Char]; 

		
unsigned 	CntOverFlow;

unsigned char	BufIn[IOBufSize],
		BufOut[IOBufSize];
		
unsigned long 	SizeIn,
		SizeOut;

struct Head {
	unsigned long fsize;
} Head_File={0UL};


void EncodeChar(unsigned char);
unsigned char DecodeChar(void);
void PutBits(unsigned);
void GetBits(unsigned);

void EncodeFile(void) {
	unsigned r = 0;
 
	while(fread(&Buffer,1,1,in)!=0) {
		SizeIn++; r++;
		EncodeChar(Buffer);
		if(r == PAUSE) {
			r=0;
			printf("\x0dIn:%lu Out:%lu Ratio:%5.2f",
				SizeIn, SizeOut, 100.0 * SizeOut / SizeIn);
		}
	}
	PutBits(31);
}

void DecodeFile(void) {
	unsigned 	r = 0;
	unsigned char	Byte;
 
	MFARC_Mask=0;
	GetBits(32);
	while(SizeIn < SizeOut) {
		r++; SizeIn++;
		Byte = DecodeChar();
		fwrite(&Byte, 1, 1, out); 
		if(r == PAUSE) {
			r = 0;
			printf("\rRestore: %5.2f%%",100.0 * SizeIn / SizeOut);
		}
	} 
}

/* Bit's I/O for MFARC */

void PutBits(unsigned k) {
	register unsigned i;
 
	for(i = 0; i < k; i++) {
		if ((C & 0x80000000) != 0) MFARC_Word |= MFARC_Mask;
		C <<= 1;
		MFARC_Mask >>= 1;
		if(MFARC_Mask == 0) {
			fwrite(&MFARC_Word, 1, 1, out);
			MFARC_Word = 0; SizeOut += 1;
			MFARC_Mask = 0x80;
		}
	}
}

void GetBits(unsigned k) {
	register unsigned i;

	for(i = 0; i < k; i++) {
		if(MFARC_Mask == 0) {
			fread(&MFARC_Word, 1, 1, in);
			MFARC_Mask = 0x80;
		}
		C <<= 1; OC <<= 1;
		if((MFARC_Word & MFARC_Mask) != 0) C++;
		MFARC_Mask >>= 1;
	}
}

/* A Multiplication-free Arithmetic coding scheme */

int MFARC_Init(void) {
	register unsigned i;

	MFARC_Word = 0;	
	MFARC_Mask = 0x80; 
	C = OC = 0UL;
	CntOverFlow = 0;
	SizeIn = SizeOut = 0;
	for(i = 0; i < N_Char; i++) {
		Node[i].A = 1;
		Node[i].Q = i;
	} 
	return(0);
}

void Reduce(void) {
	register unsigned i;
	unsigned cum = 0;

	for(i = 0; i < N_Char; i++) {
		Node[i].Q = cum;
		++Node[i].A;
		Node[i].A >>=1;
		cum += Node[i].A;
	}
}

void Rebuild(unsigned index) {
	register int i;

	Node[index].A += 1;
	for(i = index+1; i < N_Char; i++) Node[i].Q++;
	if(Node[N_Char-1].Q == MaxQ) Reduce();
	return;
}

void EncodeChar(unsigned char Ind) {
	unsigned long RAZ;
	unsigned k;
	static unsigned Cnt = 0;

	Cnt++;
	C += Node[Ind].Q;

	RAZ = Node[Ind].A;
	for (k = 0;  Node[N_Char-1].Q + Node[N_Char-1].A >= RAZ; k++) {
		RAZ <<= 1;
	}

	PutBits(k);
	while (C >= 0xfffffffe - Node[N_Char-1].Q) {
		PutBits(1);
		CntOverFlow++;
	}
	Rebuild(Ind);
}

unsigned char DecodeChar(void) {
	unsigned i,j,k;
	unsigned long RAZ;

	for (i = 0; (Node[i].Q <= C) && (i < N_Char); i++);
	if (i > 0) i--;
 

	C -= Node[i].Q;
 
	OC += (unsigned long)Node[i].Q;

	RAZ = Node[i].A;
	for (k = 0; Node[N_Char-1].Q + Node[N_Char-1].A >= RAZ; k++) {
		RAZ <<= 1;
	}

	GetBits(k);

	while (OC >= 0xfffffffe - Node[N_Char-1].Q) {
		GetBits(1);
	} 

	Rebuild(i);
	return(i);
}


void main(int argc,char *argv[]) {
	time_t T0,T;
	int opt;

	if (argc < 3 || argc > 4) {
		printf("Usage: mfarc [-d] infile outfile\n\t-d - decompress\n");
	}

	opt = getopt(argc, argv, "d");
	if (opt == - 1) {

		printf("Compressing...\n");
		if ( (in = fopen(argv[1], "rb")) == NULL ||
			setvbuf(in, BufIn, _IOFBF, IOBufSize) != 0 ) {
				perror("input file");
		}
		if ( (out = fopen(argv[2], "wb")) == NULL ||
			setvbuf(out, BufOut, _IOFBF, IOBufSize) != 0 ) {
				perror("output file");
		}
		fseek(in, 0, SEEK_END);
		SizeIn = ftell(in);
		fseek(in, 0, SEEK_SET);
		printf(" Size=%ld\n", SizeIn);

		fwrite(&Head_File, 1, sizeof(Head_File), out);
		T0 = time(NULL);

		MFARC_Init();
		EncodeFile();

		T = time(NULL);
		Head_File.fsize = SizeIn;
		fseek(out, 0, SEEK_SET);
		fwrite(&Head_File, 1, sizeof(Head_File), out);
		flushall();
		SizeOut=filelength(fileno(out));
		printf("\rRatio=%5.2f%% Time=%5ds Encode speed=%5.2f Kbit/s\n",
        		100.0 * SizeOut / SizeIn, (T-T0), 
			8.0 * SizeIn / (T-T0) / 1024.0);
		printf("Data Ratio=%5.2f%%\n",
			100.0 * (SizeOut - sizeof(Head_File)) / SizeIn);
		printf("Aproax Code Length:%6.3f\n",
			8.0 * (SizeOut - sizeof(Head_File)) / SizeIn);
		printf("Cnt Overflow:%d\n", CntOverFlow);
		fclose(in);
		fclose(out);

	} else if (opt == 'd') {

		printf("Uncompressing...\n");
		if ( (in = fopen(argv[2], "rb")) == NULL ||
			setvbuf(in, BufIn, _IOFBF, IOBufSize) != 0 ) {
				perror("input file");
		}
		if ( (out = fopen(argv[3], "wb")) == NULL ||
			setvbuf(out, BufOut, _IOFBF, IOBufSize) != 0 ) {
				perror("output file");
		}
		fseek(in, 0, SEEK_SET);
		fread(&Head_File, 1, sizeof(Head_File), in);
		T0 = time(NULL);

		MFARC_Init();
		SizeOut = Head_File.fsize;
		DecodeFile();

		T = time(NULL);
		printf("\rTime=%5ds Decode speed=%5.2f Kbit/s\n",
			(T-T0), 8.0 * SizeIn / (T-T0) / 1024.0);
		fclose(in);
		fclose(out);
	}

	return;
}