Schnelle 8-Bit Binär nach BCD für 8Bit-AVR

[Christof Rieger (Gast)]

Hi,
hier ein Kleiner Aufruf zum Wettkampf, wer kann es schnller 8-Bit Binär 
in BCD wandeln. Eine gewöhnliche Routine mit Schleifen benötigt auf dem 
8-Bit AVR je nach zu wandelder Zahl 9 bis 64 Taktzyklen (Dafür aber sehr 
kompakter Code). Meine Vorschlag benötigt 7 bis 42 Taktzyklen. In beiden 
Fällen ohne call und ret gezählt.

Register r15;r16;r17;r18
Argument: r16: Binärwert
Ergebnis: r15: Hunderter; r16 HighNibbel: Zehner; r16 LowNibbel: Einer

BIN2BCD:
  clr r15
BIN2BCDL:        ;Hunderter in r15 schreiben
  cpi r16,100    ;maximal 2 Durchläufe
  brlo BIN2BCD1
  subi r16,100
  inc r15
  rjmp BIN2BCDL
BIN2BCD1:        ;Prüfen ob 96 bis 99 bzw. 196 bis 199
  cpi r16,0x60
  brlo BIN2BCD2
  subi r16, -0x36    ;wenn ja nur 0x36 addieren
  ret      ;r16 HighNibbel Zehner LowNibbel Einer
BIN2BCD2:        ;sonst LowNibbel isolieren
  mov r17,r16
  andi r17,0b00001111
  cpi r17,10
  brlo BIN2BCD3    ;Wenn LowNibbel größer 9  
  subi r17,-6    ;Dezimaladjust durchfüren
BIN2BCD3:
  clr r18      ;Da der Rest kleiner 96 ist
  sbrc r16,6    ;kann nur 2^6
  subi r18,-0x64    ;sprich 6 Zehner und 4 Einer
  sbrc r16,5    ;oder 2^5
  subi r18,-0x32    ;sprich 3 Zehner und 2 Einer
  add r17,r18    ;vorhanden sein.
  mov r18,r17    ;BCD aus LowNibbel dazu addieren
  andi r18,0b00001111  ;Prüfen ob Dezimaladjust nötig.
  cpi r18,10
  brlo BIN2BCD4  
  subi r17,-6
BIN2BCD4:
  sbrc r16,4    ;zuletzt noch 2^4 prüfen    
  subi r17,-0x16    ;entsprich 1 Zehner und 6 Einer
  mov r16,r17
  andi r17,0b00001111  ;Prüfen ob Dezimaladjust nötig.
  cpi r17,10
  brlo BIN2BCD5  
  subi r16,-6    ;r16 HighNibbel Zehner LowNibbel Einer
BIN2BCD5:
  ret

[Simon K. (simon)]

Mit dem Klassiker Lookup-Table komme ich auf 12 Takte statische 
Laufzeit.

Assembler Code (Ohne die Initialisierung vom Y Pointer)

  uint8_t Bin = 233;

  volatile uint16_t BCD = pgm_read_word(&BcdTab[Bin]);
 29c:  e6 e2         ldi  r30, 0x26  ; 38
 29e:  f2 e0         ldi  r31, 0x02  ; 2
 2a0:  85 91         lpm  r24, Z+
 2a2:  94 91         lpm  r25, Z+
 2a4:  9a 83         std  Y+2, r25  ; 0x02
 2a6:  89 83         std  Y+1, r24  ; 0x01

[Peter D. (peda)]

Die erste Frage ist, wozu braucht man gepacktes BCD von einem Byte. Ich 
habe es bisher nirgends gebraucht.

Meistens braucht man größeren Zahlen (2 oder 4 Byte) und dann nicht als 
gepacktes BCD sondern ASCII oder 7-Segment. Dann müßte man die gepackten 
Nibble erst wieder mühsam auseinanderfummeln.



Die zweite Frage ist, welches Auge+Gehirn ist in der Lage, Zahlen 
innerhalb weniger µs zu erfassen?

