# 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:

```rust

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

```rust

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:

```rust

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:

```rust

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.