diff options
author | Mark Adler <madler@alumni.caltech.edu> | 2011-09-09 23:24:24 -0700 |
---|---|---|
committer | Mark Adler <madler@alumni.caltech.edu> | 2011-09-09 23:24:24 -0700 |
commit | 9811b53dd9e8f67015c7199fff12b5bfc6965330 (patch) | |
tree | bfa72ee22967fb56833203dfcd31c473c86b1bf1 /crc32.c | |
parent | 79fbcdc939b5d515218187a0d5f2526fb632075a (diff) | |
download | zlib-9811b53dd9e8f67015c7199fff12b5bfc6965330.tar.gz zlib-9811b53dd9e8f67015c7199fff12b5bfc6965330.tar.bz2 zlib-9811b53dd9e8f67015c7199fff12b5bfc6965330.zip |
zlib 1.2.2.1v1.2.2.1
Diffstat (limited to 'crc32.c')
-rw-r--r-- | crc32.c | 95 |
1 files changed, 92 insertions, 3 deletions
@@ -1,12 +1,12 @@ | |||
1 | /* crc32.c -- compute the CRC-32 of a data stream | 1 | /* crc32.c -- compute the CRC-32 of a data stream |
2 | * Copyright (C) 1995-2003 Mark Adler | 2 | * Copyright (C) 1995-2004 Mark Adler |
3 | * For conditions of distribution and use, see copyright notice in zlib.h | 3 | * For conditions of distribution and use, see copyright notice in zlib.h |
4 | * | 4 | * |
5 | * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster | 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 | 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 | 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 | 8 | * instead of four steps with four exclusive-ors. This results in about a |
9 | * of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. | 9 | * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. |
10 | */ | 10 | */ |
11 | 11 | ||
12 | /* @(#) $Id$ */ | 12 | /* @(#) $Id$ */ |
@@ -72,6 +72,9 @@ local void make_crc_table OF((void)); | |||
72 | #ifdef MAKECRCH | 72 | #ifdef MAKECRCH |
73 | local void write_table OF((FILE *, const unsigned long FAR *)); | 73 | local void write_table OF((FILE *, const unsigned long FAR *)); |
74 | #endif /* MAKECRCH */ | 74 | #endif /* MAKECRCH */ |
75 | local unsigned long gf2_matrix_times OF((unsigned long *mat, | ||
76 | unsigned long vec)); | ||
77 | local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); | ||
75 | 78 | ||
76 | /* | 79 | /* |
77 | Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: | 80 | Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: |
@@ -331,3 +334,89 @@ local unsigned long crc32_big(crc, buf, len) | |||
331 | } | 334 | } |
332 | 335 | ||
333 | #endif /* BYFOUR */ | 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 | uLong 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 | } | ||