Der Mensch ist >10.000-mal langsamer als der MC, daher ist für 
Zahlenausgaben immer die codeoptimierte Lösung am effektivsten.
Ob ein Ausgabe nun 0,001% oder 0,002% CPU-Last bewirkt, interessiert 
nicht die Bohne.


Peter

[Simon K. (simon)]

Peter Dannegger wrote:
> ...

Du kannst aber auch echt jedem den Spaß vermiesen ;)

Wenn der Controller erstmal genug zu tun hat, dann kommt es vielleicht 
doch hier und da noch ein bisschen auf die Geschwindigkeit an.

Wenn man dann plötzlich 1000000 Zahlen nach BCD umwandeln will, fällt's 
doch ins Gewicht ;)

[Peter D. (peda)]

Simon K. wrote:

> Wenn man dann plötzlich 1000000 Zahlen nach BCD umwandeln will, fällt's
> doch ins Gewicht ;)

Nö, die CPU-Last ist ganz genau die gleiche (nämlich nicht 
erwähnenswert).

Sie hängt nicht von der Anzahl Werte ab, sondern von dem Verhältnis der 
Zeiten, die der MC braucht, um sie darzustellen und die der Mensch 
braucht, um sie abzulesen.

Bei 1000000 Zahlen braucht der Mensch eben mehrere Tage zum Ablesen.

Ich benutze dazu oft ne Timertask die nur alle 200ms nen neuen Wert 
ausgibt, damit die Anzeige ablesbar bleibt, sonst sieht man ja nur 
flackernde Achten.


Peter

[Simon K. (simon)]

Peter Dannegger wrote:
> Bei 1000000 Zahlen braucht der Mensch eben mehrere Tage zum Ablesen.

Vielleicht will er die Zahlen ja nicht ablesen sondern irgendwo 
speichern... ;)

[Peter D. (peda)]

Simon K. wrote:

> Vielleicht will er die Zahlen ja nicht ablesen sondern irgendwo
> speichern... ;)

Dann macht es natürlich Sinn, sie erstmal durch BCD-Wandlung unnötig 
aufzublähen ;)


Peter

[Christof Rieger (Gast)]

Die Aufgabe hat eher ein sportlichen Aspekt.
Zur Frage:"Für was eine 8-Bit Umwandlung"
Wenn ich eine Prozentwert auf einem Display ausgeben will, genügt mir 
eine 8-Bit Umwandlung.
Zur Frage:"Warum schnell"
Es gibt Situationen in denen es sinnvoll ist einen Prozess vor dem 
nächsten Interrupt abzuschließen um sich z.B. eine evetuelle 
Zwischenspeicherung von Werten zu sparen, dass auch wieder Zeit kostet.
Desweiteren gibt es hier einige Projekte die aus einem Mega8 ein 
Schwarz-Weiß Fernsehbild raus kitzel. Hier kann es sinnvoll sein, die 
BCD-Umwandlung und die Zeichenaufbereitung innerhalb eine 
Zeilenaustastung abzuschließen.

Liebe Grüße Christof

PS: Es gibt viele Freizeitbeschäftigungen die nicht wirklich einen Sinn 
machen aber sie machen einfach Spaß.

[Christof Rieger (Gast)]

@Simon
Ich glaube, noch schneller geht es kaum. Gut ist auch, dass jede 
Wandlung die gleich dauer hat. Allerdigs sind 524 Bytes für die 
kleineren AVR'ne menge Holz.

Aber moment, die Perversion ist noch steigebar.

Binwert in ZL:

  ldi ZH, High(TabellenBasis) ;(Low(TabellenBasis) muß 0 sein!)
  ijmp

TabellenBasis:
  rjmp BCD_1
  .
  .
  rjmp BCD_256

Ein Tabelleneintrag von 256:
BCD_X:
  ldi r16,(Passeder Zehner/Einer)
  ldi r17,(Passender Hunerter)
  ret

7 Zyklen ohne call und ret !
Wenn ZH Grundsätzlich vorbelegt bleiben kann, dann sogar nur 6 Zyklen ! 
Aber dafür satte 2052 Bytes verschlungen

