thru carry

[netch80]

Мини-квест для пользователей десктопов и лаптопов, в общем, x86: найдите хоть одну команду RCL или RCR в естественно возникшем (из пакетов, etc.) программном коде на своей системе. Ложные срабатывания (показ мусора как кода в mplayer, libavcodec) не в счёт.

У меня пока что результат - только libgmp с куском хитрой арифметики (__gmpn_rsh1add_n, __gmpn_rsh1sub_n и тому подобные), причём там сдвиги ровно по 1 биту, и libgcrypt (в OpenSuSE), с каким-то бешеным алгоритмом, аналогично.

UPDATE[2016.08.23]: RCR была бы полезна для небольших упрощений деления на 7, 19 и т.п., там, где сейчас борются с беззнаковым переполнением через промежуточные короткие результаты.

Comments

[dimich-dmb.livejournal.com]

$ find /usr/lib -name '*.so' | xargs objdump -d 2>/dev/null | perl -ne '{ print if /\s+rc[rl][bwl]\s+/ }' | wc -l
99
потом попробую выловить, где именно

[netch80.livejournal.com]

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

[dmarck.livejournal.com]

У меня (рабочая станция на Фре) получился вот такой список:

/usr/local/lib/libavcodec.so.1: file format elf32-i386-freebsd
/usr/local/lib/libavahi-ui.so.0: file format elf32-i386-freebsd
/usr/local/lib/libcrypto.so.8: file format elf32-i386-freebsd
/usr/local/lib/libgmp.so.10: file format elf32-i386-freebsd
/usr/local/lib/libx264.so.125: file format elf32-i386-freebsd

на другой машине, серверной, и с более свежей Фрёй:

/lib/libcrypto.so.7: file format elf64-x86-64-freebsd
/usr/local/lib/libgcrypt.so.20: file format elf64-x86-64-freebsd
/usr/local/lib/libsqlite3.so.0: file format elf64-x86-64-freebsd
/usr/local/lib/libsvn_fs_util-1.so.0: file format elf64-x86-64-freebsd
/usr/local/lib/cairo/cairo-fdr.so.0: file format elf64-x86-64-freebsd

все использования похожи на реальные.

[netch80.livejournal.com]

libgmp - да. Остальные - 95%, что результат декодинга данных, хранящихся в секции ".text". Ну разве что про cairo у меня сомнения.

[dimich-dmb.livejournal.com]

Да, действительно. Использование в реальном коде нашел в libgmp, libxul и VBoxVMM. В последнем — функции-обертки для соответствующих инструкций.
Ну оно и неудивительно: почти все написано на высокоуровневых языках. Очень уж интеллектуальным должен быть оптимизатор, чтобы найти, что из высокоуровневого кода можно можно эффективно заменить этими инструкциями.

[netch80.livejournal.com]

В XUL у меня не нашлось, зато нашлось ещё в mpdivtwo() из какой-то криптографии в librpmcpio. И во всех сдвиг только на 1 бит.

По-нормальному эти инструкции следовало бы прирезать ещё в i386. shld/shrd дают аналогичный результат не хуже, зато универсальнее.

[dimich-dmb.livejournal.com]

Насколько знаю, основное преднаначение rcr/rcl — подсчет CRC. В LFSR обычно как раз 2^n+1 бит. Сейчас считают в основном табличным методом, но при экстремальной оптимизации по размеру может быть полезно.
Вообще CISC, как по мне, тупиковый путь. Хотя с технологией микрокодов плюс-минус одна инструкция — небольшие расходы.

[netch80.livejournal.com]

> Насколько знаю, основное преднаначение rcr/rcl — подсчет CRC.

Если речь про саму CRC, то все существующие реализации могут быть основаны на ror, а не rcr. И даже без него тривиально делается, где-то так:

bit_step:
    rol $1,%edx
    jc 1f
    xor $ALGO_CONST,%edx
1:  shl $1,%eax
    setc %si
    xor %esi,%edx

Все найденные примеры на rcl/rcr это действия типа умножения длинного числа на 2 или деления такого числа. Сама по себе цель неплоха, но тут же видно, например, 4-кратное применение цепочки из таких команд, а это то, что лучше было бы покрыто каким-нибудь shrd за один проход вместо одного прохода на каждый бит.

> Вообще CISC, как по мне, тупиковый путь. Хотя с технологией микрокодов плюс-минус одна инструкция — небольшие расходы.

Тут вопрос не в CISC, а просто в бессмысленности этих команд (и зачем их тянут через все версии, просто непонятно - их надо было убить сразу для 32-битного кода, просто не реализовывать там). С упоминанием CISC я не согласен потому, что CISC это не сложный набор команд, это сами команды сложные (например, типа PDP-11 адресации @(Rn)+); сами команды могут быть сколь угодно извращёнными (например, инкремент 4 регистров одновременно), если это нужно для важной задачи и делается легко в стандартный набор внутренних действий. Реализация логики rcl/rcr тривиальна в один такт отдельным экземпляром barrel shifter, это тоже не безумно сложно - просто громоздко (блок на пару сотен вентилей, который больше ни на что нафиг не сдался).

