in x86 64 assembly language mostly is already written Objective The objectives of the programming assignment are 1) to gain experience writing larger assembly language programs, 2) to gain further experience with branching operations, and 3) to practice some indexed addressing modes Background The most basic case of string searching involves one (often very long) string, sometimes called the haystack , and one (often very short) string, sometimes called the needle The goal is to find one or more occurrences of the needle within the haystack For example, one might search for needle within Pattern in a haystack, needle in a haystack, needle in a haystacktext needle needle appears after 14 characters from the first character in the pattern Although the text to be search appears more than once, a simple substring search algorithm would indicate only its first appearance in the pattern Your goal is to determine the first occurrence of the text to be searched (specified via standard input) within the following text pattern (provided as a part of the code snippet) The text to be searched can include white spaces and punctuation and may even be a partial string within a word (substring) record row1 row2 db Knight Rider a shadowy flight db into the dangerous world of a db man who does not exist Mich db ael Knight, a young loner on db a crusade to champion the cau db se of the innocent, the innoc db ent, the helpless in a world db of criminals who operate abov db e the law Knight Rider, Keep db riding brave into the night Your assignment for this project is to write an assembly language program that computes the first occurrence of a string (provided via standard input) within text embedded within the code snippet Your program may execute like this textSearch Enter search string K Text you searched for, appears at 0 characters after the first linux3 $ textSearch Enter search string Rider Text you searched for, appears at 7 characters after the first linux3 $ textSearch Enter search string er, Text you searched for, appears at 253 characters after the first 1 linux3 $ textSearch Enter search string ht Text you searched for, appears at 287 characters after the first linux3 $ textSearch Enter search string anger Text you searched for, appears at 39 characters after the first linux3 $ textSearch Enter search string criminals who operate above the law Text you searched for, appears at 206 characters after the first linux3 $ textSearch Enter search string cent Text you searched for, appears at 159 characters after the first d linux3 $ textSearch Enter search string Knight Rider, Text you searched for, appears at 243 characters after the first linux3 $ textSearch Enter search string a crusade Text you searched for, appears at 116 characters after the first linux3 $ textSearch Enter search string random 3456 String not found Implementation Notes A good starting point for your program is the textSearch asm program shown in class It already queries the user for input and prints out digits for a number in the register RAX Your can assume that no more than 100 characters will ever be input to your program The text to be searched can include white spaces and punctuation and may even be a partial string within a word (substring) Although you may modify the embedded text within the provided code snippet, you are required to preserve the text as is when you make your final code submission Your code will be evaluated on test cases that presume the original embedded text is preserved with no modifications Remember, all characters input into the system are ASCII values Refer to an ASCII table when determining how to implement your code Your code must be case sensitive if the input is upper case, then the corresponding output must be upper case if the input is lower case, then the corresponding output must be lower case, as in the following example (also above) linux3 $ textSearch Enter search string Rider Text you searched for, appears at 7 characters after the first If the input string was not found, then your code should print out the following message linux3 $ textSearch Enter search string random 3456 String not found To make things easier, you are also provided a code snippet that prints out the digits of the location found You are allowed to change optimize the provided code if required There are many ways to implement your search routine Although, you may be creative in your implementation, points are awarded, on a correctness basis, where you are supposed to clear all provided test cases You may use indexed addressing instructions and conditional loops to achieve the objective You may also explore efficient techniques for searching substrings such as the KMP Algorithm However, since efficiency is not the goal, you may use a naive string search technique One aspect that you should definitely consider, is that your code should produce results in a few seconds (not minutes, or hours at a stretch ) It may be helpful to write the code to perform the Substring Search in a higher level language of your choosing (C, C , Java, Python, ) This will help you understand the mechanics of your assembly language program This is not required and you should NOT submit this if you choose to do it Source code for text search asm File textSearch asm This program demonstrates the use of an indexed addressing mode to access data within a record Assemble using NASM nasm f elf64 textSearch asm Link with ld ld textSearch o o textSearch define STDIN 0 define STDOUT 1 define SYSCALL EXIT 60 define SYSCALL READ 0 define SYSCALL WRITE 1 define BUFLEN 100 SECTION data Data section msg1 db Enter search string user prompt len1 equ $ msg1 length of message msg2 db 10, Read error , 10 error message len2 equ $ msg2 length of error message msg3a db Text you searched, appears at String found message len3a equ $ msg3a length of message msg3b db characters after the first Remainder of string found message len3b equ $ msg3b length of message msg4 db String not found , 10 string not found message len4 equ $ msg4 length of message endl db 10 Linefeed simulates a text file (record) record row1 db Knight Rider a shadowy flight row2 db into the dangerous world of a db man who does not exist Mich db ael Knight, a young loner on db a crusade to champion the cau db se of the innocent, the innoc db ent, the helpless in a world db of criminals who operate abov db e the law Knight Rider, Keep db riding brave into the night rlen equ $ record rowlen equ row2 row1 SECTION bss uninitialized data section buf resb BUFLEN buffer for read loc resb BUFLEN buffer to store found location string count resb 4 reserve storage for user input bytes SECTION text Code section global start start nop Entry point prompt user for input mov rax, SYSCALL WRITE write function mov rdi, STDOUT Arg1 file descriptor mov rsi, msg1 Arg2 addr of message mov rdx, len1 Arg3 length of message syscall 64 bit system call read user input mov rax, SYSCALL READ read function mov rdi, STDIN Arg1 file descriptor mov rsi, buf Arg2 addr of message mov rdx, BUFLEN Arg3 length of message syscall 64 bit system call error check mov count , rax save length of string read cmp rax, 0 check if any chars read jg read OK 0 chars read OK mov rax, SYSCALL WRITE Or Print Error Message mov rdi, STDOUT Arg1 file descriptor mov rsi, msg2 Arg2 addr of message mov rdx, len2 Arg3 length of message syscall 64 bit system call jmp exit skip over rest read OK Input was accepted, now initialize init Regsiter initializations found If string was found print location Following is a snippet of code for printing out the digits of a number if its more than one digit long mov r10, 1 Keeps track of the number of digits to be printed mov rdi, loc Store the address of location buffer mov rax, 212 Lets assume, that the location found was 212 characters from the first character mov cl, 10 Print out its digits using a loop cmp ax, 9 Is the number larger than a single digit jg digits if so, jump to store the digits routine mov rbx, rax Copy the value into rbx (Used later by a shifting out routine) add bl, '0' Add the ASCII character offset for numbers jmp shOut Shift out routine digits div cl Divide by 10 (212 10 , Quotient (AH) 21, Remainder (AL) 2) On the first iteration of this loop mov bl, ah Store the remainder in bl add bl, '0' Add the ASCII character offset for numbers shl rbx, 8 Shift left the character, so that they can be shifted out in reverse and ax, 0x00FF Clear out the remainder from the result inc r10 R10 keeps track of the number of digits cmp al, 0 See if we have any more digits to convert jnz digits If there are more, keep looping shOut mov rdi , bl move the first digit (now a character) into destination inc rdi update to next character position shr rbx, 8 Shift out the next digit cmp bl, 0 Check to see if we have shifted out all digits jnz shOut More digits Keep looping mov rax, SYSCALL WRITE Print Message mov rdi, STDOUT Arg1 file descriptor mov rsi, msg3a Arg2 addr of message mov rdx, len3a Arg3 length of message syscall 64 bit system call mov rax, SYSCALL WRITE Write out location information mov rdi, STDOUT Arg1 file descriptor mov rsi, loc Arg2 addr of message mov rdx, r10 Arg3 length of message syscall 64 bit system call mov rax, SYSCALL WRITE Print remainder of Message mov rdi, STDOUT Arg1 file descriptor mov rsi, msg3b Arg2 addr of message mov rdx, len3b Arg3 length of message syscall 64 bit system call mov rax, SYSCALL WRITE Write out string mov rdi, STDOUT Arg1 file descriptor mov rsi, endl Arg2 addr of message mov rdx, 1 Arg3 length of message syscall 64 bit system call jmp exit nope String not found message mov rax, SYSCALL WRITE Print Message mov rdi, STDOUT Arg1 file descriptor mov rsi, msg4 Arg2 addr of message mov rdx, len4 Arg3 length of message syscall 64 bit system call exit mov rax, SYSCALL EXIT exit system call id mov rdi, 0 exit to shell syscall

