/*
 *	cliprc.c
 *
 *	Range Coder
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2014 Naoyuki Sawa
 *
 *	* Wed Dec 03 21:01:59 JST 2014 Naoyuki Sawa
 *	- 1st リリース。
 *	  RangeCoderDecoder_Decode(),RangeCoderDecoder_Init(),RangeCoderDecoder_Getc()のアセンブラ化も行いました。
 *	  圧縮データの作成は、DOSコマンドラインツール「tool/dprc」を利用してください。
 *	- 下記の記事を参考にしました。
 *	  「高速な算術圧縮を実現する「Range Coder」」(http://codezine.jp/article/detail/443)
 *	  (ダウンロードして「keep/高速な算術圧縮を実現する「Range Coder」.7z」に保存しておきました。)
 *	  当モジュールの実装は、サンプルソースの実装を参考にし、加えて以下の工夫を行いました。
 *	  ・圧縮時に格納する確率表が小さく済むよう工夫しました。
 *	  ・サンプルソースは確率分母がデータサイズのままですが、当モジュールは1/65536に正規化しました。
 *	  ・サンプルソースはデコーダが二分探索を行っていますが、当モジュールは出現確率が高い順に線形探索を行うようにしました。
 *	  ・サンプルソースは元データのサイズをヘッダに格納していますが、当モジュールは終端符号で判断するようにしました。
 *	- RangeCoderDecoder_Decode()の速度は、HuffmanDecoder_Decode()に較べて、おおよそ二倍遅いです。
 *	  出現確率の偏りが小さいファイルでは、圧縮率も大差無いか、又は、確率表が大きい分ハフマンよりも圧縮率が劣ります。
 *	  構造体のサイズも、ハフマンの8バイトに較べて、Range Coderは16バイトと、劣っています。
 *	  コードサイズは、ハフマンよりも、Range Coderの方が、かなり小さいです。
 *	  以上の特性を考慮すると、出現確率の偏りが大きいことが判っている場合や、コードサイズが非常に重要な場合を除いて、
 *	  一般的には、ハフマンを使用する方が適切であるように思います。
 *	* Fri Dec 05 21:45:35 JST 2014 Naoyuki Sawa
 *	- アセンブラ版RangeCoderDecoder_Getc()の、'工夫した実装'を作成しました。
 *	  RangeCoderDecoder_Decode()で、約39KB⇒約62KBの展開を行った時の速度が、約1.350秒⇒約1.272秒に高速化しました。(Clock=48MHz,Code=SRAM,Stack=FRAM)
 *	  RangeCoderDecoder_Decode()で、約39KB⇒約62KBの展開を行った時の速度が、約0.554秒⇒約0.534秒に高速化しました。(Clock=48MHz,Code=FRAM,Stack=FRAM)
 *	  詳細は、'工夫した実装'の'RangeCoderDecoder_Getc_L10〜'のループ区間のコメントを参照してください。
 *	  コードサイズは、'素直な実装'も'工夫した実装'も、同じです。
 */
#include "clip.h"

/****************************************************************************
 *	RangeCoderエンコーダー
 ****************************************************************************/
//文字情報のノード
typedef struct _ST_RangeCoderNode {
	int	x;	//文字0〜255
	int	c;	//c(x)=文字xの出現回数
	int	p;	//p(x)=文字xの出現確率(p/65536)		//終端文字に(1/65536)の出現確率を与えるので、文字0〜255の出現確率は(65535/65536)以下となる。
	int	cum;	//cum(x+1)=文字0〜xの出現確率の和
} ST_RangeCoderNode;
//------------------------------------------------------------------------------
//(ST_RangeCoderNode)を、(ST_RangeCoderNode.c)の降順にソートする、比較関数。
//(ST_RangeCoderNode.c)が同じならば、(ST_RangeCoderNode.x)の昇順とする。		この判断は必須ではない。見易さのためだけです。
static int RangeCoderEncoder_CompareNode(const void* _a, const void* _b) {
	ST_RangeCoderNode* a = (ST_RangeCoderNode*)_a;
	ST_RangeCoderNode* b = (ST_RangeCoderNode*)_b;
	if(a->c > b->c) { return -1; }	//出現回数の降順とする。
	if(a->c < b->c) { return  1; }	//
	if(a->x < b->x) { return -1; }	//出現回数が同じならば、文字の昇順とする。	この判断は必須ではない。見易さのためだけです。
	if(a->x > b->x) { return  1; }	//
	return 0;
}
//------------------------------------------------------------------------------
//圧縮元データ全体をエンコードし、圧縮データを作成する。
// - src,dst共に、アライメント不要。
// - 圧縮データがdstBytesを超えた場合は、越えた部分は格納しない。
//   格納の可否に関係なく、戻り値は、圧縮データのバイト数である。
//   この性質を利用して、一回目は(dst=NULL,dstBytes=0)で呼び出し、必要なバッファサイズを確認,確保した後、再度呼び出す方法も可能です。
//   <例>
//   │dstBytes=RangeCoderEncoder_Encode(src,srcBytes,NULL,0);
//   │dst=malloc(dstBytes);
//   │RangeCoderEncoder_Encode(src,srcBytes,dst,dstBytes);
int RangeCoderEncoder_Encode(const void* _src, int srcBytes, void* _dst, int dstBytes) {
	ST_RangeCoderNode TBL_Node[256];
	unsigned char     TBL_Map[ 256];	//文字⇒ノード対応表	文字xに対応するノードは、TBL_Node[TBL_Map[x]]で求まる。
	const unsigned char* src = _src;
	      unsigned char* dst = _dst;
	int dstPos = 0;
	//--- 準備処理 ---
	{
		int i;
		//ノードを初期化する。
		memset(TBL_Node, 0, sizeof TBL_Node);
		for(i = 0; i < 256; i++) {
			TBL_Node[i].x = i;
		}
		//文字0〜255の出現回数を数える。
		for(i = 0; i < srcBytes; i++) {
			TBL_Node[src[i]].c++;
		}
		//ノードを出現回数の降順にソートする。
		qsort(TBL_Node, 256, sizeof TBL_Node[0], RangeCoderEncoder_CompareNode);
		//出現回数を、出現確率(p/65536)に変換する。
		TBL_Node[0].p = 65536 - 1/*終端文字の出現確率*/;	//終端文字に(1/65536)の出現確率を与え、残りを文字0〜255に分配する。	//打ち切り誤差によって余った出現確率は、出現回数が最大の文字の出現確率に含めて与える。
		for(i = 255; i > 0; i--) {
			ST_RangeCoderNode* pNode = &TBL_Node[i];
			if(pNode->c) {
				pNode->p = (int)((uint64_t)pNode->c * (uint64_t)(65536 - 1/*終端文字の出現確率*/) / (uint64_t)srcBytes);	//ここの除算で打ち切り誤差が発生する。
				if(!pNode->p) { pNode->p = 1; }											//出現回数c(x)≧1を、(出現回数⇒出現確率)に変換した後も、出現確率p(x)≧1となるように、調整する必要が有る。
				TBL_Node[0].p -= pNode->p;											//出現回数が最大の文字の出現確率から引く。
				if(TBL_Node[0].p <= 0) { DIE(); }										//上記の切り上げが累積してこうなることは起こり得るか？論理的に起こり得ないと思うが念のため確認しておくことにした。もしここで停止したらアルゴリズムを再検討せよ。
			}
		}
		//出現確率(p/65536)を、出現確率の和(cum(x+1))に変換する。
		for(i = 0; i < 256; i++) {
			TBL_Node[i].cum = TBL_Node[i].p;
			if(i) { TBL_Node[i].cum += TBL_Node[i - 1].cum; }
		}
		if(TBL_Node[255].cum != 65536 - 1/*終端文字の出現確率*/) { DIE(); }	//バグ
#if 1 //{{0バイトのデータに対する特例処理。少しだけ確率表を小さくできる。この特例処理は必須ではなく、通常通りの処理を行っても構わない。
		// - 0バイトのデータを圧縮すると、全てのノードのc=0だが、TBL_Node[0].pに出現確率の余りが与えられ、TBL_Node[0].p=65535になる。
		//   そのため、TBL_Node[0]が確率表に出力されてしまう。動作上は問題無いが、無駄である。
		//   そこで、TBL_Node[0].pを明示的に0にすることにより、TBL_Node[0]が確率表に出力されることを防ぐことにした。
		//   尚、TBL_Node[i].cumを0にする必要は無いのだが、判り易さのために0にしておくことにした。動作には関係無い。
		// - 以上の特性処理を行うことによって、0バイトのデータを圧縮した時のサイズが、11バイト⇒8バイトに低減した。
		//   デコーダは、この特例処理を考慮する必要は無い。
		if(!srcBytes) {
			for(i = 0; i < 256; i++) {
				TBL_Node[i].p = TBL_Node[i].cum = 0;
			}
		}
#endif//}}0バイトのデータに対する特例処理。少しだけ確率表を小さくできる。この特例処理は必須ではなく、通常通りの処理を行っても構わない。
		//文字⇒ノード対応表を作成する。
		for(i = 0; i < 256; i++) {
			TBL_Map[TBL_Node[i].x] = i;
		}
	}
	//--- 確率表出力処理 ---
	{
		int i;
		//確率表を出力する。
		//- 確率表の形式は、以下の通り:
		//│+ 0,2 HIBYTE(p(0))	┬上位バイト先行で格納することにした理由は、こうする方がアセンブラ版RangeCoderDecoder_Getc()でインターロックを減らせるからです。
		//│+ 2,2 LOBYTE(p(0))	┘詳細は、アセンブラ版RangeCoderDecoder_Getc()の'工夫した実装'の、'RangeCoderDecoder_Getc_L10〜'のループ区間を参照してください。
		//│+ 4,1 文字0
		//│+ 5,2 HIBYTE(p(1))
		//│+ 7,2 LOBYTE(p(1))
		//│+ 9,1 文字1
		//│      …
		//│+ ?,2 HIBYTE(p(x))
		//│+ ?,2 LOBYTE(p(x))
		//│+ ?,1 文字x
		//│+ ?,2 0		┬p(x)=0で終端を表す。もし0バイトのデータを圧縮して、空の確率表を出力した場合は、空の確率表は{0,0}の2バイトで構成される。
		//│+ ?,2 0		┘
		//│			←p(x)=0の後に文字xは無いことに注意せよ。
		//│〜 ここから圧縮データが開始する 〜
		//- 終端文字は確率表に含めない。
		//  従って、デコーダは確率表を走査して、符号に一致する文字が見つからなければ、終端文字と判断できる。
		for(i = 0; i < 256; i++) {
			ST_RangeCoderNode* pNode = &TBL_Node[i];
			if(!pNode->p) { break; }
			if(dstPos++ < dstBytes) { *dst++ = pNode->p >> 8; }	//HIBYTE(p(x))
			if(dstPos++ < dstBytes) { *dst++ = pNode->p; }		//LOBYTE(p(x))
			if(dstPos++ < dstBytes) { *dst++ = pNode->x; }		//文字x
		}
		if(dstPos++ < dstBytes) { *dst++ = 0; }	//┬p(x)=0で終端を表す。
		if(dstPos++ < dstBytes) { *dst++ = 0; }	//┘
	}
	//--- 圧縮処理 ---
	{
		int buffer =  0;	//初回に'buffer=newBuffer'を行うので初期化不要だが、警告抑制のために初期化することにした。
		int carryN = -1;	//(carryN==-1)は、スタート状態(=bufferが未格納)である事を意味する。
		int L      =  0;
		int R      = -1;
		int i, lo, hi, r, newL;
		for(i = 0; i <= srcBytes; i++) {	//ループ条件が'<'ではなく'<='であることに注意せよ。'i=srcBytes'の時に仮想的な終端文字を出力する。
			//lo=cum(x),hi=cum(x+1)を求める。
			if(i < srcBytes) {		//文字0〜255
				int  x = TBL_Map[src[i]];
				lo = x ? TBL_Node[x - 1].cum : 0;
				hi =     TBL_Node[x    ].cum;
			} else {			//終端文字
				lo = 65536 - 1;		//┬終端文字に(1/65536)の出現確率を与える。
				hi = 65536;		//┘
			}
			if(lo >= hi) { DIE(); }		//バグ
			//Rを更新する。
			r = (unsigned)R >> 16;		//r = (unsigned)R / 65536
			R = r * (hi - lo);												//参考資料のプログラムは、最後の文字に残りの区間を全て与えているが、当実装ではその処理は不要である。当実装において、最後の文字とは終端文字であり、圧縮処理の最終にしか現れない。終端文字に残りの区間を全て与えても 、圧縮率の改善に寄与しないから。
			//Lを更新する。
			newL = L + r * lo;
			if((unsigned)newL < (unsigned)L) {	//繰り上がりが発生したら…
				if(buffer == -1) { DIE(); }	//バグ。bufferに保持している値が繰り上がることは無いはず。
				if(carryN == -1) { DIE(); }	//バグ。スタート状態で繰り上がりが発生することは無いはず。
				//{buffer,FF,FF,…,FF,FF} ⇒ {buffer+1,00,00,…,00,00}
				//        └─carryN─┘               └─carryN─┘
				buffer++;
				if(carryN) {
					//{buffer+1,00,00,…,00,00} ⇒ {buffer+1,00,00,…,00,00}
					//          └─carryN─┘      └──出力する──┘ └→buffer
					do {
						if(dstPos++ < dstBytes) { *dst++ = buffer; }
						buffer = 0;
					} while(--carryN);
				}
			}
			L = newL;
			//Vの上位8ビットが決定し次第、出力する。
			while((unsigned)R < (unsigned)(1 << 24)) {
				int newBuffer = L >> 24;
				//スタート状態(=bufferが未格納)ならば…
				if(carryN == -1) {
					carryN = 0;		//┬スタート状態の直後に、(buffer=-1)となる事も有る得る。その場合、(buffer=-1,carryN=0)で表す。┬スタート状態の直後に、(buffer=-1)となる事は無いような気もしてきた。
					buffer = newBuffer;	//┘(buffer=0,carryN=1)で表すと、この後の処理で不要な(buffer=0)が出力されてしまう問題が生じる。┘いずれにしても、左記の処理で問題なく動作するはず。
				//bufferには最後の0xFFでは無かった値を保存しておき、carryNに0xFFが連続して何回出現回数を保存する。
				//bufferとcarryNを用いて、現在出力待ちの符号は、{buffer,FF,FF,…,FF,FF} と表される。(carryN=0の場合も有る)
				//                                                      └─carryN─┘
				} else if(newBuffer == -1) {
					carryN++;
				} else {
					//{buffer,FF,FF,…,FF,FF},newBuffer
					// │     └─carryN─┘     │
					// └── 出力する──┘     └→buffer
					if(dstPos++ < dstBytes) { *dst++ = buffer; }
					if(carryN) {
						do {
							if(dstPos++ < dstBytes) { *dst++ = -1; }
						} while(--carryN);
					}
					buffer = newBuffer;
				}
				//LとRをシフトする。
				L <<= 8;
				R <<= 8;
			}
		}
		//残っているbuffer,及び,Lを出力する。
		if(carryN != -1) {	//スタート状態(=bufferが未格納)でなければ…							//参考資料のプログラムは、左記の判断を行っておらず、スタート状態(=bufferが未格納)であっても、bufferを出力しているようだ。参考資料のプログラムは、誤りではないか？小さなデータを圧縮して、bufferを格納する前に処理が終了すると、本来は存在しないbufferが出力されてしまい、復元できない圧縮データが生成されると思う。
			if(dstPos++ < dstBytes) { *dst++ = buffer; }
			if(carryN) {
				do {
					if(dstPos++ < dstBytes) { *dst++ = -1; }
				} while(--carryN);
			}
		}
		for(i = 0; i < 4; i++) {
			if(dstPos++ < dstBytes) { *dst++ = L >> 24; }
			L <<= 8;
		}
	}
	//出力バイト数を返す。
	return dstPos;
}
