diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp --- a/src/script/interpreter.cpp +++ b/src/script/interpreter.cpp @@ -297,8 +297,6 @@ case OP_2MUL: case OP_2DIV: case OP_MUL: - case OP_DIV: - case OP_MOD: case OP_LSHIFT: case OP_RSHIFT: // Disabled opcodes. @@ -311,6 +309,8 @@ case OP_XOR: case OP_NUM2BIN: case OP_BIN2NUM: + case OP_DIV: + case OP_MOD: // Opcodes that have been reenabled. if ((flags & SCRIPT_ENABLE_MONOLITH_OPCODES) == 0) { return true; @@ -926,6 +926,8 @@ case OP_ADD: case OP_SUB: + case OP_DIV: + case OP_MOD: case OP_BOOLAND: case OP_BOOLOR: case OP_NUMEQUAL: @@ -954,6 +956,24 @@ bn = bn1 - bn2; break; + case OP_DIV: + // denominator must not be 0 + if (bn2 == 0) { + return set_error(serror, + SCRIPT_ERR_DIV_BY_ZERO); + } + bn = bn1 / bn2; + break; + + case OP_MOD: + // divisor must not be 0 + if (bn2 == 0) { + return set_error(serror, + SCRIPT_ERR_MOD_BY_ZERO); + } + bn = bn1 % bn2; + break; + case OP_BOOLAND: bn = (bn1 != bnZero && bn2 != bnZero); break; diff --git a/src/script/script.h b/src/script/script.h --- a/src/script/script.h +++ b/src/script/script.h @@ -266,6 +266,20 @@ return operator-(rhs.m_value); } + inline CScriptNum operator/(const int64_t &rhs) const { + return CScriptNum(m_value / rhs); + } + inline CScriptNum operator/(const CScriptNum &rhs) const { + return operator/(rhs.m_value); + } + + inline CScriptNum operator%(const int64_t &rhs) const { + return CScriptNum(m_value % rhs); + } + inline CScriptNum operator%(const CScriptNum &rhs) const { + return operator%(rhs.m_value); + } + inline CScriptNum &operator+=(const CScriptNum &rhs) { return operator+=(rhs.m_value); } diff --git a/src/script/script_error.h b/src/script/script_error.h --- a/src/script/script_error.h +++ b/src/script/script_error.h @@ -40,6 +40,10 @@ SCRIPT_ERR_INVALID_ALTSTACK_OPERATION, SCRIPT_ERR_UNBALANCED_CONDITIONAL, + /* Divisor errors */ + SCRIPT_ERR_DIV_BY_ZERO, + SCRIPT_ERR_MOD_BY_ZERO, + /* CHECKLOCKTIMEVERIFY and CHECKSEQUENCEVERIFY */ SCRIPT_ERR_NEGATIVE_LOCKTIME, SCRIPT_ERR_UNSATISFIED_LOCKTIME, diff --git a/src/script/script_error.cpp b/src/script/script_error.cpp --- a/src/script/script_error.cpp +++ b/src/script/script_error.cpp @@ -55,6 +55,10 @@ return "OP_RETURN was encountered"; case SCRIPT_ERR_UNBALANCED_CONDITIONAL: return "Invalid OP_IF construction"; + case SCRIPT_ERR_DIV_BY_ZERO: + return "Division by zero error"; + case SCRIPT_ERR_MOD_BY_ZERO: + return "Modulo by zero error"; case SCRIPT_ERR_NEGATIVE_LOCKTIME: return "Negative locktime"; case SCRIPT_ERR_UNSATISFIED_LOCKTIME: diff --git a/src/test/data/script_tests.json b/src/test/data/script_tests.json --- a/src/test/data/script_tests.json +++ b/src/test/data/script_tests.json @@ -943,9 +943,9 @@ ["2 2 0 IF MUL ELSE 1 ENDIF", "NOP", "P2SH,STRICTENC", "DISABLED_OPCODE", "MUL disabled"], ["2 2 0 IF MUL ELSE 1 ENDIF", "NOP", "P2SH,STRICTENC,MONOLITH_OPCODES", "DISABLED_OPCODE", "MUL disabled"], ["2 2 0 IF DIV ELSE 1 ENDIF", "NOP", "P2SH,STRICTENC", "DISABLED_OPCODE", "DIV disabled"], -["2 2 0 IF DIV ELSE 1 ENDIF", "NOP", "P2SH,STRICTENC,MONOLITH_OPCODES", "DISABLED_OPCODE", "DIV disabled"], +["2 2 0 IF DIV ELSE 1 ENDIF", "NOP", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK", "DIV enabled"], ["2 2 0 IF MOD ELSE 1 ENDIF", "NOP", "P2SH,STRICTENC", "DISABLED_OPCODE", "MOD disabled"], -["2 2 0 IF MOD ELSE 1 ENDIF", "NOP", "P2SH,STRICTENC,MONOLITH_OPCODES", "DISABLED_OPCODE", "MOD disabled"], +["2 2 0 IF MOD ELSE 1 ENDIF", "NOP", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK", "MOD enabled"], ["2 2 0 IF LSHIFT ELSE 1 ENDIF", "NOP", "P2SH,STRICTENC", "DISABLED_OPCODE", "LSHIFT disabled"], ["2 2 0 IF LSHIFT ELSE 1 ENDIF", "NOP", "P2SH,STRICTENC,MONOLITH_OPCODES", "DISABLED_OPCODE", "LSHIFT disabled"], ["2 2 0 IF RSHIFT ELSE 1 ENDIF", "NOP", "P2SH,STRICTENC", "DISABLED_OPCODE", "RSHIFT disabled"], @@ -983,6 +983,39 @@ ["0 1", "XOR 1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OPERAND_SIZE", "XOR, different operand size"], ["0x01 0xab 0x01 0xcd", "XOR 0x01 0x66 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK", "XOR, more complex operands"], +["DIV"], +["1 1", "DIV 1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["1 -1", "DIV -1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["-1 1", "DIV -1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["-1 -1", "DIV 1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["2 2", "DIV 1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["2 -2", "DIV -1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["-2 2", "DIV -1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["-2 -2", "DIV 1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["0 1", "DIV 0 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["1 0", "DIV", "P2SH,STRICTENC,MONOLITH_OPCODES", "DIV_BY_ZERO", "DIV, divide by zero"], +["3 2", "DIV 1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK", "Round towards zero"], +["3 -2", "DIV -1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK", "Round towards zero"], +["1 1", "DIV DEPTH 1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK", "Stack depth correct"], +["1", "DIV", "P2SH,STRICTENC,MONOLITH_OPCODES", "INVALID_STACK_OPERATION", "Not enough operands"], +["0", "DIV", "P2SH,STRICTENC,MONOLITH_OPCODES", "INVALID_STACK_OPERATION", "Not enough operands"], +["1 1", "DIV 1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["2147483648 1", "DIV", "P2SH,STRICTENC,MONOLITH_OPCODES", "UNKNOWN_ERROR", "We cannot do math on 5-byte integers"], +["1 2147483648", "DIV", "P2SH,STRICTENC,MONOLITH_OPCODES", "UNKNOWN_ERROR", "We cannot do math on 5-byte integers"], + +["MOD"], +["1 1", "MOD 0 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["7 -3", "MOD 1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["-7 3", "MOD -1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["10 3", "MOD 1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["0 1", "MOD 0 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], +["1 0", "MOD", "P2SH,STRICTENC,MONOLITH_OPCODES", "MOD_BY_ZERO", "MOD, modulo by zero"], +["1 1", "MOD DEPTH 1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK", "Stack depth correct"], +["1", "MOD", "P2SH,STRICTENC,MONOLITH_OPCODES", "INVALID_STACK_OPERATION", "Not enough operands"], +["0", "MOD", "P2SH,STRICTENC,MONOLITH_OPCODES", "INVALID_STACK_OPERATION", "Not enough operands"], +["2147483648 1", "MOD", "P2SH,STRICTENC,MONOLITH_OPCODES", "UNKNOWN_ERROR", "We cannot do math on 5-byte integers"], +["1 2147483648", "MOD", "P2SH,STRICTENC,MONOLITH_OPCODES", "UNKNOWN_ERROR", "We cannot do math on 5-byte integers"], + ["EQUAL"], ["", "EQUAL NOT", "P2SH,STRICTENC", "INVALID_STACK_OPERATION", "EQUAL must error when there are no stack items"], ["0", "EQUAL NOT", "P2SH,STRICTENC", "INVALID_STACK_OPERATION", "EQUAL must error when there are not 2 stack items"], @@ -998,13 +1031,13 @@ ["2 DUP MUL", "4 EQUAL", "P2SH,STRICTENC", "DISABLED_OPCODE", "disabled"], ["2 DUP MUL", "4 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "DISABLED_OPCODE", "disabled"], ["2 DUP DIV", "1 EQUAL", "P2SH,STRICTENC", "DISABLED_OPCODE", "disabled"], -["2 DUP DIV", "1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "DISABLED_OPCODE", "disabled"], +["2 DUP DIV", "1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], ["2 2MUL", "4 EQUAL", "P2SH,STRICTENC", "DISABLED_OPCODE", "disabled"], ["2 2MUL", "4 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "DISABLED_OPCODE", "disabled"], ["2 2DIV", "1 EQUAL", "P2SH,STRICTENC", "DISABLED_OPCODE", "disabled"], ["2 2DIV", "1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "DISABLED_OPCODE", "disabled"], ["7 3 MOD", "1 EQUAL", "P2SH,STRICTENC", "DISABLED_OPCODE", "disabled"], -["7 3 MOD", "1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "DISABLED_OPCODE", "disabled"], +["7 3 MOD", "1 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "OK"], ["2 2 LSHIFT", "8 EQUAL", "P2SH,STRICTENC", "DISABLED_OPCODE", "disabled"], ["2 2 LSHIFT", "8 EQUAL", "P2SH,STRICTENC,MONOLITH_OPCODES", "DISABLED_OPCODE", "disabled"], ["2 1 RSHIFT", "1 EQUAL", "P2SH,STRICTENC", "DISABLED_OPCODE", "disabled"], diff --git a/src/test/monolith_opcodes.cpp b/src/test/monolith_opcodes.cpp --- a/src/test/monolith_opcodes.cpp +++ b/src/test/monolith_opcodes.cpp @@ -88,6 +88,42 @@ CheckTestResultForAllFlags({a, b}, CScript() << op, {expected}); } +static valtype NegativeValtype(const valtype &v) { + valtype r(v); + if (r.size() > 0) { + r[r.size() - 1] ^= 0x80; + } + CScriptNum::MinimallyEncode(r); + return r; +} + +BOOST_AUTO_TEST_CASE(negative_valtype_test) { + // Test zero values + BOOST_CHECK(NegativeValtype({}) == valtype{}); + BOOST_CHECK(NegativeValtype({0x00}) == valtype{}); + BOOST_CHECK(NegativeValtype({0x80}) == valtype{}); + BOOST_CHECK(NegativeValtype({0x00, 0x00}) == valtype{}); + BOOST_CHECK(NegativeValtype({0x00, 0x80}) == valtype{}); + + // Non-zero values + BOOST_CHECK(NegativeValtype({0x01}) == valtype{0x81}); + BOOST_CHECK(NegativeValtype({0x81}) == valtype{0x01}); + BOOST_CHECK(NegativeValtype({0x02, 0x01}) == (valtype{0x02, 0x81})); + BOOST_CHECK(NegativeValtype({0x02, 0x81}) == (valtype{0x02, 0x01})); + BOOST_CHECK(NegativeValtype({0xff, 0x02, 0x01}) == + (valtype{0xff, 0x02, 0x81})); + BOOST_CHECK(NegativeValtype({0xff, 0x02, 0x81}) == + (valtype{0xff, 0x02, 0x01})); + BOOST_CHECK(NegativeValtype({0xff, 0xff, 0x02, 0x01}) == + (valtype{0xff, 0xff, 0x02, 0x81})); + BOOST_CHECK(NegativeValtype({0xff, 0xff, 0x02, 0x81}) == + (valtype{0xff, 0xff, 0x02, 0x01})); + + // Should not be overly-minimized + BOOST_CHECK(NegativeValtype({0xff, 0x80}) == (valtype{0xff, 0x00})); + BOOST_CHECK(NegativeValtype({0xff, 0x00}) == (valtype{0xff, 0x80})); +} + /** * Bitwise Opcodes */ @@ -613,4 +649,141 @@ SCRIPT_ERR_IMPOSSIBLE_ENCODING); } +/** + * Arithmetic Opcodes + */ +static void CheckDivMod(const valtype &a, const valtype &b, + const valtype &divExpected, + const valtype &modExpected) { + // Negative values for division + CheckBinaryOp(a, b, OP_DIV, divExpected); + CheckBinaryOp(a, NegativeValtype(b), OP_DIV, NegativeValtype(divExpected)); + CheckBinaryOp(NegativeValtype(a), b, OP_DIV, NegativeValtype(divExpected)); + CheckBinaryOp(NegativeValtype(a), NegativeValtype(b), OP_DIV, divExpected); + + // Negative values for modulo + CheckBinaryOp(a, b, OP_MOD, modExpected); + CheckBinaryOp(a, NegativeValtype(b), OP_MOD, modExpected); + CheckBinaryOp(NegativeValtype(a), b, OP_MOD, NegativeValtype(modExpected)); + CheckBinaryOp(NegativeValtype(a), NegativeValtype(b), OP_MOD, + NegativeValtype(modExpected)); + + // Div/Mod by zero + for (uint32_t flags : flagset) { + CheckError(flags, {a, {}}, CScript() << OP_DIV, SCRIPT_ERR_DIV_BY_ZERO); + CheckError(flags, {b, {}}, CScript() << OP_DIV, SCRIPT_ERR_DIV_BY_ZERO); + + if (flags & SCRIPT_VERIFY_MINIMALDATA) { + CheckError(flags, {a, {0x00}}, CScript() << OP_DIV, + SCRIPT_ERR_UNKNOWN_ERROR); + CheckError(flags, {a, {0x80}}, CScript() << OP_DIV, + SCRIPT_ERR_UNKNOWN_ERROR); + CheckError(flags, {a, {0x00, 0x00}}, CScript() << OP_DIV, + SCRIPT_ERR_UNKNOWN_ERROR); + CheckError(flags, {a, {0x00, 0x80}}, CScript() << OP_DIV, + SCRIPT_ERR_UNKNOWN_ERROR); + + CheckError(flags, {b, {0x00}}, CScript() << OP_DIV, + SCRIPT_ERR_UNKNOWN_ERROR); + CheckError(flags, {b, {0x80}}, CScript() << OP_DIV, + SCRIPT_ERR_UNKNOWN_ERROR); + CheckError(flags, {b, {0x00, 0x00}}, CScript() << OP_DIV, + SCRIPT_ERR_UNKNOWN_ERROR); + CheckError(flags, {b, {0x00, 0x80}}, CScript() << OP_DIV, + SCRIPT_ERR_UNKNOWN_ERROR); + } else { + CheckError(flags, {a, {0x00}}, CScript() << OP_DIV, + SCRIPT_ERR_DIV_BY_ZERO); + CheckError(flags, {a, {0x80}}, CScript() << OP_DIV, + SCRIPT_ERR_DIV_BY_ZERO); + CheckError(flags, {a, {0x00, 0x00}}, CScript() << OP_DIV, + SCRIPT_ERR_DIV_BY_ZERO); + CheckError(flags, {a, {0x00, 0x80}}, CScript() << OP_DIV, + SCRIPT_ERR_DIV_BY_ZERO); + + CheckError(flags, {b, {0x00}}, CScript() << OP_DIV, + SCRIPT_ERR_DIV_BY_ZERO); + CheckError(flags, {b, {0x80}}, CScript() << OP_DIV, + SCRIPT_ERR_DIV_BY_ZERO); + CheckError(flags, {b, {0x00, 0x00}}, CScript() << OP_DIV, + SCRIPT_ERR_DIV_BY_ZERO); + CheckError(flags, {b, {0x00, 0x80}}, CScript() << OP_DIV, + SCRIPT_ERR_DIV_BY_ZERO); + } + } + + // Division identities + CheckBinaryOp(a, {0x01}, OP_DIV, a); + CheckBinaryOp(a, {0x81}, OP_DIV, NegativeValtype(a)); + CheckBinaryOp(a, a, OP_DIV, {0x01}); + CheckBinaryOp(a, NegativeValtype(a), OP_DIV, {0x81}); + CheckBinaryOp(NegativeValtype(a), a, OP_DIV, {0x81}); + + CheckBinaryOp(b, {0x01}, OP_DIV, b); + CheckBinaryOp(b, {0x81}, OP_DIV, NegativeValtype(b)); + CheckBinaryOp(b, b, OP_DIV, {0x01}); + CheckBinaryOp(b, NegativeValtype(b), OP_DIV, {0x81}); + CheckBinaryOp(NegativeValtype(b), b, OP_DIV, {0x81}); + + // Modulo identities + // a % b % b = a % b + CheckTestResultForAllFlags( + {a, b}, CScript() << OP_MOD << CScriptNum(b, true).getint() << OP_MOD, + {modExpected}); +} + +static void CheckDivModError(const stacktype &original_stack, + ScriptError expected_error) { + CheckOpError(original_stack, OP_DIV, expected_error); + CheckOpError(original_stack, OP_MOD, expected_error); +} + +BOOST_AUTO_TEST_CASE(div_and_mod_opcode_tests) { + CheckDivModError({}, SCRIPT_ERR_INVALID_STACK_OPERATION); + CheckDivModError({{}}, SCRIPT_ERR_INVALID_STACK_OPERATION); + + // CheckOps not valid numbers + CheckDivModError( + {{0x01, 0x02, 0x03, 0x04, 0x05}, {0x01, 0x02, 0x03, 0x04, 0x05}}, + SCRIPT_ERR_UNKNOWN_ERROR); + CheckDivModError({{0x01, 0x02, 0x03, 0x04, 0x05}, {0x01}}, + SCRIPT_ERR_UNKNOWN_ERROR); + CheckDivModError({{0x01, 0x05}, {0x01, 0x02, 0x03, 0x04, 0x05}}, + SCRIPT_ERR_UNKNOWN_ERROR); + + // 0x185377af / 0x85f41b01 = -4 + // 0x185377af % 0x85f41b01 = 0x00830bab + // 408123311 / -99883777 = -4 + // 408123311 % -99883777 = 8588203 + CheckDivMod({0xaf, 0x77, 0x53, 0x18}, {0x01, 0x1b, 0xf4, 0x85}, {0x84}, + {0xab, 0x0b, 0x83, 0x00}); + // 0x185377af / 0x00001b01 = 0xe69d + // 0x185377af % 0x00001b01 = 0x0212 + // 408123311 / 6913 = 59037 + // 408123311 % 6913 = 530 + CheckDivMod({0xaf, 0x77, 0x53, 0x18}, {0x01, 0x1b}, {0x9d, 0xe6, 0x00}, + {0x12, 0x02}); + + // 15/4 = 3 (and negative operands) + CheckDivMod({0x0f}, {0x04}, {0x03}, {0x03}); + // 15000/4 = 3750 (and negative operands) + CheckDivMod({0x98, 0x3a}, {0x04}, {0xa6, 0x0e}, {}); + // 15000/4000 = 3 (and negative operands) + CheckDivMod({0x98, 0x3a}, {0xa0, 0x0f}, {0x03}, {0xb8, 0x0b}); + // 15000000/4000 = 3750 (and negative operands) + CheckDivMod({0xc0, 0xe1, 0xe4, 0x00}, {0xa0, 0x0f}, {0xa6, 0x0e}, {}); + // 15000000/4 = 3750000 (and negative operands) + CheckDivMod({0xc0, 0xe1, 0xe4, 0x00}, {0x04}, {0x70, 0x38, 0x39}, {}); + + // 56488123 % 321 = 148 (and negative operands) + CheckDivMod({0xbb, 0xf0, 0x5d, 0x03}, {0x41, 0x01}, {0x67, 0xaf, 0x02}, + {0x94, 0x00}); + // 56488123 % 3 = 1 (and negative operands) + CheckDivMod({0xbb, 0xf0, 0x5d, 0x03}, {0x03}, {0x3e, 0x50, 0x1f, 0x01}, + {0x01}); + // 56488123 % 564881230 = 56488123 (and negative operands) + CheckDivMod({0xbb, 0xf0, 0x5d, 0x03}, {0x4e, 0x67, 0xab, 0x21}, {}, + {0xbb, 0xf0, 0x5d, 0x03}); +} + BOOST_AUTO_TEST_SUITE_END() diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp --- a/src/test/script_tests.cpp +++ b/src/test/script_tests.cpp @@ -93,6 +93,8 @@ {SCRIPT_ERR_NONCOMPRESSED_PUBKEY, "NONCOMPRESSED_PUBKEY"}, {SCRIPT_ERR_ILLEGAL_FORKID, "ILLEGAL_FORKID"}, {SCRIPT_ERR_MUST_USE_FORKID, "MISSING_FORKID"}, + {SCRIPT_ERR_DIV_BY_ZERO, "DIV_BY_ZERO"}, + {SCRIPT_ERR_MOD_BY_ZERO, "MOD_BY_ZERO"}, }; const char *FormatScriptError(ScriptError_t err) {