% Section 2.2.3, Exo.24, Topological sorting w/ loop detection % Author Chan Vinh VONG % includes work of Andey Dubinchak. % Draft Version 2012 March 25th % % The answer to the exercise is integrated into the previous proposal % for program T (Topological sorting) from Andey Dubinchak. Changes are % clearly indicated. % % In order to test the loop detection, two files are also provided: % - "loop.dat" which contains relations: {1<2, 2<3, 3<1} % - expected computation: % - "output.dat" is empty % - loop 1 3 2 1 is echoed % - "chain-loop.dat" with: {1<2, 2<3, 4<5, 5<6, 6<4} % - expected computation: % - "output.dat" embeds linear order 1 2 3 % - loop 4 6 5 4 is echoed % % For interactive mode, two files are provided: % - "nodes" which queries the pool of nodes % - "succs" which queries the pool of successors % % Misc notes: % - when translating index to address, sequence SET,16ADDU is used % instead of MUL,LDA because the latter takes 11v cycles while the % former takes 2v cycles % - input file is still hardcoded; don't forget to change filename % in the code and recompile % COUNT IS 0 QLINK IS 0 TOP IS 8 SUC IS 0 NEXT IS 8 T IS $0 F IS $1 P IS $2 j IS $3 k IS $4 ZERO IS $5 N IS $6 kx IS $7 nn IS $8 count IS $9 jb IS $10 kb IS $11 jx IS $12 R IS $13 t IS $255 %====================================================================== % Chan: added for loop detection (note: should optimize # of used $) %====================================================================== N0 IS $14 % keep initial value of N char IS $15 temp IS $16 %====================================================================== LOC Data_Segment x0 GREG @ X0 IS @ LOC Data_Segment+#B000000 BUFFER (Loaded data) b0 GREG @ B0 IS @ LOC Data_Segment+#B200000 BUFFER (Output data) b20 GREG @ B20 IS @ LOC Data_Segment+#5000000 Storage pool AVAIL GREG @ %====================================================================== % Chan: added for output %====================================================================== LOC Data_Segment+#6000000 Ascii Data output GREG @ BYTE "X",#A,0 OCTA 0 title GREG @ BYTE "LOOP DETECTED IN INPUT:",#A,0 %====================================================================== LOC #100 i_file BYTE "chain-loop.dat",0 o_file BYTE "output.dat",0 i_read OCTA i_file,BinaryRead o_write OCTA o_file,BinaryWrite b_read OCTA B0,400 b_write OCTA B20,400 * inserting Main GETA t,i_read T1: TRAP 0,Fopen,3 % Chan: changed to correct handler GETA t,o_write TRAP 0,Fopen,4 % Chan: idem GETA t,b_read TRAP 0,Fread,3 % Chan: idem LDOU N,b0 N <- n SET nn,N SET N0,N % Chan: added for loop detection {l14a} SET ZERO,0 SET kx,x0 1H STO ZERO,kx,COUNT COUNT[k] <- 0 STO ZERO,kx,TOP TOP[k] <- 0 ADD kx,kx,#10 SUB nn,nn,1 BNN nn,1B LDA jb,b0,8 T2: 2H LDTU j,jb BP j,3F j>0? BZ j,4F JMP 2B 3H ADD kb,jb,4 LDTU k,kb MUL kx,k,#10 LDA kx,x0,kx LDOU count,kx,COUNT COUNT[k] ADD count,count,1 +1 STOU count,kx,COUNT -> COUNT[k] MUL jx,j,#10 LDA jx,x0,jx SET P,AVAIL LDA AVAIL,P,#10 AVAIL <- LINK(P). STO k,P,SUC SUC(P) <- k. LDOU T,jx,TOP STOU T,P,NEXT NEXT(P) <- TOP(j) STOU P,jx,TOP TOP(j) <- P ADD jb,jb,8 JMP 2B 4H SET R,0 SET k,N MUL R,R,#10 LDA R,x0,R 4H MUL kx,k,#10 LDA kx,x0,kx LDOU count,kx,COUNT BP count,H41 STO k,R,QLINK QLINK[R] <- k SET R,k MUL R,R,#10 LDA R,x0,R H41 SUB k,k,1 BP k,4B * sorting LDOU F,x0,QLINK F <- QLINK[0] SET nn,0 5H STOU F,b20,nn BZ F,8F ADD nn,nn,#8 SUB N,N,1 N <- N-1 MUL F,F,#10 LDA F,x0,F LDOU P,F,TOP P <- TOP(F) STCO 0,F,TOP TOP[F] <- NULL % added BZ P,7F 6H LDO k,P,SUC r4 <- SUC(P) MUL kx,k,#10 LDA kx,x0,kx LDOU count,kx,COUNT COUNT[r4] SUB count,count,1 -1 STOU count,kx,COUNT ->COUNT[r4] BP count,H61 STO k,R,QLINK SET R,k MUL R,R,#10 LDA R,x0,R H61 LDOU P,P,NEXT P <- NEXT(P) BNZ P,6B 7H LDOU F,F,QLINK JMP 5B 8H GETA t,b_write TRAP 0,Fwrite,4 % TRAP 0,Halt,0 %====================================================================== % Chan: integrating answer to Ex24 {l74-75} %====================================================================== BZ N,DONE LDA $255,title Print indication of loop TRAP 0,Fputs,StdOut SET nn,N0 9H SET kx,x0 16ADDU kx,nn,kx kx = 2*OCTA*Index + Base STCO 0,kx,QLINK QLINK[k] <- 0 SUB nn,nn,1 BP nn,9B n >= k >= 1 % BP: all COUNT/QLINK[k] are now NULL SET nn,N0 {note: nn is rI6/k} T9 SET kx,x0 16ADDU kx,nn,kx LDO P,kx,TOP P <- TOP[k] {note: P is rI2} STCO 0,kx,TOP TOP[k] <- 0 BZ P,T9A Is P = NULL ? T10 LDO t,P,SUC t <- SUC(P) {note: t is rI1} SET kx,x0 16ADDU kx,t,kx STO nn,kx,QLINK QLINK[t] <- k LDO P,P,NEXT P <- NEXT(P) BP P,T10 Is P != NULL? T9A SUB nn,nn,1 BP nn,T9 n >= k >= 1 % BP: all nodes are now detached from their chain of successors T11 ADD nn,nn,1 SET kx,x0 16ADDU kx,nn,kx LDO t,kx,QLINK BZ t,T11 find k with QLINK[k] != NULL T12 STO nn,kx,TOP TOP[k] <- k LDO nn,kx,QLINK k <- QLINK[k] SET kx,x0 16ADDU kx,nn,kx LDO temp,kx,TOP BZ temp,T12 Is TOP[k] = 0? % printing (assume N <= 9 for simplicity otherwise DIV10 etc) T13 SET char,nn ADD char,char,#30 Convert k to alphameric STB char,output LDA $255,output Print TRAP 0,Fputs,StdOut BZ temp,DONE Stop when TOP[k] = 0 STCO 0,kx,TOP Top[k] <- 0 LDO nn,kx,QLINK k <- QLINK[k] SET kx,x0 16ADDU kx,nn,kx LDO temp,kx,TOP JMP T13 DONE TRAP 0,Halt,0 End of computation %====================================================================== % Chan: integrating answer to Ex24 {l74-75} %======================================================================