Fremdes ASM debuggen

[DGL-luke]

Hallo,

zu allererst eine Entschuldigung, dass ich hier mit einer "hab ich gesaugt - funzt nicht - tut bitte was"-Anfrage komme.

Ich hab mir hier eine wunderschöne Datenstruktur aufgebaut, namentlich ein AVL Baum, und da meine eigene Implementation nich so doll war, hab ich den gefunden: http://www.torry.net/pages.php?id=278 -> zweiter Eintrag.

Jetzt funzt aber das Find nicht... Ich erstelle eine neue TBinaryTree-Instanz, weise ihr die Keys zu, und schicke den Binärbaum auf die Suche.

Der liefert mir auch ein Ergebnis - in dem aber leider der Inhalt nicht gesetzt ist (eine TList). Nach längerem Debuggen hab ich im Evaluator mal genauer geschaut: Und das Ergebnis der Find-Funktion ist genau die Node, die ich übergeben habe. Genau die selbe Speicheradresse im Instanzenzeiger gespeichert. Logisch dass da kein Inhalt ist - den brauch ich ja genau dort nicht.

Hier ist der ASM-Code, in den ich gerne ein bisschen Einblick hätte:

Delphi-Quellcode:

function TBalancedTree.Find( ANode : TBalancedTree ) : TBalancedTree; assembler;
asm
// eax = Self - Tree
// edx = ANode
// ecx = Result
  test  eax,eax
  jz    @@Exit
  push  esi
  push  edi
  mov   esi,edx // esi = cur
  mov   edi,eax // edi = ANode
  xchg  eax,edx
  test  eax,eax
  jnz   @@8
  jmp   @@Nil
@@1:  //das muss die verzweigung sein, in der getestet wird, obs links oder rechts weitergeht
  lea   eax,[esi].TBalancedTree.RLink
  jl    @@5
  lea   eax,[esi].TBalancedTree.LLink
@@5:
  mov   edx,[eax]
  test  edx,edx
  jz    @@Nil
  mov   esi,edx
  mov   eax,edi
@@8:
  mov   ecx,[edi]
  //call  dword ptr [ecx].vmtCompare    // Compare - cur ?? Node  //da hat der autor optimiert. als fehlerquelle ausgeschlossen ;-)
  call dword ptr [ecx + vmtoffset TBalancedTree.Compare] //vergleichen... schiebt wohl das ergebnis auf eax.
  test  eax,eax
  jnz   @@1  //springt wenn eax <> 0
  mov   eax,esi //das passiert wenn eax = 0, d.h. ein treffer vorliegt, müsste also die zuweisung des results sein (trotz result=ecx...)
@@Nil:
  pop   edi
  pop   esi
@@Exit:
end; {TBalancedTree.Find}

Der übliche Pseudocode für die binäre Suche, der meine unqualifizierten kommentare oben etwas erhellen könnte:

Code:

function Find(gesuchterNode)
  cmp = Vergleiche(this.Key, gesuchterNode.Key) //das ist der call
  if cmp < 0
    return this.LeftChild.Find(gesuchterNode.Key)
  if cmp = 0
    return this
  if cmp > 0
    return this.RightChild.Find(gesuchterNode.Key)

Genau das sollte dieser asm-code machen. nur scheint er statt "return this" "return gesuchterKey (alias ANode)" zu machen. Kann irgendjemand, der asm flüssig liest, das nachvollziehen? Es würde mir sehr viel Arbeit ersparen...

Die Erkenntnis, dass genau dann ANode zurückgegeben wird, wenn er einfach nix findet, würde mir ja auch schon weiterhelfen.

Ich will jetzt auch nicht meinen Code posten, dass da ein Fehler ist, ist natürlich immer noch möglich, aber gehen wir zunächst einfach einmal davon aus, er wäre es nicht.

PS: Der baum wird übrigens richtig sortiert(nachdem ich bei der Compare-Funktion einige Anläufe brauchte), das lasse ich mir ausgeben, und die Values liegen dort auch hundertprozentig.

EDIT: Ähmm... ja... :gruebel:
Nachdem der Pseudocode so leicht runterzutippen ging, hab ich mich kurz gewundert, und es einfach selbst implementiert:

Delphi-Quellcode:

function TBalancedTree.Find( ANode : TBalancedTree ) : TBalancedTree;
var
  cmp: Integer;
begin
  cmp := -Compare(ANode);
  if (cmp < 0) then
    if (LLink <> nil) then
      Result := LLink.Find(ANode)
    else
      Result := nil
  else if cmp > 0 then
    if (RLink <> nil) then
      Result := RLink.Find(ANode)
    else
      Result := nil
  else {if cmp = 0 then}
    Result := self;
end;

Jo, das tut auf den ersten Blick - extensives Testen natürlcih noch erforderlich. Was der ASM tut, interessiert mich dann eigentlcih nicht mehr so brennend. Aber wenn zufällig jemand vorbeikommt, der ASM lesen üben will ;-)

EDIT: Im obigen Code Compare invertiert. Ka warum, funzt aber nur so. :gruebel: