#
#   malloc.zasm  --  zasm routines for memory allocation
#   Copyright (C) 1998  Matt Kimball
#
#   Permission is hereby granted, free of charge, to any person
#   obtaining a copy of this software and associated documentation
#   files (the "Software"), to deal in the Software without
#   restriction, including without limitation the rights to use, copy,
#   modify, merge, publish, distribute, sublicense, and/or sell copies
#   of the Software, and to permit persons to whom the Software is
#   furnished to do so, subject to the following condition:
#
#   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
#   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
#   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
#   NONINFRINGEMENT.  IN NO EVENT SHALL MATT KIMBALL BE LIABLE FOR ANY
#   CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
#   CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
#   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
#

#
#  Allocate a particular amount of memory
#
#  Called with the size, in bytes, of the memory to allocate.  The routine
#  will return a byte address of the newly allocated memory, or 0 if
#  there is insufficient memory to allocate
#
routine malloc 5
	loadw 0x40 0 $2		#  Load the total heap size
	je $2 0	@_malloc_already_initialized	#  If it is zero, we have
						#    already initialized it
	call_1n :_malloc_initialize

label _malloc_already_initialized
	and $1 1 $2		    #  Is the low size bit set?
	jz $2 @_malloc_rounded_up
	add $1 1 $1		    #  If not, round up to the next word

label _malloc_rounded_up
	add $1 2 $1		    #  We need to have size for the header
	log_shift $1 -1 $1	    #  Store the number of words required
				    #    for our block
	store 3 0x42		    #  Start at the first heap block

label _malloc_main_loop
	call_2n :_malloc_consolidate $3
	loadw $3 0 $2
	jz $2 @rfalse		    #  Is this the end of the heap?
	jl $2 $1 @_malloc_next_block

	je $2 $1 @_malloc_block_split
	log_shift $1 1 $4
	add $4 $3 $4
	sub $2 $1 $5
	storew $4 0 $5

label _malloc_block_split
	or $1 0x8000 $1		    #  Mark this block as used
	storew $3 0 $1

       	add $3 2 $3		    #  Return the address after the header
	ret $3

label _malloc_next_block
	and $2 0x7FFF $2	    #  Mask off the allocated bit
	log_shift $2 1 $2	    #  Convert from words to bytes
	add $3 $2 $3		    #  Add the block size to our offset
				    #    in the heap
	jump @_malloc_main_loop
	
# 
#  Free a previously allocated chunk of memory.  This routine is 
#  called with the address of the memory to free.
#
routine free 2
	sub $1 2 $1		#  Move to the block header
	loadw $1 0 $2		#  Load it 
	and $2 0x7FFF $2	#  Mark it as unused
	storew $1 0 $2		#  Store it
	ret 0

#
#  Initialize the heap structure for malloc/free
#
routine _malloc_initialize 2
	loadw 0x40 0 $1		#  Load the total heap size

       	sub $1 4 $1		#  Subtract the size of the header and
				#    last heap stub
	log_shift $1 -1 $1	#  Convert to words

	storew 0x42 0 $1	#  Store it in the first block
	storew 0x40 0 0 	#  Mark that we have initialized the heap
	ret 0

#
#  Consolidate the block pointed at will all following free blocks
#
routine _malloc_consolidate 4
	loadw $1 0 $2		#  Load the header of this block
	jl! 0 $2 @rfalse	#  Return if this isn't a free block

label _malloc_consolidate_loop
	log_shift $2 1 $3	#  Get the address of the next block
	add $3 $1 $3
	loadw $3 0 $4		#  Load its header
	jl! 0 $4 @rfalse	#  Return if this isn't a free block

	add $4 $2 $2		#  Combine these two blocks
	storew $1 0 $2
	jump @_malloc_consolidate_loop