csa-rhdl 0.1.0

Carry-save adder compressor trees composed via comp-cat-rs, with hdl-cat backend
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

//! Single-level arithmetic: `M` bundles → `floor(M/3)*2 + M%3` bundles.

use crate::category::graph::{LevelEdge, LevelKind};
use comp_cat_rs::collapse::free_category::Vertex;

/// Output bundle count after one CSA reduction stage.
#[must_use]
pub const fn next_bundles(m: usize) -> usize {
    (m / 3) * 2 + m % 3
}

/// Build a single [`LevelEdge`] for a CSA stage of `m` bundles at width `w`.
///
/// `source_idx` is the vertex index of the input shape; the edge
/// targets `source_idx + 1`.
#[must_use]
pub fn tree_level_edge(source_idx: usize, m: usize, w: usize) -> LevelEdge {
    LevelEdge {
        source: Vertex::new(source_idx),
        target: Vertex::new(source_idx + 1),
        kind: LevelKind::Csa { m, w },
    }
}

#[cfg(test)]
mod tests {
    use super::next_bundles;

    #[test]
    fn next_bundles_transitions() {
        let table: [(usize, usize); 8] = [
            (0, 0),
            (1, 1),
            (2, 2),
            (3, 2),
            (4, 3),
            (5, 4),
            (6, 4),
            (9, 6),
        ];
        table
            .iter()
            .for_each(|(m, want)| assert_eq!(next_bundles(*m), *want, "m={m}"));
    }

    #[test]
    fn nine_reduces_to_two_in_four_steps() {
        let steps = std::iter::successors(Some(9usize), |&b| match b {
            0..=2 => None,
            _ => Some(next_bundles(b)),
        })
        .collect::<Vec<_>>();
        assert_eq!(steps, vec![9, 6, 4, 3, 2]);
    }
}