New faster random generator
authorunc0rr
Mon, 07 Aug 2006 12:08:43 +0000
changeset 102 c45643d3fd78
parent 101 f568cc72ea8c
child 103 8c56db04ea52
New faster random generator
hedgewars/CCHandlers.inc
hedgewars/uConsts.pas
hedgewars/uLand.pas
hedgewars/uRandom.pas
hedgewars/uSHA.pas
--- a/hedgewars/CCHandlers.inc	Sun Aug 06 20:58:05 2006 +0000
+++ b/hedgewars/CCHandlers.inc	Mon Aug 07 12:08:43 2006 +0000
@@ -360,7 +360,7 @@
 begin
 if isDeveloperMode then
    begin
-   SetRandomParams(s, rndfillstr);
+   SetRandomSeed(s);
    cSeed:= s;
    InitStepsFlags:= InitStepsFlags or cifRandomize
    end
--- a/hedgewars/uConsts.pas	Sun Aug 06 20:58:05 2006 +0000
+++ b/hedgewars/uConsts.pas	Mon Aug 07 12:08:43 2006 +0000
@@ -91,8 +91,6 @@
 const
       cNetProtoVersion = 1;
 
-      rndfillstr = 'hw';
-
       MAXNAMELEN = 32;
 
       COLOR_LAND = $00FFFFFF;
--- a/hedgewars/uLand.pas	Sun Aug 06 20:58:05 2006 +0000
+++ b/hedgewars/uLand.pas	Mon Aug 07 12:08:43 2006 +0000
@@ -43,7 +43,7 @@
 procedure GenMap;
 
 implementation
-uses uConsole, uStore, uMisc, uConsts, uRandom, uTeams, uIO, uLandTemplates, uLandObjects, uSHA;
+uses uConsole, uStore, uMisc, uConsts, uRandom, uTeams, uIO, uLandTemplates, uLandObjects;
 
 type TPixAr = record
               Count: Longword;
@@ -51,16 +51,16 @@
               end;
 
 procedure LogLandDigest;
-var ctx: TSHA1Context;
-    dig: TSHA1Digest;
+//var ctx: TSHA1Context;
+//    dig: TSHA1Digest;
 begin
-SHA1Init(ctx);
-SHA1Update(ctx, @Land, sizeof(Land));
-dig:= SHA1Final(ctx);
+//SHA1Init(ctx);
+//SHA1Update(ctx, @Land, sizeof(Land));
+//dig:= SHA1Final(ctx);
 {$IFDEF DEBUGFILE}
-AddFileLog('SHA1 Land digest: {'+inttostr(dig.LongWords[0])+':'
-           +inttostr(dig.LongWords[1])+':'+inttostr(dig.LongWords[2])+':'
-           +inttostr(dig.LongWords[3])+':'+inttostr(dig.LongWords[4])+'}');
+//AddFileLog('SHA1 Land digest: {'+inttostr(dig.LongWords[0])+':'
+//           +inttostr(dig.LongWords[1])+':'+inttostr(dig.LongWords[2])+':'
+//           +inttostr(dig.LongWords[3])+':'+inttostr(dig.LongWords[4])+'}');
 {$ENDIF}
 end;
 
--- a/hedgewars/uRandom.pas	Sun Aug 06 20:58:05 2006 +0000
+++ b/hedgewars/uRandom.pas	Mon Aug 07 12:08:43 2006 +0000
@@ -33,41 +33,46 @@
 
 unit uRandom;
 interface
-uses uSHA;
 
-procedure SetRandomParams(Seed: shortstring; FillBuf: shortstring);
+procedure SetRandomSeed(Seed: shortstring);
 function  GetRandom: real; overload;
 function  GetRandom(m: LongWord): LongWord; overload;
 
 implementation
-var  sc1, sc2: TSHA1Context;
-     Fill: shortstring;
+const rndM = 2147483578;
+var cirbuf: array[0..63] of Longword;
+    n: byte;
 
-procedure SetRandomParams(Seed: shortstring; FillBuf: shortstring);
+function GetNext: Longword;
 begin
-SHA1Init(sc1);
-SHA1Update(sc1, @Seed, Length(Seed)+1);
-Fill:= FillBuf
+n:= (n + 1) and $3F;
+cirbuf[n]:=
+           (cirbuf[(n + 40) and $3F] +           {== n - 24 mod 64}
+            cirbuf[(n +  9) and $3F]) mod rndM;  {== n - 55 mod 64}
+            
+Result:= cirbuf[n]
+end;
+
+procedure SetRandomSeed(Seed: shortstring);
+var i: Longword;
+begin
+for i:= 0 to pred(Length(Seed)) do
+    cirbuf[i]:= byte(Seed[i + 1]) * 35791253;
+
+for i:= Length(Seed) to 63 do
+    cirbuf[i]:= i * 23860799;
+
+for i:= 0 to 1024 do GetNext;
 end;
 
 function GetRandom: real;
-var dig: TSHA1Digest;
 begin
-SHA1Update(sc1, @Fill[1], Length(Fill));
-sc2:= sc1;
-dig:= SHA1Final(sc2);
-Result:= frac( dig.LongWords[0]*0.0000731563977
-               + pi * dig.Words[6]
-               + 0.0109070019*dig.Words[9])
+Result:= frac( GetNext * 0.0007301 + GetNext * 0.003019)
 end;
 
-function  GetRandom(m: LongWord): LongWord;
-var dig: TSHA1Digest;
+function GetRandom(m: LongWord): LongWord;
 begin
