GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libz/crc32.c Lines: 0 73 0.0 %
Date: 2017-11-13 Branches: 0 46 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: crc32.c,v 1.8 2005/07/20 15:56:41 millert Exp $	*/
2
/* crc32.c -- compute the CRC-32 of a data stream
3
 * Copyright (C) 1995-2005 Mark Adler
4
 * For conditions of distribution and use, see copyright notice in zlib.h
5
 *
6
 * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
7
 * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
8
 * tables for updating the shift register in one step with three exclusive-ors
9
 * instead of four steps with four exclusive-ors.  This results in about a
10
 * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
11
 */
12
13
/*
14
  Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
15
  protection on the static variables used to control the first-use generation
16
  of the crc tables.  Therefore, if you #define DYNAMIC_CRC_TABLE, you should
17
  first call get_crc_table() to initialize the tables before allowing more than
18
  one thread to use crc32().
19
 */
20
21
#ifdef MAKECRCH
22
#  include <stdio.h>
23
#  ifndef DYNAMIC_CRC_TABLE
24
#    define DYNAMIC_CRC_TABLE
25
#  endif /* !DYNAMIC_CRC_TABLE */
26
#endif /* MAKECRCH */
27
28
#include "zutil.h"      /* for STDC and FAR definitions */
29
30
#define local static
31
32
/* Find a four-byte integer type for crc32_little() and crc32_big(). */
33
#ifndef NOBYFOUR
34
#  ifdef STDC           /* need ANSI C limits.h to determine sizes */
35
#    include <limits.h>
36
#    define BYFOUR
37
#    if (UINT_MAX == 0xffffffffUL)
38
       typedef unsigned int u4;
39
#    else
40
#      if (ULONG_MAX == 0xffffffffUL)
41
         typedef unsigned long u4;
42
#      else
43
#        if (USHRT_MAX == 0xffffffffUL)
44
           typedef unsigned short u4;
45
#        else
46
#          undef BYFOUR     /* can't find a four-byte integer type! */
47
#        endif
48
#      endif
49
#    endif
50
#  endif /* STDC */
51
#endif /* !NOBYFOUR */
52
53
/* Definitions for doing the crc four data bytes at a time. */
54
#ifdef BYFOUR
55
#  define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
56
                (((w)&0xff00)<<8)+(((w)&0xff)<<24))
57
   local unsigned long crc32_little OF((unsigned long,
58
                        const unsigned char FAR *, unsigned));
59
   local unsigned long crc32_big OF((unsigned long,
60
                        const unsigned char FAR *, unsigned));
61
#  define TBLS 8
62
#else
63
#  define TBLS 1
64
#endif /* BYFOUR */
65
66
/* Local functions for crc concatenation */
67
local unsigned long gf2_matrix_times OF((unsigned long *mat,
68
                                         unsigned long vec));
69
local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
70
71
#ifdef DYNAMIC_CRC_TABLE
72
73
local volatile int crc_table_empty = 1;
74
local unsigned long FAR crc_table[TBLS][256];
75
local void make_crc_table OF((void));
76
#ifdef MAKECRCH
77
   local void write_table OF((FILE *, const unsigned long FAR *));
78
#endif /* MAKECRCH */
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
*/
105
local 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
182
local 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
 */
204
const 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
/* ========================================================================= */
218
unsigned 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
/* ========================================================================= */
261
local 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 *)(const void 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
/* ========================================================================= */
301
local 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 *)(const void 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
/* ========================================================================= */
341
local 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
/* ========================================================================= */
358
local 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
/* ========================================================================= */
369
uLong 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
}