linux/lib/crc32.c
<<
>>
Prefs
   1/*
   2 * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com>
   3 * Nicer crc32 functions/docs submitted by linux@horizon.com.  Thanks!
   4 * Code was from the public domain, copyright abandoned.  Code was
   5 * subsequently included in the kernel, thus was re-licensed under the
   6 * GNU GPL v2.
   7 *
   8 * Oct 12, 2000 Matt Domsch <Matt_Domsch@dell.com>
   9 * Same crc32 function was used in 5 other places in the kernel.
  10 * I made one version, and deleted the others.
  11 * There are various incantations of crc32().  Some use a seed of 0 or ~0.
  12 * Some xor at the end with ~0.  The generic crc32() function takes
  13 * seed as an argument, and doesn't xor at the end.  Then individual
  14 * users can do whatever they need.
  15 *   drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0.
  16 *   fs/jffs2 uses seed 0, doesn't xor with ~0.
  17 *   fs/partitions/efi.c uses seed ~0, xor's with ~0.
  18 *
  19 * This source code is licensed under the GNU General Public License,
  20 * Version 2.  See the file COPYING for more details.
  21 */
  22
  23#include <linux/crc32.h>
  24#include <linux/kernel.h>
  25#include <linux/module.h>
  26#include <linux/compiler.h>
  27#include <linux/types.h>
  28#include <linux/slab.h>
  29#include <linux/init.h>
  30#include <asm/atomic.h>
  31#include "crc32defs.h"
  32#if CRC_LE_BITS == 8
  33#define tole(x) __constant_cpu_to_le32(x)
  34#define tobe(x) __constant_cpu_to_be32(x)
  35#else
  36#define tole(x) (x)
  37#define tobe(x) (x)
  38#endif
  39#include "crc32table.h"
  40
  41MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
  42MODULE_DESCRIPTION("Ethernet CRC32 calculations");
  43MODULE_LICENSE("GPL");
  44
  45/**
  46 * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32
  47 * @crc: seed value for computation.  ~0 for Ethernet, sometimes 0 for
  48 *      other uses, or the previous crc32 value if computing incrementally.
  49 * @p: pointer to buffer over which CRC is run
  50 * @len: length of buffer @p
  51 */
  52u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len);
  53
  54#if CRC_LE_BITS == 1
  55/*
  56 * In fact, the table-based code will work in this case, but it can be
  57 * simplified by inlining the table in ?: form.
  58 */
  59
  60u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
  61{
  62        int i;
  63        while (len--) {
  64                crc ^= *p++;
  65                for (i = 0; i < 8; i++)
  66                        crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0);
  67        }
  68        return crc;
  69}
  70#else                           /* Table-based approach */
  71
  72u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
  73{
  74# if CRC_LE_BITS == 8
  75        const u32      *b =(u32 *)p;
  76        const u32      *tab = crc32table_le;
  77
  78# ifdef __LITTLE_ENDIAN
  79#  define DO_CRC(x) crc = tab[ (crc ^ (x)) & 255 ] ^ (crc>>8)
  80# else
  81#  define DO_CRC(x) crc = tab[ ((crc >> 24) ^ (x)) & 255] ^ (crc<<8)
  82# endif
  83
  84        crc = __cpu_to_le32(crc);
  85        /* Align it */
  86        if(unlikely(((long)b)&3 && len)){
  87                do {
  88                        u8 *p = (u8 *)b;
  89                        DO_CRC(*p++);
  90                        b = (void *)p;
  91                } while ((--len) && ((long)b)&3 );
  92        }
  93        if(likely(len >= 4)){
  94                /* load data 32 bits wide, xor data 32 bits wide. */
  95                size_t save_len = len & 3;
  96                len = len >> 2;
  97                --b; /* use pre increment below(*++b) for speed */
  98                do {
  99                        crc ^= *++b;
 100                        DO_CRC(0);
 101                        DO_CRC(0);
 102                        DO_CRC(0);
 103                        DO_CRC(0);
 104                } while (--len);
 105                b++; /* point to next byte(s) */
 106                len = save_len;
 107        }
 108        /* And the last few bytes */
 109        if(len){
 110                do {
 111                        u8 *p = (u8 *)b;
 112                        DO_CRC(*p++);
 113                        b = (void *)p;
 114                } while (--len);
 115        }
 116
 117        return __le32_to_cpu(crc);
 118#undef ENDIAN_SHIFT
 119#undef DO_CRC
 120
 121# elif CRC_LE_BITS == 4
 122        while (len--) {
 123                crc ^= *p++;
 124                crc = (crc >> 4) ^ crc32table_le[crc & 15];
 125                crc = (crc >> 4) ^ crc32table_le[crc & 15];
 126        }
 127        return crc;
 128# elif CRC_LE_BITS == 2
 129        while (len--) {
 130                crc ^= *p++;
 131                crc = (crc >> 2) ^ crc32table_le[crc & 3];
 132                crc = (crc >> 2) ^ crc32table_le[crc & 3];
 133                crc = (crc >> 2) ^ crc32table_le[crc & 3];
 134                crc = (crc >> 2) ^ crc32table_le[crc & 3];
 135        }
 136        return crc;
 137# endif
 138}
 139#endif
 140
 141/**
 142 * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
 143 * @crc: seed value for computation.  ~0 for Ethernet, sometimes 0 for
 144 *      other uses, or the previous crc32 value if computing incrementally.
 145 * @p: pointer to buffer over which CRC is run
 146 * @len: length of buffer @p
 147 */
 148u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len);
 149
 150#if CRC_BE_BITS == 1
 151/*
 152 * In fact, the table-based code will work in this case, but it can be
 153 * simplified by inlining the table in ?: form.
 154 */
 155
 156u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
 157{
 158        int i;
 159        while (len--) {
 160                crc ^= *p++ << 24;
 161                for (i = 0; i < 8; i++)
 162                        crc =
 163                            (crc << 1) ^ ((crc & 0x80000000) ? CRCPOLY_BE :
 164                                          0);
 165        }
 166        return crc;
 167}
 168
 169#else                           /* Table-based approach */
 170u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
 171{
 172# if CRC_BE_BITS == 8
 173        const u32      *b =(u32 *)p;
 174        const u32      *tab = crc32table_be;
 175
 176# ifdef __LITTLE_ENDIAN
 177#  define DO_CRC(x) crc = tab[ (crc ^ (x)) & 255 ] ^ (crc>>8)
 178# else
 179#  define DO_CRC(x) crc = tab[ ((crc >> 24) ^ (x)) & 255] ^ (crc<<8)
 180# endif
 181
 182        crc = __cpu_to_be32(crc);
 183        /* Align it */
 184        if(unlikely(((long)b)&3 && len)){
 185                do {
 186                        u8 *p = (u8 *)b;
 187                        DO_CRC(*p++);
 188                        b = (u32 *)p;
 189                } while ((--len) && ((long)b)&3 );
 190        }
 191        if(likely(len >= 4)){
 192                /* load data 32 bits wide, xor data 32 bits wide. */
 193                size_t save_len = len & 3;
 194                len = len >> 2;
 195                --b; /* use pre increment below(*++b) for speed */
 196                do {
 197                        crc ^= *++b;
 198                        DO_CRC(0);
 199                        DO_CRC(0);
 200                        DO_CRC(0);
 201                        DO_CRC(0);
 202                } while (--len);
 203                b++; /* point to next byte(s) */
 204                len = save_len;
 205        }
 206        /* And the last few bytes */
 207        if(len){
 208                do {
 209                        u8 *p = (u8 *)b;
 210                        DO_CRC(*p++);
 211                        b = (void *)p;
 212                } while (--len);
 213        }
 214        return __be32_to_cpu(crc);
 215#undef ENDIAN_SHIFT
 216#undef DO_CRC
 217
 218# elif CRC_BE_BITS == 4
 219        while (len--) {
 220                crc ^= *p++ << 24;
 221                crc = (crc << 4) ^ crc32table_be[crc >> 28];
 222                crc = (crc << 4) ^ crc32table_be[crc >> 28];
 223        }
 224        return crc;
 225# elif CRC_BE_BITS == 2
 226        while (len--) {
 227                crc ^= *p++ << 24;
 228                crc = (crc << 2) ^ crc32table_be[crc >> 30];
 229                crc = (crc << 2) ^ crc32table_be[crc >> 30];
 230                crc = (crc << 2) ^ crc32table_be[crc >> 30];
 231                crc = (crc << 2) ^ crc32table_be[crc >> 30];
 232        }
 233        return crc;
 234# endif
 235}
 236#endif
 237
 238EXPORT_SYMBOL(crc32_le);
 239EXPORT_SYMBOL(crc32_be);
 240
 241/*
 242 * A brief CRC tutorial.
 243 *
 244 * A CRC is a long-division remainder.  You add the CRC to the message,
 245 * and the whole thing (message+CRC) is a multiple of the given
 246 * CRC polynomial.  To check the CRC, you can either check that the
 247 * CRC matches the recomputed value, *or* you can check that the
 248 * remainder computed on the message+CRC is 0.  This latter approach
 249 * is used by a lot of hardware implementations, and is why so many
 250 * protocols put the end-of-frame flag after the CRC.
 251 *
 252 * It's actually the same long division you learned in school, except that
 253 * - We're working in binary, so the digits are only 0 and 1, and
 254 * - When dividing polynomials, there are no carries.  Rather than add and
 255 *   subtract, we just xor.  Thus, we tend to get a bit sloppy about
 256 *   the difference between adding and subtracting.
 257 *
 258 * A 32-bit CRC polynomial is actually 33 bits long.  But since it's
 259 * 33 bits long, bit 32 is always going to be set, so usually the CRC
 260 * is written in hex with the most significant bit omitted.  (If you're
 261 * familiar with the IEEE 754 floating-point format, it's the same idea.)
 262 *
 263 * Note that a CRC is computed over a string of *bits*, so you have
 264 * to decide on the endianness of the bits within each byte.  To get
 265 * the best error-detecting properties, this should correspond to the
 266 * order they're actually sent.  For example, standard RS-232 serial is
 267 * little-endian; the most significant bit (sometimes used for parity)
 268 * is sent last.  And when appending a CRC word to a message, you should
 269 * do it in the right order, matching the endianness.
 270 *
 271 * Just like with ordinary division, the remainder is always smaller than
 272 * the divisor (the CRC polynomial) you're dividing by.  Each step of the
 273 * division, you take one more digit (bit) of the dividend and append it
 274 * to the current remainder.  Then you figure out the appropriate multiple
 275 * of the divisor to subtract to being the remainder back into range.
 276 * In binary, it's easy - it has to be either 0 or 1, and to make the
 277 * XOR cancel, it's just a copy of bit 32 of the remainder.
 278 *
 279 * When computing a CRC, we don't care about the quotient, so we can
 280 * throw the quotient bit away, but subtract the appropriate multiple of
 281 * the polynomial from the remainder and we're back to where we started,
 282 * ready to process the next bit.
 283 *
 284 * A big-endian CRC written this way would be coded like:
 285 * for (i = 0; i < input_bits; i++) {
 286 *      multiple = remainder & 0x80000000 ? CRCPOLY : 0;
 287 *      remainder = (remainder << 1 | next_input_bit()) ^ multiple;
 288 * }
 289 * Notice how, to get at bit 32 of the shifted remainder, we look
 290 * at bit 31 of the remainder *before* shifting it.
 291 *
 292 * But also notice how the next_input_bit() bits we're shifting into
 293 * the remainder don't actually affect any decision-making until
 294 * 32 bits later.  Thus, the first 32 cycles of this are pretty boring.
 295 * Also, to add the CRC to a message, we need a 32-bit-long hole for it at
 296 * the end, so we have to add 32 extra cycles shifting in zeros at the
 297 * end of every message,
 298 *
 299 * So the standard trick is to rearrage merging in the next_input_bit()
 300 * until the moment it's needed.  Then the first 32 cycles can be precomputed,
 301 * and merging in the final 32 zero bits to make room for the CRC can be
 302 * skipped entirely.
 303 * This changes the code to:
 304 * for (i = 0; i < input_bits; i++) {
 305 *      remainder ^= next_input_bit() << 31;
 306 *      multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
 307 *      remainder = (remainder << 1) ^ multiple;
 308 * }
 309 * With this optimization, the little-endian code is simpler:
 310 * for (i = 0; i < input_bits; i++) {
 311 *      remainder ^= next_input_bit();
 312 *      multiple = (remainder & 1) ? CRCPOLY : 0;
 313 *      remainder = (remainder >> 1) ^ multiple;
 314 * }
 315 *
 316 * Note that the other details of endianness have been hidden in CRCPOLY
 317 * (which must be bit-reversed) and next_input_bit().
 318 *
 319 * However, as long as next_input_bit is returning the bits in a sensible
 320 * order, we can actually do the merging 8 or more bits at a time rather
 321 * than one bit at a time:
 322 * for (i = 0; i < input_bytes; i++) {
 323 *      remainder ^= next_input_byte() << 24;
 324 *      for (j = 0; j < 8; j++) {
 325 *              multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
 326 *              remainder = (remainder << 1) ^ multiple;
 327 *      }
 328 * }
 329 * Or in little-endian:
 330 * for (i = 0; i < input_bytes; i++) {
 331 *      remainder ^= next_input_byte();
 332 *      for (j = 0; j < 8; j++) {
 333 *              multiple = (remainder & 1) ? CRCPOLY : 0;
 334 *              remainder = (remainder << 1) ^ multiple;
 335 *      }
 336 * }
 337 * If the input is a multiple of 32 bits, you can even XOR in a 32-bit
 338 * word at a time and increase the inner loop count to 32.
 339 *
 340 * You can also mix and match the two loop styles, for example doing the
 341 * bulk of a message byte-at-a-time and adding bit-at-a-time processing
 342 * for any fractional bytes at the end.
 343 *
 344 * The only remaining optimization is to the byte-at-a-time table method.
 345 * Here, rather than just shifting one bit of the remainder to decide
 346 * in the correct multiple to subtract, we can shift a byte at a time.
 347 * This produces a 40-bit (rather than a 33-bit) intermediate remainder,
 348 * but again the multiple of the polynomial to subtract depends only on
 349 * the high bits, the high 8 bits in this case.  
 350 *
 351 * The multiple we need in that case is the low 32 bits of a 40-bit
 352 * value whose high 8 bits are given, and which is a multiple of the
 353 * generator polynomial.  This is simply the CRC-32 of the given
 354 * one-byte message.
 355 *
 356 * Two more details: normally, appending zero bits to a message which
 357 * is already a multiple of a polynomial produces a larger multiple of that
 358 * polynomial.  To enable a CRC to detect this condition, it's common to
 359 * invert the CRC before appending it.  This makes the remainder of the
 360 * message+crc come out not as zero, but some fixed non-zero value.
 361 *
 362 * The same problem applies to zero bits prepended to the message, and
 363 * a similar solution is used.  Instead of starting with a remainder of
 364 * 0, an initial remainder of all ones is used.  As long as you start
 365 * the same way on decoding, it doesn't make a difference.
 366 */
 367
 368#ifdef UNITTEST
 369
 370#include <stdlib.h>
 371#include <stdio.h>
 372
 373#if 0                           /*Not used at present */
 374static void
 375buf_dump(char const *prefix, unsigned char const *buf, size_t len)
 376{
 377        fputs(prefix, stdout);
 378        while (len--)
 379                printf(" %02x", *buf++);
 380        putchar('\n');
 381
 382}
 383#endif
 384
 385static void bytereverse(unsigned char *buf, size_t len)
 386{
 387        while (len--) {
 388                unsigned char x = bitrev8(*buf);
 389                *buf++ = x;
 390        }
 391}
 392
 393static void random_garbage(unsigned char *buf, size_t len)
 394{
 395        while (len--)
 396                *buf++ = (unsigned char) random();
 397}
 398
 399#if 0                           /* Not used at present */
 400static void store_le(u32 x, unsigned char *buf)
 401{
 402        buf[0] = (unsigned char) x;
 403        buf[1] = (unsigned char) (x >> 8);
 404        buf[2] = (unsigned char) (x >> 16);
 405        buf[3] = (unsigned char) (x >> 24);
 406}
 407#endif
 408
 409static void store_be(u32 x, unsigned char *buf)
 410{
 411        buf[0] = (unsigned char) (x >> 24);
 412        buf[1] = (unsigned char) (x >> 16);
 413        buf[2] = (unsigned char) (x >> 8);
 414        buf[3] = (unsigned char) x;
 415}
 416
 417/*
 418 * This checks that CRC(buf + CRC(buf)) = 0, and that
 419 * CRC commutes with bit-reversal.  This has the side effect
 420 * of bytewise bit-reversing the input buffer, and returns
 421 * the CRC of the reversed buffer.
 422 */
 423static u32 test_step(u32 init, unsigned char *buf, size_t len)
 424{
 425        u32 crc1, crc2;
 426        size_t i;
 427
 428        crc1 = crc32_be(init, buf, len);
 429        store_be(crc1, buf + len);
 430        crc2 = crc32_be(init, buf, len + 4);
 431        if (crc2)
 432                printf("\nCRC cancellation fail: 0x%08x should be 0\n",
 433                       crc2);
 434
 435        for (i = 0; i <= len + 4; i++) {
 436                crc2 = crc32_be(init, buf, i);
 437                crc2 = crc32_be(crc2, buf + i, len + 4 - i);
 438                if (crc2)
 439                        printf("\nCRC split fail: 0x%08x\n", crc2);
 440        }
 441
 442        /* Now swap it around for the other test */
 443
 444        bytereverse(buf, len + 4);
 445        init = bitrev32(init);
 446        crc2 = bitrev32(crc1);
 447        if (crc1 != bitrev32(crc2))
 448                printf("\nBit reversal fail: 0x%08x -> 0x%08x -> 0x%08x\n",
 449                       crc1, crc2, bitrev32(crc2));
 450        crc1 = crc32_le(init, buf, len);
 451        if (crc1 != crc2)
 452                printf("\nCRC endianness fail: 0x%08x != 0x%08x\n", crc1,
 453                       crc2);
 454        crc2 = crc32_le(init, buf, len + 4);
 455        if (crc2)
 456                printf("\nCRC cancellation fail: 0x%08x should be 0\n",
 457                       crc2);
 458
 459        for (i = 0; i <= len + 4; i++) {
 460                crc2 = crc32_le(init, buf, i);
 461                crc2 = crc32_le(crc2, buf + i, len + 4 - i);
 462                if (crc2)
 463                        printf("\nCRC split fail: 0x%08x\n", crc2);
 464        }
 465
 466        return crc1;
 467}
 468
 469#define SIZE 64
 470#define INIT1 0
 471#define INIT2 0
 472
 473int main(void)
 474{
 475        unsigned char buf1[SIZE + 4];
 476        unsigned char buf2[SIZE + 4];
 477        unsigned char buf3[SIZE + 4];
 478        int i, j;
 479        u32 crc1, crc2, crc3;
 480
 481        for (i = 0; i <= SIZE; i++) {
 482                printf("\rTesting length %d...", i);
 483                fflush(stdout);
 484                random_garbage(buf1, i);
 485                random_garbage(buf2, i);
 486                for (j = 0; j < i; j++)
 487                        buf3[j] = buf1[j] ^ buf2[j];
 488
 489                crc1 = test_step(INIT1, buf1, i);
 490                crc2 = test_step(INIT2, buf2, i);
 491                /* Now check that CRC(buf1 ^ buf2) = CRC(buf1) ^ CRC(buf2) */
 492                crc3 = test_step(INIT1 ^ INIT2, buf3, i);
 493                if (crc3 != (crc1 ^ crc2))
 494                        printf("CRC XOR fail: 0x%08x != 0x%08x ^ 0x%08x\n",
 495                               crc3, crc1, crc2);
 496        }
 497        printf("\nAll test complete.  No failures expected.\n");
 498        return 0;
 499}
 500
 501#endif                          /* UNITTEST */
 502