1pub type SparseCol = Vec<u32>;
2
3#[derive(Debug, Clone, PartialEq, Eq)]
4pub struct ReductionSummary {
5 pub rank: usize,
6 pub pivots: Vec<u32>,
7}
8
9#[derive(Debug, Clone, Copy, PartialEq, Eq)]
10pub enum Strategy {
11 SparseList,
12 PackedCached,
13 DenseMacro,
14 Auto,
15}
16
17#[derive(Clone)]
18pub struct DenseCol {
19 words: Vec<u64>,
20}
21
22#[derive(Clone)]
23pub struct PackedCol {
24 words: Vec<u64>,
25 top_word: isize,
26 low: Option<u32>,
27}
28
29#[derive(Clone)]
30pub struct XorShift64 {
31 state: u64,
32}
33
34impl XorShift64 {
35 pub fn new(seed: u64) -> Self {
36 let s = if seed == 0 { 0x9E3779B97F4A7C15 } else { seed };
37 Self { state: s }
38 }
39
40 fn next_u64(&mut self) -> u64 {
41 let mut x = self.state;
42 x ^= x >> 12;
43 x ^= x << 25;
44 x ^= x >> 27;
45 self.state = x;
46 x.wrapping_mul(0x2545F4914F6CDD1D)
47 }
48
49 pub fn next_f64(&mut self) -> f64 {
50 let x = self.next_u64() >> 11;
51 (x as f64) * (1.0 / ((1u64 << 53) as f64))
52 }
53
54 pub fn gen_range_usize(&mut self, upper: usize) -> usize {
55 if upper <= 1 {
56 0
57 } else {
58 (self.next_u64() as usize) % upper
59 }
60 }
61}
62
63pub fn avg_col_weight(cols: &[SparseCol]) -> f64 {
64 if cols.is_empty() {
65 return 0.0;
66 }
67 let total: usize = cols.iter().map(|c| c.len()).sum();
68 total as f64 / cols.len() as f64
69}
70
71pub fn recommended_strategy(cols: &[SparseCol]) -> Strategy {
72 let avg = avg_col_weight(cols);
73 if avg <= 7.0 {
74 Strategy::PackedCached
75 } else {
76 Strategy::DenseMacro
77 }
78}
79
80pub fn reduce(rows: usize, cols: &[SparseCol]) -> ReductionSummary {
81 reduce_with_strategy(rows, cols, Strategy::Auto)
82}
83
84pub fn reduce_with_strategy(
85 rows: usize,
86 cols: &[SparseCol],
87 strategy: Strategy,
88) -> ReductionSummary {
89 match strategy {
90 Strategy::SparseList => reduce_sparse_list(rows, cols),
91 Strategy::PackedCached => {
92 let packed: Vec<PackedCol> =
93 cols.iter().map(|c| sparse_to_packed_col(rows, c)).collect();
94 reduce_packed_cached(rows, &packed)
95 }
96 Strategy::DenseMacro => {
97 let dense: Vec<DenseCol> = cols.iter().map(|c| sparse_to_dense_col(rows, c)).collect();
98 reduce_dense_macro(rows, &dense)
99 }
100 Strategy::Auto => match recommended_strategy(cols) {
101 Strategy::PackedCached => {
102 let packed: Vec<PackedCol> =
103 cols.iter().map(|c| sparse_to_packed_col(rows, c)).collect();
104 reduce_packed_cached(rows, &packed)
105 }
106 _ => {
107 let dense: Vec<DenseCol> =
108 cols.iter().map(|c| sparse_to_dense_col(rows, c)).collect();
109 reduce_dense_macro(rows, &dense)
110 }
111 },
112 }
113}
114
115pub fn reduce_sparse_list(rows: usize, cols: &[SparseCol]) -> ReductionSummary {
116 let mut basis: Vec<Option<SparseCol>> = vec![None; rows];
117
118 for template in cols {
119 let mut col = template.clone();
120 while let Some(&pivot) = col.last() {
121 let slot = &mut basis[pivot as usize];
122 if let Some(bcol) = slot.as_ref() {
123 sym_diff_sorted_in_place(&mut col, bcol);
124 } else {
125 *slot = Some(col);
126 break;
127 }
128 }
129 }
130
131 let pivots: Vec<u32> = basis
132 .iter()
133 .enumerate()
134 .filter_map(|(i, c)| c.as_ref().map(|_| i as u32))
135 .collect();
136
137 ReductionSummary {
138 rank: pivots.len(),
139 pivots,
140 }
141}
142
143pub fn reduce_dense_macro(rows: usize, cols: &[DenseCol]) -> ReductionSummary {
144 let mut basis: Vec<Option<Vec<u64>>> = vec![None; rows];
145
146 for template in cols {
147 let mut col = template.words.clone();
148 while let Some(pivot) = low_dense(&col) {
149 let slot = &mut basis[pivot as usize];
150 if let Some(bcol) = slot.as_ref() {
151 xor_words_in_place(&mut col, bcol);
152 } else {
153 *slot = Some(col);
154 break;
155 }
156 }
157 }
158
159 let pivots: Vec<u32> = basis
160 .iter()
161 .enumerate()
162 .filter_map(|(i, c)| c.as_ref().map(|_| i as u32))
163 .collect();
164
165 ReductionSummary {
166 rank: pivots.len(),
167 pivots,
168 }
169}
170
171pub fn reduce_packed_cached(rows: usize, cols: &[PackedCol]) -> ReductionSummary {
172 let mut basis: Vec<Option<PackedCol>> = vec![None; rows];
173
174 for template in cols {
175 let mut col = template.clone();
176 while let Some(pivot) = col.low {
177 let slot = &mut basis[pivot as usize];
178 if let Some(bcol) = slot.as_ref() {
179 xor_words_active_prefix(&mut col, bcol);
180 } else {
181 *slot = Some(col);
182 break;
183 }
184 }
185 }
186
187 let pivots: Vec<u32> = basis
188 .iter()
189 .enumerate()
190 .filter_map(|(i, c)| c.as_ref().map(|_| i as u32))
191 .collect();
192
193 ReductionSummary {
194 rank: pivots.len(),
195 pivots,
196 }
197}
198
199pub fn generate_er_sparse(rows: usize, cols: usize, density: f64, seed: u64) -> Vec<SparseCol> {
200 let mut rng = XorShift64::new(seed);
201 let mut out = Vec::with_capacity(cols);
202
203 for _ in 0..cols {
204 let mut col = Vec::new();
205 for r in 0..rows {
206 if rng.next_f64() < density {
207 col.push(r as u32);
208 }
209 }
210 col.sort_unstable();
211 col.dedup();
212 out.push(col);
213 }
214
215 out
216}
217
218pub fn generate_ldpc_like(
219 rows: usize,
220 cols: usize,
221 col_weight: usize,
222 seed: u64,
223) -> Vec<SparseCol> {
224 let mut rng = XorShift64::new(seed);
225 let mut out = Vec::with_capacity(cols);
226
227 for _ in 0..cols {
228 let mut picked = std::collections::BTreeSet::new();
229 while picked.len() < col_weight {
230 picked.insert(rng.gen_range_usize(rows) as u32);
231 }
232 out.push(picked.into_iter().collect());
233 }
234
235 out
236}
237
238pub fn generate_banded(
239 rows: usize,
240 cols: usize,
241 bandwidth: usize,
242 weight: usize,
243 seed: u64,
244) -> Vec<SparseCol> {
245 let mut rng = XorShift64::new(seed);
246 let mut out = Vec::with_capacity(cols);
247
248 for c in 0..cols {
249 let center = if cols > 1 { (c * rows) / cols } else { 0 };
250 let lo = center.saturating_sub(bandwidth / 2);
251 let hi = (center + bandwidth / 2 + 1).min(rows);
252 let target = weight.min(hi.saturating_sub(lo)).max(1);
253
254 let mut picked = std::collections::BTreeSet::new();
255 while picked.len() < target {
256 let rr = lo + rng.gen_range_usize(hi - lo);
257 picked.insert(rr as u32);
258 }
259 out.push(picked.into_iter().collect());
260 }
261
262 out
263}
264
265fn sparse_to_dense_col(rows: usize, col: &[u32]) -> DenseCol {
266 let words_per_col = (rows + 63) / 64;
267 let mut words = vec![0u64; words_per_col];
268 for &r in col {
269 let rr = r as usize;
270 words[rr / 64] |= 1u64 << (rr % 64);
271 }
272 DenseCol { words }
273}
274
275fn sparse_to_packed_col(rows: usize, col: &[u32]) -> PackedCol {
276 let dense = sparse_to_dense_col(rows, col);
277 let low = col.last().copied();
278 let top_word = low.map(|x| (x as usize / 64) as isize).unwrap_or(-1);
279 PackedCol {
280 words: dense.words,
281 top_word,
282 low,
283 }
284}
285
286fn sym_diff_sorted_in_place(a: &mut Vec<u32>, b: &[u32]) {
287 let mut out = Vec::with_capacity(a.len() + b.len());
288 let (mut i, mut j) = (0usize, 0usize);
289
290 while i < a.len() && j < b.len() {
291 let av = a[i];
292 let bv = b[j];
293 if av < bv {
294 out.push(av);
295 i += 1;
296 } else if av > bv {
297 out.push(bv);
298 j += 1;
299 } else {
300 i += 1;
301 j += 1;
302 }
303 }
304
305 out.extend_from_slice(&a[i..]);
306 out.extend_from_slice(&b[j..]);
307 *a = out;
308}
309
310fn xor_words_in_place(a: &mut [u64], b: &[u64]) {
311 for (x, y) in a.iter_mut().zip(b.iter()) {
312 *x ^= *y;
313 }
314}
315
316fn low_dense(words: &[u64]) -> Option<u32> {
317 for (w_idx, &w) in words.iter().enumerate().rev() {
318 if w != 0 {
319 let bit = 63 - w.leading_zeros() as usize;
320 return Some((w_idx * 64 + bit) as u32);
321 }
322 }
323 None
324}
325
326fn low_packed_from(words: &[u64], mut top_word: isize) -> (Option<u32>, isize) {
327 while top_word >= 0 {
328 let w = words[top_word as usize];
329 if w != 0 {
330 let bit = 63 - w.leading_zeros() as usize;
331 return (Some((top_word as usize * 64 + bit) as u32), top_word);
332 }
333 top_word -= 1;
334 }
335 (None, -1)
336}
337
338fn xor_words_active_prefix(a: &mut PackedCol, b: &PackedCol) {
339 if a.top_word < 0 {
340 return;
341 }
342 let hi = a.top_word as usize;
343 for i in 0..=hi {
344 a.words[i] ^= b.words[i];
345 }
346 let (low, top_word) = low_packed_from(&a.words, a.top_word);
347 a.low = low;
348 a.top_word = top_word;
349}
350
351#[cfg(test)]
352mod tests {
353 use super::*;
354
355 fn assert_all_agree(rows: usize, cols: &[SparseCol]) {
356 let s = reduce_with_strategy(rows, cols, Strategy::SparseList);
357 let p = reduce_with_strategy(rows, cols, Strategy::PackedCached);
358 let d = reduce_with_strategy(rows, cols, Strategy::DenseMacro);
359 let a = reduce_with_strategy(rows, cols, Strategy::Auto);
360
361 assert_eq!(s, p);
362 assert_eq!(s, d);
363 assert_eq!(s, a);
364 }
365
366 #[test]
367 fn er_strategies_agree() {
368 let cols = generate_er_sparse(256, 256, 0.03, 1337);
369 assert_all_agree(256, &cols);
370 }
371
372 #[test]
373 fn ldpc_strategies_agree() {
374 let cols = generate_ldpc_like(256, 512, 6, 7331);
375 assert_all_agree(256, &cols);
376 }
377
378 #[test]
379 fn banded_strategies_agree() {
380 let cols = generate_banded(256, 256, 32, 8, 4242);
381 assert_all_agree(256, &cols);
382 }
383}
384
385pub mod abi;
386
387pub mod io;