Computer Systems Fundamentals

call_return.c

C Function with No Parameters or Return Value 
#include <stdio.h>

void f(void);

int main(void) {
    printf("calling function f\n");
    f();
    printf("back from function f\n");
    return 0;
}

void f(void) {
    printf("in function f\n");
}
call_return.broken.s
simple example of returning from a function loops because main does not save return address 
main:
	la	$a0, string0		# printf("calling function f\n");
	li	$v0, 4
	syscall

	jal	f			# set $ra to following address

	la	$a0, string1		# printf("back from function f\n");
	li	$v0, 4
	syscall

	li	$v0, 0			# return from function main
	jr	$ra			# breaks because $ra has been changed since main called


f:
	la	$a0, string2		# printf("in function f\n");
	li	$v0, 4
	syscall
	jr	$ra			# return from function f


	.data
string0:
	.asciiz "calling function f\n"
string1:
	.asciiz "back from function f\n"
string2:
	.asciiz "in function f\n"
call_return_raw.s
simple example of placing return address on stack note stack grows down 
main:
	addi	$sp, $sp, -4		# move stack pointer down to make room
	sw	$ra, 0($sp)		# save $ra on $stack

	la	$a0, string0		# printf("calling function f\n");
	li	$v0, 4
	syscall

	jal	f			# set $ra to following address

	la	$a0, string1		# printf("back from function f\n");
	li	$v0, 4
	syscall

	lw	$ra, 0($sp)		# recover $ra from $stack
	addi	$sp, $sp, 4		# move stack pointer back to what it was

	li	$v0, 0			# return 0 from function main
	jr	$ra			#


f:
	la	$a0, string2		# printf("in function f\n");
	li	$v0, 4
	syscall
	jr	$ra			# return from function f


	.data
string0:
	.asciiz "calling function f\n"
string1:
	.asciiz "back from function f\n"
string2:
	.asciiz "in function f\n"
call_return.s
simple example of placing return address on stack begin, end, push pop are pseudo-instructions provided by mipsy but not spim 
main:
	push	$ra			# save $ra on $stack

	la	$a0, string0		# printf("calling function f\n");
	li	$v0, 4
	syscall

	jal	f			# set $ra to following address

	la	$a0, string1		# printf("back from function f\n");
	li	$v0, 4
	syscall

	pop	$ra			# recover $ra from $stack

	li	$v0, 0			# return 0 from function main
	jr	$ra			#


# f is a leaf function so it doesn't need an epilogue or prologue
f:
	la	$a0, string2		# printf("in function f\n");
	li	$v0, 4
	syscall
	jr	$ra			# return from function f


	.data
string0:
	.asciiz "calling function f\n"
string1:
	.asciiz "back from function f\n"
string2:
	.asciiz "in function f\n"
return_answer.c
simple example of returning a value from a function 
#include <stdio.h>

int answer(void);

int main(void) {
    int a = answer();
    printf("%d\n", a);
    return 0;
}

int answer(void) {
    return 42;
}
return_answer.s
simple example of returning a value from a function note storing of return address $ra
code for function main 
main:
	begin				# move frame pointer
	push	$ra			# save $ra onto stack

	jal	answer			# call answer(), return value will be in $v0

	move	$a0, $v0		# printf("%d", a);
	li	$v0, 1			#
	syscall				#

	li	$a0, '\n'		# printf("%c", '\n');
	li	$v0, 11			#
	syscall				#

	pop	$ra			# recover $ra from stack
	end				# move frame pointer back

	li	$v0, 0			# return
	jr	$ra			#


# code for function answer
answer:
	li	$v0, 42			# return 42
	jr	$ra			#
more_calls.c
example of function calls 
#include <stdio.h>

int sum_product(int a, int b);
int product(int x, int y);

int main(void) {
    int z = sum_product(10, 12);
    printf("%d\n", z);
    return 0;
}

int sum_product(int a, int b) {
    int p = product(6, 7);
    return p + a + b;
}

int product(int x, int y) {
    return x * y;
}
more_calls.s
example of function calls note storing of return address $a0, $a1 and $ra on stack 
main:
	begin				# move frame pointer
	push	$ra			# save $ra onto stack

	li	$a0, 10			# sum_product(10, 12);
	li	$a1, 12
	jal	sum_product

	move	$a0, $v0		# printf("%d", z);
	li	$v0, 1
	syscall

	li	$a0, '\n'		# printf("%c", '\n');
	li	$v0, 11
	syscall

	pop	$ra			# recover $ra from stack
	end				# move frame pointer back

	li	$v0, 0			# return 0 from function main
	jr	$ra			# return from function main



sum_product:
	begin				# move frame pointer
	push	$ra			# save $ra onto stack
	push	$s0			# save $s0 onto stack
	push	$s1			# save $s1 onto stack

	move	$s0, $a0		# preserve $a0 for use after function call
	move	$s1, $a1		# preserve $a1 for use after function call

	li	$a0, 6			# product(6, 7);
	li	$a1, 7
	jal	product



	add	$v0, $v0, $s0		# add a and b to value returned in $v0
	add	$v0, $v0, $s1		# and put result in $v0 to be returned

	pop	$s1			# recover $s1 from stack
	pop	$s0			# recover $s0 from stack
	pop	$ra			# recover $ra from stack
	end				# move frame pointer back

	jr	$ra			# return from sum_product


product:				# product doesn't call other functions
                        # so it doesn't need to save any registers
	mul	$v0, $a0, $a1		# return argument * argument 2
	jr	$ra			#
two_powerful.c
recursive function which prints first 20 powers of two in reverse 
#include <stdio.h>

void two(int i);

int main(void) {
    two(1);
}

void two(int i) {
    if (i < 1000000) {
        two(2 * i);
    }
    printf("%d\n", i);
}
two_powerful.s
simple example of placing return address ($ra) and $a0 on the stack recursive function which prints first 20 powers of two in reverse 
main:
	begin				# move frame pointer
	push	$ra			# save $ra onto stack

	li	$a0, 1
	jal	two			# two(1);

	pop	$ra			# recover $ra from stack
	end				# move frame pointer back

	li	$v0, 0			# return 0
	jr	$ra			#


two:
	begin				# move frame pointer
	push	$ra			# save $ra onto stack
	push	$s0			# save $s0 onto stack

	move	$s0, $a0

	bge	$a0, 1000000, two_end_if
	mul	$a0, $a0, 2
	jal	two
two_end_if:

	move	$a0, $s0
	li	$v0, 1			# printf("%d");
	syscall

	li	$a0, '\n'		# printf("%c", '\n');
	li	$v0, 11
	syscall

	pop	$s0			# recover $s0 from stack
	pop	$ra			# recover $ra from stack
	end				# move frame pointer back

	jr	$ra			# return from two
squares.c
store first 10 squares into an array which is a local variable then print them from array 
#include <stdio.h>

int main(void) {
    int squares[10];
    int i = 0;
    while (i < 10) {
        squares[i] = i * i;
        i++;
    }
    i = 0;
    while (i < 10) {
        printf("%d", squares[i]);
        printf("%c",'\n');
        i++;
    }
    return 0;
}
squares.s
i in register $t0 registers $t1, and $t2, used to hold temporary results 
main:
	begin				# move frame pointer
	addi	$sp, $sp, -40		# move stack pointer down to make room to store array numbers on stack

	li	$t0, 0			# i = 0
loop0:
	bge	$t0, 10, end0		# while (i < 10) {

	mul	$t1, $t0, 4		#    calculate &numbers[i]
	add	$t2, $t1, $sp		#
	mul	$t3, $t0, $t0		#    calculate i * i
	sw	$t3, 0($t2)		#    store in array

	addi	$t0, $t0, 1		#    i++;
	b	loop0			# }
end0:

	li	$t0, 0			# i = 0
loop1:
	bge	$t0, 10, end1		# while (i < 10) {

	mul	$t1, $t0, 4
	add	$t2, $t1, $sp		#   calculate &numbers[i]

	lw	$a0, 0($t2)		#   load numbers[i] into $a0
	li	$v0, 1			#   printf("%d", numbers[i])
	syscall				#

	li	$a0, '\n'		#   printf("%c", '\n');
	li	$v0, 11			#
	syscall				#

	addi	$t0, $t0, 1		#   i++
	b	loop1			# }
end1:

	addi	$sp, $sp, 40		# move stack pointer back up to what it was when main called
	end				# move frame pointer back

	li	$v0, 0			# return 0
	jr	$ra			#
frame_pointer.c
example of function where frame pointer useful because stack grows during function execution 
#include <stdio.h>

void f(int a) {
    int length;
    scanf("%d", &length);
    int array[length];
    // ... more code ...
    printf("%d\n", a);
}
frame_pointer.broken.s
example stack growing during function execution breaking the function return 
f:
	addi	$sp, $sp, -8		# move stack pointer down to make room
	sw	$ra, 4($sp)		# save $ra on $stack
	sw	$a0, 0($sp)		# save $a0 on $stack

	li	$v0, 5			# scanf("%d", &length);
	syscall

	mul	$v0, $v0, 4		# calculate array size
	sub	$sp, $sp, $v0		# move stack_pointer down to hold array

    # ...

                        # breaks because stack pointer moved down to hold array
                        # so we won't restore the correct value
	lw	$ra, 4($sp)		# restore $ra from $stack
	addi	$sp, $sp, 8		# move stack pointer back up to what it was when main called

	jr	$ra			# return from f
frame_pointer.s
using a frame pointer to handle stack growing during function execution 
f:
	begin				# move frame pointer
	push	$ra			# save $ra on stack

	li	$v0, 5			# scanf("%d", &length);
	syscall

	mul	$v0, $v0, 4		# calculate array size
	sub	$sp, $sp, $v0		# move stack_pointer down to hold array

    # ... more code ...

	pop	$ra			# restore $ra
	end
	jr	$ra			# return
strlen_array.c
calculate the length of a string using a strlen like function 
#include <stdio.h>

int my_strlen(char *s);

int main(void) {
    int i = my_strlen("Hello");
    printf("%d\n", i);
    return 0;
}

int my_strlen(char *s) {
    int length = 0;
    while (s[length] != 0) {
        length++;
    }
    return length;
}
strlen_array.simple.c
calculate the length of a string using a strlen like function 
#include <stdio.h>

int my_strlen(char *s);

int main(void) {
    int i = my_strlen("Hello");
    printf("%d\n", i);
    return 0;
}

int my_strlen(char *s) {
    int length = 0;
loop:;
    if (s[length] == 0) goto end;
       length++;
    goto loop;
end:;
    return length;
}
strlen_array.s
simple example of placing return address ($ra) on the stack calculate the length of a string using a strlen like function 
main:
	begin				# move frame pointer
	push	$ra			# save $ra onto stack

	la	$a0, string		# my_strlen("Hello");
	jal	my_strlen

	move	$a0, $v0		# printf("%d", i);
	li	$v0, 1
	syscall

	li	$a0, '\n'		# printf("%c", '\n');
	li	$v0, 11
	syscall

	pop	$ra			# recover $ra from stack
	end				# move frame pointer back

	li	$v0, 0			# return 0 from function main
	jr	$ra			#


my_strlen:				# length in t0, s in $a0
	li	$t0, 0
loop:					# while (s[length] != 0) {
	add	$t1, $a0, $t0		#   calculate &s[length]
	lb	$t2, 0($t1)		#   load s[length] into $t2
	beq	$t2, 0, end		#
	addi	$t0, $t0, 1		#   length++;
	b	loop			# }
end:
	move	$v0, $t0		# return length
	jr	$ra			#


	.data
string:
	.asciiz "Hello"
strlen_pointer.c
calculate the length of a string using a strlen like function 
#include <stdio.h>

int my_strlen(char *s);

int main(void) {
    int i = my_strlen("Hello Andrew");
    printf("%d\n", i);
    return 0;
}

int my_strlen(char *s) {
    int length = 0;
    while (*s != 0) {
        length++;
        s++;
    }
    return length;
}
strlen_pointer.simple.c
calculate the length of a string using a strlen like function 
#include <stdio.h>

int my_strlen(char *s);

int main(void) {
    int i = my_strlen("Hello Andrew");
    printf("%d\n", i);
    return 0;
}

int my_strlen(char *s) {
    int length = 0;
loop:;
    if (*s == 0) goto end;
        length++;
        s++;
        goto loop;
end:;
    return length;
}
strlen_pointer.s
simple example of placing return address ($ra) on the stack calculate the length of a string using a strlen like function 
main:
	begin				# move frame pointer
	push	$ra			# save $ra onto stack

	la	$a0, string		# my_strlen("Hello");
	jal	my_strlen

	move	$a0, $v0		# printf("%d", i);
	li	$v0, 1
	syscall

	li	$a0, '\n'		# printf("%c", '\n');
	li	$v0, 11
	syscall

	pop	$ra			# recover $ra from stack
	end				# move frame pointer back

	li	$v0, 0			# return 0 from function main
	jr	$ra			#


my_strlen:				# length in t0, s in $a0
	li	$t0, 0
loop:					#
	lb	$t1, 0($a0)		# load *s into $t1
	beq	$t1, 0, end		#
	addi	$t0, $t0, 1		# length++
	addi	$a0, $a0, 1		# s++
	b	loop			#
end:
	move	$v0, $t0		# return length
	jr	$ra			#


	.data
string:
	.asciiz "Hello Andrew"
stack_inspect.c 
#include <stdio.h>
#include <stdint.h>

