crc32.c 8.6 KB
Newer Older
L
Linus Torvalds 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
/*
 * 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.
 */

23 24
/* see: Documentation/crc32.txt for a description of algorithms */

L
Linus Torvalds 已提交
25 26 27 28 29 30
#include <linux/crc32.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/compiler.h>
#include <linux/types.h>
#include <linux/init.h>
A
Arun Sharma 已提交
31
#include <linux/atomic.h>
L
Linus Torvalds 已提交
32 33
#include "crc32defs.h"
#if CRC_LE_BITS == 8
J
Joakim Tjernlund 已提交
34
# define tole(x) __constant_cpu_to_le32(x)
L
Linus Torvalds 已提交
35
#else
J
Joakim Tjernlund 已提交
36 37 38 39 40 41 42
# define tole(x) (x)
#endif

#if CRC_BE_BITS == 8
# define tobe(x) __constant_cpu_to_be32(x)
#else
# define tobe(x) (x)
L
Linus Torvalds 已提交
43 44 45 46 47 48 49
#endif
#include "crc32table.h"

MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
MODULE_DESCRIPTION("Ethernet CRC32 calculations");
MODULE_LICENSE("GPL");

50 51 52
#if CRC_LE_BITS == 8 || CRC_BE_BITS == 8

static inline u32
J
Joakim Tjernlund 已提交
53
crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256])
54
{
55
# ifdef __LITTLE_ENDIAN
J
Joakim Tjernlund 已提交
56 57 58 59 60
#  define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8)
#  define DO_CRC4 crc = t3[(crc) & 255] ^ \
		t2[(crc >> 8) & 255] ^ \
		t1[(crc >> 16) & 255] ^ \
		t0[(crc >> 24) & 255]
61
# else
J
Joakim Tjernlund 已提交
62 63 64 65 66
#  define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
#  define DO_CRC4 crc = t0[(crc) & 255] ^ \
		t1[(crc >> 8) & 255] ^  \
		t2[(crc >> 16) & 255] ^	\
		t3[(crc >> 24) & 255]
67
# endif
J
Joakim Tjernlund 已提交
68
	const u32 *b;
69
	size_t    rem_len;
J
Joakim Tjernlund 已提交
70
	const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3];
71 72

	/* Align it */
J
Joakim Tjernlund 已提交
73
	if (unlikely((long)buf & 3 && len)) {
74
		do {
J
Joakim Tjernlund 已提交
75 76
			DO_CRC(*buf++);
		} while ((--len) && ((long)buf)&3);
77 78 79 80
	}
	rem_len = len & 3;
	/* load data 32 bits wide, xor data 32 bits wide. */
	len = len >> 2;
J
Joakim Tjernlund 已提交
81
	b = (const u32 *)buf;
82 83
	for (--b; len; --len) {
		crc ^= *++b; /* use pre increment for speed */
J
Joakim Tjernlund 已提交
84
		DO_CRC4;
85 86 87 88 89 90 91 92 93 94
	}
	len = rem_len;
	/* And the last few bytes */
	if (len) {
		u8 *p = (u8 *)(b + 1) - 1;
		do {
			DO_CRC(*++p); /* use pre increment for speed */
		} while (--len);
	}
	return crc;
J
Joakim Tjernlund 已提交
95
#undef DO_CRC
J
Joakim Tjernlund 已提交
96
#undef DO_CRC4
97 98
}
#endif
R
Randy Dunlap 已提交
99 100 101 102 103 104 105
/**
 * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32
 * @crc: seed value for computation.  ~0 for Ethernet, sometimes 0 for
 *	other uses, or the previous crc32 value if computing incrementally.
 * @p: pointer to buffer over which CRC is run
 * @len: length of buffer @p
 */
106
u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len);
R
Randy Dunlap 已提交
107

L
Linus Torvalds 已提交
108 109 110 111 112 113
#if CRC_LE_BITS == 1
/*
 * In fact, the table-based code will work in this case, but it can be
 * simplified by inlining the table in ?: form.
 */

