/*	
 *	clipbary.h
 *
 *	汎用ビット配列
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2015 Naoyuki Sawa
 *
 *	* Tue Dec 20 00:06:44 JST 2011 Naoyuki Sawa
 *	- 1st リリース。
 *	* Thu Nov 20 20:22:14 JST 2014 Naoyuki Sawa
 *	- 既存のLSB先行バージョンに加えて、MSB先行バージョンを作成しました。
 *	- 既存のbitarray_get(),bitarray_set()を、bitarray_lsb1st_get(),bitarray_lsb1st_set()に名称変更しました。
 *	- 新規に、bitarray_msb1st_get(),bitarray_msb1st_set()を追加しました。
 *	  bitarray_msb1st_get(),bitarray_msb1st_set()はまだ、アセンブラ化していません。
 *	* Sat Nov 22 11:57:45 JST 2014 Naoyuki Sawa
 *	- bitarray_msb1st_get()をアセンブラ化しました。
 *	  処理の序盤〜中盤は、既存のbitarray_lsb1st_get()のアセンブラ版とほぼ同じで、シフト方向が違うだけです。
 *	  処理の終盤は、既存のbitarray_lsb1st_get()と異なり、マスクを取る必要が無いので、より単純になりました。
 *	- HuffmanDecoder_Decode()から使用して、C言語版と同じ結果になることを動作確認しました。
 *	  HuffmanDecoder_Decode()で、約39KB⇒約62KBの展開を行った時の速度が、約1.203秒⇒約1.106秒に高速化しました。(Clock=48MHz,Stack=FRAM)
 *	  bitarray_msb1st_get()単体で、どれぐらい高速化したかは、まだ計測していません。
 *	* Sat Nov 22 13:00:53 JST 2014 Naoyuki Sawa
 *	- bitarray_msb1st_set()をアセンブラ化しました。
 *	  処理の序盤と終盤は、既存のbitarray_lsb1st_set()のアセンブラ版とほぼ同じで、シフト方向が違うだけです。
 *	  処理の中盤は、既存のbitarray_lsb1st_set()と異なり、マスクと値をそれぞれにシフトするようになりました。
 *	- HuffmanEncoder_Encode()から使用して、C言語版と同じ結果になることを動作確認しました。
 *	  HuffmanEncoder_Encode()で、約62KB⇒約39KBの圧縮を行った時の速度が、約12.91秒⇒約12.69秒に高速化しました。(Clock=48MHz,Stack=FRAM)
 *	  bitarray_msb1st_set()単体で、どれぐらい高速化したかは、まだ計測していません。
 *	* Sat Nov 29 10:50:31 JST 2014 Naoyuki Sawa
 *	- bitarray_lsb1st_get(),bitarray_msb1st_get()を、clipbary.cからframbary.cへ分離しました。
 *	  HuffmanDecoder_Decode()で、約39KB⇒約62KBの展開を行った時の速度が、以下のように高速化しました。(Clock=48MHz,Code=FRAM,Stack=FRAM)
 *	  高速RAMに配置するモジュール:無し                ⇒約0.756秒
 *	  高速RAMに配置するモジュール:frambary.o          ⇒約0.586秒
 *	  高速RAMに配置するモジュール:framhfm.o           ⇒約0.418秒
 *	  高速RAMに配置するモジュール:frambary.o+framhfm.o⇒約0.248秒
 *	* Thu Dec 11 21:02:26 JST 2014 Naoyuki Sawa
 *	- bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。
 *	  これまでは、bits=1〜32でしたが、今後は、bits=0〜32となります。
 *	  bits=0を許容した理由は、呼び出し側の処理の都合上bits=0となり得るケースがよく有り、呼び出し側で判断して呼び出しを回避するよりも、当モジュール側で判断する方が便利であると考えたからです。
 *	- 今回変更を行った箇所は、bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()のC言語版のみです。
 *	  bitarray_lsb1st_get(),bitarray_msb1st_get()は、処理の先頭でbits=0であるか判断して、そうならば0を返すように特例処理を追加しました。
 *	  bitarray_lsb1st_set(),bitarray_msb1st_set()は、処理の先頭でbits=0であるか判断して、そうならば何もせずに帰る特例処理を追加しました。
 *	  C言語版で、上記の特例処理が必要である理由は、bits=0の時にそのまま処理を行うと、(32-bits)ビットのシフトを行う箇所があり、32ビットのシフトが発生してしまうからです。
 *	  C言語の仕様により、32ビットのシフトは不可であり、たとえばx86では0ビットシフトと同じ扱いとなり、間違った結果になってしまうからです。
 *	- 今回の変更において、bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()のAsm版は、何も変更していません。
 *	  Asm版の処理は、既に32ビットのシフトにも対応できるように作成されており、そのまま処理を行っても正しい結果となるからです。
 *	  C言語版の変更と同様に、処理の先頭で特例処理を行っても構いませんが、コードサイズが増えるだけで無駄なので、特例処理の追加を行わないことにしました。
 *	  bits=0で呼び出されるケースよりも、そうでないケースの方が多いので、bits=0の場合だけの性能向上を図って特例処理を追加することは、得策ではありません。
 *	* Thu Dec 11 22:00:00 JST 2014 Naoyuki Sawa
 *	- bitarray_lsb1st_test(),bitarray_msb1st_test()を追加しました。
 *	  使用頻度は低いと思うので、frambary.cではなくclipbary.cに含めました。
 *	* Mon Oct 19 22:47:19 JST 2015 Naoyuki Sawa
 *	- bitarray_lsb1st_copy(),bitarray_msb1st_copy()を追加しました。
 *	  使用頻度は低いと思うので、frambary.cではなくclipbary.cに含めました。
 *	* Wed Nov 18 21:37:53 JST 2015 Naoyuki Sawa
 *	- 'extern "C" {'〜'}'で囲みました。.cppを含むWin32プロジェクトからもインクルード出来るようにするためです。
 */
