vendor/crc-fast/.kiro/specs/future-proof-crc-params/design.md at 9b723f69b032 · andymccall/oxygen

# 9b723f69b032 oxygen / vendor / crc-fast / .kiro / specs / future-proof-crc-params / design.md

11.6 KiB · Markdown · last changed Strata: the cloud stores send through ureq, so every release target links 1 month ago rendered source blame history raw

# Design Document

## Overview

This design implements a future-proof CrcParams structure using an internal enum-based key storage system that can expand to support different key array sizes without breaking compatibility. The approach maintains the simplicity of const definitions while providing safe key access and zero runtime overhead through compiler optimizations.

## Architecture

### Core Components

1. **CrcKeysStorage Enum**: Internal storage that can hold different key array sizes
2. **CrcParams Structure**: Updated to use CrcKeysStorage internally while maintaining public API
3. **Safe Accessor Methods**: Bounds-checked key access methods on CrcParams
4. **Helper Functions**: Const-friendly constructors for CrcKeysStorage variants

### Design Principles

- **Zero Runtime Overhead**: Enum dispatch optimized away by compiler
- **Backwards Compatibility**: Existing const definitions require minimal changes
- **Gradual Migration**: Can be implemented in phases without breaking builds
- **Safety First**: Bounds checking prevents panics from out-of-range access

## Components and Interfaces

### CrcKeysStorage Enum

```rust
#[derive(Clone, Copy, Debug)]
enum CrcKeysStorage {
    /// Current 23-key format (for existing algorithms which includes 256 byte folding distances)
    KeysFold256([u64; 23]),
    /// Future 25-key format (for potential future expanded folding distances, for testing purposes only)
    KeysFutureTest([u64; 25]),
    // Additional variants can be added as needed
}
```

**Key Methods:**
- `get_key(index: usize) -> u64`: Safe key access with bounds checking
- `key_count() -> usize`: Returns actual number of keys available
- `from_keys_fold_256(keys: [u64; 23]) -> Self`: Const constructor for 23-key arrays
- `from_keys_fold_future_test(keys: [u64; 25]) -> Self`: Const constructor for 25-key arrays

### Updated CrcParams Structure

```rust
#[derive(Clone, Copy, Debug)]
pub struct CrcParams {
    pub algorithm: CrcAlgorithm,
    pub name: &'static str,
    pub width: u8,
    pub poly: u64,
    pub init: u64,
    pub refin: bool,
    pub refout: bool,
    pub xorout: u64,
    pub check: u64,
    pub keys: CrcKeysStorage,  // Changed from [u64; 23]
}
```

**Key Methods:**
- `get_key(index: usize) -> u64`: Delegates to CrcKeysStorage
- `get_key_checked(index: usize) -> Option<u64>`: Optional key access
- `key_count() -> usize`: Returns actual key count

### Const Definition Pattern

```rust
// Before (Phase 2):
pub const CRC32_ISCSI: CrcParams = CrcParams {
    // ... other fields unchanged ...
    keys: KEYS_1EDC6F41_REFLECTED,  // [u64; 23]
};

// After (Phase 3):
pub const CRC32_ISCSI: CrcParams = CrcParams {
    // ... other fields unchanged ...
    keys: CrcKeysStorage::from_keys_fold_256(KEYS_1EDC6F41_REFLECTED),
};
```

## Data Models

### Key Storage Variants

| Variant | Array Size | Use Case |
|---------|------------|----------|
| KeysFold256 | [u64; 23] | Current implementation (128/256-byte folding) |
| KeysFutureTest | [u64; 25] | Future expansion |

### Migration States

| Phase | CrcParams.keys Type | Architecture Code | Const Definitions |
|-------|-------------------|------------------|------------------|
| 1 | [u64; 23] | Direct access | Unchanged |
| 2 | [u64; 23] | Safe accessors | Unchanged |
| 3 | CrcKeysStorage | Safe accessors | Updated |

## Error Handling

### Bounds Checking Strategy

1. **Safe Default**: Out-of-bounds key access returns 0 instead of panicking
2. **Optional Access**: `get_key_checked()` returns `None` for invalid indices
3. **Graceful Degradation**: Code continues to function with missing keys

### Error Scenarios

| Scenario | Behavior | Rationale |
|----------|----------|-----------|
| Access key[30] with 23-key storage | Returns 0 | Allows future expansion without breaking existing code |
| Invalid key index | Returns 0 | Prevents panics, maintains stability |
| Empty key storage | Returns 0 for all indices | Defensive programming |

## Testing Strategy

### Unit Tests

1. **CrcKeysStorage Tests**:
   - Verify correct key storage and retrieval for each variant
   - Test bounds checking behavior
   - Validate const constructor functions

2. **CrcParams Integration Tests**:
   - Verify safe accessor methods work correctly
   - Test backwards compatibility with existing const definitions
   - Validate zero runtime overhead through benchmarks

3. **Migration Tests**:
   - Test each phase independently
   - Verify existing functionality remains intact
   - Validate const definition updates

### Compatibility Tests

1. **Third-Party Simulation**:
   - Create mock third-party const definitions
   - Verify they continue working through all phases
   - Test key access patterns used by external code

2. **Performance Tests**:
   - Benchmark key access performance vs direct array access
   - Verify compiler optimizations eliminate enum dispatch
   - Measure memory usage impact

### Integration Tests

1. **Architecture Code Tests**:
   - Update existing architecture tests to use safe accessors
   - Verify SIMD operations work correctly with new key access
   - Test folding operations across different key storage variants

2. **End-to-End Tests**:
   - Verify CRC calculations remain correct after migration
   - Test custom CrcParams creation and usage
   - Validate `get-custom-params` binary output

## Implementation Phases

### Phase 1: Add New Types
- Add CrcKeysStorage enum to codebase
- Add helper methods to CrcParams (delegating to existing keys field)
- Maintain existing [u64; 23] field for compatibility
- All tests continue to pass

### Phase 2: Update Architecture Code
- Replace direct key array access with safe accessor methods
- Update SIMD and folding code to use `params.get_key(index)`
- Maintain backwards compatibility
- Performance remains identical

### Phase 3: Switch to New Storage
- Change CrcParams.keys field from [u64; 23] to CrcKeysStorage
- Update all const definitions to use CrcKeysStorage::from_keys_23()
- Update `get-custom-params` binary output format
- This is the only breaking change, but minimal impact

## Performance Considerations

### Compiler Optimizations

The Rust compiler optimizes enum dispatch when:
1. All variants have the same access pattern
2. The enum is used in hot paths with predictable patterns
3. Inlining is enabled for accessor methods

Expected assembly output for `params.get_key(21)`:
```assembly
; Same as direct array access keys[21]
mov rax, qword ptr [rdi + 168 + 21*8]
```

### Memory Layout

| Storage Type | Memory Usage | Alignment |
|--------------|--------------|-----------|
| KeysFold256 | 184 bytes | 8-byte aligned |
| KeysFutureTest | 200 bytes | 8-byte aligned |
| Enum overhead | 0 bytes | (optimized away) |

## FFI Future-Proofing Design

### Problem Analysis

The current C FFI interface has several limitations:
1. **Fixed Key Array**: `CrcFastParams` struct uses `uint64_t keys[23]` hardcoded
2. **No Expansion Path**: Cannot support future key variants with different sizes
3. **Conversion Limitation**: `to_keys_array_23()` only works for current 23-key variant

### FFI Design Solution

Since the current FFI hasn't shipped yet, we can make it truly future-proof from the start using a pointer-based approach that can handle any number of keys.

#### Truly Future-Proof CrcFastParams Structure

```c
// Completely future-proof structure using pointer to keys
typedef struct CrcFastParams {
    enum CrcFastAlgorithm algorithm;
    uint8_t width;
    uint64_t poly;
    uint64_t init;
    bool refin;
    bool refout;
    uint64_t xorout;
    uint64_t check;
    uint32_t key_count;        // Number of keys available
    const uint64_t *keys;      // Pointer to keys array (managed by Rust)
} CrcFastParams;
```

#### Key Management Strategy

1. **Rust-Managed Memory**: Keys remain in Rust-managed memory
2. **Stable Pointers**: Use Box::leak or static storage for stable pointers
3. **Automatic Cleanup**: Rust handles memory management transparently
4. **No Size Limits**: Can support any number of keys (23, 25, 50, 100+)

#### Internal Implementation

```rust
// Helper to create stable key pointers
fn create_stable_key_pointer(keys: &CrcKeysStorage) -> *const u64 {
    match keys {
        CrcKeysStorage::KeysFold256(keys) => keys.as_ptr(),
        CrcKeysStorage::KeysFutureTest(keys) => keys.as_ptr(),
        // Future variants automatically supported
    }
}

impl From<CrcParams> for CrcFastParams {
    fn from(params: CrcParams) -> Self {
        CrcFastParams {
            algorithm: params.algorithm.into(),
            width: params.width,
            poly: params.poly,
            init: params.init,
            refin: params.refin,
            refout: params.refout,
            xorout: params.xorout,
            check: params.check,
            key_count: params.key_count() as u32,
            keys: create_stable_key_pointer(&params.keys),
        }
    }
}

impl From<CrcFastParams> for CrcParams {
    fn from(value: CrcFastParams) -> Self {
        // Convert C array back to appropriate CrcKeysStorage
        let keys = unsafe {
            std::slice::from_raw_parts(value.keys, value.key_count as usize)
        };
        
        let storage = match value.key_count {
            23 => CrcKeysStorage::from_keys_fold_256(
                keys.try_into().expect("Invalid key count for fold_256")
            ),
            25 => CrcKeysStorage::from_keys_fold_future_test(
                keys.try_into().expect("Invalid key count for future_test")
            ),
            _ => panic!("Unsupported key count: {}", value.key_count),
        };
        
        CrcParams {
            algorithm: value.algorithm.into(),
            name: "custom",
            width: value.width,
            poly: value.poly,
            init: value.init,
            refin: value.refin,
            refout: value.refout,
            xorout: value.xorout,
            check: value.check,
            keys: storage,
        }
    }
}
```

#### Enhanced FFI Functions

```rust
#[no_mangle]
pub extern "C" fn crc_fast_get_custom_params(...) -> CrcFastParams {
    let params = CrcParams::new(...);
    params.into()  // Automatic conversion
}
```

#### Benefits of This Approach

1. **Truly Future-Proof**: No hardcoded limits, supports any key count
2. **Zero Copy**: Keys remain in original Rust memory, just expose pointer
3. **Memory Safe**: Rust manages memory, C gets stable pointers
4. **Performance**: Direct pointer access, no copying overhead
5. **Automatic Support**: New CrcKeysStorage variants automatically work
6. **Idiomatic C**: Direct array access pattern familiar to C developers

#### C Usage Pattern

```c
// Get custom parameters
CrcFastParams params = crc_fast_get_custom_params(...);

// Direct access with bounds checking (C developer responsibility)
for (uint32_t i = 0; i < params.key_count; i++) {
    uint64_t key = params.keys[i];
    // Use key...
}

// Or access specific keys directly
uint64_t key21 = params.keys[21];  // Direct access (if bounds known)
```

## Security Considerations

### Bounds Safety

The new design eliminates array bounds panics, which could be exploited in unsafe contexts. Safe key access prevents:
- Buffer overflow attacks through malicious key indices
- Denial of service through panic-induced crashes
- Information disclosure through out-of-bounds memory access

### FFI Safety

The enhanced FFI design adds additional safety measures:
- **Key Count Validation**: V2 functions validate key_count before conversion
- **Buffer Bounds**: 32-key buffer prevents overflow while allowing future expansion
- **Graceful Degradation**: Invalid key counts return error codes instead of panicking

### Const Safety

