Autor |
Beitrag |
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Fr 14.03.08 22:18
Hi,
Im Praktikum arbeite ich derzeit mit einem kleinen Mikrocontroller (ATmega128, dürften einige sicherlich kennen). An diesem Controller hängt über TWI\I²C ein Display, auf dem ich einige Status-Werte ausgeben möchte.
Nun zum Problem: Der Controller kennt kein Mul und auch kein Div: D.h. Multiplikation und Division müssen in Software gerechnet werden. Somit ist to Bibliotheks-Funktion von C (itoa), die sichdieser Methode bedient, furchtbar lahm (pro Ziffer ~ 1.2% Systemlast - zzgl. weiterem Overhead).
Ich suche nun nach einer Möglichkeit, die Zahlen schneller darstellen zu können, brauche aber ungefähr folgende Randbedingungen:
- Keine Multiplikation** oder Division
- Lookup-Tables dürfen verwendet werden
- Reentrant
- Sehr viele Temp-Variablen möglich (der Controller hat 32 8-Bit-Register; davon 4 als 16-Bit kombinierbar)
- Möglichst auf Byte-Ebene operierend*
- möglichst KEIN RAM verbrauchen (hab nur noch ca. 1KB verfügbar ...)
Zusätzlich wäre folgendes Wünschenswert:
- Konvertierungszeit wenn möglich konstant
*Der Controller kann nur bei Konstanten (Immediates) 16-Bit addieren\subtrahieren, sonst nur 8 Bit
**Multiplikation 8x8 Bit möglich, nicht jedoch 16x16 oder 32x32 Bit, Division überhaupt nicht
Zu meinem Ansatz:
In einer Lookup-Table sind für jede Stelle die Grenzwerte (10, 20, 30, ..., 100, 200, 300, ..., 1000, ...) enthalten, die Byteweise verglichen werden; sobald ich weiß "Zahl >= Wert in Tabelle" trag ich diesen ein und subtrahieren den Wert aus der Lookup-Table.
Vorteile:
+ Erfüllt Rahmenbedingungen
+ Nahezu konstante Zeit erreichbar
Nachteil:
- Worst-Case für kleine Zahlen (viel Overhead)
- Recht hoher ROM-Verbrauch (für Lookup-Tabellen: 9*10*4Byte = 360 Byte)
- Benötigt teilweise 16- und 32-Bit-Operationen
Wer genaueres zum Controller wissen möchte: hier.
Würde mich auf jeden Fall über Anregungen und Optimierungen freuen. Bitte wenn möglich in Delphi oder C programmieren (oder AVR-Assembler  ).
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
Zuletzt bearbeitet von BenBE am Fr 20.03.09 14:30, insgesamt 1-mal bearbeitet
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Sa 15.03.08 10:06
Hallo,
bei der Berechnung von Pi habe ich doch mal ein Programm zur Basisumwandlung angegeben.
Nur Additionen und braucht nur den doppelten Platz der Stellenzahl und ein paar zusätzliche Variablen.
www.delphi-forum.de/...ight=basisumwandlung
Gruß Horst
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Sa 15.03.08 10:30
Deine Aufgabenstellung habe ich jetzt konkret verpasst. Du willst Zahlen ins Dezimalsystem umwandeln? Floats/Int? Welcher Range?
|
|
BenBE 
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Sa 15.03.08 10:32
@Aufgabenstellung: Geht um Integers 16 und 32 Bit, Floats hat man typischer Weise auf einem Controller noch weniger
@Horst: Thx, ich wusste doch, dass wir in die Richtung schon mal was hier in der Sparte hatten. Werd es bei Gelegenheit mal portieren und mich melden.
Ich nehme aber auch noch andere Vorschläge entgegen ^^
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Sa 15.03.08 10:43
Ganz unten hat's vielleicht paar Routinen, die interessant sein könnten (z.B. die div10 ganz unten. Dort erhältst du /10 + Rest):
pheatt.emporia.edu/c...mal%20Conversion.htm
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Sa 15.03.08 12:11
Hallo,
ich habe mal meine gepostete Version von BasisUmwandlung getestet , ach die lief ja überhaupt nicht.... RangeCheck Error abfrage brachte es an den Tag. schaem...
Die zweite Basis sollte also kleiner als die Hälfte der ersten sein dann kann man die Variablen Vergleich und Sum bei tZiffer lassen.
Bei meiner nicht geposteten Assemblerversion konnte man ja noch das Carry-Flag nutzen.
Hier eine korrigierte Version für Turbo Pascal.
Gruß Horst
Einloggen, um Attachments anzusehen!
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Sa 15.03.08 20:38
Hallo,
da fällt mir noch etwas ein.
Bei dieser Seite mit C für PIC 16/8F...
www.htsoft.com/forum...lat.php?Number=13298
stand etwas von DivMod100
Genau dies hatte ich mal komponiert, weil jemand unbedingt longint in DX:AX in einen String ausgeben wollte.Dort auch mittels Tabelle für die Zahlen von 0..99.
DIVMOD100 arbeitet für Zahlen in DX:AX > 6553599 ( =65536*100-1 ) ohne MUl und DIV.
1/25= 41*(1-1/1024+1/1024^2-1/1024^3+..-..+ ) und
1/100 = 1/25/4 alles schoen mit shiften.
1/1024 bedeutet 3 Dezimalen mehr Genauigkeit pro Schritt, das fand ich imposant.
www.softgames.de/for...ge29878-0-asc-0.html
Ein einzelner Aufruf für Zahlen > 1e9 kostet ~86 Takte beim PentiumM 1.7 Ghz.(WinXP.TurboPascal ist schliesslich 16-bit Code )
Natürlich shiftet der AVR nur mit 8 Bit
Gruß Horst
P.S.
1.2% Last pro Ziffer ergibt für mich keinen Sinn.
Wieviele Taktzyklen schon eher.
P.S.S
Meine Basisumwandlung wandelt am sinnvollsten mit Lookup Tabelle also am besten von Basis1 256 zu Basis2 100.
Ob die Laufzeit so toll ist weiß ich nicht.
Für jede der 32 BitStellen werden im Schnitt 3*2.5 Additionen ( 10 Dezimalen(5 Stellen zur Basis 100) ) aber immer nur bis MaxIndex ) ausgeführ und einmal kopieren und loeschen also 5*2.5 also eher 5*3 = 15
Operationen insgesamt also 32*15 Takte mit etwas drumherum für Vergleiche und Schleifen,Sprünge also Minimum 32*25 = 800 Takte für eine 32 Bit-Zahl.
Dann fehlt noch die Umwandlung per LookUp.
Bei 1 Mhz wäre das geratene 1%  für 10 Ziffern ( 2^32-1)
P.S.S.S
Es geht immer um positive Zahlen. Die negativen kann man ja leicht umwandeln und ein Flag für die Ausgabe von "-" nutzen.
EDIT
www.avr-asm-tutorial.../quellen/konvert.asm
|
|
BenBE 
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Mo 17.03.08 14:05
So, hab mich heut mal rangesetzt, und die Performance der neuen Routine (Variante von delfiphans Link) funktioniert super. Hab mir auch ne Variante für 8-Bit-Int nach ASCII daraus geschrieben, die für den Auslastungswert der CPU sauber funktioneirt.
Exakte Befehls-Timings mess ich nachher im Simulator noch aus; laut Anzeige des OS ist's aber schon erheblich besser geworden. Ich informiere euch weiter ...
Ach ja: Besagte Variante von mir:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37:
| inline INT8U *fast_itoa_b( INT8U n, INT8U *buf, INT8U bufsize ) { if(bufsize < 2 || !buf) { return NULL; } if(bufsize < 4) { *buf = 0; if(3 == bufsize && n > 99) { return buf; } if(2 == bufsize && n > 9) { return buf; } }
INT8U d2, d1, d0, q; INT8U *tmp = buf;
d1 = (n>>4) & 0xF;
d0 = 6*d1 + (n & 0xF); q = (d0 * 0x19A) >> 12; d0 = d0 - 10*q;
d1 = q + d1; q = (d1 * 0x19A) >> 12; d1 = d1 - 10*q;
d2 = q;
if(d2) *tmp++ = d2 + '0'; if(d2 || d1) *tmp++ = d1 + '0' ; if(d2 || d1 || d0 || (!d0 && !d1 && !d2)) *tmp++ = d1 + '0';
*tmp = 0; } |
Wer jetzt meint, da sind Variable überflüssig: der AVR-GCC optimiert an der Stelle sauber und so ist der Source übersichtlicher.
Timings folgen nachher.
Edit: Ok, hier die Timings: Die Routine kommt auf folgende Taktzeiten:
1 Ziffer Ausgabe: 91 Taktzyklen (6,1µs)
2 Ziffern Ausgabe: 94 Taktzyklen (6,3µs)
3 Ziffern Ausgabe: 96 Taktzyklen (6,4µs)
Insgesamt also <10µs für die Konvertierung... und dabei nahezu konstant in der Konvertierungszeit.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
Zuletzt bearbeitet von BenBE am Mo 17.03.08 14:32, insgesamt 1-mal bearbeitet
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Mo 17.03.08 14:17
Titel: Re: StrToInt - Wie ohne Multiplikation\Division?
[quote=" BenBE"]
Ach ja: Besagte Variante von mir:
C#-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
| inline INT8U *fast_itoa_b( INT8U n, INT8U *buf, INT8U bufsize ) ... INT8U d2, d1, d0, q; INT8U *tmp = buf;
d1 = (n>>4) & 0xF;
d0 = 6*d1 + (n & 0xF); q = (d0 * 0x19A) >> 12; d0 = d0 - 10*q; ... |
BenBE hat folgendes geschrieben: | ...brauche aber ungefähr folgende Randbedingungen:
- Keine Multiplikation** oder Division |
 Wieso habe ich die Aufgabenstellung nicht verstanden?
