2005-09-10 Frank Ch. Eigler <fche@elastic.org>

	* arith.c: Add some comments explaining why the last change works.

2 files changed, 175 insertions, 159 deletions

diff --git a/runtime/ChangeLog b/runtime/ChangeLog
index b0eebe87..b1e9a3c2 100644
--- a/runtime/ChangeLog
+++ b/runtime/ChangeLog
@@ -1,3 +1,7 @@
+2005-09-10  Frank Ch. Eigler  <fche@elastic.org>
+
+	* arith.c: Add some comments explaining why the last change works.
+
 2005-09-09  Martin Hunt  <hunt@redhat.com>
 
 	* stat-common.c (_stp_stat_print_valtype): Use _stp_div64().
diff --git a/runtime/arith.c b/runtime/arith.c
index 19b22df4..452c9434 100644
--- a/runtime/arith.c
+++ b/runtime/arith.c
@@ -1,7 +1,7 @@
 /* -*- linux-c -*- */
 /* Math functions
  * Copyright (C) 2005 Red Hat Inc.
- * Portions (C)  Free Software Foundation, Inc.
+ * Portions (C) Free Software Foundation, Inc.
  *
  * This file is part of systemtap, and is free software.  You can
  * redistribute it and/or modify it under the terms of the GNU General
@@ -31,24 +31,31 @@ long long _mod64 (long long u, long long v);
 int64_t _stp_div64 (const char **error, int64_t x, int64_t y)
 {
 #ifdef __LP64__
-	if (unlikely (y == 0 || (x == LONG_MIN && y == -1))) {	
-		if (error) *error = "divisor out of range";
-		return 0;
-	}
-	return x/y;
+  if (unlikely (y == 0 || (x == LONG_MIN && y == -1))) {	
+    if (error) *error = "divisor out of range";
+    return 0;
+  }
+  return x/y;
 #else
-	if (likely ((x > LONG_MIN && x < LONG_MAX) && (y > LONG_MIN && y < LONG_MAX))) {
-		long xx = (long) x;
-		long yy = (long) y;
+  // Note use of ">" and "<" here instead of "<=" and ">=".
+  // This passes the potentially problematic division overflow
+  // case of 32-bit LONG_MIN divided by -1 over to the _div64
+  // case.
+  if (likely ((x > LONG_MIN && x < LONG_MAX) &&
+	      (y > LONG_MIN && y < LONG_MAX))) {
+    long xx = (long) x;
+    long yy = (long) y;
 
-		// check for division-by-zero
-		if (unlikely (yy == 0 )) {
-			if (error) *error = "division by 0";
-			return 0;
-		}
-		return xx / yy;
-	} else
-		return _div64 (x, y);
+    // check for division-by-zero
+    if (unlikely (yy == 0)) {
+      if (error) *error = "division by 0";
+      return 0;
+    }
+    return xx / yy;
+  } else
+    // Note that the 64-bit LONG_MIN divided by -1 case is
+    // *passed* by the libgcc code without overflow indication.
+    return _div64 (x, y);
 #endif
 }
 
@@ -59,52 +66,57 @@ int64_t _stp_div64 (const char **error, int64_t x, int64_t y)
 int64_t _stp_mod64 (const char **error, int64_t x, int64_t y)
 {
 #ifdef __LP64__
-	if (unlikely (y == 0 || (x == LONG_MIN && y == -1))) {	
-		if (error) *error = "divisor out of range";
-		return 0;
-	}
-	return x%y;
+  // XXX: is the LONG_MIN%-1 case interesting?
+  if (unlikely (y == 0 || (x == LONG_MIN && y == -1))) {	
+    if (error) *error = "divisor out of range";
+    return 0;
+  }
+  return x%y;
 
 #else
+  // Note again ">" and "<" here instead of "<=" and ">=".
+  // The implications are not clear here since anything modulo +-1 is 0.
+  if (likely ((x > LONG_MIN && x < LONG_MAX) &&
+	      (y > LONG_MIN && y < LONG_MAX))) {
+    long xx = (long) x;
+    long yy = (long) y;
 
-	if (likely ((x > LONG_MIN && x < LONG_MAX) && (y > LONG_MIN && y < LONG_MAX))) {
-		long xx = (long) x;
-		long yy = (long) y;
-
-		// check for division-by-zero
-		if (unlikely (yy == 0)) {
-			if (error) *error = "division by 0";
-			return 0;
-		}
-		return xx % yy;
-	} else
-		return _mod64 (x,y);
+    // check for division-by-zero
+    if (unlikely (yy == 0)) {
+      if (error) *error = "division by 0";
+      return 0;
+    }
+    return xx % yy;
+  } else
+    return _mod64 (x,y);
 #endif
 }
 
+
 #ifndef _STP_TEST_
 /** Return a random integer between -n and n.
  * @param n how far from zero to go.  Make it positive but less than a million or so.
  */
 int _stp_random_pm (int n)
 {
-	static unsigned long seed;
-	static int initialized_p = 0;
+  static unsigned long seed;
+  static int initialized_p = 0;
 	
-	if (unlikely (! initialized_p)) {
-		seed = (unsigned long) jiffies;
-		initialized_p = 1;
-	}
+  if (unlikely (! initialized_p)) {
+    seed = (unsigned long) jiffies;
+    initialized_p = 1;
+  }
 	
-	/* from glibc rand man page */
-	seed = seed * 1103515245 + 12345;
+  /* from glibc rand man page */
+  seed = seed * 1103515245 + 12345;
 	
-	return (seed % (2*n+1)-n);
+  return (seed % (2*n+1)-n);
 }
 #endif /* _STP_TEST_ */
 
