reihenfolge der bits in einem byte umdrehen

[kernel_panic (Gast)]

hallo alle!

ich möchte die reihenfolge der bits in einem byte mit C umdrehen. also 
zb aus
10001001 -> 10010001 machen. muss ich das in einer schleife tun oder 
gibt es dafür eine funktion.

[Rufus Τ. F. (rufus)]

Das musst Du schon selbst erledigen. Eine Funktion gibt es dafür nicht.

Kommt es auf Geschwindigkeit an, dann ließe sich eine Tabelle mit 256 
Einträgen verwenden ...

[kernel_panic (Gast)]

ok danke ich dachte nur vielleicht könnte ich meine momentane lösung 
verschönern...

[Peter (Gast)]

Ich weiss nicht wie deine Momentane Lösung aussieht, aber so gehts schon 
recht elegant:

{
  Val = (Val&0xF0)>>4 | (Val&0x0F)<<4;
  Val = (Val&0xCC)>>2 | (Val&0x33)<<2;
  Val = (Val&0xAA)>>1 | (Val&0x55)<<1;
}

[Jörg W. (dl8dtl) (Moderator)]

Und, hast du mal nachgerechnet, wie elegant das wirklich ist?

Das letzte Mal, als ich es nachgerechnet habe, war die simple Schleife
bei einem Byte, das es umzudrehen gilt, kürzer und schneller.

[Peter (Gast)]

Hängt natürlich sehr davon ab, wie "smart" der Optimizer ist.  Im 
Idealfall wird für "Val = (Val&0xF0)>>4 | (Val&0x0F)<<4;" eine "swap 
Val" ASM-Instruktion ausgeführt!

Habs mal ausprobiert und dabei mit Ensetzen festgestellt, dass der 
aktuelle WinAVR mit -OS ein riesen Schrott erzeugt!

unsigned char Val;
Val= PORTC;
Val = (Val&0xF0)>>4 | (Val&0x0F)<<4;
Val = (Val&0xCC)>>2 | (Val&0x33)<<2;
Val = (Val&0xAA)>>1 | (Val&0x55)<<1;
PORTC=Val;

Wird zu:

Val= PORTC;
  IN      R18,0x15         In from I/O location
Val = (Val&0xF0)>>4 | (Val&0x0F)<<4;
  CLR     R19              Clear Register
Val = (Val&0xCC)>>2 | (Val&0x33)<<2;
  MOV     R24,R18          Copy register
  SWAP    R24              Swap nibbles
  ANDI    R24,0xF0         Logical AND with immediate
  LDI     R23,0x04         Load immediate
  LSR     R19              Logical shift right
  ROR     R18              Rotate right through carry
  DEC     R23              Decrement
  BRNE    PC-0x03          Branch if not equal
  OR      R24,R18          Logical OR
  CLR     R25              Clear Register
63:           Val = (Val&0xAA)>>1 | (Val&0x55)<<1;
  MOVW    R18,R24          Copy register pair
  ANDI    R18,0xCC         Logical AND with immediate
  ANDI    R19,0x00         Logical AND with immediate
  ASR     R19              Arithmetic shift right
  ROR     R18              Rotate right through carry
  ASR     R19              Arithmetic shift right
  ROR     R18              Rotate right through carry
  ANDI    R24,0x33         Logical AND with immediate
  ANDI    R25,0x00         Logical AND with immediate
  LSL     R24              Logical Shift Left
  ROL     R25              Rotate Left Through Carry
  LSL     R24              Logical Shift Left
  ROL     R25              Rotate Left Through Carry
  OR      R18,R24          Logical OR
  MOV     R24,R18          Copy register
  CLR     R25              Clear Register
  MOVW    R18,R24          Copy register pair
  ANDI    R18,0xAA         Logical AND with immediate
  ANDI    R19,0x00         Logical AND with immediate
  ASR     R19              Arithmetic shift right
  ROR     R18              Rotate right through carry
  ANDI    R24,0x55         Logical AND with immediate
  ANDI    R25,0x00         Logical AND with immediate
  LSL     R24              Logical Shift Left
  ROL     R25              Rotate Left Through Carry
  OR      R18,R24          Logical OR
