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
41typedef uint32_t Crcnum_t;
42
43typedef 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
60static const
61Crcnum_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
116static Sum_t*
117crc_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
210static int
211crc_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
233static int
234crc_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
285static int
286crc_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
304static int
305crc_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