Minor fixes to Haddock markup
[ghc.git] / libraries / base / 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 /Since: 4.7.0.0/
154 -}
155 bitSizeMaybe :: a -> Maybe Int
156
157 {-| Return the number of bits in the type of the argument. The actual
158 value of the argument is ignored. The function 'bitSize' is
159 undefined for types that do not have a fixed bitsize, like 'Integer'.
160 -}
161 bitSize :: a -> Int
162
163 {-| Return 'True' if the argument is a signed type. The actual
164 value of the argument is ignored -}
165 isSigned :: a -> Bool
166
167 {-# INLINE setBit #-}
168 {-# INLINE clearBit #-}
169 {-# INLINE complementBit #-}
170 x `setBit` i = x .|. bit i
171 x `clearBit` i = x .&. complement (bit i)
172 x `complementBit` i = x `xor` bit i
173
174 {-| Shift the argument left by the specified number of bits
175 (which must be non-negative).
176
177 An instance can define either this and 'shiftR' or the unified
178 'shift', depending on which is more convenient for the type in
179 question. -}
180 shiftL :: a -> Int -> a
181 {-# INLINE shiftL #-}
182 x `shiftL` i = x `shift` i
183
184 {-| Shift the argument left by the specified number of bits. The
185 result is undefined for negative shift amounts and shift amounts
186 greater or equal to the 'bitSize'.
187
188 Defaults to 'shiftL' unless defined explicitly by an instance.
189
190 /Since: 4.5.0.0/ -}
191 unsafeShiftL :: a -> Int -> a
192 {-# INLINE unsafeShiftL #-}
193 x `unsafeShiftL` i = x `shiftL` i
194
195 {-| Shift the first argument right by the specified number of bits. The
196 result is undefined for negative shift amounts and shift amounts
197 greater or equal to the 'bitSize'.
198
199 Right shifts perform sign extension on signed number types;
200 i.e. they fill the top bits with 1 if the @x@ is negative
201 and with 0 otherwise.
202
203 An instance can define either this and 'shiftL' or the unified
204 'shift', depending on which is more convenient for the type in
205 question. -}
206 shiftR :: a -> Int -> a
207 {-# INLINE shiftR #-}
208 x `shiftR` i = x `shift` (-i)
209
210 {-| Shift the first argument right by the specified number of bits, which
211 must be non-negative an smaller than the number of bits in the type.
212
213 Right shifts perform sign extension on signed number types;
214 i.e. they fill the top bits with 1 if the @x@ is negative
215 and with 0 otherwise.
216
217 Defaults to 'shiftR' unless defined explicitly by an instance.
218
219 /Since: 4.5.0.0/ -}
220 unsafeShiftR :: a -> Int -> a
221 {-# INLINE unsafeShiftR #-}
222 x `unsafeShiftR` i = x `shiftR` i
223
224 {-| Rotate the argument left by the specified number of bits
225 (which must be non-negative).
226
227 An instance can define either this and 'rotateR' or the unified
228 'rotate', depending on which is more convenient for the type in
229 question. -}
230 rotateL :: a -> Int -> a
231 {-# INLINE rotateL #-}
232 x `rotateL` i = x `rotate` i
233
234 {-| Rotate the argument right by the specified number of bits
235 (which must be non-negative).
236
237 An instance can define either this and 'rotateL' or the unified
238 'rotate', depending on which is more convenient for the type in
239 question. -}
240 rotateR :: a -> Int -> a
241 {-# INLINE rotateR #-}
242 x `rotateR` i = x `rotate` (-i)
243
244 {-| Return the number of set bits in the argument. This number is
245 known as the population count or the Hamming weight.
246
247 /Since: 4.5.0.0/ -}
248 popCount :: a -> Int
249
250 {-# MINIMAL (.&.), (.|.), xor, complement,
251 (shift | (shiftL, shiftR)),
252 (rotate | (rotateL, rotateR)),
253 bitSize, bitSizeMaybe, isSigned, testBit, bit, popCount #-}
254
255 -- |The 'FiniteBits' class denotes types with a finite, fixed number of bits.
256 --
257 -- /Since: 4.7.0.0/
258 class Bits b => FiniteBits b where
259 -- | Return the number of bits in the type of the argument.
260 -- The actual value of the argument is ignored. Moreover, 'finiteBitSize'
261 -- is total, in contrast to the deprecated 'bitSize' function it replaces.
262 --
263 -- @
264 -- 'finiteBitSize' = 'bitSize'
265 -- 'bitSizeMaybe' = 'Just' . 'finiteBitSize'
266 -- @
267 --
268 -- /Since: 4.7.0.0/
269 finiteBitSize :: b -> Int
270
271 -- The defaults below are written with lambdas so that e.g.
272 -- bit = bitDefault
273 -- is fully applied, so inlining will happen
274
275 -- | Default implementation for 'bit'.
276 --
277 -- Note that: @bitDefault i = 1 `shiftL` i@
278 --
279 -- /Since: 4.6.0.0/
280 bitDefault :: (Bits a, Num a) => Int -> a
281 bitDefault = \i -> 1 `shiftL` i
282 {-# INLINE bitDefault #-}
283
284 -- | Default implementation for 'testBit'.
285 --
286 -- Note that: @testBitDefault x i = (x .&. bit i) /= 0@
287 --
288 -- /Since: 4.6.0.0/
289 testBitDefault :: (Bits a, Num a) => a -> Int -> Bool
290 testBitDefault = \x i -> (x .&. bit i) /= 0
291 {-# INLINE testBitDefault #-}
292
293 -- | Default implementation for 'popCount'.
294 --
295 -- This implementation is intentionally naive. Instances are expected to provide
296 -- an optimized implementation for their size.
297 --
298 -- /Since: 4.6.0.0/
299 popCountDefault :: (Bits a, Num a) => a -> Int
300 popCountDefault = go 0
301 where
302 go !c 0 = c
303 go c w = go (c+1) (w .&. (w - 1)) -- clear the least significant
304 {-# INLINABLE popCountDefault #-}
305
306
307 -- Interpret 'Bool' as 1-bit bit-field; /Since: 4.7.0.0/
308 instance Bits Bool where
309 (.&.) = (&&)
310
311 (.|.) = (||)
312
313 xor = (/=)
314
315 complement = not
316
317 shift x 0 = x
318 shift _ _ = False
319
320 rotate x _ = x
321
322 bit 0 = True
323 bit _ = False
324
325 testBit x 0 = x
326 testBit _ _ = False
327
328 bitSizeMaybe _ = Just 1
329
330 bitSize _ = 1
331
332 isSigned _ = False
333
334 popCount False = 0
335 popCount True = 1
336
337 instance FiniteBits Bool where
338 finiteBitSize _ = 1
339
340
341 instance Bits Int where
342 {-# INLINE shift #-}
343 {-# INLINE bit #-}
344 {-# INLINE testBit #-}
345
346 bit = bitDefault
347
348 testBit = testBitDefault
349
350 (I# x#) .&. (I# y#) = I# (x# `andI#` y#)
351 (I# x#) .|. (I# y#) = I# (x# `orI#` y#)
352 (I# x#) `xor` (I# y#) = I# (x# `xorI#` y#)
353 complement (I# x#) = I# (notI# x#)
354 (I# x#) `shift` (I# i#)
355 | isTrue# (i# >=# 0#) = I# (x# `iShiftL#` i#)
356 | otherwise = I# (x# `iShiftRA#` negateInt# i#)
357 (I# x#) `shiftL` (I# i#) = I# (x# `iShiftL#` i#)
358 (I# x#) `unsafeShiftL` (I# i#) = I# (x# `uncheckedIShiftL#` i#)
359 (I# x#) `shiftR` (I# i#) = I# (x# `iShiftRA#` i#)
360 (I# x#) `unsafeShiftR` (I# i#) = I# (x# `uncheckedIShiftRA#` i#)
361
362 {-# INLINE rotate #-} -- See Note [Constant folding for rotate]
363 (I# x#) `rotate` (I# i#) =
364 I# ((x# `uncheckedIShiftL#` i'#) `orI#` (x# `uncheckedIShiftRL#` (wsib -# i'#)))
365 where
366 !i'# = i# `andI#` (wsib -# 1#)
367 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
368 bitSizeMaybe i = Just (finiteBitSize i)
369 bitSize i = finiteBitSize i
370
371 popCount (I# x#) = I# (word2Int# (popCnt# (int2Word# x#)))
372
373 isSigned _ = True
374
375 instance FiniteBits Int where
376 finiteBitSize _ = WORD_SIZE_IN_BITS
377
378 instance Bits Word where
379 {-# INLINE shift #-}
380 {-# INLINE bit #-}
381 {-# INLINE testBit #-}
382
383 (W# x#) .&. (W# y#) = W# (x# `and#` y#)
384 (W# x#) .|. (W# y#) = W# (x# `or#` y#)
385 (W# x#) `xor` (W# y#) = W# (x# `xor#` y#)
386 complement (W# x#) = W# (x# `xor#` mb#)
387 where !(W# mb#) = maxBound
388 (W# x#) `shift` (I# i#)
389 | isTrue# (i# >=# 0#) = W# (x# `shiftL#` i#)
390 | otherwise = W# (x# `shiftRL#` negateInt# i#)
391 (W# x#) `shiftL` (I# i#) = W# (x# `shiftL#` i#)
392 (W# x#) `unsafeShiftL` (I# i#) = W# (x# `uncheckedShiftL#` i#)
393 (W# x#) `shiftR` (I# i#) = W# (x# `shiftRL#` i#)
394 (W# x#) `unsafeShiftR` (I# i#) = W# (x# `uncheckedShiftRL#` i#)
395 (W# x#) `rotate` (I# i#)
396 | isTrue# (i'# ==# 0#) = W# x#
397 | otherwise = W# ((x# `uncheckedShiftL#` i'#) `or#` (x# `uncheckedShiftRL#` (wsib -# i'#)))
398 where
399 !i'# = i# `andI#` (wsib -# 1#)
400 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
401 bitSizeMaybe i = Just (finiteBitSize i)
402 bitSize i = finiteBitSize i
403 isSigned _ = False
404 popCount (W# x#) = I# (word2Int# (popCnt# x#))
405 bit = bitDefault
406 testBit = testBitDefault
407
408 instance FiniteBits Word where
409 finiteBitSize _ = WORD_SIZE_IN_BITS
410
411 instance Bits Integer where
412 (.&.) = andInteger
413 (.|.) = orInteger
414 xor = xorInteger
415 complement = complementInteger
416 shift x i@(I# i#) | i >= 0 = shiftLInteger x i#
417 | otherwise = shiftRInteger x (negateInt# i#)
418 testBit x (I# i) = testBitInteger x i
419
420 bit = bitDefault
421 popCount = popCountDefault
422
423 rotate x i = shift x i -- since an Integer never wraps around
424
425 bitSizeMaybe _ = Nothing
426 bitSize _ = error "Data.Bits.bitSize(Integer)"
427 isSigned _ = True
428
429 {- Note [Constant folding for rotate]
430 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
431 The INLINE on the Int instance of rotate enables it to be constant
432 folded. For example:
433 sumU . mapU (`rotate` 3) . replicateU 10000000 $ (7 :: Int)
434 goes to:
435 Main.$wfold =
436 \ (ww_sO7 :: Int#) (ww1_sOb :: Int#) ->
437 case ww1_sOb of wild_XM {
438 __DEFAULT -> Main.$wfold (+# ww_sO7 56) (+# wild_XM 1);
439 10000000 -> ww_sO7
440 whereas before it was left as a call to $wrotate.
441
442 All other Bits instances seem to inline well enough on their
443 own to enable constant folding; for example 'shift':
444 sumU . mapU (`shift` 3) . replicateU 10000000 $ (7 :: Int)
445 goes to:
446 Main.$wfold =
447 \ (ww_sOb :: Int#) (ww1_sOf :: Int#) ->
448 case ww1_sOf of wild_XM {
449 __DEFAULT -> Main.$wfold (+# ww_sOb 56) (+# wild_XM 1);
450 10000000 -> ww_sOb
451 }
452 -}
453