The Answer is in the image, click to view ...

Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Sep 07, 2024

in x86-64 assembly language mostly is already written Objective:- The objectives of the programming assignment are 1) to gain experience writing larger assembly language programs,

in x86-64 assembly language mostly is already written

Objective:- The objectives of the programming assignment are 1) to gain experience writing larger assembly language programs, 2) to gain further experience with branching operations, and 3) to practice some indexed addressing modes

Background;- The most basic case of string searching involves one (often very long) string, sometimes called the "haystack", and one (often very short) string, sometimes called the "needle". The goal is to find one or more occurrences of the "needle" within the "haystack". For example, one might search for "needle" within:

Pattern: in a haystack, needle in a haystack, needle in a haystacktext: needle

needle appears after 14 characters from the first character in the pattern. Although the text to be search appears more than once, a simple substring search

algorithm would indicate only its first appearance in the pattern.

Your goal is to determine the first occurrence of the text to be searched (specified via standard input) within the following text pattern (provided as a part of the code snippet). The text to be searched can include white spaces and punctuation and may even be a partial string within a word (substring).

record: row1: row2:

db "Knight Rider a shadowy flight" db "into the dangerous world of a"

db " man who does not exist. Mich" db "ael Knight, a young loner on "

db "a crusade to champion the cau" db "se of the innocent, the innoc"

db "ent, the helpless in a world " db "of criminals who operate abov"

db "e the law. Knight Rider, Keep"

db " riding brave into the night."

Your assignment for this project is to write an assembly language program that computes the first occurrence of a string (provided via standard input) within text embedded within the code snippet. Your program may execute like this:

 ./textSearch Enter search string: K Text you searched for, appears at 0 characters after the first. [linux3 ~]$ ./textSearch Enter search string: Rider Text you searched for, appears at 7 characters after the first. [@linux3 ~]$ ./textSearch Enter search string: er, Text you searched for, appears at 253 characters after the first. [1@linux3 ~]$ ./textSearch Enter search string: ht. Text you searched for, appears at 287 characters after the first. [@linux3 ~]$ ./textSearch Enter search string: anger Text you searched for, appears at 39 characters after the first. [@linux3 ~]$ ./textSearch Enter search string: criminals who operate above the law Text you searched for, appears at 206 characters after the first. [@linux3 ~]$ ./textSearch Enter search string: cent Text you searched for, appears at 159 characters after the first. [d@linux3 ~]$ ./textSearch Enter search string: Knight Rider, Text you searched for, appears at 243 characters after the first. [@linux3 ~]$ ./textSearch Enter search string: a crusade Text you searched for, appears at 116 characters after the first. [@linux3 ~]$ ./textSearch Enter search string: random@3456 String not found!

Implementation Notes

A good starting point for your program is the textSearch.asm program shown in class. It already queries the user for input and prints out digits for a number in the register RAX.
Your can assume that no more than 100 characters will ever be input to your program. The text to be searched can include white spaces and punctuation and may even be a partial string within a word (substring).
Although you may modify the embedded text within the provided code snippet, you are required to preserve the text as is when you make your final code submission. Your code will be evaluated on test cases that presume the original embedded text is preserved with no modifications.
Remember, all characters input into the system are ASCII values. Refer to an ASCII table when determining how to implement your code.
Your code must be case-sensitive: if the input is upper-case, then the corresponding output must be upper-case; if the input is lower-case, then the corresponding output must be lower-case, as in the following example (also above):
```
 [@linux3 ~]$ ./textSearch Enter search string: Rider Text you searched for, appears at 7 characters after the first. 
```
If the input string was not found, then your code should print out the following message
```
 [@linux3 ~]$ ./textSearch Enter search string: random@3456 String not found! 
```
To make things easier, you are also provided a code snippet that prints out the digits of the location found. You are allowed to change/optimize the provided code if required.
There are many ways to implement your search routine. Although, you may be creative in your implementation, points are awarded, on a correctness basis, where you are supposed to clear all provided test cases. You may use indexed addressing instructions and conditional loops to achieve the objective. You may also explore efficient techniques for searching substrings such as the KMP Algorithm. However, since efficiency is not the goal, you may use a naive string search technique. One aspect that you should definitely consider, is that your code should produce results in a few seconds (not minutes, or hours at a stretch!).
It may be helpful to write the code to perform the Substring Search in a higher-level language of your choosing (C, C++, Java, Python, ...). This will help you understand the mechanics of your assembly language program.This is not required and you should NOT submit this if you choose to do it.

Source code for text search.asm

