Forum: Mikrocontroller und Digitale Elektronik Präprozessor-Trick gesucht


von Vlad T. (vlad_tepesch)


Lesenswert?

Hi,
ich habe eine Bitmaske zb 0b00110000 um aus einem uint8 ein signal 
rauszupulen.
ich hätt jetzt gern ein Präprozessormakro, dem ich diese Bitmaske geben 
kann und dass mir den shiftwert zurückgibt, den ich brauche um das 
Signal am untersten Bit auszurichten.  die Bits eines Signals sind immer 
zusammenhängend.



Beispiele:
0b00110000   -> 4
0b01111110   -> 1
0b00000111   -> 0


hab schon überlegt, aber ich komm auf nix, was der Präprozessor kann.
Bild mir aber ein mal gelesenzu haben, dass die Präprozessorsprache 
turing-complete ist, also müsste das ja gehen.

Bin mal gespannt auf eure ideen ;-)
Gruß,
Vlad

von Jörg W. (dl8dtl) (Moderator) Benutzerseite


Lesenswert?

Aus avr-libc's <string.h>:
1
#define _FFS(x) \
2
        (1                              \
3
         + (((x) & 1) == 0)             \
4
         + (((x) & 3) == 0)             \
5
         + (((x) & 7) == 0)             \
6
         + (((x) & 017) == 0)           \
7
         + (((x) & 037) == 0)           \
8
         + (((x) & 077) == 0)           \
9
         + (((x) & 0177) == 0)          \
10
         + (((x) & 0377) == 0)          \
11
         + (((x) & 0777) == 0)          \
12
         + (((x) & 01777) == 0)         \
13
         + (((x) & 03777) == 0)         \
14
         + (((x) & 07777) == 0)         \
15
         + (((x) & 017777) == 0)        \
16
         + (((x) & 037777) == 0)        \
17
         + (((x) & 077777) == 0)        \
18
         - (((x) & 0177777) == 0) * 16)

von Peter D. (peda)


Lesenswert?

1
#define LSB_N(i) (\
2
        (i & 1)   ? 1 :\
3
        (i & 2)   ? 2 :\
4
        (i & 4)   ? 3 :\
5
        (i & 8)   ? 4 :\
6
        (i & 16)  ? 5 :\
7
        (i & 32)  ? 6 :\
8
        (i & 64)  ? 7 :\
9
        (i & 128) ? 8 : 0)


Peter

von gast (Gast)


Lesenswert?

darum nicht

#define shifted(x) ((x&0x30)>>4)

von Zulu (Gast)


Lesenswert?

Das mit der Turing-Vollständigkeit halte ich für eine urbane Legende. 
Aber ich mag mich irren. Gib doch mal an, wo Du das gelesen hast.

Das Problem ist, das Du mit dem Preprozessor nur Textersatz machen 
kannst. Auch Parameter werden nur textuell ersetzt. Die Berechnungen 
erfolgen durch den Compiler. Dabei werden nur konstante Ausdrücke 
berechnet.

