I'm having big problems with writing an asm x86 code in emu8086 that finds a topological sorting of a graph (with no cicles) given its adjacency matrix, and the number of nodes. I've tried a couple of ideas but nothing has worked...so if any of you guys could give me ANY help (in words or in code) with how to solve this, or how to aproach this problem, it would be great 'cause I don't know what to do... The data is given like this:
JMP main
size db 4
graph db 0 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0
ordering db 0 ,0 ,0 ,0
main :
I think that the DFS algorithm could be the best to solve this. But again, I sincerely have tried everything and nothing has worked so far...so I will apreciate any help. Thanks in advance!!! (and sorry for the bad english)
Edit: I wrote this but it doesn't work at all:
JMP main
size db 4
graph db 0 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0
ordering db 0 ,0 ,0 ,0
permanente db 0, 0, 0, 0
main :
MOV CL,1
PUSH CX
LEA BX,graph
PUSH BX
CALL visitar
RET
visitar:
PUSH BP
MOV BP,SP
MOV BX,[BP+4]
MOV CX,[BP+6]
LEA DI,size
MOV DX,[DI]
MOV SI,0
for:
CMP SI,DX
JE end_for
CMP [BX+SI],1
JE nodo
JMP next
nodo:
MOV CX,SI
ADD CX,1
PUSH CX
MOV AX,SI
MUL size
LEA BX,graph
ADD BX,AX
PUSH BX
CALL visitar
next:
ADD SI,1
JMP for
end_for:
LEA DI,permanente
ADD DI,CX
SUB DI,1
MOV [DI],1
MOV SI,DX
LEA DX,ordering
bajar:
SUB SI,1
CMP [DX+SI],0
JE cambiar
CMP SI,0
JG bajar
cambiar:
MOV [DX+SI],CX
CMP SI,0
JE return
JMP revisar
revisar:
LEA AX,permanente
MOV SI,0
sumar:
CMP [AX+SI],0
JE seguir
ADD SI,1
LEA DI,size
MOV DX,[DI]
CMP SI,DX
JE return
JMP sumar
seguir:
JMP nodo
return:
POP BP
RET 4
Some bugs I caught by reading the source (I don't claim any completeness of the list, there may be more):
LEA DI,size
MOV DX,[DI]
Size is declared as byte, but you fetch word, so you are actually fetching size + first edge from graph. If the first edge would be 1, the dx would be 300 instead of expected 4.
Either extend size to word by dw declaration, or work with bytes only.
Also you can fetch the size directly from address like mov dx,[size], no need to lea it's address.
CMP [BX+SI],1
I don't like this syntax, it's not clear what size is compared. I'm not sure what emu8086 syntax has, try adding byte on either side like BYTE 1, or BYTE PTR [bx+si] like TASM/MASM syntax. I hope one of it would work.
While this may look like "style" preference, if your edges definition would be more complex than 0/1 and use words, it would be bug (as I suspect the default result is byte compare).
MUL size
Check the instruction guide for details. You destroy content of one other register, which would make your for to fail.
Also I don't like the syntax, you want the value from memory at size address, not the address itself, so adding [] around size makes it easier to understand, that you are interested into memory content.
And finally no data size is specified, I missed that one completely. So if the assembler treats this as byte, then the first remark about destroyed register content is invalid, but then it looks like you wanted to do ax*size, which would require word specifier. BTW, you already had size loaded in dx, so mul dx or mul dl would save you memory access.
CALL visitar
Your lack of high-level documentation does catch you here.
When creating assembly functions, always document in comments what are parameters (how to call it), what is the result (if any), and what registers are modified.
Your visitar does modify many registers, yet during the for loop you somehow expect the si to be preserved. It's not. Then later you work with cx as original node number, but again, already destroyed during preparation of call parameters. Etc... as it's recursive call, you can be pretty much sure it destroys all registers, which are important to you.
You store words into ordering, while it's defined as byte array, and offsets are in bytes.
MOV CL,1
PUSH CX
ch is uninitialized here (it's probably zero by emu8086, but it's better to initialize everything, as different target platforms may call your "start" in different state.
How to improve what you have:
I would do some design work, what are global variables and what are locals. Then you may try to keep globals around, like size doesn't change during whole run, or ordering[next_to_write] pointer is global, etc.
push/pop important registers before calling visitar to preserve their values. Or as you work with stack frame anyway because of using stack for function arguments, consider putting local variables into stack (sub sp,reserved_space and accessing it by [bp-x]). That way you don't need to worry about modified registers, although it will work slower due to memory access.
Make sure you are using correct size of all values. Decide whether number of nodes (size) is byte or word, that pretty much decides the rest of variables. Although your graph definition is size*size long, so actually you can't have more than ~200 nodes anyway, so going for byte size only is OK. But that means to stick with it, ie. mov [dx+si],cl to store node number into ordering. And when addressing graph, make sure the mul works for 16+ size too.
Some style notes:
add/sub r16,1 -> there're also inc/dec instructions.
LEA AX,permanente - original Intel syntax requires the expression to be like accessing memory, so LEA AX,[permanente] looks more like Intel intended it. Although in case of lea it's actually not working with memory content, so I was not a big fan of the Intel's decision originally. Then again lea ax,bx+si*2+permanente looks weird too.
MOV SI,0 - xor si,si - was one of first "tricks" I learned, made me understand the instructions have exact definition what they do with registers and memory, and if that effect can be used to achieve what I want, I'm free to use any of them, even if their name doesn't directly imply that usage.
Try some more different addressing modes, you don't need always to lea every variable address. I'm never sure what registers are allowed in 16b mode (32b protected mode allows many more combinations, so I'm used to things like [eax+ecx*8], which wouldn't work in 16b), but for example [permanente+si] should work ok, etc.
Oh, and of course get some debugger and learn how to use it. I'm pretty sure your original code must get into unexpected state in few steps inside debugger.
Also try to keep around source some "high level" comments, like for every group of 3-10 instructions. And some notes about register allocation, what value you expect where.