Twiddling

General Idea

How to generated the twiddled index from an untwiddled texture:

Original:        Twiddled:

0 1 2 3          0 2 8 A
4 5 6 7          1 3 9 B
8 9 A B          4 6 C E
C D E F          5 7 D F
G H I J          G I O Q
K L M N          H J P R
O P Q R          K M S U
S T U V          L N T V
W X Y Z          W Y % &
~ ! # $          X Z ^ *
% ^ & *          ~ # ( _
( ) _ +          ! $ ) +

The matching characters between the two images represent the same pixel, just relocated. These images would be 4 * 12 pixel images, but the steps work for any valid 2^x * 2^y sizes, where x and y are whole numbers.

Now lets say we want to find the twiddled index of the untwiddled "O" pixel (index 24). By hand we can work it out and tell the twiddle index should be "18", but what algorithm/logic can we use to find this automatically for any i?

Here are my steps:

• We first need to start by figuring out the "Biggest-Order Inverted-N" (BOIN) that fits in this image.
• Now if our starting image was a square, then the BOIN is the same size as the image
• For rectangles like this, we have to find the smallest side first (width) then our BOIN is width * width
• If we start off with a rectangle, then we need to do an extra step that squares can skip.
• Notice how we can completely encapsulate the whole image with (bigger_side / smaller_side) == 3 BOINs? Our first step is to determine which of these BOINs our index i belongs in.
• We can take advantage of a quirk I mentioned earlier. Notice how the first BOIN contains the first 1/3 of the original pixels, the 2nd BOIN contains the next 1/3 and the 3rd BOIN contains the last 1/3.
• Therefore using the formula k = floor(i / (BOIN area == 4 * 4 = 16)) == 1 we can determine that our twiddled index is somewhere in the middle/2nd BOIN (Since k is of the set {0,1,2})
• Note the index where our BOIN starts according to the original texture. The first index in the 2nd BOIN is "16". Keep track of this value, lets call it d
• Also keep track of the index where our BOIN starts according to the twiddled texture, this is also 16 in this case. Lets add this to a running sum s
• Forget about the other two BOINs and subtract d from the indexes in our new BOIN as well as i

So now we have:

i == 8
0 2 8 A
1 3 9 B
4 6 C E
5 7 D F

Great! We can already see by hand that this still looks right, but how do we automatically solve square BOINs?

• In order to solve a square BOIN, we need to determine what quadrant our pixel is in
• So we determine how many pixels are in each quadrant (4 per quadrant here, == a), Then calculate k = floor(i / a) == 2 to know its in the 3rd quadrant (k is in the set {0,1,2,3}).
• That means its in the top right. So we need to set d = a * k), add our new s value to the running sum, discard the other quadrants, then subtract i and the new BOIN's indexes by d
• The easy way to calculate the new part of s is that:
  • top left quadrant is 0
  • top right quad is BOIN-width / 2
  • bottom left is BOIN-width * (BOIN-height / 2)
  • bottom right is (BOIN-width * (BOIN-height / 2)) + (BOIN-width / 2)

Now we have:

i == 0
0 2
1 3

You would repeat until we have a single pixel. Once we have the last pixel, our new twiddled index should be the running sum s (16 + 2 + 0 == 18)

DISCLAIMER

This theorized solution has only been tested on a few examples by hand, so I might have missed something. But I believe at least the general logic of this is sound. Also note for implementation, some of the divisions could be replaced with bit-shifting since some of those numbers are guaranteed to be powers of 2.

For an example of an algorithm that does the reverse (Convert twiddled index to untwiddled), you can refer to this code made by JamoHTP