main.cpp

#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>

typedef int64_t s64;
typedef uint64_t u64;

typedef int32_t s32;
typedef uint32_t u32;

typedef int8_t s8;
typedef uint8_t u8;

class PcgRandom {
public:
	const static s32 RANDOM_MIN   = -0x7fffffff - 1;
	const static s32 RANDOM_MAX   = 0x7fffffff;
	const static u32 RANDOM_RANGE = 0xffffffff;

	PcgRandom(u64 state=0x853c49e6748fea9bULL, u64 seq=0xda3e39cb94b95bdbULL);
	void seed(u64 state, u64 seq=0xda3e39cb94b95bdbULL);
	u32 next();
	u32 range(u32 bound);
	s32 range(s32 min, s32 max);
	void bytes(void *out, size_t len);

private:
	u64 m_state;
	u64 m_inc;
};

PcgRandom::PcgRandom(u64 state, u64 seq)
{
	seed(state, seq);
}

void PcgRandom::seed(u64 state, u64 seq)
{
	m_state = 0U;
	m_inc = (seq << 1u) | 1u;
	next();
	m_state += state;
	next();
}


u32 PcgRandom::next()
{
	u64 oldstate = m_state;
	m_state = oldstate * 6364136223846793005ULL + m_inc;

	u32 xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
	u32 rot = oldstate >> 59u;
	return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}


u32 PcgRandom::range(u32 bound)
{
	// If the bound is 0, we cover the whole RNG's range
	if (bound == 0)
		return next();

	/*
		This is an optimization of the expression:
		  0x100000000ull % bound
		since 64-bit modulo operations typically much slower than 32.
	*/
	u32 threshold = -bound % bound;
	u32 r;

	/*
		If the bound is not a multiple of the RNG's range, it may cause bias,
		e.g. a RNG has a range from 0 to 3 and we take want a number 0 to 2.
		Using rand() % 3, the number 0 would be twice as likely to appear.
		With a very large RNG range, the effect becomes less prevalent but
		still present.

		This can be solved by modifying the range of the RNG to become a
		multiple of bound by dropping values above the a threshold.

		In our example, threshold == 4 % 3 == 1, so reject values < 1
		(that is, 0), thus making the range == 3 with no bias.

		This loop may look dangerous, but will always terminate due to the
		RNG's property of uniformity.
	*/
	while ((r = next()) < threshold)
		;

	return r % bound;
}


s32 PcgRandom::range(s32 min, s32 max)
{
	if (max < min) {
        std::cerr << "Invalid range (max < min)" << std::endl;
        abort();
    }

	u32 bound = max - min + 1;
	return range(bound) + min;
}


void PcgRandom::bytes(void *out, size_t len)
{
	u8 *outb = (u8 *)out;
	int bytes_left = 0;
	u32 r;

	while (len--) {
		if (bytes_left == 0) {
			bytes_left = sizeof(u32);
			r = next();
		}

		*outb = r & 0xFF;
		outb++;
		bytes_left--;
		r >>= 8;
	}
}

