# Where is std::num::Saturating? (Going to pre-RFC!) **URL:** \ **Category:** libs\ **Created:** [September 13, 2020, 7:50pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053 "2020-09-13T19:50:58Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![pdolezal](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pdolezal/32/7137_2.png) [@pdolezal](https://internals.rust-lang.org/u/pdolezal)\ **Post date:** [September 13, 2020, 7:50pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/1 "2020-09-13T19:50:58Z")
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)? ---
**Author:** ![josh](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/josh/32/5934_2.png) [@josh](https://internals.rust-lang.org/u/josh)\ **Post date:** [September 13, 2020, 8:02pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/2 "2020-09-13T20:02:43Z")
I'd also love to have a wrapper for panic-on-overflow behavior (even in release builds). ---
**Author:** ![Tom-Phinney](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tom-phinney/32/3299_2.png) [@Tom-Phinney](https://internals.rust-lang.org/u/Tom-Phinney)\ **Post date:** [September 13, 2020, 8:16pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/3 "2020-09-13T20:16:40Z")
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 `::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. ---
**Author:** ![bascule](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bascule/32/3057_2.png) [@bascule](https://internals.rust-lang.org/u/bascule)\ **Post date:** [September 13, 2020, 8:58pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/4 "2020-09-13T20:58:42Z")
> [@josh](#): > > I'd also love to have a wrapper for panic-on-overflow behavior (even in release builds). Yes yes yes! I know there's the [`checked` crate](https://docs.rs/checked/), 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). ---
**Author:** ![pdolezal](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pdolezal/32/7137_2.png) [@pdolezal](https://internals.rust-lang.org/u/pdolezal)\ **Post date:** [September 13, 2020, 9:19pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/5 "2020-09-13T21:19:43Z")
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? ---
**Author:** ![bascule](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bascule/32/3057_2.png) [@bascule](https://internals.rust-lang.org/u/bascule)\ **Post date:** [September 13, 2020, 10:12pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/6 "2020-09-13T22:12:19Z")
> [@pdolezal](#): > > So… it would be nice to have `Wrapping` , `Saturating` and `Checked` types, all with the same methods etc., right? Exactly. > [@](#): > > 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? 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. ---
**Author:** ![jstarks](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jstarks/32/6296_2.png) [@jstarks](https://internals.rust-lang.org/u/jstarks)\ **Post date:** [September 14, 2020, 2:20am UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/7 "2020-09-14T02:20:20Z")
Out of curiosity, where is checked arithmetic useful in crypto? ---
**Author:** ![mcy](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mcy/32/6512_2.png) [@mcy](https://internals.rust-lang.org/u/mcy)\ **Post date:** [September 14, 2020, 2:14pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/8 "2020-09-14T14:14:33Z")
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. ---
**Author:** ![bascule](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bascule/32/3057_2.png) [@bascule](https://internals.rust-lang.org/u/bascule)\ **Post date:** [September 14, 2020, 2:15pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/9 "2020-09-14T14:15:12Z")
> [@jstarks](#): > > Out of curiosity, where is checked arithmetic useful in crypto? 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). ---
**Author:** ![pdolezal](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pdolezal/32/7137_2.png) [@pdolezal](https://internals.rust-lang.org/u/pdolezal)\ **Post date:** [September 14, 2020, 3:52pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/10 "2020-09-14T15:52:52Z")
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? ---
**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\ **Post date:** [September 14, 2020, 5:50pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/11 "2020-09-14T17:50:47Z")
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](https://github.com/rust-lang/rfcs/pull/2417#issuecomment-386537396) ---
**Author:** ![mcy](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mcy/32/6512_2.png) [@mcy](https://internals.rust-lang.org/u/mcy)\ **Post date:** [September 14, 2020, 6:15pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/12 "2020-09-14T18:15:55Z")
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.) ---
**Author:** ![Tom-Phinney](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tom-phinney/32/3299_2.png) [@Tom-Phinney](https://internals.rust-lang.org/u/Tom-Phinney)\ **Post date:** [September 14, 2020, 6:51pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/13 "2020-09-14T18:51:51Z")
> [@mcy](#): > > 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 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. ---
**Author:** ![mbrubeck](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mbrubeck/32/174_2.png) [@mbrubeck](https://internals.rust-lang.org/u/mbrubeck)\ **Post date:** [September 14, 2020, 6:54pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/14 "2020-09-14T18:54:16Z")
We currently have `overflowing_add` and `overflowing_sub` for access to the carry bit. See this thread for related discussion: > [@Adding access to the carry flag bit](https://internals.rust-lang.org/t/adding-access-to-the-carry-flag-bit/12854): > > I've often lamented that most compilers do not expose the carry bit, detecting overflow/underflow and rotate through carry instructions... I think that the performance of numerous programs can be significantly enhanced by the addition of instructions that operate on the carry flag. The tricky bit... The actual condition is easy, but for anyone not familiar with most cpu implementations, the carry flag is a flag set only by various instructions, usually, add, sub, cmp, rcr/rcl (rotate right/… ---
**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\ **Post date:** [September 14, 2020, 7:19pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/15 "2020-09-14T19:19:51Z")
> [@mbrubeck](#): > > We currently have `overflowing_add` and `overflowing_sub` for access to the carry bit. And I was pleased to see that chaining those into a full-adder appears to actually work: [Compiler Explorer](https://rust.godbolt.org/z/cbr91q) (Chaining `overflowing_mul`, however, sadly doesn't because it only give a bit of overflow, not the full carry-out.) ---
**Author:** ![mcy](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mcy/32/6512_2.png) [@mcy](https://internals.rust-lang.org/u/mcy)\ **Post date:** [September 14, 2020, 8:39pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/16 "2020-09-14T20:39:56Z")
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). ---
**Author:** ![bascule](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bascule/32/3057_2.png) [@bascule](https://internals.rust-lang.org/u/bascule)\ **Post date:** [September 14, 2020, 9:29pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/17 "2020-09-14T21:29:27Z")
Here's the technique used by several Rust ECC libraries for implementing add-with-carry: > ---
**Author:** ![newpavlov](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/newpavlov/32/3290_2.png) [@newpavlov](https://internals.rust-lang.org/u/newpavlov)\ **Post date:** [September 14, 2020, 9:40pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/18 "2020-09-14T21:40:59Z")
> [@scottmcm](#): > > And I was pleased to see that chaining those into a full-adder appears to actually work: [https://rust.godbolt.org/z/cbr91q](https://rust.godbolt.org/z/cbr91q) 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](https://rust.godbolt.org/z/GcsK47) or [Compiler Explorer](https://rust.godbolt.org/z/jfhhMY) All my attempts have ended in compiler either inserting branches or generating inefficient code. ---
**Author:** ![bascule](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bascule/32/3057_2.png) [@bascule](https://internals.rust-lang.org/u/bascule)\ **Post date:** [September 14, 2020, 10:17pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/19 "2020-09-14T22:17:50Z")
@newpavlov here's an example of an `adc` wrapper using `overflowing_add`: ```rust #[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: > **[Compiler Explorer - Rust (rustc 1.45.2)](https://godbolt.org/z/E94EE5)** > > /// Computes a + b + carry, returning the result along with the new carry. > \#\[inline\] > 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... ```x86asm 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. ---
**Author:** ![newpavlov](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/newpavlov/32/3290_2.png) [@newpavlov](https://internals.rust-lang.org/u/newpavlov)\ **Post date:** [September 14, 2020, 10:24pm UTC](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053/20 "2020-09-14T22:24:16Z")
Ah, good to know! Indeed it works as desired: [https://rust.godbolt.org/z/n65abs](https://rust.godbolt.org/z/n65abs) [https://rust.godbolt.org/z/54dvor](https://rust.godbolt.org/z/54dvor) (looks like I was missing the `bool as u8` trick). [Next page](https://internals.rust-lang.org/t/where-is-std-saturating-going-to-pre-rfc/13053.md?page=2)