]>
Commit | Line | Data |
---|---|---|
1 | /* | |
2 | * Aug 8, 2011 Bob Pearson with help from Joakim Tjernlund and George Spelvin | |
3 | * cleaned up code to current version of sparse and added the slicing-by-8 | |
4 | * algorithm to the closely similar existing slicing-by-4 algorithm. | |
5 | * | |
6 | * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com> | |
7 | * Nicer crc32 functions/docs submitted by linux@horizon.com. Thanks! | |
8 | * Code was from the public domain, copyright abandoned. Code was | |
9 | * subsequently included in the kernel, thus was re-licensed under the | |
10 | * GNU GPL v2. | |
11 | * | |
12 | * Oct 12, 2000 Matt Domsch <Matt_Domsch@dell.com> | |
13 | * Same crc32 function was used in 5 other places in the kernel. | |
14 | * I made one version, and deleted the others. | |
15 | * There are various incantations of crc32(). Some use a seed of 0 or ~0. | |
16 | * Some xor at the end with ~0. The generic crc32() function takes | |
17 | * seed as an argument, and doesn't xor at the end. Then individual | |
18 | * users can do whatever they need. | |
19 | * drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0. | |
20 | * fs/jffs2 uses seed 0, doesn't xor with ~0. | |
21 | * fs/partitions/efi.c uses seed ~0, xor's with ~0. | |
22 | * | |
23 | * This source code is licensed under the GNU General Public License, | |
24 | * Version 2. See the file COPYING for more details. | |
25 | */ | |
26 | ||
27 | /* see: Documentation/crc32.txt for a description of algorithms */ | |
28 | ||
29 | #include <linux/crc32.h> | |
30 | #include <linux/module.h> | |
31 | #include <linux/types.h> | |
32 | #include <linux/sched.h> | |
33 | #include "crc32defs.h" | |
34 | ||
35 | #if CRC_LE_BITS > 8 | |
36 | # define tole(x) ((__force u32) cpu_to_le32(x)) | |
37 | #else | |
38 | # define tole(x) (x) | |
39 | #endif | |
40 | ||
41 | #if CRC_BE_BITS > 8 | |
42 | # define tobe(x) ((__force u32) cpu_to_be32(x)) | |
43 | #else | |
44 | # define tobe(x) (x) | |
45 | #endif | |
46 | ||
47 | #include "crc32table.h" | |
48 | ||
49 | MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>"); | |
50 | MODULE_DESCRIPTION("Various CRC32 calculations"); | |
51 | MODULE_LICENSE("GPL"); | |
52 | ||
53 | #if CRC_LE_BITS > 8 || CRC_BE_BITS > 8 | |
54 | ||
55 | /* implements slicing-by-4 or slicing-by-8 algorithm */ | |
56 | static inline u32 __pure | |
57 | crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) | |
58 | { | |
59 | # ifdef __LITTLE_ENDIAN | |
60 | # define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8) | |
61 | # define DO_CRC4 (t3[(q) & 255] ^ t2[(q >> 8) & 255] ^ \ | |
62 | t1[(q >> 16) & 255] ^ t0[(q >> 24) & 255]) | |
63 | # define DO_CRC8 (t7[(q) & 255] ^ t6[(q >> 8) & 255] ^ \ | |
64 | t5[(q >> 16) & 255] ^ t4[(q >> 24) & 255]) | |
65 | # else | |
66 | # define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8) | |
67 | # define DO_CRC4 (t0[(q) & 255] ^ t1[(q >> 8) & 255] ^ \ | |
68 | t2[(q >> 16) & 255] ^ t3[(q >> 24) & 255]) | |
69 | # define DO_CRC8 (t4[(q) & 255] ^ t5[(q >> 8) & 255] ^ \ | |
70 | t6[(q >> 16) & 255] ^ t7[(q >> 24) & 255]) | |
71 | # endif | |
72 | const u32 *b; | |
73 | size_t rem_len; | |
74 | # ifdef CONFIG_X86 | |
75 | size_t i; | |
76 | # endif | |
77 | const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3]; | |
78 | # if CRC_LE_BITS != 32 | |
79 | const u32 *t4 = tab[4], *t5 = tab[5], *t6 = tab[6], *t7 = tab[7]; | |
80 | # endif | |
81 | u32 q; | |
82 | ||
83 | /* Align it */ | |
84 | if (unlikely((long)buf & 3 && len)) { | |
85 | do { | |
86 | DO_CRC(*buf++); | |
87 | } while ((--len) && ((long)buf)&3); | |
88 | } | |
89 | ||
90 | # if CRC_LE_BITS == 32 | |
91 | rem_len = len & 3; | |
92 | len = len >> 2; | |
93 | # else | |
94 | rem_len = len & 7; | |
95 | len = len >> 3; | |
96 | # endif | |
97 | ||
98 | b = (const u32 *)buf; | |
99 | # ifdef CONFIG_X86 | |
100 | --b; | |
101 | for (i = 0; i < len; i++) { | |
102 | # else | |
103 | for (--b; len; --len) { | |
104 | # endif | |
105 | q = crc ^ *++b; /* use pre increment for speed */ | |
106 | # if CRC_LE_BITS == 32 | |
107 | crc = DO_CRC4; | |
108 | # else | |
109 | crc = DO_CRC8; | |
110 | q = *++b; | |
111 | crc ^= DO_CRC4; | |
112 | # endif | |
113 | } | |
114 | len = rem_len; | |
115 | /* And the last few bytes */ | |
116 | if (len) { | |
117 | u8 *p = (u8 *)(b + 1) - 1; | |
118 | # ifdef CONFIG_X86 | |
119 | for (i = 0; i < len; i++) | |
120 | DO_CRC(*++p); /* use pre increment for speed */ | |
121 | # else | |
122 | do { | |
123 | DO_CRC(*++p); /* use pre increment for speed */ | |
124 | } while (--len); | |
125 | # endif | |
126 | } | |
127 | return crc; | |
128 | #undef DO_CRC | |
129 | #undef DO_CRC4 | |
130 | #undef DO_CRC8 | |
131 | } | |
132 | #endif | |
133 | ||
134 | ||
135 | /** | |
136 | * crc32_le_generic() - Calculate bitwise little-endian Ethernet AUTODIN II | |
137 | * CRC32/CRC32C | |
138 | * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for other | |
139 | * uses, or the previous crc32/crc32c value if computing incrementally. | |
140 | * @p: pointer to buffer over which CRC32/CRC32C is run | |
141 | * @len: length of buffer @p | |
142 | * @tab: little-endian Ethernet table | |
143 | * @polynomial: CRC32/CRC32c LE polynomial | |
144 | */ | |
145 | static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p, | |
146 | size_t len, const u32 (*tab)[256], | |
147 | u32 polynomial) | |
148 | { | |
149 | #if CRC_LE_BITS == 1 | |
150 | int i; | |
151 | while (len--) { | |
152 | crc ^= *p++; | |
153 | for (i = 0; i < 8; i++) | |
154 | crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0); | |
155 | } | |
156 | # elif CRC_LE_BITS == 2 | |
157 | while (len--) { | |
158 | crc ^= *p++; | |
159 | crc = (crc >> 2) ^ tab[0][crc & 3]; | |
160 | crc = (crc >> 2) ^ tab[0][crc & 3]; | |
161 | crc = (crc >> 2) ^ tab[0][crc & 3]; | |
162 | crc = (crc >> 2) ^ tab[0][crc & 3]; | |
163 | } | |
164 | # elif CRC_LE_BITS == 4 | |
165 | while (len--) { | |
166 | crc ^= *p++; | |
167 | crc = (crc >> 4) ^ tab[0][crc & 15]; | |
168 | crc = (crc >> 4) ^ tab[0][crc & 15]; | |
169 | } | |
170 | # elif CRC_LE_BITS == 8 | |
171 | /* aka Sarwate algorithm */ | |
172 | while (len--) { | |
173 | crc ^= *p++; | |
174 | crc = (crc >> 8) ^ tab[0][crc & 255]; | |
175 | } | |
176 | # else | |
177 | crc = (__force u32) __cpu_to_le32(crc); | |
178 | crc = crc32_body(crc, p, len, tab); | |
179 | crc = __le32_to_cpu((__force __le32)crc); | |
180 | #endif | |
181 | return crc; | |
182 | } | |
183 | ||
184 | #if CRC_LE_BITS == 1 | |
185 | u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) | |
186 | { | |
187 | return crc32_le_generic(crc, p, len, NULL, CRCPOLY_LE); | |
188 | } | |
189 | u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len) | |
190 | { | |
191 | return crc32_le_generic(crc, p, len, NULL, CRC32C_POLY_LE); | |
192 | } | |
193 | #else | |
194 | u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) | |
195 | { | |
196 | return crc32_le_generic(crc, p, len, | |
197 | (const u32 (*)[256])crc32table_le, CRCPOLY_LE); | |
198 | } | |
199 | u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len) | |
200 | { | |
201 | return crc32_le_generic(crc, p, len, | |
202 | (const u32 (*)[256])crc32ctable_le, CRC32C_POLY_LE); | |
203 | } | |
204 | #endif | |
205 | EXPORT_SYMBOL(crc32_le); | |
206 | EXPORT_SYMBOL(__crc32c_le); | |
207 | ||
208 | /* | |
209 | * This multiplies the polynomials x and y modulo the given modulus. | |
210 | * This follows the "little-endian" CRC convention that the lsbit | |
211 | * represents the highest power of x, and the msbit represents x^0. | |
212 | */ | |
213 | static u32 __attribute_const__ gf2_multiply(u32 x, u32 y, u32 modulus) | |
214 | { | |
215 | u32 product = x & 1 ? y : 0; | |
216 | int i; | |
217 | ||
218 | for (i = 0; i < 31; i++) { | |
219 | product = (product >> 1) ^ (product & 1 ? modulus : 0); | |
220 | x >>= 1; | |
221 | product ^= x & 1 ? y : 0; | |
222 | } | |
223 | ||
224 | return product; | |
225 | } | |
226 | ||
227 | /** | |
228 | * crc32_generic_shift - Append len 0 bytes to crc, in logarithmic time | |
229 | * @crc: The original little-endian CRC (i.e. lsbit is x^31 coefficient) | |
230 | * @len: The number of bytes. @crc is multiplied by x^(8*@len) | |
231 | * @polynomial: The modulus used to reduce the result to 32 bits. | |
232 | * | |
233 | * It's possible to parallelize CRC computations by computing a CRC | |
234 | * over separate ranges of a buffer, then summing them. | |
235 | * This shifts the given CRC by 8*len bits (i.e. produces the same effect | |
236 | * as appending len bytes of zero to the data), in time proportional | |
237 | * to log(len). | |
238 | */ | |
239 | static u32 __attribute_const__ crc32_generic_shift(u32 crc, size_t len, | |
240 | u32 polynomial) | |
241 | { | |
242 | u32 power = polynomial; /* CRC of x^32 */ | |
243 | int i; | |
244 | ||
245 | /* Shift up to 32 bits in the simple linear way */ | |
246 | for (i = 0; i < 8 * (int)(len & 3); i++) | |
247 | crc = (crc >> 1) ^ (crc & 1 ? polynomial : 0); | |
248 | ||
249 | len >>= 2; | |
250 | if (!len) | |
251 | return crc; | |
252 | ||
253 | for (;;) { | |
254 | /* "power" is x^(2^i), modulo the polynomial */ | |
255 | if (len & 1) | |
256 | crc = gf2_multiply(crc, power, polynomial); | |
257 | ||
258 | len >>= 1; | |
259 | if (!len) | |
260 | break; | |
261 | ||
262 | /* Square power, advancing to x^(2^(i+1)) */ | |
263 | power = gf2_multiply(power, power, polynomial); | |
264 | } | |
265 | ||
266 | return crc; | |
267 | } | |
268 | ||
269 | u32 __attribute_const__ crc32_le_shift(u32 crc, size_t len) | |
270 | { | |
271 | return crc32_generic_shift(crc, len, CRCPOLY_LE); | |
272 | } | |
273 | ||
274 | u32 __attribute_const__ __crc32c_le_shift(u32 crc, size_t len) | |
275 | { | |
276 | return crc32_generic_shift(crc, len, CRC32C_POLY_LE); | |
277 | } | |
278 | EXPORT_SYMBOL(crc32_le_shift); | |
279 | EXPORT_SYMBOL(__crc32c_le_shift); | |
280 | ||
281 | /** | |
282 | * crc32_be_generic() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32 | |
283 | * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for | |
284 | * other uses, or the previous crc32 value if computing incrementally. | |
285 | * @p: pointer to buffer over which CRC32 is run | |
286 | * @len: length of buffer @p | |
287 | * @tab: big-endian Ethernet table | |
288 | * @polynomial: CRC32 BE polynomial | |
289 | */ | |
290 | static inline u32 __pure crc32_be_generic(u32 crc, unsigned char const *p, | |
291 | size_t len, const u32 (*tab)[256], | |
292 | u32 polynomial) | |
293 | { | |
294 | #if CRC_BE_BITS == 1 | |
295 | int i; | |
296 | while (len--) { | |
297 | crc ^= *p++ << 24; | |
298 | for (i = 0; i < 8; i++) | |
299 | crc = | |
300 | (crc << 1) ^ ((crc & 0x80000000) ? polynomial : | |
301 | 0); | |
302 | } | |
303 | # elif CRC_BE_BITS == 2 | |
304 | while (len--) { | |
305 | crc ^= *p++ << 24; | |
306 | crc = (crc << 2) ^ tab[0][crc >> 30]; | |
307 | crc = (crc << 2) ^ tab[0][crc >> 30]; | |
308 | crc = (crc << 2) ^ tab[0][crc >> 30]; | |
309 | crc = (crc << 2) ^ tab[0][crc >> 30]; | |
310 | } | |
311 | # elif CRC_BE_BITS == 4 | |
312 | while (len--) { | |
313 | crc ^= *p++ << 24; | |
314 | crc = (crc << 4) ^ tab[0][crc >> 28]; | |
315 | crc = (crc << 4) ^ tab[0][crc >> 28]; | |
316 | } | |
317 | # elif CRC_BE_BITS == 8 | |
318 | while (len--) { | |
319 | crc ^= *p++ << 24; | |
320 | crc = (crc << 8) ^ tab[0][crc >> 24]; | |
321 | } | |
322 | # else | |
323 | crc = (__force u32) __cpu_to_be32(crc); | |
324 | crc = crc32_body(crc, p, len, tab); | |
325 | crc = __be32_to_cpu((__force __be32)crc); | |
326 | # endif | |
327 | return crc; | |
328 | } | |
329 | ||
330 | #if CRC_LE_BITS == 1 | |
331 | u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) | |
332 | { | |
333 | return crc32_be_generic(crc, p, len, NULL, CRCPOLY_BE); | |
334 | } | |
335 | #else | |
336 | u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) | |
337 | { | |
338 | return crc32_be_generic(crc, p, len, | |
339 | (const u32 (*)[256])crc32table_be, CRCPOLY_BE); | |
340 | } | |
341 | #endif | |
342 | EXPORT_SYMBOL(crc32_be); |