IA.vim

" http://burtleburtle.net/bob/rand/isaac.html#IAcode
" IA was designed to satisfy these goals:
"
"    Deducing the internal state from the results should be intractable.
"    The code should be easy to memorize.
"    It should be as fast as possible.

" {{{ bitwise shifts.
if 0x7fffffff <= 0 || 0x7fffffff+1 >= 0
    " Need to:
    " 1. fix bitwise operations
    " 2. fix test data (or report missing)
    throw "TODO IA is actually ok for any wordsize >= 2*ALPHA bits!"
endif
let s:p2 = [1]
for i in range(30)
    let s:p2 += [ s:p2[i] * 2 ]
endfor
if s:p2[3] != 8 | throw "p2 bug" | endif
function! s:lshift(x, nbits)
    return a:x * s:p2[a:nbits]
endfunction
function! s:rshift(x, nbits)
    if a:x < 0
        if ! a:nbits | return a:x | endif
        " nonzero shift: sign bit would be cleared anyway
        let shifted1 = or(0x40000000, and(a:x, 0x7fffffff) / 2)
        return s:rshift(shifted1, a:nbits-1)
    endif
    return a:x / s:p2[a:nbits]
endfunction
" }}}

let s:ALPHA = 8
let IA_SIZE  = s:lshift(1, s:ALPHA)
function! s:ind(x)
    return and(a:x, g:IA_SIZE-1)
endfunction

"static void ia(m,r,bb)
"u4 *m;   /* Memory: array of IA_SIZE ALPHA-bit terms */
"u4 *r;   /* Results: the sequence, same size as m */
"u4 *bb;  /* the previous result */
function! s:ia(m, r, bb)
    let b = a:bb
    for i in range(g:IA_SIZE)
        let x = a:m[i]
        " a=b=c isn't in vim
        let y = a:m[s:ind(x)] + b
        let a:m[i] = y    " set m
        let b = a:m[s:ind(s:rshift(y,s:ALPHA))] + x
        let a:r[i] = b    " set r
    endfor
    return b
endfunction

" XXX "Unlike RC4, the values in m should contain at least 2ALPHA bits":
"
" This technically means that you should use at least uint16(**),
" but in the past I misunderstood it to mean "the state shall have
" at leat 2ALPHA bits set"; this requirement is because y>>ALPHA
" must have enough bits to index an array with 1<<ALPHA elements.
"
" (**) misleading since his example uses uint32...

" XXX The comment "/* Memory: array of SIZE ALPHA-bit terms */"
" seems to suggest a terrifying idea... whatever, even if it is,
" IA() works perfectly fine generating integers >= 2ALPHA bits.
function! IA()
    " This is ~10x slower than Xkcd221()
    if 0 == s:rng.numsleft
        let s:rng.bb = s:ia(s:rng.m, s:rng.r, s:rng.bb)
        let s:rng.numsleft = g:IA_SIZE-1
    else
        let s:rng.numsleft -= 1
    endif
    return s:rng.r[s:rng.numsleft]
endfunction

" Initialization is a bit tricky, and **not** documented.
" Because IA works using only addition of (last result, values in m[]),
" at least one of (m[],bb) must be odd (cfr. lagged fibonacci).
" This guarantees we never get into an "all even" state
" --proof:
"       we __trivially__ can't get out of an "all even" state by calling IA();
"       but IA() is reversible, so after long enough we should get
"       back to the (not "all even") initial state - QED.
"       [We may still be stuck in a short cycle :]
" A super-simple way to enforce this is to use an odd value for "bb".
"
" Notice also that IA() is **slow** at getting out of a mostly-zero state!!!
" Try eg m=[0xFFFFFFFF, 0..0],b=0 and see for yourself...
function s:all_even(A)
    for n in a:A
        if n % 2
            return 0
        endif
    endfor
    return 1
endfunction
function! IA_seed(m, ...)
    if len(a:m) != g:IA_SIZE
        throw printf("IA(m[%d]) - length should be %d", len(a:m), g:IA_SIZE)
    endif
    let bb = 0x1a5eed   " any odd value
    let warmup = 0
    if a:0 == 1 " a:0 is # of optional arguments
        let warmup = a:1
    endif
    let x = {}
    let x.numsleft = 0
    let x.m = copy(a:m)
    let x.r = range(256) " will be overwritten
    let x.bb = bb
    if s:all_even(x.m + [x.bb])
        throw "IA([all even]) => [all even]"
    endif
    let s:rng = x   " not seeded => E121 undefined variable
    " "warmup" is measured in rounds, not numbers skipped.
    for i in range(warmup)
        for j in range(g:IA_SIZE)
            call IA()
        endfor
    endfor
