pub type SparseCol = Vec<u32>;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ReductionSummary {
pub rank: usize,
pub pivots: Vec<u32>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Strategy {
SparseList,
PackedCached,
DenseMacro,
Auto,
}
#[derive(Clone)]
pub struct DenseCol {
words: Vec<u64>,
}
#[derive(Clone)]
pub struct PackedCol {
words: Vec<u64>,
top_word: isize,
low: Option<u32>,
}
#[derive(Clone)]
pub struct XorShift64 {
state: u64,
}
impl XorShift64 {
pub fn new(seed: u64) -> Self {
let s = if seed == 0 { 0x9E3779B97F4A7C15 } else { seed };
Self { state: s }
}
fn next_u64(&mut self) -> u64 {
let mut x = self.state;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
self.state = x;
x.wrapping_mul(0x2545F4914F6CDD1D)
}
pub fn next_f64(&mut self) -> f64 {
let x = self.next_u64() >> 11;
(x as f64) * (1.0 / ((1u64 << 53) as f64))
}
pub fn gen_range_usize(&mut self, upper: usize) -> usize {
if upper <= 1 {
0
} else {
(self.next_u64() as usize) % upper
}
}
}
pub fn avg_col_weight(cols: &[SparseCol]) -> f64 {
if cols.is_empty() {
return 0.0;
}
let total: usize = cols.iter().map(|c| c.len()).sum();
total as f64 / cols.len() as f64
}
pub fn recommended_strategy(cols: &[SparseCol]) -> Strategy {
let avg = avg_col_weight(cols);
if avg <= 7.0 {
Strategy::PackedCached
} else {
Strategy::DenseMacro
}
}
pub fn reduce(rows: usize, cols: &[SparseCol]) -> ReductionSummary {
reduce_with_strategy(rows, cols, Strategy::Auto)
}
pub fn reduce_with_strategy(
rows: usize,
cols: &[SparseCol],
strategy: Strategy,
) -> ReductionSummary {
match strategy {
Strategy::SparseList => reduce_sparse_list(rows, cols),
Strategy::PackedCached => {
let packed: Vec<PackedCol> =
cols.iter().map(|c| sparse_to_packed_col(rows, c)).collect();
reduce_packed_cached(rows, &packed)
}
Strategy::DenseMacro => {
let dense: Vec<DenseCol> = cols.iter().map(|c| sparse_to_dense_col(rows, c)).collect();
reduce_dense_macro(rows, &dense)
}
Strategy::Auto => match recommended_strategy(cols) {
Strategy::PackedCached => {
let packed: Vec<PackedCol> =
cols.iter().map(|c| sparse_to_packed_col(rows, c)).collect();
reduce_packed_cached(rows, &packed)
}
_ => {
let dense: Vec<DenseCol> =
cols.iter().map(|c| sparse_to_dense_col(rows, c)).collect();
reduce_dense_macro(rows, &dense)
}
},
}
}
pub fn reduce_sparse_list(rows: usize, cols: &[SparseCol]) -> ReductionSummary {
let mut basis: Vec<Option<SparseCol>> = vec![None; rows];
for template in cols {
let mut col = template.clone();
while let Some(&pivot) = col.last() {
let slot = &mut basis[pivot as usize];
if let Some(bcol) = slot.as_ref() {
sym_diff_sorted_in_place(&mut col, bcol);
} else {
*slot = Some(col);
break;
}
}
}
let pivots: Vec<u32> = basis
.iter()
.enumerate()
.filter_map(|(i, c)| c.as_ref().map(|_| i as u32))
.collect();
ReductionSummary {
rank: pivots.len(),
pivots,
}
}
pub fn reduce_dense_macro(rows: usize, cols: &[DenseCol]) -> ReductionSummary {
let mut basis: Vec<Option<Vec<u64>>> = vec![None; rows];
for template in cols {
let mut col = template.words.clone();
while let Some(pivot) = low_dense(&col) {
let slot = &mut basis[pivot as usize];
if let Some(bcol) = slot.as_ref() {
xor_words_in_place(&mut col, bcol);
} else {
*slot = Some(col);
break;
}
}
}
let pivots: Vec<u32> = basis
.iter()
.enumerate()
.filter_map(|(i, c)| c.as_ref().map(|_| i as u32))
.collect();
ReductionSummary {
rank: pivots.len(),
pivots,
}
}
pub fn reduce_packed_cached(rows: usize, cols: &[PackedCol]) -> ReductionSummary {
let mut basis: Vec<Option<PackedCol>> = vec![None; rows];
for template in cols {
let mut col = template.clone();
while let Some(pivot) = col.low {
let slot = &mut basis[pivot as usize];
if let Some(bcol) = slot.as_ref() {
xor_words_active_prefix(&mut col, bcol);
} else {
*slot = Some(col);
break;
}
}
}
let pivots: Vec<u32> = basis
.iter()
.enumerate()
.filter_map(|(i, c)| c.as_ref().map(|_| i as u32))
.collect();
ReductionSummary {
rank: pivots.len(),
pivots,
}
}
pub fn generate_er_sparse(rows: usize, cols: usize, density: f64, seed: u64) -> Vec<SparseCol> {
let mut rng = XorShift64::new(seed);
let mut out = Vec::with_capacity(cols);
for _ in 0..cols {
let mut col = Vec::new();
for r in 0..rows {
if rng.next_f64() < density {
col.push(r as u32);
}
}
col.sort_unstable();
col.dedup();
out.push(col);
}
out
}
pub fn generate_ldpc_like(
rows: usize,
cols: usize,
col_weight: usize,
seed: u64,
) -> Vec<SparseCol> {
let mut rng = XorShift64::new(seed);
let mut out = Vec::with_capacity(cols);
for _ in 0..cols {
let mut picked = std::collections::BTreeSet::new();
while picked.len() < col_weight {
picked.insert(rng.gen_range_usize(rows) as u32);
}
out.push(picked.into_iter().collect());
}
out
}
pub fn generate_banded(
rows: usize,
cols: usize,
bandwidth: usize,
weight: usize,
seed: u64,
) -> Vec<SparseCol> {
let mut rng = XorShift64::new(seed);
let mut out = Vec::with_capacity(cols);
for c in 0..cols {
let center = if cols > 1 { (c * rows) / cols } else { 0 };
let lo = center.saturating_sub(bandwidth / 2);
let hi = (center + bandwidth / 2 + 1).min(rows);
let target = weight.min(hi.saturating_sub(lo)).max(1);
let mut picked = std::collections::BTreeSet::new();
while picked.len() < target {
let rr = lo + rng.gen_range_usize(hi - lo);
picked.insert(rr as u32);
}
out.push(picked.into_iter().collect());
}
out
}
fn sparse_to_dense_col(rows: usize, col: &[u32]) -> DenseCol {
let words_per_col = (rows + 63) / 64;
let mut words = vec![0u64; words_per_col];
for &r in col {
let rr = r as usize;
words[rr / 64] |= 1u64 << (rr % 64);
}
DenseCol { words }
}
fn sparse_to_packed_col(rows: usize, col: &[u32]) -> PackedCol {
let dense = sparse_to_dense_col(rows, col);
let low = col.last().copied();
let top_word = low.map(|x| (x as usize / 64) as isize).unwrap_or(-1);
PackedCol {
words: dense.words,
top_word,
low,
}
}
fn sym_diff_sorted_in_place(a: &mut Vec<u32>, b: &[u32]) {
let mut out = Vec::with_capacity(a.len() + b.len());
let (mut i, mut j) = (0usize, 0usize);
while i < a.len() && j < b.len() {
let av = a[i];
let bv = b[j];
if av < bv {
out.push(av);
i += 1;
} else if av > bv {
out.push(bv);
j += 1;
} else {
i += 1;
j += 1;
}
}
out.extend_from_slice(&a[i..]);
out.extend_from_slice(&b[j..]);
*a = out;
}
fn xor_words_in_place(a: &mut [u64], b: &[u64]) {
for (x, y) in a.iter_mut().zip(b.iter()) {
*x ^= *y;
}
}
fn low_dense(words: &[u64]) -> Option<u32> {
for (w_idx, &w) in words.iter().enumerate().rev() {
if w != 0 {
let bit = 63 - w.leading_zeros() as usize;
return Some((w_idx * 64 + bit) as u32);
}
}
None
}
fn low_packed_from(words: &[u64], mut top_word: isize) -> (Option<u32>, isize) {
while top_word >= 0 {
let w = words[top_word as usize];
if w != 0 {
let bit = 63 - w.leading_zeros() as usize;
return (Some((top_word as usize * 64 + bit) as u32), top_word);
}
top_word -= 1;
}
(None, -1)
}
fn xor_words_active_prefix(a: &mut PackedCol, b: &PackedCol) {
if a.top_word < 0 {
return;
}
let hi = a.top_word as usize;
for i in 0..=hi {
a.words[i] ^= b.words[i];
}
let (low, top_word) = low_packed_from(&a.words, a.top_word);
a.low = low;
a.top_word = top_word;
}
#[cfg(test)]
mod tests {
use super::*;
fn assert_all_agree(rows: usize, cols: &[SparseCol]) {
let s = reduce_with_strategy(rows, cols, Strategy::SparseList);
let p = reduce_with_strategy(rows, cols, Strategy::PackedCached);
let d = reduce_with_strategy(rows, cols, Strategy::DenseMacro);
let a = reduce_with_strategy(rows, cols, Strategy::Auto);
assert_eq!(s, p);
assert_eq!(s, d);
assert_eq!(s, a);
}
#[test]
fn er_strategies_agree() {
let cols = generate_er_sparse(256, 256, 0.03, 1337);
assert_all_agree(256, &cols);
}
#[test]
fn ldpc_strategies_agree() {
let cols = generate_ldpc_like(256, 512, 6, 7331);
assert_all_agree(256, &cols);
}
#[test]
fn banded_strategies_agree() {
let cols = generate_banded(256, 256, 32, 8, 4242);
assert_all_agree(256, &cols);
}
}
pub mod abi;
pub mod io;