Skip to main content

fprint_mindtct/
init.rs

1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! One-time lookup-table construction: `init_dir2rad` (direction→radians), `init_dftwaves` (DFT
6//! waveform tables), and `init_rotgrids` (rotated-grid pixel-offset tables) for the DFT and
7//! directional-binarization passes, plus `get_max_padding_V2` — the single border-pad width that
8//! covers every rotated grid so the input image is padded exactly once.
9//!
10//! Faithful port of stock NBIS `mindtct/src/lib/mindtct/init.c`. The bit-exactness contract here
11//! turns on **one deliberate asymmetry** (see `docs/mindtct-algorithm.md` §Bit-exactness):
12//!
13//! * `init_dir2rad` **quantizes** every `cos`/`sin` through
14//!   [`trunc_dbl_precision`](crate::num::trunc_dbl_precision) at `1/16384`, so the integer-direction
15//!   table is reproducible across architectures.
16//! * `init_dftwaves` stores the **raw, un-truncated** `f64::cos`/`f64::sin` — stock does *not*
17//!   quantize the DFT waveforms. This is the one place a `libm` difference can leak in, and it is
18//!   kept verbatim rather than "fixed".
19//!
20//! `init_rotgrids` precomputes, for each of `ndirs` rotations, a flat list of pixel offsets
21//! `ixt + iyt * pw` into the *padded* image, where `pw = iw + 2*pad` — so every offset is tied to
22//! the width the image will actually be padded to. Two conventions are supported: offsets relative
23//! to the grid's [`Center`](Relative2::Center) (directional binarization) or its
24//! [`Origin`](Relative2::Origin) (DFT windows).
25
26use crate::consts::TRUNC_SCALE;
27use crate::num::{sround, trunc_dbl_precision};
28
29/// Whether an [`init_rotgrids`] grid's rotated offsets are measured from the grid's geometric
30/// **center** or its **origin** (top-left) — the stock `RELATIVE2CENTER` (`0`) / `RELATIVE2ORIGIN`
31/// (`1`) flags, made an enum so the illegal-flag error path in the C (`-31`) cannot arise.
32///
33/// Directional binarization uses [`Center`](Self::Center) (grid centers sit on valid pixels); the
34/// DFT window analysis uses [`Origin`](Self::Origin) (window origins sit on valid pixels). The
35/// choice changes both the required padding and whether the grid center offset is folded back in.
36#[derive(Clone, Copy, PartialEq, Eq, Debug)]
37pub(crate) enum Relative2 {
38    /// `RELATIVE2CENTER`: offsets are relative to the grid center `((w-1)/2, (h-1)/2)`.
39    Center,
40    /// `RELATIVE2ORIGIN`: offsets are relative to the grid origin (top-left), so the center is
41    /// added back into each offset.
42    Origin,
43}
44
45/// Lookup table converting an integer IMAP direction to its angle's `cos`/`sin` — the stock
46/// `DIR2RAD`.
47///
48/// `cos[i]` and `sin[i]` hold the (quantized) cosine and sine of `theta = i * 2*PI/ndirs`, the angle
49/// of direction `i` around a semicircle. Both vectors are `ndirs` long.
50#[derive(Clone, Debug)]
51pub(crate) struct Dir2Rad {
52    /// Number of integer directions across the semicircle.
53    pub(crate) ndirs: i32,
54    /// Quantized cosine per direction.
55    pub(crate) cos: Vec<f64>,
56    /// Quantized sine per direction.
57    pub(crate) sin: Vec<f64>,
58}
59
60/// A single DFT waveform — matched `cos`/`sin` sample vectors for one frequency (the stock
61/// `DFTWAVE`). Each vector is `blocksize` long.
62#[derive(Clone, Debug)]
63pub(crate) struct DftWave {
64    /// Cosine samples (raw, un-truncated `f64`).
65    pub(crate) cos: Vec<f64>,
66    /// Sine samples (raw, un-truncated `f64`).
67    pub(crate) sin: Vec<f64>,
68}
69
70/// The full set of DFT waveforms applied to each block window (the stock `DFTWAVES`).
71#[derive(Clone, Debug)]
72pub(crate) struct DftWaves {
73    /// Number of waveforms.
74    pub(crate) nwaves: i32,
75    /// Sample length of every waveform (all identical; equals `blocksize`).
76    pub(crate) wavelen: i32,
77    /// One [`DftWave`] per frequency coefficient.
78    pub(crate) waves: Vec<DftWave>,
79}
80
81/// Precomputed rotated-grid pixel offsets for `ngrids` orientations (the stock `ROTGRIDS`).
82///
83/// `grids[dir]` is a `grid_w * grid_h` flat list (row-major over the *unrotated* grid) of signed
84/// offsets `ixt + iyt * pw` into the padded image, where `pw = iw + 2*pad`. Adding a grid's offset
85/// to a base pixel index lands on the correspondingly rotated pixel.
86#[derive(Clone, Debug)]
87pub(crate) struct RotGrids {
88    /// Border padding (in pixels) these offsets assume on every side of the image.
89    pub(crate) pad: i32,
90    /// Whether offsets are relative to the grid center or origin.
91    // `dead_code` (not `expect`): these fields are written in every build but read only by the tests,
92    // so the lint fires in the plain lib build and not in the `--test` build — `expect` would be
93    // unfulfilled in the latter. `relative2`/`start_angle` mirror the stock `ROTGRIDS` layout but are
94    // consumed only while *building* the grids (`init_rotgrids`); the offsets carry all the port needs
95    // afterward, so nothing reads them back at runtime. Transcribed for fidelity and pinned by tests.
96    #[allow(dead_code)]
97    pub(crate) relative2: Relative2,
98    /// Angle (radians) of the first grid (direction `0`).
99    #[allow(dead_code)]
100    pub(crate) start_angle: f64,
101    /// Number of rotated grids (`= ndirs`).
102    pub(crate) ngrids: i32,
103    /// Grid width in pixels.
104    pub(crate) grid_w: i32,
105    /// Grid height in pixels.
106    pub(crate) grid_h: i32,
107    /// Per-direction flat offset lists.
108    pub(crate) grids: Vec<Vec<i32>>,
109}
110
111/// `init_dir2rad` — build the direction→radians `cos`/`sin` table.
112///
113/// Stock `init_dir2rad` (init.c L86). `pi_factor = 2*PI/ndirs` sets the period to `ndirs` units;
114/// for each direction `i`, `theta = i * pi_factor` and the cosine/sine are **quantized** to
115/// `1/16384` via [`trunc_dbl_precision`] so the table is identical on every architecture.
116pub(crate) fn init_dir2rad(ndirs: i32) -> Dir2Rad {
117    // pi_factor sets the period of the trig functions to ndirs units in x.
118    let pi_factor = 2.0 * std::f64::consts::PI / f64::from(ndirs);
119
120    let mut cos = Vec::with_capacity(ndirs.max(0) as usize);
121    let mut sin = Vec::with_capacity(ndirs.max(0) as usize);
122    for i in 0..ndirs {
123        let theta = f64::from(i) * pi_factor;
124        // Truncate precision so answers are consistent across architectures.
125        cos.push(trunc_dbl_precision(theta.cos(), TRUNC_SCALE));
126        sin.push(trunc_dbl_precision(theta.sin(), TRUNC_SCALE));
127    }
128
129    Dir2Rad { ndirs, cos, sin }
130}
131
132/// `init_dftwaves` — build the set of DFT waveforms for block analysis.
133///
134/// Stock `init_dftwaves` (init.c L160). `pi_factor = 2*PI/blocksize`; each waveform `i` has
135/// `freq = pi_factor * dft_coefs[i]` and samples `cos(freq*j)` / `sin(freq*j)` for `j` in
136/// `0..blocksize`. **Unlike [`init_dir2rad`], these samples are stored raw — not quantized** —
137/// exactly as stock does; this is the one deliberate `libm`-sensitive spot in the port.
138pub(crate) fn init_dftwaves(dft_coefs: &[f64], nwaves: i32, blocksize: i32) -> DftWaves {
139    // pi_factor sets the period of the trig functions to blocksize units in x.
140    let pi_factor = 2.0 * std::f64::consts::PI / f64::from(blocksize);
141
142    let mut waves = Vec::with_capacity(nwaves.max(0) as usize);
143    for i in 0..nwaves {
144        // Compute actual frequency for this coefficient.
145        let freq = pi_factor * dft_coefs[i as usize];
146        let mut cos = Vec::with_capacity(blocksize.max(0) as usize);
147        let mut sin = Vec::with_capacity(blocksize.max(0) as usize);
148        for j in 0..blocksize {
149            let x = freq * f64::from(j);
150            // Store cos and sin components of sample point (NO truncation — stock keeps these raw).
151            cos.push(x.cos());
152            sin.push(x.sin());
153        }
154        waves.push(DftWave { cos, sin });
155    }
156
157    DftWaves {
158        nwaves,
159        wavelen: blocksize,
160        waves,
161    }
162}
163
164/// `get_max_padding_V2` — the single border pad covering every rotated grid used by `_V2`.
165///
166/// Stock `get_max_padding_V2` (init.c L364). Takes the larger of two paddings so the image is padded
167/// only once:
168///
169/// * **DFT windows** (`RELATIVE2ORIGIN`): rotational pad `round((diag - windowsize)/2)` over the
170///   window's diagonal, **plus** `map_windowoffset` (the window overhangs the block by that much).
171/// * **Directional-binarization grids** (`RELATIVE2CENTER`): `round((diag - 1)/2)` over the grid's
172///   diagonal.
173///
174/// Each `pad` is quantized to `1/16384` before [`sround`] to stay architecture-stable. For the
175/// shipping `_V2` geometry (`windowsize 24`, `offset 8`, dirbin grid `7x9`) this returns `13`.
176#[expect(non_snake_case)]
177pub(crate) fn get_max_padding_V2(
178    map_windowsize: i32,
179    map_windowoffset: i32,
180    dirbin_grid_w: i32,
181    dirbin_grid_h: i32,
182) -> i32 {
183    // 1. Pad for rotated windows used in DFT analyses (offsets RELATIVE2ORIGIN).
184    let diag = (2.0 * f64::from(map_windowsize) * f64::from(map_windowsize)).sqrt();
185    let pad = (diag - f64::from(map_windowsize)) / 2.0;
186    let pad = trunc_dbl_precision(pad, TRUNC_SCALE);
187    // Must add the window offset to the rotational padding.
188    let dft_pad = sround(pad) + map_windowoffset;
189
190    // 2. Pad for rotated blocks used in directional binarization (offsets RELATIVE2CENTER).
191    let diag = f64::from(dirbin_grid_w * dirbin_grid_w + dirbin_grid_h * dirbin_grid_h).sqrt();
192    let pad = (diag - 1.0) / 2.0;
193    let pad = trunc_dbl_precision(pad, TRUNC_SCALE);
194    let dirbin_pad = sround(pad);
195
196    dft_pad.max(dirbin_pad)
197}
198
199/// `init_rotgrids` — precompute rotated pixel offsets for `ndirs` grid orientations.
200///
201/// Stock `init_rotgrids` (init.c L471). Rotates a `grid_w x grid_h` grid about its center for each
202/// of `ndirs` directions starting at `start_dir_angle` and stepping `PI/ndirs`, and stores, per
203/// pixel, the signed offset `ixt + iyt * pw` into the padded image (`pw = iw + 2*pad`).
204///
205/// The grid's own required padding is `round((diag - 1)/2)` for [`Relative2::Center`] or
206/// `round((diag - min(w,h))/2)` for [`Relative2::Origin`] (`diag` = grid diagonal), quantized to
207/// `1/16384`. `ipad` selects the padding actually used: [`None`] (stock `UNDEFINED`) adopts the
208/// grid's own pad; `Some(p)` uses `p` (which callers size via [`get_max_padding_V2`] so a single
209/// padded image serves every grid — it must be at least the grid's own pad).
210///
211/// The rotation transform of pixel `P=(ix,iy)` about center `C=(cx,cy)` is
212/// `Rx = cx + (ix-cx)cos - (iy-cy)sin`, `Ry = cy + (ix-cx)sin + (iy-cy)cos`; for
213/// [`Relative2::Center`] the leading `cx`/`cy` are dropped (offsets stay center-relative). Each
214/// `fx`/`fy` is quantized then [`sround`]ed, verbatim with stock.
215///
216/// (Stock's `ih` image-height parameter is intentionally omitted: `init_rotgrids` never reads it —
217/// only `iw` feeds the padded width `pw`.)
218pub(crate) fn init_rotgrids(
219    iw: i32,
220    ipad: Option<i32>,
221    start_dir_angle: f64,
222    ndirs: i32,
223    grid_w: i32,
224    grid_h: i32,
225    relative2: Relative2,
226) -> RotGrids {
227    // Compute the grid's own required pad from its diagonal.
228    let diag = f64::from(grid_w * grid_w + grid_h * grid_h).sqrt();
229    let grid_pad = match relative2 {
230        Relative2::Center => {
231            // Grid centers reside in valid memory.
232            let pad = (diag - 1.0) / 2.0;
233            sround(trunc_dbl_precision(pad, TRUNC_SCALE))
234        }
235        Relative2::Origin => {
236            // Grid origins reside in valid memory; pad off the smallest dimension.
237            let min_dim = grid_w.min(grid_h);
238            let pad = (diag - f64::from(min_dim)) / 2.0;
239            sround(trunc_dbl_precision(pad, TRUNC_SCALE))
240        }
241    };
242
243    // UNDEFINED -> use the grid's own pad; otherwise use the caller's pad (must be large enough).
244    let pad = match ipad {
245        None => grid_pad,
246        Some(p) => {
247            debug_assert!(
248                p >= grid_pad,
249                "init_rotgrids: pad {p} too small for grid (needs >= {grid_pad})"
250            );
251            p
252        }
253    };
254
255    // Width of the "padded" image — the multiplier on every offset's y-component.
256    let pw = iw + (pad << 1);
257
258    // Center coord of grid (0-oriented).
259    let cx = f64::from(grid_w - 1) / 2.0;
260    let cy = f64::from(grid_h - 1) / 2.0;
261
262    // pi_offset is the radian offset at which angles begin; pi_incr steps a semicircle over ndirs.
263    let pi_offset = start_dir_angle;
264    let pi_incr = std::f64::consts::PI / f64::from(ndirs);
265
266    let mut grids = Vec::with_capacity(ndirs.max(0) as usize);
267    for dir in 0..ndirs {
268        let theta = pi_offset + f64::from(dir) * pi_incr;
269        let cs = theta.cos();
270        let sn = theta.sin();
271
272        let mut grid = Vec::with_capacity((grid_w * grid_h).max(0) as usize);
273        for iy in 0..grid_h {
274            // Rotation factors dependent on iy.
275            let mut fxm = -((f64::from(iy) - cy) * sn);
276            let mut fym = (f64::from(iy) - cy) * cs;
277            // For origin-relative offsets, fold the center back in.
278            if relative2 == Relative2::Origin {
279                fxm += cx;
280                fym += cy;
281            }
282
283            for ix in 0..grid_w {
284                // Combine the ix-dependent factors with the iy-dependent ones.
285                let fx = fxm + ((f64::from(ix) - cx) * cs);
286                let fy = fym + ((f64::from(ix) - cx) * sn);
287                // Truncate precision so answers are consistent across architectures.
288                let fx = trunc_dbl_precision(fx, TRUNC_SCALE);
289                let fy = trunc_dbl_precision(fy, TRUNC_SCALE);
290                let ixt = sround(fx);
291                let iyt = sround(fy);
292                // Multiply the y-component of the offset by the padded image width.
293                grid.push(ixt + iyt * pw);
294            }
295        }
296        grids.push(grid);
297    }
298
299    RotGrids {
300        pad,
301        relative2,
302        start_angle: start_dir_angle,
303        ngrids: ndirs,
304        grid_w,
305        grid_h,
306        grids,
307    }
308}
309
310#[cfg(test)]
311mod tests {
312    use super::*;
313    use crate::consts::{
314        DFT_COEFS, MAP_WINDOWOFFSET_V2, MAP_WINDOWSIZE_V2, NUM_DFT_WAVES, NUM_DIRECTIONS,
315    };
316
317    // --- init_dir2rad: quantized cos/sin ------------------------------------------------------
318    #[test]
319    fn dir2rad_matches_stock_known_values() {
320        let t = init_dir2rad(NUM_DIRECTIONS);
321        assert_eq!(t.ndirs, 16);
322        assert_eq!(t.cos.len(), 16);
323        assert_eq!(t.sin.len(), 16);
324
325        // theta(0) = 0: cos 1, sin 0.
326        assert_eq!(t.cos[0], 1.0);
327        assert_eq!(t.sin[0], 0.0);
328        // theta(4) = PI/2: cos ~6.1e-17 QUANTIZES to exactly 0.0; sin exactly 1.0.
329        // This exact 0.0 is the signature of dir2rad's truncation (contrast dftwaves below).
330        assert_eq!(t.cos[4], 0.0);
331        assert_eq!(t.sin[4], 1.0);
332        // theta(8) = PI: cos -1, sin 0.
333        assert_eq!(t.cos[8], -1.0);
334        assert_eq!(t.sin[8], 0.0);
335
336        // Every entry is an exact multiple of 1/16384.
337        for &c in t.cos.iter().chain(t.sin.iter()) {
338            assert_eq!((c * 16384.0).round(), c * 16384.0);
339        }
340    }
341
342    // --- init_dftwaves: RAW (un-truncated) cos/sin --------------------------------------------
343    #[test]
344    fn dftwaves_are_raw_untruncated() {
345        let w = init_dftwaves(&DFT_COEFS, NUM_DFT_WAVES, MAP_WINDOWSIZE_V2);
346        assert_eq!(w.nwaves, 4);
347        assert_eq!(w.wavelen, 24);
348        assert_eq!(w.waves.len(), 4);
349        for wave in &w.waves {
350            assert_eq!(wave.cos.len(), 24);
351            assert_eq!(wave.sin.len(), 24);
352        }
353
354        // Wave 0, sample 0: cos 1, sin 0.
355        assert_eq!(w.waves[0].cos[0], 1.0);
356        assert_eq!(w.waves[0].sin[0], 0.0);
357
358        // Wave 0, sample 6: x = (2PI/24)*6 = PI/2. Stock does NOT quantize, so cos is the raw
359        // ~6.123233995736766e-17 (NOT the 0.0 that dir2rad would produce) and sin is 1.0.
360        let c = w.waves[0].cos[6];
361        assert!(c != 0.0, "dftwaves must keep the raw non-zero cos, got {c}");
362        assert!(c.abs() < 1e-15);
363        assert!((w.waves[0].sin[6] - 1.0).abs() < 1e-15);
364    }
365
366    // --- get_max_padding_V2 -------------------------------------------------------------------
367    #[test]
368    fn max_padding_v2_shipping_geometry_is_13() {
369        // DFT window pad = round((sqrt(1152)-24)/2)+8 = 5+8 = 13; dirbin = round((sqrt(130)-1)/2) = 5.
370        assert_eq!(get_max_padding_V2(24, 8, 7, 9), 13);
371        // Same via the named constants.
372        assert_eq!(
373            get_max_padding_V2(MAP_WINDOWSIZE_V2, MAP_WINDOWOFFSET_V2, 7, 9),
374            13
375        );
376    }
377
378    // --- init_rotgrids: pad derivation --------------------------------------------------------
379    #[test]
380    fn rotgrids_pad_derivation() {
381        // RELATIVE2ORIGIN, 24x24 window: pad = round((sqrt(1152)-24)/2) = 5.
382        let g = init_rotgrids(100, None, 0.0, 4, 24, 24, Relative2::Origin);
383        assert_eq!(g.pad, 5);
384
385        // RELATIVE2CENTER, 3x3 grid: pad = round((sqrt(18)-1)/2) = 2.
386        let g = init_rotgrids(10, None, 0.0, 4, 3, 3, Relative2::Center);
387        assert_eq!(g.pad, 2);
388    }
389
390    // --- init_rotgrids: exact offsets at theta = 0 (center-relative) --------------------------
391    #[test]
392    fn rotgrids_center_offsets_at_zero_angle() {
393        // start_angle 0, dir 0 -> theta 0 -> cos 1, sin 0. Center of a 3x3 grid is (1,1).
394        // fx = ix-1, fy = iy-1, so offset = (ix-1) + (iy-1)*pw.
395        let iw = 10;
396        let g = init_rotgrids(iw, None, 0.0, 4, 3, 3, Relative2::Center);
397        // pad = 2 -> pw = 10 + 4 = 14.
398        let pw = iw + 2 * g.pad;
399        assert_eq!(pw, 14);
400
401        let grid0 = &g.grids[0];
402        assert_eq!(grid0.len(), 9);
403        // Row-major over (iy, ix): expected (ix-1) + (iy-1)*pw.
404        let expected: Vec<i32> = (0..3)
405            .flat_map(|iy| (0..3).map(move |ix| (ix - 1) + (iy - 1) * pw))
406            .collect();
407        assert_eq!(grid0, &expected);
408        // Spot points: top-left = -1-pw, center = 0, bottom-right = 1+pw.
409        assert_eq!(grid0[0], -1 - pw);
410        assert_eq!(grid0[4], 0);
411        assert_eq!(grid0[8], 1 + pw);
412    }
413
414    // --- init_rotgrids: offsets track the padded width via the caller's pad --------------------
415    #[test]
416    fn rotgrids_offsets_use_caller_pad_width() {
417        // A larger caller-supplied pad widens pw, which scales every y-component of the offsets.
418        let iw = 20;
419        let big_pad = 9; // >= grid's own pad (2 for a 3x3 center grid)
420        let g = init_rotgrids(iw, Some(big_pad), 0.0, 4, 3, 3, Relative2::Center);
421        assert_eq!(g.pad, big_pad);
422        let pw = iw + 2 * big_pad; // 38
423                                   // Bottom-centre pixel (ix=1, iy=2) at theta 0 -> offset (0) + (1)*pw = pw.
424                                   // Index in row-major 3x3 is iy*3 + ix = 2*3 + 1 = 7.
425        assert_eq!(g.grids[0][7], pw);
426    }
427
428    // --- init_rotgrids: structural attributes -------------------------------------------------
429    #[test]
430    fn rotgrids_attributes() {
431        let g = init_rotgrids(64, None, START_ANGLE, 16, 24, 24, Relative2::Origin);
432        assert_eq!(g.ngrids, 16);
433        assert_eq!(g.grid_w, 24);
434        assert_eq!(g.grid_h, 24);
435        assert_eq!(g.relative2, Relative2::Origin);
436        assert_eq!(g.start_angle, START_ANGLE);
437        assert_eq!(g.grids.len(), 16);
438        for grid in &g.grids {
439            assert_eq!(grid.len(), 24 * 24);
440        }
441    }
442
443    const START_ANGLE: f64 = std::f64::consts::PI / 2.0;
444}