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

(* Last modified on Wed Mar  4 12:05:38 PST 1992 by muller                   *)
(*      modified on Fri Dec 13 16:13:14 PST 1991 by kalsow                   *)
(*      modified on Sat Aug 12 15:13:23 1989 by ellis                        *)

MODULE Poly;

(* This module provides polynomials of degree 64 with
   coefficients in the field Z(2).

   The coefficients of a polynominal are in reverse (VAX) order:
      P(x) = x^64 + c[0]*x^63 + c[1]*x^62 + c[2]*x^61 + ... + c[62]*x + c[63]

   The leading coefficient is not stored in the 64 bit
   representation of the basis polynomial.  All other
   polynomials are residues MOD the basis, hence they
   don't have an x^64 term.

   Here's the scoop:
     Most Significant -- Least Significant
        c[0]         ....   c[63]
         b0          ....    b7
         i0          ....    i1
*)

IMPORT Word;

FROM PolyBasis IMPORT
  poly64, poly72, poly80, poly88, power, power8, power16, power24;

TYPE
  DoublePoly = ARRAY [0..3] OF INTEGER;

PROCEDURE Sum (p, q: T) : T =
  VAR r : T;
  BEGIN
    r[0] := Word.Xor (p[0], q[0]);
    r[1] := Word.Xor (p[1], q[1]);
    RETURN r;
  END Sum;

PROCEDURE Product (p, q: T) : T =
  (* returns (p * q MOD PolyBasis.P) *)
  VAR
    temp, accum : DoublePoly;
  BEGIN
    (* zero the temporaries *)
    temp[0]:=0;  temp[1]:=0;  temp[2]:=0;  temp[3]:=0;
    accum := temp;

    (* form the 128 bit product in accum *)
    temp[0] := p[0];  temp[1] := p[1];
    FOR j := 0 TO 1 DO
      FOR i := 31 TO 0 BY -1 DO
        IF Word.And (q[j], Word.Shift (1, i)) # 0 THEN
	  DoubleINC (accum, temp); END;
        DoubleTimesX (temp); END; END;

    (* collapse and return the accumulated result MOD P *)
    RETURN  ComputeMod (accum, ZERO);
  END Product;


PROCEDURE ComputeMod (READONLY source: ARRAY OF INTEGER; init: T) : T =

  (* This is the main ``internal'' procedure. It returns the A MOD PolyBasis.P
     where A is 'init' concatenated with the string of 'count' contiguous
     integers pointed to by 'source'. *)

  VAR
    result: T;
    temp0, temp1, temp2, temp3: INTEGER;
  BEGIN
    result := init;
    FOR i := 0 TO LAST (source) DO
      temp3 := Word.Extract (result[0], 24, 8);
      temp2 := Word.Extract (result[0], 16, 8);
      temp1 := Word.Extract (result[0],  8, 8);
      temp0 := Word.Extract (result[0],  0, 8);

      result[0] := Word.Xor (result[1],
                             Word.Xor (Word.Xor (poly88[temp0][0],
                                                 poly80[temp1][0]),
                                       Word.Xor (poly72[temp2][0],
	                                         poly64[temp3][0])));
      result[1] := Word.Xor (source[i],
                             Word.Xor (Word.Xor (poly88[temp0][1],
                                                 poly80[temp1][1]),
                                       Word.Xor (poly72[temp2][1],
                                                 poly64[temp3][1])));
    END;
    RETURN (result);
  END ComputeMod;


