MG Mud User | 88f1247 | 2016-06-24 23:31:02 +0200 | [diff] [blame^] | 1 | /* 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 | |
| 41 | private int polynom = DEFAULTP; |
| 42 | private int state = 2553647223; |
| 43 | //private int period; |
| 44 | |
| 45 | public 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 | |
| 62 | public 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 | |
| 84 | public 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 | |
| 103 | public 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 | |
| 113 | public int nextbyte() |
| 114 | { |
| 115 | return nextbits(8); |
| 116 | } |
| 117 | |
| 118 | public 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. |
| 128 | public void skipbits(int count) |
| 129 | { |
| 130 | foreach(int i: count) |
| 131 | nextbit(); |
| 132 | } |
| 133 | |
| 134 | |
| 135 | public 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 | |
| 145 | public 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 | |