16-Bit-Zahl ausgeben, nur wie?

[Johann L. (gjlayde)]

Hi, ich steh grad aufm Schlauch.

Ich möchte 16-Bit Zahlen im q-Format als Dezimalbruch ausgeben, d.h. die 
Zahlen liegen alle im Bereich von -1 bis 1 und haben 1 Vorkommastelle 
und 15 Nachkommastellen.

Siehe dazu auch AppNote AVR201 von Atmel:

http://faculty.capitol-college.edu/~andresho/tutor/Multimedia/AVR/HW_mult/avr201.htm

Momentan hab ich folgende C-Routine, die Teil einer printf-ähnlichen 
Ausgabefunktion ist (put_char2() gibt nen char aus und put_str() nen 
0-terminierten String):

void put_sfrac16 (int16_t frac)
{
    if (frac < 0)
    {
        put_char2 ('-');
        frac = -frac;
    }
    put_char2 ('0');
    put_char2 ('.');
 
    // frac ist jetzt positiv (ausser im pathologischen Fall 0x8000)   

    // 6 Nachkommastellen ausgeben (dezimal)
    char *pbuf = buf;
    
    for (uint8_t i=0; i < 6; i++)
    {
        uint8_t digit = '0';

        // solange frac >= 0.1 ist: 0.1 abziehen
        while (frac >= (1U << 15)/10)
        {
            frac -= (1U << 15)/10;
            digit++;
        }
        *pbuf++ = digit;
        frac *= 10;
    }
    *pbuf = '\0';
    put_str (buf);
}

Solange die Zahl >= 0.1 ist, wird von frac 0.1 abgezogen, um die 
entsprechende Ziffer zu erhalten. Danach wird frac mit 10 multipliziert 
und es geht bei der nächsten Ziffer weiter.

Problem ist nun, dass 32768/10 = 3276.8 ist und nicht 3276, d.h. die 
Ausgabe so nicht korrekt ist, uns teilweise auch Ziffern größer als '9' 
bringt.

Ursprünglich hatte ich ne Version, in der nachgeschaut wird, ob frac*10 
>= 0x8000 ist. Allerdings musste ich dann mit 32-Bit-Zahlen rechnen, und 
das ist mir zu teuer. Zudem gibt es auch ne Version mit 32-Bit q-Format, 
und da bräuchte ich dann 64 Bits...der Horror.

Ich hab auch schon versucht, 3277 abzuziehen und zu merken, dass man 
einen Fehler von 0.2 gemacht hat, aber das Ergebnis ist noch falscher...

Jemand ne Idee?

[Matthias L. (Gast)]

>Bereich von -1 bis 1 und haben 1 Vorkommastelle
>und 15 Nachkommastellen.

Wie muss ich mir das vorstellen, wie das intern (in 16Bit) gespeichert 
sein soll?

zB:

2Byte Wert     richtiger Wert
-------------------------------
0x0000          0.000000
0x7FFF          0.999999
0xFFFF         -0.999999

Oder wie möchtest du das?

[Johann L. (gjlayde)]

Ja, genau so.

Hier noch ein etwas zielgenauerer Link:

http://faculty.capitol-college.edu/~andresho/tutor/Multimedia/AVR/HW_mult/avr201.htm#book10

Wobei für 0x7fff die Ausgabe 0.99996 oder 0.99997 ist wegen der 
Genauigkeit.

5 Nachkommastellen sind eigentlich genug, weil 1/32768 ~ 0.00003.

Die Zahlen sind also ganz normale signed short, die immer noch impizit 
durch 2**15 geteilt werden.

Die Addition ist die normale short-Addition und die Multiplikation ist

mul(x,y) = (x*y) << 1

damit das Komma wieder an der rechten Stelle steht.

[Matthias L. (Gast)]

Hm.. Für sowas ist mir mal eine "geniale" Idee eingefallen.
Hab das hier schonmal gepostet, finds aber nicht mehr.

Das lästige Dividieren kann man weglassen, wenn man High/Low-Words 
nimmt.

Hier nochmal am Beispiel erklärt:
Im WORD steht 0x7FFF. Das soll nach 32767/32768 = 0.999'969'482'4.. 
sein.

AUsgange vorbereiten: "0."
du nimmst jetzt das
                    high  lowword
