LC-3 Palindrome Help

[daki001]

Hi, i need help with my code which i have been working on for a few days now! Using lc-3 assembly language i need to read in one string, check whether the string is a palindrome and display the result of the checking. I also need to echo each character typed in by the user and the input is ended with an LF character, so after the user presses the "enter" key the program should check whether the string is a palindrome or not and output the result. I've got a piece of code which displays weird things after typing in the string and pressing enter and i can't seem to find what's wrong with it.. PLEASE HELP ME FIX IT!!

.ORIG x3000 
			LEA		R0, Message ; display a message
			PUTS
			LEA		R1, FirstChar ; R1 points to the first
						  ; character which will be entered

; the loop for echoing user's input and deciding whether the string is
; a palindrome	
Next	LD	R2, LF_ASCII															 
		GETC				; read in one character 
		OUT					; write character entered
		ADD	R3, R1, 1			; R3 points to the next character
		ADD	R4, R0,	R2		; check whether the input is LF
		BRnp	Next			; if input is LF check whether it's,
							; a palindrome, otherwise go       ;back to NEXT
		ADD R3, R3, -2
									
Check	LD	R3, Negate ; negate the value of the Last char
		ADD	R5, R1, R3 ; check whether first and last chars
					 ; are equal
		BRz	NextChar	 ; if they are, check the next characters,
					 ; otherwise the string isn't a palindrome
		LEA	R6, NotPalindrome
		PUTS
		BRnzp Done
			
Negate	NOT	R3, R3			; negate R3
		ADD R3, R3, 1			; 2's complement
		RET					; return
		
			
NextChar	        ADD	R1, R1, 1	; increment the first pointer
			ADD	R3, R3, -1	; decrement the second pointer
			BRp	Check       ; check whether the string is done
			LEA	R6, IsPalindrome  ; the string is a palindrome
			PUTS
			BRnzp	Done
									 
Done		HALT						

Message  .STRINGZ	"Please enter a string: "
LF_ASCII	.FILL		-10 
FirstChar	.BLKW		10
IsPalindrome	.STRINGZ	"The string is a palindrome."
NotPalindrome	.STRINGZ	"The string is not a palindrome."
		.END

[schroeder]

Daki this is a classic pushdown automata problem. You can solve it easily by creating a PDA that accepts by empty stack. The language the PDA will accept will be strings of the form x#y where y is the reverse of x, # is the pivot symbol for odd length strings and the pivot is empty string for even length strings. Have the user enter a string and then check it's length to see if it's odd or even. If it's odd, there will be a pivot symbol at n/2 + 1. If it is even there will be no pivot and the string should be a mirror reflection of itself beyond n/2.

Now iterate through the string. Push each character of the string onto the stack. If you reach the pivot point, start popping the stack. If the character popped off the stack is the same as the character you're reading past the pivot, keep popping the stack until the characters are different or until the stack is empty/until you've reached the end of the string. If you empty the stack and you have reached the end of the string, then your PDA has accepted the string and the str is a palindrome. If you encounter any characters different past the pivot or if you reach the end of the string before you emptythe stack, it's not a palindrome. Really though since you should know the length of the string the only case that should happen is the case where characters are different past the pivot.

One caveat: for odd strings don't push the pivot onto the stack, or if you do push it onto the stack then pop it off and throw it away. For even length palindromes this won't be a problem.

As for how to implement that in assembly, you should have all the tools you need including a stack. You will need to know the length of the string to make this method work. This is a classic problem in automata theory for computer science students. Good luck, I hate assembly but without it the 21st century and computers in general would not be possible. It's not assembly's fault, it's the ugly hardware underneath it :-)

cheers
schroeder

[schroeder]

Btw there is another way to solve this problem which you may be attempting to do. You can read the input string into memory and then iterate through the string up to n/2. As you iterate, check to see if the character at position x is equal to the character at n-x-1 where n is the length of the string. If they are equal then the string is a palindrome. If the string is stored contiguously in memory 4 characters at a time as a 32 bit word, then the tricky part is reading each character from the string, which you'd have to do either way anyways. As for debugging your code I'm afraid I won't be able to help with that.

good luck
schroeder

[daki001]

