Лучшие практики для операций кругового сдвига (поворота) в C ++

Question

Операторы сдвига влево и вправо (<< и >>) уже доступны в C ++. Однако я не мог выяснить, как я мог выполнять операции кругового сдвига или поворота.

Как можно выполнять такие операции, как «Поворот влево» и «Поворот вправо»?

Здесь дважды вращается вправо

Initial --> 1000 0011 0100 0010

должно привести к:

Final   --> 1010 0000 1101 0000

Пример будет полезен.

(примечание редактора: многие распространенные способы выражения поворотов в C страдают от неопределенного поведения, если счетчик поворотов равен нулю или компилируется в более чем одну машинную инструкцию поворота. Ответ на этот вопрос должен задокументировать лучшие практики)

Answer 1

См. Также более раннюю версию этого ответа на другой вопрос поворота с некоторыми подробностями о том, что asm gcc / clang производит для x86.

Наиболее удобным для компилятора способом выражения поворота в C и C ++, позволяющим избежать любого неопределенного поведения, является реализация Джона Регера . Я адаптировал его для поворота по ширине шрифта (используя типы фиксированной ширины, такие как uint32_t).

#include <stdint.h>   // for uint32_t
#include <limits.h>   // for CHAR_BIT
// #define NDEBUG
#include <assert.h>

static inline uint32_t rotl32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);  // assumes width is a power of 2.

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n<<c) | (n>>( (-c)&mask ));
}

static inline uint32_t rotr32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n>>c) | (n<<( (-c)&mask ));
}

Работает для любого целого типа без знака, а не только uint32_t, поэтому вы можете создавать версии для других размеров.

См. также шаблонную версию C ++ 11 с множеством проверок безопасности (включая static_assert, что ширина типа равна степени 2) , что не например, для некоторых 24-битных DSP или 36-битных мэйнфреймов.

Я бы порекомендовал использовать шаблон только в качестве серверной части для упаковщиков с именами, в которых явно указана ширина поворота. Правила целочисленного продвижения означают, что rotl_template(u16 & 0x11UL, 7) будет выполнять 32- или 64-битное вращение, а не 16 (в зависимости от ширины unsigned long). Даже uint16_t & uint16_t повышается до signed int по правилам целочисленного продвижения C ++, за исключением платформ, где int не шире, чем uint16_t.

---

На x86 эта версия встроена в один rol r32, cl (или rol r32, imm8) с компиляторами, которые его проглатывают, потому что компилятор знает, что x86 вращается и инструкции сдвига маскируют счет сдвига так же, как это делает источник C.

Поддержка компилятора для этой идиомы избегания UB на x86, для uint32_t x и unsigned int n для сдвигов с переменным числом:

• clang: распознается для поворотов с переменным числом, начиная с clang3.5, с несколькими сменами + или insns до этого.
• gcc: распознается для поворотов с переменным числом, начиная с gcc4.9 , с несколькими сменами + или insns до этого. gcc5 и более поздние версии также оптимизируют ветку и маску в версии википедии, используя только инструкцию ror или rol для подсчета переменных.
• icc: поддерживается для вращений с переменным числом, начиная с ICC13 или ранее . Для поворота с постоянным счетом используется shld edi,edi,7, который медленнее и занимает больше байтов, чем rol edi,7 на некоторых процессорах (особенно AMD, но также и на некоторых Intel), когда BMI2 недоступен для rorx eax,edi,25 для сохранения MOV.
• MSVC: x86-64 CL19: распознается только для поворотов с постоянным счетом. (Идиома википедии распознается, но ветвь и AND не оптимизированы). Используйте свойства _rotl / _rotr из <intrin.h> на x86 (включая x86-64).

gcc для ARM использует and r1, r1, #31 для вращений с переменным счетом, но все же выполняет фактическое вращение с одной инструкцией : ror r0, r0, r1. Таким образом, gcc не понимает, что число поворотов является модульным. Как сказано в документации ARM, "ROR с длиной смещения, n, более 32 - это то же самое, что ROR с длиной смещения n-32" . Я думаю, что gcc здесь запутался, потому что сдвиги влево / вправо на ARM насыщают счет, поэтому сдвиг на 32 или больше очистит регистр. (В отличие от x86, где сдвиги маскируют счет так же, как и вращение). Вероятно, он решает, что ему нужна инструкция AND перед распознаванием идиомы поворота, из-за того, как некруглые сдвиги работают на этой цели.

