/*
 *	clipdrh.c
 *
 *	差分圧縮⇒連長圧縮⇒ハフマン圧縮
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2016 Naoyuki Sawa
 *
 *	* Mon Nov 24 10:36:38 JST 2014 Naoyuki Sawa
 *	- 1st リリース。
 *	- ハフマン圧縮の応用例として、作成しました。
 *	  連続して変化するようなデータを圧縮する際に、ハフマン圧縮だけを単独で使用するよりも圧縮率が良くなります。
 *	  今後、LEDデコーダーで利用することを想定しています。
 *	- 当モジュールで工夫した点は、連長と差分の符号をマージした事です。
 *	  連長と差分は、別々の符号表で圧縮します。(連長と差分の出現値は偏りの傾向が違うので、別々の符号表で圧縮する方が圧縮率が良いと思うから)
 *	  一方、連長と差分の符号並びは分けない方が、次に読み出す符号のビット位置を一つで管理でき、都合が良いです。
 *	  従って、連長と差分の符号が交互に取得できるよう、マージしました。
 *	  確か、一般的な圧縮形式(zipやlzh等)も、そうなっていたと思います。
 *	- 連長圧縮が効かないデータだと、ハフマン圧縮よりも単純に2倍の処理時間がかかります。(連長と差分の復号化を行う必要があるため)
 *	  データの特性によって、圧縮の方式を慎重に選択する必要があります。
 *	* Thu Nov 27 21:49:37 JST 2014 Naoyuki Sawa
 *	- DeltaRunHuffmanDecoder_Decode(),DeltaRunHuffmanDecoder_Init(),DeltaRunHuffmanDecoder_Getc()をアセンブラ化しました。
 *	  DeltaRunHuffmanDecoder_Decode()で、約50KB⇒約64KBの展開を行った時の速度が、約2.237秒⇒約1.487秒に高速化しました。(Clock=48MHz,Code=SRAM,Stack=FRAM)
 *	- まだ、アセンブラ版DeltaRunHuffmanDecoder_Decode(),DeltaRunHuffmanDecoder_Init(),DeltaRunHuffmanDecoder_Getc()の動作確認を、充分に行っていません。	//┐
 *	  引き続き、アセンブラ版DeltaRunHuffmanDecoder_Decode(),DeltaRunHuffmanDecoder_Init(),DeltaRunHuffmanDecoder_Getc()の動作確認を行う予定です。		//※TODO:2014/11/27時点未完了。充分に動作確認したらこのコメントは消せ。
 *	  特に、アセンブラ版DeltaRunHuffmanDecoder_Getc()の動作確認を、重点的に行う必要があります。								//┘
 *	* Tue Sep 06 21:06:46 JST 2016 Naoyuki Sawa
 *	- DeltaRunHuffmanEncoder_GetHdrSize()が、(int)でアドレス演算を行っていたのを、(char*)で行うように修正しました。
 *	  64ビット対応のための準備ですが、32ビットでも(char*)で行う方が本当は正しいからです。
 *	  とは言え、32ビットではどちらでも同じ結果になるので、既存の32ビットコードには影響有りません。
 *	* Thu Sep 29 21:37:05 JST 2016 Naoyuki Sawa
 *	- Hewではエンコーダーを含めないようにしました。
 */
#include "clip.h"

//[note]
//詳細なコメントは省略した。
//アルゴリズムの説明はcliphfm.c,framhfm.cを参照せよ。

#ifndef __RENESAS__	//{{2016/09/29追加:Hewではエンコーダーを含めないようにしました。}}
/****************************************************************************
 *	差分圧縮⇒連長圧縮⇒ハフマン圧縮エンコーダー
 ****************************************************************************/
