All About Bit Rotation
#1
All About Bit Rotation



Chapter 1: Introduction

If you have been making codes, even for a tiny bit, you have definitely came across an instruction like this...

rlwinm r0, r5, 3, 0, 28

This is a bit rotation instruction. There are 3 major bit rotation instructions...

rlwnm - Rotate Left Word Then And w/ Mask
rlwinm - Rotate Left Word Immediate Then And w/ Mask
rlwimi - Rotate Left Word Immediate Then Insert Mask

These rotation instructions are like PowerPC's Swiss army knife. They can do many tasks such as multiply, divide, shift, rotate, clear, clear then shift, etc. The instructions can also be used to check for negative values, check for alignment, etc. With these instructions being so useful (and commonly used by PPC compilers), it's recommended you at least learn a little bit about bit rotation.

Even though there are only 3 major rotating instructions (aka standard mnemonics), there are many simplified mnemonics available. It's easier to use these simplified mnemonics instead of the actual rlw type standard mnemonics.



Chapter 2: Understanding Binary/Bits

Values you see in registers are obviously displayed in Hex. The values are actually in binary, but they are displayed in Hex for ease of use and readability.

For example, let's say r5 has a value 0x12300BCD. Obviously, registers (GPRs) are 32 bits. Thus each digit represents 4 bits. The value in r5 in binary is this....

0001 0010 0011 0000 0000 1011 1100 1101

Since each digit represents 4 binary numbers, it's easier to display the bits in groups of 4. The first bit (Sometimes called the sign bit) is bit 0. The last bit is bit 31.

When converting Hex to Binary, or Binary to Hex, use some online converter if you haven't memorized all the conversion values.



Chapter 3: Basic Bit Clearing

Going back to r5... (0x12300BCD) Bits 0 thru 3 are 0001. Let's say we set it to all 0's (0000). r5's value would now be 0x02300BCD. This is called clearing bits. There are 2 basic clearing simplified mnemonics...

clrlwi rD, rA, XX
clrrwi rD, rA, XX

clrlwi is Clear Left Word Immediate. This instruction will clear the upper (left-hand) bits (starting at bit 0 going right) of rA, via the XX value (XX value range is 1 thru 31), and the result is placed in rD.

clrrwi is Clear Right Word Immediate. It's the opposite of clrlwi. This will clear the lower bits (starting at bit 31 going left) of rA, and place result in rD.

Let's say r5 has the value of 0x1AAB000F. This in binary is...

0001 1010 1010 1011 0000 0000 0000 1111

If we do the clrrwi instruction of "clrrwi r5, r5, 22", we will need to zero-out the lower/right-hand 22 bits of r5. The 10 upper/left-hand bits are left alone. r5 in binary would now be..

0001 1010 1000 0000 0000 0000 0000 0000

The bits in blue were the bits that were cleared by the instruction. Convert the result back to hex, and see r5 is now 0x1A800000. Notice how the 3rd digit of r5 went from A to 8. This is because bits 8 thru 11 went from 1010 to 1000.



Chapter 4: Basic Bit Shifting

Clearing was easy enough, let's dive in bit shifting. Instead of zero-ing out bits, we will 'move/shift' them. Obviously, we can shift them either left or right.

Here are two basic shifting instructions...

slwi rD, rA, XX
srwi rD, rA, XX

The XX value designates how many bits to shift by, XX can be anything from 1 to 31. There are also these shifting instructions..

slw rD, rA, rB
srw rD, rA, rB

It's the same thing as before but the amount to shift is in a source register instead of an immediate value.

Let's say r5, has a value of 0x0000FE1F. This in binary is...

0000 0000 0000 0000 1111 1110 0001 1111

Take note of the purple '1'. If we execute the instruction of "srwi r5, r5, 15", r5's result in binary is...

0000 0000 0000 0000 0000 0000 0000 0001

Thus r5 is 0x00000001. Notice where the purple '1' is at now. It was moved/shifted to the right by 15 bits. Whatever bits that went beyond bit 31 are thrown away. Same rule applies if you were shifting bits toward the left and they went beyond bit 0. Let's take a look an at example shifting left...

Example: "slwi r6, r6, 2" r6 starts off as 0x80000007. Binary form is...

