Add Haddock `/Since: 4.5.[01].0/` comments to symbols
[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 /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 instance Bits Int where
307 {-# INLINE shift #-}
308 {-# INLINE bit #-}
309 {-# INLINE testBit #-}
310
311 bit = bitDefault
312
313 testBit = testBitDefault
314
315 (I# x#) .&. (I# y#) = I# (word2Int# (int2Word# x# `and#` int2Word# y#))
316
317 (I# x#) .|. (I# y#) = I# (word2Int# (int2Word# x# `or#` int2Word# y#))
318
319 (I# x#) `xor` (I# y#) = I# (word2Int# (int2Word# x# `xor#` int2Word# y#))
320
321 complement (I# x#) = I# (word2Int# (int2Word# x# `xor#` int2Word# (-1#)))
322
323 (I# x#) `shift` (I# i#)
324 | isTrue# (i# >=# 0#) = I# (x# `iShiftL#` i#)
325 | otherwise = I# (x# `iShiftRA#` negateInt# i#)
326 (I# x#) `shiftL` (I# i#) = I# (x# `iShiftL#` i#)
327 (I# x#) `unsafeShiftL` (I# i#) = I# (x# `uncheckedIShiftL#` i#)
328 (I# x#) `shiftR` (I# i#) = I# (x# `iShiftRA#` i#)
329 (I# x#) `unsafeShiftR` (I# i#) = I# (x# `uncheckedIShiftRA#` i#)
330
331 {-# INLINE rotate #-} -- See Note [Constant folding for rotate]
332 (I# x#) `rotate` (I# i#) =
333 I# (word2Int# ((x'# `uncheckedShiftL#` i'#) `or#`
334 (x'# `uncheckedShiftRL#` (wsib -# i'#))))
335 where
336 !x'# = int2Word# x#
337 !i'# = word2Int# (int2Word# i# `and#` int2Word# (wsib -# 1#))
338 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
339 bitSizeMaybe i = Just (finiteBitSize i)
340 bitSize i = finiteBitSize i
341
342 popCount (I# x#) = I# (word2Int# (popCnt# (int2Word# x#)))
343
344 isSigned _ = True
345
346 instance FiniteBits Int where
347 finiteBitSize _ = WORD_SIZE_IN_BITS
348
349 instance Bits Word where
350 {-# INLINE shift #-}
351 {-# INLINE bit #-}
352 {-# INLINE testBit #-}
353
354 (W# x#) .&. (W# y#) = W# (x# `and#` y#)
355 (W# x#) .|. (W# y#) = W# (x# `or#` y#)
356 (W# x#) `xor` (W# y#) = W# (x# `xor#` y#)
357 complement (W# x#) = W# (x# `xor#` mb#)
358 where !(W# mb#) = maxBound
359 (W# x#) `shift` (I# i#)
360 | isTrue# (i# >=# 0#) = W# (x# `shiftL#` i#)
361 | otherwise = W# (x# `shiftRL#` negateInt# i#)
362 (W# x#) `shiftL` (I# i#) = W# (x# `shiftL#` i#)
363 (W# x#) `unsafeShiftL` (I# i#) = W# (x# `uncheckedShiftL#` i#)
364 (W# x#) `shiftR` (I# i#) = W# (x# `shiftRL#` i#)
365 (W# x#) `unsafeShiftR` (I# i#) = W# (x# `uncheckedShiftRL#` i#)
366 (W# x#) `rotate` (I# i#)
367 | isTrue# (i'# ==# 0#) = W# x#
368 | otherwise = W# ((x# `uncheckedShiftL#` i'#) `or#` (x# `uncheckedShiftRL#` (wsib -# i'#)))
369 where
370 !i'# = word2Int# (int2Word# i# `and#` int2Word# (wsib -# 1#))
371 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
372 bitSizeMaybe i = Just (finiteBitSize i)
373 bitSize i = finiteBitSize i
374 isSigned _ = False
375 popCount (W# x#) = I# (word2Int# (popCnt# x#))
376 bit = bitDefault
377 testBit = testBitDefault
378
379 instance FiniteBits Word where
380 finiteBitSize _ = WORD_SIZE_IN_BITS
381
382 instance Bits Integer where
383 (.&.) = andInteger
384 (.|.) = orInteger
385 xor = xorInteger
386 complement = complementInteger
387 shift x i@(I# i#) | i >= 0 = shiftLInteger x i#
388 | otherwise = shiftRInteger x (negateInt# i#)
389 testBit x (I# i) = testBitInteger x i
390
391 bit = bitDefault
392 popCount = popCountDefault
393
394 rotate x i = shift x i -- since an Integer never wraps around
395
396 bitSizeMaybe _ = Nothing
397 bitSize _ = error "Data.Bits.bitSize(Integer)"
398 isSigned _ = True
399
400 {- Note [Constant folding for rotate]
401 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
402 The INLINE on the Int instance of rotate enables it to be constant
403 folded. For example:
404 sumU . mapU (`rotate` 3) . replicateU 10000000 $ (7 :: Int)
405 goes to:
406 Main.$wfold =
407 \ (ww_sO7 :: Int#) (ww1_sOb :: Int#) ->
408 case ww1_sOb of wild_XM {
409 __DEFAULT -> Main.$wfold (+# ww_sO7 56) (+# wild_XM 1);
410 10000000 -> ww_sO7
411 whereas before it was left as a call to $wrotate.
412
413 All other Bits instances seem to inline well enough on their
414 own to enable constant folding; for example 'shift':
415 sumU . mapU (`shift` 3) . replicateU 10000000 $ (7 :: Int)
416 goes to:
417 Main.$wfold =
418 \ (ww_sOb :: Int#) (ww1_sOf :: Int#) ->
419 case ww1_sOf of wild_XM {
420 __DEFAULT -> Main.$wfold (+# ww_sOb 56) (+# wild_XM 1);
421 10000000 -> ww_sOb
422 }
423 -}
424