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