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
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.
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
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?
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.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.