[project @ 2003-01-30 20:41:10 by panne]
[packages/random.git] / Data / Bits.hs
index c280fe2..bbd8fe1 100644 (file)
@@ -3,15 +3,17 @@
 -- |
 -- Module      :  Data.Bits
 -- Copyright   :  (c) The University of Glasgow 2001
--- License     :  BSD-style (see the file libraries/core/LICENSE)
+-- License     :  BSD-style (see the file libraries/base/LICENSE)
 -- 
 -- Maintainer  :  libraries@haskell.org
 -- Stability   :  experimental
 -- Portability :  portable
 --
--- $Id: Bits.hs,v 1.5 2002/04/24 16:31:39 simonmar Exp $
---
--- Bitwise operations.
+--  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
+--  "Int" and "Word" modules.
 --
 -----------------------------------------------------------------------------
 
@@ -27,10 +29,11 @@ module Data.Bits (
     complementBit,     -- :: a -> Int -> a
     testBit,           -- :: a -> Int -> Bool
     bitSize,           -- :: a -> Int
-    isSigned           -- :: a -> Bool
-  ),
-  shiftL, shiftR,      -- :: Bits a => a -> Int -> a
-  rotateL, rotateR,    -- :: Bits a => a -> Int -> a
+    isSigned,          -- :: a -> Bool
+    shiftL, shiftR,    -- :: a -> Int -> a
+    rotateL, rotateR   -- :: a -> Int -> a
+  )
+
   -- instance Bits Int
   -- instance Bits Integer
  ) where
@@ -46,41 +49,135 @@ import GHC.Real
 import GHC.Base
 #endif
 
---ADR: The fixity for .|. conflicts with that for .|. in Fran.
---     Removing all fixities is a fairly safe fix; fixing the "one fixity
---     per symbol per program" limitation in Hugs would take a lot longer.
-#ifndef __HUGS__
 infixl 8 `shift`, `rotate`, `shiftL`, `shiftR`, `rotateL`, `rotateR`
 infixl 7 .&.
 infixl 6 `xor`
 infixl 5 .|.
-#endif
 
+{-| 
+The 'Bits' class defines bitwise operations over integral types.
+
+* Bits are numbered from 0 with bit 0 being the least
+  significant bit.
+-}
 class Num a => Bits a where
-    (.&.), (.|.), xor :: a -> a -> a
+    -- | Bitwise \"and\"
+    (.&.) :: a -> a -> a
+
+    -- | Bitwise \"or\"
+    (.|.) :: a -> a -> a
+
+    -- | Bitwise \"xor\"
+    xor :: a -> a -> a
+
+    {-| Reverse all the bits in the argument -}
     complement        :: a -> a
+
+    {-| Shift the argument left by the specified number of bits.
+       Right shifts (signed) are specified by giving a negative value.
+
+       An instance can define either this unified 'shift' or 'shiftL' and
+       'shiftR', depending on which is more convenient for the type in
+       question. -}
     shift             :: a -> Int -> a
+
+    x `shift`   i | i<0  = x `shiftR` (-i)
+                  | i==0 = x
+                  | i>0  = x `shiftL` i
+
+    {-| Rotate the argument left by the specified number of bits.
+       Right rotates are specified by giving a negative value.
+
+        'rotate' is well defined only if 'bitSize' is also well defined
+        ('bitSize' is undefined for 'Integer', for example).
+
+       An instance can define either this unified 'rotate' or 'rotateL' and
+       'rotateR', depending on which is more convenient for the type in
+       question. -}
     rotate            :: a -> Int -> a
+
+    x `rotate`  i | i<0  = x `rotateR` (-i)
+                  | i==0 = x
+                  | i>0  = x `rotateL` i
+
+    {-
+    -- 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))
+    -}
+
+    -- | @bit i@ is a value with the @i@th bit set
     bit               :: Int -> a
