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


-- | Generate routines for integer division, employing arithmetic and
--   bitwise operations only, which are <b>2.5x-3.5x faster</b> than
--   <a>quot</a>. 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 <b>2.5x-3.5x faster</b> than
--   <a>quot</a>. Divisors must be known in compile-time and be positive.
module Numeric.QuoteQuot

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

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

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

-- | <a>astQuot</a> <tt>d</tt> constructs an <a>AST</a> representing a
--   function, equivalent to <a>quot</a> <tt>a</tt> for positive
--   <tt>a</tt>, but avoiding division instructions.
--   
--   <pre>
--   &gt;&gt;&gt; astQuot (10 :: Data.Word.Word8)
--   Shr (MulHi Arg 205) 3
--   </pre>
--   
--   And indeed to divide <a>Word8</a> 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.
--   
--   <a>astQuot</a> 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 <a>AST</a>. It is not meant to be
--   used in production and is provided primarily for testing purposes.
--   
--   <pre>
--   &gt;&gt;&gt; interpretAST (astQuot (10 :: Data.Word.Word8)) 123
--   12
--   </pre>
interpretAST :: (Integral a, FiniteBits a) => AST a -> a -> a

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

-- | Optimize <a>AST</a>, assuming that <a>Arg</a> 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)