PROCEDURE Power (d: CARDINAL) : T =
  (* returns x^d MOD PolyBasis.P *)
  VAR
    tmp0, tmp1, tmp2, tmp3 : INTEGER;
    i : [0..15];
  BEGIN
    tmp3 := Word.Extract (d, 24, 8);
    tmp2 := Word.Extract (d, 16, 8);
    tmp1 := Word.Extract (d,  8, 8);
    tmp0 := Word.Extract (d,  0, 8);

    (* find the non-zero bytes of 'd' *)
    i := 0;
    IF (tmp0 # 0) THEN i := 1; END;
    IF (tmp1 # 0) THEN INC (i,2); END;
    IF (tmp2 # 0) THEN INC (i,4); END;
    IF (tmp3 # 0) THEN INC (i,8); END;

    CASE i OF
    | 0  => RETURN ONE;
    | 1  => RETURN power [tmp0]
    | 2  => RETURN power8 [tmp1];
    | 3  => RETURN Product (power8 [tmp1], power [tmp0]);
    | 4  => RETURN power16 [tmp2];
    | 5  => RETURN Product (power16 [tmp2], power [tmp0]);
    | 6  => RETURN Product (power16 [tmp2], power8 [tmp1]);
    | 7  => RETURN Product (power16 [tmp2], 
                            Product(power8 [tmp1], power [tmp0]));
    | 8  => RETURN power24 [tmp3]
    | 9  => RETURN Product (power24 [tmp3], power [tmp0]);
    | 10 => RETURN Product (power24 [tmp3], power8 [tmp1]);
    | 11 => RETURN Product (power24 [tmp3],
                            Product(power8 [tmp1], power [tmp0]));
    | 12 => RETURN Product (power24 [tmp3], power16 [tmp2]);
    | 13 =>  RETURN Product (power24 [tmp3],
                             Product(power16 [tmp2], power [tmp0]));
    | 14 => RETURN Product (power24 [tmp3],
                            Product(power16 [tmp2], power8 [tmp1]));
    | 15 => RETURN Product (Product (power24 [tmp3], power16 [tmp2]),
                            Product (power8 [tmp1], power [tmp0]));
    END;

  END Power;

PROCEDURE TimesX (p : T) : T =
  (* return (p * X^1) *)
  VAR result : T;
  BEGIN
    result[0] := LSR (p[0], 1);
    IF Word.And (p[1], 1) = 1 THEN result[0] := Word.Or (result[0], -1) END;
    result[1] := LSR (p[1], 1);
    RETURN result;
  END TimesX;

PROCEDURE DoubleINC (VAR a,b : DoublePoly) =
(*  a := a + b *)
BEGIN
  a[0] := Word.Xor (a[0], b[0]);
  a[1] := Word.Xor (a[1], b[1]);
  a[2] := Word.Xor (a[2], b[2]);
  a[3] := Word.Xor (a[3], b[3]);
END DoubleINC;

PROCEDURE DoubleTimesX (VAR a : DoublePoly) =
(* a := a*x  *)
BEGIN
  a[0] := LSR (a[0],1); 
  IF Word.And (a[1], 1) # 0 THEN a[0] := Word.Or (a[0], FIRST (INTEGER)); END;
  a[1] := LSR (a[1],1);    
  IF Word.And (a[2], 1) # 0 THEN a[1] := Word.Or (a[1], FIRST (INTEGER)); END;
  a[2] := LSR (a[2],1); 
  IF Word.And (a[3], 1) # 0 THEN a[2] := Word.Or (a[2], FIRST (INTEGER)); END;
  a[3] := LSR (a[3],1);
END DoubleTimesX;

(********
PROCEDURE LSL (a, cnt : INTEGER) : INTEGER =
(* return 'a' shifted 'cnt' bits to the left,
   with zeros filling from the right *)
BEGIN
  RETURN Word.Shift (a, cnt);
END LSL;
******)

PROCEDURE LSR (a, cnt : INTEGER) : INTEGER =
(* return 'a' shifted 'cnt' bits to the right,
   with zeros filling from the left *)
BEGIN
  RETURN Word.Shift (a, -cnt);
END LSR;

BEGIN
  <* ASSERT BITSIZE (INTEGER) = 32 AND BITSIZE (CHAR) = 8 *>
END Poly.