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

(* Last modified on Tue Feb 13 15:42:53 1990 by kalsow         *)
(*      modified on Mon Jan 22 09:11:29 1990 by muller         *)


MODULE FPrint;

(* This module contains the routines for computing fingerprints for strings.
   Externally a fingerprint is an opaque object of 64 bits. Internally a
   fingerprint is a polynomial of degree 64 over Z[2]. *)

IMPORT Text, Poly, Word;

PROCEDURE FromText (t: Text.T): T =
  (* returns the fingerprint of t *)
  VAR result: T;  length, start: CARDINAL;  buffer: ARRAY [0..999] OF CHAR;
  BEGIN
    result := Poly.ONE;
    length := Text.Length (t);
    start := 0;
    WHILE (length > 0) DO
      WITH i = MIN (length, 1000) DO
        Text.SetChars (buffer, Text.Sub (t, start, i));
        result := Extend (result, buffer, i);
        DEC (length, i);
        INC (start, i);
      END;
    END;
    RETURN result;
  END FromText;

PROCEDURE Extend (t: T; READONLY p: ARRAY [0..999] OF CHAR; c: INTEGER): T =
  (* returns the fingerprint of t concatenated with the characters of p *)

  VAR
    init: Poly.T;			(* first two words of input *)
    result: Poly.T;			(* fingerprint of the input *)
    intCount, start: CARDINAL;		(* number of full integers in input *)
    residueBits: [0 .. 24];		(* number of leftover bits *)
    temp: ARRAY [0..0] OF INTEGER;	(* intermediate result *)
    ip: ARRAY [0..250] OF INTEGER;

  BEGIN
    intCount := c DIV 4			(* number of full integers *);
    residueBits := 8 * (c MOD 4)	(* number of leftover bits *);
    result := t;

    IF residueBits # 0 THEN
      (* Assign to temp the fingerprint of t concatenated with the first
         residueBits bits of the input. Then compute the fingerprint of temp
         concatenated with the rest of the input *)
      init [0] := Word.Shift (result [0], 32 - residueBits);
      init [1] := Word.Xor (Word.Shift (result [0], -residueBits),
                            Word.Shift (result [1], 32 - residueBits));
      CASE residueBits OF <*NOWARN*>
      |  8 =>  temp[0] := Word.Xor (Word.Shift (result [1], -residueBits),
                                    Word.Shift (ORD (p[0]), 24));
      | 16 =>  temp[0] := Word.Xor (Word.Shift (result [1], -residueBits),
                                    Word.Or (Word.Shift (ORD (p[0]), 16),
				             Word.Shift (ORD (p[1]), 24)));
      | 24 =>  temp[0] := Word.Xor (Word.Shift (result [1], -residueBits),
                                 Word.Or (Word.Shift (ORD (p[0]), 8),
                                 Word.Or (Word.Shift (ORD (p[1]), 16),
				          Word.Shift (ORD (p[2]), 24))));
      END;
    
      result := Poly.ComputeMod (temp, init);
    END;


    start := residueBits DIV 8;
    FOR i := 0 TO intCount - 1 DO
      ip [i] := Word.Or (            ORD (p [start]),
	        Word.Or (Word.Shift (ORD (p[start+1]), 8),
                Word.Or (Word.Shift (ORD (p[start+2]), 16),
	                 Word.Shift (ORD (p[start+3]), 24))));
      INC (start, 4);
    END;

    result := Poly.ComputeMod (SUBARRAY (ip, 0, intCount), result);
    RETURN (result);
  END Extend;

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