Starter/editDist.c #include #include #include int editDist(char* word1, char* word2); int min(int a, int b); void swap(int** a, int** b); int min(int a, int b){ return a

editDist/editDist.c
#include
#include
#include
int editDist(char* word1, char* word2);
int min(int a, int b);
void swap(int** a, int** b);
int min(int a, int b){
return a < b ? a:b;
}
void swap(int** a, int** b){
int* temp = *a;
*a = *b;
*b = temp;
}
int editDist(char* word1, char* word2){
int word1_len = strlen(word1);
int word2_len = strlen(word2);
int* oldDist = (int*)malloc((word2_len + 1) * sizeof(int));
int* curDist = (int*)malloc((word2_len + 1) * sizeof(int));
int i,j,dist;
//intialize distances to length of the substrings
for(i = 0; i < word2_len + 1; i++){
oldDist[i] = i;
curDist[i] = i;
}
for(i = 1; i < word1_len + 1; i++){
curDist[0] = i;
for(j = 1; j < word2_len + 1; j++){
if(word1[i-1] == word2[j-1]){
curDist[j] = oldDist[j - 1];
}//the characters in the words are the same
else{
curDist[j] = min(min(oldDist[j], //deletion
curDist[j-1]), //insertion
oldDist[j-1]) + 1; //subtitution
}
}//for each character in the second word
swap(&oldDist, &curDist);
}//for each character in the first word
dist = oldDist[word2_len];//using oldDist instead of curDist because of the last swap
free(oldDist);
free(curDist);
return dist;
}
int main(int argc, char** argv){
if(argc < 3){
printf("Usage: %s word1 word 2\n", argv[0]);
exit(1);
}
printf("The distance between %s and %s is %d.\n", argv[1], argv[2], editDist(argv[1], argv[2]));
return 0;
}
editDist/editDist.s
    .globl _start
    .data
string1: .space 100
string2: .space 100
output_string_a: .string "The distance between "
output_string_end_a:
output_string_b: .string " and "
output_string_end_b:
output_string_c: .string " is "
output_string_end_c:
output_string_d: .string ".\n"
output_string_end_d:
usage_string_a: .string "Usage: "
usage_string_end_a:
usage_string_b: .string " word1 word2\n"
usage_string_end_b:
    .text
editDist:
    push %ebp
    movl %esp, %ebp            # save the registers
    
    cld
    xor %al, %al
    xor %ecx, %ecx
    dec %ecx            # ecx = -1
    movl 8(%ebp), %edi        # address of string pushed into the stack by calling function as argmument
    repne scasb            # find the null character in the string and decrement ecx
    not %ecx            # ecx = -ecx
    push %ecx            # save the length of string 1 in the stack
    xor %ecx, %ecx
    dec %ecx            # ecx = -1
    movl 12(%ebp), %edi        # address of string pushed into the stack by calling function as argmument
    repne scasb            # find the null character in the string and decrement ecx
    not %ecx            # ecx = -ecx
    push %ecx            # save the length of string 2 in the stack
    mov -4(%ebp), %eax        # check for empty strings
    mov -8(%ebp), %ebx
    cmp $1, %eax
    je empty_string_1        # if string is empty then return the length of second string
    cmp $1, %ebx
    jne valid_string        # if second string is empty then return the length of first string
empty_string_1:
    cmp %ebx, %eax            
    cmovle %ebx, %eax
    dec %eax            
    jmp exit            # exit the function
valid_string:
    sub $8, %esp            # temporary varibles in the stack to store the address of oldDist, curDist
    mov -4(%ebp), %eax        # length of string1 in word size
    shl $2, %eax            # size in bytes
    sub %eax, %esp            # create space in stack...