RiscV checking if overflow has occurred during multiplication

Question

using this algorithm to calculate a multiplication of signed integers (we cant use mul, mulh etc so I implemented the mul with shift and add) how can you check if the result has overflown. The product has to stay in 32 bits

I tried using some of the overflow condition such as (a * b = c):

1. a > 0 and b > 0 c < 0 this means the result has overflown.
2. a < 0 and b < 0 c > 0 this means the result has overflown.

But, for example when a = -3434421 and b = -12555 the program cant understand it has overflown. I am thinking that probably the condition of overflow arent correct.

Answer 1

It seems you're doing this arithmetic in 32 bits.

But multiplication of two 32-bit numbers produces a 64-bit result (without any possibility of overflow).

If you consider only the lower 32 bits of the answer, that is meaningless with multiplication because there are so many bits being ignored.

This approach of looking at the low 32 bits only works with addition, and there it works because adding two 32-bit numbers results in a 33-bit number (without any possibility of overflow), so truncating a 33-bit addition result to 32-bits, we can still detect overflow by looking at the original input values compared with the truncated (32-bit) result.

---

To detect overflow of multiplication using a 32-bit shift & add approach, you must check for overflow at addition and at the left shift — and each and every iteration, and then either early out on overflow or make overflow "sticky" so once set it is set it stays set.

---

Alternately, compute the full 64-bit result of the 32×32 input operands, and then see if the 64-bit number fits in 32 bits with the same numeric value.

That can be done by taking the lower 32-bits and sign extending to 64-bits, the compare the two 64-bit values for equality.

Or else, more primitively, take the sign (MSB) bit of the lower 32-bit portion and if set, verify the upper 32 bits is all 1's, or if clear, then verify the upper 32 bits are all 0's, to make sure the 32 bit truncation hasn't lost value (overflow).

Algorithmically, a naïve approach is to convert both 32-bit numbers to 64 bits, the do 64×64 multiplication, keeping only the low 64 bits, knowing that this cannot overflow because the input numbers were only 32 bits to start with, then attempt to truncate to 32 bits to see if that overflows.

---

a < 0 and b < 0 c > 0 this means the result has overflown

This formula is simply wrong because -1 × -1 = 1 (so a<0, b<0, c>0) yet there is no overflow here (in truncating the result to 32 bits).