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