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