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