博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
浅析C语言中的rand函数和srand函数(二)
阅读量:6602 次
发布时间:2019-06-24

本文共 6127 字,大约阅读时间需要 20 分钟。

尽管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 }
__random_r函数的定义

 

在看完了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 }
__srandom_r函数的定义

 

 

至此,我们应该可以说自己对glibc中rand函数和srand函数的实现有了初步的认识。

 

转载于:https://www.cnblogs.com/nipan/p/4082351.html

你可能感兴趣的文章
【实战】烂泥:解决无法找到"txfile:platformres:msgmgr\msgmgr.htm"
查看>>
《图论》——图的存储与遍历(Java)
查看>>
一招一式攻克linux(三)
查看>>
IT运维管理——流程与表单定义
查看>>
WP下ListBox的绑定和效果
查看>>
Powershell管理系列(三十一)PowerShell操作之批量创建邮箱
查看>>
【REACT NATIVE 系列教程之十】真机运行报错COMMAND /BIN/SH FAILED WITH EXIT CODE 1 的解决方法...
查看>>
SEO外链算法独家揭秘
查看>>
[MySQL优化案例]系列 -- OPTIMIZE的威力
查看>>
Apache2 之虚拟主机设置指南
查看>>
Linux系统开机过程解释笔记
查看>>
js实现购物车数量的自增与自减
查看>>
沟通、务实、平等——读《Scrum and XP from the Trenches》
查看>>
Android java.lang.NoClassDefFoundError 的解决办法
查看>>
UIWebview与js交互[转]
查看>>
Windows Azure Cloud Service (26) Windows Azure 性能监视器
查看>>
swift:高级运算符(位运算符、溢出运算符、优先级和结合性、运算符重载函数)...
查看>>
用户空间缺页异常pte_handle_fault()分析--(上)【转】
查看>>
【转】UIView 的 autoresizingMask 属性
查看>>
HashMap常用方法
查看>>