proggen.org

Tag zusammen

So, ich wollte euch mal vor eine Aufgabe stellen:
Ich muss eine bestimmte Bitfolge (bzw eine Folge von Bits, die alle den Wert 0 besitzen) in einem relativ großem Speicherbereich suchen.
Ich hab also sozusagen: Nun möchte ich darin möglichst effizient (Das ist hierbei das wichtige) z.B. die Bitfolge 0000 suchen.
Wie mach ich das?

Dirty Oerti hat geschrieben:Nun möchte ich darin möglichst effizient (Das ist hierbei das wichtige) z.B. die Bitfolge 0000 suchen.
Wie mach ich das?

Pro Byte gibt es nur eine bestimmte Anzahl Muster, die Du prüfen musst:
- 10000000 post 1
- 11000000 post 2
- 11100000 post 3
- 11110000 match
- 01111000 match
- 00111100 match
- 00011110 match
- 00001111 match
- 00000111 pre 1
- 00000011 pre 2
- 00000001 pre 3

Die Einser erfordern Übereinstimmung, die 0er sind Dir egal. Also kannst Du & verwenden. Du musst hast also 5 Muster, die sofort einen Treffer signalisieren, Du hast 3 Muster, die ein Prefix darstellen, denen im nachfolgenden Byte ein Postfix folgen muss, damit es ein match ist. Hast Du zuvor kein Prefix gefunden, brauchst Du auf Postfixe schonmal nicht mehr zu achten. Hast Du prefix 3 gefunden, brauchst Du postfix 1 und 2 auch nicht mehr zu prüfen.
Heißt pro Byte maximal 11 Vergleiche, im Regelfall 8. Programmierst Du die 11 Möglichkeiten aus, so dass Du eine Statusmaschine erhälst, sollte das sehr schnell sein. If-Abfragen kosten hier richtig Zeit.

Möglichkeit 2:
Du nimmst ein Short, machst ein & auf 0xF000 und guckst, um es Dein Suchmuster ergibt. Du hast maximal 16 Möglichkeiten, also machst Du ein Array, wo Du den Ergebniswert von & als Index verwendest, der Dir sagt, ob Du 1, 2, 3 oder sogar vier Bits verschieben kannst. Nachdem Du acht Bit verschoben hast, lädst Du das nächste Byte ins Deine Short-Testvariable rein. Auch hier gilt - ifs vermeiden, so programmieren, dass hier einfach durchgerannt werden kann.

Hm...ich hab vergessen das wichtigste zu schreiben, glaube ich:

Diese Bitfolge darf (und wird) sich auch über Bytegrenzen ersrtecken.
Sprich so in etwa (Suche nach 0000) :

10110100|00100011|11111100|01000010|00011111

Und das natürlich über diesen kompletten Speicherbereich.

Dirty Oerti hat geschrieben:Diese Bitfolge darf (und wird) sich auch über Bytegrenzen ersrtecken.

Beide Möglichkeiten berücksichtigen das!?

Ähm..ja, natürlich^^

Ok, jetzt bei genauerer Betrachtung habe ich verstanden, was du mit Möglichkeit eins bezwecken möchtest.
Möglichkeit 2 verstehe ich irgendwie nicht so ganz...kannst du das an einem Beispiel zeigen?

Hm..bei Möglichkeit 1 könnte ich nur das Problem haben, dass ich ja variable Bitmuster (manchmal 00, dann wieder 000000000) suchen muss...

Dirty Oerti hat geschrieben:Ähm..ja, natürlich^^

Ok, jetzt bei genauerer Betrachtung habe ich verstanden, was du mit Möglichkeit eins bezwecken möchtest.
Möglichkeit 2 verstehe ich irgendwie nicht so ganz...kannst du das an einem Beispiel zeigen?

Du nimmst ein Short. Da sind 0 Bits drin, solange weniger Bits als für Deinen Test notwendig sind, lädst Du nach.
repeat...
- Bytenachladen. 8 Bits sind belegt: reicht für einen Test
- Dein Bitmuster hat vier Bit, also prüfst Du Dein (Short >> 12) == Dein Bitmuster. Wenn ja => Treffer
- Wenn nein, dann ist (Short >> 12) eine Zahl zwischen 1 und 15. In einem Array verzeichnest Du, wie weit Du Dein Short nach links bewegen musst. Bei 1000???? läuft der nächste Test, 1 Bit weiter nach links. bei 1001???? kannst Du das Bitmuster um ganze 4 Bit verschieben.
until fertig.

Dirty Oerti hat geschrieben:Hm..bei Möglichkeit 1 könnte ich nur das Problem haben, dass ich ja variable Bitmuster (manchmal 00, dann wieder 000000000) suchen muss...

Könntest Du. Wenn Du allerdings mitten im Spiel die Spielregeln änderst, bekommst Du immer Probleme. :->