-1

我在 emu8086 中编写 asm x86 代码时遇到了很大的问题，该代码在给定邻接矩阵和节点数的情况下找到图的拓扑排序（没有 cicles）。我已经尝试了几个想法，但没有任何效果......所以如果你们中的任何一个人可以给我任何帮助（在文字或代码中）如何解决这个问题，或者如何解决这个问题，那就太好了因为我不知道该怎么做......数据是这样给出的：

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 :

我认为 DFS 算法可能是解决这个问题的最佳方法。但同样，我真诚地尝试了一切，但到目前为止没有任何效果......所以我会感谢任何帮助。提前致谢！！！（抱歉英语不好）

编辑：我写了这个，但它根本不起作用：

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
4

1 回答 1

0

我通过阅读源代码发现了一些错误（我不声称列表的任何完整性，可能还有更多）：

LEA DI,size
MOV DX,[DI]

大小被声明为字节，但您获取的是字，因此您实际上是从图中获取大小+第一条边。如果第一条边为 1，dx则为 300 而不是预期的 4。

通过声明扩展size到单词dw，或者仅使用字节。

你也可以直接从地址中获取大小mov dx,[size]，不需要lea它的地址。

CMP [BX+SI],1

我不喜欢这种语法，不清楚比较的大小。我不确定 emu8086 语法有什么，尝试byte在任一侧添加 likeBYTE 1或BYTE PTR [bx+si]like TASM/MASM 语法。我希望其中之一能奏效。

虽然这可能看起来像“风格”偏好，但如果您的边缘定义比 0/1 更复杂并使用单词，那将是错误（因为我怀疑默认结果是字节比较）。

MUL size

详情请查看说明指南。您破坏了另一个寄存器的内容，这将使您for失败。

另外我不喜欢这种语法，你想要地址中的内存值size，而不是地址本身，所以添加[]大小可以更容易理解，你对内存内容感兴趣。

最后没有指定数据大小，我完全错过了那个。因此，如果汇编器将其视为字节，那么关于被破坏的寄存器内容的第一条评论是无效的，但看起来你想要做 ax*size，这需要单词说明符。顺便说一句，您已经加载了大小dx，因此mul dx或者mul dl会节省您的内存访问。

CALL visitar

您缺乏高级文档确实会吸引您。

创建汇编函数时，始终在注释中记录什么是参数（如何调用它）、结果是什么（如果有）以及修改了哪些寄存器。

您visitar确实修改了许多寄存器，但在for循环期间您以某种方式期望si保留。它不是。然后稍后您将使用cx原始节点号，但同样，在准备调用参数期间已经销毁。等等......因为它是递归调用，你可以确定它会破坏所有对你很重要的寄存器。

您将单词存储到ordering中，而它被定义为字节数组，并且偏移量以字节为单位。

MOV CL,1
PUSH CX

ch此处未初始化（emu8086 可能为零，但最好初始化所有内容，因为不同的目标平台可能会在不同的状态下调用您的“开始”。

如何改善你所拥有的：

我会做一些设计工作，什么是全局变量，什么是本地变量。然后你可以尝试保持全局变量，比如在整个运行过程中大小不会改变，或者 ordering[next_to_write] 指针是全局的，等等。

在调用之前推送/弹出重要寄存器visitar以保留其值。或者，由于使用堆栈作为函数参数，因此无论如何都使用堆栈框架，请考虑将局部变量放入堆栈（sub sp,reserved_space并通过 访问它[bp-x]）。这样您就不必担心修改寄存器，尽管由于内存访问它会运行得更慢。

确保您使用正确大小的所有值。决定节点数 ( size) 是字节还是字，这几乎决定了其余的变量。虽然你的graph定义是 size*size long，所以实际上你不能有超过 ~200 个节点，所以byte只考虑 size 是可以的。但这意味着坚持下去，即。mov [dx+si],cl将节点号存储到ordering. 并且在处理图表时，请确保mul也适用于 16+ 大小。

一些风格说明：

add/sub r16,1-> 还有inc/dec说明。

LEA AX,permanente- 原始 Intel 语法要求表达式类似于访问内存，因此LEA AX,[permanente]看起来更像 Intel 的意图。虽然如果lea它实际上不适用于内存内容，所以我最初并不是英特尔决定的忠实粉丝。然后lea ax,bx+si*2+permanente看起来也很奇怪。

MOV SI,0- xor si,si- 是我学到的第一个“技巧”之一，让我明白指令有确切的定义它们对寄存器和内存的作用，如果这种效果可以用来实现我想要的，我可以自由使用它们中的任何一个，即使他们的名字并不直接暗示这种用法。

尝试一些更多不同的寻址模式，你不需要总是对lea每个变量地址。我不确定在 16b 模式下允许哪些寄存器（32b 保护模式允许更多组合，所以我习惯了 [eax+ecx*8] 之类的东西，这在 16b 中不起作用），但例如[permanente+si]应该工作正常等

哦，当然还有一些调试器并学习如何使用它。我很确定您的原始代码必须在调试器中的几个步骤中进入意外状态。

还要尽量保留一些“高级”注释，例如每组 3-10 条指令。还有一些关于寄存器分配的注释，你期望在哪里得到什么值。

于 2016-10-19T05:19:08.137 回答