vendor/crc-fast/src/algorithm.rs at c96354484bd9 · andymccall/oxygen

# c96354484bd9 oxygen / vendor / crc-fast / src / algorithm.rs

18.7 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 contains the main algorithm for CRC calculation.
//!
//! This implementation is designed to work with both CRC-32 and CRC-64 algorithms.
//!
//! It uses SIMD instructions for performance optimization and is designed to be
//! platform-agnostic.
//!
//! The code is structured to allow for easy extension and modification for
//! different architectures and CRC algorithms.
//!
//! The main entry point is the `update` function, which takes the current CRC state,
//! the input data, CRC parameters, and architecture-specific operations.

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

use crate::consts::CRC_CHUNK_SIZE;
use crate::enums::{DataChunkProcessor, Reflector};
use crate::structs::CrcState;
use crate::traits::{ArchOps, EnhancedCrcWidth};
use crate::{crc16, crc32, crc64, CrcParams};

/// Extract keys from CrcParams using safe accessor methods
/// This ensures bounds checking and future compatibility
#[inline(always)]
fn extract_keys_array(params: &CrcParams) -> [u64; 23] {
    [
        params.get_key(0),
        params.get_key(1),
        params.get_key(2),
        params.get_key(3),
        params.get_key(4),
        params.get_key(5),
        params.get_key(6),
        params.get_key(7),
        params.get_key(8),
        params.get_key(9),
        params.get_key(10),
        params.get_key(11),
        params.get_key(12),
        params.get_key(13),
        params.get_key(14),
        params.get_key(15),
        params.get_key(16),
        params.get_key(17),
        params.get_key(18),
        params.get_key(19),
        params.get_key(20),
        params.get_key(21),
        params.get_key(22),
    ]
}

/// Main entry point that works for both CRC-32 and CRC-64
#[inline(always)]
pub unsafe fn update<T: ArchOps, W: EnhancedCrcWidth>(
    state: W::Value,
    bytes: &[u8],
    params: &CrcParams,
    ops: &T,
) -> W::Value
where
    T::Vector: Copy,
{
    let len = bytes.len();
    if len == 0 {
        return state;
    }

    // Create the appropriate reflector based on CRC type
    let reflector = if params.refin {
        Reflector::NoReflector
    } else {
        // Load mask for byte-swapping operations
        let smask = ops.load_aligned(&W::load_constants(params.refin)[0] as *const [u64; 2]);
        Reflector::ForwardReflector { smask }
    };

    // Create initial CRC state
    let mut crc_state = W::create_state(state, params.refin, ops);

    // Extract keys once and pass by reference to avoid repeated stack copies
    let keys = extract_keys_array(params);

    // Process data differently based on length
    // On ARM M4 Max, ARM c8g, x86 c7a, and x86 c7i, using 128 bytes is a measurably faster
    // threshold than 256 bytes...
    if len < 128 {
        // Select processor based on input length
        let processor = DataChunkProcessor::for_length(len);
        return process_by_strategy::<T, W>(
            processor,
            bytes,
            &mut crc_state,
            reflector,
            &keys,
            ops,
        );
    }

    // Process large inputs with SIMD-optimized approach
    process_large_aligned::<T, W>(bytes, &mut crc_state, reflector, &keys, ops)
}

/// Process data with the selected strategy
#[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"))]
unsafe fn process_by_strategy<T: ArchOps, W: EnhancedCrcWidth>(
    strategy: DataChunkProcessor,
    data: &[u8],
    state: &mut CrcState<T::Vector>,
    reflector: Reflector<T::Vector>,
    keys: &[u64; 23],
    ops: &T,
) -> W::Value
where
    T::Vector: Copy,
{
    match strategy {
        DataChunkProcessor::From0To15 => match W::WIDTH {
            16 => crc16::algorithm::process_0_to_15::<T, W>(data, state, &reflector, keys, ops),
            32 => crc32::algorithm::process_0_to_15::<T, W>(data, state, &reflector, keys, ops),
            64 => crc64::algorithm::process_0_to_15::<T, W>(data, state, &reflector, keys, ops),
            _ => panic!("Unsupported CRC width"),
        },
        DataChunkProcessor::From16 => {
            process_exactly_16::<T, W>(data, state, &reflector, keys, ops)
        }
        DataChunkProcessor::From17To31 => {
            process_17_to_31::<T, W>(data, state, &reflector, keys, ops)
        }
        DataChunkProcessor::From32To255 => {
            process_32_to_255::<T, W>(data, state, &reflector, keys, ops)
        }
    }
}

/// Process large inputs with proper SIMD alignment
#[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"))]
unsafe fn process_large_aligned<T: ArchOps, W: EnhancedCrcWidth>(
    bytes: &[u8],
    state: &mut CrcState<T::Vector>,
    reflector: Reflector<T::Vector>,
    keys: &[u64; 23],
    ops: &T,
) -> W::Value
where
    T::Vector: Copy,
{
    // Align data for SIMD processing
    let (left, middle, right) = bytes.align_to::<[T::Vector; 8]>();

    if let Some((first, rest)) = middle.split_first() {
        if !left.is_empty() {
            let processor = DataChunkProcessor::for_length(left.len());
            // Process unaligned bytes at the start
            let left_crc =
                process_by_strategy::<T, W>(processor, left, state, reflector, keys, ops);
            // Update state with the result from processing left bytes
            *state = W::create_state(left_crc, state.reflected, ops);
        }

        // try to use the enhanced SIMD implementation first, fall back to non-enhanced if necessary
        if rest.is_empty()
            || !ops.process_enhanced_simd_blocks::<W>(state, first, rest, &reflector, keys)
        {
            process_simd_chunks::<T, W>(state, first, rest, &reflector, keys, ops);
        }

        // Process any unaligned bytes at the end
        if !right.is_empty() {
            let processor = DataChunkProcessor::for_length(right.len());
            // Use the current state to process the right bytes
            return process_by_strategy::<T, W>(processor, right, state, reflector, keys, ops);
        }

        // Extract the final result
        return W::extract_result(state.value, state.reflected, ops);
    }

    // Fall back to existing implementation if proper alignment isn't possible
    let processor = DataChunkProcessor::for_length(bytes.len());
    process_by_strategy::<T, W>(processor, bytes, state, reflector, keys, ops)
}

/// Process SIMD-aligned chunks of 128 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"))]
unsafe fn process_simd_chunks<T: ArchOps, W: EnhancedCrcWidth>(
    state: &mut CrcState<T::Vector>,
    first: &[T::Vector; 8],
    rest: &[[T::Vector; 8]],
    reflector: &Reflector<T::Vector>,
    keys: &[u64; 23],
    ops: &T,
) where
    T::Vector: Copy,
{
    // Create a copy of the first 128 bytes
    let mut x = *first;

    // Apply initial reflection if needed
    for item in &mut x {
        *item = reflect_bytes(reflector, *item, ops);
    }

    // XOR initial CRC with the first 16 bytes
    x[0] = ops.xor_vectors(x[0], state.value);

    // Load the coefficient pair for folding
    let coeff = W::create_coefficient(keys[4], keys[3], state.reflected, ops);

    // Process remaining 128-byte chunks
    for chunk in rest {
        for (xi, yi) in x.iter_mut().zip(chunk.iter()) {
            // Load and reflect the new data if needed
            let yi = reflect_bytes(reflector, *yi, ops);

            // Create a temporary state for folding
            let mut temp_state = CrcState {
                value: *xi,
                reflected: state.reflected,
            };

            // Fold 16 bytes
            W::fold_16(&mut temp_state, coeff, yi, ops);

            // XOR with new data
            *xi = temp_state.value;
        }
    }

    // Fold the 8 xmm registers to 1 xmm register with different constants
    let mut res = x[7];

    // Create fold coefficients for different distances
    let fold_coefficients = [
        W::create_coefficient(keys[10], keys[9], state.reflected, ops), // 112 bytes
        W::create_coefficient(keys[12], keys[11], state.reflected, ops), // 96 bytes
        W::create_coefficient(keys[14], keys[13], state.reflected, ops), // 80 bytes
        W::create_coefficient(keys[16], keys[15], state.reflected, ops), // 64 bytes
        W::create_coefficient(keys[18], keys[17], state.reflected, ops), // 48 bytes
        W::create_coefficient(keys[20], keys[19], state.reflected, ops), // 32 bytes
        W::create_coefficient(keys[2], keys[1], state.reflected, ops),  // 16 bytes
    ];

    for (i, &coeff) in fold_coefficients.iter().enumerate() {
        let mut temp_state = CrcState {
            value: x[i],
            reflected: state.reflected,
        };
        W::fold_16(&mut temp_state, coeff, res, ops);

        res = temp_state.value
    }

    // Perform final reduction and update state
    let final_value = W::perform_final_reduction(res, state.reflected, keys, ops);
    *state = W::create_state(final_value, state.reflected, ops);
}

/// Process exactly 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"))]
unsafe fn process_exactly_16<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,
{
    // Process 16 bytes and fold to width-specific size
    W::perform_final_reduction(
        process_16_byte_block(data.as_ptr(), state.value, reflector, ops),
        state.reflected,
        keys,
        ops,
    )
}

/// Process a 16-byte block of data
#[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"))]
unsafe fn process_16_byte_block<T: ArchOps>(
    data_ptr: *const u8,
    initial_crc: T::Vector,
    reflector: &Reflector<T::Vector>,
    ops: &T,
) -> T::Vector
where
    T::Vector: Copy,
{
    // Load data, apply reflection, and XOR with initial CRC
    ops.xor_vectors(
        reflect_bytes(reflector, ops.load_bytes(data_ptr), ops),
        initial_crc,
    )
}

/// Reflect bytes according to the reflector strategy
#[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 reflect_bytes<T: ArchOps>(
    reflector: &Reflector<T::Vector>,
    data: T::Vector,
    ops: &T,
) -> T::Vector
where
    T::Vector: Copy,
{
    match reflector {
        Reflector::NoReflector => data,
        Reflector::ForwardReflector { smask } => ops.shuffle_bytes(data, *smask),
    }
}

