{-# LANGUAGE CPP #-} #if __GLASGOW_HASKELL__ {-# LANGUAGE MagicHash #-} #endif #if !defined(TESTING) && defined(__GLASGOW_HASKELL__) {-# LANGUAGE Safe #-} #endif #include "containers.h" ----------------------------------------------------------------------------- -- | -- Module : Utils.Containers.Internal.BitUtil -- Copyright : (c) Clark Gaebel 2012 -- (c) Johan Tibel 2012 -- License : BSD-style -- Maintainer : libraries@haskell.org -- Portability : portable ----------------------------------------------------------------------------- -- -- = WARNING -- -- This module is considered __internal__. -- -- The Package Versioning Policy __does not apply__. -- -- The contents of this module may change __in any way whatsoever__ -- and __without any warning__ between minor versions of this package. -- -- Authors importing this module are expected to track development -- closely. module Utils.Containers.Internal.BitUtil ( bitcount , highestBitMask , shiftLL , shiftRL , wordSize ) where import Data.Bits (popCount, unsafeShiftL, unsafeShiftR , countLeadingZeros, finiteBitSize ) {---------------------------------------------------------------------- [bitcount] as posted by David F. Place to haskell-cafe on April 11, 2006, based on the code on http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan, where the following source is given: Published in 1988, the C Programming Language 2nd Ed. (by Brian W. Kernighan and Dennis M. Ritchie) mentions this in exercise 2-9. On April 19, 2006 Don Knuth pointed out to me that this method "was first published by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)" ----------------------------------------------------------------------} bitcount :: Int -> Word -> Int bitcount :: Int -> Word -> Int bitcount Int a Word x = Int a Int -> Int -> Int forall a. Num a => a -> a -> a + Word -> Int forall a. Bits a => a -> Int popCount Word x {-# INLINE bitcount #-} -- 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 :: Word -> Word highestBitMask :: Word -> Word highestBitMask Word w = Word -> Int -> Word shiftLL Word 1 (Int wordSize Int -> Int -> Int forall a. Num a => a -> a -> a - Int 1 Int -> Int -> Int forall a. Num a => a -> a -> a - Word -> Int forall b. FiniteBits b => b -> Int countLeadingZeros Word w) {-# INLINE highestBitMask #-} -- Right and left logical shifts. shiftRL, shiftLL :: Word -> Int -> Word shiftRL :: Word -> Int -> Word shiftRL = Word -> Int -> Word forall a. Bits a => a -> Int -> a unsafeShiftR shiftLL :: Word -> Int -> Word shiftLL = Word -> Int -> Word forall a. Bits a => a -> Int -> a unsafeShiftL {-# INLINE wordSize #-} wordSize :: Int wordSize :: Int wordSize = Word -> Int forall b. FiniteBits b => b -> Int finiteBitSize (Word 0 :: Word)