Where is std::num::Saturating? (Going to pre-RFC!)

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

3 Likes

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

1 Like

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:

2 Likes

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

3 Likes

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.

2 Likes

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

1 Like

Or completely identical, using the add_with_carry_using_overflowing from my previous godbolt: Compiler Explorer

1 Like

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.

2 Likes

there is an RFC for this (widening_mul) widening_mul by strake · Pull Request #2417 · rust-lang/rfcs · GitHub.