Я не хотел ограничиваться целым числом фиксированного размера и составлением списков похожих команд с жестко закодированными константами, поэтому я разработал решение C ++ 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 репозиторий и livedemo .
Реализация
Практически каждый шаг в функции morton1 работает путем смещения и добавления в последовательность констант, которые выглядят следующим образом:
0b0101010101010101 (поочередно 1 и 0) 0b0011001100110011 (поочередно 2x 1 и 0) 0b0000111100001111 (поочередно 4x 1 и 0) 0b0000000011111111 (поочередно 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);
}