// Code generated by go generate; DO NOT EDIT.
// This file was generated by robots.

package {{.PACKAGE}}

import (
	"github.com/cloudflare/circl/dh/sidh/internal/common"
)

// Montgomery multiplication. Input values must be already
// in Montgomery domain.
func mulP(dest, lhs, rhs *common.Fp) {
	var ab common.FpX2
	mul{{.FIELD}}(&ab, lhs, rhs) // = a*b*R*R
	rdc{{.FIELD}}(dest, &ab)     // = a*b*R mod p
}

// Set dest = x^((p-3)/4).  If x is square, this is 1/sqrt(x).
// Uses variation of sliding-window algorithm from with window size
// of 5 and least to most significant bit sliding (left-to-right)
// See HAC 14.85 for general description.
//
// Allowed to overlap x with dest.
// All values in Montgomery domains
// Set dest = x^(2^k), for k >= 1, by repeated squarings.
func p34(dest, x *common.Fp) {
	var lookup [16]common.Fp

	// This performs sum(powStrategy) + 1 squarings and len(lookup) + len(mulStrategy)
	// multiplications.
	powStrategy := {{.P34_POW_STRATEGY}}
	mulStrategy := {{.P34_MUL_STRATEGY}}
	initialMul := uint8({{.P34_INITIAL_MUL}})

	// Precompute lookup table of odd multiples of x for window
	// size k=5.
	var xx common.Fp
	mulP(&xx, x, x)
	lookup[0] = *x
	for i := 1; i < 16; i++ {
		mulP(&lookup[i], &lookup[i-1], &xx)
	}

	// Now lookup = {x, x^3, x^5, ... }
	// so that lookup[i] = x^{2*i + 1}
	// so that lookup[k/2] = x^k, for odd k
	*dest = lookup[initialMul]
	for i := uint8(0); i < uint8(len(powStrategy)); i++ {
		mulP(dest, dest, dest)
		for j := uint8(1); j < powStrategy[i]; j++ {
			mulP(dest, dest, dest)
		}
		mulP(dest, dest, &lookup[mulStrategy[i]])
	}
}

func add(dest, lhs, rhs *common.Fp2) {
	add{{.FIELD}}(&dest.A, &lhs.A, &rhs.A)
	add{{.FIELD}}(&dest.B, &lhs.B, &rhs.B)
}

func sub(dest, lhs, rhs *common.Fp2) {
	sub{{.FIELD}}(&dest.A, &lhs.A, &rhs.A)
	sub{{.FIELD}}(&dest.B, &lhs.B, &rhs.B)
}

func mul(dest, lhs, rhs *common.Fp2) {
	var bMinA, cMinD common.Fp
	var ac, bd common.FpX2
	var adPlusBc common.FpX2
	var acMinBd common.FpX2

	// Let (a,b,c,d) = (lhs.a,lhs.b,rhs.a,rhs.b).
	//
	// (a + bi)*(c + di) = (a*c - b*d) + (a*d + b*c)i
	//
	// Use Karatsuba's trick: note that
	//
	// (b - a)*(c - d) = (b*c + a*d) - a*c - b*d
	//
	// so (a*d + b*c) = (b-a)*(c-d) + a*c + b*d.
	sub{{.FIELD}}(&bMinA, &lhs.B, &lhs.A)    // = (b-a)*R
	sub{{.FIELD}}(&cMinD, &rhs.A, &rhs.B)    // = (c-d)*R
	mul{{.FIELD}}(&ac, &lhs.A, &rhs.A)       // = a*c*R*R
	mul{{.FIELD}}(&bd, &lhs.B, &rhs.B)       // = b*d*R*R
	mul{{.FIELD}}(&adPlusBc, &bMinA, &cMinD) // = (b-a)*(c-d)*R*R
	adl{{.FIELD}}(&adPlusBc, &adPlusBc, &ac) // = ((b-a)*(c-d) + a*c)*R*R
	adl{{.FIELD}}(&adPlusBc, &adPlusBc, &bd) // = ((b-a)*(c-d) + a*c + b*d)*R*R
	rdc{{.FIELD}}(&dest.B, &adPlusBc)        // = (a*d + b*c)*R mod p
	sul{{.FIELD}}(&acMinBd, &ac, &bd)        // = (a*c - b*d)*R*R
	rdc{{.FIELD}}(&dest.A, &acMinBd)         // = (a*c - b*d)*R mod p
}

