palacios/src/geekos/crc32.c

   1 /* Copyright abandoned; this code is in the public domain. */
   2 /* Provided to GNUnet by peter@horizon.com */
   3
   4 /*
   5  * Adapted for GeekOS by David Hovemeyer
   6  * Code downloaded from OVM (http://www.ovmj.org)
   7  */
   8
   9 #include <geekos/crc32.h>
  10 #include <geekos/kassert.h>
  11 #include <geekos/serial.h>
  12 #include <geekos/debug.h>
  13
  14 #define POLYNOMIAL (ulong_t)0xedb88320
  15 static ulong_t crc_table[256];
  16
  17 /*
  18  * This routine writes each crc_table entry exactly once,
  19  * with the correct final value.  Thus, it is safe to call
  20  * even on a table that someone else is using concurrently.
  21  */
  22 void Init_CRC32(void) {
  23   unsigned int i, j;
  24   ulong_t h = 1;
  25   PrintBoth("Initializing CRC32\n");
  26   crc_table[0] = 0;
  27   for (i = 128; i; i >>= 1) {
  28     h = (h >> 1) ^ ((h & 1) ? POLYNOMIAL : 0);
  29     /* h is now crc_table[i] */
  30     for (j = 0; j < 256; j += 2*i)
  31       crc_table[i+j] = crc_table[j] ^ h;
  32   }
  33 }
  34
  35 /*
  36  * This computes the standard preset and inverted CRC, as used
  37  * by most networking standards.  Start by passing in an initial
  38  * chaining value of 0, and then pass in the return value from the
  39  * previous crc32() call.  The final return value is the CRC.
  40  * Note that this is a little-endian CRC, which is best used with
  41  * data transmitted lsbit-first, and it should, itself, be appended
  42  * to data in little-endian byte and bit order to preserve the
  43  * property of detecting all burst errors of length 32 bits or less.
  44  */
  45 ulong_t crc32(ulong_t crc, char const *buf, size_t len) {
  46   KASSERT(crc_table[255] != 0);
  47   crc ^= 0xffffffff;
  48   while (len--)
  49     crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
  50   return crc ^ 0xffffffff;
  51 }
  52
  53 /* end of crc32.c */