vendor/crc-fast/src/crc32/width32_ops.rs at 31d3e932e97a · andymccall/oxygen

# 31d3e932e97a oxygen / vendor / crc-fast / src / crc32 / width32_ops.rs

9.4 KiB · Rust · last changed Strata: the cloud stores send through ureq, so every release target links 1 month ago source blame history raw

// Copyright 2025 Don MacAskill. Licensed under MIT or Apache-2.0.

//! Shared operations for CRC widths that operate in 32-bit space (CRC-16, CRC-32).
//!
//! CRC-16 computation scales 16-bit values to 32-bit space, uses these operations,
//! then scales results back to 16 bits. CRC-32 uses these operations directly.
//!
//! This module eliminates code duplication between the CRC-16 and CRC-32 implementations,
//! which share nearly identical SIMD operations for folding, Barrett reduction, and
//! small input processing.

#![cfg(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64"))]

use crate::algorithm;
use crate::consts::CRC_CHUNK_SIZE;
use crate::crc32::consts::{PSHUFB_SHF_TABLE_FORWARD, PSHUFB_SHF_TABLE_REVERSE, SIMD_CONSTANTS};
use crate::enums::Reflector;
use crate::structs::CrcState;
use crate::traits::{ArchOps, EnhancedCrcWidth};

/// SIMD constants for reflected 32-bit-space CRC operations
pub const WIDTH32_CONSTANTS_REFLECTED: [[u64; 2]; 4] = [
    [0x08090a0b0c0d0e0f, 0x0001020304050607], // smask
    [0x8080808080808080, 0x8080808080808080], // mask1
    [0xFFFFFFFF00000000, 0xFFFFFFFFFFFFFFFF], // mask2 reverse
    [0x0000000000000000, 0x0000000000000000], // unused
];

/// SIMD constants for forward (non-reflected) 32-bit-space CRC operations
pub const WIDTH32_CONSTANTS_FORWARD: [[u64; 2]; 4] = [
    [0x08090a0b0c0d0e0f, 0x0001020304050607], // smask
    [0x8080808080808080, 0x8080808080808080], // mask1
    [0xffffffffffffffff, 0x00000000ffffffff], // mask2 forward
    [0x0000000000000000, 0x0000000000000000], // unused
];

/// Load SIMD constants for 32-bit-space CRC operations
#[inline(always)]
pub fn load_constants(reflected: bool) -> [[u64; 2]; 4] {
    if reflected {
        WIDTH32_CONSTANTS_REFLECTED
    } else {
        WIDTH32_CONSTANTS_FORWARD
    }
}

/// Fold 16 bytes for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
#[inline(always)]
pub unsafe fn fold_16<T: ArchOps>(
    state: &mut CrcState<T::Vector>,
    coeff: T::Vector,
    data_to_xor: T::Vector,
    ops: &T,
) where
    T::Vector: Copy,
{
    let (h, l) = if state.reflected {
        (
            ops.carryless_mul_10(state.value, coeff),
            ops.carryless_mul_01(state.value, coeff),
        )
    } else {
        (
            ops.carryless_mul_00(state.value, coeff),
            ops.carryless_mul_11(state.value, coeff),
        )
    };
    state.value = ops.xor3_vectors(h, l, data_to_xor);
}

/// Fold to width for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
#[inline(always)]
pub unsafe fn fold_width<T: ArchOps>(state: &mut CrcState<T::Vector>, high: u64, low: u64, ops: &T)
where
    T::Vector: Copy,
{
    let coeff_vector_low = ops.create_vector_from_u64_pair_non_reflected(0, low);
    let coeff_vector_high = ops.create_vector_from_u64_pair_non_reflected(high, 0);

    state.value = if state.reflected {
        ops.xor_vectors(
            ops.carryless_mul_00(state.value, coeff_vector_low),
            ops.shift_right_8(state.value),
        )
    } else {
        ops.xor_vectors(
            ops.carryless_mul_01(state.value, coeff_vector_low),
            ops.shift_left_8(state.value),
        )
    };

    let (clmul, masked) = if state.reflected {
        let mask2 = ops.load_aligned(&[0xFFFFFFFF00000000, 0xFFFFFFFFFFFFFFFF]);
        let masked = ops.and_vectors(state.value, mask2);
        let shifted = ops.shift_left_12(state.value);
        let clmul = ops.carryless_mul_11(shifted, coeff_vector_high);
        (clmul, masked)
    } else {
        let mask2 = ops.load_aligned(&[0xFFFFFFFFFFFFFFFF, 0x00000000FFFFFFFF]);
        let masked = ops.and_vectors(state.value, mask2);
        let shifted = ops.shift_right_12(state.value);
        let clmul = ops.carryless_mul_10(shifted, coeff_vector_high);
        (clmul, masked)
    };

    state.value = ops.xor_vectors(clmul, masked);
}

