|
|
Forum: Mikrocontroller und Digitale Elektronik Binär-->BCD in CKennt jemand einen relativ schnellen Algorithmus um eine binäre Zahl kleiner 99 in eine zwei Stelle umzuwandeln. Der Code soll auf einem PIC18 laufen, der kann Multiplikationen in Hardware. Von BCD nach binär würde ich so machen:
Daraus macht der Compiler 9 ASM Befehle Aber wie geht das in die andere Richtung? Simon V. schrieb: > Kennt jemand einen relativ schnellen Algorithmus um eine binäre Zahl > kleiner 99 in eine zwei Stelle umzuwandeln. Der Code soll auf einem > PIC18 laufen, der kann Multiplikationen in Hardware. So richtig ist mir irgendwie noch nicht klar, was du machen willst. Ich habe eine unsigned char mit einer Zahl kleiner 99 und will sie in eine 2 stellige BCD Zahl umwandeln. 99/10 = linkes Nibble. Der Rest (oder modulo 99) ist das rechte Nibble. Wenn du das in einem Byte haben willst: (99/10)*16 OR Rest Grüsse Folgendes geht deutlich schneller als eine Division:
BCD01 = Binary;
BCD10 = 0;
while( BCD01>9 )
{
BCD01 -= 10;
BCD10 += 1;
}
BCD = BCD10 << 4 + BCD01
Wenn es ganz schnell gehen muss, dann 100 Byte für eine look-up table
spendieren, wovon ein paar Byte durch das einfachere Programm
kompensiert werden
BCD = BCDTable[ Binary ];
Die naheliegende Formulierung für die Umgekehrung ist:
Durch die Division ist das aber langsamer als eine Lookup-Tabelle. Wie es sich im Vergleich zur Schleife verhält, müsstest Du ausprobieren. Du kannst auch folgendes ausprobieren:
Auf einem ATmega ergibt das 12 Befehle und 13 Taktzyklen. Bei Michaels Code (wo in der letzten Zeile übrigens noch ein Klammerpaar fehlt) sind es 10 Befehle und minimal 9, maximal 63 und im Mittel 36 Taktzyklen. Die Methode mit der Lookup-Tabelle braucht 5 Befehle (plus die 100 Bytes der Tabelle) und 6 Taktzyklen (bzw. 7 Taktzyklen, wenn die Tabelle mit PROGMEM im Flash angelegt wird). Einen PIC-Compiler habe ich nicht, da kann es natürlich wieder anders aussehen. Dein obiger Code zur Umrechnung von BCD nach Binär belegt auf dem ATmega übrigens ebenfalls 9 Befehlsworte. Er wird in 10 Zyklen ausgeführt. Alternativ kannst du auch mit BCD Zahlen rechnen. Der Pic18 hat dafür immer noch ein DC Flag. Irgendjemand sollte dieses Flag doch mal benutzen! Yalu X. schrieb: > Du kannst auch folgendes ausprobieren:
Ich habe das jetzt in PIC-ASM umgeschrieben, und ich braucht 13 Befehlszyklen und es funktioniert. Vielen Dank. Jetzt muss ich nur noch herausfinden, wieso es funktioniert...
Ich habe es mit ASM gemacht, weil der CODE in C viel länger brauch und ich für "bin" eine unsigned int nehmen musste. Ist es möglich kurz zu erklären, wieso ich mit dieser Formel ans Ziel kommen? Klassisch (und lesbar ;-)) würde man die Berechnung so schreiben:
Einsetzen von Zeile 2 in Zeile 3 ergibt:
Das kann man noch etwas zusammenfassen:
Einsetzen von Zeile 1 in Zeile 2 ergibt:
Das ist vermutlich die C-Schreibweise mit der kleinsten Anzahl von Operatoren. Jetzt muss die Division noch wegoptimiert werden: Eine Division durch eine Konstante kann prozessorfreundlich durch eine Multiplikation und eine Division durch eine Zweierpotenz angenähert werden. Da
wäre eine Näherung für zahl / 10:
Diese Näherung hat sich aber als zu ungenau herausgestellt. Eine bessere Nährung erhält man mit der nächsthöheren Zweierpotenz:
Diese Näherung liefert aber in einigen Fällen immer noch falsche, nämlich zu kleine Ergebnisse. Also wird versucht, dies durch Addition einer Korrekturkonstanten c zu beheben:
Es stellt sich heraus, dass die Ergebnisse stimmen, wenn c im Bereich von 18 bis 52 liegt. Setzt man c = 52, erhält man insgesamt den folgenden Ausdruck:
Das ist schon fast das Ergebnis aus meinem letzten Beitrag. Der GCC tut sich etwas leichter, wenn man statt um 9 nur um 8 Bits shiftet und dafür den Faktor 6 halbiert. Da mit diesem Vorgehen praktisch eine Division durch 2 und eine anschließende Multiplikation mit 2 entfällt, muss zusätzlich der Klammerausdruck auf die nächstkleinere gerade Zahl abgerundet werden. Dazu wird einfach das letzte Bit gelöscht:
Während ich dies schrieb, ist mir noch eingefallen, dass man für c auch 51 einsetzen könnte, was den Ausdruck weiter vereinfacht, weil dann die linke Addition vor der Multiplikation und damit im 8-Bit-Wertebereich gerechnet werden kann:
:
Bearbeitet durch Moderator
Yalu X. schrieb: > bcd = 3 * (((uint8_t)(zahl + 1) * 51) >> 8 & ~1) + zahl; Auch wenn ich es so mache muss ich zahl in eine unsigend int umwandeln damit es funktioniert: bcd = 3 * (((unsigned int)(zahl + 1) * 51) >> 8 & ~1) + zahl; Kann es sein, dass das am Compiler liegt? Ich verwende den C18. Und den asm Code konnte ich noch kürzen: _asm //bin_to_bcd MOVLB 0 incf zahl,WREG,BANKED mullw 51 movf PRODH,WREG,ACCESS ANDLW 0b11111110 mullw 3 movf PRODL,WREG,ACCESS addwf zahl,WREG,BANKED movwf bcd,BANKED _endasm Es ist sicher ein Problem vom C18. Wenn isch das in Code::Blocks eingebe funktioniert es wie es soll:
Aber ob ich jetzt mit char oder int rechen ändert nichts daran, dass ich 66 Zyklen brauche. Mit int stimmt das Ergebnis aber... 66 Zyklen sind schnell genug. Ich könnte das Ganze auch noch als Übung sehen ASM-Funktionen in C einzubauen... Ich muss nur noch herausfinden, wie ich dem BSR sagen kann in welcher Bank meine C-Variable ist. Wenn ich versuche Banksel zu verwenden, sagt der Compiler syntax-error. So ganz werde ich aus dem C18 nicht schlau: Wenn ich den die Formel aufteile, brauch der PIC mit 21 Zyklen: [c] bcd= ((unsigned int)(zahl+1) * 51) >> 8; bcd = 3 * (bcd & ~1) + zahl; //bin to bcd [c/] Jetzt bin ich zufrieden. Vielen Dank für eure Hilfe :) Simon V. schrieb: > Yalu X. schrieb: >> bcd = 3 * (((uint8_t)(zahl + 1) * 51) >> 8 & ~1) + zahl; > > Auch wenn ich es so mache muss ich zahl in eine unsigend int umwandeln > damit es funktioniert: > bcd = 3 * (((unsigned int)(zahl + 1) * 51) >> 8 & ~1) + zahl; Da zahl+1 wegen zahl<100 immer in uint8_t darstellbar ist, sollte es eigentlich keinen Unterschied machen, ob man das Ergebnis in (uint8_t) oder (unsigned int) castet. Ich habe den Cast nur deswegen eingebaut, um dem Compiler darauf hinzuweisen, dass mich nur die unteren 8 Bits des Ergebnisses interessieren, er also bedenkenlos 8-Bit-Arithmetik anwenden darf, ohne mit den Integer-Promotionsregeln des C-Standards in Konflikt zu geraten. Simon V. schrieb: > Kann es sein, dass das am Compiler liegt? Möglicherweise ist das ein Bug. Hast du ein Zahlenbeispiel für einen Fall, wo ein falsches Ergebnis geliefert wird? Simon V. schrieb: > Und den asm Code konnte ich noch kürzen: Das ist doch das, was zählt ;-) Simon V. schrieb: > So ganz werde ich aus dem C18 nicht schlau: > Wenn ich den die Formel aufteile, brauch der PIC mit 21 Zyklen: > [c] > bcd= ((unsigned int)(zahl+1) * 51) >> 8; > bcd = 3 * (bcd & ~1) + zahl; //bin to bcd > [c/] Durch die Aufteilung wird in der Mitte der Berechnung, nämlich bei der ersten Zuweisung an bcd, das Zwischenergebnis für den Compiler sichtbar auf 8 Bits gestutzt. Dadurch kann er möglicherweise den zweiten Teil der Berechnung optimieren. An solchen Stellen ist es immer recht schwierig vorherzusagen, wie gut der Compiler optimieren wird. In den seltenen Fällen, wo wirklich jeder Taktzyklus zählt, ist deswegen manchmal tatsächlich der Einsatz von (Inline-)Assembler angebracht. Jetz, nach dem Aufteilen der Formel funktioniert es mit int und char, bei char brauch der PIC laut MPLAB SIM 60 Zyklen, bei int nur 20. Wenn ich den Cast weglasse, passiert das gleiche wie wenn ich zu unsigned char caste. bcd und zahl sind beides unsigned char.
Und so wären es nur 13 Zyklen:
Ich glaube ich kann den Code nur mehr Optimieren, wenn ich ihn in ASM schreibe... 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
Noch kein Account? Hier anmelden.
|
|
Thread beobachten
Seitenaufteilung abschalten