[Haskell-cafe] The Marriage of Heaven and Hell: Type Classes and Bit-Twiddling

[David F. Place]

Hi:

Looking around further for a charming way to count bits, I found a  
method that is completely inscrutable might be very fast.

http://graphics.stanford.edu/~seander/bithacks.html
Counting bits set in 12, 24, or 32-bit words using 64-bit instructions

I thought it would be neat to have size function constrained to  
members of Bounded that would automatically choose which method  
depending on the extent of the domain of the set.  So, a small set  
could be computed by the very fast method and the compiler would be  
able to do the dispatch as part of constant folding.

This is what I came up with.  It works, but it seems kind of forced.   
I wonder if there is a better way.

sizeB :: (Bounded a,Enum a) => a -> Set a -> Int
sizeB e =
     case fromEnum $ maxBound `asTypeOf` e of
       x | x <= 12 -> \(Set w) -> fromIntegral $ c12 $ fromIntegral w
       x | x <= 24 -> \(Set w) -> fromIntegral $ c24 $ fromIntegral w
       x | x <= 32 -> \(Set w) -> fromIntegral $ c32 $ fromIntegral w
       _ -> \(Set w) -> bitcount 0 w

c12 :: Word64 -> Word64
c12 v = (v * 0x1001001001001 .&. 0x84210842108421) `rem` 0x1f
c24' :: Word64 -> Word64
c24' v = ((v .&. 0xfff) * 0x1001001001001 .&. 0x84210842108421) `rem`  
0x1f
c24 :: Word64 -> Word64
c24 v = (c24' v) + ((((v .&. 0xfff000) `shiftR` 12) *  
0x1001001001001 .&. 0x84210842108421) `rem` 0x1f)
c32 :: Word64 -> Word64
c32 v = (c24 v) + (((v `shiftR` 24) * 0x1001001001001 .&.  
0x84210842108421) `rem` 0x1f)

For example:

data Test1 = Foo | Bar | Baaz | Quux deriving (Enum, Bounded)

sizeTest1 :: (Set Test1) -> Int
sizeTest1 = sizeB Foo

Cheers, David

--------------------------------
David F. Place
mailto:d at vidplace.com