Created
March 13, 2013 16:34
-
-
Save loreb/5153866 to your computer and use it in GitHub Desktop.
Bob Jenkins' ISAAC implementation converted to Vimscript (http://www.burtleburtle.net/bob/rand/isaacafa.html).
At least three orders of magnitude slower than the C version.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
" http://www.burtleburtle.net/bob/c/readable.c | |
" ---------------------------------------------------------------------------- | |
" readable.c: My random number generator, ISAAC. | |
" (c) Bob Jenkins, March 1996, Public Domain | |
" You may use this code in any way you wish, and it is free. No warrantee. | |
" * May 2008 -- made it not depend on standard.h | |
" ---------------------------------------------------------------------------- | |
" /* a ub4 is an unsigned 4-byte quantity */ | |
" typedef uint32_t ub4 | |
if 0x7fffffff <= 0 || 0x7fffffff+1 >= 0 | |
throw '32 bits -- TODO 64 bits?' | |
endif | |
" Shift 32 bit numbers left/right {{{ | |
let s:pow2 = [ | |
\ 0x1, 0x2, 0x4, 0x8, | |
\ 0x10, 0x20, 0x40, 0x80, | |
\ 0x100, 0x200, 0x400, 0x800, | |
\ 0x1000, 0x2000, 0x4000, 0x8000, | |
\ 0x10000, 0x20000, 0x40000, 0x80000, | |
\ 0x100000, 0x200000, 0x400000, 0x800000, | |
\ 0x1000000, 0x2000000, 0x4000000, 0x8000000, | |
\ 0x10000000, 0x20000000, 0x40000000 | |
\ ] | |
function! s:rightshift(x, n) | |
if a:n == 0 | |
return a:x | |
endif | |
if a:x < 0 | |
" shift 1 manually ==> make positive | |
let y = or(0x40000000, and(a:x, 0x7fffffff) / 2) | |
return s:rightshift(y, a:n-1) | |
endif | |
return a:x / s:pow2[a:n] | |
endfunction | |
function! s:leftshift(x, n) | |
return a:x * s:pow2[a:n] | |
endfunction | |
" }}} | |
" /* external results */ | |
" ub4 randrsl[256], randcnt | |
let s:randrsl = repeat([0], 256) | let s:randcnt = 0 | |
" /* internal state */ | |
let s:mm = repeat([0], 256) | |
let s:aa = 0 | let s:bb = 0 | let s:cc = 0 | |
function! s:isaac() | |
" register ub4 i, x, y | |
let s:cc += 1 " /* cc just gets incremented once per 256 results */ | |
let s:bb += s:cc " /* then combined with bb */ | |
for i in range(256) | |
let x = s:mm[i] | |
let i4 = i%4 | |
if i4 == 0 | |
let s:aa = xor(s:aa, s:leftshift(s:aa, 13)) | |
elseif i4 == 1 | |
let s:aa = xor(s:aa, s:rightshift(s:aa, 6)) | |
elseif i4 == 2 | |
let s:aa = xor(s:aa, s:leftshift(s:aa, 2)) | |
else | |
let s:aa = xor(s:aa, s:rightshift(s:aa, 16)) | |
endif | |
let s:aa = s:mm[(i + 128) % 256] + s:aa | |
let y = s:mm[s:rightshift(x, 2) % 256] + s:aa + s:bb | let s:mm[i] = y | |
let s:bb = s:mm[s:rightshift(y, 10) % 256] + x | let s:randrsl[i] = s:bb | |
" /* Note that bits 2..9 are chosen from x but 10..17 are chosen | |
" from y. The only important thing here is that 2..9 and 10..17 | |
" don't overlap. 2..9 and 10..17 were then chosen for speed in | |
" the optimized version (rand.c) */ | |
" /* See http://burtleburtle.net/bob/rand/isaac.html | |
" for further explanations and analysis. */ | |
endfor | |
endfunction | |
" /* if (flag!=0), then use the contents of randrsl[] to initialize mm[]. */ | |
" Vim: structs are faked with hashtables + syntactic sugar (sounds familiar); | |
" Vim: microbenchmark says structs are ~10% slower than variable name lookup. | |
" #define mix(a,b,c,d,e,f,g,h) \ | |
function! s:mix(x) | |
let x = a:x | |
let x.a = xor(x.a, s:leftshift(x.b,11)) | let x.d+=x.a | let x.b+=x.c | |
let x.b = xor(x.b, s:rightshift(x.c,2)) | let x.e+=x.b | let x.c+=x.d | |
let x.c = xor(x.c, s:leftshift(x.d,8)) | let x.f+=x.c | let x.d+=x.e | |
let x.d = xor(x.d, s:rightshift(x.e,16)) | let x.g+=x.d | let x.e+=x.f | |
let x.e = xor(x.e, s:leftshift(x.f,10)) | let x.h+=x.e | let x.f+=x.g | |
let x.f = xor(x.f, s:rightshift(x.g,4)) | let x.a+=x.f | let x.g+=x.h | |
let x.g = xor(x.g, s:leftshift(x.h,8)) | let x.b+=x.g | let x.h+=x.a | |
let x.h = xor(x.h, s:rightshift(x.a,9)) | let x.c+=x.h | let x.a+=x.b | |
endfunction | |
function! s:randinit(flag) " int flag -- in vim, 'y' evaluates to zero. | |
" ub4 a, b, c, d, e, f, g, h | |
let s:aa = 0 | let s:bb = 0 | let s:cc = 0 | |
" a = b = c = d = e = f = g = h = 0x9e3779b9; /* the golden ratio */ | |
let x = {} " see s:mix() | |
for field in [ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' ] | |
let x[field] = 0x9e3779b9 " /* the golden ratio */ | |
endfor | |
for i in range(4) " /* scramble it */ | |
" mix(a, b, c, d, e, f, g, h) | |
call s:mix(x) | |
endfor | |
" Vim's range() is such a mess... | |
let i = 0 | |
while i < 256 | |
" for (i = 0; i < 256; i += 8) { /* fill in mm[] with messy stuff */ | |
if a:flag " /* use all the information in the seed */ | |
let x.a += s:randrsl[i] | |
let x.b += s:randrsl[i + 1] | |
let x.c += s:randrsl[i + 2] | |
let x.d += s:randrsl[i + 3] | |
let x.e += s:randrsl[i + 4] | |
let x.f += s:randrsl[i + 5] | |
let x.g += s:randrsl[i + 6] | |
let x.h += s:randrsl[i + 7] | |
endif | |
call s:mix(x) | |
let s:mm[i] = x.a | |
let s:mm[i + 1] = x.b | |
let s:mm[i + 2] = x.c | |
let s:mm[i + 3] = x.d | |
let s:mm[i + 4] = x.e | |
let s:mm[i + 5] = x.f | |
let s:mm[i + 6] = x.g | |
let s:mm[i + 7] = x.h | |
let i += 8 | |
endwhile | |
if a:flag " /* do a second pass to make all of the seed affect all of mm */ | |
let i = 0 | |
while i < 256 | |
let x.a += s:mm[i] | |
let x.b += s:mm[i + 1] | |
let x.c += s:mm[i + 2] | |
let x.d += s:mm[i + 3] | |
let x.e += s:mm[i + 4] | |
let x.f += s:mm[i + 5] | |
let x.g += s:mm[i + 6] | |
let x.h += s:mm[i + 7] | |
call s:mix(x) " (a, b, c, d, e, f, g, h) | |
let s:mm[i] = x.a | |
let s:mm[i + 1] = x.b | |
let s:mm[i + 2] = x.c | |
let s:mm[i + 3] = x.d | |
let s:mm[i + 4] = x.e | |
let s:mm[i + 5] = x.f | |
let s:mm[i + 6] = x.g | |
let s:mm[i + 7] = x.h | |
let i += 8 | |
endwhile | |
endif | |
call s:isaac() " /* fill in the first set of results */ | |
let s:randcnt = 256 " /* prepare to use the first set of results */ | |
endfunction | |
" Pass an array with 256 ints, or no argument for default seed. | |
function! Randinit(...) | |
if a:0 > 1 | |
throw 'Randinit(seed[256])' | |
endif | |
if a:0 == 0 | |
call s:randinit(0) | |
else | |
let a = a:1 | |
if len(a) != 256 | |
throw printf("seed[%d]", len(a)) | |
endif | |
for i in range(len(a)) | |
let s:randrsl[i] = a[i] | |
endfor | |
call s:randinit(1) | |
endif | |
endfunction | |
" $ grep Hz /proc/cpuinfo | |
" cpu MHz : 1800.000 | |
" 10k calls in just above 2 seconds. | |
function! RandIsaac() | |
" The original API is to expose randrsl and randcnt; | |
" I prefer returning single integers. | |
if s:randcnt == 0 | |
call s:isaac() | |
let s:randcnt = 256 | |
endif | |
let s:randcnt -= 1 | |
return s:randrsl[s:randcnt] | |
endfunction | |
if len($DEBUG) > 0 | |
" This must output the same string as readable.c -- ok. | |
let s:aa = 0 | let s:bb = 0 | let s:cc = 0 | |
for i in range(256) | |
let s:mm[i] = 0 | |
let s:randrsl[i] = 0 | |
endfor | |
call s:randinit(1) | |
for i in range(2) | |
call s:isaac() | |
let h = '' | |
for j in range(256) | |
" let h .= printf("%.8lx", s:randrsl[j]) | |
let h .= printf("%.8x", s:randrsl[j]) | |
if and(j, 7) == 7 | |
echomsg h | |
let h = '' | |
endif | |
endfor | |
if len(h) > 0 | |
throw 'bug!' | |
endif | |
endfor | |
else | |
" Seed! | |
call s:randinit(0) | |
endif | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment