Bits.hs 17.5 KB
Newer Older
1
{-# LANGUAGE Trustworthy #-}
2 3
{-# LANGUAGE CPP, NoImplicitPrelude, BangPatterns, MagicHash #-}

4
-----------------------------------------------------------------------------
5
-- |
6 7
-- Module      :  Data.Bits
-- Copyright   :  (c) The University of Glasgow 2001
8
-- License     :  BSD-style (see the file libraries/base/LICENSE)
Jan Stolarek's avatar
Jan Stolarek committed
9
--
10 11
-- Maintainer  :  libraries@haskell.org
-- Stability   :  experimental
12
-- Portability :  portable
13
--
Ross Paterson's avatar
Ross Paterson committed
14 15 16 17 18
-- This module defines bitwise operations for signed and unsigned
-- integers.  Instances of the class 'Bits' for the 'Int' and
-- 'Integer' types are available from this module, and instances for
-- explicitly sized integral types are available from the
-- "Data.Int" and "Data.Word" modules.
19 20 21
--
-----------------------------------------------------------------------------

Jan Stolarek's avatar
Jan Stolarek committed
22
module Data.Bits (
23
  Bits(
24 25 26 27
    (.&.), (.|.), xor,
    complement,
    shift,
    rotate,
28
    zeroBits,
29 30 31 32 33
    bit,
    setBit,
    clearBit,
    complementBit,
    testBit,
34
    bitSizeMaybe,
35 36 37 38 39 40
    bitSize,
    isSigned,
    shiftL, shiftR,
    unsafeShiftL, unsafeShiftR,
    rotateL, rotateR,
    popCount
41
  ),
42 43 44 45 46
  FiniteBits(
    finiteBitSize,
    countLeadingZeros,
    countTrailingZeros
  ),
47

48 49 50
  bitDefault,
  testBitDefault,
  popCountDefault
51 52 53 54 55 56 57
 ) where

-- Defines the @Bits@ class containing bit-based operations.
-- See library document for details on the semantics of the
-- individual operations.

#include "MachDeps.h"
ross's avatar
ross committed
58

59
import Data.Maybe
60
import GHC.Enum
61 62 63
import GHC.Num
import GHC.Base

64
infixl 8 `shift`, `rotate`, `shiftL`, `shiftR`, `rotateL`, `rotateR`
65 66 67 68
infixl 7 .&.
infixl 6 `xor`
infixl 5 .|.

69
{-# DEPRECATED bitSize "Use 'bitSizeMaybe' or 'finiteBitSize' instead" #-} -- deprecated in 7.8
ian@well-typed.com's avatar
ian@well-typed.com committed
70

Jan Stolarek's avatar
Jan Stolarek committed
71
{-|
72 73 74 75
The 'Bits' class defines bitwise operations over integral types.

* Bits are numbered from 0 with bit 0 being the least
  significant bit.
76 77 78

Minimal complete definition: '.&.', '.|.', 'xor', 'complement',
('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 85 86 87 88 89 90 91 92 93
    -- | Bitwise \"and\"
    (.&.) :: a -> a -> a

    -- | Bitwise \"or\"
    (.|.) :: a -> a -> a

    -- | Bitwise \"xor\"
    xor :: a -> a -> a

    {-| 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,
Don Stewart's avatar
Don Stewart committed
97 98 99 100 101 102 103 104
        or right by @-i@ bits otherwise.
        Right shifts perform sign extension on signed number types;
        i.e. they fill the top bits with 1 if the @x@ is negative
        and with 0 otherwise.

        An instance can define either this unified 'shift' or 'shiftL' and
        'shiftR', depending on which is more convenient for the type in
        question. -}
105
    shift             :: a -> Int -> a
106

Ian Lynagh's avatar
Ian Lynagh committed
107 108 109
    x `shift`   i | i<0       = x `shiftR` (-i)
                  | i>0       = x `shiftL` i
                  | otherwise = x
110

111
    {-| @'rotate' x i@ rotates @x@ left by @i@ bits if @i@ is positive,
Don Stewart's avatar
Don Stewart committed
112
        or right by @-i@ bits otherwise.
113

ross's avatar
ross committed
114
        For unbounded types like 'Integer', 'rotate' is equivalent to 'shift'.
115

Don Stewart's avatar
Don Stewart committed
116 117 118
        An instance can define either this unified 'rotate' or 'rotateL' and
        'rotateR', depending on which is more convenient for the type in
        question. -}
119
    rotate            :: a -> Int -> a
120

Ian Lynagh's avatar
Ian Lynagh committed
121 122 123
    x `rotate`  i | i<0       = x `rotateR` (-i)
                  | i>0       = x `rotateL` i
                  | otherwise = x
124

125 126 127 128 129 130 131 132 133 134 135 136 137 138
    {-
    -- Rotation can be implemented in terms of two shifts, but care is
    -- needed for negative values.  This suggested implementation assumes
    -- 2's-complement arithmetic.  It is commented out because it would
    -- require an extra context (Ord a) on the signature of 'rotate'.
    x `rotate`  i | i<0 && isSigned x && x<0
                         = let left = i+bitSize x in
                           ((x `shift` i) .&. complement ((-1) `shift` left))
                           .|. (x `shift` left)
                  | i<0  = (x `shift` i) .|. (x `shift` (i+bitSize x))
                  | i==0 = x
                  | i>0  = (x `shift` i) .|. (x `shift` (i-bitSize x))
    -}

139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158
    -- | 'zeroBits' is the value with all bits unset.
    --
    -- The following laws ought to hold (for all valid bit indices @/n/@):
    --
    --   * @'clearBit' 'zeroBits' /n/ == 'zeroBits'@
    --   * @'setBit'   'zeroBits' /n/ == 'bit' /n/@
    --   * @'testBit'  'zeroBits' /n/ == False@
    --   * @'popCount' 'zeroBits'   == 0@
    --
    -- This method uses @'clearBit' ('bit' 0) 0@ as its default
    -- implementation (which ought to be equivalent to 'zeroBits' for
    -- types which possess a 0th bit).
    --
    -- /Since: 4.7.0.0/
    zeroBits :: a
    zeroBits = clearBit (bit 0) 0

    -- | @bit /i/@ is a value with the @/i/@th bit set and all other bits clear.
    --
    -- 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 174 175
    {-| Return the number of bits in the type of the argument.  The actual
        value of the argument is ignored.  Returns Nothing
        for types that do not have a fixed bitsize, like 'Integer'.
176 177

        /Since: 4.7.0.0/
178 179 180
        -}
    bitSizeMaybe      :: a -> Maybe Int

181
    {-| Return the number of bits in the type of the argument.  The actual
Don Stewart's avatar
Don Stewart committed
182 183 184
        value of the argument is ignored.  The function 'bitSize' is
        undefined for types that do not have a fixed bitsize, like 'Integer'.
        -}
185
    bitSize           :: a -> Int
186 187 188

    {-| Return 'True' if the argument is a signed type.  The actual
        value of the argument is ignored -}
189 190
    isSigned          :: a -> Bool

191 192 193
    {-# INLINE setBit #-}
    {-# INLINE clearBit #-}
    {-# INLINE complementBit #-}
194 195 196 197
    x `setBit` i        = x .|. bit i
    x `clearBit` i      = x .&. complement (bit i)
    x `complementBit` i = x `xor` bit i

198
    {-| Shift the argument left by the specified number of bits
Don Stewart's avatar
Don Stewart committed
199
        (which must be non-negative).
200

Don Stewart's avatar
Don Stewart committed
201 202 203
        An instance can define either this and 'shiftR' or the unified
        'shift', depending on which is more convenient for the type in
        question. -}
204
    shiftL            :: a -> Int -> a
205
    {-# INLINE shiftL #-}
206
    x `shiftL`  i = x `shift`  i
207

tibbe's avatar
tibbe committed
208 209 210 211
    {-| Shift the argument left by the specified number of bits.  The
        result is undefined for negative shift amounts and shift amounts
        greater or equal to the 'bitSize'.

212 213 214
        Defaults to 'shiftL' unless defined explicitly by an instance.

        /Since: 4.5.0.0/ -}
tibbe's avatar
tibbe committed
215 216 217 218 219 220 221 222
    unsafeShiftL            :: a -> Int -> a
    {-# INLINE unsafeShiftL #-}
    x `unsafeShiftL` i = x `shiftL` i

    {-| Shift the first argument right by the specified number of bits. The
        result is undefined for negative shift amounts and shift amounts
        greater or equal to the 'bitSize'.

Don Stewart's avatar
Don Stewart committed
223 224 225 226 227 228 229
        Right shifts perform sign extension on signed number types;
        i.e. they fill the top bits with 1 if the @x@ is negative
        and with 0 otherwise.

        An instance can define either this and 'shiftL' or the unified
        'shift', depending on which is more convenient for the type in
        question. -}
230
    shiftR            :: a -> Int -> a
231
    {-# INLINE shiftR #-}
232
    x `shiftR`  i = x `shift`  (-i)
233

tibbe's avatar
tibbe committed
234 235 236 237 238 239 240
    {-| Shift the first argument right by the specified number of bits, which
        must be non-negative an smaller than the number of bits in the type.

        Right shifts perform sign extension on signed number types;
        i.e. they fill the top bits with 1 if the @x@ is negative
        and with 0 otherwise.

241 242 243
        Defaults to 'shiftR' unless defined explicitly by an instance.

        /Since: 4.5.0.0/ -}
tibbe's avatar
tibbe committed
244 245 246 247
    unsafeShiftR            :: a -> Int -> a
    {-# INLINE unsafeShiftR #-}
    x `unsafeShiftR` i = x `shiftR` i

248
    {-| Rotate the argument left by the specified number of bits
Don Stewart's avatar
Don Stewart committed
249
        (which must be non-negative).
250

Don Stewart's avatar
Don Stewart committed
251 252 253
        An instance can define either this and 'rotateR' or the unified
        'rotate', depending on which is more convenient for the type in
        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
Don Stewart's avatar
Don Stewart committed
259
        (which must be non-negative).
260

Don Stewart's avatar
Don Stewart committed
261 262 263
        An instance can define either this and 'rotateL' or the unified
        'rotate', depending on which is more convenient for the type in
        question. -}
264
    rotateR           :: a -> Int -> a
265
    {-# INLINE rotateR #-}
266
    x `rotateR` i = x `rotate` (-i)
267

tibbe's avatar
tibbe committed
268
    {-| Return the number of set bits in the argument.  This number is
269 270 271
        known as the population count or the Hamming weight.

        /Since: 4.5.0.0/ -}
tibbe's avatar
tibbe committed
272
    popCount          :: a -> Int
273

274 275 276 277 278
    {-# MINIMAL (.&.), (.|.), xor, complement,
                (shift | (shiftL, shiftR)),
                (rotate | (rotateL, rotateR)),
                bitSize, bitSizeMaybe, isSigned, testBit, bit, popCount #-}

279 280 281
-- |The 'FiniteBits' class denotes types with a finite, fixed number of bits.
--
-- /Since: 4.7.0.0/
282
class Bits b => FiniteBits b where
283 284 285 286 287 288 289 290 291 292
    -- | Return the number of bits in the type of the argument.
    -- The actual value of the argument is ignored. Moreover, 'finiteBitSize'
    -- is total, in contrast to the deprecated 'bitSize' function it replaces.
    --
    -- @
    -- 'finiteBitSize' = 'bitSize'
    -- 'bitSizeMaybe' = 'Just' . 'finiteBitSize'
    -- @
    --
    -- /Since: 4.7.0.0/
293 294
    finiteBitSize :: b -> Int

295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353
    -- | Count number of zero bits preceding the most significant set bit.
    --
    -- @
    -- 'countLeadingZeros' ('zeroBits' :: a) = finiteBitSize ('zeroBits' :: a)
    -- 'countLeadingZeros' . 'negate' = 'const' 0
    -- @
    --
    -- 'countLeadingZeros' can be used to compute log base 2 via
    --
    -- @
    -- logBase2 x = 'finiteBitSize' x - 1 - 'countLeadingZeros' x
    -- @
    --
    -- Note: The default implementation for this method is intentionally
    -- naive. However, the instances provided for the primitive
    -- integral types are implemented using CPU specific machine
    -- instructions.
    --
    -- /Since: 4.8.0.0/
    countLeadingZeros :: b -> Int
    countLeadingZeros x = (w-1) - go (w-1)
      where
        go i | i < 0       = i -- no bit set
             | testBit x i = i
             | otherwise   = go (i-1)

        w = finiteBitSize x

    -- | Count number of zero bits following the least significant set bit.
    --
    -- @
    -- 'countTrailingZeros' ('zeroBits' :: a) = finiteBitSize ('zeroBits' :: a)
    -- 'countTrailingZeros' . 'negate' = 'countTrailingZeros'
    -- @
    --
    -- The related
    -- <http://en.wikipedia.org/wiki/Find_first_set find-first-set operation>
    -- can be expressed in terms of 'countTrailingZeros' as follows
    --
    -- @
    -- findFirstSet x = 1 + 'countTrailingZeros' x
    -- @
    --
    -- Note: The default implementation for this method is intentionally
    -- naive. However, the instances provided for the primitive
    -- integral types are implemented using CPU specific machine
    -- instructions.
    --
    -- /Since: 4.8.0.0/
    countTrailingZeros :: b -> Int
    countTrailingZeros x = go 0
      where
        go i | i >= w      = i
             | testBit x i = i
             | otherwise   = go (i+1)

        w = finiteBitSize x


354 355 356 357
-- The defaults below are written with lambdas so that e.g.
--     bit = bitDefault
-- is fully applied, so inlining will happen

358 359 360
-- | Default implementation for 'bit'.
--
-- 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 366 367 368 369
{-# INLINE bitDefault #-}

-- | Default implementation for 'testBit'.
--
-- 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 375 376 377 378 379
{-# INLINE testBitDefault #-}

-- | Default implementation for 'popCount'.
--
-- This implementation is intentionally naive. Instances are expected to provide
-- an optimized implementation for their size.
380 381
--
-- /Since: 4.6.0.0/
382 383 384 385
popCountDefault :: (Bits a, Num a) => a -> Int
popCountDefault = go 0
 where
   go !c 0 = c
386 387
   go c w = go (c+1) (w .&. (w - 1)) -- clear the least significant
{-# INLINABLE popCountDefault #-}
tibbe's avatar
tibbe committed
388

389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421

-- Interpret 'Bool' as 1-bit bit-field; /Since: 4.7.0.0/
instance Bits Bool where
    (.&.) = (&&)

    (.|.) = (||)

    xor = (/=)

    complement = not

    shift x 0 = x
    shift _ _ = False

    rotate x _ = x

    bit 0 = True
    bit _ = False

    testBit x 0 = x
    testBit _ _ = False

    bitSizeMaybe _ = Just 1

    bitSize _ = 1

    isSigned _ = False

    popCount False = 0
    popCount True  = 1

instance FiniteBits Bool where
    finiteBitSize _ = 1
422 423
    countTrailingZeros x = if x then 0 else 1
    countLeadingZeros  x = if x then 0 else 1
424

425
instance Bits Int where
426
    {-# INLINE shift #-}
427 428
    {-# INLINE bit #-}
    {-# INLINE testBit #-}
429

430 431
    zeroBits = 0

432 433 434 435
    bit     = bitDefault

    testBit = testBitDefault

436 437 438 439
    (I# x#) .&.   (I# y#)          = I# (x# `andI#` y#)
    (I# x#) .|.   (I# y#)          = I# (x# `orI#`  y#)
    (I# x#) `xor` (I# y#)          = I# (x# `xorI#` y#)
    complement (I# x#)             = I# (notI# x#)
440
    (I# x#) `shift` (I# i#)
441 442 443
        | isTrue# (i# >=# 0#)      = I# (x# `iShiftL#` i#)
        | otherwise                = I# (x# `iShiftRA#` negateInt# i#)
    (I# x#) `shiftL` (I# i#)       = I# (x# `iShiftL#` i#)
tibbe's avatar
tibbe committed
444
    (I# x#) `unsafeShiftL` (I# i#) = I# (x# `uncheckedIShiftL#` i#)
445
    (I# x#) `shiftR` (I# i#)       = I# (x# `iShiftRA#` i#)
tibbe's avatar
tibbe committed
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 455
    bitSizeMaybe i         = Just (finiteBitSize i)
    bitSize i              = finiteBitSize i
Simon Marlow's avatar
Simon Marlow committed
456

tibbe's avatar
tibbe committed
457 458
    popCount (I# x#) = I# (word2Int# (popCnt# (int2Word# x#)))

ross's avatar
ross committed
459 460
    isSigned _             = True

461 462
instance FiniteBits Int where
    finiteBitSize _ = WORD_SIZE_IN_BITS
463 464
    countLeadingZeros  (I# x#) = I# (word2Int# (clz# (int2Word# x#)))
    countTrailingZeros (I# x#) = I# (word2Int# (ctz# (int2Word# x#)))
465

466 467 468 469 470 471 472 473 474 475 476
instance Bits Word where
    {-# INLINE shift #-}
    {-# INLINE bit #-}
    {-# INLINE testBit #-}

    (W# x#) .&.   (W# y#)    = W# (x# `and#` y#)
    (W# x#) .|.   (W# y#)    = W# (x# `or#`  y#)
    (W# x#) `xor` (W# y#)    = W# (x# `xor#` y#)
    complement (W# x#)       = W# (x# `xor#` mb#)
        where !(W# mb#) = maxBound
    (W# x#) `shift` (I# i#)
477 478 479
        | isTrue# (i# >=# 0#)      = W# (x# `shiftL#` i#)
        | otherwise                = W# (x# `shiftRL#` negateInt# i#)
    (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 483
    (W# x#) `unsafeShiftR` (I# i#) = W# (x# `uncheckedShiftRL#` i#)
    (W# x#) `rotate` (I# i#)
484
        | isTrue# (i'# ==# 0#) = W# x#
485 486
        | otherwise  = W# ((x# `uncheckedShiftL#` i'#) `or#` (x# `uncheckedShiftRL#` (wsib -# i'#)))
        where
487
        !i'# = i# `andI#` (wsib -# 1#)
488
        !wsib = WORD_SIZE_IN_BITS#  {- work around preprocessor problem (??) -}
489 490
    bitSizeMaybe i           = Just (finiteBitSize i)
    bitSize i                = finiteBitSize i
491 492 493 494
    isSigned _               = False
    popCount (W# x#)         = I# (word2Int# (popCnt# x#))
    bit                      = bitDefault
    testBit                  = testBitDefault
495 496 497

instance FiniteBits Word where
    finiteBitSize _ = WORD_SIZE_IN_BITS
498 499
    countLeadingZeros  (W# x#) = I# (word2Int# (clz# x#))
    countTrailingZeros (W# x#) = I# (word2Int# (ctz# x#))
500

501
instance Bits Integer where
502 503 504 505
   (.&.) = andInteger
   (.|.) = orInteger
   xor = xorInteger
   complement = complementInteger
506 507
   shift x i@(I# i#) | i >= 0    = shiftLInteger x i#
                     | otherwise = shiftRInteger x (negateInt# i#)
508 509 510
   shiftL x (I# i#) = shiftLInteger x i#
   shiftR x (I# i#) = shiftRInteger x i#

511
   testBit x (I# i) = testBitInteger x i
512

513
   zeroBits   = 0
514 515 516
   bit        = bitDefault
   popCount   = popCountDefault

517 518
   rotate x i = shift x i   -- since an Integer never wraps around

519
   bitSizeMaybe _ = Nothing
ross's avatar
ross committed
520
   bitSize _  = error "Data.Bits.bitSize(Integer)"
521
   isSigned _ = True
522

523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545
{- 	Note [Constant folding for rotate]
	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The INLINE on the Int instance of rotate enables it to be constant
folded.  For example:
     sumU . mapU (`rotate` 3) . replicateU 10000000 $ (7 :: Int)
goes to:
   Main.$wfold =
     \ (ww_sO7 :: Int#) (ww1_sOb :: Int#) ->
       case ww1_sOb of wild_XM {
         __DEFAULT -> Main.$wfold (+# ww_sO7 56) (+# wild_XM 1);
         10000000 -> ww_sO7
whereas before it was left as a call to $wrotate.

All other Bits instances seem to inline well enough on their
own to enable constant folding; for example 'shift':
     sumU . mapU (`shift` 3) . replicateU 10000000 $ (7 :: Int)
 goes to:
     Main.$wfold =
       \ (ww_sOb :: Int#) (ww1_sOf :: Int#) ->
         case ww1_sOf of wild_XM {
           __DEFAULT -> Main.$wfold (+# ww_sOb 56) (+# wild_XM 1);
           10000000 -> ww_sOb
         }
Jan Stolarek's avatar
Jan Stolarek committed
546
-}
547