summaryrefslogtreecommitdiff
path: root/absl/random/internal/randen_engine.h
blob: b47086649e2b15ec2aaa8f4ad999d310272cbaff (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
// Copyright 2017 The Abseil 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.

#ifndef ABSL_RANDOM_INTERNAL_RANDEN_ENGINE_H_
#define ABSL_RANDOM_INTERNAL_RANDEN_ENGINE_H_

#include <algorithm>
#include <cinttypes>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <limits>
#include <type_traits>

#include "absl/base/internal/endian.h"
#include "absl/meta/type_traits.h"
#include "absl/random/internal/iostream_state_saver.h"
#include "absl/random/internal/randen.h"

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace random_internal {

// Deterministic pseudorandom byte generator with backtracking resistance
// (leaking the state does not compromise prior outputs). Based on Reverie
// (see "A Robust and Sponge-Like PRNG with Improved Efficiency") instantiated
// with an improved Simpira-like permutation.
// Returns values of type "T" (must be a built-in unsigned integer type).
//
// RANDen = RANDom generator or beetroots in Swiss High German.
// 'Strong' (well-distributed, unpredictable, backtracking-resistant) random
// generator, faster in some benchmarks than std::mt19937_64 and pcg64_c32.
template <typename T>
class alignas(8) randen_engine {
 public:
  // C++11 URBG interface:
  using result_type = T;
  static_assert(std::is_unsigned<result_type>::value,
                "randen_engine template argument must be a built-in unsigned "
                "integer type");

  static constexpr result_type(min)() {
    return (std::numeric_limits<result_type>::min)();
  }

  static constexpr result_type(max)() {
    return (std::numeric_limits<result_type>::max)();
  }

  randen_engine() : randen_engine(0) {}
  explicit randen_engine(result_type seed_value) { seed(seed_value); }

  template <class SeedSequence,
            typename = typename absl::enable_if_t<
                !std::is_same<SeedSequence, randen_engine>::value>>
  explicit randen_engine(SeedSequence&& seq) {
    seed(seq);
  }

  // alignment requirements dictate custom copy and move constructors.
  randen_engine(const randen_engine& other)
      : next_(other.next_), impl_(other.impl_) {
    std::memcpy(state(), other.state(), kStateSizeT * sizeof(result_type));
  }
  randen_engine& operator=(const randen_engine& other) {
    next_ = other.next_;
    impl_ = other.impl_;
    std::memcpy(state(), other.state(), kStateSizeT * sizeof(result_type));
    return *this;
  }

  // Returns random bits from the buffer in units of result_type.
  result_type operator()() {
    // Refill the buffer if needed (unlikely).
    auto* begin = state();
    if (next_ >= kStateSizeT) {
      next_ = kCapacityT;
      impl_.Generate(begin);
    }
    return little_endian::ToHost(begin[next_++]);
  }

  template <class SeedSequence>
  typename absl::enable_if_t<
      !std::is_convertible<SeedSequence, result_type>::value>
  seed(SeedSequence&& seq) {
    // Zeroes the state.
    seed();
    reseed(seq);
  }

  void seed(result_type seed_value = 0) {
    next_ = kStateSizeT;
    // Zeroes the inner state and fills the outer state with seed_value to
    // mimic the behaviour of reseed
    auto* begin = state();
    std::fill(begin, begin + kCapacityT, 0);
    std::fill(begin + kCapacityT, begin + kStateSizeT, seed_value);
  }

  // Inserts entropy into (part of) the state. Calling this periodically with
  // sufficient entropy ensures prediction resistance (attackers cannot predict
  // future outputs even if state is compromised).
  template <class SeedSequence>
  void reseed(SeedSequence& seq) {
    using sequence_result_type = typename SeedSequence::result_type;
    static_assert(sizeof(sequence_result_type) == 4,
                  "SeedSequence::result_type must be 32-bit");
    constexpr size_t kBufferSize =
        Randen::kSeedBytes / sizeof(sequence_result_type);
    alignas(16) sequence_result_type buffer[kBufferSize];

    // Randen::Absorb XORs the seed into state, which is then mixed by a call
    // to Randen::Generate. Seeding with only the provided entropy is preferred
    // to using an arbitrary generate() call, so use [rand.req.seed_seq]
    // size as a proxy for the number of entropy units that can be generated
    // without relying on seed sequence mixing...
    const size_t entropy_size = seq.size();
    if (entropy_size < kBufferSize) {
      // ... and only request that many values, or 256-bits, when unspecified.
      const size_t requested_entropy = (entropy_size == 0) ? 8u : entropy_size;
      std::fill(buffer + requested_entropy, buffer + kBufferSize, 0);
      seq.generate(buffer, buffer + requested_entropy);
#ifdef ABSL_IS_BIG_ENDIAN
      // Randen expects the seed buffer to be in Little Endian; reverse it on
      // Big Endian platforms.
      for (sequence_result_type& e : buffer) {
        e = absl::little_endian::FromHost(e);
      }
#endif
      // The Randen paper suggests preferentially initializing even-numbered
      // 128-bit vectors of the randen state (there are 16 such vectors).
      // The seed data is merged into the state offset by 128-bits, which
      // implies prefering seed bytes [16..31, ..., 208..223]. Since the
      // buffer is 32-bit values, we swap the corresponding buffer positions in
      // 128-bit chunks.
      size_t dst = kBufferSize;
      while (dst > 7) {
        // leave the odd bucket as-is.
        dst -= 4;
        size_t src = dst >> 1;
        // swap 128-bits into the even bucket
        std::swap(buffer[--dst], buffer[--src]);
        std::swap(buffer[--dst], buffer[--src]);
        std::swap(buffer[--dst], buffer[--src]);
        std::swap(buffer[--dst], buffer[--src]);
      }
    } else {
      seq.generate(buffer, buffer + kBufferSize);
    }
    impl_.Absorb(buffer, state());

    // Generate will be called when operator() is called
    next_ = kStateSizeT;
  }

  void discard(uint64_t count) {
    uint64_t step = std::min<uint64_t>(kStateSizeT - next_, count);
    count -= step;

    constexpr uint64_t kRateT = kStateSizeT - kCapacityT;
    auto* begin = state();
    while (count > 0) {
      next_ = kCapacityT;
      impl_.Generate(*reinterpret_cast<result_type(*)[kStateSizeT]>(begin));
      step = std::min<uint64_t>(kRateT, count);
      count -= step;
    }
    next_ += step;
  }

  bool operator==(const randen_engine& other) const {
    const auto* begin = state();
    return next_ == other.next_ &&
           std::equal(begin, begin + kStateSizeT, other.state());
  }

  bool operator!=(const randen_engine& other) const {
    return !(*this == other);
  }

  template <class CharT, class Traits>
  friend std::basic_ostream<CharT, Traits>& operator<<(
      std::basic_ostream<CharT, Traits>& os,  // NOLINT(runtime/references)
      const randen_engine<T>& engine) {       // NOLINT(runtime/references)
    using numeric_type =
        typename random_internal::stream_format_type<result_type>::type;
    auto saver = random_internal::make_ostream_state_saver(os);
    auto* it = engine.state();
    for (auto* end = it + kStateSizeT; it < end; ++it) {
      // In the case that `elem` is `uint8_t`, it must be cast to something
      // larger so that it prints as an integer rather than a character. For
      // simplicity, apply the cast all circumstances.
      os << static_cast<numeric_type>(little_endian::FromHost(*it))
         << os.fill();
    }
    os << engine.next_;
    return os;
  }

  template <class CharT, class Traits>
  friend std::basic_istream<CharT, Traits>& operator>>(
      std::basic_istream<CharT, Traits>& is,  // NOLINT(runtime/references)
      randen_engine<T>& engine) {             // NOLINT(runtime/references)
    using numeric_type =
        typename random_internal::stream_format_type<result_type>::type;
    result_type state[kStateSizeT];
    size_t next;
    for (auto& elem : state) {
      // It is not possible to read uint8_t from wide streams, so it is
      // necessary to read a wider type and then cast it to uint8_t.
      numeric_type value;
      is >> value;
      elem = little_endian::ToHost(static_cast<result_type>(value));
    }
    is >> next;
    if (is.fail()) {
      return is;
    }
    std::memcpy(engine.state(), state, sizeof(state));
    engine.next_ = next;
    return is;
  }

 private:
  static constexpr size_t kStateSizeT =
      Randen::kStateBytes / sizeof(result_type);
  static constexpr size_t kCapacityT =
      Randen::kCapacityBytes / sizeof(result_type);

  // Returns the state array pointer, which is aligned to 16 bytes.
  // The first kCapacityT are the `inner' sponge; the remainder are available.
  result_type* state() {
    return reinterpret_cast<result_type*>(
        (reinterpret_cast<uintptr_t>(&raw_state_) & 0xf) ? (raw_state_ + 8)
                                                         : raw_state_);
  }
  const result_type* state() const {
    return const_cast<randen_engine*>(this)->state();
  }

  // raw state array, manually aligned in state(). This overallocates
  // by 8 bytes since C++ does not guarantee extended heap alignment.
  alignas(8) char raw_state_[Randen::kStateBytes + 8];
  size_t next_;  // index within state()
  Randen impl_;
};

}  // namespace random_internal
ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_RANDOM_INTERNAL_RANDEN_ENGINE_H_