-- | Table of Conway polynomials
--
-- The data is from <http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol/index.html>
--

{-# LANGUAGE ForeignFunctionInterface, StandaloneDeriving, BangPatterns #-}
{-# LANGUAGE GADTs, ExistentialQuantification, DataKinds, KindSignatures #-}

module Math.FiniteField.Conway 
  ( ConwayPoly
  , SomeConwayPoly(..)
  , conwayPrime  , conwayDim
  , conwayParams , conwayParams'
  , conwayCoefficients
  , lookupSomeConwayPoly   
  , lookupConwayPoly
  , unsafeLookupConwayPoly 
  , lookupConwayPrimRoot
  )
  where

--------------------------------------------------------------------------------

import Data.Word
import Data.Bits

import Data.Proxy

import GHC.TypeNats (Nat)

import qualified Data.IntMap.Strict as IntMap

--import Foreign.C
import Foreign.Ptr
--import Foreign.Storable
--import Foreign.Marshal
--import Foreign.Marshal.Array

import qualified System.IO.Unsafe as Unsafe

import Math.FiniteField.TypeLevel
import Math.FiniteField.TypeLevel.Singleton
import Math.FiniteField.Conway.Internal

-- import Data.Array
-- import Math.FiniteField.PrimeField.Small

--------------------------------------------------------------------------------

-- data ConwayPoly p = ConwayPoly
--   { _prime    :: !(IsPrime p)
--   , _exponent :: !Int
--   , _coeffs   :: !(Array Int (Fp p))
--   }

--------------------------------------------------------------------------------
-- * Witness for the existence of precomputed Conway polynomials

data SomeConwayPoly = forall p m. SomeConwayPoly (ConwayPoly p m) 

deriving instance Show SomeConwayPoly

conwayProxies :: ConwayPoly p m -> (Proxy p, Proxy m)
conwayProxies :: forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Proxy p, Proxy m)
conwayProxies ConwayPoly p m
_ = (forall {k} (t :: k). Proxy t
Proxy, forall {k} (t :: k). Proxy t
Proxy)

instance Show (ConwayPoly p m) where
  show :: ConwayPoly p m -> String
show ConwayPoly p m
witness = String
"ConwayPoly[" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Word64
p forall a. [a] -> [a] -> [a]
++ String
"^" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Int
m forall a. [a] -> [a] -> [a]
++ String
"]" where
    (Word64
p,Int
m) = forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
witness

-- | The prime characteristic @p@
conwayPrime :: ConwayPoly p m -> IsSmallPrime p
conwayPrime :: forall (p :: Nat) (m :: Nat). ConwayPoly p m -> IsSmallPrime p
conwayPrime (ConwayWitness Ptr Word32
ptr) = forall a. IO a -> a
Unsafe.unsafePerformIO forall a b. (a -> b) -> a -> b
$ do
  (Word64
p,Int
_) <- Ptr Word32 -> IO (Word64, Int)
getConwayEntryParams Ptr Word32
ptr
  forall (m :: * -> *) a. Monad m => a -> m a
return (forall (n :: Nat). SNat64 n -> IsSmallPrime n
believeMeItsASmallPrime (forall (n :: Nat). Word64 -> SNat64 n
SNat64 Word64
p))

-- | The dimension @m@ of @F_q@ over @F_p@
conwayDim :: ConwayPoly p m -> Int
conwayDim :: forall (p :: Nat) (m :: Nat). ConwayPoly p m -> Int
conwayDim (ConwayWitness Ptr Word32
ptr) = forall a. IO a -> a
Unsafe.unsafePerformIO forall a b. (a -> b) -> a -> b
$ do
  (Word64
_,Int
m) <- Ptr Word32 -> IO (Word64, Int)
getConwayEntryParams Ptr Word32
ptr
  forall (m :: * -> *) a. Monad m => a -> m a
return (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
m)

-- | The pair @(p,m)@
conwayParams :: ConwayPoly p m -> (Int,Int)
conwayParams :: forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Int, Int)
conwayParams ConwayPoly p m
witness = (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
p, forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
m) where
  (Word64
p,Int
m) = forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
witness

