Skip to main content

fprint_mindtct/
num.rs

1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! Bit-exact numeric primitives shared across the port: `sround` (round-half-away-from-zero),
6//! `trunc_dbl_precision` (fixed-scale quantization), and the stable bubble-sort group the stock C
7//! relies on wherever ordering matters. All arithmetic is `f64` (the sole `f32` exception,
8//! `xytreps`'s `degrees_per_unit`, lives in `xyt`). See `docs/mindtct-algorithm.md` §Bit-exactness.
9//!
10//! These reproduce the corresponding `lfs.h` macros and `sort.c` routines *verbatim*: the same
11//! rounding direction, the same truncating `(int)` casts, and the same strict-`>` / strict-`<`
12//! comparisons — the latter being what makes every sort **stable** (equal keys never swap, so their
13//! input order is preserved). Nothing here allocates beyond the index vectors the `sort_indices_*`
14//! helpers are defined to return.
15
16/// Round half away from zero, then truncate to `i32` — the `lfs.h` `sround` macro.
17///
18/// Stock: `((int)(((x)<0) ? (x)-0.5 : (x)+0.5))`. A positive value gets `+0.5`, a negative value
19/// `-0.5`, and the `(int)` cast then truncates toward zero — so `2.5 -> 3` and `-2.5 -> -3` (half
20/// rounds *away* from zero, not to-even). Equivalent to `(x + copysign(0.5, x)).trunc()` for every
21/// value except `-0.0`, where stock's `(x)<0` test is false and takes the `+0.5` branch, matched
22/// here. The `as i32` truncation mirrors C's `(int)` cast over the ranges MINDTCT feeds it.
23pub(crate) fn sround(x: f64) -> i32 {
24    (if x < 0.0 { x - 0.5 } else { x + 0.5 }) as i32
25}
26
27/// Quantize `x` to a multiple of `1.0 / scale`, matching the `lfs.h` `trunc_dbl_precision` macro.
28///
29/// Stock: `((double)(((x)<0.0) ? ((int)((x)*(scale)-0.5))/(scale) : ((int)((x)*(scale)+0.5))/(scale)))`.
30/// Multiply by `scale`, round half away from zero via the signed `±0.5`, truncate to `int`, then
31/// divide back out as a `double`. MINDTCT calls this with `scale = TRUNC_SCALE` (16384) to strip
32/// sub-`1/16384` noise so intermediate `f64` results are reproducible bit-for-bit.
33pub(crate) fn trunc_dbl_precision(x: f64, scale: f64) -> f64 {
34    let scaled = x * scale;
35    let n = if x < 0.0 {
36        (scaled - 0.5) as i32
37    } else {
38        (scaled + 0.5) as i32
39    };
40    f64::from(n) / scale
41}
42
43/// Stable bubble-sort core shared by the `*_2` routines: sort `ranks` ascending (or by whatever
44/// `should_swap` decides) while carrying `items` along in lockstep.
45///
46/// Faithful to `sort.c`: an outer "did anything swap?" loop with a shrinking `n`, an inner
47/// adjacent-pair scan, and a swap guarded by a *strict* comparison so equal keys are left untouched
48/// — the property that keeps the sort stable. `should_swap(ranks[p], ranks[p+1])` returns whether
49/// the pair is out of order.
50fn bubble_2<R: Copy>(ranks: &mut [R], items: &mut [i32], should_swap: impl Fn(R, R) -> bool) {
51    debug_assert_eq!(ranks.len(), items.len());
52    let mut n = ranks.len();
53    let mut done = false;
54    while !done {
55        done = true;
56        for p in 0..n.saturating_sub(1) {
57            if should_swap(ranks[p], ranks[p + 1]) {
58                ranks.swap(p, p + 1);
59                items.swap(p, p + 1);
60                done = false;
61            }
62        }
63        n = n.saturating_sub(1);
64    }
65}
66
67/// `bubble_sort_int_inc_2`: sort integer `ranks` into increasing order, carrying `items`.
68pub(crate) fn bubble_sort_int_inc_2(ranks: &mut [i32], items: &mut [i32]) {
69    bubble_2(ranks, items, |a, b| a > b);
70}
71
72/// `bubble_sort_double_inc_2`: sort double `ranks` into increasing order, carrying `items`.
73pub(crate) fn bubble_sort_double_inc_2(ranks: &mut [f64], items: &mut [i32]) {
74    bubble_2(ranks, items, |a, b| a > b);
75}
76
77/// `bubble_sort_double_dec_2`: sort double `ranks` into decreasing order, carrying `items`.
78pub(crate) fn bubble_sort_double_dec_2(ranks: &mut [f64], items: &mut [i32]) {
79    bubble_2(ranks, items, |a, b| a < b);
80}
81
82/// `bubble_sort_int_inc`: sort integer `ranks` into increasing order in place (no carried items).
83pub(crate) fn bubble_sort_int_inc(ranks: &mut [i32]) {
84    let mut n = ranks.len();
85    let mut done = false;
86    while !done {
87        done = true;
88        for p in 0..n.saturating_sub(1) {
89            if ranks[p] > ranks[p + 1] {
90                ranks.swap(p, p + 1);
91                done = false;
92            }
93        }
94        n = n.saturating_sub(1);
95    }
96}
97
98/// `sort_indices_int_inc`: sort `ranks` ascending in place and return the permutation of original
99/// indices (`0..len`) that produces that order — the stock C's `order` output.
100pub(crate) fn sort_indices_int_inc(ranks: &mut [i32]) -> Vec<i32> {
101    let mut order: Vec<i32> = (0..ranks.len()).map(|i| i as i32).collect();
102    bubble_sort_int_inc_2(ranks, &mut order);
103    order
104}
105
106/// `sort_indices_double_inc`: sort `ranks` ascending in place and return the permutation of original
107/// indices (`0..len`) that produces that order — the stock C's `order` output.
108///
109/// The `double` twin of the wired [`sort_indices_int_inc`]. The V2 pipeline sorts only integer ranks,
110/// so this variant has no caller; it is transcribed for fidelity and compiled only for the test below.
111#[cfg(test)]
112pub(crate) fn sort_indices_double_inc(ranks: &mut [f64]) -> Vec<i32> {
113    let mut order: Vec<i32> = (0..ranks.len()).map(|i| i as i32).collect();
114    bubble_sort_double_inc_2(ranks, &mut order);
115    order
116}
117
118#[cfg(test)]
119mod tests {
120    use super::*;
121
122    // --- sround: round half away from zero, then truncate toward zero -------------------------
123    #[test]
124    fn sround_matches_stock_macro() {
125        assert_eq!(sround(0.0), 0);
126        assert_eq!(sround(0.4), 0);
127        assert_eq!(sround(0.5), 1);
128        assert_eq!(sround(0.6), 1);
129        assert_eq!(sround(1.49), 1);
130        assert_eq!(sround(2.5), 3); // half rounds AWAY from zero, not to-even
131
132        // Negative side: -0.5 branch, still truncating toward zero.
133        assert_eq!(sround(-0.4), 0);
134        assert_eq!(sround(-0.5), -1);
135        assert_eq!(sround(-0.6), -1);
136        assert_eq!(sround(-2.5), -3);
137        // -0.0 takes the (x)<0 == false / +0.5 branch, exactly like the C macro.
138        assert_eq!(sround(-0.0), 0);
139    }
140
141    // --- trunc_dbl_precision: quantize to 1/scale --------------------------------------------
142    #[test]
143    fn trunc_dbl_precision_quantizes_to_scale() {
144        let s = 16384.0_f64; // TRUNC_SCALE
145
146        // Exactly representable multiples pass through unchanged.
147        assert_eq!(trunc_dbl_precision(0.0, s), 0.0);
148        assert_eq!(trunc_dbl_precision(1.0, s), 1.0);
149        assert_eq!(trunc_dbl_precision(-1.0, s), -1.0);
150        assert_eq!(trunc_dbl_precision(0.5, s), 0.5);
151        assert_eq!(trunc_dbl_precision(-0.5, s), -0.5);
152
153        // A value landing on x*scale == 1.5 rounds half away from zero to 2 units.
154        assert_eq!(trunc_dbl_precision(3.0 / 32768.0, s), 2.0 / 16384.0);
155        assert_eq!(trunc_dbl_precision(-3.0 / 32768.0, s), -2.0 / 16384.0);
156
157        // Result is always an integer multiple of 1/scale.
158        let q = trunc_dbl_precision(0.123_456_789, s);
159        assert_eq!((q * s).round(), q * s);
160    }
161
162    // --- stable bubble sorts ------------------------------------------------------------------
163    #[test]
164    fn bubble_sort_int_inc_sorts_ascending() {
165        let mut v = [3, 1, 2, 1, 0];
166        bubble_sort_int_inc(&mut v);
167        assert_eq!(v, [0, 1, 1, 2, 3]);
168    }
169
170    #[test]
171    fn bubble_sort_int_inc_2_is_stable() {
172        let mut ranks = [2, 1, 1, 0];
173        let mut items = [0, 1, 2, 3];
174        bubble_sort_int_inc_2(&mut ranks, &mut items);
175        assert_eq!(ranks, [0, 1, 1, 2]);
176        // The two equal keys (rank 1) keep their input order: item 1 before item 2.
177        assert_eq!(items, [3, 1, 2, 0]);
178    }
179
180    #[test]
181    fn bubble_sort_double_inc_2_is_stable() {
182        let mut ranks = [2.0, 1.0, 1.0, 0.0];
183        let mut items = [0, 1, 2, 3];
184        bubble_sort_double_inc_2(&mut ranks, &mut items);
185        assert_eq!(ranks, [0.0, 1.0, 1.0, 2.0]);
186        assert_eq!(items, [3, 1, 2, 0]);
187    }
188
189    #[test]
190    fn bubble_sort_double_dec_2_is_stable() {
191        let mut ranks = [1.0, 3.0, 2.0, 3.0];
192        let mut items = [0, 1, 2, 3];
193        bubble_sort_double_dec_2(&mut ranks, &mut items);
194        assert_eq!(ranks, [3.0, 3.0, 2.0, 1.0]);
195        // The two equal keys (rank 3.0) keep their input order: item 1 before item 3.
196        assert_eq!(items, [1, 3, 2, 0]);
197    }
198
199    #[test]
200    fn sort_indices_int_inc_returns_permutation() {
201        let mut ranks = [30, 10, 20];
202        let order = sort_indices_int_inc(&mut ranks);
203        assert_eq!(ranks, [10, 20, 30]);
204        assert_eq!(order, [1, 2, 0]);
205    }
206
207    #[test]
208    fn sort_indices_double_inc_returns_permutation() {
209        let mut ranks = [30.0, 10.0, 20.0];
210        let order = sort_indices_double_inc(&mut ranks);
211        assert_eq!(ranks, [10.0, 20.0, 30.0]);
212        assert_eq!(order, [1, 2, 0]);
213    }
214
215    // Empty and single-element inputs must not loop forever or panic.
216    #[test]
217    fn sorts_handle_degenerate_lengths() {
218        let mut empty: [i32; 0] = [];
219        bubble_sort_int_inc(&mut empty);
220        let mut one = [42];
221        bubble_sort_int_inc(&mut one);
222        assert_eq!(one, [42]);
223
224        let mut r0: [i32; 0] = [];
225        assert_eq!(sort_indices_int_inc(&mut r0), Vec::<i32>::new());
226    }
227}