vendor/crc-fast/src/crc64/algorithm.rs at show-stat · andymccall/oxygen

◆ show-stat oxygen / vendor / crc-fast / src / crc64 / algorithm.rs

9.3 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.

//! This module provides the CRC-64 implementation for areas where it differs from CRC-32.

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

use crate::algorithm;
use crate::consts::{CRC_CHUNK_SIZE, CRC_HALF_CHUNK_SIZE};
use crate::crc64::consts::SIMD_CONSTANTS;
use crate::enums::Reflector;
use crate::structs::CrcState;
use crate::traits::{ArchOps, EnhancedCrcWidth};

impl EnhancedCrcWidth for crate::structs::Width64 {
    #[inline(always)]
    fn load_constants(_reflected: bool) -> [[u64; 2]; 4] {
        [
            [0x08090a0b0c0d0e0f, 0x0001020304050607], // smask
            [0x8080808080808080, 0x8080808080808080], // mask1 (mask3 reflected)
            [0xffffffffffffffff, 0x00000000ffffffff], // mask2
            [0x0000000000000000, 0xffffffffffffffff], // mask3 (forward)
        ]
    }

    #[inline(always)]
    unsafe fn create_state<T: ArchOps>(
        value: Self::Value,
        reflected: bool,
        ops: &T,
    ) -> CrcState<T::Vector>
    where
        T::Vector: Copy,
    {
        let vector = if reflected {
            ops.create_vector_from_u64(value, false) // Set low 64 bits
        } else {
            ops.create_vector_from_u64(value, true) // Set high 64 bits
        };

        CrcState {
            value: vector,
            reflected,
        }
    }

    #[inline(always)]
    unsafe fn extract_result<T: ArchOps>(vector: T::Vector, reflected: bool, ops: &T) -> Self::Value
    where
        T::Vector: Copy,
    {
        let u64s = ops.extract_u64s(vector);
        if reflected {
            u64s[0] // Low 64 bits for reflected mode
        } else {
            u64s[1] // High 64 bits for non-reflected mode
        }
    }

    #[inline(always)]
    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,
    {
        // CRC-64 specific implementation for folding 16 bytes
        state.value = {
            ops.xor3_vectors(
                ops.carryless_mul_00(state.value, coeff),
                ops.carryless_mul_11(state.value, coeff),
                data_to_xor,
            )
        };
    }

