uint256

package module
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 13, 2020 License: BSD-3-Clause Imports: 5 Imported by: 2,303

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. This is meant for use in go-ethereum eventually, once it's deemed fast, stable and secure enough.

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, uint256 wins over big in every single case, often with orders of magnitude.
  • And as of release 0.1.0, the uint256 library is alloc-free.
  • With the 1.0.0 release, it also has 100% test coverage.
Conversion from/to big.Int
BenchmarkSetFromBig/1word-6        	252819142	         5.02 ns/op	       0 B/op	       0 allocs/op
BenchmarkSetFromBig/2words-6       	246641738	         5.17 ns/op	       0 B/op	       0 allocs/op
BenchmarkSetFromBig/3words-6       	238986948	         5.11 ns/op	       0 B/op	       0 allocs/op
BenchmarkSetFromBig/4words-6       	235735474	         5.29 ns/op	       0 B/op	       0 allocs/op
BenchmarkSetFromBig/overflow-6     	233997644	         5.76 ns/op	       0 B/op	       0 allocs/op
BenchmarkToBig/1word-6             	16905244	        76.4 ns/op	      64 B/op	       2 allocs/op
BenchmarkToBig/2words-6            	16532232	        75.3 ns/op	      64 B/op	       2 allocs/op
BenchmarkToBig/3words-6            	16193755	        73.7 ns/op	      64 B/op	       2 allocs/op
BenchmarkToBig/4words-6            	16226127	        76.5 ns/op	      64 B/op	       2 allocs/op
Math operations

uint256:

Benchmark_Add/single/uint256-6     	629591630	         1.93 ns/op	       0 B/op	       0 allocs/op
Benchmark_Sub/single/uint256-6     	546594793	         2.19 ns/op	       0 B/op	       0 allocs/op
Benchmark_Sub/single/uint256_of-6  	569249097	         2.12 ns/op	       0 B/op	       0 allocs/op
BenchmarkMul/single/uint256-6      	121926037	         8.92 ns/op	       0 B/op	       0 allocs/op
BenchmarkSquare/single/uint256-6   	175970640	         6.86 ns/op	       0 B/op	       0 allocs/op
Benchmark_Exp/large/uint256-6      	  325039	      3698 ns/op	       0 B/op	       0 allocs/op
Benchmark_Exp/small/uint256-6      	 3832027	       328 ns/op	       0 B/op	       0 allocs/op
BenchmarkDiv/small/uint256-6       	86487969	        14.3 ns/op	       0 B/op	       0 allocs/op
BenchmarkDiv/mod64/uint256-6       	18414321	        66.7 ns/op	       0 B/op	       0 allocs/op
BenchmarkDiv/mod128/uint256-6      	 9474686	       120 ns/op	       0 B/op	       0 allocs/op
BenchmarkDiv/mod192/uint256-6      	11031271	       107 ns/op	       0 B/op	       0 allocs/op
BenchmarkDiv/mod256/uint256-6      	13804608	        87.3 ns/op	       0 B/op	       0 allocs/op
BenchmarkMod/small/uint256-6       	83189749	        14.3 ns/op	       0 B/op	       0 allocs/op
BenchmarkMod/mod64/uint256-6       	17734662	        67.8 ns/op	       0 B/op	       0 allocs/op
BenchmarkMod/mod128/uint256-6      	10050982	       119 ns/op	       0 B/op	       0 allocs/op
BenchmarkMod/mod192/uint256-6      	10477886	       112 ns/op	       0 B/op	       0 allocs/op
BenchmarkMod/mod256/uint256-6      	13230618	        92.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkAddMod/small/uint256-6    	64955443	        19.5 ns/op	       0 B/op	       0 allocs/op
BenchmarkAddMod/mod64/uint256-6    	15589430	        79.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkAddMod/mod128/uint256-6   	 8173804	       138 ns/op	       0 B/op	       0 allocs/op
BenchmarkAddMod/mod192/uint256-6   	 9115947	       133 ns/op	       0 B/op	       0 allocs/op
BenchmarkAddMod/mod256/uint256-6   	10549335	       119 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulMod/small/uint256-6    	29009958	        41.4 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulMod/mod64/uint256-6    	10366879	       115 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulMod/mod128/uint256-6   	 5339348	       256 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulMod/mod192/uint256-6   	 5322434	       231 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulMod/mod256/uint256-6   	 5229891	       229 ns/op	       0 B/op	       0 allocs/op
Benchmark_SDiv/large/uint256-6     	10094680	       122 ns/op	       0 B/op	       0 allocs/op

vs big.Int

