Advertisement
Tatantyler

Mersenne Twister / ISAAC RNG

Apr 14th, 2013
1,730
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Lua 6.26 KB | None | 0 0
  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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement