crc32.c 9.06 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1
/*
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.
 *
Linus Torvalds's avatar
Linus Torvalds committed
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
 * 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.
 */

27 28
/* see: Documentation/crc32.txt for a description of algorithms */

Linus Torvalds's avatar
Linus Torvalds committed
29 30 31
#include <linux/crc32.h>
#include <linux/module.h>
#include <linux/types.h>
32
#include <linux/sched.h>
Linus Torvalds's avatar
Linus Torvalds committed
33
#include "crc32defs.h"
Bob Pearson's avatar
Bob Pearson committed
34

35
#if CRC_LE_BITS > 8
36
# define tole(x) ((__force u32) cpu_to_le32(x))
Linus Torvalds's avatar
Linus Torvalds committed
37
#else
38 39 40
# define tole(x) (x)
#endif

41
#if CRC_BE_BITS > 8
42
# define tobe(x) ((__force u32) cpu_to_be32(x))
43 44
#else
# define tobe(x) (x)
Linus Torvalds's avatar
Linus Torvalds committed
45
#endif
Bob Pearson's avatar
Bob Pearson committed
46

Linus Torvalds's avatar
Linus Torvalds committed
47 48 49
#include "crc32table.h"

MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
Darrick J. Wong's avatar
Darrick J. Wong committed
50
MODULE_DESCRIPTION("Various CRC32 calculations");
Linus Torvalds's avatar
Linus Torvalds committed
51 52
MODULE_LICENSE("GPL");

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
Joakim Tjernlund's avatar
Joakim Tjernlund committed
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 62 63 64
#  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])
65
# else
66
#  define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
67 68 69 70
#  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])
71
# endif
72
	const u32 *b;
73
	size_t    rem_len;
74 75 76
# ifdef CONFIG_X86
	size_t i;
# 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 87
			DO_CRC(*buf++);
		} while ((--len) && ((long)buf)&3);
88
	}
89 90

# if CRC_LE_BITS == 32
91 92
	rem_len = len & 3;
	len = len >> 2;
93 94 95 96 97
# else
	rem_len = len & 7;
	len = len >> 3;
# endif

98
	b = (const u32 *)buf;
99 100 101 102
# ifdef CONFIG_X86
	--b;
	for (i = 0; i < len; i++) {
# else
103
	for (--b; len; --len) {
104
# endif
105 106 107 108 109 110 111 112
		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
113 114 115 116 117
	}
	len = rem_len;
	/* And the last few bytes */
	if (len) {
		u8 *p = (u8 *)(b + 1) - 1;
118 119 120 121
# ifdef CONFIG_X86
		for (i = 0; i < len; i++)
			DO_CRC(*++p); /* use pre increment for speed */
# else
122 123 124
		do {
			DO_CRC(*++p); /* use pre increment for speed */
		} while (--len);
125
# endif
126 127
	}
	return crc;
128
#undef DO_CRC
Joakim Tjernlund's avatar
Joakim Tjernlund committed
129
#undef DO_CRC4
130
#undef DO_CRC8
131 132
}
#endif
Bob Pearson's avatar
Bob Pearson committed
133

134

135
/**
136 137 138 139 140
 * 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
141
 * @len: length of buffer @p
142 143
 * @tab: little-endian Ethernet table
 * @polynomial: CRC32/CRC32c LE polynomial
144
 */
Darrick J. Wong's avatar
Darrick J. Wong committed
145 146 147
static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p,
					  size_t len, const u32 (*tab)[256],
					  u32 polynomial)
Linus Torvalds's avatar
Linus Torvalds committed
148
{
Bob Pearson's avatar
Bob Pearson committed
149
#if CRC_LE_BITS == 1
Linus Torvalds's avatar
Linus Torvalds committed
150 151 152 153
	int i;
	while (len--) {
		crc ^= *p++;
		for (i = 0; i < 8; i++)
Darrick J. Wong's avatar
Darrick J. Wong committed
154
			crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0);
Linus Torvalds's avatar
Linus Torvalds committed
155
	}
Bob Pearson's avatar
Bob Pearson committed
156
# elif CRC_LE_BITS == 2
Linus Torvalds's avatar
Linus Torvalds committed
157 158
	while (len--) {
		crc ^= *p++;
Darrick J. Wong's avatar
Darrick J. Wong committed
159 160 161 162
		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];
Linus Torvalds's avatar
Linus Torvalds committed
163
	}
Bob Pearson's avatar
Bob Pearson committed
164
# elif CRC_LE_BITS == 4
Linus Torvalds's avatar
Linus Torvalds committed
165 166
	while (len--) {
		crc ^= *p++;
Darrick J. Wong's avatar
Darrick J. Wong committed
167 168
		crc = (crc >> 4) ^ tab[0][crc & 15];
		crc = (crc >> 4) ^ tab[0][crc & 15];
Linus Torvalds's avatar
Linus Torvalds committed
169
	}
Bob Pearson's avatar
Bob Pearson committed
170
# elif CRC_LE_BITS == 8
171 172 173
	/* aka Sarwate algorithm */
	while (len--) {
		crc ^= *p++;
Darrick J. Wong's avatar
Darrick J. Wong committed
174
		crc = (crc >> 8) ^ tab[0][crc & 255];
175 176
	}
