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

## Interface:
##
##   void * allocate_block ( int size_in_bytes );
##
##	Allocates (obtains for computational use) a
##      contiguous block of memory whose size is at
##      least the given size and which starts at a word
##      boundary.  Returns the address of that block.
##
##      Calls sbrk to expand the data segment if
##      necessary.  The block returned contains
##	indeterminant data: it is NOT zeroed.
##
##   void free_block ( void * block );
##
##      Frees (returns for other use) the block with the
##	given address that was obtained by a call to
##	allocate_block.  The memory in this block may
##      then be included in blocks returned by allocate
##      in the future.
##
##   extern unsigned long allocate_minimum_region_size;
##
##      The minimum size region obtained by allocate_
##	block when it calls sbrk.  This region
##	is divided into blocks by the allocator.
##	Defaults to 4096.  Must be an exact multiple
##	of 4 bytes (the word size).
##
##   The current implementation uses the first-fit
##   algorithm.  Alternate implementations are possible.
##
##   extern unsigned long allocate_block_calls;
##   extern unsigned long free_block_calls;
##   extern unsigned long allocate_block_bytes;
##   extern unsigned long free_block_bytes;
##   extern unsigned long currently_used_blocks;
##   extern unsigned long currently_free_blocks;
##   extern unsigned long currently_used_bytes;
##   extern unsigned long currently_free_bytes;
##   extern unsigned long current_number_of_regions;
##
##	Counters of the number of calls to allocate_
##      block, the number of calls to free_block, the
##	actual number of bytes in the blocks returned
##	from all calls to allocate_block (rounded up
##	from the requested sizes), the actual number
##	of bytes in the blocks given to all calls to
##	free_block.  Also the current number of blocks
##	in use, the current number of free blocks
##	(continguous free blocks may be merged), the
##	total number of bytes in currently used blocks,
##	and total number of bytes in currently free
##	blocks, and the total number of current regions.
##	The number of bytes in a block includes
##	bytes for per-block records kept by the
##	allocation system between blocks in memory.
##
##   void allocate_memory_damage
##	    ( void * address1, void * address2 );
##
##	The allocator system keeps records of block
##	lengths between the blocks in memory, and
##	continually checks for damage to these records.
##	If there is damage, this routine is called
##	with two addresses at least one of which
##	usually points at a damaged record.  The user
##	code that writes blocks near these records is
##	probably overwriting the records.  A breakpoint
##	may be set on this routine for debugging.
#

## Internal Data Format (not visible to user):
##
##   region ::= end-point block* end-point
##
##   end-point ::= a word with 0 value
##
##   block ::= free-block | used-block
##
##   free-block ::= length space length
##
##   used-block ::= -length data -length
##
##   length ::= a word containing the length of a block
##
##   -length ::= a word containing the negative of
##               the length of a block
##
##   space ::= word*		data ::= word*
##
##   search-start-block ::= pointer the block to start
##	with when searching for a free block; or at
##	the last end-point.  Not greater than the
##	address of the first free block.
##
##   Block lengths are in bytes and include the length
##   words at each end of a block.  Therefore these
##   lengths are always >= 8 and an exact multiple of 4.
##
##   No two free blocks are adjacent.
##
##   There is only one region.  It is expanded by call-
##   ing sbrk and formatting the space between the ori-
##   ginal region and the new memory as a used block.
##   This used block contains words allocated by other
##   callers to sbrk.
##
##   The current implementation assumes sbrk always
##   returns memory at a higher address than any
##   existing used data memory.
##
##   The current implementation is first fit.  A
##   search-start-block variable is maintained that
##   points at or before the first free block in
##   memory, or points at the last end-point if there
##   is no free block.  The search can always start
##   at this point.  If a block is freed with
##   a lower address, this lower address replaces
##   the search-start-block value.

#

