bin2bcd, effektiverer Code ?1?

[Ralph S. (jjflash)]

Warum auch immer (der Hintergrund ist hier nicht gefragt und deshalb 
bitte keine "Sinnfrage") stellt sich mir die Frage der 
Ausführungsgeschwindigkeit für eine BIN2BCD Funktion. Mein eigentliches 
Programm in dem ein Konverter benötigt wird, habe ich verändert, sodass 
dort die Geschwindigkeit keine Rolle mehr spielt.

Meine Funktionen sind diese hier (und werden momentan in einem AVR 
System verwendet). Ganz gezielt die Division- und Modulodivision sind 
mir hier ein Dorn im Auge, weil ich genau weiß, dass AVR keine 
Hardwaredivision besitzt:

uint32_t bin2bcd(uint32_t bin, uint8_t diganz)
{
  int bcd, dig, i;

  bcd= 0;
  
  for (i= 0; i < diganz; i++) 
  {
    dig = bin % 10;
    bin = bin / 10;
    bcd = (dig << (i << 2)) | bcd;
  }
  return bcd;
}

uint8_t byte2bcd(uint8_t bin)
{
  uint8_t bcd;
  
  bcd= bin % 10;
  bcd |= (bin / 10) << 4;
  return bcd;
}

Also, geht das besser, im Besonderen die Konvertierfunktion für einen 
8-Bitwert (und außer, dass man das auch in ein define packen kann und 
sich so den CALL und den RET sparen kann)?
Mir geht es hier vor allem um die Logik und nicht darum, etwas mittels 
Inline-Assembler zu machen.

[Walter (Gast)]

der konvertierbare Zahlenbereich ist etwas eingeschränkt

[Walter (Gast)]

und zu deiner Frage:
wenn Geschwindigkeit keine Rolle spielt kannst du auch subtrahieren

[ein Array vielleicht (Gast)]

Willsd du binäre Darstellung als eine Zahl direkt abspeichern? Alle 8 
Bits (oder gar mehr)?

Das passt in uint8_t nicht rein. Auch nicht in eine int-Variable (beim 
AVR).


Am PC könnte man mit auch so vorgehen:

#include <stdlib.h>
#include <stdio.h>

int
nibble2bcd (int bin)
{
   switch (bin) {
      case 0:
         return 0;
      case 1:
         return 1;
      case 10:
         return 2;
      case 11:
         return 3;
      case 100:
         return 4;
      case 101:
         return 5;
      case 110:
         return 6;
      case 111:
         return 7;
      case 1000:
         return 8;
      case 1001:
         return 9;
   }

   return 0;
}

int
byte2bcd (int bin)
{
   return nibble2bcd (bin / 10000) * 10 +
          nibble2bcd (bin % 10000);
}

int
main (void)
{
   int x = 10001001; // BCD: 89

   printf ("bcd:%d\n", byte2bcd (x));

   return EXIT_SUCCESS;
}

aber am PC passt sowas wie

int x = 10001001;

 auch in den Wertebeich.

Vielleicht lieber als Array abspeichern?

[ein Array vielleicht (Gast)]

ein Array vielleicht schrieb:
> int x = 10001001;

Ach so, und mit einer 0 darf die Zahl dann auch nicht anfangen, sonst 
würde das als eine Oktalzahl interpretiert;

int x = 01001; // octal!

Die Darstellung ist also irgendwie nicht optimal.

[W.S. (Gast)]

Ralph S. schrieb:
> Warum auch immer

Mir erschließt sich der Zweck deiner Funktion nicht. Immerhin soll 
diese ein Argument unsigned long bekommen und ebenso ein Ergebnis 
unsigned long liefern.

Bedenke mal, daß sowas wie BCD und Konsorten lediglich Darstellungen 
sind für den menschlichen Gebrauch, wo bei genauerer Betrachtung eine 
Anzahl von Bitkonstellationen im Argument keinen Sinn ergeben.

Wenn das eine Vorbereitung für eine E/A-Konvertierung werden soll, dann 
arbeite mit einem Feld von Textzeichen.

Und nochwas: Wenn du schon Modulo und Division direkt nebeneinander 
verwendest, dann ist das vom Rechenaufwand so etwa das Doppelte, als 
wenn du nur einmal 'ldiv' verwendest.

W.S.

[Tilo R. (joey5337)]

Ralph S. schrieb:
> bcd = (dig << (i << 2)) | bcd;

Das i<<2 ist typische premature Optimization.
Der Code wäre deutlich verständlicher, wenn dort stehen würde
> bcd = (dig << (i*4)) | bcd
Dann wüsste man sofort, dass positionsabhängig jeweils 4 bit verschoben 
wird.
So muss man sich erst mal überlegen "Wofür ist diese Berechnung?"

