1 /*
2 * PCG Random Number Generation for C++
3 *
4 * Copyright 2014-2019 Melissa O'Neill <oneill@pcg-random.org>,
5 * and the PCG Project contributors.
6 *
7 * SPDX-License-Identifier: (Apache-2.0 OR MIT)
8 *
9 * Licensed under the Apache License, Version 2.0 (provided in
10 * LICENSE-APACHE.txt and at http://www.apache.org/licenses/LICENSE-2.0)
11 * or under the MIT license (provided in LICENSE-MIT.txt and at
12 * http://opensource.org/licenses/MIT), at your option. This file may not
13 * be copied, modified, or distributed except according to those terms.
14 *
15 * Distributed on an "AS IS" BASIS, WITHOUT WARRANTY OF ANY KIND, either
16 * express or implied. See your chosen license for details.
17 *
18 * For additional information about the PCG random number generation scheme,
19 * visit http://www.pcg-random.org/.
20 */
21
22 /*
23 * This code provides the reference implementation of the PCG family of
24 * random number generators. The code is complex because it implements
25 *
26 * - several members of the PCG family, specifically members corresponding
27 * to the output functions:
28 * - XSH RR (good for 64-bit state, 32-bit output)
29 * - XSH RS (good for 64-bit state, 32-bit output)
30 * - XSL RR (good for 128-bit state, 64-bit output)
31 * - RXS M XS (statistically most powerful generator)
32 * - XSL RR RR (good for 128-bit state, 128-bit output)
33 * - and RXS, RXS M, XSH, XSL (mostly for testing)
34 * - at potentially *arbitrary* bit sizes
35 * - with four different techniques for random streams (MCG, one-stream
36 * LCG, settable-stream LCG, unique-stream LCG)
37 * - and the extended generation schemes allowing arbitrary periods
38 * - with all features of C++11 random number generation (and more),
39 * some of which are somewhat painful, including
40 * - initializing with a SeedSequence which writes 32-bit values
41 * to memory, even though the state of the generator may not
42 * use 32-bit values (it might use smaller or larger integers)
43 * - I/O for RNGs and a prescribed format, which needs to handle
44 * the issue that 8-bit and 128-bit integers don't have working
45 * I/O routines (e.g., normally 8-bit = char, not integer)
46 * - equality and inequality for RNGs
47 * - and a number of convenience typedefs to mask all the complexity
48 *
49 * The code employes a fairly heavy level of abstraction, and has to deal
50 * with various C++ minutia. If you're looking to learn about how the PCG
51 * scheme works, you're probably best of starting with one of the other
52 * codebases (see www.pcg-random.org). But if you're curious about the
53 * constants for the various output functions used in those other, simpler,
54 * codebases, this code shows how they are calculated.
55 *
56 * On the positive side, at least there are convenience typedefs so that you
57 * can say
58 *
59 * pcg32 myRNG;
60 *
61 * rather than:
62 *
63 * pcg_detail::engine<
64 * uint32_t, // Output Type
65 * uint64_t, // State Type
66 * pcg_detail::xsh_rr_mixin<uint32_t, uint64_t>, true, // Output Func
67 * pcg_detail::specific_stream<uint64_t>, // Stream Kind
68 * pcg_detail::default_multiplier<uint64_t> // LCG Mult
69 * > myRNG;
70 *
71 */
72
73 #ifndef PCG_RAND_HPP_INCLUDED
74 #define PCG_RAND_HPP_INCLUDED 1
75
76 #include <algorithm>
77 #include <cinttypes>
78 #include <cstddef>
79 #include <cstdlib>
80 #include <cstring>
81 #include <cassert>
82 #include <limits>
83 #include <iostream>
84 #include <iterator>
85 #include <type_traits>
86 #include <utility>
87 #include <locale>
88 #include <new>
89 #include <stdexcept>
90
91 #ifdef _MSC_VER
92 #pragma warning(disable:4146)
93 #endif
94
95 #ifdef _MSC_VER
96 #define PCG_ALWAYS_INLINE __forceinline
97 #elif __GNUC__
98 #define PCG_ALWAYS_INLINE __attribute__((always_inline))
99 #else
100 #define PCG_ALWAYS_INLINE inline
101 #endif
102
103 /*
104 * The pcg_extras namespace contains some support code that is likley to
105 * be useful for a variety of RNGs, including:
106 * - 128-bit int support for platforms where it isn't available natively
107 * - bit twiddling operations
108 * - I/O of 128-bit and 8-bit integers
109 * - Handling the evilness of SeedSeq
110 * - Support for efficiently producing random numbers less than a given
111 * bound
112 */
113
114 #include "pcg_extras.hpp"
115
116 namespace arrow_vendored {
117 namespace pcg_detail {
118
119 using namespace pcg_extras;
120
121 /*
122 * The LCG generators need some constants to function. This code lets you
123 * look up the constant by *type*. For example
124 *
125 * default_multiplier<uint32_t>::multiplier()
126 *
127 * gives you the default multipler for 32-bit integers. We use the name
128 * of the constant and not a generic word like value to allow these classes
129 * to be used as mixins.
130 */
131
132 template <typename T>
133 struct default_multiplier {
134 // Not defined for an arbitrary type
135 };
136
137 template <typename T>
138 struct default_increment {
139 // Not defined for an arbitrary type
140 };
141
142 #define PCG_DEFINE_CONSTANT(type, what, kind, constant) \
143 template <> \
144 struct what ## _ ## kind<type> { \
145 static constexpr type kind() { \
146 return constant; \
147 } \
148 };
149
150 PCG_DEFINE_CONSTANT(uint8_t, default, multiplier, 141U)
151 PCG_DEFINE_CONSTANT(uint8_t, default, increment, 77U)
152
153 PCG_DEFINE_CONSTANT(uint16_t, default, multiplier, 12829U)
154 PCG_DEFINE_CONSTANT(uint16_t, default, increment, 47989U)
155
156 PCG_DEFINE_CONSTANT(uint32_t, default, multiplier, 747796405U)
157 PCG_DEFINE_CONSTANT(uint32_t, default, increment, 2891336453U)
158
159 PCG_DEFINE_CONSTANT(uint64_t, default, multiplier, 6364136223846793005ULL)
160 PCG_DEFINE_CONSTANT(uint64_t, default, increment, 1442695040888963407ULL)
161
162 PCG_DEFINE_CONSTANT(pcg128_t, default, multiplier,
163 PCG_128BIT_CONSTANT(2549297995355413924ULL,4865540595714422341ULL))
164 PCG_DEFINE_CONSTANT(pcg128_t, default, increment,
165 PCG_128BIT_CONSTANT(6364136223846793005ULL,1442695040888963407ULL))
166
167 /* Alternative (cheaper) multipliers for 128-bit */
168
169 template <typename T>
170 struct cheap_multiplier : public default_multiplier<T> {
171 // For most types just use the default.
172 };
173
174 template <>
175 struct cheap_multiplier<pcg128_t> {
multiplierarrow_vendored::pcg_detail::cheap_multiplier176 static constexpr uint64_t multiplier() {
177 return 0xda942042e4dd58b5ULL;
178 }
179 };
180
181
182 /*
183 * Each PCG generator is available in four variants, based on how it applies
184 * the additive constant for its underlying LCG; the variations are:
185 *
186 * single stream - all instances use the same fixed constant, thus
187 * the RNG always somewhere in same sequence
188 * mcg - adds zero, resulting in a single stream and reduced
189 * period
190 * specific stream - the constant can be changed at any time, selecting
191 * a different random sequence
192 * unique stream - the constant is based on the memory address of the
193 * object, thus every RNG has its own unique sequence
194 *
195 * This variation is provided though mixin classes which define a function
196 * value called increment() that returns the nesessary additive constant.
197 */
198
199
200
201 /*
202 * unique stream
203 */
204
205
206 template <typename itype>
207 class unique_stream {
208 protected:
209 static constexpr bool is_mcg = false;
210
211 // Is never called, but is provided for symmetry with specific_stream
set_stream(...)212 void set_stream(...)
213 {
214 abort();
215 }
216
217 public:
218 typedef itype state_type;
219
increment() const220 constexpr itype increment() const {
221 return itype(reinterpret_cast<uintptr_t>(this) | 1);
222 }
223
stream() const224 constexpr itype stream() const
225 {
226 return increment() >> 1;
227 }
228
229 static constexpr bool can_specify_stream = false;
230
streams_pow2()231 static constexpr size_t streams_pow2()
232 {
233 return (sizeof(itype) < sizeof(size_t) ? sizeof(itype)
234 : sizeof(size_t))*8 - 1u;
235 }
236
237 protected:
238 constexpr unique_stream() = default;
239 };
240
241
242 /*
243 * no stream (mcg)
244 */
245
246 template <typename itype>
247 class no_stream {
248 protected:
249 static constexpr bool is_mcg = true;
250
251 // Is never called, but is provided for symmetry with specific_stream
set_stream(...)252 void set_stream(...)
253 {
254 abort();
255 }
256
257 public:
258 typedef itype state_type;
259
increment()260 static constexpr itype increment() {
261 return 0;
262 }
263
264 static constexpr bool can_specify_stream = false;
265
streams_pow2()266 static constexpr size_t streams_pow2()
267 {
268 return 0u;
269 }
270
271 protected:
272 constexpr no_stream() = default;
273 };
274
275
276 /*
277 * single stream/sequence (oneseq)
278 */
279
280 template <typename itype>
281 class oneseq_stream : public default_increment<itype> {
282 protected:
283 static constexpr bool is_mcg = false;
284
285 // Is never called, but is provided for symmetry with specific_stream
set_stream(...)286 void set_stream(...)
287 {
288 abort();
289 }
290
291 public:
292 typedef itype state_type;
293
stream()294 static constexpr itype stream()
295 {
296 return default_increment<itype>::increment() >> 1;
297 }
298
299 static constexpr bool can_specify_stream = false;
300
streams_pow2()301 static constexpr size_t streams_pow2()
302 {
303 return 0u;
304 }
305
306 protected:
307 constexpr oneseq_stream() = default;
308 };
309
310
311 /*
312 * specific stream
313 */
314
315 template <typename itype>
316 class specific_stream {
317 protected:
318 static constexpr bool is_mcg = false;
319
320 itype inc_ = default_increment<itype>::increment();
321
322 public:
323 typedef itype state_type;
324 typedef itype stream_state;
325
increment() const326 constexpr itype increment() const {
327 return inc_;
328 }
329
stream()330 itype stream()
331 {
332 return inc_ >> 1;
333 }
334
set_stream(itype specific_seq)335 void set_stream(itype specific_seq)
336 {
337 inc_ = (specific_seq << 1) | 1;
338 }
339
340 static constexpr bool can_specify_stream = true;
341
streams_pow2()342 static constexpr size_t streams_pow2()
343 {
344 return (sizeof(itype)*8) - 1u;
345 }
346
347 protected:
348 specific_stream() = default;
349
specific_stream(itype specific_seq)350 specific_stream(itype specific_seq)
351 : inc_(itype(specific_seq << 1) | itype(1U))
352 {
353 // Nothing (else) to do.
354 }
355 };
356
357
358 /*
359 * This is where it all comes together. This function joins together three
360 * mixin classes which define
361 * - the LCG additive constant (the stream)
362 * - the LCG multiplier
363 * - the output function
364 * in addition, we specify the type of the LCG state, and the result type,
365 * and whether to use the pre-advance version of the state for the output
366 * (increasing instruction-level parallelism) or the post-advance version
367 * (reducing register pressure).
368 *
369 * Given the high level of parameterization, the code has to use some
370 * template-metaprogramming tricks to handle some of the suble variations
371 * involved.
372 */
373
374 template <typename xtype, typename itype,
375 typename output_mixin,
376 bool output_previous = true,
377 typename stream_mixin = oneseq_stream<itype>,
378 typename multiplier_mixin = default_multiplier<itype> >
379 class engine : protected output_mixin,
380 public stream_mixin,
381 protected multiplier_mixin {
382 protected:
383 itype state_;
384
385 struct can_specify_stream_tag {};
386 struct no_specifiable_stream_tag {};
387
388 using stream_mixin::increment;
389 using multiplier_mixin::multiplier;
390
391 public:
392 typedef xtype result_type;
393 typedef itype state_type;
394
period_pow2()395 static constexpr size_t period_pow2()
396 {
397 return sizeof(state_type)*8 - 2*stream_mixin::is_mcg;
398 }
399
400 // It would be nice to use std::numeric_limits for these, but
401 // we can't be sure that it'd be defined for the 128-bit types.
402
min()403 static constexpr result_type min()
404 {
405 return result_type(0UL);
406 }
407
max()408 static constexpr result_type max()
409 {
410 return result_type(~result_type(0UL));
411 }
412
413 protected:
bump(itype state)414 itype bump(itype state)
415 {
416 return state * multiplier() + increment();
417 }
418
base_generate()419 itype base_generate()
420 {
421 return state_ = bump(state_);
422 }
423
base_generate0()424 itype base_generate0()
425 {
426 itype old_state = state_;
427 state_ = bump(state_);
428 return old_state;
429 }
430
431 public:
operator ()()432 result_type operator()()
433 {
434 if (output_previous)
435 return this->output(base_generate0());
436 else
437 return this->output(base_generate());
438 }
439
operator ()(result_type upper_bound)440 result_type operator()(result_type upper_bound)
441 {
442 return bounded_rand(*this, upper_bound);
443 }
444
445 protected:
446 static itype advance(itype state, itype delta,
447 itype cur_mult, itype cur_plus);
448
449 static itype distance(itype cur_state, itype newstate, itype cur_mult,
450 itype cur_plus, itype mask = ~itype(0U));
451
distance(itype newstate,itype mask=itype (~itype (0U))) const452 itype distance(itype newstate, itype mask = itype(~itype(0U))) const
453 {
454 return distance(state_, newstate, multiplier(), increment(), mask);
455 }
456
457 public:
advance(itype delta)458 void advance(itype delta)
459 {
460 state_ = advance(state_, delta, this->multiplier(), this->increment());
461 }
462
backstep(itype delta)463 void backstep(itype delta)
464 {
465 advance(-delta);
466 }
467
discard(itype delta)468 void discard(itype delta)
469 {
470 advance(delta);
471 }
472
wrapped()473 bool wrapped()
474 {
475 if (stream_mixin::is_mcg) {
476 // For MCGs, the low order two bits never change. In this
477 // implementation, we keep them fixed at 3 to make this test
478 // easier.
479 return state_ == 3;
480 } else {
481 return state_ == 0;
482 }
483 }
484
engine(itype state=itype (0xcafef00dd15ea5e5ULL))485 engine(itype state = itype(0xcafef00dd15ea5e5ULL))
486 : state_(this->is_mcg ? state|state_type(3U)
487 : bump(state + this->increment()))
488 {
489 // Nothing else to do.
490 }
491
492 // This function may or may not exist. It thus has to be a template
493 // to use SFINAE; users don't have to worry about its template-ness.
494
495 template <typename sm = stream_mixin>
engine(itype state,typename sm::stream_state stream_seed)496 engine(itype state, typename sm::stream_state stream_seed)
497 : stream_mixin(stream_seed),
498 state_(this->is_mcg ? state|state_type(3U)
499 : bump(state + this->increment()))
500 {
501 // Nothing else to do.
502 }
503
504 template<typename SeedSeq>
engine(SeedSeq && seedSeq,typename std::enable_if<!stream_mixin::can_specify_stream &&!std::is_convertible<SeedSeq,itype>::value &&!std::is_convertible<SeedSeq,engine>::value,no_specifiable_stream_tag>::type={})505 engine(SeedSeq&& seedSeq, typename std::enable_if<
506 !stream_mixin::can_specify_stream
507 && !std::is_convertible<SeedSeq, itype>::value
508 && !std::is_convertible<SeedSeq, engine>::value,
509 no_specifiable_stream_tag>::type = {})
510 : engine(generate_one<itype>(std::forward<SeedSeq>(seedSeq)))
511 {
512 // Nothing else to do.
513 }
514
515 template<typename SeedSeq>
engine(SeedSeq && seedSeq,typename std::enable_if<stream_mixin::can_specify_stream &&!std::is_convertible<SeedSeq,itype>::value &&!std::is_convertible<SeedSeq,engine>::value,can_specify_stream_tag>::type={})516 engine(SeedSeq&& seedSeq, typename std::enable_if<
517 stream_mixin::can_specify_stream
518 && !std::is_convertible<SeedSeq, itype>::value
519 && !std::is_convertible<SeedSeq, engine>::value,
520 can_specify_stream_tag>::type = {})
521 {
522 itype seeddata[2];
523 generate_to<2>(std::forward<SeedSeq>(seedSeq), seeddata);
524 seed(seeddata[1], seeddata[0]);
525 }
526
527
528 template<typename... Args>
seed(Args &&...args)529 void seed(Args&&... args)
530 {
531 new (this) engine(std::forward<Args>(args)...);
532 }
533
534 template <typename xtype1, typename itype1,
535 typename output_mixin1, bool output_previous1,
536 typename stream_mixin_lhs, typename multiplier_mixin_lhs,
537 typename stream_mixin_rhs, typename multiplier_mixin_rhs>
538 friend bool operator==(const engine<xtype1,itype1,
539 output_mixin1,output_previous1,
540 stream_mixin_lhs, multiplier_mixin_lhs>&,
541 const engine<xtype1,itype1,
542 output_mixin1,output_previous1,
543 stream_mixin_rhs, multiplier_mixin_rhs>&);
544
545 template <typename xtype1, typename itype1,
546 typename output_mixin1, bool output_previous1,
547 typename stream_mixin_lhs, typename multiplier_mixin_lhs,
548 typename stream_mixin_rhs, typename multiplier_mixin_rhs>
549 friend itype1 operator-(const engine<xtype1,itype1,
550 output_mixin1,output_previous1,
551 stream_mixin_lhs, multiplier_mixin_lhs>&,
552 const engine<xtype1,itype1,
553 output_mixin1,output_previous1,
554 stream_mixin_rhs, multiplier_mixin_rhs>&);
555
556 template <typename CharT, typename Traits,
557 typename xtype1, typename itype1,
558 typename output_mixin1, bool output_previous1,
559 typename stream_mixin1, typename multiplier_mixin1>
560 friend std::basic_ostream<CharT,Traits>&
561 operator<<(std::basic_ostream<CharT,Traits>& out,
562 const engine<xtype1,itype1,
563 output_mixin1,output_previous1,
564 stream_mixin1, multiplier_mixin1>&);
565
566 template <typename CharT, typename Traits,
567 typename xtype1, typename itype1,
568 typename output_mixin1, bool output_previous1,
569 typename stream_mixin1, typename multiplier_mixin1>
570 friend std::basic_istream<CharT,Traits>&
571 operator>>(std::basic_istream<CharT,Traits>& in,
572 engine<xtype1, itype1,
573 output_mixin1, output_previous1,
574 stream_mixin1, multiplier_mixin1>& rng);
575 };
576
577 template <typename CharT, typename Traits,
578 typename xtype, typename itype,
579 typename output_mixin, bool output_previous,
580 typename stream_mixin, typename multiplier_mixin>
581 std::basic_ostream<CharT,Traits>&
operator <<(std::basic_ostream<CharT,Traits> & out,const engine<xtype,itype,output_mixin,output_previous,stream_mixin,multiplier_mixin> & rng)582 operator<<(std::basic_ostream<CharT,Traits>& out,
583 const engine<xtype,itype,
584 output_mixin,output_previous,
585 stream_mixin, multiplier_mixin>& rng)
586 {
587 using pcg_extras::operator<<;
588
589 auto orig_flags = out.flags(std::ios_base::dec | std::ios_base::left);
590 auto space = out.widen(' ');
591 auto orig_fill = out.fill();
592
593 out << rng.multiplier() << space
594 << rng.increment() << space
595 << rng.state_;
596
597 out.flags(orig_flags);
598 out.fill(orig_fill);
599 return out;
600 }
601
602
603 template <typename CharT, typename Traits,
604 typename xtype, typename itype,
605 typename output_mixin, bool output_previous,
606 typename stream_mixin, typename multiplier_mixin>
607 std::basic_istream<CharT,Traits>&
operator >>(std::basic_istream<CharT,Traits> & in,engine<xtype,itype,output_mixin,output_previous,stream_mixin,multiplier_mixin> & rng)608 operator>>(std::basic_istream<CharT,Traits>& in,
609 engine<xtype,itype,
610 output_mixin,output_previous,
611 stream_mixin, multiplier_mixin>& rng)
612 {
613 using pcg_extras::operator>>;
614
615 auto orig_flags = in.flags(std::ios_base::dec | std::ios_base::skipws);
616
617 itype multiplier, increment, state;
618 in >> multiplier >> increment >> state;
619
620 if (!in.fail()) {
621 bool good = true;
622 if (multiplier != rng.multiplier()) {
623 good = false;
624 } else if (rng.can_specify_stream) {
625 rng.set_stream(increment >> 1);
626 } else if (increment != rng.increment()) {
627 good = false;
628 }
629 if (good) {
630 rng.state_ = state;
631 } else {
632 in.clear(std::ios::failbit);
633 }
634 }
635
636 in.flags(orig_flags);
637 return in;
638 }
639
640
641 template <typename xtype, typename itype,
642 typename output_mixin, bool output_previous,
643 typename stream_mixin, typename multiplier_mixin>
644 itype engine<xtype,itype,output_mixin,output_previous,stream_mixin,
645 multiplier_mixin>::advance(
646 itype state, itype delta, itype cur_mult, itype cur_plus)
647 {
648 // The method used here is based on Brown, "Random Number Generation
649 // with Arbitrary Stride,", Transactions of the American Nuclear
650 // Society (Nov. 1994). The algorithm is very similar to fast
651 // exponentiation.
652 //
653 // Even though delta is an unsigned integer, we can pass a
654 // signed integer to go backwards, it just goes "the long way round".
655
656 constexpr itype ZERO = 0u; // itype may be a non-trivial types, so
657 constexpr itype ONE = 1u; // we define some ugly constants.
658 itype acc_mult = 1;
659 itype acc_plus = 0;
660 while (delta > ZERO) {
661 if (delta & ONE) {
662 acc_mult *= cur_mult;
663 acc_plus = acc_plus*cur_mult + cur_plus;
664 }
665 cur_plus = (cur_mult+ONE)*cur_plus;
666 cur_mult *= cur_mult;
667 delta >>= 1;
668 }
669 return acc_mult * state + acc_plus;
670 }
671
672 template <typename xtype, typename itype,
673 typename output_mixin, bool output_previous,
674 typename stream_mixin, typename multiplier_mixin>
675 itype engine<xtype,itype,output_mixin,output_previous,stream_mixin,
676 multiplier_mixin>::distance(
677 itype cur_state, itype newstate, itype cur_mult, itype cur_plus, itype mask)
678 {
679 constexpr itype ONE = 1u; // itype could be weird, so use constant
680 bool is_mcg = cur_plus == itype(0);
681 itype the_bit = is_mcg ? itype(4u) : itype(1u);
682 itype distance = 0u;
683 while ((cur_state & mask) != (newstate & mask)) {
684 if ((cur_state & the_bit) != (newstate & the_bit)) {
685 cur_state = cur_state * cur_mult + cur_plus;
686 distance |= the_bit;
687 }
688 assert((cur_state & the_bit) == (newstate & the_bit));
689 the_bit <<= 1;
690 cur_plus = (cur_mult+ONE)*cur_plus;
691 cur_mult *= cur_mult;
692 }
693 return is_mcg ? distance >> 2 : distance;
694 }
695
696 template <typename xtype, typename itype,
697 typename output_mixin, bool output_previous,
698 typename stream_mixin_lhs, typename multiplier_mixin_lhs,
699 typename stream_mixin_rhs, typename multiplier_mixin_rhs>
700 itype operator-(const engine<xtype,itype,
701 output_mixin,output_previous,
702 stream_mixin_lhs, multiplier_mixin_lhs>& lhs,
703 const engine<xtype,itype,
704 output_mixin,output_previous,
705 stream_mixin_rhs, multiplier_mixin_rhs>& rhs)
706 {
707 static_assert(
708 std::is_same<stream_mixin_lhs, stream_mixin_rhs>::value &&
709 std::is_same<multiplier_mixin_lhs, multiplier_mixin_rhs>::value,
710 "Incomparable generators");
711 if (lhs.increment() == rhs.increment()) {
712 return rhs.distance(lhs.state_);
713 } else {
714 constexpr itype ONE = 1u;
715 itype lhs_diff = lhs.increment() + (lhs.multiplier()-ONE) * lhs.state_;
716 itype rhs_diff = rhs.increment() + (rhs.multiplier()-ONE) * rhs.state_;
717 if ((lhs_diff & itype(3u)) != (rhs_diff & itype(3u))) {
718 rhs_diff = -rhs_diff;
719 }
720 return rhs.distance(rhs_diff, lhs_diff, rhs.multiplier(), itype(0u));
721 }
722 }
723
724
725 template <typename xtype, typename itype,
726 typename output_mixin, bool output_previous,
727 typename stream_mixin_lhs, typename multiplier_mixin_lhs,
728 typename stream_mixin_rhs, typename multiplier_mixin_rhs>
operator ==(const engine<xtype,itype,output_mixin,output_previous,stream_mixin_lhs,multiplier_mixin_lhs> & lhs,const engine<xtype,itype,output_mixin,output_previous,stream_mixin_rhs,multiplier_mixin_rhs> & rhs)729 bool operator==(const engine<xtype,itype,
730 output_mixin,output_previous,
731 stream_mixin_lhs, multiplier_mixin_lhs>& lhs,
732 const engine<xtype,itype,
733 output_mixin,output_previous,
734 stream_mixin_rhs, multiplier_mixin_rhs>& rhs)
735 {
736 return (lhs.multiplier() == rhs.multiplier())
737 && (lhs.increment() == rhs.increment())
738 && (lhs.state_ == rhs.state_);
739 }
740
741 template <typename xtype, typename itype,
742 typename output_mixin, bool output_previous,
743 typename stream_mixin_lhs, typename multiplier_mixin_lhs,
744 typename stream_mixin_rhs, typename multiplier_mixin_rhs>
operator !=(const engine<xtype,itype,output_mixin,output_previous,stream_mixin_lhs,multiplier_mixin_lhs> & lhs,const engine<xtype,itype,output_mixin,output_previous,stream_mixin_rhs,multiplier_mixin_rhs> & rhs)745 inline bool operator!=(const engine<xtype,itype,
746 output_mixin,output_previous,
747 stream_mixin_lhs, multiplier_mixin_lhs>& lhs,
748 const engine<xtype,itype,
749 output_mixin,output_previous,
750 stream_mixin_rhs, multiplier_mixin_rhs>& rhs)
751 {
752 return !operator==(lhs,rhs);
753 }
754
755
756 template <typename xtype, typename itype,
757 template<typename XT,typename IT> class output_mixin,
758 bool output_previous = (sizeof(itype) <= 8),
759 template<typename IT> class multiplier_mixin = default_multiplier>
760 using oneseq_base = engine<xtype, itype,
761 output_mixin<xtype, itype>, output_previous,
762 oneseq_stream<itype>,
763 multiplier_mixin<itype> >;
764
765 template <typename xtype, typename itype,
766 template<typename XT,typename IT> class output_mixin,
767 bool output_previous = (sizeof(itype) <= 8),
768 template<typename IT> class multiplier_mixin = default_multiplier>
769 using unique_base = engine<xtype, itype,
770 output_mixin<xtype, itype>, output_previous,
771 unique_stream<itype>,
772 multiplier_mixin<itype> >;
773
774 template <typename xtype, typename itype,
775 template<typename XT,typename IT> class output_mixin,
776 bool output_previous = (sizeof(itype) <= 8),
777 template<typename IT> class multiplier_mixin = default_multiplier>
778 using setseq_base = engine<xtype, itype,
779 output_mixin<xtype, itype>, output_previous,
780 specific_stream<itype>,
781 multiplier_mixin<itype> >;
782
783 template <typename xtype, typename itype,
784 template<typename XT,typename IT> class output_mixin,
785 bool output_previous = (sizeof(itype) <= 8),
786 template<typename IT> class multiplier_mixin = default_multiplier>
787 using mcg_base = engine<xtype, itype,
788 output_mixin<xtype, itype>, output_previous,
789 no_stream<itype>,
790 multiplier_mixin<itype> >;
791
792 /*
793 * OUTPUT FUNCTIONS.
794 *
795 * These are the core of the PCG generation scheme. They specify how to
796 * turn the base LCG's internal state into the output value of the final
797 * generator.
798 *
799 * They're implemented as mixin classes.
800 *
801 * All of the classes have code that is written to allow it to be applied
802 * at *arbitrary* bit sizes, although in practice they'll only be used at
803 * standard sizes supported by C++.
804 */
805
806 /*
807 * XSH RS -- high xorshift, followed by a random shift
808 *
809 * Fast. A good performer.
810 */
811
812 template <typename xtype, typename itype>
813 struct xsh_rs_mixin {
outputarrow_vendored::pcg_detail::xsh_rs_mixin814 static xtype output(itype internal)
815 {
816 constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
817 constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype) * 8);
818 constexpr bitcount_t sparebits = bits - xtypebits;
819 constexpr bitcount_t opbits =
820 sparebits-5 >= 64 ? 5
821 : sparebits-4 >= 32 ? 4
822 : sparebits-3 >= 16 ? 3
823 : sparebits-2 >= 4 ? 2
824 : sparebits-1 >= 1 ? 1
825 : 0;
826 constexpr bitcount_t mask = (1 << opbits) - 1;
827 constexpr bitcount_t maxrandshift = mask;
828 constexpr bitcount_t topspare = opbits;
829 constexpr bitcount_t bottomspare = sparebits - topspare;
830 constexpr bitcount_t xshift = topspare + (xtypebits+maxrandshift)/2;
831 bitcount_t rshift =
832 opbits ? bitcount_t(internal >> (bits - opbits)) & mask : 0;
833 internal ^= internal >> xshift;
834 xtype result = xtype(internal >> (bottomspare - maxrandshift + rshift));
835 return result;
836 }
837 };
838
839 /*
840 * XSH RR -- high xorshift, followed by a random rotate
841 *
842 * Fast. A good performer. Slightly better statistically than XSH RS.
843 */
844
845 template <typename xtype, typename itype>
846 struct xsh_rr_mixin {
outputarrow_vendored::pcg_detail::xsh_rr_mixin847 static xtype output(itype internal)
848 {
849 constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
850 constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype)*8);
851 constexpr bitcount_t sparebits = bits - xtypebits;
852 constexpr bitcount_t wantedopbits =
853 xtypebits >= 128 ? 7
854 : xtypebits >= 64 ? 6
855 : xtypebits >= 32 ? 5
856 : xtypebits >= 16 ? 4
857 : 3;
858 constexpr bitcount_t opbits =
859 sparebits >= wantedopbits ? wantedopbits
860 : sparebits;
861 constexpr bitcount_t amplifier = wantedopbits - opbits;
862 constexpr bitcount_t mask = (1 << opbits) - 1;
863 constexpr bitcount_t topspare = opbits;
864 constexpr bitcount_t bottomspare = sparebits - topspare;
865 constexpr bitcount_t xshift = (topspare + xtypebits)/2;
866 bitcount_t rot = opbits ? bitcount_t(internal >> (bits - opbits)) & mask
867 : 0;
868 bitcount_t amprot = (rot << amplifier) & mask;
869 internal ^= internal >> xshift;
870 xtype result = xtype(internal >> bottomspare);
871 result = rotr(result, amprot);
872 return result;
873 }
874 };
875
876 /*
877 * RXS -- random xorshift
878 */
879
880 template <typename xtype, typename itype>
881 struct rxs_mixin {
output_rxsarrow_vendored::pcg_detail::rxs_mixin882 static xtype output_rxs(itype internal)
883 {
884 constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
885 constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype)*8);
886 constexpr bitcount_t shift = bits - xtypebits;
887 constexpr bitcount_t extrashift = (xtypebits - shift)/2;
888 bitcount_t rshift = shift > 64+8 ? (internal >> (bits - 6)) & 63
889 : shift > 32+4 ? (internal >> (bits - 5)) & 31
890 : shift > 16+2 ? (internal >> (bits - 4)) & 15
891 : shift > 8+1 ? (internal >> (bits - 3)) & 7
892 : shift > 4+1 ? (internal >> (bits - 2)) & 3
893 : shift > 2+1 ? (internal >> (bits - 1)) & 1
894 : 0;
895 internal ^= internal >> (shift + extrashift - rshift);
896 xtype result = internal >> rshift;
897 return result;
898 }
899 };
900
901 /*
902 * RXS M XS -- random xorshift, mcg multiply, fixed xorshift
903 *
904 * The most statistically powerful generator, but all those steps
905 * make it slower than some of the others. We give it the rottenest jobs.
906 *
907 * Because it's usually used in contexts where the state type and the
908 * result type are the same, it is a permutation and is thus invertable.
909 * We thus provide a function to invert it. This function is used to
910 * for the "inside out" generator used by the extended generator.
911 */
912
913 /* Defined type-based concepts for the multiplication step. They're actually
914 * all derived by truncating the 128-bit, which was computed to be a good
915 * "universal" constant.
916 */
917
918 template <typename T>
919 struct mcg_multiplier {
920 // Not defined for an arbitrary type
921 };
922
923 template <typename T>
924 struct mcg_unmultiplier {
925 // Not defined for an arbitrary type
926 };
927
928 PCG_DEFINE_CONSTANT(uint8_t, mcg, multiplier, 217U)
929 PCG_DEFINE_CONSTANT(uint8_t, mcg, unmultiplier, 105U)
930
931 PCG_DEFINE_CONSTANT(uint16_t, mcg, multiplier, 62169U)
932 PCG_DEFINE_CONSTANT(uint16_t, mcg, unmultiplier, 28009U)
933
934 PCG_DEFINE_CONSTANT(uint32_t, mcg, multiplier, 277803737U)
935 PCG_DEFINE_CONSTANT(uint32_t, mcg, unmultiplier, 2897767785U)
936
937 PCG_DEFINE_CONSTANT(uint64_t, mcg, multiplier, 12605985483714917081ULL)
938 PCG_DEFINE_CONSTANT(uint64_t, mcg, unmultiplier, 15009553638781119849ULL)
939
940 PCG_DEFINE_CONSTANT(pcg128_t, mcg, multiplier,
941 PCG_128BIT_CONSTANT(17766728186571221404ULL, 12605985483714917081ULL))
942 PCG_DEFINE_CONSTANT(pcg128_t, mcg, unmultiplier,
943 PCG_128BIT_CONSTANT(14422606686972528997ULL, 15009553638781119849ULL))
944
945
946 template <typename xtype, typename itype>
947 struct rxs_m_xs_mixin {
outputarrow_vendored::pcg_detail::rxs_m_xs_mixin948 static xtype output(itype internal)
949 {
950 constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype) * 8);
951 constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
952 constexpr bitcount_t opbits = xtypebits >= 128 ? 6
953 : xtypebits >= 64 ? 5
954 : xtypebits >= 32 ? 4
955 : xtypebits >= 16 ? 3
956 : 2;
957 constexpr bitcount_t shift = bits - xtypebits;
958 constexpr bitcount_t mask = (1 << opbits) - 1;
959 bitcount_t rshift =
960 opbits ? bitcount_t(internal >> (bits - opbits)) & mask : 0;
961 internal ^= internal >> (opbits + rshift);
962 internal *= mcg_multiplier<itype>::multiplier();
963 xtype result = internal >> shift;
964 result ^= result >> ((2U*xtypebits+2U)/3U);
965 return result;
966 }
967
unoutputarrow_vendored::pcg_detail::rxs_m_xs_mixin968 static itype unoutput(itype internal)
969 {
970 constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
971 constexpr bitcount_t opbits = bits >= 128 ? 6
972 : bits >= 64 ? 5
973 : bits >= 32 ? 4
974 : bits >= 16 ? 3
975 : 2;
976 constexpr bitcount_t mask = (1 << opbits) - 1;
977
978 internal = unxorshift(internal, bits, (2U*bits+2U)/3U);
979
980 internal *= mcg_unmultiplier<itype>::unmultiplier();
981
982 bitcount_t rshift = opbits ? (internal >> (bits - opbits)) & mask : 0;
983 internal = unxorshift(internal, bits, opbits + rshift);
984
985 return internal;
986 }
987 };
988
989
990 /*
991 * RXS M -- random xorshift, mcg multiply
992 */
993
994 template <typename xtype, typename itype>
995 struct rxs_m_mixin {
outputarrow_vendored::pcg_detail::rxs_m_mixin996 static xtype output(itype internal)
997 {
998 constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype) * 8);
999 constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
1000 constexpr bitcount_t opbits = xtypebits >= 128 ? 6
1001 : xtypebits >= 64 ? 5
1002 : xtypebits >= 32 ? 4
1003 : xtypebits >= 16 ? 3
1004 : 2;
1005 constexpr bitcount_t shift = bits - xtypebits;
1006 constexpr bitcount_t mask = (1 << opbits) - 1;
1007 bitcount_t rshift = opbits ? (internal >> (bits - opbits)) & mask : 0;
1008 internal ^= internal >> (opbits + rshift);
1009 internal *= mcg_multiplier<itype>::multiplier();
1010 xtype result = internal >> shift;
1011 return result;
1012 }
1013 };
1014
1015
1016 /*
1017 * DXSM -- double xorshift multiply
1018 *
1019 * This is a new, more powerful output permutation (added in 2019). It's
1020 * a more comprehensive scrambling than RXS M, but runs faster on 128-bit
1021 * types. Although primarily intended for use at large sizes, also works
1022 * at smaller sizes as well.
1023 *
1024 * This permutation is similar to xorshift multiply hash functions, except
1025 * that one of the multipliers is the LCG multiplier (to avoid needing to
1026 * have a second constant) and the other is based on the low-order bits.
1027 * This latter aspect means that the scrambling applied to the high bits
1028 * depends on the low bits, and makes it (to my eye) impractical to back
1029 * out the permutation without having the low-order bits.
1030 */
1031
1032 template <typename xtype, typename itype>
1033 struct dxsm_mixin {
outputarrow_vendored::pcg_detail::dxsm_mixin1034 inline xtype output(itype internal)
1035 {
1036 constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype) * 8);
1037 constexpr bitcount_t itypebits = bitcount_t(sizeof(itype) * 8);
1038 static_assert(xtypebits <= itypebits/2,
1039 "Output type must be half the size of the state type.");
1040
1041 xtype hi = xtype(internal >> (itypebits - xtypebits));
1042 xtype lo = xtype(internal);
1043
1044 lo |= 1;
1045 hi ^= hi >> (xtypebits/2);
1046 hi *= xtype(cheap_multiplier<itype>::multiplier());
1047 hi ^= hi >> (3*(xtypebits/4));
1048 hi *= lo;
1049 return hi;
1050 }
1051 };
1052
1053
1054 /*
1055 * XSL RR -- fixed xorshift (to low bits), random rotate
1056 *
1057 * Useful for 128-bit types that are split across two CPU registers.
1058 */
1059
1060 template <typename xtype, typename itype>
1061 struct xsl_rr_mixin {
outputarrow_vendored::pcg_detail::xsl_rr_mixin1062 static xtype output(itype internal)
1063 {
1064 constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype) * 8);
1065 constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
1066 constexpr bitcount_t sparebits = bits - xtypebits;
1067 constexpr bitcount_t wantedopbits = xtypebits >= 128 ? 7
1068 : xtypebits >= 64 ? 6
1069 : xtypebits >= 32 ? 5
1070 : xtypebits >= 16 ? 4
1071 : 3;
1072 constexpr bitcount_t opbits = sparebits >= wantedopbits ? wantedopbits
1073 : sparebits;
1074 constexpr bitcount_t amplifier = wantedopbits - opbits;
1075 constexpr bitcount_t mask = (1 << opbits) - 1;
1076 constexpr bitcount_t topspare = sparebits;
1077 constexpr bitcount_t bottomspare = sparebits - topspare;
1078 constexpr bitcount_t xshift = (topspare + xtypebits) / 2;
1079
1080 bitcount_t rot =
1081 opbits ? bitcount_t(internal >> (bits - opbits)) & mask : 0;
1082 bitcount_t amprot = (rot << amplifier) & mask;
1083 internal ^= internal >> xshift;
1084 xtype result = xtype(internal >> bottomspare);
1085 result = rotr(result, amprot);
1086 return result;
1087 }
1088 };
1089
1090
1091 /*
1092 * XSL RR RR -- fixed xorshift (to low bits), random rotate (both parts)
1093 *
1094 * Useful for 128-bit types that are split across two CPU registers.
1095 * If you really want an invertable 128-bit RNG, I guess this is the one.
1096 */
1097
1098 template <typename T> struct halfsize_trait {};
1099 template <> struct halfsize_trait<pcg128_t> { typedef uint64_t type; };
1100 template <> struct halfsize_trait<uint64_t> { typedef uint32_t type; };
1101 template <> struct halfsize_trait<uint32_t> { typedef uint16_t type; };
1102 template <> struct halfsize_trait<uint16_t> { typedef uint8_t type; };
1103
1104 template <typename xtype, typename itype>
1105 struct xsl_rr_rr_mixin {
1106 typedef typename halfsize_trait<itype>::type htype;
1107
outputarrow_vendored::pcg_detail::xsl_rr_rr_mixin1108 static itype output(itype internal)
1109 {
1110 constexpr bitcount_t htypebits = bitcount_t(sizeof(htype) * 8);
1111 constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
1112 constexpr bitcount_t sparebits = bits - htypebits;
1113 constexpr bitcount_t wantedopbits = htypebits >= 128 ? 7
1114 : htypebits >= 64 ? 6
1115 : htypebits >= 32 ? 5
1116 : htypebits >= 16 ? 4
1117 : 3;
1118 constexpr bitcount_t opbits = sparebits >= wantedopbits ? wantedopbits
1119 : sparebits;
1120 constexpr bitcount_t amplifier = wantedopbits - opbits;
1121 constexpr bitcount_t mask = (1 << opbits) - 1;
1122 constexpr bitcount_t topspare = sparebits;
1123 constexpr bitcount_t xshift = (topspare + htypebits) / 2;
1124
1125 bitcount_t rot =
1126 opbits ? bitcount_t(internal >> (bits - opbits)) & mask : 0;
1127 bitcount_t amprot = (rot << amplifier) & mask;
1128 internal ^= internal >> xshift;
1129 htype lowbits = htype(internal);
1130 lowbits = rotr(lowbits, amprot);
1131 htype highbits = htype(internal >> topspare);
1132 bitcount_t rot2 = lowbits & mask;
1133 bitcount_t amprot2 = (rot2 << amplifier) & mask;
1134 highbits = rotr(highbits, amprot2);
1135 return (itype(highbits) << topspare) ^ itype(lowbits);
1136 }
1137 };
1138
1139
1140 /*
1141 * XSH -- fixed xorshift (to high bits)
1142 *
1143 * You shouldn't use this at 64-bits or less.
1144 */
1145
1146 template <typename xtype, typename itype>
1147 struct xsh_mixin {
outputarrow_vendored::pcg_detail::xsh_mixin1148 static xtype output(itype internal)
1149 {
1150 constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype) * 8);
1151 constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
1152 constexpr bitcount_t sparebits = bits - xtypebits;
1153 constexpr bitcount_t topspare = 0;
1154 constexpr bitcount_t bottomspare = sparebits - topspare;
1155 constexpr bitcount_t xshift = (topspare + xtypebits) / 2;
1156
1157 internal ^= internal >> xshift;
1158 xtype result = internal >> bottomspare;
1159 return result;
1160 }
1161 };
1162
1163 /*
1164 * XSL -- fixed xorshift (to low bits)
1165 *
1166 * You shouldn't use this at 64-bits or less.
1167 */
1168
1169 template <typename xtype, typename itype>
1170 struct xsl_mixin {
outputarrow_vendored::pcg_detail::xsl_mixin1171 inline xtype output(itype internal)
1172 {
1173 constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype) * 8);
1174 constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
1175 constexpr bitcount_t sparebits = bits - xtypebits;
1176 constexpr bitcount_t topspare = sparebits;
1177 constexpr bitcount_t bottomspare = sparebits - topspare;
1178 constexpr bitcount_t xshift = (topspare + xtypebits) / 2;
1179
1180 internal ^= internal >> xshift;
1181 xtype result = internal >> bottomspare;
1182 return result;
1183 }
1184 };
1185
1186
1187 /* ---- End of Output Functions ---- */
1188
1189
1190 template <typename baseclass>
1191 struct inside_out : private baseclass {
1192 inside_out() = delete;
1193
1194 typedef typename baseclass::result_type result_type;
1195 typedef typename baseclass::state_type state_type;
1196 static_assert(sizeof(result_type) == sizeof(state_type),
1197 "Require a RNG whose output function is a permutation");
1198
external_steparrow_vendored::pcg_detail::inside_out1199 static bool external_step(result_type& randval, size_t i)
1200 {
1201 state_type state = baseclass::unoutput(randval);
1202 state = state * baseclass::multiplier() + baseclass::increment()
1203 + state_type(i*2);
1204 result_type result = baseclass::output(state);
1205 randval = result;
1206 state_type zero =
1207 baseclass::is_mcg ? state & state_type(3U) : state_type(0U);
1208 return result == zero;
1209 }
1210
external_advancearrow_vendored::pcg_detail::inside_out1211 static bool external_advance(result_type& randval, size_t i,
1212 result_type delta, bool forwards = true)
1213 {
1214 state_type state = baseclass::unoutput(randval);
1215 state_type mult = baseclass::multiplier();
1216 state_type inc = baseclass::increment() + state_type(i*2);
1217 state_type zero =
1218 baseclass::is_mcg ? state & state_type(3U) : state_type(0U);
1219 state_type dist_to_zero = baseclass::distance(state, zero, mult, inc);
1220 bool crosses_zero =
1221 forwards ? dist_to_zero <= delta
1222 : (-dist_to_zero) <= delta;
1223 if (!forwards)
1224 delta = -delta;
1225 state = baseclass::advance(state, delta, mult, inc);
1226 randval = baseclass::output(state);
1227 return crosses_zero;
1228 }
1229 };
1230
1231
1232 template <bitcount_t table_pow2, bitcount_t advance_pow2, typename baseclass, typename extvalclass, bool kdd = true>
1233 class extended : public baseclass {
1234 public:
1235 typedef typename baseclass::state_type state_type;
1236 typedef typename baseclass::result_type result_type;
1237 typedef inside_out<extvalclass> insideout;
1238
1239 private:
1240 static constexpr bitcount_t rtypebits = sizeof(result_type)*8;
1241 static constexpr bitcount_t stypebits = sizeof(state_type)*8;
1242
1243 static constexpr bitcount_t tick_limit_pow2 = 64U;
1244
1245 static constexpr size_t table_size = 1UL << table_pow2;
1246 static constexpr size_t table_shift = stypebits - table_pow2;
1247 static constexpr state_type table_mask =
1248 (state_type(1U) << table_pow2) - state_type(1U);
1249
1250 static constexpr bool may_tick =
1251 (advance_pow2 < stypebits) && (advance_pow2 < tick_limit_pow2);
1252 static constexpr size_t tick_shift = stypebits - advance_pow2;
1253 static constexpr state_type tick_mask =
1254 may_tick ? state_type(
1255 (uint64_t(1) << (advance_pow2*may_tick)) - 1)
1256 // ^-- stupidity to appease GCC warnings
1257 : ~state_type(0U);
1258
1259 static constexpr bool may_tock = stypebits < tick_limit_pow2;
1260
1261 result_type data_[table_size];
1262
1263 PCG_NOINLINE void advance_table();
1264
1265 PCG_NOINLINE void advance_table(state_type delta, bool isForwards = true);
1266
get_extended_value()1267 result_type& get_extended_value()
1268 {
1269 state_type state = this->state_;
1270 if (kdd && baseclass::is_mcg) {
1271 // The low order bits of an MCG are constant, so drop them.
1272 state >>= 2;
1273 }
1274 size_t index = kdd ? state & table_mask
1275 : state >> table_shift;
1276
1277 if (may_tick) {
1278 bool tick = kdd ? (state & tick_mask) == state_type(0u)
1279 : (state >> tick_shift) == state_type(0u);
1280 if (tick)
1281 advance_table();
1282 }
1283 if (may_tock) {
1284 bool tock = state == state_type(0u);
1285 if (tock)
1286 advance_table();
1287 }
1288 return data_[index];
1289 }
1290
1291 public:
period_pow2()1292 static constexpr size_t period_pow2()
1293 {
1294 return baseclass::period_pow2() + table_size*extvalclass::period_pow2();
1295 }
1296
operator ()()1297 PCG_ALWAYS_INLINE result_type operator()()
1298 {
1299 result_type rhs = get_extended_value();
1300 result_type lhs = this->baseclass::operator()();
1301 return lhs ^ rhs;
1302 }
1303
operator ()(result_type upper_bound)1304 result_type operator()(result_type upper_bound)
1305 {
1306 return bounded_rand(*this, upper_bound);
1307 }
1308
set(result_type wanted)1309 void set(result_type wanted)
1310 {
1311 result_type& rhs = get_extended_value();
1312 result_type lhs = this->baseclass::operator()();
1313 rhs = lhs ^ wanted;
1314 }
1315
1316 void advance(state_type distance, bool forwards = true);
1317
backstep(state_type distance)1318 void backstep(state_type distance)
1319 {
1320 advance(distance, false);
1321 }
1322
extended(const result_type * data)1323 extended(const result_type* data)
1324 : baseclass()
1325 {
1326 datainit(data);
1327 }
1328
extended(const result_type * data,state_type seed)1329 extended(const result_type* data, state_type seed)
1330 : baseclass(seed)
1331 {
1332 datainit(data);
1333 }
1334
1335 // This function may or may not exist. It thus has to be a template
1336 // to use SFINAE; users don't have to worry about its template-ness.
1337
1338 template <typename bc = baseclass>
extended(const result_type * data,state_type seed,typename bc::stream_state stream_seed)1339 extended(const result_type* data, state_type seed,
1340 typename bc::stream_state stream_seed)
1341 : baseclass(seed, stream_seed)
1342 {
1343 datainit(data);
1344 }
1345
extended()1346 extended()
1347 : baseclass()
1348 {
1349 selfinit();
1350 }
1351
extended(state_type seed)1352 extended(state_type seed)
1353 : baseclass(seed)
1354 {
1355 selfinit();
1356 }
1357
1358 // This function may or may not exist. It thus has to be a template
1359 // to use SFINAE; users don't have to worry about its template-ness.
1360
1361 template <typename bc = baseclass>
extended(state_type seed,typename bc::stream_state stream_seed)1362 extended(state_type seed, typename bc::stream_state stream_seed)
1363 : baseclass(seed, stream_seed)
1364 {
1365 selfinit();
1366 }
1367
1368 private:
1369 void selfinit();
1370 void datainit(const result_type* data);
1371
1372 public:
1373
1374 template<typename SeedSeq, typename = typename std::enable_if<
1375 !std::is_convertible<SeedSeq, result_type>::value
1376 && !std::is_convertible<SeedSeq, extended>::value>::type>
extended(SeedSeq && seedSeq)1377 extended(SeedSeq&& seedSeq)
1378 : baseclass(seedSeq)
1379 {
1380 generate_to<table_size>(seedSeq, data_);
1381 }
1382
1383 template<typename... Args>
seed(Args &&...args)1384 void seed(Args&&... args)
1385 {
1386 new (this) extended(std::forward<Args>(args)...);
1387 }
1388
1389 template <bitcount_t table_pow2_, bitcount_t advance_pow2_,
1390 typename baseclass_, typename extvalclass_, bool kdd_>
1391 friend bool operator==(const extended<table_pow2_, advance_pow2_,
1392 baseclass_, extvalclass_, kdd_>&,
1393 const extended<table_pow2_, advance_pow2_,
1394 baseclass_, extvalclass_, kdd_>&);
1395
1396 template <typename CharT, typename Traits,
1397 bitcount_t table_pow2_, bitcount_t advance_pow2_,
1398 typename baseclass_, typename extvalclass_, bool kdd_>
1399 friend std::basic_ostream<CharT,Traits>&
1400 operator<<(std::basic_ostream<CharT,Traits>& out,
1401 const extended<table_pow2_, advance_pow2_,
1402 baseclass_, extvalclass_, kdd_>&);
1403
1404 template <typename CharT, typename Traits,
1405 bitcount_t table_pow2_, bitcount_t advance_pow2_,
1406 typename baseclass_, typename extvalclass_, bool kdd_>
1407 friend std::basic_istream<CharT,Traits>&
1408 operator>>(std::basic_istream<CharT,Traits>& in,
1409 extended<table_pow2_, advance_pow2_,
1410 baseclass_, extvalclass_, kdd_>&);
1411
1412 };
1413
1414
1415 template <bitcount_t table_pow2, bitcount_t advance_pow2,
1416 typename baseclass, typename extvalclass, bool kdd>
datainit(const result_type * data)1417 void extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd>::datainit(
1418 const result_type* data)
1419 {
1420 for (size_t i = 0; i < table_size; ++i)
1421 data_[i] = data[i];
1422 }
1423
1424 template <bitcount_t table_pow2, bitcount_t advance_pow2,
1425 typename baseclass, typename extvalclass, bool kdd>
selfinit()1426 void extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd>::selfinit()
1427 {
1428 // We need to fill the extended table with something, and we have
1429 // very little provided data, so we use the base generator to
1430 // produce values. Although not ideal (use a seed sequence, folks!),
1431 // unexpected correlations are mitigated by
1432 // - using XOR differences rather than the number directly
1433 // - the way the table is accessed, its values *won't* be accessed
1434 // in the same order the were written.
1435 // - any strange correlations would only be apparent if we
1436 // were to backstep the generator so that the base generator
1437 // was generating the same values again
1438 result_type lhs = baseclass::operator()();
1439 result_type rhs = baseclass::operator()();
1440 result_type xdiff = lhs - rhs;
1441 for (size_t i = 0; i < table_size; ++i) {
1442 data_[i] = baseclass::operator()() ^ xdiff;
1443 }
1444 }
1445
1446 template <bitcount_t table_pow2, bitcount_t advance_pow2,
1447 typename baseclass, typename extvalclass, bool kdd>
operator ==(const extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd> & lhs,const extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd> & rhs)1448 bool operator==(const extended<table_pow2, advance_pow2,
1449 baseclass, extvalclass, kdd>& lhs,
1450 const extended<table_pow2, advance_pow2,
1451 baseclass, extvalclass, kdd>& rhs)
1452 {
1453 auto& base_lhs = static_cast<const baseclass&>(lhs);
1454 auto& base_rhs = static_cast<const baseclass&>(rhs);
1455 return base_lhs == base_rhs
1456 && std::equal(
1457 std::begin(lhs.data_), std::end(lhs.data_),
1458 std::begin(rhs.data_)
1459 );
1460 }
1461
1462 template <bitcount_t table_pow2, bitcount_t advance_pow2,
1463 typename baseclass, typename extvalclass, bool kdd>
operator !=(const extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd> & lhs,const extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd> & rhs)1464 inline bool operator!=(const extended<table_pow2, advance_pow2,
1465 baseclass, extvalclass, kdd>& lhs,
1466 const extended<table_pow2, advance_pow2,
1467 baseclass, extvalclass, kdd>& rhs)
1468 {
1469 return !operator==(lhs, rhs);
1470 }
1471
1472 template <typename CharT, typename Traits,
1473 bitcount_t table_pow2, bitcount_t advance_pow2,
1474 typename baseclass, typename extvalclass, bool kdd>
1475 std::basic_ostream<CharT,Traits>&
operator <<(std::basic_ostream<CharT,Traits> & out,const extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd> & rng)1476 operator<<(std::basic_ostream<CharT,Traits>& out,
1477 const extended<table_pow2, advance_pow2,
1478 baseclass, extvalclass, kdd>& rng)
1479 {
1480 using pcg_extras::operator<<;
1481
1482 auto orig_flags = out.flags(std::ios_base::dec | std::ios_base::left);
1483 auto space = out.widen(' ');
1484 auto orig_fill = out.fill();
1485
1486 out << rng.multiplier() << space
1487 << rng.increment() << space
1488 << rng.state_;
1489
1490 for (const auto& datum : rng.data_)
1491 out << space << datum;
1492
1493 out.flags(orig_flags);
1494 out.fill(orig_fill);
1495 return out;
1496 }
1497
1498 template <typename CharT, typename Traits,
1499 bitcount_t table_pow2, bitcount_t advance_pow2,
1500 typename baseclass, typename extvalclass, bool kdd>
1501 std::basic_istream<CharT,Traits>&
operator >>(std::basic_istream<CharT,Traits> & in,extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd> & rng)1502 operator>>(std::basic_istream<CharT,Traits>& in,
1503 extended<table_pow2, advance_pow2,
1504 baseclass, extvalclass, kdd>& rng)
1505 {
1506 extended<table_pow2, advance_pow2, baseclass, extvalclass> new_rng;
1507 auto& base_rng = static_cast<baseclass&>(new_rng);
1508 in >> base_rng;
1509
1510 if (in.fail())
1511 return in;
1512
1513 using pcg_extras::operator>>;
1514
1515 auto orig_flags = in.flags(std::ios_base::dec | std::ios_base::skipws);
1516
1517 for (auto& datum : new_rng.data_) {
1518 in >> datum;
1519 if (in.fail())
1520 goto bail;
1521 }
1522
1523 rng = new_rng;
1524
1525 bail:
1526 in.flags(orig_flags);
1527 return in;
1528 }
1529
1530
1531
1532 template <bitcount_t table_pow2, bitcount_t advance_pow2,
1533 typename baseclass, typename extvalclass, bool kdd>
1534 void
advance_table()1535 extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd>::advance_table()
1536 {
1537 bool carry = false;
1538 for (size_t i = 0; i < table_size; ++i) {
1539 if (carry) {
1540 carry = insideout::external_step(data_[i],i+1);
1541 }
1542 bool carry2 = insideout::external_step(data_[i],i+1);
1543 carry = carry || carry2;
1544 }
1545 }
1546
1547 template <bitcount_t table_pow2, bitcount_t advance_pow2,
1548 typename baseclass, typename extvalclass, bool kdd>
1549 void
advance_table(state_type delta,bool isForwards)1550 extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd>::advance_table(
1551 state_type delta, bool isForwards)
1552 {
1553 typedef typename baseclass::state_type base_state_t;
1554 typedef typename extvalclass::state_type ext_state_t;
1555 constexpr bitcount_t basebits = sizeof(base_state_t)*8;
1556 constexpr bitcount_t extbits = sizeof(ext_state_t)*8;
1557 static_assert(basebits <= extbits || advance_pow2 > 0,
1558 "Current implementation might overflow its carry");
1559
1560 base_state_t carry = 0;
1561 for (size_t i = 0; i < table_size; ++i) {
1562 base_state_t total_delta = carry + delta;
1563 ext_state_t trunc_delta = ext_state_t(total_delta);
1564 if (basebits > extbits) {
1565 carry = total_delta >> extbits;
1566 } else {
1567 carry = 0;
1568 }
1569 carry +=
1570 insideout::external_advance(data_[i],i+1, trunc_delta, isForwards);
1571 }
1572 }
1573
1574 template <bitcount_t table_pow2, bitcount_t advance_pow2,
1575 typename baseclass, typename extvalclass, bool kdd>
advance(state_type distance,bool forwards)1576 void extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd>::advance(
1577 state_type distance, bool forwards)
1578 {
1579 static_assert(kdd,
1580 "Efficient advance is too hard for non-kdd extension. "
1581 "For a weak advance, cast to base class");
1582 state_type zero =
1583 baseclass::is_mcg ? this->state_ & state_type(3U) : state_type(0U);
1584 if (may_tick) {
1585 state_type ticks = distance >> (advance_pow2*may_tick);
1586 // ^-- stupidity to appease GCC
1587 // warnings
1588 state_type adv_mask =
1589 baseclass::is_mcg ? tick_mask << 2 : tick_mask;
1590 state_type next_advance_distance = this->distance(zero, adv_mask);
1591 if (!forwards)
1592 next_advance_distance = (-next_advance_distance) & tick_mask;
1593 if (next_advance_distance < (distance & tick_mask)) {
1594 ++ticks;
1595 }
1596 if (ticks)
1597 advance_table(ticks, forwards);
1598 }
1599 if (forwards) {
1600 if (may_tock && this->distance(zero) <= distance)
1601 advance_table();
1602 baseclass::advance(distance);
1603 } else {
1604 if (may_tock && -(this->distance(zero)) <= distance)
1605 advance_table(state_type(1U), false);
1606 baseclass::advance(-distance);
1607 }
1608 }
1609
1610 } // namespace pcg_detail
1611
1612 namespace pcg_engines {
1613
1614 using namespace pcg_detail;
1615
1616 /* Predefined types for XSH RS */
1617
1618 typedef oneseq_base<uint8_t, uint16_t, xsh_rs_mixin> oneseq_xsh_rs_16_8;
1619 typedef oneseq_base<uint16_t, uint32_t, xsh_rs_mixin> oneseq_xsh_rs_32_16;
1620 typedef oneseq_base<uint32_t, uint64_t, xsh_rs_mixin> oneseq_xsh_rs_64_32;
1621 typedef oneseq_base<uint64_t, pcg128_t, xsh_rs_mixin> oneseq_xsh_rs_128_64;
1622 typedef oneseq_base<uint64_t, pcg128_t, xsh_rs_mixin, true, cheap_multiplier>
1623 cm_oneseq_xsh_rs_128_64;
1624
1625 typedef unique_base<uint8_t, uint16_t, xsh_rs_mixin> unique_xsh_rs_16_8;
1626 typedef unique_base<uint16_t, uint32_t, xsh_rs_mixin> unique_xsh_rs_32_16;
1627 typedef unique_base<uint32_t, uint64_t, xsh_rs_mixin> unique_xsh_rs_64_32;
1628 typedef unique_base<uint64_t, pcg128_t, xsh_rs_mixin> unique_xsh_rs_128_64;
1629 typedef unique_base<uint64_t, pcg128_t, xsh_rs_mixin, true, cheap_multiplier>
1630 cm_unique_xsh_rs_128_64;
1631
1632 typedef setseq_base<uint8_t, uint16_t, xsh_rs_mixin> setseq_xsh_rs_16_8;
1633 typedef setseq_base<uint16_t, uint32_t, xsh_rs_mixin> setseq_xsh_rs_32_16;
1634 typedef setseq_base<uint32_t, uint64_t, xsh_rs_mixin> setseq_xsh_rs_64_32;
1635 typedef setseq_base<uint64_t, pcg128_t, xsh_rs_mixin> setseq_xsh_rs_128_64;
1636 typedef setseq_base<uint64_t, pcg128_t, xsh_rs_mixin, true, cheap_multiplier>
1637 cm_setseq_xsh_rs_128_64;
1638
1639 typedef mcg_base<uint8_t, uint16_t, xsh_rs_mixin> mcg_xsh_rs_16_8;
1640 typedef mcg_base<uint16_t, uint32_t, xsh_rs_mixin> mcg_xsh_rs_32_16;
1641 typedef mcg_base<uint32_t, uint64_t, xsh_rs_mixin> mcg_xsh_rs_64_32;
1642 typedef mcg_base<uint64_t, pcg128_t, xsh_rs_mixin> mcg_xsh_rs_128_64;
1643 typedef mcg_base<uint64_t, pcg128_t, xsh_rs_mixin, true, cheap_multiplier>
1644 cm_mcg_xsh_rs_128_64;
1645
1646 /* Predefined types for XSH RR */
1647
1648 typedef oneseq_base<uint8_t, uint16_t, xsh_rr_mixin> oneseq_xsh_rr_16_8;
1649 typedef oneseq_base<uint16_t, uint32_t, xsh_rr_mixin> oneseq_xsh_rr_32_16;
1650 typedef oneseq_base<uint32_t, uint64_t, xsh_rr_mixin> oneseq_xsh_rr_64_32;
1651 typedef oneseq_base<uint64_t, pcg128_t, xsh_rr_mixin> oneseq_xsh_rr_128_64;
1652 typedef oneseq_base<uint64_t, pcg128_t, xsh_rr_mixin, true, cheap_multiplier>
1653 cm_oneseq_xsh_rr_128_64;
1654
1655 typedef unique_base<uint8_t, uint16_t, xsh_rr_mixin> unique_xsh_rr_16_8;
1656 typedef unique_base<uint16_t, uint32_t, xsh_rr_mixin> unique_xsh_rr_32_16;
1657 typedef unique_base<uint32_t, uint64_t, xsh_rr_mixin> unique_xsh_rr_64_32;
1658 typedef unique_base<uint64_t, pcg128_t, xsh_rr_mixin> unique_xsh_rr_128_64;
1659 typedef unique_base<uint64_t, pcg128_t, xsh_rr_mixin, true, cheap_multiplier>
1660 cm_unique_xsh_rr_128_64;
1661
1662 typedef setseq_base<uint8_t, uint16_t, xsh_rr_mixin> setseq_xsh_rr_16_8;
1663 typedef setseq_base<uint16_t, uint32_t, xsh_rr_mixin> setseq_xsh_rr_32_16;
1664 typedef setseq_base<uint32_t, uint64_t, xsh_rr_mixin> setseq_xsh_rr_64_32;
1665 typedef setseq_base<uint64_t, pcg128_t, xsh_rr_mixin> setseq_xsh_rr_128_64;
1666 typedef setseq_base<uint64_t, pcg128_t, xsh_rr_mixin, true, cheap_multiplier>
1667 cm_setseq_xsh_rr_128_64;
1668
1669 typedef mcg_base<uint8_t, uint16_t, xsh_rr_mixin> mcg_xsh_rr_16_8;
1670 typedef mcg_base<uint16_t, uint32_t, xsh_rr_mixin> mcg_xsh_rr_32_16;
1671 typedef mcg_base<uint32_t, uint64_t, xsh_rr_mixin> mcg_xsh_rr_64_32;
1672 typedef mcg_base<uint64_t, pcg128_t, xsh_rr_mixin> mcg_xsh_rr_128_64;
1673 typedef mcg_base<uint64_t, pcg128_t, xsh_rr_mixin, true, cheap_multiplier>
1674 cm_mcg_xsh_rr_128_64;
1675
1676
1677 /* Predefined types for RXS M XS */
1678
1679 typedef oneseq_base<uint8_t, uint8_t, rxs_m_xs_mixin> oneseq_rxs_m_xs_8_8;
1680 typedef oneseq_base<uint16_t, uint16_t, rxs_m_xs_mixin> oneseq_rxs_m_xs_16_16;
1681 typedef oneseq_base<uint32_t, uint32_t, rxs_m_xs_mixin> oneseq_rxs_m_xs_32_32;
1682 typedef oneseq_base<uint64_t, uint64_t, rxs_m_xs_mixin> oneseq_rxs_m_xs_64_64;
1683 typedef oneseq_base<pcg128_t, pcg128_t, rxs_m_xs_mixin>
1684 oneseq_rxs_m_xs_128_128;
1685 typedef oneseq_base<pcg128_t, pcg128_t, rxs_m_xs_mixin, true, cheap_multiplier>
1686 cm_oneseq_rxs_m_xs_128_128;
1687
1688 typedef unique_base<uint8_t, uint8_t, rxs_m_xs_mixin> unique_rxs_m_xs_8_8;
1689 typedef unique_base<uint16_t, uint16_t, rxs_m_xs_mixin> unique_rxs_m_xs_16_16;
1690 typedef unique_base<uint32_t, uint32_t, rxs_m_xs_mixin> unique_rxs_m_xs_32_32;
1691 typedef unique_base<uint64_t, uint64_t, rxs_m_xs_mixin> unique_rxs_m_xs_64_64;
1692 typedef unique_base<pcg128_t, pcg128_t, rxs_m_xs_mixin> unique_rxs_m_xs_128_128;
1693 typedef unique_base<pcg128_t, pcg128_t, rxs_m_xs_mixin, true, cheap_multiplier>
1694 cm_unique_rxs_m_xs_128_128;
1695
1696 typedef setseq_base<uint8_t, uint8_t, rxs_m_xs_mixin> setseq_rxs_m_xs_8_8;
1697 typedef setseq_base<uint16_t, uint16_t, rxs_m_xs_mixin> setseq_rxs_m_xs_16_16;
1698 typedef setseq_base<uint32_t, uint32_t, rxs_m_xs_mixin> setseq_rxs_m_xs_32_32;
1699 typedef setseq_base<uint64_t, uint64_t, rxs_m_xs_mixin> setseq_rxs_m_xs_64_64;
1700 typedef setseq_base<pcg128_t, pcg128_t, rxs_m_xs_mixin> setseq_rxs_m_xs_128_128;
1701 typedef setseq_base<pcg128_t, pcg128_t, rxs_m_xs_mixin, true, cheap_multiplier>
1702 cm_setseq_rxs_m_xs_128_128;
1703
1704 // MCG versions don't make sense here, so aren't defined.
1705
1706 /* Predefined types for RXS M */
1707
1708 typedef oneseq_base<uint8_t, uint16_t, rxs_m_mixin> oneseq_rxs_m_16_8;
1709 typedef oneseq_base<uint16_t, uint32_t, rxs_m_mixin> oneseq_rxs_m_32_16;
1710 typedef oneseq_base<uint32_t, uint64_t, rxs_m_mixin> oneseq_rxs_m_64_32;
1711 typedef oneseq_base<uint64_t, pcg128_t, rxs_m_mixin> oneseq_rxs_m_128_64;
1712 typedef oneseq_base<uint64_t, pcg128_t, rxs_m_mixin, true, cheap_multiplier>
1713 cm_oneseq_rxs_m_128_64;
1714
1715 typedef unique_base<uint8_t, uint16_t, rxs_m_mixin> unique_rxs_m_16_8;
1716 typedef unique_base<uint16_t, uint32_t, rxs_m_mixin> unique_rxs_m_32_16;
1717 typedef unique_base<uint32_t, uint64_t, rxs_m_mixin> unique_rxs_m_64_32;
1718 typedef unique_base<uint64_t, pcg128_t, rxs_m_mixin> unique_rxs_m_128_64;
1719 typedef unique_base<uint64_t, pcg128_t, rxs_m_mixin, true, cheap_multiplier>
1720 cm_unique_rxs_m_128_64;
1721
1722 typedef setseq_base<uint8_t, uint16_t, rxs_m_mixin> setseq_rxs_m_16_8;
1723 typedef setseq_base<uint16_t, uint32_t, rxs_m_mixin> setseq_rxs_m_32_16;
1724 typedef setseq_base<uint32_t, uint64_t, rxs_m_mixin> setseq_rxs_m_64_32;
1725 typedef setseq_base<uint64_t, pcg128_t, rxs_m_mixin> setseq_rxs_m_128_64;
1726 typedef setseq_base<uint64_t, pcg128_t, rxs_m_mixin, true, cheap_multiplier>
1727 cm_setseq_rxs_m_128_64;
1728
1729 typedef mcg_base<uint8_t, uint16_t, rxs_m_mixin> mcg_rxs_m_16_8;
1730 typedef mcg_base<uint16_t, uint32_t, rxs_m_mixin> mcg_rxs_m_32_16;
1731 typedef mcg_base<uint32_t, uint64_t, rxs_m_mixin> mcg_rxs_m_64_32;
1732 typedef mcg_base<uint64_t, pcg128_t, rxs_m_mixin> mcg_rxs_m_128_64;
1733 typedef mcg_base<uint64_t, pcg128_t, rxs_m_mixin, true, cheap_multiplier>
1734 cm_mcg_rxs_m_128_64;
1735
1736 /* Predefined types for DXSM */
1737
1738 typedef oneseq_base<uint8_t, uint16_t, dxsm_mixin> oneseq_dxsm_16_8;
1739 typedef oneseq_base<uint16_t, uint32_t, dxsm_mixin> oneseq_dxsm_32_16;
1740 typedef oneseq_base<uint32_t, uint64_t, dxsm_mixin> oneseq_dxsm_64_32;
1741 typedef oneseq_base<uint64_t, pcg128_t, dxsm_mixin> oneseq_dxsm_128_64;
1742 typedef oneseq_base<uint64_t, pcg128_t, dxsm_mixin, true, cheap_multiplier>
1743 cm_oneseq_dxsm_128_64;
1744
1745 typedef unique_base<uint8_t, uint16_t, dxsm_mixin> unique_dxsm_16_8;
1746 typedef unique_base<uint16_t, uint32_t, dxsm_mixin> unique_dxsm_32_16;
1747 typedef unique_base<uint32_t, uint64_t, dxsm_mixin> unique_dxsm_64_32;
1748 typedef unique_base<uint64_t, pcg128_t, dxsm_mixin> unique_dxsm_128_64;
1749 typedef unique_base<uint64_t, pcg128_t, dxsm_mixin, true, cheap_multiplier>
1750 cm_unique_dxsm_128_64;
1751
1752 typedef setseq_base<uint8_t, uint16_t, dxsm_mixin> setseq_dxsm_16_8;
1753 typedef setseq_base<uint16_t, uint32_t, dxsm_mixin> setseq_dxsm_32_16;
1754 typedef setseq_base<uint32_t, uint64_t, dxsm_mixin> setseq_dxsm_64_32;
1755 typedef setseq_base<uint64_t, pcg128_t, dxsm_mixin> setseq_dxsm_128_64;
1756 typedef setseq_base<uint64_t, pcg128_t, dxsm_mixin, true, cheap_multiplier>
1757 cm_setseq_dxsm_128_64;
1758
1759 typedef mcg_base<uint8_t, uint16_t, dxsm_mixin> mcg_dxsm_16_8;
1760 typedef mcg_base<uint16_t, uint32_t, dxsm_mixin> mcg_dxsm_32_16;
1761 typedef mcg_base<uint32_t, uint64_t, dxsm_mixin> mcg_dxsm_64_32;
1762 typedef mcg_base<uint64_t, pcg128_t, dxsm_mixin> mcg_dxsm_128_64;
1763 typedef mcg_base<uint64_t, pcg128_t, dxsm_mixin, true, cheap_multiplier>
1764 cm_mcg_dxsm_128_64;
1765
1766 /* Predefined types for XSL RR (only defined for "large" types) */
1767
1768 typedef oneseq_base<uint32_t, uint64_t, xsl_rr_mixin> oneseq_xsl_rr_64_32;
1769 typedef oneseq_base<uint64_t, pcg128_t, xsl_rr_mixin> oneseq_xsl_rr_128_64;
1770 typedef oneseq_base<uint64_t, pcg128_t, xsl_rr_mixin, true, cheap_multiplier>
1771 cm_oneseq_xsl_rr_128_64;
1772
1773 typedef unique_base<uint32_t, uint64_t, xsl_rr_mixin> unique_xsl_rr_64_32;
1774 typedef unique_base<uint64_t, pcg128_t, xsl_rr_mixin> unique_xsl_rr_128_64;
1775 typedef unique_base<uint64_t, pcg128_t, xsl_rr_mixin, true, cheap_multiplier>
1776 cm_unique_xsl_rr_128_64;
1777
1778 typedef setseq_base<uint32_t, uint64_t, xsl_rr_mixin> setseq_xsl_rr_64_32;
1779 typedef setseq_base<uint64_t, pcg128_t, xsl_rr_mixin> setseq_xsl_rr_128_64;
1780 typedef setseq_base<uint64_t, pcg128_t, xsl_rr_mixin, true, cheap_multiplier>
1781 cm_setseq_xsl_rr_128_64;
1782
1783 typedef mcg_base<uint32_t, uint64_t, xsl_rr_mixin> mcg_xsl_rr_64_32;
1784 typedef mcg_base<uint64_t, pcg128_t, xsl_rr_mixin> mcg_xsl_rr_128_64;
1785 typedef mcg_base<uint64_t, pcg128_t, xsl_rr_mixin, true, cheap_multiplier>
1786 cm_mcg_xsl_rr_128_64;
1787
1788
1789 /* Predefined types for XSL RR RR (only defined for "large" types) */
1790
1791 typedef oneseq_base<uint64_t, uint64_t, xsl_rr_rr_mixin>
1792 oneseq_xsl_rr_rr_64_64;
1793 typedef oneseq_base<pcg128_t, pcg128_t, xsl_rr_rr_mixin>
1794 oneseq_xsl_rr_rr_128_128;
1795 typedef oneseq_base<pcg128_t, pcg128_t, xsl_rr_rr_mixin, true, cheap_multiplier>
1796 cm_oneseq_xsl_rr_rr_128_128;
1797
1798 typedef unique_base<uint64_t, uint64_t, xsl_rr_rr_mixin>
1799 unique_xsl_rr_rr_64_64;
1800 typedef unique_base<pcg128_t, pcg128_t, xsl_rr_rr_mixin>
1801 unique_xsl_rr_rr_128_128;
1802 typedef unique_base<pcg128_t, pcg128_t, xsl_rr_rr_mixin, true, cheap_multiplier>
1803 cm_unique_xsl_rr_rr_128_128;
1804
1805 typedef setseq_base<uint64_t, uint64_t, xsl_rr_rr_mixin>
1806 setseq_xsl_rr_rr_64_64;
1807 typedef setseq_base<pcg128_t, pcg128_t, xsl_rr_rr_mixin>
1808 setseq_xsl_rr_rr_128_128;
1809 typedef setseq_base<pcg128_t, pcg128_t, xsl_rr_rr_mixin, true, cheap_multiplier>
1810 cm_setseq_xsl_rr_rr_128_128;
1811
1812 // MCG versions don't make sense here, so aren't defined.
1813
1814 /* Extended generators */
1815
1816 template <bitcount_t table_pow2, bitcount_t advance_pow2,
1817 typename BaseRNG, bool kdd = true>
1818 using ext_std8 = extended<table_pow2, advance_pow2, BaseRNG,
1819 oneseq_rxs_m_xs_8_8, kdd>;
1820
1821 template <bitcount_t table_pow2, bitcount_t advance_pow2,
1822 typename BaseRNG, bool kdd = true>
1823 using ext_std16 = extended<table_pow2, advance_pow2, BaseRNG,
1824 oneseq_rxs_m_xs_16_16, kdd>;
1825
1826 template <bitcount_t table_pow2, bitcount_t advance_pow2,
1827 typename BaseRNG, bool kdd = true>
1828 using ext_std32 = extended<table_pow2, advance_pow2, BaseRNG,
1829 oneseq_rxs_m_xs_32_32, kdd>;
1830
1831 template <bitcount_t table_pow2, bitcount_t advance_pow2,
1832 typename BaseRNG, bool kdd = true>
1833 using ext_std64 = extended<table_pow2, advance_pow2, BaseRNG,
1834 oneseq_rxs_m_xs_64_64, kdd>;
1835
1836
1837 template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
1838 using ext_oneseq_rxs_m_xs_32_32 =
1839 ext_std32<table_pow2, advance_pow2, oneseq_rxs_m_xs_32_32, kdd>;
1840
1841 template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
1842 using ext_mcg_xsh_rs_64_32 =
1843 ext_std32<table_pow2, advance_pow2, mcg_xsh_rs_64_32, kdd>;
1844
1845 template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
1846 using ext_oneseq_xsh_rs_64_32 =
1847 ext_std32<table_pow2, advance_pow2, oneseq_xsh_rs_64_32, kdd>;
1848
1849 template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
1850 using ext_setseq_xsh_rr_64_32 =
1851 ext_std32<table_pow2, advance_pow2, setseq_xsh_rr_64_32, kdd>;
1852
1853 template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
1854 using ext_mcg_xsl_rr_128_64 =
1855 ext_std64<table_pow2, advance_pow2, mcg_xsl_rr_128_64, kdd>;
1856
1857 template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
1858 using ext_oneseq_xsl_rr_128_64 =
1859 ext_std64<table_pow2, advance_pow2, oneseq_xsl_rr_128_64, kdd>;
1860
1861 template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
1862 using ext_setseq_xsl_rr_128_64 =
1863 ext_std64<table_pow2, advance_pow2, setseq_xsl_rr_128_64, kdd>;
1864
1865 } // namespace pcg_engines
1866
1867 typedef pcg_engines::setseq_xsh_rr_64_32 pcg32;
1868 typedef pcg_engines::oneseq_xsh_rr_64_32 pcg32_oneseq;
1869 typedef pcg_engines::unique_xsh_rr_64_32 pcg32_unique;
1870 typedef pcg_engines::mcg_xsh_rs_64_32 pcg32_fast;
1871
1872 typedef pcg_engines::setseq_xsl_rr_128_64 pcg64;
1873 typedef pcg_engines::oneseq_xsl_rr_128_64 pcg64_oneseq;
1874 typedef pcg_engines::unique_xsl_rr_128_64 pcg64_unique;
1875 typedef pcg_engines::mcg_xsl_rr_128_64 pcg64_fast;
1876
1877 typedef pcg_engines::setseq_rxs_m_xs_8_8 pcg8_once_insecure;
1878 typedef pcg_engines::setseq_rxs_m_xs_16_16 pcg16_once_insecure;
1879 typedef pcg_engines::setseq_rxs_m_xs_32_32 pcg32_once_insecure;
1880 typedef pcg_engines::setseq_rxs_m_xs_64_64 pcg64_once_insecure;
1881 typedef pcg_engines::setseq_xsl_rr_rr_128_128 pcg128_once_insecure;
1882
1883 typedef pcg_engines::oneseq_rxs_m_xs_8_8 pcg8_oneseq_once_insecure;
1884 typedef pcg_engines::oneseq_rxs_m_xs_16_16 pcg16_oneseq_once_insecure;
1885 typedef pcg_engines::oneseq_rxs_m_xs_32_32 pcg32_oneseq_once_insecure;
1886 typedef pcg_engines::oneseq_rxs_m_xs_64_64 pcg64_oneseq_once_insecure;
1887 typedef pcg_engines::oneseq_xsl_rr_rr_128_128 pcg128_oneseq_once_insecure;
1888
1889
1890 // These two extended RNGs provide two-dimensionally equidistributed
1891 // 32-bit generators. pcg32_k2_fast occupies the same space as pcg64,
1892 // and can be called twice to generate 64 bits, but does not required
1893 // 128-bit math; on 32-bit systems, it's faster than pcg64 as well.
1894
1895 typedef pcg_engines::ext_setseq_xsh_rr_64_32<1,16,true> pcg32_k2;
1896 typedef pcg_engines::ext_oneseq_xsh_rs_64_32<1,32,true> pcg32_k2_fast;
1897
1898 // These eight extended RNGs have about as much state as arc4random
1899 //
1900 // - the k variants are k-dimensionally equidistributed
1901 // - the c variants offer better crypographic security
1902 //
1903 // (just how good the cryptographic security is is an open question)
1904
1905 typedef pcg_engines::ext_setseq_xsh_rr_64_32<6,16,true> pcg32_k64;
1906 typedef pcg_engines::ext_mcg_xsh_rs_64_32<6,32,true> pcg32_k64_oneseq;
1907 typedef pcg_engines::ext_oneseq_xsh_rs_64_32<6,32,true> pcg32_k64_fast;
1908
1909 typedef pcg_engines::ext_setseq_xsh_rr_64_32<6,16,false> pcg32_c64;
1910 typedef pcg_engines::ext_oneseq_xsh_rs_64_32<6,32,false> pcg32_c64_oneseq;
1911 typedef pcg_engines::ext_mcg_xsh_rs_64_32<6,32,false> pcg32_c64_fast;
1912
1913 typedef pcg_engines::ext_setseq_xsl_rr_128_64<5,16,true> pcg64_k32;
1914 typedef pcg_engines::ext_oneseq_xsl_rr_128_64<5,128,true> pcg64_k32_oneseq;
1915 typedef pcg_engines::ext_mcg_xsl_rr_128_64<5,128,true> pcg64_k32_fast;
1916
1917 typedef pcg_engines::ext_setseq_xsl_rr_128_64<5,16,false> pcg64_c32;
1918 typedef pcg_engines::ext_oneseq_xsl_rr_128_64<5,128,false> pcg64_c32_oneseq;
1919 typedef pcg_engines::ext_mcg_xsl_rr_128_64<5,128,false> pcg64_c32_fast;
1920
1921 // These eight extended RNGs have more state than the Mersenne twister
1922 //
1923 // - the k variants are k-dimensionally equidistributed
1924 // - the c variants offer better crypographic security
1925 //
1926 // (just how good the cryptographic security is is an open question)
1927
1928 typedef pcg_engines::ext_setseq_xsh_rr_64_32<10,16,true> pcg32_k1024;
1929 typedef pcg_engines::ext_oneseq_xsh_rs_64_32<10,32,true> pcg32_k1024_fast;
1930
1931 typedef pcg_engines::ext_setseq_xsh_rr_64_32<10,16,false> pcg32_c1024;
1932 typedef pcg_engines::ext_oneseq_xsh_rs_64_32<10,32,false> pcg32_c1024_fast;
1933
1934 typedef pcg_engines::ext_setseq_xsl_rr_128_64<10,16,true> pcg64_k1024;
1935 typedef pcg_engines::ext_oneseq_xsl_rr_128_64<10,128,true> pcg64_k1024_fast;
1936
1937 typedef pcg_engines::ext_setseq_xsl_rr_128_64<10,16,false> pcg64_c1024;
1938 typedef pcg_engines::ext_oneseq_xsl_rr_128_64<10,128,false> pcg64_c1024_fast;
1939
1940 // These generators have an insanely huge period (2^524352), and is suitable
1941 // for silly party tricks, such as dumping out 64 KB ZIP files at an arbitrary
1942 // point in the future. [Actually, over the full period of the generator, it
1943 // will produce every 64 KB ZIP file 2^64 times!]
1944
1945 typedef pcg_engines::ext_setseq_xsh_rr_64_32<14,16,true> pcg32_k16384;
1946 typedef pcg_engines::ext_oneseq_xsh_rs_64_32<14,32,true> pcg32_k16384_fast;
1947
1948 } // namespace arrow_vendored
1949
1950 #ifdef _MSC_VER
1951 #pragma warning(default:4146)
1952 #endif
1953
1954 #endif // PCG_RAND_HPP_INCLUDED
1955