word=
0x7FFF mal 20dez =>  09  '  FFEC       => HIGH Word anhängen: "0.9"

lowword=
0xFFEC mal 10dez =>  09  '  FF38       => HIGH Word anhängen: "0.99"

lowword
0xFF38 mal 10dez =>  09  '  F830       => "0.999"

lowword
0xF830 mal 10dez =>  09  '  B1E0       => "0.999'9"

lowword
0xB1E0 mal 10dez =>  06  '  F2C0       => "0.999'96"

lowword
0xF2C0 mal 10dez =>  09  '  7B80       => "0.999'969"

lowword
0x7B80 mal 10dez =>  04  '  D300       => "0.999'969'4"

lowword
0xD300 mal 10dez =>  08  '  3E00       => "0.999'969'48"

lowword
0x3E00 mal 10dez =>  02  '  6C00       => "0.999'969'482"
...
Benötigst aber eine 16x16=32bit Multipikation, oder was äquvalentes
Das kann als Schleife programmiert werden, und muss dann sinnvoll 
abgebrochen werden.
Ist die Zahl negativ, so muss vorerst das Minus drangehangen werden, und 
die Zahl in eine (temp) pos. umgewandelt werden...

PS: Vielleicht kann/sollte das mal als Wiki Artikel gemacht werden?
Oder was meint ihr?

[Johann L. (gjlayde)]

Ich dividiere doch nicht. Die Division durch 10 macht gcc zur 
Compilezeit beim Falten der Konstanten.

Soweit hab ich das ja alles schon.

Es geht wie gesagt darum, bei 16-Bit-Typen ohne 32 Bits auszukommen und 
bei 32-Bit-Typen ohne 64-Bits, weil das eben super aufwändig ist.

Hier die Version für Ausgabe von 1.31. Das ganze sieht easy aus, belegt 
aber wegen der 64-Bit-Arithmetik weit über 500 Byte Programmcode. (Und 
ja, ich hab Optimierung aktiviert. Die Zahl bezieht sich auf avr-gcc und 
ATmega8)

void put_sfrac32 (int32_t frac)
{
    if (frac < 0)
    {
        put_char2 ('-');
        frac = -frac;
    }
    put_char2 ('0');
    put_char2 ('.');
    
    uint64_t frac64 = (uint32_t) frac;
    frac64 <<= 1;
    
    char *pbuf = buf;
    
    for (uint8_t i=0; i < 10; i++)
    {
        frac64 *= 10;
        *pbuf++ = '0' + (frac64 >> 32);
        frac64 &= 0xffffffff;
    }

    *pbuf = 0;
    put_str (buf);
}

Die Frage ist also, wie man an die einzelnen Ziffern kommt, ohne auf den 
nächst größeren Typ zu müssen.

avr-gcc hat nur die wichtigsten Sachen für long long implementiert. Für 
Multiplikation hat er weder Pattern noch Funktionen in der libgcc2, so 
daß die Mutiplikation auf algebraischer Ebene auf keinere Typen 
abgebildet wird. Daß der Code dann suboptimal wird versteht sich da von 
selbst.

[Matthias L. (Gast)]

>Die Frage ist also, wie man an die einzelnen Ziffern kommt, ohne auf den
>nächst größeren Typ zu müssen.

In dem du zur Laufzeit entsprechend dividierst. Das kostet aber 
sicherlich mehr recourcen als mit 10 (oder wie im Bsp) mit 20 zu 
multiplizieren, auch wenns ein größerer Datentyp ist.

Sonst wirst du wohl keine andere Möglichkeit haben.


aus vielleicht mit einem solchen Konstruct:
Das liefert eine Stelle, und müsste mehrfach aufgerufen werden...
Aber wie schnell das ist, weiß ich nicht.

if ( x >  (1*32768/10) )
{
  // Zahl größergleich 0.1
  *pBuf++ = '1';
  x -= (1*32768/10);
if ( x >  (2*32768/10) )
{
  // Zahl größergleich 0.1
  *pBuf++ = '2';
  x -= (2*32768/10);
}
...
if ( x >  (9*32768/10) )
{
  // Zahl größergleich 0.9
 *pBuf++ = '9';
  x -= (9*32768/10);
}
x = x * 10;

[Johann L. (gjlayde)]

Die Laufzeit ist weniger das Problem, eher der belegte Speicher. Über 
500 Byte nur für eine Teilfunktion der Ausgabe ist schon satt.

Ich hab die Funktionen jetzt so umgeschrieben, dass sie einigermassen 
klein sind. Die 32-Bit-Variante (also 1.31-Variablen) braucht nur noch 
ca. 270 Bytes :-)

