=======================[ Ground rules ]=======================

You may use any tools including AI/LLMs for this assignment. We expect you to
follow through the manual steps as we describe them, so that you can build up
fluency. Think of it as learning a foreign language: you can always paste a
quote into an automatic translator, but you'll never develop an appreciation
for the language's style and structure, and will miss most of the
nuance. These are the things that will matter in this class.

You can discuss general issues, techniques, and tools with other students.
You can show others your technique but you should not share solutions.  

=======================[ Homework 1 ]=======================

You will receive a binary file generated for you personally and compiled to
run on a Linux x86-64 bit machine. This file contains the following function
and some other functions that construct some data structures than run this
function and some others on these data structures. 

0000000000001260 <test>:
    1260:       48 89 f8                mov    %rdi,%rax
    1263:       eb 16                   jmp    127b <test+0x1b>
    1265:       48 8b 40 08             mov    0x8(%rax),%rax
    1269:       48 85 c0                test   %rax,%rax
    126c:       74 12                   je     1280 <test+0x20>
    126e:       48 8b 7f 08             mov    0x8(%rdi),%rdi
    1272:       48 8b 40 08             mov    0x8(%rax),%rax
    1276:       48 39 c7                cmp    %rax,%rdi
    1279:       74 08                   je     1283 <test+0x23>
    127b:       48 85 c0                test   %rax,%rax
    127e:       75 e5                   jne    1265 <test+0x5>
    1280:       31 c0                   xor    %eax,%eax
    1282:       c3                      ret
    1283:       b8 01 00 00 00          mov    $0x1,%eax
    1288:       c3                      ret

If you can't stand the AT&T syntax, see below for the Intel disassembly.

You can receive this homework in Aarch64 ARM assembly. See below for the
M1 assembly snippet.

====================[ Easy Mode or Hard Mode? ]===================

Before you go further, you can decide if you want to do the assignment
in the easy mode or a harder mode. For the easy mode, we'll give you
the source code file so that you'll see the C source of all the other
functions. For the harder mode we'll only give you the binary.

The harder mode is not much harder because LLMs these days are pretty
good at recovering normally compiled, unobfuscated source code from the
bare binary. So the easy mode will bring you 20 points for a correct
solution, the harder mode will bring you 5 extra points.

=======================[ Getting the file ]=====================

You filename is tied to your student id. If you if is f00xyzt, fetch
your file from
 https://cosc59.gitlab.io/hw1/x86/F00XYZT.zip       if working on x86-64 Linux
 https://cosc59.gitlab.io/hw1/aarch64/F00XYZT.zip   if working on Apple Silicon

Discard the .c if you are going for the hard mode. 

Please ask the TAs if something is failing.

==========================[ Assignment ]===================

1. Describe what the function test() does. Show your work.

2. Trace the values of RAX and RDI throughout the data structures
   that test() gets called on in the program handed to you. Hand in
   your work.

   We recommend that you manually trace the instructions, on paper.
   Executing CPU instructions in your head is important: that way
   you will catch any misconceptions you might have, and wouldn't
   gloss over details that actually matter.

   A useful technique is to draw structures in memory as boxes and
   pointers as arrows. It's an abstraction, because it hides the
   actual memory addresses of objects but it's useful because it shows
   the chains of pointers and aliasing (when who pointers point to the
   same address and object). See 
     https://cosc59.gitlab.io/hw1/example-linked-list.png
   We will use this technique a lot when we talk about abstract machines.

3. Count the number of instructions executed in every call to test()
   on these data structures. Show your work.

   Once again, we recommend that you manually step through the
   instructions, in your head, keeping track on paper. 

=======================[ Submission ]=======================

Submit your work as a single PDF to yaning.jia.gr@dartmouth.edu by Tuesday,
September 29 EOD. Make sure it's legible and that your student ID is
included somewhere in the PDF.

Remember you can go to any of the TAs' office hours or reach out by email
if you have any questions!

====================[ Intel disassembly of test() ]====================

0000000000001260 <test>:
    1260:	48 89 f8             	mov    rax,rdi
    1263:	eb 16                	jmp    127b <test+0x1b>
    1265:	48 8b 40 08          	mov    rax,QWORD PTR [rax+0x8]
    1269:	48 85 c0             	test   rax,rax
    126c:	74 12                	je     1280 <test+0x20>
    126e:	48 8b 7f 08          	mov    rdi,QWORD PTR [rdi+0x8]
    1272:	48 8b 40 08          	mov    rax,QWORD PTR [rax+0x8]
    1276:	48 39 c7             	cmp    rdi,rax
    1279:	74 08                	je     1283 <test+0x23>
    127b:	48 85 c0             	test   rax,rax
    127e:	75 e5                	jne    1265 <test+0x5>
    1280:	31 c0                	xor    eax,eax
    1282:	c3                   	ret
    1283:	b8 01 00 00 00       	mov    eax,0x1
    1288:	c3                   	ret

====================[ Aarch64 assembly of test() ]====================

0000000100003db4 <_test>:
100003db4: e8 03 00 aa 	mov	x8, x0
100003db8: 28 01 00 b4 	cbz	x8, 0x100003ddc <_test+0x28>
100003dbc: 08 05 40 f9 	ldr	x8, [x8, #8]
100003dc0: e8 00 00 b4 	cbz	x8, 0x100003ddc <_test+0x28>
100003dc4: 00 04 40 f9 	ldr	x0, [x0, #8]
100003dc8: 08 05 40 f9 	ldr	x8, [x8, #8]
100003dcc: 1f 00 08 eb 	cmp	x0, x8
100003dd0: 41 ff ff 54 	b.ne	0x100003db8 <_test+0x4>
100003dd4: 20 00 80 52 	mov	w0, #1
100003dd8: c0 03 5f d6 	ret
100003ddc: 00 00 80 52 	mov	w0, #0
100003de0: c0 03 5f d6 	ret