Re: Fastest way to check for int32 overflows

[e]

I keep this CMU SEI bookmark 
_
 as a reference for whenever I need to deal with overflow in C... it's probably 
useful for safe cross platform Nim coding, too.

Re: Fastest way to check for int32 overflows

[Stefan_Salewski]

> 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.

Re: Fastest way to check for int32 overflows

[AmbrusFernas]

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.

Re: Fastest way to check for int32 overflows

[mratsim]

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](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")


Run

Re: Fastest way to check for int32 overflows

[Stefan_Salewski]

> 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?

[https://en.wikipedia.org/wiki/Saturation_arithmetic](https://en.wikipedia.org/wiki/Saturation_arithmetic)

Re: Fastest way to check for int32 overflows

[drkameleon]

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


Run

**Output:**


overflows!
did not overflow: 2147483647


Run

Fastest way to check for int32 overflows

[drkameleon]

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 = 0x7FFF

if a > MAX_INT-1:
# will overflow
else:
# will not overflow, proceed with the addition


Run

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?