Как эффективно деинтегрировать биты (обратный Мортон)

Ответ 1

Если ваш процессор эффективно обрабатывает 64-битные ints, вы можете комбинировать операции...

int64 w = (z &0xAAAAAAAA)<<31 | (z &0x55555555 )
w = (w | (w >> 1)) & 0x3333333333333333;
w = (w | (w >> 2)) & 0x0F0F0F0F0F0F0F0F; 
...

Ответ 2

Код для Intel Haswell и более поздних процессоров. Вы можете использовать набор команд BMI2, содержащий инструкции pext и pdep. Они могут (среди других великих вещей) использоваться для создания ваших функций.

#include <immintrin.h>
#include <stdint.h>

// on GCC, compile with option -mbmi2, requires Haswell or better.

uint64_t xy_to_morton (uint32_t x, uint32_t y)
{
    return _pdep_u32(x, 0x55555555) | _pdep_u32(y,0xaaaaaaaa);
}

uint64_t morton_to_xy (uint64_t m, uint32_t *x, uint32_t *y)
{
    *x = _pext_u64(m, 0x5555555555555555);
    *y = _pext_u64(m, 0xaaaaaaaaaaaaaaaa);
}

Ответ 3

В случае, если кто-то использует смертные коды в 3d, поэтому ему нужно прочитать один бит каждые 3, а 64 бит - это функция, которую я использовал:

uint64_t morton3(uint64_t x) {
    x = x & 0x9249249249249249;
    x = (x | (x >> 2))  & 0x30c30c30c30c30c3;
    x = (x | (x >> 4))  & 0xf00f00f00f00f00f;
    x = (x | (x >> 8))  & 0x00ff0000ff0000ff;
    x = (x | (x >> 16)) & 0xffff00000000ffff;
    x = (x | (x >> 32)) & 0x00000000ffffffff;
    return x;
}
uint64_t bits; 
uint64_t x = morton3(bits)
uint64_t y = morton3(bits>>1)
uint64_t z = morton3(bits>>2)

Ответ 4

Если вам нужна скорость, вы можете использовать поиск таблиц для однобайтового преобразования сразу (таблица с двумя байтами быстрее, но большая). Процедура выполняется в среде Delphi IDE, но ассемблер/алгоритм тот же.

const
  MortonTableLookup : array[byte] of byte = ($00, $01, $10, $11, $12, ... ;

procedure DeinterleaveBits(Input: cardinal);
//In: eax
//Out: dx = EvenBits; ax = OddBits;
asm
  movzx   ecx, al                                     //Use 0th byte
  mov     dl, byte ptr[MortonTableLookup + ecx]
//
  shr     eax, 8
  movzx   ecx, ah                                     //Use 2th byte
  mov     dh, byte ptr[MortonTableLookup + ecx]
//
  shl     edx, 16
  movzx   ecx, al                                     //Use 1th byte
  mov     dl, byte ptr[MortonTableLookup + ecx]
//
  shr     eax, 8
  movzx   ecx, ah                                     //Use 3th byte
  mov     dh, byte ptr[MortonTableLookup + ecx]
//
  mov     ecx, edx  
  and     ecx, $F0F0F0F0
  mov     eax, ecx
  rol     eax, 12
  or      eax, ecx

  rol     edx, 4
  and     edx, $F0F0F0F0
  mov     ecx, edx
  rol     ecx, 12
  or      edx, ecx
end;

Ответ 5

Я не хотел ограничиваться целым числом фиксированного размера и составлял списки аналогичных команд с жестко закодированными константами, поэтому я разработал решение С++ 11, которое использует метапрограммирование шаблона для генерации функций и констант. Код сборки, сгенерированный с помощью -O3, выглядит настолько тугим, насколько он может получить без использования BMI:

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 исходное репо и живая демонстрация.

Реализация

В принципе, каждый шаг в функции morton1 работает путем изменения и добавления к последовательности констант, которые выглядят следующим образом:

• 0b0101010101010101 (alternate 1 и 0)
• 0b0011001100110011 (чередовать 2x 1 и 0)
• 0b0000111100001111 (alternate 4x 1 и 0)
• 0b0000000011111111 (alternate 8x 1 и 0)

Если бы мы использовали размеры D, у нас был бы шаблон с D-1 нулями и 1 один. Поэтому для генерации их достаточно создать последовательные и применить побитовое или:

/// @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))> {
};

Теперь, когда мы можем сгенерировать константы во время компиляции для произвольных измерений со следующим:

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)>;

При том же типе рекурсии мы можем генерировать функции для каждого из шагов алгоритма 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

Остается ответить на вопрос "сколько шагов нам нужно?". Это зависит также от количества измерений. В общем случае, k вычисляет выходные биты 2^k - 1; максимальное количество значащих битов для каждого измерения определяется z = sizeof(T) * 8 / dimensions, поэтому достаточно выполнить шаги 1 + log_2 z. Проблема в том, что нам нужно это как constexpr, чтобы использовать его в качестве параметра шаблона. Лучшим способом, который я нашел для этого, является определение log2 с помощью метапрограммирования:

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>;

И, наконец, мы можем выполнить один вызов:

/// @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);
}