vector.go

// Copyright 2020-2025 Consensys Software Inc.
// Licensed under the Apache License, Version 2.0. See the LICENSE file for details.

// Code generated by consensys/gnark-crypto DO NOT EDIT

package fp

import (
	"bytes"
	"encoding/binary"
	"errors"
	"fmt"
	"io"
	"math/bits"
	"runtime"
	"slices"
	"strings"
	"sync"
	"sync/atomic"
	"unsafe"
)

// Vector represents a slice of Element.
//
// It implements the following interfaces:
//   - Stringer
//   - io.WriterTo
//   - io.ReaderFrom
//   - encoding.BinaryMarshaler
//   - encoding.BinaryUnmarshaler
//   - sort.Interface
type Vector []Element

// MarshalBinary implements encoding.BinaryMarshaler
func (vector *Vector) MarshalBinary() (data []byte, err error) {
	var buf bytes.Buffer

	if _, err = vector.WriteTo(&buf); err != nil {
		return
	}
	return buf.Bytes(), nil
}

// UnmarshalBinary implements encoding.BinaryUnmarshaler
func (vector *Vector) UnmarshalBinary(data []byte) error {
	r := bytes.NewReader(data)
	_, err := vector.ReadFrom(r)
	return err
}

// WriteTo implements io.WriterTo and writes a vector of big endian encoded Element.
// Length of the vector is encoded as a uint32 on the first 4 bytes.
func (vector *Vector) WriteTo(w io.Writer) (int64, error) {
	// encode slice length
	if err := binary.Write(w, binary.BigEndian, uint32(len(*vector))); err != nil {
		return 0, err
	}

	n := int64(4)

	var buf [Bytes]byte
	for i := 0; i < len(*vector); i++ {
		BigEndian.PutElement(&buf, (*vector)[i])
		m, err := w.Write(buf[:])
		n += int64(m)
		if err != nil {
			return n, err
		}
	}
	return n, nil
}

// AsyncReadFrom implements an asynchronous version of [Vector.ReadFrom]. It
// reads the reader r in full and then performs the validation and conversion to
// Montgomery form separately in a goroutine. Any error encountered during
// reading is returned directly, while errors encountered during
// validation/conversion are sent on the returned channel. Thus the caller must
// wait on the channel to ensure the vector is ready to use. The method
// additionally returns the number of bytes read from r.
//
// The reader can contain more bytes than needed to decode the vector, in which
// case the extra bytes are ignored. In that case the reader is not seeked nor
// read further.
//
// The method allocates sufficiently large slice to store the vector. If the
// current slice fits the vector, it is reused, otherwise the slice is grown to
// fit the vector.
//
// The serialized encoding is as follows:
//   - first 4 bytes: length of the vector as a big-endian uint32
//   - for each element of the vector, [Bytes] bytes representing the element in
//     big-endian encoding.
func (vector *Vector) AsyncReadFrom(r io.Reader) (int64, error, chan error) { // nolint ST1008
	chErr := make(chan error, 1)
	var buf [Bytes]byte
	if read, err := io.ReadFull(r, buf[:4]); err != nil {
		close(chErr)
		return int64(read), err, chErr
	}
	headerSliceLen := uint64(binary.BigEndian.Uint32(buf[:4]))

	// to avoid allocating too large slice when the header is tampered, we limit
	// the maximum allocation. We set the target to 4GB. This incurs a performance
	// hit when reading very large slices, but protects against OOM.
	targetSize := uint64(1 << 32) // 4GB
	if bits.UintSize == 32 {
		// reduce target size to 1GB on 32 bits architectures
		targetSize = uint64(1 << 30) // 1GB
	}
	maxAllocateSliceLength := targetSize / uint64(Bytes)

	totalRead := int64(4)
	*vector = (*vector)[:0]
	if headerSliceLen == 0 {
		// if the vector was nil previously even by reslicing we have a nil vector.
		// but we want to have an empty slice to indicate that the vector has zero length.
		if *vector == nil {
			*vector = []Element{}
		}
		// we return already here to avoid launching a goroutine doing nothing below
		close(chErr)
		return totalRead, nil, chErr
	}

	for i := uint64(0); i < headerSliceLen; i += maxAllocateSliceLength {
		if len(*vector) <= int(i) {
			(*vector) = append(*vector, make([]Element, int(min(headerSliceLen-i, maxAllocateSliceLength)))...)
		}
		bSlice := unsafe.Slice((*byte)(unsafe.Pointer(&(*vector)[i])), int(min(headerSliceLen-i, maxAllocateSliceLength))*Bytes)
		read, err := io.ReadFull(r, bSlice)
		totalRead += int64(read)
		if errors.Is(err, io.ErrUnexpectedEOF) {
			close(chErr)
			return totalRead, fmt.Errorf("less data than expected: read %d elements, expected %d", i+uint64(read)/Bytes, headerSliceLen), chErr
		}
		if err != nil {
			close(chErr)
			return totalRead, err, chErr
		}
	}

	bSlice := unsafe.Slice((*byte)(unsafe.Pointer(&(*vector)[0])), int(headerSliceLen)*Bytes)
	go func() {
		var cptErrors uint64
		// process the elements in parallel
		execute(int(headerSliceLen), func(start, end int) {

			var z Element
			for i := start; i < end; i++ {
				// we have to set vector[i]
				bstart := i * Bytes
				bend := bstart + Bytes
				b := bSlice[bstart:bend]
				z[0] = binary.BigEndian.Uint64(b[40:48])
				z[1] = binary.BigEndian.Uint64(b[32:40])
				z[2] = binary.BigEndian.Uint64(b[24:32])
				z[3] = binary.BigEndian.Uint64(b[16:24])
				z[4] = binary.BigEndian.Uint64(b[8:16])
				z[5] = binary.BigEndian.Uint64(b[0:8])

				if !z.smallerThanModulus() {
					atomic.AddUint64(&cptErrors, 1)
					return
				}
				z.toMont()
				(*vector)[i] = z
			}
		})

		if cptErrors > 0 {
			chErr <- fmt.Errorf("async read: %d elements failed validation", cptErrors)
		}
		close(chErr)
	}()
	return totalRead, nil, chErr
}

