xref: /illumos-gate/usr/src/contrib/ast/src/lib/libsum/sum-crc.c (revision b30d193948be5a7794d7ae3ba0ed9c2f72c88e0f)
1 /***********************************************************************
2 *                                                                      *
3 *               This software is part of the ast package               *
4 *          Copyright (c) 1996-2011 AT&T Intellectual Property          *
5 *                      and is licensed under the                       *
6 *                 Eclipse Public License, Version 1.0                  *
7 *                    by AT&T Intellectual Property                     *
8 *                                                                      *
9 *                A copy of the License is available at                 *
10 *          http://www.eclipse.org/org/documents/epl-v10.html           *
11 *         (with md5 checksum b35adb5213ca9657e911e9befb180842)         *
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 		sum->tab=sum->tabdata;
204 	}
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