fprint_bozorth3/lib.rs
1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! # fprint-bozorth3
6//!
7//! A pure-Rust, dependency-free reimplementation of **BOZORTH3** — NIST NBIS's minutiae fingerprint
8//! matcher, which **tolerates rotation and translation** between two impressions of a finger. Given
9//! two prints as lists of minutiae, it returns an integer match score reproducing the stock NBIS
10//! tool's output; higher means more corresponding ridge structure.
11//!
12//! The two tolerances differ in strength, and `tests/properties.rs` holds each to its claim:
13//!
14//! * **Translation is exact.** Shifting a print by any whole number of pixels does not move the
15//! score: stage 1 reads only `dx`/`dy`, and the one absolute-coordinate reader (the cluster
16//! centroid) enters the score only as a difference between two centroids of the same print.
17//! The centroid divides with truncation, so this holds while coordinate sums stay non-negative,
18//! which every real print satisfies.
19//! * **Rotation is a threshold.** Rotating a print runs its coordinates through trig and rounds
20//! them back to integers, changing the `(x, y)` sort order and so the rows stage 1 emits. A
21//! rotated impression does not reproduce the score; it keeps enough of it to out-score an
22//! unrelated print.
23//!
24//! ## Provenance
25//!
26//! BOZORTH3 is public-domain U.S. Government software (title 17 §105). This crate is a faithful
27//! port of stock upstream NBIS (see `docs/bozorth3-algorithm.md`), verified black-box against the
28//! stock C tool; score-exactness requires following its arithmetic closely, which public domain
29//! permits. It is not derived from libfprint's patched `nbis/` copy, whose changes carry LGPL
30//! terms. The crate carries `MIT OR Apache-2.0`. See `ARCHITECTURE.md` §Provenance & licensing.
31//!
32//! ## Types
33//!
34//! The crate takes its own [`Minutia`] (`{ x, y, theta }`) — the `xyt` triple is an
35//! interoperability fact, so the matcher stays a self-contained arithmetic kernel with no
36//! dependency on the domain model. A consumer (e.g. `fprint-backend-native`) converts its
37//! `fprint_core::Minutia` at the boundary — one `map` into [`Minutia`]:
38//!
39//! ```
40//! use fprint_bozorth3::{match_score, Minutia, MIN_COMPUTABLE_BOZORTH_MINUTIAE};
41//!
42//! // Your type, whatever it is.
43//! struct MyMinutia { col: i32, row: i32, angle_deg: i32 }
44//!
45//! fn to_bozorth(mine: &[MyMinutia]) -> Vec<Minutia> {
46//! mine.iter()
47//! .map(|m| Minutia { x: m.col, y: m.row, theta: m.angle_deg })
48//! .collect()
49//! }
50//!
51//! let mine: Vec<MyMinutia> = (0..12)
52//! .map(|i| MyMinutia { col: 20 + i * 9, row: 30 + (i * 17) % 40, angle_deg: (i * 30) % 360 })
53//! .collect();
54//! let print = to_bozorth(&mine);
55//!
56//! // Check the count before reading the score: under the minimum, 0 means "cannot tell".
57//! assert!(print.len() >= MIN_COMPUTABLE_BOZORTH_MINUTIAE);
58//! assert!(match_score(&print, &print) > 0);
59//! ```
60
61#![forbid(unsafe_code)]
62#![deny(missing_docs)]
63
64mod cluster;
65mod consts;
66mod inter;
67mod intra;
68mod xyt;
69
70pub use consts::{DEFAULT_BOZORTH_MINUTIAE, MAX_BOZORTH_MINUTIAE, MIN_COMPUTABLE_BOZORTH_MINUTIAE};
71
72/// One detected minutia: pixel position and ridge direction.
73///
74/// Matches the shape of `fprint_core::Minutia` (the consumer converts).
75#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
76pub struct Minutia {
77 /// Column, in pixels, increasing right.
78 pub x: i32,
79 /// Row, in pixels, increasing down.
80 pub y: i32,
81 /// Ridge orientation in integer **degrees**, canonically `0..=359`.
82 ///
83 /// Normalization is the reference's *single conditional subtract* (`t > 180 ? t - 360 : t`),
84 /// not a modulo, so canonical input lands in `(-180, 180]` — the representation stage 1
85 /// expects. Only canonical input is normalized: `720` becomes `360` and `-270` stays `-270`,
86 /// both outside that range.
87 ///
88 /// Give canonical input. A full turn is not the identity: `theta` and `theta - 360` are one
89 /// direction but two different scores. A `theta` far outside the canonical range still scores
90 /// (the relative-angle square is computed in i64), but the single conditional subtract leaves
91 /// it unfolded, so it is a different input, not the same angle. Non-canonical input is the
92 /// reference's arithmetic reproduced, not an error.
93 pub theta: i32,
94}
95
96impl Minutia {
97 /// Construct a minutia from the `xyt` triple. The value is stored as given — see the `theta`
98 /// field for what "canonical" means and why this reader does not normalize.
99 #[must_use]
100 pub const fn from_xyt(x: i32, y: i32, theta: i32) -> Self {
101 Self { x, y, theta }
102 }
103
104 /// The `(x, y, theta)` triple, for moving a minutia between kernels that name the same fact.
105 #[must_use]
106 pub const fn as_xyt(&self) -> (i32, i32, i32) {
107 (self.x, self.y, self.theta)
108 }
109}
110
111impl From<(i32, i32, i32)> for Minutia {
112 fn from((x, y, theta): (i32, i32, i32)) -> Self {
113 Self { x, y, theta }
114 }
115}
116
117/// The BOZORTH3 match score between a `probe` and a `gallery` minutia set.
118///
119/// Runs the full stock pipeline: build each print's intra-comparison Web (capped at
120/// [`DEFAULT_BOZORTH_MINUTIAE`] minutiae, pruned by edge length), form the inter-print compatibility
121/// list, then cluster it. Returns `0` when either print has fewer than
122/// [`MIN_COMPUTABLE_BOZORTH_MINUTIAE`] minutiae, and `4000` (`QQ_OVERFLOW_SCORE`) if the internal
123/// work queue overflows on a pathological input. The caller decides a match/non-match threshold.
124///
125/// The score is asymmetric by construction — stage 2's loop bounds are — so `match_score(a, b)` and
126/// `match_score(b, a)` need not agree. Pick an order and keep it.
127///
128/// # Panics
129///
130/// It does not panic on any input. The two squarings that carry unbounded deltas — the squared
131/// distance in stage 1 and the squared relative angle in stage 2 — are computed in i64, so an
132/// extreme coordinate span (two minutiae more than **46340 pixels** apart on an axis) or an
133/// unfolded `theta` (beyond about **±46340**, see [`Minutia::theta`]) yields a well-defined score
134/// instead of an `i32` overflow. Valid-reader inputs stay well inside that range and score exactly
135/// as the reference does; the widening changes nothing there. Totality on these extremes is
136/// recorded in `tests/totality.rs`.
137///
138/// ```
139/// use fprint_bozorth3::{match_score, Minutia};
140///
141/// let probe: Vec<Minutia> = (0..12)
142/// .map(|i| Minutia { x: 20 + i * 9, y: 30 + (i * 17) % 40, theta: (i * 30) % 360 })
143/// .collect();
144/// let gallery: Vec<Minutia> = probe
145/// .iter()
146/// .map(|m| Minutia { x: m.x + 2, y: m.y + 2, theta: m.theta })
147/// .collect();
148///
149/// assert!(match_score(&probe, &gallery) > 0);
150/// ```
151#[must_use]
152pub fn match_score(probe: &[Minutia], gallery: &[Minutia]) -> u32 {
153 let p = xyt::prepare(probe, DEFAULT_BOZORTH_MINUTIAE);
154 let g = xyt::prepare(gallery, DEFAULT_BOZORTH_MINUTIAE);
155 if p.nrows < MIN_COMPUTABLE_BOZORTH_MINUTIAE || g.nrows < MIN_COMPUTABLE_BOZORTH_MINUTIAE {
156 return 0;
157 }
158
159 let p_comp = intra::comp(&p);
160 let g_comp = intra::comp(&g);
161 let p_len = intra::prune_len(&p_comp);
162 let g_len = intra::prune_len(&g_comp);
163
164 let colp = inter::bz_match(&p_comp[..p_len], &g_comp[..g_len]);
165 let score = cluster::match_score(&colp, &p, &g);
166 score.max(0) as u32
167}
168
169/// Diagnostic: the pipeline sizes `(probe_web_len, gallery_web_len, num_compat_edges)` for a pair —
170/// stages 1 and 2, which `tests/golden.rs` checks against the stock C triple to localize any
171/// divergence to a stage.
172///
173/// Behind the `unstable-diagnostics` feature and `#[doc(hidden)]`: not part of the stable API, and
174/// `match_score` needs none of it. Mirrors the reference's `bozorth_probe_init` /
175/// `bozorth_gallery_init` / `bz_match`, none of which consults [`MIN_COMPUTABLE_BOZORTH_MINUTIAE`] —
176/// that guard is a *scoring* decision and lives in [`match_score`]; these sizes are facts about the
177/// tables.
178#[cfg(feature = "unstable-diagnostics")]
179#[doc(hidden)]
180#[must_use]
181pub fn debug_pipeline(probe: &[Minutia], gallery: &[Minutia]) -> (usize, usize, usize) {
182 let p = xyt::prepare(probe, DEFAULT_BOZORTH_MINUTIAE);
183 let g = xyt::prepare(gallery, DEFAULT_BOZORTH_MINUTIAE);
184 let p_comp = intra::comp(&p);
185 let g_comp = intra::comp(&g);
186 let p_len = intra::prune_len(&p_comp);
187 let g_len = intra::prune_len(&g_comp);
188 let colp = inter::bz_match(&p_comp[..p_len], &g_comp[..g_len]);
189 (p_len, g_len, colp.len())
190}