Текущие компиляторы x86 по-прежнему используют дополнительную инструкцию для маскировки счетчика переменных для 8- и 16-битных поворотов, вероятно, по той же причине, по которой они не избегают AND в ARM. Это пропущенная оптимизация, поскольку производительность не зависит от числа оборотов на любом процессоре x86-64. (Маскирование счетчиков было введено с 286 по соображениям производительности, потому что оно обрабатывало сдвиги итеративно, а не с постоянной задержкой, как современные процессоры.)

Кстати, для поворотов с переменным числом предпочтение отдается повороту вправо, чтобы компилятор не делал 32-n для реализации поворота влево на архитектурах, таких как ARM и MIPS, которые обеспечивают только поворот вправо. (Это оптимизирует счет с постоянными времени компиляции.)

Интересный факт: ARM на самом деле не имеет специальных команд сдвига / поворота, это просто MOV с операндом источника , проходящим через баррель в режиме ROR : mov r0, r0, ror r1. Таким образом, вращение может сложиться в операнд источника-регистра для инструкции EOR или чего-то еще.

---

Убедитесь, что вы используете беззнаковые типы для n и возвращаемого значения, иначе это не будет поворот . (gcc для целей x86 выполняет арифметическое смещение вправо, смещение копий знака-знака, а не нуля, что приводит к проблеме, когда вы OR объединяете два сдвинутых значения. Сдвиг вправо отрицательных целых чисел со знаком является определяемым реализацией C).

Кроме того, убедитесь, что счетчик сдвигов относится к типу без знака , потому что (-n)&31 со знаком со знаком может быть дополнением или знаком / величиной, а не модульным 2 ^ n, который вы получаете. с неподписанным или двумя дополнениями. (См. Комментарии к сообщению в блоге Регера). unsigned int хорошо работает на каждом компиляторе, на который я смотрел, при любой ширине x. Некоторые другие типы фактически игнорируют распознавание идиомы для некоторых компиляторов, поэтому не просто используйте тот же тип, что и x.

---

Некоторые компиляторы предоставляют встроенные функции для поворотов , что намного лучше, чем inline-asm, если переносимая версия не генерирует хороший код на выбранном вами компиляторе. Не существует кроссплатформенных встроенных функций для каких-либо известных мне компиляторов. Вот некоторые из вариантов x86:

• Intel документирует, что <immintrin.h> обеспечивает _rotl и _rotl64 встроенные , и то же самое для сдвига вправо. MSVC требует <intrin.h>, в то время как gcc требует <x86intrin.h>. #ifdef заботится о gcc против icc, но, похоже, clang их нигде не предоставляет, за исключением режима совместимости MSVC с -fms-extensions -fms-compatibility -fms-compatibility-version=17.00. И asm, который он испускает для них, отстой (дополнительная маскировка и CMOV).
• MSVC: _rotr8 и _rotr16.
• gcc и icc (не clang): <x86intrin.h> также обеспечивает __rolb / __rorb для 8-битного поворота влево / вправо, __rolw / __rorw (16-бит), __rold / __rord (32-битный), __rolq / __rorq (64-битный, только для 64-битных целей). Для узких поворотов в реализации используются __builtin_ia32_rolhi или ...qi, но 32- и 64-разрядные повороты определяются с помощью сдвига / или (без защиты от UB, поскольку код только в ia32intrin.h должен работать на gcc для x86). Похоже, что GNU C не имеет каких-либо кроссплатформенных функций __builtin_rotate, как для __builtin_popcount (которые расширяются до того, что является оптимальным на целевой платформе, даже если это не одна инструкция). Большую часть времени вы получаете хороший код от распознавания идиом.

// For real use, probably use a rotate intrinsic for MSVC, or this idiom for other compilers.  This pattern of #ifdefs may be helpful
#if defined(__x86_64__) || defined(__i386__)

#ifdef _MSC_VER
#include <intrin.h>
#else
#include <x86intrin.h>  // Not just <immintrin.h> for compilers other than icc
#endif

uint32_t rotl32_x86_intrinsic(rotwidth_t x, unsigned n) {
  //return __builtin_ia32_rorhi(x, 7);  // 16-bit rotate, GNU C
  return _rotl(x, n);  // gcc, icc, msvc.  Intel-defined.
  //return __rold(x, n);  // gcc, icc.
  // can't find anything for clang
}
#endif

Предположительно, некоторые компиляторы, отличные от x86, также имеют встроенные функции, но давайте не будем расширять этот ответ вики-сообщества, чтобы включить их все. (Возможно, сделайте это в существующем ответе о внутренностях ).

---

