-- CoordinatorTransIDImpl.mesa
-- Transaction ID generator.
-- Last edited by
--   MBrown on November 3, 1982 3:29 pm

-- NOTES:
-- (1) random bits in TransID should be more unpredictable; someone who sees enough
--consecutive TransIDs should not be able to guess the next one, even knowing
--the TransID generation algorithm.
-- (2) need to implement controlled shutdown (and restart) of TransID generator?
--Note that the value of maxSeqNumsIssuedWithoutForce may only be decreased after
--a controlled shutdown (not after a crash); increasing it is always OK.

  DIRECTORY
    AlpineEnvironment,
    AlpineInternal,
    ConcreteTransID,
    Coordinator,
    CoordinatorInternal USING [],
    Log;

CoordinatorTransIDImpl: MONITOR
  IMPORTS
    Log
  EXPORTS
    AlpineEnvironment,
    AlpineInternal,
    CoordinatorInternal =
  BEGIN
  VolumeID: TYPE = AlpineEnvironment.VolumeID;

  TransID: PUBLIC TYPE = ConcreteTransID.TransID;
    -- AlpineEnvironment.TransID.
  CoordinatorObject: PUBLIC TYPE = Coordinator.Object;
    -- AlpineInternal.CoordinatorObject.

  myFileStoreID: VolumeID;
  randomSeed: INT ← 0;
  lastSeqNum: INT ← INT.FIRST;
    -- The largest transaction sequence number ever issued.
  nSeqNumsIssuedSinceForce: INT [0 .. maxSeqNumsIssuedWithoutForce];
  maxSeqNumsIssuedWithoutForce: INT = 8;
  nextForceLogRecordID: Log.RecordID;


  NoticeCoordinatorBegin: PUBLIC PROC [trans: TransID] = {
    lastSeqNum ← MAX [trans.idOnFileStore, lastSeqNum];
    randomSeed ← trans.randomBits;
    };

  InitTransIDGenerator: PUBLIC ENTRY PROC [fileStore: VolumeID] = {
    myFileStoreID ← fileStore;
    lastSeqNum ← lastSeqNum + (2*maxSeqNumsIssuedWithoutForce - 1);
    nSeqNumsIssuedSinceForce ← 0;
    -- nextForceLogRecordID will be initialized on first call to NextTransID, since
    --nSeqNumsIssuedSinceForce = 0.
    InitRandom[randomSeed];
    };

  NextTransID: PUBLIC ENTRY PROC [c: Coordinator.Handle] = {
    IF nSeqNumsIssuedSinceForce = maxSeqNumsIssuedWithoutForce THEN {
      Log.Force[followingRecord: nextForceLogRecordID];
      nSeqNumsIssuedSinceForce ← 0 };
    c.transID ← TransID[
      fileStore: myFileStoreID,
      idOnFileStore: (lastSeqNum ← lastSeqNum + 1),
      randomBits: Random[]];
    [thisRecord: c.beginRecord, followingRecord: c.forceRecord] ← Log.CoordinatorWrite[
      c, coordinatorBegin, Log.nullBlock];
    IF nSeqNumsIssuedSinceForce = 0 THEN nextForceLogRecordID ← c.forceRecord;
    nSeqNumsIssuedSinceForce ← nSeqNumsIssuedSinceForce + 1;
    };

  -- Additive random number generator using the recurrence  y(n) = y(n-55) - y(n-24).
  --See Knuth Algorithm 3.2.2 A (Volume 2, second edition, p.27.)

  y: ARRAY [0..55] OF INT; -- y[0] included to improve the compiled code.
  j, k: INTEGER [0..55];

  Random: INTERNAL PROC [] RETURNS [result: INT] = INLINE {
    result ← y[k] - y[j];
    y[k] ← result;
    IF (j ← j-1) = 0 THEN j ← 55;
    IF (k ← k-1) = 0 THEN k ← 55;
    RETURN [result]
    };

  InitRandom: INTERNAL PROC [seed: INT] = {
    numCalls: INTEGER = 289;
    minSeed: INT = INT.LAST / 10;
    maxSeed: INT = minSeed * 9;
    defaultSeed: INT = 1354117939;
    g, gPrev, gSave: INT;

    IF seed = 0 OR seed = INT.FIRST THEN seed ← defaultSeed;
    seed ← seed.ABS;
    WHILE seed<minSeed DO seed ← seed*3 ENDLOOP;
    WHILE seed>maxSeed DO seed ← seed/3 ENDLOOP;
    
    -- The array y is initialized by placing seed in y[55], and scattering the values

    --  (-1)**(i-1) * (F(i) - seed*F(i-1)), 0<i<55,

    -- (where F(i) denotes the i-th Fibonacci number) throughout the rest of y.  Then
    --the generating procedure Random is called, numCalls times, to make things
    --sufficiently random.

    y[55] ← gPrev ← seed;
    g ← 1;
    FOR i: CARDINAL IN [1..54] DO
      y[(21*i) MOD 55] ← gSave ← g;  g ← gPrev-g;  gPrev ← gSave;
      ENDLOOP;
    j ← 24; k ← 55;
    THROUGH [1..numCalls] DO [] ← Random[] ENDLOOP;
    };
  
  END.