Re: Detect overflow by reading ALU's carryout
On Mar 14, 1:07 pm, Jorgen Grahn <grahn+n...@snipabacken.se> wrote:
On Sun, 2010-03-14, Nando wrote:
Hi all! I'm writing a piece of code that will cycle
thousands of thousands of times. Within the cycle I perform
an addition of two unsigned ints. I need to be able to read
the carryout bit (signal or flag) from the CPU/ALU. I cannot
use another math operation just to detect if there was an
overflow, because timing for this algorithm is very
important.
And you have verified that if you write it in a
straight-forward way, (a) the compiler doesn't optimize it to
perfection and (b) it *does* take unacceptable long time?
But I'm not actually sure what the straightforward test would
be.
The "straightforward" solution involves using smaller types as
input, and testing whether the results are larger than the max
of the smaller type. If you're doing multidigit arithmetic, it
means doubling the number of times you loop for addition (and
multiplying it by 4 for multiplication).
It would be an interesting exercise. And you're right, if you
know assembly it's annoying, because you know the information
*is* there. (At least on the CPUs I know.)
I've yet to see a CPU without it, and I've seen quite a few.
Doing multiple precision multiplication is even more
frustrating, because most (but not all) machines have a
multiplication instruction which returns a result in two
registers. But C++ (and every other language I've used)
promptly throw away the high order word.
std::pair<unsigned, bool>
add_with_overflows(unsigned a, unsigned b)
{
// ???
// Supposing unsigned long long is larger than unsigned...
unsigned long long r = (unsigned long long)a + b;
std::pair<unsigned, bool> result;
result.first = r;
result.second = r > std::numeric_limits<unsigned>::max();
return result;
}
This is certainly the most effective way on any 64 bit machine.
On a 32 bit machine, with 32 bit ints and longs, there's a clear
risk that the compiler will generate 64 bit operations, using
several machine instructions.
--
James Kanze