[commit: base] master: GHC.Event.IntMap.highestBitMap reimplementation (26b449e)

[Johan Tibell]

Repository : ssh://darcs.haskell.org//srv/darcs/packages/base

On branch  : master

http://hackage.haskell.org/trac/ghc/changeset/26b449ee3fbf02bc0cea109f967ef08070a4a97e

>---------------------------------------------------------------

commit 26b449ee3fbf02bc0cea109f967ef08070a4a97e
Author: Johan Tibell <johan.tibell at gmail.com>
Date:   Wed Dec 12 18:07:08 2012 -0800

    GHC.Event.IntMap.highestBitMap reimplementation
    
    Replaced the previous implementation due to licensing concerns. The new
    implementation is a reimplementation by Clark Gaebel, based on the
    public domain implementation at
    http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2

>---------------------------------------------------------------

 GHC/Event/IntMap.hs |   63 +++++++++++++-------------------------------------
 1 files changed, 17 insertions(+), 46 deletions(-)

diff --git a/GHC/Event/IntMap.hs b/GHC/Event/IntMap.hs
index 6c397e5..7e7814e 100644
--- a/GHC/Event/IntMap.hs
+++ b/GHC/Event/IntMap.hs
@@ -327,50 +327,21 @@ branchMask :: Prefix -> Prefix -> Mask
 branchMask p1 p2
     = intFromNat (highestBitMask (natFromInt p1 `xor` natFromInt p2))
 
-{-
-Finding the highest bit mask in a word [x] can be done efficiently in
-three ways:
-
-* convert to a floating point value and the mantissa tells us the
-  [log2(x)] that corresponds with the highest bit position. The mantissa
-  is retrieved either via the standard C function [frexp] or by some bit
-  twiddling on IEEE compatible numbers (float). Note that one needs to
-  use at least [double] precision for an accurate mantissa of 32 bit
-  numbers.
-
-* use bit twiddling, a logarithmic sequence of bitwise or's and shifts (bit).
-
-* use processor specific assembler instruction (asm).
-
-The most portable way would be [bit], but is it efficient enough?
-I have measured the cycle counts of the different methods on an AMD
-Athlon-XP 1800 (~ Pentium III 1.8Ghz) using the RDTSC instruction:
-
-highestBitMask: method  cycles
-                --------------
-                 frexp   200
-                 float    33
-                 bit      11
-                 asm      12
-
-Wow, the bit twiddling is on today's RISC like machines even faster
-than a single CISC instruction (BSR)!
--}
-
--- | @highestBitMask@ returns a word where only the highest bit is
--- set.  It is found by first setting all bits in lower positions than
--- the highest bit and than taking an exclusive or with the original
--- value.  Allthough the function may look expensive, GHC compiles
--- this into excellent C code that subsequently compiled into highly
--- efficient machine code. The algorithm is derived from Jorg Arndt's
--- FXT library.
-highestBitMask :: Nat -> Nat
-highestBitMask x0
-  = case (x0 .|. shiftRL x0 1) of
-     x1 -> case (x1 .|. shiftRL x1 2) of
-      x2 -> case (x2 .|. shiftRL x2 4) of
-       x3 -> case (x3 .|. shiftRL x3 8) of
-        x4 -> case (x4 .|. shiftRL x4 16) of
-         x5 -> case (x5 .|. shiftRL x5 32) of   -- for 64 bit platforms
-          x6 -> (x6 `xor` (shiftRL x6 1))
+-- The highestBitMask implementation is based on
+-- http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
+-- which has been put in the public domain.
 
+-- | Return a word where only the highest bit is set.
+highestBitMask :: Nat -> Nat
+highestBitMask x1 = let x2 = x1 .|. x1 `shiftR` 1
+                        x3 = x2 .|. x2 `shiftR` 2
+                        x4 = x3 .|. x3 `shiftR` 4
+                        x5 = x4 .|. x4 `shiftR` 8
+                        x6 = x5 .|. x5 `shiftR` 16
+#if !(WORD_SIZE_IN_BITS==32)
+                        x7 = x6 .|. x6 `shiftR` 32
+                     in x7 `xor` (x7 `shiftR` 1)
+#else
+                     in x6 `xor` (x6 `shiftR` 1)
+#endif
+{-# INLINE highestBitMask #-}