numeric_domains/
znum.rs

1use core::ops::{Add, BitAnd, BitOr, BitXor, Div, Mul, Neg, Not, Rem, Shl, Shr, Sub};
2
3/// Tracks which bits "may be 1s" (o) and "may be 0s" (z)
4///
5/// Compared to other bit domains, the Z domain requires minimal storage, which is not scaled with
6/// the number of operations, but as a result the accuracy of the domain is somewhat limited.
7///
8///  - ["Abstract Domains for Bit-Level Machine Integer and Floating-point Operations"](https://www-apr.lip6.fr/~mine/publi/article-mine-wing12.pdf)
9///  - Published proceedings entry and DOI: <https://doi.org/10.29007/b63g>
10#[derive(Debug, Eq, PartialEq, Clone, Copy)]
11pub struct Znum {
12    z: u64,
13    o: u64,
14}
15
16impl Znum {
17    pub const fn from_parts(ones: u64, zeros: u64) -> Self {
18        if ones | zeros == u64::MAX {
19            Znum { o: ones, z: zeros }
20        } else {
21            Self::empty()
22        }
23    }
24
25    const fn empty() -> Self {
26        Self { z: 0, o: 0 }
27    }
28
29    const fn is_empty(&self) -> bool {
30        self.o | self.z == 0
31    }
32
33    const fn validity_mask(&self) -> u64 {
34        self.o | self.z
35    }
36
37    const fn unknown() -> Self {
38        Self {
39            z: u64::MAX,
40            o: u64::MAX,
41        }
42    }
43
44    /// From a value, generate a Znum
45    ///
46    /// The resulting Znum only contains the provided value `v`, and no other values. It is
47    /// considered a "constant"
48    pub const fn from_value(v: u64) -> Self {
49        Znum { o: v, z: !v }
50    }
51
52    /// Is there only a single contained value?
53    pub const fn is_const(&self) -> bool {
54        // all const bits (differing)
55        let a = self.z ^ self.o;
56        // ensure all are set
57        !a == 0
58    }
59
60    /// If this is a constant (only a single contained value), return that value. Otherwise, return
61    /// None.
62    pub const fn value(&self) -> Option<u64> {
63        if self.is_const() {
64            Some(self.o)
65        } else {
66            None
67        }
68    }
69
70    /// Is any value contained in this?
71    ///
72    /// In other words, are there _no_ undefined bits?
73    pub const fn is_defined(&self) -> bool {
74        !self.is_empty()
75    }
76
77    /// Is a specific value contained in this?
78    pub const fn contains_value(&self, v: u64) -> bool {
79        // bits provided by `ones`
80        let po = self.o & v;
81        // bits provided by `zeros`
82        let pz = self.z & !v;
83        // ensure all bits are provided
84        !(po | pz) == 0
85    }
86
87    /// Return the least Z-domain containing every value in either operand.
88    pub const fn union(&self, other: Self) -> Self {
89        if self.is_empty() {
90            return other;
91        }
92        if other.is_empty() {
93            return *self;
94        }
95        Znum {
96            o: self.o | other.o,
97            z: self.z | other.z,
98        }
99    }
100
101    /// `self` includes all possible elements in `other`
102    pub const fn contains(&self, other: Self) -> bool {
103        other.is_empty() || (!self.is_empty() && other.o & !self.o == 0 && other.z & !self.z == 0)
104    }
105
106    /// Return the values represented by both operands.
107    pub const fn intersection(&self, other: Self) -> Self {
108        Self::from_parts(self.o & other.o, self.z & other.z)
109    }
110
111    pub const fn has_value(&self) -> bool {
112        !self.is_empty()
113    }
114
115    pub const fn max_value(&self) -> Option<u64> {
116        if self.has_value() {
117            Some(self.o)
118        } else {
119            None
120        }
121    }
122
123    pub const fn min_value(&self) -> Option<u64> {
124        if self.has_value() {
125            Some(self.o & !(self.z))
126        } else {
127            None
128        }
129    }
130
131    pub const fn unsigned_bounds(&self) -> Option<(u64, u64)> {
132        if self.is_empty() {
133            None
134        } else {
135            Some((self.o & !self.z, self.o))
136        }
137    }
138
139    pub const fn signed_bounds(&self) -> Option<(i64, i64)> {
140        const SIGN: u64 = 1 << 63;
141        if !self.has_value() {
142            return None;
143        }
144        match (self.z & SIGN != 0, self.o & SIGN != 0) {
145            (true, true) => Some((((self.o & !self.z) | SIGN) as i64, (self.o & !SIGN) as i64)),
146            (true, false) => Some(((self.o & !self.z) as i64, self.o as i64)),
147            (false, true) => Some(((self.o & !self.z) as i64, self.o as i64)),
148            (false, false) => None,
149        }
150    }
151
152    pub const fn bit_or(self, other: Self) -> Self {
153        let valid = self.validity_mask() & other.validity_mask();
154        Self {
155            z: (self.z & other.z) & valid,
156            o: (self.o | other.o) & valid,
157        }
158    }
159
160    pub const fn bit_and(self, other: Self) -> Self {
161        let valid = self.validity_mask() & other.validity_mask();
162        Self {
163            z: (self.z | other.z) & valid,
164            o: (self.o & other.o) & valid,
165        }
166    }
167
168    pub const fn bit_xor(self, other: Self) -> Self {
169        let valid = self.validity_mask() & other.validity_mask();
170        Self {
171            z: ((self.z & other.z) | (self.o & other.o)) & valid,
172            o: ((self.z & other.o) | (self.o & other.z)) & valid,
173        }
174    }
175
176    pub const fn bit_not(self) -> Self {
177        Self {
178            z: self.o,
179            o: self.z,
180        }
181    }
182
183    pub const fn add(self, other: Self) -> Self {
184        if self.is_empty() || other.is_empty() {
185            return Self::empty();
186        }
187        let left_value = self.o & !self.z;
188        let left_mask = self.o & self.z;
189        let right_value = other.o & !other.z;
190        let right_mask = other.o & other.z;
191        let mask_sum = left_mask.wrapping_add(right_mask);
192        let value_sum = left_value.wrapping_add(right_value);
193        let sigma = mask_sum.wrapping_add(value_sum);
194        let carry_changes = sigma ^ value_sum;
195        let mask = carry_changes | left_mask | right_mask;
196        let value = value_sum & !mask;
197        Self {
198            o: value | mask,
199            z: !value | mask,
200        }
201    }
202
203    pub const fn subtract(self, other: Self) -> Self {
204        if self.is_empty() || other.is_empty() {
205            return Self::empty();
206        }
207        let left_value = self.o & !self.z;
208        let left_mask = self.o & self.z;
209        let right_value = other.o & !other.z;
210        let right_mask = other.o & other.z;
211        let value_difference = left_value.wrapping_sub(right_value);
212        let alpha = value_difference.wrapping_add(left_mask);
213        let beta = value_difference.wrapping_sub(right_mask);
214        let borrow_changes = alpha ^ beta;
215        let mask = borrow_changes | left_mask | right_mask;
216        let value = value_difference & !mask;
217        Self {
218            o: value | mask,
219            z: !value | mask,
220        }
221    }
222
223    pub const fn shift_left(self, shift: u8) -> Self {
224        if self.is_empty() {
225            return Self::empty();
226        }
227        let shift = (shift as u32) % 64;
228        Self {
229            z: self.z.wrapping_shl(shift) | (1_u64.wrapping_shl(shift) - 1),
230            o: self.o.wrapping_shl(shift),
231        }
232    }
233
234    pub const fn shift_right(self, shift: u8) -> Self {
235        if self.is_empty() {
236            return Self::empty();
237        }
238        let shift = (shift as u32) % 64;
239        let new_zeros = if shift == 0 {
240            0
241        } else {
242            u64::MAX.wrapping_shl(64 - shift)
243        };
244        Self {
245            z: self.z.wrapping_shr(shift) | new_zeros,
246            o: self.o.wrapping_shr(shift),
247        }
248    }
249
250    pub const fn negate(self) -> Self {
251        Self::from_value(0).subtract(self)
252    }
253
254    pub const fn multiply(self, other: Self) -> Self {
255        if self.is_empty() || other.is_empty() {
256            return Self::empty();
257        }
258        let mut product = Self::from_value(0);
259        let mut bit = 0_u8;
260        while bit < 64 {
261            let mask = 1_u64 << bit;
262            if self.o & mask != 0 {
263                let with_bit = product.add(other.shift_left(bit));
264                product = if self.z & mask != 0 {
265                    product.union(with_bit)
266                } else {
267                    with_bit
268                };
269            }
270            bit += 1;
271        }
272        product
273    }
274
275    /// Divide by `other`, returning `None` when it can only be zero.
276    ///
277    /// If `other` contains both zero and nonzero values, the result describes
278    /// the divisions by its nonzero values.
279    pub const fn checked_div(self, other: Self) -> Option<Self> {
280        if let Some(0) = other.max_value() {
281            return None;
282        }
283
284        if self.is_empty() || other.is_empty() {
285            return Some(Self::empty());
286        }
287
288        match (self.value(), other.value()) {
289            (Some(_), Some(0)) => None,
290            (Some(dividend), Some(divisor)) => Some(Self::from_value(dividend / divisor)),
291            _ => Some(Self::unknown()),
292        }
293    }
294
295    pub const fn divide(self, other: Self) -> Self {
296        match self.checked_div(other) {
297            Some(result) => result,
298            None => Self::empty(),
299        }
300    }
301
302    pub const fn remainder(self, other: Self) -> Self {
303        if self.is_empty() || other.is_empty() {
304            return Self::empty();
305        }
306        match (self.value(), other.value()) {
307            (_, Some(0)) => Self::empty(),
308            (Some(dividend), Some(divisor)) => Self::from_value(dividend % divisor),
309            _ => Self::unknown(),
310        }
311    }
312
313    /*
314    /// All elements in `other` are also elements in `self`
315    pub fn is_subset(&self, other: Self) -> bool {
316        todo!()
317    }
318    */
319
320    /*
321    pub fn from_range(low: u64, high: u64) -> Self {
322        todo!()
323    }
324    */
325}
326
327impl Default for Znum {
328    /// Default is a completely unknown value.
329    fn default() -> Self {
330        Self::unknown()
331    }
332}
333
334impl BitOr for Znum {
335    type Output = Znum;
336    fn bitor(self, other: Self) -> Self {
337        Self::bit_or(self, other)
338    }
339}
340
341impl BitAnd for Znum {
342    type Output = Znum;
343    fn bitand(self, other: Self) -> Self {
344        Self::bit_and(self, other)
345    }
346}
347
348impl BitXor for Znum {
349    type Output = Znum;
350    fn bitxor(self, other: Self) -> Self {
351        Self::bit_xor(self, other)
352    }
353}
354
355impl Not for Znum {
356    type Output = Znum;
357    fn not(self) -> Self {
358        self.bit_not()
359    }
360}
361
362impl Add for Znum {
363    type Output = Znum;
364
365    fn add(self, other: Self) -> Self {
366        Self::add(self, other)
367    }
368}
369
370impl Sub for Znum {
371    type Output = Znum;
372
373    fn sub(self, other: Self) -> Self {
374        self.subtract(other)
375    }
376}
377
378impl Shl<u8> for Znum {
379    type Output = Znum;
380    fn shl(self, shift: u8) -> Self {
381        self.shift_left(shift)
382    }
383}
384
385impl Shr<u8> for Znum {
386    type Output = Znum;
387    fn shr(self, shift: u8) -> Self {
388        self.shift_right(shift)
389    }
390}
391
392/*
393impl Add for Znum {
394    type Output = Znum;
395    fn add(self, other: Self) -> Self {
396        /*
397         * 1 bit addition truth table:
398         *
399         * o1z1o2z2O Z
400         * 0 0 0 0 0 0
401         * 0 0 0 1 0 0
402         * 0 0 1 0 0 0
403         * 0 0 1 1 0 0
404         * 0 1 0 0 0 0
405         * 0 1 0 1 0 1
406         * 0 1 1 0 1 0
407         * 0 1 1 1 1 1
408         * 1 0 0 0 0 0
409         * 1 0 0 1 1 0
410         * 1 0 1 0 0 1
411         * 1 0 1 1 1 1
412         * 1 1 0 0 0 0
413         * 1 1 0 1 1 1
414         * 1 1 1 0 1 1
415         * 1 1 1 1 1 1
416         */
417
418        /*
419         * +1:
420         *   o: self.o + 1 | ((self.o ^ self.z) & 1)
421         *   z: self.z
422         *
423         *  if self.o & 1 == 1
424         *
425         * +2:
426         *   o
427         */
428
429        /*
430        Self {
431            o: self.o + other.o,
432        }
433        */
434
435    }
436}
437*/
438
439impl Neg for Znum {
440    type Output = Znum;
441
442    fn neg(self) -> Self {
443        self.negate()
444    }
445}
446
447impl Mul for Znum {
448    type Output = Znum;
449
450    fn mul(self, other: Self) -> Self {
451        self.multiply(other)
452    }
453}
454
455impl Div for Znum {
456    type Output = Znum;
457
458    fn div(self, other: Self) -> Self {
459        self.divide(other)
460    }
461}
462
463impl Rem for Znum {
464    type Output = Znum;
465
466    fn rem(self, other: Self) -> Self {
467        self.remainder(other)
468    }
469}
numeric_domains/znum.rs

numeric_domains/
znum.rs
