From: Andre Noll <maan@tuebingen.mpg.de>
Date: Wed, 16 Mar 2016 21:48:54 +0000 (+0100)
Subject: mood.c: Avoid overflow in update_quadratic_deviation().
X-Git-Tag: v0.5.6~45^2~3
X-Git-Url: http://git.tuebingen.mpg.de/?p=paraslash.git;a=commitdiff_plain;h=66b8dbf57fe5e4c940caef0493e81987ced2dc4a

mood.c: Avoid overflow in update_quadratic_deviation().

The last multiplication of the expression returned can overflow. This
patch replaces the expression by an equivalent one which avoids to
multiply large numbers.
---

diff --git a/mood.c b/mood.c
index 415e1702..45b051a7 100644
--- a/mood.c
+++ b/mood.c
@@ -652,7 +652,8 @@ static int add_if_admissible(struct osl_row *aft_row, void *data)
  * the last number a_n was replaced by b) may be computed in O(1) time in terms
  * of n, q, a_n, b, and S as
  *
- * 	q' = q + d * s - (2 * S + d) * d / n,
+ * 	q' = q + d * s - (2 * S + d) * d / n
+ *	   = q + d * (s - 2 * S / n - d /n),
  *
  * where d = b - a_n, and s = b + a_n.
  *
@@ -669,7 +670,7 @@ _static_inline_ int64_t update_quadratic_deviation(int64_t n, int64_t old_qd,
 {
 	int64_t delta = new_val - old_val;
 	int64_t sigma = new_val + old_val;
-	return old_qd + delta * sigma - (2 * old_sum + delta) * delta / n;
+	return old_qd + delta * (sigma - 2 * old_sum / n - delta / n);
 }
 
 static int update_afs_statistics(struct afs_info *old_afsi, struct afs_info *new_afsi)