Bits aus einem unsigned char array extrahieren

[Neb N. (bluemorph)]

Hallo Leute,

ich habe eine Funktion geschrieben, der ich ein unsigned char feld, ein 
Startbit, eine Länge und ein Zielpointer übergebe. Diese Funktion soll 
nun aus dem unsigned char Feld, ab dem Startbit für die übergebene 
Länge, alle Bits an die Adresse des Zielpointers kopieren.

Der Funktionsheader sieht wie folgt aus:

void f_extract_data (t_uchar *W_sourcefield, t_uint W_start_bit, t_uint W_len, t_uchar *W_destination);

Folgende Fälle habe ich schon abgedeckt:
1.) W_len <= 8 und die Bits sind in einem Byte in W_sourcefield
2.) W_len <= 8 und die Bits sind über zwei Bytes in W_sourcefield 
verteilt
3.) W_len > 8 und die Bits sind über zwei Bytes in W_sourcefield 
verteilt

Nun fehlt mir also noch der vierte Fall! Wenn W_len nun Länger als 8 ist 
und die Bits die ich auslesen möchte zum Beispiel über 3 Bytes verteilt 
sind.

Dazu folgendes Beispiel:

Byte:         1           2           3           4
Bit:      0000 1 010 | 1010 0000 | 1 111 0001 | 0000 0000

W_start_bit = 6,
W_len       = 12

In dem Fett markierten Bereich steckt nun also meine Information. Diese 
möchte ich nun an meinen Zielpointer W_destination schreiben, wobei 
W_destination immer die Adresse des niederwertigsten Bytes enthält.

Der Inhalt von W_destination sollte dann so aussehen:

W_destination[0] = 0100 0001
W_destination[1] = 0000 0101

Ich komme mit meinen Überlegungen einfach nicht so recht weiter. Hat 
jemand eine Idee von euch, wie man das realisieren kann?

MfG BlueMorph

[Falk B. (falk)]

@Benny Nestler (bluemorph)

>Ich komme mit meinen Überlegungen einfach nicht so recht weiter. Hat
>jemand eine Idee von euch, wie man das realisieren kann?

Ja. Man muss eigentlich keine deiner Fallunterscheidungen machen, das 
geht auch mit einem allgemeinen Ablauf, IMO sogar besser.

void f_extract_data (t_uchar *W_sourcefield, t_uint W_start_bit, t_uint W_len, t_uchar *W_destination) {
    uint8_t mask_in;
    uint8_t mask_out=1;
    uint8_t cnt_in;
    uint8_t data_out=0;
    uint8_t data_in;

    W_sourcefield+= W_start_bit / 8;
    data_in = *W_sourcefield;
    mask_in = 1<<(W_start_bit % 8);
    cnt_in  = 8-(W_start_bit  % 8);

    for (; W_len > 0; W_Len--) {
        if (data_in & mask_in) data_out |= mask_out;
        mask_in <<= 1;
        mask_out <<= 1;
        cnt_in--;
        if (cnt_in==0) {
            cnt_in=8;
            mask_in = 1;
            W_sourcefield--;
            data_in = *W_sourcefield;
        }
        if (mask_out==0) {
            mask_out = 1;
            *W_destination = data_out;
            W_destination++;
            data_out=0;
        }
    }    
}

MfG
Falk

[Neb N. (bluemorph)]

Hallo Falk,

danke für deine schnelle Antwort!
Leider habe ich bedenken, dass deine Funktion, so wie sie ist 
funktioniert.

Folgendes Beispiel:

Byte:               0              1
W_sourcefield = 0000 0011 | 0101 0011

W_start_bit = 4 und W_len = 4.

void f_extract_data (t_uchar *W_sourcefield, t_uint W_start_bit, t_uint W_len, t_uchar *W_destination) {
    uint8_t mask_in;
    uint8_t mask_out=1;
    uint8_t cnt_in;
    uint8_t data_out=0;
    uint8_t data_in;

    W_sourcefield+= W_start_bit / 8; 
    data_in = *W_sourcefield;          // data_in = 0000 0011
    mask_in = 1<<(W_start_bit % 8);    // mask_in = 0010 0000
    cnt_in  = 8-(W_start_bit  % 8);    // cnt_in  = 4

    for (; W_len > 0; W_Len--) {       //W_len = 4
        if (data_in & mask_in)         // 0000 0011 & 0010 0000 = 0
             data_out |= mask_out;     // wird also nichts gemacht
        mask_in <<= 1;                 // mask_in  = 0100 0000
        mask_out <<= 1;                // mask_out = 0000 0010
        cnt_in--;                      // cnt_in   = 3
        if (cnt_in==0) {
            cnt_in=8;
            mask_in = 1;
            W_sourcefield--;
            data_in = *W_sourcefield;
        }
        if (mask_out==0) {
            mask_out = 1;
            *W_destination = data_out;
            W_destination++;
            data_out=0;
        }
    }    
}

Ich hab jetzt nur den ersten for - Schleifendurchlauf gemacht!
Warum setzt du die mask_in mit

 1 << (W_start_bit % 8 )

