1 use core::ops::{BitAnd, BitOr, BitXor, Not, Shl, Shr};
2
3 use bounds::Bounded;
4 use ops::checked::*;
5 use ops::saturating::Saturating;
6 use {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.
34 pub 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 /// ```
count_ones(self) -> u3266 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 /// ```
count_zeros(self) -> u3279 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 /// ```
leading_ones(self) -> u3293 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 /// ```
leading_zeros(self) -> u32109 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 /// ```
trailing_ones(self) -> u32123 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 /// ```
trailing_zeros(self) -> u32139 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 /// ```
rotate_left(self, n: u32) -> Self154 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 /// ```
rotate_right(self, n: u32) -> Self169 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 /// ```
signed_shl(self, n: u32) -> Self186 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 /// ```
signed_shr(self, n: u32) -> Self203 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 /// ```
unsigned_shl(self, n: u32) -> Self220 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 /// ```
unsigned_shr(self, n: u32) -> Self237 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 /// ```
swap_bytes(self) -> Self251 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 /// ```
reverse_bits(self) -> Self269 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 /// ```
from_be(x: Self) -> Self290 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 /// ```
from_le(x: Self) -> Self309 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 /// ```
to_be(self) -> Self328 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 /// ```
to_le(self) -> Self347 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 /// ```
pow(self, exp: u32) -> Self358 fn pow(self, exp: u32) -> Self;
359 }
360
one_per_byte<P: PrimInt>() -> P361 fn 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
reverse_bits_fallback<P: PrimInt>(i: P) -> P377 fn 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
394 macro_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 #[cfg(has_leading_trailing_ones)]
408 #[inline]
409 fn leading_ones(self) -> u32 {
410 <$T>::leading_ones(self)
411 }
412
413 #[inline]
414 fn leading_zeros(self) -> u32 {
415 <$T>::leading_zeros(self)
416 }
417
418 #[cfg(has_leading_trailing_ones)]
419 #[inline]
420 fn trailing_ones(self) -> u32 {
421 <$T>::trailing_ones(self)
422 }
423
424 #[inline]
425 fn trailing_zeros(self) -> u32 {
426 <$T>::trailing_zeros(self)
427 }
428
429 #[inline]
430 fn rotate_left(self, n: u32) -> Self {
431 <$T>::rotate_left(self, n)
432 }
433
434 #[inline]
435 fn rotate_right(self, n: u32) -> Self {
436 <$T>::rotate_right(self, n)
437 }
438
439 #[inline]
440 fn signed_shl(self, n: u32) -> Self {
441 ((self as $S) << n) as $T
442 }
443
444 #[inline]
445 fn signed_shr(self, n: u32) -> Self {
446 ((self as $S) >> n) as $T
447 }
448
449 #[inline]
450 fn unsigned_shl(self, n: u32) -> Self {
451 ((self as $U) << n) as $T
452 }
453
454 #[inline]
455 fn unsigned_shr(self, n: u32) -> Self {
456 ((self as $U) >> n) as $T
457 }
458
459 #[inline]
460 fn swap_bytes(self) -> Self {
461 <$T>::swap_bytes(self)
462 }
463
464 #[cfg(has_reverse_bits)]
465 #[inline]
466 fn reverse_bits(self) -> Self {
467 <$T>::reverse_bits(self)
468 }
469
470 #[inline]
471 fn from_be(x: Self) -> Self {
472 <$T>::from_be(x)
473 }
474
475 #[inline]
476 fn from_le(x: Self) -> Self {
477 <$T>::from_le(x)
478 }
479
480 #[inline]
481 fn to_be(self) -> Self {
482 <$T>::to_be(self)
483 }
484
485 #[inline]
486 fn to_le(self) -> Self {
487 <$T>::to_le(self)
488 }
489
490 #[inline]
491 fn pow(self, exp: u32) -> Self {
492 <$T>::pow(self, exp)
493 }
494 }
495 };
496 }
497
498 // prim_int_impl!(type, signed, unsigned);
499 prim_int_impl!(u8, i8, u8);
500 prim_int_impl!(u16, i16, u16);
501 prim_int_impl!(u32, i32, u32);
502 prim_int_impl!(u64, i64, u64);
503 #[cfg(has_i128)]
504 prim_int_impl!(u128, i128, u128);
505 prim_int_impl!(usize, isize, usize);
506 prim_int_impl!(i8, i8, u8);
507 prim_int_impl!(i16, i16, u16);
508 prim_int_impl!(i32, i32, u32);
509 prim_int_impl!(i64, i64, u64);
510 #[cfg(has_i128)]
511 prim_int_impl!(i128, i128, u128);
512 prim_int_impl!(isize, isize, usize);
513
514 #[cfg(test)]
515 mod tests {
516 use int::PrimInt;
517
518 #[test]
reverse_bits()519 pub fn reverse_bits() {
520 use core::{i16, i32, i64, i8};
521
522 assert_eq!(
523 PrimInt::reverse_bits(0x0123_4567_89ab_cdefu64),
524 0xf7b3_d591_e6a2_c480
525 );
526
527 assert_eq!(PrimInt::reverse_bits(0i8), 0);
528 assert_eq!(PrimInt::reverse_bits(-1i8), -1);
529 assert_eq!(PrimInt::reverse_bits(1i8), i8::MIN);
530 assert_eq!(PrimInt::reverse_bits(i8::MIN), 1);
531 assert_eq!(PrimInt::reverse_bits(-2i8), i8::MAX);
532 assert_eq!(PrimInt::reverse_bits(i8::MAX), -2);
533
534 assert_eq!(PrimInt::reverse_bits(0i16), 0);
535 assert_eq!(PrimInt::reverse_bits(-1i16), -1);
536 assert_eq!(PrimInt::reverse_bits(1i16), i16::MIN);
537 assert_eq!(PrimInt::reverse_bits(i16::MIN), 1);
538 assert_eq!(PrimInt::reverse_bits(-2i16), i16::MAX);
539 assert_eq!(PrimInt::reverse_bits(i16::MAX), -2);
540
541 assert_eq!(PrimInt::reverse_bits(0i32), 0);
542 assert_eq!(PrimInt::reverse_bits(-1i32), -1);
543 assert_eq!(PrimInt::reverse_bits(1i32), i32::MIN);
544 assert_eq!(PrimInt::reverse_bits(i32::MIN), 1);
545 assert_eq!(PrimInt::reverse_bits(-2i32), i32::MAX);
546 assert_eq!(PrimInt::reverse_bits(i32::MAX), -2);
547
548 assert_eq!(PrimInt::reverse_bits(0i64), 0);
549 assert_eq!(PrimInt::reverse_bits(-1i64), -1);
550 assert_eq!(PrimInt::reverse_bits(1i64), i64::MIN);
551 assert_eq!(PrimInt::reverse_bits(i64::MIN), 1);
552 assert_eq!(PrimInt::reverse_bits(-2i64), i64::MAX);
553 assert_eq!(PrimInt::reverse_bits(i64::MAX), -2);
554 }
555
556 #[test]
557 #[cfg(has_i128)]
reverse_bits_i128()558 pub fn reverse_bits_i128() {
559 use core::i128;
560
561 assert_eq!(PrimInt::reverse_bits(0i128), 0);
562 assert_eq!(PrimInt::reverse_bits(-1i128), -1);
563 assert_eq!(PrimInt::reverse_bits(1i128), i128::MIN);
564 assert_eq!(PrimInt::reverse_bits(i128::MIN), 1);
565 assert_eq!(PrimInt::reverse_bits(-2i128), i128::MAX);
566 assert_eq!(PrimInt::reverse_bits(i128::MAX), -2);
567 }
568 }
569