Hallo allerseits,
ich möchte gerne die Bitfolge eines Integers invertieren, d.g. RBIT [1]
nutzen. Ich dachte, dass ich sowas durch "__builtin_rbit(x)" nutzen
kann, dies führte aber zu einem Fehler. Aber wie nutze ich das korrekt
in C?
Mein Ziel: Eine Bitfolge umkehren.
D.h. angenommen ich habe "0b1010" dann "0b0101". Laut der Beschreibung
soll das wohl RBIT leisten. Eine schnellere Lösung gibt es dann wohl
nicht.
Die Verwendung: Ich übergebe einen uint32_t typen an die Funktion und
bekomme die umgekehrte Bitfolge zurück.
[1]
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0553a/BABJJDDB.html
Meinst du, wenn ich den Befehl in C per Hand programmiere? Ich bin
relativ neu in Programmierwelt. Nutze C erst seit knapp 3 Monaten und
das ist praktisch neues Terrain.
A. K. schrieb:> Christopher S. schrieb:>> dies führte aber zu einem Fehler.>> Zu welchem?
undefined reference to `__builtin_rbit'
und
gf_arithmetics.c:12:20: warning: implicit declaration of function
'__builtin_rbit' [-Wimplicit-function-declaration]
#define REVERT(x) (__builtin_rbit(x))
^
gf_arithmetics.c:205:14: note: in expansion of macro 'REVERT'
uint8_t a = REVERT(A[10]);
Implementiert als:
#define REVERT(x) (__builtin_rbit(x))
das hier funktioniert übrigens:
#define CLZ(x) (__builtin_clz(x))
Christopher S. schrieb:> Vielen Dank an alle Codeschnipsel, könntet ihr mir nochmal erklären> worin der Unterschied in der "static inline" Variante und der anderen> liegt?
Ohne ist das eine externe Funktionsdefinition, die es exakt einmal geben
darf. Mit "static inline" darf sie in jedem Quellfile auftauchen, wird
aber meist inlined. Der Kram dahinter ändert das "meist" zu "immer".
darf ich bitte auch so eine Frage fragen?
Warum habe ich in CTZ() das Ergebnis doppelt drin stehen? Es
funktioniert, aber hier kann man doch bestimmt etwas verbessern?
eagle user schrieb:> aber hier kann man doch bestimmt etwas verbessern?
Jein.
Inline-Assembler ist bezüglich des möglichen
sich-selbst-ins-Knie-Schiessen-Potentials die Steigerung (um nicht zu
sagen, Potenzierung) von C.
Schauen wir uns mal an, was der Inline-Assembler daraus macht:
(ich habe hier die %[]-Schreibweise benutzt (so auch erlaubt), die m.E.
wesentlich besser zu lesen ist.
Dabei kommt das dabei raus:
1
2074: 230e movs r3, #14
2
2076: fa93 f2a3 rbit r2, r3
3
207a: fab2 f182 clz r1, r2
Wir konstatieren: funktioniert, aber belegt - wie Du ja bereits bemerkt
hast - ein paar Register/Variablen mehr als notwendig. Man könnte jetzt
auf die Idee kommen, das zu optimieren:
1
static inline int // count trailing zeroes
2
CTZ2 (uint32_t input)
3
{
4
uint32_t result, tupni;
5
6
__asm__ (" rbit %[result], %[input]\n"
7
" clz %[input], %[result]"
8
/* output */ : [result]"=r" (result)
9
/* input */ : [input]"r" (input));
10
return result;
11
}
... und richtig:
1
2070: 210e movs r1, #14
2
2072: b508 push {r3, lr}
3
2074: fa91 f1a1 rbit r1, r1
4
2078: fab1 f181 clz r1, r1
Prima, statt drei Registern brauchen wir jetzt nur noch eins.
Funktioniert.
Allerdings nur genauso lange, bis wir auf die Idee kommen, das ganze
mehrfach aufzurufen:
Der zweite Aufruf macht nicht das, was er soll. Statt "0xe" als Eingabe
wird das Ergebnis des letzten Aufrufs genommen, was definitiv nicht das
ist, was wir haben wollten.
Leider kann man über input-constraints nicht angeben, ob input-Parameter
im Inline-Code verändert werden oder nicht, der Compiler geht aber davon
aus, dass das nicht der Fall ist. Früher konnte man mal Parameter in der
Clobber-Liste angeben, das geht aber nicht mehr. Also muss man selbst
darauf achten.
Walter T. schrieb:> Was passiert denn, wenn Du den Befehl einfach ausschreibst mit> Shift-Operationen?
Weil ich neugierig war, habe ich es einfach mal probiert:
Aus diesem naiv zusammengeschusterten Stück:
1
/* Test: Bits vertauschen */
2
uint32_treverseBitOrder32(uint32_tin)
3
{
4
uint32_tout=0,maskl=0x00010000,maskr=0x00008000;
5
uint_fast8_ti=1;
6
while(maskl){
7
out|=(in&maskl)>>i;
8
out|=(in&maskr)<<i;
9
maskl<<=1;
10
maskr>>=1;
11
i+=2;
12
}
13
14
returnout;
15
}
erzeugt der Compiler (GCC 5.4.1) für einen STM32F446 bei
Optimierungsstufe -O2 noch:
1
08000506 bne.n 0x80004e8 <main+400>
2
08000508 str.w lr, [sp, #20]
3
0800050C ldr.w r12, [sp, #20]
4
08000510 mov.w r7, #32768 ; 0x8000
5
08000514 mov.w lr, #0
6
08000518 movs r2, #1
7
0800051A mov.w r0, #65536 ; 0x10000
8
0800051E and.w r1, r12, r0
9
08000522 and.w r3, r12, r7
10
08000526 lsrs r1, r2
11
08000528 lsls r3, r2
12
0800052A adds r2, #2
13
0800052C orrs r3, r1
14
0800052E cmp r2, #33 ; 0x21
15
08000530 mov.w r0, r0, lsl #1
16
08000534 orr.w lr, lr, r3
17
08000538 mov.w r7, r7, lsr #1
18
...
d.h. erkennt wohl nicht die konstante Vertauschung der Bits, für die ein
Hardware-Befehl existiert.
Dazu gibt's einen enhancement request:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50481
Es ist also nicht ausgeschlossen, dass sich ein weiterer Versuch mit
einer der nächsten Compilerversionen lohnt.
CTZ gibt's schon länger als __builtin_ctz().
Markus F. schrieb:> Inline-Assembler ist bezüglich des möglichen> sich-selbst-ins-Knie-Schiessen-Potentials die Steigerung (um nicht zu> sagen, Potenzierung) von C.
Stimmt. ;-)
Vorschlag:
1
staticinlineint
2
CTZ(unsignedinput)
3
{
4
unsignedresult;
5
__asm__(" rbit %[result], %[input]\n"
6
" clz %[result], %[result]"
7
:[result]"=r"(result)
8
:[input]"r"(input));
9
returnresult;
10
}
> Leider kann man über input-constraints nicht angeben, ob input-Parameter> im Inline-Code verändert werden oder nicht
Aber man kann beim Output angeben, dass er auch ein Input ist:
1
staticinlineint
2
CTZ(unsignedinput)
3
{
4
__asm__(" rbit %[input], %[input]\n"
5
" clz %[input], %[input]"
6
:[input]"+r"(input)
7
:);
8
returninput;
9
}
Anders würden sich 1-Operand Befehle wie x86 NEG nicht sinnvoll abbilden
lassen. Die Variante mit separatem Resultat erlaubt dem Compiler aber,
einen möglicherweise sonst erforderlichen Move einzusparen.
Man gibt dem Compiler zusätzliche Freiheit, wenn man die Befehle
auftrennt:
1
staticinlineunsigned
2
RBIT(unsignedinput)
3
{
4
unsignedresult;
5
__asm__(" rbit %[result], %[input]\n"
6
:[result]"=r"(result)
7
:[input]"r"(input));
8
returnresult;
9
}
10
11
staticinlineunsigned
12
CLZ(unsignedinput)
13
{
14
unsignedresult;
15
__asm__(" clz %[result], %[input]\n"
16
:[result]"=r"(result)
17
:[input]"r"(input));
18
returnresult;
19
}
20
21
staticinlineunsigned
22
CTZ(unsignedinput)
23
{
24
returnCLZ(RBIT(input));
25
}
Für eine Maschine mit einfacher superskalarer Befehlsausführung (wie
Cortex M7) kann der Compiler dann die Befehle passend umordnen. Die
beiden Befehle lassen sich ja nur nacheinander ausführen. In dieser Form
hingegen hingegen lassen sich die Befehle von 2 CTZ Aufrufen so
ineinander verzahnen, so dass pro Takt auch 2 Befehle ausgeführt werden.