{$ALIGN ON} {$OPTIMIZATION ON} {$OVERFLOWCHECKS OFF} unit Isaac; { This is ISAAC, a high-quality pseudo-random number generator. ISAAC is crypto-secure. ISAAC has no bias. ISAAC has a minimal garanteed period of 2^40. ISAAC average period is 2^8295. ISAAC algorithm is the property of Bob Jenkins. ISAAC is freely reusable. ISAAC can be used for encryption (mainly stream cipher). ISAAC has a 8192 bits seed (read: 8192 bits key for encryption). This is an optimized Pascal/Assembler version for Delphi 2. The Assembler version has been translated from the optimized Delphi implementation like shown in the comments preceding every method. My changes to the original Delphi 4 version before translating it to Assembler: - All 32bit variables declared as Integer instead of Cardinals because Delphi 2 doesn't allow cardinals > MAXLONGINT like the golden ratio: no impact on the algorithm as checked against the C implementation used as an included object file within a Delphi 2 application - Flag has been added because Delphi 2 doesn't support overlays - Some methods have been renamed - Some methods have been moved to the private object section - Create doesn't execute any algorithm code, it just initializes the object - Changes to (Re)Seed: "const s: Array of integer" prevents Delphi from copying the Array to the local stack "m" is calculated without using jump instructions (if ... then ... else) "rsl" is filled using fast memory operations instead of a loop - Some redundant "count := 0" instructions have been removed - Using the Assembler version compared to the optimized Delphi version is about 10-15% faster on my Pentium machine This code has been (re)written by Michael in der Wiesche , Oct 31st, 2000 The ISAAC algorihm is freely reusable. This implementation of ISAAC is freely reusable. ISAAC algorithm by Bob Jenkins (http://burtleburtle.net/bob) First Delphi ISAAC implementation by Sébastien SAUVAGE (http://sebsauvage.net) Quote from the author of the ISAAC algorithm: > My random number generator, ISAAC. > (c) Bob Jenkins, March 1996 > You may use this code in any way you wish, and it is free. No warrantee. Usage example: uses Windows, StdCtrls, Isaac; var i: integer; x: TIsaac; begin x:=TIsaac.Create; try x.Seed([GetMessageTime, GetMessagePos], false); // don't use given seed for i:=1 to 20 do Memo1.Lines.Add(IntToHex(x.Val, 8)); // get values x.Seed([0, 0], false); // reseed for i:=1 to 20 do Memo1.Lines.Add(IntToHex(x.Val, 8)); // same values finally x.Free; end; end; } interface type TIsaac = class(TObject) private count : integer; { count through the results in rsl[] } rsl : array[0..255] of integer; { the results given to the user } mem : array[0..255] of integer; { the internal state } aa : integer; { accumulator } bb : integer; { the last result } cc : integer; { counter, guarantees cycle is at least 2^^40 } procedure Generate(flag: boolean); { generate new seed } procedure Isaac; { fill in results } public procedure Seed(const s: array of integer; flag: boolean); function Val : integer; { get 1 random value } end; implementation // Initialize the object with a given seed. // The array can have any size. The first 256 values will be used. // If the array has less than 256 values, all available values will be used, the remainder will be zero. { procedure TIsaac.Seed(const s: array of integer; flag: boolean); var m : integer; begin if flag then begin m:=succ(High(s) and 255); // make sure m doesn't exceed 255; succ(m) is the maximum number of elements in s Move(s[0], rsl[0], m*SizeOf(integer)); // move m elements from s to rsl if (m<256) then FillChar(rsl[m], SizeOf(rsl) - (m*SizeOf(integer)), 0); // fill in remainder with zero end; Generate(flag); // generate seed from given seed depending on flag Isaac; // fill in the first set of results end; } procedure TIsaac.Seed(const s: array of integer; flag: boolean); assembler; asm // EAX=Self, ECX=High(s), EDX=@s, flag on stack PUSH EBX // will take m PUSH EDI // will take @rsl PUSH ESI // will taKe @s OR flag,FALSE JZ @END // m:=succ(High(s) and 255); AND ECX,255 INC ECX MOV EBX,ECX // Move(s[0], rsl[0], m*SizeOf(integer)); MOV ESI,EDX LEA EDI,Self.rsl CLD REP MOVSD // if (m<256) CMP EBX,256 JNB @END // then FillChar(rsl[m], SizeOf(rsl) - (m*SizeOf(integer)), 0); PUSH EAX // store Self MOV ECX,TYPE rsl/TYPE INTEGER SUB ECX,EBX XOR EAX,EAX CLD REP STOSD POP EAX // restore Self @END: // create seed from given seed MOVZX EDX,flag CALL Generate; // fill in the first set of results CALL Isaac; POP ESI POP EDI POP EBX end; // EAX=Self, ECX=High(s), EDX=@s, flag on stack { procedure TIsaac.Generate(flag: boolean); var i,a,b,c,d,e,f,g,h : integer; begin aa := 0; bb := 0; cc := 0; // the golden ratio a := $9E3779B9; b:=a; c:=a; d:=a; e:=a; f:=a; g:=a; h:=a; // scramble it for i := 0 to 3 do begin // mix a,b,c,d,e,f,g and h a := a xor (b shl 11); d:=d+a; b:=b+c; b := b xor (c shr 2); e:=e+b; c:=c+d; c := c xor (d shl 8); f:=f+c; d:=d+e; d := d xor (e shr 16); g:=g+d; e:=e+f; e := e xor (f shl 10); h:=h+e; f:=f+g; f := f xor (g shr 4); a:=a+f; g:=g+h; g := g xor (h shl 8); b:=b+g; h:=h+a; h := h xor (a shr 9); c:=c+h; a:=a+b; end; // fill in mem[] with messy stuff i := 0; while (i<256) do begin if flag then begin // use all the information in the seed a:=a+rsl[i ]; b:=b+rsl[i+1]; c:=c+rsl[i+2]; d:=d+rsl[i+3]; e:=e+rsl[i+4]; f:=f+rsl[i+5]; g:=g+rsl[i+6]; h:=h+rsl[i+7]; end; // mix a,b,c,d,e,f,g and h a := a xor (b shl 11); d:=d+a; b:=b+c; b := b xor (c shr 2); e:=e+b; c:=c+d; c := c xor (d shl 8); f:=f+c; d:=d+e; d := d xor (e shr 16); g:=g+d; e:=e+f; e := e xor (f shl 10); h:=h+e; f:=f+g; f := f xor (g shr 4); a:=a+f; g:=g+h; g := g xor (h shl 8); b:=b+g; h:=h+a; h := h xor (a shr 9); c:=c+h; a:=a+b; mem[i ]:=a; mem[i+1]:=b; mem[i+2]:=c; mem[i+3]:=d; mem[i+4]:=e; mem[i+5]:=f; mem[i+6]:=g; mem[i+7]:=h; i:=i+8; end; if flag then begin // do a second pass to make all of the seed affect all of mem i := 0; while (i<256) do begin // use all the information in the seed a:=a+mem[i ]; b:=b+mem[i+1]; c:=c+mem[i+2]; d:=d+mem[i+3]; e:=e+mem[i+4]; f:=f+mem[i+5]; g:=g+mem[i+6]; h:=h+mem[i+7]; // mix a,b,c,d,e,f,g and h a:=a xor (b shl 11); d:=d+a; b:=b+c; b:=b xor (c shr 2); e:=e+b; c:=c+d; c:=c xor (d shl 8); f:=f+c; d:=d+e; d:=d xor (e shr 16); g:=g+d; e:=e+f; e:=e xor (f shl 10); h:=h+e; f:=f+g; f:=f xor (g shr 4); a:=a+f; g:=g+h; g:=g xor (h shl 8); b:=b+g; h:=h+a; h:=h xor (a shr 9); c:=c+h; a:=a+b; mem[i ]:=a; mem[i+1]:=b; mem[i+2]:=c; mem[i+3]:=d; mem[i+4]:=e; mem[i+5]:=f; mem[i+6]:=g; mem[i+7]:=h; i:=i+8; end; end; end; } procedure TIsaac.Generate(flag: boolean); assembler; asm // EAX=Self, EDX=flag SUB ESP,TYPE INTEGER*5 // registers for a,b,c,d, stack for e,f,g,h,i PUSH EBP // temp var PUSH EDI // will take Self PUSH ESI // will take @rsl/@mem PUSH EBX PUSH EDX MOV EDI,EAX // aa := 0; bb := 0; cc := 0; XOR EBP,EBP MOV [EDI.aa],EBP MOV [EDI.bb],EBP MOV [EDI.cc],EBP // a := $9E3779B9 MOV EAX,9E3779B9h // b:=a; c:=a; d:=a; e:=a; f:=a; g:=a; h:=a; MOV EBX,EAX MOV ECX,EAX MOV EDX,EAX MOV [ESP+20],EAX MOV [ESP+24],EAX MOV [ESP+28],EAX MOV [ESP+32],EAX // for i := 0 to 3 do MOV DWORD PTR [ESP+36],4 @LOOP: MOV EBP,EBX // a := a xor (b shl 11); SHL EBP,11 XOR EAX,EBP // d:=d+a; ADD EDX,EAX // b:=b+c; MOV EBP,ECX ADD EBX,ECX // b := b xor (c shr 2); SHR EBP,2 XOR EBX,EBP // e:=e+b; ADD [ESP+20],EBX // c:=c+d; MOV EBP,EDX ADD ECX,EDX // c := c xor (d shl 8); SHL EBP,8 XOR ECX,EBP // f:=f+c; ADD [ESP+24],ECX // d:=d+e; MOV EBP,[ESP+20] ADD EDX,EBP // d := d xor (e shr 16); SHR EBP,16 XOR EDX,EBP // g:=g+d; ADD [ESP+28],EDX // e:=e+f; MOV EBP,[ESP+24] ADD [ESP+20],EBP // e := e xor (f shl 10); SHL EBP,10 XOR EBP,[ESP+20] MOV [ESP+20],EBP // h:=h+e; ADD [ESP+32],EBP // f:=f+g; MOV EBP,[ESP+28] ADD [ESP+24],EBP // f := f xor (g shr 4); SHR EBP,4 XOR EBP,[ESP+24] MOV [ESP+24],EBP // a:=a+f; ADD EAX,EBP // g:=g+h; MOV EBP,[ESP+32] ADD [ESP+28],EBP // g := g xor (h shl 8); SHL EBP,8 XOR EBP,[ESP+28] MOV [ESP+28],EBP // b:=b+g; ADD EBX,EBP // h:=h+a; MOV EBP,EAX ADD [ESP+32],EBP // h := h xor (a shr 9); SHR EBP,9 XOR EBP,[ESP+32] MOV [ESP+32],EBP // c:=c+h; ADD ECX,EBP // a:=a+b; ADD EAX,EBX DEC DWORD PTR [ESP+36] JNZ @LOOP // fill in mem[] with messy stuff // i:= 0; // [ESP+36] is already zero XOR EBP,EBP @USE_RSL: // a:=a+rsl[i ]; b:=b+rsl[i+1]; c:=c+rsl[i+2]; d:=d+rsl[i+3]; // e:=e+rsl[i+4]; f:=f+rsl[i+5]; g:=g+rsl[i+6]; h:=h+rsl[i+7]; OR DWORD PTR [ESP],FALSE JZ @MIX LEA ESI,EDI.rsl[EBP*TYPE INTEGER] MOV EBP,[ESI+4*TYPE INTEGER] ADD EAX,[ESI] ADD [ESP+20],EBP MOV EBP,[ESI+5*TYPE INTEGER] ADD EBX,[ESI+1*TYPE INTEGER] ADD [ESP+24],EBP MOV EBP,[ESI+6*TYPE INTEGER] ADD ECX,[ESI+2*TYPE INTEGER] ADD [ESP+28],EBP MOV EBP,[ESI+7*TYPE INTEGER] ADD EDX,[ESI+3*TYPE INTEGER] ADD [ESP+32],EBP @MIX: MOV EBP,EBX // a := a xor (b shl 11); SHL EBP,11 XOR EAX,EBP // d:=d+a; ADD EDX,EAX // b:=b+c; MOV EBP,ECX ADD EBX,ECX // b := b xor (c shr 2); SHR EBP,2 XOR EBX,EBP // e:=e+b; ADD [ESP+20],EBX // c:=c+d; MOV EBP,EDX ADD ECX,EDX // c := c xor (d shl 8); SHL EBP,8 XOR ECX,EBP // f:=f+c; ADD [ESP+24],ECX // d:=d+e; MOV EBP,[ESP+20] ADD EDX,EBP // d := d xor (e shr 16); SHR EBP,16 XOR EDX,EBP // g:=g+d; ADD [ESP+28],EDX // e:=e+f; MOV EBP,[ESP+24] ADD [ESP+20],EBP // e := e xor (f shl 10); SHL EBP,10 XOR EBP,[ESP+20] MOV [ESP+20],EBP // h:=h+e; ADD [ESP+32],EBP // f:=f+g; MOV EBP,[ESP+28] ADD [ESP+24],EBP // f := f xor (g shr 4); SHR EBP,4 XOR EBP,[ESP+24] MOV [ESP+24],EBP // a:=a+f; ADD EAX,EBP // g:=g+h; MOV EBP,[ESP+32] ADD [ESP+28],EBP // g := g xor (h shl 8); SHL EBP,8 XOR EBP,[ESP+28] MOV [ESP+28],EBP // b:=b+g; ADD EBX,EBP // h:=h+a; MOV EBP,EAX ADD [ESP+32],EBP // h := h xor (a shr 9); SHR EBP,9 XOR EBP,[ESP+32] MOV [ESP+32],EBP // c:=c+h; ADD ECX,EBP // a:=a+b; ADD EAX,EBX // mem[i ]:=a; mem[i+1]:=b; mem[i+2]:=c; mem[i+3]:=d; // mem[i+4]:=e; mem[i+5]:=f; mem[i+6]:=g; mem[i+7]:=h; MOV EBP,[ESP+36] LEA ESI,EDI.mem[EBP*TYPE INTEGER] MOV EBP,[ESP+20] MOV [ESI],EAX MOV [ESI+4*TYPE INTEGER],EBP MOV EBP,[ESP+24] MOV [ESI+1*TYPE INTEGER],EBX MOV [ESI+5*TYPE INTEGER],EBP MOV EBP,[ESP+28] MOV [ESI+2*TYPE INTEGER],ECX MOV [ESI+6*TYPE INTEGER],EBP MOV EBP,[ESP+32] MOV [ESI+3*TYPE INTEGER],EDX MOV [ESI+7*TYPE INTEGER],EBP MOV EBP,[ESP+36] ADD EBP,8 MOV [ESP+36],EBP CMP EBP,256 JNZ @USE_RSL OR DWORD PTR [ESP],FALSE JZ @END // i := 0; XOR EBP,EBP MOV [ESP+36],EBP // [ESP+36] has be set to zero here // do a second pass to make all of the seed affect all of mem @USE_MEM: // a:=a+mem[i ]; b:=b+mem[i+1]; c:=c+mem[i+2]; d:=d+mem[i+3]; // e:=e+mem[i+4]; f:=f+mem[i+5]; g:=g+mem[i+6]; h:=h+mem[i+7]; LEA ESI,EDI.mem[EBP*TYPE INTEGER] MOV EBP,[ESI+4*TYPE INTEGER] ADD EAX,[ESI] ADD [ESP+20],EBP MOV EBP,[ESI+5*TYPE INTEGER] ADD EBX,[ESI+1*TYPE INTEGER] ADD [ESP+24],EBP MOV EBP,[ESI+6*TYPE INTEGER] ADD ECX,[ESI+2*TYPE INTEGER] ADD [ESP+28],EBP MOV EBP,[ESI+7*TYPE INTEGER] ADD EDX,[ESI+3*TYPE INTEGER] ADD [ESP+32],EBP MOV EBP,EBX // a := a xor (b shl 11); SHL EBP,11 XOR EAX,EBP // d:=d+a; ADD EDX,EAX // b:=b+c; MOV EBP,ECX ADD EBX,ECX // b := b xor (c shr 2); SHR EBP,2 XOR EBX,EBP // e:=e+b; ADD [ESP+20],EBX // c:=c+d; MOV EBP,EDX ADD ECX,EDX // c := c xor (d shl 8); SHL EBP,8 XOR ECX,EBP // f:=f+c; ADD [ESP+24],ECX // d:=d+e; MOV EBP,[ESP+20] ADD EDX,EBP // d := d xor (e shr 16); SHR EBP,16 XOR EDX,EBP // g:=g+d; ADD [ESP+28],EDX // e:=e+f; MOV EBP,[ESP+24] ADD [ESP+20],EBP // e := e xor (f shl 10); SHL EBP,10 XOR EBP,[ESP+20] MOV [ESP+20],EBP // h:=h+e; ADD [ESP+32],EBP // f:=f+g; MOV EBP,[ESP+28] ADD [ESP+24],EBP // f := f xor (g shr 4); SHR EBP,4 XOR EBP,[ESP+24] MOV [ESP+24],EBP // a:=a+f; ADD EAX,EBP // g:=g+h; MOV EBP,[ESP+32] ADD [ESP+28],EBP // g := g xor (h shl 8); SHL EBP,8 XOR EBP,[ESP+28] MOV [ESP+28],EBP // b:=b+g; ADD EBX,EBP // h:=h+a; MOV EBP,EAX ADD [ESP+32],EBP // h := h xor (a shr 9); SHR EBP,9 XOR EBP,[ESP+32] MOV [ESP+32],EBP // c:=c+h; ADD ECX,EBP // a:=a+b; ADD EAX,EBX // mem[i ]:=a; mem[i+1]:=b; mem[i+2]:=c; mem[i+3]:=d; // mem[i+4]:=e; mem[i+5]:=f; mem[i+6]:=g; mem[i+7]:=h; MOV EBP,[ESP+36] LEA ESI,EDI.mem[EBP*TYPE INTEGER] MOV EBP,[ESP+20] MOV [ESI],EAX MOV [ESI+4*TYPE INTEGER],EBP MOV EBP,[ESP+24] MOV [ESI+1*TYPE INTEGER],EBX MOV [ESI+5*TYPE INTEGER],EBP MOV EBP,[ESP+28] MOV [ESI+2*TYPE INTEGER],ECX MOV [ESI+6*TYPE INTEGER],EBP MOV EBP,[ESP+32] MOV [ESI+3*TYPE INTEGER],EDX MOV [ESI+7*TYPE INTEGER],EBP MOV EBP,[ESP+36] ADD EBP,8 MOV [ESP+36],EBP CMP EBP,256 JNZ @USE_MEM @END: MOV EAX,EDI POP EDX POP EBX POP ESI POP EDI POP EBP ADD ESP,TYPE INTEGER*5 end; // EAX=Self, EDX=flag { procedure TIsaac.Isaac; var i,x,y : integer; begin inc(cc); bb := bb + cc; for i := 0 to 255 do begin x := mem[i]; case (i and 3) of 0: aa := aa xor (aa shl 13); 1: aa := aa xor (aa shr 6); 2: aa := aa xor (aa shl 2); 3: aa := aa xor (aa shr 16); end; aa := aa + mem[(i+128) and 255]; y := mem[(x shr 2) and 255] + aa + bb; mem[i] := y; bb := mem[(y shr 10) and 255] + x; rsl[i] := bb; end; count := 0; end; } procedure TIsaac.Isaac; assembler; asm // EAX=Self PUSH EBX // temp aa PUSH EBP // temp bb PUSH EDI // will take x PUSH ESI // will take y // inc(cc) INC [Self.cc] // bb := bb + cc; MOV EBP,[Self.bb] ADD EBP,[Self.cc] // i := 0; XOR ECX,ECX @LOOP: MOV EBX,[Self.aa] // case (i and 3) of MOV EDX,ECX AND EDX,3 SUB EDX,1 JC @00 JZ @01 DEC EDX JZ @02 DEC EDX JZ @03 @00: // aa := aa xor (aa shl 13); MOV EDX,EBX SHL EDX,13 XOR EBX,EDX JMP @END @01: // aa := aa xor (aa shr 6); MOV EDX,EBX SHR EDX,6 XOR EBX,EDX JMP @END @02: // aa := aa xor (aa shl 2); MOV EDX,EBX SHL EDX,2 XOR EBX,EDX JMP @END @03: // aa := aa xor (aa shr 16); MOV EDX,EBX SHR EDX,16 XOR EBX,EDX @END: // aa := aa + mem[(i+128) and 255]; MOV EDX,ECX ADD EDX,128 AND EDX,255 ADD EBX,DWORD PTR [Self.mem + EDX*TYPE INTEGER] MOV [Self.aa],EBX // x := mem[i]; MOV EDI,DWORD PTR [Self.mem + ECX*TYPE INTEGER] // y := mem[(x shr 2) and 255] + aa + bb; MOV EDX,EDI SHR EDX,2 AND EDX,255 MOV ESI,DWORD PTR [Self.mem + EDX*TYPE INTEGER] ADD ESI,EBX ADD ESI,EBP // mem[i] := y; MOV DWORD PTR [Self.mem + ECX*TYPE INTEGER],ESI // bb := mem[(y shr 10) and 255] + x; SHR ESI,10 AND ESI,255 MOV EBP,DWORD PTR [Self.mem + ESI*TYPE INTEGER] ADD EBP,EDI // rsl[i] := bb; MOV DWORD PTR [Self.rsl + ECX*TYPE INTEGER],EBP // inc(i); INC ECX CMP ECX,256 JNZ @LOOP MOV [Self.bb],EBP // count := 0; MOV Self.count,0 POP ESI POP EDI POP EBP POP EBX end; // EAX=Self // Call Val to get a random value (32 bits). { function TIsaac.Val : integer; begin Result := rsl[count]; inc(count); if (count=256) then Isaac; end; } function TIsaac.Val : integer; assembler; asm // EAX=Self // Result := rsl[count]; MOV EDX,[Self.count] MOV ECX,DWORD PTR [Self.rsl + EDX*TYPE INTEGER] // inc(count); INC EDX MOV [Self.count],EDX // if (count=256) CMP EDX,256 JNZ @EXIT // then get next set of results; PUSH ECX // store Result CALL Isaac POP ECX // restore Result @EXIT: MOV EAX,ECX end; // EAX=Result end.