Gegeben ein Bytearray uint8_t data[N] Was ist eine effiziente Methode, um ein Byte uint8_t search innerhalb von zu finden, auch wenn search nicht oktet ausgerichtet ist ? d.h. die ersten drei Bits von search könnten in data[i] und die nächsten 5 Bits in data[i+1] sein.
Meine aktuelle Methode beinhaltet das Erstellen einer bool get_bit(const uint8_t* src, struct internal_state* state) -Funktion ( struct internal_state enthält eine Maske, die nach rechts verschoben ist, & ed mit src und zurückgegeben, behält size_t src_index < size_t src_len bei), schiebt die zurückgegebenen Bits in eine uint8_t my_register und Vergleichen Sie es jedes Mal mit search und verwenden Sie state->src_index und state->src_mask , um die Position des übereinstimmenden Bytes zu erhalten.
Gibt es dafür eine bessere Methode?
Wenn Sie ein Acht-Bit-Muster in einem großen Array suchen, können Sie ein gleitendes Fenster über 16-Bit-Werte implementieren, um zu überprüfen, ob das gesuchte Muster Teil der zwei Bytes ist, die diesen 16-Bit-Wert bilden.
Um portierbar zu sein, müssen Sie sich um Endianness-Probleme kümmern, was durch meine Implementierung geschieht, indem Sie den 16-Bit-Wert erstellen, um manuell nach dem Muster zu suchen. Das High-Byte ist immer das aktuell iterierte Byte und das Low-Byte ist das folgende Byte. Wenn du eine einfache Konvertierung wie value = *((unsigned short *)pData) machst, wirst du auf x86-Prozessoren Probleme bekommen ...
Sobald value , cmp und mask sind Setup cmp und mask sind verschoben. Wenn das Muster nicht innerhalb eines hohen Bytes gefunden wurde, wird die Schleife fortgesetzt, indem das nächste Byte als Startbyte überprüft wird.
Hier ist meine Implementierung einschließlich einiger Debug-Ausdrucke (die Funktion gibt die Bitposition zurück oder -1, wenn das Muster nicht gefunden wurde):
%Vor%Ich denke nicht, dass Sie viel besser als das in C tun können:
%Vor% Die Hauptidee besteht darin, die 87,5% der Fälle zu behandeln, die die Grenze zwischen aufeinanderfolgenden Bytes durch Paarung Bytes in einem breiteren Datentyp überschreiten ( uint16_t in diesem Fall). Sie könnten es anpassen, um einen noch breiteren Datentyp zu verwenden, aber ich bin mir nicht sicher, dass das irgendetwas bringen würde.
Was Sie nicht sicher oder einfach tun können, ist alles, was den Casting Teil oder das gesamte Array zu einem breiteren Integer-Typ über einen Zeiger (d. h. (uint16_t *)&haystack[i] ) führt. Es kann nicht sichergestellt werden, dass die Ausrichtung für einen solchen Cast richtig ist, und auch nicht die Byte-Reihenfolge, mit der das Ergebnis interpretiert werden kann.
Wenn AVX2 akzeptabel ist (mit früheren Versionen funktionierte es nicht so gut, aber Sie können immer noch etwas tun), können Sie an vielen Orten gleichzeitig suchen. Ich konnte das nicht auf meinem Rechner testen (nur kompilieren), also ist das Folgende mehr, um Ihnen eine Vorstellung davon zu geben, wie man es angehen könnte, als Code kopieren und einfügen, also werde ich versuchen, es zu erklären, anstatt nur Code-Dump .
Der Grundgedanke ist, ein uint64_t zu lesen, nach allen sinnvollen Werten (0 bis 7) nach rechts zu verschieben, dann für jedes dieser 8 neuen uint64_t , ob das Byte drin ist. Kleine Komplikation: Für die uint64_t , die um mehr als 0 verschoben sind, sollte die höchste Position nicht gezählt werden, da Nullen darin eingefügt sind, die möglicherweise nicht in den tatsächlichen Daten enthalten sind. Sobald dies erledigt ist, sollte das nächste uint64_t mit einem Offset von 7 vom aktuellen gelesen werden, ansonsten gibt es eine Grenze, die nicht überkreuzt wird. Das ist in Ordnung, unausgerichtete Lasten sind nicht mehr so schlimm, besonders wenn sie nicht breit sind.
Also jetzt für einige (ungeprüfte und unvollständige, siehe unten) Code,
%Vor%Der witzige "Bit-Index und Byte-Index werden vertauscht", weil die Suche innerhalb eines Q-Worts byteweise erfolgt und die Ergebnisse dieser Vergleiche in 8 benachbarten Bits enden, während die Suche nach "um 1 verschoben" ist. endet in den nächsten 8 Bits und so weiter. In den resultierenden Masken ist der Index des Bytes, der die 1 enthält, ein Bit-Offset, aber der Bit-Index in diesem Byte ist tatsächlich der Byte-Offset, zum Beispiel würde 0x8000 dem Finden des Bytes am 7. Byte entsprechen das QWord, das um 1 nach rechts verschoben wurde, so ist der tatsächliche Index 8 * 7 + 1.
Es gibt auch das Problem des "Tails", des Teils der Daten, der übrig bleibt, wenn alle Blöcke von 7 Bytes verarbeitet wurden. Es kann auf die gleiche Weise gemacht werden, aber jetzt enthalten mehr Positionen gefälschte Bytes. Jetzt sind n - i Bytes übrig, also muss die Maske n - i Bits im untersten Byte setzen, und eine weniger für alle anderen Bytes (aus dem gleichen Grund wie früher haben die anderen Positionen Nullen hinein geschoben). Auch wenn es genau 1 Byte "left" gibt, ist es nicht wirklich übrig, weil es bereits getestet worden wäre, aber das ist nicht wirklich wichtig. Ich nehme an, dass die Daten ausreichend aufgefüllt sind, dass der Zugriff außerhalb der Grenzen keine Rolle spielt. Hier ist es, ungeprüft:
Wenn Sie eine große Menge an Speicher suchen und sich ein teures Setup leisten können, besteht eine andere Möglichkeit darin, eine 64K-Lookup-Tabelle zu verwenden. Für jeden möglichen 16-Bit-Wert speichert die Tabelle ein Byte, das den Bitverschiebungs-Offset enthält, bei dem das passende Oktett auftritt (+1, so dass 0 keine Übereinstimmung anzeigen kann). Sie können es folgendermaßen initialisieren:
%Vor%Beachten Sie, dass der Fall, in dem der Wert um 8 Bit verschoben ist, nicht enthalten ist (der Grund wird in einer Minute offensichtlich).
Dann können Sie Ihr Array von Bytes wie folgt scannen:
%Vor%Weitere Optimierung:
Es hängt von Ihrer Speicherarchitektur ab, ob dies schneller ist als eine entrollte Schleife, die keine Nachschlagetabelle verwendet.