Module Name: src
Committed By: rillig
Date: Sun Mar 10 12:50:46 UTC 2024
Modified Files:
src/usr.bin/xlint/lint1: tree.c
Log Message:
lint: split integer overflow check into separate functions
The checks for unsigned and signed integers differ for each operator, so
there's no point having both parts in the same function.
To generate a diff of this commit:
cvs rdiff -u -r1.617 -r1.618 src/usr.bin/xlint/lint1/tree.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/usr.bin/xlint/lint1/tree.c
diff -u src/usr.bin/xlint/lint1/tree.c:1.617 src/usr.bin/xlint/lint1/tree.c:1.618
--- src/usr.bin/xlint/lint1/tree.c:1.617 Sun Mar 10 10:31:29 2024
+++ src/usr.bin/xlint/lint1/tree.c Sun Mar 10 12:50:45 2024
@@ -1,4 +1,4 @@
-/* $NetBSD: tree.c,v 1.617 2024/03/10 10:31:29 rillig Exp $ */
+/* $NetBSD: tree.c,v 1.618 2024/03/10 12:50:45 rillig Exp $ */
/*
* Copyright (c) 1994, 1995 Jochen Pohl
@@ -37,7 +37,7 @@
#include <sys/cdefs.h>
#if defined(__RCSID)
-__RCSID("$NetBSD: tree.c,v 1.617 2024/03/10 10:31:29 rillig Exp $");
+__RCSID("$NetBSD: tree.c,v 1.618 2024/03/10 12:50:45 rillig Exp $");
#endif
#include <float.h>
@@ -787,147 +787,206 @@ build_address(bool sys, tnode_t *tn, boo
tn, NULL);
}
-/*
- * XXX
- * Note: There appear to be a number of bugs in detecting overflow in
- * this function. An audit and a set of proper regression tests are needed.
- * --Perry Metzger, Nov. 16, 2001
- */
-static tnode_t *
-fold_constant_integer(tnode_t *tn)
+static uint64_t
+fold_unsigned_integer(op_t op, uint64_t l, uint64_t r,
+ uint64_t max_value, bool *overflow)
{
-
- lint_assert(has_operands(tn));
- tspec_t t = tn->u.ops.left->tn_type->t_tspec;
- bool utyp = !is_integer(t) || is_uinteger(t);
- int64_t sl = tn->u.ops.left->u.value.u.integer, sr = 0;
- uint64_t ul = sl, ur = 0;
- if (is_binary(tn))
- ur = sr = tn->u.ops.right->u.value.u.integer;
-
- uint64_t mask = value_bits(size_in_bits(t));
- int64_t max_value = (int64_t)(mask >> 1);
- int64_t min_value = -max_value - 1;
- bool ovfl = false;
-
- int64_t si;
- switch (tn->tn_op) {
+ switch (op) {
case COMPL:
- si = ~sl;
- break;
+ return ~l;
case UPLUS:
- si = sl;
- break;
+ return l;
case UMINUS:
- if (utyp)
- si = (int64_t)-ul;
- else {
- ovfl = sl == min_value;
- si = ovfl ? sl : -sl;
- }
- break;
- case MULT:
- if (utyp) {
- si = (int64_t)(ul * ur);
- if (si != (si & (int64_t)mask))
- ovfl = true;
- else if (ul != 0 && si / ul != ur)
- ovfl = true;
- } else {
- uint64_t al = sl >= 0 ? ul : -ul;
- uint64_t ar = sr >= 0 ? ur : -ur;
- bool neg = (sl >= 0) != (sr >= 0);
- uint64_t max_prod = (uint64_t)max_value
- + (neg ? 1 : 0);
- if (al > 0 && ar > max_prod / al) {
- si = (int64_t)(al * ar);
- ovfl = true;
- } else
- si = sl * sr;
- if (msb(si, t) != (msb(sl, t) ^ msb(sr, t)))
- ovfl = true;
- }
- break;
+ return -l;
+ case MULT:;
+ uint64_t mult_result = l * r;
+ if (mult_result != (mult_result & max_value))
+ *overflow = true;
+ else if (l != 0 && mult_result / l != r)
+ *overflow = true;
+ return mult_result;
case DIV:
- if (sr == 0) {
+ if (r == 0) {
/* division by 0 */
error(139);
- si = utyp ? -1 : max_value;
- } else if (!utyp && sl == min_value && sr == -1) {
- ovfl = true;
- si = sl;
+ return max_value;
} else
- si = utyp ? (int64_t)(ul / ur) : sl / sr;
- break;
+ return l / r;
case MOD:
- if (sr == 0) {
+ if (r == 0) {
/* modulus by 0 */
error(140);
- si = 0;
- } else if (!utyp && sl == min_value && sr == -1) {
- ovfl = true;
- si = 0;
+ return 0;
} else
- si = utyp ? (int64_t)(ul % ur) : sl % sr;
- break;
- case PLUS:
- si = (int64_t)(ul + ur);
- if (msb(sl, t) && msb(sr, t) && !msb(si, t))
- ovfl = true;
- if (!utyp && !msb(sl, t) && !msb(sr, t) && msb(si, t))
- ovfl = true;
- break;
- case MINUS:
- si = (int64_t)(ul - ur);
- if (!utyp && msb(sl, t) && !msb(sr, t) && !msb(si, t))
- ovfl = true;
- if (!msb(sl, t) && msb(sr, t) && msb(si, t))
- ovfl = true;
- break;
+ return l % r;
+ case PLUS:;
+ uint64_t plus_result = l + r;
+ uint64_t hi = max_value ^ (max_value >> 1);
+ if (l & hi && r & hi && !(plus_result & hi))
+ *overflow = true;
+ return plus_result;
+ case MINUS:;
+ uint64_t minus_result = l - r;
+ hi = max_value ^ (max_value >> 1);
+ if (!(l & hi) && r & hi && minus_result & hi)
+ *overflow = true;
+ return minus_result;
case SHL:
/* TODO: warn about out-of-bounds 'sr'. */
- /* TODO: warn about overflow in signed '<<'. */
- si = utyp ? (int64_t)(ul << (sr & 63)) : sl << (sr & 63);
- break;
+ return l << (r & 63);
case SHR:
- /*
- * The sign must be explicitly extended because shifts of
- * signed values are implementation dependent.
- */
/* TODO: warn about out-of-bounds 'sr'. */
- si = (int64_t)(ul >> (sr & 63));
- si = convert_integer(si, t, size_in_bits(t) - (int)sr);
- break;
+ return l >> (r & 63);
case LT:
- si = (utyp ? ul < ur : sl < sr) ? 1 : 0;
- break;
+ return l < r ? 1 : 0;
case LE:
- si = (utyp ? ul <= ur : sl <= sr) ? 1 : 0;
- break;
+ return l <= r ? 1 : 0;
case GT:
- si = (utyp ? ul > ur : sl > sr) ? 1 : 0;
- break;
+ return l > r ? 1 : 0;
case GE:
- si = (utyp ? ul >= ur : sl >= sr) ? 1 : 0;
- break;
+ return l >= r ? 1 : 0;
case EQ:
- si = (utyp ? ul == ur : sl == sr) ? 1 : 0;
- break;
+ return l == r ? 1 : 0;
case NE:
- si = (utyp ? ul != ur : sl != sr) ? 1 : 0;
- break;
+ return l != r ? 1 : 0;
case BITAND:
- si = utyp ? (int64_t)(ul & ur) : sl & sr;
- break;
+ return l & r;
case BITXOR:
- si = utyp ? (int64_t)(ul ^ ur) : sl ^ sr;
- break;
+ return l ^ r;
case BITOR:
- si = utyp ? (int64_t)(ul | ur) : sl | sr;
- break;
+ return l | r;
+ default:
+ lint_assert(/*CONSTCOND*/false);
+ }
+ /* NOTREACHED */
+}
+
+static int64_t
+fold_signed_integer(op_t op, int64_t l, int64_t r,
+ int64_t min_value, int64_t max_value, bool *overflow)
+{
+ switch (op) {
+ case COMPL:
+ return ~l;
+ case UPLUS:
+ return l;
+ case UMINUS:
+ *overflow = l == min_value;
+ return *overflow ? l : -l;
+ case MULT:;
+ uint64_t al = l >= 0 ? (uint64_t)l : -(uint64_t)l;
+ uint64_t ar = r >= 0 ? (uint64_t)r : -(uint64_t)r;
+ bool neg = (l >= 0) != (r >= 0);
+ uint64_t max_prod = (uint64_t)max_value + (neg ? 1 : 0);
+ if (al > 0 && ar > max_prod / al) {
+ *overflow = true;
+ return (int64_t)(al * ar);
+ }
+ uint64_t mult_result = l * r;
+ uint64_t hi = (uint64_t)max_value + 1;
+ // FIXME: Overflow can also happen in other bits.
+ if ((mult_result & hi) != ((l & hi) ^ (r & hi)))
+ *overflow = true;
+ return (int64_t)mult_result;
+ case DIV:
+ if (r == 0) {
+ /* division by 0 */
+ error(139);
+ return max_value;
+ }
+ if (l == min_value && r == -1) {
+ *overflow = true;
+ return l;
+ }
+ return l / r;
+ case MOD:
+ if (r == 0) {
+ /* modulus by 0 */
+ error(140);
+ return 0;
+ }
+ if (l == min_value && r == -1) {
+ *overflow = true;
+ return 0;
+ }
+ return l % r;
+ case PLUS:;
+ uint64_t plus_result = (uint64_t)l + (uint64_t)r;
+ hi = (uint64_t)max_value + 1;
+
+ if (l & hi && r & hi && !(plus_result & hi))
+ *overflow = true;
+ if (!(l & hi) && !(r & hi) && plus_result & hi)
+ *overflow = true;
+ return (int64_t)plus_result;
+ case MINUS:;
+ uint64_t minus_result = (uint64_t)l - (uint64_t)r;
+ hi = (uint64_t)max_value + 1;
+ if (l & hi && !(r & hi) && !(minus_result & hi))
+ *overflow = true;
+ if (!(l & hi) && r & hi && minus_result & hi)
+ *overflow = true;
+ return (int64_t)minus_result;
+ case SHL:
+ /* TODO: warn about out-of-bounds 'sr'. */
+ /* TODO: warn about overflow in signed '<<'. */
+ return l << (r & 63);
+ case SHR:;
+ uint64_t shr_result = (uint64_t)l >> (r & 63);
+ if (shr_result & min_value)
+ shr_result |= min_value;
+ return (int64_t)shr_result;
+ case LT:
+ return l < r ? 1 : 0;
+ case LE:
+ return l <= r ? 1 : 0;
+ case GT:
+ return l > r ? 1 : 0;
+ case GE:
+ return l >= r ? 1 : 0;
+ case EQ:
+ return l == r ? 1 : 0;
+ case NE:
+ return l != r ? 1 : 0;
+ case BITAND:
+ return l & r;
+ case BITXOR:
+ return l ^ r;
+ case BITOR:
+ return l | r;
default:
lint_assert(/*CONSTCOND*/false);
}
+ /* NOTREACHED */
+}
+
+/*
+ * XXX
+ * Note: There appear to be a number of bugs in detecting overflow in
+ * this function. An audit and a set of proper regression tests are needed.
+ * --Perry Metzger, Nov. 16, 2001
+ */
+static tnode_t *
+fold_constant_integer(tnode_t *tn)
+{
+
+ lint_assert(has_operands(tn));
+ tspec_t t = tn->u.ops.left->tn_type->t_tspec;
+ bool utyp = !is_integer(t) || is_uinteger(t);
+ int64_t sl = tn->u.ops.left->u.value.u.integer, sr = 0;
+ uint64_t ul = sl, ur = 0;
+ if (is_binary(tn))
+ ur = sr = tn->u.ops.right->u.value.u.integer;
+
+ uint64_t mask = value_bits(size_in_bits(t));
+ int64_t max_value = (int64_t)(mask >> 1);
+ int64_t min_value = -max_value - 1;
+ bool ovfl = false;
+
+ int64_t si = utyp
+ ? (int64_t)fold_unsigned_integer(tn->tn_op, ul, ur, mask, &ovfl)
+ : fold_signed_integer(tn->tn_op, sl, sr, min_value, max_value,
+ &ovfl);
/* XXX: The overflow check does not work for 64-bit integers. */
if (ovfl ||
