ECS404: Computer Systems and Networks (2019)
Coursework 2 (10%)
Computer Architecture, Machine Language, MIPS Assembly
DUE DATE: WEDNESDAY 04 DECEMBER 2019, 10:00 AM
Instructions: Submit a single PDF file electronically to QM+ using the link on the coursework 2 section. Do not submit your work by emailing it to a member of staff.
The PDF can include scans of handwritten material but a typewritten version is encouraged
(even better if you use LATEX!).
Collaboration is NOT permitted when attempting the answers. High level discussion
when not attempting the questions may be fine.
Please be aware that systems can be busy and slow to respond shortly before deadlines. You
should aim to submit at least one hour before the final deadline.
Question 1
A programme in 32-bit MIPS Assembler is shown in the following:
1 . data
2 msg1 : . a s c i i z ”nnEnter the f i r s t i n t e g e r : ”
3 msg2 : . a s c i i z ” Enter the second i n t e g e r : ”
4 msg3 : . a s c i i z ” Result : ”
5 6
. t e x t
7 l i $v0 , 4 # s y s c a l l to p r i n t a s t r i n g
8 l a $a0 , msg1
9 s y s c a l l
10
11 l i $v0 , 5 # s y s c a l l to read an i n t e g e r
12 s y s c a l l
13 add $t1 , $zero , $v0
Page 2 ECS404U (2019-2020)
14
15 l i $v0 , 4 # s y s c a l l to p r i n t a s t r i n g
16 l a $a0 , msg2
17 s y s c a l l
18
19 l i $v0 , 5 # s y s c a l l to read an i n t e g er
20 s y s c a l l
21 add $t2 , $zero , $v0
22
23 LOOP:
24 s l t $t3 , $t1 , $t2
25 bne $t3 , $zero , DONE
26 sub $t1 , $t1 , $t2
27 addi $t0 , $t0 , 1
28 j LOOP
29
30 DONE:
31 l i $v0 , 4 # s y s c a l l to p r i n t a s t r i n g
32 l a $a0 , msg3
33 s y s c a l l
34
35 l i $v0 , 1 # s y s c a l l to p r i n t an i n t e g er
36 add $a0 , $t0 , $zero
37 s y s c a l l
38
39
| l i $v0 , 10 s y s c a l l | # s y s c a l l code to e x i t |
40 (a) Suppose when prompted at the console, we input numbers 13 and 3 . Provide
the trace of the values in registers $t1 and $t2 (as a pair) when this code is
executed until it finishes. That is, write down the new values in both $t1 and
$t2 each time either one of them changes as you step through the programme
until the programme finishes execution. You can choose to present the values either
in decimal, hex, or binary, as long as you clearly specify which.
[20 marks]
(b) Express in a simple sentence what this programme effectively does? (Your answer
should be a sentence starting like: “this programme takes two integers from the user
and computes . . . ” )
[10 marks]
(c) (Bonus – Optional) This program may not perform as intended if either one of the
entered numbers is negative. Fix the code so it works for negative numbers as well to
achieve the intended functionality.
[10 marks]
ECS404U (2019-2020) Page 3
Question 2
MIPS, memory access and Arrays
In all of the questions of this part, you are still only allowed to use beq or bne for branching,
and slt for comparison (no pseudo-instructions for branching). Also, try to reuse the
given code as much as possible. In particular, try to keep the name of the variables and
labels the same. For instance, use register $s0 to hold the value of the requested quantity.
Also, of course, your answer should not depend on the particular values that the array is
initialised with (these are just for your testing).
(a) The following code computes and prints the sum of the entries in the array A:
1 . t e x t
2
| l a lw l a | $t0 , A LENGTH $t0 , 0( $t0 ) $t1 , A | # t0 <- A LENGTH # t1 : to hold the ” address ” of the next # array element , i n i t i a l i s e d to the # address of the f i r s t byte of the array # s0 : w i l l hold the t o t a l sum, # i n i t i a l i s e d to zero |
| addi $s0 , $zero , 0 |
3 4 5 6 7 8 9
10 NEXT ARRAY ELEMENT:
11 beq $t0 , $zero , DONE # jump to DONE when reached array ’ s end
12
13
| lw $t2 , 0( $t1 ) add $s0 , $s0 , $t2 | # t2 <- the current array element # s0 <- s0 + t2 |
14 15
16
| addiu $t1 , $t1 , 4 | # t1<-t1 +4 , to get the address of # the the next element # decrementing t0 by 1 |
| addiu $t0 , $t0 , -1 |
17 18 19
20 j NEXT ARRAY ELEMENT # jump to NEXT ARRAY ELEMENT ( f o r loop )
21
22 DONE:
23
| addi $v0 , $zero , 1 | # set v0 to ” 1 ” to s e l e c t # ” p r i n t i n t e g e r ” s y s c a l l # a0 <- s0 ( the t o t a l sum) to be p r i n t e d # invoking the s y s c a l l to p r i n t the i n t e g e r |
| add | $a0 , $zero , $s0 |
| s y s c a l l |
24 25 26 27
28
| addi $v0 , $zero , 10 s y s c a l l | # set v0 to ”10” to s e l e c t e x i t s y s c a l l # invoking the s y s c a l l to a c t u a l l y e x i t ! |
29 30
31 . data
32
| A: | # our i n t e g e r array |
| . word . word . word | 1 -4 5 |
| . word | 0 |
| . word . word | 2 -5 |
33 34 35 36 37 38
Page 4 ECS404U (2019-2020)
39
| . word A LENGTH: | -3 . word | 7 | # the length of the array |
40 Codes/array sum.asm
Modify the code so that it prints the minimum of the elements.
[15 marks]
(b) (i) Describe a simple condition for a number to be (perfectly) divisible by 4 based on
the bit-sequence of its binary representation.
[5 marks]
(ii) Now, using this observation, modify the code in part (a), to print the number of
elements in the array that are NOT divisible by 4.
[10 marks]
Question 3
Simple arithmetic with bit shifting
(a) sll (shift left logical) is a MIPS instruction with the following description:
syntax : sll $rd, $rt, h
operation : Shifts the value in register rt left by the shift amount h (zeroes are shifted
in for the new h rightmost bits) and places the result in register rd.
Suppose that rt is a register that contains an integer (for the purposes of this
question, you can take this to be unsigned, but it could also be signed). Explain why
the instruction sll $rd, $rt, h has the effective of putting 2h ∗ rt in register rd.
An “excellent” answer will use algebra and the fact that if the bits in the register are
b31; : : : ; b0, then this represents Pi bi × 2i. A “good” answer could just use a couple
of well chosen examples to illustrate the principle. You may assume that there is no
issue with overflow, i.e., the result is still an integer in the appropriate range.
[5 marks]
(b) The following examples show how to compute multiplications with some (small)
constants using shifts and additions. Provide a short sequence of MIPS instructions
that will implement the multiplication operation given. Note that you are allowed to
use the add, sub and sll instructions, however, you must at most use as many
instructions as requested (and of course, you are not allowed to use any “multiply”
instructions.)
| (i) $t1 4×$t1 solved example 1: | (1 instruction) |
| sll $t1, $t1, 2 | |
| (ii) $t1 5×$t1 | (2 instructions) |
solved example 2:
ECS404U (2019-2020) Page 5
sll $t0, $t1, 2
add $t1, $t0, $t1
| (iii) $t1 16×$t1 (iv) $t1 12×$t1 (v) $t1 31×$t1 (vi) $t1 40×$t1 | (1 instruction) (3 instructions) (2 instructions) (3 instructions) | [3 marks] [4 marks] [4 marks] [4 marks] |
Question 4
Disassembling (reverse engineering from machine code)
Suppose a 32-bit MIPS processor is executing the following machine instructions (represented in Hex):
2002000b
20040044
0000000c
2002000b
2004004f
0000000c
2002000a
0000000c
(a) Using this MIPS Converter web app at https://www.eg.bucknell.edu/∼csci320/mips web/
(designed by three CS students at Bucknell University for their module!), disassemble
this machine code. In particular, for each machine code, identify the opcode, and
other relevant fields and the MIPS Assembly code, similar to the worked out example.
[10 marks]
Example:
• 2002000b
Binary : 00100000000000100000000000001011
Opcode : 001000 (addi)
Format : I
| rs rt | : 00000 : 00010 | ($zero) ($v0) |
| Immediate: 0000000000001011 | (11) |
Assembly : addi $v0, $zero, 11
(b) Now putting your disassembling together, what is the overall MIPS Assembly code?
[5 marks]
(c) What does this programme do (what do we expect when this programme is executed?)
[5 marks]