114
u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
L
Linus Torvalds 已提交
115 116 117 118 119 120 121 122 123 124 125
{
	int i;
	while (len--) {
		crc ^= *p++;
		for (i = 0; i < 8; i++)
			crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0);
	}
	return crc;
}
#else				/* Table-based approach */

126
u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
L
Linus Torvalds 已提交
127 128
{
# if CRC_LE_BITS == 8
J
Joakim Tjernlund 已提交
129
	const u32      (*tab)[] = crc32table_le;
L
Linus Torvalds 已提交
130 131

	crc = __cpu_to_le32(crc);
132
	crc = crc32_body(crc, p, len, tab);
L
Linus Torvalds 已提交
133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
	return __le32_to_cpu(crc);
# elif CRC_LE_BITS == 4
	while (len--) {
		crc ^= *p++;
		crc = (crc >> 4) ^ crc32table_le[crc & 15];
		crc = (crc >> 4) ^ crc32table_le[crc & 15];
	}
	return crc;
# elif CRC_LE_BITS == 2
	while (len--) {
		crc ^= *p++;
		crc = (crc >> 2) ^ crc32table_le[crc & 3];
		crc = (crc >> 2) ^ crc32table_le[crc & 3];
		crc = (crc >> 2) ^ crc32table_le[crc & 3];
		crc = (crc >> 2) ^ crc32table_le[crc & 3];
	}
	return crc;
# endif
}
#endif

R
Randy Dunlap 已提交
154 155 156 157 158 159 160
/**
 * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
 * @crc: seed value for computation.  ~0 for Ethernet, sometimes 0 for
 *	other uses, or the previous crc32 value if computing incrementally.
 * @p: pointer to buffer over which CRC is run
 * @len: length of buffer @p
 */
161
u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len);
R
Randy Dunlap 已提交
162

L
Linus Torvalds 已提交
163 164 165 166 167 168
#if CRC_BE_BITS == 1
/*
 * In fact, the table-based code will work in this case, but it can be
 * simplified by inlining the table in ?: form.
 */

169
u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
L
Linus Torvalds 已提交
170 171 172 173 174 175 176 177 178 179 180 181 182
{
	int i;
	while (len--) {
		crc ^= *p++ << 24;
		for (i = 0; i < 8; i++)
			crc =
			    (crc << 1) ^ ((crc & 0x80000000) ? CRCPOLY_BE :
					  0);
	}
	return crc;
}

#else				/* Table-based approach */
183
u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
L
Linus Torvalds 已提交
184 185
{
# if CRC_BE_BITS == 8
J
Joakim Tjernlund 已提交
186
	const u32      (*tab)[] = crc32table_be;
L
Linus Torvalds 已提交
187 188

	crc = __cpu_to_be32(crc);
189
	crc = crc32_body(crc, p, len, tab);
L
Linus Torvalds 已提交
190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233
	return __be32_to_cpu(crc);
# elif CRC_BE_BITS == 4
	while (len--) {
		crc ^= *p++ << 24;
		crc = (crc << 4) ^ crc32table_be[crc >> 28];
		crc = (crc << 4) ^ crc32table_be[crc >> 28];
	}
	return crc;
# elif CRC_BE_BITS == 2
	while (len--) {
		crc ^= *p++ << 24;
		crc = (crc << 2) ^ crc32table_be[crc >> 30];
		crc = (crc << 2) ^ crc32table_be[crc >> 30];
		crc = (crc << 2) ^ crc32table_be[crc >> 30];
		crc = (crc << 2) ^ crc32table_be[crc >> 30];
	}
	return crc;
# endif
}
#endif

EXPORT_SYMBOL(crc32_le);
EXPORT_SYMBOL(crc32_be);

#ifdef UNITTEST

#include <stdlib.h>
#include <stdio.h>

#if 0				/*Not used at present */
static void
buf_dump(char const *prefix, unsigned char const *buf, size_t len)
{
	fputs(prefix, stdout);
	while (len--)
		printf(" %02x", *buf++);
	putchar('\n');

}
#endif

