Autor Beitrag
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: Sa 15.03.08 10:30 
Deine Aufgabenstellung habe ich jetzt konkret verpasst. Du willst Zahlen ins Dezimalsystem umwandeln? Floats/Int? Welcher Range?
BenBE Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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:
ausblenden volle Höhe C#-Quelltext
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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Mo 17.03.08 14:17 
Titel: Re: StrToInt - Wie ohne Multiplikation\Division?
[quote="user profile iconBenBE"]
Ach ja: Besagte Variante von mir:
ausblenden 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;
...

user profile iconBenBE hat folgendes geschrieben:
...brauche aber ungefähr folgende Randbedingungen:
- Keine Multiplikation** oder Division

:gruebel: Wieso habe ich die Aufgabenstellung nicht verstanden?

_________________
Na denn, dann. Bis dann, denn.
BenBE Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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.

ausblenden volle Höhe Delphi-Quelltext
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}
{aus BintoBCD http://www.htsoft.com/forum/all/showflat.php?Number=13298 }
var
  i,res,d2,d1,d0: byte;


function BintoBCD(res:byte):byte;
{ n aus [0..99] }
const
 adj_val : array[0..7of byte = (00,22,50,72,100,128,150,178);
var
  tmp : ^byte;
  adj : byte;

begin
  ADj := res;
  Adj := adj shr 4;  {SWAP Adj }
  Adj := adj AND 7;
  {adj:= adj_val[adj];}
  tmp := @adj_val;
  inc(tmp,Adj);
  adj := tmp^;

  res := res AND 15;
  res := res + adj;

  {Simuliert falls HalfCarry Gesetzt }
  {if Hc ->  res := res+6 }
  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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Do 20.03.08 10:18 
So, hab noch ein paar Optimierungen gesehen in deinem Source:

user profile iconHorst_H hat folgendes geschrieben:
ausblenden volle Höhe Delphi-Quelltext
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}
{aus BintoBCD http://www.htsoft.com/forum/all/showflat.php?Number=13298 }
var
  i,res,d2,d1,d0: byte;


function BintoBCD(res:byte):byte;
{ n aus [0..99] }
const
 adj_val : array[0..7of byte = (00,22,50,72,100,128,150,178);
var
  tmp : ^byte;
  adj : byte;

begin
  ADj := res;//Swap kan der ATmega als direkten Befehl.
  Adj := adj shr 4;  {SWAP Adj }
  Adj := adj AND 7;
  {adj:= adj_val[adj];}
  tmp := @adj_val;
  inc(tmp,Adj);
  adj := tmp^;

  res := res AND 15;
  res := res + adj;

  {Simuliert falls HalfCarry Gesetzt }
  {if Hc ->  res := res+6 } //Skip Branch If HC clear; als nächsten dann addi r, 6)
  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
//Diese Optimierung geht, weil Inc in nem register in einem Takt geht UND du dadurch ein wenig Zeit sparst ...
//Je nach dem, ob häufig dreistellige Zahlen vorkommen, kann man den Block auch mit verschachtelten Ifs darstellen
  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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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.