Bonus Question 1

Deadline	Tuesday, December 5, 11:59pm Extensions are not given for Bonus Questions
Name on Marmoset	BQ1
To Submit	`loader.asm`
Bonus Points	Up to +0.25% on your final grade

Writing a Loader

This question is about writing a relocating loader for MIPS programs.

Write a MIPS procedure called loader that works as follows.

The procedure should take one parameter in $1, which is a memory address.
It should then read a MERL file from standard input, and copy the MIPS code segment into memory at starting address $1, performing relocation using the data in the MERL footer if needed. For the precise details of the loading and relocation process, review your lecture notes, the course notes, or the lecture slides.
After loading the program, it should place the number of words in the MIPS code segment in $3, then return.

Notes:

Your procedure should preserve all general-purpose registers. For this question, Marmoset won't explicitly check that registers are preserved, but the main program that Marmoset uses to call your loader might not work correctly if you don't preserve registers.
The MERL files provided as input will only contain REL (relocation) entries, not ESR or ESD entries. So your loader does not need additional logic to skip ESRs and ESDs.

MERL Specification

The MERL Specification may be useful as a reference for this question.

Reading Words

We provide a procedure called readWord which reads a word (4 bytes) from standard input and places the word in $3. Since MERL files are meant to be read word-by-word rather than byte-by-byte, this will help you read and process the input MERL file more easily.

The readWord procedure (also available as a downloadable file, readWord.asm)

readWord:
sw $1,  -4($30)
sw $2,  -8($30)
sw $4, -12($30)
sw $5, -16($30)
sw $6, -20($30)
sw $7, -24($30)
sw $8, -28($30)
lis $8
.word 28
sub $30, $30, $8
lis $4
.word 0x01000000
lis $3
.word 0x00010000
lis $2
.word 0x00000100
lis $1
.word 0xffff0004
lw $8, 0($1)
lw $7, 0($1)
lw $6, 0($1)
lw $5, 0($1)
multu $8, $4
mflo $8
multu $7, $3
mflo $7
multu $6, $2
mflo $6
add $4, $8, $7
add $3, $6, $5
add $3, $4, $3
lis $8
.word 28
add $30, $30, $8
lw $1,  -4($30)
lw $2,  -8($30)
lw $4, -12($30)
lw $5, -16($30)
lw $6, -20($30)
lw $7, -24($30)
lw $8, -28($30)
jr $31

Testing

We provide several additional files and tools to help you test your loader, including:

An assembler, cs241.linkasm, that can be used to generate MERL files
A MIPS program load-and-print.asm that calls your loader procedure and prints out the loaded data, so you can check that your loader is doing the right thing
A library for working with MERL files (C++, Racket) and a program using this library (C++, Racket) that reads a MERL file and performs relocation, allowing you to confirm the expected result of relocating the MIPS code segment

More details are given below.

Creating MERL Files

To test your loader, you will need to create MERL files.

You can use the assembler cs241.linkasm for this. It works just like cs241.binasm except the output is a MERL file.

Viewing the Loaded Data

The MIPS emulators in this course do not have a convenient way to view the contents of memory, so it is not straightforward to tell whether your loader actually accomplished its task.

We provide a MIPS program called load-and-print.asm to help test your loader. The program calls your loader, then prints a hexadecimal representation of the data you loaded into memory. This allows you to actually see the data you loaded and check whether it is correct.

Note that the memory address used as the parameter to your loader procedure (the starting address where the MIPS code should be loaded) is hardcoded at the top of this file. You can modify this line to test with different starting addresses.

Marmoset will use a similar program to load-and-print.asm check the correctness of your loader. Note that if your loader procedure is implemented incorrectly, does not preserve all general-purpose registers, or gives an incorrect return value in $3, the load-and-print.asm program may crash, or it may produce unexpected output that is not related to the loaded code.

Checking Correctness

To check that the output produced by load-and-print.asm is correct, compare it with the C++ program reloc.cc or Racket program reloc.rkt.

