OXYGENHUB
# f2f91ceb0e9f oxygen / vendor / crc-fast / .kiro / specs / crc16-hardware-acceleration / tasks.md
5.6 KiB · Markdown · last changed Strata: the cloud stores send through ureq, so every release target links 1 month ago renderedsource blame history raw
1 
# Implementation Plan: CRC-16 Hardware Acceleration
2
3 
## Overview
4
5 
This implementation adds hardware-accelerated CRC-16 support to the crc-fast library in two phases: first extending the key generator, then extending the algorithm module. The implementation leverages the existing CRC-32 infrastructure by scaling CRC-16 values to 32-bit space.
6
7 
## Tasks
8
9 
- [x] 1. Extend Key Generator for CRC-16
10 
  - [x] 1.1 Add CRC-16 exponents constant and update keys() function
11 
    - Add `CRC16_EXPONENTS` constant (same as CRC32_EXPONENTS)
12 
    - Update `keys()` function to handle width=16
13 
    - Update `key()` function to dispatch to `crc16_key()`
14 
    - _Requirements: 1.3_
15
16 
  - [x] 1.2 Implement crc16_key() function
17 
    - Compute x^exponent mod P(x) for 17-bit CRC-16 polynomial
18 
    - Handle both forward and reflected modes
19 
    - Follow the pattern from reference/crc16f/crc16fg.cpp and reference/crc16r/crc16rg.cpp
20 
    - _Requirements: 1.1, 1.2, 1.7_
21
22 
  - [x] 1.3 Implement crc16_mu() function
23 
    - Compute Barrett reduction constant floor(x^64/P(x))
24 
    - Handle both forward and reflected modes
25 
    - _Requirements: 1.4_
26
27 
  - [x] 1.4 Implement crc16_polynomial() function
28 
    - Format polynomial for forward mode: (poly << 16) | (1 << 32)
29 
    - Format polynomial for reflected mode: (bit_reverse_16(poly) << 1) | 1
30 
    - _Requirements: 1.5, 1.6_
31
32 
  - [x] 1.5 Write property tests for CRC-16 key generation
33 
    - **Property 1: Forward polynomial formatting**
34 
    - **Property 2: Reflected polynomial formatting**
35 
    - **Validates: Requirements 1.5, 1.6**
36
37 
  - [x] 1.6 Add unit tests for CRC-16 key generation
38 
    - Test generated keys match KEYS_8BB7_FORWARD for CRC-16/T10-DIF
39 
    - Test generated keys match KEYS_1021_REVERSE for CRC-16/IBM-SDLC
40 
    - Add CRC-16 test configs to TEST_ALL_CONFIGS
41 
    - _Requirements: 1.1, 1.2, 4.1_
42
43 
- [x] 2. Checkpoint - Verify key generation
44 
  - Ensure all tests pass, ask the user if questions arise.
45
46 
- [x] 3. Update CRC-16 Constants and Parameters
47 
  - [x] 3.1 Update src/crc16/consts.rs with complete constants
48 
    - Update KEYS_8BB7_FORWARD with 256-byte folding keys (indices 21-22)
49 
    - Update KEYS_1021_REVERSE with 256-byte folding keys (indices 21-22)
50 
    - Add SIMD_CONSTANTS if different from CRC-32
51 
    - _Requirements: 5.1, 5.2, 5.4_
52
53 
  - [x] 3.2 Add Width16 struct to src/structs.rs
54 
    - Implement CrcWidth trait for Width16
55 
    - _Requirements: 5.3_
56
57 
  - [x] 3.3 Update CrcAlgorithm enum and CrcParams::new()
58 
    - Add Crc16Custom variant to CrcAlgorithm enum
59 
    - Update CrcParams::new() to handle width=16
60 
    - Update cache module if needed for CRC-16 key caching
61 
    - _Requirements: 5.5, 6.1_
62
63 
- [x] 4. Implement CRC-16 Algorithm
64 
  - [x] 4.1 Create src/crc16/algorithm.rs with EnhancedCrcWidth implementation
