e2eb3fe0cf997f4ef44d3865bd4f4ad2a2d7397a
[packages/base.git] / Data / Bits.hs
1 {-# LANGUAGE Trustworthy #-}
2 {-# LANGUAGE CPP, NoImplicitPrelude, BangPatterns, MagicHash #-}
3
4 -----------------------------------------------------------------------------
5 -- |
6 -- Module : Data.Bits
7 -- Copyright : (c) The University of Glasgow 2001
8 -- License : BSD-style (see the file libraries/base/LICENSE)
9 --
10 -- Maintainer : libraries@haskell.org
11 -- Stability : experimental
12 -- Portability : portable
13 --
14 -- This module defines bitwise operations for signed and unsigned
15 -- integers. Instances of the class 'Bits' for the 'Int' and
16 -- 'Integer' types are available from this module, and instances for
17 -- explicitly sized integral types are available from the
18 -- "Data.Int" and "Data.Word" modules.
19 --
20 -----------------------------------------------------------------------------
21
22 module Data.Bits (
23 Bits(
24 (.&.), (.|.), xor,
25 complement,
26 shift,
27 rotate,
28 bit,
29 setBit,
30 clearBit,
31 complementBit,
32 testBit,
33 bitSizeMaybe,
34 bitSize,
35 isSigned,
36 shiftL, shiftR,
37 unsafeShiftL, unsafeShiftR,
38 rotateL, rotateR,
39 popCount
40 ),
41 FiniteBits(finiteBitSize),
42
43 bitDefault,
44 testBitDefault,
45 popCountDefault
46 ) where
47
48 -- Defines the @Bits@ class containing bit-based operations.
49 -- See library document for details on the semantics of the
50 -- individual operations.
51
52 #include "MachDeps.h"
53
54 import Data.Maybe
55 import GHC.Enum
56 import GHC.Num
57 import GHC.Base
58
59 infixl 8 `shift`, `rotate`, `shiftL`, `shiftR`, `rotateL`, `rotateR`
60 infixl 7 .&.
61 infixl 6 `xor`
62 infixl 5 .|.
63
64 {-# DEPRECATED bitSize "Use bitSizeMaybe or finiteBitSize instead" #-} -- deprecated in 7.8
65
66 {-|
67 The 'Bits' class defines bitwise operations over integral types.
68
69 * Bits are numbered from 0 with bit 0 being the least
70 significant bit.
71
72 Minimal complete definition: '.&.', '.|.', 'xor', 'complement',
73 ('shift' or ('shiftL' and 'shiftR')), ('rotate' or ('rotateL' and 'rotateR')),
74 'bitSize', 'isSigned', 'testBit', 'bit', and 'popCount'. The latter three can
75 be implemented using `testBitDefault', 'bitDefault, and 'popCountDefault', if
76 @a@ is also an instance of 'Num'.
77 -}
78 class Eq a => Bits a where
79 -- | Bitwise \"and\"
80 (.&.) :: a -> a -> a
81
82 -- | Bitwise \"or\"
83 (.|.) :: a -> a -> a
84
85 -- | Bitwise \"xor\"
86 xor :: a -> a -> a
87
88 {-| Reverse all the bits in the argument -}
89 complement :: a -> a
90
91 {-| @'shift' x i@ shifts @x@ left by @i@ bits if @i@ is positive,
92 or right by @-i@ bits otherwise.
93 Right shifts perform sign extension on signed number types;
94 i.e. they fill the top bits with 1 if the @x@ is negative
95 and with 0 otherwise.
96
97 An instance can define either this unified 'shift' or 'shiftL' and
98 'shiftR', depending on which is more convenient for the type in
99 question. -}
100 shift :: a -> Int -> a
101
102 x `shift` i | i<0 = x `shiftR` (-i)
103 | i>0 = x `shiftL` i
104 | otherwise = x
105
106 {-| @'rotate' x i@ rotates @x@ left by @i@ bits if @i@ is positive,
107 or right by @-i@ bits otherwise.
108
109 For unbounded types like 'Integer', 'rotate' is equivalent to 'shift'.
110
111 An instance can define either this unified 'rotate' or 'rotateL' and
112 'rotateR', depending on which is more convenient for the type in
113 question. -}
114 rotate :: a -> Int -> a
115
116 x `rotate` i | i<0 = x `rotateR` (-i)
117 | i>0 = x `rotateL` i
118 | otherwise = x
119
120 {-
121 -- Rotation can be implemented in terms of two shifts, but care is
122 -- needed for negative values. This suggested implementation assumes
123 -- 2's-complement arithmetic. It is commented out because it would
124 -- require an extra context (Ord a) on the signature of 'rotate'.
125 x `rotate` i | i<0 && isSigned x && x<0
126 = let left = i+bitSize x in
127 ((x `shift` i) .&. complement ((-1) `shift` left))
128 .|. (x `shift` left)
129 | i<0 = (x `shift` i) .|. (x `shift` (i+bitSize x))
130 | i==0 = x
131 | i>0 = (x `shift` i) .|. (x `shift` (i-bitSize x))
132 -}
133
134 -- | @bit i@ is a value with the @i@th bit set and all other bits clear
135 bit :: Int -> a
136
137 -- | @x \`setBit\` i@ is the same as @x .|. bit i@
138 setBit :: a -> Int -> a
139
140 -- | @x \`clearBit\` i@ is the same as @x .&. complement (bit i)@
141 clearBit :: a -> Int -> a
142
143 -- | @x \`complementBit\` i@ is the same as @x \`xor\` bit i@
144 complementBit :: a -> Int -> a
145
146 -- | Return 'True' if the @n@th bit of the argument is 1
147 testBit :: a -> Int -> Bool
148
149 {-| Return the number of bits in the type of the argument. The actual
150 value of the argument is ignored. Returns Nothing
151 for types that do not have a fixed bitsize, like 'Integer'.
152 -}
153 bitSizeMaybe :: a -> Maybe Int
154
155 {-| Return the number of bits in the type of the argument. The actual
156 value of the argument is ignored. The function 'bitSize' is
157 undefined for types that do not have a fixed bitsize, like 'Integer'.
158 -}
159 bitSize :: a -> Int
160
161 {-| Return 'True' if the argument is a signed type. The actual
162 value of the argument is ignored -}
163 isSigned :: a -> Bool
164
165 {-# INLINE setBit #-}
166 {-# INLINE clearBit #-}
167 {-# INLINE complementBit #-}
168 x `setBit` i = x .|. bit i
169 x `clearBit` i = x .&. complement (bit i)
170 x `complementBit` i = x `xor` bit i
171
172 {-| Shift the argument left by the specified number of bits
173 (which must be non-negative).
174
175 An instance can define either this and 'shiftR' or the unified
176 'shift', depending on which is more convenient for the type in
177 question. -}
178 shiftL :: a -> Int -> a
179 {-# INLINE shiftL #-}
180 x `shiftL` i = x `shift` i
181
182 {-| Shift the argument left by the specified number of bits. The
183 result is undefined for negative shift amounts and shift amounts
184 greater or equal to the 'bitSize'.
185
186 Defaults to 'shiftL' unless defined explicitly by an instance. -}
187 unsafeShiftL :: a -> Int -> a
188 {-# INLINE unsafeShiftL #-}
189 x `unsafeShiftL` i = x `shiftL` i
190
191 {-| Shift the first argument right by the specified number of bits. The
192 result is undefined for negative shift amounts and shift amounts
193 greater or equal to the 'bitSize'.
194
195 Right shifts perform sign extension on signed number types;
196 i.e. they fill the top bits with 1 if the @x@ is negative
197 and with 0 otherwise.
198
199 An instance can define either this and 'shiftL' or the unified
200 'shift', depending on which is more convenient for the type in
201 question. -}
202 shiftR :: a -> Int -> a
203 {-# INLINE shiftR #-}
204 x `shiftR` i = x `shift` (-i)
205
206 {-| Shift the first argument right by the specified number of bits, which
207 must be non-negative an smaller than the number of bits in the type.
208
209 Right shifts perform sign extension on signed number types;
210 i.e. they fill the top bits with 1 if the @x@ is negative
211 and with 0 otherwise.
212
213 Defaults to 'shiftR' unless defined explicitly by an instance. -}
214 unsafeShiftR :: a -> Int -> a
215 {-# INLINE unsafeShiftR #-}
216 x `unsafeShiftR` i = x `shiftR` i
217
218 {-| Rotate the argument left by the specified number of bits
219 (which must be non-negative).
220
221 An instance can define either this and 'rotateR' or the unified
222 'rotate', depending on which is more convenient for the type in
223 question. -}
224 rotateL :: a -> Int -> a
225 {-# INLINE rotateL #-}
226 x `rotateL` i = x `rotate` i
227
228 {-| Rotate the argument right by the specified number of bits
229 (which must be non-negative).
230
231 An instance can define either this and 'rotateL' or the unified
232 'rotate', depending on which is more convenient for the type in
233 question. -}
234 rotateR :: a -> Int -> a
235 {-# INLINE rotateR #-}
236 x `rotateR` i = x `rotate` (-i)
237
238 {-| Return the number of set bits in the argument. This number is
239 known as the population count or the Hamming weight. -}
240 popCount :: a -> Int
241
242 class Bits b => FiniteBits b where
243 finiteBitSize :: b -> Int
244
245 -- The defaults below are written with lambdas so that e.g.
246 -- bit = bitDefault
247 -- is fully applied, so inlining will happen
248
249 -- | Default implementation for 'bit'.
250 --
251 -- Note that: @bitDefault i = 1 `shiftL` i@
252 bitDefault :: (Bits a, Num a) => Int -> a
253 bitDefault = \i -> 1 `shiftL` i
254 {-# INLINE bitDefault #-}
255
256 -- | Default implementation for 'testBit'.
257 --
258 -- Note that: @testBitDefault x i = (x .&. bit i) /= 0@
259 testBitDefault :: (Bits a, Num a) => a -> Int -> Bool
260 testBitDefault = \x i -> (x .&. bit i) /= 0
261 {-# INLINE testBitDefault #-}
262
263 -- | Default implementation for 'popCount'.
264 --
265 -- This implementation is intentionally naive. Instances are expected to provide
266 -- an optimized implementation for their size.
267 popCountDefault :: (Bits a, Num a) => a -> Int
268 popCountDefault = go 0
269 where
270 go !c 0 = c
271 go c w = go (c+1) (w .&. (w - 1)) -- clear the least significant
272 {-# INLINABLE popCountDefault #-}
273
274 instance Bits Int where
275 {-# INLINE shift #-}
276 {-# INLINE bit #-}
277 {-# INLINE testBit #-}
278
279 bit = bitDefault
280
281 testBit = testBitDefault
282
283 (I# x#) .&. (I# y#) = I# (word2Int# (int2Word# x# `and#` int2Word# y#))
284
285 (I# x#) .|. (I# y#) = I# (word2Int# (int2Word# x# `or#` int2Word# y#))
286
287 (I# x#) `xor` (I# y#) = I# (word2Int# (int2Word# x# `xor#` int2Word# y#))
288
289 complement (I# x#) = I# (word2Int# (int2Word# x# `xor#` int2Word# (-1#)))
290
291 (I# x#) `shift` (I# i#)
292 | i# >=# 0# = I# (x# `iShiftL#` i#)
293 | otherwise = I# (x# `iShiftRA#` negateInt# i#)
294 (I# x#) `shiftL` (I# i#) = I# (x# `iShiftL#` i#)
295 (I# x#) `unsafeShiftL` (I# i#) = I# (x# `uncheckedIShiftL#` i#)
296 (I# x#) `shiftR` (I# i#) = I# (x# `iShiftRA#` i#)
297 (I# x#) `unsafeShiftR` (I# i#) = I# (x# `uncheckedIShiftRA#` i#)
298
299 {-# INLINE rotate #-} -- See Note [Constant folding for rotate]
300 (I# x#) `rotate` (I# i#) =
301 I# (word2Int# ((x'# `uncheckedShiftL#` i'#) `or#`
302 (x'# `uncheckedShiftRL#` (wsib -# i'#))))
303 where
304 !x'# = int2Word# x#
305 !i'# = word2Int# (int2Word# i# `and#` int2Word# (wsib -# 1#))
306 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
307 bitSizeMaybe i = Just (finiteBitSize i)
308 bitSize i = finiteBitSize i
309
310 popCount (I# x#) = I# (word2Int# (popCnt# (int2Word# x#)))
311
312 isSigned _ = True
313
314 instance FiniteBits Int where
315 finiteBitSize _ = WORD_SIZE_IN_BITS
316
317 instance Bits Word where
318 {-# INLINE shift #-}
319 {-# INLINE bit #-}
320 {-# INLINE testBit #-}
321
322 (W# x#) .&. (W# y#) = W# (x# `and#` y#)
323 (W# x#) .|. (W# y#) = W# (x# `or#` y#)
324 (W# x#) `xor` (W# y#) = W# (x# `xor#` y#)
325 complement (W# x#) = W# (x# `xor#` mb#)
326 where !(W# mb#) = maxBound
327 (W# x#) `shift` (I# i#)
328 | i# >=# 0# = W# (x# `shiftL#` i#)
329 | otherwise = W# (x# `shiftRL#` negateInt# i#)
330 (W# x#) `shiftL` (I# i#) = W# (x# `shiftL#` i#)
331 (W# x#) `unsafeShiftL` (I# i#) = W# (x# `uncheckedShiftL#` i#)
332 (W# x#) `shiftR` (I# i#) = W# (x# `shiftRL#` i#)
333 (W# x#) `unsafeShiftR` (I# i#) = W# (x# `uncheckedShiftRL#` i#)
334 (W# x#) `rotate` (I# i#)
335 | i'# ==# 0# = W# x#
336 | otherwise = W# ((x# `uncheckedShiftL#` i'#) `or#` (x# `uncheckedShiftRL#` (wsib -# i'#)))
337 where
338 !i'# = word2Int# (int2Word# i# `and#` int2Word# (wsib -# 1#))
339 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
340 bitSizeMaybe i = Just (finiteBitSize i)
341 bitSize i = finiteBitSize i
342 isSigned _ = False
343 popCount (W# x#) = I# (word2Int# (popCnt# x#))
344 bit = bitDefault
345 testBit = testBitDefault
346
347 instance FiniteBits Word where
348 finiteBitSize _ = WORD_SIZE_IN_BITS
349
350 instance Bits Integer where
351 (.&.) = andInteger
352 (.|.) = orInteger
353 xor = xorInteger
354 complement = complementInteger
355 shift x i@(I# i#) | i >= 0 = shiftLInteger x i#
356 | otherwise = shiftRInteger x (negateInt# i#)
357 testBit x (I# i) = testBitInteger x i
358
359 bit = bitDefault
360 popCount = popCountDefault
361
362 rotate x i = shift x i -- since an Integer never wraps around
363
364 bitSizeMaybe _ = Nothing
365 bitSize _ = error "Data.Bits.bitSize(Integer)"
366 isSigned _ = True
367
368 {- Note [Constant folding for rotate]
369 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
370 The INLINE on the Int instance of rotate enables it to be constant
371 folded. For example:
372 sumU . mapU (`rotate` 3) . replicateU 10000000 $ (7 :: Int)
373 goes to:
374 Main.$wfold =
375 \ (ww_sO7 :: Int#) (ww1_sOb :: Int#) ->
376 case ww1_sOb of wild_XM {
377 __DEFAULT -> Main.$wfold (+# ww_sO7 56) (+# wild_XM 1);
378 10000000 -> ww_sO7
379 whereas before it was left as a call to $wrotate.
380
381 All other Bits instances seem to inline well enough on their
382 own to enable constant folding; for example 'shift':
383 sumU . mapU (`shift` 3) . replicateU 10000000 $ (7 :: Int)
384 goes to:
385 Main.$wfold =
386 \ (ww_sOb :: Int#) (ww1_sOf :: Int#) ->
387 case ww1_sOf of wild_XM {
388 __DEFAULT -> Main.$wfold (+# ww_sOb 56) (+# wild_XM 1);
389 10000000 -> ww_sOb
390 }
391 -}
392