common/dist/zlib/crc32.c

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