bsv_script/interpreter/
scriptnum.rs

1//! Script number arithmetic with Bitcoin consensus rules.
2//!
3//! All numbers on the Bitcoin script stack are encoded as little-endian
4//! byte arrays with a sign bit in the most significant bit of the last byte.
5//! Numeric opcodes operate on 4-byte integers in [-2^31+1, 2^31-1] but
6//! results may overflow and remain valid as long as they are not reinterpreted
7//! as numbers.
8
9use num_bigint::BigInt;
10use num_traits::{One, Signed, ToPrimitive, Zero};
11
12use super::error::{InterpreterError, InterpreterErrorCode};
13
14/// A script number using big integer arithmetic for overflow safety.
15#[derive(Debug, Clone)]
16pub struct ScriptNumber {
17    /// The numeric value stored as a big integer.
18    pub val: BigInt,
19    /// Whether post-genesis rules are active (affects serialization clamping).
20    pub after_genesis: bool,
21}
22
23impl ScriptNumber {
24    /// Create a new ScriptNumber from an i64 value.
25    pub fn new(val: i64, after_genesis: bool) -> Self {
26        ScriptNumber {
27            val: BigInt::from(val),
28            after_genesis,
29        }
30    }
31
32    /// Parse a byte array into a ScriptNumber.
33    ///
34    /// `script_num_len` is the max allowed byte length.
35    /// `require_minimal` enforces minimal encoding.
36    /// `after_genesis` enables post-genesis rules.
37    pub fn from_bytes(
38        bb: &[u8],
39        script_num_len: usize,
40        require_minimal: bool,
41        after_genesis: bool,
42    ) -> Result<Self, InterpreterError> {
43        if bb.len() > script_num_len {
44            return Err(InterpreterError::new(
45                InterpreterErrorCode::NumberTooBig,
46                format!(
47                    "numeric value encoded as {:02x?} is {} bytes which exceeds the max allowed of {}",
48                    bb, bb.len(), script_num_len
49                ),
50            ));
51        }
52
53        if require_minimal {
54            check_minimal_data_encoding(bb)?;
55        }
56
57        if bb.is_empty() {
58            return Ok(ScriptNumber {
59                val: BigInt::zero(),
60                after_genesis,
61            });
62        }
63
64        // Decode from little endian with sign bit
65        let mut v = BigInt::zero();
66        for (i, &b) in bb.iter().enumerate() {
67            v |= BigInt::from(b) << (8 * i);
68        }
69
70        // If the most significant byte has the sign bit set, the number is negative
71        if bb[bb.len() - 1] & 0x80 != 0 {
72            // Remove the sign bit and negate
73            let mask = !(BigInt::from(0x80_i64) << (8 * (bb.len() - 1)));
74            v &= mask;
75            v = -v;
76        }
77
78        Ok(ScriptNumber {
79            val: v,
80            after_genesis,
81        })
82    }
83
84    /// Serialize the number to bytes in little-endian with sign bit.
85    pub fn to_bytes(&self) -> Vec<u8> {
86        if self.val.is_zero() {
87            return vec![];
88        }
89
90        let is_negative = self.val.is_negative();
91        let abs_val = if is_negative {
92            -self.val.clone()
93        } else {
94            self.val.clone()
95        };
96
97        // For pre-genesis, clamp to i32 range for serialization
98        let working_val = if !self.after_genesis {
99            let v = self.val.to_i64().unwrap_or(if is_negative {
100                i64::MIN
101            } else {
102                i64::MAX
103            });
104            if v > i32::MAX as i64 {
105                BigInt::from(i32::MAX)
106            } else if v < i32::MIN as i64 {
107                BigInt::from(i32::MIN).abs()
108            } else {
109                abs_val.clone()
110            }
111        } else {
112            abs_val.clone()
113        };
114
115        let _ = working_val; // we use abs_val below
116
117        // Convert absolute value to little-endian bytes
118        let mut result: Vec<u8> = Vec::new();
119        let mut cpy = abs_val;
120        while cpy > BigInt::zero() {
121            result.push((&cpy & BigInt::from(0xff_u8))
122                .to_u8()
123                .unwrap_or(0));
124            cpy >>= 8;
125        }
126
127        if result.is_empty() {
128            return vec![];
129        }
130
131        // Handle sign bit
132        if result[result.len() - 1] & 0x80 != 0 {
133            // Need an extra byte for the sign
134            result.push(if is_negative { 0x80 } else { 0x00 });
135        } else if is_negative {
136            let last = result.len() - 1;
137            result[last] |= 0x80;
138        }
139
140        result
141    }
142
143    // Arithmetic operations (mutating, return self for chaining like Go)
144
145    /// Add another script number to this one and return self for chaining.
146    pub fn add(&mut self, other: &ScriptNumber) -> &mut Self {
147        self.val = &self.val + &other.val;
148        self
149    }
150
151    /// Subtract another script number from this one and return self for chaining.
152    pub fn sub(&mut self, other: &ScriptNumber) -> &mut Self {
153        self.val = &self.val - &other.val;
154        self
155    }
156
157    /// Multiply this script number by another and return self for chaining.
158    pub fn mul(&mut self, other: &ScriptNumber) -> &mut Self {
159        self.val = &self.val * &other.val;
160        self
161    }
162
163    /// Divide this script number by another (truncated toward zero) and return self for chaining.
164    pub fn div(&mut self, other: &ScriptNumber) -> &mut Self {
165        // Truncation towards zero (like Go's Quo)
166        use num_integer::Integer;
167        let (q, r) = self.val.div_rem(&other.val);
168        // Go's Quo truncates toward zero. BigInt div_rem might differ for negatives.
169        // num_integer div_rem uses truncated division, which matches Go's Quo.
170        let _ = r;
171        self.val = q;
172        self
173    }
174
175    /// Compute the truncated remainder of dividing by another and return self for chaining.
176    pub fn modulo(&mut self, other: &ScriptNumber) -> &mut Self {
177        // Go's Rem: truncated remainder
178        use num_integer::Integer;
179        let (_, r) = self.val.div_rem(&other.val);
180        self.val = r;
181        self
182    }
183
184    /// Increment this number by one and return self for chaining.
185    pub fn incr(&mut self) -> &mut Self {
186        self.val = &self.val + BigInt::one();
187        self
188    }
189
190    /// Decrement this number by one and return self for chaining.
191    pub fn decr(&mut self) -> &mut Self {
192        self.val = &self.val - BigInt::one();
193        self
194    }
195
196    /// Negate this number and return self for chaining.
197    pub fn neg(&mut self) -> &mut Self {
198        self.val = -self.val.clone();
199        self
200    }
201
202    /// Replace this number with its absolute value and return self for chaining.
203    pub fn abs(&mut self) -> &mut Self {
204        if self.val.is_negative() {
205            self.val = -self.val.clone();
206        }
207        self
208    }
209
210    /// Set this number to the given i64 value and return self for chaining.
211    pub fn set(&mut self, i: i64) -> &mut Self {
212        self.val = BigInt::from(i);
213        self
214    }
215
216    // Comparison operations
217
218    /// Return true if this number is zero.
219    pub fn is_zero(&self) -> bool {
220        self.val.is_zero()
221    }
222
223    /// Return true if this number is less than `other`.
224    pub fn less_than(&self, other: &ScriptNumber) -> bool {
225        self.val < other.val
226    }
227
228    /// Return true if this number is less than the given i64 value.
229    pub fn less_than_int(&self, i: i64) -> bool {
230        self.val < BigInt::from(i)
231    }
232
233    /// Return true if this number is less than or equal to `other`.
234    pub fn less_than_or_equal(&self, other: &ScriptNumber) -> bool {
235        self.val <= other.val
236    }
237
238    /// Return true if this number is greater than `other`.
239    pub fn greater_than(&self, other: &ScriptNumber) -> bool {
240        self.val > other.val
241    }
242
243    /// Return true if this number is greater than the given i64 value.
244    pub fn greater_than_int(&self, i: i64) -> bool {
245        self.val > BigInt::from(i)
246    }
247
248    /// Return true if this number is greater than or equal to `other`.
249    pub fn greater_than_or_equal(&self, other: &ScriptNumber) -> bool {
250        self.val >= other.val
251    }
252
253    /// Return true if this number is equal to `other`.
254    pub fn equal(&self, other: &ScriptNumber) -> bool {
255        self.val == other.val
256    }
257
258    /// Return true if this number is equal to the given i64 value.
259    pub fn equal_int(&self, i: i64) -> bool {
260        self.val == BigInt::from(i)
261    }
262
263    // Conversion
264
265    /// Convert to i32, clamping to [i32::MIN, i32::MAX] on overflow.
266    pub fn to_i32(&self) -> i32 {
267        match self.val.to_i64() {
268            Some(v) => {
269                if v > i32::MAX as i64 {
270                    i32::MAX
271                } else if v < i32::MIN as i64 {
272                    i32::MIN
273                } else {
274                    v as i32
275                }
276            }
277            None => {
278                if self.val.is_positive() {
279                    i32::MAX
280                } else {
281                    i32::MIN
282                }
283            }
284        }
285    }
286
287    /// Convert to i64, clamping to [i64::MIN, i64::MAX] on overflow.
288    pub fn to_i64(&self) -> i64 {
289        if self.greater_than_int(i64::MAX) {
290            return i64::MAX;
291        }
292        if self.less_than_int(i64::MIN) {
293            return i64::MIN;
294        }
295        self.val.to_i64().unwrap_or(0)
296    }
297
298    /// Convert to i64, returning 0 if the value does not fit.
299    pub fn to_int(&self) -> i64 {
300        self.val.to_i64().unwrap_or(0)
301    }
302}
303
304/// Minimally encode a byte array (used by OP_BIN2NUM).
305pub fn minimally_encode(data: &[u8]) -> Vec<u8> {
306    if data.is_empty() {
307        return vec![];
308    }
309
310    let mut data = data.to_vec();
311    let last = data[data.len() - 1];
312
313    if last & 0x7f != 0 {
314        return data;
315    }
316
317    if data.len() == 1 {
318        return vec![];
319    }
320
321    if data[data.len() - 2] & 0x80 != 0 {
322        return data;
323    }
324
325    let mut i = data.len() - 1;
326    while i > 0 {
327        if data[i - 1] != 0 {
328            if data[i - 1] & 0x80 != 0 {
329                data[i] = last;
330                return data[..=i].to_vec();
331            } else {
332                data[i - 1] |= last;
333                return data[..i].to_vec();
334            }
335        }
336        i -= 1;
337    }
338
339    vec![]
340}
341
342/// Check that a byte array uses minimal data encoding.
343pub fn check_minimal_data_encoding(v: &[u8]) -> Result<(), InterpreterError> {
344    if v.is_empty() {
345        return Ok(());
346    }
347
348    if v[v.len() - 1] & 0x7f == 0 {
349        if v.len() == 1 || v[v.len() - 2] & 0x80 == 0 {
350            return Err(InterpreterError::new(
351                InterpreterErrorCode::MinimalData,
352                format!(
353                    "numeric value encoded as {:02x?} is not minimally encoded",
354                    v
355                ),
356            ));
357        }
358    }
359
360    Ok(())
361}
362
363#[cfg(test)]
364mod tests {
365    use super::*;
366
367    fn hex_to_bytes(s: &str) -> Vec<u8> {
368        hex::decode(s).unwrap()
369    }
370
371    #[test]
372    fn test_script_num_bytes() {
373        let tests: Vec<(i64, Vec<u8>)> = vec![
374            (0, vec![]),
375            (1, hex_to_bytes("01")),
376            (-1, hex_to_bytes("81")),
377            (127, hex_to_bytes("7f")),
378            (-127, hex_to_bytes("ff")),
379            (128, hex_to_bytes("8000")),
380            (-128, hex_to_bytes("8080")),
381            (129, hex_to_bytes("8100")),
382            (-129, hex_to_bytes("8180")),
383            (256, hex_to_bytes("0001")),
384            (-256, hex_to_bytes("0081")),
385            (32767, hex_to_bytes("ff7f")),
386            (-32767, hex_to_bytes("ffff")),
387            (32768, hex_to_bytes("008000")),
388            (-32768, hex_to_bytes("008080")),
389            (65535, hex_to_bytes("ffff00")),
390            (-65535, hex_to_bytes("ffff80")),
391            (524288, hex_to_bytes("000008")),
392            (-524288, hex_to_bytes("000088")),
393            (7340032, hex_to_bytes("000070")),
394            (-7340032, hex_to_bytes("0000f0")),
395            (8388608, hex_to_bytes("00008000")),
396            (-8388608, hex_to_bytes("00008080")),
397            (2147483647, hex_to_bytes("ffffff7f")),
398            (-2147483647, hex_to_bytes("ffffffff")),
399            // Out of range values (still valid for results)
400            (2147483648, hex_to_bytes("0000008000")),
401            (-2147483648, hex_to_bytes("0000008080")),
402            (2415919104, hex_to_bytes("0000009000")),
403            (-2415919104, hex_to_bytes("0000009080")),
404            (4294967295, hex_to_bytes("ffffffff00")),
405            (-4294967295, hex_to_bytes("ffffffff80")),
406            (4294967296, hex_to_bytes("0000000001")),
407            (-4294967296, hex_to_bytes("0000000081")),
408            (281474976710655, hex_to_bytes("ffffffffffff00")),
409            (-281474976710655, hex_to_bytes("ffffffffffff80")),
410            (72057594037927935, hex_to_bytes("ffffffffffffff00")),
411            (-72057594037927935, hex_to_bytes("ffffffffffffff80")),
412            (9223372036854775807, hex_to_bytes("ffffffffffffff7f")),
413            (-9223372036854775807, hex_to_bytes("ffffffffffffffff")),
414        ];
415
416        for (num, expected) in &tests {
417            let sn = ScriptNumber {
418                val: BigInt::from(*num),
419                after_genesis: true, // after_genesis doesn't clamp
420            };
421            let got = sn.to_bytes();
422            assert_eq!(
423                &got, expected,
424                "Bytes: num={}, got={:02x?}, want={:02x?}",
425                num, got, expected
426            );
427        }
428    }
429
430    #[test]
431    fn test_make_script_num() {
432        struct Test {
433            serialized: Vec<u8>,
434            num: i64,
435            num_len: usize,
436            minimal_encoding: bool,
437            expect_err: bool,
438        }
439
440        let tests = vec![
441            // Minimal encoding rejects negative 0
442            Test { serialized: hex_to_bytes("80"), num: 0, num_len: 4, minimal_encoding: true, expect_err: true },
443            // Valid minimally encoded
444            Test { serialized: vec![], num: 0, num_len: 4, minimal_encoding: true, expect_err: false },
445            Test { serialized: hex_to_bytes("01"), num: 1, num_len: 4, minimal_encoding: true, expect_err: false },
446            Test { serialized: hex_to_bytes("81"), num: -1, num_len: 4, minimal_encoding: true, expect_err: false },
447            Test { serialized: hex_to_bytes("7f"), num: 127, num_len: 4, minimal_encoding: true, expect_err: false },
448            Test { serialized: hex_to_bytes("ff"), num: -127, num_len: 4, minimal_encoding: true, expect_err: false },
449            Test { serialized: hex_to_bytes("8000"), num: 128, num_len: 4, minimal_encoding: true, expect_err: false },
450            Test { serialized: hex_to_bytes("8080"), num: -128, num_len: 4, minimal_encoding: true, expect_err: false },
451            Test { serialized: hex_to_bytes("8100"), num: 129, num_len: 4, minimal_encoding: true, expect_err: false },
452            Test { serialized: hex_to_bytes("8180"), num: -129, num_len: 4, minimal_encoding: true, expect_err: false },
453            Test { serialized: hex_to_bytes("0001"), num: 256, num_len: 4, minimal_encoding: true, expect_err: false },
454            Test { serialized: hex_to_bytes("0081"), num: -256, num_len: 4, minimal_encoding: true, expect_err: false },
455            Test { serialized: hex_to_bytes("ff7f"), num: 32767, num_len: 4, minimal_encoding: true, expect_err: false },
456            Test { serialized: hex_to_bytes("ffff"), num: -32767, num_len: 4, minimal_encoding: true, expect_err: false },
457            Test { serialized: hex_to_bytes("008000"), num: 32768, num_len: 4, minimal_encoding: true, expect_err: false },
458            Test { serialized: hex_to_bytes("008080"), num: -32768, num_len: 4, minimal_encoding: true, expect_err: false },
459            Test { serialized: hex_to_bytes("ffffff7f"), num: 2147483647, num_len: 4, minimal_encoding: true, expect_err: false },
460            Test { serialized: hex_to_bytes("ffffffff"), num: -2147483647, num_len: 4, minimal_encoding: true, expect_err: false },
461            // 5-byte numbers
462            Test { serialized: hex_to_bytes("ffffffff7f"), num: 549755813887, num_len: 5, minimal_encoding: true, expect_err: false },
463            Test { serialized: hex_to_bytes("ffffffffff"), num: -549755813887, num_len: 5, minimal_encoding: true, expect_err: false },
464            // Out of range for 4-byte
465            Test { serialized: hex_to_bytes("0000008000"), num: 0, num_len: 4, minimal_encoding: true, expect_err: true },
466            // Non-minimally encoded with flag
467            Test { serialized: hex_to_bytes("00"), num: 0, num_len: 4, minimal_encoding: true, expect_err: true },
468            Test { serialized: hex_to_bytes("0100"), num: 0, num_len: 4, minimal_encoding: true, expect_err: true },
469            // Non-minimally encoded without flag (OK)
470            Test { serialized: hex_to_bytes("00"), num: 0, num_len: 4, minimal_encoding: false, expect_err: false },
471            Test { serialized: hex_to_bytes("0100"), num: 1, num_len: 4, minimal_encoding: false, expect_err: false },
472        ];
473
474        for test in &tests {
475            let result = ScriptNumber::from_bytes(
476                &test.serialized,
477                test.num_len,
478                test.minimal_encoding,
479                true,
480            );
481            match result {
482                Ok(sn) => {
483                    assert!(
484                        !test.expect_err,
485                        "from_bytes({:02x?}): expected error",
486                        test.serialized
487                    );
488                    assert_eq!(
489                        sn.to_int(),
490                        test.num,
491                        "from_bytes({:02x?}): got {}, want {}",
492                        test.serialized,
493                        sn.to_int(),
494                        test.num
495                    );
496                }
497                Err(_) => {
498                    assert!(
499                        test.expect_err,
500                        "from_bytes({:02x?}): unexpected error",
501                        test.serialized
502                    );
503                }
504            }
505        }
506    }
507
508    #[test]
509    fn test_script_num_int32() {
510        let tests: Vec<(i64, i32)> = vec![
511            (0, 0),
512            (1, 1),
513            (-1, -1),
514            (2147483647, 2147483647),
515            (-2147483647, -2147483647),
516            (-2147483648, -2147483648),
517            // Clamped values
518            (2147483648, 2147483647),
519            (-2147483649, -2147483648),
520            (9223372036854775807, 2147483647),
521            (-9223372036854775808, -2147483648),
522        ];
523
524        for (input, want) in &tests {
525            let sn = ScriptNumber {
526                val: BigInt::from(*input),
527                after_genesis: false,
528            };
529            assert_eq!(
530                sn.to_i32(),
531                *want,
532                "Int32({}): got {}, want {}",
533                input,
534                sn.to_i32(),
535                want
536            );
537        }
538    }
539
540    #[test]
541    fn test_minimally_encode() {
542        // Empty stays empty
543        assert_eq!(minimally_encode(&[]), Vec::<u8>::new());
544        // Already minimal
545        assert_eq!(minimally_encode(&[0x7f]), vec![0x7f]);
546        // Single zero byte becomes empty
547        assert_eq!(minimally_encode(&[0x00]), Vec::<u8>::new());
548        // Negative zero becomes empty
549        assert_eq!(minimally_encode(&[0x80]), Vec::<u8>::new());
550    }
551}
bsv_script/interpreter/scriptnum.rs

bsv_script/interpreter/
scriptnum.rs
