```-- |
-- Module      : Unicode.Internal.Division
-- Copyright   : (c) 2020 Andrew Lelechenko
--
-- 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
```