Matthew's Stats

    Time it took Matthew to complete: 2 hours (but I was super rusty when I did it. Probably 45 – 60 mins now)

What To Submit

    editDist.s

Prompt

Translate the given program, editDist.c , into an assembly program, editDist.s, that is capable of finding the edit distance between two strings that are up to 100 characters long.
Input

    string1: The first string to use in the edit distance calculation
        Label: string1
        Space: 101 bytes
    string2: The second string to use in the edit distance calculation
        Label: string2
        Space: 101 bytes

Output

The edit distance between string1 and string2 should be placed in EAX.
Making Sure Your Code Works With The Grader

    AFTER the last line of code that you wish to be executed in your program please place the label done:.
    Make sure that there is an instruction after the done label
    After the last instruction you should have at least one blank line.

In general the .text section of your program should look like this

1. _start:
2.   Your Code
3. done:
4.   nop
5.

Notice that there is a blank line after the nop

In addition to the above formatting conditions, IT IS OF VITAL IMPORTANCE THAT YOU NAME YOUR LABELS AS SPECIFIED AND MAKE THE APPROPRIATE AMOUNT OF SPACE FOR EACH VARIABLE! I will be using gdb to test your code and if your labels do not match or there is not enough space for the values I try and put in, the tests will fail.
Translating The Calls to Malloc

The C program that you were given can find the edit distance between two strings of anything length, which is why it had to make calls to malloc. Your assembly program, HOWEVER, needs to only work with strings that are up to 100 characters long so you can just statically allocate space to fit the largest input and you will be fine.
What Is Edit Distance?

The edit distance between two strings is the minimum number of edits that need to be performed on one string to transform it into another where an edit can be adding a character, deleting a character, or changing a character into another character.

It isn't important that you understand the code in editDist.c, just that you be capable of translating it to assembly. This is you akin to being a human compiler because the real compiler doesn't truly understand what your code means, it just translates C code to assembly. If you are curious about the edit distance algorithm, you can read up on it in this Wikipedia Article. Google is also helpful but Chat-GPT might be even more helpful. You might ask it

    Explain the intuition behind the edit distance algorithm and how it works.
    Work through the edit distance example step by step on the strings sitting and kittens and explain what you are doing on each step.

Common Problems

One of the biggest issues that students have translating is the swap function. They run into trouble because the swap function cannot swap constants. I.E. you can't do swap(3,4). This seems obvious but don't forget that labels are also constants, so you can't do swap($label1, $label2). I'm mixing C and assembly syntax in the previous statement, but hopefully you get the point. So if you want to swap a value, make sure it is in something swappable: either a register or memory.

Also try not to do the following if you are trying to swap x and y

int x = 10, y = 20;
int temp1 = x, temp2 = y;
swap(&temp1, &temp2);

as it won't swap x and y.
Hints

    It is worth the time to write a Makefile to make compiling easier
    You don't have to implement edit distance from scratch! Please translate the given C code editDist.c
    When testing on your machine, it is probably easiest to set string1 and string2 to the strings you want to test, recompile your program, and then run it through gdb to see if it works. If you are doing this, don't forget to set string1 and string2 back to 101 bytes of space before submitting.
    Breaking the problem into subroutines makes it easier to solve and test (at least in my opinion).