Due date:   11:59pm, Friday, March 22, 2024, submitted via git

Objectives

The purpose of this assignment is to practice your coding in C, and to reinforce the concepts discussed in class on program representation.

In this assignment1 you will implement a binary translator2  like Rosetta3 .  Your program will translate from a simple instruction set (much simpler than x86) to x86 and generate x86 assembly code.  The code will then be tested by assembling and running it.  This assignment is divided into two parts to make it simpler. In the first part, you will implement the loader and a simple translator, which translates the simpler in- structions.  In the second part, you will extend the translator to translate more complex instructions.

Preparation:

1.    Complete Assignment 0 or ensure that the tools you would need to complete it are installed. 2.    Clone your assignment repository:

where ???? is your CSID.   Please see instructions in Assignment 0 and the tutorials on Brightspace if you are not sure how.

Inside the repository there is one directory: xtra, where code is to be written.   Inside the directory is a tests directory that contains tests that will be executed each time you submit your code.  Please do not modify the tests directory or the  .gitlab-ci.yml file that is found in the root directory.  Modifying these files may break the tests.   These files will be replaced with originals when the assignments are graded.  You are provided with sample Makefile files that can be used to build your program.   If you are using CLion, a Makefile will be generated from the CMakeLists.txt file generated by CLion.

Background:

For this assignment you will translate a binary in a simplified RISC-based 16-bit instruction set to x86-64 assembly. Specifically, the X instruction set comprises a small number (approximately 30) instructions, most of which are two bytes (one word) in size.

The X Architecture has a 16-bit word-size and 16 general purpose 16-bit registers (r0 . . . r15 ).   Nearly all instructions operate on 16-bit chunks of data.  Thus, all values and addresses are 16 bits in size. All 16-bit values are also encoded in big-endian format, meaning that the most-significant byte comes first.

Apart from the 16 general purpose registers, the architecture has two special 16-bit registers: a program counter (PC), which stores the address of the next instruction that will be executed, and the status (F), which stores bit-flags representing the CPU state. The least significant bit of the status register (F) is the condition flag, which represents the truth value of the last logical test operation. The bit is set to true if the condition was true, and to false otherwise.

Additionally, the CPU uses the last general-purpose register, r15, to store the pointer to the program stack. This register is incremented by two when an item is popped off the stack and decremented by two when an item is pushed on the stack.  The program stack is used to store temporary values, arguments to a function, and the return address of a function call.

The X Instruction Set

The instruction set comprises approximately 30 instructions that perform arithmetic and logic, data move- ment, stack manipulation, and flow control. Most instructions take registers as their operands and store the result of the operation in a register. However, some instructions also take immediate values as oper- ands. Thus, there are four classes of instructions: 0-operand instructions, 1-operand instructions, 2-oper- and instructions, and extended instructions, which take two words (4 bytes) instead of one word.

All but the extended instructions are encoded as a single word (16 bits). The extended instructions are also one word but are followed by an additional one-word operand. Thus, if the instruction is an extended instruction, the PC needs an additional increment of 2 during the instruction’s execution.  As mentioned previously, most instructions are encoded as a single word. The most significant two bits of the word indicates whether the instruction is a 0-operand instruction (00), a 1-operand instruction (01), a 2-operand instruction (10), or an extended instruction (11). For a 0-operand instruction encoding, the two most sig-

nificant bits are 00 and the next six bits represent the instruction identifier. The second byte of the instruction is 0.

For a 1-operand instruction encoding, the two most significant bits are 01, the next bit indicates whether the operand is an immediate or a register, and the next five bits represent the instruction identifier. If the third most

significant bit is 0, then the four most significant bits of the second byte encode the register that is to be operated on (0 … 15). Otherwise, if the third most significant bit is 1, then the second byte encodes the immediate value.

For a 2-operand instruction encoding, the two most significant bits are 10, and the next six bits represent the instruction identifier. The second byte encodes the two register operands in two four-bit chunks. Each of the 4-bit chunks identifies a register (r0 … r15).

For an extended instruction encoding, the two most significant bits are 11, the next bit indicates whether a second register operand is used, and the next five bits represent the instruction identifier. If the third most

significant bit is 0, then the instruction only uses the one-word immedi- ate operand that follows the instruction. Otherwise, if the third most significant bit is 1, then the four most significant bits of the second byte encode a register (1 … 15) that is the second operand.

The instruction set is described in Tables 1, 2, 3, and 4. Each description includes the mnemonic (and syntax), the encoding of the instruction, the instruction’s description, and function. For example, the add,

loadi  and           instructions have the                   descr

First, observe that the add instruction takes two register operands and adds the first register to the sec- ond. All 2-operand instructions operate only on registers and the second register is both a source and destination, while the first is the source. It is a 2-operand instruction; hence the first two bits are 10, its instruction identifier is 000001 hence the first byte of the instruction is 0x81.

Second, the loadi instruction is an extended instruction that takes a 16-bit immediate and stores it in a register. Hence, the first two bits are 11, the register bit is set to 1, and the instruction identifier is 00001. Hence, the first byte is encoded as 0xE1.

Third, the push instruction is a 1-operand instruction, taking a single register operand. Hence, the first two bits are 01, the immediate bit is 0, and the instruction identifier is 00011. Hence, the first byte is encoded as 0x43.

Note that S and D are 4-bit vectors representing S and D.

Table 1: 0-Operand Instructions

Table 1: 1-Operand Instructions