Simple batch decoding of unary codes

Unary codes are a form of universal variable-length code (UVLC) that are sometimes used on their own but more commonly used as a building block for more general families of UVLCs like Golomb, Rice or Gamma/Exp-Golomb codes. There are multiple conventions in use, the one I’ll use in the following has codewords terminated with a “1” bit and is 0-based, i.e. the codebook goes 0 -> 11 -> 012 -> 0013 -> 00014 -> 00001 and so forth. That is, some value i is encoded by sending i “0” bits and a single “1” bit at the end. You sometimes see the opposite convention (variable-length run of 1s terminated by a single 0), but having the runs be 0 bits is a bit nicer in code. The main reason is that “count leading/trailing zero bits” instructions are readily available on most machines these days; these can also be used to count leading/trailing ones by doing a bitwise complement first, but that extra work disappears when we use 0s in the first place. In this post, I want to consider the case where…