0

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.

Lance
  • 75,200
  • 93
  • 289
  • 503

1 Answers1

1

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
chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
  • Did you just figure this out or get it from somewhere? Should divide by 2 be floored? Is this the most optimal solution? Like [this](https://gist.github.com/lancejpollard/86359ed3f2b832044c265f2e4f633bad)? – Lance Apr 20 '22 at 08:19
  • [Similar question](https://stackoverflow.com/questions/71934050/how-to-generate-the-count-trailing-zeroes-table). – Lance Apr 20 '22 at 10:12
  • @Lance I figured it out. Yes, the division is floored. Optimal - perhaps not. Could instead walk `clzlut[]`, first element is 8, next 1 element is 7, next 2 is 6, next 4 is 5, next 8 elements are 4, ... This omits the inner while loop. – chux - Reinstate Monica Apr 20 '22 at 13:27