lib/crc32.c

   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 /* see: Documentation/crc32.txt for a description of algorithms */
  24
  25 #include <linux/crc32.h>
  26 #include <linux/kernel.h>
  27 #include <linux/module.h>
  28 #include <linux/compiler.h>
  29 #include <linux/types.h>
  30 #include <linux/init.h>
  31 #include <linux/atomic.h>
  32 #include "crc32defs.h"
  33 #if CRC_LE_BITS == 8
  34 # define tole(x) __constant_cpu_to_le32(x)
  35 #else
  36 # define tole(x) (x)
  37 #endif
  38
  39 #if CRC_BE_BITS == 8
  40 # define tobe(x) __constant_cpu_to_be32(x)
  41 #else
  42 # define tobe(x) (x)
  43 #endif
  44 #include "crc32table.h"
  45
  46 MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
  47 MODULE_DESCRIPTION("Ethernet CRC32 calculations");
  48 MODULE_LICENSE("GPL");
  49
  50 #if CRC_LE_BITS == 8 || CRC_BE_BITS == 8
  51
  52 static inline u32
  53 crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256])
  54 {
  55 # ifdef __LITTLE_ENDIAN
  56 #  define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8)
  57 #  define DO_CRC4 crc = t3[(crc) & 255] ^ \
  58                 t2[(crc >> 8) & 255] ^ \
  59                 t1[(crc >> 16) & 255] ^ \
  60                 t0[(crc >> 24) & 255]
  61 # else
  62 #  define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
  63 #  define DO_CRC4 crc = t0[(crc) & 255] ^ \
  64                 t1[(crc >> 8) & 255] ^  \
  65                 t2[(crc >> 16) & 255] ^ \
  66                 t3[(crc >> 24) & 255]
  67 # endif
  68         const u32 *b;
  69         size_t    rem_len;
  70         const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3];
  71
  72         /* Align it */
  73         if (unlikely((long)buf & 3 && len)) {
  74                 do {
  75                         DO_CRC(*buf++);
  76                 } while ((--len) && ((long)buf)&3);
  77         }
  78         rem_len = len & 3;
  79         /* load data 32 bits wide, xor data 32 bits wide. */
  80         len = len >> 2;
  81         b = (const u32 *)buf;
  82         for (--b; len; --len) {
  83                 crc ^= *++b; /* use pre increment for speed */
  84                 DO_CRC4;
  85         }
  86         len = rem_len;
  87         /* And the last few bytes */
  88         if (len) {
  89                 u8 *p = (u8 *)(b + 1) - 1;
  90                 do {
  91                         DO_CRC(*++p); /* use pre increment for speed */
  92                 } while (--len);
  93         }
  94         return crc;
  95 #undef DO_CRC
  96 #undef DO_CRC4
  97 }
  98 #endif
  99 /**
 100  * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32
 101  * @crc: seed value for computation.  ~0 for Ethernet, sometimes 0 for
 102  *      other uses, or the previous crc32 value if computing incrementally.
 103  * @p: pointer to buffer over which CRC is run
 104  * @len: length of buffer @p
 105  */
 106 u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len);
 107
 108 #if CRC_LE_BITS == 1
 109 /*
 110  * In fact, the table-based code will work in this case, but it can be
 111  * simplified by inlining the table in ?: form.
 112  */
 113
 114 u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
 115 {
 116         int i;
 117         while (len--) {
 118                 crc ^= *p++;
 119                 for (i = 0; i < 8; i++)
 120                         crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0);
 121         }
 122         return crc;
 123 }
 124 #else                           /* Table-based approach */
 125
 126 u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
 127 {
 128 # if CRC_LE_BITS == 8
 129         const u32      (*tab)[] = crc32table_le;
 130
 131         crc = __cpu_to_le32(crc);
 132         crc = crc32_body(crc, p, len, tab);
 133         return __le32_to_cpu(crc);
 134 # elif CRC_LE_BITS == 4
 135         while (len--) {
 136                 crc ^= *p++;
 137                 crc = (crc >> 4) ^ crc32table_le[crc & 15];
 138                 crc = (crc >> 4) ^ crc32table_le[crc & 15];
 139         }
 140         return crc;
 141 # elif CRC_LE_BITS == 2
 142         while (len--) {
 143                 crc ^= *p++;
 144                 crc = (crc >> 2) ^ crc32table_le[crc & 3];
 145                 crc = (crc >> 2) ^ crc32table_le[crc & 3];
 146                 crc = (crc >> 2) ^ crc32table_le[crc & 3];
 147                 crc = (crc >> 2) ^ crc32table_le[crc & 3];
 148         }
 149         return crc;
 150 # endif
 151 }
 152 #endif
 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 __pure 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 __pure 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 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
 184 {
 185 # if CRC_BE_BITS == 8
 186         const u32      (*tab)[] = crc32table_be;
 187
 188         crc = __cpu_to_be32(crc);
 189         crc = crc32_body(crc, p, len, tab);
 190         return __be32_to_cpu(crc);
 191 # elif CRC_BE_BITS == 4
 192         while (len--) {
 193                 crc ^= *p++ << 24;
 194                 crc = (crc << 4) ^ crc32table_be[crc >> 28];
 195                 crc = (crc << 4) ^ crc32table_be[crc >> 28];
 196         }
 197         return crc;
 198 # elif CRC_BE_BITS == 2
 199         while (len--) {
 200                 crc ^= *p++ << 24;
 201                 crc = (crc << 2) ^ crc32table_be[crc >> 30];
 202                 crc = (crc << 2) ^ crc32table_be[crc >> 30];
 203                 crc = (crc << 2) ^ crc32table_be[crc >> 30];
 204                 crc = (crc << 2) ^ crc32table_be[crc >> 30];
 205         }
 206         return crc;
 207 # endif
 208 }
 209 #endif
 210
 211 EXPORT_SYMBOL(crc32_le);
 212 EXPORT_SYMBOL(crc32_be);
 213
 214 #ifdef UNITTEST
 215
 216 #include <stdlib.h>
 217 #include <stdio.h>
 218
 219 #if 0                           /*Not used at present */
 220 static void
 221 buf_dump(char const *prefix, unsigned char const *buf, size_t len)
 222 {
 223         fputs(prefix, stdout);
 224         while (len--)
 225                 printf(" %02x", *buf++);
 226         putchar('\n');
 227
 228 }
 229 #endif
 230
 231 static void bytereverse(unsigned char *buf, size_t len)
 232 {
 233         while (len--) {
 234                 unsigned char x = bitrev8(*buf);
 235                 *buf++ = x;
 236         }
 237 }
 238
 239 static void random_garbage(unsigned char *buf, size_t len)
 240 {
 241         while (len--)
 242                 *buf++ = (unsigned char) random();
 243 }
 244
 245 #if 0                           /* Not used at present */
 246 static void store_le(u32 x, unsigned char *buf)
 247 {
 248         buf[0] = (unsigned char) x;
 249         buf[1] = (unsigned char) (x >> 8);
 250         buf[2] = (unsigned char) (x >> 16);
 251         buf[3] = (unsigned char) (x >> 24);
 252 }
 253 #endif
 254
 255 static void store_be(u32 x, unsigned char *buf)
 256 {
 257         buf[0] = (unsigned char) (x >> 24);
 258         buf[1] = (unsigned char) (x >> 16);
 259         buf[2] = (unsigned char) (x >> 8);
 260         buf[3] = (unsigned char) x;
 261 }
 262
 263 /*
 264  * This checks that CRC(buf + CRC(buf)) = 0, and that
 265  * CRC commutes with bit-reversal.  This has the side effect
 266  * of bytewise bit-reversing the input buffer, and returns
 267  * the CRC of the reversed buffer.
 268  */
 269 static u32 test_step(u32 init, unsigned char *buf, size_t len)
 270 {
 271         u32 crc1, crc2;
 272         size_t i;
 273
 274         crc1 = crc32_be(init, buf, len);
 275         store_be(crc1, buf + len);
 276         crc2 = crc32_be(init, buf, len + 4);
 277         if (crc2)
 278                 printf("\nCRC cancellation fail: 0x%08x should be 0\n",
 279                        crc2);
 280
 281         for (i = 0; i <= len + 4; i++) {
 282                 crc2 = crc32_be(init, buf, i);
 283                 crc2 = crc32_be(crc2, buf + i, len + 4 - i);
 284                 if (crc2)
 285                         printf("\nCRC split fail: 0x%08x\n", crc2);
 286         }
 287
 288         /* Now swap it around for the other test */
 289
 290         bytereverse(buf, len + 4);
 291         init = bitrev32(init);
 292         crc2 = bitrev32(crc1);
 293         if (crc1 != bitrev32(crc2))
 294                 printf("\nBit reversal fail: 0x%08x -> 0x%08x -> 0x%08x\n",
 295                        crc1, crc2, bitrev32(crc2));
 296         crc1 = crc32_le(init, buf, len);
 297         if (crc1 != crc2)
 298                 printf("\nCRC endianness fail: 0x%08x != 0x%08x\n", crc1,
 299                        crc2);
 300         crc2 = crc32_le(init, buf, len + 4);
 301         if (crc2)
 302                 printf("\nCRC cancellation fail: 0x%08x should be 0\n",
 303                        crc2);
 304
 305         for (i = 0; i <= len + 4; i++) {
 306                 crc2 = crc32_le(init, buf, i);
 307                 crc2 = crc32_le(crc2, buf + i, len + 4 - i);
 308                 if (crc2)
 309                         printf("\nCRC split fail: 0x%08x\n", crc2);
 310         }
 311
 312         return crc1;
 313 }
 314
 315 #define SIZE 64
 316 #define INIT1 0
 317 #define INIT2 0
 318
 319 int main(void)
 320 {
 321         unsigned char buf1[SIZE + 4];
 322         unsigned char buf2[SIZE + 4];
 323         unsigned char buf3[SIZE + 4];
 324         int i, j;
 325         u32 crc1, crc2, crc3;
 326
 327         for (i = 0; i <= SIZE; i++) {
 328                 printf("\rTesting length %d...", i);
 329                 fflush(stdout);
 330                 random_garbage(buf1, i);
 331                 random_garbage(buf2, i);
 332                 for (j = 0; j < i; j++)
 333                         buf3[j] = buf1[j] ^ buf2[j];
 334
 335                 crc1 = test_step(INIT1, buf1, i);
 336                 crc2 = test_step(INIT2, buf2, i);
 337                 /* Now check that CRC(buf1 ^ buf2) = CRC(buf1) ^ CRC(buf2) */
 338                 crc3 = test_step(INIT1 ^ INIT2, buf3, i);
 339                 if (crc3 != (crc1 ^ crc2))
 340                         printf("CRC XOR fail: 0x%08x != 0x%08x ^ 0x%08x\n",
 341                                crc3, crc1, crc2);
 342         }
 343         printf("\nAll test complete.  No failures expected.\n");
 344         return 0;
 345 }
 346
 347 #endif                          /* UNITTEST */