-- |
-- 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
    , modF2m
    , invF2m
    , divF2m
    ) where

import Data.Bits ((.&.),(.|.),xor,shift,testBit)
import Crypto.Number.Basic
import Crypto.Internal.Imports

-- | 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 #-}

-- | Binary polynomial reduction modulo using long division algorithm.
modF2m :: BinaryPolynomial -- ^ Irreducible binary polynomial
       -> Integer -> Integer
modF2m fx = go
  where
    lfx = log2 fx
    go n | s == 0  = n `xor` fx
         | s < 0 = n
         | otherwise = go $ n `xor` shift fx s
      where
        s = log2 n - lfx
{-# INLINE modF2m #-}

-- | Multiplication over F₂m.
--
--     n1 * n2 (in F(2^m))
mulF2m :: BinaryPolynomial  -- ^ Irreducible binary polynomial
       -> Integer -> Integer -> Integer
mulF2m fx n1 n2 = 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 `xor` shift n1 s) (s - 1)
                            else go n (s - 1)
{-# INLINABLE mulF2m #-}

-- | Squaring over F₂m.
-- TODO: This is still slower than @mulF2m@.

-- Multiplication table? C?
squareF2m :: BinaryPolynomial  -- ^ Irreducible binary polynomial
          -> Integer -> Integer
squareF2m fx = modF2m fx . square
{-# INLINE squareF2m #-}

square :: Integer -> Integer
square n1 = go n1 ln1
  where
    ln1 = log2 n1
    go n s | s == 0 = n
           | otherwise = go (x .|. y) (s - 1)
      where
        x = shift (shift n (2 * (s - ln1) - 1)) (2 * (ln1 - s) + 2)
        y = n .&. (shift 1 (2 * (ln1 - s) + 1) - 1)
{-# INLINE square #-}

-- | Inversion of @n over F₂m using extended Euclidean algorithm.
--
-- If @n doesn't have an inverse, Nothing is returned.
invF2m :: BinaryPolynomial -- ^ Irreducible binary polynomial
       -> Integer -> Maybe Integer
invF2m _  0 = Nothing
invF2m fx n
    | n >= fx   = Nothing
    | otherwise = go n fx 1 0
    where
      go u v g1 g2
          | u == 1    = Just $ modF2m fx g1
          | j < 0     = go u  (v  `xor` shift  u (-j)) g1 (g2 `xor` shift g1 (-j))
          | otherwise = go (u  `xor` shift v  j) v (g1 `xor` shift g2 j) g2
        where
          j = log2 u - log2 v
{-# INLINABLE invF2m #-}

-- | Division over F₂m. If the dividend doesn't have an inverse it returns
-- 'Nothing'.
--
-- Compute n1 / n2
divF2m :: BinaryPolynomial  -- ^ Irreducible binary polynomial
       -> Integer  -- ^ Dividend
       -> Integer  -- ^ Quotient
       -> Maybe Integer
divF2m fx n1 n2 = mulF2m fx n1 <$> invF2m fx n2
{-# INLINE divF2m #-}