Skip to main content

leto_ops/application/
triangular.rs

1//! Rank-2 triangular masking (tril / triu): [`triangular_into`](crate::application::triangular::triangular_into) and [`triangular`].
2//!
3//! CPU counterpart of `hephaestus_core::TriangularOps` (1:1 parity):
4//! `output[row, col]` copies the input when the element is on the kept side
5//! of the diagonal offset by `diagonal`, else [`NumericElement::ZERO`](eunomia::NumericElement::ZERO).
6//! [`TriangularMode::Lower`](crate::application::triangular::TriangularMode::Lower) keeps `col <= row + diagonal` (numpy's `tril`:
7//! `diagonal = 0` is the main diagonal, positive shifts it up-right,
8//! negative down-left); [`TriangularMode::Upper`](crate::application::triangular::TriangularMode::Upper) keeps
9//! `col >= row + diagonal` (numpy's `triu`, the mirror condition).
10//!
11//! [`triangular_keeps`](crate::application::triangular::triangular_keeps) ports the device seam's predicate verbatim — the
12//! same overflow-safe `u128` comparison, including the `usize`/`i64`
13//! extremes — so host and device agree cell for cell on every input.
14//! Zero-copy: masking writes directly into the caller-owned output view,
15//! holding only scalar registers besides the two buffers.
16
17use crate::application::index::validate_mutable_output;
18use crate::domain::scalar::Scalar;
19use leto::{Array, ArrayView, ArrayViewMut, Layout, LetoError, Result, VecStorage};
20
21/// Which side of the diagonal survives.
22#[derive(Clone, Copy, Debug, PartialEq, Eq)]
23pub enum TriangularMode {
24    /// Keep `col <= row + diagonal` (numpy's `tril`).
25    Lower,
26    /// Keep `col >= row + diagonal` (numpy's `triu`).
27    Upper,
28}
29
30/// Whether element `(row, col)` survives `mode`'s mask at the given
31/// `diagonal` offset.
32///
33/// Verbatim port of the `TriangularOps` seam predicate: the difference is
34/// measured in `u128` so `usize::MAX` coordinates and `i64::MIN`/`MAX`
35/// diagonals compare mathematically, without clamping. `const`: the widening
36/// casts are lossless (`usize`/`u64` magnitudes always fit `u128`), and the
37/// sign-extending `diagonal as u128` only evaluates under a `diagonal >= 0`
38/// guard, where it is exact.
39#[inline]
40#[must_use]
41pub const fn triangular_keeps(mode: TriangularMode, row: usize, col: usize, diagonal: i64) -> bool {
42    // Both operands widen to `u128` for the mixed-width compare: the
43    // predicate evaluates in const contexts (the compile-time-asserted
44    // contract in the test), and `usize -> u128` is a lossless widening
45    // for which std provides no `From`/`TryFrom` on 64-bit targets - the
46    // conversion-module class the stack's cast rule names: all three are
47    // lossless 64 -> 128-bit widenings, and `From`'s associated function
48    // is not yet stable as const. The eunomia conversion module owning
49    // these widenings is a separate item.
50    let difference = if col >= row {
51        (true, (col - row) as u128)
52    } else {
53        (false, (row - col) as u128)
54    };
55    let diagonal_magnitude = diagonal.unsigned_abs() as u128;
56    match mode {
57        TriangularMode::Lower => match difference {
58            (true, magnitude) => diagonal >= 0 && magnitude <= diagonal_magnitude,
59            (false, magnitude) => diagonal >= 0 || magnitude >= diagonal_magnitude,
60        },
61        TriangularMode::Upper => match difference {
62            (true, magnitude) => diagonal < 0 || magnitude >= diagonal_magnitude,
63            (false, magnitude) => diagonal < 0 && magnitude <= diagonal_magnitude,
64        },
65    }
66}
67
68/// Row-granular masking for C-contiguous operands: each row copies its kept
69/// run and fills the masked remainder, replacing the per-element branch with
70/// vectorized slice operations. The split point derives from the same
71/// `col <= row + diagonal` / `col >= row + diagonal` boundary
72/// [`triangular_keeps`](crate::application::triangular::triangular_keeps) tests, computed in `i128` so `usize` rows and any
73/// `i64` diagonal combine without overflow or clamping.
74fn triangular_contiguous<T: Scalar>(
75    input: &[T],
76    output: &mut [T],
77    rows: usize,
78    cols: usize,
79    mode: TriangularMode,
80    diagonal: i64,
81) {
82    for row in 0..rows {
83        let base = row * cols;
84        let bound = i128::try_from(row).expect("invariant: row fits i128") + i128::from(diagonal);
85        let split = match mode {
86            // Lower keeps `col <= row + diagonal`: the kept prefix length.
87            TriangularMode::Lower => usize::try_from(
88                (bound + 1).clamp(0, i128::try_from(cols).expect("invariant: cols fits i128")),
89            )
90            .expect("invariant: prefix length fits usize"),
91            // Upper keeps `col >= row + diagonal`: the masked prefix length.
92            TriangularMode::Upper => usize::try_from(
93                bound.clamp(0, i128::try_from(cols).expect("invariant: cols fits i128")),
94            )
95            .expect("invariant: prefix length fits usize"),
96        };
97        let (out_head, out_tail) = output[base..base + cols].split_at_mut(split);
98        let (in_head, in_tail) = input[base..base + cols].split_at(split);
99        match mode {
100            TriangularMode::Lower => {
101                out_head.copy_from_slice(in_head);
102                out_tail.fill(T::ZERO);
103            }
104            TriangularMode::Upper => {
105                out_head.fill(T::ZERO);
106                out_tail.copy_from_slice(in_tail);
107            }
108        }
109    }
110}
111
112/// Mask `input` by `mode` and `diagonal` into `output`, whose shape must
113/// equal `input`'s exactly.
114///
115/// Strided and offset views are served on both operands; the output must be
116/// injective. C-contiguous operands take a row-granular copy/fill fast path
117/// instead of the per-element branch.
118///
119/// # Errors
120///
121/// Returns [`LetoError::ShapeMismatch`] when the output shape differs from
122/// the input shape, and the layout errors for invalid storage lengths or an
123/// aliased output.
124pub fn triangular_into<T: Scalar>(
125    input: &ArrayView<'_, T, 2>,
126    mode: TriangularMode,
127    diagonal: i64,
128    output: &mut ArrayViewMut<'_, T, 2>,
129) -> Result<()> {
130    if output.shape() != input.shape() {
131        return Err(LetoError::ShapeMismatch {
132            lhs: input.shape().to_vec(),
133            rhs: output.shape().to_vec(),
134        });
135    }
136    input.layout().validate_storage_len(input.data().len())?;
137    validate_mutable_output(output, "triangular output")?;
138
139    let [rows, cols] = input.shape();
140    if let (Some(input_slice), Some(output_slice)) = (input.as_slice(), output.as_mut_slice()) {
141        triangular_contiguous(input_slice, output_slice, rows, cols, mode, diagonal);
142        return Ok(());
143    }
144
145    let input_layout = input.layout();
146    let output_layout = output.layout();
147    let input_data = input.data();
148    let output_data = output.data_mut();
149    let input_base = isize::try_from(input_layout.offset()).expect("invariant: offset fits isize");
150    let output_base =
151        isize::try_from(output_layout.offset()).expect("invariant: offset fits isize");
152    let (in_row, in_col) = (input_layout.strides()[0], input_layout.strides()[1]);
153    let (out_row, out_col) = (output_layout.strides()[0], output_layout.strides()[1]);
154    for row in 0..rows {
155        for col in 0..cols {
156            let from = usize::try_from(
157                input_base
158                    + isize::try_from(row).expect("invariant: row fits isize") * in_row
159                    + isize::try_from(col).expect("invariant: col fits isize") * in_col,
160            )
161            .expect("invariant: index fits usize");
162            let to = usize::try_from(
163                output_base
164                    + isize::try_from(row).expect("invariant: row fits isize") * out_row
165                    + isize::try_from(col).expect("invariant: col fits isize") * out_col,
166            )
167            .expect("invariant: index fits usize");
168            output_data[to] = if triangular_keeps(mode, row, col, diagonal) {
169                input_data[from]
170            } else {
171                T::ZERO
172            };
173        }
174    }
175    Ok(())
176}
177
178/// Mask `input` by `mode` and `diagonal` into a newly allocated C-contiguous
179/// output of the input's shape.
180///
181/// See [`triangular_into`] for the contract and errors.
182pub fn triangular<T: Scalar>(
183    input: &ArrayView<'_, T, 2>,
184    mode: TriangularMode,
185    diagonal: i64,
186) -> Result<Array<T, VecStorage<T>, 2>> {
187    let layout = Layout::c_contiguous(input.shape())?;
188    let size = layout.checked_size()?;
189    let storage = VecStorage::fill(size, T::ZERO);
190    let mut output = Array::new(layout, storage)?;
191    triangular_into(input, mode, diagonal, &mut output.view_mut())?;
192    Ok(output)
193}