leo hendrickson / Mbed OS example-Ethernet-mbed-Cloud-connect

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.

simple-mbed-cloud-client/mbed-cloud-client/mbed-client-randlib/source/randLIB.c@0:8f0bb79ddd48, 2021-05-04 (annotated)

Committer:
leothedragon
Date:
Tue May 04 08:55:12 2021 +0000
Revision:
0:8f0bb79ddd48
nmn

Who changed what in which revision?

UserRevisionLine numberNew contents of line
leothedragon 0:8f0bb79ddd48 1 /*
leothedragon 0:8f0bb79ddd48 2 * Copyright (c) 2014-2015 ARM Limited. All rights reserved.
leothedragon 0:8f0bb79ddd48 3 * SPDX-License-Identifier: Apache-2.0
leothedragon 0:8f0bb79ddd48 4 * Licensed under the Apache License, Version 2.0 (the License); you may
leothedragon 0:8f0bb79ddd48 5 * not use this file except in compliance with the License.
leothedragon 0:8f0bb79ddd48 6 * You may obtain a copy of the License at
leothedragon 0:8f0bb79ddd48 7 *
leothedragon 0:8f0bb79ddd48 8 * http://www.apache.org/licenses/LICENSE-2.0
leothedragon 0:8f0bb79ddd48 9 *
leothedragon 0:8f0bb79ddd48 10 * Unless required by applicable law or agreed to in writing, software
leothedragon 0:8f0bb79ddd48 11 * distributed under the License is distributed on an AS IS BASIS, WITHOUT
leothedragon 0:8f0bb79ddd48 12 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
leothedragon 0:8f0bb79ddd48 13 * See the License for the specific language governing permissions and
leothedragon 0:8f0bb79ddd48 14 * limitations under the License.
leothedragon 0:8f0bb79ddd48 15 */
leothedragon 0:8f0bb79ddd48 16 #include <stdint.h>
leothedragon 0:8f0bb79ddd48 17 #include <limits.h>
leothedragon 0:8f0bb79ddd48 18 #include "randLIB.h"
leothedragon 0:8f0bb79ddd48 19 #include "platform/arm_hal_random.h"
leothedragon 0:8f0bb79ddd48 20
leothedragon 0:8f0bb79ddd48 21 /**
leothedragon 0:8f0bb79ddd48 22 * This library is made for getting random numbers for timing needs in
leothedragon 0:8f0bb79ddd48 23 * protocols, plus to generate dynamic ports, random IDs etc.
leothedragon 0:8f0bb79ddd48 24 *
leothedragon 0:8f0bb79ddd48 25 * **not safe to use for security or cryptographic operations.**
leothedragon 0:8f0bb79ddd48 26 *
leothedragon 0:8f0bb79ddd48 27 * Base implementation is a pseudo-RNG, but may also use a system RNG.
leothedragon 0:8f0bb79ddd48 28 * Replay of sequence by reseeding is not possible.
leothedragon 0:8f0bb79ddd48 29 *
leothedragon 0:8f0bb79ddd48 30 * Base pseudo-RNG is the xoroshiro128+ generator by Marsaglia, Blackman and
leothedragon 0:8f0bb79ddd48 31 * Vigna:
leothedragon 0:8f0bb79ddd48 32 *
leothedragon 0:8f0bb79ddd48 33 * http://xoroshiro.di.unimi.it/
leothedragon 0:8f0bb79ddd48 34 *
leothedragon 0:8f0bb79ddd48 35 * Certainly not the fastest for 32-bit or smaller platforms, but speed
leothedragon 0:8f0bb79ddd48 36 * is not critical. None of the long operations in the core are actually hard,
leothedragon 0:8f0bb79ddd48 37 * unlike the divisions and multiplies in the utility functions below, where we
leothedragon 0:8f0bb79ddd48 38 * do try to keep the operations narrow.
leothedragon 0:8f0bb79ddd48 39 */
leothedragon 0:8f0bb79ddd48 40
leothedragon 0:8f0bb79ddd48 41 /* On some platforms, read from a system RNG, rather than use our own */
leothedragon 0:8f0bb79ddd48 42 /* RANDLIB_PRNG disables this and forces use of the PRNG (useful for test only?) */
leothedragon 0:8f0bb79ddd48 43 #ifndef RANDLIB_PRNG
leothedragon 0:8f0bb79ddd48 44 #ifdef __linux
leothedragon 0:8f0bb79ddd48 45 #define RANDOM_DEVICE "/dev/urandom"
leothedragon 0:8f0bb79ddd48 46 #endif
leothedragon 0:8f0bb79ddd48 47 #endif // RANDLIB_PRNG
leothedragon 0:8f0bb79ddd48 48
leothedragon 0:8f0bb79ddd48 49 /* RAM usage - 16 bytes of state (or a FILE * pointer and underlying FILE, which
leothedragon 0:8f0bb79ddd48 50 * will include a buffer) */
leothedragon 0:8f0bb79ddd48 51 #ifdef RANDOM_DEVICE
leothedragon 0:8f0bb79ddd48 52 #include <stdio.h>
leothedragon 0:8f0bb79ddd48 53 static FILE *random_file;
leothedragon 0:8f0bb79ddd48 54 #else
leothedragon 0:8f0bb79ddd48 55 static uint64_t state[2];
leothedragon 0:8f0bb79ddd48 56 #endif
leothedragon 0:8f0bb79ddd48 57
leothedragon 0:8f0bb79ddd48 58 #ifdef RANDLIB_PRNG
leothedragon 0:8f0bb79ddd48 59 void randLIB_reset(void)
leothedragon 0:8f0bb79ddd48 60 {
leothedragon 0:8f0bb79ddd48 61 state[0] = 0;
leothedragon 0:8f0bb79ddd48 62 state[1] = 0;
leothedragon 0:8f0bb79ddd48 63 }
leothedragon 0:8f0bb79ddd48 64 #endif
leothedragon 0:8f0bb79ddd48 65
leothedragon 0:8f0bb79ddd48 66 #ifndef RANDOM_DEVICE
leothedragon 0:8f0bb79ddd48 67 static inline uint64_t rol(uint64_t n, int bits)
leothedragon 0:8f0bb79ddd48 68 {
leothedragon 0:8f0bb79ddd48 69 return (n << bits) | (n >> (64 - bits));
leothedragon 0:8f0bb79ddd48 70 }
leothedragon 0:8f0bb79ddd48 71
leothedragon 0:8f0bb79ddd48 72 /* Lower-quality generator used only for initial seeding, if platform
leothedragon 0:8f0bb79ddd48 73 * isn't returning multiple seeds itself. Multiplies are rather heavy
leothedragon 0:8f0bb79ddd48 74 * for lower-end platforms, but this is initialisation only.
leothedragon 0:8f0bb79ddd48 75 */
leothedragon 0:8f0bb79ddd48 76 static uint64_t splitmix64(uint64_t *seed)
leothedragon 0:8f0bb79ddd48 77 {
leothedragon 0:8f0bb79ddd48 78 uint64_t z = (*seed += UINT64_C(0x9E3779B97F4A7C15));
leothedragon 0:8f0bb79ddd48 79 z = (z ^ (z >> 30)) * UINT64_C(0xBF58476D1CE4E5B9);
leothedragon 0:8f0bb79ddd48 80 z = (z ^ (z >> 27)) * UINT64_C(0x94D049BB133111EB);
leothedragon 0:8f0bb79ddd48 81 return z ^ (z >> 31);
leothedragon 0:8f0bb79ddd48 82 }
leothedragon 0:8f0bb79ddd48 83 #endif // RANDOM_DEVICE
leothedragon 0:8f0bb79ddd48 84
leothedragon 0:8f0bb79ddd48 85 void randLIB_seed_random(void)
leothedragon 0:8f0bb79ddd48 86 {
leothedragon 0:8f0bb79ddd48 87 #ifdef RANDOM_DEVICE
leothedragon 0:8f0bb79ddd48 88 if (!random_file) {
leothedragon 0:8f0bb79ddd48 89 random_file = fopen(RANDOM_DEVICE, "rb");
leothedragon 0:8f0bb79ddd48 90 }
leothedragon 0:8f0bb79ddd48 91 #else
leothedragon 0:8f0bb79ddd48 92 arm_random_module_init();
leothedragon 0:8f0bb79ddd48 93
leothedragon 0:8f0bb79ddd48 94 /* We exclusive-OR with the current state, in case they make this call
leothedragon 0:8f0bb79ddd48 95 * multiple times,or in case someone has called randLIB_add_seed before
leothedragon 0:8f0bb79ddd48 96 * this. We don't want to potentially lose entropy.
leothedragon 0:8f0bb79ddd48 97 */
leothedragon 0:8f0bb79ddd48 98
leothedragon 0:8f0bb79ddd48 99 /* Spell out expressions so we get known ordering of 4 seed calls */
leothedragon 0:8f0bb79ddd48 100 uint64_t s = (uint64_t) arm_random_seed_get() << 32;
leothedragon 0:8f0bb79ddd48 101 state[0] ^= ( s | arm_random_seed_get());
leothedragon 0:8f0bb79ddd48 102
leothedragon 0:8f0bb79ddd48 103 s = (uint64_t) arm_random_seed_get() << 32;
leothedragon 0:8f0bb79ddd48 104 state[1] ^= s | arm_random_seed_get();
leothedragon 0:8f0bb79ddd48 105
leothedragon 0:8f0bb79ddd48 106 /* This check serves to both to stir the state if the platform is returning
leothedragon 0:8f0bb79ddd48 107 * constant seeding values, and to avoid the illegal all-zero state.
leothedragon 0:8f0bb79ddd48 108 */
leothedragon 0:8f0bb79ddd48 109 if (state[0] == state[1]) {
leothedragon 0:8f0bb79ddd48 110 randLIB_add_seed(state[0]);
leothedragon 0:8f0bb79ddd48 111 }
leothedragon 0:8f0bb79ddd48 112 #endif // RANDOM_DEVICE
leothedragon 0:8f0bb79ddd48 113 }
leothedragon 0:8f0bb79ddd48 114
leothedragon 0:8f0bb79ddd48 115 void randLIB_add_seed(uint64_t seed)
leothedragon 0:8f0bb79ddd48 116 {
leothedragon 0:8f0bb79ddd48 117 #ifndef RANDOM_DEVICE
leothedragon 0:8f0bb79ddd48 118 state[0] ^= splitmix64(&seed);
leothedragon 0:8f0bb79ddd48 119 state[1] ^= splitmix64(&seed);
leothedragon 0:8f0bb79ddd48 120 /* This is absolutely necessary, but I challenge you to add it to line coverage */
leothedragon 0:8f0bb79ddd48 121 if (state[1] == 0 && state[0] == 0) {
leothedragon 0:8f0bb79ddd48 122 state[0] = 1;
leothedragon 0:8f0bb79ddd48 123 }
leothedragon 0:8f0bb79ddd48 124 #else
leothedragon 0:8f0bb79ddd48 125 (void)seed;
leothedragon 0:8f0bb79ddd48 126 #endif
leothedragon 0:8f0bb79ddd48 127 }
leothedragon 0:8f0bb79ddd48 128
leothedragon 0:8f0bb79ddd48 129 uint8_t randLIB_get_8bit(void)
leothedragon 0:8f0bb79ddd48 130 {
leothedragon 0:8f0bb79ddd48 131 uint64_t r = randLIB_get_64bit();
leothedragon 0:8f0bb79ddd48 132 return (uint8_t) (r >> 56);
leothedragon 0:8f0bb79ddd48 133 }
leothedragon 0:8f0bb79ddd48 134
leothedragon 0:8f0bb79ddd48 135 uint16_t randLIB_get_16bit(void)
leothedragon 0:8f0bb79ddd48 136 {
leothedragon 0:8f0bb79ddd48 137 uint64_t r = randLIB_get_64bit();
leothedragon 0:8f0bb79ddd48 138 return (uint16_t) (r >> 48);
leothedragon 0:8f0bb79ddd48 139 }
leothedragon 0:8f0bb79ddd48 140
leothedragon 0:8f0bb79ddd48 141 uint32_t randLIB_get_32bit(void)
leothedragon 0:8f0bb79ddd48 142 {
leothedragon 0:8f0bb79ddd48 143 uint64_t r = randLIB_get_64bit();
leothedragon 0:8f0bb79ddd48 144 return (uint32_t) (r >> 32);
leothedragon 0:8f0bb79ddd48 145 }
leothedragon 0:8f0bb79ddd48 146
leothedragon 0:8f0bb79ddd48 147
leothedragon 0:8f0bb79ddd48 148 uint64_t randLIB_get_64bit(void)
leothedragon 0:8f0bb79ddd48 149 {
leothedragon 0:8f0bb79ddd48 150 #ifdef RANDOM_DEVICE
leothedragon 0:8f0bb79ddd48 151 if (!random_file) {
leothedragon 0:8f0bb79ddd48 152 return 0;
leothedragon 0:8f0bb79ddd48 153 }
leothedragon 0:8f0bb79ddd48 154 uint64_t result;
leothedragon 0:8f0bb79ddd48 155 if (fread(&result, sizeof result, 1, random_file) != 1) {
leothedragon 0:8f0bb79ddd48 156 result = 0;
leothedragon 0:8f0bb79ddd48 157 }
leothedragon 0:8f0bb79ddd48 158 return result;
leothedragon 0:8f0bb79ddd48 159 #else
leothedragon 0:8f0bb79ddd48 160 const uint64_t s0 = state[0];
leothedragon 0:8f0bb79ddd48 161 uint64_t s1 = state[1];
leothedragon 0:8f0bb79ddd48 162 const uint64_t result = s0 + s1;
leothedragon 0:8f0bb79ddd48 163
leothedragon 0:8f0bb79ddd48 164 s1 ^= s0;
leothedragon 0:8f0bb79ddd48 165 state[0] = rol(s0, 55) ^ s1 ^ (s1 << 14);
leothedragon 0:8f0bb79ddd48 166 state[1] = rol(s1, 36);
leothedragon 0:8f0bb79ddd48 167
leothedragon 0:8f0bb79ddd48 168 return result;
leothedragon 0:8f0bb79ddd48 169 #endif
leothedragon 0:8f0bb79ddd48 170 }
leothedragon 0:8f0bb79ddd48 171
leothedragon 0:8f0bb79ddd48 172 void *randLIB_get_n_bytes_random(void *ptr, uint8_t count)
leothedragon 0:8f0bb79ddd48 173 {
leothedragon 0:8f0bb79ddd48 174 uint8_t *data_ptr = ptr;
leothedragon 0:8f0bb79ddd48 175 uint64_t r = 0;
leothedragon 0:8f0bb79ddd48 176 for (uint_fast8_t i = 0; i < count; i++) {
leothedragon 0:8f0bb79ddd48 177 /* Take 8 bytes at a time */
leothedragon 0:8f0bb79ddd48 178 if (i % 8 == 0) {
leothedragon 0:8f0bb79ddd48 179 r = randLIB_get_64bit();
leothedragon 0:8f0bb79ddd48 180 } else {
leothedragon 0:8f0bb79ddd48 181 r >>= 8;
leothedragon 0:8f0bb79ddd48 182 }
leothedragon 0:8f0bb79ddd48 183 data_ptr[i] = (uint8_t) r;
leothedragon 0:8f0bb79ddd48 184 }
leothedragon 0:8f0bb79ddd48 185 return data_ptr;
leothedragon 0:8f0bb79ddd48 186 }
leothedragon 0:8f0bb79ddd48 187
leothedragon 0:8f0bb79ddd48 188 uint16_t randLIB_get_random_in_range(uint16_t min, uint16_t max)
leothedragon 0:8f0bb79ddd48 189 {
leothedragon 0:8f0bb79ddd48 190 /* This special case is potentially common, particularly in this routine's
leothedragon 0:8f0bb79ddd48 191 * first user (Trickle), so worth catching immediately */
leothedragon 0:8f0bb79ddd48 192 if (min == max) {
leothedragon 0:8f0bb79ddd48 193 return min;
leothedragon 0:8f0bb79ddd48 194 }
leothedragon 0:8f0bb79ddd48 195
leothedragon 0:8f0bb79ddd48 196 #if UINT_MAX >= 0xFFFFFFFF
leothedragon 0:8f0bb79ddd48 197 const unsigned int rand_max = 0xFFFFFFFFu; // will use rand32
leothedragon 0:8f0bb79ddd48 198 #else
leothedragon 0:8f0bb79ddd48 199 const unsigned int rand_max = 0xFFFFu; // will use rand16
leothedragon 0:8f0bb79ddd48 200
leothedragon 0:8f0bb79ddd48 201 /* 16-bit arithmetic below fails in this extreme case; we can optimise it */
leothedragon 0:8f0bb79ddd48 202 if (max - min == 0xFFFF) {
leothedragon 0:8f0bb79ddd48 203 return randLIB_get_16bit();
leothedragon 0:8f0bb79ddd48 204 }
leothedragon 0:8f0bb79ddd48 205 #endif
leothedragon 0:8f0bb79ddd48 206
leothedragon 0:8f0bb79ddd48 207 /* We get rand_max values from rand16 or 32() in the range [0..rand_max-1], and
leothedragon 0:8f0bb79ddd48 208 * need to divvy them up into the number of values we need. And reroll any
leothedragon 0:8f0bb79ddd48 209 * odd values off the end as we insist every value having equal chance.
leothedragon 0:8f0bb79ddd48 210 *
leothedragon 0:8f0bb79ddd48 211 * Using the range [0..rand_max-1] saves long division on the band
leothedragon 0:8f0bb79ddd48 212 * calculation - it means rand_max ends up always being rerolled.
leothedragon 0:8f0bb79ddd48 213 *
leothedragon 0:8f0bb79ddd48 214 * Eg, range(1,2), rand_max = 0xFFFF:
leothedragon 0:8f0bb79ddd48 215 * We have 2 bands of size 0x7FFF (0xFFFF/2).
leothedragon 0:8f0bb79ddd48 216 *
leothedragon 0:8f0bb79ddd48 217 * We roll: 0x0000..0x7FFE -> 1
leothedragon 0:8f0bb79ddd48 218 * 0x7FFF..0xFFFD -> 2
leothedragon 0:8f0bb79ddd48 219 * 0xFFFE..0xFFFF -> reroll
leothedragon 0:8f0bb79ddd48 220 * (calculating band size as 0x10000/2 would have avoided the reroll cases)
leothedragon 0:8f0bb79ddd48 221 *
leothedragon 0:8f0bb79ddd48 222 * Eg, range(1,3), rand_max = 0xFFFFFFFF:
leothedragon 0:8f0bb79ddd48 223 * We have 3 bands of size 0x55555555 (0xFFFFFFFF/3).
leothedragon 0:8f0bb79ddd48 224 *
leothedragon 0:8f0bb79ddd48 225 * We roll: 0x00000000..0x555555554 -> 1
leothedragon 0:8f0bb79ddd48 226 * 0x55555555..0xAAAAAAAA9 -> 2
leothedragon 0:8f0bb79ddd48 227 * 0xAAAAAAAA..0xFFFFFFFFE -> 3
leothedragon 0:8f0bb79ddd48 228 * 0xFFFFFFFF -> reroll
leothedragon 0:8f0bb79ddd48 229 *
leothedragon 0:8f0bb79ddd48 230 * (Bias problem clearly pretty insignificant there, but gets worse as
leothedragon 0:8f0bb79ddd48 231 * range increases).
leothedragon 0:8f0bb79ddd48 232 */
leothedragon 0:8f0bb79ddd48 233 const unsigned int values_needed = max + 1 - min;
leothedragon 0:8f0bb79ddd48 234 /* Avoid the need for long division, at the expense of fractionally
leothedragon 0:8f0bb79ddd48 235 * increasing reroll chance. */
leothedragon 0:8f0bb79ddd48 236 const unsigned int band_size = rand_max / values_needed;
leothedragon 0:8f0bb79ddd48 237 const unsigned int top_of_bands = band_size * values_needed;
leothedragon 0:8f0bb79ddd48 238 unsigned int result;
leothedragon 0:8f0bb79ddd48 239 do {
leothedragon 0:8f0bb79ddd48 240 #if UINT_MAX > 0xFFFF
leothedragon 0:8f0bb79ddd48 241 result = randLIB_get_32bit();
leothedragon 0:8f0bb79ddd48 242 #else
leothedragon 0:8f0bb79ddd48 243 result = randLIB_get_16bit();
leothedragon 0:8f0bb79ddd48 244 #endif
leothedragon 0:8f0bb79ddd48 245 } while (result >= top_of_bands);
leothedragon 0:8f0bb79ddd48 246
leothedragon 0:8f0bb79ddd48 247 return min + (uint16_t)(result / band_size);
leothedragon 0:8f0bb79ddd48 248 }
leothedragon 0:8f0bb79ddd48 249
leothedragon 0:8f0bb79ddd48 250 uint32_t randLIB_randomise_base(uint32_t base, uint16_t min_factor, uint16_t max_factor)
leothedragon 0:8f0bb79ddd48 251 {
leothedragon 0:8f0bb79ddd48 252 uint16_t random_factor = randLIB_get_random_in_range(min_factor, max_factor);
leothedragon 0:8f0bb79ddd48 253
leothedragon 0:8f0bb79ddd48 254 /* 32x16-bit long multiplication, to get 48-bit result */
leothedragon 0:8f0bb79ddd48 255 uint32_t hi = (base >> 16) * random_factor;
leothedragon 0:8f0bb79ddd48 256 uint32_t lo = (base & 0xFFFF) * random_factor;
leothedragon 0:8f0bb79ddd48 257 /* Add halves, and take top 32 bits of 48-bit result */
leothedragon 0:8f0bb79ddd48 258 uint32_t res = hi + (lo >> 16);
leothedragon 0:8f0bb79ddd48 259
leothedragon 0:8f0bb79ddd48 260 /* Randomisation factor is *2^15, so need to shift up 1 more bit, avoiding overflow */
leothedragon 0:8f0bb79ddd48 261 if (res & 0x80000000) {
leothedragon 0:8f0bb79ddd48 262 res = 0xFFFFFFFF;
leothedragon 0:8f0bb79ddd48 263 } else {
leothedragon 0:8f0bb79ddd48 264 res = (res << 1) | ((lo >> 15) & 1);
leothedragon 0:8f0bb79ddd48 265 }
leothedragon 0:8f0bb79ddd48 266
leothedragon 0:8f0bb79ddd48 267 return res;
leothedragon 0:8f0bb79ddd48 268 }