1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
{-# LANGUAGE MagicHash #-}
import Control.Monad
import Data.Bits
import GHC.Exts
import GHC.Word
import Numeric (showHex)
-- Reference Implementation
-- count trailing zeros
ctzRI :: FiniteBits a => a -> Word
ctzRI x = fromIntegral $ go 0
where
go i | i >= w = i
| testBit x i = i
| otherwise = go (i+1)
w = finiteBitSize x
-- count leading zeros
clzRI :: FiniteBits a => a -> Word
clzRI x = fromIntegral $ (w-1) - go (w-1)
where
go i | i < 0 = i -- no bit set
| testBit x i = i
| otherwise = go (i-1)
w = finiteBitSize x
clzRI32, ctzRI32 :: Word -> Word
clzRI32 x = clzRI (fromIntegral x :: Word32)
ctzRI32 x = ctzRI (fromIntegral x :: Word32)
clzRI16, ctzRI16 :: Word -> Word
clzRI16 x = clzRI (fromIntegral x :: Word16)
ctzRI16 x = ctzRI (fromIntegral x :: Word16)
clzRI8, ctzRI8 :: Word -> Word
clzRI8 x = clzRI (fromIntegral x :: Word8)
ctzRI8 x = ctzRI (fromIntegral x :: Word8)
-- Implementation Under Test
ctzIUT, clzIUT :: Word -> Word
ctzIUT (W# x#) = W# (ctz# x#)
clzIUT (W# x#) = W# (clz# x#)
ctzIUT8, clzIUT8 :: Word -> Word
ctzIUT8 (W# x#) = W# (ctz8# x#)
clzIUT8 (W# x#) = W# (clz8# x#)
ctzIUT16, clzIUT16 :: Word -> Word
ctzIUT16 (W# x#) = W# (ctz16# x#)
clzIUT16 (W# x#) = W# (clz16# x#)
ctzIUT32, clzIUT32 :: Word -> Word
ctzIUT32 (W# x#) = W# (ctz32# x#)
clzIUT32 (W# x#) = W# (clz32# x#)
ctzIUT64, clzIUT64 :: Word64 -> Word
ctzIUT64 (W64# x#) = W# (ctz64# x#)
clzIUT64 (W64# x#) = W# (clz64# x#)
main :: IO ()
main = do
forM_ testpats $ \w64 -> do
let w = fromIntegral w64 :: Word
check "clz" clzRI clzIUT w
check "clz8" clzRI8 clzIUT8 w
check "clz16" clzRI16 clzIUT16 w
check "clz32" clzRI32 clzIUT32 w
check "clz64" clzRI clzIUT64 w64
check "ctz" ctzRI ctzIUT w
check "ctz8" ctzRI8 ctzIUT8 w
check "ctz16" ctzRI16 ctzIUT16 w
check "ctz32" ctzRI32 ctzIUT32 w
check "ctz64" ctzRI ctzIUT64 w64
putStrLn $ concat ["tested ", show (length testpats), " patterns"]
where
-- try to construct some interesting patterns
testpats :: [Word64]
testpats = [ bit i - 1 | i <- [0..63] ] ++
[ complement (bit i - 1) | i <- [0..63] ] ++
[ bit i .|. bit j | i <- [0..63], j <- [0..i] ]
check s fri fiut v = unless (vri == viut) $ do
putStrLn $ concat [ "FAILED ", s, " for x=0x", showHex v ""
, " (RI=", show vri, " IUT=", show viut, ")"
]
where
vri = fri v
viut = fiut v
|
