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. OK, I Understand
 
Top