crc32.c 13.7 KB
Newer Older
M
Mark Adler 已提交
1
/* crc32.c -- compute the CRC-32 of a data stream
M
Mark Adler 已提交
2
 * Copyright (C) 1995-2006 Mark Adler
M
Mark Adler 已提交
3 4 5 6 7
 * For conditions of distribution and use, see copyright notice in zlib.h
 *
 * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
 * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
 * tables for updating the shift register in one step with three exclusive-ors
M
Mark Adler 已提交
8 9
 * instead of four steps with four exclusive-ors.  This results in about a
 * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
M
Mark Adler 已提交
10 11
 */

M
Mark Adler 已提交
12
/* @(#) $Id$ */
M
Mark Adler 已提交
13

M
Mark Adler 已提交
14
/*
M
Mark Adler 已提交
15 16 17 18 19
  Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
  protection on the static variables used to control the first-use generation
  of the crc tables.  Therefore, if you #define DYNAMIC_CRC_TABLE, you should
  first call get_crc_table() to initialize the tables before allowing more than
  one thread to use crc32().
M
Mark Adler 已提交
20 21
 */

M
Mark Adler 已提交
22 23 24 25 26 27 28
#ifdef MAKECRCH
#  include <stdio.h>
#  ifndef DYNAMIC_CRC_TABLE
#    define DYNAMIC_CRC_TABLE
#  endif /* !DYNAMIC_CRC_TABLE */
#endif /* MAKECRCH */

M
Mark Adler 已提交
29
#include "zutil.h"      /* for STDC and FAR definitions */
M
Mark Adler 已提交
30

M
Mark Adler 已提交
31
#define local static
M
Mark Adler 已提交
32

M
Mark Adler 已提交
33 34
/* Find a four-byte integer type for crc32_little() and crc32_big(). */
#ifndef NOBYFOUR
M
Mark Adler 已提交
35
#  ifdef STDC           /* need ANSI C limits.h to determine sizes */
M
Mark Adler 已提交
36 37
#    include <limits.h>
#    define BYFOUR
M
Mark Adler 已提交
38
#    if (UINT_MAX == 0xffffffffUL)
M
Mark Adler 已提交
39 40
       typedef unsigned int u4;
#    else
M
Mark Adler 已提交
41 42 43 44 45 46 47 48 49
#      if (ULONG_MAX == 0xffffffffUL)
         typedef unsigned long u4;
#      else
#        if (USHRT_MAX == 0xffffffffUL)
           typedef unsigned short u4;
#        else
#          undef BYFOUR     /* can't find a four-byte integer type! */
#        endif
#      endif
M
Mark Adler 已提交
50
#    endif
M
Mark Adler 已提交
51
#  endif /* STDC */
M
Mark Adler 已提交
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
#endif /* !NOBYFOUR */

/* Definitions for doing the crc four data bytes at a time. */
#ifdef BYFOUR
#  define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
                (((w)&0xff00)<<8)+(((w)&0xff)<<24))
   local unsigned long crc32_little OF((unsigned long,
                        const unsigned char FAR *, unsigned));
   local unsigned long crc32_big OF((unsigned long,
                        const unsigned char FAR *, unsigned));
#  define TBLS 8
#else
#  define TBLS 1
#endif /* BYFOUR */

M
Mark Adler 已提交
67 68 69 70
/* Local functions for crc concatenation */
local unsigned long gf2_matrix_times OF((unsigned long *mat,
                                         unsigned long vec));
local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
M
Mark Adler 已提交
71 72 73 74 75 76
#ifdef _LARGEFILE64_SOURCE
   local uLong crc32_combine_(uLong crc1, uLong crc2, off64_t len2);
#else
   local uLong crc32_combine_(uLong crc1, uLong crc2, z_off_t len2);
#endif

M
Mark Adler 已提交
77

M
Mark Adler 已提交
78
#ifdef DYNAMIC_CRC_TABLE
M
Mark Adler 已提交
79

M
Mark Adler 已提交
80
local volatile int crc_table_empty = 1;
M
Mark Adler 已提交
81
local unsigned long FAR crc_table[TBLS][256];
M
Mark Adler 已提交
82
local void make_crc_table OF((void));
M
Mark Adler 已提交
83 84 85
#ifdef MAKECRCH
   local void write_table OF((FILE *, const unsigned long FAR *));
