Instructions
Objective
Write a program to search linked list in assembly language for matching string using GCC C++, Assembly language.
Requirements and Specifications
You are responsible to write an assembly function assignment to perform searching of a list of names stored in ascending order. This function will use the linear search algorithm. The names could be stored in mixed cases. Therefore your assembly function must do the comparison in a case insensitive manner. This function will use the C function signature but everything within this function should be assembly code using the ASM block similar to the assembly example shown in class.
Program Specification:
long search_by_name (char* list, long count, char* token);
list – the starting address of the list of structures to be searched
count – total number of names in the list
token – name to be search in the list
This function returns the Student ID of the student record in the list. While the list was constructed, the ID was populated in sequence starting with 1001. If the name is not found, then it returns 0 and prints an error message on the console.
Screenshots of output
Source Code
//* CMPE102 - Project #2 template */
#include
#include
#include
struct student
{
long ID; /* 8 bytes in 64-bit, and 4 bypes in 32-bit */
char name[24];
};
/* This function returns the char* to the name string if the input sid has a match on the student ID
from the array of student structures */
long search_by_id (char* list, long count, long sid)
{
long index=0;
asm
(
"movq %1, %%rax;" /* pointer to the beginning of the array of structures */
"movq %2, %%rbx;" /* student ID */
"movq %3, %%rcx;" /* number of array entries */
"xorq %%rdx, %%rdx;"
"loop_start:"
"cmpq %%rdx, %%rcx;"
"je not_found;"
"movq (%%rax), %%rsi;" /* moving list[i].ID to %%rsi */
"cmpq %%rsi, %%rbx;" /* compare list[i].ID to the input sid */
"je found;"
"addq $32, %%rax;" /* 32 = size of each record for 64-bit; In 32-bit, it is 28 */
"inc %%rdx;"
"jmp loop_start;"
"not_found:"
"xorq %%rax, %%rax;"
"jmp done;"
"found:"
"addq $8, %%rax;" /* skip over 8 bytes from the beginning of ID to the name field */
"done:"
: "=a" (index)
: "m" (list), "m" (sid), "m" (count)
:
);
return index;
}
long search_by_name (char* list, long count, char* token)
{
long index = 0;
asm
(
"movq %1, %%rsi;" /* point to start of structures */
"movq %2, %%rdi;" /* token address */
"movq %3, %%rcx;" /* count */
"xorq %%rax, %%rax;" /* by default, returns 0 */
"cmp $0, %%rcx;" /* if count = 0 */
"je for_end;" /* end */
"for_loop:" /* loop to go through list */
"movq $0, %%rdx;" /* i = 0*/
"string_cmp:" /* loop to compare strings */
"movb 0x8(%%rsi, %%rdx), %%bl;" /* load character from list[index].name[i] */
"movb (%%rdi, %%rdx), %%bh;" /* load character from token[i] */
"cmpb $65, %%bl;" /* compare with 'A' */
"jl conv_tok;" /* if not letter, convert token char */
"cmpb $90, %%bl;" /* compare with 'Z' */
"jg conv_tok;" /* if not letter, convert token char */
"addb $32, %%bl;" /* if uppercase letter, convert to lowercase */
"conv_tok:"
"cmpb $65, %%bh;" /* compare with 'A' */
"jl cmp_chars;" /* if not letter, compare chars */
"cmpb $90, %%bh;" /* compare with 'Z' */
"jg cmp_chars;" /* if not letter, compare chars */
"addb $32, %%bh;" /* if uppercase letter, convert to lowercase */
"cmp_chars:"
"cmpb %%bl, %%bh;" /* compare characters name[i] and token [i] */
"jne for_next;" /* if not equal, end and compare next array element */
"cmpb $0, %%bl;" /* if end of string */
"je str_equal;" /* strings were equal */
"incq %%rdx;" /* i++*/
"jmp string_cmp;" /* compare next character */
"str_equal:"
"movq (%%rsi), %%rax;" /* load list[index].ID */
"jmp for_end;" /* return */
"for_next:"
"addq $32, %%rsi;" /* advance to next position in structure array */
"loop for_loop;" /* decrement remaining elements in list, repeat if not zero */
"for_end:"
: "=a" (index)
: "m" (list), "m" (token), "m" (count)
);
return index;
}
int main(int argc, char** argv)
{
char *token;
FILE *fptr;
long id = 0;
long sid = 0;
long i = 0;
struct student list[100]; /* array of structure */
if (argc != 4)
{
printf("Usage: %s filename token student_id\n", argv[0]);
return 1;
}
token = argv[2];
sid = atol(argv[3]);
printf("\n");
fptr = fopen((argv[1]), "rtc");
if (fptr == NULL)
printf( "File %s was not opened\n",argv[1] );
else
{
/* Set pointer to beginning of file: */
fseek( fptr, 0L, SEEK_SET );
/* Read data from file: */
while ( fscanf(fptr, "%s", (char*) &list[i].name) != EOF )
{
list[i].ID = i+1001;
printf( "%s ", list[i].name );
i++;
}
printf( "\n\nNumber of names = %ld\n", i );
printf( "Search Token = %s\n", token );
fclose( fptr );
}
printf( "\nStudent Id = %ld; Name = %s.\n\n", sid, (char*)search_by_id((char*)list, i, sid));
id = search_by_name ((char*)list, i, token);
if (id)
printf( "Student Id = %ld; Name = %s\n", id, list[id-(1001)].name );
else
printf( "Student is not found.\n");
return 0;
}