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 */
22 /* Faster generic_fls */
23 /* (c) 2002, D.Phillips and Sistina Software */
25 #include "rabinpoly.h"
26 #define MSB64 0x8000000000000000ULL
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 }
35 static inline unsigned fls16(unsigned n)
36 {
37 return n & 0xff00? fls8(n >> 8) + 8: fls8(n);
38 }
40 static inline unsigned fls32(unsigned n)
41 {
42 return n & 0xffff0000? fls16(n >> 16) + 16: fls16(n);
43 }
45 static inline unsigned fls64(unsigned long long n) /* should be u64 */
46 {
47 return n & 0xffffffff00000000ULL? fls32(n >> 32) + 32: fls32(n);
48 }
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);
56 static u_int64_t poly = 0xb15e234bd3792f63ull; // Actual polynomial
57 static u_int64_t T[256]; // Lookup table for mod
58 static int shift;
60 u_int64_t append8 (u_int64_t p, u_char m)
61 { return ((p << 8) | m) ^ T[p >> shift];
62 }
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;
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 }
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 }
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 }
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];
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);
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 }
136 void
137 rabin_reset ()
138 { rabin_init();
139 fingerprint = 0;
140 bzero (buf, sizeof (buf));
141 }
143 u_int64_t
144 rabin_slide8 (u_char m)
145 { u_char om;
146 if (++bufpos >= size) bufpos = 0;
148 om = buf[bufpos];
149 buf[bufpos] = m;
150 fingerprint = append8 (fingerprint ^ U[om], m);
152 return fingerprint;
153 }