fix unlikely loop in median computation

SCCS-vsn: usr.sbin/timed/timed/networkdelta.c 8.2

diff --git a/usr/src/usr.sbin/timed/timed/networkdelta.c b/usr/src/usr.sbin/timed/timed/networkdelta.c
index 04ada10..15f6b8b 100644 (file)
--- a/usr/src/usr.sbin/timed/timed/networkdelta.c
+++ b/usr/src/usr.sbin/timed/timed/networkdelta.c
@@ -6,7 +6,7 @@
  */
 
 #ifndef lint
  */
 
 #ifndef lint

-static char sccsid[] = "@(#)networkdelta.c     8.1 (Berkeley) %G%";
+static char sccsid[] = "@(#)networkdelta.c     8.2 (Berkeley) %G%";

 #endif /* not lint */
 
 #ifdef sgi
 #endif /* not lint */
 
 #ifdef sgi


@@ -75,15 +75,23 @@ networkdelta()
        if (numdelta == 1)
                return 0;
 
        if (numdelta == 1)
                return 0;
 

+       /* get average of trusted values */

        med /= numdelta;
        med /= numdelta;

-       eps = med - x[0];
+

        if (trace)
                fprintf(fd, "median of %d values starting at %ld is about ",
                        numdelta, med);
        if (trace)
                fprintf(fd, "median of %d values starting at %ld is about ",
                        numdelta, med);

+       /* get median of all trusted values, using average as initial guess */
+       eps = med - x[0];

        med = median(med, &eps, &x[0], xp+1, VALID_RANGE);
 
        med = median(med, &eps, &x[0], xp+1, VALID_RANGE);
 

-       /*
-        * compute the median of all values near the good median
+       /* Compute the median of all good values.
+        * Good values are those of all clocks, including untrusted clocks,
+        * that are
+        *      - trusted and somewhat close to the median of the
+        *              trusted clocks
+        *      - trusted or untrusted and very close to the median of the
+        *              trusted clocks

         */
        hidelta = med + GOOD_RANGE;
        lodelta = med - GOOD_RANGE;
         */
        hidelta = med + GOOD_RANGE;
        lodelta = med - GOOD_RANGE;


@@ -163,7 +171,7 @@ median(a, eps_ptr, x, xlim, gnuf)
                        float xx = *xptr;
 
                        dum = xx - a;
                        float xx = *xptr;
 
                        dum = xx - a;

-                       if (dum != 0.0) {       /* avoid dividing by 0 */
+                       if (dum != 0.0) {   /* avoid dividing by 0 */

                                if (dum > 0.0) {
                                        npts++;
                                        if (xx < xp)
                                if (dum > 0.0) {
                                        npts++;
                                        if (xx < xp)


@@ -183,7 +191,8 @@ median(a, eps_ptr, x, xlim, gnuf)
                if (ap-am < gnuf || sum == 0) {
                        if (trace)
                                fprintf(fd,
                if (ap-am < gnuf || sum == 0) {
                        if (trace)
                                fprintf(fd,

-                                  "%ld in %d passes; early out balance=%d\n",
+                                       "%ld in %d passes;"
+                                       " early out balance=%d\n",

                                        (long)a, pass, npts);
                        return a;       /* guess was good enough */
                }
                                        (long)a, pass, npts);
                        return a;       /* guess was good enough */
                }


@@ -191,14 +200,14 @@ median(a, eps_ptr, x, xlim, gnuf)
                aa = (sumx/sum-a)*AMP;
                if (npts >= 2) {        /* guess was too low */
                        am = a;
                aa = (sumx/sum-a)*AMP;
                if (npts >= 2) {        /* guess was too low */
                        am = a;

-                       aa = xp + max(0.0, aa);;
-                       if (aa > ap)
+                       aa = xp + max(0.0, aa);
+                       if (aa >= ap)

                                aa = (a + ap)/2;
 
                                aa = (a + ap)/2;
 

-               } else if (npts <= -2) {  /* guess was two high */
+               } else if (npts <= -2) {    /* guess was two high */

                        ap = a;
                        ap = a;

-                       aa = xm + min(0.0, aa);;
-                       if (aa < am)
+                       aa = xm + min(0.0, aa);
+                       if (aa <= am)

                                aa = (a + am)/2;
 
                } else {
                                aa = (a + am)/2;
 
                } else {


@@ -207,8 +216,8 @@ median(a, eps_ptr, x, xlim, gnuf)
 
                if (a == aa) {
                        if (trace)
 
                if (a == aa) {
                        if (trace)

-                               fprintf(fd,
-                                 "%ld in %d passes; force out balance=%d\n",
+                               fprintf(fd, "%ld in %d passes;"
+                                       " force out balance=%d\n",

                                        (long)a, pass, npts);
                        return a;
                }
                                        (long)a, pass, npts);
                        return a;
                }


@@ -225,7 +234,7 @@ median(a, eps_ptr, x, xlim, gnuf)
                else
                        a = (xm+a)/2;
 
                else
                        a = (xm+a)/2;
 

-       } else  if (npts != 0) {        /* odd number of points */
+       } else if (npts != 0) {         /* odd number of points */

                if (npts > 0)
                        a = xp;
                else
                if (npts > 0)
                        a = xp;
                else