// ReadFrom reads the vector from the reader r. It returns the number of bytes
// read and an error, if any. The errors can be:
//   - an error while reading from r (including [io.EOF] i.e. not enough bytes in r);
//   - when decoding the bytes into elements.
//
// The reader can contain more bytes than needed to decode the vector, in which case
// the extra bytes are ignored. In that case the reader is not seeked nor read further.
//
// The method allocates sufficiently large slice to store the vector. If the current slice fits
// the vector, it is reused, otherwise the slice is grown to fit the vector.
//
// The serialized encoding is as follows:
//   - first 4 bytes: length of the vector as a big-endian uint32
//   - for each element of the vector, [Bytes] bytes representing the element in big-endian encoding.
//
// The method implements [io.ReaderFrom] interface.
func (vector *Vector) ReadFrom(r io.Reader) (int64, error) {
	var buf [Bytes]byte
	if read, err := io.ReadFull(r, buf[:4]); err != nil {
		return int64(read), err
	}
	headerSliceLen := uint64(binary.BigEndian.Uint32(buf[:4]))

	// to avoid allocating too large slice when the header is tampered, we limit
	// the maximum allocation. We set the target to 4GB. This incurs a performance
	// hit when reading very large slices, but protects against OOM.
	targetSize := uint64(1 << 32) // 4GB
	if bits.UintSize == 32 {
		// reduce target size to 1GB on 32 bits architectures
		targetSize = uint64(1 << 30) // 1GB
	}
	maxAllocateSliceLength := targetSize / uint64(Bytes)

	totalRead := int64(4) // include already the header length
	*vector = (*vector)[:0]
	// if the vector was nil previously even by reslicing we have a nil vector. But we want
	// to have an empty slice to indicate that the vector has zero length. When headerSliceLen == 0
	// we handle this edge case after reading the header as the loop body below is skipped.
	if headerSliceLen == 0 && *vector == nil {
		*vector = []Element{}
	}

	for i := uint64(0); i < headerSliceLen; i++ {
		read, err := io.ReadFull(r, buf[:])
		totalRead += int64(read)
		if errors.Is(err, io.EOF) {
			return totalRead, fmt.Errorf("less data than expected: read %d elements, expected %d", i, headerSliceLen)
		}
		if err != nil {
			return totalRead, fmt.Errorf("error reading element %d: %w", i, err)
		}
		if uint64(cap(*vector)) <= i {
			(*vector) = slices.Grow(*vector, int(min(headerSliceLen-i, maxAllocateSliceLength)))
		}
		el, err := BigEndian.Element(&buf)
		if err != nil {
			return totalRead, fmt.Errorf("error decoding element %d: %w", i, err)
		}
		*vector = append(*vector, el)
	}

	return totalRead, nil
}

// String implements fmt.Stringer interface
func (vector Vector) String() string {
	var sbb strings.Builder
	sbb.WriteByte('[')
	for i := 0; i < len(vector); i++ {
		sbb.WriteString(vector[i].String())
		if i != len(vector)-1 {
			sbb.WriteByte(',')
		}
	}
	sbb.WriteByte(']')
	return sbb.String()
}

// Len is the number of elements in the collection.
func (vector Vector) Len() int {
	return len(vector)
}

// Less reports whether the element with
// index i should sort before the element with index j.
func (vector Vector) Less(i, j int) bool {
	return vector[i].Cmp(&vector[j]) == -1
}

// Swap swaps the elements with indexes i and j.
func (vector Vector) Swap(i, j int) {
	vector[i], vector[j] = vector[j], vector[i]
}

