This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Fingerprinting code



In private email, Jason Merrill requested that I contribute the
following code for use in GCC.  This code is a port of the Modula-3
fingerprinting algorithm to C.  The fingerprinting algorithm is a
provably good 64-bit hash function; the chance of two random strings
colliding is provably small.  It is useful for providing very good
hashes; if the fingerprints match you can be extremely confident that
the original strings matched.

Another nice property is that you can build a new hash given two
hashes.  So, for instance, you can easily use this code to fingerprint
a binary tree by fingerprinting the left and right subtrees, and then
calling fingerprint_combine.

This code is under a BSD-style copyright, at the request of someone
instrumental to its existence.  It may be freely used in any software,
GPL'd or not.

Since CodeSourcery has a blanket copyright assignment on file for
*all* GNU software projects, I think that's all Jason should need to
start using it.

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com

/***********************************************************************

 File:   fingerprint.h
 Author: Mark Mitchell
 Date:   05/31/1998

 Contents: A port of the Modula-3 fingerpinting module to C.

 Copyright (c) 1998 Mark Mitchell.  All rights reserved.

 Redistribution and use in source and binary forms are permitted
 provided that the above copyright notice and this paragraph are
 duplicated in all such forms.  The name Mark Mitchell may not be used
 to endorse or promote products derived from this software without
 specific prior written permission.  THIS SOFTWARE IS PROVIDED ``AS
 IS'' AND WITHOUT EXPRESS OR IMPLIED WARRANTIES, INCLUDING, WITHOUT
 LIMITATION, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
 A PARTICULAR PURPOSE.

***********************************************************************/

#ifndef FINGERPRINT_H
#define FINGERPRINT_H

#ifdef __cplusplus
extern "C" {
#endif /* ifdef __cplusplus */

/***********************************************************************
  Notes									
***********************************************************************/

/* Origins
   -------

   The contents of this module are derived from the fingerprinting
   routines provided in the Digital Equipment Corporation Modula-3
   sources.  The entire contents of the source distribution are
   available at:

     http://www.research.digital.com/SRC/m3sources/html/INDEX.html

   The fingerprinting algorithm is just a hashing algorithm, but it is
   a very good one: the probability of collisions is provably
   negligible.  There is a precise description of this property at the
   above URL.  

   Implementation
   --------------

   The code below contains two variants: one for machines which have a
   native 64-bit little-endian integral type, and one for all other
   systems.  (Actually, the "portable" code will not work on those
   systems which have bytes containing more than 8 bits.  In addition,
   neither version of the code will work if there is no integer type
   with the same number of bits as all pointer values.  This may occur
   either if some pointer types have more or less bits than others, or
   if there are no integer types with the right number of bits.) 

   Configuration
   -------------

   Before including this file, you may define the following macros:

     FINGERPRINT_INTEGRAL_TYPE

       If this macro is defined, it must be the name of a signed,
       64-bit, little-endian integral type.  If your system has such a
       type, you should use this macro, as it will result in faster
       code. 

     FINGERPRINT_INT_32_TYPE
     
       This macro may be defined to the name of a signed 32-bit
       integral type.  If this macro is not defined, `int' is used
       instead.  

     FINGERPRINT_POINTER_INT_TYPE 

       This macro may be defined to the name of a signed integral type
       with the same number of bits as pointer values.  If this macro
       is not defined, `int' is used instead.  

     FINGERPRINT_LITTLE_ENDIAN

       If this macro is defined to 1, the system is little-endian.  If
       this macro is defined to 0, the system is big-endian.  This
       macro may be left undefined, in which case the fingerprinting
       routines will determine the endianness at run-time.  If
       FINGERPRINT_INTEGRAL_TYPE is defined, it is assumed that the
       system is little-endian; you must not set this flag in that
       case.  

   Testing
   -------

   When the fingerprint module is initialized, if will perform some
   basic consistency checking, unless NDEBUG is defined.  In addition,
   you can build fingerprint.c, defining FINGERPRINT_TEST, to build a
   small program which tests the basic functionality of the
   fingerprint module.  You should undertake this procedure if running
   the fingerprint module in a configuration you have not used 
   before.  */

/***********************************************************************
  Macros								
***********************************************************************/

/* FINGERPRINT_USE_INTEGRAL_TYPE is defined if we have a 64-bit
   integral type to use for fingerprints.  */

#ifdef FINGERPRINT_INTEGRAL_TYPE
#define FINGERPRINT_USE_INTEGRAL_TYPE 1
#else /* ifndef FINGERPRINT_USE_INTEGRAL_TYPE */
#define FINGERPRINT_USE_INTEGRAL_TYPE 0
#endif /* ifdef FINGERPRINT_USE_INTEGRAL_TYPE */

/***********************************************************************
  Types									
***********************************************************************/

/* A fingerprint_byte_t is an unsigned 8-bit integral type:

     TYPE Byte = BITS 8 FOR [0..255];  */

typedef unsigned char fingerprint_byte_t;

/* A fingerprint_word_t w represents a sequence of Word.Size bits
   w(0), ..., w(Word.Size - 1).  It also represents the  unsigned
   number sum of 2^(i) * w(i) for i in 0, ..., Word.Size - 1.  

   The idea is that this type will occupy the natural word size of the
   machine.  */

typedef unsigned int fingerprint_word_t;

#if !FINGERPRINT_USE_INTEGRAL_TYPE
/* A fingerprint_t is a 64-bit checksum:
 
     TYPE T = RECORD
	 byte: ARRAY [0..7] OF BITS 8 FOR [0..255]
       END;  */

typedef struct fingerprint_t {
  fingerprint_byte_t
                byte[8];
			/* Externally, a fingerprint is an opaque
			   object of 64 bits.  */
} fingerprint_t;

/* Returns the address of the first byte of the fingerprint.  Use this
   macro to access the bytes in a configuration-independent manner.  */

#define FINGERPRINT_BYTE(fp) (&((fp).byte[0]))

#else /* FINGERPRINT_USE_INTEGRAL_TYPE */
typedef FINGERPRINT_INTEGRAL_TYPE fingerprint_t;
#define FINGERPRINT_BYTE(fp) ((fingerprint_byte_t*) &(fp))
#endif /* !FINGERPRINT_USE_INTEGRAL_TYPE */

/***********************************************************************
  Variables
***********************************************************************/

#if !FINGERPRINT_USE_INTEGRAL_TYPE
extern const fingerprint_t 
                fingerprint_zero;
                        /* This value is not the fingerprint of any
			   text.  */
#else /* FINGERPRINT_USE_INTEGRAL_TYPE */
#define fingerprint_zero ((fingerprint_t) 0)
#endif /* FINGERPRINT_USE_INTEGRAL_TYPE */

extern /*const*/ fingerprint_t 
                fingerprint_of_empty;
			/*  The fingerprint of the empty text.  This
			    value should be thought of as const, but
			    cannot be, since it must be dynamically
			    initialized.   */

/***********************************************************************
  Functions
***********************************************************************/

/* Initialize the fingerprint module.  This routine must be called
   before any other routine in this module.  */
extern void fingerprint_init (void);

/* Return the fingerprint of TEXT.  */
extern fingerprint_t fingerprint_from_text (const char* text);

/* Return the fingerprint of the ordered pair (FP1, FP2).  */
extern fingerprint_t fingerprint_combine (fingerprint_t fp1,
					  fingerprint_t fp2);

/* Return of the fingerprint of T and TEXT where T is the text whose
   fingerprint is FP.  */
extern fingerprint_t fingerprint_from_chars (const char*   text,
					     fingerprint_t fp);

/* Return FP1 == FP2.  */
#if !FINGERPRINT_USE_INTEGRAL_TYPE
extern int fingerprint_equal (fingerprint_t fp1,
			      fingerprint_t fp2);
#else /* FINGERPRINT_USE_INTEGRAL_TYPE */
#define fingerprint_equal(fp1, fp2) ((fp1) == (fp2))
#endif /* !FINGERPRINT_USE_INTEGRAL_TYPE */

/* Return FP1 == FP2.  This function is provided for use by
   applications which use pointers to functions when creating
   container objects, or other such data structures.  Unlike
   fingerprint_equal, fingerprint_equal_f is always a function.  */
extern int fingerprint_equal_f (fingerprint_t fp1,
				fingerprint_t fp2);

/* Return a hash code for FP.  */
extern fingerprint_word_t fingerprint_hash (fingerprint_t fp);

#ifdef __cplusplus
}
#endif /* ifdef __cplusplus */

#endif /* FINGERPRINT_H */
/***********************************************************************

 File:   fingerprint.c
 Author: Mark Mitchell
 Date:   05/31/1998

 Contents: A port of the Modula-3 fingerpinting module to C.

 Copyright (c) 1998 by Mark Mitchell.  All rights reserved.

 Redistribution and use in source and binary forms are permitted
 provided that the above copyright notice and this paragraph are
 duplicated in all such forms.  The name Mark Mitchell may not be used
 to endorse or promote products derived from this software without
 specific prior written permission.

 THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT AND EXPRESS OR
 IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.

***********************************************************************/

/***********************************************************************
  Included Files
***********************************************************************/

#include <assert.h>
#include <limits.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include "fingerprint.h"

/***********************************************************************
  Macros
***********************************************************************/

/* FINGERPRINT_INT_32_TYPE is a 32-bit signed integral type.  */

#ifndef FINGERPRINT_INT_32_TYPE 
#define FINGERPRINT_INT_32_TYPE int
#endif /* ifndef FINGERPRINT_INT_32_TYPE */

/* FINGERPRINT_POINTER_INT_TYPE is an integral type with the same
   number of bits as pointers.  */

#ifndef FINGERPRINT_POINTER_INT_TYPE
#define FINGERPRINT_POINTER_INT_TYPE int
#endif /* ifndef FINGERPRINT_POINTER_INT_TYPE */

/* FINGERPRINT_LITTLE_ENDIAN is 1 if the target is little-endian, 0 if
   it is big-endian, and undefined otherwise.  */

#if FINGERPRINT_USE_INTEGRAL_TYPE
#ifdef FINGERPRINT_LITTLE_ENDIAN
#error "You must not define FINGERPRINT_LITTLE_ENDIAN if you define FINGERPRINT_INTEGRAL_TYPE"
#else /* ifndef FINGERPRINT_LITTLE_ENDIAN */
#define FINGERPRINT_LITTLE_ENDIAN 1
#endif /* ifdef FINGERPRINT_LITTLE_ENDIAN */
#endif /* FINGERPRINT_USE_INTEGRAL_TYPE */

/* MAY_BE_LITTLE_ENDIAN is non-zero if the target might be
   little-endian.  */

#if !defined(FINGERPRINT_LITTLE_ENDIAN) || FINGERPRINT_LITTLE_ENDIAN
#define MAY_BE_LITTLE_ENDIAN 1
#else /* !(!defined(FINGERPRINT_LITTLE_ENDIAN)
	   || FINGERPRINT_LITTLE_ENDIAN) */
#define MAY_BE_LITTLE_ENDIAN 0
#endif /* (!defined(FINGERPRINT_LITTLE_ENDIAN)
	   || FINGERPRINT_LITTLE_ENDIAN) */

/* MAY_BE_LITTLE_ENDIAN is non-zero if the target might be
   big-endian.  */

#if !defined(FINGERPRINT_LITTLE_ENDIAN) || !FINGERPRINT_LITTLE_ENDIAN
#define MAY_BE_BIG_ENDIAN 1
#else /* !(!defined(FINGERPRINT_LITTLE_ENDIAN)
	   || 1FINGERPRINT_LITTLE_ENDIAN) */