/// Barrett reduction for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
///
/// Returns the raw u64 values from the vector; caller extracts appropriate bits:
/// - CRC-32: extracts 32 bits
/// - CRC-16: extracts 16 bits (after scaling back from 32-bit space)
#[inline(always)]
pub unsafe fn barrett_reduction<T: ArchOps>(
    state: &CrcState<T::Vector>,
    poly: u64,
    mu: u64,
    ops: &T,
) -> [u64; 2]
where
    T::Vector: Copy,
{
    let x = state.value;
    let mu_poly = ops.create_vector_from_u64_pair_non_reflected(poly, mu);

    if state.reflected {
        let clmul1 = ops.carryless_mul_00(x, mu_poly);
        let clmul2 = ops.carryless_mul_10(clmul1, mu_poly);
        let xorred = ops.xor_vectors(x, clmul2);
        ops.extract_u64s(xorred)
    } else {
        let clmul1 = ops.shift_left_4(ops.carryless_mul_01(x, mu_poly));
        let clmul2_shifted = ops.shift_left_4(ops.carryless_mul_11(clmul1, mu_poly));
        let final_xor = ops.xor_vectors(clmul2_shifted, x);
        ops.extract_u64s(final_xor)
    }
}

/// Create coefficient vector for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
#[inline(always)]
pub unsafe fn create_coefficient<T: ArchOps>(high: u64, low: u64, ops: &T) -> T::Vector
where
    T::Vector: Copy,
{
    ops.create_vector_from_u64_pair_non_reflected(high, low)
}

/// Get shuffle table pointer for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
#[inline(always)]
pub fn get_last_bytes_table_ptr(reflected: bool, remaining_len: usize) -> (*const u8, usize) {
    if reflected {
        let base_ptr = &PSHUFB_SHF_TABLE_REVERSE as *const _ as *const u8;
        (base_ptr, remaining_len)
    } else {
        let base_ptr = &PSHUFB_SHF_TABLE_FORWARD as *const _ as *const u8;
        (base_ptr, 16 - remaining_len)
    }
}

/// Perform final reduction for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
///
/// Returns the raw u64 values; caller extracts appropriate bits.
#[inline(always)]
pub unsafe fn perform_final_reduction<T: ArchOps>(
    state: T::Vector,
    reflected: bool,
    keys: &[u64; 23],
    ops: &T,
) -> [u64; 2]
where
    T::Vector: Copy,
{
    let mut crc_state = CrcState {
        value: state,
        reflected,
    };

    // Fold 16 bytes into 8 bytes, then 8 bytes into 4 bytes
    fold_width(&mut crc_state, keys[6], keys[5], ops);

    // Perform Barrett reduction to finalize
    barrett_reduction(&crc_state, keys[8], keys[7], ops)
}