## allocate_block Pseudo-Code:
##
##   (1) Compute the desired block length to be the
##	 given size in bytes rounded up to a multiple
##	 of 4, plus 8 for the two length words.
##
##   (2) While search-start-block is NOT pointing
##	 at a free block as large as the desired
##	 size:
##
##	 (2a) If start-search-block is pointing at the
##	      last end-point of a region, call allocate_
##	      region (see below) to get a new region and
##	      a free block that is large enough.
##
##	 (2a) Check that the block length is a multiple
##	      of 4 and that the length word at the other
##	      end of the block is correct.  If not, call
##	      allocate_memory_damage.
##
##	 (2b) Move search-start-block to the next
##	      block in memory and continue while loop.
##
##   (3) Now we are at a free block that is large
##	 enough.  Check that its length is a multiple
##	 of 4 and the length word at the other end of
##	 the block is correct.  If not, call allocate_
##	 memory_damage.
##
##   (4) If the search-start-block is a free block
##	 whose length is >= the desired length + 8,
##	 then divide this block into a free block
##	 of the desired length followed by another
##	 free block of the remaining length, and
##	 update statistics.  The free block
##	 of the desired length is now pointed at
##	 by the search-start-block.
##
##   (5) Convert the free block pointed at by
##	 search-start-block to a used block,
##       update statistics, and return this
##       block to the caller.

#

## allocate_block Pseudo-Code:
##
##   (1) Add 8 to the desired size to account for
##	 region end points.  The desired size must
##	 be a multiple of 4.
##
##   (2) If the desired size is less than allocate_
##       mininimum_region_size, then replace the
##       desired size with the latter.  Assert
##       that the allocate_region_minimum_size
##       is an exact multiple of 4.
##
##   (3) Call sbrk to get a new region of the desired
##       size.  Initialize this region to contain one
##       free block and two end-points, and update
##	 statistics.
##
##   (4) Assert that the new region has an address
##       higher than the last end-point of the
##       previous region (pointed at by start-search-
##       block).  ) Reset the last end-point of the old
##	 region and the first end-point of the new
##       region to make the space between regions into
##       a used block.  Do NOT count this block in
##       statistics.
##
##   (5) Reset the search-start-block to point at the
##	 free block in the new region.

#

## free_block Pseudo-Code:
##
##   (1) Compute the block length by looking in the
##	 word before the given address.  Assert that
##	 the given address is a multiple of 4.
##
##   (2) Check that the block length is >= 8, an exact
##	 multiple of 4, and equals the length word at
##	 the other end of the block.  If not, call
##	 allocate_memory_damage.
##
##   (3) Negate the length words to mark the block
##	 free and update statistics.
##
##   (4) If the new free block is preceded in memory by
##       a free block, check that free block for damaged
##       lengths, and then merge the free blocks and
##	 update statistics.
##
##   (5) If the new free block is followed in memory by
##       a free block, check that free block for damaged
##       lengths, and then merge the free blocks and
##	 update statistics.
##
##   (6) If the new free block has an address less than
##	 the start-search-block, reset the latter to
##	 point at the new free block.

#

## Global Data:

## int allocate_starter_region [2] = { 0, 0 };
##     // An empty starter region.
##
## int * search_start_block =
##		allocate_starter_region + 1;
##     // Points at block or end-point to start search.
##
## unsigned long allocate_minimum_region_size	= 4096;
## unsigned long allocate_block_calls		= 0;
## unsigned long free_block_calls		= 0;
## unsigned long allocate_block_bytes		= 0;
## unsigned long free_block_bytes		= 0;
## unsigned long currently_used_blocks		= 0;
## unsigned long currently_free_blocks		= 0;
## unsigned long currently_used_bytes		= 0;
## unsigned long currently_free_bytes		= 0;
## unsigned long current_number_of_regions	= 0;
##     // Counters.  Do NOT count starter region.
#
    .data
    .align 2

    .globl allocate_starter_region  # for debugging only
allocate_starter_region:
    .word 0
    .word 0
    .globl search_start_block       # for debugging only
