Four logic operations and a mask
and, or, xor and nor work on all 32 bits at once, each bit on its
own. The immediate forms andi, ori, xori take a 16-bit constant,
zero-extended (§3.2). Click bits in the figure and watch the result row.
a AND b, bit by bit
Which bits of a survive?
305419896 (signed) · 0x12345678
255 (signed) · 0x000000ff
120 (signed) · 0x00000078
- the result bits
Click any input bit to flip it.
What to notice
Where b has a 1, the bit of a comes through. Where b has a 0, the result
is 0. So b = 0x000000FF keeps the low byte of a and clears the rest.
A constant used like that is a . The four operations, in one table:
| operation | rule per bit | typical use |
|---|---|---|
and | 1 only if both are 1 | keep the masked bits, clear the others |
or | 1 if either is 1 | set bits |
xor | 1 if they differ | flip bits; xor a,a is 0 |
nor | 1 only if both are 0 | NOT: nor rd,rs,$zero inverts every bit |
MIPS has no not instruction. not rd,rs is a pseudo-instruction for
nor rd,rs,$zero: OR with zero changes nothing, and nor inverts the result.
The compiler uses masks constantly. hello.c at -O2 stores a character with
andi v0,v0,0xff first: keep the low byte, clear the rest. fib.c at -O0 has
andi v0,v0,0xf: keep the low four bits.
Shifts by a constant
A shift slides every bit left or right by the same amount. Bits that fall off one end are lost. What comes in at the other end is the whole question.
One value, four shifts
What fills the empty bits in each case?
-268435448 (signed) · 0xf0000008 · 4026531848 if read unsigned
-1073741792 (signed) · 0xc0000020 · 3221225504 if read unsigned
1006632962 (signed) · 0x3c000002
-67108862 (signed) · 0xfc000002 · 4227858434 if read unsigned
1006632962 (signed) · 0x3c000002
- bits that came in from outside (or came back around)
- bits that moved
- the sign bit of the input
Click any input bit to flip it.
What to notice
sll moves left and fills zeros on the right: ×4. srl moves right and
fills zeros on the left. sra moves right and fills the sign bit, so the
negative value stays negative. rotr fills with the bits that fell off. Drag
the count and watch the amber fill grow.
Three of these are as old as MIPS:
sll rd,rt,sais a left: multiply by 2ⁿ.sll v0,v0,2atfib_o0.dump bfc001f4computes 4×i, the byte offset ofarray[i].srl rd,rt,sais a logical shift right: divide an unsigned value by 2ⁿ.sra rd,rt,sais an right: divide a signed value by 2ⁿ. −8 shifted right by 1 gives −4.
The count is the 5-bit sa field of the R-format word. Here is the sll
from fib.c:
sll v0,v0,2 from fib.c at -O0 (0x00021080 at 0xBFC001F4)
Where is the shift count, and what is rs doing?
What to notice
sa = 2 is the count. rt = v0 is the value, rd = v0 the destination.
rs is 0: unused. Keep that rs = 0 in mind; it matters below.
Before reading on, decide:
$t1 holds −8 (0xFFFFFFF8). What do `srl $t0,$t1,1` and `sra $t0,$t1,1` give?
Shifts by a register
When the count is not known at compile time, it comes from a register:
sllv, srlv, srav rd,rt,rs. Careful with the order. The value is
rt and the count is rs. Only the low 5 bits of the count are used.
srav v0,v1,v0 from fib.c at -O0 (0x00431007 at 0xBFC001FC)
Which register is shifted, and which one is the count?
What to notice
Assembly srav v0,v1,v0: v1 (in rt) is shifted by v0 (in rs), into
v0. The sa field is 0 here; the count lives in a register instead. The
rt-then-rs order is the opposite of add rd,rs,rt.
Rotate, and a trick in the encoding
Release 2 added
right: rotr rd,rt,sa and rotrv rd,rt,rs. Where srl fills the top with
zeros, rotr fills it with the bits that left the bottom.
Where did release 2 find room for it? In a field srl never used:
srl $t0,$t1,4 — rs is 0
Compare the rs field with the next figure.
rotr $t0,$t1,4 — the same word with rs = 1
Same opcode, same funct. What changed?
What to notice
Opcode 0, funct 2 in both. Only rs differs: 0 means srl, 1 means
rotr. The same trick separates srlv from rotrv, using the sa field.
A decoder that looked only at opcode and funct would confuse them.
Carolyne’s decoder states this explicitly: the matcher for srl is
funct | rs with values (2, 0), and for rotr (2, 1). Leaving rs out of
srl’s rule would make one word match two instructions, and a test pins it.
Go deeper: why there is no not, why rotates came late, and what sra rounds toward
not would be a whole instruction whose job nor already does with $zero.
MIPS kept the instruction count small by letting the assembler write the
alias. The same logic gave us move, li and neg.
Rotates were left out in 1985 because compilers rarely needed them. They
came back in release 2 (2002) for cryptography and hashing, which use them
constantly, and they had to fit into words that were already assigned. The
rs field of srl had been zero for seventeen years, so it became the switch.
sra divides by 2ⁿ rounding toward negative infinity: −7 sra 1 is −4, not
−3. C’s / rounds toward zero, so a compiler that implements x / 2 for a
signed x adds a correction before the shift. You can see that pattern in
optimised code as a srl by 31 followed by an addu and then the sra.
Can you now explain it?
Logic works bit by bit under a mask: and keeps, or sets, xor flips, nor inverts. Shifts move bits; what fills the gap is the whole difference: zeros (sll, srl), the sign (sra) or the fallen bits (rotr). Register-count shifts read the value from rt and the count from rs.
If you remember only three things
- A mask chooses the bits; the operation says what happens to them. andi v0,v0,0xff keeps a byte. nor with $zero is the missing not.
- Three right shifts, three fills. srl fills zeros (unsigned divide), sra fills the sign (signed divide), rotr fills the fallen bits. sll is the only left shift.
- The same opcode and funct can hide two instructions. srl and rotr differ only in rs; srlv and rotrv only in sa. A decoder must test every stated field.
Now try to explain this one yourself: a C program computes x >> 3 with
x an unsigned int. It also computes y >> 3 with y an int. Which shift
does the compiler use for each? What would go wrong if it swapped them?
Go deeper: a model answer, once you have tried
unsigned gets srl: an unsigned value has no sign bit, and its top bits
must become zeros. int gets sra: bit 31 is the sign, and dividing a
negative number must keep it negative. Swap them and two things break. sra
on a large unsigned value (bit 31 set) would fill ones and produce a wrong,
huge result. srl on a negative int would turn −8 into 536870911 instead of
−1. The types decide, and the compiler never guesses.
Check your understanding
0/5 answered1.x is a signed int that may be negative. Which instruction computes x / 8 (rounding down)?
2.What does `nor $t0,$zero,$zero` put in $t0?
3.In `sllv $t0,$t1,$t2`, which register holds the shift count?
4.What does `andi v0,v0,0xff` do, and why does the compiler emit it?
5.`srl $t0,$t1,4` and `rotr $t0,$t1,4` differ in one field of the word and in one thing they do. Which?