rust signed difference of unsigned integers

Question

I know that rust has mixed integer operations, but I can't find a straightforward way to get a signed difference of two unsigned integers, while correctly handling overflow:

// one or both values may be too large to just cast to isize
let x: usize = (isize::MAX as usize) + 5;
let y: usize = (isize::MAX as usize) + 7;
let d: isize = x.signed_saturating_sub(y); // non-existent method
assert_eq!(d, -2);

I could try to implement it in terms of casts, but I'm not sure how to correctly detect overflow:

trait SignedSub {
    type Signed;
    fn signed_overflowing_sub(self, rhs: Self) -> (Self::Signed, bool);
    fn signed_wrapping_sub(self, rhs: Self) -> Self::Signed;
    fn signed_saturating_sub(self, rhs: Self) -> Self::Signed;
    fn signed_checked_sub(self, rhs: Self) -> Option<Self::Signed>;
}
impl SignedSub for usize {
    type Signed = isize;

    fn signed_overflowing_sub(self, rhs: Self) -> (Self::Signed, bool) {
        let (abs, neg) = if self < rhs {
            (rhs - self, true)
        } else {
            (self - rhs, false)
        };
        let abs = abs as isize;
        let res = match neg {
            true => -abs,
            false => abs,
        };
        (res, todo!("how to tell if it overflowed isize?"))
    }

    fn signed_wrapping_sub(self, rhs: Self) -> Self::Signed {
        self.signed_overflowing_sub(rhs).0
    }

    fn signed_saturating_sub(self, rhs: Self) -> Self::Signed {
        let (r, overflowed) = self.signed_overflowing_sub(rhs);
        match overflowed {
            true => match self.cmp(&rhs) {
                Ordering::Less => isize::MIN,
                Ordering::Equal => unreachable!(),
                Ordering::Greater => isize::MAX,
            },
            false => r,
        }
    }

    fn signed_checked_sub(self, rhs: Self) -> Option<Self::Signed> {
        let (r, overflowed) = self.signed_overflowing_sub(rhs);
        match overflowed {
            true => None,
            false => Some(r),
        }
    }
}

#[cfg(test)]
mod test {
    use super::SignedSub;
    use proptest::prelude::*;

    proptest! {
        #[test]
        fn it_works(a: usize, b: isize) {
            // a + b = c
            // a + b - a = c - a
            // b = c - a
            let (c,flag) = a.overflowing_add_signed(b);
            let (b2, flag2) = c.signed_overflowing_sub(a);
            // the flags should be the same
            assert_eq!((b, flag), (b2, flag2));
        }
    }
}

as shown in the test above, it's conceptually an inverse of the uX::overflowing_add_signed(iX) method, and it overflows in the same circumstances.

Answer 1

You can also build this out of usize::overflowing_sub:

fn signed_overflowing_sub(self, rhs: Self) -> (Self::Signed, bool) {
    let (res, overflowed) = self.overflowing_sub(rhs);
    let res = res as Self::Signed;
    (res, overflowed ^ (res < 0))
}

• If the subtraction doesn’t overflow usize, the result is positive, and overflows isize exactly when it’s over isize::MAX, which is equivalent to being negative when cast to isize.

• If the subtraction does overflow usize, the result is negative, and overflows isize exactly when it’s under isize::MIN, which is equivalent to being positive when cast to isize.

Correctness proof on u8/i8

Answer 2

The semantics are tricky to get right, but here's what I think is a correct version:

fn signed_overflowing_sub(self, rhs: Self) -> (Self::Signed, bool) {
    if self < rhs {
        let result = rhs - self;
        if result == 1 << (usize::BITS - 1) /* -isize::MIN */ {
            // `-isize::MIN` will overflow if we convert to it `isize`, so we need to handle it specifically.
            (isize::MIN, false)
        } else {
            (-(result as isize), result > isize::MAX as usize)
        }
    } else {
        let result = self - rhs;
        (result as isize, result > isize::MAX as usize)
    }
}

Answer 3

Here's a very simple always-correct version, that assumes that usize is no more than 64 bits (currently true on all supported platforms):

fn signed_overflowing_sub(self, rhs: Self) -> (Self::Signed, bool) {
    let result = i128::try_from(self).expect("i128 too small")
        - i128::try_from(rhs).expect("i128 too small");
    (result as isize, isize::try_from(result).is_err())
}

I'm not even sure it will be less efficient than manual checks, it might as well be more efficient.

Answer 4

By inspecting the code for the std lib implementations of the related operations, I've sort of stumbled upon a fairly minimal implementation in terms of a helper trait:

trait Cast {
    type OtherSign: Cast<OtherSign = Self>;
    fn overflowing_cast(self) -> (Self::OtherSign, bool);
}

impl Cast for isize {
    type OtherSign = usize;

    fn overflowing_cast(self) -> (Self::OtherSign, bool) {
        (0 as Self::OtherSign).overflowing_add_signed(self)
    }
}
impl Cast for usize {
    type OtherSign = isize;

    fn overflowing_cast(self) -> (Self::OtherSign, bool) {
        (0 as Self::OtherSign).overflowing_add_unsigned(self)
    }
}

impl SignedSub for usize {
    fn signed_overflowing_sub(self, rhs: Self) -> (Self::Signed, bool) {
        let (res, overflowed) = self.wrapping_sub(rhs).overflowing_cast();
        (res, overflowed ^ (self < rhs))
    }
    ...
}

This passes the test, but the downside is that I'm less clear on why it works.