2015-03-05 10:52+0100, Markus Armbruster:
> Gerd Hoffmann <kra...@redhat.com> writes:
>
> > From: Radim Krčmář <rkrc...@redhat.com>
> >
> > We already have pow2floor, mirror it and use instead of a function with
> > similar results (same in used domain), to clarify our intent.
> >
> > Signed-off-by: Radim Krčmář <rkrc...@redhat.com>
> > Signed-off-by: Gerd Hoffmann <kra...@redhat.com>
> [...]
> > +/* round up to the nearest power of 2 (0 if overflow) */
>
> Callers need to check for overflow, but that's the callers' problem.
It's obvious that the return value is 0 in this case -- the correct
result would have been a multiple of the modulo, but I wanted to be
explicit about it.
> > +uint64_t pow2ceil(uint64_t value)
> > +{
> > + uint8_t nlz = clz64(value);
>
> You convert the value of clz64() from int to uint8_t only to promote it
> right back to int in every single use. Please don't muddy the waters
> that way.
Ok, the down-cast might cause some runtime overhead.
(I don't understand why the return value of clz64() is 'int' --
using the smallest sufficient data type seems clearer to me.)
> > + if (is_power_of_2(value)) {
> > + return value;
> > + }
> > + if (!nlz) {
> > + return 0;
> > + }
> > + return 1ULL << (64 - nlz);
> > +}
>
> Doesn't really mirror pow2floor() in master, because that one uses
> int64_t. Fine with me, because my "[PATCH 0/2] Proactive pow2floor()
> fix, and dead code removal" changes pow2floor() to uint64_t.
Yeah, I didn't understand why that returned 'int64_t' either.
I understood that pow2floor() used is_power_of_2() because it expected
higher probability of numbers that already are the power, so the clunky
code was balanced by a faster common case; and I duplicated this.
(clz64() without hardware support is slow.)
> Unfortunately, the two patches conflict.
>
> This patch's implementation of pow2ceil() is needlessly complicated,
> just like pow2floor() in master. Simpler:
>
> uint64_t pow2ceil2(uint64_t value)
> {
> int n = clz64(value - 1);
> return n ? 1ull << (64 - n) : 0;
Mapping 0 to 0 is probably what we would want in most uses, but I'd name
the function differently then -- the closest power of 2 bigger than (or
equal to) 0 is 1, and 2^64 == 0, so the result was mathematically
correct.
We also lose the ability to detect overflow after the call, so callers
would have to do it before, with a code like
'passed_value > DESTINATION_TYPE_MAX / 2 + 1'
> I can rebase my patch on top of this one, and clean things up to my
> taste.
Ok, thanks!
---
If eliminating is_power_of_2() and using the ternary operator is fine,
I'd write it like this:
unsigned nlz = clz64(value - 1);
return !value ? 1 : (nlz ? 1ULL << (64 - nlz) : 0);
If we don't believe that the compiler can optimize, and after applying
all I know about QEMU coding style:
int nlz;
if (!value) {
return 1;
}
nlz = clz64(value - 1);
return n ? 1ull << (64 - n) : 0;
