    module Data.Aeson.Internal.Integer (
        bsToInteger,
        bsToIntegerSimple
    ) where

    import qualified Data.ByteString as B

    import Data.Aeson.Internal.Word8

    ------------------ Copy-pasted and adapted from base ------------------------

    bsToInteger :: B.ByteString -> Integer
    bsToInteger :: ByteString -> Integer
    bsToInteger ByteString
    bs
        | Int
    l Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    40    = Integer -> Int -> [Integer] -> Integer
    valInteger Integer
    10 Int
    l [ Word8 -> Integer
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Word8
    w Word8 -> Word8 -> Word8
    forall a. Num a => a -> a -> a
    - Word8
    W8_0) | Word8
    w <- ByteString -> [Word8]
    B.unpack ByteString
    bs ]
        | Bool
    otherwise = ByteString -> Integer
    bsToIntegerSimple ByteString
    bs
      where
        l :: Int
    l = ByteString -> Int
    B.length ByteString
    bs

    bsToIntegerSimple :: B.ByteString -> Integer
    bsToIntegerSimple :: ByteString -> Integer
    bsToIntegerSimple = (Integer -> Word8 -> Integer) -> Integer -> ByteString -> Integer
    forall a. (a -> Word8 -> a) -> a -> ByteString -> a
    B.foldl' Integer -> Word8 -> Integer
    forall {a}. Num a => a -> Word8 -> a
    step Integer
    0 where
      step :: a -> Word8 -> a
    step a
    a Word8
    b = a
    a a -> a -> a
    forall a. Num a => a -> a -> a
    * a
    10 a -> a -> a
    forall a. Num a => a -> a -> a
    + Word8 -> a
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Word8
    b Word8 -> Word8 -> Word8
    forall a. Num a => a -> a -> a
    - Word8
    W8_0)

    -- A sub-quadratic algorithm for Integer. Pairs of adjacent radix b
    -- digits are combined into a single radix b^2 digit. This process is
    -- repeated until we are left with a single digit. This algorithm
    -- performs well only on large inputs, so we use the simple algorithm
    -- for smaller inputs.
    valInteger :: Integer -> Int -> [Integer] -> Integer
    valInteger :: Integer -> Int -> [Integer] -> Integer
    valInteger = Integer -> Int -> [Integer] -> Integer
    go
      where
        go :: Integer -> Int -> [Integer] -> Integer
        go :: Integer -> Int -> [Integer] -> Integer
    go Integer
    _ Int
    _ []  = Integer
    0
        go Integer
    _ Int
    _ [Integer
    d] = Integer
    d
        go Integer
    b Int
    l [Integer]
    ds
            | Int
    l Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    40 = Integer
    b' Integer -> Integer -> Integer
    forall a b. a -> b -> b
    `seq` Integer -> Int -> [Integer] -> Integer
    go Integer
    b' Int
    l' (Integer -> [Integer] -> [Integer]
    forall {t}. Num t => t -> [t] -> [t]
    combine Integer
    b [Integer]
    ds')
            | Bool
    otherwise = Integer -> [Integer] -> Integer
    valSimple Integer
    b [Integer]
    ds
          where
            -- ensure that we have an even number of digits
            -- before we call combine:
            ds' :: [Integer]
    ds' = if Int -> Bool
    forall a. Integral a => a -> Bool
    even Int
    l then [Integer]
    ds else Integer
    0 Integer -> [Integer] -> [Integer]
    forall a. a -> [a] -> [a]
    : [Integer]
    ds
            b' :: Integer
    b' = Integer
    b Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer
    b
            l' :: Int
    l' = (Int
    l Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1) Int -> Int -> Int
    forall a. Integral a => a -> a -> a
    `quot` Int
    2

        combine :: t -> [t] -> [t]
    combine t
    b (t
    d1 : t
    d2 : [t]
    ds) = t
    d t -> [t] -> [t]
    forall a b. a -> b -> b
    `seq` (t
    d t -> [t] -> [t]
    forall a. a -> [a] -> [a]
    : t -> [t] -> [t]
    combine t
    b [t]
    ds)
          where
            d :: t
    d = t
    d1 t -> t -> t
    forall a. Num a => a -> a -> a
    * t
    b t -> t -> t
    forall a. Num a => a -> a -> a
    + t
    d2
        combine t
    _ []  = []
        combine t
    _ [t
    _] = [Char] -> [t]
    forall a. [Char] -> a
    errorWithoutStackTrace [Char]
    "this should not happen"

    -- The following algorithm is only linear for types whose Num operations
    -- are in constant time.
    valSimple :: Integer -> [Integer] -> Integer
    valSimple :: Integer -> [Integer] -> Integer
    valSimple Integer
    base = Integer -> [Integer] -> Integer
    forall {a}. Integral a => Integer -> [a] -> Integer
    go Integer
    0
      where
        go :: Integer -> [a] -> Integer
    go Integer
    r [] = Integer
    r
        go Integer
    r (a
    d : [a]
    ds) = Integer
    r' Integer -> Integer -> Integer
    forall a b. a -> b -> b
    `seq` Integer -> [a] -> Integer
    go Integer
    r' [a]
    ds
          where
            r' :: Integer
    r' = Integer
    r Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer
    base Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + a -> Integer
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral a
    d