//符号表のバイト数を取得する。
static int DeltaRunHuffmanEncoder_GetHdrSize(const void* _src) {
	const unsigned char* hdr = _src;
	int codeLenMask, codeLenCount;
	codeLenMask = *(*(int**)&hdr)++;
	do {
		if(codeLenMask < 0) {
			codeLenCount = *hdr++ + 1;
			hdr += codeLenCount;
		}
	} while(codeLenMask <<= 1);
//{{2016/09/06変更:DeltaRunHuffmanEncoder_GetHdrSize()が、(int)でアドレス演算を行っていたのを、(char*)で行うように修正しました。
//	return (((int)hdr - (int)_src) + 3) & ~3;	//32bit境界まで進める。
//↓2016/09/06変更:DeltaRunHuffmanEncoder_GetHdrSize()が、(int)でアドレス演算を行っていたのを、(char*)で行うように修正しました。
	return (((char*)hdr - (char*)_src) + 3) & ~3;	//32bit境界まで進める。
//}}2016/09/06変更:DeltaRunHuffmanEncoder_GetHdrSize()が、(int)でアドレス演算を行っていたのを、(char*)で行うように修正しました。
}
/*--------------------------------------------------------------------------*/
//次のハフマン符号を取得する。
//圧縮データの終端ならば、(-1)を返す。
static int DeltaRunHuffmanEncoder_GetCode(ST_HuffmanDecoder* pHuffmanDecoder, int* pCodeLen) {
	const unsigned char* hdr = pHuffmanDecoder->src;
	int code, codeLenMask, codeLen, codeTmp1, codeTmp2, codeLenCount;
	code = bitarray_msb1st_get(pHuffmanDecoder->src, pHuffmanDecoder->srcPos, 32);
	codeLenMask = *(*(int**)&hdr)++;
	codeLen = codeTmp1 = codeTmp2 = 0;
	do {
		codeTmp1 <<= 1;
		codeTmp2 = (codeTmp2 << 1) | (code < 0);
		code <<= 1;
		codeLen++;
		if(codeLenMask < 0) {
			codeLenCount = *hdr++ + 1;
			hdr      += codeLenCount;
			codeTmp1 += codeLenCount;
			if(codeTmp2 < codeTmp1) {
				pHuffmanDecoder->srcPos += codeLen;
				*pCodeLen = codeLen;
				return codeTmp2;
			}
		}
	} while(codeLenMask <<= 1);
	return -1;
}
/*--------------------------------------------------------------------------*/
//差分圧縮⇒連長圧縮⇒ハフマン圧縮エンコードを行う。
//圧縮データがdstBytesを超えた場合は、越えた部分は格納しない。
// - 値の実質バイト数が8bit未満である場合は、呼び出し側で上詰めにシフトしておけ。
//   上詰めにシフトしておくことによって、差分の±がラップアラウンド同じになる値が生じ、圧縮率がより向上する。
// - データ構造は下図のとおり:
//
//	┌──────┐32bit境界
//	│　　　　　　│
//	│連長の符号表│
//	│　　　　　　│
//	├──────┤
//	│(パディング)│
//	├──────┤32bit境界
//	│　　　　　　│
//	│差分の符号表│
//	│　　　　　　│
//	├──────┤
//	│(パディング)│
//	├──────┤32bit境界
//	│ 連長の符号 │
//	│ 差分の符号 │
//	│ 連長の符号 │
//	│ 差分の符号 │
//	│ 　　・　　 │
//	│ 　　・　　 │
//	│ 　　・　　 │
//	│ 連長の符号 │
//	│ 差分の符号 │
//	│　終端符号　│
//	├──────┤
//	│(パディング)│
//	└──────┘32bit境界
//
int DeltaRunHuffmanEncoder_Encode(const void* _src, int srcBytes, void* _dst, int dstBytes) {
	const unsigned char* src = _src;
	      unsigned char* dst = _dst;
	unsigned char *pDelta, *pRun1, *pRun2, *pHuffman1, *pHuffman2;
	int i, nRun, nHuffman1, nHuffman2, nHdr1, nHdr2, dstBits, dstPos;
	ST_HuffmanDecoder stHuffmanDecoder1, stHuffmanDecoder2;
	//--- 差分圧縮 ---
	if(!(pDelta = calloc(srcBytes, 1))) { DIE(); }
	for(i = 0; i < srcBytes; i++) {
		pDelta[i] = src[i];
		if(i) { pDelta[i] -= src[i - 1]; }
	}
	//--- 連長圧縮 ---
	if(!(pRun1 = calloc(srcBytes, 1))) { DIE(); }	//連長
	if(!(pRun2 = calloc(srcBytes, 1))) { DIE(); }	//差分
	nRun = 0;
	for(i = 0; i < srcBytes; i++) {
		if(nRun && (pRun1[nRun - 1] != 255) && (pRun2[nRun - 1] == pDelta[i])) {
			pRun1[nRun - 1]++;
		} else {
			pRun2[nRun++] = pDelta[i];
		}
	}
	//--- ハフマン圧縮 ---
	nHuffman1 = HuffmanEncoder_Encode(pRun1, nRun, NULL, 0);	//連長
	if(!(pHuffman1 = calloc(nHuffman1, 1))) { DIE(); }
	HuffmanEncoder_Encode(pRun1, nRun, pHuffman1, nHuffman1);
	nHuffman2 = HuffmanEncoder_Encode(pRun2, nRun, NULL, 0);	//差分
	if(!(pHuffman2 = calloc(nHuffman2, 1))) { DIE(); }
	HuffmanEncoder_Encode(pRun2, nRun, pHuffman2, nHuffman2);
	//符号表のバイト数を取得する。
	nHdr1 = DeltaRunHuffmanEncoder_GetHdrSize(pHuffman1);	//連長
	nHdr2 = DeltaRunHuffmanEncoder_GetHdrSize(pHuffman2);	//差分
	//符号表をマージする。
	if((nHdr1 + nHdr2) <= dstBytes) {
		memcpy(dst +     0, pHuffman1, nHdr1);	//連長
		memcpy(dst + nHdr1, pHuffman2, nHdr2);	//差分
	}
	dstBits = dstBytes << 3;
	dstPos  = (nHdr1 + nHdr2) << 3;
	//データをマージする。
	HuffmanDecoder_Init(&stHuffmanDecoder1, pHuffman1);	//連長
	HuffmanDecoder_Init(&stHuffmanDecoder2, pHuffman2);	//差分
	for(;;) {
		int codeLen1, codeLen2;
		int code1 = DeltaRunHuffmanEncoder_GetCode(&stHuffmanDecoder1, &codeLen1);	//連長
		int code2 = DeltaRunHuffmanEncoder_GetCode(&stHuffmanDecoder2, &codeLen2);	//差分
		if((code1 ^ code2) < 0) { DIE(); }	//同時に終了しなければバグ。
		if(code1 == -1) { break; }
		if((dstPos + codeLen1) <= dstBits) {
			bitarray_msb1st_set(dst, dstPos, codeLen1, code1);	//連長
		}
		dstPos += codeLen1;
		if((dstPos + codeLen2) <= dstBits) {
			bitarray_msb1st_set(dst, dstPos, codeLen2, code2);	//差分
		}
		dstPos += codeLen2;
	}
	if((dstPos + 32) <= dstBits) {
		bitarray_msb1st_set(dst, dstPos, 32, -1);	//本来は連長の符号表の終端符号を使用すべきだが、(-1)でも確実に終端符号と見なされるので問題無い。いずれにせよ、終端符号は32bit分出力しておく必要があるので、無駄は生じない。
	}
	dstPos += 32;
	//圧縮データの部分は、bitarray_msb1st_getでアクセスするので、32bit単位に切上げておく必要が有る。
	if(dstPos & 31) {
		int codeLen = 32 - (dstPos & 31);
		if((dstPos + codeLen) <= dstBits) {
			bitarray_msb1st_set(dst, dstPos, codeLen, 0);	//圧縮データの余りのビットは、不定値でも構わないが、判り易さのために、0で埋めておくことにした。
		}
		dstPos += codeLen;
	}
	//メモリを開放する。
	free(pDelta);
	free(pRun1);
	free(pRun2);
	free(pHuffman1);
	free(pHuffman2);
	//出力バイト数を返す。
	return dstPos >> 3;
}
#endif//__RENESAS__	//{{2016/09/29追加:Hewではエンコーダーを含めないようにしました。}}