Benchmark_Add/single/big-6         	48557786	        21.9 ns/op	       0 B/op	       0 allocs/op
Benchmark_Sub/single/big-6         	55511476	        21.7 ns/op	       0 B/op	       0 allocs/op
BenchmarkMul/single/big-6          	17177685	        72.1 ns/op	       0 B/op	       0 allocs/op
BenchmarkSquare/single/big-6       	18434874	        67.6 ns/op	       0 B/op	       0 allocs/op
Benchmark_Exp/large/big-6          	   30236	     34919 ns/op	   18144 B/op	     189 allocs/op
Benchmark_Exp/small/big-6          	  138970	      8290 ns/op	    7392 B/op	      77 allocs/op
BenchmarkDiv/small/big-6           	20982415	        55.9 ns/op	       8 B/op	       1 allocs/op
BenchmarkDiv/mod64/big-6           	 7928998	       168 ns/op	       8 B/op	       1 allocs/op
BenchmarkDiv/mod128/big-6          	 3858378	       312 ns/op	      80 B/op	       1 allocs/op
BenchmarkDiv/mod192/big-6          	 4733641	       251 ns/op	      80 B/op	       1 allocs/op
BenchmarkDiv/mod256/big-6          	 5928298	       204 ns/op	      80 B/op	       1 allocs/op
BenchmarkMod/small/big-6           	21673300	        63.5 ns/op	       8 B/op	       1 allocs/op
BenchmarkMod/mod64/big-6           	 7451844	       162 ns/op	      64 B/op	       1 allocs/op
BenchmarkMod/mod128/big-6          	 4138648	       308 ns/op	      64 B/op	       1 allocs/op
BenchmarkMod/mod192/big-6          	 4895036	       244 ns/op	      48 B/op	       1 allocs/op
BenchmarkMod/mod256/big-6          	 6530869	       208 ns/op	       8 B/op	       1 allocs/op
BenchmarkAddMod/small/big-6        	16872976	        73.4 ns/op	       8 B/op	       1 allocs/op
BenchmarkAddMod/mod64/big-6        	 6000974	       204 ns/op	      77 B/op	       1 allocs/op
BenchmarkAddMod/mod128/big-6       	 3480322	       355 ns/op	      64 B/op	       1 allocs/op
BenchmarkAddMod/mod192/big-6       	 3627595	       309 ns/op	      61 B/op	       1 allocs/op
BenchmarkAddMod/mod256/big-6       	 4768058	       247 ns/op	      40 B/op	       1 allocs/op
BenchmarkMulMod/small/big-6        	15861763	        77.0 ns/op	       8 B/op	       1 allocs/op
BenchmarkMulMod/mod64/big-6        	 3656503	       330 ns/op	      96 B/op	       1 allocs/op
BenchmarkMulMod/mod128/big-6       	 2104412	       577 ns/op	      96 B/op	       1 allocs/op
BenchmarkMulMod/mod192/big-6       	 2198616	       534 ns/op	      80 B/op	       1 allocs/op
BenchmarkMulMod/mod256/big-6       	 2492029	       536 ns/op	      80 B/op	       1 allocs/op
Benchmark_SDiv/large/big-6         	 2056039	       938 ns/op	     312 B/op	       6 allocs/op
Boolean logic

uint256

Benchmark_And/single/uint256-6     	590464702	         1.93 ns/op	       0 B/op	       0 allocs/op
Benchmark_Or/single/uint256-6      	629714779	         2.06 ns/op	       0 B/op	       0 allocs/op
Benchmark_Xor/single/uint256-6     	625039024	         1.94 ns/op	       0 B/op	       0 allocs/op
Benchmark_Cmp/single/uint256-6     	408978940	         2.90 ns/op	       0 B/op	       0 allocs/op
BenchmarkLt/large/uint256-6        	388216880	         3.14 ns/op	       0 B/op	       0 allocs/op
BenchmarkLt/small/uint256-6        	388475845	         3.37 ns/op	       0 B/op	       0 allocs/op

vs big.Int

Benchmark_And/single/big-6         	86528250	        14.6 ns/op	       0 B/op	       0 allocs/op
Benchmark_Or/single/big-6          	69813108	        17.7 ns/op	       0 B/op	       0 allocs/op
Benchmark_Xor/single/big-6         	66239239	        18.2 ns/op	       0 B/op	       0 allocs/op
Benchmark_Cmp/single/big-6         	160121772	         7.46 ns/op	       0 B/op	       0 allocs/op
BenchmarkLt/large/big-6            	84170188	        12.5 ns/op	       0 B/op	       0 allocs/op
BenchmarkLt/small/big-6            	84369852	        13.2 ns/op	       0 B/op	       0 allocs/op
Bitwise shifts

uint256:

