43#ifndef RANGES_V3_UTILITY_RANDOM_HPP
44#define RANGES_V3_UTILITY_RANDOM_HPP
49#include <initializer_list>
65#if !RANGES_CXX_THREAD_LOCAL
69#include <range/v3/detail/prologue.hpp>
72RANGES_DIAGNOSTIC_IGNORE_CXX17_COMPAT
81 template<
typename Gen>
82 CPP_requires(uniform_random_bit_generator_,
90 template(
typename Gen)(
91 concept (uniform_random_bit_generator_)(Gen),
92 unsigned_integral<invoke_result_t<Gen &>> AND
93 same_as<invoke_result_t<Gen &>,
decltype(Gen::min())> AND
94 same_as<invoke_result_t<Gen &>,
decltype(Gen::max())>);
98 template<
typename Gen>
99 CPP_concept uniform_random_bit_generator =
111 inline std::array<std::uint32_t, 8> get_entropy()
113 std::array<std::uint32_t, 8> seeds;
116#if defined(__GLIBCXX__) && defined(RANGES_WORKAROUND_VALGRIND_RDRAND)
117 std::random_device rd{
"/dev/urandom"};
119 std::random_device rd;
121 std::uniform_int_distribution<std::uint32_t> dist{};
122 ranges::generate(seeds, [&] {
return dist(rd); });
127 template(
typename I)(
128 requires unsigned_integral<I>)
129 constexpr I fast_exp(I x, I power, I result = I{1})
133 : randutils::fast_exp(
134 x * x, power >> 1, result * (power & I{1} ? x : 1));
205 template<std::
size_t count,
typename IntRep = std::u
int32_t>
209 CPP_assert(unsigned_integral<IntRep>);
210 typedef IntRep result_type;
213 static constexpr std::size_t mix_rounds = 1 + (
count <= 2);
215 static constexpr std::uint32_t INIT_A = 0x43b0d7e5;
216 static constexpr std::uint32_t MULT_A = 0x931e8875;
218 static constexpr std::uint32_t INIT_B = 0x8b51f9dd;
219 static constexpr std::uint32_t MULT_B = 0x58f38ded;
221 static constexpr std::uint32_t MIX_MULT_L = 0xca01f9dd;
222 static constexpr std::uint32_t MIX_MULT_R = 0x4973f715;
223 static constexpr std::uint32_t XSHIFT =
sizeof(IntRep) * 8 / 2;
225 std::array<IntRep, count> mixer_;
227 template(
typename I,
typename S)(
228 requires input_iterator<I> AND sentinel_for<S, I> AND
229 convertible_to<iter_reference_t<I>, IntRep>)
230 void mix_entropy(I first, S last)
232 auto hash_const = INIT_A;
233 auto hash = [&](IntRep value) RANGES_INTENDED_MODULAR_ARITHMETIC {
235 hash_const *= MULT_A;
237 value ^= value >> XSHIFT;
240 auto mix = [](IntRep x, IntRep y) RANGES_INTENDED_MODULAR_ARITHMETIC {
241 IntRep result = MIX_MULT_L * x - MIX_MULT_R * y;
242 result ^= result >> XSHIFT;
246 for(
auto & elem : mixer_)
250 elem =
hash(
static_cast<IntRep
>(*first));
254 elem =
hash(IntRep{0});
256 for(
auto & src : mixer_)
257 for(auto & dest : mixer_)
259 dest = mix(dest,
hash(src));
261 for(
auto & dest : mixer_)
262 dest = mix(dest,
hash(static_cast<IntRep>(*
first)));
266 seed_seq_fe(
const seed_seq_fe &) =
delete;
267 void operator=(
const seed_seq_fe &) =
delete;
269 template(
typename T)(
270 requires convertible_to<T const &, IntRep>)
271 seed_seq_fe(std::initializer_list<T> init)
273 seed(init.begin(), init.end());
276 template(
typename I,
typename S)(
277 requires input_iterator<I> AND sentinel_for<S, I> AND
278 convertible_to<iter_reference_t<I>, IntRep>)
279 seed_seq_fe(I first, S last)
285 template(
typename I,
typename S)(
286 requires random_access_iterator<I> AND sentinel_for<S, I>)
287 RANGES_INTENDED_MODULAR_ARITHMETIC
288 void generate(I first, S
const last)
const
290 auto src_begin = mixer_.begin();
291 auto src_end = mixer_.end();
292 auto src = src_begin;
293 auto hash_const = INIT_B;
299 dataval ^= hash_const;
300 hash_const *= MULT_B;
301 dataval *= hash_const;
302 dataval ^= dataval >> XSHIFT;
307 constexpr std::size_t
size()
const
312 template(
typename O)(
313 requires weakly_incrementable<O> AND
314 indirectly_copyable<
decltype(mixer_.begin()), O>)
315 RANGES_INTENDED_MODULAR_ARITHMETIC
void param(O dest)
const
317 constexpr IntRep INV_A = randutils::fast_exp(MULT_A, IntRep(-1));
318 constexpr IntRep MIX_INV_L =
319 randutils::fast_exp(MIX_MULT_L, IntRep(-1));
321 auto mixer_copy = mixer_;
322 for(std::size_t round = 0; round < mix_rounds; ++round)
326 INIT_A * randutils::fast_exp(MULT_A, IntRep(count * count));
328 for(
auto src = mixer_copy.rbegin(); src != mixer_copy.rend();
330 for(
auto rdest = mixer_copy.rbegin();
331 rdest != mixer_copy.rend();
335 IntRep revhashed = *src;
336 auto mult_const = hash_const;
338 revhashed ^= hash_const;
339 revhashed *= mult_const;
340 revhashed ^= revhashed >> XSHIFT;
341 IntRep unmixed = *rdest;
342 unmixed ^= unmixed >> XSHIFT;
343 unmixed += MIX_MULT_R * revhashed;
344 unmixed *= MIX_INV_L;
348 for(
auto i = mixer_copy.rbegin(); i != mixer_copy.rend(); ++i)
350 IntRep unhashed = *i;
351 unhashed ^= unhashed >> XSHIFT;
352 unhashed *= randutils::fast_exp(hash_const, IntRep(-1));
354 unhashed ^= hash_const;
358 ranges::copy(mixer_copy, dest);
361 template(
typename I,
typename S)(
362 requires input_iterator<I> AND sentinel_for<S, I> AND
363 convertible_to<iter_reference_t<I>, IntRep>)
364 void seed(I first, S last)
366 mix_entropy(first, last);
369 for(std::size_t i = 1; i < mix_rounds; ++i)
375 mix_entropy(mixer_.begin(), mixer_.end());
380 using seed_seq_fe128 = seed_seq_fe<4, std::uint32_t>;
381 using seed_seq_fe256 = seed_seq_fe<8, std::uint32_t>;
408 template<
typename SeedSeq>
409 struct auto_seeded :
public SeedSeq
412 : auto_seeded(randutils::get_entropy())
414 template<std::
size_t N>
415 auto_seeded(std::array<std::uint32_t, N>
const & seeds)
416 : SeedSeq(seeds.begin(), seeds.end())
418 using SeedSeq::SeedSeq;
420 const SeedSeq & base()
const
430 using auto_seed_128 = auto_seeded<seed_seq_fe128>;
431 using auto_seed_256 = auto_seeded<seed_seq_fe256>;
434 using default_URNG = meta::if_c<(
sizeof(
void *) >=
sizeof(
long long)),
435 std::mt19937_64, std::mt19937>;
437#if !RANGES_CXX_THREAD_LOCAL
438 template<
typename URNG>
439 class sync_URNG :
private URNG
441 mutable std::mutex mtx_;
445 sync_URNG() =
default;
446 using typename URNG::result_type;
447 result_type operator()()
449 std::lock_guard<std::mutex> guard{mtx_};
450 return static_cast<URNG &
>(*this)();
455 using default_random_engine = sync_URNG<default_URNG>;
457 using default_random_engine = default_URNG;
460 template<
typename T =
void>
461 default_random_engine & get_random_engine()
463 using Seeder = meta::if_c<(
sizeof(default_URNG) > 16),
464 randutils::auto_seed_256,
465 randutils::auto_seed_128>;
467#if RANGES_CXX_THREAD_LOCAL >= RANGES_CXX_THREAD_LOCAL_11
468 static thread_local default_random_engine engine{Seeder{}.base()};
470#elif RANGES_CXX_THREAD_LOCAL
471 static __thread
bool initialized =
false;
472 static __thread
meta::_t<std::aligned_storage<
sizeof(default_random_engine),
473 alignof(default_random_engine)>>
478 ::new(
static_cast<void *
>(&storage))
479 default_random_engine{Seeder{}.base()};
482 auto & engine =
reinterpret_cast<default_random_engine &
>(storage);
484 static default_random_engine engine{Seeder{}.base()};
495#include <range/v3/detail/epilogue.hpp>
typename T::type _t
Type alias for T::type.
Definition meta.hpp:141
front< Pair > first
Retrieve the first element of the pair Pair.
Definition meta.hpp:2251
meta::size_t< L::size()> size
An integral constant wrapper that is the size of the meta::list L.
Definition meta.hpp:1696
_t< detail::count_< L, T > > count
Count the number of times a type T appears in the list L.
Definition meta.hpp:2725
std::size_t hash(const BasicJsonType &j)
hash a JSON value
Definition hash.hpp:34