Program 5: Removing Duplicates

Program due: Friday, April 25th, 8 p.m.

For this assignment, you will write two procedures: rmDup and printPartial.

The rmDup procedure will take one argument: the address of the first character of a string of ASCII characters. The string may contain repeated characters. rmDup will create a new string in a local buffer that is the original string without the repeated characters. For example, if the original string is:

While I nodded, nearly napping, suddenly there came a tapping,

then rmDup will create the following string:

While I noded, nearly naping, sudenly there came a taping,

The printPartial procedure will take two arguments: the address of the first character of an array of ASCII characters, and the number of characters to be printed. Note that the array of ASCII characters is may not contain a nul character at the end.

The main purpose of printPartial will be its use in debugging rmDup. Each time that rmDup decides to add a character from the original string to the new string it is creating, rmDup will call printPartial to print the current contents of the new string.

We will provide main and printStrings. main will call rmDup on each string of a set of strings. When rmDup has finished processing each string, it will call printStrings. printStrings takes two arguments: the address of the first character of the original string, and the address of the first character of the new string. printStrings does assume that both strings are nul terminated; thus, rmDup will need to add a nul character to the end of the new string it has created.

Here is a sample test case that calls rmDup three times:

.data

mainNumStrings:

.word 3

mainStrings:

.word mainStr1

.word mainStr2

.word mainStr3

mainStr1:

.asciiz "While I nodded, nearly napping, suddenly there came a tapping,"

mainStr2:

.asciiz "Duuuupppliiicaaatteeeeed IIIIIIIItttteemms 9998888"

mainStr3:

.asciiz "1987777272722222(#*@^^^^@^@@@@@***@(((((;;;;;{{{{{}}}}}"

mainNewline:

.asciiz "\n"

.text

main:

# Function prologue -- even main has one

subu $sp, $sp, 24 # allocate stack space -- default of 24 here

sw $fp, 0($sp) # save caller's frame pointer

sw $ra, 4($sp) # save return address

addiu $fp, $sp, 24 # setup main's frame pointer

# for (i = 0; i < mainNumStrings; i++ )

# load address of string into $a0

# call rmDup

# $s0 = i

addi $s0, $zero, 0

# $s1 = mainNumStrings

la $t0, mainNumStrings

lw $s1, 0($t0)

# $s2 = address of mainStrings

la $s2, mainStrings

MainLoopBegin:

slt $t0, $s0, $s1 # $t0 = $s0 < $s1

beq $t0, $zero, MainLoopEnd

lw $a0, 0($s2) # $a0 = addr of a string

jal rmDup

la $a0, mainNewline

li $v0, 4

syscall

addi $s0, $s0, 1 # i++

addi $s2, $s2, 4 # $s2 += 4, to get addr of next string

j MainLoopBegin

MainLoopEnd:

MainDone:

# Epilogue for main -- restore stack & frame pointers and return

lw $ra, 4($sp) # get return address from stack

lw $fp, 0($sp) # restore the caller's frame pointer

addiu $sp, $sp, 24 # restore the caller's stack pointer

jr $ra # return to caller

.data

printStringsOrig:

.asciiz "Original string:\n"

printStringsModified:

.asciiz "Modified string:\n"

printStringsNewline:

.asciiz "\n"

.text

printStrings:

# Function prologue

subu $sp, $sp, 24 # allocate stack space -- default of 24 here

sw $fp, 0($sp) # save caller's frame pointer

sw $ra, 4($sp) # save return address

sw $a0, 8($sp) # preserve $a0

sw $a1, 12($sp) # preserve $a1

addiu $fp, $sp, 24 # setup printStrings's frame pointer

# print the original string

la $a0, printStringsOrig

li $v0, 4

syscall

lw $a0, 8($sp)

li $v0, 4

syscall

la $a0, printStringsNewline

li $v0, 4

syscall

# print the modified string

la $a0, printStringsModified

li $v0, 4

syscall

addi $a0, $a1, 0

li $v0, 4

syscall

la $a0, printStringsNewline

li $v0, 4

syscall

# Epilogue for printString -- restore stack & frame pointers and return

lw $fp, 0($sp) # restore the caller's frame pointer

lw $ra, 4($sp) # get return address from stack

lw $a0, 8($sp) # restore $a0

lw $a1, 12($sp) # restore $a1

addiu $sp, $sp, 24 # restore the caller's stack pointer

jr $ra # return to caller

Here is the correct output from this test case:

Whi

Whil

While

While I

While I n

While I no

While I nod

While I node

While I noded

While I noded,

While I noded, n

While I noded, ne

While I noded, nea

While I noded, near

While I noded, nearl

While I noded, nearly

While I noded, nearly n

While I noded, nearly na

While I noded, nearly nap

While I noded, nearly napi

While I noded, nearly napin

While I noded, nearly naping

While I noded, nearly naping,

While I noded, nearly naping, s

While I noded, nearly naping, su

While I noded, nearly naping, sud

While I noded, nearly naping, sude

While I noded, nearly naping, suden

While I noded, nearly naping, sudenl

While I noded, nearly naping, sudenly

While I noded, nearly naping, sudenly t

While I noded, nearly naping, sudenly th

While I noded, nearly naping, sudenly the

While I noded, nearly naping, sudenly ther

While I noded, nearly naping, sudenly there

While I noded, nearly naping, sudenly there c

