So entschachteln Sie Bits effizient (inverses Morton)

Question

Diese Frage: Wie entschachtelt man Bits (UnMortonizing?) hat eine gute Antwort zum Extrahieren einer der beiden Hälften einer Morton-Zahl (nur die ungeraden Bits), aber ich brauche eine Lösung, die beide Teile (die ungeraden Bits und die geraden Bits) in möglichst wenigen Operationen extrahiert.

Für meine Verwendung müsste ich ein 32-Bit-Int nehmen und zwei 16-Bit-Ints extrahieren, wobei eines die geraden Bits und das andere die ungeraden Bits sind, die um 1 Bit nach rechts verschoben sind, z. B.

input,  z: 11101101 01010111 11011011 01101110

output, x: 11100001 10110111 // odd bits shifted right by 1
        y: 10111111 11011010 // even bits

Es scheint viele Lösungen zu geben, die Verschiebungen und Masken mit magischen Zahlen zur Generierung von Morton-Zahlen verwenden (z. B.Interleaving-Bits), z.B. Interleave-Bits durch Binary Magic Numbers, aber ich habe noch nichts gefunden, um das Gegenteil zu tun (d. h.Entschachtelung).

AKTUALISIEREN

Nachdem ich den Abschnitt über perfektes Mischen/Unmischen von Hacker's Delight noch einmal gelesen hatte, fand ich einige nützliche Beispiele, die ich wie folgt angepasst habe:

// morton1 - extract even bits

uint32_t morton1(uint32_t x)
{
    x = x & 0x55555555;
    x = (x | (x >> 1)) & 0x33333333;
    x = (x | (x >> 2)) & 0x0F0F0F0F;
    x = (x | (x >> 4)) & 0x00FF00FF;
    x = (x | (x >> 8)) & 0x0000FFFF;
    return x;
}

// morton2 - extract odd and even bits

void morton2(uint32_t *x, uint32_t *y, uint32_t z)
{
    *x = morton1(z);
    *y = morton1(z >> 1);
}

Ich denke, dass dies sowohl in der aktuellen Skalarform als auch durch die Nutzung von SIMD noch verbessert werden kann, daher bin ich immer noch an besseren Lösungen (entweder Skalar oder SIMD) interessiert.

Answer 1

Wenn Ihr Prozessor 64 Bit ints effizient umgibt, können Sie die Operationen kombinieren ... generasacodicetagpre.

Answer 2

Code für den Intel Haswell und den späteren CPUs.Sie können den BMI2-Anweisungssatz verwenden, der die Anweisungen von Pext- und PDEP enthält.Diese können (ua großartige Dinge) zum Erstellen Ihrer Funktionen verwendet werden. generasacodicetagpre.

Answer 3

falls jemand Morton-Codes in 3D verwendet, sodass er alle 3 ein Bit lesen muss, und 64 Bits hier ist die Funktion, die ich verwendet habe: generasacodicetagpre.

Answer 4

Wenn Sie Geschwindigkeit benötigen, als Sie eine Tabellensuche für eine Byte-Konvertierung gleichzeitig verwenden können (zwei Bytes-Tabelle ist schneller, aber zu groß).Verfahren erfolgt unter Delphi-IDE, aber der Assembler / Algorithem ist derselbe. generasacodicetagpre.

Answer 5

Ich wollte mich nicht auf eine Ganzzahl fester Größe und das Erstellen von Listen ähnlicher Befehle mit fest codierten Konstanten beschränken, also habe ich eine C++11-Lösung entwickelt, die Template-Metaprogrammierung nutzt, um die Funktionen und Konstanten zu generieren.Der mit generierte Assemblercode -O3 scheint so eng wie möglich zu sein, ohne den BMI zu verwenden:

andl    $0x55555555, %eax
movl    %eax, %ecx
shrl    %ecx
orl     %eax, %ecx
andl    $0x33333333, %ecx
movl    %ecx, %eax
shrl    $2, %eax
orl     %ecx, %eax
andl    $0xF0F0F0F, %eax
movl    %eax, %ecx
shrl    $4, %ecx
orl     %eax, %ecx
movzbl  %cl, %esi
shrl    $8, %ecx
andl    $0xFF00, %ecx
orl     %ecx, %esi

