Homework answers / question archive / F28HS     Coursework 2 - Assembly 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

F28HS     Coursework 2 - Assembly 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

Computer Science

Share With

---

F28HS     Coursework 2 - Assembly

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.

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

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 policy^[1] 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.

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:

Thenhttps://gitlab-student.macs.hw.ac.uk/f28hs-2020-21/f28hs-2020-21-students/f28hs-2020-21-cwk2-asclone your fork on your own computer.           m 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. Remember 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

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 ...

1. 1. (4 points) Frequency table Parse the string character-by-character and increment the counters in the frequency table.
   2. (1 point) Powers of 10 table Compute 10^N for N from 0 to 9, storing the values in the powers ten memory locations (in the ten array).
   3. (2 points) Convert counts to ASCII Convert the frequency counts to ASCII character values.
   4. (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:
   1. (2 points) Implementation choices

Explain your algorithms, and your use of memory and registers to support those algorithms.

1. 2. (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 frequency table.

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 0 _{x7efff7e 0} is used to keep a count of the ’a’ character, then the memory cell for counting occurrences of the ’b’ character would be 0_x7efff7e4.

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.

 

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 lowlevel software.
• Detailed theoretical and practical understanding of hardware and operating system concepts, interfacing to low-level software.
• Practical skills in low-level, systems programming, with effective resource management.

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

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.

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.