Marco Zecchini
/
Example_RTOS
Rtos API example
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 #endif 00125 } 00126 00127 uint8_t randLIB_get_8bit(void) 00128 { 00129 uint64_t r = randLIB_get_64bit(); 00130 return (uint8_t) (r >> 56); 00131 } 00132 00133 uint16_t randLIB_get_16bit(void) 00134 { 00135 uint64_t r = randLIB_get_64bit(); 00136 return (uint16_t) (r >> 48); 00137 } 00138 00139 uint32_t randLIB_get_32bit(void) 00140 { 00141 uint64_t r = randLIB_get_64bit(); 00142 return (uint32_t) (r >> 32); 00143 } 00144 00145 00146 uint64_t randLIB_get_64bit(void) 00147 { 00148 #ifdef RANDOM_DEVICE 00149 if (!random_file) { 00150 return 0; 00151 } 00152 uint64_t result; 00153 if (fread(&result, sizeof result, 1, random_file) != 1) { 00154 result = 0; 00155 } 00156 return result; 00157 #else 00158 const uint64_t s0 = state[0]; 00159 uint64_t s1 = state[1]; 00160 const uint64_t result = s0 + s1; 00161 00162 s1 ^= s0; 00163 state[0] = rol(s0, 55) ^ s1 ^ (s1 << 14); 00164 state[1] = rol(s1, 36); 00165 00166 return result; 00167 #endif 00168 } 00169 00170 void *randLIB_get_n_bytes_random(void *ptr, uint8_t count) 00171 { 00172 uint8_t *data_ptr = ptr; 00173 uint64_t r = 0; 00174 for (uint_fast8_t i = 0; i < count; i++) { 00175 /* Take 8 bytes at a time */ 00176 if (i % 8 == 0) { 00177 r = randLIB_get_64bit(); 00178 } else { 00179 r >>= 8; 00180 } 00181 data_ptr[i] = (uint8_t) r; 00182 } 00183 return data_ptr; 00184 } 00185 00186 uint16_t randLIB_get_random_in_range(uint16_t min, uint16_t max) 00187 { 00188 /* This special case is potentially common, particularly in this routine's 00189 * first user (Trickle), so worth catching immediately */ 00190 if (min == max) { 00191 return min; 00192 } 00193 00194 #if UINT_MAX >= 0xFFFFFFFF 00195 const unsigned int rand_max = 0xFFFFFFFFu; // will use rand32 00196 #else 00197 const unsigned int rand_max = 0xFFFFu; // will use rand16 00198 00199 /* 16-bit arithmetic below fails in this extreme case; we can optimise it */ 00200 if (max - min == 0xFFFF) { 00201 return randLIB_get_16bit(); 00202 } 00203 #endif 00204 00205 /* We get rand_max values from rand16 or 32() in the range [0..rand_max-1], and 00206 * need to divvy them up into the number of values we need. And reroll any 00207 * odd values off the end as we insist every value having equal chance. 00208 * 00209 * Using the range [0..rand_max-1] saves long division on the band 00210 * calculation - it means rand_max ends up always being rerolled. 00211 * 00212 * Eg, range(1,2), rand_max = 0xFFFF: 00213 * We have 2 bands of size 0x7FFF (0xFFFF/2). 00214 * 00215 * We roll: 0x0000..0x7FFE -> 1 00216 * 0x7FFF..0xFFFD -> 2 00217 * 0xFFFE..0xFFFF -> reroll 00218 * (calculating band size as 0x10000/2 would have avoided the reroll cases) 00219 * 00220 * Eg, range(1,3), rand_max = 0xFFFFFFFF: 00221 * We have 3 bands of size 0x55555555 (0xFFFFFFFF/3). 00222 * 00223 * We roll: 0x00000000..0x555555554 -> 1 00224 * 0x55555555..0xAAAAAAAA9 -> 2 00225 * 0xAAAAAAAA..0xFFFFFFFFE -> 3 00226 * 0xFFFFFFFF -> reroll 00227 * 00228 * (Bias problem clearly pretty insignificant there, but gets worse as 00229 * range increases). 00230 */ 00231 const unsigned int values_needed = max + 1 - min; 00232 /* Avoid the need for long division, at the expense of fractionally 00233 * increasing reroll chance. */ 00234 const unsigned int band_size = rand_max / values_needed; 00235 const unsigned int top_of_bands = band_size * values_needed; 00236 unsigned int result; 00237 do { 00238 #if UINT_MAX > 0xFFFF 00239 result = randLIB_get_32bit(); 00240 #else 00241 result = randLIB_get_16bit(); 00242 #endif 00243 } while (result >= top_of_bands); 00244 00245 return min + (uint16_t)(result / band_size); 00246 } 00247 00248 uint32_t randLIB_randomise_base(uint32_t base, uint16_t min_factor, uint16_t max_factor) 00249 { 00250 uint16_t random_factor = randLIB_get_random_in_range(min_factor, max_factor); 00251 00252 /* 32x16-bit long multiplication, to get 48-bit result */ 00253 uint32_t hi = (base >> 16) * random_factor; 00254 uint32_t lo = (base & 0xFFFF) * random_factor; 00255 /* Add halves, and take top 32 bits of 48-bit result */ 00256 uint32_t res = hi + (lo >> 16); 00257 00258 /* Randomisation factor is *2^15, so need to shift up 1 more bit, avoiding overflow */ 00259 if (res & 0x80000000) { 00260 res = 0xFFFFFFFF; 00261 } else { 00262 res = (res << 1) | ((lo >> 15) & 1); 00263 } 00264 00265 return res; 00266 }
Generated on Sun Jul 17 2022 08:25:29 by 1.7.2