Task

Implement integer division based on Knuth's algorithm D. The algo is described in the book "Hackers Delight", and is implemented in a lot of places over the internet.
The golang int lib uses it internally, with asm backing.

One implementation: https://deamentiaemundi.wordpress.com/2014/10/01/multiprecision-long-division-knuths-algorithm-d/
64/32 bit: http://www.hackersdelight.org/hdcodetxt/divmnu64.c.txt
Golang impl: https://golang.org/src/math/big/nat.go#L611

The task requires

• Implementing it in pure go (no asm)
• The implementation must work on both big-endian and little-endian systems

Extend this library for 512-bit types

This #141 broke 100% coverage, need a touch-up

1. Full test coverage: https://codecov.io/gh/holiman/uint256
2. Inspect Exp() implementation (constant time, but gas cost proportional to exponent size).
3. Remove unneeded public functions.
4. Fix SDiv(), SMod() - they modify arguments.
5. Review decision to return zero on division by zero. #62 #64
6. Test arm architecture?
7. Test any big-endian architecture? #60
8. Unify names: Sub64() vs LtUint64(). #65
9. Run benchmarks against 0.1 version.

When calling Bytes32() on an Int [4]uint64{uint64(0), uint64(0), uint64(0), uint64(1)} (according to directions here https://github.com/holiman/uint256/blob/master/uint256.go#L40 where Int[3] is most significant), I get the following bytes:

[0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

There are a few issues with the above:

• If Int[3] is most significant and Int[0] is least significant as per https://github.com/holiman/uint256/blob/master/uint256.go#L40, then that would be big-endian order rather than little-endian as described
• the marshaling of the input is neither in big or little-endian order

If I call Bytes32() on an Int [4]uint64{uint64(1), uint64(0), uint64(0), uint64(0)} (where the input is in little-endian order, with most significant at Int[0]), I get the following output:

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]

The output above is in big-endian order which contradicts the description here: https://github.com/holiman/uint256/blob/master/uint256.go#L99

Expected behavior:

Input of [4]uint64{uint64(1), uint64(0), uint64(0), uint64(0)} marshals to []byte{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} when Bytes32() is called on Input.

hi @holiman, could you make a new tag / release? There are so many improvements / additions since the last tag.

thank you

We have started using https://github.com/holiman/uint256 at https://github.com/stellar/go and we are missing the DivMod() method.

This has required invoking Div() and Mod() separately, which isn't great for performance.

Feature

func (*uint256.Int) CmpBig(big.Int) int

Motivation

Generally uint256.Int is superior and should replace big.Int everywhere. But in forked or in sufficiently large codebases it may not be practical or necessary to replace all instances. At the boundaries, this function could circumvent an explicit conversion.

I didn't find this feature when I looked for it so please close this if it already exists.

thank you

Hi,

We have a problem converting hash values into uint256 as uint256.FromHex() does not accept hex values with leading zeroes. Is there a particular reason for this?
Why do I think this behavior is inconsistent? I can easily convert byte array with leading zeroes to uint256:

uint256.NewInt(0).SetBytes([]byte{0x00, 0x01})

It would be nice to be able to covert using FromHex() directly without intermediate manipulations.
Thanks

The 1.2.0 release broke the API, and thus should have been 2.0.0
The breaking change came in b323bdc
Where NewInt() changed to NewInt(val uint64).

This breaks MVS, and thus all libraries depending on your library, like go-ethereum where currently new developers importing go-ethereum will get the latest compatible version of uint256 (the latest in version 1 which is 1.2.0) but is not actually compatible.
The result is new developers not being able to build their projects.

The steps to rectify this is:

• retract version 1.2.0 so that MVS no longer selects it, see: https://golang.org/ref/mod#go-mod-file-retract
• tag a new 2.0.0 version

Hi, I would like to ask if it would be possible to license this code under a more permissive license. GPL is viral and LGPL is hard to apply to Golang as there are no shared libraries.

MIT or Apache-2 would work best the projects I would like to use it for (libp2p/ipfs).

I fully understand any objections against it.

When printing ints in logs or console, it's usually better to print as a decimal vs hex. But there's no way to flatten a uint256 Int currently into a decimal string. It feels a bit wonky to do uint256.Int.ToBig().String()

We now have rlp encoding, and can encode RLP. However, RLP decoding requires to implement this interface: https://github.com/ethereum/go-ethereum/blob/44b41641f8220fe79e43461356c147cc3cc72380/rlp/decode.go#L64

I.e,

type Decoder interface {
	DecodeRLP(*Stream) error
}

Where *Stream is this struct from the same package.

If we want uint256.Int to implement that, it would require adding rlp as a dependency :( .

@fjl any ideas to get us out of this? Seems quirky, from API-perspective, to have Encoder interface be implementable without rlp-dependency, but have the Decoder interface depend on package rlp.

@holiman, can you enable this project on Circle CI? https://circleci.com/gh/organizations/holiman/settings#projects

I will take care of the rest.

We are getting overflow errors in go-ethereum from the uint256.FromBig method.

R, ok = uint256.FromBig((*big.Int)(dec.R))

Here are the logs with the values that cause the overflow error (dec.R.String()).

INFO   [0007] (tx-listener.session.ethereum.hook): block processed  block_number=5263607 chain=4b0aed40-c2da-44b1-9396-50233910590e owner_id= tenant_id=_
'r' value overflows uint256: 0xb75685b724028d4cc66bd8ff0aa46b6e4721842ac1f7f4880563b581dcfb2ee
's' value overflows uint256: 0x4cdd5a8417fa2c49aa472b8e079e01f276120089ea0c7b27df4533193876abed
'v' value overflows uint256: 0x1
'r' value overflows uint256: 0x241bff69a5506e1a26543b97b22854ec556f822b71627a3136f245e05b98fda9
's' value overflows uint256: 0x7a8ee9210af64eee6e3a15b331ea7d491d3d983f93d52b06f97282a050a9e973
'v' value overflows uint256: 0x1

That does not seem right. What is going wrong here?

Thanks for cheking!

Negative value change after uint256.FromBig and then ToBig:

func TestReverse(t *testing.T) {
	a, _ := big.NewInt(0).SetString("-1", 10)
	u, _ := uint256.FromBig(a)
	areverse := u.ToBig()
	fmt.Println(areverse, areverse.Sign(), a.Sign())
	// areverse:  115792089237316195423570985008687907853269984665640564039457584007913129639935 1 -1
}

https://en.wikipedia.org/wiki/Intel_ADX for adcx/adox and mulx/sarx/shrx/shlx being in bmi2.
I recognize the gcc-go for accessing them as compiler defined functions/instructions instead of raw assembly.

gmp/mpir is using them along other extensions for most cpu instructions sets.

The current implementation is done by bits manipulation on whole 256-bit values (as you would do it for architecture native integers). There exists more efficient implementation which handles each of 4 64-bit words separately. This has been implemented in evmone in ethereum/evmone#390.

Can there be a natural log or base 2 log implemented?
Thanks

Hey,

it would be nice to have a math/big.Int SetString equivalent so that we can re-use Int objects without releasing to GC. Maybe just expose (z *Int) fromHex(hex string)?

Thanks