diff options
author | Mark Adler <madler@alumni.caltech.edu> | 2011-09-09 23:11:37 -0700 |
---|---|---|
committer | Mark Adler <madler@alumni.caltech.edu> | 2011-09-09 23:11:37 -0700 |
commit | 56bcb184fac036a45cb8937238d51778d0a796aa (patch) | |
tree | 7b127418b30e135f8ce27ec136038b5090540820 /crc32.c | |
parent | 25e5325501edade156e897f95afdaa2be78ad9a3 (diff) | |
download | zlib-56bcb184fac036a45cb8937238d51778d0a796aa.tar.gz zlib-56bcb184fac036a45cb8937238d51778d0a796aa.tar.bz2 zlib-56bcb184fac036a45cb8937238d51778d0a796aa.zip |
zlib 0.99v0.99
Diffstat (limited to 'crc32.c')
-rw-r--r-- | crc32.c | 60 |
1 files changed, 51 insertions, 9 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 Mark Adler | 2 | * Copyright (C) 1995-1996 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,23 +10,53 @@ | |||
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 | */ | ||
17 | local int crc_table_empty = 1; | 14 | local int crc_table_empty = 1; |
18 | local uLong crc_table[256]; | 15 | local uLongf 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. | ||
19 | 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 | */ | ||
20 | local void make_crc_table() | 42 | local void make_crc_table() |
21 | { | 43 | { |
22 | uLong c; | 44 | uLong c; |
23 | int n, k; | 45 | 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]); | ||
24 | 54 | ||
25 | for (n = 0; n < 256; n++) | 55 | for (n = 0; n < 256; n++) |
26 | { | 56 | { |
27 | c = (uLong)n; | 57 | c = (uLong)n; |
28 | for (k = 0; k < 8; k++) | 58 | for (k = 0; k < 8; k++) |
29 | c = c & 1 ? 0xedb88320L ^ (c >> 1) : c >> 1; | 59 | c = c & 1 ? poly ^ (c >> 1) : c >> 1; |
30 | crc_table[n] = c; | 60 | crc_table[n] = c; |
31 | } | 61 | } |
32 | crc_table_empty = 0; | 62 | crc_table_empty = 0; |
@@ -35,7 +65,7 @@ local void make_crc_table() | |||
35 | /* ======================================================================== | 65 | /* ======================================================================== |
36 | * Table of CRC-32's of all single-byte values (made by make_crc_table) | 66 | * Table of CRC-32's of all single-byte values (made by make_crc_table) |
37 | */ | 67 | */ |
38 | local uLong crc_table[] = { | 68 | local uLongf crc_table[256] = { |
39 | 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L, | 69 | 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L, |
40 | 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L, | 70 | 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L, |
41 | 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L, | 71 | 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L, |
@@ -91,6 +121,18 @@ local uLong crc_table[] = { | |||
91 | }; | 121 | }; |
92 | #endif | 122 | #endif |
93 | 123 | ||
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 | /* ========================================================================= */ | ||
94 | #define DO1(buf) crc = crc_table[((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8); | 136 | #define DO1(buf) crc = crc_table[((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8); |
95 | #define DO2(buf) DO1(buf); DO1(buf); | 137 | #define DO2(buf) DO1(buf); DO1(buf); |
96 | #define DO4(buf) DO2(buf); DO2(buf); | 138 | #define DO4(buf) DO2(buf); DO2(buf); |
@@ -99,7 +141,7 @@ local uLong crc_table[] = { | |||
99 | /* ========================================================================= */ | 141 | /* ========================================================================= */ |
100 | uLong crc32(crc, buf, len) | 142 | uLong crc32(crc, buf, len) |
101 | uLong crc; | 143 | uLong crc; |
102 | Bytef *buf; | 144 | const Bytef *buf; |
103 | uInt len; | 145 | uInt len; |
104 | { | 146 | { |
105 | if (buf == Z_NULL) return 0L; | 147 | if (buf == Z_NULL) return 0L; |