C jedes zweite Bit verwerfen

[Werner (Gast)]

Hallo,

ich habe einen Bitstrom (uint_8 bindata[8]), von welchem jedes 2. Bit 
verworfen werden soll, weil es redundant ist (aber das Vorgängerbit 
invertiert). Im Moment sieht mein Code so aus:

uint8_t bindata[8];
uint8_t netdata[4];

for (i=0;i<64;i+=2)
  netdata[i / 16] |= ((bindata[i / 8] >> (i % 8 + 1)) & 0x01) << ((i / 2) % 8);

Problem ist im Moment dass das jeweils erste Nibble der Rohdaten im 
jeweils unteren Nibble der Ausgangsdaten landen, und es müsste doch 
überhaupt viel einfacher gehen? Das Ergebnis soll quasi so sein als ob 
ich die Daten über eine UART schicke, und jedes 2. Bit verloren ginge...

[holger (Gast)]

>Im Moment sieht mein Code so aus:
>
>  netdata[i / 16] |= ((bindata[i / 8] >> (i % 8 + 1)) & 0x01) << ((i / 2) >% 8);

Für solche Codezeilen sollte Teeren und Federn wieder eingeführt 
werden;)

[Joe F. (easylife)]

wie wäre es damit (zwar nicht kürzer, aber logischer):

uint8_t bindata[8];
uint8_t netdata[4];

uint8_t j;

for (i=0;i<4;i++)
{
  j = i*2;
  netdata[i]  =  bindata[j] & 0x01;
  netdata[i] |= (bindata[j] & 0x04) >> 1;
  netdata[i] |= (bindata[j] & 0x10) >> 2;
  netdata[i] |= (bindata[j] & 0x40) >> 3;

  j++;
  netdata[i] |= (bindata[j] & 0x01) << 4;
  netdata[i] |= (bindata[j] & 0x04) << 3;
  netdata[i] |= (bindata[j] & 0x10) << 2;
  netdata[i] |= (bindata[j] & 0x40) << 1;
}

[Falk B. (falk)]

@Werner (Gast)

>überhaupt viel einfacher gehen? Das Ergebnis soll quasi so sein als ob
>ich die Daten über eine UART schicke, und jedes 2. Bit verloren ginge...

Du willst ein Byte auf ein Nibble zusammenschieben. Das kann man 
entweder mit einer Tabelle mit 256 Einträgen (sehr schnell aber hoher 
Speicherbedarf) oder einer Berechnungsfunktion (langsam, geringer 
Speicherbedarf) erledigen, siehe Bitmanipulation. Auf dem avr gcc 
gibt es eine Spezialfunktion, die kann die Bits in einem Byte beliebig 
verwürfeln.

http://gcc.gnu.org/onlinedocs/gcc-4.7.1/gcc/AVR-Built_002din-Functions.html


Das hier ist Standard-C, das kann jeder Compiler.

uint8_t squeeze(uint8_t data) {
  uint8_t tmp=0;
  
  if (data & (1<<7)) tmp |= (1<<3);
  if (data & (1<<5)) tmp |= (1<<2);
  if (data & (1<<3)) tmp |= (1<<1);
  if (data & (1<<1)) tmp |= (1<<0);

  return tmp;  
}

uint8_t bindata[8];
uint8_t netdata[4];

for (i=0; i<4; i++) {
  netdata[i] = (squeeze(bindata[2*i]) << 4) | squeeze(bindata[2*i+1]);
}

[Joe F. (easylife)]

Falk B. schrieb:
(...)

Hehe, gleicher Ansatz, 2 Implementierungen.

Geht auch viel schneller als TOs Code (keine Divisionen, Modulos und 
Diesdas).

[Falk B. (falk)]

Die avr gcc Version wäre diese hier.

uint8_t tmp;

for (i=0; i<4; i++) {
  tmp = __builtin_avr_insert_bits(0x7531FFFF, bindata[2*i], 0);
  netdata[i] = __builtin_avr_insert_bits(0xFFFF7531, bindata[2*i+1], tmp);
}

[Frank B. (frank501)]

Falk B. schrieb:
> mit einer Tabelle mit 256 Einträgen

reichen da nicht 16 Einträge die mit dem zu prüfenden Byte verodert 
werden?

edit:

Nee, nur verodern reicht nicht.
Man müsste die relevanten Bits mit einer Maske aus Einsen und-verknüpfen 
und kann dann mit einer 16 Byte großen Tabelle vergleichen.

[Ralf D. (doeblitz)]

Frank B. schrieb:
> Falk B. schrieb:
>> mit einer Tabelle mit 256 Einträgen
>
> reichen da nicht 16 Einträge die mit dem zu prüfenden Byte verodert
> werden?

Du brauchst zwar nur 16 Einträge, die sind aber über die halbe Tabelle 
verteilt (sparse table), weshalb sie eben trotzdem mindestens 128 
Einträge groß ist (wenn man vorher die irrelevanten Bits wegmaskiert).

