← Back to branch summary

~xnox/ubuntu/quantal/mdadm/merge

« back to all changes in this revision

Viewing changes to crc32.c

  • Committer: Dmitrijs Ledkovs
  • Author(s): Surbhi Palande
  • Date: 2010-09-30 17:46:19 UTC
  • mfrom: (1.1.25 sid)
  • Revision ID: dmitrijs.ledkovs@canonical.com-20100930174619-cqsokylnluraiyr8
Tags: 3.1.4-1+8efb9d1ubuntu1
https://launchpad.net/bugs/603582
* Merge from debian unstable. (LP: #603582) 
* Remaining changes
  - Assemble.c, config.c: upgraded to the mdadm-3.1.4 version of these files
    from Debian.
  - debian/control: we need udev and util-linux in the right version. We
    also remove the build dependency from quilt and docbook-to-man as both
    are not used in Ubuntus mdadm.
  - debian/initramfs/hook: kept the Ubuntus version for handling the absence
    of active raid arrays in <initramfs>/etc/mdadm/mdadm.conf
  - debian/initramfs/script.local-top.DEBIAN, debian/mdadm-startall,
    debian/mdadm.raid.DEBIAN: removed. udev does its job now instead.
  - debian/mdadm-startall.sgml, debian/mdadm-startall.8: documentation of
    unused startall script
  - debian/mdadm.config, debian/mdadm.postinst - let udev do the handling
    instead. Resolved merge conflict by keeping Ubuntu's version.
  - debian/rules: kept debian's switch to using dh_lintian
  - debian/mdadm.links, debian/mdadm.manpages: dropped owing to the fact
    that these are not used in Ubuntu. Also dropped the build-dep on docbook
    to man)
  - debian/mdadm.postinst, debian/mdadm.config, initramfs/init-premount:
    boot-degraded enablement; maintain udev starting of RAID devices;
    init-premount hook script for the initramfs, to provide information at
    boot
  - debian/mkconf.in is the older mkconf. Kept the Ubuntus version.
  - debian/rules: Kept Ubuntus version for installing apport hooks, not
    installing un-used startall script and for adding a udev rule
    corresponding to mdadm.
  - debian/install-rc, check.d/_numbers, check.d/root_on_raid: Ubuntu partman
    installer changes
  - debian/presubj: Dropped this unused bug reporting file. Instead use
    source_mdadm.py act as an apport hook for bug handling.
  - rename debian/mdadm.vol_id.udev to debian/mdadm.mdadm-blkid.udev so that
    the rules file ends up with a more reasonable name

Show diffs side-by-side

added added

removed removed

Lines of Context:
crc32.c
 
1
/* crc32.c -- compute the CRC-32 of a data stream
 
2
 * Copyright (C) 1995-2003 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 about a factor
 
9
 * 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
#define STDC
 
31
#define FAR
 
32
#define Z_NULL ((void*)0)
 
33
#define OF(X) X
 
34
#define ZEXPORT
 
35
typedef long ptrdiff_t;
 
36
#define NOBYFOUR
 
37
 
 
38
#define local static
 
39
 
 
40
/* Find a four-byte integer type for crc32_little() and crc32_big(). */
 
41
#ifndef NOBYFOUR
 
42
#  ifdef STDC           /* need ANSI C limits.h to determine sizes */
 
43
#    include <limits.h>
 
44
#    define BYFOUR
 
45
#    if (UINT_MAX == 0xffffffffUL)
 
46
       typedef unsigned int u4;
 
47
#    else
 
48
#      if (ULONG_MAX == 0xffffffffUL)
 
49
         typedef unsigned long u4;
 
50
#      else
 
51
#        if (USHRT_MAX == 0xffffffffUL)
 
52
           typedef unsigned short u4;
 
53
#        else
 
54
#          undef BYFOUR     /* can't find a four-byte integer type! */
 
55
#        endif
 
56
#      endif
 
57
#    endif
 
58
#  endif /* STDC */
 
59
#endif /* !NOBYFOUR */
 
60
 
 
61
/* Definitions for doing the crc four data bytes at a time. */
 
62
#ifdef BYFOUR
 
63
#  define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
 
64
                (((w)&0xff00)<<8)+(((w)&0xff)<<24))
 
65
   local unsigned long crc32_little OF((unsigned long,
 
66
                        const unsigned char FAR *, unsigned));
 
67
   local unsigned long crc32_big OF((unsigned long,
 
68
                        const unsigned char FAR *, unsigned));
 
69
#  define TBLS 8
 
70
#else
 
71
#  define TBLS 1
 
72
#endif /* BYFOUR */
 
73
 
 
74
#ifdef DYNAMIC_CRC_TABLE
 
75
 
 
76
local volatile int crc_table_empty = 1;
 
77
local unsigned long FAR crc_table[TBLS][256];
 
78
local void make_crc_table OF((void));
 
79
#ifdef MAKECRCH
 
80
   local void write_table OF((FILE *, const unsigned long FAR *));
 
