Homework 3
                               DEADLINE: Due Feb. 6

The "textbook" for the assembly unit of the course is "Appendix A":
  https://pages.cs.wisc.edu/~larus/HP_AppA.pdf

You will write a MIPS assembly language program.  Note that Appendix A
includes a full MIPS description.  You will want to concentrate on:
  * MIPS tutorial with examples:  Section A.5 and A.6
  * MIPS assembler directives:  Appendix A: "Assembler syntax": pp. A-47 to A-49
  * Syscalls using MIPS:  Appendix A: page A-44 (Figure A.9.1: System services)
    (You will need the following MIPS syscalls (system calls):
        print_string, print_int, and exit ('exit', for end of 'main').)
  * Full description of all MIPS instructions:  Section A.10
  * Green card for MIPS (summary or "cheat sheet"):  See course web page

We will also use the free Mars assembler (simulator).  See the course
web page for instructions on where to find it and download.

And here is an _excellent_ tutorial on how to run MARS:
  https://www.ece.ucdavis.edu/~chuah/rubinet/people/chuah/classes/eec70/eec70-f13/spimsal/MARS_bySticlaru.pdf
or here:
  https://faculty.kfupm.edu.sa/COE/aimane/coe301/lab/COE301_Lab_1_Introduction_MARS.pdf
and here is a much shorter MARS description:
  https://cs.slu.edu/~fritts/CSCI140_F12/schedule/using_MARS_simulator.html
and a nice tutorial on some very short MIPS programs:
  https://profile.iiita.ac.in/bibhas.ghoshal/COA_2021/tutorials/Tutorial_MIPS_Using_MARS.pdf

Your job is to write in assembly language the following two functions:

Define collatz(n) to be f(n,1)

Define f(n,x) to be:
  If n is 1, then f(1,x) = x.
  If n is even, then f(n,x) = f(n/2, x+1)
  If n is odd and greater than 1, then f(n,x) = f(3n+1, x+1)

You must program collatz(n) and f(n,x) in assembly.  The function f(n,x)
must be written as a _recursive_ function, as expressed above.
Your assembly program, in the 'main' routine, must then execute
a 'for loop' in assembly for collatz(i), for i from 1 to 99:
  for (i = 1; i < 100; i++) {
     printf("collatz(%d): %d\n", i, collatz(i);
  }

I have given you an implementation of the function in Python, in collatz.py.
Your assembly format must match _exactly_ the format of collatz.py.
Otherwise, your 'make check' (see below) will not work.

If you are curious about this collatz fnc, you can read the following article:
  https://www.quantamagazine.org/why-mathematicians-still-cant-solve-the-collatz-conjecture-20200922/

As before, you must submit a "tarball".  It must include a Makefile
and a README file.  You will include 'hw3.asm'.  Please do _not_
include Mars4_5.jar in your tarball.  Let's keep the tarballs small.

One of the targets of your Makefile should be
${FILE}.tar.gz, just as you did in hw1 and hw2.  As before, you will
use the 'submit' script for hw3 to submit.

Finally, your Makefile must include a 'check' target.  The graders
will run 'make check' on your program to verify that it works.
Your 'check' target will compare the output of your assembly program
with the output of collatz.py.  The Linux 'diff' command compares
the two outputs.

You will need the following targets.  (Don't forget that the Makefile
command after the target must begin with a '<TAB>' character.)

On Khoury login, it's possible to run Mars from the command line.
I suggest debugging your hw3.asm locally with the full Mars GUI.
You can then verify with 'make check' either on your local computer
or on Khoury login.  (But the graders will grade, based on Khoury login.)
For 'make check' on Khoury, you can copy from the course dir to your hw3 dir:
  cp /course/cs3650/MIPS-simulator/Mars4_5.jar ./

# The command 'tail -n +3', below, is a 'filter' command.  It omits the first
# two lines, since that is the banner for Mars itself.
hw3.out: hw3.asm Mars4_5.jar
	java -jar Mars4_5.jar hw3.asm | tail -n +3 > hw3.out

collatz.out: collatz.py
	python3 collatz.py > collatz.out

check: collatz.out hw3.out
	diff collatz.out hw3.out

And of course, you must include a standard 'clean' and 'dist' target:

# Note that this will remove your 'Mars4_5.jar'.  Keep an extra copy elsewhere.
clean:
	rm -f collatz.out hw3.out Mars4_5.jar

dist: clean
	dir=`basename $$PWD`; cd ..; tar czvf $$dir.tar.gz ./$$dir
	dir=`basename $$PWD`; ls -l ../$$dir.tar.gz