crc32c/
combine.rs

Help
1//! Implements the CRC32c "combine" function, which calculates the CRC32c of two byte streams
2//! concatenated together using their individual CRC32c values (plus the length of the second byte
3//! stream).
4//!
5//! This module is essentially a line-by-line translation of ZLIB's CRC "combine" function
6//! implementation from C to Rust, except for the CRC polynomial used (original uses the CRC32
7//! polynomial 0xedb88320UL, we use the CRC32c polynomial 0x82F63B78).
8//!
9//! Link to original implementation: https://github.com/madler/zlib/blob/master/crc32.c
10//!
11//! This file is based on the Zlib project, located at: https://github.com/madler/zlib,
12//! which includes the following notice:
13//!
14//! crc32.c -- compute the CRC-32 of a data stream
15//! Copyright (C) 1995-2006, 2010, 2011, 2012, 2016 Mark Adler
16//! For conditions of distribution and use, see copyright notice in zlib.h
17//!
18//! Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
19//! CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
20//! tables for updating the shift register in one step with three exclusive-ors
21//! instead of four steps with four exclusive-ors.  This results in about a
22//! factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
23
24const GF2_DIM: usize = 32;
25
26fn gf2_matrix_times(mat: &[u32; GF2_DIM], mut vec: u32) -> u32 {
27    let mut sum = 0;
28    let mut idx = 0;
29    while vec > 0 {
30        if vec & 1 == 1 {
31            sum ^= mat[idx];
32        }
33        vec >>= 1;
34        idx += 1;
35    }
36    sum
37}
38
39fn gf2_matrix_square(square: &mut [u32; GF2_DIM], mat: &[u32; GF2_DIM]) {
40    for n in 0..GF2_DIM {
41        square[n] = gf2_matrix_times(mat, mat[n]);
42    }
43}
44
45pub(crate) fn crc32c_combine(mut crc1: u32, crc2: u32, mut len2: usize) -> u32 {
46    let mut row: u32 = 1;
47    let mut even = [0u32; GF2_DIM]; /* even-power-of-two zeros operator */
48    let mut odd = [0u32; GF2_DIM]; /* odd-power-of-two zeros operator */
49
50    /* degenerate case (also disallow negative lengths) */
51    if len2 == 0 {
52        return crc1;
53    }
54
55    /* put operator for one zero bit in odd */
56    odd[0] = 0x82F63B78; /* CRC-32c polynomial */
57    #[allow(clippy::needless_range_loop)]
58    for n in 1..GF2_DIM {
59        odd[n] = row;
60        row <<= 1;
61    }
62
63    /* put operator for two zero bits in even */
64    gf2_matrix_square(&mut even, &odd);
65
66    /* put operator for four zero bits in odd */
67    gf2_matrix_square(&mut odd, &even);
68
69    /* apply len2 zeros to crc1 (first square will put the operator for one
70    zero byte, eight zero bits, in even) */
71    loop {
72        /* apply zeros operator for this bit of len2 */
73        gf2_matrix_square(&mut even, &odd);
74        if len2 & 1 == 1 {
75            crc1 = gf2_matrix_times(&even, crc1);
76        }
77        len2 >>= 1;
78
79        /* if no more bits set, then done */
80        if len2 == 0 {
81            break;
82        }
83
84        /* another iteration of the loop with odd and even swapped */
85        gf2_matrix_square(&mut odd, &even);
86        if len2 & 1 == 1 {
87            crc1 = gf2_matrix_times(&odd, crc1);
88        }
89        len2 >>= 1;
90
91        /* if no more bits set, then done */
92        if len2 == 0 {
93            break;
94        }
95    }
96
97    /* return combined crc */
98    crc1 ^= crc2;
99    crc1
100}
crc32c/combine.rs

crc32c/
combine.rs
