minroot_cat/
interleave.rs

1//! N-way interleaving as a product functor.
2//!
3//! The `MinRoot` hardware interleaves `N` independent fifth-root
4//! computations around a shared pipeline ring.  On each clock cycle,
5//! data from a different computation advances through the stages.
6//!
7//! Categorically, interleaving is a **product functor** `F(X) = X^N`:
8//! it lifts each pipeline object to an N-tuple and each morphism to
9//! a component-wise application with rotation.
10//!
11//! The rotation is a **natural transformation** `σ: F => F` that
12//! cyclically shifts which computation is active.
13
14use comp_cat_rs::foundation::kind::Kind;
15
16/// The product functor `F(X) = [X; N]` for interleaving.
17///
18/// Each element of the array corresponds to one independent
19/// fifth-root computation occupying a slot in the ring.
20pub struct InterleaveK<const N: usize>;
21
22impl<const N: usize> Kind for InterleaveK<N> {
23    type F<A> = [A; N];
24}
25
26/// Rotation: cyclically shifts the active slot.
27///
28/// On each clock cycle, the pipeline advances data for the next
29/// computation.  After `N` cycles, all computations have advanced
30/// by one pipeline stage.
31///
32/// The rotation is a natural transformation (`[A; N] -> [A; N]`
33/// for all `A: Copy`).  It commutes with any per-element operation,
34/// so applying a pipeline stage then rotating is the same as rotating
35/// then applying.
36///
37/// Note: this is not implemented via [`comp_cat_rs::foundation::nat_trans::NatTrans`]
38/// because that trait's `transform<A>` has no bounds on `A`, and we
39/// require `Copy` (moving individual array elements without `Copy` is
40/// not possible in safe Rust without allocation).  The naturality
41/// property holds for all `A: Copy`, which covers all hardware signal
42/// types.
43pub struct Rotate<const N: usize>;
44
45impl<const N: usize> Rotate<N> {
46    /// Rotate the array left by one position.
47    ///
48    /// `[a, b, c, d]` becomes `[b, c, d, a]`.
49    #[must_use]
50    pub fn apply<A: Copy>(arr: [A; N]) -> [A; N] {
51        rotate_left(arr)
52    }
53}
54
55/// Rotates an array left by one position.
56///
57/// `[a, b, c, d]` becomes `[b, c, d, a]`.
58///
59/// Requires `Copy` because we index into the source array
60/// at `(i + 1) % N`, which is always in bounds.
61fn rotate_left<A: Copy, const N: usize>(arr: [A; N]) -> [A; N] {
62    core::array::from_fn(|i| arr[(i + 1) % N])
63}
64
65/// The interleave depth used by the default `MinRoot` hardware.
66///
67/// The original design uses `N = 3` datapaths.  `N` must divide
68/// [`FIFTH_ROOT_CYCLES`](super::traced::FIFTH_ROOT_CYCLES) for
69/// synchronized completion (258 / 3 = 86 exactly).
70pub const DEFAULT_INTERLEAVE: usize = 3;
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn rotate_identity_for_single() {
78        let arr = [42];
79        assert_eq!(Rotate::<1>::apply(arr), [42]);
80    }
81
82    #[test]
83    fn rotate_left_by_one() {
84        let arr = [1, 2, 3, 4];
85        assert_eq!(Rotate::<4>::apply(arr), [2, 3, 4, 1]);
86    }
87
88    #[test]
89    fn rotate_n_times_is_identity() {
90        let arr = [10, 20, 30];
91        let rotated = (0..3).fold(arr, |a, _| Rotate::<3>::apply(a));
92        assert_eq!(rotated, arr);
93    }
94
95    #[test]
96    fn default_interleave_divides_cycles() {
97        assert_eq!(
98            super::super::traced::FIFTH_ROOT_CYCLES % DEFAULT_INTERLEAVE,
99            0
100        );
101    }
102}
minroot_cat/interleave.rs

minroot_cat/
interleave.rs
