Right shift gives wrong result

[shuklaayush]

Aim

One of the tests in the noir-bigint library is failing because 0x80000000000000 >> 0x37 (as u56) is evaluating to 0 instead of 1

I wasn't able to create a minimal reproducible example but you can check it if you run

nargo test --package biguint --show-output test_div3

This test is failing and the relevant lines of code are here

Expected Behavior

Right shift should be calculated properly

Bug

0x80000000000000 >> 0x37 is evaluating to 0 instead of 1

To Reproduce

1. Clone https://github.com/shuklaayush/noir-bigint/tree/debug/print-shl1-debug
2. Run nargo test --package biguint --show-output test_div3

Installation Method

Binary

Nargo Version

nargo 0.12.0 (git version hash: 7b3df8e, is dirty: false)

Additional Context

No response

Would you like to submit a PR for this Issue?

Maybe

Support Needs

No response

[vezenovm]

I was unable to reproduce a runtime or comptime bitshift of 0x80000000000000 >> 0x37 that did not give 1. It looks like your program has an overflow. I see in your program you even have a TODO about returning early when n is zero here, because this can cause you to potentially right shift by 0x38 which is 56 and would cause an overflow. When running this program with #2713 I fail with Failed assertion: 'attempt to subtract with overflow'. I am going to leave this issue open until the overflow PR is finished.

So the bug looks to actually be that the prints are out of order when used in a loop in this manner. For example I should always have prints in this format:

"------------------"
"self.limbs[i - 1]"
0x00
"rshift"
0x37
"self.limbs[i - 1] >> rshift"
0x00
"0x80000000000000 >> rshift"
0x01

but I got this sometimes:

"------------------"
"self.limbs[i - 1]"
0x00
"rshift"
0x37
"self.limbs[i - 1] >> rshift"
0x00
"0x80000000000000 >> rshift"
0x01
0x01
0x38

I am going to reproduce the printing issue and make a separate issue for that.

[shuklaayush]

this can cause you to potentially right shift by 0x38 which is 56 and would cause an overflow

I don't believe right shifting should cause an overflow with any inputs. If the shift is by 56, then shouldn't it just return 0?

When running this program with #2713 I fail with Failed assertion: 'attempt to subtract with overflow'.

I'll take a look but I would assume this is coming from other parts of the code that depends on wrapping operations

If you look at the screenshot, then one of the series of logs is the following

"------------------"
"self.limbs[i - 1]"
0x80000000000000
"rshift"
0x37
"self.limbs[i - 1] >> rshift"
0x00
"0x80000000000000 >> rshift"
0x01
"------------------"

This is wrong since 0x80000000000000 >> 0x37 should be 0x01 and not 0x00. I wasn't able to create a minimal example that reproduces this. Maybe it's because the prints are out of order, but they seem pretty orderly on my machine

[shuklaayush]

I don't believe right shifting should cause an overflow with any inputs. If the shift is by 56, then shouldn't it just return 0?

Actually, I was wrong. This is considered overflowing behaviour in rust. The test works if I handle the overflowing case separately