> В LFSR обычно как раз 2^n+1 бит.

Даже нетаблично работают с N битами (CRC-32 => 32 бита), а старший присутствует виртуально.

[dimich-dmb.livejournal.com]

> Все найденные примеры на rcl/rcr это действия типа умножения длинного числа на 2 или деления такого числа.

Да, нашел вот в Guide to Assembly Language Programming in Linux (http://books.google.com.ua/books?id=HeorH2cE7WkC), что эти инструкции предназнаются для сдвига длинных чисел. Тогда неясно, зачем потом ввели сдвиг на несколько бит сразу.

> Тут вопрос не в CISC, а просто в бессмысленности этих команд (и зачем их тянут через все версии, просто непонятно - их надо было убить сразу для 32-битного кода, просто не реализовывать там)

Так в 386 ядре еще не было микрокода, 16-битный код выполнялся тем же декодером. Поэтому оставили для совместимости. А в x86_64 в long mode, согласен, можно было и выбросить.

Ради интереса грепнул свои ассемблерные исходники в археологических залежах, нашел использование rcl/rcr в каком-то ГПСЧ и в преобразовании числа в двоичную строку (хотя можно было и rol, и shl).

[netch80.livejournal.com]

> Тогда неясно, зачем потом ввели сдвиг на несколько бит сразу.

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

> 16-битный код выполнялся тем же декодером.

По-нормальному для 32-битного кода нужно было сделать новый декодер, и при этом:
1. Перевести следующие инструкции на двухбайтные коды: push/pop сегментных регистров, двоично-десятичная арифметика, lds/les/lss, xlat, in/out/ins/outs, hlt, cmc, [i]mul/[i]div, всех "строковых" операций, iret, int3, cli, sti, lahf, sahf.
Освобождённые коды в дальнейшем применить на что-то более полезное (аналоги MMX/SSE уже тогда были широко известны, и перспективность расширения - тоже).
2. Устраненить все сокращённые коды операций при участии аккумулятора в качестве первого операнда. (типа ${op} al,imm)
3. Отменить pusha/popa, или опять же перенести в 2-байтные.
4. Устраненить исключения в командах целочисленного деления.
5. Удалить rcl, rcr или опять же перенести в 2-байтные коды.
(shld, shrd обеспечивают те же потребности не хуже.)
6. Сделать cpuid (хотя бы работающий как nop, но документированный), доступный по факту поддержки 32-битных команд.
7. Оставить генерацию признака чётности в флаге PF только для логических команд (and, test, or, xor, not, сдвиги) и только для младших 16 бит результата. А лучше - вообще вынести подсчёт чётности в отдельные команды, а флаг применить под что-то более полезное.
8. Перевести сопроцессор со стека на фиксированные номера регистров.

(Это я всё не с точки зрения знания 2014 года, а с точки зрения 1985-го.)
Почему это не было сделано - это как раз то, почему я не уважаю Intel.

[dimich-dmb.livejournal.com]

> По-нормальному для 32-битного кода нужно было сделать новый декодер

По-нормальному с технической точки зрения — безусловно. Но тогда пришлось бы на кристалле размещать еще один декодер для совместимости со старым 16-битным кодом. Кстати, интересно: возможность использования 32-битных инструкций в 16-битном режиме — это побочный эффект, или было такое требование при проектировании?
Или еще как вариант: отказаться от аппаратной поддержки 16-битного режима, но в БИОС встроить программный супервизор для эмуляции. Но тут тоже могли быть трудности, 80386 использовался не только в IBM AT c его БИОСом.

[netch80.livejournal.com]

> Кстати, интересно: возможность использования 32-битных инструкций в 16-битном режиме — это побочный эффект, или было такое требование при проектировании?

Я думаю, было, иначе было невозможно организовать даже включение 32-битного режима. И вообще, выполнять только часть операций в 32, остальные в 16 - это активно использовалось (например, была сборка MultiEdit для 386-го процессора, сильно быстрее обычной).

> Но тогда пришлось бы на кристалле размещать еще один декодер для совместимости со старым 16-битным кодом.

Для некоторых из этих переходов новый декодер можно было бы отложить. Например, реально не отменяя некоторые коды сразу в 386, а только когда они понадобятся. Аналогично с удлинением - если потребовать некоторый префикс только для 32, а реально поддерживать и для 16. В общем, захотели бы сделать с умом - сделали бы. Обидно именно то, что желания не было.

[netch80.livejournal.com]

> Но тогда пришлось бы на кристалле размещать еще один декодер для совместимости со старым 16-битным кодом.

Кстати, а ведь и так есть другой декодер. Потому что правила интерпретации mod-reg-r/m изменились полностью.
Блок разбора первого байта, по сравнению с ним и его последствиями, не такой и большой.

[dimich-dmb.livejournal.com]

Сейчас — да, но сейчас с технологией микрокодов плюс-минус еще один блок — не такая уж проблема.