// Copyright (c) 2016 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 (
	
	
)

// A Scalar is an integer modulo
//
//	l = 2^252 + 27742317777372353535851937790883648493
//
// which is the prime order of the edwards25519 group.
//
// This type works similarly to math/big.Int, and all arguments and
// receivers are allowed to alias.
//
// The zero value is a valid zero element.
type Scalar struct {
	// s is the scalar in the Montgomery domain, in the format of the
	// fiat-crypto implementation.
	s fiatScalarMontgomeryDomainFieldElement
}

// The field implementation in scalar_fiat.go is generated by the fiat-crypto
// project (https://github.com/mit-plv/fiat-crypto) at version v0.0.9 (23d2dbc)
// from a formally verified model.
//
// fiat-crypto code comes under the following license.
//
//     Copyright (c) 2015-2020 The fiat-crypto Authors. All rights reserved.
//
//     Redistribution and use in source and binary forms, with or without
//     modification, are permitted provided that the following conditions are
//     met:
//
//         1. Redistributions of source code must retain the above copyright
//         notice, this list of conditions and the following disclaimer.
//
//     THIS SOFTWARE IS PROVIDED BY the fiat-crypto authors "AS IS"
//     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
//     THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
//     PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL Berkeley Software Design,
//     Inc. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
//     EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
//     PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
//     PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
//     LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
//     NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
//     SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//

// NewScalar returns a new zero Scalar.
func () *Scalar {
	return &Scalar{}
}

// MultiplyAdd sets s = x * y + z mod l, and returns s. It is equivalent to
// using Multiply and then Add.
func ( *Scalar) (, ,  *Scalar) *Scalar {
	// Make a copy of z in case it aliases s.
	 := new(Scalar).Set()
	return .Multiply(, ).Add(, )
}

// Add sets s = x + y mod l, and returns s.
func ( *Scalar) (,  *Scalar) *Scalar {
	// s = 1 * x + y mod l
	fiatScalarAdd(&.s, &.s, &.s)
	return 
}

// Subtract sets s = x - y mod l, and returns s.
func ( *Scalar) (,  *Scalar) *Scalar {
	// s = -1 * y + x mod l
	fiatScalarSub(&.s, &.s, &.s)
	return 
}

// Negate sets s = -x mod l, and returns s.
func ( *Scalar) ( *Scalar) *Scalar {
	// s = -1 * x + 0 mod l
	fiatScalarOpp(&.s, &.s)
	return 
}

// Multiply sets s = x * y mod l, and returns s.
func ( *Scalar) (,  *Scalar) *Scalar {
	// s = x * y + 0 mod l
	fiatScalarMul(&.s, &.s, &.s)
	return 
}

// Set sets s = x, and returns s.
func ( *Scalar) ( *Scalar) *Scalar {
	* = *
	return 
}

// SetUniformBytes sets s = x mod l, where x is a 64-byte little-endian integer.
// If x is not of the right length, SetUniformBytes returns nil and an error,
// and the receiver is unchanged.
//
// SetUniformBytes can be used to set s to a uniformly distributed value given
// 64 uniformly distributed random bytes.
func ( *Scalar) ( []byte) (*Scalar, error) {
	if len() != 64 {
		return nil, errors.New("edwards25519: invalid SetUniformBytes input length")
	}

	// We have a value x of 512 bits, but our fiatScalarFromBytes function
	// expects an input lower than l, which is a little over 252 bits.
	//
	// Instead of writing a reduction function that operates on wider inputs, we
	// can interpret x as the sum of three shorter values a, b, and c.
	//
	//    x = a + b * 2^168 + c * 2^336  mod l
	//
	// We then precompute 2^168 and 2^336 modulo l, and perform the reduction
	// with two multiplications and two additions.

	.setShortBytes([:21])
	 := new(Scalar).setShortBytes([21:42])
	.Add(, .Multiply(, scalarTwo168))
	.setShortBytes([42:])
	.Add(, .Multiply(, scalarTwo336))

	return , nil
}

// scalarTwo168 and scalarTwo336 are 2^168 and 2^336 modulo l, encoded as a
// fiatScalarMontgomeryDomainFieldElement, which is a little-endian 4-limb value
// in the 2^256 Montgomery domain.
var scalarTwo168 = &Scalar{s: [4]uint64{0x5b8ab432eac74798, 0x38afddd6de59d5d7,
	0xa2c131b399411b7c, 0x6329a7ed9ce5a30}}
var scalarTwo336 = &Scalar{s: [4]uint64{0xbd3d108e2b35ecc5, 0x5c3a3718bdf9c90b,
	0x63aa97a331b4f2ee, 0x3d217f5be65cb5c}}

// setShortBytes sets s = x mod l, where x is a little-endian integer shorter
// than 32 bytes.
func ( *Scalar) ( []byte) *Scalar {
	if len() >= 32 {
		panic("edwards25519: internal error: setShortBytes called with a long string")
	}
	var  [32]byte
	copy([:], )
	fiatScalarFromBytes((*[4]uint64)(&.s), &)
	fiatScalarToMontgomery(&.s, (*fiatScalarNonMontgomeryDomainFieldElement)(&.s))
	return 
}

// SetCanonicalBytes sets s = x, where x is a 32-byte little-endian encoding of
// s, and returns s. If x is not a canonical encoding of s, SetCanonicalBytes
// returns nil and an error, and the receiver is unchanged.
func ( *Scalar) ( []byte) (*Scalar, error) {
	if len() != 32 {
		return nil, errors.New("invalid scalar length")
	}
	if !isReduced() {
		return nil, errors.New("invalid scalar encoding")
	}

	fiatScalarFromBytes((*[4]uint64)(&.s), (*[32]byte)())
	fiatScalarToMontgomery(&.s, (*fiatScalarNonMontgomeryDomainFieldElement)(&.s))

	return , nil
}

// scalarMinusOneBytes is l - 1 in little endian.
var scalarMinusOneBytes = [32]byte{236, 211, 245, 92, 26, 99, 18, 88, 214, 156, 247, 162, 222, 249, 222, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16}

// isReduced returns whether the given scalar in 32-byte little endian encoded
// form is reduced modulo l.
func ( []byte) bool {
	if len() != 32 {
		return false
	}

	for  := len() - 1;  >= 0; -- {
		switch {
		case [] > scalarMinusOneBytes[]:
			return false
		case [] < scalarMinusOneBytes[]:
			return true
		}
	}
	return true
}

// SetBytesWithClamping applies the buffer pruning described in RFC 8032,
// Section 5.1.5 (also known as clamping) and sets s to the result. The input
// must be 32 bytes, and it is not modified. If x is not of the right length,
// SetBytesWithClamping returns nil and an error, and the receiver is unchanged.
//
// Note that since Scalar values are always reduced modulo the prime order of
// the curve, the resulting value will not preserve any of the cofactor-clearing
// properties that clamping is meant to provide. It will however work as
// expected as long as it is applied to points on the prime order subgroup, like
// in Ed25519. In fact, it is lost to history why RFC 8032 adopted the
// irrelevant RFC 7748 clamping, but it is now required for compatibility.
func ( *Scalar) ( []byte) (*Scalar, error) {
	// The description above omits the purpose of the high bits of the clamping
	// for brevity, but those are also lost to reductions, and are also
	// irrelevant to edwards25519 as they protect against a specific
	// implementation bug that was once observed in a generic Montgomery ladder.
	if len() != 32 {
		return nil, errors.New("edwards25519: invalid SetBytesWithClamping input length")
	}

	// We need to use the wide reduction from SetUniformBytes, since clamping
	// sets the 2^254 bit, making the value higher than the order.
	var  [64]byte
	copy([:], [:])
	[0] &= 248
	[31] &= 63
	[31] |= 64
	return .SetUniformBytes([:])
}

// Bytes returns the canonical 32-byte little-endian encoding of s.
func ( *Scalar) () []byte {
	// This function is outlined to make the allocations inline in the caller
	// rather than happen on the heap.
	var  [32]byte
	return .bytes(&)
}

func ( *Scalar) ( *[32]byte) []byte {
	var  fiatScalarNonMontgomeryDomainFieldElement
	fiatScalarFromMontgomery(&, &.s)
	fiatScalarToBytes(, (*[4]uint64)(&))
	return [:]
}

// Equal returns 1 if s and t are equal, and 0 otherwise.
func ( *Scalar) ( *Scalar) int {
	var  fiatScalarMontgomeryDomainFieldElement
	fiatScalarSub(&, &.s, &.s)
	var  uint64
	fiatScalarNonzero(&, (*[4]uint64)(&))
	 |=  >> 32
	 |=  >> 16
	 |=  >> 8
	 |=  >> 4
	 |=  >> 2
	 |=  >> 1
	return int(^) & 1
}

// nonAdjacentForm computes a width-w non-adjacent form for this scalar.
//
// w must be between 2 and 8, or nonAdjacentForm will panic.
func ( *Scalar) ( uint) [256]int8 {
	// This implementation is adapted from the one
	// in curve25519-dalek and is documented there:
	// https://github.com/dalek-cryptography/curve25519-dalek/blob/f630041af28e9a405255f98a8a93adca18e4315b/src/scalar.rs#L800-L871
	 := .Bytes()
	if [31] > 127 {
		panic("scalar has high bit set illegally")
	}
	if  < 2 {
		panic("w must be at least 2 by the definition of NAF")
	} else if  > 8 {
		panic("NAF digits must fit in int8")
	}

	var  [256]int8
	var  [5]uint64

	for  := 0;  < 4; ++ {
		[] = binary.LittleEndian.Uint64([*8:])
	}

	 := uint64(1 << )
	 := uint64( - 1)

	 := uint(0)
	 := uint64(0)
	for  < 256 {
		 :=  / 64
		 :=  % 64
		var  uint64
		if  < 64- {
			// This window's bits are contained in a single u64
			 = [] >> 
		} else {
			// Combine the current 64 bits with bits from the next 64
			 = ([] >> ) | ([1+] << (64 - ))
		}

		// Add carry into the current window
		 :=  + ( & )

		if &1 == 0 {
			// If the window value is even, preserve the carry and continue.
			// Why is the carry preserved?
			// If carry == 0 and window & 1 == 0,
			//    then the next carry should be 0
			// If carry == 1 and window & 1 == 0,
			//    then bit_buf & 1 == 1 so the next carry should be 1
			 += 1
			continue
		}

		if  < /2 {
			 = 0
			[] = int8()
		} else {
			 = 1
			[] = int8() - int8()
		}

		 += 
	}
	return 
}

func ( *Scalar) () [64]int8 {
	 := .Bytes()
	if [31] > 127 {
		panic("scalar has high bit set illegally")
	}

	var  [64]int8

	// Compute unsigned radix-16 digits:
	for  := 0;  < 32; ++ {
		[2*] = int8([] & 15)
		[2*+1] = int8(([] >> 4) & 15)
	}

	// Recenter coefficients:
	for  := 0;  < 63; ++ {
		 := ([] + 8) >> 4
		[] -=  << 4
		[+1] += 
	}

	return 
}