vppinfra/vppinfra/random.h

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16   Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
  17
  18   Permission is hereby granted, free of charge, to any person obtaining
  19   a copy of this software and associated documentation files (the
  20   "Software"), to deal in the Software without restriction, including
  21   without limitation the rights to use, copy, modify, merge, publish,
  22   distribute, sublicense, and/or sell copies of the Software, and to
  23   permit persons to whom the Software is furnished to do so, subject to
  24   the following conditions:
  25
  26   The above copyright notice and this permission notice shall be
  27   included in all copies or substantial portions of the Software.
  28
  29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  36 */
  37
  38 #ifndef included_random_h
  39 #define included_random_h
  40
  41 #include <vppinfra/clib.h>
  42 #include <vppinfra/vec.h>       /* for vec_resize */
  43 #include <vppinfra/format.h>    /* for unformat_input_t */
  44
  45 /** \file
  46     Linear Congruential Random Number Generator
  47
  48     This specific random number generator is described in
  49     "Numerical Recipes in C", 2nd edition, page 284. If you need
  50     random numbers with really excellent statistics, take a look
  51     at Chapter 7...
  52
  53     By definition, a linear congruential random number generator
  54     is of the form: rand[i+1] = a*rand[i] + c (mod m) for specific
  55     values of (a,c,m).
  56
  57     In this case, choose m = 2**32 and use the low-order 32-bits of
  58     the 64-bit product a*N[i]. Knuth suggests the use of a=1664525,
  59     H.W. Lewis has tested C=1013904223 extensively. This routine is
  60     reputedly as good as any 32-bit LCRN, and costs only a single
  61     multiply-add.
  62
  63     Several variants: 32/64-bit, machine word width,
  64     f64 on the closed interval [0,1].
  65 */
  66
  67 /** \brief 32-bit random number generator */
  68 always_inline u32
  69 random_u32 (u32 * seed)
  70 {
  71   *seed = (1664525 * *seed) + 1013904223;
  72   return *seed;
  73 }
  74
  75 /* External test routine. */
  76 int test_random_main (unformat_input_t * input);
  77
  78 /** \brief Maximum value returned by random_u32() */
  79 always_inline u32
  80 random_u32_max (void)
  81 {
  82   return 0xffffffff;
  83 }
  84
  85 #ifdef CLIB_UNIX
  86
  87 #include <unistd.h>             /* for getpid */
  88
  89 /** \brief Default random seed (unix/linux user-mode) */
  90 always_inline uword
  91 random_default_seed (void)
  92 {
  93   return getpid ();
  94 }
  95
  96 #endif
  97
  98 #ifdef CLIB_LINUX_KERNEL
  99
 100 #include <linux/sched.h>        /* for jiffies */
 101
 102 /** \brief Default random seed (Linux kernel) */
 103 always_inline uword
 104 random_default_seed (void)
 105 {
 106   return jiffies;
 107 }
 108
 109 #endif
 110
 111 #ifdef CLIB_STANDALONE
 112 extern u32 standalone_random_default_seed;
 113
 114 always_inline u32
 115 random_default_seed (void)
 116 {
 117   return standalone_random_default_seed;
 118 }
 119 #endif
 120
 121 /** \brief 64-bit random number generator
 122
 123     created via two calls to random_u32(). Quick and dirty.
 124 */
 125 always_inline u64
 126 random_u64 (u32 * seed)
 127 {
 128   u64 result;
 129
 130   result = (u64) random_u32 (seed) << 32;
 131   result |= random_u32 (seed);
 132   return result;
 133 }
 134
 135 /** \brief machine word size random number generator */
 136
 137 always_inline uword
 138 random_uword (u32 * seed)
 139 {
 140   if (sizeof (uword) == sizeof (u64))
 141     return random_u64 (seed);
 142   else
 143     return random_u32 (seed);
 144 }
 145
 146 /** \brief Generate f64 random number in the interval [0,1] */
 147 always_inline f64
 148 random_f64 (u32 * seed)
 149 {
 150   return (f64) random_u32 (seed) / (f64) random_u32_max ();
 151 }
 152
 153 /** \brief Generate random character vector
 154
 155     From the alphabet a-z, lower case.
 156     Returns a vector of the supplied length which is NOT guaranteed to be
 157     NULL-terminated. FIXME?
 158 */
 159 always_inline u8 *
 160 random_string (u32 * seed, uword len)
 161 {
 162   u8 *alphabet = (u8 *) "abcdefghijklmnopqrstuvwxyz";
 163   u8 *s = 0;
 164   word i;
 165
 166   vec_resize (s, len);
 167   for (i = 0; i < len; i++)
 168     s[i] = alphabet[random_u32 (seed) % 26];
 169
 170   return s;
 171 }
 172
 173 #endif /* included_random_h */
 174
 175 /*
 176  * fd.io coding-style-patch-verification: ON
 177  *
 178  * Local Variables:
 179  * eval: (c-set-style "gnu")
 180  * End:
 181  */