legacy-libs/grpc/deps/grpc/third_party/abseil-cpp/absl/random/internal/randen_engine.h

   1 // Copyright 2017 The Abseil Authors.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of 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,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 #ifndef ABSL_RANDOM_INTERNAL_RANDEN_ENGINE_H_
  16 #define ABSL_RANDOM_INTERNAL_RANDEN_ENGINE_H_
  17
  18 #include <algorithm>
  19 #include <cinttypes>
  20 #include <cstdlib>
  21 #include <iostream>
  22 #include <iterator>
  23 #include <limits>
  24 #include <type_traits>
  25
  26 #include "absl/meta/type_traits.h"
  27 #include "absl/random/internal/iostream_state_saver.h"
  28 #include "absl/random/internal/randen.h"
  29
  30 namespace absl {
  31 namespace random_internal {
  32
  33 // Deterministic pseudorandom byte generator with backtracking resistance
  34 // (leaking the state does not compromise prior outputs). Based on Reverie
  35 // (see "A Robust and Sponge-Like PRNG with Improved Efficiency") instantiated
  36 // with an improved Simpira-like permutation.
  37 // Returns values of type "T" (must be a built-in unsigned integer type).
  38 //
  39 // RANDen = RANDom generator or beetroots in Swiss High German.
  40 // 'Strong' (well-distributed, unpredictable, backtracking-resistant) random
  41 // generator, faster in some benchmarks than std::mt19937_64 and pcg64_c32.
  42 template <typename T>
  43 class alignas(16) randen_engine {
  44  public:
  45   // C++11 URBG interface:
  46   using result_type = T;
  47   static_assert(std::is_unsigned<result_type>::value,
  48                 "randen_engine template argument must be a built-in unsigned "
  49                 "integer type");
  50
  51   static constexpr result_type(min)() {
  52     return (std::numeric_limits<result_type>::min)();
  53   }
  54
  55   static constexpr result_type(max)() {
  56     return (std::numeric_limits<result_type>::max)();
  57   }
  58
  59   explicit randen_engine(result_type seed_value = 0) { seed(seed_value); }
  60
  61   template <class SeedSequence,
  62             typename = typename absl::enable_if_t<
  63                 !std::is_same<SeedSequence, randen_engine>::value>>
  64   explicit randen_engine(SeedSequence&& seq) {
  65     seed(seq);
  66   }
  67
  68   randen_engine(const randen_engine&) = default;
  69
  70   // Returns random bits from the buffer in units of result_type.
  71   result_type operator()() {
  72     // Refill the buffer if needed (unlikely).
  73     if (next_ >= kStateSizeT) {
  74       next_ = kCapacityT;
  75       impl_.Generate(state_);
  76     }
  77
  78     return state_[next_++];
  79   }
  80
  81   template <class SeedSequence>
  82   typename absl::enable_if_t<
  83       !std::is_convertible<SeedSequence, result_type>::value>
  84   seed(SeedSequence&& seq) {
  85     // Zeroes the state.
  86     seed();
  87     reseed(seq);
  88   }
  89
  90   void seed(result_type seed_value = 0) {
  91     next_ = kStateSizeT;
  92     // Zeroes the inner state and fills the outer state with seed_value to
  93     // mimics behaviour of reseed
  94     std::fill(std::begin(state_), std::begin(state_) + kCapacityT, 0);
  95     std::fill(std::begin(state_) + kCapacityT, std::end(state_), seed_value);
  96   }
  97
  98   // Inserts entropy into (part of) the state. Calling this periodically with
  99   // sufficient entropy ensures prediction resistance (attackers cannot predict
 100   // future outputs even if state is compromised).
 101   template <class SeedSequence>
 102   void reseed(SeedSequence& seq) {
 103     using sequence_result_type = typename SeedSequence::result_type;
 104     static_assert(sizeof(sequence_result_type) == 4,
 105                   "SeedSequence::result_type must be 32-bit");
 106
 107     constexpr size_t kBufferSize =
 108         Randen::kSeedBytes / sizeof(sequence_result_type);
 109     alignas(16) sequence_result_type buffer[kBufferSize];
 110
 111     // Randen::Absorb XORs the seed into state, which is then mixed by a call
 112     // to Randen::Generate. Seeding with only the provided entropy is preferred
 113     // to using an arbitrary generate() call, so use [rand.req.seed_seq]
 114     // size as a proxy for the number of entropy units that can be generated
 115     // without relying on seed sequence mixing...
 116     const size_t entropy_size = seq.size();
 117     if (entropy_size < kBufferSize) {
 118       // ... and only request that many values, or 256-bits, when unspecified.
 119       const size_t requested_entropy = (entropy_size == 0) ? 8u : entropy_size;
 120       std::fill(std::begin(buffer) + requested_entropy, std::end(buffer), 0);
 121       seq.generate(std::begin(buffer), std::begin(buffer) + requested_entropy);
 122       // The Randen paper suggests preferentially initializing even-numbered
 123       // 128-bit vectors of the randen state (there are 16 such vectors).
 124       // The seed data is merged into the state offset by 128-bits, which
 125       // implies prefering seed bytes [16..31, ..., 208..223]. Since the
 126       // buffer is 32-bit values, we swap the corresponding buffer positions in
 127       // 128-bit chunks.
 128       size_t dst = kBufferSize;
 129       while (dst > 7) {
 130         // leave the odd bucket as-is.
 131         dst -= 4;
 132         size_t src = dst >> 1;
 133         // swap 128-bits into the even bucket
 134         std::swap(buffer[--dst], buffer[--src]);
 135         std::swap(buffer[--dst], buffer[--src]);
 136         std::swap(buffer[--dst], buffer[--src]);
 137         std::swap(buffer[--dst], buffer[--src]);
 138       }
 139     } else {
 140       seq.generate(std::begin(buffer), std::end(buffer));
 141     }
 142     impl_.Absorb(buffer, state_);
 143
 144     // Generate will be called when operator() is called
 145     next_ = kStateSizeT;
 146   }
 147
 148   void discard(uint64_t count) {
 149     uint64_t step = std::min<uint64_t>(kStateSizeT - next_, count);
 150     count -= step;
 151
 152     constexpr uint64_t kRateT = kStateSizeT - kCapacityT;
 153     while (count > 0) {
 154       next_ = kCapacityT;
 155       impl_.Generate(state_);
 156       step = std::min<uint64_t>(kRateT, count);
 157       count -= step;
 158     }
 159     next_ += step;
 160   }
 161
 162   bool operator==(const randen_engine& other) const {
 163     return next_ == other.next_ &&
 164            std::equal(std::begin(state_), std::end(state_),
 165                       std::begin(other.state_));
 166   }
 167
 168   bool operator!=(const randen_engine& other) const {
 169     return !(*this == other);
 170   }
 171
 172   template <class CharT, class Traits>
 173   friend std::basic_ostream<CharT, Traits>& operator<<(
 174       std::basic_ostream<CharT, Traits>& os,  // NOLINT(runtime/references)
 175       const randen_engine<T>& engine) {       // NOLINT(runtime/references)
 176     using numeric_type =
 177         typename random_internal::stream_format_type<result_type>::type;
 178     auto saver = random_internal::make_ostream_state_saver(os);
 179     for (const auto& elem : engine.state_) {
 180       // In the case that `elem` is `uint8_t`, it must be cast to something
 181       // larger so that it prints as an integer rather than a character. For
 182       // simplicity, apply the cast all circumstances.
 183       os << static_cast<numeric_type>(elem) << os.fill();
 184     }
 185     os << engine.next_;
 186     return os;
 187   }
 188
 189   template <class CharT, class Traits>
 190   friend std::basic_istream<CharT, Traits>& operator>>(
 191       std::basic_istream<CharT, Traits>& is,  // NOLINT(runtime/references)
 192       randen_engine<T>& engine) {             // NOLINT(runtime/references)
 193     using numeric_type =
 194         typename random_internal::stream_format_type<result_type>::type;
 195     result_type state[kStateSizeT];
 196     size_t next;
 197     for (auto& elem : state) {
 198       // It is not possible to read uint8_t from wide streams, so it is
 199       // necessary to read a wider type and then cast it to uint8_t.
 200       numeric_type value;
 201       is >> value;
 202       elem = static_cast<result_type>(value);
 203     }
 204     is >> next;
 205     if (is.fail()) {
 206       return is;
 207     }
 208     std::memcpy(engine.state_, state, sizeof(engine.state_));
 209     engine.next_ = next;
 210     return is;
 211   }
 212
 213  private:
 214   static constexpr size_t kStateSizeT =
 215       Randen::kStateBytes / sizeof(result_type);
 216   static constexpr size_t kCapacityT =
 217       Randen::kCapacityBytes / sizeof(result_type);
 218
 219   // First kCapacityT are `inner', the others are accessible random bits.
 220   alignas(16) result_type state_[kStateSizeT];
 221   size_t next_;  // index within state_
 222   Randen impl_;
 223 };
 224
 225 }  // namespace random_internal
 226 }  // namespace absl
 227
 228 #endif  // ABSL_RANDOM_INTERNAL_RANDEN_ENGINE_H_