Important changes to repositories hosted on mbed.com
Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.
To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.
It is also possible to export all your personal repositories from the account settings page.
randLIB.c
00001 /* 00002 * Copyright (c) 2014-2015 ARM Limited. All rights reserved. 00003 * SPDX-License-Identifier: Apache-2.0 00004 * Licensed under the Apache License, Version 2.0 (the License); you may 00005 * not use this file except in compliance with the License. 00006 * You may obtain a copy of the License at 00007 * 00008 * http://www.apache.org/licenses/LICENSE-2.0 00009 * 00010 * Unless required by applicable law or agreed to in writing, software 00011 * distributed under the License is distributed on an AS IS BASIS, WITHOUT 00012 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00013 * See the License for the specific language governing permissions and 00014 * limitations under the License. 00015 */ 00016 #include <stdint.h> 00017 #include <limits.h> 00018 #include "randLIB.h" 00019 #include "platform/arm_hal_random.h" 00020 00021 /** 00022 * This library is made for getting random numbers for timing needs in 00023 * protocols, plus to generate dynamic ports, random IDs etc. 00024 * 00025 * **not safe to use for security or cryptographic operations.** 00026 * 00027 * Base implementation is a pseudo-RNG, but may also use a system RNG. 00028 * Replay of sequence by reseeding is not possible. 00029 * 00030 * Base pseudo-RNG is the xoroshiro128+ generator by Marsaglia, Blackman and 00031 * Vigna: 00032 * 00033 * http://xoroshiro.di.unimi.it/ 00034 * 00035 * Certainly not the fastest for 32-bit or smaller platforms, but speed 00036 * is not critical. None of the long operations in the core are actually hard, 00037 * unlike the divisions and multiplies in the utility functions below, where we 00038 * do try to keep the operations narrow. 00039 */ 00040 00041 /* On some platforms, read from a system RNG, rather than use our own */ 00042 /* RANDLIB_PRNG disables this and forces use of the PRNG (useful for test only?) */ 00043 #ifndef RANDLIB_PRNG 00044 #ifdef __linux 00045 #define RANDOM_DEVICE "/dev/urandom" 00046 #endif 00047 #endif // RANDLIB_PRNG 00048 00049 /* RAM usage - 16 bytes of state (or a FILE * pointer and underlying FILE, which 00050 * will include a buffer) */ 00051 #ifdef RANDOM_DEVICE 00052 #include <stdio.h> 00053 static FILE *random_file; 00054 #else 00055 static uint64_t state[2]; 00056 #endif 00057 00058 #ifdef RANDLIB_PRNG 00059 void randLIB_reset(void) 00060 { 00061 state[0] = 0; 00062 state[1] = 0; 00063 } 00064 #endif 00065 00066 #ifndef RANDOM_DEVICE 00067 static inline uint64_t rol(uint64_t n, int bits) 00068 { 00069 return (n << bits) | (n >> (64 - bits)); 00070 } 00071 00072 /* Lower-quality generator used only for initial seeding, if platform 00073 * isn't returning multiple seeds itself. Multiplies are rather heavy 00074 * for lower-end platforms, but this is initialisation only. 00075 */ 00076 static uint64_t splitmix64(uint64_t *seed) 00077 { 00078 uint64_t z = (*seed += UINT64_C(0x9E3779B97F4A7C15)); 00079 z = (z ^ (z >> 30)) * UINT64_C(0xBF58476D1CE4E5B9); 00080 z = (z ^ (z >> 27)) * UINT64_C(0x94D049BB133111EB); 00081 return z ^ (z >> 31); 00082 } 00083 #endif // RANDOM_DEVICE 00084 00085 void randLIB_seed_random(void) 00086 { 00087 #ifdef RANDOM_DEVICE 00088 if (!random_file) { 00089 random_file = fopen(RANDOM_DEVICE, "rb"); 00090 } 00091 #else 00092 arm_random_module_init(); 00093 00094 /* We exclusive-OR with the current state, in case they make this call 00095 * multiple times,or in case someone has called randLIB_add_seed before 00096 * this. We don't want to potentially lose entropy. 00097 */ 00098 00099 /* Spell out expressions so we get known ordering of 4 seed calls */ 00100 uint64_t s = (uint64_t) arm_random_seed_get() << 32; 00101 state[0] ^= ( s | arm_random_seed_get()); 00102 00103 s = (uint64_t) arm_random_seed_get() << 32; 00104 state[1] ^= s | arm_random_seed_get(); 00105 00106 /* This check serves to both to stir the state if the platform is returning 00107 * constant seeding values, and to avoid the illegal all-zero state. 00108 */ 00109 if (state[0] == state[1]) { 00110 randLIB_add_seed(state[0]); 00111 } 00112 #endif // RANDOM_DEVICE 00113 } 00114 00115 void randLIB_add_seed(uint64_t seed) 00116 { 00117 #ifndef RANDOM_DEVICE 00118 state[0] ^= splitmix64(&seed); 00119 state[1] ^= splitmix64(&seed); 00120 /* This is absolutely necessary, but I challenge you to add it to line coverage */ 00121 if (state[1] == 0 && state[0] == 0) { 00122 state[0] = 1; 00123 } 00124 #else 00125 (void)seed; 00126 #endif 00127 } 00128 00129 uint8_t randLIB_get_8bit(void) 00130 { 00131 uint64_t r = randLIB_get_64bit(); 00132 return (uint8_t) (r >> 56); 00133 } 00134 00135 uint16_t randLIB_get_16bit(void) 00136 { 00137 uint64_t r = randLIB_get_64bit(); 00138 return (uint16_t) (r >> 48); 00139 } 00140 00141 uint32_t randLIB_get_32bit(void) 00142 { 00143 uint64_t r = randLIB_get_64bit(); 00144 return (uint32_t) (r >> 32); 00145 } 00146 00147 00148 uint64_t randLIB_get_64bit(void) 00149 { 00150 #ifdef RANDOM_DEVICE 00151 if (!random_file) { 00152 return 0; 00153 } 00154 uint64_t result; 00155 if (fread(&result, sizeof result, 1, random_file) != 1) { 00156 result = 0; 00157 } 00158 return result; 00159 #else 00160 const uint64_t s0 = state[0]; 00161 uint64_t s1 = state[1]; 00162 const uint64_t result = s0 + s1; 00163 00164 s1 ^= s0; 00165 state[0] = rol(s0, 55) ^ s1 ^ (s1 << 14); 00166 state[1] = rol(s1, 36); 00167 00168 return result; 00169 #endif 00170 } 00171 00172 void *randLIB_get_n_bytes_random(void *ptr, uint8_t count) 00173 { 00174 uint8_t *data_ptr = ptr; 00175 uint64_t r = 0; 00176 for (uint_fast8_t i = 0; i < count; i++) { 00177 /* Take 8 bytes at a time */ 00178 if (i % 8 == 0) { 00179 r = randLIB_get_64bit(); 00180 } else { 00181 r >>= 8; 00182 } 00183 data_ptr[i] = (uint8_t) r; 00184 } 00185 return data_ptr; 00186 } 00187 00188 uint16_t randLIB_get_random_in_range(uint16_t min, uint16_t max) 00189 { 00190 /* This special case is potentially common, particularly in this routine's 00191 * first user (Trickle), so worth catching immediately */ 00192 if (min == max) { 00193 return min; 00194 } 00195 00196 #if UINT_MAX >= 0xFFFFFFFF 00197 const unsigned int rand_max = 0xFFFFFFFFu; // will use rand32 00198 #else 00199 const unsigned int rand_max = 0xFFFFu; // will use rand16 00200 00201 /* 16-bit arithmetic below fails in this extreme case; we can optimise it */ 00202 if (max - min == 0xFFFF) { 00203 return randLIB_get_16bit(); 00204 } 00205 #endif 00206 00207 /* We get rand_max values from rand16 or 32() in the range [0..rand_max-1], and 00208 * need to divvy them up into the number of values we need. And reroll any 00209 * odd values off the end as we insist every value having equal chance. 00210 * 00211 * Using the range [0..rand_max-1] saves long division on the band 00212 * calculation - it means rand_max ends up always being rerolled. 00213 * 00214 * Eg, range(1,2), rand_max = 0xFFFF: 00215 * We have 2 bands of size 0x7FFF (0xFFFF/2). 00216 * 00217 * We roll: 0x0000..0x7FFE -> 1 00218 * 0x7FFF..0xFFFD -> 2 00219 * 0xFFFE..0xFFFF -> reroll 00220 * (calculating band size as 0x10000/2 would have avoided the reroll cases) 00221 * 00222 * Eg, range(1,3), rand_max = 0xFFFFFFFF: 00223 * We have 3 bands of size 0x55555555 (0xFFFFFFFF/3). 00224 * 00225 * We roll: 0x00000000..0x555555554 -> 1 00226 * 0x55555555..0xAAAAAAAA9 -> 2 00227 * 0xAAAAAAAA..0xFFFFFFFFE -> 3 00228 * 0xFFFFFFFF -> reroll 00229 * 00230 * (Bias problem clearly pretty insignificant there, but gets worse as 00231 * range increases). 00232 */ 00233 const unsigned int values_needed = max + 1 - min; 00234 /* Avoid the need for long division, at the expense of fractionally 00235 * increasing reroll chance. */ 00236 const unsigned int band_size = rand_max / values_needed; 00237 const unsigned int top_of_bands = band_size * values_needed; 00238 unsigned int result; 00239 do { 00240 #if UINT_MAX > 0xFFFF 00241 result = randLIB_get_32bit(); 00242 #else 00243 result = randLIB_get_16bit(); 00244 #endif 00245 } while (result >= top_of_bands); 00246 00247 return min + (uint16_t)(result / band_size); 00248 } 00249 00250 uint32_t randLIB_randomise_base(uint32_t base, uint16_t min_factor, uint16_t max_factor) 00251 { 00252 uint16_t random_factor = randLIB_get_random_in_range(min_factor, max_factor); 00253 00254 /* 32x16-bit long multiplication, to get 48-bit result */ 00255 uint32_t hi = (base >> 16) * random_factor; 00256 uint32_t lo = (base & 0xFFFF) * random_factor; 00257 /* Add halves, and take top 32 bits of 48-bit result */ 00258 uint32_t res = hi + (lo >> 16); 00259 00260 /* Randomisation factor is *2^15, so need to shift up 1 more bit, avoiding overflow */ 00261 if (res & 0x80000000) { 00262 res = 0xFFFFFFFF; 00263 } else { 00264 res = (res << 1) | ((lo >> 15) & 1); 00265 } 00266 00267 return res; 00268 }
Generated on Tue Jul 12 2022 12:45:42 by
