Word Search Program using Assembly Language Homework Solution

Word Search Program in assembly

This is the final assignment in the assembly portion of the CS1520 course. The assignment consists of a program that searches a text for occurrences of a given string and reports the lines in the text where the string was found. The detailed specification of the program will be described below. Introduction

Suppose you have the following (admittedly silly) text, stored in a file:

roses are red violets are blue

blue is the sky (blue) blue

so blue red blue

Now you want to find all the lines in the file where the word “blue” occurs. You then set the searching string in your program to “blue”, and run the program on the file; your program should then print the following output to the screen:

2

violets are blue 3

blue is the sky (blue) 4

blue

6

so blue 8

blue

total num of lines: 8

num of matches: 5

The details of how this should work — including how to use the contents of a file as inputs to your program, and how exactly to store the string we are searching for are described in more detail in the Specification section below. For now, focus on the output listed above. The number of each line that contains the string is listed, followed by a copy of that line. Then at the end, the total number of lines in the file is printed, as well as the number of lines where there was a match. Notice that the word “blue” appears in line 3 twice, but that line is printed only once in the output- each line where a match was found should only be counted once, even if there are multiple matches on that line.

Specification

Now we give a detailed specification of the program you must implement in this assignment. Please make your program works exactly as described here.

Name your program wsearch. The string you are searching for should be stored in the .data section of your program, under the label search_string. For example:

. . . .

.data

search_string: .asciz "blue"

. . . .

Of course, your program is required to work for any string stored in search_string, not only for the particular string in the example above.

To write your assembly language assignment program reads the input from the terminal — just like you have been doing in the previous practicals. In order to read the contents of a file using the same system calls that we used to read the input from the terminal, we exploit a feature of the Unix operating system called “pipes”. If you have the file some.txt with some text, you can send (“pipe”) the text to your program using the following command in the codio terminal:

cat some.txt | qemu-arm -L /usr/arm-linux-gnueabi/ wsearch

This command behaves as if you executed the wsearch program and then manually typed the text in the entire file, character by character. So, you can use the same routines you created in previous practicals to read file contents.

The number of each line that contains the searched-for string is listed, and then the corresponding line is printed. After all matching lines are reported, the program should report the total number of lines in the file, and then the number of lines where

there was a match. Each matching line should only be reported once, even if there are multiple matches on that line. Notice that you are only looking to find the given string in the text: so “blue”, “blues” and “bluer” all match the search string “blue”.

But “Blue” does not match: the search is case-sensitive.

Furthermore, the search string can be comprised of any characters except the newline: so the string "ab-1&" is a valid search string.

Starting point:

Use this code as your starting point:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @ ( from practical 6) @ Print an integer on the screen , followed @ by a newline . ( uses C library function ) @ @ arguments : r1 : integer to be printed @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ .global printf print_num : push {r0-r3 , lr } ldr r0 , =fmt bl printf pop {r0-r3 , lr } bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @ ( from practical 6) @ Read a string from the terminal . @ ( only the first 1000000 characters are read ) @ @ arguments : r1 : address of string used to @ store result @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ read_str : push {r0-r7 , lr} @ read a string from the terminal mov r0 , #0 @ 0 = std input ( terminal ) ldr r2 , =#1000000 @ max num of bytes to read mov r7 , #3 @ 3 = " read " system call svc #0 @ make the system call pop {r0-r7 , lr} bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ Compute the length of a zero terminated @ string . @ @ arguments : r1 - string address @ results : r0 - length of string str_length: push {r1 , r2 , lr} mov r0 , #0 str_length_loop : ldrb r2 , [ r1 ] , #1 cmp r2 , #0 beq str_length_end add r0 , #1 b str_length_loop str_length_end: pop {r1 , r2 , lr} bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ Print the first n characters of a string @ @ arguments : r1 - string address @ r2 - num of characters @ returns : ( nothing ) print_str_n : push {r0-r7 , lr} mov r0 , #1 @ r0 = output device = std output @ r1 = string address @ r2 = num of bytes mov r7 , #4 @ r7 = sys call code (4 = "write ") svc #0 @ print ! pop {r0-r7 , lr} bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ Print a zero terminated string @ @ arguments : r1 - string address @ returns : ( nothing ) print_str : push {r0-r2 , lr} bl str_length mov r2 , r0 bl print_str_n pop {r0-r2 , lr} bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ Print a newline character @ @ arguments : ( nothing ) @ returns : ( nothing ) print_newline: push {r1 , lr} ldr r1 , =newline bl print_str pop {r1 , lr} bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ This function returns 1 if the string in r1 @ is a prefix of the string in r2 @ @ arguments : r1 - prefix string address @ r2 - string address @ returns : r0 - 1 if r1 is a prefix of r2 @ 0 otherwise starts_with: @@ YOUR CODE GOES HERE @@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ Return the address of the end @ of the currentline , or of the end of @ the text @ @ arguments : r1 - address of current location @ in string @ returns : r0 - address of the next newline @ character , or of the end of the @ string find_eol : @@ YOUR CODE GOES HERE @@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ Print the string from the location r1 to the @ end of the line @ @ arguments : r1 - string address @ returns : ( nothing ) print_line: @@ YOUR CODE GOES HERE @@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ .global main main: ldr r1 , =txt bl read_str @ read the text from the terminal @ and store it in the txt string ldr r1 , =search_string ldr r2 , =txt mov r3 , #1 @ r3 = line number mov r4 , r2 @ r4 = pos of start of curr line mov r6 , #1 @ r6 = total num of lines in file @ ( the file starts at line 1) mov r7 , #0 @ r7 = num of lines that match loop : @@ @@ @@ YOUR CODE GOES HERE @@ @@ @@ mov r7 , #1 svc #0 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ .data search_string: .asciz "blue" newline: .asciz "\n" num_of_lines_str: .asciz " total num of lines : " num_of_matches_str: .asciz "num of matches : " fmt: .asciz "%d\n" txt: .space 1000000 @ input text as a @ single string .end

