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

(* Last modified on Wed Jan  8 10:06:04 PST 1992 by kalsow         *)
(*      modified on Mon Jan 22 09:11:29 1990 by muller         *)


UNSAFE 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, ADR (buffer[0]), i);
        DEC (length, i);
        INC (start, i);
      END;
    END;
    RETURN result;
  END FromText;


PROCEDURE Extend (t: T;  addr: ADDRESS;  cnt: INTEGER): T =
  (* returns the fingerprint of t concatenated with the characters of p *)

  CONST
    ChunkSize = 250;
  TYPE
    CharBuf = ARRAY [0.. (1 + ChunkSize) * BYTESIZE (INTEGER) - 1] OF CHAR;
    CharPtr = UNTRACED REF CharBuf;
  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..ChunkSize-1] OF INTEGER;
    p: CharPtr := addr;
  BEGIN
    intCount := cnt DIV 4		(* number of full integers *);
    residueBits := 8 * (cnt 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;

    (* crunch the full sized chunks *)
    WHILE (intCount > LAST (ip)) DO
      FOR i := 0 TO LAST (ip) 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 (ip, result);
      DEC (intCount, NUMBER (ip));
      INC (p, BYTESIZE (ip));
      start := residueBits DIV 8;
    END;

    (* finally, crunch any remaining bits *)
    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.