    -- |
    -- Module      : Unicode.Internal.Division
    -- Copyright   : (c) 2020 Andrew Lelechenko
    --
    -- License     : BSD-3-Clause
    -- Maintainer  : streamly@composewell.com
    -- Stability   : experimental
    -- Portability : GHC
    --
    -- Fast division by known constants.
    --
    -- Division by a constant can be replaced by a double-word multiplication.
    -- Roughly speaking, instead of dividing by x, multiply by 2^64/x,
    -- obtaining 128-bit-long product, and take upper 64 bits. The peculiar
    -- details can be found in Hacker's Delight, Ch. 10.
    --
    -- Even GHC 8.10 does not provide a primitive for a signed double-word
    -- multiplication, but since our applications does not involve negative
    -- integers, we convert 'Int' to 'Word' and use 'GHC.Exts.timesWord#'.
    --
    -- Textbook unsigned division by 21 or 28 becomes involved, when an argument
    -- is allowed to take the full range of 'Word' up to 2^64. Luckily, in our
    -- case the argument was casted from 'Int', so we can guarantee that it is
    -- below 2^63.

    module Unicode.Internal.Division
        ( quotRem21
        , quotRem28
        ) where

    import Data.Bits (Bits(..), FiniteBits(..))
    import GHC.Exts (Word(..), timesWord2#)

    highMul :: Word -> Word -> Word
    highMul :: Word -> Word -> Word
    highMul (W# Word#
    x#) (W# Word#
    y#) = Word# -> Word
    W# Word#
    high#
        where
            !(# Word#
    high#, Word#
    _ #) = Word# -> Word# -> (# Word#, Word# #)
    timesWord2# Word#
    x# Word#
    y#

    -- | Input must be non-negative.
    --
    -- Instead of division by 21, we compute
    -- floor(floor((2^68+17)/21 * n) / 2^68) = floor((2^68+17)/21 * n/2^68) =
    -- floor(n/21 + (n/2^63 * 17/32)/21) = floor(n/21),
    -- because n/2^63 * 17/32 < 1.
    {-# INLINE quotRem21 #-}
    quotRem21 :: Int -> (Int, Int)
    quotRem21 :: Int -> (Int, Int)
    quotRem21 Int
    n
        | Word -> Int
    forall b. FiniteBits b => b -> Int
    finiteBitSize (Word
    0 :: Word) Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    /= Int
    64
        = Int
    n Int -> Int -> (Int, Int)
    forall a. Integral a => a -> a -> (a, a)
    `quotRem` Int
    21
        | Bool
    otherwise
        = (Word -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Word
    q, Word -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Word
    w Word -> Word -> Word
    forall a. Num a => a -> a -> a
    - Word
    21 Word -> Word -> Word
    forall a. Num a => a -> a -> a
    * Word
    q))
        where
            w :: Word
    w = Int -> Word
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Int
    n
            high :: Word
    high = Word -> Word -> Word
    highMul Word
    w Word
    14054662151397753613 -- (2^68+17)/21
            q :: Word
    q = Word
    high Word -> Int -> Word
    forall a. Bits a => a -> Int -> a
    `shiftR` Int
    4

    -- | Input must be non-negative.
    --
    -- Instead of division by 28, we compute
    -- floor(floor((2^65+3)/7 * n) / 2^67) = floor((2^65+3)/7 * n/2^67) =
    -- floor(n/28 + (n/2^63 * 3/4)/28) = floor(n/28),
    -- because n/2^63 * 3/4 < 1.
    {-# INLINE quotRem28 #-}
    quotRem28 :: Int -> (Int, Int)
    quotRem28 :: Int -> (Int, Int)
    quotRem28 Int
    n
        | Word -> Int
    forall b. FiniteBits b => b -> Int
    finiteBitSize (Word
    0 :: Word) Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    /= Int
    64
        = Int
    n Int -> Int -> (Int, Int)
    forall a. Integral a => a -> a -> (a, a)
    `quotRem` Int
    28
        | Bool
    otherwise
        = (Word -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Word
    q, Word -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Word
    r)
        where
            w :: Word
    w = Int -> Word
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Int
    n
            high :: Word
    high = Word -> Word -> Word
    highMul Word
    w Word
    5270498306774157605 -- (2^65+3)/7
            q :: Word
    q = Word
    high Word -> Int -> Word
    forall a. Bits a => a -> Int -> a
    `shiftR` Int
    3
            prod :: Word
    prod = (Word
    q Word -> Int -> Word
    forall a. Bits a => a -> Int -> a
    `shiftL` Int
    3 Word -> Word -> Word
    forall a. Num a => a -> a -> a
    - Word
    q) Word -> Int -> Word
    forall a. Bits a => a -> Int -> a
    `shiftL` Int
    2
            r :: Word
    r = Word
    w Word -> Word -> Word
    forall a. Num a => a -> a -> a
    - Word
    prod