/*	
 *	frambary.c
 *
 *	汎用ビット配列
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2014 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に含めました。
 */
#include "clip.h"

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

#ifndef PIECE
int bitarray_lsb1st_get(const void* ptr, int pos, int bits) {
	//
	//	                                              s2               s1
	//	                                              /                /
	//	                                        +----------+----------------------+
	//	MSB|........ .......x xxxxxxxx xxxxxxxx|xxxxxxxx xxx..... ........ ........|LSB
	//	                    +------------------------------+                      |
	//	                                   /               |                      |
	//	                                 bits             pos                     p
	//	             mask = 1_11111111_11111111_11111111_111
	//
	int value;
	int s1;
	int s2;
	const int* p;
//{{2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。
//	/* 1bit未満、及び、32bit超過の操作は対応していません。 */
//	if((bits < 1) || (bits > 32)) { DIE(); }
//↓2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。
	/* 32bit超過の操作は対応していません。 */
	if((unsigned)bits > 32) { DIE(); }
	/* bits=0ならば、0を返します。 */
	if(!bits) { return 0; }
//}}2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。
	/* 32bit単位のポインタを求めます。 */
	p = (const int*)ptr + (pos >> 5);
	/* p[0]の位置のint値に含まれる、不要bit数を求めます。 */
	s1 = pos & 31;	/* 0〜31 */
	/* p[0]の位置のint値に含まれる、必要bit数を求めます。 */
	s2 = 32 - s1;	/* 1〜32 */
	/* p[0]の位置のint値から、必要bitを取得します。 */
	value = (unsigned)p[0] >> s1;
	/* p[1]の位置のint値に、必要bitがまたがっていたら… */
	if(bits > s2) {
		/* p[1]の位置のint値から、必要bitを取得します。 */
		value |= (unsigned)p[1] << s2;
	}
	/* 不要bitをマスクします。(必要bitの符号拡張は行わない) */
	value &= ((unsigned)-1 >> (32 - bits));											//{{2014/12/11コメント:bits=0ならば不正な32ビットシフトが発生するので、bits=0でここへ来ないよう当関数の先頭で判断している。}}
	return value;
}
#else /*PIECE*/
int bitarray_lsb1st_get(const void* ptr, int pos, int bits);
asm("
		.code
		.align		1
		.global		bitarray_lsb1st_get
bitarray_lsb1st_get:
		;//-------------------------------------;//
		;// %r12 := ptr
		;// %r13 := pos
		;// %r14 := bits
		xand		%r4, %r13, 31		;// %r4  := s1 = pos & 31
;//{{xldのext拡張を節約
;//		xld.w		%r5, 32			;// %r5  := s2 = 32 - s1
;//		sub		%r5, %r4
;//↓xldのext拡張を節約
		not		%r5, %r4		;// %r5  := s2 = 32 - s1 = 33 + ~s1
		add		%r5, 33
;//}}xldのext拡張を節約
		srl		%r13, 5			;// %r12 := p = (const int*)ptr + (pos >> 5)
		sll		%r13, 2
		add		%r12, %r13
		;//-------------------------------------;//
		;// %r4  := s1
		;// %r5  := s2
		;// %r12 := p
		;// %r14 := bits
		ld.w		%r10, [%r12]+		;// %r10 := value = (unsigned)p[0]
;//{{%r4を破壊しても良いのでxsrlを最適化
;//		xsrl		%r10, %r4		;// %r10 := value = (unsigned)p[0] >> s1
;//↓%r4を破壊しても良いのでxsrlを最適化
		cmp		%r4, 8			;//<---+
		jrle		4			;//--+ |
		srl		%r10, 8			;//  | |
		jp.d		-3			;//--|-+
		sub		%r4, 8			;//  |							*delay*
		srl		%r10, %r4		;//<-+
;//}}%r4を破壊しても良いのでxsrlを最適化
		;//-------------------------------------;//
		;// %r5  := s2
		;// %r10 := value
		;// %r12 := p
		;// %r14 := bits
		cmp		%r14, %r5		;// if(bits > s2)
		jrle.d		10			;//---------------------------------------------+
		 ld.w		%r6, -1			;//   %r6  := -1				|	*delay*
		 ld.w		%r11, [%r12]		;//   %r11 := (unsigned)p[1]			|
;//{{%r5を破壊しても良いのでxsllを最適化		;//						|
;//		 xsll		%r11, %r5		;//   %r11 := (unsigned)p[1] << s2		|
;//↓%r5を破壊しても良いのでxsllを最適化		;//						|
		 cmp		%r5, 8			;//<---+					|
		 jrle		4			;//--+ |					|
		 sll		%r11, 8			;//  | |					|
		 jp.d		-3			;//--|-+					|
		 sub		%r5, 8			;//  |						|	*delay*
		 sll		%r11, %r5		;//<-+						|
;//}}%r5を破壊しても良いのでxsllを最適化		;//						|
		 or		%r10, %r11		;// %r10 := value |= (unsigned)p[1] << s2	|
		;//-------------------------------------;//<--------------------------------------------+
		;// %r6  := -1
		;// %r10 := value
		;// %r14 := bits
;//{{xldのext拡張を節約
;//		xld.w		%r7, 32			;// %r7  := 32 - bits
;//		sub		%r7, %r14
;//↓xldのext拡張を節約
		not		%r7, %r14		;// %r7  := 32 - bits = 33 + ~bits
		add		%r7, 33
;//}}xldのext拡張を節約
;//{{%r7を破壊しても良いのでxsrlを最適化
;//		xsrl		%r6, %r7		;// %r6  :=          (unsigned)-1 >> (32 - bits)
;//↓%r7を破壊しても良いのでxsrlを最適化
		cmp		%r7, 8			;//<---+								//{{2014/12/11コメント:Asm版は32ビットシフト可能なので、C言語版のような特例処理は不要で、通常と同じ方法で処理して構わない。}}
		jrle		4			;//--+ |
		srl		%r6, 8			;//  | |
		jp.d		-3			;//--|-+
		sub		%r7, 8			;//  |							*delay*
		srl		%r6, %r7		;//<-+
;//}}%r7を破壊しても良いのでxsrlを最適化
		ret.d
		and		%r10, %r6		;// %r10 := value &= (unsigned)-1 >> (32 - bits)	*delay*
");
#endif/*PIECE*/

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

#ifndef PIECE
int bitarray_msb1st_get(const void* ptr, int pos, int bits) {
	//
	//	                s1               s2
	//	                /                /
	//	    +----------------------+----------+
	//	MSB|........ ........ .....xxx xxxxxxxx|xxxxxxxx xxxxxxxx x....... ........|LSB
	//	    |                      +------------------------------+               |
	//	    |                      |              /                               |
	//	    p                     pos           bits                              p
	//	                    mask = 111_11111111_11111111_11111111_1
	//
	int value;
	int s1;
	int s2;
	const int* p;
//{{2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。
//	/* 1bit未満、及び、32bit超過の操作は対応していません。 */
//	if((bits < 1) || (bits > 32)) { DIE(); }
//↓2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。
	/* 32bit超過の操作は対応していません。 */
	if((unsigned)bits > 32) { DIE(); }
	/* bits=0ならば、0を返します。 */
	if(!bits) { return 0; }
//}}2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。
	/* 32bit単位のポインタを求めます。 */
	p = (const int*)ptr + (pos >> 5);
	/* p[0]の位置のint値に含まれる、不要bit数を求めます。 */
	s1 = pos & 31;	/* 0〜31 */
	/* p[0]の位置のint値に含まれる、必要bit数を求めます。 */
	s2 = 32 - s1;	/* 1〜32 */
	/* p[0]の位置のint値から、必要bitを取得します。 */
	value = (unsigned)p[0] << s1;
	/* p[1]の位置のint値に、必要bitがまたがっていたら… */
	if(bits > s2) {
		/* p[1]の位置のint値から、必要bitを取得します。 */
		value |= (unsigned)p[1] >> s2;
	}
	/* 不要bitをマスクします。(必要bitの符号拡張は行わない) */
	value = (unsigned)value >> (32 - bits);											//{{2014/12/11コメント:bits=0ならば不正な32ビットシフトが発生するので、bits=0でここへ来ないよう当関数の先頭で判断している。}}
	return value;
}
#else /*PIECE*/
int bitarray_msb1st_get(const void* ptr, int pos, int bits);
asm("
		.code
		.align		1
		.global		bitarray_msb1st_get
bitarray_msb1st_get:
		;//-------------------------------------;//
		;// %r12 := ptr
		;// %r13 := pos
		;// %r14 := bits
		xand		%r4, %r13, 31		;// %r4  := s1 = pos & 31
;//{{xldのext拡張を節約
;//		xld.w		%r5, 32			;// %r5  := s2 = 32 - s1
;//		sub		%r5, %r4
;//↓xldのext拡張を節約
		not		%r5, %r4		;// %r5  := s2 = 32 - s1 = 33 + ~s1
		add		%r5, 33
;//}}xldのext拡張を節約
		srl		%r13, 5			;// %r12 := p = (const int*)ptr + (pos >> 5)
		sll		%r13, 2
		add		%r12, %r13
		;//-------------------------------------;//
		;// %r4  := s1
		;// %r5  := s2
		;// %r12 := p
		;// %r14 := bits
		ld.w		%r10, [%r12]+		;// %r10 := value = (unsigned)p[0]
;//{{%r4を破壊しても良いのでxsllを最適化
;//		xsll		%r10, %r4		;// %r10 := value = (unsigned)p[0] << s1
;//↓%r4を破壊しても良いのでxsllを最適化
		cmp		%r4, 8			;//<---+
		jrle		4			;//--+ |
		sll		%r10, 8			;//  | |
		jp.d		-3			;//--|-+
		sub		%r4, 8			;//  |							*delay*
		sll		%r10, %r4		;//<-+
;//}}%r4を破壊しても良いのでxsllを最適化
		;//-------------------------------------;//
		;// %r5  := s2
		;// %r10 := value
		;// %r12 := p
		;// %r14 := bits
		cmp		%r14, %r5		;// if(bits > s2)
		jrle.d		10			;//---------------------------------------------+
		 not		%r7, %r14		;//   %r7  :=                ~bits		|	*delay*
		 ld.w		%r11, [%r12]		;//   %r11 := (unsigned)p[1]			|
;//{{%r5を破壊しても良いのでxsrlを最適化		;//						|
;//		 xsrl		%r11, %r5		;//   %r11 := (unsigned)p[1] >> s2		|
;//↓%r5を破壊しても良いのでxsrlを最適化		;//						|
		 cmp		%r5, 8			;//<---+					|
		 jrle		4			;//--+ |					|
		 srl		%r11, 8			;//  | |					|
		 jp.d		-3			;//--|-+					|
		 sub		%r5, 8			;//  |						|	*delay*
		 srl		%r11, %r5		;//<-+						|
;//}}%r5を破壊しても良いのでxsrlを最適化		;//						|
		 or		%r10, %r11		;// %r10 := value |= (unsigned)p[1] >> s2	|
		;//-------------------------------------;//<--------------------------------------------+
		;// %r7  := ~bits
		;// %r10 := value
		add		%r7, 33			;// %r7  := 32 - bits = 33 + ~bits
		cmp		%r7, 8			;//<---+								//{{2014/12/11コメント:Asm版は32ビットシフト可能なので、C言語版のような特例処理は不要で、通常と同じ方法で処理して構わない。}}
		jrle		4			;//--+ |
		srl		%r10, 8			;//  | |
		jp.d		-3			;//--|-+
		sub		%r7, 8			;//  |							*delay*
		ret.d					;//<-+
		srl		%r10, %r7		;// %r10 := value = (unsigned)value >> (32 - bits)	*delay*
");
#endif/*PIECE*/