81
#endif /* MAKECRCH */
 
82
 
 
83
/*
 
84
  Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
 
85
  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.
 
86
 
 
87
  Polynomials over GF(2) are represented in binary, one bit per coefficient,
 
88
  with the lowest powers in the most significant bit.  Then adding polynomials
 
89
  is just exclusive-or, and multiplying a polynomial by x is a right shift by
 
90
  one.  If we call the above polynomial p, and represent a byte as the
 
91
  polynomial q, also with the lowest power in the most significant bit (so the
 
92
  byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
 
93
  where a mod b means the remainder after dividing a by b.
 
94
 
 
95
  This calculation is done using the shift-register method of multiplying and
 
96
  taking the remainder.  The register is initialized to zero, and for each
 
97
  incoming bit, x^32 is added mod p to the register if the bit is a one (where
 
98
  x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
 
99
  x (which is shifting right by one and adding x^32 mod p if the bit shifted
 
100
  out is a one).  We start with the highest power (least significant bit) of
 
101
  q and repeat for all eight bits of q.
 
102
 
 
103
  The first table is simply the CRC of all possible eight bit values.  This is
 
104
  all the information needed to generate CRCs on data a byte at a time for all
 
105
  combinations of CRC register values and incoming bytes.  The remaining tables
 
106
  allow for word-at-a-time CRC calculation for both big-endian and little-
 
107
  endian machines, where a word is four bytes.
 
108
*/
 
109
local void make_crc_table()
 
110
{
 
111
    unsigned long c;
 
112
    int n, k;
 
113
    unsigned long poly;                 /* polynomial exclusive-or pattern */
 
114
    /* terms of polynomial defining this crc (except x^32): */
 
115
    static volatile int first = 1;      /* flag to limit concurrent making */
 
116
    static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
 
117
 
 
118
    /* See if another task is already doing this (not thread-safe, but better
 
119
       than nothing -- significantly reduces duration of vulnerability in
 
120
       case the advice about DYNAMIC_CRC_TABLE is ignored) */
 
121
    if (first) {
 
122
        first = 0;
 
123
 
 
124
        /* make exclusive-or pattern from polynomial (0xedb88320UL) */
 
125
        poly = 0UL;
 
126
        for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
 
127
            poly |= 1UL << (31 - p[n]);
 
128
 
 
129
        /* generate a crc for every 8-bit value */
 
130
        for (n = 0; n < 256; n++) {
 
131
            c = (unsigned long)n;
 
132
            for (k = 0; k < 8; k++)
 
133
                c = c & 1 ? poly ^ (c >> 1) : c >> 1;
 
134
            crc_table[0][n] = c;
 
135
        }
 
136
 
 
137
#ifdef BYFOUR
 
138
        /* generate crc for each value followed by one, two, and three zeros,
 
139
           and then the byte reversal of those as well as the first table */
 
140
        for (n = 0; n < 256; n++) {
 
141
            c = crc_table[0][n];
 
142
            crc_table[4][n] = REV(c);
 
143
            for (k = 1; k < 4; k++) {
 
144
                c = crc_table[0][c & 0xff] ^ (c >> 8);
 
145
                crc_table[k][n] = c;
 
146
                crc_table[k + 4][n] = REV(c);
 
147
            }
 
148
        }
 
149
#endif /* BYFOUR */
 
150
 
 
151
        crc_table_empty = 0;
 
152
    }
 
153
    else {      /* not first */
 
154
        /* wait for the other guy to finish (not efficient, but rare) */
 
155
        while (crc_table_empty)
 
156
            ;
 
157
    }
 
158
 
 
159
#ifdef MAKECRCH
 
160
    /* write out CRC tables to crc32.h */
 
161
    {
 
162
        FILE *out;
 
163
 
 
164
        out = fopen("crc32.h", "w");
 
165
        if (out == NULL) return;
 
166
        fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
 
167
        fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
 
168
        fprintf(out, "local const unsigned long FAR ");
 
169
        fprintf(out, "crc_table[TBLS][256] =\n{\n  {\n");
 
170
        write_table(out, crc_table[0]);
 
171
#  ifdef BYFOUR
 
172
        fprintf(out, "#ifdef BYFOUR\n");
 
173
        for (k = 1; k < 8; k++) {
 
174
            fprintf(out, "  },\n  {\n");
 
175
            write_table(out, crc_table[k]);
 
176
        }
 
177
        fprintf(out, "#endif\n");
 
178
#  endif /* BYFOUR */
 
179
        fprintf(out, "  }\n};\n");
 
180
        fclose(out);
 
181
    }
 
182
#endif /* MAKECRCH */
 
183
}
 
184
 
 
185
#ifdef MAKECRCH
 
186
local void write_table(out, table)
 
187
    FILE *out;
 
188
    const unsigned long FAR *table;
 
189
{
 
190
    int n;
 
191
 
 
192
    for (n = 0; n < 256; n++)
 
193
        fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ", table[n],
 
194
                n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
 
195
}
 
