Add BitCount trait

15 files changed, 287 insertions, 16 deletions

diff --git a/src/libcore/core.rc b/src/libcore/core.rc
index 55cabad7412..b7d657669fe 100644
--- a/src/libcore/core.rc
+++ b/src/libcore/core.rc
@@ -106,7 +106,7 @@ pub use iter::{ExtendedMutableIter};
 pub use num::{Num, NumCast};
 pub use num::{Signed, Unsigned, Integer};
 pub use num::{Round, Fractional, Real, RealExt};
-pub use num::{Bitwise, Bounded};
+pub use num::{Bitwise, BitCount, Bounded};
 pub use num::{Primitive, PrimitiveInt};
 pub use num::{Int, Uint, Float};
 pub use ptr::Ptr;
diff --git a/src/libcore/num/int-template.rs b/src/libcore/num/int-template.rs
index 877767b5cbf..11dacdd4493 100644
--- a/src/libcore/num/int-template.rs
+++ b/src/libcore/num/int-template.rs
@@ -646,7 +646,7 @@ mod tests {
     }
 
     #[test]
-    fn test_bitwise_ops() {
+    fn test_bitwise() {
         assert_eq!(0b1110 as T, (0b1100 as T).bitor(&(0b1010 as T)));
         assert_eq!(0b1000 as T, (0b1100 as T).bitand(&(0b1010 as T)));
         assert_eq!(0b0110 as T, (0b1100 as T).bitxor(&(0b1010 as T)));
@@ -656,6 +656,11 @@ mod tests {
     }
 
     #[test]
+    fn test_bitcount() {
+        assert_eq!((0b010101 as T).population_count(), 3);
+    }
+
+    #[test]
     fn test_primitive() {
         assert_eq!(Primitive::bits::<T>(), sys::size_of::<T>() * 8);
         assert_eq!(Primitive::bytes::<T>(), sys::size_of::<T>());
diff --git a/src/libcore/num/int-template/i16.rs b/src/libcore/num/int-template/i16.rs
index d67017ec62d..28263378555 100644
--- a/src/libcore/num/int-template/i16.rs
+++ b/src/libcore/num/int-template/i16.rs
@@ -11,7 +11,8 @@
 //! Operations and constants for `i16`
 
 mod inst {
-    use num::Primitive;
+    use num::{Primitive, BitCount};
+    use unstable::intrinsics;
 
     pub type T = i16;
     pub static bits: uint = ::u16::bits;
@@ -23,4 +24,18 @@ mod inst {
         #[inline(always)]
         fn bytes() -> uint { Primitive::bits::<i16>() / 8 }
     }
+
+    impl BitCount for i16 {
+        /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+        #[inline(always)]
+        fn population_count(&self) -> i16 { unsafe { intrinsics::ctpop16(*self) } }
+
+        /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+        #[inline(always)]
+        fn leading_zeros(&self) -> i16 { unsafe { intrinsics::ctlz16(*self) } }
+
+        /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> i16 { unsafe { intrinsics::cttz16(*self) } }
+    }
 }
diff --git a/src/libcore/num/int-template/i32.rs b/src/libcore/num/int-template/i32.rs
index fe2014bd3e0..959cf8f7d77 100644
--- a/src/libcore/num/int-template/i32.rs
+++ b/src/libcore/num/int-template/i32.rs
@@ -11,7 +11,8 @@
 //! Operations and constants for `i32`
 
 mod inst {
-    use num::Primitive;
+    use num::{Primitive, BitCount};
+    use unstable::intrinsics;
 
     pub type T = i32;
     pub static bits: uint = ::u32::bits;
@@ -23,4 +24,18 @@ mod inst {
         #[inline(always)]
         fn bytes() -> uint { Primitive::bits::<i32>() / 8 }
     }
+
+    impl BitCount for i32 {
+        /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+        #[inline(always)]
+        fn population_count(&self) -> i32 { unsafe { intrinsics::ctpop32(*self) } }
+
+        /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+        #[inline(always)]
+        fn leading_zeros(&self) -> i32 { unsafe { intrinsics::ctlz32(*self) } }
+
+        /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> i32 { unsafe { intrinsics::cttz32(*self) } }
+    }
 }
diff --git a/src/libcore/num/int-template/i64.rs b/src/libcore/num/int-template/i64.rs
index 0b39b421dab..3b51c70be12 100644
--- a/src/libcore/num/int-template/i64.rs
+++ b/src/libcore/num/int-template/i64.rs
@@ -11,7 +11,8 @@
 //! Operations and constants for `i64`
 
 mod inst {
-    use num::Primitive;
+    use num::{Primitive, BitCount};
+    use unstable::intrinsics;
 
     pub type T = i64;
     pub static bits: uint = ::u64::bits;
@@ -23,4 +24,18 @@ mod inst {
         #[inline(always)]
         fn bytes() -> uint { Primitive::bits::<i64>() / 8 }
     }
+
+    impl BitCount for i64 {
+        /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+        #[inline(always)]
+        fn population_count(&self) -> i64 { unsafe { intrinsics::ctpop64(*self) } }
+
+        /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+        #[inline(always)]
+        fn leading_zeros(&self) -> i64 { unsafe { intrinsics::ctlz64(*self) } }
+
+        /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> i64 { unsafe { intrinsics::cttz64(*self) } }
+    }
 }
diff --git a/src/libcore/num/int-template/i8.rs b/src/libcore/num/int-template/i8.rs
index 0babd3779f1..896fb4dbf50 100644
--- a/src/libcore/num/int-template/i8.rs
+++ b/src/libcore/num/int-template/i8.rs
@@ -11,7 +11,8 @@
 //! Operations and constants for `i8`
 
 mod inst {
-    use num::Primitive;
+    use num::{Primitive, BitCount};
+    use unstable::intrinsics;
 
     pub type T = i8;
     pub static bits: uint = ::u8::bits;
@@ -23,4 +24,18 @@ mod inst {
         #[inline(always)]
         fn bytes() -> uint { Primitive::bits::<i8>() / 8 }
     }
+
+    impl BitCount for i8 {
+        /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+        #[inline(always)]
+        fn population_count(&self) -> i8 { unsafe { intrinsics::ctpop8(*self) } }
+
+        /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+        #[inline(always)]
+        fn leading_zeros(&self) -> i8 { unsafe { intrinsics::ctlz8(*self) } }
+
+        /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> i8 { unsafe { intrinsics::cttz8(*self) } }
+    }
 }
diff --git a/src/libcore/num/int-template/int.rs b/src/libcore/num/int-template/int.rs
index 3c179c554a8..bfe8bd0bfe6 100644
--- a/src/libcore/num/int-template/int.rs
+++ b/src/libcore/num/int-template/int.rs
@@ -13,7 +13,7 @@
 pub use self::inst::pow;
 
 mod inst {
-    use num::Primitive;
+    use num::{Primitive, BitCount};
 
     pub type T = int;
     pub static bits: uint = ::uint::bits;
@@ -31,12 +31,79 @@ mod inst {
         #[cfg(not(target_word_size = "32"),
               not(target_word_size = "64"))]
         #[inline(always)]
-        fn bits() -> uint { sys::size_of::<int>() * 8 }
+        fn bits() -> uint { ::sys::size_of::<int>() * 8 }
 
         #[inline(always)]
         fn bytes() -> uint { Primitive::bits::<int>() / 8 }
     }
 
+    #[cfg(target_word_size = "32")]
+    #[inline(always)]
+    impl BitCount for int {
+        /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+        #[inline(always)]
+        fn population_count(&self) -> int { (*self as i32).population_count() as uint }
+
+        /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+        #[inline(always)]
+        fn leading_zeros(&self) -> int { (*self as i32).leading_zeros() as uint }
+
+        /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> int { (*self as i32).trailing_zeros() as uint }
+    }
+
+    #[cfg(target_word_size = "64")]
+    #[inline(always)]
+    impl BitCount for int {
+        /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+        #[inline(always)]
+        fn population_count(&self) -> int { (*self as i64).population_count() as int }
+
+        /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+        #[inline(always)]
+        fn leading_zeros(&self) -> int { (*self as i64).leading_zeros() as int }
+
+        /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> int { (*self as i32).trailing_zeros() as int }
+    }
+
+    // fallback if we don't have access to the current word size
+    #[cfg(not(target_word_size = "32"),
+          not(target_word_size = "64"))]
+    impl BitCount for int {
+        /// Counts the number of bits set.
+        #[inline(always)]
+        fn population_count(&self) -> int {
+            match ::sys::size_of::<int>() {
+                8 => (*self as i64).population_count() as int,
+                4 => (*self as i32).population_count() as int,
+                s => fail!(fmt!("unsupported word size: %?", s)),
+            }
+        }
+
+        /// Counts the number of leading zeros.
+        #[inline(always)]
+        fn leading_zeros(&self) -> int {
+            match ::sys::size_of::<int>() {
+                8 => (*self as i64).leading_zeros() as int,
+                4 => (*self as i32).leading_zeros() as int,
+                s => fail!(fmt!("unsupported word size: %?", s)),
+            }
+        }
+
+        /// Counts the number of trailing zeros.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> int {
+            match ::sys::size_of::<int>() {
+                8 => (*self as i64).trailing_zeros() as int,
+                4 => (*self as i32).trailing_zeros() as int,
+                s => fail!(fmt!("unsupported word size: %?", s)),
+            }
+        }
+    }
+
     /// Returns `base` raised to the power of `exponent`
     pub fn pow(base: int, exponent: uint) -> int {
         if exponent == 0u {
diff --git a/src/libcore/num/num.rs b/src/libcore/num/num.rs
index 8e6128ceb97..cec5fe8cd28 100644
--- a/src/libcore/num/num.rs
+++ b/src/libcore/num/num.rs
@@ -184,6 +184,12 @@ pub trait Bitwise: Not<Self>
                  + Shl<Self,Self>
                  + Shr<Self,Self> {}
 
+pub trait BitCount {
+    fn population_count(&self) -> Self;
+    fn leading_zeros(&self) -> Self;
+    fn trailing_zeros(&self) -> Self;
+}
+
 pub trait Bounded {
     // FIXME (#5527): These should be associated constants
     fn min_value() -> Self;
@@ -214,7 +220,8 @@ pub trait Primitive: Num
 pub trait PrimitiveInt: Integer
                       + Primitive
                       + Bounded
-                      + Bitwise {}
+                      + Bitwise
+                      + BitCount {}
 
 ///
 /// Specialisation of `PrimitiveInt` for unsigned integers
diff --git a/src/libcore/num/uint-template.rs b/src/libcore/num/uint-template.rs
index 67a930c72a4..2e6c7e28b18 100644
--- a/src/libcore/num/uint-template.rs
+++ b/src/libcore/num/uint-template.rs
@@ -389,7 +389,7 @@ mod tests {
     }
 
     #[test]
-    fn test_bitwise_ops() {
+    fn test_bitwise() {
         assert_eq!(0b1110 as T, (0b1100 as T).bitor(&(0b1010 as T)));
         assert_eq!(0b1000 as T, (0b1100 as T).bitand(&(0b1010 as T)));
         assert_eq!(0b0110 as T, (0b1100 as T).bitxor(&(0b1010 as T)));
@@ -399,6 +399,11 @@ mod tests {
     }
 
     #[test]
+    fn test_bitcount() {
+        assert_eq!((0b010101 as T).population_count(), 3);
+    }
+
+    #[test]
     fn test_primitive() {
         assert_eq!(Primitive::bits::<T>(), sys::size_of::<T>() * 8);
         assert_eq!(Primitive::bytes::<T>(), sys::size_of::<T>());
diff --git a/src/libcore/num/uint-template/u16.rs b/src/libcore/num/uint-template/u16.rs
index fda731b7a18..cc262f6b4de 100644
--- a/src/libcore/num/uint-template/u16.rs
+++ b/src/libcore/num/uint-template/u16.rs
@@ -11,7 +11,8 @@
 //! Operations and constants for `u16`
 
 mod inst {
-    use num::Primitive;
+    use num::{Primitive, BitCount};
+    use unstable::intrinsics;
 
     pub type T = u16;
     #[allow(non_camel_case_types)]
@@ -25,4 +26,18 @@ mod inst {
         #[inline(always)]
         fn bytes() -> uint { Primitive::bits::<u16>() / 8 }
     }
+
+    impl BitCount for u16 {
+        /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+        #[inline(always)]
+        fn population_count(&self) -> u16 { unsafe { intrinsics::ctpop16(*self as i16) as u16 } }
+
+        /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+        #[inline(always)]
+        fn leading_zeros(&self) -> u16 { unsafe { intrinsics::ctlz16(*self as i16) as u16 } }
+
+        /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> u16 { unsafe { intrinsics::cttz16(*self as i16) as u16 } }
+    }
 }
diff --git a/src/libcore/num/uint-template/u32.rs b/src/libcore/num/uint-template/u32.rs
index 2ebf86a749f..7d7c8e3be30 100644
--- a/src/libcore/num/uint-template/u32.rs
+++ b/src/libcore/num/uint-template/u32.rs
@@ -11,7 +11,8 @@
 //! Operations and constants for `u32`
 
 mod inst {
-    use num::Primitive;
+    use num::{Primitive, BitCount};
+    use unstable::intrinsics;
 
     pub type T = u32;
     #[allow(non_camel_case_types)]
@@ -25,4 +26,18 @@ mod inst {
         #[inline(always)]
         fn bytes() -> uint { Primitive::bits::<u32>() / 8 }
     }
+
+    impl BitCount for u32 {
+        /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+        #[inline(always)]
+        fn population_count(&self) -> u32 { unsafe { intrinsics::ctpop32(*self as i32) as u32 } }
+
+        /// Counts the number of leading zeros. Wraps LLVM's `ctlp` intrinsic.
+        #[inline(always)]
+        fn leading_zeros(&self) -> u32 { unsafe { intrinsics::ctlz32(*self as i32) as u32 } }
+
+        /// Counts the number of trailing zeros. Wraps LLVM's `cttp` intrinsic.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> u32 { unsafe { intrinsics::cttz32(*self as i32) as u32 } }
+    }
 }
diff --git a/src/libcore/num/uint-template/u64.rs b/src/libcore/num/uint-template/u64.rs
index d34c6ced36f..756c29950c3 100644
--- a/src/libcore/num/uint-template/u64.rs
+++ b/src/libcore/num/uint-template/u64.rs
@@ -11,7 +11,8 @@
 //! Operations and constants for `u64`
 
 mod inst {
-    use num::Primitive;
+    use num::{Primitive, BitCount};
+    use unstable::intrinsics;
 
     pub type T = u64;
     #[allow(non_camel_case_types)]
@@ -25,4 +26,18 @@ mod inst {
         #[inline(always)]
         fn bytes() -> uint { Primitive::bits::<u64>() / 8 }
     }
+
+    impl BitCount for u64 {
+        /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+        #[inline(always)]
+        fn population_count(&self) -> u64 { unsafe { intrinsics::ctpop64(*self as i64) as u64 } }
+
+        /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+        #[inline(always)]
+        fn leading_zeros(&self) -> u64 { unsafe { intrinsics::ctlz64(*self as i64) as u64 } }
+
+        /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> u64 { unsafe { intrinsics::cttz64(*self as i64) as u64 } }
+    }
 }
diff --git a/src/libcore/num/uint-template/u8.rs b/src/libcore/num/uint-template/u8.rs
index 857a3f90caa..5ac860c0359 100644
--- a/src/libcore/num/uint-template/u8.rs
+++ b/src/libcore/num/uint-template/u8.rs
@@ -11,7 +11,8 @@
 //! Operations and constants for `u8`
 
 mod inst {
-    use num::Primitive;
+    use num::{Primitive, BitCount};
+    use unstable::intrinsics;
 
     pub type T = u8;
     #[allow(non_camel_case_types)]
@@ -25,4 +26,18 @@ mod inst {
         #[inline(always)]
         fn bytes() -> uint { Primitive::bits::<u8>() / 8 }
     }
+
+    impl BitCount for u8 {
+        /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+        #[inline(always)]
+        fn population_count(&self) -> u8 { unsafe { intrinsics::ctpop8(*self as i8) as u8 } }
+
+        /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+        #[inline(always)]
+        fn leading_zeros(&self) -> u8 { unsafe { intrinsics::ctlz8(*self as i8) as u8 } }
+
+        /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> u8 { unsafe { intrinsics::cttz8(*self as i8) as u8 } }
+    }
 }
diff --git a/src/libcore/num/uint-template/uint.rs b/src/libcore/num/uint-template/uint.rs
index df7d45f6201..9e10ed63968 100644
--- a/src/libcore/num/uint-template/uint.rs
+++ b/src/libcore/num/uint-template/uint.rs
@@ -18,7 +18,7 @@ pub use self::inst::{
 pub mod inst {
     use sys;
     use iter;
-    use num::Primitive;
+    use num::{Primitive, BitCount};
 
     pub type T = uint;
     #[allow(non_camel_case_types)]
@@ -51,6 +51,73 @@ pub mod inst {
         fn bytes() -> uint { Primitive::bits::<uint>() / 8 }
     }
 
+    #[cfg(target_word_size = "32")]
+    #[inline(always)]
+    impl BitCount for uint {
+        /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+        #[inline(always)]
+        fn population_count(&self) -> uint { (*self as i32).population_count() as uint }
+
+        /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+        #[inline(always)]
+        fn leading_zeros(&self) -> uint { (*self as i32).leading_zeros() as uint }
+
+        /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> uint { (*self as i32).trailing_zeros() as uint }
+    }
+
+    #[cfg(target_word_size = "64")]
+    #[inline(always)]
+    impl BitCount for uint {
+        /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+        #[inline(always)]
+        fn population_count(&self) -> uint { (*self as i64).population_count() as uint }
+
+        /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+        #[inline(always)]
+        fn leading_zeros(&self) -> uint { (*self as i64).leading_zeros() as uint }
+
+        /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> uint { (*self as i32).trailing_zeros() as uint }
+    }
+
+    // fallback if we don't have access to the current word size
+    #[cfg(not(target_word_size = "32"),
+          not(target_word_size = "64"))]
+    impl BitCount for uint {
+        /// Counts the number of bits set.
+        #[inline(always)]
+        fn population_count(&self) -> uint {
+            match sys::size_of::<uint>() {
+                8 => (*self as i64).population_count() as uint,
+                4 => (*self as i32).population_count() as uint,
+                s => fail!(fmt!("unsupported word size: %?", s)),
+            }
+        }
+
+        /// Counts the number of leading zeros.
+        #[inline(always)]
+        fn leading_zeros(&self) -> uint {
+            match sys::size_of::<uint>() {
+                8 => (*self as i64).leading_zeros() as uint,
+                4 => (*self as i32).leading_zeros() as uint,
+                s => fail!(fmt!("unsupported word size: %?", s)),
+            }
+        }
+
+        /// Counts the number of trailing zeros.
+        #[inline(always)]
+        fn trailing_zeros(&self) -> uint {
+            match sys::size_of::<uint>() {
+                8 => (*self as i64).trailing_zeros() as uint,
+                4 => (*self as i32).trailing_zeros() as uint,
+                s => fail!(fmt!("unsupported word size: %?", s)),
+            }
+        }
+    }
+
     ///
     /// Divide two numbers, return the result, rounded up.
     ///
diff --git a/src/libcore/prelude.rs b/src/libcore/prelude.rs
index fdae5298d7c..1ab6f8d4441 100644
--- a/src/libcore/prelude.rs
+++ b/src/libcore/prelude.rs
@@ -40,7 +40,7 @@ pub use iter::{Times, ExtendedMutableIter};
 pub use num::{Num, NumCast};
 pub use num::{Signed, Unsigned, Integer};
 pub use num::{Round, Fractional, Real, RealExt};
-pub use num::{Bitwise, Bounded};
+pub use num::{Bitwise, BitCount, Bounded};
 pub use num::{Primitive, PrimitiveInt};
 pub use num::{Int, Uint, Float};
 pub use path::GenericPath;