aboutsummaryrefslogtreecommitdiff
path: root/crc32.c
diff options
context:
space:
mode:
authorMark Adler <madler@alumni.caltech.edu>2011-09-09 23:13:27 -0700
committerMark Adler <madler@alumni.caltech.edu>2011-09-09 23:13:27 -0700
commit8a2acbffc86012de3523ecf91db2c4ea1b1c4ea2 (patch)
treec461eb314065024b6cb87d136e107dca2cc09a33 /crc32.c
parent56bcb184fac036a45cb8937238d51778d0a796aa (diff)
downloadzlib-8a2acbffc86012de3523ecf91db2c4ea1b1c4ea2.tar.gz
zlib-8a2acbffc86012de3523ecf91db2c4ea1b1c4ea2.tar.bz2
zlib-8a2acbffc86012de3523ecf91db2c4ea1b1c4ea2.zip
zlib 1.0-prev1.0-pre
Diffstat (limited to 'crc32.c')
-rw-r--r--crc32.c60
1 files changed, 9 insertions, 51 deletions
diff --git a/crc32.c b/crc32.c
index 7d6aa02..4089255 100644
--- a/crc32.c
+++ b/crc32.c
@@ -1,5 +1,5 @@
1/* crc32.c -- compute the CRC-32 of a data stream 1/* crc32.c -- compute the CRC-32 of a data stream
2 * Copyright (C) 1995-1996 Mark Adler 2 * Copyright (C) 1995 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h 3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */ 4 */
5 5
@@ -10,53 +10,23 @@
10#define local static 10#define local static
11 11
12#ifdef DYNAMIC_CRC_TABLE 12#ifdef DYNAMIC_CRC_TABLE
13 13/* =========================================================================
14 * Make the crc table. This function is needed only if you want to compute
15 * the table dynamically.
16 */
14local int crc_table_empty = 1; 17local int crc_table_empty = 1;
15local uLongf crc_table[256]; 18local uLong 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 19
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() 20local void make_crc_table()
43{ 21{
44 uLong c; 22 uLong c;
45 int n, k; 23 int n, k;
46 uLong poly; /* polynomial exclusive-or pattern */
47 /* terms of polynomial defining this crc (except x^32): */
48 static 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 24
55 for (n = 0; n < 256; n++) 25 for (n = 0; n < 256; n++)
56 { 26 {
57 c = (uLong)n; 27 c = (uLong)n;
58 for (k = 0; k < 8; k++) 28 for (k = 0; k < 8; k++)
59 c = c & 1 ? poly ^ (c >> 1) : c >> 1; 29 c = c & 1 ? 0xedb88320L ^ (c >> 1) : c >> 1;
60 crc_table[n] = c; 30 crc_table[n] = c;
61 } 31 }
62 crc_table_empty = 0; 32 crc_table_empty = 0;
@@ -65,7 +35,7 @@ local void make_crc_table()
65/* ======================================================================== 35/* ========================================================================
66 * Table of CRC-32's of all single-byte values (made by make_crc_table) 36 * Table of CRC-32's of all single-byte values (made by make_crc_table)
67 */ 37 */
68local uLongf crc_table[256] = { 38local uLong crc_table[] = {
69 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L, 39 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
70 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L, 40 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
71 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L, 41 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
@@ -121,18 +91,6 @@ local uLongf crc_table[256] = {
121}; 91};
122#endif 92#endif
123 93
124/* =========================================================================
125 * This function can be used by asm versions of crc32()
126 */
127uLongf *get_crc_table()
128{
129#ifdef DYNAMIC_CRC_TABLE
130 if (crc_table_empty) make_crc_table();
131#endif
132 return (uLongf *)crc_table;
133}
134
135/* ========================================================================= */
136#define DO1(buf) crc = crc_table[((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8); 94#define DO1(buf) crc = crc_table[((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8);
137#define DO2(buf) DO1(buf); DO1(buf); 95#define DO2(buf) DO1(buf); DO1(buf);
138#define DO4(buf) DO2(buf); DO2(buf); 96#define DO4(buf) DO2(buf); DO2(buf);
@@ -141,7 +99,7 @@ uLongf *get_crc_table()
141/* ========================================================================= */ 99/* ========================================================================= */
142uLong crc32(crc, buf, len) 100uLong crc32(crc, buf, len)
143 uLong crc; 101 uLong crc;
144 const Bytef *buf; 102 Bytef *buf;
145 uInt len; 103 uInt len;
146{ 104{
147 if (buf == Z_NULL) return 0L; 105 if (buf == Z_NULL) return 0L;