starkware-libs · Stavbe · Jun 15, 2025 · Jun 15, 2025
diff --git a/stwo_cairo_prover/Cargo.lock b/stwo_cairo_prover/Cargo.lock
diff --git a/stwo_cairo_prover/crates/adapter/Cargo.toml b/stwo_cairo_prover/crates/adapter/Cargo.toml
@@ -27,6 +27,7 @@ bincode = { version = "2.0.1", features = [
 ] }
 dashmap = "6.1.0"
 rayon.workspace = true
+crypto-bigint = "0.5.1"
 
 [dev-dependencies]
 cairo-lang-casm.workspace = true

diff --git a/stwo_cairo_prover/crates/adapter/src/memory.rs b/stwo_cairo_prover/crates/adapter/src/memory.rs
@@ -7,7 +7,8 @@ use serde::{Deserialize, Serialize};
 use stwo_cairo_common::memory::{N_BITS_PER_FELT, N_M31_IN_SMALL_FELT252};
 use tracing::{span, Level};
 
+/// P is 2^251 + 17 * 2^192 - 1.
+/// All constants below are in little endian.
 pub const P_MIN_1: [u32; 8] = [
     0x0000_0000,
     0x0000_0000,
@@ -18,6 +19,7 @@ pub const P_MIN_1: [u32; 8] = [
     0x0000_0011,
     0x0800_0000,
 ];
+
 pub const P_MIN_2: [u32; 8] = [
     0xFFFF_FFFF,
     0xFFFF_FFFF,

diff --git a/stwo_cairo_prover/crates/adapter/src/opcodes.rs b/stwo_cairo_prover/crates/adapter/src/opcodes.rs
@@ -1,5 +1,6 @@
 use std::fmt::Display;
 
+use crypto_bigint::U256;
 use rayon::iter::ParallelIterator;
 use rayon::slice::ParallelSlice;
 use serde::{Deserialize, Serialize};
@@ -12,10 +13,6 @@ use super::memory::{MemoryBuilder, MemoryValue};
 use super::vm_import::RelocatedTraceEntry;
 use crate::memory::limbs_to_u128;
 
-// Small add operands are 27 bits.
-const SMALL_ADD_MAX_VALUE: i32 = 2_i32.pow(27) - 1;
-const SMALL_ADD_MIN_VALUE: i32 = -(2_i32.pow(27));
-
 // Small mul operands are 36 bits.
 const SMALL_MUL_MAX_VALUE: u64 = 2_u64.pow(36) - 1;
 const SMALL_MUL_MIN_VALUE: u64 = 0;
@@ -694,14 +691,38 @@ fn is_within_range(val: MemoryValue, min: i128, max: i128) -> bool {
     }
 }
 
-// Returns 'true' if all the operands are within the range of [-2^27, 2^27 - 1].
+fn u256_from_le_array(arr: [u32; 8]) -> U256 {
+    let mut buf = [0u8; 32];
+    for (i, x) in arr.iter().enumerate() {
+        buf[i * 4..(i + 1) * 4].copy_from_slice(&x.to_le_bytes());
+    }
+    U256::from_le_slice(&buf)
+}
+
+// 2^27 - 1
+const SMALL_ADD_POSITIVE_UPPER_BOUND: U256 = U256::from_u32(2_u32.pow(27) - 1);
+// P + 2^27 -1
+const SMALL_ADD_NEGATIVE_UPPER_BOUND: U256 = U256::from_words([
+    0x0000000008000000,
+    0x0000000000000000,
+    0x0000000000000000,
+    0x0800000000000011,
+]);
+// P - 2^27
+const SMALL_ADD_NEGATIVE_LOWER_BOUND: U256 = U256::from_words([
+    0xFFFFFFFFF8000001,
+    0xFFFFFFFFFFFFFFFF,
+    0xFFFFFFFFFFFFFFFF,
+    0x0800000000000010,
+]);
+
+// Returns 'true' if all the operands modulo P are within the range of [-2^27, 2^27 - 1].
 fn is_small_add(dst: MemoryValue, op0: MemoryValue, op_1: MemoryValue) -> bool {
     [dst, op0, op_1].iter().all(|val| {
-        is_within_range(
-            *val,
-            SMALL_ADD_MIN_VALUE as i128,
-            SMALL_ADD_MAX_VALUE as i128,
-        )
+        let value = u256_from_le_array(val.as_u256());
+
+        value <= SMALL_ADD_POSITIVE_UPPER_BOUND
+            || (value >= SMALL_ADD_NEGATIVE_LOWER_BOUND && value <= SMALL_ADD_NEGATIVE_UPPER_BOUND)
     })<
8000
/span>
 }
 
@@ -730,7 +751,7 @@ mod mappings_tests {
     use crate::adapter::adapter;
     use crate::decode::{Instruction, OpcodeExtension};
     use crate::memory::*;
-    use crate::opcodes::{CasmStatesByOpcode, StateTransitions};
+    use crate::opcodes::{is_small_add, CasmStatesByOpcode, StateTransitions};
     use crate::relocator::relocator_tests::{create_test_relocator, get_test_relocatble_trace};
     use crate::test_utils::program_from_casm;
     use crate::vm_import::RelocatedTraceEntry;
@@ -760,6 +781,133 @@ mod mappings_tests {
         .expect("Failed to run adapter")
     }
 
+    /// Small ranges: [0 … 2^27 − 1] (positive) | [P − 2^27 … P − 1] (negative mod P) | ([P.. P +
+    /// 2^27 − 1] (positive over P)).
+    #[test]
+    fn test_small_add_postive_range() {
+        // lower bound
+        let mut dst = MemoryValue::Small(0);
+        let mut op0 = MemoryValue::Small(0);
+        let mut op1 = MemoryValue::Small(0);
+        assert!(is_small_add(dst, op0, op1));
+
+        // upper bound
+        let postive_upper_bound = 2_u128.pow(27) - 1;
+        dst = MemoryValue::Small(postive_upper_bound);
+        op0 = MemoryValue::Small(postive_upper_bound);
+        op1 = MemoryValue::Small(postive_upper_bound);
+        assert!(is_small_add(dst, op0, op1));
+
+        dst = MemoryValue::F252(dst.as_u256());
+        op0 = MemoryValue::F252(op0.as_u256());
+        op1 = MemoryValue::F252(op1.as_u256());
+        assert!(is_small_add(dst, op0, op1));
+
+        // value in the range
+        let value_in_range = MemoryValue::Small(2_u128.pow(25) - 10);
+        dst = value_in_range;
+        op0 = value_in_range;
+        op1 = value_in_range;
+        assert!(is_small_add(dst, op0, op1));
+    }
+
+    #[test]
+    fn test_small_add_negative_range() {
+        // lower bound
+        let p_min_2_to_27: [u32; 8] = [
+            0xF800_0001,
+            0xFFFF_FFFF,
+            0xFFFF_FFFF,
+            0xFFFF_FFFF,
+            0xFFFF_FFFF,
+            0xFFFF_FFFF,
+            0x0000_0010,
+            0x0800_0000,
+        ];
+        let mut dst = MemoryValue::F252(p_min_2_to_27);
+        let mut op0 = MemoryValue::F252(p_min_2_to_27);
+        let mut op1 = MemoryValue::F252(p_min_2_to_27);
+        assert!(is_small_add(dst, op0, op1));
+
+        // upper bound
+        dst = MemoryValue::F252(P_MIN_1);
+        op0 = MemoryValue::F252(P_MIN_1);
+        op1 = MemoryValue::F252(P_MIN_1);
+        assert!(is_small_add(dst, op0, op1));
+
+        // value in the range
+        let p_min_2_to_10 = [
+            0xfffffc01, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0x00000010,
+            0x08000000,
+        ];
+        op1 = MemoryValue::F252(p_min_2_to_10);
+        op0 = MemoryValue::F252(p_min_2_to_10);
+        assert!(is_small_add(dst, op0, op1));
+    }
+
+    #[test]
+    fn test_small_add_positive_over_p() {
+        // lower bound
+        let p = [
+            0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000011,
+            0x08000000,
+        ];
+        let mut dst = MemoryValue::F252(p);
+        let mut op0 = MemoryValue::F252(p);
+        let mut op1 = MemoryValue::F252(p);
+        assert!(is_small_add(dst, op0, op1));
+
+        // upper bound
+        let mut p_plus_2_to_27_min_1: [u32; 8] = p;
+        p_plus_2_to_27_min_1[0] += 2_u32.pow(27) - 1;
+        dst = MemoryValue::F252(p_plus_2_to_27_min_1);
+        op0 = MemoryValue::F252(p_plus_2_to_27_min_1);
+        op1 = MemoryValue::F252(p_plus_2_to_27_min_1);
+        assert!(is_small_add(dst, op0, op1));
+
+        // value in the range
+        let mut p_plus_2_to_10: [u32; 8] = p;
+        p_plus_2_to_10[0] += 2_u32.pow(10);
+        dst = MemoryValue::F252(p_plus_2_to_10);
+        op0 = MemoryValue:
7D55
:F252(p_plus_2_to_10);
+        op1 = MemoryValue::F252(p_plus_2_to_10);
+        assert!(is_small_add(dst, op0, op1));
+    }
+
+    #[test]
+    fn test_not_small_add() {
+        let value = 2_u128.pow(27);
+        let mut dst = MemoryValue::Small(value);
+        let mut op0 = MemoryValue::Small(value);
+        let mut op1 = MemoryValue::Small(value);
+        assert!(!is_small_add(dst, op0, op1));
+
+        let p_min_2_to_27_min_1: [u32; 8] = [
+            0xF800_0000,
+            0xFFFF_FFFF,
+            0xFFFF_FFFF,
+            0xFFFF_FFFF,
+            0xFFFF_FFFF,
+            0xFFFF_FFFF,
+            0x0000_0010,
+            0x0800_0000,
+        ];
+        dst = MemoryValue::F252(p_min_2_to_27_min_1);
+        op0 = MemoryValue::F252(p_min_2_to_27_min_1);
+        op1 = MemoryValue::F252(p_min_2_to_27_min_1);
+        assert!(!is_small_add(dst, op0, op1));
+
+        let p_plus_2_to_27: [u32; 8] = [
+            0x08000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000011,
+            0x08000000,
+        ];
+
+        dst = MemoryValue::F252(p_plus_2_to_27);
+        op0 = MemoryValue::F252(p_plus_2_to_27);
+        op1 = MemoryValue::F252(p_plus_2_to_27);
+        assert!(!is_small_add(dst, op0, op1));
+    }
+
     #[test]
     fn test_jmp_rel() {
         // Encoding for the instruction `jmp rel [fp]`.
@@ -1036,6 +1184,48 @@ mod mappings_tests {
         assert_eq!(casm_states_by_opcode.assert_eq_opcode_imm.len(), 2);
     }
 
+    #[test]
+    fn test_add_small_negative() {
+        // Encoding for the instruction `[fp + 2] = [fp] + Imm`.
+        // Flags: dst_base_fp, op0_base_fp, op1_imm
+        // Offsets: offset2 = 1, offset1 = 0, offset0 = 0
+            let [ap, fp, pc] = [7, 20, 1];
+        let encoded_instr = 0b0100000000100111100000000000000110000000000000001000000000000010;
+        let x = u128_to_4_limbs(encoded_instr);
+        let mut memory_builder = MemoryBuilder::new(MemoryConfig::default());
+        memory_builder.set(pc, MemoryValue::F252([x[0], x[1], x[2], x[3], 0, 0, 0, 0]));
+        memory_builder.set(pc + 1, MemoryValue::F252(P_MIN_1));
+        memory_builder.set(fp, MemoryValue::F252(P_MIN_1));
+        memory_builder.set(fp + 2, MemoryValue::F252(P_MIN_2));
+        let trace_entry = relocated_trace_entry!(ap as usize, fp as usize, pc as usize);
+
+        let casm_states_by_opcode =
+            CasmStatesByOpcode::from_iter([trace_entry].into_iter(), &memory_builder);
+
+        assert_eq!(casm_states_by_opcode.add_opcode_small.len(), 1);
+    }
+
+    #[test]
+    fn test_add_big_f252() {
+        let [ap, fp, pc] = [7, 20, 1];
+        let encoded_instr = 0b0100000000100111100000000000000110000000000000001000000000000010;
+        let x = u128_to_4_limbs(encoded_instr);
+        let mut memory_builder = MemoryBuilder::new(MemoryConfig::default());
+        memory_builder.set(pc, MemoryValue::F252([x[0], x[1], x[2], x[3], 0, 0, 0, 0]));
+
+        let mut value = [0; 8];
+        value[0..4].copy_from_slice(&u128_to_4_limbs((1 << 127) + 346));
+        memory_builder.set(pc + 1, MemoryValue::F252(value));
+        memory_builder.set(fp, MemoryValue::F252(value));
+        memory_builder.set(fp + 2, MemoryValue::F252(value));
+        let trace_entry = relocated_trace_entry!(ap as usize, fp as usize, pc as usize);
+
+        let casm_states_by_opcode =
+            CasmStatesByOpcode::from_iter([trace_entry].into_iter(), &memory_builder);
+
+        assert_eq!(casm_states_by_opcode.add_opcode.len(), 1);
+    }
+
     #[test]
     fn test_add_big() {
         let instructions = casm! {