(* Copyright (C) 1989, Digital Equipment Corporation           *)
(* All rights reserved.                                        *)
(* See the file COPYRIGHT for a full description.              *)

(* Created September 1989 by Bill Kalsow                       *)
(* Based on Random.mod by Mark R. Brown                        *)
(* Last modified on Thu Jan 25 22:46:01 PST 1990 by stolfi     *)
(*      modified on Thu Nov  2 18:28:01 1989 by muller         *)
(*      modified on Fri Sep 29 09:38:39 1989 by kalsow         *)

MODULE Random;

IMPORT Word, Time, UID;

CONST
  DefaultSeed = 1202056903;

REVEAL
  T = BRANDED REF RECORD
        i: [0..56];
        a: ARRAY [1..55] OF INTEGER;
      END;

VAR default: T;

PROCEDURE New (seed: INTEGER := 0): T =
  VAR result: T;
  BEGIN
    result := NEW (T);
    Start (result, seed);
    RETURN (result);
  END New;

PROCEDURE Start (self: T := Default; seed: INTEGER := 0) =
  VAR
    j, k: INTEGER;
    i2: [1..54];
  BEGIN
    IF self = Default THEN self := default;  END;

    IF seed = 0 THEN
      seed := DefaultSeed;
    ELSIF seed = -1 THEN
      seed := RandomSeed ();
    END;

    (* For an explanation of this initialization procedure see the Fortran
       program in Section 3.6 of Knuth Volume 2, second edition. *)
    WITH z = self^ DO
      z.a[55] := seed;
      j := seed;
      k := 1;
      FOR i := 1 TO 54 DO
        i2 := (21 * i) MOD 55;
        z.a[i2] := k;
        k := j - k; (* ignore underflow *)
        j := z.a[i2];
      END;
      FOR i := 1 TO 20 DO Next55 (self) END;
    END;
  END Start;

PROCEDURE RandomSeed (): INTEGER =
  VAR
    seed, i, j: INTEGER;
    constant: UID.Constant;
    counter: UID.FineCounter;
    now: Time.T;
  BEGIN
    (* XOR everything we can get our hands on. The idea here is to move
       around volitile portions of these quantities so that we will get as
       many random bits as possible. The constant is just so that if some
       other machine does this same thing at the same time it will get
       different results. -- Garret *)

    UID.GetConstant (constant);
    UID.GetFineCounter (counter);
    now := Time.Now ();
    i := now.microseconds;
    j := counter.coarse;

    seed := DefaultSeed;
    seed := Word.Xor (seed, Word.Shift (constant[0], 24));
    seed := Word.Xor (seed, Word.Shift (constant[1], 18));
    seed := Word.Xor (seed, Word.Shift (constant[2], 12));
    seed := Word.Xor (seed, Word.Shift (constant[3], 6));
    seed := Word.Xor (seed, Word.Shift (constant[4], 3));
    seed := Word.Xor (seed, Word.Shift (constant[5], 0));
    seed := Word.Xor (seed, 4139 * counter.fine);
    seed := Word.Xor (seed, Word.Shift (j MOD 256, 24));
    seed := Word.Xor (seed, Word.Shift ((j DIV 256) MOD 256, 16));
    seed := Word.Xor (seed, Word.Shift ((j DIV (256 * 256)) MOD 256, 8));
    seed := Word.Xor (seed, (j DIV (256 * 256 * 256)) MOD 256);
    seed := Word.Xor (seed, i);

    (* normalize the seed *)
    IF seed < 0 THEN seed :=  -(seed + 1);  END;
    IF seed > 9 * (LAST (CARDINAL) DIV 10) THEN
      seed := (seed DIV (j MOD 7 + 2)) + (i MOD 23);
    END;
    WHILE seed < LAST (CARDINAL) DIV 10 DO
      seed := seed * (j MOD 7 + 2) + (i MOD 23);
    END;

    RETURN seed;
  END RandomSeed;

PROCEDURE Next55 (self: T) =
  BEGIN
    WITH z = self^ DO
      FOR j := 55 TO 32 BY  -1 DO
        DEC (z.a[j], z.a[j - 31]); (* ignore underflow *)
      END;
      FOR j := 31 TO 1 BY  -1 DO
        DEC (z.a[j], z.a[j + 24]); (* ignore underflow *)
      END;
      z.i := 56;
    END;
  END Next55;

PROCEDURE Integer (self: T := Default): INTEGER =
  BEGIN
    IF self = Default THEN self := default;  END;
    WITH z = self^ DO
      LOOP
        DEC (z.i);
        IF z.i > 0 THEN EXIT END;
        Next55 (self);
      END;
      RETURN (z.a[z.i]);
    END;
  END Integer;

PROCEDURE Cardinal (self: T := Default): CARDINAL =
  BEGIN
    IF self = Default THEN self := default;  END;
    WITH z = self^ DO
      LOOP
        DEC (z.i);
        IF z.i > 0 THEN EXIT END;
        Next55 (self);
      END;
      RETURN (Word.And (2147483647, z.a[z.i]));
    END;
  END Cardinal;

PROCEDURE Subrange (self: T; first, last: CARDINAL): CARDINAL =
  VAR card, card1, range: CARDINAL;
  BEGIN
    IF self = Default THEN self := default;  END;
    WITH z = self^ DO
      LOOP
        LOOP
          DEC (z.i);
          IF z.i > 0 THEN EXIT END;
          Next55 (self);
        END;
        card := Word.And (2147483647, z.a[z.i]);
        IF first > last THEN RETURN (card);  END;
        range := last - first;
        IF range = LAST (CARDINAL) THEN RETURN (card);  END;
        INC (range);
        card1 := card - card MOD range;
        IF card1 <= LAST (CARDINAL) - range THEN
          RETURN (first + (card - card1));
        END;
      END;
    END;
  END Subrange;

BEGIN
  default := New ();
END Random.