endfunction

" TODO IA_srand()
if 1    " Ensure it is initialized; crappy, enough for pracrand (4GB,twice)
    let m = range(g:IA_SIZE)
    let m[0] = v:version
    let m[1] = localtime()
    let m[2] = getpid()
    for i in range(3, g:IA_SIZE - 1)
        let m[i] += m[i-2] * 0xabcd
    endfor
    call IA_seed(m, 3)
endif

if len($DEBUG) > 0
    echomsg 'testing IA()...'
    let seed = range(256)
    call IA_seed(seed)
    let s:rng.bb = 0
    let toskip = 12345
    echomsg printf("skip %d numbers...", toskip)
    for i in range(toskip)
        call IA()
    endfor
    " test data {{{
    let wanted = [
                \ 682770751, 202370840, 1659755063,
                \ 201515335, 3744739662, 290014044,
                \ 4230394385, 2095749816, 2017529560,
                \ 220196879, 2578162933, 841868531,
                \ 3283917246, 3752146780, 227508933,
                \ 2312258408, 2132762797, 3982514702,
                \ 455538537, 650270402, 2849063617,
                \ 3894684160, 346054575, 4074495357,
                \ 1000635744, 1769256658, 3598136081,
                \ 2708108429, 4079244707, 1256051634,
                \ 794199801, 480094484, 3920141609,
                \ 608064421, 3374004227, 715612082,
                \ 1103973707, 2602929887, 1952772700,
                \ 1875731997, 1107366261, 3000158353,
                \ 3439922618, 4264682574, 3785237167,
                \ 2466440741, 3155059477, 3321966149,
                \ 797145535, 4029367313, 2390499563,
                \ 1176747889, 4077878308, 2108489013,
                \ 2139933093, 2939777267, 3695736275,
                \ 4241460930, 3486232558, 1524621020,
                \ 3328088944, 1121124269, 769597369,
                \ 3924597833, 987470339, 280213856,
                \ 3709621268, 2524501306, 2088932708,
                \ 2319670508, 745692457, 1759458762,
                \ 4138282667, 1899329623, 4185213277,
                \ 2545110319, 856127362, 4210657296,
                \ 378718283, 2444119293, 1055298676,
                \ 3333023370, 3325395720, 21513781,
                \ 440466309, 1092840752, 3202445045,
                \ 3284675087, 337021248, 1823129402,
                \ 3658864861, 341923757, 2522009002,
                \ 4181247571, 71973246, 2589385034,
                \ 1377261112, 3335744764, 3226356650,
                \ 2173377915, 3659884748, 567598143,
                \ 1371369438, 2931349681, 706678903,
                \ 3929806024, 2165928073, 2662133603,
                \ 998376191, 1244263378, 1621408466,
                \ 4089943486, 2300894724, 471789511,
                \ 1006347374, 56187779, 2088247017,
                \ 2027440856, 3665582494, 1021524363,
                \ 1944464664, 3797388592, 207383488,
                \ 2689342774, 2786961173, 3398859669,
                \ 2792677025, 2669027254, 3953422864,
                \ 1552867139, 3510061684, 2294910963,
                \ 2273459806, 3796257496, 2681268246,
                \ 2268846234, 1300826435, 2214437491,
                \ 3140540045, 286489442, 314514648,
                \ 2762314631, 2530433264, 2930405990,
                \ 35623206, 2793556056, 2517131491,
                \ 897579152, 2605887378, 2365962101,
                \ 169188968, 3084464974, 765161617,
                \ 278603821, 1822715760, 939618329,
                \ 236414971, 1020073139, 834324686,
                \ 265298401, 3537821968, 1374353490,
                \ 3307611301, 2339740759, 1795222517,
                \ 805139588, 3135605467, 596905610,
                \ 1005977580, 2002856081, 4252641760,
                \ 2789733400, 1114048040, 1047828065,
                \ 1584173131, 4143071673, 3834514264,
                \ 399648544, 1549613476, 1783357071,
                \ 3765427007, 2827200129, 4140399978,
                \ 3592713207, 3956783409, 2794714782,
                \ 2715771979, 2547148461, 2483142943,
                \ 1620150928, 2542070569, 1970034153,
                \ 2760428226, 740615411, 2127554532,
                \ 705932557, 353358523, 1957186936,
                \ 2571506503, 937379206, 1783227127,
                \ 3794923655, 3894285461, 75975171,
                \ 1522253826, 2337324831, 3136856325,
                \ 1545034510, 3178151334, 4253608890,
                \ 1273136174, 2891623159, 3126761730,
                \ 2307011030, 639232003, 919198941,
                \ 424020881, 2236335699, 2239906733,
                \ 3017243360, 3043479375, 2377620129,
                \ 2909075542, 3766770138, 4271672106,
                \ 1812085812, 3974462064, 213816164,
                \ 2319489518, 3727833273, 578769343,
                \ 1200922345, 3203773654, 2338792550,
                \ 3522081791, 1352560907, 1009889558,
                \ 1034065116, 514610327, 190474039,
                \ 357995783, 6482803, 3073670930,
                \ 3278247313, 1304270038, 1777065249,
                \ 645001840, 2823058787, 3465400515,
                \ 3353367052, 1135619576, 3799013637,
                \ 1618081652, 3618943645, 586667915,
                \ 795478459, 355451167, 3821494902,
                \ 4129451237, 52384632, 1911702954,
                \ 2904776302, 144364292, 634870290,
                \ 476857825, 3926616828, 2116164658,
                \ 207486675, 3614257095, 2897017513,
                \ 2288046283, 4123044772, 2652422826,
                \ 3475505183, 2380569110, 1576765626,
                \ 3693528695, 3631083047, 320033888,
                \ 404408465, 97089641, 140842766,
                \ 3782529106, 4207029151, 1963678263,
                \ 26973309, 575258436, 3048519821,
                \ 338651963, 2891646838, 515048326,
                \ 2711393284, 3023005598, 4106035433,
                \ 1961524865, 2531973706, 2348787396,
                \ 1223718621, 1303424941, 3956775264,
                \ 2603458768, 972517737, 2958030269,
                \ 2614469846, 3945813578, 121191208,
                \ 1214900548, 2748283286, 1402114054,
                \ 1524163465, 733766699, 2730641675,
                \ 4027550676, 739627239, 30278853,
                \ 3807857276, 1073058123, 1026175728,
                \ 4198973623, 3713845575, 3346741766,
                \ 1854346996, 437965585, 1051733074,
                \ 3267449458, 2353821834, 4011899591,
                \ 987589769, 4278063190, 3085295821,
                \ 4066956608, 3056680290, 3608083466,
                \ 2393132692, 4190341265, 3860521919,
                \ 1146021955, 104070810, 465287216,
                \ 3366517348, 3656477986, 734114981,
                \ 2115588334, 3193706929, 1934030058,
                \ 1135572836, 1094331587, 3314633633,
                \ 4067991417, 2680743072, 3244647347,
                \ 2185998298, 1573137886, 449139408,
                \ 4281116468, 2323449420, 3101109492,
                \ 3124521004, 430200255, 3391307914,
                \ 1553240602, 2708193827, 2292616049,
                \ 1219301775, 2440823335, 2681206228,
                \ 3833407422, 2189619913, 2974842573,
                \ 2589328461, 3975972121, 3295803499,
                \ 3710953329, 2716512123, 321940237,
                \ 4052604235, 3476054929, 903389424,
                \ 3855789469, 883291410, 2525067551,
                \ 226820213, 2736424920, 2787554804,
                \ 3253544857, 191511743, 928693033,
                \ 2245391144, 2297336709, 4138608368,
                \ 2577940554, 117725487, 2991833920,
                \ 725787036, 1285643750, 3683471987,
                \ 358436672, 929202039, 1384195556,
                \ 609571389, 2923879946, 3577260006,
                \ 3594296807, 2914043013, 1451037886,
                \ 2877411867, 2333972228, 3637185555,
                \ 3774092780, 1765651001, 671418260,
                \ 441831046, 3032374534, 1062601043,
                \ 45472381, 3511037431, 2294139752,
                \ 1395065273, 955397137, 103610856,
                \ 1699857746, 249314980, 1750548302,
                \ 4169350131, 2419496640, 1999591658,
                \ 145789495, 1196415518, 2377945831,
                \ 223031959, 226846393, 693242088,
                \ 303217878, 3038820238, 145425886,
                \ 3101482922, 1326112946, 1860452751,
                \ 572661160, 114688745, 3957866596,
                \ 4050626989, 735134060, 3795552504,
                \ 2045492859, 669947398, 1653807372,
                \ 3665056381, 1412831433, 709447865,
                \ 151874675, 2599801200, 2740182388,
                \ 1764040606, 2487418217, 4205657817,
                \ 4130824189, 3540432198, 2580802698,
                \ 2357808023, 1375946283, 3580510094,
                \ 810673654, 1088304493, 357745849,
                \ 3320471552, 1817834973, 377872273,
                \ 661154454, 61152437, 3294607851,
                \ 1132202361, 891084971, 4063996413,
                \ 3387356785, 4218931145, 2438515849,
                \ 2456664957, 3006775217, 974682746,
                \ 2493546483, 1971232603, 4123229754,
                \ 1883053782, 4291808320, 1433233903,
                \ 3686788296, 217547124, 474797644,
                \ 1841062352, 2864325898, 1703023583,
                \ 2428472851, 611001806, 3372207049,
                \ 3704618796, 4035036663, 13518954,
                \ 4271370905, 1836237475, 1013744111,
                \ 1645779890, 567520820, 4132702622,
                \ 416936475, 1213897460, 371815172,
                \ 1139908056, 2677606123, 353422195,
                \ 3419973855, 365579201, 3589158038,
                \ 3897598587, 996448123, 2657643903,
                \ 1046019032, 1012260695, 3979004786,
                \ 3361424210, 3782542941, 3615716449,
                \ 1817165128, 2721909352, 294186482,
                \ 488681913, 1445958411, 317099347,
                \ 3049353716, 3665759613, 2813231448,
                \ 3932120581, 2976068788, 4179485121,
                \ 1371052719, 4217799026, 3863794286,
                \ 1863593855, 3079903954, 3100041193,
                \ 2800864246, 3764314408, 3906997355,
                \ 3980351697, 786998631, 541602333,
                \ 3081666215, 3526251937, 3144517885,
                \ 2611582714, 4222372243, 955880989,
                \ 1069893981, 3298638493, 2467763106,
                \ 1314323319, 188047779, 440241568,
                \ 2020657876, 1427130383, 1561035880,
                \ 3963049297, 3973279828, 388591619,
                \ 3232677853, 1428594074, 141943184,
                \ 2482751599, 2235141060, 3236169833,
                \ 79999396, 948398460, 696701716,
                \ 3425052149, 1277832825, 3763684464,
                \ 1255800305, 297559060, 3473009217,
                \ 4215538464, 2765420661, 4013853409,
                \ 2524913851, 3245456049, 2036803265,
                \ 3640340512, 2104049363, 1918030736,
                \ 2640751527, 1882312606, 1296465522,
                \ 2703697859, 503956567, 3552132700,
                \ 1105027829, 3329842513, 821824676,
                \ 2414277600, 2666165083, 3134012190,
                \ 3738112651, 3959934276, 1498180771,
                \ 2338231736, 1526240537, 2894047196,
                \ 2628807421, 4278527254, 2158065956,
                \ 3006423447, 3512669785, 3393647115,
                \ 1752896273, 2074610661, 2446805505,
                \ 2158260853, 3103079553, 4058574093,
                \ 3069424148, 1308654880, 3716366296,
                \ 887702812, 3052440697, 3039461501,
                \ 3820945798, 387264184, 2403303908,
                \ 1051295727, 548420493, 3999415282,
                \ 3274730957, 2294411886, 3151960667,
                \ 53153083, 1787022870, 2083023753,
                \ 23557139, 1774366382, 59516945,
                \ 1712853318, 3361142011, 3811244839,
                \ 926724521, 3988105581, 3442000971,
                \ 344837321, 2600972270, 1577899986,
                \ 655499818, 2645919503, 3059357774,
                \ 3288772530, 3817712455, 3481848814,
                \ 3324238316, 934774860, 639044091,
                \ 3883846113, 2180174841, 2433412013,
                \ 13227884, 3124391939, 3152974677,
                \ 1388793133, 2370464842, 125239610,
                \ 1962617895, 2191102621, 4027502780,
                \ 1883956096, 2900207871, 1778794124,
                \ 2262081890, 149191219, 2325093310,
                \ 639102810, 3868111332, 3721166590,
                \ ]
    " }}}
    for i in range(len(wanted))
        let expected = wanted[i]
        let actual   = IA()
        if actual == expected
            continue
        endif
        throw printf('IA#%d: wanted %d, got %d', i, expected, actual)
    endfor
    echomsg printf('ok (%d samples)', len(wanted))
    unlet toskip
    unlet wanted
    unlet seed
endif

" {{{ Original C code for reference.
" typedef  unsigned int  u4;   /* unsigned four bytes, 32 bits */
" #define ALPHA      (8)
" #define SIZE       (1<<ALPHA)
" #define ind(x)     (x&(SIZE-1))
"
" static void ia(m,r,bb)
" u4 *m;   /* Memory: array of SIZE ALPHA-bit terms */
" u4 *r;   /* Results: the sequence, same size as m */
" u4 *bb;  /* the previous result */
" {
"   register u4 b,x,y,i;
"
"   b = *bb;
"   for (i=0; i<SIZE; ++i)
"   {
"     x = m[i];
"     m[i] = y = m[ind(x)] + b;              /* set m */
"     r[i] = b = m[ind(y>>ALPHA)] + x;       /* set r */
"   }
"   *bb = b;
" }
" }}}