Item — HN Reader

I posted overflow checking of signed integer arithmetic as a puzzle yesterday[1]. I got some good responses but none quite as minimal wrt number of instructions as my own solution:

    bool add_will_overflow(int32_t a, int32_t b) {
        uint32_t c = (uint32_t)a + (uint32_t)b;
        return (((uint32_t)a ^ c) & ((uint32_t)b ^ c)) >> 31;
    }

That produces the following assembly (see Godbolt[2]):

        lea     edx, [rdi+rsi]
        mov     eax, edi
        xor     eax, edx
        xor     esi, edx
        and     eax, esi
        shr     eax, 31
        ret

In Rust, you can write a.checked_add(b).is_none() which produces the following assembly[3]:

        add     edi, esi
        seto    al
        ret

A fun fact about this code: the overflow flag which is set by the add instruction and then harvested dates back at least to the 8080 (almost 50 years ago) and is not present in vanilla ARM. However, Apple Silicon has it as an extension, to make life easier for Rosetta 2 binary translation[4]. So when you do get to use this shorter code sequence, be thankful of the effort that chip designers put in to make it execute efficiently.

I expect the C23 built-in functions will perform as well as Rust here, which is a win both for ergonomics (you can't really consider the current state of "will a+b overflow" to be discoverable) and performance.

[1]: https://mastodon.online/@raph/109535617953722719

[2]: https://godbolt.org/z/17zMsWjYv

[3]: https://rust.godbolt.org/z/36Ta9oP1P

[4]: https://news.ycombinator.com/item?id=33635720

6 comments

Checked overflow operations are kind of the goto operation for "it's easy in assembly, hard in programming languages"--in hardware terms, it's usually check a flag, but since flag registers are not provided for in high-level languages, it becomes a game of try to write it in a pattern that the compiler can recognize, which is never a fun game to play. Even worse than addition is multiplication. Thankfully, C23 has finally added these operations.

Although, recently, I noticed I wanted a case where I wanted checked (u32 - u32) -> i32 and (u32 + i32) -> u32 operations, which even Rust's standard library doesn't provide. (The use case is keeping track of a running delta between two lists of u32 values--the delta can go positive or negative, so it has to be signed, but the values in the lists can never be negative).

> it becomes a game of try to write it in a pattern that the compiler can recognize

Worse, in C or C++ you also need to find a way to do it without undefined behaviour. You can't just do the operation and see if the result matches expectations…

The addition operator just landed in Rust 1.66 (checked_add_signed[1]), but the subtraction one it looks like you'd need to roll your own.

[1]: https://github.com/rust-lang/rust/issues/87840

You are probably looking at it wrong. You can now write

  i32::checked_add_unsigned(some_u32)  and

  i32::checked_sub_unsigned(some_u32)

... which I think are exactly what your parent needs.

u32::checked_add_signed solves one of the pairs (u32 + i32 -> u32), but there's nothing for the other one (u32 - u32 -> i32).

Good point, I'm sure this made sense to me when I wrote it, but I can't ask past me why.

C is supposed to be reasonably portable so it doesn’t make too much sense to depend on flags that are not available on all platforms.

Why can’t it be a flag on some platforms and complex hereafter branching logic on other platforms? Like the division shim on platforms that don’t have a division instruction?

It's easier to find a platform that doesn't support floating-point numbers than one that doesn't have some kind of overflow flag. Some kind of platform-independent abstraction is long (as in, decades) overdue.

Sure, but it kind of is insane that there are platforms (like ARM apparently, did not know) that do NOT have a carry flag.

This is already present as a builtin in in GNU C (as indicated in TFA) and it already results in the optimal code: https://godbolt.org/z/qc4zvav7E

"__builtin_add_overflow" in gcc produces the same output as "checked_add()".

I really hope stuff like this is added to the standard.

Hmm, isn't the Apple-specific magic only for parity(PF) and aux carry (AF)? aarch64 does have a 'V' flag for signed overflow.

Oops, you're right. Too late to edit, sorry about the confusion.

How does it actually perform? by default I generally assume flags registers are kinda dicey for performance due to the dependency.

Also, Hacker's Delight and OpenBSD probably have clever solutions for these.

Surprisingly, OpenBSD does not have a library (neither a public API nor even just routines which are copied project-to-project as is common with OpenBSD utilities and daemons) to handle arithmetic overflow. The closest might be malloc/realloc extensions, like reallocarray, that handle common scenarios where arithmetic overflow is seen.