Ist zwar noch kein schöner Code, aber soll ja auch keinen Preis 
gewinnen. Für 1.15-Werte geht das analog. Hier noch der Code, falls wer 
was ähnliches braucht. Es brauch weder Division noch 64-Bit-Werte:

void put_sfrac32 (int32_t frac)
{
    if (frac < 0)
    {
        put_char2 ('-');
        frac = -frac;
    }
    put_char2 ('0');
    put_char2 ('.');
    
    uint32_t f = frac;
    
    char *pbuf = buf;
    uint8_t digit = 0;
    
    for (uint8_t i=0; i < 10; i++)
    {
        if (digit == 10)
        {
_9:
            *pbuf++ = '9';
            continue;
        }    
    
        uint32_t f2 = f + (f >> 2);

        // uint8_t digit = f2 >> 28;
        union { uint8_t b[4]; uint32_t l; } u = {.l = f2 >> 4};
        digit = u.b[3];

        if (digit == 10)
            goto _9;
            
        *pbuf++ = '0' + digit;
        f -= (1UL<<31)/10 * digit;
        
        if (digit >= 2)
        {
            if (digit >= 6)
                f++;
            
            digit--;
            f -= digit;
        }
        f *= 10;
    }
    
    *pbuf = '\0';
    put_str (buf);
}

[Johann L. (gjlayde)]

Matthias Lipinsky wrote:
>>Bereich von -1 bis 1 und haben 1 Vorkommastelle
>>und 15 Nachkommastellen.
>
> Wie muss ich mir das vorstellen, wie das intern (in 16Bit) gespeichert
> sein soll?
>
> zB:
>
> 2Byte Wert     richtiger Wert
> -------------------------------
> 0x0000          0.000000
> 0x7FFF          0.999999
> 0xFFFF         -0.999999
>
> Oder wie möchtest du das?

Die Darstellung ist analog zu signed short, d.h. wenn man von 0 Eins 
abzieht (ist 0xFFFF), kommt man zur nächst kleineren Zahl.

"richtiger Wert" = "2-Byte-Wert als signed" / 2**15

Also so:

2Byte Wert     richtiger Wert
-------------------------------
0x0000          0.00000
0x7FFF          0.99997
0xFFFF         -0.00003
0x8000         -1.00000
0x8001         -0.99997

[eProfi (Gast)]

Mit ein bisschen Überlegen kommt man auf folgenden genial-einfachen 
high-density-Code:

#include <stdio.h>
#define examp 0x1234 // 0.1422119140625
#define examp 0x7654 // 0.9244384765625
#define examp 0x7fff // 0.999969482421875
#define examp 0x8000 //-1.0000000000000
#define examp 0x8001 //-0.999969482421875
#define examp 0x89ab //-0.924468994140625
#define examp 0xfedc //-0.0089111328125
#define examp 0xffff //-0.000030517578125
//nur der letzte #define ist wirksam
#define scale 50000000L //0.50000000

void main(void){
  unsigned int numb=examp,mask=0x4000;
  signed long  summ=0,temp=scale;
  if(numb&0x8000){s=-2*scale;} //-1.00000000 wenn bit15 gesetzt
  do{if(nubm&mask){summ+=temp;}temp/=2;}while(mask/=2);
  printf("\r\n%05x : %1.9f",numb,summ/(2.0*scale);}

zur Funktion:
wenn bit15 gesetzt: 1.00000000 (100000000) abziehen
wenn bit14 gesetzt: 0.50000000 ( 50000000) addieren
wenn bit13 gesetzt: 0.25000000 ( 25000000) addieren
...
wenn bit00 gesetzt: 0.000030517578125 addieren

Je nach Anzahl der Nullen von scale ist die Auflösung.

Im µC-Programm wird die Ausgabe natürlich nicht mit dem float gemacht, 
sondern mit longint, wobei man das Komma an der richtigen Stelle 
reinsetzt.

Es gibt eine noch effektivere Methode, indem man die Umwandlung und die 
Ausgabe zusammen in einer Routine macht. Das beschreibe ich im nächsten 
Beitrag.

[Gast (Gast)]

Hallo,
bekannte Methode:

Bsp.: 0x7FFF = 32767 := 0.99997

Multiplikation:

0x7FFF * 20000 = 0x270FB1E0 = 9999 * 65536 + 45536

Ergebnis 1: 0.9999

Multiplikation:

45536 * 10000 = 0x1B243E00 = 6948 * 65536 + 15872

Ergebnis 2: 0.9999 + 0.00006948 = 0.99996948


Ergo: 2 * 16(32)Bit Multiplikation und bekannte Binär nach BCD Wandlung.

[Simon K. (simon)]

eProfi wrote:
> Mit ein bisschen Überlegen kommt man auf folgenden genial-einfachen
> high-density-Code:

Schön, dass du da offensichtlichen very-high-density code erzeugt hast, 
aber meinst du nicht zu Demonstrationszwecken sollte man den Code etwas 
entfädeln?

[Matthias L. (Gast)]

>Ergo: 2 * 16(32)Bit Multiplikation und bekannte Binär nach BCD Wandlung.

Geht auch anders:
Beitrag "Re: Bei der Berechnung von Kommazahlen "float" vermeiden"

[Gast (Gast)]

Also genau mein Vorschlag!

[Matthias L. (Gast)]

>Also genau mein Vorschlag!

Nein ist es nicht.

[eProfi (Gast)]

So, wie versprochen die Kombinationsroutine.

Funktioniert wie Peter D.s Subtraktions-Additions-Methode,
aber statt 1000000 wird ein anderer Wert subtrahiert und dadurch 
erübrigt sich die vorgelagerte Umwandlung.


Diese Idee hatte ich vor langer Zeit schon mal gepostet (angehängt), 
aber ich finde sie nicht wieder. Kann sich jemand erinnern? Bitte den 
Link posten.

Damals habe ich (soweit ich mich erinnere) die Subtrahenden für 5,0000, 
4,9951, 3,3000 und 3,2967 und 100,00  angegeben. War vermutlich ein 
.asm-file.

Beim Runden der /10-geteilten Subtrahenden muss man aufpassen: sie sind 
so gewählt, dass bei Eingang 0 auch 0 rauskommt (ist ein Spezialfall, 
den andere extra abfangen), wählt man sie geringfügig anders, kommt z.B. 
000/0;0  heraus (also mit 0x2f und 0x3a).

@Simon K.
"aber meinst du nicht zu Demonstrationszwecken sollte man den Code etwas 
entfädeln?"

Hast ja recht, aber die paar CrLf wird ja jeder noch selbst einfügen 
können. Ich mag´s halt lieber kompakt.
n.b. Du hättest mal den Original-Code sehen sollen ;-), der war noch 
wesentlich kürzer (Variablen-Namen mit einem Buchstaben und keine 
Geschweifte Klammer nach dem if).

Deshalb haben sich oben auch 2-3 Tippfehler eingeschlichen:
{s=-2*scale;} --> {summ=-2*scale;}
nubm&mask --> numb&mask
evtl. alle bis auf einen #define examp  weggkommentieren

@Gast: Stimmt, ist ebenso genial. Habe es auch schon öfters so 
vorgeschlagen.

[Johann L. (gjlayde)]

eProfi wrote:
> So, wie versprochen die Kombinationsroutine.

Irgendwas stimmt mit der Union nicht. Entweder geht es für 16-Bit-Werte 
nicht, oder für 32-Bit-Werte hakt es. So wie es dasteht soll das zweite 
"int" wohl "short" heissen?

noch'n Tipp:

numb.si[hi]^=0xffff;;numb.si[hi]+=1;

geht lesbarer als

numb.si[hi] = -numb.si[hi];

[eProfi (Gast)]

@Johann L.
1.
"Irgendwas stimmt mit der Union nicht."
Das kommt auf den Compiler an, mit TurboC geht's so, mit CodeWarrior 
auch.

Gemeint ist, dass ich mit numb.sl auf alle 32 Bits zugreife  und  mit 
numb.si[hi] direkt (ohne Bit-Geschiebe) auf die höheren 16 Bits.

