Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Signed math on Cat gives incorrect results #473

Closed
pepijndevos opened this issue Aug 14, 2020 · 9 comments
Closed

Signed math on Cat gives incorrect results #473

pepijndevos opened this issue Aug 14, 2020 · 9 comments

Comments

@pepijndevos
Copy link
Contributor

Consider the following minimal example:

from nmigen import *
from nmigen.sim.pysim import *

def resolve(expr):
    sim = Simulator(Module())
    a = []
    def testbench():
        a.append((yield expr))
    sim.add_process(testbench)
    sim.run()
    return a[0]

sig = Const(-3, 8)
print(sig, sig.shape())
print(bin(resolve(sig)))
print(bin(resolve(-sig)))

sig2 = Cat(sig).as_signed()
print(sig2, sig2.shape())
print(bin(resolve(sig2)))
print(bin(resolve(-sig2)))

Which prints

(const 8'sd-3) signed(8)
-0b11
0b11
(s (cat (const 8'sd-3))) signed(8)
-0b11
-0b11111101

Of course python's binary representation is a bit misleading here. -0b11 should actually be 0b111...1101 in two's complement.
So actually -0b11111101 would be 0b1111...1100000011 IIRC, which is 3 except not sign-extended.

So it appears that when you put a signed number in a Cat and convert that to signed, the result is not sign-extended correctly.

@whitequark
Copy link
Member

Good catch!

@pepijndevos
Copy link
Contributor Author

pepijndevos commented Aug 15, 2020

I thought about it a bit more, and actually the result is obviously sign-extended, but I believe the issues is related to the width of the result. The result of negating an 8-bit number is a 9-bit number, and the result we get from the cat case only has 8 correct bits. Maybe there is some code that understandably but incorrectly assumes the result of a negation does not increase the width. (recall that the range of a signed number is -2^n to 2^n-1, so negating 10000000 would overflow and produce 10000000)

Is there an easy way to confirm this bug is specific to pysim? I see there are many backends, but not sure how easy it is to simulate their output from within Python, or you'd have to write say a whole Verilog testbench and run it in verilator.

@whitequark
Copy link
Member

Maybe there is some code that understandably but incorrectly assumes the result of a negation does not increase the width.

The only place where this happens is here: https://github.com/nmigen/nmigen/blob/73f672f57c606ac29087ffb09c43a7e4d9a9dfc6/nmigen/hdl/ast.py#L678-L679

you'd have to write say a whole Verilog testbench and run it in verilator.

This.

@pepijndevos
Copy link
Contributor Author

I added some debugging:

(const 8'sd-3) signed(8)
compile ((b'result = -3\n', '<string>'),)
-0b11
compile ((b'result = (--3)\n', '<string>'),)
0b11
(s (cat (const 8'sd-3))) signed(8)
compile ((b'result = (((-3 & 255) << 0))\n', '<string>'),)
-0b11
compile ((b'result = (-(((-3 & 255) << 0)))\n', '<string>'),)
-0b11111101

I believe this mask originates here

https://github.com/nmigen/nmigen/blob/30e2f91176edcd1c8766c2cb11f413b9c77936b9/nmigen/sim/_pyrtl.py#L183-L192

I'm not sure exactly what is going on with the masking and what would be the correct solution.

@whitequark
Copy link
Member

Looks like .as_signed() gets ignored in the second case; the masking for Cat seems fine.

@pepijndevos
Copy link
Contributor Author

pepijndevos commented Aug 15, 2020

What effect is .as_signed() expected to have on the Python side?
https://github.com/nmigen/nmigen/blob/30e2f91176edcd1c8766c2cb11f413b9c77936b9/nmigen/sim/_pyrtl.py#L129-L131

I don't think the masking is fine. It's basically masked to 8 bits, then negated, and then 9 bits of the result are used, leaving the MSB inverted. But maybe something else is missing.

@whitequark
Copy link
Member

What effect is .as_signed() expected to have on the Python side?

None; exactly as the comment says. Treating the bits as signed or unsigned doesn't change the bits, it changes how the bits are treated by arithmetic operations that follow.

I don't think the masking is fine.

The masking code performed by Cat is fine because Cat doesn't care about bitness at all, neither for its inputs (which it does not extend and does not perform arithmetics on) nor for its output (which is treated as unsigned). There's of course still a bug somewhere else.

@whitequark whitequark added this to the 0.3 milestone Aug 26, 2020
@whitequark
Copy link
Member

(The bug was in the implementation of negation.)

@pepijndevos
Copy link
Contributor Author

Thank you)))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Development

No branches or pull requests

2 participants