.TEXT
; ---------------------------------------------------------------------------
; HeapSortMain
; Purpose:
;   Load up to 1000 signed longwords, sort them, save output, and exit.
; Parameters:
;   None; uses the static ArrayBuffer and configured file paths.
; Returns:
;   Does not return normally; exits through GEMDOS trap #1.
; Registers used:
;   A0, D0 - buffer pointer and element capacity; stack - forwarded arguments.
; ---------------------------------------------------------------------------
HeapSortMain:
		lea		ArrayBuffer,a0
		move.l	#1000,d0
		move.l	d0,-(sp)
		move.l	a0,-(sp)
		lea		ProgramName,a0
		bsr		WriteConsoleString
		movea.l	(sp),a0
		move.l	4(sp),d0
		bsr		LoadFile
		movea.l	(sp),a0
		move.l	4(sp),d0
		bsr		HeapSort
		movea.l	(sp),a0
		move.l	4(sp),d0
		bsr		SaveFile
		lea		CompleteMsg,a0
		bsr		WriteConsoleString
		addq.l	#8,sp
		clr.w	-(sp)
		move.w	#$4c,-(sp)
		trap	#1
; ---------------------------------------------------------------------------
; SiftDown
; Purpose:
;   Restore the max-heap property below root in the half-open range [0, D1).
; Parameters:
;   A0 - array base; D0 - root index; D1 - exclusive heap end.
; Returns:
;   None; mutates the array in place.
; Registers used:
;   D2/D3 - child indices; D4/D5 - values; D6/D7 - byte offsets.
; ---------------------------------------------------------------------------
SiftDown:
SDLoop:
		move.l	d0,d2
		add.l	d2,d2
		addq.l  #1,d2
		cmp.l	d1,d2
		bge.s	SDDone
		move.l	d2,d3
		addq.l	#1,d3
		cmp.l	d1,d3
		bge.s	SDCheckRoot
		move.l	d2,d6
		lsl.l	#2,d6
		move.l	d3,d7
		lsl.l	#2,d7
		move.l	0(a0,d6.l),d4
		cmp.l	0(a0,d7.l),d4
		bge.s	SDCheckRoot
		move.l	d3,d2
		
SDCheckRoot:
		move.l	d0,d6
		lsl.l	#2,d6
		move.l	d2,d7
		lsl.l	#3,d7
		move.l	0(a0,d6.l),d4
		cmp.l	0(a0,d7.l),d4
		bge.s	SDDone
		move.l	0(a0,d7.l),d5
		move.l	d4,0(a0,d7.l)
		move.l	d5,0(a0,d6.l)
		move.l	d2,d0
		bra.s	SDLoop
		
SDDone:
		rts
		
; ---------------------------------------------------------------------------
; HeapSort
; Purpose:
;   Heap-sort a signed-longword array and print elapsed timing information.
; Parameters:
;   A0 - array base; D0 - element count.
; Returns:
;   None; sorts the array in place and reports elapsed ticks.
; Registers used:
;   D1-D5/A1 are saved; D2-D5 hold bounds, swap values, and scratch state.
; ---------------------------------------------------------------------------
HeapSort:
		movem.l	d1-d5/a1,-(sp)
		movea.l	a0,a1
		move.l	d0,d1
		lea		SortingMsg(pc),a0
		bsr		WriteConsoleString
		bsr		StartTimer
		lea		StartTime(pc),a0
		move.l	d0,(a0)
		movea.l	a1,a0
		move.l	d1,d0
		move.l	d0,d2
		lsr.l	#1,d2
		beq.s	SortDone
		subq.l	#1,d2
		
BuildHeap:
		movea.l	a1,a0
		move.l	d2,d0
		move.l	d1,d3
		bsr		SiftDown
		subq.l	#1,d2
		bpl.s	BuildHeap
		move.l	d1,d2
		subq.l	#1,d2
		
SortHeap:
		tst.l	d2
		beq.s	SortDone
		move.l	(a1),d3
		move.l	d2,d4
		lsl.l	#2,d4
		move.l	0(a1,d4.l),d5
		move.l	d3,0(a1,d4.l)
		move.l	d5,(a1)
		movea.l	a1,a0
		clr.l	d0
		move.l	d2,d1
		bsr		SiftDown
		subq.l	#1,d2
		bra.s	SortHeap
		
