#### Memory Allocator Test
####
#### File:         memory_allocator_test.asm
#### Author:       CS 51 (Bob Walton)
#### Version:      1

## void main ()
## {
##     static int * block [128];
##
##     int i; for ( i = 0; i < 1000; ++ i )
##     {
##         int j = random () % 128;
##	   int * bp = block[j];
##
##	   if ( bp == NULL )
##	   {
##	        int k = random () % 4;
##		int size = ( ( random () % 16 ) + 1 )
##					<< (k + 2);
##		bp = (int *)
##		    allocate_block ( 4 * size );
##
##		block [j] = bp;
##		bp [0] = j;
##		bp [1] = size - 1;
##		bp [size - 1] = j;
##         }
##	   else
##	   {
##		assert ( bp [0] == j
##		         &&
##			 bp [bp [1]] == j );
##		free_block ( bp );
##		block [j] = NULL;
##	   }
##     }
## }
#

# void main ()
#
    .globl main
main:

    # push $ra, $s6, $s5, $s4, $s3, $s2, $s1, $s0
    #
    addiu $sp, $sp, -4
    sw $ra, 0($sp)
    addiu $sp, $sp, -4
    sw $s6, 0($sp)
    addiu $sp, $sp, -4
    sw $s5, 0($sp)
    addiu $sp, $sp, -4
    sw $s4, 0($sp)
    addiu $sp, $sp, -4
    sw $s3, 0($sp)
    addiu $sp, $sp, -4
    sw $s2, 0($sp)
    addiu $sp, $sp, -4
    sw $s1, 0($sp)
    addiu $sp, $sp, -4
    sw $s0, 0($sp)

#
    # static int * block [128];
    #
    .data
    .globl block  # for debugging only
    .align 2
block:
    .word 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
    .word 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
    .word 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
    .word 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
    .word 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
    .word 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
    .word 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
    .word 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
    .text

    # int i (assign to $s0);
    # for ( i = 0; i < 1000; ++ i )
    #
    li $s0, 0
    b main_1
for_loop:
    add $s0, $s0, 1
main_1:
    slti $t0, $s0, 1000
    beqz $t0, for_loop_end

	# int j (assign to $s1) = random () % 128;
	# $s2 = &block[j];
	# int * bp (assign to $s3) = block[j];
	#
	jal random
	andi $s1, $v0, 127
	add  $t0, $s1, $s1
	add  $t0, $t0, $t0
	la   $t1, block
	addu $s2, $t0, $t1
	lw   $s3, 0($s2)
#
	# if ( ! bp == NULL ) goto free
	#
	bnez $s3, not_free

	    # int k (assign to $s4) = random () % 4;
	    #
	    jal random
	    andi $s4, $v0, 3

	    # int size (assign to $s5) =
	    #	( ( random () % 16 ) + 1 )<< (k + 2);
	    #
	    jal random
	    andi $s5, $v0, 15
	    addi $s5, $s5, 1
	    addi $t0, $s4, 2
	main_2:
	    beqz $t0, main_3
	    add $s5, $s5, $s5
	    addi $t0, $t0, -1
	    b main_2
	main_3:

	    # s6 = 4 * size;
	    add $s6, $s5, $s5
	    add $s6, $s6, $s6

	    # bp = (int *) allocate_block ( 4 * size );
	    #
	    move $a0, $s6
	    jal allocate_block
	    move $s3, $v0
#
	    # block [j] = bp;
	    # bp [0] = j;
	    # bp [1] = size - 1;
	    # bp [size - 1] = j;
	    sw $s3, 0($s2)
	    sw $s1, 0($s3)
	    addi $t0, $s5, -1
	    sw $t0, 4($s3)
	    addu $t0, $s3, $s6
	    sw $s1, -4($t0)

	    # goto for_loop 
	    #
	    b for_loop

	not_free:

	    # assert ( bp [0] == j
	    #          &&
	    #          bp [bp [1]] == j );
	    #
	    lw $t0, 0($s3)
	    bne $t0, $s1, main_4
	    lw $t0, 4($s3)
	    add $t0, $t0, $t0
	    add $t0, $t0, $t0
	    addu $t0, $t0, $s3
	    lw $t1, 0($t0)
	    beq $t1, $s1, main_5
	main_4:
	    break 0
	main_5:
#
	    # free_block ( bp );
	    #
	    move $a0, $s3
	    jal free_block

	    # block [j] = NULL;
	    #
	    sw $0, 0($s2)

	    # goto for_loop
	    #
	    b for_loop


for_loop_end:

    # exit ();
    #
    li $v0, 10
    syscall

#

## RR: random () ===> seed after setting
##	  seed = ( seed * ( 7**5 ) ) mod ( 2**31 - 1 )
##
##     seed is an integer static variable
##	    intialized to 1
##
##     7**5 = 16807

## Pseudo C-Code:
##
## int random ()
## {
##   static unsigned int seed = 1;
##
##   unsigned 64-bit int hilo = seed * 16807;
##
##   unsigned int result = hilo low order 32 bits;
##
##   if (result >= 2**31 - 1)
##	    result = result - ( 2**31 - 1 );
##
##   result = result + 2 * hilo high order 32 bits;
##
##   while (result >= 2**31 - 1)
##	    result = result - ( 2**31 - 1 );
##
##   seed = result;
##   return result;
## }

#

## Pseudo C-Code with Register Assignment and Gotos:
##
## int random ( )
## {
##   static unsigned int seed = 1;
##
##   $hi$lo = seed * 16807;
##   $v0    = $lo;
##   if ( ! $v0 >= 0x7fffffff ) goto v0_lt_7fffffff
##       $v0 = $v0 - 0x7fffffff;
## v0_lt_7fffffff:
##
##   $v0    = $v0 + $hi * 2;
##
## random_loop:
##   if ( ! $v0 >== 0x7fffffff ) goto v0_lt_7fffffff_2
##       $v0 = $v0 - 0x7fffffff;
##       goto random_loop;
##
## v0_lt_7fffffff_2:
##   seed = $v0;
##   goto $ra;
## }

#

    .globl random
random:

    #   static unsigned int seed = 1;
    #
    .data
    .globl seed
    .align 2  # Must align before following label.
seed:
    .word 1
    .text

    #   $hi$lo = seed * 16807;
    #
    lw $t0, seed
    li $t1, 16807
    multu $t0, $t1

    #   $v0    = $lo;
    #
    mflo $v0

    #   if ( ! $v0 >= 0x7fffffff ) goto v0_lt_7fffffff
    #
    li   $t2, 0x7fffffff
    sltu $t3, $v0, $t2
    bnez $t3, v0_lt_7fffffff

    #       $v0 = $v0 - 0x7fffffff;
    #
    subu $v0, $v0, $t2

#

v0_lt_7fffffff:

    #   $v0    = $v0 + $hi * 2;
    #
    mfhi  $t0
    addu  $t0, $t0, $t0
    addu  $v0, $v0, $t0

random_loop:

    #   if ( ! $v0 >= 0x7fffffff ) goto v0_lt_7fffffff_2
    #
    li   $t2, 0x7fffffff
    sltu $t3, $v0, $t2
    bnez $t3, v0_lt_7fffffff_2

    #       $v0 = $v0 - 0x7fffffff;
    #
    subu $v0, $v0, $t2

    #       goto random_loop;
    #
    b random_loop

v0_lt_7fffffff_2:

    # seed = $v0;
    #
    sw $v0, seed

    # goto $ra;
    #
    jr $ra