bianry tree search 16Bit, ASM

[Andi (Gast)]

Moin!

Ich hab gerade in Assembler (für AVR-Mega8535) eine Suchroutine
gebastelt, die mir die Tabellenposition eines 16-Bit-Wertes
heraussucht. Ich hab nur irgendwie das Gefühl, daß es etwas kompliziert
geworden ist und frage mich, ob man das irgendwie vereinfachen oder
optimieren kann. (asm-File im Anhang.)

Die Routine funktioniert wie folgt:

der zu suchende 16-Bit-Wert steht in r9/r19, die (sortierte)Tabelle
enthält insgesamt 128 Werte. Gestartet wird die Suche in der Mitte der
Tabelle, der dort stehende Wert mit dem Suchwert verglichen, und je
nachdem, ob er größer oder kleiner ist, weiter oben oder weiter unten
gesucht.

Das ganze wird 7mal in einer Schleife durchgeführt, dabei der Offset
und gleichzeitig Schleifenzähler (rLoopCnt1) durch 2 geteilt.

Zu Begin beträgt der Offset also 64, der Wert wird zur
Tabellenstartadresse hinzuaddiert, damit zeigt der Pointer auf den
mittleren Wert. Im Zweiten Durchlauf beträgt der Offset 32, dieser wird
je nach gefundenem 16Bit-Tabellen-Wert hinzuaddiert oder abgezogen, der
Pointer also weiter nach oben oder weiter nach unten geschoben. 3.
Durchlauf beträgt der Offset dann nur noch 16, usw. Bis alle
Tabelleneinträge durch sind.

Zum Schluß zeigt mein Pointer also auf die Tabellenposition, in dem der
Wert dem des zu Suchendem recht nahe ist, entweder auf der nächst
höheren oder nächst niedrigeren Position. Das wird in einem letzten
Schritt geprüft, und bei Bedarf - falls der Wert höher war - der
Pointer auf die nächst niedrigere Position verschoben.

Getestet habe ich die Routine mit mehreren Werten, funktionieren tut
das ganze. Allerdings benötige ich doch ganze 250 Zyklen für den
komplette Durchlauf, irgendwie hätte ich es doch gerne etwas schneller,
wenn es denn möglich wäre. Vielleicht hat jemand Ideen, wie man das
ganze etwas "abkürzen" kann?

Gruß,
Andi

[Profi (Gast)]

Du kannst es wohl nicht lassen....
Anstatt den Bresenham zu implementieren.
Naja, ist auf jeden Fall eine gute Übung.


Hat der Assembler statt des .DB kein .DW?
Oder ist dann die Reihenfolge falsch?


      lsr rLoopcnt1
      breq tsearchok

      add ZL, rloopcnt1
      adc ZH, Temp
      add ZL, rloopcnt1
      adc ZH, Temp

Ist rLoopcnt und rloopcnt dasselbe? Dann kannst Du das Addieren /
Subtrahieren evtl. vor das lsr legen, dann brauchst Du nicht zweimal
Addieren / Subtrahieren.

Wenn genug Programmspeicher vorhanden, kannst Du die Schleife auch
ausschreiben, also sequentiell programmieren, das spart den
Schleifen-Overhead.

[Andi (Gast)]

Hallo Profi!

Jaja, ich kanns nicht lassen... ;-) Nein, mir geht es hierbei doch um
ein ganz anderes Problem als das mit dem Bresenham. Das sind zwei paar
Schuhe. Ich gehe jetzt einfach mal so weit und sage, daß das eine
Problem nix mit dem anderen zu tun hat. Für meine Fräse werd ich die
Tabelle wohl gar nicht brauchen, aber ggf für andere Projekte, und da
ich damit schon angefangen habe, wollte ich es auch bis zum Ende
durchziehen. Also wie Du schon sagtest... sozusagen als Übung. :-)

>Hat der Assembler statt des .DB kein .DW?

Doch klar. Hab den Walt vor lauter Bäumen nicht gesehen... ;-) Kommt
davon, wenn man nen alten Code per drag&drop nimmt und nur verändert.
Hab ich gar nicht dran gedacht. Naja, aber dadurch wirds ja nicht
schneller, ich hätte mir nur einiges an Tiparbeit erpart. :-/

>      lsr rLoopcnt1
>      breq tsearchok
>
>      add ZL, rLoopcnt1
>      adc ZH, Temp
>      add ZL, rloopcnt1
>      adc ZH, Temp
>
>Ist rLoopcnt und rloopcnt dasselbe? Dann kannst Du das Addieren /
>Subtrahieren evtl. vor das lsr legen, dann brauchst Du nicht zweimal
>Addieren / Subtrahieren.

"rLoopcnt" und "rloopcnt" ist dasselbe (war zu Faul 'shift' zu
dürcken;-) Daran hab auch schon gedacht, geht aber nicht, da rLoopcnt1
nicht verändert werden darf, es zählt gleichzeitig als Schleifenzähler
und wird so oft nach rechts geschiftet bis der Wert 0 ist ->'breq'
direkt nach 'lsr'.

Wenn ich die Problematik nicht ganz umständlich programmiert habe,
wirds vermutlich tatsächlich nicht schneller gehen. Und anstelle der
Schleife das ganze sequentiell zu programmieren... naja, auf diese 10
Taktzyklen o.ä. die ich dadurch einspare, machen den Kohl nicht fett.

Gruß,
Andi

[Simon (Gast)]

hi,
ich find die Tabellengeschichte spannend kann aber kein Assembler. Hat
jemand sowas schon in C und läßt mich in die Karten sehen. Bin auch
noch C-Anfänger ...
Gibts zu sowas ein Tuto oder ein Buch zum nachlesen?

[Werner (Gast)]

Wahrscheinlich hab ich dich falsch verstanden, aber wenn du nur 128
Einträge in deiner Tabelle hast und die eventuell auch noch alle
unterschiedlich sind, könntest du nicht Hashing benutzen?
Kommt halt drauf an, ob man das modulo effizient hinkriegt.