use crate::Error;
#[allow(clippy::too_many_arguments)]
pub fn element_offset_u32(
s: u64,
t: u64,
h: u64,
d: u64,
page_size: u32,
num_pages: u64,
num_heads: u64,
head_dim: u64,
block_table: &[u32],
seq_ptr: &[u32],
) -> crate::Result<u64> {
element_offset_impl(
s,
t,
h,
d,
page_size,
num_pages,
num_heads,
head_dim,
seq_ptr,
block_table,
)
}
#[allow(clippy::too_many_arguments)]
pub fn element_offset_u64(
s: u64,
t: u64,
h: u64,
d: u64,
page_size: u32,
num_pages: u64,
num_heads: u64,
head_dim: u64,
block_table: &[u64],
seq_ptr: &[u64],
) -> crate::Result<u64> {
element_offset_impl(
s,
t,
h,
d,
page_size,
num_pages,
num_heads,
head_dim,
seq_ptr,
block_table,
)
}
#[allow(clippy::too_many_arguments)]
fn element_offset_impl<T: Copy + Into<u64>>(
s: u64,
t: u64,
h: u64,
d: u64,
page_size: u32,
num_pages: u64,
num_heads: u64,
head_dim: u64,
seq_ptr: &[T],
block_table: &[T],
) -> crate::Result<u64> {
let num_seqs = seq_ptr.len().saturating_sub(1) as u64;
if s >= num_seqs {
return Err(Error::IndexOutOfRange {
dim: 0,
index: s,
size: num_seqs,
});
}
if h >= num_heads {
return Err(Error::IndexOutOfRange {
dim: 1,
index: h,
size: num_heads,
});
}
if d >= head_dim {
return Err(Error::IndexOutOfRange {
dim: 2,
index: d,
size: head_dim,
});
}
let page_size_u64 = page_size as u64;
let bt_start: u64 = seq_ptr[s as usize].into();
let bt_end: u64 = seq_ptr[s as usize + 1].into();
let seq_page_count = bt_end.checked_sub(bt_start).ok_or_else(|| {
Error::InvalidLayout(
"block-paged: seq_ptr is not non-decreasing (storage invariant violated)".to_string(),
)
})?;
let page_in_seq = t / page_size_u64;
let offset_in_page = t % page_size_u64;
if page_in_seq >= seq_page_count {
return Err(Error::IndexOutOfRange {
dim: 0,
index: t,
size: seq_page_count.saturating_mul(page_size_u64),
});
}
let bt_idx = bt_start
.checked_add(page_in_seq)
.ok_or(Error::AddressOverflow)?;
let bt_idx_usize = bt_idx as usize;
if bt_idx_usize >= block_table.len() {
return Err(Error::IndexOutOfRange {
dim: 0,
index: bt_idx,
size: block_table.len() as u64,
});
}
let phys_page: u64 = block_table[bt_idx_usize].into();
if phys_page >= num_pages {
return Err(Error::IndexOutOfRange {
dim: 0,
index: phys_page,
size: num_pages,
});
}
let flat = phys_page
.checked_mul(page_size_u64)
.and_then(|v| v.checked_add(offset_in_page))
.and_then(|v| v.checked_mul(num_heads))
.and_then(|v| v.checked_add(h))
.and_then(|v| v.checked_mul(head_dim))
.and_then(|v| v.checked_add(d))
.ok_or(Error::AddressOverflow)?;
Ok(flat)
}
pub fn validate_index_buffers_u64(
num_pages: u64,
num_seqs: u32,
seq_ptr: &[u64],
block_table: &[u64],
) -> crate::Result<()> {
validate_index_buffers_impl(num_pages, num_seqs, seq_ptr, block_table)
}
pub fn validate_index_buffers_u32(
num_pages: u64,
num_seqs: u32,
seq_ptr: &[u32],
block_table: &[u32],
) -> crate::Result<()> {
let sp: Vec<u64> = seq_ptr.iter().map(|&v| v as u64).collect();
let bt: Vec<u64> = block_table.iter().map(|&v| v as u64).collect();
validate_index_buffers_impl(num_pages, num_seqs, &sp, &bt)
}
fn validate_index_buffers_impl(
num_pages: u64,
num_seqs: u32,
seq_ptr: &[u64],
block_table: &[u64],
) -> crate::Result<()> {
let expected_sp_len = (num_seqs as usize).saturating_add(1);
if seq_ptr.len() != expected_sp_len {
return Err(Error::InvalidLayout(format!(
"block-paged: seq_ptr length {} does not equal num_seqs + 1 = {}",
seq_ptr.len(),
expected_sp_len
)));
}
if seq_ptr[0] != 0 {
return Err(Error::InvalidLayout(format!(
"block-paged: seq_ptr[0] must be 0, got {}",
seq_ptr[0]
)));
}
for i in 0..(seq_ptr.len() - 1) {
if seq_ptr[i] > seq_ptr[i + 1] {
return Err(Error::InvalidLayout(format!(
"block-paged: seq_ptr is not non-decreasing at index {}: seq_ptr[{}]={} > seq_ptr[{}]={}",
i,
i,
seq_ptr[i],
i + 1,
seq_ptr[i + 1]
)));
}
}
let total_logical_pages = seq_ptr[num_seqs as usize];
if total_logical_pages != block_table.len() as u64 {
return Err(Error::InvalidLayout(format!(
"block-paged: seq_ptr[num_seqs]={} does not equal block_table.len()={}",
total_logical_pages,
block_table.len()
)));
}
for (k, &phys_page) in block_table.iter().enumerate() {
if phys_page >= num_pages {
return Err(Error::InvalidLayout(format!(
"block-paged: block_table[{k}]={phys_page} >= num_pages={num_pages}"
)));
}
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::Error;
fn spec_example_u32() -> (&'static [u32], &'static [u32]) {
let block_table: &[u32] = &[0, 1, 0];
let seq_ptr: &[u32] = &[0, 2, 3];
(block_table, seq_ptr)
}
fn spec_example_u64() -> (&'static [u64], &'static [u64]) {
let block_table: &[u64] = &[0, 1, 0];
let seq_ptr: &[u64] = &[0, 2, 3];
(block_table, seq_ptr)
}
#[test]
fn element_offset_u32_spec_example_seq0_t0_h0_d0() {
let (bt, sp) = spec_example_u32();
let flat = element_offset_u32(0, 0, 0, 0, 4, 5, 2, 8, bt, sp).unwrap();
assert_eq!(flat, 0);
}
#[test]
fn element_offset_u32_spec_example_seq0_t4_h0_d0() {
let (bt, sp) = spec_example_u32();
let flat = element_offset_u32(0, 4, 0, 0, 4, 5, 2, 8, bt, sp).unwrap();
assert_eq!(flat, 64);
}
#[test]
fn element_offset_u32_spec_example_seq0_t5_h1_d7() {
let (bt, sp) = spec_example_u32();
let flat = element_offset_u32(0, 5, 1, 7, 4, 5, 2, 8, bt, sp).unwrap();
assert_eq!(flat, 95);
}
#[test]
fn element_offset_u32_prefix_sharing_seq1_same_physical_page_as_seq0() {
let (bt, sp) = spec_example_u32();
let flat_seq0 = element_offset_u32(0, 0, 0, 0, 4, 5, 2, 8, bt, sp).unwrap();
let flat_seq1 = element_offset_u32(1, 0, 0, 0, 4, 5, 2, 8, bt, sp).unwrap();
assert_eq!(
flat_seq0, flat_seq1,
"aliased pages must resolve to identical flat offsets"
);
assert_eq!(flat_seq1, 0);
}
#[test]
fn element_offset_u32_token_beyond_sequence_page_count_is_error() {
let (bt, sp) = spec_example_u32();
let result = element_offset_u32(1, 4, 0, 0, 4, 5, 2, 8, bt, sp);
assert!(
matches!(result, Err(Error::IndexOutOfRange { .. })),
"token 4 in seq 1 (only 1 page) must be IndexOutOfRange"
);
}
#[test]
fn element_offset_u32_head_out_of_range_is_error() {
let (bt, sp) = spec_example_u32();
let result = element_offset_u32(0, 0, 2, 0, 4, 5, 2, 8, bt, sp);
assert!(matches!(result, Err(Error::IndexOutOfRange { dim: 1, .. })));
}
#[test]
fn element_offset_u32_dim_out_of_range_is_error() {
let (bt, sp) = spec_example_u32();
let result = element_offset_u32(0, 0, 0, 8, 4, 5, 2, 8, bt, sp);
assert!(matches!(result, Err(Error::IndexOutOfRange { dim: 2, .. })));
}
#[test]
fn element_offset_u32_seq_out_of_range_is_error() {
let (bt, sp) = spec_example_u32();
let result = element_offset_u32(2, 0, 0, 0, 4, 5, 2, 8, bt, sp);
assert!(matches!(result, Err(Error::IndexOutOfRange { dim: 0, .. })));
}
#[test]
fn element_offset_u32_non_monotone_seq_ptr_is_error_not_panic() {
let block_table: &[u32] = &[0];
let seq_ptr: &[u32] = &[0, 2, 1]; let result = element_offset_u32(1, 0, 0, 0, 4, 5, 2, 8, block_table, seq_ptr);
assert!(matches!(
result,
Err(Error::InvalidLayout(_) | Error::IndexOutOfRange { .. })
));
}
#[test]
fn element_offset_u64_matches_u32_on_spec_example() {
let (bt, sp) = spec_example_u64();
let flat = element_offset_u64(0, 4, 0, 0, 4, 5, 2, 8, bt, sp).unwrap();
assert_eq!(flat, 64);
}
#[test]
fn element_offset_u64_prefix_sharing_aliased_offsets_are_equal() {
let (bt, sp) = spec_example_u64();
let flat_seq0 = element_offset_u64(0, 0, 0, 0, 4, 5, 2, 8, bt, sp).unwrap();
let flat_seq1 = element_offset_u64(1, 0, 0, 0, 4, 5, 2, 8, bt, sp).unwrap();
assert_eq!(flat_seq0, flat_seq1);
}
#[test]
fn element_offset_u32_last_element_in_pool() {
let block_table: &[u32] = &[4]; let seq_ptr: &[u32] = &[0, 1];
let flat = element_offset_u32(0, 3, 1, 7, 4, 5, 2, 8, block_table, seq_ptr).unwrap();
assert_eq!(flat, 319);
}
#[test]
fn validate_index_buffers_u32_spec_example_is_valid() {
let seq_ptr: &[u32] = &[0, 2, 3];
let block_table: &[u32] = &[0, 1, 0];
assert!(
validate_index_buffers_u32(5, 2, seq_ptr, block_table).is_ok(),
"spec example index buffers must be valid"
);
}
#[test]
fn validate_index_buffers_u32_empty_batch_is_valid() {
let seq_ptr: &[u32] = &[0];
let block_table: &[u32] = &[];
assert!(
validate_index_buffers_u32(5, 0, seq_ptr, block_table).is_ok(),
"empty batch must be valid"
);
}
#[test]
fn validate_index_buffers_u32_single_seq_multiple_pages_is_valid() {
let seq_ptr: &[u32] = &[0, 3];
let block_table: &[u32] = &[2, 0, 4];
assert!(validate_index_buffers_u32(5, 1, seq_ptr, block_table).is_ok());
}
#[test]
fn validate_index_buffers_u32_rejects_seq_ptr_not_starting_at_zero() {
let seq_ptr: &[u32] = &[1, 3]; let block_table: &[u32] = &[0, 1, 2];
let result = validate_index_buffers_u32(5, 1, seq_ptr, block_table);
assert!(
matches!(result, Err(Error::InvalidLayout(_))),
"seq_ptr[0] != 0 must be InvalidLayout"
);
}
#[test]
fn validate_index_buffers_u32_rejects_non_monotonic_seq_ptr() {
let seq_ptr: &[u32] = &[0, 3, 2]; let block_table: &[u32] = &[0, 1, 0];
let result = validate_index_buffers_u32(5, 2, seq_ptr, block_table);
assert!(
matches!(result, Err(Error::InvalidLayout(_))),
"non-monotonic seq_ptr must be InvalidLayout"
);
}
#[test]
fn validate_index_buffers_u32_rejects_seq_ptr_total_mismatch_block_table_len() {
let seq_ptr: &[u32] = &[0, 2, 4];
let block_table: &[u32] = &[0, 1, 2]; let result = validate_index_buffers_u32(5, 2, seq_ptr, block_table);
assert!(
matches!(result, Err(Error::InvalidLayout(_))),
"seq_ptr[num_seqs] != block_table.len() must be InvalidLayout"
);
}
#[test]
fn validate_index_buffers_u32_rejects_out_of_bounds_page_id() {
let seq_ptr: &[u32] = &[0, 2, 3];
let block_table: &[u32] = &[0, 5, 0]; let result = validate_index_buffers_u32(5, 2, seq_ptr, block_table);
assert!(
matches!(result, Err(Error::InvalidLayout(_))),
"block_table[k] >= num_pages must be InvalidLayout"
);
}
#[test]
fn validate_index_buffers_u32_rejects_page_id_equal_to_num_pages() {
let seq_ptr: &[u32] = &[0, 1];
let block_table: &[u32] = &[5]; let result = validate_index_buffers_u32(5, 1, seq_ptr, block_table);
assert!(matches!(result, Err(Error::InvalidLayout(_))));
}
#[test]
fn validate_index_buffers_u64_spec_example_is_valid() {
let seq_ptr: &[u64] = &[0, 2, 3];
let block_table: &[u64] = &[0, 1, 0];
assert!(validate_index_buffers_u64(5, 2, seq_ptr, block_table).is_ok());
}
#[test]
fn validate_index_buffers_u64_empty_batch_is_valid() {
let seq_ptr: &[u64] = &[0];
let block_table: &[u64] = &[];
assert!(validate_index_buffers_u64(5, 0, seq_ptr, block_table).is_ok());
}
#[test]
fn validate_index_buffers_u64_rejects_out_of_bounds_page_id() {
let seq_ptr: &[u64] = &[0, 1];
let block_table: &[u64] = &[5]; let result = validate_index_buffers_u64(5, 1, seq_ptr, block_table);
assert!(matches!(result, Err(Error::InvalidLayout(_))));
}
}