fixed_bigint/heapless/
bit_deposit.rs

1//! `const_num_traits::DepositBits` / `ExtractBits` (PDEP / PEXT) for
2//! `HeaplessBigInt<_, Nct>`.
3//!
4//! Nct-only: the loop runs once per set bit of the mask, which is
5//! value-dependent. (A constant-time version would iterate the full width
6//! unconditionally — a separate Ct exercise, as on `FixedUInt`.)
7//!
8//! The result is seeded at `max(self.len, mask.len)` so it carries the
9//! operand width rather than the minimal identity width.
10
11use super::HeaplessBigInt;
12use crate::MachineWord;
13use const_num_traits::{
14    DepositBits, ExtractBits, IsolateLowestOne, Nct, One, WrappingShl, WrappingSub, Zero,
15};
16
17impl<T, const CAP: usize> DepositBits for HeaplessBigInt<T, CAP, Nct>
18where
19    T: MachineWord,
20{
21    type Output = Self;
22    fn deposit_bits(self, mask: Self) -> Self {
23        // Scatter the contiguous low bits of `self` into the one-bit
24        // positions of `mask`, lowest to highest.
25        let width = core::cmp::max(self.len(), mask.len());
26        let mut result = Self::new_zero_with_len(width);
27        // Nothing to scatter for an all-zero mask (which is the only way
28        // `width == 0`); returning early also avoids `one().widened(0)`, which
29        // rejects the grow. A non-zero mask has `len >= 1`, so `width >= 1`.
30        if <Self as Zero>::is_zero(&mask) {
31            return result;
32        }
33        let one = <Self as One>::one();
34        let mut remaining = mask;
35        let mut bb = one.widened(width);
36        while !<Self as Zero>::is_zero(&remaining) {
37            let lowest = IsolateLowestOne::isolate_lowest_one(remaining);
38            if !<Self as Zero>::is_zero(&(self & bb)) {
39                result |= lowest;
40            }
41            // Clear the lowest set bit of `remaining` (`x & (x - 1)`).
42            remaining &= WrappingSub::wrapping_sub(remaining, one);
43            bb = WrappingShl::wrapping_shl(bb, 1);
44        }
45        result
46    }
47}
48
49impl<T, const CAP: usize> ExtractBits for HeaplessBigInt<T, CAP, Nct>
50where
51    T: MachineWord,
52{
53    type Output = Self;
54    fn extract_bits(self, mask: Self) -> Self {
55        // Gather the `mask`-selected bits of `self` into the low end —
56        // mirror of `deposit_bits`.
57        let width = core::cmp::max(self.len(), mask.len());
58        let mut result = Self::new_zero_with_len(width);
59        // See `deposit_bits`: an all-zero mask (the only `width == 0` case)
60        // gathers nothing and would otherwise trip `one().widened(0)`.
61        if <Self as Zero>::is_zero(&mask) {
62            return result;
63        }
64        let one = <Self as One>::one();
65        let mut remaining = mask;
66        let mut bb = one.widened(width);
67        while !<Self as Zero>::is_zero(&remaining) {
68            let lowest = IsolateLowestOne::isolate_lowest_one(remaining);
69            if !<Self as Zero>::is_zero(&(self & lowest)) {
70                result |= bb;
71            }
72            remaining &= WrappingSub::wrapping_sub(remaining, one);
73            bb = WrappingShl::wrapping_shl(bb, 1);
74        }
75        result
76    }
77}
78
79// Reference-receiver mirrors (`&HeaplessBigInt`), so `(&h).deposit_bits(m)`
80// resolves. `HeaplessBigInt` is `Copy`; each delegates to the value impl,
81// dereferencing both `self` and the `mask` operand.
82
83impl<T, const CAP: usize> DepositBits for &HeaplessBigInt<T, CAP, Nct>
84where
85    T: MachineWord,
86{
87    type Output = HeaplessBigInt<T, CAP, Nct>;
88    fn deposit_bits(self, mask: Self) -> HeaplessBigInt<T, CAP, Nct> {
89        <HeaplessBigInt<T, CAP, Nct> as DepositBits>::deposit_bits(*self, *mask)
90    }
91}
92
93impl<T, const CAP: usize> ExtractBits for &HeaplessBigInt<T, CAP, Nct>
94where
95    T: MachineWord,
96{
97    type Output = HeaplessBigInt<T, CAP, Nct>;
98    fn extract_bits(self, mask: Self) -> HeaplessBigInt<T, CAP, Nct> {
99        <HeaplessBigInt<T, CAP, Nct> as ExtractBits>::extract_bits(*self, *mask)
100    }
101}
102
103#[cfg(test)]
104mod tests {
105    use super::HeaplessBigInt;
106    use const_num_traits::{DepositBits, ExtractBits};
107
108    type H = HeaplessBigInt<u8, 4>;
109
110    #[test]
111    fn deposit_extract_roundtrip() {
112        // mask selects bits 0,2,4,6; deposit the low nibble of 0b1011 into them.
113        let mask = H::from(0b0101_0101u8).widened(4);
114        let src = H::from(0b1011u8).widened(4);
115        let dep = DepositBits::deposit_bits(src, mask);
116        // low four mask bits get 1,1,0,1 → positions 0,2,6 set = 0b0100_0101
117        assert_eq!(dep, H::from(0b0100_0101u8));
118        assert_eq!(dep.len(), 4);
119
120        // extract is the inverse: pull those masked bits back to the low end.
121        let ext = ExtractBits::extract_bits(dep, mask);
122        assert_eq!(ext, H::from(0b1011u8));
123        assert_eq!(ext.len(), 4);
124    }
125
126    #[test]
127    fn deposit_full_mask_is_identity() {
128        let mask = H::from(0xFFFF_FFFFu32);
129        let v = H::from(0x1234_5678u32);
130        assert_eq!(DepositBits::deposit_bits(v, mask), v);
131        assert_eq!(ExtractBits::extract_bits(v, mask), v);
132    }
133
134    // An all-zero mask scatters/gathers nothing and returns zero — including
135    // the len-0 shape, which would otherwise panic on one().widened(0).
136    #[test]
137    fn zero_mask_returns_zero_without_panic() {
138        let src = H::from(0x1234_5678u32);
139        let zero_mask = H::new_zero_with_len(4);
140        assert_eq!(DepositBits::deposit_bits(src, zero_mask), H::from(0u8));
141        assert_eq!(ExtractBits::extract_bits(src, zero_mask), H::from(0u8));
142
143        // Both operands the minimal len-0 zero shape (width 0).
144        let z0 = H::new_zero_with_len(0);
145        assert_eq!(DepositBits::deposit_bits(z0, z0).len(), 0);
146        assert_eq!(ExtractBits::extract_bits(z0, z0).len(), 0);
147    }
148
149    // The `&Self` mirrors agree with the value impls.
150    #[test]
151    fn by_ref_matches_value() {
152        let mask = H::from(0b0101_0101u8).widened(4);
153        let src = H::from(0b1011u8).widened(4);
154        assert_eq!(
155            DepositBits::deposit_bits(&src, &mask),
156            DepositBits::deposit_bits(src, mask)
157        );
158        assert_eq!(
159            ExtractBits::extract_bits(&src, &mask),
160            ExtractBits::extract_bits(src, mask)
161        );
162    }
163}
fixed_bigint/heapless/bit_deposit.rs

fixed_bigint/heapless/
bit_deposit.rs
