num_traits/
int.rs

1use core::ops::{BitAnd, BitOr, BitXor, Not, Shl, Shr};
2
3use crate::bounds::Bounded;
4use crate::ops::checked::*;
5use crate::ops::saturating::Saturating;
6use crate::{Num, NumCast};
7
8/// Generic trait for primitive integers.
9///
10/// The `PrimInt` trait is an abstraction over the builtin primitive integer types (e.g., `u8`,
11/// `u32`, `isize`, `i128`, ...). It inherits the basic numeric traits and extends them with
12/// bitwise operators and non-wrapping arithmetic.
13///
14/// The trait explicitly inherits `Copy`, `Eq`, `Ord`, and `Sized`. The intention is that all
15/// types implementing this trait behave like primitive types that are passed by value by default
16/// and behave like builtin integers. Furthermore, the types are expected to expose the integer
17/// value in binary representation and support bitwise operators. The standard bitwise operations
18/// (e.g., bitwise-and, bitwise-or, right-shift, left-shift) are inherited and the trait extends
19/// these with introspective queries (e.g., `PrimInt::count_ones()`, `PrimInt::leading_zeros()`),
20/// bitwise combinators (e.g., `PrimInt::rotate_left()`), and endianness converters (e.g.,
21/// `PrimInt::to_be()`).
22///
23/// All `PrimInt` types are expected to be fixed-width binary integers. The width can be queried
24/// via `T::zero().count_zeros()`. The trait currently lacks a way to query the width at
25/// compile-time.
26///
27/// While a default implementation for all builtin primitive integers is provided, the trait is in
28/// no way restricted to these. Other integer types that fulfil the requirements are free to
29/// implement the trait was well.
30///
31/// This trait and many of the method names originate in the unstable `core::num::Int` trait from
32/// the rust standard library. The original trait was never stabilized and thus removed from the
33/// standard library.
34pub trait PrimInt:
35    Sized
36    + Copy
37    + Num
38    + NumCast
39    + Bounded
40    + PartialOrd
41    + Ord
42    + Eq
43    + Not<Output = Self>
44    + BitAnd<Output = Self>
45    + BitOr<Output = Self>
46    + BitXor<Output = Self>
47    + Shl<usize, Output = Self>
48    + Shr<usize, Output = Self>
49    + CheckedAdd<Output = Self>
50    + CheckedSub<Output = Self>
51    + CheckedMul<Output = Self>
52    + CheckedDiv<Output = Self>
53    + Saturating
54{
55    /// Returns the number of ones in the binary representation of `self`.
56    ///
57    /// # Examples
58    ///
59    /// ```
60    /// use num_traits::PrimInt;
61    ///
62    /// let n = 0b01001100u8;
63    ///
64    /// assert_eq!(n.count_ones(), 3);
65    /// ```
66    fn count_ones(self) -> u32;
67
68    /// Returns the number of zeros in the binary representation of `self`.
69    ///
70    /// # Examples
71    ///
72    /// ```
73    /// use num_traits::PrimInt;
74    ///
75    /// let n = 0b01001100u8;
76    ///
77    /// assert_eq!(n.count_zeros(), 5);
78    /// ```
79    fn count_zeros(self) -> u32;
80
81    /// Returns the number of leading ones in the binary representation
82    /// of `self`.
83    ///
84    /// # Examples
85    ///
86    /// ```
87    /// use num_traits::PrimInt;
88    ///
89    /// let n = 0xF00Du16;
90    ///
91    /// assert_eq!(n.leading_ones(), 4);
92    /// ```
93    fn leading_ones(self) -> u32 {
94        (!self).leading_zeros()
95    }
96
97    /// Returns the number of leading zeros in the binary representation
98    /// of `self`.
99    ///
100    /// # Examples
101    ///
102    /// ```
103    /// use num_traits::PrimInt;
104    ///
105    /// let n = 0b0101000u16;
106    ///
107    /// assert_eq!(n.leading_zeros(), 10);
108    /// ```
109    fn leading_zeros(self) -> u32;
110
111    /// Returns the number of trailing ones in the binary representation
112    /// of `self`.
113    ///
114    /// # Examples
115    ///
116    /// ```
117    /// use num_traits::PrimInt;
118    ///
119    /// let n = 0xBEEFu16;
120    ///
121    /// assert_eq!(n.trailing_ones(), 4);
122    /// ```
123    fn trailing_ones(self) -> u32 {
124        (!self).trailing_zeros()
125    }
126
127    /// Returns the number of trailing zeros in the binary representation
128    /// of `self`.
129    ///
130    /// # Examples
131    ///
132    /// ```
133    /// use num_traits::PrimInt;
134    ///
135    /// let n = 0b0101000u16;
136    ///
137    /// assert_eq!(n.trailing_zeros(), 3);
138    /// ```
139    fn trailing_zeros(self) -> u32;
140
141    /// Shifts the bits to the left by a specified amount, `n`, wrapping
142    /// the truncated bits to the end of the resulting integer.
143    ///
144    /// # Examples
145    ///
146    /// ```
147    /// use num_traits::PrimInt;
148    ///
149    /// let n = 0x0123456789ABCDEFu64;
150    /// let m = 0x3456789ABCDEF012u64;
151    ///
152    /// assert_eq!(n.rotate_left(12), m);
153    /// ```
154    fn rotate_left(self, n: u32) -> Self;
155
156    /// Shifts the bits to the right by a specified amount, `n`, wrapping
157    /// the truncated bits to the beginning of the resulting integer.
158    ///
159    /// # Examples
160    ///
161    /// ```
162    /// use num_traits::PrimInt;
163    ///
164    /// let n = 0x0123456789ABCDEFu64;
165    /// let m = 0xDEF0123456789ABCu64;
166    ///
167    /// assert_eq!(n.rotate_right(12), m);
168    /// ```
169    fn rotate_right(self, n: u32) -> Self;
170
171    /// Shifts the bits to the left by a specified amount, `n`, filling
172    /// zeros in the least significant bits.
173    ///
174    /// This is bitwise equivalent to signed `Shl`.
175    ///
176    /// # Examples
177    ///
178    /// ```
179    /// use num_traits::PrimInt;
180    ///
181    /// let n = 0x0123456789ABCDEFu64;
182    /// let m = 0x3456789ABCDEF000u64;
183    ///
184    /// assert_eq!(n.signed_shl(12), m);
185    /// ```
186    fn signed_shl(self, n: u32) -> Self;
187
188    /// Shifts the bits to the right by a specified amount, `n`, copying
189    /// the "sign bit" in the most significant bits even for unsigned types.
190    ///
191    /// This is bitwise equivalent to signed `Shr`.
192    ///
193    /// # Examples
194    ///
195    /// ```
196    /// use num_traits::PrimInt;
197    ///
198    /// let n = 0xFEDCBA9876543210u64;
199    /// let m = 0xFFFFEDCBA9876543u64;
200    ///
201    /// assert_eq!(n.signed_shr(12), m);
202    /// ```
203    fn signed_shr(self, n: u32) -> Self;
204
205    /// Shifts the bits to the left by a specified amount, `n`, filling
206    /// zeros in the least significant bits.
207    ///
208    /// This is bitwise equivalent to unsigned `Shl`.
209    ///
210    /// # Examples
211    ///
212    /// ```
213    /// use num_traits::PrimInt;
214    ///
215    /// let n = 0x0123456789ABCDEFi64;
216    /// let m = 0x3456789ABCDEF000i64;
217    ///
218    /// assert_eq!(n.unsigned_shl(12), m);
219    /// ```
220    fn unsigned_shl(self, n: u32) -> Self;
221
222    /// Shifts the bits to the right by a specified amount, `n`, filling
223    /// zeros in the most significant bits.
224    ///
225    /// This is bitwise equivalent to unsigned `Shr`.
226    ///
227    /// # Examples
228    ///
229    /// ```
230    /// use num_traits::PrimInt;
231    ///
232    /// let n = -8i8; // 0b11111000
233    /// let m = 62i8; // 0b00111110
234    ///
235    /// assert_eq!(n.unsigned_shr(2), m);
236    /// ```
237    fn unsigned_shr(self, n: u32) -> Self;
238
239    /// Reverses the byte order of the integer.
240    ///
241    /// # Examples
242    ///
243    /// ```
244    /// use num_traits::PrimInt;
245    ///
246    /// let n = 0x0123456789ABCDEFu64;
247    /// let m = 0xEFCDAB8967452301u64;
248    ///
249    /// assert_eq!(n.swap_bytes(), m);
250    /// ```
251    fn swap_bytes(self) -> Self;
252
253    /// Reverses the order of bits in the integer.
254    ///
255    /// The least significant bit becomes the most significant bit, second least-significant bit
256    /// becomes second most-significant bit, etc.
257    ///
258    /// # Examples
259    ///
260    /// ```
261    /// use num_traits::PrimInt;
262    ///
263    /// let n = 0x12345678u32;
264    /// let m = 0x1e6a2c48u32;
265    ///
266    /// assert_eq!(n.reverse_bits(), m);
267    /// assert_eq!(0u32.reverse_bits(), 0);
268    /// ```
269    fn reverse_bits(self) -> Self {
270        reverse_bits_fallback(self)
271    }
272
273    /// Convert an integer from big endian to the target's endianness.
274    ///
275    /// On big endian this is a no-op. On little endian the bytes are swapped.
276    ///
277    /// # Examples
278    ///
279    /// ```
280    /// use num_traits::PrimInt;
281    ///
282    /// let n = 0x0123456789ABCDEFu64;
283    ///
284    /// if cfg!(target_endian = "big") {
285    ///     assert_eq!(u64::from_be(n), n)
286    /// } else {
287    ///     assert_eq!(u64::from_be(n), n.swap_bytes())
288    /// }
289    /// ```
290    fn from_be(x: Self) -> Self;
291
292    /// Convert an integer from little endian to the target's endianness.
293    ///
294    /// On little endian this is a no-op. On big endian the bytes are swapped.
295    ///
296    /// # Examples
297    ///
298    /// ```
299    /// use num_traits::PrimInt;
300    ///
301    /// let n = 0x0123456789ABCDEFu64;
302    ///
303    /// if cfg!(target_endian = "little") {
304    ///     assert_eq!(u64::from_le(n), n)
305    /// } else {
306    ///     assert_eq!(u64::from_le(n), n.swap_bytes())
307    /// }
308    /// ```
309    fn from_le(x: Self) -> Self;
310
311    /// Convert `self` to big endian from the target's endianness.
312    ///
313    /// On big endian this is a no-op. On little endian the bytes are swapped.
314    ///
315    /// # Examples
316    ///
317    /// ```
318    /// use num_traits::PrimInt;
319    ///
320    /// let n = 0x0123456789ABCDEFu64;
321    ///
322    /// if cfg!(target_endian = "big") {
323    ///     assert_eq!(n.to_be(), n)
324    /// } else {
325    ///     assert_eq!(n.to_be(), n.swap_bytes())
326    /// }
327    /// ```
328    fn to_be(self) -> Self;
329
330    /// Convert `self` to little endian from the target's endianness.
331    ///
332    /// On little endian this is a no-op. On big endian the bytes are swapped.
333    ///
334    /// # Examples
335    ///
336    /// ```
337    /// use num_traits::PrimInt;
338    ///
339    /// let n = 0x0123456789ABCDEFu64;
340    ///
341    /// if cfg!(target_endian = "little") {
342    ///     assert_eq!(n.to_le(), n)
343    /// } else {
344    ///     assert_eq!(n.to_le(), n.swap_bytes())
345    /// }
346    /// ```
347    fn to_le(self) -> Self;
348
349    /// Raises self to the power of `exp`, using exponentiation by squaring.
350    ///
351    /// # Examples
352    ///
353    /// ```
354    /// use num_traits::PrimInt;
355    ///
356    /// assert_eq!(2i32.pow(4), 16);
357    /// ```
358    fn pow(self, exp: u32) -> Self;
359}
360
361fn one_per_byte<P: PrimInt>() -> P {
362    // i8, u8: return 0x01
363    // i16, u16: return 0x0101 = (0x01 << 8) | 0x01
364    // i32, u32: return 0x01010101 = (0x0101 << 16) | 0x0101
365    // ...
366    let mut ret = P::one();
367    let mut shift = 8;
368    let mut b = ret.count_zeros() >> 3;
369    while b != 0 {
370        ret = (ret << shift) | ret;
371        shift <<= 1;
372        b >>= 1;
373    }
374    ret
375}
376
377fn reverse_bits_fallback<P: PrimInt>(i: P) -> P {
378    let rep_01: P = one_per_byte();
379    let rep_03 = (rep_01 << 1) | rep_01;
380    let rep_05 = (rep_01 << 2) | rep_01;
381    let rep_0f = (rep_03 << 2) | rep_03;
382    let rep_33 = (rep_03 << 4) | rep_03;
383    let rep_55 = (rep_05 << 4) | rep_05;
384
385    // code above only used to determine rep_0f, rep_33, rep_55;
386    // optimizer should be able to do it in compile time
387    let mut ret = i.swap_bytes();
388    ret = ((ret & rep_0f) << 4) | ((ret >> 4) & rep_0f);
389    ret = ((ret & rep_33) << 2) | ((ret >> 2) & rep_33);
390    ret = ((ret & rep_55) << 1) | ((ret >> 1) & rep_55);
391    ret
392}
393
394macro_rules! prim_int_impl {
395    ($T:ty, $S:ty, $U:ty) => {
396        impl PrimInt for $T {
397            #[inline]
398            fn count_ones(self) -> u32 {
399                <$T>::count_ones(self)
400            }
401
402            #[inline]
403            fn count_zeros(self) -> u32 {
404                <$T>::count_zeros(self)
405            }
406
407            #[inline]
408            fn leading_ones(self) -> u32 {
409                <$T>::leading_ones(self)
410            }
411
412            #[inline]
413            fn leading_zeros(self) -> u32 {
414                <$T>::leading_zeros(self)
415            }
416
417            #[inline]
418            fn trailing_ones(self) -> u32 {
419                <$T>::trailing_ones(self)
420            }
421
422            #[inline]
423            fn trailing_zeros(self) -> u32 {
424                <$T>::trailing_zeros(self)
425            }
426
427            #[inline]
428            fn rotate_left(self, n: u32) -> Self {
429                <$T>::rotate_left(self, n)
430            }
431
432            #[inline]
433            fn rotate_right(self, n: u32) -> Self {
434                <$T>::rotate_right(self, n)
435            }
436
437            #[inline]
438            fn signed_shl(self, n: u32) -> Self {
439                ((self as $S) << n) as $T
440            }
441
442            #[inline]
443            fn signed_shr(self, n: u32) -> Self {
444                ((self as $S) >> n) as $T
445            }
446
447            #[inline]
448            fn unsigned_shl(self, n: u32) -> Self {
449                ((self as $U) << n) as $T
450            }
451
452            #[inline]
453            fn unsigned_shr(self, n: u32) -> Self {
454                ((self as $U) >> n) as $T
455            }
456
457            #[inline]
458            fn swap_bytes(self) -> Self {
459                <$T>::swap_bytes(self)
460            }
461
462            #[inline]
463            fn reverse_bits(self) -> Self {
464                <$T>::reverse_bits(self)
465            }
466
467            #[inline]
468            fn from_be(x: Self) -> Self {
469                <$T>::from_be(x)
470            }
471
472            #[inline]
473            fn from_le(x: Self) -> Self {
474                <$T>::from_le(x)
475            }
476
477            #[inline]
478            fn to_be(self) -> Self {
479                <$T>::to_be(self)
480            }
481
482            #[inline]
483            fn to_le(self) -> Self {
484                <$T>::to_le(self)
485            }
486
487            #[inline]
488            fn pow(self, exp: u32) -> Self {
489                <$T>::pow(self, exp)
490            }
491        }
492    };
493}
494
495// prim_int_impl!(type, signed, unsigned);
496prim_int_impl!(u8, i8, u8);
497prim_int_impl!(u16, i16, u16);
498prim_int_impl!(u32, i32, u32);
499prim_int_impl!(u64, i64, u64);
500prim_int_impl!(u128, i128, u128);
501prim_int_impl!(usize, isize, usize);
502prim_int_impl!(i8, i8, u8);
503prim_int_impl!(i16, i16, u16);
504prim_int_impl!(i32, i32, u32);
505prim_int_impl!(i64, i64, u64);
506prim_int_impl!(i128, i128, u128);
507prim_int_impl!(isize, isize, usize);
508
509#[cfg(test)]
510mod tests {
511    use crate::int::PrimInt;
512
513    #[test]
514    pub fn reverse_bits() {
515        use core::{i16, i32, i64, i8};
516
517        assert_eq!(
518            PrimInt::reverse_bits(0x0123_4567_89ab_cdefu64),
519            0xf7b3_d591_e6a2_c480
520        );
521
522        assert_eq!(PrimInt::reverse_bits(0i8), 0);
523        assert_eq!(PrimInt::reverse_bits(-1i8), -1);
524        assert_eq!(PrimInt::reverse_bits(1i8), i8::MIN);
525        assert_eq!(PrimInt::reverse_bits(i8::MIN), 1);
526        assert_eq!(PrimInt::reverse_bits(-2i8), i8::MAX);
527        assert_eq!(PrimInt::reverse_bits(i8::MAX), -2);
528
529        assert_eq!(PrimInt::reverse_bits(0i16), 0);
530        assert_eq!(PrimInt::reverse_bits(-1i16), -1);
531        assert_eq!(PrimInt::reverse_bits(1i16), i16::MIN);
532        assert_eq!(PrimInt::reverse_bits(i16::MIN), 1);
533        assert_eq!(PrimInt::reverse_bits(-2i16), i16::MAX);
534        assert_eq!(PrimInt::reverse_bits(i16::MAX), -2);
535
536        assert_eq!(PrimInt::reverse_bits(0i32), 0);
537        assert_eq!(PrimInt::reverse_bits(-1i32), -1);
538        assert_eq!(PrimInt::reverse_bits(1i32), i32::MIN);
539        assert_eq!(PrimInt::reverse_bits(i32::MIN), 1);
540        assert_eq!(PrimInt::reverse_bits(-2i32), i32::MAX);
541        assert_eq!(PrimInt::reverse_bits(i32::MAX), -2);
542
543        assert_eq!(PrimInt::reverse_bits(0i64), 0);
544        assert_eq!(PrimInt::reverse_bits(-1i64), -1);
545        assert_eq!(PrimInt::reverse_bits(1i64), i64::MIN);
546        assert_eq!(PrimInt::reverse_bits(i64::MIN), 1);
547        assert_eq!(PrimInt::reverse_bits(-2i64), i64::MAX);
548        assert_eq!(PrimInt::reverse_bits(i64::MAX), -2);
549    }
550
551    #[test]
552    pub fn reverse_bits_i128() {
553        use core::i128;
554
555        assert_eq!(PrimInt::reverse_bits(0i128), 0);
556        assert_eq!(PrimInt::reverse_bits(-1i128), -1);
557        assert_eq!(PrimInt::reverse_bits(1i128), i128::MIN);
558        assert_eq!(PrimInt::reverse_bits(i128::MIN), 1);
559        assert_eq!(PrimInt::reverse_bits(-2i128), i128::MAX);
560        assert_eq!(PrimInt::reverse_bits(i128::MAX), -2);
561    }
562}
num_traits/int.rs

num_traits/
int.rs
