Bitmaske erzeugen

[John Doe (Gast)]

Hallo!


Angenommen ich möchte mit einer UND-Maske die n untersten bits 
maskieren. n ist aber variabel und nicht fest. Wie mache ich das 
effektiv?

Wege die mir einfallene

Weg 1)
Ich definiere mir die Masken als lookup table, also so

uint8_t masken[] = {0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
n = (...) //Aus irgendeiner Berechnung
auszumaskieren &= masken[n];

das wäre eigentlich doch recht schnell, aber bei größeren Wortbreiten 
geht das durch den lookup table irgendwie in den Speicher finde ich.


Weg 2)
Ausrechnen:

auszumaskieren &=  ( 2**n ) - 1;

Da habe ich nur keine Ahnung, wie lange die Berechnung 2**n eigenltich 
dauert. Und da man nun eigentlich immer so schnell wie es geht bits 
maskieren möchte verunsichert mich das.


Weg 3)

Was würdet ihr machen bzw. welche Tips mir geben?

[Karl H. (kbuchegg)]

John Doe schrieb:

> Weg 2)
> Ausrechnen:
>
> auszumaskieren &=  ( 2**n ) - 1;

Das kommt drauf an, ob die fragliche CPU einen Barrelshifter hat oder 
nicht.
Hat sie einen, dann ist das eine schnelle Operation.
Hat sie keinen, dann ist das eher langsam, weil der Compiler die 
Operation als Schleife implementieren muss.

> Weg 3)
>
> Was würdet ihr machen

Ich würds als Lookup-Tabelle machen.

[Klaus F. (kfalser)]

John Doe schrieb:
> das wäre eigentlich doch recht schnell, aber bei größeren Wortbreiten
> geht das durch den lookup table irgendwie in den Speicher finde ich.

Wieso?
Die Werte die n maximal annehmen kann sind je nach Prozessor 8, 16, 32, 
64 und vielleicht maximal 128 oder 256.
Das sind kleine Tabellen.

[Peter (Gast)]

Klaus Falser schrieb:
> Das sind kleine Tabellen.

auf einen Atmel mit 512byte ram, kann das schon zu viel sein.


aber eigentlich braucht man ja nur 8 werte in der Tabelle, denn die 
kleinere bits sind ja dann alle 1

[Thomas (Gast)]

mir gefällt die Methode mit dem Lookup Table und die Größe der Tables 
steigt eh nur linear mit der Bitbreite, also werden die auch nicht 
schnell groß.

Allerdings sollte auch:
auszumaskieren &=  ( 2**n ) - 1

sehr schnell gehen, wie schon oben erwähnt, wenn der Controller einen 
Barrel Shifter hat, denn daraus macht der Compiler dann:

auszumaskieren &=  (1<<n) - 1

Wär interessant was der Compiler daraus macht.

[Rolf Magnus (Gast)]

Peter schrieb:
> Klaus Falser schrieb:
>> Das sind kleine Tabellen.
>
> auf einen Atmel mit 512byte ram, kann das schon zu viel sein.
>
>
> aber eigentlich braucht man ja nur 8 werte in der Tabelle, denn die
> kleinere bits sind ja dann alle 1

Außerdem müssen die nicht im RAM stehen.

[sebastians (Gast)]

angenommen, du hast maximal 8 bit (ansonsten einfach die Konstanten 
anpassen):

0xFF >> (8-n)

Sind genau so viele shift- und subtraktions-Operationen wie

(1<<n) - 1

aber vieleicht kannst du ja schon von vornherein mit 8-n statt n 
rechnen. Vielleicht kannst du auch die negierung davon

~(0xFF << n)

wegoptimieren (weil du das Ergebnis sowieso negiert brauchst).

[JW (Gast)]

was spricht gegen:

#include <avr/pgmspace.h>

const uint8_t masks[] PROGMEM = {
  0b00000001,
  0b00000011,
  0b00000111,
  0b00001111,
  0b00011111,
  0b00111111,
  0b01111111,
  0b11111111
};

main()
{
  // volatile damit WinAVR das nicht gänzlich wegoptimiert
  static volatile uint8_t auszumaskieren = 42;
  static volatile uint8_t n = 4;

  // n = (...) //Aus irgendeiner Berechnung

  auszumaskieren &= pgm_read_byte( masks + n );
}

übersetzt:
...
0000008c <masks>:
  8c:  01 03 07 0f 1f 3f 7f ff                             .....?..
...
000000c6 <main>:
  auszumaskieren &= pgm_read_byte( masks + n );
  c6:  90 91 01 01   lds  r25, 0x0101
  ca:  80 91 00 01   lds  r24, 0x0100

  ce:  ec e8         ldi  r30, 0x8C  ; 140
  d0:  f0 e0         ldi  r31, 0x00  ; 0
  d2:  e8 0f         add  r30, r24
  d4:  f1 1d         adc  r31, r1
  d6:  e4 91         lpm  r30, Z+
  d8:  e9 23         and  r30, r25

  da:  e0 93 01 01   sts  0x0101, r30
}
  de:  80 e0         ldi  r24, 0x00  ; 0
  e0:  90 e0         ldi  r25, 0x00  ; 0
  e2:  08 95         ret

das sind 10 bytes code + 8 bytes masken im Flash
und 7 Takte um von N auf die Maske zu kommen
(Sorry schon mal imk Voraus, falls ich mich bei Bytes/Takten verrechnet 
haben sollte ;-)