Der Compiler optimiert das ohnehin zum selben Code.

Hab etwas Vertrauen in den Compiler:
https://www.youtube.com/watch?v=w0sz5WbS5AM&t=25s

[A. S. (Gast)]

Für bin 2 bcd gibt es seit 50 Jahren das addiere 3 Verfahren oder so. 
Nur schieben und addieren.

Es spielt aber heute keine Rolle mehr, da Tabellen oder mal und geteilt 
kaum etwas kosten.

[MaWin (Gast)]

Ralph S. schrieb:
> stellt sich mir die Frage der Ausführungsgeschwindigkeit für eine
> BIN2BCD Funktion.

bin2bcd ist genau so abarbeitbar wie bin2ascii

static uint32_t tab[] = {4000000000, 2000000000, 1000000000, 800000000, 400000000, 200000000, 100000000, 80000000, 40000000, 20000000, 10000000, 8000000, 4000000, 2000000, 1000000, 800000, 400000, 200000, 100000, 80000, 40000, 20000, 10000, 8000, 4000, 2000, 1000, 800, 400, 200, 100, 80, 40, 20, 10, 0};

void l2a(uint32_t zahl, char *s)       // l -> zu wandelnde Zahl, *s -> Ergebnis
{
  register uint8_t t; // i -> tab-index
  register uint32_t temp; // für schnellere Ausführung
  register char j;        // j -> aktueller BCD code
  uint32_t *tabptr=tab;

  t = 4;
  j = 0;                  // Start 
  while(1)
  {
    temp=*tabptr++;
    if ( zahl >= temp ) // nicht subtrahieren 
    {
      j+=t;
      zahl-=temp;
    }
    t >>= 1;
    if ( !t ) // Stellenwechsel
    {
      *s++ = j; // BCD code ablegen
      j = 0;
      if(!*tabptr) break;
      t = 8;
    }
  }
  *s++=j+(uint8_t)zahl; // letzte Stelle immer ausgeben
}

[A. S. (Gast)]

A. S. schrieb:
> addiere 3 Verfahren

Scheint im Englischen so zu heißen (nie gehört)

https://en.wikipedia.org/wiki/Double_dabble

[c-hater (Gast)]

Ralph S. schrieb:

> Mir geht es hier vor allem um die Logik und nicht darum, etwas mittels
> Inline-Assembler zu machen.

Aber gerade das wäre doch logisch...

Einen zu den Anforderungen passenden Algorithmus wählen muss man 
natürlich unabhängig von der Programmiersprache.

Aber praktisch jeder der in Frage kommenden läßt sich dann (speziell auf 
einem AVR8) in Asm deutlich bis sehr deutlich effizienter implementieren 
als in "native" C.

[Tilo R. (joey5337)]

c-hater schrieb:
> Aber praktisch jeder der in Frage kommenden läßt sich dann (speziell auf
> einem AVR8) in Asm deutlich bis sehr deutlich effizienter implementieren
> als in "native" C.
Fragezeichen angemeldet :-)
Auf dem AVR mag das u.U. noch stimmen.
Auf komplizierteren Prozessoren ist es sehr wahrscheinlich, dass der 
Compiler mehr Tricks drauf hat und besser Assembler kann als ein 
normalsterblicher Programmierer.

[S. Landolt (Gast)]

Für AVR-asm gab es hier vor einem Jahr eine Diskussion:
Beitrag "asm 16 Bit in BCD"

[c-hater (Gast)]

Tilo R. schrieb:

> Auf dem AVR mag das u.U. noch stimmen.

Da stimmt das sogar ganz sicher. Und der Performance-Vorteil fällt hier 
ziemlich beeindruckend aus.

> Auf komplizierteren Prozessoren ist es sehr wahrscheinlich, dass der
> Compiler mehr Tricks drauf hat und besser Assembler kann als ein
> normalsterblicher Programmierer.

Was soll ein normalsterblicher Programmierer sein? Einer, der de facto 
nur C kann? Ja klar, so einer hat natürlich kaum Chancen, besser als der 
Compiler zu sein.

Dass das so ist, liegt allerdings zu einem gut Teil daran, dass der 
Compiler wiederum große Teile der Mathematik aus vorgefertigten, bereits 
in Assembler geschriebenen Macros zusammenbaut. Ein tiefer Blick in die 
Quelltexte der Compiler zeigt dir das. Das gilt für praktisch jede 
Zielarchitektur, die sich einer einigermaßen breiten Nutzung erfreut.

[Tilo R. (joey5337)]

c-hater schrieb:
> Dass das so ist, liegt allerdings zu einem gut Teil daran, dass der
> Compiler wiederum große Teile der Mathematik aus vorgefertigten, bereits
> in Assembler geschriebenen Macros zusammenbaut. Ein tiefer Blick in die
> Quelltexte der Compiler zeigt dir das. Das gilt für praktisch jede
> Zielarchitektur, die sich einer einigermaßen breiten Nutzung erfreut.
c-hater, da sind wir ganz einer Meinung.
Es ist wie beim Schach: Ein Schachcomputer hat eine riesige 
Eröffnungsbibliothek, während selbst erfahrene Schachspieler nur eine 
überschaubare Anzahl und Varianten im Kopf haben.
Auf populären Architekturen gewinnt der Compiler, so wie der Computer 
gegen normale Schachspieler.

Auf der Randgruppenarchitektur AVR hast du sicher oft recht. Allein wie 
oft der avrgcc unnötig Register auf den Stack pusht...

Pluspunkt Compiler ist, dass er neben der Assembler-Bibliothek auf 
logischer Ebene argumentieren/optimieren kann, und so ggf. manche 
Berechnungen gar nicht machen muss, durch Lookups ersetzen kann etc.
Und das über den lokalen Kontext hinaus, ggf. auch durch den Einsatz von 
Heuristiken.

Heuristiken sind lustigerweise auch, warum JIT-Compiler schneller sein 
können als statisch kompilierter Code: Der JIT-Compiler kann in den 
ersten (langsamen) Durchläufen Statistiken erstellen, um danach auf die 
tatsächlich verarbeiteten Daten hin optimierten Maschinencode zu 
erstellen.
Selbst aus Horror-Sprachen, wie dem schwach typisierten JavaScript, wo 
ein Objekt ein beliebig erweiterbares Dictionary ist, kommt so 
irgendwann (einigermaßen) performanter Maschinencode raus. Aus dem 
teuren Member-Lookup wird ein typisierter Speicherzugriff mit fixem 
Offset, so effizient wie ein C-Struct.
Nur so lässt sich der Web-Bloat überhaupt ertragen. Ohne sowas wäre 
Webassembly nicht denkbar.

Aber lass uns das nicht zum Flamewar werden.
Was ich sagen will ist: Die Welt ist nicht schwarz und weiß. In vielen 
Fällen lohnt es sich nicht über Optimierungen nachzudenken. (Effizienten 
Algorithmus mal vorausgesetzt.)
In manchen (imho seltenen) Fällen ist Assembler ungeschlagen.

[Walter (Gast)]

ein Array vielleicht schrieb:
> Am PC könnte man mit auch so vorgehen:

alles sehr seltsam, ich verstehe nicht was du mit dem Programm erreichen 
willst?
Eine Umwandlung in BCD ist es mit Sicherheit nicht

[Search, Will. U. (Gast)]

https://stackoverflow.com/questions/13247647/convert-integer-from-pure-binary-to-bcd

[Peter D. (peda)]

Walter schrieb:
> alles sehr seltsam, ich verstehe nicht was du mit dem Programm erreichen
> willst?

Das geht mir auch so.
Ich wüßte keinerlei Anwendung, wo man gepackte BCD-Nibbles benötigt. 
Vielleicht ganz zu Anfang der Computerära hat mal jemand 7-Segment 
Decoder an eine CPU angeschlossen. Seitdem geistert diese komische 
Packroutine durch die Lehrbeispiele.

Speziell auf dem AVR geht zur Ausgabe die Subtraktionsmethode mit 
Zehnerpotenzen am schnellsten. Aber das wurde ja schon bis zum Abwinken 
hier im Forum diskutiert.
In der Programmierpraxis benutzt man einfach sprintf().

[Arno (Gast)]

W.S. schrieb:
> Und nochwas: Wenn du schon Modulo und Division direkt nebeneinander
> verwendest, dann ist das vom Rechenaufwand so etwa das Doppelte, als
> wenn du nur einmal 'ldiv' verwendest.

Das dürfte der Compiler schon passend optimieren. Nicht umsonst heißen 
die entsprechenden Funktionen irgendwas mit _divmod, die werden nicht 
öfter aufgerufen als nötig.

Zur ursprünglichen Frage: Ich vermute (ohne in den generierten 
Assembler-Code geschaut zu haben), das langsamste daran dürfte der 
variable Shift um (4*i) sein.