#endif /* MAKECRCH */
M
Mark Adler 已提交
86
/*
M
Mark Adler 已提交
87
  Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
M
Mark Adler 已提交
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.
M
Mark Adler 已提交
89

M
Mark Adler 已提交
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
  Polynomials over GF(2) are represented in binary, one bit per coefficient,
  with the lowest powers in the most significant bit.  Then adding polynomials
  is just exclusive-or, and multiplying a polynomial by x is a right shift by
  one.  If we call the above polynomial p, and represent a byte as the
  polynomial q, also with the lowest power in the most significant bit (so the
  byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
  where a mod b means the remainder after dividing a by b.

  This calculation is done using the shift-register method of multiplying and
  taking the remainder.  The register is initialized to zero, and for each
  incoming bit, x^32 is added mod p to the register if the bit is a one (where
  x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
  x (which is shifting right by one and adding x^32 mod p if the bit shifted
  out is a one).  We start with the highest power (least significant bit) of
  q and repeat for all eight bits of q.

M
Mark Adler 已提交
106 107 108 109 110
  The first table is simply the CRC of all possible eight bit values.  This is
  all the information needed to generate CRCs on data a byte at a time for all
  combinations of CRC register values and incoming bytes.  The remaining tables
  allow for word-at-a-time CRC calculation for both big-endian and little-
  endian machines, where a word is four bytes.
M
Mark Adler 已提交
111
*/
M
Mark Adler 已提交
112
local void make_crc_table()
M
Mark Adler 已提交
113
{
M
Mark Adler 已提交
114 115
    unsigned long c;
    int n, k;
M
Mark Adler 已提交
116
    unsigned long poly;                 /* polynomial exclusive-or pattern */
M
Mark Adler 已提交
117
    /* terms of polynomial defining this crc (except x^32): */
M
Mark Adler 已提交
118
    static volatile int first = 1;      /* flag to limit concurrent making */
M
Mark Adler 已提交
119 120
    static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};

M
Mark Adler 已提交
121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
    /* See if another task is already doing this (not thread-safe, but better
       than nothing -- significantly reduces duration of vulnerability in
       case the advice about DYNAMIC_CRC_TABLE is ignored) */
    if (first) {
        first = 0;

        /* make exclusive-or pattern from polynomial (0xedb88320UL) */
        poly = 0UL;
        for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
            poly |= 1UL << (31 - p[n]);

        /* generate a crc for every 8-bit value */
        for (n = 0; n < 256; n++) {
            c = (unsigned long)n;
            for (k = 0; k < 8; k++)
                c = c & 1 ? poly ^ (c >> 1) : c >> 1;
            crc_table[0][n] = c;
        }
M
Mark Adler 已提交
139 140

#ifdef BYFOUR
M
Mark Adler 已提交
141 142 143 144 145 146 147 148 149 150 151
        /* generate crc for each value followed by one, two, and three zeros,
           and then the byte reversal of those as well as the first table */
        for (n = 0; n < 256; n++) {
            c = crc_table[0][n];
            crc_table[4][n] = REV(c);
            for (k = 1; k < 4; k++) {
                c = crc_table[0][c & 0xff] ^ (c >> 8);
                crc_table[k][n] = c;
                crc_table[k + 4][n] = REV(c);
            }
        }
M
Mark Adler 已提交
152 153
#endif /* BYFOUR */

M
Mark Adler 已提交
154 155 156 157 158 159 160
        crc_table_empty = 0;
    }
    else {      /* not first */
        /* wait for the other guy to finish (not efficient, but rare) */
        while (crc_table_empty)
            ;
    }
M
Mark Adler 已提交
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185

#ifdef MAKECRCH
    /* write out CRC tables to crc32.h */
    {
        FILE *out;

        out = fopen("crc32.h", "w");
        if (out == NULL) return;
        fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
        fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
        fprintf(out, "local const unsigned long FAR ");
        fprintf(out, "crc_table[TBLS][256] =\n{\n  {\n");
        write_table(out, crc_table[0]);
#  ifdef BYFOUR
        fprintf(out, "#ifdef BYFOUR\n");
        for (k = 1; k < 8; k++) {
            fprintf(out, "  },\n  {\n");
            write_table(out, crc_table[k]);
        }
        fprintf(out, "#endif\n");
#  endif /* BYFOUR */
        fprintf(out, "  }\n};\n");
        fclose(out);
    }
#endif /* MAKECRCH */
M
Mark Adler 已提交
186
}
M
Mark Adler 已提交
187 188 189 190 191 192 193 194 195 196 197 198 199 200 201

#ifdef MAKECRCH
local void write_table(out, table)
    FILE *out;
    const unsigned long FAR *table;
{
    int n;

    for (n = 0; n < 256; n++)
        fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ", table[n],
                n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
}
#endif /* MAKECRCH */

#else /* !DYNAMIC_CRC_TABLE */
M
Mark Adler 已提交
202
/* ========================================================================
M
Mark Adler 已提交
203
 * Tables of CRC-32s of all single-byte values, made by make_crc_table().
M
Mark Adler 已提交
204
 */
M
Mark Adler 已提交
205 206
#include "crc32.h"
#endif /* DYNAMIC_CRC_TABLE */
M
Mark Adler 已提交
207

M
Mark Adler 已提交
208 209 210
/* =========================================================================
 * This function can be used by asm versions of crc32()
 */
M
Mark Adler 已提交
211
const unsigned long FAR * ZEXPORT get_crc_table()
M
Mark Adler 已提交
212 213
{
#ifdef DYNAMIC_CRC_TABLE
M
Mark Adler 已提交
214 215
    if (crc_table_empty)
        make_crc_table();
M
Mark Adler 已提交
216
#endif /* DYNAMIC_CRC_TABLE */
M
Mark Adler 已提交
217
    return (const unsigned long FAR *)crc_table;
M
Mark Adler 已提交
218 219 220
}

/* ========================================================================= */
M
Mark Adler 已提交
221 222
#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
M
Mark Adler 已提交
223 224

/* ========================================================================= */
M
Mark Adler 已提交
225 226 227 228
unsigned long ZEXPORT crc32(crc, buf, len)
    unsigned long crc;
    const unsigned char FAR *buf;
    unsigned len;
M
Mark Adler 已提交
229
{
M
Mark Adler 已提交
230 231
    if (buf == Z_NULL) return 0UL;

M
Mark Adler 已提交
232 233
#ifdef DYNAMIC_CRC_TABLE
    if (crc_table_empty)
M
Mark Adler 已提交
234 235 236 237
        make_crc_table();
#endif /* DYNAMIC_CRC_TABLE */

#ifdef BYFOUR
M
Mark Adler 已提交
238
    if (sizeof(void *) == sizeof(ptrdiff_t)) {
M
Mark Adler 已提交
239 240 241 242 243 244 245 246
        u4 endian;

        endian = 1;
        if (*((unsigned char *)(&endian)))
            return crc32_little(crc, buf, len);
        else
            return crc32_big(crc, buf, len);
    }
M
Mark Adler 已提交
247
#endif /* BYFOUR */
M
Mark Adler 已提交
248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277
    crc = crc ^ 0xffffffffUL;
    while (len >= 8) {
        DO8;
        len -= 8;
    }
    if (len) do {
        DO1;
    } while (--len);
    return crc ^ 0xffffffffUL;
}

#ifdef BYFOUR

/* ========================================================================= */
#define DOLIT4 c ^= *buf4++; \
        c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
            crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4

/* ========================================================================= */
local unsigned long crc32_little(crc, buf, len)
    unsigned long crc;
    const unsigned char FAR *buf;
    unsigned len;
{
    register u4 c;
    register const u4 FAR *buf4;

    c = (u4)crc;
    c = ~c;
M
Mark Adler 已提交
278
    while (len && ((ptrdiff_t)buf & 3)) {
M
Mark Adler 已提交
279 280 281 282
        c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
        len--;
    }

M
Mark Adler 已提交
283
    buf4 = (const u4 FAR *)(const void FAR *)buf;
M
Mark Adler 已提交
284 285 286 287 288 289 290
    while (len >= 32) {
        DOLIT32;
        len -= 32;
    }
    while (len >= 4) {
        DOLIT4;
        len -= 4;
M
Mark Adler 已提交
291
    }
M
Mark Adler 已提交
292 293
    buf = (const unsigned char FAR *)buf4;

M
Mark Adler 已提交
294
    if (len) do {
M
Mark Adler 已提交
295
        c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
M
Mark Adler 已提交
296
    } while (--len);
M
Mark Adler 已提交
297 298
    c = ~c;
    return (unsigned long)c;
M
Mark Adler 已提交
299
}
M
Mark Adler 已提交
300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317

