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