F28HS Coursework 2 - Assembly Deadline: Week 8, 4 March, 2021

F28HS Hardware-Software Interface

Coursework 2: Character Frequency Count in ARM Assembly

Overview
You are to write a program in the ARM assembly language to count and display how often each character
occurs in the chorus of the Robert Burns poem, My Heart’s in the Highlands.

“Highlands,
My heart’s in the Highlands, my heart is not here, My heart’s in the
a-chasing the deer; Chasing the wild-deer, and following
the roe, My heart’s in the Highlands, wherever I go.”

Robert Burns, 1789.

A sample of the character count for this Robert Burns poem is:

0000000001 .
0000000001 ;
0000000001 C
0000000003 H
0000000001 I
0000000003 M
0000000011 a
0000000001 c
0000000007 d
0000000020 e
0000000001 f
0000000007 g
0000000017 h
0000000011 i
0000000006 l
0000000001 m
0000000011 n
F28HS Coursework 2 - Assembly, Page 2 of 10 Deadline: Week 8, 4 March, 2021

Plagiarism Policy
This coursework is individual work. It is not group work, and you are assessed individually. Therefore, the
code and report you submit for this lab must be entirely your own. You must not share your code with
other students, and you must not copy code solutions from others. The university plagiarism policy1 is
clear:

“Plagiarism involves the act of taking the ideas, writings or inventions of another person and
using these as if they were one’s own, whether intentionally or not.” Definition 2.1.

We run plagiarism software against all source code submissions, which identifies any code similarity
across multiple submissions. The disciplinary action for plagiarism is an award of an F grade (fail) for the
course. Serious instances of plagiarism will result in Compulsory Withdrawal from the university.

Lab Environment
The coursework requires you to write and test ARM Assembly code. Your technology options are:
CPUlater An online ARM CPU simulator (Questions 1 and 2).
Cross compiler and ARM emulator A command line based approach using GCC’s cross compiler and the
QEMU ARM emulator (Question 3, and also Questions 1 and 2 if you wish).
We have produced videos that show how to test and debug your ARM Assembly code:
• Using CPUlator
https://web.microsoftstream.com/video/da46cf13-3427-4e0a-93d4-bcf04caf2a6c
• Running ARM Assembly remotely on the command line
https://web.microsoftstream.com/video/b4b1cd84-2d0c-4c60-852f-c3a31630d034
We recommend:
Linux users install GCC’s cross compiler; install QEMU; log in remotely to university’s servers with ssh;
use the CPUlator for debugging Questions 1 and 2.
Mac OSX users install GCC’s cross compiler; install QEMU; log in remotely to university’s servers with ssh;
use the CPUlator for debugging Questions 1 and 2.
Windows users log in remotely to university’s servers with Putty; use the CPUlator for debugging Ques-
tions 1 and 2.

Asking for help

You can discussion ideas and ask questions about how to implement this coursework on Discourse:
https://discourse.macs.hw.ac.uk/c/F28HS/51
As with coursework 1, you can also ask for help directly next to your partially written code on GitLab. A
video tutorial is here.

1 https://www.hw.ac.uk/uk/students/doc/plagiarismguide.pdf
F28HS Coursework 2 - Assembly, Page 3 of 10 Deadline: Week 8, 4 March, 2021

ARM Assembly Programming: Character Frequency Count

This coursework involves writing a program in the ARM assembly language to count and display how often
each character occurs in a string.

Starter code
You are provided starter files, which is a template for your solution.
Fork this project:
https://gitlab-student.macs.hw.ac.uk/f28hs-2020-21/f28hs-2020-21-students/f28hs-2020-21-cwk2-asm
Then clone your fork on your own computer.
If you are using a terminal window, clone your fork (replacing username) with:

git clone git@gitlab-student.macs.hw.ac.uk:username/f28hs-2020-21-cwk2-asm.git

Make sure that you can compile the starter code, or at least compile it with the web based CPUlater,
before you start making changes.
As you progress through the coursework, push your work to GitLab. This will ensure that you don’t lose
your work, and also enables you to ask for help directly next to your code on the GitLab website. Remem-
ber to create small incremental improvements with git commits, and refer to the coursework question
(listed below) that the commit is working on. When you push your commits, GitLab will check that your
files can be compiled.
Question 1 and 2 can be debugged using CPUlator. You should comment out any software interrupt
instructions (SWI) before simulating it in CPUlator. Question 3 requires reading from a text file so can’t be
tested with CPUlator. Instead, for Question 3 remotely log into the university’s Linux servers and run it in
a terminal window (video tutorial above).

Submission
To submit coursework 2, push your code to your fork of f28hs-2020-21-cwk2-asm, to the MACS GitLab
Student server.
Your project on GitLab should include:

