Potential integer division by zero in search path when bits parameter is invalid

Summary

There is a potential integer division overflow/underflow issue in the search() function in turbovec/src/search.rs that could cause a panic or undefined behavior if the bits parameter is passed an unexpected value.

Location

File: turbovec/src/search.rs
Line: ~3227-3230
Function: pub(crate) fn search()

The Problem

The code calculates n_byte_groups using:

let n_byte_groups = dim / (8 / bits);

This expression is vulnerable when bits takes unexpected values:

• When bits == 2: dim / (8/2) = dim / 4 ✓ Safe
• When bits == 4: dim / (8/4) = dim / 2 ✓ Safe
• When bits > 8: 8 / bits = 0 (integer division), leading to dim / 0 → panic in debug mode or undefined behavior in release mode

Example scenarios:

• bits = 16: Results in 8 / 16 = 0 → div by zero
• bits = 32: Results in 8 / 32 = 0 → div by zero
• bits = 1: Results in 8 / 1 = 8 (mathematically incorrect: would expect 8 byte-groups for dim/1 bits)

Additional Issue

The code does not validate that dim is a multiple of (8 / bits) before performing integer division, which could silently truncate dimensions in edge cases:

let n_byte_groups = dim / (8 / bits);  // No validation that dim % (8/bits) == 0

Current Mitigation

The crate currently enforces that bits ∈ {2, 4} in TurboQuantIndex::new(), which validates inputs through the public API. However, the search() function is marked pub(crate), meaning it can be called internally by other functions. If future refactoring bypasses validation or adds new code paths, this hidden assumption could cause failures.

Recommended Fix

Add explicit validation in the search() function:

pub(crate) fn search(
    queries: &[f32],
    nq: usize,
    rotation: &Rotation,
    blocked_codes: &[u8],
    centroids: &[f32],
    vec_scales: &[f32],
    tqplus_shift: &[f32],
    tqplus_scale: &[f32],
    bits: usize,
    dim: usize,
    n_vectors: usize,
    n_blocks: usize,
    k: usize,
    mask: Option<&[u64]>,
) -> (Vec<f32>, Vec<i64>) {
    // ... existing code ...
    
    // Add validation:
    let divisor = 8 / bits;
    debug_assert!(divisor > 0, "bits must be in range [1, 8]; got {}", bits);
    debug_assert_eq!(dim % divisor, 0, "dim must be a multiple of {}; got {}", divisor, dim);
    
    let n_byte_groups = dim / divisor;
    
    // ... rest of function ...
}

Alternatively, use a safer division:

let divisor = (8 / bits).max(1);
let n_byte_groups = dim / divisor;
assert_eq!(dim % divisor, 0, "dim must be a multiple of {}", divisor);

Impact

• Severity: Medium
• Type: Safety/Correctness
• Affected code paths: Any internal caller of search() that doesn't validate bits before calling
• User-facing impact: Unlikely (public API validates), but defensive programming should still apply

Testing Suggestion

Add a test case to verify the bounds:

#[test]
#[should_panic]
fn search_panics_on_invalid_bits_greater_than_8() {
    // Create test inputs with bits = 16
    // Call search() and verify it panics or returns an error
}

#[test]
#[should_panic]
fn search_panics_on_dim_not_multiple_of_divisor() {
    // Create test inputs where dim % (8/bits) != 0
    // Verify assertion fails
}

Related Issues

• This is a defensive measure against future refactoring that might add new code paths to search() without proper validation
• Similar validation issues may exist in other pub(crate) functions that depend on undocumented constraints