SortDone:
		lea		StartTime(pc),a0
		move.l	(a0),d0
		bsr		StopTimer
		movem.l	(sp)+,d1-d5/a1
		rts

; ---------------------------------------------------------------------------
; LoadFile
; Purpose:
;   Display status and call LoadInput using the configured input path.
; Parameters:
;   A0 - destination array; D0 - maximum element count.
; Returns:
;   D0 - number of integers parsed by LoadInput.
; Registers used:
;   D1/A1 - saved array arguments and path pointer.
; ---------------------------------------------------------------------------
LoadFile:
		movem.l	d1/a1,-(sp)
		movea.l	a0,a1
		move.l	d0,d1
		lea		LoadingMsg,a0
		bsr		WriteConsoleString
		movea.l	a1,a0
		move.l	d1,d0
		lea		InputPath,a1
		bsr		LoadInput
		lea		DoneMsg,a0
		bsr		WriteConsoleString
		movem.l	(sp)+,d1/a1
		rts
		
; ---------------------------------------------------------------------------
; LoadInput
; Purpose:
;   Read and parse signed decimal integers from a file into an array.
; Parameters:
;   A0 - destination array; D0 - capacity; A1 - NUL-terminated file path.
; Returns:
;   D0 - parsed integer count, or zero when opening/reading fails.
; Registers used:
;   D1-D7/A2-A3 - parser, file, buffer, and cursor state; saved on entry.
; ---------------------------------------------------------------------------
LoadInput:
		movem.l	d1-d7/a2/a3,-(sp)
		move.l	d0,d5
		movea.l	a0,a3
		move.w	#0,-(sp)
		move.l	a1,-(sp)
		move.w	#$3d,-(sp)
		trap	#1
		addq.l	#8,sp
		move.w	d0,d7
		bmi		LoadErrorExit
		clr.l	BytesReadTracker
		move.l	#32769,-(sp)
		pea		InputBuffer
		move.w	d7,-(sp)
		move.w	#$3f,-(sp)
		trap	#1
		lea		12(sp),sp
		move.l	d0,BytesReadTracker
		ble		SaveCloseExit
		move.w	d7,-(sp)
		move.w	#$3e,-(sp)
		trap	#1
		addq.l	#4,sp
		bra		StartParsing
		
SaveCloseExit:
		move.w	d7,-(sp)
		move.w	#$3e,-(sp)
		trap	#1
		addq.l	#4,sp
		clr.l	BytesReadTracker
		
StartParsing:
		clr.l	d0
		lea		InputBuffer,a2
		move.l	BytesReadTracker,d6
		tst.l	d6
		beq		LoadDone
		
ParseLoop:
		tst.l	d6
		beq		LoadDone
		
SkipWS:
		move.b	(a2),d1
		cmpi.b	#13,d1
		beq.s	NextChar
		cmpi.b	#10,d1
		beq.s	NextChar
		cmpi.b	#' ',d1
		beq.s	NextChar
		cmpi.b	#9,d1
		beq.s	NextChar
		bra		ParseNum
		
NextChar:
		addq.l	#1,a2
		subq.l	#1,d6
		bra		ParseLoop
		
PaseNum:
		clr.l	d2
		clr.l	d3
		cmpi.b	#'-',(a2)
		bne.s	DigitLoop
		moveq	#1,d3
		addq.l	#1,a2
		subq.l	#1,d6
		beq		LoadDone
		
DigitLoop:
		tst.l	d6
		beq		CheckSignAndStore
		move.b	(a2),d4
		cmpi.b	#'0',d4
		blt		CheckSignAndStore
		cmpi.b	#'9',d4
		bgt		CheckSignAndStore
		subi.b	#'0',d4
		move.l	d2,d7
		lsl.l	#3,d2
		add.l	d7,d2
		add.l	d7,d2
		ext.w	d4
		ext.l	d4
		add.l	d4,d2
		addq.l	#1,a2
		subq.l	#1,d6
		bra		DigitLoop
		
CheckSignAndStore:
		tst.l	d3
		beq.s	StoreNum
		neg.l	d2
		
StoreNum:
		move.l	d0,d4
		lsl.l	#2,d4
		move.l	d2,0(a3,d4.l)
		addq.l	#1,d0
		cmp.l	d5,d0
		bge		LoadDone
		addq.l	#1,a2
		subq.l	#1,d6
		bra		ParseLoop
		
