Exactly.
Nope. Cryptography needs both wrapping and checked arithmetic, and I use the hell out of Wrapping
, but also really, really wish it had a Checked
equivalent.
Exactly.
Nope. Cryptography needs both wrapping and checked arithmetic, and I use the hell out of Wrapping
, but also really, really wish it had a Checked
equivalent.
Out of curiosity, where is checked arithmetic useful in crypto?
I'm not sure where checked (panic-on-overflow) is useful, but wrap-with-carry-bit is incredibly useful, since you can use it to implement things like branchless absolute value and constant-time modular arithmetic (and, by extension, Montgomery multiplication). Panic-on-overflow is a special case of this primitive, though the panic part requires a branch.
One of the main ones is counters, e.g. an incrementing counter in a nonce (often a 32-bit one). If these counters ever were to overflow back to 0 and nothing else caught that, it'd result in nonce reuse, and with it often a breakage of confidentiality (and in some algorithms, key recovery).
I guess it would be useful for implementing big integer libraries too. And I guess as well that it would be nice to have some type like WrappingCarry
, which would encapsulate wrapping-with-carry operations, while it could be implemented with compiler intrinsics and therefore highly optimized. Am I right?
I would love to have mul_with_carry
and friends in the library. They're not strictly necessary -- LLVM doesn't have instructions for these, they're just patterns on using wider types -- but I think having a canonical way would be nonetheless good.
RFC: https://github.com/rust-lang/rfcs/pull/2417#issuecomment-386537396
I don't know that I'd call that mul_with_carry
personally... though it would be nice to have add_with_carry
and sub_with_borrow
, at least to access adc
and sbb
in a cross-platform way...
(I'm of half a mind that core
should have as many dumb tricks from the first few chapters of Hacker's Delight in it as possible, e.g. a function that's just 0.wrapping_sub(my_bool as _)
, but that's just me.)
Of course those instructions are platform-specific; they (or equivalents) do not exist on all platforms. For example, RISC-V does not have such instructions, though it can implement a widening-mul as referenced in the prior post.
We currently have overflowing_add
and overflowing_sub
for access to the carry bit. See this thread for related discussion:
And I was pleased to see that chaining those into a full-adder appears to actually work: Compiler Explorer
(Chaining overflowing_mul
, however, sadly doesn't because it only give a bit of overflow, not the full carry-out.)
Well, yeah, on RV I expect that to get lowered into a bunch of sltu
instructions. I'm just saying that it would be nice to be able to do a full adder without having to think about it. (For reference, I work in an rv32imcb environment, so I don't actually care about adc
personally.)
Though it is nice that LLVM is able to optimize it correctly, so I guess it's not a terrible loss. (Looks like it produces the appropriate mess of sltu
instructions there, too).
Here's the technique used by several Rust ECC libraries for implementing add-with-carry:
Unfortunately, it's not really sufficient for long arithmetics, especially if you want to enforce const time. For example, try to get a similar assembly output using overflowing_add
: Compiler Explorer or Compiler Explorer
All my attempts have ended in compiler either inserting branches or generating inefficient code.
@newpavlov here's an example of an adc
wrapper using overflowing_add
:
#[inline(always)]
pub const fn adc(a: u64, b: u64, carry: u64) -> (u64, u64) {
let (c, overflow1) = a.overflowing_add(b);
let (ret, overflow2) = c.overflowing_add(carry as u64);
(ret, (overflow1 | overflow2) as u64)
}
...which looks similar to the above example I just gave, although IMO slightly more convoluted.
It results in the following generated assembly in the context of a carry chain:
mov rax, rdi
mov r8, qword ptr [rsi]
add r8, qword ptr [rdx]
mov rdi, qword ptr [rsi + 8]
adc rdi, qword ptr [rdx + 8]
mov rcx, qword ptr [rsi + 16]
adc rcx, qword ptr [rdx + 16]
mov rdx, qword ptr [rdx + 24]
adc rdx, qword ptr [rsi + 24]
mov qword ptr [rax], r8
mov qword ptr [rax + 8], rdi
mov qword ptr [rax + 16], rcx
mov qword ptr [rax + 24], rdx
ret
This assembly is practically identical to the same assembly generated using a carry chain implemented using the previous adc64
example I gave.
Ah, good to know! Indeed it works as desired: https://rust.godbolt.org/z/n65abs https://rust.godbolt.org/z/54dvor (looks like I was missing the bool as u8
trick).
Or completely identical, using the add_with_carry_using_overflowing
from my previous godbolt: Compiler Explorer
Note that this version produces some fairly garbage assembly for the adc()
function in -Oz; you should use a bool for the carry like @scottmcm did. (See also why I really think this should be an intrinsic...). https://godbolt.org/z/WoWKK1
(In -Oz rustc fails to inline any of these for whatever reason, though that's not included in the example.)
Alright, so if I didn't miss it, there should be all the methods for all the cases – checked, wrapping and overflow –, but so far only Wrapping
exists and the two remaining cases could be possibly added to make this corner of std::num
complete. And it seems there are good uses for it.
I think it is worth making an RFC, isn't it?
While for unsigned integers those give access to the carry flag, for signed integers they give access to the overflow flag. So for example to access the carry bit in i64 addition, you'd need to first cast the integers to u64, then use overflowing_add, and then cast the sum back to i64.
there is an RFC for this (widening_mul
) widening_mul by strake · Pull Request #2417 · rust-lang/rfcs · GitHub.