module HaskellWorks.Data.Bits.Log2
  ( Log2(..)
  ) where

import Data.Word
import HaskellWorks.Data.AtIndex
import HaskellWorks.Data.Bits.BitWise

import qualified Data.Vector.Storable as DVS

class Log2 a where
  -- | Log base of the given value rounded down to the nearest integer
  log2 :: a -> Int

log2_64_tab :: DVS.Vector Int
log2_64_tab :: Vector Int
log2_64_tab = [Int] -> Vector Int
forall a. Storable a => [a] -> Vector a
DVS.fromList [
    Int
63,  Int
0, Int
58,  Int
1, Int
59, Int
47, Int
53,  Int
2,
    Int
60, Int
39, Int
48, Int
27, Int
54, Int
33, Int
42,  Int
3,
    Int
61, Int
51, Int
37, Int
40, Int
49, Int
18, Int
28, Int
20,
    Int
55, Int
30, Int
34, Int
11, Int
43, Int
14, Int
22,  Int
4,
    Int
62, Int
57, Int
46, Int
52, Int
38, Int
26, Int
32, Int
41,
    Int
50, Int
36, Int
17, Int
19, Int
29, Int
10, Int
13, Int
21,
    Int
56, Int
45, Int
25, Int
31, Int
35, Int
16,  Int
9, Int
12,
    Int
44, Int
24, Int
15,  Int
8, Int
23,  Int
7,  Int
6,  Int
5]

log2_32_tab :: DVS.Vector Int
log2_32_tab :: Vector Int
log2_32_tab = [Int] -> Vector Int
forall a. Storable a => [a] -> Vector a
DVS.fromList [
     Int
0,  Int
9,  Int
1, Int
10, Int
13, Int
21,  Int
2, Int
29,
    Int
11, Int
14, Int
16, Int
18, Int
22, Int
25,  Int
3, Int
30,
     Int
8, Int
12, Int
20, Int
28, Int
15, Int
17, Int
24,  Int
7,
    Int
19, Int
27, Int
23,  Int
6, Int
26,  Int
5,  Int
4, Int
31]

instance Log2 Word64 where
  log2 :: Word64 -> Int
log2 Word64
v0 =
      let v1 :: Word64
v1 = Word64
v0 Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.|. (Word64
v0 Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>.  Word64
1) in
      let v2 :: Word64
v2 = Word64
v1 Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.|. (Word64
v1 Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>.  Word64
2) in
      let v3 :: Word64
v3 = Word64
v2 Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.|. (Word64
v2 Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>.  Word64
4) in
      let v4 :: Word64
v4 = Word64
v3 Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.|. (Word64
v3 Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>.  Word64
8) in
      let v5 :: Word64
v5 = Word64
v4 Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.|. (Word64
v4 Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
16) in
      let v6 :: Word64
v6 = Word64
v5 Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.|. (Word64
v5 Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
32) in
      Vector Int
log2_64_tab Vector Int -> Position -> Elem (Vector Int)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word64 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral (((Word64
v6 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
- (Word64
v6 Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
1)) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
0x07EDD5E59A4E28C2) Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
58)

instance Log2 Word32 where
  log2 :: Word32 -> Int
log2 Word32
v0 =
      let v1 :: Word32
v1 = Word32
v0 Word32 -> Word32 -> Word32
forall a. BitWise a => a -> a -> a
.|. (Word32
v0 Word32 -> Word64 -> Word32
forall a. Shift a => a -> Word64 -> a
.>.  Word64
1) in
      let v2 :: Word32
v2 = Word32
v1 Word32 -> Word32 -> Word32
forall a. BitWise a => a -> a -> a
.|. (Word32
v1 Word32 -> Word64 -> Word32
forall a. Shift a => a -> Word64 -> a
.>.  Word64
2) in
      let v3 :: Word32
v3 = Word32
v2 Word32 -> Word32 -> Word32
forall a. BitWise a => a -> a -> a
.|. (Word32
v2 Word32 -> Word64 -> Word32
forall a. Shift a => a -> Word64 -> a
.>.  Word64
4) in
      let v4 :: Word32
v4 = Word32
v3 Word32 -> Word32 -> Word32
forall a. BitWise a => a -> a -> a
.|. (Word32
v3 Word32 -> Word64 -> Word32
forall a. Shift a => a -> Word64 -> a
.>.  Word64
8) in
      let v5 :: Word32
v5 = Word32
v4 Word32 -> Word32 -> Word32
forall a. BitWise a => a -> a -> a
.|. (Word32
v4 Word32 -> Word64 -> Word32
forall a. Shift a => a -> Word64 -> a
.>. Word64
16) in
      Vector Int
log2_32_tab Vector Int -> Position -> Elem (Vector Int)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word32 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral ((Word32
v5 Word32 -> Word32 -> Word32
forall a. Num a => a -> a -> a
* Word32
0x07C4ACDD) Word32 -> Word64 -> Word32
forall a. Shift a => a -> Word64 -> a
.>. Word64
27)