search_start_block:
    .word allocate_starter_region
    .globl allocate_minimum_region_size
allocate_minimum_region_size:
    .word 4096
#
    .globl allocate_block_calls
allocate_block_calls:
    .word 0
    .globl free_block_calls
free_block_calls:
    .word 0
    .globl allocate_block_bytes
allocate_block_bytes:
    .word 0
    .globl free_block_bytes
free_block_bytes:
    .word 0
    .globl currently_used_blocks
currently_used_blocks:
    .word 0
    .globl currently_free_blocks
currently_free_blocks:
    .word 0
    .globl currently_used_bytes
currently_used_bytes:
    .word 0
    .globl currently_free_bytes
currently_free_bytes:
    .word 0
    .globl current_number_of_regions
current_number_of_regions:
    .word 0

    .text

#

## Allocate Region: (called by allocate_block)
##
## Allocate a new region large enough to hold a block
## of the given size.  This size must be a multiple of
## 4 and includes the length words of the block.
##
## void allocate_region ( int size_in_bytes )
## {
##     size_in_bytes += 8;
##     assert
##	 ( ( allocate_minimum_region_size & 3 ) == 0 );
##
##     if ( size_in_bytes
##	    <=
##	    allocate_minimum_region_size )
##	   size_in_bytes = allocate_minimum_region_size;
##
##     int * new_region = sbrk ( size_in_bytes );
##     assert
##	 ( ( (unsigned int) new_region & 3 ) == 0 );
##     
##     int * end_region = (int *)
##	   ( (char *) new_region + size_int_bytes );
##
##     new_region [0]	= end_region [-1]	= 0;
##     new_region [1]	= end_region [-2]	=
##	   			size_in_bytes - 8;
##
##     ++ current_number_of_regions;
##     ++ currently_free_blocks;
##     currently_free_bytes += size_in_bytes - 8;
##
##     assert ( search_start_block < new_region );
##
##     int length_of_fake_used_block =
##	   (char *) new_region + 4
##	   -
##	   (char *) search_start_block;
##
##     search_start_block [0] = new_region [0] =
##		- length_of_fake_used_block;
##
##     search_start_block = new_region + 1;
## }

#

# void allocate_region ( int size_in_bytes )
#
    .globl allocate_region
allocate_region:

    # push $ra, $s1, $s0
    #
    addiu $sp, $sp, -4
    sw $ra, 0($sp)
    addiu $sp, $sp, -4
    sw $s1, 0($sp)
    addiu $sp, $sp, -4
    sw $s0, 0($sp)

    # assign size_in_bytes to $s0
    #
    move $s0, $a0

    # size_in_bytes += 8;
    #
    addi $s0, $s0, 8

    # $t0 = allocate_minimum_region_size;
    #
    lw $t0, allocate_minimum_region_size

    # assert ( ( $t0 & 3 ) == 0 );
    #
    andi $t1, $t0, 3
    beqz $t1, region_1
    break 0
region_1:
#
    # if ( size_in_bytes
    #	   <=
    #	   allocate_minimum_region_size )
    #	  size_in_bytes = allocate_minimum_region_size;
    slt $t1, $t0, $s0
    bnez $t1, region_2
    move $s0, $t0
region_2:

    # int * new_region (assign to $s1) =
    #		sbrk ( size_in_bytes );
    #
    move $a0, $s0
    li $v0, 9
    syscall
    move $s1, $v0

    # assert
    #	 ( ( (unsigned int) new_region & 3 ) == 0 );
    andi $t0, $s1, 3
    beqz $t0, region_3
    break 0
region_3:

    # int * end_region (assign to $t0) = (int *)
    #   ( (char *) new_region + size_int_bytes );
    #
    addu $t0, $s1, $s0

    # $t1 = size_in_bytes - 8
    #
    addi $t1, $s0, -8