/// Fold and XOR generic implementation
#[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"))]
unsafe fn fold_and_xor<T: ArchOps, W: EnhancedCrcWidth>(
    current: T::Vector,
    coefficient: T::Vector,
    data_to_xor: T::Vector,
    reflected: bool,
    ops: &T,
) -> T::Vector
where
    T::Vector: Copy,
{
    // Create a temporary state for folding
    let mut temp_state = CrcState {
        value: current,
        reflected,
    };

    // Fold 16 bytes using width-specific method
    W::fold_16(&mut temp_state, coefficient, data_to_xor, ops);

    temp_state.value
}

/// Process inputs between 17 and 31 bytes
/// This implementation works for both CRC-32 and CRC-64 using the width-specific traits
#[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"))]
unsafe fn process_17_to_31<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,
{
    // Process the first 16 bytes
    let xmm7 = process_16_byte_block(data.as_ptr(), state.value, reflector, ops);

    // Process the remaining bytes (1-15)
    let remaining_len = data.len() - CRC_CHUNK_SIZE;

    // Use the shared function to handle the last two chunks
    let final_xmm7 = get_last_two_xmms::<T, W>(
        DataRegion {
            full_data: data,
            offset: CRC_CHUNK_SIZE,
            remaining: remaining_len,
        },
        xmm7,
        keys,
        reflector,
        state.reflected,
        ops,
    );

    // Perform final reduction
    W::perform_final_reduction(final_xmm7, state.reflected, keys, ops)
}

// Process inputs between 32 and 255 bytes
/// This implementation works for both CRC-32 and CRC-64 using the width-specific traits
#[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"))]
unsafe fn process_32_to_255<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 current_pos = CRC_CHUNK_SIZE;
    let mut remaining_len = data.len() - CRC_CHUNK_SIZE;

    // Process first 16 bytes
    let mut xmm7 = process_16_byte_block(data.as_ptr(), state.value, reflector, ops);

    // Create coefficient for folding operations
    let rk01rk02 = W::create_coefficient(keys[2], keys[1], state.reflected, ops);

    // Main processing loop - 16 bytes at a time
    while remaining_len >= CRC_CHUNK_SIZE {
        // Load next 16 bytes of data
        let next_data = reflect_bytes(
            reflector,
            ops.load_bytes(data.as_ptr().add(current_pos)),
            ops,
        );

        // Fold and XOR
        xmm7 = fold_and_xor::<T, W>(xmm7, rk01rk02, next_data, state.reflected, ops);

        // Update position tracking
        current_pos += CRC_CHUNK_SIZE;
        remaining_len -= CRC_CHUNK_SIZE;
    }

    // Handle remaining bytes (if any)
    if remaining_len > 0 {
        // Use the shared get_last_two_xmms function to handle the remaining bytes
        xmm7 = get_last_two_xmms::<T, W>(
            DataRegion {
                full_data: data,
                offset: current_pos,
                remaining: remaining_len,
            },
            xmm7,
            keys,
            reflector,
            state.reflected,
            ops,
        );
    }

    // Perform final reduction
    W::perform_final_reduction(xmm7, state.reflected, keys, ops)
}

/// Data region descriptor for overlapping SIMD reads in CRC processing
///
/// # Safety Invariants
///
/// When this struct is used with overlapping SIMD reads:
/// - `offset` must be >= `CRC_CHUNK_SIZE` (16 bytes)
/// - `remaining` must be in range 1..=15
/// - `full_data` must contain at least `offset + remaining` bytes
struct DataRegion<'a> {
    full_data: &'a [u8],
    offset: usize,
    remaining: usize,
}

/// Handle the last two chunks of data using an overlapping SIMD read
///
/// # Safety
///
/// - `region.full_data` must contain at least `region.offset + region.remaining` bytes
/// - `region.offset` must be >= `CRC_CHUNK_SIZE` (16 bytes)
/// - `region.remaining` must be in range 1..=15
/// - Caller must ensure appropriate SIMD features are available
#[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"))]
unsafe fn get_last_two_xmms<T: ArchOps, W: EnhancedCrcWidth>(
    region: DataRegion,
    current_state: T::Vector,
    keys: &[u64; 23],
    reflector: &Reflector<T::Vector>,
    reflected: bool,
    ops: &T,
) -> T::Vector
where
    T::Vector: Copy,
{
    debug_assert!(region.offset >= CRC_CHUNK_SIZE);
    debug_assert!(region.remaining > 0 && region.remaining < CRC_CHUNK_SIZE);
    debug_assert!(region.offset + region.remaining <= region.full_data.len());

    let coefficient = W::create_coefficient(keys[2], keys[1], reflected, ops);
    let const_mask = ops.set_all_bytes(0x80);
    let (table_ptr, offset) = W::get_last_bytes_table_ptr(reflected, region.remaining);

    if reflected {
        // Overlapping read: loads tail of previous chunk + remaining data
        let read_offset = region.offset - CRC_CHUNK_SIZE + region.remaining;
        let xmm1 = ops.load_bytes(region.full_data.as_ptr().add(read_offset));
        let mut xmm0 = ops.load_bytes(table_ptr.add(offset));
        let shuffled = ops.shuffle_bytes(current_state, xmm0);
        xmm0 = ops.xor_vectors(xmm0, const_mask);

        let shuffled_masked = ops.shuffle_bytes(current_state, xmm0);

        // CRC-16 and CRC-32 use the same logic (both operate in 32-bit space)
        let (xmm2_blended, mut temp_state) = if W::WIDTH <= 32 {
            let compare_mask = ops.create_compare_mask(xmm0);

            let xmm2_blended = ops.blend_vectors(xmm1, shuffled, compare_mask);

            let temp_state = CrcState {
                value: shuffled_masked,
                reflected,
            };

            (xmm2_blended, temp_state)
        } else {
            let xmm2_blended = ops.blend_vectors(shuffled_masked, xmm1, xmm0);

            let temp_state = CrcState {
                value: shuffled,
                reflected,
            };

            (xmm2_blended, temp_state)
        };

        W::fold_16(&mut temp_state, coefficient, xmm2_blended, ops);

        temp_state.value
    } else {
        let read_offset = region.offset - CRC_CHUNK_SIZE + region.remaining;
        let mut xmm1 = ops.load_bytes(region.full_data.as_ptr().add(read_offset));

        if let Reflector::ForwardReflector { smask } = reflector {
            xmm1 = ops.shuffle_bytes(xmm1, *smask);
        }

        let xmm0 = ops.load_bytes(table_ptr.add(offset));
        let shuffled = ops.shuffle_bytes(current_state, xmm0);
        let xmm0_masked = ops.xor_vectors(xmm0, const_mask);
        let shuffled_masked = ops.shuffle_bytes(current_state, xmm0_masked);
        let xmm2_blended = ops.blend_vectors(xmm1, shuffled, xmm0_masked);

        // Create a temporary state for folding
        let mut temp_state = CrcState {
            value: shuffled_masked,
            reflected,
        };

        W::fold_16(&mut temp_state, coefficient, xmm2_blended, ops);

        temp_state.value
    }
}

`/`	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 contains the main algorithm for CRC calculation.
	4	//!
	5	//! This implementation is designed to work with both CRC-32 and CRC-64 algorithms.
	6	//!
	7	//! It uses SIMD instructions for performance optimization and is designed to be
	8	//! platform-agnostic.
	9	//!
	10	//! The code is structured to allow for easy extension and modification for
	11	//! different architectures and CRC algorithms.
	12	//!
	13	//! The main entry point is the `update` function, which takes the current CRC state,
	14	//! the input data, CRC parameters, and architecture-specific operations.
	15
	16	#![cfg(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64"))]
	17
	18	use crate::consts::CRC_CHUNK_SIZE;
	19	use crate::enums::{DataChunkProcessor, Reflector};
	20	use crate::structs::CrcState;
	21	use crate::traits::{ArchOps, EnhancedCrcWidth};
	22	use crate::{crc16, crc32, crc64, CrcParams};
	23
	24	/// Extract keys from CrcParams using safe accessor methods
	25	/// This ensures bounds checking and future compatibility
	26	#[inline(always)]
	27	fn extract_keys_array(params: &CrcParams) -> [u64; 23] {
	28	[
	29	params.get_key(0),
	30	params.get_key(1),
	31	params.get_key(2),
	32	params.get_key(3),
	33	params.get_key(4),
	34	params.get_key(5),
	35	params.get_key(6),
	36	params.get_key(7),
	37	params.get_key(8),
	38	params.get_key(9),
	39	params.get_key(10),
	40	params.get_key(11),
	41	params.get_key(12),
	42	params.get_key(13),
	43	params.get_key(14),
	44	params.get_key(15),
	45	params.get_key(16),
	46	params.get_key(17),
	47	params.get_key(18),
	48	params.get_key(19),
	49	params.get_key(20),
	50	params.get_key(21),
	51	params.get_key(22),
	52	]
	53	}
	54
	55	/// Main entry point that works for both CRC-32 and CRC-64
	56	#[inline(always)]
	57	pub unsafe fn update<T: ArchOps, W: EnhancedCrcWidth>(
	58	state: W::Value,
	59	bytes: &[u8],
	60	params: &CrcParams,
	61	ops: &T,
	62	) -> W::Value
	63	where
	64	T::Vector: Copy,
