diff options
author | Mark Adler <madler@alumni.caltech.edu> | 2011-09-09 23:13:27 -0700 |
---|---|---|
committer | Mark Adler <madler@alumni.caltech.edu> | 2011-09-09 23:13:27 -0700 |
commit | 8a2acbffc86012de3523ecf91db2c4ea1b1c4ea2 (patch) | |
tree | c461eb314065024b6cb87d136e107dca2cc09a33 /crc32.c | |
parent | 56bcb184fac036a45cb8937238d51778d0a796aa (diff) | |
download | zlib-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.c | 60 |
1 files changed, 9 insertions, 51 deletions
@@ -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 | */ | ||
14 | local int crc_table_empty = 1; | 17 | local int crc_table_empty = 1; |
15 | local uLongf crc_table[256]; | 18 | local uLong crc_table[256]; |
16 | local 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 | */ | ||
42 | local void make_crc_table() | 20 | local 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 | */ |
68 | local uLongf crc_table[256] = { | 38 | local 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 | */ | ||
127 | uLongf *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 | /* ========================================================================= */ |
142 | uLong crc32(crc, buf, len) | 100 | uLong 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; |