01cbbe4f26bca28bba590501cfc5560f061adf2e
[packages/containers.git] / Utils / Containers / Internal / BitUtil.hs
1 {-# LANGUAGE CPP #-}
2 #if __GLASGOW_HASKELL__
3 {-# LANGUAGE MagicHash #-}
4 #endif
5 #if !defined(TESTING) && defined(__GLASGOW_HASKELL__)
6 {-# LANGUAGE Safe #-}
7 #endif
8
9 #include "containers.h"
10
11 -----------------------------------------------------------------------------
12 -- |
13 -- Module : Utils.Containers.Internal.BitUtil
14 -- Copyright : (c) Clark Gaebel 2012
15 -- (c) Johan Tibel 2012
16 -- License : BSD-style
17 -- Maintainer : libraries@haskell.org
18 -- Portability : portable
19 -----------------------------------------------------------------------------
20 --
21 -- = WARNING
22 --
23 -- This module is considered __internal__.
24 --
25 -- The Package Versioning Policy __does not apply__.
26 --
27 -- The contents of this module may change __in any way whatsoever__
28 -- and __without any warning__ between minor versions of this package.
29 --
30 -- Authors importing this module are expected to track development
31 -- closely.
32
33 module Utils.Containers.Internal.BitUtil
34 ( bitcount
35 , highestBitMask
36 , shiftLL
37 , shiftRL
38 , wordSize
39 ) where
40
41 import Data.Bits ((.|.), xor)
42 import Data.Bits (popCount, unsafeShiftL, unsafeShiftR
43 #if MIN_VERSION_base(4,8,0)
44 , countLeadingZeros
45 #endif
46 )
47 #if MIN_VERSION_base(4,7,0)
48 import Data.Bits (finiteBitSize)
49 #else
50 import Data.Bits (bitSize)
51 #endif
52
53 #if !MIN_VERSION_base (4,8,0)
54 import Data.Word (Word)
55 #endif
56
57 {----------------------------------------------------------------------
58 [bitcount] as posted by David F. Place to haskell-cafe on April 11, 2006,
59 based on the code on
60 http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan,
61 where the following source is given:
62 Published in 1988, the C Programming Language 2nd Ed. (by Brian W.
63 Kernighan and Dennis M. Ritchie) mentions this in exercise 2-9. On April
64 19, 2006 Don Knuth pointed out to me that this method "was first published
65 by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by
66 Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)"
67 ----------------------------------------------------------------------}
68
69 bitcount :: Int -> Word -> Int
70 bitcount a x = a + popCount x
71 {-# INLINE bitcount #-}
72
73 -- The highestBitMask implementation is based on
74 -- http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
75 -- which has been put in the public domain.
76
77 -- | Return a word where only the highest bit is set.
78 highestBitMask :: Word -> Word
79 #if MIN_VERSION_base(4,8,0)
80 highestBitMask w = shiftLL 1 (wordSize - 1 - countLeadingZeros w)
81 #else
82 highestBitMask x1 = let x2 = x1 .|. x1 `shiftRL` 1
83 x3 = x2 .|. x2 `shiftRL` 2
84 x4 = x3 .|. x3 `shiftRL` 4
85 x5 = x4 .|. x4 `shiftRL` 8
86 x6 = x5 .|. x5 `shiftRL` 16
87 #if !(defined(__GLASGOW_HASKELL__) && WORD_SIZE_IN_BITS==32)
88 x7 = x6 .|. x6 `shiftRL` 32
89 in x7 `xor` (x7 `shiftRL` 1)
90 #else
91 in x6 `xor` (x6 `shiftRL` 1)
92 #endif
93 #endif
94 {-# INLINE highestBitMask #-}
95
96 -- Right and left logical shifts.
97 shiftRL, shiftLL :: Word -> Int -> Word
98 shiftRL = unsafeShiftR
99 shiftLL = unsafeShiftL
100
101 {-# INLINE wordSize #-}
102 wordSize :: Int
103 #if MIN_VERSION_base(4,7,0)
104 wordSize = finiteBitSize (0 :: Word)
105 #else
106 wordSize = bitSize (0 :: Word)
107 #endif