/*
$ clang --version
Ubuntu clang version 11.0.0-2~ubuntu20.04.1
$ clang stack_inspect.c
$ a.out
 0: Address 0x7ffe7d80defc contains        3     <- e[0]
 1: Address 0x7ffe7d80df00 contains        7     <- e[1]
 2: Address 0x7ffe7d80df04 contains        5     <- d
 3: Address 0x7ffe7d80df08 contains        9     <- c
 4: Address 0x7ffe7d80df0c contains       2a     <- b
 5: Address 0x7ffe7d80df10 contains 7d80df30     <- saved frame pointer of main (lower 32 bits)
 6: Address 0x7ffe7d80df14 contains     7ffe     <- saved frame pointer of main (upper 32 bits)
 7: Address 0x7ffe7d80df18 contains   4011d3     <- saved return address of main (lower 32 bits)
 8: Address 0x7ffe7d80df1c contains        0     <- saved return address of main (upper 32 bits)

 9: Address 0x7ffe7d80df20 contains 7d80e020     <- STACK pointer (???) (lower 32 bits)
10: Address 0x7ffe7d80df24 contains     7ffe     <- STACK pointer (???) (upper 32 bits)
11: Address 0x7ffe7d80df28 contains        9     <- a
12: Address 0x7ffe7d80df2c contains        0     <- padding (for next 64-bit pointer ^)
13: Address 0x7ffe7d80df30 contains        0     <- saved frame pointer of _start (lower 32 bits)
14: Address 0x7ffe7d80df34 contains        0     <- saved frame pointer of _start (upper 32 bits)
15: Address 0x7ffe7d80df38 contains 9fbb30b3     <- saved return address of _start (lower 32 bits)
16: Address 0x7ffe7d80df3c contains     7f98     <- saved return address of _start (upper 32 bits)
17: Address 0x7ffe7d80df40 contains       71     <- ???
18: Address 0x7ffe7d80df44 contains        0     <- ???
19: Address 0x7ffe7d80df48 contains 7d80e028     <- source information
20: Address 0x7ffe7d80df4c contains     7ffe     <- source information

$ gcc --version
gcc (Ubuntu 10.3.0-1ubuntu1~20.04) 10.3.0
$ gcc stack_inspect.c
$ a.out                                          # GCC stores local arrays first in the stack, so some things are missing from the start of the output.
                                           9     <- c
                                          2a     <- b
                                                 <- TEXT pointer (???)
                                                 <- TEXT pointer (???)
                                           0     <- padding (for next 64-bit pointer ^)
                                           5     <- d
 0: Address 0x7ffccc6e6e90 contains        3     <- e[0]
 1: Address 0x7ffccc6e6e94 contains        7     <- e[1]
 2: Address 0x7ffccc6e6e98 contains f08e2f00     <- ???
 3: Address 0x7ffccc6e6e9c contains 8c526a01     <- ???
 4: Address 0x7ffccc6e6ea0 contains cc6e6ec0     <- saved frame pointer of main (lower 32 bits)
 5: Address 0x7ffccc6e6ea4 contains     7ffc     <- saved frame pointer of main (upper 32 bits)
 6: Address 0x7ffccc6e6ea8 contains 11c6a221     <- saved return address of main (lower 32 bits)
 7: Address 0x7ffccc6e6eac contains     5582     <- saved return address of main (upper 32 bits)

 8: Address 0x7ffccc6e6eb0 contains cc6e6fb0     <- STACK pointer (???) (lower 32 bits)
 9: Address 0x7ffccc6e6eb4 contains     7ffc     <- STACK pointer (???) (upper 32 bits)
10: Address 0x7ffccc6e6eb8 contains        0     <- padding (for next 64-bit pointer ^)
11: Address 0x7ffccc6e6ebc contains        9     <- a
12: Address 0x7ffccc6e6ec0 contains        0     <- saved frame pointer of _start (lower 32 bits)
13: Address 0x7ffccc6e6ec4 contains        0     <- saved frame pointer of _start (upper 32 bits)
14: Address 0x7ffccc6e6ec8 contains 6f6d70b3     <- saved return address of _start (lower 32 bits)
15: Address 0x7ffccc6e6ecc contains     7fba     <- saved return address of _start (upper 32 bits)
16: Address 0x7ffccc6e6ed0 contains       71     <- ???
17: Address 0x7ffccc6e6ed4 contains        0     <- ???
18: Address 0x7ffccc6e6ed8 contains cc6e6fb8     <- source information
19: Address 0x7ffccc6e6edc contains     7ffc     <- source information
20: Address 0x7ffccc6e6ee0 contains 6f898618     <- ??? (upper 32 bits)
*/

void f(int b, int c) {
    int d = 5;
    uint32_t e[2] = { 3, 7 };

    for (int i = 0; i < 20; i++)
        printf("%2d: Address %p contains %8x\n", i, &e[i], e[0 + i]);
}

int main(void) {
    int a = 9;
    f(42, a);
    return 0;
}
invalid0.c 



Run at CSE like this


$ clang -Wno-everything invalid0.c -o invalid0
$ ./invalid0
42 77 77 77 77 77 77 77 77 77




#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int a[10];
    int b[10];
    printf("a[0] is at address %p\n", &a[0]);
    printf("a[9] is at address %p\n", &a[9]);
    printf("b[0] is at address %p\n", &b[0]);
    printf("b[9] is at address %p\n", &b[9]);

    for (int i = 0; i < 10; i++) {
        a[i] = 77;
    }

    // loop writes to b[10] .. b[12] which don't exist -
    // on CSE servers  (clang 7.0 x86_64/Linux)
    // b[12] is stored where a[0] is stored
    // on CSE servers  (clang 7.0 x86_64/Linux)
    // b[10] is stored where a[0] is stored

    for (int i = 0; i <= 12; i++) {
        b[i] = 42;
    }

    // prints 42 77 77 77 77 77 77 77 77 77 on x86_64/Linux
    // prints 42 42 42 77 77 77 77 77 77 77 at CSE
    for (int i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}
invalid1.c 



Run at CSE like this


$ clang -Wno-everything invalid1.c -o invalid1
$ ./invalid1
i is at address 0x7ffe2c01cd58
a[0] is at address 0x7ffe2c01cd30
a[9] is at address 0x7ffe2c01cd54
a[10] would be stored at address 0x7ffe2c01cd58