Es könnte sich lohnen, das mit einem char[] zu machen und entweder 
hinterher zu packen (wenn überhaupt nötig - die Frage, was du mit dem 
zurückgegebenen int denn machen willst, wurde ja schon gestellt) oder 
zwei Stellen pro Schleifendurchlauf zu verarbeiten. Hätte auch den 
(vermutlich theoretischen) Vorteil, dass dir dein Rückgabewert nicht 
schon bei 100.000.000 überläuft, wenn du Eingaben bis 2^32-1, also 
~4.000.000.000, erlaubst.

Für den 8-Bit-Wert ist auch der Speicher-Mehraufwand für eine 
Lookup-Table handhabbar - muss ja nur bis 99 gehen, mehr kannst du als 
gepacktes BCD in einem Byte eh nicht zurückgeben (dein Code macht für 
Eingaben über 99 auch Blödsinn, da würde ich auf AVR ohne Betriebssystem 
auch einen *Lese*zugriff außerhalb der Arraygrenzen akzeptieren).

MfG, Arno

[Polmann (Gast)]

ein Array vielleicht schrieb:
> Ach so, und mit einer 0 darf die Zahl dann auch nicht anfangen, sonst
> würde das als eine Oktalzahl interpretiert;

??
Was für einen Compiler verwendest du denn?
Ich arbeite selten unter C, aber in PAscal kannst du klar sagen es 
Oktalm, Binär oder sonst was sein soll

[pro Richtige Hochsprachen (Gast)]

c-hater schrieb:
>> Compiler mehr Tricks drauf hat und besser Assembler kann als ein
>> normalsterblicher Programmierer.
>
> Was soll ein normalsterblicher Programmierer sein? Einer, der de facto
> nur C kann? Ja klar, so einer hat natürlich kaum Chancen, besser als der
> Compiler zu sein.

Das ist einer der in C/C++ programmiert und dann normal stirbt. (eine 
Aussage über sein Können ist nicht möglich, sicher ist nur dass 
ausschliesslich Gottheiten C/C++ so gut beherrschen können dass kein 
Mensch was daran zu meckern hat)

Das ist anders bei c-hater: er ist dazu verdammt als Zombie bis in die 
Ewigkeit sein Assembler-Evangelismus zu verbreiten. Sterben wird nie 
dürfen. Leider.

[Hannes J. (Firma: _⌨_) (pnuebergang)]

Ich musste ein bisschen suchen, dann habe ich das wieder gefunden:

Konvertierung als Einzeiler:
https://www.avrfreaks.net/forum/simple-formula-binary-bcd-conversion

Besonders interessant wird es ab hier,
https://www.avrfreaks.net/comment/3086041#comment-3086041
wo sich rausstellte dass der Compiler in höheren Optimisierungsstufen 
die Werte um 2^16 hochskaliert und dann die Integerdivisionen durch 10^n 
durch Multiplikationen (und Shifts) mit magischen Zahlen ersetzte:

1/10 = 52429/8/2^16
1/100 = 5243/8/2^16
1/1000 = 8389/128/2^16
1/10000 = 839/128/2^16

Damit soll eine Konvertierung 13,7µs auf einem Atmega328P mit 16MHz 
gedauert haben.

[W.S. (Gast)]

pro Richtige Hochsprachen schrieb:
> c-hater schrieb:
>>> Compiler mehr Tricks drauf hat und besser Assembler kann als ein
>>> normalsterblicher Programmierer.
>>
>> Was soll ein normalsterblicher Programmierer sein? Einer, der de facto
>> nur C kann? Ja klar, so einer hat natürlich kaum Chancen, besser als der
>> Compiler zu sein.
>
> Das ist einer der in C/C++ programmiert und dann normal stirbt. (eine
> Aussage über sein Können ist nicht möglich,...

Nun ja, dir wohl nicht. Sowas ist eine Frage deines Horizontes. Aber 
wenn du das so siehst, dann ist nach deiner Auffassung ein 
'normalsterblicher' Programmierer einer, der außer C oder C++ nichts in 
seinem Leben gesehen hat. So einer hat natürlich keine Chance, irgend 
etwas außer C bzw. C++ zu kennen und zu können.

Andere Leute mit weiterem Horizont sehen das ganz anders.

W.S.

[Ralph S. (jjflash)]

A. S. schrieb:
> A. S. schrieb:
>> addiere 3 Verfahren
>
> Scheint im Englischen so zu heißen (nie gehört)
>
> https://en.wikipedia.org/wiki/Double_dabble

so, nachdem ich hier jetzt alles mal gelesen habe, werde ich das 
Verfahren hier mal genauer ansehen.

Wie zu erwarten war gabs wieder mal Anfeindungen gegeneinander, Posts 
natuerlich nach dem Sinn des ganzen und warum man das ueberhaupt will 
(es soll ja auch RTC Chips geben, die mit BCD Zahlen gefuettert werden 
wollen).

Und natuerlich wieder, was fuer schlechte Programmierer denn alle sind 
(ausgenommen die eigene Person).

W.S. schrieb:
> Und nochwas: Wenn du schon Modulo und Division direkt nebeneinander
> verwendest, dann ist das vom Rechenaufwand so etwa das Doppelte, als
> wenn du nur einmal 'ldiv' verwendest.

:-) das war so ziemlich das erste (sogar noch vor deinem Post) was 
geaendert wurde...

