lib/crc32.c

   1 /*
   2  * This file is derived from crc32.c from the zlib-1.1.3 distribution
   3  * by Jean-loup Gailly and Mark Adler.
   4  */
   5
   6 /* crc32.c -- compute the CRC-32 of a data stream
   7  * Copyright (C) 1995-1998 Mark Adler
   8  * For conditions of distribution and use, see copyright notice in zlib.h
   9  */
  10
  11 #ifdef __BAREBOX__      /* Shut down "ANSI does not permit..." warnings */
  12 #include <common.h>
  13 #endif
  14
  15 #ifdef CONFIG_DYNAMIC_CRC_TABLE
  16
  17 static int crc_table_empty = 1;
  18 static ulong crc_table[256];
  19 static void make_crc_table(void);
  20
  21 /*
  22   Generate a table for a byte-wise 32-bit CRC calculation on the polynomial:
  23   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.
  24
  25   Polynomials over GF(2) are represented in binary, one bit per coefficient,
  26   with the lowest powers in the most significant bit.  Then adding polynomials
  27   is just exclusive-or, and multiplying a polynomial by x is a right shift by
  28   one.  If we call the above polynomial p, and represent a byte as the
  29   polynomial q, also with the lowest power in the most significant bit (so the
  30   byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
  31   where a mod b means the remainder after dividing a by b.
  32
  33   This calculation is done using the shift-register method of multiplying and
  34   taking the remainder.  The register is initialized to zero, and for each
  35   incoming bit, x^32 is added mod p to the register if the bit is a one (where
  36   x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
  37   x (which is shifting right by one and adding x^32 mod p if the bit shifted
  38   out is a one).  We start with the highest power (least significant bit) of
  39   q and repeat for all eight bits of q.
  40
  41   The table is simply the CRC of all possible eight bit values.  This is all
  42   the information needed to generate CRC's on data a byte at a time for all
  43   combinations of CRC register values and incoming bytes.
  44 */
  45 static void make_crc_table()
  46 {
  47   ulong c;
  48   int n, k;
  49   ulong poly;            /* polynomial exclusive-or pattern */
  50   /* terms of polynomial defining this crc (except x^32): */
  51   static const char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
  52
  53   /* make exclusive-or pattern from polynomial (0xedb88320L) */
  54   poly = 0L;
  55   for (n = 0; n < sizeof(p)/sizeof(char); n++)
  56     poly |= 1L << (31 - p[n]);
  57
  58   for (n = 0; n < 256; n++)
  59   {
  60     c = (ulong)n;
  61     for (k = 0; k < 8; k++)
  62       c = c & 1 ? poly ^ (c >> 1) : c >> 1;
  63     crc_table[n] = c;
  64   }
  65   crc_table_empty = 0;
  66 }
  67 #else
  68 /* ========================================================================
  69  * Table of CRC-32's of all single-byte values (made by make_crc_table)
  70  */
  71 static const ulong crc_table[256] = {
  72   0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
  73   0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
  74   0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
  75   0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
  76   0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
  77   0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
  78   0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
  79   0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
  80   0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
  81   0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
  82   0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
  83   0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
  84   0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
  85   0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
  86   0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
  87   0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
  88   0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
  89   0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
  90   0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
  91   0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
  92   0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
  93   0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
  94   0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
  95   0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
  96   0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
  97   0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
  98   0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
  99   0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
 100   0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
 101   0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
 102   0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
 103   0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
 104   0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
 105   0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
 106   0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
 107   0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
 108   0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
 109   0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
 110   0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
 111   0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
 112   0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
 113   0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
 114   0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
 115   0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
 116   0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
 117   0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
 118   0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
 119   0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
 120   0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
 121   0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
 122   0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
 123   0x2d02ef8dL
 124 };
 125 #endif
 126
 127
 128 /* ========================================================================= */
 129 #define DO1(buf) crc = crc_table[((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8);
 130 #define DO2(buf)  DO1(buf); DO1(buf);
 131 #define DO4(buf)  DO2(buf); DO2(buf);
 132 #define DO8(buf)  DO4(buf); DO4(buf);
 133
 134 /* ========================================================================= */
 135 uint32_t crc32(uint32_t crc, const void *_buf, unsigned int len)
 136 {
 137     const unsigned char *buf = _buf;
 138
 139 #ifdef CONFIG_DYNAMIC_CRC_TABLE
 140     if (crc_table_empty)
 141       make_crc_table();
 142 #endif
 143     crc = crc ^ 0xffffffffL;
 144     while (len >= 8)
 145     {
 146       DO8(buf);
 147       len -= 8;
 148     }
 149     if (len) do {
 150       DO1(buf);
 151     } while (--len);
 152     return crc ^ 0xffffffffL;
 153 }
 154 #ifdef __BAREBOX__
 155 EXPORT_SYMBOL(crc32);
 156 #endif
 157
 158 /* No ones complement version. JFFS2 (and other things ?)
 159  * don't use ones compliment in their CRC calculations.
 160  */
 161 uint32_t crc32_no_comp(uint32_t crc, const void *_buf, unsigned int len)
 162 {
 163    const unsigned char *buf = _buf;
 164
 165 #ifdef CONFIG_DYNAMIC_CRC_TABLE
 166     if (crc_table_empty)
 167       make_crc_table();
 168 #endif
 169     while (len >= 8)
 170     {
 171       DO8(buf);
 172       len -= 8;
 173     }
 174     if (len) do {
 175       DO1(buf);
 176     } while (--len);
 177
 178     return crc;
 179 }
 180