Line data Source code
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 63142 : random_u32 (u32 * seed)
70 : {
71 63142 : *seed = (1664525 * *seed) + 1013904223;
72 63142 : 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 1046 : random_u32_max (void)
81 : {
82 1046 : 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 1207 : random_default_seed (void)
92 : {
93 1207 : 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 376 : random_u64 (u64 * seed)
127 : {
128 376 : *seed = 6364136223846793005ULL * *seed + 1442695040888963407ULL;
129 376 : 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 1043 : random_f64 (u32 * seed)
146 : {
147 1043 : 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 : f64 clib_chisquare (u64 * values);
171 :
172 : #endif /* included_random_h */
173 :
174 : /*
175 : * fd.io coding-style-patch-verification: ON
176 : *
177 : * Local Variables:
178 : * eval: (c-set-style "gnu")
179 : * End:
180 : */
|