(В старой версии этого ответа предлагался встроенный asm для MSVC (который работает только для 32-битного кода x86), или http://www.devx.com/tips/Tip/14043 для версии на C. На это отвечают комментарии.)

Встроенный asm побеждает многие оптимизации , , особенно в стиле MSVC, поскольку он заставляет входные данные быть сохраненными / перезагруженными . Тщательно написанное вращение in-asm в GNU C позволило бы счету быть непосредственным операндом для счетчиков смещения во время компиляции, но он все равно не мог оптимизировать полностью, если значение, которое должно быть смещено, также является константой времени компиляции после встраивания. https://gcc.gnu.org/wiki/DontUseInlineAsm.

Answer 2

Поскольку это C ++, используйте встроенную функцию:

template <typename INT> 
INT rol(INT val) {
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}

C ++ 11 вариант:

template <typename INT> 
constexpr INT rol(INT val) {
    static_assert(std::is_unsigned<INT>::value,
                  "Rotate Left only makes sense for unsigned types");
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}

Answer 3

Большинство компиляторов имеют встроенные функции для этого. Visual Studio, например _rotr8, _rotr16

Answer 4

Определённо:

template<class T>
T ror(T x, unsigned int moves)
{
  return (x >> moves) | (x << sizeof(T)*8 - moves);
}

Answer 5

Как примерно так, используя стандартный набор битов ...

#include <bitset> 
#include <iostream> 

template <std::size_t N> 
inline void 
rotate(std::bitset<N>& b, unsigned m) 
{ 
   b = b << m | b >> (N-m); 
} 

int main() 
{ 
   std::bitset<8> b(15); 
   std::cout << b << '\n'; 
   rotate(b, 2); 
   std::cout << b << '\n'; 

   return 0;
}

НТН,

Answer 6

В деталях вы можете применить следующую логику.

Если битовый массив равен 33602 в целых числах

1000 0011 0100 0010

и вам нужно перевернуться с двумя правыми сдвигами: сначала сделайте копию битового шаблона, а затем сдвиньте его влево: длина - правое смещение то есть длина равна 16, значение правого сдвига равно 2 16 - 2 = 14

После 14 раз сдвига влево вы получите.

1000 0000 0000 0000

Теперь сдвиньте вправо значение 33602, 2 раза, как требуется. Вы получаете

0010 0000 1101 0000

Теперь возьмите ИЛИ между 14 смещенным влево значением и 2 смещенным вправо значением.

1000 0000 0000 0000
0010 0000 1101 0000
===================
1010 0000 1101 0000
===================

И вы получите смещенное значение ролловера. Помните, что побитовые операции выполняются быстрее, и для этого даже не требуется никакого цикла.

Answer 7

Если x является 8-битным значением, вы можете использовать это:

x=(x>>1 | x<<7);

Answer 8

Предполагая, что вы хотите сдвинуть вправо на L бит, а вход x - это число с N битами:

unsigned ror(unsigned x, int L, int N) 
{
    unsigned lsbs = x & ((1 << L) - 1);
    return (x >> L) | (lsbs << (N-L));
}

Answer 9

Правильный ответ следующий:

#define BitsCount( val ) ( sizeof( val ) * CHAR_BIT )
#define Shift( val, steps ) ( steps % BitsCount( val ) )
#define ROL( val, steps ) ( ( val << Shift( val, steps ) ) | ( val >> ( BitsCount( val ) - Shift( val, steps ) ) ) )
#define ROR( val, steps ) ( ( val >> Shift( val, steps ) ) | ( val << ( BitsCount( val ) - Shift( val, steps ) ) ) )

Answer 10

--- Substituting RLC in 8051 C for speed --- Rotate left carry
Here is an example using RLC to update a serial 8 bit DAC msb first:
                               (r=DACVAL, P1.4= SDO, P1.5= SCLK)
MOV     A, r
?1:
MOV     B, #8
RLC     A
MOV     P1.4, C
CLR     P1.5
SETB    P1.5
DJNZ    B, ?1

Here is the code in 8051 C at its fastest:
sbit ACC_7  = ACC ^ 7 ; //define this at the top to access bit 7 of ACC
ACC     =   r;
B       =   8;  
do  {
P1_4    =   ACC_7;  // this assembles into mov c, acc.7  mov P1.4, c 
ACC     <<= 1;
P1_5    =   0;
P1_5    =   1;
B       --  ; 
    } while ( B!=0 );
The keil compiler will use DJNZ when a loop is written this way.
I am cheating here by using registers ACC and B in c code.
If you cannot cheat then substitute with:
P1_4    =   ( r & 128 ) ? 1 : 0 ;
r     <<=   1;
This only takes a few extra instructions.
Also, changing B for a local var char n is the same.
Keil does rotate ACC left by ADD A, ACC which is the same as multiply 2.
It only takes one extra opcode i think.
Keeping code entirely in C keeps things simpler sometimes.