/* Written in 2018 by Sebastiano Vigna (vigna@acm.org)

Easily computes the state of a PCG generator from its output,
making it trivial to predict all its future output.

To the extent possible under law, the author has dedicated all copyright
and related and neighboring rights to this software to the public domain
worldwide. This software is distributed without any warranty.

See <http://creativecommons.org/publicdomain/zero/1.0/>. */


#include <stdio.h>
#include <inttypes.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>

// -------
// PCG code Copyright by Melissa O'Neill

#define PCG_DEFAULT_MULTIPLIER_64  6364136223846793005ULL
#define PCG_DEFAULT_INCREMENT_64   1442695040888963407ULL

struct pcg_state_64 {
	uint64_t state;
} rng;

inline uint32_t pcg_rotr_32(uint32_t value, unsigned int rot) {
	return (value >> rot) | (value << ((- rot) & 31));
}

inline void pcg_oneseq_64_step_r(struct pcg_state_64* rng) {
	rng->state = rng->state * PCG_DEFAULT_MULTIPLIER_64 + PCG_DEFAULT_INCREMENT_64;
}

inline uint32_t pcg_output_xsh_rr_64_32(uint64_t state) {
	return pcg_rotr_32(((state >> 18u) ^ state) >> 27u, state >> 59u);
}

inline uint32_t pcg_oneseq_64_xsh_rr_32_random_r(struct pcg_state_64* rng) {
	uint64_t oldstate = rng->state;
	pcg_oneseq_64_step_r(rng);
	return pcg_output_xsh_rr_64_32(oldstate);
}

// -------


// Given three consecutive outputs of the generator above, recover the initial state.

uint64_t recover(const uint32_t x0, const uint32_t x1, const uint32_t x2) {
	for(uint64_t upper = 0; upper < (UINT64_C(1) << 32); upper++) {
		const int rot = upper >> 27;
		const uint32_t rotx0 = x0 << rot | x0 >> (32 - rot);

		//	rotx0 = state >> 45 ^ state >> 27
		// rotx0 ^ upper >> 13 = state >> 27
		// state >> 27 & ~31 = upper << 5

		if (((rotx0 ^ upper >> 13) & ~31) == (uint32_t)(upper << 5)) {
			const uint32_t high_lower_bits = ((rotx0 ^ upper >> 13) & 31) << 27;
			for(uint32_t lower = 0; lower < (UINT64_C(1) << 27); lower++) {
				const uint64_t candidate = (uint64_t)upper << 32 | high_lower_bits | lower;
				struct pcg_state_64 t = { candidate };
				if (pcg_oneseq_64_xsh_rr_32_random_r(&t) == x0 
				 && pcg_oneseq_64_xsh_rr_32_random_r(&t) == x1
				 && pcg_oneseq_64_xsh_rr_32_random_r(&t) == x2) {
					return candidate;
				}
			}
		}
	}
	// Can't happen	
	abort();
}

// Pass an initial state (in decimal or hexadecimal), see it
// recovered from the output in a few seconds.

int main(int argc, char* argv[]) {
	if (argc != 2) {
		fprintf(stderr, "USAGE: %s STATE\n", argv[0]);
		exit(1);
	}

	const uint64_t initial = strtoull(argv[1], NULL, 0);
	if (errno) {
		fprintf(stderr, "%s\n", strerror(errno));
		exit(1);
	}

	// Computes three outputs (that should be enough, add another otherwise)
	rng.state = initial;
	const uint32_t x0 = pcg_oneseq_64_xsh_rr_32_random_r(&rng);
	const uint32_t x1 = pcg_oneseq_64_xsh_rr_32_random_r(&rng);
	const uint32_t x2 = pcg_oneseq_64_xsh_rr_32_random_r(&rng);

	printf("Provided generator state: %016" PRIx64 "\n", initial);
	printf("First three outputs: %08x, %08x, %08x\n", x0, x1, x2);
	const uint64_t recovered = recover(x0, x1, x2);
	printf("Recovered generator state (from output): %016" PRIx64 "\n", recovered);
}