]>
git.ipfire.org Git - thirdparty/mdadm.git/blob - crc32.c
1 /* crc32.c -- compute the CRC-32 of a data stream
2 * Copyright (C) 1995-2003 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
5 * Note: zlib license from from zlib.h added explicitly as mdadm does
6 * not include zlib.h. License from v1.2.2 of zlib:
8 * This software is provided 'as-is', without any express or implied
9 * warranty. In no event will the authors be held liable for any damages
10 * arising from the use of this software.
12 * Permission is granted to anyone to use this software for any purpose,
13 * including commercial applications, and to alter it and redistribute it
14 * freely, subject to the following restrictions:
16 * 1. The origin of this software must not be misrepresented; you must not
17 * claim that you wrote the original software. If you use this software
18 * in a product, an acknowledgment in the product documentation would be
19 * appreciated but is not required.
20 * 2. Altered source versions must be plainly marked as such, and must not be
21 * misrepresented as being the original software.
22 * 3. This notice may not be removed or altered from any source distribution.
25 * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
26 * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
27 * tables for updating the shift register in one step with three exclusive-ors
28 * instead of four steps with four exclusive-ors. This results about a factor
29 * of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
35 Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
36 protection on the static variables used to control the first-use generation
37 of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should
38 first call get_crc_table() to initialize the tables before allowing more than
39 one thread to use crc32().
44 # ifndef DYNAMIC_CRC_TABLE
45 # define DYNAMIC_CRC_TABLE
46 # endif /* !DYNAMIC_CRC_TABLE */
49 /* #include "zutil.h" / * for STDC and FAR definitions */
52 #define Z_NULL ((void*)0)
55 typedef long ptrdiff_t;
60 /* Find a four-byte integer type for crc32_little() and crc32_big(). */
62 # ifdef STDC /* need ANSI C limits.h to determine sizes */
65 # if (UINT_MAX == 0xffffffffUL)
66 typedef unsigned int u4
;
68 # if (ULONG_MAX == 0xffffffffUL)
69 typedef unsigned long u4
;
71 # if (USHRT_MAX == 0xffffffffUL)
72 typedef unsigned short u4
;
74 # undef BYFOUR /* can't find a four-byte integer type! */
79 #endif /* !NOBYFOUR */
81 /* Definitions for doing the crc four data bytes at a time. */
83 # define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
84 (((w)&0xff00)<<8)+(((w)&0xff)<<24))
85 local
unsigned long crc32_little
OF((unsigned long,
86 const unsigned char FAR
*, unsigned));
87 local
unsigned long crc32_big
OF((unsigned long,
88 const unsigned char FAR
*, unsigned));
94 #ifdef DYNAMIC_CRC_TABLE
96 local
volatile int crc_table_empty
= 1;
97 local
unsigned long FAR crc_table
[TBLS
][256];
98 local
void make_crc_table
OF((void));
100 local
void write_table
OF((FILE *, const unsigned long FAR
*));
101 #endif /* MAKECRCH */
104 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
105 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.
107 Polynomials over GF(2) are represented in binary, one bit per coefficient,
108 with the lowest powers in the most significant bit. Then adding polynomials
109 is just exclusive-or, and multiplying a polynomial by x is a right shift by
110 one. If we call the above polynomial p, and represent a byte as the
111 polynomial q, also with the lowest power in the most significant bit (so the
112 byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
113 where a mod b means the remainder after dividing a by b.
115 This calculation is done using the shift-register method of multiplying and
116 taking the remainder. The register is initialized to zero, and for each
117 incoming bit, x^32 is added mod p to the register if the bit is a one (where
118 x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
119 x (which is shifting right by one and adding x^32 mod p if the bit shifted
120 out is a one). We start with the highest power (least significant bit) of
121 q and repeat for all eight bits of q.
123 The first table is simply the CRC of all possible eight bit values. This is
124 all the information needed to generate CRCs on data a byte at a time for all
125 combinations of CRC register values and incoming bytes. The remaining tables
126 allow for word-at-a-time CRC calculation for both big-endian and little-
127 endian machines, where a word is four bytes.
129 local
void make_crc_table()
133 unsigned long poly
; /* polynomial exclusive-or pattern */
134 /* terms of polynomial defining this crc (except x^32): */
135 static volatile int first
= 1; /* flag to limit concurrent making */
136 static const unsigned char p
[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
138 /* See if another task is already doing this (not thread-safe, but better
139 than nothing -- significantly reduces duration of vulnerability in
140 case the advice about DYNAMIC_CRC_TABLE is ignored) */
144 /* make exclusive-or pattern from polynomial (0xedb88320UL) */
146 for (n
= 0; n
< sizeof(p
)/sizeof(unsigned char); n
++)
147 poly
|= 1UL << (31 - p
[n
]);
149 /* generate a crc for every 8-bit value */
150 for (n
= 0; n
< 256; n
++) {
151 c
= (unsigned long)n
;
152 for (k
= 0; k
< 8; k
++)
153 c
= c
& 1 ? poly
^ (c
>> 1) : c
>> 1;
158 /* generate crc for each value followed by one, two, and three zeros,
159 and then the byte reversal of those as well as the first table */
160 for (n
= 0; n
< 256; n
++) {
162 crc_table
[4][n
] = REV(c
);
163 for (k
= 1; k
< 4; k
++) {
164 c
= crc_table
[0][c
& 0xff] ^ (c
>> 8);
166 crc_table
[k
+ 4][n
] = REV(c
);
173 else { /* not first */
174 /* wait for the other guy to finish (not efficient, but rare) */
175 while (crc_table_empty
)
180 /* write out CRC tables to crc32.h */
184 out
= fopen("crc32.h", "w");
185 if (out
== NULL
) return;
186 fprintf(out
, "/* crc32.h -- tables for rapid CRC calculation\n");
187 fprintf(out
, " * Generated automatically by crc32.c\n */\n\n");
188 fprintf(out
, "local const unsigned long FAR ");
189 fprintf(out
, "crc_table[TBLS][256] =\n{\n {\n");
190 write_table(out
, crc_table
[0]);
192 fprintf(out
, "#ifdef BYFOUR\n");
193 for (k
= 1; k
< 8; k
++) {
194 fprintf(out
, " },\n {\n");
195 write_table(out
, crc_table
[k
]);
197 fprintf(out
, "#endif\n");
199 fprintf(out
, " }\n};\n");
202 #endif /* MAKECRCH */
206 local
void write_table(out
, table
)
208 const unsigned long FAR
*table
;
212 for (n
= 0; n
< 256; n
++)
213 fprintf(out
, "%s0x%08lxUL%s", n
% 5 ? "" : " ", table
[n
],
214 n
== 255 ? "\n" : (n
% 5 == 4 ? ",\n" : ", "));
216 #endif /* MAKECRCH */
218 #else /* !DYNAMIC_CRC_TABLE */
219 /* ========================================================================
220 * Tables of CRC-32s of all single-byte values, made by make_crc_table().
223 #endif /* DYNAMIC_CRC_TABLE */
225 /* =========================================================================
226 * This function can be used by asm versions of crc32()
228 const unsigned long FAR
* ZEXPORT
get_crc_table(void)
230 #ifdef DYNAMIC_CRC_TABLE
233 #endif /* DYNAMIC_CRC_TABLE */
234 return (const unsigned long FAR
*)crc_table
;
237 /* ========================================================================= */
238 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
239 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
241 /* ========================================================================= */
242 unsigned long ZEXPORT
crc32(
244 const unsigned char FAR
*buf
,
247 if (buf
== Z_NULL
) return 0UL;
249 #ifdef DYNAMIC_CRC_TABLE
252 #endif /* DYNAMIC_CRC_TABLE */
255 if (sizeof(void *) == sizeof(ptrdiff_t)) {
259 if (*((unsigned char *)(&endian
)))
260 return crc32_little(crc
, buf
, len
);
262 return crc32_big(crc
, buf
, len
);
265 /* crc = crc ^ 0xffffffffUL;*/
273 return crc
/* ^ 0xffffffffUL*/;
278 /* ========================================================================= */
279 #define DOLIT4 c ^= *buf4++; \
280 c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
281 crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
282 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
284 /* ========================================================================= */
285 local
unsigned long crc32_little(crc
, buf
, len
)
287 const unsigned char FAR
*buf
;
291 register const u4 FAR
*buf4
;
295 while (len
&& ((ptrdiff_t)buf
& 3)) {
296 c
= crc_table
[0][(c
^ *buf
++) & 0xff] ^ (c
>> 8);
300 buf4
= (const u4 FAR
*)buf
;
309 buf
= (const unsigned char FAR
*)buf4
;
312 c
= crc_table
[0][(c
^ *buf
++) & 0xff] ^ (c
>> 8);
315 return (unsigned long)c
;
318 /* ========================================================================= */
319 #define DOBIG4 c ^= *++buf4; \
320 c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
321 crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
322 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
324 /* ========================================================================= */
325 local
unsigned long crc32_big(crc
, buf
, len
)
327 const unsigned char FAR
*buf
;
331 register const u4 FAR
*buf4
;
335 while (len
&& ((ptrdiff_t)buf
& 3)) {
336 c
= crc_table
[4][(c
>> 24) ^ *buf
++] ^ (c
<< 8);
340 buf4
= (const u4 FAR
*)buf
;
351 buf
= (const unsigned char FAR
*)buf4
;
354 c
= crc_table
[4][(c
>> 24) ^ *buf
++] ^ (c
<< 8);
357 return (unsigned long)(REV(c
));