69446f9adcc2050866aae1b2bce857e6f120633c
[ghc.git] / libraries / base / Data / Bits.hs
1 {-# LANGUAGE Trustworthy #-}
2 {-# LANGUAGE CPP, NoImplicitPrelude, BangPatterns, MagicHash #-}
3
4 -----------------------------------------------------------------------------
5 -- |
6 -- Module : Data.Bits
7 -- Copyright : (c) The University of Glasgow 2001
8 -- License : BSD-style (see the file libraries/base/LICENSE)
9 --
10 -- Maintainer : libraries@haskell.org
11 -- Stability : experimental
12 -- Portability : portable
13 --
14 -- This module defines bitwise operations for signed and unsigned
15 -- integers. Instances of the class 'Bits' for the 'Int' and
16 -- 'Integer' types are available from this module, and instances for
17 -- explicitly sized integral types are available from the
18 -- "Data.Int" and "Data.Word" modules.
19 --
20 -----------------------------------------------------------------------------
21
22 module Data.Bits (
23 Bits(
24 (.&.), (.|.), xor,
25 complement,
26 shift,
27 rotate,
28 zeroBits,
29 bit,
30 setBit,
31 clearBit,
32 complementBit,
33 testBit,
34 bitSizeMaybe,
35 bitSize,
36 isSigned,
37 shiftL, shiftR,
38 unsafeShiftL, unsafeShiftR,
39 rotateL, rotateR,
40 popCount
41 ),
42 FiniteBits(
43 finiteBitSize,
44 countLeadingZeros,
45 countTrailingZeros
46 ),
47
48 bitDefault,
49 testBitDefault,
50 popCountDefault,
51 toIntegralSized
52 ) where
53
54 -- Defines the @Bits@ class containing bit-based operations.
55 -- See library document for details on the semantics of the
56 -- individual operations.
57
58 #include "MachDeps.h"
59
60 import Data.Maybe
61 import GHC.Enum
62 import GHC.Num
63 import GHC.Base
64 import GHC.Real
65
66 infixl 8 `shift`, `rotate`, `shiftL`, `shiftR`, `rotateL`, `rotateR`
67 infixl 7 .&.
68 infixl 6 `xor`
69 infixl 5 .|.
70
71 {-# DEPRECATED bitSize "Use 'bitSizeMaybe' or 'finiteBitSize' instead" #-} -- deprecated in 7.8
72
73 -- | The 'Bits' class defines bitwise operations over integral types.
74 --
75 -- * Bits are numbered from 0 with bit 0 being the least
76 -- significant bit.
77 class Eq a => Bits a where
78 {-# MINIMAL (.&.), (.|.), xor, complement,
79 (shift | (shiftL, shiftR)),
80 (rotate | (rotateL, rotateR)),
81 bitSize, bitSizeMaybe, isSigned, testBit, bit, popCount #-}
82
83 -- | Bitwise \"and\"
84 (.&.) :: a -> a -> a
85
86 -- | Bitwise \"or\"
87 (.|.) :: a -> a -> a
88
89 -- | Bitwise \"xor\"
90 xor :: a -> a -> a
91
92 {-| Reverse all the bits in the argument -}
93 complement :: a -> a
94
95 {-| @'shift' x i@ shifts @x@ left by @i@ bits if @i@ is positive,
96 or right by @-i@ bits otherwise.
97 Right shifts perform sign extension on signed number types;
98 i.e. they fill the top bits with 1 if the @x@ is negative
99 and with 0 otherwise.
100
101 An instance can define either this unified 'shift' or 'shiftL' and
102 'shiftR', depending on which is more convenient for the type in
103 question. -}
104 shift :: a -> Int -> a
105
106 x `shift` i | i<0 = x `shiftR` (-i)
107 | i>0 = x `shiftL` i
108 | otherwise = x
109
110 {-| @'rotate' x i@ rotates @x@ left by @i@ bits if @i@ is positive,
111 or right by @-i@ bits otherwise.
112
113 For unbounded types like 'Integer', 'rotate' is equivalent to 'shift'.
114
115 An instance can define either this unified 'rotate' or 'rotateL' and
116 'rotateR', depending on which is more convenient for the type in
117 question. -}
118 rotate :: a -> Int -> a
119
120 x `rotate` i | i<0 = x `rotateR` (-i)
121 | i>0 = x `rotateL` i
122 | otherwise = x
123
124 {-
125 -- Rotation can be implemented in terms of two shifts, but care is
126 -- needed for negative values. This suggested implementation assumes
127 -- 2's-complement arithmetic. It is commented out because it would
128 -- require an extra context (Ord a) on the signature of 'rotate'.
129 x `rotate` i | i<0 && isSigned x && x<0
130 = let left = i+bitSize x in
131 ((x `shift` i) .&. complement ((-1) `shift` left))
132 .|. (x `shift` left)
133 | i<0 = (x `shift` i) .|. (x `shift` (i+bitSize x))
134 | i==0 = x
135 | i>0 = (x `shift` i) .|. (x `shift` (i-bitSize x))
136 -}
137
138 -- | 'zeroBits' is the value with all bits unset.
139 --
140 -- The following laws ought to hold (for all valid bit indices @/n/@):
141 --
142 -- * @'clearBit' 'zeroBits' /n/ == 'zeroBits'@
143 -- * @'setBit' 'zeroBits' /n/ == 'bit' /n/@
144 -- * @'testBit' 'zeroBits' /n/ == False@
145 -- * @'popCount' 'zeroBits' == 0@
146 --
147 -- This method uses @'clearBit' ('bit' 0) 0@ as its default
148 -- implementation (which ought to be equivalent to 'zeroBits' for
149 -- types which possess a 0th bit).
150 --
151 -- @since 4.7.0.0
152 zeroBits :: a
153 zeroBits = clearBit (bit 0) 0
154
155 -- | @bit /i/@ is a value with the @/i/@th bit set and all other bits clear.
156 --
157 -- Can be implemented using `bitDefault' if @a@ is also an
158 -- instance of 'Num'.
159 --
160 -- See also 'zeroBits'.
161 bit :: Int -> a
162
163 -- | @x \`setBit\` i@ is the same as @x .|. bit i@
164 setBit :: a -> Int -> a
165
166 -- | @x \`clearBit\` i@ is the same as @x .&. complement (bit i)@
167 clearBit :: a -> Int -> a
168
169 -- | @x \`complementBit\` i@ is the same as @x \`xor\` bit i@
170 complementBit :: a -> Int -> a
171
172 -- | Return 'True' if the @n@th bit of the argument is 1
173 --
174 -- Can be implemented using `testBitDefault' if @a@ is also an
175 -- instance of 'Num'.
176 testBit :: a -> Int -> Bool
177
178 {-| Return the number of bits in the type of the argument. The actual
179 value of the argument is ignored. Returns Nothing
180 for types that do not have a fixed bitsize, like 'Integer'.
181
182 @since 4.7.0.0
183 -}
184 bitSizeMaybe :: a -> Maybe Int
185
186 {-| Return the number of bits in the type of the argument. The actual
187 value of the argument is ignored. The function 'bitSize' is
188 undefined for types that do not have a fixed bitsize, like 'Integer'.
189
190 Default implementation based upon 'bitSizeMaybe' provided since
191 4.12.0.0.
192 -}
193 bitSize :: a -> Int
194 bitSize b = fromMaybe (error "bitSize is undefined") (bitSizeMaybe b)
195
196 {-| Return 'True' if the argument is a signed type. The actual
197 value of the argument is ignored -}
198 isSigned :: a -> Bool
199
200 {-# INLINE setBit #-}
201 {-# INLINE clearBit #-}
202 {-# INLINE complementBit #-}
203 x `setBit` i = x .|. bit i
204 x `clearBit` i = x .&. complement (bit i)
205 x `complementBit` i = x `xor` bit i
206
207 {-| Shift the argument left by the specified number of bits
208 (which must be non-negative). Some instances may throw an
209 'Control.Exception.Overflow' exception if given a negative input.
210
211 An instance can define either this and 'shiftR' or the unified
212 'shift', depending on which is more convenient for the type in
213 question. -}
214 shiftL :: a -> Int -> a
215 {-# INLINE shiftL #-}
216 x `shiftL` i = x `shift` i
217
218 {-| Shift the argument left by the specified number of bits. The
219 result is undefined for negative shift amounts and shift amounts
220 greater or equal to the 'bitSize'.
221
222 Defaults to 'shiftL' unless defined explicitly by an instance.
223
224 @since 4.5.0.0 -}
225 unsafeShiftL :: a -> Int -> a
226 {-# INLINE unsafeShiftL #-}
227 x `unsafeShiftL` i = x `shiftL` i
228
229 {-| Shift the first argument right by the specified number of bits. The
230 result is undefined for negative shift amounts and shift amounts
231 greater or equal to the 'bitSize'. Some instances may throw an
232 'Control.Exception.Overflow' exception if given a negative input.
233
234 Right shifts perform sign extension on signed number types;
235 i.e. they fill the top bits with 1 if the @x@ is negative
236 and with 0 otherwise.
237
238 An instance can define either this and 'shiftL' or the unified
239 'shift', depending on which is more convenient for the type in
240 question. -}
241 shiftR :: a -> Int -> a
242 {-# INLINE shiftR #-}
243 x `shiftR` i = x `shift` (-i)
244
245 {-| Shift the first argument right by the specified number of bits, which
246 must be non-negative and smaller than the number of bits in the type.
247
248 Right shifts perform sign extension on signed number types;
249 i.e. they fill the top bits with 1 if the @x@ is negative
250 and with 0 otherwise.
251
252 Defaults to 'shiftR' unless defined explicitly by an instance.
253
254 @since 4.5.0.0 -}
255 unsafeShiftR :: a -> Int -> a
256 {-# INLINE unsafeShiftR #-}
257 x `unsafeShiftR` i = x `shiftR` i
258
259 {-| Rotate the argument left by the specified number of bits
260 (which must be non-negative).
261
262 An instance can define either this and 'rotateR' or the unified
263 'rotate', depending on which is more convenient for the type in
264 question. -}
265 rotateL :: a -> Int -> a
266 {-# INLINE rotateL #-}
267 x `rotateL` i = x `rotate` i
268
269 {-| Rotate the argument right by the specified number of bits
270 (which must be non-negative).
271
272 An instance can define either this and 'rotateL' or the unified
273 'rotate', depending on which is more convenient for the type in
274 question. -}
275 rotateR :: a -> Int -> a
276 {-# INLINE rotateR #-}
277 x `rotateR` i = x `rotate` (-i)
278
279 {-| Return the number of set bits in the argument. This number is
280 known as the population count or the Hamming weight.
281
282 Can be implemented using `popCountDefault' if @a@ is also an
283 instance of 'Num'.
284
285 @since 4.5.0.0 -}
286 popCount :: a -> Int
287
288 -- |The 'FiniteBits' class denotes types with a finite, fixed number of bits.
289 --
290 -- @since 4.7.0.0
291 class Bits b => FiniteBits b where
292 -- | Return the number of bits in the type of the argument.
293 -- The actual value of the argument is ignored. Moreover, 'finiteBitSize'
294 -- is total, in contrast to the deprecated 'bitSize' function it replaces.
295 --
296 -- @
297 -- 'finiteBitSize' = 'bitSize'
298 -- 'bitSizeMaybe' = 'Just' . 'finiteBitSize'
299 -- @
300 --
301 -- @since 4.7.0.0
302 finiteBitSize :: b -> Int
303
304 -- | Count number of zero bits preceding the most significant set bit.
305 --
306 -- @
307 -- 'countLeadingZeros' ('zeroBits' :: a) = finiteBitSize ('zeroBits' :: a)
308 -- @
309 --
310 -- 'countLeadingZeros' can be used to compute log base 2 via
311 --
312 -- @
313 -- logBase2 x = 'finiteBitSize' x - 1 - 'countLeadingZeros' x
314 -- @
315 --
316 -- Note: The default implementation for this method is intentionally
317 -- naive. However, the instances provided for the primitive
318 -- integral types are implemented using CPU specific machine
319 -- instructions.
320 --
321 -- @since 4.8.0.0
322 countLeadingZeros :: b -> Int
323 countLeadingZeros x = (w-1) - go (w-1)
324 where
325 go i | i < 0 = i -- no bit set
326 | testBit x i = i
327 | otherwise = go (i-1)
328
329 w = finiteBitSize x
330
331 -- | Count number of zero bits following the least significant set bit.
332 --
333 -- @
334 -- 'countTrailingZeros' ('zeroBits' :: a) = finiteBitSize ('zeroBits' :: a)
335 -- 'countTrailingZeros' . 'negate' = 'countTrailingZeros'
336 -- @
337 --
338 -- The related
339 -- <http://en.wikipedia.org/wiki/Find_first_set find-first-set operation>
340 -- can be expressed in terms of 'countTrailingZeros' as follows
341 --
342 -- @
343 -- findFirstSet x = 1 + 'countTrailingZeros' x
344 -- @
345 --
346 -- Note: The default implementation for this method is intentionally
347 -- naive. However, the instances provided for the primitive
348 -- integral types are implemented using CPU specific machine
349 -- instructions.
350 --
351 -- @since 4.8.0.0
352 countTrailingZeros :: b -> Int
353 countTrailingZeros x = go 0
354 where
355 go i | i >= w = i
356 | testBit x i = i
357 | otherwise = go (i+1)
358
359 w = finiteBitSize x
360
361
362 -- The defaults below are written with lambdas so that e.g.
363 -- bit = bitDefault
364 -- is fully applied, so inlining will happen
365
366 -- | Default implementation for 'bit'.
367 --
368 -- Note that: @bitDefault i = 1 `shiftL` i@
369 --
370 -- @since 4.6.0.0
371 bitDefault :: (Bits a, Num a) => Int -> a
372 bitDefault = \i -> 1 `shiftL` i
373 {-# INLINE bitDefault #-}
374
375 -- | Default implementation for 'testBit'.
376 --
377 -- Note that: @testBitDefault x i = (x .&. bit i) /= 0@
378 --
379 -- @since 4.6.0.0
380 testBitDefault :: (Bits a, Num a) => a -> Int -> Bool
381 testBitDefault = \x i -> (x .&. bit i) /= 0
382 {-# INLINE testBitDefault #-}
383
384 -- | Default implementation for 'popCount'.
385 --
386 -- This implementation is intentionally naive. Instances are expected to provide
387 -- an optimized implementation for their size.
388 --
389 -- @since 4.6.0.0
390 popCountDefault :: (Bits a, Num a) => a -> Int
391 popCountDefault = go 0
392 where
393 go !c 0 = c
394 go c w = go (c+1) (w .&. (w - 1)) -- clear the least significant
395 {-# INLINABLE popCountDefault #-}
396
397
398 -- | Interpret 'Bool' as 1-bit bit-field
399 --
400 -- @since 4.7.0.0
401 instance Bits Bool where
402 (.&.) = (&&)
403
404 (.|.) = (||)
405
406 xor = (/=)
407
408 complement = not
409
410 shift x 0 = x
411 shift _ _ = False
412
413 rotate x _ = x
414
415 bit 0 = True
416 bit _ = False
417
418 testBit x 0 = x
419 testBit _ _ = False
420
421 bitSizeMaybe _ = Just 1
422
423 bitSize _ = 1
424
425 isSigned _ = False
426
427 popCount False = 0
428 popCount True = 1
429
430 -- | @since 4.7.0.0
431 instance FiniteBits Bool where
432 finiteBitSize _ = 1
433 countTrailingZeros x = if x then 0 else 1
434 countLeadingZeros x = if x then 0 else 1
435
436 -- | @since 2.01
437 instance Bits Int where
438 {-# INLINE shift #-}
439 {-# INLINE bit #-}
440 {-# INLINE testBit #-}
441 -- We want popCnt# to be inlined in user code so that `ghc -msse4.2`
442 -- can compile it down to a popcnt instruction without an extra function call
443 {-# INLINE popCount #-}
444
445 zeroBits = 0
446
447 bit = bitDefault
448
449 testBit = testBitDefault
450
451 (I# x#) .&. (I# y#) = I# (x# `andI#` y#)
452 (I# x#) .|. (I# y#) = I# (x# `orI#` y#)
453 (I# x#) `xor` (I# y#) = I# (x# `xorI#` y#)
454 complement (I# x#) = I# (notI# x#)
455 (I# x#) `shift` (I# i#)
456 | isTrue# (i# >=# 0#) = I# (x# `iShiftL#` i#)
457 | otherwise = I# (x# `iShiftRA#` negateInt# i#)
458 (I# x#) `shiftL` (I# i#)
459 | isTrue# (i# >=# 0#) = I# (x# `iShiftL#` i#)
460 | otherwise = overflowError
461 (I# x#) `unsafeShiftL` (I# i#) = I# (x# `uncheckedIShiftL#` i#)
462 (I# x#) `shiftR` (I# i#)
463 | isTrue# (i# >=# 0#) = I# (x# `iShiftRA#` i#)
464 | otherwise = overflowError
465 (I# x#) `unsafeShiftR` (I# i#) = I# (x# `uncheckedIShiftRA#` i#)
466
467 {-# INLINE rotate #-} -- See Note [Constant folding for rotate]
468 (I# x#) `rotate` (I# i#) =
469 I# ((x# `uncheckedIShiftL#` i'#) `orI#` (x# `uncheckedIShiftRL#` (wsib -# i'#)))
470 where
471 !i'# = i# `andI#` (wsib -# 1#)
472 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
473 bitSizeMaybe i = Just (finiteBitSize i)
474 bitSize i = finiteBitSize i
475
476 popCount (I# x#) = I# (word2Int# (popCnt# (int2Word# x#)))
477
478 isSigned _ = True
479
480 -- | @since 4.6.0.0
481 instance FiniteBits Int where
482 finiteBitSize _ = WORD_SIZE_IN_BITS
483 countLeadingZeros (I# x#) = I# (word2Int# (clz# (int2Word# x#)))
484 {-# INLINE countLeadingZeros #-}
485 countTrailingZeros (I# x#) = I# (word2Int# (ctz# (int2Word# x#)))
486 {-# INLINE countTrailingZeros #-}
487
488 -- | @since 2.01
489 instance Bits Word where
490 {-# INLINE shift #-}
491 {-# INLINE bit #-}
492 {-# INLINE testBit #-}
493 {-# INLINE popCount #-}
494
495 (W# x#) .&. (W# y#) = W# (x# `and#` y#)
496 (W# x#) .|. (W# y#) = W# (x# `or#` y#)
497 (W# x#) `xor` (W# y#) = W# (x# `xor#` y#)
498 complement (W# x#) = W# (x# `xor#` mb#)
499 where !(W# mb#) = maxBound
500 (W# x#) `shift` (I# i#)
501 | isTrue# (i# >=# 0#) = W# (x# `shiftL#` i#)
502 | otherwise = W# (x# `shiftRL#` negateInt# i#)
503 (W# x#) `shiftL` (I# i#)
504 | isTrue# (i# >=# 0#) = W# (x# `shiftL#` i#)
505 | otherwise = overflowError
506 (W# x#) `unsafeShiftL` (I# i#) = W# (x# `uncheckedShiftL#` i#)
507 (W# x#) `shiftR` (I# i#)
508 | isTrue# (i# >=# 0#) = W# (x# `shiftRL#` i#)
509 | otherwise = overflowError
510 (W# x#) `unsafeShiftR` (I# i#) = W# (x# `uncheckedShiftRL#` i#)
511 (W# x#) `rotate` (I# i#)
512 | isTrue# (i'# ==# 0#) = W# x#
513 | otherwise = W# ((x# `uncheckedShiftL#` i'#) `or#` (x# `uncheckedShiftRL#` (wsib -# i'#)))
514 where
515 !i'# = i# `andI#` (wsib -# 1#)
516 !wsib = WORD_SIZE_IN_BITS# {- work around preprocessor problem (??) -}
517 bitSizeMaybe i = Just (finiteBitSize i)
518 bitSize i = finiteBitSize i
519 isSigned _ = False
520 popCount (W# x#) = I# (word2Int# (popCnt# x#))
521 bit = bitDefault
522 testBit = testBitDefault
523
524 -- | @since 4.6.0.0
525 instance FiniteBits Word where
526 finiteBitSize _ = WORD_SIZE_IN_BITS
527 countLeadingZeros (W# x#) = I# (word2Int# (clz# x#))
528 {-# INLINE countLeadingZeros #-}
529 countTrailingZeros (W# x#) = I# (word2Int# (ctz# x#))
530 {-# INLINE countTrailingZeros #-}
531
532 -- | @since 2.01
533 instance Bits Integer where
534 (.&.) = andInteger
535 (.|.) = orInteger
536 xor = xorInteger
537 complement = complementInteger
538 shift x i@(I# i#) | i >= 0 = shiftLInteger x i#
539 | otherwise = shiftRInteger x (negateInt# i#)
540 testBit x (I# i) = testBitInteger x i
541 zeroBits = 0
542
543 bit (I# i#) = bitInteger i#
544 popCount x = I# (popCountInteger x)
545
546 rotate x i = shift x i -- since an Integer never wraps around
547
548 bitSizeMaybe _ = Nothing
549 bitSize _ = errorWithoutStackTrace "Data.Bits.bitSize(Integer)"
550 isSigned _ = True
551
552 -- | @since 4.8.0
553 instance Bits Natural where
554 (.&.) = andNatural
555 (.|.) = orNatural
556 xor = xorNatural
557 complement _ = errorWithoutStackTrace
558 "Bits.complement: Natural complement undefined"
559 shift x i
560 | i >= 0 = shiftLNatural x i
561 | otherwise = shiftRNatural x (negate i)
562 testBit x i = testBitNatural x i
563 zeroBits = wordToNaturalBase 0##
564 clearBit x i = x `xor` (bit i .&. x)
565
566 bit (I# i#) = bitNatural i#
567 popCount x = popCountNatural x
568
569 rotate x i = shift x i -- since an Natural never wraps around
570
571 bitSizeMaybe _ = Nothing
572 bitSize _ = errorWithoutStackTrace "Data.Bits.bitSize(Natural)"
573 isSigned _ = False
574
575 -----------------------------------------------------------------------------
576
577 -- | Attempt to convert an 'Integral' type @a@ to an 'Integral' type @b@ using
578 -- the size of the types as measured by 'Bits' methods.
579 --
580 -- A simpler version of this function is:
581 --
582 -- > toIntegral :: (Integral a, Integral b) => a -> Maybe b
583 -- > toIntegral x
584 -- > | toInteger x == y = Just (fromInteger y)
585 -- > | otherwise = Nothing
586 -- > where
587 -- > y = toInteger x
588 --
589 -- This version requires going through 'Integer', which can be inefficient.
590 -- However, @toIntegralSized@ is optimized to allow GHC to statically determine
591 -- the relative type sizes (as measured by 'bitSizeMaybe' and 'isSigned') and
592 -- avoid going through 'Integer' for many types. (The implementation uses
593 -- 'fromIntegral', which is itself optimized with rules for @base@ types but may
594 -- go through 'Integer' for some type pairs.)
595 --
596 -- @since 4.8.0.0
597
598 toIntegralSized :: (Integral a, Integral b, Bits a, Bits b) => a -> Maybe b
599 toIntegralSized x -- See Note [toIntegralSized optimization]
600 | maybe True (<= x) yMinBound
601 , maybe True (x <=) yMaxBound = Just y
602 | otherwise = Nothing
603 where
604 y = fromIntegral x
605
606 xWidth = bitSizeMaybe x
607 yWidth = bitSizeMaybe y
608
609 yMinBound
610 | isBitSubType x y = Nothing
611 | isSigned x, not (isSigned y) = Just 0
612 | isSigned x, isSigned y
613 , Just yW <- yWidth = Just (negate $ bit (yW-1)) -- Assumes sub-type
614 | otherwise = Nothing
615
616 yMaxBound
617 | isBitSubType x y = Nothing
618 | isSigned x, not (isSigned y)
619 , Just xW <- xWidth, Just yW <- yWidth
620 , xW <= yW+1 = Nothing -- Max bound beyond a's domain
621 | Just yW <- yWidth = if isSigned y
622 then Just (bit (yW-1)-1)
623 else Just (bit yW-1)
624 | otherwise = Nothing
625 {-# INLINABLE toIntegralSized #-}
626
627 -- | 'True' if the size of @a@ is @<=@ the size of @b@, where size is measured
628 -- by 'bitSizeMaybe' and 'isSigned'.
629 isBitSubType :: (Bits a, Bits b) => a -> b -> Bool
630 isBitSubType x y
631 -- Reflexive
632 | xWidth == yWidth, xSigned == ySigned = True
633
634 -- Every integer is a subset of 'Integer'
635 | ySigned, Nothing == yWidth = True
636 | not xSigned, not ySigned, Nothing == yWidth = True
637
638 -- Sub-type relations between fixed-with types
639 | xSigned == ySigned, Just xW <- xWidth, Just yW <- yWidth = xW <= yW
640 | not xSigned, ySigned, Just xW <- xWidth, Just yW <- yWidth = xW < yW
641
642 | otherwise = False
643 where
644 xWidth = bitSizeMaybe x
645 xSigned = isSigned x
646
647 yWidth = bitSizeMaybe y
648 ySigned = isSigned y
649 {-# INLINE isBitSubType #-}
650
651 {- Note [Constant folding for rotate]
652 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
653 The INLINE on the Int instance of rotate enables it to be constant
654 folded. For example:
655 sumU . mapU (`rotate` 3) . replicateU 10000000 $ (7 :: Int)
656 goes to:
657 Main.$wfold =
658 \ (ww_sO7 :: Int#) (ww1_sOb :: Int#) ->
659 case ww1_sOb of wild_XM {
660 __DEFAULT -> Main.$wfold (+# ww_sO7 56) (+# wild_XM 1);
661 10000000 -> ww_sO7
662 whereas before it was left as a call to $wrotate.
663
664 All other Bits instances seem to inline well enough on their
665 own to enable constant folding; for example 'shift':
666 sumU . mapU (`shift` 3) . replicateU 10000000 $ (7 :: Int)
667 goes to:
668 Main.$wfold =
669 \ (ww_sOb :: Int#) (ww1_sOf :: Int#) ->
670 case ww1_sOf of wild_XM {
671 __DEFAULT -> Main.$wfold (+# ww_sOb 56) (+# wild_XM 1);
672 10000000 -> ww_sOb
673 }
674 -}
675
676 -- Note [toIntegralSized optimization]
677 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
678 -- The code in 'toIntegralSized' relies on GHC optimizing away statically
679 -- decidable branches.
680 --
681 -- If both integral types are statically known, GHC will be able optimize the
682 -- code significantly (for @-O1@ and better).
683 --
684 -- For instance (as of GHC 7.8.1) the following definitions:
685 --
686 -- > w16_to_i32 = toIntegralSized :: Word16 -> Maybe Int32
687 -- >
688 -- > i16_to_w16 = toIntegralSized :: Int16 -> Maybe Word16
689 --
690 -- are translated into the following (simplified) /GHC Core/ language:
691 --
692 -- > w16_to_i32 = \x -> Just (case x of _ { W16# x# -> I32# (word2Int# x#) })
693 -- >
694 -- > i16_to_w16 = \x -> case eta of _
695 -- > { I16# b1 -> case tagToEnum# (<=# 0 b1) of _
696 -- > { False -> Nothing
697 -- > ; True -> Just (W16# (narrow16Word# (int2Word# b1)))
698 -- > }
699 -- > }