Design Document: CRC Width-32 Shared Base

Overview

This design refactors the CRC-16 and CRC-32 algorithm implementations to share a common base module. Since CRC-16 operates in 32-bit space (scaling 16-bit values up for processing, then down for results), both widths use nearly identical SIMD operations. By extracting this shared logic into src/crc32/width32_ops.rs, we eliminate ~200 lines of duplicated code and prepare the codebase for future CRC width additions.

Architecture

Current Structure

src/
├── crc16/
│   ├── algorithm.rs    # Width16 impl + process_0_to_15 (duplicated)
│   ├── consts.rs
│   └── mod.rs
├── crc32/
│   ├── algorithm.rs    # Width32 impl + process_0_to_15 (duplicated)
│   ├── consts.rs
│   └── mod.rs
├── crc64/
│   ├── algorithm.rs    # Width64 impl + process_0_to_15 (unique)
│   ├── consts.rs
│   └── mod.rs
└── algorithm.rs        # Shared algorithm infrastructure

Proposed Structure

src/
├── crc16/
│   ├── algorithm.rs    # Width16 impl (delegates to width32_ops)
│   ├── consts.rs
│   └── mod.rs
├── crc32/
│   ├── algorithm.rs    # Width32 impl (delegates to width32_ops)
│   ├── consts.rs
│   ├── mod.rs
│   └── width32_ops.rs  # NEW: Shared 32-bit-space operations
├── crc64/
│   ├── algorithm.rs    # Width64 impl + process_0_to_15 (unchanged)
│   ├── consts.rs
│   └── mod.rs
└── algorithm.rs        # Shared algorithm infrastructure

Components and Interfaces

1. New Module: src/crc32/width32_ops.rs

This module contains all shared 32-bit-space operations:

//! 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.

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 shared by CRC-16 and CRC-32
pub const WIDTH32_CONSTANTS_REFLECTED: [[u64; 2]; 4] = [
    [0x08090a0b0c0d0e0f, 0x0001020304050607], // smask
    [0x8080808080808080, 0x8080808080808080], // mask1
    [0xFFFFFFFF00000000, 0xFFFFFFFFFFFFFFFF], // mask2 reverse
    [0x0000000000000000, 0x0000000000000000], // unused
];

pub const WIDTH32_CONSTANTS_FORWARD: [[u64; 2]; 4] = [
    [0x08090a0b0c0d0e0f, 0x0001020304050607], // smask
    [0x8080808080808080, 0x8080808080808080], // mask1
    [0xffffffffffffffff, 0x00000000ffffffff], // mask2 forward
    [0x0000000000000000, 0x0000000000000000], // unused
];

/// Load 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
#[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
#[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
/// Returns the full u64 result; caller extracts appropriate bits
#[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
#[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
#[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)
    }
}

/// Process inputs smaller than 16 bytes for 32-bit-space CRC operations
#[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,
{
    // Implementation shared by CRC-16 and CRC-32
    // ... (full implementation)
}

2. Updated src/crc16/algorithm.rs

The Width16 implementation delegates to shared operations:

impl EnhancedCrcWidth for Width16 {
    #[inline(always)]
    fn load_constants(reflected: bool) -> [[u64; 2]; 4] {
        crate::crc32::width32_ops::load_constants(reflected)
    }

    #[inline(always)]
    unsafe fn fold_16<T: ArchOps>(...) {
        crate::crc32::width32_ops::fold_16(state, coeff, data_to_xor, ops)
    }

    #[inline(always)]
    unsafe fn barrett_reduction<T: ArchOps>(...) -> Self::Value {
        let u64s = crate::crc32::width32_ops::barrett_reduction(state, poly, mu, ops);
        // Extract 16-bit result
        if state.reflected {
            u64s[1] as u16
        } else {
            ((u64s[0] >> 32) >> 16) as u16
        }
    }
    
    // ... other delegating methods
}

// process_0_to_15 delegates to shared implementation
pub(crate) unsafe fn process_0_to_15<T: ArchOps, W: EnhancedCrcWidth>(...) -> W::Value {
    crate::crc32::width32_ops::process_0_to_15::<T, W>(data, state, reflector, keys, ops)
}

3. Updated src/crc32/algorithm.rs

The Width32 implementation also delegates to shared operations:

impl EnhancedCrcWidth for Width32 {
    #[inline(always)]
    fn load_constants(reflected: bool) -> [[u64; 2]; 4] {
        crate::crc32::width32_ops::load_constants(reflected)
    }

    #[inline(always)]
    unsafe fn barrett_reduction<T: ArchOps>(...) -> Self::Value {
        let u64s = crate::crc32::width32_ops::barrett_reduction(state, poly, mu, ops);
        // Extract 32-bit result
        if state.reflected {
            u64s[1] as u32
        } else {
            (u64s[0] >> 32) as u32
        }
    }
    
    // ... other delegating methods
}

// process_0_to_15 delegates to shared implementation
pub(crate) unsafe fn process_0_to_15<T: ArchOps, W: EnhancedCrcWidth>(...) -> W::Value {
    crate::crc32::width32_ops::process_0_to_15::<T, W>(data, state, reflector, keys, ops)
}

4. Updated src/crc32/mod.rs

Export the new module:

pub mod algorithm;
pub mod consts;
pub(crate) mod width32_ops;  // NEW

Data Models

No changes to data models. The refactoring only affects internal implementation.

Correctness Properties

A property is a characteristic or behavior that should hold true across all valid executions of a system.

Property 1: CRC-16 Computation Unchanged

For any input byte sequence and any CRC-16 parameters, the computed checksum after refactoring SHALL equal the checksum computed before refactoring.

Validates: Requirements 4.1

Property 2: CRC-32 Computation Unchanged

For any input byte sequence and any CRC-32 parameters, the computed checksum after refactoring SHALL equal the checksum computed before refactoring.

Validates: Requirements 4.2

Property 3: CRC-64 Computation Unchanged

For any input byte sequence and any CRC-64 parameters, the computed checksum after refactoring SHALL equal the checksum computed before refactoring.

Validates: Requirements 4.3

Error Handling

No changes to error handling. The refactoring is purely internal.

Testing Strategy

Existing Tests

All existing tests serve as regression tests:

• CRC-16 check value tests (0x906E, 0xD0DB)
• CRC-32 check value tests
• CRC-64 check value tests
• Property-based tests comparing against crc crate
• Length-based tests for various input sizes

Verification Approach

1. Run cargo test before refactoring to establish baseline
2. Perform refactoring
3. Run cargo test after refactoring to verify no regressions
4. Run cargo fmt --check and cargo clippy -- -D warnings

No new tests are needed since this is a pure refactoring with no behavior changes.