尽管ISO C99使用了非常简单的并且具备移植性的样例描述了rand函数和srand函数的实现。但是在具体的C语言函数库的实现上,由于考虑到运行效率以及线程安全,代码就稍微多了一些。
这里以glibc 2.18为例。
在stdlib目录下,我们找到rand.c,内容如下:
1 /* Return a random integer between 0 and RAND_MAX. */2 int3 rand (void)4 {5 return (int) __random ();6 }
在同目录下的random.c,我们找到__random函数,内容如下:
1 long int 2 __random (void) 3 { 4 int32_t retval; 5 6 __libc_lock_lock (lock); 7 8 (void) __random_r (&unsafe_state, &retval); 9 10 __libc_lock_unlock (lock);11 12 return retval;13 }
这个函数调用__random_r函数,传入两个参数&unsafe_state和&retval,返回retval。所以我们可以确定retval是即将生成的伪随机数,而unsafe_state是什么呢?
在random.c中,我们找到unsafe_state的定义:
1 static struct random_data unsafe_state = 2 { 3 .fptr = &randtbl[SEP_3 + 1], 4 .rptr = &randtbl[1], 5 6 .state = &randtbl[1], 7 8 .rand_type = TYPE_3, 9 .rand_deg = DEG_3,10 .rand_sep = SEP_3,11 12 .end_ptr = &randtbl[sizeof (randtbl) / sizeof (randtbl[0])]13 };
unsafe_state是一个全局的静态变量,类型为random_data的结构体。我们查看stdlib.h,找到struct random_data的定义,发现它其实就是我们一直所说的伪随机数发生器的“种子”,在glibc的实现中,由于在多线程的情况下,如果函数使用一个静态变量,则这个函数不具备有“可重入”性,就是在多线程调用的情况下会发生意想不到的情形。所以glibc对这种情况作出了修正,保证了rand函数的“可重入性”。首先我们来看random_data的定义:
1 /* Reentrant versions of the `random' family of functions. 2 These functions all use the following data structure to contain 3 state, rather than global state variables. */ 4 5 struct random_data 6 { 7 int32_t *fptr; /* Front pointer. */ 8 int32_t *rptr; /* Rear pointer. */ 9 int32_t *state; /* Array of state values. */10 int rand_type; /* Type of random number generator. */11 int rand_deg; /* Degree of random number generator. */12 int rand_sep; /* Distance between front and rear. */13 int32_t *end_ptr; /* Pointer behind state table. */14 };
那么glibc是如何保证函数的可重入性的呢?其实就是__random函数中的两行代码__libc_lock_lock (lock)和__libc_lock_unlock (lock),这个lock保证了线程在访问&unsafe_state资源的互斥性,从而保证了函数的可重入性。那么这个lock的机制是从何而来的呢?在random.c文件中我们可以读到lock的初始化语句:
1 /* POSIX.1c requires that there is mutual exclusion for the `rand' and2 `srand' functions to prevent concurrent calls from modifying common3 data. */4 __libc_lock_define_initialized (static, lock)
初始化锁(__libc_lock_define_initialized)、加锁(__libc_lock_lock)、解锁(__libc_lock_unlock)的操作属于宏,我们可以在bits目录下的libc-lock.h中找到宏的定义(这里说明一下,在我下载的glic源码中的该文件是stub version,缺少具体的定义,仅有宏名称。我在unbuntu12.04上找到了相应的bits目录下的libc-lock.h,属于NPTL version,有宏的定义):
1 typedef pthread_mutex_t __libc_lock_t; 2 3 # define __libc_lock_define_initialized(CLASS,NAME) \ 4 CLASS __libc_lock_t NAME; 5 6 # define __libc_lock_lock(NAME) \ 7 ({ lll_lock (NAME, LLL_PRIVATE); 0; }) 8 9 # define __libc_lock_unlock(NAME) \10 lll_unlock (NAME, LLL_PRIVATE)
而lll_lock和lll_unlock属于底层的对互斥锁进行操作的宏,这里不深究。
在保证了函数的“可重入性”之后,rand函数调用链条上的最后一环就是__random_r这个函数(在random_r.c中),它真正进行对unsafe_state和retval的操作,产生一个伪随机数,并且对“种子”进行更新。
1 int 2 __random_r (buf, result) 3 struct random_data *buf; 4 int32_t *result; 5 { 6 int32_t *state; 7 8 if (buf == NULL || result == NULL) 9 goto fail;10 11 state = buf->state;12 13 if (buf->rand_type == TYPE_0)14 {15 int32_t val = state[0];16 val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;17 state[0] = val;18 *result = val;19 }20 else21 {22 int32_t *fptr = buf->fptr;23 int32_t *rptr = buf->rptr;24 int32_t *end_ptr = buf->end_ptr;25 int32_t val;26 27 val = *fptr += *rptr;28 /* Chucking least random bit. */29 *result = (val >> 1) & 0x7fffffff;30 ++fptr;31 if (fptr >= end_ptr)32 {33 fptr = state;34 ++rptr;35 }36 else37 {38 ++rptr;39 if (rptr >= end_ptr)40 rptr = state;41 }42 buf->fptr = fptr;43 buf->rptr = rptr;44 }45 return 0;46 47 fail:48 __set_errno (EINVAL);49 return -1;50 }
在看完了rand函数之后,让我们来看看srand函数。在目录中,我们找不到srand.c这样的文件,但是在random.c中,我们可以看到:
1 weak_alias (__srandom, srandom)
1 weak_alias (__srandom, srand)
这两行代码的意思就是为__srandom这个符号设置一个弱符号的别名。什么是弱符号,这里不深究。大致的意思就是如果你在其他的文件中定义了srand函数和srandom函数,你可以放心使用你定义的函数,而不必担心被这里的弱符号别名所影响。weak_alias的定义在libc-symbols.h当中:
1 /* Define ALIASNAME as a weak alias for NAME.2 If weak aliases are not available, this defines a strong alias. */3 # define weak_alias(name, aliasname) _weak_alias (name, aliasname)4 # define _weak_alias(name, aliasname) \5 extern __typeof (name) aliasname __attribute__ ((weak, alias (#name)));
所以要看srand函数,就看__srandom函数,这个函数接收一个x,在编程当中我们调用srand((unsigned int)time(NULL)),所以x就是当前的时间距离1970年1月1日0时的秒数。函数如下:
1 void2 __srandom (x)3 unsigned int x;4 {5 __libc_lock_lock (lock);6 (void) __srandom_r (x, &unsafe_state);7 __libc_lock_unlock (lock);8 }
我们在random_r.c中找到__srandom_r函数,这个函数根据传入的x来改变全局静态变量unsafe_state的状态,就是改变了“种子”,所以能够使伪随机数发生器根据这个“种子”来产生伪随机数序列。函数的实现如下:
1 int 2 __srandom_r (seed, buf) 3 unsigned int seed; 4 struct random_data *buf; 5 { 6 int type; 7 int32_t *state; 8 long int i; 9 int32_t word;10 int32_t *dst;11 int kc;12 13 if (buf == NULL)14 goto fail;15 type = buf->rand_type;16 if ((unsigned int) type >= MAX_TYPES)17 goto fail;18 19 state = buf->state;20 /* We must make sure the seed is not 0. Take arbitrarily 1 in this case. */21 if (seed == 0)22 seed = 1;23 state[0] = seed;24 if (type == TYPE_0)25 goto done;26 27 dst = state;28 word = seed;29 kc = buf->rand_deg;30 for (i = 1; i < kc; ++i)31 {32 /* This does:33 state[i] = (16807 * state[i - 1]) % 2147483647;34 but avoids overflowing 31 bits. */35 long int hi = word / 127773;36 long int lo = word % 127773;37 word = 16807 * lo - 2836 * hi;38 if (word < 0)39 word += 2147483647;40 *++dst = word;41 }42 43 buf->fptr = &state[buf->rand_sep];44 buf->rptr = &state[0];45 kc *= 10;46 while (--kc >= 0)47 {48 int32_t discard;49 (void) __random_r (buf, &discard);50 }51 52 done:53 return 0;54 55 fail:56 return -1;57 }
至此,我们应该可以说自己对glibc中rand函数和srand函数的实现有了初步的认识。