1 /* 2 * crc32.c --- CRC32 function 3 * 4 * Copyright (C) 2008 Theodore Ts'o. 5 * 6 * %Begin-Header% 7 * This file may be redistributed under the terms of the GNU Public 8 * License. 9 * %End-Header% 10 */ 11 12 /* 13 * Oct 15, 2000 Matt Domsch <Matt_Domsch (at) dell.com> 14 * Nicer crc32 functions/docs submitted by linux (at) horizon.com. Thanks! 15 * Code was from the public domain, copyright abandoned. Code was 16 * subsequently included in the kernel, thus was re-licensed under the 17 * GNU GPL v2. 18 * 19 * Oct 12, 2000 Matt Domsch <Matt_Domsch (at) dell.com> 20 * Same crc32 function was used in 5 other places in the kernel. 21 * I made one version, and deleted the others. 22 * There are various incantations of crc32(). Some use a seed of 0 or ~0. 23 * Some xor at the end with ~0. The generic crc32() function takes 24 * seed as an argument, and doesn't xor at the end. Then individual 25 * users can do whatever they need. 26 * drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0. 27 * fs/jffs2 uses seed 0, doesn't xor with ~0. 28 * fs/partitions/efi.c uses seed ~0, xor's with ~0. 29 * 30 * This source code is licensed under the GNU General Public License, 31 * Version 2. See the file COPYING for more details. 32 */ 33 34 #include <stdlib.h> 35 #include <unistd.h> 36 #include <string.h> 37 #include <ctype.h> 38 39 #ifdef UNITTEST 40 #undef ENABLE_NLS 41 #endif 42 #include "e2fsck.h" 43 44 #include "crc32defs.h" 45 #if CRC_LE_BITS == 8 46 #define tole(x) __constant_cpu_to_le32(x) 47 #define tobe(x) __constant_cpu_to_be32(x) 48 #else 49 #define tole(x) (x) 50 #define tobe(x) (x) 51 #endif 52 #include "crc32table.h" 53 54 #ifdef UNITTEST 55 56 /** 57 * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32 58 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for 59 * other uses, or the previous crc32 value if computing incrementally. 60 * @p: pointer to buffer over which CRC is run 61 * @len: length of buffer @p 62 */ 63 __u32 crc32_le(__u32 crc, unsigned char const *p, size_t len); 64 65 #if CRC_LE_BITS == 1 66 /* 67 * In fact, the table-based code will work in this case, but it can be 68 * simplified by inlining the table in ?: form. 69 */ 70 71 __u32 crc32_le(__u32 crc, unsigned char const *p, size_t len) 72 { 73 int i; 74 while (len--) { 75 crc ^= *p++; 76 for (i = 0; i < 8; i++) 77 crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0); 78 } 79 return crc; 80 } 81 #else /* Table-based approach */ 82 83 __u32 crc32_le(__u32 crc, unsigned char const *p, size_t len) 84 { 85 # if CRC_LE_BITS == 8 86 const __u32 *b =(__u32 *)p; 87 const __u32 *tab = crc32table_le; 88 89 # ifdef WORDS_BIGENDIAN 90 # define DO_CRC(x) crc = tab[ ((crc >> 24) ^ (x)) & 255] ^ (crc<<8) 91 # else 92 # define DO_CRC(x) crc = tab[ (crc ^ (x)) & 255 ] ^ (crc>>8) 93 # endif 94 95 crc = __cpu_to_le32(crc); 96 /* Align it */ 97 if(unlikely(((long)b)&3 && len)){ 98 do { 99 __u8 *p = (__u8 *)b; 100 DO_CRC(*p++); 101 b = (void *)p; 102 } while ((--len) && ((long)b)&3 ); 103 } 104 if(likely(len >= 4)){ 105 /* load data 32 bits wide, xor data 32 bits wide. */ 106 size_t save_len = len & 3; 107 len = len >> 2; 108 --b; /* use pre increment below(*++b) for speed */ 109 do { 110 crc ^= *++b; 111 DO_CRC(0); 112 DO_CRC(0); 113 DO_CRC(0); 114 DO_CRC(0); 115 } while (--len); 116 b++; /* point to next byte(s) */ 117 len = save_len; 118 } 119 /* And the last few bytes */ 120 if(len){ 121 do { 122 __u8 *p = (__u8 *)b; 123 DO_CRC(*p++); 124 b = (void *)p; 125 } while (--len); 126 } 127 128 return __le32_to_cpu(crc); 129 #undef ENDIAN_SHIFT 130 #undef DO_CRC 131 132 # elif CRC_LE_BITS == 4 133 while (len--) { 134 crc ^= *p++; 135 crc = (crc >> 4) ^ crc32table_le[crc & 15]; 136 crc = (crc >> 4) ^ crc32table_le[crc & 15]; 137 } 138 return crc; 139 # elif CRC_LE_BITS == 2 140 while (len--) { 141 crc ^= *p++; 142 crc = (crc >> 2) ^ crc32table_le[crc & 3]; 143 crc = (crc >> 2) ^ crc32table_le[crc & 3]; 144 crc = (crc >> 2) ^ crc32table_le[crc & 3]; 145 crc = (crc >> 2) ^ crc32table_le[crc & 3]; 146 } 147 return crc; 148 # endif 149 } 150 #endif 151 152 #endif /* UNITTEST */ 153 154 /** 155 * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32 156 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for 157 * other uses, or the previous crc32 value if computing incrementally. 158 * @p: pointer to buffer over which CRC is run 159 * @len: length of buffer @p 160 */ 161 __u32 crc32_be(__u32 crc, unsigned char const *p, size_t len); 162 163 #if CRC_BE_BITS == 1 164 /* 165 * In fact, the table-based code will work in this case, but it can be 166 * simplified by inlining the table in ?: form. 167 */ 168 169 __u32 crc32_be(__u32 crc, unsigned char const *p, size_t len) 170 { 171 int i; 172 while (len--) { 173 crc ^= *p++ << 24; 174 for (i = 0; i < 8; i++) 175 crc = 176 (crc << 1) ^ ((crc & 0x80000000) ? CRCPOLY_BE : 177 0); 178 } 179 return crc; 180 } 181 182 #else /* Table-based approach */ 183 __u32 crc32_be(__u32 crc, unsigned char const *p, size_t len) 184 { 185 # if CRC_BE_BITS == 8 186 const __u32 *b =(const __u32 *)p; 187 const __u32 *tab = crc32table_be; 188 189 # ifdef WORDS_BIGENDIAN 190 # define DO_CRC(x) crc = tab[ ((crc >> 24) ^ (x)) & 255] ^ (crc<<8) 191 # else 192 # define DO_CRC(x) crc = tab[ (crc ^ (x)) & 255 ] ^ (crc>>8) 193 # endif 194 195 crc = __cpu_to_be32(crc); 196 /* Align it */ 197 if(unlikely(((long)b)&3 && len)){ 198 do { 199 const __u8 *q = (const __u8 *)b; 200 DO_CRC(*q++); 201 b = (const __u32 *)q; 202 } while ((--len) && ((long)b)&3 ); 203 } 204 if(likely(len >= 4)){ 205 /* load data 32 bits wide, xor data 32 bits wide. */ 206 size_t save_len = len & 3; 207 len = len >> 2; 208 --b; /* use pre increment below(*++b) for speed */ 209 do { 210 crc ^= *++b; 211 DO_CRC(0); 212 DO_CRC(0); 213 DO_CRC(0); 214 DO_CRC(0); 215 } while (--len); 216 b++; /* point to next byte(s) */ 217 len = save_len; 218 } 219 /* And the last few bytes */ 220 if(len){ 221 do { 222 const __u8 *q = (const __u8 *)b; 223 DO_CRC(*q++); 224 b = (const void *)q; 225 } while (--len); 226 } 227 return __be32_to_cpu(crc); 228 #undef ENDIAN_SHIFT 229 #undef DO_CRC 230 231 # elif CRC_BE_BITS == 4 232 while (len--) { 233 crc ^= *p++ << 24; 234 crc = (crc << 4) ^ crc32table_be[crc >> 28]; 235 crc = (crc << 4) ^ crc32table_be[crc >> 28]; 236 } 237 return crc; 238 # elif CRC_BE_BITS == 2 239 while (len--) { 240 crc ^= *p++ << 24; 241 crc = (crc << 2) ^ crc32table_be[crc >> 30]; 242 crc = (crc << 2) ^ crc32table_be[crc >> 30]; 243 crc = (crc << 2) ^ crc32table_be[crc >> 30]; 244 crc = (crc << 2) ^ crc32table_be[crc >> 30]; 245 } 246 return crc; 247 # endif 248 } 249 #endif 250 251 /* 252 * A brief CRC tutorial. 253 * 254 * A CRC is a long-division remainder. You add the CRC to the message, 255 * and the whole thing (message+CRC) is a multiple of the given 256 * CRC polynomial. To check the CRC, you can either check that the 257 * CRC matches the recomputed value, *or* you can check that the 258 * remainder computed on the message+CRC is 0. This latter approach 259 * is used by a lot of hardware implementations, and is why so many 260 * protocols put the end-of-frame flag after the CRC. 261 * 262 * It's actually the same long division you learned in school, except that 263 * - We're working in binary, so the digits are only 0 and 1, and 264 * - When dividing polynomials, there are no carries. Rather than add and 265 * subtract, we just xor. Thus, we tend to get a bit sloppy about 266 * the difference between adding and subtracting. 267 * 268 * A 32-bit CRC polynomial is actually 33 bits long. But since it's 269 * 33 bits long, bit 32 is always going to be set, so usually the CRC 270 * is written in hex with the most significant bit omitted. (If you're 271 * familiar with the IEEE 754 floating-point format, it's the same idea.) 272 * 273 * Note that a CRC is computed over a string of *bits*, so you have 274 * to decide on the endianness of the bits within each byte. To get 275 * the best error-detecting properties, this should correspond to the 276 * order they're actually sent. For example, standard RS-232 serial is 277 * little-endian; the most significant bit (sometimes used for parity) 278 * is sent last. And when appending a CRC word to a message, you should 279 * do it in the right order, matching the endianness. 280 * 281 * Just like with ordinary division, the remainder is always smaller than 282 * the divisor (the CRC polynomial) you're dividing by. Each step of the 283 * division, you take one more digit (bit) of the dividend and append it 284 * to the current remainder. Then you figure out the appropriate multiple 285 * of the divisor to subtract to being the remainder back into range. 286 * In binary, it's easy - it has to be either 0 or 1, and to make the 287 * XOR cancel, it's just a copy of bit 32 of the remainder. 288 * 289 * When computing a CRC, we don't care about the quotient, so we can 290 * throw the quotient bit away, but subtract the appropriate multiple of 291 * the polynomial from the remainder and we're back to where we started, 292 * ready to process the next bit. 293 * 294 * A big-endian CRC written this way would be coded like: 295 * for (i = 0; i < input_bits; i++) { 296 * multiple = remainder & 0x80000000 ? CRCPOLY : 0; 297 * remainder = (remainder << 1 | next_input_bit()) ^ multiple; 298 * } 299 * Notice how, to get at bit 32 of the shifted remainder, we look 300 * at bit 31 of the remainder *before* shifting it. 301 * 302 * But also notice how the next_input_bit() bits we're shifting into 303 * the remainder don't actually affect any decision-making until 304 * 32 bits later. Thus, the first 32 cycles of this are pretty boring. 305 * Also, to add the CRC to a message, we need a 32-bit-long hole for it at 306 * the end, so we have to add 32 extra cycles shifting in zeros at the 307 * end of every message, 308 * 309 * So the standard trick is to rearrage merging in the next_input_bit() 310 * until the moment it's needed. Then the first 32 cycles can be precomputed, 311 * and merging in the final 32 zero bits to make room for the CRC can be 312 * skipped entirely. 313 * This changes the code to: 314 * for (i = 0; i < input_bits; i++) { 315 * remainder ^= next_input_bit() << 31; 316 * multiple = (remainder & 0x80000000) ? CRCPOLY : 0; 317 * remainder = (remainder << 1) ^ multiple; 318 * } 319 * With this optimization, the little-endian code is simpler: 320 * for (i = 0; i < input_bits; i++) { 321 * remainder ^= next_input_bit(); 322 * multiple = (remainder & 1) ? CRCPOLY : 0; 323 * remainder = (remainder >> 1) ^ multiple; 324 * } 325 * 326 * Note that the other details of endianness have been hidden in CRCPOLY 327 * (which must be bit-reversed) and next_input_bit(). 328 * 329 * However, as long as next_input_bit is returning the bits in a sensible 330 * order, we can actually do the merging 8 or more bits at a time rather 331 * than one bit at a time: 332 * for (i = 0; i < input_bytes; i++) { 333 * remainder ^= next_input_byte() << 24; 334 * for (j = 0; j < 8; j++) { 335 * multiple = (remainder & 0x80000000) ? CRCPOLY : 0; 336 * remainder = (remainder << 1) ^ multiple; 337 * } 338 * } 339 * Or in little-endian: 340 * for (i = 0; i < input_bytes; i++) { 341 * remainder ^= next_input_byte(); 342 * for (j = 0; j < 8; j++) { 343 * multiple = (remainder & 1) ? CRCPOLY : 0; 344 * remainder = (remainder << 1) ^ multiple; 345 * } 346 * } 347 * If the input is a multiple of 32 bits, you can even XOR in a 32-bit 348 * word at a time and increase the inner loop count to 32. 349 * 350 * You can also mix and match the two loop styles, for example doing the 351 * bulk of a message byte-at-a-time and adding bit-at-a-time processing 352 * for any fractional bytes at the end. 353 * 354 * The only remaining optimization is to the byte-at-a-time table method. 355 * Here, rather than just shifting one bit of the remainder to decide 356 * in the correct multiple to subtract, we can shift a byte at a time. 357 * This produces a 40-bit (rather than a 33-bit) intermediate remainder, 358 * but again the multiple of the polynomial to subtract depends only on 359 * the high bits, the high 8 bits in this case. 360 * 361 * The multiple we need in that case is the low 32 bits of a 40-bit 362 * value whose high 8 bits are given, and which is a multiple of the 363 * generator polynomial. This is simply the CRC-32 of the given 364 * one-byte message. 365 * 366 * Two more details: normally, appending zero bits to a message which 367 * is already a multiple of a polynomial produces a larger multiple of that 368 * polynomial. To enable a CRC to detect this condition, it's common to 369 * invert the CRC before appending it. This makes the remainder of the 370 * message+crc come out not as zero, but some fixed non-zero value. 371 * 372 * The same problem applies to zero bits prepended to the message, and 373 * a similar solution is used. Instead of starting with a remainder of 374 * 0, an initial remainder of all ones is used. As long as you start 375 * the same way on decoding, it doesn't make a difference. 376 */ 377 378 #ifdef UNITTEST 379 380 #include <stdlib.h> 381 #include <stdio.h> 382 383 const __u8 byte_rev_table[256] = { 384 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 385 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, 386 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 387 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, 388 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, 389 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4, 390 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 391 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc, 392 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, 393 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, 394 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, 395 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa, 396 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 397 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6, 398 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee, 399 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, 400 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1, 401 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1, 402 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 403 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9, 404 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5, 405 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, 406 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed, 407 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd, 408 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 409 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3, 410 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, 411 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, 412 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, 413 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7, 414 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 415 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff, 416 }; 417 418 static inline __u8 bitrev8(__u8 byte) 419 { 420 return byte_rev_table[byte]; 421 } 422 423 static inline __u16 bitrev16(__u16 x) 424 { 425 return (bitrev8(x & 0xff) << 8) | bitrev8(x >> 8); 426 } 427 428 /** 429 * bitrev32 - reverse the order of bits in a u32 value 430 * @x: value to be bit-reversed 431 */ 432 static __u32 bitrev32(__u32 x) 433 { 434 return (bitrev16(x & 0xffff) << 16) | bitrev16(x >> 16); 435 } 436 437 #if 0 /*Not used at present */ 438 439 static void 440 buf_dump(char const *prefix, unsigned char const *buf, size_t len) 441 { 442 fputs(prefix, stdout); 443 while (len--) 444 printf(" %02x", *buf++); 445 putchar('\n'); 446 447 } 448 #endif 449 450 static void bytereverse(unsigned char *buf, size_t len) 451 { 452 while (len--) { 453 unsigned char x = bitrev8(*buf); 454 *buf++ = x; 455 } 456 } 457 458 static void random_garbage(unsigned char *buf, size_t len) 459 { 460 while (len--) 461 *buf++ = (unsigned char) random(); 462 } 463 464 #if 0 /* Not used at present */ 465 static void store_le(__u32 x, unsigned char *buf) 466 { 467 buf[0] = (unsigned char) x; 468 buf[1] = (unsigned char) (x >> 8); 469 buf[2] = (unsigned char) (x >> 16); 470 buf[3] = (unsigned char) (x >> 24); 471 } 472 #endif 473 474 static void store_be(__u32 x, unsigned char *buf) 475 { 476 buf[0] = (unsigned char) (x >> 24); 477 buf[1] = (unsigned char) (x >> 16); 478 buf[2] = (unsigned char) (x >> 8); 479 buf[3] = (unsigned char) x; 480 } 481 482 /* 483 * This checks that CRC(buf + CRC(buf)) = 0, and that 484 * CRC commutes with bit-reversal. This has the side effect 485 * of bytewise bit-reversing the input buffer, and returns 486 * the CRC of the reversed buffer. 487 */ 488 static __u32 test_step(__u32 init, unsigned char *buf, size_t len) 489 { 490 __u32 crc1, crc2; 491 size_t i; 492 493 crc1 = crc32_be(init, buf, len); 494 store_be(crc1, buf + len); 495 crc2 = crc32_be(init, buf, len + 4); 496 if (crc2) 497 printf("\nCRC cancellation fail: 0x%08x should be 0\n", 498 crc2); 499 500 for (i = 0; i <= len + 4; i++) { 501 crc2 = crc32_be(init, buf, i); 502 crc2 = crc32_be(crc2, buf + i, len + 4 - i); 503 if (crc2) 504 printf("\nCRC split fail: 0x%08x\n", crc2); 505 } 506 507 /* Now swap it around for the other test */ 508 509 bytereverse(buf, len + 4); 510 init = bitrev32(init); 511 crc2 = bitrev32(crc1); 512 if (crc1 != bitrev32(crc2)) 513 printf("\nBit reversal fail: 0x%08x -> 0x%08x -> 0x%08x\n", 514 crc1, crc2, bitrev32(crc2)); 515 crc1 = crc32_le(init, buf, len); 516 if (crc1 != crc2) 517 printf("\nCRC endianness fail: 0x%08x != 0x%08x\n", crc1, 518 crc2); 519 crc2 = crc32_le(init, buf, len + 4); 520 if (crc2) 521 printf("\nCRC cancellation fail: 0x%08x should be 0\n", 522 crc2); 523 524 for (i = 0; i <= len + 4; i++) { 525 crc2 = crc32_le(init, buf, i); 526 crc2 = crc32_le(crc2, buf + i, len + 4 - i); 527 if (crc2) 528 printf("\nCRC split fail: 0x%08x\n", crc2); 529 } 530 531 return crc1; 532 } 533 534 #define SIZE 64 535 #define INIT1 0 536 #define INIT2 0 537 538 int main(int argc, char **argv) 539 { 540 unsigned char buf1[SIZE + 4]; 541 unsigned char buf2[SIZE + 4]; 542 unsigned char buf3[SIZE + 4]; 543 int i, j; 544 __u32 crc1, crc2, crc3; 545 int exit_status = 0; 546 547 for (i = 0; i <= SIZE; i++) { 548 printf("\rTesting length %d...", i); 549 fflush(stdout); 550 random_garbage(buf1, i); 551 random_garbage(buf2, i); 552 for (j = 0; j < i; j++) 553 buf3[j] = buf1[j] ^ buf2[j]; 554 555 crc1 = test_step(INIT1, buf1, i); 556 crc2 = test_step(INIT2, buf2, i); 557 /* Now check that CRC(buf1 ^ buf2) = CRC(buf1) ^ CRC(buf2) */ 558 crc3 = test_step(INIT1 ^ INIT2, buf3, i); 559 if (crc3 != (crc1 ^ crc2)) { 560 printf("CRC XOR fail: 0x%08x != 0x%08x ^ 0x%08x\n", 561 crc3, crc1, crc2); 562 exit_status++; 563 } 564 } 565 printf("\nAll test complete. No failures expected.\n"); 566 return 0; 567 } 568 569 #endif /* UNITTEST */ 570
