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