#define MAY_BE_BIG_ENDIAN 0
#endif /* (!defined(FINGERPRINT_LITTLE_ENDIAN)
           || FINGERPRINT_LITTLE_ENDIAN) */

/***********************************************************************
  Types
***********************************************************************/

/* The Modula-3 INTEGER type is the type of all integers represented
   by the implementation.  Implicit in the Modula-3 fingerprinting
   algorithm is the idea that this type has the same size as a
   pointer as the code contains:

     LOOPHOLE (addr, INTEGER) 

   at one point.  */

typedef FINGERPRINT_POINTER_INT_TYPE integer_t;

/* A fingerprint_int_32_t is a 32-bit integral type:

     TYPE Int32 = [-16_7fffffff - 1 .. 16_7fffffff].  */

typedef FINGERPRINT_INT_32_TYPE 
                int_32_t;

#if !FINGERPRINT_USE_INTEGRAL_TYPE
/* A fingerprint_poly_t is a polynomial of degree [0..63] with
   coefficients in the field Z[2]:

     TYPE T = ARRAY [0..1] OF Int32;

   Because arrays are not first-class types in C, we enclose the array
   in a structure type. 

   The coefficients of a polynomial are in reverse (VAX) order: P(x) =
   x^64 + c[0] * x^63 + c[1] * x^62 + ... + 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.  */

typedef struct poly_t {
  int_32_t      array[2];
} poly_t;
#else /* FINGERPRINT_USE_INTEGRAL_TYPE */
typedef FINGERPRINT_INTEGRAL_TYPE poly_t;
#endif /* !FINGERPRINT_USE_INTEGRAL_TYPE */

/* We carefully use only names beginning with "fingerprint" in the
   external interface, but there is no reason to be so careful
   internally.  */

typedef fingerprint_byte_t byte_t;
typedef fingerprint_word_t word_t;

/***********************************************************************
  Static Function Definitions
***********************************************************************/

/* The Modula-3 `MOD' operator is such that `X MOD Y' is non-negative
   if Y is positive and non-positive if Y is negative.  C's `%'
   operator makes no such guarantee.  This function computes the
   Modula-3 MOD operation.  If your C compiler explicitly ensures a
   Modula-3-like `%' operator, you might be able to improve
   performance by replacing this function with a macro.  */

static integer_t mod (integer_t x, integer_t y)
{
  const int positive = (y > 0);
  /* We cannot use the library function `abs' to do these conversions
     since we don't know that integer_t is `int' which is the type of
     `abs'.  */
  if (x < 0)
    x = -x;
  if (y < 0)
    y = -y;
  return positive ? (x % y) : - (x % y);
}

/***********************************************************************
  Modula-3 `Word' Module
***********************************************************************/

/* (x + y) MOD 2^[Word.Size] */
#define word_plus(x, y) (((word_t) (x)) + ((word_t) (y)))

/* (x * y) MOD 2^[Word.Size] */
#define word_times(x, y) (((word_t) (x)) * ((word_t) (y)))

/* Bitwise AND of X and Y.  */
#define word_and(x, y) (((word_t) (x)) & ((word_t) (y)))

/* Bitwise OR of X and Y.  */
#define word_or(x, y) (((word_t) (x)) | ((word_t) (y)))

/* Bitwise XOR of X and Y.  */
#define word_xor(x, y) (((word_t) (x)) ^ ((word_t) (y)))

/* Bitwise complement of X.  */
#define word_not(x) (~((word_t) (x)))

/* The Modula-3 versions of word_left_shift and word_right_shift are
   in terms of Word.Shift.  Here, we code them directly.  Note that
   C's right-shift operator does not necessarily behave as desired,
   unless the operand is unsigned.  */
#define word_left_shift(x, n) (((word_t) (x)) << n)
#define word_right_shift(x, n) (((word_t) (x)) >> n)

/* Take N bits from X, with bit I as the least significant bit, and
   return them as the least significant N bits of a word whose other
   bits are 0.  */
#define word_extract(x, i, n) \
  ((((word_t) (x)) >> i) & ~(((word_t) -1) << n))

/***********************************************************************
  Modula-3 `Poly' Module
***********************************************************************/

/* Mask to grab 32 significant bits.  */

#define POLY_SIG_BITS 0xffffffff 

#if !FINGERPRINT_USE_INTEGRAL_TYPE

/* Return the Ith half of T.  */

#define POLY_HALF(t, i) ((t).array[i])

/* Form an initialization expression for the polynomial whose first
   word is T0 and whose second is T1.  */

#define POLY_INIT(t0, t1) { (t0), (t1) }

/* Construct in T the polynomial whose first word is T0 and whose
   second is T1.  */

#define POLY_FORM(t, t0, t1) \
  (POLY_HALF (t, 0) = t0, POLY_HALF (t, 1) = t1)

#else /* FINGERPRINT_USE_INTEGRAL_TYPE */

#define POLY_HALF(t, i) (((int_32_t*) &(t))[i])
#define POLY_INIT(t0, t1) \
  ((((poly_t) (t1)) << 32) | (((poly_t) (t0)) & POLY_SIG_BITS))
#define POLY_FORM(t, t0, t1) ((t) = POLY_INIT ((t0), (t1)))

#endif /* !FINGERPRINT_USE_INTEGRAL_TYPE */

/***********************************************************************
  Types
***********************************************************************/

/* TYPE IntPtr = UNTRACED REF Int32 */

typedef int_32_t* 
                int_ptr_t;

/* TYPE IntBytes = RECORD b0, b1, b2, b2: Byte END;

   The Modula-3 code assumes that it can treat these bytes as an Int32
   as well.  We therefore use a union; that guarantees that
   Int32-accesses will not be misaligned.  Note: this use of unions
   (to preform "type punning") results in implementation-defined
   behavior in ANSI/ISO C.  */

typedef union int_bytes_t {
  int_32_t      w;
  byte_t        b[4];
} int_bytes_t;

/***********************************************************************
  Variables
***********************************************************************/

#ifndef FINGERPRINT_LITTLE_ENDIAN
static int poly_little_endian;
static int poly_big_endian;
static int poly_init_done;
#else /* ifdef FINGERPRINT_LITTLE_ENDIAN */
#define poly_little_endian FINGERPRINT_LITTLE_ENDIAN
#endif /* ifndef FINGERPRINT_LITTLE_ENDIAN */

/* ONE = T { 0, FIRST (Int32) }; */

static const poly_t
                POLY_ONE = POLY_INIT (0, (-0x7fffffff - 1));