Dafür habe ich auch einige Versuche gebraucht.
Wie müsste es denn korrekt heißen?


2.
numb.si[hi] = -numb.si[hi];

Ui, da hast Du recht! Danke.
Und ich freue mich wie ein neues Fuffzgerl, da es noch kürzer geht:
numb.si[hi] *= -1;  //hoffentlich weiß der Compiler das zu optimieren
                    // da habe ich schon kuriose Sachen erlebt


@all
das .c-Programm in obigem Anhang verwendet weder Multiplikation noch 
Division und ist deshalb in den kleinen µC ohne mul-Befehl besonders 
effektiv, wenn man z.B. den ADC-Wert in eine Spannung umrechnen und 
ausgeben will.

[Johann L. (gjlayde)]

eProfi wrote:
> @Johann L.
> 1.
> "Irgendwas stimmt mit der Union nicht."
> Das kommt auf den Compiler an, mit TurboC geht's so, mit CodeWarrior
> auch.

Es kommt darauf an, wie int implementiert ist, das ist compilerabhängig. 
Sind es 16 Bit, dann geht es, mit 32 Bits nicht.

Für 16-Bit Ausgabe passt also die Kombination long/short, und für 32-Bit 
Ausgabe die Kombination long long/long.

> Gemeint ist, dass ich mit numb.sl auf alle 32 Bits zugreife  und  mit
> numb.si[hi] direkt (ohne Bit-Geschiebe) auf die höheren 16 Bits.

Ein guter Compiler wird hier eh nicht schieben -- vorausgesetzt, die 
Maschine kann einfach auf die obere Hälfte zugreifen. Teilweise bringt's 
aber schon etwas besseren Code als Shift, manchmal aber auch 
schlechteren. Beachte, daß die 32-Bit-Werte immer zusammenhängend 
reserviert werden müssen, während 2*16 Bits nicht zusammenhängend liegen 
müssen. Dies kann insbesondere auf 16- und 8-Bit-Maschinen besseren Code 
geben, weil eine bessere Register-Allokierung möglich ist. Allgemeine 
Aussagen kann man schlecht machen.

> Dafür habe ich auch einige Versuche gebraucht.
> Wie müsste es denn korrekt heißen?

Wie gesagt: short/char, long/short, long long/long. Je nachdem, ob man 
8, 16 oder 32 Bits ausgeben will. Aber eigentlich will man sich den 
jeweils nächstgrößeren Datentyp nicht aufbürden und macht zB die 
16-Bit-Ausgabe, ohne 32-Bit große Typen zu brauchen -- auch wenn's nur 
elementare arithmetische Operationen sind. Um a-= b in 32 Bit auf einem 
8-Bit-µC auszuführen, braucht's schon 8 Register!

Und noch einen Haken gibt's: eine Implementierung via Union ist abhängig 
von der Endianess der Maschine und kann nur entweder für little Endian 
oder nur für big Endian funzen.

> 2.
> numb.si[hi] = -numb.si[hi];
>
> Ui, da hast Du recht! Danke.
> Und ich freue mich wie ein neues Fuffzgerl, da es noch kürzer geht:
> numb.si[hi] *= -1;  //hoffentlich weiß der Compiler das zu optimieren
>                     // da habe ich schon kuriose Sachen erlebt

Wenn, dann optimiert er es zu
numb.si[hi] = -numb.si[hi];

weil Negierung selbst mit Multiplikations-Hardware billiger ist.

> @all
> das .c-Programm in obigem Anhang verwendet weder Multiplikation noch
> Division und ist deshalb in den kleinen µC ohne mul-Befehl besonders
> effektiv, wenn man z.B. den ADC-Wert in eine Spannung umrechnen und
> ausgeben will.

[eProfi (Gast)]

> Diese Idee hatte ich vor langer Zeit schon mal gepostet (angehängt),
> aber ich finde sie nicht wieder. Kann sich jemand erinnern?
> Bitte den Link posten.

Selbst gefunden:
Beitrag "Re: 1023 auf 100% umformen"
das dort genannte Programm nutzt noch nicht die Add-Sub-Methode, 
außerdem sind 48/64-bit ein wenig zu viel, 32 reichen in den meisten 
Fällen.
Deshalb schreibe ich sie gerade neu.