src/libcore/num/mod.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Numeric traits and functions for the built-in numeric types.
  12
  13 #![stable(feature = "rust1", since = "1.0.0")]
  14 #![allow(missing_docs)]
  15
  16 use self::wrapping::OverflowingOps;
  17
  18 use char::CharExt;
  19 use cmp::{Eq, PartialOrd};
  20 use convert::From;
  21 use fmt;
  22 use intrinsics;
  23 use marker::{Copy, Sized};
  24 use mem::size_of;
  25 use option::Option::{self, Some, None};
  26 use result::Result::{self, Ok, Err};
  27 use str::{FromStr, StrExt};
  28 use slice::SliceExt;
  29
  30 /// Provides intentionally-wrapped arithmetic on `T`.
  31 ///
  32 /// Operations like `+` on `u32` values is intended to never overflow,
  33 /// and in some debug configurations overflow is detected and results
  34 /// in a panic. While most arithmetic falls into this category, some
  35 /// code explicitly expects and relies upon modular arithmetic (e.g.,
  36 /// hashing).
  37 ///
  38 /// Wrapping arithmetic can be achieved either through methods like
  39 /// `wrapping_add`, or through the `Wrapping<T>` type, which says that
  40 /// all standard arithmetic operations on the underlying value are
  41 /// intended to have wrapping semantics.
  42 #[stable(feature = "rust1", since = "1.0.0")]
  43 #[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Debug, Default)]
  44 pub struct Wrapping<T>(#[stable(feature = "rust1", since = "1.0.0")] pub T);
  45
  46 pub mod wrapping;
  47
  48 // All these modules are technically private and only exposed for libcoretest:
  49 pub mod flt2dec;
  50 pub mod dec2flt;
  51 pub mod bignum;
  52 pub mod diy_float;
  53
  54 /// Types that have a "zero" value.
  55 ///
  56 /// This trait is intended for use in conjunction with `Add`, as an identity:
  57 /// `x + T::zero() == x`.
  58 #[unstable(feature = "zero_one",
  59            reason = "unsure of placement, wants to use associated constants",
  60            issue = "27739")]
  61 pub trait Zero: Sized {
  62     /// The "zero" (usually, additive identity) for this type.
  63     fn zero() -> Self;
  64 }
  65
  66 /// Types that have a "one" value.
  67 ///
  68 /// This trait is intended for use in conjunction with `Mul`, as an identity:
  69 /// `x * T::one() == x`.
  70 #[unstable(feature = "zero_one",
  71            reason = "unsure of placement, wants to use associated constants",
  72            issue = "27739")]
  73 pub trait One: Sized {
  74     /// The "one" (usually, multiplicative identity) for this type.
  75     fn one() -> Self;
  76 }
  77
  78 macro_rules! zero_one_impl {
  79     ($($t:ty)*) => ($(
  80         impl Zero for $t {
  81             #[inline]
  82             fn zero() -> Self { 0 }
  83         }
  84         impl One for $t {
  85             #[inline]
  86             fn one() -> Self { 1 }
  87         }
  88     )*)
  89 }
  90 zero_one_impl! { u8 u16 u32 u64 usize i8 i16 i32 i64 isize }
  91
  92 macro_rules! zero_one_impl_float {
  93     ($($t:ty)*) => ($(
  94         impl Zero for $t {
  95             #[inline]
  96             fn zero() -> Self { 0.0 }
  97         }
  98         impl One for $t {
  99             #[inline]
 100             fn one() -> Self { 1.0 }
 101         }
 102     )*)
 103 }
 104 zero_one_impl_float! { f32 f64 }
 105
 106 // Just for stage0; a byte swap on a byte is a no-op
 107 // Delete this once it becomes unused
 108 #[cfg(stage0)]
 109 unsafe fn bswap8(x: u8) -> u8 { x }
 110
 111 macro_rules! checked_op {
 112     ($U:ty, $op:path, $x:expr, $y:expr) => {{
 113         let (result, overflowed) = unsafe { $op($x as $U, $y as $U) };
 114         if overflowed { None } else { Some(result as Self) }
 115     }}
 116 }
 117
 118 // `Int` + `SignedInt` implemented for signed integers
 119 macro_rules! int_impl {
 120     ($ActualT:ty, $UnsignedT:ty, $BITS:expr,
 121      $add_with_overflow:path,
 122      $sub_with_overflow:path,
 123      $mul_with_overflow:path) => {
 124         /// Returns the smallest value that can be represented by this integer type.
 125         #[stable(feature = "rust1", since = "1.0.0")]
 126         #[inline]
 127         pub fn min_value() -> Self {
 128             (-1 as Self) << ($BITS - 1)
 129         }
 130
 131         /// Returns the largest value that can be represented by this integer type.
 132         #[stable(feature = "rust1", since = "1.0.0")]
 133         #[inline]
 134         pub fn max_value() -> Self {
 135             let min = Self::min_value(); !min
 136         }
 137
 138         /// Converts a string slice in a given base to an integer.
 139         ///
 140         /// Leading and trailing whitespace represent an error.
 141         ///
 142         /// # Examples
 143         ///
 144         /// ```
 145         /// assert_eq!(u32::from_str_radix("A", 16), Ok(10));
 146         /// ```
 147         #[stable(feature = "rust1", since = "1.0.0")]
 148         pub fn from_str_radix(src: &str, radix: u32) -> Result<Self, ParseIntError> {
 149             from_str_radix(src, radix)
 150         }
 151
 152         /// Returns the number of ones in the binary representation of `self`.
 153         ///
 154         /// # Examples
 155         ///
 156         /// ```rust
 157         /// let n = 0b01001100u8;
 158         ///
 159         /// assert_eq!(n.count_ones(), 3);
 160         /// ```
 161         #[stable(feature = "rust1", since = "1.0.0")]
 162         #[inline]
 163         pub fn count_ones(self) -> u32 { (self as $UnsignedT).count_ones() }
 164
 165         /// Returns the number of zeros in the binary representation of `self`.
 166         ///
 167         /// # Examples
 168         ///
 169         /// ```rust
 170         /// let n = 0b01001100u8;
 171         ///
 172         /// assert_eq!(n.count_zeros(), 5);
 173         /// ```
 174         #[stable(feature = "rust1", since = "1.0.0")]
 175         #[inline]
 176         pub fn count_zeros(self) -> u32 {
 177             (!self).count_ones()
 178         }
 179
 180         /// Returns the number of leading zeros in the binary representation
 181         /// of `self`.
 182         ///
 183         /// # Examples
 184         ///
 185         /// ```rust
 186         /// let n = 0b0101000u16;
 187         ///
 188         /// assert_eq!(n.leading_zeros(), 10);
 189         /// ```
 190         #[stable(feature = "rust1", since = "1.0.0")]
 191         #[inline]
 192         pub fn leading_zeros(self) -> u32 {
 193             (self as $UnsignedT).leading_zeros()
 194         }
 195
 196         /// Returns the number of trailing zeros in the binary representation
 197         /// of `self`.
 198         ///
 199         /// # Examples
 200         ///
 201         /// ```rust
 202         /// let n = 0b0101000u16;
 203         ///
 204         /// assert_eq!(n.trailing_zeros(), 3);
 205         /// ```
 206         #[stable(feature = "rust1", since = "1.0.0")]
 207         #[inline]
 208         pub fn trailing_zeros(self) -> u32 {
 209             (self as $UnsignedT).trailing_zeros()
 210         }
 211
 212         /// Shifts the bits to the left by a specified amount, `n`,
 213         /// wrapping the truncated bits to the end of the resulting integer.
 214         ///
 215         /// # Examples
 216         ///
 217         /// ```rust
 218         /// let n = 0x0123456789ABCDEFu64;
 219         /// let m = 0x3456789ABCDEF012u64;
 220         ///
 221         /// assert_eq!(n.rotate_left(12), m);
 222         /// ```
 223         #[stable(feature = "rust1", since = "1.0.0")]
 224         #[inline]
 225         pub fn rotate_left(self, n: u32) -> Self {
 226             (self as $UnsignedT).rotate_left(n) as Self
 227         }
 228
 229         /// Shifts the bits to the right by a specified amount, `n`,
 230         /// wrapping the truncated bits to the beginning of the resulting
 231         /// integer.
 232         ///
 233         /// # Examples
 234         ///
 235         /// ```rust
 236         /// let n = 0x0123456789ABCDEFu64;
 237         /// let m = 0xDEF0123456789ABCu64;
 238         ///
 239         /// assert_eq!(n.rotate_right(12), m);
 240         /// ```
 241         #[stable(feature = "rust1", since = "1.0.0")]
 242         #[inline]
 243         pub fn rotate_right(self, n: u32) -> Self {
 244             (self as $UnsignedT).rotate_right(n) as Self
 245         }
 246
 247         /// Reverses the byte order of the integer.
 248         ///
 249         /// # Examples
 250         ///
 251         /// ```rust
 252         /// let n = 0x0123456789ABCDEFu64;
 253         /// let m = 0xEFCDAB8967452301u64;
 254         ///
 255         /// assert_eq!(n.swap_bytes(), m);
 256         /// ```
 257         #[stable(feature = "rust1", since = "1.0.0")]
 258         #[inline]
 259         pub fn swap_bytes(self) -> Self {
 260             (self as $UnsignedT).swap_bytes() as Self
 261         }
 262
 263         /// Converts an integer from big endian to the target's endianness.
 264         ///
 265         /// On big endian this is a no-op. On little endian the bytes are
 266         /// swapped.
 267         ///
 268         /// # Examples
 269         ///
 270         /// ```rust
 271         /// let n = 0x0123456789ABCDEFu64;
 272         ///
 273         /// if cfg!(target_endian = "big") {
 274         ///     assert_eq!(u64::from_be(n), n)
 275         /// } else {
 276         ///     assert_eq!(u64::from_be(n), n.swap_bytes())
 277         /// }
 278         /// ```
 279         #[stable(feature = "rust1", since = "1.0.0")]
 280         #[inline]
 281         pub fn from_be(x: Self) -> Self {
 282             if cfg!(target_endian = "big") { x } else { x.swap_bytes() }
 283         }
 284
 285         /// Converts an integer from little endian to the target's endianness.
 286         ///
 287         /// On little endian this is a no-op. On big endian the bytes are
 288         /// swapped.
 289         ///
 290         /// # Examples
 291         ///
 292         /// ```rust
 293         /// let n = 0x0123456789ABCDEFu64;
 294         ///
 295         /// if cfg!(target_endian = "little") {
 296         ///     assert_eq!(u64::from_le(n), n)
 297         /// } else {
 298         ///     assert_eq!(u64::from_le(n), n.swap_bytes())
 299         /// }
 300         /// ```
 301         #[stable(feature = "rust1", since = "1.0.0")]
 302         #[inline]
 303         pub fn from_le(x: Self) -> Self {
 304             if cfg!(target_endian = "little") { x } else { x.swap_bytes() }
 305         }
 306
 307         /// Converts `self` to big endian from the target's endianness.
 308         ///
 309         /// On big endian this is a no-op. On little endian the bytes are
 310         /// swapped.
 311         ///
 312         /// # Examples
 313         ///
 314         /// ```rust
 315         /// let n = 0x0123456789ABCDEFu64;
 316         ///
 317         /// if cfg!(target_endian = "big") {
 318         ///     assert_eq!(n.to_be(), n)
 319         /// } else {
 320         ///     assert_eq!(n.to_be(), n.swap_bytes())
 321         /// }
 322         /// ```
 323         #[stable(feature = "rust1", since = "1.0.0")]
 324         #[inline]
 325         pub fn to_be(self) -> Self { // or not to be?
 326             if cfg!(target_endian = "big") { self } else { self.swap_bytes() }
 327         }
 328
 329         /// Converts `self` to little endian from the target's endianness.
 330         ///
 331         /// On little endian this is a no-op. On big endian the bytes are
 332         /// swapped.
 333         ///
 334         /// # Examples
 335         ///
 336         /// ```rust
 337         /// let n = 0x0123456789ABCDEFu64;
 338         ///
 339         /// if cfg!(target_endian = "little") {
 340         ///     assert_eq!(n.to_le(), n)
 341         /// } else {
 342         ///     assert_eq!(n.to_le(), n.swap_bytes())
 343         /// }
 344         /// ```
 345         #[stable(feature = "rust1", since = "1.0.0")]
 346         #[inline]
 347         pub fn to_le(self) -> Self {
 348             if cfg!(target_endian = "little") { self } else { self.swap_bytes() }
 349         }
 350
 351         /// Checked integer addition. Computes `self + other`, returning `None`
 352         /// if overflow occurred.
 353         ///
 354         /// # Examples
 355         ///
 356         /// ```rust
 357         /// assert_eq!(5u16.checked_add(65530), Some(65535));
 358         /// assert_eq!(6u16.checked_add(65530), None);
 359         /// ```
 360         #[stable(feature = "rust1", since = "1.0.0")]
 361         #[inline]
 362         pub fn checked_add(self, other: Self) -> Option<Self> {
 363             checked_op!($ActualT, $add_with_overflow, self, other)
 364         }
 365
 366         /// Checked integer subtraction. Computes `self - other`, returning
 367         /// `None` if underflow occurred.
 368         ///
 369         /// # Examples
 370         ///
 371         /// ```rust
 372         /// assert_eq!((-127i8).checked_sub(1), Some(-128));
 373         /// assert_eq!((-128i8).checked_sub(1), None);
 374         /// ```
 375         #[stable(feature = "rust1", since = "1.0.0")]
 376         #[inline]
 377         pub fn checked_sub(self, other: Self) -> Option<Self> {
 378             checked_op!($ActualT, $sub_with_overflow, self, other)
 379         }
 380
 381         /// Checked integer multiplication. Computes `self * other`, returning
 382         /// `None` if underflow or overflow occurred.
 383         ///
 384         /// # Examples
 385         ///
 386         /// ```rust
 387         /// assert_eq!(5u8.checked_mul(51), Some(255));
 388         /// assert_eq!(5u8.checked_mul(52), None);
 389         /// ```
 390         #[stable(feature = "rust1", since = "1.0.0")]
 391         #[inline]
 392         pub fn checked_mul(self, other: Self) -> Option<Self> {
 393             checked_op!($ActualT, $mul_with_overflow, self, other)
 394         }
 395
 396         /// Checked integer division. Computes `self / other`, returning `None`
 397         /// if `other == 0` or the operation results in underflow or overflow.
 398         ///
 399         /// # Examples
 400         ///
 401         /// ```rust
 402         /// assert_eq!((-127i8).checked_div(-1), Some(127));
 403         /// assert_eq!((-128i8).checked_div(-1), None);
 404         /// assert_eq!((1i8).checked_div(0), None);
 405         /// ```
 406         #[stable(feature = "rust1", since = "1.0.0")]
 407         #[inline]
 408         pub fn checked_div(self, other: Self) -> Option<Self> {
 409             match other {
 410                 0    => None,
 411                -1 if self == Self::min_value()
 412                      => None,
 413                other => Some(self / other),
 414             }
 415         }
 416
 417         /// Saturating integer addition. Computes `self + other`, saturating at
 418         /// the numeric bounds instead of overflowing.
 419         #[stable(feature = "rust1", since = "1.0.0")]
 420         #[inline]
 421         pub fn saturating_add(self, other: Self) -> Self {
 422             match self.checked_add(other) {
 423                 Some(x)                       => x,
 424                 None if other >= Self::zero() => Self::max_value(),
 425                 None => Self::min_value(),
 426             }
 427         }
 428
 429         /// Saturating integer subtraction. Computes `self - other`, saturating
 430         /// at the numeric bounds instead of overflowing.
 431         #[stable(feature = "rust1", since = "1.0.0")]
 432         #[inline]
 433         pub fn saturating_sub(self, other: Self) -> Self {
 434             match self.checked_sub(other) {
 435                 Some(x)                      => x,
 436                 None if other >= Self::zero() => Self::min_value(),
 437                 None => Self::max_value(),
 438             }
 439         }
 440
 441         /// Wrapping (modular) addition. Computes `self + other`,
 442         /// wrapping around at the boundary of the type.
 443         #[stable(feature = "rust1", since = "1.0.0")]
 444         #[inline]
 445         pub fn wrapping_add(self, rhs: Self) -> Self {
 446             unsafe {
 447                 intrinsics::overflowing_add(self, rhs)
 448             }
 449         }
 450
 451         /// Wrapping (modular) subtraction. Computes `self - other`,
 452         /// wrapping around at the boundary of the type.
 453         #[stable(feature = "rust1", since = "1.0.0")]
 454         #[inline]
 455         pub fn wrapping_sub(self, rhs: Self) -> Self {
 456             unsafe {
 457                 intrinsics::overflowing_sub(self, rhs)
 458             }
 459         }
 460
 461         /// Wrapping (modular) multiplication. Computes `self *
 462         /// other`, wrapping around at the boundary of the type.
 463         #[stable(feature = "rust1", since = "1.0.0")]
 464         #[inline]
 465         pub fn wrapping_mul(self, rhs: Self) -> Self {
 466             unsafe {
 467                 intrinsics::overflowing_mul(self, rhs)
 468             }
 469         }
 470
 471         /// Wrapping (modular) division. Computes `self / other`,
 472         /// wrapping around at the boundary of the type.
 473         ///
 474         /// The only case where such wrapping can occur is when one
 475         /// divides `MIN / -1` on a signed type (where `MIN` is the
 476         /// negative minimal value for the type); this is equivalent
 477         /// to `-MIN`, a positive value that is too large to represent
 478         /// in the type. In such a case, this function returns `MIN`
 479         /// itself.
 480         #[stable(feature = "num_wrapping", since = "1.2.0")]
 481         #[inline(always)]
 482         pub fn wrapping_div(self, rhs: Self) -> Self {
 483             self.overflowing_div(rhs).0
 484         }
 485
 486         /// Wrapping (modular) remainder. Computes `self % other`,
 487         /// wrapping around at the boundary of the type.
 488         ///
 489         /// Such wrap-around never actually occurs mathematically;
 490         /// implementation artifacts make `x % y` invalid for `MIN /
 491         /// -1` on a signed type (where `MIN` is the negative
 492         /// minimal value). In such a case, this function returns `0`.
 493         #[stable(feature = "num_wrapping", since = "1.2.0")]
 494         #[inline(always)]
 495         pub fn wrapping_rem(self, rhs: Self) -> Self {
 496             self.overflowing_rem(rhs).0
 497         }
 498
 499         /// Wrapping (modular) negation. Computes `-self`,
 500         /// wrapping around at the boundary of the type.
 501         ///
 502         /// The only case where such wrapping can occur is when one
 503         /// negates `MIN` on a signed type (where `MIN` is the
 504         /// negative minimal value for the type); this is a positive
 505         /// value that is too large to represent in the type. In such
 506         /// a case, this function returns `MIN` itself.
 507         #[stable(feature = "num_wrapping", since = "1.2.0")]
 508         #[inline(always)]
 509         pub fn wrapping_neg(self) -> Self {
 510             self.overflowing_neg().0
 511         }
 512
 513         /// Panic-free bitwise shift-left; yields `self << mask(rhs)`,
 514         /// where `mask` removes any high-order bits of `rhs` that
 515         /// would cause the shift to exceed the bitwidth of the type.
 516         #[stable(feature = "num_wrapping", since = "1.2.0")]
 517         #[inline(always)]
 518         pub fn wrapping_shl(self, rhs: u32) -> Self {
 519             self.overflowing_shl(rhs).0
 520         }
 521
 522         /// Panic-free bitwise shift-left; yields `self >> mask(rhs)`,
 523         /// where `mask` removes any high-order bits of `rhs` that
 524         /// would cause the shift to exceed the bitwidth of the type.
 525         #[stable(feature = "num_wrapping", since = "1.2.0")]
 526         #[inline(always)]
 527         pub fn wrapping_shr(self, rhs: u32) -> Self {
 528             self.overflowing_shr(rhs).0
 529         }
 530
 531         /// Raises self to the power of `exp`, using exponentiation by squaring.
 532         ///
 533         /// # Examples
 534         ///
 535         /// ```
 536         /// let x: i32 = 2; // or any other integer type
 537         ///
 538         /// assert_eq!(x.pow(4), 16);
 539         /// ```
 540         #[stable(feature = "rust1", since = "1.0.0")]
 541         #[inline]
 542         pub fn pow(self, mut exp: u32) -> Self {
 543             let mut base = self;
 544             let mut acc = Self::one();
 545
 546             while exp > 1 {
 547                 if (exp & 1) == 1 {
 548                     acc = acc * base;
 549                 }
 550                 exp /= 2;
 551                 base = base * base;
 552             }
 553
 554             // Deal with the final bit of the exponent separately, since
 555             // squaring the base afterwards is not necessary and may cause a
 556             // needless overflow.
 557             if exp == 1 {
 558                 acc = acc * base;
 559             }
 560
 561             acc
 562         }
 563
 564         /// Computes the absolute value of `self`.
 565         ///
 566         /// # Overflow behavior
 567         ///
 568         /// The absolute value of `i32::min_value()` cannot be represented as an
 569         /// `i32`, and attempting to calculate it will cause an overflow. This
 570         /// means that code in debug mode will trigger a panic on this case and
 571         /// optimized code will return `i32::min_value()` without a panic.
 572         #[stable(feature = "rust1", since = "1.0.0")]
 573         #[inline]
 574         pub fn abs(self) -> Self {
 575             if self.is_negative() {
 576                 // Note that the #[inline] above means that the overflow
 577                 // semantics of this negation depend on the crate we're being
 578                 // inlined into.
 579                 -self
 580             } else {
 581                 self
 582             }
 583         }
 584
 585         /// Returns a number representing sign of `self`.
 586         ///
 587         /// - `0` if the number is zero
 588         /// - `1` if the number is positive
 589         /// - `-1` if the number is negative
 590         #[stable(feature = "rust1", since = "1.0.0")]
 591         #[inline]
 592         pub fn signum(self) -> Self {
 593             match self {
 594                 n if n > 0 =>  1,
 595                 0          =>  0,
 596                 _          => -1,
 597             }
 598         }
 599
 600         /// Returns `true` if `self` is positive and `false` if the number
 601         /// is zero or negative.
 602         #[stable(feature = "rust1", since = "1.0.0")]
 603         #[inline]
 604         pub fn is_positive(self) -> bool { self > 0 }
 605
 606         /// Returns `true` if `self` is negative and `false` if the number
 607         /// is zero or positive.
 608         #[stable(feature = "rust1", since = "1.0.0")]
 609         #[inline]
 610         pub fn is_negative(self) -> bool { self < 0 }
 611     }
 612 }
 613
 614 #[lang = "i8"]
 615 #[cfg(stage0)]
 616 impl i8 {
 617     int_impl! { i8, u8, 8,
 618         intrinsics::i8_add_with_overflow,
 619         intrinsics::i8_sub_with_overflow,
 620         intrinsics::i8_mul_with_overflow }
 621 }
 622 #[lang = "i8"]
 623 #[cfg(not(stage0))]
 624 impl i8 {
 625     int_impl! { i8, u8, 8,
 626         intrinsics::add_with_overflow,
 627         intrinsics::sub_with_overflow,
 628         intrinsics::mul_with_overflow }
 629 }
 630
 631 #[lang = "i16"]
 632 #[cfg(stage0)]
 633 impl i16 {
 634     int_impl! { i16, u16, 16,
 635         intrinsics::i16_add_with_overflow,
 636         intrinsics::i16_sub_with_overflow,
 637         intrinsics::i16_mul_with_overflow }
 638 }
 639 #[lang = "i16"]
 640 #[cfg(not(stage0))]
 641 impl i16 {
 642     int_impl! { i16, u16, 16,
 643         intrinsics::add_with_overflow,
 644         intrinsics::sub_with_overflow,
 645         intrinsics::mul_with_overflow }
 646 }
 647
 648 #[lang = "i32"]
 649 #[cfg(stage0)]
 650 impl i32 {
 651     int_impl! { i32, u32, 32,
 652         intrinsics::i32_add_with_overflow,
 653         intrinsics::i32_sub_with_overflow,
 654         intrinsics::i32_mul_with_overflow }
 655 }
 656 #[lang = "i32"]
 657 #[cfg(not(stage0))]
 658 impl i32 {
 659     int_impl! { i32, u32, 32,
 660         intrinsics::add_with_overflow,
 661         intrinsics::sub_with_overflow,
 662         intrinsics::mul_with_overflow }
 663 }
 664
 665 #[lang = "i64"]
 666 #[cfg(stage0)]
 667 impl i64 {
 668     int_impl! { i64, u64, 64,
 669         intrinsics::i64_add_with_overflow,
 670         intrinsics::i64_sub_with_overflow,
 671         intrinsics::i64_mul_with_overflow }
 672 }
 673 #[lang = "i64"]
 674 #[cfg(not(stage0))]
 675 impl i64 {
 676     int_impl! { i64, u64, 64,
 677         intrinsics::add_with_overflow,
 678         intrinsics::sub_with_overflow,
 679         intrinsics::mul_with_overflow }
 680 }
 681
 682 #[cfg(target_pointer_width = "32")]
 683 #[lang = "isize"]
 684 #[cfg(stage0)]
 685 impl isize {
 686     int_impl! { i32, u32, 32,
 687         intrinsics::i32_add_with_overflow,
 688         intrinsics::i32_sub_with_overflow,
 689         intrinsics::i32_mul_with_overflow }
 690 }
 691 #[cfg(target_pointer_width = "32")]
 692 #[lang = "isize"]
 693 #[cfg(not(stage0))]
 694 impl isize {
 695     int_impl! { i32, u32, 32,
 696         intrinsics::add_with_overflow,
 697         intrinsics::sub_with_overflow,
 698         intrinsics::mul_with_overflow }
 699 }
 700
 701 #[cfg(target_pointer_width = "64")]
 702 #[lang = "isize"]
 703 #[cfg(stage0)]
 704 impl isize {
 705     int_impl! { i64, u64, 64,
 706         intrinsics::i64_add_with_overflow,
 707         intrinsics::i64_sub_with_overflow,
 708         intrinsics::i64_mul_with_overflow }
 709 }
 710 #[cfg(target_pointer_width = "64")]
 711 #[lang = "isize"]
 712 #[cfg(not(stage0))]
 713 impl isize {
 714     int_impl! { i64, u64, 64,
 715         intrinsics::add_with_overflow,
 716         intrinsics::sub_with_overflow,
 717         intrinsics::mul_with_overflow }
 718 }
 719
 720 // `Int` + `UnsignedInt` implemented for signed integers
 721 macro_rules! uint_impl {
 722     ($ActualT:ty, $BITS:expr,
 723      $ctpop:path,
 724      $ctlz:path,
 725      $cttz:path,
 726      $bswap:path,
 727      $add_with_overflow:path,
 728      $sub_with_overflow:path,
 729      $mul_with_overflow:path) => {
 730         /// Returns the smallest value that can be represented by this integer type.
 731         #[stable(feature = "rust1", since = "1.0.0")]
 732         #[inline]
 733         pub fn min_value() -> Self { 0 }
 734
 735         /// Returns the largest value that can be represented by this integer type.
 736         #[stable(feature = "rust1", since = "1.0.0")]
 737         #[inline]
 738         pub fn max_value() -> Self { !0 }
 739
 740         /// Converts a string slice in a given base to an integer.
 741         ///
 742         /// Leading and trailing whitespace represent an error.
 743         ///
 744         /// # Arguments
 745         ///
 746         /// * src - A string slice
 747         /// * radix - The base to use. Must lie in the range [2 .. 36]
 748         ///
 749         /// # Return value
 750         ///
 751         /// `Err(ParseIntError)` if the string did not represent a valid number.
 752         /// Otherwise, `Ok(n)` where `n` is the integer represented by `src`.
 753         #[stable(feature = "rust1", since = "1.0.0")]
 754         pub fn from_str_radix(src: &str, radix: u32) -> Result<Self, ParseIntError> {
 755             from_str_radix(src, radix)
 756         }
 757
 758         /// Returns the number of ones in the binary representation of `self`.
 759         ///
 760         /// # Examples
 761         ///
 762         /// ```rust
 763         /// let n = 0b01001100u8;
 764         ///
 765         /// assert_eq!(n.count_ones(), 3);
 766         /// ```
 767         #[stable(feature = "rust1", since = "1.0.0")]
 768         #[inline]
 769         pub fn count_ones(self) -> u32 {
 770             unsafe { $ctpop(self as $ActualT) as u32 }
 771         }
 772
 773         /// Returns the number of zeros in the binary representation of `self`.
 774         ///
 775         /// # Examples
 776         ///
 777         /// ```rust
 778         /// let n = 0b01001100u8;
 779         ///
 780         /// assert_eq!(n.count_zeros(), 5);
 781         /// ```
 782         #[stable(feature = "rust1", since = "1.0.0")]
 783         #[inline]
 784         pub fn count_zeros(self) -> u32 {
 785             (!self).count_ones()
 786         }
 787
 788         /// Returns the number of leading zeros in the binary representation
 789         /// of `self`.
 790         ///
 791         /// # Examples
 792         ///
 793         /// ```rust
 794         /// let n = 0b0101000u16;
 795         ///
 796         /// assert_eq!(n.leading_zeros(), 10);
 797         /// ```
 798         #[stable(feature = "rust1", since = "1.0.0")]
 799         #[inline]
 800         pub fn leading_zeros(self) -> u32 {
 801             unsafe { $ctlz(self as $ActualT) as u32 }
 802         }
 803
 804         #[stable(feature = "rust1", since = "1.0.0")]
 805         #[cfg(stage0)]
 806         #[inline]
 807         pub fn trailing_zeros(self) -> u32 {
 808             // As of LLVM 3.6 the codegen for the zero-safe cttz8 intrinsic
 809             // emits two conditional moves on x86_64. By promoting the value to
 810             // u16 and setting bit 8, we get better code without any conditional
 811             // operations.
 812             // FIXME: There's a LLVM patch (http://reviews.llvm.org/D9284)
 813             // pending, remove this workaround once LLVM generates better code
 814             // for cttz8.
 815             unsafe {
 816                 if $BITS == 8 {
 817                     intrinsics::cttz16(self as u16 | 0x100) as u32
 818                 } else {
 819                     $cttz(self as $ActualT) as u32
 820                 }
 821             }
 822         }
 823         /// Returns the number of trailing zeros in the binary representation
 824         /// of `self`.
 825         ///
 826         /// # Examples
 827         ///
 828         /// ```rust
 829         /// let n = 0b0101000u16;
 830         ///
 831         /// assert_eq!(n.trailing_zeros(), 3);
 832         /// ```
 833         #[stable(feature = "rust1", since = "1.0.0")]
 834         #[cfg(not(stage0))]
 835         #[inline]
 836         pub fn trailing_zeros(self) -> u32 {
 837             // As of LLVM 3.6 the codegen for the zero-safe cttz8 intrinsic
 838             // emits two conditional moves on x86_64. By promoting the value to
 839             // u16 and setting bit 8, we get better code without any conditional
 840             // operations.
 841             // FIXME: There's a LLVM patch (http://reviews.llvm.org/D9284)
 842             // pending, remove this workaround once LLVM generates better code
 843             // for cttz8.
 844             unsafe {
 845                 if $BITS == 8 {
 846                     intrinsics::cttz(self as u16 | 0x100) as u32
 847                 } else {
 848                     intrinsics::cttz(self) as u32
 849                 }
 850             }
 851         }
 852
 853         /// Shifts the bits to the left by a specified amount, `n`,
 854         /// wrapping the truncated bits to the end of the resulting integer.
 855         ///
 856         /// # Examples
 857         ///
 858         /// ```rust
 859         /// let n = 0x0123456789ABCDEFu64;
 860         /// let m = 0x3456789ABCDEF012u64;
 861         ///
 862         /// assert_eq!(n.rotate_left(12), m);
 863         /// ```
 864         #[stable(feature = "rust1", since = "1.0.0")]
 865         #[inline]
 866         pub fn rotate_left(self, n: u32) -> Self {
 867             // Protect against undefined behaviour for over-long bit shifts
 868             let n = n % $BITS;
 869             (self << n) | (self >> (($BITS - n) % $BITS))
 870         }
 871
 872         /// Shifts the bits to the right by a specified amount, `n`,
 873         /// wrapping the truncated bits to the beginning of the resulting
 874         /// integer.
 875         ///
 876         /// # Examples
 877         ///
 878         /// ```rust
 879         /// let n = 0x0123456789ABCDEFu64;
 880         /// let m = 0xDEF0123456789ABCu64;
 881         ///
 882         /// assert_eq!(n.rotate_right(12), m);
 883         /// ```
 884         #[stable(feature = "rust1", since = "1.0.0")]
 885         #[inline]
 886         pub fn rotate_right(self, n: u32) -> Self {
 887             // Protect against undefined behaviour for over-long bit shifts
 888             let n = n % $BITS;
 889             (self >> n) | (self << (($BITS - n) % $BITS))
 890         }
 891
 892         /// Reverses the byte order of the integer.
 893         ///
 894         /// # Examples
 895         ///
 896         /// ```rust
 897         /// let n = 0x0123456789ABCDEFu64;
 898         /// let m = 0xEFCDAB8967452301u64;
 899         ///
 900         /// assert_eq!(n.swap_bytes(), m);
 901         /// ```
 902         #[stable(feature = "rust1", since = "1.0.0")]
 903         #[inline]
 904         pub fn swap_bytes(self) -> Self {
 905             unsafe { $bswap(self as $ActualT) as Self }
 906         }
 907
 908         /// Converts an integer from big endian to the target's endianness.
 909         ///
 910         /// On big endian this is a no-op. On little endian the bytes are
 911         /// swapped.
 912         ///
 913         /// # Examples
 914         ///
 915         /// ```rust
 916         /// let n = 0x0123456789ABCDEFu64;
 917         ///
 918         /// if cfg!(target_endian = "big") {
 919         ///     assert_eq!(u64::from_be(n), n)
 920         /// } else {
 921         ///     assert_eq!(u64::from_be(n), n.swap_bytes())
 922         /// }
 923         /// ```
 924         #[stable(feature = "rust1", since = "1.0.0")]
 925         #[inline]
 926         pub fn from_be(x: Self) -> Self {
 927             if cfg!(target_endian = "big") { x } else { x.swap_bytes() }
 928         }
 929
 930         /// Converts an integer from little endian to the target's endianness.
 931         ///
 932         /// On little endian this is a no-op. On big endian the bytes are
 933         /// swapped.
 934         ///
 935         /// # Examples
 936         ///
 937         /// ```rust
 938         /// let n = 0x0123456789ABCDEFu64;
 939         ///
 940         /// if cfg!(target_endian = "little") {
 941         ///     assert_eq!(u64::from_le(n), n)
 942         /// } else {
 943         ///     assert_eq!(u64::from_le(n), n.swap_bytes())
 944         /// }
 945         /// ```
 946         #[stable(feature = "rust1", since = "1.0.0")]
 947         #[inline]
 948         pub fn from_le(x: Self) -> Self {
 949             if cfg!(target_endian = "little") { x } else { x.swap_bytes() }
 950         }
 951
 952         /// Converts `self` to big endian from the target's endianness.
 953         ///
 954         /// On big endian this is a no-op. On little endian the bytes are
 955         /// swapped.
 956         ///
 957         /// # Examples
 958         ///
 959         /// ```rust
 960         /// let n = 0x0123456789ABCDEFu64;
 961         ///
 962         /// if cfg!(target_endian = "big") {
 963         ///     assert_eq!(n.to_be(), n)
 964         /// } else {
 965         ///     assert_eq!(n.to_be(), n.swap_bytes())
 966         /// }
 967         /// ```
 968         #[stable(feature = "rust1", since = "1.0.0")]
 969         #[inline]
 970         pub fn to_be(self) -> Self { // or not to be?
 971             if cfg!(target_endian = "big") { self } else { self.swap_bytes() }
 972         }
 973
 974         /// Converts `self` to little endian from the target's endianness.
 975         ///
 976         /// On little endian this is a no-op. On big endian the bytes are
 977         /// swapped.
 978         ///
 979         /// # Examples
 980         ///
 981         /// ```rust
 982         /// let n = 0x0123456789ABCDEFu64;
 983         ///
 984         /// if cfg!(target_endian = "little") {
 985         ///     assert_eq!(n.to_le(), n)
 986         /// } else {
 987         ///     assert_eq!(n.to_le(), n.swap_bytes())
 988         /// }
 989         /// ```
 990         #[stable(feature = "rust1", since = "1.0.0")]
 991         #[inline]
 992         pub fn to_le(self) -> Self {
 993             if cfg!(target_endian = "little") { self } else { self.swap_bytes() }
 994         }
 995
 996         /// Checked integer addition. Computes `self + other`, returning `None`
 997         /// if overflow occurred.
 998         ///
 999         /// # Examples
1000         ///
1001         /// ```rust
1002         /// assert_eq!(5u16.checked_add(65530), Some(65535));
1003         /// assert_eq!(6u16.checked_add(65530), None);
1004         /// ```
1005         #[stable(feature = "rust1", since = "1.0.0")]
1006         #[inline]
1007         pub fn checked_add(self, other: Self) -> Option<Self> {
1008             checked_op!($ActualT, $add_with_overflow, self, other)
1009         }
1010
1011         /// Checked integer subtraction. Computes `self - other`, returning
1012         /// `None` if underflow occurred.
1013         ///
1014         /// # Examples
1015         ///
1016         /// ```rust
1017         /// assert_eq!((-127i8).checked_sub(1), Some(-128));
1018         /// assert_eq!((-128i8).checked_sub(1), None);
1019         /// ```
1020         #[stable(feature = "rust1", since = "1.0.0")]
1021         #[inline]
1022         pub fn checked_sub(self, other: Self) -> Option<Self> {
1023             checked_op!($ActualT, $sub_with_overflow, self, other)
1024         }
1025
1026         /// Checked integer multiplication. Computes `self * other`, returning
1027         /// `None` if underflow or overflow occurred.
1028         ///
1029         /// # Examples
1030         ///
1031         /// ```rust
1032         /// assert_eq!(5u8.checked_mul(51), Some(255));
1033         /// assert_eq!(5u8.checked_mul(52), None);
1034         /// ```
1035         #[stable(feature = "rust1", since = "1.0.0")]
1036         #[inline]
1037         pub fn checked_mul(self, other: Self) -> Option<Self> {
1038             checked_op!($ActualT, $mul_with_overflow, self, other)
1039         }
1040
1041         /// Checked integer division. Computes `self / other`, returning `None`
1042         /// if `other == 0` or the operation results in underflow or overflow.
1043         ///
1044         /// # Examples
1045         ///
1046         /// ```rust
1047         /// assert_eq!((-127i8).checked_div(-1), Some(127));
1048         /// assert_eq!((-128i8).checked_div(-1), None);
1049         /// assert_eq!((1i8).checked_div(0), None);
1050         /// ```
1051         #[stable(feature = "rust1", since = "1.0.0")]
1052         #[inline]
1053         pub fn checked_div(self, other: Self) -> Option<Self> {
1054             match other {
1055                 0 => None,
1056                 other => Some(self / other),
1057             }
1058         }
1059
1060         /// Saturating integer addition. Computes `self + other`, saturating at
1061         /// the numeric bounds instead of overflowing.
1062         #[stable(feature = "rust1", since = "1.0.0")]
1063         #[inline]
1064         pub fn saturating_add(self, other: Self) -> Self {
1065             match self.checked_add(other) {
1066                 Some(x)                       => x,
1067                 None if other >= Self::zero() => Self::max_value(),
1068                 None => Self::min_value(),
1069             }
1070         }
1071
1072         /// Saturating integer subtraction. Computes `self - other`, saturating
1073         /// at the numeric bounds instead of overflowing.
1074         #[stable(feature = "rust1", since = "1.0.0")]
1075         #[inline]
1076         pub fn saturating_sub(self, other: Self) -> Self {
1077             match self.checked_sub(other) {
1078                 Some(x)                       => x,
1079                 None if other >= Self::zero() => Self::min_value(),
1080                 None => Self::max_value(),
1081             }
1082         }
1083
1084         /// Wrapping (modular) addition. Computes `self + other`,
1085         /// wrapping around at the boundary of the type.
1086         #[stable(feature = "rust1", since = "1.0.0")]
1087         #[inline]
1088         pub fn wrapping_add(self, rhs: Self) -> Self {
1089             unsafe {
1090                 intrinsics::overflowing_add(self, rhs)
1091             }
1092         }
1093
1094         /// Wrapping (modular) subtraction. Computes `self - other`,
1095         /// wrapping around at the boundary of the type.
1096         #[stable(feature = "rust1", since = "1.0.0")]
1097         #[inline]
1098         pub fn wrapping_sub(self, rhs: Self) -> Self {
1099             unsafe {
1100                 intrinsics::overflowing_sub(self, rhs)
1101             }
1102         }
1103
1104         /// Wrapping (modular) multiplication. Computes `self *
1105         /// other`, wrapping around at the boundary of the type.
1106         #[stable(feature = "rust1", since = "1.0.0")]
1107         #[inline]
1108         pub fn wrapping_mul(self, rhs: Self) -> Self {
1109             unsafe {
1110                 intrinsics::overflowing_mul(self, rhs)
1111             }
1112         }
1113
1114         /// Wrapping (modular) division. Computes `self / other`,
1115         /// wrapping around at the boundary of the type.
1116         ///
1117         /// The only case where such wrapping can occur is when one
1118         /// divides `MIN / -1` on a signed type (where `MIN` is the
1119         /// negative minimal value for the type); this is equivalent
1120         /// to `-MIN`, a positive value that is too large to represent
1121         /// in the type. In such a case, this function returns `MIN`
1122         /// itself.
1123         #[stable(feature = "num_wrapping", since = "1.2.0")]
1124         #[inline(always)]
1125         pub fn wrapping_div(self, rhs: Self) -> Self {
1126             self.overflowing_div(rhs).0
1127         }
1128
1129         /// Wrapping (modular) remainder. Computes `self % other`,
1130         /// wrapping around at the boundary of the type.
1131         ///
1132         /// Such wrap-around never actually occurs mathematically;
1133         /// implementation artifacts make `x % y` invalid for `MIN /
1134         /// -1` on a signed type (where `MIN` is the negative
1135         /// minimal value). In such a case, this function returns `0`.
1136         #[stable(feature = "num_wrapping", since = "1.2.0")]
1137         #[inline(always)]
1138         pub fn wrapping_rem(self, rhs: Self) -> Self {
1139             self.overflowing_rem(rhs).0
1140         }
1141
1142         /// Wrapping (modular) negation. Computes `-self`,
1143         /// wrapping around at the boundary of the type.
1144         ///
1145         /// The only case where such wrapping can occur is when one
1146         /// negates `MIN` on a signed type (where `MIN` is the
1147         /// negative minimal value for the type); this is a positive
1148         /// value that is too large to represent in the type. In such
1149         /// a case, this function returns `MIN` itself.
1150         #[stable(feature = "num_wrapping", since = "1.2.0")]
1151         #[inline(always)]
1152         pub fn wrapping_neg(self) -> Self {
1153             self.overflowing_neg().0
1154         }
1155
1156         /// Panic-free bitwise shift-left; yields `self << mask(rhs)`,
1157         /// where `mask` removes any high-order bits of `rhs` that
1158         /// would cause the shift to exceed the bitwidth of the type.
1159         #[stable(feature = "num_wrapping", since = "1.2.0")]
1160         #[inline(always)]
1161         pub fn wrapping_shl(self, rhs: u32) -> Self {
1162             self.overflowing_shl(rhs).0
1163         }
1164
1165         /// Panic-free bitwise shift-left; yields `self >> mask(rhs)`,
1166         /// where `mask` removes any high-order bits of `rhs` that
1167         /// would cause the shift to exceed the bitwidth of the type.
1168         #[stable(feature = "num_wrapping", since = "1.2.0")]
1169         #[inline(always)]
1170         pub fn wrapping_shr(self, rhs: u32) -> Self {
1171             self.overflowing_shr(rhs).0
1172         }
1173
1174         /// Raises self to the power of `exp`, using exponentiation by squaring.
1175         ///
1176         /// # Examples
1177         ///
1178         /// ```rust
1179         /// assert_eq!(2i32.pow(4), 16);
1180         /// ```
1181         #[stable(feature = "rust1", since = "1.0.0")]
1182         #[inline]
1183         pub fn pow(self, mut exp: u32) -> Self {
1184             let mut base = self;
1185             let mut acc = Self::one();
1186
1187             let mut prev_base = self;
1188             let mut base_oflo = false;
1189             while exp > 0 {
1190                 if (exp & 1) == 1 {
1191                     if base_oflo {
1192                         // ensure overflow occurs in the same manner it
1193                         // would have otherwise (i.e. signal any exception
1194                         // it would have otherwise).
1195                         acc = acc * (prev_base * prev_base);
1196                     } else {
1197                         acc = acc * base;
1198                     }
1199                 }
1200                 prev_base = base;
1201                 let (new_base, new_base_oflo) = base.overflowing_mul(base);
1202                 base = new_base;
1203                 base_oflo = new_base_oflo;
1204                 exp /= 2;
1205             }
1206             acc
1207         }
1208
1209         /// Returns `true` if and only if `self == 2^k` for some `k`.
1210         #[stable(feature = "rust1", since = "1.0.0")]
1211         #[inline]
1212         pub fn is_power_of_two(self) -> bool {
1213             (self.wrapping_sub(Self::one())) & self == Self::zero() &&
1214                 !(self == Self::zero())
1215         }
1216
1217         /// Returns the smallest power of two greater than or equal to `self`.
1218         /// Unspecified behavior on overflow.
1219         #[stable(feature = "rust1", since = "1.0.0")]
1220         #[inline]
1221         pub fn next_power_of_two(self) -> Self {
1222             let bits = size_of::<Self>() * 8;
1223             let one: Self = Self::one();
1224             one << ((bits - self.wrapping_sub(one).leading_zeros() as usize) % bits)
1225         }
1226
1227         /// Returns the smallest power of two greater than or equal to `n`. If
1228         /// the next power of two is greater than the type's maximum value,
1229         /// `None` is returned, otherwise the power of two is wrapped in `Some`.
1230         #[stable(feature = "rust1", since = "1.0.0")]
1231         pub fn checked_next_power_of_two(self) -> Option<Self> {
1232             let npot = self.next_power_of_two();
1233             if npot >= self {
1234                 Some(npot)
1235             } else {
1236                 None
1237             }
1238         }
1239     }
1240 }
1241
1242 #[lang = "u8"]
1243 #[cfg(stage0)]
1244 impl u8 {
1245     uint_impl! { u8, 8,
1246         intrinsics::ctpop8,
1247         intrinsics::ctlz8,
1248         intrinsics::cttz8,
1249         bswap8,
1250         intrinsics::u8_add_with_overflow,
1251         intrinsics::u8_sub_with_overflow,
1252         intrinsics::u8_mul_with_overflow }
1253 }
1254 #[lang = "u8"]
1255 #[cfg(not(stage0))]
1256 impl u8 {
1257     uint_impl! { u8, 8,
1258         intrinsics::ctpop,
1259         intrinsics::ctlz,
1260         intrinsics::cttz,
1261         intrinsics::bswap,
1262         intrinsics::add_with_overflow,
1263         intrinsics::sub_with_overflow,
1264         intrinsics::mul_with_overflow }
1265 }
1266
1267 #[lang = "u16"]
1268 #[cfg(stage0)]
1269 impl u16 {
1270     uint_impl! { u16, 16,
1271         intrinsics::ctpop16,
1272         intrinsics::ctlz16,
1273         intrinsics::cttz16,
1274         intrinsics::bswap16,
1275         intrinsics::u16_add_with_overflow,
1276         intrinsics::u16_sub_with_overflow,
1277         intrinsics::u16_mul_with_overflow }
1278 }
1279 #[lang = "u16"]
1280 #[cfg(not(stage0))]
1281 impl u16 {
1282     uint_impl! { u16, 16,
1283         intrinsics::ctpop,
1284         intrinsics::ctlz,
1285         intrinsics::cttz,
1286         intrinsics::bswap,
1287         intrinsics::add_with_overflow,
1288         intrinsics::sub_with_overflow,
1289         intrinsics::mul_with_overflow }
1290 }
1291
1292 #[lang = "u32"]
1293 #[cfg(stage0)]
1294 impl u32 {
1295     uint_impl! { u32, 32,
1296         intrinsics::ctpop32,
1297         intrinsics::ctlz32,
1298         intrinsics::cttz32,
1299         intrinsics::bswap32,
1300         intrinsics::u32_add_with_overflow,
1301         intrinsics::u32_sub_with_overflow,
1302         intrinsics::u32_mul_with_overflow }
1303 }
1304 #[lang = "u32"]
1305 #[cfg(not(stage0))]
1306 impl u32 {
1307     uint_impl! { u32, 32,
1308         intrinsics::ctpop,
1309         intrinsics::ctlz,
1310         intrinsics::cttz,
1311         intrinsics::bswap,
1312         intrinsics::add_with_overflow,
1313         intrinsics::sub_with_overflow,
1314         intrinsics::mul_with_overflow }
1315 }
1316
1317 #[lang = "u64"]
1318 #[cfg(stage0)]
1319 impl u64 {
1320     uint_impl! { u64, 64,
1321         intrinsics::ctpop64,
1322         intrinsics::ctlz64,
1323         intrinsics::cttz64,
1324         intrinsics::bswap64,
1325         intrinsics::u64_add_with_overflow,
1326         intrinsics::u64_sub_with_overflow,
1327         intrinsics::u64_mul_with_overflow }
1328 }
1329 #[lang = "u64"]
1330 #[cfg(not(stage0))]
1331 impl u64 {
1332     uint_impl! { u64, 64,
1333         intrinsics::ctpop,
1334         intrinsics::ctlz,
1335         intrinsics::cttz,
1336         intrinsics::bswap,
1337         intrinsics::add_with_overflow,
1338         intrinsics::sub_with_overflow,
1339         intrinsics::mul_with_overflow }
1340 }
1341
1342 #[cfg(target_pointer_width = "32")]
1343 #[lang = "usize"]
1344 #[cfg(stage0)]
1345 impl usize {
1346     uint_impl! { u32, 32,
1347         intrinsics::ctpop32,
1348         intrinsics::ctlz32,
1349         intrinsics::cttz32,
1350         intrinsics::bswap32,
1351         intrinsics::u32_add_with_overflow,
1352         intrinsics::u32_sub_with_overflow,
1353         intrinsics::u32_mul_with_overflow }
1354 }
1355 #[cfg(target_pointer_width = "32")]
1356 #[lang = "usize"]
1357 #[cfg(not(stage0))]
1358 impl usize {
1359     uint_impl! { u32, 32,
1360         intrinsics::ctpop,
1361         intrinsics::ctlz,
1362         intrinsics::cttz,
1363         intrinsics::bswap,
1364         intrinsics::add_with_overflow,
1365         intrinsics::sub_with_overflow,
1366         intrinsics::mul_with_overflow }
1367 }
1368
1369 #[cfg(target_pointer_width = "64")]
1370 #[lang = "usize"]
1371 #[cfg(stage0)]
1372 impl usize {
1373     uint_impl! { u64, 64,
1374         intrinsics::ctpop64,
1375         intrinsics::ctlz64,
1376         intrinsics::cttz64,
1377         intrinsics::bswap64,
1378         intrinsics::u64_add_with_overflow,
1379         intrinsics::u64_sub_with_overflow,
1380         intrinsics::u64_mul_with_overflow }
1381 }
1382 #[cfg(target_pointer_width = "64")]
1383 #[lang = "usize"]
1384 #[cfg(not(stage0))]
1385 impl usize {
1386     uint_impl! { u64, 64,
1387         intrinsics::ctpop,
1388         intrinsics::ctlz,
1389         intrinsics::cttz,
1390         intrinsics::bswap,
1391         intrinsics::add_with_overflow,
1392         intrinsics::sub_with_overflow,
1393         intrinsics::mul_with_overflow }
1394 }
1395
1396 /// Used for representing the classification of floating point numbers
1397 #[derive(Copy, Clone, PartialEq, Debug)]
1398 #[stable(feature = "rust1", since = "1.0.0")]
1399 pub enum FpCategory {
1400     /// "Not a Number", often obtained by dividing by zero
1401     #[stable(feature = "rust1", since = "1.0.0")]
1402     Nan,
1403
1404     /// Positive or negative infinity
1405     #[stable(feature = "rust1", since = "1.0.0")]
1406     Infinite ,
1407
1408     /// Positive or negative zero
1409     #[stable(feature = "rust1", since = "1.0.0")]
1410     Zero,
1411
1412     /// De-normalized floating point representation (less precise than `Normal`)
1413     #[stable(feature = "rust1", since = "1.0.0")]
1414     Subnormal,
1415
1416     /// A regular floating point number
1417     #[stable(feature = "rust1", since = "1.0.0")]
1418     Normal,
1419 }
1420
1421 /// A built-in floating point number.
1422 #[doc(hidden)]
1423 #[unstable(feature = "core_float",
1424            reason = "stable interface is via `impl f{32,64}` in later crates",
1425            issue = "27702")]
1426 pub trait Float: Sized {
1427     /// Returns the NaN value.
1428     fn nan() -> Self;
1429     /// Returns the infinite value.
1430     fn infinity() -> Self;
1431     /// Returns the negative infinite value.
1432     fn neg_infinity() -> Self;
1433     /// Returns -0.0.
1434     fn neg_zero() -> Self;
1435     /// Returns 0.0.
1436     fn zero() -> Self;
1437     /// Returns 1.0.
1438     fn one() -> Self;
1439     /// Parses the string `s` with the radix `r` as a float.
1440     fn from_str_radix(s: &str, r: u32) -> Result<Self, ParseFloatError>;
1441
1442     /// Returns true if this value is NaN and false otherwise.
1443     fn is_nan(self) -> bool;
1444     /// Returns true if this value is positive infinity or negative infinity and
1445     /// false otherwise.
1446     fn is_infinite(self) -> bool;
1447     /// Returns true if this number is neither infinite nor NaN.
1448     fn is_finite(self) -> bool;
1449     /// Returns true if this number is neither zero, infinite, denormal, or NaN.
1450     fn is_normal(self) -> bool;
1451     /// Returns the category that this number falls into.
1452     fn classify(self) -> FpCategory;
1453
1454     /// Returns the mantissa, exponent and sign as integers, respectively.
1455     fn integer_decode(self) -> (u64, i16, i8);
1456
1457     /// Computes the absolute value of `self`. Returns `Float::nan()` if the
1458     /// number is `Float::nan()`.
1459     fn abs(self) -> Self;
1460     /// Returns a number that represents the sign of `self`.
1461     ///
1462     /// - `1.0` if the number is positive, `+0.0` or `Float::infinity()`
1463     /// - `-1.0` if the number is negative, `-0.0` or `Float::neg_infinity()`
1464     /// - `Float::nan()` if the number is `Float::nan()`
1465     fn signum(self) -> Self;
1466     /// Returns `true` if `self` is positive, including `+0.0` and
1467     /// `Float::infinity()`.
1468     fn is_positive(self) -> bool;
1469     /// Returns `true` if `self` is negative, including `-0.0` and
1470     /// `Float::neg_infinity()`.
1471     fn is_negative(self) -> bool;
1472
1473     /// Take the reciprocal (inverse) of a number, `1/x`.
1474     fn recip(self) -> Self;
1475
1476     /// Raise a number to an integer power.
1477     ///
1478     /// Using this function is generally faster than using `powf`
1479     fn powi(self, n: i32) -> Self;
1480
1481     /// Convert radians to degrees.
1482     fn to_degrees(self) -> Self;
1483     /// Convert degrees to radians.
1484     fn to_radians(self) -> Self;
1485 }
1486
1487 macro_rules! from_str_radix_int_impl {
1488     ($($t:ty)*) => {$(
1489         #[stable(feature = "rust1", since = "1.0.0")]
1490         impl FromStr for $t {
1491             type Err = ParseIntError;
1492             fn from_str(src: &str) -> Result<Self, ParseIntError> {
1493                 from_str_radix(src, 10)
1494             }
1495         }
1496     )*}
1497 }
1498 from_str_radix_int_impl! { isize i8 i16 i32 i64 usize u8 u16 u32 u64 }
1499
1500 #[doc(hidden)]
1501 trait FromStrRadixHelper: PartialOrd + Copy {
1502     fn min_value() -> Self;
1503     fn from_u32(u: u32) -> Self;
1504     fn checked_mul(&self, other: u32) -> Option<Self>;
1505     fn checked_sub(&self, other: u32) -> Option<Self>;
1506     fn checked_add(&self, other: u32) -> Option<Self>;
1507 }
1508
1509 macro_rules! doit {
1510     ($($t:ty)*) => ($(impl FromStrRadixHelper for $t {
1511         fn min_value() -> Self { Self::min_value() }
1512         fn from_u32(u: u32) -> Self { u as Self }
1513         fn checked_mul(&self, other: u32) -> Option<Self> {
1514             Self::checked_mul(*self, other as Self)
1515         }
1516         fn checked_sub(&self, other: u32) -> Option<Self> {
1517             Self::checked_sub(*self, other as Self)
1518         }
1519         fn checked_add(&self, other: u32) -> Option<Self> {
1520             Self::checked_add(*self, other as Self)
1521         }
1522     })*)
1523 }
1524 doit! { i8 i16 i32 i64 isize u8 u16 u32 u64 usize }
1525
1526 fn from_str_radix<T: FromStrRadixHelper>(src: &str, radix: u32)
1527                                          -> Result<T, ParseIntError> {
1528     use self::IntErrorKind::*;
1529     use self::ParseIntError as PIE;
1530
1531     assert!(radix >= 2 && radix <= 36,
1532            "from_str_radix_int: must lie in the range `[2, 36]` - found {}",
1533            radix);
1534
1535     if src.is_empty() {
1536         return Err(PIE { kind: Empty });
1537     }
1538
1539     let is_signed_ty = T::from_u32(0) > T::min_value();
1540
1541     // all valid digits are ascii, so we will just iterate over the utf8 bytes
1542     // and cast them to chars. .to_digit() will safely return None for anything
1543     // other than a valid ascii digit for the given radix, including the first-byte
1544     // of multi-byte sequences
1545     let src = src.as_bytes();
1546
1547     let (is_positive, digits) = match src[0] {
1548         b'+' => (true, &src[1..]),
1549         b'-' if is_signed_ty => (false, &src[1..]),
1550         _ => (true, src)
1551     };
1552
1553     if digits.is_empty() {
1554         return Err(PIE { kind: Empty });
1555     }
1556
1557     let mut result = T::from_u32(0);
1558     if is_positive {
1559         // The number is positive
1560         for &c in digits {
1561             let x = match (c as char).to_digit(radix) {
1562                 Some(x) => x,
1563                 None => return Err(PIE { kind: InvalidDigit }),
1564             };
1565             result = match result.checked_mul(radix) {
1566                 Some(result) => result,
1567                 None => return Err(PIE { kind: Overflow }),
1568             };
1569             result = match result.checked_add(x) {
1570                 Some(result) => result,
1571                 None => return Err(PIE { kind: Overflow }),
1572             };
1573         }
1574     } else {
1575         // The number is negative
1576         for &c in digits {
1577             let x = match (c as char).to_digit(radix) {
1578                 Some(x) => x,
1579                 None => return Err(PIE { kind: InvalidDigit }),
1580             };
1581             result = match result.checked_mul(radix) {
1582                 Some(result) => result,
1583                 None => return Err(PIE { kind: Underflow }),
1584             };
1585             result = match result.checked_sub(x) {
1586                 Some(result) => result,
1587                 None => return Err(PIE { kind: Underflow }),
1588             };
1589         }
1590     }
1591     Ok(result)
1592 }
1593
1594 /// An error which can be returned when parsing an integer.
1595 #[derive(Debug, Clone, PartialEq)]
1596 #[stable(feature = "rust1", since = "1.0.0")]
1597 pub struct ParseIntError { kind: IntErrorKind }
1598
1599 #[derive(Debug, Clone, PartialEq)]
1600 enum IntErrorKind {
1601     Empty,
1602     InvalidDigit,
1603     Overflow,
1604     Underflow,
1605 }
1606
1607 impl ParseIntError {
1608     #[unstable(feature = "int_error_internals",
1609                reason = "available through Error trait and this method should \
1610                          not be exposed publicly",
1611                issue = "0")]
1612     #[doc(hidden)]
1613     pub fn __description(&self) -> &str {
1614         match self.kind {
1615             IntErrorKind::Empty => "cannot parse integer from empty string",
1616             IntErrorKind::InvalidDigit => "invalid digit found in string",
1617             IntErrorKind::Overflow => "number too large to fit in target type",
1618             IntErrorKind::Underflow => "number too small to fit in target type",
1619         }
1620     }
1621 }
1622
1623 #[stable(feature = "rust1", since = "1.0.0")]
1624 impl fmt::Display for ParseIntError {
1625     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1626         self.__description().fmt(f)
1627     }
1628 }
1629
1630 pub use num::dec2flt::ParseFloatError;
1631
1632 // Conversion traits for primitive integer and float types
1633 // Conversions T -> T are covered by a blanket impl and therefore excluded
1634 // Some conversions from and to usize/isize are not implemented due to portability concerns
1635 macro_rules! impl_from {
1636     ($Small: ty, $Large: ty) => {
1637         #[stable(feature = "lossless_prim_conv", since = "1.5.0")]
1638         impl From<$Small> for $Large {
1639             #[inline]
1640             fn from(small: $Small) -> $Large {
1641                 small as $Large
1642             }
1643         }
1644     }
1645 }
1646
1647 // Unsigned -> Unsigned
1648 impl_from! { u8, u16 }
1649 impl_from! { u8, u32 }
1650 impl_from! { u8, u64 }
1651 impl_from! { u8, usize }
1652 impl_from! { u16, u32 }
1653 impl_from! { u16, u64 }
1654 impl_from! { u32, u64 }
1655
1656 // Signed -> Signed
1657 impl_from! { i8, i16 }
1658 impl_from! { i8, i32 }
1659 impl_from! { i8, i64 }
1660 impl_from! { i8, isize }
1661 impl_from! { i16, i32 }
1662 impl_from! { i16, i64 }
1663 impl_from! { i32, i64 }
1664
1665 // Unsigned -> Signed
1666 impl_from! { u8, i16 }
1667 impl_from! { u8, i32 }
1668 impl_from! { u8, i64 }
1669 impl_from! { u16, i32 }
1670 impl_from! { u16, i64 }
1671 impl_from! { u32, i64 }
1672
1673 // Note: integers can only be represented with full precision in a float if
1674 // they fit in the significand, which is 24 bits in f32 and 53 bits in f64.
1675 // Lossy float conversions are not implemented at this time.
1676
1677 // Signed -> Float
1678 impl_from! { i8, f32 }
1679 impl_from! { i8, f64 }
1680 impl_from! { i16, f32 }
1681 impl_from! { i16, f64 }
1682 impl_from! { i32, f64 }
1683
1684 // Unsigned -> Float
1685 impl_from! { u8, f32 }
1686 impl_from! { u8, f64 }
1687 impl_from! { u16, f32 }
1688 impl_from! { u16, f64 }
1689 impl_from! { u32, f64 }
1690
1691 // Float -> Float
1692 impl_from! { f32, f64 }