crc32.c revision 1.4 1 1.4 dsl /* $NetBSD: crc32.c,v 1.4 2006/02/18 18:39:58 dsl Exp $ */
2 1.1 christos
3 1.1 christos /* crc32.c -- compute the CRC-32 of a data stream
4 1.1 christos * Copyright (C) 1995-2005 Mark Adler
5 1.1 christos * For conditions of distribution and use, see copyright notice in zlib.h
6 1.1 christos *
7 1.1 christos * Thanks to Rodney Brown <rbrown64 (at) csc.com.au> for his contribution of faster
8 1.1 christos * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
9 1.1 christos * tables for updating the shift register in one step with three exclusive-ors
10 1.1 christos * instead of four steps with four exclusive-ors. This results in about a
11 1.1 christos * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
12 1.1 christos */
13 1.1 christos
14 1.1 christos /* @(#) Id */
15 1.1 christos
16 1.1 christos /*
17 1.1 christos Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
18 1.1 christos protection on the static variables used to control the first-use generation
19 1.1 christos of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should
20 1.1 christos first call get_crc_table() to initialize the tables before allowing more than
21 1.1 christos one thread to use crc32().
22 1.1 christos */
23 1.1 christos
24 1.1 christos #ifdef MAKECRCH
25 1.1 christos # include <stdio.h>
26 1.1 christos # ifndef DYNAMIC_CRC_TABLE
27 1.1 christos # define DYNAMIC_CRC_TABLE
28 1.1 christos # endif /* !DYNAMIC_CRC_TABLE */
29 1.1 christos #endif /* MAKECRCH */
30 1.1 christos
31 1.1 christos #include "zutil.h" /* for STDC and FAR definitions */
32 1.1 christos
33 1.1 christos #define local static
34 1.1 christos
35 1.4 dsl #if defined(__NetBSD__) && defined(_STANDALONE)
36 1.4 dsl #define NOBYFOUR
37 1.4 dsl #define DYNAMIC_CRC_TABLE
38 1.4 dsl #endif
39 1.4 dsl
40 1.1 christos /* Find a four-byte integer type for crc32_little() and crc32_big(). */
41 1.1 christos #ifndef NOBYFOUR
42 1.4 dsl #if defined(__NetBSD__) && defined(_KERNEL)
43 1.3 uwe # define BYFOUR
44 1.3 uwe typedef uint32_t u4;
45 1.3 uwe #else
46 1.1 christos # ifdef STDC /* need ANSI C limits.h to determine sizes */
47 1.1 christos # include <limits.h>
48 1.1 christos # define BYFOUR
49 1.1 christos # if (UINT_MAX == 0xffffffffUL)
50 1.1 christos typedef unsigned int u4;
51 1.1 christos # else
52 1.1 christos # if (ULONG_MAX == 0xffffffffUL)
53 1.1 christos typedef unsigned long u4;
54 1.1 christos # else
55 1.1 christos # if (USHRT_MAX == 0xffffffffUL)
56 1.1 christos typedef unsigned short u4;
57 1.1 christos # else
58 1.1 christos # undef BYFOUR /* can't find a four-byte integer type! */
59 1.1 christos # endif
60 1.1 christos # endif
61 1.1 christos # endif
62 1.1 christos # endif /* STDC */
63 1.4 dsl #endif /* __NetBSD__ && _KERNEL */
64 1.1 christos #endif /* !NOBYFOUR */
65 1.1 christos
66 1.1 christos /* Definitions for doing the crc four data bytes at a time. */
67 1.1 christos #ifdef BYFOUR
68 1.1 christos # define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
69 1.1 christos (((w)&0xff00)<<8)+(((w)&0xff)<<24))
70 1.1 christos local unsigned long crc32_little OF((unsigned long,
71 1.1 christos const unsigned char FAR *, unsigned));
72 1.1 christos local unsigned long crc32_big OF((unsigned long,
73 1.1 christos const unsigned char FAR *, unsigned));
74 1.1 christos # define TBLS 8
75 1.1 christos #else
76 1.1 christos # define TBLS 1
77 1.1 christos #endif /* BYFOUR */
78 1.1 christos
79 1.1 christos /* Local functions for crc concatenation */
80 1.1 christos local unsigned long gf2_matrix_times OF((unsigned long *mat,
81 1.1 christos unsigned long vec));
82 1.1 christos local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
83 1.1 christos
84 1.1 christos #ifdef DYNAMIC_CRC_TABLE
85 1.1 christos
86 1.1 christos local volatile int crc_table_empty = 1;
87 1.1 christos local unsigned long FAR crc_table[TBLS][256];
88 1.1 christos local void make_crc_table OF((void));
89 1.1 christos #ifdef MAKECRCH
90 1.1 christos local void write_table OF((FILE *, const unsigned long FAR *));
91 1.1 christos #endif /* MAKECRCH */
92 1.1 christos /*
93 1.1 christos Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
94 1.1 christos 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.
95 1.1 christos
96 1.1 christos Polynomials over GF(2) are represented in binary, one bit per coefficient,
97 1.1 christos with the lowest powers in the most significant bit. Then adding polynomials
98 1.1 christos is just exclusive-or, and multiplying a polynomial by x is a right shift by
99 1.1 christos one. If we call the above polynomial p, and represent a byte as the
100 1.1 christos polynomial q, also with the lowest power in the most significant bit (so the
101 1.1 christos byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
102 1.1 christos where a mod b means the remainder after dividing a by b.
103 1.1 christos
104 1.1 christos This calculation is done using the shift-register method of multiplying and
105 1.1 christos taking the remainder. The register is initialized to zero, and for each
106 1.1 christos incoming bit, x^32 is added mod p to the register if the bit is a one (where
107 1.1 christos x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
108 1.1 christos x (which is shifting right by one and adding x^32 mod p if the bit shifted
109 1.1 christos out is a one). We start with the highest power (least significant bit) of
110 1.1 christos q and repeat for all eight bits of q.
111 1.1 christos
112 1.1 christos The first table is simply the CRC of all possible eight bit values. This is
113 1.1 christos all the information needed to generate CRCs on data a byte at a time for all
114 1.1 christos combinations of CRC register values and incoming bytes. The remaining tables
115 1.1 christos allow for word-at-a-time CRC calculation for both big-endian and little-
116 1.1 christos endian machines, where a word is four bytes.
117 1.1 christos */
118 1.1 christos local void make_crc_table()
119 1.1 christos {
120 1.1 christos unsigned long c;
121 1.1 christos int n, k;
122 1.1 christos unsigned long poly; /* polynomial exclusive-or pattern */
123 1.1 christos /* terms of polynomial defining this crc (except x^32): */
124 1.1 christos static volatile int first = 1; /* flag to limit concurrent making */
125 1.1 christos static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
126 1.1 christos
127 1.1 christos /* See if another task is already doing this (not thread-safe, but better
128 1.1 christos than nothing -- significantly reduces duration of vulnerability in
129 1.1 christos case the advice about DYNAMIC_CRC_TABLE is ignored) */
130 1.1 christos if (first) {
131 1.1 christos first = 0;
132 1.1 christos
133 1.1 christos /* make exclusive-or pattern from polynomial (0xedb88320UL) */
134 1.1 christos poly = 0UL;
135 1.1 christos for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
136 1.1 christos poly |= 1UL << (31 - p[n]);
137 1.1 christos
138 1.1 christos /* generate a crc for every 8-bit value */
139 1.1 christos for (n = 0; n < 256; n++) {
140 1.1 christos c = (unsigned long)n;
141 1.1 christos for (k = 0; k < 8; k++)
142 1.1 christos c = c & 1 ? poly ^ (c >> 1) : c >> 1;
143 1.1 christos crc_table[0][n] = c;
144 1.1 christos }
145 1.1 christos
146 1.1 christos #ifdef BYFOUR
147 1.1 christos /* generate crc for each value followed by one, two, and three zeros,
148 1.1 christos and then the byte reversal of those as well as the first table */
149 1.1 christos for (n = 0; n < 256; n++) {
150 1.1 christos c = crc_table[0][n];
151 1.1 christos crc_table[4][n] = REV(c);
152 1.1 christos for (k = 1; k < 4; k++) {
153 1.1 christos c = crc_table[0][c & 0xff] ^ (c >> 8);
154 1.1 christos crc_table[k][n] = c;
155 1.1 christos crc_table[k + 4][n] = REV(c);
156 1.1 christos }
157 1.1 christos }
158 1.1 christos #endif /* BYFOUR */
159 1.1 christos
160 1.1 christos crc_table_empty = 0;
161 1.1 christos }
162 1.1 christos else { /* not first */
163 1.1 christos /* wait for the other guy to finish (not efficient, but rare) */
164 1.1 christos while (crc_table_empty)
165 1.1 christos ;
166 1.1 christos }
167 1.1 christos
168 1.1 christos #ifdef MAKECRCH
169 1.1 christos /* write out CRC tables to crc32.h */
170 1.1 christos {
171 1.1 christos FILE *out;
172 1.1 christos
173 1.1 christos out = fopen("crc32.h", "w");
174 1.1 christos if (out == NULL) return;
175 1.1 christos fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
176 1.1 christos fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
177 1.1 christos fprintf(out, "local const unsigned long FAR ");
178 1.1 christos fprintf(out, "crc_table[TBLS][256] =\n{\n {\n");
179 1.1 christos write_table(out, crc_table[0]);
180 1.1 christos # ifdef BYFOUR
181 1.1 christos fprintf(out, "#ifdef BYFOUR\n");
182 1.1 christos for (k = 1; k < 8; k++) {
183 1.1 christos fprintf(out, " },\n {\n");
184 1.1 christos write_table(out, crc_table[k]);
185 1.1 christos }
186 1.1 christos fprintf(out, "#endif\n");
187 1.1 christos # endif /* BYFOUR */
188 1.1 christos fprintf(out, " }\n};\n");
189 1.1 christos fclose(out);
190 1.1 christos }
191 1.1 christos #endif /* MAKECRCH */
192 1.1 christos }
193 1.1 christos
194 1.1 christos #ifdef MAKECRCH
195 1.1 christos local void write_table(out, table)
196 1.1 christos FILE *out;
197 1.1 christos const unsigned long FAR *table;
198 1.1 christos {
199 1.1 christos int n;
200 1.1 christos
201 1.1 christos for (n = 0; n < 256; n++)
202 1.1 christos fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n],
203 1.1 christos n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
204 1.1 christos }
205 1.1 christos #endif /* MAKECRCH */
206 1.1 christos
207 1.1 christos #else /* !DYNAMIC_CRC_TABLE */
208 1.1 christos /* ========================================================================
209 1.1 christos * Tables of CRC-32s of all single-byte values, made by make_crc_table().
210 1.1 christos */
211 1.1 christos #include "crc32.h"
212 1.1 christos #endif /* DYNAMIC_CRC_TABLE */
213 1.1 christos
214 1.1 christos /* =========================================================================
215 1.1 christos * This function can be used by asm versions of crc32()
216 1.1 christos */
217 1.1 christos const unsigned long FAR * ZEXPORT get_crc_table()
218 1.1 christos {
219 1.1 christos #ifdef DYNAMIC_CRC_TABLE
220 1.1 christos if (crc_table_empty)
221 1.1 christos make_crc_table();
222 1.1 christos #endif /* DYNAMIC_CRC_TABLE */
223 1.1 christos return (const unsigned long FAR *)crc_table;
224 1.1 christos }
225 1.1 christos
226 1.1 christos /* ========================================================================= */
227 1.1 christos #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
228 1.1 christos #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
229 1.1 christos
230 1.1 christos /* ========================================================================= */
231 1.1 christos unsigned long ZEXPORT crc32(crc, buf, len)
232 1.1 christos unsigned long crc;
233 1.1 christos const unsigned char FAR *buf;
234 1.1 christos unsigned len;
235 1.1 christos {
236 1.1 christos if (buf == Z_NULL) return 0UL;
237 1.1 christos
238 1.1 christos #ifdef DYNAMIC_CRC_TABLE
239 1.1 christos if (crc_table_empty)
240 1.1 christos make_crc_table();
241 1.1 christos #endif /* DYNAMIC_CRC_TABLE */
242 1.1 christos
243 1.1 christos #ifdef BYFOUR
244 1.2 christos if (sizeof(void *) == sizeof(z_ptrdiff_t)) {
245 1.1 christos u4 endian;
246 1.1 christos
247 1.1 christos endian = 1;
248 1.1 christos if (*((unsigned char *)(&endian)))
249 1.1 christos return crc32_little(crc, buf, len);
250 1.1 christos else
251 1.1 christos return crc32_big(crc, buf, len);
252 1.1 christos }
253 1.1 christos #endif /* BYFOUR */
254 1.1 christos crc = crc ^ 0xffffffffUL;
255 1.1 christos while (len >= 8) {
256 1.1 christos DO8;
257 1.1 christos len -= 8;
258 1.1 christos }
259 1.1 christos if (len) do {
260 1.1 christos DO1;
261 1.1 christos } while (--len);
262 1.1 christos return crc ^ 0xffffffffUL;
263 1.1 christos }
264 1.1 christos
265 1.1 christos #ifdef BYFOUR
266 1.1 christos
267 1.1 christos /* ========================================================================= */
268 1.1 christos #define DOLIT4 c ^= *buf4++; \
269 1.1 christos c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
270 1.1 christos crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
271 1.1 christos #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
272 1.1 christos
273 1.1 christos /* ========================================================================= */
274 1.1 christos local unsigned long crc32_little(crc, buf, len)
275 1.1 christos unsigned long crc;
276 1.1 christos const unsigned char FAR *buf;
277 1.1 christos unsigned len;
278 1.1 christos {
279 1.1 christos register u4 c;
280 1.1 christos register const u4 FAR *buf4;
281 1.1 christos
282 1.1 christos c = (u4)crc;
283 1.1 christos c = ~c;
284 1.2 christos while (len && ((z_ptrdiff_t)buf & 3)) {
285 1.1 christos c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
286 1.1 christos len--;
287 1.1 christos }
288 1.1 christos
289 1.1 christos buf4 = (const u4 FAR *)(const void FAR *)buf;
290 1.1 christos while (len >= 32) {
291 1.1 christos DOLIT32;
292 1.1 christos len -= 32;
293 1.1 christos }
294 1.1 christos while (len >= 4) {
295 1.1 christos DOLIT4;
296 1.1 christos len -= 4;
297 1.1 christos }
298 1.1 christos buf = (const unsigned char FAR *)buf4;
299 1.1 christos
300 1.1 christos if (len) do {
301 1.1 christos c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
302 1.1 christos } while (--len);
303 1.1 christos c = ~c;
304 1.1 christos return (unsigned long)c;
305 1.1 christos }
306 1.1 christos
307 1.1 christos /* ========================================================================= */
308 1.1 christos #define DOBIG4 c ^= *++buf4; \
309 1.1 christos c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
310 1.1 christos crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
311 1.1 christos #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
312 1.1 christos
313 1.1 christos /* ========================================================================= */
314 1.1 christos local unsigned long crc32_big(crc, buf, len)
315 1.1 christos unsigned long crc;
316 1.1 christos const unsigned char FAR *buf;
317 1.1 christos unsigned len;
318 1.1 christos {
319 1.1 christos register u4 c;
320 1.1 christos register const u4 FAR *buf4;
321 1.1 christos
322 1.1 christos c = REV((u4)crc);
323 1.1 christos c = ~c;
324 1.2 christos while (len && ((z_ptrdiff_t)buf & 3)) {
325 1.1 christos c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
326 1.1 christos len--;
327 1.1 christos }
328 1.1 christos
329 1.1 christos buf4 = (const u4 FAR *)(const void FAR *)buf;
330 1.1 christos buf4--;
331 1.1 christos while (len >= 32) {
332 1.1 christos DOBIG32;
333 1.1 christos len -= 32;
334 1.1 christos }
335 1.1 christos while (len >= 4) {
336 1.1 christos DOBIG4;
337 1.1 christos len -= 4;
338 1.1 christos }
339 1.1 christos buf4++;
340 1.1 christos buf = (const unsigned char FAR *)buf4;
341 1.1 christos
342 1.1 christos if (len) do {
343 1.1 christos c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
344 1.1 christos } while (--len);
345 1.1 christos c = ~c;
346 1.1 christos return (unsigned long)(REV(c));
347 1.1 christos }
348 1.1 christos
349 1.1 christos #endif /* BYFOUR */
350 1.1 christos
351 1.1 christos #define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */
352 1.1 christos
353 1.1 christos /* ========================================================================= */
354 1.1 christos local unsigned long gf2_matrix_times(mat, vec)
355 1.1 christos unsigned long *mat;
356 1.1 christos unsigned long vec;
357 1.1 christos {
358 1.1 christos unsigned long sum;
359 1.1 christos
360 1.1 christos sum = 0;
361 1.1 christos while (vec) {
362 1.1 christos if (vec & 1)
363 1.1 christos sum ^= *mat;
364 1.1 christos vec >>= 1;
365 1.1 christos mat++;
366 1.1 christos }
367 1.1 christos return sum;
368 1.1 christos }
369 1.1 christos
370 1.1 christos /* ========================================================================= */
371 1.1 christos local void gf2_matrix_square(square, mat)
372 1.1 christos unsigned long *square;
373 1.1 christos unsigned long *mat;
374 1.1 christos {
375 1.1 christos int n;
376 1.1 christos
377 1.1 christos for (n = 0; n < GF2_DIM; n++)
378 1.1 christos square[n] = gf2_matrix_times(mat, mat[n]);
379 1.1 christos }
380 1.1 christos
381 1.1 christos /* ========================================================================= */
382 1.1 christos uLong ZEXPORT crc32_combine(crc1, crc2, len2)
383 1.1 christos uLong crc1;
384 1.1 christos uLong crc2;
385 1.1 christos z_off_t len2;
386 1.1 christos {
387 1.1 christos int n;
388 1.1 christos unsigned long row;
389 1.1 christos unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */
390 1.1 christos unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */
391 1.1 christos
392 1.1 christos /* degenerate case */
393 1.1 christos if (len2 == 0)
394 1.1 christos return crc1;
395 1.1 christos
396 1.1 christos /* put operator for one zero bit in odd */
397 1.1 christos odd[0] = 0xedb88320L; /* CRC-32 polynomial */
398 1.1 christos row = 1;
399 1.1 christos for (n = 1; n < GF2_DIM; n++) {
400 1.1 christos odd[n] = row;
401 1.1 christos row <<= 1;
402 1.1 christos }
403 1.1 christos
404 1.1 christos /* put operator for two zero bits in even */
405 1.1 christos gf2_matrix_square(even, odd);
406 1.1 christos
407 1.1 christos /* put operator for four zero bits in odd */
408 1.1 christos gf2_matrix_square(odd, even);
409 1.1 christos
410 1.1 christos /* apply len2 zeros to crc1 (first square will put the operator for one
411 1.1 christos zero byte, eight zero bits, in even) */
412 1.1 christos do {
413 1.1 christos /* apply zeros operator for this bit of len2 */
414 1.1 christos gf2_matrix_square(even, odd);
415 1.1 christos if (len2 & 1)
416 1.1 christos crc1 = gf2_matrix_times(even, crc1);
417 1.1 christos len2 >>= 1;
418 1.1 christos
419 1.1 christos /* if no more bits set, then done */
420 1.1 christos if (len2 == 0)
421 1.1 christos break;
422 1.1 christos
423 1.1 christos /* another iteration of the loop with odd and even swapped */
424 1.1 christos gf2_matrix_square(odd, even);
425 1.1 christos if (len2 & 1)
426 1.1 christos crc1 = gf2_matrix_times(odd, crc1);
427 1.1 christos len2 >>= 1;
428 1.1 christos
429 1.1 christos /* if no more bits set, then done */
430 1.1 christos } while (len2 != 0);
431 1.1 christos
432 1.1 christos /* return combined crc */
433 1.1 christos crc1 ^= crc2;
434 1.1 christos return crc1;
435 1.1 christos }
436