_________________ Na denn, dann. Bis dann, denn.
|
|
BenBE 
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Mo 17.03.08 14:37
Siehe die Sternchen ... Außerdem würde an besagter Stelle auch ein Shifting-Konstrukt gehen, wodurch die Multiplikation auch umgangen wäre. Wollte damit nur vermeiden, dass mir Leute mit Algorithmen kommen, die haufenweise auf Multiplikation aufsetzen. Außerdem hatte ich das Datenblatt nicht umsonst angehängt, damit man im Zweifelsfall auch selber kurz gucken kann zwecks Befehlssatz. Ging hier wirklich hauptsächlich drum, das ganze so zu schreiben, dass es bestimmte Operationen nicht unnötig in Software emuliert, sondern diese so effizient wie möglich abarbeitet.
Ich arbeite bei besagten Projekt mit einem Echtzeit-System, da kann ich mir bestimmten Overhead nicht leisten.
MfG,
BenBE.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 17.03.08 23:04
Hallo,
Die Funktion funktioniert jetzt aber nur für Byte Werte.
Für Byte Werte ginge doch auch ein einfacher Test auf die größte Stelle
>200, > 100 umd d2 zu bestimmmen und entsprechend 200 oder 100 abzuziehen.
Dann aus einer grossen Tabelle den BCD Wert auslesen oder berechnen:
mittels BintoBCD wie ganz unten bei www.htsoft.com/forum...lat.php?Number=13298 angegeben.
Aus BCD den String zu formen ist ja nicht schwer.
Als Gag mal Befehl für Befehl.
Bis zum write sind es 17 Zeilen, also etwas über 20 Takte, jen achdem wie lange der indizierte Zugriff dauert.
Man muss nur noch d0 und d1 aus res erzeugen.
Damit kommt man sicher unter 50 Takte.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88:
| program nichts;
{$Apptype console}
var i,res,d2,d1,d0: byte;
function BintoBCD(res:byte):byte;
const adj_val : array[0..7] of byte = (00,22,50,72,100,128,150,178); var tmp : ^byte; adj : byte;
begin ADj := res; Adj := adj shr 4; Adj := adj AND 7; tmp := @adj_val; inc(tmp,Adj); adj := tmp^;
res := res AND 15; res := res + adj;
adj := res; adj := adj XOR adj; adj := adj AND 16; if adj <> 0 then res := res+6;
adj := res; adj := adj AND 15; if adj > 9 then res := res+6; BintoBCD := res; end;
procedure itoa_b(res:byte); Label SprungMarke;
var d2,d1,d0:byte; begin d2 := 0+ord('0'); if res >199 then begin d2:= 2+ord('0'); res := res-200; GOTO SprungMarke; end; if res >99 then begin d2:= 1+ord('0'); res := res-100; end;
SprungMarke: res := BintoBCD(res);
d0 := res; d0 := d0 AND 15; d0 := d0+ord('0');
d1 := res; d1 := res shr 4; d1 := d1+ord('0');
write(chr(d2):2); write(chr(d1):1); write(chr(d0):1); end;
begin for i := 0 to 255 do begin write(i:4); itoa_b(i); end; writeln; end. |
Gruß Horst
EDIT:
Das Programm lässt sich wohl leicht in Assembler übersetzen.
Man kann auch die Variable tmp und res im Speicher an der Stelle von Pos speichern um Register zu sparen.
EDIT2:
Nochmals geändert. Ich muß wohl doch mal AVR Studio Installieren...
Ich glaube, das ist schneller als 50 Takte
|
|
BenBE 
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Do 20.03.08 10:18
So, hab noch ein paar Optimierungen gesehen in deinem Source:
Horst_H hat folgendes geschrieben: | 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84:
| program nichts;
{$Apptype console}
var i,res,d2,d1,d0: byte;
function BintoBCD(res:byte):byte;
const adj_val : array[0..7] of byte = (00,22,50,72,100,128,150,178); var tmp : ^byte; adj : byte;
begin ADj := res; Adj := adj shr 4; Adj := adj AND 7; tmp := @adj_val; inc(tmp,Adj); adj := tmp^;
res := res AND 15; res := res + adj;
adj := res; adj := adj XOR adj; adj := adj AND 16; if adj <> 0 then res := res+6;
adj := res; adj := adj AND 15; if adj > 9 then res := res+6; BintoBCD := res; end;
procedure itoa_b(res:byte); var d2,d1,d0:byte; begin d2 := ord('0'); if res > 199 then begin inc(d2); res := res-100; end; if res > 99 then begin Inc(d2); res := res-100; end;
res := BintoBCD(res);
d0 := res; d0 := d0 AND 15; d0 := d0+ord('0');
d1 := res; d1 := res shr 4; d1 := d1+ord('0');
write(chr(d2):2); write(chr(d1):1); write(chr(d0):1); end;
begin for i := 0 to 255 do begin write(i:4); itoa_b(i); end; writeln; end. |
Gruß Horst |
Das wären meine kleinen Ergänzungen dabei ... was sagt die Taktzyklenzahl?
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 20.03.08 19:05
Hallo,
ich habe es nicht nicht AVR assembler umgesetzt.
Habe mal AVRco-Pascal genommen, mit nicht ermutigendem Ergebnis.
Scheinbar sind die Register extrem volatil, jedenfalls werden die ständig gerettet.
Zudem ist die Taktzyklenbestimmung im Simulator sehr ungenau. (BreakPoint itoa und folgendes endfor )
170(2 Dezi)/138(1 Dezi) bei 1 Mhz und 270/226 bei 20 Mhz kann ja wohl nicht sein.
Man müßte also Zeilen zählen.
In BintoBCD kann man eigentlich das HC-Flag in asm ausnutzen, was etwas spart.
Auch übersetzte der Compiler > 199 zu zwei Sprungbefehlen und >= 200 zu einem.
Ich die Variablen nur deshalb global gemacht, damit ich sie bei Einzelschritt überwachen konnte. ( Da hatte ich einen blöden Tippfehler drin.. )
In der asm und lst Datei sieht man den riesigen Aufwand beim speichern der Zeichen.
Gruß Horst
Einloggen, um Attachments anzusehen!
|
|
BenBE 
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Do 20.03.08 23:45
Schau ich mir Dienstag bei Gelegenheit mit an.
Wobei der Simulator, der zum AVRstudio mit zu ist, recht gut geht. BTW: Takt ist 14.7456 MHz auf dem Board; das hochrechnen geht aber zur Not auch so.
Das die Register sehr volatile sind, kann ich nicht bestätigen. Bei GCC sollte man eigentlich immer mit -Os oder -O2 compilieren; der dabei resultierende Code ist etwa auf dem Niveau des Delphi-Compilers und soweit ich das beurteilen kann, schon ziemlich gut optimiert.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
|