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