PORTC=Val;
  OUT     0x15,R18         Out to I/O location

Ist ja echt zum kotzen, hab eigentlich immer gedacht der AVR-GCC sei
besser!

Peter

[Jörg W. (dl8dtl) (Moderator)]

Abgesehen vom bekannten Problem der überflüssigen Bearbeitung der
high bytes, was bitte würdest du an diesem Code noch großartig
verbessern wollen?

Du hast vergessen, dass der "smart" aussehene C-Code auf einer
Maschine, die nicht shift/rotate N kann, sondern nur shift/rotate 1
zwangsläufig einen ganzen Batzen Code erzeugen muss.

[Peter (Gast)]

Naja, ich würde erwarten, dass der Otimizer tut, was er tun sollte, 
nämlich den generierten Code optimeren. Ich finde dazu dazu gehört auch 
dass er erkennen müsste, wenn int Konstanten auf 1 Byte reduziert werden 
dürfen, weil alle anderen Terme des Ausdrucks ebenfalls nur 8-Bit Werte 
sind.

Das mindeste wäre, dass wenn ich schon die Konstanten explizit auf 
unsigned char caste, keine 16 Bit Operationen mehr erzeugt werden.

Wieso werden Typecasts von Konstanten ignoriert?

Ich würde in etwa den folgenden Output erwarten:

Val= PORTC;
  IN      R25,0x15         In from I/O location
Val = (u08)((Val & 0xF0)>>4) | (u08)((Val & 0x0F)<<4);
  SWAP    R25              Swap nibbles
Val = (u08)((Val & 0xCC)>>2) | (u08)((Val & 0x33)<<2);
  MOV     R25,R24          Copy register
  ANDI    R25,0xCC         Logical AND with immediate
  LSR     R25              Logical shift right
  LSR     R25              Logical shift right
  ANDI    R24,0x33         Logical AND with immediate
  LSL     R24              Logical Shift Left
  LSL     R24              Logical Shift Left
  OR      R25,R24          Logical OR
Val = (u08)((Val & 0xAA)>>1) | (u08)((Val & 0x55)<<1);
  MOV     R24,R25          Copy register
  ANDI    R24,0xAA         Logical AND with immediate
  LSR     R24              Logical shift right
  ANDI    R25,0x55         Logical AND with immediate
  LSL     R25              Logical Shift Left
  OR      R25,R24          Logical OR
PORTC=Val;
  OUT     0x15,R25         Out to I/O location

[Peter D. (peda)]

Versuch mal das hier:

unsigned char mirror( unsigned char a )
{
  a = ((a >> 4) & 0x0F) | ((a << 4) & 0xF0);
  a = ((a >> 2) & 0x33) | ((a << 2) & 0xCC);
  a = ((a >> 1) & 0x55) | ((a << 1) & 0xAA);

  return a;
}

Peter

[Jörg W. (dl8dtl) (Moderator)]

Peter wrote:

> Ich finde dazu dazu gehört auch dass er erkennen müsste, wenn int
> Konstanten auf 1 Byte reduziert werden dürfen, weil alle anderen
> Terme des Ausdrucks ebenfalls nur 8-Bit Werte sind.

Dass er das oft nicht (richtig gut) kann, ist ein alter Hut.  Das
liegt einerseits daran, dass das bei GCC sonst für kaum ein anderes
Target wirklich notwendig ist (weil deren natürliche Wortbreite den
Mindestforderungen an ein int gemäß C-Standard entspricht), zweitens
liegt es wohl (so hat mir mal jemand gesagt) daran, dass der AVR-GCC
nicht als richtige 8-bit-Maschine implementiert ist, sondern als
fiktive 16-bit-Maschine, bei der dann Ausnahmen für 8 bits separat
definiert worden sind.

> Das mindeste wäre, dass wenn ich schon die Konstanten explizit auf
> unsigned char caste, keine 16 Bit Operationen mehr erzeugt werden.

Du kannst die Konstante casten wie du willst, der C-Standard verlangt,
dass die Rechnung so auszuführen ist, als wären alle
Zwischenergebnisse wenigstens vom Typ "int".  Genau das macht der
Compiler dann folglich erst einmal (damit die compliance
sichergestellt ist), und beim anschließenden Erkennen, dass das obere
Byte nichts zum Ergebnis beitragen kann, fehlt's zuweilen.

Davon abgesehen funktioniert es mit Peters Version schon recht gut.
Dort fehlt eigentlich fast nur noch die Erkenntniss, dass

        mov r25,r24
        swap r25
        andi r25,0xf0
        swap r24
        andi r24,0x0f
        or r24,r25
        mov r25,r24

nichts weiter als

        swap r25
        mov r24,r25

macht.  Das müsste man wohl dem Optimizer wirklich mal beibringen
können, gibt's hier jemanden, der genügend RTL versteht das zu tun?
;-)

Dennoch, wenn du's insgesamt nachrechnest, selbst mit dem reparierten
swap ist das Ergebnis nicht wirklich besser (gleich schnell mit mehr
Code) als mit einer einfachen Schleife.  So genial dieser Algorithmus
für große Zahlen ist, bei 8 bits kann er seinen Charme nicht
ausspielen.

[Peter (Gast)]

Okydoky, der Loop ist dann offenbar tatsächlich die beste Lösung, wenn 
man nicht etwas in Assembler stricken möchte!

MfG Peter

[Jörg W. (dl8dtl) (Moderator)]

Peter wrote:

> Okydoky, der Loop ist dann offenbar tatsächlich die beste Lösung, wenn
> man nicht etwas in Assembler stricken möchte!

Du hast es immer noch nicht verstanden: selbst in Assembler wirst du
nicht besser werden als mit der Schleife.

[Stefan K. (_sk_)]

<WAS> ist schon besser?
Wenn das selten gemacht wird, dann "besser" ggf. wenig Speicherbedarf 
haben, die Laufzeit ist nicht so wichtig.
Muss das sehr oft getan werden, ist es genau andersherum.
Im Extremfall lohnt es sich, eine Tabelle mit den gespiegelten Bitwerten 
anzulegen und darauf zugreifen:

PROGMEM uint8_t bit_revers_tab[256] = { 0x00, 0xF0, 0x40, 0x20, ...};
uint8_t my_revers_byte;
uint8_t my_byte;

  my_byte = 0x01;
  my_revers_byte = pgm_read_byte(bit_revers_tab + my_byte;);

Das ist zwar unschlagbar schnell, dafür schmerzen die 256 Tabbellenbytes 
vielleicht.


Gruß, Stefan

[Jörg W. (dl8dtl) (Moderator)]

Stefan Kleinwort wrote:

> Wenn das selten gemacht wird, dann "besser" ggf. wenig Speicherbedarf
> haben, die Laufzeit ist nicht so wichtig.

Es ging ja darum, dass die mit der Hand entrollte und in Assembler
codierte Form dieses lustigen Algorithmus weder schneller noch
kürzer als die einfache Schleife ist, wenn man nur 8 bits hat.

> Im Extremfall lohnt es sich, eine Tabelle mit den gespiegelten Bitwerten
> anzulegen und darauf zugreifen:

Ja, das ist unbestritten die schnellste Variante.

[Rufus Τ. F. (rufus)]

PROGMEM uint8_t bit_revers_tab[256] = { 0x00, 0xF0, 0x40, 0x20, ...};

Spot-the-Error ... ich würde als zweites Byte 0x80 in die Tabelle 
eintragen, das gibt sonst witzige Effekte.

[Stefan K. (_sk_)]

oh sorry .. 0x80 war doch im Kopf, wie kommt denn da 0xF0 hin?

Gruß, Stefan

[Dieter Werner (Gast)]

@ Rufus
0x00, 0x80, 0x40, 0x20, ...};

Auch diese Reihenfolge überzeugt mich noch nicht so recht, machen wir 
doch mal ein Bit reversing zur Probe (alles in Hex):

00 -> 00    ganz klar
80 -> 01    auch gut
40 -> 02    passt
20 -> 04    ähhhh..

Da gehört vielleicht noch C0 zwischen 40 und 20.

[Marco G. (stan)]

Ein Kompromiss zwischen Codegröße und Geschwindigkeit wäre es, nur 16 
Nibbles abzulegen und aus der Tabelle zu holen.
So habe ich das bei meinen Bytes gemacht und es müsste auch für 16 und 
32 Bit Zahlen funktionieren.