    #[inline(always)]
    unsafe fn fold_width<T: ArchOps>(state: &mut CrcState<T::Vector>, high: u64, low: u64, ops: &T)
    where
        T::Vector: Copy,
    {
        // CRC-64 specific implementation for folding 8 bytes
        let coeff = Self::create_coefficient(high, low, state.reflected, ops);

        if state.reflected {
            let h = ops.carryless_mul_01(coeff, state.value);
            let shifted = ops.shift_right_8(state.value);

            state.value = ops.xor_vectors(h, shifted);
        } else {
            let clmul = ops.carryless_mul_01(state.value, coeff);
            let shifted = ops.shift_left_8(state.value);

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

    #[inline(always)]
    unsafe fn barrett_reduction<T: ArchOps>(
        state: &CrcState<T::Vector>,
        poly: u64,
        mu: u64,
        ops: &T,
    ) -> Self::Value
    where
        T::Vector: Copy,
    {
        // CRC-64 Barrett reduction
        let x = state.value;
        let mu_poly = Self::create_coefficient(mu, poly, state.reflected, ops);

        if state.reflected {
            let clmul1 = ops.carryless_mul_00(x, mu_poly);
            let clmul2 = ops.carryless_mul_10(clmul1, mu_poly);
            let clmul1_shifted = ops.shift_left_8(clmul1);
            let final_xor = ops.xor3_vectors(clmul2, clmul1_shifted, x);

            ops.extract_u64s(final_xor)[1]
        } else {
            // Load mask3 for non-reflected mode
            let mask3 = ops.load_aligned(&[0x0000000000000000, 0xffffffffffffffff]);
            let x1 = ops.and_vectors(x, mask3);
            let clmul1 = ops.carryless_mul_11(x1, mu_poly);
            let clmul2 = ops.carryless_mul_01(ops.xor_vectors(clmul1, x1), mu_poly);
            let final_xor = ops.xor_vectors(clmul2, x);

            ops.extract_u64s(final_xor)[0]
        }
    }

    #[inline(always)]
    unsafe fn create_coefficient<T: ArchOps>(
        high: u64,
        low: u64,
        reflected: bool,
        ops: &T,
    ) -> T::Vector
    where
        T::Vector: Copy,
    {
        ops.create_vector_from_u64_pair(high, low, reflected)
    }

    #[inline(always)]
    unsafe fn perform_final_reduction<T: ArchOps>(
        state: T::Vector,
        reflected: bool,
        keys: &[u64; 23],
        ops: &T,
    ) -> Self::Value
    where
        T::Vector: Copy,
    {
        let mut crc_state = CrcState {
            value: state,
            reflected,
        };

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

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

    #[inline(always)]
    fn get_last_bytes_table_ptr(reflected: bool, remaining_len: usize) -> (*const u8, usize) {
        use crate::crc64::consts::{PSBTBL_FORWARD, PSBTBL_REVERSE};

        if reflected {
            // For reflected mode
            let base_ptr = &PSBTBL_REVERSE as *const _ as *const u8;
            let offset = if remaining_len <= CRC_CHUNK_SIZE {
                remaining_len
            } else {
                let real_remaining = remaining_len % CRC_CHUNK_SIZE;
                if real_remaining == 0 {
                    0
                } else {
                    real_remaining
                }
            };

            (base_ptr, offset)
        } else {
            // For non-reflected mode
            let base_ptr = &PSBTBL_FORWARD as *const _ as *const u8;
            let offset = if remaining_len <= CRC_CHUNK_SIZE {
                CRC_CHUNK_SIZE - remaining_len
            } else {
                let real_remaining = remaining_len % CRC_CHUNK_SIZE;
                if real_remaining == 0 {
                    0
                } else {
                    CRC_CHUNK_SIZE - real_remaining
                }
            };

            (base_ptr, offset)
        }
    }
}

/// Process inputs smaller than 16 bytes
#[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(crate) 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,
{
    // Create a zero-initialized aligned buffer
    let mut buffer = [0u8; CRC_CHUNK_SIZE];

    // Copy input data into the buffer
    buffer[..data.len()].copy_from_slice(data);

    // Get the length for processing
    let len = data.len() as i32;

    // Process the buffer
    let xmm7 = if state.reflected {
        // Get base pointer and standard offset from the trait method
        let (base_ptr, standard_offset) = W::get_last_bytes_table_ptr(true, len as usize);

        // Apply special adjustment for 1-7 bytes
        let ptr = if len < CRC_HALF_CHUNK_SIZE as i32 {
            // For 1-7 bytes: Add CRC_HALF_CHUNK_SIZE (8) to the offset
            base_ptr.add(standard_offset + CRC_HALF_CHUNK_SIZE)
        } else {
            // For 8-15 bytes: Use the standard offset directly
            base_ptr.add(standard_offset)
        };

        // Load shuffle mask
        let xmm0 = ops.load_bytes(ptr);

        // Apply shuffle to data XORed with initial state
        let data_with_crc = ops.xor_vectors(ops.load_bytes(buffer.as_ptr()), state.value);

        ops.shuffle_bytes(data_with_crc, xmm0)
    } else {
        // Calculate pointer offset for forward table
        // For non-reflected mode, we need to apply a special base offset
        let base_offset = if len < CRC_HALF_CHUNK_SIZE as i32 {
            24
        } else {
            16
        };

        // Use the trait method to get the base pointer and standard offset
        let (base_ptr, _) = W::get_last_bytes_table_ptr(false, len as usize);

        // Instead of using standard_offset directly, we use our special base_offset
        // This is the key difference that makes the code work correctly
        let ptr = base_ptr.add(base_offset - len as usize);

        // Load and reflect data
        let reflected_data =
            algorithm::reflect_bytes(reflector, ops.load_bytes(buffer.as_ptr()), ops);
        let data_with_crc = ops.xor_vectors(reflected_data, state.value);

        // Load shuffle mask
        let x0 = ops.load_bytes(ptr);

        if len >= CRC_HALF_CHUNK_SIZE as i32 {
            // For lengths 8-15, XOR with mask1
            let mask1 = ops.load_aligned(&SIMD_CONSTANTS[1]);
            ops.shuffle_bytes(data_with_crc, ops.xor_vectors(x0, mask1))
        } else {
            // For lengths 1-7, just return shuffled data
            ops.shuffle_bytes(data_with_crc, x0)
        }
    };

    if len >= CRC_HALF_CHUNK_SIZE as i32 {
        // For 8-15 bytes, perform additional folding
        return W::perform_final_reduction(xmm7, state.reflected, keys, ops);
    }

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

    // Barrett reduction to finalize
    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

2cd40ea1 Andy McCall 1 month ago ↶	1	// Copyright 2025 Don MacAskill. Licensed under MIT or Apache-2.0.
	2
	3	//! This module provides the CRC-64 implementation for areas where it differs from CRC-32.
	4
	5	#![cfg(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64"))]
	6
	7	use crate::algorithm;
	8	use crate::consts::{CRC_CHUNK_SIZE, CRC_HALF_CHUNK_SIZE};
	9	use crate::crc64::consts::SIMD_CONSTANTS;
	10	use crate::enums::Reflector;
	11	use crate::structs::CrcState;
	12	use crate::traits::{ArchOps, EnhancedCrcWidth};
	13
	14	impl EnhancedCrcWidth for crate::structs::Width64 {
	15	#[inline(always)]
	16	fn load_constants(_reflected: bool) -> [[u64; 2]; 4] {
	17	[
	18	[0x08090a0b0c0d0e0f, 0x0001020304050607], // smask
	19	[0x8080808080808080, 0x8080808080808080], // mask1 (mask3 reflected)
	20	[0xffffffffffffffff, 0x00000000ffffffff], // mask2
	21	[0x0000000000000000, 0xffffffffffffffff], // mask3 (forward)
	22	]
	23	}
	24
	25	#[inline(always)]
	26	unsafe fn create_state<T: ArchOps>(
	27	value: Self::Value,
	28	reflected: bool,
	29	ops: &T,
	30	) -> CrcState<T::Vector>
	31	where
	32	T::Vector: Copy,
	33	{
	34	let vector = if reflected {
	35	ops.create_vector_from_u64(value, false) // Set low 64 bits
	36	} else {
	37	ops.create_vector_from_u64(value, true) // Set high 64 bits
	38	};
	39
	40	CrcState {
	41	value: vector,
	42	reflected,
	43	}
	44	}
	45
	46	#[inline(always)]
	47	unsafe fn extract_result<T: ArchOps>(vector: T::Vector, reflected: bool, ops: &T) -> Self::Value
	48	where
	49	T::Vector: Copy,
	50	{
	51	let u64s = ops.extract_u64s(vector);
	52	if reflected {
	53	u64s[0] // Low 64 bits for reflected mode
	54	} else {
	55	u64s[1] // High 64 bits for non-reflected mode
	56	}
	57	}
	58
	59	#[inline(always)]
	60	unsafe fn fold_16<T: ArchOps>(
	61	state: &mut CrcState<T::Vector>,
	62	coeff: T::Vector,
	63	data_to_xor: T::Vector,
	64	ops: &T,
65	) where
66	T::Vector: Copy,
67	{
68	// CRC-64 specific implementation for folding 16 bytes
69	state.value = {
70	ops.xor3_vectors(
71	ops.carryless_mul_00(state.value, coeff),
72	ops.carryless_mul_11(state.value, coeff),
73	data_to_xor,
74	)
75	};
76	}
77
78	#[inline(always)]
79	unsafe fn fold_width<T: ArchOps>(state: &mut CrcState<T::Vector>, high: u64, low: u64, ops: &T)
80	where
81	T::Vector: Copy,
82	{
83	// CRC-64 specific implementation for folding 8 bytes
84	let coeff = Self::create_coefficient(high, low, state.reflected, ops);
85
86	if state.reflected {
87	let h = ops.carryless_mul_01(coeff, state.value);
88	let shifted = ops.shift_right_8(state.value);
89
90	state.value = ops.xor_vectors(h, shifted);
91	} else {
92	let clmul = ops.carryless_mul_01(state.value, coeff);
93	let shifted = ops.shift_left_8(state.value);
94
95	state.value = ops.xor_vectors(clmul, shifted);
96	}
97	}
98
99	#[inline(always)]
100	unsafe fn barrett_reduction<T: ArchOps>(
101	state: &CrcState<T::Vector>,
102	poly: u64,
103	mu: u64,
104	ops: &T,
105	) -> Self::Value
106	where
107	T::Vector: Copy,
108	{
109	// CRC-64 Barrett reduction
110	let x = state.value;
111	let mu_poly = Self::create_coefficient(mu, poly, state.reflected, ops);
112
113	if state.reflected {
114	let clmul1 = ops.carryless_mul_00(x, mu_poly);
115	let clmul2 = ops.carryless_mul_10(clmul1, mu_poly);
116	let clmul1_shifted = ops.shift_left_8(clmul1);
117	let final_xor = ops.xor3_vectors(clmul2, clmul1_shifted, x);
118
119	ops.extract_u64s(final_xor)[1]
120	} else {
121	// Load mask3 for non-reflected mode
122	let mask3 = ops.load_aligned(&[0x0000000000000000, 0xffffffffffffffff]);
123	let x1 = ops.and_vectors(x, mask3);
124	let clmul1 = ops.carryless_mul_11(x1, mu_poly);
125	let clmul2 = ops.carryless_mul_01(ops.xor_vectors(clmul1, x1), mu_poly);
126	let final_xor = ops.xor_vectors(clmul2, x);
127
128	ops.extract_u64s(final_xor)[0]
129	}
130	}
131
132	#[inline(always)]
133	unsafe fn create_coefficient<T: ArchOps>(
134	high: u64,
135	low: u64,
136	reflected: bool,
137	ops: &T,
138	) -> T::Vector
139	where
140	T::Vector: Copy,
141	{
142	ops.create_vector_from_u64_pair(high, low, reflected)
143	}
144
145	#[inline(always)]
146	unsafe fn perform_final_reduction<T: ArchOps>(
147	state: T::Vector,
148	reflected: bool,
149	keys: &[u64; 23],
150	ops: &T,
151	) -> Self::Value
152	where
153	T::Vector: Copy,
154	{
155	let mut crc_state = CrcState {
156	value: state,
157	reflected,
158	};
159
160	// Fold 16 bytes into 8 bytes
161	Self::fold_width(&mut crc_state, keys[6], keys[5], ops);
162
163	// Perform Barrett reduction to finalize
164	Self::barrett_reduction(&crc_state, keys[8], keys[7], ops)
165	}
166
167	#[inline(always)]
168	fn get_last_bytes_table_ptr(reflected: bool, remaining_len: usize) -> (*const u8, usize) {
169	use crate::crc64::consts::{PSBTBL_FORWARD, PSBTBL_REVERSE};
170
171	if reflected {
172	// For reflected mode
173	let base_ptr = &PSBTBL_REVERSE as const _ as const u8;
174	let offset = if remaining_len <= CRC_CHUNK_SIZE {
175	remaining_len
176	} else {
177	let real_remaining = remaining_len % CRC_CHUNK_SIZE;
178	if real_remaining == 0 {
179	0
180	} else {
181	real_remaining
182	}
183	};
184
185	(base_ptr, offset)
186	} else {
187	// For non-reflected mode
188	let base_ptr = &PSBTBL_FORWARD as const _ as const u8;
189	let offset = if remaining_len <= CRC_CHUNK_SIZE {
190	CRC_CHUNK_SIZE - remaining_len
191	} else {
192	let real_remaining = remaining_len % CRC_CHUNK_SIZE;
193	if real_remaining == 0 {
194	0
195	} else {
196	CRC_CHUNK_SIZE - real_remaining
197	}
198	};
199
200	(base_ptr, offset)
201	}
202	}
203	}
204
205	/// Process inputs smaller than 16 bytes
206	#[inline]
207	#[cfg_attr(
208	any(target_arch = "x86", target_arch = "x86_64"),
209	target_feature(enable = "ssse3,sse4.1,pclmulqdq")
210	)]
211	#[cfg_attr(target_arch = "aarch64", target_feature(enable = "aes"))]
212	pub(crate) unsafe fn process_0_to_15<T: ArchOps, W: EnhancedCrcWidth>(
213	data: &[u8],
214	state: &mut CrcState<T::Vector>,
215	reflector: &Reflector<T::Vector>,
216	keys: &[u64; 23],
217	ops: &T,
218	) -> W::Value
219	where
220	T::Vector: Copy,
221	{
222	// Create a zero-initialized aligned buffer
223	let mut buffer = [0u8; CRC_CHUNK_SIZE];
224
225	// Copy input data into the buffer
226	buffer[..data.len()].copy_from_slice(data);
227
228	// Get the length for processing
229	let len = data.len() as i32;
230
231	// Process the buffer
232	let xmm7 = if state.reflected {
233	// Get base pointer and standard offset from the trait method
234	let (base_ptr, standard_offset) = W::get_last_bytes_table_ptr(true, len as usize);
235
236	// Apply special adjustment for 1-7 bytes
237	let ptr = if len < CRC_HALF_CHUNK_SIZE as i32 {
238	// For 1-7 bytes: Add CRC_HALF_CHUNK_SIZE (8) to the offset
239	base_ptr.add(standard_offset + CRC_HALF_CHUNK_SIZE)
240	} else {
241	// For 8-15 bytes: Use the standard offset directly
242	base_ptr.add(standard_offset)
243	};
244
245	// Load shuffle mask
246	let xmm0 = ops.load_bytes(ptr);
247
248	// Apply shuffle to data XORed with initial state
249	let data_with_crc = ops.xor_vectors(ops.load_bytes(buffer.as_ptr()), state.value);
250
251	ops.shuffle_bytes(data_with_crc, xmm0)
252	} else {
253	// Calculate pointer offset for forward table
254	// For non-reflected mode, we need to apply a special base offset
255	let base_offset = if len < CRC_HALF_CHUNK_SIZE as i32 {
256	24
257	} else {
258	16
259	};
260
261	// Use the trait method to get the base pointer and standard offset
262	let (base_ptr, _) = W::get_last_bytes_table_ptr(false, len as usize);
263
264	// Instead of using standard_offset directly, we use our special base_offset
265	// This is the key difference that makes the code work correctly
266	let ptr = base_ptr.add(base_offset - len as usize);
267
268	// Load and reflect data
269	let reflected_data =
270	algorithm::reflect_bytes(reflector, ops.load_bytes(buffer.as_ptr()), ops);
271	let data_with_crc = ops.xor_vectors(reflected_data, state.value);
272
273	// Load shuffle mask
274	let x0 = ops.load_bytes(ptr);
275
276	if len >= CRC_HALF_CHUNK_SIZE as i32 {
277	// For lengths 8-15, XOR with mask1
278	let mask1 = ops.load_aligned(&SIMD_CONSTANTS[1]);
279	ops.shuffle_bytes(data_with_crc, ops.xor_vectors(x0, mask1))
280	} else {
281	// For lengths 1-7, just return shuffled data
282	ops.shuffle_bytes(data_with_crc, x0)
283	}
284	};
285
286	if len >= CRC_HALF_CHUNK_SIZE as i32 {
287	// For 8-15 bytes, perform additional folding
288	return W::perform_final_reduction(xmm7, state.reflected, keys, ops);
289	}
290
291	let final_state = CrcState {
292	value: xmm7,
293	reflected: state.reflected,
294	};
295
296	// Barrett reduction to finalize
297	W::barrett_reduction(&final_state, keys[8], keys[7], ops)
298	}

Keyboard