// SetRandom sets the elements in vector to independent uniform random values in [0, q).
//
// This might error only if reading from crypto/rand.Reader errors,
// in which case the values in vector are undefined.
func (vector Vector) SetRandom() error {
	for i := range vector {
		if _, err := vector[i].SetRandom(); err != nil {
			return err
		}
	}
	return nil
}

// Exp sets vector[i] = a[i]ᵏ for all i
func (vector Vector) Exp(a Vector, k int64) {
	N := len(a)
	if N != len(vector) {
		panic("vector.Exp: vectors don't have the same length")
	}
	if k == 0 {
		for i := range vector {
			vector[i].SetOne()
		}
		return
	}
	base := a
	exp := k
	if k < 0 {
		// call batch inverse
		base = BatchInvert(a)
		exp = -k // if k == math.MinInt64, -k overflows, but uint64(-k) is correct
	} else if N > 0 {
		// ensure that vector and a are not the same slice; else we need to copy a into base
		v0 := &vector[0] // #nosec G602 we check that N > 0 above
		a0 := &a[0]      // #nosec G602 we check that N > 0 above
		if v0 == a0 {
			base = make(Vector, N)
			copy(base, a)
		}
	}

	copy(vector, base)

	// Use bits.Len64 to iterate only over significant bits
	for i := bits.Len64(uint64(exp)) - 2; i >= 0; i-- {
		vector.Mul(vector, vector)
		if (uint64(exp)>>uint(i))&1 != 0 {
			vector.Mul(vector, base)
		}
	}
}

// MustSetRandom sets the elements in vector to independent uniform random values in [0, q).
//
// It panics if reading from crypto/rand.Reader errors.
func (vector Vector) MustSetRandom() {
	for i := range vector {
		if _, err := vector[i].SetRandom(); err != nil {
			panic(err)
		}
	}
}

// Equal returns true if vector and other have the same length and same elements.
func (vector Vector) Equal(other Vector) bool {
	return slices.Equal(vector, other)
}

func addVecGeneric(res, a, b Vector) {
	if len(a) != len(b) || len(a) != len(res) {
		panic("vector.Add: vectors don't have the same length")
	}
	for i := 0; i < len(a); i++ {
		res[i].Add(&a[i], &b[i])
	}
}

func subVecGeneric(res, a, b Vector) {
	if len(a) != len(b) || len(a) != len(res) {
		panic("vector.Sub: vectors don't have the same length")
	}
	for i := 0; i < len(a); i++ {
		res[i].Sub(&a[i], &b[i])
	}
}

func scalarMulVecGeneric(res, a Vector, b *Element) {
	if len(a) != len(res) {
		panic("vector.ScalarMul: vectors don't have the same length")
	}
	for i := 0; i < len(a); i++ {
		res[i].Mul(&a[i], b)
	}
}

func sumVecGeneric(res *Element, a Vector) {
	for i := 0; i < len(a); i++ {
		res.Add(res, &a[i])
	}
}

func innerProductVecGeneric(res *Element, a, b Vector) {
	if len(a) != len(b) {
		panic("vector.InnerProduct: vectors don't have the same length")
	}
	var tmp Element
	for i := 0; i < len(a); i++ {
		tmp.Mul(&a[i], &b[i])
		res.Add(res, &tmp)
	}
}

func mulVecGeneric(res, a, b Vector) {
	if len(a) != len(b) || len(a) != len(res) {
		panic("vector.Mul: vectors don't have the same length")
	}
	for i := 0; i < len(a); i++ {
		res[i].Mul(&a[i], &b[i])
	}
}

// TODO @gbotrel make a public package out of that.
// execute executes the work function in parallel.
// this is copy paste from internal/parallel/parallel.go
// as we don't want to generate code importing internal/
func execute(nbIterations int, work func(int, int), maxCpus ...int) {

	nbTasks := runtime.NumCPU()
	if len(maxCpus) == 1 {
		nbTasks = maxCpus[0]
		if nbTasks < 1 {
			nbTasks = 1
		} else if nbTasks > 512 {
			nbTasks = 512
		}
	}

	if nbTasks == 1 {
		// no go routines
		work(0, nbIterations)
		return
	}

	nbIterationsPerCpus := nbIterations / nbTasks

	// more CPUs than tasks: a CPU will work on exactly one iteration
	if nbIterationsPerCpus < 1 {
		nbIterationsPerCpus = 1
		nbTasks = nbIterations
	}

	var wg sync.WaitGroup

	extraTasks := nbIterations - (nbTasks * nbIterationsPerCpus)
	extraTasksOffset := 0

	for i := 0; i < nbTasks; i++ {
		wg.Add(1)
		_start := i*nbIterationsPerCpus + extraTasksOffset
		_end := _start + nbIterationsPerCpus
		if extraTasks > 0 {
			_end++
			extraTasks--
			extraTasksOffset++
		}
		go func() {
			work(_start, _end)
			wg.Done()
		}()
	}

	wg.Wait()
}