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