Resit Coursework — Systems Programming in C and ARM Assembler
Resit Coursework — Systems Programming in C and ARM Assembler
1 Overview
The aim of this coursework is to develop a simple, systems-level application in C and ARM assembler. The ARM code should run on the CPUlator. The C code can run on any Linux platform.
The learning objective of this coursework is for students to obtain understanding of the interaction beween embedded hardware and external devices, in order to control this interaction in low-level code. The programming skills will cover detailed resource management and time sensitive operations. Design choices regarding languages, tools, and libraries chosen for the implementation need to be justified in the accompanying report. This coursework will develop personal abilities in articulating system-level operations and identifying performance implications of given systems through the written report that should accompany the complete implementation.
The report needs to critically reflect on the software development process for (embedded) systems programming and contrast it to mainstream programming.
Screencasts with explanations of the CW spec are available in a short version and in a long version .
The gitlab repos for the coursework are here for the C code and here for the ARM Assembler code .
2 Lab Environment
No physical or remote lab access is required for the CW. The programming can be done on a local machine for the C part, and on the online CPUlator for the Assembler part (see below). If needed, the departmental machine jove can be used via ssh or x2go, and has all necessary software installed to do the C programming, and it supports cross-compilation for ARM so that most of the Assembler programming can be done there as well (except for programming the HEX display).
The C coding for this coursework can be done on a local machine, or in the MACS VM, that has a C compiler, and the gcc compilation toolchain (including assembler and linker) installed. No external devices are programmed and no hardware specific aspects need to be considered for the C coding.
The ARM Assembler coding is best done on the web-based, online CPUlator. The hardware specific aspects of programming the HEX device, will only run on the CPUlator, or directly on hardware with the DE1-SOC by Altera.
Part 1: C Program: Cracking a Rotation Cipher
The goal of this part of the CW is to develop a program that can crack a simple rotation cipher. See the series of exercises and screencasts on developing a simple rotation cipher (rot13): Week 7 of the F28HS course and this gitlab repo with Version 0 of a sequence of exercises. The C code for the rotation cipher can be taken from these exercises.
Given: a cipher text (a text after application of a rotation cipher), and a dictionary of words, that covers all words in the plain text;
Find: the key for the rotation cipher that can be used to decrypt the plain text, and print the key (if found) together with the plain text.
Ciphertext: gur dhvpx oebja sbk whzc bire gur ynml qbt
Figure 1: Idea for the algorithm trying to find the decryption key
Assumptions: The following assumptions can be made on the input text. All words in the original plain text are lower case words and each word is contained in the given dictionary (in words.txt). The words are separated by exactly one space symbol and there are no punctuation symbols in the plain text. The space symbol is unmodified by the encryption/decryption (as can be seen from the given encryption function in the template code). Note that the given encryption function can be used for both encryption and decryptions: if the key for encrypting is N, then the key for decrypting is 26−N.
Idea: The main idea of the algorithm to crack the cipher is to do a brute force search through a dictionary for words, that, when encrypted, give the current word in cipher text. This needs to be checked for all possible rotation values of 1–26. This is feasible, since typically only a few words will be mapped to a cipher word for any of the possible keys. The correct key needs to map dictionary words to all of the words in the cipher text.
Figure 1 shows the main idea of the algorithm: An outer loop should iterate over all cipher words. In an inner loop try all possible keys (1–26) on the current cipher word and check whether the resulting word is in the dictionary. If this is the case, the key is a candidate for decrypting the entire cipher text. In this case, use the candidate key to try and decrypt the entire ciphertext. If every decrypted word in the cipher text is in the dictionary, then we can assume that the candidate key is valid decyption key, and we can terminate the search. Return the key and print it as the result.
Structure of the Algorithm: The template in the gitlab repo contains the basic code structure to be used in this brute force search. The filename for the dictionary (words.txt) can be hard-coded in the program. The main functions are:
• int crack_rot(char **dict, char **text)
this is the top level function for cracking the rotation cipher; it takes the dictionary as an array of strings (i.e. pointer to characters) and the cipher text, split into words, also represented as an array of strings.
• int try_key(char **dict, char **text, int key)
this function takes the dictionary, as an array of words, the cipher text, also as an array of words, and the candidate key as input, and tries do decipher each work int text with the key; if each deciphered word is in the dictionary, we have found the key and return it as the result; otherwise a value of −1 should be returned.
• char** read_dictionary(char *fname)
this function takes the filename of the dictionary as input, reads all words from the file (one word per line), and returns an array of words, containing all the words from the dictionay, as a result
• void rotN(char *str, int n)
this is an implementation of the rotation cipher, and encripts the string str with the key n; it performs the encryption in-place, i.e. the result of the execution is a modified string str containing the ciphertext of the input.
• char** str_to_arr_words (char *str)
this is an auxiliary function that takes a string as an input, which is either a plain text or cipher text string, breaks it into words and returns an array of these words as a result; the words in the input string are separated by exactly one space, use only lower case letter, and there are no punctuation symbols in the text.
• void show_arr_words (char **arr_words)
this is an auxiliary function that prints all words in the given array of words; it’s not needed for the main functionality of the code, but very useful for testing.
Support files: For an example how to read all lines from a file, using the POSIX function getline, see the getlineexample.c. Use this function in your code to read all words from the dictionary words.txt, and store the words in an array of strings in the code. The program should be able to process several ciphertexts in one execution, taking a file with one ciphertext per line as input. The file filein.txt is a sample file of such ciphertexts. The script test.sh tests the execution of the program with the filein.txt input file. This script can be run from the command line, without arguments. It is also automatically executed when uploading a new version of the code into the gitlab repo.
Interface: The program should run from the command-line and use the following options:
./crack_rot [-h] [-v] [-d] [-f <filename>] [<key> <plaintext>]
The -h options should print a short help message and terminate. The -v option should enable verbose output, about files read and keys tested. The -d option should enable debugging output, with more detailed output that can be used for debugging. The -f options should provide the file filename as an input file (see below).
If no arguments are provided, the program should use a hard-coded ciphertext in the main function, and try to crack the cipher (see existing template code for an example). If a key and plaintext argument are provided, then the program should encrypt the plaintext with the key and print the ciphertext. This is useful for generating test cases, but is not used in the main functionality of the algorithm. If the option -f is provided with a filename, then this filename should contain a list of ciphertexts, one on each line, and each cipher text should be cracked in turn by the main algorithm above. For each ciphertexts the key and the decrypted text should be printed. Below is the expected output, using the filein.txt sample file from the repository. Use exactly this output format: the test.sh script uses this format to check the results automatically, when uploading in the gitlab repo and you can check the CI-pipeline to see whether your implementation produces the expected result.
# ./crack_rot -f filein.txt
Key: 13
Testing
Cipher text: ’gur jbeq vf guvf’ Cracked text: ’the word is this’ with cracked key: 13
Key: 13
Testing
Cipher text: ’gur dhvpx oebja sbk whzc bire gur ynml qbt’ Cracked text: ’the quick brown fox jump over the lazy dog’ with cracked key: 13
Key: 13
Testing
Cipher text: ’gur yvggyr gbja snqr njnl vagb pbhagel ba bar fvqr pybfr gb gur ragenaprjnl Cracked text: ’the little town fade away into country on one side close to the entranceway with cracked key: 13
Key: 7
Testing
Cipher text: ’aol xbpjr iyvdu mve qbtw vcly aol shgf kvn’ Cracked text: ’the quick brown fox jump over the lazy dog’ with cracked key: 7
Key: 20
Testing
Cipher text: ’yllihyiom wixy cm nby miolwy iz uff ypcf’ Cracked text: ’erroneous code is the source of all evil’ with cracked key: 20
Key: 17
Testing
Cipher text: ’sv sfcu reu xf nyviv efsfup yrj xfev svwfiv’ Cracked text: ’be bold and go where nobody has gone before’ with cracked key: 17
Testing: Test Part 1 by running the above command from the command-line and put a screenshot of the result in your report. The expected output is also available in the repository file fileout.txt. Also, generate your own input file (using key and plaintext arguments in the command line above) and test your program with a 5-line input file. Use the script test.sh from the command line for automatic testing:
# sh ./test.sh
and check that it ends with a line like
2 of 2 tests are OK
Part 2: ARM Assembler Program: 2 Button counters
Implement counters for the two right-most buttons on the CPUlator in ARM Assembler and display the counters on the 2 rightmost HEX displays. The ARM Assembler code should probe for button presses of the two right-most buttons, labelled 0 and 1 on the CPUlator, keep counters for the number of button presses detected and display the two counters, each as a two digit number, on the HEX displays of the CPUlator. Continuously pressing one button should increment the counter, i.e. it’s not necessary to check for distinct button presses. The gitlab project with a template for the ARM Assembler code is here. .
The starting point for the code is the sample source code for counting button presses from the course. This code also has a delay function which should be used in the main counting loop. This code needs to be extended to check for two buttons, and keep counters separate. These counters need to be kept in main
Figure 2: Example of running the ARM Assembler program for counting button presses
memory, and not just in a register. For displaying the numbers on the HEX displays, the divrem sample source code from the course is useful: it allows to split an integer value into its digits.
The gitlab repo for this ARM Assembler part of the coursework contains a template file with a suggested structure, and with the delay function. It is recommended that you implement these subroutines:
- divrem
this is an auxiliary function, computing divisor and remainder for the values in registers R0 and R1
• show_counters
this function should iterate over the counters for the button presses, and display each counter using the functions below;
• show_counter
this function should take the number of the button in register R0 as input and display its counter using the function below;
• show2digits
this function should take the two digits of the counter in registers R0 and R1 and display the values on two HEX displays
Figure 2 shows an example of running the program, highlighting the buttons to press and the HEX display to use for displaying the counters.
Testing: Test Part 2 by running it on the CPUlator and include a screenshot of the running application in your report.
3 Submission
You must submit the complete project files, containing the source code (separate files for the C and for the ARM Assembler code), a stand-alone executable of the C program, and the report (in .pdf format) as one .zip file no later than 3:30 PM on Thursday 5th August 2021. You should also submit the C code and ARM Assembler code in separate files by pushing to a forked version for each of the 2 gitlab repositories (one for the C and one for the ARM Assembler part of the CW). Submission must be through Vision (find the “Resit Assessment” item in the top-level ”Assessment” section), submitting all of the above files in one .zip file. This resit coursework is worth 100% of the course’s mark.
You are marked for the functionality of the application, but also for code quality and the discussion in the short report. The marking scheme for this project is attached. This project should be done individually.
4 Report Format
The report should have 1 – 4 pages and needs to cover the following:
- A short discussion of the code structure, specifying the functionality of the main functions (for each of the C and Assembler part)
- A discussion of the behaviour of the main functions in the C and Assembler programs, realising the specified behaviour.
- A sample execution of the program in debug mode (see Testing discussion above)
- A summary, covering what was achieved (and what not), outstanding features, and what you have learnt from this coursework
Marking Scheme
| Criteria | Marks |
| Meeting system requirements and functionality (as specified in Part 1 and 2 of this document) | 60 |
| Report Quality
Contents matching the structure in Section 4; discussion of program logic (C) and of the core Assembler functions; summary of learning outcomes achieved. |
10 |
| Code Quality
Code quality (both C and ARM Assembler), clear function interfaces, sufficient comments. |
30 |
| Total marks | 100 |
Professional Conduct and Plagiarism
This is a individual project, and you will have to submit your own, original solution for this coursework specification, consisting of a report, the source code and an executable. Where external resources have been used, these need to be clearly identified and referenced.
A check on source code plagiarism will be performed on all submissions. Confirmed plagiarism will result in disciplinary procedures depending on the scale of misconduct.
Plagiarism:
This project is assessed as an individual project. You must work on your own and not share work with other students on this course. You can discuss general technical issues related to this work with other students, however, you must not share concrete pieces of code or text. Readings, web sources and any other material that you use from sources other than lecture material must be appropriately acknowledged and referenced. Plagiarism in any part of your report will result in referral to the disciplinary committee, which may lead to you losing all marks for this coursework and may have further implications on your degree. For details see this link
Late Submission Policy
The standard penalty of -30% of the maximum available mark applies to late submissions. No submissions will be accepted after 5 working days beyond the submission deadline.
