/*
	This C language subroutine provides heap memory
	management for the runtime library.
	
	The Run Time Library for the C Language.

	Gordon A. Sterling	(617) 461 - 3076
	DSP Development Tools Engineering

	Created on 12/9/90
	Updated on 5/94 by AS

	#include <stdlib.h>				    <Header>
	void *malloc(size_t size);			    <Prototype>
	void *calloc(int nmemb, size_t size);		    <Prototype>
*/

#include "lib_glob.h"
#include "sdl_glob.h"

.SEGMENT/CODE	Code_Space_Name;
.FILE 		RTL_FILENAME;

.GLOBAL	    	_malloc, _calloc;

_malloc:	put(R14);
		put(R3);
		put(R5);
		put(R6);
		put(R7);
		put(R9);
		put(R10);
		put(R11);
		
		CALL (PC, ___lib_get_heap_info) (DB);	/*Read heap information*/
		R2=PASS R4, put(R13);
		put(R15);

malloc_core:	R0=PASS R2, R8=R5;			/*Test for zero input, hold #*/
		IF EQ JUMP (PC, restore_state);		/*Return NULL ptr*/

		R3=PASS R3;				/*Test for DM/PM alloc*/
		IF GT JUMP (PC, pm_allocation) (DB);	/*Allocated from PM*/
		dm_lnt=0;				/*Clear length registers*/
		pm_lnt=0;				/* for DM and PM*/

/*  The memory allocation functions work by examining a heap memory space
    for an unallocated area that meets the minium requirements.  There can 
    be many seperate heap spaces, and the pointers are adjusted by other
    routines. */

/*  There is one control block per heap structured as follows:
	| 0 | |First_Blk_Ptr| */

/*  Each heap space is structured in blocks, as follows:
	    
blk1:	|block_size| |next_block_pointer| | - - memory block - - |	*/

/*  Begin by examining the heap space for free area.  When this loop completes
    R15 --> previous block, R3 --> current block, R0 --> Next block
    R14 holds block length, R2 holds desired length */

dm_allocation:	R0=PASS R4, dm_ptr=R4;
		IF EQ JUMP (PC, restore_state);		/*No memory available*/
		R3=PASS R0, R14=DM(dm_ptr,1);		/*Fetch length, Load R3*/
		DO scan_free UNTIL EQ;			/*NEVER EXITS!*/
		   R4=R14-R2, R0=DM(dm_ptr,0);		/*Fetch address of next*/
		   IF GE JUMP (PC, dm_block_found) (LA); /*Found one!*/
		   R0=PASS R0, dm_ptr=R0;		/*Test for end of list*/
		   IF EQ JUMP (PC, restore_state) (LA);	/*Return with NULL*/
		   R15=PASS R3, R3=R0;			/*Hold previous pointers*/
scan_free:	   R14=DM(dm_ptr,1);			/*Fetch length*/

dm_block_found:	R5=3;					/*Must be at least 3*/
		R5=R4-R5;				/*Test for almost same size*/
		IF GT JUMP (PC, fragment_block);	/* if not, split block*/

same_size:	R15=PASS R15, dm_ptr=R15;		/*Set pointer to previous*/
		IF NE DM(1,dm_ptr)=R0;			/*Point to next block*/
		R0=R3+1, dm_ptr=R3;			/*Point to allocated space*/
		JUMP (PC, restore_state) (DB);		/*Return*/
		R0=R0+1, DM(dm_1, dm_ptr)=R8;		/*Set heap # in header*/
		NOP;
				
fragment_block: R4=R4-1, dm_ptr=R3;			/*Point to current block*/
		R4=R4-1;				/*Decrement space left by 2*/
		R5=R14+R3, DM(dm_ptr,dm_0)=R4;		/*Write out new length in current blk*/
		R0=R5-R2;				/*Subtract allocated space*/
		R0=R0+1;				/*Increment pointer of length*/
		R0=R0+1, dm_ptr=R0;			/*Point to new header*/
		JUMP (PC, restore_state) (DB);		/*Return with ptr*/
		DM(dm_M1,dm_ptr)=R2;			/*Set length in header*/
		DM(dm_0, dm_ptr)=R8;			/*Set heap number in header*/