static const poly_t   
                poly64[256]
			/* poly64[i] = i(x) * x^64 MOD P */
			= {POLY_INIT (0, 0),          
			   POLY_INIT (36728807, 152935311),
			   POLY_INIT (73457614, 305870622),
			   POLY_INIT (105951273, 455519377),
			   POLY_INIT (85802743, 386180924),
			   POLY_INIT (120410384, 504970419),
			   POLY_INIT (25026873, 88051746),       
			   POLY_INIT (55414494, 203557805),
			   POLY_INIT (132578437, 494634872),    
			   POLY_INIT (97948514, 342236407),
			   POLY_INIT (59122507, 255897702),     
			   POLY_INIT (28724396, 106769385),
			   POLY_INIT (50053746, 176103492),     
			   POLY_INIT (13348245, 56802251),
			   POLY_INIT (110828988, 407115610),    
			   POLY_INIT (78344795, 291081429),
			   POLY_INIT (34699361, 159762416),     
			   POLY_INIT (2168710, 9985151),
			   POLY_INIT (108111791, 465498350),    
			   POLY_INIT (71419976, 312699745),
			   POLY_INIT (118245014, 511795404),    
			   POLY_INIT (87828849, 396163907),
			   POLY_INIT (57448792, 213538770),     
			   POLY_INIT (22869695, 94882909),
			   POLY_INIT (100107492, 352206984),    
			   POLY_INIT (130542339, 501472007),
			   POLY_INIT (26696490, 113604502),     
			   POLY_INIT (61289677, 265874457),
			   POLY_INIT (15383059, 66774964),      
			   POLY_INIT (47896052, 182942779),
			   POLY_INIT (76178909, 297914538),     
			   POLY_INIT (112855610, 417090341),
			   POLY_INIT (69398722, 319524832),     
			   POLY_INIT (101883685, 437654639),
			   POLY_INIT (4337420, 19970302),       
			   POLY_INIT (41042155, 137175921),
			   POLY_INIT (20958773, 68102364),      
			   POLY_INIT (51356114, 219329363),
			   POLY_INIT (90116603, 372514754),     
			   POLY_INIT (124747292, 522814541),
			   POLY_INIT (63179847, 242223256),     
			   POLY_INIT (32793504, 124621591),
			   POLY_INIT (128242569, 474693510),    
			   POLY_INIT (93633646, 357999625),
			   POLY_INIT (114897584, 427077540),    
			   POLY_INIT (82402647, 275330091),
			   POLY_INIT (45739390, 189765818),     
			   POLY_INIT (9011865, 38929205),
			   POLY_INIT (104040611, 445532176),    
			   POLY_INIT (67364676, 328455071),
			   POLY_INIT (39016301, 146112270),     
			   POLY_INIT (6502538, 27845761),
			   POLY_INIT (53392980, 227209004),     
			   POLY_INIT (18799027, 77034659),
			   POLY_INIT (122579354, 531748914),    
			   POLY_INIT (92145277, 380388285),
			   POLY_INIT (30766118, 133549928),     
			   POLY_INIT (65346497, 250107111),
			   POLY_INIT (95792104, 365885558),     
			   POLY_INIT (126206991, 483615737),
			   POLY_INIT (80235217, 284256340),     
			   POLY_INIT (116925750, 434959323),
			   POLY_INIT (11048223, 46817098),      
			   POLY_INIT (43580152, 198689989),
			   POLY_INIT (93937903, 358995648),     
			   POLY_INIT (128519944, 477646159),
			   POLY_INIT (33144609, 123658718),     
			   POLY_INIT (63557830, 239303249),
			   POLY_INIT (8674840, 39940604),       
			   POLY_INIT (45363711, 192735859),
			   POLY_INIT (82084310, 274351842),     
			   POLY_INIT (114617905, 424140141),
			   POLY_INIT (41917546, 136204728),     
			   POLY_INIT (5239693, 17025591),
			   POLY_INIT (102712228, 438658726),    
			   POLY_INIT (70200387, 322501929),
			   POLY_INIT (123904669, 521860740),    
			   POLY_INIT (89312634, 369585419),
			   POLY_INIT (50494803, 220316058),     
			   POLY_INIT (20058804, 71064085),
			   POLY_INIT (126359694, 484446512),    
			   POLY_INIT (95975273, 368937663),
			   POLY_INIT (65587008, 249243182),     
			   POLY_INIT (30976167, 130465185),
			   POLY_INIT (43329145, 199538188),     
			   POLY_INIT (10832286, 49884547),
			   POLY_INIT (116783543, 434077970),    
			   POLY_INIT (80057936, 281156253),
			   POLY_INIT (7267339, 26973768),       
			   POLY_INIT (39750636, 143003079),
			   POLY_INIT (68041669, 329294166),     
			   POLY_INIT (104748066, 448608985),
			   POLY_INIT (91478780, 379531636),     
			   POLY_INIT (121877787, 528657147),
			   POLY_INIT (18023730, 77858410),      
			   POLY_INIT (52652757, 230268389),
			   POLY_INIT (29069357, 107895072),     
			   POLY_INIT (59506634, 259244719),
			   POLY_INIT (98258915, 341143102),     
			   POLY_INIT (132849668, 491320753),
			   POLY_INIT (78032602, 292224540),     
			   POLY_INIT (110543165, 410477971),
			   POLY_INIT (13005076, 55691522),      
			   POLY_INIT (49684211, 172774029),
			   POLY_INIT (106785960, 454418008),    
			   POLY_INIT (74253135, 302532055),
			   POLY_INIT (37598054, 154069318),     
			   POLY_INIT (908417, 3371721),
			   POLY_INIT (54547039, 202471780),     
			   POLY_INIT (24133048, 84730603),
			   POLY_INIT (119573905, 506089082),    
			   POLY_INIT (84992630, 389535221),
			   POLY_INIT (61532236, 267099856),     
			   POLY_INIT (26904491, 116786527),
			   POLY_INIT (130692994, 500214222),    
			   POLY_INIT (100292709, 348992065),
			   POLY_INIT (112711355, 418331116),    
			   POLY_INIT (76003676, 301113955),
			   POLY_INIT (47647093, 181669618),     
			   POLY_INIT (15165074, 63542653),
			   POLY_INIT (72094921, 311433640),     
			   POLY_INIT (108821294, 462258727),
			   POLY_INIT (2935559, 11218614),       
			   POLY_INIT (35431648, 162968889),
			   POLY_INIT (22096446, 93634196),      
			   POLY_INIT (56706521, 210314523),
			   POLY_INIT (87160304, 397379978),     
			   POLY_INIT (117545495, 514986501),
			   POLY_INIT (116277429, 431580288),    
			   POLY_INIT (81669970, 279248655),
			   POLY_INIT (42901371, 193090462),     
			   POLY_INIT (12513436, 44025873),
			   POLY_INIT (66289218, 247317436),     
			   POLY_INIT (29561253, 127948851),
			   POLY_INIT (127115660, 478606498),    
			   POLY_INIT (94621291, 362508077),
			   POLY_INIT (17349680, 79881208),      
			   POLY_INIT (54055895, 232749175),
			   POLY_INIT (90727422, 385471718),     
			   POLY_INIT (123210777, 535056233),
			   POLY_INIT (68518599, 331760836),     
			   POLY_INIT (103148832, 450617163),
			   POLY_INIT (7691529, 33387482),       
			   POLY_INIT (38089454, 148957269),
			   POLY_INIT (83835092, 272409456),     
			   POLY_INIT (114251571, 421607679),
			   POLY_INIT (10479386, 34051182),      
			   POLY_INIT (45058301, 186257377),
			   POLY_INIT (31589923, 121111628),     
			   POLY_INIT (64121284, 237346755),
			   POLY_INIT (92461549, 352531282),     
			   POLY_INIT (129152522, 471771357),
			   POLY_INIT (52020305, 222766088),     
			   POLY_INIT (19508150, 73056135),
			   POLY_INIT (125377439, 528225046),    
			   POLY_INIT (88700024, 375490713),
			   POLY_INIT (100989606, 440632116),    
			   POLY_INIT (70554945, 324933819),
			   POLY_INIT (40117608, 142128170),     
			   POLY_INIT (5524111, 23408549),
			   POLY_INIT (46968951, 179497824),     
			   POLY_INIT (16572304, 61829359),
			   POLY_INIT (111964089, 411688062),    
			   POLY_INIT (77332574, 294930417),
			   POLY_INIT (131174016, 498486364),    
			   POLY_INIT (98689383, 346806227),
			   POLY_INIT (61952334, 260930370),     
			   POLY_INIT (25247401, 110158029),
			   POLY_INIT (86658290, 399076376),     
			   POLY_INIT (119153429, 517273495),
			   POLY_INIT (21664572, 99769094),      
			   POLY_INIT (58391771, 217038985),
			   POLY_INIT (3633669, 13486884),       
			   POLY_INIT (34020834, 164647083),
			   POLY_INIT (72854987, 318176314),     
			   POLY_INIT (107463212, 468412341),
			   POLY_INIT (14534678, 53947536),      
			   POLY_INIT (49129457, 170571551),
			   POLY_INIT (79501272, 286006158),     
			   POLY_INIT (109934655, 403800065),
			   POLY_INIT (96532193, 338922412),     
			   POLY_INIT (133208326, 489558051),
			   POLY_INIT (27273519, 101235890),     
			   POLY_INIT (59786952, 253044541),
			   POLY_INIT (121320595, 508341224),    
			   POLY_INIT (84630388, 391196775),
			   POLY_INIT (56355677, 209165558),     
			   POLY_INIT (23823546, 90834809),
			   POLY_INIT (36047460, 155716820),     
			   POLY_INIT (1467779, 5609307),
			   POLY_INIT (105305514, 460536778),    
			   POLY_INIT (74889805, 309239877),
			   POLY_INIT (58138714, 215790144),     
			   POLY_INIT (21450685, 96545231),
			   POLY_INIT (119013268, 518489438),    
			   POLY_INIT (86478963, 402267857),
			   POLY_INIT (107617965, 467146108),    
			   POLY_INIT (73036106, 314937075),
			   POLY_INIT (34259299, 165880418),     
			   POLY_INIT (3845764, 16693741),
			   POLY_INIT (76668127, 296170808),     
			   POLY_INIT (111260472, 414887607),
			   POLY_INIT (15794961, 60555814),      
			   POLY_INIT (46230774, 176265641),
			   POLY_INIT (26010152, 111383044),     
			   POLY_INIT (62688719, 264112523),
			   POLY_INIT (99368422, 345548058),     
			   POLY_INIT (131879425, 495271573),
			   POLY_INIT (23484475, 89748912),      
			   POLY_INIT (55982044, 205844031),
			   POLY_INIT (84314101, 392315566),     
			   POLY_INIT (121038866, 511695137),
			   POLY_INIT (75196108, 308138636),     
			   POLY_INIT (105580843, 457197827),
			   POLY_INIT (1816834, 6743442),        
			   POLY_INIT (36427493, 159088157),
			   POLY_INIT (109094078, 404943560),    
			   POLY_INIT (78695257, 289368391),
			   POLY_INIT (48266096, 169461206),     
			   POLY_INIT (13636759, 50617945),
			   POLY_INIT (60660297, 254170612),     
			   POLY_INIT (28177838, 104582779),
			   POLY_INIT (134038919, 488465130),    
			   POLY_INIT (97331808, 335608165),
			   POLY_INIT (123064472, 534199712),    
			   POLY_INIT (90554239, 382379567),
			   POLY_INIT (53808982, 233573054),     
			   POLY_INIT (17129649, 82940209),
			   POLY_INIT (38334063, 148085404),     
			   POLY_INIT (7897480, 30277907),
			   POLY_INIT (103297441, 451456386),    
			   POLY_INIT (68705862, 334837261),
			   POLY_INIT (11742237, 44874456),      
			   POLY_INIT (42157050, 196157783),
			   POLY_INIT (80999379, 278367686),     
			   POLY_INIT (115579956, 428480073),
			   POLY_INIT (95294186, 363339236),     
			   POLY_INIT (127827213, 481658475),
			   POLY_INIT (30330148, 127085306),     
			   POLY_INIT (67019459, 244232565),
			   POLY_INIT (88385785, 374536784),     
			   POLY_INIT (125093662, 525296095),
			   POLY_INIT (19167031, 74042702),      
			   POLY_INIT (51648720, 225728193),
			   POLY_INIT (5871118, 22437228),       
			   POLY_INIT (40499689, 139183843),
			   POLY_INIT (70863296, 325937778),     
			   POLY_INIT (101262887, 443609597),
			   POLY_INIT (44192892, 187268392),     
			   POLY_INIT (9583515, 37021351),
			   POLY_INIT (113413042, 420629046),    
			   POLY_INIT (83027029, 269472185),
			   POLY_INIT (129985163, 472766996),    
			   POLY_INIT (93259116, 355484059),
			   POLY_INIT (64992581, 236383498),     
			   POLY_INIT (32496290, 118191749)
			};

