Requirements Document

Introduction

This feature adds hardware-accelerated CRC-16 calculation support to the crc-fast library, which already has working hardware-accelerated CRC-32 and CRC-64 implementations. The implementation will leverage PCLMULQDQ/PMULL SIMD instructions for high-performance CRC-16 computation, supporting any CRC-16 variant (both forward/non-reflected and reflected). While CRC-16/IBM-SDLC and CRC-16/T10-DIF serve as reference variants for initial validation, the final implementation must support custom CRC-16 variants with arbitrary polynomials, just like the existing CRC-32 and CRC-64 support. The feature must maintain full backwards compatibility with existing CRC-32 and CRC-64 functionality.

Glossary

• CRC-16: A 16-bit Cyclic Redundancy Check algorithm used for error detection
• Key_Generator: The module responsible for generating PCLMULQDQ folding keys from CRC polynomials
• Folding_Keys: Precomputed constants (x^n mod P(x)) used for parallel CRC computation via PCLMULQDQ
• PCLMULQDQ: Intel's carryless multiplication instruction used for hardware-accelerated CRC computation
• PMULL: ARM's polynomial multiplication instruction, equivalent to PCLMULQDQ
• Forward_CRC: A CRC variant where data is processed MSB-first (refin=false)
• Reflected_CRC: A CRC variant where data is processed LSB-first (refin=true)
• CRC-16/T10-DIF: A forward (non-reflected) CRC-16 variant with polynomial 0x8BB7
• CRC-16/IBM-SDLC: A reflected CRC-16 variant with polynomial 0x1021
• Barrett_Reduction: An algorithm for fast modular reduction without division, used in final CRC computation
• Mu_Constant: The Barrett reduction constant (μ = floor(x^64/P(x))) used for final reduction
• Algorithm_Module: The SIMD-based CRC calculation module that processes data using folding keys
• Check_Value: The expected CRC result for the industry standard test string "123456789"
• 256-Byte_Folding_Keys: Extended folding keys (indices 21-22) for AVX-512 VPCLMULQDQ 256-byte chunk processing

Requirements

Requirement 1: CRC-16 Key Generation

User Story: As a library maintainer, I want the key generator to produce correct CRC-16 folding keys for any CRC-16 polynomial, so that hardware-accelerated CRC-16 computation produces correct results for all variants.

Acceptance Criteria

1. WHEN the Key_Generator receives a 16-bit polynomial and forward reflection mode, THE Key_Generator SHALL produce folding keys that match the reference values in KEYS_8BB7_FORWARD for CRC-16/T10-DIF
2. WHEN the Key_Generator receives a 16-bit polynomial and reflected mode, THE Key_Generator SHALL produce folding keys that match the reference values in KEYS_1021_REVERSE for CRC-16/IBM-SDLC
3. WHEN generating CRC-16 keys for any 16-bit polynomial, THE Key_Generator SHALL use exponents based on 32-bit distances (32*N) matching the CRC-32 exponent pattern
4. WHEN generating the Mu_Constant for any CRC-16 polynomial, THE Key_Generator SHALL compute floor(x^64/P(x)) where P(x) is the 17-bit polynomial (16-bit poly with implicit leading 1)
5. WHEN generating the polynomial key for any forward CRC-16, THE Key_Generator SHALL shift the polynomial left by 16 bits and set bit 32
6. WHEN generating the polynomial key for any reflected CRC-16, THE Key_Generator SHALL bit-reverse the 16-bit polynomial, shift left by 1, and set the LSB
7. WHEN generating 256-byte folding keys (indices 21-22) for any CRC-16 polynomial, THE Key_Generator SHALL compute keys for distances 3263 and 3265 bits

Requirement 2: CRC-16 Algorithm Implementation

User Story: As a developer, I want to compute CRC-16 checksums using hardware acceleration for any CRC-16 variant, so that I can achieve high-performance CRC-16 calculations.

Acceptance Criteria

