Skip to main content

fprint_mindtct/detect/
matchpat.rs

1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! The fixed 2×3 pixel-pair feature patterns and the routines that match them against the binary
6//! image to flag ridge endings and bifurcations — port of stock NBIS
7//! `mindtct/src/lib/mindtct/matchpat.c` (`match_{1st,2nd,3rd}_pair`,
8//! `skip_repeated_{horizontal,vertical}_pair`) and the `feature_patterns[]` table from `globals.c`.
9//!
10//! A candidate minutia is a run of three consecutive pixel *pairs* along a scan (two adjacent rows
11//! for a horizontal scan, two adjacent columns for a vertical one). Each of the ten
12//! [`FEATURE_PATTERNS`] fixes the top/left and bottom/right pixel of the first, second and third
13//! pair; a location matches a pattern only when all three pairs agree. The scan narrows the
14//! candidate set one pair at a time — [`match_1st_pair`] seeds it from the first pair,
15//! [`match_2nd_pair`] and [`match_3rd_pair`] filter it — while
16//! [`skip_repeated_horizontal_pair`]/[`skip_repeated_vertical_pair`] slide across runs of the
17//! repeated second pair so the third pair is tested at the far edge of the feature. See
18//! `docs/mindtct-algorithm.md`.
19
20use super::{BIFURCATION, RIDGE_ENDING};
21
22/// Number of feature patterns — stock `NFEATURES` (`lfs.h` L151).
23pub(crate) const NFEATURES: usize = 10;
24
25/// One entry of the stock `feature_patterns[]` table — the port's analogue of `FEATURE_PATTERN`
26/// (`lfs.h` L178–L184), one field per member.
27///
28/// A pattern fixes three ordered pixel pairs (`first`, `second`, `third`). Each pair is
29/// `[top_or_left, bottom_or_right]` and each pixel is a *binary* value in stock detect convention
30/// (`0 == valley/white`, `1 == ridge/black`) — the same domain as the `bdata` the scan reads
31/// (`detect.c` L614 `gray2bin(1, 1, 0)`), so the stored `u8`s compare directly against scan pixels.
32///
33/// The stock struct carries `int type` (`RIDGE_ENDING`/`BIFURCATION`) and `int appearing`
34/// (`APPEARING`/`DISAPPEARING`); here `type` becomes [`kind`](Self::kind) (a Rust keyword) and
35/// `appearing` becomes a `bool` (`APPEARING == true`), mirroring the fields of
36/// [`DetMinutia`](super::DetMinutia) that a match copies out.
37#[derive(Clone, Copy, Debug, PartialEq, Eq)]
38pub(crate) struct FeaturePattern {
39    /// Feature class, [`RIDGE_ENDING`](super::RIDGE_ENDING) or
40    /// [`BIFURCATION`](super::BIFURCATION) (stock `type`).
41    pub kind: i32,
42    /// Ridge-scan polarity: `true` = `APPEARING`, `false` = `DISAPPEARING` (stock `appearing`).
43    pub appearing: bool,
44    /// First pixel pair `[top_or_left, bottom_or_right]` (stock `first[2]`).
45    pub first: [u8; 2],
46    /// Second pixel pair (stock `second[2]`).
47    pub second: [u8; 2],
48    /// Third pixel pair (stock `third[2]`).
49    pub third: [u8; 2],
50}
51
52/// The fixed table of minutia feature patterns — verbatim from stock `feature_patterns[]`
53/// (`globals.c` L255–L314). The ten entries are the three vertical-pair definitions for a ridge
54/// ending (appearing/disappearing) followed by eight bifurcation variants; a matched location's
55/// index into this table becomes the stock `feature_id` (and thus `possible[0]`).
56///
57// PORT: `APPEARING`/`DISAPPEARING` (`lfs.h` L154–L155, `1`/`0`) collapse into the `appearing`
58// `bool`; the `{0,1}` pixel literals become `u8`. The table is a `const` (read-only, no interior
59// mutability) rather than the C file-scope array; order is preserved so indices match the reference.
60pub(crate) const FEATURE_PATTERNS: [FeaturePattern; NFEATURES] = [
61    // a. Ridge Ending (appearing).
62    FeaturePattern {
63        kind: RIDGE_ENDING,
64        appearing: true,
65        first: [0, 0],
66        second: [0, 1],
67        third: [0, 0],
68    },
69    // b. Ridge Ending (disappearing).
70    FeaturePattern {
71        kind: RIDGE_ENDING,
72        appearing: false,
73        first: [0, 0],
74        second: [1, 0],
75        third: [0, 0],
76    },
77    // c. Bifurcation (disappearing).
78    FeaturePattern {
79        kind: BIFURCATION,
80        appearing: false,
81        first: [1, 1],
82        second: [0, 1],
83        third: [1, 1],
84    },
85    // d. Bifurcation (appearing).
86    FeaturePattern {
87        kind: BIFURCATION,
88        appearing: true,
89        first: [1, 1],
90        second: [1, 0],
91        third: [1, 1],
92    },
93    // e. Bifurcation (disappearing).
94    FeaturePattern {
95        kind: BIFURCATION,
96        appearing: false,
97        first: [1, 0],
98        second: [0, 1],
99        third: [1, 1],
100    },
101    // f. Bifurcation (disappearing).
102    FeaturePattern {
103        kind: BIFURCATION,
104        appearing: false,
105        first: [1, 1],
106        second: [0, 1],
107        third: [1, 0],
108    },
109    // g. Bifurcation (appearing).
110    FeaturePattern {
111        kind: BIFURCATION,
112        appearing: true,
113        first: [1, 1],
114        second: [1, 0],
115        third: [0, 1],
116    },
117    // h. Bifurcation (appearing).
118    FeaturePattern {
119        kind: BIFURCATION,
120        appearing: true,
121        first: [0, 1],
122        second: [1, 0],
123        third: [1, 1],
124    },
125    // i. Bifurcation (disappearing).
126    FeaturePattern {
127        kind: BIFURCATION,
128        appearing: false,
129        first: [1, 0],
130        second: [0, 1],
131        third: [1, 0],
132    },
133    // j. Bifurcation (appearing).
134    FeaturePattern {
135        kind: BIFURCATION,
136        appearing: true,
137        first: [0, 1],
138        second: [1, 0],
139        third: [0, 1],
140    },
141];
142
143/// Feature-pattern indices whose **first** pixel pair equals `(p1, p2)` — port of stock
144/// `match_1st_pair` (`matchpat.c` L82).
145///
146/// Seeds the candidate set for a scan location. The stock out-parameters `possible[]`/`nposs`
147/// collapse into the returned `Vec` (stock `nposs` is `.len()`); the returned indices are in
148/// ascending table order, exactly as the reference fills `possible[]`.
149pub(crate) fn match_1st_pair(p1: u8, p2: u8) -> Vec<usize> {
150    // PORT L88–L100: `nposs = 0`, then keep every feature whose first pair matches the scan pair.
151    let mut possible = Vec::new();
152    for (i, fp) in FEATURE_PATTERNS.iter().enumerate() {
153        if p1 == fp.first[0] && p2 == fp.first[1] {
154            possible.push(i);
155        }
156    }
157    // PORT L102–L103: return the accumulated possibilities.
158    possible
159}
160
161/// Subset of `possible` whose **second** pixel pair equals `(p1, p2)` — port of stock
162/// `match_2nd_pair` (`matchpat.c` L122).
163///
164/// Filters the candidate set produced by [`match_1st_pair`], preserving order. A pair whose two
165/// pixels are equal can never be a second pair (every pattern's `second` differs across the pair),
166/// so it short-circuits to empty.
167pub(crate) fn match_2nd_pair(p1: u8, p2: u8, possible: &[usize]) -> Vec<usize> {
168    // PORT L134–L136: equal pixels cannot form a second pair — return no possibilities.
169    if p1 == p2 {
170        return Vec::new();
171    }
172
173    // PORT L131/L138–L148: reset output, then retain candidates whose second pair matches.
174    let mut out = Vec::new();
175    for &i in possible {
176        if p1 == FEATURE_PATTERNS[i].second[0] && p2 == FEATURE_PATTERNS[i].second[1] {
177            out.push(i);
178        }
179    }
180    // PORT L150–L151: return the surviving possibilities.
181    out
182}
183
184/// Subset of `possible` whose **third** pixel pair equals `(p1, p2)` — port of stock
185/// `match_3rd_pair` (`matchpat.c` L170).
186///
187/// The final filter of the candidate set; the surviving indices identify the matched feature(s),
188/// with `possible[0]` the accepted `feature_id`. Unlike [`match_2nd_pair`] there is no equal-pixel
189/// guard (a ridge-ending pattern's third pair is `{0, 0}`).
190pub(crate) fn match_3rd_pair(p1: u8, p2: u8, possible: &[usize]) -> Vec<usize> {
191    // PORT L179/L181–L191: reset output, then retain candidates whose third pair matches.
192    let mut out = Vec::new();
193    for &i in possible {
194        if p1 == FEATURE_PATTERNS[i].third[0] && p2 == FEATURE_PATTERNS[i].third[1] {
195            out.push(i);
196        }
197    }
198    // PORT L193–L194: return the surviving possibilities.
199    out
200}
201
202/// Slide a horizontal pixel-pair cursor rightward across repeats of the current pair — port of stock
203/// `skip_repeated_horizontal_pair` (`matchpat.c` L216).
204///
205/// `p1`/`p2` are byte indices into `bdata` for the top and bottom pixel of the pair (the stock
206/// `p1ptr`/`p2ptr`), and `cx` is their shared X-coordinate. The cursor is bumped one column right,
207/// then advanced while the pair keeps repeating the *starting* pair, stopping at the first differing
208/// pair or when `cx` reaches the region's right edge `ex`. On return `cx`, `p1` and `p2` mark where
209/// the skip terminated. This lets the scan test the third pair against the pixels immediately past
210/// the run of identical second pairs.
211///
212// PORT: the stock signature also takes `iw`/`ih`; both are unused in the horizontal skip (the step
213// is `+1`), so they are omitted here. The `unsigned char **p1ptr`/`**p2ptr` pointer-to-pointer
214// out-parameters become `&mut usize` byte indices into `bdata`; the terminal index is bumped one
215// past the last compared pixel but never dereferenced (the `cx < ex` guard), matching the C.
216pub(crate) fn skip_repeated_horizontal_pair(
217    cx: &mut i32,
218    ex: i32,
219    p1: &mut usize,
220    p2: &mut usize,
221    bdata: &[u8],
222) {
223    // PORT L222–L223: remember the starting pixel pair.
224    let old1 = bdata[*p1];
225    let old2 = bdata[*p2];
226
227    // PORT L226–L229: bump horizontally to the next pixel pair.
228    *cx += 1;
229    *p1 += 1;
230    *p2 += 1;
231
232    // PORT L231–L242: advance while the pair keeps repeating and the region is not exhausted.
233    while *cx < ex {
234        if bdata[*p1] != old1 || bdata[*p2] != old2 {
235            return;
236        }
237        *cx += 1;
238        *p1 += 1;
239        *p2 += 1;
240    }
241}
242
243/// Slide a vertical pixel-pair cursor downward across repeats of the current pair — port of stock
244/// `skip_repeated_vertical_pair` (`matchpat.c` L264).
245///
246/// The vertical analogue of [`skip_repeated_horizontal_pair`]: `p1`/`p2` are byte indices for the
247/// left and right pixel of the pair and `cy` their shared Y-coordinate. Each step advances by one
248/// image row (`iw` bytes) rather than one column, stopping at the first differing pair or when `cy`
249/// reaches the region's bottom edge `ey`.
250///
251// PORT: the stock signature also takes `ih` (unused; the row step is `iw`), so it is omitted. As in
252// the horizontal case the pointer-to-pointer out-parameters become `&mut usize` byte indices; the
253// per-step increment is `iw` (`p1ptr += iw`).
254pub(crate) fn skip_repeated_vertical_pair(
255    cy: &mut i32,
256    ey: i32,
257    p1: &mut usize,
258    p2: &mut usize,
259    iw: i32,
260    bdata: &[u8],
261) {
262    // PORT L270–L271: remember the starting pixel pair.
263    let old1 = bdata[*p1];
264    let old2 = bdata[*p2];
265
266    // PORT L274–L277: bump vertically (one row = `iw` bytes) to the next pixel pair.
267    let step = iw as usize;
268    *cy += 1;
269    *p1 += step;
270    *p2 += step;
271
272    // PORT L279–L290: advance while the pair keeps repeating and the region is not exhausted.
273    while *cy < ey {
274        if bdata[*p1] != old1 || bdata[*p2] != old2 {
275            return;
276        }
277        *cy += 1;
278        *p1 += step;
279        *p2 += step;
280    }
281}
282
283#[cfg(test)]
284mod tests {
285    use super::*;
286
287    #[test]
288    fn table_matches_reference() {
289        // Length and the two anchor entries transcribed straight from globals.c.
290        assert_eq!(FEATURE_PATTERNS.len(), NFEATURES);
291        assert_eq!(
292            FEATURE_PATTERNS[0],
293            FeaturePattern {
294                kind: RIDGE_ENDING,
295                appearing: true,
296                first: [0, 0],
297                second: [0, 1],
298                third: [0, 0],
299            }
300        );
301        assert_eq!(
302            FEATURE_PATTERNS[9],
303            FeaturePattern {
304                kind: BIFURCATION,
305                appearing: true,
306                first: [0, 1],
307                second: [1, 0],
308                third: [0, 1],
309            }
310        );
311    }
312
313    #[test]
314    fn first_pair_seeds_in_table_order() {
315        // `{0,0}` is the first pair of the two ridge-ending patterns (indices 0, 1), in order.
316        assert_eq!(match_1st_pair(0, 0), vec![0, 1]);
317        // `{1,1}` is the first pair of patterns c, d, f, g (indices 2, 3, 5, 6).
318        assert_eq!(match_1st_pair(1, 1), vec![2, 3, 5, 6]);
319        // `{1,0}` seeds e and i; `{0,1}` seeds h and j.
320        assert_eq!(match_1st_pair(1, 0), vec![4, 8]);
321        assert_eq!(match_1st_pair(0, 1), vec![7, 9]);
322    }
323
324    #[test]
325    fn full_match_narrows_to_ridge_ending_appearing() {
326        // Walk pattern a end to end: first {0,0} -> second {0,1} -> third {0,0}.
327        let p = match_1st_pair(0, 0);
328        assert_eq!(p, vec![0, 1]);
329        let p = match_2nd_pair(0, 1, &p);
330        assert_eq!(p, vec![0]);
331        let p = match_3rd_pair(0, 0, &p);
332        assert_eq!(p, vec![0]);
333        assert_eq!(FEATURE_PATTERNS[p[0]].kind, RIDGE_ENDING);
334        assert!(FEATURE_PATTERNS[p[0]].appearing);
335    }
336
337    #[test]
338    fn second_pair_rejects_equal_pixels() {
339        // A pair of identical pixels can never be a valid second pair.
340        assert!(match_2nd_pair(0, 0, &[0, 1, 2]).is_empty());
341        assert!(match_2nd_pair(1, 1, &[2, 3]).is_empty());
342    }
343
344    #[test]
345    fn third_pair_disambiguates_bifurcations() {
346        // e and f share first {1,1}?  No: seed {1,0} then {0,1} keeps e (idx 4) and i (idx 8);
347        // third {1,1} accepts only e, third {1,0} only i.
348        let seed = match_1st_pair(1, 0);
349        assert_eq!(seed, vec![4, 8]);
350        let second = match_2nd_pair(0, 1, &seed);
351        assert_eq!(second, vec![4, 8]);
352        assert_eq!(match_3rd_pair(1, 1, &second), vec![4]);
353        assert_eq!(match_3rd_pair(1, 0, &second), vec![8]);
354    }
355
356    #[test]
357    fn horizontal_skip_stops_at_first_differing_pair() {
358        // iw = 4. Row 0: 0 0 0 1 ; row 1: 1 1 1 1.  Pair (top,bottom) is (0,1) at x=0,1,2 then
359        // (1,1) at x=3.  Starting at x=0 the skip slides to x=3 where the top pixel changes.
360        let bdata = [0u8, 0, 0, 1, /* row 1 */ 1, 1, 1, 1];
361        let mut cx = 0i32;
362        let mut p1 = 0usize; // (row 0, col 0)
363        let mut p2 = 4usize; // (row 1, col 0)
364        skip_repeated_horizontal_pair(&mut cx, 4, &mut p1, &mut p2, &bdata);
365        assert_eq!((cx, p1, p2), (3, 3, 7));
366    }
367
368    #[test]
369    fn horizontal_skip_terminates_at_region_edge() {
370        // Every pair identical: the skip runs to the right edge `ex` and stops there.
371        let bdata = [0u8, 0, 0, 0, /* row 1 */ 1, 1, 1, 1];
372        let mut cx = 0i32;
373        let mut p1 = 0usize;
374        let mut p2 = 4usize;
375        skip_repeated_horizontal_pair(&mut cx, 4, &mut p1, &mut p2, &bdata);
376        assert_eq!(cx, 4);
377    }
378
379    #[test]
380    fn vertical_skip_stops_at_first_differing_pair() {
381        // iw = 2, 4 rows.  Left/right columns:
382        //   row 0: 0 1   row 1: 0 1   row 2: 0 1   row 3: 1 1
383        // Pair (left,right) is (0,1) for rows 0..2 then (1,1) at row 3.
384        let bdata = [
385            0u8, 1, /* r1 */ 0, 1, /* r2 */ 0, 1, /* r3 */ 1, 1,
386        ];
387        let mut cy = 0i32;
388        let mut p1 = 0usize; // (row 0, col 0)
389        let mut p2 = 1usize; // (row 0, col 1)
390        skip_repeated_vertical_pair(&mut cy, 4, &mut p1, &mut p2, 2, &bdata);
391        assert_eq!((cy, p1, p2), (3, 6, 7));
392    }
393}