~axehind007/libmemcached/axehind-testing

« back to all changes in this revision

Viewing changes to zlib/crc32.c

  • Committer: Brian Pontz
  • Date: 2011-05-05 04:37:26 UTC
  • Revision ID: bpontz@bpontz-laptop-20110505043726-2gv8ybayvoojydur
Adding required zlib files for memory compression

Show diffs side-by-side

added added

removed removed

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