While I noded, nearly naping, sudenly there ca

While I noded, nearly naping, sudenly there cam

While I noded, nearly naping, sudenly there came

While I noded, nearly naping, sudenly there came a

While I noded, nearly naping, sudenly there came a t

While I noded, nearly naping, sudenly there came a ta

While I noded, nearly naping, sudenly there came a tap

While I noded, nearly naping, sudenly there came a tapi

While I noded, nearly naping, sudenly there came a tapin

While I noded, nearly naping, sudenly there came a taping

While I noded, nearly naping, sudenly there came a taping,

Original string:

While I nodded, nearly napping, suddenly there came a tapping,

Modified string:

While I noded, nearly naping, sudenly there came a taping,

Dup

Dupl

Dupli

Duplic

Duplica

Duplicat

Duplicate

Duplicated

Duplicated I

Duplicated It

Duplicated Ite

Duplicated Item

Duplicated Items

Duplicated Items 9

Duplicated Items 98

Original string:

Duuuupppliiicaaatteeeeed IIIIIIIItttteemms 9998888

Modified string:

Duplicated Items 98

198

1987

19872

198727

1987272

19872727

198727272

198727272(

198727272(#

198727272(#*

198727272(#*@

198727272(#*@^

198727272(#*@^@

198727272(#*@^@^

198727272(#*@^@^@

198727272(#*@^@^@*

198727272(#*@^@^@*@

198727272(#*@^@^@*@(

198727272(#*@^@^@*@(;

198727272(#*@^@^@*@(;{

198727272(#*@^@^@*@(;{}

Original string:

1987777272722222(#*@^^^^@^@@@@@***@(((((;;;;;{{{{{}}}}}

Modified string:

198727272(#*@^@^@*@(;{}

Input:

We will supply main and printStrings. main will call your rmDup function for each of the strings.

Output:

Your rmDup procedure create a modified string. Where the original string had a run of identical characters, only one instance of the character will appear in the modified string.

rmDup will need a place to put the modified string. Treat the modified string as a local variable and store it on rmDup’s stack. The stack for rmDup then will have space for the $a, $fp and $ra registers on top, space for $s registers that need to be preserved, and space for the modified string (as shown on the drawing). The space shown for the $s registers may not be present; it depends on whether rmDup does or does not use any $s registers.

You can assume that the original string will not contain more than 80 characters, including the nul character at the end of the string.

Label naming conventions:

Labels in MIPS programs are global. This presents a problem when you want to use a label that is already in use elsewhere in the program. To avoid conflicts in labels between your code and the test cases, we will adopt the following practice:

Labels will have the name of the procedure or function at the start of the label. For example, if I want to use the label LoopBegin: in main, then I will name the label mainLoopBegin:. If you also want to use the label LoopBegin: in your rmDup procedure, you will name it rmDupLoopBegin:.

We will check that you are following these labeling conventions when we grade your program!

What will be provided:

Each test case will contain main and printStrings.

Your program must have the comment:

# Your code goes below this line

Everything that you provide must go below this required comment line. This includes all comments that you put in, all .text code segments that you add, and any .data segments that you might need.

We will provide some sample files for you to copy. They will be available to copy on the Unix machines (lectura and the Fedora machines, fd01 to fd08). They will also be on the Windows machines. On the Windows systems, look in the shared Rotis drive: Rotis->csc252->shared->prog5. On the Unix machines, look in the directory: ~cs252/spring08/prog5. In both cases, the files will be named: test01.s, test02.s, etc. Secure ftp can also be used to access the test cases on lectura from your home system. Please check with us if you have problems accessing these test cases.

The required comment line:

# Your code goes below this line

must be present in the prog5.s file that you turnin! The prog5.s that you turnin may contain one of the test cases above the required comment, or the required comment can be the very first line (no test case data above it). Either is acceptable.

Turnin:

Note: We are asking for submission of programs via D2L only.

•Name your program: prog5.s
•Using a web browser, go to: http://d2l.arizona.edu/
•Login using the “UA NetID Login” (upper-left corner of the web page).
•You should now be at “My Home” on D2L. At the center bottom of the screen, under the heading “My Academic Courses”, you should find “C SC252 SP08 001-002H Homer” listed under 2008 Spring. Click on this link.
•You will now be at the CSc 252 page for Spring 08.
•There is a row of links just underneath the Wildcat. In this row, you will find the link “Dropbox”. Click on this link.
•You will be at a page that shows three Dropbox Folders: Program5, Program5-Late, Program5-Regrade. Only one of these will be active. The Program5 folder is for on-time submissions. The Program5-Late folder will be available for late submissions. The Program5-Regrade folder is used for requesting a re-grade of the program after the grades have been returned. Click on “Program5”. If you are doing a late turnin, click on “Program5-Late”.
•You should now be at the page: “Submit Files - Program5”. Click on the “Add a File” button. A pop-up window will appear. Click on the “Choose File” button. Use the file browser that will appear to select your prog5.s file. Click on the “Upload” button in the lower-right corner of the pop-up window.
•You are now back at the “Submit Files - Program5”. Click on “Upload” in the lower-right of this window. You should now be at the “File Upload Results” page, and should see the message File Submission Successful.
•You can repeat this process as often as necessary. Each submission will be time-stamped. When we grade programs, we will grade only the most recent submission.