More Programming

13 September

More on programming.

Questions?

Stack Pointer

• Register \$sp is used to keep track of the stack

• Nothing special about \$sp in the hardware, just a convention

• Stack starts at the TOP of memory and grows DOWN (Why?)

• Allocate space on the stack by decrementing \$sp

• Free space on the stack by incrementing \$sp

• Used to save return address and temporary variables as well as for local variables and arrays

Making code work!

• This example is available here

• Write algorithms in C/Java first

• Then hand translate

C to ASM

```char S1[] = "This is a string."
int Foo[16];
char S2[100];

void main()
{
strcpy(S2, S1);
}

void strcpy(char* dst, char* src)
{
int i = 0;
while((dst[i] = src[i]) != 0)
i = i+1;
}
```

Data Segment

```#char S1[] = "This is a string."
#int Foo[16];
#char S2[100];

.data
S1:     .asciiz "This is a string."
.align 2    # get to a 4 byte boundary
Foo:    .space 64   # room for 16 ints
S2:     .space  100 # destination string
```

strcpy

```#void strcpy(char* dst, char* src) {
#        int i = 0;
#   while((dst[i] = src[i]) != 0)
#     i = i+1;
# }

strcpy:
move \$t0,\$zero    # i in \$t0 = 0
L1:
lb   \$t2, 0(\$t1)  # t2 = src[i]
sb   \$t2, 0(\$t1)  # dst[i] = \$t2
addi \$t0, \$t0, 1  # i = i+1
bne  \$t2,\$zero,L1 # if dst[i] != 0 repeat

jr   \$ra          # return
```

Text Segment (main)

```#void main() { strcpy(S2, S1); }

.text
.globl main
main:
addi \$sp, \$sp, -4 # get space on the stack
sw   \$ra, 0(\$sp)  # save main's return address
la   \$a0, S2      # address of S2 in the first argument
la   \$a1, S1      # address of S1 in the second argument
jal  strcpy       # call strcpy
lw   \$ra, 0(\$sp)  # restore main's return address
addi \$sp, \$sp, 4  # restore the stack pointer
jr   \$ra          # exit main
```

How to write assembly programs

• Develop the algorithm in a higher-level language (C/Java/Whatever)

• Translate statement by statement to assembly

• Use “Code Patterns” to guide the translation

• Only a few idioms to master

• Then it is just a mechanical process

Code Pattern for IF

```if(COND_EXPR) { STMTS1 } else { STMTS2 }

CONDCODE(COND_EXPR, Lfalse1, Ltrue2)
Ltrue2:
CODE(STMTS1)
j    Lnext3
Lfalse1:
CODE(STMTS2)
Lnext3:
```

Code Pattern for Conditional Expr

Comparisons: == != < > <= >= Conjunctions: && || Parenthesis: ( )

while

```while(COND_EXPR) { STMTS; }

Lwhile44:
CONDCODE(COND_EXPR, Lfalse45, Ltrue46)
Ltrue46:
CODE(STMTS)
j    Lwhile44
Lfalse45:
```

for

```for(INIT; COND_EXPR; UPDATE) { STMTS }

CODE(INIT)
Lfor17:
CONDCODE(COND_EXPR, Lnext18, Ltrue19)
Ltrue19:
CODE(STMTS)
CODE(UPDATE)
j    Lfor17
Lnext18:
```

Functions

```int foo(int a, int b, int c, int d) { STMTS; return EXPR; }
```

We know a=\$a0, b=\$a1, c=\$a2, d=\$a3. Assign other simple variables to registers as possible

```foo:
save any of \$ra or \$s0-s7 that are overwritten
CODE(STMTS)
CODE(EXPR) leave result in \$v0
restore \$ra, and \$s0-s7 if we saved them earlier
jr   \$ra
```

cfind

```int cfind(char str[], char c) {
for(int i=0; str[i] != 0; i++)
if(str[i] == c) return i;
return -1;
}

a1 == value of character c
v0 == i

no need to save anything
```

Expand function template

