Multiplication Overflow
Problem
A commonly overlooked problem with C integral types is multiplication and what happens if the result overflows.
There is useful a StackExchange article on multiplication of large numbers, how to catch overflow.
The nub of the issue is this. Let's take an 8 bit machine and two unsigned numbers and do some maths:
uint8_t n1 = 129; uint8_t n2 = 129; uint8_t r = n1 * n2;
What do we know about the result, r? Answer, nothing. It can't be 16641 (the result of 129 * 129) as that is too big for the 8 bit integral type. Could it be 1 (16641 modulo 256)? Well, it could be but as the number overflowed we can't rely on anything about r.
Not only is the result undefined but we don't even know that the result overflowed and is undefined!
Solution
Can we do anything about it? Yes we can but suddenly everything is hard.
Essentially, we need to pre-test that the result will not overflow before we perform the multiplication. How can we do a pre-test without overflowing in the pre-test? Well, what we want of the pre-test is to answer the question: is the result of the multiplication going to be bigger than our maximum value, i.e. is n1 * n2 > UINT8_MAX true?
We can do some trivial rewrite of that (divide both sides by n2) to get the question: is n1 > UINT8_MAX / n2 true? Division doesn't overflow (other than if n2 is zero, of course) so now we have a "quick" test to see if the projected multiplication will overflow.
Integral division isn't very quick and so we're trading risky for slow (as we now have to do a division, a comparison and the multiplication as a minimum).
Carry
If you want to go ahead and multiply anyway to compute the carry then the StackExchange page lists a few variations on the theme: chop the arguments up into half-words (4 bits in our case!) but use full-word objects for them, perform long multiplication of the four (half-word) segments watching for overflow into the top half of the word and keeping track of the carry. Mash all the parts together at the end.
Easy!
Repercussions
Now we know what to do this means that every occurrence of integral multiplication in your code must be managed for the case where it could overflow the result type.
Groan!
Document Actions