PS: ich weiß dass der thread älter ist, aber es war der erste Treffer in 
meiner Suche und beinhaltet viele Lösungsvorschläge, da dachte ich 
sollte dieser nicht fehlen :)

[Daniel P. (polzi)]

Register Stunden "spiegeln". Ergebniss in temp speichern:

sbrs r16, 0
sbr r17, 0b10000000
sbrs 16, 1
sbr r17, 0b01000000
sbrs r16, 2
sbr r17, 0b00100000
sbrs r16, 3
sbr r17, 0b00010000
sbrs r16, 4
sbr r17, 0b00001000
sbrs r16, 5
sbr r17, 0b00000100
sbrs r16, 6
sbr r17, 0b00000010
sbrs r16, 7
sbr r17, 0b00000001

fertig... läuft... ganz ohne tabellen

[Jörg W. (dl8dtl) (Moderator)]

Daniel Polz wrote:
> Register Stunden "spiegeln".

Stunden?  Nein, Jahre.  Später als die letzte vorhandene Antwort...

> fertig... läuft... ganz ohne tabellen

Aber halt auch mit 17 Takten.  Ein Tabellenzugriff in eine ROM-
Tabelle geht schneller.

[Michael G. (linuxgeek)]

Jörg Wunsch wrote:

> Aber halt auch mit 17 Takten.  Ein Tabellenzugriff in eine ROM-
> Tabelle geht schneller.

Wirklich? Ist der Flash tatsaechlich so schnell? Eine Lookup-Tabelle 
muss ja auch nur 254 Bytes gross sein, wenn man die Operation haeufig 
braucht koennte es sich auch lohnen, sie im SRAM zu halten.

[Falk B. (falk)]

@ Michael G. (linuxgeek) Benutzerseite

>Wirklich? Ist der Flash tatsaechlich so schnell?

RTFM. Der AVR braucht für einen Flashzugriff 3 Takte, für den SRAM 2.

>braucht koennte es sich auch lohnen, sie im SRAM zu halten.

Geringfügig.

MFG
Falk

[dö (Gast)]

Peter Dannegger schrieb:

>       Versuch mal das hier:
> unsigned char mirror( unsigned char a )
> {
>   a = ((a >> 4) & 0x0F) | ((a << 4) & 0xF0);
>   a = ((a >> 2) & 0x33) | ((a << 2) & 0xCC);
>   a = ((a >> 1) & 0x55) | ((a << 1) & 0xAA);
>
>   return a;
> }
>
>
> Peter


gehe ich richtig der annahme, dass wenn ich das ganze für 16 bit machen 
will, ich nur noch eine zeile mit 8 einfügen muss und die Vergleiche 
entsprechend ergänzen??

quasi so dann:

 unsigned char mirror( unsigned char a )
 {
   a = ((a >> 8) & 0x00FF) | ((a << 8) & 0xFF00);
   a = ((a >> 4) & 0x0F0F) | ((a << 4) & 0xF0F0);
   a = ((a >> 2) & 0x3333) | ((a << 2) & 0xCCCC);
   a = ((a >> 1) & 0x5555) | ((a << 1) & 0xAAAA);

   return a;
 }

gruß dö

[Karl H. (kbuchegg)]

dö schrieb:
> Peter Dannegger schrieb:
>
>>       Versuch mal das hier:
>> unsigned char mirror( unsigned char a )
>> {
>>   a = ((a >> 4) & 0x0F) | ((a << 4) & 0xF0);
>>   a = ((a >> 2) & 0x33) | ((a << 2) & 0xCC);
>>   a = ((a >> 1) & 0x55) | ((a << 1) & 0xAA);
>>
>>   return a;
>> }
>>
>>
>> Peter
>
>
> gehe ich richtig der annahme, dass wenn ich das ganze für 16 bit machen
> will, ich nur noch eine zeile mit 8 einfügen muss und die Vergleiche
> entsprechend ergänzen??

Warum probierst du es nicht einfach aus?


Würde ich so machen:

uint16_t mirror16( uint16_t a )
{
  return mirror( a >> 8 ) | ( mirror( a ) << 8 );
}