numeric_domains/
rnum.rs

1use core::ops::{Add, Div, Mul, Neg, Not, Rem, Sub};
2
3/// Range number.
4///
5/// This independent signed/unsigned-bounds representation follows the scalar
6/// range information maintained alongside tracked numbers by the Linux eBPF
7/// verifier:
8/// <https://docs.kernel.org/bpf/verifier.html#register-value-tracking>
9#[derive(Debug, Clone, Copy, PartialEq, Eq)]
10pub struct Rnum {
11    max: u64,
12    min: u64,
13
14    smax: i64,
15    smin: i64,
16    empty: bool,
17}
18
19impl Rnum {
20    const fn unknown() -> Self {
21        Self {
22            min: u64::MIN,
23            max: u64::MAX,
24            smin: i64::MIN,
25            smax: i64::MAX,
26            empty: false,
27        }
28    }
29
30    /// Construct independent unsigned and signed inclusive ranges.
31    pub const fn new(min: u64, max: u64, smin: i64, smax: i64) -> Option<Self> {
32        if min <= max && smin <= smax {
33            Some(Self {
34                min,
35                max,
36                smin,
37                smax,
38                empty: false,
39            })
40        } else {
41            None
42        }
43    }
44
45    pub const fn from_value(value: u64) -> Self {
46        let signed = value as i64;
47        Self {
48            min: value,
49            max: value,
50            smin: signed,
51            smax: signed,
52            empty: false,
53        }
54    }
55
56    pub const fn unsigned_bounds(&self) -> (u64, u64) {
57        (self.min, self.max)
58    }
59
60    pub const fn signed_bounds(&self) -> (i64, i64) {
61        (self.smin, self.smax)
62    }
63
64    /// Whether the domain contains exactly one machine value.
65    pub const fn is_const(&self) -> bool {
66        matches!((self.min_value(), self.max_value()), (Some(min), Some(max)) if min == max)
67    }
68
69    /// Return the sole contained value, if this domain is constant.
70    pub const fn value(&self) -> Option<u64> {
71        match self.extrema() {
72            Some((min, max)) if min == max => Some(min),
73            _ => None,
74        }
75    }
76
77    /// Whether the domain contains at least one machine value.
78    pub const fn is_defined(&self) -> bool {
79        self.has_value()
80    }
81
82    /// Whether this domain includes `value` in both interpretations.
83    pub const fn contains_value(&self, value: u64) -> bool {
84        !self.empty
85            && self.min <= value
86            && value <= self.max
87            && self.smin <= value as i64
88            && (value as i64) <= self.smax
89    }
90
91    /// Return the least range containing both operands.
92    pub const fn union(&self, other: Self) -> Self {
93        if self.empty || !self.has_value() {
94            return other;
95        }
96        if other.empty || !other.has_value() {
97            return *self;
98        }
99        Self {
100            min: if self.min < other.min {
101                self.min
102            } else {
103                other.min
104            },
105            max: if self.max > other.max {
106                self.max
107            } else {
108                other.max
109            },
110            smin: if self.smin < other.smin {
111                self.smin
112            } else {
113                other.smin
114            },
115            smax: if self.smax > other.smax {
116                self.smax
117            } else {
118                other.smax
119            },
120            empty: false,
121        }
122    }
123
124    /// Return the values represented by both operands.
125    pub const fn intersection(&self, other: Self) -> Self {
126        if self.empty || other.empty {
127            return Self::empty();
128        }
129        let result = Self {
130            min: if self.min > other.min {
131                self.min
132            } else {
133                other.min
134            },
135            max: if self.max < other.max {
136                self.max
137            } else {
138                other.max
139            },
140            smin: if self.smin > other.smin {
141                self.smin
142            } else {
143                other.smin
144            },
145            smax: if self.smax < other.smax {
146                self.smax
147            } else {
148                other.smax
149            },
150            empty: false,
151        };
152        if result.min > result.max || result.smin > result.smax || !result.has_value() {
153            Self::empty()
154        } else {
155            result
156        }
157    }
158
159    /// Whether this abstract range includes all bounds represented by `other`.
160    pub const fn contains(&self, other: Self) -> bool {
161        !other.has_value()
162            || (self.has_value()
163                && self.min <= other.min
164                && other.max <= self.max
165                && self.smin <= other.smin
166                && other.smax <= self.smax)
167    }
168
169    pub const fn has_value(&self) -> bool {
170        self.extrema().is_some()
171    }
172
173    pub const fn min_value(&self) -> Option<u64> {
174        match self.extrema() {
175            Some((min, _)) => Some(min),
176            None => None,
177        }
178    }
179
180    pub const fn max_value(&self) -> Option<u64> {
181        match self.extrema() {
182            Some((_, max)) => Some(max),
183            None => None,
184        }
185    }
186
187    const fn extrema(&self) -> Option<(u64, u64)> {
188        if self.empty {
189            return None;
190        }
191        let mut result: Option<(u64, u64)> = None;
192
193        if self.smax >= 0 {
194            let low = (if self.smin > 0 { self.smin } else { 0 }) as u64;
195            let low = if low > self.min { low } else { self.min };
196            let high = self.smax as u64;
197            let high = if high < self.max { high } else { self.max };
198            if low <= high {
199                result = Some((low, high));
200            }
201        }
202        if self.smin < 0 {
203            let low = self.smin as u64;
204            let low = if low > self.min { low } else { self.min };
205            let signed_high = if self.smax < -1 { self.smax } else { -1 };
206            let high = signed_high as u64;
207            let high = if high < self.max { high } else { self.max };
208            if low <= high {
209                result = Some(match result {
210                    Some((min, max)) => (
211                        if min < low { min } else { low },
212                        if max > high { max } else { high },
213                    ),
214                    None => (low, high),
215                });
216            }
217        }
218        result
219    }
220
221    const fn empty() -> Self {
222        Self {
223            min: 0,
224            max: 0,
225            smin: 0,
226            smax: 0,
227            empty: true,
228        }
229    }
230
231    const fn bounded(min: u64, max: u64, smin: i64, smax: i64) -> Self {
232        let result = Self {
233            min,
234            max,
235            smin,
236            smax,
237            empty: false,
238        };
239        // The bounds are computed independently.  A valid input always leaves
240        // at least one concrete result in their intersection, but retaining
241        // this guard makes the helper robust against future transfer functions.
242        if result.has_value() {
243            result
244        } else {
245            Self::unknown()
246        }
247    }
248
249    const fn signed_hull(min: u64, max: u64) -> (i64, i64) {
250        if max <= i64::MAX as u64 || min > i64::MAX as u64 {
251            (min as i64, max as i64)
252        } else {
253            (i64::MIN, i64::MAX)
254        }
255    }
256
257    pub const fn add(self, other: Self) -> Self {
258        if !self.has_value() || !other.has_value() {
259            return Self::empty();
260        }
261        let (min, max) = if self.max <= u64::MAX - other.max {
262            (self.min + other.min, self.max + other.max)
263        } else {
264            (u64::MIN, u64::MAX)
265        };
266        let signed_min = self.smin as i128 + other.smin as i128;
267        let signed_max = self.smax as i128 + other.smax as i128;
268        let (smin, smax) = if signed_min >= i64::MIN as i128 && signed_max <= i64::MAX as i128 {
269            (signed_min as i64, signed_max as i64)
270        } else {
271            (i64::MIN, i64::MAX)
272        };
273        Self::bounded(min, max, smin, smax)
274    }
275
276    pub const fn subtract(self, other: Self) -> Self {
277        if !self.has_value() || !other.has_value() {
278            return Self::empty();
279        }
280        let (min, max) = if self.min >= other.max {
281            (self.min - other.max, self.max - other.min)
282        } else {
283            (u64::MIN, u64::MAX)
284        };
285        let signed_min = self.smin as i128 - other.smax as i128;
286        let signed_max = self.smax as i128 - other.smin as i128;
287        let (smin, smax) = if signed_min >= i64::MIN as i128 && signed_max <= i64::MAX as i128 {
288            (signed_min as i64, signed_max as i64)
289        } else {
290            (i64::MIN, i64::MAX)
291        };
292        Self::bounded(min, max, smin, smax)
293    }
294
295    pub const fn negate(self) -> Self {
296        if !self.has_value() {
297            return Self::empty();
298        }
299        let (min, max) = if self.min == 0 && self.max == 0 {
300            (0, 0)
301        } else if self.min > 0 {
302            (self.max.wrapping_neg(), self.min.wrapping_neg())
303        } else {
304            (u64::MIN, u64::MAX)
305        };
306        let (smin, smax) = if self.smin != i64::MIN {
307            (-self.smax, -self.smin)
308        } else {
309            (i64::MIN, i64::MAX)
310        };
311        Self::bounded(min, max, smin, smax)
312    }
313
314    pub const fn bit_not(self) -> Self {
315        if !self.has_value() {
316            return Self::empty();
317        }
318        Self::bounded(!self.max, !self.min, !self.smax, !self.smin)
319    }
320
321    pub const fn multiply(self, other: Self) -> Self {
322        if !self.has_value() || !other.has_value() {
323            return Self::empty();
324        }
325        let (min, max) = if self.max == 0 || other.max <= u64::MAX / self.max {
326            (self.min * other.min, self.max * other.max)
327        } else {
328            (u64::MIN, u64::MAX)
329        };
330        let products = [
331            self.smin as i128 * other.smin as i128,
332            self.smin as i128 * other.smax as i128,
333            self.smax as i128 * other.smin as i128,
334            self.smax as i128 * other.smax as i128,
335        ];
336        let mut signed_min = products[0];
337        let mut signed_max = products[0];
338        let mut index = 1;
339        while index < products.len() {
340            if products[index] < signed_min {
341                signed_min = products[index];
342            }
343            if products[index] > signed_max {
344                signed_max = products[index];
345            }
346            index += 1;
347        }
348        let (smin, smax) = if signed_min >= i64::MIN as i128 && signed_max <= i64::MAX as i128 {
349            (signed_min as i64, signed_max as i64)
350        } else {
351            (i64::MIN, i64::MAX)
352        };
353        Self::bounded(min, max, smin, smax)
354    }
355
356    pub const fn checked_div(self, other: Self) -> Option<Self> {
357        if !self.has_value() || !other.has_value() {
358            return Some(Self::empty());
359        }
360        if other.max == 0 {
361            return None;
362        }
363        let least_divisor = if other.min == 0 { 1 } else { other.min };
364        let min = self.min / other.max;
365        let max = self.max / least_divisor;
366        let (smin, smax) = Self::signed_hull(min, max);
367        Some(Self::bounded(min, max, smin, smax))
368    }
369
370    pub const fn divide(self, other: Self) -> Self {
371        match self.checked_div(other) {
372            Some(result) => result,
373            None => Self::empty(),
374        }
375    }
376
377    pub const fn remainder(self, other: Self) -> Self {
378        if !self.has_value() || !other.has_value() {
379            return Self::empty();
380        }
381        if other.max == 0 {
382            return Self::empty();
383        }
384        let max = if self.max < other.max - 1 {
385            self.max
386        } else {
387            other.max - 1
388        };
389        let (smin, smax) = Self::signed_hull(0, max);
390        Self::bounded(0, max, smin, smax)
391    }
392}
393
394impl Default for Rnum {
395    /// Default is the range containing every 64-bit machine value.
396    fn default() -> Self {
397        Self::unknown()
398    }
399}
400
401impl Add for Rnum {
402    type Output = Rnum;
403    fn add(self, other: Self) -> Self {
404        Self::add(self, other)
405    }
406}
407
408impl Sub for Rnum {
409    type Output = Rnum;
410    fn sub(self, other: Self) -> Self {
411        self.subtract(other)
412    }
413}
414
415impl Neg for Rnum {
416    type Output = Rnum;
417    fn neg(self) -> Self {
418        self.negate()
419    }
420}
421
422impl Not for Rnum {
423    type Output = Rnum;
424    fn not(self) -> Self {
425        self.bit_not()
426    }
427}
428
429impl Mul for Rnum {
430    type Output = Rnum;
431    fn mul(self, other: Self) -> Self {
432        self.multiply(other)
433    }
434}
435
436impl Div for Rnum {
437    type Output = Rnum;
438    fn div(self, other: Self) -> Self {
439        self.divide(other)
440    }
441}
442
443impl Rem for Rnum {
444    type Output = Rnum;
445    fn rem(self, other: Self) -> Self {
446        self.remainder(other)
447    }
448}
numeric_domains/rnum.rs

numeric_domains/
rnum.rs
