lkml.org 
[lkml]   [2010]   [Aug]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: [PATCHv2 1/3] lib: vsprintf: optimised put_dec_trunc() and put_dec_full()
Date
Denys Vlasenko <vda.linux@googlemail.com> writes:

> 2010/8/10 Michał Nazarewicz <m.nazarewicz@samsung.com>:
>>> On Sunday 08 August 2010 21:29, Michal Nazarewicz wrote:
>>>>
>>>> +       /*
>>>> +        * '(x * 0xcccd) >> 19' is an approximation of 'x / 10' that
>>>> +        * gives correct results for all x < 81920.  However, because
>>>> +        * intermediate result can be at most 32-bit we limit x to be
>>>> +        * 16-bit.
>>>> +        *
>>>> +        * Because of those, we check if we are dealing with a "big"
>>>> +        * number and if so, we make it smaller remembering to add to
>>>> +        * the most significant digit.
>>>> +        */
>>>> +       if (q >= 50000) {
>>>> +               a  = '5';
>>>> +               q -= 50000;
>>>
>>> ...
>>>>
>>>> +       /*
>>>> +        * We need to check if q is < 65536 so we might as well check
>>
>> On Tue, 10 Aug 2010 05:17:48 +0200, Denys Vlasenko
>> <vda.linux@googlemail.com> wrote:
>>>
>>> You meant "need to check if q is < 81920"?
>>
>> No.  81920 is a 17 bit number and when we multiply it by 0xcccd we lose
>> the most significant bit.
>> Therefore we cannot use the '(x * 0xcccd) >>
>> 19' approximation for numbers which are higher then 65535.
>
> No. All x up to (exclusive) 81920 can be multiplied by 0xcccd
> and result still fits into 32 bits. Proof:
>
> # printf "%x\n" $((81919 * 0xcccd))
> ffff7333

Turns out something else was a problem ((x * 13) >> 7 works for x <
69). I'll update comments in the next version.

--
Best regards, _ _
.o. | Liege of Serenly Enlightened Majesty of o' \,=./ `o
..o | Computer Science, Michal "mina86" Nazarewicz (o o)
ooo +--<mina86-tlen.pl>--<jid:mina86-jabber.org>--ooO--(_)--Ooo--
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2010-08-11 00:45    [W:5.078 / U:0.216 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site