ON Semiconductor / mbed-os

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.

Dependents:   mbed-TFT-example-NCS36510 mbed-Accelerometer-example-NCS36510 mbed-Accelerometer-example-NCS36510

features/FEATURE_COMMON_PAL/mbed-client-randlib/source/randLIB.c@0:098463de4c5d, 2017-01-25 (annotated)

Committer:
group-onsemi
Date:
Wed Jan 25 20:34:15 2017 +0000
Revision:
0:098463de4c5d
Initial commit

Who changed what in which revision?

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