freq-hard-coded.s Your implementation of character frequency count for a hard-coded string (Questions
1 and 2).
freq.s Your implementation of character frequency count for the contents of a file (Question 3).
Report.md Your report describing your implementation.

Report Format
For the last question for this coursework, you are to write a report about your implementation.
To do this, in Report.md write about:

1. Algorithm design and implementation choices.

2. Program design.
3. The output from running your program.

Use Markdown syntax in the Report.md file. GitLab will render your markdown syntax nicely. For
instruction on markdown syntax, follow: https://www.markdownguide.org/basic-syntax
F28HS Coursework 2 - Assembly, Page 4 of 10 Deadline: Week 8, 4 March, 2021

Requirements
1. Design and implement frequency count. Your implementation for this question should be developed
in the freq-hard-code.s file. Your code should process the hard-coded poem string at the end of the
freq-hard-coded.s file. Your program should run like this:

$ ./freq-hard-coded
0000000032
0000000003 '
0000000006 ,
0000000002 -
etc ...
(a) (4 points) Frequency table Parse the string character-by-character and increment the counters
in the frequency table.
(b) (1 point) Powers of 10 table Compute 10N for N from 0 to 9, storing the values in the powers ten
memory locations (in the ten array).
(c) (2 points) Convert counts to ASCII Convert the frequency counts to ASCII character values.
(d) (3 points) Print the frequency table Display the count for each character in the format:
<count> <space> <character> <newline character>
e.g.
0000000017 h
2. (2 points) Filter unused characters When printing the character frequencies, avoid printing informa-
tion about ASCII characters that do not appear in the input string. E.g. do not print this line:
0000000000 z
In your ARM Assembly code, add documentation next to the code that adds this functionality to make
it clear where your code is for this Question 2.
3. (4 points) You should extend your program to support the character frequency count for any input
string stored in a file. Your implementation for this question should be developed in the freq.s file.
You should only start on this when you have a fully working solution to Questions 1 and 2, since you
will be unable to use CPUlator to debug your character frequency count algorithm from this point.
For processing the provided RobertBurns.txt file, your program should run like this:

./freq RobertBurns.txt
0000000001
0000000032
0000000003 '
0000000006 ,
0000000002 -
etc ...

4. Report In the Report.md file:

(a) (2 points) Implementation choices
Explain your algorithms, and your use of memory and registers to support those algorithms.
(b) (2 points) Program design
Describe the structural layout in your freq-hard-coded.s file. If you attempted Question 3, also
describe the structural layout for adding the functionality of parsing file content into the fre-
quency table.
F28HS Coursework 2 - Assembly, Page 5 of 10 Deadline: Week 8, 4 March, 2021

Important Document your Assembly code with comments. To ensure you get all the marks you deserve
for your efforts, in those comments refer to the question number that the code beneath each comment
is implementing e.g. @ closes the file (Q3).

Marks
Question: 1 2 3 4 Total
Points: 10 2 4 4 20

Algorithm
We recommend you base your algorithm design and implementation on the following procedure:
• Phase 1: string processing
– Consume one character at a time, either from the hard-coded string (pointed to by the robert burns
label) for Questions 1 and 2 or from a file (Question 3).
– For each character in the string, increment the counter in the frequency table for that character.
– Close the input file (Question 3 only).
• Phase 2: printing the character frequencies
– For each character in the frequency table, print out the count and the character e.g.
0000000017 h
It is fine if you wish to deviate from this algorithm. If you do, say why in your Report.md file, e.g. if you
have a more efficient algorithm (either shorter runtime or using less memory).
There are 128 characters in the ASCII table, that may appear in the string. You could approach designing
and implementing your algorithm by creating a continuous region in memory for the character counting.
We’ll refer to this as the “frequency table”. That memory region you could split into 4 bytes, since storing an
integer (to count each character) requires 4 bytes. For example if the memory cell at address 0x7efff7e0
is used to keep a count of the ’a’ character, then the memory cell for counting occurrences of the ’b’
character would be 0x7efff7e4.
The next page visualises the complete workflow.

Program design
Your program is likely going to need:

• A decision on which registers R0-R12 you will use, and for which algorithmic variables.
• Control flow to ensure that you complete each algorithmic component in phases 1 and 2, before
moving onto the next algorithmic component.
• Areas reserved in memory to communicate data to/from POSIX system function calls (see Hint8!).
• Sub routines that perform system function calls, e.g. read for reading file content (Question 3) and
write for displaying frequency counts to the terminal window (Questions 1-3). Remember to use the
Link Register to return to the correct next instruction after these sub routines are executed.
• Sub routines to print formatting characters in the output. E.g. you will need to print the ’ ’ character
to separate the count and the character, and the newline character to separate the output for each
character.
F28HS Coursework 2 - Assembly, Page 6 of 10 Deadline: Week 8, 4 March, 2021
F28HS Coursework 2 - Assembly, Page 7 of 10 Deadline: Week 8, 4 March, 2021

