-- 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 <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 :: (MulHi a, Lift a) => a -> Q (TExp (a -> a))

-- | Similar to <a>quoteQuot</a>, but for <a>rem</a>.
quoteRem :: (MulHi a, Lift a) => a -> Q (TExp (a -> a))

-- | Similar to <a>quoteQuot</a>, but for <a>quotRem</a>.
quoteQuotRem :: (MulHi a, Lift a) => a -> Q (TExp (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 :: (MulHi a, Lift a) => AST a -> Q (TExp (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 GHC.Show.Show a => GHC.Show.Show (Numeric.QuoteQuot.AST a)
instance Numeric.QuoteQuot.MulHi GHC.Word.Word8
instance Numeric.QuoteQuot.MulHi GHC.Word.Word16
instance Numeric.QuoteQuot.MulHi GHC.Word.Word32
instance Numeric.QuoteQuot.MulHi GHC.Word.Word64
instance Numeric.QuoteQuot.MulHi GHC.Types.Word
instance Numeric.QuoteQuot.MulHi GHC.Int.Int8
instance Numeric.QuoteQuot.MulHi GHC.Int.Int16
instance Numeric.QuoteQuot.MulHi GHC.Int.Int32