1. WHEN computing CRC-16 for the industry standard string "123456789", THE Algorithm_Module SHALL produce the Check_Value 0x906E for CRC-16/IBM-SDLC
2. WHEN computing CRC-16 for the industry standard string "123456789", THE Algorithm_Module SHALL produce the Check_Value 0xD0DB for CRC-16/T10-DIF
3. WHEN processing data for any forward CRC-16 variant, THE Algorithm_Module SHALL byte-reflect input data using pshufb before folding operations
4. WHEN processing data for any reflected CRC-16 variant, THE Algorithm_Module SHALL process input data without byte reflection
5. WHEN performing the final Barrett reduction for any CRC-16 variant, THE Algorithm_Module SHALL extract the 16-bit result from the appropriate register position
6. WHEN the initial CRC value is provided for any forward CRC-16 variant, THE Algorithm_Module SHALL scale it to 32 bits by shifting left 16 bits before processing
7. WHEN the final CRC is computed for any forward CRC-16 variant, THE Algorithm_Module SHALL scale the result back to 16 bits by shifting right 16 bits

Requirement 3: Backwards Compatibility

User Story: As an existing library user, I want CRC-32 and CRC-64 functionality to remain unchanged, so that my existing code continues to work correctly.

Acceptance Criteria

1. WHEN computing CRC-32 checksums after CRC-16 support is added, THE Algorithm_Module SHALL produce identical results to the current implementation
2. WHEN computing CRC-64 checksums after CRC-16 support is added, THE Algorithm_Module SHALL produce identical results to the current implementation
3. WHEN using the existing public API functions (checksum, Digest, checksum_combine), THE API SHALL maintain the same function signatures and behavior
4. WHEN generating CRC-32 or CRC-64 keys, THE Key_Generator SHALL produce identical keys to the current implementation

Requirement 4: Test Coverage

User Story: As a library maintainer, I want comprehensive tests for CRC-16 functionality, so that I can ensure correctness and prevent regressions.

Acceptance Criteria

1. WHEN testing CRC-16 key generation, THE Test_Suite SHALL verify generated keys match the known good reference values from the reference implementation
2. WHEN testing CRC-16 computation, THE Test_Suite SHALL verify the Check_Value for the industry standard "123456789" string for both CRC-16/IBM-SDLC and CRC-16/T10-DIF
3. WHEN testing CRC-16 computation, THE Test_Suite SHALL compare results against the crc crate reference implementation for various input sizes
4. WHEN testing backwards compatibility, THE Test_Suite SHALL verify all existing CRC-32 and CRC-64 tests continue to pass

Requirement 5: CRC-16 Constants and Parameters

User Story: As a library maintainer, I want properly defined CRC-16 constants and parameters, so that the implementation is consistent with industry standards and supports custom variants.

Acceptance Criteria

1. THE CRC-16 module SHALL define CRC16_IBM_SDLC with polynomial 0x1021, init 0xFFFF, refin=true, refout=true, xorout=0xFFFF, check=0x906E
2. THE CRC-16 module SHALL define CRC16_T10_DIF with polynomial 0x8BB7, init 0x0000, refin=false, refout=false, xorout=0x0000, check=0xD0DB
3. WHEN storing CRC-16 parameters, THE CrcParams structure SHALL use width=16 to distinguish from CRC-32 and CRC-64 variants
4. THE CRC-16 module SHALL include SIMD constants (smask, mask1, mask2) appropriate for 16-bit CRC computation
5. WHEN creating custom CRC-16 parameters via CrcParams::new(), THE Key_Generator SHALL dynamically generate folding keys for the provided polynomial

Requirement 6: Custom CRC-16 Variant Support

User Story: As a developer, I want to use custom CRC-16 parameters with any polynomial, so that I can compute CRC-16 checksums for non-standard variants.

Acceptance Criteria

1. WHEN CrcParams::new() is called with width=16 and any valid polynomial, THE system SHALL generate correct folding keys for that polynomial
2. WHEN checksum_with_params() is called with custom CRC-16 parameters, THE Algorithm_Module SHALL compute the correct CRC-16 checksum
3. WHEN Digest::new_with_params() is called with custom CRC-16 parameters, THE Digest SHALL correctly accumulate and finalize CRC-16 checksums
4. WHEN checksum_combine_with_params() is called with custom CRC-16 parameters, THE system SHALL correctly combine two CRC-16 checksums