COMP2300/6300 Final Exam 2018
Student ID:
Reading time: 15 minutes
Writing time: 180 minutes
Permitted materials: one A4 page with notes on both sides
Make sure you read each question carefully. Some words have footnotes1 to clarify what they mean in the context of the question.
Questions are not equally weighted, and the size of the answer box is not necessarily related to the length of the expected answer or the number of marks given for the question.
All answers must be written in the boxes provided in this booklet. You will be provided with scrap paper for working, but only the answers written in this booklet will be marked. Do not remove this booklet from the examination room. There is additional space at the end of the booklet in case the boxes provided are insufficient. If you use these extra pages, make sure you clearly label which question the answer refers to.
Greater marks will be awarded for short, specific answers than long, vague/rambling ones. Marks may be deducted for providing information that is irrelevant to a question. If a ques- tion ask for you to “explain your answer”, make sure both your answer (e.g. yes/no) and your explanation are clearly indicated. If a question has several parts, you may answer the later parts even if you cannot answer the earlier ones.
u
1like this one!
For examiner use
1
COMP2300/6300 final exam S1 2018
Question 1 Instructions & encoding (25 marks total) Part 1 2.5 marks
True or false: the Arithmetic and Logic Unit (ALU) is responsible for reading and writing data in RAM memory.
Answer:
Part 2 2.5 marks
true false
mov r0, 0
maybe_infinite_loop:
adds r0, r0, 1
beq somewhere_else
b maybe_infinite_loop
If program execution enters the maybe_infinte_loop loop, will it ever exit (branch out of) the loop, or will it stay in the loop forever? You may assume that somewhere_else is a valid branch destination.
Answer:
• program execution will stay in the maybe_infinte_loop forever (i.e. it is an infinite loop)
• programexecutionwillexitthemaybe_infinte_loopeventually(i.e.itisnotaninfi- nite loop)
2
COMP2300/6300 final exam S1 2018
Part 3 5 marks
Using the T1 encoding for the rev instruction as shown above, fill out (in the boxes provided) the 16-bit bit pattern (0s and 1s) which represents the following line of assembly code:
rev r2, r6 Answer:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Part 4 5 marks
initial r0
31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 final r0
31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0
Assuming an initial bit pattern in r0 as shown in the diagram, write a sequence of one (or more) ARMv7 assembly instructions which will transform the initial r0 bit pattern into the final r0 bit pattern shown in the diagram.
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
3
COMP2300/6300 final exam S1 2018
Part 5 10 marks
In your own words, explain how the fetch-decode-execute cycle works on your discoboard. Be as specific as you can. You may include pictures/diagrams in your answer.
4
COMP2300/6300 final exam S1 2018
Question 2 Functions (25 marks total) Part 1 2.5 marks
√
foo(a,b,c)= (4a+b)c (1) Assume there is a (ARM) function foo which calculates the (mathematical) function above and
obeys the ARM Architecture Procedure Call Standard (AAPCS)2.
On entry to the function (i.e. immediately after the instruction “bl foo”) where will the value
of the argument c be found? Answer:
• inr0
• inr1
• inr2
• inr3
• inr4
• inr5
• onthestack
• inthe.datasection
Part 2 2.5 marks
You inherit a broken discoboard where the branch-with-link instruction bl does not work—if the program attempts to execute a bl instruction the discoboard will explode.
You come up with an idea for a workaround—a call assembler macro which could be used to make a function call like so:
call my_func @ equivalent to ”bl my_func” on a working discoboard
2which is the “standard” ARM calling convention, which we have been using all along in the course. 5
COMP2300/6300 final exam S1 2018
Which one of the following definitions of the call assembler macro is correct? That is, for which of these macros is call my_func equivalent3 to bl my_func?
Answer:
@ macro (a)
.macro call function_name mov lr, pc
b \function_name
.endm
@ macro (b)
.macro call function_name add lr, pc, 4
b \function_name
.endm
@ macro (c)
.macro call function_name add lr, pc, 4
bx lr
.endm
@ macro (d)
.macro call function_name mov r0, lr
bx lr
.endm
3In this question you can ignore any ARM/Thumb mode interworking issues, i.e. the Thumb bit. And if you don’t know what I’m talking about, don’t worry. The macro you’re looking for is the one which best represents (conceptually) what the bl instruction actually does.
6
COMP2300/6300 final exam S1 2018
Part 3 5 marks
The following code snippet is from a JavaScript-like language4 which compiles (without opti- misations) directly to ARMv7 machine code to run on your discoboard.
function bar() {
let x = 50;
let y = 3.14;
let blockchain = [1, 4, 6, 3, 6, 3, 6, 5, 3, 7, 7, 7, 8, 1, 5, -4]; let name = ”Satoshi”;
// *breakpoint*
// more code follows…
//
//
}
When a breakpoint is set on the *breakpoint* line (shown in the comment above) and the function bar is called, which picture best represents the state of bar’s stack frame at the *breakpoint* point in time, assuming that a descending stack is in use?
Answer:
higher memory addresses
lower memory addresses
(a) (b)
(c) (d)
4This is not JavaScript, it’s a simple, direct-compiled language with JavaScript-like syntax. 7
COMP2300/6300 final exam S1 2018
Part 4 5 marks
my-code.S
10010100
10100101
00101010
10010101
input output
A source file containing a valid sequence of ARM assembly instructions (e.g. my-code.S) is “assembled” into binary machine code by the assembler program in the usual fashion (as shown in the diagram, although it’s not to scale—there will be many more 0s and 1s than that).
If you cannot see the original source file my-code.S but you can see the binary machine code output, is it possible to determine whether the original source file contained a function call? Explain your answer—be as specific as you can. You may include pictures/diagrams in your answer.
8
COMP2300/6300 final exam S1 2018
Part 5 5 marks
In the same situation as Part 4 , is it possible to determine whether the original source file my-code.S contained an assembler macro? Explain your answer—be as specific as you can. You may include pictures/diagrams in your answer.
9
COMP2300/6300 final exam
S1 2018
Part 6 5 marks
Consider the triangular number5 function
∑n
(2)
Tn =
which takes a single positive integer argument n and returns the sum of all the integers from
k=1
k=1+2+…+n
1 up to n. As an example,
Here is a recursive function triangular in ARM assembly language which takes a single in-
T3 =1+2+3=6 (3) teger argument n (in r0) and returns Tn (also in r0):
triangular:
push {lr}
push {r0}
cmp r0, 1
beq end_triangular sub r0, r0, 1
bl triangular ldr r1, [sp] add r0, r0, r1
end_triangular:
add sp, sp, 4 pop {lr}
bx lr
Are there any disadvantages to this recursive approach compared to a non-recursive version of the same function? Explain your answer—be as specific as you can. You may include pictures/diagrams in your answer.
Answer on the next page.
5Don’t worry about why it’s called a triangular number—the point of this question is to think about how this function might be implemented in ARM assembly language.
10
COMP2300/6300 final exam
S1 2018
11
COMP2300/6300 final exam S1 2018
Question 3 Memory & data (25 marks total) Part 1 2.5 marks
After the following code has been executed, what is the value (in hex) in the 32-bit little-endian memory word at the address 0x20000004?
Answer:
• 0x114 • 0xF5 • 0x1F5 • 0xFF
Part 2 2.5 marks
After all the code in Part 1 has been executed, what is the value (in hex) in the register r0?
Part 3 2.5 marks
You spill coffee on your discoboard and the result is that 16 lines of the discoboard’s address bus are damaged, so that the 16 least-significant bits of the address register (i.e. the register holding the memory address) in any load or store instruction are always read as 0 (regardless of the value in the register).
True or false: the memory addresses 0x20000000 and 0x20000004 can both still be used in- dependently to load & store data in your programs.
mov r4, 0x15
mov r5, 0xFF
adds r6, r4, r5 ldr r0, =0x20000000 str r6, [r0, 4]!
Answer:
true
false
12
COMP2300/6300 final exam S1 2018
Part 4 2.5 marks
Assuming the same “damaged address bus” discoboard from Part 3 , what has happened to the size of the addressable memory space, i.e. the number of valid memory addresses?
Answer:
• the damaged discoboard has the same address space as a correctly-functioning6 dis- coboard
• thedamageddiscoboardhashalftheaddressspaceofacorrectly-functioningdiscoboard
• thedamageddiscoboard’saddressspacehasbeenreducedinsizeby16validmemory
addresses compared to a correctly-functioning discoboard
• the damaged discoboard’s address space has been reduced in size by a factor of 216
compared to a correctly-functioning discoboard
6a discoboard without a damaged address bus
13
COMP2300/6300 final exam S1 2018
Part 5 10 marks
The final marks & grades for COMP2300 will be calculated and recorded using a grading pro- gram running on Ben’s discoboard7. For every student, the grading program must store the student’s
• UID (e.g. u1234567)
• finalmark(outof100)
Describe a data structure which could be used to store this data for one student. Be specific about the size, layout and interpretation (e.g. width, signed/unsigned, offsets, etc.) of all the fields in the data structure. Your answer must include an example of the data structure in use (i.e. storing one student’s data). You may include pictures/diagrams in your answer.
You are not optimising for any particular criteria (e.g. minimum size, maximum read/write performance). You can design the data structure however you like, as long as it stores the UID & mark information as described above. The following ASCII table may be helpful, although you do not have to use it.
Answer on the next page.
7This isn’t actually true, but let’s just pretend it is for the purposes of this question. 14
COMP2300/6300 final exam
S1 2018
15
COMP2300/6300 final exam S1 2018
Part 6 5 marks
The grading program (using your “student mark” data structure from Part 5 ) gives correct results, but runs too slowly. If you were given the task of optimising the program for maxi- mum performance8 what changes would you make? You are able to make changes to the data structure and/or the grading program itself (i.e. Ben’s code). Be as specific as you can. You may include pictures/diagrams in your answer.
8i.e. so that it finishes in as few cycles as possible
16
COMP2300/6300 final exam S1 2018
Question 4 Networks & Operating Systems (25 marks total) Part 1 2.5 marks
When an interrupt is triggered, where is the value in the program counter (pc) stored so that it can be restored after the interrupt handler(s) returns?
Answer:
• inthestackpointerregister(sp) • onthestack(inmemory)
• inthelinkregister(lr)
Part 2 2.5 marks
The network protocols P1 and P2 are exactly the same except for the way they use their data line:
• inP1,arising-edgeonthedatalineisinterpretedbythephysicallayerasa1andafalling- edgeasa0
• inP2,afalling-edgeonthedatalineisinterpretedbythephysicallayerasa1andarising- edgeasa0
Assuming the exact same hardware and environment, which one of the following statements is true:
Answer:
• P1 will transfer data faster9 than P2
• P2 will transfer data faster than P1
• P1 will transfer data at the exact same rate as P2
9faster == more bits-per-second
17
COMP2300/6300 final exam S1 2018
Part 3 2.5 marks
You are writing an assembly program which will run as one task managed by a multitasking OS on your discoboard, and it needs to store some “private”10 data in memory (RAM).
True or false: the load/store exclusive instructions ldrex and strex can prevent other tasks from reading and writing your private data in memory.
Answer:
Part 4 2.5 marks
true false
True or false: an operating system must be at least 100Mb in size when compiled to machine code.
Answer:
true false
10This is just regular data—0s and 1s—but it’s data that you don’t want any of the other tasks running on the discoboard to be able to read or modify.
18
COMP2300/6300 final exam S1 2018
Part 5 5 marks
serial parallel
What are the advantages of a serial (single-wire) compared to a parallel (multiple-wire) net- work protocol? In which situation(s) would you prefer a serial protocol over a parallel one? Be as specific as you can. You may include pictures/diagrams in your answer.
19
COMP2300/6300 final exam S1 2018
Part 6 5 marks
Ok, now the opposite of Part 5 : what are the advantages of a parallel (multiple-wire) com- pared to a serial (single-wire) network protocol? In which situation(s) would you prefer a par- allel protocol over a serial one? Be as specific as you can. You may include pictures/diagrams in your answer.
20
COMP2300/6300 final exam S1 2018
Part 7 5 marks
A company sells a product called TweetyPotatoTM: a potato with a discoboard inside that is connected to the internet (each TweetyPotato has its own twitter account). The company’s engineers have written a new version of the TweetyPotato software and uploaded it to their deployment server ready to be uploaded to all the TweetyPotatoes in the world.
You are a bad person and have hacked into the company’s deployment server. You cannot change all of the code for the new version of the TweetyPotato software, but you can modify anything which will be mapped in the memory region from 0x0 to 0x07FFFFFF of the dis- coboard’s address space (up to—but not including—the executable code region which starts at 0x8000000).
Is it possible to modify the software to compromise11 the TweetyPotato devices? If so, how? If not, why not? Explain your answer—be as specific as you can. You may include pictures/diagrams in your answer.
11In this question, “compromise” means to make the TweetyPotato device execute any code you (the hacker) want, not just the code written by the company’s software engineers
21
COMP2300/6300 final exam
S1 2018
22
COMP2300/6300 final exam S1 2018
Note: you don’t have to use all of the following pages for your answer—the extra pages are included in case you need them for other questions (as described on the title page).
23
COMP2300/6300 final exam
S1 2018
24
COMP2300/6300 final exam
S1 2018
25
COMP2300/6300 final exam
S1 2018
26