6 ms·
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
by raphlinus 4y ago
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 https://mastodon.online/@raph/109535617953722719
[2]: https://godbolt.org/z/17zMsWjYv https://godbolt.org/z/17zMsWjYv
[3]: https://rust.godbolt.org/z/36Ta9oP1P https://rust.godbolt.org/z/36Ta9oP1P
[4]: https://news.ycombinator.com/item?id=33635720 https://news.ycombinator.com/item?id=33635720
- dooglius 4y agoThis 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 https://godbolt.org/z/qc4zvav7E
- tinglymintyfrsh 4y agoAlso, Hacker's Delight and OpenBSD probably have clever solutions for these.
- wahern 4y agoSurprisingly, 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.
- dezgeg 4y agoHmm, isn't the Apple-specific magic only for parity(PF) and aux carry (AF)? aarch64 does have a 'V' flag for signed overflow.
- raphlinus 4y agoOops, you're right. Too late to edit, sorry about the confusion.
- jcranmer 4y agoChecked 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).
- raphlinus 4y agoThe 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 https://github.com/rust-lang/rust/issues/87840
- tialaramex 4y agoYou 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.
- jcranmer 4y agou32::checked_add_signed solves one of the pairs (u32 + i32 -> u32), but there's nothing for the other one (u32 - u32 -> i32).
- tialaramex 4y agoGood point, I'm sure this made sense to me when I wrote it, but I can't ask past me why.
- 4y ago
- rightbyte 4y ago"__builtin_add_overflow" in gcc produces the same output as "checked_add()". I really hope stuff like this is added to the standard.
- nullc 4y agoHow does it actually perform? by default I generally assume flags registers are kinda dicey for performance due to the dependency.