ruint/
bits.rs

1use crate::Uint;
2use core::ops::{
3    BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not, Shl, ShlAssign, Shr,
4    ShrAssign,
5};
6
7impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
8    /// Returns whether a specific bit is set.
9    ///
10    /// Returns `false` if `index` exceeds the bit width of the number.
11    #[must_use]
12    #[inline]
13    pub const fn bit(&self, index: usize) -> bool {
14        if index >= BITS {
15            return false;
16        }
17        let (limbs, bits) = (index / 64, index % 64);
18        self.limbs[limbs] & (1 << bits) != 0
19    }
20
21    /// Sets a specific bit to a value.
22    #[inline]
23    pub fn set_bit(&mut self, index: usize, value: bool) {
24        if index >= BITS {
25            return;
26        }
27        let (limbs, bits) = (index / 64, index % 64);
28        if value {
29            self.limbs[limbs] |= 1 << bits;
30        } else {
31            self.limbs[limbs] &= !(1 << bits);
32        }
33    }
34
35    /// Returns a specific byte. The byte at index `0` is the least significant
36    /// byte (little endian).
37    ///
38    /// # Panics
39    ///
40    /// Panics if `index` exceeds the byte width of the number.
41    ///
42    /// # Examples
43    ///
44    /// ```
45    /// # use ruint::uint;
46    /// let x = uint!(0x1234567890_U64);
47    /// let bytes = [
48    ///     x.byte(0), // 0x90
49    ///     x.byte(1), // 0x78
50    ///     x.byte(2), // 0x56
51    ///     x.byte(3), // 0x34
52    ///     x.byte(4), // 0x12
53    ///     x.byte(5), // 0x00
54    ///     x.byte(6), // 0x00
55    ///     x.byte(7), // 0x00
56    /// ];
57    /// assert_eq!(bytes, x.to_le_bytes());
58    /// ```
59    ///
60    /// Panics if out of range.
61    ///
62    /// ```should_panic
63    /// # use ruint::uint;
64    /// let x = uint!(0x1234567890_U64);
65    /// let _ = x.byte(8);
66    /// ```
67    #[inline]
68    #[must_use]
69    #[track_caller]
70    pub const fn byte(&self, index: usize) -> u8 {
71        #[cfg(target_endian = "little")]
72        {
73            self.as_le_slice()[index]
74        }
75
76        #[cfg(target_endian = "big")]
77        #[allow(clippy::cast_possible_truncation)] // intentional
78        {
79            (self.limbs[index / 8] >> ((index % 8) * 8)) as u8
80        }
81    }
82
83    /// Reverses the order of bits in the integer. The least significant bit
84    /// becomes the most significant bit, second least-significant bit becomes
85    /// second most-significant bit, etc.
86    #[inline]
87    #[must_use]
88    pub fn reverse_bits(mut self) -> Self {
89        self.limbs.reverse();
90        for limb in &mut self.limbs {
91            *limb = limb.reverse_bits();
92        }
93        if BITS % 64 != 0 {
94            self >>= 64 - BITS % 64;
95        }
96        self
97    }
98
99    /// Returns the number of leading zeros in the binary representation of
100    /// `self`.
101    #[inline]
102    #[must_use]
103    pub fn leading_zeros(&self) -> usize {
104        self.as_limbs()
105            .iter()
106            .rev()
107            .position(|&limb| limb != 0)
108            .map_or(BITS, |n| {
109                let fixed = Self::MASK.leading_zeros() as usize;
110                let skipped = n * 64;
111                let top = self.as_limbs()[LIMBS - n - 1].leading_zeros() as usize;
112                skipped + top - fixed
113            })
114    }
115
116    /// Returns the number of leading ones in the binary representation of
117    /// `self`.
118    #[inline]
119    #[must_use]
120    pub fn leading_ones(&self) -> usize {
121        (self.not()).leading_zeros()
122    }
123
124    /// Returns the number of trailing zeros in the binary representation of
125    /// `self`.
126    #[inline]
127    #[must_use]
128    pub fn trailing_zeros(&self) -> usize {
129        self.as_limbs()
130            .iter()
131            .position(|&limb| limb != 0)
132            .map_or(BITS, |n| {
133                n * 64 + self.as_limbs()[n].trailing_zeros() as usize
134            })
135    }
136
137    /// Returns the number of trailing ones in the binary representation of
138    /// `self`.
139    #[inline]
140    #[must_use]
141    pub fn trailing_ones(&self) -> usize {
142        self.as_limbs()
143            .iter()
144            .position(|&limb| limb != u64::MAX)
145            .map_or(BITS, |n| {
146                n * 64 + self.as_limbs()[n].trailing_ones() as usize
147            })
148    }
149
150    /// Returns the number of ones in the binary representation of `self`.
151    #[inline]
152    #[must_use]
153    pub fn count_ones(&self) -> usize {
154        self.as_limbs()
155            .iter()
156            .map(|limb| limb.count_ones() as usize)
157            .sum()
158    }
159
160    /// Returns the number of zeros in the binary representation of `self`.
161    #[must_use]
162    #[inline]
163    pub fn count_zeros(&self) -> usize {
164        BITS - self.count_ones()
165    }
166
167    /// Length of the number in bits ignoring leading zeros.
168    #[must_use]
169    #[inline]
170    pub fn bit_len(&self) -> usize {
171        BITS - self.leading_zeros()
172    }
173
174    /// Length of the number in bytes ignoring leading zeros.
175    #[must_use]
176    #[inline]
177    pub fn byte_len(&self) -> usize {
178        (self.bit_len() + 7) / 8
179    }
180
181    /// Returns the most significant 64 bits of the number and the exponent.
182    ///
183    /// Given return value $(\mathtt{bits}, \mathtt{exponent})$, the `self` can
184    /// be approximated as
185    ///
186    /// $$
187    /// \mathtt{self} ≈ \mathtt{bits} ⋅ 2^\mathtt{exponent}
188    /// $$
189    ///
190    /// If `self` is $<≥> 2^{63}$, then `exponent` will be zero and `bits` will
191    /// have leading zeros.
192    #[inline]
193    #[must_use]
194    pub fn most_significant_bits(&self) -> (u64, usize) {
195        let first_set_limb = self
196            .as_limbs()
197            .iter()
198            .rposition(|&limb| limb != 0)
199            .unwrap_or(0);
200        if first_set_limb == 0 {
201            (self.as_limbs().first().copied().unwrap_or(0), 0)
202        } else {
203            let hi = self.as_limbs()[first_set_limb];
204            let lo = self.as_limbs()[first_set_limb - 1];
205            let leading_zeros = hi.leading_zeros();
206            let bits = if leading_zeros > 0 {
207                (hi << leading_zeros) | (lo >> (64 - leading_zeros))
208            } else {
209                hi
210            };
211            let exponent = first_set_limb * 64 - leading_zeros as usize;
212            (bits, exponent)
213        }
214    }
215
216    /// Checked left shift by `rhs` bits.
217    ///
218    /// Returns $\mathtt{self} ⋅ 2^{\mathtt{rhs}}$ or [`None`] if the result
219    /// would $≥ 2^{\mathtt{BITS}}$. That is, it returns [`None`] if the bits
220    /// shifted out would be non-zero.
221    ///
222    /// Note: This differs from [`u64::checked_shl`] which returns `None` if the
223    /// shift is larger than BITS (which is IMHO not very useful).
224    #[inline(always)]
225    #[must_use]
226    pub fn checked_shl(self, rhs: usize) -> Option<Self> {
227        match self.overflowing_shl(rhs) {
228            (value, false) => Some(value),
229            _ => None,
230        }
231    }
232
233    /// Saturating left shift by `rhs` bits.
234    ///
235    /// Returns $\mathtt{self} ⋅ 2^{\mathtt{rhs}}$ or [`Uint::MAX`] if the
236    /// result would $≥ 2^{\mathtt{BITS}}$. That is, it returns
237    /// [`Uint::MAX`] if the bits shifted out would be non-zero.
238    #[inline(always)]
239    #[must_use]
240    pub fn saturating_shl(self, rhs: usize) -> Self {
241        match self.overflowing_shl(rhs) {
242            (value, false) => value,
243            _ => Self::MAX,
244        }
245    }
246
247    /// Left shift by `rhs` bits with overflow detection.
248    ///
249    /// Returns $\mod{\mathtt{value} ⋅ 2^{\mathtt{rhs}}}_{2^{\mathtt{BITS}}}$.
250    /// If the product is $≥ 2^{\mathtt{BITS}}$ it returns `true`. That is, it
251    /// returns true if the bits shifted out are non-zero.
252    ///
253    /// Note: This differs from [`u64::overflowing_shl`] which returns `true` if
254    /// the shift is larger than `BITS` (which is IMHO not very useful).
255    #[inline]
256    #[must_use]
257    pub fn overflowing_shl(mut self, rhs: usize) -> (Self, bool) {
258        let (limbs, bits) = (rhs / 64, rhs % 64);
259        if limbs >= LIMBS {
260            return (Self::ZERO, self != Self::ZERO);
261        }
262        if bits == 0 {
263            // Check for overflow
264            let mut overflow = false;
265            for i in (LIMBS - limbs)..LIMBS {
266                overflow |= self.limbs[i] != 0;
267            }
268            if self.limbs[LIMBS - limbs - 1] > Self::MASK {
269                overflow = true;
270            }
271
272            // Shift
273            for i in (limbs..LIMBS).rev() {
274                assume!(i >= limbs && i - limbs < LIMBS);
275                self.limbs[i] = self.limbs[i - limbs];
276            }
277            self.limbs[..limbs].fill(0);
278            self.limbs[LIMBS - 1] &= Self::MASK;
279            return (self, overflow);
280        }
281
282        // Check for overflow
283        let mut overflow = false;
284        for i in (LIMBS - limbs)..LIMBS {
285            overflow |= self.limbs[i] != 0;
286        }
287        if self.limbs[LIMBS - limbs - 1] >> (64 - bits) != 0 {
288            overflow = true;
289        }
290        if self.limbs[LIMBS - limbs - 1] << bits > Self::MASK {
291            overflow = true;
292        }
293
294        // Shift
295        for i in (limbs + 1..LIMBS).rev() {
296            assume!(i - limbs < LIMBS && i - limbs - 1 < LIMBS);
297            self.limbs[i] = self.limbs[i - limbs] << bits;
298            self.limbs[i] |= self.limbs[i - limbs - 1] >> (64 - bits);
299        }
300        self.limbs[limbs] = self.limbs[0] << bits;
301        self.limbs[..limbs].fill(0);
302        self.limbs[LIMBS - 1] &= Self::MASK;
303        (self, overflow)
304    }
305
306    /// Left shift by `rhs` bits.
307    ///
308    /// Returns $\mod{\mathtt{value} ⋅ 2^{\mathtt{rhs}}}_{2^{\mathtt{BITS}}}$.
309    ///
310    /// Note: This differs from [`u64::wrapping_shl`] which first reduces `rhs`
311    /// by `BITS` (which is IMHO not very useful).
312    #[inline(always)]
313    #[must_use]
314    pub fn wrapping_shl(self, rhs: usize) -> Self {
315        self.overflowing_shl(rhs).0
316    }
317
318    /// Checked right shift by `rhs` bits.
319    ///
320    /// $$
321    /// \frac{\mathtt{self}}{2^{\mathtt{rhs}}}
322    /// $$
323    ///
324    /// Returns the above or [`None`] if the division is not exact. This is the
325    /// same as
326    ///
327    /// Note: This differs from [`u64::checked_shr`] which returns `None` if the
328    /// shift is larger than BITS (which is IMHO not very useful).
329    #[inline(always)]
330    #[must_use]
331    pub fn checked_shr(self, rhs: usize) -> Option<Self> {
332        match self.overflowing_shr(rhs) {
333            (value, false) => Some(value),
334            _ => None,
335        }
336    }
337
338    /// Right shift by `rhs` bits with underflow detection.
339    ///
340    /// $$
341    /// \floor{\frac{\mathtt{self}}{2^{\mathtt{rhs}}}}
342    /// $$
343    ///
344    /// Returns the above and `false` if the division was exact, and `true` if
345    /// it was rounded down. This is the same as non-zero bits being shifted
346    /// out.
347    ///
348    /// Note: This differs from [`u64::overflowing_shr`] which returns `true` if
349    /// the shift is larger than `BITS` (which is IMHO not very useful).
350    #[inline]
351    #[must_use]
352    pub fn overflowing_shr(mut self, rhs: usize) -> (Self, bool) {
353        let (limbs, bits) = (rhs / 64, rhs % 64);
354        if limbs >= LIMBS {
355            return (Self::ZERO, self != Self::ZERO);
356        }
357        if bits == 0 {
358            // Check for overflow
359            let mut overflow = false;
360            for i in 0..limbs {
361                overflow |= self.limbs[i] != 0;
362            }
363
364            // Shift
365            for i in 0..(LIMBS - limbs) {
366                self.limbs[i] = self.limbs[i + limbs];
367            }
368            self.limbs[LIMBS - limbs..].fill(0);
369            return (self, overflow);
370        }
371
372        // Check for overflow
373        let overflow = self.limbs[LIMBS - limbs - 1] >> (bits - 1) & 1 != 0;
374
375        // Shift
376        for i in 0..(LIMBS - limbs - 1) {
377            assume!(i + limbs < LIMBS && i + limbs + 1 < LIMBS);
378            self.limbs[i] = self.limbs[i + limbs] >> bits;
379            self.limbs[i] |= self.limbs[i + limbs + 1] << (64 - bits);
380        }
381        self.limbs[LIMBS - limbs - 1] = self.limbs[LIMBS - 1] >> bits;
382        self.limbs[LIMBS - limbs..].fill(0);
383        (self, overflow)
384    }
385
386    /// Right shift by `rhs` bits.
387    ///
388    /// $$
389    /// \mathtt{wrapping\\_shr}(\mathtt{self}, \mathtt{rhs}) =
390    /// \floor{\frac{\mathtt{self}}{2^{\mathtt{rhs}}}}
391    /// $$
392    ///
393    /// Note: This differs from [`u64::wrapping_shr`] which first reduces `rhs`
394    /// by `BITS` (which is IMHO not very useful).
395    #[inline(always)]
396    #[must_use]
397    pub fn wrapping_shr(self, rhs: usize) -> Self {
398        self.overflowing_shr(rhs).0
399    }
400
401    /// Arithmetic shift right by `rhs` bits.
402    #[inline]
403    #[must_use]
404    pub fn arithmetic_shr(self, rhs: usize) -> Self {
405        if BITS == 0 {
406            return Self::ZERO;
407        }
408        let sign = self.bit(BITS - 1);
409        let mut r = self >> rhs;
410        if sign {
411            r |= Self::MAX << BITS.saturating_sub(rhs);
412        }
413        r
414    }
415
416    /// Shifts the bits to the left by a specified amount, `rhs`, wrapping the
417    /// truncated bits to the end of the resulting integer.
418    #[inline]
419    #[must_use]
420    #[allow(clippy::missing_const_for_fn)] // False positive
421    pub fn rotate_left(self, rhs: usize) -> Self {
422        if BITS == 0 {
423            return Self::ZERO;
424        }
425        let rhs = rhs % BITS;
426        self << rhs | self >> (BITS - rhs)
427    }
428
429    /// Shifts the bits to the right by a specified amount, `rhs`, wrapping the
430    /// truncated bits to the beginning of the resulting integer.
431    #[inline(always)]
432    #[must_use]
433    pub fn rotate_right(self, rhs: usize) -> Self {
434        if BITS == 0 {
435            return Self::ZERO;
436        }
437        let rhs = rhs % BITS;
438        self.rotate_left(BITS - rhs)
439    }
440}
441
442impl<const BITS: usize, const LIMBS: usize> Not for Uint<BITS, LIMBS> {
443    type Output = Self;
444
445    #[inline]
446    fn not(mut self) -> Self::Output {
447        if BITS == 0 {
448            return Self::ZERO;
449        }
450        for limb in &mut self.limbs {
451            *limb = u64::not(*limb);
452        }
453        self.limbs[LIMBS - 1] &= Self::MASK;
454        self
455    }
456}
457
458impl<const BITS: usize, const LIMBS: usize> Not for &Uint<BITS, LIMBS> {
459    type Output = Uint<BITS, LIMBS>;
460
461    #[inline]
462    fn not(self) -> Self::Output {
463        (*self).not()
464    }
465}
466
467macro_rules! impl_bit_op {
468    ($trait:ident, $fn:ident, $trait_assign:ident, $fn_assign:ident) => {
469        impl<const BITS: usize, const LIMBS: usize> $trait_assign<Uint<BITS, LIMBS>>
470            for Uint<BITS, LIMBS>
471        {
472            #[inline(always)]
473            fn $fn_assign(&mut self, rhs: Uint<BITS, LIMBS>) {
474                self.$fn_assign(&rhs);
475            }
476        }
477
478        impl<const BITS: usize, const LIMBS: usize> $trait_assign<&Uint<BITS, LIMBS>>
479            for Uint<BITS, LIMBS>
480        {
481            #[inline]
482            fn $fn_assign(&mut self, rhs: &Uint<BITS, LIMBS>) {
483                for i in 0..LIMBS {
484                    u64::$fn_assign(&mut self.limbs[i], rhs.limbs[i]);
485                }
486            }
487        }
488
489        impl<const BITS: usize, const LIMBS: usize> $trait<Uint<BITS, LIMBS>>
490            for Uint<BITS, LIMBS>
491        {
492            type Output = Uint<BITS, LIMBS>;
493
494            #[inline(always)]
495            fn $fn(mut self, rhs: Uint<BITS, LIMBS>) -> Self::Output {
496                self.$fn_assign(rhs);
497                self
498            }
499        }
500
501        impl<const BITS: usize, const LIMBS: usize> $trait<&Uint<BITS, LIMBS>>
502            for Uint<BITS, LIMBS>
503        {
504            type Output = Uint<BITS, LIMBS>;
505
506            #[inline(always)]
507            fn $fn(mut self, rhs: &Uint<BITS, LIMBS>) -> Self::Output {
508                self.$fn_assign(rhs);
509                self
510            }
511        }
512
513        impl<const BITS: usize, const LIMBS: usize> $trait<Uint<BITS, LIMBS>>
514            for &Uint<BITS, LIMBS>
515        {
516            type Output = Uint<BITS, LIMBS>;
517
518            #[inline(always)]
519            fn $fn(self, mut rhs: Uint<BITS, LIMBS>) -> Self::Output {
520                rhs.$fn_assign(self);
521                rhs
522            }
523        }
524
525        impl<const BITS: usize, const LIMBS: usize> $trait<&Uint<BITS, LIMBS>>
526            for &Uint<BITS, LIMBS>
527        {
528            type Output = Uint<BITS, LIMBS>;
529
530            #[inline(always)]
531            fn $fn(self, rhs: &Uint<BITS, LIMBS>) -> Self::Output {
532                self.clone().$fn(rhs)
533            }
534        }
535    };
536}
537
538impl_bit_op!(BitOr, bitor, BitOrAssign, bitor_assign);
539impl_bit_op!(BitAnd, bitand, BitAndAssign, bitand_assign);
540impl_bit_op!(BitXor, bitxor, BitXorAssign, bitxor_assign);
541
542impl<const BITS: usize, const LIMBS: usize> Shl<Self> for Uint<BITS, LIMBS> {
543    type Output = Self;
544
545    #[inline(always)]
546    fn shl(self, rhs: Self) -> Self::Output {
547        // This check shortcuts, and prevents panics on the `[0]` later
548        if BITS == 0 {
549            return self;
550        }
551        // Rationale: if BITS is larger than 2**64 - 1, it means we're running
552        // on a 128-bit platform with 2.3 exabytes of memory. In this case,
553        // the code produces incorrect output.
554        #[allow(clippy::cast_possible_truncation)]
555        self.wrapping_shl(rhs.as_limbs()[0] as usize)
556    }
557}
558
559impl<const BITS: usize, const LIMBS: usize> Shl<&Self> for Uint<BITS, LIMBS> {
560    type Output = Self;
561
562    #[inline(always)]
563    fn shl(self, rhs: &Self) -> Self::Output {
564        self << *rhs
565    }
566}
567
568impl<const BITS: usize, const LIMBS: usize> Shr<Self> for Uint<BITS, LIMBS> {
569    type Output = Self;
570
571    #[inline(always)]
572    fn shr(self, rhs: Self) -> Self::Output {
573        // This check shortcuts, and prevents panics on the `[0]` later
574        if BITS == 0 {
575            return self;
576        }
577        // Rationale: if BITS is larger than 2**64 - 1, it means we're running
578        // on a 128-bit platform with 2.3 exabytes of memory. In this case,
579        // the code produces incorrect output.
580        #[allow(clippy::cast_possible_truncation)]
581        self.wrapping_shr(rhs.as_limbs()[0] as usize)
582    }
583}
584
585impl<const BITS: usize, const LIMBS: usize> Shr<&Self> for Uint<BITS, LIMBS> {
586    type Output = Self;
587
588    #[inline(always)]
589    fn shr(self, rhs: &Self) -> Self::Output {
590        self >> *rhs
591    }
592}
593
594impl<const BITS: usize, const LIMBS: usize> ShlAssign<Self> for Uint<BITS, LIMBS> {
595    #[inline(always)]
596    fn shl_assign(&mut self, rhs: Self) {
597        *self = *self << rhs;
598    }
599}
600
601impl<const BITS: usize, const LIMBS: usize> ShlAssign<&Self> for Uint<BITS, LIMBS> {
602    #[inline(always)]
603    fn shl_assign(&mut self, rhs: &Self) {
604        *self = *self << rhs;
605    }
606}
607
608impl<const BITS: usize, const LIMBS: usize> ShrAssign<Self> for Uint<BITS, LIMBS> {
609    #[inline(always)]
610    fn shr_assign(&mut self, rhs: Self) {
611        *self = *self >> rhs;
612    }
613}
614
615impl<const BITS: usize, const LIMBS: usize> ShrAssign<&Self> for Uint<BITS, LIMBS> {
616    #[inline(always)]
617    fn shr_assign(&mut self, rhs: &Self) {
618        *self = *self >> rhs;
619    }
620}
621
622macro_rules! impl_shift {
623    (@main $u:ty) => {
624        impl<const BITS: usize, const LIMBS: usize> Shl<$u> for Uint<BITS, LIMBS> {
625            type Output = Self;
626
627            #[inline(always)]
628            #[allow(clippy::cast_possible_truncation)]
629            fn shl(self, rhs: $u) -> Self::Output {
630                self.wrapping_shl(rhs as usize)
631            }
632        }
633
634        impl<const BITS: usize, const LIMBS: usize> Shr<$u> for Uint<BITS, LIMBS> {
635            type Output = Self;
636
637            #[inline(always)]
638            #[allow(clippy::cast_possible_truncation)]
639            fn shr(self, rhs: $u) -> Self::Output {
640                self.wrapping_shr(rhs as usize)
641            }
642        }
643    };
644
645    (@ref $u:ty) => {
646        impl<const BITS: usize, const LIMBS: usize> Shl<&$u> for Uint<BITS, LIMBS> {
647            type Output = Self;
648
649            #[inline(always)]
650            fn shl(self, rhs: &$u) -> Self::Output {
651                <Self>::shl(self, *rhs)
652            }
653        }
654
655        impl<const BITS: usize, const LIMBS: usize> Shr<&$u> for Uint<BITS, LIMBS> {
656            type Output = Self;
657
658            #[inline(always)]
659            fn shr(self, rhs: &$u) -> Self::Output {
660                <Self>::shr(self, *rhs)
661            }
662        }
663    };
664
665    (@assign $u:ty) => {
666        impl<const BITS: usize, const LIMBS: usize> ShlAssign<$u> for Uint<BITS, LIMBS> {
667            #[inline(always)]
668            fn shl_assign(&mut self, rhs: $u) {
669                *self = *self << rhs;
670            }
671        }
672
673        impl<const BITS: usize, const LIMBS: usize> ShrAssign<$u> for Uint<BITS, LIMBS> {
674            #[inline(always)]
675            fn shr_assign(&mut self, rhs: $u) {
676                *self = *self >> rhs;
677            }
678        }
679    };
680
681    ($u:ty) => {
682        impl_shift!(@main $u);
683        impl_shift!(@ref $u);
684        impl_shift!(@assign $u);
685        impl_shift!(@assign &$u);
686    };
687
688    ($u:ty, $($tail:ty),*) => {
689        impl_shift!($u);
690        impl_shift!($($tail),*);
691    };
692}
693
694impl_shift!(usize, u8, u16, u32, isize, i8, i16, i32);
695
696// Only when losslessy castable to usize.
697#[cfg(target_pointer_width = "64")]
698impl_shift!(u64, i64);
699
700#[cfg(test)]
701mod tests {
702    use super::*;
703    use crate::{aliases::U128, const_for, nlimbs};
704    use core::cmp::min;
705    use proptest::proptest;
706
707    #[test]
708    fn test_leading_zeros() {
709        assert_eq!(Uint::<0, 0>::ZERO.leading_zeros(), 0);
710        assert_eq!(Uint::<1, 1>::ZERO.leading_zeros(), 1);
711        assert_eq!(Uint::<1, 1>::from(1).leading_zeros(), 0);
712        const_for!(BITS in NON_ZERO {
713            const LIMBS: usize = nlimbs(BITS);
714            type U = Uint::<BITS, LIMBS>;
715            assert_eq!(U::ZERO.leading_zeros(), BITS);
716            assert_eq!(U::MAX.leading_zeros(), 0);
717            assert_eq!(U::from(1).leading_zeros(), BITS - 1);
718            proptest!(|(value: U)| {
719                let zeros = value.leading_zeros();
720                assert!(zeros <= BITS);
721                assert!(zeros < BITS || value == U::ZERO);
722                if zeros < BITS {
723                    let (left, overflow) = value.overflowing_shl(zeros);
724                    assert!(!overflow);
725                    assert!(left.leading_zeros() == 0 || value == U::ZERO);
726                    assert!(left.bit(BITS - 1));
727                    assert_eq!(value >> (BITS - zeros), Uint::ZERO);
728                }
729            });
730        });
731        proptest!(|(value: u128)| {
732            let uint = U128::from(value);
733            assert_eq!(uint.leading_zeros(), value.leading_zeros() as usize);
734        });
735    }
736
737    #[test]
738    fn test_leading_ones() {
739        assert_eq!(Uint::<0, 0>::ZERO.leading_ones(), 0);
740        assert_eq!(Uint::<1, 1>::ZERO.leading_ones(), 0);
741        assert_eq!(Uint::<1, 1>::from(1).leading_ones(), 1);
742    }
743
744    #[test]
745    fn test_most_significant_bits() {
746        const_for!(BITS in NON_ZERO {
747            const LIMBS: usize = nlimbs(BITS);
748            type U = Uint::<BITS, LIMBS>;
749            proptest!(|(value: u64)| {
750                let value = if U::LIMBS <= 1 { value & U::MASK } else { value };
751                assert_eq!(U::from(value).most_significant_bits(), (value, 0));
752            });
753        });
754        proptest!(|(mut limbs: [u64; 2])| {
755            if limbs[1] == 0 {
756                limbs[1] = 1;
757            }
758            let (bits, exponent) = U128::from_limbs(limbs).most_significant_bits();
759            assert!(bits >= 1_u64 << 63);
760            assert_eq!(exponent, 64 - limbs[1].leading_zeros() as usize);
761        });
762    }
763
764    #[test]
765    fn test_checked_shl() {
766        assert_eq!(
767            Uint::<65, 2>::from_limbs([0x0010_0000_0000_0000, 0]).checked_shl(1),
768            Some(Uint::<65, 2>::from_limbs([0x0020_0000_0000_0000, 0]))
769        );
770        assert_eq!(
771            Uint::<127, 2>::from_limbs([0x0010_0000_0000_0000, 0]).checked_shl(64),
772            Some(Uint::<127, 2>::from_limbs([0, 0x0010_0000_0000_0000]))
773        );
774    }
775
776    #[test]
777    #[allow(clippy::cast_lossless, clippy::cast_possible_truncation)]
778    fn test_small() {
779        const_for!(BITS in [1, 2, 8, 16, 32, 63, 64] {
780            type U = Uint::<BITS, 1>;
781            proptest!(|(a: U, b: U)| {
782                assert_eq!(a | b, U::from_limbs([a.limbs[0] | b.limbs[0]]));
783                assert_eq!(a & b, U::from_limbs([a.limbs[0] & b.limbs[0]]));
784                assert_eq!(a ^ b, U::from_limbs([a.limbs[0] ^ b.limbs[0]]));
785            });
786            proptest!(|(a: U, s in 0..BITS)| {
787                assert_eq!(a << s, U::from_limbs([a.limbs[0] << s & U::MASK]));
788                assert_eq!(a >> s, U::from_limbs([a.limbs[0] >> s]));
789            });
790        });
791        proptest!(|(a: Uint::<32, 1>, s in 0_usize..=34)| {
792            assert_eq!(a.reverse_bits(), Uint::from((a.limbs[0] as u32).reverse_bits() as u64));
793            assert_eq!(a.rotate_left(s), Uint::from((a.limbs[0] as u32).rotate_left(s as u32) as u64));
794            assert_eq!(a.rotate_right(s), Uint::from((a.limbs[0] as u32).rotate_right(s as u32) as u64));
795            if s < 32 {
796                let arr_shifted = (((a.limbs[0] as i32) >> s) as u32) as u64;
797                assert_eq!(a.arithmetic_shr(s), Uint::from_limbs([arr_shifted]));
798            }
799        });
800        proptest!(|(a: Uint::<64, 1>, s in 0_usize..=66)| {
801            assert_eq!(a.reverse_bits(), Uint::from(a.limbs[0].reverse_bits()));
802            assert_eq!(a.rotate_left(s), Uint::from(a.limbs[0].rotate_left(s as u32)));
803            assert_eq!(a.rotate_right(s), Uint::from(a.limbs[0].rotate_right(s as u32)));
804            if s < 64 {
805                let arr_shifted = ((a.limbs[0] as i64) >> s) as u64;
806                assert_eq!(a.arithmetic_shr(s), Uint::from_limbs([arr_shifted]));
807            }
808        });
809    }
810
811    #[test]
812    fn test_shift_reverse() {
813        const_for!(BITS in SIZES {
814            const LIMBS: usize = nlimbs(BITS);
815            type U = Uint::<BITS, LIMBS>;
816            proptest!(|(value: U, shift in 0..=BITS + 2)| {
817                let left = (value << shift).reverse_bits();
818                let right = value.reverse_bits() >> shift;
819                assert_eq!(left, right);
820            });
821        });
822    }
823
824    #[test]
825    fn test_rotate() {
826        const_for!(BITS in SIZES {
827            const LIMBS: usize = nlimbs(BITS);
828            type U = Uint::<BITS, LIMBS>;
829            proptest!(|(value: U, shift in  0..=BITS + 2)| {
830                let rotated = value.rotate_left(shift).rotate_right(shift);
831                assert_eq!(value, rotated);
832            });
833        });
834    }
835
836    #[test]
837    fn test_arithmetic_shr() {
838        const_for!(BITS in SIZES {
839            const LIMBS: usize = nlimbs(BITS);
840            type U = Uint::<BITS, LIMBS>;
841            proptest!(|(value: U, shift in  0..=BITS + 2)| {
842                let shifted = value.arithmetic_shr(shift);
843                dbg!(value, shifted, shift);
844                assert_eq!(shifted.leading_ones(), match value.leading_ones() {
845                    0 => 0,
846                    n => min(BITS, n + shift)
847                });
848            });
849        });
850    }
851
852    #[test]
853    fn test_overflowing_shr() {
854        // Test: Single limb right shift from 40u64 by 1 bit.
855        // Expects resulting integer: 20 with no fractional part.
856        assert_eq!(
857            Uint::<64, 1>::from_limbs([40u64]).overflowing_shr(1),
858            (Uint::<64, 1>::from(20), false)
859        );
860
861        // Test: Single limb right shift from 41u64 by 1 bit.
862        // Expects resulting integer: 20 with a detected fractional part.
863        assert_eq!(
864            Uint::<64, 1>::from_limbs([41u64]).overflowing_shr(1),
865            (Uint::<64, 1>::from(20), true)
866        );
867
868        // Test: Two limbs right shift from 0x0010_0000_0000_0000 and 0 by 1 bit.
869        // Expects resulting limbs: [0x0080_0000_0000_000, 0] with no fractional part.
870        assert_eq!(
871            Uint::<65, 2>::from_limbs([0x0010_0000_0000_0000, 0]).overflowing_shr(1),
872            (Uint::<65, 2>::from_limbs([0x0080_0000_0000_000, 0]), false)
873        );
874
875        // Test: Shift beyond single limb capacity with MAX value.
876        // Expects the highest possible value in 256-bit representation with a detected
877        // fractional part.
878        assert_eq!(
879            Uint::<256, 4>::MAX.overflowing_shr(65),
880            (
881                Uint::<256, 4>::from_str_radix(
882                    "7fffffffffffffffffffffffffffffffffffffffffffffff",
883                    16
884                )
885                .unwrap(),
886                true
887            )
888        );
889        // Test: Large 4096-bit integer right shift by 34 bits.
890        // Expects a specific value with no fractional part.
891        assert_eq!(
892            Uint::<4096, 64>::from_str_radix("3ffffffffffffffffffffffffffffc00000000", 16,)
893                .unwrap()
894                .overflowing_shr(34),
895            (
896                Uint::<4096, 64>::from_str_radix("fffffffffffffffffffffffffffff", 16).unwrap(),
897                false
898            )
899        );
900        // Test: Extremely large 4096-bit integer right shift by 100 bits.
901        // Expects a specific value with no fractional part.
902        assert_eq!(
903            Uint::<4096, 64>::from_str_radix(
904                "fffffffffffffffffffffffffffff0000000000000000000000000",
905                16,
906            )
907            .unwrap()
908            .overflowing_shr(100),
909            (
910                Uint::<4096, 64>::from_str_radix("fffffffffffffffffffffffffffff", 16).unwrap(),
911                false
912            )
913        );
914        // Test: Complex 4096-bit integer right shift by 1 bit.
915        // Expects a specific value with no fractional part.
916        assert_eq!(
917            Uint::<4096, 64>::from_str_radix(
918                "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff0bdbfe",
919                16,
920            )
921            .unwrap()
922            .overflowing_shr(1),
923            (
924                Uint::<4096, 64>::from_str_radix(
925                    "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffff85edff",
926                    16
927                )
928                .unwrap(),
929                false
930            )
931        );
932        // Test: Large 4096-bit integer right shift by 1000 bits.
933        // Expects a specific value with no fractional part.
934        assert_eq!(
935            Uint::<4096, 64>::from_str_radix(
936                "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
937                16,
938            )
939            .unwrap()
940            .overflowing_shr(1000),
941            (
942                Uint::<4096, 64>::from_str_radix(
943                    "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
944                    16
945                )
946                .unwrap(),
947                false
948            )
949        );
950        // Test: MAX 4096-bit integer right shift by 34 bits.
951        // Expects a specific value with a detected fractional part.
952        assert_eq!(
953            Uint::<4096, 64>::MAX
954            .overflowing_shr(34),
955            (
956                Uint::<4096, 64>::from_str_radix(
957                    "3fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
958                    16
959                )
960                .unwrap(),
961                true
962            )
963        );
964    }
965}
ruint/bits.rs

ruint/
bits.rs
