31 #define RANDUTILS_HPP 1 97 #include <initializer_list> 99 #include <type_traits> 107 #if !defined(RANDUTILS_CPU_ENTROPY) && defined(__has_builtin) 108 #if __has_builtin(__builtin_readcyclecounter) 109 #define RANDUTILS_CPU_ENTROPY __builtin_readcyclecounter() 112 #if !defined(RANDUTILS_CPU_ENTROPY) 115 #define RANDUTILS_CPU_ENTROPY __builtin_ia32_rdtsc() 117 #include <immintrin.h> 118 #define RANDUTILS_CPU_ENTROPY __rdtsc() 121 #define RANDUTILS_CPU_ENTROPY 0 125 #if defined(RANDUTILS_GETPID) 127 #elif defined(_WIN64) || defined(_WIN32) 129 #define RANDUTILS_GETPID _getpid() 130 #elif defined(__unix__) || defined(__unix) || (defined(__APPLE__) && defined(__MACH__)) 132 #define RANDUTILS_GETPID getpid() 134 #define RANDUTILS_GETPID 0 137 #if __cpp_constexpr >= 201304L 138 #define RANDUTILS_GENERALIZED_CONSTEXPR constexpr 140 #define RANDUTILS_GENERALIZED_CONSTEXPR 212 template <
size_t count = 4,
typename IntRep = u
int32_t,
size_t mix_rounds = 1 + (count <= 2)>
217 typedef IntRep result_type;
220 static constexpr u
int32_t INIT_A = 0x43b0d7e5;
221 static constexpr u
int32_t MULT_A = 0x931e8875;
223 static constexpr u
int32_t INIT_B = 0x8b51f9dd;
224 static constexpr u
int32_t MULT_B = 0x58f38ded;
226 static constexpr u
int32_t MIX_MULT_L = 0xca01f9dd;
227 static constexpr u
int32_t MIX_MULT_R = 0x4973f715;
228 static constexpr u
int32_t XSHIFT = sizeof(IntRep) * 8 / 2;
230 RANDUTILS_GENERALIZED_CONSTEXPR
232 fast_exp(IntRep x, IntRep power)
234 IntRep result = IntRep(1);
235 IntRep multiplier = x;
236 while (power != IntRep(0))
238 IntRep thismult = power & IntRep(1) ? multiplier : IntRep(1);
241 multiplier *= multiplier;
246 std::array<IntRep, count> mixer_;
248 template <
typename InputIter>
249 void mix_entropy(InputIter begin, InputIter end);
252 seed_seq_fe(
const seed_seq_fe&) =
delete;
253 void operator=(
const seed_seq_fe&) =
delete;
255 template <
typename T>
256 seed_seq_fe(std::initializer_list<T>
init)
258 seed(init.begin(), init.end());
261 template <
typename InputIter>
262 seed_seq_fe(InputIter begin, InputIter end)
268 template <
typename RandomAccessIterator>
269 void generate(RandomAccessIterator first, RandomAccessIterator last)
const;
271 static constexpr
size_t 277 template <
typename OutputIterator>
278 void param(OutputIterator dest)
const;
280 template <
typename InputIter>
282 seed(InputIter begin, InputIter end)
284 mix_entropy(begin, end);
287 for (
size_t i = 1; i < mix_rounds; ++i) stir();
293 mix_entropy(mixer_.begin(), mixer_.end());
298 template <
size_t count,
typename IntRep,
size_t r>
299 template <
typename InputIter>
301 seed_seq_fe<count, IntRep, r>::mix_entropy(InputIter begin, InputIter end)
303 auto hash_const = INIT_A;
304 auto hash = [&](IntRep value)
307 hash_const *= MULT_A;
309 value ^= value >> XSHIFT;
312 auto mix = [](IntRep x, IntRep y)
314 IntRep result = MIX_MULT_L * x - MIX_MULT_R * y;
315 result ^= result >> XSHIFT;
319 InputIter current = begin;
320 for (
auto& elem : mixer_)
323 elem = hash(*current++);
327 for (
auto& src : mixer_)
328 for (
auto& dest : mixer_)
329 if (&src != &dest) dest = mix(dest, hash(src));
330 for (; current != end; ++current)
331 for (
auto& dest : mixer_) dest = mix(dest, hash(*current));
334 template <
size_t count,
typename IntRep,
size_t mix_rounds>
335 template <
typename OutputIterator>
337 seed_seq_fe<count, IntRep, mix_rounds>::param(OutputIterator dest)
const 339 const IntRep INV_A = fast_exp(MULT_A, IntRep(-1));
340 const IntRep MIX_INV_L = fast_exp(MIX_MULT_L, IntRep(-1));
342 auto mixer_copy = mixer_;
343 for (
size_t round = 0; round < mix_rounds; ++round)
346 auto hash_const = INIT_A * fast_exp(MULT_A, IntRep(
count *
count));
348 for (
auto src = mixer_copy.rbegin(); src != mixer_copy.rend(); ++src)
349 for (
auto dest = mixer_copy.rbegin(); dest != mixer_copy.rend(); ++dest)
352 IntRep revhashed = *src;
353 auto mult_const = hash_const;
355 revhashed ^= hash_const;
356 revhashed *= mult_const;
357 revhashed ^= revhashed >> XSHIFT;
358 IntRep unmixed = *dest;
359 unmixed ^= unmixed >> XSHIFT;
360 unmixed += MIX_MULT_R * revhashed;
361 unmixed *= MIX_INV_L;
364 for (
auto i = mixer_copy.rbegin(); i != mixer_copy.rend(); ++i)
366 IntRep unhashed = *i;
367 unhashed ^= unhashed >> XSHIFT;
368 unhashed *= fast_exp(hash_const, IntRep(-1));
370 unhashed ^= hash_const;
374 std::copy(mixer_copy.begin(), mixer_copy.end(), dest);
377 template <
size_t count,
typename IntRep,
size_t mix_rounds>
378 template <
typename RandomAccessIterator>
380 seed_seq_fe<count, IntRep, mix_rounds>::generate(RandomAccessIterator dest_begin,
381 RandomAccessIterator dest_end)
const 383 auto src_begin = mixer_.begin();
384 auto src_end = mixer_.end();
385 auto src = src_begin;
386 auto hash_const = INIT_B;
387 for (
auto dest = dest_begin; dest != dest_end; ++dest)
390 if (++src == src_end) src = src_begin;
391 dataval ^= hash_const;
392 hash_const *= MULT_B;
393 dataval *= hash_const;
394 dataval ^= dataval >> XSHIFT;
399 using seed_seq_fe128 = seed_seq_fe<4, uint32_t>;
400 using seed_seq_fe256 = seed_seq_fe<8, uint32_t>;
427 template <
typename SeedSeq>
428 class auto_seeded :
public SeedSeq
430 using default_seeds = std::array<uint32_t, 11>;
432 template <
typename T>
441 result *= 0xbc2ad017d719504d;
442 return uint32_t(result ^ (result >> 32));
446 template <
typename T>
451 std::hash<
typename std::remove_reference<
typename std::remove_cv<T>::type>::type>{}(
452 std::forward<T>(value)));
458 return *pos ==
'\0' ? hash : fnv((hash * 16777619U) ^ *pos, pos + 1);
470 static uint32_t random_int = std::random_device{}();
473 void* malloc_addr = malloc(
sizeof(
int));
475 auto heap = hash(malloc_addr);
476 auto stack = hash(&malloc_addr);
480 random_int += 0xedf19156;
484 auto hitime = std::chrono::high_resolution_clock::now().time_since_epoch().count();
491 auto self_data = hash(
this);
502 auto exit_func = hash(&_Exit);
509 auto self_func = hash(
static_cast<uint32_t (*)(
uint64_t)
>(&auto_seeded::crushto32));
513 auto thread_id = hash(std::this_thread::get_id());
517 #if __cpp_rtti || __GXX_RTTI 518 auto type_id = crushto32(
typeid(*this).hash_code());
524 auto pid = crushto32(RANDUTILS_GETPID);
525 auto cpu = crushto32(RANDUTILS_CPU_ENTROPY);
527 return {{random_int, crushto32(hitime), stack, heap, self_data, self_func, exit_func,
528 thread_id, type_id, pid, cpu}};
532 using SeedSeq::SeedSeq;
534 using base_seed_seq = SeedSeq;
548 auto_seeded(default_seeds seeds)
549 : SeedSeq(seeds.begin(), seeds.end())
555 : auto_seeded(local_entropy())
561 using auto_seed_128 = auto_seeded<seed_seq_fe128>;
562 using auto_seed_256 = auto_seeded<seed_seq_fe256>;
577 template <
typename Numeric>
578 using uniform_distribution =
579 typename std::conditional<std::is_integral<Numeric>::value,
580 std::uniform_int_distribution<Numeric>,
581 std::uniform_real_distribution<Numeric>>::type;
607 template <
typename RandomEngine = std::default_random_engine,
608 typename DefaultSeedSeq = auto_seed_256>
609 class random_generator
612 using engine_type = RandomEngine;
613 using default_seed_type = DefaultSeedSeq;
624 template <
typename T>
625 static constexpr
bool 626 has_base_seed_seq(
typename T::base_seed_seq*)
631 template <
typename T>
632 static constexpr
bool has_base_seed_seq(...)
637 template <
typename SeedSeqBased>
638 static auto seed_seq_cast(
639 SeedSeqBased&& seq,
typename std::enable_if<has_base_seed_seq<SeedSeqBased>(0)>::type* = 0)
640 -> decltype(seq.base())
645 template <
typename SeedSeq>
647 seed_seq_cast(SeedSeq&& seq,
typename std::enable_if<!has_base_seed_seq<SeedSeq>(0)>::type* = 0)
653 template <
typename Seeding = default_seed_type,
typename... Params>
654 random_generator(Seeding&& seeding = default_seed_type{})
655 : engine_{seed_seq_cast(std::forward<Seeding>(seeding))}
664 template <
typename Seeding,
typename... Params>
665 random_generator(Seeding&& seeding, Params&&... params)
666 : engine_{seed_seq_cast(std::forward<Seeding>(seeding)), std::forward<Params>(params)...}
671 template <
typename Seeding = default_seed_type,
typename... Params>
673 seed(Seeding&& seeding = default_seed_type{})
675 engine_.seed(seed_seq_cast(seeding));
682 template <
typename Seeding,
typename... Params>
684 seed(Seeding&& seeding, Params&&... params)
686 engine_.seed(seed_seq_cast(seeding), std::forward<Params>(params)...);
695 template <
typename ResultType,
696 template <
typename>
class DistTmpl = std::normal_distribution,
699 variate(Params&&... params)
701 DistTmpl<ResultType> dist(std::forward<Params>(params)...);
703 return dist(engine_);
706 template <
typename Numeric>
708 uniform(Numeric lower, Numeric upper)
710 return variate<Numeric, uniform_distribution>(lower, upper);
713 template <
template <
typename>
class DistTmpl = uniform_distribution,
717 generate(Iter first, Iter last, Params&&... params)
719 using result_type =
typename std::remove_reference<decltype(*(first))>::type;
721 DistTmpl<result_type> dist(std::forward<Params>(params)...);
723 std::generate(first, last, [&]
725 return dist(engine_);
729 template <
template <
typename>
class DistTmpl = uniform_distribution,
733 generate(Range&& range, Params&&... params)
735 generate<DistTmpl>(std::begin(range), std::end(range), std::forward<Params>(params)...);
738 template <
typename Iter>
740 shuffle(Iter first, Iter last)
742 std::shuffle(first, last, engine_);
745 template <
typename Range>
747 shuffle(Range&& range)
749 shuffle(std::begin(range), std::end(range));
752 template <
typename Iter>
754 choose(Iter first, Iter last)
756 auto dist = std::distance(first, last);
757 if (dist < 2)
return first;
758 using distance_type = decltype(dist);
759 distance_type choice = uniform(distance_type(0), --dist);
760 std::advance(first, choice);
764 template <
typename Range>
765 auto choose(Range&& range) -> decltype(std::begin(range))
767 return choose(std::begin(range), std::end(range));
770 template <
typename Range>
771 auto pick(Range&& range) -> decltype(*std::begin(range))
773 return *choose(std::begin(range), std::end(range));
776 template <
typename T>
777 auto pick(std::initializer_list<T> range) -> decltype(*range.begin())
779 return *choose(range.begin(), range.end());
782 template <
typename Size,
typename Iter>
784 sample(Size to_go, Iter first, Iter last)
786 auto total = std::distance(first, last);
787 using value_type = decltype(*first);
789 return std::stable_partition(first, last, [&](
const value_type&)
792 using distance_type = decltype(total);
793 distance_type zero{};
794 if (uniform(zero, total) < to_go)
806 template <
typename Size,
typename Range>
807 auto sample(Size to_go, Range&& range) -> decltype(std::begin(range))
809 return sample(to_go, std::begin(range), std::end(range));
813 using default_rng = random_generator<std::default_random_engine>;
814 using mt19937_rng = random_generator<std::mt19937>;
817 #endif // RANDUTILS_HPP unsigned int uint32_t
Unsigned 32-bit integer.
void copy(T *dest, const T *src, size_t len)
Copy one array of objects to another.
unsigned long uint64_t
Unsigned 64-bit integer.
void init()
Initialize UTL++.
size_t count(const FwdIt &begin, const FwdIt &end, const Predicate *pred=nullptr, bool predVal=true)
Count objects that satisfy a Predicate.