123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259 |
- // Copyright 2017 The go-ethereum Authors
- // This file is part of the go-ethereum library.
- //
- // The go-ethereum library is free software: you can redistribute it and/or modify
- // it under the terms of the GNU Lesser General Public License as published by
- // the Free Software Foundation, either version 3 of the License, or
- // (at your option) any later version.
- //
- // The go-ethereum library is distributed in the hope that it will be useful,
- // but WITHOUT ANY WARRANTY; without even the implied warranty of
- // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- // GNU Lesser General Public License for more details.
- //
- // You should have received a copy of the GNU Lesser General Public License
- // along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
- // Package math provides integer math utilities.
- package math
- import (
- "fmt"
- "math/big"
- )
- // Various big integer limit values.
- var (
- tt255 = BigPow(2, 255)
- tt256 = BigPow(2, 256)
- tt256m1 = new(big.Int).Sub(tt256, big.NewInt(1))
- tt63 = BigPow(2, 63)
- MaxBig256 = new(big.Int).Set(tt256m1)
- MaxBig63 = new(big.Int).Sub(tt63, big.NewInt(1))
- )
- const (
- // number of bits in a big.Word
- wordBits = 32 << (uint64(^big.Word(0)) >> 63)
- // number of bytes in a big.Word
- wordBytes = wordBits / 8
- )
- // HexOrDecimal256 marshals big.Int as hex or decimal.
- type HexOrDecimal256 big.Int
- // NewHexOrDecimal256 creates a new HexOrDecimal256
- func NewHexOrDecimal256(x int64) *HexOrDecimal256 {
- b := big.NewInt(x)
- h := HexOrDecimal256(*b)
- return &h
- }
- // UnmarshalText implements encoding.TextUnmarshaler.
- func (i *HexOrDecimal256) UnmarshalText(input []byte) error {
- bigint, ok := ParseBig256(string(input))
- if !ok {
- return fmt.Errorf("invalid hex or decimal integer %q", input)
- }
- *i = HexOrDecimal256(*bigint)
- return nil
- }
- // MarshalText implements encoding.TextMarshaler.
- func (i *HexOrDecimal256) MarshalText() ([]byte, error) {
- if i == nil {
- return []byte("0x0"), nil
- }
- return []byte(fmt.Sprintf("%#x", (*big.Int)(i))), nil
- }
- // Decimal256 unmarshals big.Int as a decimal string. When unmarshalling,
- // it however accepts either "0x"-prefixed (hex encoded) or non-prefixed (decimal)
- type Decimal256 big.Int
- // NewHexOrDecimal256 creates a new Decimal256
- func NewDecimal256(x int64) *Decimal256 {
- b := big.NewInt(x)
- d := Decimal256(*b)
- return &d
- }
- // UnmarshalText implements encoding.TextUnmarshaler.
- func (i *Decimal256) UnmarshalText(input []byte) error {
- bigint, ok := ParseBig256(string(input))
- if !ok {
- return fmt.Errorf("invalid hex or decimal integer %q", input)
- }
- *i = Decimal256(*bigint)
- return nil
- }
- // MarshalText implements encoding.TextMarshaler.
- func (i *Decimal256) MarshalText() ([]byte, error) {
- return []byte(i.String()), nil
- }
- // String implements Stringer.
- func (i *Decimal256) String() string {
- if i == nil {
- return "0"
- }
- return fmt.Sprintf("%#d", (*big.Int)(i))
- }
- // ParseBig256 parses s as a 256 bit integer in decimal or hexadecimal syntax.
- // Leading zeros are accepted. The empty string parses as zero.
- func ParseBig256(s string) (*big.Int, bool) {
- if s == "" {
- return new(big.Int), true
- }
- var bigint *big.Int
- var ok bool
- if len(s) >= 2 && (s[:2] == "0x" || s[:2] == "0X") {
- bigint, ok = new(big.Int).SetString(s[2:], 16)
- } else {
- bigint, ok = new(big.Int).SetString(s, 10)
- }
- if ok && bigint.BitLen() > 256 {
- bigint, ok = nil, false
- }
- return bigint, ok
- }
- // MustParseBig256 parses s as a 256 bit big integer and panics if the string is invalid.
- func MustParseBig256(s string) *big.Int {
- v, ok := ParseBig256(s)
- if !ok {
- panic("invalid 256 bit integer: " + s)
- }
- return v
- }
- // BigPow returns a ** b as a big integer.
- func BigPow(a, b int64) *big.Int {
- r := big.NewInt(a)
- return r.Exp(r, big.NewInt(b), nil)
- }
- // BigMax returns the larger of x or y.
- func BigMax(x, y *big.Int) *big.Int {
- if x.Cmp(y) < 0 {
- return y
- }
- return x
- }
- // BigMin returns the smaller of x or y.
- func BigMin(x, y *big.Int) *big.Int {
- if x.Cmp(y) > 0 {
- return y
- }
- return x
- }
- // FirstBitSet returns the index of the first 1 bit in v, counting from LSB.
- func FirstBitSet(v *big.Int) int {
- for i := 0; i < v.BitLen(); i++ {
- if v.Bit(i) > 0 {
- return i
- }
- }
- return v.BitLen()
- }
- // PaddedBigBytes encodes a big integer as a big-endian byte slice. The length
- // of the slice is at least n bytes.
- func PaddedBigBytes(bigint *big.Int, n int) []byte {
- if bigint.BitLen()/8 >= n {
- return bigint.Bytes()
- }
- ret := make([]byte, n)
- ReadBits(bigint, ret)
- return ret
- }
- // bigEndianByteAt returns the byte at position n,
- // in Big-Endian encoding
- // So n==0 returns the least significant byte
- func bigEndianByteAt(bigint *big.Int, n int) byte {
- words := bigint.Bits()
- // Check word-bucket the byte will reside in
- i := n / wordBytes
- if i >= len(words) {
- return byte(0)
- }
- word := words[i]
- // Offset of the byte
- shift := 8 * uint(n%wordBytes)
- return byte(word >> shift)
- }
- // Byte returns the byte at position n,
- // with the supplied padlength in Little-Endian encoding.
- // n==0 returns the MSB
- // Example: bigint '5', padlength 32, n=31 => 5
- func Byte(bigint *big.Int, padlength, n int) byte {
- if n >= padlength {
- return byte(0)
- }
- return bigEndianByteAt(bigint, padlength-1-n)
- }
- // ReadBits encodes the absolute value of bigint as big-endian bytes. Callers must ensure
- // that buf has enough space. If buf is too short the result will be incomplete.
- func ReadBits(bigint *big.Int, buf []byte) {
- i := len(buf)
- for _, d := range bigint.Bits() {
- for j := 0; j < wordBytes && i > 0; j++ {
- i--
- buf[i] = byte(d)
- d >>= 8
- }
- }
- }
- // U256 encodes as a 256 bit two's complement number. This operation is destructive.
- func U256(x *big.Int) *big.Int {
- return x.And(x, tt256m1)
- }
- // U256Bytes converts a big Int into a 256bit EVM number.
- // This operation is destructive.
- func U256Bytes(n *big.Int) []byte {
- return PaddedBigBytes(U256(n), 32)
- }
- // S256 interprets x as a two's complement number.
- // x must not exceed 256 bits (the result is undefined if it does) and is not modified.
- //
- // S256(0) = 0
- // S256(1) = 1
- // S256(2**255) = -2**255
- // S256(2**256-1) = -1
- func S256(x *big.Int) *big.Int {
- if x.Cmp(tt255) < 0 {
- return x
- }
- return new(big.Int).Sub(x, tt256)
- }
- // Exp implements exponentiation by squaring.
- // Exp returns a newly-allocated big integer and does not change
- // base or exponent. The result is truncated to 256 bits.
- //
- // Courtesy @karalabe and @chfast
- func Exp(base, exponent *big.Int) *big.Int {
- result := big.NewInt(1)
- for _, word := range exponent.Bits() {
- for i := 0; i < wordBits; i++ {
- if word&1 == 1 {
- U256(result.Mul(result, base))
- }
- U256(base.Mul(base, base))
- word >>= 1
- }
- }
- return result
- }
|