static const poly_t   
                poly72[256]
			/* poly72[i] = i(x) * x^72 MOD P */
			= {POLY_INIT (0, 0),                    
			   POLY_INIT (-1961202135, 335293334),
			   POLY_INIT (468213049, 344628781),    
			   POLY_INIT (-1863175408, 125220283),
			   POLY_INIT (973880089, 443020634),    
			   POLY_INIT (-1323936464, 161210060),
			   POLY_INIT (568616480, 250440567),    
			   POLY_INIT (-1426192375, 487669985),
			   POLY_INIT (2042951513, 129835956),   
			   POLY_INIT (-220292752, 339806242),
			   POLY_INIT (1647094368, 322420121),   
			   POLY_INIT (-382286775, 13342223),
			   POLY_INIT (1137232960, 500881134),   
			   POLY_INIT (-925719959, 237436280),
			   POLY_INIT (1478529401, 156256451),   
			   POLY_INIT (-751108272, 447505237),
			   POLY_INIT (-209064270, 259671912),   
			   POLY_INIT (2022932635, 478571774),
			   POLY_INIT (-396250229, 468769093),   
			   POLY_INIT (1669062050, 135066323),
			   POLY_INIT (-913975893, 354267698),   
			   POLY_INIT (1117764482, 115448228),
			   POLY_INIT (-764573550, 26684447),    
			   POLY_INIT (1501030075, 309004169),
			   POLY_INIT (-1974658581, 147285212),  
			   POLY_INIT (22509506, 456871754),
			   POLY_INIT (-1851439918, 474872561),  
			   POLY_INIT (448735995, 263311719),
			   POLY_INIT (-1337908494, 312512902),  
			   POLY_INIT (995839195, 22854160),
			   POLY_INIT (-1414955061, 103419819),  
			   POLY_INIT (548606434, 366355517),
			   POLY_INIT (-418128540, 519343825),   
			   POLY_INIT (1812575053, 218670407),
			   POLY_INIT (-50626467, 176034044),    
			   POLY_INIT (2011295348, 427965290),
			   POLY_INIT (-585111939, 76774283),    
			   POLY_INIT (1443203156, 393170973),
			   POLY_INIT (-956843196, 270132646),   
			   POLY_INIT (1307432301, 65392176),
			   POLY_INIT (-1630066115, 424258917),  
			   POLY_INIT (365773844, 179668723),
			   POLY_INIT (-2059438332, 230896456),  
			   POLY_INIT (237312301, 507451614),
			   POLY_INIT (-1529147100, 53368895),   
			   POLY_INIT (801210125, 282227625),
			   POLY_INIT (-1087157219, 396674578),  
			   POLY_INIT (875110964, 72936836),
			   POLY_INIT (345650134, 294570425),    
			   POLY_INIT (-1618977281, 41083439),
			   POLY_INIT (259157743, 84170644),     
			   POLY_INIT (-2073558842, 385383426),
			   POLY_INIT (781584591, 199834851),    
			   POLY_INIT (-1517525274, 404035445),
			   POLY_INIT (897471990, 526623438),    
			   POLY_INIT (-1100727329, 211781976),
			   POLY_INIT (1834927247, 372501005),   
			   POLY_INIT (-431707482, 97501595),
			   POLY_INIT (1991678390, 45708320),    
			   POLY_INIT (-38996065, 289759158),
			   POLY_INIT (1465057174, 206839639),   
			   POLY_INIT (-599223873, 531117249),
			   POLY_INIT (1287299759, 417235322),   
			   POLY_INIT (-945763194, 186821356),
			   POLY_INIT (-1006945373, 245093539),  
			   POLY_INIT (1222727050, 493354805),
			   POLY_INIT (-669817190, 437340814),   
			   POLY_INIT (1393100979, 166551832),
			   POLY_INIT (-101252934, 352068089),   
			   POLY_INIT (1928162963, 117443183),
			   POLY_INIT (-501260925, 7782356),     
			   POLY_INIT (1761948586, 327849026),
			   POLY_INIT (-1170223878, 153548567),  
			   POLY_INIT (824550099, 450550913),
			   POLY_INIT (-1579707965, 497838394),  
			   POLY_INIT (718143466, 240140972),
			   POLY_INIT (-2144077853, 323027533),  
			   POLY_INIT (187275722, 12397019),
			   POLY_INIT (-1680102694, 130784352),  
			   POLY_INIT (281134323, 339195894),
			   POLY_INIT (812832017, 31560651),     
			   POLY_INIT (-1150764232, 303937629),
			   POLY_INIT (731547688, 359337446),    
			   POLY_INIT (-1602165247, 110569072),
			   POLY_INIT (176090632, 461792913),    
			   POLY_INIT (-2124120031, 142232839),
			   POLY_INIT (295088945, 252508348),    
			   POLY_INIT (-1702044392, 485544746),
			   POLY_INIT (1236673096, 106737791),   
			   POLY_INIT (-1028895647, 362847209),
			   POLY_INIT (1381924721, 316026450),   
			   POLY_INIT (-649850536, 19531204),
			   POLY_INIT (1941576017, 473646373),   
			   POLY_INIT (-123701384, 264728243),
			   POLY_INIT (1750221928, 145873672),   
			   POLY_INIT (-481809855, 458092702),
			   POLY_INIT (619243207, 275733106),    
			   POLY_INIT (-1343059730, 59994596),
			   POLY_INIT (1057012734, 82166879),    
			   POLY_INIT (-1273309737, 387575753),
			   POLY_INIT (518315486, 168341288),    
			   POLY_INIT (-1778469897, 435455166),
			   POLY_INIT (84705511, 511848709),     
			   POLY_INIT (-1911099698, 226368147),
			   POLY_INIT (1563169182, 399669702),   
			   POLY_INIT (-701071433, 70144592),
			   POLY_INIT (1187269799, 56158187),    
			   POLY_INIT (-841080178, 279235709),
			   POLY_INIT (1730161287, 230001820),   
			   POLY_INIT (-331725650, 508143370),
			   POLY_INIT (2093512638, 423563953),   
			   POLY_INIT (-137225833, 180566311),
			   POLY_INIT (-681506699, 521477402),   
			   POLY_INIT (1551591004, 216610444),
			   POLY_INIT (-863414964, 195003191),   
			   POLY_INIT (1200831333, 409184417),
			   POLY_INIT (-311610516, 91416640),    
			   POLY_INIT (1719098693, 378454998),
			   POLY_INIT (-159027627, 301495917),   
			   POLY_INIT (2107572348, 33840635),
			   POLY_INIT (-1364852948, 413679278),  
			   POLY_INIT (633311493, 190059832),
			   POLY_INIT (-1253203435, 203595907),  
			   POLY_INIT (1045941308, 534678293),
			   POLY_INIT (-1800813515, 47172596),   
			   POLY_INIT (531868188, 288612450),
			   POLY_INIT (-1891526388, 373642713),  
			   POLY_INIT (73135909, 96042575),
			   POLY_INIT (-2013890746, 490187079),  
			   POLY_INIT (216799599, 248218321),
			   POLY_INIT (-1675744641, 163395434),  
			   POLY_INIT (386155606, 440474876),
			   POLY_INIT (-1107669921, 122706973),  
			   POLY_INIT (920658550, 346847115),
			   POLY_INIT (-1508765338, 333103664),  
			   POLY_INIT (755531599, 2550182),
			   POLY_INIT (-30244833, 445287155),    
			   POLY_INIT (1965616694, 158769509),
			   POLY_INIT (-438641370, 234886366),   
			   POLY_INIT (1858122511, 503070536),
			   POLY_INIT (-1002521850, 15564713),   
			   POLY_INIT (1327813935, 319902783),
			   POLY_INIT (-539564481, 342352260),   
			   POLY_INIT (1422690326, 127650322),
			   POLY_INIT (1954519540, 307097135),   
			   POLY_INIT (-10094627, 28427705),
			   POLY_INIT (1872217293, 113733634),   
			   POLY_INIT (-460477724, 356211604),
			   POLY_INIT (1316201197, 136977269),   
			   POLY_INIT (-982922044, 467022051),
			   POLY_INIT (1436286932, 480281944),   
			   POLY_INIT (-561933827, 257732302),
			   POLY_INIT (230387373, 368102811),    
			   POLY_INIT (-2036268924, 101508621),
			   POLY_INIT (374551444, 24794038),     
			   POLY_INIT (-1656136259, 310802464),
			   POLY_INIT (934761908, 261568705),    
			   POLY_INIT (-1129497699, 476779351),
			   POLY_INIT (744425613, 454928108),    
			   POLY_INIT (-1488623964, 148999546),
			   POLY_INIT (1625664034, 63121302),    
			   POLY_INIT (-335559669, 272567296),
			   POLY_INIT (2064512795, 390707643),   
			   POLY_INIT (-266888910, 79008301),
			   POLY_INIT (1525256507, 430232268),   
			   POLY_INIT (-772538606, 173603162),
			   POLY_INIT (1090636802, 221138145),   
			   POLY_INIT (-904158677, 517105527),
			   POLY_INIT (421617019, 75367458),     
			   POLY_INIT (-1841613998, 394407860),
			   POLY_INIT (46727234, 284465679),     
			   POLY_INIT (-1982632341, 50901401),
			   POLY_INIT (590177890, 505016696),    
			   POLY_INIT (-1472788405, 233167598),
			   POLY_INIT (952449883, 177434453),    
			   POLY_INIT (-1277209230, 426722499),
			   POLY_INIT (-1821621104, 213475582),  
			   POLY_INIT (410397369, 524634984),
			   POLY_INIT (-2004608599, 406060755),  
			   POLY_INIT (60716928, 198169925),
			   POLY_INIT (-1453293687, 383686052),  
			   POLY_INIT (578425248, 86162994),
			   POLY_INIT (-1299701072, 39062409),   
			   POLY_INIT (965889177, 296230943),
			   POLY_INIT (-358042679, 184828746),   
			   POLY_INIT (1639112160, 418932956),
			   POLY_INIT (-247402768, 529456487),   
			   POLY_INIT (2052751577, 208860913),
			   POLY_INIT (-794523440, 291747344),   
			   POLY_INIT (1539237625, 44014982),
			   POLY_INIT (-884156951, 99166269),    
			   POLY_INIT (1079425984, 370475947),
			   POLY_INIT (1141722341, 330071524),   
			   POLY_INIT (-820567348, 5265010),
			   POLY_INIT (1608847836, 119989193),   
			   POLY_INIT (-721453067, 349882463),
			   POLY_INIT (2114025468, 164333758),   
			   POLY_INIT (-182773291, 439853864),
			   POLY_INIT (1709779653, 490804883),   
			   POLY_INIT (-286046996, 247282949),
			   POLY_INIT (1036630972, 336682576),   
			   POLY_INIT (-1227631211, 133002694),
			   POLY_INIT (639755909, 10207357),     
			   POLY_INIT (-1388607316, 325577707),
			   POLY_INIT (130384037, 242658058),    
			   POLY_INIT (-1931481460, 495616156),
			   POLY_INIT (472767900, 452736295),    
			   POLY_INIT (-1757957195, 151002801),
			   POLY_INIT (-1216044457, 483801740),  
			   POLY_INIT (1017039998, 254415130),
			   POLY_INIT (-1402142866, 140289185),  
			   POLY_INIT (662081863, 463507255),
			   POLY_INIT (-1920427698, 112316374),  
			   POLY_INIT (110294887, 357426240),
			   POLY_INIT (-1772043145, 305877499),  
			   POLY_INIT (494578270, 29850221),
			   POLY_INIT (-834644722, 460003640),   
			   POLY_INIT (1163541287, 144126638),
			   POLY_INIT (-710408137, 266438421),   
			   POLY_INIT (1588749854, 471706755),
			   POLY_INIT (-196317673, 17624162),    
			   POLY_INIT (2136342590, 317769716),
			   POLY_INIT (-274451666, 361132623),   
			   POLY_INIT (1690197255, 108681689),
			   POLY_INIT (-1558277759, 223933237),  
			   POLY_INIT (671416232, 514119843),
			   POLY_INIT (-1191785288, 433220888),  
			   POLY_INIT (871146129, 170804878),
			   POLY_INIT (-1726829928, 390006383),  
			   POLY_INIT (302564529, 79900153),
			   POLY_INIT (-2097481823, 62232642),   
			   POLY_INIT (165714312, 273265620),
			   POLY_INIT (-623221032, 182833281),   
			   POLY_INIT (1371539697, 421133079),
			   POLY_INIT (-1053672479, 510611116),  
			   POLY_INIT (1244157384, 227763514),
			   POLY_INIT (-522822207, 276964827),   
			   POLY_INIT (1808544744, 58592845),
			   POLY_INIT (-79822600, 67681270),     
			   POLY_INIT (1881435857, 401903712),
			   POLY_INIT (1352105779, 35828829),    
			   POLY_INIT (-611512038, 299802571),
			   POLY_INIT (1266622986, 380119664),   
			   POLY_INIT (-1067103197, 89391590),
			   POLY_INIT (1788560426, 407191815),   
			   POLY_INIT (-511628797, 196700817),
			   POLY_INIT (1903368467, 214949674),   
			   POLY_INIT (-93751494, 523498684),
			   POLY_INIT (693340266, 94345193),     
			   POLY_INIT (-1572215229, 375635071),
			   POLY_INIT (851170643, 286591428),    
			   POLY_INIT (-1180583046, 48833106),
			   POLY_INIT (325038963, 536371891),    
			   POLY_INIT (-1740251814, 201607461),
			   POLY_INIT (146271818, 192085150),    
			   POLY_INIT (-2085781405, 412014344)
			};