#
    # new_region [0]	= end_region [-1]	= 0;
    #
    # new_region [1]	= end_region [-2]	=
    #	   			size_in_bytes - 8;
    sw $0, 0($s1)
    sw $0, -4($t0)
    sw $t1, 4($s1)
    sw $t1, -8($t0)

    # ++ current_number_of_regions;
    # ++ currently_free_blocks;
    # currently_free_bytes += size_in_bytes - 8;
    #
    lw $t2, current_number_of_regions
    lw $t3, currently_free_blocks
    lw $t4, currently_free_bytes
    addiu $t2, $t2, 1
    addiu $t3, $t3, 1
    addu  $t4, $t4, $t1
    sw $t2, current_number_of_regions
    sw $t3, currently_free_blocks
    sw $t4, currently_free_bytes

    # $t1 = search_start_block
    #
    lw $t1, search_start_block

    # assert ( search_start_block < new_region );
    #
    sltu $t2, $t1, $t0
    bnez $t2, region_4
    break 0
region_4:
#
    # int length_of_fake_used_block (assign to $t2) =
    #   (char *) new_region + 4
    #   -
    #   (char *) search_start_block;
    #
    addiu $t2, $s1, 4
    subu  $t2, $t2, $t1

    # search_start_block [0] = new_region [0] =
    #     - length_of_fake_used_block;
    #
    sub $t3, $0, $t2
    sw  $t3, 0($t1)
    sw  $t3, 0($s1)

    # search_start_block = new_region + 1;
    #
    addiu $t3, $s1, 4
    sw    $t3, search_start_block

    # pop $s0, $s1, $ra
    #
    lw $s0, 0($sp)
    addiu $sp, $sp, 4
    lw $s1, 0($sp)
    addiu $sp, $sp, 4
    lw $ra, 0($sp)
    addiu $sp, $sp, 4

    # goto $ra
    #
    jr $ra

#

## Allocate Block:

## void * allocate_block ( int size_in_bytes )
## {
##     size_in_bytes = (size_in_bytes + 3) & (-4);
##     size_in_bytes += 8;
##
##     int * ssb = search_start_block;
##     int * ssb_next;
##     int length;
##
##     while ( ( length = * ssb ) < size_in_bytes )
##     {
##	   // Block is used or too small or end pointer.
##
##	   if ( length == 0)
##	   {
##		// End of region.
##
##		search_start_block = ssb;
##		allocate_region ( size_in_bytes );
##		ssb = search_start_block;
##	   }
##
##	   else
##	   {
##	       // Used block or too small free block.
##
##	       int real_length = length;
##	       if ( real_length < 0 )
##		   real_length = - real_length;
##
##	       ssb_next = (int *)
##		   ( (char *) ssb + real_length );
##
##	       if ( ( length & 3 ) != 0
##		    ||
##		    ssb_next [-1] != length )
##		   allocate_memory_damage
##		       ( ssb, ssb_next - 1 );
##
##	       ssb = ssb_next;
##	   }
##     }
##
##     // Found free block that is long enough.
##     
##     ssb_next = (int *) ( (char *) ssb + length );
##
##     if ( ( length & 3 ) != 0
##	    ||
##	    ssb_next [-1] != length )
##	   allocate_memory_damage ( ssb, ssb_next - 1 );
##
##     if ( length >= size_in_bytes + 8 )
##     {
##	   int * new_block =
##	       (int *) ( (char *) ssb + size_in_bytes );
##
##	   ssb_next [-1] = new_block [0] =
##	       length - size_in_bytes;
##
##	   next_ssb = new_block;
##	   length = size_in_bytes;
##
##	   ++ currently_free_blocks;
##     }
##
##     ssb [0] = ssb_next [-1] = - length;
##
##     -- currently_free_blocks;
##     ++ currently_used_blocks;
##     currently_free_bytes -= length;
##     currently_used_bytes += length;
##
##     ++ allocate_block_calls;
##     allocate_block_bytes += length;
##
##     search_start_block = ssb_next;
##     return ssb + 1;
## }

#

# void * allocate_block ( int size_in_bytes )
#
    .globl allocate_block
