range_check/
lib.rs

1// Copyright 2026 The Fuchsia Authors
2//
3// Use of this source code is governed by a MIT-style
4// license that can be found in the LICENSE file or at
5// https://opensource.org/licenses/MIT
6
7//! Range checking and interval arithmetic utilities mirroring `<kernel/range_check.h>`.
8
9#![no_std]
10
11use core::ops::Range;
12
13/// Constructs a half-open `Range<u64>` from `(offset, len)`.
14///
15/// Returns `None` if `offset + len` overflows `u64`.
16pub const fn from_offset_len(offset: u64, len: u64) -> Option<Range<u64>> {
17    match offset.checked_add(len) {
18        Some(end) => Some(offset..end),
19        None => None,
20    }
21}
22
23/// Constructs a half-open `Range<usize>` from `(offset, len)`.
24///
25/// Returns `None` if `offset + len` overflows `usize`.
26pub const fn from_offset_len_usize(offset: usize, len: usize) -> Option<Range<usize>> {
27    match offset.checked_add(len) {
28        Some(end) => Some(offset..end),
29        None => None,
30    }
31}
32
33/// Returns true if `inner` is fully contained inside `outer`.
34///
35/// Both ranges are treated as half-open intervals `[start, end)`.
36/// An empty `inner` range is considered contained within `outer` iff `inner.start` lies within `outer.start..=outer.end`.
37pub fn in_range<T: Ord + Copy>(inner: &Range<T>, outer: &Range<T>) -> bool {
38    inner.start >= outer.start && inner.end <= outer.end && inner.start <= inner.end
39}
40
41/// Returns true if the range `[offset, offset + len)` is fully inside `[0, max)`.
42///
43/// Returns `false` on arithmetic overflow or if out of bounds.
44pub fn in_range_max(offset: u64, len: u64, max: u64) -> bool {
45    let Some(range) = from_offset_len(offset, len) else {
46        return false;
47    };
48    in_range(&range, &(0..max))
49}
50
51/// Returns true if the range `[offset, offset + len)` is fully inside `[min, max)`.
52///
53/// Returns `false` on arithmetic overflow, underflow, or if out of bounds.
54pub fn in_range_min_max(offset: u64, len: u64, min: u64, max: u64) -> bool {
55    let Some(range) = from_offset_len(offset, len) else {
56        return false;
57    };
58    in_range(&range, &(min..max))
59}
60
61/// Trims `range` so that it fits within `0..trim_to_len`.
62///
63/// Returns `Some(trimmed_range)` if `range.start <= trim_to_len`.
64/// Returns `None` if `range.start > trim_to_len` or `range.start > range.end`.
65pub fn trim_range<T: Ord + Copy>(range: &Range<T>, trim_to_len: T) -> Option<Range<T>> {
66    if range.start > trim_to_len || range.start > range.end {
67        return None;
68    }
69    let end = core::cmp::min(range.end, trim_to_len);
70    Some(range.start..end)
71}
72
73/// Trims `[offset, offset + len)` to `[0, trim_to_len)`.
74///
75/// Returns `Some(trimmed_len)` on success, or `None` if `offset > trim_to_len` or on overflow.
76pub fn trim_range_offset_len(offset: u64, len: u64, trim_to_len: u64) -> Option<u64> {
77    let range = from_offset_len(offset, len)?;
78    let trimmed = trim_range(&range, trim_to_len)?;
79    Some(trimmed.end - trimmed.start)
80}
81
82/// Determines if two half-open ranges overlap.
83///
84/// Empty ranges (where `start >= end`) do not overlap with any range.
85pub fn intersects<T: Ord + Copy>(r1: &Range<T>, r2: &Range<T>) -> bool {
86    r1.start < r1.end && r2.start < r2.end && r1.start < r2.end && r2.start < r1.end
87}
88
89/// Determines if two `(offset, len)` pairs overlap as half-open ranges `[offset, offset + len)`.
90///
91/// Returns `false` if either length is zero or if an integer overflow occurs on `offset + len`.
92pub fn intersects_offset_len(offset1: u64, len1: u64, offset2: u64, len2: u64) -> bool {
93    let Some(r1) = from_offset_len(offset1, len1) else {
94        return false;
95    };
96    let Some(r2) = from_offset_len(offset2, len2) else {
97        return false;
98    };
99    intersects(&r1, &r2)
100}
101
102/// Computes the intersection of two half-open ranges, returning `Some(intersection)` if they
103/// overlap, or `None` if they do not.
104pub fn get_intersect<T: Ord + Copy>(r1: &Range<T>, r2: &Range<T>) -> Option<Range<T>> {
105    if !intersects(r1, r2) {
106        return None;
107    }
108    let start = core::cmp::max(r1.start, r2.start);
109    let end = core::cmp::min(r1.end, r2.end);
110    Some(start..end)
111}
112
113/// Computes the intersection of two `(offset, len)` pairs, returning `Some((offset, len))`
114/// if they overlap, or `None` if they do not.
115pub fn get_intersect_offset_len(
116    offset1: u64,
117    len1: u64,
118    offset2: u64,
119    len2: u64,
120) -> Option<(u64, u64)> {
121    let r1 = from_offset_len(offset1, len1)?;
122    let r2 = from_offset_len(offset2, len2)?;
123    let intersection = get_intersect(&r1, &r2)?;
124    Some((intersection.start, intersection.end - intersection.start))
125}
126
127/// Extension trait providing range-checking methods directly on `Range<T>`.
128pub trait RangeExt<T> {
129    /// Returns true if this range is fully contained inside `outer`.
130    fn in_range(&self, outer: &Range<T>) -> bool;
131
132    /// Returns true if this range overlaps with `other`.
133    fn intersects(&self, other: &Range<T>) -> bool;
134
135    /// Computes the intersection of this range with `other`.
136    fn intersect(&self, other: &Range<T>) -> Option<Range<T>>;
137
138    /// Trims this range to fit within `0..trim_to_len`.
139    fn trim(&self, trim_to_len: T) -> Option<Range<T>>;
140}
141
142impl<T: Ord + Copy> RangeExt<T> for Range<T> {
143    fn in_range(&self, outer: &Range<T>) -> bool {
144        in_range(self, outer)
145    }
146
147    fn intersects(&self, other: &Range<T>) -> bool {
148        intersects(self, other)
149    }
150
151    fn intersect(&self, other: &Range<T>) -> Option<Range<T>> {
152        get_intersect(self, other)
153    }
154
155    fn trim(&self, trim_to_len: T) -> Option<Range<T>> {
156        trim_range(self, trim_to_len)
157    }
158}
159
160#[cfg(test)]
161mod tests {
162    use super::*;
163
164    #[test]
165    fn test_in_range_basic() {
166        // [0, 1024) is within [0, 4096)
167        assert!(in_range_max(0, 1024, 4096));
168        assert!(in_range_min_max(0, 1024, 0, 4096));
169        assert!((0..1024).in_range(&(0..4096)));
170
171        // [0, 1024) is not within [1, 4096)
172        assert!(!in_range_min_max(0, 1024, 1, 4096));
173        assert!(!(0..1024).in_range(&(1..4096)));
174
175        // [0, 1024) is within [0, 1024)
176        assert!(in_range_min_max(0, 1024, 0, 1024));
177        assert!((0..1024).in_range(&(0..1024)));
178
179        // [0, 1024) is not within [0, 1023)
180        assert!(!in_range_min_max(0, 1024, 0, 1023));
181        assert!(!(0..1024).in_range(&(0..1023)));
182
183        // offset < min tests
184        assert!(!in_range_min_max(32768, 1024, 524288, 1048576));
185        assert!(!(32768..33792).in_range(&(524288..1048576)));
186
187        // Right overlap, left overlap, full overlap
188        assert!(!in_range_min_max(4000, 1000, 4500, 5500));
189        assert!(!in_range_min_max(5000, 1000, 4500, 5500));
190        assert!(!in_range_min_max(4000, 2000, 4500, 5500));
191    }
192
193    #[test]
194    fn test_in_range_overflow() {
195        assert!(!in_range_max(u64::MAX - 10, 20, u64::MAX));
196        assert!(!in_range_min_max(u64::MAX - 10, 20, 0, u64::MAX));
197    }
198
199    #[test]
200    fn test_trim_range() {
201        assert_eq!(trim_range_offset_len(0, 1000, 500), Some(500));
202        assert_eq!(trim_range_offset_len(0, 1000, 2000), Some(1000));
203        assert_eq!(trim_range_offset_len(500, 1000, 1000), Some(500));
204        assert_eq!(trim_range_offset_len(1000, 1000, 1000), Some(0));
205        assert_eq!(trim_range_offset_len(1500, 1000, 1000), None);
206
207        assert_eq!((0..1000).trim(500), Some(0..500));
208        assert_eq!((0..1000).trim(2000), Some(0..1000));
209        assert_eq!((1500..2500).trim(1000), None);
210    }
211
212    #[test]
213    fn test_intersects() {
214        // Disjoint ranges
215        assert!(!intersects_offset_len(0, 10, 10, 10));
216        assert!(!intersects_offset_len(10, 10, 0, 10));
217        assert!(!(0..10).intersects(&(10..20)));
218        assert!(!(10..20).intersects(&(0..10)));
219
220        // Overlapping ranges
221        assert!(intersects_offset_len(0, 10, 5, 10));
222        assert!(intersects_offset_len(5, 10, 0, 10));
223        assert!((0..10).intersects(&(5..15)));
224        assert!((5..15).intersects(&(0..10)));
225
226        // Fully contained
227        assert!(intersects_offset_len(0, 20, 5, 5));
228        assert!(intersects_offset_len(5, 5, 0, 20));
229        assert!((0..20).intersects(&(5..10)));
230        assert!((5..10).intersects(&(0..20)));
231
232        // Zero-length regions do not intersect
233        assert!(!intersects_offset_len(5, 0, 0, 20));
234        assert!(!intersects_offset_len(0, 20, 5, 0));
235        assert!(!(5..5).intersects(&(0..20)));
236        assert!(!(0..20).intersects(&(5..5)));
237    }
238
239    #[test]
240    fn test_get_intersect() {
241        assert_eq!(get_intersect_offset_len(0, 10, 10, 10), None);
242        assert_eq!(get_intersect_offset_len(0, 10, 5, 10), Some((5, 5)));
243        assert_eq!(get_intersect_offset_len(5, 10, 0, 10), Some((5, 5)));
244        assert_eq!(get_intersect_offset_len(0, 20, 5, 10), Some((5, 10)));
245        assert_eq!(get_intersect_offset_len(5, 10, 0, 20), Some((5, 10)));
246
247        assert_eq!((0..10).intersect(&(10..20)), None);
248        assert_eq!((0..10).intersect(&(5..15)), Some(5..10));
249        assert_eq!((5..15).intersect(&(0..10)), Some(5..10));
250        assert_eq!((0..20).intersect(&(5..15)), Some(5..15));
251    }
252}
range_check/lib.rs

range_check/
lib.rs
