[project @ 2003-01-30 20:41:10 by panne]
[packages/random.git] / 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