allocate_block:

    # push $ra, $s3, $s2, $s1, $s0
    #
    addiu $sp, $sp, -4
    sw $ra, 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)

    # assign size_in_bytes to $s0
    #
    move $s0, $a0

    # size_in_bytes = (size_in_bytes + 3) & (-4);
    # size_in_bytes += 8;
    #
    addi $s0, $s0, 3
    li   $t0, -4
    and  $s0, $s0, $t0
    addi $s0, $s0, 8

    # int * ssb (assign to $s1) = search_start_block;
    # int * ssb_next (assign to $s2);
    # int length (assign to $s3);
    #
    lw $s1, search_start_block
#

allocate_loop:

    # if ( ! ( length = * ssb ) < size_in_bytes )
    #		goto allocate_loop_end
    #
    lw $s3, 0($s1)
    slt $t0, $s3, $s0
    beqz $t0, allocate_loop_end


	# // Block is used or too small or end pointer.

	# if ( ! length == 0) not_end_pointer
	#
	bnez $s3, not_end_pointer

	    # // End of region.

	    # search_start_block = ssb;
	    #	allocate_region ( size_in_bytes );
	    # ssb = search_start_block;
	    #
	    sw $s1, search_start_block
	    move $a0, $s0
	    jal allocate_region
	    lw $s1, search_start_block

	    # goto allocate_loop;
	    #
	    b allocate_loop

	not_end_pointer:
#
	    # // Used block or too small free block.

	    # int real_length (assign to $t0) = length;
	    # if ( real_length < 0 )
	    #	   real_length = - real_length;
	    #
	    move $t0, $s3
	    slt  $t1, $t0, $0
	    beqz $t1, allocate_1
	    sub  $t0, $0, $t0
	allocate_1:

	    # ssb_next = (int *)
	    #    ( (char *) ssb + real_length );
	    #
	    addu $s2, $s1, $t0

	    # if ( ( length & 3 ) != 0
	    #      ||
	    #	   ssb_next [-1] != length )
	    #	  allocate_memory_damage
	    #	       ( ssb, ssb_next - 1 );
	    #
	    andi $t1, $s3, 3
	    bnez $t1, allocate_2
	    lw $t1, -4($s2)
	    beq $t1, $s3, allocate_3
	allocate_2:
	    move $a0, $s1
	    addiu $a1, $s2, -4
	    jal allocate_memory_damage
	allocate_3:

	    # ssb = ssb_next;
	    #
	    move $s1, $s2
#
	    # goto allocate_loop;
	    #
	    b allocate_loop

allocate_loop_end:

    # // Found free block that is long enough.

    # ssb_next = (int *) ( (char *) ssb + length );
    #
    addu $s2, $s1, $s3

    # if ( ( length & 3 ) != 0
    #	   ||
    #	   ssb_next [-1] != length )
    #	 allocate_memory_damage ( ssb, ssb_next - 1 );
    #
    andi $t0, $s3, 3
    bnez $t0, allocate_4
    lw $t0, -4($s2)
    beq $t0, $s3, allocate_5
allocate_4:
    move $a0, $s1
    addu $a1, $s2, -4
    jal allocate_memory_damage
allocate_5:
#
    # if ( ! length >= size_in_bytes + 8 )
    #		goto smaller_length
    #
    addi $t0, $s0, 8
    slt  $t0, $s3, $t0
    bnez $t0, smaller_length

	# int * new_block (assign to $t0) =
	#      (int *) ( (char *) ssb + size_in_bytes );
	#
	addu $t0, $s1, $s0

	# ssb_next [-1] = new_block [0] =
	#       length - size_in_bytes;
	#
	sub $t1, $s3, $s0
	sw  $t1, -4($s2)
	sw  $t1, 0($t0)

	# next_ssb = new_block;
	# length = size_in_bytes;
	#
	move $s2, $t0
	move $s3, $s0

	# ++ currently_free_blocks;
	#
	lw $t0, currently_free_blocks
	addiu $t0, $t0, 1
	sw $t0, currently_free_blocks

    smaller_length:

    # ssb [0] = ssb_next [-1] = - length;
    #
    sub $t0, $0, $s3
    sw  $t0, 0($s1)
    sw  $t0, -4($s2)
