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}