static const poly_t   
                poly80[256]
                        /* poly80[i] = i(x) * X^80 MOD P */
			= {POLY_INIT (0, 0),                    
			   POLY_INIT (-1753253426, 125726524),
			   POLY_INIT (788460444, 251453049),    
			   POLY_INIT (-1182692782, 159560005),
			   POLY_INIT (1576920888, 502906098),   
			   POLY_INIT (-897409290, 445109198),
			   POLY_INIT (1929581732, 319120011),   
			   POLY_INIT (-461607574, 343608759),
			   POLY_INIT (-1238937829, 142717156),  
			   POLY_INIT (559429333, 268427224),
			   POLY_INIT (-1730560889, 108883613),  
			   POLY_INIT (262587721, 16974241),
			   POLY_INIT (-337991645, 360188950),   
			   POLY_INIT (2091241965, 302408490),
			   POLY_INIT (-987472961, 461689455),   
			   POLY_INIT (1381704305, 486194515),
			   POLY_INIT (1817091638, 285434313),   
			   POLY_INIT (-80615432, 377294581),
			   POLY_INIT (1118858666, 536854448),   
			   POLY_INIT (-707849116, 411160716),
			   POLY_INIT (833845518, 217767227),    
			   POLY_INIT (-1496579904, 193245703),
			   POLY_INIT (525175442, 33948482),     
			   POLY_INIT (-2009926820, 91778174),
			   POLY_INIT (-630599379, 428003629),   
			   POLY_INIT (1293330659, 519880209),
			   POLY_INIT (-191421775, 394137428),   
			   POLY_INIT (1676172159, 268460136),
			   POLY_INIT (-2020329963, 75197919),   
			   POLY_INIT (283856859, 50660067),
			   POLY_INIT (-1452620407, 176665510),  
			   POLY_INIT (1041611847, 234478746),
			   POLY_INIT (-717112057, 292817554),   
			   POLY_INIT (1111409865, 369780142),
			   POLY_INIT (-71348581, 529061099),    
			   POLY_INIT (1824536405, 418823127),
			   POLY_INIT (-2000922049, 210613856),  
			   POLY_INIT (532882417, 200530268),
			   POLY_INIT (-1505580637, 40986649),   
			   POLY_INIT (826134637, 84870949),
			   POLY_INIT (1667691036, 435534454),   
			   POLY_INIT (-199652398, 512480586),
			   POLY_INIT (1301807488, 386491407),   
			   POLY_INIT (-622364594, 276237107),
			   POLY_INIT (1050350884, 67896964),    
			   POLY_INIT (-1444647702, 57829816),
			   POLY_INIT (275113656, 183556349),    
			   POLY_INIT (-2028298378, 227456961),
			   POLY_INIT (-1190190287, 7826267),    
			   POLY_INIT (779115263, 118031463),
			   POLY_INIT (-1745760083, 244036898),  
			   POLY_INIT (9349475, 167107102),
			   POLY_INIT (-453852151, 495900585),   
			   POLY_INIT (1938668999, 451983509),
			   POLY_INIT (-905169003, 326240720),   
			   POLY_INIT (1567837787, 336357100),
			   POLY_INIT (254307370, 150395839),    
			   POLY_INIT (-1739123228, 260617347),
			   POLY_INIT (567713718, 101320134),    
			   POLY_INIT (-1230379400, 24406778),
			   POLY_INIT (1389726482, 353331021),   
			   POLY_INIT (-978652452, 309397617),
			   POLY_INIT (2083223694, 468957492),   
			   POLY_INIT (-346816192, 479057416),
			   POLY_INIT (-1486881947, 295361573),  
			   POLY_INIT (807436971, 384086809),
			   POLY_INIT (-1985935111, 526778972),  
			   POLY_INIT (517894455, 404254048),
			   POLY_INIT (-90039203, 207839447),    
			   POLY_INIT (1843226003, 186453995),
			   POLY_INIT (-732106815, 44023470),    
			   POLY_INIT (1126405647, 98685330),
			   POLY_INIT (293123198, 421227713),    
			   POLY_INIT (-2046308944, 509936637),
			   POLY_INIT (1065764834, 401060536),   
			   POLY_INIT (-1460060628, 278519172),
			   POLY_INIT (1283806022, 81973299),    
			   POLY_INIT (-604362104, 60604175),
			   POLY_INIT (1652269274, 169741898),   
			   POLY_INIT (-184231660, 224420214),
			   POLY_INIT (-888052397, 10075628),    
			   POLY_INIT (1550720157, 132633296),
			   POLY_INIT (-437283121, 241525653),   
			   POLY_INIT (1922100993, 152767657),
			   POLY_INIT (-1762885013, 492831006),  
			   POLY_INIT (26475429, 438201890),
			   POLY_INIT (-1206750729, 329047911),  
			   POLY_INIT (795674681, 350400603),
			   POLY_INIT (2100701768, 135793928),   
			   POLY_INIT (-364293242, 258368052),
			   POLY_INIT (1405671892, 115659633),   
			   POLY_INIT (-994598886, 26917965),
			   POLY_INIT (550227312, 367112698),    
			   POLY_INIT (-1212894018, 312467142),
			   POLY_INIT (238370540, 454913923),    
			   POLY_INIT (-1723185374, 476250303),
			   POLY_INIT (1914586722, 15652535),    
			   POLY_INIT (-446611540, 126925195),
			   POLY_INIT (1558230526, 236062926),   
			   POLY_INIT (-878719952, 158099442),
			   POLY_INIT (803447130, 488073797),    
			   POLY_INIT (-1197680492, 443090297),
			   POLY_INIT (18698950, 334214204),     
			   POLY_INIT (-1771951352, 345365248),
			   POLY_INIT (-1002894983, 141518419),  
			   POLY_INIT (1397125303, 252774767),
			   POLY_INIT (-355992859, 110344234),   
			   POLY_INIT (2109244203, 32364310),
			   POLY_INIT (-1715147199, 362207905),  
			   POLY_INIT (247175055, 317240733),
			   POLY_INIT (-1220928035, 459932888),  
			   POLY_INIT (541418515, 471100388),
			   POLY_INIT (508614740, 300791678),    
			   POLY_INIT (-1993367142, 378787906),
			   POLY_INIT (816720840, 521234695),    
			   POLY_INIT (-1479454202, 409929275),
			   POLY_INIT (1135427436, 202640268),   
			   POLY_INIT (-724416862, 191521968),
			   POLY_INIT (1834208496, 48813557),    
			   POLY_INIT (-97733314, 93764297),
			   POLY_INIT (-1468557489, 426510234),  
			   POLY_INIT (1057549953, 504522918),
			   POLY_INIT (-2037816109, 395368931),  
			   POLY_INIT (301341981, 284079839),
			   POLY_INIT (-175476617, 76921704),    
			   POLY_INIT (1660225977, 65786964),
			   POLY_INIT (-613121045, 174679313),   
			   POLY_INIT (1275853349, 219613741),
			   POLY_INIT (1130592161, 273117515),   
			   POLY_INIT (-736358801, 389619319),
			   POLY_INIT (1839039549, 515616562),   
			   POLY_INIT (-85787149, 432390158),
			   POLY_INIT (513708185, 230608313),    
			   POLY_INIT (-1981683369, 180396677),
			   POLY_INIT (811623173, 54662080),     
			   POLY_INIT (-1491133749, 71073020),
			   POLY_INIT (-180078406, 415678895),   
			   POLY_INIT (1648050548, 532197011),
			   POLY_INIT (-608515290, 372907990),   
			   POLY_INIT (1288024808, 289698026),
			   POLY_INIT (-1464213630, 88046941),   
			   POLY_INIT (1069983308, 37818977),
			   POLY_INIT (-2042156002, 197370660),  
			   POLY_INIT (288904656, 213765144),
			   POLY_INIT (791538071, 21237890),     
			   POLY_INIT (-1202548647, 104497086),
			   POLY_INIT (30611979, 263769851),     
			   POLY_INIT (-1767087163, 147235271),
			   POLY_INIT (1926237871, 482192496),   
			   POLY_INIT (-441485471, 465814348),
			   POLY_INIT (1546583347, 306278921),   
			   POLY_INIT (-883849987, 356457781),
			   POLY_INIT (-1727355252, 163946598),  
			   POLY_INIT (242605890, 247189338),
			   POLY_INIT (-1208724208, 121208351),  
			   POLY_INIT (545991902, 4657443),
			   POLY_INIT (-990428748, 339483796),   
			   POLY_INIT (1401436282, 323122088),
			   POLY_INIT (-368463320, 448840429),   
			   POLY_INIT (2104937446, 499035601),
			   POLY_INIT (-1776104794, 20151257),   
			   POLY_INIT (22917992, 105714917),
			   POLY_INIT (-1193526982, 265266592),  
			   POLY_INIT (799228148, 145869468),
			   POLY_INIT (-874566242, 483051307),   
			   POLY_INIT (1554011216, 464824343),
			   POLY_INIT (-450765310, 305535314),   
			   POLY_INIT (1918805964, 357070446),
			   POLY_INIT (537232829, 162712381),    
			   POLY_INIT (-1216676749, 248292353),
			   POLY_INIT (251360801, 122557764),    
			   POLY_INIT (-1719398417, 3177080),
			   POLY_INIT (2113430149, 340490191),   
			   POLY_INIT (-360244405, 322246899),
			   POLY_INIT (1392939289, 448244150),   
			   POLY_INIT (-998643497, 499762826),
			   POLY_INIT (-93563760, 271587856),    
			   POLY_INIT (1829973342, 391017772),
			   POLY_INIT (-728586484, 516736105),   
			   POLY_INIT (1139662530, 431139669),
			   POLY_INIT (-1483623512, 231319266),  
			   POLY_INIT (820955750, 179816926),
			   POLY_INIT (-1989197772, 53835931),   
			   POLY_INIT (504379898, 72030119),
			   POLY_INIT (1279990667, 414296820),   
			   POLY_INIT (-617323963, 533710280),
			   POLY_INIT (1656088599, 374174861),   
			   POLY_INIT (-171273767, 288562097),
			   POLY_INIT (297204915, 88610310),     
			   POLY_INIT (-2033613443, 37124410),
			   POLY_INIT (1061687087, 196397183),   
			   POLY_INIT (-1472760095, 214607683),
			   POLY_INIT (-465793852, 31305070),    
			   POLY_INIT (1933833482, 111395410),
			   POLY_INIT (-893223080, 253850391),   
			   POLY_INIT (1572669078, 140450859),
			   POLY_INIT (-1178506244, 472125852),  
			   POLY_INIT (784208434, 458915488),
			   POLY_INIT (-1757439904, 316198885),  
			   POLY_INIT (4252078, 363241689),
			   POLY_INIT (1377551327, 157031818),   
			   POLY_INIT (-983254511, 237138614),
			   POLY_INIT (2095394883, 127976435),   
			   POLY_INIT (-342210163, 14593231),
			   POLY_INIT (266740967, 346399096),    
			   POLY_INIT (-1734779607, 333172292),
			   POLY_INIT (555276155, 442072833),    
			   POLY_INIT (-1234719051, 489099325),
			   POLY_INIT (-2005789966, 283036839),  
			   POLY_INIT (520973116, 396403611),
			   POLY_INIT (-1500716690, 505549534),  
			   POLY_INIT (838047904, 425491938),
			   POLY_INIT (-711985718, 220688469),   
			   POLY_INIT (1123060740, 173612905),
			   POLY_INIT (-76478890, 64728620),     
			   POLY_INIT (1812889496, 77971728),
			   POLY_INIT (1045781993, 408910915),   
			   POLY_INIT (-1456856025, 522261375),
			   POLY_INIT (279686773, 379822650),    
			   POLY_INIT (-2016094277, 299748614),
			   POLY_INIT (1672002257, 94814385),    
			   POLY_INIT (-187186401, 47755149),
			   POLY_INIT (1297500493, 190455496),   
			   POLY_INIT (-634834813, 203715060),
			   POLY_INIT (830288323, 279554044),    
			   POLY_INIT (-1509799923, 400017600),
			   POLY_INIT (528728671, 508918149),    
			   POLY_INIT (-1996702831, 422254265),
			   POLY_INIT (1820382971, 223353614),   
			   POLY_INIT (-67129547, 170816562),
			   POLY_INIT (1115563367, 61654391),    
			   POLY_INIT (-721331031, 80915019),
			   POLY_INIT (-2024112424, 405280536),  
			   POLY_INIT (270862102, 525760548),
			   POLY_INIT (-1448833724, 383043937),  
			   POLY_INIT (1054602378, 296396381),
			   POLY_INIT (-626550304, 97627114),    
			   POLY_INIT (1306058798, 45073622),
			   POLY_INIT (-195466628, 187528595),   
			   POLY_INIT (1663439794, 206772911),
			   POLY_INIT (1563668469, 27969077),    
			   POLY_INIT (-900934085, 114600201),
			   POLY_INIT (1942838377, 257300556),   
			   POLY_INIT (-458087001, 136869744),
			   POLY_INIT (13519053, 475232967),     
			   POLY_INIT (-1749995261, 455939579),
			   POLY_INIT (774945617, 313500862),    
			   POLY_INIT (-1185955169, 366070658),
			   POLY_INIT (-350953234, 153843409),   
			   POLY_INIT (2087426336, 240458221),
			   POLY_INIT (-974515342, 131573928),   
			   POLY_INIT (1385523900, 11126676),
			   POLY_INIT (-1226242090, 349358627),  
			   POLY_INIT (563510808, 330081567),
			   POLY_INIT (-1743260598, 439227482),  
			   POLY_INIT (258510212, 491813734)
};

static const poly_t   
                poly88[256]
                        /* poly80[i] = i(x) * X^80 MOD P */
			= {POLY_INIT (0, 0),                    
			   POLY_INIT (964379295, 346020725),
			   POLY_INIT (2133460053, 441286634),   
			   POLY_INIT (1179731658, 248685727),
			   POLY_INIT (-209155647, 132658900),   
			   POLY_INIT (-889992354, 326626721),
			   POLY_INIT (-1935503980, 497371454),  
			   POLY_INIT (-1244016885, 154833483),
			   POLY_INIT (-418311294, 265317801),   
			   POLY_INIT (-563457763, 458208988),
			   POLY_INIT (-1740957737, 362615363),  
			   POLY_INIT (-1589619384, 16959798),
			   POLY_INIT (345610819, 137911165),    
			   POLY_INIT (769841372, 480739336),
			   POLY_INIT (1806933526, 309666967),   
			   POLY_INIT (1388895369, 116064226),
			   POLY_INIT (-836622588, 530635603),   
			   POLY_INIT (-145136229, 188678182),
			   POLY_INIT (-1324866735, 99460281),   
			   POLY_INIT (-2005704242, 292716492),
			   POLY_INIT (1034596037, 407432583),   
			   POLY_INIT (80866394, 215430898),
			   POLY_INIT (1115728528, 33919597),    
			   POLY_INIT (2080106511, 379210008),
			   POLY_INIT (691221638, 275822330),    
			   POLY_INIT (273184281, 82800015),
			   POLY_INIT (1444491475, 171821328),   
			   POLY_INIT (1868722764, 513938021),
			   POLY_INIT (-625230521, 395870254),   
			   POLY_INIT (-473890856, 50813787),
			   POLY_INIT (-1517176558, 232128452),  
			   POLY_INIT (-1662321779, 424289457),
			   POLY_INIT (-1852256413, 204701607),  
			   POLY_INIT (-1461481988, 413967570),
			   POLY_INIT (-290272458, 377356365),   
			   POLY_INIT (-674657879, 48356152),
			   POLY_INIT (1645233826, 198920563),   
			   POLY_INIT (1533740093, 524587526),
			   POLY_INIT (490357495, 295057049),    
			   POLY_INIT (608239720, 84536812),
			   POLY_INIT (1988746465, 65212942),    
			   POLY_INIT (1341300350, 394054011),
			   POLY_INIT (161732788, 430861796),    
			   POLY_INIT (819501611, 221361809),
			   POLY_INIT (-2063510240, 67839194),   
			   POLY_INIT (-1132849217, 278200239),
			   POLY_INIT (-97824395, 507927344),    
			   POLY_INIT (-1018162198, 182026309),
			   POLY_INIT (1606084711, 328443124),   
			   POLY_INIT (1723968248, 118259585),
			   POLY_INIT (546368562, 165600030),    
			   POLY_INIT (434876077, 490799211),
			   POLY_INIT (-1405984346, 343642656),  
			   POLY_INIT (-1790368967, 14960981),
			   POLY_INIT (-753375757, 238480842),   
			   POLY_INIT (-362600596, 447297215),
			   POLY_INIT (-1196688411, 474204509),  
			   POLY_INIT (-2117027462, 148640296),
			   POLY_INIT (-947781712, 101627575),   
			   POLY_INIT (-17122001, 311520706),
			   POLY_INIT (1260614180, 464256905),   
			   POLY_INIT (1918382267, 255075580),
			   POLY_INIT (873035377, 31883363),     
			   POLY_INIT (225588462, 360274710),
			   POLY_INIT (590454470, 409403215),    
			   POLY_INIT (441113689, 217654330),
			   POLY_INIT (1545312915, 36405413),    
			   POLY_INIT (1700845580, 380918736),
			   POLY_INIT (-793176313, 529451419),   
			   POLY_INIT (-373140072, 185668334),
			   POLY_INIT (-1349315758, 96712305),   
			   POLY_INIT (-1763159603, 291269892),
			   POLY_INIT (-1004499644, 397841126),  
			   POLY_INIT (-44314661, 53037459),
			   POLY_INIT (-1156937455, 234614028),  
			   POLY_INIT (-2106471538, 425997945),
			   POLY_INIT (933758085, 274637874),    
			   POLY_INIT (248727066, 79789895),
			   POLY_INIT (1216479440, 169073624),   
			   POLY_INIT (1912160847, 512491693),
			   POLY_INIT (-317474366, 130425884),   
			   POLY_INIT (-731317411, 324665193),
			   POLY_INIT (-1841709673, 495672310),  
			   POLY_INIT (-1421672696, 152338563),
			   POLY_INIT (513486851, 3019464),      
			   POLY_INIT (669020828, 347195837),
			   POLY_INIT (1639003222, 442723618),   
			   POLY_INIT (1489663689, 251442775),
			   POLY_INIT (167946816, 135678389),    
			   POLY_INIT (863627487, 478778048),
			   POLY_INIT (1965600277, 307967583),   
			   POLY_INIT (1280568458, 113569066),
			   POLY_INIT (-108387455, 268336993),   
			   POLY_INIT (-1057922786, 459383828),
			   POLY_INIT (-2036324396, 364052619),  
			   POLY_INIT (-1076140725, 19717118),
			   POLY_INIT (-1297526363, 341147880),  
			   POLY_INIT (-1949166790, 13261725),
			   POLY_INIT (-847030800, 236519170),   
			   POLY_INIT (-185067665, 445064311),
			   POLY_INIT (1092737124, 331200060),   
			   POLY_INIT (2019203835, 119696713),
			   POLY_INIT (1040964657, 166775254),   
			   POLY_INIT (124821166, 493818531),
			   POLY_INIT (1438138919, 461761857),   
			   POLY_INIT (1824719032, 253376052),
			   POLY_INIT (714229362, 29921963),     
			   POLY_INIT (334038253, 358042078),
			   POLY_INIT (-1506751514, 476961685),  
			   POLY_INIT (-1622439559, 150077664),
			   POLY_INIT (-652554317, 102802559),   
			   POLY_INIT (-530477780, 314539786),
			   POLY_INIT (2089514657, 200629179),   
			   POLY_INIT (1173369918, 527073486),
			   POLY_INIT (60912372, 297280593),     
			   POLY_INIT (987377771, 86507300),
			   POLY_INIT (-1895563424, 203255151),  
			   POLY_INIT (-1233601025, 411219482),
			   POLY_INIT (-265684171, 374346373),   
			   POLY_INIT (-917325398, 47172080),
			   POLY_INIT (-1684380381, 69547538),   
			   POLY_INIT (-1562302532, 280685927),
			   POLY_INIT (-458202762, 510151160),   
			   POLY_INIT (-573889559, 183997069),
			   POLY_INIT (1746070754, 63766726),    
			   POLY_INIT (1365880445, 391306163),
			   POLY_INIT (389605559, 427851564),    
			   POLY_INIT (776186408, 220177497),
			   POLY_INIT (1270856935, 62863262),    
			   POLY_INIT (1925512824, 388033771),
			   POLY_INIT (882227378, 435308660),    
			   POLY_INIT (233765421, 225284865),
			   POLY_INIT (-1204341466, 72810826),   
			   POLY_INIT (-2125695047, 281598527),
			   POLY_INIT (-954388109, 505052832),   
			   POLY_INIT (-26840084, 176530901),
			   POLY_INIT (-1397837979, 208624183),  
			   POLY_INIT (-1781142022, 418414914),
			   POLY_INIT (-746280144, 371336669),   
			   POLY_INIT (-352327249, 46005928),
			   POLY_INIT (1596335780, 193424611),   
			   POLY_INIT (1717396539, 521713558),
			   POLY_INIT (537666289, 298455817),    
			   POLY_INIT (427253870, 89507964),
			   POLY_INIT (-2053268509, 471854285),  
			   POLY_INIT (-1125721732, 142620600),
			   POLY_INIT (-88629322, 106074919),    
			   POLY_INIT (-1009984215, 315443282),
			   POLY_INIT (1981092386, 469228057),   
			   POLY_INIT (1332629693, 258474348),
			   POLY_INIT (155129463, 29009395),     
			   POLY_INIT (809784552, 354778758),
			   POLY_INIT (1653377121, 332366180),   
			   POLY_INIT (1542966014, 122706449),
			   POLY_INIT (497454132, 159579790),    
			   POLY_INIT (618516139, 488449531),
			   POLY_INIT (-1862008416, 338147248),  
			   POLY_INIT (-1468054721, 12086469),
			   POLY_INIT (-298973707, 241879130),   
			   POLY_INIT (-682277014, 452268847),
			   POLY_INIT (-634948732, 260851769),   
			   POLY_INIT (-480497381, 454267724),
			   POLY_INIT (-1525844015, 364984275),  
			   POLY_INIT (-1669974706, 22998182),
			   POLY_INIT (699398725, 140803821),    
			   POLY_INIT (282376410, 486253976),
			   POLY_INIT (1451621904, 304677127),   
			   POLY_INIT (1878965391, 112646770),
			   POLY_INIT (1026973702, 6038928),     
			   POLY_INIT (72163993, 348389093),
			   POLY_INIT (1109156947, 437344890),   
			   POLY_INIT (2070357708, 244220175),
			   POLY_INIT (-826349113, 129241924),   
			   POLY_INIT (-138040488, 321636401),
			   POLY_INIT (-1315639918, 502885550),  
			   POLY_INIT (-1997558003, 157726683),
			   POLY_INIT (335893632, 271356778),    
			   POLY_INIT (763237919, 78858271),
			   POLY_INIT (1798262997, 174189696),   
			   POLY_INIT (1381241418, 519976949),
			   POLY_INIT (-410133183, 398763454),   
			   POLY_INIT (-554262562, 56327883),
			   POLY_INIT (-1733830380, 227138132),  
			   POLY_INIT (-1579377781, 420872481),
			   POLY_INIT (-216774910, 536673987),   
			   POLY_INIT (-898693731, 191047094),
			   POLY_INIT (-1942076585, 95519017),   
			   POLY_INIT (-1253768760, 288250460),
			   POLY_INIT (10276547, 404015127),     
			   POLY_INIT (971476060, 210441058),
			   POLY_INIT (2142685846, 39434237),    
			   POLY_INIT (1187874825, 382102664),
			   POLY_INIT (1754145313, 467257553),   
			   POLY_INIT (1375035582, 256250788),
			   POLY_INIT (396633716, 26523451),     
			   POLY_INIT (786392299, 353070158),
			   POLY_INIT (-1694061600, 473038341),  
			   POLY_INIT (-1568806529, 145630576),
			   POLY_INIT (-466833483, 108823023),   
			   POLY_INIT (-581440214, 316889754),
			   POLY_INIT (-1885392477, 336176504),  
			   POLY_INIT (-1226542276, 9862669),
			   POLY_INIT (-256559626, 239393426),   
			   POLY_INIT (-909215895, 450560487),
			   POLY_INIT (2081929314, 333550508),   
			   POLY_INIT (1164770045, 125716697),
			   POLY_INIT (54377527, 162327622),     
			   POLY_INIT (977731240, 489895731),
			   POLY_INIT (-1498675931, 75043714),   
			   POLY_INIT (-1613281350, 283560183),
			   POLY_INIT (-645529232, 506752104),   
			   POLY_INIT (-520272913, 179025693),
			   POLY_INIT (1428458724, 59843926),    
			   POLY_INIT (1818218107, 386858531),
			   POLY_INIT (705595569, 433871548),    
			   POLY_INIT (326486574, 222527945),
			   POLY_INIT (1102911143, 195657259),   
			   POLY_INIT (2026263608, 523674974),
			   POLY_INIT (1050088178, 300155329),   
			   POLY_INIT (132927597, 92002996),
			   POLY_INIT (-1305108634, 205605119),  
			   POLY_INIT (-1957765639, 417239946),
			   POLY_INIT (-853566669, 369899285),   
			   POLY_INIT (-194717268, 43248736),
			   POLY_INIT (-115937982, 401258358),   
			   POLY_INIT (-1066553379, 58027011),
			   POLY_INIT (-2042828521, 229099676),  
			   POLY_INIT (-1085822072, 423105513),
			   POLY_INIT (178152579, 268599714),    
			   POLY_INIT (870655516, 77421271),
			   POLY_INIT (1974755542, 173014600),   
			   POLY_INIT (1288643145, 516957501),
			   POLY_INIT (503840448, 406510303),    
			   POLY_INIT (662486111, 212140458),
			   POLY_INIT (1630403221, 41395509),    
			   POLY_INIT (1482078218, 384335424),
			   POLY_INIT (-309364991, 533916683),   
			   POLY_INIT (-722192994, 189609854),
			   POLY_INIT (-1834650796, 94344161),   
			   POLY_INIT (-1411501621, 285231252),
			   POLY_INIT (926206534, 139095077),    
			   POLY_INIT (240093401, 483768144),
			   POLY_INIT (1209978387, 302453711),   
			   POLY_INIT (1902480524, 110676154),
			   POLY_INIT (-994294905, 262298353),   
			   POLY_INIT (-37289704, 457015684),
			   POLY_INIT (-1147779118, 367994139),  
			   POLY_INIT (-2098395827, 24182382),
			   POLY_INIT (-802825788, 127533452),   
			   POLY_INIT (-379675813, 319150841),
			   POLY_INIT (-1357914735, 500661862),  
			   POLY_INIT (-1770742002, 155755795),
			   POLY_INIT (598560773, 7485272),      
			   POLY_INIT (450237082, 351136813),
			   POLY_INIT (1552372816, 440354994),   
			   POLY_INIT (1711019727, 245404615)
			};

