ref: ac6232bc87d0855337dac0efb1e2f8283a588798
parent: b16ec83a33f52e44a72bd464aa08128f44e915d4
parent: b11d121c485014640011d682d4284f3af8ea28ad
author: Eldred Habert <eldredhabert0@gmail.com>
date: Sun Feb 2 22:49:38 EST 2020
Merge pull request #473 from ISSOtm/shift_ub Remove undefined behavior from shifts
--- a/include/asm/warning.h
+++ b/include/asm/warning.h
@@ -20,6 +20,7 @@
WARNING_OBSOLETE,
WARNING_SHIFT,
WARNING_USER,
+ WARNING_SHIFT_AMOUNT,
NB_WARNINGS,
--- a/src/asm/constexpr.c
+++ b/src/asm/constexpr.c
@@ -205,28 +205,52 @@
result = value1 & value2;
break;
case T_OP_SHL:
- if (value1 < 0)
- warning(WARNING_SHIFT, "Left shift of negative value: %d",
- value1);
-
- if (value2 < 0)
- fatalerror("Shift by negative value: %d",- value2);
- else if (value2 >= 32)
- fatalerror("Shift by too big value: %d",- value2);
-
- result = (uint32_t)value1 << value2;
- break;
case T_OP_SHR:
if (value2 < 0)
- fatalerror("Shift by negative value: %d",- value2);
- else if (value2 >= 32)
- fatalerror("Shift by too big value: %d",- value2);
+ warning(WARNING_SHIFT_AMOUNT, "Shifting %s by negative amount %d",
+ op == T_OP_SHL ? "left" : "right",
+ value2);
+ if (op == T_OP_SHR) {+ value2 = -value2; /* Right shift == neg left */
- result = value1 >> value2;
+ if (value1 < 0)
+ warning(WARNING_SHIFT, "Shifting negative value %d",
+ value1);
+ }
+
+ if (value2 >= 0) {+ // Shift left
+ if (value2 >= 32) {+ warning(WARNING_SHIFT_AMOUNT, "Shifting left by large amount %d",
+ value2);
+ result = 0;
+ } else {+ /*
+ * Use unsigned to force a bitwise shift
+ * Casting back is OK because the types
+ * implement two's complement behavior
+ */
+ result = (uint32_t)value1 << value2;
+ }
+ } else {+ // Shift right
+ value2 = -value2;
+ if (value2 >= 32) {+ warning(WARNING_SHIFT_AMOUNT, "Shifting right by large amount %d",
+ value2);
+ result = value1 < 0 ? -1 : 0;
+ } else if (value1 >= 0) {+ result = value1 >> value2;
+ } else {+ /*
+ * The C standard leaves shifting right
+ * negative values undefined, so use a
+ * left shift manually sign-extended
+ */
+ result = (uint32_t)value1 >> value2 |
+ -((uint32_t)1 << (32 - value2));
+ }
+ }
break;
case T_OP_MUL:
result = (uint32_t)value1 * (uint32_t)value2;
--- a/src/asm/rpn.c
+++ b/src/asm/rpn.c
@@ -409,6 +409,48 @@
expr->nRPNPatchSize++;
}
+static int32_t shift(int32_t shiftee, int32_t amount)
+{+ if (shiftee < 0)
+ warning(WARNING_SHIFT, "Shifting negative value %d", shiftee);
+
+ if (amount >= 0) {+ // Left shift
+ if (amount >= 32) {+ warning(WARNING_SHIFT_AMOUNT, "Shifting left by large amount %d",
+ amount);
+ return 0;
+
+ } else {+ /*
+ * Use unsigned to force a bitwise shift
+ * Casting back is OK because the types implement two's
+ * complement behavior
+ */
+ return (uint32_t)shiftee << amount;
+ }
+ } else {+ // Right shift
+ amount = -amount;
+ if (amount >= 32) {+ warning(WARNING_SHIFT_AMOUNT, "Shifting right by large amount %d",
+ amount);
+ return shiftee < 0 ? -1 : 0;
+
+ } else if (shiftee >= 0) {+ return shiftee >> amount;
+
+ } else {+ /*
+ * The C standard leaves shifting right negative values
+ * undefined, so use a left shift manually sign-extended
+ */
+ return (uint32_t)shiftee >> amount
+ | -((uint32_t)1 << (32 - amount));
+ }
+ }
+}
+
void rpn_SHL(struct Expression *expr, const struct Expression *src1,
const struct Expression *src2)
{@@ -415,16 +457,11 @@
mergetwoexpressions(expr, src1, src2);
if (!expr->isReloc) {- if (src1->nVal < 0)
- warning(WARNING_SHIFT, "Left shift of negative value: %d",
- src1->nVal);
-
if (src2->nVal < 0)
- fatalerror("Shift by negative value: %d", src2->nVal);- else if (src2->nVal >= 32)
- fatalerror("Shift by too big value: %d", src2->nVal);+ warning(WARNING_SHIFT_AMOUNT, "Shifting left by negative value: %d",
+ src2->nVal);
- expr->nVal = ((uint32_t)src1->nVal << src2->nVal);
+ expr->nVal = shift(src1->nVal, src2->nVal);
}
pushbyte(expr, RPN_SHL);
@@ -438,11 +475,10 @@
if (!expr->isReloc) {if (src2->nVal < 0)
- fatalerror("Shift by negative value: %d", src2->nVal);- else if (src2->nVal >= 32)
- fatalerror("Shift by too big value: %d", src2->nVal);+ warning(WARNING_SHIFT_AMOUNT, "Shifting right by negative value: %d",
+ src2->nVal);
- expr->nVal = (src1->nVal >> src2->nVal);
+ expr->nVal = shift(src1->nVal, -src2->nVal);
}
pushbyte(expr, RPN_SHR);
--- a/src/asm/warning.c
+++ b/src/asm/warning.c
@@ -36,6 +36,7 @@
WARNING_DISABLED, /* Obsolete things */
WARNING_DISABLED, /* Shifting undefined behavior */
WARNING_ENABLED, /* User warnings */
+ WARNING_DISABLED, /* Strange shift amount */
};
static enum WarningState warningStates[NB_WARNINGS];
@@ -70,6 +71,7 @@
"obsolete",
"shift",
"user",
+ "shift-amount",
/* Meta warnings */
"all",
@@ -106,6 +108,7 @@
WARNING_OBSOLETE,
WARNING_SHIFT,
WARNING_USER,
+ WARNING_SHIFT_AMOUNT,
META_WARNING_DONE
};
--- a/src/link/patch.c
+++ b/src/link/patch.c
@@ -18,6 +18,47 @@
#include "extern/err.h"
+static int32_t asl(int32_t value, int32_t shiftamt); // Forward decl for below
+static int32_t asr(int32_t value, int32_t shiftamt)
+{+ uint32_t uvalue = value;
+
+ // Get the easy cases out of the way
+ if (shiftamt == 0)
+ return value;
+ if (value == 0 || shiftamt <= -32)
+ return 0;
+ if (shiftamt > 31)
+ return (value < 0) ? -1 : 0;
+ if (shiftamt < 0)
+ return asl(value, -shiftamt);
+ if (value > 0)
+ return uvalue >> shiftamt;
+
+ {+ // Calculate an OR mask for sign extension
+ // 1->0x80000000, 2->0xC0000000, ..., 31->0xFFFFFFFE
+ uint32_t shiftamt_high_bits = -((uint32_t)1 << (32 - shiftamt));
+
+ return (uvalue >> shiftamt) | shiftamt_high_bits;
+ }
+}
+
+static int32_t asl(int32_t value, int32_t shiftamt)
+{+ // Repeat the easy cases here to avoid INT_MIN funny business
+ if (shiftamt == 0)
+ return value;
+ if (value == 0 || shiftamt >= 32)
+ return 0;
+ if (shiftamt < -31)
+ return (value < 0) ? -1 : 0;
+ if (shiftamt < 0)
+ return asr(value, -shiftamt);
+
+ return (uint32_t)value << shiftamt;
+}
+
/* This is an "empty"-type stack */
struct RPNStack {int32_t *buf;
@@ -182,14 +223,13 @@
value = popRPN() <= value;
break;
- /* FIXME: sanitize shifts */
case RPN_SHL:
value = popRPN();
- value = popRPN() << value;
+ value = asl(popRPN(), value);
break;
case RPN_SHR:
value = popRPN();
- value = popRPN() >> value;
+ value = asr(popRPN(), value);
break;
case RPN_BANK_SYM:
--- a/test/asm/overflow.err
+++ b/test/asm/overflow.err
@@ -2,10 +2,8 @@
Division of min value by -1
warning: overflow.asm(25): [-Wdiv]
Division of min value by -1
-warning: overflow.asm(34): [-Wshift]
- Left shift of negative value: -1
warning: overflow.asm(35): [-Wshift]
- Left shift of negative value: -1
+ Shifting negative value -1
warning: overflow.asm(39): [-Wlarge-constant]
Integer constant '4294967296' is too large
warning: overflow.asm(42): [-Wlarge-constant]
--- /dev/null
+++ b/test/asm/shift.asm
@@ -1,0 +1,27 @@
+test: macro
+ ; Test the rpn system, as well as the linker...
+ dl \1 + zero
+
+ ; ...as well as the constexpr system
+result\@ equ \1
+ printt "\1 = {result\@}\n"+endm
+
+section "test", ROM0[0]
+
+ test 1 << 1
+ test 1 << 32
+ test 1 << 9001
+ test -1 << 1
+ test -1 << 32
+ test -1 << -9001
+
+ test -1 >> 1
+ test -1 >> 32
+ test -1 >> 9001
+ test -4 >> 1
+ test -4 >> 2
+ test -1 >> -9001
+
+SECTION "Zero", ROM0[0]
+zero:
--- /dev/null
+++ b/test/asm/shift.err
@@ -1,0 +1,66 @@
+warning: shift.asm(13) -> shift.asm::test(3): [-Wshift-amount]
+ Shifting left by large amount 32
+warning: shift.asm(13) -> shift.asm::test(6): [-Wshift-amount]
+ Shifting left by large amount 32
+warning: shift.asm(14) -> shift.asm::test(3): [-Wshift-amount]
+ Shifting left by large amount 9001
+warning: shift.asm(14) -> shift.asm::test(6): [-Wshift-amount]
+ Shifting left by large amount 9001
+warning: shift.asm(15) -> shift.asm::test(3): [-Wshift]
+ Shifting negative value -1
+warning: shift.asm(16) -> shift.asm::test(3): [-Wshift]
+ Shifting negative value -1
+warning: shift.asm(16) -> shift.asm::test(3): [-Wshift-amount]
+ Shifting left by large amount 32
+warning: shift.asm(16) -> shift.asm::test(6): [-Wshift-amount]
+ Shifting left by large amount 32
+warning: shift.asm(17) -> shift.asm::test(3): [-Wshift-amount]
+ Shifting left by negative value: -9001
+warning: shift.asm(17) -> shift.asm::test(3): [-Wshift]
+ Shifting negative value -1
+warning: shift.asm(17) -> shift.asm::test(3): [-Wshift-amount]
+ Shifting right by large amount 9001
+warning: shift.asm(17) -> shift.asm::test(6): [-Wshift-amount]
+ Shifting left by negative amount -9001
+warning: shift.asm(17) -> shift.asm::test(6): [-Wshift-amount]
+ Shifting right by large amount 9001
+warning: shift.asm(19) -> shift.asm::test(3): [-Wshift]
+ Shifting negative value -1
+warning: shift.asm(19) -> shift.asm::test(6): [-Wshift]
+ Shifting negative value -1
+warning: shift.asm(20) -> shift.asm::test(3): [-Wshift]
+ Shifting negative value -1
+warning: shift.asm(20) -> shift.asm::test(3): [-Wshift-amount]
+ Shifting right by large amount 32
+warning: shift.asm(20) -> shift.asm::test(6): [-Wshift]
+ Shifting negative value -1
+warning: shift.asm(20) -> shift.asm::test(6): [-Wshift-amount]
+ Shifting right by large amount 32
+warning: shift.asm(21) -> shift.asm::test(3): [-Wshift]
+ Shifting negative value -1
+warning: shift.asm(21) -> shift.asm::test(3): [-Wshift-amount]
+ Shifting right by large amount 9001
+warning: shift.asm(21) -> shift.asm::test(6): [-Wshift]
+ Shifting negative value -1
+warning: shift.asm(21) -> shift.asm::test(6): [-Wshift-amount]
+ Shifting right by large amount 9001
+warning: shift.asm(22) -> shift.asm::test(3): [-Wshift]
+ Shifting negative value -4
+warning: shift.asm(22) -> shift.asm::test(6): [-Wshift]
+ Shifting negative value -4
+warning: shift.asm(23) -> shift.asm::test(3): [-Wshift]
+ Shifting negative value -4
+warning: shift.asm(23) -> shift.asm::test(6): [-Wshift]
+ Shifting negative value -4
+warning: shift.asm(24) -> shift.asm::test(3): [-Wshift-amount]
+ Shifting right by negative value: -9001
+warning: shift.asm(24) -> shift.asm::test(3): [-Wshift]
+ Shifting negative value -1
+warning: shift.asm(24) -> shift.asm::test(3): [-Wshift-amount]
+ Shifting left by large amount 9001
+warning: shift.asm(24) -> shift.asm::test(6): [-Wshift-amount]
+ Shifting right by negative amount -9001
+warning: shift.asm(24) -> shift.asm::test(6): [-Wshift]
+ Shifting negative value -1
+warning: shift.asm(24) -> shift.asm::test(6): [-Wshift-amount]
+ Shifting left by large amount 9001
--- /dev/null
+++ b/test/asm/shift.out
@@ -1,0 +1,12 @@
+1 << 1 = $2
+1 << 32 = $0
+1 << 9001 = $0
+-1 << 1 = $FFFFFFFE
+-1 << 32 = $0
+-1 << -9001 = $FFFFFFFF
+-1 >> 1 = $FFFFFFFF
+-1 >> 32 = $FFFFFFFF
+-1 >> 9001 = $FFFFFFFF
+-4 >> 1 = $FFFFFFFE
+-4 >> 2 = $FFFFFFFF
+-1 >> -9001 = $0
binary files /dev/null b/test/asm/shift.out.bin differ