CSCI 2122 Assignment 4
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:
https://git.cs.dal.ca/courses/2024-winter/csci-2122/assignment-4/????.git
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 modifythetestsdirectoryorthe.gitlab-ci.ymlfilethatisfoundintherootdirectory. 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.
1 The idea for this assignment came indirectly from Kyle Smith. 2 https://en.wikipedia.org/wiki/Binary_translation
3 https://en.wikipedia.org/wiki/Rosetta_(software)
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, **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 **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 **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 push instructions have the following descriptions:
loadi V, rD 11100001 D 0 Load immediate value or address V into rD ← memory[PC] register rD. PC ← PC + 2
Mnemonic Encoding Description Function
add rS, rD
10000001 S D
Add register rS to register rD.
rD ← rD + rS
push rS
01000011 S 0
Push register rS onto program stack.
r15 ← r15 - 2 memory[r15 ] ← rS
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 **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
Mnemonic Encoding Description Function
ret
00000001 0
Return from a procedure call.
P C ← memory[r15 ] r15 ← r15 + 2
cld 00000010 0 Table 1: **Operand Instructions
Stop debug mode
Logically negate register rD . Decrement rD .
Pop value from stack into register rD.
Branch relative to label L if condition bit is true.
Subtract register rS from register rD. And register rS with register rD .
Xor register rS with register rD .
See Debug Mode below.
rD ←!rD
rD ← rD – 1
rD ← memory[r15 ] r15 ← r15 + 2
if F & 0x0001 == 0x001: PC ← PC + L – 2
rD ← rD - rS rD ← rD & rS rD ← rD ^ rS
std
00000011 S 0
Start debug mode
See Debug Mode below.
Mnemonic Encoding Description Function
neg rD
01000001 D 0
Negate register rD .
rD ← −rD
not rD dec rD
pop rD br L
01000010 D 0 01001001 D 0
01000100 D 0 01100001 L
inc rD
01001000 D 0
Increment rD .
rD ← rD + 1
push rS
01000011 S 0
Push register rS onto the pro- gram stack.
r15 ← r15 – 2 memory[r15] ← rS
out rS
01000111 S 0
Output character in rS to std- out.
output ← rS (see below)
jr L
01100010 L
Jump relative to label L.
PC ← PC + L – 2
Table 3: 2-Operand Instructions
Mnemonic Encoding Description Function
add rS , rD
10000001 S D
Add register rS to register rD .
rD ← rD + rS
sub rS , rD and rS , rD xor rS , rD
10000010 S D 10000101 S D 10000111 S D
mul rS , rD
10000011 S D
Multiply register rD by register rS.
rD ← rD * rS
or rS , rD
10000110 S D
Or register rS with register rD .
rD ← rD | rS
test rS1, rS2
10001010 S D
Set condition flag to true if and only if rS1 ∧ rS2 is not 0.
ifrS1 &rS2 !=0:
F ← F | 0x0001
else:
F ← F & 0xFFFE
cmp rS1, rS2
10001011 S D
Set condition flag to true if and only If rS1 < rS2.
if rS1 < rS2:
F ← F | 0x0001
else:
F ← F & 0xFFFE
equ rS1, rS2
10001100 S D
Set condition flag to true if and only if rS1 == rS2.
if rS1 == rS2:
F ← F | 0x0001
else:
F ← F & 0xFFFE
mov rS , rD stor rS , rD
10001101 S D 10001111 S D
10010001 S D Table 3: Extended Instructions
Copy register rS to register rD .
Store word from register rS to memory at address in register rD.
Store byte from register rS to memory at address in register rD.
rD ← rS memory[rD] ← rS
(byte)memory[rD] ← rS
load rS , rD
10001110 S D
Load word into register rD from memory pointed to by register rS.
rD ← memory[rS]
loadb rS , rD
10010000 S D
Load byte into register rD from memory pointed to by register rS.
rD ← (byte)memory[rS]
storb rS , rD
Mnemonic Encoding Description Function
jmp L
11000001 0
Absolute jump to label L.
PC ← memory[PC]
call L
11000010 0
Absolute call to label L..
r15 ← r15 – 2 memory[r15] ← PC + 2 PC ← memory[PC]
loadi V, rD
11100001 D 0
Load immediate value or address V into register rD.
rD ← memory[PC] PC ← PC + 2
Note that in the case of extended instructions, the label L or value V are encoded as a single word (16-bit value) following the word containing the instruction. The 0 in the encodings above represents a 4-bit 0 vector.
An assembler is provided for you to use (if needed). Please see the manual at the end of the assignment.
The Xtra Translation Specification (IMPORTANT)
The binary translation is conducted in the following manner. The translator
1. Opens the specified file containing the X binary code.
2. Outputs a prologue (see below), which will be the same for all translations. 3. It then enters a loop that
a. Reads the next instruction from the binary
b. Decodes the instruction, and
c. Outputs the corresponding x86 assembly instruction(s). If the instruction is an extended,
an additional two bytes will need to be read.
d. The loop exits when the instruction composed of two 0 bytes is read.
4. Outputs an epilogue.
Prologue
The translator first outputs a simple prologue that is the same for all translations. The prologue is shown on the right. Epilogue
After the translator finishes translating, it outputs a simple ep- ilogue that is the same for all translations. The epilogue is shown on the right.
Translation
Each X instruction will need to be translated into
the corresponding instruction or instructions in
x86-64 assembly. See table on right for examples.
Most instructions will have a direct corresponding
instruction in x86 assembly so the translation will
beeasy. Someinstructions,liketheequ,test,andcmp,instructions may require multiple x86 instructions for a single X instruction. Note: The translator will need to perform a register mapping. Register Mapping
The X architecture has 16 general and the F status register. In x86-64
there are also 16 general purpose registers. The register mapping on
the right must be used when translating from X to x86-64. Note that
for this exercise register r13 will not be used by the X executables. In-
stead of r13 (X) being mapped to r15 (x86), the F register (X) is mapped
to register r15 (x86). Note: for this assignment, It is ok to map 16-bit registers to 64-bit registers. r9 Debug mode STD and CLD
.globl test
test:
push %rbp
mov %rsp, %rbp
pop %rbp ret
mov $42, %rax
add %rax, %rdi
%rbx
%rdx
%rdi
%r9
%r11
%r13
%r15
%rsp
call debug
X Instruction Output x86 Assembly
mov r0, r1
mov %rax, %rdi
loadi 42, r0
add r0, r1
push r0
push %rax
X Registers x86 Registers
r0
%rax
r1 r3 r5 r7
r2
%rcx
r4
%rsi
r6
%r8
r8
%r10
r10
%r12
The std and cld X instructions enable and disable debug mode on the X architecture. However, debug mode does not exist in x86-64. Instead, when a std instruction is encountered, the translator should set an internal debug flag in the translator and, clear the debug flag when it encounters the cld instruction.
When the debug flag is true, the translator should output the assembly code on the right before translating each X instruction.
Output and the OUT Instruction (For Task 2)
r11 F r15
r12
%r14
r14
%rbp
On the X architecture, the out rN instruction outputs to the screen the character stored in register rN. However, no such instruction exists in x86-64. Instead, the out instruction is translated to a call to the function outchar(char c), which performs this function. Recall that the first argument is passed in register %rdi. Consequently, the corresponding translation code will need to save the current value of %rdi on the stack, move the byte to be printed into %rdi, call outchar, and restore %rdi.
Your task will be to implement the Xtra binary translator which is used to translate into x86 assembly programs assembled with the X assembler.
Task 1: Implement the Simple Xtra
Your first task is to implement a simple version of the translator that works for the simple instructions. The source file main.c should contain the main() function. The translator should:
1. Take one (1) argument on the command line: The argument is the object/executable file of the program to translate. For example, the invocation
./xtra hello.xo
instructs the translator to translate the program hello.xo into x86-64 assembly.
2. Open for reading the file specified on the command-line.
3. Output (to stdout) the prologue.
4. In a loop,
a. Read in instruction.
b. If the instruction is 0x00 0x00, break out of the loop.
c. Translate the instruction and output (to stdout) the x86-64 assembly.
5. Output (to stdout) the epilogue.
Input
The input to the program is via the command line. The program takes one argument, the name of the file containing the assembled X code.
Processing
All input shall be correct. All program files shall be at most 65536 bytes (64KB). The translator must be able to translate all instructions except:
Instruction Description
ret
Return from a procedure call.
br L
jmp L
load rS , rD loadb rS , rD out rS
Branch relative to label L if condition bit is true.
Absolute jump to label L.
Load word into register rD from memory pointed to by register rS. Load byte into register rD from memory pointed to by register rS. Output character in rS to stdout.
jr L
Jump relative to label L.
call L
Absolute call to label L.
stor rS , rD
Store word from register rS to memory at address in register rD.
storb rS , rD
Store byte from register rS to memory at address in register rD.
Recommendation: While no error checking is required, it may be helpful to still do error checking, e.g., make sure files are properly opened because it will help with debugging as well.
Output
Output should be to stdout. The output is the translated assembly code. The format should ATT style assembly. The exact formatting of the assembly is up to you, but the assembly code will be passed through the standard assembler (as) on timberlea. See next section for how to test your code. (See example)
Testing
To test your translator, the test scripts will assembler, link, and run the translated code! J A runit.sh script is provided. The script takes an X assembly file as an argument:
./runit.sh foo.xas The script:
1. Assembles the .xas file with the provided (xas) to create a .xo file.
2. Runs xtra on the .xo file, to create a corresponding x86 .s assembly file.
3. Assembles, compiles, and links the generated assembly file with some runner code, creating an
executable. Therunneriscomposedofrunner.c,regsdump.s,andthetranslated.sfile.
Please DO NOT delete the first two files.
4. Runs the executable.
This script is used by the test scripts and is also useful for you to test your code.
Most of the tests use the std instruction to turn on debugging and output the state of the registers after each instruction is executed. For most of the tests the output being compared are the register values.
Example
Original X assembly code Translated x86 code
loadi 2, r0
loadi 3, r1
loadi 4, r2
loadi 5, r3
loadi 7, r5
std # turn debugging on
add r2, r3
mul r2, r1
cld # turn debugging off neg r0
inc r5
.literal 0
.globl test
test:
push %rbp
mov %rsp, %rbp
mov $2, %rax
mov $3, %rbx
mov $4, %rcx
mov $5, %rdx
mov $7, %rdi
call debug
add %rcx, %rdx
call debug
imul %rcx, %rbx
call debug
neg %rax
inc %rdi
pop %rbp
ret
Task 2: The Full Translator
Your second task is to extend xtra to translate the instructions exempted in Task 1. lation for the following instructions.
Implement trans-
Instruction Description
ret
Return from a procedure call.
br L
jmp L
load rS , rD loadb rS , rD out rS
Branch relative to label L if condition bit is true.
Absolute jump to label L.
Load word into register rD from memory pointed to by register rS. Load byte into register rD from memory pointed to by register rS. Output character in rS to stdout.
jr L
Jump relative to label L.
call L
Absolute call to label L.
stor rS , rD
Store word from register rS to memory at address in register rD.
storb rS , rD
Store byte from register rS to memory at address in register rD.
Input
The input is the same as Task 1.
Processing
The processing is the same as for Task 1. The challenge is that translation is a bit more challenging.
First, for many of the additional instructions you will need to emit more than one assembly instruction. This is particularly true for the conditional branching and output instructions.
Second, for the branching instructions you will need to compute the labels where to branch to. The easy solution is to create a label for each instruction being translated. The label should encode the address in the name. For example, L1234 would be the label for the X instruction at address 1234. By doing this, you will not need to keep a list or database of labels.
Third, the addresses used by the load and store are full 64-bit values.
Output
The output is the same as Task 1.
Example
Original X assembly code Translated x86 code
loadi 1, r0
jmp j1 j2:
loadi 3, r0
jmp j3 j1:
loadi 2, r0
jmp j2 j3:
std # turn debugging on
loadi 4, r0
.literal 0
.globl test
test:
push %rbp
mov %rsp, %rbp
.L0000:
mov $1, %rax
.L0004:
jmp .L0010
.L0008:
mov $3, %rax
.L000c:
jmp .L0018
.L0010:
mov $2, %rax
.L0014:
jmp .L0008
.L0018:
.L001a:
call debug
mov $4, %rax
.L001e:
call debug
pop %rbp
ret
Hints and Suggestions
• Use the unsigned short type for all registers and indices.
• Use two files: one the main program and one for the translator loop.
• Start early, this is the hardest assignment of the term and there is a lot to digest in the assignment
specifications.
Assignment Submission
Submission and testing are done using Git, Gitlab, and Gitlab CI/CD. You can submit as many times as you wish, up to the deadline. Every time a submission occurs, functional tests are executed, and you can view the results of the tests. To submit use the same procedure as Assignment 0.
Grading
If your program does not compile, it is considered non-functional and of extremely poor quality, mean- ing you will receive 0 for the solution.
The assignment will be graded based on three criteria:
Functionality: “Does it work according to specifications?”. This is determined in an automated fashion by running your program on several inputs and ensuring that the outputs match the expected outputs. The score is determined based on the number of tests that your program passes. So, if your program passes t/T tests, you will receive that proportion of the marks.
Quality of Solution: “Is it a good solution?” This considers whether the approach and algorithm in your solution is correct. This is determined by visual inspection of the code. It is possible to get a good grade on this part even if you have bugs that cause your code to fail some of the tests.
Code Clarity: “Is it well written?” This considers whether the solution is properly formatted, well docu- mented, and follows coding style guidelines. A single overall mark will be assigned for clarity. Please see the Style Guide in the Assignment section of the course in Brightspace.
The following grading scheme will be used:
Task 100% 80% 60% 40% 20% 0%
Functionality (20 marks)
Equal to the number of tests passed.
Solution Quality Task 1
(15 marks)
Implemented correctly. Code is robust.
Implemented cor- rectly. Code is not robust.
Some minor bugs.
Major flaws in implementation
An attempt has been made.
Solution Quality Task 2
(5 marks)
Implemented correctly. Code is robust.
Implemented cor- rectly. Code is not robust.
Some minor bugs.
Major flaws in implementation
An attempt has been made
Code Clarity (10 marks) Indentation, for- matting, naming, comments
Code looks pro- fessional and fol- lows all style guidelines
Code looks good and mostly fol- lows style guide- lines.
Code is mostly readable and mostly follows some of the style guidelines
Code is hard to read and fol- lows few of the style guidelines
Code is not legible
No code submitted or
code does not compile
Assignment Testing without Submission
Testing via submission can take some time, especially if the server is loaded. You can run the tests without submittingyourcodebyusingtheprovidedruntests.shscript. Runningthescriptwithnoarguments will run all the tests. Running the script with the test number, i.e., 00, 01, 02, 03, ... 09, will run that specific test. Please see below for how run the script.
Get your program ready to run
If you are developing directly on the unix server,
1. SSH into the remote server and be sure you are in the xtra directory. 2. Be sure the program is compiled by running make.
If you are using CLion
1. Run your program on the remote server as described in the CLion tutorials. 2. Open a remote host terminal via Tools → Open Remote Host Terminal
If you are using VSCode
1. Run your program on the remote server as described in VSCode tutorials.
2. Click on the Terminal pane in the bottom half of the window or via Terminal → New Terminal
Run the script
3. Run the script in the terminal by using the command:
./runtest.sh
to run all the tests, or specify the test number to run a specific test, e.g. :
./runtest.sh 07
You will see the test run in the terminal window.
The X Assembler (xas)
An assembler (xas) is provided to allow you to write and compile programs for the X Architecture. To make the assembler, simply run “make xas” in the xtra directory. To run the assembler, specify the assembly and executable file on the command-line. For example,
./xas example.xas example.xo
Assembles the X assembly file example.xas into an X executable example.xo.
The format of the assembly files is simple.
1. Anything to the right of a # mark, including the #, is considered a comment and ignored.
2. Blank lines are ignored.
3. Each line in the assembly file that is not blank must contains a directive, a label and/or an instruc-
tion. If the line contains both a label and an instruction, the label must come first. 4. A label is of the form
identifier:
where identifier consists of any sequence of letters (A-Za-z), digits (0-9), or underscores ( ) as long the first character is not a digit. A colon (:) must terminate the label. A label represents the corre- sponding location in the program and may be used to jump to that location in the code.
5. An instruction consists of a mnemonic, such as add, loadi, push, etc., followed by zero or more operands. The operand must be separated from the mnemonic by one or more white spaces. Multiple operands are separated by a comma.
6. If an operand is a register, then it must be in the form r# where # ranges between 0 and 15 inclu- sively. E.g., r13.
7. If the instruction is an immediate, then the argument may either be a label, or an integer. Note: labels are case-sensitive. If a label is specified, no colon should follow the label.
8. Directives instruct the assembler to perform a specific function or behave in a specific manner. All directives begin with a period and are followed by a keyword. There are three directives: .lit- eral, .words and .glob, each of which takes an operand.
(a) The .literal directive encodes a null terminated string or an integer at the present
location in the program. E.g.,
mystring:
.literal "Hello World!" myvalue:
.literal 42
encodes a nil-terminated string followed by a 16-bit (1 word) value representing the dec- imal value 42. In this example, there are labels preceding each of the encodings so that it is easy to access these literals. That is, the label mystring represents the address (rel- ative to the start of the program) where the string is encoded, and the label myvalue represents the address (relative to the start of the program) of the value. This is used in the hello.xas example.
(b) The.wordsdirectivesetsasideaspecifiednumberofwordsofmemoryatthepresent
location in the program. E.g., myspace:
.words 6
allocates 6 words of memory at the present point in the program. This space is not initial- ized to any specific value. Just as before, the label preceding the directive represents the address of the first word, relative to the start of the program. This is used in xrt0.xas to set aside space for the program stack.
(c) The .glob directive exports the specified symbol (label) if it is defined in the file and imports the specified symbol (label) if it is used but not defined in the file. E.g.,
.glob foo .glob bar ...
loadi bar, r0 ...
foo:
.literal "Hello World!"
declares two symbols (labels) foo and bar. Symbol foo is declared in this file, so it will be exported (can be accessed) in other files. The latter symbol, bar, is used but not defined. When this file is linked, the linker looks for the symbol (label) definition in other files makes all references to the symbol refer to where it is defined.
Note: it is recommended that you place literals and all space allocations at the end of your program, so that they will not interfere with program itself. If you do place literals in the middle of your program, you will need to ensure that your code jumps around these allocations.
There are several example assembly files provided (ending in .xas). You can assemble them by invoking
the assembler, for example:
./xas example.xas example.xo
This invocation will cause the assembler to read in the file example.xas and generate an output file example.xo. Feel free to look at the code for the assembler.
請加QQ：99515681 郵箱：99515681@qq.com WX：codehelp
