Loading...
1/*
2 * Aug 8, 2011 Bob Pearson with help from Joakim Tjernlund and George Spelvin
3 * cleaned up code to current version of sparse and added the slicing-by-8
4 * algorithm to the closely similar existing slicing-by-4 algorithm.
5 *
6 * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com>
7 * Nicer crc32 functions/docs submitted by linux@horizon.com. Thanks!
8 * Code was from the public domain, copyright abandoned. Code was
9 * subsequently included in the kernel, thus was re-licensed under the
10 * GNU GPL v2.
11 *
12 * Oct 12, 2000 Matt Domsch <Matt_Domsch@dell.com>
13 * Same crc32 function was used in 5 other places in the kernel.
14 * I made one version, and deleted the others.
15 * There are various incantations of crc32(). Some use a seed of 0 or ~0.
16 * Some xor at the end with ~0. The generic crc32() function takes
17 * seed as an argument, and doesn't xor at the end. Then individual
18 * users can do whatever they need.
19 * drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0.
20 * fs/jffs2 uses seed 0, doesn't xor with ~0.
21 * fs/partitions/efi.c uses seed ~0, xor's with ~0.
22 *
23 * This source code is licensed under the GNU General Public License,
24 * Version 2. See the file COPYING for more details.
25 */
26
27/* see: Documentation/crc32.txt for a description of algorithms */
28
29#include <linux/crc32.h>
30#include <linux/module.h>
31#include <linux/types.h>
32#include <linux/sched.h>
33#include "crc32defs.h"
34
35#if CRC_LE_BITS > 8
36# define tole(x) ((__force u32) cpu_to_le32(x))
37#else
38# define tole(x) (x)
39#endif
40
41#if CRC_BE_BITS > 8
42# define tobe(x) ((__force u32) cpu_to_be32(x))
43#else
44# define tobe(x) (x)
45#endif
46
47#include "crc32table.h"
48
49MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
50MODULE_DESCRIPTION("Various CRC32 calculations");
51MODULE_LICENSE("GPL");
52
53#if CRC_LE_BITS > 8 || CRC_BE_BITS > 8
54
55/* implements slicing-by-4 or slicing-by-8 algorithm */
56static inline u32 __pure
57crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256])
58{
59# ifdef __LITTLE_ENDIAN
60# define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8)
61# define DO_CRC4 (t3[(q) & 255] ^ t2[(q >> 8) & 255] ^ \
62 t1[(q >> 16) & 255] ^ t0[(q >> 24) & 255])
63# define DO_CRC8 (t7[(q) & 255] ^ t6[(q >> 8) & 255] ^ \
64 t5[(q >> 16) & 255] ^ t4[(q >> 24) & 255])
65# else
66# define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
67# define DO_CRC4 (t0[(q) & 255] ^ t1[(q >> 8) & 255] ^ \
68 t2[(q >> 16) & 255] ^ t3[(q >> 24) & 255])
69# define DO_CRC8 (t4[(q) & 255] ^ t5[(q >> 8) & 255] ^ \
70 t6[(q >> 16) & 255] ^ t7[(q >> 24) & 255])
71# endif
72 const u32 *b;
73 size_t rem_len;
74# ifdef CONFIG_X86
75 size_t i;
76# endif
77 const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3];
78# if CRC_LE_BITS != 32
79 const u32 *t4 = tab[4], *t5 = tab[5], *t6 = tab[6], *t7 = tab[7];
80# endif
81 u32 q;
82
83 /* Align it */
84 if (unlikely((long)buf & 3 && len)) {
85 do {
86 DO_CRC(*buf++);
87 } while ((--len) && ((long)buf)&3);
88 }
89
90# if CRC_LE_BITS == 32
91 rem_len = len & 3;
92 len = len >> 2;
93# else
94 rem_len = len & 7;
95 len = len >> 3;
96# endif
97
98 b = (const u32 *)buf;
99# ifdef CONFIG_X86
100 --b;
101 for (i = 0; i < len; i++) {
102# else
103 for (--b; len; --len) {
104# endif
105 q = crc ^ *++b; /* use pre increment for speed */
106# if CRC_LE_BITS == 32
107 crc = DO_CRC4;
108# else
109 crc = DO_CRC8;
110 q = *++b;
111 crc ^= DO_CRC4;
112# endif
113 }
114 len = rem_len;
115 /* And the last few bytes */
116 if (len) {
117 u8 *p = (u8 *)(b + 1) - 1;
118# ifdef CONFIG_X86
119 for (i = 0; i < len; i++)
120 DO_CRC(*++p); /* use pre increment for speed */
121# else
122 do {
123 DO_CRC(*++p); /* use pre increment for speed */
124 } while (--len);
125# endif
126 }
127 return crc;
128#undef DO_CRC
129#undef DO_CRC4
130#undef DO_CRC8
131}
132#endif
133
134
135/**
136 * crc32_le_generic() - Calculate bitwise little-endian Ethernet AUTODIN II
137 * CRC32/CRC32C
138 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for other
139 * uses, or the previous crc32/crc32c value if computing incrementally.
140 * @p: pointer to buffer over which CRC32/CRC32C is run
141 * @len: length of buffer @p
142 * @tab: little-endian Ethernet table
143 * @polynomial: CRC32/CRC32c LE polynomial
144 */
145static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p,
146 size_t len, const u32 (*tab)[256],
147 u32 polynomial)
148{
149#if CRC_LE_BITS == 1
150 int i;
151 while (len--) {
152 crc ^= *p++;
153 for (i = 0; i < 8; i++)
154 crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0);
155 }
156# elif CRC_LE_BITS == 2
157 while (len--) {
158 crc ^= *p++;
159 crc = (crc >> 2) ^ tab[0][crc & 3];
160 crc = (crc >> 2) ^ tab[0][crc & 3];
161 crc = (crc >> 2) ^ tab[0][crc & 3];
162 crc = (crc >> 2) ^ tab[0][crc & 3];
163 }
164# elif CRC_LE_BITS == 4
165 while (len--) {
166 crc ^= *p++;
167 crc = (crc >> 4) ^ tab[0][crc & 15];
168 crc = (crc >> 4) ^ tab[0][crc & 15];
169 }
170# elif CRC_LE_BITS == 8
171 /* aka Sarwate algorithm */
172 while (len--) {
173 crc ^= *p++;
174 crc = (crc >> 8) ^ tab[0][crc & 255];
175 }
176# else
177 crc = (__force u32) __cpu_to_le32(crc);
178 crc = crc32_body(crc, p, len, tab);
179 crc = __le32_to_cpu((__force __le32)crc);
180#endif
181 return crc;
182}
183
184#if CRC_LE_BITS == 1
185u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
186{
187 return crc32_le_generic(crc, p, len, NULL, CRCPOLY_LE);
188}
189u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len)
190{
191 return crc32_le_generic(crc, p, len, NULL, CRC32C_POLY_LE);
192}
193#else
194u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
195{
196 return crc32_le_generic(crc, p, len,
197 (const u32 (*)[256])crc32table_le, CRCPOLY_LE);
198}
199u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len)
200{
201 return crc32_le_generic(crc, p, len,
202 (const u32 (*)[256])crc32ctable_le, CRC32C_POLY_LE);
203}
204#endif
205EXPORT_SYMBOL(crc32_le);
206EXPORT_SYMBOL(__crc32c_le);
207
208/*
209 * This multiplies the polynomials x and y modulo the given modulus.
210 * This follows the "little-endian" CRC convention that the lsbit
211 * represents the highest power of x, and the msbit represents x^0.
212 */
213static u32 __attribute_const__ gf2_multiply(u32 x, u32 y, u32 modulus)
214{
215 u32 product = x & 1 ? y : 0;
216 int i;
217
218 for (i = 0; i < 31; i++) {
219 product = (product >> 1) ^ (product & 1 ? modulus : 0);
220 x >>= 1;
221 product ^= x & 1 ? y : 0;
222 }
223
224 return product;
225}
226
227/**
228 * crc32_generic_shift - Append len 0 bytes to crc, in logarithmic time
229 * @crc: The original little-endian CRC (i.e. lsbit is x^31 coefficient)
230 * @len: The number of bytes. @crc is multiplied by x^(8*@len)
231 * @polynomial: The modulus used to reduce the result to 32 bits.
232 *
233 * It's possible to parallelize CRC computations by computing a CRC
234 * over separate ranges of a buffer, then summing them.
235 * This shifts the given CRC by 8*len bits (i.e. produces the same effect
236 * as appending len bytes of zero to the data), in time proportional
237 * to log(len).
238 */
239static u32 __attribute_const__ crc32_generic_shift(u32 crc, size_t len,
240 u32 polynomial)
241{
242 u32 power = polynomial; /* CRC of x^32 */
243 int i;
244
245 /* Shift up to 32 bits in the simple linear way */
246 for (i = 0; i < 8 * (int)(len & 3); i++)
247 crc = (crc >> 1) ^ (crc & 1 ? polynomial : 0);
248
249 len >>= 2;
250 if (!len)
251 return crc;
252
253 for (;;) {
254 /* "power" is x^(2^i), modulo the polynomial */
255 if (len & 1)
256 crc = gf2_multiply(crc, power, polynomial);
257
258 len >>= 1;
259 if (!len)
260 break;
261
262 /* Square power, advancing to x^(2^(i+1)) */
263 power = gf2_multiply(power, power, polynomial);
264 }
265
266 return crc;
267}
268
269u32 __attribute_const__ crc32_le_shift(u32 crc, size_t len)
270{
271 return crc32_generic_shift(crc, len, CRCPOLY_LE);
272}
273
274u32 __attribute_const__ __crc32c_le_shift(u32 crc, size_t len)
275{
276 return crc32_generic_shift(crc, len, CRC32C_POLY_LE);
277}
278EXPORT_SYMBOL(crc32_le_shift);
279EXPORT_SYMBOL(__crc32c_le_shift);
280
281/**
282 * crc32_be_generic() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
283 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for
284 * other uses, or the previous crc32 value if computing incrementally.
285 * @p: pointer to buffer over which CRC32 is run
286 * @len: length of buffer @p
287 * @tab: big-endian Ethernet table
288 * @polynomial: CRC32 BE polynomial
289 */
290static inline u32 __pure crc32_be_generic(u32 crc, unsigned char const *p,
291 size_t len, const u32 (*tab)[256],
292 u32 polynomial)
293{
294#if CRC_BE_BITS == 1
295 int i;
296 while (len--) {
297 crc ^= *p++ << 24;
298 for (i = 0; i < 8; i++)
299 crc =
300 (crc << 1) ^ ((crc & 0x80000000) ? polynomial :
301 0);
302 }
303# elif CRC_BE_BITS == 2
304 while (len--) {
305 crc ^= *p++ << 24;
306 crc = (crc << 2) ^ tab[0][crc >> 30];
307 crc = (crc << 2) ^ tab[0][crc >> 30];
308 crc = (crc << 2) ^ tab[0][crc >> 30];
309 crc = (crc << 2) ^ tab[0][crc >> 30];
310 }
311# elif CRC_BE_BITS == 4
312 while (len--) {
313 crc ^= *p++ << 24;
314 crc = (crc << 4) ^ tab[0][crc >> 28];
315 crc = (crc << 4) ^ tab[0][crc >> 28];
316 }
317# elif CRC_BE_BITS == 8
318 while (len--) {
319 crc ^= *p++ << 24;
320 crc = (crc << 8) ^ tab[0][crc >> 24];
321 }
322# else
323 crc = (__force u32) __cpu_to_be32(crc);
324 crc = crc32_body(crc, p, len, tab);
325 crc = __be32_to_cpu((__force __be32)crc);
326# endif
327 return crc;
328}
329
330#if CRC_LE_BITS == 1
331u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
332{
333 return crc32_be_generic(crc, p, len, NULL, CRCPOLY_BE);
334}
335#else
336u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
337{
338 return crc32_be_generic(crc, p, len,
339 (const u32 (*)[256])crc32table_be, CRCPOLY_BE);
340}
341#endif
342EXPORT_SYMBOL(crc32_be);
343
344#ifdef CONFIG_CRC32_SELFTEST
345
346/* 4096 random bytes */
347static u8 const __aligned(8) test_buf[] __initconst =
348{
349 0x5b, 0x85, 0x21, 0xcb, 0x09, 0x68, 0x7d, 0x30,
350 0xc7, 0x69, 0xd7, 0x30, 0x92, 0xde, 0x59, 0xe4,
351 0xc9, 0x6e, 0x8b, 0xdb, 0x98, 0x6b, 0xaa, 0x60,
352 0xa8, 0xb5, 0xbc, 0x6c, 0xa9, 0xb1, 0x5b, 0x2c,
353 0xea, 0xb4, 0x92, 0x6a, 0x3f, 0x79, 0x91, 0xe4,
354 0xe9, 0x70, 0x51, 0x8c, 0x7f, 0x95, 0x6f, 0x1a,
355 0x56, 0xa1, 0x5c, 0x27, 0x03, 0x67, 0x9f, 0x3a,
356 0xe2, 0x31, 0x11, 0x29, 0x6b, 0x98, 0xfc, 0xc4,
357 0x53, 0x24, 0xc5, 0x8b, 0xce, 0x47, 0xb2, 0xb9,
358 0x32, 0xcb, 0xc1, 0xd0, 0x03, 0x57, 0x4e, 0xd4,
359 0xe9, 0x3c, 0xa1, 0x63, 0xcf, 0x12, 0x0e, 0xca,
360 0xe1, 0x13, 0xd1, 0x93, 0xa6, 0x88, 0x5c, 0x61,
361 0x5b, 0xbb, 0xf0, 0x19, 0x46, 0xb4, 0xcf, 0x9e,
362 0xb6, 0x6b, 0x4c, 0x3a, 0xcf, 0x60, 0xf9, 0x7a,
363 0x8d, 0x07, 0x63, 0xdb, 0x40, 0xe9, 0x0b, 0x6f,
364 0xad, 0x97, 0xf1, 0xed, 0xd0, 0x1e, 0x26, 0xfd,
365 0xbf, 0xb7, 0xc8, 0x04, 0x94, 0xf8, 0x8b, 0x8c,
366 0xf1, 0xab, 0x7a, 0xd4, 0xdd, 0xf3, 0xe8, 0x88,
367 0xc3, 0xed, 0x17, 0x8a, 0x9b, 0x40, 0x0d, 0x53,
368 0x62, 0x12, 0x03, 0x5f, 0x1b, 0x35, 0x32, 0x1f,
369 0xb4, 0x7b, 0x93, 0x78, 0x0d, 0xdb, 0xce, 0xa4,
370 0xc0, 0x47, 0xd5, 0xbf, 0x68, 0xe8, 0x5d, 0x74,
371 0x8f, 0x8e, 0x75, 0x1c, 0xb2, 0x4f, 0x9a, 0x60,
372 0xd1, 0xbe, 0x10, 0xf4, 0x5c, 0xa1, 0x53, 0x09,
373 0xa5, 0xe0, 0x09, 0x54, 0x85, 0x5c, 0xdc, 0x07,
374 0xe7, 0x21, 0x69, 0x7b, 0x8a, 0xfd, 0x90, 0xf1,
375 0x22, 0xd0, 0xb4, 0x36, 0x28, 0xe6, 0xb8, 0x0f,
376 0x39, 0xde, 0xc8, 0xf3, 0x86, 0x60, 0x34, 0xd2,
377 0x5e, 0xdf, 0xfd, 0xcf, 0x0f, 0xa9, 0x65, 0xf0,
378 0xd5, 0x4d, 0x96, 0x40, 0xe3, 0xdf, 0x3f, 0x95,
379 0x5a, 0x39, 0x19, 0x93, 0xf4, 0x75, 0xce, 0x22,
380 0x00, 0x1c, 0x93, 0xe2, 0x03, 0x66, 0xf4, 0x93,
381 0x73, 0x86, 0x81, 0x8e, 0x29, 0x44, 0x48, 0x86,
382 0x61, 0x7c, 0x48, 0xa3, 0x43, 0xd2, 0x9c, 0x8d,
383 0xd4, 0x95, 0xdd, 0xe1, 0x22, 0x89, 0x3a, 0x40,
384 0x4c, 0x1b, 0x8a, 0x04, 0xa8, 0x09, 0x69, 0x8b,
385 0xea, 0xc6, 0x55, 0x8e, 0x57, 0xe6, 0x64, 0x35,
386 0xf0, 0xc7, 0x16, 0x9f, 0x5d, 0x5e, 0x86, 0x40,
387 0x46, 0xbb, 0xe5, 0x45, 0x88, 0xfe, 0xc9, 0x63,
388 0x15, 0xfb, 0xf5, 0xbd, 0x71, 0x61, 0xeb, 0x7b,
389 0x78, 0x70, 0x07, 0x31, 0x03, 0x9f, 0xb2, 0xc8,
390 0xa7, 0xab, 0x47, 0xfd, 0xdf, 0xa0, 0x78, 0x72,
391 0xa4, 0x2a, 0xe4, 0xb6, 0xba, 0xc0, 0x1e, 0x86,
392 0x71, 0xe6, 0x3d, 0x18, 0x37, 0x70, 0xe6, 0xff,
393 0xe0, 0xbc, 0x0b, 0x22, 0xa0, 0x1f, 0xd3, 0xed,
394 0xa2, 0x55, 0x39, 0xab, 0xa8, 0x13, 0x73, 0x7c,
395 0x3f, 0xb2, 0xd6, 0x19, 0xac, 0xff, 0x99, 0xed,
396 0xe8, 0xe6, 0xa6, 0x22, 0xe3, 0x9c, 0xf1, 0x30,
397 0xdc, 0x01, 0x0a, 0x56, 0xfa, 0xe4, 0xc9, 0x99,
398 0xdd, 0xa8, 0xd8, 0xda, 0x35, 0x51, 0x73, 0xb4,
399 0x40, 0x86, 0x85, 0xdb, 0x5c, 0xd5, 0x85, 0x80,
400 0x14, 0x9c, 0xfd, 0x98, 0xa9, 0x82, 0xc5, 0x37,
401 0xff, 0x32, 0x5d, 0xd0, 0x0b, 0xfa, 0xdc, 0x04,
402 0x5e, 0x09, 0xd2, 0xca, 0x17, 0x4b, 0x1a, 0x8e,
403 0x15, 0xe1, 0xcc, 0x4e, 0x52, 0x88, 0x35, 0xbd,
404 0x48, 0xfe, 0x15, 0xa0, 0x91, 0xfd, 0x7e, 0x6c,
405 0x0e, 0x5d, 0x79, 0x1b, 0x81, 0x79, 0xd2, 0x09,
406 0x34, 0x70, 0x3d, 0x81, 0xec, 0xf6, 0x24, 0xbb,
407 0xfb, 0xf1, 0x7b, 0xdf, 0x54, 0xea, 0x80, 0x9b,
408 0xc7, 0x99, 0x9e, 0xbd, 0x16, 0x78, 0x12, 0x53,
409 0x5e, 0x01, 0xa7, 0x4e, 0xbd, 0x67, 0xe1, 0x9b,
410 0x4c, 0x0e, 0x61, 0x45, 0x97, 0xd2, 0xf0, 0x0f,
411 0xfe, 0x15, 0x08, 0xb7, 0x11, 0x4c, 0xe7, 0xff,
412 0x81, 0x53, 0xff, 0x91, 0x25, 0x38, 0x7e, 0x40,
413 0x94, 0xe5, 0xe0, 0xad, 0xe6, 0xd9, 0x79, 0xb6,
414 0x92, 0xc9, 0xfc, 0xde, 0xc3, 0x1a, 0x23, 0xbb,
415 0xdd, 0xc8, 0x51, 0x0c, 0x3a, 0x72, 0xfa, 0x73,
416 0x6f, 0xb7, 0xee, 0x61, 0x39, 0x03, 0x01, 0x3f,
417 0x7f, 0x94, 0x2e, 0x2e, 0xba, 0x3a, 0xbb, 0xb4,
418 0xfa, 0x6a, 0x17, 0xfe, 0xea, 0xef, 0x5e, 0x66,
419 0x97, 0x3f, 0x32, 0x3d, 0xd7, 0x3e, 0xb1, 0xf1,
420 0x6c, 0x14, 0x4c, 0xfd, 0x37, 0xd3, 0x38, 0x80,
421 0xfb, 0xde, 0xa6, 0x24, 0x1e, 0xc8, 0xca, 0x7f,
422 0x3a, 0x93, 0xd8, 0x8b, 0x18, 0x13, 0xb2, 0xe5,
423 0xe4, 0x93, 0x05, 0x53, 0x4f, 0x84, 0x66, 0xa7,
424 0x58, 0x5c, 0x7b, 0x86, 0x52, 0x6d, 0x0d, 0xce,
425 0xa4, 0x30, 0x7d, 0xb6, 0x18, 0x9f, 0xeb, 0xff,
426 0x22, 0xbb, 0x72, 0x29, 0xb9, 0x44, 0x0b, 0x48,
427 0x1e, 0x84, 0x71, 0x81, 0xe3, 0x6d, 0x73, 0x26,
428 0x92, 0xb4, 0x4d, 0x2a, 0x29, 0xb8, 0x1f, 0x72,
429 0xed, 0xd0, 0xe1, 0x64, 0x77, 0xea, 0x8e, 0x88,
430 0x0f, 0xef, 0x3f, 0xb1, 0x3b, 0xad, 0xf9, 0xc9,
431 0x8b, 0xd0, 0xac, 0xc6, 0xcc, 0xa9, 0x40, 0xcc,
432 0x76, 0xf6, 0x3b, 0x53, 0xb5, 0x88, 0xcb, 0xc8,
433 0x37, 0xf1, 0xa2, 0xba, 0x23, 0x15, 0x99, 0x09,
434 0xcc, 0xe7, 0x7a, 0x3b, 0x37, 0xf7, 0x58, 0xc8,
435 0x46, 0x8c, 0x2b, 0x2f, 0x4e, 0x0e, 0xa6, 0x5c,
436 0xea, 0x85, 0x55, 0xba, 0x02, 0x0e, 0x0e, 0x48,
437 0xbc, 0xe1, 0xb1, 0x01, 0x35, 0x79, 0x13, 0x3d,
438 0x1b, 0xc0, 0x53, 0x68, 0x11, 0xe7, 0x95, 0x0f,
439 0x9d, 0x3f, 0x4c, 0x47, 0x7b, 0x4d, 0x1c, 0xae,
440 0x50, 0x9b, 0xcb, 0xdd, 0x05, 0x8d, 0x9a, 0x97,
441 0xfd, 0x8c, 0xef, 0x0c, 0x1d, 0x67, 0x73, 0xa8,
442 0x28, 0x36, 0xd5, 0xb6, 0x92, 0x33, 0x40, 0x75,
443 0x0b, 0x51, 0xc3, 0x64, 0xba, 0x1d, 0xc2, 0xcc,
444 0xee, 0x7d, 0x54, 0x0f, 0x27, 0x69, 0xa7, 0x27,
445 0x63, 0x30, 0x29, 0xd9, 0xc8, 0x84, 0xd8, 0xdf,
446 0x9f, 0x68, 0x8d, 0x04, 0xca, 0xa6, 0xc5, 0xc7,
447 0x7a, 0x5c, 0xc8, 0xd1, 0xcb, 0x4a, 0xec, 0xd0,
448 0xd8, 0x20, 0x69, 0xc5, 0x17, 0xcd, 0x78, 0xc8,
449 0x75, 0x23, 0x30, 0x69, 0xc9, 0xd4, 0xea, 0x5c,
450 0x4f, 0x6b, 0x86, 0x3f, 0x8b, 0xfe, 0xee, 0x44,
451 0xc9, 0x7c, 0xb7, 0xdd, 0x3e, 0xe5, 0xec, 0x54,
452 0x03, 0x3e, 0xaa, 0x82, 0xc6, 0xdf, 0xb2, 0x38,
453 0x0e, 0x5d, 0xb3, 0x88, 0xd9, 0xd3, 0x69, 0x5f,
454 0x8f, 0x70, 0x8a, 0x7e, 0x11, 0xd9, 0x1e, 0x7b,
455 0x38, 0xf1, 0x42, 0x1a, 0xc0, 0x35, 0xf5, 0xc7,
456 0x36, 0x85, 0xf5, 0xf7, 0xb8, 0x7e, 0xc7, 0xef,
457 0x18, 0xf1, 0x63, 0xd6, 0x7a, 0xc6, 0xc9, 0x0e,
458 0x4d, 0x69, 0x4f, 0x84, 0xef, 0x26, 0x41, 0x0c,
459 0xec, 0xc7, 0xe0, 0x7e, 0x3c, 0x67, 0x01, 0x4c,
460 0x62, 0x1a, 0x20, 0x6f, 0xee, 0x47, 0x4d, 0xc0,
461 0x99, 0x13, 0x8d, 0x91, 0x4a, 0x26, 0xd4, 0x37,
462 0x28, 0x90, 0x58, 0x75, 0x66, 0x2b, 0x0a, 0xdf,
463 0xda, 0xee, 0x92, 0x25, 0x90, 0x62, 0x39, 0x9e,
464 0x44, 0x98, 0xad, 0xc1, 0x88, 0xed, 0xe4, 0xb4,
465 0xaf, 0xf5, 0x8c, 0x9b, 0x48, 0x4d, 0x56, 0x60,
466 0x97, 0x0f, 0x61, 0x59, 0x9e, 0xa6, 0x27, 0xfe,
467 0xc1, 0x91, 0x15, 0x38, 0xb8, 0x0f, 0xae, 0x61,
468 0x7d, 0x26, 0x13, 0x5a, 0x73, 0xff, 0x1c, 0xa3,
469 0x61, 0x04, 0x58, 0x48, 0x55, 0x44, 0x11, 0xfe,
470 0x15, 0xca, 0xc3, 0xbd, 0xca, 0xc5, 0xb4, 0x40,
471 0x5d, 0x1b, 0x7f, 0x39, 0xb5, 0x9c, 0x35, 0xec,
472 0x61, 0x15, 0x32, 0x32, 0xb8, 0x4e, 0x40, 0x9f,
473 0x17, 0x1f, 0x0a, 0x4d, 0xa9, 0x91, 0xef, 0xb7,
474 0xb0, 0xeb, 0xc2, 0x83, 0x9a, 0x6c, 0xd2, 0x79,
475 0x43, 0x78, 0x5e, 0x2f, 0xe5, 0xdd, 0x1a, 0x3c,
476 0x45, 0xab, 0x29, 0x40, 0x3a, 0x37, 0x5b, 0x6f,
477 0xd7, 0xfc, 0x48, 0x64, 0x3c, 0x49, 0xfb, 0x21,
478 0xbe, 0xc3, 0xff, 0x07, 0xfb, 0x17, 0xe9, 0xc9,
479 0x0c, 0x4c, 0x5c, 0x15, 0x9e, 0x8e, 0x22, 0x30,
480 0x0a, 0xde, 0x48, 0x7f, 0xdb, 0x0d, 0xd1, 0x2b,
481 0x87, 0x38, 0x9e, 0xcc, 0x5a, 0x01, 0x16, 0xee,
482 0x75, 0x49, 0x0d, 0x30, 0x01, 0x34, 0x6a, 0xb6,
483 0x9a, 0x5a, 0x2a, 0xec, 0xbb, 0x48, 0xac, 0xd3,
484 0x77, 0x83, 0xd8, 0x08, 0x86, 0x4f, 0x48, 0x09,
485 0x29, 0x41, 0x79, 0xa1, 0x03, 0x12, 0xc4, 0xcd,
486 0x90, 0x55, 0x47, 0x66, 0x74, 0x9a, 0xcc, 0x4f,
487 0x35, 0x8c, 0xd6, 0x98, 0xef, 0xeb, 0x45, 0xb9,
488 0x9a, 0x26, 0x2f, 0x39, 0xa5, 0x70, 0x6d, 0xfc,
489 0xb4, 0x51, 0xee, 0xf4, 0x9c, 0xe7, 0x38, 0x59,
490 0xad, 0xf4, 0xbc, 0x46, 0xff, 0x46, 0x8e, 0x60,
491 0x9c, 0xa3, 0x60, 0x1d, 0xf8, 0x26, 0x72, 0xf5,
492 0x72, 0x9d, 0x68, 0x80, 0x04, 0xf6, 0x0b, 0xa1,
493 0x0a, 0xd5, 0xa7, 0x82, 0x3a, 0x3e, 0x47, 0xa8,
494 0x5a, 0xde, 0x59, 0x4f, 0x7b, 0x07, 0xb3, 0xe9,
495 0x24, 0x19, 0x3d, 0x34, 0x05, 0xec, 0xf1, 0xab,
496 0x6e, 0x64, 0x8f, 0xd3, 0xe6, 0x41, 0x86, 0x80,
497 0x70, 0xe3, 0x8d, 0x60, 0x9c, 0x34, 0x25, 0x01,
498 0x07, 0x4d, 0x19, 0x41, 0x4e, 0x3d, 0x5c, 0x7e,
499 0xa8, 0xf5, 0xcc, 0xd5, 0x7b, 0xe2, 0x7d, 0x3d,
500 0x49, 0x86, 0x7d, 0x07, 0xb7, 0x10, 0xe3, 0x35,
501 0xb8, 0x84, 0x6d, 0x76, 0xab, 0x17, 0xc6, 0x38,
502 0xb4, 0xd3, 0x28, 0x57, 0xad, 0xd3, 0x88, 0x5a,
503 0xda, 0xea, 0xc8, 0x94, 0xcc, 0x37, 0x19, 0xac,
504 0x9c, 0x9f, 0x4b, 0x00, 0x15, 0xc0, 0xc8, 0xca,
505 0x1f, 0x15, 0xaa, 0xe0, 0xdb, 0xf9, 0x2f, 0x57,
506 0x1b, 0x24, 0xc7, 0x6f, 0x76, 0x29, 0xfb, 0xed,
507 0x25, 0x0d, 0xc0, 0xfe, 0xbd, 0x5a, 0xbf, 0x20,
508 0x08, 0x51, 0x05, 0xec, 0x71, 0xa3, 0xbf, 0xef,
509 0x5e, 0x99, 0x75, 0xdb, 0x3c, 0x5f, 0x9a, 0x8c,
510 0xbb, 0x19, 0x5c, 0x0e, 0x93, 0x19, 0xf8, 0x6a,
511 0xbc, 0xf2, 0x12, 0x54, 0x2f, 0xcb, 0x28, 0x64,
512 0x88, 0xb3, 0x92, 0x0d, 0x96, 0xd1, 0xa6, 0xe4,
513 0x1f, 0xf1, 0x4d, 0xa4, 0xab, 0x1c, 0xee, 0x54,
514 0xf2, 0xad, 0x29, 0x6d, 0x32, 0x37, 0xb2, 0x16,
515 0x77, 0x5c, 0xdc, 0x2e, 0x54, 0xec, 0x75, 0x26,
516 0xc6, 0x36, 0xd9, 0x17, 0x2c, 0xf1, 0x7a, 0xdc,
517 0x4b, 0xf1, 0xe2, 0xd9, 0x95, 0xba, 0xac, 0x87,
518 0xc1, 0xf3, 0x8e, 0x58, 0x08, 0xd8, 0x87, 0x60,
519 0xc9, 0xee, 0x6a, 0xde, 0xa4, 0xd2, 0xfc, 0x0d,
520 0xe5, 0x36, 0xc4, 0x5c, 0x52, 0xb3, 0x07, 0x54,
521 0x65, 0x24, 0xc1, 0xb1, 0xd1, 0xb1, 0x53, 0x13,
522 0x31, 0x79, 0x7f, 0x05, 0x76, 0xeb, 0x37, 0x59,
523 0x15, 0x2b, 0xd1, 0x3f, 0xac, 0x08, 0x97, 0xeb,
524 0x91, 0x98, 0xdf, 0x6c, 0x09, 0x0d, 0x04, 0x9f,
525 0xdc, 0x3b, 0x0e, 0x60, 0x68, 0x47, 0x23, 0x15,
526 0x16, 0xc6, 0x0b, 0x35, 0xf8, 0x77, 0xa2, 0x78,
527 0x50, 0xd4, 0x64, 0x22, 0x33, 0xff, 0xfb, 0x93,
528 0x71, 0x46, 0x50, 0x39, 0x1b, 0x9c, 0xea, 0x4e,
529 0x8d, 0x0c, 0x37, 0xe5, 0x5c, 0x51, 0x3a, 0x31,
530 0xb2, 0x85, 0x84, 0x3f, 0x41, 0xee, 0xa2, 0xc1,
531 0xc6, 0x13, 0x3b, 0x54, 0x28, 0xd2, 0x18, 0x37,
532 0xcc, 0x46, 0x9f, 0x6a, 0x91, 0x3d, 0x5a, 0x15,
533 0x3c, 0x89, 0xa3, 0x61, 0x06, 0x7d, 0x2e, 0x78,
534 0xbe, 0x7d, 0x40, 0xba, 0x2f, 0x95, 0xb1, 0x2f,
535 0x87, 0x3b, 0x8a, 0xbe, 0x6a, 0xf4, 0xc2, 0x31,
536 0x74, 0xee, 0x91, 0xe0, 0x23, 0xaa, 0x5d, 0x7f,
537 0xdd, 0xf0, 0x44, 0x8c, 0x0b, 0x59, 0x2b, 0xfc,
538 0x48, 0x3a, 0xdf, 0x07, 0x05, 0x38, 0x6c, 0xc9,
539 0xeb, 0x18, 0x24, 0x68, 0x8d, 0x58, 0x98, 0xd3,
540 0x31, 0xa3, 0xe4, 0x70, 0x59, 0xb1, 0x21, 0xbe,
541 0x7e, 0x65, 0x7d, 0xb8, 0x04, 0xab, 0xf6, 0xe4,
542 0xd7, 0xda, 0xec, 0x09, 0x8f, 0xda, 0x6d, 0x24,
543 0x07, 0xcc, 0x29, 0x17, 0x05, 0x78, 0x1a, 0xc1,
544 0xb1, 0xce, 0xfc, 0xaa, 0x2d, 0xe7, 0xcc, 0x85,
545 0x84, 0x84, 0x03, 0x2a, 0x0c, 0x3f, 0xa9, 0xf8,
546 0xfd, 0x84, 0x53, 0x59, 0x5c, 0xf0, 0xd4, 0x09,
547 0xf0, 0xd2, 0x6c, 0x32, 0x03, 0xb0, 0xa0, 0x8c,
548 0x52, 0xeb, 0x23, 0x91, 0x88, 0x43, 0x13, 0x46,
549 0xf6, 0x1e, 0xb4, 0x1b, 0xf5, 0x8e, 0x3a, 0xb5,
550 0x3d, 0x00, 0xf6, 0xe5, 0x08, 0x3d, 0x5f, 0x39,
551 0xd3, 0x21, 0x69, 0xbc, 0x03, 0x22, 0x3a, 0xd2,
552 0x5c, 0x84, 0xf8, 0x15, 0xc4, 0x80, 0x0b, 0xbc,
553 0x29, 0x3c, 0xf3, 0x95, 0x98, 0xcd, 0x8f, 0x35,
554 0xbc, 0xa5, 0x3e, 0xfc, 0xd4, 0x13, 0x9e, 0xde,
555 0x4f, 0xce, 0x71, 0x9d, 0x09, 0xad, 0xf2, 0x80,
556 0x6b, 0x65, 0x7f, 0x03, 0x00, 0x14, 0x7c, 0x15,
557 0x85, 0x40, 0x6d, 0x70, 0xea, 0xdc, 0xb3, 0x63,
558 0x35, 0x4f, 0x4d, 0xe0, 0xd9, 0xd5, 0x3c, 0x58,
559 0x56, 0x23, 0x80, 0xe2, 0x36, 0xdd, 0x75, 0x1d,
560 0x94, 0x11, 0x41, 0x8e, 0xe0, 0x81, 0x8e, 0xcf,
561 0xe0, 0xe5, 0xf6, 0xde, 0xd1, 0xe7, 0x04, 0x12,
562 0x79, 0x92, 0x2b, 0x71, 0x2a, 0x79, 0x8b, 0x7c,
563 0x44, 0x79, 0x16, 0x30, 0x4e, 0xf4, 0xf6, 0x9b,
564 0xb7, 0x40, 0xa3, 0x5a, 0xa7, 0x69, 0x3e, 0xc1,
565 0x3a, 0x04, 0xd0, 0x88, 0xa0, 0x3b, 0xdd, 0xc6,
566 0x9e, 0x7e, 0x1e, 0x1e, 0x8f, 0x44, 0xf7, 0x73,
567 0x67, 0x1e, 0x1a, 0x78, 0xfa, 0x62, 0xf4, 0xa9,
568 0xa8, 0xc6, 0x5b, 0xb8, 0xfa, 0x06, 0x7d, 0x5e,
569 0x38, 0x1c, 0x9a, 0x39, 0xe9, 0x39, 0x98, 0x22,
570 0x0b, 0xa7, 0xac, 0x0b, 0xf3, 0xbc, 0xf1, 0xeb,
571 0x8c, 0x81, 0xe3, 0x48, 0x8a, 0xed, 0x42, 0xc2,
572 0x38, 0xcf, 0x3e, 0xda, 0xd2, 0x89, 0x8d, 0x9c,
573 0x53, 0xb5, 0x2f, 0x41, 0x01, 0x26, 0x84, 0x9c,
574 0xa3, 0x56, 0xf6, 0x49, 0xc7, 0xd4, 0x9f, 0x93,
575 0x1b, 0x96, 0x49, 0x5e, 0xad, 0xb3, 0x84, 0x1f,
576 0x3c, 0xa4, 0xe0, 0x9b, 0xd1, 0x90, 0xbc, 0x38,
577 0x6c, 0xdd, 0x95, 0x4d, 0x9d, 0xb1, 0x71, 0x57,
578 0x2d, 0x34, 0xe8, 0xb8, 0x42, 0xc7, 0x99, 0x03,
579 0xc7, 0x07, 0x30, 0x65, 0x91, 0x55, 0xd5, 0x90,
580 0x70, 0x97, 0x37, 0x68, 0xd4, 0x11, 0xf9, 0xe8,
581 0xce, 0xec, 0xdc, 0x34, 0xd5, 0xd3, 0xb7, 0xc4,
582 0xb8, 0x97, 0x05, 0x92, 0xad, 0xf8, 0xe2, 0x36,
583 0x64, 0x41, 0xc9, 0xc5, 0x41, 0x77, 0x52, 0xd7,
584 0x2c, 0xa5, 0x24, 0x2f, 0xd9, 0x34, 0x0b, 0x47,
585 0x35, 0xa7, 0x28, 0x8b, 0xc5, 0xcd, 0xe9, 0x46,
586 0xac, 0x39, 0x94, 0x3c, 0x10, 0xc6, 0x29, 0x73,
587 0x0e, 0x0e, 0x5d, 0xe0, 0x71, 0x03, 0x8a, 0x72,
588 0x0e, 0x26, 0xb0, 0x7d, 0x84, 0xed, 0x95, 0x23,
589 0x49, 0x5a, 0x45, 0x83, 0x45, 0x60, 0x11, 0x4a,
590 0x46, 0x31, 0xd4, 0xd8, 0x16, 0x54, 0x98, 0x58,
591 0xed, 0x6d, 0xcc, 0x5d, 0xd6, 0x50, 0x61, 0x9f,
592 0x9d, 0xc5, 0x3e, 0x9d, 0x32, 0x47, 0xde, 0x96,
593 0xe1, 0x5d, 0xd8, 0xf8, 0xb4, 0x69, 0x6f, 0xb9,
594 0x15, 0x90, 0x57, 0x7a, 0xf6, 0xad, 0xb0, 0x5b,
595 0xf5, 0xa6, 0x36, 0x94, 0xfd, 0x84, 0xce, 0x1c,
596 0x0f, 0x4b, 0xd0, 0xc2, 0x5b, 0x6b, 0x56, 0xef,
597 0x73, 0x93, 0x0b, 0xc3, 0xee, 0xd9, 0xcf, 0xd3,
598 0xa4, 0x22, 0x58, 0xcd, 0x50, 0x6e, 0x65, 0xf4,
599 0xe9, 0xb7, 0x71, 0xaf, 0x4b, 0xb3, 0xb6, 0x2f,
600 0x0f, 0x0e, 0x3b, 0xc9, 0x85, 0x14, 0xf5, 0x17,
601 0xe8, 0x7a, 0x3a, 0xbf, 0x5f, 0x5e, 0xf8, 0x18,
602 0x48, 0xa6, 0x72, 0xab, 0x06, 0x95, 0xe9, 0xc8,
603 0xa7, 0xf4, 0x32, 0x44, 0x04, 0x0c, 0x84, 0x98,
604 0x73, 0xe3, 0x89, 0x8d, 0x5f, 0x7e, 0x4a, 0x42,
605 0x8f, 0xc5, 0x28, 0xb1, 0x82, 0xef, 0x1c, 0x97,
606 0x31, 0x3b, 0x4d, 0xe0, 0x0e, 0x10, 0x10, 0x97,
607 0x93, 0x49, 0x78, 0x2f, 0x0d, 0x86, 0x8b, 0xa1,
608 0x53, 0xa9, 0x81, 0x20, 0x79, 0xe7, 0x07, 0x77,
609 0xb6, 0xac, 0x5e, 0xd2, 0x05, 0xcd, 0xe9, 0xdb,
610 0x8a, 0x94, 0x82, 0x8a, 0x23, 0xb9, 0x3d, 0x1c,
611 0xa9, 0x7d, 0x72, 0x4a, 0xed, 0x33, 0xa3, 0xdb,
612 0x21, 0xa7, 0x86, 0x33, 0x45, 0xa5, 0xaa, 0x56,
613 0x45, 0xb5, 0x83, 0x29, 0x40, 0x47, 0x79, 0x04,
614 0x6e, 0xb9, 0x95, 0xd0, 0x81, 0x77, 0x2d, 0x48,
615 0x1e, 0xfe, 0xc3, 0xc2, 0x1e, 0xe5, 0xf2, 0xbe,
616 0xfd, 0x3b, 0x94, 0x9f, 0xc4, 0xc4, 0x26, 0x9d,
617 0xe4, 0x66, 0x1e, 0x19, 0xee, 0x6c, 0x79, 0x97,
618 0x11, 0x31, 0x4b, 0x0d, 0x01, 0xcb, 0xde, 0xa8,
619 0xf6, 0x6d, 0x7c, 0x39, 0x46, 0x4e, 0x7e, 0x3f,
620 0x94, 0x17, 0xdf, 0xa1, 0x7d, 0xd9, 0x1c, 0x8e,
621 0xbc, 0x7d, 0x33, 0x7d, 0xe3, 0x12, 0x40, 0xca,
622 0xab, 0x37, 0x11, 0x46, 0xd4, 0xae, 0xef, 0x44,
623 0xa2, 0xb3, 0x6a, 0x66, 0x0e, 0x0c, 0x90, 0x7f,
624 0xdf, 0x5c, 0x66, 0x5f, 0xf2, 0x94, 0x9f, 0xa6,
625 0x73, 0x4f, 0xeb, 0x0d, 0xad, 0xbf, 0xc0, 0x63,
626 0x5c, 0xdc, 0x46, 0x51, 0xe8, 0x8e, 0x90, 0x19,
627 0xa8, 0xa4, 0x3c, 0x91, 0x79, 0xfa, 0x7e, 0x58,
628 0x85, 0x13, 0x55, 0xc5, 0x19, 0x82, 0x37, 0x1b,
629 0x0a, 0x02, 0x1f, 0x99, 0x6b, 0x18, 0xf1, 0x28,
630 0x08, 0xa2, 0x73, 0xb8, 0x0f, 0x2e, 0xcd, 0xbf,
631 0xf3, 0x86, 0x7f, 0xea, 0xef, 0xd0, 0xbb, 0xa6,
632 0x21, 0xdf, 0x49, 0x73, 0x51, 0xcc, 0x36, 0xd3,
633 0x3e, 0xa0, 0xf8, 0x44, 0xdf, 0xd3, 0xa6, 0xbe,
634 0x8a, 0xd4, 0x57, 0xdd, 0x72, 0x94, 0x61, 0x0f,
635 0x82, 0xd1, 0x07, 0xb8, 0x7c, 0x18, 0x83, 0xdf,
636 0x3a, 0xe5, 0x50, 0x6a, 0x82, 0x20, 0xac, 0xa9,
637 0xa8, 0xff, 0xd9, 0xf3, 0x77, 0x33, 0x5a, 0x9e,
638 0x7f, 0x6d, 0xfe, 0x5d, 0x33, 0x41, 0x42, 0xe7,
639 0x6c, 0x19, 0xe0, 0x44, 0x8a, 0x15, 0xf6, 0x70,
640 0x98, 0xb7, 0x68, 0x4d, 0xfa, 0x97, 0x39, 0xb0,
641 0x8e, 0xe8, 0x84, 0x8b, 0x75, 0x30, 0xb7, 0x7d,
642 0x92, 0x69, 0x20, 0x9c, 0x81, 0xfb, 0x4b, 0xf4,
643 0x01, 0x50, 0xeb, 0xce, 0x0c, 0x1c, 0x6c, 0xb5,
644 0x4a, 0xd7, 0x27, 0x0c, 0xce, 0xbb, 0xe5, 0x85,
645 0xf0, 0xb6, 0xee, 0xd5, 0x70, 0xdd, 0x3b, 0xfc,
646 0xd4, 0x99, 0xf1, 0x33, 0xdd, 0x8b, 0xc4, 0x2f,
647 0xae, 0xab, 0x74, 0x96, 0x32, 0xc7, 0x4c, 0x56,
648 0x3c, 0x89, 0x0f, 0x96, 0x0b, 0x42, 0xc0, 0xcb,
649 0xee, 0x0f, 0x0b, 0x8c, 0xfb, 0x7e, 0x47, 0x7b,
650 0x64, 0x48, 0xfd, 0xb2, 0x00, 0x80, 0x89, 0xa5,
651 0x13, 0x55, 0x62, 0xfc, 0x8f, 0xe2, 0x42, 0x03,
652 0xb7, 0x4e, 0x2a, 0x79, 0xb4, 0x82, 0xea, 0x23,
653 0x49, 0xda, 0xaf, 0x52, 0x63, 0x1e, 0x60, 0x03,
654 0x89, 0x06, 0x44, 0x46, 0x08, 0xc3, 0xc4, 0x87,
655 0x70, 0x2e, 0xda, 0x94, 0xad, 0x6b, 0xe0, 0xe4,
656 0xd1, 0x8a, 0x06, 0xc2, 0xa8, 0xc0, 0xa7, 0x43,
657 0x3c, 0x47, 0x52, 0x0e, 0xc3, 0x77, 0x81, 0x11,
658 0x67, 0x0e, 0xa0, 0x70, 0x04, 0x47, 0x29, 0x40,
659 0x86, 0x0d, 0x34, 0x56, 0xa7, 0xc9, 0x35, 0x59,
660 0x68, 0xdc, 0x93, 0x81, 0x70, 0xee, 0x86, 0xd9,
661 0x80, 0x06, 0x40, 0x4f, 0x1a, 0x0d, 0x40, 0x30,
662 0x0b, 0xcb, 0x96, 0x47, 0xc1, 0xb7, 0x52, 0xfd,
663 0x56, 0xe0, 0x72, 0x4b, 0xfb, 0xbd, 0x92, 0x45,
664 0x61, 0x71, 0xc2, 0x33, 0x11, 0xbf, 0x52, 0x83,
665 0x79, 0x26, 0xe0, 0x49, 0x6b, 0xb7, 0x05, 0x8b,
666 0xe8, 0x0e, 0x87, 0x31, 0xd7, 0x9d, 0x8a, 0xf5,
667 0xc0, 0x5f, 0x2e, 0x58, 0x4a, 0xdb, 0x11, 0xb3,
668 0x6c, 0x30, 0x2a, 0x46, 0x19, 0xe3, 0x27, 0x84,
669 0x1f, 0x63, 0x6e, 0xf6, 0x57, 0xc7, 0xc9, 0xd8,
670 0x5e, 0xba, 0xb3, 0x87, 0xd5, 0x83, 0x26, 0x34,
671 0x21, 0x9e, 0x65, 0xde, 0x42, 0xd3, 0xbe, 0x7b,
672 0xbc, 0x91, 0x71, 0x44, 0x4d, 0x99, 0x3b, 0x31,
673 0xe5, 0x3f, 0x11, 0x4e, 0x7f, 0x13, 0x51, 0x3b,
674 0xae, 0x79, 0xc9, 0xd3, 0x81, 0x8e, 0x25, 0x40,
675 0x10, 0xfc, 0x07, 0x1e, 0xf9, 0x7b, 0x9a, 0x4b,
676 0x6c, 0xe3, 0xb3, 0xad, 0x1a, 0x0a, 0xdd, 0x9e,
677 0x59, 0x0c, 0xa2, 0xcd, 0xae, 0x48, 0x4a, 0x38,
678 0x5b, 0x47, 0x41, 0x94, 0x65, 0x6b, 0xbb, 0xeb,
679 0x5b, 0xe3, 0xaf, 0x07, 0x5b, 0xd4, 0x4a, 0xa2,
680 0xc9, 0x5d, 0x2f, 0x64, 0x03, 0xd7, 0x3a, 0x2c,
681 0x6e, 0xce, 0x76, 0x95, 0xb4, 0xb3, 0xc0, 0xf1,
682 0xe2, 0x45, 0x73, 0x7a, 0x5c, 0xab, 0xc1, 0xfc,
683 0x02, 0x8d, 0x81, 0x29, 0xb3, 0xac, 0x07, 0xec,
684 0x40, 0x7d, 0x45, 0xd9, 0x7a, 0x59, 0xee, 0x34,
685 0xf0, 0xe9, 0xd5, 0x7b, 0x96, 0xb1, 0x3d, 0x95,
686 0xcc, 0x86, 0xb5, 0xb6, 0x04, 0x2d, 0xb5, 0x92,
687 0x7e, 0x76, 0xf4, 0x06, 0xa9, 0xa3, 0x12, 0x0f,
688 0xb1, 0xaf, 0x26, 0xba, 0x7c, 0xfc, 0x7e, 0x1c,
689 0xbc, 0x2c, 0x49, 0x97, 0x53, 0x60, 0x13, 0x0b,
690 0xa6, 0x61, 0x83, 0x89, 0x42, 0xd4, 0x17, 0x0c,
691 0x6c, 0x26, 0x52, 0xc3, 0xb3, 0xd4, 0x67, 0xf5,
692 0xe3, 0x04, 0xb7, 0xf4, 0xcb, 0x80, 0xb8, 0xcb,
693 0x77, 0x56, 0x3e, 0xaa, 0x57, 0x54, 0xee, 0xb4,
694 0x2c, 0x67, 0xcf, 0xf2, 0xdc, 0xbe, 0x55, 0xf9,
695 0x43, 0x1f, 0x6e, 0x22, 0x97, 0x67, 0x7f, 0xc4,
696 0xef, 0xb1, 0x26, 0x31, 0x1e, 0x27, 0xdf, 0x41,
697 0x80, 0x47, 0x6c, 0xe2, 0xfa, 0xa9, 0x8c, 0x2a,
698 0xf6, 0xf2, 0xab, 0xf0, 0x15, 0xda, 0x6c, 0xc8,
699 0xfe, 0xb5, 0x23, 0xde, 0xa9, 0x05, 0x3f, 0x06,
700 0x54, 0x4c, 0xcd, 0xe1, 0xab, 0xfc, 0x0e, 0x62,
701 0x33, 0x31, 0x73, 0x2c, 0x76, 0xcb, 0xb4, 0x47,
702 0x1e, 0x20, 0xad, 0xd8, 0xf2, 0x31, 0xdd, 0xc4,
703 0x8b, 0x0c, 0x77, 0xbe, 0xe1, 0x8b, 0x26, 0x00,
704 0x02, 0x58, 0xd6, 0x8d, 0xef, 0xad, 0x74, 0x67,
705 0xab, 0x3f, 0xef, 0xcb, 0x6f, 0xb0, 0xcc, 0x81,
706 0x44, 0x4c, 0xaf, 0xe9, 0x49, 0x4f, 0xdb, 0xa0,
707 0x25, 0xa4, 0xf0, 0x89, 0xf1, 0xbe, 0xd8, 0x10,
708 0xff, 0xb1, 0x3b, 0x4b, 0xfa, 0x98, 0xf5, 0x79,
709 0x6d, 0x1e, 0x69, 0x4d, 0x57, 0xb1, 0xc8, 0x19,
710 0x1b, 0xbd, 0x1e, 0x8c, 0x84, 0xb7, 0x7b, 0xe8,
711 0xd2, 0x2d, 0x09, 0x41, 0x41, 0x37, 0x3d, 0xb1,
712 0x6f, 0x26, 0x5d, 0x71, 0x16, 0x3d, 0xb7, 0x83,
713 0x27, 0x2c, 0xa7, 0xb6, 0x50, 0xbd, 0x91, 0x86,
714 0xab, 0x24, 0xa1, 0x38, 0xfd, 0xea, 0x71, 0x55,
715 0x7e, 0x9a, 0x07, 0x77, 0x4b, 0xfa, 0x61, 0x66,
716 0x20, 0x1e, 0x28, 0x95, 0x18, 0x1b, 0xa4, 0xa0,
717 0xfd, 0xc0, 0x89, 0x72, 0x43, 0xd9, 0x3b, 0x49,
718 0x5a, 0x3f, 0x9d, 0xbf, 0xdb, 0xb4, 0x46, 0xea,
719 0x42, 0x01, 0x77, 0x23, 0x68, 0x95, 0xb6, 0x24,
720 0xb3, 0xa8, 0x6c, 0x28, 0x3b, 0x11, 0x40, 0x7e,
721 0x18, 0x65, 0x6d, 0xd8, 0x24, 0x42, 0x7d, 0x88,
722 0xc0, 0x52, 0xd9, 0x05, 0xe4, 0x95, 0x90, 0x87,
723 0x8c, 0xf4, 0xd0, 0x6b, 0xb9, 0x83, 0x99, 0x34,
724 0x6d, 0xfe, 0x54, 0x40, 0x94, 0x52, 0x21, 0x4f,
725 0x14, 0x25, 0xc5, 0xd6, 0x5e, 0x95, 0xdc, 0x0a,
726 0x2b, 0x89, 0x20, 0x11, 0x84, 0x48, 0xd6, 0x3a,
727 0xcd, 0x5c, 0x24, 0xad, 0x62, 0xe3, 0xb1, 0x93,
728 0x25, 0x8d, 0xcd, 0x7e, 0xfc, 0x27, 0xa3, 0x37,
729 0xfd, 0x84, 0xfc, 0x1b, 0xb2, 0xf1, 0x27, 0x38,
730 0x5a, 0xb7, 0xfc, 0xf2, 0xfa, 0x95, 0x66, 0xd4,
731 0xfb, 0xba, 0xa7, 0xd7, 0xa3, 0x72, 0x69, 0x48,
732 0x48, 0x8c, 0xeb, 0x28, 0x89, 0xfe, 0x33, 0x65,
733 0x5a, 0x36, 0x01, 0x7e, 0x06, 0x79, 0x0a, 0x09,
734 0x3b, 0x74, 0x11, 0x9a, 0x6e, 0xbf, 0xd4, 0x9e,
735 0x58, 0x90, 0x49, 0x4f, 0x4d, 0x08, 0xd4, 0xe5,
736 0x4a, 0x09, 0x21, 0xef, 0x8b, 0xb8, 0x74, 0x3b,
737 0x91, 0xdd, 0x36, 0x85, 0x60, 0x2d, 0xfa, 0xd4,
738 0x45, 0x7b, 0x45, 0x53, 0xf5, 0x47, 0x87, 0x7e,
739 0xa6, 0x37, 0xc8, 0x78, 0x7a, 0x68, 0x9d, 0x8d,
740 0x65, 0x2c, 0x0e, 0x91, 0x5c, 0xa2, 0x60, 0xf0,
741 0x8e, 0x3f, 0xe9, 0x1a, 0xcd, 0xaa, 0xe7, 0xd5,
742 0x77, 0x18, 0xaf, 0xc9, 0xbc, 0x18, 0xea, 0x48,
743 0x1b, 0xfb, 0x22, 0x48, 0x70, 0x16, 0x29, 0x9e,
744 0x5b, 0xc1, 0x2c, 0x66, 0x23, 0xbc, 0xf0, 0x1f,
745 0xef, 0xaf, 0xe4, 0xd6, 0x04, 0x19, 0x82, 0x7a,
746 0x0b, 0xba, 0x4b, 0x46, 0xb1, 0x6a, 0x85, 0x5d,
747 0xb4, 0x73, 0xd6, 0x21, 0xa1, 0x71, 0x60, 0x14,
748 0xee, 0x0a, 0x77, 0xc4, 0x66, 0x2e, 0xf9, 0x69,
749 0x30, 0xaf, 0x41, 0x0b, 0xc8, 0x83, 0x3c, 0x53,
750 0x99, 0x19, 0x27, 0x46, 0xf7, 0x41, 0x6e, 0x56,
751 0xdc, 0x94, 0x28, 0x67, 0x4e, 0xb7, 0x25, 0x48,
752 0x8a, 0xc2, 0xe0, 0x60, 0x96, 0xcc, 0x18, 0xf4,
753 0x84, 0xdd, 0xa7, 0x5e, 0x3e, 0x05, 0x0b, 0x26,
754 0x26, 0xb2, 0x5c, 0x1f, 0x57, 0x1a, 0x04, 0x7e,
755 0x6a, 0xe3, 0x2f, 0xb4, 0x35, 0xb6, 0x38, 0x40,
756 0x40, 0xcd, 0x6f, 0x87, 0x2e, 0xef, 0xa3, 0xd7,
757 0xa9, 0xc2, 0xe8, 0x0d, 0x27, 0xdf, 0x44, 0x62,
758 0x99, 0xa0, 0xfc, 0xcf, 0x81, 0x78, 0xcb, 0xfe,
759 0xe5, 0xa0, 0x03, 0x4e, 0x6c, 0xd7, 0xf4, 0xaf,
760 0x7a, 0xbb, 0x61, 0x82, 0xfe, 0x71, 0x89, 0xb2,
761 0x22, 0x7c, 0x8e, 0x83, 0x04, 0xce, 0xf6, 0x5d,
762 0x84, 0x8f, 0x95, 0x6a, 0x7f, 0xad, 0xfd, 0x32,
763 0x9c, 0x5e, 0xe4, 0x9c, 0x89, 0x60, 0x54, 0xaa,
764 0x96, 0x72, 0xd2, 0xd7, 0x36, 0x85, 0xa9, 0x45,
765 0xd2, 0x2a, 0xa1, 0x81, 0x49, 0x6f, 0x7e, 0x04,
766 0xfa, 0xe2, 0xfe, 0x90, 0x26, 0x77, 0x5a, 0x33,
767 0xb8, 0x04, 0x9a, 0x7a, 0xe6, 0x4c, 0x4f, 0xad,
768 0x72, 0x96, 0x08, 0x28, 0x58, 0x13, 0xf8, 0xc4,
769 0x1c, 0xf0, 0xc3, 0x45, 0x95, 0x49, 0x20, 0x8c,
770 0x9f, 0x39, 0x70, 0xe1, 0x77, 0xfe, 0xd5, 0x4b,
771 0xaf, 0x86, 0xda, 0xef, 0x22, 0x06, 0x83, 0x36,
772 0x29, 0x12, 0x11, 0x40, 0xbc, 0x3b, 0x86, 0xaa,
773 0xaa, 0x65, 0x60, 0xc3, 0x80, 0xca, 0xed, 0xa9,
774 0xf3, 0xb0, 0x79, 0x96, 0xa2, 0x55, 0x27, 0x28,
775 0x55, 0x73, 0x26, 0xa5, 0x50, 0xea, 0x92, 0x4b,
776 0x3c, 0x5c, 0x82, 0x33, 0xf0, 0x01, 0x3f, 0x03,
777 0xc1, 0x08, 0x05, 0xbf, 0x98, 0xf4, 0x9b, 0x6d,
778 0xa5, 0xa8, 0xb4, 0x82, 0x0c, 0x06, 0xfa, 0xff,
779 0x2d, 0x08, 0xf3, 0x05, 0x4f, 0x57, 0x2a, 0x39,
780 0xd4, 0x83, 0x0d, 0x75, 0x51, 0xd8, 0x5b, 0x1b,
781 0xd3, 0x51, 0x5a, 0x32, 0x2a, 0x9b, 0x32, 0xb2,
782 0xf2, 0xa4, 0x96, 0x12, 0xf2, 0xae, 0x40, 0x34,
783 0x67, 0xa8, 0xf5, 0x44, 0xd5, 0x35, 0x53, 0xfe,
784 0xa3, 0x60, 0x96, 0x63, 0x0f, 0x1f, 0x6e, 0xb0,
785 0x5a, 0x42, 0xa6, 0xfc, 0x51, 0x0b, 0x60, 0x27,
786 0xbc, 0x06, 0x71, 0xed, 0x65, 0x5b, 0x23, 0x86,
787 0x4a, 0x07, 0x3b, 0x22, 0x07, 0x46, 0xe6, 0x90,
788 0x3e, 0xf3, 0x25, 0x50, 0x1b, 0x4c, 0x7f, 0x03,
789 0x08, 0xa8, 0x36, 0x6b, 0x87, 0xe5, 0xe3, 0xdb,
790 0x9a, 0x38, 0x83, 0xff, 0x9f, 0x1a, 0x9f, 0x57,
791 0xa4, 0x2a, 0xf6, 0x37, 0xbc, 0x1a, 0xff, 0xc9,
792 0x1e, 0x35, 0x0c, 0xc3, 0x7c, 0xa3, 0xb2, 0xe5,
793 0xd2, 0xc6, 0xb4, 0x57, 0x47, 0xe4, 0x32, 0x16,
794 0x6d, 0xa9, 0xae, 0x64, 0xe6, 0x2d, 0x8d, 0xc5,
795 0x8d, 0x50, 0x8e, 0xe8, 0x1a, 0x22, 0x34, 0x2a,
796 0xd9, 0xeb, 0x51, 0x90, 0x4a, 0xb1, 0x41, 0x7d,
797 0x64, 0xf9, 0xb9, 0x0d, 0xf6, 0x23, 0x33, 0xb0,
798 0x33, 0xf4, 0xf7, 0x3f, 0x27, 0x84, 0xc6, 0x0f,
799 0x54, 0xa5, 0xc0, 0x2e, 0xec, 0x0b, 0x3a, 0x48,
800 0x6e, 0x80, 0x35, 0x81, 0x43, 0x9b, 0x90, 0xb1,
801 0xd0, 0x2b, 0xea, 0x21, 0xdc, 0xda, 0x5b, 0x09,
802 0xf4, 0xcc, 0x10, 0xb4, 0xc7, 0xfe, 0x79, 0x51,
803 0xc3, 0xc5, 0xac, 0x88, 0x74, 0x84, 0x0b, 0x4b,
804 0xca, 0x79, 0x16, 0x29, 0xfb, 0x69, 0x54, 0xdf,
805 0x41, 0x7e, 0xe9, 0xc7, 0x8e, 0xea, 0xa5, 0xfe,
806 0xfc, 0x76, 0x0e, 0x90, 0xc4, 0x92, 0x38, 0xad,
807 0x7b, 0x48, 0xe6, 0x6e, 0xf7, 0x21, 0xfd, 0x4e,
808 0x93, 0x0a, 0x7b, 0x41, 0x83, 0x68, 0xfb, 0x57,
809 0x51, 0x76, 0x34, 0xa9, 0x6c, 0x00, 0xaa, 0x4f,
810 0x66, 0x65, 0x98, 0x4a, 0x4f, 0xa3, 0xa0, 0xef,
811 0x69, 0x3f, 0xe3, 0x1c, 0x92, 0x8c, 0xfd, 0xd8,
812 0xe8, 0xde, 0x7c, 0x7f, 0x3e, 0x84, 0x8e, 0x69,
813 0x3c, 0xf1, 0xf2, 0x05, 0x46, 0xdc, 0x2f, 0x9d,
814 0x5e, 0x6e, 0x4c, 0xfb, 0xb5, 0x99, 0x2a, 0x59,
815 0x63, 0xc1, 0x34, 0xbc, 0x57, 0xc0, 0x0d, 0xb9,
816 0x61, 0x25, 0xf3, 0x33, 0x23, 0x51, 0xb6, 0x0d,
817 0x07, 0xa6, 0xab, 0x94, 0x4a, 0xb7, 0x2a, 0xea,
818 0xee, 0xac, 0xa3, 0xc3, 0x04, 0x8b, 0x0e, 0x56,
819 0xfe, 0x44, 0xa7, 0x39, 0xe2, 0xed, 0xed, 0xb4,
820 0x22, 0x2b, 0xac, 0x12, 0x32, 0x28, 0x91, 0xd8,
821 0xa5, 0xab, 0xff, 0x5f, 0xe0, 0x4b, 0xda, 0x78,
822 0x17, 0xda, 0xf1, 0x01, 0x5b, 0xcd, 0xe2, 0x5f,
823 0x50, 0x45, 0x73, 0x2b, 0xe4, 0x76, 0x77, 0xf4,
824 0x64, 0x1d, 0x43, 0xfb, 0x84, 0x7a, 0xea, 0x91,
825 0xae, 0xf9, 0x9e, 0xb7, 0xb4, 0xb0, 0x91, 0x5f,
826 0x16, 0x35, 0x9a, 0x11, 0xb8, 0xc7, 0xc1, 0x8c,
827 0xc6, 0x10, 0x8d, 0x2f, 0x63, 0x4a, 0xa7, 0x57,
828 0x3a, 0x51, 0xd6, 0x32, 0x2d, 0x64, 0x72, 0xd4,
829 0x66, 0xdc, 0x10, 0xa6, 0x67, 0xd6, 0x04, 0x23,
830 0x9d, 0x0a, 0x11, 0x77, 0xdd, 0x37, 0x94, 0x17,
831 0x3c, 0xbf, 0x8b, 0x65, 0xb0, 0x2e, 0x5e, 0x66,
832 0x47, 0x64, 0xac, 0xdd, 0xf0, 0x84, 0xfd, 0x39,
833 0xfa, 0x15, 0x5d, 0xef, 0xae, 0xca, 0xc1, 0x36,
834 0xa7, 0x5c, 0xbf, 0xc7, 0x08, 0xc2, 0x66, 0x00,
835 0x74, 0x74, 0x4e, 0x27, 0x3f, 0x55, 0x8a, 0xb7,
836 0x38, 0x66, 0x83, 0x6d, 0xcf, 0x99, 0x9e, 0x60,
837 0x8f, 0xdd, 0x2e, 0x62, 0x22, 0x0e, 0xef, 0x0c,
838 0x98, 0xa7, 0x85, 0x74, 0x3b, 0x9d, 0xec, 0x9e,
839 0xa9, 0x19, 0x72, 0xa5, 0x7f, 0x2c, 0x39, 0xb7,
840 0x7d, 0xb7, 0xf1, 0x12, 0x65, 0x27, 0x4b, 0x5a,
841 0xde, 0x17, 0xfe, 0xad, 0x44, 0xf3, 0x20, 0x4d,
842 0xfd, 0xe4, 0x1f, 0xb5, 0x81, 0xb0, 0x36, 0x37,
843 0x08, 0x6f, 0xc3, 0x0c, 0xe9, 0x85, 0x98, 0x82,
844 0xa9, 0x62, 0x0c, 0xc4, 0x97, 0xc0, 0x50, 0xc8,
845 0xa7, 0x3c, 0x50, 0x9f, 0x43, 0xb9, 0xcd, 0x5e,
846 0x4d, 0xfa, 0x1c, 0x4b, 0x0b, 0xa9, 0x98, 0x85,
847 0x38, 0x92, 0xac, 0x8d, 0xe4, 0xad, 0x9b, 0x98,
848 0xab, 0xd9, 0x38, 0xac, 0x62, 0x52, 0xa3, 0x22,
849 0x63, 0x0f, 0xbf, 0x95, 0x48, 0xdf, 0x69, 0xe7,
850 0x8b, 0x33, 0xd5, 0xb2, 0xbd, 0x05, 0x49, 0x49,
851 0x9d, 0x57, 0x73, 0x19, 0x33, 0xae, 0xfa, 0x33,
852 0xf1, 0x19, 0xa8, 0x80, 0xce, 0x04, 0x9f, 0xbc,
853 0x1d, 0x65, 0x82, 0x1b, 0xe5, 0x3a, 0x51, 0xc8,
854 0x1c, 0x21, 0xe3, 0x5d, 0xf3, 0x7d, 0x9b, 0x2f,
855 0x2c, 0x1d, 0x4a, 0x7f, 0x9b, 0x68, 0x35, 0xa3,
856 0xb2, 0x50, 0xf7, 0x62, 0x79, 0xcd, 0xf4, 0x98,
857 0x4f, 0xe5, 0x63, 0x7c, 0x3e, 0x45, 0x31, 0x8c,
858 0x16, 0xa0, 0x12, 0xc8, 0x58, 0xce, 0x39, 0xa6,
859 0xbc, 0x54, 0xdb, 0xc5, 0xe0, 0xd5, 0xba, 0xbc,
860 0xb9, 0x04, 0xf4, 0x8d, 0xe8, 0x2f, 0x15, 0x9d,
861};
862
863/* 100 test cases */
864static struct crc_test {
865 u32 crc; /* random starting crc */
866 u32 start; /* random 6 bit offset in buf */
867 u32 length; /* random 11 bit length of test */
868 u32 crc_le; /* expected crc32_le result */
869 u32 crc_be; /* expected crc32_be result */
870 u32 crc32c_le; /* expected crc32c_le result */
871} const test[] __initconst =
872{
873 {0x674bf11d, 0x00000038, 0x00000542, 0x0af6d466, 0xd8b6e4c1, 0xf6e93d6c},
874 {0x35c672c6, 0x0000003a, 0x000001aa, 0xc6d3dfba, 0x28aaf3ad, 0x0fe92aca},
875 {0x496da28e, 0x00000039, 0x000005af, 0xd933660f, 0x5d57e81f, 0x52e1ebb8},
876 {0x09a9b90e, 0x00000027, 0x000001f8, 0xb45fe007, 0xf45fca9a, 0x0798af9a},
877 {0xdc97e5a9, 0x00000025, 0x000003b6, 0xf81a3562, 0xe0126ba2, 0x18eb3152},
878 {0x47c58900, 0x0000000a, 0x000000b9, 0x8e58eccf, 0xf3afc793, 0xd00d08c7},
879 {0x292561e8, 0x0000000c, 0x00000403, 0xa2ba8aaf, 0x0b797aed, 0x8ba966bc},
880 {0x415037f6, 0x00000003, 0x00000676, 0xa17d52e8, 0x7f0fdf35, 0x11d694a2},
881 {0x3466e707, 0x00000026, 0x00000042, 0x258319be, 0x75c484a2, 0x6ab3208d},
882 {0xafd1281b, 0x00000023, 0x000002ee, 0x4428eaf8, 0x06c7ad10, 0xba4603c5},
883 {0xd3857b18, 0x00000028, 0x000004a2, 0x5c430821, 0xb062b7cb, 0xe6071c6f},
884 {0x1d825a8f, 0x0000002b, 0x0000050b, 0xd2c45f0c, 0xd68634e0, 0x179ec30a},
885 {0x5033e3bc, 0x0000000b, 0x00000078, 0xa3ea4113, 0xac6d31fb, 0x0903beb8},
886 {0x94f1fb5e, 0x0000000f, 0x000003a2, 0xfbfc50b1, 0x3cfe50ed, 0x6a7cb4fa},
887 {0xc9a0fe14, 0x00000009, 0x00000473, 0x5fb61894, 0x87070591, 0xdb535801},
888 {0x88a034b1, 0x0000001c, 0x000005ad, 0xc1b16053, 0x46f95c67, 0x92bed597},
889 {0xf0f72239, 0x00000020, 0x0000026d, 0xa6fa58f3, 0xf8c2c1dd, 0x192a3f1b},
890 {0xcc20a5e3, 0x0000003b, 0x0000067a, 0x7740185a, 0x308b979a, 0xccbaec1a},
891 {0xce589c95, 0x0000002b, 0x00000641, 0xd055e987, 0x40aae25b, 0x7eabae4d},
892 {0x78edc885, 0x00000035, 0x000005be, 0xa39cb14b, 0x035b0d1f, 0x28c72982},
893 {0x9d40a377, 0x0000003b, 0x00000038, 0x1f47ccd2, 0x197fbc9d, 0xc3cd4d18},
894 {0x703d0e01, 0x0000003c, 0x000006f1, 0x88735e7c, 0xfed57c5a, 0xbca8f0e7},
895 {0x776bf505, 0x0000000f, 0x000005b2, 0x5cc4fc01, 0xf32efb97, 0x713f60b3},
896 {0x4a3e7854, 0x00000027, 0x000004b8, 0x8d923c82, 0x0cbfb4a2, 0xebd08fd5},
897 {0x209172dd, 0x0000003b, 0x00000356, 0xb89e9c2b, 0xd7868138, 0x64406c59},
898 {0x3ba4cc5b, 0x0000002f, 0x00000203, 0xe51601a9, 0x5b2a1032, 0x7421890e},
899 {0xfc62f297, 0x00000000, 0x00000079, 0x71a8e1a2, 0x5d88685f, 0xe9347603},
900 {0x64280b8b, 0x00000016, 0x000007ab, 0x0fa7a30c, 0xda3a455f, 0x1bef9060},
901 {0x97dd724b, 0x00000033, 0x000007ad, 0x5788b2f4, 0xd7326d32, 0x34720072},
902 {0x61394b52, 0x00000035, 0x00000571, 0xc66525f1, 0xcabe7fef, 0x48310f59},
903 {0x29b4faff, 0x00000024, 0x0000006e, 0xca13751e, 0x993648e0, 0x783a4213},
904 {0x29bfb1dc, 0x0000000b, 0x00000244, 0x436c43f7, 0x429f7a59, 0x9e8efd41},
905 {0x86ae934b, 0x00000035, 0x00000104, 0x0760ec93, 0x9cf7d0f4, 0xfc3d34a5},
906 {0xc4c1024e, 0x0000002e, 0x000006b1, 0x6516a3ec, 0x19321f9c, 0x17a52ae2},
907 {0x3287a80a, 0x00000026, 0x00000496, 0x0b257eb1, 0x754ebd51, 0x886d935a},
908 {0xa4db423e, 0x00000023, 0x0000045d, 0x9b3a66dc, 0x873e9f11, 0xeaaeaeb2},
909 {0x7a1078df, 0x00000015, 0x0000014a, 0x8c2484c5, 0x6a628659, 0x8e900a4b},
910 {0x6048bd5b, 0x00000006, 0x0000006a, 0x897e3559, 0xac9961af, 0xd74662b1},
911 {0xd8f9ea20, 0x0000003d, 0x00000277, 0x60eb905b, 0xed2aaf99, 0xd26752ba},
912 {0xea5ec3b4, 0x0000002a, 0x000004fe, 0x869965dc, 0x6c1f833b, 0x8b1fcd62},
913 {0x2dfb005d, 0x00000016, 0x00000345, 0x6a3b117e, 0xf05e8521, 0xf54342fe},
914 {0x5a214ade, 0x00000020, 0x000005b6, 0x467f70be, 0xcb22ccd3, 0x5b95b988},
915 {0xf0ab9cca, 0x00000032, 0x00000515, 0xed223df3, 0x7f3ef01d, 0x2e1176be},
916 {0x91b444f9, 0x0000002e, 0x000007f8, 0x84e9a983, 0x5676756f, 0x66120546},
917 {0x1b5d2ddb, 0x0000002e, 0x0000012c, 0xba638c4c, 0x3f42047b, 0xf256a5cc},
918 {0xd824d1bb, 0x0000003a, 0x000007b5, 0x6288653b, 0x3a3ebea0, 0x4af1dd69},
919 {0x0470180c, 0x00000034, 0x000001f0, 0x9d5b80d6, 0x3de08195, 0x56f0a04a},
920 {0xffaa3a3f, 0x00000036, 0x00000299, 0xf3a82ab8, 0x53e0c13d, 0x74f6b6b2},
921 {0x6406cfeb, 0x00000023, 0x00000600, 0xa920b8e8, 0xe4e2acf4, 0x085951fd},
922 {0xb24aaa38, 0x0000003e, 0x000004a1, 0x657cc328, 0x5077b2c3, 0xc65387eb},
923 {0x58b2ab7c, 0x00000039, 0x000002b4, 0x3a17ee7e, 0x9dcb3643, 0x1ca9257b},
924 {0x3db85970, 0x00000006, 0x000002b6, 0x95268b59, 0xb9812c10, 0xfd196d76},
925 {0x857830c5, 0x00000003, 0x00000590, 0x4ef439d5, 0xf042161d, 0x5ef88339},
926 {0xe1fcd978, 0x0000003e, 0x000007d8, 0xae8d8699, 0xce0a1ef5, 0x2c3714d9},
927 {0xb982a768, 0x00000016, 0x000006e0, 0x62fad3df, 0x5f8a067b, 0x58576548},
928 {0x1d581ce8, 0x0000001e, 0x0000058b, 0xf0f5da53, 0x26e39eee, 0xfd7c57de},
929 {0x2456719b, 0x00000025, 0x00000503, 0x4296ac64, 0xd50e4c14, 0xd5fedd59},
930 {0xfae6d8f2, 0x00000000, 0x0000055d, 0x057fdf2e, 0x2a31391a, 0x1cc3b17b},
931 {0xcba828e3, 0x00000039, 0x000002ce, 0xe3f22351, 0x8f00877b, 0x270eed73},
932 {0x13d25952, 0x0000000a, 0x0000072d, 0x76d4b4cc, 0x5eb67ec3, 0x91ecbb11},
933 {0x0342be3f, 0x00000015, 0x00000599, 0xec75d9f1, 0x9d4d2826, 0x05ed8d0c},
934 {0xeaa344e0, 0x00000014, 0x000004d8, 0x72a4c981, 0x2064ea06, 0x0b09ad5b},
935 {0xbbb52021, 0x0000003b, 0x00000272, 0x04af99fc, 0xaf042d35, 0xf8d511fb},
936 {0xb66384dc, 0x0000001d, 0x000007fc, 0xd7629116, 0x782bd801, 0x5ad832cc},
937 {0x616c01b6, 0x00000022, 0x000002c8, 0x5b1dab30, 0x783ce7d2, 0x1214d196},
938 {0xce2bdaad, 0x00000016, 0x0000062a, 0x932535c8, 0x3f02926d, 0x5747218a},
939 {0x00fe84d7, 0x00000005, 0x00000205, 0x850e50aa, 0x753d649c, 0xde8f14de},
940 {0xbebdcb4c, 0x00000006, 0x0000055d, 0xbeaa37a2, 0x2d8c9eba, 0x3563b7b9},
941 {0xd8b1a02a, 0x00000010, 0x00000387, 0x5017d2fc, 0x503541a5, 0x071475d0},
942 {0x3b96cad2, 0x00000036, 0x00000347, 0x1d2372ae, 0x926cd90b, 0x54c79d60},
943 {0xc94c1ed7, 0x00000005, 0x0000038b, 0x9e9fdb22, 0x144a9178, 0x4c53eee6},
944 {0x1aad454e, 0x00000025, 0x000002b2, 0xc3f6315c, 0x5c7a35b3, 0x10137a3c},
945 {0xa4fec9a6, 0x00000000, 0x000006d6, 0x90be5080, 0xa4107605, 0xaa9d6c73},
946 {0x1bbe71e2, 0x0000001f, 0x000002fd, 0x4e504c3b, 0x284ccaf1, 0xb63d23e7},
947 {0x4201c7e4, 0x00000002, 0x000002b7, 0x7822e3f9, 0x0cc912a9, 0x7f53e9cf},
948 {0x23fddc96, 0x00000003, 0x00000627, 0x8a385125, 0x07767e78, 0x13c1cd83},
949 {0xd82ba25c, 0x00000016, 0x0000063e, 0x98e4148a, 0x283330c9, 0x49ff5867},
950 {0x786f2032, 0x0000002d, 0x0000060f, 0xf201600a, 0xf561bfcd, 0x8467f211},
951 {0xfebe4e1f, 0x0000002a, 0x000004f2, 0x95e51961, 0xfd80dcab, 0x3f9683b2},
952 {0x1a6e0a39, 0x00000008, 0x00000672, 0x8af6c2a5, 0x78dd84cb, 0x76a3f874},
953 {0x56000ab8, 0x0000000e, 0x000000e5, 0x36bacb8f, 0x22ee1f77, 0x863b702f},
954 {0x4717fe0c, 0x00000000, 0x000006ec, 0x8439f342, 0x5c8e03da, 0xdc6c58ff},
955 {0xd5d5d68e, 0x0000003c, 0x000003a3, 0x46fff083, 0x177d1b39, 0x0622cc95},
956 {0xc25dd6c6, 0x00000024, 0x000006c0, 0x5ceb8eb4, 0x892b0d16, 0xe85605cd},
957 {0xe9b11300, 0x00000023, 0x00000683, 0x07a5d59a, 0x6c6a3208, 0x31da5f06},
958 {0x95cd285e, 0x00000001, 0x00000047, 0x7b3a4368, 0x0202c07e, 0xa1f2e784},
959 {0xd9245a25, 0x0000001e, 0x000003a6, 0xd33c1841, 0x1936c0d5, 0xb07cc616},
960 {0x103279db, 0x00000006, 0x0000039b, 0xca09b8a0, 0x77d62892, 0xbf943b6c},
961 {0x1cba3172, 0x00000027, 0x000001c8, 0xcb377194, 0xebe682db, 0x2c01af1c},
962 {0x8f613739, 0x0000000c, 0x000001df, 0xb4b0bc87, 0x7710bd43, 0x0fe5f56d},
963 {0x1c6aa90d, 0x0000001b, 0x0000053c, 0x70559245, 0xda7894ac, 0xf8943b2d},
964 {0xaabe5b93, 0x0000003d, 0x00000715, 0xcdbf42fa, 0x0c3b99e7, 0xe4d89272},
965 {0xf15dd038, 0x00000006, 0x000006db, 0x6e104aea, 0x8d5967f2, 0x7c2f6bbb},
966 {0x584dd49c, 0x00000020, 0x000007bc, 0x36b6cfd6, 0xad4e23b2, 0xabbf388b},
967 {0x5d8c9506, 0x00000020, 0x00000470, 0x4c62378e, 0x31d92640, 0x1dca1f4e},
968 {0xb80d17b0, 0x00000032, 0x00000346, 0x22a5bb88, 0x9a7ec89f, 0x5c170e23},
969 {0xdaf0592e, 0x00000023, 0x000007b0, 0x3cab3f99, 0x9b1fdd99, 0xc0e9d672},
970 {0x4793cc85, 0x0000000d, 0x00000706, 0xe82e04f6, 0xed3db6b7, 0xc18bdc86},
971 {0x82ebf64e, 0x00000009, 0x000007c3, 0x69d590a9, 0x9efa8499, 0xa874fcdd},
972 {0xb18a0319, 0x00000026, 0x000007db, 0x1cf98dcc, 0x8fa9ad6a, 0x9dc0bb48},
973};
974
975#include <linux/time.h>
976
977static int __init crc32c_test(void)
978{
979 int i;
980 int errors = 0;
981 int bytes = 0;
982 struct timespec start, stop;
983 u64 nsec;
984 unsigned long flags;
985
986 /* keep static to prevent cache warming code from
987 * getting eliminated by the compiler */
988 static u32 crc;
989
990 /* pre-warm the cache */
991 for (i = 0; i < 100; i++) {
992 bytes += 2*test[i].length;
993
994 crc ^= __crc32c_le(test[i].crc, test_buf +
995 test[i].start, test[i].length);
996 }
997
998 /* reduce OS noise */
999 local_irq_save(flags);
1000 local_irq_disable();
1001
1002 getnstimeofday(&start);
1003 for (i = 0; i < 100; i++) {
1004 if (test[i].crc32c_le != __crc32c_le(test[i].crc, test_buf +
1005 test[i].start, test[i].length))
1006 errors++;
1007 }
1008 getnstimeofday(&stop);
1009
1010 local_irq_restore(flags);
1011 local_irq_enable();
1012
1013 nsec = stop.tv_nsec - start.tv_nsec +
1014 1000000000 * (stop.tv_sec - start.tv_sec);
1015
1016 pr_info("crc32c: CRC_LE_BITS = %d\n", CRC_LE_BITS);
1017
1018 if (errors)
1019 pr_warn("crc32c: %d self tests failed\n", errors);
1020 else {
1021 pr_info("crc32c: self tests passed, processed %d bytes in %lld nsec\n",
1022 bytes, nsec);
1023 }
1024
1025 return 0;
1026}
1027
1028static int __init crc32c_combine_test(void)
1029{
1030 int i, j;
1031 int errors = 0, runs = 0;
1032
1033 for (i = 0; i < 10; i++) {
1034 u32 crc_full;
1035
1036 crc_full = __crc32c_le(test[i].crc, test_buf + test[i].start,
1037 test[i].length);
1038 for (j = 0; j <= test[i].length; ++j) {
1039 u32 crc1, crc2;
1040 u32 len1 = j, len2 = test[i].length - j;
1041
1042 crc1 = __crc32c_le(test[i].crc, test_buf +
1043 test[i].start, len1);
1044 crc2 = __crc32c_le(0, test_buf + test[i].start +
1045 len1, len2);
1046
1047 if (!(crc_full == __crc32c_le_combine(crc1, crc2, len2) &&
1048 crc_full == test[i].crc32c_le))
1049 errors++;
1050 runs++;
1051 cond_resched();
1052 }
1053 }
1054
1055 if (errors)
1056 pr_warn("crc32c_combine: %d/%d self tests failed\n", errors, runs);
1057 else
1058 pr_info("crc32c_combine: %d self tests passed\n", runs);
1059
1060 return 0;
1061}
1062
1063static int __init crc32_test(void)
1064{
1065 int i;
1066 int errors = 0;
1067 int bytes = 0;
1068 struct timespec start, stop;
1069 u64 nsec;
1070 unsigned long flags;
1071
1072 /* keep static to prevent cache warming code from
1073 * getting eliminated by the compiler */
1074 static u32 crc;
1075
1076 /* pre-warm the cache */
1077 for (i = 0; i < 100; i++) {
1078 bytes += 2*test[i].length;
1079
1080 crc ^= crc32_le(test[i].crc, test_buf +
1081 test[i].start, test[i].length);
1082
1083 crc ^= crc32_be(test[i].crc, test_buf +
1084 test[i].start, test[i].length);
1085 }
1086
1087 /* reduce OS noise */
1088 local_irq_save(flags);
1089 local_irq_disable();
1090
1091 getnstimeofday(&start);
1092 for (i = 0; i < 100; i++) {
1093 if (test[i].crc_le != crc32_le(test[i].crc, test_buf +
1094 test[i].start, test[i].length))
1095 errors++;
1096
1097 if (test[i].crc_be != crc32_be(test[i].crc, test_buf +
1098 test[i].start, test[i].length))
1099 errors++;
1100 }
1101 getnstimeofday(&stop);
1102
1103 local_irq_restore(flags);
1104 local_irq_enable();
1105
1106 nsec = stop.tv_nsec - start.tv_nsec +
1107 1000000000 * (stop.tv_sec - start.tv_sec);
1108
1109 pr_info("crc32: CRC_LE_BITS = %d, CRC_BE BITS = %d\n",
1110 CRC_LE_BITS, CRC_BE_BITS);
1111
1112 if (errors)
1113 pr_warn("crc32: %d self tests failed\n", errors);
1114 else {
1115 pr_info("crc32: self tests passed, processed %d bytes in %lld nsec\n",
1116 bytes, nsec);
1117 }
1118
1119 return 0;
1120}
1121
1122static int __init crc32_combine_test(void)
1123{
1124 int i, j;
1125 int errors = 0, runs = 0;
1126
1127 for (i = 0; i < 10; i++) {
1128 u32 crc_full;
1129
1130 crc_full = crc32_le(test[i].crc, test_buf + test[i].start,
1131 test[i].length);
1132 for (j = 0; j <= test[i].length; ++j) {
1133 u32 crc1, crc2;
1134 u32 len1 = j, len2 = test[i].length - j;
1135
1136 crc1 = crc32_le(test[i].crc, test_buf +
1137 test[i].start, len1);
1138 crc2 = crc32_le(0, test_buf + test[i].start +
1139 len1, len2);
1140
1141 if (!(crc_full == crc32_le_combine(crc1, crc2, len2) &&
1142 crc_full == test[i].crc_le))
1143 errors++;
1144 runs++;
1145 cond_resched();
1146 }
1147 }
1148
1149 if (errors)
1150 pr_warn("crc32_combine: %d/%d self tests failed\n", errors, runs);
1151 else
1152 pr_info("crc32_combine: %d self tests passed\n", runs);
1153
1154 return 0;
1155}
1156
1157static int __init crc32test_init(void)
1158{
1159 crc32_test();
1160 crc32c_test();
1161
1162 crc32_combine_test();
1163 crc32c_combine_test();
1164
1165 return 0;
1166}
1167
1168static void __exit crc32_exit(void)
1169{
1170}
1171
1172module_init(crc32test_init);
1173module_exit(crc32_exit);
1174#endif /* CONFIG_CRC32_SELFTEST */
1/*
2 * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com>
3 * Nicer crc32 functions/docs submitted by linux@horizon.com. Thanks!
4 * Code was from the public domain, copyright abandoned. Code was
5 * subsequently included in the kernel, thus was re-licensed under the
6 * GNU GPL v2.
7 *
8 * Oct 12, 2000 Matt Domsch <Matt_Domsch@dell.com>
9 * Same crc32 function was used in 5 other places in the kernel.
10 * I made one version, and deleted the others.
11 * There are various incantations of crc32(). Some use a seed of 0 or ~0.
12 * Some xor at the end with ~0. The generic crc32() function takes
13 * seed as an argument, and doesn't xor at the end. Then individual
14 * users can do whatever they need.
15 * drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0.
16 * fs/jffs2 uses seed 0, doesn't xor with ~0.
17 * fs/partitions/efi.c uses seed ~0, xor's with ~0.
18 *
19 * This source code is licensed under the GNU General Public License,
20 * Version 2. See the file COPYING for more details.
21 */
22
23#include <linux/crc32.h>
24#include <linux/kernel.h>
25#include <linux/module.h>
26#include <linux/compiler.h>
27#include <linux/types.h>
28#include <linux/init.h>
29#include <linux/atomic.h>
30#include "crc32defs.h"
31#if CRC_LE_BITS == 8
32# define tole(x) __constant_cpu_to_le32(x)
33#else
34# define tole(x) (x)
35#endif
36
37#if CRC_BE_BITS == 8
38# define tobe(x) __constant_cpu_to_be32(x)
39#else
40# define tobe(x) (x)
41#endif
42#include "crc32table.h"
43
44MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
45MODULE_DESCRIPTION("Ethernet CRC32 calculations");
46MODULE_LICENSE("GPL");
47
48#if CRC_LE_BITS == 8 || CRC_BE_BITS == 8
49
50static inline u32
51crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256])
52{
53# ifdef __LITTLE_ENDIAN
54# define DO_CRC(x) crc = tab[0][(crc ^ (x)) & 255] ^ (crc >> 8)
55# define DO_CRC4 crc = tab[3][(crc) & 255] ^ \
56 tab[2][(crc >> 8) & 255] ^ \
57 tab[1][(crc >> 16) & 255] ^ \
58 tab[0][(crc >> 24) & 255]
59# else
60# define DO_CRC(x) crc = tab[0][((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
61# define DO_CRC4 crc = tab[0][(crc) & 255] ^ \
62 tab[1][(crc >> 8) & 255] ^ \
63 tab[2][(crc >> 16) & 255] ^ \
64 tab[3][(crc >> 24) & 255]
65# endif
66 const u32 *b;
67 size_t rem_len;
68
69 /* Align it */
70 if (unlikely((long)buf & 3 && len)) {
71 do {
72 DO_CRC(*buf++);
73 } while ((--len) && ((long)buf)&3);
74 }
75 rem_len = len & 3;
76 /* load data 32 bits wide, xor data 32 bits wide. */
77 len = len >> 2;
78 b = (const u32 *)buf;
79 for (--b; len; --len) {
80 crc ^= *++b; /* use pre increment for speed */
81 DO_CRC4;
82 }
83 len = rem_len;
84 /* And the last few bytes */
85 if (len) {
86 u8 *p = (u8 *)(b + 1) - 1;
87 do {
88 DO_CRC(*++p); /* use pre increment for speed */
89 } while (--len);
90 }
91 return crc;
92#undef DO_CRC
93#undef DO_CRC4
94}
95#endif
96/**
97 * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32
98 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for
99 * other uses, or the previous crc32 value if computing incrementally.
100 * @p: pointer to buffer over which CRC is run
101 * @len: length of buffer @p
102 */
103u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len);
104
105#if CRC_LE_BITS == 1
106/*
107 * In fact, the table-based code will work in this case, but it can be
108 * simplified by inlining the table in ?: form.
109 */
110
111u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
112{
113 int i;
114 while (len--) {
115 crc ^= *p++;
116 for (i = 0; i < 8; i++)
117 crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0);
118 }
119 return crc;
120}
121#else /* Table-based approach */
122
123u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
124{
125# if CRC_LE_BITS == 8
126 const u32 (*tab)[] = crc32table_le;
127
128 crc = __cpu_to_le32(crc);
129 crc = crc32_body(crc, p, len, tab);
130 return __le32_to_cpu(crc);
131# elif CRC_LE_BITS == 4
132 while (len--) {
133 crc ^= *p++;
134 crc = (crc >> 4) ^ crc32table_le[crc & 15];
135 crc = (crc >> 4) ^ crc32table_le[crc & 15];
136 }
137 return crc;
138# elif CRC_LE_BITS == 2
139 while (len--) {
140 crc ^= *p++;
141 crc = (crc >> 2) ^ crc32table_le[crc & 3];
142 crc = (crc >> 2) ^ crc32table_le[crc & 3];
143 crc = (crc >> 2) ^ crc32table_le[crc & 3];
144 crc = (crc >> 2) ^ crc32table_le[crc & 3];
145 }
146 return crc;
147# endif
148}
149#endif
150
151/**
152 * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
153 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for
154 * other uses, or the previous crc32 value if computing incrementally.
155 * @p: pointer to buffer over which CRC is run
156 * @len: length of buffer @p
157 */
158u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len);
159
160#if CRC_BE_BITS == 1
161/*
162 * In fact, the table-based code will work in this case, but it can be
163 * simplified by inlining the table in ?: form.
164 */
165
166u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
167{
168 int i;
169 while (len--) {
170 crc ^= *p++ << 24;
171 for (i = 0; i < 8; i++)
172 crc =
173 (crc << 1) ^ ((crc & 0x80000000) ? CRCPOLY_BE :
174 0);
175 }
176 return crc;
177}
178
179#else /* Table-based approach */
180u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
181{
182# if CRC_BE_BITS == 8
183 const u32 (*tab)[] = crc32table_be;
184
185 crc = __cpu_to_be32(crc);
186 crc = crc32_body(crc, p, len, tab);
187 return __be32_to_cpu(crc);
188# elif CRC_BE_BITS == 4
189 while (len--) {
190 crc ^= *p++ << 24;
191 crc = (crc << 4) ^ crc32table_be[crc >> 28];
192 crc = (crc << 4) ^ crc32table_be[crc >> 28];
193 }
194 return crc;
195# elif CRC_BE_BITS == 2
196 while (len--) {
197 crc ^= *p++ << 24;
198 crc = (crc << 2) ^ crc32table_be[crc >> 30];
199 crc = (crc << 2) ^ crc32table_be[crc >> 30];
200 crc = (crc << 2) ^ crc32table_be[crc >> 30];
201 crc = (crc << 2) ^ crc32table_be[crc >> 30];
202 }
203 return crc;
204# endif
205}
206#endif
207
208EXPORT_SYMBOL(crc32_le);
209EXPORT_SYMBOL(crc32_be);
210
211/*
212 * A brief CRC tutorial.
213 *
214 * A CRC is a long-division remainder. You add the CRC to the message,
215 * and the whole thing (message+CRC) is a multiple of the given
216 * CRC polynomial. To check the CRC, you can either check that the
217 * CRC matches the recomputed value, *or* you can check that the
218 * remainder computed on the message+CRC is 0. This latter approach
219 * is used by a lot of hardware implementations, and is why so many
220 * protocols put the end-of-frame flag after the CRC.
221 *
222 * It's actually the same long division you learned in school, except that
223 * - We're working in binary, so the digits are only 0 and 1, and
224 * - When dividing polynomials, there are no carries. Rather than add and
225 * subtract, we just xor. Thus, we tend to get a bit sloppy about
226 * the difference between adding and subtracting.
227 *
228 * A 32-bit CRC polynomial is actually 33 bits long. But since it's
229 * 33 bits long, bit 32 is always going to be set, so usually the CRC
230 * is written in hex with the most significant bit omitted. (If you're
231 * familiar with the IEEE 754 floating-point format, it's the same idea.)
232 *
233 * Note that a CRC is computed over a string of *bits*, so you have
234 * to decide on the endianness of the bits within each byte. To get
235 * the best error-detecting properties, this should correspond to the
236 * order they're actually sent. For example, standard RS-232 serial is
237 * little-endian; the most significant bit (sometimes used for parity)
238 * is sent last. And when appending a CRC word to a message, you should
239 * do it in the right order, matching the endianness.
240 *
241 * Just like with ordinary division, the remainder is always smaller than
242 * the divisor (the CRC polynomial) you're dividing by. Each step of the
243 * division, you take one more digit (bit) of the dividend and append it
244 * to the current remainder. Then you figure out the appropriate multiple
245 * of the divisor to subtract to being the remainder back into range.
246 * In binary, it's easy - it has to be either 0 or 1, and to make the
247 * XOR cancel, it's just a copy of bit 32 of the remainder.
248 *
249 * When computing a CRC, we don't care about the quotient, so we can
250 * throw the quotient bit away, but subtract the appropriate multiple of
251 * the polynomial from the remainder and we're back to where we started,
252 * ready to process the next bit.
253 *
254 * A big-endian CRC written this way would be coded like:
255 * for (i = 0; i < input_bits; i++) {
256 * multiple = remainder & 0x80000000 ? CRCPOLY : 0;
257 * remainder = (remainder << 1 | next_input_bit()) ^ multiple;
258 * }
259 * Notice how, to get at bit 32 of the shifted remainder, we look
260 * at bit 31 of the remainder *before* shifting it.
261 *
262 * But also notice how the next_input_bit() bits we're shifting into
263 * the remainder don't actually affect any decision-making until
264 * 32 bits later. Thus, the first 32 cycles of this are pretty boring.
265 * Also, to add the CRC to a message, we need a 32-bit-long hole for it at
266 * the end, so we have to add 32 extra cycles shifting in zeros at the
267 * end of every message,
268 *
269 * So the standard trick is to rearrage merging in the next_input_bit()
270 * until the moment it's needed. Then the first 32 cycles can be precomputed,
271 * and merging in the final 32 zero bits to make room for the CRC can be
272 * skipped entirely.
273 * This changes the code to:
274 * for (i = 0; i < input_bits; i++) {
275 * remainder ^= next_input_bit() << 31;
276 * multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
277 * remainder = (remainder << 1) ^ multiple;
278 * }
279 * With this optimization, the little-endian code is simpler:
280 * for (i = 0; i < input_bits; i++) {
281 * remainder ^= next_input_bit();
282 * multiple = (remainder & 1) ? CRCPOLY : 0;
283 * remainder = (remainder >> 1) ^ multiple;
284 * }
285 *
286 * Note that the other details of endianness have been hidden in CRCPOLY
287 * (which must be bit-reversed) and next_input_bit().
288 *
289 * However, as long as next_input_bit is returning the bits in a sensible
290 * order, we can actually do the merging 8 or more bits at a time rather
291 * than one bit at a time:
292 * for (i = 0; i < input_bytes; i++) {
293 * remainder ^= next_input_byte() << 24;
294 * for (j = 0; j < 8; j++) {
295 * multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
296 * remainder = (remainder << 1) ^ multiple;
297 * }
298 * }
299 * Or in little-endian:
300 * for (i = 0; i < input_bytes; i++) {
301 * remainder ^= next_input_byte();
302 * for (j = 0; j < 8; j++) {
303 * multiple = (remainder & 1) ? CRCPOLY : 0;
304 * remainder = (remainder << 1) ^ multiple;
305 * }
306 * }
307 * If the input is a multiple of 32 bits, you can even XOR in a 32-bit
308 * word at a time and increase the inner loop count to 32.
309 *
310 * You can also mix and match the two loop styles, for example doing the
311 * bulk of a message byte-at-a-time and adding bit-at-a-time processing
312 * for any fractional bytes at the end.
313 *
314 * The only remaining optimization is to the byte-at-a-time table method.
315 * Here, rather than just shifting one bit of the remainder to decide
316 * in the correct multiple to subtract, we can shift a byte at a time.
317 * This produces a 40-bit (rather than a 33-bit) intermediate remainder,
318 * but again the multiple of the polynomial to subtract depends only on
319 * the high bits, the high 8 bits in this case.
320 *
321 * The multiple we need in that case is the low 32 bits of a 40-bit
322 * value whose high 8 bits are given, and which is a multiple of the
323 * generator polynomial. This is simply the CRC-32 of the given
324 * one-byte message.
325 *
326 * Two more details: normally, appending zero bits to a message which
327 * is already a multiple of a polynomial produces a larger multiple of that
328 * polynomial. To enable a CRC to detect this condition, it's common to
329 * invert the CRC before appending it. This makes the remainder of the
330 * message+crc come out not as zero, but some fixed non-zero value.
331 *
332 * The same problem applies to zero bits prepended to the message, and
333 * a similar solution is used. Instead of starting with a remainder of
334 * 0, an initial remainder of all ones is used. As long as you start
335 * the same way on decoding, it doesn't make a difference.
336 */
337
338#ifdef UNITTEST
339
340#include <stdlib.h>
341#include <stdio.h>
342
343#if 0 /*Not used at present */
344static void
345buf_dump(char const *prefix, unsigned char const *buf, size_t len)
346{
347 fputs(prefix, stdout);
348 while (len--)
349 printf(" %02x", *buf++);
350 putchar('\n');
351
352}
353#endif
354
355static void bytereverse(unsigned char *buf, size_t len)
356{
357 while (len--) {
358 unsigned char x = bitrev8(*buf);
359 *buf++ = x;
360 }
361}
362
363static void random_garbage(unsigned char *buf, size_t len)
364{
365 while (len--)
366 *buf++ = (unsigned char) random();
367}
368
369#if 0 /* Not used at present */
370static void store_le(u32 x, unsigned char *buf)
371{
372 buf[0] = (unsigned char) x;
373 buf[1] = (unsigned char) (x >> 8);
374 buf[2] = (unsigned char) (x >> 16);
375 buf[3] = (unsigned char) (x >> 24);
376}
377#endif
378
379static void store_be(u32 x, unsigned char *buf)
380{
381 buf[0] = (unsigned char) (x >> 24);
382 buf[1] = (unsigned char) (x >> 16);
383 buf[2] = (unsigned char) (x >> 8);
384 buf[3] = (unsigned char) x;
385}
386
387/*
388 * This checks that CRC(buf + CRC(buf)) = 0, and that
389 * CRC commutes with bit-reversal. This has the side effect
390 * of bytewise bit-reversing the input buffer, and returns
391 * the CRC of the reversed buffer.
392 */
393static u32 test_step(u32 init, unsigned char *buf, size_t len)
394{
395 u32 crc1, crc2;
396 size_t i;
397
398 crc1 = crc32_be(init, buf, len);
399 store_be(crc1, buf + len);
400 crc2 = crc32_be(init, buf, len + 4);
401 if (crc2)
402 printf("\nCRC cancellation fail: 0x%08x should be 0\n",
403 crc2);
404
405 for (i = 0; i <= len + 4; i++) {
406 crc2 = crc32_be(init, buf, i);
407 crc2 = crc32_be(crc2, buf + i, len + 4 - i);
408 if (crc2)
409 printf("\nCRC split fail: 0x%08x\n", crc2);
410 }
411
412 /* Now swap it around for the other test */
413
414 bytereverse(buf, len + 4);
415 init = bitrev32(init);
416 crc2 = bitrev32(crc1);
417 if (crc1 != bitrev32(crc2))
418 printf("\nBit reversal fail: 0x%08x -> 0x%08x -> 0x%08x\n",
419 crc1, crc2, bitrev32(crc2));
420 crc1 = crc32_le(init, buf, len);
421 if (crc1 != crc2)
422 printf("\nCRC endianness fail: 0x%08x != 0x%08x\n", crc1,
423 crc2);
424 crc2 = crc32_le(init, buf, len + 4);
425 if (crc2)
426 printf("\nCRC cancellation fail: 0x%08x should be 0\n",
427 crc2);
428
429 for (i = 0; i <= len + 4; i++) {
430 crc2 = crc32_le(init, buf, i);
431 crc2 = crc32_le(crc2, buf + i, len + 4 - i);
432 if (crc2)
433 printf("\nCRC split fail: 0x%08x\n", crc2);
434 }
435
436 return crc1;
437}
438
439#define SIZE 64
440#define INIT1 0
441#define INIT2 0
442
443int main(void)
444{
445 unsigned char buf1[SIZE + 4];
446 unsigned char buf2[SIZE + 4];
447 unsigned char buf3[SIZE + 4];
448 int i, j;
449 u32 crc1, crc2, crc3;
450
451 for (i = 0; i <= SIZE; i++) {
452 printf("\rTesting length %d...", i);
453 fflush(stdout);
454 random_garbage(buf1, i);
455 random_garbage(buf2, i);
456 for (j = 0; j < i; j++)
457 buf3[j] = buf1[j] ^ buf2[j];
458
459 crc1 = test_step(INIT1, buf1, i);
460 crc2 = test_step(INIT2, buf2, i);
461 /* Now check that CRC(buf1 ^ buf2) = CRC(buf1) ^ CRC(buf2) */
462 crc3 = test_step(INIT1 ^ INIT2, buf3, i);
463 if (crc3 != (crc1 ^ crc2))
464 printf("CRC XOR fail: 0x%08x != 0x%08x ^ 0x%08x\n",
465 crc3, crc1, crc2);
466 }
467 printf("\nAll test complete. No failures expected.\n");
468 return 0;
469}
470
471#endif /* UNITTEST */