Schieben vs. Tabelle

[Bertram Bügler (Gast)]

Ich würde gerne zeitkritische sachen in C auf einem wirklich kleinen uC 
wie Attiny10 programmieren. Da mein PC gerade Lieferprobleme hat, muss 
ich "trocken-programmieren"

uint_8t maske,n;

/* ein paar Berechnungen */

maske = 0xFF >> n;

Die Frage, nach 8 mal schieben ist alles raus, maske ist dann 0. Würde, 
falls n jetzt zum Beispiel 255 ist, der Compiler den Armen uC jetzt 
tatsächlich 255 x schieben lassen? Oder limitiert der Compiler die 
Schieberei auf 8? Oder legt der Compiler netterweise eine für den User 
unsichtbare Tabelle mit 10 Einträgen an?
Sorry for that, aber ich habe in Noment nur Handy.
Ich sollte einen C Compiler für Handy suchen.

[A. S. (Gast)]

Bertram Bügler schrieb:
> der Compiler den Armen uC jetzt
> tatsächlich 255 x schieben lassen? Oder limitiert der Compiler die
> Schieberei auf 8? Oder legt der Compiler netterweise eine für den User
> unsichtbare Tabelle mit 10 Einträgen an?
Wie er will. Er kann auch intern ein paar Floating-Point Berechnungen 
machen, wenn er meint, dass das notwendig ist und am Ende alles richtig 
ist.

> Ich sollte einen C Compiler für Handy suchen.
Ein Compiler liefert Dir ein Compilat. Das sagt nichts aus über das 
Compilat eines anderen Compilers oder das beim nächsten Start.

[Jemand2 (Gast)]

Bertram Bügler schrieb:
> Die Frage, nach 8 mal schieben ist alles raus, maske ist dann 0. Würde,
> falls n jetzt zum Beispiel 255 ist, der Compiler den Armen uC jetzt
> tatsächlich 255 x schieben lassen? Oder limitiert der Compiler die
> Schieberei auf 8? Oder legt der Compiler netterweise eine für den User
> unsichtbare Tabelle mit 10 Einträgen an?

Ein Shift der Breite des Typs oder mehr ist undefined behavior

[An oder In (den Futtertrog) - das ist die Frage (Gast)]

Bertram Bügler schrieb:
> Ich sollte einen C Compiler für Handy suchen.

Oder einen online c- compiler nutzen
https://www.programiz.com/c-programming/online-compiler/

ohne eine programiersprache benutzen die dein Handyresp. App native 
kann. (Java-scripz o.ä.).

[Dergute W. (derguteweka)]

Moin,

Oder einfach mal 'nen Apfel essen.

scnr,
WK

[Keep focused (Gast)]

Dergute W. schrieb:
> Oder einfach mal 'nen Apfel essen.

Dachte sich Schneewittchen auch:
https://youtu.be/6B3EncbvLnA

[Michael F. (Firma: IAR Systems) (michael_iar)]

Bertram Bügler schrieb:
> Die Frage, nach 8 mal schieben ist alles raus, maske ist dann 0. Würde,
> falls n jetzt zum Beispiel 255 ist, der Compiler den Armen uC jetzt
> tatsächlich 255 x schieben lassen? Oder limitiert der Compiler die
> Schieberei auf 8? Oder legt der Compiler netterweise eine für den User
> unsichtbare Tabelle mit 10 Einträgen an?

Servus,

keine der genannten Variablen ist volatile und falls in "ein paar 
Berechnungen" nirgends ein volatile-Wert genutzt wird, von dem "n" 
abhängt, dann sollte der Compiler das Ergebnis von "maske = 0xFF >> n;" 
bereits zur compile-zeit berechnen können und dann (bei höherer 
Optimierungsstufe) einfach entsprechend zuweisen.

Gruß,
Michael

[Bertram Bügler (Gast)]