doesn't terminate




#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int i;
    int a[10];
    printf("i is at address %p\n", &i);
    printf("a[0] is at address %p\n", &a[0]);
    printf("a[9] is at address %p\n", &a[9]);
    printf("a[10] would be stored at address %p\n", &a[10]);

    // loop writes to a[10] .. a[11] which don't exist -
    // but on CSE servers  (clang 7.0 x86_64/Linux)
    // i would be stored where a[11] is stored

    for (i = 0; i <= 11; i++) {
        a[i] = 0;
    }

    return 0;
}
invalid2.c 



Run at CSE like this


$ clang -Wno-everything  invalid2.c -o invalid2
$ ./invalid2
answer=42




#include <stdio.h>

void f(int x);

int main(void) {
    int answer = 36;
    printf("answer is stored at address %p\n", &answer);

    f(5);
    printf("answer=%d\n", answer); // prints 42 not 36

    return 0;
}

void f(int x) {
    int a[10];

    // a[18] doesn't exist
    // on CSE servers  (clang 7.0 x86_64/Linux)
    // variable answer in main happens to be where a[19] would be

    printf("a[18] would be stored at address %p\n", &a[18]);

    a[18] = 42;
}
invalid3.c 



Run at CSE like this


$ clang -Wno-everything invalid3.c -o invalid3
$ ./invalid3

I hate you.
$



#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

void f(void);

int main(void) {
    f();

    printf("I love you and will never say,\n");
    printf("I hate you.\n");

    return 0;
}

void f(void) {
    uint64_t a[1];

#ifdef __clang__
#if __clang_major__ >= 18
#error "Don't know the correct offset for this clang version"
#elif __clang_major__ >= 14
    a[2] += 14;
#elif __clang_major__ >= 4
    a[2] += 17;
#elif __clang_major__ == 3
#if __clang_minor__ >= 5
    a[2] += 17;
#elif __clang_minor__ >= 4
    a[2] += 15;
#else
// clang 3.0-3.3 are broken on godbolt.org
#error "Don't know the correct offset for this clang version"
#endif
#else
// clang <3.0 are not avalible on godbolt.org
#error "Don't know the correct offset for this clang version"
#endif
#else
#error "This program must be compiled with clang"
#endif

    // function f has it return address on the stack
    // the call of function f from main should return to
    // the next statement which is:  printf("I love you and will never say,\n");
    //
    // on CSE servers  (clang 11.0 x86_64/Linux)
    // f's return address is stored where a[2] would be
    //
    // so changing a[2] changes where the function returns
    //
    // adding 17 to a[12] happens to cause it to return 2 statements later
    // at:  printf("I hate you.\n");
}
invalid4.c 



Run at CSE like this


$ clang invalid4.c -o invalid4
$ ./invalid4
authenticated is at address 0xff94bf44
password is at address 0xff94bf3c

Enter your password: 123456789

Welcome. You are authorized.
$



#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[]) {
    int authenticated = 0;
    char password[8];

    printf("authenticated is at address %p\n", &authenticated);
    printf("password[8] would be at address %p\n", &password[8]);

    printf("Enter your password: ");
    int i = 0;
    int ch = getchar();
    while (ch != '\n' && ch != EOF) {
        password[i] = ch;
        ch = getchar();
        i = i + 1;
    }
    password[i] = '\0';

    if (strcmp(password, "buffalo") == 0) {
        authenticated = 1;
    }

    // a password longer than 8 characters will overflow the array password
    // on CSE servers  (clang 7.0 x86_64/Linux)
    // the variable authenticated is at the address where
    // where password[8] would be and gets overwritten
    //
    // This allows access without knowing the correct password

    if (authenticated) {
        printf("Welcome. You are authorized.\n");
    } else {
        printf("Welcome. You are unauthorized.  Your death will now be implemented.\n");
        printf("Welcome. You will experience a tingling sensation and then death. \n");
        printf("Remain calm while your life is extracted.\n");
    }

    return 0;
}
func.c 
#include <stdio.h>

int func(int n);

int main(void) {
    printf("main is calling func(42)\n");
    int f = func(42);
    printf("func has returned back to main. func(42) returned %d\n", f);

    return 0;
}

int func(int n) {
    printf("hello from func!\n");
    return 2 * n;
}
factorial.c 
#include <stdio.h>

int factorial(int);

int main(void) {
    int input;
    scanf("%d", &input);

    int f = factorial(input);

    printf("%d", input);
    printf("! = ");
    printf("%d", f);
    putchar('\n');

    return 0;
}

int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}
factorial.simple.c 
#include <stdio.h>

int factorial(int);

int main(void) {
    int input;
    scanf("%d", &input);

    int f = factorial(input);

    printf("%d", input);
    printf("! = ");
    printf("%d", f);

    putchar('\n');

    return 0;
}

