rand函數(shù)
函數(shù)說明：
rand()會返回一隨機(jī)數(shù)值誓篱，范圍在0至RAND_MAX 間朋贬。在調(diào)用此函數(shù)產(chǎn)生隨機(jī)數(shù)前，必須先利用srand()設(shè)好隨機(jī)數(shù)種子窜骄，如果未設(shè)隨機(jī)數(shù)種子锦募，rand()在調(diào)用時會自動設(shè)隨機(jī)數(shù)種子為1，關(guān)于隨機(jī)數(shù)種子請參考srand()
返回值：
返回0至RAND_MAX之間的隨機(jī)數(shù)值邻遏，RAND_MAX定義在stdlib.h糠亩，其值為2147483647
srand函數(shù)
函數(shù)說明：
srand()用來設(shè)置rand()產(chǎn)生隨機(jī)數(shù)時的隨機(jī)數(shù)種子。參數(shù)seed必須是個整數(shù)准验，通呈晗撸可以利用geypid()或time(0)的返回值來當(dāng)做seed。如果每次seed都設(shè)相同值沟娱，rand()所產(chǎn)生的隨機(jī)數(shù)值每次就會一樣氛驮。
Linux隨機(jī)數(shù)分析
最一般的隨機(jī)數(shù)過程，即srand->rand的過程济似，目的是根據(jù)獲得的隨機(jī)數(shù)逆向出種子
unsafe_state：
146 static int32_t randtbl[DEG_3 + 1] =
147 {
148 TYPE_3,
149
150 -1726662223, 379960547, 1735697613, 1040273694, 1313901226,
151 1627687941, -179304937, -2073333483, 1780058412, -1989503057,
152 -615974602, 344556628, 939512070, -1249116260, 1507946756,
153 -812545463, 154635395, 1388815473, -1926676823, 525320961,
154 -1009028674, 968117788, -123449607, 1284210865, 435012392,
155 -2017506339, -911064859, -370259173, 1132637927, 1398500161,
156 -205601318,
157 };
160 static struct random_data unsafe_state =
161 {
162 /* FPTR and RPTR are two pointers into the state info, a front and a rear
163 pointer. These two pointers are always rand_sep places apart, as they
164 cycle through the state information. (Yes, this does mean we could get
165 away with just one pointer, but the code for random is more efficient
166 this way). The pointers are left positioned as they would be from the call:
167 initstate(1, randtbl, 128);
168 (The position of the rear pointer, rptr, is really 0 (as explained above
169 in the initialization of randtbl) because the state table pointer is set
170 to point to randtbl[1] (as explained below).) */
171
172 .fptr = &randtbl[SEP_3 + 1], // 前指針
173 .rptr = &randtbl[1], // 后指針
174
175 /* The following things are the pointer to the state information table,
176 the type of the current generator, the degree of the current polynomial
177 being used, and the separation between the two pointers.
178 Note that for efficiency of random, we remember the first location of
179 the state information, not the zeroth. Hence it is valid to access
180 state[-1], which is used to store the type of the R.N.G.
181 Also, we remember the last location, since this is more efficient than
182 indexing every time to find the address of the last element to see if
183 the front and rear pointers have wrapped. */
184
185 .state = &randtbl[1], // randtbl為基礎(chǔ)的表矫废，state會在srand設(shè)置種子后對這個表進(jìn)行轉(zhuǎn)換，并將生成的隨機(jī)數(shù)循環(huán)存在這里
186
187 .rand_type = TYPE_3, // 3
188 .rand_deg = DEG_3, // state的大小為31砰蠢，因?yàn)閟tate是從randtbl[1]開始算起蓖扑，randtbl[0]始終為TYPE_3
189 .rand_sep = SEP_3, // 3
190
191 .end_ptr = &randtbl[sizeof (randtbl) / sizeof (randtbl[0])] // randtbl終結(jié)的位置
192 };
srand函數(shù)：
srand的具體實(shí)現(xiàn)就是__srandom_r，其中參數(shù) seed為種子台舱，buf就是上面的unsafe_state律杠。
這里主要是以seed為基礎(chǔ)，記為state[0]竞惋，實(shí)現(xiàn)state[i] = (16807 * state[i - 1]) % 2147483647柜去。
161 __srandom_r (unsigned int seed, struct random_data *buf)
162 {
163 int type;
164 int32_t *state;
165 long int i;
166 int32_t word;
167 int32_t *dst;
168 int kc;
169
170 if (buf == NULL)
171 goto fail;
172 type = buf->rand_type; // type默認(rèn)為3
173 if ((unsigned int) type >= MAX_TYPES)
174 goto fail;
175
176 state = buf->state; // state默認(rèn)從randtbl[1]開始
177 /* We must make sure the seed is not 0. Take arbitrarily 1 in this case. */
178 if (seed == 0) // seed為0也改為1
179 seed = 1;
180 state[0] = seed; // state[0]設(shè)置為seed，默認(rèn)是TYPE_3
181 if (type == TYPE_0)
182 goto done;
183 // 從state[1]開始拆宛，實(shí)現(xiàn)state[i] = (16807 * state[i - 1]) % 2147483647
184 dst = state; // dst表示state[i]
185 word = seed; // word表示state[i-1]
186 kc = buf->rand_deg; // kc=31嗓奢，表示table的大小
187 for (i = 1; i < kc; ++i) //一共30個
188 {
189 /* This does:
190 state[i] = (16807 * state[i - 1]) % 2147483647;
191 but avoids overflowing 31 bits. */
192 long int hi = word / 127773;
193 long int lo = word % 127773;
194 word = 16807 * lo - 2836 * hi;
195 if (word < 0)
196 word += 2147483647;
197 *++dst = word;
198 }
199
200 buf->fptr = &state[buf->rand_sep]; // fptr從state[3]開始
201 buf->rptr = &state[0]; // rptr從state[0]開始
202 kc *= 10; // 310
203 while (--kc >= 0) // 通過__random_r生成310個隨機(jī)數(shù)
204 {
205 int32_t discard;
206 (void) __random_r (buf, &discard);
207 }
208
209 done:
210 return 0;
211
212 fail:
213 return -1;
214 }
rand函數(shù)：
rand的具體實(shí)現(xiàn)就是__random_r，參數(shù)buf依然是上面的unsafe_state浑厚，result就是我們返回的隨機(jī)數(shù)股耽。
352 int
353 __random_r (struct random_data *buf, int32_t *result)
354 {
355 int32_t *state;
356
357 if (buf == NULL || result == NULL)
358 goto fail;
359
360 state = buf->state;
361
362 if (buf->rand_type == TYPE_0)
363 {
364 int32_t val = state[0];
365 val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
366 state[0] = val;
367 *result = val;
368 }
369 else // 一般type=3根盒，所以走下面這一段
370 {
371 int32_t *fptr = buf->fptr;
372 int32_t *rptr = buf->rptr;
373 int32_t *end_ptr = buf->end_ptr;
374 int32_t val;
375
376 val = *fptr += *rptr;
377 /* Chucking least random bit. */
378 *result = (val >> 1) & 0x7fffffff;
379 ++fptr;
380 if (fptr >= end_ptr)
381 {
382 fptr = state;
383 ++rptr;
384 }
385 else
386 {
387 ++rptr;
388 if (rptr >= end_ptr)
389 rptr = state;
390 }
391 buf->fptr = fptr;
392 buf->rptr = rptr;
393 }
394 return 0;
395
396 fail:
397 __set_errno (EINVAL);
398 return -1;
399 }
偽代碼：
通過上面的分析，已經(jīng)可以根據(jù)跟定的seed獲得隨機(jī)數(shù)物蝙，以及對應(yīng)的state了：
#include <stdio.h>
#define MAX 1000
#define seed 1
#int main() {
int r[MAX],i,j;
int state[31];
state[0] = seed;
for (i=1; i<31; i++){
state[i] = (16807LL * state[i-1]) % 2147483647;
if (state[i] < 0) {
state[i] += 2147483647;
}
}
for (i=31; i<341;i++){
state[(i+3)%31] = (state[(i+3)%31]+state[i%31]);
}
for (i=341;i<MAX;i++){
state[(i+3)%31] = (state[(i+3)%31]+state[i%31]);
r[i-340] = (state[(i+3)%31]>>1)&0x7fffffff;
printf("%d : %x\n",i-340,r[i-340]);
}
return 0;
}
代碼簡化：
#include <stdio.h>
#define MAX 1000
#define seed 1
int main() {
int r[MAX],i;
r[0] = seed;
for (i=1; i<31; i++){
r[i] = (16807LL * r[i-1])%0x7fffffff;
if (r[i] < 0) {
r[i] += 0x7fffffff;
}
}
for (i=31; i<34; i++){
r[i] = r[i-31];
}
for (i=34; i<344;i++){
r[i] = r[i-31] + r[i-3];
}
for (i=344;i<350;i++){
r[i] = r[i-31] + r[i-3];
printf("%d %#x\n", i-343, (r[i]>>1)&0x7fffffff);
}
return 0;
}
預(yù)測：
可以看到上面存在&0x7fffffff炎滞，并且還存在除以2，所以要能成功預(yù)測的情況是r[i-31]和r[i-3]都沒有&0x7fffffff诬乞，這樣就是r[i] = ((r[i-31]<<1)+(r[i-3]<<1))
對應(yīng)的隨機(jī)數(shù)還是(r[i]>>1)&0x7fffffff)册赛，但是實(shí)際上還能更簡單，由于我們獲得的是隨機(jī)數(shù)丽惭，那么就是這樣的：
rand[i] = (r[i]>>1)&0x7fffffff
r[i] = ((r[i-31]<<1)+(r[i-3]<<1))
rand[i-3] = (r[i-3]>>1)&0x7fffffff
rand[i-31] = (r[i-31]>>1)&0x7fffffff
綜上：
rand[i] = (((r[i-31]<<1)+(r[i-3]<<1))>>1)&0x7fffffff 推出
rand[i] = (rand[i-3]+rand[i-31])&0x7fffffff
但是由于存在除以2的原因击奶，所以可能會存在1的誤差