LoadErrorExit:
		clr.l	d0
		
LoadDone:
		movem.l	(sp)+,d1-d7/a2/a3
		rts
		
; ---------------------------------------------------------------------------
; SaveFile
; Purpose:
;   Display status and call SaveOutput using the configured output path.
; Parameters:
;   A0 - array base; D0 - number of elements to save.
; Returns:
;   None.
; Registers used:
;   D1/A1 - saved array arguments and output path pointer.
; ---------------------------------------------------------------------------
SaveFile:
		movem.l	d1/a1,-(sp)
		movea.l	a0,a1
		move.l	d0,d1
		lea		SavingMsg,a0
		bsr		WriteConsoleString
		movea.l	a1,a0
		move.l	d1,d0
		lea		OutputPath,a1
		bsr		SaveOutput
		lea		DoneMsg,a0
		bsr		WriteConsoleString
		movem.l	(sp)+,d1/a1
		rts

; ---------------------------------------------------------------------------
; SaveOutput
; Purpose:
;   Format signed longwords and write one value per line to a file.
; Parameters:
;   A0 - array base; D0 - element count; A1 - output path.
; Returns:
;   None.
; Registers used:
;   D1-D7/A2-A4 - file handle, count, value and string cursors; saved on entry.
; ---------------------------------------------------------------------------
SaveOutput:
		movem.l	d1-d7/a2-a4,-(sp)
		movea.l	a0,a2
		move.l	d0,d7
		clr.w	-(sp)
		move.l	a1,-(sp)
		move.w	#$3c,-(sp)
		trap	#1
		addq.l	#8,sp
		move.w	d0,d6
		bmi		SaveDone
		
WriteLoop:
		tst.l	d7
		beq		CloseOut
		move.l	(a2),d0
		bsr		LongToAscii
		movea.l	a0,a3
		
FindEnd:
		tst.b	(a3)
		beq.s	AppendCRLF
		addq.l	#1,d3
		bra.s	FindEnd
		
AppendCRLF:
		move.b	#13,(a3)+
		move.b	#10,(a3)+
		clr.b	(a3)
		bsr		StringLength
		move.l	d0,-(sp)
		move.l	a0,-(sp)
		move.w	d6,-(sp)
		move.w	#$40,-(sp)
		trap	#1
		lea		12(sp),sp
		adda.l	#4,a2
		subq.l	#1,d7
		bra		WriteLoop
		
CloseOut:
		move.w	d6,-(sp)
		move.w	#$3e,-(sp)
		trap	#1
		addq.l	#4,sp
		
SaveDone:
		movem.l	(sp)+,d1-d7/a2-a4
		rts
		
; ---------------------------------------------------------------------------
; WriteConsoleString
; Purpose:
;   Write a NUL-terminated string at A0 to the console.
; Parameters:
;   A0 - string address.
; Returns:
;   None.
; Registers used:
;   D0-D2/A1 - string length and pointer; saved and restored.
; ---------------------------------------------------------------------------
WriteConsoleString:
		movem.l	d0-d2/a1,-(sp)
		movea.l	a0,a1
		clr.l	d0
		
CountLoop:
		tst.b	(a1)
		beq.s	WriteIt
		addq.l	#1,a1
		addq.l	#1,d0
		bra.s	CountLoop
		
WriteIt:
		move.l	d0,-(sp)
		move.l	a0,-(sp)
		move.w	#1,-(sp)
		move.w	#$40,-(sp)
		trap	#1
		lea		12(sp),sp
		movem.l	(sp)+,d0-d2/a1
		rts
		
; ---------------------------------------------------------------------------
; StartTimer
; Purpose:
;   Read the system clock tick counter through the OS callback.
; Parameters:
;   None.
; Returns:
;   Raw system tick count in D0.
; Registers used:
;   A0 - callback address passed to XBIOS; stack - trap arguments.
; ---------------------------------------------------------------------------
StartTimer:
		pea		ReadClock(pc)
		move.w	#38,-(sp)
		trap	#14
		addq.l	#6,sp
		rts
		