#ifndef __CLIP_BARY_H__
#define __CLIP_BARY_H__

#ifdef  __cplusplus
extern "C" {
#endif//__cplusplus

/*****************************************************************************
 *	
 *****************************************************************************/

/* ビット配列のメモリを確保します。
 * [in]
 *	bit_len		ビット数。
 * [out]
 *	戻り値		ビット配列の先頭アドレス。
 * [note]
 *	* ビット配列のメモリ領域は、このマクロ以外の方法を使って確保しても構いません。
 *	  静的なメモリ領域や、別の方法で確保したメモリ領域に対して、ビット配列の操作を行うことも可能です。
 *	- ただし、必ず32ビットアライメントされたメモリ領域としてください。
 *	  高速化のため、bitarray_?sb1st_get()とbitarray_?sb1st_set()を、32ビット単位で処理を行うように実装したからです。
 *	- 8ビット単位で処理を行うようにすれば、32ビットアライメントの制約は無くなるのですが、
 *	  頻繁にビット配列を操作する場合、速度の方が重要と考えて、32ビット単位で処理を行う実装にしました。
 */
#define bitarray_alloc(bit_len) (calloc(((bit_len) + 31) >> 5, 4)) /* 指定されたbit数を、32bit単位に切り上げて、int配列として確保します */

/* ビット配列のメモリを開放します。
 * [in]
 *	ptr		ビット配列の先頭アドレス。
 */
#define bitarray_free(ptr) do { free(ptr); } while(0)

/* ビット配列の任意の位置から、{0〜32}ビット値を取得します。						//{{2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。}}
 * [in]
 *	ptr		ビット配列の先頭アドレス。
 *	pos		ビット配列の先頭から、何ビット目の位置から、値を取得するか。
 *	bits		取得する値のビット数。
 * [out]
 *	戻り値		取得した値。
 * [note]
 *	* 32ビット超過の操作は対応していません。							//{{2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。}}
 *	  bitsに32超過の値を指定すると、C版の実装は実行時エラー,ASM版は動作未定義となります。		//{{2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。}}
 *	* 31ビット以下の値を取得した場合、最上位ビットは符号拡張 *されません* 。
 *	  31ビット以下の値を、符号付きとして扱いたい場合は、呼び出し側で符号拡張してください。
 */
int bitarray_lsb1st_get(const void* ptr, int pos, int bits);		//LSB先行バージョン
int bitarray_msb1st_get(const void* ptr, int pos, int bits);		//MSB先行バージョン

/* ビット配列の任意の位置に、{0〜32}ビット値を格納します。						//{{2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。}}
 * [in]
 *	ptr		ビット配列の先頭アドレス。
 *	pos		ビット配列の先頭から、何ビット目の位置に、値を格納するか。
 *	bits		格納する値のビット数。
 *	value		格納する値。
 * [note]
 *	* 32ビット超過の操作は対応していません。							//{{2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。}}
 *	  bitsに32超過の値を指定すると、C版の実装は実行時エラー,ASM版は動作未定義となります。		//{{2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。}}
 *	* 引数valueの、不要な上位ビットは、本関数内でマスクします。
 *	  呼び出し側で、マスクしておく必要はありません。
 */
void bitarray_lsb1st_set(void* ptr, int pos, int bits, int value);	//LSB先行バージョン
void bitarray_msb1st_set(void* ptr, int pos, int bits, int value);	//MSB先行バージョン

/*****************************************************************************
 *	
 *****************************************************************************/

//	■使用例１：動的に確保したビット配列のメモリを使用する。
//	void* ba = bitarray_lsb1st_alloc(321);		//321ビット分確保。切り上げて324ビット(81ワード)確保される
//	bitarray_lsb1st_set(ba, 100, 24, 0xFEDCBA);	//100ビット目から、24ビット長の範囲に、0xFEDCBAを格納する
//	tmp = bitarray_lsb1st_get(ba, 100, 24);		//100ビット目から、24ビット長を取得。0x00FEDCBAが返される	//符号拡張されて0xFFFEDCBAには*ならない*ことに注意

//	■使用例２：静的に作成したビット配列のデータを使用する。
//	//                   +-------------------31ビット目
//	//                   |      +------------ 0ビット目
//	//                   |      |   +--------63ビット目
//	//                   |      |   |      +-32ビット目
//	const int ba[2] = {0x76543210,0xFEDCBA98};
//	tmp = bitarray_lsb1st_get(ba, 20, 16);		//20ビット目から、16ビット長を取得。0x00008765が返される	//符号拡張されて0xFFFF8765には*ならない*ことに注意

/*****************************************************************************
 *	
 *****************************************************************************/

/* ビット配列の指定した範囲に、1のビットが有るかを検査する。
 * [in]
 *	ptr		ビット配列の先頭アドレス。
 *	pos		検査するビット範囲の先頭ビット位置。
 *	bits		検査するビット範囲のビット数。							//{{2014/12/11コメント:0も指定可能です。0を指定した場合、戻り値は常に0になります。}}
 * [out]
 *	戻り値		ビット配列の指定した範囲に、1のビットが有れば、0以外の値を返す。
 *			ビット配列の指定した範囲に、1のビットが無ければ、0を返す。
 * [note]
 *	- 以下の例のように、１ビットづつ取得して判定する方法でも、結果は同じになります。
 *	  │int bitarray_lsb1st_test(const void* ptr, int pos, int bits) {
 *	  │ while(--bits >= 0) { if(bitarray_lsb1st_get(ptr, pos++, 1)) { return 1; } }
 *	  │ return 0; }
 *	  しかし、ある程度、高速性が求められる用途に使用するつもりなので、当実装では、ビット範囲の途中部分はワード単位で判定するようにして高速化しました。
 *	  ビット範囲の大きさにもよりますが、200ビット分ぐらいの範囲を検査するならば、上記のような単純な実装と比べて、当実装のほうが、100倍ぐらい早いです。
 *	- 具体的には、ビット配列を用いてマークを行う、GCの別実装を作る予定です。そのモジュールから当関数を利用する予定です。(2014/12/10現在は未実装です。)
 */
int bitarray_lsb1st_test(const void* ptr, int pos, int bits);	//LSB先行バージョン
int bitarray_msb1st_test(const void* ptr, int pos, int bits);	//MSB先行バージョン

/*****************************************************************************
 *	
 *****************************************************************************/

/* ビット配列をコピーする。
 * [in]
 *	dst_ptr		コピー先ビット配列の先頭アドレス。
 *	dst_pos		コピー先の先頭ビット位置。
 *	src_ptr		コピー元ビット配列の先頭アドレス。
 *	dst_pos		コピー元の先頭ビット位置。
 *	bits		コピーするビット数。(0〜INT_MAX)
 * [note]
 *	- コピー先の範囲とコピー元の範囲が重なっていてはいけません。
 */
void bitarray_lsb1st_copy(void* dst_ptr, int dst_pos, const void* src_ptr, int src_pos, int bits);	//LSB先行バージョン
void bitarray_msb1st_copy(void* dst_ptr, int dst_pos, const void* src_ptr, int src_pos, int bits);	//MSB先行バージョン

#ifdef  __cplusplus
}//extern "C"
#endif//__cplusplus

#endif /*__CLIP_BARY_H__*/
