Repository: ergoplatform/sigma-rust (language: rust)

Issue:
[200 SigmaUSD] Implement modulo `%` bin op
- Add `ArithOp::Modulo`;
- implement evaluation in `eval::bin_op`;


Discussion / hints:
taking this one
@greenhat bigint doesn't support checked_rem, what should I do in that case?
> @greenhat bigint doesn't support checked_rem, what should I do in that case?

We need to implement it the same way it's done in Java (modulus > 0) which is used in Scala reference version (sigmastate) - https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#mod-java.math.BigInteger- 
I did some research so correct me if I'm wrong. 
This type of modulo acts different way than normal %. 
Example: 10 mod 7 = 3 but -10 mod 7 = 4

I saw `BigInt` includes a trait method `mod_floor` but I can't bring the trait into scope.
Also if my assumption about mod is correct than existing implementation of checked_rem are wrong because they do -10 mod 7 = -3
Good catch! We need to implement modulo op with exactly the same semantics as `java.math.BigInteger.mod` for our BigInt256 type and as java modulo op for other numeric types. This is very important since the reference interpreter in Scala (sigmastate) implements modulo op in terms of java ops.

Regarding `mod_floor`, have you tried to use https://docs.rs/num-integer/0.1.44/num_integer/ ?

I'm upping the bounty for this issue due to increased complexity.
So `BigInteger.mod` for `BigInt256` and `%` for other numeric types.
Should I add `num-integer` as dependency?
> So `BigInteger.mod` for `BigInt256` and `%` for other numeric types. Should I add `num-integer` as dependency?

That's correct. Yes, please add it.

Fix patch:
diff --git a/ergotree-interpreter/src/eval/bin_op.rs b/ergotree-interpreter/src/eval/bin_op.rs
index 7b0f5ef65..2f872e938 100644
--- a/ergotree-interpreter/src/eval/bin_op.rs
+++ b/ergotree-interpreter/src/eval/bin_op.rs
@@ -12,6 +12,7 @@ use eval::costs::Costs;
 use num_traits::CheckedAdd;
 use num_traits::CheckedDiv;
 use num_traits::CheckedMul;
+use num_traits::CheckedRem;
 use num_traits::CheckedSub;
 use num_traits::Num;
 
@@ -77,6 +78,17 @@ where
         .map(|t| t.into()) // convert T to Value
 }
 
+fn eval_mod<T>(lv_raw: T, rv: Value) -> Result<Value, EvalError>
+where
+    T: Num + CheckedRem + TryExtractFrom<Value> + Into<Value> + std::fmt::Display,
+{
+    let rv_raw = rv.try_extract_into::<T>()?;
+    lv_raw
+        .checked_rem(&rv_raw)
+        .ok_or_else(|| arithmetic_err("%", lv_raw, rv_raw, "exception"))
+        .map(|t| t.into()) // convert T to Value
+}
+
 fn eval_bit_op<T, F>(lv_raw: T, rv: Value, op: F) -> Result<Value, EvalError>
 where
     T: Num + TryExtractFrom<Value> + Into<Value> + std::fmt::Display,
@@ -256,6 +268,17 @@ impl Evaluable for BinOp {
                         lv
                     ))),
                 },