int factorial(int n) {

    int retval;

    if (n == 0) goto factorial__n_eq_0;

    retval = n * factorial(n - 1);
    goto factorial__epilogue;


factorial__n_eq_0:
    retval = 1;

factorial__epilogue:
    return retval;



}
factorial.s 
main:
	# Args:	void
	# Returns:
	#	- $v0: int
	#
	# Locals:
	#	- $s0: int input
	#	- $t0: int f
	#
	# Stack:	[$ra, $s0]
	# Uses:		[$ra, $s0, $v0, $t0, $a0]
	# Clobbers:	[$v0, $t0, $a0]
	#
	# Structure:
	# -> main
	#	-> [prologue]
	#	-> [body]
	#	-> [epilogue]

main__prologue:
	begin
	push	$ra
	push	$s0

	# The following two instructions are equivalent to `push $s0`
	# addi	$sp, $sp, -4
	# sw	$s0, ($sp)

main__body:
	li	$v0, 5			# syscall 5: read_int
	syscall				#
	move	$s0, $v0		# scanf("%d", &input);

	move	$a0, $v0
	jal	factorial		#
	move	$t0, $v0		# int f = factorial(input);

	li	$v0, 1			# syscall 1: print_int
	move	$a0, $s0		#
	syscall				# printf("%d", input);

	li	$v0, 4			# syscall 4: print_string
	la	$a0, main__result_msg	#
	syscall				# printf("!= ");


	li	$v0, 1			# syscall 1: print_int
	move	$a0, $t0		#
	syscall				# printf("%d", f);

	li	$v0, 11			# syscall 11: print_char
	li	$a0, '\n'		#
	syscall				# putchar('\n');

	# Restore the original value of $s0 from memory
	# lw	$s0, ($sp)
	# addi	$sp, $sp, 4

main__epilogue:
	pop	$s0
	pop	$ra
	end

	li	$v0, 0			#
	jr	$ra			# return 0;

factorial:
	# Args:
	# 	- $a0: int n
	# Returns:
	#	- $v0: int
	# Locals:
	#	- $s0: int n
	#
	# Stack:	[$ra, $s0]
	# Uses:		[$ra, $s0, $v0, $a0]
	# Clobbers:	[$v0, $t0, $a0]
	#
	# Structure:
	# -> main
	#	-> [prologue]
	#	-> [body]
	#		-> n_eq_0
	#	-> [epilogue]
factorial__prologue:
	begin
	push	$ra
	push	$s0

factorial__body:
	move	$s0, $a0

	beqz	$a0, factorial__n_eq_0	# if (n != 0) {

	addi	$a0, $a0, -1
	jal	factorial		#   factorial(n - 1)

	mul	$v0, $v0, $s0		#   return n * factorial(n - 1);
	j	factorial__epilogue	# }

factorial__n_eq_0:
	li	$v0, 1			# return 1;

factorial__epilogue:
	pop	$s0
	pop	$ra
	end

	jr	$ra


	.data
main__result_msg:
	.asciiz	"! = "
function_example.c

A simple example of a program with functions
These functions have no parameters or return values (except for main that returns 0) 
#include <stdio.h>

void f(void);
void g(void);

int main(void){
    printf("I am in the main\n");
    f();
    printf("I am about to return from the main function\n");
    return 0;
}

void f(void){
    printf("I am in the f function\n");
    g();
    printf("I am about to return from f the function\n");
}

void g(void){
    printf("I am in the g function\n");
}
function_example_broken.s

Live coding exercises from recap lecture
A simple example of a program with functions
These functions have no parameters or return values (except for main that returns 0)
This code is broken! 
	.data
msg_main1: 	.asciiz "I am in the main\n"
msg_main2: 	.asciiz "I am about to return from the main function\n"
msg_f1: 	.asciiz "I am in the f function\n"
msg_f2: 	.asciiz "I am about to return from the f function\n"
msg_g1:		.asciiz "I am in the g function\n"

	.text
main:
	li	$v0, 4			#printf("I am in the main");
	la	$a0, msg_main1
	syscall

	jal	f			# f()

	li	$v0, 4			#printf("I am in the main");
	la	$a0, msg_main2
	syscall

	li	$v0, 0			# set return value for main to be 0
	jr	$ra			# return from main to (__start)

f:
	li	$v0, 4			#printf("I am in the f function");
	la	$a0, msg_f1
	syscall

	jal	g			# g()

	li	$v0, 4			#printf("I am in the f function");
	la	$a0, msg_f2
	syscall
	jr	$ra			#return

g:
	li	$v0, 4			#printf("I am in the g function");
	la	$a0, msg_g1
	syscall
	jr	$ra			#return
function_example.s

Live coding exercises from recap lecture
A simple example of a program with functions
These functions have no parameters or return values (except for main that returns 0) 

	.data
msg_main1: 	.asciiz "I am in the main\n"
msg_main2: 	.asciiz "I am about to return from the main function\n"
msg_f1: 	.asciiz "I am in the f function\n"
msg_f2: 	.asciiz "I am about to return from the f function\n"
msg_g1:		.asciiz "I am in the g function\n"

	.text