```cfind:
# no need to save anything
CODE(‘for ...’)
CODE(‘return -1’)
jr   \$ra
```

Expand for

```cfind:
CODE(‘i=0’)
Lfor1:
CONDCODE(‘s[i] != 0, Lnext2, Ltrue3)
Ltrue3:
CODE(‘if ...’)
CODE(‘i++’)
j    Lfor1
Lnext2:
CODE(‘return -1’)
jr   \$ra
```

Expand for init

```cfind:
move \$v0, \$zero
Lfor1:
CONDCODE(‘s[i] != 0’, Lnext2, Ltrue3)
Ltrue3:
CODE(‘if ...’)
CODE(‘i++’)
j    Lfor1
Lnext2:
CODE(‘return -1’)
jr   \$ra
```

Expand for COND_EXPR

```cfind:
# no need to save anything
move \$v0, \$zero
Lfor1:
lb   \$t1, 0(\$t0) # t1 = s[i]
beq \$t1, \$zero, Lnext2
Ltrue3:
CODE(‘if ...’)
CODE(‘i++’)
j    Lfor1
Lnext2:
CODE(‘return -1’)
jr   \$ra
```

Expand if

```cfind:
move \$v0, \$zero
Lfor1:
lb   \$t1, 0(\$t0) # t1 = s[i]
beq \$t1, \$zero, Lnext2
Ltrue3:
CONDCODE(‘s[i] == c’, Lfalse4, Ltrue5)
Ltrue5:
CODE(‘return i’);
Lfalse4:
CODE(‘i++’)
j    Lfor1
Lnext2:
CODE(‘return -1’)
jr   \$ra
```

Expand if COND_EXPR

```cfind:
move \$v0, \$zero
Lfor1:
lb   \$t1, 0(\$t0) # t1 = s[i]
beq \$t1, \$zero, Lnext2
Ltrue3:
bne \$t1, \$a1, Lfalse4
Ltrue5:
CODE(‘return i’);
Lfalse4:
CODE(‘i++’)
j    Lfor1
Lnext2:
CODE(‘return -1’)
jr   \$ra
```

Expand return

```cfind:
move \$v0, \$zero
Lfor1:
lb   \$t1, 0(\$t0) # t1 = s[i]
beq \$t1, \$zero, Lnext2
Ltrue3:
bne \$t1, \$a1, Lfalse4
Ltrue5:
jr   \$ra # return i already in v0
Lfalse4:
CODE(‘i++’)
j    Lfor1
Lnext2:
CODE(‘return -1’)
jr   \$ra

```

Expand return i

```cfind:
move \$v0, \$zero
Lfor1:
lb   \$t1, 0(\$t0) # t1 = s[i]
beq \$t1, \$zero, Lnext2
Ltrue3:
bne \$t1, \$a1, Lfalse4
Ltrue5:
jr   \$ra # return i already in v0
Lfalse4:
CODE(‘i++’)
j    Lfor1
Lnext2:
CODE(‘return -1’)
jr   \$ra
```

Exand i++

```cfind:
move \$v0, \$zero
Lfor1:
lb   \$t1, 0(\$t0) # t1 = s[i]
beq \$t1, \$zero, Lnext2
Ltrue3:
bne \$t1, \$a1, Lfalse4
Ltrue5:
jr   \$ra # return i already in v0
Lfalse4:
addi \$v0, \$v0, 1 # i = i+1;
j    Lfor1
Lnext2:
CODE(‘return -1’)
jr   \$ra
```

Expand return -1

```cfind:
move \$v0, \$zero
Lfor1:
lb   \$t1, 0(\$t0) # t1 = s[i]
beq \$t1, \$zero, Lnext2
Ltrue3:
bne \$t1, \$a1, Lfalse4
Ltrue5:
jr   \$ra # return i already in v0
Lfalse4:
addi \$v0, \$v0, 1 # i = i+1;
j    Lfor1
Lnext2:
subi \$v0, \$zero, 1 # return value = -1
jr   \$ra
```

Remove unused labels

```cfind:
move \$v0, \$zero # i = 0
Lfor1: