;
; UFRGS - INF - M Johann - 2023 - johann@inf.ufrgs.br
; Simple 8-bit placer on Ramses (using Threshold Accepting)
; STATUS: working with 1 full iteration loop (255 to 0)
; Room for 4 instructions and 1 byte before data at h8A
; TODO: check speed on the PocketRamses (Arduino 16MHz)
; If not too slow, make a second iterations loop

; The placer works on a graph with exactly 16 cells (nodes)
; and 32 point-to-point connections (edges), in a 4x4 square;
; cells with no connections could represent spaces;
; connections from-to the same cells will have no effect.
; So it can place any graph with up to 16 nodes and 32 edges

; The given example was generated with a PEKO-like method:
; only neighbor cells were connected, and then scrambled.
; It has at least 8 solutions with cost=32 (rotation and mirroring)
; from a total of ~21 trillion configurations (16!)
; This code finds solutions with costs between 42 and 46, 
; and a lower cost of 39 when used with seed h02, but
; varying a lot with randomness and would be improved if
; another iteration loop is implemented. 

; ----- DATA and Random generation at the end

		org		h8A

costatual: 	db 	0
oldcost:	db	0
threshold:	db 	32
iteration:	db	255	; starts with 0 after each cycle

cella:		db	0
cellb:		db	0

Xbase:		dab	0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3; X coordinates
Ybase:		dab	0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3; Y coordinates
src:		dab	15,8,8,13,13,0,14,6,0,5,11,14,12,0,12,1,
		dab	8,1,2,3,12,13,8,4,9,5,13,1,0,15,15,3
dst:		dab	4,1,9,1,1,15,11,10,15,15,6,2,5,15,5,7,
		dab	1,8,7,2,4,6,0,12,8,13,1,7,13,4,4,2

temp: 		db	0
index: 		db 	0
randval:	db	h02	; used as random seed

; ----- RANDOM NUMBER in [0-15] - very simple algorithm using regs and mem 

SELECT: NOP
	ADD X,randval
	ADD X,0,X
	STR X,randval
	ADD A,randval	; cannot be eliminated
	AND A,#hF	; result in 4 bits on RA
	JMP SELECT,I
		
; ----- BEGIN MAIN CODE 

		org	0
init:		JSR	COST
nextt:					; next threshold
		LDR	A,threshold
		SUB	A,#1
		STR	A,threshold
		JZ	fim
nexti:					; next SWAP
		JSR	SELECT
		STR	A,cella
		JSR	SELECT
		STR	A,cellb
		LDR	A,costatual
		STR	A,oldcost
		JSR	SWAP
		JSR 	COST
		SUB	B,oldcost
		SUB	B,threshold
		JN	accept
unswap:		JSR	SWAP
		LDR	A,oldcost
		STR	A,costatual
accept:		
		LDR	A,iteration
		SUB	A,#1
		STR	A,iteration
		JZ	nextt
		JMP	nexti
fim:
		HLT

; ----- SUBROUTINES

; ----- COST += abs(X[src[i]]-X[dst[i]])+abs(Y[src[i]]-Y[dst[i]])
; result will be on costatual and also on RB

COST: 	NOP
	LDR 	A,#0
	STR	A,costatual
	LDR 	X,#31
	STR	X,index
next:   LDR 	A, src,X
	LDR 	X, dst,X	; here RX has dst
	STR 	A, temp		; temp is source
	LDR 	A, Xbase,X	; RA has X[dst]
	LDR 	B, Ybase,X	; RB has Y[dst]
	LDR	X, temp		; RX = temp is source
	SUB 	A, Xbase,X	; RA = RA - X[src]
	JN 	otherx
	NEG	A		; JMP 	cont1
otherx: NEG 	A
cont1: 	
	SUB	B, Ybase,X	; RB = RB - Y[src] : RX has source
	JN	othery
	NEG	B		; JMP 	cont2
othery: NEG	B
cont2:
	ADD	A,costatual
	STR	A,costatual
	ADD	B,costatual
	STR	B,costatual
	LDR 	X,index
	SUB	X,#1
	JN 	COST,I
	STR 	X,index
	JMP	next

; ----- SWAP - exchange X and Y coordinates between cella and cellb

SWAP:	NOP
	LDR X, cella
	LDR A, Xbase,X
	LDR X, cellb
	LDR B, Xbase,X
	STR A, Xbase,X
	LDR X, cella
	STR B, Xbase,X  
	LDR A, Ybase,X
	LDR X, cellb
	LDR B, Ybase,X
	STR A, Ybase,X
	LDR X, cella
	STR B, Ybase,X
	JMP SWAP,I

; END OF FILE