Фортран ISHFTC это просто поворот. C не имеет этого напрямую, но вы можете + безопасно написать функцию, которая компилирует с распознаванием образов и компилирует в одну инструкцию поворота. Лучшие практики для операций кругового сдвига (поворота) в C ++
Я не уверен, что это полезный строительный блок, но он доступен.
На x86 с расширениями набора команд BMI2 , есть команда pext извлечения битов, которую можно использовать с управляющим входом 0x5555.
См. Документы Intel для _pext_u32 и _u64
Это очень быстро для Intel Haswell и более поздних версий (1 моп, 3 такта, 1 / тактовая пропускная способность),
но довольно медленный медленный на AMD (Ryzen: 7 моп, задержка 18 циклов / пропускная способность). https://agner.org/optimize/ Я думаю, что это хуже, чем то, что мне приходилось использовать в чистом C, с использованием сдвига / маски, особенно если имеет значение задержка (а не только пропускная способность).
#include <immintrin.h>
unsigned extract_even_bits_bmi2(unsigned a) {
return _pext_u32(a, 0x5555);
}
С GCC / clang вы должны скомпилировать с -mbmi2 (или лучше, -march=haswell), чтобы разрешить использование встроенных функций BMI2.
Портативный ISO C ++
Я не думаю, что обычные трюки умножения (чтобы сдвинуть несколько входных байтов и добавить в верхний байт результата) будут работать здесь; у вас слишком много битов, и они слишком близко друг к другу. См. Как подсчитать количество установленных бит в 32-разрядном целом числе? для варианта использования:
((n & 0x0F0F0F0F) * 0x01010101) >> 24 для горизонтального добавления всех байтов в n.
Вы можете представить себе что-то подобное на своем входе с * 0x08040201, чтобы по-разному выровнять биты из разных байтов. Но это все еще оставляет главные нерешенные проблемы. Возможно, SIMD умножится на 8-битные элементы, чтобы сдвинуть пары бит вместе?
Но это не лучше, чем перемещать биты, маскируя, сдвигая и ИЛИ или добавляя перемещенные биты с неизменяющимися битами. С помощью шагов log2 (n_bits) мы можем получить все смежные биты.
Есть несколько способов сделать это, см. на Godbolt . В этом есть возможности для улучшения, например, настройка для лучшей компиляции для одного ISA против другого. например помогая некоторым компиляторам ARM увидеть, что 0b0000011000000110 - это просто другая постоянная, сдвинутая вправо, поэтому она может and r0, r1, r2, lsr #4 или что-то в этом роде.
Или сдвинуть биты вправо, а не влево, для ISA, которые не могут сделать ничего особенного для левого.
unsigned pack_even_bits16_v2(unsigned x)
{
x &= 0x5555; // 0a0b0c0d0e0f0g0h
x += x<<1; // aabbccddeeffgghh // x86 LEA eax, [rdi + rdi*2]
unsigned move = x & 0b0000011000000110; // bits to move
unsigned keep = x & 0b0110000001100000; // bits to keep
x = keep + (move << 2); // 0abcd000 0efgh000
// 0abcd000 0efgh000 // with byte boundary shown
unsigned tmp = x >> 7; // high group into place, shifting out the low bits
x &= 0xFF; // grab the whole low byte ; possibly with a zero-latency movzx
x = (x>>3) | tmp;
return x;
}
Я сдвигаю младшие биты влево вместо того, чтобы сдвигать старшие биты вправо, потому что x86 может сдвигать и добавлять влево с помощью одной инструкции, LEA. На других ISA, вероятно, было бы сэкономить одну смену в конце, чтобы переместить биты вправо.
Это прекрасно компилируется для AArch64 и PowerPC64, а также для x86. Clang просматривает эту битовую манипуляцию для PowerPC и использует мощные инструкции rlwinm (Поворот левого слова и немедленная маска) и rlwimi (... Вставка маски):)
# clang trunk -O3 for PowerPC64.
# Compiling the x += x & 0x1111; version, not the x += x<<1 version where we get a multiply
andi. 4, 3, 21845 # x & 0x5555
andi. 3, 3, 4369 # x & 0x1111
add 4, 4, 3 #
rlwinm 3, 4, 31, 30, 31 # isolate the low 2 bits. PPC counts bits from MSB=0 LSB=31 for 32-bit registers
rlwimi 3, 4, 29, 28, 29 # insert the next 2-bit bitfield
rlwimi 3, 4, 27, 26, 27 # ...
rlwimi 3, 4, 25, 24, 25
blr
Было бы лучше объединить пары, чем образовывать одну большую цепь.
Другой способ переместить биты - обнулить выбранные биты с помощью XOR, затем сдвинуть и поместить их в другое место с помощью сдвига и добавить.
unsigned tmp = x & mask;
x += tmp; // left shift those bits
x += tmp<<1; // left shift them again. (x86 can do this with LEA eax, [rax + rdx*2])
или
unsigned tmp = x & 0b0000011000000110; // bits to move
x ^= tmp; // clear those bits
x += tmp << 2; // LEA eax, [eax + edx*4] 1 fast instruction on x86
При перемещении только на 2 позиции add + shift-and-add в основном имеет ту же длину цепочки зависимостей, что и xor + shift-and-add.
Но очистка старых битов условно вместо противоположной маски, вероятно, хуже. По крайней мере, если противоположная маска подходит немедленно или если ISA имеет инструкцию ANDNOT. Или для ARM, сдвинутая маска. И 2 способа на старом x могут выполняться параллельно, против tmp = x & mask; x ^= tmp сериализации выполнения с зависимостью данных, если она компилируется как записано. (Это не так; gcc и clang достаточно умны, чтобы знать, что делает XOR, и безоговорочно очищают эти биты.)