/*
 *	clipstl.c
 *
 *	STL傪嶲峫偵偟偰嶌惉偟偨娭悢
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2016 Naoyuki Sawa
 *
 *	* Sat Mar 05 21:53:08 JST 2016 Naoyuki Sawa
 *	- 1st 儕儕乕僗丅
 *	- lower_bound()娭悢,upper_bound()娭悢傪嶌惉偟傑偟偨丅
 *	- 僗儗僢僪僙乕僼斉偺lower_bound_r()娭悢,upper_bound_r()傕捛壛偟傑偟偨丅
 *	* Tue Jun 07 22:13:11 JST 2016 Naoyuki Sawa
 *	- std_rotate()娭悢傪捛壛偟傑偟偨丅
 *	  栚揑偼丄儊儌儕儘乕僥乕僩張棟偺崅懍壔偺偨傔偱偡丅
 *	  徻嵶偼丄埲壓偺捠傝偱偡丅
 *	- 嶐擔丄clipstr.c儌僕儏乕儖偵memrotate()娭悢傪捛壛偟偨偺偱偡偑丄慺捈側傾儖僑儕僘儉偱偼偁傞偺偱偡偑丄偄傑偄偪掅懍偱偟偨丅
 *	  memrotate()偑屇傃弌偟偰偄傞memmove()傕崅懍壔偡傞摍偟偰岺晇偟偨偺偱偡偑丄偁傑傝岠壥偼桳傝傑偣傫偱偟偨丅(memmove()傪崅懍壔弌棃偨帠偼偦傟扨懱偱傕堄媊偼桳偭偨偺偱偡偑乧)
 *	  夝寛曽朄傪扵偟偰丄Web偱儊儌儕儘乕僥乕僩張棟偺傾儖僑儕僘儉偵偮偄偰専嶕偟偰尒偨張丄婛偵丄昗弨C++儔僀僽儔儕偵丄std::rotate()偲偄偆娭悢偑桳傞帠偑敾傝傑偟偨丅
 *	  乽cppreference.com - std::rotate乿(http://en.cppreference.com/w/cpp/algorithm/rotate)偵丄偦偺幚憰曽朄偑彂偐傟偰偍傝丄偲偰傕岠棪偺椙偄傾儖僑儕僘儉偺傛偆偱偡丅
 *	  偦偙偱丄偙偺傾儖僑儕僘儉傪丄C尵岅斉偲偟偰幚憰偡傞帠偵偟傑偟偨丅
 *	  捈愙丄clipstr.c儌僕儏乕儖偺memrotate()傪曄峏偟偰傕椙偄偺偱偡偑丄姼偊偰暿娭悢std_rotate()偲偟偰幚憰偟丄memrotate()偼std_rotate()傪屇傃弌偡傛偆偵曄峏偡傞帠偵偟傑偟偨丅
 *	  偦偆偟偨棟桼偼丄STL傗昗弨C++儔僀僽儔儕傪尦偵偟偰嶌惉偟偨僐乕僪偼丄摉儌僕儏乕儖(clipstl.c)偵廤傔傞曽恓偩偐傜偱偡丅
 *	- 仩巊梡椺
 *	  劆void test() {
 *	  劆    int a[] = { 0,1,2,3,4,5,6,7,8,9 }, i;
 *	  劆    std_rotate(a, &a[3], &a[10]);
 *	  劆    for(i = 0; i < 10; i++) { printf("%d ", a[i]); }
 *	  劆    //寢壥:     3 4 5 6 7 8 9 0 1 2
 *	  劆}
 *	- 摉儌僕儏乕儖偵捛壛偡傞娭悢柤偵'std_'偺僾儗僼傿僋僗傪晅偗傞曽恓偱偼側偐偭偨偺偱偡偑丄'rotate'偩偗偱偼偁傑傝偵扨弮夁偓偰柤慜偺徴撍偑怱攝側偺偱丄摿暿偵'std_'偺僾儗僼傿僋僗傪晅偗傞帠偵偟傑偟偨丅
 *	  埲慜偵捛壛偟偨lower_bound()娭悢摍偵偼'std_'偺僾儗僼傿僋僗偼晅偗偰偄側偐偭偨偺偱摑堦偑庢傟偰偄傑偣傫偑丄幚梡忋偼栤戣柍偄偲巚偄傑偡丅
 *	  摉儌僕儏乕儖偵捛壛偡傞娭悢偺娭悢柤偵偮偄偰偼丄偁傑傝尩枾偵峫偊側偄帠偵偟傑偟偨丅
 *	  崱屻傕丄働乕僗僶僀働乕僗偱丄'std_'偺僾儗僼傿僋僗傪晅偗傞偐偳偆偐敾抐偟偰壓偝偄丅
 *	* Wed Jun 08 21:50:02 JST 2016 Naoyuki Sawa
 *	- std::rotate()偺傾儖僑儕僘儉偑棟夝弌棃偨偺偱丄僐儊儞僩傪捛婰偟傑偟偨丅
 *	* Sun Sep 04 21:41:17 JST 2016 Naoyuki Sawa
 *	- std_rotate()偑丄(int)偱傾僪儗僗墘嶼傪峴偭偰偄偨偺傪丄(intptr_t)偱峴偆傛偆偵廋惓偟傑偟偨丅
 *	  64價僢僩懳墳偺偨傔偺弨旛偱偡偑丄32價僢僩偱傕(intptr_t)偱峴偆曽偑杮摉偼惓偟偄偐傜偱偡丅
 *	  偲偼尵偊丄32價僢僩偱偼偳偪傜偱傕摨偠寢壥偵側傞偺偱丄婛懚偺32價僢僩僐乕僪偵偼塭嬁桳傝傑偣傫丅
 */
#include "clip.h"
/****************************************************************************
 *	
 ****************************************************************************/