Benchmark_Lsh/n_eq_0/uint256-6     	260736044	         4.61 ns/op	       0 B/op	       0 allocs/op
Benchmark_Lsh/n_gt_192/uint256-6   	208642209	         6.60 ns/op	       0 B/op	       0 allocs/op
Benchmark_Lsh/n_gt_128/uint256-6   	185939301	         6.29 ns/op	       0 B/op	       0 allocs/op
Benchmark_Lsh/n_gt_64/uint256-6    	134935269	         8.84 ns/op	       0 B/op	       0 allocs/op
Benchmark_Lsh/n_gt_0/uint256-6     	100000000	        10.6 ns/op	       0 B/op	       0 allocs/op
Benchmark_Rsh/n_eq_0/uint256-6     	267984342	         4.47 ns/op	       0 B/op	       0 allocs/op
Benchmark_Rsh/n_gt_192/uint256-6   	226595919	         5.46 ns/op	       0 B/op	       0 allocs/op
Benchmark_Rsh/n_gt_128/uint256-6   	174888495	         7.03 ns/op	       0 B/op	       0 allocs/op
Benchmark_Rsh/n_gt_64/uint256-6    	135138018	         9.03 ns/op	       0 B/op	       0 allocs/op
Benchmark_Rsh/n_gt_0/uint256-6     	100000000	        10.8 ns/op	       0 B/op	       0 allocs/op

vs big.Int:

Benchmark_Lsh/n_eq_0/big-6         	22462352	        52.2 ns/op	      64 B/op	       1 allocs/op
Benchmark_Lsh/n_gt_192/big-6       	18483247	        69.3 ns/op	      96 B/op	       1 allocs/op
Benchmark_Lsh/n_gt_128/big-6       	17845354	        67.6 ns/op	      96 B/op	       1 allocs/op
Benchmark_Lsh/n_gt_64/big-6        	19200085	        66.7 ns/op	      80 B/op	       1 allocs/op
Benchmark_Lsh/n_gt_0/big-6         	18988237	        63.1 ns/op	      80 B/op	       1 allocs/op
Benchmark_Rsh/n_eq_0/big-6         	22768628	        54.5 ns/op	      64 B/op	       1 allocs/op
Benchmark_Rsh/n_gt_192/big-6       	29468035	        38.1 ns/op	       8 B/op	       1 allocs/op
Benchmark_Rsh/n_gt_128/big-6       	23145200	        54.2 ns/op	      48 B/op	       1 allocs/op
Benchmark_Rsh/n_gt_64/big-6        	19201986	        86.3 ns/op	      64 B/op	       1 allocs/op
Benchmark_Rsh/n_gt_0/big-6         	20327937	        62.3 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

Constants

This section is empty.

Variables

This section is empty.

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 

func FromBig(b *big.Int) (*Int, bool)

FromBig is a convenience-constructor from big.Int. Returns a new Int and whether overflow occurred.

func NewInt 

func NewInt() *Int

func (*Int) Abs 

func (z *Int) Abs(x *Int) *Int

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) Add 

func (z *Int) Add(x, y *Int) *Int

Add sets z to the sum x+y

func (*Int) AddMod 

func (z *Int) AddMod(x, y, m *Int) *Int

AddMod sets z to the sum ( x+y ) mod m, and returns z

func (*Int) AddOverflow 

func (z *Int) AddOverflow(x, y *Int) bool

AddOverflow sets z to the sum x+y, and returns whether overflow occurred

func (*Int) And 

func (z *Int) And(x, y *Int) *Int

And sets z = x & y and returns z.

func (*Int) BitLen 

func (z *Int) BitLen() int

BitLen returns the number of bits required to represent x

func (*Int) Byte 

func (z *Int) Byte(n *Int) *Int

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) ByteLen 

func (z *Int) ByteLen() int

func (*Int) Bytes 

func (z *Int) Bytes() []byte

Bytes returns the value of z as a big-endian byte slice.

func (*Int) Bytes20 

func (z *Int) Bytes20() [20]byte

Bytes20 returns a the a 32 byte big-endian array.

func (*Int) Bytes32 

func (z *Int) Bytes32() [32]byte

Bytes32 returns a the a 32 byte big-endian array.

func (*Int) Clear 

func (z *Int) Clear() *Int

Clear sets z to 0

func (*Int) Clone 

func (z *Int) Clone() *Int

Clone create a new Int identical to z

func (*Int) Cmp 

func (z *Int) Cmp(x *Int) (r int)

Cmp compares z and x and returns: 

-1 if z <  x
 0 if z == x
+1 if z >  x

func (*Int) Div 

func (z *Int) Div(x, y *Int) *Int

Div sets z to the quotient x/y for returns z. If d == 0, z is set to 0

func (*Int) Eq 

func (z *Int) Eq(x *Int) bool

Eq returns true if z == x

func (*Int) Exp 

func (z *Int) Exp(base, exponent *Int) *Int

Exp sets z = base**exponent mod 2**256, and returns z.

func (*Int) ExtendSign added in v1.0.0 

func (z *Int) ExtendSign(x, byteNum *Int) *Int

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 