-#ifdef __i386__
 
+
+#ifdef __i386__
 /* 64-bit division functions extracted from libgcc */
 typedef long long DWtype;
 typedef unsigned long long UDWtype;
@@ -163,150 +175,150 @@ typedef union
 
 inline UDWtype _stp_udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp)
 {
-	const DWunion nn = {.ll = n};
-	const DWunion dd = {.ll = d};
-	DWunion ww,rr;
-	UWtype d0, d1, n0, n1, n2;
-	UWtype q0, q1;
-	UWtype b, bm;
+  const DWunion nn = {.ll = n};
+  const DWunion dd = {.ll = d};
+  DWunion ww,rr;
+  UWtype d0, d1, n0, n1, n2;
+  UWtype q0, q1;
+  UWtype b, bm;
 	
-	d0 = dd.s.low;
-	d1 = dd.s.high;
-	n0 = nn.s.low;
-	n1 = nn.s.high;
+  d0 = dd.s.low;
+  d1 = dd.s.high;
+  n0 = nn.s.low;
+  n1 = nn.s.high;
 	
-	if (d1 == 0) {
-		if (d0 > n1)	{
-			/* 0q = nn / 0D */
-			udiv_qrnnd (q0, n0, n1, n0, d0);
-			q1 = 0;
-			/* Remainder in n0.  */
-		} else {
-			/* qq = NN / 0d */
-			if (d0 == 0)
-				d0 = 1 / d0;	/* Divide intentionally by zero.  */
-			udiv_qrnnd (q1, n1, 0, n1, d0);
-			udiv_qrnnd (q0, n0, n1, n0, d0);
-			/* Remainder in n0.  */
-		}
+  if (d1 == 0) {
+    if (d0 > n1)	{
+      /* 0q = nn / 0D */
+      udiv_qrnnd (q0, n0, n1, n0, d0);
+      q1 = 0;
+      /* Remainder in n0.  */
+    } else {
+      /* qq = NN / 0d */
+      if (d0 == 0)
+	d0 = 1 / d0;	/* Divide intentionally by zero.  */
+      udiv_qrnnd (q1, n1, 0, n1, d0);
+      udiv_qrnnd (q0, n0, n1, n0, d0);
+      /* Remainder in n0.  */
+    }
 		
-		if (rp != 0)	{
-			rr.s.low = n0;
-			rr.s.high = 0;
-			*rp = rr.ll;
-		}
-	} else {
-		if (d1 > n1) {
-			/* 00 = nn / DD */
-			q0 = 0;
-			q1 = 0;
+    if (rp != 0)	{
+      rr.s.low = n0;
+      rr.s.high = 0;
+      *rp = rr.ll;
+    }
+  } else {
+    if (d1 > n1) {
+      /* 00 = nn / DD */
+      q0 = 0;
+      q1 = 0;
 			
-			/* Remainder in n1n0.  */
-			if (rp != 0) {
-				rr.s.low = n0;
-				rr.s.high = n1;
-				*rp = rr.ll;
-			}
-		} else {
-			/* 0q = NN / dd */
-			count_leading_zeros (bm, d1);
-			if (bm == 0) {
-				/* From (n1 >= d1) /\ (the most significant bit of d1 is set),
-				   conclude (the most significant bit of n1 is set) /\ (the
-				   quotient digit q0 = 0 or 1).
-				   This special case is necessary, not an optimization.  */
+      /* Remainder in n1n0.  */
+      if (rp != 0) {
+	rr.s.low = n0;
+	rr.s.high = n1;
+	*rp = rr.ll;
+      }
+    } else {
+      /* 0q = NN / dd */
+      count_leading_zeros (bm, d1);
+      if (bm == 0) {
+	/* From (n1 >= d1) /\ (the most significant bit of d1 is set),
+	   conclude (the most significant bit of n1 is set) /\ (the
+	   quotient digit q0 = 0 or 1).
+	   This special case is necessary, not an optimization.  */
 				
-				/* The condition on the next line takes advantage of that
-				   n1 >= d1 (true due to program flow).  */
-				if (n1 > d1 || n0 >= d0) {
-					q0 = 1;
-					sub_ddmmss (n1, n0, n1, n0, d1, d0);
-				} else
-					q0 = 0;
+	/* The condition on the next line takes advantage of that
+	   n1 >= d1 (true due to program flow).  */
+	if (n1 > d1 || n0 >= d0) {
+	  q0 = 1;
+	  sub_ddmmss (n1, n0, n1, n0, d1, d0);
+	} else
+	  q0 = 0;
 				
-				q1 = 0;
+	q1 = 0;
 				
-				if (rp != 0) {
-					rr.s.low = n0;
-					rr.s.high = n1;
-					*rp = rr.ll;
-				}
-			} else {
-				UWtype m1, m0;
-				/* Normalize.  */
+	if (rp != 0) {
+	  rr.s.low = n0;
+	  rr.s.high = n1;
+	  *rp = rr.ll;
+	}
+      } else {
+	UWtype m1, m0;
+	/* Normalize.  */
 				
-				b = W_TYPE_SIZE - bm;
+	b = W_TYPE_SIZE - bm;
 				
-				d1 = (d1 << bm) | (d0 >> b);
-				d0 = d0 << bm;
-				n2 = n1 >> b;
-				n1 = (n1 << bm) | (n0 >> b);
-				n0 = n0 << bm;
+	d1 = (d1 << bm) | (d0 >> b);
+	d0 = d0 << bm;
+	n2 = n1 >> b;
+	n1 = (n1 << bm) | (n0 >> b);
+	n0 = n0 << bm;
 		      
-				udiv_qrnnd (q0, n1, n2, n1, d1);
-				umul_ppmm (m1, m0, q0, d0);
+	udiv_qrnnd (q0, n1, n2, n1, d1);
+	umul_ppmm (m1, m0, q0, d0);
 		      
-				if (m1 > n1 || (m1 == n1 && m0 > n0)) {
-					q0--;
-					sub_ddmmss (m1, m0, m1, m0, d1, d0);
-				}
+	if (m1 > n1 || (m1 == n1 && m0 > n0)) {
+	  q0--;
+	  sub_ddmmss (m1, m0, m1, m0, d1, d0);
+	}
 		      
-				q1 = 0;
+	q1 = 0;
 		      
-				/* Remainder in (n1n0 - m1m0) >> bm.  */
-				if (rp != 0) {
-					sub_ddmmss (n1, n0, n1, n0, m1, m0);
-					rr.s.low = (n1 << b) | (n0 >> bm);
-					rr.s.high = n1 >> bm;
-					*rp = rr.ll;
-				}
-			}
-		}
+	/* Remainder in (n1n0 - m1m0) >> bm.  */
+	if (rp != 0) {
+	  sub_ddmmss (n1, n0, n1, n0, m1, m0);
+	  rr.s.low = (n1 << b) | (n0 >> bm);
+	  rr.s.high = n1 >> bm;
+	  *rp = rr.ll;
 	}
+      }
+    }
+  }
   
-	ww.s.low = q0; ww.s.high = q1;
-	return ww.ll;
+  ww.s.low = q0; ww.s.high = q1;
+  return ww.ll;
 }
 
 long long _div64 (long long u, long long v)
 {
-	long c = 0;
-	DWunion uu = {.ll = u};
-	DWunion vv = {.ll = v};
-	DWtype w;
+  long c = 0;
+  DWunion uu = {.ll = u};
+  DWunion vv = {.ll = v};
+  DWtype w;
 	
-	if (uu.s.high < 0)
-		c = ~c,
-			uu.ll = -uu.ll;
-	if (vv.s.high < 0)
-		c = ~c,
-			vv.ll = -vv.ll;
+  if (uu.s.high < 0)
+    c = ~c,
+      uu.ll = -uu.ll;
+  if (vv.s.high < 0)
+    c = ~c,
+      vv.ll = -vv.ll;
 	
-	w = _stp_udivmoddi4 (uu.ll, vv.ll, (UDWtype *) 0);
-	if (c)
-		w = -w;
+  w = _stp_udivmoddi4 (uu.ll, vv.ll, (UDWtype *) 0);
+  if (c)
+    w = -w;
 	
-	return w;
+  return w;
 }
 
 long long _mod64 (long long u, long long v)
 {
-	long c = 0;
-	DWunion uu = {.ll = u};
-	DWunion vv = {.ll = v};
-	DWtype w;
+  long c = 0;
+  DWunion uu = {.ll = u};
+  DWunion vv = {.ll = v};
+  DWtype w;
 	
-	if (uu.s.high < 0)
-		c = ~c,
-			uu.ll = -uu.ll;
-	if (vv.s.high < 0)
-		vv.ll = -vv.ll;
+  if (uu.s.high < 0)
+    c = ~c,
+      uu.ll = -uu.ll;
+  if (vv.s.high < 0)
+    vv.ll = -vv.ll;
 	
-	(void) _stp_udivmoddi4 (uu.ll, vv.ll, (UDWtype*)&w);
-	if (c)
-		w = -w;
+  (void) _stp_udivmoddi4 (uu.ll, vv.ll, (UDWtype*)&w);
+  if (c)
+    w = -w;
 	
-	return w;
+  return w;
 }
 #endif /* __i386__ */