SecurityServer/MacYarrow/zlib/crc32.c

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