main:
main__prologue:
	push	$ra
main__body:
	li	$v0, 4			#printf("I am in the main");
	la	$a0, msg_main1
	syscall

	jal	f			# f()

	li	$v0, 4			#printf("I am in the main");
	la	$a0, msg_main2
	syscall

	li	$v0, 0			# set return value for main to be 0
main__epilog:
	pop	$ra
	jr	$ra			# return from main to (__start)

f:
f__prologue:
	push	$ra
f__body:
	li	$v0, 4			#printf("I am in the f function");
	la	$a0, msg_f1
	syscall

	jal	g			# g()

	li	$v0, 4			#printf("I am in the f function");
	la	$a0, msg_f2
	syscall

f__epilog:
	pop	$ra
	jr	$ra			#return

g:
g__prologue:
	push	$ra
g__body:
	li	$v0, 4			#printf("I am in the g function");
	la	$a0, msg_g1
	syscall
g__epilog:
	pop	$ra
	jr	$ra			#return
sum_to.c

An example of a C program with a function with one input and a return value 
#include <stdio.h>

int sum_to(int n);

int main(void) {
    int max = 10;
    int result = sum_to(max);
    printf("Sum 1.. %d = %d\n", max, result);
    return 0;
}

// An iterative solution
int sum_to(int n) {
    int sum = 0;
    int i = 1;
    while (i <= n) {
        sum = sum + i;
        i++;
    }  
    return sum;
}
sum_to.s

A live coding example done as a recap on functions.
This has a simple function with 1 parameter and a return value 
	.data
msg_sum1:
	.asciiz "Sum 1.. "
msg_sum2:
	.asciiz " = "

	.text
main:
	# $s0 used for max since we set it before doing the jal
	# but need it again after the jal
	# If a function uses $s0 that same function must
	# push it to the stack and pop it to restore it later

	# $t0 was used for result since we are not doing another
	# jal after we set its value so we do not need to worry
	# about it getting overwritten by another function
main__prologue:
	push	$ra
	push	$s0
main__body:
	li	$s0, 10			# int max = 10;
	move	$a0, $s0		# int max = 10;
	jal	sum_to			# result = sum_to(max);
	move	$t0, $v0		# $t0 = result

	li	$v0, 4			# printf("Sum 1.. ");
	la	$a0, msg_sum1
	syscall

	li	$v0, 1			# printf("%d",max);
	move	$a0, $s0
	syscall

	li	$v0, 4			# printf(" = ");
	la	$a0, msg_sum2
	syscall

	li	$v0, 1			# printf("%d", result);
	move	$a0, $t0
	syscall

	li	$v0, 11			# putchar('\n')
	li	$a0, '\n'
	syscall

	li	$v0, 0
main__epilog:
	pop	$s0
	pop	$ra
	jr	$ra


sum_to:
sum_to__prologue:
sum_to__body:
	li	$t0, 0			# sum = 0
	li	$t1, 1			# i = 1

sum_to__while:
	bgt	$t1, $a0, sum_to__while_end	# while (i <= n)
	add	$t0, $t0, $t1		# sum = sum + i
	addi	$t1, $t1, 1		# i++
	j	sum_to__while
sum_to__while_end:

	move	$v0, $t0		# return sum
sum_to__epilog:
	jr	$ra
sum_to_r.c

An example of a C program with a recursive function 
#include <stdio.h>

int sum_to(int n);

int main(void) {
    int max = 10;
    int result = sum_to(max);
    printf("Sum 1.. %d = %d\n", max, result);
    return 0;
}

int sum_to(int n) {
   if(n == 0){
       return 0;
   } else {
       int result = sum_to(n-1); 
       return n + result;   
   }
}
sum_to_r.s

A live coding example done as a recap on functions.
This has a recursive function 
	.data
msg_sum1:
	.asciiz "Sum 1.. "
msg_sum2:
	.asciiz " = "

	.text
main:
main__prologue:
	push	$ra
	push	$s0
main__body:
	li	$s0, 10			# int max = 10;
	move	$a0, $s0		# int max = 10;
	jal	sum_to			# result = sum_to(max);
	move	$t0, $v0		# $t0 = result

	li	$v0, 4			# printf("Sum 1.. ");
	la	$a0, msg_sum1
	syscall

	li	$v0, 1			# printf("%d",max);
	move	$a0, $s0
	syscall

	li	$v0, 4			# printf(" = ");
	la	$a0, msg_sum2
	syscall

	li	$v0, 1			# printf("%d", result);
	move	$a0, $t0
	syscall

	li	$v0, 11			# putchar('\n')
	li	$a0, '\n'
	syscall

	li	$v0, 0
main__epilog:
	pop	$s0
	pop	$ra
	jr	$ra


sum_to:
	# We move our input n from $a0 to $s0
	# We need to do this as $a0 will be modified
	# so we need to store n somewhere safe
	# as we need to use it again in the last line of
	# the function.
sum_to__prologue:
	push	$ra
	push	$s0
sum_to__body:
	move	$s0, $a0		# n $s0