Hints
• Hint1! You might find it useful to write sub routines to display a space and a newline.
• Hint2! If a sub routines calls other sub routines, values in registers may become corrupted/overwritten.
To avoid this possibility, you should always save and restore the registers before and after calling
the sub routine. This is especially the case when calling system functions, which use registers R0,
R1 and R2 for their formal parameter values.
• Hint3! Sometimes it is easier to maintain variables in memory rather than in registers:
LDR Ri, =variable
LDR Rj, [Ri]
@ do stuff to value Rj ...
STR Rj, [Ri]

This is the only way to communicate data between system calls and your ARM Assembly code (e.g.
read and write system functions), see Hint8!.
• Hint4! To increment a word pointer, e.g. a memory address, add 4 not 1.
• Hint5! Don’t try to write the whole program at once! Write it in stages and get each one working
before moving on to the next one.
• Hint6! Do make extensive use of the CPUlater online simulator to inspect registers and memory
values during program development. There are many examples of CPUlater in video tutorials and
the ARM Assembly video lectures.
• Hint7! If using CPUlator to debug your ARM ASM code, comment out any software interrupt calls
(SWI) (i.e. for calling system functions) as this resets the CPUlator’s state.
• Hint8! If you are calling POSIX system functions, you must use memory to communicate data to/from
the call. E.g. when printing an ASCII value with the write call you need to tell that function the
memory address of the ASCII value to print, after you’ve written data to memory at that address.

F28HS Learning Objectives in Coursework 2

Syllabus
• Low-level, assembler programming.
• Operating system interfaces for low-level software.
• Operating system concepts such as device handling, interrupts, BIOS etc.
• Embedded systems programming.
• Resource-conscious programming techniques.

Learning outcomes
• Critical understanding of computer architecture concepts and their performance implication for low-
level software.
• Detailed theoretical and practical understanding of hardware and operating system concepts, inter-
facing to low-level software.
• Practical skills in low-level, systems programming, with effective resource management.
F28HS Coursework 2 - Assembly, Page 8 of 10 Deadline: Week 8, 4 March, 2021

Appendix A: Frequency Counts for the Robert Burns Poem

0000000001

0000000032
0000000003 '
0000000006 ,
0000000002 -
0000000001 .
0000000001 ;
0000000001 C
0000000003 H
0000000001 I
0000000003 M
0000000011 a
0000000001 c
0000000007 d
0000000020 e
0000000001 f
0000000007 g
0000000017 h
0000000011 i
0000000006 l
0000000001 m
0000000011 n
0000000005 o
0000000010 r
0000000009 s
0000000011 t
0000000001 v
0000000003 w
0000000004 y
F28HS Coursework 2 - Assembly, Page 9 of 10 Deadline: Week 8, 4 March, 2021

Appendix B: Strings in Memory

Here is the memory content for the “coooow” string (the test string ASCII):

Here is the memory content for the Robert Burns poem (the robert burns ASCII):

You can see this for yourself by loading in the freq-hard-coded.s file into CPUlator.
F28HS Coursework 2 - Assembly, Page 10 of 10 Deadline: Week 8, 4 March, 2021

Appendix C: Relevant learning Material

For the two phases of the recommended algorithm, below is a list of the ARM Assembly programming
lectures 1-5 and their corresponding GitLab projects, to help you complete each task.

Learning Material for algorithm phase 1

• Control flow with comparison and branching
– Lecture 1: comparison, flags, branches.
– Lecture 4: sub-routines, parameter passing.
• String processing
– Lecture 3: strings, computing the length of a string example.
– GitLab project for lecture 3: string-length.s. This code shows how to traverse a string in
memory, starting at the 1st character then moving character-by-character to the last character.
• Arrays, for the frequency table and power-of-10 table
– Lecture 2: memory allocation, memory access
– Lecture 3: arrays
– GitLab project for lecture 3: static-array.s
• Reading the content of a file (Question 3)
– GitLab project for lecture 5: fcopy.s
Learning Material for algorithm phase 2
• Converting decimal values in memory to ASCII for printing the counts
– Lecture 5: printing decimals using a power-of-10 table and repeated subtraction
– GitLab project for lecture 5: power10table.s and print-decimal.s
• System calls, for printing character frequencies (Question 1) and reading file contents (Question 2)
– Lecture 5: software interrupts, POSIX system calls, file IO
• Printing ASCII values to the terminal window
– GitLab project for lecture 5: copy-keyboard.s