]> git.ipfire.org Git - thirdparty/mdadm.git/blame_incremental - crc32.c
clustermd_tests: add test case to test manage_re-add against cluster-raid10
[thirdparty/mdadm.git] / crc32.c
... / ...
CommitLineData
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
4 *
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:
7 *
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.
11 *
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:
15 *
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.
23 *
24 *
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.
30 */
31
32/* @(#) $Id$ */
33
34/*
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().
40 */
41
42#ifdef MAKECRCH
43# include <stdio.h>
44# ifndef DYNAMIC_CRC_TABLE
45# define DYNAMIC_CRC_TABLE
46# endif /* !DYNAMIC_CRC_TABLE */
47#endif /* MAKECRCH */
48
49/* #include "zutil.h" / * for STDC and FAR definitions */
50#define STDC
51#define FAR
52#define Z_NULL ((void*)0)
53#define OF(X) X
54#define ZEXPORT
55typedef long ptrdiff_t;
56#define NOBYFOUR
57
58#define local static
59
60/* Find a four-byte integer type for crc32_little() and crc32_big(). */
61#ifndef NOBYFOUR
62# ifdef STDC /* need ANSI C limits.h to determine sizes */
63# include <limits.h>
64# define BYFOUR
65# if (UINT_MAX == 0xffffffffUL)
66 typedef unsigned int u4;
67# else
68# if (ULONG_MAX == 0xffffffffUL)
69 typedef unsigned long u4;
70# else
71# if (USHRT_MAX == 0xffffffffUL)
72 typedef unsigned short u4;
73# else
74# undef BYFOUR /* can't find a four-byte integer type! */
75# endif
76# endif
77# endif
78# endif /* STDC */
79#endif /* !NOBYFOUR */
80
81/* Definitions for doing the crc four data bytes at a time. */
82#ifdef BYFOUR
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));
89# define TBLS 8
90#else
91# define TBLS 1
92#endif /* BYFOUR */
93
94#ifdef DYNAMIC_CRC_TABLE
95
96local volatile int crc_table_empty = 1;
97local unsigned long FAR crc_table[TBLS][256];
98local void make_crc_table OF((void));
99#ifdef MAKECRCH
100 local void write_table OF((FILE *, const unsigned long FAR *));
101#endif /* MAKECRCH */
102
103/*
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.
106
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.
114
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.
122
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.
128*/
129local void make_crc_table()
130{
131 unsigned long c;
132 int n, k;
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};
137
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) */
141 if (first) {
142 first = 0;
143
144 /* make exclusive-or pattern from polynomial (0xedb88320UL) */
145 poly = 0UL;
146 for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
147 poly |= 1UL << (31 - p[n]);
148
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;
154 crc_table[0][n] = c;
155 }
156
157#ifdef BYFOUR
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++) {
161 c = crc_table[0][n];
162 crc_table[4][n] = REV(c);
163 for (k = 1; k < 4; k++) {
164 c = crc_table[0][c & 0xff] ^ (c >> 8);
165 crc_table[k][n] = c;
166 crc_table[k + 4][n] = REV(c);
167 }
168 }
169#endif /* BYFOUR */
170
171 crc_table_empty = 0;
172 }
173 else { /* not first */
174 /* wait for the other guy to finish (not efficient, but rare) */
175 while (crc_table_empty)
176 ;
177 }
178
179#ifdef MAKECRCH
180 /* write out CRC tables to crc32.h */
181 {
182 FILE *out;
183
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]);
191# ifdef BYFOUR
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]);
196 }
197 fprintf(out, "#endif\n");
198# endif /* BYFOUR */
199 fprintf(out, " }\n};\n");
200 fclose(out);
201 }
202#endif /* MAKECRCH */
203}
204
205#ifdef MAKECRCH
206local void write_table(out, table)
207 FILE *out;
208 const unsigned long FAR *table;
209{
210 int n;
211
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" : ", "));
215}
216#endif /* MAKECRCH */
217
218#else /* !DYNAMIC_CRC_TABLE */
219/* ========================================================================
220 * Tables of CRC-32s of all single-byte values, made by make_crc_table().
221 */
222#include "crc32.h"
223#endif /* DYNAMIC_CRC_TABLE */
224
225/* =========================================================================
226 * This function can be used by asm versions of crc32()
227 */
228const unsigned long FAR * ZEXPORT get_crc_table(void)
229{
230#ifdef DYNAMIC_CRC_TABLE
231 if (crc_table_empty)
232 make_crc_table();
233#endif /* DYNAMIC_CRC_TABLE */
234 return (const unsigned long FAR *)crc_table;
235}
236
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
240
241/* ========================================================================= */
242unsigned long ZEXPORT crc32(
243 unsigned long crc,
244 const unsigned char FAR *buf,
245 unsigned len)
246{
247 if (buf == Z_NULL) return 0UL;
248
249#ifdef DYNAMIC_CRC_TABLE
250 if (crc_table_empty)
251 make_crc_table();
252#endif /* DYNAMIC_CRC_TABLE */
253
254#ifdef BYFOUR
255 if (sizeof(void *) == sizeof(ptrdiff_t)) {
256 u4 endian;
257
258 endian = 1;
259 if (*((unsigned char *)(&endian)))
260 return crc32_little(crc, buf, len);
261 else
262 return crc32_big(crc, buf, len);
263 }
264#endif /* BYFOUR */
265/* crc = crc ^ 0xffffffffUL;*/
266 while (len >= 8) {
267 DO8;
268 len -= 8;
269 }
270 if (len) do {
271 DO1;
272 } while (--len);
273 return crc /* ^ 0xffffffffUL*/;
274}
275
276#ifdef BYFOUR
277
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
283
284/* ========================================================================= */
285local unsigned long crc32_little(crc, buf, len)
286 unsigned long crc;
287 const unsigned char FAR *buf;
288 unsigned len;
289{
290 register u4 c;
291 register const u4 FAR *buf4;
292
293 c = (u4)crc;
294 c = ~c;
295 while (len && ((ptrdiff_t)buf & 3)) {
296 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
297 len--;
298 }
299
300 buf4 = (const u4 FAR *)buf;
301 while (len >= 32) {
302 DOLIT32;
303 len -= 32;
304 }
305 while (len >= 4) {
306 DOLIT4;
307 len -= 4;
308 }
309 buf = (const unsigned char FAR *)buf4;
310
311 if (len) do {
312 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
313 } while (--len);
314 c = ~c;
315 return (unsigned long)c;
316}
317
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
323
324/* ========================================================================= */
325local unsigned long crc32_big(crc, buf, len)
326 unsigned long crc;
327 const unsigned char FAR *buf;
328 unsigned len;
329{
330 register u4 c;
331 register const u4 FAR *buf4;
332
333 c = REV((u4)crc);
334 c = ~c;
335 while (len && ((ptrdiff_t)buf & 3)) {
336 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
337 len--;
338 }
339
340 buf4 = (const u4 FAR *)buf;
341 buf4--;
342 while (len >= 32) {
343 DOBIG32;
344 len -= 32;
345 }
346 while (len >= 4) {
347 DOBIG4;
348 len -= 4;
349 }
350 buf4++;
351 buf = (const unsigned char FAR *)buf4;
352
353 if (len) do {
354 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
355 } while (--len);
356 c = ~c;
357 return (unsigned long)(REV(c));
358}
359
360#endif /* BYFOUR */