sum_to_if:
	bnez	$s0, sum_to_else	# if(n == 0)
	li	$v0, 0			# return 0
	j	sum_to__epilog
sum_to_else:
	sub	$a0, $s0, 1		# n - 1
	jal	sum_to			# int result = sum_to(n-1);
	add	$v0, $v0, $s0
sum_to_if_end:

sum_to__epilog:
	pop	$s0
	pop	$ra
	jr	$ra
class.c 
#include <stdio.h>

struct pizza_t {
    char size[10];      //offset of 0
    int price_cents;    //offset of 10 bytes + 2 bytes of space = 12 bytes
};

struct pizza_t pizza_opts[3] = {
    {"small", 300},
    {"medium", 550},
    {"large", 800}
};

void print_pizza_t(struct pizza_t *pizza) {
    printf("Size: ");
    printf("%s", pizza->size);
    printf(", price: ");
    printf("%d", pizza->price_cents);
    printf(" cents\n");
}

void increase_price(struct pizza_t *pizza, int increase_cents) {
    pizza->price_cents += increase_cents;
}

int main() {
    printf("The available pizza options are:\n");
    int i = 0; 
loop__cond:
    if (i >= 3) goto loop__end;

    struct pizza_t *pizza_opt = &pizza_opts[i];

    increase_price(pizza_opt, 100);
    print_pizza_t(pizza_opt);

    i++;
    goto loop__cond;
loop__end:
    return 0;
}
class.s 
PIZZA_OPT_SIZE_STR_OFFS = 0
PIZZA_OPT_PRICE_CENTS_OFFS = PIZZA_OPT_SIZE_STR_OFFS + 10+2
PIZZA_OPT_SIZE = PIZZA_OPT_PRICE_CENTS_OFFS + 4

	.text
print_pizza_t:				# void print_pizza_t(struct pizza_t *pizza) {
	#argument in $a0 is a pointer to a pizza
	move	$t0, $a0

	la	$a0, size_str
	li	$v0, 4
	syscall				#     printf("Size: ");

	move	$a0, $t0
	addi	$a0, $a0, PIZZA_OPT_SIZE_STR_OFFS
	li	$v0, 4
	syscall				#     printf("%s", pizza->size);

	la	$a0, price_str
	li	$v0, 4
	syscall				#     printf(", price: ");

	lw	$a0, PIZZA_OPT_PRICE_CENTS_OFFS($t0)
	li	$v0, 1
	syscall				#     printf("%d", pizza->price_cents);

	la	$a0, cents_str
	li	$v0, 4
	syscall				#     printf(" cents\n");

	jr	$ra

increase_price:				#void increase_price(struct pizza_t *pizza, int increase_cents)
	#two arguments - $a0 which is the pointer
	#              - $a1 which is the increase_cents

	lw	$t0, PIZZA_OPT_PRICE_CENTS_OFFS($a0)	#load current pizza->price
						     # and we put it in t0
	add	$t0, $t0, $a1
	sw	$t0, PIZZA_OPT_PRICE_CENTS_OFFS($a0)
		#pizza->price_cents += increase_cents;

	jr	$ra

main:					#int main() {
	begin
	push	$ra
	push	$s0

	la	$a0, welcome_str
	li	$v0, 4
	syscall				#printf("The available pizza options are:\n");

	#s0 is being used for int i;
	li	$s0, 0			#int i = 0;

loop__cond:
	bge	$s0, 3, loop__end	#if (i >= 3) goto loop__end;

	la	$t1, pizza_opts		#base address of pizza_opts[0]
	li	$t2, PIZZA_OPT_SIZE	#this is the size of each pizza_opt
	mul	$t2, $s0, $t2		#multiply the size by "i" (our counter)
	add	$t1, $t1, $t2		#add it to get &pizza_opts[i]
    	#struct pizza_t *pizza_opt = &pizza_opts[i];

	move	$a0, $t1
	li	$a1, 100
	jal	increase_price		#increase_price(pizza_opt, 100);

	move	$a0, $t1
	jal	print_pizza_t		#print_pizza_t(pizza_opt);

	addi	$s0, $s0, 1		#i++;
	b	loop__cond		#goto loop__cond
loop__end:
	li	$v0, 0

	pop	$s0
	pop	$ra
	end
	jr	$ra

	.data
size_str:
	.asciiz "Size: "
price_str:
	.asciiz ", price: "
cents_str:
	.asciiz " cents\n"
welcome_str:
	.asciiz "The available pizza options are:\n"

	.align 2
pizza_opts:
	.asciiz "small"			#6 bytes
	.space 4			# + 4 = 10
	.align 2
	.word 300

	.asciiz "medium"		#7 bytes
	.space 3			# + 3 = 10
	.align 2
	.word 550

	.asciiz "large"			#6 bytes
	.space 4			# + 4 = 10
	.align 2
	.word 800

# struct pizza_t pizza_opts[3] = {
#     {"small", 300},
#     {"medium", 550},
#     {"large", 800}
# };