Skip to main content

fprint_bozorth3/
inter.rs

1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! Stage 2: the inter-print compatibility table (`bz_match`).
6//!
7//! Walk the two sorted stage-1 Webs and emit one **compatible edge pair** per (probe row, gallery
8//! row) that agrees in edge length (the `TK` distance band, in f32) and in both relative angles
9//! (the `TXS`/`CTXS` integer band). Each output row is
10//! `[ΔθKJ, probe_k, probe_j, gallery_a, gallery_b]`, sorted by `(probe_k, gallery_a, probe_j)`.
11
12use crate::consts::{iangle180, CTXS, TABLE_OVERFLOW_LIMIT, TK, TXS};
13use crate::intra::CompRow;
14
15/// A compatibility-table row: `[delta_theta, probe_k, probe_j, gallery_a, gallery_b]`.
16pub(crate) type ColpRow = [i32; 5];
17
18/// `bz_match`: build the sorted compatibility list from the two pruned Webs.
19///
20/// `probe` and `gallery` are the sorted stage-1 tables already truncated to their pruned lengths
21/// (`prune_len`), so their slice lengths are the `*_ptrlist_len` values. The persistent `st` cursor
22/// and the asymmetric loop bounds (`k` up to `probe.len()-1`, `j` up to `gallery.len()`) are
23/// reproduced exactly.
24pub(crate) fn bz_match(probe: &[CompRow], gallery: &[CompRow]) -> Vec<ColpRow> {
25    let probe_len = probe.len();
26    let gallery_len = gallery.len();
27    let mut rot: Vec<ColpRow> = Vec::new();
28    let mut st: usize = 1;
29
30    'k: for k in 1..probe_len {
31        let ss = &probe[k - 1];
32        let mut j = st;
33        while j <= gallery_len {
34            let ff = &gallery[j - 1];
35
36            // --- distance-agreement test (the sole f32 decision in stage 2) ---
37            let dz = (ff[0] - ss[0]) as f32;
38            let fi = (2.0_f32 * TK) * ((ff[0] + ss[0]) as f32);
39            if dz * dz > fi * fi {
40                if dz < 0.0 {
41                    // Gallery edge shorter than probe edge: advance the persistent start cursor.
42                    st = j + 1;
43                    j += 1;
44                    continue;
45                }
46                // Gallery edge longer and out of band: no later (longer) j can match.
47                break;
48            }
49
50            // --- relative-angle test (integer, exact) ---
51            let mut incompatible = false;
52            for i in 1..3usize {
53                let d = ss[i] - ff[i];
54                // Squared in i64 so an unfolded relative angle cannot overflow the multiply; the
55                // band bounds are the same integers, widened.
56                let d2 = i64::from(d) * i64::from(d);
57                if d2 > i64::from(TXS) && d2 < i64::from(CTXS) {
58                    incompatible = true;
59                    break;
60                }
61            }
62            if incompatible {
63                j += 1;
64                continue;
65            }
66
67            // --- relative rotation (decode the +400 swap flags, then IANGLE180 the difference) ---
68            let (mut p1, n) = if ss[5] >= 220 {
69                (ss[5] - 580, 1)
70            } else {
71                (ss[5], 0)
72            };
73            let (p2, b) = if ff[5] >= 220 {
74                (ff[5] - 580, 1)
75            } else {
76                (ff[5], 0)
77            };
78            p1 -= p2;
79            p1 = iangle180(p1);
80
81            // --- endpoint pairing (flip the gallery pair when the swap flags differ) ---
82            let row: ColpRow = if n != b {
83                [p1, ss[3], ss[4], ff[4], ff[3]]
84            } else {
85                [p1, ss[3], ss[4], ff[3], ff[4]]
86            };
87            rot.push(row);
88            if rot.len() == TABLE_OVERFLOW_LIMIT {
89                break 'k;
90            }
91            j += 1;
92        }
93    }
94
95    // Sort key precedence {1, 3, 2}: probe_k, gallery_a, probe_j. Stable → equal keys keep
96    // generation order, matching the reference's insertion sort.
97    rot.sort_by(|a, b| (a[1], a[3], a[2]).cmp(&(b[1], b[3], b[2])));
98    rot
99}
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104
105    /// One stage-1 row: `[distance, beta_min, beta_max, k+1, j+1, theta_kj]`.
106    fn row(distance: i32, betas: (i32, i32), ids: (i32, i32), theta_kj: i32) -> CompRow {
107        [distance, betas.0, betas.1, ids.0, ids.1, theta_kj]
108    }
109
110    /// A row that agrees with any other `plain` row of the same distance: betas equal, no swap.
111    fn plain(distance: i32, ids: (i32, i32)) -> CompRow {
112        row(distance, (0, 0), ids, 0)
113    }
114
115    #[test]
116    fn bz_match_empty_and_single_row_webs() {
117        // `1..probe_len` is empty below two rows, so there is nothing to pair and nothing to index.
118        assert!(bz_match(&[], &[]).is_empty());
119        assert!(bz_match(&[], &[plain(100, (1, 2))]).is_empty());
120        assert!(bz_match(&[plain(100, (1, 2))], &[]).is_empty());
121        assert!(bz_match(&[plain(100, (1, 2))], &[plain(100, (3, 4))]).is_empty());
122    }
123
124    #[test]
125    fn bz_match_advances_st_across_probe_rows() {
126        // `st` is carried across `k`: once a gallery row is passed as too short, no later probe row
127        // reconsiders it. Sound only because both Webs are distance-sorted, and observable only
128        // from a probe that is not — which stage 1 cannot emit.
129        let gallery = [plain(100, (11, 12)), plain(1000, (13, 14))];
130
131        // Probe descending: the long row first pushes `st` past gallery[0], then the short row
132        // starts at gallery[1] and breaks immediately.
133        let descending = [plain(1000, (1, 2)), plain(100, (3, 4)), plain(100, (5, 6))];
134        let rows = bz_match(&descending, &gallery);
135        assert_eq!(rows.len(), 1, "only the long/long pair survives");
136        assert_eq!(rows[0][1], 1, "and it is probe row 1");
137        assert!(
138            !rows.iter().any(|r| r[1] == 3),
139            "probe row 3 must find nothing: st has already passed the gallery row it matches"
140        );
141
142        // The control: the same probe row 3, same gallery, examined from st = 1 — it matches. So
143        // the absence above is the cursor, not the geometry.
144        let short_first = [plain(100, (3, 4)), plain(100, (5, 6))];
145        let rows = bz_match(&short_first, &gallery);
146        assert_eq!(rows.len(), 1);
147        assert_eq!(
148            (rows[0][1], rows[0][3]),
149            (3, 11),
150            "probe row 3 pairs with gallery row 11 when st has not passed it"
151        );
152    }
153
154    #[test]
155    fn bz_match_breaks_when_gallery_edge_longer() {
156        // A gallery edge longer than the probe edge and out of band ends the row: every later j is
157        // longer still. The long gallery row after it is never paired.
158        let probe = [plain(100, (1, 2)), plain(100, (3, 4))];
159        let gallery = [plain(10_000, (11, 12)), plain(100, (13, 14))];
160        assert!(
161            bz_match(&probe, &gallery).is_empty(),
162            "the break must skip gallery row 13, despite its matching distance"
163        );
164    }
165
166    #[test]
167    fn bz_match_angle_band_boundaries() {
168        // Incompatible when `d*d > TXS && d*d < CTXS` — both strict, so both bounds are kept.
169        for (delta, compatible) in [(11, true), (12, false), (348, false), (349, true)] {
170            let probe = [row(100, (delta, 0), (1, 2), 0), plain(100, (3, 4))];
171            let gallery = [plain(100, (11, 12))];
172            let rows = bz_match(&probe, &gallery);
173            assert_eq!(
174                !rows.is_empty(),
175                compatible,
176                "beta delta {delta} (d*d = {}) should be {}",
177                delta * delta,
178                if compatible { "kept" } else { "rejected" }
179            );
180        }
181    }
182
183    #[test]
184    fn bz_match_decodes_swap_flag_at_220() {
185        let gallery = [plain(100, (11, 12))];
186        let paired = |theta_kj| {
187            let probe = [row(100, (0, 0), (1, 2), theta_kj), plain(100, (3, 4))];
188            bz_match(&probe, &gallery)[0]
189        };
190
191        // Below the threshold: theta_kj is taken as-is, and the gallery pair keeps its order.
192        let unswapped = paired(219);
193        assert_eq!(unswapped[0], iangle180(219), "219 is not a swap flag");
194        assert_eq!((unswapped[3], unswapped[4]), (11, 12));
195
196        // At it: theta_kj decodes as `- 580`, and the differing flags flip the gallery pair.
197        let swapped = paired(220);
198        assert_eq!(swapped[0], iangle180(220 - 580), "220 is a swap flag");
199        assert_eq!(
200            (swapped[3], swapped[4]),
201            (12, 11),
202            "one side swapped, so the gallery endpoints flip"
203        );
204    }
205
206    #[test]
207    fn bz_match_keeps_the_gallery_pair_when_both_sides_are_swapped() {
208        // Flags equal, so no flip — the flip is about disagreement, not about being swapped.
209        let probe = [row(100, (0, 0), (1, 2), 400), plain(100, (3, 4))];
210        let gallery = [row(100, (0, 0), (11, 12), 400)];
211        let rows = bz_match(&probe, &gallery);
212        assert_eq!(rows.len(), 1);
213        assert_eq!((rows[0][3], rows[0][4]), (11, 12));
214    }
215
216    #[test]
217    fn bz_match_sorts_by_probe_k_then_gallery_a_then_probe_j() {
218        // The key precedence is {1, 3, 2}, not (1, 2, 3): gallery_a outranks probe_j. A "tidying"
219        // refactor to the natural column order would reorder the table the cluster stage walks.
220        let probe = [plain(100, (1, 9)), plain(100, (1, 5)), plain(100, (7, 7))];
221        let gallery = [plain(100, (30, 31)), plain(100, (20, 21))];
222        let rows = bz_match(&probe, &gallery);
223        assert!(rows.len() > 2, "need several rows to observe an order");
224        let keys: Vec<_> = rows.iter().map(|r| (r[1], r[3], r[2])).collect();
225        let mut want = keys.clone();
226        want.sort();
227        assert_eq!(
228            keys, want,
229            "rows must ascend by (probe_k, gallery_a, probe_j)"
230        );
231    }
232
233    #[test]
234    fn bz_match_stops_at_table_overflow_limit() {
235        // Unlike stage 1's identical guard, this one is reachable from `match_score`: the pair
236        // count is bounded by the two Webs' lengths, not by the minutia cap.
237        let probe: Vec<CompRow> = (0..201).map(|i| plain(100, (i, i))).collect();
238        let gallery: Vec<CompRow> = (0..101).map(|i| plain(100, (i, i))).collect();
239        assert_eq!(bz_match(&probe, &gallery).len(), TABLE_OVERFLOW_LIMIT);
240    }
241}