nanvm_lib/common/
bit_subset64.rs

1use core::marker::PhantomData;
2
3use super::cast::Cast;
4
5/// A bit subset of `u64`.
6///
7/// This structure represents a subset of bits within a 64-bit unsigned integer,
8/// defined by a specific pattern where each bit is either `0`, `1`, or `S`.
9///
10/// - `0` means the bit is always `0`. These bits contribute to both the tag and the mask.
11/// - `1` means the bit is always `1`. These bits also contribute to both the tag and the mask.
12/// - `S` represents a superposition state, meaning the bit can be either `0` or `1`.
13///
14/// The cardinality of the set is calculated as `2^(superposition.count_ones())`, representing
15/// the number of unique combinations possible within the superposition bits.
16///
17/// The following table summarizes how each field is derived:
18///
19/// |Property      | 0 | 1 | S | Description        |
20/// |--------------|---|---|---|--------------------|
21/// | union        | 0 | 1 | 1 | items.reduce(or)   |
22/// | tag          | 0 | 1 | 0 | items.reduce(and)  |
23/// | superposition| 0 | 0 | 1 | union ^ tag        |
24/// | mask         | 1 | 1 | 0 | !superposition     |
25pub struct BitSubset64<T: Cast<u64> = u64>
26where
27    u64: Cast<T>,
28{
29    /// Represents the intersection of all items in the subset. A pattern of bits
30    /// where a `1` in each position indicates that the corresponding bit is consistently `1`
31    /// across all items, and a `0` indicates that it is not consistently `1`.
32    pub tag: u64,
33    /// Identifies the bits that are constant (either `0` or `1`). A `1` in a position
34    /// indicates a fixed bit (as per the `tag`), and a `0` indicates a superposition bit.
35    pub mask: u64,
36    _0: PhantomData<T>,
37}
38
39impl<T: Cast<u64>> Clone for BitSubset64<T>
40where
41    u64: Cast<T>,
42{
43    #[inline(always)]
44    fn clone(&self) -> Self {
45        *self
46    }
47}
48
49impl<T: Cast<u64>> Copy for BitSubset64<T> where u64: Cast<T> {}
50
51impl BitSubset64<u64> {
52    #[inline(always)]
53    pub const fn cast<U: Cast<u64>>(self) -> BitSubset64<U>
54    where
55        u64: Cast<U>,
56    {
57        BitSubset64 {
58            tag: self.tag,
59            mask: self.mask,
60            _0: PhantomData,
61        }
62    }
63}
64
65impl<T: Cast<u64>> BitSubset64<T>
66where
67    u64: Cast<T>,
68{
69    #[inline(always)]
70    pub const fn from_tag_and_mask(tag: u64, mask: u64) -> Self {
71        assert!(mask & tag == tag);
72        Self {
73            tag,
74            mask,
75            _0: PhantomData,
76        }
77    }
78    #[inline(always)]
79    pub const fn from_tag_and_superposition(tag: u64, sup: u64) -> Self {
80        Self::from_tag_and_mask(tag, !sup)
81    }
82    #[inline(always)]
83    pub const fn from_tag_and_union(tag: u64, union: u64) -> Self {
84        Self::from_tag_and_superposition(tag, tag ^ union)
85    }
86    #[inline(always)]
87    pub const fn from_tag(tag: u64) -> Self {
88        Self::from_tag_and_mask(tag, tag)
89    }
90    #[inline(always)]
91    pub const fn has(self, value: u64) -> bool {
92        value & self.mask == self.tag
93    }
94    #[inline(always)]
95    pub const fn union(self) -> u64 {
96        self.tag ^ self.superposition()
97    }
98    #[inline(always)]
99    pub const fn superposition(self) -> u64 {
100        !self.mask
101    }
102    #[inline(always)]
103    pub const fn or_unchecked(self, b: Self) -> Self {
104        Self::from_tag_and_union(self.tag & b.tag, self.union() | b.union())
105    }
106    #[inline(always)]
107    pub const fn or(self, b: Self) -> Self {
108        assert!(self.superposition() == b.superposition());
109        self.or_unchecked(b)
110    }
111    #[inline(always)]
112    pub const fn and(self, b: Self) -> Self {
113        Self::from_tag_and_union(self.tag | b.tag, self.union() & b.union())
114    }
115    #[inline(always)]
116    pub const fn split(self, sub_mask: u64) -> (Self, Self) {
117        // we need at least one bit to distinguish the two subsets.
118        assert!(sub_mask != 0);
119        // the bit shouldn't be a part of the original set mask.
120        assert!(sub_mask & self.mask == 0);
121        let mask = self.mask | sub_mask;
122        // the subsets should have different tags.
123        (
124            Self::from_tag_and_mask(self.tag, mask),
125            Self::from_tag_and_mask(self.tag | sub_mask, mask),
126        )
127    }
128    #[inline(always)]
129    const fn subset_value_to_raw_value(self, set: u64) -> u64 {
130        self.superposition() & set
131    }
132    #[inline(always)]
133    pub const fn raw_value_to_subset_value(self, value: u64) -> u64 {
134        self.tag | value
135    }
136    #[inline(always)]
137    pub fn typed_value_to_subset_value(self, value: T) -> u64 {
138        self.raw_value_to_subset_value(value.cast())
139    }
140    #[inline(always)]
141    pub fn subset_value_to_typed_value(self, set: u64) -> T {
142        (self.subset_value_to_raw_value(set)).cast()
143    }
144}
145
146#[cfg(test)]
147mod test {
148    use wasm_bindgen_test::wasm_bindgen_test;
149
150    use super::BitSubset64;
151
152    const A: BitSubset64 = BitSubset64::from_tag_and_union(0b010, 0b011);
153    const _: () = assert!(A.superposition() == 0b001);
154    const _: () = assert!(A.tag == 0b010);
155    const _: () = assert!(!A.has(0b000));
156    const _: () = assert!(A.has(0b010));
157    const _: () = assert!(A.has(0b011));
158
159    const _AS: (BitSubset64, BitSubset64) = A.split(1);
160    const _: () = assert!(_AS.0.tag == 0b010);
161    const _: () = assert!(_AS.0.superposition() == 0);
162    const _: () = assert!(_AS.1.tag == 0b011);
163    const _: () = assert!(_AS.1.superposition() == 0);
164
165    #[test]
166    #[wasm_bindgen_test]
167    fn test_a() {
168        assert_eq!(A.superposition(), 0b001);
169        assert_eq!(A.tag, 0b010);
170        assert!(!A.has(0b000));
171        assert!(A.has(0b010));
172        assert!(A.has(0b011));
173    }
174
175    const B: BitSubset64 = BitSubset64::from_tag_and_union(0b000110, 0b000111);
176    const C: BitSubset64 = BitSubset64::from_tag_and_union(0b010100, 0b011111);
177    const UBC: BitSubset64 = B.or_unchecked(C);
178    const _: () = assert!(UBC.superposition() == 0b011011);
179    const _: () = assert!(UBC.tag == 0b000100);
180    const _: () = assert!(UBC.union() == 0b011111);
181
182    const _UBCS: (BitSubset64, BitSubset64) = UBC.split(0b1000);
183    const _: () = assert!(_UBCS.0.superposition() == 0b010011);
184    const _: () = assert!(_UBCS.0.tag == 0b000100);
185    const _: () = assert!(_UBCS.1.tag == 0b001100);
186
187    #[test]
188    #[wasm_bindgen_test]
189    fn test_ubc() {
190        assert_eq!(UBC.superposition(), 0b011011);
191        assert_eq!(UBC.tag, 0b000100);
192        assert_eq!(UBC.union(), 0b011111);
193    }
194
195    #[test]
196    #[wasm_bindgen_test]
197    #[should_panic]
198    fn test_ibc() {
199        B.and(C);
200    }
201
202    #[test]
203    #[wasm_bindgen_test]
204    #[should_panic]
205    fn test_split_fail() {
206        UBC.split(0b100);
207    }
208
209    const D: BitSubset64 = BitSubset64::from_tag_and_union(0b00110, 0b00111);
210    const E: BitSubset64 = BitSubset64::from_tag_and_union(0b00100, 0b01111);
211    const UDE: BitSubset64 = D.or_unchecked(E);
212    const _: () = assert!(UDE.superposition() == 0b01011);
213    const _: () = assert!(UDE.tag == 0b00100);
214    const _: () = assert!(UDE.union() == 0b01111);
215    const IDE: BitSubset64 = D.and(E);
216    const _: () = assert!(IDE.superposition() == 0b00001);
217    const _: () = assert!(IDE.tag == 0b00110);
218    const _: () = assert!(IDE.union() == 0b00111);
219
220    #[test]
221    #[wasm_bindgen_test]
222    fn test_ude() {
223        assert_eq!(UDE.superposition(), 0b01011);
224        assert_eq!(UDE.tag, 0b00100);
225        assert_eq!(UDE.union(), 0b01111);
226    }
227
228    #[test]
229    #[wasm_bindgen_test]
230    fn test_ide() {
231        assert_eq!(IDE.superposition(), 0b00001);
232        assert_eq!(IDE.tag, 0b00110);
233        assert_eq!(IDE.union(), 0b00111);
234    }
235}
nanvm_lib/common/bit_subset64.rs

nanvm_lib/common/
bit_subset64.rs
