-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/

-- | Divide without division
--   
--   Generate routines for integer division, employing arithmetic and
--   bitwise operations only, which are 2.5x-3.5x faster than
--   quot. Divisors must be known in compile-time and be positive.
@package quote-quot
@version 0.2.1.0

-- | Generate routines for integer division, employing arithmetic and
--   bitwise operations only, which are 2.5x-3.5x faster than
--   quot. Divisors must be known in compile-time and be positive.
module Numeric.QuoteQuot

-- | Quote integer division (quot) by a compile-time known divisor,
--   which generates source code, employing arithmetic and bitwise
--   operations only. This is usually 2.5x-3.5x faster than using
--   normal quot.
--   
--   
--   {-# LANGUAGE TemplateHaskell #-}
--   {-# OPTIONS_GHC -ddump-splices -ddump-simpl -dsuppress-all #-}
--   module Example where
--   import Numeric.QuoteQuot
--   
--   -- Equivalent to (`quot` 10).
--   quot10 :: Word -> Word
--   quot10 = $$(quoteQuot 10)
--   
--   
--   
--   >>> quot10 123
--   12
--   
--   
--   Here -ddump-splices demonstrates the chosen implementation
--   for division by 10:
--   
--   
--   Splicing expression quoteQuot 10 ======>
--   ((`shiftR` 3) . ((\ (W# w_a9N4) ->
--     let !(# hi_a9N5, _ #) = (timesWord2# w_a9N4) 14757395258967641293##
--     in W# hi_a9N5) . id))
--   
--   
--   And -ddump-simpl demonstrates generated Core:
--   
--   
--   quot10 = \ x_a5t2 ->
--     case x_a5t2 of { W# w_acHY ->
--     case timesWord2# w_acHY 14757395258967641293## of
--     { (# hi_acIg, ds_dcIs #) ->
--     W# (uncheckedShiftRL# hi_acIg 3#)
--     }
--     }
--   
--   
--   Benchmarks show that this implementation is 3.5x faster than
--   (`</tt><a>quot</a><tt>` 10).
quoteQuot :: forall a (m :: Type -> Type). (MulHi a, Lift a, Quote m) => a -> Code m (a -> a)

-- | Similar to quoteQuot, but for rem.
quoteRem :: forall a (m :: Type -> Type). (MulHi a, Lift a, Quote m) => a -> Code m (a -> a)

-- | Similar to quoteQuot, but for quotRem.
quoteQuotRem :: forall a (m :: Type -> Type). (MulHi a, Lift a, Quote m) => a -> Code m (a -> (a, a))

-- | astQuot d constructs an AST representing a
--   function, equivalent to quot a for positive
--   a, but avoiding division instructions.
--   
--   
--   >>> astQuot (10 :: Data.Word.Word8)
--   Shr (MulHi Arg 205) 3
--   
--   
--   And indeed to divide Word8 by 10 one can multiply it by 205,
--   take the high byte and shift it right by 3. Somewhat
--   counterintuitively, this sequence of operations is faster than a
--   single division on most modern achitectures.
--   
--   astQuot function is polymorphic and supports both signed and
--   unsigned operands of arbitrary finite bitness. Implementation is based
--   on Ch. 10 of Hacker's Delight by Henry S. Warren, 2012.
astQuot :: (Integral a, FiniteBits a) => a -> AST a

-- | An abstract syntax tree to represent a function of one argument.
data AST a

-- | Argument of the function
Arg :: AST a

-- | Multiply wide and return the high word of result
MulHi :: AST a -> a -> AST a

-- | Multiply
MulLo :: AST a -> a -> AST a

-- | Add
Add :: AST a -> AST a -> AST a

-- | Subtract
Sub :: AST a -> AST a -> AST a

-- | Shift left
Shl :: AST a -> Int -> AST a

-- | Shift right with sign extension
Shr :: AST a -> Int -> AST a

-- | 1 if greater than or equal, 0 otherwise
CmpGE :: AST a -> a -> AST a

-- | 1 if less than, 0 otherwise
CmpLT :: AST a -> a -> AST a

-- | Reference (but slow) interpreter of AST. It is not meant to be
--   used in production and is provided primarily for testing purposes.
--   
--   
--   >>> interpretAST (astQuot (10 :: Data.Word.Word8)) 123
--   12
--   
interpretAST :: (Integral a, FiniteBits a) => AST a -> a -> a

-- | Embed AST into Haskell expression.
quoteAST :: forall a (m :: Type -> Type). (MulHi a, Lift a, Quote m) => AST a -> Code m (a -> a)

-- | Optimize AST, assuming that Arg is non-negative.
assumeNonNegArg :: (Ord a, Num a) => AST a -> AST a

-- | Types allowing to multiply wide and return the high word of result.
class (Integral a, FiniteBits a) => MulHi a
mulHi :: MulHi a => a -> a -> a
instance Numeric.QuoteQuot.MulHi GHC.Types.Int
instance Numeric.QuoteQuot.MulHi GHC.Internal.Int.Int16
instance Numeric.QuoteQuot.MulHi GHC.Internal.Int.Int32
instance Numeric.QuoteQuot.MulHi GHC.Internal.Int.Int64
instance Numeric.QuoteQuot.MulHi GHC.Internal.Int.Int8
instance Numeric.QuoteQuot.MulHi GHC.Types.Word
instance Numeric.QuoteQuot.MulHi GHC.Internal.Word.Word16
instance Numeric.QuoteQuot.MulHi GHC.Internal.Word.Word32
instance Numeric.QuoteQuot.MulHi GHC.Internal.Word.Word64
instance Numeric.QuoteQuot.MulHi GHC.Internal.Word.Word8
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Numeric.QuoteQuot.AST a)