1000 0000 0000 0000 0000 0000 0000 0111

After instruction is executed. The result in binary is...

0000 0000 0000 0000 0000 0000 0001 1100

Hex result is 0x0000001C. The red 1 is thrown away because it was shifted beyond bit 0. Obviously the three green 1's are shifted accordingly, but take a look at the blue bits (bits 30 and 31). They are set to 0, because shifting instructions do a 'cut-paste' method.



Chapter 5: Disassembling rlw Type Standard Mnemonics... (Pt 1: rlwinm and rlwnm)

Dolphin displays all bit-rotating instructions in their standard mnemonic form. So does all PPC Decompilers. This can be frustrating as some bit clearing/shifting instructions are easier to read in their simplified mnemonic form.

Dolphin also displays bit-rotation instructions incorrectly. We will cover this more in Chapter 8. First let's disassemble a rlwinm instruction..

rlwinm r0, r5, 3, 0, 28

Ok at this point, you are probably thinking what the hell the values 3, 0, and 28 are used for.

The 3 is called the 'SH'. It's the amount of digits to rotate to the left. Rotating is DIFFERENT than shifting. You still shift to the left, but whatever bits that are shifted leftward past bit 0, are cycled back and looped back into the lower bits, instead of being thrown away. For example if you rotated a value by 1 bit. Bit 0 now goes to Bit 31. Bit 1 to 0. Bit 2 to 1, etc etc.

For a picture showing shifting left vs rotating left - http://programmedlessons.org/AssemblyTut...iftRot.gif

The 0 in our rlwinm instruction is the 'MB' (Mask beginning), and the 28 is the 'ME' (Mask end). The MB and ME creates a string of 1's aka a Mask. The MB is the bit where the mask begins, the ME is the bit where the mask ends.

So an MB of 0 with an ME of 28 means that bits 0 thru 28 are all set to 1. In hex form, that value would is 0xFFFFFFF8. This is our Mask. Instead of using decimal values to show MB/ME in the instruction, you can show the Mask in full Hex form like this...

rlwinm r0, r5, 3, 0xFFFFFFF8

Let's say we have the value 0x81234567 in r5, and we executed the rlwinm from above. What we do first is ROTATE all the bits leftward by 3.

Before rotation (Take note of the first 3 bits that are color coded):

1000 0001 0010 0011 0100 0101 0110 0111

After rotation (Look at the color coded bits)

0000 1001 0001 1010 0010 1011 0011 1100

As you can see bit 0 is now bit 29! So the result in hex is now 0x091A2B3C. We take this current result, and logically AND it with the Mask (0xFFFFFFF8).

The final result (r0) is 0x091A2B38. For the rlwnm instruction (Rotate Left Word Then And w/ Mask) it's the same procedure except instead of using an immediate value for the initial rotation, we use a second source register. 



Chapter 6: Disassembling rlw Type Standard Mnemonics... (Pt 2: rlwimi)

The 3rd 'rlw' type standard mnemonic is rlwimi. Rotate Left Word Immediate Then Mask Insert. This still involves rotating the bits but there is no logical AND'ing.

This instruction is going to be a bit difficult to explain as it even took me a while to figure this out and there is no really good information anywhere on the net explaining this instruction in a 'noob sense'. Let's look at an example instruction...

rlwimi r6, r4, 2, 0, 29

So you should already know that we will rotate the contents of r4 by 2 bits. Let's say BEFORE the rotation, r4 is this...

0x4455AA01

In binary that is....

0100 0100 0101 0101 1010 1010 0000 0001

After rotation, r4 is now...

0001 0001 0101 0110 1010 1000 0000 0101

Which in hex is 0x1156A805. We know that the mask (0, 29) is 0xFFFFFFFC. With the rlwimi instruction, there is NO logical ANDing. What we need to do is look at what is CURRENTLY in r6 (the Destination Register).

Let's say r6 is 0x0000FFFF. Binary form is...

0000 0000 0000 0000 1111 1111 1111 1111

With our 0xFFFFFFFC mask, if a bit in the mask is 1, then whatever bits are in our rotated r4 register will replace whatever bits are in r6. If a bit in the mask is 0, then those bits in r6 are preserved (not replaced by bits in r4!)

