4 ms·
I found most of them in code and on the 'net but came up with a couple myself. When I started looking at bit interleaving some years back, I found a few example
by jandrewrogers 15y ago
I found most of them in code and on the 'net but came up with a couple myself. When I started looking at bit interleaving some years back, I found a few examples for 2- and 3-dimensions but not much explanation. If you step through the algorithm and label every bit to watch how they move, it starts to become obvious what is going on. This was how I learned. The constants mask individual bits so that the sum of the shifts applied to a bit equals the total shift. If a bit needs to be shifted 5 bits to its final position, the mask is not applied to that bit for the ">>4" and ">>1" step. Consequently, constants and shifts for a particular transform do not have to be based on powers of two, just numbers where the sum of some subset of shifts matches every shift in the integer you are transforming.
Once you know that, you can generate any distribution you need. However, Morton numbers take advantage of a property of their bit distributions where intermediate steps never corrupt a bit that is not going to be masked off anyway. This is not true for some other bit interleaving patterns. Extending it to arbitrary patterns requires two masking operations with another magic constant at each step which protects bits that would otherwise be destroyed in the simple Morton algorithm.
Nothing like the transform engine I wrote is open source to the best of my knowledge. There is no reason I could not open source it, I just haven't. It is pretty efficient in that it can do a number of reductions and simplifications to the minimum number of steps and constants required to produce an n-dimensional interleaved result. For irregular patterns, you end up with quite a few no-op steps that can be eliminated; for regular patterns you can reuse steps, saving memory. I'll probably write it up and put it on the web at some point.