-----------------------------

Fuer alle anderen die die Frage nach dem Sinn stellen: das ist eine Uhr, 
die die Uhrzeit auf einer charliegeplexten LED Anzeige mit 20 Leds die 
Uhrzeit ausgibt. Die LED sind so angeordnet, dass sie im BCD Code 
abgelesen werden koennen.

[W.S. (Gast)]

Ralph S. schrieb:
> Die LED sind so angeordnet, dass sie im BCD Code
> abgelesen werden koennen.

Ich nehme mal an, daß du das mit einem kleinen Padauk-µC machen willst. 
Deshalb der Versuch, die verschiedenen Dinge wie Ausgabekonverter und 
Display-Ansteuerung miteinander zu vermengen - in der Hoffnung, dadurch 
ein wenig Code zu sparen.

Naja, damit erklärt sich so einiges.

W.S.

[TotoMitHarry (Gast)]

Man könnte das ganze ja auch im C Modus ausprobieren..

vom Sprintf Ergebnis einfach die 4Bits des Asciicodes direkt in den 
Quell ULong zurückschreiben.

[TotoMitHarry (Gast)]

z.B.

#include <stdio.h>
#include <stdlib.h>
int main ()
{  
   char* t;
   uint32_t i=12345690;
   char buffer [sizeof(unsigned long)*8+1];

   sprintf (buffer,"%lu",i);
   i=0;
   for (t = buffer; *t != '\0'; t++)
        i |= (i<<4)|(((uint8_t)*t-48) & 0xff);
   
return 0;
}

[Ralph S. (jjflash)]

W.S. schrieb:
> Ich nehme mal an, daß du das mit einem kleinen Padauk-µC machen willst.

Nein, in diesem Falle ein ATtiny44 an den auch noch ein DCf77 Modul 
angeschlossen ist... Und läuft. Für den Padauk werde ich das dann 
realisieren, wenn ich für diesen eine genaue Zeitbasis zustande bekomme. 
Ein DCf will ich dort nicht hernehmen.

Grundsätzlich geht's mir ja darum , ultrabilliges Bastelzeugs zu nehmen 
und daraus etwas zu machen. Seit der Pandemie (und den neueren 
Zollgesetzen) habe ich da keinen wirklichen Spaß mehr daran, weil es 
ultrabillig nicht mehr gibt.

[TotoMitHarry (Gast)]

Ralph S. schrieb:
> ein, in diesem Falle ein ATtiny44

bei so wenig speicher würde ich das mit ultoa versuchen, das sollte 
eigentlich nochmal Speicher sparen.. nur muss man sich dann um führende 
Nullen etc. selbst kümmern.

   ultoa(i,buffer,8);
   i=0;
   for (t = buffer; *t != '\0'; t++)
        i |= (i<<4)|(((uint8_t)*t-48) & 0xff);

Denke die Welt kleiner wird das nicht mehr..

[Ralph S. (jjflash)]

... unfassbar!!! Es ging um schneller (und effizienter) und nicht 
kleiner im Sourcecode....

Umwege über Ascii-Zeichen oder gar Strings sollen da Zielführend sein? 
Im Leben nicht...

Am ehesten ldiv, weil in der rückgebenden Struktur die Modulo und 
normale Division schon enthalten die ist.

[TotoMitHarry (Gast)]

Ralph S. schrieb:
> ... unfassbar!!! Es ging um schneller (und effizienter) und nicht
> kleiner im Sourcecode....

Meine Idee funktioniert auch garnicht, man müsste danach verdrahten und 
bei nullen gibts auch ein Problem. Sry, ups.

Außerdem gibt es die beste Lösung ausdiskutiert anno 2005 in einem Atmel 
Forum. Da ging es auch um einen Attiny.

Das dcf kommt doch sowieso in Häppchen, die ports sind 8bit.. da 
erschliesst sich mir der Sinn nicht ganz wieso man mit uint32 daher 
kommt.