Skip to main content

openreadout_core/
region.rs

1//! Region reads and resolution levels.
2//!
3//! A [`Region`] is a rectangle of one plane in the pixel coordinates of one resolution level
4//! (level 0 = full resolution). [`crate::Dataset::read_region`] decodes only that rectangle:
5//! readers whose pixels are stored in tiles, subblocks or chunks (CZI, tiled TIFF and
6//! whole-slide TIFF flavours, VSI/ETS, Imaris, OME-Zarr) touch only the tiles the region
7//! overlaps, so a 512 × 512 window of a 40 GB slide costs a few tiles and a few megabytes.
8//! Every other reader gets the default: read the whole plane at that level, then crop.
9//!
10//! [`ResolutionLevel`] is the geometry of one level (`info` → `images[].resolution_levels`):
11//! its size, its downsampling factor relative to level 0 and the natural tile a region read
12//! should align to. [`TileCache`] is a small byte-bounded cache of decoded tiles readers use
13//! so that neighbouring region reads (dask chunks, export blocks) do not decode a tile twice.
14
15// x, y, w, h are the natural names of a rectangle.
16#![allow(clippy::many_single_char_names)]
17
18use std::collections::HashMap;
19use std::hash::Hash;
20use std::sync::Arc;
21
22use schemars::JsonSchema;
23use serde::{Deserialize, Serialize};
24
25use crate::error::{Error, Result};
26use crate::model::ImageInfo;
27use crate::pixel::{Plane, plane_bytes_checked};
28
29/// A rectangle of a plane, in the pixel coordinates of the resolution level it is read at.
30#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default, Serialize, Deserialize, JsonSchema)]
31pub struct Region {
32    /// Left edge (column of the first pixel).
33    pub x: u32,
34    /// Top edge (row of the first pixel).
35    pub y: u32,
36    /// Width in pixels (at least 1).
37    pub width: u32,
38    /// Height in pixels (at least 1).
39    pub height: u32,
40}
41
42impl Region {
43    /// A `width` × `height` rectangle whose top-left pixel is `(x, y)`.
44    pub fn new(x: u32, y: u32, width: u32, height: u32) -> Self {
45        Region {
46            x,
47            y,
48            width,
49            height,
50        }
51    }
52
53    /// The whole of a `width` × `height` plane.
54    pub fn full(width: u32, height: u32) -> Self {
55        Region::new(0, 0, width, height)
56    }
57
58    /// Parse `X,Y,W,H` (the CLI's `--region`), all non-negative integers, W and H ≥ 1.
59    pub fn parse(s: &str) -> Result<Region> {
60        let bad = || {
61            Error::Usage(format!(
62                "--region '{s}': expected X,Y,WIDTH,HEIGHT in pixels (e.g. 1024,2048,512,512), \
63                 in the coordinates of the level read (--level, default 0)"
64            ))
65        };
66        let parts: Vec<u32> = s
67            .split(',')
68            .map(|p| p.trim().parse::<u32>())
69            .collect::<std::result::Result<_, _>>()
70            .map_err(|_| bad())?;
71        let [x, y, w, h] = parts[..] else {
72            return Err(bad());
73        };
74        if w == 0 || h == 0 {
75            return Err(Error::Usage(format!(
76                "--region '{s}': width and height must be at least 1"
77            )));
78        }
79        Ok(Region::new(x, y, w, h))
80    }
81
82    /// One past the last column.
83    pub fn right(&self) -> u64 {
84        u64::from(self.x) + u64::from(self.width)
85    }
86
87    /// One past the last row.
88    pub fn bottom(&self) -> u64 {
89        u64::from(self.y) + u64::from(self.height)
90    }
91
92    /// True when the region is the whole `width` × `height` plane.
93    pub fn is_full(&self, width: u32, height: u32) -> bool {
94        *self == Region::full(width, height)
95    }
96
97    /// A usage error (exit 2) unless the region is non-empty and lies inside a `width` ×
98    /// `height` plane. `what` names the plane in the message (e.g. `image 0 level 2`).
99    pub fn check_within(&self, width: u32, height: u32, what: &str) -> Result<()> {
100        if self.width == 0 || self.height == 0 {
101            return Err(Error::Usage(format!(
102                "region {self} is empty; width and height must be at least 1"
103            )));
104        }
105        if self.right() > u64::from(width) || self.bottom() > u64::from(height) {
106            return Err(Error::Usage(format!(
107                "region {self} extends past {what}, which is {width} x {height} pixels; \
108                 regions are in the pixel coordinates of the level read \
109                 (`info` → images[].resolution_levels lists each level's size)"
110            )));
111        }
112        Ok(())
113    }
114
115    /// The overlap with the rectangle at `(x, y)` of `w` × `h` (signed, may start left of or
116    /// above 0), as `(x0, y0, x1, y1)` in the same coordinates; `None` when they do not meet.
117    pub fn overlap(&self, x: i64, y: i64, w: u64, h: u64) -> Option<(i64, i64, i64, i64)> {
118        let wi = i64::try_from(w).ok()?;
119        let hi = i64::try_from(h).ok()?;
120        let x0 = x.max(i64::from(self.x));
121        let y0 = y.max(i64::from(self.y));
122        let x1 = x.saturating_add(wi).min(self.right() as i64);
123        let y1 = y.saturating_add(hi).min(self.bottom() as i64);
124        (x1 > x0 && y1 > y0).then_some((x0, y0, x1, y1))
125    }
126
127    /// Map a region of a `from` (width, height) level onto a `to` level of the same image: the
128    /// smallest `to` rectangle covering it (start rounded down, end rounded up), clamped to
129    /// the `to` plane and never empty.
130    pub fn rescale(&self, from: (u32, u32), to: (u32, u32)) -> Region {
131        let map = |v: u64, n_from: u32, n_to: u32, up: bool| -> u64 {
132            if n_from == 0 {
133                return 0;
134            }
135            let num = u128::from(v) * u128::from(n_to);
136            let d = u128::from(n_from);
137            let r = if up { num.div_ceil(d) } else { num / d };
138            u64::try_from(r).unwrap_or(u64::MAX).min(u64::from(n_to))
139        };
140        let x0 = map(u64::from(self.x), from.0, to.0, false);
141        let y0 = map(u64::from(self.y), from.1, to.1, false);
142        let x1 = map(self.right(), from.0, to.0, true).max(x0 + 1);
143        let y1 = map(self.bottom(), from.1, to.1, true).max(y0 + 1);
144        let clamp = |v: u64, n: u32| v.min(u64::from(n)) as u32;
145        let (x0, y0) = (
146            clamp(x0, to.0.saturating_sub(1)),
147            clamp(y0, to.1.saturating_sub(1)),
148        );
149        let (x1, y1) = (clamp(x1, to.0), clamp(y1, to.1));
150        Region::new(
151            x0,
152            y0,
153            x1.saturating_sub(x0).max(1),
154            y1.saturating_sub(y0).max(1),
155        )
156    }
157}
158
159impl std::fmt::Display for Region {
160    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
161        write!(f, "{},{},{},{}", self.x, self.y, self.width, self.height)
162    }
163}
164
165/// Allocate the buffer of a region plane (zeros), refusing regions above
166/// [`crate::pixel::MAX_PLANE_BYTES`] with the usual "plane too large" error.
167pub fn region_buffer(
168    format: &'static str,
169    region: Region,
170    bytes_per_pixel: usize,
171) -> Result<Vec<u8>> {
172    let n = plane_bytes_checked(format, region.width, region.height, bytes_per_pixel)?;
173    Ok(vec![0u8; n])
174}
175
176/// A decoded tile placed in a plane: `width` × `height` pixels, rows of `row_bytes` bytes
177/// (≥ `width` × bytes per pixel), its top-left pixel at `(x, y)` in the plane's coordinates
178/// (it may start left of or above the plane).
179#[derive(Debug, Clone, Copy)]
180pub struct PlacedTile<'a> {
181    /// The tile's samples, row by row.
182    pub data: &'a [u8],
183    /// Bytes per tile row.
184    pub row_bytes: usize,
185    /// Column of the tile's first pixel in the plane.
186    pub x: i64,
187    /// Row of the tile's first pixel in the plane.
188    pub y: i64,
189    /// Tile width in pixels.
190    pub width: u32,
191    /// Tile height in pixels.
192    pub height: u32,
193}
194
195/// Copy the part of `tile` that overlaps `region` into `out` (the region's buffer, rows of
196/// `region.width * bpp` bytes). Pixels outside the tile or the region are left untouched; short
197/// tile data is copied as far as it goes.
198pub fn paste_into_region(out: &mut [u8], region: Region, tile: &PlacedTile<'_>, bpp: usize) {
199    let (tx, ty) = (tile.x, tile.y);
200    let Some((x0, y0, x1, y1)) =
201        region.overlap(tx, ty, u64::from(tile.width), u64::from(tile.height))
202    else {
203        return;
204    };
205    let out_row = region.width as usize * bpp;
206    let len = (x1 - x0) as usize * bpp;
207    let src_x = (x0 - tx) as usize * bpp;
208    let dst_x = (x0 - i64::from(region.x)) as usize * bpp;
209    for y in y0..y1 {
210        let s = (y - ty) as usize * tile.row_bytes + src_x;
211        let d = (y - i64::from(region.y)) as usize * out_row + dst_x;
212        if let (Some(src), Some(dst)) = (tile.data.get(s..s + len), out.get_mut(d..d + len)) {
213            dst.copy_from_slice(src);
214        }
215    }
216}
217
218/// Crop `region` out of a whole plane (the generic region read). A usage error when the
219/// region does not lie inside the plane.
220pub fn crop(plane: Plane, region: Region, what: &str) -> Result<Plane> {
221    region.check_within(plane.width, plane.height, what)?;
222    if region.is_full(plane.width, plane.height) {
223        return Ok(plane);
224    }
225    let bpp = plane.samples_per_pixel.max(1) as usize * plane.pixel_type.bytes_per_sample();
226    let row = plane.row_bytes();
227    if plane.data.len() < row * plane.height as usize {
228        return Err(Error::Other(format!(
229            "plane holds {} bytes, expected {}",
230            plane.data.len(),
231            row * plane.height as usize
232        )));
233    }
234    let out_row = region.width as usize * bpp;
235    let mut data = Vec::with_capacity(out_row * region.height as usize);
236    for y in region.y..region.y + region.height {
237        let s = y as usize * row + region.x as usize * bpp;
238        data.extend_from_slice(&plane.data[s..s + out_row]);
239    }
240    Ok(Plane {
241        width: region.width,
242        height: region.height,
243        pixel_type: plane.pixel_type,
244        samples_per_pixel: plane.samples_per_pixel,
245        data,
246    })
247}
248
249/// Geometry of one resolution level of an image.
250#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
251pub struct ResolutionLevel {
252    /// Level index: 0 is full resolution, larger is more downsampled (`--level`).
253    pub level: u32,
254    /// Width in pixels.
255    pub size_x: u32,
256    /// Height in pixels.
257    pub size_y: u32,
258    /// Level-0 width over this level's width (1 for level 0; 2, 4, ... for a halving pyramid).
259    pub downsample_x: f64,
260    /// Level-0 height over this level's height.
261    pub downsample_y: f64,
262    /// Width of the tiles (subblocks, chunks) the level is stored in, when it is tiled: region
263    /// reads aligned to this grid decode each tile once.
264    #[serde(default, skip_serializing_if = "Option::is_none")]
265    pub tile_width: Option<u32>,
266    /// Height of the stored tiles.
267    #[serde(default, skip_serializing_if = "Option::is_none")]
268    pub tile_height: Option<u32>,
269    /// Number of z planes at this level, when it differs from the image's `size_z` (Imaris
270    /// downsamples z as well).
271    #[serde(default, skip_serializing_if = "Option::is_none")]
272    pub size_z: Option<u32>,
273}
274
275impl ResolutionLevel {
276    /// Level `level` of `size_x` × `size_y` pixels in an image whose level 0 is
277    /// `base_x` × `base_y`; downsampling factors are the size ratios, snapped to the power of
278    /// two `2^k` when the level is level 0 halved `k` times (rounding either way: within one
279    /// pixel of `base / 2^k`).
280    pub fn new(level: u32, size_x: u32, size_y: u32, base_x: u32, base_y: u32) -> Self {
281        let f = |b: u32, s: u32| {
282            if s == 0 {
283                return 1.0;
284            }
285            let r = f64::from(b) / f64::from(s);
286            let p = r.log2().round().clamp(0.0, 62.0).exp2();
287            if (f64::from(b) / p - f64::from(s)).abs() <= 1.0 {
288                return p;
289            }
290            (r * 1e6).round() / 1e6
291        };
292        ResolutionLevel {
293            level,
294            size_x,
295            size_y,
296            downsample_x: f(base_x, size_x),
297            downsample_y: f(base_y, size_y),
298            tile_width: None,
299            tile_height: None,
300            size_z: None,
301        }
302    }
303
304    /// With the stored tile size (ignored when it is 0 or not smaller than the level).
305    #[must_use]
306    pub fn with_tile(mut self, width: u32, height: u32) -> Self {
307        if width > 0 && height > 0 && (width < self.size_x || height < self.size_y) {
308            self.tile_width = Some(width.min(self.size_x));
309            self.tile_height = Some(height.min(self.size_y));
310        }
311        self
312    }
313}
314
315/// The resolution levels of an image, level 0 first: the reader's `resolution_levels` when it
316/// filled them, otherwise level 0 alone (from `size_x`/`size_y`).
317pub fn levels_of(im: &ImageInfo) -> Vec<ResolutionLevel> {
318    if im.resolution_levels.is_empty() {
319        vec![ResolutionLevel::new(
320            0, im.size_x, im.size_y, im.size_x, im.size_y,
321        )]
322    } else {
323        im.resolution_levels.clone()
324    }
325}
326
327/// `(width, height)` of level `level` of `im`, or a usage error naming the levels there are.
328pub fn level_size(im: &ImageInfo, level: u32) -> Result<(u32, u32)> {
329    if level == 0 {
330        return Ok((im.size_x, im.size_y));
331    }
332    let levels = levels_of(im);
333    levels
334        .iter()
335        .find(|l| l.level == level)
336        .map(|l| (l.size_x, l.size_y))
337        .ok_or_else(|| {
338            Error::Usage(format!(
339                "pyramid level {level} out of range for image {} ({} level{}: 0..{})",
340                im.index,
341                im.pyramid_levels.max(1),
342                if im.pyramid_levels > 1 { "s" } else { "" },
343                im.pyramid_levels.max(1)
344            ))
345        })
346}
347
348/// A cache of decoded tiles, bounded by the bytes it holds; the least recently used tile goes
349/// first. Readers keep one per open file so that overlapping or neighbouring region reads
350/// decode each tile once.
351#[derive(Debug)]
352pub struct TileCache<K, V = Vec<u8>> {
353    budget: usize,
354    held: usize,
355    tick: u64,
356    map: HashMap<K, (Arc<V>, usize, u64)>,
357}
358
359/// Default budget of a [`TileCache`]: 64 MiB of decoded samples.
360pub const DEFAULT_TILE_CACHE_BYTES: usize = 64 << 20;
361
362impl<K: Hash + Eq + Clone, V> Default for TileCache<K, V> {
363    fn default() -> Self {
364        TileCache::new(DEFAULT_TILE_CACHE_BYTES)
365    }
366}
367
368impl<K: Hash + Eq + Clone, V> TileCache<K, V> {
369    /// An empty cache that holds at most `budget` bytes (0 disables it).
370    pub fn new(budget: usize) -> Self {
371        TileCache {
372            budget,
373            held: 0,
374            tick: 0,
375            map: HashMap::new(),
376        }
377    }
378
379    /// The tile stored under `key`, if cached (and mark it recently used).
380    pub fn get(&mut self, key: &K) -> Option<Arc<V>> {
381        self.tick += 1;
382        let t = self.tick;
383        self.map.get_mut(key).map(|(v, _, used)| {
384            *used = t;
385            v.clone()
386        })
387    }
388
389    /// Store a decoded tile of `bytes` bytes; evicts the least recently used tiles to stay
390    /// within the budget. Tiles larger than a quarter of the budget are not kept.
391    pub fn put(&mut self, key: K, tile: Arc<V>, bytes: usize) {
392        if self.budget == 0 || bytes > self.budget / 4 {
393            return;
394        }
395        self.tick += 1;
396        if let Some((_, old, _)) = self.map.insert(key, (tile, bytes, self.tick)) {
397            self.held -= old;
398        }
399        self.held += bytes;
400        while self.held > self.budget {
401            let Some(k) = self
402                .map
403                .iter()
404                .min_by_key(|(_, (_, _, used))| *used)
405                .map(|(k, _)| k.clone())
406            else {
407                break;
408            };
409            if let Some((_, n, _)) = self.map.remove(&k) {
410                self.held -= n;
411            }
412        }
413    }
414
415    /// Bytes currently held.
416    pub fn bytes(&self) -> usize {
417        self.held
418    }
419
420    /// Drop every tile.
421    pub fn clear(&mut self) {
422        self.map.clear();
423        self.held = 0;
424    }
425}
426
427#[cfg(test)]
428mod tests {
429    use super::*;
430    use crate::pixel::PixelType;
431
432    fn ramp(w: u32, h: u32) -> Plane {
433        Plane {
434            width: w,
435            height: h,
436            pixel_type: PixelType::Uint16,
437            samples_per_pixel: 1,
438            data: (0..w * h).flat_map(|v| (v as u16).to_le_bytes()).collect(),
439        }
440    }
441
442    #[test]
443    fn parse_and_check() {
444        let r = Region::parse("10, 20,30,40").unwrap();
445        assert_eq!(r, Region::new(10, 20, 30, 40));
446        assert_eq!(r.to_string(), "10,20,30,40");
447        for bad in ["1,2,3", "1,2,3,4,5", "-1,0,1,1", "a,b,c,d", "0,0,0,5"] {
448            assert_eq!(Region::parse(bad).unwrap_err().exit_code(), 2, "{bad}");
449        }
450        assert!(r.check_within(40, 60, "p").is_ok());
451        let e = r.check_within(39, 60, "image 0 level 1").unwrap_err();
452        assert_eq!(e.exit_code(), 2);
453        assert!(e.to_string().contains("39 x 60"), "{e}");
454    }
455
456    #[test]
457    fn crop_matches_slicing() {
458        let p = ramp(7, 5);
459        let c = crop(p.clone(), Region::new(2, 1, 3, 2), "p").unwrap();
460        let v: Vec<u16> = c
461            .data
462            .chunks(2)
463            .map(|b| u16::from_le_bytes([b[0], b[1]]))
464            .collect();
465        assert_eq!(v, [9, 10, 11, 16, 17, 18]);
466        assert_eq!(
467            crop(p.clone(), Region::full(7, 5), "p").unwrap().data,
468            p.data
469        );
470        assert!(crop(p, Region::new(5, 0, 3, 1), "p").is_err());
471    }
472
473    #[test]
474    fn paste_clips_to_tile_and_region() {
475        // A 4x4 tile at (-2, 1) pasted into region (0, 0, 3, 3) of a plane.
476        let tile: Vec<u8> = (0..16).collect();
477        let r = Region::new(0, 0, 3, 3);
478        let mut out = vec![0xFFu8; 9];
479        paste_into_region(
480            &mut out,
481            r,
482            &PlacedTile {
483                data: &tile,
484                row_bytes: 4,
485                x: -2,
486                y: 1,
487                width: 4,
488                height: 4,
489            },
490            1,
491        );
492        assert_eq!(out, [0xFF, 0xFF, 0xFF, 2, 3, 0xFF, 6, 7, 0xFF]);
493        // No overlap: untouched.
494        let mut out2 = vec![1u8; 9];
495        paste_into_region(
496            &mut out2,
497            r,
498            &PlacedTile {
499                data: &tile,
500                row_bytes: 4,
501                x: 3,
502                y: 0,
503                width: 4,
504                height: 4,
505            },
506            1,
507        );
508        assert_eq!(out2, [1u8; 9]);
509    }
510
511    #[test]
512    fn rescale_covers_the_region() {
513        let r = Region::new(101, 51, 10, 10);
514        let s = r.rescale((1000, 500), (250, 125));
515        assert_eq!(s, Region::new(25, 12, 3, 4));
516        // Always at least one pixel and inside the target.
517        let t = Region::new(999, 499, 1, 1).rescale((1000, 500), (3, 2));
518        assert_eq!(t, Region::new(2, 1, 1, 1));
519    }
520
521    #[test]
522    #[allow(clippy::float_cmp)] // the factors are exact powers of two (or exact ratios)
523    fn halving_pyramids_have_power_of_two_factors() {
524        let l = ResolutionLevel::new(2, 16793, 14581, 67170, 58321);
525        assert_eq!((l.downsample_x, l.downsample_y), (4.0, 4.0));
526        assert_eq!(
527            ResolutionLevel::new(8, 263, 228, 67170, 58321).downsample_x,
528            256.0
529        );
530        // A 3x pyramid keeps its own ratio.
531        assert_eq!(ResolutionLevel::new(1, 100, 67, 300, 200).downsample_x, 3.0);
532        assert!((ResolutionLevel::new(1, 97, 67, 300, 200).downsample_x - 3.092_784).abs() < 1e-6);
533    }
534
535    #[test]
536    fn cache_evicts_least_recently_used() {
537        let mut c: TileCache<u32> = TileCache::new(40);
538        c.put(1, Arc::new(vec![0; 10]), 10);
539        c.put(2, Arc::new(vec![0; 10]), 10);
540        c.put(3, Arc::new(vec![0; 10]), 10);
541        assert!(c.get(&1).is_some());
542        c.put(4, Arc::new(vec![0; 10]), 10);
543        c.put(5, Arc::new(vec![0; 10]), 10);
544        assert!(c.bytes() <= 40);
545        assert!(c.get(&2).is_none(), "2 was least recently used");
546        assert!(c.get(&1).is_some());
547        c.put(6, Arc::new(vec![0; 11]), 11); // above a quarter of the budget: not kept
548        assert!(c.get(&6).is_none());
549    }
550}