{-# LANGUAGE CPP, BangPatterns, MagicHash #-}
module Data.RangeMin.Common.Math (bit', bitW, div', divRoundMod', divMod',  ceilLog, intLog, shiftR') where

import Data.Bits (Bits(..))
import Data.Word

#if __GLASGOW_HASKELL__
-- Unchecked versions of normal arithmetic functions, for when you just need
-- the performance that badly.

import GHC.Exts
import GHC.Base

div' :: Int -> Int -> Int
bit' :: Int -> Int
bitW :: Int -> Word
div' = quotInt
bit' (I# i#) = I# (uncheckedIShiftL# 1# i#)
bitW (I# i#) = W# (uncheckedShiftL# 1## i#)
shiftR' :: Int -> Int -> Int
shiftR' (I# i#) (I# j#) = I# (uncheckedIShiftRL# i# j#)
#else
div' :: Int -> Int -> Int
bit' :: Int -> Int
bitW :: Int -> Word
shiftR' :: Int -> Int -> Int
div' = quot
bit' = bit
bitW = bit
shiftR' = shiftR
#endif

divRoundMod' :: Int -> Int -> (Int, Int, Int)
a `divRoundMod'` b = (q, r, a - r) where
	!q = a `div'` b
	!r = q * b

divMod' :: Int -> Int -> (Int, Int)
a `divMod'` b = let !q = a `div'` b in (q, a - b * q) 

ceilLog :: Int -> Int
ceilLog n = intLog (2 * n - 1)

intLog :: Int -> Int
intLog = fromIntegral . wordLog . fromIntegral

#include "MachDeps.h"

wordLog :: Word -> Word
#if WORD_SIZE_IN_BITS == 64
wordLog v = intLog5 v 0 where
	intLog5 = intLogI 5 intLog4
#elif WORD_SIZE_IN_BITS == 32
wordLog v = intLog4 v 0 where
#else
wordLog !v = fromIntegral (binSearch 0 (bitSize (0 :: Word))) where
	binSearch !i !d = case d of
	  1	-> i
	  2	-> if bitW (i+1) <= v then i+1 else i
	  _	-> let
	    !d' = d `div'` 2
	    !m = i + d'
	    !bm = bitW m
	    in if bm <= v then binSearch m (d - d') else binSearch i d'
#endif
	intLog4 = intLogI 4 $ intLogI 3 $ intLogI 2 $ intLogI 1 $ intLogI 0 $ \ _ r -> r
	{-# INLINE [0] intLogI #-}
	intLogI !i intLogI' = let
		bi = bit i
		!maski = (bit bi - 1) `shiftL` bi
		in \ !v !r -> case v .&. maski of
			0	-> intLogI' v r
			_	-> intLogI' (v `shiftR` bi) (r .|. fromIntegral bi)