1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
49MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
50MODULE_DESCRIPTION("Various CRC32 calculations");
51MODULE_LICENSE("GPL");
52
53#if CRC_LE_BITS > 8 || CRC_BE_BITS > 8
54
55
56static inline u32 __pure
57crc32_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
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;
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
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);
121# else
122 do {
123 DO_CRC(*++p);
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
137
138
139
140
141
142
143
144
145static 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
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
185u32 __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}
189u32 __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
194u32 __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}
199u32 __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
205EXPORT_SYMBOL(crc32_le);
206EXPORT_SYMBOL(__crc32c_le);
207
208
209
210
211
212
213static 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
229
230
231
232
233
234
235
236
237
238
239static u32 __attribute_const__ crc32_generic_shift(u32 crc, size_t len,
240 u32 polynomial)
241{
242 u32 power = polynomial;
243 int i;
244
245
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
255 if (len & 1)
256 crc = gf2_multiply(crc, power, polynomial);
257
258 len >>= 1;
259 if (!len)
260 break;
261
262
263 power = gf2_multiply(power, power, polynomial);
264 }
265
266 return crc;
267}
268
269u32 __attribute_const__ crc32_le_shift(u32 crc, size_t len)
270{
271 return crc32_generic_shift(crc, len, CRCPOLY_LE);
272}
273
274u32 __attribute_const__ __crc32c_le_shift(u32 crc, size_t len)
275{
276 return crc32_generic_shift(crc, len, CRC32C_POLY_LE);
277}
278EXPORT_SYMBOL(crc32_le_shift);
279EXPORT_SYMBOL(__crc32c_le_shift);
280
281
282
283
284
285
286
287
288
289
290static 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
331u32 __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
336u32 __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
342EXPORT_SYMBOL(crc32_be);
343