Root/
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 <asm/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 | |
44 | MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>"); |
45 | MODULE_DESCRIPTION("Ethernet CRC32 calculations"); |
46 | MODULE_LICENSE("GPL"); |
47 | |
48 | #if CRC_LE_BITS == 8 || CRC_BE_BITS == 8 |
49 | |
50 | static inline u32 |
51 | crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 *tab) |
52 | { |
53 | # ifdef __LITTLE_ENDIAN |
54 | # define DO_CRC(x) crc = tab[(crc ^ (x)) & 255 ] ^ (crc >> 8) |
55 | # else |
56 | # define DO_CRC(x) crc = tab[((crc >> 24) ^ (x)) & 255] ^ (crc << 8) |
57 | # endif |
58 | const u32 *b; |
59 | size_t rem_len; |
60 | |
61 | /* Align it */ |
62 | if (unlikely((long)buf & 3 && len)) { |
63 | do { |
64 | DO_CRC(*buf++); |
65 | } while ((--len) && ((long)buf)&3); |
66 | } |
67 | rem_len = len & 3; |
68 | /* load data 32 bits wide, xor data 32 bits wide. */ |
69 | len = len >> 2; |
70 | b = (const u32 *)buf; |
71 | for (--b; len; --len) { |
72 | crc ^= *++b; /* use pre increment for speed */ |
73 | DO_CRC(0); |
74 | DO_CRC(0); |
75 | DO_CRC(0); |
76 | DO_CRC(0); |
77 | } |
78 | len = rem_len; |
79 | /* And the last few bytes */ |
80 | if (len) { |
81 | u8 *p = (u8 *)(b + 1) - 1; |
82 | do { |
83 | DO_CRC(*++p); /* use pre increment for speed */ |
84 | } while (--len); |
85 | } |
86 | return crc; |
87 | #undef DO_CRC |
88 | } |
89 | #endif |
90 | /** |
91 | * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32 |
92 | * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for |
93 | * other uses, or the previous crc32 value if computing incrementally. |
94 | * @p: pointer to buffer over which CRC is run |
95 | * @len: length of buffer @p |
96 | */ |
97 | u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len); |
98 | |
99 | #if CRC_LE_BITS == 1 |
100 | /* |
101 | * In fact, the table-based code will work in this case, but it can be |
102 | * simplified by inlining the table in ?: form. |
103 | */ |
104 | |
105 | u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) |
106 | { |
107 | int i; |
108 | while (len--) { |
109 | crc ^= *p++; |
110 | for (i = 0; i < 8; i++) |
111 | crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0); |
112 | } |
113 | return crc; |
114 | } |
115 | #else /* Table-based approach */ |
116 | |
117 | u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) |
118 | { |
119 | # if CRC_LE_BITS == 8 |
120 | const u32 *tab = crc32table_le; |
121 | |
122 | crc = __cpu_to_le32(crc); |
123 | crc = crc32_body(crc, p, len, tab); |
124 | return __le32_to_cpu(crc); |
125 | # elif CRC_LE_BITS == 4 |
126 | while (len--) { |
127 | crc ^= *p++; |
128 | crc = (crc >> 4) ^ crc32table_le[crc & 15]; |
129 | crc = (crc >> 4) ^ crc32table_le[crc & 15]; |
130 | } |
131 | return crc; |
132 | # elif CRC_LE_BITS == 2 |
133 | while (len--) { |
134 | crc ^= *p++; |
135 | crc = (crc >> 2) ^ crc32table_le[crc & 3]; |
136 | crc = (crc >> 2) ^ crc32table_le[crc & 3]; |
137 | crc = (crc >> 2) ^ crc32table_le[crc & 3]; |
138 | crc = (crc >> 2) ^ crc32table_le[crc & 3]; |
139 | } |
140 | return crc; |
141 | # endif |
142 | } |
143 | #endif |
144 | |
145 | /** |
146 | * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32 |
147 | * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for |
148 | * other uses, or the previous crc32 value if computing incrementally. |
149 | * @p: pointer to buffer over which CRC is run |
150 | * @len: length of buffer @p |
151 | */ |
152 | u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len); |
153 | |
154 | #if CRC_BE_BITS == 1 |
155 | /* |
156 | * In fact, the table-based code will work in this case, but it can be |
157 | * simplified by inlining the table in ?: form. |
158 | */ |
159 | |
160 | u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) |
161 | { |
162 | int i; |
163 | while (len--) { |
164 | crc ^= *p++ << 24; |
165 | for (i = 0; i < 8; i++) |
166 | crc = |
167 | (crc << 1) ^ ((crc & 0x80000000) ? CRCPOLY_BE : |
168 | 0); |
169 | } |
170 | return crc; |
171 | } |
172 | |
173 | #else /* Table-based approach */ |
174 | u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) |
175 | { |
176 | # if CRC_BE_BITS == 8 |
177 | const u32 *tab = crc32table_be; |
178 | |
179 | crc = __cpu_to_be32(crc); |
180 | crc = crc32_body(crc, p, len, tab); |
181 | return __be32_to_cpu(crc); |
182 | # elif CRC_BE_BITS == 4 |
183 | while (len--) { |
184 | crc ^= *p++ << 24; |
185 | crc = (crc << 4) ^ crc32table_be[crc >> 28]; |
186 | crc = (crc << 4) ^ crc32table_be[crc >> 28]; |
187 | } |
188 | return crc; |
189 | # elif CRC_BE_BITS == 2 |
190 | while (len--) { |
191 | crc ^= *p++ << 24; |
192 | crc = (crc << 2) ^ crc32table_be[crc >> 30]; |
193 | crc = (crc << 2) ^ crc32table_be[crc >> 30]; |
194 | crc = (crc << 2) ^ crc32table_be[crc >> 30]; |
195 | crc = (crc << 2) ^ crc32table_be[crc >> 30]; |
196 | } |
197 | return crc; |
198 | # endif |
199 | } |
200 | #endif |
201 | |
202 | EXPORT_SYMBOL(crc32_le); |
203 | EXPORT_SYMBOL(crc32_be); |
204 | |
205 | /* |
206 | * A brief CRC tutorial. |
207 | * |
208 | * A CRC is a long-division remainder. You add the CRC to the message, |
209 | * and the whole thing (message+CRC) is a multiple of the given |
210 | * CRC polynomial. To check the CRC, you can either check that the |
211 | * CRC matches the recomputed value, *or* you can check that the |
212 | * remainder computed on the message+CRC is 0. This latter approach |
213 | * is used by a lot of hardware implementations, and is why so many |
214 | * protocols put the end-of-frame flag after the CRC. |
215 | * |
216 | * It's actually the same long division you learned in school, except that |
217 | * - We're working in binary, so the digits are only 0 and 1, and |
218 | * - When dividing polynomials, there are no carries. Rather than add and |
219 | * subtract, we just xor. Thus, we tend to get a bit sloppy about |
220 | * the difference between adding and subtracting. |
221 | * |
222 | * A 32-bit CRC polynomial is actually 33 bits long. But since it's |
223 | * 33 bits long, bit 32 is always going to be set, so usually the CRC |
224 | * is written in hex with the most significant bit omitted. (If you're |
225 | * familiar with the IEEE 754 floating-point format, it's the same idea.) |
226 | * |
227 | * Note that a CRC is computed over a string of *bits*, so you have |
228 | * to decide on the endianness of the bits within each byte. To get |
229 | * the best error-detecting properties, this should correspond to the |
230 | * order they're actually sent. For example, standard RS-232 serial is |
231 | * little-endian; the most significant bit (sometimes used for parity) |
232 | * is sent last. And when appending a CRC word to a message, you should |
233 | * do it in the right order, matching the endianness. |
234 | * |
235 | * Just like with ordinary division, the remainder is always smaller than |
236 | * the divisor (the CRC polynomial) you're dividing by. Each step of the |
237 | * division, you take one more digit (bit) of the dividend and append it |
238 | * to the current remainder. Then you figure out the appropriate multiple |
239 | * of the divisor to subtract to being the remainder back into range. |
240 | * In binary, it's easy - it has to be either 0 or 1, and to make the |
241 | * XOR cancel, it's just a copy of bit 32 of the remainder. |
242 | * |
243 | * When computing a CRC, we don't care about the quotient, so we can |
244 | * throw the quotient bit away, but subtract the appropriate multiple of |
245 | * the polynomial from the remainder and we're back to where we started, |
246 | * ready to process the next bit. |
247 | * |
248 | * A big-endian CRC written this way would be coded like: |
249 | * for (i = 0; i < input_bits; i++) { |
250 | * multiple = remainder & 0x80000000 ? CRCPOLY : 0; |
251 | * remainder = (remainder << 1 | next_input_bit()) ^ multiple; |
252 | * } |
253 | * Notice how, to get at bit 32 of the shifted remainder, we look |
254 | * at bit 31 of the remainder *before* shifting it. |
255 | * |
256 | * But also notice how the next_input_bit() bits we're shifting into |
257 | * the remainder don't actually affect any decision-making until |
258 | * 32 bits later. Thus, the first 32 cycles of this are pretty boring. |
259 | * Also, to add the CRC to a message, we need a 32-bit-long hole for it at |
260 | * the end, so we have to add 32 extra cycles shifting in zeros at the |
261 | * end of every message, |
262 | * |
263 | * So the standard trick is to rearrage merging in the next_input_bit() |
264 | * until the moment it's needed. Then the first 32 cycles can be precomputed, |
265 | * and merging in the final 32 zero bits to make room for the CRC can be |
266 | * skipped entirely. |
267 | * This changes the code to: |
268 | * for (i = 0; i < input_bits; i++) { |
269 | * remainder ^= next_input_bit() << 31; |
270 | * multiple = (remainder & 0x80000000) ? CRCPOLY : 0; |
271 | * remainder = (remainder << 1) ^ multiple; |
272 | * } |
273 | * With this optimization, the little-endian code is simpler: |
274 | * for (i = 0; i < input_bits; i++) { |
275 | * remainder ^= next_input_bit(); |
276 | * multiple = (remainder & 1) ? CRCPOLY : 0; |
277 | * remainder = (remainder >> 1) ^ multiple; |
278 | * } |
279 | * |
280 | * Note that the other details of endianness have been hidden in CRCPOLY |
281 | * (which must be bit-reversed) and next_input_bit(). |
282 | * |
283 | * However, as long as next_input_bit is returning the bits in a sensible |
284 | * order, we can actually do the merging 8 or more bits at a time rather |
285 | * than one bit at a time: |
286 | * for (i = 0; i < input_bytes; i++) { |
287 | * remainder ^= next_input_byte() << 24; |
288 | * for (j = 0; j < 8; j++) { |
289 | * multiple = (remainder & 0x80000000) ? CRCPOLY : 0; |
290 | * remainder = (remainder << 1) ^ multiple; |
291 | * } |
292 | * } |
293 | * Or in little-endian: |
294 | * for (i = 0; i < input_bytes; i++) { |
295 | * remainder ^= next_input_byte(); |
296 | * for (j = 0; j < 8; j++) { |
297 | * multiple = (remainder & 1) ? CRCPOLY : 0; |
298 | * remainder = (remainder << 1) ^ multiple; |
299 | * } |
300 | * } |
301 | * If the input is a multiple of 32 bits, you can even XOR in a 32-bit |
302 | * word at a time and increase the inner loop count to 32. |
303 | * |
304 | * You can also mix and match the two loop styles, for example doing the |
305 | * bulk of a message byte-at-a-time and adding bit-at-a-time processing |
306 | * for any fractional bytes at the end. |
307 | * |
308 | * The only remaining optimization is to the byte-at-a-time table method. |
309 | * Here, rather than just shifting one bit of the remainder to decide |
310 | * in the correct multiple to subtract, we can shift a byte at a time. |
311 | * This produces a 40-bit (rather than a 33-bit) intermediate remainder, |
312 | * but again the multiple of the polynomial to subtract depends only on |
313 | * the high bits, the high 8 bits in this case. |
314 | * |
315 | * The multiple we need in that case is the low 32 bits of a 40-bit |
316 | * value whose high 8 bits are given, and which is a multiple of the |
317 | * generator polynomial. This is simply the CRC-32 of the given |
318 | * one-byte message. |
319 | * |
320 | * Two more details: normally, appending zero bits to a message which |
321 | * is already a multiple of a polynomial produces a larger multiple of that |
322 | * polynomial. To enable a CRC to detect this condition, it's common to |
323 | * invert the CRC before appending it. This makes the remainder of the |
324 | * message+crc come out not as zero, but some fixed non-zero value. |
325 | * |
326 | * The same problem applies to zero bits prepended to the message, and |
327 | * a similar solution is used. Instead of starting with a remainder of |
328 | * 0, an initial remainder of all ones is used. As long as you start |
329 | * the same way on decoding, it doesn't make a difference. |
330 | */ |
331 | |
332 | #ifdef UNITTEST |
333 | |
334 | #include <stdlib.h> |
335 | #include <stdio.h> |
336 | |
337 | #if 0 /*Not used at present */ |
338 | static void |
339 | buf_dump(char const *prefix, unsigned char const *buf, size_t len) |
340 | { |
341 | fputs(prefix, stdout); |
342 | while (len--) |
343 | printf(" %02x", *buf++); |
344 | putchar('\n'); |
345 | |
346 | } |
347 | #endif |
348 | |
349 | static void bytereverse(unsigned char *buf, size_t len) |
350 | { |
351 | while (len--) { |
352 | unsigned char x = bitrev8(*buf); |
353 | *buf++ = x; |
354 | } |
355 | } |
356 | |
357 | static void random_garbage(unsigned char *buf, size_t len) |
358 | { |
359 | while (len--) |
360 | *buf++ = (unsigned char) random(); |
361 | } |
362 | |
363 | #if 0 /* Not used at present */ |
364 | static void store_le(u32 x, unsigned char *buf) |
365 | { |
366 | buf[0] = (unsigned char) x; |
367 | buf[1] = (unsigned char) (x >> 8); |
368 | buf[2] = (unsigned char) (x >> 16); |
369 | buf[3] = (unsigned char) (x >> 24); |
370 | } |
371 | #endif |
372 | |
373 | static void store_be(u32 x, unsigned char *buf) |
374 | { |
375 | buf[0] = (unsigned char) (x >> 24); |
376 | buf[1] = (unsigned char) (x >> 16); |
377 | buf[2] = (unsigned char) (x >> 8); |
378 | buf[3] = (unsigned char) x; |
379 | } |
380 | |
381 | /* |
382 | * This checks that CRC(buf + CRC(buf)) = 0, and that |
383 | * CRC commutes with bit-reversal. This has the side effect |
384 | * of bytewise bit-reversing the input buffer, and returns |
385 | * the CRC of the reversed buffer. |
386 | */ |
387 | static u32 test_step(u32 init, unsigned char *buf, size_t len) |
388 | { |
389 | u32 crc1, crc2; |
390 | size_t i; |
391 | |
392 | crc1 = crc32_be(init, buf, len); |
393 | store_be(crc1, buf + len); |
394 | crc2 = crc32_be(init, buf, len + 4); |
395 | if (crc2) |
396 | printf("\nCRC cancellation fail: 0x%08x should be 0\n", |
397 | crc2); |
398 | |
399 | for (i = 0; i <= len + 4; i++) { |
400 | crc2 = crc32_be(init, buf, i); |
401 | crc2 = crc32_be(crc2, buf + i, len + 4 - i); |
402 | if (crc2) |
403 | printf("\nCRC split fail: 0x%08x\n", crc2); |
404 | } |
405 | |
406 | /* Now swap it around for the other test */ |
407 | |
408 | bytereverse(buf, len + 4); |
409 | init = bitrev32(init); |
410 | crc2 = bitrev32(crc1); |
411 | if (crc1 != bitrev32(crc2)) |
412 | printf("\nBit reversal fail: 0x%08x -> 0x%08x -> 0x%08x\n", |
413 | crc1, crc2, bitrev32(crc2)); |
414 | crc1 = crc32_le(init, buf, len); |
415 | if (crc1 != crc2) |
416 | printf("\nCRC endianness fail: 0x%08x != 0x%08x\n", crc1, |
417 | crc2); |
418 | crc2 = crc32_le(init, buf, len + 4); |
419 | if (crc2) |
420 | printf("\nCRC cancellation fail: 0x%08x should be 0\n", |
421 | crc2); |
422 | |
423 | for (i = 0; i <= len + 4; i++) { |
424 | crc2 = crc32_le(init, buf, i); |
425 | crc2 = crc32_le(crc2, buf + i, len + 4 - i); |
426 | if (crc2) |
427 | printf("\nCRC split fail: 0x%08x\n", crc2); |
428 | } |
429 | |
430 | return crc1; |
431 | } |
432 | |
433 | #define SIZE 64 |
434 | #define INIT1 0 |
435 | #define INIT2 0 |
436 | |
437 | int main(void) |
438 | { |
439 | unsigned char buf1[SIZE + 4]; |
440 | unsigned char buf2[SIZE + 4]; |
441 | unsigned char buf3[SIZE + 4]; |
442 | int i, j; |
443 | u32 crc1, crc2, crc3; |
444 | |
445 | for (i = 0; i <= SIZE; i++) { |
446 | printf("\rTesting length %d...", i); |
447 | fflush(stdout); |
448 | random_garbage(buf1, i); |
449 | random_garbage(buf2, i); |
450 | for (j = 0; j < i; j++) |
451 | buf3[j] = buf1[j] ^ buf2[j]; |
452 | |
453 | crc1 = test_step(INIT1, buf1, i); |
454 | crc2 = test_step(INIT2, buf2, i); |
455 | /* Now check that CRC(buf1 ^ buf2) = CRC(buf1) ^ CRC(buf2) */ |
456 | crc3 = test_step(INIT1 ^ INIT2, buf3, i); |
457 | if (crc3 != (crc1 ^ crc2)) |
458 | printf("CRC XOR fail: 0x%08x != 0x%08x ^ 0x%08x\n", |
459 | crc3, crc1, crc2); |
460 | } |
461 | printf("\nAll test complete. No failures expected.\n"); |
462 | return 0; |
463 | } |
464 | |
465 | #endif /* UNITTEST */ |
466 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9