Basically, I want to predict when the result of an operation between 2 int32's will overflow (addition, multiplication, exponentation).
Up to now, I was to doing it by catching overflow exceptions, but exceptions are quite expensive.
Now, I'm trying checking it like this (for addition):
const MAX_INT = 0x7FFFFFFF
if a > MAX_INT-1:
# will overflow
else:
# will not overflow, proceed with the addition
I've also seen the __builtin_add_overflow commands (available for both Clang and GCC) and I'm wondering how I could use them.
Any recommendations?
I want to predict when the result
I think predict is only possible in rare cases.
Why not use saturated arithmetic to detect overflow after it has occurred?
Answering my own question:
proc int32AddOverflow(a, b: int32, c: var int32): bool {.
importc: "__builtin_sadd_overflow", nodecl, nosideeffect.}
var rez: int32
if int32AddOverflow(int32(2147483647),int32(1),rez):
echo "overflows!"
else:
echo rez
if int32AddOverflow(int32(2147483646),int32(1),rez):
echo "overflows!"
else:
echo "did not overflow: ", rez
Output:
overflows!
did not overflow: 2147483647
Unfortunately overflows and carry flags are where the "C is a portable assembly" narratives die ...
You can't access those flags even though they would be incredibly useful for cryptography and interpreters. Sometimes you can trick the compiler to generate the proper code but other times you get silly code that sets flag explicitly instead of reusing the result of the previous operation.
Anyway, this is what I use to be portable for my bigint library, obviously the builtins are better but I'm not sure MSVC also provides some and they don't work anyway for uint256+:
https://github.com/status-im/nim-stint/blob/master/stint/private/int_addsub.nim
func `+`*(x, y: IntImpl): IntImpl {.inline.}=
# Addition for multi-precision signed int.
type SubTy = type x.hi
result.lo = x.lo + y.lo
result.hi = (result.lo < y.lo).toSubtype(SubTy) + x.hi + y.hi
when compileOption("boundChecks"):
if unlikely(
not(result.isNegative xor x.isNegative) or
not(result.isNegative xor y.isNegative)
):
return
raise newException(OverflowError, "Addition overflow")
func `-`*(x, y: IntImpl): IntImpl {.inline.}=
# Substraction for multi-precision signed int.
type SubTy = type x.hi
result.lo = x.lo - y.lo
result.hi = x.hi - y.hi - (x.lo < y.lo).toSubtype(SubTy)
when compileOption("boundChecks"):
if unlikely(
not(result.isNegative xor x.isNegative) or
not(result.isNegative xor y.isNegative.not)
):
return
raise newException(OverflowError, "Substraction underflow")
I tried searching it but I couldn’t find anything, could have been me not using the right words though 😕
Anyway, why are i32 integers the fastest when performing calculations? I think this is the case for C/C++ too so I’m assuming it’s an architectural thing.
Anyway, why are i32 integers the fastest when performing calculations?
Some CPU may have no 64 bit data type at all, like some ARM and embedded chips. So for int64 addition we would get two operations at least, one plain addition and one add with carry. Even for a CPU with 64 bit support a multiplication will result in a 128 bit result which may be not a native type.
And finally, even when the 64 bit type is fully supported, you have to regard memory bandwidth and cache size. There can be twice as much int32 in cache as int64.
For smaller types than native word size, like int16 or int8 there may exists CPUs which first have to extent the size to native word size like 32 or 64 bit, and then do the math. I think for x86 CPU that is not true.
For float types -- well when there is a FPU add and mul can be fast too, division is generally not that fast and has latency.