Re: [PATCH] NTP shift_right cleanup (v. A3)

Re: [PATCH] NTP shift_right cleanup (v. A3)

[linux]

- For fixed shifts, you can just write it as a divide; GCC will DTRT.
  For interest's sake, GCC 4.0 generates, for x /= 64:
        testl   %eax, %eax
	jns	.L2
	addl	$63, %eax
.L2:
	sarl	$6, %eax

- If you want to be more verbose with the explanation, try something like:
  (Public domain, copyright abandoned, use freely, yadda yadda.)
/*
 * NTP uses power-of-two divides a lot for speed, but it wants to use
 * negative numbers.
 * 1) ANSI C does not guarantee signed right shifts (but GCC does)
 * 2) Such a shift is like a divide that rounds to -infinity.
 *    NTP wants rounding to zero, i.e. -3/2 = -2, while -3>>1 = -2.
 */

Interestingly, _Hacker's Delight_ chapter 10 skips over this particular
case, signed division by a variable power of two.

Re: [PATCH] NTP shift_right cleanup (v. A3)

[Nick Piggin]

Ulrich Windl wrote:

> 
> Hi,
> 
> I'm against "signed shift right", because the reason for the macro is exaclty that 
> CPUs do a "signed" shift right. John does a "signum(arg) * right_shift(abs(arg), 
> number_of_positions)". So maybe it's the signed_unsigned_shift_right(), susr() to 
> be cryptic ;-)
> 

I see, so that would be a divide by 2^shift?

Well, nevermind - I guess the patch is better than what was
there before.

-- 
SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] NTP shift_right cleanup (v. A3)

[Ulrich Windl]

On 21 Sep 2005 at 15:24, Nick Piggin wrote:

> john stultz wrote:
> 
> > 
> >+/* Required to safely shift negative values */
> >+#define shift_right(x, s) ({	\
> >+	__typeof__(x) __x = (x);	\
> >+	__typeof__(s) __s = (s);	\
> >+	__x < 0 ? -(-__x >> __s) : __x >> __s;	\
> >+})
> >+
> >
> 
> I'd hate to be the one to make you do another version of this ;)
> 
> However, how about having something more descriptive than shift_right?
> signed_shift_right / shift_right_signed, maybe?

Hi,

I'm against "signed shift right", because the reason for the macro is exaclty that 
CPUs do a "signed" shift right. John does a "signum(arg) * right_shift(abs(arg), 
number_of_positions)". So maybe it's the signed_unsigned_shift_right(), susr() to 
be cryptic ;-)

I'm only surprised that there are many places where such a routine is needed, and 
still it's missing in sime bitops.h #include.

Regards,
Ulrich

Re: [PATCH] NTP shift_right cleanup (v. A3)

[Nick Piggin]

john stultz wrote:

> 
>+/* Required to safely shift negative values */
>+#define shift_right(x, s) ({	\
>+	__typeof__(x) __x = (x);	\
>+	__typeof__(s) __s = (s);	\
>+	__x < 0 ? -(-__x >> __s) : __x >> __s;	\
>+})
>+
>

I'd hate to be the one to make you do another version of this ;)

However, how about having something more descriptive than shift_right?
signed_shift_right / shift_right_signed, maybe?

Nick


Send instant messages to your online friends http://au.messenger.yahoo.com 

[PATCH] NTP shift_right cleanup (v. A3)

[john stultz]

Andrew,
	After some close scrutiny I found a mistake in the A2 version of this
patch. I guess it just goes to prove how difficult to read the current
code is. 


In one part of the old patch, a nested if stated:

       if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
               ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;

However that only bounds ltemp if it is positive, when the current
mainline code bounds it if it is negative as well. Replacing the above
with:

       ltemp = min(ltemp, (MAXPHASE / MINSEC) << SHIFT_UPDATE);
       ltemp = max(ltemp, -(MAXPHASE / MINSEC) << SHIFT_UPDATE);

Corrects the issue.

Below is the corrected patch which should replace the
ntp-shift_right-cleanup.patch file in your tree.

Thanks
-john


Create a macro shift_right() that avoids the numerous ugly conditionals
in the NTP code that look like:

        if(a < 0)
                b = -(-a >> shift);
        else
                b = a >> shift;

Replacing it with:

        b = shift_right(a, shift);

This should have zero effect on the logic, however it should probably
have a bit of testing just to be sure.

Also replace open-coded min/max with the macros.

Signed-off-by : John Stultz <johnstul@us.ibm.com>
---

 include/linux/timex.h |    7 +++++++
 kernel/time.c         |   25 ++++++-------------------
 kernel/timer.c        |   48 ++++++++++--------------------------------------
 3 files changed, 23 insertions(+), 57 deletions(-)

diff --git a/include/linux/timex.h b/include/linux/timex.h
--- a/include/linux/timex.h
+++ b/include/linux/timex.h
@@ -282,6 +282,13 @@ static inline int ntp_synced(void)
 	return !(time_status & STA_UNSYNC);
 }
 
+/* Required to safely shift negative values */
+#define shift_right(x, s) ({	\
+	__typeof__(x) __x = (x);	\
+	__typeof__(s) __s = (s);	\
+	__x < 0 ? -(-__x >> __s) : __x >> __s;	\
+})
+
 
 #ifdef CONFIG_TIME_INTERPOLATION
 
diff --git a/kernel/time.c b/kernel/time.c
--- a/kernel/time.c
+++ b/kernel/time.c
@@ -338,30 +338,20 @@ int do_adjtimex(struct timex *txc)
 		        if (mtemp >= MINSEC) {
 			    ltemp = (time_offset / mtemp) << (SHIFT_USEC -
 							      SHIFT_UPDATE);
-			    if (ltemp < 0)
-			        time_freq -= -ltemp >> SHIFT_KH;
-			    else
-			        time_freq += ltemp >> SHIFT_KH;
+			    time_freq += shift_right(ltemp, SHIFT_KH);
 			} else /* calibration interval too short (p. 12) */
 				result = TIME_ERROR;
 		    } else {	/* PLL mode */
 		        if (mtemp < MAXSEC) {
 			    ltemp *= mtemp;
-			    if (ltemp < 0)
-			        time_freq -= -ltemp >> (time_constant +
-							time_constant +
-							SHIFT_KF - SHIFT_USEC);
-			    else
-			        time_freq += ltemp >> (time_constant +
+			    time_freq += shift_right(ltemp,(time_constant +
 						       time_constant +
-						       SHIFT_KF - SHIFT_USEC);
+						       SHIFT_KF - SHIFT_USEC));
 			} else /* calibration interval too long (p. 12) */
 				result = TIME_ERROR;
 		    }
-		    if (time_freq > time_tolerance)
-		        time_freq = time_tolerance;
-		    else if (time_freq < -time_tolerance)
-		        time_freq = -time_tolerance;
+		    time_freq = min(time_freq, time_tolerance);
+		    time_freq = max(time_freq, -time_tolerance);
 		} /* STA_PLL || STA_PPSTIME */
 	    } /* txc->modes & ADJ_OFFSET */
 	    if (txc->modes & ADJ_TICK) {
@@ -384,10 +374,7 @@ leave:	if ((time_status & (STA_UNSYNC|ST
 	if ((txc->modes & ADJ_OFFSET_SINGLESHOT) == ADJ_OFFSET_SINGLESHOT)
 	    txc->offset	   = save_adjust;
 	else {
-	    if (time_offset < 0)
-		txc->offset = -(-time_offset >> SHIFT_UPDATE);
-	    else
-		txc->offset = time_offset >> SHIFT_UPDATE;
+	    txc->offset = shift_right(time_offset, SHIFT_UPDATE);
 	}
 	txc->freq	   = time_freq + pps_freq;
 	txc->maxerror	   = time_maxerror;
diff --git a/kernel/timer.c b/kernel/timer.c
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -703,23 +703,13 @@ static void second_overflow(void)
      * the adjustment over not more than the number of
      * seconds between updates.
      */
-    if (time_offset < 0) {
-	ltemp = -time_offset;
-	if (!(time_status & STA_FLL))
-	    ltemp >>= SHIFT_KG + time_constant;
-	if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
-	    ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
-	time_offset += ltemp;
-	time_adj = -ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
-    } else {
 	ltemp = time_offset;
 	if (!(time_status & STA_FLL))
-	    ltemp >>= SHIFT_KG + time_constant;
-	if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
-	    ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
+		ltemp = shift_right(ltemp, SHIFT_KG + time_constant);
+	ltemp = min(ltemp, (MAXPHASE / MINSEC) << SHIFT_UPDATE);
+	ltemp = max(ltemp, -(MAXPHASE / MINSEC) << SHIFT_UPDATE);
 	time_offset -= ltemp;
 	time_adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
-    }
 
     /*
      * Compute the frequency estimate and additional phase
@@ -736,30 +726,19 @@ static void second_overflow(void)
 			 STA_PPSWANDER | STA_PPSERROR);
     }
     ltemp = time_freq + pps_freq;
-    if (ltemp < 0)
-	time_adj -= -ltemp >>
-	    (SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE);
-    else
-	time_adj += ltemp >>
-	    (SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE);
+    time_adj += shift_right(ltemp,(SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE));
 
 #if HZ == 100
     /* Compensate for (HZ==100) != (1 << SHIFT_HZ).
      * Add 25% and 3.125% to get 128.125; => only 0.125% error (p. 14)
      */
-    if (time_adj < 0)
-	time_adj -= (-time_adj >> 2) + (-time_adj >> 5);
-    else
-	time_adj += (time_adj >> 2) + (time_adj >> 5);
+    time_adj += shift_right(time_adj, 2) + shift_right(time_adj, 5);
 #endif
 #if HZ == 1000
     /* Compensate for (HZ==1000) != (1 << SHIFT_HZ).
      * Add 1.5625% and 0.78125% to get 1023.4375; => only 0.05% error (p. 14)
      */
-    if (time_adj < 0)
-	time_adj -= (-time_adj >> 6) + (-time_adj >> 7);
-    else
-	time_adj += (time_adj >> 6) + (time_adj >> 7);
+    time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
 #endif
 }
 
@@ -778,10 +757,8 @@ static void update_wall_time_one_tick(vo
 	     * Limit the amount of the step to be in the range
 	     * -tickadj .. +tickadj
 	     */
-	     if (time_adjust > tickadj)
-		time_adjust_step = tickadj;
-	     else if (time_adjust < -tickadj)
-		time_adjust_step = -tickadj;
+	     time_adjust_step = min(time_adjust_step, (long)tickadj);
+	     time_adjust_step = max(time_adjust_step, (long)-tickadj);
 
 	    /* Reduce by this step the amount of time left  */
 	    time_adjust -= time_adjust_step;
@@ -792,13 +769,8 @@ static void update_wall_time_one_tick(vo
 	 * advance the tick more.
 	 */
 	time_phase += time_adj;
-	if (time_phase <= -FINENSEC) {
-		long ltemp = -time_phase >> (SHIFT_SCALE - 10);
-		time_phase += ltemp << (SHIFT_SCALE - 10);
-		delta_nsec -= ltemp;
-	}
-	else if (time_phase >= FINENSEC) {
-		long ltemp = time_phase >> (SHIFT_SCALE - 10);
+	if ((time_phase >= FINENSEC) || (time_phase <= -FINENSEC)) {
+		long ltemp = shift_right(time_phase, (SHIFT_SCALE - 10));
 		time_phase -= ltemp << (SHIFT_SCALE - 10);
 		delta_nsec += ltemp;
 	}