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::{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            // For unsigned types the sign bit is always 0, so the
89            // arithmetic (sign-extending) right shift produces the
90            // same result as the logical right shift.
91            core::ops::Shr::<u32>::shr(self, n)
92        }
93        fn reverse_bits(self) -> Self {
94            let mut ret = <Self as const_num_traits::ConstZero>::ZERO;
95            let mut i = 0;
96            while i < N {
97                ret.array[N - 1 - i] = self.array[i].reverse_bits();
98                i += 1;
99            }
100            ret
101        }
102        // TODO: Add big-endian support via #[cfg(target_endian = "big")]
103        fn from_be(x: Self) -> Self {
104            x.swap_bytes()
105        }
106        fn from_le(x: Self) -> Self {
107            x
108        }
109        fn to_be(self) -> Self {
110            self.swap_bytes()
111        }
112        fn to_le(self) -> Self {
113            self
114        }
115    }
116}
117
118c0nst::c0nst! {
119    /// Const-callable `pow` body. Free-floating because the c0nst macro
120    /// only accepts `[c0nst]` bounds on trait-impl headers and
121    /// standalone `const fn` items, not on inherent `impl` blocks.
122    pub(crate) c0nst fn pow_impl<T: [c0nst] ConstMachineWord + MachineWord, const N: usize>(
123        v: FixedUInt<T, N, Nct>, exp: u32,
124    ) -> FixedUInt<T, N, Nct> {
125        if exp == 0 {
126            return <FixedUInt<T, N, Nct> as const_num_traits::ConstOne>::ONE;
127        }
128        let mut result = <FixedUInt<T, N, Nct> as const_num_traits::ConstOne>::ONE;
129        let mut base = v;
130        let mut e = exp;
131        while e > 0 {
132            if (e & 1) == 1 {
133                result = core::ops::Mul::mul(result, base);
134            }
135            e >>= 1;
136            if e > 0 {
137                base = core::ops::Mul::mul(base, base);
138            }
139        }
140        result
141    }
142}
143
144impl<T: ConstMachineWord + MachineWord, const N: usize> FixedUInt<T, N, Nct> {
145    /// Inherent `pow`. `FixedUInt` does not implement external
146    /// `const_num_traits::PrimInt` (which supertrait-bundles `Num`,
147    /// `NumCast`, `Saturating`, and others), so this stays on the type
148    /// itself. For const-callable use on nightly, call the free
149    /// `pow_impl` function above directly.
150    pub fn pow(self, exp: u32) -> Self {
151        pow_impl(self, exp)
152    }
153}
154
155#[cfg(feature = "num-traits")]
156impl<T: MachineWord, const N: usize> num_traits::PrimInt for FixedUInt<T, N, Nct> {
157    fn count_ones(self) -> u32 {
158        self.array.iter().map(|&val| val.count_ones()).sum()
159    }
160    fn count_zeros(self) -> u32 {
161        self.array.iter().map(|&val| val.count_zeros()).sum()
162    }
163    fn leading_zeros(self) -> u32 {
164        const_leading_zeros(&self.array)
165    }
166    fn trailing_zeros(self) -> u32 {
167        const_trailing_zeros(&self.array)
168    }
169    fn rotate_left(self, bits: u32) -> Self {
170        let bit_size = Self::BIT_SIZE as u32;
171        if bit_size == 0 {
172            return self;
173        }
174        let shift = bits % bit_size;
175        let a = self << shift;
176        let b = self >> (bit_size - shift);
177        a | b
178    }
179    fn rotate_right(self, bits: u32) -> Self {
180        let bit_size = Self::BIT_SIZE as u32;
181        if bit_size == 0 {
182            return self;
183        }
184        let shift = bits % bit_size;
185        let a = self >> shift;
186        let b = self << (bit_size - shift);
187        a | b
188    }
189    fn signed_shl(self, bits: u32) -> Self {
190        <Self as num_traits::PrimInt>::unsigned_shl(self, bits)
191    }
192    fn signed_shr(self, bits: u32) -> Self {
193        <Self as num_traits::PrimInt>::unsigned_shr(self, bits)
194    }
195    fn unsigned_shl(self, bits: u32) -> Self {
196        self << bits
197    }
198    fn unsigned_shr(self, bits: u32) -> Self {
199        self >> bits
200    }
201    fn swap_bytes(self) -> Self {
202        let mut ret = Self::new();
203        for index in 0..N {
204            ret.array[index] = self.array[N - 1 - index].swap_bytes();
205        }
206
207        ret
208    }
209    // TODO: Add big-endian support via #[cfg(target_endian = "big")]
210    fn from_be(source: Self) -> Self {
211        <Self as num_traits::PrimInt>::swap_bytes(source)
212    }
213    fn from_le(source: Self) -> Self {
214        source
215    }
216    fn to_be(self) -> Self {
217        <Self as num_traits::PrimInt>::swap_bytes(self)
218    }
219    fn to_le(self) -> Self {
220        self
221    }
222    fn pow(self, exp: u32) -> Self {
223        pow_impl(self, exp)
224    }
225}
226
227#[cfg(test)]
228mod tests {
229    use super::*;
230    use const_num_traits::PrimBits;
231
232    type U16 = FixedUInt<u8, 2, Nct>;
233
234    // --- Empirical const-evaluability proofs for `PrimBits` ----------------
235    //
236    // Wraps each by-value `PrimBits` method in a `c0nst fn` so the
237    // surrounding `c0nst::c0nst!` block forces it into const-callable
238    // form on nightly. The `nightly_const_eval_prim_bits` test then binds
239    // each wrapper's result to a `const` item, proving the trait method
240    // actually evaluates at compile time.
241
242    c0nst::c0nst! {
243        pub c0nst fn const_count_ones<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> u32 {
244            PrimBits::count_ones(v)
245        }
246        pub c0nst fn const_count_zeros<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> u32 {
247            PrimBits::count_zeros(v)
248        }
249        pub c0nst fn const_leading_zeros<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> u32 {
250            PrimBits::leading_zeros(v)
251        }
252        pub c0nst fn const_trailing_zeros<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> u32 {
253            PrimBits::trailing_zeros(v)
254        }
255        pub c0nst fn const_swap_bytes<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> FixedUInt<T, N, P> {
256            PrimBits::swap_bytes(v)
257        }
258        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> {
259            PrimBits::rotate_left(v, n)
260        }
261        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> {
262            PrimBits::rotate_right(v, n)
263        }
264        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> {
265            PrimBits::unsigned_shl(v, n)
266        }
267        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> {
268            PrimBits::unsigned_shr(v, n)
269        }
270        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> {
271            PrimBits::signed_shl(v, n)
272        }
273        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> {
274            PrimBits::signed_shr(v, n)
275        }
276        pub c0nst fn const_reverse_bits<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> FixedUInt<T, N, P> {
277            PrimBits::reverse_bits(v)
278        }
279        pub c0nst fn const_to_be<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> FixedUInt<T, N, P> {
280            PrimBits::to_be(v)
281        }
282        pub c0nst fn const_to_le<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> FixedUInt<T, N, P> {
283            PrimBits::to_le(v)
284        }
285        pub c0nst fn const_from_be<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> FixedUInt<T, N, P> {
286            PrimBits::from_be(v)
287        }
288        pub c0nst fn const_from_le<T: [c0nst] ConstMachineWord + MachineWord, const N: usize, P: Personality>(v: FixedUInt<T, N, P>) -> FixedUInt<T, N, P> {
289            PrimBits::from_le(v)
290        }
291    }
292
293    #[test]
294    fn nightly_const_eval_prim_bits() {
295        // runtime smoke
296        let v = U16::from(0b0010_1000u8);
297        assert_eq!(const_count_ones(v), 2);
298        assert_eq!(const_leading_zeros(v), 10);
299        assert_eq!(const_trailing_zeros(v), 3);
300
301        #[cfg(feature = "nightly")]
302        {
303            const V: U16 = FixedUInt::from_array([0x28, 0]);
304            const V_FULL: U16 = FixedUInt::from_array([0xFF, 0xFF]);
305            const V_ONE: U16 = FixedUInt::from_array([1, 0]);
306
307            const C_ONES: u32 = const_count_ones(V);
308            const C_ZEROS: u32 = const_count_zeros(V);
309            const LZ: u32 = const_leading_zeros(V);
310            const TZ: u32 = const_trailing_zeros(V);
311            const SWAP: U16 = const_swap_bytes(V_ONE);
312            const ROTL: U16 = const_rotate_left(V_ONE, 4);
313            const ROTR: U16 = const_rotate_right(V_ONE, 4);
314            const USHL: U16 = const_unsigned_shl(V_ONE, 4);
315            const USHR: U16 = const_unsigned_shr(V_FULL, 4);
316            const SSHL: U16 = const_signed_shl(V_ONE, 4);
317            const SSHR: U16 = const_signed_shr(V_FULL, 4);
318            const REV: U16 = const_reverse_bits(V_ONE);
319            const TO_BE: U16 = const_to_be(V_ONE);
320            const TO_LE: U16 = const_to_le(V_ONE);
321            const FROM_BE: U16 = const_from_be(V_ONE);
322            const FROM_LE: U16 = const_from_le(V_ONE);
323
324            assert_eq!(C_ONES, 2);
325            assert_eq!(C_ZEROS, 14);
326            assert_eq!(LZ, 10);
327            assert_eq!(TZ, 3);
328            assert_eq!(SWAP.array, [0, 1]);
329            assert_eq!(ROTL.array, [16, 0]);
330            assert_eq!(ROTR.array, [0, 0x10]);
331            assert_eq!(USHL.array, [16, 0]);
332            assert_eq!(USHR.array, [0xFF, 0x0F]);
333            assert_eq!(SSHL.array, [16, 0]);
334            assert_eq!(SSHR.array, [0xFF, 0x0F]);
335            assert_eq!(REV.array, [0, 0x80]);
336            assert_eq!(TO_BE.array, [0, 1]);
337            assert_eq!(TO_LE.array, [1, 0]);
338            assert_eq!(FROM_BE.array, [0, 1]);
339            assert_eq!(FROM_LE.array, [1, 0]);
340        }
341    }
342
343    // --- Empirical const-eval proof for the standalone `pow_impl` ----------
344
345    #[test]
346    fn nightly_const_eval_pow() {
347        // runtime smoke (works on stable + nightly)
348        let v = U16::from(2u8);
349        assert_eq!(super::pow_impl(v, 8), U16::from(256u16));
350        assert_eq!(super::pow_impl(v, 0), U16::from(1u8));
351
352        #[cfg(feature = "nightly")]
353        {
354            const TWO: U16 = FixedUInt::from_array([2, 0]);
355            const THREE: U16 = FixedUInt::from_array([3, 0]);
356            const TWO_TO_THE_EIGHT: U16 = super::pow_impl(TWO, 8);
357            const THREE_TO_THE_FIVE: U16 = super::pow_impl(THREE, 5);
358            const ZERO_EXP: U16 = super::pow_impl(TWO, 0);
359            assert_eq!(TWO_TO_THE_EIGHT, FixedUInt::from_array([0, 1])); // 256
360            assert_eq!(THREE_TO_THE_FIVE, FixedUInt::from_array([243, 0]));
361            assert_eq!(ZERO_EXP, FixedUInt::from_array([1, 0]));
362        }
363    }
364}
fixed_bigint/fixeduint/prim_int_impl.rs

fixed_bigint/fixeduint/
prim_int_impl.rs
