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/check.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 // Calculate a uniformly distributed random number in the range [0, 46 // exclusive_upper_bound). This avoids modulo biasing. Uniformity is only 47 // guaranteed if the underlying generator generates uniform data. Uniformity 48 // is achieved by generating new random numbers until one is generated in the 49 // desired range (with optimizations). 50 template <class T> GetInt(T & dest,const T & exclusive_upper_bound)51 void GetInt(T& dest, const T& exclusive_upper_bound) { 52 static_assert(std::is_unsigned_v<T>, "T must be an unsigned integer"); 53 PW_DCHECK(exclusive_upper_bound != 0); 54 55 if (exclusive_upper_bound < 2) { 56 dest = 0; 57 return; 58 } 59 60 const uint8_t leading_zeros_in_upper_bound = 61 CountLeadingZeros(exclusive_upper_bound); 62 63 // Create a mask that discards the higher order bits of the random number. 64 const T mask = 65 std::numeric_limits<T>::max() >> leading_zeros_in_upper_bound; 66 67 // This loop should end fairly soon. It discards all the values that aren't 68 // below exclusive_upper_bound. The probability of values being greater or 69 // equal than exclusive_upper_bound is less than 1/2, which means that the 70 // expected amount of iterations is less than 2. 71 while (true) { 72 GetInt(dest); 73 dest &= mask; 74 if (dest < exclusive_upper_bound) { 75 return; 76 } 77 } 78 } 79 80 // Populates the destination buffer with a randomly generated value. 81 virtual void Get(ByteSpan dest) = 0; 82 83 // Injects entropy into the pool. `data` may have up to 32 bits of random 84 // entropy. If the number of bits of entropy is less than 32, entropy is 85 // assumed to be stored in the least significant bits of `data`. 86 virtual void InjectEntropyBits(uint32_t data, uint_fast8_t num_bits) = 0; 87 88 // Injects entropy into the pool byte-by-byte. InjectEntropy(ConstByteSpan data)89 void InjectEntropy(ConstByteSpan data) { 90 for (std::byte b : data) { 91 InjectEntropyBits(std::to_integer<uint32_t>(b), /*num_bits=*/8); 92 } 93 } 94 95 private: 96 template <class T> CountLeadingZeros(T value)97 uint8_t CountLeadingZeros(T value) { 98 if constexpr (std::is_same_v<T, unsigned>) { 99 return static_cast<uint8_t>(__builtin_clz(value)); 100 } else if constexpr (std::is_same_v<T, unsigned long>) { 101 return static_cast<uint8_t>(__builtin_clzl(value)); 102 } else if constexpr (std::is_same_v<T, unsigned long long>) { 103 return static_cast<uint8_t>(__builtin_clzll(value)); 104 } else { 105 static_assert(sizeof(T) < sizeof(unsigned)); 106 // __builtin_clz returns the count of leading zeros in an unsigned , so we 107 // need to subtract the size difference of T in bits. 108 return static_cast<uint8_t>(__builtin_clz(value) - 109 ((sizeof(unsigned) - sizeof(T)) * CHAR_BIT)); 110 } 111 } 112 }; 113 114 } // namespace pw::random 115