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 "crc32defs.h"
33
34#if CRC_LE_BITS > 8
35# define tole(x) ((__force u32) __constant_cpu_to_le32(x))
36#else
37# define tole(x) (x)
38#endif
39
40#if CRC_BE_BITS > 8
41# define tobe(x) ((__force u32) __constant_cpu_to_be32(x))
42#else
43# define tobe(x) (x)
44#endif
45
46#include "crc32table.h"
47
48MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
49MODULE_DESCRIPTION("Various CRC32 calculations");
50MODULE_LICENSE("GPL");
51
52#if CRC_LE_BITS > 8 || CRC_BE_BITS > 8
53
54/* implements slicing-by-4 or slicing-by-8 algorithm */
55static inline u32
56crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256])
57{
58# ifdef __LITTLE_ENDIAN
59# define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8)
60# define DO_CRC4 (t3[(q) & 255] ^ t2[(q >> 8) & 255] ^ \
61 t1[(q >> 16) & 255] ^ t0[(q >> 24) & 255])
62# define DO_CRC8 (t7[(q) & 255] ^ t6[(q >> 8) & 255] ^ \
63 t5[(q >> 16) & 255] ^ t4[(q >> 24) & 255])
64# else
65# define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
66# define DO_CRC4 (t0[(q) & 255] ^ t1[(q >> 8) & 255] ^ \
67 t2[(q >> 16) & 255] ^ t3[(q >> 24) & 255])
68# define DO_CRC8 (t4[(q) & 255] ^ t5[(q >> 8) & 255] ^ \
69 t6[(q >> 16) & 255] ^ t7[(q >> 24) & 255])
70# endif
71 const u32 *b;
72 size_t rem_len;
73# ifdef CONFIG_X86
74 size_t i;
75# endif
76 const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3];
77 const u32 *t4 = tab[4], *t5 = tab[5], *t6 = tab[6], *t7 = tab[7];
78 u32 q;
79
80 /* Align it */
81 if (unlikely((long)buf & 3 && len)) {
82 do {
83 DO_CRC(*buf++);
84 } while ((--len) && ((long)buf)&3);
85 }
86
87# if CRC_LE_BITS == 32
88 rem_len = len & 3;
89 len = len >> 2;
90# else
91 rem_len = len & 7;
92 len = len >> 3;
93# endif
94
95 b = (const u32 *)buf;
96# ifdef CONFIG_X86
97 --b;
98 for (i = 0; i < len; i++) {
99# else
100 for (--b; len; --len) {
101# endif
102 q = crc ^ *++b; /* use pre increment for speed */
103# if CRC_LE_BITS == 32
104 crc = DO_CRC4;
105# else
106 crc = DO_CRC8;
107 q = *++b;
108 crc ^= DO_CRC4;
109# endif
110 }
111 len = rem_len;
112 /* And the last few bytes */
113 if (len) {
114 u8 *p = (u8 *)(b + 1) - 1;
115# ifdef CONFIG_X86
116 for (i = 0; i < len; i++)
117 DO_CRC(*++p); /* use pre increment for speed */
118# else
119 do {
120 DO_CRC(*++p); /* use pre increment for speed */
121 } while (--len);
122# endif
123 }
124 return crc;
125#undef DO_CRC
126#undef DO_CRC4
127#undef DO_CRC8
128}
129#endif
130
131/**
132 * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32
133 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for
134 * other uses, or the previous crc32 value if computing incrementally.
135 * @p: pointer to buffer over which CRC is run
136 * @len: length of buffer @p
137 */
138static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p,
139 size_t len, const u32 (*tab)[256],
140 u32 polynomial)
141{
142#if CRC_LE_BITS == 1
143 int i;
144 while (len--) {
145 crc ^= *p++;
146 for (i = 0; i < 8; i++)
147 crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0);
148 }
149# elif CRC_LE_BITS == 2
150 while (len--) {
151 crc ^= *p++;
152 crc = (crc >> 2) ^ tab[0][crc & 3];
153 crc = (crc >> 2) ^ tab[0][crc & 3];
154 crc = (crc >> 2) ^ tab[0][crc & 3];
155 crc = (crc >> 2) ^ tab[0][crc & 3];
156 }
157# elif CRC_LE_BITS == 4
158 while (len--) {
159 crc ^= *p++;
160 crc = (crc >> 4) ^ tab[0][crc & 15];
161 crc = (crc >> 4) ^ tab[0][crc & 15];
162 }
163# elif CRC_LE_BITS == 8
164 /* aka Sarwate algorithm */
165 while (len--) {
166 crc ^= *p++;
167 crc = (crc >> 8) ^ tab[0][crc & 255];
168 }
169# else
170 crc = (__force u32) __cpu_to_le32(crc);
171 crc = crc32_body(crc, p, len, tab);
172 crc = __le32_to_cpu((__force __le32)crc);
173#endif
174 return crc;
175}
176
177#if CRC_LE_BITS == 1
178u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
179{
180 return crc32_le_generic(crc, p, len, NULL, CRCPOLY_LE);
181}
182u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len)
183{
184 return crc32_le_generic(crc, p, len, NULL, CRC32C_POLY_LE);
185}
186#else
187u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
188{
189 return crc32_le_generic(crc, p, len, crc32table_le, CRCPOLY_LE);
190}
191u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len)
192{
193 return crc32_le_generic(crc, p, len, crc32ctable_le, CRC32C_POLY_LE);
194}
195#endif
196EXPORT_SYMBOL(crc32_le);
197EXPORT_SYMBOL(__crc32c_le);
198
199/**
200 * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
201 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for
202 * other uses, or the previous crc32 value if computing incrementally.
203 * @p: pointer to buffer over which CRC is run
204 * @len: length of buffer @p
205 */
206static inline u32 __pure crc32_be_generic(u32 crc, unsigned char const *p,
207 size_t len, const u32 (*tab)[256],
208 u32 polynomial)
209{
210#if CRC_BE_BITS == 1
211 int i;
212 while (len--) {
213 crc ^= *p++ << 24;
214 for (i = 0; i < 8; i++)
215 crc =
216 (crc << 1) ^ ((crc & 0x80000000) ? polynomial :
217 0);
218 }
219# elif CRC_BE_BITS == 2
220 while (len--) {
221 crc ^= *p++ << 24;
222 crc = (crc << 2) ^ tab[0][crc >> 30];
223 crc = (crc << 2) ^ tab[0][crc >> 30];
224 crc = (crc << 2) ^ tab[0][crc >> 30];
225 crc = (crc << 2) ^ tab[0][crc >> 30];
226 }
227# elif CRC_BE_BITS == 4
228 while (len--) {
229 crc ^= *p++ << 24;
230 crc = (crc << 4) ^ tab[0][crc >> 28];
231 crc = (crc << 4) ^ tab[0][crc >> 28];
232 }
233# elif CRC_BE_BITS == 8
234 while (len--) {
235 crc ^= *p++ << 24;
236 crc = (crc << 8) ^ tab[0][crc >> 24];
237 }
238# else
239 crc = (__force u32) __cpu_to_be32(crc);
240 crc = crc32_body(crc, p, len, tab);
241 crc = __be32_to_cpu((__force __be32)crc);
242# endif
243 return crc;
244}
245
246#if CRC_LE_BITS == 1
247u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
248{
249 return crc32_be_generic(crc, p, len, NULL, CRCPOLY_BE);
250}
251#else
252u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
253{
254 return crc32_be_generic(crc, p, len, crc32table_be, CRCPOLY_BE);
255}
256#endif
257EXPORT_SYMBOL(crc32_be);
258
259#ifdef CONFIG_CRC32_SELFTEST
260
261/* 4096 random bytes */
262static u8 __attribute__((__aligned__(8))) test_buf[] =
263{
264 0x5b, 0x85, 0x21, 0xcb, 0x09, 0x68, 0x7d, 0x30,
265 0xc7, 0x69, 0xd7, 0x30, 0x92, 0xde, 0x59, 0xe4,
266 0xc9, 0x6e, 0x8b, 0xdb, 0x98, 0x6b, 0xaa, 0x60,
267 0xa8, 0xb5, 0xbc, 0x6c, 0xa9, 0xb1, 0x5b, 0x2c,
268 0xea, 0xb4, 0x92, 0x6a, 0x3f, 0x79, 0x91, 0xe4,
269 0xe9, 0x70, 0x51, 0x8c, 0x7f, 0x95, 0x6f, 0x1a,
270 0x56, 0xa1, 0x5c, 0x27, 0x03, 0x67, 0x9f, 0x3a,
271 0xe2, 0x31, 0x11, 0x29, 0x6b, 0x98, 0xfc, 0xc4,
272 0x53, 0x24, 0xc5, 0x8b, 0xce, 0x47, 0xb2, 0xb9,
273 0x32, 0xcb, 0xc1, 0xd0, 0x03, 0x57, 0x4e, 0xd4,
274 0xe9, 0x3c, 0xa1, 0x63, 0xcf, 0x12, 0x0e, 0xca,
275 0xe1, 0x13, 0xd1, 0x93, 0xa6, 0x88, 0x5c, 0x61,
276 0x5b, 0xbb, 0xf0, 0x19, 0x46, 0xb4, 0xcf, 0x9e,
277 0xb6, 0x6b, 0x4c, 0x3a, 0xcf, 0x60, 0xf9, 0x7a,
278 0x8d, 0x07, 0x63, 0xdb, 0x40, 0xe9, 0x0b, 0x6f,
279 0xad, 0x97, 0xf1, 0xed, 0xd0, 0x1e, 0x26, 0xfd,
280 0xbf, 0xb7, 0xc8, 0x04, 0x94, 0xf8, 0x8b, 0x8c,
281 0xf1, 0xab, 0x7a, 0xd4, 0xdd, 0xf3, 0xe8, 0x88,
282 0xc3, 0xed, 0x17, 0x8a, 0x9b, 0x40, 0x0d, 0x53,
283 0x62, 0x12, 0x03, 0x5f, 0x1b, 0x35, 0x32, 0x1f,
284 0xb4, 0x7b, 0x93, 0x78, 0x0d, 0xdb, 0xce, 0xa4,
285 0xc0, 0x47, 0xd5, 0xbf, 0x68, 0xe8, 0x5d, 0x74,
286 0x8f, 0x8e, 0x75, 0x1c, 0xb2, 0x4f, 0x9a, 0x60,
287 0xd1, 0xbe, 0x10, 0xf4, 0x5c, 0xa1, 0x53, 0x09,
288 0xa5, 0xe0, 0x09, 0x54, 0x85, 0x5c, 0xdc, 0x07,
289 0xe7, 0x21, 0x69, 0x7b, 0x8a, 0xfd, 0x90, 0xf1,
290 0x22, 0xd0, 0xb4, 0x36, 0x28, 0xe6, 0xb8, 0x0f,
291 0x39, 0xde, 0xc8, 0xf3, 0x86, 0x60, 0x34, 0xd2,
292 0x5e, 0xdf, 0xfd, 0xcf, 0x0f, 0xa9, 0x65, 0xf0,
293 0xd5, 0x4d, 0x96, 0x40, 0xe3, 0xdf, 0x3f, 0x95,
294 0x5a, 0x39, 0x19, 0x93, 0xf4, 0x75, 0xce, 0x22,
295 0x00, 0x1c, 0x93, 0xe2, 0x03, 0x66, 0xf4, 0x93,
296 0x73, 0x86, 0x81, 0x8e, 0x29, 0x44, 0x48, 0x86,
297 0x61, 0x7c, 0x48, 0xa3, 0x43, 0xd2, 0x9c, 0x8d,
298 0xd4, 0x95, 0xdd, 0xe1, 0x22, 0x89, 0x3a, 0x40,
299 0x4c, 0x1b, 0x8a, 0x04, 0xa8, 0x09, 0x69, 0x8b,
300 0xea, 0xc6, 0x55, 0x8e, 0x57, 0xe6, 0x64, 0x35,
301 0xf0, 0xc7, 0x16, 0x9f, 0x5d, 0x5e, 0x86, 0x40,
302 0x46, 0xbb, 0xe5, 0x45, 0x88, 0xfe, 0xc9, 0x63,
303 0x15, 0xfb, 0xf5, 0xbd, 0x71, 0x61, 0xeb, 0x7b,
304 0x78, 0x70, 0x07, 0x31, 0x03, 0x9f, 0xb2, 0xc8,
305 0xa7, 0xab, 0x47, 0xfd, 0xdf, 0xa0, 0x78, 0x72,
306 0xa4, 0x2a, 0xe4, 0xb6, 0xba, 0xc0, 0x1e, 0x86,
307 0x71, 0xe6, 0x3d, 0x18, 0x37, 0x70, 0xe6, 0xff,
308 0xe0, 0xbc, 0x0b, 0x22, 0xa0, 0x1f, 0xd3, 0xed,
309 0xa2, 0x55, 0x39, 0xab, 0xa8, 0x13, 0x73, 0x7c,
310 0x3f, 0xb2, 0xd6, 0x19, 0xac, 0xff, 0x99, 0xed,
311 0xe8, 0xe6, 0xa6, 0x22, 0xe3, 0x9c, 0xf1, 0x30,
312 0xdc, 0x01, 0x0a, 0x56, 0xfa, 0xe4, 0xc9, 0x99,
313 0xdd, 0xa8, 0xd8, 0xda, 0x35, 0x51, 0x73, 0xb4,
314 0x40, 0x86, 0x85, 0xdb, 0x5c, 0xd5, 0x85, 0x80,
315 0x14, 0x9c, 0xfd, 0x98, 0xa9, 0x82, 0xc5, 0x37,
316 0xff, 0x32, 0x5d, 0xd0, 0x0b, 0xfa, 0xdc, 0x04,
317 0x5e, 0x09, 0xd2, 0xca, 0x17, 0x4b, 0x1a, 0x8e,
318 0x15, 0xe1, 0xcc, 0x4e, 0x52, 0x88, 0x35, 0xbd,
319 0x48, 0xfe, 0x15, 0xa0, 0x91, 0xfd, 0x7e, 0x6c,
320 0x0e, 0x5d, 0x79, 0x1b, 0x81, 0x79, 0xd2, 0x09,
321 0x34, 0x70, 0x3d, 0x81, 0xec, 0xf6, 0x24, 0xbb,
322 0xfb, 0xf1, 0x7b, 0xdf, 0x54, 0xea, 0x80, 0x9b,
323 0xc7, 0x99, 0x9e, 0xbd, 0x16, 0x78, 0x12, 0x53,
324 0x5e, 0x01, 0xa7, 0x4e, 0xbd, 0x67, 0xe1, 0x9b,
325 0x4c, 0x0e, 0x61, 0x45, 0x97, 0xd2, 0xf0, 0x0f,
326 0xfe, 0x15, 0x08, 0xb7, 0x11, 0x4c, 0xe7, 0xff,
327 0x81, 0x53, 0xff, 0x91, 0x25, 0x38, 0x7e, 0x40,
328 0x94, 0xe5, 0xe0, 0xad, 0xe6, 0xd9, 0x79, 0xb6,
329 0x92, 0xc9, 0xfc, 0xde, 0xc3, 0x1a, 0x23, 0xbb,
330 0xdd, 0xc8, 0x51, 0x0c, 0x3a, 0x72, 0xfa, 0x73,
331 0x6f, 0xb7, 0xee, 0x61, 0x39, 0x03, 0x01, 0x3f,
332 0x7f, 0x94, 0x2e, 0x2e, 0xba, 0x3a, 0xbb, 0xb4,
333 0xfa, 0x6a, 0x17, 0xfe, 0xea, 0xef, 0x5e, 0x66,
334 0x97, 0x3f, 0x32, 0x3d, 0xd7, 0x3e, 0xb1, 0xf1,
335 0x6c, 0x14, 0x4c, 0xfd, 0x37, 0xd3, 0x38, 0x80,
336 0xfb, 0xde, 0xa6, 0x24, 0x1e, 0xc8, 0xca, 0x7f,
337 0x3a, 0x93, 0xd8, 0x8b, 0x18, 0x13, 0xb2, 0xe5,
338 0xe4, 0x93, 0x05, 0x53, 0x4f, 0x84, 0x66, 0xa7,
339 0x58, 0x5c, 0x7b, 0x86, 0x52, 0x6d, 0x0d, 0xce,
340 0xa4, 0x30, 0x7d, 0xb6, 0x18, 0x9f, 0xeb, 0xff,
341 0x22, 0xbb, 0x72, 0x29, 0xb9, 0x44, 0x0b, 0x48,
342 0x1e, 0x84, 0x71, 0x81, 0xe3, 0x6d, 0x73, 0x26,
343 0x92, 0xb4, 0x4d, 0x2a, 0x29, 0xb8, 0x1f, 0x72,
344 0xed, 0xd0, 0xe1, 0x64, 0x77, 0xea, 0x8e, 0x88,
345 0x0f, 0xef, 0x3f, 0xb1, 0x3b, 0xad, 0xf9, 0xc9,
346 0x8b, 0xd0, 0xac, 0xc6, 0xcc, 0xa9, 0x40, 0xcc,
347 0x76, 0xf6, 0x3b, 0x53, 0xb5, 0x88, 0xcb, 0xc8,
348 0x37, 0xf1, 0xa2, 0xba, 0x23, 0x15, 0x99, 0x09,
349 0xcc, 0xe7, 0x7a, 0x3b, 0x37, 0xf7, 0x58, 0xc8,
350 0x46, 0x8c, 0x2b, 0x2f, 0x4e, 0x0e, 0xa6, 0x5c,
351 0xea, 0x85, 0x55, 0xba, 0x02, 0x0e, 0x0e, 0x48,
352 0xbc, 0xe1, 0xb1, 0x01, 0x35, 0x79, 0x13, 0x3d,
353 0x1b, 0xc0, 0x53, 0x68, 0x11, 0xe7, 0x95, 0x0f,
354 0x9d, 0x3f, 0x4c, 0x47, 0x7b, 0x4d, 0x1c, 0xae,
355 0x50, 0x9b, 0xcb, 0xdd, 0x05, 0x8d, 0x9a, 0x97,
356 0xfd, 0x8c, 0xef, 0x0c, 0x1d, 0x67, 0x73, 0xa8,
357 0x28, 0x36, 0xd5, 0xb6, 0x92, 0x33, 0x40, 0x75,
358 0x0b, 0x51, 0xc3, 0x64, 0xba, 0x1d, 0xc2, 0xcc,
359 0xee, 0x7d, 0x54, 0x0f, 0x27, 0x69, 0xa7, 0x27,
360 0x63, 0x30, 0x29, 0xd9, 0xc8, 0x84, 0xd8, 0xdf,
361 0x9f, 0x68, 0x8d, 0x04, 0xca, 0xa6, 0xc5, 0xc7,
362 0x7a, 0x5c, 0xc8, 0xd1, 0xcb, 0x4a, 0xec, 0xd0,
363 0xd8, 0x20, 0x69, 0xc5, 0x17, 0xcd, 0x78, 0xc8,
364 0x75, 0x23, 0x30, 0x69, 0xc9, 0xd4, 0xea, 0x5c,
365 0x4f, 0x6b, 0x86, 0x3f, 0x8b, 0xfe, 0xee, 0x44,
366 0xc9, 0x7c, 0xb7, 0xdd, 0x3e, 0xe5, 0xec, 0x54,
367 0x03, 0x3e, 0xaa, 0x82, 0xc6, 0xdf, 0xb2, 0x38,
368 0x0e, 0x5d, 0xb3, 0x88, 0xd9, 0xd3, 0x69, 0x5f,
369 0x8f, 0x70, 0x8a, 0x7e, 0x11, 0xd9, 0x1e, 0x7b,
370 0x38, 0xf1, 0x42, 0x1a, 0xc0, 0x35, 0xf5, 0xc7,
371 0x36, 0x85, 0xf5, 0xf7, 0xb8, 0x7e, 0xc7, 0xef,
372 0x18, 0xf1, 0x63, 0xd6, 0x7a, 0xc6, 0xc9, 0x0e,
373 0x4d, 0x69, 0x4f, 0x84, 0xef, 0x26, 0x41, 0x0c,
374 0xec, 0xc7, 0xe0, 0x7e, 0x3c, 0x67, 0x01, 0x4c,
375 0x62, 0x1a, 0x20, 0x6f, 0xee, 0x47, 0x4d, 0xc0,
376 0x99, 0x13, 0x8d, 0x91, 0x4a, 0x26, 0xd4, 0x37,
377 0x28, 0x90, 0x58, 0x75, 0x66, 0x2b, 0x0a, 0xdf,
378 0xda, 0xee, 0x92, 0x25, 0x90, 0x62, 0x39, 0x9e,
379 0x44, 0x98, 0xad, 0xc1, 0x88, 0xed, 0xe4, 0xb4,
380 0xaf, 0xf5, 0x8c, 0x9b, 0x48, 0x4d, 0x56, 0x60,
381 0x97, 0x0f, 0x61, 0x59, 0x9e, 0xa6, 0x27, 0xfe,
382 0xc1, 0x91, 0x15, 0x38, 0xb8, 0x0f, 0xae, 0x61,
383 0x7d, 0x26, 0x13, 0x5a, 0x73, 0xff, 0x1c, 0xa3,
384 0x61, 0x04, 0x58, 0x48, 0x55, 0x44, 0x11, 0xfe,
385 0x15, 0xca, 0xc3, 0xbd, 0xca, 0xc5, 0xb4, 0x40,
386 0x5d, 0x1b, 0x7f, 0x39, 0xb5, 0x9c, 0x35, 0xec,
387 0x61, 0x15, 0x32, 0x32, 0xb8, 0x4e, 0x40, 0x9f,
388 0x17, 0x1f, 0x0a, 0x4d, 0xa9, 0x91, 0xef, 0xb7,
389 0xb0, 0xeb, 0xc2, 0x83, 0x9a, 0x6c, 0xd2, 0x79,
390 0x43, 0x78, 0x5e, 0x2f, 0xe5, 0xdd, 0x1a, 0x3c,
391 0x45, 0xab, 0x29, 0x40, 0x3a, 0x37, 0x5b, 0x6f,
392 0xd7, 0xfc, 0x48, 0x64, 0x3c, 0x49, 0xfb, 0x21,
393 0xbe, 0xc3, 0xff, 0x07, 0xfb, 0x17, 0xe9, 0xc9,
394 0x0c, 0x4c, 0x5c, 0x15, 0x9e, 0x8e, 0x22, 0x30,
395 0x0a, 0xde, 0x48, 0x7f, 0xdb, 0x0d, 0xd1, 0x2b,
396 0x87, 0x38, 0x9e, 0xcc, 0x5a, 0x01, 0x16, 0xee,
397 0x75, 0x49, 0x0d, 0x30, 0x01, 0x34, 0x6a, 0xb6,
398 0x9a, 0x5a, 0x2a, 0xec, 0xbb, 0x48, 0xac, 0xd3,
399 0x77, 0x83, 0xd8, 0x08, 0x86, 0x4f, 0x48, 0x09,
400 0x29, 0x41, 0x79, 0xa1, 0x03, 0x12, 0xc4, 0xcd,
401 0x90, 0x55, 0x47, 0x66, 0x74, 0x9a, 0xcc, 0x4f,
402 0x35, 0x8c, 0xd6, 0x98, 0xef, 0xeb, 0x45, 0xb9,
403 0x9a, 0x26, 0x2f, 0x39, 0xa5, 0x70, 0x6d, 0xfc,
404 0xb4, 0x51, 0xee, 0xf4, 0x9c, 0xe7, 0x38, 0x59,
405 0xad, 0xf4, 0xbc, 0x46, 0xff, 0x46, 0x8e, 0x60,
406 0x9c, 0xa3, 0x60, 0x1d, 0xf8, 0x26, 0x72, 0xf5,
407 0x72, 0x9d, 0x68, 0x80, 0x04, 0xf6, 0x0b, 0xa1,
408 0x0a, 0xd5, 0xa7, 0x82, 0x3a, 0x3e, 0x47, 0xa8,
409 0x5a, 0xde, 0x59, 0x4f, 0x7b, 0x07, 0xb3, 0xe9,
410 0x24, 0x19, 0x3d, 0x34, 0x05, 0xec, 0xf1, 0xab,
411 0x6e, 0x64, 0x8f, 0xd3, 0xe6, 0x41, 0x86, 0x80,
412 0x70, 0xe3, 0x8d, 0x60, 0x9c, 0x34, 0x25, 0x01,
413 0x07, 0x4d, 0x19, 0x41, 0x4e, 0x3d, 0x5c, 0x7e,
414 0xa8, 0xf5, 0xcc, 0xd5, 0x7b, 0xe2, 0x7d, 0x3d,
415 0x49, 0x86, 0x7d, 0x07, 0xb7, 0x10, 0xe3, 0x35,
416 0xb8, 0x84, 0x6d, 0x76, 0xab, 0x17, 0xc6, 0x38,
417 0xb4, 0xd3, 0x28, 0x57, 0xad, 0xd3, 0x88, 0x5a,
418 0xda, 0xea, 0xc8, 0x94, 0xcc, 0x37, 0x19, 0xac,
419 0x9c, 0x9f, 0x4b, 0x00, 0x15, 0xc0, 0xc8, 0xca,
420 0x1f, 0x15, 0xaa, 0xe0, 0xdb, 0xf9, 0x2f, 0x57,
421 0x1b, 0x24, 0xc7, 0x6f, 0x76, 0x29, 0xfb, 0xed,
422 0x25, 0x0d, 0xc0, 0xfe, 0xbd, 0x5a, 0xbf, 0x20,
423 0x08, 0x51, 0x05, 0xec, 0x71, 0xa3, 0xbf, 0xef,
424 0x5e, 0x99, 0x75, 0xdb, 0x3c, 0x5f, 0x9a, 0x8c,
425 0xbb, 0x19, 0x5c, 0x0e, 0x93, 0x19, 0xf8, 0x6a,
426 0xbc, 0xf2, 0x12, 0x54, 0x2f, 0xcb, 0x28, 0x64,
427 0x88, 0xb3, 0x92, 0x0d, 0x96, 0xd1, 0xa6, 0xe4,
428 0x1f, 0xf1, 0x4d, 0xa4, 0xab, 0x1c, 0xee, 0x54,
429 0xf2, 0xad, 0x29, 0x6d, 0x32, 0x37, 0xb2, 0x16,
430 0x77, 0x5c, 0xdc, 0x2e, 0x54, 0xec, 0x75, 0x26,
431 0xc6, 0x36, 0xd9, 0x17, 0x2c, 0xf1, 0x7a, 0xdc,
432 0x4b, 0xf1, 0xe2, 0xd9, 0x95, 0xba, 0xac, 0x87,
433 0xc1, 0xf3, 0x8e, 0x58, 0x08, 0xd8, 0x87, 0x60,
434 0xc9, 0xee, 0x6a, 0xde, 0xa4, 0xd2, 0xfc, 0x0d,
435 0xe5, 0x36, 0xc4, 0x5c, 0x52, 0xb3, 0x07, 0x54,
436 0x65, 0x24, 0xc1, 0xb1, 0xd1, 0xb1, 0x53, 0x13,
437 0x31, 0x79, 0x7f, 0x05, 0x76, 0xeb, 0x37, 0x59,
438 0x15, 0x2b, 0xd1, 0x3f, 0xac, 0x08, 0x97, 0xeb,
439 0x91, 0x98, 0xdf, 0x6c, 0x09, 0x0d, 0x04, 0x9f,
440 0xdc, 0x3b, 0x0e, 0x60, 0x68, 0x47, 0x23, 0x15,
441 0x16, 0xc6, 0x0b, 0x35, 0xf8, 0x77, 0xa2, 0x78,
442 0x50, 0xd4, 0x64, 0x22, 0x33, 0xff, 0xfb, 0x93,
443 0x71, 0x46, 0x50, 0x39, 0x1b, 0x9c, 0xea, 0x4e,
444 0x8d, 0x0c, 0x37, 0xe5, 0x5c, 0x51, 0x3a, 0x31,
445 0xb2, 0x85, 0x84, 0x3f, 0x41, 0xee, 0xa2, 0xc1,
446 0xc6, 0x13, 0x3b, 0x54, 0x28, 0xd2, 0x18, 0x37,
447 0xcc, 0x46, 0x9f, 0x6a, 0x91, 0x3d, 0x5a, 0x15,
448 0x3c, 0x89, 0xa3, 0x61, 0x06, 0x7d, 0x2e, 0x78,
449 0xbe, 0x7d, 0x40, 0xba, 0x2f, 0x95, 0xb1, 0x2f,
450 0x87, 0x3b, 0x8a, 0xbe, 0x6a, 0xf4, 0xc2, 0x31,
451 0x74, 0xee, 0x91, 0xe0, 0x23, 0xaa, 0x5d, 0x7f,
452 0xdd, 0xf0, 0x44, 0x8c, 0x0b, 0x59, 0x2b, 0xfc,
453 0x48, 0x3a, 0xdf, 0x07, 0x05, 0x38, 0x6c, 0xc9,
454 0xeb, 0x18, 0x24, 0x68, 0x8d, 0x58, 0x98, 0xd3,
455 0x31, 0xa3, 0xe4, 0x70, 0x59, 0xb1, 0x21, 0xbe,
456 0x7e, 0x65, 0x7d, 0xb8, 0x04, 0xab, 0xf6, 0xe4,
457 0xd7, 0xda, 0xec, 0x09, 0x8f, 0xda, 0x6d, 0x24,
458 0x07, 0xcc, 0x29, 0x17, 0x05, 0x78, 0x1a, 0xc1,
459 0xb1, 0xce, 0xfc, 0xaa, 0x2d, 0xe7, 0xcc, 0x85,
460 0x84, 0x84, 0x03, 0x2a, 0x0c, 0x3f, 0xa9, 0xf8,
461 0xfd, 0x84, 0x53, 0x59, 0x5c, 0xf0, 0xd4, 0x09,
462 0xf0, 0xd2, 0x6c, 0x32, 0x03, 0xb0, 0xa0, 0x8c,
463 0x52, 0xeb, 0x23, 0x91, 0x88, 0x43, 0x13, 0x46,
464 0xf6, 0x1e, 0xb4, 0x1b, 0xf5, 0x8e, 0x3a, 0xb5,
465 0x3d, 0x00, 0xf6, 0xe5, 0x08, 0x3d, 0x5f, 0x39,
466 0xd3, 0x21, 0x69, 0xbc, 0x03, 0x22, 0x3a, 0xd2,
467 0x5c, 0x84, 0xf8, 0x15, 0xc4, 0x80, 0x0b, 0xbc,
468 0x29, 0x3c, 0xf3, 0x95, 0x98, 0xcd, 0x8f, 0x35,
469 0xbc, 0xa5, 0x3e, 0xfc, 0xd4, 0x13, 0x9e, 0xde,
470 0x4f, 0xce, 0x71, 0x9d, 0x09, 0xad, 0xf2, 0x80,
471 0x6b, 0x65, 0x7f, 0x03, 0x00, 0x14, 0x7c, 0x15,
472 0x85, 0x40, 0x6d, 0x70, 0xea, 0xdc, 0xb3, 0x63,
473 0x35, 0x4f, 0x4d, 0xe0, 0xd9, 0xd5, 0x3c, 0x58,
474 0x56, 0x23, 0x80, 0xe2, 0x36, 0xdd, 0x75, 0x1d,
475 0x94, 0x11, 0x41, 0x8e, 0xe0, 0x81, 0x8e, 0xcf,
476 0xe0, 0xe5, 0xf6, 0xde, 0xd1, 0xe7, 0x04, 0x12,
477 0x79, 0x92, 0x2b, 0x71, 0x2a, 0x79, 0x8b, 0x7c,
478 0x44, 0x79, 0x16, 0x30, 0x4e, 0xf4, 0xf6, 0x9b,
479 0xb7, 0x40, 0xa3, 0x5a, 0xa7, 0x69, 0x3e, 0xc1,
480 0x3a, 0x04, 0xd0, 0x88, 0xa0, 0x3b, 0xdd, 0xc6,
481 0x9e, 0x7e, 0x1e, 0x1e, 0x8f, 0x44, 0xf7, 0x73,
482 0x67, 0x1e, 0x1a, 0x78, 0xfa, 0x62, 0xf4, 0xa9,
483 0xa8, 0xc6, 0x5b, 0xb8, 0xfa, 0x06, 0x7d, 0x5e,
484 0x38, 0x1c, 0x9a, 0x39, 0xe9, 0x39, 0x98, 0x22,
485 0x0b, 0xa7, 0xac, 0x0b, 0xf3, 0xbc, 0xf1, 0xeb,
486 0x8c, 0x81, 0xe3, 0x48, 0x8a, 0xed, 0x42, 0xc2,
487 0x38, 0xcf, 0x3e, 0xda, 0xd2, 0x89, 0x8d, 0x9c,
488 0x53, 0xb5, 0x2f, 0x41, 0x01, 0x26, 0x84, 0x9c,
489 0xa3, 0x56, 0xf6, 0x49, 0xc7, 0xd4, 0x9f, 0x93,
490 0x1b, 0x96, 0x49, 0x5e, 0xad, 0xb3, 0x84, 0x1f,
491 0x3c, 0xa4, 0xe0, 0x9b, 0xd1, 0x90, 0xbc, 0x38,
492 0x6c, 0xdd, 0x95, 0x4d, 0x9d, 0xb1, 0x71, 0x57,
493 0x2d, 0x34, 0xe8, 0xb8, 0x42, 0xc7, 0x99, 0x03,
494 0xc7, 0x07, 0x30, 0x65, 0x91, 0x55, 0xd5, 0x90,
495 0x70, 0x97, 0x37, 0x68, 0xd4, 0x11, 0xf9, 0xe8,
496 0xce, 0xec, 0xdc, 0x34, 0xd5, 0xd3, 0xb7, 0xc4,
497 0xb8, 0x97, 0x05, 0x92, 0xad, 0xf8, 0xe2, 0x36,
498 0x64, 0x41, 0xc9, 0xc5, 0x41, 0x77, 0x52, 0xd7,
499 0x2c, 0xa5, 0x24, 0x2f, 0xd9, 0x34, 0x0b, 0x47,
500 0x35, 0xa7, 0x28, 0x8b, 0xc5, 0xcd, 0xe9, 0x46,
501 0xac, 0x39, 0x94, 0x3c, 0x10, 0xc6, 0x29, 0x73,
502 0x0e, 0x0e, 0x5d, 0xe0, 0x71, 0x03, 0x8a, 0x72,
503 0x0e, 0x26, 0xb0, 0x7d, 0x84, 0xed, 0x95, 0x23,
504 0x49, 0x5a, 0x45, 0x83, 0x45, 0x60, 0x11, 0x4a,
505 0x46, 0x31, 0xd4, 0xd8, 0x16, 0x54, 0x98, 0x58,
506 0xed, 0x6d, 0xcc, 0x5d, 0xd6, 0x50, 0x61, 0x9f,
507 0x9d, 0xc5, 0x3e, 0x9d, 0x32, 0x47, 0xde, 0x96,
508 0xe1, 0x5d, 0xd8, 0xf8, 0xb4, 0x69, 0x6f, 0xb9,
509 0x15, 0x90, 0x57, 0x7a, 0xf6, 0xad, 0xb0, 0x5b,
510 0xf5, 0xa6, 0x36, 0x94, 0xfd, 0x84, 0xce, 0x1c,
511 0x0f, 0x4b, 0xd0, 0xc2, 0x5b, 0x6b, 0x56, 0xef,
512 0x73, 0x93, 0x0b, 0xc3, 0xee, 0xd9, 0xcf, 0xd3,
513 0xa4, 0x22, 0x58, 0xcd, 0x50, 0x6e, 0x65, 0xf4,
514 0xe9, 0xb7, 0x71, 0xaf, 0x4b, 0xb3, 0xb6, 0x2f,
515 0x0f, 0x0e, 0x3b, 0xc9, 0x85, 0x14, 0xf5, 0x17,
516 0xe8, 0x7a, 0x3a, 0xbf, 0x5f, 0x5e, 0xf8, 0x18,
517 0x48, 0xa6, 0x72, 0xab, 0x06, 0x95, 0xe9, 0xc8,
518 0xa7, 0xf4, 0x32, 0x44, 0x04, 0x0c, 0x84, 0x98,
519 0x73, 0xe3, 0x89, 0x8d, 0x5f, 0x7e, 0x4a, 0x42,
520 0x8f, 0xc5, 0x28, 0xb1, 0x82, 0xef, 0x1c, 0x97,
521 0x31, 0x3b, 0x4d, 0xe0, 0x0e, 0x10, 0x10, 0x97,
522 0x93, 0x49, 0x78, 0x2f, 0x0d, 0x86, 0x8b, 0xa1,
523 0x53, 0xa9, 0x81, 0x20, 0x79, 0xe7, 0x07, 0x77,
524 0xb6, 0xac, 0x5e, 0xd2, 0x05, 0xcd, 0xe9, 0xdb,
525 0x8a, 0x94, 0x82, 0x8a, 0x23, 0xb9, 0x3d, 0x1c,
526 0xa9, 0x7d, 0x72, 0x4a, 0xed, 0x33, 0xa3, 0xdb,
527 0x21, 0xa7, 0x86, 0x33, 0x45, 0xa5, 0xaa, 0x56,
528 0x45, 0xb5, 0x83, 0x29, 0x40, 0x47, 0x79, 0x04,
529 0x6e, 0xb9, 0x95, 0xd0, 0x81, 0x77, 0x2d, 0x48,
530 0x1e, 0xfe, 0xc3, 0xc2, 0x1e, 0xe5, 0xf2, 0xbe,
531 0xfd, 0x3b, 0x94, 0x9f, 0xc4, 0xc4, 0x26, 0x9d,
532 0xe4, 0x66, 0x1e, 0x19, 0xee, 0x6c, 0x79, 0x97,
533 0x11, 0x31, 0x4b, 0x0d, 0x01, 0xcb, 0xde, 0xa8,
534 0xf6, 0x6d, 0x7c, 0x39, 0x46, 0x4e, 0x7e, 0x3f,
535 0x94, 0x17, 0xdf, 0xa1, 0x7d, 0xd9, 0x1c, 0x8e,
536 0xbc, 0x7d, 0x33, 0x7d, 0xe3, 0x12, 0x40, 0xca,
537 0xab, 0x37, 0x11, 0x46, 0xd4, 0xae, 0xef, 0x44,
538 0xa2, 0xb3, 0x6a, 0x66, 0x0e, 0x0c, 0x90, 0x7f,
539 0xdf, 0x5c, 0x66, 0x5f, 0xf2, 0x94, 0x9f, 0xa6,
540 0x73, 0x4f, 0xeb, 0x0d, 0xad, 0xbf, 0xc0, 0x63,
541 0x5c, 0xdc, 0x46, 0x51, 0xe8, 0x8e, 0x90, 0x19,
542 0xa8, 0xa4, 0x3c, 0x91, 0x79, 0xfa, 0x7e, 0x58,
543 0x85, 0x13, 0x55, 0xc5, 0x19, 0x82, 0x37, 0x1b,
544 0x0a, 0x02, 0x1f, 0x99, 0x6b, 0x18, 0xf1, 0x28,
545 0x08, 0xa2, 0x73, 0xb8, 0x0f, 0x2e, 0xcd, 0xbf,
546 0xf3, 0x86, 0x7f, 0xea, 0xef, 0xd0, 0xbb, 0xa6,
547 0x21, 0xdf, 0x49, 0x73, 0x51, 0xcc, 0x36, 0xd3,
548 0x3e, 0xa0, 0xf8, 0x44, 0xdf, 0xd3, 0xa6, 0xbe,
549 0x8a, 0xd4, 0x57, 0xdd, 0x72, 0x94, 0x61, 0x0f,
550 0x82, 0xd1, 0x07, 0xb8, 0x7c, 0x18, 0x83, 0xdf,
551 0x3a, 0xe5, 0x50, 0x6a, 0x82, 0x20, 0xac, 0xa9,
552 0xa8, 0xff, 0xd9, 0xf3, 0x77, 0x33, 0x5a, 0x9e,
553 0x7f, 0x6d, 0xfe, 0x5d, 0x33, 0x41, 0x42, 0xe7,
554 0x6c, 0x19, 0xe0, 0x44, 0x8a, 0x15, 0xf6, 0x70,
555 0x98, 0xb7, 0x68, 0x4d, 0xfa, 0x97, 0x39, 0xb0,
556 0x8e, 0xe8, 0x84, 0x8b, 0x75, 0x30, 0xb7, 0x7d,
557 0x92, 0x69, 0x20, 0x9c, 0x81, 0xfb, 0x4b, 0xf4,
558 0x01, 0x50, 0xeb, 0xce, 0x0c, 0x1c, 0x6c, 0xb5,
559 0x4a, 0xd7, 0x27, 0x0c, 0xce, 0xbb, 0xe5, 0x85,
560 0xf0, 0xb6, 0xee, 0xd5, 0x70, 0xdd, 0x3b, 0xfc,
561 0xd4, 0x99, 0xf1, 0x33, 0xdd, 0x8b, 0xc4, 0x2f,
562 0xae, 0xab, 0x74, 0x96, 0x32, 0xc7, 0x4c, 0x56,
563 0x3c, 0x89, 0x0f, 0x96, 0x0b, 0x42, 0xc0, 0xcb,
564 0xee, 0x0f, 0x0b, 0x8c, 0xfb, 0x7e, 0x47, 0x7b,
565 0x64, 0x48, 0xfd, 0xb2, 0x00, 0x80, 0x89, 0xa5,
566 0x13, 0x55, 0x62, 0xfc, 0x8f, 0xe2, 0x42, 0x03,
567 0xb7, 0x4e, 0x2a, 0x79, 0xb4, 0x82, 0xea, 0x23,
568 0x49, 0xda, 0xaf, 0x52, 0x63, 0x1e, 0x60, 0x03,
569 0x89, 0x06, 0x44, 0x46, 0x08, 0xc3, 0xc4, 0x87,
570 0x70, 0x2e, 0xda, 0x94, 0xad, 0x6b, 0xe0, 0xe4,
571 0xd1, 0x8a, 0x06, 0xc2, 0xa8, 0xc0, 0xa7, 0x43,
572 0x3c, 0x47, 0x52, 0x0e, 0xc3, 0x77, 0x81, 0x11,
573 0x67, 0x0e, 0xa0, 0x70, 0x04, 0x47, 0x29, 0x40,
574 0x86, 0x0d, 0x34, 0x56, 0xa7, 0xc9, 0x35, 0x59,
575 0x68, 0xdc, 0x93, 0x81, 0x70, 0xee, 0x86, 0xd9,
576 0x80, 0x06, 0x40, 0x4f, 0x1a, 0x0d, 0x40, 0x30,
577 0x0b, 0xcb, 0x96, 0x47, 0xc1, 0xb7, 0x52, 0xfd,
578 0x56, 0xe0, 0x72, 0x4b, 0xfb, 0xbd, 0x92, 0x45,
579 0x61, 0x71, 0xc2, 0x33, 0x11, 0xbf, 0x52, 0x83,
580 0x79, 0x26, 0xe0, 0x49, 0x6b, 0xb7, 0x05, 0x8b,
581 0xe8, 0x0e, 0x87, 0x31, 0xd7, 0x9d, 0x8a, 0xf5,
582 0xc0, 0x5f, 0x2e, 0x58, 0x4a, 0xdb, 0x11, 0xb3,
583 0x6c, 0x30, 0x2a, 0x46, 0x19, 0xe3, 0x27, 0x84,
584 0x1f, 0x63, 0x6e, 0xf6, 0x57, 0xc7, 0xc9, 0xd8,
585 0x5e, 0xba, 0xb3, 0x87, 0xd5, 0x83, 0x26, 0x34,
586 0x21, 0x9e, 0x65, 0xde, 0x42, 0xd3, 0xbe, 0x7b,
587 0xbc, 0x91, 0x71, 0x44, 0x4d, 0x99, 0x3b, 0x31,
588 0xe5, 0x3f, 0x11, 0x4e, 0x7f, 0x13, 0x51, 0x3b,
589 0xae, 0x79, 0xc9, 0xd3, 0x81, 0x8e, 0x25, 0x40,
590 0x10, 0xfc, 0x07, 0x1e, 0xf9, 0x7b, 0x9a, 0x4b,
591 0x6c, 0xe3, 0xb3, 0xad, 0x1a, 0x0a, 0xdd, 0x9e,
592 0x59, 0x0c, 0xa2, 0xcd, 0xae, 0x48, 0x4a, 0x38,
593 0x5b, 0x47, 0x41, 0x94, 0x65, 0x6b, 0xbb, 0xeb,
594 0x5b, 0xe3, 0xaf, 0x07, 0x5b, 0xd4, 0x4a, 0xa2,
595 0xc9, 0x5d, 0x2f, 0x64, 0x03, 0xd7, 0x3a, 0x2c,
596 0x6e, 0xce, 0x76, 0x95, 0xb4, 0xb3, 0xc0, 0xf1,
597 0xe2, 0x45, 0x73, 0x7a, 0x5c, 0xab, 0xc1, 0xfc,
598 0x02, 0x8d, 0x81, 0x29, 0xb3, 0xac, 0x07, 0xec,
599 0x40, 0x7d, 0x45, 0xd9, 0x7a, 0x59, 0xee, 0x34,
600 0xf0, 0xe9, 0xd5, 0x7b, 0x96, 0xb1, 0x3d, 0x95,
601 0xcc, 0x86, 0xb5, 0xb6, 0x04, 0x2d, 0xb5, 0x92,
602 0x7e, 0x76, 0xf4, 0x06, 0xa9, 0xa3, 0x12, 0x0f,
603 0xb1, 0xaf, 0x26, 0xba, 0x7c, 0xfc, 0x7e, 0x1c,
604 0xbc, 0x2c, 0x49, 0x97, 0x53, 0x60, 0x13, 0x0b,
605 0xa6, 0x61, 0x83, 0x89, 0x42, 0xd4, 0x17, 0x0c,
606 0x6c, 0x26, 0x52, 0xc3, 0xb3, 0xd4, 0x67, 0xf5,
607 0xe3, 0x04, 0xb7, 0xf4, 0xcb, 0x80, 0xb8, 0xcb,
608 0x77, 0x56, 0x3e, 0xaa, 0x57, 0x54, 0xee, 0xb4,
609 0x2c, 0x67, 0xcf, 0xf2, 0xdc, 0xbe, 0x55, 0xf9,
610 0x43, 0x1f, 0x6e, 0x22, 0x97, 0x67, 0x7f, 0xc4,
611 0xef, 0xb1, 0x26, 0x31, 0x1e, 0x27, 0xdf, 0x41,
612 0x80, 0x47, 0x6c, 0xe2, 0xfa, 0xa9, 0x8c, 0x2a,
613 0xf6, 0xf2, 0xab, 0xf0, 0x15, 0xda, 0x6c, 0xc8,
614 0xfe, 0xb5, 0x23, 0xde, 0xa9, 0x05, 0x3f, 0x06,
615 0x54, 0x4c, 0xcd, 0xe1, 0xab, 0xfc, 0x0e, 0x62,
616 0x33, 0x31, 0x73, 0x2c, 0x76, 0xcb, 0xb4, 0x47,
617 0x1e, 0x20, 0xad, 0xd8, 0xf2, 0x31, 0xdd, 0xc4,
618 0x8b, 0x0c, 0x77, 0xbe, 0xe1, 0x8b, 0x26, 0x00,
619 0x02, 0x58, 0xd6, 0x8d, 0xef, 0xad, 0x74, 0x67,
620 0xab, 0x3f, 0xef, 0xcb, 0x6f, 0xb0, 0xcc, 0x81,
621 0x44, 0x4c, 0xaf, 0xe9, 0x49, 0x4f, 0xdb, 0xa0,
622 0x25, 0xa4, 0xf0, 0x89, 0xf1, 0xbe, 0xd8, 0x10,
623 0xff, 0xb1, 0x3b, 0x4b, 0xfa, 0x98, 0xf5, 0x79,
624 0x6d, 0x1e, 0x69, 0x4d, 0x57, 0xb1, 0xc8, 0x19,
625 0x1b, 0xbd, 0x1e, 0x8c, 0x84, 0xb7, 0x7b, 0xe8,
626 0xd2, 0x2d, 0x09, 0x41, 0x41, 0x37, 0x3d, 0xb1,
627 0x6f, 0x26, 0x5d, 0x71, 0x16, 0x3d, 0xb7, 0x83,
628 0x27, 0x2c, 0xa7, 0xb6, 0x50, 0xbd, 0x91, 0x86,
629 0xab, 0x24, 0xa1, 0x38, 0xfd, 0xea, 0x71, 0x55,
630 0x7e, 0x9a, 0x07, 0x77, 0x4b, 0xfa, 0x61, 0x66,
631 0x20, 0x1e, 0x28, 0x95, 0x18, 0x1b, 0xa4, 0xa0,
632 0xfd, 0xc0, 0x89, 0x72, 0x43, 0xd9, 0x3b, 0x49,
633 0x5a, 0x3f, 0x9d, 0xbf, 0xdb, 0xb4, 0x46, 0xea,
634 0x42, 0x01, 0x77, 0x23, 0x68, 0x95, 0xb6, 0x24,
635 0xb3, 0xa8, 0x6c, 0x28, 0x3b, 0x11, 0x40, 0x7e,
636 0x18, 0x65, 0x6d, 0xd8, 0x24, 0x42, 0x7d, 0x88,
637 0xc0, 0x52, 0xd9, 0x05, 0xe4, 0x95, 0x90, 0x87,
638 0x8c, 0xf4, 0xd0, 0x6b, 0xb9, 0x83, 0x99, 0x34,
639 0x6d, 0xfe, 0x54, 0x40, 0x94, 0x52, 0x21, 0x4f,
640 0x14, 0x25, 0xc5, 0xd6, 0x5e, 0x95, 0xdc, 0x0a,
641 0x2b, 0x89, 0x20, 0x11, 0x84, 0x48, 0xd6, 0x3a,
642 0xcd, 0x5c, 0x24, 0xad, 0x62, 0xe3, 0xb1, 0x93,
643 0x25, 0x8d, 0xcd, 0x7e, 0xfc, 0x27, 0xa3, 0x37,
644 0xfd, 0x84, 0xfc, 0x1b, 0xb2, 0xf1, 0x27, 0x38,
645 0x5a, 0xb7, 0xfc, 0xf2, 0xfa, 0x95, 0x66, 0xd4,
646 0xfb, 0xba, 0xa7, 0xd7, 0xa3, 0x72, 0x69, 0x48,
647 0x48, 0x8c, 0xeb, 0x28, 0x89, 0xfe, 0x33, 0x65,
648 0x5a, 0x36, 0x01, 0x7e, 0x06, 0x79, 0x0a, 0x09,
649 0x3b, 0x74, 0x11, 0x9a, 0x6e, 0xbf, 0xd4, 0x9e,
650 0x58, 0x90, 0x49, 0x4f, 0x4d, 0x08, 0xd4, 0xe5,
651 0x4a, 0x09, 0x21, 0xef, 0x8b, 0xb8, 0x74, 0x3b,
652 0x91, 0xdd, 0x36, 0x85, 0x60, 0x2d, 0xfa, 0xd4,
653 0x45, 0x7b, 0x45, 0x53, 0xf5, 0x47, 0x87, 0x7e,
654 0xa6, 0x37, 0xc8, 0x78, 0x7a, 0x68, 0x9d, 0x8d,
655 0x65, 0x2c, 0x0e, 0x91, 0x5c, 0xa2, 0x60, 0xf0,
656 0x8e, 0x3f, 0xe9, 0x1a, 0xcd, 0xaa, 0xe7, 0xd5,
657 0x77, 0x18, 0xaf, 0xc9, 0xbc, 0x18, 0xea, 0x48,
658 0x1b, 0xfb, 0x22, 0x48, 0x70, 0x16, 0x29, 0x9e,
659 0x5b, 0xc1, 0x2c, 0x66, 0x23, 0xbc, 0xf0, 0x1f,
660 0xef, 0xaf, 0xe4, 0xd6, 0x04, 0x19, 0x82, 0x7a,
661 0x0b, 0xba, 0x4b, 0x46, 0xb1, 0x6a, 0x85, 0x5d,
662 0xb4, 0x73, 0xd6, 0x21, 0xa1, 0x71, 0x60, 0x14,
663 0xee, 0x0a, 0x77, 0xc4, 0x66, 0x2e, 0xf9, 0x69,
664 0x30, 0xaf, 0x41, 0x0b, 0xc8, 0x83, 0x3c, 0x53,
665 0x99, 0x19, 0x27, 0x46, 0xf7, 0x41, 0x6e, 0x56,
666 0xdc, 0x94, 0x28, 0x67, 0x4e, 0xb7, 0x25, 0x48,
667 0x8a, 0xc2, 0xe0, 0x60, 0x96, 0xcc, 0x18, 0xf4,
668 0x84, 0xdd, 0xa7, 0x5e, 0x3e, 0x05, 0x0b, 0x26,
669 0x26, 0xb2, 0x5c, 0x1f, 0x57, 0x1a, 0x04, 0x7e,
670 0x6a, 0xe3, 0x2f, 0xb4, 0x35, 0xb6, 0x38, 0x40,
671 0x40, 0xcd, 0x6f, 0x87, 0x2e, 0xef, 0xa3, 0xd7,
672 0xa9, 0xc2, 0xe8, 0x0d, 0x27, 0xdf, 0x44, 0x62,
673 0x99, 0xa0, 0xfc, 0xcf, 0x81, 0x78, 0xcb, 0xfe,
674 0xe5, 0xa0, 0x03, 0x4e, 0x6c, 0xd7, 0xf4, 0xaf,
675 0x7a, 0xbb, 0x61, 0x82, 0xfe, 0x71, 0x89, 0xb2,
676 0x22, 0x7c, 0x8e, 0x83, 0x04, 0xce, 0xf6, 0x5d,
677 0x84, 0x8f, 0x95, 0x6a, 0x7f, 0xad, 0xfd, 0x32,
678 0x9c, 0x5e, 0xe4, 0x9c, 0x89, 0x60, 0x54, 0xaa,
679 0x96, 0x72, 0xd2, 0xd7, 0x36, 0x85, 0xa9, 0x45,
680 0xd2, 0x2a, 0xa1, 0x81, 0x49, 0x6f, 0x7e, 0x04,
681 0xfa, 0xe2, 0xfe, 0x90, 0x26, 0x77, 0x5a, 0x33,
682 0xb8, 0x04, 0x9a, 0x7a, 0xe6, 0x4c, 0x4f, 0xad,
683 0x72, 0x96, 0x08, 0x28, 0x58, 0x13, 0xf8, 0xc4,
684 0x1c, 0xf0, 0xc3, 0x45, 0x95, 0x49, 0x20, 0x8c,
685 0x9f, 0x39, 0x70, 0xe1, 0x77, 0xfe, 0xd5, 0x4b,
686 0xaf, 0x86, 0xda, 0xef, 0x22, 0x06, 0x83, 0x36,
687 0x29, 0x12, 0x11, 0x40, 0xbc, 0x3b, 0x86, 0xaa,
688 0xaa, 0x65, 0x60, 0xc3, 0x80, 0xca, 0xed, 0xa9,
689 0xf3, 0xb0, 0x79, 0x96, 0xa2, 0x55, 0x27, 0x28,
690 0x55, 0x73, 0x26, 0xa5, 0x50, 0xea, 0x92, 0x4b,
691 0x3c, 0x5c, 0x82, 0x33, 0xf0, 0x01, 0x3f, 0x03,
692 0xc1, 0x08, 0x05, 0xbf, 0x98, 0xf4, 0x9b, 0x6d,
693 0xa5, 0xa8, 0xb4, 0x82, 0x0c, 0x06, 0xfa, 0xff,
694 0x2d, 0x08, 0xf3, 0x05, 0x4f, 0x57, 0x2a, 0x39,
695 0xd4, 0x83, 0x0d, 0x75, 0x51, 0xd8, 0x5b, 0x1b,
696 0xd3, 0x51, 0x5a, 0x32, 0x2a, 0x9b, 0x32, 0xb2,
697 0xf2, 0xa4, 0x96, 0x12, 0xf2, 0xae, 0x40, 0x34,
698 0x67, 0xa8, 0xf5, 0x44, 0xd5, 0x35, 0x53, 0xfe,
699 0xa3, 0x60, 0x96, 0x63, 0x0f, 0x1f, 0x6e, 0xb0,
700 0x5a, 0x42, 0xa6, 0xfc, 0x51, 0x0b, 0x60, 0x27,
701 0xbc, 0x06, 0x71, 0xed, 0x65, 0x5b, 0x23, 0x86,
702 0x4a, 0x07, 0x3b, 0x22, 0x07, 0x46, 0xe6, 0x90,
703 0x3e, 0xf3, 0x25, 0x50, 0x1b, 0x4c, 0x7f, 0x03,
704 0x08, 0xa8, 0x36, 0x6b, 0x87, 0xe5, 0xe3, 0xdb,
705 0x9a, 0x38, 0x83, 0xff, 0x9f, 0x1a, 0x9f, 0x57,
706 0xa4, 0x2a, 0xf6, 0x37, 0xbc, 0x1a, 0xff, 0xc9,
707 0x1e, 0x35, 0x0c, 0xc3, 0x7c, 0xa3, 0xb2, 0xe5,
708 0xd2, 0xc6, 0xb4, 0x57, 0x47, 0xe4, 0x32, 0x16,
709 0x6d, 0xa9, 0xae, 0x64, 0xe6, 0x2d, 0x8d, 0xc5,
710 0x8d, 0x50, 0x8e, 0xe8, 0x1a, 0x22, 0x34, 0x2a,
711 0xd9, 0xeb, 0x51, 0x90, 0x4a, 0xb1, 0x41, 0x7d,
712 0x64, 0xf9, 0xb9, 0x0d, 0xf6, 0x23, 0x33, 0xb0,
713 0x33, 0xf4, 0xf7, 0x3f, 0x27, 0x84, 0xc6, 0x0f,
714 0x54, 0xa5, 0xc0, 0x2e, 0xec, 0x0b, 0x3a, 0x48,
715 0x6e, 0x80, 0x35, 0x81, 0x43, 0x9b, 0x90, 0xb1,
716 0xd0, 0x2b, 0xea, 0x21, 0xdc, 0xda, 0x5b, 0x09,
717 0xf4, 0xcc, 0x10, 0xb4, 0xc7, 0xfe, 0x79, 0x51,
718 0xc3, 0xc5, 0xac, 0x88, 0x74, 0x84, 0x0b, 0x4b,
719 0xca, 0x79, 0x16, 0x29, 0xfb, 0x69, 0x54, 0xdf,
720 0x41, 0x7e, 0xe9, 0xc7, 0x8e, 0xea, 0xa5, 0xfe,
721 0xfc, 0x76, 0x0e, 0x90, 0xc4, 0x92, 0x38, 0xad,
722 0x7b, 0x48, 0xe6, 0x6e, 0xf7, 0x21, 0xfd, 0x4e,
723 0x93, 0x0a, 0x7b, 0x41, 0x83, 0x68, 0xfb, 0x57,
724 0x51, 0x76, 0x34, 0xa9, 0x6c, 0x00, 0xaa, 0x4f,
725 0x66, 0x65, 0x98, 0x4a, 0x4f, 0xa3, 0xa0, 0xef,
726 0x69, 0x3f, 0xe3, 0x1c, 0x92, 0x8c, 0xfd, 0xd8,
727 0xe8, 0xde, 0x7c, 0x7f, 0x3e, 0x84, 0x8e, 0x69,
728 0x3c, 0xf1, 0xf2, 0x05, 0x46, 0xdc, 0x2f, 0x9d,
729 0x5e, 0x6e, 0x4c, 0xfb, 0xb5, 0x99, 0x2a, 0x59,
730 0x63, 0xc1, 0x34, 0xbc, 0x57, 0xc0, 0x0d, 0xb9,
731 0x61, 0x25, 0xf3, 0x33, 0x23, 0x51, 0xb6, 0x0d,
732 0x07, 0xa6, 0xab, 0x94, 0x4a, 0xb7, 0x2a, 0xea,
733 0xee, 0xac, 0xa3, 0xc3, 0x04, 0x8b, 0x0e, 0x56,
734 0xfe, 0x44, 0xa7, 0x39, 0xe2, 0xed, 0xed, 0xb4,
735 0x22, 0x2b, 0xac, 0x12, 0x32, 0x28, 0x91, 0xd8,
736 0xa5, 0xab, 0xff, 0x5f, 0xe0, 0x4b, 0xda, 0x78,
737 0x17, 0xda, 0xf1, 0x01, 0x5b, 0xcd, 0xe2, 0x5f,
738 0x50, 0x45, 0x73, 0x2b, 0xe4, 0x76, 0x77, 0xf4,
739 0x64, 0x1d, 0x43, 0xfb, 0x84, 0x7a, 0xea, 0x91,
740 0xae, 0xf9, 0x9e, 0xb7, 0xb4, 0xb0, 0x91, 0x5f,
741 0x16, 0x35, 0x9a, 0x11, 0xb8, 0xc7, 0xc1, 0x8c,
742 0xc6, 0x10, 0x8d, 0x2f, 0x63, 0x4a, 0xa7, 0x57,
743 0x3a, 0x51, 0xd6, 0x32, 0x2d, 0x64, 0x72, 0xd4,
744 0x66, 0xdc, 0x10, 0xa6, 0x67, 0xd6, 0x04, 0x23,
745 0x9d, 0x0a, 0x11, 0x77, 0xdd, 0x37, 0x94, 0x17,
746 0x3c, 0xbf, 0x8b, 0x65, 0xb0, 0x2e, 0x5e, 0x66,
747 0x47, 0x64, 0xac, 0xdd, 0xf0, 0x84, 0xfd, 0x39,
748 0xfa, 0x15, 0x5d, 0xef, 0xae, 0xca, 0xc1, 0x36,
749 0xa7, 0x5c, 0xbf, 0xc7, 0x08, 0xc2, 0x66, 0x00,
750 0x74, 0x74, 0x4e, 0x27, 0x3f, 0x55, 0x8a, 0xb7,
751 0x38, 0x66, 0x83, 0x6d, 0xcf, 0x99, 0x9e, 0x60,
752 0x8f, 0xdd, 0x2e, 0x62, 0x22, 0x0e, 0xef, 0x0c,
753 0x98, 0xa7, 0x85, 0x74, 0x3b, 0x9d, 0xec, 0x9e,
754 0xa9, 0x19, 0x72, 0xa5, 0x7f, 0x2c, 0x39, 0xb7,
755 0x7d, 0xb7, 0xf1, 0x12, 0x65, 0x27, 0x4b, 0x5a,
756 0xde, 0x17, 0xfe, 0xad, 0x44, 0xf3, 0x20, 0x4d,
757 0xfd, 0xe4, 0x1f, 0xb5, 0x81, 0xb0, 0x36, 0x37,
758 0x08, 0x6f, 0xc3, 0x0c, 0xe9, 0x85, 0x98, 0x82,
759 0xa9, 0x62, 0x0c, 0xc4, 0x97, 0xc0, 0x50, 0xc8,
760 0xa7, 0x3c, 0x50, 0x9f, 0x43, 0xb9, 0xcd, 0x5e,
761 0x4d, 0xfa, 0x1c, 0x4b, 0x0b, 0xa9, 0x98, 0x85,
762 0x38, 0x92, 0xac, 0x8d, 0xe4, 0xad, 0x9b, 0x98,
763 0xab, 0xd9, 0x38, 0xac, 0x62, 0x52, 0xa3, 0x22,
764 0x63, 0x0f, 0xbf, 0x95, 0x48, 0xdf, 0x69, 0xe7,
765 0x8b, 0x33, 0xd5, 0xb2, 0xbd, 0x05, 0x49, 0x49,
766 0x9d, 0x57, 0x73, 0x19, 0x33, 0xae, 0xfa, 0x33,
767 0xf1, 0x19, 0xa8, 0x80, 0xce, 0x04, 0x9f, 0xbc,
768 0x1d, 0x65, 0x82, 0x1b, 0xe5, 0x3a, 0x51, 0xc8,
769 0x1c, 0x21, 0xe3, 0x5d, 0xf3, 0x7d, 0x9b, 0x2f,
770 0x2c, 0x1d, 0x4a, 0x7f, 0x9b, 0x68, 0x35, 0xa3,
771 0xb2, 0x50, 0xf7, 0x62, 0x79, 0xcd, 0xf4, 0x98,
772 0x4f, 0xe5, 0x63, 0x7c, 0x3e, 0x45, 0x31, 0x8c,
773 0x16, 0xa0, 0x12, 0xc8, 0x58, 0xce, 0x39, 0xa6,
774 0xbc, 0x54, 0xdb, 0xc5, 0xe0, 0xd5, 0xba, 0xbc,
775 0xb9, 0x04, 0xf4, 0x8d, 0xe8, 0x2f, 0x15, 0x9d,
776};
777
778/* 100 test cases */
779static struct crc_test {
780 u32 crc; /* random starting crc */
781 u32 start; /* random 6 bit offset in buf */
782 u32 length; /* random 11 bit length of test */
783 u32 crc_le; /* expected crc32_le result */
784 u32 crc_be; /* expected crc32_be result */
785 u32 crc32c_le; /* expected crc32c_le result */
786} test[] =
787{
788 {0x674bf11d, 0x00000038, 0x00000542, 0x0af6d466, 0xd8b6e4c1,
789 0xf6e93d6c},
790 {0x35c672c6, 0x0000003a, 0x000001aa, 0xc6d3dfba, 0x28aaf3ad,
791 0x0fe92aca},
792 {0x496da28e, 0x00000039, 0x000005af, 0xd933660f, 0x5d57e81f,
793 0x52e1ebb8},
794 {0x09a9b90e, 0x00000027, 0x000001f8, 0xb45fe007, 0xf45fca9a,
795 0x0798af9a},
796 {0xdc97e5a9, 0x00000025, 0x000003b6, 0xf81a3562, 0xe0126ba2,
797 0x18eb3152},
798 {0x47c58900, 0x0000000a, 0x000000b9, 0x8e58eccf, 0xf3afc793,
799 0xd00d08c7},
800 {0x292561e8, 0x0000000c, 0x00000403, 0xa2ba8aaf, 0x0b797aed,
801 0x8ba966bc},
802 {0x415037f6, 0x00000003, 0x00000676, 0xa17d52e8, 0x7f0fdf35,
803 0x11d694a2},
804 {0x3466e707, 0x00000026, 0x00000042, 0x258319be, 0x75c484a2,
805 0x6ab3208d},
806 {0xafd1281b, 0x00000023, 0x000002ee, 0x4428eaf8, 0x06c7ad10,
807 0xba4603c5},
808 {0xd3857b18, 0x00000028, 0x000004a2, 0x5c430821, 0xb062b7cb,
809 0xe6071c6f},
810 {0x1d825a8f, 0x0000002b, 0x0000050b, 0xd2c45f0c, 0xd68634e0,
811 0x179ec30a},
812 {0x5033e3bc, 0x0000000b, 0x00000078, 0xa3ea4113, 0xac6d31fb,
813 0x0903beb8},
814 {0x94f1fb5e, 0x0000000f, 0x000003a2, 0xfbfc50b1, 0x3cfe50ed,
815 0x6a7cb4fa},
816 {0xc9a0fe14, 0x00000009, 0x00000473, 0x5fb61894, 0x87070591,
817 0xdb535801},
818 {0x88a034b1, 0x0000001c, 0x000005ad, 0xc1b16053, 0x46f95c67,
819 0x92bed597},
820 {0xf0f72239, 0x00000020, 0x0000026d, 0xa6fa58f3, 0xf8c2c1dd,
821 0x192a3f1b},
822 {0xcc20a5e3, 0x0000003b, 0x0000067a, 0x7740185a, 0x308b979a,
823 0xccbaec1a},
824 {0xce589c95, 0x0000002b, 0x00000641, 0xd055e987, 0x40aae25b,
825 0x7eabae4d},
826 {0x78edc885, 0x00000035, 0x000005be, 0xa39cb14b, 0x035b0d1f,
827 0x28c72982},
828 {0x9d40a377, 0x0000003b, 0x00000038, 0x1f47ccd2, 0x197fbc9d,
829 0xc3cd4d18},
830 {0x703d0e01, 0x0000003c, 0x000006f1, 0x88735e7c, 0xfed57c5a,
831 0xbca8f0e7},
832 {0x776bf505, 0x0000000f, 0x000005b2, 0x5cc4fc01, 0xf32efb97,
833 0x713f60b3},
834 {0x4a3e7854, 0x00000027, 0x000004b8, 0x8d923c82, 0x0cbfb4a2,
835 0xebd08fd5},
836 {0x209172dd, 0x0000003b, 0x00000356, 0xb89e9c2b, 0xd7868138,
837 0x64406c59},
838 {0x3ba4cc5b, 0x0000002f, 0x00000203, 0xe51601a9, 0x5b2a1032,
839 0x7421890e},
840 {0xfc62f297, 0x00000000, 0x00000079, 0x71a8e1a2, 0x5d88685f,
841 0xe9347603},
842 {0x64280b8b, 0x00000016, 0x000007ab, 0x0fa7a30c, 0xda3a455f,
843 0x1bef9060},
844 {0x97dd724b, 0x00000033, 0x000007ad, 0x5788b2f4, 0xd7326d32,
845 0x34720072},
846 {0x61394b52, 0x00000035, 0x00000571, 0xc66525f1, 0xcabe7fef,
847 0x48310f59},
848 {0x29b4faff, 0x00000024, 0x0000006e, 0xca13751e, 0x993648e0,
849 0x783a4213},
850 {0x29bfb1dc, 0x0000000b, 0x00000244, 0x436c43f7, 0x429f7a59,
851 0x9e8efd41},
852 {0x86ae934b, 0x00000035, 0x00000104, 0x0760ec93, 0x9cf7d0f4,
853 0xfc3d34a5},
854 {0xc4c1024e, 0x0000002e, 0x000006b1, 0x6516a3ec, 0x19321f9c,
855 0x17a52ae2},
856 {0x3287a80a, 0x00000026, 0x00000496, 0x0b257eb1, 0x754ebd51,
857 0x886d935a},
858 {0xa4db423e, 0x00000023, 0x0000045d, 0x9b3a66dc, 0x873e9f11,
859 0xeaaeaeb2},
860 {0x7a1078df, 0x00000015, 0x0000014a, 0x8c2484c5, 0x6a628659,
861 0x8e900a4b},
862 {0x6048bd5b, 0x00000006, 0x0000006a, 0x897e3559, 0xac9961af,
863 0xd74662b1},
864 {0xd8f9ea20, 0x0000003d, 0x00000277, 0x60eb905b, 0xed2aaf99,
865 0xd26752ba},
866 {0xea5ec3b4, 0x0000002a, 0x000004fe, 0x869965dc, 0x6c1f833b,
867 0x8b1fcd62},
868 {0x2dfb005d, 0x00000016, 0x00000345, 0x6a3b117e, 0xf05e8521,
869 0xf54342fe},
870 {0x5a214ade, 0x00000020, 0x000005b6, 0x467f70be, 0xcb22ccd3,
871 0x5b95b988},
872 {0xf0ab9cca, 0x00000032, 0x00000515, 0xed223df3, 0x7f3ef01d,
873 0x2e1176be},
874 {0x91b444f9, 0x0000002e, 0x000007f8, 0x84e9a983, 0x5676756f,
875 0x66120546},
876 {0x1b5d2ddb, 0x0000002e, 0x0000012c, 0xba638c4c, 0x3f42047b,
877 0xf256a5cc},
878 {0xd824d1bb, 0x0000003a, 0x000007b5, 0x6288653b, 0x3a3ebea0,
879 0x4af1dd69},
880 {0x0470180c, 0x00000034, 0x000001f0, 0x9d5b80d6, 0x3de08195,
881 0x56f0a04a},
882 {0xffaa3a3f, 0x00000036, 0x00000299, 0xf3a82ab8, 0x53e0c13d,
883 0x74f6b6b2},
884 {0x6406cfeb, 0x00000023, 0x00000600, 0xa920b8e8, 0xe4e2acf4,
885 0x085951fd},
886 {0xb24aaa38, 0x0000003e, 0x000004a1, 0x657cc328, 0x5077b2c3,
887 0xc65387eb},
888 {0x58b2ab7c, 0x00000039, 0x000002b4, 0x3a17ee7e, 0x9dcb3643,
889 0x1ca9257b},
890 {0x3db85970, 0x00000006, 0x000002b6, 0x95268b59, 0xb9812c10,
891 0xfd196d76},
892 {0x857830c5, 0x00000003, 0x00000590, 0x4ef439d5, 0xf042161d,
893 0x5ef88339},
894 {0xe1fcd978, 0x0000003e, 0x000007d8, 0xae8d8699, 0xce0a1ef5,
895 0x2c3714d9},
896 {0xb982a768, 0x00000016, 0x000006e0, 0x62fad3df, 0x5f8a067b,
897 0x58576548},
898 {0x1d581ce8, 0x0000001e, 0x0000058b, 0xf0f5da53, 0x26e39eee,
899 0xfd7c57de},
900 {0x2456719b, 0x00000025, 0x00000503, 0x4296ac64, 0xd50e4c14,
901 0xd5fedd59},
902 {0xfae6d8f2, 0x00000000, 0x0000055d, 0x057fdf2e, 0x2a31391a,
903 0x1cc3b17b},
904 {0xcba828e3, 0x00000039, 0x000002ce, 0xe3f22351, 0x8f00877b,
905 0x270eed73},
906 {0x13d25952, 0x0000000a, 0x0000072d, 0x76d4b4cc, 0x5eb67ec3,
907 0x91ecbb11},
908 {0x0342be3f, 0x00000015, 0x00000599, 0xec75d9f1, 0x9d4d2826,
909 0x05ed8d0c},
910 {0xeaa344e0, 0x00000014, 0x000004d8, 0x72a4c981, 0x2064ea06,
911 0x0b09ad5b},
912 {0xbbb52021, 0x0000003b, 0x00000272, 0x04af99fc, 0xaf042d35,
913 0xf8d511fb},
914 {0xb66384dc, 0x0000001d, 0x000007fc, 0xd7629116, 0x782bd801,
915 0x5ad832cc},
916 {0x616c01b6, 0x00000022, 0x000002c8, 0x5b1dab30, 0x783ce7d2,
917 0x1214d196},
918 {0xce2bdaad, 0x00000016, 0x0000062a, 0x932535c8, 0x3f02926d,
919 0x5747218a},
920 {0x00fe84d7, 0x00000005, 0x00000205, 0x850e50aa, 0x753d649c,
921 0xde8f14de},
922 {0xbebdcb4c, 0x00000006, 0x0000055d, 0xbeaa37a2, 0x2d8c9eba,
923 0x3563b7b9},
924 {0xd8b1a02a, 0x00000010, 0x00000387, 0x5017d2fc, 0x503541a5,
925 0x071475d0},
926 {0x3b96cad2, 0x00000036, 0x00000347, 0x1d2372ae, 0x926cd90b,
927 0x54c79d60},
928 {0xc94c1ed7, 0x00000005, 0x0000038b, 0x9e9fdb22, 0x144a9178,
929 0x4c53eee6},
930 {0x1aad454e, 0x00000025, 0x000002b2, 0xc3f6315c, 0x5c7a35b3,
931 0x10137a3c},
932 {0xa4fec9a6, 0x00000000, 0x000006d6, 0x90be5080, 0xa4107605,
933 0xaa9d6c73},
934 {0x1bbe71e2, 0x0000001f, 0x000002fd, 0x4e504c3b, 0x284ccaf1,
935 0xb63d23e7},
936 {0x4201c7e4, 0x00000002, 0x000002b7, 0x7822e3f9, 0x0cc912a9,
937 0x7f53e9cf},
938 {0x23fddc96, 0x00000003, 0x00000627, 0x8a385125, 0x07767e78,
939 0x13c1cd83},
940 {0xd82ba25c, 0x00000016, 0x0000063e, 0x98e4148a, 0x283330c9,
941 0x49ff5867},
942 {0x786f2032, 0x0000002d, 0x0000060f, 0xf201600a, 0xf561bfcd,
943 0x8467f211},
944 {0xfebe4e1f, 0x0000002a, 0x000004f2, 0x95e51961, 0xfd80dcab,
945 0x3f9683b2},
946 {0x1a6e0a39, 0x00000008, 0x00000672, 0x8af6c2a5, 0x78dd84cb,
947 0x76a3f874},
948 {0x56000ab8, 0x0000000e, 0x000000e5, 0x36bacb8f, 0x22ee1f77,
949 0x863b702f},
950 {0x4717fe0c, 0x00000000, 0x000006ec, 0x8439f342, 0x5c8e03da,
951 0xdc6c58ff},
952 {0xd5d5d68e, 0x0000003c, 0x000003a3, 0x46fff083, 0x177d1b39,
953 0x0622cc95},
954 {0xc25dd6c6, 0x00000024, 0x000006c0, 0x5ceb8eb4, 0x892b0d16,
955 0xe85605cd},
956 {0xe9b11300, 0x00000023, 0x00000683, 0x07a5d59a, 0x6c6a3208,
957 0x31da5f06},
958 {0x95cd285e, 0x00000001, 0x00000047, 0x7b3a4368, 0x0202c07e,
959 0xa1f2e784},
960 {0xd9245a25, 0x0000001e, 0x000003a6, 0xd33c1841, 0x1936c0d5,
961 0xb07cc616},
962 {0x103279db, 0x00000006, 0x0000039b, 0xca09b8a0, 0x77d62892,
963 0xbf943b6c},
964 {0x1cba3172, 0x00000027, 0x000001c8, 0xcb377194, 0xebe682db,
965 0x2c01af1c},
966 {0x8f613739, 0x0000000c, 0x000001df, 0xb4b0bc87, 0x7710bd43,
967 0x0fe5f56d},
968 {0x1c6aa90d, 0x0000001b, 0x0000053c, 0x70559245, 0xda7894ac,
969 0xf8943b2d},
970 {0xaabe5b93, 0x0000003d, 0x00000715, 0xcdbf42fa, 0x0c3b99e7,
971 0xe4d89272},
972 {0xf15dd038, 0x00000006, 0x000006db, 0x6e104aea, 0x8d5967f2,
973 0x7c2f6bbb},
974 {0x584dd49c, 0x00000020, 0x000007bc, 0x36b6cfd6, 0xad4e23b2,
975 0xabbf388b},
976 {0x5d8c9506, 0x00000020, 0x00000470, 0x4c62378e, 0x31d92640,
977 0x1dca1f4e},
978 {0xb80d17b0, 0x00000032, 0x00000346, 0x22a5bb88, 0x9a7ec89f,
979 0x5c170e23},
980 {0xdaf0592e, 0x00000023, 0x000007b0, 0x3cab3f99, 0x9b1fdd99,
981 0xc0e9d672},
982 {0x4793cc85, 0x0000000d, 0x00000706, 0xe82e04f6, 0xed3db6b7,
983 0xc18bdc86},
984 {0x82ebf64e, 0x00000009, 0x000007c3, 0x69d590a9, 0x9efa8499,
985 0xa874fcdd},
986 {0xb18a0319, 0x00000026, 0x000007db, 0x1cf98dcc, 0x8fa9ad6a,
987 0x9dc0bb48},
988};
989
990#include <linux/time.h>
991
992static int __init crc32c_test(void)
993{
994 int i;
995 int errors = 0;
996 int bytes = 0;
997 struct timespec start, stop;
998 u64 nsec;
999 unsigned long flags;
1000
1001 /* keep static to prevent cache warming code from
1002 * getting eliminated by the compiler */
1003 static u32 crc;
1004
1005 /* pre-warm the cache */
1006 for (i = 0; i < 100; i++) {
1007 bytes += 2*test[i].length;
1008
1009 crc ^= __crc32c_le(test[i].crc, test_buf +
1010 test[i].start, test[i].length);
1011 }
1012
1013 /* reduce OS noise */
1014 local_irq_save(flags);
1015 local_irq_disable();
1016
1017 getnstimeofday(&start);
1018 for (i = 0; i < 100; i++) {
1019 if (test[i].crc32c_le != __crc32c_le(test[i].crc, test_buf +
1020 test[i].start, test[i].length))
1021 errors++;
1022 }
1023 getnstimeofday(&stop);
1024
1025 local_irq_restore(flags);
1026 local_irq_enable();
1027
1028 nsec = stop.tv_nsec - start.tv_nsec +
1029 1000000000 * (stop.tv_sec - start.tv_sec);
1030
1031 pr_info("crc32c: CRC_LE_BITS = %d\n", CRC_LE_BITS);
1032
1033 if (errors)
1034 pr_warn("crc32c: %d self tests failed\n", errors);
1035 else {
1036 pr_info("crc32c: self tests passed, processed %d bytes in %lld nsec\n",
1037 bytes, nsec);
1038 }
1039
1040 return 0;
1041}
1042
1043static int __init crc32_test(void)
1044{
1045 int i;
1046 int errors = 0;
1047 int bytes = 0;
1048 struct timespec start, stop;
1049 u64 nsec;
1050 unsigned long flags;
1051
1052 /* keep static to prevent cache warming code from
1053 * getting eliminated by the compiler */
1054 static u32 crc;
1055
1056 /* pre-warm the cache */
1057 for (i = 0; i < 100; i++) {
1058 bytes += 2*test[i].length;
1059
1060 crc ^= crc32_le(test[i].crc, test_buf +
1061 test[i].start, test[i].length);
1062
1063 crc ^= crc32_be(test[i].crc, test_buf +
1064 test[i].start, test[i].length);
1065 }
1066
1067 /* reduce OS noise */
1068 local_irq_save(flags);
1069 local_irq_disable();
1070
1071 getnstimeofday(&start);
1072 for (i = 0; i < 100; i++) {
1073 if (test[i].crc_le != crc32_le(test[i].crc, test_buf +
1074 test[i].start, test[i].length))
1075 errors++;
1076
1077 if (test[i].crc_be != crc32_be(test[i].crc, test_buf +
1078 test[i].start, test[i].length))
1079 errors++;
1080 }
1081 getnstimeofday(&stop);
1082
1083 local_irq_restore(flags);
1084 local_irq_enable();
1085
1086 nsec = stop.tv_nsec - start.tv_nsec +
1087 1000000000 * (stop.tv_sec - start.tv_sec);
1088
1089 pr_info("crc32: CRC_LE_BITS = %d, CRC_BE BITS = %d\n",
1090 CRC_LE_BITS, CRC_BE_BITS);
1091
1092 if (errors)
1093 pr_warn("crc32: %d self tests failed\n", errors);
1094 else {
1095 pr_info("crc32: self tests passed, processed %d bytes in %lld nsec\n",
1096 bytes, nsec);
1097 }
1098
1099 return 0;
1100}
1101
1102static int __init crc32test_init(void)
1103{
1104 crc32_test();
1105 crc32c_test();
1106 return 0;
1107}
1108
1109static void __exit crc32_exit(void)
1110{
1111}
1112
1113module_init(crc32test_init);
1114module_exit(crc32_exit);
1115#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 */