[Benedikt K. (benedikt)]

Unter Verwendung eines externen 256x16bit ROMs, dessen Adressen an PORTA 
und die Daten an PORTB & PORTC angeschlossen sind:
out PORTA, r16
nop
in r16, PINB
in r17, PINC

Benötigt nur 4 Takte und 8 Bytes, aber halt ein externes ROM und 24 IO 
Pins...

[Christof Rieger (Gast)]

O.K. !!!!!!!!!!!!!!!!!!!
Da Sprach der Elektrotechniker. Ich kann mich dunkel erinnern. Benedikt 
K. baut gerne schnelle Hardware und nutzt den AVR nur zur Steuerung der 
Hardware.
Wenn du einen CPLD oder FPGA mit entsprechender Programmierung dran 
hängst, kannst du die auch noch den NOP sparen ;-)

Interesannt wären aber noch Lösungen die weniger als 512 Bytes 
verschlingen und ohne externe Hardware auskommen und unter 42 Takten 
liegt.

[Benedikt K. (benedikt)]

Es gäbe da noch die Möglichkeit einer Mischung aus deiner Lösung und der 
von  Simon:
Die Hunderter vergleichen (sind ja nur 2 Vergleiche), und die Zener und 
Einer über Tabelle machen. Benötigt 100Bytes für die Tabelle + ein paar 
für den Code. Sollte also mit etwa mit etwa 130-140Bytes und rund 20 
Takten machbar sein.

[Christof Rieger (Gast)]

Änderung am Post 1.
Die Berechnug der Hunderter ersätzen. Takte 8-35. Der Code verlängert 
sich um 6 Bytes (3 Instructions).

BIN2BCD:
  clr r15
  subi r16,100
  brlo BIN2BCDE
  inc r15
  subi r16,100
  brlo BIN2BCDE
  inc r15
  rjmp BIN2BCD1
BIN2BCDE:
  subi r16,-100

[Christof Rieger (Gast)]

@Benedikt

Das sähe dann so aus:
Argument in ZL

BIN2BCD:
  clr r15
  subi ZL,100
  brlo BIN2BCDE
  inc r15
  subi ZL,100
  brlo BIN2BCDE
  inc r15
  rjmp BIN2BCD1
BIN2BCDE:
  subi ZL,-100
BIN2BCD1:
ldi  ZH, High(BasisTabelle) ;BasisTabelle mit Low(BasisTabelle)=0
lpm  r16, Z
ret

9-13 Takte und 122 Bytes wie immer ohne call und ret
Wenn ZH vorbelegt bleiben kann
8-12 Takte und 120 Bytes.

[Simon K. (simon)]

Gute Idee! Wie du siehst muss man stark abwägen, welcher Verbrauch von 
ROM und Rechenleistung für den speziellen Fall am besten ist. Du 
schriebst in deinem ersten Post nur von "schnellste" Version. Da habe 
ich dann natürlich nicht mit dem ROM geknausert ;)

[Christof Rieger (Gast)]

@Simon

So etwas entwickelt sich! Ich konte ja beim schreiben des ersten 
Beitrags noch nicht ahnen, welche Ansätze kommen werden. Der Beitrag 
wird auf jedem Fall der Rubrik Code-Sammlung gerecht. Wenn jetzt jemand 
nach so einer Routine sucht kann er schon die passende für seine 
Anwendug raussuchen. Bin mal gespannt was noch für Ideen kommen.

Ersteinmal Danke an Alle

[Christof Rieger (Gast)]

Argument in r17

BIN2BCD1:
  clr r15
  mov ZL,r17
  swap ZL
  andi ZL,0b00001111
  ldi  ZH, High(BasisTabelle) ;BasisTabelle mit Low(BasisTabelle)=0
  lpm  r16, Z
  lsl r16
  rol r15
  andi r17,0b00001111
  subi r17,-6
  brhc BIN2BCD1    ;Wenn LowNibbel kleiner 10  
  subi r17,6       ;kein Dezimaladjust durchfüren
