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 */
20static uint32_t crc32_combine_(uint32_t crc1, uint32_t crc2, z_off64_t len2);
21static void crc32_combine_gen_(uint32_t op[GF2_DIM], z_off64_t len2);
22
23/* ========================================================================= */
24static 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(mat: crc_comb[n], vec: crc1);
32 return crc1 ^ crc2;
33}
34
35/* ========================================================================= */
36#ifdef ZLIB_COMPAT
37unsigned long Z_EXPORT PREFIX(crc32_combine)(unsigned long crc1, unsigned long crc2, z_off_t len2) {
38 return (unsigned long)crc32_combine_(crc1: (uint32_t)crc1, crc2: (uint32_t)crc2, len2);
39}
40
41unsigned long Z_EXPORT PREFIX4(crc32_combine)(unsigned long crc1, unsigned long crc2, z_off64_t len2) {
42 return (unsigned long)crc32_combine_(crc1: (uint32_t)crc1, crc2: (uint32_t)crc2, len2);
43}
44#else
45uint32_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
52static void crc32_combine_gen_(uint32_t op[GF2_DIM], 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(mat: crc_comb[i], vec: op[j]);
90 }
91}
92
93/* ========================================================================= */
94
95#ifdef ZLIB_COMPAT
96void Z_EXPORT PREFIX(crc32_combine_gen)(uint32_t *op, z_off_t len2) {
97 crc32_combine_gen_(op, len2);
98}
99void Z_EXPORT PREFIX4(crc32_combine_gen)(uint32_t *op, z_off64_t len2) {
100 crc32_combine_gen_(op, len2);
101}
102#else
103void Z_EXPORT PREFIX4(crc32_combine_gen)(uint32_t op[GF2_DIM], z_off64_t len2) {
104 crc32_combine_gen_(op, len2);
105}
106#endif
107
108/* ========================================================================= */
109uint32_t Z_EXPORT PREFIX(crc32_combine_op)(uint32_t crc1, uint32_t crc2, const uint32_t *op) {
110 return gf2_matrix_times(mat: op, vec: crc1) ^ crc2;
111}
112