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