The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/lib/random32.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*
    2   This is a maximally equidistributed combined Tausworthe generator
    3   based on code from GNU Scientific Library 1.5 (30 Jun 2004)
    4 
    5    x_n = (s1_n ^ s2_n ^ s3_n)
    6 
    7    s1_{n+1} = (((s1_n & 4294967294) <<12) ^ (((s1_n <<13) ^ s1_n) >>19))
    8    s2_{n+1} = (((s2_n & 4294967288) << 4) ^ (((s2_n << 2) ^ s2_n) >>25))
    9    s3_{n+1} = (((s3_n & 4294967280) <<17) ^ (((s3_n << 3) ^ s3_n) >>11))
   10 
   11    The period of this generator is about 2^88.
   12 
   13    From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe
   14    Generators", Mathematics of Computation, 65, 213 (1996), 203--213.
   15 
   16    This is available on the net from L'Ecuyer's home page,
   17 
   18    http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
   19    ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps
   20 
   21    There is an erratum in the paper "Tables of Maximally
   22    Equidistributed Combined LFSR Generators", Mathematics of
   23    Computation, 68, 225 (1999), 261--269:
   24    http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
   25 
   26         ... the k_j most significant bits of z_j must be non-
   27         zero, for each j. (Note: this restriction also applies to the
   28         computer code given in [4], but was mistakenly not mentioned in
   29         that paper.)
   30 
   31    This affects the seeding procedure by imposing the requirement
   32    s1 > 1, s2 > 7, s3 > 15.
   33 
   34 */
   35 
   36 #include <linux/types.h>
   37 #include <linux/percpu.h>
   38 #include <linux/export.h>
   39 #include <linux/jiffies.h>
   40 #include <linux/random.h>
   41 
   42 static DEFINE_PER_CPU(struct rnd_state, net_rand_state);
   43 
   44 /**
   45  *      prandom_u32_state - seeded pseudo-random number generator.
   46  *      @state: pointer to state structure holding seeded state.
   47  *
   48  *      This is used for pseudo-randomness with no outside seeding.
   49  *      For more random results, use prandom_u32().
   50  */
   51 u32 prandom_u32_state(struct rnd_state *state)
   52 {
   53 #define TAUSWORTHE(s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b)
   54 
   55         state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12);
   56         state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4);
   57         state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17);
   58 
   59         return (state->s1 ^ state->s2 ^ state->s3);
   60 }
   61 EXPORT_SYMBOL(prandom_u32_state);
   62 
   63 /**
   64  *      prandom_u32 - pseudo random number generator
   65  *
   66  *      A 32 bit pseudo-random number is generated using a fast
   67  *      algorithm suitable for simulation. This algorithm is NOT
   68  *      considered safe for cryptographic use.
   69  */
   70 u32 prandom_u32(void)
   71 {
   72         unsigned long r;
   73         struct rnd_state *state = &get_cpu_var(net_rand_state);
   74         r = prandom_u32_state(state);
   75         put_cpu_var(state);
   76         return r;
   77 }
   78 EXPORT_SYMBOL(prandom_u32);
   79 
   80 /*
   81  *      prandom_bytes_state - get the requested number of pseudo-random bytes
   82  *
   83  *      @state: pointer to state structure holding seeded state.
   84  *      @buf: where to copy the pseudo-random bytes to
   85  *      @bytes: the requested number of bytes
   86  *
   87  *      This is used for pseudo-randomness with no outside seeding.
   88  *      For more random results, use prandom_bytes().
   89  */
   90 void prandom_bytes_state(struct rnd_state *state, void *buf, int bytes)
   91 {
   92         unsigned char *p = buf;
   93         int i;
   94 
   95         for (i = 0; i < round_down(bytes, sizeof(u32)); i += sizeof(u32)) {
   96                 u32 random = prandom_u32_state(state);
   97                 int j;
   98 
   99                 for (j = 0; j < sizeof(u32); j++) {
  100                         p[i + j] = random;
  101                         random >>= BITS_PER_BYTE;
  102                 }
  103         }
  104         if (i < bytes) {
  105                 u32 random = prandom_u32_state(state);
  106 
  107                 for (; i < bytes; i++) {
  108                         p[i] = random;
  109                         random >>= BITS_PER_BYTE;
  110                 }
  111         }
  112 }
  113 EXPORT_SYMBOL(prandom_bytes_state);
  114 
  115 /**
  116  *      prandom_bytes - get the requested number of pseudo-random bytes
  117  *      @buf: where to copy the pseudo-random bytes to
  118  *      @bytes: the requested number of bytes
  119  */
  120 void prandom_bytes(void *buf, int bytes)
  121 {
  122         struct rnd_state *state = &get_cpu_var(net_rand_state);
  123 
  124         prandom_bytes_state(state, buf, bytes);
  125         put_cpu_var(state);
  126 }
  127 EXPORT_SYMBOL(prandom_bytes);
  128 
  129 /**
  130  *      prandom_seed - add entropy to pseudo random number generator
  131  *      @seed: seed value
  132  *
  133  *      Add some additional seeding to the prandom pool.
  134  */
  135 void prandom_seed(u32 entropy)
  136 {
  137         int i;
  138         /*
  139          * No locking on the CPUs, but then somewhat random results are, well,
  140          * expected.
  141          */
  142         for_each_possible_cpu (i) {
  143                 struct rnd_state *state = &per_cpu(net_rand_state, i);
  144                 state->s1 = __seed(state->s1 ^ entropy, 1);
  145         }
  146 }
  147 EXPORT_SYMBOL(prandom_seed);
  148 
  149 /*
  150  *      Generate some initially weak seeding values to allow
  151  *      to start the prandom_u32() engine.
  152  */
  153 static int __init prandom_init(void)
  154 {
  155         int i;
  156 
  157         for_each_possible_cpu(i) {
  158                 struct rnd_state *state = &per_cpu(net_rand_state,i);
  159 
  160 #define LCG(x)  ((x) * 69069)   /* super-duper LCG */
  161                 state->s1 = __seed(LCG(i + jiffies), 1);
  162                 state->s2 = __seed(LCG(state->s1), 7);
  163                 state->s3 = __seed(LCG(state->s2), 15);
  164 
  165                 /* "warm it up" */
  166                 prandom_u32_state(state);
  167                 prandom_u32_state(state);
  168                 prandom_u32_state(state);
  169                 prandom_u32_state(state);
  170                 prandom_u32_state(state);
  171                 prandom_u32_state(state);
  172         }
  173         return 0;
  174 }
  175 core_initcall(prandom_init);
  176 
  177 /*
  178  *      Generate better values after random number generator
  179  *      is fully initialized.
  180  */
  181 static int __init prandom_reseed(void)
  182 {
  183         int i;
  184 
  185         for_each_possible_cpu(i) {
  186                 struct rnd_state *state = &per_cpu(net_rand_state,i);
  187                 u32 seeds[3];
  188 
  189                 get_random_bytes(&seeds, sizeof(seeds));
  190                 state->s1 = __seed(seeds[0], 1);
  191                 state->s2 = __seed(seeds[1], 7);
  192                 state->s3 = __seed(seeds[2], 15);
  193 
  194                 /* mix it in */
  195                 prandom_u32_state(state);
  196         }
  197         return 0;
  198 }
  199 late_initcall(prandom_reseed);

Cache object: c3578858d3be7faed150ccbe3a465fb5


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.