README
¶
Fixed size 256-bit math library
This is a library specialized at replacing the big.Int library for math based on 256-bit types, used by both go-ethereum and turbo-geth.
Benchmarks
Current benchmarks, with tests ending with big being the standard big.Int library, and uint256 being this library.
Current status
- As of 2020-03-18,
uint256wins over big in every single case, often with orders of magnitude. - And as of release
0.1.0, theuint256library is alloc-free. - With the
1.0.0release, it also has100%test coverage.
Conversion from/to big.Int and other formats
BenchmarkSetFromBig/1word-6 253798280 4.84 ns/op 0 B/op 0 allocs/op
BenchmarkSetFromBig/2words-6 242738034 5.00 ns/op 0 B/op 0 allocs/op
BenchmarkSetFromBig/3words-6 233704105 5.22 ns/op 0 B/op 0 allocs/op
BenchmarkSetFromBig/4words-6 192542544 5.70 ns/op 0 B/op 0 allocs/op
BenchmarkSetFromBig/overflow-6 212680123 6.05 ns/op 0 B/op 0 allocs/op
BenchmarkToBig/1word-6 14953528 81.6 ns/op 64 B/op 2 allocs/op
BenchmarkToBig/2words-6 15932970 85.1 ns/op 64 B/op 2 allocs/op
BenchmarkToBig/3words-6 15629001 77.0 ns/op 64 B/op 2 allocs/op
BenchmarkToBig/4words-6 14525355 78.0 ns/op 64 B/op 2 allocs/op
BenchmarkSetBytes/generic-6 5386718 230 ns/op 0 B/op 0 allocs/op
BenchmarkSetBytes/specific-6 9418405 130 ns/op 0 B/op 0 allocs/op
BenchmarkRLPEncoding-6 82531 13085 ns/op 11911 B/op 255 allocs/op
Math operations
uint256:
Benchmark_Add/single/uint256-6 575308741 2.19 ns/op 0 B/op 0 allocs/op
Benchmark_Sub/single/uint256-6 551694393 2.71 ns/op 0 B/op 0 allocs/op
Benchmark_Sub/single/uint256_of-6 405466652 2.52 ns/op 0 B/op 0 allocs/op
BenchmarkMul/single/uint256-6 147034321 8.19 ns/op 0 B/op 0 allocs/op
BenchmarkMulOverflow/single/uint256-6 45344761 25.4 ns/op 0 B/op 0 allocs/op
BenchmarkSquare/single/uint256-6 196272379 6.14 ns/op 0 B/op 0 allocs/op
Benchmark_Exp/large/uint256-6 374550 3199 ns/op 0 B/op 0 allocs/op
Benchmark_Exp/small/uint256-6 4426760 270 ns/op 0 B/op 0 allocs/op
BenchmarkDiv/small/uint256-6 94629267 12.5 ns/op 0 B/op 0 allocs/op
BenchmarkDiv/mod64/uint256-6 17367373 67.6 ns/op 0 B/op 0 allocs/op
BenchmarkDiv/mod128/uint256-6 10192484 130 ns/op 0 B/op 0 allocs/op
BenchmarkDiv/mod192/uint256-6 10936984 107 ns/op 0 B/op 0 allocs/op
BenchmarkDiv/mod256/uint256-6 13436908 93.5 ns/op 0 B/op 0 allocs/op
BenchmarkMod/small/uint256-6 80138805 15.2 ns/op 0 B/op 0 allocs/op
BenchmarkMod/mod64/uint256-6 17065768 72.1 ns/op 0 B/op 0 allocs/op
BenchmarkMod/mod128/uint256-6 9469146 123 ns/op 0 B/op 0 allocs/op
BenchmarkMod/mod192/uint256-6 11193145 115 ns/op 0 B/op 0 allocs/op
BenchmarkMod/mod256/uint256-6 12896706 93.1 ns/op 0 B/op 0 allocs/op
BenchmarkAddMod/small/uint256-6 62187169 21.0 ns/op 0 B/op 0 allocs/op
BenchmarkAddMod/mod64/uint256-6 15169026 82.5 ns/op 0 B/op 0 allocs/op
BenchmarkAddMod/mod128/uint256-6 8460835 144 ns/op 0 B/op 0 allocs/op
BenchmarkAddMod/mod192/uint256-6 9273334 141 ns/op 0 B/op 0 allocs/op
BenchmarkAddMod/mod256/uint256-6 10145329 113 ns/op 0 B/op 0 allocs/op
BenchmarkMulMod/small/uint256-6 26673195 42.3 ns/op 0 B/op 0 allocs/op
BenchmarkMulMod/mod64/uint256-6 10133446 125 ns/op 0 B/op 0 allocs/op
BenchmarkMulMod/mod128/uint256-6 4955551 229 ns/op 0 B/op 0 allocs/op
BenchmarkMulMod/mod192/uint256-6 5210977 220 ns/op 0 B/op 0 allocs/op
BenchmarkMulMod/mod256/uint256-6 5527972 220 ns/op 0 B/op 0 allocs/op
Benchmark_SDiv/large/uint256-6 9823093 124 ns/op 0 B/op 0 allocs/op
vs big.Int
Benchmark_Add/single/big-6 45798462 25.0 ns/op 0 B/op 0 allocs/op
Benchmark_Sub/single/big-6 51314886 23.7 ns/op 0 B/op 0 allocs/op
BenchmarkMul/single/big-6 14101502 75.9 ns/op 0 B/op 0 allocs/op
BenchmarkMulOverflow/single/big-6 15774238 81.5 ns/op 0 B/op 0 allocs/op
BenchmarkSquare/single/big-6 16739438 71.5 ns/op 0 B/op 0 allocs/op
Benchmark_Exp/large/big-6 41250 42132 ns/op 18144 B/op 189 allocs/op
Benchmark_Exp/small/big-6 130993 10813 ns/op 7392 B/op 77 allocs/op
BenchmarkDiv/small/big-6 18169453 70.8 ns/op 8 B/op 1 allocs/op
BenchmarkDiv/mod64/big-6 7500694 147 ns/op 8 B/op 1 allocs/op
BenchmarkDiv/mod128/big-6 3075676 370 ns/op 80 B/op 1 allocs/op
BenchmarkDiv/mod192/big-6 3908166 307 ns/op 80 B/op 1 allocs/op
BenchmarkDiv/mod256/big-6 4416366 252 ns/op 80 B/op 1 allocs/op
BenchmarkMod/small/big-6 19958649 70.8 ns/op 8 B/op 1 allocs/op
BenchmarkMod/mod64/big-6 6718828 167 ns/op 64 B/op 1 allocs/op
BenchmarkMod/mod128/big-6 3347608 349 ns/op 64 B/op 1 allocs/op
BenchmarkMod/mod192/big-6 4072453 293 ns/op 48 B/op 1 allocs/op
BenchmarkMod/mod256/big-6 4545860 254 ns/op 8 B/op 1 allocs/op
BenchmarkAddMod/small/big-6 13976365 79.6 ns/op 8 B/op 1 allocs/op
BenchmarkAddMod/mod64/big-6 5799034 208 ns/op 77 B/op 1 allocs/op
BenchmarkAddMod/mod128/big-6 2998821 409 ns/op 64 B/op 1 allocs/op
BenchmarkAddMod/mod192/big-6 3420640 351 ns/op 61 B/op 1 allocs/op
BenchmarkAddMod/mod256/big-6 4124067 298 ns/op 40 B/op 1 allocs/op
BenchmarkMulMod/small/big-6 14748193 85.8 ns/op 8 B/op 1 allocs/op
BenchmarkMulMod/mod64/big-6 3524833 420 ns/op 96 B/op 1 allocs/op
BenchmarkMulMod/mod128/big-6 1851936 637 ns/op 96 B/op 1 allocs/op
BenchmarkMulMod/mod192/big-6 2028134 584 ns/op 80 B/op 1 allocs/op
BenchmarkMulMod/mod256/big-6 2125716 576 ns/op 80 B/op 1 allocs/op
Benchmark_SDiv/large/big-6 1658139 848 ns/op 312 B/op 6 allocs/op
Boolean logic
uint256
Benchmark_And/single/uint256-6 571318570 2.13 ns/op 0 B/op 0 allocs/op
Benchmark_Or/single/uint256-6 500672864 2.09 ns/op 0 B/op 0 allocs/op
Benchmark_Xor/single/uint256-6 575198724 2.24 ns/op 0 B/op 0 allocs/op
Benchmark_Cmp/single/uint256-6 400446943 3.09 ns/op 0 B/op 0 allocs/op
BenchmarkLt/large/uint256-6 322143085 3.50 ns/op 0 B/op 0 allocs/op
BenchmarkLt/small/uint256-6 351231680 3.33 ns/op 0 B/op 0 allocs/op
vs big.Int
Benchmark_And/single/big-6 78524395 16.2 ns/op 0 B/op 0 allocs/op
Benchmark_Or/single/big-6 65390958 20.5 ns/op 0 B/op 0 allocs/op
Benchmark_Xor/single/big-6 58333172 20.6 ns/op 0 B/op 0 allocs/op
Benchmark_Cmp/single/big-6 144781878 8.37 ns/op 0 B/op 0 allocs/op
BenchmarkLt/large/big-6 95643212 13.8 ns/op 0 B/op 0 allocs/op
BenchmarkLt/small/big-6 84561792 14.6 ns/op 0 B/op 0 allocs/op
Bitwise shifts
uint256:
Benchmark_Lsh/n_eq_0/uint256-6 291558974 3.96 ns/op 0 B/op 0 allocs/op
Benchmark_Lsh/n_gt_192/uint256-6 208429646 5.80 ns/op 0 B/op 0 allocs/op
Benchmark_Lsh/n_gt_128/uint256-6 151857447 6.90 ns/op 0 B/op 0 allocs/op
Benchmark_Lsh/n_gt_64/uint256-6 124543732 9.55 ns/op 0 B/op 0 allocs/op
Benchmark_Lsh/n_gt_0/uint256-6 100000000 11.2 ns/op 0 B/op 0 allocs/op
Benchmark_Rsh/n_eq_0/uint256-6 296913555 4.08 ns/op 0 B/op 0 allocs/op
Benchmark_Rsh/n_gt_192/uint256-6 212698939 5.52 ns/op 0 B/op 0 allocs/op
Benchmark_Rsh/n_gt_128/uint256-6 157391629 7.59 ns/op 0 B/op 0 allocs/op
Benchmark_Rsh/n_gt_64/uint256-6 124916373 9.46 ns/op 0 B/op 0 allocs/op
Benchmark_Rsh/n_gt_0/uint256-6 100000000 11.5 ns/op
vs big.Int:
Benchmark_Lsh/n_eq_0/big-6 21387698 78.6 ns/op 64 B/op 1 allocs/op
Benchmark_Lsh/n_gt_192/big-6 15645853 73.9 ns/op 96 B/op 1 allocs/op
Benchmark_Lsh/n_gt_128/big-6 15954750 75.0 ns/op 96 B/op 1 allocs/op
Benchmark_Lsh/n_gt_64/big-6 16771413 81.3 ns/op 80 B/op 1 allocs/op
Benchmark_Lsh/n_gt_0/big-6 17118044 70.7 ns/op 80 B/op 1 allocs/op
Benchmark_Rsh/n_eq_0/big-6 21585044 65.5 ns/op 64 B/op 1 allocs/op
Benchmark_Rsh/n_gt_192/big-6 28313300 42.3 ns/op 8 B/op 1 allocs/op
Benchmark_Rsh/n_gt_128/big-6 21191526 58.1 ns/op 48 B/op 1 allocs/op
Benchmark_Rsh/n_gt_64/big-6 15906076 69.0 ns/op 64 B/op 1 allocs/op
Benchmark_Rsh/n_gt_0/big-6 19234408 93.0 ns/op 64 B/op 1 allocs/op
Helping out
If you're interested in low-level algorithms and/or doing optimizations for shaving off nanoseconds, then this is certainly for you!
Implementation work
Choose an operation, and optimize the s**t out of it!
A few rules, though, to help your PR get approved:
- Do not optimize for 'best-case'/'most common case' at the expense of worst-case.
- We'll hold off on go assembly for a while, until the algos and interfaces are finished in a 'good enough' first version. After that, it's assembly time.
Doing benchmarks
To do a simple benchmark for everything, do
go test -run - -bench . -benchmem
To see the difference between a branch and master, for a particular benchmark, do
git checkout master
go test -run - -bench Benchmark_Lsh -benchmem -count=10 > old.txt
git checkout opt_branch
go test -run - -bench Benchmark_Lsh -benchmem -count=10 > new.txt
benchstat old.txt new.txt
Documentation
¶
Index ¶
- Variables
- type Int
- func (z *Int) Abs(x *Int) *Int
- func (z *Int) Add(x, y *Int) *Int
- func (z *Int) AddMod(x, y, m *Int) *Int
- func (z *Int) AddOverflow(x, y *Int) bool
- func (z *Int) And(x, y *Int) *Int
- func (z *Int) BitLen() int
- func (z *Int) Byte(n *Int) *Int
- func (z *Int) ByteLen() int
- func (z *Int) Bytes() []byte
- func (z *Int) Bytes20() [20]byte
- func (z *Int) Bytes32() [32]byte
- func (z *Int) Clear() *Int
- func (z *Int) Clone() *Int
- func (z *Int) Cmp(x *Int) (r int)
- func (z *Int) Div(x, y *Int) *Int
- func (z *Int) EncodeRLP(w io.Writer) error
- func (z *Int) Eq(x *Int) bool
- func (z *Int) Exp(base, exponent *Int) *Int
- func (z *Int) ExtendSign(x, byteNum *Int) *Int
- func (z *Int) Format(s fmt.State, ch rune)
- func (z *Int) Gt(x *Int) bool
- func (z *Int) GtUint64(n uint64) bool
- func (z *Int) Hex() string
- func (z *Int) IsUint64() bool
- func (z *Int) IsZero() bool
- func (z *Int) Lsh(x *Int, n uint) *Int
- func (z *Int) Lt(x *Int) bool
- func (z *Int) LtUint64(n uint64) bool
- func (z *Int) MarshalText() ([]byte, error)
- func (z *Int) Mod(x, y *Int) *Int
- func (z *Int) Mul(x, y *Int) *Int
- func (z *Int) MulMod(x, y, m *Int) *Int
- func (z *Int) MulOverflow(x, y *Int) bool
- func (z *Int) Neg(x *Int) *Int
- func (z *Int) Not(x *Int) *Int
- func (z *Int) Or(x, y *Int) *Int
- func (z *Int) PaddedBytes(n int) []byte
- func (z *Int) Rsh(x *Int, n uint) *Int
- func (z *Int) SDiv(n, d *Int) *Int
- func (z *Int) SMod(x, y *Int) *Int
- func (z *Int) SRsh(x *Int, n uint) *Int
- func (z *Int) Set(x *Int) *Int
- func (z *Int) SetAllOne() *Int
- func (z *Int) SetBytes(buf []byte) *Int
- func (z *Int) SetBytes1(in []byte) *Int
- func (z *Int) SetBytes10(in []byte) *Int
- func (z *Int) SetBytes11(in []byte) *Int
- func (z *Int) SetBytes12(in []byte) *Int
- func (z *Int) SetBytes13(in []byte) *Int
- func (z *Int) SetBytes14(in []byte) *Int
- func (z *Int) SetBytes15(in []byte) *Int
- func (z *Int) SetBytes16(in []byte) *Int
- func (z *Int) SetBytes17(in []byte) *Int
- func (z *Int) SetBytes18(in []byte) *Int
- func (z *Int) SetBytes19(in []byte) *Int
- func (z *Int) SetBytes2(in []byte) *Int
- func (z *Int) SetBytes20(in []byte) *Int
- func (z *Int) SetBytes21(in []byte) *Int
- func (z *Int) SetBytes22(in []byte) *Int
- func (z *Int) SetBytes23(in []byte) *Int
- func (z *Int) SetBytes24(in []byte) *Int
- func (z *Int) SetBytes25(in []byte) *Int
- func (z *Int) SetBytes26(in []byte) *Int
- func (z *Int) SetBytes27(in []byte) *Int
- func (z *Int) SetBytes28(in []byte) *Int
- func (z *Int) SetBytes29(in []byte) *Int
- func (z *Int) SetBytes3(in []byte) *Int
- func (z *Int) SetBytes30(in []byte) *Int
- func (z *Int) SetBytes31(in []byte) *Int
- func (z *Int) SetBytes32(in []byte) *Int
- func (z *Int) SetBytes4(in []byte) *Int
- func (z *Int) SetBytes5(in []byte) *Int
- func (z *Int) SetBytes6(in []byte) *Int
- func (z *Int) SetBytes7(in []byte) *Int
- func (z *Int) SetBytes8(in []byte) *Int
- func (z *Int) SetBytes9(in []byte) *Int
- func (z *Int) SetFromBig(b *big.Int) bool
- func (z *Int) SetOne() *Int
- func (z *Int) SetUint64(x uint64) *Int
- func (z *Int) Sgt(x *Int) bool
- func (z *Int) Sign() int
- func (z *Int) Slt(x *Int) bool
- func (z *Int) String() string
- func (z *Int) Sub(x, y *Int) *Int
- func (z *Int) SubOverflow(x, y *Int) bool
- func (z *Int) SubUint64(x *Int, y uint64) *Int
- func (z *Int) ToBig() *big.Int
- func (z *Int) Uint64() uint64
- func (z *Int) Uint64WithOverflow() (uint64, bool)
- func (z *Int) UnmarshalJSON(input []byte) error
- func (z *Int) UnmarshalText(input []byte) error
- func (z *Int) WriteToArray20(dest *[20]byte)
- func (z *Int) WriteToArray32(dest *[32]byte)
- func (z *Int) WriteToSlice(dest []byte)
- func (z *Int) Xor(x, y *Int) *Int
Constants ¶
This section is empty.
Variables ¶
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") ErrNonString = errors.New("non-string") )
Functions ¶
This section is empty.
Types ¶
type Int ¶
type Int [4]uint64
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
func FromBig ¶
FromBig is a convenience-constructor from big.Int. Returns a new Int and whether overflow occurred.
func FromHex ¶
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 (*Int) Abs ¶
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 (*Int) AddMod ¶
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 (*Int) AddOverflow ¶
AddOverflow sets z to the sum x+y, and returns whether overflow occurred
func (*Int) Byte ¶
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, f is set to 0 Example: f = '5', n=31 => 5
func (*Int) EncodeRLP ¶
EncodeRLP implements the rlp.Encoder interface from go-ethereum and writes the RLP encoding of z to w.
func (*Int) ExtendSign ¶
ExtendSign extends length of two’s complement signed integer, sets z to
- x if byteNum > 31
- x interpreted as a signed number with sign-bit at (byteNum*8+7), extended to the full 256 bits
and returns z.
func (*Int) Format ¶
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 (*Int) MarshalText ¶
MarshalText implements encoding.TextMarshaler
func (*Int) Mod ¶
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 (*Int) MulMod ¶
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 (*Int) MulOverflow ¶
MulOverflow sets z to the product x*y, and returns whether overflow occurred
func (*Int) PaddedBytes ¶
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 (*Int) SDiv ¶
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 (*Int) SMod ¶
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 (*Int) SRsh ¶
SRsh (Signed/Arithmetic right shift) considers z to be a signed integer, during right-shift and sets z = x >> n and returns z.
func (*Int) SetBytes ¶
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 (*Int) SetBytes10 ¶
func (*Int) SetBytes11 ¶
func (*Int) SetBytes12 ¶
func (*Int) SetBytes13 ¶
func (*Int) SetBytes14 ¶
func (*Int) SetBytes15 ¶
func (*Int) SetBytes16 ¶
SetBytes16 is identical to SetBytes(in[:16]), but panics is input is too short
func (*Int) SetBytes17 ¶
func (*Int) SetBytes18 ¶
func (*Int) SetBytes19 ¶
func (*Int) SetBytes20 ¶
func (*Int) SetBytes21 ¶
func (*Int) SetBytes22 ¶
func (*Int) SetBytes23 ¶
func (*Int) SetBytes24 ¶
SetBytes16 is identical to SetBytes(in[:24]), but panics is input is too short
func (*Int) SetBytes25 ¶
func (*Int) SetBytes26 ¶
func (*Int) SetBytes27 ¶
func (*Int) SetBytes28 ¶
func (*Int) SetBytes29 ¶
func (*Int) SetBytes30 ¶
func (*Int) SetBytes31 ¶
func (*Int) SetBytes32 ¶
func (*Int) SetBytes8 ¶
SetBytes8 is identical to SetBytes(in[:8]), but panics is input is too short
func (*Int) SetFromBig ¶
SetFromBig converts a big.Int to Int and sets the value to z. TODO: Ensure we have sufficient testing, esp for negative bigints.
func (*Int) Sign ¶
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 (*Int) SubOverflow ¶
SubOverflow sets z to the difference x-y and returns true if the operation underflowed
func (*Int) Uint64WithOverflow ¶
Uint64WithOverflow returns the lower 64-bits of z and bool whether overflow occurred
func (*Int) UnmarshalJSON ¶
UnmarshalJSON implements json.Unmarshaler.
func (*Int) UnmarshalText ¶
UnmarshalText implements encoding.TextUnmarshaler
func (*Int) WriteToArray20 ¶
WriteToArray20 writes the last 20 bytes of z to the destination array, including zero-bytes
func (*Int) WriteToArray32 ¶
WriteToArray32 writes all 32 bytes of z to the destination array, including zero-bytes
func (*Int) WriteToSlice ¶
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
Source Files