• API
• FAQ
• Tools
• Archive
daily pastebin goal
24%
SHARE
TWEET

# Mersenne Twister / ISAAC RNG

Tatantyler Apr 14th, 2013 895 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. -- KillaVanilla's RNG('s), composed of the Mersenne Twister RNG and the ISAAC algorithm.
2.
3. -- Exposed functions:
4. -- initalize_mt_generator(seed) - Seed the Mersenne Twister RNG.
5. -- extract_mt() - Get a number from the Mersenne Twister RNG.
6. -- seed_from_mt(seed) - Seed the ISAAC RNG, optionally seeding the Mersenne Twister RNG beforehand.
7. -- generate_isaac() - Force a reseed.
8. -- random(min, max) - Get a random number between min and max.
9.
10. -- Helper functions:
11. local function toBinary(a) -- Convert from an integer to an arbitrary-length table of bits
12.         local b = {}
13.         local copy = a
14.         while true do
15.                 table.insert(b, copy % 2)
16.                 copy = math.floor(copy / 2)
17.                 if copy == 0 then
18.                         break
19.                 end
20.         end
21.         return b
22. end
23.
24. local function fromBinary(a) -- Convert from an arbitrary-length table of bits (from toBinary) to an integer
25.         local dec = 0
26.         for i=#a, 1, -1 do
27.                 dec = dec * 2 + a[i]
28.         end
29.         return dec
30. end
31.
32. -- ISAAC internal state:
33. local aa, bb, cc = 0, 0, 0
34. local randrsl = {} -- Acts as entropy/seed-in. Fill to randrsl[256].
35. local mm = {} -- Fill to mm[256]. Acts as output.
36.
37. -- Mersenne Twister State:
38. local MT = {} -- Twister state
39. local index = 0
40.
41. -- Other variables for the seeding mechanism
42. local mtSeeded = false
43. local mtSeed = math.random(1, 2^31-1)
44.
45. -- The Mersenne Twister can be used as an RNG for non-cryptographic purposes.
46. -- Here, we're using it to seed the ISAAC algorithm, which *can* be used for cryptographic purposes.
47.
48. function initalize_mt_generator(seed)
49.         index = 0
50.         MT[0] = seed
51.         for i=1, 623 do
52.                 local full = ( (1812433253 * bit.bxor(MT[i-1], bit.brshift(MT[i-1], 30) ) )+i)
53.                 local b = toBinary(full)
54.                 while #b > 32 do
55.                         table.remove(b, 1)
56.                 end
57.                 MT[i] = fromBinary(b)
58.         end
59. end
60.
61. local function generate_mt() -- Restock the MT with new random numbers.
62.         for i=0, 623 do
63.                 local y = bit.band(MT[i], 0x80000000)
64.                 y = y + bit.band(MT[(i+1)%624], 0x7FFFFFFF)
65.                 MT[i] = bit.bxor(MT[(i+397)%624], bit.brshift(y, 1))
66.                 if y % 2 == 1 then
67.                         MT[i] = bit.bxor(MT[i], 0x9908B0DF)
68.                 end
69.         end
70. end
71.
72. function extract_mt(min, max) -- Get one number from the Mersenne Twister.
73.         if index == 0 then
74.                 generate_mt()
75.         end
76.         local y = MT[index]
77.         min = min or 0
78.         max = max or 2^32-1
79.         --print("Accessing: MT["..index.."]...")
80.         y = bit.bxor(y, bit.brshift(y, 11) )
81.         y = bit.bxor(y, bit.band(bit.blshift(y, 7), 0x9D2C5680) )
82.         y = bit.bxor(y, bit.band(bit.blshift(y, 15), 0xEFC60000) )
83.         y = bit.bxor(y, bit.brshift(y, 18) )
84.         index = (index+1) % 624
85.         return (y % max)+min
86. end
87.
88. function seed_from_mt(seed) -- seed ISAAC with numbers from the MT:
89.         if seed then
90.                 mtSeeded = false
91.                 mtSeed = seed
92.         end
93.         if not mtSeeded or (math.random(1, 100) == 50) then -- Always seed the first time around. Otherwise, seed approximately once per 100 times.
94.                 initalize_mt_generator(mtSeed)
95.                 mtSeeded = true
96.                 mtSeed = extract_mt()
97.         end
98.         for i=1, 256 do
99.                 randrsl[i] = extract_mt()
100.         end
101. end
102.
103. local function mix(a,b,c,d,e,f,g,h)
104.         a = a % (2^32-1)
105.         b = b % (2^32-1)
106.         c = c % (2^32-1)
107.         d = d % (2^32-1)
108.         e = e % (2^32-1)
109.         f = f % (2^32-1)
110.         g = g % (2^32-1)
111.         h = h % (2^32-1)
112.          a = bit.bxor(a, bit.blshift(b, 11))
113.          d = (d + a) % (2^32-1)
114.          b = (b + c) % (2^32-1)
115.          b = bit.bxor(b, bit.brshift(c, 2) )
116.          e = (e + b) % (2^32-1)
117.      c = (c + d) % (2^32-1)
118.          c = bit.bxor(c, bit.blshift(d, 8) )
119.          f = (f + c) % (2^32-1)
120.          d = (d + e) % (2^32-1)
121.          d = bit.bxor(d, bit.brshift(e, 16) )
122.          g = (g + d) % (2^32-1)
123.          e = (e + f) % (2^32-1)
124.          e = bit.bxor(e, bit.blshift(f, 10) )
125.          h = (h + e) % (2^32-1)
126.          f = (f + g) % (2^32-1)
127.          f = bit.bxor(f, bit.brshift(g, 4) )
128.          a = (a + f) % (2^32-1)
129.          g = (g + h) % (2^32-1)
130.          g = bit.bxor(g, bit.blshift(h, 8) )
131.          b = (b + g) % (2^32-1)
132.          h = (h + a) % (2^32-1)
133.          h = bit.bxor(h, bit.brshift(a, 9) )
134.          c = (c + h) % (2^32-1)
135.          a = (a + b) % (2^32-1)
136.          return a,b,c,d,e,f,g,h
137. end
138.
139. local function isaac()
140.         local x, y = 0, 0
141.         for i=1, 256 do
142.                 x = mm[i]
143.                 if (i % 4) == 0 then
144.                         aa = bit.bxor(aa, bit.blshift(aa, 13))
145.                 elseif (i % 4) == 1 then
146.                         aa = bit.bxor(aa, bit.brshift(aa, 6))
147.                 elseif (i % 4) == 2 then
148.                         aa = bit.bxor(aa, bit.blshift(aa, 2))
149.                 elseif (i % 4) == 3 then
150.                         aa = bit.bxor(aa, bit.brshift(aa, 16))
151.                 end
152.                 aa = (mm[ ((i+128) % 256)+1 ] + aa) % (2^32-1)
153.                 y = (mm[ (bit.brshift(x, 2) % 256)+1 ] + aa + bb) % (2^32-1)
154.                 mm[i] = y
155.                 bb = (mm[ (bit.brshift(y,10) % 256)+1 ] + x) % (2^32-1)
156.                 randrsl[i] = bb
157.         end
158. end
159.
160. local function randinit(flag)
161.         local a,b,c,d,e,f,g,h = 0x9e3779b9,0x9e3779b9,0x9e3779b9,0x9e3779b9,0x9e3779b9,0x9e3779b9,0x9e3779b9,0x9e3779b9-- 0x9e3779b9 is the golden ratio
162.         aa = 0
163.         bb = 0
164.         cc = 0
165.         for i=1,4 do
166.                 a,b,c,d,e,f,g,h = mix(a,b,c,d,e,f,g,h)
167.         end
168.         for i=1, 256, 8 do
169.                 if flag then
170.                         a = (a + randrsl[i]) % (2^32-1)
171.                         b = (b + randrsl[i+1]) % (2^32-1)
172.                         c = (c + randrsl[i+2]) % (2^32-1)
173.                         d = (b + randrsl[i+3]) % (2^32-1)
174.                         e = (e + randrsl[i+4]) % (2^32-1)
175.                         f = (f + randrsl[i+5]) % (2^32-1)
176.                         g = (g + randrsl[i+6]) % (2^32-1)
177.                         h = (h + randrsl[i+7]) % (2^32-1)
178.                 end
179.                 a,b,c,d,e,f,g,h = mix(a,b,c,d,e,f,g,h)
180.                 mm[i] = a
181.                 mm[i+1] = b
182.                 mm[i+2] = c
183.                 mm[i+3] = d
184.                 mm[i+4] = e
185.                 mm[i+5] = f
186.                 mm[i+6] = g
187.                 mm[i+7] = h
188.         end
189.
190.         if flag then
191.                 for i=1, 256, 8 do
192.                         a = (a + randrsl[i]) % (2^32-1)
193.                         b = (b + randrsl[i+1]) % (2^32-1)
194.                         c = (c + randrsl[i+2]) % (2^32-1)
195.                         d = (b + randrsl[i+3]) % (2^32-1)
196.                         e = (e + randrsl[i+4]) % (2^32-1)
197.                         f = (f + randrsl[i+5]) % (2^32-1)
198.                         g = (g + randrsl[i+6]) % (2^32-1)
199.                         h = (h + randrsl[i+7]) % (2^32-1)
200.                         a,b,c,d,e,f,g,h = mix(a,b,c,d,e,f,g,h)
201.                         mm[i] = a
202.                         mm[i+1] = b
203.                         mm[i+2] = c
204.                         mm[i+3] = d
205.                         mm[i+4] = e
206.                         mm[i+5] = f
207.                         mm[i+6] = g
208.                         mm[i+7] = h
209.                 end
210.         end
211.         isaac()
212.         randcnt = 256
213. end
214.
215. function generate_isaac(entropy)
216.         aa = 0
217.         bb = 0
218.         cc = 0
219.         if entropy and #entropy >= 256 then
220.                 for i=1, 256 do
221.                         randrsl[i] = entropy[i]
222.                 end
223.         else
224.                 seed_from_mt()
225.         end
226.         for i=1, 256 do
227.                 mm[i] = 0
228.         end
229.         randinit(true)
230.         isaac()
231.         isaac() -- run isaac twice
232. end
233.
234. local function getRandom()
235.         if #mm > 0 then
236.                 return table.remove(mm, 1)
237.         else
238.                 generate_isaac()
239.                 return table.remove(mm, 1)
240.         end
241. end
242.
243. function random(min, max)
244.         if not max then
245.                 max = 2^32-1
246.         end
247.         if not min then
248.                 min = 0
249.         end
250.         return (getRandom() % max) + min
251. end
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top