/*	
 *	cliprnd.h
 *
 *	乱数
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2015 Naoyuki Sawa
 *
 *	* Tue Jan 06 21:26:41 JST 2015 Naoyuki Sawa
 *	- 新規作成。
 *	- 乱数関連の宣言と実装を、clipmisc.*⇒cliprnd.*へ分離しました。
 *	  使用頻度は高いので、無駄なリンクを防ぐためと言うよりも、モジュール分けして分り易くするためです。
 */
#ifndef __CLIP_RND_H__
#define __CLIP_RND_H__

/*****************************************************************************
 *	乱数
 *****************************************************************************/

///* 8ビット乱数(『Z80マシン語秘伝の書』より) */
//#define RND8(s)	(((s) = (s) * 5 + 0x3711) >> 8 & 0xff)
///* 16ビット乱数(VisualC++ 6.0 \VC98\CRT\SRC\RAND.C を参考にしました) */
//#define RND16(s)	(((s) = (s) * 214013 + 2531011) >> 16 & 0xffff)
//↓2004/09/15 コンパイラバグ(?)で負値になってしまう場合があったので、本体処理を関数化しました。
//↓           過去のソースの互換性のため、関数を呼び出すマクロも定義してあります。
/* 8ビット乱数 */
int rnd8(int* seed);			/* 戻り値の型は符号付き(int)で、範囲は+0x00000000～+0x000000FFです。 */
#define RND8(s)		(rnd8(&(s)))
/* 16ビット乱数 */
int rnd16(int* seed);			/* 戻り値の型は符号付き(int)で、範囲は+0x00000000～+0x0000FFFFです。 */
#define RND16(s)	(rnd16(&(s)))
/* 32ビット乱数 */
int rnd32(int* seed);			/* 戻り値の型は符号付き(int)で、範囲は-0x80000000～+0x7FFFFFFFです。要注意!! */
#define RND32(s)	(rnd32(&(s)))

/* (a)以上(b)★未満★の乱数を生成 */
//#define RND8_RANGE(s, a, b)	(RND8(s) % ((b) - (a)) + (a))
//#define RND16_RANGE(s, a, b)	(RND16(s) % ((b) - (a)) + (a))
//↓2004/09/15 コンパイラバグ(?)で負値になってしまう場合があったので、本体処理を関数化しました。
//↓           過去のソースの互換性のため、関数を呼び出すマクロも定義してあります。
/* (a)以上(b)★未満★の乱数を生成 */
int rnd8_range(int* seed, int a, int b);
#define RND8_RANGE(s, a, b)	(rnd8_range(&(s), (a), (b)))
int rnd16_range(int* seed, int a, int b);
#define RND16_RANGE(s, a, b)	(rnd16_range(&(s), (a), (b)))
int rnd32_range(int* seed, int a, int b);
#define RND32_RANGE(s, a, b)	(rnd32_range(&(s), (a), (b)))

/* 配列要素をシャッフルします。
 * [in]
 *	base		配列の先頭アドレス。
 *	num		配列の要素数。
 *	width		配列要素ひとつ当りのバイト数。
 *	seed		シャッフル用乱数シード。
 * [note]
 *	* 引数の並びは、最後のseed以外、標準Cライブラリのqsort()関数に互換です。
 *	* numが0未満ならば、不正な配列と見なしてアサートします。
 *	// * 2005/03/31現在の実装は、16bit乱数を利用しているために、65536要素以上の配列をシャッフルできません。
 *	//   numが65536よりも大きいと、アサートします。
 *	↓2006/07/06 追記
 *	* Thu Jul 06 11:48:53 JST 2006 Naoyuki Sawa
 *	- rnd32()の新設に伴い、16bit乱数→32bit乱数を利用するよう変更しました。
 *	  この変更により、65536要素以上の配列をシャッフルできなかった制限が無くなりました。
 */
//void shuffle(void* base, int num, int width, int seed);
//↓* Mon Oct 31 05:10:00 JST 2005 Naoyuki Sawa
//↓- shuffle()関数にて、seed引数を参照で受け取り、乱数シードを更新するよう変更しました。
//↓  これまでは、呼び出し側にて乱数シードを更新する必要がありましたが、今後は不要となります。
//↓  <変更前の使用例> shuffle(array, 10, sizeof(int), RND16(seed));
//↓  <変更後の使用例> shuffle(array, 10, sizeof(int), &seed);
void shuffle(void* base, int num, int width, int* seed);

/*****************************************************************************
 *	ユーティリティ：範囲乱数
 *****************************************************************************/

/* 0～xの範囲で正確に分布する、乱数値を取得します。
 * [in]
 *	x		乱数値の最大値(xも含みます)
 *	generator	乱数生成関数
 *	param		乱数生成関数への引数
 * [out]
 *	戻り値		乱数値
 * [note]
 *	- 正確な分布で特定の範囲の乱数を取得する方法を定義するために、本関数を作成しました。
 *
 *	- 特定の範囲の乱数を取得する場合、剰余を使用すると、正確な分布が得られません。
 *	  以下、極端な例を挙げて説明します。
 *	  
 *	  0～255の乱数を生成する関数を利用して、0～99の範囲の乱数を取得するケースを考えます:
 *	    //0～255の乱数を生成する関数 (Test1～Test3で共通使用)
 *	    unsigned SimpleRng(unsigned* s) {
 *	      (*s) = (*s) * 5 + 0x3711;
 *	      return (unsigned char)((*s) >> 8);
 *	    }
 *	  
 *	  ■実験① 剰余を用いる方法
 *	    void Test1() {
 *	      unsigned s = 0, i, r, c[100];
 *	      memset(c, 0, sizeof c);
 *	      for(i = 0; i < 10000000; i++) {
 *	        r = SimpleRng(&s) % 100; //←①
 *	        c[r]++;
 *	      }
 *	      die("c[0]=%d,c[99]=%d", c[0], c[99]);
 *	      //⇒結果: c[0]=117179,c[99]=78111
 *	    }
 *	  □考察
 *	    [0]の回数が[99]の回数よりも明らかに多く、一様な乱数が得られていません。
 *	    原因は、0～255を100で剰余すると、200～255の分が、0～55への偏りになるからです。
 *	    解決策は、乱数生成関数から得られた値のうち、範囲外の値を捨てることです。
 *	  
 *	  ■実験② 範囲内の値となるまで繰り返す方法
 *	    void Test2() {
 *	      unsigned s = 0, i, r, c[100];
 *	      memset(c, 0, sizeof c);
 *	      for(i = 0; i < 10000000; i++) {
 *	        do { r = SimpleRng(&s); } while(r > 99); //←②
 *	        c[r]++;
 *	      }
 *	      die("c[0]=%d,c[99]=%d", c[0], c[99]);
 *	      //⇒結果: c[0]= 99993,c[99]=99986
 *	    }
 *	  □考察
 *	    [0]の回数と[99]の回数がほぼ同じとなり、一様な乱数が得られました。
 *	    ただし、②の方法は、実行速度の問題が生じるケースがあります。
 *	    仮に、乱数生成関数が0～65535を返し、得たい範囲が0～9だったとすると、0～9を得るまでに多くの回数繰り返す必要が生じます。
 *	    改善策として、乱数生成関数から返された値の、上位ビット一定範囲を捨てた後、範囲内の値となるまで繰り返す方法を採ります。
 *	    一般的に、乱数生成関数は[0～(2^N-1)]の値を生成するので、上位ビット一定範囲を捨てても、一様な分布に影響は無いはずです。
 *	  
 *	  ■実験③ マスクを取って範囲内の値となるまで繰り返す方法
 *	    void Test3() {
 *	      unsigned s = 0, i, r, c[100];
 *	      memset(c, 0, sizeof c);
 *	      for(i = 0; i < 10000000; i++) {
 *	        do { r = SimpleRng(&s) & 127; } while(r > 99); //←③
 *	        c[r]++;
 *	      }
 *	      die("c[0]=%d,c[99]=%d", c[0], c[99]);
 *	      //⇒結果: c[0]=100007,c[99]=99999
 *	    }
 *	  □考察
 *	    ②と同様に、[0]の回数と[99]の回数がほぼ同じであり、一様な乱数が得られています。
 *	    ③の方法ならば、範囲内の値となるまで繰り返す回数は、平均2回程度となるはずです。
 *	  
 *	  ■結論 "実験③"と同じ方法を、本関数を利用して実行する方法は、以下の通りです:
 *	    void Test4() {
 *	      unsigned s = 0, i, r, c[100];
 *	      memset(c, 0, sizeof c);
 *	      for(i = 0; i < 10000000; i++) {
 *	        r = random_value_less_than_or_equal_to(99, (unsigned(*)(void*))SimpleRng, &s); //←④
 *	        c[r]++;
 *	      }
 *	      die("c[0]=%d,c[99]=%d", c[0], c[99]);
 *	      //⇒結果: c[0]=100007,c[99]=99999
 *	    }
 *
 *	- 既存の乱数生成関数を利用しての、使用例を挙げます:
 *	  ＜例:Xorshift乱数＞
 *	    int s = pceTimerGetCount();
 *	    r = random_value_less_than_or_equal_to(<最大値>, (unsigned(*)(void*))rnd32, &s);
 *	  ＜例:MT乱数＞
 *	    MT mt;
 *	    MT_init(&mt, pceTimerGetCount());
 *	    r = random_value_less_than_or_equal_to(<最大値>, (unsigned(*)(void*))MT_int32, &mt);
 *	  ＜例:WELL乱数＞
 *	    WELL w;
 *	    WELL_init(&w, pceTimerGetCount());
 *	    r = random_value_less_than_or_equal_to(<最大値>, (unsigned(*)(void*))WELL_next, &w);
 *	  ＜例:JKISS32乱数＞
 *	    JKISS32 jk;
 *	    JKISS32_init(&jk, pceTimerGetCount());
 *	    r = random_value_less_than_or_equal_to(<最大値>, (unsigned(*)(void*))JKISS32_next, &jk);
 */
