Lab 5
Palindromes are words or phrases
that read the same backwards
or forwards such as “A Santa at NASA” and “A
man, a plan, a canal:
Serious
programming should start not with coding, but with careful design.
- The first step of the development
process is to understand the requirements.
- Then the requirements should be
translated into an unambiguous specification.
- Now the design can begin, defining a program structure, the data structures and the algorithms. The algorithms may be expressed in pseudo-code. Only when the design is developed should the coding begin. Individual modules should be coded, tested thoroughly and documented, and the program built piece by piece.
*An
algorithm (pronounced AL-go-rith-um) is a procedure or formula for
solving a problem. In computer
science an algorithm
is a finite set of well-defined instructions for accomplishing
some task which, given an initial state, will terminate in a corresponding
recognizable end-state (contrast with heuristic). Algorithms can be implemented
by computer programs, although often in restricted forms; mistakes in
implementation and limitations of the computer can prevent a computer program
from correctly executing its intended algorithm.
The concept of an algorithm is often illustrated
by the example of a recipe, although many algorithms are much more complex;
algorithms often have steps that repeat (iterate) or require decisions (such as
logic or comparison) until the task is completed. Correctly performing an
algorithm will not solve a problem if the algorithm is flawed or not
appropriate to the problem. For example, a hypothetical algorithm for making a
potato salad will fail if there are no potatoes present, even if all the
motions of preparing the salad are performed as if the potatoes were there.
Different algorithms may complete the same task
with a different set of instructions in more or less time, space, or effort
than others. For example, given two different recipes for making potato salad,
one may have peel the potato before boil the potato while the
other presents the steps in the reverse order, yet they both call for these
steps to be repeated for all potatoes and end when the potato salad is ready to
be eaten.
Below is an algorithm* which
takes a string and determines if it is a palindrome.
Palindrome = true
Set left pointer to point at leftmost character
Set right pointer to point at rightmost character
Repeat
Get left character at the left pointer position
Get rightt character at the right pointer position
IF left character <> right character
THEN Palindrome = false
Left pointer = left pointer + 1
Right pointer = right pointer – 1
Until middle of string OR Palindrome = false
An algorithm describes a solution at some level abstraction …. in order to implement the solution as code we must develop more detail.
Case in point…
When have you reached the “middle”?
Looking at some examples
A.
Even length strings such as “ABCCBA”
Terminates when left pointer=right pointer+1
B.
Odd length string “ABCCBA”
Terminates when left pointer=right pointer
1. Design the detailed algorithm to find the middle and give a code fragment which implements it.
test for middle
CMP r0,r1
BEQ waspal
ADD r2, r0,#1
CMP r2,r1
BEQ waspal
2. Create a code fragment written as subroutine which is passed the start of the string in r0 and its end in r1. The subroutine should return a 0 if the string is not a palindrome and 1 if it is.
again LDRB r3, [r0],#1 ;get characters and update pointers
LDRB r4, [r1],#-1
CMP r3,r4 ;compare characters
BNE notpal ;if different then fail
… ;test for mddle of string
BNE again
waspal
notpal MOV pc,lr
The above has a problem it automatically updates the pointers. Change test to left pointer = right pointer + 2.
3. Create a code fragment which finds the end of string (terminated by 0).
4. Add the above fragment to a shell which calls the palindrome subroutine.
5. Merge the code fragments into a running program and test it with several potential palindromes. Use the debugger to follow the flow.
AREA palindrome, CODE,
READONLY
SWI_Exit EQU 0x11
ENTRY
start
LDR r0,=string
MOV r1,r0
loop LDRB r2,[r1],#1
CMP r2,#0
BNE loop
SUB r1,r1,#2
BL pal
stop SWI SWI_Exit
pal MOV r10,#0x0
again LDRB r3,[r0]
LDRB r4,[r1]
CMP r3,r4
BNE notpal
CMP r0,r1
BEQ waspal
ADD r2,r0,#1
CMP r2,r1
BEQ waspal
ADD r0,r0,#1
SUB r1,r1,#1
B again
waspal MOV r10,#0x1
notpal MOV pc,lr
string DCB "abcba",0
END
5. The concept of “Computational density'' concerns the number of useful computational operations per unit space, and per unit time, and also per unit mass/energy included in the system. Briefer code can be easier to understand, faster to run, and have smaller space requirements. Review your code and see if it can be simplified.
Area palindrome, CODE, READONLY
SWI_Exit EQU 0x11
ENTRY
start
LDR r0,=string
MOV r1,r0
loop LDRB r10,[r1],#1
CMP r10,#0
BNE loop
SUB r1,r1,#2
BL pal
stop SWI SWI_Exit
pal LDRB r3,[r0],#1
LDRB r4,[r1],#-1
CMP r3,r4
MOVNE pc,lr
SUBS r3,r1,r0
CMP r0,r1
BEQ waspal
BMI waspal
B pal
waspal MOV r10,#0x1
MOV pc,lr
END
6. SWIs (often called software traps) allow a user program to “call” the OS that is, SWIs are how system calls are implemented. When SWIs execute, the processor changes modes (from User to Supervisor mode on the ARM) and disables interrupts. It then executes the system code to perform the necessary function.
The ARM architecture defines a Vector Table indexed by exception type. One SWI, CPU does the following: PC 0x08
On SWI, the processor
(1) copies CPSR to SPSR_SVC
(2) set the CPSR mode bits to supervisor mode
(3) sets the CPSR IRQ to disable
(4) stores the value (PC + 4) into LR_SVC
(5) forces PC to 0x08
Types of SWIs
· SWI_WriteC(SWI 0) Write a byte
· SWI_Write0(SWI 2) Write the nullterminated string SWI_ReadC(SWI 4) Read a byte
· SWI_Exit(SWI 0x11) Halt emulation this is how a program exits
· SWI_EnterOS(SWI 0x16) Put the processor in supervisor mode
· SWI_Clock(SWI 0x61) Return the number of centiseconds
· SWI_Time(SWI 0x63) Return the number of secs since Jan. 1, 1970
Alter your program so that it outputs “yes” or “no” to the console using a SWI 0. Register r0 should contain the byte value representing the ascii code of the character to write.
AREA palindrome, CODE, READONLY
SWI_Exit EQU 0x11
SWI_WriteC EQU 0x00
ENTRY
start
LDR r0,=string
MOV r1,r0
loop LDRB r2,[r1],#1
CMP r2,#0
BNE loop
SUB r1,r1,#2
BL pal
print LDRB r0, [r10]
CMP
r0, #0
SWINE SWI_WriteC
ADD r10, r10, #1
BNE print
stop SWI SWI_Exit
pal ADR r10, textn
again LDRB r3,[r0]
LDRB r4,[r1]
CMP r3,r4
BNE notpal
CMP r0,r1
BEQ waspal
ADD r2,r0,#1
CMP r2,r1
BEQ waspal
ADD r0,r0,#1
SUB r1,r1,#1
B again
waspal ADR r10, texty
notpal MOV pc,lr
string DCB "abcba",0
texty DCB "YES\n",0
textn DCB "NO\n",0