Michael F. schrieb:
> keine der genannten Variablen ist volatile und falls in "ein paar
> Berechnungen" nirgends ein volatile-Wert genutzt wird, von dem "n"
> abhängt, dann sollte der Compiler das Ergebnis von "maske = 0xFF >> n;"
> bereits zur compile-zeit berechnen können und dann (bei höherer
> Optimierungsstufe) einfach entsprechend zuweisen.
> Gruß,
> Michael

Natürlich wird n berechnet und maske wird weiterverwendet. Und

maske = 0xFF >> n;
seriell_out(maske);
/* seriell_out(0xFF >> n); */
Liegt in einer zeitkritischen Schleife und wird ganz häufig aufgerufen!
Ich könnte natürlich schreiben :

if (n > 8) n = 8; // nötig?!

Aber da ich NICHT "volatile" verwendet habe ist meine Frage ob C 
Compiler (GCC) in hoher Optimierungsstufe mir automatisch die 
Limitierung der Schiebevorgänge auf 8 abnehmen?

[Oliver S. (oliverso)]

Bertram Bügler schrieb:
> Aber da ich NICHT "volatile" verwendet habe ist meine Frage ob C
> Compiler (GCC) in hoher Optimierungsstufe mir automatisch die
> Limitierung der Schiebevorgänge auf 8 abnehmen?

Nein.
Da das aber, wie schon geschrieben wurde, undefined behaviour wird, kann 
der Compiler da dann andere, für dich unerwartete Dinge tun.

Das es dazu auf einem AVR viel schneller wäre, die Maske jedes mal um 1 
zu shiften, an statt den Ausgangswert um n, sei hier nur angemerkt.

Alles in allem solltest du aber zunächst laufen lernen, bevor du zu 
sprinten beginnst.

Oliver

[Keep focused (Gast)]

Oliver S. schrieb:
> Alles in allem solltest du aber zunächst laufen lernen, bevor du zu
> sprinten beginnst.

Dummer Spruch.


> Das es dazu auf einem AVR viel schneller wäre, die Maske jedes mal um 1
> zu shiften, an statt den Ausgangswert um n,

Wertvoller Hinweis.


Bei Programmieren geht es darum, es gleich von Anfang an richtig zu 
lernen und sich nicht widersinnige Beispiele einfallen zu lassen, nur um 
irgendwelchen Akadämikern was zu beweisen.

[Yalu X. (yalu) (Moderator)]

Bertram Bügler schrieb:
> Aber da ich NICHT "volatile" verwendet habe ist meine Frage ob C
> Compiler (GCC) in hoher Optimierungsstufe mir automatisch die
> Limitierung der Schiebevorgänge auf 8 abnehmen?

Hoffentlich nicht, denn das wäre ja für alle n<8 (was der Normalfall
sein sollte) keine Optimierung, sondern das Gegenteil davon. Sinnvolle
Optimierungen kann der Compiler nur dann vornehmen, wenn er bereits zu
Compilezeit Schlüsse über mögliche Werte von n ziehen kann. Ob dies der
Fall ist, hängt davon ab, was sich hinter

/* ein paar Berechnungen */

verbirgt.

[Wilhelm M. (wimalopaan)]

Mit uint8_t hast Du einen logical-right-shift. Bei uint8_t bekommst Du 
das auch mit Division durch 2 statt >>. Natürlich ist der Compiler so 
intelligent, und ersetzt die Division durch `lsr` (AVR). Dann hast Du 
das Problem mit dem UB nicht, wenn mehr als die Anzahl der Bits 
geschoben wird. Nichts desto trotz machen die meisten Compiler dann aus 
dem Ausdruck eine `0` ...

[Bauform B. (bauformb)]

Bertram Bügler schrieb:
> Natürlich wird n berechnet

Dann kennt der Compiler den Wert von n nicht und darf davon ausgehen, 
dass n nie größer als 8 wird, weil:

Jemand2 schrieb:
> Ein Shift der Breite des Typs oder mehr ist undefined behavior

Ich als Compiler würde 8 shift-right Befehle hintereinander schreiben 
und je nach n die ersten 0 bis 7 davon überspringen. Die CPU kann 
wahrscheinlich sinngemäß etwas wie "add pc,(8-n)" -- optimal schnell, 
korrekt übersetzt, aber mit eingebauter Überraschung ;)

