;
; UFRGS - INF - M Johann - 2023 - johann@inf.ufrgs.br
; Makes a histogram of characters from a text and then
; sorts them in decreasing order of occurrence
; Text message may have at most 110 chars, from 92h to FFh


; ----- GLOBAL DATA 

		org	h5C

; ----- with char table starting at h5C, decreasing order is: 
		; first data pos = 8Fh, second is 8Dh
		; last data pos = 5Dh, next is 5Bh

table:		dab	65,0,66,0,67,0,68,0,69,0,70,0,71,0,72,0,
                dab	73,0,74,0,75,0,76,0,77,0,78,0,79,0,80,0,
                dab	81,0,82,0,83,0,84,0,85,0,86,0,87,0,88,0,
                dab	89,0,90,0

; ----- global pointer to string and temp for both algorithms
		
ptr:		db 	text		; points to the beginning of text
temp:		db	0

; ----- here is the input text message

		org	h92

text:	dab 	'T','H','I','S',' ','I','S',' ','A',' ','M','E','S','S','A','G','E',' '
	dab 	'w','i','t','h',' ','a',' ','l','o','w','e','r','c','a','s','e',' ',
	dab	'p','a','r','t','!'
	dab	' ','X','X','X','X','X','X','X','X','X','X','X','X','X','X','X'	; +15 x
	dab	' ','z','z','z','z','z','z','z','z','z','z' ; and 10 'z's

		
; ----- BEGIN MAIN CODE 

		org	0
init:		
loop:		LDR	X,ptr,I
		SUB	X,#65
		JN	continue
		SUB	X,#26
		JN	addchar
		SUB	X,#6
		JN 	continue
		SUB	X,#26
		JN	addchar
		JMP 	continue	

addchar:	ADD	X,#26
		STR	X,temp
		ADD	X,temp
		LDR 	A,table+1,X
		ADD	A,#1
		STR	A,table+1,X	

continue:	LDR	A,ptr
		ADD 	A,#1
		STR	A,ptr	
		JZ 	initsort
		JMP 	loop

; ----- now bubble sort the resulting table

initsort:	LDR	B,#1		; force star as if swap was done	
pass:		LDR	X,#h8D		; index at second position
		SUB	B,#1		; if no swap was made B was 0
		JN	finish

iteration:	LDR	A,+2,X		; reads right value
		SUB	A,0,X		; subtracts current
		JN 	next		; if second is smaller, skip
		JZ	next   

		JSR	SWAP
		SUB	X,#1
		JSR 	SWAP
		ADD	X,#1
		LDR	B,#1		; mark a swap has occurred
		
next:
		SUB	X,#h5D		; compare to the last pos
		JZ	pass		; if pass ended
		ADD	X,#h5B		; recover from sub and add 2
		JMP 	iteration

finish:		HLT

; ----- subroutine to swap two positions X and X+2 from table

SWAP:		nop
		LDR	A,+2,X
		STR	A, temp
		LDR	A,0,X
		STR	A,+2,X
		LDR	A, temp
		STR	A,0,X
		JMP	SWAP,I	

; END OF FILE