1 #include <sys/types.h>
2 #include "rabin-checksum.h"
3
4 #ifdef WIN32
5 #include <stdint.h>
6 #ifndef u_int
7 typedef unsigned int u_int;
8 #endif
9
10 #ifndef u_char
11 typedef unsigned char u_char;
12 #endif
13
14 #ifndef u_short
15 typedef unsigned short u_short;
16 #endif
17
18 #ifndef u_long
19 typedef unsigned long u_long;
20 #endif
21
22 #ifndef u_int16_t
23 typedef uint16_t u_int16_t;
24 #endif
25
26 #ifndef u_int32_t
27 typedef uint32_t u_int32_t;
28 #endif
29
30 #ifndef u_int64_t
31 typedef uint64_t u_int64_t;
32 #endif
33 #endif
34
35 #define INT64(n) n##LL
36 #define MSB64 INT64(0x8000000000000000)
37
38 static u_int64_t poly = 0xbfe6b8a5bf378d83LL;
39 static u_int64_t T[256];
40 static u_int64_t U[256];
41 static int shift;
42
43 /* Highest bit set in a byte */
44 static const char bytemsb[0x100] = {
45 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5,
46 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
47 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7,
48 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
49 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
50 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
51 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
52 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
53 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
54 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
55 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
56 };
57
58 /* Find last set (most significant bit) */
fls32(u_int32_t v)59 static inline u_int fls32 (u_int32_t v)
60 {
61 if (v & 0xffff0000) {
62 if (v & 0xff000000)
63 return 24 + bytemsb[v>>24];
64 else
65 return 16 + bytemsb[v>>16];
66 }
67 if (v & 0x0000ff00)
68 return 8 + bytemsb[v>>8];
69 else
70 return bytemsb[v];
71 }
72
fls64(u_int64_t v)73 static inline char fls64 (u_int64_t v)
74 {
75 u_int32_t h;
76 if ((h = v >> 32))
77 return 32 + fls32 (h);
78 else
79 return fls32 ((u_int32_t) v);
80 }
81
polymod(u_int64_t nh,u_int64_t nl,u_int64_t d)82 u_int64_t polymod (u_int64_t nh, u_int64_t nl, u_int64_t d)
83 {
84 int i = 0;
85 int k = fls64 (d) - 1;
86
87 d <<= 63 - k;
88
89 if (nh) {
90 if (nh & MSB64)
91 nh ^= d;
92 for (i = 62; i >= 0; i--)
93 if (nh & ((u_int64_t) 1) << i) {
94 nh ^= d >> (63 - i);
95 nl ^= d << (i + 1);
96 }
97 }
98 for (i = 63; i >= k; i--)
99 {
100 if (nl & INT64 (1) << i)
101 nl ^= d >> (63 - i);
102 }
103
104 return nl;
105 }
106
polymult(u_int64_t * php,u_int64_t * plp,u_int64_t x,u_int64_t y)107 void polymult (u_int64_t *php, u_int64_t *plp, u_int64_t x, u_int64_t y)
108 {
109 int i;
110 u_int64_t ph = 0, pl = 0;
111 if (x & 1)
112 pl = y;
113 for (i = 1; i < 64; i++)
114 if (x & (INT64 (1) << i)) {
115 ph ^= y >> (64 - i);
116 pl ^= y << i;
117 }
118 if (php)
119 *php = ph;
120 if (plp)
121 *plp = pl;
122 }
123
polymmult(u_int64_t x,u_int64_t y,u_int64_t d)124 u_int64_t polymmult (u_int64_t x, u_int64_t y, u_int64_t d)
125 {
126 u_int64_t h, l;
127 polymult (&h, &l, x, y);
128 return polymod (h, l, d);
129 }
130
append8(u_int64_t p,u_char m)131 static u_int64_t append8 (u_int64_t p, u_char m)
132 {
133 return ((p << 8) | m) ^ T[p >> shift];
134 }
135
calcT(u_int64_t poly)136 static void calcT (u_int64_t poly)
137 {
138 int j = 0;
139 int xshift = fls64 (poly) - 1;
140 shift = xshift - 8;
141 u_int64_t T1 = polymod (0, INT64 (1) << xshift, poly);
142 for (j = 0; j < 256; j++) {
143 T[j] = polymmult (j, T1, poly) | ((u_int64_t) j << xshift);
144 }
145 }
146
calcU(int size)147 static void calcU(int size)
148 {
149 int i;
150 u_int64_t sizeshift = 1;
151 for (i = 1; i < size; i++)
152 sizeshift = append8 (sizeshift, 0);
153 for (i = 0; i < 256; i++)
154 U[i] = polymmult (i, sizeshift, poly);
155 }
156
rabin_init(int len)157 void rabin_init(int len)
158 {
159 calcT(poly);
160 calcU(len);
161 }
162
163 /*
164 * a simple 32 bit checksum that can be upadted from end
165 */
rabin_checksum(char * buf,int len)166 unsigned int rabin_checksum(char *buf, int len)
167 {
168 int i;
169 unsigned int sum = 0;
170 for (i = 0; i < len; ++i) {
171 sum = rabin_rolling_checksum (sum, len, 0, buf[i]);
172 }
173 return sum;
174 }
175
rabin_rolling_checksum(unsigned int csum,int len,char c1,char c2)176 unsigned int rabin_rolling_checksum(unsigned int csum, int len,
177 char c1, char c2)
178 {
179 return append8(csum ^ U[(unsigned char)c1], c2);
180 }
181