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