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}