/// Process inputs smaller than 16 bytes for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
#[inline]
#[cfg_attr(
    any(target_arch = "x86", target_arch = "x86_64"),
    target_feature(enable = "ssse3,sse4.1,pclmulqdq")
)]
#[cfg_attr(target_arch = "aarch64", target_feature(enable = "aes"))]
pub unsafe fn process_0_to_15<T: ArchOps, W: EnhancedCrcWidth>(
    data: &[u8],
    state: &mut CrcState<T::Vector>,
    reflector: &Reflector<T::Vector>,
    keys: &[u64; 23],
    ops: &T,
) -> W::Value
where
    T::Vector: Copy,
{
    let mut buffer = [0u8; CRC_CHUNK_SIZE];
    if state.reflected {
        buffer[CRC_CHUNK_SIZE - data.len()..].copy_from_slice(data);
    } else {
        buffer[..data.len()].copy_from_slice(data);
    }

    let len = data.len() as i32;
    let base = &PSHUFB_SHF_TABLE_REVERSE as *const _ as *const u8;

    let xmm7 = if state.reflected {
        let data = ops.load_bytes(buffer.as_ptr());
        let mask1 = ops.load_aligned(&SIMD_CONSTANTS[1]);

        let ptr = base.add(if len < 4 {
            8 + len as usize
        } else {
            len as usize
        });
        let mask = ops.load_bytes(ptr);
        let modified_mask = ops.xor_vectors(mask, mask1);
        let shuffled_crc = ops.shuffle_bytes(state.value, modified_mask);

        ops.xor_vectors(
            if len < 4 {
                ops.shift_right_8(data)
            } else {
                data
            },
            shuffled_crc,
        )
    } else {
        let data_arr = ops.load_bytes(buffer.as_ptr());
        let reflected_data = algorithm::reflect_bytes(reflector, data_arr, ops);
        let data_with_crc = ops.xor_vectors(reflected_data, state.value);

        if len < 4 {
            let result = match len {
                3 => ops.shift_right_5(data_with_crc),
                2 => ops.shift_right_6(data_with_crc),
                1 => ops.shift_right_7(data_with_crc),
                _ => data_with_crc,
            };

            return W::barrett_reduction(
                &CrcState {
                    value: result,
                    reflected: false,
                },
                keys[8],
                keys[7],
                ops,
            );
        }

        let base = &PSHUFB_SHF_TABLE_FORWARD as *const _ as *const u8;
        let ptr = base.add(16 - len as usize);
        let x0 = ops.load_bytes(ptr);
        let mask1 = ops.load_aligned(&SIMD_CONSTANTS[1]);
        let x0 = ops.xor_vectors(x0, mask1);

        if len < 8 {
            ops.shuffle_bytes(data_with_crc, x0)
        } else {
            let mut xmm7 = ops.load_bytes(buffer.as_ptr());
            if let Reflector::ForwardReflector { smask } = reflector {
                xmm7 = ops.shuffle_bytes(xmm7, *smask);
            }
            xmm7 = ops.xor_vectors(xmm7, state.value);
            let ptr = base.add(16 - len as usize);
            let x0 = ops.load_bytes(ptr);
            let xmm0 = ops.xor_vectors(x0, mask1);

            ops.shuffle_bytes(xmm7, xmm0)
        }
    };

    if len >= 4 {
        return W::perform_final_reduction(xmm7, state.reflected, keys, ops);
    }

    let final_state = CrcState {
        value: xmm7,
        reflected: state.reflected,
    };

    W::barrett_reduction(&final_state, keys[8], keys[7], ops)
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1	// Copyright 2025 Don MacAskill. Licensed under MIT or Apache-2.0.
2
3	//! Shared operations for CRC widths that operate in 32-bit space (CRC-16, CRC-32).
4	//!
5	//! CRC-16 computation scales 16-bit values to 32-bit space, uses these operations,
6	//! then scales results back to 16 bits. CRC-32 uses these operations directly.
7	//!
8	//! This module eliminates code duplication between the CRC-16 and CRC-32 implementations,
9	//! which share nearly identical SIMD operations for folding, Barrett reduction, and
10	//! small input processing.
11
12	#![cfg(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64"))]
13
14	use crate::algorithm;
15	use crate::consts::CRC_CHUNK_SIZE;
16	use crate::crc32::consts::{PSHUFB_SHF_TABLE_FORWARD, PSHUFB_SHF_TABLE_REVERSE, SIMD_CONSTANTS};
17	use crate::enums::Reflector;
18	use crate::structs::CrcState;
19	use crate::traits::{ArchOps, EnhancedCrcWidth};
20
21	/// SIMD constants for reflected 32-bit-space CRC operations
22	pub const WIDTH32_CONSTANTS_REFLECTED: [[u64; 2]; 4] = [
23	[0x08090a0b0c0d0e0f, 0x0001020304050607], // smask
24	[0x8080808080808080, 0x8080808080808080], // mask1
25	[0xFFFFFFFF00000000, 0xFFFFFFFFFFFFFFFF], // mask2 reverse
26	[0x0000000000000000, 0x0000000000000000], // unused
27	];
28
29	/// SIMD constants for forward (non-reflected) 32-bit-space CRC operations
30	pub const WIDTH32_CONSTANTS_FORWARD: [[u64; 2]; 4] = [
31	[0x08090a0b0c0d0e0f, 0x0001020304050607], // smask
32	[0x8080808080808080, 0x8080808080808080], // mask1
33	[0xffffffffffffffff, 0x00000000ffffffff], // mask2 forward
34	[0x0000000000000000, 0x0000000000000000], // unused
35	];
36
37	/// Load SIMD constants for 32-bit-space CRC operations
38	#[inline(always)]
39	pub fn load_constants(reflected: bool) -> [[u64; 2]; 4] {
40	if reflected {
41	WIDTH32_CONSTANTS_REFLECTED
42	} else {
43	WIDTH32_CONSTANTS_FORWARD
44	}
45	}
46
47	/// Fold 16 bytes for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
48	#[inline(always)]
49	pub unsafe fn fold_16<T: ArchOps>(
50	state: &mut CrcState<T::Vector>,
51	coeff: T::Vector,
52	data_to_xor: T::Vector,
53	ops: &T,
54	) where
55	T::Vector: Copy,
56	{
57	let (h, l) = if state.reflected {
58	(
59	ops.carryless_mul_10(state.value, coeff),
60	ops.carryless_mul_01(state.value, coeff),
61	)
62	} else {
63	(
64	ops.carryless_mul_00(state.value, coeff),
65	ops.carryless_mul_11(state.value, coeff),
66	)
67	};
68	state.value = ops.xor3_vectors(h, l, data_to_xor);
69	}
70
71	/// Fold to width for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
72	#[inline(always)]
73	pub unsafe fn fold_width<T: ArchOps>(state: &mut CrcState<T::Vector>, high: u64, low: u64, ops: &T)
74	where
75	T::Vector: Copy,
76	{
77	let coeff_vector_low = ops.create_vector_from_u64_pair_non_reflected(0, low);
78	let coeff_vector_high = ops.create_vector_from_u64_pair_non_reflected(high, 0);
79
80	state.value = if state.reflected {
81	ops.xor_vectors(
82	ops.carryless_mul_00(state.value, coeff_vector_low),
83	ops.shift_right_8(state.value),
84	)
85	} else {
86	ops.xor_vectors(
87	ops.carryless_mul_01(state.value, coeff_vector_low),
88	ops.shift_left_8(state.value),
89	)
90	};
91
92	let (clmul, masked) = if state.reflected {
93	let mask2 = ops.load_aligned(&[0xFFFFFFFF00000000, 0xFFFFFFFFFFFFFFFF]);
94	let masked = ops.and_vectors(state.value, mask2);
95	let shifted = ops.shift_left_12(state.value);
96	let clmul = ops.carryless_mul_11(shifted, coeff_vector_high);
97	(clmul, masked)
98	} else {
99	let mask2 = ops.load_aligned(&[0xFFFFFFFFFFFFFFFF, 0x00000000FFFFFFFF]);
100	let masked = ops.and_vectors(state.value, mask2);
101	let shifted = ops.shift_right_12(state.value);
102	let clmul = ops.carryless_mul_10(shifted, coeff_vector_high);
103	(clmul, masked)
104	};
105
106	state.value = ops.xor_vectors(clmul, masked);
107	}
108
109	/// Barrett reduction for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
110	///
111	/// Returns the raw u64 values from the vector; caller extracts appropriate bits:
112	/// - CRC-32: extracts 32 bits
113	/// - CRC-16: extracts 16 bits (after scaling back from 32-bit space)
114	#[inline(always)]
115	pub unsafe fn barrett_reduction<T: ArchOps>(
116	state: &CrcState<T::Vector>,
117	poly: u64,
118	mu: u64,
119	ops: &T,
120	) -> [u64; 2]
121	where
122	T::Vector: Copy,
123	{
124	let x = state.value;
125	let mu_poly = ops.create_vector_from_u64_pair_non_reflected(poly, mu);
126
127	if state.reflected {
128	let clmul1 = ops.carryless_mul_00(x, mu_poly);
129	let clmul2 = ops.carryless_mul_10(clmul1, mu_poly);
130	let xorred = ops.xor_vectors(x, clmul2);
131	ops.extract_u64s(xorred)
132	} else {
133	let clmul1 = ops.shift_left_4(ops.carryless_mul_01(x, mu_poly));
134	let clmul2_shifted = ops.shift_left_4(ops.carryless_mul_11(clmul1, mu_poly));
135	let final_xor = ops.xor_vectors(clmul2_shifted, x);
136	ops.extract_u64s(final_xor)
137	}
138	}
139
140	/// Create coefficient vector for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
141	#[inline(always)]
142	pub unsafe fn create_coefficient<T: ArchOps>(high: u64, low: u64, ops: &T) -> T::Vector
143	where
144	T::Vector: Copy,
145	{
146	ops.create_vector_from_u64_pair_non_reflected(high, low)
147	}
148
149	/// Get shuffle table pointer for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
150	#[inline(always)]
151	pub fn get_last_bytes_table_ptr(reflected: bool, remaining_len: usize) -> (*const u8, usize) {
152	if reflected {
153	let base_ptr = &PSHUFB_SHF_TABLE_REVERSE as const _ as const u8;
154	(base_ptr, remaining_len)
155	} else {
156	let base_ptr = &PSHUFB_SHF_TABLE_FORWARD as const _ as const u8;
157	(base_ptr, 16 - remaining_len)
158	}
159	}
160
161	/// Perform final reduction for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
162	///
163	/// Returns the raw u64 values; caller extracts appropriate bits.
164	#[inline(always)]
165	pub unsafe fn perform_final_reduction<T: ArchOps>(
166	state: T::Vector,
167	reflected: bool,
168	keys: &[u64; 23],
169	ops: &T,
170	) -> [u64; 2]
171	where
172	T::Vector: Copy,
173	{
174	let mut crc_state = CrcState {
175	value: state,
176	reflected,
177	};
178
179	// Fold 16 bytes into 8 bytes, then 8 bytes into 4 bytes
180	fold_width(&mut crc_state, keys[6], keys[5], ops);
181
182	// Perform Barrett reduction to finalize
183	barrett_reduction(&crc_state, keys[8], keys[7], ops)
184	}
185
186	/// Process inputs smaller than 16 bytes for 32-bit-space CRC operations (used by CRC-16 and CRC-32)
187	#[inline]
188	#[cfg_attr(
189	any(target_arch = "x86", target_arch = "x86_64"),
190	target_feature(enable = "ssse3,sse4.1,pclmulqdq")
191	)]
192	#[cfg_attr(target_arch = "aarch64", target_feature(enable = "aes"))]
193	pub unsafe fn process_0_to_15<T: ArchOps, W: EnhancedCrcWidth>(
194	data: &[u8],
195	state: &mut CrcState<T::Vector>,
196	reflector: &Reflector<T::Vector>,
197	keys: &[u64; 23],
198	ops: &T,
199	) -> W::Value
200	where
201	T::Vector: Copy,
202	{
203	let mut buffer = [0u8; CRC_CHUNK_SIZE];
204	if state.reflected {
205	buffer[CRC_CHUNK_SIZE - data.len()..].copy_from_slice(data);
206	} else {
207	buffer[..data.len()].copy_from_slice(data);
208	}
209
210	let len = data.len() as i32;
211	let base = &PSHUFB_SHF_TABLE_REVERSE as const _ as const u8;
212
213	let xmm7 = if state.reflected {
214	let data = ops.load_bytes(buffer.as_ptr());
215	let mask1 = ops.load_aligned(&SIMD_CONSTANTS[1]);
216
217	let ptr = base.add(if len < 4 {
218	8 + len as usize
219	} else {
220	len as usize
221	});
222	let mask = ops.load_bytes(ptr);
223	let modified_mask = ops.xor_vectors(mask, mask1);
224	let shuffled_crc = ops.shuffle_bytes(state.value, modified_mask);
225
226	ops.xor_vectors(
227	if len < 4 {
228	ops.shift_right_8(data)
229	} else {
230	data
231	},
232	shuffled_crc,
233	)
234	} else {
235	let data_arr = ops.load_bytes(buffer.as_ptr());
236	let reflected_data = algorithm::reflect_bytes(reflector, data_arr, ops);
237	let data_with_crc = ops.xor_vectors(reflected_data, state.value);
238
239	if len < 4 {
240	let result = match len {
241	3 => ops.shift_right_5(data_with_crc),
242	2 => ops.shift_right_6(data_with_crc),
243	1 => ops.shift_right_7(data_with_crc),
244	_ => data_with_crc,
245	};
246
247	return W::barrett_reduction(
248	&CrcState {
249	value: result,
250	reflected: false,
251	},
252	keys[8],
253	keys[7],
254	ops,
255	);
256	}
257
258	let base = &PSHUFB_SHF_TABLE_FORWARD as const _ as const u8;
259	let ptr = base.add(16 - len as usize);
260	let x0 = ops.load_bytes(ptr);
261	let mask1 = ops.load_aligned(&SIMD_CONSTANTS[1]);
262	let x0 = ops.xor_vectors(x0, mask1);
263
264	if len < 8 {
265	ops.shuffle_bytes(data_with_crc, x0)
266	} else {
267	let mut xmm7 = ops.load_bytes(buffer.as_ptr());
268	if let Reflector::ForwardReflector { smask } = reflector {
269	xmm7 = ops.shuffle_bytes(xmm7, *smask);
270	}
271	xmm7 = ops.xor_vectors(xmm7, state.value);
272	let ptr = base.add(16 - len as usize);
273	let x0 = ops.load_bytes(ptr);
274	let xmm0 = ops.xor_vectors(x0, mask1);
275
276	ops.shuffle_bytes(xmm7, xmm0)
277	}
278	};
279
280	if len >= 4 {
281	return W::perform_final_reduction(xmm7, state.reflected, keys, ops);
282	}
283
284	let final_state = CrcState {
285	value: xmm7,
286	reflected: state.reflected,
287	};
288
289	W::barrett_reduction(&final_state, keys[8], keys[7], ops)
290	}

Keyboard