RNG

1 files changed, 78 insertions, 0 deletions

diff --git a/rng.cpp b/rng.cpp
new file mode 100644
index 0000000..c9e7f03
--- /dev/null
+++ b/rng.cpp
@@ -0,0 +1,78 @@
+// #include <iostream>
+// #include <bitset>
+#include <cstring>
+#include <cassert>
+#include "rng.h"
+
+using namespace std;
+
+
+//adapted from http://blog.regehr.org/archives/1063 (rotl32c version)
+inline uint64_t rotl64(uint64_t x,uint32_t n){
+	assert(n<64);
+	return (x<<n)|(x>>(-n&63));
+}
+inline uint64_t rotr64(uint64_t x,uint32_t n){
+	assert(n<64);
+	return (x>>n)|(x<<(-n&63));
+}
+
+KeyRng::KeyRng(const char *key_,int keylen_)
+		:keylen(keylen_),idx(0),state(0){
+	assert(keylen>0);
+	assert(key_);
+	key=new uint8_t[keylen];
+	memcpy(key,key_,keylen);
+	stir();
+}
+
+KeyRng::KeyRng(const string &key_)
+		:keylen(key_.size()),idx(0),state(0){
+	assert(keylen>0);
+	key=new uint8_t[keylen];
+	memcpy(key,key_.data(),keylen);
+	stir();
+}
+
+KeyRng::~KeyRng(){
+	delete[] key;
+}
+
+void KeyRng::stir(){
+	for(int i=0;i<10;i++)get();
+}
+
+uint32_t KeyRng::get(){
+	//Progressively and cyclicly mixes in the key with the state.
+	//Mostly own creation; the "tempering" part is derived from a (part of a) Mersenne Twister implementation.
+	//In terms of distribution of values, this is similar to arc4random().
+	//This passes DieHarder 3.31.1 (tested 2016/10/06) with 2 "weak" results. The initial key "wachtwoord" was used.
+	//At least n subsequent values should be independent, where n is the length of the initial key.
+	state^=key[idx];
+	state+=17;
+	key[idx]+=13;
+	idx=(idx+1)%keylen;
+	state^=rotr64(state,11); //tempering
+	state^=rotl64(state,7)&0x9d2c5680;
+	state^=rotr64(state,18);
+	// cerr<<bitset<64>(state)<<endl;
+	return state>>32;
+}
+
+uint32_t KeyRng::get_uniform(uint32_t upbound){
+	if(upbound<=1)return 0;
+	uint32_t min=((uint64_t)1<<32)%upbound; //this is the amount of unusable RNG outputs when avoiding modulo bias
+	while(true){
+		uint32_t v=get();
+		if(v>=min)return v%upbound;
+	}
+}
+
+
+uint32_t Arc4Rng::get(){
+	return arc4random();
+}
+
+uint32_t Arc4Rng::get_uniform(uint32_t upbound){
+	return arc4random_uniform(upbound);
+}