With all of that being said, that means r6's bits 30 & 31 do NOT change. And the bits 0 thru 29 of our rotated r4 data replaces bits 0 thru 29 of r6. r6 will thus equal (in binary)..

0001 0001 0101 0110 1010 1000 0000 0111

Which in hex is 0x1156A807. The bits in BLUE are the blues that were used/replaced by the rotated r4 value. The bits in RED were the bits that were preserved (not replaced).

If you have a rlwimi instruction where the destination register is same as the source register (let's say r4). Then the Mask comparison is done w/ old r4 (BEFORE the initial rotation).



Chapter 7: Simplified Mnemonic List

Name = Simplified Menomnic = Standard Menomic

Extract & Left Justify Word Immediate = extlwi rD, rA, n, b (n > 0) = rlwinm rD, rA, b, 0, n - 1
Extract & Right Justify Word Immediate = extrwi rD, rA, n, b, (n > 0) = rlwinm rD, rA, b + n, 32 - n, 31
Insert From Left Word Immediate = inslwi rD, rA, n, b (n > 0) = rlwimi rD, rA, 32 - b, b , (b + n) - 1
Insert From Right Word Immediate = insrwi rD, rA, n , b (n > 0) = rlwimi rD, rA, 32 - (b + n), b, (b + n) - 1
Rotate Left Word Immediate = rotlwi rD, rA, n = rlwinm rD, rA, n, 0, 31
Rotate Right Word Immediate = rotrwi, rD, rA, n = rlwinm, rD, rA, 32 - n, 0, 31
Rotate Word Left = rotlw rD, rA, rB = rlwnm rD, rA, rB, 0, 31
Shift Left Word Immediate = slwi rD, rA, n (n < 32) = rlwinm rD, rA, n, 0, 31 -n
Shift Right Word Immediate = srwi rD, rA, n (n < 32) = rlwinm rD, rA, 32 - n, n, 31
Clear Left Word Immediate = clrlwi rD, rA, n (n < 32) = rlwinm rD, rA, 0, n, 31
Clear Right Word Immediate = clrrwi rD, rA, n (n < 32) = rlwinm rD, rA, 0, 0, 31 - n
Clear Left And Shift Left Word Immediate = clrlslwi rD, rA, b, n, (n ≤ b ≤ 31) = rlwinm rD, rA, n, b - n, 31 - n

• Extract — Select a field of n bits starting at bit position b in the source register; left or right justify
this field in the target register; clear all other bits of the target register.

• Insert — Select a left- or right-justified field of n bits in the source register; insert this field starting
at bit position b of the target register; leave other bits of the target register unchanged.

• Rotate — Rotate the contents of a register right or left n bits without masking.

• Shift — Shift the contents of a register right or left n bits, clearing vacated bits (logical shift).

• Clear — Clear the leftmost or rightmost n bits of a register.

• Clear left and shift left — Clear the leftmost b bits of a register, then shift the register left by n bits. This operation can be used to scale a (known non-negative) array index by the width of an element. 



Chapter 8: Issues with Dolphin

Dolphin will always display the Hex value of the Mask in parenthesis at the very end of every rlw type instruction. The problem is Dolphin displays an incorrect Mask hex value.

For example, let's say we have this instruction...
r0, r5, 3, 0, 28

We know the Mask Hex value for this would be 0xFFFFFFF8. So you would think that Dolphin would display this as.. r0, r5, 3, 0, 28 (0xFFFFFFF8), but it doesn't. Dolphin will display the Mask Hex value as 1FFFFFFF. I have no idea why Dolphin does this.



Chapter 9: Mimicking a 'clrlw/clrrw' Instruction

PowerPC does not come with clrlw/clrrw (clear left word / clear right word) instructions.

To achieve a 'clear left word' (ex: clrlw rD, rA, rB), execute these two instructions...

slw rD, rA, rB
srw rD, rA (rD from the slw), rB

For a 'clear right word', you do the opposite...

srw rD, rA, rB
slw rD, rA (rD from the srw), rB



Chapter 10: Conclusion & Credits

And that's it! Still confused? Don't be afraid to ask questions!

Credits:
NXP (AN2491 pdf file)
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)