I've been trying to come up with a piece of code which does the first solution you gave me but am failing terribly as i realize that once i get the user input R0 is overwritten everytime a character is entered which means that in order for me to be able to work with the string i need to store it somewhere in memory and also have a counter running at the same time so i can determine the length of the string. Therefore, what i done was store the string entered in a stack, however there lies another problem because although i know now whether the string is even or odd and where the pivot lies i need to pop a few characters to get to n/2 and start checking.. the problem here is how do i store those characters in the order popped so i can compare them to the rest of the string in the stack rather than losing the popped values??

[schroeder]

Daki now that I think about it there should be an easy way to implement the second solution if only you could index each character of the string. If you could store the string contiguously in memory (one character after another), then you could retrieve each string in constant time and scan the string linearly in O(N) to determine if it's a palindrome by implementing the second solution.

I think the way to do this is to mess around with the memory load commands. It should ask you for an address in memory to load. And you should be able to do math on that address (e.g. add bytes to it). If you add 8 bits / 1 byte to the word storing the first character, that should increase its address by 8 bits / 1 byte to the next character location, and so on.

Can you try that solution? If you can make that work, your code will be really short and efficient. The PDA solution might be a little tough as you say because you would probably need two stacks to work with (at which point I believe you have a turing machine and no longer a PDA).

So the psuedo code would look something like this:
<establish some starting memory address for your string in your data area>
<make a copy of this address and store it some register, say $0>
<set a ctr $8 to be 0; $8 will keep track of the length of the str>
<repeat for each character the user enters>
<increment $8 by 1>
<store the character at the memory address in $0>
<echo the character if desired>
<increment $0 by 1 byte so that it's ready for storing the next character>
<end repeat>
<set a var, say $0, to the starting memory address for your string (the original memory location that $0 was created from, not $0's current value>
<set a ctr, say $2, to 0; we'll use this ctr to keep track of which position in the string we're on; it goes from 0 to n/2-1>
<repeat from 0 to n/2 - 1>
<set a var, say $1, to be the address at $0 + (($8 - 1) - $2) bytes> # remember $8 is the length of the string
<set a var, say $3, to be the first byte at the address stored by $0; this is character at position i in your string, e.g. the first character for the first pass>
<set a var, say $4, to be the first byte at the address stored by $1, this is the character at position n-1-i in your string, e.g. the last character for the first pass, where n is the length of the string and i is the character position you're on in the loop, from 0 to n/2-1>
<compare $3 and $4 and make sure they are equal; if they are not, branch off somewhere to tell the user that the str is not a palindrome and then halt; otherwise, continue>
<end repeat>
<if you've made this far, the string is a palindrome>

The trick here is to make sure you can store the characters contiguously in memory and that you can read two of them in constant time, which you should be able to do using math on your address as I've detailed above.

BTW, just to be clear, the literal identifier IsPalindrome is a memory address :-) The compiler should actually replace literals with that name with the memory address that it actually points to in your data segment as compile time. So you should be able to do math on it just the same as if it was any other memory location. That's the key to this algorithm is being able to do that. IsPalindrome +1byte should be the character T, IsPalindrome +2bytes should be the character h, and IsPalindrome +5bytes should be the character s, etc, etc. Part of the point of this assignment might be to get you to realize that. It's also a good idea to store the string to be entered at the END of the data stack, to keep from overwriting any variables before it (buffer overflow) and to keep your program from behaving oddly. Finally, you should make use of whatever debugger you have to watch the variables you set at runtime to make sure they are being set properly. Watch $3 and $4 in particular to make sure they are being set to the right characters. If they are not, you have a bug somewhere! You should also watch $1 and $2 be incremented and decremented by 1 byte respectively, which you should be able to see in hex as the value in your debugger will decrease by 1 byte each time.

Good luck!
schroeder

[sasser]

What you need to do is you need to create an address and stack the letters that the user is inputting into it.

1) For example, set the stack address at x2000, then increment it everytime the user enters a letter. You cannot stack into registers because it's only a temporary slot.

2) Then while it increments, you can also allow it to count how many letters the users have entered.

3) Work out if the length is odd or even

.... and then you can work out the rest, :D

[vkszn]

http://www.techpint.com/forum/lc3-assembly-palindrome-program
for the correct solution

[maaria]

that's great news. i din't hear about this before. thanks for informing me about this.