Simple interface for Mbed Cloud Client
Embed:
(wiki syntax)
Show/hide line numbers
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 19:01:36 by 1.7.2