Add support for bitreverse primop

    This commit includes the necessary changes in code and
    documentation to support a primop that reverses a word's
    bits. It also includes a test.

5 files changed, 133 insertions, 2 deletions

diff --git a/libraries/base/Data/Word.hs b/libraries/base/Data/Word.hs
index b341f9c4bc..df43b5ae06 100644
--- a/libraries/base/Data/Word.hs
+++ b/libraries/base/Data/Word.hs
@@ -25,6 +25,9 @@ module Data.Word
         -- * byte swapping
         byteSwap16, byteSwap32, byteSwap64,
 
+        -- * bit reversal
+
+        bitReverse8, bitReverse16, bitReverse32, bitReverse64
         -- * Notes
 
         -- $notes
diff --git a/libraries/base/GHC/Word.hs b/libraries/base/GHC/Word.hs
index e714392e9c..dcd9e16208 100644
--- a/libraries/base/GHC/Word.hs
+++ b/libraries/base/GHC/Word.hs
@@ -31,6 +31,12 @@ module GHC.Word (
     byteSwap32,
     byteSwap64,
 
+    -- * Bit reversal
+    bitReverse8,
+    bitReverse16,
+    bitReverse32,
+    bitReverse64,
+
     -- * Equality operators
     -- | See GHC.Classes#matching_overloaded_methods_in_rules
     eqWord, neWord, gtWord, geWord, ltWord, leWord,
@@ -1006,6 +1012,35 @@ byteSwap64 :: Word64 -> Word64
 byteSwap64 (W64# w#) = W64# (byteSwap# w#)
 #endif
 
+-- | Reverse the order of the bits in a 'Word8'.
+--
+-- @since 4.12.0.0
+bitReverse8 :: Word8 -> Word8
+bitReverse8 (W8# w#) = W8# (narrow8Word# (bitReverse8# w#))
+
+-- | Reverse the order of the bits in a 'Word16'.
+--
+-- @since 4.12.0.0
+bitReverse16 :: Word16 -> Word16
+bitReverse16 (W16# w#) = W16# (narrow16Word# (bitReverse16# w#))
+
+-- | Reverse the order of the bits in a 'Word32'.
+--
+-- @since 4.12.0.0
+bitReverse32 :: Word32 -> Word32
+bitReverse32 (W32# w#) = W32# (narrow32Word# (bitReverse32# w#))
+
+-- | Reverse the order of the bits in a 'Word64'.
+--
+-- @since 4.12.0.0
+#if WORD_SIZE_IN_BITS < 64
+bitReverse64 :: Word64 -> Word64
+bitReverse64 (W64# w#) = W64# (bitReverse64# w#)
+#else
+bitReverse64 :: Word64 -> Word64
+bitReverse64 (W64# w#) = W64# (bitReverse# w#)
+#endif
+
 -------------------------------------------------------------------------------
 
 {-# RULES
diff --git a/libraries/ghc-prim/cbits/bitrev.c b/libraries/ghc-prim/cbits/bitrev.c
new file mode 100644
index 0000000000..1d65ae9c04
--- /dev/null
+++ b/libraries/ghc-prim/cbits/bitrev.c
@@ -0,0 +1,81 @@
+#include "Rts.h"
+
+/*
+Note [Bit reversal primop]
+~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+There are two main ways of reversing the bit order of a word: bit twiddling
+and using a lookup table.
+See [this excellent](https://stackoverflow.com/questions/746171/most-efficient-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c this)
+Stack Overflow answer about bit order reversal for (much) more detail.
+(Link valid as of March 2019.)
+
+To summarize,
+
+    * the lookup table is faster, but much more memory-heavy e.g.
+      doing it for 64-bit words can take 64KB if only 16-bits are reversed at
+      a time.
+    * working directly with bits is slower (roughly on the same order of
+      magnitude as the previous alternative), but uses much less memory as
+      bit-wise operators aren't space-onerous.
+
+The code below uses the latter option. If in the future the performance of this
+primop must be improved, the information provided in this comment should be
+useful in making the decision of which changes to make.
+
+For more information on how the below bit-twiddling functions came to be, see
+[this](http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel)
+page.
+*/
+
+extern StgWord hs_bitrev8(StgWord x);
+StgWord
+hs_bitrev8(StgWord x)
+{
+  x = ((x >> 1) & 0x55) | ((x & 0x55) << 1 );
+  x = ((x >> 2) & 0x33) | ((x & 0x33) << 2 );
+  x = ((x >> 4) & 0x0F) | ((x & 0x0F) << 4 );
+  return x;
+}
+
+extern StgWord16 hs_bitrev16(StgWord16 x);
+StgWord16
+hs_bitrev16(StgWord16 x)
+{
+  x = ((x >> 1) & 0x5555) | ((x & 0x5555) << 1 );
+  x = ((x >> 2) & 0x3333) | ((x & 0x3333) << 2 );
+  x = ((x >> 4) & 0x0F0F) | ((x & 0x0F0F) << 4 );
+  x = ((x >> 8) & 0x00FF) | ((x & 0x00FF) << 8 );
+  return x;
+}
+
+extern StgWord32 hs_bitrev32(StgWord32 x);
+StgWord32
+hs_bitrev32(StgWord32 x)
+{
+  x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1 );
+  x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2 );
+  x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4 );
+  x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8 );
+  x = ( x >> 16             ) | ( x << 16              );
+  return x;
+}
+
+extern StgWord64 hs_bitrev64(StgWord64 x);
+StgWord64
+hs_bitrev64(StgWord64 x)
+{
+  // swap odd and even bits
+  x = ((x >> 1)  & 0x5555555555555555) | ((x & 0x5555555555555555) << 1 );
+  // swap consecutive pairs of bits
+  x = ((x >> 2)  & 0x3333333333333333) | ((x & 0x3333333333333333) << 2 );
+  // swap consecutive pairs of nibbles (a nibble is 4 bits)
+  x = ((x >> 4)  & 0x0F0F0F0F0F0F0F0F) | ((x & 0x0F0F0F0F0F0F0F0F) << 4 );
+  // swap consecutive pairs of bytes
+  x = ((x >> 8)  & 0x00FF00FF00FF00FF) | ((x & 0x00FF00FF00FF00FF) << 8 );
+  // swap consecutive pairs of 16-bit words
+  x = ((x >> 16) & 0x0000FFFF0000FFFF) | ((x & 0x0000FFFF0000FFFF) << 16);
+  // swap 32-bit long pairs
+  x = ( x >> 32                      ) | ( x << 32                      );
+  return x;
+}
\ No newline at end of file
diff --git a/libraries/ghc-prim/changelog.md b/libraries/ghc-prim/changelog.md
index 2298846cd1..2a19164d58 100644
--- a/libraries/ghc-prim/changelog.md
+++ b/libraries/ghc-prim/changelog.md
@@ -1,4 +1,4 @@
-## 0.6.1
+## 0.6.1 (edit as necessary)
 
 - Shipped with GHC 8.10.1
 
@@ -6,6 +6,17 @@
 
         closureSize# :: a -> Int#
 
+- Added to `GHC.Prim`:
+        bitReverse# :: Word# -> Word#
+        bitReverse8# :: Word# -> Word#
+        bitReverse16# :: Word# -> Word#
+        bitReverse32# :: Word# -> Word#
+        bitReverse64# :: Word# -> Word#
+
+  `bitReverse#` is a primop that, for a `Word` of 8, 16, 32 or 64 bits,
+  reverses the order of its bits e.g. `0b110001` becomes `0b100011`.
+  These primitives use optimized machine instructions when available.
+
 ## 0.6.0
 
 - Shipped with GHC 8.8.1
@@ -14,7 +25,7 @@
 
         traceBinaryEvent# :: Addr# -> Int# -> State# s -> State# s
 
-## 0.5.3 (edit as necessary)
+## 0.5.3
 
 - Shipped with GHC 8.6.1
 
diff --git a/libraries/ghc-prim/ghc-prim.cabal b/libraries/ghc-prim/ghc-prim.cabal
index b97d305e12..2f0b1b5ee5 100644
--- a/libraries/ghc-prim/ghc-prim.cabal
+++ b/libraries/ghc-prim/ghc-prim.cabal
@@ -69,6 +69,7 @@ Library
     c-sources:
         cbits/atomic.c
         cbits/bswap.c
+        cbits/bitrev.c
         cbits/clz.c
         cbits/ctz.c
         cbits/debug.c