Logical and Shift Operations
COMP273 McGill 1
Up Until Now
• Up until now, we’ve done
– Arithmetic: add, sub,addi
– Memory access: lw and sw
– branches and jumps: j, jr, jal, beq, bne
• These instructions view contents of register as a single quantity (such as a signed or unsigned integer)
COMP273 McGill 2
Bitwise Operations
• View contents of register as 32 independent bits
– Since registers are composed of 32 bits, we may want to access individual bits (or groups of bits) rather than the whole.
• Two new classes of MIPS instructions for bitwise operations: – Logical Operators
– Shift Operators
COMP273 McGill 3
Bitwise Operations
• Truth Table: lists all combinations of inputs and outputs
AND: outputs 1 if both inputs are 1
OR : outputs 1 if at least one input is 1 NOR: outputs 1 if both inputs are 0
A
B
AND
OR
NOR
0
0
0
0
1
0
1
0
1
0
1
0
0
1
0
1
1
1
1
0
COMP273 McGill 4
Bitwise Operations
• Bitwise result applies function to each bit independently • The ith bit of inputs produce the ith bit of outputs
Bit-wise AND
AND( 01101001,
11001100 )
= 01001000
Bit-wise OR
OR ( 01101001,
11001100 )
= 11101101
A
B
AND
OR
NOR
0
0
0
0
1
0
1
0
1
0
1
0
0
1
0
1
1
1
1
0
Boolean function applied at each bit position
COMP273 McGill
5
MIPS Logical Operators
6
MIPS Logical Operations • MIPS Logical Operators are bitwise operations
• Basic MIPS logical operators
Syntax
and TargetReg, SourceReg1, SourceReg2
or TargetReg, SourceReg1, SourceReg2
nor TargetReg, SourceReg1, SourceReg2
• Like many MIPS instructions, logical operations accept exactly 2 inputs and produce 1 output
COMP273 McGill
7
Use Logical Operator in Conditional Statement • Conditional statements
$t0 = 0000 0000 0000 0000 0000 0000 0000 0001
$t1 = 0000 0000 0000 0000 0000 0000 0000 0000 $t0 and $t1 = 0000 0000 0000 0000 0000 0000 0000 0000
// C
if ( A < 0 && B < 0 ) {
...
}
# MIPS code
slt $t0, $s0, $zero # $t0 = $s0 < 0? slt $t1, $s1, $zero # $t1 = $s1 < 0?
and $t2, $t0, $t1 # $t2 = ( $s0 < 0 && $s1 < 0)?
COMP273 McGill 8
Use Logical Operator in Conditional Statement • Conditional statements
$t0 = 0000 0000 0000 0000 0000 0000 0000 0001
$t1 = 0000 0000 0000 0000 0000 0000 0000 0000 $t0 or $t1 = 0000 0000 0000 0000 0000 0000 0000 0001
// C
if ( A < 0 || B < 0 ) {
...
}
# MIPS code
slt $t0, $s0, $zero # $t0 = $s0 < 0? slt $t1, $s1, $zero # $t1 = $s1 < 0?
or $t2, $t0, $t1 # $t2 = ( $s0 < 0 || $s1 < 0)?
COMP273 McGill 9
Logical Operators with Immediate
• Similar to and, or, nor, but the third argument is an immediate
Syntax
andi TargetReg, SourceReg, Immediate
ori TargetReg, SourceReg, Immediate
COMP273 McGill 10
NOR for NOT
• Boolean expressions are made with AND and OR and NOT
• Why is NOT not a MIPS instruction?
– NOT takes one operand and produces one result, which is not in
keeping with the three-operand format of other instructions – How do we do NOT with NOR?
$zero
Input
NOR
0
0
1
0
1
0
nor $t1, $t0, $zero
COMP273 McGill 11
Mask
An Application of Logical Operators
No, not this
12
one
Use AND for Mask • Any bit and 0 produces an output 0
0
Input
AND
0
0
0
0
1
0
• Any bit and 1 produces the original bit
This can be used to create a mask.
1
Input
AND
1
0
0
1
1
1
COMP273 McGill
13
Example:
Use AND for Mask
A = 1011 0110 1010 0100 0011 1101 1001 1010 B = 0000 0000 0000 0000 0000 0000 1111 1111 A and B= 0000 0000 0000 0000 0000 0000 1001 1010
• In this example, B is called a mask.
• B is used to isolate the rightmost 8 bits of A by masking out
the rest of the string (e.g., setting it to all 0s)
• Thus, the and operator can be used to set certain portions of a bitstring to 0s, while leaving the rest alone.
COMP273 McGill
14
Use AND for Mask
Example: If A = 0xB6A43D9A is saved in $t0, then what is $t1 and $t2 after the following instructions?
OMP273 McGill
15
andi $t1, $t0, 0xFF
$t0 = 1011 0110 1010 0100 0011 1101 1001 1010
0xFF = 0000 0000 0000 0000 0000 0000 1111 1111
$t1 = 0000 0000 0000 0000 0000 0000 1001 1010
$t0 = 1011 0110 1010 0100 0011 1101 1001 1010 0x000000FF = 0000 0000 0000 0000 0000 0000 1111 1111
= 0x9A
andi $t2, $t0, 0x000000FF
$t2 = 0000 0000 0000 0000 0000 0000 1001 1010 = 0x9A
C
Uses OR for Mask • Any bit or 0 produces the original bit
0
Input
OR
0
0
0
0
1
1
• Any bit or 1 produces 1
This can also be used to create a mask.
0
Input
OR
1
0
1
1
1
1
COMP273 McGill
16
Uses OR for Mask
• Can be used to force certain bits of a string to 1s.
Example: if $t0 contains 0x12345678, then after
ori $t1, $t0, 0xFFFF
$t1 contains 0x1234FFFF (high-order 16 bits are untouched, low-order 16 bits are forced to 1s).
$t0 = 0001 0010 0011 0100 0101 0110 0111 1000
0xFFFF = 0000 0000 0000 0000 1111 1111 1111 1111
$t1 = 0001 0010 0011 0100 1111 1111 1111 1111
COMP273 McGill 17
Shift Operators <<<<<<<<<
18
Shift Logical Instructions
• Shift Instruction Syntax:
Operation TargetReg, SourceReg, ShiftAmount
1) Operation: operation name
2) TargetReg: register that will receive value
3) SourceReg: register that contains the original value
4) ShiftAmount: shift amount (non-negative constant < 32)
COMP273 McGill
19
Shift Logical Instructions • Shiftleftlogicalsll
– shifts left and fills emptied bits with 0s
sll TargetReg, SourceReg, ShiftAmount
• Shiftrightlogicalsrl
– shifts right and fills emptied bits with 0s
srl TargetReg, SourceReg, ShiftAmount
COMP273 McGill 20
Shift Logical Instructions
Example:
Assume $t0 contains 0001 0010 0011 0100 0101 0110 0111 1000 What are $t1 and $t2
COMP273 McGill
21
# shift right
srl $t1, $t0, 8
# shift left
sll $t2, $t0, 8
Shift Logical Instructions
$t0
$t1
Fill with eight 0s
Gone
0001 0010 0011 0100 0101 0110
0111 1000
# shift right
srl $t1, $t0, 8
0000 0000
0001 0010 0011 0100 0101 0110
0001 0010
0011 0100 0101 0110 0111 1000
# shift left
sll $t2, $t0, 8
$t0
Gone
$t2
0011 0100 0101 0110 0111 1000
0000 0000
COMP273 McGill
Fill with eight 0s
22
Shift Arithmetic Instructions • Shift right arithmetic sra
– Shifts right and fills emptied bits by sign extending
sra TargetReg, SourceReg, ShiftAmount
• Why? A negative number should stay negative after shifting – If MSB = 0, shift and fill the new bits with 0s
– If MSB = 1, shift and fill the new bits with 1s
COMP273 McGill 23
Shift Arithmetic Instructions
Example: SRA (shift right arithmetic) by 8 bits
$t3 = 0001 0010 0011 0100 0101 0110 0111 1000 $t4 = 1001 0010 0011 0100 0101 0110 0111 1000
What happen after shift right arithmetic by 8 bits?
sra $t5, $t3, 8
sra $t5, $t4, 8
COMP273 McGill 24
Shift Arithmetic Instructions
0001 0010 0011 0100 0101 0110
0111 1000
# shift right
sra $t5, $t3, 8
$t3
$t5
Fill with eight 0s
$t4
$t5
Fill with eight 1s
Gone
If MSB = 0, the new bit after shifting = 0
0000 0000
0001 0010 0011 0100 0101 0110
1001 0010 0011 0100 0101 0110
0111 1000
# shift right
sra $t5, $t4, 8
COMP273 McGill
25
Gone
1111 1111
1001 0010 0011 0100 0101 0110
If MSB = 1, the new bit after shifting = 1
Use Shift Instructions in Multiplication
• In decimal:
– Multiplying by 10 = shifting left by 1: 71410 x 1010 = 714010
– Multiplying by 100 =shifting left by 2: 71410 x 10010 = 7140010 – Multiplying by 10n = shifting left by n
• In binary:
– Multiplying by 2 = shifting left by 1: 112 x 102 = 1102
– Multiplying by 4 = shifting left by 2: 112 x 1002 = 11002 – Multiplying by 2n = shifting left by n
COMP273 McGill 26
Use Shift Instructions in Multiplication • Shifting maybe faster than multiplication!
– a good compiler usually notices when C code multiplies by a power of 2 and compiles it to a shift instruction:
→
• Likewise, shift right to divide by powers of 2
– Use sra but watch out for negative numbers as the result is rounded down
→
a = a * 8 ; // C
sll $s0, $s0, 3 # MIPS
b = b / 2 ; // C
sra $s1, $s1, 1 # MIPS
COMP273 McGill with $s1 = -3 answer is -2 27
Use Shift to Extract Information
• Suppose we want to isolate byte 0 (rightmost 8 bits) of a word stored in $t0
• Suppose we want to isolate byte 1 (bit 15 to bit 8) of a word stored in $t0.
• How do we “extract” the information?
COMP273 McGill 28
andi $t0, $t0, 0xFF
andi $t0, $t0, 0xFF00
Use Shift to Extract Information
0001 0010 0011 0100
0101 0110 0111 1000 0000 0000 0000 0000
0111 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
sll $t0, $t0, 16
srl $t0, $t0, 24
COMP273 McGill
29
0101 0110
0101 0110 0111 1000
0101 0110
Application: Pixel Data for Images
30
Example: Packing pixel data for images
• Suppose each pixel of an image has – Red r [0 ~ 255]
– Green g [0 ~ 255]
– Blue b [0 ~ 255]
– Alpha a, transparency value [0 ~ 255] COMP273 McGill
Each of them can be represeted by a byte (8-bit)
PNG
31
Example: Packing pixel data for images
PNG
• Instead of using 4 registers for r, g, b, and a, we pack each of 8 bits into a 32-bit integer
// C code
int packARGB ( int r, int g, int b, int a ) {
return a << 24 | r << 16 | g << 8 | b ;
}
COMP273 McGill 32
Example: Packing pixel data for images
// C code
int packARGB ( int r, int g, int b, int a ) { return a << 24 | r << 16 | g << 8 | b ;
}
# MIPS
sll $t0, $a3, 24 # shift a to the left or $v0, $t0, $zero # combine a with $v0
sll $t0, $a2, 16 or $v0, $t0, $v0 sll $t0, $a1, 8 or $v0, $t0, $v0 or $v0, $a0, $v0 jr $ra
# shift r to the left # combine r with $v0 # shift g to the left # combine g with $v0 # combine b with $v0 # return to $ra
COMP273 McGill
33
Example 2: Changing pixel formats
• ARGB to ABGR
– Write a conversion function (C or Java syntax):
int argb2abgr( int ARGB )
– Write function processImage to convert all pixels – Convert to MIPS assembly
.data
# reserve space for 256x256 display display: .space 0x40000
# filename of image to load
fname: .asciiz "wall-eImage.bin"
.text main:
jal loadImage
jal touchDisplay
jal processImage
li $v0, 10 # exit syscall
argb2abgr:
# TODO: finish this function
jr $ra
processImage:
# TODO: finish this function
jr $ra
COMP273 McGill 34
MARS Bitmap Display Tool
• Open and connect to MIPS
• For this example, change width to 256 • Base address is static .data segment
• Display updates when memory written
– Loading sets the memory, but not the display
– Must call another function to touch the memory for image to show
COMP273 McGill 35
Review
• Logical and Shift Instructions operate on bits individually, unlike arithmetic, which operate on entire word
• Use Logical and Shift Instructions to isolate fields, either by masking or by shifting back and forth
• New Instructions:
– Logical: and, andi, or, ori, nor – Shift: sll, srl, sra
• Practice: try writing MIPS functions
• Textbook 2.6
COMP273 McGill
36