TL;DR Quell-Repo Und Live-Demo.

---

Implementierung

Grundsätzlich jeder Schritt in der morton1 Funktion funktioniert durch das Verschieben und Hinzufügen zu einer Folge von Konstanten, die wie folgt aussehen:

1. 0b0101010101010101 (abwechselnd 1 und 0)
2. 0b0011001100110011 (abwechselnd 2x 1 und 0)
3. 0b0000111100001111 (abwechselnd 4x 1 und 0)
4. 0b0000000011111111 (abwechselnd 8x 1 und 0)

Wenn wir verwenden würden D Abmessungen, mit denen wir ein Muster hätten D-1 Nullen und 1 eins.Um diese zu generieren, reicht es also aus, aufeinanderfolgende zu generieren und einige bitweise anzuwenden oder:

/// @brief Generates 0b1...1 with @tparam n ones
template <class T, unsigned n>
using n_ones = std::integral_constant<T, (~static_cast<T>(0) >> (sizeof(T) * 8 - n))>;

/// @brief Performs `@tparam input | (@tparam input << @tparam width` @tparam repeat times.
template <class T, T input, unsigned width, unsigned repeat>
struct lshift_add :
    public lshift_add<T, lshift_add<T, input, width, 1>::value, width, repeat - 1> {
};
/// @brief Specialization for 1 repetition, just does the shift-and-add operation.
template <class T, T input, unsigned width>
struct lshift_add<T, input, width, 1> : public std::integral_constant<T,
    (input & n_ones<T, width>::value) | (input << (width < sizeof(T) * 8 ? width : 0))> {
};

Jetzt können wir die Konstanten zur Kompilierzeit für beliebige Dimensionen wie folgt generieren:

template <class T, unsigned step, unsigned dimensions = 2u>
using mask = lshift_add<T, n_ones<T, 1 << step>::value, dimensions * (1 << step), sizeof(T) * 8 / (2 << step)>;

Mit der gleichen Rekursionsart können wir Funktionen für jeden Schritt des Algorithmus generieren x = (x | (x >> K)) & M:

template <class T, unsigned step, unsigned dimensions>
struct deinterleave {
    static T work(T input) {
        input = deinterleave<T, step - 1, dimensions>::work(input);
        return (input | (input >> ((dimensions - 1) * (1 << (step - 1))))) & mask<T, step, dimensions>::value;
    }
};
// Omitted specialization for step 0, where there is just a bitwise and

Es bleibt die Frage „Wie viele Schritte brauchen wir?“ zu beantworten.Dies hängt auch von der Anzahl der Dimensionen ab.Allgemein, k Schritte berechnen 2^k - 1 Ausgabebits;Die maximale Anzahl sinnvoller Bits für jede Dimension ist gegeben durch z = sizeof(T) * 8 / dimensions, daher reicht die Einnahme aus 1 + log_2 z Schritte.Das Problem ist jetzt, dass wir das brauchen constexpr um es als Vorlagenparameter zu verwenden.Der beste Weg, dies zu umgehen, ist meiner Meinung nach die Definition log2 über Metaprogrammierung:

template <unsigned arg>
struct log2 : public std::integral_constant<unsigned, log2<(arg >> 1)>::value + 1> {};
template <>
struct log2<1u> : public std::integral_constant<unsigned, 0u> {};

/// @brief Helper constexpr which returns the number of steps needed to fully interleave a type @tparam T.
template <class T, unsigned dimensions>
using num_steps = std::integral_constant<unsigned, log2<sizeof(T) * 8 / dimensions>::value + 1>;

Und schließlich können wir einen einzigen Aufruf durchführen:

/// @brief Helper function which combines @see deinterleave and @see num_steps into a single call.
template <class T, unsigned dimensions>
T deinterleave_first(T n) {
    return deinterleave<T, num_steps<T, dimensions>::value - 1, dimensions>::work(n);
}