1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1996-2010 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Common Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.opensource.org/licenses/cpl1.0.txt *
11 * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
12 * *
13 * Information and Software Systems Research *
14 * AT&T Research *
15 * Florham Park NJ *
16 * *
17 * Glenn Fowler <gsf@research.att.com> *
18 * *
19 ***********************************************************************/
20 #pragma prototyped
21
22 /*
23 * crc
24 */
25
26 #define crc_description \
27 "32 bit CRC (cyclic redundancy check)."
28 #define crc_options "\
29 [+polynomial?The 32 bit crc polynomial bitmask with implicit bit 32.]:[mask:=0xedb88320]\
30 [+done?XOR the final crc value with \anumber\a. 0xffffffff is used if \anumber\a is omitted.]:?[number:=0]\
31 [+init?The initial crc value. 0xffffffff is used if \anumber\a is omitted.]:?[number:=0]\
32 [+rotate?XOR each input character with the high order crc byte (instead of the low order).]\
33 [+size?Include the total number of bytes in the crc. \anumber\a, if specified, is first XOR'd into the size.]:?[number:=0]\
34 "
35 #define crc_match "crc"
36 #define crc_open crc_open
37 #define crc_print long_print
38 #define crc_data long_data
39 #define crc_scale 0
40
41 typedef uint32_t Crcnum_t;
42
43 typedef struct Crc_s
44 {
45 _SUM_PUBLIC_
46 _SUM_PRIVATE_
47 _INTEGRAL_PRIVATE_
48 Crcnum_t init;
49 Crcnum_t done;
50 Crcnum_t xorsize;
51 const Crcnum_t *tab; /* use |const| to give the compiler a hint that the data won't change */
52 Crcnum_t tabdata[256];
53 unsigned int addsize;
54 unsigned int rotate;
55 } Crc_t;
56
57 #define CRC(p,s,c) (s = (s >> 8) ^ (p)->tab[(s ^ (c)) & 0xff])
58 #define CRCROTATE(p,s,c) (s = (s << 8) ^ (p)->tab[((s >> 24) ^ (c)) & 0xff])
59
60 static const
61 Crcnum_t posix_cksum_tab[256] = {
62 0x00000000U,
63 0x04c11db7U, 0x09823b6eU, 0x0d4326d9U, 0x130476dcU, 0x17c56b6bU,
64 0x1a864db2U, 0x1e475005U, 0x2608edb8U, 0x22c9f00fU, 0x2f8ad6d6U,
65 0x2b4bcb61U, 0x350c9b64U, 0x31cd86d3U, 0x3c8ea00aU, 0x384fbdbdU,
66 0x4c11db70U, 0x48d0c6c7U, 0x4593e01eU, 0x4152fda9U, 0x5f15adacU,
67 0x5bd4b01bU, 0x569796c2U, 0x52568b75U, 0x6a1936c8U, 0x6ed82b7fU,
68 0x639b0da6U, 0x675a1011U, 0x791d4014U, 0x7ddc5da3U, 0x709f7b7aU,
69 0x745e66cdU, 0x9823b6e0U, 0x9ce2ab57U, 0x91a18d8eU, 0x95609039U,
70 0x8b27c03cU, 0x8fe6dd8bU, 0x82a5fb52U, 0x8664e6e5U, 0xbe2b5b58U,
71 0xbaea46efU, 0xb7a96036U, 0xb3687d81U, 0xad2f2d84U, 0xa9ee3033U,
72 0xa4ad16eaU, 0xa06c0b5dU, 0xd4326d90U, 0xd0f37027U, 0xddb056feU,
73 0xd9714b49U, 0xc7361b4cU, 0xc3f706fbU, 0xceb42022U, 0xca753d95U,
74 0xf23a8028U, 0xf6fb9d9fU, 0xfbb8bb46U, 0xff79a6f1U, 0xe13ef6f4U,
75 0xe5ffeb43U, 0xe8bccd9aU, 0xec7dd02dU, 0x34867077U, 0x30476dc0U,
76 0x3d044b19U, 0x39c556aeU, 0x278206abU, 0x23431b1cU, 0x2e003dc5U,
77 0x2ac12072U, 0x128e9dcfU, 0x164f8078U, 0x1b0ca6a1U, 0x1fcdbb16U,
78 0x018aeb13U, 0x054bf6a4U, 0x0808d07dU, 0x0cc9cdcaU, 0x7897ab07U,
79 0x7c56b6b0U, 0x71159069U, 0x75d48ddeU, 0x6b93dddbU, 0x6f52c06cU,
80 0x6211e6b5U, 0x66d0fb02U, 0x5e9f46bfU, 0x5a5e5b08U, 0x571d7dd1U,
81 0x53dc6066U, 0x4d9b3063U, 0x495a2dd4U, 0x44190b0dU, 0x40d816baU,
82 0xaca5c697U, 0xa864db20U, 0xa527fdf9U, 0xa1e6e04eU, 0xbfa1b04bU,
83 0xbb60adfcU, 0xb6238b25U, 0xb2e29692U, 0x8aad2b2fU, 0x8e6c3698U,
84 0x832f1041U, 0x87ee0df6U, 0x99a95df3U, 0x9d684044U, 0x902b669dU,
85 0x94ea7b2aU, 0xe0b41de7U, 0xe4750050U, 0xe9362689U, 0xedf73b3eU,
86 0xf3b06b3bU, 0xf771768cU, 0xfa325055U, 0xfef34de2U, 0xc6bcf05fU,
87 0xc27dede8U, 0xcf3ecb31U, 0xcbffd686U, 0xd5b88683U, 0xd1799b34U,
88 0xdc3abdedU, 0xd8fba05aU, 0x690ce0eeU, 0x6dcdfd59U, 0x608edb80U,
89 0x644fc637U, 0x7a089632U, 0x7ec98b85U, 0x738aad5cU, 0x774bb0ebU,
90 0x4f040d56U, 0x4bc510e1U, 0x46863638U, 0x42472b8fU, 0x5c007b8aU,
91 0x58c1663dU, 0x558240e4U, 0x51435d53U, 0x251d3b9eU, 0x21dc2629U,
92 0x2c9f00f0U, 0x285e1d47U, 0x36194d42U, 0x32d850f5U, 0x3f9b762cU,
93 0x3b5a6b9bU, 0x0315d626U, 0x07d4cb91U, 0x0a97ed48U, 0x0e56f0ffU,
94 0x1011a0faU, 0x14d0bd4dU, 0x19939b94U, 0x1d528623U, 0xf12f560eU,
95 0xf5ee4bb9U, 0xf8ad6d60U, 0xfc6c70d7U, 0xe22b20d2U, 0xe6ea3d65U,
96 0xeba91bbcU, 0xef68060bU, 0xd727bbb6U, 0xd3e6a601U, 0xdea580d8U,
97 0xda649d6fU, 0xc423cd6aU, 0xc0e2d0ddU, 0xcda1f604U, 0xc960ebb3U,
98 0xbd3e8d7eU, 0xb9ff90c9U, 0xb4bcb610U, 0xb07daba7U, 0xae3afba2U,
99 0xaafbe615U, 0xa7b8c0ccU, 0xa379dd7bU, 0x9b3660c6U, 0x9ff77d71U,
100 0x92b45ba8U, 0x9675461fU, 0x8832161aU, 0x8cf30badU, 0x81b02d74U,
101 0x857130c3U, 0x5d8a9099U, 0x594b8d2eU, 0x5408abf7U, 0x50c9b640U,
102 0x4e8ee645U, 0x4a4ffbf2U, 0x470cdd2bU, 0x43cdc09cU, 0x7b827d21U,
103 0x7f436096U, 0x7200464fU, 0x76c15bf8U, 0x68860bfdU, 0x6c47164aU,
104 0x61043093U, 0x65c52d24U, 0x119b4be9U, 0x155a565eU, 0x18197087U,
105 0x1cd86d30U, 0x029f3d35U, 0x065e2082U, 0x0b1d065bU, 0x0fdc1becU,
106 0x3793a651U, 0x3352bbe6U, 0x3e119d3fU, 0x3ad08088U, 0x2497d08dU,
107 0x2056cd3aU, 0x2d15ebe3U, 0x29d4f654U, 0xc5a92679U, 0xc1683bceU,
108 0xcc2b1d17U, 0xc8ea00a0U, 0xd6ad50a5U, 0xd26c4d12U, 0xdf2f6bcbU,
109 0xdbee767cU, 0xe3a1cbc1U, 0xe760d676U, 0xea23f0afU, 0xeee2ed18U,
110 0xf0a5bd1dU, 0xf464a0aaU, 0xf9278673U, 0xfde69bc4U, 0x89b8fd09U,
111 0x8d79e0beU, 0x803ac667U, 0x84fbdbd0U, 0x9abc8bd5U, 0x9e7d9662U,
112 0x933eb0bbU, 0x97ffad0cU, 0xafb010b1U, 0xab710d06U, 0xa6322bdfU,
113 0xa2f33668U, 0xbcb4666dU, 0xb8757bdaU, 0xb5365d03U, 0xb1f740b4U
114 };
115
116 static Sum_t*
crc_open(const Method_t * method,const char * name)117 crc_open(const Method_t* method, const char* name)
118 {
119 register Crc_t* sum;
120 register const char* s;
121 register const char* t;
122 register const char* v;
123 register int i;
124 register int j;
125 Crcnum_t polynomial;
126 Crcnum_t x;
127
128 if (sum = newof(0, Crc_t, 1, 0))
129 {
130 sum->method = (Method_t*)method;
131 sum->name = name;
132 }
133
134 if(!strcmp(name, "crc-0x04c11db7-rotate-done-size"))
135 {
136 sum->init=0;
137 sum->done=0xffffffff;
138 sum->xorsize=0x0;
139 sum->addsize=0x1;
140 sum->rotate=1;
141
142 /* Optimized codepath for POSIX cksum to save startup time */
143 sum->tab=posix_cksum_tab;
144 }
145 else
146 {
147 polynomial = 0xedb88320;
148 s = name;
149 while (*(t = s))
150 {
151 for (t = s, v = 0; *s && *s != '-'; s++)
152 if (*s == '=' && !v)
153 v = s;
154 i = (v ? v : s) - t;
155 if (isdigit(*t) || v && i >= 4 && strneq(t, "poly", 4) && (t = v + 1))
156 polynomial = strtoul(t, NiL, 0);
157 else if (strneq(t, "done", i))
158 sum->done = v ? strtoul(v + 1, NiL, 0) : ~sum->done;
159 else if (strneq(t, "init", i))
160 sum->init = v ? strtoul(v + 1, NiL, 0) : ~sum->init;
161 else if (strneq(t, "rotate", i))
162 sum->rotate = 1;
163 else if (strneq(t, "size", i))
164 {
165 sum->addsize = 1;
166 if (v)
167 sum->xorsize = strtoul(v + 1, NiL, 0);
168 }
169 if (*s == '-')
170 s++;
171 }
172 if (sum->rotate)
173 {
174 Crcnum_t t;
175 Crcnum_t p[8];
176
177 p[0] = polynomial;
178 for (i = 1; i < 8; i++)
179 p[i] = (p[i-1] << 1) ^ ((p[i-1] & 0x80000000) ? polynomial : 0);
180 for (i = 0; i < elementsof(sum->tabdata); i++)
181 {
182 t = 0;
183 x = i;
184 for (j = 0; j < 8; j++)
185 {
186 if (x & 1)
187 t ^= p[j];
188 x >>= 1;
189 }
190 sum->tabdata[i] = t;
191 }
192 }
193 else
194 {
195 for (i = 0; i < elementsof(sum->tabdata); i++)
196 {
197 x = i;
198 for (j = 0; j < 8; j++)
199 x = (x>>1) ^ ((x & 1) ? polynomial : 0);
200 sum->tabdata[i] = x;
201 }
202 }
203
204 sum->tab=sum->tabdata;
205 }
206
207 return (Sum_t*)sum;
208 }
209
210 static int
crc_init(Sum_t * p)211 crc_init(Sum_t* p)
212 {
213 Crc_t* sum = (Crc_t*)p;
214
215 sum->sum = sum->init;
216 return 0;
217 }
218
219 #if defined(__SUNPRO_C) || defined(__GNUC__)
220
221 #if defined(__SUNPRO_C)
222 # include <sun_prefetch.h>
223 # define sum_prefetch(addr) sun_prefetch_read_many((void *)(addr))
224 #elif defined(__GNUC__)
225 # define sum_prefetch(addr) __builtin_prefetch((addr), 0, 3)
226 #else
227 # error Unknown compiler
228 #endif
229
230 #define CBLOCK_SIZE (64)
231 #pragma unroll(16)
232
233 static int
crc_block(Sum_t * p,const void * s,size_t n)234 crc_block(Sum_t* p, const void* s, size_t n)
235 {
236 Crc_t* sum = (Crc_t*)p;
237 register Crcnum_t c = sum->sum;
238 register const unsigned char* b = (const unsigned char*)s;
239 register const unsigned char* e = b + n;
240 unsigned short i;
241
242 sum_prefetch(b);
243
244 if (sum->rotate)
245 {
246 while (n > CBLOCK_SIZE)
247 {
248 sum_prefetch(b+CBLOCK_SIZE);
249 for(i=0 ; i < CBLOCK_SIZE ; i++)
250 {
251 CRCROTATE(sum, c, *b++);
252 }
253
254 n-=CBLOCK_SIZE;
255 }
256
257 while (b < e)
258 {
259 CRCROTATE(sum, c, *b++);
260 }
261 }
262 else
263 {
264 while (n > CBLOCK_SIZE)
265 {
266 sum_prefetch(b+CBLOCK_SIZE);
267 for(i=0 ; i < CBLOCK_SIZE ; i++)
268 {
269 CRC(sum, c, *b++);
270 }
271
272 n-=CBLOCK_SIZE;
273 }
274
275 while (b < e)
276 {
277 CRC(sum, c, *b++);
278 }
279 }
280
281 sum->sum = c;
282 return 0;
283 }
284 #else
285 static int
crc_block(Sum_t * p,const void * s,size_t n)286 crc_block(Sum_t* p, const void* s, size_t n)
287 {
288 Crc_t* sum = (Crc_t*)p;
289 register Crcnum_t c = sum->sum;
290 register unsigned char* b = (unsigned char*)s;
291 register unsigned char* e = b + n;
292
293 if (sum->rotate)
294 while (b < e)
295 CRCROTATE(sum, c, *b++);
296 else
297 while (b < e)
298 CRC(sum, c, *b++);
299 sum->sum = c;
300 return 0;
301 }
302 #endif /* defined(__SUNPRO_C) || defined(__GNUC__) */
303
304 static int
crc_done(Sum_t * p)305 crc_done(Sum_t* p)
306 {
307 register Crc_t* sum = (Crc_t*)p;
308 register Crcnum_t c;
309 register uintmax_t n;
310 int i;
311 int j;
312
313 c = sum->sum;
314 if (sum->addsize)
315 {
316 n = sum->size ^ sum->xorsize;
317 if (sum->rotate)
318 while (n)
319 {
320 CRCROTATE(sum, c, n);
321 n >>= 8;
322 }
323 else
324 for (i = 0, j = 32; i < 4; i++)
325 {
326 j -= 8;
327 CRC(sum, c, n >> j);
328 }
329 }
330 sum->sum = c ^ sum->done;
331 sum->total_sum ^= (sum->sum &= 0xffffffff);
332 return 0;
333 }
334