Bit Array in C

[Peter Z. (Gast)]

Hallo,
ich bin über ein kleines C Problemchen gestolpert, das es da keine 
Bit-Arrays gibt.

Ich würde aber gerne ein Bit Array haben, mit sagen wir mal 4096 
Plätzen.
Dort soll gespeichert werden, ob der externe 12-Bit-AD-Wandler schon 
diesen Code einmal ausgegeben hat.
Klar, im könnte

unsigned char AD_check[4096];

machen, aber soviel Speicherplatz hat mein µC nicht...

Gibt es ein Workaround, oder muß ich es mit Hardcore-Bitnapperei machen?

[Karl H. (kbuchegg)]

Peter Zz schrieb:

> Gibt es ein Workaround, oder muß ich es mit Hardcore-Bitnapperei machen?


Na ja. So schwer ist es dann auch wieder nicht, die Bits in 8 Bit 
Häppchen anzuordnen und aus der gewünschten Bitnummer die Adresse eines 
8 Bit Happens und die Nummer dieses Bits in diesem Happen zu errechnen.

In einer Strasse stehen 10 Häuser (durchnummeriert).
In derselben Strasse wohnen 40 Menschen (ebenfalls durchnummeriert), 
wobei jeweils 4 Menschen in einem Haus wohnen.

In welchem Haus (Nummer?) wohnt daher Bewohner 25 und wenn dort alle 
aufgefädelt auf der Couch sitzen ... die wievielte Person auf der Couch 
ist das dann?
Und der drückst du dann ein Bier in die Hand oder befragst sie, ob sie 
schon ein Bier hatte.

[Kan a. (Firma: Basta) (kanasta)]

Karl Heinz Buchegger schrieb:
> In welchem Haus (Nummer?) wohnt daher Bewohner 25 und wenn dort alle
> aufgefädelt auf der Couch sitzen ... die wievielte Person auf der Couch
> ist das dann?

Mann Karl, ich glaube du sitzt auch schon etwas länger. Auf der Couch.

[Rene H. (Gast)]

   unsigned char  AD_CHECK[512];                   // 512*8 = 4096Bit

   uint16_t       idx = pos >> 3;                  // position = Bit Nummer 0...
   unsigned char  mask = 1 << (pos - (idx<<3));

   if (AD_CHECK[idx] & mask) .....                 // wenn bit@pos true ist .....

Grüsse,
René

[Dosmo (Gast)]

Peter Zz schrieb:
> Gibt es ein Workaround, oder muß ich es mit Hardcore-Bitnapperei machen?

Es gibt bestimmte Microcontroller, die bitadressierbare RAM-Bereiche 
haben. Vielleicht hat Deiner ja sowas?!

[Sauger (Gast)]

Mahlzeit,

wie Rene H. vorgeschlagen hat, hier als Makros:

// Bits in einer Bitspur setzen/rücksetzen/testen
#define SETBIT(ByteArr,Bit) ((ByteArr)[Bit/8] |=  (1<<(Bit%8)))
#define CLRBIT(ByteArr,Bit) ((ByteArr)[Bit/8] &= ~(1<<(Bit%8)))
#define TSTBIT(ByteAry,Bit) ((ByteAry)[Bit/8] &   (1<<(Bit%8)))

MfG

[Peter Z. (Gast)]

Sauger schrieb:
> #define SETBIT(ByteArr,Bit) ((ByteArr)[Bit/8] |=  (1<<(Bit%8)))

Thx.

Würden Compiler das in jedem Fall immer effizient umsetzen, oder ist es 
nicht besser es so zu schreiben?

#define SETBIT(ByteArr,Bit) ((ByteArr)[Bit >> 3] |=  (1<<(Bit & 0x07)))

[Karl H. (kbuchegg)]

