Skip to main content

1. Sort in Assembly

Goals​

  • Understand how the stack works
  • Understand x86 calling conventions
  • Learn how to write x86 assemblies

Preparation​

Download the handout tarball, assign-1-handout.tar.gz and then decompress it. The following commands show how you download the tarball using wget and then decompress it using the command tar.

$ wget https://compsec.snu.ac.kr/class/systems-programming/files/assign-1-handout.tar.gz

...

$ tar -xvf ./assign-1-handout.tar.gz
assign-1-handout/
assign-1-handout/prepare-submit.sh
assign-1-handout/main.c
assign-1-handout/Makefile
assign-1-handout/sort_tree.s

$ cd assign-1-handout

$ ls -1
Makefile
main.c
prepare-submit.sh
sort_tree.s

Problem description​

The program, main is implemented with main.c and sort_tree.s. Once executed, main first picks 10 random values (see gen_rand_nums()). Then it constructs and then populates the binary search tree with those 10 random values (see make_tree()).

Your job is to implement sort_tree(), which traverses the tree (where its root is provided with the parameter, root) to sort all tree elements into the array sorted_nums[]. Of course we don't ask you to implement this sort_tree() in C. You must implement your sort_tree() using x86 assembly, which should be written in the file sort_tree.s. To be more specific, the below shows the provided sort_tree.s, and your job is to write your own assemblies where TODO comments are placed.

sort_tree.s
	.text
	.globl	sort_tree
	.type	sort_tree, @function
sort_tree:
	pushq	%rbp
	movq	%rsp, %rbp

        /* TODO: Write your code! */

	leave
	ret
	.size	sort_tree, .-sort_tree
	.section	.note.GNU-stack,"",@progbits

The reference solution implements the in-order tree traverser algorithm with around 40 lines of assembly code. You don't need to follow the reference implementation though.

tip

If it's unclear which logics should be implemented within sorted_tree(), you can refer to check_if_sorted(). This function checks if (1) the given array, sorted_nums[], is accordingly sorted and (2) each element of sorted_nums[] indeed presents in nums[].

warning

In this problem, you are only allowed to modify sort_tree.s. As such, you are NOT allowed to modify any other files.

Run and test your implementation​

After implementing your sort_tree.s, you can run and test as follows.

$ ls
Makefile  main.c  sort_tree.s

$ make
gcc -fno-asynchronous-unwind-tables -fcf-protection=none -c main.c -o main.o
gcc -fno-asynchronous-unwind-tables -fcf-protection=none -c sort_tree.s -o sort_tree.o
gcc main.o sort_tree.o -o main

$ ls
Makefile  main  main.c  main.o  sort_tree.o  sort_tree.s

$ ./main
[+] PASS

If you see the output [+] PASS by executing main, then your implementation is likely correct. Make sure that the executable main is generated based on your sort_tree.s implementation.

warning

Note that it is not guranteed that your submission will received the full scores simply because you meet the test condition above. We may extend the testcases in the evaluation, which further checks if your implementation correctly follows the problem specification. Since we won't provide such extended testcases to you, it's your job to thoroughly check if your implementation is correctly done.

Submission​

Prepare your submission by executing the script, prepare-submit.sh. It creates a compressed tar ball, assign-1-submit.tar.gz using your ./sort_tree.s.

$ bash ./prepare-submit.sh
[*] Remove tar file...
[*] Compress files...
./sort_tree.s
[*] Successfully Compressed!
[*] Done! You are ready to submit: assign-1-submit.tar.gz

Option 1: Download from the Remote Server Container​

If you are using the container on the kayle server, you can transfer the assign-1-submit.tar.gz file to your local computer using the scp command:

# Open your local terminal (e.g., PowerShell, Bash, etc.)
$ scp -P <port> compsec@kayle.snu.ac.kr:~/assign-1-handout/assign-1-submit.tar.gz ./
compsec@kayle.snu.ac.kr's password:
assign-1-submit.tar.gz   100%  273    36.8KB/s   00:00

$ ls
assign-1-submit.tar.gz
  • <port>: This is the SSH port used to connect to the container.

Option 2: Download from Your Local Machine’s Container​

If you are running the container on your own local machine, use the following scp command to copy the file from the container:

# Open your local terminal (e.g., PowerShell, Bash, etc.)
$ scp -P 22222 compsec@localhost:~/assign-1-handout/assign-1-submit.tar.gz ./
compsec@localhost's password:
assign-1-submit.tar.gz   100%  273    36.8KB/s   00:00

$ ls
assign-1-submit.tar.gz

Finally, once you have the assign-1-submit.tar.gz file on your local machine, upload it to the eTL.

Honor Code​

You should work alone for this assignment. You may ask questions or discuss ideas through eTL or with your classmates. However, you SHOULD write your own code. We will run the plagiarism checker, and if you get caught, you will get F and be notified to the student committee in the department. The plagiarism checker works pretty good, and we have strong records in catching genuine cheaters. Let's not cheat. It's not only harming you. It's harming your classmates.

warning

The student who has shown his code to others will get the same penalty as the one who cheated. So NEVER share your code!

warning

We have collected all submissions from the previous course offerings, all of which will be checked against yours. So do NOT submit the solution of your friends or seniors who took the class before.