Datum:
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.
Autor:
Rufus Τ. Firefly
(rufus)
(Moderator)
Datum:
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 ...
Datum:
ok danke ich dachte nur vielleicht könnte ich meine momentane lösung verschönern...
Datum:
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;
}
|
Autor:
Jörg Wunsch
(dl8dtl)
(Moderator)
Datum:
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.
Datum:
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
Autor:
Jörg Wunsch
(dl8dtl)
(Moderator)
Datum:
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.
Datum:
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 |
Datum:
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
Autor:
Jörg Wunsch
(dl8dtl)
(Moderator)
Datum:
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.
Datum:
Okydoky, der Loop ist dann offenbar tatsächlich die beste Lösung, wenn man nicht etwas in Assembler stricken möchte! MfG Peter
Autor:
Jörg Wunsch
(dl8dtl)
(Moderator)
Datum:
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.
Datum:
<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
Autor:
Jörg Wunsch
(dl8dtl)
(Moderator)
Datum:
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.
Autor:
Rufus Τ. Firefly
(rufus)
(Moderator)
Datum:
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.
Datum:
oh sorry .. 0x80 war doch im Kopf, wie kommt denn da 0xF0 hin? Gruß, Stefan
Datum:
@ 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.
Datum:
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 :)
Datum:
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
Autor:
Jörg Wunsch
(dl8dtl)
(Moderator)
Datum:
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.
Autor:
Michael G.
(linuxgeek)
Datum:
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.
Datum:
@ 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
Datum:
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ö
Datum:
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 );
}
|
E-Mail-Benachrichtigung einschalten
Neu: Seitenaufteilung einschalten