Wenn du anfängst irgendwie rumzurechnen, um mit einer kleinen Tabelle zu 
vergleichen, dann kannst du gleich vollständig rechnen, das macht vom 
Aufwand her auch kaum noch was aus.

[Carl D. (jcw2)]

Wenn's nur für AVR sein soll:
Inline ASM,
 8 x BLD/BLS,
 2 Byte rein, 1 Byte raus, macht 3 Register, in denen ICE Werte eh schon 
stehen.
 16 Takte, 16 Byte Flash
Und gut is,

[Werner (Gast)]

Danke für die schönen Lösungen!

Werner

[Klaus (Gast)]

Ralf D. schrieb:
> Du brauchst zwar nur 16 Einträge, die sind aber über die halbe Tabelle
> verteilt (sparse table), weshalb sie eben trotzdem mindestens 128
> Einträge groß ist (wenn man vorher die irrelevanten Bits wegmaskiert).

Na eigentlich 17.

Werner schrieb:
> von welchem jedes 2. Bit
> verworfen werden soll, weil es redundant ist (aber das Vorgängerbit
> invertiert)

Es gibt ja noch den Fall, daß das Bit nicht das invertierte Vorgängerbit 
ist. Der Code wäre dann fehlerhaft, Fall 17.

MfG Klaus

[Jupp (Gast)]

Werner schrieb:
> von welchem jedes 2. Bit
> verworfen werden soll, weil es redundant ist (aber das Vorgängerbit
> invertiert)

Warum prüfst du nicht auf Verfälschung, wenn du schon die Möglichkeit 
hast?

[Sebastian (Gast)]

Jupp schrieb:
> Warum prüfst du nicht auf Verfälschung, wenn du schon die Möglichkeit
> hast?

Tut er vielleicht, war aber zu trivial um danach zu fragen (um 1 
schieben, XOR)?


Hier ist noch eine Lösung für CPUs mit 64 bit Registern. Zugegeben, dort 
sind dann meistens auch die anderen Varianten schnell genug :-)

#include <stdio.h>
#include <assert.h>
#include <stdint.h>

// Falks Version zum Vergleich im Unittest:
uint8_t squeeze8(uint8_t data)
{
    uint8_t tmp=0;

    if (data & (1<<7)) tmp |= (1<<3);
    if (data & (1<<5)) tmp |= (1<<2);
    if (data & (1<<3)) tmp |= (1<<1);
    if (data & (1<<1)) tmp |= (1<<0);

    return tmp;  
}
// Erweitert auf 16 bit
uint8_t squeeze16(uint16_t data)
{
    return squeeze8(data) | (squeeze8(data>>8) << 4);
}


uint8_t squeeze(uint16_t data)
{    
    data &= 0b1010101010101010;
    // data = A B C D E F G H
    
    uint64_t tmp = data * 0x3000300030003;
    // 0x3000300030003 = 1<<0 | 1<<1 | 1<<16 | 1<<17 | 1<<32 | 1<<33 | 1<<48 | 1<<49
    // 7654321076543210765432107654321076543210765432107654321076543210
    //                                                 A B C D E F G H   0
    //                                                A B C D E F G H    1
    //                                 A B C D E F G H                  16
    //                                A B C D E F G H                   17
    //                 A B C D E F G H                                  32
    //                A B C D E F G H                                   33
    // A B C D E F G H                                                  48
    //  B C D E F G H                                                   49
    
    tmp &= 0xC0000C0000C0000C;
    // 0xC0000C0000C0000C = 3<<2 | 3<<22 | 3<<42 | 3<<62
    //                48              32              16
    // 7654321076543210765432107654321076543210765432107654321076543210
    // AB                  CD                  EF                  GH
    // 0                   18                  36                  54
    
    tmp *= 0x40001000040001;
    // 0x40001000040001 = 1<<0 | 1<<18 | 1<<36 | 1<<54
    
    return tmp >> 56;
}


int main(int argc, const char* argv[])
{
    // Stichprobe:
    //                 _ _ _ _ _ _ _ _ 
    assert(squeeze16(0b1001100101011001) == 0b10100010);
    assert(squeeze(0b1001100101011001) == 0b10100010);
    // Decke alles ab, mit Vergleichs-Funktion:
    for(uint32_t i = 0; i < 0x10000; ++i)
    {
        assert  (squeeze(i) == squeeze16(i));
    }
    printf("Done.\n");
    return 0;
}

[Werner (Gast)]

>Warum prüfst du nicht auf Verfälschung, wenn du schon die Möglichkeit
>hast?

Ja, mache ich, allerdings mit einer Schleife die ähnlich unleserlich 
aussieht wie die im Eröffnungspost...

Werner

[Daniel A. (daniel-a)]

ungetestet, prüffunktion:

bool isOk(uint8_t x){
  return !(x&(x>>1)&0x55);
}

[Sebastian (Gast)]

Daniel A. schrieb:
> ungetestet

und falsch. Gegenbeispiel: x=0.

Mein Vorschlag:

((x ^ (x>>1)) & 0x55) == 0x55

[Klaus (Gast)]

Werner schrieb:
>>Warum prüfst du nicht auf Verfälschung, wenn du schon die Möglichkeit
>>hast?
>
> Ja, mache ich, allerdings mit einer Schleife die ähnlich unleserlich
> aussieht wie die im Eröffnungspost...

Dann wäre doch eine Tabelle von 256 Werten, wie

Falk B. schrieb:
> Du willst ein Byte auf ein Nibble zusammenschieben. Das kann man
> entweder mit einer Tabelle mit 256 Einträgen (sehr schnell aber hoher
> Speicherbedarf)

das Richtige. Da geht man mit dem Originalbyte rein und bekommt 
Ergebniss oder Fehler heraus. Check und Umsetzung in einem Rutsch. Und 
256 Byte halte ich heutzutage nicht wirklich für einen "hohen" 
Speicherbedarf.

MfG Klaus

[chris_ (Gast)]

Man kann auch 2 Tabellen mit 16 Werten nehmen und vorher den 
Eingangswert in 2 Nibble teilen.

[Falk B. (falk)]

@  chris_ (Gast)

>Man kann auch 2 Tabellen mit 16 Werten nehmen und vorher den
>Eingangswert in 2 Nibble teilen.

Kann man, aber dann ist er Vorteil der hohen Geschwindigkeit einer 
Tabelle schon fast wieder weg. Selbst die Einfachversion mit bitweise 
Prüfung und Setzen ist nicht wirklich langsam.

[chris_ (Gast)]

>Kann man, aber dann ist er Vorteil der hohen Geschwindigkeit einer
>Tabelle schon fast wieder weg.

... fast ... vielleicht ... ist es auch ein Mittelding zwischen Tabelle 
und Bit-Algo. Man müsste es mal probieren ...

[Axel S. (a-za-z0-9)]

In Assembler ist das simpelst zu programmieren. Einfach das eine 
Register immer zweimal links schieben (oder rotieren). Und dann das 
Carry-Bit in das Zielregister hinein schieben (oder rotieren). 3 
Assemblerinstruktionen pro Bit. Und trivial ausrollbar.

[Carl D. (jcw2)]

> 3 Assemblerinstruktionen pro Bit. Und trivial ausrollbar.

BLD/BST sind nur 2 pro Bit.

[Falk B. (falk)]

@chris_ (Gast)

>>Kann man, aber dann ist er Vorteil der hohen Geschwindigkeit einer
>>Tabelle schon fast wieder weg.

>... fast ... vielleicht ... ist es auch ein Mittelding zwischen Tabelle
>und Bit-Algo. Man müsste es mal probieren ...

Siehe Anhang.

Wobei die Behandlung des Bit 7 SEHR merkwürding aussieht. Da hat sich 
der Optimierer selber ins Knie geschossen, auch wenn das Ergebnis stimmt 
;-)

uint8_t squeeze(uint8_t data) {
  uint8_t tmp=0;
  
  if (data & (1<<7)) tmp |= (1<<3);
  5e:  98 2f         mov  r25, r24
  60:  99 1f         adc  r25, r25
  62:  99 27         eor  r25, r25
  64:  99 1f         adc  r25, r25
  66:  99 0f         add  r25, r25
  68:  99 0f         add  r25, r25
  6a:  99 0f         add  r25, r25
  if (data & (1<<5)) tmp |= (1<<2);
  6c:  85 fd         sbrc  r24, 5
  6e:  94 60         ori  r25, 0x04  ; 4
  if (data & (1<<3)) tmp |= (1<<1);
  70:  83 fd         sbrc  r24, 3
  72:  92 60         ori  r25, 0x02  ; 2
  if (data & (1<<1)) tmp |= (1<<0);
  74:  81 fd         sbrc  r24, 1
  76:  91 60         ori  r25, 0x01  ; 1

  return tmp;  
}
  78:  89 2f         mov  r24, r25
  7a:  08 95         ret

>  if (data & (1<<7)) tmp |= (1<<3);
>  5e:  98 2f         mov  r25, r24
>  60:  99 1f         adc  r25, r25

*2, MSB wandert ins Carry-Bit

>  62:  99 27         eor  r25, r25

r25 =0

>  64:  99 1f         adc  r25, r25

Carry-Bit ins LSB "kopieren"

>  66:  99 0f         add  r25, r25
>  68:  99 0f         add  r25, r25
>  6a:  99 0f         add  r25, r25

3x *2 -> 3 mal links schieben

Das ist ein guter Kandidat für code obfuscation ;-)
Manchmal ist einfach auch besser. Bei den 3 anderen Bits geht es doch 
auch.

Macht 24 Takte für die normale Funktion incl. call/return. Die muss 2x 
aufgerufen werden. Macht in Summe 275 Takte für die Schleife mit 4 
Zielbytes.

Die 256er Tabelle klappert mit gerade mal 138 Takten durch.

Die 16er Tabelle braucht 293 Takte, sogar mehr als die Version mit der 
squeeze Funktion!