{-# OPTIONS_HADDOCK not-home #-}

-- | Some arithmetic implemented using bit operations
--
-- Valid for non-negative arguments.
module Database.LSMTree.Internal.BitMath (
    -- * Two
    div2,
    mod2,
    mul2,
    ceilDiv2,
    -- * Four
    div4,
    mod4,
    mul4,
    -- * Eight
    div8,
    mod8,
    mul8,
    ceilDiv8,
    -- * Sixteen
    div16,
    mod16,
    mul16,
    -- * 32
    div32,
    mod32,
    -- * 64
    div64,
    mod64,
    mul64,
    ceilDiv64,
    -- * 4096, page size
    divPageSize,
    modPageSize,
    mulPageSize,
    ceilDivPageSize,
    roundUpToPageSize,
) where

import           Data.Bits

-------------------------------------------------------------------------------
-- 2
-------------------------------------------------------------------------------

div2 :: Bits a => a -> a
div2 :: forall a. Bits a => a -> a
div2 a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftR a
x Int
1
{-# INLINE div2 #-}

mod2 :: (Bits a, Num a) => a -> a
mod2 :: forall a. (Bits a, Num a) => a -> a
mod2 a
x = a
x a -> a -> a
forall a. Bits a => a -> a -> a
.&. a
1
{-# INLINE mod2 #-}

mul2 :: Bits a => a -> a
mul2 :: forall a. Bits a => a -> a
mul2 a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftL a
x Int
1
{-# INLINE mul2 #-}

ceilDiv2 :: (Bits a, Num a) => a -> a
ceilDiv2 :: forall a. (Bits a, Num a) => a -> a
ceilDiv2 a
i = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftR (a
i a -> a -> a
forall a. Num a => a -> a -> a
+ a
1) Int
1
{-# INLINE ceilDiv2 #-}

-------------------------------------------------------------------------------
-- 4
-------------------------------------------------------------------------------

div4 :: Bits a => a -> a
div4 :: forall a. Bits a => a -> a
div4 a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftR a
x Int
2
{-# INLINE div4 #-}

mod4 :: (Bits a, Num a) => a -> a
mod4 :: forall a. (Bits a, Num a) => a -> a
mod4 a
x = a
x a -> a -> a
forall a. Bits a => a -> a -> a
.&. a
3
{-# INLINE mod4 #-}

mul4 :: Bits a => a -> a
mul4 :: forall a. Bits a => a -> a
mul4 a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftL a
x Int
2
{-# INLINE mul4 #-}

-------------------------------------------------------------------------------
-- 8
-------------------------------------------------------------------------------

div8 :: Bits a => a -> a
div8 :: forall a. Bits a => a -> a
div8 a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftR a
x Int
3
{-# INLINE div8 #-}

mod8 :: (Bits a, Num a) => a -> a
mod8 :: forall a. (Bits a, Num a) => a -> a
mod8 a
x = a
x a -> a -> a
forall a. Bits a => a -> a -> a
.&. a
7
{-# INLINE mod8 #-}

mul8 :: Bits a => a -> a
mul8 :: forall a. Bits a => a -> a
mul8 a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftL a
x Int
3
{-# INLINE mul8 #-}

ceilDiv8 :: (Bits a, Num a) => a -> a
ceilDiv8 :: forall a. (Bits a, Num a) => a -> a
ceilDiv8 a
i = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftR (a
i a -> a -> a
forall a. Num a => a -> a -> a
+ a
7) Int
3
{-# INLINE ceilDiv8 #-}

-------------------------------------------------------------------------------
-- 16
-------------------------------------------------------------------------------

div16 :: Bits a => a -> a
div16 :: forall a. Bits a => a -> a
div16 a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftR a
x Int
4
{-# INLINE div16 #-}

mod16 :: (Bits a, Num a) => a -> a
mod16 :: forall a. (Bits a, Num a) => a -> a
mod16 a
x = a
x a -> a -> a
forall a. Bits a => a -> a -> a
.&. a
15
{-# INLINE mod16 #-}

mul16 :: Bits a => a -> a
mul16 :: forall a. Bits a => a -> a
mul16 a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftL a
x Int
4
{-# INLINE mul16 #-}

-------------------------------------------------------------------------------
-- 32
-------------------------------------------------------------------------------

div32 :: Bits a => a -> a
div32 :: forall a. Bits a => a -> a
div32 a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftR a
x Int
5
{-# INLINE div32 #-}

mod32 :: (Bits a, Num a) => a -> a
mod32 :: forall a. (Bits a, Num a) => a -> a
mod32 a
x = a
x a -> a -> a
forall a. Bits a => a -> a -> a
.&. a
31
{-# INLINE mod32 #-}

-------------------------------------------------------------------------------
-- 64
-------------------------------------------------------------------------------

-- |
--
-- >>> map div64 [0 :: Word, 1, 63, 64, 65]
-- [0,0,0,1,1]
--
div64 :: Bits a => a -> a
div64 :: forall a. Bits a => a -> a
div64 a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftR a
x Int
6
{-# INLINE div64 #-}

-- |
--
-- >>> map mod64 [0 :: Word, 1, 63, 64, 65]
-- [0,1,63,0,1]
--
mod64 :: (Bits a, Num a) => a -> a
mod64 :: forall a. (Bits a, Num a) => a -> a
mod64 a
x = a
x a -> a -> a
forall a. Bits a => a -> a -> a
.&. a
63
{-# INLINE mod64 #-}

mul64 :: Bits a => a -> a
mul64 :: forall a. Bits a => a -> a
mul64 a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftL a
x Int
6
{-# INLINE mul64 #-}

-- | rounding up division
--
-- >>> map ceilDiv64 [0 :: Word, 1, 63, 64, 65]
-- [0,1,1,1,2]
--
ceilDiv64 :: (Bits a, Num a) => a -> a
ceilDiv64 :: forall a. (Bits a, Num a) => a -> a
ceilDiv64 a
i = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftR (a
i a -> a -> a
forall a. Num a => a -> a -> a
+ a
63) Int
6
{-# INLINE ceilDiv64 #-}

-------------------------------------------------------------------------------
-- 4096
-------------------------------------------------------------------------------

-- | Assumes @pageSize = 4096@.
divPageSize :: Bits a => a -> a
divPageSize :: forall a. Bits a => a -> a
divPageSize a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftR a
x Int
12
{-# INLINE divPageSize #-}

-- | Assumes @pageSize = 4096@.
modPageSize :: (Bits a, Num a) => a -> a
modPageSize :: forall a. (Bits a, Num a) => a -> a
modPageSize a
x = a
x a -> a -> a
forall a. Bits a => a -> a -> a
.&. a
4095
{-# INLINE modPageSize #-}

-- | Assumes @pageSize = 4096@.
mulPageSize :: Bits a => a -> a
mulPageSize :: forall a. Bits a => a -> a
mulPageSize a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftL a
x Int
12
{-# INLINE mulPageSize #-}

-- | Assumes @pageSize = 4096@.
ceilDivPageSize :: (Bits a, Num a) => a -> a
ceilDivPageSize :: forall a. (Bits a, Num a) => a -> a
ceilDivPageSize a
x = a -> Int -> a
forall a. Bits a => a -> Int -> a
unsafeShiftR (a
x a -> a -> a
forall a. Num a => a -> a -> a
+ a
4095) Int
12
{-# INLINE ceilDivPageSize #-}

-- | Assumes @pageSize = 4096@.
roundUpToPageSize :: (Bits a, Num a) => a -> a
roundUpToPageSize :: forall a. (Bits a, Num a) => a -> a
roundUpToPageSize a
x = (a
x a -> a -> a
forall a. Num a => a -> a -> a
+ a
4095) a -> a -> a
forall a. Bits a => a -> a -> a
.&. a -> a
forall a. Bits a => a -> a
complement a
4095
{-# INLINE roundUpToPageSize #-}