linux-kernel - Re: [PATCHv2 1/3] lib: vsprintf: optimised put_dec_trunc() and put_dec

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <AANLkTinQNvdKXGmeBS0UbBuur1LQJb=JUf1WyrYN7Yez@mail.gmail.com>
Date:	Tue, 10 Aug 2010 18:08:16 +0200
From:	Denys Vlasenko <vda.linux@...glemail.com>
To:	Michał Nazarewicz <m.nazarewicz@...sung.com>
Cc:	Michal Nazarewicz <mina86@...a86.com>,
	linux-kernel@...r.kernel.org,
	"Douglas W. Jones" <jones@...uiowa.edu>,
	Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: [PATCHv2 1/3] lib: vsprintf: optimised put_dec_trunc() and 
	put_dec_full()

2010/8/10 Michał Nazarewicz <m.nazarewicz@...sung.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@...glemail.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

-- 
vda
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/