Эффективно деперемеживать четные и нечетные биты из целого числа в руке / неоне [дубликат]

Если вам удастся использовать специфические для архитектуры инструкции, вы, скорее всего, сможете ускорить операцию за пределами того, что возможно, используя бит-twiddeling hacks:

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

Вот полный пример (проверенный с помощью GCC):

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

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

Если вам нужно поддерживать более ранние процессоры или платформа ARM не все потеряно. Вы по-прежнему можете получить хотя бы помощь для функции xy_to_morton из инструкций, специфичных для криптографии.

В наши дни многие процессоры имеют поддержку переноса без потерь. В ARM, который будет vmul_p8 из набора команд NEON. На X86 вы найдете его как PCLMULQDQ из набора команд CLMUL (доступного с 2010 года).

Трюк здесь в том, что переносное умножение числа с собой вернет бит- который содержит исходные биты аргумента с чередованием нулевых битов. Таким образом, он идентичен показанному выше _pdep_u32 (x, 0x55555555). Например. он превращает следующий байт:

 +----+----+----+----+----+----+----+----+
 | b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 |
 +----+----+----+----+----+----+----+----+

В:

 +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
 | 0  | b7 | 0  | b6 | 0  | b5 | 0  | b4 | 0  | b3 | 0  | b2 | 0  | b1 | 0  | b0 |
 +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+

Теперь вы можете построить функцию xy_to_morton как (здесь показано для набора команд CLMUL):

#include <wmmintrin.h>
#include <stdint.h>

// on GCC, compile with option -mpclmul

uint64_t carryless_square (uint32_t x)
{
  uint64_t val[2] = {x, 0};
  __m128i *a = (__m128i * )val;
  *a = _mm_clmulepi64_si128 (*a,*a,0);
  return val[0];
}

uint64_t xy_to_morton (uint32_t x, uint32_t y)
{
  return carryless_square(x)|(carryless_square(y) <<1);
}

_mm_clmulepi64_si128 генерирует 128-битный результат, из которого мы используем только младшие 64 бит. Таким образом, вы можете даже улучшить версию выше и использовать один _mm_clmulepi64_si128, чтобы выполнить эту работу.

Это так хорошо, как вы можете попасть на основные платформы (например, современные ARM с NEON и x86). К сожалению, я не знаю никакого трюка, чтобы ускорить работу функции morton_to_xy с помощью инструкций по шифрованию, и я пробовал очень много работать в течение нескольких месяцев.