blob: 8bd624c03e9a6db175cfa22d4e4f3a3b58b92d17 [file] [log] [blame]
MG Mud User88f12472016-06-24 23:31:02 +02001/* Dieses File implementiert einen Pseudo-Zufallszahlengenerator mit einem
2 * Linear Feedback Shift Register in der Galois-Variante.
3 * Dieses PRNG ist schlechter und viel ineffizienter als der im Driver
4 * eingebaute.
5 * Die einzige sinnvolle Anwendung ist, wenn man aus irgendeinem Grund das
6 * seed selber waehlen muss, damit man die Sequenz von Pseudozufall immer
7 * wieder reproduzieren kann.
8 *
9 * Das Seed von der Blueprint wird vermutlich staendig veraendert (d.h.
10 * verlasst euch nicht drauf, dass es konstant bleibt), wollt ihr eine
11 * 'private' Instanz mit eurem Seed, clont das Objekt (aber verliert den Clone
12 * nicht).
13 *
14 * Es wird standardmaessig ein Polynom fuer eine Periodenlaenge von 2^32 - 1
15 * verwendet.
16 *
17 * Im Netz finden sich Infos ueber LFSRs und Tabellen fuer maximum-length
18 * feedback polynomials (M-Sequence Feedback Taps), falls jemand braucht.
19 *
20*/
21#pragma strong_types,rtt_checks,pedantic
22
23#include <tls.h>
24
25// Default-Polynom ist das:
26// x^32 + x^31 + x^28 + x^27 + x^24 + x^23 + x^20 + x^19 + x^16 + x^15 + x^12
27// + x^11 + x^8 + x^7 + x^5 + x^3 + 1
28// Taps: 32, 31, 28, 27, 24, 23, 20, 19, 16, 15, 12, 11, 8, 7, 5, 3
29// Binary: 110011001100110011001100110101000
30#define DEFAULTP 0x1999999a8
31// Andere gebraeuchliche:
32// x^32 + x^30 + x^26 + x^25 + 1,
33// Taps 32, 30, 26, 25
34// Binary: 101000110000000000000000000000000
35//#define DEFAULTP 0x146000000
36// x^16 + x^14 + x^13 + x^11 + 1
37// Taps 16, 14, 13, 11
38// Binary: 1011010000000000
39//#define DEFAULTP 0xB400
40
41private int polynom = DEFAULTP;
42private int state = 2553647223;
43//private int period;
44
45public varargs void init(int seed, int newp)
46{
47 if (!seed)
48 raise_error("Illegal seed 0\n");
49 // Es darf nur ein 32 bit breiter Seed verwendet werden. Die oberen 32 bit
50 // werden mit den unteren 32 bit XOR-rt (also, einmal die oberen 32 shiften
51 // und einmal die oberen 32 wegmaskieren.
52 seed = ((seed>>32) & 0xffffffff) ^ (seed & 0xffffffff);
53 //printf("Seed: %064b - 0x%x\n",seed,seed);
54
55 if (!seed)
56 raise_error("Illegal reduced seed: 0\n");
57
58 state = seed;
59 polynom = newp || DEFAULTP;
60}
61
62public void InitWithUUID(string uuid)
63{
64 string md5hash = hash(TLS_HASH_MD5, uuid);
65 int seed;
66 // 8 Bytes aus dem Hash ermitteln
67 foreach(int b: 16)
68 {
69 // Jeweils zwei Zeichen herausschneiden und als Hexadezimalzahl
70 // interpretieren, was jeweils ein byte (8 bit) gibt.
71 int tmp = to_int("0x"+md5hash[b*2..b*2+1]);
72 // diese werden dann in eine 64 bit breite Zahl zusammengefasst. Das
73 // gerade ermittelte Byte wird nach links geshiftet und mit dem, was da
74 // ggf. schon steht, XORred. Ist der int voll, faengt man wegen Modulo 64
75 // wieder rechts an.
76 //printf("S: %064b - %08b\n",seed,tmp);
77 seed = seed ^ (tmp << ((b*8)%64));
78 //printf("S: %064b - 0x%x\n",seed, seed);
79 }
80 //printf("Seed: 0x%x - %b\n",seed,seed);
81 init(seed);
82}
83
84public int nextbit()
85{
86 // Get LSB (i.e., the output bit).
87 int lsb = state & 1;
88 // Shift register by one bit
89 state >>= 1;
90 // Apply a toggle mask, which flips all the tap bits, _if_ the output bit is
91 // 1. The mask has 1 at bits corresponding to taps, 0 elsewhere. In other
92 // words, the polynom from above.
93 if (lsb)
94 state ^= polynom;
95 // debug check ;-)
96 if (!state)
97 raise_error("State must not be zero, but it is.\n");
98 //++period;
99 //printf("State: %032b (Period: %d)\n",state,period);
100 return lsb;
101}
102
103public int nextbits(int count)
104{
105 int result;
106 if (count>64)
107 raise_error(sprintf("Count is %d, but must be <= 64.\n",count));
108 foreach(int i: count)
109 result = (result << 1) | nextbit();
110 return result;
111}
112
113public int nextbyte()
114{
115 return nextbits(8);
116}
117
118public int random(int n)
119{
120 int rnd = nextbits(32);
121 //generates a random number on [0,1)-real-interval
122 float tmp = rnd * (1.0/4294967296.0);
123 // Skalieren auf [0,n)
124 return to_int(tmp * n);
125}
126
127// Just skip some bits and discard them.
128public void skipbits(int count)
129{
130 foreach(int i: count)
131 nextbit();
132}
133
134
135public void dumpstream(string file, int bytes)
136{
137 int *stream = allocate(bytes);
138 foreach(int i: bytes)
139 {
140 stream[i] = nextbits(8);
141 }
142 write_file(file, sprintf("%@c",stream));
143}
144
145public int Configure(int data)
146{
147 if (!data)
148 return state;
149
150 if (!intp(data))
151 return 0;
152 state = data;
153 return 1;
154}
155