76af67b6f6f4da0464d3385d0833f06d9bc8c35e
[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 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 {-# MINIMAL (.&.), (.|.), xor, complement,
243 (shift | (shiftL, shiftR)),
244 (rotate | (rotateL, rotateR)),
245 bitSize, bitSizeMaybe, isSigned, testBit, bit, popCount #-}
246
247 class Bits b => FiniteBits b where
248 finiteBitSize :: b -> Int
249
250 -- The defaults below are written with lambdas so that e.g.
251 -- bit = bitDefault
252 -- is fully applied, so inlining will happen
253
254 -- | Default implementation for 'bit'.
255 --
256 -- Note that: @bitDefault i = 1 `shiftL` i@
257 bitDefault :: (Bits a, Num a) => Int -> a
258 bitDefault = \i -> 1 `shiftL` i
259 {-# INLINE bitDefault #-}
260
261 -- | Default implementation for 'testBit'.
262 --
263 -- Note that: @testBitDefault x i = (x .&. bit i) /= 0@
264 testBitDefault :: (Bits a, Num a) => a -> Int -> Bool
265 testBitDefault = \x i -> (x .&. bit i) /= 0
266 {-# INLINE testBitDefault #-}
267
268 -- | Default implementation for 'popCount'.
269 --
270 -- This implementation is intentionally naive. Instances are expected to provide
271 -- an optimized implementation for their size.
272 popCountDefault :: (Bits a, Num a) => a -> Int
273 popCountDefault = go 0
274 where
275 go !c 0 = c
276 go c w = go (c+1) (w .&. (w - 1)) -- clear the least significant
277 {-# INLINABLE popCountDefault #-}
278
279 instance Bits Int where
280 {-# INLINE shift #-}
281 {-# INLINE bit #-}
282 {-# INLINE testBit #-}
283
284 bit = bitDefault
285
286 testBit = testBitDefault
287
288 (I# x#) .&. (I# y#) = I# (word2Int# (int2Word# x# `and#` int2Word# y#))
289
290 (I# x#) .|. (I# y#) = I# (word2Int# (int2Word# x# `or#` int2Word# y#))
291
292 (I# x#) `xor` (I# y#) = I# (word2Int# (int2Word# x# `xor#` int2Word# y#))
293
294 complement (I# x#) = I# (word2Int# (int2Word# x# `xor#` int2Word# (-1#)))
295
296 (I# x#) `shift` (I# i#)
297 | i# >=# 0# = I# (x# `iShiftL#` i#)
298 | otherwise = I# (x# `iShiftRA#` negateInt# i#)
299 (I# x#) `shiftL` (I# i#) = I# (x# `iShiftL#` i#)
300 (I# x#) `unsafeShiftL` (I# i#) = I# (x# `uncheckedIShiftL#` i#)
301 (I# x#) `shiftR` (I# i#) = I# (x# `iShiftRA#` i#)
302 (I# x#) `unsafeShiftR` (I# i#) = I# (x# `uncheckedIShiftRA#` i#)
303
304 {-# INLINE rotate #-} -- See Note [Constant folding for rotate]
305 (I# x#) `rotate` (I# i#) =
306 I# (word2Int# ((x'# `uncheckedShiftL#` i'#) `or#`
307 (x'# `uncheckedShiftRL#` (wsib -# i'#))))
308 where
309 !x'# = int2Word# x#
310 !i'# = word2Int# (int2Word# i# `and#` int2Word# (wsib -# 1#))
311 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
312 bitSizeMaybe i = Just (finiteBitSize i)
313 bitSize i = finiteBitSize i
314
315 popCount (I# x#) = I# (word2Int# (popCnt# (int2Word# x#)))
316
317 isSigned _ = True
318
319 instance FiniteBits Int where
320 finiteBitSize _ = WORD_SIZE_IN_BITS
321
322 instance Bits Word where
323 {-# INLINE shift #-}
324 {-# INLINE bit #-}
325 {-# INLINE testBit #-}
326
327 (W# x#) .&. (W# y#) = W# (x# `and#` y#)
328 (W# x#) .|. (W# y#) = W# (x# `or#` y#)
329 (W# x#) `xor` (W# y#) = W# (x# `xor#` y#)
330 complement (W# x#) = W# (x# `xor#` mb#)
331 where !(W# mb#) = maxBound
332 (W# x#) `shift` (I# i#)
333 | i# >=# 0# = W# (x# `shiftL#` i#)
334 | otherwise = W# (x# `shiftRL#` negateInt# i#)
335 (W# x#) `shiftL` (I# i#) = W# (x# `shiftL#` i#)
336 (W# x#) `unsafeShiftL` (I# i#) = W# (x# `uncheckedShiftL#` i#)
337 (W# x#) `shiftR` (I# i#) = W# (x# `shiftRL#` i#)
338 (W# x#) `unsafeShiftR` (I# i#) = W# (x# `uncheckedShiftRL#` i#)
339 (W# x#) `rotate` (I# i#)
340 | i'# ==# 0# = W# x#
341 | otherwise = W# ((x# `uncheckedShiftL#` i'#) `or#` (x# `uncheckedShiftRL#` (wsib -# i'#)))
342 where
343 !i'# = word2Int# (int2Word# i# `and#` int2Word# (wsib -# 1#))
344 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
345 bitSizeMaybe i = Just (finiteBitSize i)
346 bitSize i = finiteBitSize i
347 isSigned _ = False
348 popCount (W# x#) = I# (word2Int# (popCnt# x#))
349 bit = bitDefault
350 testBit = testBitDefault
351
352 instance FiniteBits Word where
353 finiteBitSize _ = WORD_SIZE_IN_BITS
354
355 instance Bits Integer where
356 (.&.) = andInteger
357 (.|.) = orInteger
358 xor = xorInteger
359 complement = complementInteger
360 shift x i@(I# i#) | i >= 0 = shiftLInteger x i#
361 | otherwise = shiftRInteger x (negateInt# i#)
362 testBit x (I# i) = testBitInteger x i
363
364 bit = bitDefault
365 popCount = popCountDefault
366
367 rotate x i = shift x i -- since an Integer never wraps around
368
369 bitSizeMaybe _ = Nothing
370 bitSize _ = error "Data.Bits.bitSize(Integer)"
371 isSigned _ = True
372
373 {- Note [Constant folding for rotate]
374 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
375 The INLINE on the Int instance of rotate enables it to be constant
376 folded. For example:
377 sumU . mapU (`rotate` 3) . replicateU 10000000 $ (7 :: Int)
378 goes to:
379 Main.$wfold =
380 \ (ww_sO7 :: Int#) (ww1_sOb :: Int#) ->
381 case ww1_sOb of wild_XM {
382 __DEFAULT -> Main.$wfold (+# ww_sO7 56) (+# wild_XM 1);
383 10000000 -> ww_sO7
384 whereas before it was left as a call to $wrotate.
385
386 All other Bits instances seem to inline well enough on their
387 own to enable constant folding; for example 'shift':
388 sumU . mapU (`shift` 3) . replicateU 10000000 $ (7 :: Int)
389 goes to:
390 Main.$wfold =
391 \ (ww_sOb :: Int#) (ww1_sOf :: Int#) ->
392 case ww1_sOf of wild_XM {
393 __DEFAULT -> Main.$wfold (+# ww_sOb 56) (+# wild_XM 1);
394 10000000 -> ww_sOb
395 }
396 -}
397