+                ArithOp::Modulo => match lv {
+                    Value::Byte(lv_raw) => eval_mod(lv_raw, rv()?),
+                    Value::Short(lv_raw) => eval_mod(lv_raw, rv()?),
+                    Value::Int(lv_raw) => eval_mod(lv_raw, rv()?),
+                    Value::Long(lv_raw) => eval_mod(lv_raw, rv()?),
+                    Value::BigInt(lv_raw) => eval_mod(lv_raw, rv()?),
+                    _ => Err(EvalError::UnexpectedValue(format!(
+                        "expected BinOp::left to be numeric value, got {0:?}",
+                        lv
+                    ))),
+                },
             },
             BinOpKind::Bit(op) => match op {
                 BitOp::BitAnd => match lv {
@@ -490,6 +513,11 @@ mod tests {
         );
         assert!(eval_arith_op(ArithOp::Divide, b(20), b(0)).is_err());
 
+        assert!(eval_arith_op(ArithOp::Modulo, b(20), b(-1)).is_err());
+        assert!(eval_arith_op(ArithOp::Modulo, b(20), b(0)).is_err());
+        assert_eq!(eval_arith_op(ArithOp::Modulo, max(), b(1)), Ok(b(0)));
+        assert_eq!(eval_arith_op(ArithOp::Modulo, min(), b(1)), Ok(b(0)));
+
         assert!(eval_arith_op(ArithOp::Plus, max(), b(1)).is_err());
         assert_eq!(eval_arith_op(ArithOp::Plus, max(), b(0)), Ok(max()));
         assert!(eval_arith_op(ArithOp::Plus, min(), b(-1)).is_err());
@@ -520,6 +548,7 @@ mod tests {
             prop_assert_eq!(eval_arith_op(ArithOp::Minus, l, r).ok(), l.checked_sub(r));
             prop_assert_eq!(eval_arith_op(ArithOp::Multiply, l, r).ok(), l.checked_mul(r));
             prop_assert_eq!(eval_arith_op(ArithOp::Divide, l, r).ok(), l.checked_div(r));
+            prop_assert_eq!(eval_arith_op(ArithOp::Modulo, l, r).ok(), l.checked_rem(r));
             prop_assert_eq!(eval_arith_op::<i64>(ArithOp::Max, l, r).unwrap(), l.max(r));
             prop_assert_eq!(eval_arith_op::<i64>(ArithOp::Min, l, r).unwrap(), l.min(r));
 
@@ -539,6 +568,7 @@ mod tests {
             prop_assert_eq!(eval_arith_op(ArithOp::Minus, l, r).ok(), l.checked_sub(r));
             prop_assert_eq!(eval_arith_op(ArithOp::Multiply, l, r).ok(), l.checked_mul(r));
             prop_assert_eq!(eval_arith_op(ArithOp::Divide, l, r).ok(), l.checked_div(r));
+            prop_assert_eq!(eval_arith_op(ArithOp::Modulo, l, r).ok(), l.checked_rem(r));
             prop_assert_eq!(eval_arith_op::<i32>(ArithOp::Max, l, r).unwrap(), l.max(r));
             prop_assert_eq!(eval_arith_op::<i32>(ArithOp::Min, l, r).unwrap(), l.min(r));
 
@@ -558,6 +588,7 @@ mod tests {
             prop_assert_eq!(eval_arith_op(ArithOp::Minus, l, r).ok(), l.checked_sub(r));
             prop_assert_eq!(eval_arith_op(ArithOp::Multiply, l, r).ok(), l.checked_mul(r));
             prop_assert_eq!(eval_arith_op(ArithOp::Divide, l, r).ok(), l.checked_div(r));
+            prop_assert_eq!(eval_arith_op(ArithOp::Modulo, l, r).ok(), l.checked_rem(r));
             prop_assert_eq!(eval_arith_op::<i16>(ArithOp::Max, l, r).unwrap(), l.max(r));
             prop_assert_eq!(eval_arith_op::<i16>(ArithOp::Min, l, r).unwrap(), l.min(r));
 
@@ -577,6 +608,7 @@ mod tests {
             prop_assert_eq!(eval_arith_op(ArithOp::Minus, l, r).ok(), l.checked_sub(r));
             prop_assert_eq!(eval_arith_op(ArithOp::Multiply, l, r).ok(), l.checked_mul(r));
             prop_assert_eq!(eval_arith_op(ArithOp::Divide, l, r).ok(), l.checked_div(r));
+            prop_assert_eq!(eval_arith_op(ArithOp::Modulo, l, r).ok(), l.checked_rem(r));
             prop_assert_eq!(eval_arith_op::<i8>(ArithOp::Max, l, r).unwrap(), l.max(r));
             prop_assert_eq!(eval_arith_op::<i8>(ArithOp::Min, l, r).unwrap(), l.min(r));
 
@@ -598,6 +630,7 @@ mod tests {
             prop_assert_eq!(eval_arith_op(ArithOp::Minus, l.clone(), r.clone()).ok(), l.checked_sub(&r));
             prop_assert_eq!(eval_arith_op(ArithOp::Multiply, l.clone(), r.clone()).ok(), l.checked_mul(&r));
             prop_assert_eq!(eval_arith_op(ArithOp::Divide, l.clone(), r.clone()).ok(), l.checked_div(&r));
+            prop_assert_eq!(eval_arith_op(ArithOp::Modulo, l.clone(), r.clone()).ok(), l.checked_rem(&r));
             prop_assert_eq!(eval_arith_op::<BigInt256>(ArithOp::Max, l.clone(),
                     r.clone()).unwrap(), l.clone().max(r.clone()));
             prop_assert_eq!(eval_arith_op::<BigInt256>(ArithOp::Min, l.clone(),
diff --git a/ergotree-ir/Cargo.toml b/ergotree-ir/Cargo.toml
index 130ed820a..44ab5055d 100644
--- a/ergotree-ir/Cargo.toml
+++ b/ergotree-ir/Cargo.toml
@@ -33,6 +33,7 @@ bounded-vec = { version = "^0.4.0" }
 num256 = "0.3.1"
 num-traits = "0.2.14"
 num-derive = "0.3.3"
+num-integer = "0.1.44"
 strum = "0.21"
 strum_macros = "0.21"
 indexmap = "1.3.2"
diff --git a/ergotree-ir/src/bigint256.rs b/ergotree-ir/src/bigint256.rs
index 15b723ba5..e7ffc38dd 100644
--- a/ergotree-ir/src/bigint256.rs
+++ b/ergotree-ir/src/bigint256.rs
@@ -9,7 +9,10 @@ use num_bigint::BigInt;
 use num_bigint::BigUint;
 use num_bigint::ToBigInt;
 use num_derive::{One, Zero};
-use num_traits::{Bounded, CheckedAdd, CheckedDiv, CheckedMul, CheckedNeg, CheckedSub, Num};
+use num_integer::Integer;
+use num_traits::{
+    Bounded, CheckedAdd, CheckedDiv, CheckedMul, CheckedNeg, CheckedRem, CheckedSub, Num, Zero,
+};
 
 /// 256-bit signed integer type
 #[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone, Zero, One)]
@@ -200,6 +203,15 @@ impl CheckedDiv for BigInt256 {
     }
 }
 
+impl CheckedRem for BigInt256 {
+    fn checked_rem(&self, v: &Self) -> Option<Self> {
+        if v.0 .0 <= BigInt::zero() {
+            return None;
+        }
+        Some(BigInt256(Int256(self.0 .0.mod_floor(&v.0 .0))))
+    }
+}
+
 impl CheckedNeg for BigInt256 {
     fn checked_neg(&self) -> Option<Self> {
         if self == &BigInt256::min_value() {
diff --git a/ergotree-ir/src/mir/bin_op.rs b/ergotree-ir/src/mir/bin_op.rs
index e048663c3..d2756bef0 100644
--- a/ergotree-ir/src/mir/bin_op.rs
+++ b/ergotree-ir/src/mir/bin_op.rs
@@ -27,6 +27,8 @@ pub enum ArithOp {
     Max,
     /// Min of two values
     Min,
+    /// Modulo
+    Modulo,
 }
 
 impl From<ArithOp> for OpCode {
@@ -38,6 +40,7 @@ impl From<ArithOp> for OpCode {
             ArithOp::Divide => OpCode::DIVISION,
             ArithOp::Max => OpCode::MAX,
             ArithOp::Min => OpCode::MIN,
+            ArithOp::Modulo => OpCode::MODULO,
         }
     }
 }
diff --git a/ergotree-ir/src/serialization/expr.rs b/ergotree-ir/src/serialization/expr.rs
index 0bd5e593b..827e249e6 100644
--- a/ergotree-ir/src/serialization/expr.rs
+++ b/ergotree-ir/src/serialization/expr.rs
@@ -139,6 +139,7 @@ impl Expr {
                 OpCode::DIVISION => Ok(bin_op_sigma_parse(ArithOp::Divide.into(), r)?),
                 OpCode::MAX => Ok(bin_op_sigma_parse(ArithOp::Max.into(), r)?),
                 OpCode::MIN => Ok(bin_op_sigma_parse(ArithOp::Min.into(), r)?),
+                OpCode::MODULO => Ok(bin_op_sigma_parse(ArithOp::Modulo.into(), r)?),
                 OpCode::BIT_OR => Ok(bin_op_sigma_parse(BitOp::BitOr.into(), r)?),
                 OpCode::BIT_AND => Ok(bin_op_sigma_parse(BitOp::BitAnd.into(), r)?),
                 OpCode::BIT_XOR => Ok(bin_op_sigma_parse(BitOp::BitXor.into(), r)?),


Test patch: