Re: On writing JITs

[Ken Fox]

Nicholas Clark wrote:
> It seems that foo & (foo - 1) is zero only for a power of 2 (or foo == 0) 
> but is there a fast way once you know that foo is a power of 2, to find out
> log2 foo?

You're right about (foo & (foo -1)).

gcc uses a repeated test and shift. That's works very nicely if foo
is small -- and I bet it usually is. If you want to protect yourself
from the cases where foo is large, you can unroll the loop 2 or 3 times
and then use a binary search.

I've attached two simple implementations I wrote. Neither log2()
implementation is from gcc, so don't worry about GPL contamination.

- Ken

#include <stdio.h>
#include <assert.h>

int simple_log2(int foo) {
     int log = 0;

     assert((foo & (foo - 1)) == 0);

     while (foo) {
        ++log;
        foo >>= 1;
     }

     --log;

     return log;
}

int unrolled_log2(int foo) {
     int log = 0;
     int mid = 4 * sizeof(foo);

     assert(foo != 0);
     assert((foo & (foo - 1)) == 0);

     foo >>= 1;
     if (foo == 0) goto done;
     foo >>= 1; ++log;
     if (foo == 0) goto done;
     foo >>= 1; ++log;
     if (foo == 0) goto done;

     do {
        if (foo >= (1 << mid)) {
            foo >>= mid;
            log += mid;
        }
        mid >>= 1;
     }
     while (mid);

     ++log;

done:

     return log;
}

int main(int argc, char *argv[]) {

#if 1

     int i = 1;
     while (i < (1 << 30)) {
        printf("log2(%d) == %d\n", i, unrolled_log2(i));
        i <<= 1;
     }

#else

     /* simple timing loop */

     int i = 10000000;
     volatile int j;
     while (i > 0) {
        j = unrolled_log2(1 << 29);
        j = unrolled_log2(2);
        j = simple_log2(1 << 29);
        j = simple_log2(2);
        --i;
     }

#endif

     return 0;
}