auf?

MfG BlueMorph

[Falk B. (falk)]

@Benny Nestler (bluemorph)

>Leider habe ich bedenken, dass deine Funktion, so wie sie ist
>funktioniert.

Kann schon sein, ist NICHT getestet, sollte im Wesentlichen nur das 
Prinzip darstellen.

OK, hier die debuggte Version, auch wenn das pädagogisch unklug ist.

#include <stdint.h>

// global

    uint8_t source[3] = {0b00010101, 0b00110011, 0b10101010};
    uint8_t target[3];

void f_extract_data (uint8_t *W_sourcefield, uint8_t W_start_bit, uint8_t W_len, uint8_t *W_destination) {
    uint8_t mask_in;
    uint8_t mask_out=1;
    uint8_t cnt_in;
    uint8_t data_out=0;
    uint8_t data_in;

    W_sourcefield+= (W_start_bit+W_len-1) / 8;
    data_in = *W_sourcefield;
    mask_in = 1<<(7-((W_start_bit+W_len-1) % 8));
    cnt_in  = 1 + ((W_start_bit+W_len-1)  % 8);

    for (; W_len > 0; W_len--) {
        if (data_in & mask_in) data_out |= mask_out;
        mask_in <<= 1;
        mask_out <<= 1;
        cnt_in--;
        if (cnt_in==0) {
            cnt_in=8;
            mask_in = 1;
            W_sourcefield--;
            data_in = *W_sourcefield;
        }
        if (mask_out==0) {
            mask_out = 1;
            *W_destination = data_out;
            W_destination++;
            data_out=0;
        }
    }
    if (mask_out != 1) *W_destination = data_out;
}

int main(void) {

    f_extract_data (source, 3, 9, target); 
    return 0;
};

>Warum setzt du die mask_in mit

> 1 << (W_start_bit % 8 )

>auf?

Weil damit die Postion des ersten, niederwertigsten Bits markiert wird.

MFG
Falk

[Neb N. (bluemorph)]

Okay, du hast natürlich recht, der pädagogische Effekt ist jetzt weg. 
Aber sag mal, wie bist du denn vorgegangen, um die Formeln für mask_in 
und cnt_in zu erstellen?

Ich glaube das Prinzip ist mir soweit klar. Mit cnt_in zählst du die 
übrigen, noch nicht geschriebenen Bits im aktuellen W_sourcefield - 
Byte. Ist das richtig? Wenn dann alle Bits geschrieben sind, 
dekrementierst du den Zeiger und er zeigt auf das vorhergende Byte des 
W_sourcefields. Diesmal kann die mask_in bei 1 beginnen, da ja das 
niederwertigste Bit auch das LSB des aktuellen Bytes ist.
Wenn mask_out soweit fortgeschritten ist, dass die 1 aus dem unsigned 
char herausgeschoben wird und damit mask_out wieder 0 ist, muss an das 
nächste W_destination Byte geschrieben werden.
Übergeordnet wird bei jedem Schleifendurchlauf W_len dekrementiert, so 
dass die Schleife entsprechend abgebrochen wird, wenn das Ende der zu 
extrahierende Information erreicht ist. usw.

Vielen Dank dir schonmal!

[Falk B. (falk)]

@  Benny Nestler (bluemorph)

Deine Erkläsrung stimmt. Jetzt wo ich das alles nochmal sehe, kann man 
cnt_in auch weglassen und die Abfrage wie bei mask_out machen. Macht es 
einen Tick schneller.

MFG
Falk

[Neb N. (bluemorph)]

Meinst du das so:

void f_extract_data (t_uchar *W_sourcefield, t_uint W_start_bit, t_uint W_len, t_uchar *W_destination) {
    t_uchar V_mask_in;
    t_uchar V_mask_out = 1;
    t_uchar V_data_out = 0;
    t_uchar V_data_in;

    W_sourcefield += (W_start_bit + W_len - 1) / 8;        //Setze Zeiger auf das Byte wo das LSB drin steht steht
    V_data_in = *W_sourcefield;                  //Kopiere das Byte in eine temp Variable
    V_mask_in = 1 << (7 - ((W_start_bit + W_len - 1) % 8));    //Maskiere das LSB des niederwertigsten Bytes

    for (; W_len > 0; W_len--) {
        if (V_data_in & V_mask_in) V_data_out |= V_mask_out;
        V_mask_in <<= 1;
        V_mask_out <<= 1;
        if (V_mask_in == 0) {                  //aktuelles Byte hat keine Bits mehr die geschrieben werden müssen
            V_mask_in = 1;                    //Maskiere das LSB des nächsten Bytes, diesmal ist es auch das tatsächliche LSB
            W_sourcefield--;                  //dekrementiere den W_Sourcefield - Pointer
            V_data_in = *W_sourcefield;              //Kopiere das neue Byte in die temp - Variable
        }
        if (V_mask_out == 0) {                  //Die temporäre Variable V_data_out ist voll mit Bits
            V_mask_out = 1;                    //Setzte die Ausgangsmaske wieder an den Anfang
            *W_destination = V_data_out;            //Kopiere V_data_out an den destination Pointer  
            W_destination++;                  //Inkrementiere den Destination - Pointer
            V_data_out = 0;                    //V_data muss nun wieder mit 0 anfangen
        }
    }
    if (V_mask_out != 1) *W_destination = V_data_out;      //Für den Fall, dass nur wenige Bits in einem Byte geschrieben werden, muss V_data_out noch an die W_destination Speicherstelle geschrieben werden
}

Verrätst du mir noch, wie du auf die Formeln für die Maske gekommen 
bist???
War das so eine Überlegung ... von wegen "Ich kenne das Ziel" und "ich 
probiere jetzt aus, wie ich rechnen muss, damit ich mein Ziel erreiche"?

Das Ziel war ja im niederwertigsten Byte das LSB zu markieren. Das war 
auch mein Ziel, allerdings bin ich ganz anders herangegangen und habe 
versucht verschiedene Fälle, die auftreten können zu unterscheiden ... 
bis ich mich verrannt habe und nicht mehr weiter wusst ;-) .

Du wirst lachen, aber ich kann dir ja mal meine Funktion zeigen, die ich 
angefangen habe zu schreiben:

void f_extract_data (t_uchar *W_sourcefield, t_uint W_start_bit, t_uint W_len, t_uchar *W_destination){
  
  t_uchar V_index = 0;
  t_uint V_start_byte = 0, V_end_byte = 0;
  t_ulong V_mask = 0;
  
  V_start_byte   = W_start_bit / 8;
  V_end_byte    = ((W_start_bit + (W_len - 1)) / 8);
    
  if (W_len <= 8){
    for (V_index = 0; V_index < W_len; V_index++){
      V_mask |= (1 << V_index);
    }
    if (V_start_byte == V_end_byte){
      // The data to extract is stored only in one byte
      
      *W_destination = (W_sourcefield[V_start_byte] >> (8 - (W_len + (W_start_bit - V_start_byte * 8))) ) & V_mask;
      return;
    }
    // The data to extract is stored about two byte
    else{
      t_uchar V_bits_in_start_byte = 8 - (W_start_bit % 8);
      t_uchar V_bits_in_end_byte    = W_len - V_bits_in_start_byte;
      
      *W_destination = (W_sourcefield[V_end_byte] >> (8 - V_bits_in_end_byte));
      *W_destination |= (W_sourcefield[V_start_byte] << (V_bits_in_end_byte)) & V_mask;
    }    
  }
  else{
    // The data is bigger than 8 bits 
    t_uchar V_bits_in_start_byte = 8 - (W_start_bit % 8);
    t_uchar V_bits_in_following_bytes    = W_len - V_bits_in_start_byte;
    
    
    if (V_bits_in_following_bytes <= 8){
      *W_destination = W_sourcefield[V_end_byte] >> (8 - V_bits_in_following_bytes);
      *W_destination |= W_sourcefield[V_start_byte] << (V_bits_in_following_bytes);
      
      for (V_index = 0; V_index < (W_len - 8); V_index++){
        V_mask |= (1 << V_index);
      }

      *(W_destination + 1) = (W_sourcefield[V_start_byte] >> (8 - V_bits_in_following_bytes)) & V_mask;
    }
  }
}

MfG BlueMorph

[Falk B. (falk)]

@  Benny Nestler (bluemorph)

>Meinst du das so:

Ja. Noch ein Tip. Verwende die standardisierten Datentypen aus stdint 
und nichts selbstgestricktes. Macht die u.a. Sache leichter lesbar. UN 
Zeilenlänge auf 80...100 Zeichen begrenzen.

>Verrätst du mir noch, wie du auf die Formeln für die Maske gekommen
>bist???

Brain 2.0 ;-)

>War das so eine Überlegung ... von wegen "Ich kenne das Ziel" und "ich
>probiere jetzt aus, wie ich rechnen muss, damit ich mein Ziel erreiche"?

Eigentlich ist es nichts weiter als Bitmanipulation plus ein paar 
Schleifen.

Erste Idee. Ich maskiere die Bits im Quell- und Zielbereich mit einer 
Maske.
Zweite Idee. Ich berechne aus den Parametern eben diese Masken sowie die 
Offsets im Array.
Drittens. Die Daten werden rückwärts gelesen.

Der Rest ergibt sich daraus. Der "Trick" mit Division und Modulo setze 
ich mal als bekannt vorraus, siehe Festkommaarithmetik.

>Du wirst lachen, aber ich kann dir ja mal meine Funktion zeigen, die ich
>angefangen habe zu schreiben:

Naja, dein Ansatz ist erstmal OK, wenn gleich du dich verrannt hast. 
Bitmaske erzeugen, Bits maskieren und schieben, eben halt 
Bitmanipulation.

MfG
Falk

[Neb N. (bluemorph)]

Dann danke ich dir erstmal für deine Unterstützung Falk!

Schönen Abend noch!

MfG BlueMorph

[name (Gast)]

12