rabinpoly.c

   1 /*
   2  *
   3  * Copyright (C) 1999 David Mazieres (dm@uun.org)
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation; either version 2, or (at
   8  * your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  18  * USA
  19  *
  20  */
  21
  22   /* Faster generic_fls */
  23   /* (c) 2002, D.Phillips and Sistina Software */
  24
  25 #include "rabinpoly.h"
  26 #define MSB64 0x8000000000000000ULL
  27
  28 static inline unsigned fls8(unsigned n)
  29 {
  30        return n & 0xf0?
  31            n & 0xc0? (n >> 7) + 7: (n >> 5) + 5:
  32            n & 0x0c? (n >> 3) + 3: n - ((n + 1) >> 2);
  33 }
  34
  35 static inline unsigned fls16(unsigned n)
  36 {
  37        return n & 0xff00? fls8(n >> 8) + 8: fls8(n);
  38 }
  39
  40 static inline unsigned fls32(unsigned n)
  41 {
  42        return n & 0xffff0000? fls16(n >> 16) + 16: fls16(n);
  43 }
  44
  45 static inline unsigned fls64(unsigned long long n) /* should be u64 */
  46 {
  47        return n & 0xffffffff00000000ULL? fls32(n >> 32) + 32: fls32(n);
  48 }
  49
  50
  51 static u_int64_t polymod (u_int64_t nh, u_int64_t nl, u_int64_t d);
  52 static void      polymult (u_int64_t *php, u_int64_t *plp,
  53                            u_int64_t x, u_int64_t y);
  54 static u_int64_t polymmult (u_int64_t x, u_int64_t y, u_int64_t d);
  55
  56 static u_int64_t poly = 0xb15e234bd3792f63ull;  // Actual polynomial
  57 static u_int64_t T[256];                        // Lookup table for mod
  58 static int shift;
  59
  60 u_int64_t append8 (u_int64_t p, u_char m)
  61 { return ((p << 8) | m) ^ T[p >> shift];
  62 }
  63
  64 static u_int64_t
  65 polymod (u_int64_t nh, u_int64_t nl, u_int64_t d)
  66 { int i, k;
  67   assert (d);
  68   k = fls64 (d) - 1;
  69   d <<= 63 - k;
  70
  71   if (nh) {
  72     if (nh & MSB64)
  73       nh ^= d;
  74     for (i = 62; i >= 0; i--)
  75       if (nh & 1ULL << i) {
  76         nh ^= d >> (63 - i);
  77         nl ^= d << (i + 1);
  78       }
  79   }
  80   for (i = 63; i >= k; i--)
  81     if (nl & 1ULL << i)
  82       nl ^= d >> (63 - i);
  83   return nl;
  84 }
  85
  86 static void
  87 polymult (u_int64_t *php, u_int64_t *plp, u_int64_t x, u_int64_t y)
  88 { int i;
  89   u_int64_t ph = 0, pl = 0;
  90   if (x & 1)
  91     pl = y;
  92   for (i = 1; i < 64; i++)
  93     if (x & (1ULL << i)) {
  94       ph ^= y >> (64 - i);
  95       pl ^= y << i;
  96     }
  97   if (php)
  98     *php = ph;
  99   if (plp)
 100     *plp = pl;
 101 }
 102
 103 static u_int64_t
 104 polymmult (u_int64_t x, u_int64_t y, u_int64_t d)
 105 {
 106   u_int64_t h, l;
 107   polymult (&h, &l, x, y);
 108   return polymod (h, l, d);
 109 }
 110
 111 static int size = RABIN_WINDOW_SIZE;
 112 static u_int64_t fingerprint = 0;
 113 static int bufpos = -1;
 114 static u_int64_t U[256];
 115 static u_char buf[RABIN_WINDOW_SIZE];
 116
 117 void rabin_init ()
 118 { u_int64_t sizeshift = 1;
 119  u_int64_t T1;
 120   int xshift;
 121   int i, j;
 122   assert (poly >= 0x100);
 123   xshift = fls64 (poly) - 1;
 124   shift = xshift - 8;
 125   T1 = polymod (0, 1ULL << xshift, poly);
 126   for (j = 0; j < 256; j++)
 127     T[j] = polymmult (j, T1, poly) | ((u_int64_t) j << xshift);
 128
 129   for (i = 1; i < size; i++)
 130     sizeshift = append8 (sizeshift, 0);
 131   for (i = 0; i < 256; i++)
 132     U[i] = polymmult (i, sizeshift, poly);
 133   bzero (buf, sizeof (buf));
 134 }
 135
 136 void
 137 rabin_reset ()
 138 { rabin_init();
 139   fingerprint = 0;
 140   bzero (buf, sizeof (buf));
 141 }
 142
 143 u_int64_t
 144 rabin_slide8 (u_char m)
 145 { u_char om;
 146   if (++bufpos >= size) bufpos = 0;
 147
 148   om = buf[bufpos];
 149   buf[bufpos] = m;
 150   fingerprint = append8 (fingerprint ^ U[om], m);
 151
 152   return fingerprint;
 153 }
 154