Logical AND using only shift and rotate, for a known constant AND mask

Question

I would like to replace the "AND" in the following set of instructions (in Assembly MIPS) with shift and rotate instructions only and obviously have the same result for any word

.text
main:
        la $a0,input            
        lw $t1,0($a0)           
        li $t0,0xFFF00FFF   #mask
        and $t2,$t1,$t0     
        li $v0,10
        syscall
        .data
input:  .word 0x12345678

I know for this particular mask that the answer is the following:

ror $t2, $t1, 9
srl $t2, $t2, 17
ror $t2, $t2, 6

I would like to know how are the above shifts/rotations calculated.

The output in binary is:

input : 00010010001101000101011001111000 ($t1)
mask  : 11111100000000000000000111111111 ($t0)

output: 00010000000000000000000001111000 ($t2)

Answer 1

You're taking advantage of the fact that a shift (logical) will shift in 0 bits and discard bits shifted out while a rotate will preserve all the bits bringing the shifted out bits back in the other end. So a constant AND mask will turn into a shift for each range of 0s in the mask and a rotate for each range of 1s, with a total shift/rotate count of 32.

To calculate the shifts/rotates, you need to just find all the extents of 0s or 1s in the mask and shift or rotate by that amount. You can start from the bottom of the mask (using ror/srl) or from the top of the mask (using rol/sll)

So for the mask 0xfff00fff, starting from the bottom, you have 12 1s, then 8 0s, then 12 1s, giving

ror $t2, $t1, 12
srl $t2, $t2, 8
ror $t2, $t2, 12

For the worst case of a mask with alternating bits like 0x55555555, you end up with a total of 32 (alternating) shifts and rotates, each by 1 bit.