196
#endif /* MAKECRCH */
 
197
 
 
198
#else /* !DYNAMIC_CRC_TABLE */
 
199
/* ========================================================================
 
200
 * Tables of CRC-32s of all single-byte values, made by make_crc_table().
 
201
 */
 
202
#include "crc32.h"
 
203
#endif /* DYNAMIC_CRC_TABLE */
 
204
 
 
205
/* =========================================================================
 
206
 * This function can be used by asm versions of crc32()
 
207
 */
 
208
const unsigned long FAR * ZEXPORT get_crc_table(void)
 
209
{
 
210
#ifdef DYNAMIC_CRC_TABLE
 
211
    if (crc_table_empty)
 
212
        make_crc_table();
 
213
#endif /* DYNAMIC_CRC_TABLE */
 
214
    return (const unsigned long FAR *)crc_table;
 
215
}
 
216
 
 
217
/* ========================================================================= */
 
218
#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
 
219
#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
 
220
 
 
221
/* ========================================================================= */
 
222
unsigned long ZEXPORT crc32(
 
223
        unsigned long crc,
 
224
        const unsigned char FAR *buf,
 
225
        unsigned len)
 
226
{
 
227
    if (buf == Z_NULL) return 0UL;
 
228
 
 
229
#ifdef DYNAMIC_CRC_TABLE
 
230
    if (crc_table_empty)
 
231
        make_crc_table();
 
232
#endif /* DYNAMIC_CRC_TABLE */
 
233
 
 
234
#ifdef BYFOUR
 
235
    if (sizeof(void *) == sizeof(ptrdiff_t)) {
 
236
        u4 endian;
 
237
 
 
238
        endian = 1;
 
239
        if (*((unsigned char *)(&endian)))
 
240
            return crc32_little(crc, buf, len);
 
241
        else
 
242
            return crc32_big(crc, buf, len);
 
243
    }
 
244
#endif /* BYFOUR */
 
245
/*    crc = crc ^ 0xffffffffUL;*/
 
246
    while (len >= 8) {
 
247
        DO8;
 
248
        len -= 8;
 
249
    }
 
250
    if (len) do {
 
251
        DO1;
 
252
    } while (--len);
 
253
    return crc /* ^ 0xffffffffUL*/;
 
254
}
 
255
 
 
256
#ifdef BYFOUR
 
257
 
 
258
/* ========================================================================= */
 
259
#define DOLIT4 c ^= *buf4++; \
 
260
        c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
 
261
            crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
 
262
#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
 
263
 
 
264
/* ========================================================================= */
 
265
local unsigned long crc32_little(crc, buf, len)
 
266
    unsigned long crc;
 
267
    const unsigned char FAR *buf;
 
268
    unsigned len;
 
269
{
 
270
    register u4 c;
 
271
    register const u4 FAR *buf4;
 
272
 
 
273
    c = (u4)crc;
 
274
    c = ~c;
 
275
    while (len && ((ptrdiff_t)buf & 3)) {
 
276
        c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
 
277
        len--;
 
278
    }
 
279
 
 
280
    buf4 = (const u4 FAR *)buf;
 
281
    while (len >= 32) {
 
282
        DOLIT32;
 
283
        len -= 32;
 
284
    }
 
285
    while (len >= 4) {
 
286
        DOLIT4;
 
287
        len -= 4;
 
288
    }
 
289
    buf = (const unsigned char FAR *)buf4;
 
290
 
 
291
    if (len) do {
 
292
        c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
 
293
    } while (--len);
 
294
    c = ~c;
 
295
    return (unsigned long)c;
 
296
}
 
297
 
 
298
/* ========================================================================= */
 
299
#define DOBIG4 c ^= *++buf4; \
 
300
        c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
 
301
            crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
 
302
#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
 
303
 
 
304
/* ========================================================================= */
 
305
local unsigned long crc32_big(crc, buf, len)
 
306
    unsigned long crc;
 
307
    const unsigned char FAR *buf;
 
308
    unsigned len;
 
309
{
 
310
    register u4 c;
 
311
    register const u4 FAR *buf4;
 
312
 
 
313
    c = REV((u4)crc);
 
314
    c = ~c;
 
315
    while (len && ((ptrdiff_t)buf & 3)) {
 
316
        c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
 
317
        len--;
 
318
    }
 
319
 
 
320
    buf4 = (const u4 FAR *)buf;
 
321
    buf4--;
 
322
    while (len >= 32) {
 
323
        DOBIG32;
 
324
        len -= 32;
 
325
    }
 
326
    while (len >= 4) {
 
327
        DOBIG4;
 
328
        len -= 4;
 
329
    }
 
330
    buf4++;
 
331
    buf = (const unsigned char FAR *)buf4;
 
332
 
 
333
    if (len) do {
 
334
        c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
 
335
    } while (--len);
 
336
    c = ~c;
 
337
    return (unsigned long)(REV(c));
 
338
}
 
339
 
 
340
#endif /* BYFOUR */