Letzlich suchst Du also nach einer Funktion, die zur Laufzeit das nötige 
tut.
Da wird die Sache dann schon etwas einfacher.
Zunächst kannst Du eine Tabelle benutzen. Das ist das schnellste.
Es geht ja darum die Bitnummer des niederwertigsten gesetzten Bits zu 
ermitteln, nicht wahr?
1
/* Die bits zahlen ab 1 und nicht ab null, weil sonst der Fall, das kein Bit gesetzt ist nicht erkannt werden kann */
2
3
/* dezimal:           0, 1, 2, 3, 4, 5, 6, 7, 8, ...
4
uint8 bitnummer [] = {0, 1, 2, 1, 3, 1, 2, 1, 4, ...}

Mir fallen da auf Anhieb zwei berechnende Verfahren ein mit denen man 
auch die Tabelle erzeugen könnte.

Das wiederum einfachste wäre selbst ein Bit durchzuschieben, und zu 
zählen, wann denn die Und-Verknüpfung ungleich Null ist.

Das etwas komplizierter würde den Logarithmus zur Basis 2 errechnen, 
wobei vorher die höherwertigen Bits entfernt werden müssen.

von Zulu (Gast)


Lesenswert?

Oh. Das von Peter ist natürlich recht auch möglich und sogar recht 
hübsch.

von Mark B. (markbrandis)


Lesenswert?

Ich wußte gar nicht, dass man den ternären Operator so vergewaltigen 
kann. ;-)

von Vlad T. (vlad_tepesch)


Lesenswert?

>Das mit der Turing-Vollständigkeit halte ich für eine urbane Legende.
>Aber ich mag mich irren. Gib doch mal an, wo Du das gelesen hast.
weiß ich nicht mehr.

>Letzlich suchst Du also nach einer Funktion, die zur Laufzeit das nötige  tut.
Ebend nicht, es soll zur Compiletime gemacht werden.

Das von Peter sieht mir am gesten aus.
An den ?-operator hab ich gar nicht gedacht, nur an if else, was ja aber 
nicht geht, da das ganze ein r-value sein soll.
Danke.

Die Frage ist nur kriegt das jeder c-complier hin mit der optimierung.

von Jörg W. (dl8dtl) (Moderator) Benutzerseite


Lesenswert?

Vlad Tepesch schrieb:

> Die Frage ist nur kriegt das jeder c-complier hin mit der optimierung.

Wenn nicht, dann solltest du über einen Wechsel nachdenken.

von Uhu U. (uhu)


Lesenswert?

Was man mit der CPP-Sprache alles anstellen kann, kann man dem Teilpaket 
preprocessor der BOOST-Library entnehmen.

Der Aufwand, den das Paket treibt, ist gigantisch, weil der CPP 
gigantisch blöd ist - aber es geht.

http://sourceforge.net/projects/boost/files/

von Zulu (Gast)


Lesenswert?

@ Vlad

>>Letzlich suchst Du also nach einer Funktion, die zur Laufzeit das nötige  tut.
>Ebend nicht, es soll zur Compiletime gemacht werden.
>Das von Peter sieht mir am gesten aus.

Na aber, das von Peter rennt ja auch erst zur Laufzeit. Das kann nicht 
schon zur Compilezeit vereinfacht werden.

von Uhu U. (uhu)


Lesenswert?

Zulu schrieb:
> Na aber, das von Peter rennt ja auch erst zur Laufzeit. Das kann nicht
> schon zur Compilezeit vereinfacht werden.

Das ist falsch. #define wird vom CPP abgearbeitet und alle Parameter 
dafür müssen zur Übersetzungszeit bekannt sein.

von Zulu (Gast)


Lesenswert?

>> Na aber, das von Peter rennt ja auch erst zur Laufzeit. Das kann nicht
>> schon zur Compilezeit vereinfacht werden.

>Das ist falsch. #define wird vom CPP abgearbeitet und alle Parameter
>dafür müssen zur Übersetzungszeit bekannt sein.

So? Na, mit der Ansicht komme ich seit 20 Jahren durchs 
Programmiererleben. Wenn sie also auch falsch sein sollte, dann 
funktioniert es wenigstens wenn man davon ausgeht das sie richtig ist.

von STK500-Besitzer (Gast)


Lesenswert?

>Das ist falsch. #define wird vom CPP abgearbeitet und alle Parameter
>dafür müssen zur Übersetzungszeit bekannt sein.

Was fürn Ding?
Der Präprozessor machrt doch nichts anderes als eine Textersetzung, 
ausser wenn es sich um eine Berechnung mit Konstanten handelt. Dann 
rechnet er sich auch aus. Deswegen nennt sicjh das Ding ja auch Makro 
und erhöht die Übersichtlichkeit.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Uhu Uhuhu schrieb:
> Zulu schrieb:
>> Na aber, das von Peter rennt ja auch erst zur Laufzeit. Das kann nicht
>> schon zur Compilezeit vereinfacht werden.
>
> Das ist falsch. #define wird vom CPP abgearbeitet und alle Parameter
> dafür müssen zur Übersetzungszeit bekannt sein.

Nö. Es ist lediglich so, daß wenn der Compiler zur Compilezeit alles 
auswerten kann, er Konstanten falten und nicht Code erzeugen muss, der 
zur Laufzeit berechnet.

Übrigens gibt's in gcc auch
1
__builtin_ctz (x);

"ctz" steht für "count trailing zeros"

Johann

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

> Das ist falsch. #define wird vom CPP abgearbeitet und alle Parameter
> dafür müssen zur Übersetzungszeit bekannt sein.
Richtig muß es heißen:
Wenn alle Parameter zum Übersetzungszeitpunkt konstant und bekannt sind, 
wird es sofort berechnet.

Sowas kann z.B. nur zur Laufzeit berechnet werden:
1
#define square(x) ((x)*(x))
2
:
3
    r = square(a);

Sowas kann bereits beim Übersetzen berechnet werden:
1
#define square(x) ((x)*(x))
2
:
3
    r = square(4);

von Oliver (Gast)


Lesenswert?

>Das ist falsch. #define wird vom CPP abgearbeitet und alle Parameter
>dafür müssen zur Übersetzungszeit bekannt sein.

Das ist noch falscher. Der CPP ersetzt grundsätzlich nur Text. Und 
solange da eine Variable x oder i drin ist, die erst zur Laufzeit 
bekannt ist, macht den Rest der Compiler.

Wenn alle Werte schon zur Compilezeit definiert wären, würde das 
narütlich auch zur Compilezeit berechnet, aber nicht durch den CPP, 
sondern durch den Compiler. Allerdings kann bei der Aufgabenstellung 
eigentlich nicht alles bekannt sein.


Oliver

von Uhu U. (uhu)


Lesenswert?

Zulu schrieb:
>>> Na aber, das von Peter rennt ja auch erst zur Laufzeit. Das kann nicht
>>> schon zur Compilezeit vereinfacht werden.
>
>>Das ist falsch. #define wird vom CPP abgearbeitet und alle Parameter
>>dafür müssen zur Übersetzungszeit bekannt sein.
>
> So? Na, mit der Ansicht komme ich seit 20 Jahren durchs
> Programmiererleben. Wenn sie also auch falsch sein sollte, dann
> funktioniert es wenigstens wenn man davon ausgeht das sie richtig ist.

Du hast dich auf diesen Beitrag bezogen: 
Beitrag "Re: Präprozessor-Trick gesucht" ?

Der CPP setzt die rechte Seite der Macrodefinition für den Macroaufruf 
ein.

Es handelt sich um einen rein konstanten Ausdruck und das Ergebnis ist 
dem Compiler zur Übersetzungszeit bekannt und kann - vom Optimierer - 
durch das konstante Ergebnis ersetzt werden.

von Sven P. (Gast)


Lesenswert?

Der Präprozessor rechnet wenig bis garnix. Selbst wenn man mit dem so 
einen ternären Operator vergewaltigt, ersetzt er nur die Variablen und 
lässt den Compiler rechnen. Wenns nachher konstant ist, optimiert der 
Compiler es, wenn nicht, läufts wohl auf irgendeine verzweigte 
Konstruktion raus und gut ist.

Wo der Präprozessor 'rechnet', das sind z.B. die Bedingungen hinter 
'#if' und '#elif'.

von Uhu U. (uhu)


Lesenswert?

Oliver schrieb:
> Wenn alle Werte schon zur Compilezeit definiert wären, würde das
> narütlich auch zur Compilezeit berechnet, aber nicht durch den CPP,
> sondern durch den Compiler.

Siehe oben.

> Allerdings kann bei der Aufgabenstellung eigentlich nicht alles bekannt
> sein.

Dann lies nochmal das Eingangsposting: Dort steht nichts von einer 
Bitmaske, die erst zur Laufzeit bekannt ist, sondern es ist nach einem 
Präprozessormakro gefragt, das die Verschiebung für die Maske berechnet. 
Damit ist implizit, daß die Maske zur Übersetzungszeit bekannt sein 
muß.

von Jörg W. (dl8dtl) (Moderator) Benutzerseite


Lesenswert?

Sven P. schrieb:
> Der Präprozessor rechnet wenig bis garnix.

Er rechnet nur (und zwar mit dem Typ `int', den man auch nicht
vergrößern kann) innerhalb der Ausdrücke, die nach #if stehen.

von Zulu (Gast)


Lesenswert?

>Dann lies nochmal das Eingangsposting: Dort steht nichts von einer
>Bitmaske, die erst zur Laufzeit bekannt ist, sondern es ist nach einem
>Präprozessormakro gefragt, das die Verschiebung für die Maske berechnet.
>Damit ist implizit, daß die Maske zur Übersetzungszeit bekannt sein
>muß.

Weder der Text von Dir, den ich hier zitiere, noch die Fragestellung 
implizieren, dass der Makroparameter bekannt sein muss .
Man kann ihn so verstehen und das habe ich übersehen. Es wäre aber auch 
möglich gewesen, dass das "signal" der Makroparameter ist und so habe 
ich es aufgefasst.

Es wäre für mich viel hilfreicher gewesen wenn Du geschrieben hättest.
"Ich verstehe die Fragestellung so, das das gesuchte Makro mit einem 
konstanten Wert aufgerufen werden soll".

Mein Irrtum basierte nicht darauf, das ich nicht wusste, das bei 
konstanten Ausdrücken, der Compiler vereinfachen kann. Die Nennung des 
Grundes, warum Du annimmst, das die die Vereinfachung in diesem Fall 
greift, hätte mehr gebracht als allgemeine (und dazu noch unpräzise) 
Aussagen.

von Zulu (Gast)


Lesenswert?

Ooops: Das vorherige ist an Uhu gerichtet.

von Jörg W. (dl8dtl) (Moderator) Benutzerseite


Lesenswert?

Johann L. schrieb:

> Übrigens gibt's in gcc auch
>
1
> __builtin_ctz (x);
2
>

Besser noch: __builtin_ffs().

von Vlad T. (vlad_tepesch)


Lesenswert?

Um den Diskussionen ein Ende zu bereiten:
die Bitmaske ist ein #define.

es geht um die spezifikation eines Signals (wie erwähnt)
da wär es ungünstig, wenn erst zur laufzeit klar sein würde welche Daten 
an welchen bits stehen.

und ja. der PP rechnet selbst nix, der ersetzt nur.
Allerdings rechnet der Compiler, sofer die Optimierung angaschaltne ist.
Optimalerweise sollte dieser dann in seinem abstraktem Syntaxbaum so 
weit nach oben gehen, bis eins der Argumente primitiver operationen 
nicht mehr zur Compilezeit bestimmbar ist.

Die Frage ist halt inwiefern man sich darauf verlassen kann, dass sie 
compiletime optimierung des ternären operators zum Grundwissen eines 
jeden Compilers gehört.

von Jörg W. (dl8dtl) (Moderator) Benutzerseite


Lesenswert?

Vlad Tepesch schrieb:

> Die Frage ist halt inwiefern man sich darauf verlassen kann, dass sie
> compiletime optimierung des ternären operators zum Grundwissen eines
> jeden Compilers gehört.

Siehe oben.  Wenn die Berechnung von konstanten Ausdrücken zur
Compilezeit nicht zum Optmimierungsumfang deines Compilers gehört,
dann solltest du dich dringend nach was anderem umschauen.

von Zulu (Gast)


Lesenswert?

Der Assembler-Text sollte das klarstellen.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Jörg Wunsch schrieb:
> Johann L. schrieb:
>
>> Übrigens gibt's in gcc auch
>>
1
>> __builtin_ctz (x);
2
>>
>
> Besser noch: __builtin_ffs().

Und dann? ffs zählt doch vom MSB, während ctz vom LSB her zählt (was 
wohl gewünscht ist).

__builtin_ctz (x) wertet übrigens auch zu Compilezeit aus falls die 
Eingabe bekannt ist.

Johann

von Jörg W. (dl8dtl) (Moderator) Benutzerseite


Lesenswert?

Johann L. schrieb:

> Und dann? ffs zählt doch vom MSB, während ctz vom LSB her zählt (was
> wohl gewünscht ist).

— Built-in Function: int __builtin_ffs (unsigned int x)

Returns one plus the index of the least significant 1-bit of x,
                                  ^^^^^^^^^^^^^^^^^^^^^^^
or if x is zero, returns zero.

von Vlad T. (vlad_tepesch)


Lesenswert?

buildins sind keine Option, da der Code dann nicht mehr portabel ist.

Das ganze muss in 3 verschiedenen Toolchains funktionieren.

von yalu (Gast)


Lesenswert?

Die bereits geposteten Makros werden etwas unhandlich, wenn man auch 16-
oder 32-Bit-Masken verarbeiten will. Kompakter geht es so:
1
#define CTZ2(x) (~(x)&0x01)
2
#define CTZ4(x) ((x)&0x0003 ? CTZ2(x) : 2+CTZ2((x)>> 2))
3
#define CTZ8(x) ((x)&0x000f ? CTZ4(x) : 4+CTZ4((x)>> 4))
4
#define CTZ16(x) ((x)&0x00ff ? CTZ8(x) : 8+CTZ8((x)>> 8))
5
#define CTZ32(x) ((x)&0xffff ? CTZ16(x) : 16+CTZ16((x)>>16))

CTZ32 verhält sich im Wesentlichen wie __builtin_ctz auf 32-Bit-
Rechnern. Zu beachten: CTZ32(0) liefert 31, obwohl unendlich oder 32
logischer wären. Man könnte diesen Fall durch eine zusätzlich Abfrage
abfangen, was aber für Vlads Anwendung nicht nötig ist, da dort 0 nie
als Argument vorkommt. Auch __builtin_ctz sollte nicht mit dem Argument
0 aufgerufen werden, da dann das Ergebnis "undefined" ist.

Wenn man nur 8 Bits benötigt, kann man die beiden letzten Zeilen
weglassen.

von Michael (Gast)


Lesenswert?

Man könnte die Berechnung / Schiebeoperation noch etwas beschleunigen.
In der Lösung oben werden bis zu 7 Shiftoperationen fällig. Wenn man 
beispielsweise die Daten zunächst mit 0b00001111 verodert und prüft ob 
der Wert größer als null ist, befindet sich das erste lsb im unteren 
Nibble sonst möglicherweise im oberen. Danach werden nur noch maximal 4 
Shifts notwendig.

Zugegeben bei 8bit ist der Performancegewinn nicht so groß, bei 16 / 
32bit bringt das einiges.

von chris (Gast)


Lesenswert?

Wenn der Code portabel sein sollte, ev auch bei versch GCC gibt es mit
der optimierung von ?: probleme, bzw wird diese zur Laufzeit und nicht
zur Kompilerzeit gemacht.
Also, bits zählen mit | oder +, ein ?: kann sehr schnell zu einem 
if/else
ausarten.

von Peter D. (peda)


Lesenswert?

chris schrieb:
> Wenn der Code portabel sein sollte, ev auch bei versch GCC gibt es mit
> der optimierung von ?: probleme, bzw wird diese zur Laufzeit und nicht
> zur Kompilerzeit gemacht.

Ist das jetzt Dein persönliches Bauchgefühl oder kannst Du das irgendwie 
belegen.
Warum sollte ausgerechnet dieser Operator anders behandelt werden?

Ich weiß, daß das ?: seltener benutzt wird und daher manchen Leuten 
suspekt ist.

Der AVR-GCC und der Keil C51 machen es jedenfalls zur Compilezeit.


Peter

P.S.:
Ich verwende ihn oft in Macros anstatt Inline-Funktionen

von yalu (Gast)


Lesenswert?

Meines Wissens ist nicht vorgeschrieben, dass der Compiler konstante
Ausdrücke immer zur Compilezeit berechnet (habe jetzt aber auch nicht
nachgeschaut). In einigen Fällen kann er aber gar nicht anders, bspw.
bei der Dimensionierung von Arrays:
1
static int arr[5>3 ? 4*5 : 5*6];  // legal -> Array mit 20 Elementen

Wenn der Compiler in der Lage ist, obigen Ausdruck auszurechnen, gibt es
keinen Grund, warum er das nicht auch in folgendem Fall tun sollte:
1
x = 5>3 ? 4*5 : 5*6;

Und weil der Compiler die Auswertung konstanter Ausdrücke sowieso können
muss, zählt diese üblicherweise auch nicht zu den Optimierungen. So
macht der GCC (aber wahrscheinlich auch jeder andere C-Compiler) auch
bei ausgeschalteter Optimierung aus dem zweiten Beispiel einfach x=20.
Das gleiche gilt für die in diesem Thread geposteten Makros, wenn das
Argument eine Konstante ist.

von Maxxie (Gast)


Lesenswert?

@Turing Vollständigkeit des Preprozessors
Ist er auch nicht:

Der Präprozessor erzeugt kontextfreie Gramatik (Genau ein nicht 
terminalsymbold wird durch eine beliebige Menge von terminal- und nicht 
terminalsymbolen ersetzt)

Damit ist der Preprozessor gleichmächtig zu nicht-determistischen 
Kellerautomaten. Diese sind bekanntlich nicht turingmächtig. Allerdings 
mächtiger als endliche Automaten.
Für viele nicht triviale Dinge also durchaus brauchbar :-D

von Vlad T. (vlad_tepesch)


Lesenswert?

http://www.ioccc.org/2001/herrmann1.hint
http://www.ioccc.org/2001/herrmann1.c

du scheinst (mit einschränkungen) recht zu haben,

wenn du dem Präprozessor mehrere (beliebig viele) iterationen erlaubst, 
ist er es wohl doch.

von Maxxie (Gast)


Lesenswert?

Oh, den "Beweis" hab ich schon gefunden. Aber leider hat der einen 
Fehler.

Es reicht für die Turing-Vollständigkeit nicht eine große Menge von 
Turing-Maschinen nachbauen zu können, sondern muss zeigen, dass er alle 
TMs nachbilden kann.

Der seit Gödel standardisierte Weg dazu ist die UTM zu implementieren. 
In dem "Beweis" kann ich keine solche entdecken, oder irgendeine andere 
Induktion.

von Maxxie (Gast)


Lesenswert?

Es muss natürlich "eine UTM" heissen.

von Mark B. (markbrandis)


Lesenswert?

War die Vorlesung in Theoretischer Informatik doch zu was gut :-)

von Vlad T. (vlad_tepesch)


Lesenswert?

Ich habs mir nicht im detail angeschaut, ich fand den code einfach nur 
geil.

von Prof. Dr.-Ing. (Gast)


Lesenswert?

Ja, beim IOCCC gibt's schon krankes Zeug :-)
Schade dass der anscheinend überhaupt nicht mehr stattfindet; die 
bringen es nicht mal mehr fertig den Code der letztmaligen Gewinner 
(2006?) zu posten.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.