Какова цель инструкций поворота (ROL, RCL на x86)?

Question

Мне всегда было интересно, какова цель инструкций поворота, которые есть у некоторых процессоров (например, ROL, RCL на x86). Какое программное обеспечение использует эти инструкции? Сначала я подумал, что они могут быть использованы для шифрования / вычисления хеш-кодов, но эти библиотеки обычно пишутся на C, в котором нет операторов, которые соответствуют этим инструкциям.
Кто-нибудь нашел применение для них? Почему, где они добавили в набор инструкций?

Answer 1

Повороты требуются для сдвигов битов по нескольким словам. Когда вы SHL младшее слово, старший бит выливается в перенос. Чтобы завершить операцию, вам нужно сдвинуть старшее слово (слова), одновременно передавая перенос в младший бит. RCL - это инструкция, которая выполняет это.

                      Старшее слово Низкое слово CF
Начальный 0110 1001 1011 1001   1100 0010 0000 1101?
SHL младшее слово 0110 1001 1011 1001 1000 0100 0001 1010 1
Старшее слово RCL 1101 0011 0111 0011 1000 0100 0001 1010 1 

ROL и ROR полезны для проверки значения побитовым способом, который (в конечном счете) является неразрушающим. Они также могут быть использованы, чтобы шунтировать битовую маску, не внося мусорные биты.

Answer 2

Коды операций сдвига поворота ROL, RCL, ROR, RCR) используются почти исключительно для хеширования и вычислений CRC. Они довольно загадочны и очень редко используются.

Сдвиговые коды операций (SHL, SHR) используются для быстрого умножения на степени 2 или для перемещения младшего байта в старший байт большого регистра.

Разница между ROL и SHL заключается в том, что ROL берет старший бит и катит его в младшую позицию. SHL отбрасывает старший бит и заполняет позицию младшего бита нулем.

Answer 3

ROR ROL являются "историческими", но все же полезными во многих отношениях.

До 80386 (и опкода BT) ROL много использовался бы для проверки бита (SHL не распространяется на флаг переноса) - фактически в 8088 году ROR/ROL сдвигался только на 1 бит за раз!!!!

Также, если вы хотите сдвинуться в одну сторону, а затем в другую, не теряя биты, которые были сдвинуты за пределы области видимости, вы бы использовали ROR/ROL вместо SHR/SHL

Answer 4

Если я вас правильно понимаю, ваш вопрос таков:

"Учитывая тот факт, что инструкции ротации кажутся очень специализированными и не генерируются компиляторами, когда они на самом деле используются и почему они включены в процессоры?".

Ответ двоякий:

1. Процессоры не предназначены специально для выполнения программ на C. Скорее, они спроектированы как машины общего назначения, предназначенные для решения широкого круга задач с использованием широкого спектра различных инструментов и языков.

2. Разработчики языка не обязаны использовать каждый код операции в CPU. Фактически, в большинстве случаев это не так, потому что некоторые инструкции ЦП являются узкоспециализированными, и у разработчика языка нет острой необходимости их использовать.

Дополнительную информацию о побитовых операторах (и как они связаны с программированием на C) можно найти здесь: http://en.wikipedia.org/wiki/Bitwise_operation

Answer 5

Когда микропроцессоры были созданы впервые, большинство программ были написаны на ассемблере, а не скомпилированы. Большинство инструкций процессора, вероятно, не генерируются компиляторами (что является стимулом для создания RISC), но часто относительно легко реализуются в аппаратном обеспечении.

Многие алгоритмы в графике и криптографии используют ротацию, и их включение в процессоры позволяет писать очень быстрые алгоритмы в сборке.

Answer 6

Я думаю, что многие ответы здесь получили это несколько назад, включая принятый в настоящее время. Самое большое применение заключается в перемещении данных через границы байтов/слов, что широко используется в

• извлечение и вставка битовых комбинаций
  • протоколы (вставьте 5 бит, начиная с бита 6)
  • схемы сжатия (LZW77 и более)
  • передача данных (любые модемы 300 бод? 7-битные данные + четность)
• арифметика произвольной точности
  • умножение/деление на 2 использует сквозной перенос
  • умножение/деление на другие степени двойки требует ROL (или ROR)
  • прокрутка 1-битной графики по горизонтали

И нишевые приложения:

• crc16/32
• шифры
• неразрушающие движущиеся биты для знакового бита или переноски для тестирования

Исторически сложилось так, что сдвиг был дорогостоящим: когда нужно сдвинуть, скажем, 16 бит влево на 3 фрагментами по 8 бит (или оставшиеся 128 бит фрагментами по 64 бита), ROL выполняет два дорогостоящих сдвига по цене одного:

      rotate all bits left by 3
      hi       lo
src = fedcba98|76543210
dst = cba98765|43210---

Обратите внимание, что биты «765» нужно сдвинуть вправо на 5, а биты «43210» нужно сдвинуть влево на 3. Все это достигается одним поворотом, который ставит все правые биты в правильное положение, даже если они сопровождаются неправильными битами, которые рекомбинируются путем маскирования, что является недорогой операцией:

      dst_lo = ((src_lo ROL 3) & 0b11111000)
dst_hi = ((src_lo ROL 3) & 0b00000111) | (src_hi << 3)

Это распространяется на смещение большого числа или прокрутку монохромной графической плоскости по горизонтали на произвольное количество пикселей.

Этот алгоритм настолько важен, что в 80386 для него включена инструкция двойного поворота.