BIN2BCD1:
  add r16,r17
  brhc BIN2BCD2    ;Wenn HalfCarry
  subi r16,-6      ;auf jeden Fall ein Dezimaladjust
  rjmp BIN2BCD3    ;LowNibbel ist hier immer kleiner 10
BIN2BCD2:
  subi r16,-6
  brhc BIN2BCD3    ;Wenn LowNibbel kleiner 10
  subi r16,6       ;kein Dezimaladjust durchfüren
BIN2BCD3:
  subi r16,-0x60   
  brcs BIN2BCD4    ;Wenn HighNibbel größer 9
  inc r15          ;ein Hunderter mehr
  ret
BIN2BCD4:
  subi r16,-0x60   ;Wenn nicht, kein Dezimaladjust
  ret
.org 0xy0/8
.db 0x00,0x0B,0x19,0x24,0x32,0x40,0x4B,0x89
.db 0x94,0xA2,0xB0,0xBB,0xC9,0xD4,0xE2,0xF0
;Bit 7 => Dezimaler Hunderter
;Bit 3-6 => Zehner Binär
;Bit 0-2 => Hälfte der Dezimalen Einer
;Das HighNibbel hat niemals einen Ungeraden Einer

22-24 Takte  66 Bytes Damit Kürzer und Schneller als mein Erster 
Vorschlag
ich hoffe das geht auch habe es nicht getestet ;-)

[Peter D. (peda)]

Christof Rieger wrote:
> Desweiteren gibt es hier einige Projekte die aus einem Mega8 ein
> Schwarz-Weiß Fernsehbild raus kitzel. Hier kann es sinnvoll sein, die
> BCD-Umwandlung und die Zeichenaufbereitung innerhalb eine
> Zeilenaustastung abzuschließen.

Sinnvoll ist dann aber nicht als packed BCD sondern als ASCII zum 
Adressieren des Zeichengenerators.

Sinnvoll ist dann aber die Wandlung einmal im Main, wenn sich die Zahl 
ändert und nicht in jedem Bildaufbau neu. Man muß ja die Rechenzeit 
nicht mit Gewalt vergeuden.
Die Optimierung eines Algorithmus nützt garnichts, wenn man ihn dann 
unnötiger Weise viel oft ausführt.

Hier mal die auf Effizienz (=Codesparend) getrimmte Version:

packed_bcd:
        ldi     r17, -1         ; ldi r18, '0'-1
_pbcd1:
        inc     r17             ; inc r18
        subi    r16, 100
        brcc    _pbcd1
        ldi     r18, 0xA0       ; ldi r17, '0'+10
_pbcd2:
        subi    r18, 0x10       ; dec r17
        subi    r16, -10
        brcs    _pbcd2
        or      r16, r18        ; subi r16, -'0'

; 9 .. 53 cycle, 9 words

Bis auf die 5 geänderten Zeilen entspricht sie der (sinnvolleren) 
ASCII-Ausgabe.


Die Frage stellt sich aber weiterhin, wozu man packed BCD überhaupt 
brauchen könnte?


Peter

[Christof Rieger (Gast)]

Peter,
gefällt mir auch gut, die Zeile
or      r16, r18        ; subi r16, -'0'
schenke ich dir. Es hängt sowiso von der Anwendug ab, ob gepackt oder 
ungepakt gebraucht wird.

Was mich etwas fuchst, dass ich nicht selbst darauf gekommen bin, mal 
über subtrahieren und mal über addieren die Hunderter und Zehner zu 
bestimmen.

Was natürlich auch die Takt-Bilanz verbessrt ist die Möglichkeit der 
direkten ASCII-Codierung wenn man sie zur Ausgabe benötigt.

Die Umwandung eines Pached BCD braucht

r16:LowBCD r17:HighBCD

mov r18,r16
andi r16,0b00001111
subi r16,-'0'
swap r18
andi r18,0b00001111
subi r18,-'0'
subi r17,-'0'

auch nochmal 7 Takte und weitere 7 Words