CSE 30 Spring 2024 PA 7 & 8 - (Version 1.01)
PA7 Due Date: Sunday May 26, 2024 @ 11:59PM
PA7 Final Submission Date: Wednesday May 29, 2024 @ 11:59PM
PA8 Due Date: Tuesday June 4, 2024 @ 11:59PM
PA8 Final Submission Date: Friday June 7, 2024 @ 11:59PM
Grading PA7
Difficulty Gauge 1 = Easy 2 3 4 5 = Hard
You must complete all of the following items by the due date to get all points.
There are 30 points available for this PA that are distributed as follows:
Up to 10 points (at our discretion) if the following files compile/assemble without warnings that fail the supplied tests. This has to be a meaningful attempt to write the code that meets the specifications of the program. Random C or assembly statements, or empty files will not be awarded any points: Cmain.c (1 point), Crdbuf.c (1 point), Cecrypt.c (2 points), Cdcrypt.c (2 points), ecrypt.S (2 points), dcrypt.S (2 points)
Up to 10 points for passing test 1 and test 2 in the text fixture.
Up to 10 points for passing the gradescope tests (these will only be run after the late deadline).
Minus 1 point for each submitted file that passes the supplied tests but compiles/assembles with a warning (max of 6 points deducted).
Minus 2 points at our discretion, for not following the CSE30 C Style. Guide or the CSE30 Assembly Style. Guide
Minus 3 points for each submitted ARM32 assembly language file that uses any ARM instructions not listed in: ARM Green Card
Grading PA8
Difficulty Gauge 1 = Easy 2 3 4 5 = Hard
You must complete all of the following items by the due date to get all points.
There are 30 points available for this PA that are distributed as follows:
Up to 6 points (at our discretion) if the following files assemble without warnings that fail the supplied tests. This has to be a meaningful attempt to write the code that meets the specifications of the program. Random assembly statements, or empty files will not be awarded any points: main.S (5 points), rdbuf.S (1 point)
Up to 14 points for passing the test 1 and test 2 in the text fixture.
Up to 10 points for passing the gradescope tests (these will only be run after the late deadline).
Minus 2 points for each submitted file that passes the supplied tests but assembles with a warning (max of 4 points deducted).
Minus 3 points at our discretion, for not following the CSE30 Assembly Style. Guide
Minus 7 points for each submitted ARM32 assembly language file that uses any ARM instructions not listed in: ARM Green Card
Need Help?
You are always welcome to go to either Instructor or TA office hours. Their hours are listed in the Canvas calendar and the autograder calendar. In office hours, conceptual questions are prioritized.
If you need help while working on this PA, make sure to attend labs hours with a tutor at: https://autograder.ucsd.edu
You can also post questions on Piazza.
https://piazza.com/ucsd/spring2024/cse30_sp24_a00/home
References
CSE30 ARM Programming Guide ARM Green Card
Bitwise operations, file I/O, Stack Frames, and Passing Arguments
This is a two part project where you will be working on a program called cipher. Cipher is a file encryption/decryption program that uses a variation of what is called a book cipher. Cipher will both encrypt and decrypt any type of file (text and binary) using a combination of per byte bit manipulation (using bitwise operations) and an exclusive or (EOR in ARM32 and the ^ operator in C) encoding using sequence of bytes from a book file (traditionally a real book, but it can be any text or binary file). What you will learn in this project:
1. Practice bitwise operations in both C and ARM32.
2. Calling C library fread() and fwrite() from C and ARM32.
3. Writing loops and conditional statements in ARM32.
4. Implementing ARM32 functions using the Aarch32 Procedure Call Standards. All assembly language functions must have at least the minimum stack frame. as shown in the lecture.
5. Passing arguments to functions in registers and on the stack frame. in ARM32.
6. Using Function pointers in C and ARM32.
7. Implementing a stack frame. in ARM32.
Coding requirements
1. You will write your code only in C and ARM32 (v6) and it must run in a Linux environment on the pi-cluster.
2. You may not use recursion in your code, processing must only use iterative approaches.
3. You will use the supplied Makefile to compile your program.
4. You may not add any additional #include files.
5. Be aware that we will be testing your code using the supplied .h include files. If you change any of these files (other than version.h) that your code depends on, you run the risk that your code will fail gradescope tests.
6. For the code that you write, you can only use the following C library functions. You can use any functions that are supplied with the starter code.
fread(), fwrite(), fclose(), fopen(), fprintf()
7. All assembly language functions must conform. to AArch32 procedure call standards (must have the minimum stack frame. and the stack must be properly 8-byte aligned - PA8).
8. Only use the ARM32 assembly instructions listed in the document: ARM Green Card
9. Follow the CSE30 C Style. Guide CSE30 Assembly Style. Guide
10.You will not need to create any helper functions in these PA's as the functions you need to write are short in length.
11. You may copy and modify any code supplied to you, including code from lecture and discussion, and submit it as part of your work. You should not be copying code from the web or using any AI tools to write your code. Using code obtained from others is a violation of the CSE30 Academic Integrity policy and will be strongly enforced.
Get the Starter files from Github and the setup
Step 1: You need to get the starter files for PA. Login into your account on the pi-cluster and run the following command. You will develop the code on the pi-cluster. You must do the git clone on the pi-cluster.
cs30sp24@pi-cluster-153:~ % cd ~/cse30
cs30sp24@pi-cluster-153:~ % git clone https://github.com/cse30-sp24/pa7-starter.git pa7
cs30sp24@pi-cluster-153:~ % cd pa7
Step 2: Set the execute bits on runtest and the test cmd files. Note this also turns off write permission. This is to help students who were changing these files by accident.
cs30sp24@pi-cluster-153:~ /pa7 % chmod 0555 runtest in/cmd*
Step 3: Compile the program.
cs30sp24@pi-cluster-153:~ /pa7 % make
Description of the Command Line Options
cipher reads the data to be processed from standard input, either encrypts or decrypts the data, and then writes the result to standard output. Cipher has two required arguments:
1. A flag that specifies one of either encrypt (-e) or decrypt (-d) operational mode
2. A flag -b <filename> that specifies the name of the book file that contains the encoding keys
Synopsis: ./cipher (-d|-e) -b <bookfile>
Flag Description
-d Sets the program to decrypt. Exactly 1 of -d OR -e must be provided, but not both.
-e Sets the program to encrypt. Exactly 1 of -d OR -e must be provided, but not both.
-b bookfile The file path to the input bookfile. This is required.
cipher returns EXIT_SUCCESS when it operates correctly, otherwise it returns EXIT_FAILURE.
How the Program Works
The program is called with a decrypt or encrypt flag, the bookfile flag, followed by a file path to the bookfile.
Command line option handling is done for you in the supplied function setup() (written in C in the file setup.c). It is highly suggested that you look over this file to see how the parameters are passed to it when you write main.S for PA8.
Inputs:
● Decrypt flag OR encrypt flag
● Bookfile flag and file path of the bookfile
● Standard input is read to obtain the data to encrypt or decrypt
Outputs:
● When encrypting or decrypting, the output goes to stdout
Important! Encrypted files are not printable as they contain 8-bit byte values that will not always map to printable 7-bit ASCII characters. So when using cipher, it is best to specify the input and output data files using command line redirection (the < and > operators in the command shell).
Here is the typical usage to encrypt the file input_file creating an encrypted version in output_file:
./cipher -e -b in/BOOK < input_file > output_file
Here is the typical usage to decrypt the file input_file creating a decrypted version in output_file:
./cipher -d -b in/BOOK < input_file > output_file
Use the linux command hexdump (man hexdump) if you need to look at encrypted files.
Obtaining the Encryption/Decryption Key
If you do not know what a key in cryptography is (specifically, symmetric cryptography), it is essentially similar to how a physical key and a lock work. The key is used to close the lock (or encrypt a message), and the same key is required to unlock the lock (or decrypt the encrypted message).
In practice, this often uses the exclusive-or operation, or XOR. This is because XOR has the wonderful identity and self-inverse properties, meaning that A ⊕ 0 = A (⊕ is the XOR symbol), and A ⊕ A = 0.
Thus, if we have the message M and we XOR it with key K, we can XOR the key again to reobtain M.
Example: M ⊕ K ⊕ K = M ⊕ (K ⊕ K) = M ⊕ (0) = M
The bookfile is simply a file to obtain keys from. This is based on book ciphers, in which the plaintext of a book is used as a key to a cipher. This is more convenient than carrying around specific keys, as books are public and easily accessible. In the starter code, the bookfile is just a plaintext file of The Adventures of Sherlock Holmes by Arthur Conan Doyle. However a book file does not have to be a text file, as any file can be used as long as it has the same or more bytes (same length or longer) in it than the input file.
How the program obtains keys from this bookfile is reading bytes from the book file. The first key is the very first character of the input, which in the case of the starter code is 'T' (the first line of the file being "The Adventures of Sherlock Holmes"). The first key is used to encrypt (or decrypt) the first byte of the input file (read from standard input). However, the next time we obtain a key, we will increment the location by one byte, meaning that the next key would be 'h'. This second byte of the book file, the ‘h’ is used to encrypt (or decrypt) the second byte of the input file and so on until we reach EOF on the input file.
The only requirement for the bookfile is that the number of bytes in the bookfile is equal to or greater than the number of bytes in the input file. If EOF is reached on the book file before reaching EOF on the input file then there are not enough bytes in the bookfile to encrypt (or decrypt) the input file. This is treated as an error and the program terminates with EXIT_FAILURE.
In the starter code, reading of the input and bookfile into two buffers is handled by the function rdbuf() (see the description of rdbuf() below).
Encryption Algorithm
There are two main steps to the encryption algorithm: reversing the bits for each input file one byte at a time, then XORing this with a one byte key from the book file. Remember that the encryption algorithm is performed one byte at a time (byte is 8 bits or the sizeof of an unsigned char) in a buffer of bytes (char).
Step 1: Reversing the bits (bit order) in one byte
Let’s begin with the example of encrypting a byte containing the hexadecimal value of 0x61. In binary it is the following (6 = 0110, 1 = 0001):
msb 7 6 5 4 3 2 1 lsb 0
0 1 1 0 0 0 0 1
The first step of the algorithm is to reverse the order of the bits in the byte. After this procedure, the result will be the following:
msb 7 6 5 4 3 2 1 lsb 0
1 0 0 0 0 1 1 0
This process can be done any number of ways using shifts and bitwise operations. However, one thing to note is that at this point in the process, the encryption would result in the hexadecimal value of 0x86 (1000 0110). This approach will work with any byte value (ASCII text or binary).
Step 2: XORing the Key
Once we have performed the first step, a single bitwise operation needs to be done on the byte. Using a single byte key (how to obtain the key is described above), the next step of the algorithm is to exclusive-or (XOR) this single byte key with the single byte result from the first step. (The ARM32 instruction to do this is eor).
For example, let’s use the letter 'T' as the key. In ASCII, 'T' has the hexadecimal value of 0x54.
This means in binary it is the following (5 = 0101, 4 = 0100):
msb 7 6 5 4 3 2 1 lsb 0
0 1 0 1 0 1 0 0
XOR 0101 0100 (the key above) with 1000 0110 (the input below),
msb 7 6 5 4 3 2 1 lsb 0
1 0 0 0 0 1 1 0
and obtain the final result:
msb 7 6 5 4 3 2 1 lsb 0
1 1 0 1 0 0 1 0
This gives hexadecimal 0xd2 (1101 0010) as the output byte.
Decryption Algorithm
The decryption algorithm is the exact inverse of the encryption process.
Step 1: XORing the Key
Step 2: Reversing the bits of a byte
Version.h Controls the compilation process
In the starter file there is a file called Version.h. This file works the same way as it did in previous PA's. You will be writing four functions in both ARM and C for a total of eight functions. The contents of Version.h is shown below:
// PA7 functions
// at most one of the following two should be uncommented
// if both are commented out, use the solution code
//#define MYDCRYPT_C // when defined will use your Cdcrypt.c
//#define MYDCRYPT_S // when defined will use your dcrypt.S
// at most one of the following two should be uncommented
// if both are commented out, use the solution code
//#define MYECRYPT_C // when defined will use your Cecrypt.c
//#define MYECRYPT_S // when defined will use your ecrypt.S
// PA8 functions
// at most one of the following two should be uncommented
// if both are commented out, use the solution code
//#define MYMAIN_C // when defined will use your Cmain.c
//#define MYMAIN_S // when defined will use your main.S
// at most one of the following two should be uncommented
// if both are commented out, use the solution code
//#define MYRDBUF_C // when defined will use your Crdbuf.c
//#define MYRDBUF_S // when defined will use your rdbuf.S
Testing cipher with the test harness
This PA uses the same test harness as used in the last two PA's with the addition that this one also checks the return value (exit) value from running the command in the cmd file.
in/cmd files contain the command line execution.
in/data files contain the data to be encrypted (data1) and decrypted (data2).
exp/out files contain the encrypted data (out1) and the decrypted data (out2).
exp/err files contain any error messages and the last line is the return value from cipher.
Test one file of yours at a time. It is suggested you start with the c programs first. Use hexdump to look at encrypted files.
It is suggested to start with test1 to test decryption first for all the files except Cecrypt.c and ecrypt.S:
% make test2 (or ./runtest 2)
Then for files Cecrypt.c and ecrypt.S test the encryption process.
% make test1 (or ./runtest 1)
You may want to test much longer test files (more than 128 bytes in length and with both readable text and binary files) once you have test 1 and test 2 passing.
Turning in Files For Your Grade
Before submitting your program to gradescope, make sure at a minimum that your program passes the supplied tests in the test harness.
PA7 Submit to gradescope under the assignment titled PA7:
Crdbuf.c
Cmain.c
Cecrypt.c
Cdcrypt.c
ecrypt.S
dcrypt.S
PA8 Submit to gradescope under the assignment titled PA8:
main.S
rdbuf.S
Writing routines in ARM
While you are designing your assembly language functions, once you have settled on an algorithm, your next task is to decide which registers are going to be used for what purpose.
On entry to a function, r0-r3 are used to pass the first four arguments. It is ok to modify these as you see fit in your code. However, if you are going to make a call to another function (PA 8 only), remember that the called function has the right to change r0-r3 (and you must assume that they will). So if you will still need the parameters after making a function call, either copy them to a protected register or save them on the stack (this is a step you will only take in PA8, you do not have to do this in PA7).
Next decide which registers you are going to use for each local variable first. If the function you are working on does not call any function that has output parameters, you can assign local variables to be in registers (using a combination of preserved and scratch registers).
One way to keep track of the registers is to create a table either in your code inside a comment at the top of the function or elsewhere (like a sheet of paper) that describes how you have decided to use each register relative to your algorithm. We have put an example of such a table inside the assembly language starter files. For example:
// register use table
// r0 on entry contains the address of iobuf (char * pointer)
// r1 on entry contains the address of bookbuf (char * pointer)
// r2 on entry contains cnt
// r3 is loop counter i
// r4 contains the shifted byte
Examine the number of parameters each function that you call requires (PA8 only). Of importance is any output parameters where the called function is expected to change the value passed to it, these output parameters require a pointer to a memory location which must be either on the stack or in a global variable like a string literal passed to fprintf().
Remember that any function with more than 4 parameters will require space on the calling functions stack for parameters 5 and higher. And always keep your total stack size in bytes to divide by 8 evenly (8-byte aligned).
Ecrypt notes (Two versions: Cecrypt.c and ecrypt.S) - PA7
int ecrypt(unsigned char *inbuf, unsigned char *bookbuf, int cnt);
ecrypt() is passed pointers to two buffers. inbuf which contains the bytes to be encrypted and bookbuf the cipher key buffer. Each buffer contains the same number of bytes (cnt) in them.
In the body of a loop, you will need to process the buffers, one byte at a time. Assume we are processing inbuf[0], first reverse the bits and then XOR the results with the contents of bookbuf[0] and finally store the result of the XOR back into inbuf[0]. Continue processing each byte until all cnt bytes are processed (use pointers in your C code).
When writing ARM assembly version of the function, you will need to (1) use a load instruction to read one byte at a time from inbuf and bookbuf into different registers, (2) process them as described above, and then (3) using a store instruction write the processed byte (in a register) back into inbuf.
In the starter code, reserved registers r4-r9 may be used (all have been saved on the stack). You also have use of temporary registers r0-r3. You do not need any local variables on the stack.
Dcrypt notes (Two Versions: Cdcrypt.c and dcrypt.S) - PA7
int dcrypt(unsigned char *inbuf, unsigned char *bookbuf, int cnt);
Same as ecrypt() above except XOR inbuf[0] and bookbuf[0] first, then reverse the order of the bits and store the result back into inbuf[0].
Cmain.c Notes (C version: see Cmain.c) - PA7
This is a relatively short function. Follow the instructions in the starter code. main() calls setup() to parse the command line arguments, open the bookfile and set the func() pointer to point at either ecrypt() or dcrypt(). Be aware that when calling setup() there are two output parameters (you are passing addresses of main() stack variables) to the function setup() to change.
setup() returns RETRN_FAIL if there is an error. Important: If setup() fails, then both output variables, fpbook and func, are set to contain NULL.
main() I/O loop consists of the following three steps:
1. call rdbuf() to fill the inbuf (from stdin) and bookbuf (from bookfp) with the same number of characters. If 0 is returned EOF was reached on stdin.
2. Call the function pointed at by func() to encrypt or decrypt inbuf.
3. Call fwrite() to write inbuf to stdout.
Make sure to fclose() the bookbuf and return either EXIT_SUCCESS (if all ok) or EXIT_FAILURE otherwise.
main.S Notes (ARM version: see main.S) - PA8
This is the ARM32 version of Cmain.c. Tasks are as follows:
1. You will need to finish the design of the stack frame. and calculate the stack variables offsets as shown in the lecture. Use the local variables as defined in Cmain.c starter code to guide your design. You may add additional variables to the stack. If you use the registers carefully, additional stack space will not be needed.
2. In the starter code we have saved r4-r10 on the stack for you. Be aware that this is an odd number of registers and you may need to adjust the size of the pad to make sure the entire size of the stack frame. is evenly divisible by 8 (8-byte aligned) depending on the number of variables you place on the stack. Also keep the two buffers (inbuf and bookbuf) 8-byte aligned.
Here is a sample stack frame. based on Cmain.c to get you started.
3. Figure out how you are going to use the preserved registers in your code by filling out the preserved register use table comment section. This documents your use and is helpful when writing your code.
4. Call setup(). setup() is passed four arguments, using registers r0-r3. Argc (r0) and **argv (r1) are input parameters and **func() (r2) and **fpbook (r3) are both output parameters. It is important to note that the first two arguments to setup() are argc (in r0) and arg (in r1). So all you have to do is pass a pointer to a stack variable *func() in register r2 and a pointer to the stack variable *fpbook in register r3. Setup will write to both these stack locations.
5. If setup() failed (returns RETRN_FAIL), you will need to exit the program with EXIT_FAILURE. Make sure you branch to the exit code located at the bottom of the main() function. In assembly language programming, all stack frame. deallocation and function returns are done only at one place, and are located near the bottom of the function (this differs from high level programming). Do not forget that on setup() failure, the bookfile is not open and the two stack variables *func() and *fpbook will both contain NULL.
6. Prepare all the registers prior to the I/O loop. You may want to store as many of the most referenced stack variables in preserved registers to avoid reading the stack all the time.
7. Main I/O loop is the same as in Cmain.c. If there is an error, branch to the exit code at the bottom of the function. Be aware that when calling rdbuf(), it has 5 parameters, so the last one is on the stack.
8. There should be two branch targets near the end of main() (below the I/O loop) for calling fprintf() with either .Lrdmess or .Lwrmess. It is possible to have both targets share the same code section to make the call to fprintf().
9. Part of the code at the bottom of main() (below the I/O loop) calls fclose(fpbook). Be aware that there should be a branch target for setup() failure that should not call fclose() as this may cause a segfault.
10.Make sure to return EXIT_FAILURE or exit_SUCCESS as appropriate when main() returns.
setup.c Notes (Supplied code nothing to do: see setup.c)
int setup(int argc, char **argv, int (**func)(), FILE **fpbook);
setup() is supplied in source form. and you do not have to write an assembly language version of it. You do need to call it from both your C and assembly language versions of main().
**func() is a pointer to a memory location on main()s stack. This location is written with the starting address of either ecrypt() (when the -e flag is present) or dcrypt() (when the -d flag is present) functions. This will allow main() to call the correction operation (encrypt or decrypt) by calling the function pointed at by *func() when processing the input.
**fpbook is a pointer to a memory location in main()’s stack. This location is written to contain a FILE * pointer for the bookfile (the return value of fopen()).
Setup() uses getopt() to parse the command line options to determine if the mode of operation is either encrypt or decrypt, setting the specified function address in **func (using the address passed to it by main().
Next setup() opens the bookfile using the filename operand to the -b option. It calls the C library function fopen() to do so, then storing the FILE* value returned in the output parameter fpbook.
Setup() like all functions, puts its return value in register r0. Setup() returns a 0 (RETRN_OK) on success and RETRN_FAIL on any error.
When RETRN_FAIL is returned from setup(), both **func() and **fpbook are set to NULL (and the bookfile is not open, so a call to fclose() should not be performed). When main() gets a RETRN_FAIL from setup, main() exits returning an EXIT_FAILURE.
Crdbuf.c Notes (C version: see Crdbuf.c) - PA7
int rdbuf(FILE *in, FILE *fpbook, int cnt, unsigned char *inbuf,
unsigned char *bookbuf);
rdbuf() fills inbuf and bookbuf with the same number of bytes. This function uses fread() to perform. the reads on both FILE pointers. Remember that you cannot assume that fread() will fill the buffer with the number of bytes you requested.
Remember to only read the same number of bytes into bookbuf that were read into inbuf.
inbuf[0] inbuf[bytes-1]
bookbuf[0] bookbuf[bytes-1]
Use the return value from fread() on FILE *in to determine how many bytes to read into bookbuf from the FILE *fpbook. If you cannot read the same number of bytes into bookbuf as was read into inbuf, return RETRN_FAIL.
rdbuf() returns the number of valid bytes in inbuf (0 indicates EOF and the buffers are empty, and RETRN_FAIL indicates one of the fread() calls failed - like the bookfile is shorter in length that the file being processed).
rdbuf.S Notes (ARM version: see Crdbuf.c) - PA8
This is Crdbuf.c written in ARM32 assembler. Be aware that this function has 5 parameters, so the 5th parameter the unsigned char *bookbuf, is passed on the stack and not in a register. Follow the instructions in the starter code.
Here is a sample of what the stack looks like after rdbuf() is called:
Bit Operators Reference Table: C and ARM assembly