/*	
 *	clipbary.c
 *
 *	汎用ビット配列
 *
 *	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に含めました。
 */
#include "clip.h"

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

#ifndef PIECE
void bitarray_lsb1st_set(void* ptr, int pos, int bits, int value) {
	//
	//	                                              s2               s1
	//	                                              /                /
	//	                                        +----------+----------------------+
	//	MSB|........ .......x xxxxxxxx xxxxxxxx|xxxxxxxx xxx..... ........ ........|LSB
	//	                    +------------------------------+                      |
	//	                                   /               |                      |
	//	                                 bits             pos                     p
	//	             mask = 1_11111111_11111111_11111111_111
	//
	int s1;
	int s2;
	int mask;
	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ならば、何もせずに帰ります。 */
	if(!bits) { return; }
//}}2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。
	/* 32bit単位のポインタを求めます。 */
	p = (int*)ptr + (pos >> 5);
	/* p[0]の位置のint値に含まれる、不要bit数を求めます。 */
	s1 = pos & 31;	/* 0〜31 */
	/* p[0]の位置のint値に含まれる、必要bit数を求めます。 */
	s2 = 32 - s1;	/* 1〜32 */
	/* 格納する値の、不要bitをマスクします。 */
	mask  = (unsigned)-1    >> (32 - bits);											//{{2014/12/11コメント:bits=0ならば不正な32ビットシフトが発生するので、bits=0でここへ来ないよう当関数の先頭で判断している。}}
	value &= mask;
	/* p[0]の位置のint値に、必要bitを合成します。 */
	p[0] &= ~((unsigned)mask  << s1);
	p[0] |=   (unsigned)value << s1;
	/* p[1]の位置のint値に、必要bitがまたがっていたら… */
	if(bits > s2) {
		/* p[1]の位置のint値に、必要bitを合成します。 */
		p[1] &= ~((unsigned)mask  >> s2);
		p[1] |=   (unsigned)value >> s2;
	}
}
#else /*PIECE*/
void bitarray_lsb1st_set(void* ptr, int pos, int bits, int value);
asm("
		.code
		.align		1
		.global		bitarray_lsb1st_set
bitarray_lsb1st_set:
		;//-------------------------------------;//
		;// %r12 := ptr
		;// %r13 := pos
		;// %r14 := bits
		;// %r15 := value
		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
		;// %r15 := value
		ld.w		%r6, -1			;// %r6  := -1
;//{{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  := mask = (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を最適化
		and		%r15, %r6		;// %r15 := value &= mask
		;//-------------------------------------;//
		;// %r4  := s1
		;// %r5  := s2
		;// %r6  := mask
		;// %r12 := p
		;// %r14 := bits
		;// %r15 := value
		ld.w		%r7, [%r12]		;// %r7  := tmp = p[0]
		ld.w		%r10, %r6		;// %r10 :=                   mask
		ld.w		%r11, %r15		;// %r11 :=                   value
;//{{%r4を破壊しても良いのでxsllを最適化
;//		xsll		%r10, %r4		;// %r10 :=         (unsigned)mask  << s1
;//		xsll		%r11, %r4		;// %r11 :=         (unsigned)value << s1
;//↓%r4を破壊しても良いのでxsllを最適化
		cmp		%r4, 8			;//<---+
		jrle		5			;//--+ |
		sll		%r10, 8			;//  | |
		sll		%r11, 8			;//  | |
		jp.d		-4			;//--|-+
		sub		%r4, 8			;//  |							*delay*
		sll		%r10, %r4		;//<-+
		sll		%r11, %r4
;//}}%r4を破壊しても良いのでxsllを最適化
		not		%r10, %r10		;// %r10 :=       ~((unsigned)mask  << s1)
		and		%r7, %r10		;// %r7  := tmp & ~((unsigned)mask  << s1)
		or		%r7, %r11		;// %r7  := tmp & ~((unsigned)mask  << s1) | ((unsigned)value << s1)
		ld.w		[%r12]+, %r7		;// p[0]  = tmp
		;//-------------------------------------;//
		;// %r5  := s2
		;// %r6  := mask
		;// %r12 := p
		;// %r14 := bits
		;// %r15 := value
		cmp		%r14, %r5		;// if(bits > s2)
		jrle		14			;//---------------------------------------------------------------------+
		 ld.w		%r7, [%r12]		;//   %r7  := tmp = p[1]						|
;//{{%r5を破壊しても良いのでxsrlを最適化		;//									|
;//		 xsrl		%r6, %r5		;//   %r6  :=         (unsigned)mask  >> s2				|
;//		 xsrl		%r15, %r5		;//   %r15 :=         (unsigned)value >> s2				|
;//↓%r5を破壊しても良いのでxsrlを最適化		;//									|
		 cmp		%r5, 8			;//<---+								|
		 jrle		5			;//--+ |								|
		 srl		%r6, 8			;//  | |								|
		 srl		%r15, 8			;//  | |								|
		 jp.d		-4			;//--|-+								|
		 sub		%r5, 8			;//  |							*delay*		|
		 srl		%r6, %r5		;//<-+									|
		 srl		%r15, %r5		;//									|
;//}}%r5を破壊しても良いのでxsrlを最適化		;//									|
		 not		%r6, %r6		;//   %r6  :=       ~((unsigned)mask  >> s2)				|
		 and		%r7, %r6		;//   %r7  := tmp & ~((unsigned)mask  >> s2)				|
		 or		%r7, %r15		;//   %r7  := tmp & ~((unsigned)mask  >> s2) | ((unsigned)value >> s2)	|
		 ld.w		[%r12], %r7		;//   p[1]  = tmp							|
		ret					;//<--------------------------------------------------------------------+
");
#endif/*PIECE*/

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

#ifndef PIECE
void bitarray_msb1st_set(void* ptr, int pos, int bits, int value) {
	//
	//	                s1               s2
	//	                /                /
	//	    +----------------------+----------+
	//	MSB|........ ........ .....xxx xxxxxxxx|xxxxxxxx xxxxxxxx x....... ........|LSB
	//	    |                      +------------------------------+               |
	//	    |                      |              /                               |
	//	    p                     pos           bits                              p
	//	                    mask = 111_11111111_11111111_11111111_1
	//
	int s1;
	int s2;
	int mask;
	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ならば、何もせずに帰ります。 */
	if(!bits) { return; }
//}}2014/12/11変更:bitarray_lsb1st_get(),bitarray_msb1st_get(),bitarray_lsb1st_set(),bitarray_msb1st_set()に、bits=0を指定できるように変更しました。
	/* 32bit単位のポインタを求めます。 */
	p = (int*)ptr + (pos >> 5);
	/* p[0]の位置のint値に含まれる、不要bit数を求めます。 */
	s1 = pos & 31;	/* 0〜31 */
	/* p[0]の位置のint値に含まれる、必要bit数を求めます。 */
	s2 = 32 - s1;	/* 1〜32 */
	/* 格納する値の、不要bitをマスクします。 */
	mask  = (unsigned)-1    << (32 - bits);											//{{2014/12/11コメント:bits=0ならば不正な32ビットシフトが発生するので、bits=0でここへ来ないよう当関数の先頭で判断している。}}
	value = (unsigned)value << (32 - bits);											//{{2014/12/11コメント:bits=0ならば不正な32ビットシフトが発生するので、bits=0でここへ来ないよう当関数の先頭で判断している。}}
	/* p[0]の位置のint値に、必要bitを合成します。 */
	p[0] &= ~((unsigned)mask  >> s1);
	p[0] |=   (unsigned)value >> s1;
	/* p[1]の位置のint値に、必要bitがまたがっていたら… */
	if(bits > s2) {
		/* p[1]の位置のint値に、必要bitを合成します。 */
		p[1] &= ~((unsigned)mask  << s2);
		p[1] |=   (unsigned)value << s2;
	}
}
#else /*PIECE*/
void bitarray_msb1st_set(void* ptr, int pos, int bits, int value);
asm("
		.code
		.align		1
		.global		bitarray_msb1st_set
bitarray_msb1st_set:
		;//-------------------------------------;//
		;// %r12 := ptr
		;// %r13 := pos
		;// %r14 := bits
		;// %r15 := value
		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
		;// %r15 := value
		ld.w		%r6, -1			;// %r6  := -1
;//{{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を破壊しても良いのでxsllを最適化
;//		xsll		%r6, %r7		;// %r6  := mask  = (unsigned)-1    << (32 - bits)
;//		xsll		%r15, %r7		;// %r15 := value = (unsigned)value << (32 - bits)
;//↓%r7を破壊しても良いのでxsllを最適化
		cmp		%r7, 8			;//<---+								//{{2014/12/11コメント:Asm版は32ビットシフト可能なので、C言語版のような特例処理は不要で、通常と同じ方法で処理して構わない。}}
		jrle		5			;//--+ |
		sll		%r6, 8			;//  | |
		sll		%r15, 8			;//  | |
		jp.d		-4			;//--|-+
		sub		%r7, 8			;//  |							*delay*
		sll		%r6, %r7		;//<-+
		sll		%r15, %r7		;//
;//}}%r7を破壊しても良いのでxsllを最適化
		;//-------------------------------------;//
		;// %r4  := s1
		;// %r5  := s2
		;// %r6  := mask
		;// %r12 := p
		;// %r14 := bits
		;// %r15 := value
		ld.w		%r7, [%r12]		;// %r7  := tmp = p[0]
		ld.w		%r10, %r6		;// %r10 :=                   mask
		ld.w		%r11, %r15		;// %r11 :=                   value
;//{{%r4を破壊しても良いのでxsrlを最適化
;//		xsrl		%r10, %r4		;// %r10 :=         (unsigned)mask  >> s1
;//		xsrl		%r11, %r4		;// %r11 :=         (unsigned)value >> s1
;//↓%r4を破壊しても良いのでxsrlを最適化
		cmp		%r4, 8			;//<---+
		jrle		5			;//--+ |
		srl		%r10, 8			;//  | |
		srl		%r11, 8			;//  | |
		jp.d		-4			;//--|-+
		sub		%r4, 8			;//  |							*delay*
		srl		%r10, %r4		;//<-+
		srl		%r11, %r4
;//}}%r4を破壊しても良いのでxsrlを最適化
		not		%r10, %r10		;// %r10 :=       ~((unsigned)mask  >> s1)
		and		%r7, %r10		;// %r7  := tmp & ~((unsigned)mask  >> s1)
		or		%r7, %r11		;// %r7  := tmp & ~((unsigned)mask  >> s1) | ((unsigned)value >> s1)
		ld.w		[%r12]+, %r7		;// p[0]  = tmp
		;//-------------------------------------;//
		;// %r5  := s2
		;// %r6  := mask
		;// %r12 := p
		;// %r14 := bits
		;// %r15 := value
		cmp		%r14, %r5		;// if(bits > s2)
		jrle		14			;//---------------------------------------------------------------------+
		 ld.w		%r7, [%r12]		;//   %r7  := tmp = p[1]						|
;//{{%r5を破壊しても良いのでxsllを最適化		;//									|
;//		 xsll		%r6, %r5		;//   %r6  :=         (unsigned)mask  << s2				|
;//		 xsll		%r15, %r5		;//   %r15 :=         (unsigned)value << s2				|
;//↓%r5を破壊しても良いのでxsllを最適化		;//									|
		 cmp		%r5, 8			;//<---+								|
		 jrle		5			;//--+ |								|
		 sll		%r6, 8			;//  | |								|
		 sll		%r15, 8			;//  | |								|
		 jp.d		-4			;//--|-+								|
		 sub		%r5, 8			;//  |							*delay*		|
		 sll		%r6, %r5		;//<-+									|
		 sll		%r15, %r5		;//									|
;//}}%r5を破壊しても良いのでxsllを最適化		;//									|
		 not		%r6, %r6		;//   %r6  :=       ~((unsigned)mask  << s2)				|
		 and		%r7, %r6		;//   %r7  := tmp & ~((unsigned)mask  << s2)				|
		 or		%r7, %r15		;//   %r7  := tmp & ~((unsigned)mask  << s2) | ((unsigned)value << s2)	|
		 ld.w		[%r12], %r7		;//   p[1]  = tmp							|
		ret					;//<--------------------------------------------------------------------+
");
#endif/*PIECE*/

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

#ifndef PIECE
static int bitarray_test(const int* ptr, int pos, int bits, int (*fnGet)(const void*, int, int));
int bitarray_lsb1st_test(const void* ptr, int pos, int bits) { return bitarray_test(ptr, pos, bits, bitarray_lsb1st_get); }
int bitarray_msb1st_test(const void* ptr, int pos, int bits) { return bitarray_test(ptr, pos, bits, bitarray_msb1st_get); }
static int bitarray_test(const int* ptr, int pos, int bits, int (*fnGet)(const void*, int, int)) {
	int m, n, v;
	ptr += pos >> 5;				//検査するビット範囲の先頭を含む、先頭ワードのアドレス。
	pos &= 31;					//検査するビット範囲の先頭の、先頭ワード内でのビット位置(0〜31)。
	if(!pos) { goto L20; }				//上記ビット位置が0ならば、L20へ。
	;//---------------------------------------------------------------------
	m = 32 - pos;					//上記ビット位置から、先頭ワードの末尾までのビット数。
	n = bits;					//検査する総ビット数。
	if(m < n) { n = m; }				//先頭ワードから取得するビット数。
	v = (*fnGet)(ptr, pos, n);			//先頭ワードからビットを取得する。					//{{2014/12/11コメント:n=0でも安全です。}}
	if(v) { return v; }				//1のビットが有れば、0以外の値を返す。
	bits -= n;					//取得したビット数を、検査する総ビット数から差し引く。
	ptr++;						//次のワードへ進める。
	;//---------------------------------------------------------------------
	goto L20;					//ループ最適化のため'while{〜}'⇒do{〜}while'に変換した。L20から開始する。
	do {
		v = *ptr++;				//現在のワードを取得して、次のワードへ進める。
		if(v) { return v; }			//1のビットが有れば、0以外の値を返す。
L20:		bits -= 32;				//┬検査する総ビット数が32ビット以上残っていれば…
	} while(bits >= 0);				//┘
	;//---------------------------------------------------------------------
	bits += 32;					//上記ループを抜ける時に一回引き過ぎているので戻す。
	v = (*fnGet)(ptr, 0, bits);			//検査する総ビット数が残っていれば、取得する。				//{{2014/12/11コメント:bits=0でも安全です。}}
	return v;					//1のビットが有れば、0以外の値を返す。
}
#else //PIECE
int bitarray_lsb1st_test(const void* ptr, int pos, int bits);
int bitarray_msb1st_test(const void* ptr, int pos, int bits);
asm("
		.code
		.align		1
		.global		bitarray_lsb1st_test
		.global		bitarray_msb1st_test
bitarray_lsb1st_test:
		xld.w		%r15, bitarray_lsb1st_get	;//%r15 := fnGet = bitarray_lsb1st_get
		jp		bitarray_test			;//
bitarray_msb1st_test:
		xld.w		%r15, bitarray_msb1st_get	;//%r15 := fnGet = bitarray_msb1st_get
bitarray_test:
		pushn		%r2
		ld.w		%r0, %r15			;//%r0  := fnGet
		ld.w		%r1, %r12			;//%r1  := ptr
		ld.w		%r2, %r14			;//%r2  := bits
		;//%r0  := fnGet
		;//%r1  := ptr
		;//%r2  := bits
		;//%r12 := ptr
		;//%r13 := pos
		;//%r14 := n = bits
		ld.w		%r9, %r13			;//%r9  :=         pos
		sra		%r9, 5				;//%r9  :=         pos >> 5
		sla		%r9, 2				;//%r9  :=        (pos >> 5) << 2
	;//	add		%r1, %r9			;//%r1  := ptr += (pos >> 5) << 2	─┐
		and		%r13, 31			;//%r13 := pos &= 31			　│
		jreq.d		bitarray_test_L20		;//if(!pos) { goto L20 }		　│
		add		%r1, %r9			;//%r1  := ptr += (pos >> 5) << 2	←┘	*delay*
		not		%r9, %r13			;//%r9  := m =            ~pos
		add		%r9, 33				;//%r9  := m = 32 - pos = ~pos + 33
		cmp		%r9, %r14			;//if(m < n) { n = m }
		jrge.d		3				;//
		 ld.w		%r12, %r1			;//%r12 :=              ptr			*delay*
		 ld.w		%r14, %r9			;//
		sub		%r2, %r14			;//%r2  := bits -= n
		call.d		%r0				;//%r10 := v = (*fnGet)(ptr, pos, n)				//{{2014/12/11コメント:n=0でも安全です。}}
		add		%r1, 4				;//%r1  := ptr  += 4				*delay*
		cmp		%r10, 0				;//if(v) { return v }
		jrne		bitarray_test_RET		;//
		;//---------------------------------------------;//
		;//%r1  := ptr
		;//%r2  := bits
		jp		bitarray_test_L20		;//goto L20
bitarray_test_L10:						;//do {
		ld.w		%r10, [%r1]+			;//  %r10 := v = *ptr++
		cmp		%r10, 0				;//  if(v) { return v }
		jrne		bitarray_test_RET		;//  
bitarray_test_L20:						;//  
		sub		%r2, 32				;//  %r2  := bits -= 32
		jrge		bitarray_test_L10		;//} while(  bits >= 0)
		;//---------------------------------------------;//
		add		%r2, 32				;//%r2  := bits += 32
		ld.w		%r12, %r1			;//%r12 :=              ptr
		ld.w		%r13, 0				;//%r13 :=                   0
		call.d		%r0				;//%r10 := v = (*fnGet)(ptr, 0, bits)				//{{2014/12/11コメント:bits=0でも安全です。}}
		ld.w		%r14, %r2			;//%r14 :=                      bits		*delay*
bitarray_test_RET:
		popn		%r2
		ret						;//return v
");
#endif//PIECE

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

#ifndef PIECE
static void bitarray_copy_subr(void* dst_ptr, int dst_pos, const void* src_ptr, int src_pos, int bits, int (*get)(const void*, int, int), void (*set)(void*, int, int, int)) {
	int n, value;
	if(bits < 0) { DIE(); }
	while(bits) {						//コピーするビット数が残っていたら…
		n = (bits < 32) ? bits : 32;			//今回コピーするビット数を決定する。
		value = (*get)(src_ptr, src_pos, n);		//コピー元ビット配列から値を取得する。
		        (*set)(dst_ptr, dst_pos, n, value);	//コピー先ビット配列に値を格納する。
		src_pos += n;					//コピー元のビット位置を進める。
		dst_pos += n;					//コピー先のビット位置を進める。
		bits    -= n;					//コピーするビット数を減らす。
	}
}
#else //PIECE
/*static*/ void bitarray_copy_subr(void* dst_ptr, int dst_pos, const void* src_ptr, int src_pos, int bits, int (*get)(const void*, int, int), void (*set)(void*, int, int, int));
asm("
		.code
		.align		1
bitarray_copy_subr:
		pushn		%r3
		xsub		%sp, %sp, 8
		;//%r12     := dst_ptr
		;//%r13     := dst_pos
		;//%r14     := src_ptr
		;//%r15     := src_pos
		;//[%sp+ 8] := %r0
		;//[%sp+12] := %r1
		;//[%sp+16] := %r2
		;//[%sp+20] := %r3
		;//[%sp+24] := retp
		;//[%sp+28] := bits
		;//[%sp+32] := get
		;//[%sp+36] := set
		xld.w		[%sp+0], %r12			;//[%sp+0] := dst_ptr
		ld.w		%r0, %r13			;//%r0     := dst_pos
		xld.w		[%sp+4], %r14			;//[%sp+4] := src_ptr
		ld.w		%r1, %r15			;//%r1     := src_pos
		xld.w		%r2, [%sp+28]			;//%r2     := bits
bitarray_copy_subr_LOOP:					;//for(;;) {
		ld.w		%r3, %r2			;//  %r3   := n     = bits	//┐高速化,及び,コードサイズ削減のために、C言語版とは少しアルゴリズムを変えました。動作結果は同じです。
		sub		%r2, 32				;//  %r2   := bits -= 32	//│1. 32ビット減少前のbitsをnにコピーする。
		jrge		2				;//  if(bits < 0) {		//│2. 32ビット減少後のbitsを求める。
		 ld.w		%r2, 0				;//    %r2 := bits  = 0 }	//│3. bitsが0ビット未満ならば0ビットにする。
		sub		%r3, %r2			;//  %r3   := n    -= bits	//│4. (n-bits)が今回転送するビット数である。
		jreq		bitarray_copy_subr_RET		;//  if(!n) { break }		//┘5. 今回転送するビット数が0ビットならばループを抜ける。	32ビット減少前のbits=0だった場合に、32ビット減少後のbits=0,及び,n=(0-0)=0となり、この条件が成立する。それ以外の場合に、この条件が成立する事は無い。
		xld.w		%r9, [%sp+32]			;//  %r9   :=           get
		xld.w		%r12, [%sp+4]			;//  %r12  :=                src_ptr
		ld.w		%r13, %r1			;//  %r13  :=                         src_pos
		call.d		%r9				;//  %r10  := value = (*get)(src_ptr, src_pos, n)
		ld.w		%r14, %r3			;//  %r14  :=                                  n		*delay*
		ld.w		%r15, %r10			;//  %r15  :=                                     value
		xld.w		%r9, [%sp+36]			;//  %r9   :=           set
		xld.w		%r12, [%sp+0]			;//  %r12  :=                dst_ptr
		ld.w		%r13, %r0			;//  %r13  :=                         dst_pos
		call.d		%r9				;//                   (*set)(dst_ptr, dst_pos, n, value)
		ld.w		%r14, %r3			;//  %r14  :=                                  n		*delay*
		add		%r0, %r3			;//  %r0   := dst_pos += n
		jp.d		bitarray_copy_subr_LOOP		;//}
		add		%r1, %r3			;//  %r1   := src_pos += n					*delay*
bitarray_copy_subr_RET:
		xadd		%sp, %sp, 8
		popn		%r3
		ret
");
#endif//PIECE
void bitarray_lsb1st_copy(void* dst_ptr, int dst_pos, const void* src_ptr, int src_pos, int bits) {	//LSB先行バージョン
	bitarray_copy_subr(dst_ptr, dst_pos, src_ptr, src_pos, bits, bitarray_lsb1st_get, bitarray_lsb1st_set);
}
void bitarray_msb1st_copy(void* dst_ptr, int dst_pos, const void* src_ptr, int src_pos, int bits) {	//MSB先行バージョン
	bitarray_copy_subr(dst_ptr, dst_pos, src_ptr, src_pos, bits, bitarray_msb1st_get, bitarray_msb1st_set);
}
