numeric_domains/
tnum.rs

1use core::ops::{Add, BitAnd, BitOr, BitXor, Not, Shl, Shr};
2
3/// Tracking number
4///
5/// Tracks on a bit-by-bit level whether we know the value of a bit & what that value is (if
6/// known).
7///
8/// References:
9///  - Linux's production implementation: <https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/bpf/tnum.c>
10///  - Linux verifier documentation: <https://docs.kernel.org/bpf/verifier.html#register-value-tracking>
11///  - <https://bitmath.blogspot.com/2013/08/addition-in-bitfield-domain.html>
12///  - <https://bitmath.blogspot.com/2014/02/addition-in-bitfield-domain-alternative.html>
13///  - "Abstract Domains for Bit-Level Machine Integer and Floating-point Operations"
14///    ([paper](https://www-apr.lip6.fr/~mine/publi/article-mine-wing12.pdf))
15///  - <https://www.omnimaga.org/other-computer-languages-help/addition-in-the-bitfield-domain/>
16///
17// bits in mask: 1 = unknown, 0 = known
18// bits in value, if known: 1 = 1, 0 = 0
19// bits in value, if unknown = 0 (iow: 1 is forbidden if bit is unknown)
20#[derive(Copy, Clone, PartialEq, Eq, Debug)]
21pub struct Tnum {
22    value: u64,
23    mask: u64,
24    empty: bool,
25}
26
27impl Tnum {
28    /// The empty set.
29    pub const fn empty() -> Self {
30        Self {
31            value: 0,
32            mask: 0,
33            empty: true,
34        }
35    }
36
37    /// Construct a tracking number from its known value and unknown-bit mask.
38    ///
39    /// Value bits covered by the mask are cleared to maintain the canonical
40    /// `value & mask == 0` representation.
41    pub const fn from_parts(value: u64, mask: u64) -> Self {
42        Self {
43            value: value & !mask,
44            mask,
45            empty: false,
46        }
47    }
48
49    pub const fn from_value(value: u64) -> Self {
50        Self {
51            value,
52            mask: 0,
53            empty: false,
54        }
55    }
56
57    /// Return the canonical `(known_value, unknown_mask)` representation.
58    pub const fn parts(&self) -> Option<(u64, u64)> {
59        if self.empty {
60            None
61        } else {
62            Some((self.value, self.mask))
63        }
64    }
65
66    pub const fn is_const(&self) -> bool {
67        !self.empty && self.mask == 0
68    }
69
70    pub const fn value(&self) -> Option<u64> {
71        if self.is_const() {
72            Some(self.value)
73        } else {
74            None
75        }
76    }
77
78    /// Whether this abstract value includes `value`.
79    pub const fn contains_value(&self, value: u64) -> bool {
80        !self.empty && value & !self.mask == self.value
81    }
82
83    /// Return the least tracking number containing both operands.
84    pub const fn union(self, other: Self) -> Self {
85        if self.empty {
86            return other;
87        }
88        if other.empty {
89            return self;
90        }
91        let differing = self.value ^ other.value;
92        let mask = self.mask | other.mask | differing;
93        Self::from_parts(self.value, mask)
94    }
95
96    /// Return the values represented by both operands.
97    pub const fn intersection(self, other: Self) -> Self {
98        if self.empty || other.empty {
99            return Self::empty();
100        }
101        let conflicting = (self.value ^ other.value) & !(self.mask | other.mask);
102        if conflicting != 0 {
103            Self::empty()
104        } else {
105            Self::from_parts(self.value | other.value, self.mask & other.mask)
106        }
107    }
108
109    pub const fn is_defined(&self) -> bool {
110        !self.empty
111    }
112
113    /// Whether this tracking number includes every value in `other`.
114    pub const fn contains(&self, other: Self) -> bool {
115        other.empty
116            || (!self.empty
117                && other.mask & !self.mask == 0
118                && other.value & !self.mask == self.value)
119    }
120
121    pub const fn has_value(&self) -> bool {
122        !self.empty
123    }
124
125    pub const fn min_value(&self) -> Option<u64> {
126        if self.empty {
127            None
128        } else {
129            Some(self.value)
130        }
131    }
132
133    pub const fn max_value(&self) -> Option<u64> {
134        if self.empty {
135            None
136        } else {
137            Some(self.value | self.mask)
138        }
139    }
140
141    pub const fn unsigned_bounds(&self) -> (u64, u64) {
142        (self.value, self.value | self.mask)
143    }
144
145    pub const fn signed_bounds(&self) -> (i64, i64) {
146        const SIGN: u64 = 1 << 63;
147        if self.mask & SIGN != 0 {
148            (
149                (self.value | SIGN) as i64,
150                ((self.value | self.mask) & !SIGN) as i64,
151            )
152        } else {
153            (self.value as i64, (self.value | self.mask) as i64)
154        }
155    }
156
157    pub const fn bit_not(self) -> Self {
158        if self.empty {
159            return self;
160        }
161        Self {
162            value: !self.value & !self.mask,
163            mask: self.mask,
164            empty: false,
165        }
166    }
167
168    pub const fn bit_or(self, other: Self) -> Self {
169        if self.empty || other.empty {
170            return Self::empty();
171        }
172        let value = self.value | other.value;
173        let mask = (self.mask | other.mask) & !value;
174        Self {
175            value,
176            mask,
177            empty: false,
178        }
179    }
180
181    pub const fn bit_and(self, other: Self) -> Self {
182        if self.empty || other.empty {
183            return Self::empty();
184        }
185        let value = self.value & other.value;
186        let may_be_one = (self.value | self.mask) & (other.value | other.mask);
187        Self::from_parts(value, may_be_one & !value)
188    }
189
190    pub const fn bit_xor(self, other: Self) -> Self {
191        if self.empty || other.empty {
192            return Self::empty();
193        }
194        Self::from_parts(self.value ^ other.value, self.mask | other.mask)
195    }
196
197    pub const fn shift_left(self, shift: u8) -> Self {
198        if self.empty {
199            return self;
200        }
201        let shift = (shift as u32) % 64;
202        Self {
203            value: self.value.wrapping_shl(shift),
204            mask: self.mask.wrapping_shl(shift),
205            empty: false,
206        }
207    }
208
209    pub const fn shift_right(self, shift: u8) -> Self {
210        if self.empty {
211            return self;
212        }
213        let shift = (shift as u32) % 64;
214        Self {
215            value: self.value.wrapping_shr(shift),
216            mask: self.mask.wrapping_shr(shift),
217            empty: false,
218        }
219    }
220
221    pub const fn add(self, other: Self) -> Self {
222        if self.empty || other.empty {
223            return Self::empty();
224        }
225        let mask_sum = self.mask.wrapping_add(other.mask);
226        let value_sum = self.value.wrapping_add(other.value);
227        let sigma = mask_sum.wrapping_add(value_sum);
228        let carry_changes = sigma ^ value_sum;
229        let mask = carry_changes | self.mask | other.mask;
230        Self::from_parts(value_sum, mask)
231    }
232}
233
234impl Default for Tnum {
235    /// Default is a completely unknown value
236    fn default() -> Self {
237        Self {
238            value: 0,
239            mask: !0,
240            empty: false,
241        }
242    }
243}
244
245impl Not for Tnum {
246    type Output = Tnum;
247    fn not(self) -> Self {
248        self.bit_not()
249    }
250}
251
252impl BitOr for Tnum {
253    type Output = Tnum;
254    fn bitor(self, other: Self) -> Self {
255        self.bit_or(other)
256    }
257}
258
259impl BitAnd for Tnum {
260    type Output = Tnum;
261    fn bitand(self, other: Self) -> Self {
262        self.bit_and(other)
263    }
264}
265
266impl BitXor for Tnum {
267    type Output = Tnum;
268    fn bitxor(self, other: Self) -> Self {
269        self.bit_xor(other)
270    }
271}
272
273impl Shl<u8> for Tnum {
274    type Output = Tnum;
275    fn shl(self, shift: u8) -> Self {
276        self.shift_left(shift)
277    }
278}
279
280impl Shr<u8> for Tnum {
281    type Output = Tnum;
282    fn shr(self, shift: u8) -> Self {
283        self.shift_right(shift)
284    }
285}
286
287impl Add for Tnum {
288    type Output = Tnum;
289    fn add(self, other: Self) -> Self::Output {
290        self.add(other)
291    }
292}
293
294/*
295impl Sub for Tnum {
296    type Output = Tnum;
297    fn sub(self, other: Self) -> Self {
298        unimplemented!()
299    }
300}
301
302impl Mul for Tnum {
303    type Output = Tnum;
304    fn mul(self, other: Self) -> Self {
305        unimplemented!()
306    }
307}
308
309impl Div for Tnum {
310    type Output = Tnum;
311    fn div(self, other: Self) -> Self {
312        unimplemented!()
313    }
314}
315
316impl Rem for Tnum {
317    type Output = Tnum;
318    fn rem(self, other: Self) -> Self {
319        unimplemented!()
320    }
321}
322
323impl Neg for Tnum {
324    type Output = Tnum;
325    fn neg(self) -> Self {
326        unimplemented!()
327    }
328}
329
330*/
numeric_domains/tnum.rs

numeric_domains/
tnum.rs
