`M-x delete-trailing-whitespace` & `M-x untabify`...
[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 zeroBits,
29 bit,
30 setBit,
31 clearBit,
32 complementBit,
33 testBit,
34 bitSizeMaybe,
35 bitSize,
36 isSigned,
37 shiftL, shiftR,
38 unsafeShiftL, unsafeShiftR,
39 rotateL, rotateR,
40 popCount
41 ),
42 FiniteBits(
43 finiteBitSize,
44 countLeadingZeros,
45 countTrailingZeros
46 ),
47
48 bitDefault,
49 testBitDefault,
50 popCountDefault
51 ) where
52
53 -- Defines the @Bits@ class containing bit-based operations.
54 -- See library document for details on the semantics of the
55 -- individual operations.
56
57 #include "MachDeps.h"
58
59 import Data.Maybe
60 import GHC.Enum
61 import GHC.Num
62 import GHC.Base
63
64 infixl 8 `shift`, `rotate`, `shiftL`, `shiftR`, `rotateL`, `rotateR`
65 infixl 7 .&.
66 infixl 6 `xor`
67 infixl 5 .|.
68
69 {-# DEPRECATED bitSize "Use 'bitSizeMaybe' or 'finiteBitSize' instead" #-} -- deprecated in 7.8
70
71 {-|
72 The 'Bits' class defines bitwise operations over integral types.
73
74 * Bits are numbered from 0 with bit 0 being the least
75 significant bit.
76
77 Minimal complete definition: '.&.', '.|.', 'xor', 'complement',
78 ('shift' or ('shiftL' and 'shiftR')), ('rotate' or ('rotateL' and 'rotateR')),
79 'bitSize', 'isSigned', 'testBit', 'bit', and 'popCount'. The latter three can
80 be implemented using `testBitDefault', 'bitDefault', and 'popCountDefault', if
81 @a@ is also an instance of 'Num'.
82 -}
83 class Eq a => Bits a where
84 -- | Bitwise \"and\"
85 (.&.) :: a -> a -> a
86
87 -- | Bitwise \"or\"
88 (.|.) :: a -> a -> a
89
90 -- | Bitwise \"xor\"
91 xor :: a -> a -> a
92
93 {-| Reverse all the bits in the argument -}
94 complement :: a -> a
95
96 {-| @'shift' x i@ shifts @x@ left by @i@ bits if @i@ is positive,
97 or right by @-i@ bits otherwise.
98 Right shifts perform sign extension on signed number types;
99 i.e. they fill the top bits with 1 if the @x@ is negative
100 and with 0 otherwise.
101
102 An instance can define either this unified 'shift' or 'shiftL' and
103 'shiftR', depending on which is more convenient for the type in
104 question. -}
105 shift :: a -> Int -> a
106
107 x `shift` i | i<0 = x `shiftR` (-i)
108 | i>0 = x `shiftL` i
109 | otherwise = x
110
111 {-| @'rotate' x i@ rotates @x@ left by @i@ bits if @i@ is positive,
112 or right by @-i@ bits otherwise.
113
114 For unbounded types like 'Integer', 'rotate' is equivalent to 'shift'.
115
116 An instance can define either this unified 'rotate' or 'rotateL' and
117 'rotateR', depending on which is more convenient for the type in
118 question. -}
119 rotate :: a -> Int -> a
120
121 x `rotate` i | i<0 = x `rotateR` (-i)
122 | i>0 = x `rotateL` i
123 | otherwise = x
124
125 {-
126 -- Rotation can be implemented in terms of two shifts, but care is
127 -- needed for negative values. This suggested implementation assumes
128 -- 2's-complement arithmetic. It is commented out because it would
129 -- require an extra context (Ord a) on the signature of 'rotate'.
130 x `rotate` i | i<0 && isSigned x && x<0
131 = let left = i+bitSize x in
132 ((x `shift` i) .&. complement ((-1) `shift` left))
133 .|. (x `shift` left)
134 | i<0 = (x `shift` i) .|. (x `shift` (i+bitSize x))
135 | i==0 = x
136 | i>0 = (x `shift` i) .|. (x `shift` (i-bitSize x))
137 -}
138
139 -- | 'zeroBits' is the value with all bits unset.
140 --
141 -- The following laws ought to hold (for all valid bit indices @/n/@):
142 --
143 -- * @'clearBit' 'zeroBits' /n/ == 'zeroBits'@
144 -- * @'setBit' 'zeroBits' /n/ == 'bit' /n/@
145 -- * @'testBit' 'zeroBits' /n/ == False@
146 -- * @'popCount' 'zeroBits' == 0@
147 --
148 -- This method uses @'clearBit' ('bit' 0) 0@ as its default
149 -- implementation (which ought to be equivalent to 'zeroBits' for
150 -- types which possess a 0th bit).
151 --
152 -- /Since: 4.7.0.0/
153 zeroBits :: a
154 zeroBits = clearBit (bit 0) 0
155
156 -- | @bit /i/@ is a value with the @/i/@th bit set and all other bits clear.
157 --
158 -- See also 'zeroBits'.
159 bit :: Int -> a
160
161 -- | @x \`setBit\` i@ is the same as @x .|. bit i@
162 setBit :: a -> Int -> a
163
164 -- | @x \`clearBit\` i@ is the same as @x .&. complement (bit i)@
165 clearBit :: a -> Int -> a
166
167 -- | @x \`complementBit\` i@ is the same as @x \`xor\` bit i@
168 complementBit :: a -> Int -> a
169
170 -- | Return 'True' if the @n@th bit of the argument is 1
171 testBit :: a -> Int -> Bool
172
173 {-| Return the number of bits in the type of the argument. The actual
174 value of the argument is ignored. Returns Nothing
175 for types that do not have a fixed bitsize, like 'Integer'.
176
177 /Since: 4.7.0.0/
178 -}
179 bitSizeMaybe :: a -> Maybe Int
180
181 {-| Return the number of bits in the type of the argument. The actual
182 value of the argument is ignored. The function 'bitSize' is
183 undefined for types that do not have a fixed bitsize, like 'Integer'.
184 -}
185 bitSize :: a -> Int
186
187 {-| Return 'True' if the argument is a signed type. The actual
188 value of the argument is ignored -}
189 isSigned :: a -> Bool
190
191 {-# INLINE setBit #-}
192 {-# INLINE clearBit #-}
193 {-# INLINE complementBit #-}
194 x `setBit` i = x .|. bit i
195 x `clearBit` i = x .&. complement (bit i)
196 x `complementBit` i = x `xor` bit i
197
198 {-| Shift the argument left by the specified number of bits
199 (which must be non-negative).
200
201 An instance can define either this and 'shiftR' or the unified
202 'shift', depending on which is more convenient for the type in
203 question. -}
204 shiftL :: a -> Int -> a
205 {-# INLINE shiftL #-}
206 x `shiftL` i = x `shift` i
207
208 {-| Shift the argument left by the specified number of bits. The
209 result is undefined for negative shift amounts and shift amounts
210 greater or equal to the 'bitSize'.
211
212 Defaults to 'shiftL' unless defined explicitly by an instance.
213
214 /Since: 4.5.0.0/ -}
215 unsafeShiftL :: a -> Int -> a
216 {-# INLINE unsafeShiftL #-}
217 x `unsafeShiftL` i = x `shiftL` i
218
219 {-| Shift the first argument right by the specified number of bits. The
220 result is undefined for negative shift amounts and shift amounts
221 greater or equal to the 'bitSize'.
222
223 Right shifts perform sign extension on signed number types;
224 i.e. they fill the top bits with 1 if the @x@ is negative
225 and with 0 otherwise.
226
227 An instance can define either this and 'shiftL' or the unified
228 'shift', depending on which is more convenient for the type in
229 question. -}
230 shiftR :: a -> Int -> a
231 {-# INLINE shiftR #-}
232 x `shiftR` i = x `shift` (-i)
233
234 {-| Shift the first argument right by the specified number of bits, which
235 must be non-negative an smaller than the number of bits in the type.
236
237 Right shifts perform sign extension on signed number types;
238 i.e. they fill the top bits with 1 if the @x@ is negative
239 and with 0 otherwise.
240
241 Defaults to 'shiftR' unless defined explicitly by an instance.
242
243 /Since: 4.5.0.0/ -}
244 unsafeShiftR :: a -> Int -> a
245 {-# INLINE unsafeShiftR #-}
246 x `unsafeShiftR` i = x `shiftR` i
247
248 {-| Rotate the argument left by the specified number of bits
249 (which must be non-negative).
250
251 An instance can define either this and 'rotateR' or the unified
252 'rotate', depending on which is more convenient for the type in
253 question. -}
254 rotateL :: a -> Int -> a
255 {-# INLINE rotateL #-}
256 x `rotateL` i = x `rotate` i
257
258 {-| Rotate the argument right by the specified number of bits
259 (which must be non-negative).
260
261 An instance can define either this and 'rotateL' or the unified
262 'rotate', depending on which is more convenient for the type in
263 question. -}
264 rotateR :: a -> Int -> a
265 {-# INLINE rotateR #-}
266 x `rotateR` i = x `rotate` (-i)
267
268 {-| Return the number of set bits in the argument. This number is
269 known as the population count or the Hamming weight.
270
271 /Since: 4.5.0.0/ -}
272 popCount :: a -> Int
273
274 {-# MINIMAL (.&.), (.|.), xor, complement,
275 (shift | (shiftL, shiftR)),
276 (rotate | (rotateL, rotateR)),
277 bitSize, bitSizeMaybe, isSigned, testBit, bit, popCount #-}
278
279 -- |The 'FiniteBits' class denotes types with a finite, fixed number of bits.
280 --
281 -- /Since: 4.7.0.0/
282 class Bits b => FiniteBits b where
283 -- | Return the number of bits in the type of the argument.
284 -- The actual value of the argument is ignored. Moreover, 'finiteBitSize'
285 -- is total, in contrast to the deprecated 'bitSize' function it replaces.
286 --
287 -- @
288 -- 'finiteBitSize' = 'bitSize'
289 -- 'bitSizeMaybe' = 'Just' . 'finiteBitSize'
290 -- @
291 --
292 -- /Since: 4.7.0.0/
293 finiteBitSize :: b -> Int
294
295 -- | Count number of zero bits preceding the most significant set bit.
296 --
297 -- @
298 -- 'countLeadingZeros' ('zeroBits' :: a) = finiteBitSize ('zeroBits' :: a)
299 -- 'countLeadingZeros' . 'negate' = 'const' 0
300 -- @
301 --
302 -- 'countLeadingZeros' can be used to compute log base 2 via
303 --
304 -- @
305 -- logBase2 x = 'finiteBitSize' x - 1 - 'countLeadingZeros' x
306 -- @
307 --
308 -- Note: The default implementation for this method is intentionally
309 -- naive. However, the instances provided for the primitive
310 -- integral types are implemented using CPU specific machine
311 -- instructions.
312 --
313 -- /Since: 4.8.0.0/
314 countLeadingZeros :: b -> Int
315 countLeadingZeros x = (w-1) - go (w-1)
316 where
317 go i | i < 0 = i -- no bit set
318 | testBit x i = i
319 | otherwise = go (i-1)
320
321 w = finiteBitSize x
322
323 -- | Count number of zero bits following the least significant set bit.
324 --
325 -- @
326 -- 'countTrailingZeros' ('zeroBits' :: a) = finiteBitSize ('zeroBits' :: a)
327 -- 'countTrailingZeros' . 'negate' = 'countTrailingZeros'
328 -- @
329 --
330 -- The related
331 -- <http://en.wikipedia.org/wiki/Find_first_set find-first-set operation>
332 -- can be expressed in terms of 'countTrailingZeros' as follows
333 --
334 -- @
335 -- findFirstSet x = 1 + 'countTrailingZeros' x
336 -- @
337 --
338 -- Note: The default implementation for this method is intentionally
339 -- naive. However, the instances provided for the primitive
340 -- integral types are implemented using CPU specific machine
341 -- instructions.
342 --
343 -- /Since: 4.8.0.0/
344 countTrailingZeros :: b -> Int
345 countTrailingZeros x = go 0
346 where
347 go i | i >= w = i
348 | testBit x i = i
349 | otherwise = go (i+1)
350
351 w = finiteBitSize x
352
353
354 -- The defaults below are written with lambdas so that e.g.
355 -- bit = bitDefault
356 -- is fully applied, so inlining will happen
357
358 -- | Default implementation for 'bit'.
359 --
360 -- Note that: @bitDefault i = 1 `shiftL` i@
361 --
362 -- /Since: 4.6.0.0/
363 bitDefault :: (Bits a, Num a) => Int -> a
364 bitDefault = \i -> 1 `shiftL` i
365 {-# INLINE bitDefault #-}
366
367 -- | Default implementation for 'testBit'.
368 --
369 -- Note that: @testBitDefault x i = (x .&. bit i) /= 0@
370 --
371 -- /Since: 4.6.0.0/
372 testBitDefault :: (Bits a, Num a) => a -> Int -> Bool
373 testBitDefault = \x i -> (x .&. bit i) /= 0
374 {-# INLINE testBitDefault #-}
375
376 -- | Default implementation for 'popCount'.
377 --
378 -- This implementation is intentionally naive. Instances are expected to provide
379 -- an optimized implementation for their size.
380 --
381 -- /Since: 4.6.0.0/
382 popCountDefault :: (Bits a, Num a) => a -> Int
383 popCountDefault = go 0
384 where
385 go !c 0 = c
386 go c w = go (c+1) (w .&. (w - 1)) -- clear the least significant
387 {-# INLINABLE popCountDefault #-}
388
389
390 -- Interpret 'Bool' as 1-bit bit-field; /Since: 4.7.0.0/
391 instance Bits Bool where
392 (.&.) = (&&)
393
394 (.|.) = (||)
395
396 xor = (/=)
397
398 complement = not
399
400 shift x 0 = x
401 shift _ _ = False
402
403 rotate x _ = x
404
405 bit 0 = True
406 bit _ = False
407
408 testBit x 0 = x
409 testBit _ _ = False
410
411 bitSizeMaybe _ = Just 1
412
413 bitSize _ = 1
414
415 isSigned _ = False
416
417 popCount False = 0
418 popCount True = 1
419
420 instance FiniteBits Bool where
421 finiteBitSize _ = 1
422 countTrailingZeros x = if x then 0 else 1
423 countLeadingZeros x = if x then 0 else 1
424
425 instance Bits Int where
426 {-# INLINE shift #-}
427 {-# INLINE bit #-}
428 {-# INLINE testBit #-}
429
430 zeroBits = 0
431
432 bit = bitDefault
433
434 testBit = testBitDefault
435
436 (I# x#) .&. (I# y#) = I# (x# `andI#` y#)
437 (I# x#) .|. (I# y#) = I# (x# `orI#` y#)
438 (I# x#) `xor` (I# y#) = I# (x# `xorI#` y#)
439 complement (I# x#) = I# (notI# x#)
440 (I# x#) `shift` (I# i#)
441 | isTrue# (i# >=# 0#) = I# (x# `iShiftL#` i#)
442 | otherwise = I# (x# `iShiftRA#` negateInt# i#)
443 (I# x#) `shiftL` (I# i#) = I# (x# `iShiftL#` i#)
444 (I# x#) `unsafeShiftL` (I# i#) = I# (x# `uncheckedIShiftL#` i#)
445 (I# x#) `shiftR` (I# i#) = I# (x# `iShiftRA#` i#)
446 (I# x#) `unsafeShiftR` (I# i#) = I# (x# `uncheckedIShiftRA#` i#)
447
448 {-# INLINE rotate #-} -- See Note [Constant folding for rotate]
449 (I# x#) `rotate` (I# i#) =
450 I# ((x# `uncheckedIShiftL#` i'#) `orI#` (x# `uncheckedIShiftRL#` (wsib -# i'#)))
451 where
452 !i'# = i# `andI#` (wsib -# 1#)
453 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
454 bitSizeMaybe i = Just (finiteBitSize i)
455 bitSize i = finiteBitSize i
456
457 popCount (I# x#) = I# (word2Int# (popCnt# (int2Word# x#)))
458
459 isSigned _ = True
460
461 instance FiniteBits Int where
462 finiteBitSize _ = WORD_SIZE_IN_BITS
463 countLeadingZeros (I# x#) = I# (word2Int# (clz# (int2Word# x#)))
464 countTrailingZeros (I# x#) = I# (word2Int# (ctz# (int2Word# x#)))
465
466 instance Bits Word where
467 {-# INLINE shift #-}
468 {-# INLINE bit #-}
469 {-# INLINE testBit #-}
470
471 (W# x#) .&. (W# y#) = W# (x# `and#` y#)
472 (W# x#) .|. (W# y#) = W# (x# `or#` y#)
473 (W# x#) `xor` (W# y#) = W# (x# `xor#` y#)
474 complement (W# x#) = W# (x# `xor#` mb#)
475 where !(W# mb#) = maxBound
476 (W# x#) `shift` (I# i#)
477 | isTrue# (i# >=# 0#) = W# (x# `shiftL#` i#)
478 | otherwise = W# (x# `shiftRL#` negateInt# i#)
479 (W# x#) `shiftL` (I# i#) = W# (x# `shiftL#` i#)
480 (W# x#) `unsafeShiftL` (I# i#) = W# (x# `uncheckedShiftL#` i#)
481 (W# x#) `shiftR` (I# i#) = W# (x# `shiftRL#` i#)
482 (W# x#) `unsafeShiftR` (I# i#) = W# (x# `uncheckedShiftRL#` i#)
483 (W# x#) `rotate` (I# i#)
484 | isTrue# (i'# ==# 0#) = W# x#
485 | otherwise = W# ((x# `uncheckedShiftL#` i'#) `or#` (x# `uncheckedShiftRL#` (wsib -# i'#)))
486 where
487 !i'# = i# `andI#` (wsib -# 1#)
488 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
489 bitSizeMaybe i = Just (finiteBitSize i)
490 bitSize i = finiteBitSize i
491 isSigned _ = False
492 popCount (W# x#) = I# (word2Int# (popCnt# x#))
493 bit = bitDefault
494 testBit = testBitDefault
495
496 instance FiniteBits Word where
497 finiteBitSize _ = WORD_SIZE_IN_BITS
498 countLeadingZeros (W# x#) = I# (word2Int# (clz# x#))
499 countTrailingZeros (W# x#) = I# (word2Int# (ctz# x#))
500
501 instance Bits Integer where
502 (.&.) = andInteger
503 (.|.) = orInteger
504 xor = xorInteger
505 complement = complementInteger
506 shift x i@(I# i#) | i >= 0 = shiftLInteger x i#
507 | otherwise = shiftRInteger x (negateInt# i#)
508 shiftL x (I# i#) = shiftLInteger x i#
509 shiftR x (I# i#) = shiftRInteger x i#
510
511 testBit x (I# i) = testBitInteger x i
512
513 zeroBits = 0
514 bit = bitDefault
515 popCount = popCountDefault
516
517 rotate x i = shift x i -- since an Integer never wraps around
518
519 bitSizeMaybe _ = Nothing
520 bitSize _ = error "Data.Bits.bitSize(Integer)"
521 isSigned _ = True
522
523 {- Note [Constant folding for rotate]
524 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
525 The INLINE on the Int instance of rotate enables it to be constant
526 folded. For example:
527 sumU . mapU (`rotate` 3) . replicateU 10000000 $ (7 :: Int)
528 goes to:
529 Main.$wfold =
530 \ (ww_sO7 :: Int#) (ww1_sOb :: Int#) ->
531 case ww1_sOb of wild_XM {
532 __DEFAULT -> Main.$wfold (+# ww_sO7 56) (+# wild_XM 1);
533 10000000 -> ww_sO7
534 whereas before it was left as a call to $wrotate.
535
536 All other Bits instances seem to inline well enough on their
537 own to enable constant folding; for example 'shift':
538 sumU . mapU (`shift` 3) . replicateU 10000000 $ (7 :: Int)
539 goes to:
540 Main.$wfold =
541 \ (ww_sOb :: Int#) (ww1_sOf :: Int#) ->
542 case ww1_sOf of wild_XM {
543 __DEFAULT -> Main.$wfold (+# ww_sOb 56) (+# wild_XM 1);
544 10000000 -> ww_sOb
545 }
546 -}