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:
