/*
 *	framrc.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デコーダー
 ****************************************************************************/
//圧縮データ全体をデコードし、圧縮元データを作成する。
// - src,dst共に、アライメント不要。
// - 圧縮元データがdstBytesを超えた場合は、越えた部分は格納しない。
//   格納の可否に関係なく、戻り値は、圧縮元データのバイト数である。
//   この性質を利用して、一回目は(dst=NULL,dstBytes=0)で呼び出し、必要なバッファサイズを確認,確保した後、再度呼び出す方法も可能です。
//   <例>
//   │dstBytes=RangeCoderDecoder_Decode(src,NULL,0);
//   │dst=malloc(dstBytes);
//   │RangeCoderDecoder_Decode(src,dst,dstBytes);
#ifndef PIECE
int RangeCoderDecoder_Decode(const void* src, void* _dst, int dstBytes) {
	ST_RangeCoderDecoder stRangeCoderDecoder;
	unsigned char* dst = _dst;
	int value, dstPos = 0;
	RangeCoderDecoder_Init(&stRangeCoderDecoder, src);			//RangeCoderデコーダーを初期化する。
	while((value = RangeCoderDecoder_Getc(&stRangeCoderDecoder)) != -1) {	//１バイトデコードする。
		if(dstPos++ < dstBytes) { *dst++ = value; }			//圧縮元データを格納する。
	}
	return dstPos;								//圧縮元データのバイト数を返す。
}
#else //PIECE
//アセンブラ版HuffmanDecoder_Decodeの'工夫した実装'とほぼ同じです。詳細はアセンブラ版HuffmanDecoder_Decodeを参照してください。
int RangeCoderDecoder_Decode(const void* src, void* _dst, int dstBytes);
asm("
		.code
		.align		1
		.global		RangeCoderDecoder_Decode
RangeCoderDecoder_Decode:
		pushn		%r3
		xsub		%sp, %sp, 16					;//%sp  := &stRangeCoderDecoder
		ld.w		%r0, %sp					;//%r0  := &stRangeCoderDecoder								%spのままでは、callの遅延スロットで既に変化しているので、%r0にもコピーしておく。
		ld.w		%r1, %r13					;//%r1  := dst
		ld.w		%r2, %r14					;//%r2  := dstBytes
		ld.w		%r13, %r12					;//%r13 := src
		xcall.d		RangeCoderDecoder_Init				;//RangeCoderDecoder_Init(&stRangeCoderDecoder, src)
		ld.w		%r12, %r0					;//%r12 :=                &stRangeCoderDecoder				*delay*
		jp.d		RangeCoderDecoder_Decode_START			;//goto START
		ld.w		%r3, -1						;//%r3  := dstPos = -1							*delay*		最後のループを抜ける時もプレインクリメントする分と相殺するため(-1)に初期化する。
		;//%sp  := &stRangeCoderDecoder
		;//%r0  := &stRangeCoderDecoder
		;//%r1  := dst
		;//%r2  := dstBytes
		;//%r3  := dstPos
RangeCoderDecoder_Decode_LOOP:							;//do {
		cmp		%r3, %r2					;//  if(dstPos < dstBytes) {								プレインクリメントであるが比較条件を(<=)に変更しないよう注意せよ。(-1)に初期化しているのでプレインクリメント分とは相殺済みである。従って比較条件は'素直な実装'と変わらない。
		jrge		2
		 ld.b		[%r1]+, %r10					;//    *dst++ = value }
RangeCoderDecoder_Decode_START:
		xcall.d		RangeCoderDecoder_Getc				;//  %r10 := value = RangeCoderDecoder_Getc(&stRangeCoderDecoder)
		ld.w		%r12, %r0					;//  %r12 :=                                &stRangeCoderDecoder	*delay*
		cmp		%r10, -1					;//} while(value != -1)
		jrne.d		RangeCoderDecoder_Decode_LOOP			;//
		add		%r3, 1						;//  %r3  := dstPos++							*delay*
		ld.w		%r10, %r3					;//%r10 := dstPos
		xadd		%sp, %sp, 16
		popn		%r3
		ret
");
#endif//PIECE
/*--------------------------------------------------------------------------*/
//RangeCoderデコーダーを初期化する。
#ifndef PIECE
void RangeCoderDecoder_Init(ST_RangeCoderDecoder* pRangeCoderDecoder, const void* _src) {
	const unsigned char* src = _src;
	int i, hi, lo, D;
	pRangeCoderDecoder->src = src;		//確率表のアドレスを格納する。
	//--- 確率表を読み飛ばす処理 ---
	do {
		hi = *src++;			//終端を判断するだけなので'<<8'は不要。
		lo = *src++;
		D  = *src++;			//文字xを読み飛ばす。		//最後に取得した値は、D[31:24]となる。
	} while(hi|lo);
	//--- Dの初期値を取得する処理 ---
	for(i = 0; i < 3; i++) {						//D[31:24]は取得済み。D[23: 0]を取得する。
		D = (D << 8) | *src++;
	}
	pRangeCoderDecoder->srcPos = src;	//次に読み出す符号のアドレスを格納する。
	pRangeCoderDecoder->D =  D;
	pRangeCoderDecoder->R = -1;
}
#else //PIECE
void RangeCoderDecoder_Init(ST_RangeCoderDecoder* pRangeCoderDecoder, const void* src);
asm("
		.code
		.align		1
		.global		RangeCoderDecoder_Init
RangeCoderDecoder_Init:
		ld.w		[%r12]+, %r13					;//pRangeCoderDecoder->src = src
RangeCoderDecoder_Init_L10:							;//do {
		ld.ub		%r4, [%r13]+					;//  %r4  := hi = *src++
		ld.ub		%r5, [%r13]+					;//  %r5  := lo = *src++
		ld.ub		%r6, [%r13]+					;//  %r6  := D  = *src++
		or		%r4, %r5					;//  %r4  := hi|lo
		jrne		RangeCoderDecoder_Init_L10			;//} while(  hi|lo)
		ld.w		%r4, 3						;//%r4    := i = 3
RangeCoderDecoder_Init_L20:							;//do {
		sla		%r6, 8						;//  %r6  := D <<= 8
		ld.ub		%r5, [%r13]+					;//  %r5  := lo = *src++
		sub		%r4, 1						;//  %r4  := i--
		jrne.d		RangeCoderDecoder_Init_L20			;//} while(  i)
		or		%r6, %r5					;//  %r6  := D |= lo				*delay*
		ld.w		[%r12]+, %r13					;//pRangeCoderDecoder->srcPos = src
		ld.w		[%r12]+, %r6					;//pRangeCoderDecoder->D =  D
		ld.w		%r9, -1
		ld.w		[%r12], %r9					;//pRangeCoderDecoder->R = -1
		ret
");
#endif//PIECE
/*--------------------------------------------------------------------------*/
//１バイトデコードする。
//圧縮データの終端ならば、(-1)を返す。
#ifndef PIECE
int RangeCoderDecoder_Getc(ST_RangeCoderDecoder* pRangeCoderDecoder) {
	const unsigned char *src, *srcPos;
	int D, R, r, t, cum, hi, lo, p, x;
	//フィールド値を取り出す。
	src    = pRangeCoderDecoder->src;
	srcPos = pRangeCoderDecoder->srcPos;
	D      = pRangeCoderDecoder->D;
	R      = pRangeCoderDecoder->R;
	//--- 展開処理 ---
	r = (unsigned)R >> 16;			//r = (unsigned)R / 65536
	t = (unsigned)D / (unsigned)r;
	cum = 0;
	for(;;) {
		hi = *src++ << 8;
		lo = *src++;
		if(!(p = hi|lo)) { return -1; }	//終端文字ならば-1を返す。この時フィールド値を格納しない。こうすれば何回RangeCoderDecoder_Getc()が呼ばれても-1を返し続ける事ができる。
		x  = *src++;
		if((t -= p) < 0) { break; }	//符号に一致する文字が見つかったら抜ける。
		cum += p;
	}
	D -= r * cum;
	R  = r * p;
	while((unsigned)R < (unsigned)(1 << 24)) {
		D = (D << 8) | *srcPos++;
		R <<= 8;
	}
	//フィールド値を格納する。
//誤//	pRangeCoderDecoder->src    = src;	←srcは変更してはいけない。
	pRangeCoderDecoder->srcPos = srcPos;
	pRangeCoderDecoder->D      = D;
	pRangeCoderDecoder->R      = R;
	return x;
}
#else //PIECE
int RangeCoderDecoder_Getc(ST_RangeCoderDecoder* pRangeCoderDecoder);
#if 0		//'素直な実装'と'工夫した実装'のどちらを使っても結果は同じです。framrc.oをSRAMに配置した場合'工夫した実装'の方が約5%高速になります。詳細は'工夫した実装'の'RangeCoderDecoder_Getc_L10〜'のループ区間のコメントを参照してください。
//□素直な実装。
asm("
		.code
		.align		1
		.global		RangeCoderDecoder_Getc
RangeCoderDecoder_Getc:
		;//%r12 := pRangeCoderDecoder
		ld.w		%r4, %r12			;//%r4  := pRangeCoderDecoder
		ld.w		%r5, [%r4]+			;//%r5  := src    = pRangeCoderDecoder->src
		ld.w		%r6, [%r4]+			;//%r6  := srcPos = pRangeCoderDecoder->srcPos
		ld.w		%r12, [%r4]+			;//%r12 := D      = pRangeCoderDecoder->D
		ld.w		%r13, [%r4]			;//%r13 := R      = pRangeCoderDecoder->R
		sub		%r4, 8				;//%r4  := &pRangeCoderDecoder->srcPos			*anti-interlock*
		srl		%r13, 8				;//%r13 :=     (unsigned)R >> 8
		xcall.d		__udivsi3			;//%r10 := t = (unsigned)D / (unsigned)r					__udivsi3は%r9,%r10,%alr,%ahr,%psr以外を破壊しないことを利用して、レジスタ退避を省略した。⇒clipidiv.s参照
		srl		%r13, 8				;//%r13 := r = (unsigned)R >> 16			*delay*
		ld.w		%r7, 0				;//%r7  := cum = 0
		;//%r4  := &pRangeCoderDecoder->srcPos
		;//%r5  := src
		;//%r6  := srcPos
		;//%r7  := cum
		;//%r10 := t
		;//%r12 := D
		;//%r13 := r
RangeCoderDecoder_Getc_L10:					;//for(;;) {
		ld.ub		%r14, [%r5]+			;//  %r14 := hi = *src++
		ld.ub		%r9, [%r5]			;//  %r9  := lo = *src
		sla		%r14, 8				;//  %r14 := hi <<= 8					*anti-interlock*
		or		%r14, %r9			;//  %r14 := p  = hi|lo
		jreq		RangeCoderDecoder_Getc_L40	;//  if(!p) { return -1 }
		add		%r5, 2				;//  %r5  := src += 2
		sub		%r10, %r14			;//  %r10 := t -= p
		jrge.d		RangeCoderDecoder_Getc_L10	;//  if(t < 0) { break }
		add		%r7, %r14			;//%r7  := cum += p } 					*delay*
		sub		%r7, %r14			;//%r7  := cum -= p
		;//%r4  := &pRangeCoderDecoder->srcPos
		;//%r5  := &x + 1
		;//%r6  := srcPos
		;//%r7  := cum
		;//%r12 := D
		;//%r13 := r
		;//%r14 := p
		mltu.h		%r13, %r7			;//%alr :=      r * cum								r,cum共に65535以下であることが保証できるので、mltu.hを使用する。rが65535以下であることは、すぐ上で「r=(unsigned)R>>16」を行っているから自明である。cumが65535以下であることは、RangeCoderEncoder_Encode()で「TBL_Node[255].cum==65535」を確認している。
		ld.w		%r9, %alr			;//%r9  :=      r * cum
		sub		%r12, %r9			;//%r12 := D -= r * cum
		mltu.h		%r13, %r14			;//%r13 :=      r * p								r,p共に65535以下であることが保証できるので、mltu.hを使用する。pが65535以下であることは、cumが65535以下であるから自明である。
		ld.w		%r13, %alr			;//%r13 := R  = r * p
		ld.w		%r14, 1				;//%r14 :=                        1		─┬─「xcmp %r13,0x1000000」にしても命令数は同じ(3命令)なので、この展開にデメリットは無い。下記の通り実際にループする頻度は低いと思うが、ループした場合のためにループ内の命令を減らす利点は有る。
		rr		%r14, 8				;//%r14 :=                        1 << 24	─┤
RangeCoderDecoder_Getc_L20:					;//						　│
		cmp		%r13, %r14			;//while((unsigned)R < (unsigned)(1 << 24)) {	←┘				「do{〜}while()」形式への変換は行わないことにした。圧縮データの読み込み処理であるから、RangeCoderDecoder_Getc()一回当りに発生する確率は1.0未満であるはず。従って、ループを高速化する効果は低い。実際のところ、「do{〜}while()」に変換すると、末尾の遅延スロットに入れられる命令が無くなり、高速化にならない。
		jruge		RangeCoderDecoder_Getc_L30	;//  
		sla		%r12, 8				;//  %r12 := D = (D << 8) | *srcPos++
		ld.ub		%r9, [%r6]+			;//  
		or		%r12, %r9			;//  
		jp.d		RangeCoderDecoder_Getc_L20	;//}
		sla		%r13, 8				;//%r13 := R <<= 8					*delay*
RangeCoderDecoder_Getc_L30:
		;//%r4  := &pRangeCoderDecoder->srcPos
		;//%r5  := &x + 1
		;//%r6  := srcPos
		;//%r12 := D
		;//%r13 := R
		ld.w		[%r4]+, %r6			;//pRangeCoderDecoder->srcPos = srcPos
		ld.w		[%r4]+, %r12			;//pRangeCoderDecoder->R      = R
		ld.w		[%r4], %r13			;//pRangeCoderDecoder->D      = D
		sub		%r5, 1				;//%r5  := &x
		ld.ub		%r10, [%r5]			;//%r10 :=  x
		ret						;//return   x
RangeCoderDecoder_Getc_L40:
		ret.d						;//return  -1
		ld.w		%r10, -1			;//%r10 := -1						*delay*
");
#else		//'素直な実装'と'工夫した実装'のどちらを使っても結果は同じです。framrc.oをSRAMに配置した場合'工夫した実装'の方が約5%高速になります。詳細は'工夫した実装'の'RangeCoderDecoder_Getc_L10〜'のループ区間のコメントを参照してください。
//□工夫した実装。
asm("
		.code
		.align		1
		.global		RangeCoderDecoder_Getc
RangeCoderDecoder_Getc:
		;//%r12 := pRangeCoderDecoder
		ld.w		%r4, %r12			;//%r4  := pRangeCoderDecoder
		ld.w		%r5, [%r4]+			;//%r5  := src    = pRangeCoderDecoder->src
		ld.w		%r6, [%r4]+			;//%r6  := srcPos = pRangeCoderDecoder->srcPos
		ld.w		%r12, [%r4]+			;//%r12 := D      = pRangeCoderDecoder->D
		ld.w		%r13, [%r4]			;//%r13 := R      = pRangeCoderDecoder->R
		sub		%r4, 8				;//%r4  := &pRangeCoderDecoder->srcPos			*anti-interlock*
		srl		%r13, 8				;//%r13 :=     (unsigned)R >> 8
		xcall.d		__udivsi3			;//%r10 := t = (unsigned)D / (unsigned)r					__udivsi3は%r9,%r10,%alr,%ahr,%psr以外を破壊しないことを利用して、レジスタ退避を省略した。⇒clipidiv.s参照
		srl		%r13, 8				;//%r13 := r = (unsigned)R >> 16			*delay*
		ld.w		%r7, %r10			;//%r7  := save_t = t
		;//%r4  := &pRangeCoderDecoder->srcPos
		;//%r5  := src
		;//%r6  := srcPos
		;//%r7  := save_t
		;//%r10 := t
		;//%r12 := D
		;//%r13 := r
RangeCoderDecoder_Getc_L10:					;//for(;;) {									┐
		ld.ub		%r14, [%r5]+			;//  %r14 := hi = *src++							│
		ld.ub		%r9, [%r5]			;//  %r9  := lo = *src								│
		sla		%r14, 8				;//  %r14 := hi <<= 8					*anti-interlock*	│この区間が最も速度に影響するループなので、この区間を最大限に高速化する工夫を行いました。
		or		%r14, %r9			;//  %r14 := p  = hi|lo								│'素直な実装'ではこの区間が10サイクル,'工夫した実装'ではこの区間が9サイクルになりました。
		jreq		RangeCoderDecoder_Getc_L40	;//  if(!p) { return -1 }							│'素直な実装'に較べて、'工夫した実装'の方が約5%高速になりました。
		sub		%r10, %r14			;//  %r10 := t -= p								│
		jrge.d		RangeCoderDecoder_Getc_L10	;//  if(t < 0) { break }							│
		add		%r5, 2				;//%r5  := src += 2 }					*delay*			┘
		sub		%r7, %r10			;//%r7  :=       save_t - t     = cum(x+1)相当
		sub		%r7, %r14			;//%r7  := cum = save_t - t - p = cum(x  )相当
		;//%r4  := &pRangeCoderDecoder->srcPos
		;//%r5  := &x + 1
		;//%r6  := srcPos
		;//%r7  := cum
		;//%r12 := D
		;//%r13 := r
		;//%r14 := p
		mltu.h		%r13, %r7			;//%alr :=      r * cum								r,cum共に65535以下であることが保証できるので、mltu.hを使用する。rが65535以下であることは、すぐ上で「r=(unsigned)R>>16」を行っているから自明である。cumが65535以下であることは、RangeCoderEncoder_Encode()で「TBL_Node[255].cum==65535」を確認している。
		ld.w		%r9, %alr			;//%r9  :=      r * cum
		sub		%r12, %r9			;//%r12 := D -= r * cum
		mltu.h		%r13, %r14			;//%r13 :=      r * p								r,p共に65535以下であることが保証できるので、mltu.hを使用する。pが65535以下であることは、cumが65535以下であるから自明である。
		ld.w		%r13, %alr			;//%r13 := R  = r * p
		ld.w		%r14, 1				;//%r14 :=                        1		─┬─「xcmp %r13,0x1000000」にしても命令数は同じ(3命令)なので、この展開にデメリットは無い。下記の通り実際にループする頻度は低いと思うが、ループした場合のためにループ内の命令を減らす利点は有る。
		rr		%r14, 8				;//%r14 :=                        1 << 24	─┤
RangeCoderDecoder_Getc_L20:					;//						　│
		cmp		%r13, %r14			;//while((unsigned)R < (unsigned)(1 << 24)) {	←┘				「do{〜}while()」形式への変換は行わないことにした。圧縮データの読み込み処理であるから、RangeCoderDecoder_Getc()一回当りに発生する確率は1.0未満であるはず。従って、ループを高速化する効果は低い。実際のところ、「do{〜}while()」に変換すると、末尾の遅延スロットに入れられる命令が無くなり、高速化にならない。
		jruge		RangeCoderDecoder_Getc_L30	;//  
		sla		%r12, 8				;//  %r12 := D = (D << 8) | *srcPos++
		ld.ub		%r9, [%r6]+			;//  
		or		%r12, %r9			;//  
		jp.d		RangeCoderDecoder_Getc_L20	;//}
		sla		%r13, 8				;//%r13 := R <<= 8					*delay*
RangeCoderDecoder_Getc_L30:
		;//%r4  := &pRangeCoderDecoder->srcPos
		;//%r5  := &x + 1
		;//%r6  := srcPos
		;//%r12 := D
		;//%r13 := R
		ld.w		[%r4]+, %r6			;//pRangeCoderDecoder->srcPos = srcPos
		ld.w		[%r4]+, %r12			;//pRangeCoderDecoder->R      = R
		ld.w		[%r4], %r13			;//pRangeCoderDecoder->D      = D
		sub		%r5, 1				;//%r5  := &x
		ld.ub		%r10, [%r5]			;//%r10 :=  x
		ret						;//return   x
RangeCoderDecoder_Getc_L40:
		ret.d						;//return  -1
		ld.w		%r10, -1			;//%r10 := -1						*delay*
");
#endif
#endif//PIECE
