Add seedable PRNG using an adaptation the original LCG algorithm.
authorJason S. Ninneman <jsn@mbar.us>
Wed, 24 May 2017 06:37:56 +0000 (23:37 -0700)
committerEric S. Raymond <esr@thyrsus.com>
Thu, 23 Mar 2023 15:28:53 +0000 (11:28 -0400)
TODO
actions2.c
funcs.h
main.c
main.h
misc.c
misc.h

diff --git a/TODO b/TODO
index 3fe80a7dc885c4bd88ffc5cb80a1c50a0432bb33..78e4e073a1d916cff2666f10de57d89f6adc6d76 100644 (file)
--- a/TODO
+++ b/TODO
@@ -1,7 +1,6 @@
 = Open Adventure TODO =
 
-* Use a real pseudorandom-number generator with a seed rather than just
-  time-sampling.
+* Update the command parser to accept a PRNG seed value.
 
 * Add command logging and command log replay.  Note that the replay log
   needs to begin with the random-number seed.
index dcc649da04b43856bcace8eab25df80c5168c3f0..6b2889558bbeebb2d024e27b4b303e8660a0cbf3 100644 (file)
@@ -233,7 +233,7 @@ int throw(FILE *cmdin) {
        return(attack(cmdin));
 
 L9172: SPK=48;
-       if(RAN(7) < DFLAG) goto L9175;
+       if(randrange(7) < DFLAG) goto L9175;
        DSEEN[I]=false;
        DLOC[I]=0;
        SPK=47;
diff --git a/funcs.h b/funcs.h
index 455de2d6b78360ae63c24aaf9528feb70b969410..deb401065dfaa5239aa845413ac34e67509ef940 100644 (file)
--- a/funcs.h
+++ b/funcs.h
@@ -23,7 +23,7 @@
 #define CNDBIT(L,N)    (TSTBIT(COND[L],N))
 #define FORCED(LOC)    (COND[LOC] == 2)
 #define DARK(DUMMY)    ((!CNDBIT(LOC,0)) && (PROP[LAMP] == 0 || !HERE(LAMP)))
-#define PCT(N) (RAN(100) < (N))
+#define PCT(N) (randrange(100) < (N))
 #define GSTONE(OBJ)    ((OBJ) == EMRALD || (OBJ) == RUBY || (OBJ) == AMBER || (OBJ) == SAPPH)
 #define FOREST(LOC)    ((LOC) >= 145 && (LOC) <= 166)
 #define VOCWRD(LETTRS,SECT)    (VOCAB(MAKEWD(LETTRS),SECT))
diff --git a/main.c b/main.c
index de25b32a388cf642e4c34af86cc5886df7dfecd3..a3051ab9dd5e74cc69e3239e47ce11b27b33c456 100644 (file)
--- a/main.c
+++ b/main.c
@@ -42,6 +42,7 @@ long ABBNUM, ACTSPK[36], AMBER, ATTACK, AXE, BACK, BATTER, BEAR, BIRD, BLOOD, BO
                WZDARK = false, ZZWORD;
 FILE  *logfp;
 bool oldstyle = false;
+lcg_state lcgstate;
 
 extern void initialise();
 extern void score(long);
@@ -93,6 +94,13 @@ int main(int argc, char *argv[]) {
 
 #include "funcs.h"
 
+/* Initialize our LCG PRNG with parameters tested against Knuth vol. 2. by the original authors */
+
+       lcgstate.a = 1093;
+       lcgstate.c = 221587;
+       lcgstate.m = 1048576;
+       set_seed_from_time();
+
 /*  Read the database if we have not yet done so */
 
        LINES = (long *)calloc(LINSIZ+1,sizeof(long));
@@ -116,7 +124,7 @@ int main(int argc, char *argv[]) {
 /*  Start-up, dwarf stuff */
 
 L1:    SETUP= -1;
-       I=RAN(-1);
+       I=0;
        ZZWORD=RNDVOC(3,0)+MESH*2;
        NOVICE=YES(stdin, 65,1,0);
        NEWLOC=1;
@@ -175,7 +183,7 @@ L6000:      if(DFLAG != 1) goto L6010;
        if(!INDEEP(LOC) || (PCT(95) && (!CNDBIT(LOC,4) || PCT(85)))) goto L2000;
        DFLAG=2;
        for (I=1; I<=2; I++) {
-       J=1+RAN(5);
+       J=1+randrange(5);
        if(PCT(50))DLOC[J]=0;
        } /* end loop */
        for (I=1; I<=5; I++) {
@@ -213,7 +221,7 @@ L6014:      KK=KK+1;
        {long x = KK-1; if(TRAVEL[x] >= 0) goto L6012;}
 L6016: TK[J]=ODLOC[I];
        if(J >= 2)J=J-1;
-       J=1+RAN(J);
+       J=1+randrange(J);
        ODLOC[I]=DLOC[I];
        DLOC[I]=TK[J];
        DSEEN[I]=(DSEEN[I] && INDEEP(LOC)) || (DLOC[I] == LOC || ODLOC[I] == LOC);
@@ -266,7 +274,7 @@ L6027:      DTOTAL=DTOTAL+1;
        if(ODLOC[I] != DLOC[I]) goto L6030;
        ATTACK=ATTACK+1;
        if(KNFLOC >= 0)KNFLOC=LOC;
-       if(RAN(1000) < 95*(DFLAG-2))STICK=STICK+1;
+       if(randrange(1000) < 95*(DFLAG-2))STICK=STICK+1;
 L6030: /*etc*/ ;
        } /* end loop */
 
@@ -380,7 +388,7 @@ L2603:      if(!CLOSED) goto L2605;
        } /* end loop */
 L2605: WZDARK=DARK(0);
        if(KNFLOC > 0 && KNFLOC != LOC)KNFLOC=0;
-       I=RAN(1);
+       I=0;
        GETIN(cmdin, WD1,WD1X,WD2,WD2X);
 
 /*  Every input, check "FOOBAR" flag.  If zero, nothing's going on.  If pos,
diff --git a/main.h b/main.h
index fa87d627ec8847e720f844ca471bcd41cea47872..a71b9e3ff113bce06f1915f1d36daf7e4a5acec3 100644 (file)
--- a/main.h
+++ b/main.h
@@ -2,9 +2,15 @@
 
 #define LINESIZE       100
 
+typedef struct lcg_state
+{
+  unsigned long a, c, m, x;
+} lcg_state;
+
 extern long ABB[], ATAB[], ATLOC[], BLKLIN, DFLAG, DLOC[], FIXED[], HOLDNG,
                KTAB[], *LINES, LINK[], LNLENG, LNPOSN,
                PARMS[], PLACE[], PTEXT[], RTEXT[], TABSIZ;
 extern signed char INLINE[LINESIZE+1], MAP1[], MAP2[];
 extern FILE *logfp;
 extern bool oldstyle;
+extern lcg_state lcgstate;
diff --git a/misc.c b/misc.c
index 680f9ff48521df346d8c6ad9cd8c1776e87c22ae..7d9f4eccff4b1be06b395aa19cfb7e46808a9c70 100644 (file)
--- a/misc.c
+++ b/misc.c
@@ -722,7 +722,7 @@ L2: ATDWRF=I;
 
 
 
-/*  Utility routines (SETBIT, TSTBIT, RAN, RNDVOC, BUG) */
+/*  Utility routines (SETBIT, TSTBIT, set_seed_from_time, get_next_lcg_value, randrange, RNDVOC, BUG) */
 
 #undef SETBIT
 long fSETBIT(long BIT) {
@@ -756,32 +756,32 @@ long TSTBIT;
 
 
 #define TSTBIT(MASK,BIT) fTSTBIT(MASK,BIT)
-#undef RAN
-long fRAN(long RANGE) {
-static long D, R = 0, RAN, T;
-
-/*  Since the ran function in LIB40 seems to be a real lose, we'll use one of
- *  our own.  It's been run through many of the tests in Knuth vol. 2 and
- *  seems to be quite reliable.  RAN returns a value uniformly selected
- *  between 0 and range-1. */
-
-
-       D=1;
-       if(R != 0 && RANGE >= 0) goto L1;
-       DATIME(D,T);
-       R=MOD(T+5,1048576L);
-       D=1000+MOD(D,1000);
-L1:    for (T=1; T<=D; T++) {
-       R=MOD(R*1093L+221587L,1048576L);
-       } /* end loop */
-       RAN=(RANGE*R)/1048576;
-       return(RAN);
+#undef RNDVOC
+
+void set_seed_from_time(void)
+{
+  /* Use the current system time to get seed the ISO rand() function, from which we get a seed for the LCG. */
+  struct timespec ts;
+  clock_gettime(CLOCK_REALTIME, &ts);
+  srand(ts.tv_nsec);
+  lcgstate.x = (unsigned long) rand() % lcgstate.m;
 }
 
+unsigned long get_next_lcg_value(void)
+{
+  /* Return the LCG's current value, and then iterate it. */
+  unsigned long old_x = lcgstate.x;
+  lcgstate.x = (lcgstate.a * lcgstate.x + lcgstate.c) % lcgstate.m;
+  return(old_x);
+}
 
+long randrange(long range)
+{
+  /* Return a random integer from [0, range). */
+  long result = range * get_next_lcg_value() / lcgstate.m;
+  return(result);
+}
 
-#define RAN(RANGE) fRAN(RANGE)
-#undef RNDVOC
 long fRNDVOC(long CHAR, long FORCE) {
 long DIV, I, J, RNDVOC;
 
@@ -794,7 +794,7 @@ long DIV, I, J, RNDVOC;
        RNDVOC=FORCE;
        if(RNDVOC != 0) goto L3;
        for (I=1; I<=5; I++) {
-       J=11+RAN(26);
+       J=11+randrange(26);
        if(I == 2)J=CHAR;
        RNDVOC=RNDVOC*64+J;
        } /* end loop */
diff --git a/misc.h b/misc.h
index 561ac52fe82e62f61e656d016544d8cc5c1df8f4..869c6728580006ac388c83a20122e21b7a76f8df 100644 (file)
--- a/misc.h
+++ b/misc.h
@@ -55,8 +55,6 @@ extern long fSETBIT(long);
 #define SETBIT(BIT) fSETBIT(BIT)
 extern long fTSTBIT(long,long);
 #define TSTBIT(MASK,BIT) fTSTBIT(MASK,BIT)
-extern long fRAN(long);
-#define RAN(RANGE) fRAN(RANGE)
 extern long fRNDVOC(long,long);
 #define RNDVOC(CHAR,FORCE) fRNDVOC(CHAR,FORCE)
 extern void fBUG(long);
@@ -74,3 +72,6 @@ extern long fIABS(long);
 #define IABS(N) fIABS(N)
 extern long fMOD(long,long);
 #define MOD(N,M) fMOD(N,M)
+extern void set_seed_from_time(void);
+extern unsigned long get_next_lcg_value(void);
+extern long randrange(long);