use crate::input::VerifyInput;
pub(crate) const R_ENCODING_LEN: usize = crate::edwards::POINT_ENCODING_LEN;
pub(crate) const SIMD_LANES: usize = 8;
pub(crate) fn for_each_simd_chunk<'a>(
inputs: &[VerifyInput<'a>],
visit_order: &mut Vec<usize>,
visit: impl FnMut(&[VerifyInput<'a>; SIMD_LANES], &[usize; SIMD_LANES], usize),
) {
if inputs.len() >= SIMD_LANES * 2 && has_mixed_block_counts(inputs) {
for_each_block_sorted_simd_chunk(inputs, visit_order, visit);
} else {
for_each_in_order_simd_chunk(inputs, visit);
}
}
fn for_each_in_order_simd_chunk<'a>(
inputs: &[VerifyInput<'a>],
mut visit: impl FnMut(&[VerifyInput<'a>; SIMD_LANES], &[usize; SIMD_LANES], usize),
) {
let (chunks, _) = inputs.as_chunks::<SIMD_LANES>();
for (chunk_index, chunk) in chunks.iter().enumerate() {
let output_indices = core::array::from_fn(|lane| chunk_index * SIMD_LANES + lane);
visit(chunk, &output_indices, SIMD_LANES);
}
let i = chunks.len() * SIMD_LANES;
let rem = inputs.len() - i;
if rem > 0 {
let last = inputs.len() - 1;
let mut chunk = [inputs[last]; SIMD_LANES];
chunk[..rem].copy_from_slice(&inputs[i..]);
let output_indices = core::array::from_fn(|lane| if lane < rem { i + lane } else { last });
visit(&chunk, &output_indices, rem);
}
}
fn for_each_block_sorted_simd_chunk<'a>(
inputs: &[VerifyInput<'a>],
visit_order: &mut Vec<usize>,
mut visit: impl FnMut(&[VerifyInput<'a>; SIMD_LANES], &[usize; SIMD_LANES], usize),
) {
sort_indices_by_block_count(inputs, visit_order);
let mut i = 0;
while i + SIMD_LANES <= visit_order.len() {
let output_indices: [usize; SIMD_LANES] =
core::array::from_fn(|lane| visit_order[i + lane]);
let chunk: [VerifyInput<'a>; SIMD_LANES] =
core::array::from_fn(|lane| inputs[output_indices[lane]]);
visit(&chunk, &output_indices, SIMD_LANES);
i += SIMD_LANES;
}
let rem = visit_order.len() - i;
if rem > 0 {
let last = visit_order[visit_order.len() - 1];
let output_indices: [usize; SIMD_LANES] = core::array::from_fn(|lane| {
if lane < rem {
visit_order[i + lane]
} else {
last
}
});
let chunk: [VerifyInput<'a>; SIMD_LANES] =
core::array::from_fn(|lane| inputs[output_indices[lane]]);
visit(&chunk, &output_indices, rem);
}
}
fn has_mixed_block_counts(inputs: &[VerifyInput<'_>]) -> bool {
let Some(first_input) = inputs.first() else {
return false;
};
let first = challenge_block_count(first_input.message.len());
let mut i = 1;
while i < inputs.len() {
if challenge_block_count(inputs[i].message.len()) != first {
return true;
}
i += 1;
}
false
}
fn sort_indices_by_block_count(inputs: &[VerifyInput<'_>], visit_order: &mut Vec<usize>) {
visit_order.clear();
visit_order.extend(0..inputs.len());
visit_order.sort_unstable_by_key(|&i| challenge_block_count(inputs[i].message.len()));
}
#[inline]
pub(crate) fn challenge_block_count(message_len: usize) -> usize {
message_len.saturating_add(64 + 1 + 16).div_ceil(128)
}
#[cfg(test)]
mod tests {
use super::*;
fn inputs(count: usize, message: &[u8]) -> Vec<VerifyInput<'_>> {
(0..count)
.map(|i| VerifyInput {
public_key: [i as u8; 32],
signature: [i as u8; 64],
message,
})
.collect()
}
fn visited(inputs: &[VerifyInput<'_>]) -> Vec<([usize; SIMD_LANES], usize)> {
let mut visit_order = Vec::new();
let mut seen = Vec::new();
for_each_simd_chunk(inputs, &mut visit_order, |_, indices, active| {
seen.push((*indices, active));
});
seen
}
#[test]
fn every_input_is_visited_exactly_once_at_each_batch_size() {
for count in 0..=(SIMD_LANES * 3 + 1) {
let inputs = inputs(count, b"same");
let mut covered = vec![0usize; count];
for (indices, active) in visited(&inputs) {
assert!(active <= SIMD_LANES);
for &index in &indices[..active] {
covered[index] += 1;
}
}
assert!(
covered.iter().all(|&hits| hits == 1),
"count {count} covered {covered:?}"
);
}
}
#[test]
fn padding_lanes_hold_in_range_output_indices() {
for count in 1..=(SIMD_LANES * 2 + 3) {
for (indices, _) in visited(&inputs(count, b"uniform")) {
assert!(
indices.iter().all(|&index| index < count),
"count {count} produced out-of-range indices {indices:?}"
);
}
}
}
#[test]
fn mixed_block_counts_are_detected_by_a_single_differing_input() {
let long = vec![0u8; 200];
assert_ne!(
challenge_block_count(long.len()),
challenge_block_count(b"short".len())
);
assert!(!has_mixed_block_counts(&inputs(0, b"short")));
assert!(!has_mixed_block_counts(&inputs(1, b"short")));
assert!(!has_mixed_block_counts(&inputs(SIMD_LANES * 2, b"short")));
for differing in [0, 5, SIMD_LANES * 2 - 1] {
let mut mixed = inputs(SIMD_LANES * 2, b"short");
mixed[differing].message = &long;
assert!(
has_mixed_block_counts(&mixed),
"missed a differing input at {differing}"
);
}
}
#[test]
fn small_batches_are_visited_in_order_despite_mixed_block_counts() {
let long = vec![0u8; 200];
let mut small = inputs(SIMD_LANES, b"short");
small[0].message = &long;
assert!(has_mixed_block_counts(&small));
let chunks = visited(&small);
assert_eq!(chunks.len(), 1);
let identity: [usize; SIMD_LANES] = core::array::from_fn(|lane| lane);
assert_eq!(
chunks[0],
(identity, SIMD_LANES),
"a batch below the reordering threshold was sorted anyway"
);
let mut large = inputs(SIMD_LANES * 2, b"short");
large[0].message = &long;
let visited_large = visited(&large);
assert_ne!(
visited_large[0].0[0], 0,
"a batch above the threshold was not reordered"
);
}
#[test]
fn sorting_visits_block_counts_in_nondecreasing_order() {
let long = vec![0u8; 200];
let mut mixed = inputs(SIMD_LANES * 2, b"short");
for index in [1, 4, 9, 14] {
mixed[index].message = &long;
}
let visited_counts: Vec<usize> = visited(&mixed)
.into_iter()
.flat_map(|(indices, active)| {
indices[..active]
.iter()
.map(|&i| challenge_block_count(mixed[i].message.len()))
.collect::<Vec<_>>()
})
.collect();
assert!(
visited_counts.windows(2).all(|pair| pair[0] <= pair[1]),
"block counts are not sorted: {visited_counts:?}"
);
}
#[test]
fn aligned_block_count_groups_produce_single_count_chunks() {
let long = vec![0u8; 200];
let mut mixed = inputs(SIMD_LANES * 2, b"short");
for index in 0..SIMD_LANES {
mixed[index * 2].message = &long;
}
let chunks = visited(&mixed);
assert_eq!(chunks.len(), 2);
for (indices, active) in chunks {
let counts: Vec<usize> = indices[..active]
.iter()
.map(|&i| challenge_block_count(mixed[i].message.len()))
.collect();
assert!(
counts.windows(2).all(|pair| pair[0] == pair[1]),
"chunk mixes block counts: {counts:?}"
);
}
}
#[test]
fn challenge_block_count_matches_sha512_padding_boundaries() {
assert_eq!(challenge_block_count(0), 1);
assert_eq!(challenge_block_count(47), 1);
assert_eq!(challenge_block_count(48), 2);
assert_eq!(challenge_block_count(175), 2);
assert_eq!(challenge_block_count(176), 3);
assert_eq!(challenge_block_count(usize::MAX), usize::MAX / 128 + 1);
}
}