CMSC 216 Project #3 Spring 2021Date due: Wednesday, March 3, 11:59:59 p.m.1 Introduction and purposeIn this project you will write some functions to manipulate the instructions of a fictional simple processor in a family ofnew CPUs being developed by the Banana computer company, to run all of its future devices. The CPU version used inthis project, named N2, has a limited set of instructions, is able to access just a small amount of memory, and is primarilyintended for use in embedded systems, like a toaster for example. (The computational needs of a toaster are not high.)One purpose of the project is to use the features of C covered recently– bit operators, arrays, and pointers– but anotherimportant objective is to introduce hardware and assembly language concepts, which will be revisited later in the course.Much of this project description explains the assembly and machine language concepts involved, as well as the hypotheticalN2 CPU. The description of the functions to write is just two and a half pages of this assignment.Although the amount of code to be written in this project is not large compared to some CMSC 132 projects moststudents should find it significantly harder than Projects #1 and #2, so start working on it right away. Before starting tocode, look at the public tests to see how the functions are called, and look at the definitions in the header file machine.hdescribed below. Also first study bit masking from lecture, which you need to understand very well, and if needed, askabout it in the TAs’ office hours before starting to code. Lastly, read the entire project completely and carefully beforestarting to code. You may need to read it several times while writing the project.Due to the size of the course it is not feasible for us to be able to provide project information or help via email/ELMSmessages, so we will be unable to answer such questions. You are welcome to ask any questions verbally during the TAs’online office hours (or during, before, or after online discussion section or lecture if time permits). However, you cannotwait to write projects in a course with nearly 550 students. If many students wait until the last few days to write orfinish projects– especially challenging ones– and have questions, the TAs will not be able to help everyone in office hours.If you are in office hours near when a project is due you may have to wait a long time, and may not even be able to get helpat all. This would not be the TAs’ fault; it would be because you waited until too late to do the project, given the size of thecourse. The only way to avoid this is starting on projects early, in case you do have to ask questions in office hours.1.1 Extra credit and number of submissionsIf you make only one submission for this project, it passes all the public tests, and it is made at least 48 hours beforethe on–time deadline (i.e., at least two days early), we will give you 10 extra–credit bonus points on the project. Inorder to make only one submission and have it pass all the public tests you will have to read this assignment very carefully,and throughly test your functions yourself, so you are confident of doing well on the secret tests, because if you find a buglater and want to submit again you won’t get the bonus points. You will also have to use good style all during your coding,because your single submission is of course the one that is going to be graded for style.However, as before, if you make too many submissions for this project you may again lose credit. The purpose of theextra credit and the point deductions for excess submissions is to motivate you to test your code thoroughly yourself.There really is little reason to make any submissions that don’t compile– you should be compiling your code yourselfand fixing problems before submitting. Other than right before the project deadline, there really is little reason to make anysubmissions that do not pass all of the public tests– you should be running your code on them yourself, comparing youroutput to the correct output as described in Appendix A.1, and fixing any problems, before submitting.(If for some reason your program passes all the public tests on Grace, but doesn’t work on the submit server whensubmitted, so you have to submit more than once– and this is not due to an error on your part– you can talk with meverbally in office hours about receiving the extra credit despite having more than one submission.)2 Machine details and background conceptsThis section explains many background concepts, while the following one describes the functions to be written.2.1 Hardware conceptsFor a program written in any computer language to be executed on a particular machine it must be translated to theinstructions that the machine’s processor can execute. These instructions are referred to as machine instructions, but weusually just say instructions. Instructions manipulate information in memory and also in the processor’s registers. Memory© 2021 L. Herman; all rights reserved 1is used to hold data, such as variables, and programs themselves are also stored in memory in modern systems. Registersare locations that store values like memory except they are internal to the CPU, so they are accessed much more quickly.Registers temporarily store values that instructions operate upon, as well as the results of instructions.The fundamental operation of any CPU is to get an instruction from memory, figure out what it says to do, perform thatoperation, and go on to get the next instruction; this is called the fetch–decode–execute cycle. (This is discussed in moredetail in the Bryant & O’Hallaron text.) Although the instruction sets of different processors vary widely, instructions canbe categorized by functionality, for example:computation instructions: These perform various arithmetic and logical operations.flow of control instructions: By default instructions are executed sequentially in memory, but there are instructions thataffect which instruction is executed next, for implementing conditionals and repetition, as well as function calls.data movement instructions: These transfer data values between memory and registers, between different registers, andsometimes between different memory locations.invoking the operating system: These instructions are used to do things like halt a program or to access parts of thehardware that user programs are not allowed to directly access, for example, I/O devices. Some instructions allowuser programs to make system calls to get the operating system to perform these types of tasks for them.2.2 Machine specificationsThe hypothetical N2 processor has a 32–bit (4 byte) word length, meaning that instructions, registers, and memory wordsare all 32 bits. (As mentioned in lecture, processors manipulate information in multibyte quantities called words.) Machinesthat use the N2 CPU are quite small, with very limited system resources. They have only 32768 bytes of memory, groupedas 8192 four–byte words (8192 × 4 = 32768). The first byte in memory has address 0. Memory addresses always referto bytes. Memory is only word–addressable, meaning that although each byte in memory has its own unique address, theCPU can only access memory in four–byte quantities, using the address of the first (or low–order) byte of a four–byte word.Consequently, the addresses that can be used to access memory are 0, 4, 8, etc., up to 32764. The value of a memory wordcan be interpreted as an instruction and executed, or treated as data.The N2 processor has 27 different instructions. It has seven registers, each of which as mentioned holds 32 bits. Theseare referred to using the names R0 through R6. The N2 has what is called a load/store architecture, which means that onlysome data movement instructions access memory. One of them loads a value from a memory location into a register andanother one stores a value from a register into a memory location, while all other instructions, including computations,operate upon values in registers and put their result into a register. So computation typically involves loading operandsfrom memory into registers, doing calculations with them, and storing the results from registers back into memory.One N2 register, R6, has a special purpose. It is the program counter, which always contains the memory address ofthe next instruction to be fetched and executed. A flow of control instruction can modify the program counter to causeexecution to jump to somewhere else in a program. All other instructions cause the program counter to be incrementedby 4. So unless specified by a flow of control instruction, the processor executes instructions sequentially in memory. R6cannot be directly modified, for example, by storing the result of a computation in it. (Instructions can use the value in R6,but not directly modify it.) The other registers may be used or modified by the various instructions.2.3 Hardware, components of instructions, and instruction formatSince the N2’s processor has a 32–bit word length, all instructions, just like all data, must fit into a 32–bit word. When a32–bit word is interpreted as an instruction, it is considered to consist of fields representing(a) an “opcode”, i.e., operationof the instruction, (b) an extension, whose use will be described below, (c) up to three registers used as operands by someinstructions, and (d) a memory address or constant/immediate field that holds either a memory address or a constant (literal)numeric operand for some instructions. The instruction format on the N2 processor is as follows:5 bits 3 bits 3 bits 3 bits 3 bits 15 bitsopcode extension register1 register2 register3 memory address or constant/literal valueThe fields have the following uses and functionality:opcode: An opcode uniquely identifies the operation that an instruction performs. Short names are used in assemblylanguage to refer to each type of instruction. (Recall that assembly instructions are just human–readable versions ofmachine instructions.) Since the N2 has 27 different opcodes, 5 bits are required to represent an opcode. Since 5 bitscan store 32 different values but the N2 only has 27 opcodes, five five–bit values do not correspond to valid opcodes.© 2021 L. Herman; all rights reserved 2extension: One instruction on the N2 has five different variants. For this instruction, a value in the extension field is used toindicate which variant an instruction represents. Not all values that can be stored in 3 bits represent valid extensions.register1, register2, register3: As Section 2.4 says, some instructions operate upon one register, others operate on tworegisters, and some have three register operands. These three fields of instructions contain numbers indicating theregisters that instructions use as operands. Since the N2 CPU has 7 registers, 3 bits can indicate any of them.Since 3 bits can store 8 different values but the N2 only has 7 registers, there is one value that can be in a registerfield that does not correspond to a valid register.address or constant: Some of the N2’s instructions have the address of a memory location as an operand. For example,an instruction may copy the value in memory location 216 to one of the registers, so 216 would be stored in thisfield of the instruction. One instruction (li) has a constant or literal value, typically called an immediate in assemblylanguage, as an operand. For example, an instruction may store the numeric value 250 in one of the registers, so 250itself would be encoded in the instruction.This field is 15 bits, which is why the N2 has 32768 bytes of memory (with addresses 0... 32767)– because 215 =
...