+
+    -- | @x \`setBit\` i@ is the same as @x .|. bit i@
     setBit            :: a -> Int -> a
+
+    -- | @x \`clearBit\` i@ is the same as @x .&. complement (bit i)@
     clearBit          :: a -> Int -> a
+
+    -- | @x \`complementBit\` i@ is the same as @x \`xor\` bit i@
     complementBit     :: a -> Int -> a
+
+    -- | Return 'True' if the @n@th bit of the argument is 1
     testBit           :: a -> Int -> Bool
+
+    {-| Return the number of bits in the type of the argument.  The actual
+        value of the argument is ignored -}
     bitSize           :: a -> Int
+
+    {-| Return 'True' if the argument is a signed type.  The actual
+        value of the argument is ignored -}
     isSigned          :: a -> Bool
 
-    bit i               = 1 `shift` i
+    bit i               = 1 `shiftL` i
     x `setBit` i        = x .|. bit i
     x `clearBit` i      = x .&. complement (bit i)
     x `complementBit` i = x `xor` bit i
     x `testBit` i       = (x .&. bit i) /= 0
 
-shiftL, shiftR   :: Bits a => a -> Int -> a
-rotateL, rotateR :: Bits a => a -> Int -> a
-x `shiftL`  i = x `shift`  i
-x `shiftR`  i = x `shift`  (-i)
-x `rotateL` i = x `rotate` i
-x `rotateR` i = x `rotate` (-i)
+    {-| Shift the argument left by the specified number of bits
+       (which must be non-negative).
+
+       An instance can define either this and 'shiftR' or the unified
+       'shift', depending on which is more convenient for the type in
+       question. -}
+    shiftL            :: a -> Int -> a
+    x `shiftL`  i = x `shift`  i
+
+    {-| Shift the argument right (signed) by the specified number of bits
+       (which must be non-negative).
+
+       An instance can define either this and 'shiftL' or the unified
+       'shift', depending on which is more convenient for the type in
+       question. -}
+    shiftR            :: a -> Int -> a
+    x `shiftR`  i = x `shift`  (-i)
+
+    {-| Rotate the argument left by the specified number of bits
+       (which must be non-negative).
+
+       An instance can define either this and 'rotateR' or the unified
+       'rotate', depending on which is more convenient for the type in
+       question. -}
+    rotateL           :: a -> Int -> a
+    x `rotateL` i = x `rotate` i
+
+    {-| Rotate the argument right by the specified number of bits
+       (which must be non-negative).
+
+       An instance can define either this and 'rotateL' or the unified
+       'rotate', depending on which is more convenient for the type in
+       question. -}
+    rotateR           :: a -> Int -> a
+    x `rotateR` i = x `rotate` (-i)
 
 #ifdef __GLASGOW_HASKELL__
 instance Bits Int where
@@ -134,3 +231,36 @@ instance Bits Integer where
    bitSize _  = error "Bits.bitSize(Integer)"
    isSigned _ = True
 #endif
+
+#ifdef __NHC__
+instance Bits Int where
+    (.&.)             = nhc_primIntAnd
+    (.|.)             = nhc_primIntOr
+    xor               = nhc_primIntXor
+    complement        = nhc_primIntCompl
+    shiftL            = nhc_primIntLsh
+    shiftR            = nhc_primIntRsh
+    bitSize _         = 32
+    isSigned _        = True
+
+foreign import ccall nhc_primIntAnd :: Int -> Int -> Int
+foreign import ccall nhc_primIntOr  :: Int -> Int -> Int
+foreign import ccall nhc_primIntXor :: Int -> Int -> Int
+foreign import ccall nhc_primIntLsh :: Int -> Int -> Int
+foreign import ccall nhc_primIntRsh :: Int -> Int -> Int
+foreign import ccall nhc_primIntCompl :: Int -> Int
+
+instance Bits Integer where
+ -- (.&.) a b          = undefined
+ -- (.|.) a b          = undefined
+ -- xor a b            = undefined
+    complement a       = (-a)
+    x `shift` i | i<0  = x `div` (2^(-i))
+                | i==0 = x
+                | i>0  = x * (2^i)
+    x `rotate` i       = x `shift` i   -- an Integer never wraps
+    bitSize _          = error "Data.Bits: bitSize :: Integer -> Int"
+    isSigned _         = True
+
+#endif
+