    -- |
    -- Module      : Crypto.Math.F2m
    -- License     : BSD-style
    -- Maintainer  : Danny Navarro <j@dannynavarro.net>
    -- Stability   : experimental
    -- Portability : Good
    --
    -- This module provides basic arithmetic operations over F₂m. Performance is
    -- not optimal and it doesn't provide protection against timing
    -- attacks. The 'm' parameter is implicitly derived from the irreducible
    -- polynomial where applicable.

    module Crypto.Number.F2m
        ( BinaryPolynomial
        , addF2m
        , mulF2m
        , squareF2m'
        , squareF2m
        , modF2m
        , invF2m
        , divF2m
        ) where

    import Data.Bits (xor, shift, testBit, setBit)
    import Data.List
    import Crypto.Internal.Imports
    import Crypto.Number.Basic

    -- | Binary Polynomial represented by an integer
    type BinaryPolynomial = Integer

    -- | Addition over F₂m. This is just a synonym of 'xor'.
    addF2m :: Integer
           -> Integer
           -> Integer
    addF2m = xor
    {-# INLINE addF2m #-}

    -- | Reduction by modulo over F₂m.
    --
    -- This function is undefined for negative arguments, because their bit
    -- representation is platform-dependent. Zero modulus is also prohibited.
    modF2m :: BinaryPolynomial -- ^ Modulus
           -> Integer
           -> Integer
    modF2m fx i
        | fx < 0 || i < 0 = error "modF2m: negative number represent no binary polynomial"
        | fx == 0         = error "modF2m: cannot divide by zero polynomial"
        | fx == 1         = 0
        | otherwise       = go i
          where
            lfx = log2 fx
            go n | s == 0    = n `addF2m` fx
                 | s < 0     = n
                 | otherwise = go $ n `addF2m` shift fx s
                    where s = log2 n - lfx
    {-# INLINE modF2m #-}

    -- | Multiplication over F₂m.
    --
    -- This function is undefined for negative arguments, because their bit
    -- representation is platform-dependent. Zero modulus is also prohibited.
    mulF2m :: BinaryPolynomial -- ^ Modulus
           -> Integer
           -> Integer
           -> Integer
    mulF2m fx n1 n2
        |    fx < 0
          || n1 < 0
          || n2 < 0 = error "mulF2m: negative number represent no binary binary polynomial"
        | fx == 0   = error "modF2m: cannot multiply modulo zero polynomial"
        | otherwise = modF2m fx $ go (if n2 `mod` 2 == 1 then n1 else 0) (log2 n2)
          where
            go n s | s == 0  = n
                   | otherwise = if testBit n2 s
                                    then go (n `addF2m` shift n1 s) (s - 1)
                                    else go n (s - 1)
    {-# INLINABLE mulF2m #-}

    -- | Squaring over F₂m.
    --
    -- This function is undefined for negative arguments, because their bit
    -- representation is platform-dependent. Zero modulus is also prohibited.
    squareF2m :: BinaryPolynomial -- ^ Modulus
              -> Integer
              -> Integer
    squareF2m fx = modF2m fx . squareF2m'
    {-# INLINE squareF2m #-}

    -- | Squaring over F₂m without reduction by modulo.
    --
    -- The implementation utilizes the fact that for binary polynomial S(x) we have
    -- S(x)^2 = S(x^2). In other words, insert a zero bit between every bits of argument: 1101 -> 1010001.
    --
    -- This function is undefined for negative arguments, because their bit
    -- representation is platform-dependent.
    squareF2m' :: Integer
               -> Integer
    squareF2m' n
        | n < 0     = error "mulF2m: negative number represent no binary binary polynomial"
        | otherwise = foldl' (\acc s -> if testBit n s then setBit acc (2 * s) else acc) 0 [0 .. log2 n]
    {-# INLINE squareF2m' #-}

    -- | Extended GCD algorithm for polynomials. For @a@ and @b@ returns @(g, u, v)@ such that @a * u + b * v == g@.
    --
    -- Reference: https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#B.C3.A9zout.27s_identity_and_extended_GCD_algorithm
    gcdF2m :: Integer
           -> Integer
           -> (Integer, Integer, Integer)
    gcdF2m a b = go (a, b, 1, 0, 0, 1)
      where
        go (g, 0, u, _, v, _)
            = (g, u, v)
        go (r0, r1, s0, s1, t0, t1)
            = go (r1, r0 `addF2m` shift r1 j, s1, s0 `addF2m` shift s1 j, t1, t0 `addF2m` shift t1 j)
                where j = max 0 (log2 r0 - log2 r1)

    -- | Modular inversion over F₂m.
    -- If @n@ doesn't have an inverse, 'Nothing' is returned.
    --
    -- This function is undefined for negative arguments, because their bit
    -- representation is platform-dependent. Zero modulus is also prohibited.
    invF2m :: BinaryPolynomial -- ^ Modulus
           -> Integer
           -> Maybe Integer
    invF2m fx n = if g == 1 then Just (modF2m fx u) else Nothing
      where
        (g, u, _) = gcdF2m n fx
    {-# INLINABLE invF2m #-}

    -- | Division over F₂m. If the dividend doesn't have an inverse it returns
    -- 'Nothing'.
    --
    -- This function is undefined for negative arguments, because their bit
    -- representation is platform-dependent. Zero modulus is also prohibited.
    divF2m :: BinaryPolynomial -- ^ Modulus
           -> Integer          -- ^ Dividend
           -> Integer          -- ^ Divisor
           -> Maybe Integer    -- ^ Quotient
    divF2m fx n1 n2 = mulF2m fx n1 <$> invF2m fx n2
    {-# INLINE divF2m #-}