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 */
50local unsigned long gf2_matrix_times OF((unsigned long *mat,
51                                         unsigned long vec));
52local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
53local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2));
54
55
56#ifdef DYNAMIC_CRC_TABLE
57
58local volatile int crc_table_empty = 1;
59local z_crc_t FAR crc_table[TBLS][256];
60local 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*/
90local 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
167local 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 */
190const 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/* ========================================================================= */
204unsigned 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/* ========================================================================= */
247local 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/* ========================================================================= */
287local 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/* ========================================================================= */
327local 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/* ========================================================================= */
344local 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/* ========================================================================= */
355local 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/* ========================================================================= */
411uLong 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
419uLong 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