py: This time, real proper overflow checking of small int power.
Previous overflow test was inadequate.
diff --git a/py/compile.c b/py/compile.c
index 3273abe..44b37b9 100644
--- a/py/compile.c
+++ b/py/compile.c
@@ -17,7 +17,7 @@
#include "obj.h"
#include "compile.h"
#include "runtime.h"
-#include "intdivmod.h"
+#include "smallint.h"
// TODO need to mangle __attr names
@@ -143,10 +143,10 @@
} else if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[1], MP_TOKEN_OP_SLASH)) {
; // pass
} else if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[1], MP_TOKEN_OP_PERCENT)) {
- pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, python_modulo(arg0, arg1));
+ pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, mp_small_int_modulo(arg0, arg1));
} else if (MP_PARSE_NODE_IS_TOKEN_KIND(pns->nodes[1], MP_TOKEN_OP_DBL_SLASH)) {
if (arg1 != 0) {
- pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, python_floor_divide(arg0, arg1));
+ pn = mp_parse_node_new_leaf(MP_PARSE_NODE_SMALL_INT, mp_small_int_floor_divide(arg0, arg1));
}
} else {
// shouldn't happen
diff --git a/py/intdivmod.c b/py/intdivmod.c
deleted file mode 100644
index 4cb363b..0000000
--- a/py/intdivmod.c
+++ /dev/null
@@ -1,24 +0,0 @@
-#include "mpconfig.h"
-
-machine_int_t python_modulo(machine_int_t dividend, machine_int_t divisor) {
- machine_int_t lsign = (dividend >= 0) ? 1 :-1;
- machine_int_t rsign = (divisor >= 0) ? 1 :-1;
- dividend %= divisor;
- if (lsign != rsign) {
- dividend += divisor;
- }
- return dividend;
-}
-
-
-machine_int_t python_floor_divide(machine_int_t num, machine_int_t denom) {
- machine_int_t lsign = num > 0 ? 1 : -1;
- machine_int_t rsign = denom > 0 ? 1 : -1;
- if (lsign == -1) {num *= -1;}
- if (rsign == -1) {denom *= -1;}
- if (lsign != rsign){
- return - ( num + denom - 1) / denom;
- } else {
- return num / denom;
- }
-}
diff --git a/py/intdivmod.h b/py/intdivmod.h
deleted file mode 100644
index 7716bd2..0000000
--- a/py/intdivmod.h
+++ /dev/null
@@ -1,4 +0,0 @@
-// Functions for integer modulo and floor division
-
-machine_int_t python_modulo(machine_int_t dividend, machine_int_t divisor);
-machine_int_t python_floor_divide(machine_int_t num, machine_int_t denom);
diff --git a/py/objint_mpz.c b/py/objint_mpz.c
index 25a069c..d338428 100644
--- a/py/objint_mpz.c
+++ b/py/objint_mpz.c
@@ -113,7 +113,7 @@
case MP_BINARY_OP_INPLACE_FLOOR_DIVIDE: {
mpz_t rem; mpz_init_zero(&rem);
mpz_divmod_inpl(&res->mpz, &rem, zlhs, zrhs);
- if (zlhs->neg != zrhs->neg) {
+ if (zlhs->neg != zrhs->neg) {
if (!mpz_is_zero(&rem)) {
mpz_t mpzone; mpz_init_from_int(&mpzone, -1);
mpz_add_inpl(&res->mpz, &res->mpz, &mpzone);
@@ -127,8 +127,8 @@
mpz_t quo; mpz_init_zero(&quo);
mpz_divmod_inpl(&quo, &res->mpz, zlhs, zrhs);
mpz_deinit(&quo);
- // Check signs and do Python style modulo
- if (zlhs->neg != zrhs->neg) {
+ // Check signs and do Python style modulo
+ if (zlhs->neg != zrhs->neg) {
mpz_add_inpl(&res->mpz, &res->mpz, zrhs);
}
break;
diff --git a/py/py.mk b/py/py.mk
index 0590292..a089973 100644
--- a/py/py.mk
+++ b/py/py.mk
@@ -84,7 +84,7 @@
vm.o \
showbc.o \
repl.o \
- intdivmod.o \
+ smallint.o \
pfenv.o \
# prepend the build destination prefix to the py object files
diff --git a/py/runtime.c b/py/runtime.c
index a5afe0e..a5f45a2 100644
--- a/py/runtime.c
+++ b/py/runtime.c
@@ -16,7 +16,7 @@
#include "builtin.h"
#include "builtintables.h"
#include "bc.h"
-#include "intdivmod.h"
+#include "smallint.h"
#include "objgenerator.h"
#if 0 // print debugging info
@@ -289,7 +289,7 @@
// If long long type exists and is larger than machine_int_t, then
// we can use the following code to perform overflow-checked multiplication.
- // Otherwise (eg in x64 case) we must use the branching code below.
+ // Otherwise (eg in x64 case) we must use mp_small_int_mul_overflow.
#if 0
// compute result using long long precision
long long res = (long long)lhs_val * (long long)rhs_val;
@@ -302,36 +302,14 @@
}
#endif
- if (lhs_val > 0) { // lhs_val is positive
- if (rhs_val > 0) { // lhs_val and rhs_val are positive
- if (lhs_val > (MP_SMALL_INT_MAX / rhs_val)) {
- goto mul_overflow;
- }
- } else { // lhs_val positive, rhs_val nonpositive
- if (rhs_val < (MP_SMALL_INT_MIN / lhs_val)) {
- goto mul_overflow;
- }
- } // lhs_val positive, rhs_val nonpositive
- } else { // lhs_val is nonpositive
- if (rhs_val > 0) { // lhs_val is nonpositive, rhs_val is positive
- if (lhs_val < (MP_SMALL_INT_MIN / rhs_val)) {
- goto mul_overflow;
- }
- } else { // lhs_val and rhs_val are nonpositive
- if (lhs_val != 0 && rhs_val < (MP_SMALL_INT_MAX / lhs_val)) {
- goto mul_overflow;
- }
- } // End if lhs_val and rhs_val are nonpositive
- } // End if lhs_val is nonpositive
-
- // use standard precision
- return MP_OBJ_NEW_SMALL_INT(lhs_val * rhs_val);
-
- mul_overflow:
- // use higher precision
- lhs = mp_obj_new_int_from_ll(lhs_val);
- goto generic_binary_op;
-
+ if (mp_small_int_mul_overflow(lhs_val, rhs_val)) {
+ // use higher precision
+ lhs = mp_obj_new_int_from_ll(lhs_val);
+ goto generic_binary_op;
+ } else {
+ // use standard precision
+ return MP_OBJ_NEW_SMALL_INT(lhs_val * rhs_val);
+ }
break;
}
case MP_BINARY_OP_FLOOR_DIVIDE:
@@ -339,7 +317,7 @@
if (rhs_val == 0) {
goto zero_division;
}
- lhs_val = python_floor_divide(lhs_val, rhs_val);
+ lhs_val = mp_small_int_floor_divide(lhs_val, rhs_val);
break;
#if MICROPY_ENABLE_FLOAT
@@ -352,11 +330,11 @@
#endif
case MP_BINARY_OP_MODULO:
- case MP_BINARY_OP_INPLACE_MODULO:
- {
- lhs_val = python_modulo(lhs_val, rhs_val);
+ case MP_BINARY_OP_INPLACE_MODULO: {
+ lhs_val = mp_small_int_modulo(lhs_val, rhs_val);
break;
}
+
case MP_BINARY_OP_POWER:
case MP_BINARY_OP_INPLACE_POWER:
if (rhs_val < 0) {
@@ -370,21 +348,19 @@
machine_int_t ans = 1;
while (rhs_val > 0) {
if (rhs_val & 1) {
- machine_int_t old = ans;
- ans *= lhs_val;
- if (ans < old) {
+ if (mp_small_int_mul_overflow(ans, lhs_val)) {
goto power_overflow;
}
+ ans *= lhs_val;
}
if (rhs_val == 1) {
break;
}
rhs_val /= 2;
- machine_int_t old = lhs_val;
- lhs_val *= lhs_val;
- if (lhs_val < old) {
+ if (mp_small_int_mul_overflow(lhs_val, lhs_val)) {
goto power_overflow;
}
+ lhs_val *= lhs_val;
}
lhs_val = ans;
}
diff --git a/py/smallint.c b/py/smallint.c
new file mode 100644
index 0000000..ac0cf2f
--- /dev/null
+++ b/py/smallint.c
@@ -0,0 +1,53 @@
+#include "misc.h"
+#include "mpconfig.h"
+#include "qstr.h"
+#include "obj.h"
+
+bool mp_small_int_mul_overflow(machine_int_t x, machine_int_t y) {
+ // Check for multiply overflow; see CERT INT32-C
+ if (x > 0) { // x is positive
+ if (y > 0) { // x and y are positive
+ if (x > (MP_SMALL_INT_MAX / y)) {
+ return true;
+ }
+ } else { // x positive, y nonpositive
+ if (y < (MP_SMALL_INT_MIN / x)) {
+ return true;
+ }
+ } // x positive, y nonpositive
+ } else { // x is nonpositive
+ if (y > 0) { // x is nonpositive, y is positive
+ if (x < (MP_SMALL_INT_MIN / y)) {
+ return true;
+ }
+ } else { // x and y are nonpositive
+ if (x != 0 && y < (MP_SMALL_INT_MAX / x)) {
+ return true;
+ }
+ } // End if x and y are nonpositive
+ } // End if x is nonpositive
+ return false;
+}
+
+machine_int_t mp_small_int_modulo(machine_int_t dividend, machine_int_t divisor) {
+ machine_int_t lsign = (dividend >= 0) ? 1 :-1;
+ machine_int_t rsign = (divisor >= 0) ? 1 :-1;
+ dividend %= divisor;
+ if (lsign != rsign) {
+ dividend += divisor;
+ }
+ return dividend;
+}
+
+
+machine_int_t mp_small_int_floor_divide(machine_int_t num, machine_int_t denom) {
+ machine_int_t lsign = num > 0 ? 1 : -1;
+ machine_int_t rsign = denom > 0 ? 1 : -1;
+ if (lsign == -1) {num *= -1;}
+ if (rsign == -1) {denom *= -1;}
+ if (lsign != rsign){
+ return - ( num + denom - 1) / denom;
+ } else {
+ return num / denom;
+ }
+}
diff --git a/py/smallint.h b/py/smallint.h
new file mode 100644
index 0000000..14234fa
--- /dev/null
+++ b/py/smallint.h
@@ -0,0 +1,5 @@
+// Functions for small integer arithmetic
+
+bool mp_small_int_mul_overflow(machine_int_t x, machine_int_t y);
+machine_int_t mp_small_int_modulo(machine_int_t dividend, machine_int_t divisor);
+machine_int_t mp_small_int_floor_divide(machine_int_t num, machine_int_t denom);