conwayParams' :: ConwayPoly p m -> (SNat64 p, SNat64 m)
conwayParams' :: forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> (SNat64 p, SNat64 m)
conwayParams' ConwayPoly p m
witness = (forall (n :: Nat). Word64 -> SNat64 n
SNat64 Word64
p, forall (n :: Nat). Word64 -> SNat64 n
SNat64 (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
m)) where
  (Word64
p,Int
m) = forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
witness

conwayCoefficients :: ConwayPoly p m -> [Word64]
conwayCoefficients :: forall (p :: Nat) (m :: Nat). ConwayPoly p m -> [Word64]
conwayCoefficients (ConwayWitness Ptr Word32
ptr) = forall a. IO a -> a
Unsafe.unsafePerformIO forall a b. (a -> b) -> a -> b
$ do
  (Word64
_,Int
_,[Word64]
list) <- Ptr Word32 -> IO (Word64, Int, [Word64])
marshalConwayEntry Ptr Word32
ptr
  forall (m :: * -> *) a. Monad m => a -> m a
return [Word64]
list

-- | Usage: @lookupConwayPoly sp sm@ for @q = p^m@
lookupConwayPoly :: SNat64 p -> SNat64 m -> Maybe (ConwayPoly p m)
lookupConwayPoly :: forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> Maybe (ConwayPoly p m)
lookupConwayPoly !SNat64 p
sp !SNat64 m
sm = 
  let p :: Int
p = forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall (n :: Nat). SNat64 n -> Word64
fromSNat64 SNat64 p
sp)
      m :: Int
m = forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall (n :: Nat). SNat64 n -> Word64
fromSNat64 SNat64 m
sm)
  in case forall a. Int -> IntMap a -> Maybe a
IntMap.lookup (Int -> Int -> Int
encodePrimeExpo Int
p Int
m) (ConwayTable -> IntMap (Ptr Word32)
fromConwayTable ConwayTable
theConwayTable) of
       Maybe (Ptr Word32)
Nothing  -> forall a. Maybe a
Nothing
       Just Ptr Word32
ptr -> forall a. a -> Maybe a
Just (forall (p :: Nat) (m :: Nat). Ptr Word32 -> ConwayPoly p m
ConwayWitness Ptr Word32
ptr)

unsafeLookupConwayPoly :: SNat64 p -> SNat64 m -> ConwayPoly p m
unsafeLookupConwayPoly :: forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> ConwayPoly p m
unsafeLookupConwayPoly SNat64 p
sp SNat64 m
sm = case forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> Maybe (ConwayPoly p m)
lookupConwayPoly SNat64 p
sp SNat64 m
sm of
  Maybe (ConwayPoly p m)
Nothing  -> forall a. HasCallStack => String -> a
error String
"unsafeLookupConwayPoly: Conway polynomial not found"
  Just ConwayPoly p m
cw  -> ConwayPoly p m
cw

-- | Usage: @lookupSomeConwayPoly p m@ for @q = p^m@
lookupSomeConwayPoly :: Int -> Int -> Maybe SomeConwayPoly
lookupSomeConwayPoly :: Int -> Int -> Maybe SomeConwayPoly
lookupSomeConwayPoly !Int
p !Int
m = case (Int64 -> SomeSNat64
someSNat64 (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
p) , Int64 -> SomeSNat64
someSNat64 (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
m)) of
  (SomeSNat64 SNat64 n
sp , SomeSNat64 SNat64 n
sm) -> forall (p :: Nat) (m :: Nat). ConwayPoly p m -> SomeConwayPoly
SomeConwayPoly forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> Maybe (ConwayPoly p m)
lookupConwayPoly SNat64 n
sp SNat64 n
sm

-- | We have some Conway polynomials for @m=1@ too; the roots of 
-- these linear polynomials are primitive roots in @F_p@
lookupConwayPrimRoot :: Int -> Maybe Int
lookupConwayPrimRoot :: Int -> Maybe Int
lookupConwayPrimRoot Int
p = forall a b. (Integral a, Num b) => a -> b
fromIntegral forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Int -> Maybe Word64
lookupConwayPrimRoot_ Int
p)

--------------------------------------------------------------------------------