Skip to content

Handle nominator smaller than divisor in udivrem()#111

Merged
chfast merged 1 commit intomasterfrom
udivrem
Mar 17, 2022
Merged

Handle nominator smaller than divisor in udivrem()#111
chfast merged 1 commit intomasterfrom
udivrem

Conversation

@chfast
Copy link
Copy Markdown
Collaborator

@chfast chfast commented Mar 12, 2022

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.

@chfast chfast mentioned this pull request Mar 12, 2022
Merged
@holiman
Copy link
Copy Markdown
Owner

holiman commented Mar 15, 2022

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
Copy link
Copy Markdown
Owner

holiman commented Mar 15, 2022

Shouldn't it rather be something like this:

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

@Planxnx
Copy link
Copy Markdown
Contributor

Planxnx commented Mar 15, 2022 •
edited
Loading

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
Copy link
Copy Markdown
Contributor

Planxnx commented Mar 15, 2022

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
Planxnx reviewed Mar 15, 2022
View reviewed changes
uint256.go
}
}

if uLen < dLen {
Copy link
Copy Markdown
Contributor

@Planxnx Planxnx Mar 15, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

from #111 (comment) ,so it should be

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

Copy link
Copy Markdown
Owner

@holiman holiman Mar 15, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Copy Markdown
Contributor

@Planxnx Planxnx Mar 15, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Sorry, I just wanted to formal mark this point 😂

Copy link
Copy Markdown
Collaborator Author

@chfast chfast Mar 17, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Copy Markdown
Owner

@holiman holiman Mar 17, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes, rem is initialized blank.

@chfast chfast marked this pull request as ready for review March 17, 2022 12:48
@chfast
Copy link
Copy Markdown
Collaborator Author

chfast commented Mar 17, 2022

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

@codecov
Copy link
Copy Markdown

codecov bot commented Mar 17, 2022 •
edited
Loading

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
holiman approved these changes Mar 17, 2022
View reviewed changes
Copy link
Copy Markdown
Owner

@holiman holiman left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@holiman
Copy link
Copy Markdown
Owner

holiman commented Mar 17, 2022

Do you think we should benchmark this?

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

@chfast
Copy link
Copy Markdown
Collaborator Author

chfast commented Mar 17, 2022

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
Copy link
Copy Markdown
Collaborator Author

chfast commented Mar 17, 2022

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
Copy link
Copy Markdown
Owner

holiman commented Mar 17, 2022

:shipit:

@chfast chfast merged commit d97bdee into master Mar 17, 2022
@chfast chfast deleted the udivrem branch March 17, 2022 13:51
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@holiman holiman holiman approved these changes

+1 more reviewer

@Planxnx Planxnx Planxnx left review comments

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@chfast @holiman @Planxnx