lib: vsprintf: optimised put_dec_trunc() and put_dec_full()
in [Kernel]
|
Prev: [tip:perf/urgent] perf, x86: P4 PMU -- update nmi irq statistics and unmask lvt entry properly
Next: lib: vsprintf: optimised put_dec() for 32-bit machines
From: Michał Nazarewicz on 10 Aug 2010 03:40 > 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(a)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. >> + * if we can just call the _full version of this function. >> + */ >> + if (q > 9999) >> + return put_dec_full(buf, q); -- Best regards, _ _ | Humble Liege of Serenely Enlightened Majesty of o' \,=./ `o | Computer Science, Michał "mina86" Nazarewicz (o o) +----[mina86*mina86.com]---[mina86*jabber.org]----ooO--(_)--Ooo-- -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Michal Nazarewicz on 10 Aug 2010 18:50
Denys Vlasenko <vda.linux(a)googlemail.com> writes: > 2010/8/10 Michał Nazarewicz <m.nazarewicz(a)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(a)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(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ |