1 /* Copyright (C) 1995-2021 Free Software Foundation, Inc. 2 3 This file is free software: you can redistribute it and/or modify 4 it under the terms of the GNU Lesser General Public License as 5 published by the Free Software Foundation; either version 3 of the 6 License, or (at your option) any later version. 7 8 This file is distributed in the hope that it will be useful, 9 but WITHOUT ANY WARRANTY; without even the implied warranty of 10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 GNU Lesser General Public License for more details. 12 13 You should have received a copy of the GNU Lesser General Public License 14 along with this program. If not, see <https://www.gnu.org/licenses/>. */ 15 16 /* 17 * This is derived from the Berkeley source: 18 * @(#)random.c 5.5 (Berkeley) 7/6/88 19 * It was reworked for the GNU C Library by Roland McGrath. 20 * Rewritten to use reentrant functions by Ulrich Drepper, 1995. 21 */ 22 23 /* 24 Copyright (C) 1983 Regents of the University of California. 25 All rights reserved. 26 27 Redistribution and use in source and binary forms, with or without 28 modification, are permitted provided that the following conditions 29 are met: 30 31 1. Redistributions of source code must retain the above copyright 32 notice, this list of conditions and the following disclaimer. 33 2. Redistributions in binary form must reproduce the above copyright 34 notice, this list of conditions and the following disclaimer in the 35 documentation and/or other materials provided with the distribution. 36 4. Neither the name of the University nor the names of its contributors 37 may be used to endorse or promote products derived from this software 38 without specific prior written permission. 39 40 THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS" AND 41 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 44 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46 OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49 OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50 SUCH DAMAGE.*/ 51 52 #ifndef _LIBC 53 # include <libc-config.h> 54 # define __srandom srandom 55 # define __initstate initstate 56 # define __setstate setstate 57 # define __random random 58 # define __srandom_r srandom_r 59 # define __initstate_r initstate_r 60 # define __setstate_r setstate_r 61 # define __random_r random_r 62 #endif 63 64 /* Specification. */ 65 #include <stdlib.h> 66 67 #ifdef _LIBC 68 # include <libc-lock.h> 69 #else 70 /* Allow memory races; that's random enough. */ 71 # define __libc_lock_define_initialized(class, name) 72 # define __libc_lock_lock(name) ((void) 0) 73 # define __libc_lock_unlock(name) ((void) 0) 74 #endif 75 76 /* An improved random number generation package. In addition to the standard 77 rand()/srand() like interface, this package also has a special state info 78 interface. The initstate() routine is called with a seed, an array of 79 bytes, and a count of how many bytes are being passed in; this array is 80 then initialized to contain information for random number generation with 81 that much state information. Good sizes for the amount of state 82 information are 32, 64, 128, and 256 bytes. The state can be switched by 83 calling the setstate() function with the same array as was initialized 84 with initstate(). By default, the package runs with 128 bytes of state 85 information and generates far better random numbers than a linear 86 congruential generator. If the amount of state information is less than 87 32 bytes, a simple linear congruential R.N.G. is used. Internally, the 88 state information is treated as an array of longs; the zeroth element of 89 the array is the type of R.N.G. being used (small integer); the remainder 90 of the array is the state information for the R.N.G. Thus, 32 bytes of 91 state information will give 7 longs worth of state information, which will 92 allow a degree seven polynomial. (Note: The zeroth word of state 93 information also has some other information stored in it; see setstate 94 for details). The random number generation technique is a linear feedback 95 shift register approach, employing trinomials (since there are fewer terms 96 to sum up that way). In this approach, the least significant bit of all 97 the numbers in the state table will act as a linear feedback shift register, 98 and will have period 2^deg - 1 (where deg is the degree of the polynomial 99 being used, assuming that the polynomial is irreducible and primitive). 100 The higher order bits will have longer periods, since their values are 101 also influenced by pseudo-random carries out of the lower bits. The 102 total period of the generator is approximately deg*(2**deg - 1); thus 103 doubling the amount of state information has a vast influence on the 104 period of the generator. Note: The deg*(2**deg - 1) is an approximation 105 only good for large deg, when the period of the shift register is the 106 dominant factor. With deg equal to seven, the period is actually much 107 longer than the 7*(2**7 - 1) predicted by this formula. */ 108 109 110 111 /* For each of the currently supported random number generators, we have a 112 break value on the amount of state information (you need at least this many 113 bytes of state info to support this random number generator), a degree for 114 the polynomial (actually a trinomial) that the R.N.G. is based on, and 115 separation between the two lower order coefficients of the trinomial. */ 116 117 /* Linear congruential. */ 118 #define TYPE_0 0 119 #define BREAK_0 8 120 #define DEG_0 0 121 #define SEP_0 0 122 123 /* x**7 + x**3 + 1. */ 124 #define TYPE_1 1 125 #define BREAK_1 32 126 #define DEG_1 7 127 #define SEP_1 3 128 129 /* x**15 + x + 1. */ 130 #define TYPE_2 2 131 #define BREAK_2 64 132 #define DEG_2 15 133 #define SEP_2 1 134 135 /* x**31 + x**3 + 1. */ 136 #define TYPE_3 3 137 #define BREAK_3 128 138 #define DEG_3 31 139 #define SEP_3 3 140 141 /* x**63 + x + 1. */ 142 #define TYPE_4 4 143 #define BREAK_4 256 144 #define DEG_4 63 145 #define SEP_4 1 146 147 148 /* Array versions of the above information to make code run faster. 149 Relies on fact that TYPE_i == i. */ 150 151 #define MAX_TYPES 5 /* Max number of types above. */ 152 153 154 /* Initially, everything is set up as if from: 155 initstate(1, randtbl, 128); 156 Note that this initialization takes advantage of the fact that srandom 157 advances the front and rear pointers 10*rand_deg times, and hence the 158 rear pointer which starts at 0 will also end up at zero; thus the zeroth 159 element of the state information, which contains info about the current 160 position of the rear pointer is just 161 (MAX_TYPES * (rptr - state)) + TYPE_3 == TYPE_3. */ 162 163 static int32_t randtbl[DEG_3 + 1] = 164 { 165 TYPE_3, 166 167 -1726662223, 379960547, 1735697613, 1040273694, 1313901226, 168 1627687941, -179304937, -2073333483, 1780058412, -1989503057, 169 -615974602, 344556628, 939512070, -1249116260, 1507946756, 170 -812545463, 154635395, 1388815473, -1926676823, 525320961, 171 -1009028674, 968117788, -123449607, 1284210865, 435012392, 172 -2017506339, -911064859, -370259173, 1132637927, 1398500161, 173 -205601318, 174 }; 175 176 177 static struct random_data unsafe_state = 178 { 179 /* FPTR and RPTR are two pointers into the state info, a front and a rear 180 pointer. These two pointers are always rand_sep places apart, as they 181 cycle through the state information. (Yes, this does mean we could get 182 away with just one pointer, but the code for random is more efficient 183 this way). The pointers are left positioned as they would be from the call: 184 initstate(1, randtbl, 128); 185 (The position of the rear pointer, rptr, is really 0 (as explained above 186 in the initialization of randtbl) because the state table pointer is set 187 to point to randtbl[1] (as explained below).) */ 188 189 .fptr = &randtbl[SEP_3 + 1], 190 .rptr = &randtbl[1], 191 192 /* The following things are the pointer to the state information table, 193 the type of the current generator, the degree of the current polynomial 194 being used, and the separation between the two pointers. 195 Note that for efficiency of random, we remember the first location of 196 the state information, not the zeroth. Hence it is valid to access 197 state[-1], which is used to store the type of the R.N.G. 198 Also, we remember the last location, since this is more efficient than 199 indexing every time to find the address of the last element to see if 200 the front and rear pointers have wrapped. */ 201 202 .state = &randtbl[1], 203 204 .rand_type = TYPE_3, 205 .rand_deg = DEG_3, 206 .rand_sep = SEP_3, 207 208 .end_ptr = &randtbl[sizeof (randtbl) / sizeof (randtbl[0])] 209 }; 210 211 /* POSIX.1c requires that there is mutual exclusion for the 'rand' and 212 'srand' functions to prevent concurrent calls from modifying common 213 data. */ 214 __libc_lock_define_initialized (static, lock) /* */ 215 216 /* Initialize the random number generator based on the given seed. If the 217 type is the trivial no-state-information type, just remember the seed. 218 Otherwise, initializes state[] based on the given "seed" via a linear 219 congruential generator. Then, the pointers are set to known locations 220 that are exactly rand_sep places apart. Lastly, it cycles the state 221 information a given number of times to get rid of any initial dependencies 222 introduced by the L.C.R.N.G. Note that the initialization of randtbl[] 223 for default usage relies on values produced by this routine. */ 224 void 225 __srandom (unsigned int x) 226 { 227 __libc_lock_lock (lock); 228 (void) __srandom_r (x, &unsafe_state); 229 __libc_lock_unlock (lock); 230 } 231 232 weak_alias (__srandom, srandom) /* */ 233 weak_alias (__srandom, srand) 234 235 /* Initialize the state information in the given array of N bytes for 236 future random number generation. Based on the number of bytes we 237 are given, and the break values for the different R.N.G.'s, we choose 238 the best (largest) one we can and set things up for it. srandom is 239 then called to initialize the state information. Note that on return 240 from srandom, we set state[-1] to be the type multiplexed with the current 241 value of the rear pointer; this is so successive calls to initstate won't 242 lose this information and will be able to restart with setstate. 243 Note: The first thing we do is save the current state, if any, just like 244 setstate so that it doesn't matter when initstate is called. 245 Returns a pointer to the old state. */ 246 char * 247 __initstate (unsigned int seed, char *arg_state, size_t n) 248 { 249 int32_t *ostate; 250 int ret; 251 252 __libc_lock_lock (lock); 253 254 ostate = &unsafe_state.state[-1]; 255 256 ret = __initstate_r (seed, arg_state, n, &unsafe_state); 257 258 __libc_lock_unlock (lock); 259 260 return ret == -1 ? NULL : (char *) ostate; 261 } 262 263 weak_alias (__initstate, initstate) /* */ 264 265 /* Restore the state from the given state array. 266 Note: It is important that we also remember the locations of the pointers 267 in the current state information, and restore the locations of the pointers 268 from the old state information. This is done by multiplexing the pointer 269 location into the zeroth word of the state information. Note that due 270 to the order in which things are done, it is OK to call setstate with the 271 same state as the current state 272 Returns a pointer to the old state information. */ 273 char * 274 __setstate (char *arg_state) 275 { 276 int32_t *ostate; 277 278 __libc_lock_lock (lock); 279 280 ostate = &unsafe_state.state[-1]; 281 282 if (__setstate_r (arg_state, &unsafe_state) < 0) 283 ostate = NULL; 284 285 __libc_lock_unlock (lock); 286 287 return (char *) ostate; 288 } 289 290 weak_alias (__setstate, setstate) /* */ 291 292 /* If we are using the trivial TYPE_0 R.N.G., just do the old linear 293 congruential bit. Otherwise, we do our fancy trinomial stuff, which is the 294 same in all the other cases due to all the global variables that have been 295 set up. The basic operation is to add the number at the rear pointer into 296 the one at the front pointer. Then both pointers are advanced to the next 297 location cyclically in the table. The value returned is the sum generated, 298 reduced to 31 bits by throwing away the "least random" low bit. 299 Note: The code takes advantage of the fact that both the front and 300 rear pointers can't wrap on the same call by not testing the rear 301 pointer if the front one has wrapped. Returns a 31-bit random number. */ 302 303 long int 304 __random (void) 305 { 306 int32_t retval; 307 308 __libc_lock_lock (lock); 309 310 (void) __random_r (&unsafe_state, &retval); 311 312 __libc_lock_unlock (lock); 313 314 return retval; 315 } 316 317 weak_alias (__random, random)