static const u32 expected_pcgrandom_results[256] = {
	0x48c593f8, 0x054f59f5, 0x0d062dc1, 0x23852a23, 0x7fbbc97b, 0x1f9f141e,
	0x364e6ed8, 0x995bba58, 0xc9307dc0, 0x73fb34c4, 0xcd8de88d, 0x52e8ce08,
	0x1c4a78e4, 0x25c0882e, 0x8a82e2e0, 0xe3bc3311, 0xb8068d42, 0x73186110,
	0x19988df4, 0x69bd970b, 0x7214728c, 0x0aee320c, 0x2a5a536c, 0xaf48d715,
	0x00bce504, 0xd2b8f548, 0x520df366, 0x96d8fff5, 0xa1bb510b, 0x63477049,
	0xb85990b7, 0x7e090689, 0x275fb468, 0x50206257, 0x8bab4f8a, 0x0d6823db,
	0x63faeaac, 0x2d92deeb, 0x2ba78024, 0x0d30f631, 0x338923a0, 0xd07248d8,
	0xa5db62d3, 0xddba8af6, 0x0ad454e9, 0x6f0fd13a, 0xbbfde2bf, 0x91188009,
	0x966b394d, 0xbb9d2012, 0x7e6926cb, 0x95183860, 0x5ff4c59b, 0x035f628a,
	0xb67085ef, 0x33867e23, 0x68d1b887, 0x2e3298d7, 0x84fd0650, 0x8bc91141,
	0x6fcb0452, 0x2836fee9, 0x2e83c0a3, 0xf1bafdc5, 0x9ff77777, 0xfdfbba87,
	0x527aebeb, 0x423e5248, 0xd1756490, 0xe41148fa, 0x3361f7b4, 0xa2824f23,
	0xf4e08072, 0xc50442be, 0x35adcc21, 0x36be153c, 0xc7709012, 0xf0eeb9f2,
	0x3d73114e, 0x1c1574ee, 0x92095b9c, 0x1503d01c, 0xd6ce0677, 0x026a8ec1,
	0x76d0084d, 0x86c23633, 0x36f75ce6, 0x08fa7bbe, 0x35f6ff2a, 0x31cc9525,
	0x2c1a35e6, 0x8effcd62, 0xc782fa07, 0x8a86e248, 0x8fdb7a9b, 0x77246626,
	0x5767723f, 0x3a78b699, 0xe548ce1c, 0x5820f37d, 0x148ed9b8, 0xf6796254,
	0x32232c20, 0x392bf3a2, 0xe9af6625, 0xd40b0d88, 0x636cfa23, 0x6a5de514,
	0xc4a69183, 0xc785c853, 0xab0de901, 0x16ae7e44, 0x376f13b5, 0x070f7f31,
	0x34cbc93b, 0xe6184345, 0x1b7f911f, 0x631fbe4b, 0x86d6e023, 0xc689b518,
	0x88ef4f7c, 0xddf06b45, 0xc97f18d4, 0x2aaee94b, 0x45694723, 0x6db111d2,
	0x91974fce, 0xe33e29e2, 0xc5e99494, 0x8017e02b, 0x3ebd8143, 0x471ffb80,
	0xc0d7ca1b, 0x4954c860, 0x48935d6a, 0xf2d27999, 0xb93d608d, 0x40696e90,
	0x60b18162, 0x1a156998, 0x09b8bbab, 0xc80a79b6, 0x8adbcfbc, 0xc375248c,
	0xa584e2ea, 0x5b46fe11, 0x58e84680, 0x8a8bc456, 0xd668b94f, 0x8b9035be,
	0x278509d4, 0x6663a140, 0x81a9817a, 0xd4f9d3cf, 0x6dc5f607, 0x6ae04450,
	0x694f22a4, 0x1d061788, 0x2e39ad8b, 0x748f4db2, 0xee569b52, 0xd157166d,
	0xdabc161e, 0xc8d50176, 0x7e3110e5, 0x9f7d033b, 0x128df67f, 0xb0078583,
	0xa3a75d26, 0xc1ad8011, 0x07dd89ec, 0xef04f456, 0x91bf866c, 0x6aac5306,
	0xdd5a1573, 0xf73ff97a, 0x4e1186ad, 0xb9680680, 0xc8894515, 0xdc95a08e,
	0xc894fd8e, 0xf84ade15, 0xd787f8c1, 0x40dcecca, 0x1b24743e, 0x1ce6ab23,
	0x72321653, 0xb80fbaf7, 0x1bcf099b, 0x1ff26805, 0x78f66c8e, 0xf93bf51a,
	0xfb0c06fe, 0xe50d48cf, 0x310947e0, 0x1b78804a, 0xe73e2c14, 0x8deb8381,
	0xe576122a, 0xe5a8df39, 0x42397c5e, 0xf5503f3c, 0xbe3dbf8d, 0x1b360e5c,
	0x9254caaf, 0x7a9f6744, 0x6d4144fa, 0xd77c65fe, 0x44ca7b12, 0xf58a4c00,
	0x159500d0, 0x92769857, 0x7134fdd4, 0xa3fea693, 0xbd044831, 0xeded39a1,
	0xe4570204, 0xaea37f2f, 0x9a302971, 0x620f8402, 0x1d2f3e5e, 0xf9c2f49c,
	0x738e813a, 0xb3c92251, 0x7ecba63b, 0xbe7eebc7, 0xf800267c, 0x3fdeb760,
	0xf12d5e7d, 0x5a18dce1, 0xb35a539c, 0xe565f057, 0x2babf38c, 0xae5800ad,
	0x421004dd, 0x6715acb6, 0xff529b64, 0xd520d207, 0x7cb193e7, 0xe9b18e4c,
	0xfd2a8a59, 0x47826ae3, 0x56ba43f8, 0x453b3d99, 0x8ae1675f, 0xf66f5c34,
	0x057a6ac1, 0x010769e4, 0xa8324158, 0x410379a5, 0x5dfc8c97, 0x72848afe,
	0x59f169e5, 0xe32acb78, 0x5dfaa9c4, 0x51bb956a,
};

int main() {
	PcgRandom pr(814538, 998877);

	for (u32 i = 0; i != 256; i++) {
        u32 actual = pr.next();
        u32 expected = expected_pcgrandom_results[i];
        if (actual != expected) {
            std::cerr << "DIFFERENCE!!!" << std::endl;
            abort();
        }

    }
    return 0;
}