lkml.org 
[lkml]   [2014]   [Dec]   [4]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Re: [PATCH] optimize ktime_divns for constant divisors
On Fri, 5 Dec 2014, pang.xunlei@zte.com.cn wrote:

> Nicolas,
>
> On Thursday 04 December 2014 15:23:37: Nicolas Pitre wrote:
> > Nicolas Pitre <nicolas.pitre@linaro.org>
> >
> > u64 ktime_to_us(ktime_t kt)
> > {
> > u64 ns = ktime_to_ns(kt);
> > u32 x_lo, x_hi, y_lo, y_hi;
> > u64 res, carry;
> >
> > x_hi = ns >> 32;
> > x_lo = ns;
> > y_hi = 0x83126e97;
> > y_lo = 0x8d4fdf3b;
> >
> > res = (u64)x_lo * y_lo;
> > carry = (u64)(u32)res + y_lo;
> > res = (res >> 32) + (carry >> 32);
> >
> > res += (u64)x_lo * y_hi;
> > carry = (u64)(u32)res + (u64)x_hi * y_lo;
> > res = (res >> 32) + (carry >> 32);
> >
> > res += (u64)x_hi * y_hi;
> > return res >> 9;
> > }
>
> What's the first carry operation for?

Hmmm... OK there is a bug.

The code should actually be:

res = (u64)x_lo * y_lo;
carry = (u64)(u32)res + y_lo;
res = (res >> 32) + (carry >> 32) + y_hi;

(the addition of y_hi was missing on the third line of the above block)

The equation is: res = (y + x*y) >> 9

> Moreover, I think the carry operations can be omitted, like below:
> u64 ktime_to_us(ktime_t kt)
> {
> u64 ns = ktime_to_ns(kt);
> u32 x_lo, x_hi, y_lo, y_hi;
> u64 res;
>
> x_hi = ns >> 32;
> x_lo = ns;
> y_hi = 0x83126e97;
> y_lo = 0x8d4fdf3b;
>
> res = (u64)x_lo * y_lo;
> res = (res >> 32);

See above. y must be added to res before shifting, and that may cause an
overflow.

> res += (u64)x_lo * y_hi + (u64)x_hi * y_lo;

That, too, risk overflowing.

Let's say x_lo = 0xffffffff and x_hi = 0xffffffff. You get:

0xffffffff * 0x83126e97 -> 0x83126e967ced9169
0xffffffff * 0x8d4fdf3b -> 0x8d4fdf3a72b020c5
-------------------
0x110624dd0ef9db22e

Therefore the sum doesn't fit into a u64 variable.

It is possible to skip carry handling but only when the MSB of both
constants are zero. Here it is not the case.

> res = (res >> 32);
>
> res += (u64)x_hi * y_hi;
>
> return res >> 9;
> }
>
> Also, I ran this code using ktime "122500000000", and it results as
> 122499999 due to the y_lo deviation,

Please see bug fix above.

> maybe can use 0x8d4fdf3c instead?

No, that won't work with 0xfffffffffffffd97 for example.


Nicolas


\
 
 \ /
  Last update: 2014-12-05 06:01    [W:0.107 / U:1.048 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site