crc32.c Source File

00001 /* crc32.c -- compute the CRC-32 of a data stream
00002  * Copyright (C) 1995-1998 Mark Adler
00003  * For conditions of distribution and use, see copyright notice in zlib.h 
00004  */
00005 
00006 /* @(#) $Id$ */
00007 
00008 #include "zlib.h"
00009 
00010 #define local static
00011 
00012 #ifdef DYNAMIC_CRC_TABLE
00013 
00014 local int crc_table_empty = 1;
00015 local uLongf crc_table[256];
00016 local void make_crc_table OF((void));
00017 
00018 /*
00019   Generate a table for a byte-wise 32-bit CRC calculation on the polynomial:
00020   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.
00021 
00022   Polynomials over GF(2) are represented in binary, one bit per coefficient,
00023   with the lowest powers in the most significant bit.  Then adding polynomials
00024   is just exclusive-or, and multiplying a polynomial by x is a right shift by
00025   one.  If we call the above polynomial p, and represent a byte as the
00026   polynomial q, also with the lowest power in the most significant bit (so the
00027   byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
00028   where a mod b means the remainder after dividing a by b.
00029 
00030   This calculation is done using the shift-register method of multiplying and
00031   taking the remainder.  The register is initialized to zero, and for each
00032   incoming bit, x^32 is added mod p to the register if the bit is a one (where
00033   x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
00034   x (which is shifting right by one and adding x^32 mod p if the bit shifted
00035   out is a one).  We start with the highest power (least significant bit) of
00036   q and repeat for all eight bits of q.
00037 
00038   The table is simply the CRC of all possible eight bit values.  This is all
00039   the information needed to generate CRC's on data a byte at a time for all
00040   combinations of CRC register values and incoming bytes.
00041 */
00042 local void make_crc_table()
00043 {
00044   uLong c;
00045   int n, k;
00046   uLong poly;            /* polynomial exclusive-or pattern */
00047   /* terms of polynomial defining this crc (except x^32): */
00048   static const Byte p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
00049 
00050   /* make exclusive-or pattern from polynomial (0xedb88320L) */
00051   poly = 0L;
00052   for (n = 0; n < sizeof(p)/sizeof(Byte); n++)
00053     poly |= 1L << (31 - p[n]);
00054  
00055   for (n = 0; n < 256; n++)
00056   {
00057     c = (uLong)n;
00058     for (k = 0; k < 8; k++)
00059       c = c & 1 ? poly ^ (c >> 1) : c >> 1;
00060     crc_table[n] = c;
00061   }
00062   crc_table_empty = 0;
00063 }
00064 #else
00065 /* ========================================================================
00066  * Table of CRC-32's of all single-byte values (made by make_crc_table)
00067  */
00068 local const uLongf crc_table[256] = {
00069   0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
00070   0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
00071   0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
00072   0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
00073   0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
00074   0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
00075   0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
00076   0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
00077   0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
00078   0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
00079   0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
00080   0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
00081   0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
00082   0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
00083   0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
00084   0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
00085   0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
00086   0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
00087   0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
00088   0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
00089   0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
00090   0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
00091   0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
00092   0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
00093   0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
00094   0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
00095   0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
00096   0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
00097   0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
00098   0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
00099   0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
00100   0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
00101   0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
00102   0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
00103   0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
00104   0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
00105   0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
00106   0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
00107   0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
00108   0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
00109   0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
00110   0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
00111   0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
00112   0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
00113   0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
00114   0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
00115   0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
00116   0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
00117   0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
00118   0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
00119   0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
00120   0x2d02ef8dL
00121 };
00122 #endif
00123 
00124 /* =========================================================================
00125  * This function can be used by asm versions of crc32()
00126  */
00127 const uLongf * ZEXPORT get_crc_table()
00128 {
00129 #ifdef DYNAMIC_CRC_TABLE
00130   if (crc_table_empty) make_crc_table();
00131 #endif
00132   return (const uLongf *)crc_table;
00133 }
00134 
00135 /* ========================================================================= */
00136 #define DO1(buf) crc = crc_table[((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8);
00137 #define DO2(buf)  DO1(buf); DO1(buf);
00138 #define DO4(buf)  DO2(buf); DO2(buf);
00139 #define DO8(buf)  DO4(buf); DO4(buf);
00140 
00141 /* ========================================================================= */
00142 uLong ZEXPORT crc32(crc, buf, len)
00143     uLong crc;
00144     const Bytef *buf;
00145     uInt len;
00146 {
00147     if (buf == Z_NULL) return 0L;
00148 #ifdef DYNAMIC_CRC_TABLE
00149     if (crc_table_empty)
00150       make_crc_table();
00151 #endif
00152     crc = crc ^ 0xffffffffL;
00153     while (len >= 8)
00154     {
00155       DO8(buf);
00156       len -= 8;
00157     }
00158     if (len) do {
00159       DO1(buf);
00160     } while (--len);
00161     return crc ^ 0xffffffffL;
00162 }