partx/crc32.c

   1 /*
   2  * crc32.c
   3  * This code is in the public domain; copyright abandoned.
   4  * Liability for non-performance of this code is limited to the amount
   5  * you paid for it.  Since it is distributed for free, your refund will
   6  * be very very small.  If it breaks, you get to keep both pieces.
   7  */
   8
   9 #include "crc32.h"
  10
  11 #if __GNUC__ >= 3       /* 2.x has "attribute", but only 3.0 has "pure */
  12 #define attribute(x) __attribute__(x)
  13 #else
  14 #define attribute(x)
  15 #endif
  16
  17 /*
  18  * There are multiple 16-bit CRC polynomials in common use, but this is
  19  * *the* standard CRC-32 polynomial, first popularized by Ethernet.
  20  * x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^1+x^0
  21  */
  22 #define CRCPOLY_LE 0xedb88320
  23 #define CRCPOLY_BE 0x04c11db7
  24
  25 /* How many bits at a time to use.  Requires a table of 4<<CRC_xx_BITS bytes. */
  26 /* For less performance-sensitive, use 4 */
  27 #define CRC_LE_BITS 8
  28 #define CRC_BE_BITS 8
  29
  30 /*
  31  * Little-endian CRC computation.  Used with serial bit streams sent
  32  * lsbit-first.  Be sure to use cpu_to_le32() to append the computed CRC.
  33  */
  34 #if CRC_LE_BITS > 8 || CRC_LE_BITS < 1 || CRC_LE_BITS & CRC_LE_BITS-1
  35 # error CRC_LE_BITS must be a power of 2 between 1 and 8
  36 #endif
  37
  38 #if CRC_LE_BITS == 1
  39 /*
  40  * In fact, the table-based code will work in this case, but it can be
  41  * simplified by inlining the table in ?: form.
  42  */
  43 #define crc32init_le()
  44 #define crc32cleanup_le()
  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  *
  52  */
  53 uint32_t attribute((pure)) crc32_le(uint32_t crc, unsigned char const *p, size_t len)
  54 {
  55         int i;
  56         while (len--) {
  57                 crc ^= *p++;
  58                 for (i = 0; i < 8; i++)
  59                         crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0);
  60         }
  61         return crc;
  62 }
  63 #else                           /* Table-based approach */
  64
  65 static uint32_t *crc32table_le;
  66 /**
  67  * crc32init_le() - allocate and initialize LE table data
  68  *
  69  * crc is the crc of the byte i; other entries are filled in based on the
  70  * fact that crctable[i^j] = crctable[i] ^ crctable[j].
  71  *
  72  */
  73 static int
  74 crc32init_le(void)
  75 {
  76         unsigned i, j;
  77         uint32_t crc = 1;
  78
  79         crc32table_le =
  80                 malloc((1 << CRC_LE_BITS) * sizeof(uint32_t));
  81         if (!crc32table_le)
  82                 return 1;
  83         crc32table_le[0] = 0;
  84
  85         for (i = 1 << (CRC_LE_BITS - 1); i; i >>= 1) {
  86                 crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0);
  87                 for (j = 0; j < 1 << CRC_LE_BITS; j += 2 * i)
  88                         crc32table_le[i + j] = crc ^ crc32table_le[j];
  89         }
  90         return 0;
  91 }
  92
  93 /**
  94  * crc32cleanup_le(): free LE table data
  95  */
  96 static void
  97 crc32cleanup_le(void)
  98 {
  99         free(crc32table_le);
 100         crc32table_le = NULL;
 101 }
 102
 103 /**
 104  * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32
 105  * @crc - seed value for computation.  ~0 for Ethernet, sometimes 0 for
 106  *        other uses, or the previous crc32 value if computing incrementally.
 107  * @p   - pointer to buffer over which CRC is run
 108  * @len - length of buffer @p
 109  *
 110  */
 111 uint32_t attribute((pure)) crc32_le(uint32_t crc, unsigned char const *p, size_t len)
 112 {
 113         while (len--) {
 114 # if CRC_LE_BITS == 8
 115                 crc = (crc >> 8) ^ crc32table_le[(crc ^ *p++) & 255];
 116 # elif CRC_LE_BITS == 4
 117                 crc ^= *p++;
 118                 crc = (crc >> 4) ^ crc32table_le[crc & 15];
 119                 crc = (crc >> 4) ^ crc32table_le[crc & 15];
 120 # elif CRC_LE_BITS == 2
 121                 crc ^= *p++;
 122                 crc = (crc >> 2) ^ crc32table_le[crc & 3];
 123                 crc = (crc >> 2) ^ crc32table_le[crc & 3];
 124                 crc = (crc >> 2) ^ crc32table_le[crc & 3];
 125                 crc = (crc >> 2) ^ crc32table_le[crc & 3];
 126 # endif
 127         }
 128         return crc;
 129 }
 130 #endif
 131
 132 /*
 133  * Big-endian CRC computation.  Used with serial bit streams sent
 134  * msbit-first.  Be sure to use cpu_to_be32() to append the computed CRC.
 135  */
 136 #if CRC_BE_BITS > 8 || CRC_BE_BITS < 1 || CRC_BE_BITS & CRC_BE_BITS-1
 137 # error CRC_BE_BITS must be a power of 2 between 1 and 8
 138 #endif
 139
 140 #if CRC_BE_BITS == 1
 141 /*
 142  * In fact, the table-based code will work in this case, but it can be
 143  * simplified by inlining the table in ?: form.
 144  */
 145 #define crc32init_be()
 146 #define crc32cleanup_be()
 147
 148 /**
 149  * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
 150  * @crc - seed value for computation.  ~0 for Ethernet, sometimes 0 for
 151  *        other uses, or the previous crc32 value if computing incrementally.
 152  * @p   - pointer to buffer over which CRC is run
 153  * @len - length of buffer @p
 154  *
 155  */
 156 uint32_t attribute((pure)) crc32_be(uint32_t 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 */
 170 static uint32_t *crc32table_be;
 171
 172 /**
 173  * crc32init_be() - allocate and initialize BE table data
 174  */
 175 static int
 176 crc32init_be(void)
 177 {
 178         unsigned i, j;
 179         uint32_t crc = 0x80000000;
 180
 181         crc32table_be =
 182                 malloc((1 << CRC_BE_BITS) * sizeof(uint32_t));
 183         if (!crc32table_be)
 184                 return 1;
 185         crc32table_be[0] = 0;
 186
 187         for (i = 1; i < 1 << CRC_BE_BITS; i <<= 1) {
 188                 crc = (crc << 1) ^ ((crc & 0x80000000) ? CRCPOLY_BE : 0);
 189                 for (j = 0; j < i; j++)
 190                         crc32table_be[i + j] = crc ^ crc32table_be[j];
 191         }
 192         return 0;
 193 }
 194
 195 /**
 196  * crc32cleanup_be(): free BE table data
 197  */
 198 static void
 199 crc32cleanup_be(void)
 200 {
 201         free(crc32table_be);
 202         crc32table_be = NULL;
 203 }
 204
 205
 206 /**
 207  * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
 208  * @crc - seed value for computation.  ~0 for Ethernet, sometimes 0 for
 209  *        other uses, or the previous crc32 value if computing incrementally.
 210  * @p   - pointer to buffer over which CRC is run
 211  * @len - length of buffer @p
 212  *
 213  */
 214 uint32_t attribute((pure)) crc32_be(uint32_t crc, unsigned char const *p, size_t len)
 215 {
 216         while (len--) {
 217 # if CRC_BE_BITS == 8
 218                 crc = (crc << 8) ^ crc32table_be[(crc >> 24) ^ *p++];
 219 # elif CRC_BE_BITS == 4
 220                 crc ^= *p++ << 24;
 221                 crc = (crc << 4) ^ crc32table_be[crc >> 28];
 222                 crc = (crc << 4) ^ crc32table_be[crc >> 28];
 223 # elif CRC_BE_BITS == 2
 224                 crc ^= *p++ << 24;
 225                 crc = (crc << 2) ^ crc32table_be[crc >> 30];
 226                 crc = (crc << 2) ^ crc32table_be[crc >> 30];
 227                 crc = (crc << 2) ^ crc32table_be[crc >> 30];
 228                 crc = (crc << 2) ^ crc32table_be[crc >> 30];
 229 # endif
 230         }
 231         return crc;
 232 }
 233 #endif
 234
 235 /*
 236  * A brief CRC tutorial.
 237  *
 238  * A CRC is a long-division remainder.  You add the CRC to the message,
 239  * and the whole thing (message+CRC) is a multiple of the given
 240  * CRC polynomial.  To check the CRC, you can either check that the
 241  * CRC matches the recomputed value, *or* you can check that the
 242  * remainder computed on the message+CRC is 0.  This latter approach
 243  * is used by a lot of hardware implementations, and is why so many
 244  * protocols put the end-of-frame flag after the CRC.
 245  *
 246  * It's actually the same long division you learned in school, except that
 247  * - We're working in binary, so the digits are only 0 and 1, and
 248  * - When dividing polynomials, there are no carries.  Rather than add and
 249  *   subtract, we just xor.  Thus, we tend to get a bit sloppy about
 250  *   the difference between adding and subtracting.
 251  *
 252  * A 32-bit CRC polynomial is actually 33 bits long.  But since it's
 253  * 33 bits long, bit 32 is always going to be set, so usually the CRC
 254  * is written in hex with the most significant bit omitted.  (If you're
 255  * familiar with the IEEE 754 floating-point format, it's the same idea.)
 256  *
 257  * Note that a CRC is computed over a string of *bits*, so you have
 258  * to decide on the endianness of the bits within each byte.  To get
 259  * the best error-detecting properties, this should correspond to the
 260  * order they're actually sent.  For example, standard RS-232 serial is
 261  * little-endian; the most significant bit (sometimes used for parity)
 262  * is sent last.  And when appending a CRC word to a message, you should
 263  * do it in the right order, matching the endianness.
 264  *
 265  * Just like with ordinary division, the remainder is always smaller than
 266  * the divisor (the CRC polynomial) you're dividing by.  Each step of the
 267  * division, you take one more digit (bit) of the dividend and append it
 268  * to the current remainder.  Then you figure out the appropriate multiple
 269  * of the divisor to subtract to being the remainder back into range.
 270  * In binary, it's easy - it has to be either 0 or 1, and to make the
 271  * XOR cancel, it's just a copy of bit 32 of the remainder.
 272  *
 273  * When computing a CRC, we don't care about the quotient, so we can
 274  * throw the quotient bit away, but subtract the appropriate multiple of
 275  * the polynomial from the remainder and we're back to where we started,
 276  * ready to process the next bit.
 277  *
 278  * A big-endian CRC written this way would be coded like:
 279  * for (i = 0; i < input_bits; i++) {
 280  *      multiple = remainder & 0x80000000 ? CRCPOLY : 0;
 281  *      remainder = (remainder << 1 | next_input_bit()) ^ multiple;
 282  * }
 283  * Notice how, to get at bit 32 of the shifted remainder, we look
 284  * at bit 31 of the remainder *before* shifting it.
 285  *
 286  * But also notice how the next_input_bit() bits we're shifting into
 287  * the remainder don't actually affect any decision-making until
 288  * 32 bits later.  Thus, the first 32 cycles of this are pretty boring.
 289  * Also, to add the CRC to a message, we need a 32-bit-long hole for it at
 290  * the end, so we have to add 32 extra cycles shifting in zeros at the
 291  * end of every message,
 292  *
 293  * So the standard trick is to rearrage merging in the next_input_bit()
 294  * until the moment it's needed.  Then the first 32 cycles can be precomputed,
 295  * and merging in the final 32 zero bits to make room for the CRC can be
 296  * skipped entirely.
 297  * This changes the code to:
 298  * for (i = 0; i < input_bits; i++) {
 299  *      remainder ^= next_input_bit() << 31;
 300  *      multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
 301  *      remainder = (remainder << 1) ^ multiple;
 302  * }
 303  * With this optimization, the little-endian code is simpler:
 304  * for (i = 0; i < input_bits; i++) {
 305  *      remainder ^= next_input_bit();
 306  *      multiple = (remainder & 1) ? CRCPOLY : 0;
 307  *      remainder = (remainder >> 1) ^ multiple;
 308  * }
 309  *
 310  * Note that the other details of endianness have been hidden in CRCPOLY
 311  * (which must be bit-reversed) and next_input_bit().
 312  *
 313  * However, as long as next_input_bit is returning the bits in a sensible
 314  * order, we can actually do the merging 8 or more bits at a time rather
 315  * than one bit at a time:
 316  * for (i = 0; i < input_bytes; i++) {
 317  *      remainder ^= next_input_byte() << 24;
 318  *      for (j = 0; j < 8; j++) {
 319  *              multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
 320  *              remainder = (remainder << 1) ^ multiple;
 321  *      }
 322  * }
 323  * Or in little-endian:
 324  * for (i = 0; i < input_bytes; i++) {
 325  *      remainder ^= next_input_byte();
 326  *      for (j = 0; j < 8; j++) {
 327  *              multiple = (remainder & 1) ? CRCPOLY : 0;
 328  *              remainder = (remainder << 1) ^ multiple;
 329  *      }
 330  * }
 331  * If the input is a multiple of 32 bits, you can even XOR in a 32-bit
 332  * word at a time and increase the inner loop count to 32.
 333  *
 334  * You can also mix and match the two loop styles, for example doing the
 335  * bulk of a message byte-at-a-time and adding bit-at-a-time processing
 336  * for any fractional bytes at the end.
 337  *
 338  * The only remaining optimization is to the byte-at-a-time table method.
 339  * Here, rather than just shifting one bit of the remainder to decide
 340  * in the correct multiple to subtract, we can shift a byte at a time.
 341  * This produces a 40-bit (rather than a 33-bit) intermediate remainder,
 342  * but again the multiple of the polynomial to subtract depends only on
 343  * the high bits, the high 8 bits in this case.
 344  *
 345  * The multile we need in that case is the low 32 bits of a 40-bit
 346  * value whose high 8 bits are given, and which is a multiple of the
 347  * generator polynomial.  This is simply the CRC-32 of the given
 348  * one-byte message.
 349  *
 350  * Two more details: normally, appending zero bits to a message which
 351  * is already a multiple of a polynomial produces a larger multiple of that
 352  * polynomial.  To enable a CRC to detect this condition, it's common to
 353  * invert the CRC before appending it.  This makes the remainder of the
 354  * message+crc come out not as zero, but some fixed non-zero value.
 355  *
 356  * The same problem applies to zero bits prepended to the message, and
 357  * a similar solution is used.  Instead of starting with a remainder of
 358  * 0, an initial remainder of all ones is used.  As long as you start
 359  * the same way on decoding, it doesn't make a difference.
 360  */
 361
 362
 363 /**
 364  * init_crc32(): generates CRC32 tables
 365  *
 366  * On successful initialization, use count is increased.
 367  * This guarantees that the library functions will stay resident
 368  * in memory, and prevents someone from 'rmmod crc32' while
 369  * a driver that needs it is still loaded.
 370  * This also greatly simplifies drivers, as there's no need
 371  * to call an initialization/cleanup function from each driver.
 372  * Since crc32.o is a library module, there's no requirement
 373  * that the user can unload it.
 374  */
 375 int
 376 init_crc32(void)
 377 {
 378         int rc1, rc2, rc;
 379         rc1 = crc32init_le();
 380         rc2 = crc32init_be();
 381         rc = rc1 || rc2;
 382         return rc;
 383 }
 384
 385 /**
 386  * cleanup_crc32(): frees crc32 data when no longer needed
 387  */
 388 void
 389 cleanup_crc32(void)
 390 {
 391         crc32cleanup_le();
 392         crc32cleanup_be();
 393 }