func (z *Int) Format(s fmt.State, ch rune)

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) Gt 

func (z *Int) Gt(x *Int) bool

Gt returns true if z > x

func (*Int) GtUint64 

func (z *Int) GtUint64(n uint64) bool

LtUint64 returns true if x is larger than n

func (*Int) IsUint64 

func (z *Int) IsUint64() bool

IsUint64 reports whether z can be represented as a uint64.

func (*Int) IsZero 

func (z *Int) IsZero() bool

IsZero returns true if z == 0

func (*Int) Lsh 

func (z *Int) Lsh(x *Int, n uint) *Int

Lsh sets z = x << n and returns z.

func (*Int) Lt 

func (z *Int) Lt(x *Int) bool

Lt returns true if z < x

func (*Int) LtUint64 

func (z *Int) LtUint64(n uint64) bool

LtUint64 returns true if x is smaller than n

func (*Int) Mod 

func (z *Int) Mod(x, y *Int) *Int

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) Mul 

func (z *Int) Mul(x, y *Int) *Int

Mul sets z to the sum x*y

func (*Int) MulMod 

func (z *Int) MulMod(x, y, m *Int) *Int

MulMod calculates the modulo-n multiplication of x and y and returns z

func (*Int) Neg 

func (z *Int) Neg(x *Int) *Int

Neg returns -x mod 2**256.

func (*Int) Not 

func (z *Int) Not(x *Int) *Int

Not sets z = ^x and returns z.

func (*Int) Or 

func (z *Int) Or(x, y *Int) *Int

Or sets z = x | y and returns z.

func (*Int) PaddedBytes 

func (z *Int) PaddedBytes(n int) []byte

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) Rsh 

func (z *Int) Rsh(x *Int, n uint) *Int

Rsh sets z = x >> n and returns z.

func (*Int) SDiv added in v1.0.0 

func (z *Int) SDiv(n, d *Int) *Int

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 added in v1.0.0 

func (z *Int) SMod(x, y *Int) *Int

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 added in v1.0.0 

func (z *Int) SRsh(x *Int, n uint) *Int

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) Set added in v1.0.0 

func (z *Int) Set(x *Int) *Int

Set sets z to x and returns z.

func (*Int) SetAllOne 

func (z *Int) SetAllOne() *Int

SetAllOne sets all the bits of z to 1

func (*Int) SetBytes 

func (z *Int) SetBytes(buf []byte) *Int

SetBytes interprets buf as the bytes of a big-endian unsigned integer, sets z to that value, and returns z.

func (*Int) SetFromBig 

func (z *Int) SetFromBig(b *big.Int) bool

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) SetOne 

func (z *Int) SetOne() *Int

SetOne sets z to 1

func (*Int) SetUint64 

func (z *Int) SetUint64(x uint64) *Int

SetUint64 sets z to the value x

func (*Int) Sgt 

func (z *Int) Sgt(x *Int) bool

Sgt interprets z and x as signed integers, and returns true if z > x

func (*Int) Sign 

func (z *Int) Sign() int

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) Slt 

func (z *Int) Slt(x *Int) bool

Slt interprets z and x as signed integers, and returns true if z < x

func (*Int) Sub 

func (z *Int) Sub(x, y *Int) *Int

Sub sets z to the difference x-y

func (*Int) SubOverflow 

func (z *Int) SubOverflow(x, y *Int) bool

Sub sets z to the difference x-y and returns true if the operation underflowed

func (*Int) SubUint64 added in v1.0.0 

func (z *Int) SubUint64(x *Int, y uint64) *Int

SubUint64 set z to the difference x - y, where y is a uint64, and returns z

func (*Int) ToBig 

func (z *Int) ToBig() *big.Int

ToBig returns a big.Int version of z.

func (*Int) Uint64 

func (z *Int) Uint64() uint64
func (z *Int) WriteToArr32(dest [32]bytes){
	for i := 0; i < 32; i++ {
		dest[31-i] = byte(z[i/8] >> uint64(8*(i%8)))
	}
}

Uint64 returns the lower 64-bits of z

func (*Int) Uint64WithOverflow 

func (z *Int) Uint64WithOverflow() (uint64, bool)

Uint64 returns the lower 64-bits of z and bool whether overflow occurred

func (*Int) WriteToArray20 

func (z *Int) WriteToArray20(dest *[20]byte)

WriteToArray20 writes the last 20 bytes of z to the destination array, including zero-bytes

func (*Int) WriteToArray32 

func (z *Int) WriteToArray32(dest *[32]byte)

WriteToArray32 writes all 32 bytes of z to the destination array, including zero-bytes

func (*Int) WriteToSlice 

func (z *Int) WriteToSlice(dest []byte)

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 (*Int) Xor 

func (z *Int) Xor(x, y *Int) *Int

Xor sets z = x ^ y and returns z.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.