pm_allocation:	R0=PASS R4, pm_ptr=R4;
		IF EQ JUMP (PC, restore_state);		/*No memory available*/
		R3=PASS R0, R14=PM(pm_ptr,1);		/*Fetch length, Load R3*/
		DO scan_free_pm UNTIL EQ;		/*NEVER EXITS!*/
		   R4=R14-R2, R0=PM(pm_ptr,0);		/*Fetch address of next*/
		   IF GE JUMP (PC, pm_block_found) (LA); /*Found one!*/
		   R0=PASS R0, pm_ptr=R0;		/*Test for end of list*/
		   IF EQ JUMP (PC, restore_state) (LA);	/*Return with NULL*/
		   R15=PASS R3, R3=R0;			/*Hold previous pointers*/
scan_free_pm:	   R14=PM(pm_ptr,1);			/*Fetch length*/

pm_block_found:	R5=3;					/*Must be at least one*/
		R5=R4-R5;				/*Test for almost same size*/
		IF GT JUMP (PC, fragment_pm_blk);	/* if not, split block*/

pm_same_size:	R15=PASS R15, pm_ptr=R15;		/*Set pointer to previous*/
		IF NE PM(1,pm_ptr)=R0;			/*Point to next block*/
		R0=R3+1, pm_ptr=R3;			/*Point to allocated space*/
		JUMP (PC, restore_state) (DB);		/*Return*/
		R0=R0+1, PM(pm_1, pm_ptr)=R8;		/*Set heap number in header*/
		NOP;

fragment_pm_blk:R4=R4-1, pm_ptr=R3;			/*Point to current block*/
		R4=R4-1;
		R5=R14+R3, PM(pm_ptr,pm_0)=R4;		/*Plus one for addres*/
		R0=R5-R2;				/*Subtract allocated space*/
		R0=R0+1;
		R0=R0+1, pm_ptr=R0;			/*Point to new header*/
		JUMP (PC, restore_state) (DB);		/*Return home*/
		PM(pm_M1,pm_ptr)=R2;			/*Set length in header*/
		PM(pm_0, pm_ptr)=R8;			/*Set heap number in pointer*/

restore_state:	FETCH_RETURN
		get(R15,1);
		get(R13,2);
		get(R11,3);
		get(R10,4);
		get(R9,5);
		get(R7,6);
		get(R6,7);
		get(R5,8);
		get(R3,9);
		get(R14,10);
		RETURN (DB);
		RESTORE_STACK
		RESTORE_FRAME

_calloc:	R2=PASS R4, put(R14);
		R14=PASS R8, put(R3);
		put(R5);
		put(R6);
		put(R7);
		put(R9);
		put(R10);
		put(R11);
		R11=R2*R14 (SUI), put(R13);		/*Compute length for malloc*/
		put(R15);

		CALL (PC, ___lib_get_heap_info) (DB);	/*Read heap info*/
		R7=clr_dm;
		R6=clr_pm;

		R3=PASS R3, R4=R11;			/*Test for DM/PM alloc*/
		IF GT R7=PASS R6;			/*GT means PM	*/

		CALLER_HOLD(R2)
		CALLER_SWAP
		RTLCALL (PC, _malloc) (DB);
		SAVE_OLD_FRAME(R2)
		SAVE_RET_ADDR

		pm_ptr=R7;
		R0=PASS R0, pm_lnt=pm_0;
		IF EQ JUMP (PC, restore_state);

		JUMP (pm_0,pm_ptr) (DB);
		R2=0;
		NOP;

clr_dm:		dm_ptr=R0;
		LCNTR=R11, DO clear_dm UNTIL LCE;
clear_dm:	    DM(dm_ptr,dm_1)=R2;
		JUMP (PC, restore_state);
		
clr_pm:		pm_ptr=R0;
		LCNTR=R11, DO clear_pm UNTIL LCE;
clear_pm:	    PM(pm_ptr,pm_1)=R2;
		JUMP (PC, restore_state);
		
.ENDSEG;