DIRECTORY Random USING [RandomStream, RandomStreamRep]; RandomImpl: CEDAR MONITOR LOCKS pd USING pd: PrivateData EXPORTS Random = { OPEN Random; BadInterval: PUBLIC ERROR = CODE; defaultSeed: INT = 1354117939; numCalls: INTEGER = 3; PrivateData: TYPE = REF PrivateDataRep; PrivateDataRep: TYPE = MONITORED RECORD [ a: ARRAY Index OF INT, p: Index, maxRand: CARD ]; Index: TYPE = CARDINAL [0..HighLimit]; LowIndex: TYPE = CARDINAL [1..LowLimit]; HighIndex: TYPE = CARDINAL (LowLimit..HighLimit]; HighLimit: CARDINAL = 55; LowLimit: CARDINAL = 24; Create: PUBLIC PROC [range, seed: INT] RETURNS [rs: RandomStream] = { pd: PrivateData м NEW[PrivateDataRep]; rs м NEW[RandomStreamRep м [seed: seed, data: pd]]; { minSeed: INT; maxSeed: INT; IF range <= 0 THEN pd.maxRand м LOOPHOLE[range м LAST[INT], CARD] + 1 ELSE pd.maxRand м range; minSeed м range/10; maxSeed м range - minSeed; IF seed<0 THEN seed м PickSeed[]; IF seed=0 THEN seed м defaultSeed; WHILE seedmaxSeed DO seed м seed/3 ENDLOOP; rs.seed м seed; }; { g: INT м 1; gPrev: INT м pd.a[HighLimit] м seed; FOR i: CARDINAL IN [1..HighLimit) DO p: Index м (21*i) MOD HighLimit; gSave: INT м pd.a[p] м g; g м gPrev-g; gPrev м gSave; IF g<0 THEN LOOPHOLE[g, CARD] м LOOPHOLE[g, CARD] + pd.maxRand; ENDLOOP; THROUGH [1..numCalls) DO RandomGen[pd]; ENDLOOP; pd.p м 1; }; }; NextInt: PUBLIC PROC [rs: RandomStream] RETURNS [INT] = { IF rs = NIL THEN rs м defaultStream; WITH rs.data SELECT FROM pd: PrivateData => RETURN [NextIntEntry[pd]]; ENDCASE => ERROR; }; NextIntEntry: ENTRY PROC [pd: PrivateData] RETURNS [INT] = { p: Index м pd.p - 1; IF p=0 THEN { RandomGen[pd]; p м HighLimit }; RETURN[pd.a[pd.p м p]]; }; RandomGen: PROC [pd: PrivateData] = { maxRand: CARD м pd.maxRand; FOR i: LowIndex IN LowIndex DO g: INT м pd.a[i] - pd.a[i+(HighLimit-LowLimit)]; IF g<0 THEN LOOPHOLE[g, CARD] м LOOPHOLE[g, CARD] + maxRand; pd.a[i] м g; ENDLOOP; FOR i: -- HighIndex -- [0..HighLimit] IN HighIndex DO -- because compiler bias bug g: INT м pd.a[i] - pd.a[i-LowLimit]; IF g<0 THEN LOOPHOLE[g, CARD] м LOOPHOLE[g, CARD] + maxRand; pd.a[i] м g; ENDLOOP; }; ChooseInt: PUBLIC PROC [rs: RandomStream, min, max: INT] RETURNS [INT--[min..max]--] = { intervalLen: CARD; IF min > max THEN ERROR BadInterval; intervalLen м LOOPHOLE[max - min, CARD] + 1; IF rs = NIL THEN rs м defaultStream; WITH rs.data SELECT FROM pd: PrivateData => { IF (intervalLen <= 0) OR (intervalLen > pd.maxRand) THEN ERROR BadInterval; DO r: CARD м NextIntEntry[pd]; rem: CARD м r; IF rem >= intervalLen THEN { rem м r MOD intervalLen; IF (r - rem) > (pd.maxRand-intervalLen) THEN LOOP; }; RETURN[min + rem]; ENDLOOP; }; ENDCASE => ERROR; }; PickSeed: PROC [] RETURNS [INT] = { RETURN[ABS[LOOPHOLE[TicksForSeed[], INT]]]; }; TicksForSeed: PROC RETURNS [CARD] = TRUSTED MACHINE CODE { "XR_TicksSinceBoot" }; defaultStream: RandomStream м Create[range: 0, seed: 0]; }. CHANGE LOG Created by MBrown on July 2, 1979 Changed by MBrown on May 2, 1980 11:07 PM Changed by MBrown on September 25, 1980 9:41 AM Changed by MBrown on December 6, 1980 9:59 PM Changed by MBrown on March 9, 1982 10:37 am Changed by MBrown on June 8, 1982 10:59 am Changed by MBrown on August 27, 1982 3:09 pm Changed by Taft on June 9, 1983 3:48 pm ║ RandomImpl.mesa Copyright ╙ 1985, 1986, 1988, 1990, 1991 by Xerox Corporation. All rights reserved. For Portable Cedar MBrown on August 27, 1982 3:09 pm Taft on June 9, 1983 3:49 pm Russ Atkinson (RRA) February 5, 1985 2:53:23 pm PST Doug Wyatt, December 15, 1986 3:21:14 pm PST Carl Hauser, February 10, 1988 11:14:23 am PST Willie-s, June 18, 1990 5:18 pm PDT Constant definitions Described in InitRandom below. Described in InitRandom below. Module state Holds 55 random long integers, to be returned by Random. (A[0] is wasted to make the code generator produce better array accesses.) a[1..p-1] has not yet been returned by Random; p is [1..55] except within Random. Largest integer produced by the generator + 1. Procedures The parameters range and seed determine the sequence generated by procedure NextInt (and ChooseInt) below. If range<=0, Next will produce results in [0..LAST[INT]]; otherwise, Next will produce results in [0..range). If seed=0, a default seed value is used to determine the starting point of the sequence; if seed>0, seed is scaled if necessary and then used; if seed<0, a seed value is derived from the system clock. In any case, the seed value actually used (after scaling) is the INT value returned by Init. Avoid small values of the range parameter; the intent of range is to allow the same sequence to be produced different machines. Now scale the seed into the proper range (no log routine available...) Save this in case the user wants to reproduce this series. The array a is initialized by placing seed in a[HighLimit], and scattering the values (-1)**(i-1) * (F(i) - seed*F(i-1)) MOD pd.maxRand, 0