lustre/lvfs/prng.c

   1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
   2  * vim:expandtab:shiftwidth=8:tabstop=8:
   3  *
   4  *   This file is part of the Lustre file system, http://www.lustre.org
   5  *   Lustre is a trademark of Cluster File Systems, Inc.
   6  *
   7  * concatenation of following two 16-bit multiply with carry generators
   8  * x(n)=a*x(n-1)+carry mod 2^16 and y(n)=b*y(n-1)+carry mod 2^16,
   9  * number and carry packed within the same 32 bit integer.
  10  * algorithm recommended by Marsaglia
  11  ******************************************************************/
  12 #ifndef EXPORT_SYMTAB
  13 # define EXPORT_SYMTAB
  14 #endif
  15
  16 #ifndef __KERNEL__
  17 #include <liblustre.h>
  18 #define get_random_bytes(val, size)     (*val) = 0
  19 #endif
  20 #include <obd_class.h>
  21 #if defined(HAVE_LINUX_RANDOM_H)
  22 #include <linux/random.h>
  23 #endif
  24
  25 /*
  26 From: George Marsaglia <geo@stat.fsu.edu>
  27 Newsgroups: sci.math
  28 Subject: Re: A RANDOM NUMBER GENERATOR FOR C
  29 Date: Tue, 30 Sep 1997 05:29:35 -0700
  30
  31  * You may replace the two constants 36969 and 18000 by any
  32  * pair of distinct constants from this list:
  33  * 18000 18030 18273 18513 18879 19074 19098 19164 19215 19584
  34  * 19599 19950 20088 20508 20544 20664 20814 20970 21153 21243
  35  * 21423 21723 21954 22125 22188 22293 22860 22938 22965 22974
  36  * 23109 23124 23163 23208 23508 23520 23553 23658 23865 24114
  37  * 24219 24660 24699 24864 24948 25023 25308 25443 26004 26088
  38  * 26154 26550 26679 26838 27183 27258 27753 27795 27810 27834
  39  * 27960 28320 28380 28689 28710 28794 28854 28959 28980 29013
  40  * 29379 29889 30135 30345 30459 30714 30903 30963 31059 31083
  41  * (or any other 16-bit constants k for which both k*2^16-1
  42  * and k*2^15-1 are prime) */
  43
  44 #define RANDOM_CONST_A 18030
  45 #define RANDOM_CONST_B 29013
  46
  47 static unsigned int seed_x = 521288629;
  48 static unsigned int seed_y = 362436069;
  49 unsigned int ll_rand(void)
  50 {
  51
  52         seed_x = RANDOM_CONST_A * (seed_x & 65535) + (seed_x >> 16);
  53         seed_y = RANDOM_CONST_B * (seed_y & 65535) + (seed_y >> 16);
  54
  55         return ((seed_x << 16) + (seed_y & 65535));
  56 }
  57 EXPORT_SYMBOL(ll_rand);
  58
  59 /* Note that if the input seeds are not completely random, then there is
  60  * a preferred location for the entropy in the two seeds, in order to avoid
  61  * the initial values from the PRNG to be the same each time.
  62  *
  63  * seed1 (seed_x) should have the most entropy in the low bits of the word
  64  * seed2 (seed_y) should have the most entropy in the high bits of the word */
  65 void ll_srand(unsigned int seed1, unsigned int seed2)
  66 {
  67         if (seed1)
  68                 seed_x = seed1; /* use default seeds if parameter is 0 */
  69         if (seed2)
  70                 seed_y = seed2;
  71 }
  72 EXPORT_SYMBOL(ll_srand);
  73
  74 void ll_get_random_bytes(void *buf, int size)
  75 {
  76         int *p = buf;
  77         int rem, tmp;
  78
  79         LASSERT(size >= 0);
  80
  81         rem = min((int)((unsigned long)buf & (sizeof(int) - 1)), size);
  82         if (rem) {
  83                 get_random_bytes(&tmp, sizeof(tmp));
  84                 tmp ^= ll_rand();
  85                 memcpy(buf, &tmp, rem);
  86                 p = buf + rem;
  87                 size -= rem;
  88         }
  89
  90         while (size >= sizeof(int)) {
  91                 get_random_bytes(&tmp, sizeof(tmp));
  92                 *p = ll_rand() ^ tmp;
  93                 size -= sizeof(int);
  94                 p++;
  95         }
  96         buf = p;
  97         if (size) {
  98                 get_random_bytes(&tmp, sizeof(tmp));
  99                 tmp ^= ll_rand();
 100                 memcpy(buf, &tmp, size);
 101         }
 102 }
 103 EXPORT_SYMBOL(ll_get_random_bytes);
 104
 105 void ll_generate_random_uuid(class_uuid_t uuid_out)
 106 {
 107         ll_get_random_bytes(uuid_out, sizeof(class_uuid_t));
 108 }
 109 EXPORT_SYMBOL(ll_generate_random_uuid);
 110