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