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