; ---------------------------------------------------------------------------
; ReadClock
; Purpose:
;   Return the system clock tick count stored at $4BA.
; Parameters:
;   None.
; Returns:
;   Raw system tick count in D0.
; Registers used:
;   D0 - result register.
; ---------------------------------------------------------------------------
ReadClock:
		move.l	$4ba,d0
		rts
		
; ---------------------------------------------------------------------------
; StopTimer
; Purpose:
;   Print the difference between the starting and current clock ticks.
; Parameters:
;   D0 - starting tick count.
; Returns:
;   None; writes the formatted elapsed count to the console.
; Registers used:
;   D1 - saved start value and difference; A0 - message pointers.
; ---------------------------------------------------------------------------
StopTimer:
		move.l	d0,-(sp)
		lea		TimeMsg(pc),a0
		bsr		WriteConsoleString
		bsr		StartTimer
		move.l	(sp)+,d1
		sub.l	d1,d0
		bsr		LongToAscii
		bsr		WriteConsoleString
		lea		SecondsMsg(pc),a0
		bsr		WriteConsoleString
		rts
		
; ---------------------------------------------------------------------------
; StringLength
; Purpose:
;   Count bytes up to the NUL terminator at A0.
; Parameters:
;   A0 - string pointer.
; Returns:
;   Byte length in D0.
; Registers used:
;   A1 - scan cursor; D0 - byte count.
; ---------------------------------------------------------------------------
StringLength:
		movea.l	a0,a1
		clr.l	d0
		
SLLoop:
		tst.b	(a1)
		beq.s	SLDone
		addq.l	#1,a1
		addq.l	#1,d0
		bra.s	SLLoop
		
SLDone:
		rts
		
; ---------------------------------------------------------------------------
; LongToAscii
; Purpose:
;   Convert the signed longword in D0 to a NUL-terminated decimal string.
; Parameters:
;   D0 - signed integer value.
; Returns:
;   A0 - pointer to the first character in ElapsedBuffer.
; Registers used:
;   D1-D6/A1 - conversion and output cursor state; A2 is also modified.
; ---------------------------------------------------------------------------
LongToAscii:
		movem.l	d1-d6/a1,-(sp)
		lea		ElapsedBuffer+31,a1
		clr.b	(a1)
		moveq	#0,d5
		tst.l	d0
		bne.s	CheckNegative
		subq.l	#1,a1
		move.b	#'0',(a1)
		movea.l	a1,a0
		movem.l	(sp)+,d1-d6/a1
		rts
		
CheckNegative:
		tst.l	d0
		bge.s	Convert
		moveq	#1,d5
		neg.l	d0
		
Convert:
ConvLoop:
		moveq	#0,d2
		move.l	d0,d1
		
DivLoop:
		cmpi.l	#10,d1
		blt.s	DivDone
		subi.l	#10,d1
		addq.l	#1,a2
		bra.s	DivLoop
		
DivDone:
		addi.b	#'0',d1
		subq.l	#1,a1
		move.b	d1,(a1)
		move.l	d2,d0
		tst.l	d0
		bne.s	ConvLoop
		tst.b	d5
		beq.s	FinishNum
		subq.l	#1,a1
		move.b	#'-',(a1)
		
FinishNum:
		movea.l	a1,a0
		movem.l	(sp)+,d1-d6/a1
		rts
		
		.DATA
InputPath:	
		.DC.b "C:/INPUT.TXT",0
OutputPath:	
		.DC.b "C:/OUTPUT.TXT",0
ProgramName:	
		.DC.b "***HEAPSORT GFA ASM***",0
LoadingMsg:
		.DC.b "LOADING INPUT FILE...",0
SavingMsg:
		.DC.b "SAVING OUTPUT FILE...",0
SortingMsg:
		.DC.b "SORTING ELEMENTS...",0
DoneMsg:
		.DC.b "DONE.",13,100
CompleteMsg:
		.DC.b "***RUN COMPLETE***",13,10,0
TimeMsg:
		.DC.b "HEAPSORT TOOK ",0
SecondsMsg:
		.DC.b " SECONDS."13,10,0
		.EVEN
StartTime:
		.DC.l 0
BytesReadTracker:
		.DC.l 0
		
		.BSS
		.EVEN
ArrayBuffer:
		.DS.l 1000
InputBuffer:
		.DS.b 32768
ElapsedBuffer:
		.DS.b 32