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

While std::num::Wrapping exists, I wonder where std::num::Saturating is. Are there any plans for it (it seems it is quite a long time since Wrapping was added)?

6 Likes

I'd also love to have a wrapper for panic-on-overflow behavior (even in release builds).

7 Likes

As far as I can tell, it doesn't exist. I did look into this when I first came to Rust almost 3 years ago. IIRC, I concluded that it would be easy to create <crate>::Saturating using std::num::Wrapping as a guide. However, my interest was in modular arithmetic for crypto using uN, and thus Wrapping, so I did not explore the Saturating possibility any further.

Yes yes yes! I know there's the checked crate, but checked arithmetic is essential for secure implementations of many types of cryptography (or at least, ones which panic when buggy as opposed to being silently insecure).

So… it would be nice to have Wrapping, Saturating and Checked types, all with the same methods etc., right?

When considering Wrapping as the template for the other hypothetical types, is there anything that you don't like or you see it could be improved according to your experience?

3 Likes

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