Skip to main content

fprint_mindtct/
block.rs

1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! Image block partitioning and the block-level low-contrast test.
6//!
7//! Faithful port of the two block-geometry routines in stock NBIS `mindtct/src/lib/mindtct/block.c`:
8//!
9//! * [`block_offsets`] — carve the (unpadded) image into an `mw × mh` grid of `blocksize`-square
10//!   blocks and return, for each block, the pixel offset of its top-left corner **in the padded
11//!   image**. When a dimension is not an even multiple of `blocksize`, the last column/row of blocks
12//!   is pulled flush against the far edge and thus *overlaps* its neighbor (the stock "leftover"
13//!   strategy) — never a partial block.
14//! * [`low_contrast_block`] — build a 64-bin (6-bit) intensity histogram over one block and flag it
15//!   low-contrast when the 10th/90th percentile spread is below `min_contrast_delta`.
16//!
17//! The percentile threshold is computed with the port's bit-exact numeric primitives
18//! ([`trunc_dbl_precision`] then [`sround`]) so the rounding matches stock to the bit. The remaining
19//! `block.c` routines (`find_valid_block`, `set_margin_blocks`) belong to the map stage and live in
20//! `maps`. See `docs/mindtct-algorithm.md`.
21
22use crate::consts::TRUNC_SCALE;
23use crate::num::{sround, trunc_dbl_precision};
24use crate::params::LfsParms;
25
26/// `IMG_6BIT_PIX_LIMIT` — pixel-value limit of a 6-bit image (`lfs.h`), i.e. the number of histogram
27/// bins in [`low_contrast_block`]. Defined locally because `consts` does not export it.
28const IMG_6BIT_PIX_LIMIT: usize = 64;
29
30/// The result of [`block_offsets`]: the per-block origin offsets plus the block-grid dimensions.
31///
32/// Mirrors the stock C out-parameters `optr` / `ow` / `oh`. `offsets` is `map_w * map_h` long in
33/// row-major block order (all of row 0 left→right, then row 1, …); each entry is a pixel offset into
34/// the **padded** image to that block's top-left corner.
35#[derive(Clone, Debug, PartialEq, Eq)]
36pub(crate) struct BlockOffsets {
37    /// Pixel offsets (into the padded image) of each block's top-left corner, row-major.
38    pub offsets: Vec<i32>,
39    /// Number of block columns, `mw = ceil(iw / blocksize)` (stock `ow` / `bw`).
40    pub map_w: i32,
41    /// Number of block rows, `mh = ceil(ih / blocksize)` (stock `oh` / `bh`).
42    pub map_h: i32,
43}
44
45/// Divide an image into `mw × mh` equally sized blocks, returning the padded-image offset of each
46/// block's origin — the stock `block_offsets` (`block.c` L102).
47///
48/// For images whose dimensions are even multiples of `blocksize`, blocks are non-overlapping and
49/// immediately adjacent. Otherwise the last column and/or last row of blocks is placed flush against
50/// the far edge of the unpadded image and comes *inward* `blocksize` pixels, overlapping its
51/// neighbor — so processing arbitrary sizes never produces a partial block. Offsets account for the
52/// surrounding `pad` pixels: the grid begins `pad` rows down and `pad` columns in.
53///
54/// `mw = ceil(iw / blocksize)` and `mh = ceil(ih / blocksize)`, taken as a floating-point division
55/// then ceiling exactly as stock (`(int)ceil(iw/(double)blocksize)`).
56///
57/// # Errors
58///
59/// Returns `Err(-80)` when the unpadded image is smaller than a single block in either dimension
60/// (`iw < blocksize || ih < blocksize`), mirroring the stock C error code. (The stock `-81` malloc
61/// failure has no analogue here.)
62pub(crate) fn block_offsets(
63    iw: i32,
64    ih: i32,
65    pad: i32,
66    blocksize: i32,
67) -> Result<BlockOffsets, i32> {
68    // Test if unpadded image is smaller than a single block.
69    if iw < blocksize || ih < blocksize {
70        return Err(-80);
71    }
72
73    // Padded width of image (padded height is unused by this routine, as in stock).
74    let pad2 = pad << 1;
75    let pw = iw + pad2;
76
77    // Number of columns/rows of blocks: ceiling to account for the right/bottom "leftovers".
78    let bw = (f64::from(iw) / f64::from(blocksize)).ceil() as i32;
79    let bh = (f64::from(ih) / f64::from(blocksize)).ceil() as i32;
80
81    // Total number of blocks (allocation hint only; `push` preserves the stock `bi++` order).
82    let bsize = (bw * bh) as usize;
83
84    // Index of the last column / last row.
85    let lastbw = bw - 1;
86    let lastbh = bh - 1;
87
88    let mut blkoffs: Vec<i32> = Vec::with_capacity(bsize);
89
90    // Offset from the top of the padded image to the start of the current row of unpadded blocks.
91    // Indented `pad` in from the left edge of the padded image.
92    let mut blkrow_start = (pad * pw) + pad;
93    // Number of pixels in a row of blocks in the padded image (row width X block height).
94    let blkrow_size = pw * blocksize;
95
96    // Foreach non-overlapping row of blocks in the image.
97    for _by in 0..lastbh {
98        let mut offset = blkrow_start;
99        // Foreach non-overlapping column of blocks in the image.
100        for _bx in 0..lastbw {
101            blkoffs.push(offset);
102            offset += blocksize;
103        }
104        // "Left-over" block in the last column: flush to the far right edge of the unpadded image,
105        // coming in BLOCKSIZE pixels.
106        blkoffs.push(blkrow_start + iw - blocksize);
107        // Bump to the beginning of the next row of blocks.
108        blkrow_start += blkrow_size;
109    }
110
111    // "Left-over" row of blocks at the bottom of the image: flush to the bottom edge of the unpadded
112    // image, coming up BLOCKSIZE pixels (still accounting for padding).
113    let blkrow_start = ((pad + ih - blocksize) * pw) + pad;
114    let mut offset = blkrow_start;
115    for _bx in 0..lastbw {
116        blkoffs.push(offset);
117        offset += blocksize;
118    }
119    // Last "left-over" block in the last row.
120    blkoffs.push(blkrow_start + iw - blocksize);
121
122    Ok(BlockOffsets {
123        offsets: blkoffs,
124        map_w: bw,
125        map_h: bh,
126    })
127}
128
129/// Analyze one image block's pixel intensities and report whether it has too *little* contrast for
130/// further processing — the stock `low_contrast_block` (`block.c` L224).
131///
132/// Builds a 64-bin histogram over the `blocksize × blocksize` block anchored at `blkoffset` in the
133/// padded image `pdata` (row stride `pw`), then derives the `percentile_min_max`-th percentile
134/// minimum and maximum intensities (`prctmin` / `prctmax`). The block is **low contrast**
135/// (`Ok(true)`) when `prctmax - prctmin < min_contrast_delta`, else high contrast (`Ok(false)`).
136///
137/// The percentile rank is `sround(trunc_dbl_precision((pct/100) * (numpix - 1), TRUNC_SCALE))`,
138/// reproducing stock's exact quantize-then-round so the min/max cutoffs land on the same bins.
139///
140/// `_ph` (padded height) is part of the stock signature but unused by the routine. `pdata` must hold
141/// 6-bit values (`0..IMG_6BIT_PIX_LIMIT`); an out-of-range pixel would index past the histogram — the
142/// same 6-bit-image precondition the stock C assumes.
143///
144/// # Errors
145///
146/// Returns `Err(-510)` / `Err(-511)` if the min / max percentile pixel is not found — only reachable
147/// for an empty block (`blocksize <= 0`), matching the stock C error codes.
148pub(crate) fn low_contrast_block(
149    blkoffset: i32,
150    blocksize: i32,
151    pdata: &[u8],
152    pw: i32,
153    _ph: i32,
154    lfsparms: &LfsParms,
155) -> Result<bool, i32> {
156    let numpix = blocksize * blocksize;
157    let mut pixtable = [0i32; IMG_6BIT_PIX_LIMIT];
158
159    // Percentile rank into the sorted intensities: quantize then round, bit-for-bit as stock.
160    let tdbl = (f64::from(lfsparms.percentile_min_max) / 100.0) * f64::from(numpix - 1);
161    let tdbl = trunc_dbl_precision(tdbl, TRUNC_SCALE);
162    let prctthresh = sround(tdbl);
163
164    // Accumulate the block's intensity histogram (row stride is the padded width `pw`).
165    let start = blkoffset as usize;
166    let stride = pw as usize;
167    for py in 0..blocksize {
168        let row = start + (py as usize) * stride;
169        for px in 0..blocksize {
170            let v = pdata[row + px as usize];
171            pixtable[usize::from(v)] += 1;
172        }
173    }
174
175    // Walk up from the darkest bin to the first bin whose cumulative count reaches the rank.
176    let mut prctmin = 0i32;
177    let mut pixsum = 0i32;
178    let mut found = false;
179    for (pi, &count) in pixtable.iter().enumerate() {
180        pixsum += count;
181        if pixsum >= prctthresh {
182            prctmin = pi as i32;
183            found = true;
184            break;
185        }
186    }
187    if !found {
188        return Err(-510);
189    }
190
191    // Walk down from the brightest bin to the first bin whose cumulative count reaches the rank.
192    let mut prctmax = 0i32;
193    let mut pixsum = 0i32;
194    let mut found = false;
195    for pi in (0..IMG_6BIT_PIX_LIMIT).rev() {
196        pixsum += pixtable[pi];
197        if pixsum >= prctthresh {
198            prctmax = pi as i32;
199            found = true;
200            break;
201        }
202    }
203    if !found {
204        return Err(-511);
205    }
206
207    let delta = prctmax - prctmin;
208
209    Ok(delta < lfsparms.min_contrast_delta)
210}
211
212#[cfg(test)]
213mod tests {
214    use super::*;
215    use crate::params::LFSPARMS_V2;
216
217    // ---- block_offsets ----------------------------------------------------------------------
218
219    /// Even multiple, no padding: 16x16 image, 8x8 blocks -> a clean 2x2 non-overlapping grid.
220    /// Offsets are `by * (pw * blocksize) + bx * blocksize` with `pw = iw = 16`.
221    #[test]
222    fn block_offsets_even_multiple_no_pad() {
223        let b = block_offsets(16, 16, 0, 8).unwrap();
224        assert_eq!(b.map_w, 2);
225        assert_eq!(b.map_h, 2);
226        // row 0: cols at 0, 8; row 1 starts at 8*16 = 128: 128, 136.
227        assert_eq!(b.offsets, vec![0, 8, 128, 136]);
228    }
229
230    /// Padding shifts every origin by `pad` rows and `pad` cols of the padded image
231    /// (`pw = iw + 2*pad = 32`), and the last row is measured up from the bottom edge.
232    #[test]
233    fn block_offsets_even_multiple_with_pad() {
234        let b = block_offsets(16, 16, 8, 8).unwrap();
235        assert_eq!((b.map_w, b.map_h), (2, 2));
236        // blkrow_start = pad*pw + pad = 8*32 + 8 = 264; last row = (8+16-8)*32 + 8 = 520.
237        assert_eq!(b.offsets, vec![264, 272, 520, 528]);
238    }
239
240    /// Fractional width forces the "leftover" overlap: iw=20 -> ceil(20/8)=3 columns, the last of
241    /// which starts at `iw - blocksize = 12`, overlapping the middle block (starts at 8).
242    #[test]
243    fn block_offsets_fractional_width_overlaps() {
244        let b = block_offsets(20, 8, 0, 8).unwrap();
245        assert_eq!((b.map_w, b.map_h), (3, 1));
246        // Single row (bh=1): non-overlapping cols 0, 8, then the flush-right leftover at 12.
247        assert_eq!(b.offsets, vec![0, 8, 12]);
248    }
249
250    /// Fractional in both dimensions: iw=20, ih=12 -> 3x2 grid. Verifies the last *row* is also
251    /// pulled flush to the bottom edge (`(ih - blocksize) * pw = 4 * 20 = 80`).
252    #[test]
253    fn block_offsets_fractional_both_dims() {
254        let b = block_offsets(20, 12, 0, 8).unwrap();
255        assert_eq!((b.map_w, b.map_h), (3, 2));
256        // row 0 at y=0: 0, 8, 12 ; last row flush at y=4 (offset 80): 80, 88, 92.
257        assert_eq!(b.offsets, vec![0, 8, 12, 80, 88, 92]);
258        assert_eq!(b.offsets.len(), (b.map_w * b.map_h) as usize);
259    }
260
261    /// Image smaller than one block in either dimension is the stock `-80` error.
262    #[test]
263    fn block_offsets_too_small_is_err() {
264        assert_eq!(block_offsets(4, 16, 0, 8), Err(-80));
265        assert_eq!(block_offsets(16, 4, 0, 8), Err(-80));
266    }
267
268    // ---- low_contrast_block -----------------------------------------------------------------
269
270    /// A flat block (every pixel the same value) has zero spread -> unambiguously low contrast.
271    #[test]
272    fn low_contrast_uniform_block_is_low() {
273        let data = vec![30u8; 64]; // 8x8, tightly packed (pw == blocksize).
274        assert_eq!(
275            low_contrast_block(0, 8, &data, 8, 8, &LFSPARMS_V2),
276            Ok(true)
277        );
278    }
279
280    /// Half dark (10) / half bright (60): percentile min lands on 10, max on 60, delta 50 >= 5.
281    #[test]
282    fn low_contrast_split_block_is_high() {
283        let mut data = vec![10u8; 64];
284        for v in data.iter_mut().take(64).skip(32) {
285            *v = 60;
286        }
287        assert_eq!(
288            low_contrast_block(0, 8, &data, 8, 8, &LFSPARMS_V2),
289            Ok(false)
290        );
291    }
292
293    /// Delta exactly equal to `min_contrast_delta` (5) is NOT low contrast: the test is strict `<`.
294    /// 32 px at 10 and 32 px at 15 -> prctmin=10, prctmax=15, delta=5.
295    #[test]
296    fn low_contrast_delta_equal_threshold_is_high() {
297        let mut data = vec![10u8; 64];
298        for v in data.iter_mut().take(64).skip(32) {
299            *v = 15;
300        }
301        assert_eq!(LFSPARMS_V2.min_contrast_delta, 5);
302        assert_eq!(
303            low_contrast_block(0, 8, &data, 8, 8, &LFSPARMS_V2),
304            Ok(false)
305        );
306    }
307
308    /// One below threshold (delta 4 < 5) tips to low contrast. 32 px at 10 and 32 px at 14.
309    #[test]
310    fn low_contrast_delta_below_threshold_is_low() {
311        let mut data = vec![10u8; 64];
312        for v in data.iter_mut().take(64).skip(32) {
313            *v = 14;
314        }
315        assert_eq!(
316            low_contrast_block(0, 8, &data, 8, 8, &LFSPARMS_V2),
317            Ok(true)
318        );
319    }
320
321    /// Row-stride correctness: a padded image (`pw = 12`) whose 8x8 block region is uniform (30) but
322    /// whose surrounding padding is high-contrast (63). Only the block's pixels must be counted, so
323    /// the verdict is low contrast — a wrong stride would fold in the bright padding and flip it.
324    #[test]
325    fn low_contrast_respects_padded_stride() {
326        let pw = 12i32;
327        let ph = 12i32;
328        let pad = 2i32;
329        let mut data = vec![63u8; (pw * ph) as usize];
330        // Fill the 8x8 block at (pad, pad) with a single uniform value.
331        for by in 0..8 {
332            let row = ((pad + by) * pw + pad) as usize;
333            for bx in 0..8 {
334                data[row + bx as usize] = 30;
335            }
336        }
337        let blkoffset = pad * pw + pad;
338        assert_eq!(
339            low_contrast_block(blkoffset, 8, &data, pw, ph, &LFSPARMS_V2),
340            Ok(true)
341        );
342    }
343
344    /// The percentile rank matches the stock quantize-then-round chain for the V2 8x8 block:
345    /// `sround(trunc_dbl_precision(0.10 * 63, 16384)) == 6`. A block with only 5 dark pixels (below
346    /// the rank of 6) must not let those pixels set `prctmin`.
347    #[test]
348    fn low_contrast_percentile_rank_ignores_sub_threshold_tail() {
349        // 5 px at value 0 (below the rank-6 cutoff), 59 px at value 40.
350        let mut data = vec![40u8; 64];
351        for v in data.iter_mut().take(5) {
352            *v = 0;
353        }
354        // prctmin: cumulative reaches 6 only at value 40 (5 zeros < 6). prctmax: 40. delta 0 -> low.
355        assert_eq!(
356            low_contrast_block(0, 8, &data, 8, 8, &LFSPARMS_V2),
357            Ok(true)
358        );
359    }
360}