# else
177
	crc = (__force u32) __cpu_to_le32(crc);
Bob Pearson's avatar
Bob Pearson committed
178
	crc = crc32_body(crc, p, len, tab);
179
	crc = __le32_to_cpu((__force __le32)crc);
Bob Pearson's avatar
Bob Pearson committed
180
#endif
Linus Torvalds's avatar
Linus Torvalds committed
181 182
	return crc;
}
Darrick J. Wong's avatar
Darrick J. Wong committed
183 184 185 186 187 188 189 190 191 192 193 194 195

#if CRC_LE_BITS == 1
u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
{
	return crc32_le_generic(crc, p, len, NULL, CRCPOLY_LE);
}
u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len)
{
	return crc32_le_generic(crc, p, len, NULL, CRC32C_POLY_LE);
}
#else
u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
{
196 197
	return crc32_le_generic(crc, p, len,
			(const u32 (*)[256])crc32table_le, CRCPOLY_LE);
Darrick J. Wong's avatar
Darrick J. Wong committed
198 199 200
}
u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len)
{
201 202
	return crc32_le_generic(crc, p, len,
			(const u32 (*)[256])crc32ctable_le, CRC32C_POLY_LE);
Darrick J. Wong's avatar
Darrick J. Wong committed
203 204
}
#endif
205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227
EXPORT_SYMBOL(crc32_le);
EXPORT_SYMBOL(__crc32c_le);

/*
 * 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;
}

/**
228
 * crc32_generic_shift - Append @len 0 bytes to crc, in logarithmic time
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 269
 * @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)
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 279
EXPORT_SYMBOL(crc32_le_shift);
EXPORT_SYMBOL(__crc32c_le_shift);
Linus Torvalds's avatar
Linus Torvalds committed
280

281
/**
282
 * crc32_be_generic() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
283 284
 * @crc: seed value for computation.  ~0 for Ethernet, sometimes 0 for
 *	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 288
 * @tab: big-endian Ethernet table
 * @polynomial: CRC32 BE polynomial
289
 */
Darrick J. Wong's avatar
Darrick J. Wong committed
290 291 292
static inline u32 __pure crc32_be_generic(u32 crc, unsigned char const *p,
					  size_t len, const u32 (*tab)[256],
					  u32 polynomial)
Linus Torvalds's avatar
Linus Torvalds committed
293
{
Bob Pearson's avatar
Bob Pearson committed
294
#if CRC_BE_BITS == 1
Linus Torvalds's avatar
Linus Torvalds committed
295 296 297 298 299
	int i;
	while (len--) {
		crc ^= *p++ << 24;
		for (i = 0; i < 8; i++)
			crc =
Darrick J. Wong's avatar
Darrick J. Wong committed
300
			    (crc << 1) ^ ((crc & 0x80000000) ? polynomial :
Linus Torvalds's avatar
Linus Torvalds committed
301 302
					  0);
	}
Bob Pearson's avatar
Bob Pearson committed
303
# elif CRC_BE_BITS == 2
Linus Torvalds's avatar
Linus Torvalds committed
304 305
	while (len--) {
		crc ^= *p++ << 24;
Darrick J. Wong's avatar
Darrick J. Wong committed
306 307 308 309
		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];
Linus Torvalds's avatar
Linus Torvalds committed
310
	}
Bob Pearson's avatar
Bob Pearson committed
311
# elif CRC_BE_BITS == 4
Linus Torvalds's avatar
Linus Torvalds committed
312 313
	while (len--) {
		crc ^= *p++ << 24;
Darrick J. Wong's avatar
Darrick J. Wong committed
314 315
		crc = (crc << 4) ^ tab[0][crc >> 28];
		crc = (crc << 4) ^ tab[0][crc >> 28];
Linus Torvalds's avatar
Linus Torvalds committed
316
	}
Bob Pearson's avatar
Bob Pearson committed
317
# elif CRC_BE_BITS == 8
318 319
	while (len--) {
		crc ^= *p++ << 24;
Darrick J. Wong's avatar
Darrick J. Wong committed
320
		crc = (crc << 8) ^ tab[0][crc >> 24];
321 322
	}
# else
323
	crc = (__force u32) __cpu_to_be32(crc);
Bob Pearson's avatar
Bob Pearson committed
324
	crc = crc32_body(crc, p, len, tab);
325
	crc = __be32_to_cpu((__force __be32)crc);
Linus Torvalds's avatar
Linus Torvalds committed
326
# endif
Bob Pearson's avatar
Bob Pearson committed
327
	return crc;
Linus Torvalds's avatar
Linus Torvalds committed
328
}
Darrick J. Wong's avatar
Darrick J. Wong committed
329 330 331 332 333 334 335 336 337

#if CRC_LE_BITS == 1
u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
{
	return crc32_be_generic(crc, p, len, NULL, CRCPOLY_BE);
}
#else
u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
{
338 339
	return crc32_be_generic(crc, p, len,
			(const u32 (*)[256])crc32table_be, CRCPOLY_BE);
Darrick J. Wong's avatar
Darrick J. Wong committed
340 341
}
#endif
Linus Torvalds's avatar
Linus Torvalds committed
342
EXPORT_SYMBOL(crc32_be);