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