All const definitions remain compile-time validated, preventing:
- Runtime key generation vulnerabilities
- Dynamic key modification attacks
- Timing-based side-channel attacks on key access

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1	# Design Document
2
3	## Overview
4
5	This design implements a future-proof CrcParams structure using an internal enum-based key storage system that can expand to support different key array sizes without breaking compatibility. The approach maintains the simplicity of const definitions while providing safe key access and zero runtime overhead through compiler optimizations.
6
7	## Architecture
8
9	### Core Components
10
11	1. CrcKeysStorage Enum: Internal storage that can hold different key array sizes
12	2. CrcParams Structure: Updated to use CrcKeysStorage internally while maintaining public API
13	3. Safe Accessor Methods: Bounds-checked key access methods on CrcParams
14	4. Helper Functions: Const-friendly constructors for CrcKeysStorage variants
15
16	### Design Principles
17
18	- Zero Runtime Overhead: Enum dispatch optimized away by compiler
19	- Backwards Compatibility: Existing const definitions require minimal changes
20	- Gradual Migration: Can be implemented in phases without breaking builds
21	- Safety First: Bounds checking prevents panics from out-of-range access
22
23	## Components and Interfaces
24
25	### CrcKeysStorage Enum
26
27	```rust
28	#[derive(Clone, Copy, Debug)]
29	enum CrcKeysStorage {
30	/// Current 23-key format (for existing algorithms which includes 256 byte folding distances)
31	KeysFold256([u64; 23]),
32	/// Future 25-key format (for potential future expanded folding distances, for testing purposes only)
33	KeysFutureTest([u64; 25]),
34	// Additional variants can be added as needed
35	}
36	```
37
38	Key Methods:
39	- `get_key(index: usize) -> u64`: Safe key access with bounds checking
40	- `key_count() -> usize`: Returns actual number of keys available
41	- `from_keys_fold_256(keys: [u64; 23]) -> Self`: Const constructor for 23-key arrays
42	- `from_keys_fold_future_test(keys: [u64; 25]) -> Self`: Const constructor for 25-key arrays
43
44	### Updated CrcParams Structure
45
46	```rust
47	#[derive(Clone, Copy, Debug)]
48	pub struct CrcParams {
49	pub algorithm: CrcAlgorithm,
50	pub name: &'static str,
51	pub width: u8,
52	pub poly: u64,
53	pub init: u64,
54	pub refin: bool,
55	pub refout: bool,
56	pub xorout: u64,
57	pub check: u64,
58	pub keys: CrcKeysStorage, // Changed from [u64; 23]
59	}
60	```
61
62	Key Methods:
63	- `get_key(index: usize) -> u64`: Delegates to CrcKeysStorage
64	- `get_key_checked(index: usize) -> Option<u64>`: Optional key access
65	- `key_count() -> usize`: Returns actual key count
66
67	### Const Definition Pattern
68
69	```rust
70	// Before (Phase 2):
71	pub const CRC32_ISCSI: CrcParams = CrcParams {
72	// ... other fields unchanged ...
73	keys: KEYS_1EDC6F41_REFLECTED, // [u64; 23]
74	};
75
76	// After (Phase 3):
77	pub const CRC32_ISCSI: CrcParams = CrcParams {
78	// ... other fields unchanged ...
79	keys: CrcKeysStorage::from_keys_fold_256(KEYS_1EDC6F41_REFLECTED),
80	};
81	```
82
83	## Data Models
84
85	### Key Storage Variants
86
87	\| Variant \| Array Size \| Use Case \|
88	\|---------\|------------\|----------\|
89	\| KeysFold256 \| [u64; 23] \| Current implementation (128/256-byte folding) \|
90	\| KeysFutureTest \| [u64; 25] \| Future expansion \|
91
92	### Migration States
93
94	\| Phase \| CrcParams.keys Type \| Architecture Code \| Const Definitions \|
95	\|-------\|-------------------\|------------------\|------------------\|
96	\| 1 \| [u64; 23] \| Direct access \| Unchanged \|
97	\| 2 \| [u64; 23] \| Safe accessors \| Unchanged \|
98	\| 3 \| CrcKeysStorage \| Safe accessors \| Updated \|
99
100	## Error Handling
101
102	### Bounds Checking Strategy
103
104	1. Safe Default: Out-of-bounds key access returns 0 instead of panicking
105	2. Optional Access: `get_key_checked()` returns `None` for invalid indices
106	3. Graceful Degradation: Code continues to function with missing keys
107
108	### Error Scenarios
109
110	\| Scenario \| Behavior \| Rationale \|
111	\|----------\|----------\|-----------\|
112	\| Access key[30] with 23-key storage \| Returns 0 \| Allows future expansion without breaking existing code \|
113	\| Invalid key index \| Returns 0 \| Prevents panics, maintains stability \|
114	\| Empty key storage \| Returns 0 for all indices \| Defensive programming \|
115
116	## Testing Strategy
117
118	### Unit Tests
119
120	1. CrcKeysStorage Tests:
121	- Verify correct key storage and retrieval for each variant
122	- Test bounds checking behavior
123	- Validate const constructor functions
124
125	2. CrcParams Integration Tests:
126	- Verify safe accessor methods work correctly
127	- Test backwards compatibility with existing const definitions
128	- Validate zero runtime overhead through benchmarks
129
130	3. Migration Tests:
131	- Test each phase independently
132	- Verify existing functionality remains intact
133	- Validate const definition updates
134
135	### Compatibility Tests
136
137	1. Third-Party Simulation:
138	- Create mock third-party const definitions
139	- Verify they continue working through all phases
140	- Test key access patterns used by external code
141
142	2. Performance Tests:
143	- Benchmark key access performance vs direct array access
144	- Verify compiler optimizations eliminate enum dispatch
145	- Measure memory usage impact
146
147	### Integration Tests
148
149	1. Architecture Code Tests:
150	- Update existing architecture tests to use safe accessors
151	- Verify SIMD operations work correctly with new key access
152	- Test folding operations across different key storage variants
153
154	2. End-to-End Tests:
155	- Verify CRC calculations remain correct after migration
156	- Test custom CrcParams creation and usage
157	- Validate `get-custom-params` binary output
158
159	## Implementation Phases
160
161	### Phase 1: Add New Types
162	- Add CrcKeysStorage enum to codebase
163	- Add helper methods to CrcParams (delegating to existing keys field)
164	- Maintain existing [u64; 23] field for compatibility
165	- All tests continue to pass
166
167	### Phase 2: Update Architecture Code
168	- Replace direct key array access with safe accessor methods
169	- Update SIMD and folding code to use `params.get_key(index)`
170	- Maintain backwards compatibility
171	- Performance remains identical
172
173	### Phase 3: Switch to New Storage
174	- Change CrcParams.keys field from [u64; 23] to CrcKeysStorage
175	- Update all const definitions to use CrcKeysStorage::from_keys_23()
176	- Update `get-custom-params` binary output format
177	- This is the only breaking change, but minimal impact
178
179	## Performance Considerations
180
181	### Compiler Optimizations
182
183	The Rust compiler optimizes enum dispatch when:
184	1. All variants have the same access pattern
185	2. The enum is used in hot paths with predictable patterns
186	3. Inlining is enabled for accessor methods
187
188	Expected assembly output for `params.get_key(21)`:
189	```assembly
190	; Same as direct array access keys[21]
191	mov rax, qword ptr [rdi + 168 + 21*8]
192	```
193
194	### Memory Layout
195
196	\| Storage Type \| Memory Usage \| Alignment \|
197	\|--------------\|--------------\|-----------\|
198	\| KeysFold256 \| 184 bytes \| 8-byte aligned \|
199	\| KeysFutureTest \| 200 bytes \| 8-byte aligned \|
200	\| Enum overhead \| 0 bytes \| (optimized away) \|
201
202	## FFI Future-Proofing Design
203
204	### Problem Analysis
205
206	The current C FFI interface has several limitations:
207	1. Fixed Key Array: `CrcFastParams` struct uses `uint64_t keys[23]` hardcoded
208	2. No Expansion Path: Cannot support future key variants with different sizes
209	3. Conversion Limitation: `to_keys_array_23()` only works for current 23-key variant
210
211	### FFI Design Solution
212
213	Since the current FFI hasn't shipped yet, we can make it truly future-proof from the start using a pointer-based approach that can handle any number of keys.
214
215	#### Truly Future-Proof CrcFastParams Structure
216
217	```c
218	// Completely future-proof structure using pointer to keys
219	typedef struct CrcFastParams {
220	enum CrcFastAlgorithm algorithm;
221	uint8_t width;
222	uint64_t poly;
223	uint64_t init;
224	bool refin;
225	bool refout;
226	uint64_t xorout;
227	uint64_t check;
228	uint32_t key_count; // Number of keys available
229	const uint64_t *keys; // Pointer to keys array (managed by Rust)
230	} CrcFastParams;
231	```
232
233	#### Key Management Strategy
234
235	1. Rust-Managed Memory: Keys remain in Rust-managed memory
236	2. Stable Pointers: Use Box::leak or static storage for stable pointers
237	3. Automatic Cleanup: Rust handles memory management transparently
238	4. No Size Limits: Can support any number of keys (23, 25, 50, 100+)
239
240	#### Internal Implementation
241
242	```rust
243	// Helper to create stable key pointers
244	fn create_stable_key_pointer(keys: &CrcKeysStorage) -> *const u64 {
245	match keys {
246	CrcKeysStorage::KeysFold256(keys) => keys.as_ptr(),
247	CrcKeysStorage::KeysFutureTest(keys) => keys.as_ptr(),
248	// Future variants automatically supported
249	}
250	}
251
252	impl From<CrcParams> for CrcFastParams {
253	fn from(params: CrcParams) -> Self {
254	CrcFastParams {
255	algorithm: params.algorithm.into(),
256	width: params.width,
257	poly: params.poly,
258	init: params.init,
259	refin: params.refin,
260	refout: params.refout,
261	xorout: params.xorout,
262	check: params.check,
263	key_count: params.key_count() as u32,
264	keys: create_stable_key_pointer(&params.keys),
265	}
266	}
267	}
268
269	impl From<CrcFastParams> for CrcParams {
270	fn from(value: CrcFastParams) -> Self {
271	// Convert C array back to appropriate CrcKeysStorage
272	let keys = unsafe {
273	std::slice::from_raw_parts(value.keys, value.key_count as usize)
274	};
275
276	let storage = match value.key_count {
277	23 => CrcKeysStorage::from_keys_fold_256(
278	keys.try_into().expect("Invalid key count for fold_256")
279	),
280	25 => CrcKeysStorage::from_keys_fold_future_test(
281	keys.try_into().expect("Invalid key count for future_test")
282	),
283	_ => panic!("Unsupported key count: {}", value.key_count),
284	};
285
286	CrcParams {
287	algorithm: value.algorithm.into(),
288	name: "custom",
289	width: value.width,
290	poly: value.poly,
291	init: value.init,
292	refin: value.refin,
293	refout: value.refout,
294	xorout: value.xorout,
295	check: value.check,
296	keys: storage,
297	}
298	}
299	}
300	```
301
302	#### Enhanced FFI Functions
303
304	```rust
305	#[no_mangle]
306	pub extern "C" fn crc_fast_get_custom_params(...) -> CrcFastParams {
307	let params = CrcParams::new(...);
308	params.into() // Automatic conversion
309	}
310	```
311
312	#### Benefits of This Approach
313
314	1. Truly Future-Proof: No hardcoded limits, supports any key count
315	2. Zero Copy: Keys remain in original Rust memory, just expose pointer
316	3. Memory Safe: Rust manages memory, C gets stable pointers
317	4. Performance: Direct pointer access, no copying overhead
318	5. Automatic Support: New CrcKeysStorage variants automatically work
319	6. Idiomatic C: Direct array access pattern familiar to C developers
320
321	#### C Usage Pattern
322
323	```c
324	// Get custom parameters
325	CrcFastParams params = crc_fast_get_custom_params(...);
326
327	// Direct access with bounds checking (C developer responsibility)
328	for (uint32_t i = 0; i < params.key_count; i++) {
329	uint64_t key = params.keys[i];
330	// Use key...
331	}
332
333	// Or access specific keys directly
334	uint64_t key21 = params.keys[21]; // Direct access (if bounds known)
335	```
336
337	## Security Considerations
338
339	### Bounds Safety
340
341	The new design eliminates array bounds panics, which could be exploited in unsafe contexts. Safe key access prevents:
342	- Buffer overflow attacks through malicious key indices
343	- Denial of service through panic-induced crashes
344	- Information disclosure through out-of-bounds memory access
345
346	### FFI Safety
347
348	The enhanced FFI design adds additional safety measures:
349	- Key Count Validation: V2 functions validate key_count before conversion
350	- Buffer Bounds: 32-key buffer prevents overflow while allowing future expansion
351	- Graceful Degradation: Invalid key counts return error codes instead of panicking
352
353	### Const Safety
354
355	All const definitions remain compile-time validated, preventing:
356	- Runtime key generation vulnerabilities
357	- Dynamic key modification attacks
358	- Timing-based side-channel attacks on key access

Keyboard