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