-- File: Passworder.mesa,  Last Edit: HGM  December 7, 1980  12:23 PM

DIRECTORY
  Inline USING [BITAND, BITNOT, BITSHIFT, COPY, LowHalf, HighHalf],
  System USING [GetGreenwichMeanTime],
  Password USING [];

Passworder: PROGRAM IMPORTS Inline, System EXPORTS Password =
  BEGIN

  Encrypted: PUBLIC TYPE = RECORD [
    a: ARRAY [0..2) OF WORD, b: ARRAY [0..2) OF WORD, c: ARRAY [0..4) OF WORD];

  Encrypt: PUBLIC PROCEDURE [name, password: STRING] RETURNS [e: Encrypted] =
    BEGIN
    e.a ← [0, 0];
    FOR i: CARDINAL IN [0..name.length) DO
      c: WORD ← LOOPHOLE[name[i]];
      RightShift6[LOOPHOLE[@e.a], 2];
      e.a[0] ← e.a[0] + LeftShift9[c];
      ENDLOOP;
    e.b ← LOOPHOLE[System.GetGreenwichMeanTime[]];
    e.c ← ComputePassword[e.a, e.b, password];
    END;

  Check: PUBLIC PROCEDURE [password: STRING, old: Encrypted] RETURNS [BOOLEAN] =
    BEGIN RETURN[old.c = ComputePassword[old.a, old.b, password]]; END;


  -- Computation is:
  --  x ← 16-bit number extracted from password
  --  x ← 16-bit number extracted from password
  --  c ← -a*x*x + b*y

  ComputePassword: PROCEDURE [a, b: ARRAY [0..2) OF WORD, password: STRING]
    RETURNS [c: ARRAY [0..4) OF WORD] =
    BEGIN
    x, y: ARRAY [0..2) OF WORD ← ALL[0];
    p: POINTER TO ARRAY [0..2) OF WORD;
    t, s: ARRAY [0..4) OF WORD;
    one: ARRAY [0..4) OF WORD ← [0, 0, 0, 1];
    FOR i: CARDINAL IN [0..password.length) DO
      c: WORD ← LOOPHOLE[UpperCase[password[i]]];
      p ← IF ((c MOD 3) = 1) THEN @x ELSE @y;
      RightShift6[LOOPHOLE[p], 2];
      p[0] ← p[0] + (c*512); -- Left Shift 9

      ENDLOOP;
    -- Now we have a,b,x,y
    Mult[LOOPHOLE[@t], LOOPHOLE[@x], LOOPHOLE[@x], 1]; -- t ← x*x
    Mult[LOOPHOLE[@t], LOOPHOLE[@t], LOOPHOLE[@a], 2]; -- t ← a*x*x
    -- negate t
    FOR i: CARDINAL IN [0..4) DO t[i] ← Inline.BITNOT[t[i]]; ENDLOOP;
    Add[LOOPHOLE[@t], LOOPHOLE[@t], LOOPHOLE[@one], 4];
    Mult[LOOPHOLE[@s], LOOPHOLE[@b], LOOPHOLE[@y], 2]; -- s ← b*y
    Add[LOOPHOLE[@c], LOOPHOLE[@t], LOOPHOLE[@s], 4];
    END;

  UpperCase: PROCEDURE [c: CHARACTER] RETURNS [CHARACTER] =
    -- Copy over from StringsB to avoid not-in-memory problems from interrupt routine on the Alto
    BEGIN IF c IN ['a..'z] THEN c ← c + ('A - 'a); RETURN[c]; END;

  RightShift6: PROCEDURE [a: POINTER TO ARRAY OF WORD, n: CARDINAL] =
    BEGIN THROUGH [0..6) DO RightShift[a, n]; ENDLOOP; END;

  LeftShift9: PROCEDURE [w: WORD] RETURNS [WORD] = INLINE {RETURN[w*512]; };

  RightShift: PROCEDURE [a: POINTER TO ARRAY OF WORD, n: CARDINAL] =
    BEGIN
    ci: WORD ← 0;
    FOR i: CARDINAL IN [0..n) DO
      new: WORD ← Inline.BITSHIFT[a[i], -1] + ci;
      ci ← IF (Inline.BITAND[a[i], 1]) = 0 THEN 0 ELSE 100000B;
      a[i] ← new;
      ENDLOOP;
    END;

  Add: PROCEDURE [a, b, c: POINTER TO ARRAY OF WORD, n: CARDINAL] =
    BEGIN
    carry: BOOLEAN ← FALSE;
    FOR i: CARDINAL DECREASING IN [0..n) DO
      temp: LONG CARDINAL ← LONG[b[i]] + LONG[c[i]];
      IF carry THEN temp ← temp + 1;
      carry ← Inline.HighHalf[temp] # 0;
      a[i] ← Inline.LowHalf[temp];
      ENDLOOP;
    END;

  Mult: PROCEDURE [a, b, c: POINTER TO ARRAY OF WORD, n: CARDINAL] =
    BEGIN
    n2: CARDINAL ← 2*n;
    bb: ARRAY [0..10B) OF WORD ← ALL[0];
    Inline.COPY[to: @bb, nwords: n, from: b];
    RightShift[LOOPHOLE[@bb], n2];
    FOR i: CARDINAL IN [0..n2) DO a[i] ← 0; ENDLOOP;
    FOR i: CARDINAL IN [0..n*16 - 1) DO
      w: WORD ← c[i/16];
      IF INTEGER[Inline.BITSHIFT[w, i MOD 16]] < 0 THEN
	Add[a, a, LOOPHOLE[@bb], n2];
      RightShift[LOOPHOLE[@bb], n2];
      ENDLOOP;
    END;

  END.