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 generic mathematics
  12
  13 #![allow(missing_doc)]
  14
  15 use intrinsics;
  16 use {int, i8, i16, i32, i64};
  17 use {uint, u8, u16, u32, u64};
  18 use {f32, f64};
  19 use clone::Clone;
  20 use cmp::{PartialEq, PartialOrd};
  21 use kinds::Copy;
  22 use mem::size_of;
  23 use ops::{Add, Sub, Mul, Div, Rem, Neg};
  24 use ops::{Not, BitAnd, BitOr, BitXor, Shl, Shr};
  25 use option::{Option, Some, None};
  26
  27 /// The base trait for numeric types
  28 pub trait Num: PartialEq + Zero + One
  29              + Neg<Self>
  30              + Add<Self,Self>
  31              + Sub<Self,Self>
  32              + Mul<Self,Self>
  33              + Div<Self,Self>
  34              + Rem<Self,Self> {}
  35
  36 macro_rules! trait_impl(
  37     ($name:ident for $($t:ty)*) => ($(
  38         impl $name for $t {}
  39     )*)
  40 )
  41
  42 trait_impl!(Num for uint u8 u16 u32 u64 int i8 i16 i32 i64 f32 f64)
  43
  44 /// Simultaneous division and remainder
  45 #[inline]
  46 pub fn div_rem<T: Div<T, T> + Rem<T, T>>(x: T, y: T) -> (T, T) {
  47     (x / y, x % y)
  48 }
  49
  50 /// Defines an additive identity element for `Self`.
  51 ///
  52 /// # Deriving
  53 ///
  54 /// This trait can be automatically be derived using `#[deriving(Zero)]`
  55 /// attribute. If you choose to use this, make sure that the laws outlined in
  56 /// the documentation for `Zero::zero` still hold.
  57 pub trait Zero: Add<Self, Self> {
  58     /// Returns the additive identity element of `Self`, `0`.
  59     ///
  60     /// # Laws
  61     ///
  62     /// ~~~text
  63     /// a + 0 = a       ∀ a ∈ Self
  64     /// 0 + a = a       ∀ a ∈ Self
  65     /// ~~~
  66     ///
  67     /// # Purity
  68     ///
  69     /// This function should return the same result at all times regardless of
  70     /// external mutable state, for example values stored in TLS or in
  71     /// `static mut`s.
  72     // FIXME (#5527): This should be an associated constant
  73     fn zero() -> Self;
  74
  75     /// Returns `true` if `self` is equal to the additive identity.
  76     fn is_zero(&self) -> bool;
  77 }
  78
  79 macro_rules! zero_impl(
  80     ($t:ty, $v:expr) => {
  81         impl Zero for $t {
  82             #[inline]
  83             fn zero() -> $t { $v }
  84             #[inline]
  85             fn is_zero(&self) -> bool { *self == $v }
  86         }
  87     }
  88 )
  89
  90 macro_rules! zero_float_impl(
  91     ($t:ty, $v:expr) => {
  92         impl Zero for $t {
  93             #[inline]
  94             fn zero() -> $t { $v }
  95
  96             #[inline]
  97             fn is_zero(&self) -> bool { *self == $v || *self == -$v }
  98         }
  99     }
 100 )
 101
 102 zero_impl!(uint, 0u)
 103 zero_impl!(u8,  0u8)
 104 zero_impl!(u16, 0u16)
 105 zero_impl!(u32, 0u32)
 106 zero_impl!(u64, 0u64)
 107
 108 zero_impl!(int, 0i)
 109 zero_impl!(i8,  0i8)
 110 zero_impl!(i16, 0i16)
 111 zero_impl!(i32, 0i32)
 112 zero_impl!(i64, 0i64)
 113
 114 zero_float_impl!(f32, 0.0f32)
 115 zero_float_impl!(f64, 0.0f64)
 116
 117 /// Returns the additive identity, `0`.
 118 #[inline(always)] pub fn zero<T: Zero>() -> T { Zero::zero() }
 119
 120 /// Defines a multiplicative identity element for `Self`.
 121 pub trait One: Mul<Self, Self> {
 122     /// Returns the multiplicative identity element of `Self`, `1`.
 123     ///
 124     /// # Laws
 125     ///
 126     /// ~~~text
 127     /// a * 1 = a       ∀ a ∈ Self
 128     /// 1 * a = a       ∀ a ∈ Self
 129     /// ~~~
 130     ///
 131     /// # Purity
 132     ///
 133     /// This function should return the same result at all times regardless of
 134     /// external mutable state, for example values stored in TLS or in
 135     /// `static mut`s.
 136     // FIXME (#5527): This should be an associated constant
 137     fn one() -> Self;
 138 }
 139
 140 macro_rules! one_impl(
 141     ($t:ty, $v:expr) => {
 142         impl One for $t {
 143             #[inline]
 144             fn one() -> $t { $v }
 145         }
 146     }
 147 )
 148
 149 one_impl!(uint, 1u)
 150 one_impl!(u8,  1u8)
 151 one_impl!(u16, 1u16)
 152 one_impl!(u32, 1u32)
 153 one_impl!(u64, 1u64)
 154
 155 one_impl!(int, 1i)
 156 one_impl!(i8,  1i8)
 157 one_impl!(i16, 1i16)
 158 one_impl!(i32, 1i32)
 159 one_impl!(i64, 1i64)
 160
 161 one_impl!(f32, 1.0f32)
 162 one_impl!(f64, 1.0f64)
 163
 164 /// Returns the multiplicative identity, `1`.
 165 #[inline(always)] pub fn one<T: One>() -> T { One::one() }
 166
 167 /// Useful functions for signed numbers (i.e. numbers that can be negative).
 168 pub trait Signed: Num + Neg<Self> {
 169     /// Computes the absolute value.
 170     ///
 171     /// For `f32` and `f64`, `NaN` will be returned if the number is `NaN`.
 172     fn abs(&self) -> Self;
 173
 174     /// The positive difference of two numbers.
 175     ///
 176     /// Returns `zero` if the number is less than or equal to `other`, otherwise the difference
 177     /// between `self` and `other` is returned.
 178     fn abs_sub(&self, other: &Self) -> Self;
 179
 180     /// Returns the sign of the number.
 181     ///
 182     /// For `f32` and `f64`:
 183     ///
 184     /// * `1.0` if the number is positive, `+0.0` or `INFINITY`
 185     /// * `-1.0` if the number is negative, `-0.0` or `NEG_INFINITY`
 186     /// * `NaN` if the number is `NaN`
 187     ///
 188     /// For `int`:
 189     ///
 190     /// * `0` if the number is zero
 191     /// * `1` if the number is positive
 192     /// * `-1` if the number is negative
 193     fn signum(&self) -> Self;
 194
 195     /// Returns true if the number is positive and false if the number is zero or negative.
 196     fn is_positive(&self) -> bool;
 197
 198     /// Returns true if the number is negative and false if the number is zero or positive.
 199     fn is_negative(&self) -> bool;
 200 }
 201
 202 macro_rules! signed_impl(
 203     ($($t:ty)*) => ($(
 204         impl Signed for $t {
 205             #[inline]
 206             fn abs(&self) -> $t {
 207                 if self.is_negative() { -*self } else { *self }
 208             }
 209
 210             #[inline]
 211             fn abs_sub(&self, other: &$t) -> $t {
 212                 if *self <= *other { 0 } else { *self - *other }
 213             }
 214
 215             #[inline]
 216             fn signum(&self) -> $t {
 217                 match *self {
 218                     n if n > 0 => 1,
 219                     0 => 0,
 220                     _ => -1,
 221                 }
 222             }
 223
 224             #[inline]
 225             fn is_positive(&self) -> bool { *self > 0 }
 226
 227             #[inline]
 228             fn is_negative(&self) -> bool { *self < 0 }
 229         }
 230     )*)
 231 )
 232
 233 signed_impl!(int i8 i16 i32 i64)
 234
 235 macro_rules! signed_float_impl(
 236     ($t:ty, $nan:expr, $inf:expr, $neg_inf:expr, $fabs:path, $fcopysign:path, $fdim:ident) => {
 237         impl Signed for $t {
 238             /// Computes the absolute value. Returns `NAN` if the number is `NAN`.
 239             #[inline]
 240             fn abs(&self) -> $t {
 241                 unsafe { $fabs(*self) }
 242             }
 243
 244             /// The positive difference of two numbers. Returns `0.0` if the number is
 245             /// less than or equal to `other`, otherwise the difference between`self`
 246             /// and `other` is returned.
 247             #[inline]
 248             fn abs_sub(&self, other: &$t) -> $t {
 249                 extern { fn $fdim(a: $t, b: $t) -> $t; }
 250                 unsafe { $fdim(*self, *other) }
 251             }
 252
 253             /// # Returns
 254             ///
 255             /// - `1.0` if the number is positive, `+0.0` or `INFINITY`
 256             /// - `-1.0` if the number is negative, `-0.0` or `NEG_INFINITY`
 257             /// - `NAN` if the number is NaN
 258             #[inline]
 259             fn signum(&self) -> $t {
 260                 if self != self { $nan } else {
 261                     unsafe { $fcopysign(1.0, *self) }
 262                 }
 263             }
 264
 265             /// Returns `true` if the number is positive, including `+0.0` and `INFINITY`
 266             #[inline]
 267             fn is_positive(&self) -> bool { *self > 0.0 || (1.0 / *self) == $inf }
 268
 269             /// Returns `true` if the number is negative, including `-0.0` and `NEG_INFINITY`
 270             #[inline]
 271             fn is_negative(&self) -> bool { *self < 0.0 || (1.0 / *self) == $neg_inf }
 272         }
 273     }
 274 )
 275
 276 signed_float_impl!(f32, f32::NAN, f32::INFINITY, f32::NEG_INFINITY,
 277                    intrinsics::fabsf32, intrinsics::copysignf32, fdimf)
 278 signed_float_impl!(f64, f64::NAN, f64::INFINITY, f64::NEG_INFINITY,
 279                    intrinsics::fabsf64, intrinsics::copysignf64, fdim)
 280
 281 /// Computes the absolute value.
 282 ///
 283 /// For `f32` and `f64`, `NaN` will be returned if the number is `NaN`
 284 #[inline(always)]
 285 pub fn abs<T: Signed>(value: T) -> T {
 286     value.abs()
 287 }
 288
 289 /// The positive difference of two numbers.
 290 ///
 291 /// Returns `zero` if the number is less than or equal to `other`,
 292 /// otherwise the difference between `self` and `other` is returned.
 293 #[inline(always)]
 294 pub fn abs_sub<T: Signed>(x: T, y: T) -> T {
 295     x.abs_sub(&y)
 296 }
 297
 298 /// Returns the sign of the number.
 299 ///
 300 /// For `f32` and `f64`:
 301 ///
 302 /// * `1.0` if the number is positive, `+0.0` or `INFINITY`
 303 /// * `-1.0` if the number is negative, `-0.0` or `NEG_INFINITY`
 304 /// * `NaN` if the number is `NaN`
 305 ///
 306 /// For int:
 307 ///
 308 /// * `0` if the number is zero
 309 /// * `1` if the number is positive
 310 /// * `-1` if the number is negative
 311 #[inline(always)] pub fn signum<T: Signed>(value: T) -> T { value.signum() }
 312
 313 /// A trait for values which cannot be negative
 314 pub trait Unsigned: Num {}
 315
 316 trait_impl!(Unsigned for uint u8 u16 u32 u64)
 317
 318 /// Raises a value to the power of exp, using exponentiation by squaring.
 319 ///
 320 /// # Example
 321 ///
 322 /// ```rust
 323 /// use std::num;
 324 ///
 325 /// assert_eq!(num::pow(2i, 4), 16);
 326 /// ```
 327 #[inline]
 328 pub fn pow<T: One + Mul<T, T>>(mut base: T, mut exp: uint) -> T {
 329     if exp == 1 { base }
 330     else {
 331         let mut acc = one::<T>();
 332         while exp > 0 {
 333             if (exp & 1) == 1 {
 334                 acc = acc * base;
 335             }
 336             base = base * base;
 337             exp = exp >> 1;
 338         }
 339         acc
 340     }
 341 }
 342
 343 /// Numbers which have upper and lower bounds
 344 pub trait Bounded {
 345     // FIXME (#5527): These should be associated constants
 346     /// returns the smallest finite number this type can represent
 347     fn min_value() -> Self;
 348     /// returns the largest finite number this type can represent
 349     fn max_value() -> Self;
 350 }
 351
 352 macro_rules! bounded_impl(
 353     ($t:ty, $min:expr, $max:expr) => {
 354         impl Bounded for $t {
 355             #[inline]
 356             fn min_value() -> $t { $min }
 357
 358             #[inline]
 359             fn max_value() -> $t { $max }
 360         }
 361     }
 362 )
 363
 364 bounded_impl!(uint, uint::MIN, uint::MAX)
 365 bounded_impl!(u8, u8::MIN, u8::MAX)
 366 bounded_impl!(u16, u16::MIN, u16::MAX)
 367 bounded_impl!(u32, u32::MIN, u32::MAX)
 368 bounded_impl!(u64, u64::MIN, u64::MAX)
 369
 370 bounded_impl!(int, int::MIN, int::MAX)
 371 bounded_impl!(i8, i8::MIN, i8::MAX)
 372 bounded_impl!(i16, i16::MIN, i16::MAX)
 373 bounded_impl!(i32, i32::MIN, i32::MAX)
 374 bounded_impl!(i64, i64::MIN, i64::MAX)
 375
 376 bounded_impl!(f32, f32::MIN_VALUE, f32::MAX_VALUE)
 377 bounded_impl!(f64, f64::MIN_VALUE, f64::MAX_VALUE)
 378
 379 /// Specifies the available operations common to all of Rust's core numeric primitives.
 380 /// These may not always make sense from a purely mathematical point of view, but
 381 /// may be useful for systems programming.
 382 pub trait Primitive: Copy
 383                    + Clone
 384                    + Num
 385                    + NumCast
 386                    + PartialOrd
 387                    + Bounded {}
 388
 389 trait_impl!(Primitive for uint u8 u16 u32 u64 int i8 i16 i32 i64 f32 f64)
 390
 391 /// A primitive signed or unsigned integer equipped with various bitwise
 392 /// operators, bit counting methods, and endian conversion functions.
 393 pub trait Int: Primitive
 394              + CheckedAdd
 395              + CheckedSub
 396              + CheckedMul
 397              + CheckedDiv
 398              + Bounded
 399              + Not<Self>
 400              + BitAnd<Self,Self>
 401              + BitOr<Self,Self>
 402              + BitXor<Self,Self>
 403              + Shl<Self,Self>
 404              + Shr<Self,Self> {
 405     /// Returns the number of ones in the binary representation of the integer.
 406     ///
 407     /// # Example
 408     ///
 409     /// ```rust
 410     /// let n = 0b01001100u8;
 411     ///
 412     /// assert_eq!(n.count_ones(), 3);
 413     /// ```
 414     fn count_ones(self) -> Self;
 415
 416     /// Returns the number of zeros in the binary representation of the integer.
 417     ///
 418     /// # Example
 419     ///
 420     /// ```rust
 421     /// let n = 0b01001100u8;
 422     ///
 423     /// assert_eq!(n.count_zeros(), 5);
 424     /// ```
 425     #[inline]
 426     fn count_zeros(self) -> Self {
 427         (!self).count_ones()
 428     }
 429
 430     /// Returns the number of leading zeros in the in the binary representation
 431     /// of the integer.
 432     ///
 433     /// # Example
 434     ///
 435     /// ```rust
 436     /// let n = 0b0101000u16;
 437     ///
 438     /// assert_eq!(n.leading_zeros(), 10);
 439     /// ```
 440     fn leading_zeros(self) -> Self;
 441
 442     /// Returns the number of trailing zeros in the in the binary representation
 443     /// of the integer.
 444     ///
 445     /// # Example
 446     ///
 447     /// ```rust
 448     /// let n = 0b0101000u16;
 449     ///
 450     /// assert_eq!(n.trailing_zeros(), 3);
 451     /// ```
 452     fn trailing_zeros(self) -> Self;
 453
 454     /// Shifts the bits to the left by a specified amount amount, `n`, wrapping
 455     /// the truncated bits to the end of the resulting integer.
 456     ///
 457     /// # Example
 458     ///
 459     /// ```rust
 460     /// let n = 0x0123456789ABCDEFu64;
 461     /// let m = 0x3456789ABCDEF012u64;
 462     ///
 463     /// assert_eq!(n.rotate_left(12), m);
 464     /// ```
 465     fn rotate_left(self, n: uint) -> Self;
 466
 467     /// Shifts the bits to the right by a specified amount amount, `n`, wrapping
 468     /// the truncated bits to the beginning of the resulting integer.
 469     ///
 470     /// # Example
 471     ///
 472     /// ```rust
 473     /// let n = 0x0123456789ABCDEFu64;
 474     /// let m = 0xDEF0123456789ABCu64;
 475     ///
 476     /// assert_eq!(n.rotate_right(12), m);
 477     /// ```
 478     fn rotate_right(self, n: uint) -> Self;
 479
 480     /// Reverses the byte order of the integer.
 481     ///
 482     /// # Example
 483     ///
 484     /// ```rust
 485     /// let n = 0x0123456789ABCDEFu64;
 486     /// let m = 0xEFCDAB8967452301u64;
 487     ///
 488     /// assert_eq!(n.swap_bytes(), m);
 489     /// ```
 490     fn swap_bytes(self) -> Self;
 491
 492     /// Convert a integer from big endian to the target's endianness.
 493     ///
 494     /// On big endian this is a no-op. On little endian the bytes are swapped.
 495     ///
 496     /// # Example
 497     ///
 498     /// ```rust
 499     /// let n = 0x0123456789ABCDEFu64;
 500     ///
 501     /// if cfg!(target_endian = "big") {
 502     ///     assert_eq!(Int::from_be(n), n)
 503     /// } else {
 504     ///     assert_eq!(Int::from_be(n), n.swap_bytes())
 505     /// }
 506     /// ```
 507     #[inline]
 508     fn from_be(x: Self) -> Self {
 509         if cfg!(target_endian = "big") { x } else { x.swap_bytes() }
 510     }
 511
 512     /// Convert a integer from little endian to the target's endianness.
 513     ///
 514     /// On little endian this is a no-op. On big endian the bytes are swapped.
 515     ///
 516     /// # Example
 517     ///
 518     /// ```rust
 519     /// let n = 0x0123456789ABCDEFu64;
 520     ///
 521     /// if cfg!(target_endian = "little") {
 522     ///     assert_eq!(Int::from_le(n), n)
 523     /// } else {
 524     ///     assert_eq!(Int::from_le(n), n.swap_bytes())
 525     /// }
 526     /// ```
 527     #[inline]
 528     fn from_le(x: Self) -> Self {
 529         if cfg!(target_endian = "little") { x } else { x.swap_bytes() }
 530     }
 531
 532     /// Convert the integer to big endian from the target's endianness.
 533     ///
 534     /// On big endian this is a no-op. On little endian the bytes are swapped.
 535     ///
 536     /// # Example
 537     ///
 538     /// ```rust
 539     /// let n = 0x0123456789ABCDEFu64;
 540     ///
 541     /// if cfg!(target_endian = "big") {
 542     ///     assert_eq!(n.to_be(), n)
 543     /// } else {
 544     ///     assert_eq!(n.to_be(), n.swap_bytes())
 545     /// }
 546     /// ```
 547     #[inline]
 548     fn to_be(self) -> Self { // or not to be?
 549         if cfg!(target_endian = "big") { self } else { self.swap_bytes() }
 550     }
 551
 552     /// Convert the integer to little endian from the target's endianness.
 553     ///
 554     /// On little endian this is a no-op. On big endian the bytes are swapped.
 555     ///
 556     /// # Example
 557     ///
 558     /// ```rust
 559     /// let n = 0x0123456789ABCDEFu64;
 560     ///
 561     /// if cfg!(target_endian = "little") {
 562     ///     assert_eq!(n.to_le(), n)
 563     /// } else {
 564     ///     assert_eq!(n.to_le(), n.swap_bytes())
 565     /// }
 566     /// ```
 567     #[inline]
 568     fn to_le(self) -> Self {
 569         if cfg!(target_endian = "little") { self } else { self.swap_bytes() }
 570     }
 571 }
 572
 573 macro_rules! int_impl {
 574     ($T:ty, $BITS:expr, $ctpop:path, $ctlz:path, $cttz:path, $bswap:path) => {
 575         impl Int for $T {
 576             #[inline]
 577             fn count_ones(self) -> $T { unsafe { $ctpop(self) } }
 578
 579             #[inline]
 580             fn leading_zeros(self) -> $T { unsafe { $ctlz(self) } }
 581
 582             #[inline]
 583             fn trailing_zeros(self) -> $T { unsafe { $cttz(self) } }
 584
 585             #[inline]
 586             fn rotate_left(self, n: uint) -> $T {
 587                 // Protect against undefined behaviour for over-long bit shifts
 588                 let n = n % $BITS;
 589                 (self << n) | (self >> (($BITS - n) % $BITS))
 590             }
 591
 592             #[inline]
 593             fn rotate_right(self, n: uint) -> $T {
 594                 // Protect against undefined behaviour for over-long bit shifts
 595                 let n = n % $BITS;
 596                 (self >> n) | (self << (($BITS - n) % $BITS))
 597             }
 598
 599             #[inline]
 600             fn swap_bytes(self) -> $T { unsafe { $bswap(self) } }
 601         }
 602     }
 603 }
 604
 605 /// Swapping a single byte is a no-op. This is marked as `unsafe` for
 606 /// consistency with the other `bswap` intrinsics.
 607 unsafe fn bswap8(x: u8) -> u8 { x }
 608
 609 int_impl!(u8, 8,
 610     intrinsics::ctpop8,
 611     intrinsics::ctlz8,
 612     intrinsics::cttz8,
 613     bswap8)
 614
 615 int_impl!(u16, 16,
 616     intrinsics::ctpop16,
 617     intrinsics::ctlz16,
 618     intrinsics::cttz16,
 619     intrinsics::bswap16)
 620
 621 int_impl!(u32, 32,
 622     intrinsics::ctpop32,
 623     intrinsics::ctlz32,
 624     intrinsics::cttz32,
 625     intrinsics::bswap32)
 626
 627 int_impl!(u64, 64,
 628     intrinsics::ctpop64,
 629     intrinsics::ctlz64,
 630     intrinsics::cttz64,
 631     intrinsics::bswap64)
 632
 633 macro_rules! int_cast_impl {
 634     ($T:ty, $U:ty) => {
 635         impl Int for $T {
 636             #[inline]
 637             fn count_ones(self) -> $T { (self as $U).count_ones() as $T }
 638
 639             #[inline]
 640             fn leading_zeros(self) -> $T { (self as $U).leading_zeros() as $T }
 641
 642             #[inline]
 643             fn trailing_zeros(self) -> $T { (self as $U).trailing_zeros() as $T }
 644
 645             #[inline]
 646             fn rotate_left(self, n: uint) -> $T { (self as $U).rotate_left(n) as $T }
 647
 648             #[inline]
 649             fn rotate_right(self, n: uint) -> $T { (self as $U).rotate_right(n) as $T }
 650
 651             #[inline]
 652             fn swap_bytes(self) -> $T { (self as $U).swap_bytes() as $T }
 653         }
 654     }
 655 }
 656
 657 int_cast_impl!(i8, u8)
 658 int_cast_impl!(i16, u16)
 659 int_cast_impl!(i32, u32)
 660 int_cast_impl!(i64, u64)
 661
 662 #[cfg(target_word_size = "32")] int_cast_impl!(uint, u32)
 663 #[cfg(target_word_size = "64")] int_cast_impl!(uint, u64)
 664 #[cfg(target_word_size = "32")] int_cast_impl!(int, u32)
 665 #[cfg(target_word_size = "64")] int_cast_impl!(int, u64)
 666
 667 /// Returns the smallest power of 2 greater than or equal to `n`.
 668 #[inline]
 669 pub fn next_power_of_two<T: Unsigned + Int>(n: T) -> T {
 670     let halfbits: T = cast(size_of::<T>() * 4).unwrap();
 671     let mut tmp: T = n - one();
 672     let mut shift: T = one();
 673     while shift <= halfbits {
 674         tmp = tmp | (tmp >> shift);
 675         shift = shift << one();
 676     }
 677     tmp + one()
 678 }
 679
 680 // Returns `true` iff `n == 2^k` for some k.
 681 #[inline]
 682 pub fn is_power_of_two<T: Unsigned + Int>(n: T) -> bool {
 683     (n - one()) & n == zero()
 684 }
 685
 686 /// Returns the smallest power of 2 greater than or equal to `n`. If the next
 687 /// power of two is greater than the type's maximum value, `None` is returned,
 688 /// otherwise the power of 2 is wrapped in `Some`.
 689 #[inline]
 690 pub fn checked_next_power_of_two<T: Unsigned + Int>(n: T) -> Option<T> {
 691     let halfbits: T = cast(size_of::<T>() * 4).unwrap();
 692     let mut tmp: T = n - one();
 693     let mut shift: T = one();
 694     while shift <= halfbits {
 695         tmp = tmp | (tmp >> shift);
 696         shift = shift << one();
 697     }
 698     tmp.checked_add(&one())
 699 }
 700
 701 /// A generic trait for converting a value to a number.
 702 pub trait ToPrimitive {
 703     /// Converts the value of `self` to an `int`.
 704     #[inline]
 705     fn to_int(&self) -> Option<int> {
 706         self.to_i64().and_then(|x| x.to_int())
 707     }
 708
 709     /// Converts the value of `self` to an `i8`.
 710     #[inline]
 711     fn to_i8(&self) -> Option<i8> {
 712         self.to_i64().and_then(|x| x.to_i8())
 713     }
 714
 715     /// Converts the value of `self` to an `i16`.
 716     #[inline]
 717     fn to_i16(&self) -> Option<i16> {
 718         self.to_i64().and_then(|x| x.to_i16())
 719     }
 720
 721     /// Converts the value of `self` to an `i32`.
 722     #[inline]
 723     fn to_i32(&self) -> Option<i32> {
 724         self.to_i64().and_then(|x| x.to_i32())
 725     }
 726
 727     /// Converts the value of `self` to an `i64`.
 728     fn to_i64(&self) -> Option<i64>;
 729
 730     /// Converts the value of `self` to an `uint`.
 731     #[inline]
 732     fn to_uint(&self) -> Option<uint> {
 733         self.to_u64().and_then(|x| x.to_uint())
 734     }
 735
 736     /// Converts the value of `self` to an `u8`.
 737     #[inline]
 738     fn to_u8(&self) -> Option<u8> {
 739         self.to_u64().and_then(|x| x.to_u8())
 740     }
 741
 742     /// Converts the value of `self` to an `u16`.
 743     #[inline]
 744     fn to_u16(&self) -> Option<u16> {
 745         self.to_u64().and_then(|x| x.to_u16())
 746     }
 747
 748     /// Converts the value of `self` to an `u32`.
 749     #[inline]
 750     fn to_u32(&self) -> Option<u32> {
 751         self.to_u64().and_then(|x| x.to_u32())
 752     }
 753
 754     /// Converts the value of `self` to an `u64`.
 755     #[inline]
 756     fn to_u64(&self) -> Option<u64>;
 757
 758     /// Converts the value of `self` to an `f32`.
 759     #[inline]
 760     fn to_f32(&self) -> Option<f32> {
 761         self.to_f64().and_then(|x| x.to_f32())
 762     }
 763
 764     /// Converts the value of `self` to an `f64`.
 765     #[inline]
 766     fn to_f64(&self) -> Option<f64> {
 767         self.to_i64().and_then(|x| x.to_f64())
 768     }
 769 }
 770
 771 macro_rules! impl_to_primitive_int_to_int(
 772     ($SrcT:ty, $DstT:ty) => (
 773         {
 774             if size_of::<$SrcT>() <= size_of::<$DstT>() {
 775                 Some(*self as $DstT)
 776             } else {
 777                 let n = *self as i64;
 778                 let min_value: $DstT = Bounded::min_value();
 779                 let max_value: $DstT = Bounded::max_value();
 780                 if min_value as i64 <= n && n <= max_value as i64 {
 781                     Some(*self as $DstT)
 782                 } else {
 783                     None
 784                 }
 785             }
 786         }
 787     )
 788 )
 789
 790 macro_rules! impl_to_primitive_int_to_uint(
 791     ($SrcT:ty, $DstT:ty) => (
 792         {
 793             let zero: $SrcT = Zero::zero();
 794             let max_value: $DstT = Bounded::max_value();
 795             if zero <= *self && *self as u64 <= max_value as u64 {
 796                 Some(*self as $DstT)
 797             } else {
 798                 None
 799             }
 800         }
 801     )
 802 )
 803
 804 macro_rules! impl_to_primitive_int(
 805     ($T:ty) => (
 806         impl ToPrimitive for $T {
 807             #[inline]
 808             fn to_int(&self) -> Option<int> { impl_to_primitive_int_to_int!($T, int) }
 809             #[inline]
 810             fn to_i8(&self) -> Option<i8> { impl_to_primitive_int_to_int!($T, i8) }
 811             #[inline]
 812             fn to_i16(&self) -> Option<i16> { impl_to_primitive_int_to_int!($T, i16) }
 813             #[inline]
 814             fn to_i32(&self) -> Option<i32> { impl_to_primitive_int_to_int!($T, i32) }
 815             #[inline]
 816             fn to_i64(&self) -> Option<i64> { impl_to_primitive_int_to_int!($T, i64) }
 817
 818             #[inline]
 819             fn to_uint(&self) -> Option<uint> { impl_to_primitive_int_to_uint!($T, uint) }
 820             #[inline]
 821             fn to_u8(&self) -> Option<u8> { impl_to_primitive_int_to_uint!($T, u8) }
 822             #[inline]
 823             fn to_u16(&self) -> Option<u16> { impl_to_primitive_int_to_uint!($T, u16) }
 824             #[inline]
 825             fn to_u32(&self) -> Option<u32> { impl_to_primitive_int_to_uint!($T, u32) }
 826             #[inline]
 827             fn to_u64(&self) -> Option<u64> { impl_to_primitive_int_to_uint!($T, u64) }
 828
 829             #[inline]
 830             fn to_f32(&self) -> Option<f32> { Some(*self as f32) }
 831             #[inline]
 832             fn to_f64(&self) -> Option<f64> { Some(*self as f64) }
 833         }
 834     )
 835 )
 836
 837 impl_to_primitive_int!(int)
 838 impl_to_primitive_int!(i8)
 839 impl_to_primitive_int!(i16)
 840 impl_to_primitive_int!(i32)
 841 impl_to_primitive_int!(i64)
 842
 843 macro_rules! impl_to_primitive_uint_to_int(
 844     ($DstT:ty) => (
 845         {
 846             let max_value: $DstT = Bounded::max_value();
 847             if *self as u64 <= max_value as u64 {
 848                 Some(*self as $DstT)
 849             } else {
 850                 None
 851             }
 852         }
 853     )
 854 )
 855
 856 macro_rules! impl_to_primitive_uint_to_uint(
 857     ($SrcT:ty, $DstT:ty) => (
 858         {
 859             if size_of::<$SrcT>() <= size_of::<$DstT>() {
 860                 Some(*self as $DstT)
 861             } else {
 862                 let zero: $SrcT = Zero::zero();
 863                 let max_value: $DstT = Bounded::max_value();
 864                 if zero <= *self && *self as u64 <= max_value as u64 {
 865                     Some(*self as $DstT)
 866                 } else {
 867                     None
 868                 }
 869             }
 870         }
 871     )
 872 )
 873
 874 macro_rules! impl_to_primitive_uint(
 875     ($T:ty) => (
 876         impl ToPrimitive for $T {
 877             #[inline]
 878             fn to_int(&self) -> Option<int> { impl_to_primitive_uint_to_int!(int) }
 879             #[inline]
 880             fn to_i8(&self) -> Option<i8> { impl_to_primitive_uint_to_int!(i8) }
 881             #[inline]
 882             fn to_i16(&self) -> Option<i16> { impl_to_primitive_uint_to_int!(i16) }
 883             #[inline]
 884             fn to_i32(&self) -> Option<i32> { impl_to_primitive_uint_to_int!(i32) }
 885             #[inline]
 886             fn to_i64(&self) -> Option<i64> { impl_to_primitive_uint_to_int!(i64) }
 887
 888             #[inline]
 889             fn to_uint(&self) -> Option<uint> { impl_to_primitive_uint_to_uint!($T, uint) }
 890             #[inline]
 891             fn to_u8(&self) -> Option<u8> { impl_to_primitive_uint_to_uint!($T, u8) }
 892             #[inline]
 893             fn to_u16(&self) -> Option<u16> { impl_to_primitive_uint_to_uint!($T, u16) }
 894             #[inline]
 895             fn to_u32(&self) -> Option<u32> { impl_to_primitive_uint_to_uint!($T, u32) }
 896             #[inline]
 897             fn to_u64(&self) -> Option<u64> { impl_to_primitive_uint_to_uint!($T, u64) }
 898
 899             #[inline]
 900             fn to_f32(&self) -> Option<f32> { Some(*self as f32) }
 901             #[inline]
 902             fn to_f64(&self) -> Option<f64> { Some(*self as f64) }
 903         }
 904     )
 905 )
 906
 907 impl_to_primitive_uint!(uint)
 908 impl_to_primitive_uint!(u8)
 909 impl_to_primitive_uint!(u16)
 910 impl_to_primitive_uint!(u32)
 911 impl_to_primitive_uint!(u64)
 912
 913 macro_rules! impl_to_primitive_float_to_float(
 914     ($SrcT:ty, $DstT:ty) => (
 915         if size_of::<$SrcT>() <= size_of::<$DstT>() {
 916             Some(*self as $DstT)
 917         } else {
 918             let n = *self as f64;
 919             let max_value: $SrcT = Bounded::max_value();
 920             if -max_value as f64 <= n && n <= max_value as f64 {
 921                 Some(*self as $DstT)
 922             } else {
 923                 None
 924             }
 925         }
 926     )
 927 )
 928
 929 macro_rules! impl_to_primitive_float(
 930     ($T:ty) => (
 931         impl ToPrimitive for $T {
 932             #[inline]
 933             fn to_int(&self) -> Option<int> { Some(*self as int) }
 934             #[inline]
 935             fn to_i8(&self) -> Option<i8> { Some(*self as i8) }
 936             #[inline]
 937             fn to_i16(&self) -> Option<i16> { Some(*self as i16) }
 938             #[inline]
 939             fn to_i32(&self) -> Option<i32> { Some(*self as i32) }
 940             #[inline]
 941             fn to_i64(&self) -> Option<i64> { Some(*self as i64) }
 942
 943             #[inline]
 944             fn to_uint(&self) -> Option<uint> { Some(*self as uint) }
 945             #[inline]
 946             fn to_u8(&self) -> Option<u8> { Some(*self as u8) }
 947             #[inline]
 948             fn to_u16(&self) -> Option<u16> { Some(*self as u16) }
 949             #[inline]
 950             fn to_u32(&self) -> Option<u32> { Some(*self as u32) }
 951             #[inline]
 952             fn to_u64(&self) -> Option<u64> { Some(*self as u64) }
 953
 954             #[inline]
 955             fn to_f32(&self) -> Option<f32> { impl_to_primitive_float_to_float!($T, f32) }
 956             #[inline]
 957             fn to_f64(&self) -> Option<f64> { impl_to_primitive_float_to_float!($T, f64) }
 958         }
 959     )
 960 )
 961
 962 impl_to_primitive_float!(f32)
 963 impl_to_primitive_float!(f64)
 964
 965 /// A generic trait for converting a number to a value.
 966 pub trait FromPrimitive {
 967     /// Convert an `int` to return an optional value of this type. If the
 968     /// value cannot be represented by this value, the `None` is returned.
 969     #[inline]
 970     fn from_int(n: int) -> Option<Self> {
 971         FromPrimitive::from_i64(n as i64)
 972     }
 973
 974     /// Convert an `i8` to return an optional value of this type. If the
 975     /// type cannot be represented by this value, the `None` is returned.
 976     #[inline]
 977     fn from_i8(n: i8) -> Option<Self> {
 978         FromPrimitive::from_i64(n as i64)
 979     }
 980
 981     /// Convert an `i16` to return an optional value of this type. If the
 982     /// type cannot be represented by this value, the `None` is returned.
 983     #[inline]
 984     fn from_i16(n: i16) -> Option<Self> {
 985         FromPrimitive::from_i64(n as i64)
 986     }
 987
 988     /// Convert an `i32` to return an optional value of this type. If the
 989     /// type cannot be represented by this value, the `None` is returned.
 990     #[inline]
 991     fn from_i32(n: i32) -> Option<Self> {
 992         FromPrimitive::from_i64(n as i64)
 993     }
 994
 995     /// Convert an `i64` to return an optional value of this type. If the
 996     /// type cannot be represented by this value, the `None` is returned.
 997     fn from_i64(n: i64) -> Option<Self>;
 998
 999     /// Convert an `uint` to return an optional value of this type. If the
1000     /// type cannot be represented by this value, the `None` is returned.
1001     #[inline]
1002     fn from_uint(n: uint) -> Option<Self> {
1003         FromPrimitive::from_u64(n as u64)
1004     }
1005
1006     /// Convert an `u8` to return an optional value of this type. If the
1007     /// type cannot be represented by this value, the `None` is returned.
1008     #[inline]
1009     fn from_u8(n: u8) -> Option<Self> {
1010         FromPrimitive::from_u64(n as u64)
1011     }
1012
1013     /// Convert an `u16` to return an optional value of this type. If the
1014     /// type cannot be represented by this value, the `None` is returned.
1015     #[inline]
1016     fn from_u16(n: u16) -> Option<Self> {
1017         FromPrimitive::from_u64(n as u64)
1018     }
1019
1020     /// Convert an `u32` to return an optional value of this type. If the
1021     /// type cannot be represented by this value, the `None` is returned.
1022     #[inline]
1023     fn from_u32(n: u32) -> Option<Self> {
1024         FromPrimitive::from_u64(n as u64)
1025     }
1026
1027     /// Convert an `u64` to return an optional value of this type. If the
1028     /// type cannot be represented by this value, the `None` is returned.
1029     fn from_u64(n: u64) -> Option<Self>;
1030
1031     /// Convert a `f32` to return an optional value of this type. If the
1032     /// type cannot be represented by this value, the `None` is returned.
1033     #[inline]
1034     fn from_f32(n: f32) -> Option<Self> {
1035         FromPrimitive::from_f64(n as f64)
1036     }
1037
1038     /// Convert a `f64` to return an optional value of this type. If the
1039     /// type cannot be represented by this value, the `None` is returned.
1040     #[inline]
1041     fn from_f64(n: f64) -> Option<Self> {
1042         FromPrimitive::from_i64(n as i64)
1043     }
1044 }
1045
1046 /// A utility function that just calls `FromPrimitive::from_int`.
1047 pub fn from_int<A: FromPrimitive>(n: int) -> Option<A> {
1048     FromPrimitive::from_int(n)
1049 }
1050
1051 /// A utility function that just calls `FromPrimitive::from_i8`.
1052 pub fn from_i8<A: FromPrimitive>(n: i8) -> Option<A> {
1053     FromPrimitive::from_i8(n)
1054 }
1055
1056 /// A utility function that just calls `FromPrimitive::from_i16`.
1057 pub fn from_i16<A: FromPrimitive>(n: i16) -> Option<A> {
1058     FromPrimitive::from_i16(n)
1059 }
1060
1061 /// A utility function that just calls `FromPrimitive::from_i32`.
1062 pub fn from_i32<A: FromPrimitive>(n: i32) -> Option<A> {
1063     FromPrimitive::from_i32(n)
1064 }
1065
1066 /// A utility function that just calls `FromPrimitive::from_i64`.
1067 pub fn from_i64<A: FromPrimitive>(n: i64) -> Option<A> {
1068     FromPrimitive::from_i64(n)
1069 }
1070
1071 /// A utility function that just calls `FromPrimitive::from_uint`.
1072 pub fn from_uint<A: FromPrimitive>(n: uint) -> Option<A> {
1073     FromPrimitive::from_uint(n)
1074 }
1075
1076 /// A utility function that just calls `FromPrimitive::from_u8`.
1077 pub fn from_u8<A: FromPrimitive>(n: u8) -> Option<A> {
1078     FromPrimitive::from_u8(n)
1079 }
1080
1081 /// A utility function that just calls `FromPrimitive::from_u16`.
1082 pub fn from_u16<A: FromPrimitive>(n: u16) -> Option<A> {
1083     FromPrimitive::from_u16(n)
1084 }
1085
1086 /// A utility function that just calls `FromPrimitive::from_u32`.
1087 pub fn from_u32<A: FromPrimitive>(n: u32) -> Option<A> {
1088     FromPrimitive::from_u32(n)
1089 }
1090
1091 /// A utility function that just calls `FromPrimitive::from_u64`.
1092 pub fn from_u64<A: FromPrimitive>(n: u64) -> Option<A> {
1093     FromPrimitive::from_u64(n)
1094 }
1095
1096 /// A utility function that just calls `FromPrimitive::from_f32`.
1097 pub fn from_f32<A: FromPrimitive>(n: f32) -> Option<A> {
1098     FromPrimitive::from_f32(n)
1099 }
1100
1101 /// A utility function that just calls `FromPrimitive::from_f64`.
1102 pub fn from_f64<A: FromPrimitive>(n: f64) -> Option<A> {
1103     FromPrimitive::from_f64(n)
1104 }
1105
1106 macro_rules! impl_from_primitive(
1107     ($T:ty, $to_ty:expr) => (
1108         impl FromPrimitive for $T {
1109             #[inline] fn from_int(n: int) -> Option<$T> { $to_ty }
1110             #[inline] fn from_i8(n: i8) -> Option<$T> { $to_ty }
1111             #[inline] fn from_i16(n: i16) -> Option<$T> { $to_ty }
1112             #[inline] fn from_i32(n: i32) -> Option<$T> { $to_ty }
1113             #[inline] fn from_i64(n: i64) -> Option<$T> { $to_ty }
1114
1115             #[inline] fn from_uint(n: uint) -> Option<$T> { $to_ty }
1116             #[inline] fn from_u8(n: u8) -> Option<$T> { $to_ty }
1117             #[inline] fn from_u16(n: u16) -> Option<$T> { $to_ty }
1118             #[inline] fn from_u32(n: u32) -> Option<$T> { $to_ty }
1119             #[inline] fn from_u64(n: u64) -> Option<$T> { $to_ty }
1120
1121             #[inline] fn from_f32(n: f32) -> Option<$T> { $to_ty }
1122             #[inline] fn from_f64(n: f64) -> Option<$T> { $to_ty }
1123         }
1124     )
1125 )
1126
1127 impl_from_primitive!(int, n.to_int())
1128 impl_from_primitive!(i8, n.to_i8())
1129 impl_from_primitive!(i16, n.to_i16())
1130 impl_from_primitive!(i32, n.to_i32())
1131 impl_from_primitive!(i64, n.to_i64())
1132 impl_from_primitive!(uint, n.to_uint())
1133 impl_from_primitive!(u8, n.to_u8())
1134 impl_from_primitive!(u16, n.to_u16())
1135 impl_from_primitive!(u32, n.to_u32())
1136 impl_from_primitive!(u64, n.to_u64())
1137 impl_from_primitive!(f32, n.to_f32())
1138 impl_from_primitive!(f64, n.to_f64())
1139
1140 /// Cast from one machine scalar to another.
1141 ///
1142 /// # Example
1143 ///
1144 /// ```
1145 /// use std::num;
1146 ///
1147 /// let twenty: f32 = num::cast(0x14i).unwrap();
1148 /// assert_eq!(twenty, 20f32);
1149 /// ```
1150 ///
1151 #[inline]
1152 pub fn cast<T: NumCast,U: NumCast>(n: T) -> Option<U> {
1153     NumCast::from(n)
1154 }
1155
1156 /// An interface for casting between machine scalars.
1157 pub trait NumCast: ToPrimitive {
1158     /// Creates a number from another value that can be converted into a primitive via the
1159     /// `ToPrimitive` trait.
1160     fn from<T: ToPrimitive>(n: T) -> Option<Self>;
1161 }
1162
1163 macro_rules! impl_num_cast(
1164     ($T:ty, $conv:ident) => (
1165         impl NumCast for $T {
1166             #[inline]
1167             fn from<N: ToPrimitive>(n: N) -> Option<$T> {
1168                 // `$conv` could be generated using `concat_idents!`, but that
1169                 // macro seems to be broken at the moment
1170                 n.$conv()
1171             }
1172         }
1173     )
1174 )
1175
1176 impl_num_cast!(u8,    to_u8)
1177 impl_num_cast!(u16,   to_u16)
1178 impl_num_cast!(u32,   to_u32)
1179 impl_num_cast!(u64,   to_u64)
1180 impl_num_cast!(uint,  to_uint)
1181 impl_num_cast!(i8,    to_i8)
1182 impl_num_cast!(i16,   to_i16)
1183 impl_num_cast!(i32,   to_i32)
1184 impl_num_cast!(i64,   to_i64)
1185 impl_num_cast!(int,   to_int)
1186 impl_num_cast!(f32,   to_f32)
1187 impl_num_cast!(f64,   to_f64)
1188
1189 /// Saturating math operations
1190 pub trait Saturating {
1191     /// Saturating addition operator.
1192     /// Returns a+b, saturating at the numeric bounds instead of overflowing.
1193     fn saturating_add(self, v: Self) -> Self;
1194
1195     /// Saturating subtraction operator.
1196     /// Returns a-b, saturating at the numeric bounds instead of overflowing.
1197     fn saturating_sub(self, v: Self) -> Self;
1198 }
1199
1200 impl<T: CheckedAdd + CheckedSub + Zero + PartialOrd + Bounded> Saturating for T {
1201     #[inline]
1202     fn saturating_add(self, v: T) -> T {
1203         match self.checked_add(&v) {
1204             Some(x) => x,
1205             None => if v >= Zero::zero() {
1206                 Bounded::max_value()
1207             } else {
1208                 Bounded::min_value()
1209             }
1210         }
1211     }
1212
1213     #[inline]
1214     fn saturating_sub(self, v: T) -> T {
1215         match self.checked_sub(&v) {
1216             Some(x) => x,
1217             None => if v >= Zero::zero() {
1218                 Bounded::min_value()
1219             } else {
1220                 Bounded::max_value()
1221             }
1222         }
1223     }
1224 }
1225
1226 /// Performs addition that returns `None` instead of wrapping around on overflow.
1227 pub trait CheckedAdd: Add<Self, Self> {
1228     /// Adds two numbers, checking for overflow. If overflow happens, `None` is returned.
1229     fn checked_add(&self, v: &Self) -> Option<Self>;
1230 }
1231
1232 macro_rules! checked_impl(
1233     ($trait_name:ident, $method:ident, $t:ty, $op:path) => {
1234         impl $trait_name for $t {
1235             #[inline]
1236             fn $method(&self, v: &$t) -> Option<$t> {
1237                 unsafe {
1238                     let (x, y) = $op(*self, *v);
1239                     if y { None } else { Some(x) }
1240                 }
1241             }
1242         }
1243     }
1244 )
1245 macro_rules! checked_cast_impl(
1246     ($trait_name:ident, $method:ident, $t:ty, $cast:ty, $op:path) => {
1247         impl $trait_name for $t {
1248             #[inline]
1249             fn $method(&self, v: &$t) -> Option<$t> {
1250                 unsafe {
1251                     let (x, y) = $op(*self as $cast, *v as $cast);
1252                     if y { None } else { Some(x as $t) }
1253                 }
1254             }
1255         }
1256     }
1257 )
1258
1259 #[cfg(target_word_size = "32")]
1260 checked_cast_impl!(CheckedAdd, checked_add, uint, u32, intrinsics::u32_add_with_overflow)
1261 #[cfg(target_word_size = "64")]
1262 checked_cast_impl!(CheckedAdd, checked_add, uint, u64, intrinsics::u64_add_with_overflow)
1263
1264 checked_impl!(CheckedAdd, checked_add, u8,  intrinsics::u8_add_with_overflow)
1265 checked_impl!(CheckedAdd, checked_add, u16, intrinsics::u16_add_with_overflow)
1266 checked_impl!(CheckedAdd, checked_add, u32, intrinsics::u32_add_with_overflow)
1267 checked_impl!(CheckedAdd, checked_add, u64, intrinsics::u64_add_with_overflow)
1268
1269 #[cfg(target_word_size = "32")]
1270 checked_cast_impl!(CheckedAdd, checked_add, int, i32, intrinsics::i32_add_with_overflow)
1271 #[cfg(target_word_size = "64")]
1272 checked_cast_impl!(CheckedAdd, checked_add, int, i64, intrinsics::i64_add_with_overflow)
1273
1274 checked_impl!(CheckedAdd, checked_add, i8,  intrinsics::i8_add_with_overflow)
1275 checked_impl!(CheckedAdd, checked_add, i16, intrinsics::i16_add_with_overflow)
1276 checked_impl!(CheckedAdd, checked_add, i32, intrinsics::i32_add_with_overflow)
1277 checked_impl!(CheckedAdd, checked_add, i64, intrinsics::i64_add_with_overflow)
1278
1279 /// Performs subtraction that returns `None` instead of wrapping around on underflow.
1280 pub trait CheckedSub: Sub<Self, Self> {
1281     /// Subtracts two numbers, checking for underflow. If underflow happens, `None` is returned.
1282     fn checked_sub(&self, v: &Self) -> Option<Self>;
1283 }
1284
1285 #[cfg(target_word_size = "32")]
1286 checked_cast_impl!(CheckedSub, checked_sub, uint, u32, intrinsics::u32_sub_with_overflow)
1287 #[cfg(target_word_size = "64")]
1288 checked_cast_impl!(CheckedSub, checked_sub, uint, u64, intrinsics::u64_sub_with_overflow)
1289
1290 checked_impl!(CheckedSub, checked_sub, u8,  intrinsics::u8_sub_with_overflow)
1291 checked_impl!(CheckedSub, checked_sub, u16, intrinsics::u16_sub_with_overflow)
1292 checked_impl!(CheckedSub, checked_sub, u32, intrinsics::u32_sub_with_overflow)
1293 checked_impl!(CheckedSub, checked_sub, u64, intrinsics::u64_sub_with_overflow)
1294
1295 #[cfg(target_word_size = "32")]
1296 checked_cast_impl!(CheckedSub, checked_sub, int, i32, intrinsics::i32_sub_with_overflow)
1297 #[cfg(target_word_size = "64")]
1298 checked_cast_impl!(CheckedSub, checked_sub, int, i64, intrinsics::i64_sub_with_overflow)
1299
1300 checked_impl!(CheckedSub, checked_sub, i8,  intrinsics::i8_sub_with_overflow)
1301 checked_impl!(CheckedSub, checked_sub, i16, intrinsics::i16_sub_with_overflow)
1302 checked_impl!(CheckedSub, checked_sub, i32, intrinsics::i32_sub_with_overflow)
1303 checked_impl!(CheckedSub, checked_sub, i64, intrinsics::i64_sub_with_overflow)
1304
1305 /// Performs multiplication that returns `None` instead of wrapping around on underflow or
1306 /// overflow.
1307 pub trait CheckedMul: Mul<Self, Self> {
1308     /// Multiplies two numbers, checking for underflow or overflow. If underflow or overflow
1309     /// happens, `None` is returned.
1310     fn checked_mul(&self, v: &Self) -> Option<Self>;
1311 }
1312
1313 #[cfg(target_word_size = "32")]
1314 checked_cast_impl!(CheckedMul, checked_mul, uint, u32, intrinsics::u32_mul_with_overflow)
1315 #[cfg(target_word_size = "64")]
1316 checked_cast_impl!(CheckedMul, checked_mul, uint, u64, intrinsics::u64_mul_with_overflow)
1317
1318 checked_impl!(CheckedMul, checked_mul, u8,  intrinsics::u8_mul_with_overflow)
1319 checked_impl!(CheckedMul, checked_mul, u16, intrinsics::u16_mul_with_overflow)
1320 checked_impl!(CheckedMul, checked_mul, u32, intrinsics::u32_mul_with_overflow)
1321 checked_impl!(CheckedMul, checked_mul, u64, intrinsics::u64_mul_with_overflow)
1322
1323 #[cfg(target_word_size = "32")]
1324 checked_cast_impl!(CheckedMul, checked_mul, int, i32, intrinsics::i32_mul_with_overflow)
1325 #[cfg(target_word_size = "64")]
1326 checked_cast_impl!(CheckedMul, checked_mul, int, i64, intrinsics::i64_mul_with_overflow)
1327
1328 checked_impl!(CheckedMul, checked_mul, i8,  intrinsics::i8_mul_with_overflow)
1329 checked_impl!(CheckedMul, checked_mul, i16, intrinsics::i16_mul_with_overflow)
1330 checked_impl!(CheckedMul, checked_mul, i32, intrinsics::i32_mul_with_overflow)
1331 checked_impl!(CheckedMul, checked_mul, i64, intrinsics::i64_mul_with_overflow)
1332
1333 /// Performs division that returns `None` instead of wrapping around on underflow or overflow.
1334 pub trait CheckedDiv: Div<Self, Self> {
1335     /// Divides two numbers, checking for underflow or overflow. If underflow or overflow happens,
1336     /// `None` is returned.
1337     fn checked_div(&self, v: &Self) -> Option<Self>;
1338 }
1339
1340 macro_rules! checkeddiv_int_impl(
1341     ($t:ty, $min:expr) => {
1342         impl CheckedDiv for $t {
1343             #[inline]
1344             fn checked_div(&self, v: &$t) -> Option<$t> {
1345                 if *v == 0 || (*self == $min && *v == -1) {
1346                     None
1347                 } else {
1348                     Some(self / *v)
1349                 }
1350             }
1351         }
1352     }
1353 )
1354
1355 checkeddiv_int_impl!(int, int::MIN)
1356 checkeddiv_int_impl!(i8, i8::MIN)
1357 checkeddiv_int_impl!(i16, i16::MIN)
1358 checkeddiv_int_impl!(i32, i32::MIN)
1359 checkeddiv_int_impl!(i64, i64::MIN)
1360
1361 macro_rules! checkeddiv_uint_impl(
1362     ($($t:ty)*) => ($(
1363         impl CheckedDiv for $t {
1364             #[inline]
1365             fn checked_div(&self, v: &$t) -> Option<$t> {
1366                 if *v == 0 {
1367                     None
1368                 } else {
1369                     Some(self / *v)
1370                 }
1371             }
1372         }
1373     )*)
1374 )
1375
1376 checkeddiv_uint_impl!(uint u8 u16 u32 u64)
1377
1378 /// Used for representing the classification of floating point numbers
1379 #[deriving(PartialEq, Show)]
1380 pub enum FPCategory {
1381     /// "Not a Number", often obtained by dividing by zero
1382     FPNaN,
1383     /// Positive or negative infinity
1384     FPInfinite ,
1385     /// Positive or negative zero
1386     FPZero,
1387     /// De-normalized floating point representation (less precise than `FPNormal`)
1388     FPSubnormal,
1389     /// A regular floating point number
1390     FPNormal,
1391 }
1392
1393 /// Operations on primitive floating point numbers.
1394 // FIXME(#5527): In a future version of Rust, many of these functions will
1395 //               become constants.
1396 //
1397 // FIXME(#8888): Several of these functions have a parameter named
1398 //               `unused_self`. Removing it requires #8888 to be fixed.
1399 pub trait Float: Signed + Primitive {
1400     /// Returns the NaN value.
1401     fn nan() -> Self;
1402     /// Returns the infinite value.
1403     fn infinity() -> Self;
1404     /// Returns the negative infinite value.
1405     fn neg_infinity() -> Self;
1406     /// Returns -0.0.
1407     fn neg_zero() -> Self;
1408
1409     /// Returns true if this value is NaN and false otherwise.
1410     fn is_nan(self) -> bool;
1411     /// Returns true if this value is positive infinity or negative infinity and
1412     /// false otherwise.
1413     fn is_infinite(self) -> bool;
1414     /// Returns true if this number is neither infinite nor NaN.
1415     fn is_finite(self) -> bool;
1416     /// Returns true if this number is neither zero, infinite, denormal, or NaN.
1417     fn is_normal(self) -> bool;
1418     /// Returns the category that this number falls into.
1419     fn classify(self) -> FPCategory;
1420
1421     // FIXME (#5527): These should be associated constants
1422
1423     /// Returns the number of binary digits of mantissa that this type supports.
1424     fn mantissa_digits(unused_self: Option<Self>) -> uint;
1425     /// Returns the number of base-10 digits of precision that this type supports.
1426     fn digits(unused_self: Option<Self>) -> uint;
1427     /// Returns the difference between 1.0 and the smallest representable number larger than 1.0.
1428     fn epsilon() -> Self;
1429     /// Returns the minimum binary exponent that this type can represent.
1430     fn min_exp(unused_self: Option<Self>) -> int;
1431     /// Returns the maximum binary exponent that this type can represent.
1432     fn max_exp(unused_self: Option<Self>) -> int;
1433     /// Returns the minimum base-10 exponent that this type can represent.
1434     fn min_10_exp(unused_self: Option<Self>) -> int;
1435     /// Returns the maximum base-10 exponent that this type can represent.
1436     fn max_10_exp(unused_self: Option<Self>) -> int;
1437     /// Returns the smallest normalized positive number that this type can represent.
1438     fn min_pos_value(unused_self: Option<Self>) -> Self;
1439
1440     /// Returns the mantissa, exponent and sign as integers, respectively.
1441     fn integer_decode(self) -> (u64, i16, i8);
1442
1443     /// Return the largest integer less than or equal to a number.
1444     fn floor(self) -> Self;
1445     /// Return the smallest integer greater than or equal to a number.
1446     fn ceil(self) -> Self;
1447     /// Return the nearest integer to a number. Round half-way cases away from
1448     /// `0.0`.
1449     fn round(self) -> Self;
1450     /// Return the integer part of a number.
1451     fn trunc(self) -> Self;
1452     /// Return the fractional part of a number.
1453     fn fract(self) -> Self;
1454
1455     /// Fused multiply-add. Computes `(self * a) + b` with only one rounding
1456     /// error. This produces a more accurate result with better performance than
1457     /// a separate multiplication operation followed by an add.
1458     fn mul_add(self, a: Self, b: Self) -> Self;
1459     /// Take the reciprocal (inverse) of a number, `1/x`.
1460     fn recip(self) -> Self;
1461
1462     /// Raise a number to an integer power.
1463     ///
1464     /// Using this function is generally faster than using `powf`
1465     fn powi(self, n: i32) -> Self;
1466     /// Raise a number to a floating point power.
1467     fn powf(self, n: Self) -> Self;
1468
1469     /// sqrt(2.0).
1470     fn sqrt2() -> Self;
1471     /// 1.0 / sqrt(2.0).
1472     fn frac_1_sqrt2() -> Self;
1473
1474     /// Take the square root of a number.
1475     fn sqrt(self) -> Self;
1476     /// Take the reciprocal (inverse) square root of a number, `1/sqrt(x)`.
1477     fn rsqrt(self) -> Self;
1478
1479     // FIXME (#5527): These should be associated constants
1480
1481     /// Archimedes' constant.
1482     fn pi() -> Self;
1483     /// 2.0 * pi.
1484     fn two_pi() -> Self;
1485     /// pi / 2.0.
1486     fn frac_pi_2() -> Self;
1487     /// pi / 3.0.
1488     fn frac_pi_3() -> Self;
1489     /// pi / 4.0.
1490     fn frac_pi_4() -> Self;
1491     /// pi / 6.0.
1492     fn frac_pi_6() -> Self;
1493     /// pi / 8.0.
1494     fn frac_pi_8() -> Self;
1495     /// 1.0 / pi.
1496     fn frac_1_pi() -> Self;
1497     /// 2.0 / pi.
1498     fn frac_2_pi() -> Self;
1499     /// 2.0 / sqrt(pi).
1500     fn frac_2_sqrtpi() -> Self;
1501
1502     /// Euler's number.
1503     fn e() -> Self;
1504     /// log2(e).
1505     fn log2_e() -> Self;
1506     /// log10(e).
1507     fn log10_e() -> Self;
1508     /// ln(2.0).
1509     fn ln_2() -> Self;
1510     /// ln(10.0).
1511     fn ln_10() -> Self;
1512
1513     /// Returns `e^(self)`, (the exponential function).
1514     fn exp(self) -> Self;
1515     /// Returns 2 raised to the power of the number, `2^(self)`.
1516     fn exp2(self) -> Self;
1517     /// Returns the natural logarithm of the number.
1518     fn ln(self) -> Self;
1519     /// Returns the logarithm of the number with respect to an arbitrary base.
1520     fn log(self, base: Self) -> Self;
1521     /// Returns the base 2 logarithm of the number.
1522     fn log2(self) -> Self;
1523     /// Returns the base 10 logarithm of the number.
1524     fn log10(self) -> Self;
1525
1526     /// Convert radians to degrees.
1527     fn to_degrees(self) -> Self;
1528     /// Convert degrees to radians.
1529     fn to_radians(self) -> Self;
1530 }