Peter Zz schrieb:
> Sauger schrieb:
>> #define SETBIT(ByteArr,Bit) ((ByteArr)[Bit/8] |=  (1<<(Bit%8)))
>
> Thx.
>
> Würden Compiler das in jedem Fall immer effizient umsetzen,

Solange du die Bitnummer als unsigned definierst, machen das Compiler 
seit ungefähr 35 Jahren standardmässig und ohne große Probleme :-)

Wenn du dir Sorgen um die Effizient machst, dann solltest du dir lieber 
Sorgen um den variablen Shift machen. Denn wenn die CPU den nicht 
unterstützt (und die AVR tun das nicht), dann wird das eine teure 
Operation. Da ist eine Array mit Bitmasken, welches von der Bitnummer 
indiziert wird, schon besser.

[JuH (Gast)]

Vielleicht ein weiterer Kandidat zum Vergleichen,
der gleiche Laufzeiten für alle Bitpositionen haben sollte
(ist natürlich nur für Prozessoren relevant, die keinen multibit-shift 
haben) :

 #define SETBIT(ByteArr,Bit) ((ByteArr)[(Bit) >> 3] |=  "\0x01\0x02\0x04\0x08\0x10\0x20\0x40\0x80"[(Bit) & 0x07])

... fast zu spät ...

[Peter Z. (Gast)]

JuH schrieb:
> "\0x01\0x02\0x04\0x08\0x10\0x20\0x40\0x80"[(Bit) & 0x07])

Oh, das ist eine interressante Notation um kleine Tabellen zu 
adressieren

  My_output = "Hallo Welt"[my_pointer++];

Landet diese kleine Tabelle bzw. der String eigentlich im Progmem oder 
Datamemory?

[Johann L. (gjlayde)]

Wie alle Daten, die nicht besonders (auf nicht Standard-konforme Weise) 
markiert sind, liegt auch dieser String im RAM.

[Anton G. (anton_g)]

wird der code nich  schneller wenn man die Makros folgender massen 
verbessert:

Da zb beim MSP430 empfohle wird / und % zu umgehn.

#define SETBIT(ByteArr,Bit) ((ByteArr)[Bit>>3] |=  (1<<(Bit&0x07)))
#define CLRBIT(ByteArr,Bit) ((ByteArr)[Bit>>3] &= ~(1<<(Bit&0x07)))
#define TSTBIT(ByteAry,Bit) ((ByteAry)[Bit>>3] &   (1<<(Bit&0x07)))

[Karl H. (kbuchegg)]

Anton G. schrieb:
> wird der code nich  schneller wenn man die Makros folgender massen
> verbessert:

Nochmal.
Compilerbauer sind keine Trottel! Die kennen diese Spielchen alle. Und 
noch ein paar mehr, von denen DU noch nie gehört hast.

Dreh die Optimierung deines Compilers auf und wenn es möglich ist, eine 
Division durch etwas Besseres zu ersetzen, dann macht das der Compiler. 
So etwas ist eine (triviale) Standardoptimierung seit über 45 Jahren. 
Wenn er es nicht tut, dann wirf das Klumpert von Compiler auf den Müll 
und nimm einen besseren Compiler.

Viel wichtiger ist, dass du die richtigen Datentypen nimmst! Division 
durch Schieben zu ersetzen, geht nur bei unsigned Typen. Bei signed 
Datentypen unterscheidet sich das Ergebnis von Dividieren und Schieben 
bei negativen Zahlen. Daher darf der Compiler hier keine Ersetzung 
vornehmen. Wenn du aber sowieso nur positive Zahlen hast, dann hätte man 
von vorne herein bereits einen unsigned Datentyp verwenden sollen und 
dann kann der Compiler das dann im Falle von 2-er Potenzen auch wieder 
durch Schieben ersetzen.


