BCD Addition / Subtraktion auf ARM7

[Peter Pippinger (Gast)]

Hallo NG,

ARM7 hat wohl keine Möglichkeit (out of the box) BCD-Zahlen zu addieren 
/ subtrahieren?

Soweit ich weiß, stellt jedes Nibbel einen Dezimalen Wert dar (0-9).
So würde Beispielsweise:

0x09 + 0x14 als BCD-Addition 0x23 ergeben und nicht 0x1d.

Wie würdet Ihr das mit so wenigen Assembler-Befehlen wie möglich 
umsetzen?

Muss nicht gleich die fertige Lösung sein, aber ein paar Denkanstöße 
wären nett, damit ich heut abend gleich damit loslegen kann :-)
Ich dachte mir, dass man vielleicht erst mal in HEX "normal" rechnet, 
und dann zu BCD umwandelt?

MfG
Peter

[UBadi (Gast)]

Peter Pippinger schrieb:
> 0x09 + 0x14 als BCD-Addition 0x23 ergeben und nicht 0x1d.

1. Prüfen ob beide Zahlen auch wirklich BCD Zahlen sind (wenn dieser 
Schritt notwendig sein sollte.

2. Obere und Unter Nibble bei der Zahlen trennen

3. Die beiden unteren Nibble addieren

4. Prüfe ob Wert größer als 9? wenn ja 9 subtrahieren. Wert in unteren 
Nibble
   schreiben, Rest merken

5. Die Oberen beiden Nibble + Rest addieren

6. Prüfe ob Wert größer als 9? wenn ja 9 subtrahieren. Wert in oberen 
Nibble
   schreiben

7. Den Rest in den unteren Nibble einer neuen Variable schreiben und
   die beiden Nibble der ersten Zahl wieder in einem Byte zusammenführen

[(prx) A. K. (prx)]

result = 0;
if ((Low4Bits(x) + Low4Bits(y)) >= 10)
  result = 6;
result += x + y;
if (result >= (10 << 4))
  result += 0x60;

[(prx) A. K. (prx)]

Google kaputt? => http://www.cs.uiowa.edu/~jones/bcd/bcd.html

[Peter P. (uncle-sam7)]

...Danke für die Antworten.

Google ist nicht kaputt, aber ich möchte nur ungerne meine 
Emulatorleistung negativ beeinflussen. Hab mir auch schon Gedanken 
gemacht. Eventuell verwende ich einfach eine Lookup-Tabelle.

Wenn ich 0x25 + 0x25 "normal" kommt da 0x4a raus. Jetzt könnte man doch 
den passenden BCD-Wert (0x4a -> 0x50) in einer Lookuptabelle suchen, 
oder?

Wäre jetzt vom Speicher her auch kein Beinbruch, da ich eh nur ein 8-Bit 
Ergebnis benötige... Ich werde den Gedanken spätern mal weiterstricken. 
Vielleicht auch ein paar Bits im Ergebnis checken?

Bis später...

[someone (Gast)]

Peter Pippinger schrieb:
> Eventuell verwende ich einfach eine Lookup-Tabelle.
>
> Wenn ich 0x25 + 0x25 "normal" kommt da 0x4a raus. Jetzt könnte man doch
> den passenden BCD-Wert (0x4a -> 0x50) in einer Lookuptabelle suchen,
> oder?

0x10 + 0x02 = 0x12 ... lookup 0x12 => "12"
0x09 + 0x09 = 0x12 ... lookup 0x12 => "12" statt "18"

Geht nicht.

[someone (Gast)]

Bei der Lookuptabelle die Summanden benutzen geht natürlich. Das sind 
aber (n*n + n) / 2 = 5050 Kombinationen [Kommutativgesetz 
berücksichtigt]

[Dirk (Gast)]

Peter Pippinger schrieb:
> Wenn ich 0x25 + 0x25 "normal" kommt da 0x4a raus. Jetzt könnte man doch
> den passenden BCD-Wert (0x4a -> 0x50) in einer Lookuptabelle suchen,
> oder?

Nicht ganz! Nur musst Du folgendes beachten!

Du addierst BCD Zahlen !!!

Dann rechne mal folgendes:

0x25 + 0x25 = 0x4A

aber

0x20 + 0x30 = 0x50
0x10 + 0x40 = 0x50

Es gibt in jeder Summe einige Ausnahmen.
Die müsstest Du dann alle ausrechnen.

99x99 = 9801 Kombinationsmöglichkeiten bei den nicht jede Addition nur 
ein Ergebnis ausspuckt

[(prx) A. K. (prx)]

Probiers mal damit (untested):

; r2 = r0 + r1 (BCD)
mov     r2, r0, lsl #28
adds    r2, r2, r1, lsl #28
cmpcc   r2, #10 << 28
add     r2, r0, r1
addhs   r2, r2, #6
cmp     r2, #10 << 4
addhs   r2, r2, #6 << 4

[Peter P. (uncle-sam7)]

Hallo A.K.

meinen tiefen Respekt! Wirklich Hut ab. Ich bin begeistert.
Ich habe jetzt einige Tests gemacht. Die "normalen" Dinge haben sehr gut 
ausgesehen. Und wenn ich a-f mit ins Spiel bringe, verhält sich Dein 
Code wie die 6502 in den Beispielen, die ich habe.

Hast Du evtl. noch Lust, ein paar Kommentare zu den Befehlen zu 
schreiben? Mich würde das sehr interessieren, was Du da im Detail 
machst.

Also vielen Dank nochmal.

Gruß
Peter

[(prx) A. K. (prx)]

Peter Pippinger schrieb:

> Hast Du evtl. noch Lust, ein paar Kommentare zu den Befehlen zu
> schreiben? Mich würde das sehr interessieren, was Du da im Detail
> machst.

Nu, also bitte! Schnapp dir das Manual der ARM Befehle und klamüser das 
selbst aus. Sollst ja bischen was lernen dabei ;-).

PS: Das prinzipielle Verfahren hatte ich oben schon beschrieben.

[Peter (Gast)]

> Nicht ganz! Nur musst Du folgendes beachten!
>
> Du addierst BCD Zahlen !!!
>
> Dann rechne mal folgendes:
>
> 0x25 + 0x25 = 0x4A
>
> aber
>
> 0x20 + 0x30 = 0x50
> 0x10 + 0x40 = 0x50

0x25 + 0x25 = 0x4A >> Lookup = 0x50
aber
0x20 + 0x30 = 0x50 >> Lookup = 0x50
0x10 + 0x40 = 0x50 >> Lookup = 0x50

Bin mit dem Thema noch  nicht ganz durch :-)
A.K. hat je schon ne ganz beachtliche Kürze der Berechnung vorgelegt...
Ich habe das Gefühl, dass da noch was geht.

Es wäre ja dennoch ok, wenn in der Lookup-Tabelle 0x50 -> 0x50 wäre?

ich denke, dass ich mir mal auf nem c64 die Ergebnisse zusammenrechnen 
lasse (nur um sicher zu gehen, was denn da das Ergebins gewesen wäre). 
Dann werd ich die Daten mal vergleichen...

Gruß
Peter

[Peter (Gast)]

Also sowas wie:

0x00 = 0x00
0x01 = 0x01
0x02 = 0x02
0x03 = 0x03
0x04 = 0x04
0x05 = 0x05
0x06 = 0x06
0x07 = 0x07
0x08 = 0x08
0x09 = 0x09
0x0a = 0x10
0x0b = 0x11
0x0c = 0x12
0x0d = 0x13
0x0e = 0x14
0x0f = 0x15
0x10 = 0x10
0x11 = 0x11

und so weiter bis ff (256 Byte Lookups)...

[(prx) A. K. (prx)]

Peter schrieb:

> Ich habe das Gefühl, dass da noch was geht.

Durchaus möglich. Aber mit Lookup-Table wirds schwierig. Denk dran, dass 
ein Zugriff auf eine Lookup-Table im Flash je nach dessen Tempo 3-5 
Takte dauert (bei 1-3 Waitstates). Und für jede Art Lookup-Table, ob RAM 
(2 Takte) oder ROM musst du erst einmal deren Basisadresse ins Register 
kriegen. Setz das gegen die obigen 7 Takte.

[Peter Pippinger (Gast)]

A. K. schrieb:
> Peter schrieb:
>
>> Ich habe das Gefühl, dass da noch was geht.
>
> Durchaus möglich. Aber mit Lookup-Table wirds schwierig. Denk dran, dass
> ein Zugriff auf eine Lookup-Table im Flash je nach dessen Tempo 3-5
> Takte dauert (bei 1-3 Waitstates). Und für jede Art Lookup-Table, ob RAM
> (2 Takte) oder ROM musst du erst einmal deren Basisadresse ins Register
> kriegen. Setz das gegen die obigen 7 Takte.

hmm, daran habe ich noch gar nicht gedacht. Kannst Du mir bitte sagen, 
wo das genau steht (Datenblatt ist klar :-), wie lange der Zugriff 
dauert (AT91SAM7S256@48MHz)?

Die 7 Befehle von Dir sind echt die beste Lösung, die ich bislang im 
Netz gefunden habe.

Ich habe jetzt mal zum Testen folgendes gemacht, was scheinbar auch 
funktionieren würde (Tabelle noch nicht ganz aufgebaut):

<?php

$bcd = array(
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x08, 0x09, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15,

    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
    0x18, 0x19, 0x20, 0x21, 0x22, 0x23, 0x24, 0x25,

    0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
    0x28, 0x29, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35
);

$a = $bcd[0x9];
$b = $bcd[0x9];

echo dechex($bcd[$a+$b]);

?>

Man könnte die zu addierenden Werte und das Ergebnis direkt als Index 
verwenden. Tabelle müsste halt dann 0xff+0xff Byte groß sein.

Wie denkt Ihr darüber?

Viele Grüße,
Peter

[(prx) A. K. (prx)]

Peter Pippinger schrieb:

> hmm, daran habe ich noch gar nicht gedacht. Kannst Du mir bitte sagen,
> wo das genau steht (Datenblatt ist klar :-),

Die Laufzeit der Befehle findet sich in der ARM Dokumentation zum 
verwendeten Core, hier dem ARM7TDMI, zu finden bei arm.com. LDR benötigt 
2 Takte plus Waitstates, beim AT91SAM7 48MHz also 2 Takte bei Zugriff 
auf RAM, 3 Takte bei ROM.

Bei den AT91SAM7 ist zu beachten, dass nativer ARM Code nur dann volle 
Performance entfaltet, wenn der Code im RAM läuft, da das Flash keine 
ausreichende Bandbreite besitzt: 32 Bits Zugriffsbreite, 2 Takte pro 
Zugriff, das reicht nicht für einen 32-Bit Befehl pro Takt. Diese 
Controller sind im Wesentlichen für Thumb-Code konzipiert.

[Peter P. (uncle-sam7)]

Danke, werd ich dann mal prüfen...

jetzt wollte ich noch der Vollständigkeit halber sagen, dass das 
PHP-Konstrukt so wohl nicht funktionieren würde.

Habs jetzt mal in Assembler zusammengebastelt (Lookups nicht vollständig 
aufgebaut). Wären dann effektiv 4 Befehle, wenn man 2 Register 
"reservieren" könnte. Kann man da noch was kürzen? Ich denke, dass man 
sogar mit nur einem Zeiger arbeiten könnte, wenn man die Lookup-Tabellen 
alle aneinanderfügt:
Opcodes 256 Bytes
bcd2dec 256 Bytes // evtl. Zeiger für Opcodes + lsl verwenden
dec2bcd 256 Bytes // evtl. Zeiger für Opcodes + lsl verwenden

Was denkt Ihr?

  ldr r0, =0x19;
  ldr r1, =0x7;
  
  ldr r5, =bcd2dec; // könnte man evtl. reservieren
  ldr r6, =dec2bcd; // könnte man evtl. reservieren

  ldrb r0, [r5,r0]; // bcd2dec(r0)
  ldrb r1, [r5,r1]; // bcd2dec(r0)
  add r2,r0,r1      // r2 = r0 + r1
  ldrb r2, [r6,r2]; // dec2bcd(r2)
  
// -------------------------------------------------------------------
// bcd2dec lookup table
// -------------------------------------------------------------------
  ALIGNRAM 4
bcd2dec:  
  DC8 00, 01, 02, 03, 04, 05, 06, 07
  DC8 08, 09, 10, 11, 12, 13, 14, 15

  DC8 10, 11, 12, 13, 14, 15, 16, 17
  DC8 18, 19, 20, 21, 22, 23, 24, 25

  DC8 20, 21, 22, 23, 24, 25, 26, 27
  DC8 28, 29, 30, 31, 32, 33, 34, 35


