Rollup merge of #48573 - Amanieu:bitreverse2, r=sfackler

Add functions for reversing the bit pattern in an integer

I'm reviving PR #32798 now that the LLVM issues have been resolved.

> This adds the bitreverse intrinsic and adds a reverse_bits function to all integer types.

8 files changed, 120 insertions, 4 deletions

diff --git a/src/libcore/intrinsics.rs b/src/libcore/intrinsics.rs
index a05d67a304f..830ebad0654 100644
--- a/src/libcore/intrinsics.rs
+++ b/src/libcore/intrinsics.rs
@@ -1292,6 +1292,10 @@ extern "rust-intrinsic" {
     /// Reverses the bytes in an integer type `T`.
     pub fn bswap<T>(x: T) -> T;
 
+    /// Reverses the bits in an integer type `T`.
+    #[cfg(not(stage0))]
+    pub fn bitreverse<T>(x: T) -> T;
+
     /// Performs checked integer addition.
     /// The stabilized versions of this intrinsic are available on the integer
     /// primitives via the `overflowing_add` method. For example,
diff --git a/src/libcore/num/mod.rs b/src/libcore/num/mod.rs
index 59a67fff48c..a46ac2b5f0f 100644
--- a/src/libcore/num/mod.rs
+++ b/src/libcore/num/mod.rs
@@ -321,6 +321,33 @@ $EndFeature, "
             (self as $UnsignedT).swap_bytes() as Self
         }
 
+        /// Reverses the bit pattern of the integer.
+        ///
+        /// # Examples
+        ///
+        /// Please note that this example is shared between integer types.
+        /// Which explains why `i16` is used here.
+        ///
+        /// Basic usage:
+        ///
+        /// ```
+        /// #![feature(reverse_bits)]
+        ///
+        /// let n: i16 = 0b0000000_01010101;
+        /// assert_eq!(n, 85);
+        ///
+        /// let m = n.reverse_bits();
+        ///
+        /// assert_eq!(m as u16, 0b10101010_00000000);
+        /// assert_eq!(m, -22016);
+        /// ```
+        #[unstable(feature = "reverse_bits", issue = "48763")]
+        #[cfg(not(stage0))]
+        #[inline]
+        pub fn reverse_bits(self) -> Self {
+            (self as $UnsignedT).reverse_bits() as Self
+        }
+
         doc_comment! {
             concat!("Converts an integer from big endian to the target's endianness.
 
@@ -1773,6 +1800,33 @@ assert_eq!(n.trailing_zeros(), 3);", $EndFeature, "
             unsafe { intrinsics::bswap(self as $ActualT) as Self }
         }
 
+        /// Reverses the bit pattern of the integer.
+        ///
+        /// # Examples
+        ///
+        /// Basic usage:
+        ///
+        /// Please note that this example is shared between integer types.
+        /// Which explains why `u16` is used here.
+        ///
+        /// ```
+        /// #![feature(reverse_bits)]
+        ///
+        /// let n: u16 = 0b0000000_01010101;
+        /// assert_eq!(n, 85);
+        ///
+        /// let m = n.reverse_bits();
+        ///
+        /// assert_eq!(m, 0b10101010_00000000);
+        /// assert_eq!(m, 43520);
+        /// ```
+        #[unstable(feature = "reverse_bits", issue = "48763")]
+        #[cfg(not(stage0))]
+        #[inline]
+        pub fn reverse_bits(self) -> Self {
+            unsafe { intrinsics::bitreverse(self as $ActualT) as Self }
+        }
+
         doc_comment! {
             concat!("Converts an integer from big endian to the target's endianness.
 
diff --git a/src/libcore/tests/lib.rs b/src/libcore/tests/lib.rs
index 0049ed66a10..a9c5683e0ef 100644
--- a/src/libcore/tests/lib.rs
+++ b/src/libcore/tests/lib.rs
@@ -46,6 +46,7 @@
 #![feature(try_trait)]
 #![feature(exact_chunks)]
 #![feature(atomic_nand)]
+#![feature(reverse_bits)]
 
 extern crate core;
 extern crate test;
diff --git a/src/libcore/tests/num/uint_macros.rs b/src/libcore/tests/num/uint_macros.rs
index daa1cc3a7f4..ca6906f7310 100644
--- a/src/libcore/tests/num/uint_macros.rs
+++ b/src/libcore/tests/num/uint_macros.rs
@@ -98,6 +98,17 @@ mod tests {
     }
 
     #[test]
+    fn test_reverse_bits() {
+        assert_eq!(A.reverse_bits().reverse_bits(), A);
+        assert_eq!(B.reverse_bits().reverse_bits(), B);
+        assert_eq!(C.reverse_bits().reverse_bits(), C);
+
+        // Swapping these should make no difference
+        assert_eq!(_0.reverse_bits(), _0);
+        assert_eq!(_1.reverse_bits(), _1);
+    }
+
+    #[test]
     fn test_le() {
         assert_eq!($T::from_le(A.to_le()), A);
         assert_eq!($T::from_le(B.to_le()), B);
diff --git a/src/librustc_trans/context.rs b/src/librustc_trans/context.rs
index a285e5f263a..b93e8c2ad21 100644
--- a/src/librustc_trans/context.rs
+++ b/src/librustc_trans/context.rs
@@ -597,6 +597,12 @@ fn declare_intrinsic(cx: &CodegenCx, key: &str) -> Option<ValueRef> {
     ifn!("llvm.bswap.i64", fn(t_i64) -> t_i64);
     ifn!("llvm.bswap.i128", fn(t_i128) -> t_i128);
 
+    ifn!("llvm.bitreverse.i8", fn(t_i8) -> t_i8);
+    ifn!("llvm.bitreverse.i16", fn(t_i16) -> t_i16);
+    ifn!("llvm.bitreverse.i32", fn(t_i32) -> t_i32);
+    ifn!("llvm.bitreverse.i64", fn(t_i64) -> t_i64);
+    ifn!("llvm.bitreverse.i128", fn(t_i128) -> t_i128);
+
     ifn!("llvm.sadd.with.overflow.i8", fn(t_i8, t_i8) -> mk_struct!{t_i8, i1});
     ifn!("llvm.sadd.with.overflow.i16", fn(t_i16, t_i16) -> mk_struct!{t_i16, i1});
     ifn!("llvm.sadd.with.overflow.i32", fn(t_i32, t_i32) -> mk_struct!{t_i32, i1});
diff --git a/src/librustc_trans/intrinsic.rs b/src/librustc_trans/intrinsic.rs
index b1f1fb52c90..3f87ce7e047 100644
--- a/src/librustc_trans/intrinsic.rs
+++ b/src/librustc_trans/intrinsic.rs
@@ -287,8 +287,8 @@ pub fn trans_intrinsic_call<'a, 'tcx>(bx: &Builder<'a, 'tcx>,
             ], None)
         },
         "ctlz" | "ctlz_nonzero" | "cttz" | "cttz_nonzero" | "ctpop" | "bswap" |
-        "add_with_overflow" | "sub_with_overflow" | "mul_with_overflow" |
-        "overflowing_add" | "overflowing_sub" | "overflowing_mul" |
+        "bitreverse" | "add_with_overflow" | "sub_with_overflow" |
+        "mul_with_overflow" | "overflowing_add" | "overflowing_sub" | "overflowing_mul" |
         "unchecked_div" | "unchecked_rem" | "unchecked_shl" | "unchecked_shr" => {
             let ty = arg_tys[0];
             match int_type_width_signed(ty, cx) {
@@ -315,6 +315,10 @@ pub fn trans_intrinsic_call<'a, 'tcx>(bx: &Builder<'a, 'tcx>,
                                         &[args[0].immediate()], None)
                             }
                         }
+                        "bitreverse" => {
+                            bx.call(cx.get_intrinsic(&format!("llvm.bitreverse.i{}", width)),
+                                &[args[0].immediate()], None)
+                        }
                         "add_with_overflow" | "sub_with_overflow" | "mul_with_overflow" => {
                             let intrinsic = format!("llvm.{}{}.with.overflow.i{}",
                                                     if signed { 's' } else { 'u' },
diff --git a/src/librustc_typeck/check/intrinsic.rs b/src/librustc_typeck/check/intrinsic.rs
index 23243c3ad66..2e00040d99a 100644
--- a/src/librustc_typeck/check/intrinsic.rs
+++ b/src/librustc_typeck/check/intrinsic.rs
@@ -275,7 +275,8 @@ pub fn check_intrinsic_type<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
             "volatile_store" =>
                 (1, vec![ tcx.mk_mut_ptr(param(0)), param(0) ], tcx.mk_nil()),
 
-            "ctpop" | "ctlz" | "ctlz_nonzero" | "cttz" | "cttz_nonzero" | "bswap" =>
+            "ctpop" | "ctlz" | "ctlz_nonzero" | "cttz" | "cttz_nonzero" |
+            "bswap" | "bitreverse" =>
                 (1, vec![param(0)], param(0)),
 
             "add_with_overflow" | "sub_with_overflow"  | "mul_with_overflow" =>
diff --git a/src/test/run-pass/intrinsics-integer.rs b/src/test/run-pass/intrinsics-integer.rs
index 4896f02da20..bfa3a1e128a 100644
--- a/src/test/run-pass/intrinsics-integer.rs
+++ b/src/test/run-pass/intrinsics-integer.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-#![feature(intrinsics)]
+#![feature(intrinsics, i128_type)]
 
 mod rusti {
     extern "rust-intrinsic" {
@@ -18,6 +18,7 @@ mod rusti {
         pub fn cttz<T>(x: T) -> T;
         pub fn cttz_nonzero<T>(x: T) -> T;
         pub fn bswap<T>(x: T) -> T;
+        pub fn bitreverse<T>(x: T) -> T;
     }
 }
 
@@ -29,106 +30,127 @@ pub fn main() {
         assert_eq!(ctpop(0u16), 0); assert_eq!(ctpop(0i16), 0);
         assert_eq!(ctpop(0u32), 0); assert_eq!(ctpop(0i32), 0);
         assert_eq!(ctpop(0u64), 0); assert_eq!(ctpop(0i64), 0);
+        assert_eq!(ctpop(0u128), 0); assert_eq!(ctpop(0i128), 0);
 
         assert_eq!(ctpop(1u8), 1); assert_eq!(ctpop(1i8), 1);
         assert_eq!(ctpop(1u16), 1); assert_eq!(ctpop(1i16), 1);
         assert_eq!(ctpop(1u32), 1); assert_eq!(ctpop(1i32), 1);
         assert_eq!(ctpop(1u64), 1); assert_eq!(ctpop(1i64), 1);
+        assert_eq!(ctpop(1u128), 1); assert_eq!(ctpop(1i128), 1);
 
         assert_eq!(ctpop(10u8), 2); assert_eq!(ctpop(10i8), 2);
         assert_eq!(ctpop(10u16), 2); assert_eq!(ctpop(10i16), 2);
         assert_eq!(ctpop(10u32), 2); assert_eq!(ctpop(10i32), 2);
         assert_eq!(ctpop(10u64), 2); assert_eq!(ctpop(10i64), 2);
+        assert_eq!(ctpop(10u128), 2); assert_eq!(ctpop(10i128), 2);
 
         assert_eq!(ctpop(100u8), 3); assert_eq!(ctpop(100i8), 3);
         assert_eq!(ctpop(100u16), 3); assert_eq!(ctpop(100i16), 3);
         assert_eq!(ctpop(100u32), 3); assert_eq!(ctpop(100i32), 3);
         assert_eq!(ctpop(100u64), 3); assert_eq!(ctpop(100i64), 3);
+        assert_eq!(ctpop(100u128), 3); assert_eq!(ctpop(100i128), 3);
 
         assert_eq!(ctpop(-1i8 as u8), 8); assert_eq!(ctpop(-1i8), 8);
         assert_eq!(ctpop(-1i16 as u16), 16); assert_eq!(ctpop(-1i16), 16);
         assert_eq!(ctpop(-1i32 as u32), 32); assert_eq!(ctpop(-1i32), 32);
         assert_eq!(ctpop(-1i64 as u64), 64); assert_eq!(ctpop(-1i64), 64);
+        assert_eq!(ctpop(-1i128 as u128), 128); assert_eq!(ctpop(-1i128), 128);
 
         assert_eq!(ctlz(0u8), 8); assert_eq!(ctlz(0i8), 8);
         assert_eq!(ctlz(0u16), 16); assert_eq!(ctlz(0i16), 16);
         assert_eq!(ctlz(0u32), 32); assert_eq!(ctlz(0i32), 32);
         assert_eq!(ctlz(0u64), 64); assert_eq!(ctlz(0i64), 64);
+        assert_eq!(ctlz(0u128), 128); assert_eq!(ctlz(0i128), 128);
 
         assert_eq!(ctlz(1u8), 7); assert_eq!(ctlz(1i8), 7);
         assert_eq!(ctlz(1u16), 15); assert_eq!(ctlz(1i16), 15);
         assert_eq!(ctlz(1u32), 31); assert_eq!(ctlz(1i32), 31);
         assert_eq!(ctlz(1u64), 63); assert_eq!(ctlz(1i64), 63);
+        assert_eq!(ctlz(1u128), 127); assert_eq!(ctlz(1i128), 127);
 
         assert_eq!(ctlz(10u8), 4); assert_eq!(ctlz(10i8), 4);
         assert_eq!(ctlz(10u16), 12); assert_eq!(ctlz(10i16), 12);
         assert_eq!(ctlz(10u32), 28); assert_eq!(ctlz(10i32), 28);
         assert_eq!(ctlz(10u64), 60); assert_eq!(ctlz(10i64), 60);
+        assert_eq!(ctlz(10u128), 124); assert_eq!(ctlz(10i128), 124);
 
         assert_eq!(ctlz(100u8), 1); assert_eq!(ctlz(100i8), 1);
         assert_eq!(ctlz(100u16), 9); assert_eq!(ctlz(100i16), 9);
         assert_eq!(ctlz(100u32), 25); assert_eq!(ctlz(100i32), 25);
         assert_eq!(ctlz(100u64), 57); assert_eq!(ctlz(100i64), 57);
+        assert_eq!(ctlz(100u128), 121); assert_eq!(ctlz(100i128), 121);
 
         assert_eq!(ctlz_nonzero(1u8), 7); assert_eq!(ctlz_nonzero(1i8), 7);
         assert_eq!(ctlz_nonzero(1u16), 15); assert_eq!(ctlz_nonzero(1i16), 15);
         assert_eq!(ctlz_nonzero(1u32), 31); assert_eq!(ctlz_nonzero(1i32), 31);
         assert_eq!(ctlz_nonzero(1u64), 63); assert_eq!(ctlz_nonzero(1i64), 63);
+        assert_eq!(ctlz_nonzero(1u128), 127); assert_eq!(ctlz_nonzero(1i128), 127);
 
         assert_eq!(ctlz_nonzero(10u8), 4); assert_eq!(ctlz_nonzero(10i8), 4);
         assert_eq!(ctlz_nonzero(10u16), 12); assert_eq!(ctlz_nonzero(10i16), 12);
         assert_eq!(ctlz_nonzero(10u32), 28); assert_eq!(ctlz_nonzero(10i32), 28);
         assert_eq!(ctlz_nonzero(10u64), 60); assert_eq!(ctlz_nonzero(10i64), 60);
+        assert_eq!(ctlz_nonzero(10u128), 124); assert_eq!(ctlz_nonzero(10i128), 124);
 
         assert_eq!(ctlz_nonzero(100u8), 1); assert_eq!(ctlz_nonzero(100i8), 1);
         assert_eq!(ctlz_nonzero(100u16), 9); assert_eq!(ctlz_nonzero(100i16), 9);
         assert_eq!(ctlz_nonzero(100u32), 25); assert_eq!(ctlz_nonzero(100i32), 25);
         assert_eq!(ctlz_nonzero(100u64), 57); assert_eq!(ctlz_nonzero(100i64), 57);
+        assert_eq!(ctlz_nonzero(100u128), 121); assert_eq!(ctlz_nonzero(100i128), 121);
 
         assert_eq!(cttz(-1i8 as u8), 0); assert_eq!(cttz(-1i8), 0);
         assert_eq!(cttz(-1i16 as u16), 0); assert_eq!(cttz(-1i16), 0);
         assert_eq!(cttz(-1i32 as u32), 0); assert_eq!(cttz(-1i32), 0);
         assert_eq!(cttz(-1i64 as u64), 0); assert_eq!(cttz(-1i64), 0);
+        assert_eq!(cttz(-1i128 as u128), 0); assert_eq!(cttz(-1i128), 0);
 
         assert_eq!(cttz(0u8), 8); assert_eq!(cttz(0i8), 8);
         assert_eq!(cttz(0u16), 16); assert_eq!(cttz(0i16), 16);
         assert_eq!(cttz(0u32), 32); assert_eq!(cttz(0i32), 32);
         assert_eq!(cttz(0u64), 64); assert_eq!(cttz(0i64), 64);
+        assert_eq!(cttz(0u128), 128); assert_eq!(cttz(0i128), 128);
 
         assert_eq!(cttz(1u8), 0); assert_eq!(cttz(1i8), 0);
         assert_eq!(cttz(1u16), 0); assert_eq!(cttz(1i16), 0);
         assert_eq!(cttz(1u32), 0); assert_eq!(cttz(1i32), 0);
         assert_eq!(cttz(1u64), 0); assert_eq!(cttz(1i64), 0);
+        assert_eq!(cttz(1u128), 0); assert_eq!(cttz(1i128), 0);
 
         assert_eq!(cttz(10u8), 1); assert_eq!(cttz(10i8), 1);
         assert_eq!(cttz(10u16), 1); assert_eq!(cttz(10i16), 1);
         assert_eq!(cttz(10u32), 1); assert_eq!(cttz(10i32), 1);
         assert_eq!(cttz(10u64), 1); assert_eq!(cttz(10i64), 1);
+        assert_eq!(cttz(10u128), 1); assert_eq!(cttz(10i128), 1);
 
         assert_eq!(cttz(100u8), 2); assert_eq!(cttz(100i8), 2);
         assert_eq!(cttz(100u16), 2); assert_eq!(cttz(100i16), 2);
         assert_eq!(cttz(100u32), 2); assert_eq!(cttz(100i32), 2);
         assert_eq!(cttz(100u64), 2); assert_eq!(cttz(100i64), 2);
+        assert_eq!(cttz(100u128), 2); assert_eq!(cttz(100i128), 2);
 
         assert_eq!(cttz_nonzero(-1i8 as u8), 0); assert_eq!(cttz_nonzero(-1i8), 0);
         assert_eq!(cttz_nonzero(-1i16 as u16), 0); assert_eq!(cttz_nonzero(-1i16), 0);
         assert_eq!(cttz_nonzero(-1i32 as u32), 0); assert_eq!(cttz_nonzero(-1i32), 0);
         assert_eq!(cttz_nonzero(-1i64 as u64), 0); assert_eq!(cttz_nonzero(-1i64), 0);
+        assert_eq!(cttz_nonzero(-1i128 as u128), 0); assert_eq!(cttz_nonzero(-1i128), 0);
 
         assert_eq!(cttz_nonzero(1u8), 0); assert_eq!(cttz_nonzero(1i8), 0);
         assert_eq!(cttz_nonzero(1u16), 0); assert_eq!(cttz_nonzero(1i16), 0);
         assert_eq!(cttz_nonzero(1u32), 0); assert_eq!(cttz_nonzero(1i32), 0);
         assert_eq!(cttz_nonzero(1u64), 0); assert_eq!(cttz_nonzero(1i64), 0);
+        assert_eq!(cttz_nonzero(1u128), 0); assert_eq!(cttz_nonzero(1i128), 0);
 
         assert_eq!(cttz_nonzero(10u8), 1); assert_eq!(cttz_nonzero(10i8), 1);
         assert_eq!(cttz_nonzero(10u16), 1); assert_eq!(cttz_nonzero(10i16), 1);
         assert_eq!(cttz_nonzero(10u32), 1); assert_eq!(cttz_nonzero(10i32), 1);
         assert_eq!(cttz_nonzero(10u64), 1); assert_eq!(cttz_nonzero(10i64), 1);
+        assert_eq!(cttz_nonzero(10u128), 1); assert_eq!(cttz_nonzero(10i128), 1);
 
         assert_eq!(cttz_nonzero(100u8), 2); assert_eq!(cttz_nonzero(100i8), 2);
         assert_eq!(cttz_nonzero(100u16), 2); assert_eq!(cttz_nonzero(100i16), 2);
         assert_eq!(cttz_nonzero(100u32), 2); assert_eq!(cttz_nonzero(100i32), 2);
         assert_eq!(cttz_nonzero(100u64), 2); assert_eq!(cttz_nonzero(100i64), 2);
+        assert_eq!(cttz_nonzero(100u128), 2); assert_eq!(cttz_nonzero(100i128), 2);
 
         assert_eq!(bswap(0x0Au8), 0x0A); // no-op
         assert_eq!(bswap(0x0Ai8), 0x0A); // no-op
@@ -138,5 +160,18 @@ pub fn main() {
         assert_eq!(bswap(0x0ABBCC0Di32), 0x0DCCBB0A);
         assert_eq!(bswap(0x0122334455667708u64), 0x0877665544332201);
         assert_eq!(bswap(0x0122334455667708i64), 0x0877665544332201);
+        assert_eq!(bswap(0x0122334455667708u128), 0x08776655443322010000000000000000);
+        assert_eq!(bswap(0x0122334455667708i128), 0x08776655443322010000000000000000);
+
+        assert_eq!(bitreverse(0x0Au8), 0x50);
+        assert_eq!(bitreverse(0x0Ai8), 0x50);
+        assert_eq!(bitreverse(0x0A0Cu16), 0x3050);
+        assert_eq!(bitreverse(0x0A0Ci16), 0x3050);
+        assert_eq!(bitreverse(0x0ABBCC0Eu32), 0x7033DD50);
+        assert_eq!(bitreverse(0x0ABBCC0Ei32), 0x7033DD50);
+        assert_eq!(bitreverse(0x0122334455667708u64), 0x10EE66AA22CC4480);
+        assert_eq!(bitreverse(0x0122334455667708i64), 0x10EE66AA22CC4480);
+        assert_eq!(bitreverse(0x0122334455667708u128), 0x10EE66AA22CC44800000000000000000);
+        assert_eq!(bitreverse(0x0122334455667708i128), 0x10EE66AA22CC44800000000000000000);
     }
 }