static void bytereverse(unsigned char *buf, size_t len)
{
	while (len--) {
234
		unsigned char x = bitrev8(*buf);
L
Linus Torvalds 已提交
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 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290
		*buf++ = x;
	}
}

static void random_garbage(unsigned char *buf, size_t len)
{
	while (len--)
		*buf++ = (unsigned char) random();
}

#if 0				/* Not used at present */
static void store_le(u32 x, unsigned char *buf)
{
	buf[0] = (unsigned char) x;
	buf[1] = (unsigned char) (x >> 8);
	buf[2] = (unsigned char) (x >> 16);
	buf[3] = (unsigned char) (x >> 24);
}
#endif

static void store_be(u32 x, unsigned char *buf)
{
	buf[0] = (unsigned char) (x >> 24);
	buf[1] = (unsigned char) (x >> 16);
	buf[2] = (unsigned char) (x >> 8);
	buf[3] = (unsigned char) x;
}

/*
 * This checks that CRC(buf + CRC(buf)) = 0, and that
 * CRC commutes with bit-reversal.  This has the side effect
 * of bytewise bit-reversing the input buffer, and returns
 * the CRC of the reversed buffer.
 */
static u32 test_step(u32 init, unsigned char *buf, size_t len)
{
	u32 crc1, crc2;
	size_t i;

	crc1 = crc32_be(init, buf, len);
	store_be(crc1, buf + len);
	crc2 = crc32_be(init, buf, len + 4);
	if (crc2)
		printf("\nCRC cancellation fail: 0x%08x should be 0\n",
		       crc2);

	for (i = 0; i <= len + 4; i++) {
		crc2 = crc32_be(init, buf, i);
		crc2 = crc32_be(crc2, buf + i, len + 4 - i);
		if (crc2)
			printf("\nCRC split fail: 0x%08x\n", crc2);
	}

	/* Now swap it around for the other test */

	bytereverse(buf, len + 4);
291 292 293
	init = bitrev32(init);
	crc2 = bitrev32(crc1);
	if (crc1 != bitrev32(crc2))
D
Dominik Hackl 已提交
294
		printf("\nBit reversal fail: 0x%08x -> 0x%08x -> 0x%08x\n",
295
		       crc1, crc2, bitrev32(crc2));
L
Linus Torvalds 已提交
296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347
	crc1 = crc32_le(init, buf, len);
	if (crc1 != crc2)
		printf("\nCRC endianness fail: 0x%08x != 0x%08x\n", crc1,
		       crc2);
	crc2 = crc32_le(init, buf, len + 4);
	if (crc2)
		printf("\nCRC cancellation fail: 0x%08x should be 0\n",
		       crc2);

	for (i = 0; i <= len + 4; i++) {
		crc2 = crc32_le(init, buf, i);
		crc2 = crc32_le(crc2, buf + i, len + 4 - i);
		if (crc2)
			printf("\nCRC split fail: 0x%08x\n", crc2);
	}

	return crc1;
}

#define SIZE 64
#define INIT1 0
#define INIT2 0

int main(void)
{
	unsigned char buf1[SIZE + 4];
	unsigned char buf2[SIZE + 4];
	unsigned char buf3[SIZE + 4];
	int i, j;
	u32 crc1, crc2, crc3;

	for (i = 0; i <= SIZE; i++) {
		printf("\rTesting length %d...", i);
		fflush(stdout);
		random_garbage(buf1, i);
		random_garbage(buf2, i);
		for (j = 0; j < i; j++)
			buf3[j] = buf1[j] ^ buf2[j];

		crc1 = test_step(INIT1, buf1, i);
		crc2 = test_step(INIT2, buf2, i);
		/* Now check that CRC(buf1 ^ buf2) = CRC(buf1) ^ CRC(buf2) */
		crc3 = test_step(INIT1 ^ INIT2, buf3, i);
		if (crc3 != (crc1 ^ crc2))
			printf("CRC XOR fail: 0x%08x != 0x%08x ^ 0x%08x\n",
			       crc3, crc1, crc2);
	}
	printf("\nAll test complete.  No failures expected.\n");
	return 0;
}

#endif				/* UNITTEST */