; File: textSearch.asm ; ; This program demonstrates the use of an indexed addressing mode ; to access data within a record ; ; Assemble using NASM: nasm -f elf64 textSearch.asm ; Link with ld: ld textSearch.o -o textSearch ; %define STDIN 0 %define STDOUT 1 %define SYSCALL_EXIT 60 %define SYSCALL_READ 0 %define SYSCALL_WRITE 1 %define BUFLEN 100 SECTION .data ; Data section msg1: db "Enter search string: " ; user prompt len1: equ $-msg1 ; length of message msg2: db 10, "Read error", 10 ; error message len2: equ $-msg2 ; length of error message msg3a: db "Text you searched, appears at " ; String found message len3a: equ $-msg3a ; length of message msg3b: db " characters after the first." ; Remainder of string found message len3b: equ $-msg3b ; length of message msg4: db "String not found!", 10 ; string not found message len4: equ $-msg4 ; length of message endl: db 10 ; Linefeed ; simulates a text file (record) record: row1: db "Knight Rider a shadowy flight" row2: db "into the dangerous world of a" db " man who does not exist. Mich" db "ael Knight, a young loner on " db "a crusade to champion the cau" db "se of the innocent, the innoc" db "ent, the helpless in a world " db "of criminals who operate abov" db "e the law. Knight Rider, Keep" db " riding brave into the night." rlen: equ $-record rowlen: equ row2 - row1 SECTION .bss ; uninitialized data section buf: resb BUFLEN ; buffer for read loc: resb BUFLEN ; buffer to store found location string count: resb 4 ; reserve storage for user input bytes SECTION .text ; Code section. global _start _start: nop ; Entry point. ; prompt user for input ; mov rax, SYSCALL_WRITE ; write function mov rdi, STDOUT ; Arg1: file descriptor mov rsi, msg1 ; Arg2: addr of message mov rdx, len1 ; Arg3: length of message syscall ; 64-bit system call ; read user input ; mov rax, SYSCALL_READ ; read function mov rdi, STDIN ; Arg1: file descriptor mov rsi, buf ; Arg2: addr of message mov rdx, BUFLEN ; Arg3: length of message syscall ; 64-bit system call ; error check ; mov [count], rax ; save length of string read cmp rax, 0 ; check if any chars read jg read_OK ; >0 chars read = OK mov rax, SYSCALL_WRITE ; Or Print Error Message mov rdi, STDOUT ; Arg1: file descriptor mov rsi, msg2 ; Arg2: addr of message mov rdx, len2 ; Arg3: length of message syscall ; 64-bit system call jmp exit ; skip over rest read_OK: ; Input was accepted, now initialize init: ; Regsiter initializations found: ; If string was found print location ; Following is a snippet of code for ; printing out the digits of a number if its more ; than one digit long mov r10, 1 ; Keeps track of the number of digits to be printed mov rdi, loc ; Store the address of location buffer mov rax, 212 ; Lets assume, that the location found ; was 212 characters from the first character mov cl, 10 ; Print out its digits using a loop cmp ax, 9 ; Is the number larger than a single digit? jg digits ; if so, jump to store the digits routine mov rbx, rax ; Copy the value into rbx (Used later by a shifting out routine) add bl, '0' ; Add the ASCII character offset for numbers jmp shOut ; Shift out routine digits: div cl ; Divide by 10 (212/10 , Quotient (AH) - 21, Remainder (AL) - 2) ; ... On the first iteration of this loop mov bl, ah ; Store the remainder in bl add bl, '0' ; Add the ASCII character offset for numbers shl rbx, 8 ; Shift left the character, so that they can be shifted out in reverse and ax, 0x00FF ; Clear out the remainder from the result inc r10 ; R10 keeps track of the number of digits cmp al, 0 ; See if we have any more digits to convert jnz digits ; If there are more, keep looping shOut: mov [rdi], bl ; move the first digit (now a character) into destination inc rdi ; update to next character position shr rbx, 8 ; Shift out the next digit cmp bl, 0 ; Check to see if we have shifted out all digits jnz shOut ; More digits? Keep looping mov rax, SYSCALL_WRITE ; Print Message mov rdi, STDOUT ; Arg1: file descriptor mov rsi, msg3a ; Arg2: addr of message mov rdx, len3a ; Arg3: length of message syscall ; 64-bit system call mov rax, SYSCALL_WRITE ; Write out location information mov rdi, STDOUT ; Arg1: file descriptor mov rsi, loc ; Arg2: addr of message mov rdx, r10 ; Arg3: length of message syscall ; 64-bit system call mov rax, SYSCALL_WRITE ; Print remainder of Message mov rdi, STDOUT ; Arg1: file descriptor mov rsi, msg3b ; Arg2: addr of message mov rdx, len3b ; Arg3: length of message syscall ; 64-bit system call mov rax, SYSCALL_WRITE ; Write out string mov rdi, STDOUT ; Arg1: file descriptor mov rsi, endl ; Arg2: addr of message mov rdx, 1 ; Arg3: length of message syscall ; 64-bit system call jmp exit nope: ; String not found message ; mov rax, SYSCALL_WRITE ; Print Message mov rdi, STDOUT ; Arg1: file descriptor mov rsi, msg4 ; Arg2: addr of message mov rdx, len4 ; Arg3: length of message syscall ; 64-bit system call exit: mov rax, SYSCALL_EXIT ; exit system call id mov rdi, 0 ; exit to shell syscall