How to detect integer overflow efficiently?

Learning
1

In OCaml, unlike Standard ML, integer overflow is not detected automatically. If I want to detect it (for security purposes, say), is there any efficient way to do it? Browsing old posts I found mention of add_with_overflow, but I can’t find any evidence that that still exists, if it ever did.

I don’t want to use Zarith because in normal use my numbers are quite small.

2

In OCaml/C code there is ocaml/runtime/caml/misc.h at c94d12ceed5dcff771577423b621799fa3cff928 · ocaml/ocaml · GitHub

1 Like
3

Or use zarith because
small integers are represented as unboxed Caml integers, to save space and improve performance

1 Like
4

It is a pity, in assembler language, it would cost a single instruction to detect an overflow (jc or something like this)… surely many more to raise the exception… but it wont hurt most of the processes.

5

It depends on how efficient you need it to be. An easy way is to do the operation in a wider type (eg int64) and then check whether the result is within the expected bounds (such local use of int64 does not result in any allocation):

let add_with_overflow a b =
  let a = Int64.of_int a and b = Int64.of_int b in
  let r = Int64.add a b in
  if r > Int64.of_int max_int || r < Int64.of_int min_int then
    failwith "overflow";
  Int64.to_int r

Cheers,
Nicolas

1 Like
6

People who read this thread may be interested in a technical report from Daan Leijen, https://www.microsoft.com/en-us/research/uploads/prod/2022/07/int.pdf , that was presented at the ML workshop in 2022. The topic of the report is not just “how to detect overflow”, but how to implement arbitrary-size integers efficiently. For example, addition has to detect whether the sum overflows but also if one of the two inputs is in fact a large integer rather than a machine integer.

The conclusion is that this remains noticeably costly on most architectures – the author suggests that this could be better supported by the hardware.

1 Like
7

Thanks! How would I go about interfacing with this? The usual process for interfacing with C functions doesn’t seem to cover passing results by reference.

8

Since I would be doing this in the inner loop, I was really hoping the solution would not cost more than one or two instructions in the normal case.

9

The Euler package (opam - euler) provides integer arithmetic operations with overflow detection. This said, I’d rather use arbitrary-precision integers with the ZArith package (opam - zarith) : it’s pretty fast for small integers, and gives exact results when integers overflow, which is more useful than raising an exception.

5 Likes
10

That’s helpful, thank you. In my application the numbers are deBruijn indices. They are nearly always less than 100, and they will only overflow in the case of malicious code, in which case I’ll simply abort.

11

If your application is De Bruijn indices, then the only operation you are interested in is presumably nonnegative addition, so this can be cheaply tested:

let add x y =
  assert (0 <= y);
  let r = x + y in
  if r < x then raise Overflow;
  r
2 Likes
12

Is it exposed w/ an OCaml interface somewhere?

13

See @xavierleroy 's answer above. (Would be good to mark that as this question’s answer)

1 Like
14

For what it’s worth, @xavierleroy’s answer gave me what I need, but a little indirectly. The key device is the @inline directive that the Euler package uses. I think I can get what I need by attaching that to code similar to @silene’s.