65 
    - Implement EnhancedCrcWidth for Width16
66 
    - Implement create_state() with proper scaling for forward mode
67 
    - Implement extract_result() with proper scaling
68 
    - Implement fold_16(), fold_width(), barrett_reduction()
69 
    - Implement create_coefficient() and perform_final_reduction()
70 
    - Implement get_last_bytes_table_ptr()
71 
    - _Requirements: 2.3, 2.4, 2.5, 2.6, 2.7_
72
73 
  - [x] 4.2 Implement process_0_to_15 for CRC-16
74 
    - Handle small inputs (0-15 bytes) for CRC-16
75 
    - Follow pattern from crc32/algorithm.rs
76 
    - _Requirements: 2.1, 2.2_
77
78 
  - [x] 4.3 Update architecture dispatcher for CRC-16
79 
    - Update src/arch/mod.rs to handle width=16
80 
    - Route to Width16 implementation
81 
    - _Requirements: 2.1, 2.2_
82
83 
  - [x] 4.4 Update software fallback for CRC-16
84 
    - Update src/arch/software.rs to handle CRC-16 algorithms
85 
    - Add CRC-16 reference implementations from crc crate
86 
    - _Requirements: 2.1, 2.2_
87
88 
- [x] 5. Checkpoint - Verify basic CRC-16 computation
89 
  - Ensure all tests pass, ask the user if questions arise.
90
91 
- [x] 6. Add Public API Support for CRC-16
92 
  - [x] 6.1 Update src/lib.rs checksum() function
93 
    - Add cases for Crc16IbmSdlc and Crc16T10Dif
94 
    - _Requirements: 2.1, 2.2_
95
96 
  - [x] 6.2 Update Digest and other public APIs
97 
    - Ensure Digest works with CRC-16 algorithms
98 
    - Ensure checksum_combine works with CRC-16
99 
    - _Requirements: 6.2, 6.3, 6.4_
100
101 
- [-] 7. Add Comprehensive Tests
102 
  - [x] 7.1 Add CRC-16 check value tests
103 
    - Test "123456789" produces 0x906E for CRC-16/IBM-SDLC
104 
    - Test "123456789" produces 0xD0DB for CRC-16/T10-DIF
105 
    - _Requirements: 2.1, 2.2, 4.2_
106
107 
  - [x] 7.2 Write property test for CRC-16 computation matches reference
108 
    - **Property 3: CRC-16 computation matches reference**
109 
    - **Validates: Requirements 2.1, 2.2, 5.5, 6.1, 6.2, 6.3**
110
111 
  - [x] 7.3 Write property test for backwards compatibility
112 
    - **Property 4: CRC-32 and CRC-64 backwards compatibility**
113 
    - **Validates: Requirements 3.1, 3.2, 3.4**
114
115 
  - [x] 7.4 Write property test for CRC-16 checksum combination
116 
    - **Property 5: CRC-16 checksum combination round-trip**
117 
    - **Validates: Requirements 6.4**
118
119 
  - [x] 7.5 Add CRC-16 to existing test suites
120 
    - Add CRC-16 configs to TEST_ALL_CONFIGS in src/test/consts.rs
121 
    - Ensure all length-based tests include CRC-16
122 
    - _Requirements: 4.3, 4.4_
123
124 
- [x] 8. Final Checkpoint - Ensure all tests pass
125 
  - Ensure all tests pass, ask the user if questions arise.
126 
  - Run cargo fmt --check
127 
  - Run cargo clippy -- -D warnings
128 
  - Run cargo test
129
130 
## Notes
131
132 
- Tasks marked with `*` are optional and can be skipped for faster MVP
133 
- Each task references specific requirements for traceability
134 
- Checkpoints ensure incremental validation
135 
- Property tests validate universal correctness properties
136 
- Unit tests validate specific examples and edge cases
137 
- The implementation leverages existing CRC-32 infrastructure to minimize code duplication