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