CS计算机代考程序代写 compiler assembly Java mips Logical and Shift Operations

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