mikrocontroller.net

Forum: Compiler & IDEs Bitmaske erzeugen


Autor: John Doe (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus Falser (kfalser)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: sebastians (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: JW (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ;-)

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.