1 // Copyright 2020 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 #pragma once 15 16 #include <climits> 17 #include <cstddef> 18 #include <cstdint> 19 #include <limits> 20 21 #include "pw_assert/assert.h" 22 #include "pw_bytes/span.h" 23 #include "pw_span/span.h" 24 #include "pw_status/status_with_size.h" 25 26 namespace pw::random { 27 28 /// A random generator uses injected entropy to generate random values. Many of 29 /// the guarantees for this interface are provided at the level of the 30 /// implementations. In general: 31 /// * DO assume a generator will always succeed. 32 /// * DO NOT assume a generator is cryptographically secure. 33 /// * DO NOT assume uniformity of generated data. 34 class RandomGenerator { 35 public: 36 virtual ~RandomGenerator() = default; 37 38 template <class T> GetInt(T & dest)39 void GetInt(T& dest) { 40 static_assert(std::is_integral<T>::value, 41 "Use Get() for non-integral types"); 42 Get({reinterpret_cast<std::byte*>(&dest), sizeof(T)}); 43 } 44 45 /// Calculates a uniformly distributed random number in the range 46 /// `[0, exclusive_upper_bound)`. 47 /// 48 /// This avoids modulo biasing. Uniformity is only guaranteed if the 49 /// underlying generator generates uniform data. Uniformity is achieved by 50 /// generating new random numbers until one is generated in the desired 51 /// range (with optimizations). 52 /// 53 /// @param[out] dest The destination to populate the random number into. 54 /// 55 /// @param[in] exclusive_upper_bound The largest number that can be 56 /// populated into `dest`, exclusive. 57 template <class T> GetInt(T & dest,const T & exclusive_upper_bound)58 void GetInt(T& dest, const T& exclusive_upper_bound) { 59 static_assert(std::is_unsigned_v<T>, "T must be an unsigned integer"); 60 PW_ASSERT(exclusive_upper_bound != 0); 61 62 if (exclusive_upper_bound < 2) { 63 dest = 0; 64 return; 65 } 66 67 const uint8_t leading_zeros_in_upper_bound = 68 CountLeadingZeros(exclusive_upper_bound); 69 70 // Create a mask that discards the higher order bits of the random number. 71 const T mask = 72 std::numeric_limits<T>::max() >> leading_zeros_in_upper_bound; 73 74 // This loop should end fairly soon. It discards all the values that aren't 75 // below exclusive_upper_bound. The probability of values being greater or 76 // equal than exclusive_upper_bound is less than 1/2, which means that the 77 // expected amount of iterations is less than 2. 78 while (true) { 79 GetInt(dest); 80 dest &= mask; 81 if (dest < exclusive_upper_bound) { 82 return; 83 } 84 } 85 } 86 87 /// Populates the destination buffer with a randomly generated value. 88 /// 89 /// @param[out] dest The destination buffer. 90 virtual void Get(ByteSpan dest) = 0; 91 92 /// Injects entropy into the pool. 93 /// 94 /// @param[in] data Up to 32 bits of random entropy data. 95 /// 96 /// @param[in] num_bits The number of bits of entropy. If less than `32`, 97 /// entropy is assumed to be stored in the least significant bits of `data`. 98 virtual void InjectEntropyBits(uint32_t data, uint_fast8_t num_bits) = 0; 99 100 /// Injects entropy into the pool byte-by-byte. InjectEntropy(ConstByteSpan data)101 void InjectEntropy(ConstByteSpan data) { 102 for (std::byte b : data) { 103 InjectEntropyBits(std::to_integer<uint32_t>(b), /*num_bits=*/8); 104 } 105 } 106 107 private: 108 template <class T> CountLeadingZeros(T value)109 uint8_t CountLeadingZeros(T value) { 110 if constexpr (std::is_same_v<T, unsigned>) { 111 return static_cast<uint8_t>(__builtin_clz(value)); 112 } else if constexpr (std::is_same_v<T, unsigned long>) { 113 return static_cast<uint8_t>(__builtin_clzl(value)); 114 } else if constexpr (std::is_same_v<T, unsigned long long>) { 115 return static_cast<uint8_t>(__builtin_clzll(value)); 116 } else { 117 static_assert(sizeof(T) < sizeof(unsigned)); 118 // __builtin_clz returns the count of leading zeros in an unsigned , so we 119 // need to subtract the size difference of T in bits. 120 return static_cast<uint8_t>(__builtin_clz(value) - 121 ((sizeof(unsigned) - sizeof(T)) * CHAR_BIT)); 122 } 123 } 124 }; 125 126 } // namespace pw::random 127