Both programs require you to pass a memory address as a command line argument (in decimal or hexadecimal). They then read a MERL file from standard input, relocate the MIPS code segment of the file to work at the provided address, then print a hexadecimal representation of the relocated MIPS code segment.

To compile the C++ program or run the Racket program, you will also need to download the following MERL library and place it in the same directory as the main program. This MERL library is also used by the starter code for Bonus Question 2.

C++ MERL Library: merl-cpp.zip (contains two files, merl.h and merl.cc)
Racket MERL Library: merl.rkt

You can then compile the C++ program with the command:

g++ reloc.cc merl.cc -o reloc

And run the program as follows:

./reloc starting_address < input.merl

Alternatively, you can run the Racket program as follows (requires merl.rkt in the same directory):

racket reloc.rkt starting_address < input.merl

The standard output produced by load-and-print.asm should be identical to the standard output produced by the C++ or Racket program.

The C++ and Racket programs are intended to have identical behaviour (on valid inputs). Please report any discrepancies you notice.

Complete Example

Let's create the following file and call it input.asm:

label: .word label
two41: .word 0x241
kitten: .word meow
end: jr $31
meow: .word end

Run this program through cs241.linkasm to create a MERL file for the program:

cs241.linkasm < input.asm > input.merl

A MERL file contains raw binary data, so trying to view it with a text editor or with a command like cat will just produce unreadable gibberish. You can examine the MERL file using a tool like cs241.binview or xxd:

xxd -c4 < input.merl
00000000: 1000 0002  ....
00000004: 0000 0038  ...8
00000008: 0000 0020  ...
0000000c: 0000 000c  ....
00000010: 0000 0241  ...A
00000014: 0000 001c  ....
00000018: 03e0 0008  ....
0000001c: 0000 0018  ....
00000020: 0000 0001  ....
00000024: 0000 000c  ....
00000028: 0000 0001  ....
0000002c: 0000 0014  ....
00000030: 0000 0001  ....
00000034: 0000 001c  ....

The first 3 lines are the MERL header. The next 5 lines (up to and including line 0x1c) are the MIPS code. We can see that:

.word label was assembled to 0x0c because it appears right after the 12-byte header
.word meow was assembled to 0x1c referring to the last line of the code
.word end was assembled to 0x18 referring to the second last line of the code

The remaining lines are the MERL footer, which contains REL entries for lines 0x0c, 0x14, and 0x1c, which are the three locations in the file where labels were used in a .word directive and therefore correspond to words that need to be relocated.

Let's now combine our loader with load-and-print.asm and run it. Recall that the starting address passed to your loader procedure is hardcoded at the top of load-and-print.asm. By default, this address is 0x2410.

mips.stdin <(cat load-and-print.asm loader.asm | cs241.binasm) < input.merl
Running MIPS program.
00002410
00000241
00002420
03e00008
0000241c
MIPS program completed normally.
...

We observe that the three words which had corresponding REL entries have been relocated so that they would refer to the correct locations if this MIPS code was loaded at address 0x2410:

The first word (at address 0x2410) refers to itself (address 0x2410)
The third word (at address 0x2418) refers to the last word (address 0x2420)
The last word (at address 0x2420) refers to the second last word (address 0x241c)

We can confirm the correctness by comparing with the C++ or Racket relocation program. For example, running the C++ version with this same input file and starting address:

./reloc 0x2410 < input.merl
00002410
00000241
00002420
03e00008
0000241c

Now let's run the loader again with a different starting address. Modify load-and-print.asm so that the starting address is 0x777c.

mips.stdin <(cat load-and-print.asm loader.asm | cs241.binasm) < input.merl
Running MIPS program.
0000777c
00000241
0000778c
03e00008
00007788
MIPS program completed normally.
...

Let's now compare with the Racket version of the relocation program (just to demonstrate both the C++ and Racket versions):

racket reloc.rkt 0x777c < input.merl
0000777c
00000241
0000778c
03e00008
00007788