pw_random/public/pw_random/random.h

// Copyright 2020 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.
#pragma once

#include <climits>
#include <cstddef>
#include <cstdint>
#include <limits>

#include "pw_assert/check.h"
#include "pw_bytes/span.h"
#include "pw_span/span.h"
#include "pw_status/status_with_size.h"

namespace pw::random {

// A random generator uses injected entropy to generate random values. Many of
// the guarantees for this interface are provided at the level of the
// implementations. In general:
//  * DO assume a generator will always succeed.
//  * DO NOT assume a generator is cryptographically secure.
//  * DO NOT assume uniformity of generated data.
class RandomGenerator {
 public:
  virtual ~RandomGenerator() = default;

  template <class T>
  void GetInt(T& dest) {
    static_assert(std::is_integral<T>::value,
                  "Use Get() for non-integral types");
    Get({reinterpret_cast<std::byte*>(&dest), sizeof(T)});
  }

  // Calculate a uniformly distributed random number in the range [0,
  // exclusive_upper_bound). This avoids modulo biasing. Uniformity is only
  // guaranteed if the underlying generator generates uniform data. Uniformity
  // is achieved by generating new random numbers until one is generated in the
  // desired range (with optimizations).
  template <class T>
  void GetInt(T& dest, const T& exclusive_upper_bound) {
    static_assert(std::is_unsigned_v<T>, "T must be an unsigned integer");
    PW_DCHECK(exclusive_upper_bound != 0);

    if (exclusive_upper_bound < 2) {
      dest = 0;
      return;
    }

    const uint8_t leading_zeros_in_upper_bound =
        CountLeadingZeros(exclusive_upper_bound);

    // Create a mask that discards the higher order bits of the random number.
    const T mask =
        std::numeric_limits<T>::max() >> leading_zeros_in_upper_bound;

    // This loop should end fairly soon. It discards all the values that aren't
    // below exclusive_upper_bound. The probability of values being greater or
    // equal than exclusive_upper_bound is less than 1/2, which means that the
    // expected amount of iterations is less than 2.
    while (true) {
      GetInt(dest);
      dest &= mask;
      if (dest < exclusive_upper_bound) {
        return;
      }
    }
  }

  // Populates the destination buffer with a randomly generated value.
  virtual void Get(ByteSpan dest) = 0;

  // Injects entropy into the pool. `data` may have up to 32 bits of random
  // entropy. If the number of bits of entropy is less than 32, entropy is
  // assumed to be stored in the least significant bits of `data`.
  virtual void InjectEntropyBits(uint32_t data, uint_fast8_t num_bits) = 0;

  // Injects entropy into the pool byte-by-byte.
  void InjectEntropy(ConstByteSpan data) {
    for (std::byte b : data) {
      InjectEntropyBits(std::to_integer<uint32_t>(b), /*num_bits=*/8);
    }
  }

 private:
  template <class T>
  uint8_t CountLeadingZeros(T value) {
    if constexpr (std::is_same_v<T, unsigned>) {
      return static_cast<uint8_t>(__builtin_clz(value));
    } else if constexpr (std::is_same_v<T, unsigned long>) {
      return static_cast<uint8_t>(__builtin_clzl(value));
    } else if constexpr (std::is_same_v<T, unsigned long long>) {
      return static_cast<uint8_t>(__builtin_clzll(value));
    } else {
      static_assert(sizeof(T) < sizeof(unsigned));
      // __builtin_clz returns the count of leading zeros in an unsigned , so we
      // need to subtract the size difference of T in bits.
      return static_cast<uint8_t>(__builtin_clz(value) -
                                  ((sizeof(unsigned) - sizeof(T)) * CHAR_BIT));
    }
  }
};

}  // namespace pw::random