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 __U_BOOT__       /* Shut down "ANSI does not permit..." warnings */
  12 #include <common.h>     /* to get command definitions like CFG_CMD_JFFS2 */
  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 ulong crc32(ulong crc, const unsigned char *buf, uint len)
 136 {
 137 #ifdef CONFIG_DYNAMIC_CRC_TABLE
 138     if (crc_table_empty)
 139       make_crc_table();
 140 #endif
 141     crc = crc ^ 0xffffffffL;
 142     while (len >= 8)
 143     {
 144       DO8(buf);
 145       len -= 8;
 146     }
 147     if (len) do {
 148       DO1(buf);
 149     } while (--len);
 150     return crc ^ 0xffffffffL;
 151 }
 152 #ifdef __U_BOOT__
 153 EXPORT_SYMBOL(crc32);
 154 #endif
 155
 156 #if 0
 157
 158 /* No ones complement version. JFFS2 (and other things ?)
 159  * don't use ones compliment in their CRC calculations.
 160  */
 161 uLong crc32_no_comp(uLong crc, const Bytef *buf, uint len)
 162 {
 163 #ifdef CONFIG_DYNAMIC_CRC_TABLE
 164     if (crc_table_empty)
 165       make_crc_table();
 166 #endif
 167     while (len >= 8)
 168     {
 169       DO8(buf);
 170       len -= 8;
 171     }
 172     if (len) do {
 173       DO1(buf);
 174     } while (--len);
 175
 176     return crc;
 177 }
 178
 179 #endif