#ifndef FINGERPRINT_LITTLE_ENDIAN
static void poly_find_byte_order (void)
{
  int_32_t    i = 0x12345678;
  int_bytes_t x = { i };
  word_t      a0 = word_extract (i, 0, 8);
  word_t      a1 = word_extract (i, 8, 8);
  word_t      a2 = word_extract (i, 16, 8);
  word_t      a3 = word_extract (i, 24, 8);

  if (a0 == x.b[0] && a1 == x.b[1] && a2 == x.b[2] && a3 == x.b[3]) {
    poly_little_endian = 1;
  } else if (a0 == x.b[3] && a1 == x.b[2] && a2 == x.b[1] && a3 == x.b[0]) {
    poly_big_endian = 1;
  } else {
    /* Unsupported byte ordering ...  */
    assert (0);
  }

  poly_init_done = 1;
}
#endif /* FINGERPRINT_LITTLE_ENDIAN */

/* Return the sign-extended bottom 32 bits of X.  */

static int_32_t poly_fix_32 (word_t x)
{
  if (sizeof (word_t) == sizeof (int_32_t))
    /* Sign-extension is trivial; the types are the same size.
       Hopefully, this branch will reduce the function to the
       identity, and compilers will be clever enough to inline it.  */
    return x;
  else 
    {
      const integer_t sign = 0x80000000;
      const integer_t sign_extend = word_left_shift (word_not (0), 31);
      
      if (word_and (x, sign) == 0)
	return word_and (x, POLY_SIG_BITS);
      else
	return word_or (sign_extend, word_and (x, POLY_SIG_BITS));
    }
}

#if MAY_BE_LITTLE_ENDIAN
static poly_t poly_extend_words_le (const poly_t  p,
				    const byte_t* source,
				    int           len)
{
  int_ptr_t   ip = (int_ptr_t) source;
  int_bytes_t tmp;
  /* Curiously, the Modula-3 sources use INTEGER for the type of the
     next two variables, rather than int_32_t.  */
  integer_t   p0 = POLY_HALF (p, 0);
  integer_t   p1 = POLY_HALF (p, 1);
  poly_t      result;

  while (len > 0) {
    /* Split the low-order bytes.  */
    tmp.w = p0;

    /* Compute the new result.  */
    p0 = word_xor (p1, 
		   word_xor (word_xor (POLY_HALF (poly88[tmp.b[0]], 0),
				       POLY_HALF (poly80[tmp.b[1]], 0)),
			     word_xor (POLY_HALF (poly72[tmp.b[2]], 0),
				       POLY_HALF (poly64[tmp.b[3]], 0))));
    p1 = word_xor (*ip, 
		   word_xor (word_xor (POLY_HALF (poly88[tmp.b[0]], 1),
				       POLY_HALF (poly80[tmp.b[1]], 1)),
			     word_xor (POLY_HALF (poly72[tmp.b[2]], 1),
				       POLY_HALF (poly64[tmp.b[3]], 1))));
    len -= sizeof (int_32_t);
    ++ip; /* The Modula-3 source is INC (ip, ADRSIZE (ip^)), but C's
	     pointer arithmetic behaves differently.  */
  }
  POLY_FORM (result, p0, p1);
  return result;
}
#endif /* MAY_BE_LITTLE_ENDIAN */

#if MAY_BE_BIG_ENDIAN 
static poly_t poly_extend_words_be (const poly_t  p,
				    const byte_t* source,
				    int           len)
{
  int_ptr_t   ip = (int_ptr_t) source;
  int_bytes_t tmp;
  int_32_t    p0 = POLY_HALF (p, 0);
  int_32_t    p1 = POLY_HALF (p, 1);
  int_bytes_t x;
  int_bytes_t y;
  poly_t      result;

  while (len > 0) {
    /* Byte swap the input word -- inline.  */
    y.w = *ip;
    x.b[0] = y.b[3];
    x.b[1] = y.b[2];
    x.b[2] = y.b[1];
    x.b[3] = y.b[0];

    /* Split the low-order bytes.  */
    tmp.w = p0;

    /* Compute the new result.  */
    p0 = word_xor (p1, 
		   word_xor (word_xor (POLY_HALF (poly88[tmp.b[3]], 0),
				       POLY_HALF (poly80[tmp.b[2]], 0)),
			     word_xor (POLY_HALF (poly72[tmp.b[1]], 0),
				       POLY_HALF (poly64[tmp.b[0]], 0))));
    p1 = word_xor (x.w, 
		   word_xor (word_xor (POLY_HALF (poly88[tmp.b[3]], 1),
				       POLY_HALF (poly80[tmp.b[2]], 1)),
			     word_xor (POLY_HALF (poly72[tmp.b[1]], 1),
				       POLY_HALF (poly64[tmp.b[0]], 1))));

    len -= sizeof (int_32_t);
    ++ip; /* The Modula-3 source is INC (ip, ADRSIZE (ip^)), but C's
	     pointer arithmetic behaves differently.  */
  }
  POLY_FORM (result, p0, p1);
  return result;
}
#endif /* MAY_BE_BIG_ENDIAN */

static poly_t poly_extend_bytes (const poly_t t, 
				 const byte_t* addr, 
				 int len)
{
  const byte_t* cp = addr;
  integer_t     n_bits = 8 * len;
  integer_t     x_bits = 32 - n_bits;
  integer_t     t0 = word_and (POLY_HALF (t, 0), POLY_SIG_BITS);
  integer_t     t0_x = word_left_shift (t0, x_bits);
  integer_t     t0_n = word_right_shift (t0, n_bits);
  integer_t     t1 = word_and (POLY_HALF (t, 1), POLY_SIG_BITS);
  integer_t     t1_x = word_left_shift (t1, x_bits);
  integer_t     t1_n = word_right_shift (t1, n_bits);
  char          tmp[4];
  poly_t        result;

  POLY_HALF (result, 0) = poly_fix_32 (t0_x);
  POLY_HALF (result, 1) = poly_fix_32 (word_xor (t0_n, t1_x));

  switch (len) {
  case 1:
    tmp[0] = word_extract (t1_n, 0, 8);
    tmp[1] = word_extract (t1_n, 8, 8);
    tmp[2] = word_extract (t1_n, 16, 8);
    tmp[3] = cp[0];
    break;

  case 2:
    tmp[0] = word_extract (t1_n, 0, 8);
    tmp[1] = word_extract (t1_n, 8, 8);
    tmp[2] = cp[0];
    tmp[3] = cp[1];
    break;

  case 3:
    tmp[0] = word_extract (t1_n, 0, 8);
    tmp[1] = cp[0];
    tmp[2] = cp[1];
    tmp[3] = cp[2];
    break;

  default:
    assert (0);
  }

  if (poly_little_endian) {
#if MAY_BE_LITTLE_ENDIAN 
    return poly_extend_words_le (result, tmp, 4);
#else /* MAY_BE_LITTLE_ENDIAN */
    ;
#endif /* MAY_BE_LITTLE_ENDIAN */
  } else {
#if MAY_BE_BIG_ENDIAN 
    return poly_extend_words_be (result, tmp, 4);
#else /* MAY_BE_BIG_ENDIAN */
    ;
#endif /* MAY_BE_BIG_ENDIAN */
  }
}
			    
/* This procedure assumes that the LEN bytes beginning at address ADDR
   define a polynomial, A(x) of degree 8 * LEN.  The procedure returns
   (INIT * x ^ (8 * LEN) + A(x)) % PolyBasis.P.  */

static poly_t poly_compute_mod (poly_t        init,
				const byte_t* addr,
				integer_t     len)
{
  integer_t j;
  integer_t k;
  poly_t    result = init;

#ifndef FINGERPRINT_LITTLE_ENDIAN
  /* We don't need to do this if we already know the endianness.  */
  if (!poly_init_done) 
    poly_find_byte_order ();
#endif /* FINGERPRINT_LITTLE_ENDIAN */

  /* Word align the source pointer.  */
  j = mod ((word_t) addr, 4);
  if (len >= 4 && j != 0) {
    j = 4 - j;
    result = poly_extend_bytes (result, addr, j);
    addr += j;
    len -= j;
  }

  /* Compute the bulk of the result a word at a time.  */
  if (len >= 4) {
    j = mod ((word_t) len, 4);
    k = len - j;
    if (poly_little_endian) {
#if MAY_BE_LITTLE_ENDIAN 
      result = poly_extend_words_le (result, addr, k);
#else /* MAY_BE_LITTLE_ENDIAN */
      ;
#endif /* MAY_BE_LITTLE_ENDIAN */
    } else {
#if MAY_BE_BIG_ENDIAN 
      result = poly_extend_words_be (result, addr, k);
#else /* MAY_BE_BIG_ENDIAN */
      ;
#endif /* MAY_BE_BIG_ENDIAN */
    }
    addr += k;
    len = j;
  }

  /* Finish up the last few bytes.  */
  if (len > 0)
    result = poly_extend_bytes (result, addr, len);

  return result;
}

