33 #ifndef PCG_EXTRAS_HPP_INCLUDED
34 #define PCG_EXTRAS_HPP_INCLUDED 1
43 #include <type_traits>
57 #define PCG_NOINLINE __attribute__((noinline))
81 #define PCG_128BIT_CONSTANT(high,low) \
82 ((pcg128_t(high) << 64) + low)
88 #define PCG_128BIT_CONSTANT(high,low) \
90 #define PCG_EMULATED_128BIT_MATH 1
104 #ifndef PCG_BITCOUNT_T
119 template <
typename CharT,
typename Traits>
120 std::basic_ostream<CharT,Traits>&
123 auto desired_base = out.flags() & out.basefield;
124 bool want_hex = desired_base == out.hex;
127 uint64_t highpart = uint64_t(value >> 64);
128 uint64_t lowpart = uint64_t(value);
129 auto desired_width = out.width();
130 if (desired_width > 16) {
131 out.width(desired_width - 16);
133 if (highpart != 0 || desired_width > 16)
135 CharT oldfill =
'\0';
138 oldfill = out.fill(
'0');
140 auto oldflags = out.setf(decltype(desired_base){}, out.showbase);
148 constexpr
size_t MAX_CHARS_128BIT = 40;
150 char buffer[MAX_CHARS_128BIT];
151 char* pos = buffer+
sizeof(buffer);
153 constexpr
auto BASE =
pcg128_t(10ULL);
155 auto div = value / BASE;
156 auto mod = uint32_t(value - (div * BASE));
157 *(--pos) =
'0' +
char(mod);
163 template <
typename CharT,
typename Traits>
164 std::basic_istream<CharT,Traits>&
167 typename std::basic_istream<CharT,Traits>::sentry s(in);
172 constexpr
auto BASE =
pcg128_t(10ULL);
174 bool did_nothing =
true;
175 bool overflow =
false;
177 CharT wide_ch = in.get();
180 auto ch = in.narrow(wide_ch,
'\0');
181 if (ch < '0' || ch >
'9') {
188 overflow = overflow || timesbase < current;
189 current = timesbase + digit;
190 overflow = overflow || current < digit;
193 if (did_nothing || overflow) {
194 in.setstate(std::ios::failbit);
211 template <
typename CharT,
typename Traits>
212 std::basic_ostream<CharT,Traits>&
213 operator<<(std::basic_ostream<CharT,Traits>&out, uint8_t value)
215 return out << uint32_t(value);
218 template <
typename CharT,
typename Traits>
219 std::basic_istream<CharT,Traits>&
220 operator>>(std::basic_istream<CharT,Traits>& in, uint8_t& target)
222 uint32_t value = 0xdecea5edU;
224 if (!in && value == 0xdecea5edU)
226 if (value > uint8_t(~0)) {
227 in.setstate(std::ios::failbit);
230 target = uint8_t(value);
239 inline std::ostream&
operator<<(std::ostream& out, uint8_t value)
241 return pcg_extras::operator<< <char>(out, value);
244 inline std::istream&
operator>>(std::istream& in, uint8_t& value)
246 return pcg_extras::operator>> <
char>(in, value);
261 template <
typename itype>
264 if (2*shift >= bits) {
265 return x ^ (x >> shift);
267 itype lowmask1 = (itype(1U) << (bits - shift*2)) - 1;
268 itype highmask1 = ~lowmask1;
270 itype bottom1 = x & lowmask1;
271 top1 ^= top1 >> shift;
274 itype lowmask2 = (itype(1U) << (bits - shift)) - 1;
275 itype bottom2 = x & lowmask2;
276 bottom2 =
unxorshift(bottom2, bits - shift, shift);
278 return top1 | bottom2;
290 template <
typename itype>
293 constexpr
bitcount_t bits =
sizeof(itype) * 8;
295 #if PCG_USE_ZEROCHECK_ROTATE_IDIOM
296 return rot ? (value << rot) | (value >> (bits - rot)) : value;
298 return (value << rot) | (value >> ((- rot) & mask));
302 template <
typename itype>
305 constexpr
bitcount_t bits =
sizeof(itype) * 8;
307 #if PCG_USE_ZEROCHECK_ROTATE_IDIOM
308 return rot ? (value >> rot) | (value << (bits - rot)) : value;
310 return (value >> rot) | (value << ((- rot) & mask));
321 #if PCG_USE_INLINE_ASM && __GNUC__ && (__x86_64__ || __i386__)
325 asm (
"rorb %%cl, %0" :
"=r" (value) :
"0" (value),
"c" (rot));
331 asm (
"rorw %%cl, %0" :
"=r" (value) :
"0" (value),
"c" (rot));
337 asm (
"rorl %%cl, %0" :
"=r" (value) :
"0" (value),
"c" (rot));
344 asm (
"rorq %%cl, %0" :
"=r" (value) :
"0" (value),
"c" (rot));
349 #elif defined(_MSC_VER)
352 #pragma intrinsic(_rotr, _rotr64, _rotr8, _rotr16)
356 return _rotr8(value, rot);
361 return _rotr16(value, rot);
366 return _rotr(value, rot);
371 return _rotr64(value, rot);
374 #endif // PCG_USE_INLINE_ASM
404 template<
class SrcIter,
class DestIter>
406 SrcIter src_first, DestIter dest_first, DestIter dest_last,
409 typedef typename std::iterator_traits<SrcIter>::value_type src_t;
410 typedef typename std::iterator_traits<DestIter>::value_type dest_t;
412 constexpr
bitcount_t SRC_SIZE =
sizeof(src_t);
413 constexpr
bitcount_t DEST_SIZE =
sizeof(dest_t);
414 constexpr
bitcount_t DEST_BITS = DEST_SIZE * 8;
415 constexpr
bitcount_t SCALE = SRC_SIZE / DEST_SIZE;
420 while (dest_first != dest_last) {
421 if ((count++ % SCALE) == 0)
422 value = *src_first++;
426 *dest_first++ = dest_t(value);
433 template<
class SrcIter,
class DestIter>
435 SrcIter src_first, DestIter dest_first, DestIter dest_last,
438 typedef typename std::iterator_traits<SrcIter>::value_type src_t;
439 typedef typename std::iterator_traits<DestIter>::value_type dest_t;
441 constexpr
auto SRC_SIZE =
sizeof(src_t);
442 constexpr
auto SRC_BITS = SRC_SIZE * 8;
443 constexpr
auto DEST_SIZE =
sizeof(dest_t);
444 constexpr
auto SCALE = (DEST_SIZE+SRC_SIZE-1) / SRC_SIZE;
446 while (dest_first != dest_last) {
448 unsigned int shift = 0;
450 for (
size_t i = 0; i < SCALE; ++i) {
451 value |= dest_t(*src_first++) << shift;
455 *dest_first++ = value;
462 template<
class SrcIter,
class DestIter>
464 DestIter dest_first, DestIter dest_last)
466 typedef typename std::iterator_traits<SrcIter>::value_type src_t;
467 typedef typename std::iterator_traits<DestIter>::value_type dest_t;
469 constexpr
bool DEST_IS_SMALLER =
sizeof(dest_t) <
sizeof(src_t);
472 std::integral_constant<bool, DEST_IS_SMALLER>{});
479 template <
size_t size,
typename SeedSeq,
typename DestIter>
483 generator.generate(dest, dest+size);
486 template <
size_t size,
typename SeedSeq,
typename DestIter>
490 typedef typename std::iterator_traits<DestIter>::value_type dest_t;
491 constexpr
auto DEST_SIZE =
sizeof(dest_t);
492 constexpr
auto GEN_SIZE =
sizeof(uint32_t);
494 constexpr
bool GEN_IS_SMALLER = GEN_SIZE < DEST_SIZE;
495 constexpr
size_t FROM_ELEMS =
497 ? size * ((DEST_SIZE+GEN_SIZE-1) / GEN_SIZE)
498 : (size + (GEN_SIZE / DEST_SIZE) - 1)
499 / ((GEN_SIZE / DEST_SIZE) + GEN_IS_SMALLER);
503 if (FROM_ELEMS <= 1024) {
504 uint32_t buffer[FROM_ELEMS];
505 generator.generate(buffer, buffer+FROM_ELEMS);
508 uint32_t* buffer =
static_cast<uint32_t*
>(malloc(GEN_SIZE * FROM_ELEMS));
509 generator.generate(buffer, buffer+FROM_ELEMS);
511 free(
static_cast<void*
>(buffer));
515 template <
size_t size,
typename SeedSeq,
typename DestIter>
518 typedef typename std::iterator_traits<DestIter>::value_type dest_t;
519 constexpr
bool IS_32BIT =
sizeof(dest_t) ==
sizeof(uint32_t);
521 generate_to_impl<size>(std::forward<SeedSeq>(generator), dest,
522 std::integral_constant<bool, IS_32BIT>{});
530 template <
typename UInt,
size_t i = 0UL,
size_t N = i+1UL,
typename SeedSeq>
534 generate_to<N>(std::forward<SeedSeq>(generator), result);
538 template <
typename RngType>
539 auto bounded_rand(RngType& rng,
typename RngType::result_type upper_bound)
540 ->
typename RngType::result_type
542 typedef typename RngType::result_type rtype;
543 rtype threshold = (RngType::max() - RngType::min() + rtype(1) - upper_bound)
546 rtype r = rng() - RngType::min();
548 return r % upper_bound;
552 template <
typename Iter,
typename RandType>
553 void shuffle(Iter from, Iter to, RandType&& rng)
555 typedef typename std::iterator_traits<Iter>::difference_type delta_t;
556 typedef typename std::remove_reference<RandType>::type::result_type result_t;
557 auto count = to - from;
559 delta_t chosen = delta_t(
bounded_rand(rng, result_t(count)));
563 swap(*(from + chosen), *to);
579 template <
typename RngType>
584 typedef uint_least32_t result_type;
587 template<
typename... Args>
589 rng_(std::forward<Args>(args)...)
594 template<
typename Iter>
597 for (
auto i = start; i != finish; ++i)
598 *i = result_type(rng_());
603 return (
sizeof(
typename RngType::result_type) >
sizeof(result_type)
604 && RngType::max() > ~
size_t(0UL))
606 : size_t(RngType::max());
617 template <
typename IntType>
620 static constexpr IntType fnv(IntType hash,
const char* pos) {
623 : fnv((hash * IntType(16777619U)) ^ *pos, (pos+1));
627 static constexpr IntType
value = fnv(IntType(2166136261U ^
sizeof(IntType)),
628 __DATE__ __TIME__ __FILE__);
638 #if __cpp_rtti || __GXX_RTTI
640 template <
typename T>
641 struct printable_typename {};
643 template <
typename T>
644 std::ostream&
operator<<(std::ostream& out, printable_typename<T>) {
645 const char *implementation_typename =
typeid(T).name();
649 abi::__cxa_demangle(implementation_typename,
nullptr,
nullptr, &status);
652 free(
static_cast<void*
>(pretty_name));
656 out << implementation_typename;
660 #endif // __cpp_rtti || __GXX_RTTI
664 #endif // PCG_EXTRAS_HPP_INCLUDED