Solution:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @ ( from practical 6) @ Print an integer on the screen , followed @ by a newline . ( uses C library function ) @ @ arguments : r1 : integer to be printed @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ .global printf print_num : push {r0-r3 , lr } ldr r0 , =fmt bl printf pop {r0-r3 , lr } bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @ ( from practical 6) @ Read a string from the terminal . @ ( only the first 1000000 characters are read ) @ @ arguments : r1 : address of string used to @ store result @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ read_str : push {r0-r7 , lr} @ read a string from the terminal mov r0 , #0 @ 0 = std input ( terminal ) ldr r2 , =#1000000 @ max num of bytes to read mov r7 , #3 @ 3 = " read " system call svc #0 @ make the system call pop {r0-r7 , lr} bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ Compute the length of a zero terminated @ string . @ @ arguments : r1 - string address @ results : r0 - length of string @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ str_length: push {r1 , r2 , lr} mov r0 , #0 str_length_loop : ldrb r2 , [ r1 ] , #1 cmp r2 , #0 beq str_length_end add r0 , #1 b str_length_loop str_length_end: pop {r1 , r2 , lr} bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ Print the first n characters of a string @ @ arguments : r1 - string address @ r2 - num of characters @ returns : ( nothing ) @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ print_str_n : push {r0-r7 , lr} mov r0 , #1 @ r0 = output device = std output @ r1 = string address @ r2 = num of bytes mov r7 , #4 @ r7 = sys call code (4 = "write ") svc #0 @ print ! pop {r0-r7 , lr} bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ Print a zero terminated string @ @ arguments : r1 - string address @ returns : ( nothing ) @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ print_str : push {r0-r2 , lr} bl str_length mov r2 , r0 bl print_str_n pop {r0-r2 , lr} bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ Print a newline character @ @ arguments : ( nothing ) @ returns : ( nothing ) @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ print_newline: push {r1 , lr} ldr r1 , =newline bl print_str pop {r1 , lr} bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ This function returns 1 if the string in r1 @ is a prefix of the string in r2 @ @ arguments : r1 - prefix string address @ r2 - string address @ returns : r0 - 1 if r1 is a prefix of r2 @ 0 otherwise @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ starts_with: push {r1-r4 , lr} mov r0, #1 @ assume is prefix sw_loop: ldrb r4, [r1],#1 @ load char from first string ldrb r5, [r2],#1 @ load char from second string cmp r4,#0 @ if we reached end of first string beq sw_end @ it's prefix cmp r4, r5 @ else, compare characters beq sw_loop @ if equal, repeat loop mov r0,#0 @ return 0 to indicate is not a prefix sw_end: pop {r1-r4 , lr} bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ Return the address of the end @ of the currentline , or of the end of @ the text @ @ arguments : r1 - address of current location @ in string @ returns : r0 - address of the next newline @ character , or of the end of the @ string @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ find_eol : push {r1-r2, lr} mov r0, r1 @ load string address fe_loop: ldrb r2, [r0] @ load char from first string cmp r2,#0 @ if we reached end of string beq fe_end @ return cmp r2,#10 @ else, see if it's a newline beq fe_end @ return add r0, r0, #1 @ increment pointer b fe_loop fe_end: pop {r1-r2, lr} bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ Print the string from the location r1 to the @ end of the line @ @ arguments : r1 - string address @ returns : ( nothing ) @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ print_line: push {r1-r2, lr} bl find_eol @ find the newline or end of string sub r2, r0, r1 @ calculate string length bl print_str_n @ print the string pop {r1-r2, lr} bx lr @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ .global main main: ldr r1 , =txt bl read_str @ read the text from the terminal @ and store it in the txt string ldr r1 , =search_string ldr r2 , =txt mov r3 , #1 @ r3 = line number mov r4 , r2 @ r4 = pos of start of curr line mov r6 , #1 @ r6 = total num of lines in file @ ( the file starts at line 1) mov r7 , #0 @ r7 = num of lines that match loop: mov r8, r2 @ save start of line in r8 mov r1, r2 bl find_eol @ find end of file line mov r9, r0 @ save end of line in r9 ldr r1, =search_string line_loop: bl starts_with @ check if string starts with given text cmp r0,#0 @ check return value beq next_char @ if not, skip to next character add r7, r7, #1 @ else, increment matching lines mov r0,r1 @ save pointer mov r1, r6 @ load line number bl print_num @ print the number mov r1, r8 @ load current line pointer bl print_line @ print the line bl print_newline @ print newline mov r1,r0 @ restore pointer b next_line @ skip to next line next_char: add r2, r2, #1 @ increment position in file line cmp r2,r9 @ if we haven't reached the end of line blt line_loop @ repeat for next char in line next_line: mov r2, r9 @ point to end of line character ldr r0,[r2] @ load character from buffer and increment position cmp r0,#0 @ see if we reached the end of buffer beq end_loop @ if so, end search add r6, r6, #1 @ increment line number add r2, r2, #1 @ increment position in text b loop @ search next line end_loop: bl print_newline @ print newline ldr r1, =num_of_lines_str @ load address of number of lines message bl print_str @ print the string mov r1, r6 @ load number of lines bl print_num @ print number ldr r1, =num_of_matches_str @ load address of number of matches message bl print_str @ print the string mov r1, r7 @ load number of matches bl print_num @ print number mov r7 , #1 svc #0 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ .data search_string: .asciz "blue" newline: .asciz "\n" num_of_lines_str: .asciz " total num of lines: " num_of_matches_str: .asciz "num of matches: " fmt: .asciz "%d\n" txt: .space 1000000 @ input text as a @ single string .end

Screenshot: