uint256

package module
v0.1.0 Latest Latest
Warning

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

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

README

Fixed size math

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.

As of 2020-03-18, the fixed lib wins over big in every single case, often with orders of magnitude. As of release 0.1.0, the uint256 library is alloc-free!

Conversion from/to big.Int
BenchmarkSetFromBig/1word-6        	259504869	         4.61 ns/op	       0 B/op	       0 allocs/op
BenchmarkSetFromBig/2words-6       	243296958	         5.08 ns/op	       0 B/op	       0 allocs/op
BenchmarkSetFromBig/3words-6       	227551600	         5.15 ns/op	       0 B/op	       0 allocs/op
BenchmarkSetFromBig/4words-6       	246922267	         5.26 ns/op	       0 B/op	       0 allocs/op
BenchmarkSetFromBig/overflow-6     	238420483	         5.07 ns/op	       0 B/op	       0 allocs/op
BenchmarkToBig/1word-6             	14952933	        71.1 ns/op	      64 B/op	       2 allocs/op
BenchmarkToBig/2words-6            	17000169	        72.5 ns/op	      64 B/op	       2 allocs/op
BenchmarkToBig/3words-6            	14798148	        72.2 ns/op	      64 B/op	       2 allocs/op
BenchmarkToBig/4words-6            	15954582	        69.9 ns/op	      64 B/op	       2 allocs/op
Math operations

uint256:

enchmark_Add/single/uint256-6     	633472188	         1.89 ns/op	       0 B/op	       0 allocs/op
Benchmark_Sub/single/uint256-6     	568273075	         2.22 ns/op	       0 B/op	       0 allocs/op
Benchmark_Sub/single/uint256_of-6  	567779286	         2.11 ns/op	       0 B/op	       0 allocs/op
Benchmark_Mul/single/uint256-6     	62855088	        17.8 ns/op	       0 B/op	       0 allocs/op
Benchmark_Square/single/uint256-6  	64012897	        18.9 ns/op	       0 B/op	       0 allocs/op
Benchmark_Exp/large/uint256-6      	  153199	      7749 ns/op	       0 B/op	       0 allocs/op
Benchmark_Exp/small/uint256-6      	 1808989	       663 ns/op	       0 B/op	       0 allocs/op
BenchmarkDiv/mod64/uint256-6       	18118854	        64.7 ns/op	       0 B/op	       0 allocs/op
BenchmarkDiv/mod128/uint256-6      	10897378	       109 ns/op	       0 B/op	       0 allocs/op
BenchmarkDiv/mod192/uint256-6      	10550451	        99.1 ns/op	       0 B/op	       0 allocs/op
BenchmarkDiv/mod256/uint256-6      	13321220	        84.6 ns/op	       0 B/op	       0 allocs/op
BenchmarkMod/small/uint256-6       	78706082	        14.2 ns/op	       0 B/op	       0 allocs/op
BenchmarkMod/mod64/uint256-6       	17726313	        67.4 ns/op	       0 B/op	       0 allocs/op
BenchmarkMod/mod128/uint256-6      	10611421	       112 ns/op	       0 B/op	       0 allocs/op
BenchmarkMod/mod192/uint256-6      	11801432	       101 ns/op	       0 B/op	       0 allocs/op
BenchmarkMod/mod256/uint256-6      	13408267	        86.2 ns/op	       0 B/op	       0 allocs/op
BenchmarkAddMod/small/uint256-6    	63672259	        18.6 ns/op	       0 B/op	       0 allocs/op
BenchmarkAddMod/mod64/uint256-6    	13364508	        76.5 ns/op	       0 B/op	       0 allocs/op
BenchmarkAddMod/mod128/uint256-6   	 9374313	       128 ns/op	       0 B/op	       0 allocs/op
BenchmarkAddMod/mod192/uint256-6   	 9662953	       121 ns/op	       0 B/op	       0 allocs/op
BenchmarkAddMod/mod256/uint256-6   	11169826	       108 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulMod/small/uint256-6    	26907108	        44.5 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulMod/mod64/uint256-6    	10069104	       120 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulMod/mod128/uint256-6   	 5551214	       215 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulMod/mod192/uint256-6   	 5677230	       209 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulMod/mod256/uint256-6   	 5793927	       204 ns/op	       0 B/op	       0 allocs/op
Benchmark_SDiv/large/uint256-6     	11370470	       105 ns/op	       0 B/op	       0 allocs/op

vs big.Int