/* ========================================================================= */
#define DOBIG4 c ^= *++buf4; \
        c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
            crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4

/* ========================================================================= */
local unsigned long crc32_big(crc, buf, len)
    unsigned long crc;
    const unsigned char FAR *buf;
    unsigned len;
{
    register u4 c;
    register const u4 FAR *buf4;

    c = REV((u4)crc);
    c = ~c;
M
Mark Adler 已提交
318
    while (len && ((ptrdiff_t)buf & 3)) {
M
Mark Adler 已提交
319 320 321 322
        c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
        len--;
    }

M
Mark Adler 已提交
323
    buf4 = (const u4 FAR *)(const void FAR *)buf;
M
Mark Adler 已提交
324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343
    buf4--;
    while (len >= 32) {
        DOBIG32;
        len -= 32;
    }
    while (len >= 4) {
        DOBIG4;
        len -= 4;
    }
    buf4++;
    buf = (const unsigned char FAR *)buf4;

    if (len) do {
        c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
    } while (--len);
    c = ~c;
    return (unsigned long)(REV(c));
}

#endif /* BYFOUR */
M
Mark Adler 已提交
344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375

#define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */

/* ========================================================================= */
local unsigned long gf2_matrix_times(mat, vec)
    unsigned long *mat;
    unsigned long vec;
{
    unsigned long sum;

    sum = 0;
    while (vec) {
        if (vec & 1)
            sum ^= *mat;
        vec >>= 1;
        mat++;
    }
    return sum;
}

/* ========================================================================= */
local void gf2_matrix_square(square, mat)
    unsigned long *square;
    unsigned long *mat;
{
    int n;

    for (n = 0; n < GF2_DIM; n++)
        square[n] = gf2_matrix_times(mat, mat[n]);
}

/* ========================================================================= */
M
Mark Adler 已提交
376
local uLong crc32_combine_(crc1, crc2, len2)
M
Mark Adler 已提交
377 378
    uLong crc1;
    uLong crc2;
M
Mark Adler 已提交
379 380 381
#ifdef _LARGEFILE64_SOURCE
    off64_t len2;
#else
M
Mark Adler 已提交
382
    z_off_t len2;
M
Mark Adler 已提交
383
#endif
M
Mark Adler 已提交
384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433
{
    int n;
    unsigned long row;
    unsigned long even[GF2_DIM];    /* even-power-of-two zeros operator */
    unsigned long odd[GF2_DIM];     /* odd-power-of-two zeros operator */

    /* degenerate case */
    if (len2 == 0)
        return crc1;

    /* put operator for one zero bit in odd */
    odd[0] = 0xedb88320L;           /* CRC-32 polynomial */
    row = 1;
    for (n = 1; n < GF2_DIM; n++) {
        odd[n] = row;
        row <<= 1;
    }

    /* put operator for two zero bits in even */
    gf2_matrix_square(even, odd);

    /* put operator for four zero bits in odd */
    gf2_matrix_square(odd, even);

    /* apply len2 zeros to crc1 (first square will put the operator for one
       zero byte, eight zero bits, in even) */
    do {
        /* apply zeros operator for this bit of len2 */
        gf2_matrix_square(even, odd);
        if (len2 & 1)
            crc1 = gf2_matrix_times(even, crc1);
        len2 >>= 1;

        /* if no more bits set, then done */
        if (len2 == 0)
            break;

        /* another iteration of the loop with odd and even swapped */
        gf2_matrix_square(odd, even);
        if (len2 & 1)
            crc1 = gf2_matrix_times(odd, crc1);
        len2 >>= 1;

        /* if no more bits set, then done */
    } while (len2 != 0);

    /* return combined crc */
    crc1 ^= crc2;
    return crc1;
}
M
Mark Adler 已提交
434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460

/* ========================================================================= */
uLong ZEXPORT crc32_combine(crc1, crc2, len2)
    uLong crc1;
    uLong crc2;
    z_off_t len2;
{
    return crc32_combine_(crc1, crc2, len2);
}

#ifdef _LARGEFILE64_SOURCE
uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
    uLong crc1;
    uLong crc2;
    off64_t len2;
{
    return crc32_combine_(crc1, crc2, len2);
}
#else
uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
    uLong crc1;
    uLong crc2;
    z_off_t len2;
{
    return crc32_combine_(crc1, crc2, len2);
}
#endif