65	{
66	let len = bytes.len();
67	if len == 0 {
68	return state;
69	}
70
71	// Create the appropriate reflector based on CRC type
72	let reflector = if params.refin {
73	Reflector::NoReflector
74	} else {
75	// Load mask for byte-swapping operations
76	let smask = ops.load_aligned(&W::load_constants(params.refin)[0] as *const [u64; 2]);
77	Reflector::ForwardReflector { smask }
78	};
79
80	// Create initial CRC state
81	let mut crc_state = W::create_state(state, params.refin, ops);
82
83	// Extract keys once and pass by reference to avoid repeated stack copies
84	let keys = extract_keys_array(params);
85
86	// Process data differently based on length
87	// On ARM M4 Max, ARM c8g, x86 c7a, and x86 c7i, using 128 bytes is a measurably faster
88	// threshold than 256 bytes...
89	if len < 128 {
90	// Select processor based on input length
91	let processor = DataChunkProcessor::for_length(len);
92	return process_by_strategy::<T, W>(
93	processor,
94	bytes,
95	&mut crc_state,
96	reflector,
97	&keys,
98	ops,
99	);
100	}
101
102	// Process large inputs with SIMD-optimized approach
103	process_large_aligned::<T, W>(bytes, &mut crc_state, reflector, &keys, ops)
104	}
105
106	/// Process data with the selected strategy
107	#[inline]
108	#[cfg_attr(
109	any(target_arch = "x86", target_arch = "x86_64"),
110	target_feature(enable = "ssse3,sse4.1,pclmulqdq")
111	)]
112	#[cfg_attr(target_arch = "aarch64", target_feature(enable = "aes"))]
113	unsafe fn process_by_strategy<T: ArchOps, W: EnhancedCrcWidth>(
114	strategy: DataChunkProcessor,
115	data: &[u8],
116	state: &mut CrcState<T::Vector>,
117	reflector: Reflector<T::Vector>,
118	keys: &[u64; 23],
119	ops: &T,
120	) -> W::Value
121	where
122	T::Vector: Copy,
123	{
124	match strategy {
125	DataChunkProcessor::From0To15 => match W::WIDTH {
126	16 => crc16::algorithm::process_0_to_15::<T, W>(data, state, &reflector, keys, ops),
127	32 => crc32::algorithm::process_0_to_15::<T, W>(data, state, &reflector, keys, ops),
128	64 => crc64::algorithm::process_0_to_15::<T, W>(data, state, &reflector, keys, ops),
129	_ => panic!("Unsupported CRC width"),
130	},
131	DataChunkProcessor::From16 => {
132	process_exactly_16::<T, W>(data, state, &reflector, keys, ops)
133	}
134	DataChunkProcessor::From17To31 => {
135	process_17_to_31::<T, W>(data, state, &reflector, keys, ops)
136	}
137	DataChunkProcessor::From32To255 => {
138	process_32_to_255::<T, W>(data, state, &reflector, keys, ops)
139	}
140	}
141	}
142
143	/// Process large inputs with proper SIMD alignment
144	#[inline]
145	#[cfg_attr(
146	any(target_arch = "x86", target_arch = "x86_64"),
147	target_feature(enable = "ssse3,sse4.1,pclmulqdq")
148	)]
149	#[cfg_attr(target_arch = "aarch64", target_feature(enable = "aes"))]
150	unsafe fn process_large_aligned<T: ArchOps, W: EnhancedCrcWidth>(
151	bytes: &[u8],
152	state: &mut CrcState<T::Vector>,
153	reflector: Reflector<T::Vector>,
154	keys: &[u64; 23],
155	ops: &T,
156	) -> W::Value
157	where
158	T::Vector: Copy,
159	{
160	// Align data for SIMD processing
161	let (left, middle, right) = bytes.align_to::<[T::Vector; 8]>();
162
163	if let Some((first, rest)) = middle.split_first() {
164	if !left.is_empty() {
165	let processor = DataChunkProcessor::for_length(left.len());
166	// Process unaligned bytes at the start
167	let left_crc =
168	process_by_strategy::<T, W>(processor, left, state, reflector, keys, ops);
169	// Update state with the result from processing left bytes
170	*state = W::create_state(left_crc, state.reflected, ops);
171	}
172
173	// try to use the enhanced SIMD implementation first, fall back to non-enhanced if necessary
174	if rest.is_empty()
175	\|\| !ops.process_enhanced_simd_blocks::<W>(state, first, rest, &reflector, keys)
176	{
177	process_simd_chunks::<T, W>(state, first, rest, &reflector, keys, ops);
178	}
179
180	// Process any unaligned bytes at the end
181	if !right.is_empty() {
182	let processor = DataChunkProcessor::for_length(right.len());
183	// Use the current state to process the right bytes
184	return process_by_strategy::<T, W>(processor, right, state, reflector, keys, ops);
185	}
186
187	// Extract the final result
188	return W::extract_result(state.value, state.reflected, ops);
189	}
190
191	// Fall back to existing implementation if proper alignment isn't possible
192	let processor = DataChunkProcessor::for_length(bytes.len());
193	process_by_strategy::<T, W>(processor, bytes, state, reflector, keys, ops)
194	}
195
196	/// Process SIMD-aligned chunks of 128 bytes
197	#[inline]
198	#[cfg_attr(
199	any(target_arch = "x86", target_arch = "x86_64"),
200	target_feature(enable = "ssse3,sse4.1,pclmulqdq")
201	)]
202	#[cfg_attr(target_arch = "aarch64", target_feature(enable = "aes"))]
203	unsafe fn process_simd_chunks<T: ArchOps, W: EnhancedCrcWidth>(
204	state: &mut CrcState<T::Vector>,
205	first: &[T::Vector; 8],
206	rest: &[[T::Vector; 8]],
207	reflector: &Reflector<T::Vector>,
208	keys: &[u64; 23],
209	ops: &T,
210	) where
211	T::Vector: Copy,
212	{
213	// Create a copy of the first 128 bytes
214	let mut x = *first;
215
216	// Apply initial reflection if needed
217	for item in &mut x {
218	item = reflect_bytes(reflector, item, ops);
219	}
220
221	// XOR initial CRC with the first 16 bytes
222	x[0] = ops.xor_vectors(x[0], state.value);
223
224	// Load the coefficient pair for folding
225	let coeff = W::create_coefficient(keys[4], keys[3], state.reflected, ops);
226
227	// Process remaining 128-byte chunks
228	for chunk in rest {
229	for (xi, yi) in x.iter_mut().zip(chunk.iter()) {
230	// Load and reflect the new data if needed
231	let yi = reflect_bytes(reflector, *yi, ops);
232
233	// Create a temporary state for folding
234	let mut temp_state = CrcState {
235	value: *xi,
236	reflected: state.reflected,
237	};
238
239	// Fold 16 bytes
240	W::fold_16(&mut temp_state, coeff, yi, ops);
241
242	// XOR with new data
243	*xi = temp_state.value;
244	}
245	}
246
247	// Fold the 8 xmm registers to 1 xmm register with different constants
248	let mut res = x[7];
249
250	// Create fold coefficients for different distances
251	let fold_coefficients = [
252	W::create_coefficient(keys[10], keys[9], state.reflected, ops), // 112 bytes
253	W::create_coefficient(keys[12], keys[11], state.reflected, ops), // 96 bytes
254	W::create_coefficient(keys[14], keys[13], state.reflected, ops), // 80 bytes
255	W::create_coefficient(keys[16], keys[15], state.reflected, ops), // 64 bytes
256	W::create_coefficient(keys[18], keys[17], state.reflected, ops), // 48 bytes
257	W::create_coefficient(keys[20], keys[19], state.reflected, ops), // 32 bytes
258	W::create_coefficient(keys[2], keys[1], state.reflected, ops), // 16 bytes
259	];
260
261	for (i, &coeff) in fold_coefficients.iter().enumerate() {
262	let mut temp_state = CrcState {
263	value: x[i],
264	reflected: state.reflected,
265	};
266	W::fold_16(&mut temp_state, coeff, res, ops);
267
268	res = temp_state.value
269	}
270
271	// Perform final reduction and update state
272	let final_value = W::perform_final_reduction(res, state.reflected, keys, ops);
273	*state = W::create_state(final_value, state.reflected, ops);
274	}
275
276	/// Process exactly 16 bytes
277	#[inline]
278	#[cfg_attr(
279	any(target_arch = "x86", target_arch = "x86_64"),
280	target_feature(enable = "ssse3,sse4.1,pclmulqdq")
281	)]
282	#[cfg_attr(target_arch = "aarch64", target_feature(enable = "aes"))]
283	unsafe fn process_exactly_16<T: ArchOps, W: EnhancedCrcWidth>(
284	data: &[u8],
285	state: &mut CrcState<T::Vector>,
286	reflector: &Reflector<T::Vector>,
287	keys: &[u64; 23],
288	ops: &T,
289	) -> W::Value
290	where
291	T::Vector: Copy,
292	{
293	// Process 16 bytes and fold to width-specific size
294	W::perform_final_reduction(
295	process_16_byte_block(data.as_ptr(), state.value, reflector, ops),
296	state.reflected,
297	keys,
298	ops,
299	)
300	}
301
302	/// Process a 16-byte block of data
303	#[inline]
304	#[cfg_attr(
305	any(target_arch = "x86", target_arch = "x86_64"),
306	target_feature(enable = "ssse3,sse4.1,pclmulqdq")
307	)]
308	#[cfg_attr(target_arch = "aarch64", target_feature(enable = "aes"))]
309	unsafe fn process_16_byte_block<T: ArchOps>(
310	data_ptr: *const u8,
311	initial_crc: T::Vector,
312	reflector: &Reflector<T::Vector>,
313	ops: &T,
314	) -> T::Vector
315	where
316	T::Vector: Copy,
317	{
318	// Load data, apply reflection, and XOR with initial CRC
319	ops.xor_vectors(
320	reflect_bytes(reflector, ops.load_bytes(data_ptr), ops),
321	initial_crc,
322	)
323	}
324
325	/// Reflect bytes according to the reflector strategy
326	#[inline]
327	#[cfg_attr(
328	any(target_arch = "x86", target_arch = "x86_64"),
329	target_feature(enable = "ssse3,sse4.1,pclmulqdq")
330	)]
331	#[cfg_attr(target_arch = "aarch64", target_feature(enable = "aes"))]
332	pub(crate) unsafe fn reflect_bytes<T: ArchOps>(
333	reflector: &Reflector<T::Vector>,
334	data: T::Vector,
335	ops: &T,
336	) -> T::Vector
337	where
338	T::Vector: Copy,
339	{
340	match reflector {
341	Reflector::NoReflector => data,
342	Reflector::ForwardReflector { smask } => ops.shuffle_bytes(data, *smask),
343	}
344	}
345
346	/// Fold and XOR generic implementation
347	#[inline]
348	#[cfg_attr(
349	any(target_arch = "x86", target_arch = "x86_64"),
350	target_feature(enable = "ssse3,sse4.1,pclmulqdq")
351	)]
352	#[cfg_attr(target_arch = "aarch64", target_feature(enable = "aes"))]
353	unsafe fn fold_and_xor<T: ArchOps, W: EnhancedCrcWidth>(
354	current: T::Vector,
355	coefficient: T::Vector,
356	data_to_xor: T::Vector,
357	reflected: bool,
358	ops: &T,
359	) -> T::Vector
360	where
361	T::Vector: Copy,
362	{
363	// Create a temporary state for folding
364	let mut temp_state = CrcState {
365	value: current,
366	reflected,
367	};
368
369	// Fold 16 bytes using width-specific method
370	W::fold_16(&mut temp_state, coefficient, data_to_xor, ops);
371
372	temp_state.value
373	}
374
375	/// Process inputs between 17 and 31 bytes
376	/// This implementation works for both CRC-32 and CRC-64 using the width-specific traits
377	#[inline]
378	#[cfg_attr(
379	any(target_arch = "x86", target_arch = "x86_64"),
380	target_feature(enable = "ssse3,sse4.1,pclmulqdq")
381	)]
382	#[cfg_attr(target_arch = "aarch64", target_feature(enable = "aes"))]
383	unsafe fn process_17_to_31<T: ArchOps, W: EnhancedCrcWidth>(
384	data: &[u8],
385	state: &mut CrcState<T::Vector>,
386	reflector: &Reflector<T::Vector>,
387	keys: &[u64; 23],
388	ops: &T,
389	) -> W::Value
390	where
391	T::Vector: Copy,
392	{
393	// Process the first 16 bytes
394	let xmm7 = process_16_byte_block(data.as_ptr(), state.value, reflector, ops);
395
396	// Process the remaining bytes (1-15)
397	let remaining_len = data.len() - CRC_CHUNK_SIZE;
398
399	// Use the shared function to handle the last two chunks
400	let final_xmm7 = get_last_two_xmms::<T, W>(
401	DataRegion {
402	full_data: data,
403	offset: CRC_CHUNK_SIZE,
404	remaining: remaining_len,
405	},
406	xmm7,
407	keys,
408	reflector,
409	state.reflected,
410	ops,
411	);
412
413	// Perform final reduction
414	W::perform_final_reduction(final_xmm7, state.reflected, keys, ops)
415	}
416
417	// Process inputs between 32 and 255 bytes
418	/// This implementation works for both CRC-32 and CRC-64 using the width-specific traits
419	#[inline]
420	#[cfg_attr(
421	any(target_arch = "x86", target_arch = "x86_64"),
422	target_feature(enable = "ssse3,sse4.1,pclmulqdq")
423	)]
424	#[cfg_attr(target_arch = "aarch64", target_feature(enable = "aes"))]
425	unsafe fn process_32_to_255<T: ArchOps, W: EnhancedCrcWidth>(
426	data: &[u8],
427	state: &mut CrcState<T::Vector>,
428	reflector: &Reflector<T::Vector>,
429	keys: &[u64; 23],
430	ops: &T,
431	) -> W::Value
432	where
433	T::Vector: Copy,
434	{
435	let mut current_pos = CRC_CHUNK_SIZE;
436	let mut remaining_len = data.len() - CRC_CHUNK_SIZE;
437
438	// Process first 16 bytes
439	let mut xmm7 = process_16_byte_block(data.as_ptr(), state.value, reflector, ops);
440
441	// Create coefficient for folding operations
442	let rk01rk02 = W::create_coefficient(keys[2], keys[1], state.reflected, ops);
443
444	// Main processing loop - 16 bytes at a time
445	while remaining_len >= CRC_CHUNK_SIZE {
446	// Load next 16 bytes of data
447	let next_data = reflect_bytes(
448	reflector,
449	ops.load_bytes(data.as_ptr().add(current_pos)),
450	ops,
451	);
452
453	// Fold and XOR
454	xmm7 = fold_and_xor::<T, W>(xmm7, rk01rk02, next_data, state.reflected, ops);
455
456	// Update position tracking
457	current_pos += CRC_CHUNK_SIZE;
458	remaining_len -= CRC_CHUNK_SIZE;
459	}
460
461	// Handle remaining bytes (if any)
462	if remaining_len > 0 {
463	// Use the shared get_last_two_xmms function to handle the remaining bytes
464	xmm7 = get_last_two_xmms::<T, W>(
465	DataRegion {
466	full_data: data,
467	offset: current_pos,
468	remaining: remaining_len,
469	},
470	xmm7,
471	keys,
472	reflector,
473	state.reflected,
474	ops,
475	);
476	}
477
478	// Perform final reduction
479	W::perform_final_reduction(xmm7, state.reflected, keys, ops)
480	}
481
482	/// Data region descriptor for overlapping SIMD reads in CRC processing
483	///
484	/// # Safety Invariants
485	///
486	/// When this struct is used with overlapping SIMD reads:
487	/// - `offset` must be >= `CRC_CHUNK_SIZE` (16 bytes)
488	/// - `remaining` must be in range 1..=15
489	/// - `full_data` must contain at least `offset + remaining` bytes
490	struct DataRegion<'a> {
491	full_data: &'a [u8],
492	offset: usize,
493	remaining: usize,
494	}
495
496	/// Handle the last two chunks of data using an overlapping SIMD read
497	///
498	/// # Safety
499	///
500	/// - `region.full_data` must contain at least `region.offset + region.remaining` bytes
501	/// - `region.offset` must be >= `CRC_CHUNK_SIZE` (16 bytes)
502	/// - `region.remaining` must be in range 1..=15
503	/// - Caller must ensure appropriate SIMD features are available
504	#[inline]
505	#[cfg_attr(
506	any(target_arch = "x86", target_arch = "x86_64"),
507	target_feature(enable = "ssse3,sse4.1,pclmulqdq")
508	)]
509	#[cfg_attr(target_arch = "aarch64", target_feature(enable = "aes"))]
510	unsafe fn get_last_two_xmms<T: ArchOps, W: EnhancedCrcWidth>(
511	region: DataRegion,
512	current_state: T::Vector,
513	keys: &[u64; 23],
514	reflector: &Reflector<T::Vector>,
515	reflected: bool,
516	ops: &T,
517	) -> T::Vector
518	where
519	T::Vector: Copy,
520	{
521	debug_assert!(region.offset >= CRC_CHUNK_SIZE);
522	debug_assert!(region.remaining > 0 && region.remaining < CRC_CHUNK_SIZE);
523	debug_assert!(region.offset + region.remaining <= region.full_data.len());
524
525	let coefficient = W::create_coefficient(keys[2], keys[1], reflected, ops);
526	let const_mask = ops.set_all_bytes(0x80);
527	let (table_ptr, offset) = W::get_last_bytes_table_ptr(reflected, region.remaining);
528
529	if reflected {
530	// Overlapping read: loads tail of previous chunk + remaining data
531	let read_offset = region.offset - CRC_CHUNK_SIZE + region.remaining;
532	let xmm1 = ops.load_bytes(region.full_data.as_ptr().add(read_offset));
533	let mut xmm0 = ops.load_bytes(table_ptr.add(offset));
534	let shuffled = ops.shuffle_bytes(current_state, xmm0);
535	xmm0 = ops.xor_vectors(xmm0, const_mask);
536
537	let shuffled_masked = ops.shuffle_bytes(current_state, xmm0);
538
539	// CRC-16 and CRC-32 use the same logic (both operate in 32-bit space)
540	let (xmm2_blended, mut temp_state) = if W::WIDTH <= 32 {
541	let compare_mask = ops.create_compare_mask(xmm0);
542
543	let xmm2_blended = ops.blend_vectors(xmm1, shuffled, compare_mask);
544
545	let temp_state = CrcState {
546	value: shuffled_masked,
547	reflected,
548	};
549
550	(xmm2_blended, temp_state)
551	} else {
552	let xmm2_blended = ops.blend_vectors(shuffled_masked, xmm1, xmm0);
553
554	let temp_state = CrcState {
555	value: shuffled,
556	reflected,
557	};
558
559	(xmm2_blended, temp_state)
560	};
561
562	W::fold_16(&mut temp_state, coefficient, xmm2_blended, ops);
563
564	temp_state.value
565	} else {
566	let read_offset = region.offset - CRC_CHUNK_SIZE + region.remaining;
567	let mut xmm1 = ops.load_bytes(region.full_data.as_ptr().add(read_offset));
568
569	if let Reflector::ForwardReflector { smask } = reflector {
570	xmm1 = ops.shuffle_bytes(xmm1, *smask);
571	}
572
573	let xmm0 = ops.load_bytes(table_ptr.add(offset));
574	let shuffled = ops.shuffle_bytes(current_state, xmm0);
575	let xmm0_masked = ops.xor_vectors(xmm0, const_mask);
576	let shuffled_masked = ops.shuffle_bytes(current_state, xmm0_masked);
577	let xmm2_blended = ops.blend_vectors(xmm1, shuffled, xmm0_masked);
578
579	// Create a temporary state for folding
580	let mut temp_state = CrcState {
581	value: shuffled_masked,
582	reflected,
583	};
584
585	W::fold_16(&mut temp_state, coefficient, xmm2_blended, ops);
586
587	temp_state.value
588	}
589	}

Keyboard