[Wilhelm M. (wimalopaan)]

Wegen Integralpromotion macht er da eh intern ein 16-Bit Shift draus. 
Wenn Du also (n < 16) zusichern kannst, ist das auch ok. Oder Du benutzt 
gleich uint16_t, dann ist es auf jeden Fall ok.

[Wilhelm M. (wimalopaan)]

... ansonsten ggf. eine `static constexpr` LUT erstellen.

[W.S. (Gast)]

Michael F. schrieb:
> keine der genannten Variablen ist volatile und falls in "ein paar
> Berechnungen" nirgends ein volatile-Wert genutzt wird, von dem "n"
> abhängt, dann sollte der Compiler das Ergebnis von "maske = 0xFF >> n;"
> bereits zur compile-zeit berechnen können

Nee, falls da irgend ein Argument der Funktion an den ominösen 
Berechnungen beteiligt ist oder ein HW-Register oder irgend eine globale 
Variable, dann kann das eben nicht zur Compilezeit berechnet werden. Ein 
'volatile' ist da nicht nötig.

W.S.

[Bertram Bügler (Gast)]

Oliver S. schrieb:
> Das es dazu auf einem AVR viel schneller wäre, die Maske jedes mal um 1
> zu shiften, an statt den Ausgangswert um n, sei hier nur angemerkt.

Nein n ist nicht etwa der Schleifenzähler, n ergibt sich aus wilden 
Berechnungen mit dem Cordic-Algorithmus. (Der Attiny10 ist 
wahrscheinlich zu klein für float Berechnungen und so mache ich 
Sinus/Cosinus mit dem Cordic-Algorithmus)

Als Tabelle würde das so aussehen

unsigned_8t[9]={0xFF,0x7F,0x3F,0x1F,0x0F,0x07,0x03,0x01,0x00};

[Bertram Bügler (Gast)]

unsigned_8t maske[9]={0xFF,0x7F,0x3F,0x1F,0x0F,0x07,0x03,0x01,0x00};

[Bertram Bügler (Gast)]

uint_8t
 maske[9]={0xFF,0x7F,0x3F,0x1F,0x0F,0x07,0x03,0x01,0x00};

Irgendwann wirds...

[Wilhelm M. (wimalopaan)]

Wenn Dein `n` einen größeren Wertebereich umfasst, aknnst Du es zur 
Compilezeit berechnen lassen:

    static constexpr auto lut = []{
        std::array<uint8_t, 16> d;
        for(uint8_t i{0}; auto& v : d) {
            if (i < 8) {
                v = 0xffu >> i;
            }
            else {
                v = 0;
            }
            ++i;
        }
        return d;
    }();

[0xFFU (Gast)]

Bertram Bügler schrieb:
> Würde,
> falls n jetzt zum Beispiel 255 ist, der Compiler den Armen uC jetzt
> tatsächlich 255 x schieben lassen?

Er shiftet nur ein mal. Aber gleich um x Bits (und nicht x mal). 
Außerdem ist 0xFF eine int-Varialbe (wieder undefined behaviour sogar 
wenn n klein genug ist).

[Bertram Bügler (Gast)]

0xFFU schrieb:
> Er shiftet nur ein mal. Aber gleich um x Bits (und nicht x mal).

Äh nö, die kleinen Attiny haben keinen Barrelshifter AFAIK.
Deshalb habe ich diesen Thread überhaupt gestartet...

[Wilhelm M. (wimalopaan)]

Bertram Bügler schrieb:
> uint_8t
>  maske[9]={0xFF,0x7F,0x3F,0x1F,0x0F,0x07,0x03,0x01,0x00};
>
> Irgendwann wirds...

Nö, immer noch falsch:

uint8_t maske[9]={0xFF,0x7F,0x3F,0x1F,0x0F,0x07,0x03,0x01,0x00};

[Wilhelm M. (wimalopaan)]

Im folgenden mal ein paar Varianten, die mir noch so eingefallen sind:

* test1() führt nie zu UB
* test2() führt zu UB wenn die n_mask größer als 0x0f ist, also der 
Shift >= 16, leider wird das UB vom Compiler hier nicht angewarnt (NDR).
* test3() deckt UB ggf. zur Compiler-Zeit auf (UB in constexpr ist 
zwingend ein error)
* test4() führt nie zu UB

Wegen test3() und der LUT habe ich einfach mal angenommen, dass es eine 
sinnvolle Maske für das `n` gibt, aber trotzdem ein n >= 8 zugelassen.

#include <array>

volatile uint8_t x;
volatile uint8_t n;

static constexpr uint8_t n_mask{0x0f};
//static constexpr uint8_t n_mask{0x1f}; // führt zu UB (s.u.)

void test1() {
    uint8_t m{0xff};
    for(uint8_t i{}; i < (n & n_mask); ++i) {
        m >>= 1; // 8-Bit Shift
    }
    x = m;    
}

void test2() {
    uint8_t m2{0xff};
    x = m2 >> (n & n_mask);  // no UB, wenn rhs < 16: Int-Promo 
}

void test3() {
    static constexpr auto lut = []{
        std::array<uint8_t, (n_mask + 1)> d;
        for(uint8_t i{0}; auto& v : d) {
            v = 0xffu >> i++; // falls UB vorhanden, wird es aufgedeckt
        }
        return d;
    }();
    x = lut[n & n_mask];
}

void test4() {
    switch(n) {
    case 0:
        x = 0xff;
        break;
    case 1:
        x = 0x7f;
        break;
    case 2:
        x = 0x3f;
        break;
    case 3:
        x = 0x1f;
        break;
    case 4:
        x = 0x0f;
        break;
    case 5:
        x = 0x07;
        break;
    case 6:
        x = 0x03;
        break;
    case 7:
        x = 0x01;
        break;
    default:
        x = 0;
        break;
    }
}

Im Anhang das Kompilat.

[Wilhelm M. (wimalopaan)]

... es fehlt die Variante mit der LUT im Pgm-Space, falls man das RAM 
für die Lut sparen muss ...

[mIstA (Gast)]

Bertram Bügler schrieb:
> maske = 0xFF >> n;
> seriell_out(maske);
> /* seriell_out(0xFF >> n); */
> Liegt in einer zeitkritischen Schleife und wird ganz häufig
> aufgerufen!
> Ich könnte natürlich schreiben :
>
> if (n > 8) n = 8; // nötig?!

Wenn n größer als 8 sein kann, dann ist es absolut nötig, sonst darf der 
Compiler auch Code erzeugen der in dem Fall Deine HDD formatiert, alle 
GPIOs auf wechselnde Zufallswerte setzt oder was ihm sonst lustiges 
einfällt. Wird er zwar wahrscheinlich nicht machen, wäre ja auch 
unnötiger Aufwand, aber falls er es macht, hättest Du keinen Grund Dich 
zu beschweren.

Besser wäre allerdings (weil es den - zumindest bei breiteren Datentypen 
ebenfalls problematischen - Fall n=Bitbreite des zu schiebenden Typs 
auch korrekt abfängt):

  maske = (n>7) ? 0 : 0xFF >> n

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

mIstA schrieb:
> Wenn n größer als 8 sein kann,

C rechnet mindestens in int.

[Wilhelm M. (wimalopaan)]

(prx) A. K. schrieb:
> mIstA schrieb:
>> Wenn n größer als 8 sein kann,
>
> C rechnet mindestens in int.

Wie oben

Beitrag "Re: Schieben vs. Tabelle"

schon gesagt, haben wir Integerpromotion. Daher tauchen Probleme erst 
mit
n >= 16 auf. Wie man im Assembler-Code auch schön sehen kann, macht der 
avr-gcc einen 16-Bit Shift daraus.

Nur bei einem einfachen Shift um eine Position optimiert der Compiler 
die Integerpromotion wieder weg und macht 8-Bit Shift. Daher ist test1() 
effektiver als test2() im obigen Beispiel.