unsigned random_value_less_than_or_equal_to(unsigned x, unsigned (*generator)(void* param), void* param);

/* x以上,かつ,最小の、マスク値を作成します。
 * [in]
 *	x		マスク値を作成する値
 * [out]
 *	戻り値		マスク値
 * [note]
 *	- 主に、random_value_less_than_or_equal_to()から利用するために作成しましたが、
 *	  汎用的なので、アプリケーションからも利用できるよう、宣言することにしました。
 *	- 引数(x)と、戻り値(マスク値)の対応は、以下の通りです:
 *	  ----------------------    ----------
 *	        引数の範囲            戻り値  
 *	  ----------------------    ----------
 *	  0x00000000             ⇒ 0x00000000
 *	  0x00000001             ⇒ 0x00000001
 *	  0x00000002～0x00000003 ⇒ 0x00000003
 *	  0x00000004～0x00000007 ⇒ 0x00000007
 *	  0x00000008～0x0000000F ⇒ 0x0000000F
 *	  0x00000010～0x0000001F ⇒ 0x0000001F
 *	  0x00000020～0x0000003F ⇒ 0x0000003F
 *	  0x00000040～0x0000007F ⇒ 0x0000007F
 *	  0x00000080～0x000000FF ⇒ 0x000000FF
 *	  0x00000100～0x000001FF ⇒ 0x000001FF
 *	  0x00000200～0x000003FF ⇒ 0x000003FF
 *	  0x00000400～0x000007FF ⇒ 0x000007FF
 *	  0x00000800～0x00000FFF ⇒ 0x00000FFF
 *	  0x00001000～0x00001FFF ⇒ 0x00001FFF
 *	  0x00002000～0x00003FFF ⇒ 0x00003FFF
 *	  0x00004000～0x00007FFF ⇒ 0x00007FFF
 *	  0x00008000～0x0000FFFF ⇒ 0x0000FFFF
 *	  0x00010000～0x0001FFFF ⇒ 0x0001FFFF
 *	  0x00020000～0x0003FFFF ⇒ 0x0003FFFF
 *	  0x00040000～0x0007FFFF ⇒ 0x0007FFFF
 *	  0x00080000～0x000FFFFF ⇒ 0x000FFFFF
 *	  0x00100000～0x001FFFFF ⇒ 0x001FFFFF
 *	  0x00200000～0x003FFFFF ⇒ 0x003FFFFF
 *	  0x00400000～0x007FFFFF ⇒ 0x007FFFFF
 *	  0x00800000～0x00FFFFFF ⇒ 0x00FFFFFF
 *	  0x01000000～0x01FFFFFF ⇒ 0x01FFFFFF
 *	  0x02000000～0x03FFFFFF ⇒ 0x03FFFFFF
 *	  0x04000000～0x07FFFFFF ⇒ 0x07FFFFFF
 *	  0x08000000～0x0FFFFFFF ⇒ 0x0FFFFFFF
 *	  0x10000000～0x1FFFFFFF ⇒ 0x1FFFFFFF
 *	  0x20000000～0x3FFFFFFF ⇒ 0x3FFFFFFF
 *	  0x40000000～0x7FFFFFFF ⇒ 0x7FFFFFFF
 *	  0x80000000～0xFFFFFFFF ⇒ 0xFFFFFFFF
 */
unsigned minimum_mask_greater_than_or_equal_to(unsigned x);

#endif//__CLIP_RND_H__
