1 /* crc32_comb.c -- compute the CRC-32 of a data stream
2 * Copyright (C) 1995-2006, 2010, 2011, 2012, 2016, 2018 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 #include "zbuild.h"
13 #include <inttypes.h>
14 #include "deflate.h"
15 #include "crc32_p.h"
16 #include "crc32_comb_tbl.h"
17
18
19 /* Local functions for crc concatenation */
20 static uint32_t crc32_combine_(uint32_t crc1, uint32_t crc2, z_off64_t len2);
21 static void crc32_combine_gen_(uint32_t *op, z_off64_t len2);
22
23 /* ========================================================================= */
crc32_combine_(uint32_t crc1,uint32_t crc2,z_off64_t len2)24 static uint32_t crc32_combine_(uint32_t crc1, uint32_t crc2, z_off64_t len2) {
25 int n;
26
27 if (len2 > 0)
28 /* operator for 2^n zeros repeats every GF2_DIM n values */
29 for (n = 0; len2; n = (n + 1) % GF2_DIM, len2 >>= 1)
30 if (len2 & 1)
31 crc1 = gf2_matrix_times(crc_comb[n], crc1);
32 return crc1 ^ crc2;
33 }
34
35 /* ========================================================================= */
36 #ifdef ZLIB_COMPAT
PREFIX(crc32_combine)37 unsigned long Z_EXPORT PREFIX(crc32_combine)(unsigned long crc1, unsigned long crc2, z_off_t len2) {
38 return (unsigned long)crc32_combine_((uint32_t)crc1, (uint32_t)crc2, len2);
39 }
40
PREFIX4(crc32_combine)41 unsigned long Z_EXPORT PREFIX4(crc32_combine)(unsigned long crc1, unsigned long crc2, z_off64_t len2) {
42 return (unsigned long)crc32_combine_((uint32_t)crc1, (uint32_t)crc2, len2);
43 }
44 #else
PREFIX4(crc32_combine)45 uint32_t Z_EXPORT PREFIX4(crc32_combine)(uint32_t crc1, uint32_t crc2, z_off64_t len2) {
46 return crc32_combine_(crc1, crc2, len2);
47 }
48 #endif
49
50 /* ========================================================================= */
51
crc32_combine_gen_(uint32_t * op,z_off64_t len2)52 static void crc32_combine_gen_(uint32_t *op, z_off64_t len2) {
53 uint32_t row;
54 int j;
55 unsigned i;
56
57 /* if len2 is zero or negative, return the identity matrix */
58 if (len2 <= 0) {
59 row = 1;
60 for (j = 0; j < GF2_DIM; j++) {
61 op[j] = row;
62 row <<= 1;
63 }
64 return;
65 }
66
67 /* at least one bit in len2 is set -- find it, and copy the operator
68 corresponding to that position into op */
69 i = 0;
70 for (;;) {
71 if (len2 & 1) {
72 for (j = 0; j < GF2_DIM; j++)
73 op[j] = crc_comb[i][j];
74 break;
75 }
76 len2 >>= 1;
77 i = (i + 1) % GF2_DIM;
78 }
79
80 /* for each remaining bit set in len2 (if any), multiply op by the operator
81 corresponding to that position */
82 for (;;) {
83 len2 >>= 1;
84 i = (i + 1) % GF2_DIM;
85 if (len2 == 0)
86 break;
87 if (len2 & 1)
88 for (j = 0; j < GF2_DIM; j++)
89 op[j] = gf2_matrix_times(crc_comb[i], op[j]);
90 }
91 }
92
93 /* ========================================================================= */
94
95 #ifdef ZLIB_COMPAT
PREFIX(crc32_combine_gen)96 void Z_EXPORT PREFIX(crc32_combine_gen)(uint32_t *op, z_off_t len2) {
97 crc32_combine_gen_(op, len2);
98 }
99 #endif
100
PREFIX4(crc32_combine_gen)101 void Z_EXPORT PREFIX4(crc32_combine_gen)(uint32_t *op, z_off64_t len2) {
102 crc32_combine_gen_(op, len2);
103 }
104
105 /* ========================================================================= */
PREFIX(crc32_combine_op)106 uint32_t Z_EXPORT PREFIX(crc32_combine_op)(uint32_t crc1, uint32_t crc2, const uint32_t *op) {
107 return gf2_matrix_times(op, crc1) ^ crc2;
108 }
109