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  * Again, constants courtesy of Donald Knuth.
 123  *
 124  */
 125 always_inline u64
 126 random_u64 (u64 * seed)
 127 {
 128   *seed = 6364136223846793005ULL * *seed + 1442695040888963407ULL;
 129   return *seed;
 130 }
 131
 132 /** \brief machine word size random number generator */
 133
 134 always_inline uword
 135 random_uword (u32 * seed)
 136 {
 137   if (sizeof (uword) == sizeof (u64))
 138     return random_u64 ((u64 *) seed);
 139   else
 140     return random_u32 (seed);
 141 }
 142
 143 /** \brief Generate f64 random number in the interval [0,1] */
 144 always_inline f64
 145 random_f64 (u32 * seed)
 146 {
 147   return (f64) random_u32 (seed) / (f64) random_u32_max ();
 148 }
 149
 150 /** \brief Generate random character vector
 151
 152     From the alphabet a-z, lower case.
 153     Returns a vector of the supplied length which is NOT guaranteed to be
 154     NULL-terminated. FIXME?
 155 */
 156 always_inline u8 *
 157 random_string (u32 * seed, uword len)
 158 {
 159   u8 *alphabet = (u8 *) "abcdefghijklmnopqrstuvwxyz";
 160   u8 *s = 0;
 161   word i;
 162
 163   vec_resize (s, len);
 164   for (i = 0; i < len; i++)
 165     s[i] = alphabet[random_u32 (seed) % 26];
 166
 167   return s;
 168 }
 169
 170 #endif /* included_random_h */
 171
 172 /*
 173  * fd.io coding-style-patch-verification: ON
 174  *
 175  * Local Variables:
 176  * eval: (c-set-style "gnu")
 177  * End:
 178  */