// -------------------------------------------------------------------
// dec2bcd lookup table
// -------------------------------------------------------------------
  ALIGNRAM 4
dec2bcd:  
  DC8 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07
  DC8 0x08, 0x09, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15

  DC8 0x16, 0x17, 0x18, 0x19, 0x20, 0x21, 0x22, 0x23
  DC8 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x30, 0x31
  
  DC8 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39
  DC8 0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47

[someone (Gast)]

Peter schrieb:
> und so weiter bis ff (256 Byte Lookups)...

Das ist immer noch nicht eindeutig!

Wie unterscheidest du bei einer Lookup tabelle zwischen 0x09 + 0x09 und 
0x10 + 0x02. Beide ergeben herkömmlich 0x12. Nach BCD sollten allerdings 
zwei verschiedene Werte 0x18 und 0x12 herauskommen.

Eine Lookup Tabelle ohne einen Einbezug der Orginalwerte bzw zumindest 
einem Nibble-Carry funktioniert nicht.

[Peter P. (uncle-sam7)]

hmm, kann ich mir jetzt nicht vorstellen, da ich die beiden werte, die 
addiert werden zuerst von bcd nach dec über den ersten lookup auflöse. 
Das Ergebnis wird dann wieder von dec nach bcd über die zweite 
lookuptabelle aufgelöst...

[Peter (Gast)]

A. K. schrieb:
> Die Laufzeit der Befehle findet sich in der ARM Dokumentation zum
> verwendeten Core, hier dem ARM7TDMI, zu finden bei arm.com. LDR benötigt
> 2 Takte plus Waitstates, beim AT91SAM7 48MHz also 2 Takte bei Zugriff
> auf RAM, 3 Takte bei ROM.

Hallo, jetzt bin ichs nochmal...

Bei mir in der IAR-Workbench gehen die Clockcycles pro Befehl nur immer 
um 1 hoch. Kann man das einstellen, dass er die wirklich benötigten 
Clockcycles dazuaddiert? Wie macht man das normal mit dem Zählen der 
Clockcycles? Wenn das nicht geht, gibt es irgendwo nen kostenfreien ARM 
Emulator, bei dem man die Befehle Schritt für Schritt durchgehen kann 
und entsprechend die aktuellen Clockcycles und Register anschauenen 
kann?

Viele Grüße und danke für jeden Hinweis,
Peter

[(prx) A. K. (prx)]

Peter schrieb:

> Bei mir in der IAR-Workbench gehen die Clockcycles pro Befehl nur immer
> um 1 hoch. Kann man das einstellen, dass er die wirklich benötigten
> Clockcycles dazuaddiert?

Hier nix IAR, keine Ahnung.

> Wie macht man das normal mit dem Zählen der Clockcycles?

Finger? Hände? Bei den paar Befehlen sollten die noch reichen.

Kannst natürlich auch die reale Maschine und einen Timer bemühen. Das 
ist besonders nützlich bei Sequenzen, die sich in vereinfachenden 
Simulatoren nicht sauber darstellen, wie beispielsweise beim Einfluss 
von Flash-Puffern und Buskonflikten.

[Peter (Gast)]

A. K. schrieb:
>> Wie macht man das normal mit dem Zählen der Clockcycles?

> Finger? Hände? Bei den paar Befehlen sollten die noch reichen.
naja, das mit den Händen würde ich wahrscheinlich hinbekommen, solange 
es keine BCD-Zahlen sind ;-)

Ich finde da geht der Spaß dabei verloren. Das wäre ja schon fast so, 
als würde ich das Programm im Hex-Editor schreiben...

> Kannst natürlich auch die reale Maschine und einen Timer bemühen. Das
> ist besonders nützlich bei Sequenzen, die sich in vereinfachenden
> Simulatoren nicht sauber darstellen, wie beispielsweise beim Einfluss
> von Flash-Puffern und Buskonflikten.

Hört sich kompliziert an.

Werd mal schauen, ob man das in IAR einstellen kann. Das würde ja m.E. 
durchaus Sinn machen. Man kann ja soweit ich weiß auch den verwendeten 
Core einstellen. Bin mir aber nicht ganz sicher.

Gruß
Peter