#if !FINGERPRINT_USE_INTEGRAL_TYPE
static void poly_to_bytes (poly_t t, byte_t* b)
{
  /* Generate the bytes in little-endian order.  */
  b[0] = word_extract (POLY_HALF (t, 0), 0, 8);
  b[1] = word_extract (POLY_HALF (t, 0), 8, 8);
  b[2] = word_extract (POLY_HALF (t, 0), 16, 8);
  b[3] = word_extract (POLY_HALF (t, 0), 24, 8);
  b[4] = word_extract (POLY_HALF (t, 1), 0, 8);
  b[5] = word_extract (POLY_HALF (t, 1), 8, 8);
  b[6] = word_extract (POLY_HALF (t, 1), 16, 8);
  b[7] = word_extract (POLY_HALF (t, 1), 24, 8);
}

static void poly_from_bytes (byte_t* b, poly_t* t)
{
  /* Assume the bytes are in little-endian order.  */
  POLY_HALF (*t, 0) = 
    poly_fix_32 (word_or (word_or (                 b[0],
				   word_left_shift (b[1], 8)),
			  word_or (word_left_shift (b[2], 16),
				   word_left_shift (b[3], 24))));
  POLY_HALF (*t, 1) = 
    poly_fix_32 (word_or (word_or (                 b[4],
				   word_left_shift (b[5], 8)),
			  word_or (word_left_shift (b[6], 16),
				   word_left_shift (b[7], 24))));
}
#else /* FINGERPRINT_USE_INTEGRAL_TYPE */
#define poly_to_bytes(t, b) (*((fingerprint_t*) (b)) = t)
#define poly_from_bytes(b, t) (*(t) = (*((poly_t*) b)))
#endif /* !FINGERPRINT_USE_INTEGRAL_TYPE */

/***********************************************************************
  Modula-3 `Fingerprint' Module
***********************************************************************/

/***********************************************************************
  Macros
***********************************************************************/

#define FINGERPRINT_A 0xff208489
#define FINGERPRINT_B 0xf4872e10
#define FINGERPRINT_C 0x402d619b
#define FINGERPRINT_D 0x0bf359a7

/***********************************************************************
  Variables
***********************************************************************/

#if !FINGERPRINT_USE_INTEGRAL_TYPE
const fingerprint_t 
                fingerprint_zero;
#endif /* FINGERPRINT_USE_INTEGRAL_TYPE */

/* const */ fingerprint_t 
                fingerprint_of_empty;
                       
static const byte_t fingerprint_perm[256] 
                        = { 55, 254, 252, 251, 250, 248, 240, 245, 
			    246, 238, 237, 244, 7, 189, 214, 236, 
			    235, 20, 33, 8, 227, 14, 233, 178, 
			    172, 60, 229, 133, 152, 19, 210, 203, 
			    221, 208, 76, 18, 13, 199, 113, 62, 
			    40, 190, 213, 194, 43, 181, 21, 15, 
			    201, 162, 90, 186, 71, 117, 107, 70, 
			    191, 5, 173, 44, 39, 12, 174, 183, 
			    99, 11, 176, 163, 161, 72, 86, 105, 
			    2, 83, 42, 52, 179, 135, 103, 110, 
			    151, 58, 108, 96, 166, 25, 115, 66, 
			    142, 10, 141, 48, 104, 34, 159, 120, 
			    22, 140, 64, 82, 78, 68, 207, 125, 
			    123, 150, 144, 138, 128, 139, 136, 114, 
			    119, 53, 148, 185, 41, 124, 216, 143,
			    49, 92, 98, 51, 112, 73, 50, 63, 
			    16, 46, 158, 126, 206, 122, 94, 132, 
			    88, 184, 28, 84, 127, 156, 167, 223, 
			    118, 89, 116, 17, 111, 121, 109, 77, 
			    146, 61, 224, 101, 81, 218, 97, 188, 
			    243, 155, 57, 102, 54, 129, 93, 192, 
			    153, 106, 36, 145, 79, 31, 137, 26, 
			    67, 85, 175, 80, 168, 65, 91, 1, 
			    147, 149, 6, 29, 37, 69, 182, 165, 
			    4, 74, 55, 47, 171, 169, 75, 134, 
			    193, 195, 198, 131, 38, 180, 56, 196, 
			    23, 154, 177, 200, 205, 27, 209, 95, 
			    204, 160, 3, 30, 157, 32, 9, 212, 
			    211, 45, 202, 170, 0, 219, 187, 87, 
			    35, 100, 217, 232, 164, 228, 220, 197, 
			    231, 215, 226, 130, 225, 234, 241, 239, 
			    59, 230, 247, 24, 249, 242, 222, 253
			};

/***********************************************************************
  Function Definitions
***********************************************************************/

void fingerprint_init (void)
{
  /* Make sure that the configuration was correct.  */
#if UCHAR_MAX != 255
#error "The fingerprint module requires 8-bit characters."
#endif /* UCHAR_MAX != 255 */
  assert (sizeof (int_32_t) == 4);
  assert (sizeof (poly_t) == 8);
  assert (sizeof (fingerprint_t) == 8);
  assert (sizeof (void*) == sizeof (integer_t));

  /* Intialize.  */
  poly_to_bytes (POLY_ONE, FINGERPRINT_BYTE (fingerprint_of_empty));
}

fingerprint_t fingerprint_from_text (const char* text)
{
  fingerprint_t result;
  poly_t        poly;

  poly = poly_compute_mod (POLY_ONE, 
			   (const byte_t*) text, 
			   (integer_t) strlen (text));
  poly_to_bytes (poly, FINGERPRINT_BYTE (result));

  return result;
} 

fingerprint_t fingerprint_combine (fingerprint_t fp1,
				   fingerprint_t fp2)
{
  poly_t        poly1;
  poly_t        poly2;
  fingerprint_t buf[2];
  fingerprint_t res;
  int           i;

  buf[0] = fp1;
  buf[1] = fp2;

  poly1 = poly_compute_mod (POLY_ONE, 
			    (const byte_t*) &buf[0], 
			    sizeof (buf));

  POLY_HALF (poly2, 0) = 
    poly_fix_32 (word_plus (word_times (POLY_HALF (poly1, 0), 
					FINGERPRINT_A),
			    word_times (POLY_HALF (poly1, 1), 
					FINGERPRINT_B)));
  POLY_HALF (poly2, 1) = 
    poly_fix_32 (word_plus (word_times (POLY_HALF (poly1, 0), 
					FINGERPRINT_C),
			    word_times (POLY_HALF (poly1, 1), 
					FINGERPRINT_D)));
  poly_to_bytes (poly2, FINGERPRINT_BYTE (res));

  for (i = 0; i < 8; ++i) 
    FINGERPRINT_BYTE (res)[i] = 
      fingerprint_perm [FINGERPRINT_BYTE (res)[i]]; 

  return res;
}

fingerprint_t fingerprint_from_chars (const char*   text,
				      fingerprint_t fp)
{
  integer_t     n = (integer_t) strlen (text);
  fingerprint_t result;
  poly_t        init;
  poly_t        poly;

  if (n == 0) 
    return fp;

  poly_from_bytes (FINGERPRINT_BYTE (fp), &init);
  poly = poly_compute_mod (init, (const byte_t*) text, n);
  poly_to_bytes (poly, FINGERPRINT_BYTE (result));
  
  return result;
}

#if !FINGERPRINT_USE_INTEGRAL_TYPE
int fingerprint_equal (fingerprint_t fp1,
		       fingerprint_t fp2)
{
  return memcmp (&fp1, &fp2, sizeof (fingerprint_t)) == 0;
}
#endif /* !FINGERPRINT_USE_INTEGRAL_TYPE */

int fingerprint_equal_f (fingerprint_t fp1,
			 fingerprint_t fp2)
{
  return fingerprint_equal (fp1, fp2);
}

word_t fingerprint_hash (fingerprint_t fp)
{
  poly_t x;
  poly_from_bytes (FINGERPRINT_BYTE (fp), &x);
  return word_xor (POLY_HALF (x, 0), POLY_HALF (x, 1));
}

/***********************************************************************
  Unit Test
***********************************************************************/

#ifdef FINGERPRINT_TEST
#include <stdio.h>

static void fingerprint_print (fingerprint_t fp, byte_t* buffer)
{
  int i;

  buffer += sprintf (buffer, "{");
  for (i = 0; i < 8; ++i) {
    buffer += 
      sprintf (buffer, "%s%x", i != 0 ? ", " : "", 
	       (unsigned int) (FINGERPRINT_BYTE (fp))[i]);
  }
  buffer += sprintf (buffer, "}");
}

static fingerprint_t fingerprint_print_with_text (const char* text)
{
  char buffer[64];
  fingerprint_t fp;
  
  fp = fingerprint_from_text (text);
  fingerprint_print (fp, buffer);
  printf ("The fingerprint of:\n  %s\nis:\n  %s\n",
	  text, buffer);
  return fp;
}

static int fingerprint_compare (fingerprint_t fp, 
				unsigned      bytes[])
{
  int i;
  for (i = 0; i < 8; ++i) {
    if (FINGERPRINT_BYTE (fp)[i] != bytes[i]) 
      return 0;
  }

  return 1;
}

int main()
{
  char          buffer[64];
  fingerprint_t fp1;
  fingerprint_t fp2;
  fingerprint_t fp3;
  fingerprint_t fp4;

  unsigned      fp_of_good_men [] = { 0x79, 0x62, 0xbf, 0x45, 0xa3,
				      0x53, 0xb2, 0x2b };
  unsigned      fp_of_quick_fox [] = { 0x53, 0x3e, 0x7b, 0x88, 0x6,
				       0x19, 0xba, 0x38 };
  unsigned      fp_of_combine [] = { 0xd4, 0x18, 0x54, 0x6, 0xa7,
				     0x68, 0x8c, 0x35 };

#define XSTR(X) #X
#define STR(X) XSTR(X)

  printf ("Configuration\n"
	  "-------------\n"
	  "FINGERPRINT_INTEGRAL_TYPE:    %s\n"
	  "FINGERPRINT_INT_32_TYPE:      %s\n"
	  "FINGERPRINT_POINTER_INT_TYPE: %s\n"
	  "FINGERPRINT_LITTLE_ENDIAN:    %s\n\n"
	  "Tests\n"
	  "-----\n",
#ifdef FINGERPRINT_INTEGRAL_TYPE
	  STR(FINGERPRINT_INTEGRAL_TYPE),
#else /* ifndef FINGERPRINT_INTEGRAL_TYPE */
	  "undefined",
#endif /* ifdef FINGERPRINT_INTEGRAL_TYPE */
	  STR(FINGERPRINT_INT_32_TYPE),
	  STR(FINGERPRINT_POINTER_INT_TYPE),
#ifdef FINGERPRINT_LITTLE_ENDIAN
	  STR(FINGERPRINT_LITTLE_ENDIAN)
#else /* ifndef FINGERPRINT_LITTLE_ENDIAN */
	  "undefined"
#endif /* ifdef FINGERPRINT_INTEGRAL_TYPE */
	  );

  fingerprint_init ();

  fp1 = fingerprint_print_with_text ("");
  fp2 = fingerprint_print_with_text ("Now is the time for all good men "
				     "to come to the aid of their country.");
  fp3 = fingerprint_print_with_text ("The quick brown fox jumped over the "
				     "lazy dog.");

  fp4 = fingerprint_combine (fp2, fp3);
  fingerprint_print (fp4, buffer);
  printf ("The fingerprint of (\"Now...\", \"The quick...\") is:\n  %s\n",
	  buffer);
  fflush (stdin);

  assert (fingerprint_equal (fp1, fingerprint_of_empty));
  assert (fingerprint_compare (fp2, fp_of_good_men));
  assert (fingerprint_compare (fp3, fp_of_quick_fox));

  assert (fingerprint_compare (fp4, fp_of_combine));

  return 0;
}
#endif /* ifdef FINGERPRINT TEST */

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]