Handle nominator smaller than divisor in udivrem()

[chfast]

I wanted to make udivrem() more robust by making it handle the case where nominator is smaller than divisor (currently it will panic weirdly in this case).

I'm testing the change though TestRandomDiv and TestRandomMod where divraw and modraw wrappers are provided.

The modraw fails a test when a param and result are aliased. I have not been able to figure out the cause of the problem so far.

[holiman]

It has nothing to do with the argument aliasiing. Here's a repro:

func TestBar(t *testing.T) {
	argA := new(Int)
	argB := new(Int)
	argA.fromHex("0x66aa0a5319bcf5cb4")
	argB.fromHex("0x1ce97e1ab91a")
	z := new(Int)
	modraw(z, argB.Clone(), argA.Clone())
	fmt.Printf("z: %x\n", z)

	b1a, b2a := argA.ToBig(), argB.ToBig()

	bigintFunc := func(b1, b2, b3 *big.Int) {
		if b3.Sign() == 0 {
			b1.SetUint64(0)
		} else {
			b1.Mod(b2, b3)
		}
	}

	bigintFunc(b1a, b2a, b1a)
	fmt.Printf("z: %x\n", b1a)
}

I think it's related to the early return here: https://github.com/holiman/uint256/pull/111/files#diff-af4a4c8b4e176a360fd1472a72691c2ffab2426e94f4e69829a48bd12f01a908R512

[holiman]

Shouldn't it rather be something like this:

	if uLen < dLen {
		copy(rem[:], u[:])
		return rem
	}

[Planxnx]

in case x%y and y greater than x
I think remainder it should be x not y
cause 1234/5678 = 0 remainder 1234
so it should be

        if uLen < dLen {
		copy(rem[:], u[:])
		return rem
	}

thanks @holiman

[Planxnx]

in case x%y and y greater than x I think remainder it should be x not y cause 1234/5678 = 0 remainder 1234 so it should be

        if uLen < dLen {
		copy(rem[:], u[:])
		return rem
	}

thanks @holiman

I have tested and all tests got PASS with coverage: 99.3% of statements

[Planxnx]

from #111 (comment) ,so it should be

        if uLen < dLen {
		copy(rem[:], u[:])
		return rem
	}

[holiman]

Heh, I think the point has already been made :)

[Planxnx]

Sorry, I just wanted to formal mark this point 😂

[chfast]

Except we need to handle u[:] more carefully here because it may be bigger than Int. Is rem Int all zeros at function start?

[holiman]

Yes, rem is initialized blank.

[chfast]

Should be good now. Do you think we should benchmark this?

[codecov]

Codecov Report

Merging #111 (6453f66) into master (045cdb6) will not change coverage.
The diff coverage is 100.00%.

@@            Coverage Diff            @@
##            master      #111   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files            4         4           
  Lines         1385      1388    +3     
=========================================
+ Hits          1385      1388    +3     

[holiman]

LGTM

[holiman]

Do you think we should benchmark this?

I mean, doesn't hurt, but not a blocker for me

[chfast]

It makes it faster (probably by accident).

name                      old time/op  new time/op  delta
Div/small/uint256-8       10.7ns ± 0%  10.7ns ± 0%  +0.25%  (p=0.005 n=8+8)
Div/mod64/uint256-8       55.3ns ± 0%  55.0ns ± 0%  -0.50%  (p=0.000 n=9+10)
Div/mod128/uint256-8      81.6ns ± 0%  80.6ns ± 0%  -1.22%  (p=0.000 n=9+9)
Div/mod192/uint256-8      75.2ns ± 0%  74.5ns ± 0%  -0.86%  (p=0.000 n=10+9)
Div/mod256/uint256-8      63.9ns ± 0%  62.6ns ± 0%  -1.93%  (p=0.000 n=9+9)
Mod/small/uint256-8       11.9ns ± 0%  11.9ns ± 0%  -0.22%  (p=0.049 n=8+9)
Mod/mod64/uint256-8       59.0ns ± 0%  58.8ns ± 0%  -0.36%  (p=0.000 n=8+10)
Mod/mod128/uint256-8      85.1ns ± 0%  84.0ns ± 0%  -1.22%  (p=0.000 n=8+9)
Mod/mod192/uint256-8      79.0ns ± 0%  78.5ns ± 0%  -0.63%  (p=0.000 n=8+7)
Mod/mod256/uint256-8      67.9ns ± 0%  67.4ns ± 0%  -0.78%  (p=0.000 n=9+8)
AddMod/small/uint256-8    11.4ns ± 1%  11.4ns ± 0%    ~     (p=0.200 n=10+9)
AddMod/mod64/uint256-8    18.4ns ± 1%  18.1ns ± 0%  -1.67%  (p=0.000 n=10+8)
AddMod/mod128/uint256-8   37.2ns ± 0%  36.9ns ± 0%  -0.88%  (p=0.000 n=9+9)
AddMod/mod192/uint256-8   40.3ns ± 1%  40.0ns ± 0%  -0.71%  (p=0.000 n=10+10)
AddMod/mod256/uint256-8   15.4ns ± 0%  15.4ns ± 0%    ~     (p=0.761 n=8+10)
MulMod/small/uint256-8    28.8ns ± 1%  28.7ns ± 0%    ~     (p=0.502 n=9+8)
MulMod/mod64/uint256-8    67.8ns ± 0%  67.8ns ± 0%    ~     (p=0.481 n=9+10)
MulMod/mod128/uint256-8    103ns ± 0%   102ns ± 0%  -1.15%  (p=0.000 n=8+10)
MulMod/mod192/uint256-8    131ns ± 0%   129ns ± 0%  -1.03%  (p=0.000 n=10+9)
MulMod/mod256/uint256-8    150ns ± 0%   150ns ± 0%    ~     (p=0.135 n=10+10)
MulMod/mod256/uint256r-8  51.5ns ± 0%  51.3ns ± 0%  -0.41%  (p=0.000 n=9+8)
_SDiv/large/uint256-8     83.0ns ± 1%  82.3ns ± 0%  -0.79%  (p=0.000 n=9+9)
[Geo mean]                47.0ns       46.7ns       -0.66%

[chfast]

It looks that with additional check and "copy/return" block the total number of instructions is almost exactly the same as before so maybe this saves us some additional bounds checks down the line. https://godbolt.org/z/jq5KesEen

[holiman]