From 8a8770375ebcf69b18749be85838dc46132cbe9f Mon Sep 17 00:00:00 2001 From: "Jason S. Ninneman" Date: Tue, 23 May 2017 23:37:56 -0700 Subject: [PATCH] Add seedable PRNG using an adaptation the original LCG algorithm. --- TODO | 3 +-- actions2.c | 2 +- funcs.h | 2 +- main.c | 18 +++++++++++++----- main.h | 6 ++++++ misc.c | 48 ++++++++++++++++++++++++------------------------ misc.h | 5 +++-- 7 files changed, 49 insertions(+), 35 deletions(-) diff --git a/TODO b/TODO index 3e7758d..681e959 100644 --- 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 log replay. Note that the replay log needs to begin with the random-number seed. diff --git a/actions2.c b/actions2.c index dcc649d..6b28895 100644 --- a/actions2.c +++ b/actions2.c @@ -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 455de2d..deb4010 100644 --- 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 71d61c9..4854b69 100644 --- 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 fa87d62..a71b9e3 100644 --- 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 a08720c..320d002 100644 --- a/misc.c +++ b/misc.c @@ -723,7 +723,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) { @@ -757,32 +757,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; @@ -795,7 +795,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 561ac52..869c672 100644 --- 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); -- 2.31.1