Last active
September 9, 2025 01:27
-
-
Save michaelficarra/e59bec9a83983d31f4df81350b4f7782 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #[derive(Debug, PartialEq, Eq)] | |
| enum ArithmeticResult { | |
| Overflow, | |
| Underflow, | |
| Accurate, | |
| } | |
| fn oracle(a: i64, b: i64) -> ArithmeticResult { | |
| let a128 = i128::from(a); | |
| let b128 = i128::from(b); | |
| let real_product = a128 * b128; | |
| if real_product > i128::from(i64::MAX) { | |
| ArithmeticResult::Overflow | |
| } else if real_product < i128::from(i64::MIN) { | |
| ArithmeticResult::Underflow | |
| } else { | |
| ArithmeticResult::Accurate | |
| } | |
| } | |
| fn detect_i64_product_overflow(a: i64, b: i64) -> ArithmeticResult { | |
| let a_negative = a < 0; | |
| let b_negative = b < 0; | |
| let a_low: u64 = a.cast_unsigned() & 0xFFFFFFFF; | |
| let a_high: u64 = a.cast_unsigned() >> 32; | |
| let b_low: u64 = b.cast_unsigned() & 0xFFFFFFFF; | |
| let b_high: u64 = b.cast_unsigned() >> 32; | |
| let low_low: u64 = a_low.wrapping_mul(b_low); | |
| let low_high: u64 = a_low.wrapping_mul(b_high); | |
| let high_low: u64 = a_high.wrapping_mul(b_low); | |
| let carry: u64 = (low_low >> 32).wrapping_add(low_high & 0xFFFFFFFF).wrapping_add(high_low & 0xFFFFFFFF) >> 32; | |
| let low: u64 = low_low.wrapping_add(low_high << 32).wrapping_add(high_low << 32); | |
| let high: u64 = a_high.wrapping_mul(b_high).wrapping_add(low_high >> 32).wrapping_add(high_low >> 32).wrapping_add(carry); | |
| let mut high: i64 = high.cast_signed(); | |
| if a_negative { | |
| high = high.wrapping_sub(b); | |
| } | |
| if b_negative { | |
| high = high.wrapping_sub(a); | |
| } | |
| if !(high == 0 && low <= i64::MAX.cast_unsigned() || high == -1 && low > i64::MAX.cast_unsigned()) { | |
| if a_negative != b_negative { | |
| return ArithmeticResult::Underflow; | |
| } | |
| return ArithmeticResult::Overflow; | |
| } | |
| ArithmeticResult::Accurate | |
| } | |
| #[test] | |
| fn test_overflow_detection() { | |
| let mut v = IndexSet::from([ | |
| 123, | |
| 456, | |
| 123456, | |
| 1234567890, | |
| i64::MAX, | |
| i64::MIN, | |
| i64::MAX - 1, | |
| i64::MIN + 1, | |
| (i64::MAX / 2) - 1, | |
| i64::MAX / 2, | |
| (i64::MAX / 2) + 1, | |
| (i64::MIN / 2) - 1, | |
| i64::MIN / 2, | |
| (i64::MIN / 2) + 1, | |
| ]); | |
| for p in 0..=62 { | |
| v.insert(2i64.pow(p) - 1); | |
| v.insert(-(2i64.pow(p) - 1)); | |
| v.insert(2i64.pow(p)); | |
| v.insert(-(2i64.pow(p))); | |
| v.insert(2i64.pow(p) + 1); | |
| v.insert(-(2i64.pow(p) + 1)); | |
| } | |
| for p in 0..=18 { | |
| for c in 1..=9 { | |
| v.insert(c * 10i64.pow(p)); | |
| v.insert(c * -(10i64.pow(p))); | |
| } | |
| } | |
| eprintln!("running {} test cases", v.len().pow(2)); | |
| for i in &v { | |
| for j in &v { | |
| let oracle_result = oracle(*i, *j); | |
| let your_result = detect_i64_product_overflow(*i, *j); | |
| assert!( | |
| oracle_result == your_result, | |
| "disagreement on {i} * {j}: {oracle_result:?} (correct) vs {your_result:?} (yours)" | |
| ); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment