Skip to content

std::wrapping_mul return incorrect values for u128 arguments #7528

Closed
@TomAFrench

Description

@TomAFrench

Noticed this while removing the U128 struct and porting this test over:

#[test]
fn test_wrapping_mul() {
// 1*0==0
assert_eq(U128::zero(), U128::zero().wrapping_mul(U128::one()));
// 0*1==0
assert_eq(U128::zero(), U128::one().wrapping_mul(U128::zero()));
// 1*1==1
assert_eq(U128::one(), U128::one().wrapping_mul(U128::one()));
// 0 * ( 1 << 64 ) == 0
assert_eq(U128::zero(), U128::zero().wrapping_mul(U128::from_u64s_le(0, 1)));
// ( 1 << 64 ) * 0 == 0
assert_eq(U128::zero(), U128::from_u64s_le(0, 1).wrapping_mul(U128::zero()));
// 1 * ( 1 << 64 ) == 1 << 64
assert_eq(U128::from_u64s_le(0, 1), U128::from_u64s_le(0, 1).wrapping_mul(U128::one()));
// ( 1 << 64 ) * 1 == 1 << 64
assert_eq(U128::from_u64s_le(0, 1), U128::one().wrapping_mul(U128::from_u64s_le(0, 1)));
// ( 1 << 64 ) * ( 1 << 64 ) == 1 << 64
assert_eq(U128::zero(), U128::from_u64s_le(0, 1).wrapping_mul(U128::from_u64s_le(0, 1)));
// -1 * -1 == 1
assert_eq(
U128::one(),
U128::from_u64s_le(0xffffffffffffffff, 0xffffffffffffffff).wrapping_mul(
U128::from_u64s_le(0xffffffffffffffff, 0xffffffffffffffff),
),
);
}

    #[test]
    fn test_wrapping_mul() {
        let zero: u128 = 0;
        let one: u128 = 1;
        let two_pow_64: u128 = 0x10000000000000000;
        let u128_max: u128 = 0xffffffffffffffffffffffffffffffff;

        // 1*0==0
        assert_eq(zero, wrapping_mul(zero, one));

        // 0*1==0
        assert_eq(zero, wrapping_mul(one, zero));

        // 1*1==1
        assert_eq(one, wrapping_mul(one, one));

        // 0 * ( 1 << 64 ) ==  0
        assert_eq(zero, wrapping_mul(zero, two_pow_64));

        // ( 1 << 64 ) * 0 == 0
        assert_eq(zero, wrapping_mul(two_pow_64, zero));

        // 1 * ( 1 << 64 ) == 1 << 64
        assert_eq(two_pow_64, wrapping_mul(two_pow_64, one));

        // ( 1 << 64 ) * 1 == 1 << 64
        assert_eq(two_pow_64, wrapping_mul(one, two_pow_64));

        // ( 1 << 64 ) * ( 1 << 64 ) == 1 << 64
        assert_eq(zero, wrapping_mul(two_pow_64, two_pow_64));
        // -1 * -1 == 1
        assert_eq(one, wrapping_mul(u128_max, u128_max));
    }

This test now fails which is pretty clear from the implementation of wrapping_mul as it discounts the potential for the multiplication to overflow the field modulus

pub fn wrapping_mul<T>(x: T, y: T) -> T
where
    T: AsPrimitive<Field>,
    Field: AsPrimitive<T>,
{
    AsPrimitive::as_(x.as_() * y.as_())
}

wrapping_add and wrapping_sub seem to be ok however. There's potential for the magic constant in wrapping_sub being an issue but it seems fine to me.

pub fn wrapping_sub<T>(x: T, y: T) -> T
where
    T: AsPrimitive<Field>,
    Field: AsPrimitive<T>,
{
    //340282366920938463463374607431768211456 is 2^128, it is used to avoid underflow
    AsPrimitive::as_(x.as_() + 340282366920938463463374607431768211456 - y.as_())
}

Metadata

Metadata

Assignees

Labels

bugSomething isn't working

Type

No type

Projects

Status

✅ Done

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions