Forum: Compiler & IDEs reihenfolge der bits in einem byte umdrehen


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von kernel_panic (Gast)


Lesenswert?

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.

von Rufus Τ. F. (rufus) Benutzerseite


Lesenswert?

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

von kernel_panic (Gast)


Lesenswert?

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

von Peter (Gast)


Lesenswert?

Ich weiss nicht wie deine Momentane Lösung aussieht, aber so gehts schon 
recht elegant:
1
{
2
  Val = (Val&0xF0)>>4 | (Val&0x0F)<<4;
3
  Val = (Val&0xCC)>>2 | (Val&0x33)<<2;
4
  Val = (Val&0xAA)>>1 | (Val&0x55)<<1;
5
}

  

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


Lesenswert?

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.

von Peter (Gast)


Lesenswert?

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!
1
unsigned char Val;
2
Val= PORTC;
3
Val = (Val&0xF0)>>4 | (Val&0x0F)<<4;
4
Val = (Val&0xCC)>>2 | (Val&0x33)<<2;
5
Val = (Val&0xAA)>>1 | (Val&0x55)<<1;
6
PORTC=Val;

Wird zu:
1
Val= PORTC;
2
  IN      R18,0x15         In from I/O location
3
Val = (Val&0xF0)>>4 | (Val&0x0F)<<4;
4
  CLR     R19              Clear Register
5
Val = (Val&0xCC)>>2 | (Val&0x33)<<2;
6
  MOV     R24,R18          Copy register
7
  SWAP    R24              Swap nibbles
8
  ANDI    R24,0xF0         Logical AND with immediate
9
  LDI     R23,0x04         Load immediate
10
  LSR     R19              Logical shift right
11
  ROR     R18              Rotate right through carry
12
  DEC     R23              Decrement
13
  BRNE    PC-0x03          Branch if not equal
14
  OR      R24,R18          Logical OR
15
  CLR     R25              Clear Register
16
63:           Val = (Val&0xAA)>>1 | (Val&0x55)<<1;
17
  MOVW    R18,R24          Copy register pair
18
  ANDI    R18,0xCC         Logical AND with immediate
19
  ANDI    R19,0x00         Logical AND with immediate
20
  ASR     R19              Arithmetic shift right
21
  ROR     R18              Rotate right through carry
22
  ASR     R19              Arithmetic shift right
23
  ROR     R18              Rotate right through carry
24
  ANDI    R24,0x33         Logical AND with immediate
25
  ANDI    R25,0x00         Logical AND with immediate
26
  LSL     R24              Logical Shift Left
27
  ROL     R25              Rotate Left Through Carry
28
  LSL     R24              Logical Shift Left
29
  ROL     R25              Rotate Left Through Carry
30
  OR      R18,R24          Logical OR
31
  MOV     R24,R18          Copy register
32
  CLR     R25              Clear Register
33
  MOVW    R18,R24          Copy register pair
34
  ANDI    R18,0xAA         Logical AND with immediate
35
  ANDI    R19,0x00         Logical AND with immediate
36
  ASR     R19              Arithmetic shift right
37
  ROR     R18              Rotate right through carry
38
  ANDI    R24,0x55         Logical AND with immediate
39
  ANDI    R25,0x00         Logical AND with immediate
40
  LSL     R24              Logical Shift Left
41
  ROL     R25              Rotate Left Through Carry
42
  OR      R18,R24          Logical OR
43
PORTC=Val;
44
  OUT     0x15,R18         Out to I/O location

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

Peter

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


Lesenswert?

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.

von Peter (Gast)


Lesenswert?

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:
1
Val= PORTC;
2
  IN      R25,0x15         In from I/O location
3
Val = (u08)((Val & 0xF0)>>4) | (u08)((Val & 0x0F)<<4);
4
  SWAP    R25              Swap nibbles
5
Val = (u08)((Val & 0xCC)>>2) | (u08)((Val & 0x33)<<2);
6
  MOV     R25,R24          Copy register
7
  ANDI    R25,0xCC         Logical AND with immediate
8
  LSR     R25              Logical shift right
9
  LSR     R25              Logical shift right
10
  ANDI    R24,0x33         Logical AND with immediate
11
  LSL     R24              Logical Shift Left
12
  LSL     R24              Logical Shift Left
13
  OR      R25,R24          Logical OR
14
Val = (u08)((Val & 0xAA)>>1) | (u08)((Val & 0x55)<<1);
15
  MOV     R24,R25          Copy register
16
  ANDI    R24,0xAA         Logical AND with immediate
17
  LSR     R24              Logical shift right
18
  ANDI    R25,0x55         Logical AND with immediate
19
  LSL     R25              Logical Shift Left
20
  OR      R25,R24          Logical OR
21
PORTC=Val;
22
  OUT     0x15,R25         Out to I/O location



von Peter D. (peda)


Lesenswert?

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


Peter

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


Lesenswert?

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
1
        mov r25,r24
2
        swap r25
3
        andi r25,0xf0
4
        swap r24
5
        andi r24,0x0f
6
        or r24,r25
7
        mov r25,r24

nichts weiter als
1
        swap r25
2
        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.

von Peter (Gast)


Lesenswert?

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

MfG Peter

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


Lesenswert?

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.

von Stefan K. (_sk_)


Lesenswert?

<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:
1
PROGMEM uint8_t bit_revers_tab[256] = { 0x00, 0xF0, 0x40, 0x20, ...};
2
uint8_t my_revers_byte;
3
uint8_t my_byte;
4
5
  my_byte = 0x01;
6
  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

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


Lesenswert?

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.

von Rufus Τ. F. (rufus) Benutzerseite


Lesenswert?

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

von Stefan K. (_sk_)


Lesenswert?

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

Gruß, Stefan

von Dieter Werner (Gast)


Lesenswert?

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

von Marco G. (stan)


Lesenswert?

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

von Daniel P. (polzi)


Lesenswert?

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

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


Lesenswert?

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.

von Michael G. (linuxgeek) Benutzerseite


Lesenswert?

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.

von Falk B. (falk)


Lesenswert?

@ 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

von (Gast)


Lesenswert?

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ö

von Karl H. (kbuchegg)


Lesenswert?

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:
1
uint16_t mirror16( uint16_t a )
2
{
3
  return mirror( a >> 8 ) | ( mirror( a ) << 8 );
4
}

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.