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}