// * Sat Mar 05 21:53:08 JST 2016 Naoyuki Sawa
// - lower_bound()娭悢,upper_bound()娭悢傪捛壛偟傑偟偨丅
//   栚揑偼丄'抣偺斖埻晅偒bsearch()'傪峴偄偨偄帠偑桳偭偨偐傜偱偡丅
// - lower_bound,upper_bound偺娭悢柤偼丄STL偺std::lower_bound(),std::upper_bound()偐傜庢傝傑偟偨丅
//   崱夞捛壛偟偨lower_bound()娭悢,upper_bound()娭悢偼丄bsearch()偺堷悢巇條/栠傝抣巇條偱丄STL偺std::lower_bound(),std::upper_bound()偲摨偠張棟傪峴偆傕偺偱偡丅
// - 仩嶲峫帒椏
//   劆乽Programing Place乿(http://ppp-lab.sakura.ne.jp/)偝傫偺亀C++曇(昗弨儔僀僽儔儕) 戞20復 僜乕僩嵪傒偺斖埻傪埖偆傾儖僑儕僘儉亁(http://ppp-lab.sakura.ne.jp/cpp/library/020.html)偺婰帠
//   劆乽Stack Overflow乿偺亀Find the first element in an array that is greater than the target亁(http://stackoverflow.com/questions/6553970/find-the-first-element-in-an-array-that-is-greater-than-the-target)偺婰帠
// - 僗儗僢僪僙乕僼斉偺lower_bound_r()娭悢,upper_bound_r()傕捛壛偟傑偟偨丅
//   qsort()偵懳偡傞丄qsort_r()偵憡摉偟傑偡丅
//   偪側傒偵丄bsearch()偵懳偡傞bsearch_r()偼懚嵼偟傑偣傫丅
//   bsearch_r,lfind_r,lsearch_r,偑懚嵼偟側偄偺偼丄C昗弨儔僀僽儔儕巇條偑敳偗偰偄傞栤戣偺傛偆偱偡丅
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//(key亝val)偲側傞丄嵟弶偺val傊偺億僀儞僞傪曉偡丅
//慡偰偺val偑(key亜val)側傜偽丄嵟屻偺val偺師傊偺億僀儞僞傪曉偡丅	仼仼仼仼仼std::lower_bound()偺巇條偱偡丅NULL傪曉偡偺偱偼側偄帠偵拲堄偟偰壓偝偄丅
//[in]
//		堷悢巇條偼丄bsearch()偲摨偠偱偡丅
//		堷悢偵巜掕偡傞compar娭悢偼丄bsearch()偲摨偠傕偺偑棙梡弌棃傑偡丅
//[out]
//		栠傝抣偺巇條偼丄std::lower_bound()偲摨偠偱偡丅
//		摉娭悢偑丄NULL傪曉偡帠偼桳傝傑偣傫丅
//[note]
//		- 忦審傪枮偨偡埵抲偑柍偐偭偨応崌丄bsearch()偼NULL傪曉偟傑偡偑丄摉娭悢偼嵟屻偺val偺師傊偺億僀儞僞傪曉偡帠偵拲堄偟偰壓偝偄丅
//		  std::lower_bound()偺巇條偵曧偭偨偐傜偱偡丅
//		- 忦審傪枮偨偡埵抲偑柍偐偭偨応崌丄bsearch()偲摨條偵NULL傪曉偡巇條偵曄峏偟傛偆偐偲傕巚偭偨偺偱偡偑丄
//		  幚嵺偵巊偭偰尒傞偲丄屇傃弌偟懁偺娤揰偱傕丄嵟屻偺val偺師傊偺億僀儞僞偑曉偝傟偨曽偑巊偄堈偄働乕僗偑懡偄帠偑傢偐傝傑偟偨丅
//		  廬偭偰丄忦審傪枮偨偡埵抲偑柍偐偭偨応崌偼丄std::lower_bound()偲摨條偵丄嵟屻偺val偺師傊偺億僀儞僞傪曉偡帠偵偟傑偟偨丅
void* lower_bound(const void* key, const void* _base, size_t nmemb, size_t size, int (*compar)(const void*, const void*)) {
	return lower_bound_r(key, _base, nmemb, size, (int (*)(const void*, const void*, void*))compar, NULL);	//lower_bound()偲lower_bound_r()偼丄compar娭悢偺宍幃偑堎側傝傑偡偑丄'cdecl屇弌婯栺'側傜偽丄lower_bound()宍幃偺compar娭悢偵偍偄偰丄梋暘側堷悢偑柍帇偝傟傞偺偱栤戣偁傝傑偣傫丅
}
void* lower_bound_r(const void* key, const void* _base, size_t nmemb, size_t size, int (*compar)(const void*, const void*, void*), void* arg) {
	unsigned char* base = (unsigned char*)_base;
	unsigned lo = 0, hi = nmemb;
	while(lo != hi) {
		unsigned mid = (lo + hi) >> 1;
		if((*compar)(key, base + (size * mid), arg) >  0) {	//偙偺埵抲偺抣偑僉乕枹枮側傜偽丄偙偺埵抲偼忦審傪枮偨偟偰偄側偄偺偱乧	仼仼仼仼仼lower_bound()偲upper_bound()偺堘偄偼偙偺峴偩偗偱偡丅
			lo = mid + 1;					//寢壥偺埵抲偼丄彮側偔偲傕丄偙偺埵抲偺師埲崀偲側傞丅
		} else {						//偙偺埵抲偺抣偑僉乕埲忋側傜偽丄偙偺埵抲偼忦審傪枮偨偟偰偄傞偺偱乧
			hi = mid;					//寢壥偺埵抲偼丄彮側偔偲傕丄偙偺埵抲埲慜偲側傞丅
		}
	}
	return base + (size * lo);	//忦審傪枮偨偡埵抲偑桳偭偨応崌偼丄(lo==hi亙nmemb)偲側偭偰偄傞丅忦審傪枮偨偡埵抲偑柍偐偭偨応崌偼丄(lo==hi==nmemb)偲側偭偰偄傞丅
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
//(key亙val)偲側傞丄嵟弶偺val傊偺億僀儞僞傪曉偡丅
//慡偰偺val偑(key亞val)側傜偽丄嵟屻偺val偺師傊偺億僀儞僞傪曉偡丅	仼仼仼仼仼std::upper_bound()偺巇條偱偡丅NULL傪曉偡偺偱偼側偄帠偵拲堄偟偰壓偝偄丅
//[note]
//	- lower_bound()偺愢柧傪嶲徠偟偰壓偝偄丅
void* upper_bound(const void* key, const void* _base, size_t nmemb, size_t size, int (*compar)(const void*, const void*)) {
	return upper_bound_r(key, _base, nmemb, size, (int (*)(const void*, const void*, void*))compar, NULL);	//upper_bound()偲upper_bound_r()偼丄compar娭悢偺宍幃偑堎側傝傑偡偑丄'cdecl屇弌婯栺'側傜偽丄upper_bound()宍幃偺compar娭悢偵偍偄偰丄梋暘側堷悢偑柍帇偝傟傞偺偱栤戣偁傝傑偣傫丅
}
void* upper_bound_r(const void* key, const void* _base, size_t nmemb, size_t size, int (*compar)(const void*, const void*, void*), void* arg) {
	unsigned char* base = (unsigned char*)_base;
	unsigned lo = 0, hi = nmemb;
	while(lo != hi) {
		unsigned mid = (lo + hi) >> 1;
		if((*compar)(key, base + (size * mid), arg) >= 0) {	//偙偺埵抲偺抣偑僉乕埲壓側傜偽丄偙偺埵抲偼忦審傪枮偨偟偰偄側偄偺偱乧	仼仼仼仼仼lower_bound()偲upper_bound()偺堘偄偼偙偺峴偩偗偱偡丅
			lo = mid + 1;					//寢壥偺埵抲偼丄彮側偔偲傕丄偙偺埵抲偺師埲崀偲側傞丅
		} else {						//偙偺埵抲偺抣偑僉乕挻夁側傜偽丄偙偺埵抲偼忦審傪枮偨偟偰偄傞偺偱乧
			hi = mid;					//寢壥偺埵抲偼丄彮側偔偲傕丄偙偺埵抲埲慜偲側傞丅
		}
	}
	return base + (size * lo);	//忦審傪枮偨偡埵抲偑桳偭偨応崌偼丄(lo==hi亙nmemb)偲側偭偰偄傞丅忦審傪枮偨偡埵抲偑柍偐偭偨応崌偼丄(lo==hi==nmemb)偲側偭偰偄傞丅
}
/****************************************************************************
 *	
 ****************************************************************************/
// * Tue Jun 07 22:13:11 JST 2016 Naoyuki Sawa
// - std_rotate()娭悢傪捛壛偟傑偟偨丅
//   栚揑偼丄儊儌儕儘乕僥乕僩張棟偺崅懍壔偺偨傔偱偡丅
//   徻嵶偼丄埲壓偺捠傝偱偡丅
// - 嶐擔丄clipstr.c儌僕儏乕儖偵memrotate()娭悢傪捛壛偟偨偺偱偡偑丄慺捈側傾儖僑儕僘儉偱偼偁傞偺偱偡偑丄偄傑偄偪掅懍偱偟偨丅
//   memrotate()偑屇傃弌偟偰偄傞memmove()傕崅懍壔偡傞摍偟偰岺晇偟偨偺偱偡偑丄偁傑傝岠壥偼桳傝傑偣傫偱偟偨丅(memmove()傪崅懍壔弌棃偨帠偼偦傟扨懱偱傕堄媊偼桳偭偨偺偱偡偑乧)
//   夝寛曽朄傪扵偟偰丄Web偱儊儌儕儘乕僥乕僩張棟偺傾儖僑儕僘儉偵偮偄偰専嶕偟偰尒偨張丄婛偵丄昗弨C++儔僀僽儔儕偵丄std::rotate()偲偄偆娭悢偑桳傞帠偑敾傝傑偟偨丅
//   乽cppreference.com - std::rotate乿(http://en.cppreference.com/w/cpp/algorithm/rotate)偵丄偦偺幚憰曽朄偑彂偐傟偰偍傝丄偲偰傕岠棪偺椙偄傾儖僑儕僘儉偺傛偆偱偡丅
//   偦偙偱丄偙偺傾儖僑儕僘儉傪丄C尵岅斉偲偟偰幚憰偡傞帠偵偟傑偟偨丅
//   捈愙丄clipstr.c儌僕儏乕儖偺memrotate()傪曄峏偟偰傕椙偄偺偱偡偑丄姼偊偰暿娭悢std_rotate()偲偟偰幚憰偟丄memrotate()偼std_rotate()傪屇傃弌偡傛偆偵曄峏偡傞帠偵偟傑偟偨丅
//   偦偆偟偨棟桼偼丄STL傗昗弨C++儔僀僽儔儕傪尦偵偟偰嶌惉偟偨僐乕僪偼丄摉儌僕儏乕儖(clipstl.c)偵廤傔傞曽恓偩偐傜偱偡丅
// - 仩巊梡椺
//   劆void test() {
//   劆    int a[] = { 0,1,2,3,4,5,6,7,8,9 }, i;
//   劆    std_rotate(a, &a[3], &a[10]);
//   劆    for(i = 0; i < 10; i++) { printf("%d ", a[i]); }
//   劆    //寢壥:     3 4 5 6 7 8 9 0 1 2
//   劆}
// - 摉儌僕儏乕儖偵捛壛偡傞娭悢柤偵'std_'偺僾儗僼傿僋僗傪晅偗傞曽恓偱偼側偐偭偨偺偱偡偑丄'rotate'偩偗偱偼偁傑傝偵扨弮夁偓偰柤慜偺徴撍偑怱攝側偺偱丄摿暿偵'std_'偺僾儗僼傿僋僗傪晅偗傞帠偵偟傑偟偨丅
//   埲慜偵捛壛偟偨lower_bound()娭悢摍偵偼'std_'偺僾儗僼傿僋僗偼晅偗偰偄側偐偭偨偺偱摑堦偑庢傟偰偄傑偣傫偑丄幚梡忋偼栤戣柍偄偲巚偄傑偡丅
//   摉儌僕儏乕儖偵捛壛偡傞娭悢偺娭悢柤偵偮偄偰偼丄偁傑傝尩枾偵峫偊側偄帠偵偟傑偟偨丅
//   崱屻傕丄働乕僗僶僀働乕僗偱丄'std_'偺僾儗僼傿僋僗傪晅偗傞偐偳偆偐敾抐偟偰壓偝偄丅
//
//------------------------------------------------------------------------------------------------------------------------------
//
//	仩乽cppreference.com - std::rotate乿(http://en.cppreference.com/w/cpp/algorithm/rotate)傛傝堷梡:
//	劆template<class ForwardIt> void rotate(ForwardIt first, ForwardIt n_first, ForwardIt last);
//	劆
//	劆Parameters
//	劆	first		the beginning of the original range
//	劆	n_first		the element that should appear at the beginning of the rotated range
//	劆	last		the end of the original range
//	劆
//	劆Possible implementation
//	劆
//	劆	Possible implementation
//	劆	template<class ForwardIt> void rotate(ForwardIt first, ForwardIt n_first, ForwardIt last) {
//	劆		ForwardIt next = n_first;
//	劆		while(first != next) {
//	劆			std::iter_swap(first++, next++);
//	劆			if(next == last) {
//	劆				next = n_first;
//	劆			} else if(first == n_first) {
//	劆				n_first = next;
//	劆			}
//	劆		}
//	劆	}
//
//	椺偲偟偰丄
//		std::vector<int> v = {1,2,3,4,5};	//C++11側傜偽std::vector<int> v{1,2,3,4,5};偲彂偄偰傕椙偄丅(Uniform Initialization)
//	偵懳偟偰丄
//		std::rotate(v.begin(), v.begin() + 2, v.end());
//	傪峴偭偨帪偺摦嶌傪恾帵偟傑偡丅
//
//	劆	俥: first
//	劆	NF: n_first
//	劆	俴: last
//	劆	俶: next
//	劆
//	劆	嘆弶婜忬懺
//	劆
//	劆		丂丂丂丂丂NF丂丂丂丂丂俴
//	劆		劇劅劍劅劍劅劍劅劍劅劉丂
//	劆		劆侾劆俀劆俁劆係劆俆劆丂
//	劆		劋劅劏劅劏劅劏劅劏劅劊丂
//	劆		丂俥丂丂丂俶丂丂丂丂丂丂
//	劆
//	劆	嘇俥偺埵抲偺抣偲丄俶偺埵抲偺抣傪岎姺偟丄俥偲俶傪恑傔傞丅
//	劆
//	劆		丂丂丂丂丂NF丂丂丂丂丂俴
//	劆		劕劒劚劅劍劅劍劅劍劅劉丂
//	劆		劔俁劔俀劆侾劆係劆俆劆丂
//	劆		劘劒劤劅劏劅劏劅劏劅劊丂
//	劆		丂丂丂俥丂丂丂俶丂丂丂丂
//	劆
//	劆	嘊俥偺埵抲偺抣偲丄俶偺埵抲偺抣傪岎姺偟丄俥偲俶傪恑傔傞丅
//	劆
//	劆		丂丂丂丂丂NF丂丂丂丂丂俴
//	劆		劕劒劚劒劚劅劍劅劍劅劉丂
//	劆		劔俁劔係劔侾劆俀劆俆劆丂
//	劆		劘劒劤劒劤劅劏劅劏劅劊丂
//	劆		丂丂丂丂丂俥丂丂丂俶丂丂
//	劆
//	劆	嘋俥==NF偵側偭偨偺偱丄NF傪俶偺埵抲傊堏摦偡傞丅
//	劆
//	劆		丂丂丂丂丂丂丂丂丂NF丂俴
//	劆		劕劒劚劒劚劅劍劅劍劅劉丂
//	劆		劔俁劔係劔侾劆俀劆俆劆丂
//	劆		劘劒劤劒劤劅劏劅劏劅劊丂
//	劆		丂丂丂丂丂俥丂丂丂俶丂丂
//	劆
//	劆	嘍俥偺埵抲偺抣偲丄俶偺埵抲偺抣傪岎姺偟丄俥偲俶傪恑傔傞丅
//	劆
//	劆		丂丂丂丂丂丂丂丂丂NF丂俴
//	劆		劕劒劚劒劚劒劚劅劍劅劉丂
//	劆		劔俁劔係劔俆劔俀劆侾劆丂
//	劆		劘劒劤劒劤劒劤劅劏劅劊丂
//	劆		丂丂丂丂丂丂丂俥丂丂丂俶
//	劆
//	劆	嘐俶==俴偵側偭偨偺偱丄俶傪NF偺埵抲傊堏摦偡傞丅
//	劆
//	劆		丂丂丂丂丂丂丂丂丂NF丂俴
//	劆		劕劒劚劒劚劒劚劅劍劅劉丂
//	劆		劔俁劔係劔俆劔俀劆侾劆丂
//	劆		劘劒劤劒劤劒劤劅劏劅劊丂
//	劆		丂丂丂丂丂丂丂俥丂俶丂丂
//	劆
//	劆	嘑俥偺埵抲偺抣偲丄俶偺埵抲偺抣傪岎姺偟丄俥偲俶傪恑傔傞丅
//	劆
//	劆		丂丂丂丂丂丂丂丂丂NF丂俴
//	劆		劕劒劚劒劚劒劚劒劚劒劖丂
//	劆		劔俁劔係劔俆劔侾劔俀劔丂
//	劆		劘劒劤劒劤劒劤劒劤劒劗丂
//	劆		丂丂丂丂丂丂丂丂丂俥丂俶
//	劆
//	劆	嘒俶==俴偵側偭偨偺偱丄俶傪NF偺埵抲傊堏摦偡傞丅
//	劆
//	劆		丂丂丂丂丂丂丂丂丂NF丂俴
//	劆		劕劒劚劒劚劒劚劒劚劒劖丂
//	劆		劔俁劔係劔俆劔侾劔俀劔丂
//	劆		劘劒劤劒劤劒劤劒劤劒劗丂
//	劆		丂丂丂丂丂丂丂丂丂俥丂丂
//	劆		丂丂丂丂丂丂丂丂丂俶丂丂
//	劆
//	劆	嘓俥==俶偵側偭偨偺偱廔椆偡傞丅
//
//	懢宺慄偺晹暘偼丄抣偑寛掕偟偨売強傪帵偟傑偡丅
//	嵟弶偺梫慺偐傜抣偑寛掕偟偰峴偒丄堦搙寛掕偟偨梫慺偼暋悢夞彂偒姺偊傞帠偼柍偄偺偱丄岠棪揑偱偡丅
//	偟偐偟丄嘑乣嘒偺晹暘偑丄傑偩捈娤揑偵棟夝弌棃偰偄傑偣傫丅
//	屻傠擇偮偺梫慺偼丄堦帪揑偵擖傟懼偊傜傟偰尦偺暲傃偲堘偭偰偄傞偺偵丄忋婰偺傾儖僑儕僘儉偱側偤惓偟偄暲傃偵栠偣傞偺偱偟傚偆偐乧
//	偲偼尵偊丄昗弨C++儔僀僽儔儕偱偡偐傜傾儖僑儕僘儉偑惓偟偄帠偼娫堘偄側偄偺偱丄偦偺傑傑幚憰偡傞帠偵偟傑偟偨丅
//	捛乆丄棟夝偟傛偆偲巚偄傑偡丅	佀{{2016/06/08捛婰:std::rotate()偺傾儖僑儕僘儉偑棟夝弌棃偨偺偱丄僐儊儞僩傪捛婰偟傑偟偨丅偙偺偡偖壓傪嶲徠偟偰壓偝偄丅}}
//
// * Wed Jun 08 21:50:02 JST 2016 Naoyuki Sawa
// - std::rotate()偺傾儖僑儕僘儉偑棟夝弌棃傑偟偨丅
//   亂弶婜忬懺偑俙亖俛偱偁傞応崌亃亂弶婜忬懺偑俙亜俛偱偁傞応崌亃亂弶婜忬懺偑俙亙俛偱偁傞応崌亃偵暘偗偰峫偊偰堦庤弴傪幚峴偟丄偦偺屻丄巆偭偨斖埻偵懳偟偰std::rotate()偺張棟傪嵞婣幚峴偡傞偲峫偊傟偽敾傝堈偄偱偡丅
//   徻嵶偼丄偙偺壓偺恾傪嶲徠偟偰壓偝偄丅
//
//	劆	亂弶婜忬懺偑俙亖俛偱偁傞応崌亃
//	劆
//	劆		乽弶婜忬懺乿
//	劆
//	劆			丂丂丂丂NF丂丂丂俴
//	劆			劇劅劍劅劍劅劍劅劉
//	劆			劆侾劆俀劆俁劆係劆
//	劆			劋劅劏劅劏劅劏劅劊
//	劆			俥丂丂丂俶丂丂丂丂
//	劆			劆仼俙仺劆仼俛仺劆
//	劆
//	劆		乽嵟廔忬懺乿
//	劆
//	劆			劕劒劚劒劚劒劚劒劖
//	劆			劔俁劔係劔侾劔俀劔
//	劆			劘劒劤劒劤劒劤劒劗
//	劆			劆仼俛仺劆仼俙仺劆
//	劆
//	劆			乽弶婜忬懺乿偺俛傪愭摢傊堏摦偟丄偦偺暘俙傪屻傠傊偢傜偡偲丄乽嵟廔忬懺乿偵側傝傑偡丅
//	劆
//	劆
//	劆		乣乣乣庤弴乣乣乣
//	劆
//	劆			丂丂丂丂NF丂丂丂俴
//	劆			劇劅劍劅劍劅劍劅劉
//	劆			劆侾劆俀劆俁劆係劆
//	劆			劋劅劏劅劏劅劏劅劊
//	劆			俥丂丂丂俶丂丂丂丂
//	劆			劆仼俙仺劆仼俛仺劆
//	劆
//	劆			丂丂丂丂NF丂丂丂俴
//	劆			劕劒劚劅劍劅劍劅劉
//	劆			劔俁劔俀劆侾劆係劆
//	劆			劘劒劤劅劏劅劏劅劊
//	劆			丂丂俥丂丂丂俶丂丂
//	劆
//	劆			丂丂丂丂NF丂丂丂俴
//	劆			劕劒劚劒劚劅劍劅劉
//	劆			劔俁劔係劔侾劆俀劆
//	劆			劘劒劤劒劤劅劏劅劊
//	劆			丂丂丂丂俥丂丂丂俶
//	劆
//	劆			丂丂丂丂NF丂丂丂俴
//	劆			劕劒劚劒劚劒劚劒劖
//	劆			劔俁劔係劔侾劔俀劔
//	劆			劘劒劤劒劤劒劤劒劗
//	劆			丂丂丂丂俥丂丂丂丂
//	劆			丂丂丂丂俶丂丂丂丂
//	劆			劆仼俛仺劆仼俙仺劆
//	劆
//	劆			俙傕俛傕姰惉偟偨偺偱丄姰椆偱偡丅
//	劆
//	劆	亂弶婜忬懺偑俙亜俛偱偁傞応崌亃
//	劆
//	劆		乽弶婜忬懺乿
//	劆
//	劆			丂丂丂丂丂丂NF丂丂丂俴
//	劆			劇劅劍劅劍劅劍劅劍劅劉
//	劆			劆侾劆俀劆俁劆係劆俆劆
//	劆			劋劅劏劅劏劅劏劅劏劅劊
//	劆			俥丂丂丂丂丂俶丂丂丂丂
//	劆			劆仼劅俙劅仺劆仼俛仺劆
//	劆
//	劆		乽嵟廔忬懺乿
//	劆
//	劆			劕劒劚劒劚劒劚劒劚劒劖
//	劆			劔係劔俆劔侾劔俀劔俁劔
//	劆			劘劒劤劒劤劒劤劒劤劒劗
//	劆			劆仼俛仺劆仼劅俙劅仺劆
//	劆
//	劆			乽弶婜忬懺乿偺俛傪愭摢傊堏摦偟丄偦偺暘俙傪屻傠傊偢傜偡偲丄乽嵟廔忬懺乿偵側傝傑偡丅
//	劆
//	劆
//	劆		乣乣乣庤弴乣乣乣
//	劆
//	劆			丂丂丂丂丂丂NF丂丂丂俴
//	劆			劇劅劍劅劍劅劍劅劍劅劉
//	劆			劆侾劆俀劆俁劆係劆俆劆
//	劆			劋劅劏劅劏劅劏劅劏劅劊
//	劆			俥丂丂丂丂丂俶丂丂丂丂
//	劆			劆仼劅俙劅仺劆仼俛仺劆
//	劆
//	劆			丂丂丂丂丂丂NF丂丂丂俴
//	劆			劕劒劚劅劍劅劍劅劍劅劉
//	劆			劔係劔俀劆俁劆侾劆俆劆
//	劆			劘劒劤劅劏劅劏劅劏劅劊
//	劆			丂丂俥丂丂丂丂丂俶丂丂
//	劆
//	劆			丂丂丂丂丂丂NF丂丂丂俴
//	劆			劕劒劚劒劚劅劍劅劍劅劉
//	劆			劔係劔俆劔俁劆侾劆俀劆
//	劆			劘劒劤劒劤劅劏劅劏劅劊
//	劆			丂丂丂丂俥丂丂丂丂丂俶
//	劆
//	劆			丂丂丂丂丂丂NF丂丂丂俴
//	劆			劕劒劚劒劚劅劍劅劍劅劉
//	劆			劔係劔俆劔俁劆侾劆俀劆
//	劆			劘劒劤劒劤劅劏劅劏劅劊
//	劆			丂丂丂丂俥丂俶丂丂丂丂
//	劆			劆仼俛仺劆仼劅A'劅仺劆
//	劆
//	劆			偙偺帪揰偱丄俛偼姰惉偟偰偄傞丅A'偵懳偟偰丄std::rotate()偺張棟傪嵞婣幚峴偡傟偽椙偄丅
//	劆
//	劆	亂弶婜忬懺偑俙亙俛偱偁傞応崌亃
//	劆
//	劆		乽弶婜忬懺乿
//	劆
//	劆			丂丂丂丂NF丂丂丂丂丂俴
//	劆			劇劅劍劅劍劅劍劅劍劅劉
//	劆			劆侾劆俀劆俁劆係劆俆劆
//	劆			劋劅劏劅劏劅劏劅劏劅劊
//	劆			俥丂丂丂俶丂丂丂丂丂丂
//	劆			劆仼俙仺劆仼劅俛劅仺劆
//	劆
//	劆		乽嵟廔忬懺乿
//	劆
//	劆			劕劒劚劒劚劒劚劒劚劒劖
//	劆			劔俁劔係劔俆劔侾劔俀劔
//	劆			劘劒劤劒劤劒劤劒劤劒劗
//	劆			劆仼劅俛劅仺劆仼俙仺劆
//	劆
//	劆			乽弶婜忬懺乿偺俛傪愭摢傊堏摦偟丄偦偺暘俙傪屻傠傊偢傜偡偲丄乽嵟廔忬懺乿偵側傝傑偡丅
//	劆
//	劆
//	劆		乣乣乣庤弴乣乣乣
//	劆
//	劆			丂丂丂丂NF丂丂丂丂丂俴
//	劆			劇劅劍劅劍劅劍劅劍劅劉
//	劆			劆侾劆俀劆俁劆係劆俆劆
//	劆			劋劅劏劅劏劅劏劅劏劅劊
//	劆			俥丂丂丂俶丂丂丂丂丂丂
//	劆			劆仼俙仺劆仼劅俛劅仺劆
//	劆
//	劆			丂丂丂丂NF丂丂丂丂丂俴
//	劆			劕劒劚劅劍劅劍劅劍劅劉
//	劆			劔俁劔俀劆侾劆係劆俆劆
//	劆			劘劒劤劅劏劅劏劅劏劅劊
//	劆			丂丂俥丂丂丂俶丂丂丂丂
//	劆
//	劆			丂丂丂丂NF丂丂丂丂丂俴
//	劆			劕劒劚劒劚劅劍劅劍劅劉
//	劆			劔俁劔係劔侾劆俀劆俆劆
//	劆			劘劒劤劒劤劅劏劅劏劅劊
//	劆			丂丂丂丂俥丂丂丂俶丂丂
//	劆
//	劆			丂丂丂丂丂丂丂丂NF丂俴
//	劆			劕劒劚劒劚劅劍劅劍劅劉
//	劆			劔俁劔係劔侾劆俀劆俆劆
//	劆			劘劒劤劒劤劅劏劅劏劅劊
//	劆			丂丂丂丂俥丂丂丂俶丂丂
//	劆			劆仼B'仺劆仼劅A'劅仺劆
//	劆
//	劆			偙偺帪揰偱丄B'偼姰惉偟偰偄傞丅A'偵懳偟偰丄std::rotate()偺張棟傪嵞婣幚峴偡傟偽椙偄丅
//	劆
//------------------------------------------------------------------------------------------------------------------------------
#ifndef PIECE
static void std_rotate_word(int* first, int* n_first, int* last) {
	int* next = n_first;
    //{{偙偺斖埻偺C尵岅僜乕僗偼丄std_rotate_byte()/std_rotate_half()/std_rotate_word()偱嫟捠偱偡丅
	while(first != next) {
		int tmp = *first;
		          *first++ = *next;
		                     *next++ = tmp;
		if(next == last) {
			next = n_first;
		} else if(first == n_first) {
			n_first = next;
		}
	}
    //}}偙偺斖埻偺C尵岅僜乕僗偼丄std_rotate_byte()/std_rotate_half()/std_rotate_word()偱嫟捠偱偡丅
}
static void std_rotate_half(short* first, short* n_first, short* last) {
	short* next = n_first;
    //{{偙偺斖埻偺C尵岅僜乕僗偼丄std_rotate_byte()/std_rotate_half()/std_rotate_word()偱嫟捠偱偡丅
	while(first != next) {
		int tmp = *first;
		          *first++ = *next;
		                     *next++ = tmp;
		if(next == last) {
			next = n_first;
		} else if(first == n_first) {
			n_first = next;
		}
	}
    //}}偙偺斖埻偺C尵岅僜乕僗偼丄std_rotate_byte()/std_rotate_half()/std_rotate_word()偱嫟捠偱偡丅
}
static void std_rotate_byte(char* first, char* n_first, char* last) {
	char* next = n_first;
    //{{偙偺斖埻偺C尵岅僜乕僗偼丄std_rotate_byte()/std_rotate_half()/std_rotate_word()偱嫟捠偱偡丅
	while(first != next) {
		int tmp = *first;
		          *first++ = *next;
		                     *next++ = tmp;
		if(next == last) {
			next = n_first;
		} else if(first == n_first) {
			n_first = next;
		}
	}
    //}}偙偺斖埻偺C尵岅僜乕僗偼丄std_rotate_byte()/std_rotate_half()/std_rotate_word()偱嫟捠偱偡丅
}
void std_rotate(void* first, void* n_first, void* last) {
//{{2016/09/04曄峏:std_rotate()偑丄(int)偱傾僪儗僗墘嶼傪峴偭偰偄偨偺傪丄(intptr_t)偱峴偆傛偆偵廋惓偟傑偟偨丅
//	int x = (int)first | (int)n_first | (int)last;
//伀2016/09/04曄峏:std_rotate()偑丄(int)偱傾僪儗僗墘嶼傪峴偭偰偄偨偺傪丄(intptr_t)偱峴偆傛偆偵廋惓偟傑偟偨丅
	intptr_t x = (intptr_t)first | (intptr_t)n_first | (intptr_t)last;
//}}2016/09/04曄峏:std_rotate()偑丄(int)偱傾僪儗僗墘嶼傪峴偭偰偄偨偺傪丄(intptr_t)偱峴偆傛偆偵廋惓偟傑偟偨丅
	if(!(x & 3)) {
		std_rotate_word(first, n_first, last);	//first,n_first,last偑慡偰儚乕僪惍楍偟偰偄傞応崌
	} else if(!(x & 1)) {
		std_rotate_half(first, n_first, last);	//first,n_first,last偑慡偰僴乕僼儚乕僪惍楍偟偰偄傞応崌
	} else {
		std_rotate_byte(first, n_first, last);	//first,n_first,last偑堦偮偱傕婏悢傾僪儗僗偺応崌
	}
}
#else //PIECE
void std_rotate(void* first, void* n_first, void* last);
//仩崅懍壔専徹僾儘僌儔儉丅奺僶乕僕儑儞偵婰嵹偟偨帪娫偼丄偙偺僾儘僌儔儉偱寁應偟偨帪娫偱偡丅
//劆int test() {
//劆  static int buf[16384];
//劆  int i, t1, t2, t3;
//劆  t1 = pceTimerGetCount();
//劆  for(i = 0; i < 100; i++) { std_rotate(&buf[0], &buf[1], &buf[16384]); }		//偳偺僶乕僕儑儞偱傕摨偠懍搙偱偡丅
//劆  t1 = pceTimerGetCount() - t1;
//劆  t2 = pceTimerGetCount();
//劆  for(i = 0; i < 100; i++) { std_rotate(&buf[0], &buf[16384/2], &buf[16384]); }	//'崅懍壔慜偺僶乕僕儑儞'偑掅懍偱丄'崅懍壔僶乕僕儑儞1'偲'崅懍壔僶乕僕儑儞2'偑崅懍偱偡丅
//劆  t2 = pceTimerGetCount() - t2;
//劆  t3 = pceTimerGetCount();
//劆  for(i = 0; i < 100; i++) { std_rotate(&buf[0], &buf[16384-1], &buf[16384]); }	//'崅懍壔慜偺僶乕僕儑儞'偲'崅懍壔僶乕僕儑儞1'偑掅懍偱丄'崅懍壔僶乕僕儑儞2'偑崅懍偱偡丅
//劆  t3 = pceTimerGetCount() - t3;
//劆  die("%d[ms]\n%d[ms]\n%d[ms]", t1, t2, t3);
//劆}
//埲忋偺専徹寢壥傛傝丄'崅懍壔僶乕僕儑儞2'偑嵟懍偱偁傞帠偑敾傝丄'崅懍壔僶乕僕儑儞2'傪嵦梡偡傞帠偵偟傑偟偨丅
//彯丄僐乕僪僒僀僘偼丄'崅懍壔慜偺僶乕僕儑儞'偑3柦椷彮側偔丄'崅懍壔僶乕僕儑儞1'偲'崅懍壔僶乕僕儑儞2'偼摨偠僐乕僪僒僀僘偱偡丅
//3柦椷掱搙偺憹壛側傜偽嫋梕斖埻偩偲巚偆偺偱丄'崅懍壔僶乕僕儑儞2'傪嵦梡偡傞帠偵栤戣偼桳傝傑偣傫丅
#if 0
//仩崅懍壔慜偺僶乕僕儑儞	2830[ms] 1347[ms] 2554[ms]
asm("
		.code
		.align		1
		.global		std_rotate
std_rotate:
		;//%r12 := first
		;//%r13 := n_first
		;//%r14 := last
		ld.w		%r9, %r12			;//%r9  :=  first
		or		%r9, %r13			;//%r9  :=  first|n_first
		or		%r9, %r14			;//%r9  :=  first|n_first|last
		and		%r9, 3				;//%r9  := (first|n_first|last)&3
		jreq		std_rotate_word			;//if(    !(first|n_first|last)&3) { goto std_rotate_word }
		and		%r9, 1				;//%r9  := (first|n_first|last)&1
		jreq		std_rotate_half			;//if(    !(first|n_first|last)&1) { goto std_rotate_half }
		;/* FALLTHRU */					;//                                { goto std_rotate_byte }
		;//---------------------------------------------;//
std_rotate_byte:
		ld.w		%r15, %r13			;//%r15 := next = n_first
std_rotate_byte_LOOP:						;//for(;;) {
		cmp		%r12, %r15			;//  if(first == next) { return }
		jreq		std_rotate_RET			;//  
		ld.b		%r4, [%r12]			;//  %r4  := tmp1 = *first
		ld.b		%r5, [%r15]			;//  %r5  := tmp2 = *next
		ld.b		[%r15]+, %r4			;//  *next++  = tmp1						*anti-interlock*
		ld.b		[%r12]+, %r5			;//  *first++ = tmp2
		cmp		%r15, %r14			;//  if(next == last) { next = n_first }
		jreq		std_rotate_byte			;//  
		cmp		%r12, %r13			;//  if(first != n_first) { continue }
		jrne		std_rotate_byte_LOOP		;//  
		jp.d		std_rotate_byte_LOOP		;//}
		ld.w		%r13, %r15			;//  %r13 := n_first = next					*delay*
		;//---------------------------------------------;//
std_rotate_half:
		ld.w		%r15, %r13			;//%r15 := next = n_first
std_rotate_half_LOOP:						;//for(;;) {
		cmp		%r12, %r15			;//  if(first == next) { return }
		jreq		std_rotate_RET			;//  
		ld.h		%r4, [%r12]			;//  %r4  := tmp1 = *first
		ld.h		%r5, [%r15]			;//  %r5  := tmp2 = *next
		ld.h		[%r15]+, %r4			;//  *next++  = tmp1						*anti-interlock*
		ld.h		[%r12]+, %r5			;//  *first++ = tmp2
		cmp		%r15, %r14			;//  if(next == last) { next = n_first }
		jreq		std_rotate_half			;//  
		cmp		%r12, %r13			;//  if(first != n_first) { continue }
		jrne		std_rotate_half_LOOP		;//  
		jp.d		std_rotate_half_LOOP		;//}
		ld.w		%r13, %r15			;//  %r13 := n_first = next					*delay*
		;//---------------------------------------------;//
std_rotate_word:
		ld.w		%r15, %r13			;//%r15 := next = n_first
std_rotate_word_LOOP:						;//for(;;) {
		cmp		%r12, %r15			;//  if(first == next) { return }
		jreq		std_rotate_RET			;//  
		ld.w		%r4, [%r12]			;//  %r4  := tmp1 = *first
		ld.w		%r5, [%r15]			;//  %r5  := tmp2 = *next
		ld.w		[%r15]+, %r4			;//  *next++  = tmp1						*anti-interlock*
		ld.w		[%r12]+, %r5			;//  *first++ = tmp2
		cmp		%r15, %r14			;//  if(next == last) { next = n_first }
		jreq		std_rotate_word			;//  
		cmp		%r12, %r13			;//  if(first != n_first) { continue }
		jrne		std_rotate_word_LOOP		;//  
		jp.d		std_rotate_word_LOOP		;//}
		ld.w		%r13, %r15			;//  %r13 := n_first = next					*delay*
		;//---------------------------------------------;//
std_rotate_RET:
		ret
");
#elif 0
//仩崅懍壔僶乕僕儑儞1		2830[ms] 1278[ms] 2554[ms]
asm("
		.code
		.align		1
		.global		std_rotate
std_rotate:
		;//%r12 := first
		;//%r13 := n_first
		;//%r14 := last
		ld.w		%r9, %r12			;//%r9  :=  first
		or		%r9, %r13			;//%r9  :=  first|n_first
		or		%r9, %r14			;//%r9  :=  first|n_first|last
		and		%r9, 3				;//%r9  := (first|n_first|last)&3
		jreq		std_rotate_word			;//if(    !(first|n_first|last)&3) { goto std_rotate_word }
		and		%r9, 1				;//%r9  := (first|n_first|last)&1
		jreq		std_rotate_half			;//if(    !(first|n_first|last)&1) { goto std_rotate_half }
		;/* FALLTHRU */					;//                                { goto std_rotate_byte }
		;//---------------------------------------------;//
std_rotate_byte:
		ld.w		%r15, %r13			;//%r15 := next = n_first
		cmp		%r12, %r15			;//  	仼劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劉
std_rotate_byte_LOOP:						;//for(;;) {					劆
	;//	cmp		%r12, %r15			;//  if(first == next) { return }	劅劅劅劅劎	儖乕僾帪偺抶墑僗儘僢僩傪妶梡偡傞偨傔偵偙偺峴偺柦椷傪擇偐強偵暘偗偨丅彮偟僐乕僪僒僀僘偑憹偊傞偑懍搙傪桪愭偡傞帠偵偟偨丅
		jreq		std_rotate_RET			;//  						劆
		ld.b		%r4, [%r12]			;//  %r4  := tmp1 = *first			劆
		ld.b		%r5, [%r15]			;//  %r5  := tmp2 = *next			劆
		ld.b		[%r15]+, %r4			;//  *next++  = tmp1				劆		*anti-interlock*
		ld.b		[%r12]+, %r5			;//  *first++ = tmp2				劆
		cmp		%r15, %r14			;//  if(next == last) { next = n_first }	劆
		jreq		std_rotate_byte			;//  						劆
		cmp		%r12, %r13			;//  if(first != n_first) { continue }		劆
		jrne.d		std_rotate_byte_LOOP		;//  						劆
		cmp		%r12, %r15			;//  	仼劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劊		*delay*
		jp.d		std_rotate_byte_LOOP		;//}
		ld.w		%r13, %r15			;//  %r13 := n_first = next					*delay*
		;//---------------------------------------------;//
std_rotate_half:
		ld.w		%r15, %r13			;//%r15 := next = n_first
		cmp		%r12, %r15			;//  	仼劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劉
std_rotate_half_LOOP:						;//for(;;) {					劆
	;//	cmp		%r12, %r15			;//  if(first == next) { return }	劅劅劅劅劎	儖乕僾帪偺抶墑僗儘僢僩傪妶梡偡傞偨傔偵偙偺峴偺柦椷傪擇偐強偵暘偗偨丅彮偟僐乕僪僒僀僘偑憹偊傞偑懍搙傪桪愭偡傞帠偵偟偨丅
		jreq		std_rotate_RET			;//  						劆
		ld.h		%r4, [%r12]			;//  %r4  := tmp1 = *first			劆
		ld.h		%r5, [%r15]			;//  %r5  := tmp2 = *next			劆
		ld.h		[%r15]+, %r4			;//  *next++  = tmp1				劆		*anti-interlock*
		ld.h		[%r12]+, %r5			;//  *first++ = tmp2				劆
		cmp		%r15, %r14			;//  if(next == last) { next = n_first }	劆
		jreq		std_rotate_half			;//  						劆
		cmp		%r12, %r13			;//  if(first != n_first) { continue }		劆
		jrne.d		std_rotate_half_LOOP		;//  						劆
		cmp		%r12, %r15			;//  	仼劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劊		*delay*
		jp.d		std_rotate_half_LOOP		;//}
		ld.w		%r13, %r15			;//  %r13 := n_first = next					*delay*
		;//---------------------------------------------;//
std_rotate_word:
		ld.w		%r15, %r13			;//%r15 := next = n_first
		cmp		%r12, %r15			;//  	仼劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劉
std_rotate_word_LOOP:						;//for(;;) {					劆
	;//	cmp		%r12, %r15			;//  if(first == next) { return }	劅劅劅劅劎	儖乕僾帪偺抶墑僗儘僢僩傪妶梡偡傞偨傔偵偙偺峴偺柦椷傪擇偐強偵暘偗偨丅彮偟僐乕僪僒僀僘偑憹偊傞偑懍搙傪桪愭偡傞帠偵偟偨丅
		jreq		std_rotate_RET			;//  						劆
		ld.w		%r4, [%r12]			;//  %r4  := tmp1 = *first			劆
		ld.w		%r5, [%r15]			;//  %r5  := tmp2 = *next			劆
		ld.w		[%r15]+, %r4			;//  *next++  = tmp1				劆		*anti-interlock*
		ld.w		[%r12]+, %r5			;//  *first++ = tmp2				劆
		cmp		%r15, %r14			;//  if(next == last) { next = n_first }	劆
		jreq		std_rotate_word			;//  						劆
		cmp		%r12, %r13			;//  if(first != n_first) { continue }		劆
		jrne.d		std_rotate_word_LOOP		;//  						劆
		cmp		%r12, %r15			;//  	仼劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劊		*delay*
		jp.d		std_rotate_word_LOOP		;//}
		ld.w		%r13, %r15			;//  %r13 := n_first = next					*delay*
		;//---------------------------------------------;//
std_rotate_RET:
		ret
");
#elif 1
//仩崅懍壔僶乕僕儑儞2		2830[ms] 1278[ms] 2416[ms]	仼仼仼仼仼偙傟傪嵦梡偡傞帠偵寛掕偟傑偟偨丅'崅懍壔僶乕僕儑儞2'偼'崅懍壔僶乕僕儑儞1'傪尦偵偝傜偵抶墑僗儘僢僩傪妶梡偟偨傕偺偱偡偑丄'崅懍壔僶乕僕儑儞2'偺僐乕僪偩偗傪撉傓偲棟夝偟恏偄偲巚偄傑偡丅'崅懍壔僶乕僕儑儞1'偲'崅懍壔僶乕僕儑儞2'傪斾妑偟偰尒傟偽丄'崅懍壔僶乕僕儑儞2'偺僐乕僪傕棟夝弌棃傞偲巚偄傑偡丅
asm("
		.code
		.align		1
		.global		std_rotate
std_rotate:
		;//%r12 := first
		;//%r13 := n_first
		;//%r14 := last
		ld.w		%r9, %r12			;//%r9  :=  first
		or		%r9, %r13			;//%r9  :=  first|n_first
		or		%r9, %r14			;//%r9  :=  first|n_first|last
		and		%r9, 3				;//%r9  := (first|n_first|last)&3
		jreq		std_rotate_word			;//if(    !(first|n_first|last)&3) { goto std_rotate_word }
		and		%r9, 1				;//%r9  := (first|n_first|last)&1
		jreq		std_rotate_half			;//if(    !(first|n_first|last)&1) { goto std_rotate_half }
		;/* FALLTHRU */					;//                                { goto std_rotate_byte }
		;//---------------------------------------------;//
std_rotate_byte:
		cmp		%r12, %r13			;//%psr := first <=> n_first	仼劅劅劅劅劅劅劅劉
std_rotate_byte_NEXT:						;//						劆
		ld.w		%r15, %r13			;//%r15 := next = n_first			劆
std_rotate_byte_LOOP:						;//for(;;) {					劆
	;//	cmp		%r12, %r15			;//  if(first == next) { return }	劅劅劅劅劎	儖乕僾帪偺抶墑僗儘僢僩傪妶梡偡傞偨傔偵偙偺峴偺柦椷傪擇偐強偵暘偗偨丅彮偟僐乕僪僒僀僘偑憹偊傞偑懍搙傪桪愭偡傞帠偵偟偨丅
		jreq		std_rotate_RET			;//  						劆
		ld.b		%r4, [%r12]			;//  %r4  := tmp1 = *first			劆
		ld.b		%r5, [%r15]			;//  %r5  := tmp2 = *next			劆
		ld.b		[%r15]+, %r4			;//  *next++  = tmp1				劆		*anti-interlock*
		ld.b		[%r12]+, %r5			;//  *first++ = tmp2				劆
		cmp		%r15, %r14			;//  if(next == last) { next = n_first }	劆
		jreq.d		std_rotate_byte_NEXT		;//  						劆
		cmp		%r12, %r13			;//  if(first != n_first) { continue }		劆		*delay*		偙偺'cmp %r12,%r13'偑丄僕儍儞僾愭偱峴偆傋偒'ld.w %r15,%r13; cmp %r12,%r15'偺撪偺丄'cmp %r12,%r15'偺戙梡偲側傝傑偡丅
		jrne.d		std_rotate_byte_LOOP		;//  						劆
		cmp		%r12, %r15			;//  	仼劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劊		*delay*
		jp.d		std_rotate_byte_LOOP		;//}
		ld.w		%r13, %r15			;//  %r13 := n_first = next					*delay*
		;//---------------------------------------------;//
std_rotate_half:
		cmp		%r12, %r13			;//%psr := first <=> n_first	仼劅劅劅劅劅劅劅劉
std_rotate_half_NEXT:						;//						劆
		ld.w		%r15, %r13			;//%r15 := next = n_first			劆
std_rotate_half_LOOP:						;//for(;;) {					劆
	;//	cmp		%r12, %r15			;//  if(first == next) { return }	劅劅劅劅劎	儖乕僾帪偺抶墑僗儘僢僩傪妶梡偡傞偨傔偵偙偺峴偺柦椷傪擇偐強偵暘偗偨丅彮偟僐乕僪僒僀僘偑憹偊傞偑懍搙傪桪愭偡傞帠偵偟偨丅
		jreq		std_rotate_RET			;//  						劆
		ld.h		%r4, [%r12]			;//  %r4  := tmp1 = *first			劆
		ld.h		%r5, [%r15]			;//  %r5  := tmp2 = *next			劆
		ld.h		[%r15]+, %r4			;//  *next++  = tmp1				劆		*anti-interlock*
		ld.h		[%r12]+, %r5			;//  *first++ = tmp2				劆
		cmp		%r15, %r14			;//  if(next == last) { next = n_first }	劆
		jreq.d		std_rotate_half_NEXT		;//  						劆
		cmp		%r12, %r13			;//  if(first != n_first) { continue }		劆		*delay*		偙偺'cmp %r12,%r13'偑丄僕儍儞僾愭偱峴偆傋偒'ld.w %r15,%r13; cmp %r12,%r15'偺撪偺丄'cmp %r12,%r15'偺戙梡偲側傝傑偡丅
		jrne.d		std_rotate_half_LOOP		;//  						劆
		cmp		%r12, %r15			;//  	仼劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劊		*delay*
		jp.d		std_rotate_half_LOOP		;//}
		ld.w		%r13, %r15			;//  %r13 := n_first = next					*delay*
		;//---------------------------------------------;//
std_rotate_word:
		cmp		%r12, %r13			;//%psr := first <=> n_first	仼劅劅劅劅劅劅劅劉
std_rotate_word_NEXT:						;//						劆
		ld.w		%r15, %r13			;//%r15 := next = n_first			劆
std_rotate_word_LOOP:						;//for(;;) {					劆
	;//	cmp		%r12, %r15			;//  if(first == next) { return }	劅劅劅劅劎	儖乕僾帪偺抶墑僗儘僢僩傪妶梡偡傞偨傔偵偙偺峴偺柦椷傪擇偐強偵暘偗偨丅彮偟僐乕僪僒僀僘偑憹偊傞偑懍搙傪桪愭偡傞帠偵偟偨丅
		jreq		std_rotate_RET			;//  						劆
		ld.w		%r4, [%r12]			;//  %r4  := tmp1 = *first			劆
		ld.w		%r5, [%r15]			;//  %r5  := tmp2 = *next			劆
		ld.w		[%r15]+, %r4			;//  *next++  = tmp1				劆		*anti-interlock*
		ld.w		[%r12]+, %r5			;//  *first++ = tmp2				劆
		cmp		%r15, %r14			;//  if(next == last) { next = n_first }	劆
		jreq.d		std_rotate_word_NEXT		;//  						劆
		cmp		%r12, %r13			;//  if(first != n_first) { continue }		劆		*delay*		偙偺'cmp %r12,%r13'偑丄僕儍儞僾愭偱峴偆傋偒'ld.w %r15,%r13; cmp %r12,%r15'偺撪偺丄'cmp %r12,%r15'偺戙梡偲側傝傑偡丅
		jrne.d		std_rotate_word_LOOP		;//  						劆
		cmp		%r12, %r15			;//  	仼劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劅劊		*delay*
		jp.d		std_rotate_word_LOOP		;//}
		ld.w		%r13, %r15			;//  %r13 := n_first = next					*delay*
		;//---------------------------------------------;//
std_rotate_RET:
		ret
");
#endif
#endif//PIECE
