fixed_bigint/fixeduint/
prim_int_impl.rs

1use super::{
2    FixedUInt, MachineWord, const_leading_zeros, const_leading_zeros_ct, const_trailing_zeros,
3    const_trailing_zeros_ct,
4};
5use crate::machineword::ConstMachineWord;
6use const_num_traits::PrimBits;
7use const_num_traits::{Bounded, Nct, Personality, PersonalityTag};
8
9c0nst::c0nst! {
10    c0nst impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality> PrimBits for FixedUInt<T, N, P> {
11        // count_ones / count_zeros: no `match P::TAG` — the fixed
12        // N-limb loop + primitive `T::count_ones()` is uniform under
13        // both personalities. On a target where `T::count_ones()`
14        // itself is not constant-time (e.g. SWAR fallback without
15        // POPCNT), that CT weakness is inherited by both variants.
16        fn count_ones(self) -> u32 {
17            let mut count = 0u32;
18            let mut i = 0;
19            while i < N {
20                count += self.array[i].count_ones();
21                i += 1;
22            }
23            count
24        }
25        fn count_zeros(self) -> u32 {
26            let mut count = 0u32;
27            let mut i = 0;
28            while i < N {
29                count += self.array[i].count_zeros();
30                i += 1;
31            }
32            count
33        }
34        fn leading_zeros(self) -> u32 {
35            match P::TAG {
36                PersonalityTag::Nct => const_leading_zeros(&self.array),
37                PersonalityTag::Ct => const_leading_zeros_ct(&self.array),
38            }
39        }
40        fn trailing_zeros(self) -> u32 {
41            match P::TAG {
42                PersonalityTag::Nct => const_trailing_zeros(&self.array),
43                PersonalityTag::Ct => const_trailing_zeros_ct(&self.array),
44            }
45        }
46        fn swap_bytes(self) -> Self {
47            let mut ret = <Self as const_num_traits::ConstZero>::ZERO;
48            let mut i = 0;
49            while i < N {
50                ret.array[i] = self.array[N - 1 - i].swap_bytes();
51                i += 1;
52            }
53            ret
54        }
55        fn rotate_left(self, n: u32) -> Self {
56            let bit_size = Self::BIT_SIZE as u32;
57            if bit_size == 0 {
58                return self;
59            }
60            let shift = n % bit_size;
61            let a = core::ops::Shl::<u32>::shl(self, shift);
62            let b = core::ops::Shr::<u32>::shr(self, bit_size - shift);
63            core::ops::BitOr::bitor(a, b)
64        }
65        fn rotate_right(self, n: u32) -> Self {
66            let bit_size = Self::BIT_SIZE as u32;
67            if bit_size == 0 {
68                return self;
69            }
70            let shift = n % bit_size;
71            let a = core::ops::Shr::<u32>::shr(self, shift);
72            let b = core::ops::Shl::<u32>::shl(self, bit_size - shift);
73            core::ops::BitOr::bitor(a, b)
74        }
75        fn unsigned_shl(self, n: u32) -> Self {
76            core::ops::Shl::<u32>::shl(self, n)
77        }
78        fn unsigned_shr(self, n: u32) -> Self {
79            core::ops::Shr::<u32>::shr(self, n)
80        }
81        fn signed_shl(self, n: u32) -> Self {
82            // FixedUInt is always unsigned, so signed_shl is equivalent
83            // to unsigned_shl (the sign bit doesn't change shift-left
84            // semantics for unsigned types).
85            core::ops::Shl::<u32>::shl(self, n)
86        }
87        fn signed_shr(self, n: u32) -> Self {
88            // Arithmetic (sign-extending) right shift: the vacated top bits
89            // take the carrier's MSB, per the `PrimBits`/`PrimInt` contract
90            // (`(self as signed) >> n`). Branchless on the value — the sign
91            // bit is spread to a full-width mask via `bit * MAX` (the CT
92            // barrel's trick), so a `Ct` carrier never branches on the value;
93            // both shifts route through the `Shr` operator, which barrels a
94            // secret amount on `Ct`. The fill `sign_full ^ (sign_full >> n)`
95            // is the top-`n` sign bits when the MSB is set and zero otherwise,
96            // so a non-negative value shifts identically to `unsigned_shr`.
97            let logical = core::ops::Shr::<u32>::shr(self, n);
98            if N == 0 {
99                return logical;
100            }
101            let word_bits = FixedUInt::<T, N>::WORD_BITS;
102            let sign_bit = self.array[N - 1] >> (word_bits - 1);
103            let mask_word =
104                <T as core::ops::Mul>::mul(sign_bit, <T as Bounded>::max_value());
105            let mut sign_full = self;
106            let mut i = 0;
107            while i < N {
108                sign_full.array[i] = mask_word;
109                i += 1;
110            }
111            let sf_shr = core::ops::Shr::<u32>::shr(sign_full, n);
112            let mut result = logical;
113            let mut i = 0;
114            while i < N {
115                let fill = <T as core::ops::BitXor>::bitxor(mask_word, sf_shr.array[i]);
116                result.array[i] = <T as core::ops::BitOr>::bitor(logical.array[i], fill);
117                i += 1;
118            }
119            result
120        }
121        fn reverse_bits(self) -> Self {
122            let mut ret = <Self as const_num_traits::ConstZero>::ZERO;
123            let mut i = 0;
124            while i < N {
125                ret.array[N - 1 - i] = self.array[i].reverse_bits();
126                i += 1;
127            }
128            ret
129        }
130        // TODO: Add big-endian support via #[cfg(target_endian = "big")]
131        fn from_be(x: Self) -> Self {
132            x.swap_bytes()
133        }
134        fn from_le(x: Self) -> Self {
135            x
136        }
137        fn to_be(self) -> Self {
138            self.swap_bytes()
139        }
140        fn to_le(self) -> Self {
141            self
142        }
143    }
144}
145
146c0nst::c0nst! {
147    /// Const-callable `pow` body. Free-floating because the c0nst macro
148    /// only accepts `[c0nst]` bounds on trait-impl headers and
149    /// standalone `const fn` items, not on inherent `impl` blocks.
150    pub(crate) c0nst fn pow_impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize>(
151        v: FixedUInt<T, N, Nct>, exp: u32,
152    ) -> FixedUInt<T, N, Nct> {
153        if exp == 0 {
154            return <FixedUInt<T, N, Nct> as const_num_traits::ConstOne>::ONE;
155        }
156        let mut result = <FixedUInt<T, N, Nct> as const_num_traits::ConstOne>::ONE;
157        let mut base = v;
158        let mut e = exp;
159        while e > 0 {
160            if (e & 1) == 1 {
161                result = core::ops::Mul::mul(result, base);
162            }
163            e >>= 1;
164            if e > 0 {
165                base = core::ops::Mul::mul(base, base);
166            }
167        }
168        result
169    }
170}
171
172impl<T: ConstMachineWord + MachineWord, const N: usize> FixedUInt<T, N, Nct> {
173    /// Inherent `pow`. `FixedUInt` does not implement external
174    /// `const_num_traits::PrimInt` (which supertrait-bundles `Num`,
175    /// `NumCast`, `Saturating`, and others), so this stays on the type
176    /// itself. For const-callable use on nightly, call the free
177    /// `pow_impl` function above directly.
178    pub fn pow(self, exp: u32) -> Self {
179        pow_impl(self, exp)
180    }
181}
182
183#[cfg(feature = "num-traits")]
184impl<T: MachineWord, const N: usize> num_traits::PrimInt for FixedUInt<T, N, Nct> {
185    fn count_ones(self) -> u32 {
186        self.array.iter().map(|&val| val.count_ones()).sum()
187    }
188    fn count_zeros(self) -> u32 {
189        self.array.iter().map(|&val| val.count_zeros()).sum()
190    }
191    fn leading_zeros(self) -> u32 {
192        const_leading_zeros(&self.array)
193    }
194    fn trailing_zeros(self) -> u32 {
195        const_trailing_zeros(&self.array)
196    }
197    fn rotate_left(self, bits: u32) -> Self {
198        let bit_size = Self::BIT_SIZE as u32;
199        if bit_size == 0 {
200            return self;
201        }
202        let shift = bits % bit_size;
203        let a = self << shift;
204        let b = self >> (bit_size - shift);
205        a | b
206    }
207    fn rotate_right(self, bits: u32) -> Self {
208        let bit_size = Self::BIT_SIZE as u32;
209        if bit_size == 0 {
210            return self;
211        }
212        let shift = bits % bit_size;
213        let a = self >> shift;
214        let b = self << (bit_size - shift);
215        a | b
216    }
217    fn signed_shl(self, bits: u32) -> Self {
218        <Self as num_traits::PrimInt>::unsigned_shl(self, bits)
219    }
220    fn signed_shr(self, bits: u32) -> Self {
221        // Sign-extending shift, delegated to the single `PrimBits` body so both
222        // the num-traits and const-num-traits surfaces agree.
223        <Self as PrimBits>::signed_shr(self, bits)
224    }
225    fn unsigned_shl(self, bits: u32) -> Self {
226        self << bits
227    }
228    fn unsigned_shr(self, bits: u32) -> Self {
229        self >> bits
230    }
231    fn swap_bytes(self) -> Self {
232        let mut ret = Self::new();
233        for index in 0..N {
234            ret.array[index] = self.array[N - 1 - index].swap_bytes();
235        }
236
237        ret
238    }
239    // TODO: Add big-endian support via #[cfg(target_endian = "big")]
240    fn from_be(source: Self) -> Self {
241        <Self as num_traits::PrimInt>::swap_bytes(source)
242    }
243    fn from_le(source: Self) -> Self {
244        source
245    }
246    fn to_be(self) -> Self {
247        <Self as num_traits::PrimInt>::swap_bytes(self)
248    }
249    fn to_le(self) -> Self {
250        self
251    }
252    fn pow(self, exp: u32) -> Self {
253        pow_impl(self, exp)
254    }
255}
256
257#[cfg(test)]
258mod tests {
259    use super::*;
260    use const_num_traits::PrimBits;
261
262    type U16 = FixedUInt<u8, 2, Nct>;
263
264    // --- Empirical const-evaluability proofs for `PrimBits` ----------------
265    //
266    // Wraps each by-value `PrimBits` method in a `c0nst fn` so the
267    // surrounding `c0nst::c0nst!` block forces it into const-callable
268    // form on nightly. The `nightly_const_eval_prim_bits` test then binds
269    // each wrapper's result to a `const` item, proving the trait method
270    // actually evaluates at compile time.
271
272    c0nst::c0nst! {
273        pub c0nst fn const_count_ones<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> u32 {
274            PrimBits::count_ones(v)
275        }
276        pub c0nst fn const_count_zeros<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> u32 {
277            PrimBits::count_zeros(v)
278        }
279        pub c0nst fn const_leading_zeros<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> u32 {
280            PrimBits::leading_zeros(v)
281        }
282        pub c0nst fn const_trailing_zeros<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> u32 {
283            PrimBits::trailing_zeros(v)
284        }
285        pub c0nst fn const_swap_bytes<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> FixedUInt<T, N, P> {
286            PrimBits::swap_bytes(v)
287        }
288        pub c0nst fn const_rotate_left<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>, n: u32) -> FixedUInt<T, N, P> {
289            PrimBits::rotate_left(v, n)
290        }
291        pub c0nst fn const_rotate_right<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>, n: u32) -> FixedUInt<T, N, P> {
292            PrimBits::rotate_right(v, n)
293        }
294        pub c0nst fn const_unsigned_shl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>, n: u32) -> FixedUInt<T, N, P> {
295            PrimBits::unsigned_shl(v, n)
296        }
297        pub c0nst fn const_unsigned_shr<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>, n: u32) -> FixedUInt<T, N, P> {
298            PrimBits::unsigned_shr(v, n)
299        }
300        pub c0nst fn const_signed_shl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>, n: u32) -> FixedUInt<T, N, P> {
301            PrimBits::signed_shl(v, n)
302        }
303        pub c0nst fn const_signed_shr<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>, n: u32) -> FixedUInt<T, N, P> {
304            PrimBits::signed_shr(v, n)
305        }
306        pub c0nst fn const_reverse_bits<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> FixedUInt<T, N, P> {
307            PrimBits::reverse_bits(v)
308        }
309        pub c0nst fn const_to_be<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> FixedUInt<T, N, P> {
310            PrimBits::to_be(v)
311        }
312        pub c0nst fn const_to_le<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> FixedUInt<T, N, P> {
313            PrimBits::to_le(v)
314        }
315        pub c0nst fn const_from_be<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> FixedUInt<T, N, P> {
316            PrimBits::from_be(v)
317        }
318        pub c0nst fn const_from_le<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> FixedUInt<T, N, P> {
319            PrimBits::from_le(v)
320        }
321    }
322
323    #[test]
324    fn nightly_const_eval_prim_bits() {
325        // runtime smoke
326        let v = U16::from(0b0010_1000u8);
327        assert_eq!(const_count_ones(v), 2);
328        assert_eq!(const_leading_zeros(v), 10);
329        assert_eq!(const_trailing_zeros(v), 3);
330
331        #[cfg(feature = "nightly")]
332        {
333            const V: U16 = FixedUInt::from_array([0x28, 0]);
334            const V_FULL: U16 = FixedUInt::from_array([0xFF, 0xFF]);
335            const V_ONE: U16 = FixedUInt::from_array([1, 0]);
336
337            const C_ONES: u32 = const_count_ones(V);
338            const C_ZEROS: u32 = const_count_zeros(V);
339            const LZ: u32 = const_leading_zeros(V);
340            const TZ: u32 = const_trailing_zeros(V);
341            const SWAP: U16 = const_swap_bytes(V_ONE);
342            const ROTL: U16 = const_rotate_left(V_ONE, 4);
343            const ROTR: U16 = const_rotate_right(V_ONE, 4);
344            const USHL: U16 = const_unsigned_shl(V_ONE, 4);
345            const USHR: U16 = const_unsigned_shr(V_FULL, 4);
346            const SSHL: U16 = const_signed_shl(V_ONE, 4);
347            const SSHR: U16 = const_signed_shr(V_FULL, 4);
348            const REV: U16 = const_reverse_bits(V_ONE);
349            const TO_BE: U16 = const_to_be(V_ONE);
350            const TO_LE: U16 = const_to_le(V_ONE);
351            const FROM_BE: U16 = const_from_be(V_ONE);
352            const FROM_LE: U16 = const_from_le(V_ONE);
353
354            assert_eq!(C_ONES, 2);
355            assert_eq!(C_ZEROS, 14);
356            assert_eq!(LZ, 10);
357            assert_eq!(TZ, 3);
358            assert_eq!(SWAP.array, [0, 1]);
359            assert_eq!(ROTL.array, [16, 0]);
360            assert_eq!(ROTR.array, [0, 0x10]);
361            assert_eq!(USHL.array, [16, 0]);
362            assert_eq!(USHR.array, [0xFF, 0x0F]);
363            assert_eq!(SSHL.array, [16, 0]);
364            // V_FULL (0xFFFF) has its MSB set, so the arithmetic shift fills
365            // ones: -1 >> 4 == -1 == 0xFFFF (vs the logical 0x0FFF above).
366            assert_eq!(SSHR.array, [0xFF, 0xFF]);
367            assert_eq!(REV.array, [0, 0x80]);
368            assert_eq!(TO_BE.array, [0, 1]);
369            assert_eq!(TO_LE.array, [1, 0]);
370            assert_eq!(FROM_BE.array, [0, 1]);
371            assert_eq!(FROM_LE.array, [1, 0]);
372        }
373    }
374
375    // --- Empirical const-eval proof for the standalone `pow_impl` ----------
376
377    #[test]
378    fn nightly_const_eval_pow() {
379        // runtime smoke (works on stable + nightly)
380        let v = U16::from(2u8);
381        assert_eq!(super::pow_impl(v, 8), U16::from(256u16));
382        assert_eq!(super::pow_impl(v, 0), U16::from(1u8));
383
384        #[cfg(feature = "nightly")]
385        {
386            const TWO: U16 = FixedUInt::from_array([2, 0]);
387            const THREE: U16 = FixedUInt::from_array([3, 0]);
388            const TWO_TO_THE_EIGHT: U16 = super::pow_impl(TWO, 8);
389            const THREE_TO_THE_FIVE: U16 = super::pow_impl(THREE, 5);
390            const ZERO_EXP: U16 = super::pow_impl(TWO, 0);
391            assert_eq!(TWO_TO_THE_EIGHT, FixedUInt::from_array([0, 1])); // 256
392            assert_eq!(THREE_TO_THE_FIVE, FixedUInt::from_array([243, 0]));
393            assert_eq!(ZERO_EXP, FixedUInt::from_array([1, 0]));
394        }
395    }
396}
fixed_bigint/fixeduint/prim_int_impl.rs

fixed_bigint/fixeduint/
prim_int_impl.rs
