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 random_u32 (u32 * seed)
  69 {
  70   *seed = (1664525 * *seed) + 1013904223;
  71   return *seed;
  72 }
  73 /* External test routine. */
  74 int test_random_main (unformat_input_t * input);
  75
  76 /** \brief Maximum value returned by random_u32() */
  77 always_inline u32 random_u32_max (void)
  78 { return 0xffffffff; }
  79
  80 #ifdef CLIB_UNIX
  81
  82 #include <unistd.h>             /* for getpid */
  83
  84 /** \brief Default random seed (unix/linux user-mode) */
  85 always_inline uword random_default_seed (void)
  86 { return getpid (); }
  87
  88 #endif
  89
  90 #ifdef CLIB_LINUX_KERNEL
  91
  92 #include <linux/sched.h>        /* for jiffies */
  93
  94 /** \brief Default random seed (Linux kernel) */
  95 always_inline uword random_default_seed (void)
  96 { return jiffies; }
  97
  98 #endif
  99
 100 #ifdef CLIB_STANDALONE
 101 extern u32 standalone_random_default_seed;
 102
 103 always_inline u32 random_default_seed (void)
 104 { return standalone_random_default_seed; }
 105 #endif
 106
 107 /** \brief 64-bit random number generator
 108
 109     created via two calls to random_u32(). Quick and dirty.
 110 */
 111 always_inline u64
 112 random_u64 (u32 * seed)
 113 {
 114   u64 result;
 115
 116   result = (u64) random_u32 (seed) << 32;
 117   result |= random_u32 (seed);
 118   return result;
 119 }
 120
 121 /** \brief machine word size random number generator */
 122
 123 always_inline uword
 124 random_uword (u32 * seed)
 125 {
 126   if (sizeof (uword) == sizeof (u64))
 127     return random_u64 (seed);
 128   else
 129     return random_u32 (seed);
 130 }
 131
 132 /** \brief Generate f64 random number in the interval [0,1] */
 133 always_inline f64 random_f64 (u32 * seed)
 134 { return (f64) random_u32 (seed) / (f64) random_u32_max (); }
 135
 136 /** \brief Generate random character vector
 137
 138     From the alphabet a-z, lower case.
 139     Returns a vector of the supplied length which is NOT guaranteed to be
 140     NULL-terminated. FIXME?
 141 */
 142 always_inline u8 *
 143 random_string (u32 * seed, uword len)
 144 {
 145   u8 * alphabet = (u8 *) "abcdefghijklmnopqrstuvwxyz";
 146   u8 * s = 0;
 147   word i;
 148
 149   vec_resize (s, len);
 150   for (i = 0; i < len; i++)
 151     s[i] = alphabet[random_u32 (seed) % 26];
 152
 153   return s;
 154 }
 155
 156 #endif /* included_random_h */