use crate::ion::IonResult;
pub(crate) struct WindowEntry {
pub(crate) spectrum_index: u32,
pub(crate) mz_address: u32,
pub(crate) intensity_address: u32,
}
pub(crate) struct WindowDirectory {
starts: Vec<u32>,
spectrum_index: Vec<u32>,
mz_address: Vec<u32>,
intensity_address: Vec<u32>,
}
impl WindowDirectory {
pub(crate) fn window_count(&self) -> usize {
self.starts.len().saturating_sub(1)
}
pub(crate) fn window_range(&self, window: usize) -> std::ops::Range<usize> {
self.starts[window] as usize..self.starts[window + 1] as usize
}
pub(crate) fn row(&self, position: usize) -> WindowEntry {
WindowEntry {
spectrum_index: self.spectrum_index[position],
mz_address: self.mz_address[position],
intensity_address: self.intensity_address[position],
}
}
pub(crate) fn find_in_window(&self, window: usize, spectrum_index: u32) -> Option<WindowEntry> {
let range = self.window_range(window);
let found = self.spectrum_index[range.clone()]
.binary_search(&spectrum_index)
.ok()?;
Some(self.row(range.start + found))
}
pub(crate) fn from_bytes(
bytes: &[u8],
array_address_count: u64,
item_count: u64,
) -> IonResult<Self> {
if bytes.len() < 8 {
return Err("window directory: header too short".into());
}
let window_count_u64 = read_u32(bytes, 0) as u64;
let entry_count_u64 = read_u32(bytes, 4) as u64;
if window_count_u64 == 0 {
return Err("window directory: window_count is zero".into());
}
let starts_len_u64 = window_count_u64
.checked_add(1)
.ok_or("window directory: size overflow")?;
let expected_len_u64 = starts_len_u64
.checked_mul(4)
.and_then(|starts_bytes| starts_bytes.checked_add(8))
.and_then(|header_and_starts| {
entry_count_u64
.checked_mul(4)
.and_then(|column_bytes| column_bytes.checked_mul(3))
.and_then(|entry_bytes| header_and_starts.checked_add(entry_bytes))
})
.ok_or("window directory: size overflow")?;
if bytes.len() as u64 != expected_len_u64 {
return Err(
"window directory: length does not match window_count and entry_count".into(),
);
}
let window_count = usize::try_from(window_count_u64)
.map_err(|_| "window directory: window_count too large for this platform")?;
let entry_count = usize::try_from(entry_count_u64)
.map_err(|_| "window directory: entry_count too large for this platform")?;
let starts_len = usize::try_from(starts_len_u64)
.map_err(|_| "window directory: starts_len too large for this platform")?;
let mut starts = Vec::with_capacity(starts_len);
for slot in 0..starts_len {
starts.push(read_u32(bytes, 8 + slot * 4));
}
if starts[0] != 0 || starts[window_count] as usize != entry_count {
return Err("window directory: starts must run from 0 to entry_count".into());
}
for pair in starts.windows(2) {
if pair[1] < pair[0] {
return Err("window directory: starts must be non-decreasing".into());
}
}
let mut cursor = 8 + starts_len * 4;
let spectrum_index = read_column(bytes, &mut cursor, entry_count);
let mz_address = read_column(bytes, &mut cursor, entry_count);
let intensity_address = read_column(bytes, &mut cursor, entry_count);
for &spectrum in &spectrum_index {
if spectrum as u64 >= item_count {
return Err("window directory: spectrum_index out of range".into());
}
}
for &address in mz_address.iter().chain(intensity_address.iter()) {
if address as u64 >= array_address_count {
return Err("window directory: array address index out of range".into());
}
}
for window in 0..window_count {
let range = starts[window] as usize..starts[window + 1] as usize;
for pair in spectrum_index[range].windows(2) {
if pair[1] <= pair[0] {
return Err(
"window directory: spectrum_index must increase within a window".into(),
);
}
}
}
Ok(Self {
starts,
spectrum_index,
mz_address,
intensity_address,
})
}
}
fn read_u32(bytes: &[u8], offset: usize) -> u32 {
u32::from_le_bytes(bytes[offset..offset + 4].try_into().unwrap())
}
fn read_column(bytes: &[u8], cursor: &mut usize, count: usize) -> Vec<u32> {
let mut column = Vec::with_capacity(count);
for _ in 0..count {
column.push(read_u32(bytes, *cursor));
*cursor += 4;
}
column
}
#[cfg(test)]
mod tests {
use super::*;
fn build(windows: &[&[(u32, u32, u32)]]) -> Vec<u8> {
let entry_count: usize = windows.iter().map(|window| window.len()).sum();
let mut bytes = Vec::new();
bytes.extend_from_slice(&(windows.len() as u32).to_le_bytes());
bytes.extend_from_slice(&(entry_count as u32).to_le_bytes());
let mut start = 0u32;
for window in windows {
bytes.extend_from_slice(&start.to_le_bytes());
start += window.len() as u32;
}
bytes.extend_from_slice(&start.to_le_bytes());
for window in windows {
for row in *window {
bytes.extend_from_slice(&row.0.to_le_bytes());
}
}
for window in windows {
for row in *window {
bytes.extend_from_slice(&row.1.to_le_bytes());
}
}
for window in windows {
for row in *window {
bytes.extend_from_slice(&row.2.to_le_bytes());
}
}
bytes
}
#[test]
fn parses_and_finds_rows() {
let bytes = build(&[&[(0, 0, 4), (1, 8, 12)], &[(0, 1, 5), (1, 9, 13)]]);
let index = WindowDirectory::from_bytes(&bytes, 16, 2).unwrap();
assert_eq!(index.window_count(), 2);
assert_eq!(index.window_range(1), 2..4);
let row = index.find_in_window(1, 1).unwrap();
assert_eq!(
(row.spectrum_index, row.mz_address, row.intensity_address),
(1, 9, 13)
);
assert!(index.find_in_window(1, 5).is_none());
}
#[test]
fn rejects_length_mismatch() {
let mut bytes = build(&[&[(0, 0, 4)]]);
bytes.push(0);
assert!(WindowDirectory::from_bytes(&bytes, 16, 2).is_err());
}
#[test]
fn rejects_ref_index_out_of_range() {
let bytes = build(&[&[(0, 99, 4)]]);
assert!(WindowDirectory::from_bytes(&bytes, 16, 2).is_err());
}
#[test]
fn rejects_spectrum_index_out_of_range() {
let bytes = build(&[&[(9, 0, 4)]]);
assert!(WindowDirectory::from_bytes(&bytes, 16, 2).is_err());
}
#[test]
fn rejects_unsorted_spectrum_within_window() {
let bytes = build(&[&[(1, 0, 4), (0, 8, 12)]]);
assert!(WindowDirectory::from_bytes(&bytes, 16, 2).is_err());
}
#[test]
fn rejects_window_count_whose_starts_len_wraps_to_an_empty_directory_bonus() {
let mut bytes = Vec::with_capacity(8);
bytes.extend_from_slice(&u32::MAX.to_le_bytes());
bytes.extend_from_slice(&0u32.to_le_bytes());
let result = WindowDirectory::from_bytes(&bytes, 16, 2);
let err = match result {
Err(err) => err.to_string(),
Ok(_) => panic!(
"adversarial window_count near u32::MAX must be rejected cleanly, never panic"
),
};
assert!(
err.contains("size overflow")
|| err.contains("length does not match")
|| err.contains("too large for this platform"),
"unexpected error: {err}"
);
}
}