Du schreibst die Anweisungen so, wie sie im Zusammenhang am logischten 
sind. Wenn die Aufgabenstellung dergestalt ist, dass eine Division 
gefordert ist, dann schreib auch Division. Wenn die Aufgabenstellung 
sich im Rahmen von Bitpfriemelei abspielt, dann nimm Schieben. Hier 
haben wir es mit einer Auftailung in Gruppen zu tun, wofür Division die 
logische sinnvolle Operation ist. Den Rest überlass dem Compiler. Das 
ist nichts worüber man sich als Anwendungsprogrammierer den Kopf 
zerbrechen muss.

[Peter Z. (Gast)]

Karl Heinz Buchegger schrieb:
> Viel wichtiger ist, dass du die richtigen Datentypen nimmst! Division
> durch Schieben zu ersetzen, geht nur bei unsigned Typen.

Will nicht klugscheissern, aber es geht auch bei signed, hab es eben 
ausprobiert.

Manche µP's und µC's haben dafür im Instruction Set zwei 
unterschiedliche Schiebeoperationen:
ASR = Arithmetic Shift Right und
LSR = Logical    Shift Right

Der Unterschied ist,
beim Logischen Schieben     nach rechts wird Bit7 durch eine "0" 
ersetzt.
Beim Aritmetischen Schieben nach rechts wird Bit7 durch eine Kopie des 
Vorzeichen-Bits = Bit7 ersetzt.

[Andreas B. (andreas_b77)]

Peter Zz schrieb:
> Manche µP's und µC's haben dafür im Instruction Set zwei
> unterschiedliche Schiebeoperationen:
> ASR = Arithmetic Shift Right und
> LSR = Logical    Shift Right

Das alleine reicht aber nicht. Etwas mehr Aufwand bleibt trotzdem.

#include <stdint.h>

int8_t div(int8_t x)
{
  return x/4;
}

uint8_t udiv(uint8_t x)
{
  return x/4;
}

Mit gcc Optimierung -Os übersetzt gibt es das:

00000000 <div>:
   0:  87 fd         sbrc  r24, 7
   2:  8d 5f         subi  r24, 0xFD  ; 253
   4:  85 95         asr  r24
   6:  85 95         asr  r24
   8:  08 95         ret

0000000a <udiv>:
   a:  86 95         lsr  r24
   c:  86 95         lsr  r24
   e:  08 95         ret

[Marcus H. (mharnisch)]

Peter Zz schrieb:
> Will nicht klugscheissern, aber es geht auch bei signed, hab es eben
> ausprobiert.
>
> Beim Aritmetischen Schieben nach rechts wird Bit7 durch eine Kopie des
> Vorzeichen-Bits = Bit7 ersetzt.

Das rundet aber in die falsche Richtung.

MOV r0, #-1
ASR r0, r0, #1 ; -1/2 sollte 0 ergeben
BNE Error      ; Hoppla!

--
Marcus

[Johann L. (gjlayde)]

Marcus Harnisch schrieb:
> Peter Zz schrieb:
>>
>> Beim Aritmetischen Schieben nach rechts wird Bit7 durch eine Kopie des
>> Vorzeichen-Bits = Bit7 ersetzt.
>
> Das rundet aber in die falsche Richtung.

Nein tut es nicht. Denn ein arithmetischer Shift ist eben keine 
Ganzzahl-Division. Steht ober schon geschrieben das.

[Marcus H. (mharnisch)]

Johann L. schrieb:
> Denn ein arithmetischer Shift ist eben keine Ganzzahl-Division.

Genau das war doch die Aussage meines Posts. "Rundet falsch" aus der 
Sichtweise einer Division.

> Steht ober schon geschrieben das.

Richtig, aber Peter Zz bestand darauf, dass das auch bei signed 
funktionieren würde.

--
Marcus

[Peter Z. (Gast)]

Marcus Harnisch schrieb:
> Richtig, aber Peter Zz bestand darauf, dass das auch bei signed
> funktionieren würde.

Mit dem runden hast du absolut recht.
Ich kannte vorher das Problem mit dem runden nicht.
Wieder was dazu gelernt!   :-)