________________________________________
From: Mike Acton 
Sent: Thursday, February 22, 2007 4:37 PM
To: Mike Day; tech
Subject: RE: curiously small code...

Hey Mike,

I did think of one thing: We may want to be able to stop-and-continue walking through the texture addresses (as in your last bit of code), and in order to continue the loop, we’d need to store the index (i) as well as the calculated x and y at that index. That might not be a problem, but I thought it might be handy to have a way to calculate x and y directly from the texel address index (i) so you can continue your loop by just storing the index. 

This is what I came up with for that, based on your code below. There’re still things that can be done to make it a smaller, but it’s usable anyway. [ Forgive me if there’s already code laying around that does this. ] 

// (texel_ndx) is the same as (i) in your loop.
// So your code could do something like this…

texture_address_to_swizzle_restart( u32 start_ndx, u32 count )
{
  u32 end_ndx = start_ndx + count;
  u32 x       = texture_address_to_swizzle_x( start_ndx );
  u32 y       = texture_address_to_swizzle_y( start_ndx );

  for (u32 i=start_ndx; i<end_ndx; i++)
  {
    u32 and0 = x & y;
    u32 and1 = and0 + 1;
    u32 xinc = and0 ^ and1;
    u32 yinc = x & xinc;
    x ^= xinc;
    y ^= yinc;

    ---
  }
}


uint32_t
texture_address_to_swizzle_x( uint32_t texel_ndx )
{
    // For even texels, the x position is generated by a
    // half outer perfect unshuffle of the texel index, plus one. 
    // The bottom bit will always be set.
    //
    // For odd texels, the x position is generated by two plus a 
    // half outer perfect unshuffle of the texel index, minus one.
    // The bottom bit will always be clear.
    //
    // A half outer perfect unshuffle looks like this:
    //
    //                  31...                                     ...0
    //   source:       b 0P0N 0M0L   0K0J 0I0H   0G0F 0E0D   0C0B 0A0Z
    //   result:       b 0000 0000   0000 0000   PNML KJIH   GFED CBAZ
    //
    // Notes:
    //
    //     (1) I'm sure there's a way of combining the even and odd 
    //         cases by pushing the ndx_offset to the end and doing 
    //         both at the same time.
    //
    //     (2) I'm assuming that the texel index can use the entire 
    //         32 bit range. If it can't, this might slightly reducable.
    //

    uint32_t ndx_odd    = texel_ndx & 0x00000001;
    uint32_t ndx_offset = ndx_odd + 1;
    uint32_t x_offset   = ~( ndx_odd - 1 );
    uint32_t ndx        = texel_ndx + ndx_offset;
    uint32_t ndx_half   = ndx & 0x55555555;
    uint32_t x1sr       = ndx_half >> 1;
    uint32_t x1or       = ndx_half | x1sr;
    uint32_t x1         = x1or & 0x33333333;
    uint32_t x2sr       = x1 >> 2;
    uint32_t x2or       = x1 | x2sr;
    uint32_t x2         = x2or & 0x0f0f0f0f;
    uint32_t x4sr       = x2 >> 4;
    uint32_t x4or       = x2 | x4sr;
    uint32_t x4         = x4or & 0x00ff00ff;
    uint32_t x8sr       = x4 >> 8;
    uint32_t x8or       = x4 | x8sr;
    uint32_t x8         = x8or & 0x0000ffff;
    uint32_t x_pos      = x8 + x_offset;
    
    return (x_pos);
}

uint32_t
texture_address_to_swizzle_y( uint32_t texel_ndx )
{
    // For even texels, the y position is a half outer perfect unshuffle 
    // of one plus the texel index divided by two.
    //
    // For odd texels, the y position is a half outer perfect unshuffle 
    // of the texel index divided by two.

    uint32_t ndx_offset = texel_ndx & 0x00000001;
    uint32_t ndx        = ( texel_ndx >> 1 ) + ndx_offset;
    uint32_t ndx_half   = ndx & 0x55555555;
    uint32_t y1sr       = ndx_half >> 1;
    uint32_t y1or       = ndx_half | y1sr;
    uint32_t y1         = y1or & 0x33333333;
    uint32_t y2sr       = y1 >> 2;
    uint32_t y2or       = y1 | y2sr;
    uint32_t y2         = y2or & 0x0f0f0f0f;
    uint32_t y4sr       = y2 >> 4;
    uint32_t y4or       = y2 | y4sr;
    uint32_t y4         = y4or & 0x00ff00ff;
    uint32_t y8sr       = y4 >> 8;
    uint32_t y8or       = y4 | y8sr;
    uint32_t y8         = y8or & 0x0000ffff;
    uint32_t y_pos      = y8;
    
    return (y_pos);
}