blob: 8bd624c03e9a6db175cfa22d4e4f3a3b58b92d17 [file] [log] [blame]
/* Dieses File implementiert einen Pseudo-Zufallszahlengenerator mit einem
* Linear Feedback Shift Register in der Galois-Variante.
* Dieses PRNG ist schlechter und viel ineffizienter als der im Driver
* eingebaute.
* Die einzige sinnvolle Anwendung ist, wenn man aus irgendeinem Grund das
* seed selber waehlen muss, damit man die Sequenz von Pseudozufall immer
* wieder reproduzieren kann.
*
* Das Seed von der Blueprint wird vermutlich staendig veraendert (d.h.
* verlasst euch nicht drauf, dass es konstant bleibt), wollt ihr eine
* 'private' Instanz mit eurem Seed, clont das Objekt (aber verliert den Clone
* nicht).
*
* Es wird standardmaessig ein Polynom fuer eine Periodenlaenge von 2^32 - 1
* verwendet.
*
* Im Netz finden sich Infos ueber LFSRs und Tabellen fuer maximum-length
* feedback polynomials (M-Sequence Feedback Taps), falls jemand braucht.
*
*/
#pragma strong_types,rtt_checks,pedantic
#include <tls.h>
// Default-Polynom ist das:
// x^32 + x^31 + x^28 + x^27 + x^24 + x^23 + x^20 + x^19 + x^16 + x^15 + x^12
// + x^11 + x^8 + x^7 + x^5 + x^3 + 1
// Taps: 32, 31, 28, 27, 24, 23, 20, 19, 16, 15, 12, 11, 8, 7, 5, 3
// Binary: 110011001100110011001100110101000
#define DEFAULTP 0x1999999a8
// Andere gebraeuchliche:
// x^32 + x^30 + x^26 + x^25 + 1,
// Taps 32, 30, 26, 25
// Binary: 101000110000000000000000000000000
//#define DEFAULTP 0x146000000
// x^16 + x^14 + x^13 + x^11 + 1
// Taps 16, 14, 13, 11
// Binary: 1011010000000000
//#define DEFAULTP 0xB400
private int polynom = DEFAULTP;
private int state = 2553647223;
//private int period;
public varargs void init(int seed, int newp)
{
if (!seed)
raise_error("Illegal seed 0\n");
// Es darf nur ein 32 bit breiter Seed verwendet werden. Die oberen 32 bit
// werden mit den unteren 32 bit XOR-rt (also, einmal die oberen 32 shiften
// und einmal die oberen 32 wegmaskieren.
seed = ((seed>>32) & 0xffffffff) ^ (seed & 0xffffffff);
//printf("Seed: %064b - 0x%x\n",seed,seed);
if (!seed)
raise_error("Illegal reduced seed: 0\n");
state = seed;
polynom = newp || DEFAULTP;
}
public void InitWithUUID(string uuid)
{
string md5hash = hash(TLS_HASH_MD5, uuid);
int seed;
// 8 Bytes aus dem Hash ermitteln
foreach(int b: 16)
{
// Jeweils zwei Zeichen herausschneiden und als Hexadezimalzahl
// interpretieren, was jeweils ein byte (8 bit) gibt.
int tmp = to_int("0x"+md5hash[b*2..b*2+1]);
// diese werden dann in eine 64 bit breite Zahl zusammengefasst. Das
// gerade ermittelte Byte wird nach links geshiftet und mit dem, was da
// ggf. schon steht, XORred. Ist der int voll, faengt man wegen Modulo 64
// wieder rechts an.
//printf("S: %064b - %08b\n",seed,tmp);
seed = seed ^ (tmp << ((b*8)%64));
//printf("S: %064b - 0x%x\n",seed, seed);
}
//printf("Seed: 0x%x - %b\n",seed,seed);
init(seed);
}
public int nextbit()
{
// Get LSB (i.e., the output bit).
int lsb = state & 1;
// Shift register by one bit
state >>= 1;
// Apply a toggle mask, which flips all the tap bits, _if_ the output bit is
// 1. The mask has 1 at bits corresponding to taps, 0 elsewhere. In other
// words, the polynom from above.
if (lsb)
state ^= polynom;
// debug check ;-)
if (!state)
raise_error("State must not be zero, but it is.\n");
//++period;
//printf("State: %032b (Period: %d)\n",state,period);
return lsb;
}
public int nextbits(int count)
{
int result;
if (count>64)
raise_error(sprintf("Count is %d, but must be <= 64.\n",count));
foreach(int i: count)
result = (result << 1) | nextbit();
return result;
}
public int nextbyte()
{
return nextbits(8);
}
public int random(int n)
{
int rnd = nextbits(32);
//generates a random number on [0,1)-real-interval
float tmp = rnd * (1.0/4294967296.0);
// Skalieren auf [0,n)
return to_int(tmp * n);
}
// Just skip some bits and discard them.
public void skipbits(int count)
{
foreach(int i: count)
nextbit();
}
public void dumpstream(string file, int bytes)
{
int *stream = allocate(bytes);
foreach(int i: bytes)
{
stream[i] = nextbits(8);
}
write_file(file, sprintf("%@c",stream));
}
public int Configure(int data)
{
if (!data)
return state;
if (!intp(data))
return 0;
state = data;
return 1;
}