bitorder swap

[AndLi]

Hade vi inte ett programeringsdel förr?

Men i vilket fall, sitter och optimerar lite kod... Om man inte får använda en lookup table, går det att göra en bitswap mer effektivt?

Kod: Markera allt

unsigned char swap(unsigned char bin)
{
  unsigned char bout=0;
  unsigned char i;
  bout += (bin & 0x01);
  for(i=0;i<7;i++)
  {
    bout <<=  1;
    bin  >>=  1;
    bout += (bin & 0x01);
  }
  return bout;
}

[Kraco]

Mer optimerat än så behöver du nog inte bry dig om att göra, det där tar inte många instruktioner

[Micke_s]

AndLi: Får du göra en lookup på 16 byte?

Kod: Markera allt

const char swapbitstable[] = { 0b0000, 
									0b1000, 
									0b0100, 
									0b1100, 
									0b0010, 
									0b1010,
									0b0110,
									0b1110,
									0b0001,
									0b1001,
									0b0101,
									0b1101,
									0b0011,
									0b1011,
									0b0111,
									0b1111
									};

//swap B7 - B0, B5 - B1 and so on
uint8_t swapbits8t(uint8_t s)
{
	return ((swapbitstable[s & 0x0F]<<4) | (swapbitstable[s >> 4]));
}

uint16_t swapbits16t(uint16_t s){
	return ((swapbits8t(s & 0x00FF)<<8) | (swapbits8t(s >> 8)));
}

[AndLi]

Får och får, det var mest en hypotetisk fråga .

Om det gick att få det än lite effektivare, behövs inte i praktiken.

Används i ett program för att ladda en FPGA med kod, tar nu ca 0.47s för 212392 bytes...
(varav ca 0.25 är själva utklockningen via spi till fpgan, resten är filinläsning och konvertering)

Och den ska inte ens boota ofta (helst bara en gång...)

[Icecap]

Kod: Markera allt

typedef unsigned char byte;
byte Swap(byte Bin)
  {
  const byte Swap_Data[] =
    {0x00,0x08,0x04,0x0C,0x02,0x0A,0x06,0x0E,
     0x01,0x09,0x05,0x0D,0x03,0x0B,0x07,0x0F};
  byte BOout;
  BOut  = Swap_Data[Bin & 0x0F]  < 4;
  Bin >= 4;
  BOut |= Swap_Data[Bin & 0x0F];
  return(BOut);
  }

Visst, uppslagstabell men ganska liten.

Om det inte får vara med tabell alls är det snabbaste sättet faktisk att göra såhär:

Kod: Markera allt

typedef unsigned char byte;
byte Swap(byte BIn)
  {
  union
    {
    struct
      {
      byte B_0 : 1;
      byte B_1 : 1;
      byte B_2 : 1;
      byte B_3 : 1;
      byte B_4 : 1;
      byte B_5 : 1;
      byte B_6 : 1;
      byte B_7 : 1;
      } Bits;
    byte Byte;
    } BOut;
  BOut.Bits.B_0 = BIn & 0x80;
  BOut.Bits.B_1 = BIn & 0x40;
  BOut.Bits.B_2 = BIn & 0x20;
  BOut.Bits.B_3 = BIn & 0x10;
  BOut.Bits.B_4 = BIn & 0x08;
  BOut.Bits.B_5 = BIn & 0x04;
  BOut.Bits.B_6 = BIn & 0x02;
  BOut.Bits.B_7 = BIn & 0x01;
  return(BOut);
  }

Då sparar man overheaden på for-next delen fast å andra sidan kan kompilern peta in en hel del bit-grejer istället.

[Micke_s]

Min kod blir snabb om processorn har 4bit swap instruktion, vilket AVR har t.ex.

[SvenW]

Har roat mig med att göra en jämförelse på PC med gcc.
Som synes spelar det inte någon större roll vilken variant man använder, kompilatorns optimering tar hand om det hela.
Med en annan processor kan det säkert bli helt annorlunda, skulle jag tro.

Min egen kandidat kallad SvenW ser ut så här:

unsigned char
swap2 (unsigned char bin)
{
unsigned char bt1,bt2, bout;

bt1 = ( bin << 1) & 0xAA;
bt2 = ( bin >> 1) & 0x55;
bout = bt1 + bt2;

bt1 = (bout << 2) & 0xCC;
bt2 = (bout >> 2) & 0x33;
bout = bt1 + bt2;

bt1 = (bout << 4) & 0xF0;
bt2 = (bout >> 4) & 0x0F;
bout = bt1 + bt2;

return bout;
}



Resultat på Pentium P4/ gcc 4.1.2 (Ubuntu 4.1.2-0ubuntu4)
Antal cykler för respektive funktion
(Micke_s är lika med Icecap1, tror jag!)

AndLi SvenW Icecap1 Icecap2

gcc -O0 swap.c
404 184 140 264

gcc -O1 swap.c
248 84 84 84

gcc -O2 swap.c
200 84 84 84

gcc -O3 swap.c
108 88 84 88


Editering:

Mätningen ovan är grovkorning. Efter att ha tvivlat på att funktionen verkligen tar 84 cykler, har jag gjort om en del:

1. Deklarera inline.
2. Kör 100 iterationer med varierande parameter.

Resulatet blir nu för 100 iterationer

gcc -O0 swap.c
19436 10368 4800 14456

gcc -O1 swap.c
5420 1116 868 2048

gcc -O2 swap.c
3252 1020 844 1844

gcc -O3 swap.c
2036 1032 832 1840

Detta är lite rimligare, 20, 10, 8, 18 cykler per iteration. Tabellslagning är märkbart snabbare.
Reservation: Man vet aldrig vad kompilatorns optimering har för sig!

[AndLi]

svenW: Jag tror du kniper priset för klurigaste lösningen

Procesorn är en Atmel AT91RM9200...

[chille]

Nu vet jag inte hur RM9200 är, men vissa liknande processorer har ju "zero overhead loops", altså att du kan göra for-loopar och liknande direkt på core-nivå utan att få någon som helst overhead mer än det tar att sätta upp loopen, vilket brukar ta två cykler ungefär.

Har den det så kan det ju vara värt att fundera på ifall en for-loop inte är bättre. Blir ju åtminstånde några bytes mindre kod, däremot kanske man torskar en cykel på det.

EDIT: Angående programmeringsdelen på forumet, kan det inte vara så att du tänker på Mikroprocessor-delen? Där snackas det ju rätt mycket programmering...

[speakman]

Saknar också en renodlad programmeringsdel...

[chille]

Även jag har också saknat det. Kanske skulle fixa en sådan del. Den skulle kanske även kunna täcka upp Linux/Unix, olika scriptspråk med mera.

Ska föreslå det för moderatorern och se vad jag får för respons.

[Nisse]

Tycker det är för många forumdelar som det är redan nu.