{-# LINE 1 "src/Data/Number/Flint/Fmpz/Poly/Factor/FFI.hsc" #-}
{-|
module      :  Data.Number.Flint.Fmpz.Poly.Factor.FFI
copyright   :  (c) 2022 Hartmut Monien
license     :  GNU GPL, version 2 or above (see LICENSE)
maintainer  :  hmonien@uni-bonn.de
-}
module Data.Number.Flint.Fmpz.Poly.Factor.FFI (
  -- * Factorisation of polynomials over the integers
    FmpzPolyFactor (..)
  , CFmpzPolyFactor (..)
  , newFmpzPolyFactor
  , withFmpzPolyFactor
  , withNewFmpzPolyFactor
  -- * Types, macros and constants
  -- * Memory management
  , fmpz_poly_factor_init
  , fmpz_poly_factor_init2
  , fmpz_poly_factor_realloc
  , fmpz_poly_factor_fit_length
  , fmpz_poly_factor_clear
  -- * Manipulating factors
  , fmpz_poly_factor_set
  , fmpz_poly_factor_insert
  , fmpz_poly_factor_concat
  -- * Input and output
  , fmpz_poly_factor_print
  -- * Factoring algorithms
  , fmpz_poly_factor_squarefree
  , fmpz_poly_factor_zassenhaus_recombination
  , _fmpz_poly_factor_zassenhaus
  , fmpz_poly_factor_zassenhaus
  , _fmpz_poly_factor_quadratic
  , fmpz_poly_factor
) where 

-- factorisation of polynomials over the integers ------------------------------

import Foreign.C.String
import Foreign.C.Types
import Foreign.ForeignPtr
import Foreign.Ptr ( Ptr, FunPtr, plusPtr, castPtr )
import Foreign.Storable
import Foreign.Marshal ( free )

import Data.Number.Flint.Flint
import Data.Number.Flint.Fmpz
import Data.Number.Flint.Fmpz.Poly







-- fmpz_poly_factor_t ----------------------------------------------------------

-- Note that the structure of CFmpzPolyFactor is different from the
-- corresponding structure in <flint/fmpz_poly_factor.h>. The reason
-- for this is that we can only deal with `Ptr CFmpz` and not with the
-- structure `CFmpz` directly in Haskell. Otherwise we would have to
-- cope with the `fmpz_t` structure either containing an `slong` or
-- `mpz_ptr`.

data FmpzPolyFactor =
  FmpzPolyFactor {-# UNPACK #-} !(ForeignPtr CFmpzPolyFactor)
data CFmpzPolyFactor = CFmpzPolyFactor (Ptr CFmpz) (Ptr CFmpzPoly) (Ptr CLong) CLong CLong 

instance Storable CFmpzPolyFactor where
  {-# INLINE sizeOf #-}
  sizeOf :: CFmpzPolyFactor -> Int
sizeOf CFmpzPolyFactor
_ = (Int
40)
{-# LINE 71 "src/Data/Number/Flint/Fmpz/Poly/Factor/FFI.hsc" #-}
  {-# INLINE alignment #-}
  alignment :: CFmpzPolyFactor -> Int
alignment CFmpzPolyFactor
_ = Int
8
{-# LINE 73 "src/Data/Number/Flint/Fmpz/Poly/Factor/FFI.hsc" #-}
  peek ptr = CFmpzPolyFactor
    <$> (return $ castPtr ptr)
    <*> (\hsc_ptr -> peekByteOff hsc_ptr 8) ptr
{-# LINE 76 "src/Data/Number/Flint/Fmpz/Poly/Factor/FFI.hsc" #-}
    <*> (\hsc_ptr -> peekByteOff hsc_ptr 16) ptr
{-# LINE 77 "src/Data/Number/Flint/Fmpz/Poly/Factor/FFI.hsc" #-}
    <*> (\hsc_ptr -> peekByteOff hsc_ptr 24) ptr
{-# LINE 78 "src/Data/Number/Flint/Fmpz/Poly/Factor/FFI.hsc" #-}
    <*> (\hsc_ptr -> peekByteOff hsc_ptr 32) ptr
{-# LINE 79 "src/Data/Number/Flint/Fmpz/Poly/Factor/FFI.hsc" #-}
  poke = error "CFmpzPolyFactor.poke: Not defined"

newFmpzPolyFactor :: IO FmpzPolyFactor
newFmpzPolyFactor = do
  ForeignPtr CFmpzPolyFactor
p <- IO (ForeignPtr CFmpzPolyFactor)
forall a. Storable a => IO (ForeignPtr a)
mallocForeignPtr
  ForeignPtr CFmpzPolyFactor
-> (Ptr CFmpzPolyFactor -> IO ()) -> IO ()
forall a b. ForeignPtr a -> (Ptr a -> IO b) -> IO b
withForeignPtr ForeignPtr CFmpzPolyFactor
p Ptr CFmpzPolyFactor -> IO ()
fmpz_poly_factor_init
  FinalizerPtr CFmpzPolyFactor -> ForeignPtr CFmpzPolyFactor -> IO ()
forall a. FinalizerPtr a -> ForeignPtr a -> IO ()
addForeignPtrFinalizer FinalizerPtr CFmpzPolyFactor
p_fmpz_poly_factor_clear ForeignPtr CFmpzPolyFactor
p
  FmpzPolyFactor -> IO FmpzPolyFactor
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return (FmpzPolyFactor -> IO FmpzPolyFactor)
-> FmpzPolyFactor -> IO FmpzPolyFactor
forall a b. (a -> b) -> a -> b
$ ForeignPtr CFmpzPolyFactor -> FmpzPolyFactor
FmpzPolyFactor ForeignPtr CFmpzPolyFactor
p

{-# INLINE withFmpzPolyFactor #-}
withFmpzPolyFactor :: FmpzPolyFactor
-> (Ptr CFmpzPolyFactor -> IO a) -> IO (FmpzPolyFactor, a)
withFmpzPolyFactor (FmpzPolyFactor ForeignPtr CFmpzPolyFactor
p) Ptr CFmpzPolyFactor -> IO a
f = do
  ForeignPtr CFmpzPolyFactor
-> (Ptr CFmpzPolyFactor -> IO (FmpzPolyFactor, a))
-> IO (FmpzPolyFactor, a)
forall a b. ForeignPtr a -> (Ptr a -> IO b) -> IO b
withForeignPtr ForeignPtr CFmpzPolyFactor
p ((Ptr CFmpzPolyFactor -> IO (FmpzPolyFactor, a))
 -> IO (FmpzPolyFactor, a))
-> (Ptr CFmpzPolyFactor -> IO (FmpzPolyFactor, a))
-> IO (FmpzPolyFactor, a)
forall a b. (a -> b) -> a -> b
$ \Ptr CFmpzPolyFactor
fp -> Ptr CFmpzPolyFactor -> IO a
f Ptr CFmpzPolyFactor
fp IO a -> (a -> IO (FmpzPolyFactor, a)) -> IO (FmpzPolyFactor, a)
forall a b. IO a -> (a -> IO b) -> IO b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (FmpzPolyFactor, a) -> IO (FmpzPolyFactor, a)
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return ((FmpzPolyFactor, a) -> IO (FmpzPolyFactor, a))
-> (a -> (FmpzPolyFactor, a)) -> a -> IO (FmpzPolyFactor, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (ForeignPtr CFmpzPolyFactor -> FmpzPolyFactor
FmpzPolyFactor ForeignPtr CFmpzPolyFactor
p,)

withNewFmpzPolyFactor :: (Ptr CFmpzPolyFactor -> IO a) -> IO (FmpzPolyFactor, a)
withNewFmpzPolyFactor Ptr CFmpzPolyFactor -> IO a
f = do
  FmpzPolyFactor
x <- IO FmpzPolyFactor
newFmpzPolyFactor
  FmpzPolyFactor
-> (Ptr CFmpzPolyFactor -> IO a) -> IO (FmpzPolyFactor, a)
forall {a}.
FmpzPolyFactor
-> (Ptr CFmpzPolyFactor -> IO a) -> IO (FmpzPolyFactor, a)
withFmpzPolyFactor FmpzPolyFactor
x ((Ptr CFmpzPolyFactor -> IO a) -> IO (FmpzPolyFactor, a))
-> (Ptr CFmpzPolyFactor -> IO a) -> IO (FmpzPolyFactor, a)
forall a b. (a -> b) -> a -> b
$ \Ptr CFmpzPolyFactor
x -> Ptr CFmpzPolyFactor -> IO a
f Ptr CFmpzPolyFactor
x
  
-- Memory management -----------------------------------------------------------

-- | /fmpz_poly_factor_init/ /fac/ 
-- 
-- Initialises a new factor structure.
foreign import ccall "fmpz_poly_factor.h fmpz_poly_factor_init"
  fmpz_poly_factor_init :: Ptr CFmpzPolyFactor -> IO ()

-- | /fmpz_poly_factor_init2/ /fac/ /alloc/ 
-- 
-- Initialises a new factor structure, providing space for at least @alloc@
-- factors.
foreign import ccall "fmpz_poly_factor.h fmpz_poly_factor_init2"
  fmpz_poly_factor_init2 :: Ptr CFmpzPolyFactor -> CLong -> IO ()

-- | /fmpz_poly_factor_realloc/ /fac/ /alloc/ 
-- 
-- Reallocates the factor structure to provide space for precisely @alloc@
-- factors.
foreign import ccall "fmpz_poly_factor.h fmpz_poly_factor_realloc"
  fmpz_poly_factor_realloc :: Ptr CFmpzPolyFactor -> CLong -> IO ()

-- | /fmpz_poly_factor_fit_length/ /fac/ /len/ 
-- 
-- Ensures that the factor structure has space for at least @len@ factors.
-- This functions takes care of the case of repeated calls by always at
-- least doubling the number of factors the structure can hold.
foreign import ccall "fmpz_poly_factor.h fmpz_poly_factor_fit_length"
  fmpz_poly_factor_fit_length :: Ptr CFmpzPolyFactor -> CLong -> IO ()

-- | /fmpz_poly_factor_clear/ /fac/ 
-- 
-- Releases all memory occupied by the factor structure.
foreign import ccall "fmpz_poly_factor.h fmpz_poly_factor_clear"
  fmpz_poly_factor_clear :: Ptr CFmpzPolyFactor -> IO ()

foreign import ccall "fmpz_poly_factor.h &fmpz_poly_factor_clear"
  p_fmpz_poly_factor_clear :: FunPtr (Ptr CFmpzPolyFactor -> IO ())

-- Manipulating factors --------------------------------------------------------

-- | /fmpz_poly_factor_set/ /res/ /fac/ 
-- 
-- Sets @res@ to the same factorisation as @fac@.
foreign import ccall "fmpz_poly_factor.h fmpz_poly_factor_set"
  fmpz_poly_factor_set :: Ptr CFmpzPolyFactor -> Ptr CFmpzPolyFactor -> IO ()

-- | /fmpz_poly_factor_insert/ /fac/ /p/ /e/ 
-- 
-- Adds the primitive polynomial \(p^e\) to the factorisation @fac@.
-- 
-- Assumes that \(\deg(p) \geq 2\) and \(e \neq 0\).
foreign import ccall "fmpz_poly_factor.h fmpz_poly_factor_insert"
  fmpz_poly_factor_insert :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> CLong -> IO ()

-- | /fmpz_poly_factor_concat/ /res/ /fac/ 
-- 
-- Concatenates two factorisations.
-- 
-- This is equivalent to calling @fmpz_poly_factor_insert@ repeatedly with
-- the individual factors of @fac@.
-- 
-- Does not support aliasing between @res@ and @fac@.
foreign import ccall "fmpz_poly_factor.h fmpz_poly_factor_concat"
  fmpz_poly_factor_concat :: Ptr CFmpzPolyFactor -> Ptr CFmpzPolyFactor -> IO ()

-- Input and output ------------------------------------------------------------

-- | /fmpz_poly_factor_print/ /fac/ 
-- 
-- Prints the entries of @fac@ to standard output.
foreign import ccall "fmpz_poly_factor.h fmpz_poly_factor_print"
  fmpz_poly_factor_print :: Ptr CFmpzPolyFactor -> IO ()

-- Factoring algorithms --------------------------------------------------------

-- | /fmpz_poly_factor_squarefree/ /fac/ /F/ 
-- 
-- Takes as input a polynomial \(F\) and a freshly initialized factor
-- structure @fac@. Updates @fac@ to contain a factorization of \(F\) into
-- (not necessarily irreducible) factors that themselves have no repeated
-- factors. None of the returned factors will have the same exponent. That
-- is we return \(g_i\) and unique \(e_i\) such that
-- 
-- \[F = c \prod_{i} g_i^{e_i}\]
-- 
-- where \(c\) is the signed content of \(F\) and \(\gcd(g_i, g_i') = 1\).
foreign import ccall "fmpz_poly_factor.h fmpz_poly_factor_squarefree"
  fmpz_poly_factor_squarefree :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> IO ()

-- | /fmpz_poly_factor_zassenhaus_recombination/ /final_fac/ /lifted_fac/ /F/ /P/ /exp/ 
-- 
-- Takes as input a factor structure @lifted_fac@ containing a squarefree
-- factorization of the polynomial \(F \bmod p\). The algorithm does a
-- brute force search for irreducible factors of \(F\) over the integers,
-- and each factor is raised to the power @exp@.
-- 
-- The impact of the algorithm is to augment a factorization of @F^exp@ to
-- the factor structure @final_fac@.
foreign import ccall "fmpz_poly_factor.h fmpz_poly_factor_zassenhaus_recombination"
  fmpz_poly_factor_zassenhaus_recombination :: Ptr CFmpzPolyFactor -> Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> Ptr CFmpz -> CLong -> IO ()

-- | /_fmpz_poly_factor_zassenhaus/ /final_fac/ /exp/ /f/ /cutoff/ /use_van_hoeij/ 
-- 
-- This is the internal wrapper of Zassenhaus.
-- 
-- It will attempt to find a small prime such that \(f\) modulo \(p\) has a
-- minimal number of factors. If it cannot find a prime giving less than
-- @cutoff@ factors it aborts. Then it decides a \(p\)-adic precision to
-- lift the factors to, hensel lifts, and finally calls Zassenhaus
-- recombination.
-- 
-- Assumes that \(\operatorname{len}(f) \geq 2\).
-- 
-- Assumes that \(f\) is primitive.
-- 
-- Assumes that the constant coefficient of \(f\) is non-zero. Note that
-- this can be easily achieved by taking out factors of the form \(x^k\)
-- before calling this routine.
-- 
-- If the final flag is set, the function will use the van Hoeij
-- factorisation algorithm with gradual feeding and mod \(2^k\) data
-- truncation to find factors when the number of local factors is large.
foreign import ccall "fmpz_poly_factor.h _fmpz_poly_factor_zassenhaus"
  _fmpz_poly_factor_zassenhaus :: Ptr CFmpzPolyFactor -> CLong -> Ptr CFmpzPoly -> CLong -> CInt -> IO ()

-- | /fmpz_poly_factor_zassenhaus/ /final_fac/ /F/ 
-- 
-- A wrapper of the Zassenhaus factoring algorithm, which takes as input
-- any polynomial \(F\), and stores a factorization in @final_fac@.
-- 
-- The complexity will be exponential in the number of local factors we
-- find for the components of a squarefree factorization of \(F\).
foreign import ccall "fmpz_poly_factor.h fmpz_poly_factor_zassenhaus"
  fmpz_poly_factor_zassenhaus :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> IO ()

-- | /_fmpz_poly_factor_quadratic/ /fac/ /f/ /exp/ 
-- 
-- Inserts the factorisation of the quadratic (resp. cubic) polynomial /f/
-- into /fac/ with multiplicity /exp/. This function requires that the
-- content of /f/ has been removed, and does not update the content of
-- /fac/. The factorzation is calculated over \(\mathbb{R}\) or
-- \(\mathbb{Q}_2\) and then tested over \(\mathbb{Z}\).
foreign import ccall "fmpz_poly_factor.h _fmpz_poly_factor_quadratic"
  _fmpz_poly_factor_quadratic :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> CLong -> IO ()

-- | /fmpz_poly_factor/ /final_fac/ /F/ 
-- 
-- A wrapper of the Zassenhaus and van Hoeij factoring algorithms, which
-- takes as input any polynomial \(F\), and stores a factorization in
-- @final_fac@.
foreign import ccall "fmpz_poly_factor.h fmpz_poly_factor"
  fmpz_poly_factor :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> IO ()