{-# LANGUAGE CPP #-}{-# LANGUAGE BangPatterns #-}{-# LANGUAGE DeriveDataTypeable #-}{-# LANGUAGE DeriveGeneric #-}{-# LANGUAGE GeneralizedNewtypeDeriving #-}{-# LANGUAGE MagicHash #-}{-# LANGUAGE RankNTypes #-}
#ifndef BITVEC_THREADSAFE
moduleData.Bit.F2Poly
#else
moduleData.Bit.F2PolyTS
#endif
(F2Poly ,unF2Poly ,toF2Poly ,gcdExt )whereimportControl.DeepSeqimportControl.ExceptionimportControl.MonadimportControl.Monad.ST
#ifndef BITVEC_THREADSAFE
importData.Bit.Immutable importData.Bit.Internal importData.Bit.Mutable 
#else
importData.Bit.ImmutableTSimportData.Bit.InternalTSimportData.Bit.MutableTS
#endif
importData.Bit.Utils importData.BitsimportData.CharimportData.CoerceimportData.Primitive.ByteArrayimportData.TypeableimportqualifiedData.Vector.PrimitiveasPimportqualifiedData.Vector.UnboxedasUimportqualifiedData.Vector.Unboxed.MutableasMUimportGHC.ExtsimportGHC.GenericsimportNumeric
#ifdef MIN_VERSION_ghc_bignum
importGHC.Num.BigNatimportGHC.Num.Integer
#else
importGHC.Integer.GMP.InternalsimportGHC.Integer.Logarithms
#endif
-- | Binary polynomials of one variable, backed-- by an unboxed 'Data.Vector.Unboxed.Vector' 'Bit'.---- Polynomials are stored normalized, without leading zero coefficients.---- The 'Ord' instance does not make much sense mathematically,-- it is defined only for the sake of 'Data.Set.Set', 'Data.Map.Map', etc.---- >>> :set -XBinaryLiterals-- >>> -- (1 + x) * (1 + x + x^2) = 1 + x^3 (mod 2)-- >>> 0b11 * 0b111 :: F2Poly-- 0b1001---- @since 1.0.1.0newtypeF2Poly =F2Poly {F2Poly -> Vector Bit
unF2Poly ::U.VectorBit -- ^ Convert an 'F2Poly' to a vector of coefficients-- (first element corresponds to a constant term).---- >>> :set -XBinaryLiterals-- >>> unF2Poly 0b1101-- [1,0,1,1]---- @since 1.0.1.0}deriving(F2Poly -> F2Poly -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F2Poly -> F2Poly -> Bool
$c/= :: F2Poly -> F2Poly -> Bool
== :: F2Poly -> F2Poly -> Bool
$c== :: F2Poly -> F2Poly -> Bool
Eq,Eq F2Poly
F2Poly -> F2Poly -> Bool
F2Poly -> F2Poly -> Ordering
F2Poly -> F2Poly -> F2Poly
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: F2Poly -> F2Poly -> F2Poly
$cmin :: F2Poly -> F2Poly -> F2Poly
max :: F2Poly -> F2Poly -> F2Poly
$cmax :: F2Poly -> F2Poly -> F2Poly
>= :: F2Poly -> F2Poly -> Bool
$c>= :: F2Poly -> F2Poly -> Bool
> :: F2Poly -> F2Poly -> Bool
$c> :: F2Poly -> F2Poly -> Bool
<= :: F2Poly -> F2Poly -> Bool
$c<= :: F2Poly -> F2Poly -> Bool
< :: F2Poly -> F2Poly -> Bool
$c< :: F2Poly -> F2Poly -> Bool
compare :: F2Poly -> F2Poly -> Ordering
$ccompare :: F2Poly -> F2Poly -> Ordering
Ord,Typeable,forall x. Rep F2Poly x -> F2Poly
forall x. F2Poly -> Rep F2Poly x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cto :: forall x. Rep F2Poly x -> F2Poly
$cfrom :: forall x. F2Poly -> Rep F2Poly x
Generic,F2Poly -> ()
forall a. (a -> ()) -> NFData a
rnf :: F2Poly -> ()
$crnf :: F2Poly -> ()
NFData)-- | Make an 'F2Poly' from a list of coefficients-- (first element corresponds to a constant term).---- >>> :set -XOverloadedLists-- >>> toF2Poly [1,0,1,1,0,0]-- 0b1101---- @since 1.0.1.0toF2Poly ::U.VectorBit ->F2Poly toF2Poly :: Vector Bit -> F2Poly
toF2Poly Vector Bit
xs =Vector Bit -> F2Poly
F2Poly forall a b. (a -> b) -> a -> b
$Vector Bit -> Vector Bit
dropWhileEnd forall a b. (a -> b) -> a -> b
$Vector Word -> Vector Bit
castFromWords forall a b. (a -> b) -> a -> b
$Vector Bit -> Vector Word
cloneToWords Vector Bit
xs zero ::F2Poly zero :: F2Poly
zero =Vector Bit -> F2Poly
F2Poly forall a b. (a -> b) -> a -> b
$Int -> Int -> ByteArray -> Vector Bit
BitVec Int
0Int
0forall a b. (a -> b) -> a -> b
$
#ifdef MIN_VERSION_ghc_bignum
ByteArray# -> ByteArray
ByteArray(BigNat -> ByteArray#
unBigNatBigNat
bigNatZero)
#else
fromBigNatzeroBigNat
#endif
one ::F2Poly one :: F2Poly
one =Vector Bit -> F2Poly
F2Poly forall a b. (a -> b) -> a -> b
$Int -> Int -> ByteArray -> Vector Bit
BitVec Int
0Int
1forall a b. (a -> b) -> a -> b
$
#ifdef MIN_VERSION_ghc_bignum
ByteArray# -> ByteArray
ByteArray(BigNat -> ByteArray#
unBigNatBigNat
bigNatOne)
#else
fromBigNatoneBigNat
#endif
-- -- | A valid 'F2Poly' has offset 0 and no trailing garbage.-- _isValid :: F2Poly -> Bool-- _isValid (F2Poly (BitVec o l arr)) = o == 0 && l == l'-- where-- l' = U.length $ dropWhileEnd $ BitVec 0 (sizeofByteArray arr `shiftL` 3) arr-- | Addition and multiplication are evaluated modulo 2.---- 'abs' = 'id' and 'signum' = 'const' 1.---- 'fromInteger' converts a binary polynomial, encoded as 'Integer',-- to 'F2Poly' encoding.instanceNumF2Poly where+ :: F2Poly -> F2Poly -> F2Poly
(+)=coerce :: forall a b. Coercible a b => a -> b
coerceVector Bit -> Vector Bit -> Vector Bit
xorBits (-)=coerce :: forall a b. Coercible a b => a -> b
coerceVector Bit -> Vector Bit -> Vector Bit
xorBits negate :: F2Poly -> F2Poly
negate=forall a. a -> a
idabs :: F2Poly -> F2Poly
abs=forall a. a -> a
idsignum :: F2Poly -> F2Poly
signum=forall a b. a -> b -> a
constF2Poly
one * :: F2Poly -> F2Poly -> F2Poly
(*)=coerce :: forall a b. Coercible a b => a -> b
coerce((Vector Bit -> Vector Bit
dropWhileEnd forall b c a. (b -> c) -> (a -> b) -> a -> c
.)forall b c a. (b -> c) -> (a -> b) -> a -> c
.Vector Bit -> Vector Bit -> Vector Bit
karatsuba )
#ifdef MIN_VERSION_ghc_bignum
fromInteger :: Integer -> F2Poly
fromInteger!Integer
n =caseInteger
n ofISInt#
i# |Integer
n forall a. Ord a => a -> a -> Bool
<Integer
0->forall a e. Exception e => e -> a
throwArithException
Underflow|Bool
otherwise->Vector Bit -> F2Poly
F2Poly forall a b. (a -> b) -> a -> b
$Int -> Int -> ByteArray -> Vector Bit
BitVec Int
0(Int
wordSize forall a. Num a => a -> a -> a
-Int# -> Int
I#(Word# -> Int#
word2Int#(Word# -> Word#
clz#(Int# -> Word#
int2Word#Int#
i# ))))forall a b. (a -> b) -> a -> b
$ByteArray# -> ByteArray
ByteArray(Word# -> ByteArray#
bigNatFromWord#(Int# -> Word#
int2Word#Int#
i# ))IPByteArray#
bn# ->Vector Bit -> F2Poly
F2Poly forall a b. (a -> b) -> a -> b
$Int -> Int -> ByteArray -> Vector Bit
BitVec Int
0(Int# -> Int
I#(Word# -> Int#
word2Int#(Integer -> Word#
integerLog2#Integer
n ))forall a. Num a => a -> a -> a
+Int
1)forall a b. (a -> b) -> a -> b
$ByteArray# -> ByteArray
ByteArrayByteArray#
bn# IN{}->forall a e. Exception e => e -> a
throwArithException
Underflow{-# INLINEfromInteger#-}
#else
fromInteger!n=casenofS#i#|n<0->throwUnderflow|otherwise->F2Poly$BitVec0(wordSize-I#(word2Int#(clz#(int2Word#i#))))$fromBigNat$wordToBigNat(int2Word#i#)Jp#bn#->F2Poly$BitVec0(I#(integerLog2#n)+1)$fromBigNatbn#Jn#{}->throwUnderflow{-# INLINEfromInteger#-}
#endif
{-# INLINE(+)#-}{-# INLINE(-)#-}{-# INLINEnegate#-}{-# INLINEabs#-}{-# INLINEsignum#-}{-# INLINE(*)#-}instanceEnumF2Poly wherefromEnum :: F2Poly -> Int
fromEnum=forall a b. (Integral a, Num b) => a -> b
fromIntegral
#ifdef MIN_VERSION_ghc_bignum
toEnum :: Int -> F2Poly
toEnum(I#Int#
i# )=Vector Bit -> F2Poly
F2Poly forall a b. (a -> b) -> a -> b
$Int -> Int -> ByteArray -> Vector Bit
BitVec Int
0(Int
wordSize forall a. Num a => a -> a -> a
-Int# -> Int
I#(Word# -> Int#
word2Int#(Word# -> Word#
clz#(Int# -> Word#
int2Word#Int#
i# ))))forall a b. (a -> b) -> a -> b
$ByteArray# -> ByteArray
ByteArray(Word# -> ByteArray#
bigNatFromWord#(Int# -> Word#
int2Word#Int#
i# ))
#else
toEnum(I#i#)=F2Poly$BitVec0(wordSize-I#(word2Int#(clz#(int2Word#i#))))$fromBigNat$wordToBigNat(int2Word#i#)
#endif
instanceRealF2Poly wheretoRational :: F2Poly -> Rational
toRational=forall a b. (Integral a, Num b) => a -> b
fromIntegral-- | 'toInteger' converts a binary polynomial, encoded as 'F2Poly',-- to an 'Integer' encoding.instanceIntegralF2Poly where
#ifdef MIN_VERSION_ghc_bignum
toInteger :: F2Poly -> Integer
toIntegerF2Poly
xs =ByteArray# -> Integer
integerFromBigNat#(Vector Bit -> ByteArray#
bitsToByteArray (F2Poly -> Vector Bit
unF2Poly F2Poly
xs ))
#else
toIntegerxs=bigNatToInteger(BN#(bitsToByteArray(unF2Polyxs)))
#endif
quotRem :: F2Poly -> F2Poly -> (F2Poly, F2Poly)
quotRem(F2Poly Vector Bit
xs )(F2Poly Vector Bit
ys )=(Vector Bit -> F2Poly
F2Poly (Vector Bit -> Vector Bit
dropWhileEnd Vector Bit
qs ),Vector Bit -> F2Poly
F2Poly (Vector Bit -> Vector Bit
dropWhileEnd Vector Bit
rs ))where(Vector Bit
qs ,Vector Bit
rs )=Vector Bit -> Vector Bit -> (Vector Bit, Vector Bit)
quotRemBits Vector Bit
xs Vector Bit
ys divMod :: F2Poly -> F2Poly -> (F2Poly, F2Poly)
divMod=forall a. Integral a => a -> a -> (a, a)
quotRemmod :: F2Poly -> F2Poly -> F2Poly
mod=forall a. Integral a => a -> a -> a
reminstanceShowF2Poly whereshow :: F2Poly -> String
show=(:)Char
'0'forall b c a. (b -> c) -> (a -> b) -> a -> c
.(:)Char
'b'forall b c a. (b -> c) -> (a -> b) -> a -> c
.forall a b c. (a -> b -> c) -> b -> a -> c
flip(forall a. (Integral a, Show a) => a -> (Int -> Char) -> a -> ShowS
showIntAtBaseInteger
2Int -> Char
intToDigit)String
""forall b c a. (b -> c) -> (a -> b) -> a -> c
.forall a. Integral a => a -> Integer
toInteger-- | Inputs must be valid for wrapping into F2Poly: no trailing garbage is allowed.xorBits ::U.VectorBit ->U.VectorBit ->U.VectorBit xorBits :: Vector Bit -> Vector Bit -> Vector Bit
xorBits (BitVec Int
_Int
0ByteArray
_)Vector Bit
ys =Vector Bit
ys xorBits Vector Bit
xs (BitVec Int
_Int
0ByteArray
_)=Vector Bit
xs -- GMP has platform-dependent ASM implementations for mpn_xor_n,-- which are impossible to beat by native Haskell.
#ifdef MIN_VERSION_ghc_bignum
xorBits (BitVec Int
0Int
lx (ByteArrayByteArray#
xarr ))(BitVec Int
0Int
ly (ByteArrayByteArray#
yarr ))=caseInt
lx forall a. Ord a => a -> a -> Ordering
`compare`Int
ly ofOrdering
LT->Int -> Int -> ByteArray -> Vector Bit
BitVec Int
0Int
ly ByteArray
zs Ordering
EQ->Vector Bit -> Vector Bit
dropWhileEnd forall a b. (a -> b) -> a -> b
$Int -> Int -> ByteArray -> Vector Bit
BitVec Int
0(Int
lx forall a. Ord a => a -> a -> a
`min`(ByteArray -> Int
sizeofByteArrayByteArray
zs forall a. Bits a => a -> Int -> a
`shiftL`Int
3))ByteArray
zs Ordering
GT->Int -> Int -> ByteArray -> Vector Bit
BitVec Int
0Int
lx ByteArray
zs wherezs :: ByteArray
zs =ByteArray# -> ByteArray
ByteArray(ByteArray#
xarr ByteArray# -> ByteArray# -> ByteArray#
`bigNatXor`ByteArray#
yarr )
#else
xorBits(BitVec0lxxarr)(BitVec0lyyarr)=caselx`compare`lyofLT->BitVec0lyzsEQ->dropWhileEnd$BitVec0(lx`min`(sizeofByteArrayzs`shiftL`3))zsGT->BitVec0lxzswherezs=fromBigNat(toBigNatxarr`xorBigNat`toBigNatyarr)
#endif
xorBits Vector Bit
xs Vector Bit
ys =Vector Bit -> Vector Bit
dropWhileEnd forall a b. (a -> b) -> a -> b
$forall a. (forall s. ST s a) -> a
runSTforall a b. (a -> b) -> a -> b
$doletlx :: Int
lx =forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
xs ly :: Int
ly =forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
ys (Int
shorterLen ,Int
longerLen ,Vector Bit
longer )=ifInt
lx forall a. Ord a => a -> a -> Bool
>=Int
ly then(Int
ly ,Int
lx ,Vector Bit
xs )else(Int
lx ,Int
ly ,Vector Bit
ys )MVector s Bit
zs <-forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
MU.replicateInt
longerLen (Bool -> Bit
Bit Bool
False)forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_[Int
0,Int
wordSize ..Int
shorterLen forall a. Num a => a -> a -> a
-Int
1]forall a b. (a -> b) -> a -> b
$\Int
i ->forall (m :: * -> *).
PrimMonad m =>
MVector (PrimState m) Bit -> Int -> Word -> m ()
writeWord MVector s Bit
zs Int
i (Vector Bit -> Int -> Word
indexWord Vector Bit
xs Int
i forall a. Bits a => a -> a -> a
`xor`Vector Bit -> Int -> Word
indexWord Vector Bit
ys Int
i )forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> Vector a -> m ()
U.unsafeCopy(forall a s. Unbox a => Int -> MVector s a -> MVector s a
MU.dropInt
shorterLen MVector s Bit
zs )(forall a. Unbox a => Int -> Vector a -> Vector a
U.dropInt
shorterLen Vector Bit
longer )forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
U.unsafeFreezeMVector s Bit
zs -- | Must be >= 2 * wordSize.karatsubaThreshold ::IntkaratsubaThreshold :: Int
karatsubaThreshold =Int
2048karatsuba ::U.VectorBit ->U.VectorBit ->U.VectorBit karatsuba :: Vector Bit -> Vector Bit -> Vector Bit
karatsuba Vector Bit
xs Vector Bit
ys |Vector Bit
xs forall a. Eq a => a -> a -> Bool
==Vector Bit
ys =Vector Bit -> Vector Bit
sqrBits Vector Bit
xs |Int
lenXs forall a. Ord a => a -> a -> Bool
<=Int
karatsubaThreshold Bool -> Bool -> Bool
||Int
lenYs forall a. Ord a => a -> a -> Bool
<=Int
karatsubaThreshold =Vector Bit -> Vector Bit -> Vector Bit
mulBits Vector Bit
xs Vector Bit
ys |Bool
otherwise=forall a. (forall s. ST s a) -> a
runSTforall a b. (a -> b) -> a -> b
$doMVector s Bit
zs <-forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
MU.unsafeNewInt
lenZs forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_[Int
0..forall a. Bits a => a -> a
divWordSize (Int
lenZs forall a. Num a => a -> a -> a
-Int
1)]forall a b. (a -> b) -> a -> b
$\Int
k ->doletz0 :: Word
z0 =Vector Bit -> Int -> Word
indexWord0 Vector Bit
zs0 Int
k z11 :: Word
z11 =Vector Bit -> Int -> Word
indexWord0 Vector Bit
zs11 (Int
k forall a. Num a => a -> a -> a
-Int
m )z10 :: Word
z10 =Vector Bit -> Int -> Word
indexWord0 Vector Bit
zs0 (Int
k forall a. Num a => a -> a -> a
-Int
m )z12 :: Word
z12 =Vector Bit -> Int -> Word
indexWord0 Vector Bit
zs2 (Int
k forall a. Num a => a -> a -> a
-Int
m )z2 :: Word
z2 =Vector Bit -> Int -> Word
indexWord0 Vector Bit
zs2 (Int
k forall a. Num a => a -> a -> a
-Int
2forall a. Num a => a -> a -> a
*Int
m )forall (m :: * -> *).
PrimMonad m =>
MVector (PrimState m) Bit -> Int -> Word -> m ()
writeWord MVector s Bit
zs (forall a. Bits a => a -> a
mulWordSize Int
k )(Word
z0 forall a. Bits a => a -> a -> a
`xor`Word
z11 forall a. Bits a => a -> a -> a
`xor`Word
z10 forall a. Bits a => a -> a -> a
`xor`Word
z12 forall a. Bits a => a -> a -> a
`xor`Word
z2 )forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
U.unsafeFreezeMVector s Bit
zs wherelenXs :: Int
lenXs =forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
xs lenYs :: Int
lenYs =forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
ys lenZs :: Int
lenZs =Int
lenXs forall a. Num a => a -> a -> a
+Int
lenYs forall a. Num a => a -> a -> a
-Int
1m :: Int
m =(forall a. Ord a => a -> a -> a
minInt
lenXs Int
lenYs forall a. Num a => a -> a -> a
+Int
1)forall a. Bits a => a -> Int -> a
`unsafeShiftR`(Int
lgWordSize forall a. Num a => a -> a -> a
+Int
1)m' :: Int
m' =forall a. Bits a => a -> a
mulWordSize Int
m xs0 :: Vector Bit
xs0 =forall a. Unbox a => Int -> Int -> Vector a -> Vector a
U.unsafeSliceInt
0Int
m' Vector Bit
xs xs1 :: Vector Bit
xs1 =forall a. Unbox a => Int -> Int -> Vector a -> Vector a
U.unsafeSliceInt
m' (Int
lenXs forall a. Num a => a -> a -> a
-Int
m' )Vector Bit
xs ys0 :: Vector Bit
ys0 =forall a. Unbox a => Int -> Int -> Vector a -> Vector a
U.unsafeSliceInt
0Int
m' Vector Bit
ys ys1 :: Vector Bit
ys1 =forall a. Unbox a => Int -> Int -> Vector a -> Vector a
U.unsafeSliceInt
m' (Int
lenYs forall a. Num a => a -> a -> a
-Int
m' )Vector Bit
ys xs01 :: Vector Bit
xs01 =Vector Bit -> Vector Bit -> Vector Bit
xorBits Vector Bit
xs0 Vector Bit
xs1 ys01 :: Vector Bit
ys01 =Vector Bit -> Vector Bit -> Vector Bit
xorBits Vector Bit
ys0 Vector Bit
ys1 zs0 :: Vector Bit
zs0 =Vector Bit -> Vector Bit -> Vector Bit
karatsuba Vector Bit
xs0 Vector Bit
ys0 zs2 :: Vector Bit
zs2 =Vector Bit -> Vector Bit -> Vector Bit
karatsuba Vector Bit
xs1 Vector Bit
ys1 zs11 :: Vector Bit
zs11 =Vector Bit -> Vector Bit -> Vector Bit
karatsuba Vector Bit
xs01 Vector Bit
ys01 indexWord0 ::U.VectorBit ->Int->WordindexWord0 :: Vector Bit -> Int -> Word
indexWord0 Vector Bit
bv Int
i' |Int
i forall a. Ord a => a -> a -> Bool
<Int
0Bool -> Bool -> Bool
||Int
lenI forall a. Ord a => a -> a -> Bool
<=Int
0=Word
0|Int
lenI forall a. Ord a => a -> a -> Bool
>=Int
wordSize =Word
word |Bool
otherwise=Word
word forall a. Bits a => a -> a -> a
.&.Int -> Word
loMask Int
lenI wherei :: Int
i =forall a. Bits a => a -> a
mulWordSize Int
i' lenI :: Int
lenI =forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
bv forall a. Num a => a -> a -> a
-Int
i word :: Word
word =Vector Bit -> Int -> Word
indexWord Vector Bit
bv Int
i mulBits ::U.VectorBit ->U.VectorBit ->U.VectorBit mulBits :: Vector Bit -> Vector Bit -> Vector Bit
mulBits Vector Bit
xs Vector Bit
ys |Int
lenXs forall a. Eq a => a -> a -> Bool
==Int
0Bool -> Bool -> Bool
||Int
lenYs forall a. Eq a => a -> a -> Bool
==Int
0=forall a. Unbox a => Vector a
U.empty|Int
lenXs forall a. Ord a => a -> a -> Bool
>=Int
lenYs =Vector Bit -> Vector Bit -> Vector Bit
mulBits' Vector Bit
xs Vector Bit
ys |Bool
otherwise=Vector Bit -> Vector Bit -> Vector Bit
mulBits' Vector Bit
ys Vector Bit
xs wherelenXs :: Int
lenXs =forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
xs lenYs :: Int
lenYs =forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
ys mulBits' ::U.VectorBit ->U.VectorBit ->U.VectorBit mulBits' :: Vector Bit -> Vector Bit -> Vector Bit
mulBits' Vector Bit
xs Vector Bit
ys =forall a. (forall s. ST s a) -> a
runSTforall a b. (a -> b) -> a -> b
$doMVector s Bit
zs <-forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
MU.replicateInt
lenZs (Bool -> Bit
Bit Bool
False)forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_[Int
0..Int
lenYs forall a. Num a => a -> a -> a
-Int
1]forall a b. (a -> b) -> a -> b
$\Int
k ->forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when(Bit -> Bool
unBit (forall a. Unbox a => Vector a -> Int -> a
U.unsafeIndexVector Bit
ys Int
k ))forall a b. (a -> b) -> a -> b
$forall (m :: * -> *).
PrimMonad m =>
(forall a. Bits a => a -> a -> a)
-> Vector Bit -> MVector (PrimState m) Bit -> m ()
zipInPlace forall a. Bits a => a -> a -> a
xorVector Bit
xs (forall a s. Unbox a => Int -> Int -> MVector s a -> MVector s a
MU.unsafeSliceInt
k (Int
lenZs forall a. Num a => a -> a -> a
-Int
k )MVector s Bit
zs )forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
U.unsafeFreezeMVector s Bit
zs wherelenXs :: Int
lenXs =forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
xs lenYs :: Int
lenYs =forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
ys lenZs :: Int
lenZs =Int
lenXs forall a. Num a => a -> a -> a
+Int
lenYs forall a. Num a => a -> a -> a
-Int
1sqrBits ::U.VectorBit ->U.VectorBit sqrBits :: Vector Bit -> Vector Bit
sqrBits Vector Bit
xs =forall a. (forall s. ST s a) -> a
runSTforall a b. (a -> b) -> a -> b
$doletlenXs :: Int
lenXs =forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
xs MVector s Bit
zs <-forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
MU.replicate(forall a. Bits a => a -> a
mulWordSize (Int -> Int
nWords Int
lenXs forall a. Bits a => a -> Int -> a
`shiftL`Int
1))(Bool -> Bit
Bit Bool
False)forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_[Int
0,Int
wordSize ..Int
lenXs forall a. Num a => a -> a -> a
-Int
1]forall a b. (a -> b) -> a -> b
$\Int
i ->dolet(Word
z0 ,Word
z1 )=Word -> (Word, Word)
sparseBits (Vector Bit -> Int -> Word
indexWord Vector Bit
xs Int
i )forall (m :: * -> *).
PrimMonad m =>
MVector (PrimState m) Bit -> Int -> Word -> m ()
writeWord MVector s Bit
zs (Int
i forall a. Bits a => a -> Int -> a
`shiftL`Int
1)Word
z0 forall (m :: * -> *).
PrimMonad m =>
MVector (PrimState m) Bit -> Int -> Word -> m ()
writeWord MVector s Bit
zs ((Int
i forall a. Bits a => a -> Int -> a
`shiftL`Int
1)forall a. Num a => a -> a -> a
+Int
wordSize )Word
z1 forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
U.unsafeFreezeMVector s Bit
zs quotRemBits ::U.VectorBit ->U.VectorBit ->(U.VectorBit ,U.VectorBit )quotRemBits :: Vector Bit -> Vector Bit -> (Vector Bit, Vector Bit)
quotRemBits Vector Bit
xs Vector Bit
ys |forall a. Unbox a => Vector a -> Bool
U.nullVector Bit
ys =forall a e. Exception e => e -> a
throwArithException
DivideByZero|forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
xs forall a. Ord a => a -> a -> Bool
<forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
ys =(forall a. Unbox a => Vector a
U.empty,Vector Bit
xs )|Bool
otherwise=forall a. (forall s. ST s a) -> a
runSTforall a b. (a -> b) -> a -> b
$doletlenXs :: Int
lenXs =forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
xs lenYs :: Int
lenYs =forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
ys lenQs :: Int
lenQs =Int
lenXs forall a. Num a => a -> a -> a
-Int
lenYs forall a. Num a => a -> a -> a
+Int
1MVector s Bit
qs <-forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
MU.replicateInt
lenQs (Bool -> Bit
Bit Bool
False)MVector s Bit
rs <-forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
MU.replicateInt
lenXs (Bool -> Bit
Bit Bool
False)forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> Vector a -> m ()
U.unsafeCopyMVector s Bit
rs Vector Bit
xs forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_[Int
lenQs forall a. Num a => a -> a -> a
-Int
1,Int
lenQs forall a. Num a => a -> a -> a
-Int
2..Int
0]forall a b. (a -> b) -> a -> b
$\Int
i ->doBit Bool
r <-forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
MU.unsafeReadMVector s Bit
rs (Int
lenYs forall a. Num a => a -> a -> a
-Int
1forall a. Num a => a -> a -> a
+Int
i )forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
whenBool
r forall a b. (a -> b) -> a -> b
$doforall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> a -> m ()
MU.unsafeWriteMVector s Bit
qs Int
i (Bool -> Bit
Bit Bool
True)forall (m :: * -> *).
PrimMonad m =>
(forall a. Bits a => a -> a -> a)
-> Vector Bit -> MVector (PrimState m) Bit -> m ()
zipInPlace forall a. Bits a => a -> a -> a
xorVector Bit
ys (forall a s. Unbox a => Int -> MVector s a -> MVector s a
MU.dropInt
i MVector s Bit
rs )letrs' :: MVector s Bit
rs' =forall a s. Unbox a => Int -> Int -> MVector s a -> MVector s a
MU.unsafeSliceInt
0Int
lenYs MVector s Bit
rs (,)forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
U.unsafeFreezeMVector s Bit
qs forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*>forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
U.unsafeFreezeMVector s Bit
rs' dropWhileEnd ::U.VectorBit ->U.VectorBit dropWhileEnd :: Vector Bit -> Vector Bit
dropWhileEnd Vector Bit
xs =forall a. Unbox a => Int -> Int -> Vector a -> Vector a
U.unsafeSliceInt
0(Int -> Int
go (forall a. Unbox a => Vector a -> Int
U.lengthVector Bit
xs ))Vector Bit
xs wherego :: Int -> Int
go Int
n |Int
n forall a. Ord a => a -> a -> Bool
<Int
wordSize =Int
wordSize forall a. Num a => a -> a -> a
-forall b. FiniteBits b => b -> Int
countLeadingZeros(Vector Bit -> Int -> Word
indexWord Vector Bit
xs Int
0forall a. Bits a => a -> a -> a
.&.Int -> Word
loMask Int
n )|Bool
otherwise=caseVector Bit -> Int -> Word
indexWord Vector Bit
xs (Int
n forall a. Num a => a -> a -> a
-Int
wordSize )ofWord
0->Int -> Int
go (Int
n forall a. Num a => a -> a -> a
-Int
wordSize )Word
w ->Int
n forall a. Num a => a -> a -> a
-forall b. FiniteBits b => b -> Int
countLeadingZerosWord
w bitsToByteArray ::U.VectorBit ->ByteArray#bitsToByteArray :: Vector Bit -> ByteArray#
bitsToByteArray Vector Bit
xs =ByteArray#
arr whereys :: Vector Word
ys =ifforall a. Unbox a => Vector a -> Bool
U.nullVector Bit
xs thenforall a. Unbox a => a -> Vector a
U.singleton(Word
0::Word)elseVector Bit -> Vector Word
cloneToWords Vector Bit
xs !(P.VectorInt
_Int
_(ByteArrayByteArray#
arr ))=Vector Word -> Vector Word
toPrimVector Vector Word
ys 
#ifdef MIN_VERSION_ghc_bignum
#else
fromBigNat::BigNat->ByteArrayfromBigNat(BN#arr)=ByteArrayarrtoBigNat::ByteArray->BigNattoBigNat(ByteArrayarr)=BN#arr
#endif
-- | Execute the extended Euclidean algorithm.-- For polynomials @a@ and @b@, compute their unique greatest common divisor @g@-- and the unique coefficient polynomial @s@ satisfying \( a \cdot s + b \cdot t = g \).---- >>> :set -XBinaryLiterals-- >>> gcdExt 0b101 0b0101-- (0b101,0b0)-- >>> gcdExt 0b11 0b111-- (0b1,0b10)---- @since 1.0.2.0gcdExt ::F2Poly ->F2Poly ->(F2Poly ,F2Poly )gcdExt :: F2Poly -> F2Poly -> (F2Poly, F2Poly)
gcdExt =forall {t}. Integral t => t -> t -> t -> t -> (t, t)
go F2Poly
one F2Poly
zero wherego :: t -> t -> t -> t -> (t, t)
go t
s t
s' t
r t
r' |t
r' forall a. Eq a => a -> a -> Bool
==t
0=(t
r ,t
s )|Bool
otherwise=caseforall a. Integral a => a -> a -> (a, a)
quotRemt
r t
r' of(t
q ,t
r'' )->t -> t -> t -> t -> (t, t)
go t
s' (t
s forall a. Num a => a -> a -> a
-t
q forall a. Num a => a -> a -> a
*t
s' )t
r' t
r''