#
    # -- currently_free_blocks;
    # ++ currently_used_blocks;
    # currently_free_bytes -= length;
    # currently_used_bytes += length;
    #
    lw $t0, currently_free_blocks
    lw $t1, currently_used_blocks
    lw $t2, currently_free_bytes
    lw $t3, currently_used_bytes
    addiu $t0, $t0, -1
    addiu $t1, $t1, 1
    subu  $t2, $t2, $s0
    addu  $t3, $t3, $s0
    sw $t0, currently_free_blocks
    sw $t1, currently_used_blocks
    sw $t2, currently_free_bytes
    sw $t3, currently_used_bytes

    # ++ allocate_block_calls;
    # allocate_block_bytes += length;
    #
    lw $t0, allocate_block_calls
    lw $t1, allocate_block_bytes
    addiu $t0, $t0, 1
    addu  $t1, $t1, $s0
    sw $t0, allocate_block_calls
    sw $t1, allocate_block_bytes

    # search_start_block = ssb_next;
    # return ssb + 1;
    #
    sw $s2, search_start_block
    addu $v0, $s1, 4
#
    # pop $s0, $s1, $s2, $s3, $ra
    #
    lw $s0, 0($sp)
    addiu $sp, $sp, 4
    lw $s1, 0($sp)
    addiu $sp, $sp, 4
    lw $s2, 0($sp)
    addiu $sp, $sp, 4
    lw $s3, 0($sp)
    addiu $sp, $sp, 4
    lw $ra, 0($sp)
    addiu $sp, $sp, 4

    # return to $ra
    #
    jr $ra

#

## Free Block:

## void free_block ( void * block )
## {
##     assert ( ( (unsigned int) block & 3 ) == 0 );
##     assert ( currently_used_blocks != 0 )
##
##     int * bp = (int *) block - 1;
##     int length = bp [0];
##
##     if ( length > -8 || ( length & 3 ) != 0 )
##	   allocate_memory_damage ( bp, NULL );
##
##     int real_length = - length;
##
##     int * next_bp = (int *)
##	   ( (char *) bp + real_length );
##
##     if ( next_bp [-1] != length )
##	   allocate_memory_damage ( bp, next_bp - 1 );
##
##     bp [0] = next_bp [-1] = real_length;
##
##     -- currently_used_blocks;
##     currently_used_bytes -= real_length;
##     ++ currently_free_blocks;
##     currently_free_bytes += real_length;
##     ++ free_block_calls;
##     free_block_bytes += real_length;
##
##
##     if ( ( length = bp [-1] ) > 0 )
##     {
##	   // Block before this one is free.
##
##	   int * previous_bp =  (int *)
##		( (char *) bp - length );
##
##	   if ( length < 8
##		||
##		( length & 3 ) != 0
##		||
##		previous_bp [0] != length )
##	       allocate_memory_damage
##		   ( previous_bp, bp - 1 );
##
##	   real_length += length;
##	   bp = previous_bp;
##	   bp [0] = next_bp [-1] = real_length;
##	   -- currently_free_blocks;
##     }
##
##     if ( ( length = next_bp [0] ) > 0 )
##     {
##	   // Block after this one is free.
##
##	   int * following_bp =  (int *)
##		( (char *) next_bp + length );
##
##	   if ( length < 8
##              ||
##              ( length & 3 ) != 0
##		||
##		following_bp [-1] != length )
##	       allocate_memory_damage
##	           ( next_bp, following_bp - 1 );
##
##	   real_length += length;
##	   next_bp = following_bp;
##	   bp [0] = next_bp [-1] = real_length;
##	   -- currently_free_blocks;
##     }
##	   
##     if ( search_start_block > bp )
##	   search_start_block = bp;
## }

