Data/Bits.hs

   1 {-# OPTIONS -fno-implicit-prelude #-}
   2 -----------------------------------------------------------------------------
   3 -- |
   4 -- Module      :  Data.Bits
   5 -- Copyright   :  (c) The University of Glasgow 2001
   6 -- License     :  BSD-style (see the file libraries/base/LICENSE)
   7 --
   8 -- Maintainer  :  libraries@haskell.org
   9 -- Stability   :  experimental
  10 -- Portability :  portable
  11 --
  12 --  This module defines bitwise operations for signed and unsigned
  13 --  integers.  Instances of the class 'Bits' for the 'Int' and
  14 --  'Integer' types are available from this module, and instances for
  15 --  explicitly sized integral types are available from the
  16 --  "Int" and "Word" modules.
  17 --
  18 -----------------------------------------------------------------------------
  19
  20 module Data.Bits (
  21   Bits(
  22     (.&.), (.|.), xor, -- :: a -> a -> a
  23     complement,        -- :: a -> a
  24     shift,             -- :: a -> Int -> a
  25     rotate,            -- :: a -> Int -> a
  26     bit,               -- :: Int -> a
  27     setBit,            -- :: a -> Int -> a
  28     clearBit,          -- :: a -> Int -> a
  29     complementBit,     -- :: a -> Int -> a
  30     testBit,           -- :: a -> Int -> Bool
  31     bitSize,           -- :: a -> Int
  32     isSigned,          -- :: a -> Bool
  33     shiftL, shiftR,    -- :: a -> Int -> a
  34     rotateL, rotateR   -- :: a -> Int -> a
  35   )
  36
  37   -- instance Bits Int
  38   -- instance Bits Integer
  39  ) where
  40
  41 -- Defines the @Bits@ class containing bit-based operations.
  42 -- See library document for details on the semantics of the
  43 -- individual operations.
  44
  45 #ifdef __GLASGOW_HASKELL__
  46 #include "MachDeps.h"
  47 import GHC.Num
  48 import GHC.Real
  49 import GHC.Base
  50 #endif
  51
  52 infixl 8 `shift`, `rotate`, `shiftL`, `shiftR`, `rotateL`, `rotateR`
  53 infixl 7 .&.
  54 infixl 6 `xor`
  55 infixl 5 .|.
  56
  57 {-|
  58 The 'Bits' class defines bitwise operations over integral types.
  59
  60 * Bits are numbered from 0 with bit 0 being the least
  61   significant bit.
  62 -}
  63 class Num a => Bits a where
  64     -- | Bitwise \"and\"
  65     (.&.) :: a -> a -> a
  66
  67     -- | Bitwise \"or\"
  68     (.|.) :: a -> a -> a
  69
  70     -- | Bitwise \"xor\"
  71     xor :: a -> a -> a
  72
  73     {-| Reverse all the bits in the argument -}
  74     complement        :: a -> a
  75
  76     {-| Shift the argument left by the specified number of bits.
  77         Right shifts (signed) are specified by giving a negative value.
  78
  79         An instance can define either this unified 'shift' or 'shiftL' and
  80         'shiftR', depending on which is more convenient for the type in
  81         question. -}
  82     shift             :: a -> Int -> a
  83
  84     x `shift`   i | i<0  = x `shiftR` (-i)
  85                   | i==0 = x
  86                   | i>0  = x `shiftL` i
  87
  88     {-| Rotate the argument left by the specified number of bits.
  89         Right rotates are specified by giving a negative value.
  90
  91         'rotate' is well defined only if 'bitSize' is also well defined
  92         ('bitSize' is undefined for 'Integer', for example).
  93
  94         An instance can define either this unified 'rotate' or 'rotateL' and
  95         'rotateR', depending on which is more convenient for the type in
  96         question. -}
  97     rotate            :: a -> Int -> a
  98
  99     x `rotate`  i | i<0  = x `rotateR` (-i)
 100                   | i==0 = x
 101                   | i>0  = x `rotateL` i
 102
 103     {-
 104     -- Rotation can be implemented in terms of two shifts, but care is
 105     -- needed for negative values.  This suggested implementation assumes
 106     -- 2's-complement arithmetic.  It is commented out because it would
 107     -- require an extra context (Ord a) on the signature of 'rotate'.
 108     x `rotate`  i | i<0 && isSigned x && x<0
 109                          = let left = i+bitSize x in
 110                            ((x `shift` i) .&. complement ((-1) `shift` left))
 111                            .|. (x `shift` left)
 112                   | i<0  = (x `shift` i) .|. (x `shift` (i+bitSize x))
 113                   | i==0 = x
 114                   | i>0  = (x `shift` i) .|. (x `shift` (i-bitSize x))
 115     -}
 116
 117     -- | @bit i@ is a value with the @i@th bit set
 118     bit               :: Int -> a
 119
 120     -- | @x \`setBit\` i@ is the same as @x .|. bit i@
 121     setBit            :: a -> Int -> a
 122
 123     -- | @x \`clearBit\` i@ is the same as @x .&. complement (bit i)@
 124     clearBit          :: a -> Int -> a
 125
 126     -- | @x \`complementBit\` i@ is the same as @x \`xor\` bit i@
 127     complementBit     :: a -> Int -> a
 128
 129     -- | Return 'True' if the @n@th bit of the argument is 1
 130     testBit           :: a -> Int -> Bool
 131
 132     {-| Return the number of bits in the type of the argument.  The actual
 133         value of the argument is ignored -}
 134     bitSize           :: a -> Int
 135
 136     {-| Return 'True' if the argument is a signed type.  The actual
 137         value of the argument is ignored -}
 138     isSigned          :: a -> Bool
 139
 140     bit i               = 1 `shiftL` i
 141     x `setBit` i        = x .|. bit i
 142     x `clearBit` i      = x .&. complement (bit i)
 143     x `complementBit` i = x `xor` bit i
 144     x `testBit` i       = (x .&. bit i) /= 0
 145
 146     {-| Shift the argument left by the specified number of bits
 147         (which must be non-negative).
 148
 149         An instance can define either this and 'shiftR' or the unified
 150         'shift', depending on which is more convenient for the type in
 151         question. -}
 152     shiftL            :: a -> Int -> a
 153     x `shiftL`  i = x `shift`  i
 154
 155     {-| Shift the argument right (signed) by the specified number of bits
 156         (which must be non-negative).
 157
 158         An instance can define either this and 'shiftL' or the unified
 159         'shift', depending on which is more convenient for the type in
 160         question. -}
 161     shiftR            :: a -> Int -> a
 162     x `shiftR`  i = x `shift`  (-i)
 163
 164     {-| Rotate the argument left by the specified number of bits
 165         (which must be non-negative).
 166
 167         An instance can define either this and 'rotateR' or the unified
 168         'rotate', depending on which is more convenient for the type in
 169         question. -}
 170     rotateL           :: a -> Int -> a
 171     x `rotateL` i = x `rotate` i
 172
 173     {-| Rotate the argument right by the specified number of bits
 174         (which must be non-negative).
 175
 176         An instance can define either this and 'rotateL' or the unified
 177         'rotate', depending on which is more convenient for the type in
 178         question. -}
 179     rotateR           :: a -> Int -> a
 180     x `rotateR` i = x `rotate` (-i)
 181
 182 #ifdef __GLASGOW_HASKELL__
 183 instance Bits Int where
 184     (I# x#) .&.   (I# y#)  = I# (word2Int# (int2Word# x# `and#` int2Word# y#))
 185     (I# x#) .|.   (I# y#)  = I# (word2Int# (int2Word# x# `or#`  int2Word# y#))
 186     (I# x#) `xor` (I# y#)  = I# (word2Int# (int2Word# x# `xor#` int2Word# y#))
 187     complement (I# x#)     = I# (word2Int# (int2Word# x# `xor#` int2Word# (-1#)))
 188     (I# x#) `shift` (I# i#)
 189         | i# >=# 0#            = I# (x# `iShiftL#` i#)
 190         | otherwise            = I# (x# `iShiftRA#` negateInt# i#)
 191     (I# x#) `rotate` (I# i#) =
 192         I# (word2Int# ((x'# `shiftL#` i'#) `or#`
 193                        (x'# `shiftRL#` (wsib -# i'#))))
 194         where
 195         x'# = int2Word# x#
 196         i'# = word2Int# (int2Word# i# `and#` int2Word# (wsib -# 1#))
 197         wsib = WORD_SIZE_IN_BITS#   {- work around preprocessor problem (??) -}
 198     bitSize  _                 = WORD_SIZE_IN_BITS
 199     isSigned _                 = True
 200
 201 instance Bits Integer where
 202    (S# x) .&. (S# y) = S# (word2Int# (int2Word# x `and#` int2Word# y))
 203    x@(S# _) .&. y = toBig x .&. y
 204    x .&. y@(S# _) = x .&. toBig y
 205    (J# s1 d1) .&. (J# s2 d2) =
 206         case andInteger# s1 d1 s2 d2 of
 207           (# s, d #) -> J# s d
 208
 209    (S# x) .|. (S# y) = S# (word2Int# (int2Word# x `or#` int2Word# y))
 210    x@(S# _) .|. y = toBig x .|. y
 211    x .|. y@(S# _) = x .|. toBig y
 212    (J# s1 d1) .|. (J# s2 d2) =
 213         case orInteger# s1 d1 s2 d2 of
 214           (# s, d #) -> J# s d
 215
 216    (S# x) `xor` (S# y) = S# (word2Int# (int2Word# x `xor#` int2Word# y))
 217    x@(S# _) `xor` y = toBig x `xor` y
 218    x `xor` y@(S# _) = x `xor` toBig y
 219    (J# s1 d1) `xor` (J# s2 d2) =
 220         case xorInteger# s1 d1 s2 d2 of
 221           (# s, d #) -> J# s d
 222
 223    complement (S# x) = S# (word2Int# (int2Word# x `xor#` int2Word# (0# -# 1#)))
 224    complement (J# s d) = case complementInteger# s d of (# s, d #) -> J# s d
 225
 226    shift x i | i >= 0    = x * 2^i
 227              | otherwise = x `div` 2^(-i)
 228
 229    rotate x i = shift x i   -- since an Integer never wraps around
 230
 231    bitSize _  = error "Bits.bitSize(Integer)"
 232    isSigned _ = True
 233 #endif
 234
 235 #ifdef __NHC__
 236 instance Bits Int where
 237     (.&.)             = nhc_primIntAnd
 238     (.|.)             = nhc_primIntOr
 239     xor               = nhc_primIntXor
 240     complement        = nhc_primIntCompl
 241     shiftL            = nhc_primIntLsh
 242     shiftR            = nhc_primIntRsh
 243     bitSize _         = 32
 244     isSigned _        = True
 245
 246 foreign import ccall nhc_primIntAnd :: Int -> Int -> Int
 247 foreign import ccall nhc_primIntOr  :: Int -> Int -> Int
 248 foreign import ccall nhc_primIntXor :: Int -> Int -> Int
 249 foreign import ccall nhc_primIntLsh :: Int -> Int -> Int
 250 foreign import ccall nhc_primIntRsh :: Int -> Int -> Int
 251 foreign import ccall nhc_primIntCompl :: Int -> Int
 252
 253 instance Bits Integer where
 254  -- (.&.) a b          = undefined
 255  -- (.|.) a b          = undefined
 256  -- xor a b            = undefined
 257     complement a       = (-a)
 258     x `shift` i | i<0  = x `div` (2^(-i))
 259                 | i==0 = x
 260                 | i>0  = x * (2^i)
 261     x `rotate` i       = x `shift` i    -- an Integer never wraps
 262     bitSize _          = error "Data.Bits: bitSize :: Integer -> Int"
 263     isSigned _         = True
 264
 265 #endif
 266