Benchmark_Add/single/big-6         	55087052	        21.5 ns/op	       0 B/op	       0 allocs/op
Benchmark_Sub/single/big-6         	55020072	        21.4 ns/op	       0 B/op	       0 allocs/op
Benchmark_Mul/single/big-6         	 9587319	       119 ns/op	      96 B/op	       1 allocs/op
Benchmark_Square/single/big-6      	 9989365	       128 ns/op	      96 B/op	       1 allocs/op
Benchmark_Exp/large/big-6          	   44059	     27808 ns/op	   18264 B/op	     192 allocs/op
Benchmark_Exp/small/big-6          	  132482	      8094 ns/op	    7512 B/op	      80 allocs/op
BenchmarkDiv/small/big-6           	20346138	        56.6 ns/op	       8 B/op	       1 allocs/op
BenchmarkDiv/mod64/big-6           	 8671370	       139 ns/op	       8 B/op	       1 allocs/op
BenchmarkDiv/mod128/big-6          	 3985227	       301 ns/op	      80 B/op	       1 allocs/op
BenchmarkDiv/mod192/big-6          	 4860343	       249 ns/op	      80 B/op	       1 allocs/op
BenchmarkDiv/mod256/big-6          	 4927914	       256 ns/op	      80 B/op	       1 allocs/op
BenchmarkMod/small/big-6           	23049183	        51.9 ns/op	       8 B/op	       1 allocs/op
BenchmarkMod/mod64/big-6           	 7158260	       162 ns/op	      64 B/op	       1 allocs/op
BenchmarkMod/mod128/big-6          	 3976514	       290 ns/op	      64 B/op	       1 allocs/op
BenchmarkMod/mod192/big-6          	 4926200	       312 ns/op	      48 B/op	       1 allocs/op
BenchmarkMod/mod256/big-6          	 6534632	       180 ns/op	       8 B/op	       1 allocs/op
BenchmarkAddMod/small/big-6        	16317876	        71.8 ns/op	       8 B/op	       1 allocs/op
BenchmarkAddMod/mod64/big-6        	 5799704	       201 ns/op	      77 B/op	       1 allocs/op
BenchmarkAddMod/mod128/big-6       	 3470521	       415 ns/op	      64 B/op	       1 allocs/op
BenchmarkAddMod/mod192/big-6       	 4080316	       295 ns/op	      61 B/op	       1 allocs/op
BenchmarkAddMod/mod256/big-6       	 4928460	       239 ns/op	      40 B/op	       1 allocs/op
BenchmarkMulMod/small/big-6        	15940292	        73.8 ns/op	       8 B/op	       1 allocs/op
BenchmarkMulMod/mod64/big-6        	 3570828	       331 ns/op	      96 B/op	       1 allocs/op
BenchmarkMulMod/mod128/big-6       	 2047695	       597 ns/op	      96 B/op	       1 allocs/op
BenchmarkMulMod/mod192/big-6       	 2291578	       514 ns/op	      80 B/op	       1 allocs/op
BenchmarkMulMod/mod256/big-6       	 2463007	       509 ns/op	      80 B/op	       1 allocs/op
Benchmark_SDiv/large/big-6         	 2212314	       544 ns/op	     248 B/op	       5 allocs/op
Boolean logic

uint256

Benchmark_And/single/uint256-6     	534546528	         2.16 ns/op	       0 B/op	       0 allocs/op
Benchmark_Or/single/uint256-6      	620022866	         1.90 ns/op	       0 B/op	       0 allocs/op
Benchmark_Xor/single/uint256-6     	553041696	         2.15 ns/op	       0 B/op	       0 allocs/op
Benchmark_Cmp/single/uint256-6     	433571565	         2.76 ns/op	       0 B/op	       0 allocs/op
BenchmarkLt/large/uint256-6        	407432343	         2.98 ns/op	       0 B/op	       0 allocs/op
BenchmarkLt/small/uint256-6        	361346886	         2.95 ns/op	       0 B/op	       0 allocs/op

vs big.Int

Benchmark_And/single/big-6         	74969566	        15.8 ns/op	       0 B/op	       0 allocs/op
Benchmark_Or/single/big-6          	69831138	        18.0 ns/op	       0 B/op	       0 allocs/op
Benchmark_Xor/single/big-6         	65390836	        17.8 ns/op	       0 B/op	       0 allocs/op
Benchmark_Cmp/single/big-6         	165527830	         7.24 ns/op	       0 B/op	       0 allocs/op
BenchmarkLt/large/big-6            	85042539	        13.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkLt/small/big-6            	93413899	        12.8 ns/op	       0 B/op	       0 allocs/op
Bitwise shifts

uint256:

Benchmark_Lsh/n_eq_0/uint256-6     	275789586	         4.36 ns/op	       0 B/op	       0 allocs/op
Benchmark_Lsh/n_gt_192/uint256-6   	228063312	         5.30 ns/op	       0 B/op	       0 allocs/op
Benchmark_Lsh/n_gt_128/uint256-6   	204222584	         5.81 ns/op	       0 B/op	       0 allocs/op
Benchmark_Lsh/n_gt_64/uint256-6    	144790902	         8.27 ns/op	       0 B/op	       0 allocs/op
Benchmark_Lsh/n_gt_0/uint256-6     	122010325	         9.85 ns/op	       0 B/op	       0 allocs/op
Benchmark_Rsh/n_eq_0/uint256-6     	272249740	         4.36 ns/op	       0 B/op	       0 allocs/op
Benchmark_Rsh/n_gt_192/uint256-6   	240133351	         4.96 ns/op	       0 B/op	       0 allocs/op
Benchmark_Rsh/n_gt_128/uint256-6   	180698709	         6.65 ns/op	       0 B/op	       0 allocs/op
Benchmark_Rsh/n_gt_64/uint256-6    	142424036	         8.70 ns/op	       0 B/op	       0 allocs/op
Benchmark_Rsh/n_gt_0/uint256-6     	120315340	         9.94 ns/op	       0 B/op	       0 allocs/op

vs big.Int:

Benchmark_Lsh/n_eq_0/big-6         	19975887	        51.0 ns/op	      64 B/op	       1 allocs/op
Benchmark_Lsh/n_gt_192/big-6       	17185830	        71.5 ns/op	      96 B/op	       1 allocs/op
Benchmark_Lsh/n_gt_128/big-6       	16629559	        65.7 ns/op	      96 B/op	       1 allocs/op
Benchmark_Lsh/n_gt_64/big-6        	17201168	        62.9 ns/op	      80 B/op	       1 allocs/op
Benchmark_Lsh/n_gt_0/big-6         	16718604	        60.9 ns/op	      80 B/op	       1 allocs/op
Benchmark_Rsh/n_eq_0/big-6         	19647315	        52.7 ns/op	      64 B/op	       1 allocs/op
Benchmark_Rsh/n_gt_192/big-6       	29589792	        37.4 ns/op	       8 B/op	       1 allocs/op
Benchmark_Rsh/n_gt_128/big-6       	18169792	        74.5 ns/op	      48 B/op	       1 allocs/op
Benchmark_Rsh/n_gt_64/big-6        	21416439	        55.2 ns/op	      64 B/op	       1 allocs/op
Benchmark_Rsh/n_gt_0/big-6         	17568159	        58.7 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.
Testing

Also, any help in improving the test framework, e.g. by improving the random testing stuff is very highly appreciated.

The tests are a bit lacking, specifically tests to ensure that function on the form func (z *Int) Foo(a,b *Int)

  • does not modify a or b, if z.Foo(a,b) and z != (a,b)
  • works correctly in both cases a.Foo(a,b) and b.Foo(a,b)
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

View Source 
var (
	SignedMax = &Int{
		0xffffffffffffffff,
		0xffffffffffffffff,
		0xffffffffffffffff,
		0x7fffffffffffffff,
	}
	SignedMin = &Int{
		0x0000000000000000,
		0x0000000000000000,
		0x0000000000000000,
		0x8000000000000000,
	}
)

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

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

func (z *Int) Copy(x *Int) *Int

Copy copies the value x into z, and returns z

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

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

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

func (z *Int) Hex() string

Hex returns a hex representation of z

func (*Int) Int64 

func (z *Int) Int64() int64

Uint64 returns the lower 63-bits of z as int64

func (*Int) IsOne 

func (z *Int) IsOne() bool

IsOne returns true if z == 1

func (*Int) IsUint128 

func (z *Int) IsUint128() bool

IsUint128 reports whether z can be represented in 128 bits.

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

func (*Int) Not 

func (z *Int) Not() *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 

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

Sdiv interprets n and d as signed integers, does a signed division on the two operands and sets z to the result If d == 0, z is set to 0 OBS! This method (potentially) modifies both n and d

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

func (z *Int) SetIfEq(x *Int)

SetIfEq sets x to 1 if z == x 0 if Z != x

func (*Int) SetIfGt 

func (z *Int) SetIfGt(x *Int)

SetIfGt sets z to 1 if z > x

func (*Int) SetIfLt 

func (z *Int) SetIfLt(x *Int)

SetIfLt sets z to 1 if z < x

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 signed number

func (*Int) SignExtend 

func (z *Int) SignExtend(back, num *Int)

Extend length of two’s complement signed integer sets z to

  • num if back > 31
  • num interpreted as a signed number with sign-bit at (back*8+7), extended to the full 256 bits

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

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

Smod interprets x and y as 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) OBS! Modifies x and y

func (*Int) Squared 

func (z *Int) Squared()

func (*Int) Srsh 

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

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

Sub sets z to the difference x-y

func (*Int) Sub64 

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

Sub64 set z to the difference x - y, where y is a 64 bit uint

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