1-- |
2-- Module      : Basement.Bits
3-- License     : BSD-style
4-- Maintainer  : Haskell Foundation
5-- Stability   : experimental
6-- Portability : portable
7--
8
9{-# LANGUAGE CPP #-}
10{-# LANGUAGE MagicHash #-}
11{-# LANGUAGE DataKinds #-}
12{-# LANGUAGE DefaultSignatures #-}
13{-# LANGUAGE TypeOperators #-}
14{-# LANGUAGE ConstraintKinds #-}
15{-# LANGUAGE Rank2Types #-}
16{-# LANGUAGE TypeApplications #-}
17{-# LANGUAGE ScopedTypeVariables #-}
18{-# LANGUAGE TypeSynonymInstances #-}
19{-# LANGUAGE UndecidableInstances #-}
20{-# LANGUAGE NegativeLiterals #-}
21
22#include "MachDeps.h"
23
24module Basement.Bits
25    ( BitOps(..)
26    , FiniteBitsOps(..)
27    , Bits
28    , toBits
29    , allOne
30    ) where
31
32import Basement.Compat.Base
33import Basement.Compat.Natural
34import Basement.Numerical.Additive
35import Basement.Numerical.Subtractive
36import Basement.Numerical.Multiplicative
37import Basement.Types.OffsetSize
38import Basement.Types.Word128 (Word128)
39import qualified Basement.Types.Word128 as Word128
40import Basement.Types.Word256 (Word256)
41import qualified Basement.Types.Word256 as Word256
42import Basement.IntegralConv (wordToInt)
43import Basement.Nat
44
45import qualified Prelude
46import qualified Data.Bits as OldBits
47import Data.Maybe (fromMaybe)
48import Data.Proxy
49import GHC.Base hiding ((.))
50import GHC.Prim
51import GHC.Types
52import GHC.Word
53import GHC.Int
54
55#if WORD_SIZE_IN_BITS < 64
56import GHC.IntWord64
57#endif
58
59-- | operation over finite bits
60class FiniteBitsOps bits where
61    -- | get the number of bits in the given object
62    --
63    numberOfBits :: bits -> CountOf Bool
64
65    -- | rotate the given bit set.
66    rotateL :: bits -> CountOf Bool -> bits
67    -- | rotate the given bit set.
68    rotateR :: bits -> CountOf Bool -> bits
69
70    -- | count of number of bit set to 1 in the given bit set.
71    popCount :: bits -> CountOf Bool
72
73    -- | reverse all bits in the argument
74    bitFlip   :: bits -> bits
75
76    -- | count of the number of leading zeros
77    countLeadingZeros :: bits -> CountOf Bool
78    default countLeadingZeros :: BitOps bits => bits -> CountOf Bool
79    countLeadingZeros n = loop stop azero
80      where
81        stop = numberOfBits n
82        loop idx count
83            | idx == azero = count
84            | isBitSet n (sizeAsOffset idx) = count
85            | otherwise = loop (fromMaybe azero (idx - 1)) (count + 1)
86
87    -- | count of the number of trailing zeros
88    countTrailingZeros :: bits -> CountOf Bool
89    default countTrailingZeros :: BitOps bits => bits -> CountOf Bool
90    countTrailingZeros n = loop azero
91      where
92        stop = numberOfBits n
93        loop count
94            | count == stop = count
95            | isBitSet n (sizeAsOffset count) = count
96            | otherwise = loop (count + 1)
97
98-- | operation over bits
99class BitOps bits where
100    (.&.)     :: bits -> bits -> bits
101    (.|.)     :: bits -> bits -> bits
102    (.^.)     :: bits -> bits -> bits
103    (.<<.)    :: bits -> CountOf Bool -> bits
104    (.>>.)    :: bits -> CountOf Bool -> bits
105    -- | construct a bit set with the bit at the given index set.
106    bit       :: Offset Bool -> bits
107    default bit :: Integral bits => Offset Bool -> bits
108    bit n = 1 .<<. (offsetAsSize n)
109
110    -- | test the bit at the given index is set
111    isBitSet  :: bits -> Offset Bool -> Bool
112    default isBitSet :: (Integral bits, Eq bits) => bits -> Offset Bool -> Bool
113    isBitSet x n = x .&. (bit n) /= 0
114
115    -- | set the bit at the given index
116    setBit    :: bits -> Offset Bool -> bits
117    default setBit :: Integral bits => bits -> Offset Bool -> bits
118    setBit x n = x .|. (bit n)
119
120    -- | clear the bit at the given index
121    clearBit  :: bits -> Offset Bool -> bits
122    default clearBit :: FiniteBitsOps bits => bits -> Offset Bool -> bits
123    clearBit x n = x .&. (bitFlip (bit n))
124
125infixl 8 .<<., .>>., `rotateL`, `rotateR`
126infixl 7 .&.
127infixl 6 .^.
128infixl 5 .|.
129
130-- | Bool set of 'n' bits.
131--
132newtype Bits (n :: Nat) = Bits { bitsToNatural :: Natural }
133  deriving (Show, Eq, Ord, Typeable)
134
135-- | convenient Type Constraint Alias fot 'Bits' functions
136type SizeValid n = (KnownNat n, 1 <= n)
137
138-- convert an 'Int' into a 'Natural'.
139-- This functions is not meant to be exported
140lift :: Int -> Natural
141lift = Prelude.fromIntegral
142{-# INLINABLE lift #-}
143
144-- | convert the given 'Natural' into a 'Bits' of size 'n'
145--
146-- if bits that are not within the boundaries of the 'Bits n' will be truncated.
147toBits :: SizeValid n => Natural -> Bits n
148toBits nat = Bits nat .&. allOne
149
150-- | construct a 'Bits' with all bits set.
151--
152-- this function is equivalet to 'maxBound'
153allOne :: forall n . SizeValid n => Bits n
154allOne = Bits (2 Prelude.^ n Prelude.- midentity)
155  where
156    n = natVal (Proxy @n)
157
158instance SizeValid n => Enum (Bits n) where
159    toEnum i | i < 0 && lift i > bitsToNatural maxi = error "Bits n not within bound"
160             | otherwise                            = Bits (lift i)
161      where maxi = allOne :: Bits n
162    fromEnum (Bits n) = fromEnum n
163instance SizeValid n => Bounded (Bits n) where
164    minBound = azero
165    maxBound = allOne
166instance SizeValid n => Additive (Bits n) where
167    azero = Bits 0
168    (+) (Bits a) (Bits b) = toBits (a + b)
169    scale n (Bits a) = toBits (scale n a)
170instance SizeValid n => Subtractive (Bits n) where
171    type Difference (Bits n) = Bits n
172    (-) (Bits a) (Bits b) = maybe azero toBits (a - b)
173instance SizeValid n => Multiplicative (Bits n) where
174    midentity = Bits 1
175    (*) (Bits a) (Bits b) = Bits (a Prelude.* b)
176instance SizeValid n => IDivisible (Bits n) where
177    div (Bits a) (Bits b) = Bits (a `Prelude.div` b)
178    mod (Bits a) (Bits b) = Bits (a `Prelude.mod` b)
179    divMod (Bits a) (Bits b) = let (q, r) = Prelude.divMod a b in (Bits q, Bits r)
180
181instance SizeValid n => BitOps (Bits n) where
182    (.&.)    (Bits a) (Bits b)    = Bits (a OldBits..&. b)
183    (.|.)    (Bits a) (Bits b)    = Bits (a OldBits..|. b)
184    (.^.)    (Bits a) (Bits b)    = Bits (a `OldBits.xor` b)
185    (.<<.)   (Bits a) (CountOf w) = Bits (a `OldBits.shiftL` w)
186    (.>>.)   (Bits a) (CountOf w) = Bits (a `OldBits.shiftR` w)
187    bit               (Offset w)  = Bits (OldBits.bit w)
188    isBitSet (Bits a) (Offset w)  = OldBits.testBit a w
189    setBit   (Bits a) (Offset w)  = Bits (OldBits.setBit a w)
190    clearBit (Bits a) (Offset w)  = Bits (OldBits.clearBit a w)
191instance (SizeValid n, NatWithinBound (CountOf Bool) n) => FiniteBitsOps (Bits n) where
192    bitFlip (Bits a) = Bits (OldBits.complement a)
193    numberOfBits _ = natValCountOf (Proxy @n)
194    rotateL a i = (a .<<. i) .|. (a .>>. d)
195      where
196        n = natValCountOf (Proxy :: Proxy n)
197        d = fromMaybe (fromMaybe (error "impossible") (i - n)) (n - i)
198    rotateR a i = (a .>>. i) .|. (a .<<. d)
199      where
200        n = natValCountOf (Proxy :: Proxy n)
201        d = fromMaybe (fromMaybe (error "impossible") (i - n)) (n - i)
202    popCount (Bits n) = CountOf (OldBits.popCount n)
203
204-- Bool ------------------------------------------------------------------------
205
206instance FiniteBitsOps Bool where
207    numberOfBits _ = 1
208    rotateL x _ = x
209    rotateR x _ = x
210    popCount True = 1
211    popCount False = 0
212    bitFlip  = not
213    countLeadingZeros True  = 0
214    countLeadingZeros False = 1
215    countTrailingZeros True  = 0
216    countTrailingZeros False = 1
217instance BitOps Bool where
218    (.&.) = (&&)
219    (.|.) = (||)
220    (.^.) = (/=)
221    x .<<. 0 = x
222    _ .<<. _ = False
223    x .>>. 0 = x
224    _ .>>. _ = False
225    bit 0 = True
226    bit _ = False
227    isBitSet x 0 = x
228    isBitSet _ _ = False
229    setBit _ 0 = True
230    setBit _ _ = False
231    clearBit _ 0 = False
232    clearBit x _ = x
233
234-- Word8 ----------------------------------------------------------------------
235
236instance FiniteBitsOps Word8 where
237    numberOfBits _ = 8
238    rotateL (W8# x#) (CountOf (I# i#))
239        | isTrue# (i'# ==# 0#) = W8# x#
240        | otherwise  = W8# (narrow8Word# ((x# `uncheckedShiftL#` i'#) `or#`
241                                          (x# `uncheckedShiftRL#` (8# -# i'#))))
242      where
243        !i'# = word2Int# (int2Word# i# `and#` 7##)
244    rotateR (W8# x#) (CountOf (I# i#))
245        | isTrue# (i'# ==# 0#) = W8# x#
246        | otherwise  = W8# (narrow8Word# ((x# `uncheckedShiftRL#` i'#) `or#`
247                                          (x# `uncheckedShiftL#` (8# -# i'#))))
248      where
249        !i'# = word2Int# (int2Word# i# `and#` 7##)
250    bitFlip (W8# x#) = W8# (x# `xor#` mb#)
251        where !(W8# mb#) = maxBound
252    popCount (W8# x#) = CountOf $ wordToInt (W# (popCnt8# x#))
253    countLeadingZeros (W8# w#) = CountOf $ wordToInt (W# (clz8# w#))
254    countTrailingZeros (W8# w#) = CountOf $ wordToInt (W# (ctz8# w#))
255instance BitOps Word8 where
256    (W8# x#) .&. (W8# y#)   = W8# (x# `and#` y#)
257    (W8# x#) .|. (W8# y#)   = W8# (x# `or#`  y#)
258    (W8# x#) .^. (W8# y#)   = W8# (x# `xor#` y#)
259    (W8# x#) .<<. (CountOf (I# i#)) = W8# (narrow8Word# (x# `shiftL#` i#))
260    (W8# x#) .>>. (CountOf (I# i#)) = W8# (narrow8Word# (x# `shiftRL#` i#))
261
262-- Word16 ---------------------------------------------------------------------
263
264instance FiniteBitsOps Word16 where
265    numberOfBits _ = 16
266    rotateL (W16# x#) (CountOf (I# i#))
267        | isTrue# (i'# ==# 0#) = W16# x#
268        | otherwise  = W16# (narrow16Word# ((x# `uncheckedShiftL#` i'#) `or#`
269                                            (x# `uncheckedShiftRL#` (16# -# i'#))))
270      where
271        !i'# = word2Int# (int2Word# i# `and#` 15##)
272    rotateR (W16# x#) (CountOf (I# i#))
273        | isTrue# (i'# ==# 0#) = W16# x#
274        | otherwise  = W16# (narrow16Word# ((x# `uncheckedShiftRL#` i'#) `or#`
275                                            (x# `uncheckedShiftL#` (16# -# i'#))))
276      where
277        !i'# = word2Int# (int2Word# i# `and#` 15##)
278    bitFlip (W16# x#) = W16# (x# `xor#` mb#)
279        where !(W16# mb#) = maxBound
280    popCount (W16# x#) = CountOf $ wordToInt (W# (popCnt16# x#))
281    countLeadingZeros (W16# w#) = CountOf $ wordToInt (W# (clz16# w#))
282    countTrailingZeros (W16# w#) = CountOf $ wordToInt (W# (ctz16# w#))
283instance BitOps Word16 where
284    (W16# x#) .&. (W16# y#)   = W16# (x# `and#` y#)
285    (W16# x#) .|. (W16# y#)   = W16# (x# `or#`  y#)
286    (W16# x#) .^. (W16# y#)   = W16# (x# `xor#` y#)
287    (W16# x#) .<<. (CountOf (I# i#)) = W16# (narrow16Word# (x# `shiftL#` i#))
288    (W16# x#) .>>. (CountOf (I# i#)) = W16# (narrow16Word# (x# `shiftRL#` i#))
289
290-- Word32 ---------------------------------------------------------------------
291
292instance FiniteBitsOps Word32 where
293    numberOfBits _ = 32
294    rotateL (W32# x#) (CountOf (I# i#))
295        | isTrue# (i'# ==# 0#) = W32# x#
296        | otherwise  = W32# (narrow32Word# ((x# `uncheckedShiftL#` i'#) `or#`
297                                            (x# `uncheckedShiftRL#` (32# -# i'#))))
298      where
299        !i'# = word2Int# (int2Word# i# `and#` 31##)
300    rotateR (W32# x#) (CountOf (I# i#))
301        | isTrue# (i'# ==# 0#) = W32# x#
302        | otherwise  = W32# (narrow32Word# ((x# `uncheckedShiftRL#` i'#) `or#`
303                                            (x# `uncheckedShiftL#` (32# -# i'#))))
304      where
305        !i'# = word2Int# (int2Word# i# `and#` 31##)
306    bitFlip (W32# x#) = W32# (x# `xor#` mb#)
307        where !(W32# mb#) = maxBound
308    popCount (W32# x#) = CountOf $ wordToInt (W# (popCnt32# x#))
309    countLeadingZeros (W32# w#) = CountOf $ wordToInt (W# (clz32# w#))
310    countTrailingZeros (W32# w#) = CountOf $ wordToInt (W# (ctz32# w#))
311instance BitOps Word32 where
312    (W32# x#) .&. (W32# y#)   = W32# (x# `and#` y#)
313    (W32# x#) .|. (W32# y#)   = W32# (x# `or#`  y#)
314    (W32# x#) .^. (W32# y#)   = W32# (x# `xor#` y#)
315    (W32# x#) .<<. (CountOf (I# i#)) = W32# (narrow32Word# (x# `shiftL#` i#))
316    (W32# x#) .>>. (CountOf (I# i#)) = W32# (narrow32Word# (x# `shiftRL#` i#))
317
318-- Word ---------------------------------------------------------------------
319
320#if WORD_SIZE_IN_BITS == 64
321instance FiniteBitsOps Word where
322    numberOfBits _ = 64
323    rotateL (W# x#) (CountOf (I# i#))
324        | isTrue# (i'# ==# 0#) = W# x#
325        | otherwise  = W# ((x# `uncheckedShiftL#` i'#) `or#`
326                           (x# `uncheckedShiftRL#` (64# -# i'#)))
327      where
328        !i'# = word2Int# (int2Word# i# `and#` 63##)
329    rotateR (W# x#) (CountOf (I# i#))
330        | isTrue# (i'# ==# 0#) = W# x#
331        | otherwise  = W# ((x# `uncheckedShiftRL#` i'#) `or#`
332                           (x# `uncheckedShiftL#` (64# -# i'#)))
333      where
334        !i'# = word2Int# (int2Word# i# `and#` 63##)
335    bitFlip (W# x#) = W# (x# `xor#` mb#)
336        where !(W# mb#) = maxBound
337    popCount (W# x#) = CountOf $ wordToInt (W# (popCnt64# x#))
338    countLeadingZeros (W# w#) = CountOf $ wordToInt (W# (clz64# w#))
339    countTrailingZeros (W# w#) = CountOf $ wordToInt (W# (ctz64# w#))
340#else
341instance FiniteBitsOps Word where
342    numberOfBits _ = 32
343    rotateL (W# x#) (CountOf (I# i#))
344        | isTrue# (i'# ==# 0#) = W# x#
345        | otherwise  = W# ((x# `uncheckedShiftL#` i'#) `or#`
346                           (x# `uncheckedShiftRL#` (32# -# i'#)))
347      where
348        !i'# = word2Int# (int2Word# i# `and#` 31##)
349    rotateR (W# x#) (CountOf (I# i#))
350        | isTrue# (i'# ==# 0#) = W# x#
351        | otherwise  = W# ((x# `uncheckedShiftRL#` i'#) `or#`
352                           (x# `uncheckedShiftL#` (32# -# i'#)))
353      where
354        !i'# = word2Int# (int2Word# i# `and#` 31##)
355    bitFlip (W# x#) = W# (x# `xor#` mb#)
356        where !(W# mb#) = maxBound
357    popCount (W# x#) = CountOf $ wordToInt (W# (popCnt32# x#))
358    countLeadingZeros (W# w#) = CountOf $ wordToInt (W# (clz32# w#))
359    countTrailingZeros (W# w#) = CountOf $ wordToInt (W# (ctz32# w#))
360#endif
361
362instance BitOps Word where
363    (W# x#) .&. (W# y#)   = W# (x# `and#` y#)
364    (W# x#) .|. (W# y#)   = W# (x# `or#`  y#)
365    (W# x#) .^. (W# y#)   = W# (x# `xor#` y#)
366    (W# x#) .<<. (CountOf (I# i#)) = W# ((x# `shiftL#` i#))
367    (W# x#) .>>. (CountOf (I# i#)) = W# ((x# `shiftRL#` i#))
368
369-- Word64 ---------------------------------------------------------------------
370
371#if WORD_SIZE_IN_BITS == 64
372instance FiniteBitsOps Word64 where
373    numberOfBits _ = 64
374    rotateL (W64# x#) (CountOf (I# i#))
375        | isTrue# (i'# ==# 0#) = W64# x#
376        | otherwise  = W64# ((x# `uncheckedShiftL#` i'#) `or#`
377                             (x# `uncheckedShiftRL#` (64# -# i'#)))
378      where
379        !i'# = word2Int# (int2Word# i# `and#` 63##)
380    rotateR (W64# x#) (CountOf (I# i#))
381        | isTrue# (i'# ==# 0#) = W64# x#
382        | otherwise  = W64# ((x# `uncheckedShiftRL#` i'#) `or#`
383                             (x# `uncheckedShiftL#` (64# -# i'#)))
384      where
385        !i'# = word2Int# (int2Word# i# `and#` 63##)
386    bitFlip (W64# x#) = W64# (x# `xor#` mb#)
387        where !(W64# mb#) = maxBound
388    popCount (W64# x#) = CountOf $ wordToInt (W# (popCnt64# x#))
389    countLeadingZeros (W64# w#) = CountOf $ wordToInt (W# (clz64# w#))
390    countTrailingZeros (W64# w#) = CountOf $ wordToInt (W# (ctz64# w#))
391instance BitOps Word64 where
392    (W64# x#) .&. (W64# y#)   = W64# (x# `and#` y#)
393    (W64# x#) .|. (W64# y#)   = W64# (x# `or#`  y#)
394    (W64# x#) .^. (W64# y#)   = W64# (x# `xor#` y#)
395    (W64# x#) .<<. (CountOf (I# i#)) = W64# (x# `shiftL#` i#)
396    (W64# x#) .>>. (CountOf (I# i#)) = W64# (x# `shiftRL#` i#)
397#else
398instance FiniteBitsOps Word64 where
399    numberOfBits _ = 64
400    rotateL (W64# x#) (CountOf (I# i#))
401        | isTrue# (i'# ==# 0#) = W64# x#
402        | otherwise  = W64# ((x# `uncheckedShiftL64#` i'#) `or64#`
403                             (x# `uncheckedShiftRL64#` (64# -# i'#)))
404      where
405        !i'# = word2Int# (int2Word# i# `and#` 63##)
406    rotateR (W64# x#) (CountOf (I# i#))
407        | isTrue# (i'# ==# 0#) = W64# x#
408        | otherwise  = W64# ((x# `uncheckedShiftRL64#` i'#) `or64#`
409                             (x# `uncheckedShiftL64#` (64# -# i'#)))
410      where
411        !i'# = word2Int# (int2Word# i# `and#` 63##)
412    bitFlip (W64# x#) = W64# (not64# x#)
413    popCount (W64# x#) = CountOf $ wordToInt (W# (popCnt64# x#))
414    countLeadingZeros (W64# w#) = CountOf $ wordToInt (W# (clz64# w#))
415    countTrailingZeros (W64# w#) = CountOf $ wordToInt (W# (ctz64# w#))
416instance BitOps Word64 where
417    (W64# x#) .&. (W64# y#)   = W64# (x# `and64#` y#)
418    (W64# x#) .|. (W64# y#)   = W64# (x# `or64#`  y#)
419    (W64# x#) .^. (W64# y#)   = W64# (x# `xor64#` y#)
420    (W64# x#) .<<. (CountOf (I# i#)) = W64# (x# `shiftL64#` i#)
421    (W64# x#) .>>. (CountOf (I# i#)) = W64# (x# `shiftRL64#` i#)
422
423shiftL64#, shiftRL64# :: Word64# -> Int# -> Word64#
424a `shiftL64#` b  | isTrue# (b >=# 64#) = wordToWord64# 0##
425                 | otherwise           = a `uncheckedShiftL64#` b
426a `shiftRL64#` b | isTrue# (b >=# 64#) = wordToWord64# 0##
427                 | otherwise           = a `uncheckedShiftRL64#` b
428#endif
429
430-- Word128 --------------------------------------------------------------------
431
432instance FiniteBitsOps Word128 where
433    numberOfBits _ = 128
434    rotateL w (CountOf n) = Word128.rotateL w n
435    rotateR w (CountOf n) = Word128.rotateR w n
436    bitFlip = Word128.complement
437    popCount = CountOf . Word128.popCount
438instance BitOps Word128 where
439    (.&.) = Word128.bitwiseAnd
440    (.|.) = Word128.bitwiseOr
441    (.^.) = Word128.bitwiseXor
442    (.<<.) w (CountOf n) = Word128.shiftL w n
443    (.>>.) w (CountOf n) = Word128.shiftR w n
444
445-- Word256 --------------------------------------------------------------------
446
447instance FiniteBitsOps Word256 where
448    numberOfBits _ = 256
449    rotateL w (CountOf n) = Word256.rotateL w n
450    rotateR w (CountOf n) = Word256.rotateR w n
451    bitFlip = Word256.complement
452    popCount = CountOf . Word256.popCount
453instance BitOps Word256 where
454    (.&.) = Word256.bitwiseAnd
455    (.|.) = Word256.bitwiseOr
456    (.^.) = Word256.bitwiseXor
457    (.<<.) w (CountOf n) = Word256.shiftL w n
458    (.>>.) w (CountOf n) = Word256.shiftR w n
459
460-- Int8 -----------------------------------------------------------------------
461
462instance FiniteBitsOps Int8 where
463    numberOfBits _ = 8
464    rotateL (I8# x#) (CountOf (I# i#))
465        | isTrue# (i'# ==# 0#) = I8# x#
466        | otherwise  = I8# (narrow8Int# (word2Int# ((x'# `uncheckedShiftL#` i'#) `or#`
467                                                    (x'# `uncheckedShiftRL#` (8# -# i'#)))))
468      where
469        !x'# = narrow8Word# (int2Word# x#)
470        !i'# = word2Int# (int2Word# i# `and#` 7##)
471    rotateR (I8# x#) (CountOf (I# i#))
472        | isTrue# (i'# ==# 0#) = I8# x#
473        | otherwise  = I8# (narrow8Int# (word2Int# ((x'# `uncheckedShiftRL#` i'#) `or#`
474                                                    (x'# `uncheckedShiftL#` (8# -# i'#)))))
475      where
476        !x'# = narrow8Word# (int2Word# x#)
477        !i'# = word2Int# (int2Word# i# `and#` 7##)
478    bitFlip (I8# x#) = I8# (word2Int# (not# (int2Word# x#)))
479    popCount (I8# x#) = CountOf $ wordToInt (W# (popCnt8# (int2Word# x#)))
480    countLeadingZeros (I8# w#) = CountOf $ wordToInt (W# (clz8# (int2Word# w#)))
481    countTrailingZeros (I8# w#) = CountOf $ wordToInt (W# (ctz8# (int2Word# w#)))
482instance BitOps Int8 where
483    (I8# x#) .&. (I8# y#)   = I8# (x# `andI#` y#)
484    (I8# x#) .|. (I8# y#)   = I8# (x# `orI#`  y#)
485    (I8# x#) .^. (I8# y#)   = I8# (x# `xorI#` y#)
486    (I8# x#) .<<. (CountOf (I# i#)) = I8# (narrow8Int# (x# `iShiftL#`  i#))
487    (I8# x#) .>>. (CountOf (I# i#)) = I8# (narrow8Int# (x# `iShiftRL#` i#))
488
489-- Int16 ----------------------------------------------------------------------
490
491instance FiniteBitsOps Int16 where
492    numberOfBits _ = 16
493    rotateL (I16# x#) (CountOf (I# i#))
494        | isTrue# (i'# ==# 0#) = I16# x#
495        | otherwise  = I16# (narrow16Int# (word2Int# ((x'# `uncheckedShiftL#` i'#) `or#`
496                                                      (x'# `uncheckedShiftRL#` (16# -# i'#)))))
497      where
498        !x'# = narrow16Word# (int2Word# x#)
499        !i'# = word2Int# (int2Word# i# `and#` 15##)
500    rotateR (I16# x#) (CountOf (I# i#))
501        | isTrue# (i'# ==# 0#) = I16# x#
502        | otherwise  = I16# (narrow16Int# (word2Int# ((x'# `uncheckedShiftRL#` i'#) `or#`
503                                                      (x'# `uncheckedShiftL#` (16# -# i'#)))))
504      where
505        !x'# = narrow16Word# (int2Word# x#)
506        !i'# = word2Int# (int2Word# i# `and#` 15##)
507    bitFlip (I16# x#) = I16# (word2Int# (not# (int2Word# x#)))
508    popCount (I16# x#) = CountOf $ wordToInt (W# (popCnt16# (int2Word# x#)))
509    countLeadingZeros (I16# w#) = CountOf $ wordToInt (W# (clz16# (int2Word# w#)))
510    countTrailingZeros (I16# w#) = CountOf $ wordToInt (W# (ctz16# (int2Word# w#)))
511instance BitOps Int16 where
512    (I16# x#) .&. (I16# y#)   = I16# (x# `andI#` y#)
513    (I16# x#) .|. (I16# y#)   = I16# (x# `orI#`  y#)
514    (I16# x#) .^. (I16# y#)   = I16# (x# `xorI#` y#)
515    (I16# x#) .<<. (CountOf (I# i#)) = I16# (narrow16Int# (x# `iShiftL#`  i#))
516    (I16# x#) .>>. (CountOf (I# i#)) = I16# (narrow16Int# (x# `iShiftRL#` i#))
517
518-- Int32 ----------------------------------------------------------------------
519
520instance FiniteBitsOps Int32 where
521    numberOfBits _ = 32
522    rotateL (I32# x#) (CountOf (I# i#))
523        | isTrue# (i'# ==# 0#) = I32# x#
524        | otherwise  = I32# (narrow32Int# (word2Int# ((x'# `uncheckedShiftL#` i'#) `or#`
525                                                      (x'# `uncheckedShiftRL#` (32# -# i'#)))))
526      where
527        !x'# = narrow32Word# (int2Word# x#)
528        !i'# = word2Int# (int2Word# i# `and#` 31##)
529    rotateR (I32# x#) (CountOf (I# i#))
530        | isTrue# (i'# ==# 0#) = I32# x#
531        | otherwise  = I32# (narrow32Int# (word2Int# ((x'# `uncheckedShiftRL#` i'#) `or#`
532                                                      (x'# `uncheckedShiftL#` (32# -# i'#)))))
533      where
534        !x'# = narrow32Word# (int2Word# x#)
535        !i'# = word2Int# (int2Word# i# `and#` 31##)
536    bitFlip (I32# x#) = I32# (word2Int# (not# (int2Word# x#)))
537    popCount (I32# x#) = CountOf $ wordToInt (W# (popCnt32# (int2Word# x#)))
538    countLeadingZeros (I32# w#) = CountOf $ wordToInt (W# (clz32# (int2Word# w#)))
539    countTrailingZeros (I32# w#) = CountOf $ wordToInt (W# (ctz32# (int2Word# w#)))
540instance BitOps Int32 where
541    (I32# x#) .&. (I32# y#)   = I32# (x# `andI#` y#)
542    (I32# x#) .|. (I32# y#)   = I32# (x# `orI#`  y#)
543    (I32# x#) .^. (I32# y#)   = I32# (x# `xorI#` y#)
544    (I32# x#) .<<. (CountOf (I# i#)) = I32# (narrow32Int# (x# `iShiftL#`  i#))
545    (I32# x#) .>>. (CountOf (I# i#)) = I32# (narrow32Int# (x# `iShiftRL#` i#))
546
547-- Int64 ----------------------------------------------------------------------
548
549#if WORD_SIZE_IN_BITS == 64
550instance FiniteBitsOps Int64 where
551    numberOfBits _ = 64
552    rotateL (I64# x#) (CountOf (I# i#))
553        | isTrue# (i'# ==# 0#) = I64# x#
554        | otherwise  = I64# (word2Int# ((x'# `uncheckedShiftL#` i'#) `or#`
555                                        (x'# `uncheckedShiftRL#` (64# -# i'#))))
556      where
557        !x'# = int2Word# x#
558        !i'# = word2Int# (int2Word# i# `and#` 63##)
559    rotateR (I64# x#) (CountOf (I# i#))
560        | isTrue# (i'# ==# 0#) = I64# x#
561        | otherwise  = I64# (word2Int# ((x'# `uncheckedShiftRL#` i'#) `or#`
562                                        (x'# `uncheckedShiftL#` (64# -# i'#))))
563      where
564        !x'# = int2Word# x#
565        !i'# = word2Int# (int2Word# i# `and#` 63##)
566    bitFlip (I64# x#) = I64# (word2Int# (int2Word# x# `xor#` int2Word# (-1#)))
567    popCount (I64# x#) = CountOf $ wordToInt (W# (popCnt64# (int2Word# x#)))
568    countLeadingZeros (I64# w#) = CountOf $ wordToInt (W# (clz64# (int2Word# w#)))
569    countTrailingZeros (I64# w#) = CountOf $ wordToInt (W# (ctz64# (int2Word# w#)))
570instance BitOps Int64 where
571    (I64# x#) .&. (I64# y#)   = I64# (x# `andI#` y#)
572    (I64# x#) .|. (I64# y#)   = I64# (x# `orI#`  y#)
573    (I64# x#) .^. (I64# y#)   = I64# (x# `xorI#` y#)
574    (I64# x#) .<<. (CountOf (I# w#)) = I64# (x# `iShiftL#`  w#)
575    (I64# x#) .>>. (CountOf (I# w#)) = I64# (x# `iShiftRL#` w#)
576#else
577instance FiniteBitsOps Int64 where
578    numberOfBits _ = 64
579    rotateL (I64# x#) (CountOf (I# i#))
580        | isTrue# (i'# ==# 0#) = I64# x#
581        | otherwise  = I64# (word64ToInt64# ((x'# `uncheckedShiftL64#` i'#) `or64#`
582                                             (x'# `uncheckedShiftRL64#` (64# -# i'#))))
583      where
584        !x'# = int64ToWord64# x#
585        !i'# = word2Int# (int2Word# i# `and#` 63##)
586    rotateR (I64# x#) (CountOf (I# i#))
587        | isTrue# (i'# ==# 0#) = I64# x#
588        | otherwise  = I64# (word64ToInt64# ((x'# `uncheckedShiftRL64#` i'#) `or64#`
589                                             (x'# `uncheckedShiftL64#` (64# -# i'#))))
590      where
591        !x'# = int64ToWord64# x#
592        !i'# = word2Int# (int2Word# i# `and#` 63##)
593    bitFlip (I64# x#) = I64# (word64ToInt64# (not64# (int64ToWord64# x#)))
594    popCount (I64# x#) = CountOf $ wordToInt (W# (popCnt64# (int64ToWord64# x#)))
595    countLeadingZeros (I64# w#) = CountOf $ wordToInt (W# (clz64# (int64ToWord64# w#)))
596    countTrailingZeros (I64# w#) = CountOf $ wordToInt (W# (ctz64# (int64ToWord64# w#)))
597instance BitOps Int64 where
598    (I64# x#) .&. (I64# y#)  = I64# (word64ToInt64# (int64ToWord64# x# `and64#` int64ToWord64# y#))
599    (I64# x#) .|. (I64# y#)  = I64# (word64ToInt64# (int64ToWord64# x# `or64#`  int64ToWord64# y#))
600    (I64# x#) .^. (I64# y#)  = I64# (word64ToInt64# (int64ToWord64# x# `xor64#` int64ToWord64# y#))
601    (I64# x#) .<<. (CountOf (I# w#)) = I64# (x# `iShiftL64#`  w#)
602    (I64# x#) .>>. (CountOf (I# w#)) = I64# (x# `iShiftRA64#` w#)
603
604
605iShiftL64#, iShiftRA64# :: Int64# -> Int# -> Int64#
606a `iShiftL64#` b  | isTrue# (b >=# 64#) = intToInt64# 0#
607                  | otherwise           = a `uncheckedIShiftL64#` b
608a `iShiftRA64#` b | isTrue# (b >=# 64#) && isTrue# (a `ltInt64#` (intToInt64# 0#))
609                                        = intToInt64# (-1#)
610                  | isTrue# (b >=# 64#) = intToInt64# 0#
611                  | otherwise = a `uncheckedIShiftRA64#` b
612
613#endif
614