// Set dest = 1/x
//
// Allowed to overlap dest with x.
//
// Returns dest to allow chaining operations.
func inv(dest, x *common.Fp2) {
	var e1, e2 common.FpX2
	var f1, f2 common.Fp

	// We want to compute
	//
	//    1          1     (a - bi)	    (a - bi)
	// -------- = -------- -------- = -----------
	// (a + bi)   (a + bi) (a - bi)   (a^2 + b^2)
	//
	// Letting c = 1/(a^2 + b^2), this is
	//
	// 1/(a+bi) = a*c - b*ci.

	mul{{.FIELD}}(&e1, &x.A, &x.A) // = a*a*R*R
	mul{{.FIELD}}(&e2, &x.B, &x.B) // = b*b*R*R
	adl{{.FIELD}}(&e1, &e1, &e2)   // = (a^2 + b^2)*R*R
	rdc{{.FIELD}}(&f1, &e1)        // = (a^2 + b^2)*R mod p
	// Now f1 = a^2 + b^2

	mulP(&f2, &f1, &f1)
	p34(&f2, &f2)
	mulP(&f2, &f2, &f2)
	mulP(&f2, &f2, &f1)

	mul{{.FIELD}}(&e1, &x.A, &f2)
	rdc{{.FIELD}}(&dest.A, &e1)

	sub{{.FIELD}}(&f1, &common.Fp{}, &x.B)
	mul{{.FIELD}}(&e1, &f1, &f2)
	rdc{{.FIELD}}(&dest.B, &e1)
}

func sqr(dest, x *common.Fp2) {
	var a2, aPlusB, aMinusB common.Fp
	var a2MinB2, ab2 common.FpX2

	a := &x.A
	b := &x.B

	// (a + bi)*(a + bi) = (a^2 - b^2) + 2abi.
	add{{.FIELD}}(&a2, a, a)                   // = a*R + a*R = 2*a*R
	add{{.FIELD}}(&aPlusB, a, b)               // = a*R + b*R = (a+b)*R
	sub{{.FIELD}}(&aMinusB, a, b)              // = a*R - b*R = (a-b)*R
	mul{{.FIELD}}(&a2MinB2, &aPlusB, &aMinusB) // = (a+b)*(a-b)*R*R = (a^2 - b^2)*R*R
	mul{{.FIELD}}(&ab2, &a2, b)                // = 2*a*b*R*R
	rdc{{.FIELD}}(&dest.A, &a2MinB2)           // = (a^2 - b^2)*R mod p
	rdc{{.FIELD}}(&dest.B, &ab2)               // = 2*a*b*R mod p
}

// In case choice == 1, performs following swap in constant time:
//
// xPx <-> xQx
// xPz <-> xQz
//
// Otherwise returns xPx, xPz, xQx, xQz unchanged
func cswap(xPx, xPz, xQx, xQz *common.Fp2, choice uint8) {
	cswap{{.FIELD}}(&xPx.A, &xQx.A, choice)
	cswap{{.FIELD}}(&xPx.B, &xQx.B, choice)
	cswap{{.FIELD}}(&xPz.A, &xQz.A, choice)
	cswap{{.FIELD}}(&xPz.B, &xQz.B, choice)
}

// In case choice == 1, performs following moves in constant time:
//
// xPx <- xQx
// xPz <- xQz
//
// Otherwise returns xPx, xPz, xQx, xQz unchanged
func cmov(xPx, xPz, xQx, xQz *common.Fp2, choice uint8) {
	cmov{{.FIELD}}(&xPx.A, &xQx.A, choice)
	cmov{{.FIELD}}(&xPx.B, &xQx.B, choice)
	cmov{{.FIELD}}(&xPz.A, &xQz.A, choice)
	cmov{{.FIELD}}(&xPz.B, &xQz.B, choice)
}

func isZero(x *common.Fp2) uint8 {
	r64 := uint64(0)
	for i := 0; i < FpWords; i++ {
		r64 |= x.A[i] | x.B[i]
	}
	r := uint8(0)
	for i := uint64(0); i < 64; i++ {
		r |= uint8((r64 >> i) & 0x1)
	}
	return 1 - r
}

// Converts in.A and in.B to Montgomery domain and stores
// in 'out'
// out.A = in.A * R mod p
// out.B = in.B * R mod p
// Performs v = v*R^2*R^(-1) mod p, for both in.A and in.B
func ToMontgomery(out, in *common.Fp2) {
	var aRR common.FpX2

	// a*R*R
	mul{{.FIELD}}(&aRR, &in.A, &{{.FIELD}}R2)
	// a*R mod p
	rdc{{.FIELD}}(&out.A, &aRR)
	mul{{.FIELD}}(&aRR, &in.B, &{{.FIELD}}R2)
	rdc{{.FIELD}}(&out.B, &aRR)
}

// Converts in.A and in.B from Montgomery domain and stores
// in 'out'
// out.A = in.A mod p
// out.B = in.B mod p
//
// After returning from the call 'in' is not modified.
func FromMontgomery(out, in *common.Fp2) {
	var aR common.FpX2

	// convert from montgomery domain
	copy(aR[:], in.A[:])
	rdc{{.FIELD}}(&out.A, &aR) // = a mod p in [0, 2p)
	mod{{.FIELD}}(&out.A)      // = a mod p in [0, p)
	for i := range aR {
		aR[i] = 0
	}
	copy(aR[:], in.B[:])
	rdc{{.FIELD}}(&out.B, &aR)
	mod{{.FIELD}}(&out.B)
}