1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

MIPS Assembly loop help

  1. Apr 16, 2010 #1
    1. The problem statement, all variables and given/known data
    The goal here is to write some MIPS functions to solve a common technical interview
    question: how can you reverse the order of the words in a string? For example, reversing
    the words in the string I Love Lucy would result in Lucy Love I.
    A string is just an array of bytes, with each byte representing one character. The last byte
    of the array is always 0, to indicate the end of the string. Also, a space is represented by
    the value 32.

    First write a function rev, which simply reverses bytes in an array. The arguments
    passed in $a0 and $a1 are the starting address and the number of bytes to reverse.

    Using the rev function, you should now be able to write revwords to reverse the
    order of the words within a string.

    You can implement revwords according to the following basic algorithm.
    1. Call rev to completely reverse the original string. For example, I Love Lucy becomes
    ycuLevoLI. Remember that strings are terminated by a 0 byte.
    2. Then use rev to reverse each word in the new string—ycuLevoLI becomes Lucy Love I.
    You can assume that “words” are separated by a space character, with the byte value 32.


    3. The attempt at a solution

    revwords isn't a function in my attempt, i put it in main for now until i get it working. I created the rev function and tested it and it works for a string. Then i went on to create the other one and thats where i'm having issues. It goes through the words and everything but the output i get is LucyLove_I_ whrere _ are spaces. I've tried to fix it where the space is still in the correct location but I cannot figure it out. The code is posted below, if anyone has any suggestions it would really help, I've spent hours trying to fix this little bug and i've lost hope.

    .data

    string: .asciiz "I Love Lucy"
    endl: .asciiz "\n"
    space: .asciiz " "

    .text
    .globl main

    rev:

    #la $s0, string
    #addi $a1, $0, 7

    add $t2, $0, $0 # set the counter variable to 0
    srl $t0, $a1, 1 # divide the number of characters by 2
    add $t1, $0, $a1 # put the number of characters into t1
    addi $t1, $t1, -1 # subtract 1 from the number of characters
    add $t1, $a0, $t1 # add to the beginning address to get to the end address

    loop:
    lb $t6, 0($a0) # load the byte into t6 (left half)
    lb $t7, 0($t1) # load the byte into $t7 (right half)
    sb $t6, 0($t1) # store t6 at position t1, basically swap
    sb $t7, 0($a0) # store t7 at position a0, swapping
    addi $a0, $a0, 1 # get the address of the next pixel by adding 1
    addi $t1, $t1, -1 # get the address of the previous pixel from end by adding -1
    addi $t2,$t2, 1 # increment the counter by 1
    bne $t0, $t2, loop # while the counter is not equal to half the number of characters loop

    jr $ra # jump back to where the function was called


    main:

    la $a0, string # load the address of the string into a0

    addi $sp, $sp, -12 # make space on the stack for a0
    sw $a0, 0($sp) # store a0
    sw $ra, 4($sp) # store ra

    addi $a1, $0, 11 # 11 = total number of characters
    jal rev # call rev with whole string

    la $a0, string # print the string and an end line
    li $v0, 4
    syscall
    la $a0, endl
    syscall

    lw $a0, 0($sp) # load the string back into a0, since rev changed the variable

    addi $t3, $0, 32 # t3 holds the value for a space, 32
    add $s0, $a0, $0 # s0 is a0

    outerLoop:
    add $a1, $0, $0 # set the num of characters counter to 0
    add $a0, $s0, $0 # set a0 to s0

    innerLoop:
    addi $a0, $a0, 1 # add 1 to the current address
    addi $a1, $a1, 1 # add 1 to the counter
    lb $t8, 0($a0) # load the byte at a0
    beq $t8, $0, after # if it is the end jump to after
    bne $t8, $t3, innerLoop # if there is not a space loop again


    after:
    add $s0, $a0, $0 # add a0 to s0 for storage
    sub $a0, $a0, $a1 # subtract a1 from a0 to get to the beginning of the word
    jal rev

    add $a0, $s0, $0 # restore a0 after function call

    lb $t8, 0($a0) # load the byte into t0
    bne $t8, $0, outerLoop # if its not the end loop again






    la $a0, string
    li $v0, 4
    syscall
     
  2. jcsd
  3. Apr 17, 2010 #2

    Mark44

    Staff: Mentor

    I put your code inside [ code] [ /code] tags (w/o leading space).
    What I would do is find out why, when the string is reversed, the spaces are in the wrong place. After being reversed, the string should be ycuL_evoL_I(null). Note that you don't want to reverse the position of the null character - it should still be at the end.

    If you're getting LucyLove_I_, something is wrong. Are you getting this on the first pass, where you reverse all the characters? Or is it happening on the second pass, where you reverse the characters in each word?
     
  4. Apr 17, 2010 #3
    I have it printing after the first pass and i get ycuL_evoL_I which is why i'm lost. It seems to reverse it right, I think there's something wrong with my second loop that sends it each piece of the string. And thank you for putting it in those tags, i'll be sure to do that next time.
     
  5. Apr 17, 2010 #4

    Mark44

    Staff: Mentor

    I don't know the MIPS instruction set, so I can't help you much with the details of the code.

    I would suggest trying your code with a simpler string consisting of only two words. The first part of your code should still reverse the whole string, and maybe having just one space in the string will help you figure out why the word reversal part isn't working correctly.

    One comment on your code is that you are commenting nearly all the lines of code, which is a good thing. Assembly code is arcane enough that there should be lots of comments. An improvement you could make to your comments is to say what's happening rather than restate what the code is doing. In addition to comments on individual lines, it's useful to have a comment for a block of code, saying what that block is doing. E.g., in the loop (shown below) goes through the string swapping pairs of characters at a time until it reaches the middle of the string.

    Code (Text):

      add $t2, $0, $0   # set the counter variable to 0
      srl $t0, $a1, 1     # divide the number of characters by 2
      add $t1, $0, $a1  # put the number of characters into t1
      addi $t1, $t1, -1 # subtract 1 from the number of characters
      add $t1, $a0, $t1 # add to the beginning address to get to the end address

    loop:
      lb $t6, 0($a0)    # load the byte into t6 (left half)
      lb $t7, 0($t1)    # load the byte into $t7 (right half)
      sb $t6, 0($t1)    # store t6 at position t1, basically swap
      sb $t7, 0($a0)    # store t7 at position a0, swapping
      addi $a0, $a0, 1  # get the address of the next pixel by adding 1
      addi $t1, $t1, -1     # get the address of the previous pixel from end by adding -1
     
    The first two lines of the loop have comments that are not as informative as they could be. For example, you are using t6 to hold a character from the left half of the string, and t7 to hold the corresponding character from the right half of the string. If the string is abcdef, the first time through the loop t6 holds a and t7 holds f. The two characters are swapped, yielding the string fbcdea. Subsequent passes through the loop store the nth character and the len - nth character and swap them, so that you eventually end up with fedcba.

    The last two comments are very misleading, talking about pixels rather than characters in the string.

    Several lines have comments that merely restate the obvious without saying why they are doing it.
    Code (Text):

      add $s0, $a0, $0  # s0 is a0

      add $s0, $a0, $0  # s0 is a0
     
    Again, it's good that you are providing profuse comments, but what does a0 + 0 represent, and why are you storing it in s0? That would be very helpful information.

    Finally, what is your algorithm for taking a string that has been reversed (such as ycuL_evoL_I) and reversing the words in it. It seems to me that you would want to find out where the spaces are located, and call rev on the first substring (ycuL), skip over the space, call rev on the 2nd substring (evoL), skip over the space, and call rev on the 3rd substring (I). I can't follow your code and comments will enough to see what you are doing in outerloop and innerloop.
     
  6. Apr 19, 2010 #5
    Thank you for all the tips. Sorry about the comments, I had them just so that I knew what was what, I usually change them before submitting any code. I really should've made it more clear. I went back and re wrote the function 2 days later and now it works fine.
     
  7. Apr 19, 2010 #6

    Mark44

    Staff: Mentor

    Good. I hope my tips were helpful.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: MIPS Assembly loop help
  1. MIPS help (Replies: 1)

Loading...