// uint256: Fixed size 256-bit math library
// Copyright 2020 uint256 Authors
// SPDX-License-Identifier: BSD-3-Clause
package uint256
import (
"database/sql"
"database/sql/driver"
"encoding"
"encoding/binary"
"encoding/json"
"errors"
"fmt"
"io"
"math"
"math/big"
"math/bits"
"strings"
)
const (
maxWords = 256 / bits.UintSize // number of big.Words in 256-bit
// The constants below work as compile-time checks: in case evaluated to
// negative value it cannot be assigned to uint type and compilation fails.
// These particular expressions check if maxWords either 4 or 8 matching
// 32-bit and 64-bit architectures.
_ uint = -(maxWords & (maxWords - 1)) // maxWords is power of two.
_ uint = -(maxWords & ^(4 | 8)) // maxWords is 4 or 8.
)
// Compile time interface checks
var (
_ driver.Valuer = (*Int)(nil)
_ sql.Scanner = (*Int)(nil)
_ encoding.TextMarshaler = (*Int)(nil)
_ encoding.TextUnmarshaler = (*Int)(nil)
_ json.Marshaler = (*Int)(nil)
_ json.Unmarshaler = (*Int)(nil)
)
// ToBig returns a big.Int version of z.
// Return `nil` if z is nil
func (z *Int) ToBig() *big.Int {
if z == nil {
return nil
}
b := new(big.Int)
switch maxWords { // Compile-time check.
case 4: // 64-bit architectures.
words := [4]big.Word{big.Word(z[0]), big.Word(z[1]), big.Word(z[2]), big.Word(z[3])}
b.SetBits(words[:])
case 8: // 32-bit architectures.
words := [8]big.Word{
big.Word(z[0]), big.Word(z[0] >> 32),
big.Word(z[1]), big.Word(z[1] >> 32),
big.Word(z[2]), big.Word(z[2] >> 32),
big.Word(z[3]), big.Word(z[3] >> 32),
}
b.SetBits(words[:])
}
return b
}
// FromBig is a convenience-constructor from big.Int.
// Returns a new Int and whether overflow occurred.
// OBS: If b is `nil`, this method returns `nil, false`
func FromBig(b *big.Int) (*Int, bool) {
if b == nil {
return nil, false
}
z := &Int{}
overflow := z.SetFromBig(b)
return z, overflow
}
// MustFromBig is a convenience-constructor from big.Int.
// Returns a new Int and panics if overflow occurred.
// OBS: If b is `nil`, this method does _not_ panic, but
// instead returns `nil`
func MustFromBig(b *big.Int) *Int {
if b == nil {
return nil
}
z := &Int{}
if z.SetFromBig(b) {
panic("overflow")
}
return z
}
// Float64 returns the float64 value nearest to x.
//
// Note: The `big.Float` version of `Float64` also returns an 'Accuracy', indicating
// whether the value was too small or too large to be represented by a
// `float64`. However, the `uint256` type is unable to represent values
// out of scope (|x| < math.SmallestNonzeroFloat64 or |x| > math.MaxFloat64),
// therefore this method does not return any accuracy.
func (z *Int) Float64() float64 {
if z.IsUint64() {
return float64(z.Uint64())
}
// See [1] for a detailed walkthrough of IEEE 754 conversion
//
// 1: https://www.wikihow.com/Convert-a-Number-from-Decimal-to-IEEE-754-Floating-Point-Representation
bitlen := uint64(z.BitLen())
// Normalize the number, by shifting it so that the MSB is shifted out.
y := new(Int).Lsh(z, uint(1+256-bitlen))
// The number with the leading 1 shifted out is the fraction.
fraction := y[3]
// The exp is calculated from the number of shifts, adjusted with the bias.
// double-precision uses 1023 as bias
biased_exp := 1023 + bitlen - 1
// The IEEE 754 double-precision layout is as follows:
// 1 sign bit (we don't bother with this, since it's always zero for uints)
// 11 exponent bits
// 52 fraction bits
// --------
// 64 bits
return math.Float64frombits(biased_exp<<52 | fraction>>12)
}
// SetFromHex sets z from the given string, interpreted as a hexadecimal number.
// OBS! This method is _not_ strictly identical to the (*big.Int).SetString(..., 16) method.
// Notable differences:
// - This method _require_ "0x" or "0X" prefix.
// - This method does not accept zero-prefixed hex, e.g. "0x0001"
// - This method does not accept underscore input, e.g. "100_000",
// - This method does not accept negative zero as valid, e.g "-0x0",
// - (this method does not accept any negative input as valid)
func (z *Int) SetFromHex(hex string) error {
return z.fromHex(hex)
}
// fromHex is the internal implementation of parsing a hex-string.
func (z *Int) fromHex(hex string) error {
if err := checkNumberS(hex); err != nil {
return err
}
if len(hex) > 66 {
return ErrBig256Range
}
z.Clear()
end := len(hex)
for i := 0; i < 4; i++ {
start := end - 16
if start < 2 {
start = 2
}
for ri := start; ri < end; ri++ {
nib := bintable[hex[ri]]
if nib == badNibble {
return ErrSyntax
}
z[i] = z[i] << 4
z[i] += uint64(nib)
}
end = start
}
return nil
}
// FromHex is a convenience-constructor to create an Int from
// a hexadecimal string. The string is required to be '0x'-prefixed
// Numbers larger than 256 bits are not accepted.
func FromHex(hex string) (*Int, error) {
var z Int
if err := z.fromHex(hex); err != nil {
return nil, err
}
return &z, nil
}
// MustFromHex is a convenience-constructor to create an Int from
// a hexadecimal string.
// Returns a new Int and panics if any error occurred.
func MustFromHex(hex string) *Int {
var z Int
if err := z.fromHex(hex); err != nil {
panic(err)
}
return &z
}
// UnmarshalText implements encoding.TextUnmarshaler. This method
// can unmarshal either hexadecimal or decimal.
// - For hexadecimal, the input _must_ be prefixed with 0x or 0X
func (z *Int) UnmarshalText(input []byte) error {
if len(input) >= 2 && input[0] == '0' && (input[1] == 'x' || input[1] == 'X') {
return z.fromHex(string(input))
}
return z.fromDecimal(string(input))
}
// SetFromBig converts a big.Int to Int and sets the value to z.
// TODO: Ensure we have sufficient testing, esp for negative bigints.
func (z *Int) SetFromBig(b *big.Int) bool {
z.Clear()
words := b.Bits()
overflow := len(words) > maxWords
switch maxWords { // Compile-time check.
case 4: // 64-bit architectures.
if len(words) > 0 {
z[0] = uint64(words[0])
if len(words) > 1 {
z[1] = uint64(words[1])
if len(words) > 2 {
z[2] = uint64(words[2])
if len(words) > 3 {
z[3] = uint64(words[3])
}
}
}
}
case 8: // 32-bit architectures.
numWords := len(words)
if overflow {
numWords = maxWords
}
for i := 0; i < numWords; i++ {
if i%2 == 0 {
z[i/2] = uint64(words[i])
} else {
z[i/2] |= uint64(words[i]) << 32
}
}
}
if b.Sign() == -1 {
z.Neg(z)
}
return overflow
}
// Format implements fmt.Formatter. It accepts the formats
// 'b' (binary), 'o' (octal with 0 prefix), 'O' (octal with 0o prefix),
// 'd' (decimal), 'x' (lowercase hexadecimal), and
// 'X' (uppercase hexadecimal).
// Also supported are the full suite of package fmt's format
// flags for integral types, including '+' and ' ' for sign
// control, '#' for leading zero in octal and for hexadecimal,
// a leading "0x" or "0X" for "%#x" and "%#X" respectively,
// specification of minimum digits precision, output field
// width, space or zero padding, and '-' for left or right
// justification.
func (z *Int) Format(s fmt.State, ch rune) {
z.ToBig().Format(s, ch)
}
// SetBytes8 is identical to SetBytes(in[:8]), but panics is input is too short
func (z *Int) SetBytes8(in []byte) *Int {
_ = in[7] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2], z[1] = 0, 0, 0
z[0] = binary.BigEndian.Uint64(in[0:8])
return z
}
// SetBytes16 is identical to SetBytes(in[:16]), but panics is input is too short
func (z *Int) SetBytes16(in []byte) *Int {
_ = in[15] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2] = 0, 0
z[1] = binary.BigEndian.Uint64(in[0:8])
z[0] = binary.BigEndian.Uint64(in[8:16])
return z
}
// SetBytes16 is identical to SetBytes(in[:24]), but panics is input is too short
func (z *Int) SetBytes24(in []byte) *Int {
_ = in[23] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = 0
z[2] = binary.BigEndian.Uint64(in[0:8])
z[1] = binary.BigEndian.Uint64(in[8:16])
z[0] = binary.BigEndian.Uint64(in[16:24])
return z
}
func (z *Int) SetBytes32(in []byte) *Int {
_ = in[31] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = binary.BigEndian.Uint64(in[0:8])
z[2] = binary.BigEndian.Uint64(in[8:16])
z[1] = binary.BigEndian.Uint64(in[16:24])
z[0] = binary.BigEndian.Uint64(in[24:32])
return z
}
func (z *Int) SetBytes1(in []byte) *Int {
z[3], z[2], z[1] = 0, 0, 0
z[0] = uint64(in[0])
return z
}
func (z *Int) SetBytes9(in []byte) *Int {
_ = in[8] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2] = 0, 0
z[1] = uint64(in[0])
z[0] = binary.BigEndian.Uint64(in[1:9])
return z
}
func (z *Int) SetBytes17(in []byte) *Int {
_ = in[16] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = 0
z[2] = uint64(in[0])
z[1] = binary.BigEndian.Uint64(in[1:9])
z[0] = binary.BigEndian.Uint64(in[9:17])
return z
}
func (z *Int) SetBytes25(in []byte) *Int {
_ = in[24] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = uint64(in[0])
z[2] = binary.BigEndian.Uint64(in[1:9])
z[1] = binary.BigEndian.Uint64(in[9:17])
z[0] = binary.BigEndian.Uint64(in[17:25])
return z
}
func (z *Int) SetBytes2(in []byte) *Int {
_ = in[1] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2], z[1] = 0, 0, 0
z[0] = uint64(binary.BigEndian.Uint16(in[0:2]))
return z
}
func (z *Int) SetBytes10(in []byte) *Int {
_ = in[9] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2] = 0, 0
z[1] = uint64(binary.BigEndian.Uint16(in[0:2]))
z[0] = binary.BigEndian.Uint64(in[2:10])
return z
}
func (z *Int) SetBytes18(in []byte) *Int {
_ = in[17] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = 0
z[2] = uint64(binary.BigEndian.Uint16(in[0:2]))
z[1] = binary.BigEndian.Uint64(in[2:10])
z[0] = binary.BigEndian.Uint64(in[10:18])
return z
}
func (z *Int) SetBytes26(in []byte) *Int {
_ = in[25] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = uint64(binary.BigEndian.Uint16(in[0:2]))
z[2] = binary.BigEndian.Uint64(in[2:10])
z[1] = binary.BigEndian.Uint64(in[10:18])
z[0] = binary.BigEndian.Uint64(in[18:26])
return z
}
func (z *Int) SetBytes3(in []byte) *Int {
_ = in[2] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2], z[1] = 0, 0, 0
z[0] = uint64(binary.BigEndian.Uint16(in[1:3])) | uint64(in[0])<<16
return z
}
func (z *Int) SetBytes11(in []byte) *Int {
_ = in[10] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2] = 0, 0
z[1] = uint64(binary.BigEndian.Uint16(in[1:3])) | uint64(in[0])<<16
z[0] = binary.BigEndian.Uint64(in[3:11])
return z
}
func (z *Int) SetBytes19(in []byte) *Int {
_ = in[18] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = 0
z[2] = uint64(binary.BigEndian.Uint16(in[1:3])) | uint64(in[0])<<16
z[1] = binary.BigEndian.Uint64(in[3:11])
z[0] = binary.BigEndian.Uint64(in[11:19])
return z
}
func (z *Int) SetBytes27(in []byte) *Int {
_ = in[26] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = uint64(binary.BigEndian.Uint16(in[1:3])) | uint64(in[0])<<16
z[2] = binary.BigEndian.Uint64(in[3:11])
z[1] = binary.BigEndian.Uint64(in[11:19])
z[0] = binary.BigEndian.Uint64(in[19:27])
return z
}
func (z *Int) SetBytes4(in []byte) *Int {
_ = in[3] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2], z[1] = 0, 0, 0
z[0] = uint64(binary.BigEndian.Uint32(in[0:4]))
return z
}
func (z *Int) SetBytes12(in []byte) *Int {
_ = in[11] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2] = 0, 0
z[1] = uint64(binary.BigEndian.Uint32(in[0:4]))
z[0] = binary.BigEndian.Uint64(in[4:12])
return z
}
func (z *Int) SetBytes20(in []byte) *Int {
_ = in[19] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = 0
z[2] = uint64(binary.BigEndian.Uint32(in[0:4]))
z[1] = binary.BigEndian.Uint64(in[4:12])
z[0] = binary.BigEndian.Uint64(in[12:20])
return z
}
func (z *Int) SetBytes28(in []byte) *Int {
_ = in[27] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = uint64(binary.BigEndian.Uint32(in[0:4]))
z[2] = binary.BigEndian.Uint64(in[4:12])
z[1] = binary.BigEndian.Uint64(in[12:20])
z[0] = binary.BigEndian.Uint64(in[20:28])
return z
}
func (z *Int) SetBytes5(in []byte) *Int {
_ = in[4] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2], z[1] = 0, 0, 0
z[0] = bigEndianUint40(in[0:5])
return z
}
func (z *Int) SetBytes13(in []byte) *Int {
_ = in[12] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2] = 0, 0
z[1] = bigEndianUint40(in[0:5])
z[0] = binary.BigEndian.Uint64(in[5:13])
return z
}
func (z *Int) SetBytes21(in []byte) *Int {
_ = in[20] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = 0
z[2] = bigEndianUint40(in[0:5])
z[1] = binary.BigEndian.Uint64(in[5:13])
z[0] = binary.BigEndian.Uint64(in[13:21])
return z
}
func (z *Int) SetBytes29(in []byte) *Int {
_ = in[28] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = bigEndianUint40(in[0:5])
z[2] = binary.BigEndian.Uint64(in[5:13])
z[1] = binary.BigEndian.Uint64(in[13:21])
z[0] = binary.BigEndian.Uint64(in[21:29])
return z
}
func (z *Int) SetBytes6(in []byte) *Int {
_ = in[5] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2], z[1] = 0, 0, 0
z[0] = bigEndianUint48(in[0:6])
return z
}
func (z *Int) SetBytes14(in []byte) *Int {
_ = in[13] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2] = 0, 0
z[1] = bigEndianUint48(in[0:6])
z[0] = binary.BigEndian.Uint64(in[6:14])
return z
}
func (z *Int) SetBytes22(in []byte) *Int {
_ = in[21] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = 0
z[2] = bigEndianUint48(in[0:6])
z[1] = binary.BigEndian.Uint64(in[6:14])
z[0] = binary.BigEndian.Uint64(in[14:22])
return z
}
func (z *Int) SetBytes30(in []byte) *Int {
_ = in[29] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = bigEndianUint48(in[0:6])
z[2] = binary.BigEndian.Uint64(in[6:14])
z[1] = binary.BigEndian.Uint64(in[14:22])
z[0] = binary.BigEndian.Uint64(in[22:30])
return z
}
func (z *Int) SetBytes7(in []byte) *Int {
_ = in[6] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2], z[1] = 0, 0, 0
z[0] = bigEndianUint56(in[0:7])
return z
}
func (z *Int) SetBytes15(in []byte) *Int {
_ = in[14] // bounds check hint to compiler; see golang.org/issue/14808
z[3], z[2] = 0, 0
z[1] = bigEndianUint56(in[0:7])
z[0] = binary.BigEndian.Uint64(in[7:15])
return z
}
func (z *Int) SetBytes23(in []byte) *Int {
_ = in[22] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = 0
z[2] = bigEndianUint56(in[0:7])
z[1] = binary.BigEndian.Uint64(in[7:15])
z[0] = binary.BigEndian.Uint64(in[15:23])
return z
}
func (z *Int) SetBytes31(in []byte) *Int {
_ = in[30] // bounds check hint to compiler; see golang.org/issue/14808
z[3] = bigEndianUint56(in[0:7])
z[2] = binary.BigEndian.Uint64(in[7:15])
z[1] = binary.BigEndian.Uint64(in[15:23])
z[0] = binary.BigEndian.Uint64(in[23:31])
return z
}
// Utility methods that are "missing" among the bigEndian.UintXX methods.
func bigEndianUint40(b []byte) uint64 {
_ = b[4] // bounds check hint to compiler; see golang.org/issue/14808
return uint64(b[4]) | uint64(b[3])<<8 | uint64(b[2])<<16 | uint64(b[1])<<24 |
uint64(b[0])<<32
}
func bigEndianUint48(b []byte) uint64 {
_ = b[5] // bounds check hint to compiler; see golang.org/issue/14808
return uint64(b[5]) | uint64(b[4])<<8 | uint64(b[3])<<16 | uint64(b[2])<<24 |
uint64(b[1])<<32 | uint64(b[0])<<40
}
func bigEndianUint56(b []byte) uint64 {
_ = b[6] // bounds check hint to compiler; see golang.org/issue/14808
return uint64(b[6]) | uint64(b[5])<<8 | uint64(b[4])<<16 | uint64(b[3])<<24 |
uint64(b[2])<<32 | uint64(b[1])<<40 | uint64(b[0])<<48
}
// MarshalSSZTo implements the fastssz.Marshaler interface and serializes the
// integer into an already pre-allocated buffer.
func (z *Int) MarshalSSZTo(dst []byte) ([]byte, error) {
if len(dst) < 32 {
return nil, fmt.Errorf("%w: have %d, want %d bytes", ErrBadBufferLength, len(dst), 32)
}
binary.LittleEndian.PutUint64(dst[0:8], z[0])
binary.LittleEndian.PutUint64(dst[8:16], z[1])
binary.LittleEndian.PutUint64(dst[16:24], z[2])
binary.LittleEndian.PutUint64(dst[24:32], z[3])
return dst[32:], nil
}
// MarshalSSZ implements the fastssz.Marshaler interface and returns the integer
// marshalled into a newly allocated byte slice.
func (z *Int) MarshalSSZ() ([]byte, error) {
blob := make([]byte, 32)
_, _ = z.MarshalSSZTo(blob) // ignore error, cannot fail, surely have 32 byte space in blob
return blob, nil
}
// SizeSSZ implements the fastssz.Marshaler interface and returns the byte size
// of the 256 bit int.
func (*Int) SizeSSZ() int {
return 32
}
// UnmarshalSSZ implements the fastssz.Unmarshaler interface and parses an encoded
// integer into the local struct.
func (z *Int) UnmarshalSSZ(buf []byte) error {
if len(buf) != 32 {
return fmt.Errorf("%w: have %d, want %d bytes", ErrBadEncodedLength, len(buf), 32)
}
z[0] = binary.LittleEndian.Uint64(buf[0:8])
z[1] = binary.LittleEndian.Uint64(buf[8:16])
z[2] = binary.LittleEndian.Uint64(buf[16:24])
z[3] = binary.LittleEndian.Uint64(buf[24:32])
return nil
}
// HashTreeRoot implements the fastssz.HashRoot interface's non-dependent part.
func (z *Int) HashTreeRoot() ([32]byte, error) {
var hash [32]byte
_, _ = z.MarshalSSZTo(hash[:]) // ignore error, cannot fail
return hash, nil
}
// EncodeRLP implements the rlp.Encoder interface from go-ethereum
// and writes the RLP encoding of z to w.
func (z *Int) EncodeRLP(w io.Writer) error {
if z == nil {
_, err := w.Write([]byte{0x80})
return err
}
nBits := z.BitLen()
if nBits == 0 {
_, err := w.Write([]byte{0x80})
return err
}
if nBits <= 7 {
_, err := w.Write([]byte{byte(z[0])})
return err
}
nBytes := byte((nBits + 7) / 8)
var b [33]byte
binary.BigEndian.PutUint64(b[1:9], z[3])
binary.BigEndian.PutUint64(b[9:17], z[2])
binary.BigEndian.PutUint64(b[17:25], z[1])
binary.BigEndian.PutUint64(b[25:33], z[0])
b[32-nBytes] = 0x80 + nBytes
_, err := w.Write(b[32-nBytes:])
return err
}
// MarshalText implements encoding.TextMarshaler
// MarshalText marshals using the decimal representation (compatible with big.Int)
func (z *Int) MarshalText() ([]byte, error) {
return []byte(z.Dec()), nil
}
// MarshalJSON implements json.Marshaler.
// MarshalJSON marshals using the 'decimal string' representation. This is _not_ compatible
// with big.Int: big.Int marshals into JSON 'native' numeric format.
//
// The JSON native format is, on some platforms, (e.g. javascript), limited to 53-bit large
// integer space. Thus, U256 uses string-format, which is not compatible with
// big.int (big.Int refuses to unmarshal a string representation).
func (z *Int) MarshalJSON() ([]byte, error) {
return []byte(`"` + z.Dec() + `"`), nil
}
// UnmarshalJSON implements json.Unmarshaler. UnmarshalJSON accepts either
// - Quoted string: either hexadecimal OR decimal
// - Not quoted string: only decimal
func (z *Int) UnmarshalJSON(input []byte) error {
if len(input) < 2 || input[0] != '"' || input[len(input)-1] != '"' {
// if not quoted, it must be decimal
return z.fromDecimal(string(input))
}
return z.UnmarshalText(input[1 : len(input)-1])
}
// String returns the decimal encoding of b.
func (z *Int) String() string {
return z.Dec()
}
const (
hextable = "0123456789abcdef"
bintable = "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\x00\x01\x02\x03\x04\x05\x06\a\b\t\xff\xff\xff\xff\xff\xff\xff\n\v\f\r\x0e\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\n\v\f\r\x0e\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
badNibble = 0xff
)
// Hex encodes z in 0x-prefixed hexadecimal form.
func (z *Int) Hex() string {
// This implementation is not optimal, it allocates a full
// 66-byte output buffer which it fills. It could instead allocate a smaller
// buffer, and omit the final crop-stage.
output := make([]byte, 66)
nibbles := (z.BitLen() + 3) / 4 // nibbles [0,64]
if nibbles == 0 {
nibbles = 1
}
// Start with the most significant
zWord := (nibbles - 1) / 16
for i := zWord; i >= 0; i-- {
off := (3 - i) * 16
output[off+2] = hextable[byte(z[i]>>60)&0xf]
output[off+3] = hextable[byte(z[i]>>56)&0xf]
output[off+4] = hextable[byte(z[i]>>52)&0xf]
output[off+5] = hextable[byte(z[i]>>48)&0xf]
output[off+6] = hextable[byte(z[i]>>44)&0xf]
output[off+7] = hextable[byte(z[i]>>40)&0xf]
output[off+8] = hextable[byte(z[i]>>36)&0xf]
output[off+9] = hextable[byte(z[i]>>32)&0xf]
output[off+10] = hextable[byte(z[i]>>28)&0xf]
output[off+11] = hextable[byte(z[i]>>24)&0xf]
output[off+12] = hextable[byte(z[i]>>20)&0xf]
output[off+13] = hextable[byte(z[i]>>16)&0xf]
output[off+14] = hextable[byte(z[i]>>12)&0xf]
output[off+15] = hextable[byte(z[i]>>8)&0xf]
output[off+16] = hextable[byte(z[i]>>4)&0xf]
output[off+17] = hextable[byte(z[i]&0xF)&0xf]
}
output[64-nibbles] = '0'
output[65-nibbles] = 'x'
return string(output[64-nibbles:])
}
// Scan implements the database/sql Scanner interface.
// It decodes a string, because that is what postgres uses for its numeric type
func (dst *Int) Scan(src interface{}) error {
if src == nil {
dst.Clear()
return nil
}
switch src := src.(type) {
case string:
return dst.scanScientificFromString(src)
case []byte:
return dst.scanScientificFromString(string(src))
}
return errors.New("unsupported type")
}
func (dst *Int) scanScientificFromString(src string) error {
if len(src) == 0 {
dst.Clear()
return nil
}
idx := strings.IndexByte(src, 'e')
if idx == -1 {
return dst.SetFromDecimal(src)
}
if err := dst.SetFromDecimal(src[:idx]); err != nil {
return err
}
if src[(idx+1):] == "0" {
return nil
}
exp := new(Int)
if err := exp.SetFromDecimal(src[(idx + 1):]); err != nil {
return err
}
if exp.GtUint64(77) { // 10**78 is larger than 2**256
return ErrBig256Range
}
exp.Exp(NewInt(10), exp)
if _, overflow := dst.MulOverflow(dst, exp); overflow {
return ErrBig256Range
}
return nil
}
// Value implements the database/sql/driver Valuer interface.
// It encodes a base 10 string.
// In Postgres, this will work with both integer and the Numeric/Decimal types
// In MariaDB/MySQL, this will work with the Numeric/Decimal types up to 65 digits, however any more and you should use either VarChar or Char(79)
// In SqLite, use TEXT
func (src *Int) Value() (driver.Value, error) {
return src.Dec(), nil
}
var (
ErrEmptyString = errors.New("empty hex string")
ErrSyntax = errors.New("invalid hex string")
ErrMissingPrefix = errors.New("hex string without 0x prefix")
ErrEmptyNumber = errors.New("hex string \"0x\"")
ErrLeadingZero = errors.New("hex number with leading zero digits")
ErrBig256Range = errors.New("hex number > 256 bits")
ErrBadBufferLength = errors.New("bad ssz buffer length")
ErrBadEncodedLength = errors.New("bad ssz encoded length")
)
func checkNumberS(input string) error {
l := len(input)
if l == 0 {
return ErrEmptyString
}
if l < 2 || input[0] != '0' ||
(input[1] != 'x' && input[1] != 'X') {
return ErrMissingPrefix
}
if l == 2 {
return ErrEmptyNumber
}
if len(input) > 3 && input[2] == '0' {
return ErrLeadingZero
}
return nil
}
// uint256: Fixed size 256-bit math library
// Copyright 2020 uint256 Authors
// SPDX-License-Identifier: BSD-3-Clause
package uint256
import (
"io"
"strconv"
)
const twoPow256Sub1 = "115792089237316195423570985008687907853269984665640564039457584007913129639935"
// Dec returns the decimal representation of z.
func (z *Int) Dec() string {
if z.IsZero() {
return "0"
}
if z.IsUint64() {
return strconv.FormatUint(z.Uint64(), 10)
}
// The max uint64 value being 18446744073709551615, the largest
// power-of-ten below that is 10000000000000000000.
// When we do a DivMod using that number, the remainder that we
// get back is the lower part of the output.
//
// The ascii-output of remainder will never exceed 19 bytes (since it will be
// below 10000000000000000000).
//
// Algorithm example using 100 as divisor
//
// 12345 % 100 = 45 (rem)
// 12345 / 100 = 123 (quo)
// -> output '45', continue iterate on 123
var (
// out is 98 bytes long: 78 (max size of a string without leading zeroes,
// plus slack so we can copy 19 bytes every iteration).
// We init it with zeroes, because when strconv appends the ascii representations,
// it will omit leading zeroes.
out = []byte("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000")
divisor = NewInt(10000000000000000000) // 20 digits
y = new(Int).Set(z) // copy to avoid modifying z
pos = len(out) // position to write to
buf = make([]byte, 0, 19) // buffer to write uint64:s to
)
for {
// Obtain Q and R for divisor
var quot Int
rem := udivrem(quot[:], y[:], divisor)
y.Set(") // Set Q for next loop
// Convert the R to ascii representation
buf = strconv.AppendUint(buf[:0], rem.Uint64(), 10)
// Copy in the ascii digits
copy(out[pos-len(buf):], buf)
if y.IsZero() {
break
}
// Move 19 digits left
pos -= 19
}
// skip leading zeroes by only using the 'used size' of buf
return string(out[pos-len(buf):])
}
// PrettyDec returns the decimal representation of z, with thousands-separators.
func (z *Int) PrettyDec(separator byte) string {
if z.IsZero() {
return "0"
}
// See algorithm-description in Dec()
// This just also inserts comma while copying byte-for-byte instead
// of using copy().
var (
out = []byte("0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000")
divisor = NewInt(10000000000000000000)
y = new(Int).Set(z) // copy to avoid modifying z
pos = len(out) - 1 // position to write to
buf = make([]byte, 0, 19) // buffer to write uint64:s to
comma = 0
)
for {
var quot Int
rem := udivrem(quot[:], y[:], divisor)
y.Set(") // Set Q for next loop
buf = strconv.AppendUint(buf[:0], rem.Uint64(), 10)
for j := len(buf) - 1; j >= 0; j-- {
if comma == 3 {
out[pos] = separator
pos--
comma = 0
}
out[pos] = buf[j]
comma++
pos--
}
if y.IsZero() {
break
}
// Need to do zero-padding if we have more iterations coming
for j := 0; j < 19-len(buf); j++ {
if comma == 3 {
out[pos] = separator
pos--
comma = 0
}
comma++
pos--
}
}
return string(out[pos+1:])
}
// FromDecimal is a convenience-constructor to create an Int from a
// decimal (base 10) string. Numbers larger than 256 bits are not accepted.
func FromDecimal(decimal string) (*Int, error) {
var z Int
if err := z.SetFromDecimal(decimal); err != nil {
return nil, err
}
return &z, nil
}
// MustFromDecimal is a convenience-constructor to create an Int from a
// decimal (base 10) string.
// Returns a new Int and panics if any error occurred.
func MustFromDecimal(decimal string) *Int {
var z Int
if err := z.SetFromDecimal(decimal); err != nil {
panic(err)
}
return &z
}
// SetFromDecimal sets z from the given string, interpreted as a decimal number.
// OBS! This method is _not_ strictly identical to the (*big.Int).SetString(..., 10) method.
// Notable differences:
// - This method does not accept underscore input, e.g. "100_000",
// - This method does not accept negative zero as valid, e.g "-0",
// - (this method does not accept any negative input as valid))
func (z *Int) SetFromDecimal(s string) (err error) {
// Remove max one leading +
if len(s) > 0 && s[0] == '+' {
s = s[1:]
}
// Remove any number of leading zeroes
if len(s) > 0 && s[0] == '0' {
var i int
var c rune
for i, c = range s {
if c != '0' {
break
}
}
s = s[i:]
}
if len(s) < len(twoPow256Sub1) {
return z.fromDecimal(s)
}
if len(s) == len(twoPow256Sub1) {
if s > twoPow256Sub1 {
return ErrBig256Range
}
return z.fromDecimal(s)
}
return ErrBig256Range
}
// multipliers holds the values that are needed for fromDecimal
var multipliers = [5]*Int{
nil, // represents first round, no multiplication needed
{10000000000000000000, 0, 0, 0}, // 10 ^ 19
{687399551400673280, 5421010862427522170, 0, 0}, // 10 ^ 38
{5332261958806667264, 17004971331911604867, 2938735877055718769, 0}, // 10 ^ 57
{0, 8607968719199866880, 532749306367912313, 1593091911132452277}, // 10 ^ 76
}
// fromDecimal is a helper function to only ever be called via SetFromDecimal
// this function takes a string and chunks it up, calling ParseUint on it up to 5 times
// these chunks are then multiplied by the proper power of 10, then added together.
func (z *Int) fromDecimal(bs string) error {
// first clear the input
z.Clear()
// the maximum value of uint64 is 18446744073709551615, which is 20 characters
// one less means that a string of 19 9's is always within the uint64 limit
var (
num uint64
err error
remaining = len(bs)
)
if remaining == 0 {
return io.EOF
}
// We proceed in steps of 19 characters (nibbles), from least significant to most significant.
// This means that the first (up to) 19 characters do not need to be multiplied.
// In the second iteration, our slice of 19 characters needs to be multipleied
// by a factor of 10^19. Et cetera.
for i, mult := range multipliers {
if remaining <= 0 {
return nil // Done
} else if remaining > 19 {
num, err = strconv.ParseUint(bs[remaining-19:remaining], 10, 64)
} else {
// Final round
num, err = strconv.ParseUint(bs, 10, 64)
}
if err != nil {
return err
}
// add that number to our running total
if i == 0 {
z.SetUint64(num)
} else {
base := NewInt(num)
z.Add(z, base.Mul(base, mult))
}
// Chop off another 19 characters
if remaining > 19 {
bs = bs[0 : remaining-19]
}
remaining -= 19
}
return nil
}
// uint256: Fixed size 256-bit math library
// Copyright 2020 uint256 Authors
// SPDX-License-Identifier: BSD-3-Clause
package uint256
import "math/bits"
// reciprocal2by1 computes <^d, ^0> / d.
func reciprocal2by1(d uint64) uint64 {
reciprocal, _ := bits.Div64(^d, ^uint64(0), d)
return reciprocal
}
// udivrem2by1 divides <uh, ul> / d and produces both quotient and remainder.
// It uses the provided d's reciprocal.
// Implementation ported from https://github.com/chfast/intx and is based on
// "Improved division by invariant integers", Algorithm 4.
func udivrem2by1(uh, ul, d, reciprocal uint64) (quot, rem uint64) {
qh, ql := bits.Mul64(reciprocal, uh)
ql, carry := bits.Add64(ql, ul, 0)
qh, _ = bits.Add64(qh, uh, carry)
qh++
r := ul - qh*d
if r > ql {
qh--
r += d
}
if r >= d {
qh++
r -= d
}
return qh, r
}
// uint256: Fixed size 256-bit math library
// Copyright 2020 uint256 Authors
// SPDX-License-Identifier: BSD-3-Clause
//go:build gofuzz
// +build gofuzz
package uint256
import (
"fmt"
"math/big"
"reflect"
"runtime"
"strings"
)
const (
opUdivrem = iota
opMul
opLsh
opAdd
opSub
opMulmod
)
type opUnaryArgFunc func(*Int, *Int) *Int
type bigUnaryArgFunc func(*big.Int, *big.Int) *big.Int
type opDualArgFunc func(*Int, *Int, *Int) *Int
type bigDualArgFunc func(*big.Int, *big.Int, *big.Int) *big.Int
type opThreeArgFunc func(*Int, *Int, *Int, *Int) *Int
type bigThreeArgFunc func(*big.Int, *big.Int, *big.Int, *big.Int) *big.Int
func crash(op interface{}, msg string, args ...Int) {
fn := runtime.FuncForPC(reflect.ValueOf(op).Pointer())
fnName := fn.Name()
fnFile, fnLine := fn.FileLine(fn.Entry())
var strArgs []string
for i, arg := range args {
strArgs = append(strArgs, fmt.Sprintf("%d: %x", i, &arg))
}
panic(fmt.Sprintf("%s\nfor %s (%s:%d)\n%v",
msg, fnName, fnFile, fnLine, strings.Join(strArgs, "\n")))
}
func checkUnaryOp(op opUnaryArgFunc, bigOp bigUnaryArgFunc, x Int) {
origX := x
var result Int
ret := op(&result, &x)
if ret != &result {
crash(op, "returned not the pointer receiver", x)
}
if x != origX {
crash(op, "argument modified", x)
}
expected, _ := FromBig(bigOp(new(big.Int), x.ToBig()))
if result != *expected {
crash(op, "unexpected result", x)
}
// Test again when the receiver is not zero.
var garbage Int
garbage.Sub(&garbage, NewInt(1))
ret = op(&garbage, &x)
if ret != &garbage {
crash(op, "returned not the pointer receiver", x)
}
if garbage != *expected {
crash(op, "unexpected result", x)
}
// Test again with the receiver aliasing arguments.
ret = op(&x, &x)
if ret != &x {
crash(op, "returned not the pointer receiver", x)
}
if x != *expected {
crash(op, "unexpected result", x)
}
}
func checkDualArgOp(op opDualArgFunc, bigOp bigDualArgFunc, x, y Int) {
origX := x
origY := y
var result Int
ret := op(&result, &x, &y)
if ret != &result {
crash(op, "returned not the pointer receiver", x, y)
}
if x != origX {
crash(op, "first argument modified", x, y)
}
if y != origY {
crash(op, "second argument modified", x, y)
}
expected, _ := FromBig(bigOp(new(big.Int), x.ToBig(), y.ToBig()))
if result != *expected {
crash(op, "unexpected result", x, y)
}
// Test again when the receiver is not zero.
var garbage Int
garbage.Xor(&x, &y)
ret = op(&garbage, &x, &y)
if ret != &garbage {
crash(op, "returned not the pointer receiver", x, y)
}
if garbage != *expected {
crash(op, "unexpected result", x, y)
}
if x != origX {
crash(op, "first argument modified", x, y)
}
if y != origY {
crash(op, "second argument modified", x, y)
}
// Test again with the receiver aliasing arguments.
ret = op(&x, &x, &y)
if ret != &x {
crash(op, "returned not the pointer receiver", x, y)
}
if x != *expected {
crash(op, "unexpected result", x, y)
}
ret = op(&y, &origX, &y)
if ret != &y {
crash(op, "returned not the pointer receiver", x, y)
}
if y != *expected {
crash(op, "unexpected result", x, y)
}
}
func checkThreeArgOp(op opThreeArgFunc, bigOp bigThreeArgFunc, x, y, z Int) {
origX := x
origY := y
origZ := z
var result Int
ret := op(&result, &x, &y, &z)
if ret != &result {
crash(op, "returned not the pointer receiver", x, y, z)
}
switch {
case x != origX:
crash(op, "first argument modified", x, y, z)
case y != origY:
crash(op, "second argument modified", x, y, z)
case z != origZ:
crash(op, "third argument modified", x, y, z)
}
expected, _ := FromBig(bigOp(new(big.Int), x.ToBig(), y.ToBig(), z.ToBig()))
if have, want := result, *expected; have != want {
crash(op, fmt.Sprintf("unexpected result: have %v want %v", have, want), x, y, z)
}
// Test again when the receiver is not zero.
var garbage Int
garbage.Xor(&x, &y)
ret = op(&garbage, &x, &y, &z)
if ret != &garbage {
crash(op, "returned not the pointer receiver", x, y, z)
}
if have, want := garbage, *expected; have != want {
crash(op, fmt.Sprintf("unexpected result: have %v want %v", have, want), x, y, z)
}
switch {
case x != origX:
crash(op, "first argument modified", x, y, z)
case y != origY:
crash(op, "second argument modified", x, y, z)
case z != origZ:
crash(op, "third argument modified", x, y, z)
}
// Test again with the receiver aliasing arguments.
ret = op(&x, &x, &y, &z)
if ret != &x {
crash(op, "returned not the pointer receiver", x, y, z)
}
if have, want := x, *expected; have != want {
crash(op, fmt.Sprintf("unexpected result: have %v want %v", have, want), x, y, z)
}
ret = op(&y, &origX, &y, &z)
if ret != &y {
crash(op, "returned not the pointer receiver", x, y, z)
}
if y != *expected {
crash(op, "unexpected result", x, y, z)
}
ret = op(&z, &origX, &origY, &z)
if ret != &z {
crash(op, "returned not the pointer receiver", x, y, z)
}
if z != *expected {
crash(op, fmt.Sprintf("unexpected result: have %v want %v", z.ToBig(), expected), x, y, z)
}
}
func Fuzz(data []byte) int {
if len(data) < 32 {
return 0
}
switch {
case len(data) < 64:
return fuzzUnaryOp(data) // needs 32 byte
case len(data) < 96:
return fuzzBinaryOp(data) // needs 64 byte
case len(data) < 128:
return fuzzTernaryOp(data) // needs 96 byte
}
// Too large input
return -1
}
func fuzzUnaryOp(data []byte) int {
var x Int
x.SetBytes(data[0:32])
checkUnaryOp((*Int).Sqrt, (*big.Int).Sqrt, x)
return 1
}
func fuzzBinaryOp(data []byte) int {
var x, y Int
x.SetBytes(data[0:32])
y.SetBytes(data[32:])
if !y.IsZero() { // uDivrem
checkDualArgOp((*Int).Div, (*big.Int).Div, x, y)
checkDualArgOp((*Int).Mod, (*big.Int).Mod, x, y)
}
{ // opMul
checkDualArgOp((*Int).Mul, (*big.Int).Mul, x, y)
}
{ // opLsh
lsh := func(z, x, y *Int) *Int {
return z.Lsh(x, uint(y[0]))
}
bigLsh := func(z, x, y *big.Int) *big.Int {
n := uint(y.Uint64())
if n > 256 {
n = 256
}
return z.Lsh(x, n)
}
checkDualArgOp(lsh, bigLsh, x, y)
}
{ // opAdd
checkDualArgOp((*Int).Add, (*big.Int).Add, x, y)
}
{ // opSub
checkDualArgOp((*Int).Sub, (*big.Int).Sub, x, y)
}
return 1
}
func bigintMulMod(b1, b2, b3, b4 *big.Int) *big.Int {
return b1.Mod(big.NewInt(0).Mul(b2, b3), b4)
}
func intMulMod(f1, f2, f3, f4 *Int) *Int {
return f1.MulMod(f2, f3, f4)
}
func bigintAddMod(b1, b2, b3, b4 *big.Int) *big.Int {
return b1.Mod(big.NewInt(0).Add(b2, b3), b4)
}
func intAddMod(f1, f2, f3, f4 *Int) *Int {
return f1.AddMod(f2, f3, f4)
}
func bigintMulDiv(b1, b2, b3, b4 *big.Int) *big.Int {
b1.Mul(b2, b3)
return b1.Div(b1, b4)
}
func intMulDiv(f1, f2, f3, f4 *Int) *Int {
f1.MulDivOverflow(f2, f3, f4)
return f1
}
func fuzzTernaryOp(data []byte) int {
var x, y, z Int
x.SetBytes(data[:32])
y.SetBytes(data[32:64])
z.SetBytes(data[64:])
if z.IsZero() {
return 0
}
{ // mulMod
checkThreeArgOp(intMulMod, bigintMulMod, x, y, z)
}
{ // addMod
checkThreeArgOp(intAddMod, bigintAddMod, x, y, z)
}
{ // mulDiv
checkThreeArgOp(intMulDiv, bigintMulDiv, x, y, z)
}
return 1
}
// Test SetFromDecimal
func testSetFromDecForFuzzing(tc string) error {
a := new(Int).SetAllOne()
err := a.SetFromDecimal(tc)
// If input is negative, we should eror
if len(tc) > 0 && tc[0] == '-' {
if err == nil {
return fmt.Errorf("want error on negative input")
}
return nil
}
// Need to compare with big.Int
bigA, ok := big.NewInt(0).SetString(tc, 10)
if !ok {
if err == nil {
return fmt.Errorf("want error")
}
return nil // both agree that input is bad
}
if bigA.BitLen() > 256 {
if err == nil {
return fmt.Errorf("want error (bitlen > 256)")
}
return nil
}
want := bigA.String()
have := a.Dec()
if want != have {
return fmt.Errorf("want %v, have %v", want, have)
}
if _, err := a.Value(); err != nil {
return fmt.Errorf("fail to Value() %s, got err %s", tc, err)
}
return nil
}
func FuzzSetString(data []byte) int {
if len(data) > 512 {
// Too large, makes no sense
return -1
}
if err := testSetFromDecForFuzzing(string(data)); err != nil {
panic(err)
}
return 1
}
// uint256: Fixed size 256-bit math library
// Copyright 2021 uint256 Authors
// SPDX-License-Identifier: BSD-3-Clause
package uint256
import (
"math/bits"
)
// Reciprocal computes a 320-bit value representing 1/m
//
// Notes:
// - specialized for m[3] != 0, hence limited to 2^192 <= m < 2^256
// - returns zero if m[3] == 0
// - starts with a 32-bit division, refines with newton-raphson iterations
func Reciprocal(m *Int) (mu [5]uint64) {
if m[3] == 0 {
return mu
}
s := bits.LeadingZeros64(m[3]) // Replace with leadingZeros(m) for general case
p := 255 - s // floor(log_2(m)), m>0
// 0 or a power of 2?
// Check if at least one bit is set in m[2], m[1] or m[0],
// or at least two bits in m[3]
if m[0] | m[1] | m[2] | (m[3] & (m[3]-1)) == 0 {
mu[4] = ^uint64(0) >> uint(p & 63)
mu[3] = ^uint64(0)
mu[2] = ^uint64(0)
mu[1] = ^uint64(0)
mu[0] = ^uint64(0)
return mu
}
// Maximise division precision by left-aligning divisor
var (
y Int // left-aligned copy of m
r0 uint32 // estimate of 2^31/y
)
y.Lsh(m, uint(s)) // 1/2 < y < 1
// Extract most significant 32 bits
yh := uint32(y[3] >> 32)
if yh == 0x80000000 { // Avoid overflow in division
r0 = 0xffffffff
} else {
r0, _ = bits.Div32(0x80000000, 0, yh)
}
// First iteration: 32 -> 64
t1 := uint64(r0) // 2^31/y
t1 *= t1 // 2^62/y^2
t1, _ = bits.Mul64(t1, y[3]) // 2^62/y^2 * 2^64/y / 2^64 = 2^62/y
r1 := uint64(r0) << 32 // 2^63/y
r1 -= t1 // 2^63/y - 2^62/y = 2^62/y
r1 *= 2 // 2^63/y
if (r1 | (y[3]<<1)) == 0 {
r1 = ^uint64(0)
}
// Second iteration: 64 -> 128
// square: 2^126/y^2
a2h, a2l := bits.Mul64(r1, r1)
// multiply by y: e2h:e2l:b2h = 2^126/y^2 * 2^128/y / 2^128 = 2^126/y
b2h, _ := bits.Mul64(a2l, y[2])
c2h, c2l := bits.Mul64(a2l, y[3])
d2h, d2l := bits.Mul64(a2h, y[2])
e2h, e2l := bits.Mul64(a2h, y[3])
b2h, c := bits.Add64(b2h, c2l, 0)
e2l, c = bits.Add64(e2l, c2h, c)
e2h, _ = bits.Add64(e2h, 0, c)
_, c = bits.Add64(b2h, d2l, 0)
e2l, c = bits.Add64(e2l, d2h, c)
e2h, _ = bits.Add64(e2h, 0, c)
// subtract: t2h:t2l = 2^127/y - 2^126/y = 2^126/y
t2l, b := bits.Sub64( 0, e2l, 0)
t2h, _ := bits.Sub64(r1, e2h, b)
// double: r2h:r2l = 2^127/y
r2l, c := bits.Add64(t2l, t2l, 0)
r2h, _ := bits.Add64(t2h, t2h, c)
if (r2h | r2l | (y[3]<<1)) == 0 {
r2h = ^uint64(0)
r2l = ^uint64(0)
}
// Third iteration: 128 -> 192
// square r2 (keep 256 bits): 2^190/y^2
a3h, a3l := bits.Mul64(r2l, r2l)
b3h, b3l := bits.Mul64(r2l, r2h)
c3h, c3l := bits.Mul64(r2h, r2h)
a3h, c = bits.Add64(a3h, b3l, 0)
c3l, c = bits.Add64(c3l, b3h, c)
c3h, _ = bits.Add64(c3h, 0, c)
a3h, c = bits.Add64(a3h, b3l, 0)
c3l, c = bits.Add64(c3l, b3h, c)
c3h, _ = bits.Add64(c3h, 0, c)
// multiply by y: q = 2^190/y^2 * 2^192/y / 2^192 = 2^190/y
x0 := a3l
x1 := a3h
x2 := c3l
x3 := c3h
var q0, q1, q2, q3, q4, t0 uint64
q0, _ = bits.Mul64(x2, y[0])
q1, t0 = bits.Mul64(x3, y[0]); q0, c = bits.Add64(q0, t0, 0); q1, _ = bits.Add64(q1, 0, c)
t1, _ = bits.Mul64(x1, y[1]); q0, c = bits.Add64(q0, t1, 0)
q2, t0 = bits.Mul64(x3, y[1]); q1, c = bits.Add64(q1, t0, c); q2, _ = bits.Add64(q2, 0, c)
t1, t0 = bits.Mul64(x2, y[1]); q0, c = bits.Add64(q0, t0, 0); q1, c = bits.Add64(q1, t1, c); q2, _ = bits.Add64(q2, 0, c)
t1, t0 = bits.Mul64(x1, y[2]); q0, c = bits.Add64(q0, t0, 0); q1, c = bits.Add64(q1, t1, c)
q3, t0 = bits.Mul64(x3, y[2]); q2, c = bits.Add64(q2, t0, c); q3, _ = bits.Add64(q3, 0, c)
t1, _ = bits.Mul64(x0, y[2]); q0, c = bits.Add64(q0, t1, 0)
t1, t0 = bits.Mul64(x2, y[2]); q1, c = bits.Add64(q1, t0, c); q2, c = bits.Add64(q2, t1, c); q3, _ = bits.Add64(q3, 0, c)
t1, t0 = bits.Mul64(x1, y[3]); q1, c = bits.Add64(q1, t0, 0); q2, c = bits.Add64(q2, t1, c)
q4, t0 = bits.Mul64(x3, y[3]); q3, c = bits.Add64(q3, t0, c); q4, _ = bits.Add64(q4, 0, c)
t1, t0 = bits.Mul64(x0, y[3]); q0, c = bits.Add64(q0, t0, 0); q1, c = bits.Add64(q1, t1, c)
t1, t0 = bits.Mul64(x2, y[3]); q2, c = bits.Add64(q2, t0, c); q3, c = bits.Add64(q3, t1, c); q4, _ = bits.Add64(q4, 0, c)
// subtract: t3 = 2^191/y - 2^190/y = 2^190/y
_, b = bits.Sub64( 0, q0, 0)
_, b = bits.Sub64( 0, q1, b)
t3l, b := bits.Sub64( 0, q2, b)
t3m, b := bits.Sub64(r2l, q3, b)
t3h, _ := bits.Sub64(r2h, q4, b)
// double: r3 = 2^191/y
r3l, c := bits.Add64(t3l, t3l, 0)
r3m, c := bits.Add64(t3m, t3m, c)
r3h, _ := bits.Add64(t3h, t3h, c)
// Fourth iteration: 192 -> 320
// square r3
a4h, a4l := bits.Mul64(r3l, r3l)
b4h, b4l := bits.Mul64(r3l, r3m)
c4h, c4l := bits.Mul64(r3l, r3h)
d4h, d4l := bits.Mul64(r3m, r3m)
e4h, e4l := bits.Mul64(r3m, r3h)
f4h, f4l := bits.Mul64(r3h, r3h)
b4h, c = bits.Add64(b4h, c4l, 0)
e4l, c = bits.Add64(e4l, c4h, c)
e4h, _ = bits.Add64(e4h, 0, c)
a4h, c = bits.Add64(a4h, b4l, 0)
d4l, c = bits.Add64(d4l, b4h, c)
d4h, c = bits.Add64(d4h, e4l, c)
f4l, c = bits.Add64(f4l, e4h, c)
f4h, _ = bits.Add64(f4h, 0, c)
a4h, c = bits.Add64(a4h, b4l, 0)
d4l, c = bits.Add64(d4l, b4h, c)
d4h, c = bits.Add64(d4h, e4l, c)
f4l, c = bits.Add64(f4l, e4h, c)
f4h, _ = bits.Add64(f4h, 0, c)
// multiply by y
x1, x0 = bits.Mul64(d4h, y[0])
x3, x2 = bits.Mul64(f4h, y[0])
t1, t0 = bits.Mul64(f4l, y[0]); x1, c = bits.Add64(x1, t0, 0); x2, c = bits.Add64(x2, t1, c)
x3, _ = bits.Add64(x3, 0, c)
t1, t0 = bits.Mul64(d4h, y[1]); x1, c = bits.Add64(x1, t0, 0); x2, c = bits.Add64(x2, t1, c)
x4, t0 := bits.Mul64(f4h, y[1]); x3, c = bits.Add64(x3, t0, c); x4, _ = bits.Add64(x4, 0, c)
t1, t0 = bits.Mul64(d4l, y[1]); x0, c = bits.Add64(x0, t0, 0); x1, c = bits.Add64(x1, t1, c)
t1, t0 = bits.Mul64(f4l, y[1]); x2, c = bits.Add64(x2, t0, c); x3, c = bits.Add64(x3, t1, c)
x4, _ = bits.Add64(x4, 0, c)
t1, t0 = bits.Mul64(a4h, y[2]); x0, c = bits.Add64(x0, t0, 0); x1, c = bits.Add64(x1, t1, c)
t1, t0 = bits.Mul64(d4h, y[2]); x2, c = bits.Add64(x2, t0, c); x3, c = bits.Add64(x3, t1, c)
x5, t0 := bits.Mul64(f4h, y[2]); x4, c = bits.Add64(x4, t0, c); x5, _ = bits.Add64(x5, 0, c)
t1, t0 = bits.Mul64(d4l, y[2]); x1, c = bits.Add64(x1, t0, 0); x2, c = bits.Add64(x2, t1, c)
t1, t0 = bits.Mul64(f4l, y[2]); x3, c = bits.Add64(x3, t0, c); x4, c = bits.Add64(x4, t1, c)
x5, _ = bits.Add64(x5, 0, c)
t1, t0 = bits.Mul64(a4h, y[3]); x1, c = bits.Add64(x1, t0, 0); x2, c = bits.Add64(x2, t1, c)
t1, t0 = bits.Mul64(d4h, y[3]); x3, c = bits.Add64(x3, t0, c); x4, c = bits.Add64(x4, t1, c)
x6, t0 := bits.Mul64(f4h, y[3]); x5, c = bits.Add64(x5, t0, c); x6, _ = bits.Add64(x6, 0, c)
t1, t0 = bits.Mul64(a4l, y[3]); x0, c = bits.Add64(x0, t0, 0); x1, c = bits.Add64(x1, t1, c)
t1, t0 = bits.Mul64(d4l, y[3]); x2, c = bits.Add64(x2, t0, c); x3, c = bits.Add64(x3, t1, c)
t1, t0 = bits.Mul64(f4l, y[3]); x4, c = bits.Add64(x4, t0, c); x5, c = bits.Add64(x5, t1, c)
x6, _ = bits.Add64(x6, 0, c)
// subtract
_, b = bits.Sub64( 0, x0, 0)
_, b = bits.Sub64( 0, x1, b)
r4l, b := bits.Sub64( 0, x2, b)
r4k, b := bits.Sub64( 0, x3, b)
r4j, b := bits.Sub64(r3l, x4, b)
r4i, b := bits.Sub64(r3m, x5, b)
r4h, _ := bits.Sub64(r3h, x6, b)
// Multiply candidate for 1/4y by y, with full precision
x0 = r4l
x1 = r4k
x2 = r4j
x3 = r4i
x4 = r4h
q1, q0 = bits.Mul64(x0, y[0])
q3, q2 = bits.Mul64(x2, y[0])
q5, q4 := bits.Mul64(x4, y[0])
t1, t0 = bits.Mul64(x1, y[0]); q1, c = bits.Add64(q1, t0, 0); q2, c = bits.Add64(q2, t1, c)
t1, t0 = bits.Mul64(x3, y[0]); q3, c = bits.Add64(q3, t0, c); q4, c = bits.Add64(q4, t1, c); q5, _ = bits.Add64(q5, 0, c)
t1, t0 = bits.Mul64(x0, y[1]); q1, c = bits.Add64(q1, t0, 0); q2, c = bits.Add64(q2, t1, c)
t1, t0 = bits.Mul64(x2, y[1]); q3, c = bits.Add64(q3, t0, c); q4, c = bits.Add64(q4, t1, c)
q6, t0 := bits.Mul64(x4, y[1]); q5, c = bits.Add64(q5, t0, c); q6, _ = bits.Add64(q6, 0, c)
t1, t0 = bits.Mul64(x1, y[1]); q2, c = bits.Add64(q2, t0, 0); q3, c = bits.Add64(q3, t1, c)
t1, t0 = bits.Mul64(x3, y[1]); q4, c = bits.Add64(q4, t0, c); q5, c = bits.Add64(q5, t1, c); q6, _ = bits.Add64(q6, 0, c)
t1, t0 = bits.Mul64(x0, y[2]); q2, c = bits.Add64(q2, t0, 0); q3, c = bits.Add64(q3, t1, c)
t1, t0 = bits.Mul64(x2, y[2]); q4, c = bits.Add64(q4, t0, c); q5, c = bits.Add64(q5, t1, c)
q7, t0 := bits.Mul64(x4, y[2]); q6, c = bits.Add64(q6, t0, c); q7, _ = bits.Add64(q7, 0, c)
t1, t0 = bits.Mul64(x1, y[2]); q3, c = bits.Add64(q3, t0, 0); q4, c = bits.Add64(q4, t1, c)
t1, t0 = bits.Mul64(x3, y[2]); q5, c = bits.Add64(q5, t0, c); q6, c = bits.Add64(q6, t1, c); q7, _ = bits.Add64(q7, 0, c)
t1, t0 = bits.Mul64(x0, y[3]); q3, c = bits.Add64(q3, t0, 0); q4, c = bits.Add64(q4, t1, c)
t1, t0 = bits.Mul64(x2, y[3]); q5, c = bits.Add64(q5, t0, c); q6, c = bits.Add64(q6, t1, c)
q8, t0 := bits.Mul64(x4, y[3]); q7, c = bits.Add64(q7, t0, c); q8, _ = bits.Add64(q8, 0, c)
t1, t0 = bits.Mul64(x1, y[3]); q4, c = bits.Add64(q4, t0, 0); q5, c = bits.Add64(q5, t1, c)
t1, t0 = bits.Mul64(x3, y[3]); q6, c = bits.Add64(q6, t0, c); q7, c = bits.Add64(q7, t1, c); q8, _ = bits.Add64(q8, 0, c)
// Final adjustment
// subtract q from 1/4
_, b = bits.Sub64(0, q0, 0)
_, b = bits.Sub64(0, q1, b)
_, b = bits.Sub64(0, q2, b)
_, b = bits.Sub64(0, q3, b)
_, b = bits.Sub64(0, q4, b)
_, b = bits.Sub64(0, q5, b)
_, b = bits.Sub64(0, q6, b)
_, b = bits.Sub64(0, q7, b)
_, b = bits.Sub64(uint64(1) << 62, q8, b)
// decrement the result
x0, t := bits.Sub64(r4l, 1, 0)
x1, t = bits.Sub64(r4k, 0, t)
x2, t = bits.Sub64(r4j, 0, t)
x3, t = bits.Sub64(r4i, 0, t)
x4, _ = bits.Sub64(r4h, 0, t)
// commit the decrement if the subtraction underflowed (reciprocal was too large)
if b != 0 {
r4h, r4i, r4j, r4k, r4l = x4, x3, x2, x1, x0
}
// Shift to correct bit alignment, truncating excess bits
p = (p & 63) - 1
x0, c = bits.Add64(r4l, r4l, 0)
x1, c = bits.Add64(r4k, r4k, c)
x2, c = bits.Add64(r4j, r4j, c)
x3, c = bits.Add64(r4i, r4i, c)
x4, _ = bits.Add64(r4h, r4h, c)
if p < 0 {
r4h, r4i, r4j, r4k, r4l = x4, x3, x2, x1, x0
p = 0 // avoid negative shift below
}
{
r := uint(p) // right shift
l := uint(64 - r) // left shift
x0 = (r4l >> r) | (r4k << l)
x1 = (r4k >> r) | (r4j << l)
x2 = (r4j >> r) | (r4i << l)
x3 = (r4i >> r) | (r4h << l)
x4 = (r4h >> r)
}
if p > 0 {
r4h, r4i, r4j, r4k, r4l = x4, x3, x2, x1, x0
}
mu[0] = r4l
mu[1] = r4k
mu[2] = r4j
mu[3] = r4i
mu[4] = r4h
return mu
}
// reduce4 computes the least non-negative residue of x modulo m
//
// requires a four-word modulus (m[3] > 1) and its inverse (mu)
func reduce4(x [8]uint64, m *Int, mu [5]uint64) (z Int) {
// NB: Most variable names in the comments match the pseudocode for
// Barrett reduction in the Handbook of Applied Cryptography.
// q1 = x/2^192
x0 := x[3]
x1 := x[4]
x2 := x[5]
x3 := x[6]
x4 := x[7]
// q2 = q1 * mu; q3 = q2 / 2^320
var q0, q1, q2, q3, q4, q5, t0, t1, c uint64
q0, _ = bits.Mul64(x3, mu[0])
q1, t0 = bits.Mul64(x4, mu[0]); q0, c = bits.Add64(q0, t0, 0); q1, _ = bits.Add64(q1, 0, c)
t1, _ = bits.Mul64(x2, mu[1]); q0, c = bits.Add64(q0, t1, 0)
q2, t0 = bits.Mul64(x4, mu[1]); q1, c = bits.Add64(q1, t0, c); q2, _ = bits.Add64(q2, 0, c)
t1, t0 = bits.Mul64(x3, mu[1]); q0, c = bits.Add64(q0, t0, 0); q1, c = bits.Add64(q1, t1, c); q2, _ = bits.Add64(q2, 0, c)
t1, t0 = bits.Mul64(x2, mu[2]); q0, c = bits.Add64(q0, t0, 0); q1, c = bits.Add64(q1, t1, c)
q3, t0 = bits.Mul64(x4, mu[2]); q2, c = bits.Add64(q2, t0, c); q3, _ = bits.Add64(q3, 0, c)
t1, _ = bits.Mul64(x1, mu[2]); q0, c = bits.Add64(q0, t1, 0)
t1, t0 = bits.Mul64(x3, mu[2]); q1, c = bits.Add64(q1, t0, c); q2, c = bits.Add64(q2, t1, c); q3, _ = bits.Add64(q3, 0, c)
t1, _ = bits.Mul64(x0, mu[3]); q0, c = bits.Add64(q0, t1, 0)
t1, t0 = bits.Mul64(x2, mu[3]); q1, c = bits.Add64(q1, t0, c); q2, c = bits.Add64(q2, t1, c)
q4, t0 = bits.Mul64(x4, mu[3]); q3, c = bits.Add64(q3, t0, c); q4, _ = bits.Add64(q4, 0, c)
t1, t0 = bits.Mul64(x1, mu[3]); q0, c = bits.Add64(q0, t0, 0); q1, c = bits.Add64(q1, t1, c)
t1, t0 = bits.Mul64(x3, mu[3]); q2, c = bits.Add64(q2, t0, c); q3, c = bits.Add64(q3, t1, c); q4, _ = bits.Add64(q4, 0, c)
t1, t0 = bits.Mul64(x0, mu[4]); _, c = bits.Add64(q0, t0, 0); q1, c = bits.Add64(q1, t1, c)
t1, t0 = bits.Mul64(x2, mu[4]); q2, c = bits.Add64(q2, t0, c); q3, c = bits.Add64(q3, t1, c)
q5, t0 = bits.Mul64(x4, mu[4]); q4, c = bits.Add64(q4, t0, c); q5, _ = bits.Add64(q5, 0, c)
t1, t0 = bits.Mul64(x1, mu[4]); q1, c = bits.Add64(q1, t0, 0); q2, c = bits.Add64(q2, t1, c)
t1, t0 = bits.Mul64(x3, mu[4]); q3, c = bits.Add64(q3, t0, c); q4, c = bits.Add64(q4, t1, c); q5, _ = bits.Add64(q5, 0, c)
// Drop the fractional part of q3
q0 = q1
q1 = q2
q2 = q3
q3 = q4
q4 = q5
// r1 = x mod 2^320
x0 = x[0]
x1 = x[1]
x2 = x[2]
x3 = x[3]
x4 = x[4]
// r2 = q3 * m mod 2^320
var r0, r1, r2, r3, r4 uint64
r4, r3 = bits.Mul64(q0, m[3])
_, t0 = bits.Mul64(q1, m[3]); r4, _ = bits.Add64(r4, t0, 0)
t1, r2 = bits.Mul64(q0, m[2]); r3, c = bits.Add64(r3, t1, 0)
_, t0 = bits.Mul64(q2, m[2]); r4, _ = bits.Add64(r4, t0, c)
t1, t0 = bits.Mul64(q1, m[2]); r3, c = bits.Add64(r3, t0, 0); r4, _ = bits.Add64(r4, t1, c)
t1, r1 = bits.Mul64(q0, m[1]); r2, c = bits.Add64(r2, t1, 0)
t1, t0 = bits.Mul64(q2, m[1]); r3, c = bits.Add64(r3, t0, c); r4, _ = bits.Add64(r4, t1, c)
t1, t0 = bits.Mul64(q1, m[1]); r2, c = bits.Add64(r2, t0, 0); r3, c = bits.Add64(r3, t1, c)
_, t0 = bits.Mul64(q3, m[1]); r4, _ = bits.Add64(r4, t0, c)
t1, r0 = bits.Mul64(q0, m[0]); r1, c = bits.Add64(r1, t1, 0)
t1, t0 = bits.Mul64(q2, m[0]); r2, c = bits.Add64(r2, t0, c); r3, c = bits.Add64(r3, t1, c)
_, t0 = bits.Mul64(q4, m[0]); r4, _ = bits.Add64(r4, t0, c)
t1, t0 = bits.Mul64(q1, m[0]); r1, c = bits.Add64(r1, t0, 0); r2, c = bits.Add64(r2, t1, c)
t1, t0 = bits.Mul64(q3, m[0]); r3, c = bits.Add64(r3, t0, c); r4, _ = bits.Add64(r4, t1, c)
// r = r1 - r2
var b uint64
r0, b = bits.Sub64(x0, r0, 0)
r1, b = bits.Sub64(x1, r1, b)
r2, b = bits.Sub64(x2, r2, b)
r3, b = bits.Sub64(x3, r3, b)
r4, b = bits.Sub64(x4, r4, b)
// if r<0 then r+=m
if b != 0 {
r0, c = bits.Add64(r0, m[0], 0)
r1, c = bits.Add64(r1, m[1], c)
r2, c = bits.Add64(r2, m[2], c)
r3, c = bits.Add64(r3, m[3], c)
r4, _ = bits.Add64(r4, 0, c)
}
// while (r>=m) r-=m
for {
// q = r - m
q0, b = bits.Sub64(r0, m[0], 0)
q1, b = bits.Sub64(r1, m[1], b)
q2, b = bits.Sub64(r2, m[2], b)
q3, b = bits.Sub64(r3, m[3], b)
q4, b = bits.Sub64(r4, 0, b)
// if borrow break
if b != 0 {
break
}
// r = q
r4, r3, r2, r1, r0 = q4, q3, q2, q1, q0
}
z[3], z[2], z[1], z[0] = r3, r2, r1, r0
return z
}
// uint256: Fixed size 256-bit math library
// Copyright 2018-2020 uint256 Authors
// SPDX-License-Identifier: BSD-3-Clause
// Package math provides integer math utilities.
package uint256
import (
"encoding/binary"
"math"
"math/big"
"math/bits"
)
// Int is represented as an array of 4 uint64, in little-endian order,
// so that Int[3] is the most significant, and Int[0] is the least significant
type Int [4]uint64
// NewInt returns a new initialized Int.
func NewInt(val uint64) *Int {
z := &Int{}
z.SetUint64(val)
return z
}
// SetBytes interprets buf as the bytes of a big-endian unsigned
// integer, sets z to that value, and returns z.
// If buf is larger than 32 bytes, the last 32 bytes is used. This operation
// is semantically equivalent to `FromBig(new(big.Int).SetBytes(buf))`
func (z *Int) SetBytes(buf []byte) *Int {
switch l := len(buf); l {
case 0:
z.Clear()
case 1:
z.SetBytes1(buf)
case 2:
z.SetBytes2(buf)
case 3:
z.SetBytes3(buf)
case 4:
z.SetBytes4(buf)
case 5:
z.SetBytes5(buf)
case 6:
z.SetBytes6(buf)
case 7:
z.SetBytes7(buf)
case 8:
z.SetBytes8(buf)
case 9:
z.SetBytes9(buf)
case 10:
z.SetBytes10(buf)
case 11:
z.SetBytes11(buf)
case 12:
z.SetBytes12(buf)
case 13:
z.SetBytes13(buf)
case 14:
z.SetBytes14(buf)
case 15:
z.SetBytes15(buf)
case 16:
z.SetBytes16(buf)
case 17:
z.SetBytes17(buf)
case 18:
z.SetBytes18(buf)
case 19:
z.SetBytes19(buf)
case 20:
z.SetBytes20(buf)
case 21:
z.SetBytes21(buf)
case 22:
z.SetBytes22(buf)
case 23:
z.SetBytes23(buf)
case 24:
z.SetBytes24(buf)
case 25:
z.SetBytes25(buf)
case 26:
z.SetBytes26(buf)
case 27:
z.SetBytes27(buf)
case 28:
z.SetBytes28(buf)
case 29:
z.SetBytes29(buf)
case 30:
z.SetBytes30(buf)
case 31:
z.SetBytes31(buf)
default:
z.SetBytes32(buf[l-32:])
}
return z
}
// Bytes32 returns the value of z as a 32-byte big-endian array.
func (z *Int) Bytes32() [32]byte {
// The PutUint64()s are inlined and we get 4x (load, bswap, store) instructions.
var b [32]byte
binary.BigEndian.PutUint64(b[0:8], z[3])
binary.BigEndian.PutUint64(b[8:16], z[2])
binary.BigEndian.PutUint64(b[16:24], z[1])
binary.BigEndian.PutUint64(b[24:32], z[0])
return b
}
// Bytes20 returns the value of z as a 20-byte big-endian array.
func (z *Int) Bytes20() [20]byte {
var b [20]byte
// The PutUint*()s are inlined and we get 3x (load, bswap, store) instructions.
binary.BigEndian.PutUint32(b[0:4], uint32(z[2]))
binary.BigEndian.PutUint64(b[4:12], z[1])
binary.BigEndian.PutUint64(b[12:20], z[0])
return b
}
// Bytes returns the value of z as a big-endian byte slice.
func (z *Int) Bytes() []byte {
b := z.Bytes32()
return b[32-z.ByteLen():]
}
// WriteToSlice writes the content of z into the given byteslice.
// If dest is larger than 32 bytes, z will fill the first parts, and leave
// the end untouched.
// OBS! If dest is smaller than 32 bytes, only the end parts of z will be used
// for filling the array, making it useful for filling an Address object
func (z *Int) WriteToSlice(dest []byte) {
// ensure 32 bytes
// A too large buffer. Fill last 32 bytes
end := len(dest) - 1
if end > 31 {
end = 31
}
for i := 0; i <= end; i++ {
dest[end-i] = byte(z[i/8] >> uint64(8*(i%8)))
}
}
// WriteToArray32 writes all 32 bytes of z to the destination array, including zero-bytes
func (z *Int) WriteToArray32(dest *[32]byte) {
for i := 0; i < 32; i++ {
dest[31-i] = byte(z[i/8] >> uint64(8*(i%8)))
}
}
// WriteToArray20 writes the last 20 bytes of z to the destination array, including zero-bytes
func (z *Int) WriteToArray20(dest *[20]byte) {
for i := 0; i < 20; i++ {
dest[19-i] = byte(z[i/8] >> uint64(8*(i%8)))
}
}
// Uint64 returns the lower 64-bits of z
func (z *Int) Uint64() uint64 {
return z[0]
}
// Uint64WithOverflow returns the lower 64-bits of z and bool whether overflow occurred
func (z *Int) Uint64WithOverflow() (uint64, bool) {
return z[0], (z[1] | z[2] | z[3]) != 0
}
// Clone creates a new Int identical to z
func (z *Int) Clone() *Int {
return &Int{z[0], z[1], z[2], z[3]}
}
// Add sets z to the sum x+y
func (z *Int) Add(x, y *Int) *Int {
var carry uint64
z[0], carry = bits.Add64(x[0], y[0], 0)
z[1], carry = bits.Add64(x[1], y[1], carry)
z[2], carry = bits.Add64(x[2], y[2], carry)
z[3], _ = bits.Add64(x[3], y[3], carry)
return z
}
// AddOverflow sets z to the sum x+y, and returns z and whether overflow occurred
func (z *Int) AddOverflow(x, y *Int) (*Int, bool) {
var carry uint64
z[0], carry = bits.Add64(x[0], y[0], 0)
z[1], carry = bits.Add64(x[1], y[1], carry)
z[2], carry = bits.Add64(x[2], y[2], carry)
z[3], carry = bits.Add64(x[3], y[3], carry)
return z, carry != 0
}
// AddMod sets z to the sum ( x+y ) mod m, and returns z.
// If m == 0, z is set to 0 (OBS: differs from the big.Int)
func (z *Int) AddMod(x, y, m *Int) *Int {
// Fast path for m >= 2^192, with x and y at most slightly bigger than m.
// This is always the case when x and y are already reduced modulo such m.
if (m[3] != 0) && (x[3] <= m[3]) && (y[3] <= m[3]) {
var (
gteC1 uint64
gteC2 uint64
tmpX Int
tmpY Int
res Int
)
// reduce x/y modulo m if they are gte m
tmpX[0], gteC1 = bits.Sub64(x[0], m[0], gteC1)
tmpX[1], gteC1 = bits.Sub64(x[1], m[1], gteC1)
tmpX[2], gteC1 = bits.Sub64(x[2], m[2], gteC1)
tmpX[3], gteC1 = bits.Sub64(x[3], m[3], gteC1)
tmpY[0], gteC2 = bits.Sub64(y[0], m[0], gteC2)
tmpY[1], gteC2 = bits.Sub64(y[1], m[1], gteC2)
tmpY[2], gteC2 = bits.Sub64(y[2], m[2], gteC2)
tmpY[3], gteC2 = bits.Sub64(y[3], m[3], gteC2)
if gteC1 == 0 {
x = &tmpX
}
if gteC2 == 0 {
y = &tmpY
}
var (
c1 uint64
c2 uint64
tmp Int
)
res[0], c1 = bits.Add64(x[0], y[0], c1)
res[1], c1 = bits.Add64(x[1], y[1], c1)
res[2], c1 = bits.Add64(x[2], y[2], c1)
res[3], c1 = bits.Add64(x[3], y[3], c1)
tmp[0], c2 = bits.Sub64(res[0], m[0], c2)
tmp[1], c2 = bits.Sub64(res[1], m[1], c2)
tmp[2], c2 = bits.Sub64(res[2], m[2], c2)
tmp[3], c2 = bits.Sub64(res[3], m[3], c2)
// final sub was unnecessary
if c1 == 0 && c2 != 0 {
copy((*z)[:], res[:])
return z
}
copy((*z)[:], tmp[:])
return z
}
if m.IsZero() {
return z.Clear()
}
if z == m { // z is an alias for m and will be overwritten by AddOverflow before m is read
m = m.Clone()
}
if _, overflow := z.AddOverflow(x, y); overflow {
sum := [5]uint64{z[0], z[1], z[2], z[3], 1}
var quot [5]uint64
rem := udivrem(quot[:], sum[:], m)
return z.Set(&rem)
}
return z.Mod(z, m)
}
// AddUint64 sets z to x + y, where y is a uint64, and returns z
func (z *Int) AddUint64(x *Int, y uint64) *Int {
var carry uint64
z[0], carry = bits.Add64(x[0], y, 0)
z[1], carry = bits.Add64(x[1], 0, carry)
z[2], carry = bits.Add64(x[2], 0, carry)
z[3], _ = bits.Add64(x[3], 0, carry)
return z
}
// PaddedBytes encodes a Int as a 0-padded byte slice. The length
// of the slice is at least n bytes.
// Example, z =1, n = 20 => [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
func (z *Int) PaddedBytes(n int) []byte {
b := make([]byte, n)
for i := 0; i < 32 && i < n; i++ {
b[n-1-i] = byte(z[i/8] >> uint64(8*(i%8)))
}
return b
}
// SubUint64 set z to the difference x - y, where y is a uint64, and returns z
func (z *Int) SubUint64(x *Int, y uint64) *Int {
var carry uint64
z[0], carry = bits.Sub64(x[0], y, carry)
z[1], carry = bits.Sub64(x[1], 0, carry)
z[2], carry = bits.Sub64(x[2], 0, carry)
z[3], _ = bits.Sub64(x[3], 0, carry)
return z
}
// SubOverflow sets z to the difference x-y and returns z and true if the operation underflowed
func (z *Int) SubOverflow(x, y *Int) (*Int, bool) {
var carry uint64
z[0], carry = bits.Sub64(x[0], y[0], 0)
z[1], carry = bits.Sub64(x[1], y[1], carry)
z[2], carry = bits.Sub64(x[2], y[2], carry)
z[3], carry = bits.Sub64(x[3], y[3], carry)
return z, carry != 0
}
// Sub sets z to the difference x-y
func (z *Int) Sub(x, y *Int) *Int {
var carry uint64
z[0], carry = bits.Sub64(x[0], y[0], 0)
z[1], carry = bits.Sub64(x[1], y[1], carry)
z[2], carry = bits.Sub64(x[2], y[2], carry)
z[3], _ = bits.Sub64(x[3], y[3], carry)
return z
}
// umulStep computes (hi * 2^64 + lo) = z + (x * y) + carry.
func umulStep(z, x, y, carry uint64) (hi, lo uint64) {
hi, lo = bits.Mul64(x, y)
lo, carry = bits.Add64(lo, carry, 0)
hi, _ = bits.Add64(hi, 0, carry)
lo, carry = bits.Add64(lo, z, 0)
hi, _ = bits.Add64(hi, 0, carry)
return hi, lo
}
// umulHop computes (hi * 2^64 + lo) = z + (x * y)
func umulHop(z, x, y uint64) (hi, lo uint64) {
hi, lo = bits.Mul64(x, y)
lo, carry := bits.Add64(lo, z, 0)
hi, _ = bits.Add64(hi, 0, carry)
return hi, lo
}
// umul computes full 256 x 256 -> 512 multiplication.
func umul(x, y *Int) [8]uint64 {
var (
res [8]uint64
carry, carry4, carry5, carry6 uint64
res1, res2, res3, res4, res5 uint64
)
carry, res[0] = bits.Mul64(x[0], y[0])
carry, res1 = umulHop(carry, x[1], y[0])
carry, res2 = umulHop(carry, x[2], y[0])
carry4, res3 = umulHop(carry, x[3], y[0])
carry, res[1] = umulHop(res1, x[0], y[1])
carry, res2 = umulStep(res2, x[1], y[1], carry)
carry, res3 = umulStep(res3, x[2], y[1], carry)
carry5, res4 = umulStep(carry4, x[3], y[1], carry)
carry, res[2] = umulHop(res2, x[0], y[2])
carry, res3 = umulStep(res3, x[1], y[2], carry)
carry, res4 = umulStep(res4, x[2], y[2], carry)
carry6, res5 = umulStep(carry5, x[3], y[2], carry)
carry, res[3] = umulHop(res3, x[0], y[3])
carry, res[4] = umulStep(res4, x[1], y[3], carry)
carry, res[5] = umulStep(res5, x[2], y[3], carry)
res[7], res[6] = umulStep(carry6, x[3], y[3], carry)
return res
}
// Mul sets z to the product x*y
func (z *Int) Mul(x, y *Int) *Int {
var (
carry uint64
res0, res1, res2, res3 uint64
)
carry, res0 = bits.Mul64(x[0], y[0])
carry, res1 = umulHop(carry, x[1], y[0])
carry, res2 = umulHop(carry, x[2], y[0])
res3 = x[3]*y[0] + carry
carry, res1 = umulHop(res1, x[0], y[1])
carry, res2 = umulStep(res2, x[1], y[1], carry)
res3 = res3 + x[2]*y[1] + carry
carry, res2 = umulHop(res2, x[0], y[2])
res3 = res3 + x[1]*y[2] + carry
res3 = res3 + x[0]*y[3]
z[0], z[1], z[2], z[3] = res0, res1, res2, res3
return z
}
// MulOverflow sets z to the product x*y, and returns z and whether overflow occurred
func (z *Int) MulOverflow(x, y *Int) (*Int, bool) {
p := umul(x, y)
copy(z[:], p[:4])
return z, (p[4] | p[5] | p[6] | p[7]) != 0
}
func (z *Int) squared() {
var (
carry0, carry1, carry2 uint64
res0, res1, res2, res3 uint64
)
carry0, res0 = bits.Mul64(z[0], z[0])
carry0, res1 = umulHop(carry0, z[0], z[1])
carry0, res2 = umulHop(carry0, z[0], z[2])
carry1, res1 = umulHop(res1, z[0], z[1])
carry1, res2 = umulStep(res2, z[1], z[1], carry1)
carry2, res2 = umulHop(res2, z[0], z[2])
res3 = 2*(z[0]*z[3]+z[1]*z[2]) + carry0 + carry1 + carry2
z[0], z[1], z[2], z[3] = res0, res1, res2, res3
}
// isBitSet returns true if bit n-th is set, where n = 0 is LSB.
// The n must be <= 255.
func (z *Int) isBitSet(n uint) bool {
return (z[n/64] & (1 << (n % 64))) != 0
}
// addTo computes x += y.
// Requires len(x) >= len(y).
func addTo(x, y []uint64) uint64 {
var carry uint64
for i := 0; i < len(y); i++ {
x[i], carry = bits.Add64(x[i], y[i], carry)
}
return carry
}
// subMulTo computes x -= y * multiplier.
// Requires len(x) >= len(y).
func subMulTo(x, y []uint64, multiplier uint64) uint64 {
var borrow uint64
for i := 0; i < len(y); i++ {
s, carry1 := bits.Sub64(x[i], borrow, 0)
ph, pl := bits.Mul64(y[i], multiplier)
t, carry2 := bits.Sub64(s, pl, 0)
x[i] = t
borrow = ph + carry1 + carry2
}
return borrow
}
// udivremBy1 divides u by single normalized word d and produces both quotient and remainder.
// The quotient is stored in provided quot.
func udivremBy1(quot, u []uint64, d uint64) (rem uint64) {
reciprocal := reciprocal2by1(d)
rem = u[len(u)-1] // Set the top word as remainder.
for j := len(u) - 2; j >= 0; j-- {
quot[j], rem = udivrem2by1(rem, u[j], d, reciprocal)
}
return rem
}
// udivremKnuth implements the division of u by normalized multiple word d from the Knuth's division algorithm.
// The quotient is stored in provided quot - len(u)-len(d) words.
// Updates u to contain the remainder - len(d) words.
func udivremKnuth(quot, u, d []uint64) {
dh := d[len(d)-1]
dl := d[len(d)-2]
reciprocal := reciprocal2by1(dh)
for j := len(u) - len(d) - 1; j >= 0; j-- {
u2 := u[j+len(d)]
u1 := u[j+len(d)-1]
u0 := u[j+len(d)-2]
var qhat, rhat uint64
if u2 >= dh { // Division overflows.
qhat = ^uint64(0)
// TODO: Add "qhat one to big" adjustment (not needed for correctness, but helps avoiding "add back" case).
} else {
qhat, rhat = udivrem2by1(u2, u1, dh, reciprocal)
ph, pl := bits.Mul64(qhat, dl)
if ph > rhat || (ph == rhat && pl > u0) {
qhat--
// TODO: Add "qhat one to big" adjustment (not needed for correctness, but helps avoiding "add back" case).
}
}
// Multiply and subtract.
borrow := subMulTo(u[j:], d, qhat)
u[j+len(d)] = u2 - borrow
if u2 < borrow { // Too much subtracted, add back.
qhat--
u[j+len(d)] += addTo(u[j:], d)
}
quot[j] = qhat // Store quotient digit.
}
}
// udivrem divides u by d and produces both quotient and remainder.
// The quotient is stored in provided quot - len(u)-len(d)+1 words.
// It loosely follows the Knuth's division algorithm (sometimes referenced as "schoolbook" division) using 64-bit words.
// See Knuth, Volume 2, section 4.3.1, Algorithm D.
func udivrem(quot, u []uint64, d *Int) (rem Int) {
var dLen int
for i := len(d) - 1; i >= 0; i-- {
if d[i] != 0 {
dLen = i + 1
break
}
}
shift := uint(bits.LeadingZeros64(d[dLen-1]))
var dnStorage Int
dn := dnStorage[:dLen]
for i := dLen - 1; i > 0; i-- {
dn[i] = (d[i] << shift) | (d[i-1] >> (64 - shift))
}
dn[0] = d[0] << shift
var uLen int
for i := len(u) - 1; i >= 0; i-- {
if u[i] != 0 {
uLen = i + 1
break
}
}
if uLen < dLen {
copy(rem[:], u)
return rem
}
var unStorage [9]uint64
un := unStorage[:uLen+1]
un[uLen] = u[uLen-1] >> (64 - shift)
for i := uLen - 1; i > 0; i-- {
un[i] = (u[i] << shift) | (u[i-1] >> (64 - shift))
}
un[0] = u[0] << shift
// TODO: Skip the highest word of numerator if not significant.
if dLen == 1 {
r := udivremBy1(quot, un, dn[0])
rem.SetUint64(r >> shift)
return rem
}
udivremKnuth(quot, un, dn)
for i := 0; i < dLen-1; i++ {
rem[i] = (un[i] >> shift) | (un[i+1] << (64 - shift))
}
rem[dLen-1] = un[dLen-1] >> shift
return rem
}
// Div sets z to the quotient x/y for returns z.
// If y == 0, z is set to 0
func (z *Int) Div(x, y *Int) *Int {
if y.IsZero() || y.Gt(x) {
return z.Clear()
}
if x.Eq(y) {
return z.SetOne()
}
// Shortcut some cases
if x.IsUint64() {
return z.SetUint64(x.Uint64() / y.Uint64())
}
// At this point, we know
// x/y ; x > y > 0
var quot Int
udivrem(quot[:], x[:], y)
return z.Set(")
}
// Mod sets z to the modulus x%y for y != 0 and returns z.
// If y == 0, z is set to 0 (OBS: differs from the big.Int)
func (z *Int) Mod(x, y *Int) *Int {
if x.IsZero() || y.IsZero() {
return z.Clear()
}
switch x.Cmp(y) {
case -1:
// x < y
return z.Set(x)
case 0:
// x == y
return z.Clear() // They are equal
}
// At this point:
// x != 0
// y != 0
// x > y
// Shortcut trivial case
if x.IsUint64() {
return z.SetUint64(x.Uint64() % y.Uint64())
}
var quot Int
*z = udivrem(quot[:], x[:], y)
return z
}
// DivMod sets z to the quotient x div y and m to the modulus x mod y and returns the pair (z, m) for y != 0.
// If y == 0, both z and m are set to 0 (OBS: differs from the big.Int)
func (z *Int) DivMod(x, y, m *Int) (*Int, *Int) {
if y.IsZero() {
return z.Clear(), m.Clear()
}
switch x.Cmp(y) {
case -1:
// x < y
return z.Clear(), m.Set(x)
case 0:
// x == y
return z.SetOne(), m.Clear()
}
// At this point:
// x != 0
// y != 0
// x > y
// Shortcut trivial case
if x.IsUint64() {
x0, y0 := x.Uint64(), y.Uint64()
return z.SetUint64(x0 / y0), m.SetUint64(x0 % y0)
}
var quot Int
*m = udivrem(quot[:], x[:], y)
*z = quot
return z, m
}
// SMod interprets x and y as two's complement signed integers,
// sets z to (sign x) * { abs(x) modulus abs(y) }
// If y == 0, z is set to 0 (OBS: differs from the big.Int)
func (z *Int) SMod(x, y *Int) *Int {
ys := y.Sign()
xs := x.Sign()
// abs x
if xs == -1 {
x = new(Int).Neg(x)
}
// abs y
if ys == -1 {
y = new(Int).Neg(y)
}
z.Mod(x, y)
if xs == -1 {
z.Neg(z)
}
return z
}
// MulModWithReciprocal calculates the modulo-m multiplication of x and y
// and returns z, using the reciprocal of m provided as the mu parameter.
// Use uint256.Reciprocal to calculate mu from m.
// If m == 0, z is set to 0 (OBS: differs from the big.Int)
func (z *Int) MulModWithReciprocal(x, y, m *Int, mu *[5]uint64) *Int {
if x.IsZero() || y.IsZero() || m.IsZero() {
return z.Clear()
}
p := umul(x, y)
if m[3] != 0 {
r := reduce4(p, m, *mu)
return z.Set(&r)
}
var (
pl Int
ph Int
)
copy(pl[:], p[:4])
copy(ph[:], p[4:])
// If the multiplication is within 256 bits use Mod().
if ph.IsZero() {
return z.Mod(&pl, m)
}
var quot [8]uint64
rem := udivrem(quot[:], p[:], m)
return z.Set(&rem)
}
// MulMod calculates the modulo-m multiplication of x and y and
// returns z.
// If m == 0, z is set to 0 (OBS: differs from the big.Int)
func (z *Int) MulMod(x, y, m *Int) *Int {
if x.IsZero() || y.IsZero() || m.IsZero() {
return z.Clear()
}
p := umul(x, y)
if m[3] != 0 {
mu := Reciprocal(m)
r := reduce4(p, m, mu)
return z.Set(&r)
}
var (
pl Int
ph Int
)
copy(pl[:], p[:4])
copy(ph[:], p[4:])
// If the multiplication is within 256 bits use Mod().
if ph.IsZero() {
return z.Mod(&pl, m)
}
var quot [8]uint64
rem := udivrem(quot[:], p[:], m)
return z.Set(&rem)
}
// MulDivOverflow calculates (x*y)/d with full precision, returns z and whether overflow occurred in multiply process (result does not fit to 256-bit).
// computes 512-bit multiplication and 512 by 256 division.
func (z *Int) MulDivOverflow(x, y, d *Int) (*Int, bool) {
if x.IsZero() || y.IsZero() || d.IsZero() {
return z.Clear(), false
}
p := umul(x, y)
var quot [8]uint64
udivrem(quot[:], p[:], d)
copy(z[:], quot[:4])
return z, (quot[4] | quot[5] | quot[6] | quot[7]) != 0
}
// Abs interprets x as a two's complement signed number,
// and sets z to the absolute value
//
// Abs(0) = 0
// Abs(1) = 1
// Abs(2**255) = -2**255
// Abs(2**256-1) = -1
func (z *Int) Abs(x *Int) *Int {
if x[3] < 0x8000000000000000 {
return z.Set(x)
}
return z.Sub(new(Int), x)
}
// Neg returns -x mod 2**256.
func (z *Int) Neg(x *Int) *Int {
return z.Sub(new(Int), x)
}
// SDiv interprets n and d as two's complement signed integers,
// does a signed division on the two operands and sets z to the result.
// If d == 0, z is set to 0
func (z *Int) SDiv(n, d *Int) *Int {
if n.Sign() > 0 {
if d.Sign() > 0 {
// pos / pos
z.Div(n, d)
return z
} else {
// pos / neg
z.Div(n, new(Int).Neg(d))
return z.Neg(z)
}
}
if d.Sign() < 0 {
// neg / neg
z.Div(new(Int).Neg(n), new(Int).Neg(d))
return z
}
// neg / pos
z.Div(new(Int).Neg(n), d)
return z.Neg(z)
}
// Sign returns:
//
// -1 if z < 0
// 0 if z == 0
// +1 if z > 0
//
// Where z is interpreted as a two's complement signed number
func (z *Int) Sign() int {
if z.IsZero() {
return 0
}
if z[3] < 0x8000000000000000 {
return 1
}
return -1
}
// BitLen returns the number of bits required to represent z
func (z *Int) BitLen() int {
switch {
case z[3] != 0:
return 192 + bits.Len64(z[3])
case z[2] != 0:
return 128 + bits.Len64(z[2])
case z[1] != 0:
return 64 + bits.Len64(z[1])
default:
return bits.Len64(z[0])
}
}
// ByteLen returns the number of bytes required to represent z
func (z *Int) ByteLen() int {
return (z.BitLen() + 7) / 8
}
func (z *Int) lsh64(x *Int) *Int {
z[3], z[2], z[1], z[0] = x[2], x[1], x[0], 0
return z
}
func (z *Int) lsh128(x *Int) *Int {
z[3], z[2], z[1], z[0] = x[1], x[0], 0, 0
return z
}
func (z *Int) lsh192(x *Int) *Int {
z[3], z[2], z[1], z[0] = x[0], 0, 0, 0
return z
}
func (z *Int) rsh64(x *Int) *Int {
z[3], z[2], z[1], z[0] = 0, x[3], x[2], x[1]
return z
}
func (z *Int) rsh128(x *Int) *Int {
z[3], z[2], z[1], z[0] = 0, 0, x[3], x[2]
return z
}
func (z *Int) rsh192(x *Int) *Int {
z[3], z[2], z[1], z[0] = 0, 0, 0, x[3]
return z
}
func (z *Int) srsh64(x *Int) *Int {
z[3], z[2], z[1], z[0] = math.MaxUint64, x[3], x[2], x[1]
return z
}
func (z *Int) srsh128(x *Int) *Int {
z[3], z[2], z[1], z[0] = math.MaxUint64, math.MaxUint64, x[3], x[2]
return z
}
func (z *Int) srsh192(x *Int) *Int {
z[3], z[2], z[1], z[0] = math.MaxUint64, math.MaxUint64, math.MaxUint64, x[3]
return z
}
// Not sets z = ^x and returns z.
func (z *Int) Not(x *Int) *Int {
z[3], z[2], z[1], z[0] = ^x[3], ^x[2], ^x[1], ^x[0]
return z
}
// Gt returns true if z > x
func (z *Int) Gt(x *Int) bool {
return x.Lt(z)
}
// Slt interprets z and x as signed integers, and returns
// true if z < x
func (z *Int) Slt(x *Int) bool {
zSign := z.Sign()
xSign := x.Sign()
switch {
case zSign >= 0 && xSign < 0:
return false
case zSign < 0 && xSign >= 0:
return true
default:
return z.Lt(x)
}
}
// Sgt interprets z and x as signed integers, and returns
// true if z > x
func (z *Int) Sgt(x *Int) bool {
zSign := z.Sign()
xSign := x.Sign()
switch {
case zSign >= 0 && xSign < 0:
return true
case zSign < 0 && xSign >= 0:
return false
default:
return z.Gt(x)
}
}
// Lt returns true if z < x
func (z *Int) Lt(x *Int) bool {
// z < x <=> z - x < 0 i.e. when subtraction overflows.
_, carry := bits.Sub64(z[0], x[0], 0)
_, carry = bits.Sub64(z[1], x[1], carry)
_, carry = bits.Sub64(z[2], x[2], carry)
_, carry = bits.Sub64(z[3], x[3], carry)
return carry != 0
}
// SetUint64 sets z to the value x
func (z *Int) SetUint64(x uint64) *Int {
z[3], z[2], z[1], z[0] = 0, 0, 0, x
return z
}
// Eq returns true if z == x
func (z *Int) Eq(x *Int) bool {
return (z[0] == x[0]) && (z[1] == x[1]) && (z[2] == x[2]) && (z[3] == x[3])
}
// Cmp compares z and x and returns:
//
// -1 if z < x
// 0 if z == x
// +1 if z > x
func (z *Int) Cmp(x *Int) (r int) {
// z < x <=> z - x < 0 i.e. when subtraction overflows.
d0, carry := bits.Sub64(z[0], x[0], 0)
d1, carry := bits.Sub64(z[1], x[1], carry)
d2, carry := bits.Sub64(z[2], x[2], carry)
d3, carry := bits.Sub64(z[3], x[3], carry)
if carry == 1 {
return -1
}
if d0|d1|d2|d3 == 0 {
return 0
}
return 1
}
// CmpUint64 compares z and x and returns:
//
// -1 if z < x
// 0 if z == x
// +1 if z > x
func (z *Int) CmpUint64(x uint64) int {
if z[0] > x || (z[1]|z[2]|z[3]) != 0 {
return 1
}
if z[0] == x {
return 0
}
return -1
}
// CmpBig compares z and x and returns:
//
// -1 if z < x
// 0 if z == x
// +1 if z > x
func (z *Int) CmpBig(x *big.Int) (r int) {
// If x is negative, it's surely smaller (z > x)
if x.Sign() == -1 {
return 1
}
y := new(Int)
if y.SetFromBig(x) { // overflow
// z < x
return -1
}
return z.Cmp(y)
}
// LtUint64 returns true if z is smaller than n
func (z *Int) LtUint64(n uint64) bool {
return z[0] < n && (z[1]|z[2]|z[3]) == 0
}
// GtUint64 returns true if z is larger than n
func (z *Int) GtUint64(n uint64) bool {
return z[0] > n || (z[1]|z[2]|z[3]) != 0
}
// IsUint64 reports whether z can be represented as a uint64.
func (z *Int) IsUint64() bool {
return (z[1] | z[2] | z[3]) == 0
}
// IsZero returns true if z == 0
func (z *Int) IsZero() bool {
return (z[0] | z[1] | z[2] | z[3]) == 0
}
// Clear sets z to 0
func (z *Int) Clear() *Int {
z[3], z[2], z[1], z[0] = 0, 0, 0, 0
return z
}
// SetAllOne sets all the bits of z to 1
func (z *Int) SetAllOne() *Int {
z[3], z[2], z[1], z[0] = math.MaxUint64, math.MaxUint64, math.MaxUint64, math.MaxUint64
return z
}
// SetOne sets z to 1
func (z *Int) SetOne() *Int {
z[3], z[2], z[1], z[0] = 0, 0, 0, 1
return z
}
// Lsh sets z = x << n and returns z.
func (z *Int) Lsh(x *Int, n uint) *Int {
switch {
case n == 0:
return z.Set(x)
case n >= 192:
z.lsh192(x)
n -= 192
z[3] <<= n
return z
case n >= 128:
z.lsh128(x)
n -= 128
z[3] = (z[3] << n) | (z[2] >> (64 - n))
z[2] <<= n
return z
case n >= 64:
z.lsh64(x)
n -= 64
z[3] = (z[3] << n) | (z[2] >> (64 - n))
z[2] = (z[2] << n) | (z[1] >> (64 - n))
z[1] <<= n
return z
default:
z.Set(x)
z[3] = (z[3] << n) | (z[2] >> (64 - n))
z[2] = (z[2] << n) | (z[1] >> (64 - n))
z[1] = (z[1] << n) | (z[0] >> (64 - n))
z[0] <<= n
return z
}
}
// Rsh sets z = x >> n and returns z.
func (z *Int) Rsh(x *Int, n uint) *Int {
switch {
case n == 0:
return z.Set(x)
case n >= 192:
z.rsh192(x)
n -= 192
z[0] >>= n
return z
case n >= 128:
z.rsh128(x)
n -= 128
z[0] = (z[0] >> n) | (z[1] << (64 - n))
z[1] >>= n
return z
case n >= 64:
z.rsh64(x)
n -= 64
z[0] = (z[0] >> n) | (z[1] << (64 - n))
z[1] = (z[1] >> n) | (z[2] << (64 - n))
z[2] >>= n
return z
default:
z.Set(x)
z[0] = (z[0] >> n) | (z[1] << (64 - n))
z[1] = (z[1] >> n) | (z[2] << (64 - n))
z[2] = (z[2] >> n) | (z[3] << (64 - n))
z[3] >>= n
return z
}
}
// SRsh (Signed/Arithmetic right shift)
// considers z to be a signed integer, during right-shift
// and sets z = x >> n and returns z.
func (z *Int) SRsh(x *Int, n uint) *Int {
// If the MSB is 0, SRsh is same as Rsh.
if !x.isBitSet(255) {
return z.Rsh(x, n)
}
var a uint64 = math.MaxUint64 << (64 - n%64)
switch {
case n == 0:
return z.Set(x)
case n >= 256:
return z.SetAllOne()
case n >= 192:
z.srsh192(x)
n -= 192
z[0] = (z[0] >> n) | a
return z
case n >= 128:
z.srsh128(x)
n -= 128
z[0] = (z[0] >> n) | (z[1] << (64 - n))
z[1] = (z[1] >> n) | a
return z
case n >= 64:
z.srsh64(x)
n -= 64
z[0] = (z[0] >> n) | (z[1] << (64 - n))
z[1] = (z[1] >> n) | (z[2] << (64 - n))
z[2] = (z[2] >> n) | a
return z
default:
z.Set(x)
z[0] = (z[0] >> n) | (z[1] << (64 - n))
z[1] = (z[1] >> n) | (z[2] << (64 - n))
z[2] = (z[2] >> n) | (z[3] << (64 - n))
z[3] = (z[3] >> n) | a
return z
}
}
// Set sets z to x and returns z.
func (z *Int) Set(x *Int) *Int {
z[0], z[1], z[2], z[3] = x[0], x[1], x[2], x[3]
return z
}
// Or sets z = x | y and returns z.
func (z *Int) Or(x, y *Int) *Int {
z[0] = x[0] | y[0]
z[1] = x[1] | y[1]
z[2] = x[2] | y[2]
z[3] = x[3] | y[3]
return z
}
// And sets z = x & y and returns z.
func (z *Int) And(x, y *Int) *Int {
z[0] = x[0] & y[0]
z[1] = x[1] & y[1]
z[2] = x[2] & y[2]
z[3] = x[3] & y[3]
return z
}
// Xor sets z = x ^ y and returns z.
func (z *Int) Xor(x, y *Int) *Int {
z[0] = x[0] ^ y[0]
z[1] = x[1] ^ y[1]
z[2] = x[2] ^ y[2]
z[3] = x[3] ^ y[3]
return z
}
// Byte sets z to the value of the byte at position n,
// with z considered as a big-endian 32-byte integer.
// if n >= 32, z is set to 0
// Example: z=5, n=31 => 5
func (z *Int) Byte(n *Int) *Int {
index, overflow := n.Uint64WithOverflow()
if overflow || index >= 32 {
return z.Clear()
}
// in z, z[0] is the least significant
number := z[4-1-index/8]
offset := (index & 0x7) << 3 // 8 * (index % 8)
z[0] = (number >> (56 - offset)) & 0xff
z[3], z[2], z[1] = 0, 0, 0
return z
}
// Exp sets z = base**exponent mod 2**256, and returns z.
func (z *Int) Exp(base, exponent *Int) *Int {
res := Int{1, 0, 0, 0}
multiplier := *base
expBitLen := exponent.BitLen()
curBit := 0
word := exponent[0]
for ; curBit < expBitLen && curBit < 64; curBit++ {
if word&1 == 1 {
res.Mul(&res, &multiplier)
}
multiplier.squared()
word >>= 1
}
word = exponent[1]
for ; curBit < expBitLen && curBit < 128; curBit++ {
if word&1 == 1 {
res.Mul(&res, &multiplier)
}
multiplier.squared()
word >>= 1
}
word = exponent[2]
for ; curBit < expBitLen && curBit < 192; curBit++ {
if word&1 == 1 {
res.Mul(&res, &multiplier)
}
multiplier.squared()
word >>= 1
}
word = exponent[3]
for ; curBit < expBitLen && curBit < 256; curBit++ {
if word&1 == 1 {
res.Mul(&res, &multiplier)
}
multiplier.squared()
word >>= 1
}
return z.Set(&res)
}
// ExtendSign extends length of two’s complement signed integer,
// sets z to
// - x if byteNum > 30
// - x interpreted as a signed number with sign-bit at (byteNum*8+7), extended to the full 256 bits
//
// and returns z.
func (z *Int) ExtendSign(x, byteNum *Int) *Int {
// This implementation is based on evmone. See https://github.com/ethereum/evmone/pull/390
if byteNum.GtUint64(30) {
return z.Set(x)
}
e := byteNum.Uint64()
z.Set(x)
signWordIndex := e >> 3 // Index of the word with the sign bit.
signByteIndex := e & 7 // Index of the sign byte in the sign word.
signWord := z[signWordIndex]
signByteOffset := signByteIndex << 3
signByte := signWord >> signByteOffset // Move sign byte to position 0.
// Sign-extend the "sign" byte and move it to the right position. Value bits are zeros.
sextByte := uint64(int64(int8(signByte)))
sext := sextByte << signByteOffset
signMask := uint64(math.MaxUint64 << signByteOffset)
value := signWord & ^signMask // Reset extended bytes.
z[signWordIndex] = sext | value // Combine the result word.
// Produce bits (all zeros or ones) for extended words. This is done by SAR of
// the sign-extended byte. Shift by any value 7-63 would work.
signEx := uint64(int64(sextByte) >> 8)
switch signWordIndex {
case 2:
z[3] = signEx
return z
case 1:
z[3], z[2] = signEx, signEx
return z
case 0:
z[3], z[2], z[1] = signEx, signEx, signEx
return z
default:
return z
}
}
// Sqrt sets z to ⌊√x⌋, the largest integer such that z² ≤ x, and returns z.
func (z *Int) Sqrt(x *Int) *Int {
// This implementation of Sqrt is based on big.Int (see math/big/nat.go).
if x.LtUint64(2) {
return z.Set(x)
}
var (
z1 = &Int{1, 0, 0, 0}
z2 = &Int{}
)
// Start with value known to be too large and repeat "z = ⌊(z + ⌊x/z⌋)/2⌋" until it stops getting smaller.
z1 = z1.Lsh(z1, uint(x.BitLen()+1)/2) // must be ≥ √x
for {
z2 = z2.Div(x, z1)
z2 = z2.Add(z2, z1)
{ //z2 = z2.Rsh(z2, 1) -- the code below does a 1-bit rsh faster
a := z2[3] << 63
z2[3] = z2[3] >> 1
b := z2[2] << 63
z2[2] = (z2[2] >> 1) | a
a = z2[1] << 63
z2[1] = (z2[1] >> 1) | b
z2[0] = (z2[0] >> 1) | a
}
// end of inlined bitshift
if z2.Cmp(z1) >= 0 {
// z1 is answer.
return z.Set(z1)
}
z1, z2 = z2, z1
}
}
var (
// pows64 contains 10^0 ... 10^19
pows64 = [20]uint64{
1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
}
// pows contain 10 ** 20 ... 10 ** 80
pows = [60]Int{
{7766279631452241920, 5, 0, 0}, {3875820019684212736, 54, 0, 0}, {1864712049423024128, 542, 0, 0}, {200376420520689664, 5421, 0, 0}, {2003764205206896640, 54210, 0, 0}, {1590897978359414784, 542101, 0, 0}, {15908979783594147840, 5421010, 0, 0}, {11515845246265065472, 54210108, 0, 0}, {4477988020393345024, 542101086, 0, 0}, {7886392056514347008, 5421010862, 0, 0}, {5076944270305263616, 54210108624, 0, 0}, {13875954555633532928, 542101086242, 0, 0}, {9632337040368467968, 5421010862427, 0, 0},
{4089650035136921600, 54210108624275, 0, 0}, {4003012203950112768, 542101086242752, 0, 0}, {3136633892082024448, 5421010862427522, 0, 0}, {12919594847110692864, 54210108624275221, 0, 0}, {68739955140067328, 542101086242752217, 0, 0}, {687399551400673280, 5421010862427522170, 0, 0}, {6873995514006732800, 17316620476856118468, 2, 0}, {13399722918938673152, 7145508105175220139, 29, 0}, {4870020673419870208, 16114848830623546549, 293, 0}, {11806718586779598848, 13574535716559052564, 2938, 0},
{7386721425538678784, 6618148649623664334, 29387, 0}, {80237960548581376, 10841254275107988496, 293873, 0}, {802379605485813760, 16178822382532126880, 2938735, 0}, {8023796054858137600, 14214271235644855872, 29387358, 0}, {6450984253743169536, 13015503840481697412, 293873587, 0}, {9169610316303040512, 1027829888850112811, 2938735877, 0}, {17909126868192198656, 10278298888501128114, 29387358770, 0}, {13070572018536022016, 10549268516463523069, 293873587705, 0}, {1578511669393358848, 13258964796087472617, 2938735877055, 0}, {15785116693933588480, 3462439444907864858, 29387358770557, 0},
{10277214349659471872, 16177650375369096972, 293873587705571, 0}, {10538423128046960640, 14202551164014556797, 2938735877055718, 0}, {13150510911921848320, 12898303124178706663, 29387358770557187, 0}, {2377900603251621888, 18302566799529756941, 293873587705571876, 0}, {5332261958806667264, 17004971331911604867, 2938735877055718769, 0}, {16429131440647569408, 4029016655730084128, 10940614696847636083, 1}, {16717361816799281152, 3396678409881738056, 17172426599928602752, 15}, {1152921504606846976, 15520040025107828953, 5703569335900062977, 159}, {11529215046068469760, 7626447661401876602, 1695461137871974930, 1593}, {4611686018427387904, 2477500319180559562, 16954611378719749304, 15930}, {9223372036854775808, 6328259118096044006, 3525417123811528497, 159309},
{0, 7942358959831785217, 16807427164405733357, 1593091}, {0, 5636613303479645706, 2053574980671369030, 15930919}, {0, 1025900813667802212, 2089005733004138687, 159309191}, {0, 10259008136678022120, 2443313256331835254, 1593091911}, {0, 10356360998232463120, 5986388489608800929, 15930919111}, {0, 11329889613776873120, 4523652674959354447, 159309191113}, {0, 2618431695511421504, 8343038602174441244, 1593091911132}, {0, 7737572881404663424, 9643409726906205977, 15930919111324}, {0, 3588752519208427776, 4200376900514301694, 159309191113245}, {0, 17440781118374726144, 5110280857723913709, 1593091911132452}, {0, 8387114520361296896, 14209320429820033867, 15930919111324522}, {0, 10084168908774762496, 12965995782233477362, 159309191113245227}, {0, 8607968719199866880, 532749306367912313, 1593091911132452277}, {0, 12292710897160462336, 5327493063679123134, 15930919111324522770}, {0, 12246644529347313664, 16381442489372128114, 11735238523568814774}, {0, 11785980851215826944, 16240472304044868218, 6671920793430838052},
}
)
// Log10 returns the log in base 10, floored to nearest integer.
// **OBS** This method returns '0' for '0', not `-Inf`.
func (z *Int) Log10() uint {
// The following algorithm is taken from "Bit twiddling hacks"
// https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
//
// The idea is that log10(z) = log2(z) / log2(10)
// log2(z) trivially is z.Bitlen()
// 1/log2(10) is a constant ~ 1233 / 4096. The approximation is correct up to 5 digit after
// the decimal point and it seems no further refinement is needed.
// Our tests check all boundary cases anyway.
bitlen := z.BitLen()
if bitlen == 0 {
return 0
}
t := (bitlen + 1) * 1233 >> 12
if bitlen <= 64 && z[0] < pows64[t] || t >= 20 && z.Lt(&pows[t-20]) {
return uint(t - 1)
}
return uint(t)
}