Cortex M4 Assemblercode richtig in C nutzen

[Christopher S. (shalec)]

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

[Walter T. (nicolas)]

Was passiert denn, wenn Du den Befehl einfach ausschreibst mit 
Shift-Operationen? Wie sieht das erzeuge Assembler-Listing aus?

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

Christopher S. schrieb:
> dies führte aber zu einem Fehler.

Zu welchem?

[Christopher S. (shalec)]

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.

[Christopher S. (shalec)]

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))

[2⁵ (Gast)]

Was passt an

#include <stdint.h>

uint32_t rbit(uint32_t c)
{
    //return __builtin_rbit(c); 
    asm("rbit %1,%0" : "=r" (c) : "r" (c));
    return c;
}

nicht?

$ arm-none-eabi-gcc -mcpu=cortex-m4 -S -O2 rbit.c 
$ cat rbit.s
[...]        
        .thumb
        .thumb_func
        .fpu softvfp
        .type   rbit, %function
rbit:
        @ args = 0, pretend = 0, frame = 0
        @ frame_needed = 0, uses_anonymous_args = 0
        @ link register save eliminated.
        .syntax unified
@ 6 "rbit.c" 1
        rbit r0,r0
@ 0 "" 2
[...]

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

static inline __attribute__((always_inline))
uint32_t rbit(uint32_t x)
{
  asm("rbit %0,%1" : "=r" (x) : "r" (x));
  return x;
}

[Christopher S. (shalec)]

2⁵ schrieb:
> Was passt an
>

> #include <stdint.h>
> 
> uint32_t rbit(uint32_t c)
> {
>     //return __builtin_rbit(c);
>     asm("rbit %1,%0" : "=r" (c) : "r" (c));
>     return c;
> }
>

>
> nicht?
>

Ich wusste noch nicht, dass man das so schreiben kann. Daher frage ich 
ja :)

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

A. K. schrieb:
>   asm("rbit %0,%1" : "=r" (x) : "r" (x));

... oder andersrum, %1,%0. Weiss grad nicht, wie arm asm das hält.

[Christopher S. (shalec)]

Vielen Dank an alle Codeschnipsel, könntet ihr mir nochmal erklären 
worin der Unterschied in der "static inline" Variante und der anderen 
liegt?

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

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".

[eagle user (Gast)]

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?

// asm.h
#pragma once
#include <stdint.h>

static inline int  // count leading zeroes
CLZ (uint32_t input)
{
uint32_t  result;

   __asm__ (" clz   %0, %1" : "=r" (result) : "r" (input));
   return result;
}

static inline int  // count trailing zeroes
CTZ (uint32_t input)
{
uint32_t  result, tupni;

   __asm__ (" rbit  %0, %2\n"
            " clz   %1, %0" : "=r" (tupni), "=r" (result) : "r" (input));
   return result;
}

[Markus F. (mfro)]

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:

static inline int  // count trailing zeroes
CTZ (uint32_t input)
{
uint32_t  result, tupni;

    __asm__ ("  rbit  %[tupni], %[input]\n"
            "   clz   %[result], %[tupni]"
            /* output */ : [tupni]"=r" (tupni), [result]"=r" (result)
            /* input */ : [input]"r" (input));
    return result;
}

int main(int argc, char *argv[])
{
    xprintf("ctz 0x0e: 0x%02x\r\n", CTZ(0x0e));
    while (1);
}

(ich habe hier die %[]-Schreibweise benutzt (so auch erlaubt), die m.E. 
wesentlich besser zu lesen ist.
Dabei kommt das dabei raus:

    2074:   230e        movs    r3, #14
    2076:   fa93 f2a3   rbit    r2, r3
    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:

static inline int  // count trailing zeroes
CTZ2 (uint32_t input)
{
    uint32_t  result, tupni;

    __asm__ ("  rbit  %[result], %[input]\n"
            "   clz   %[input], %[result]"
            /* output */ : [result]"=r" (result)
            /* input */ : [input]"r" (input));
    return result;
}

... und richtig:

    2070:   210e        movs    r1, #14
    2072:   b508        push    {r3, lr}
    2074:   fa91 f1a1   rbit    r1, r1
    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:

int  // count trailing zeroes
CTZ2 (uint32_t input)
{
    uint32_t  result, tupni;

    __asm__ ("  rbit  %[result], %[input]\n"
            "   clz   %[input], %[result]"
            /* output */ : [result]"=r" (result)
            /* input */ : [input]"r" (input));
    return result;
}

int main(int argc, char *argv[])
{
    xprintf("ctz2 0x0e: 0x%02x, ctz2 0x0e: 0x%02x\r\n", CTZ(0x0e), CTZ(0x0e));

    while (1);
}

Dabei kommt das raus:

    2074:   230e        movs    r3, #14
    2076:   fa93 f1a3   rbit    r1, r3
    207a:   fab1 f381   clz r3, r1
    207e:   fa93 f3a3   rbit    r3, r3
    2082:   fab3 f283   clz r2, r3

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. (nicolas)]

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:

/* Test: Bits vertauschen */
uint32_t reverseBitOrder32(uint32_t in)
{
    uint32_t out = 0, maskl = 0x00010000, maskr = 0x00008000;
    uint_fast8_t i = 1;
    while( maskl ) {
        out |= (in & maskl) >> i;
        out |= (in & maskr) << i;
        maskl<<=1;
        maskr>>=1;
        i+=2;
    }

    return out;
}

 erzeugt der Compiler (GCC 5.4.1) für einen STM32F446 bei 
Optimierungsstufe -O2 noch:

08000506  bne.n  0x80004e8 <main+400>
08000508  str.w  lr, [sp, #20]
0800050C  ldr.w  r12, [sp, #20]
08000510  mov.w  r7, #32768  ; 0x8000
08000514  mov.w  lr, #0
08000518  movs  r2, #1
0800051A  mov.w  r0, #65536  ; 0x10000
0800051E  and.w  r1, r12, r0
08000522  and.w  r3, r12, r7
08000526  lsrs  r1, r2
08000528  lsls  r3, r2
0800052A  adds  r2, #2
0800052C  orrs  r3, r1
0800052E  cmp  r2, #33  ; 0x21
08000530  mov.w  r0, r0, lsl #1
08000534  orr.w  lr, lr, r3
08000538  mov.w  r7, r7, lsr #1
 ...

d.h. erkennt wohl nicht die konstante Vertauschung der Bits, für die ein 
Hardware-Befehl existiert.

[Walter T. (nicolas)]

Aus der Variante:

/* Test: Bits vertauschen */
uint32_t reverseBitOrder32(uint32_t in)
{
    uint32_t out = 0, temp = in;
    for( uint_fast8_t i = 0; i<32; i++ ) {
        out <<= 1;
        out |= in & 1;
        in >>=1;
    }
    return out;
}

Macht er das hier:

080004EC  mov  r2, r4
080004EE  movs  r3, #32
080004F0  movs  r1, #0
080004F2  and.w  r0, r2, #1
080004F6  subs  r3, #1
080004F8  orr.w  r1, r0, r1, lsl #1
080004FC  mov.w  r2, r2, lsr #1
08000500  bne.n  0x80004f2 <main+410>

Er rafft es also immer noch nicht...


OK, also ist hier inline-Assembler wohl angebracht. Einen Versuch war es 
trotzdem wert.

[Markus F. (mfro)]

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().

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

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:

static inline int
CTZ (unsigned input)
{
    unsigned result;
    __asm__ ("  rbit  %[result], %[input]\n"
            "   clz   %[result], %[result]"
            : [result]"=r" (result)
            : [input]"r" (input));
    return result;
}

> 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:

static inline int
CTZ (unsigned input)
{
    __asm__ ("  rbit  %[input], %[input]\n"
            "   clz   %[input], %[input]"
            : [input]"+r" (input)
            : );
    return input;
}

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.

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

Man gibt dem Compiler zusätzliche Freiheit, wenn man die Befehle 
auftrennt:

static inline unsigned
RBIT (unsigned input)
{
    unsigned result;
    __asm__ ("  rbit  %[result], %[input]\n"
            : [result]"=r" (result)
            : [input]"r" (input));
    return result;
}

static inline unsigned
CLZ (unsigned input)
{
    unsigned result;
    __asm__ ("  clz  %[result], %[input]\n"
            : [result]"=r" (result)
            : [input]"r" (input));
    return result;
}

static inline unsigned
CTZ (unsigned input)
{
    return CLZ(RBIT(input));
}

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.