-SHA1Update(sc1, @Fill[1], Length(Fill));
-sc2:= sc1;
-dig:= SHA1Final(sc2);
-Result:= (dig.LongWords[0] + dig.LongWords[2] + dig.LongWords[3]) mod m
+Result:= GetNext mod m
 end;
 
 end.
--- a/hedgewars/uSHA.pas	Sun Aug 06 20:58:05 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,161 +0,0 @@
-(*
- * Hedgewars, a worms-like game
- * Copyright (c) 2004, 2005 Andrey Korotaev <unC0Rr@gmail.com>
- *
- * Distributed under the terms of the BSD-modified licence:
- *
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to deal
- * with the Software without restriction, including without limitation the
- * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
- * sell copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- *
- * 1. Redistributions of source code must retain the above copyright notice,
- *    this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright notice,
- *    this list of conditions and the following disclaimer in the documentation
- *    and/or other materials provided with the distribution.
- * 3. The name of the author may not be used to endorse or promote products
- *    derived from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
- * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
- * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
- * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
- * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
- * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
- * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *)
-
-unit uSHA;
-interface
-
-type TSHA1Context = packed record
-                    H: array[0..4] of LongWord;
-                    Length, CurrLength: Int64;
-                    Buf: array[0..63] of byte;
-                    end;
-     TSHA1Digest = record
-                   case byte of
-                        0: (LongWords: array[0.. 4] of LongWord);
-                        1: (    Words: array[0.. 9] of     Word);
-                        2: (    Bytes: array[0..19] of     Byte)
-                   end;
-
-procedure SHA1Init(var Context: TSHA1Context);
-procedure SHA1Update(var Context: TSHA1Context; Buf: Pointer; Length: LongWord);
-function  SHA1Final(Context: TSHA1Context): TSHA1Digest;
-
-implementation
-uses SDLh;
-
-function rol(x: LongWord; y: Byte): LongWord;
-begin
-  Result:= (X shl y) or (X shr (32 - y))
-end;
-
-function Ft(t, b, c, d: LongWord): LongWord;
-begin
-case t of
-      0..19: Result := (b and c) or ((not b) and d);
-     20..39: Result :=  b xor c xor d;
-     40..59: Result := (b and c) or (b and d) or (c and d);
-     else    Result :=  b xor c xor d;
-  end;
-end;
-
-function Kt(t: Byte): LongWord;
-begin
-  case t of
-     0..19: Result := $5A827999;
-    20..39: Result := $6ED9EBA1;
-    40..59: Result := $8F1BBCDC;
-  else
-    Result := $CA62C1D6
-  end;
-end;
-
-
-procedure SHA1Hash(var Context: TSHA1Context);
-var S: array[0..4 ] of LongWord;
-    W: array[0..79] of LongWord;
-    i, t: LongWord;
-begin
-move(Context.H, S, sizeof(S));
-for i:= 0 to 3 do
-    begin
-    t:= i * 4;
-    with Context do
-         W[i]:= Buf[t + 3] or (Buf[t + 2] shl 8) or (Buf[t + 1] shl 16) or (Buf[t] shl 24);
-    end;
-for i := 16 to 79 do
-    W[i] := rol(W[i - 3] xor W[i - 8] xor W[i - 14] xor W[i - 16], 1);
-for i := 0 to 79 do
-    begin
-    t:= rol(S[0], 5) + Ft(i, S[1], S[2], S[3]) + S[4] + W[i] + Kt(i);
-    S[4]:= S[3];
-    S[3]:= S[2];
-    S[2]:= rol(S[1], 30);
-    S[1]:= S[0];
-    S[0]:= t
-    end;
-for i := 0 to 4 do
-    Context.H[i]:= Context.H[i] + S[i]
-end;
-
-procedure SHA1Init(var Context: TSHA1Context);
-begin
-  with Context do
-       begin
-       Length    := 0;
-       CurrLength:= 0;
-       H[0]:= $67452301;
-       H[1]:= $EFCDAB89;
-       H[2]:= $98BADCFE;
-       H[3]:= $10325476;
-       H[4]:= $C3D2E1F0
-  end
-end;
-
-procedure SHA1Update(var Context: TSHA1Context; Buf: Pointer; Length: LongWord);
-var i: integer;
-begin
-for i:= 0 to Pred(Length) do
-    begin
-    Context.Buf[Context.CurrLength]:= PByteArray(Buf)^[i];
-    inc(Context.CurrLength);
-    if Context.CurrLength=64 then
-       begin
-       SHA1Hash(Context);
-       inc(Context.Length, 512);
-       Context.CurrLength:=0
-       end
-    end
-end;
-
-function  SHA1Final(Context: TSHA1Context): TSHA1Digest;
-var i: LongWord;
-begin
-Context.Length:= Context.Length + Context.CurrLength shl 3;
-Context.Buf[Context.CurrLength]:= $80;
-inc(Context.CurrLength);
-if Context.CurrLength>56 then
-   begin
-   FillChar(Context.Buf[Context.CurrLength],64-Context.CurrLength,0);
-   Context.CurrLength:= 64;
-   SHA1Hash(Context);
-   Context.CurrLength:=0
-   end;
-FillChar(Context.Buf[Context.CurrLength],56-Context.CurrLength,0);
-for i:= 56 to 63 do
-    Context.Buf[i] := (Context.Length shr ((63 - i) * 8)) and $FF;
-SHA1Hash(Context);
-move(Context.H, Result, sizeof(TSHA1Digest));
-FillChar(Context, sizeof(Context), 0)
-end;
-
-end.