#

# void free_block ( void * block )
#
    .globl free_block
free_block:

    # push $ra, $s2, $s1, $s0
    #
    addiu $sp, $sp, -4
    sw $ra, 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)

    # assign block to $s0
    #
    move $s0, $a0

    # assert ( ( (unsigned int) block & 3 ) == 0 );
    #
    andi $t0, $s0, 3
    beqz $t0, free_1
    break 0
free_1:

    # assert ( currently_used_blocks != 0 )
    #
    lw $t0, currently_used_blocks
    bnez $t0, free_2
    break 0
free_2:

#
    # int * bp (assign to $s1) = (int *) block - 1;
    # int length (assign to $s2) = bp [0];
    #
    addiu $s1, $s0, -4
    lw $s2, 0($s1)

    # if ( length > -8 || ( length & 3 ) != 0 )
    #       allocate_memory_damage ( bp, NULL );
    #
    slti $t0, $s2, -7
    beqz $t0, free_3
    andi $t0, $s2, 3
    beqz $t0, free_4
free_3:
    move $a0, $s1
    move $a1, $0
    jal allocate_memory_damage
free_4:

    # int real_length (assign to $t0) = - length;
    #
    sub $t0, $0, $s2

    # int * next_bp (assign to $t1) = (int *)
    #	   ( (char *) bp + real_length );
    #
    addu $t1, $s1, $t0

    # if ( next_bp [-1] != length )
    #	   allocate_memory_damage ( bp, next_bp - 1 );
    #
    lw $t2, -4($t1)
    beq $t2, $s2, free_5
    move $a0, $s1
    addiu $a1, $t1, -4
    jal allocate_memory_damage
free_5:

#
    # bp [0] = next_bp [-1] = real_length;
    #
    sw $t0, 0($s1)
    sw $t0, -4($t1)


    # -- currently_used_blocks;
    # currently_used_bytes -= real_length;
    # ++ currently_free_blocks;
    # currently_free_bytes += real_length;
    # ++ free_block_calls;
    # free_block_bytes += real_length;
    #
    lw $t2, currently_used_blocks
    lw $t3, currently_used_bytes
    lw $t4, currently_free_blocks
    lw $t5, currently_free_bytes
    lw $t6, free_block_calls
    lw $t7, free_block_bytes
    addiu $t2, $t2, -1
    subu  $t3, $t3, $t0
    addiu $t4, $t4, 1
    addu  $t5, $t5, $t0
    addiu $t6, $t6, 1
    addu  $t7, $t7, $t0
    sw $t2, currently_used_blocks
    sw $t3, currently_used_bytes
    sw $t4, currently_free_blocks
    sw $t5, currently_free_bytes
    sw $t6, free_block_calls
    sw $t7, free_block_bytes

#
    # if ( ! ( length = bp [-1] ) > 0 )
    #		goto previous_not_free
    #
    lw $s2, -4($s1)
    slt $t2, $0, $s2
    beqz $t2, previous_not_free

	# // Block before this one is free.

	# int * previous_bp (assign to $t2) =  (int *)
	#	( (char *) bp - length );
	#
	subu $t2, $s1, $s2

	# if ( length < 8
	#      ||
	#      ( length & 3 ) != 0
	#      ||
	#      previous_bp [0] != length )
	#     allocate_memory_damage
	#         ( previous_bp, bp - 1 );
	#
	slt $t3, $s2, 8
	bnez $t3, free_6
	andi $t3, $s2, 3
	bnez $t3, free_6
	lw $t3, 0($t2)
	beq $t3, $s2, free_7
    free_6:
	move $a0, $t2
	addiu $a1, $s1, -4
	jal allocate_memory_damage
    free_7:

#
	# real_length += length;
	# bp = previous_bp;
	#
	add $t0, $t0, $s2
	move $s1, $t2


	# bp [0] = next_bp [-1] = real_length;
	#
	sw $t0, 0($s1)
	sw $t0, -4($t1)

	# -- currently_free_blocks;
	#
	lw $t3, currently_free_blocks
	addiu $t3, $t3, -1
	sw $t3, currently_free_blocks

previous_not_free:

    # if ( ! ( length = next_bp [0] ) > 0 )
    #	goto following_not_free
    #
    lw $s2, 0($t1)
    slt $t2, $0, $s2
    beqz $t2, following_not_free

	# // Block after this one is free.

	# int * following_bp (assign to $t2) =  (int *)
	#	( (char *) next_bp + length );
	#
	addu $t2, $t1, $s2

#
	# if ( length < 8
	#      ||
	#      ( length & 3 ) != 0
	#      ||
	#      following_bp [-1] != length )
	#     allocate_memory_damage
	#          ( next_bp, following_bp - 1 );
	#
	slt $t3, $s2, 8
	bnez $t3, free_8
	andi $t3, $s2, 3
	bnez $t3, free_8
	lw $t3, -4($t2)
	beq $t3, $s2, free_9
    free_8:
	move $a0, $t1
	addiu $a1, $t2, -4
	jal allocate_memory_damage
    free_9:

	# real_length += length;
	# next_bp = following_bp;
	#
	add $t0, $t0, $s2
	move $t1, $t2

	# bp [0] = next_bp [-1] = real_length;
	#
	sw $t0, 0($s1)
	sw $t0, -4($t1)

	# -- currently_free_blocks;
	#
	lw $t3, currently_free_blocks
	addiu $t3, $t3, -1
	sw $t3, currently_free_blocks

following_not_free:
#

    # if ( search_start_block > bp )
    #   search_start_block = bp;
    #
    lw $t2, search_start_block
    slt $t3, $s1, $t2
    beqz $t3, free_10
    sw $s1, search_start_block
free_10:

    # pop $s0, $s1, $s2, $ra
    #
    lw $s0, 0($sp)
    addiu $sp, $sp, 4
    lw $s1, 0($sp)
    addiu $sp, $sp, 4
    lw $s2, 0($sp)
    addiu $sp, $sp, 4
    lw $ra, 0($sp)
    addiu $sp, $sp, 4

    # return to $ra
    #
    jr $ra

#

## Memory Damage Routine:
##
## void allocate_memory_damage
##	    ( void * address1, void * address2 )
## {
##     print_string ( "\n\nMEMORY DAMAGE at " );
##     print_int ( address1 );
##     print_string ( " or " );
##     print_int ( address2 );
##     print_string ( "\n\n" );
##     exit ();
## }

# void allocate_memory_damage
#	    ( void * address1, void * address2 )
#
    .globl allocate_memory_damage
allocate_memory_damage:

    # push $ra, $s1, $s0
    #
    addiu $sp, $sp, -4
    sw $ra, 0($sp)
    addiu $sp, $sp, -4
    sw $s1, 0($sp)
    addiu $sp, $sp, -4
    sw $s0, 0($sp)

    # assign address1 to $s0, address2 to #s1
    #
    move $s0, $a0
    move $s1, $a1

#

    # print_string ( "\n\nMEMORY DAMAGE at " );
    #
    .data
damage_1:
    .ascii "\n\nMEMORY DAMAGE at \0"
    .text
    li $v0, 4
    la $a0, damage_1
    syscall

    # print_int ( address1 );
    #
    li $v0, 1
    move $a0, $s0
    syscall

    # print_string ( " or " );
    #
    .data
damage_2:
    .ascii " or \0"
    .text
    li $v0, 4
    la $a0, damage_2
    syscall

    # print_int ( address2 );
    #
    li $v0, 1
    move $a0, $s1
    syscall

#

    # print_string ( "\n\n" );
    #
    .data
damage_3:
    .ascii "\n\n\0"
    .text
    li $v0, 4
    la $a0, damage_3
    syscall

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