source: rtems/cpukit/zlib/crc32.c @ 89bace6

4.104.11
Last change on this file since 89bace6 was 959f7df2, checked in by Ralf Corsepius <ralf.corsepius@…>, on Oct 28, 2005 at 7:22:42 AM

Import of zlib-1.2.2.2.tar.gz

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