# Benjamin H. Somma
# Homework 2.4 Edit Dist (Assembly)
# 2/14/2020

/*
NOTES:
1. The label for the first string should be string1 and the label for the second string should be string2.
2. The edit distance between string1 and string2 should be placed in EAX.
3. For each string please allocate space for 100 bytes.
  a. .space 100
--- Syntax Notes ---
1. ret = Pop PC
2. cld = clear the direction flag
*/

.data
value:
  .long 0

len_i:
  .long 0

len_j:
  .long 0

# d[100][100]# "you must allocate space for 100 bytes in your final submission"
string1:
  .space 100

string2:
  .space 100

array: # repeat 1,000 times
  .rept 1000
  .long 0
  .endr

.text
.global _start

# int m = strlen(string1)
# int n = strlen(string2)
strlen:
push %ecx
push %edi
sub %ecx, %ecx
mov $-1,%ecx
sub %al, %al
cld # clear the direction flag
repne scasb # repeat while not equal, if direction EDI -= 1 else EDI += 1
neg %ecx
sub $1, %ecx
mov %ecx, %eax
pop %edi
pop %ecx
ret # Pop PC

min1_or_2:
  cmp %ebx, %eax
  jge minimum_1
  ret

minimum_1:
  movl %ebx,%eax
  ret

min_eax:
  cmp value,%eax
  jge minnimum_2
  ret

minnimum_2:
  movl value,%eax
  ret

# # #
/*
### --- Left over code from own creation of .c program --- ###
int LevenshteinDistance(char* string1, char* string2){
    int i,j,distance_of_two_inputs,substitution_cost#
    ... ... ...
    // "return d[m, n]#"
    distance_of_two_inputs = d[i-1][j-1]#

    return distance_of_two_inputs#
}
*/
# # #

_start:

lea string1, %edi
call strlen
movl %eax, len_i
lea string2, %edi
call strlen
movl %eax, len_j
movl $0, %ecx

# // "source prefixes can be transformed into empty string by dropping all characters"
# for(i = 0# i <= m# i++){
#     d[i][0] = i#
# }
loop_one:
  cmpl %ecx, len_i
  jle exit_loop_one
  movl len_j, %eax
  imull %ecx
  movl %ecx, array(,%eax,4)
  incl %ecx
  jmp loop_one

exit_loop_one:
  movl $0, %ecx

# // target prefixes can be reached from empty source prefix by inserting every character
# for(j = 0# j <= n# j++) {
#     d[0][j] = j#
# }
loop_two:
  cmpl %ecx, len_j
  jle exit_loop_two
  movl %ecx, array(,%ecx,4)
  incl %ecx
  jmp loop_two

exit_loop_two:
  movl $1, %ecx

# for(i = 1# i <= m# i++) {
#     for(j = 1# j <= n# j++) {
#         if (string1[i-1] == string2[j-1]){
#             substitution_cost = 0#
#             // substitution_cost = d[i-1][j-1]#
#         }
#         else {
#             substitution_cost = 1#
#             // substitution_cost = d[i-1][j-1]+1#
#         }

#         d[i][j] = minimum_of_two(minimum_of_two(d[i-1][j]+1,d[i][j-1]+1), (d[i-1][j-1] + substitution_cost))#

#     }
# }
first_for_large_loop:
  cmpl %ecx, len_i
  jle exit_first_for_large_loop
  movl $1, %edx

second_for_large_loop:
  cmpl %edx, len_j
  jle exit_second_for_large_loop
  movl len_i, %esi
  movl len_j, %edi
  sub $1, %esi
  sub $1, %edi
  mov string1(,%esi,4),%esi
  mov string2(,%edi,4),%edi
  sub %esi, %edi
  cmpl $0, %edi
  jz possibility2

possibility1:
  movl %ecx, %eax
  sub $1, %eax
  movl %edx, %ebx
  sub $1, %ebx
  imull len_j
  add %ebx, %eax
  movl array(,%eax,4),%eax
  add $1, %eax

do_work:
  movl %eax, value
  movl %ecx, %eax
  sub $1, %eax
  imull len_j
  add %edx,%eax
  movl array(,%eax,4),%eax
  add $1, %eax
  movl %eax, %ebx
  movl %ecx, %eax
  imull len_j
  add %edx,%eax
  sub $1, %eax
  movl array(,%eax,4),%eax
  add $1, %eax
  call min1_or_2
  call min_eax
  movl %eax, %ebx
  movl %ecx, %eax
  imull len_j
  add %edx,%eax
  movl %ebx,array(,%eax,4)
  incl %edx
  jmp second_for_large_loop

possibility2:
  movl %ecx, %eax
  sub $1, %eax
  movl %edx, %ebx
  sub $1, %ebx
  imull len_j # signed multiplication
  add %ebx, %eax
  movl array(,%eax,4),%eax
  jmp do_work

exit_second_for_large_loop:
  incl %ecx
  jmp first_for_large_loop

exit_first_for_large_loop:
  movl %ecx, %eax
  sub $1, %eax
  movl %edx, %ebx
  sub $1, %ebx
  imull len_j
  add %ebx, %eax
  movl array(,%eax,4),%eax

done:
  nop