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}