Palindrome Generation in MIPS

user_9458753 0
Viewed 212

I need help to write a program that generates palindrome.I managed to make reverse the string but I couldn't combine original string and reverse string together. When I write abc i need to get abccba or when I write hello I need to get helloolleh. Now I only get cba or olleh. Can someone help me with this problem?

.data
msg1: .asciiz "Enter the length of your input: "
msg2: .asciiz "Enter your input: "
msg3: .asciiz "Output of the program is: "

output: .space 256 # will store the output palindrome

.text
la $a0,msg1
li $v0,4
syscall

li $v0,5
syscall
move $s1,$v0 # $s1 has the length of the string



la $a0,msg2
li $v0,4
syscall


li $a1,1024
li $v0,8
syscall
move $s0,$a0 # $s0 has the starting address of the string

#
# YOUR CODE GOES HERE(You can use additional labels at the end)
#


move $a3,$s0
move $a1,$s1




add $a3,$a3,$a1
la $a2, output($zero)
jal reverse 



la $a0,msg3
li $v0,4
syscall




la $a0,output($zero)
li $v0,4
syscall

li $v0,10
syscall


reverse:
    # $a0 - address of string to reverse
    # a1 - length of the string
    # a2 - address of string where to store the reverse
    addi $sp, $sp, -4
    sw $ra, 0($sp)
    bltz $a1, reverse_end
    lb $t0, 0($a3)
    subi $a1, $a1, 1
    subi $a3, $a3, 1
    sb $t0, 0($a2)
    addi $a2, $a2, 1
    jal reverse
reverse_end:
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

Edit:Also this is the C++ implementation of palindrome generation.

C++ Implementation of the Recursive Algorithm for Palindrome Generation 

#include <iostream>
#include <string>

using namespace std;

string palindrom(string input, int rem_length)
{

  if(rem_length!=0)
  {
    input=input.substr(0,1)+palindrom(input.substr(1,input.length()-1), \\
                                      rem_length-1)+input.substr(0,1);
  }
  return input;
}

int main()
{
  string input;
  cin >> input;

  input = palindrom(input, input.length());

  cout << input<< endl;

  system("pause");

  return 0;
}
mips32 mips assembly
1 Answers

It seems you need just to copy the input string first to the output string and when you pass the output array to the reverse function you need to advance the pointer by the input string length (passing output + strlen(input)) so the reversed string will be written right next to it.

Also I think you should use a buffer for the input. Also take care of the '\n' char at the end of the input string since it will be there.

With these in mind I changed you code to this

.data
msg1: .asciiz "Enter the length of your input: "
msg2: .asciiz "Enter your input: "
msg3: .asciiz "Output of the program is: "

input: .space 128
output: .space 256 # will store the output palindrome

.text
la $a0,msg1
li $v0,4
syscall

li $v0,5
syscall
move $s1,$v0 # $s1 has the length of the string

la $a0,msg2
li $v0,4
syscall

move $a1, $1
la $a0, input
li $v0,8
syscall
move $s0,$a0 # $s0 has the starting address of the string

#
# YOUR CODE GOES HERE(You can use additional labels at the end)
#
move $a3,$s0 # a3 = (char *)input
move $a1,$s1 # a1 = strlen(input)


# replacing the read in new line char with 0
la $t4, input
add $t4, $t4, $a1
sb $zero, ($t4)

# copy the string to the resulting string
move $t0, $s1 # i = strlen(input)
move $t1, $s0
la $t3, output

copy_loop:
beq $t0, $zero, copy_end # i != 0
lb $t2, ($t1) 
sb $t2, ($t3) # *output = *input
addi $t1, $t1, 1 # advancing the input ptr
addi $t3, $t3, 1 # advancing the output ptr
subi $t0, $t0, 1 # i--
b copy_loop

copy_end:

add $a3,$a3,$a1 # a3 = &input[strlen(input)]
subi $a3,$a3,1 # subtracting one since the last input char is at input[strlen(input)-1]
la $a2, output
add $a2, $a2, $a1 # passing the address of output advanced by the input length
jal reverse 

la $a0,msg3
li $v0,4
syscall

la $a0,output($zero)
li $v0,4
syscall

li $v0,10
syscall

reverse:
    # $a0 - address of string to reverse
    # a1 - length of the string
    # a2 - address of string where to store the reverse
    addi $sp, $sp, -4
    sw $ra, 0($sp)
    bltz $a1, reverse_end
    lb $t0, 0($a3)
    subi $a1, $a1, 1
    subi $a3, $a3, 1
    sb $t0, 0($a2)
    addi $a2, $a2, 1
    jal reverse
reverse_end:
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

Which seems to work for your examples in MARS 4.5 MIPS simulator.

It is very likely that this code could be done in a more optimal way, but still it seems to get the job done.

EDIT Idea: Save the input to the output string that way the copy is not needed, therefore the code can be reduced to this (only relevant part)

move $a1, $1
la $a0, output # !! using the output buffer for the input
li $v0,8
syscall
move $s0,$a0 # $s0 has the starting address of the string

#
# YOUR CODE GOES HERE(You can use additional labels at the end)
#
move $a3,$s0 # a3 = (char *)input
move $a1,$s1 # a1 = strlen(input)

# the whole copy thing deleted and don't need to be bothered by the new
# lines, it will be overwritten with the reversed string anyway

add $a3,$a3,$a1 # a3 = &input[strlen(input)]
subi $a3,$a3,1 # subtracting one since the last input char is at input[strlen(input)-1]
la $a2, output
add $a2, $a2, $a1 # passing the address of output advanced by the input length
jal reverse
user_47087290
Related