I found this function, but there is no explanation of where the clzlut lookup table came from (and I searched for many hours for it on the web, couldn't find anything):
static uint8_t clzlut[256] = {
8,7,6,6,5,5,5,5,
4,4,4,4,4,4,4,4,
3,3,3,3,3,3,3,3,
3,3,3,3,3,3,3,3,
2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0
};
uint32_t clz(uint32_t val)
{
uint32_t accum = 0;
accum += clzlut[val >> 24];
accum += (accum == 8 ) ? clzlut[(val >> 16) & 0xFF] : 0;
accum += (accum == 16) ? clzlut[(val >> 8) & 0xFF] : 0;
accum += (accum == 24) ? clzlut[ val & 0xFF] : 0;
return accum;
}
How do you generate this lookup table? What is the algorithm (in C or JavaScript or the like), for generating this lookup table? I am going to use it for the "count leading zeroes" (clz) implementation. I know there is builtins for clz, I just want to know how to generate a fallback, and for curiosity/learning's sake.
How do you generate this lookup table?
...to know how to generate a fallback, and for curiosity/learning's sake.
For each index 0 to 255:
Start at count = 8. (Bit width of uint8_t)
Copy index to i.
while i > 0:
Divide i by 2.
Decrement count.
clzlut[index] = count