/*
 *	frambpe.c
 *
 *	Byte Pair Encoding
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2015 Naoyuki Sawa
 *
 *	* Thu Jan 29 21:20:19 JST 2015 Naoyuki Sawa
 *	- 1st リリース。
 *	- 下記の資料を参考にさせて頂きました。
 *	  「Vector - bpe - BPE圧縮/展開するコマンドラインツール」(http://www.vector.co.jp/soft/dl/winnt/util/se498916.html)
 *	  「ひそかにぐあんをめぐらして - Byte Pair Encoding・その１」(http://musyozoku211.blog118.fc2.com/blog-entry-8.html)
 *	* Fri Jan 30 21:08:25 JST 2015 Naoyuki Sawa
 *	- 「１バイトづつ展開する関数(展開ストリーム)」を高速化するために、大幅な変更を行いました。
 *	  データの特性に関係無く、「１バイトづつ展開する関数(展開ストリーム)」が常に安定した速度で動作するようになりました。
 *	  今回の変更によって、僅かに圧縮率が低下しましたが、ほとんど無視できるレベルだと思います。
 */
#include "clip.h"

/****************************************************************************
 *	BytePairEncodingデコーダー
 ****************************************************************************/
//全体を一度で展開する関数
#ifndef PIECE
int BytePairEncodingDecoder_Decode(const void* _src, void* _dst, int dstCap) {
//「全体を一度で展開する処理に最適化した実装」と「１バイトづつ展開する関数を使って全体を展開する実装」のどちらを使用しても、結果は同じです。
#if 0	//「全体を一度で展開する処理に最適化した実装」
	const unsigned char* src = _src, *charTbl, *pairTbl;
	      unsigned char* dst = _dst;
	int c, nChar, nPair, dstLen = 0, lev = 0;
	unsigned char stk[FIELD_SIZEOF(ST_BytePairEncodingDecoder,stk)];
	//--- 全体ループ ---
	while((nChar = *src++)) {	//ブロックヘッダの、文字に割り当てられた符号の数を取得する。0ならば終端ブロックである。
		nPair = *src++;		//ブロックヘッダの、ペアに割り当てられた符号の数を取得する。
		if((unsigned)(nChar + nPair) > (unsigned)255) { DIE(); }	//終端符号(符号[0])を除き、文字に割り当てられた符号の数と、ペアに割り当てられた符号の数の合計は、255以下であるはず。
		charTbl = src;		//ブロックヘッダの、変換表の文字の部分のアドレスを保存する。
		src += nChar;		//ブロックヘッダの、変換表の文字の部分をスキップする。
		pairTbl = src;		//ブロックヘッダの、変換表のペアの部分のアドレスを保存する。
		src += nPair << 1;	//ブロックヘッダの、変換表のペアの部分をスキップする。
		//--- ブロック内ループ ---
		while((c = *src++)) {	//符号を一個取り出す。終端符号(符号[0])でなければ…
			for(;;) {
				c--;						//文字に割り当てられた最初の符号からの差分に変換する。
				if((unsigned)c <  (unsigned)nChar) {
					if(dstLen < dstCap) { *dst++ = charTbl[c]; } dstLen++;	//文字を取得する。この時点でptr[0]はペアに割り当てられた符号の数を指しており、文字の符号が1ベースである事と相殺する。
					if(!lev) { break; }			//スタックに文字が残っていなければ、抜ける。
					c = stk[--lev];				//スタックの文字を取り出す。
					continue;				//ループの先頭へ。
				}
				c -= nChar;					//ペアに割り当てられた最初の符号からの差分に変換する。
				if((unsigned)c >= (unsigned)nPair) { DIE(); }	//ペアに割り当てられた符号を超えていたらデータエラー。
				c <<= 1;
				if((unsigned)lev >= (unsigned)FIELD_SIZEOF(ST_BytePairEncodingDecoder,stk)) { DIE(); }	//データエラー
				stk[lev++] = pairTbl[c + 0];			//ペアの後続符号をスタックに積む。				//┬デコーダを最適化するためにペアの変換表は{後続符号,先行符号}の順となっている。
				c =          pairTbl[c + 1];			//ペアの先行符号をスタックに積み、即取り出す事と同等。		//┘clipbpe.cのBytePairEncodingEncoder_EncodeSub()の実装を参照せよ。
			}
		}
	}
	return dstLen;	//展開後の出力サイズを返す。
#else	//「１バイトづつ展開する関数を使って全体を展開する実装」
	unsigned char* dst = _dst;
	int c, dstLen = 0;
	ST_BytePairEncodingDecoder stDecoder;
	BytePairEncodingDecoder_Init(&stDecoder, _src);
	while((c = BytePairEncodingDecoder_Getc(&stDecoder)) != -1) {
		if(dstLen++ < dstCap) { *dst++ = c; }
	}
	return dstLen;
#endif
}
#else //PIECE
int BytePairEncodingDecoder_Decode(const void* _src, void* _dst, int dstCap);
asm("
		.code
		.align		1
		.global		BytePairEncodingDecoder_Decode
BytePairEncodingDecoder_Decode:
		pushn		%r3
		xsub		%sp, %sp, 16				;//%sp  := &stDecoder
		ld.w		%r0, %sp				;//%r0  := &stDecoder								%spのままでは、callの遅延スロットで既に変化しているので、%r0にもコピーしておく。
		ld.w		%r1, %r13				;//%r1  := dst
		ld.w		%r2, %r14				;//%r2  := dstCap
		ld.w		%r13, %r12				;//%r13 :=                                  src
		xcall.d		BytePairEncodingDecoder_Init		;//BytePairEncodingDecoder_Init(&stDecoder, src)
		ld.w		%r12, %r0				;//%r12 :=                      &stDecoder			*delay*
		jp.d		BytePairEncodingDecoder_Decode_START	;//goto START
		ld.w		%r3, -1					;//%r3  := dstLen = -1						*delay*		最後のループを抜ける時もプレインクリメントする分と相殺するため(-1)に初期化する。
		;//%sp  := &stDecoder
		;//%r0  := &stDecoder
		;//%r1  := dst
		;//%r2  := dstCap
		;//%r3  := dstLen
BytePairEncodingDecoder_Decode_LOOP:					;//do {
		cmp		%r3, %r2				;//  if(dstLen < dstCap) {							プレインクリメントであるが比較条件を(<=)に変更しないよう注意せよ。(-1)に初期化しているのでプレインクリメント分とは相殺済みである。
		jrge		2					;//    
		 ld.b		[%r1]+, %r10				;//    *dst++ = c }
BytePairEncodingDecoder_Decode_START:					;//  
		xcall.d		BytePairEncodingDecoder_Getc		;//  %r10 := c = BytePairEncodingDecoder_Getc(&stDecoder)
		ld.w		%r12, %r0				;//  %r12 :=                                  &stDecoder	*delay*
		cmp		%r10, -1				;//} while(c != -1)
		jrne.d		BytePairEncodingDecoder_Decode_LOOP	;//  
		add		%r3, 1					;//  %r3  := dstLen++						*delay*
		ld.w		%r10, %r3				;//%r10 := dstLen
		xadd		%sp, %sp, 16
		popn		%r3
		ret
");
#endif//PIECE
/*--------------------------------------------------------------------------*/
//１バイトづつ展開する関数(展開ストリーム)
#ifndef PIECE
void BytePairEncodingDecoder_Init(ST_BytePairEncodingDecoder* pDecoder, const void* _src) {
	pDecoder->blk = _src;	//現在のブロック
	pDecoder->ofs = 0;	//現在のブロック内の走査位置オフセット
	pDecoder->lev = 0;	//スタックレベル
}
#else //PIECE
void BytePairEncodingDecoder_Init(ST_BytePairEncodingDecoder* pDecoder, const void* _src);
asm("
		.code
		.align		1
		.global		BytePairEncodingDecoder_Init
BytePairEncodingDecoder_Init:
		ld.w		[%r12]+, %r13				;//pDecoder->blk = _src
		ld.w		[%r12], %r8				;//pDecoder->ofs = 0, pDecoder->lev = 0, pDecoder->stk[0] = 0(ﾀﾞﾐｰ)
		ret
");
#endif//PIECE
#ifndef PIECE
int BytePairEncodingDecoder_Getc(ST_BytePairEncodingDecoder* pDecoder) {
	int c, ofs, lev, nChar, nPair;
	const unsigned char *blk, *charTbl, *pairTbl;
	      unsigned char *sp;
	//--- 符号を取り出す処理 ---
	blk = pDecoder->blk;		//現在のブロック			取り出す
	ofs = pDecoder->ofs;		//現在のブロック内の走査位置オフセット	取り出す	'if(!lev){〜}'のブロック内だけで参照するので'if(!lev){〜}'のブロックの先頭で取り出しても良いのだが、フィールド並びがblk,ofs,levの順なのでここで常に取り出す方が却って効率が良い。
	lev = pDecoder->lev;		//スタックレベル			取り出す
	sp  = pDecoder->stk + lev;	//スタックポインタ
	if(!lev) {	//スタックが空ならば…
		const unsigned char* p = blk + ofs;		//現在のブロック内の走査位置アドレス
		for(;;) {
			if(p == blk) {				//ブロック先頭ならば…
				nChar = *p++;			//ブロックヘッダの、文字に割り当てられた符号の数を取得する。
				if(!nChar) { return -1; }	//文字に割り当てられた符号の数が0ならば、終端ブロックである。
				nPair = *p++;			//ブロックヘッダの、ペアに割り当てられた符号の数を取得する。
				if((unsigned)(nChar + nPair) > (unsigned)255) { DIE(); }	//終端符号(符号[0])を除き、文字に割り当てられた符号の数と、ペアに割り当てられた符号の数の合計は、255以下であるはず。
				p += nChar;			//ブロックヘッダの、変換表の文字の部分をスキップする。
				p += nPair << 1;		//ブロックヘッダの、変換表のペアの部分をスキップする。
			}
			if((c = *p++)) { break; }		//符号を取り出し、終端符号(符号[0])でなければ抜ける。
			blk = p;				//終端符号(符号[0])だったので、次のブロックへ進める。
		}
		pDecoder->blk =     blk;	//現在のブロック			書き戻す
		pDecoder->ofs = p - blk;	//現在のブロック内の走査位置オフセット	書き戻す
		*sp++ = c;	//スタックに符号を積む。
	}
	c = *--sp;		//スタックから符号を取り出す。
	//--- 符号を復号する処理 ---
	nChar = *blk++;		//ブロックヘッダの、文字に割り当てられた符号の数を取得する。
	nPair = *blk++;		//ブロックヘッダの、ペアに割り当てられた符号の数を取得する。
	if((unsigned)(nChar + nPair) > (unsigned)255) { DIE(); }	//終端符号(符号[0])を除き、文字に割り当てられた符号の数と、ペアに割り当てられた符号の数の合計は、255以下であるはず。
	charTbl = blk;		//ブロックヘッダの、変換表の文字の部分のアドレスを保存する。
	blk += nChar;		//ブロックヘッダの、変換表の文字の部分をスキップする。
	pairTbl = blk;		//ブロックヘッダの、変換表のペアの部分のアドレスを保存する。
	for(;;) {
		c--;						//文字に割り当てられた最初の符号からの差分に変換する。
		if((unsigned)c <  (unsigned)nChar) { break; }	//文字に割り当てられた符号ならば、抜ける。
		c -= nChar;					//ペアに割り当てられた最初の符号からの差分に変換する。
		if((unsigned)c >= (unsigned)nPair) { DIE(); }	//ペアに割り当てられた符号を超えていたらデータエラー。
		c <<= 1;
		if((unsigned)(sp - pDecoder->stk) >= (unsigned)FIELD_SIZEOF(ST_BytePairEncodingDecoder,stk)) { DIE(); }	//データエラー
		*sp++ = pairTbl[c + 0];		//ペアの後続符号をスタックに積む。				//┬デコーダを最適化するためにペアの変換表は{後続符号,先行符号}の順となっている。
		c     = pairTbl[c + 1];		//ペアの先行符号をスタックに積み、即取り出す事と同等。		//┘clipbpe.cのBytePairEncodingEncoder_EncodeSub()の実装を参照せよ。
	}
	pDecoder->lev = sp - pDecoder->stk;	//スタックレベル			書き戻す
	return charTbl[c];	//変換表の文字の部分を使用して、符号を文字に変換して返す。
}
#else //PIECE
int BytePairEncodingDecoder_Getc(ST_BytePairEncodingDecoder* pDecoder);
asm("
		.code
		.align		1
		.global		BytePairEncodingDecoder_Getc
BytePairEncodingDecoder_Getc:
		ld.w		%r10, -1				;//%r10 := -1
		;//--- 符号を取り出す処理 ---
		;//%r10 := -1
		;//%r12 := pDecoder
		ld.w		%r4, [%r12]+				;//%r4  := blk = pDecoder->blk
		ld.uh		%r5, [%r12]+				;//%r5  := ofs = pDecoder->ofs
		ld.ub		%r6, [%r12]+				;//%r6  := lev = pDecoder->lev, %r12 := stk = pDecoder->stk
		cmp		%r6, 0					;//if(!lev) {
		jrne.d		BytePairEncodingDecoder_Getc_L40	;//  
		add		%r6, %r12				;//%r6  := sp  = stk + lev					*delay*
		add		%r5, %r4				;//  %r5  := p = blk + ofs
BytePairEncodingDecoder_Getc_L10:					;//  for(;;) {
		cmp		%r5, %r4				;//    if(p == blk) {
		jrne		BytePairEncodingDecoder_Getc_L20	;//      
		ld.ub		%r7, [%r5]+				;//      %r7  := nChar = *p++
		cmp		%r7, 0					;//      if(!nChar) { return -1 }
		jreq		BytePairEncodingDecoder_Getc_RET	;//      
		ld.ub		%r9, [%r5]+				;//      %r9  := nPair = *p++
		add		%r5, %r7				;//      %r5  := p += nChar
		sla		%r9, 1					;//      %r9  :=      nPair << 1
		add		%r5, %r9				;//      %r5  := p += nPair << 1
BytePairEncodingDecoder_Getc_L20:					;//    }
		ld.ub		%r7, [%r5]+				;//    %r7  := c = *p++
		rr		%r7, 8					;//    %r7[31:24] := c, %psr(Z) := !c
		jrne		BytePairEncodingDecoder_Getc_L30	;//    if(c) { break }
		jp.d		BytePairEncodingDecoder_Getc_L10	;//  }
		ld.w		%r4, %r5				;//    %r4  := blk = p						*delay*
BytePairEncodingDecoder_Getc_L30:					;//  
		sub		%r5, %r4				;//  %r5[15: 0] := ofs = p - blk
		or		%r5, %r7				;//  %r5[31:24] := c
		sub		%r6, 7					;//  %r6  := pDecoder
		ld.w		[%r6]+, %r4				;//  pDecoder->blk = blk
		ld.w		[%r6]+, %r5				;//  pDecoder->ofs = ofs, pDecoder->lev = 0(ﾀﾞﾐｰ), pDecoder->stk[0] = c, %r6 := sp = &pDecoder->stk[1]
BytePairEncodingDecoder_Getc_L40:					;//}
		sub		%r6, 1					;//%r6  :=    --sp
		ld.ub		%r5, [%r6]				;//%r5  := c = *sp
		;//--- 符号を復号する処理 ---
		;//%r4  := blk
		;//%r5  := c
		;//%r6  := sp
		;//%r12 := stk
		ld.ub		%r7, [%r4]+				;//%r7  := nChar = *blk++
		add		%r4, 1					;//%r4  := charTbl
BytePairEncodingDecoder_Getc_L50:					;//for(;;) {
		cmp		%r5, %r7				;//  if((unsigned)c <= (unsigned)nChar) { break }
		jrule.d		BytePairEncodingDecoder_Getc_L60	;//  
		sub		%r5, 1					;//  %r5  := c--						*delay*
		sla		%r5, 1					;//  %r5  := c <<= 1
		add		%r5, %r4				;//  %r5  := charTbl + c
		sub		%r5, %r7				;//  %r5  := charTbl + c - nChar = &pairTbl[c]
		ld.ub		%r9, [%r5]+				;//  %r9  := c' = pairTbl[c+0]		//┬デコーダを最適化するためにペアの変換表は{後続符号,先行符号}の順となっている。
		ld.ub		%r5, [%r5]				;//  %r5  := c  = pairTbl[c+1]		//┘clipbpe.cのBytePairEncodingEncoder_EncodeSub()の実装を参照せよ。
		ld.b		[%r6]+, %r9				;//  *sp++ = c'
		jp		BytePairEncodingDecoder_Getc_L50	;//}
BytePairEncodingDecoder_Getc_L60:					;//
		sub		%r6, %r12				;//%r6  := lev = sp - stk
		sub		%r12, 1					;//%r12 := &pDecoder->lev
		ld.b		[%r12], %r6				;//         pDecoder->lev = lev
		add		%r5, %r4				;//%r5  := &charTbl[c]
		ld.ub		%r10, [%r5]				;//%r10 :=  charTbl[c]
BytePairEncodingDecoder_Getc_RET:
		ret
");
#endif//PIECE
