// Copyright (c) 2019 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package edwards25519

import 

// basepointTable is a set of 32 affineLookupTables, where table i is generated
// from 256i * basepoint. It is precomputed the first time it's used.
func basepointTable() *[32]affineLookupTable {
	basepointTablePrecomp.initOnce.Do(func() {
		 := NewGeneratorPoint()
		for  := 0;  < 32; ++ {
			basepointTablePrecomp.table[].FromP3()
			for  := 0;  < 8; ++ {
				.Add(, )
			}
		}
	})
	return &basepointTablePrecomp.table
}

var basepointTablePrecomp struct {
	table    [32]affineLookupTable
	initOnce sync.Once
}

// ScalarBaseMult sets v = x * B, where B is the canonical generator, and
// returns v.
//
// The scalar multiplication is done in constant time.
func ( *Point) ( *Scalar) *Point {
	 := basepointTable()

	// Write x = sum(x_i * 16^i) so  x*B = sum( B*x_i*16^i )
	// as described in the Ed25519 paper
	//
	// Group even and odd coefficients
	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
	//         + x_1*16^1*B + x_3*16^3*B + ... + x_63*16^63*B
	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
	//    + 16*( x_1*16^0*B + x_3*16^2*B + ... + x_63*16^62*B)
	//
	// We use a lookup table for each i to get x_i*16^(2*i)*B
	// and do four doublings to multiply by 16.
	 := .signedRadix16()

	 := &affineCached{}
	 := &projP1xP1{}
	 := &projP2{}

	// Accumulate the odd components first
	.Set(NewIdentityPoint())
	for  := 1;  < 64;  += 2 {
		[/2].SelectInto(, [])
		.AddAffine(, )
		.fromP1xP1()
	}

	// Multiply by 16
	.FromP3()       // tmp2 =    v in P2 coords
	.Double()    // tmp1 =  2*v in P1xP1 coords
	.FromP1xP1() // tmp2 =  2*v in P2 coords
	.Double()    // tmp1 =  4*v in P1xP1 coords
	.FromP1xP1() // tmp2 =  4*v in P2 coords
	.Double()    // tmp1 =  8*v in P1xP1 coords
	.FromP1xP1() // tmp2 =  8*v in P2 coords
	.Double()    // tmp1 = 16*v in P1xP1 coords
	.fromP1xP1()    // now v = 16*(odd components)

	// Accumulate the even components
	for  := 0;  < 64;  += 2 {
		[/2].SelectInto(, [])
		.AddAffine(, )
		.fromP1xP1()
	}

	return 
}

// ScalarMult sets v = x * q, and returns v.
//
// The scalar multiplication is done in constant time.
func ( *Point) ( *Scalar,  *Point) *Point {
	checkInitialized()

	var  projLookupTable
	.FromP3()

	// Write x = sum(x_i * 16^i)
	// so  x*Q = sum( Q*x_i*16^i )
	//         = Q*x_0 + 16*(Q*x_1 + 16*( ... + Q*x_63) ... )
	//           <------compute inside out---------
	//
	// We use the lookup table to get the x_i*Q values
	// and do four doublings to compute 16*Q
	 := .signedRadix16()

	// Unwrap first loop iteration to save computing 16*identity
	 := &projCached{}
	 := &projP1xP1{}
	 := &projP2{}
	.SelectInto(, [63])

	.Set(NewIdentityPoint())
	.Add(, ) // tmp1 = x_63*Q in P1xP1 coords
	for  := 62;  >= 0; -- {
		.FromP1xP1() // tmp2 =    (prev) in P2 coords
		.Double()    // tmp1 =  2*(prev) in P1xP1 coords
		.FromP1xP1() // tmp2 =  2*(prev) in P2 coords
		.Double()    // tmp1 =  4*(prev) in P1xP1 coords
		.FromP1xP1() // tmp2 =  4*(prev) in P2 coords
		.Double()    // tmp1 =  8*(prev) in P1xP1 coords
		.FromP1xP1() // tmp2 =  8*(prev) in P2 coords
		.Double()    // tmp1 = 16*(prev) in P1xP1 coords
		.fromP1xP1()    //    v = 16*(prev) in P3 coords
		.SelectInto(, [])
		.Add(, ) // tmp1 = x_i*Q + 16*(prev) in P1xP1 coords
	}
	.fromP1xP1()
	return 
}

// basepointNafTable is the nafLookupTable8 for the basepoint.
// It is precomputed the first time it's used.
func basepointNafTable() *nafLookupTable8 {
	basepointNafTablePrecomp.initOnce.Do(func() {
		basepointNafTablePrecomp.table.FromP3(NewGeneratorPoint())
	})
	return &basepointNafTablePrecomp.table
}

var basepointNafTablePrecomp struct {
	table    nafLookupTable8
	initOnce sync.Once
}

// VarTimeDoubleScalarBaseMult sets v = a * A + b * B, where B is the canonical
// generator, and returns v.
//
// Execution time depends on the inputs.
func ( *Point) ( *Scalar,  *Point,  *Scalar) *Point {
	checkInitialized()

	// Similarly to the single variable-base approach, we compute
	// digits and use them with a lookup table.  However, because
	// we are allowed to do variable-time operations, we don't
	// need constant-time lookups or constant-time digit
	// computations.
	//
	// So we use a non-adjacent form of some width w instead of
	// radix 16.  This is like a binary representation (one digit
	// for each binary place) but we allow the digits to grow in
	// magnitude up to 2^{w-1} so that the nonzero digits are as
	// sparse as possible.  Intuitively, this "condenses" the
	// "mass" of the scalar onto sparse coefficients (meaning
	// fewer additions).

	 := basepointNafTable()
	var  nafLookupTable5
	.FromP3()
	// Because the basepoint is fixed, we can use a wider NAF
	// corresponding to a bigger table.
	 := .nonAdjacentForm(5)
	 := .nonAdjacentForm(8)

	// Find the first nonzero coefficient.
	 := 255
	for  := ;  >= 0; -- {
		if [] != 0 || [] != 0 {
			break
		}
	}

	 := &projCached{}
	 := &affineCached{}
	 := &projP1xP1{}
	 := &projP2{}
	.Zero()

	// Move from high to low bits, doubling the accumulator
	// at each iteration and checking whether there is a nonzero
	// coefficient to look up a multiple of.
	for ;  >= 0; -- {
		.Double()

		// Only update v if we have a nonzero coeff to add in.
		if [] > 0 {
			.fromP1xP1()
			.SelectInto(, [])
			.Add(, )
		} else if [] < 0 {
			.fromP1xP1()
			.SelectInto(, -[])
			.Sub(, )
		}

		if [] > 0 {
			.fromP1xP1()
			.SelectInto(, [])
			.AddAffine(, )
		} else if [] < 0 {
			.fromP1xP1()
			.SelectInto(, -[])
			.SubAffine(, )
		}

		.FromP1xP1()
	}

	.fromP2()
	return 
}