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}