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

Данная публикация основана на статье под названием "The Page-Fault Weird Machine: Lessons in Instruction-less Computation". Греет душу, что один из её соавторов, Sergey Bratus, давний выпускник Физтеха. Впервые я узнал о данной работе из заметки Gwern Barwen "Surprisingly Turing-Complete" , содержащей множество удивительных примеров Тьюринг-полных систем. Кстати, часть её переведена на Хабре, правда описываемому в данной статье явлению там отведено всего три предложения.

Оригинальная статья была опубликована в 2013 году, что может натолкнуть на вопрос об актуальности данного её пересказа в связи с завершившимся за эти годы переходом на x86-64, а следовательно отказом от защищённого режима исполнения в пользу long mode, в котором аппаратное переключение задач не поддерживается. Однако благодаря обратной совместимости архитектуры x86 излагаемая идея может быть реализована на современной аппаратуре и гипервизорах.

Продолжая тему актуальности, замечу, что первоисточник не претендовал на прямое практическое применение описанных в статье идей, а лишь приоткрыл завесу "странных вычислителей", обнаруживающихся в современных процессорах. Тем не менее, определённый полезный результат из этой работы следует напрямую: во-первых, запуск программы, которая нестандартным способом утилизирует крайние случаи, при этом полностью соответствуя спецификации отличный способ поиска ошибок в железе и гипервизорах (и немало было найдено в QEMU, по словам авторов). Во-вторых, так как обычные гипервизоры тестируются и ориентированы на наиболее распространённые операционные системы, результат исполнения в них подобной неординарной программы может отличаться от ожидаемого на голом железе. Данный феномен, позволяющий обнаружить факт исполнения под гипервизором, называется red pill, по аналогии с красной таблеткой, которая позволила Нео осознать виртуальность привычного ему мира. Число red pills является важной характеристикой гипервизора, так как многие вредоносные программы пользуются ими для определения уровня "осторожности", с которой нужно исполняться, чтобы не быть обнаруженными антивирусным ПО и системами отладки, которые обычно запускаются в безопасной среде. На самом деле тренд применения red pill в последние годы пошёл на спад, так как всё больше сервисов мигрируют в облако, где всё работает в виртуальной среде, и создатели вирусов не готовы пожертвовать этим "рынком" ради усложнения собственного анализа. И тем не менее, приведу несколько примеров вредоносного ПО, меняющего своё поведение при наличии гипервизора. Хотя часть его уже и ушла в прошлое, в своё время оно нанесло немало вреда. Среди таких программ: Neutrino(2016 г.), Conficker(2008 г.), Rebhip(2011 г.), IRC боты: Phatbot(2008 г.), Rbot, SDbot/Reptile, Mechbot, SpyBot и другие (ссылки ведут на упоминания об использовании ими методов проверки наличия виртуальной среды). В-третьих, нестандартные способы произведения вычислений открывают широкие просторы для обфускации. Особенно перспективной видится обфускация с помощью подобных "странных" вычислений в контексте unikernel.

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

Обработка исключений и аппаратное переключение задач

В архитектуре IA-32 существует функционал аппаратного переключения задач, предназначенный облегчить работу разработчикам операционных систем. Использованный вместе с механизмом call gates совершения системных вызовов, как предполагалось, он минимизирует затраты программистов на описание логики смены контекста. Но на сегодняшний день, насколько мне известно, всё это мёртвый кремний, давно заброшенный операционными системами в пользу более производительных программных решений; со стороны же производителей процессоров деоптимизированный до микрокода. А в x86-64 поддержка аппаратного переключения задач вообще отключена.

Единственный пример использования аппаратного переключения задач, с которым я сталкивался (и который, кстати, близок к описанному в работе), это использование в 32-bit Linux отдельной задачи (в терминах процессора) для обработки double fault, дословно, двойного исключения. Double fault возникает, если процессор столкнулся с ошибкой на этапе запуска или исполнения обработчика какого-то другого исключения или прерывания; например, в обработчике совершена попытка деления на ноль. Обычно, конечно, причиной double fault является не арифметика, а глубоко сломанное состояние процессора, именно поэтому системные таблицы, о которых пойдёт речь ниже, в Linux настроены так, что для обработки double fault используется отдельная задача, которая могла бы вывести в kernel panic "грязное" состояние основной задачи. Если же и в double fault возникает какая-то критическая ошибка, происходит triple fault, также известный как перезагрузка компьютера.

С каждой задачей в x86 ассоциировано состояние, хранящееся в task-state segment(TSS). Главным образом, в него сохраняются регистры процессора, подлежащие восстановлению при возобновлении исполнения задачи. Среди этих регистров нас будут особенно интересовать EIP (instruction pointer) указатель на текущую исполняемую инструкцию, ESP (stack pointer) указатель на вершину стека, CR3 указатель на таблицу страниц (строго говоря, page directory), а также регистры общего назначения EAX и ECX, о необходимости в которых чуть ниже.

Аппаратное переключение задач тесно связано с механизмами обработки прерываний, исключений, а также сегментацией памяти. Одними из важнейших таблиц, конфигурирующих работу процессора, являются GDT(Global Descriptor Table) глобальная таблица дескрипторов и IDT(Interrupt Descriptor Table) таблица дескрипторов прерываний. Опуская подробности, перечислю некоторые типы дескрипторов, которые могут в них располагаться: memory segment descriptor дескриптор сегмента памяти(кода, данных), TSS descriptor указатель на task-state segment, interrupt-gate descriptor указатель на дескриптор одного из первых двух типов, определяющий, как обрабатывать прерывание с переключением задачи или совершив far call. Неудивительно, что эти три головы гидры управление памятью, задачами и прерываниями неразлучны.

Тьюринг-полнота во всей красе

Это всё выглядит довольно сложно и, наверное, скрывает в себе вычислительную мощность, но откуда возникает Тьюринг-полнота? Дело в том, что при вызове обработчиков некоторых исключений, таких как page fault и double fault, в стек кладётся 4-байтный код ошибки. Сам код ошибки нам неинтересен, важен лишь побочный эффект, состоящий в уменьшении(не забываем, что стек в x86 растёт вниз) значения регистра ESP на 4. Но что произойдёт, если ESP на момент срабатывания прерывания уже равен нулю, то есть уменьшать его некуда? Было бы очень странно, если бы указатель на стек оборачивался вокруг 32 бит, поэтому в таких случаях срабатывает double fault-исключение.

Попробуем создать из описанных выше примитивов наш странный вычислитель. Для начала, так как никакие вычисления не будут производиться инструкциями процессора, присвоим регистру EIP во всех задачах недействительное значение, например, 0xFFFFFFFF. Это будет постоянно приводить к page fault, который срабатывает при ошибках доступа к памяти. Как мы уже выяснили, при попытке обработать page fault произойдёт нечто подобное:

if (esp == 0) {    goto double_fault_handler;} else {    esp -= 4;    goto page_fault_handler;}

Уже намечается какое-то уменьшение значения, ветвление Но для Тьюринг-полноты нам этого мало. Как уже можно догадаться, каждая "инструкция" нашего странного вычислителя будет исполняться побочными эффектами от срабатывания исключения. А так как одним из таких эффектов (согласно нашей конфигурации IDT и GDT) является загрузка в регистры содержимого очередной TSS, на момент обработки каждого исключения значение регистра CR3, отвечающего, как мы помним, за таблицу страниц, может быть своё(то, которое хранится в TSS, ассоциированного с данным исключением). И поскольку регистры IDTR и GDTR (не сохраняемые в TSS, а следовательно неизменные) хранят виртуальные адреса IDT и GDT, получается, что при исполнении очередной "инструкции" срабатывании исключения смене задачи загрузке нового значения CR3 смене таблицы страниц мы можем менять IDT и GDT, которые видит процессор. Вместе с IDT меняется и хранящийся в нём указатель на TSS, это также пригодится нам в дальнейшем.

Реализация movdbz-вычислителя

Получается, что исполнение "инструкции" состоит из следующих этапов:

1. Генерация исключения, которое выполнит следующую "инструкцию". Согласно конфигурации IDT и GDT, это приводит к смене задачи.

2. Загрузка TSS, ассоциированного со сгенерированным исключением, в регистровый файл. В частности, из TSS загружаются EIP, ESP, CR3.

3. В "стек" загруженной TSS кладётся код ошибки, а также (что более важно), если регистр ESP > 0, то из ESP вычитается 4, иначе ESP не изменяется.

4. Так как загрузка CR3 из шага 2 имела побочный эффект в виде смены таблицы страниц, результирующий ESP будет помещён в TSS, на который указывает ячейка в новом GDT (см. также Task Register) и который не обязан совпадать с исходным.

5. Если условие из пункта 3 оказалось истинным и вычитание было успешным, то произойдёт попытка исполнения инструкций процессора, что невозможно ввиду недействительного значения EIP, следовательно произойдёт переход на задачу, ассоциированную с исключением page fault; в противном случае следующей задачей будет ассоциированная с исключением double fault.

Запишем последовательность выше в виде псевдокода, в котором сразу введём некоторые обозначения: rsrc это ESP, подгруженный из исходной TSS; rdest это ESP, хранящийся в TSS, на которую указывает GDT после загрузки регистра CR3 из исходной TSS. label_zero задача, ассоциированная с исключением double fault, label_nonzero с исключением page fault. Также будем трактовать ESP как значение регистра нашего вычислителя, умноженное на 4, тогда из последнего на каждой обработке исключения будет вычитаться единица, а не четвёрка.

if (rsrc == 0) {    rdest = rsrc;    goto label_zero;} else {    rdest = rsrc - 1;    goto label_nonzero;}

Последовательность выше не что иное, как расшифровка инструкции movdbz, move-branch-if-zero-or-decrement (перемести-прыгни-если-ноль-или-уменьши). Как известно, инструкция subtract-and-branch-if-negative (вычти-и-прыгни-если-отрицательный-результат), которую несложно реализовать через вышеупомянутую movdbz(это строго показано в оригинальной статье), позволяет построить Тьюринг-полный вычислитель. Дочитавшим до сюда также, наверное, будет интересно узнать про более экзотическое доказательство это компилятор Тьюринг-полного Brainfuck в набор инструкций movdbz-вычислителя.

Итак, наша инструкция movdbz имеет четыре аргумента:

movdbz rdest, rsrc, label_nonzero, label_zero

В качестве упражнения для читателя остаётся написание с использованием одной только этой инструкции игры Жизнь Джона Конвея (коронавирус забирает лучших), использованной в демо авторов оригинальной статьи. На movdbz нужно написать именно логику эволюции ячеек, для вывода содержимого кадрового буфера на экран авторы используют реальные инструкции x86. Поэтому утверждение про недействительное значение EIP выполняется в их демо не во всех TSS.

Сопротивление архитектуры

В real-mode с его A20 и high memory, когда стрельба себе в ногу входила в стандартный арсенал программиста, можно было много всего себе позволить. Но времена изменились, и в защищённом режиме Intel создали некоторые препоны насилию нам своими чипами, которые, в частности, мешают нам развлекаться со своими странными вычислителями. Например, ESP должен указывать внутрь выделенного под стек участка памяти(иначе мы получим исключение #SS stack-segment fault), поэтому нужно пометить первую страницу памяти в каждой таблице страниц как содержащую стек. И так как в ESP хранится значение, в 4 раза большее содержимого "регистра" нашего вычислителя, последний может принимать значения от 0 до 1023, а не от 0 до 4095 (используется 4 КиБ страница). Но подобные мелочи мне кажутся довольно скучными, поэтому далее я поговорю только о тех препятствиях, методы борьбы с которыми мне показались интересными.

Данные отдельно, кодлеты отдельно

Одной из незамеченных в вышеприведённых рассуждениях оказалась следующая проблема: в пункте 4 из списка выше в "destination TSS" записывается не только ESP, но и CR3. Хорошо подумав, можно осознать, что ESP, хранящиеся в разных TSS, -- это регистры нашего вычислителя, и их значения не должны быть привязаны инструкциям. А CR3 как раз отвечает за то, какая инструкция сейчас исполняется, ведь от CR3 зависит содержимое IDT, а значит и то, какие инструкции исполнятся следующими то есть он определяет положение текущей инструкции в "программе". В связи с этим мы хотим разделить TSS на две части отвечающую за инструкции, которые исполнятся следующими; и содержающую регистр, с которым оперирует текущий movdbz. Поэтому мы "рассекаем" TSS границей страницы между регистрами ECX и EDX(сейчас стоит обратиться к картинке с содержимым TSS выше). Таким образом, так как в верхней части TSS из полезных для нашего вычислителя данных остаётся только ESP, основным смыслом трюка с CR3 становится переотбражение в верхнюю часть TSS физической страницы c rdest, куда будет записан результат исполнения инструкции.

Busy bit

Также крайне находчивым мне показался способ обхода помехи busy bit, встроенного в указатель на TSS в GDT и определяющего, находится ли сейчас процессор в состоянии обработки исключения. Если этот бит выставлен, архитетура запрещает переключение задач, что делает невозможным пункт 5 из описания выше. Этот бит автоматически выставляется при срабатывании исключения и, при обычном исполнении, очищается при выходе из обработчика. Но у нас нет обработчика, мы не исполняем инструкций процессора, поэтому нужно найти другой способ очищать этот бит. Будет нелишним заметить, что, по словам автора, на то, чтобы дойти до этой идеи и реализовать её, у него ушло 8 недель из 10, затраченных на весь проект.

Решение этой проблемы следующее: расположим GDT так, чтобы она перекрывалась с TSS! GDT может занимать максимум 16 страниц, последние 8 байт каждой из этих страниц это, как мы помним, вследствие рассечения TSS, регистры EAX и ECX. Хак состоит в том, чтобы заранее в каждой TSS положить на место регистров EAX и ECX этот самый указатель на TSS (строго говоря, дескриптор TSS) с очищенным busy bit-ом. Таким образом, при каждой выгрузке TSS из регистрового файла на 4 шаге busy bit в дескрипторе текущей TSS в GDT будет выставляться в ноль. Осталось только записать в IDT указатели на правильные дескрипторы в GDT те, которые занимают последние 8 байт в каждой из 16 страниц.

Заключение

Каков же смысл во всех этих исхищрениях, в построении такого "странного вычислителя"? Во-первых, у описанных выше идей есть прямое, хотя и не столь актуальное, практическое применение создание red pill, позволяющей отличить голое железо от гипервизора. Во-вторых, такое неортодоксальное применение архитектуры x86, выискивание тёмных уголков и крайних случаев может доставить неподдельное удовольствие любителям эзотерического программирования. В-третьих, данная работа несёт, на мой взгляд, глубокую философскую идею, подчёркивая ценность хакерского склада ума применительно к нахождению "странных вычислителей" там, где они не подразумевались или где их не видят другие. Ведь любой эксплойт по сути плод мастерского программирования "странной виртуальной машины", своеобразным "байткодом" которой являются баги, фичи и различные неожиданные пути исполнения целевой платформы. Кстати, тентакли макаронного монстра на обложке как раз и олицетворяют всевозможные особенности и изъяны, обнажаемые программными и аппаратными системами и с охотой используемые разработчиками эксплойтов для нарушения задумываемого хода работы программы.

Основные источники(в рекомендуемом порядке ознакомления):

• Запись одного из выступлений авторов оригинальной публикации на Youtube

• Имплементация Krister Walfridsson: репозиторий на Github, общее описание, немного деталей реализации

• Оригинальная статья "The Page-Fault Weird Machine: Lessons in Instruction-less Computation", сопутствующий репозиторий на Github с авторской реализацией

• Конечно, Intel 64 and IA-32 Architectures Software Developer Manuals

Оригинал текста Июнь 10, 2021 - 38 минут чтения

Программное обеспечение полно своих зависимостей, если смотреть достаточно глубоко. Компиляторы, написанные на языке, на котором они компилируются, - самый очевидный, но не единственный пример. Чтобы скомпилировать ядро, нам нужно работающее ядро. Линкеры, системы сборки, оболочки. Даже текстовые редакторы, если вы хотите писать код, а не просто загружать его. Как разорвать этот цикл?1 С тех пор как проблема начальной загрузки впервые привлекла мое внимание, я стал интересоваться этой уникальной областью программной инженерии. Не из страха, что кто-то попытается реализовать атаку на доверие, а просто как интересный вызов.

11 лет назад vanjos72 описал на Reddit то, что он называет мысленным экспериментом: что если бы вас заперли в комнате с IBM PC, на котором нет операционной системы? Какое минимальное количество программного обеспечения вам понадобилось бы для начала, чтобы вернуться к комфортной работе?

Так получилось, что в последнее время у меня появилось много свободного времени, поэтому я решил сделать это больше, чем просто мысленный эксперимент. Увы, мой компьютер не был оснащен переключателями на передней панели, поэтому некоторые программы должны уже присутствовать на компьютере ...

Самым минимальным вариантом может быть простая программа, которая принимает ввод с клавиатуры, а затем переходит на нее. Поскольку подпрограммы ввода с клавиатуры в BIOS реализуют escape-коды alt+numpad, вам даже не нужно писать код преобразования базы.2Более того, циклу даже не нужно условие завершения а просто пишите в буфер обратно, пока не столкнетесь с существующим кодом и не перезапишете точку перехода. Такой подход занимает всего 14 байт:

6a00    push word 007      pop esfd      stdbf1e7c  mov di, buffer+16 ; Adjust to taste. Beware of fenceposting.        input_loop:b400    mov ah, 0cd16    int 0x16aa      stosbebf9    jmp short input_loop        buffer:

Однако перспектива вводить код таким образом не кажется мне привлекательной. Я решил, что, поскольку BIOS в любом случае загружает целый сектор, любая загрузочная программа, которая помещается в бутсектор, является честной игрой.3Очевидно, что хочется максимизировать полезность выбранной программы. Какую самую мощную вещь мы можем уместить в 510 байт?

Оскар Толедо написал много интересных программ размером с сектор. Среди них много игр, таких как DooM-подобная игра или шахматный ИИ, а также базовый интерпретатор BASIC, но самой, пожалуй, актуальной для нашего случая является bootOS:

bootOS - это монолитная операционная система, которая помещается в одном загрузочном секторе. Она способна загружать, выполнять и сохранять программы. Также имеет файловую систему.

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

Я бы искал решение, которое минимизирует набор текста в машинном коде ручной сборки. В идеале это должен быть язык программирования, но такой, который, в отличие от BASIC, может быть расширен во время выполнения. Если вы прочитали заголовок этого поста, то уже знаете, на чем я остановился. Оказалось, что в бутсекторе можно разместить примитивный FORTH. Код можно посмотреть врепозитории Miniforth на GitHub, но я приведу большую его часть здесь.

Весь FORTH занимает на данный момент 504 байта. Как и следовало ожидать, процесс разработки включал в себя постоянный поиск возможностей экономии байтов. Однако, когда я опубликовал, как мне казалось, достаточно плотно оптимизированный код, появилсяИлья Курдюков и нашел 24 байта, которые можно сэкономить! Я быстро реинвестировал это сэкономленное место в новые возможности.

Вводная экскурсия в FORTH

Если вы когда-либо писали что-либо на FORTH, вы можете смело пропустить этот раздел.

FORTH - это язык, основанный на стеках. Например, число вталкивает свое значение в стек, а слово + выталкивает два числа и их сумму. Обычная утилита отладки, но не включенная в Miniforth, - это слово .s, которое печатает содержимое стека.

1 2 3 + .s  <enter><2> 1 5 ok

Примечание: ok - готовность системы к приёму слов языка

Пользователь может определять свои собственные слова с помощью : и ;. Например:

 : double dup + ; <enter>ok  3 double  .  <enter>6 ок

Это определяет слово double, которое делает то же самое, что и dup +. dup, кстати, является одним из слов FORTH для работы со стеком. Оно дублирует верхний элемент в стеке:

42 dup .s <enter><2> 42 42 ok

Это практически весь язык. Есть некоторые стандартные средства для условий и циклов, но нам пока не нужно ими заниматься, так как они могут быть построены поверх Miniforth позже.

Чтобы описать влияние слова на состояние стека, мы используем следующую нотацию:

dup ( a -- a a ) swap ( a b -- b a )

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

Шитый код

Хотя некоторые системы FORTH включают в себя полноценные оптимизирующие компиляторы, подобные тем, которые можно увидеть в обычном языке программирования, существует гораздо более простая стратегия. В конце концов, все, что может сделать слово в FORTH, это выполнить другие слова, так что последовательность инструкций вызова очень близка к этому:

DOUBLE:    call DUP    call PLUS    ret

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

DOUBLE:    dw DUP    dw PLUS

Это реализуется следующим образом: каждое примитивное слово извлекает из памяти адрес следующего слова и переходит к нему. Указатель на эту последовательность указателей хранится в SI, так что инструкция lodsw позволяет легко обрабатывать этот список:

DUP:    pop ax    push ax    push ax    lodsw    jmp axPLUS:    pop ax    pop bx     add ax, bx    push ax    lodsw    jmp ax

Этот общий код можно абстрагировать в макрос, который традиционно называется NEXT:

%macro NEXT 0    lodsw    jmp ax%endmacro

Этот механизм, кстати, известен как потоковый код. Никакой связи с примитивом параллелизма.

Однако что произойдет, если одно скомпилированное слово вызовет другое? Здесь в дело вступает стек возвратов. Может показаться естественным использовать регистр BP для указателя стека. Однако в 16-битных x86 не существует режима адресации [bp]. Самый близкий к нему - [bp+imm8], что означает, что при обращении к памяти по адресу bp тратится байт, чтобы указать, что вам не нужно смещение. Вот почему я использую регистр di для стека возврата вместо этого. В целом, этот выбор экономит 4 байта.

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

DOUBLE:    call DOCOL    dw DUP    dw PLUS    dw EXITDOCOL:            ; сокращение от "do colon word".    xchg ax, si ; используется здесь как  mov ax, si ,              ;   но меняет местами.                ; ax - только один байт, а  mov  - два байта.    stosw    pop si ; захватить указатель, вытолкнутый  call .    NEXTEXIT:    dec di    dec di    mov si, [di]    NEXT

Это практически та же стратегия выполнения, что и в Miniforth, с одним простым, но существенным улучшением - значение на вершине стека хранится в регистре BX. Это позволяет пропустить push и pop во многих примитивах:

PLUS:    pop ax    add bx, ax    NEXTDROP:    pop bx    NEXTDUP:      push  bx       NEXT

Однако один случай все еще остается нерешенным. Что произойдет, если слово содержит число, например : DOUBLE 2 \ ;? С этим справляется LIT, который извлекает литерал, следующий за ним, из потока указателей:

DOUBLE:      call DOCOL      dw LIT, 2      dw MULT      dw EXITLIT:      push  bx       lodsw      xchg  bx ,  ax       NEXT

Словарь

FORTH нужен способ найти реализацию слов, которые набирает пользователь. Это роль словаря. Я использую структуру, подобную многим другим небольшим FORTH - односвязный список заголовков слов, непосредственно предваряющий код каждого слова. По традиции, глава списка хранится в переменной LATEST.

В старших битах поля длины имени также хранятся некоторые флаги:

F_IMMEDIATE equ 0x80F_HIDDEN    equ 0x40F_LENMASK   equ 0x1f

Если слово помечено как IMMEDIATE, оно будет выполнено немедленно, даже если в данный момент мы составляем определение. Например, это используется для реализации ;. Если слово помечено как HIDDEN, оно игнорируется при поиске по словарю. Помимо использования в качестве элементарного механизма инкапсуляции, это может быть использовано для реализации традиционной семантики FORTH, когда определение слова может ссылаться на предыдущее слово с тем же именем (а RECURSE используется, когда вам нужно определение, которое компилируется в данный момент). Однако, ближе к концу разработки я удалил код, который действительно делает это, из стандартной реализации : и ;.

Компрессия

Обычно не стоит использовать сжатие, когда и расжатие , и его полезная нагрузка должны уместиться всего в 512 байт. Однако в реализации FORTH есть одна вещь, которая повторяется очень часто, - это реализация NEXT.

ad      lodswffe0    jmp  ax 

Мы можем попытаться сэкономить несколько байт, заменив их переходами к общей копии. Однако короткий переход все равно занимает два байта, что не является существенной экономией. Как выясняется, специальная схема сжатия, которая может обрабатывать только этот один повторяющийся паттерн, стоит того, если совместить ее со следующим наблюдением: За NEXT почти всегда следует словарная статья следующего примитива, поле ссылки которого предсказуемо.

Я выбрал схему сжатия, в которой каждый байт 0xff заменяется на NEXT, за которым следует поле ссылки, которое вычисляется на основе предыдущего появления байта 0xff. Эта стратегия сэкономила 19 байт, когда я ее внедрил.4

Сначала я использовал для этого байт 0x90, в конце концов, это опкод nop, который я точно не буду использовать. Однако этот байт все еще может встречаться в непосредственном байте инструкции. Сначала это не было проблемой, но когда код перемещался в памяти, различные адреса и смещения становились 0x90 достаточно часто, чтобы стать неприятностью. У 0xff, похоже, такой проблемы нет.

Чтобы создать ссылку, мы копируем значение LATEST на выход декомпрессора и обновляем LATEST, чтобы оно указывало на слово, которое мы только что написали. Это может быть сделано очень компактной последовательностью инструкций, но все равно занимает достаточно байт, чтобы стоило оформить это в виде подпрограммы. Она также используется в реализации :, которая создает словарные статьи во время выполнения.

; Создает ссылку словарного связного списка в DI.MakeLink:      mov  ax ,  di       xchg [LATEST],  ax    ; AX теперь указывает на старую запись,                   ; а LATEST и DI указывают на новую.      stosw      ret

В декомпрессоре использовался интересный прием, когда вместо короткого перехода вперед опкод размещается так, что непосредственный аргумент, который он требует, съедает инструкцию, через которую мы хотим перейти. То есть, вместо

     jmp short .after.write:      stosb.after:пишим3c      db 0x3c ; пропустить stosb ниже, сравнив его опкод с AL       .write:aa      stosb

Таким образом, если какой-то другой код переходит к .write, выполняется stosb, но этот кодовый путь просто выполняет cmp al, 0xaa. Сначала я не подумал об инструкции cmp al, и вместо нее использовал mov в отбрасываемый регистр. Это привело кэффектному отказуиз-за моей неспособности выбрать регистр, который можно безопасно перезаписать.

Илья Курдюков затем продемонстрировал , что тот же самый байткоунт может быть достигнут без подобной "магии". Аналогичная модификация позволила мне устранить и другое проявление этого трюка. Суть в том, что вместо того, чтобы пытаться пропустить stosb, мы выполняем его безоговорочно перед ветвлением кодовых путей, а затем, по сути, отменяем его с помощью dec di, если это необходимо:

SPECIAL_BYTE equ 0xff      mov  si , CompressedData      mov  di , CompressedBegin      mov  cx , COMPRESSED_SIZE.decompress:      lodsb      stosb      cmp  al , SPECIAL_BYTE      jnz short .not_special      dec  di       mov  ax , 0xffad ; lodsw / jmp ax      stosw      mov  al , 0xe0      stosb      call MakeLink.not_special:      loop .decompress

На самом деле генерация сжатого потока более сложна. Поскольку я хочу, чтобы переходы между сжатой и несжатой частями работали, ассемблеру нужно верить, что он пишет код в том месте, где он будет выполняться на самом деле. Сначала я попытался сделать это, корректируя org после каждого SPECIAL_BYTE, но, к сожалению, yasm это не понравилось.

boot.s:137: error: program origin redefined

Очевидно, что необходим отдельный этап постобработки. Я написал макрос для подгонки байтов, которые будет вставлять декомпрессор:

%macro compression_sentinel 0      db SPECIAL_BYTE      dd 0xdeadbeef%endmacro

Это имеет дополнительное преимущество, предoставляя простой автоматизированный способ проверки того, что никакие SPECIAL_BYTE не проскочили случайно.

Мне все еще нужно было выделить место для сжатых данных. Я выбрал следующую схему:

\1. Несжатый код начинается с 7C00 - инициализация, декомпрессия и внешний интерпретатор.

\2. Сжатые данные немедленно следуют за ним, заполняя бутсектор вплоть до момента перед 7E00.

\3. Сразу после этого выделяется буфер декомпрессии, в который yasm выводит содержимое цели.

Чтобы добиться этого, мне нужно было точно знать, сколько места нужно выделить для сжатых данных. Сначала я подсчитал точное количество сэкономленных байт, увеличив счетчик в макросе compression_sentinel:

%assign savings 0%macro compression_sentinel 0%assign savings savings+4      db SPECIAL_BYTE      dd 0xdeadbeef%endmacro

Затем я просто вычитаю это значение из размера несжатого сегмента:

CompressedData:      times COMPRESSED_SIZE db 0xccCompressedBegin:; ...CompressedEnd:COMPRESSED_SIZE equ CompressedEnd - CompressedBegin - savings

Постобработка выполняется простым скриптом Python:

SPECIAL_BYTE =  b'\xff'SENTINEL = SPECIAL_BYTE +  b '\xef\xbe\xad\xde'with open('raw.bin', 'rb') as f:      data = f.read()output_offset = data.index( b '\xcc' \  20)chunks = data[output_offset:].lstrip( b '\xcc').split(SENTINEL)assert SPECIAL_BYTE not in chunks[0]compressed =  bytearray (chunks[0])for chunk in chunks[1:]:      assert SPECIAL_BYTE not in chunk      compressed.extend(SPECIAL_BYTE)      compressed.extend(chunk)\# Убедитесь, что для сжатых данных выделено именно то место, которое нужно.\# для сжатых данных.assert  b '\xcc' \  len(compressed) in dataassert  b '\xcc' \  (len(compressed) + 1) not in dataoutput = data[:output_offset] + compressedprint(len(output), 'bytes used')output +=  b '\x00' \  (510 - len(output))output +=  b '\x55\xaa'with open('boot.bin', 'wb') as f:      f.write(output)

Этот же сценарий также генерирует расширенный образ диска, который содержит некоторый код для тестирования в блоке 1:

output +=  b '\x00' \  512output += open('test.fth', 'rb').read().replace( b '\n',  b ' ')output +=  b ' ' \  (2048 - len(output))with open('test.img', 'wb') as f:      f.write(output)

compression_sentinel чаще всего используется макросом defcode, который создает словарную статью для примитивного слова. Он принимает метку (которая затем может быть использована для перехода к реализации некоторого слова), имя слова в виде строки и, по желанию, некоторые флаги, которые должны быть включены в поле длины:

; defcode PLUS, "+"; defcode SEMI, ";", F_IMMEDIATE%macro defcode 2-3 0      compression_sentinel%strlen namelength %2      db %3 | namelength, %2%1:%endmacro

Затем это используется для определения примитивов. Код, по сути, переходит в defcode:

defcode PLUS, "+"      pop  ax       add  bx ,  ax defcode MINUS, "-"      pop  ax       sub  ax ,  bx       xchg  bx ,  ax defcode PEEK, "@"      ; ...

Однако DOCOL, EXIT и LIT также используют механизм сжатия для своих NEXT. Поскольку поле ссылки все еще записывается, это создает фиктивные словарные статьи. К счастью, первый опкод EXIT и LIT имеет установленный бит F_HIDDEN, так что это не проблема:

CompressedBegin:

DOCOL:      xchg  ax ,  si       stosw      pop  si  ; grab the pointer pushed by  call       compression_sentinelLIT:      push  bx       lodsw      xchg  bx ,  ax       compression_sentinelEXIT:      dec  di       dec  di       mov  si , [ di ]defcode PLUS, "+"      ; ...

Переменные?

Инструкции немедленной загрузки имеют тенденцию иметь более короткие кодировки, чем загрузки из памяти:

be3412    mov  si , 0x12348b363412  mov  si , [0x1234]

Именно поэтому Miniforth хранит большинство своих переменных в непосредственных полях инструкций. Конечно, это означает, что адрес этих переменных будет меняться при каждом редактировании кода, что проблематично, поскольку мы захотим получить доступ к этим переменным в коде FORTH. Типичный способ доступа к переменной - это создание слова, которое передает ее адрес. Однако это слишком дорого при наших ограничениях. То, на чем я остановился, это заталкивание адресов в стек при запуске. Это можно сделать, используя всего 2 байта для каждого адреса, просто определив начальное содержимое стека как данные:

      org 0x7c00      jmp 0:startstack:      dw HERE      dw BASE      dw STATE      dw LATESTstart:      ; ...      mov  sp , stack

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

Код инициализации

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

      jmp 0:start      ; ...start:      push  cs       push  cs       push  cs       pop  ds       pop  es       pop  ss       mov  sp , stack      cld

В этом коде есть два примечательных момента. Во-первых, сегментные регистры устанавливаются через стек. Это трюк экономии байтов, который я перенял из bootBASIC он позволяет инициализировать регистр общего назначения нулем:

31c0    xor  ax ,  ax   ; through AX - 8 bytes8ed8    mov  ds ,  ax 8ec0    mov  es ,  ax 8ed0    mov  ss ,  ax 0e      push  cs      ; through the stack - 6 bytes0e      push  cs 0e      push  cs 1f      pop  ds 07      pop  es 17      pop  ss 

Во-вторых, можно подумать, что во время перенаправления стека возникает небольшое окно состояния гонки и если прерывание произошло между pop ss и mov sp, то может возникнуть хаос, если предыдущее значение SP окажется в неудачном месте памяти. Конечно, я мог бы просто скрестить пальцы и надеяться, что этого не произойдет, если бы 2 байта, необходимые для обертывания этого в пару cli/sti, были слишком большими. Однако оказалось, что этот компромисс не нужен благодаря одному неясному уголку архитектуры x86. Процитируем том 2B Руководства разработчика программного обеспечения x86:

Загрузка регистра SS инструкцией POP5 подавляет или блокирует некоторые отладочные исключения и блокирует прерывания на границе следующей инструкции. (Запрет заканчивается после доставки исключения или выполнения следующей инструкции). Такое поведение позволяет загрузить указатель стека в регистр ESP со следующей инструкцией (POP ESP)6 ,прежде чем может быть доставлено событие.

После установки сегментов, стека и флага направления запускается декомпрессор. Очень важно, что он не использует регистр DL, который содержит номер диска BIOS, с которого мы загрузились. Затем он пихается в реализацию load (которая находится в сжатом сегменте) и заталкивается в стек для последующего использования пользовательским кодом:

      mov [DRIVE_NUMBER],  dl       push  dx  ; for FORTH code

Внешний интерпретатор

На этом этапе мы достигаем внешнего интерпретатора - части системы FORTH, которая обрабатывает пользовательский ввод. Название "внешний интерпретатор" отличает его от внутреннего интерпретатора, который является компонентом, координирующим выполнение в пределах определенного слова, и состоит из NEXT, DOCOL, EXIT и LIT.

Обычно FORTH представляет строительные блоки своего внешнего интерпретатора в виде слов в словаре, таких как

• REFILL (считывание строки ввода из текущего выполняющегося источника),

  • WORD (разбор слова из входного потока),

  • FIND (искать слово в словаре),

  • NUMBER (преобразование строки в число).

В Miniforth этой практике вообще не уделяется никакого внимания. Заголовки словарей стоят байты, как и общение только через стек. Фактически, WORD и >NUMBER объединяются в одну процедуру, которая выполняет работу обеих. Таким образом, цикл может быть общим, что экономит байты.

Эта монолитная архитектура также позволяет нам решить, что BX и DI не резервируются для вершины стека и указателя стека возврата, соответственно, во время выполнения внешнего интерпретатора. Это значительно помогает справиться с регистровым голоданием в этих сравнительно сложных частях системы. Эти регистры устанавливаются непосредственно перед переходом к слову и сохраняются после возврата.

Ввод с клавиатуры

После завершения инициализации код переходит к ReadLine, процедуре для чтения строки ввода с клавиатуры. Мы также вернемся сюда позже, когда текущая строка ввода будет исчерпана. Буфер ввода находится по адресу 0x500, сразу послеBDA. Хотя идиоматический формат строк для FORTH использует отдельное поле длины, этот буфер NULL-терминирован, так как это легче обрабатывать при разборе. Указатель на неразобранный фрагмент ввода хранится в InputPtr, которая является единственной переменной, не использующей технику самомодификации, так как ее не нужно явно инициализировать и она естественным образом записывается до чтения.

InputBuf equ 0x500 InputPtr equ 0xa02 ; dw

ReadLine:      mov  di , InputBuf      mov [InputPtr],  di .loop:      mov  ah , 0      int 0x16      cmp  al , 0x0d      je short .enter      stosb      cmp  al , 0x08      jne short .write      dec  di       cmp  di , InputBuf ; underflow check      je short .loop      dec  di .write:      call PutChar      jmp short .loop.enter:      call PutChar      mov  al , 0x0a      int 0x10      xchg  ax ,  bx  ; write the null terminator by using the BX = 0 from PutChar      stosbInterpreterLoop:      call ParseWord ; returns length in CX. Zero implies no more input.      jcxz short ReadLine

Прерывание BIOS для получения символа с клавиатуры не печатает клавишу и мы должны сделать это сами. Это делается с помощью функции "TELETYPE OUTPUT", которая уже обрабатывает специальные символы, такие как backspace или newline.

PutChar:      xor  bx ,  bx       mov  ah , 0x0e      int 0x10      ret

У этой функции есть свои недостатки. Например, необходимы "грязные" символы окончания строки CRLF (CR для перемещения курсора в начало строки и LF для перемещения на следующую строку). Кроме того, символ backspace только перемещает курсор на один символ назад, но не стирает его. Чтобы получить поведение, которого мы ожидаем, необходимо напечатать \b \b (справедливости ради, это также происходит на современных терминалах). Я решил это пропустить.

Наконец, в "Списке прерываний" Ральфа Браунаупоминается, что некоторые BIOS сбрасывают BP, когда печатаемый символ вызывает прокрутку экрана. Это нас не касается, так как мы вообще не используем этот регистр.

Парсинг

После того как мы прочитали строку, нам нужно разобрать ее на слова. Это делается по требованию и каждое слово выполняется (или компилируется, в зависимости от состояния), как только оно разобрано. Помимо цикла интерпретатора, ParseWord также вызывается реализацией : (для получения имени определяемого слова).

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

Для начала мы пропускаем все пробельные символы во входном буфере:

; returns; DX = pointer to string; CX = string length; BX = numeric value; clobbers SI and BPParseWord:      mov  si , [InputPtr]      ; repe scasb вероятно, сохранит некоторые байты здесь, если бы реестры были разработаны - SCASB  ; использует DI вместо SI :( - scasb      ; uses DI instead of SI :(.skiploop:      mov  dx ,  si  ; Если мы выйдем на петлю в этой итерации, DX укажет первую букву слова      lodsb      cmp  al , " "      je short .skiploop

Обратите внимание на то, как сохраняется указатель на начало строки. Цикл проходит на один байт дальше пробела, поэтому сохранение указателя после цикла потребовало бы отдельного декремента. Вместо этого мы обновляем регистр при каждой итерации цикла, но до того, как указатель увеличивается на lodsb.

В этот момент регистр AL загружен первым символом слова. Таким образом, наш следующий цикл должен будет выполнить lodsb в своем конце.

      xor  cx ,  cx       xor  bx ,  bx .takeloop:      and  al , ~0x20      jz short Return ; jump to a borrowed  ret  from some other routine

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

Если мы не обнаружили конец слова, мы увеличиваем счетчик длины и преобразуем цифру в ее числовое значение:

      inc  cx       sub  al , "0" &~0x20      cmp  al , 9      jbe .digit_ok      sub  al , "A" - ("0" &~0x20) - 10.digit_ok      cbw

cbw - это малоизвестная инструкция, которая преобразует знаковое число из байта в слово, но для нас это просто более короткое mov ah, 0. Возможно, аналогичным образом мы используем знаковое умножение imul, потому что у него больше возможностей для использования регистров, чем у беззнакового mul. Используемая здесь форма позволяет умножать на непосредственное значение и не перезаписывать в DX верхнюю половину произведения.7

Эта конкретная инструкция должна быть закодирована вручную, чтобы ширина литерала составляла 2 байта.8

      ; imul bx, bx, <BASE> но yasm настаивает на кодировании непосредственного в один байт...       db 0x69, 0xdbBASE equ $      dw 16      add  bx ,  ax  ; add the new digit

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

      mov [InputPtr],  si       lodsb      jmp short .takeloop

Поиск по словарю

После того как слово разобрано, мы пытаемся найти его в словаре. Для каждой записи нам нужно сравнить длину имени, а если она совпадает, то и само имя. Включая F_HIDDEN в маску, мы автоматически обрабатываем и скрытые записи. То, как мы сравниваем длину, может выглядеть немного странно. Цель состоит в том, чтобы сохранить бит F_IMMEDIATE в AL, чтобы нам не пришлось держать рядом указатель на заголовок этого слова. Это одна из умных оптимизаций Ильи Курдюкова.

    InterpreterLoop:          call ParseWord          jcxz short ReadLine        ; Пытаемся найти слово в словаре..    ; SI = указатель словаря    ; DX = указатель строки    ; CX = длина строки    ; Следим за сохранением BX, в котором хранится числовое значение    LATEST equ $+1          mov  si , 0    .find:          lodsw          push  ax  ; сохранить указатель на следующую запись          lodsb          xor  al ,  cl  ; если длина совпадает, то AL содержит только флаги          test  al , F_HIDDEN | F_LENMASK          jnz short .next              mov  di ,  dx           push  cx           repe cmpsb          pop  cx           je short .found    .next:          pop  si           or  si ,  si           jnz short .find              ; Если мы дойдем до этой точки, то это будет число.          ; ....found:      pop  bx  ; отбрасываем указатель на следующую запись      ; Когда мы дойдем до этого места, SI указывает на код слова, а AL содержит ; флаг F_IMMEDIATE

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

Должны ли мы его выполнить?

Система может находиться в двух возможных состояниях:

• интерпретация - все слова должны быть выполнены

• компиляция - непосредственные слова должны быть выполнены

Другими словами, слово должно быть выполнено, если оно немедленное, или мы его интерпретируем. Мы храним этот флаг в поле immediate инструкции or, так как при компиляции он будет установлен в 0:

      ; Когда мы сюда попадаем, SI указывает на код слова, а AL содержит ; флаг F_IMMEDIATE STATESTATE equ $+1      or  al , 1      xchg  ax ,  si  ;  оба кодовых пути должны иметь указатель в AX      jz short .compile      ; Выполняем слово      ; ...

Наиболее важными словами, которые должны изменить состояние, являются : и ;, но они просто переходят в [ и ] слова, которые позволяют временно вернуться в интерпретируемый режим при компиляции слова. Типичный случай использования - вычисление значения постоянного выражения:

 : third-foo [ foos 3 cells + ] literal @ ;

Поскольку два значения STATE отличаются только на 1, мы можем переключаться между ними с помощью inc и dec. Это имеет тот недостаток, что они больше не являются идемпотентными, но это не должно иметь значения для хорошо написанного кода:

defcode LBRACK, "[", F_IMMEDIATE      inc byte[STATE]defcode RBRACK, "]"      dec byte[STATE]

Выполнение слова

Если мы решили выполнить слово, мы извлекаем BX и DI, и настраиваем SI так, чтобы NEXT перешел обратно к .executed:

; Выполнение слова RetSP RetSP equ $+1      mov  di , RS0      pop  bx       mov  si , .return      jmp  ax .return:      dw .executed.executed:      mov [RetSP],  di       push  bx       jmp short InterpreterLoop

Обработка чисел

Для чисел нет флага F_IMMEDIATE, поэтому для принятия решения нам нужно просто проверить состояние. Это простое сравнение, но если мы будем достаточно умны, здесь можно сэкономить байт. Давайте снова посмотрим на код, который выполняет поиск в словаре. Какое значение будет иметь AH, когда мы дойдем до регистра чисел?

.find:      lodsw      push  ax  ;  сохранить указатель на следующую запись      lodsb      xor  al ,  cl  ; если длина совпадает, то AL содержит только флаги      test  al , F_HIDDEN | F_LENMASK      jnz short .next      mov  di ,  dx       push  cx       repe cmpsb      pop  cx       je short .found.next:      pop  si       or  si ,  si       jnz short .find      ; AH = ?

Видите ли вы это? В этот момент AH равен нулю, так как содержит старшую половину указателя на следующее слово, которое, как мы знаем, является NULL, поскольку мы только что добрались до конца списка. Это позволяет нам проверить значение STATE, не загружая его в регистр или какие-либо непосредственные байты:

      ; Это число. Вставьте его значение - мы выкинем его позже, если окажется, что нужно скомпилировать ; его вместо этого.       push  bx       cmp byte[STATE],  ah       jnz short InterpreterLoop      ; Иначе скомпилируйте литерал. ; ...

Компиляция вещей

Указатель точки процесса компиляции называется HERE. Он начинается сразу после распакованных данных. Функция, которая выписывает слово в эту область, называется COMMA, так как слово FORTH, которое это делает, - ,.

COMMA:HERE equ $+1      mov [CompressedEnd],  ax       add word[HERE], 2      ret

Он используется в прямом смысле для составления как чисел, так и слов. Мы можем разделить хвост, хотя составлении слова он будет перескакивать на середину составления числа:

      ; Иначе, компилируем литерал.       mov  ax , LIT      call COMMA      pop  ax .compile:      call COMMA      jmp short InterpreterLoop

Последним кусочком головоломки являются : и ;. Давайте сначала рассмотрим :. Поскольку ParseWord использует BX и SI, нам нужно сохранить эти регистры. Более того, поскольку мы пишем множество частей заголовка словаря, мы загрузим HERE в DI, чтобы упростить работу. Это большое количество регистров, которые нам нужно переместить. Однако на самом деле нам не нужно изменять ни один регистр, поэтому мы можем просто сохранить все регистры с помощью pusha.

defcode COLON, ":"      pusha      mov  di , [HERE]      call MakeLink    ; link field      call ParseWord      mov  ax ,  cx       stosb            ; length field      mov  si ,  dx       rep movsb        ; name field      mov  al , 0xe8     ; call      stosb   ; поле длины mov si, dx rep movsb ; поле имени mov al, 0xe8 ; вызов stosb ; Смещение определяется как (цель вызова) - (ip после инструкции вызова) ; Получается DOCOL - (di + 2) = DOCOL - 2 - di      mov  ax , DOCOL - 2      sub  ax ,  di       stosw      mov [HERE],  di       popa      jmp short RBRACK ; enter compilation mode   ; войти в режим компиляции

; гораздо короче. Нам просто нужно скомпилировать EXIT и вернуться в режим интерпретации:

defcode SEMI, ";", F_IMMEDIATE      mov  ax , EXIT      call COMMA      jmp short LBRACK

То, как эти слова переходят к другому слову в конце, весьма удобно. Помните, как NEXT записываются как часть кода следующего слова? Одно из слов должно быть последним в памяти, и тогда после него не будет никакого "следующего слова". : и ; - идеальные кандидаты для этого, поскольку им вообще не нужен NEXT.

Загрузка кода с диска

Поскольку мы не хотим вводить дисковые подпрограммы при каждой загрузке, нам нужно предусмотреть способ запуска исходного кода, загруженного с диска. Файловая система была бы отдельным зверем, но в традициях FORTH есть минималистичное решение: диск просто делится на блоки по 1 КБ, в которых хранится исходный код, отформатированный как 16 строк по 64 символа. Затем load ( blknum -- ) выполнит блок с указанным номером.

Мы размещаем блок 0 в LBA 0 и 1, блок 1 в LBA 2 и 3 и так далее. Это означает, что блок 0 частично занят MBR, а LBA 1 используется впустую, но меня это не особенно беспокоит.

Поскольку оригинальная служба BIOS по адресу int 0x13 / ah = 0x02 требует адресации CHS, я решил использовать вариант расширения EDD (ah = 0x42). Это означает, что дискеты не поддерживаются, но я все равно не планировал их использовать.

Чтобы использовать интерфейс EDD, нам нужно создать пакет адреса диска, который выглядит следующим образом:

      db 0x10 ; размер пакета      db 0    ; зарезервировано      dw sector_count      dw buffer_offset, buffer_segment      dq LBA

Мы используем гибридную стратегию для создания этого пакета. Первая часть сохраняется как данные в бутсекторе, а остальное записывается во время выполнения, даже если оно не меняется. Шаблон" должен находиться в таком месте, чтобы мы могли писать после него, поэтому идеальное место - прямо перед сжатыми данными:

>  >  > DiskPacket:       db 0x10, 0 .count:       dw 2 .buffer:

; остальное заполняется во время выполнения, перезаписывая сжатые данные,

; которые больше не нужны

CompressedData: times COMPRESSED_SIZE db 0xcc

Первые четыре байта пакета достаточно случайны, чтобы их можно было жестко закодировать. Однако, когда дело доходит до адреса буфера, мы можем сделать лучше. В любом случае нам нужно будет записать этот адрес в InputPtr. Самый прямой способ сделать это занимает шесть байт:

c706020a0006    mov word[InputPtr], BlockBuf

Однако мы можем получить эту переменную в AX без дополнительных затрат:

b80006          mov  ax , BlockBufa3020a          mov [InputPtr],  ax 

Таким образом, мы можем записать эти два байта дискового пакета с помощью всего 1 байта кода:

defcode LOAD, "load"      pusha      mov  di , DiskPacket.buffer      mov  ax , BlockBuf      mov word[InputPtr],  ax       stosw

Далее нам нужно записать сегмент (0000) и LBA (который заканчивается шестью байтами 00). Мне нравится думать о соответствующих инструкциях следующим образом:

31c0    xor  ax ,  ax     ; LBA zeroesab      stosw         ; segmentd1e3    shl  bx , 1     ; LBA data93      xchg  ax ,  bx    ; LBA dataab      stosw         ; LBA data93      xchg  ax ,  bx    ; segmentab      stosw         ; LBA zeroesab      stosw         ; LBA zeroesab      stosw         ; LBA zeroes

То есть, мы записываем шесть нулей LBA за 5 байт кода. Запись сегмента потребовала только перемещения xor ax, ax ранее, и дополнительных stosw и xchg ax, bx. Таким образом, он занимает нейтральные 2 байта (но нам нужно выписать его в коде, чтобы указатель был правильным для остальной части пакета). Наконец, конечно, у нас есть фактические данные LBA, которые меняются.

Пока AX равен нулю, воспользуемся случаем и поставим нулевой терминатор после буфера:

      mov [BlockBuf.end],  al 

Теперь мы готовы вызвать функцию BIOS. Если она выдаст ошибку, мы просто зациклимся, так как восстановление сложное и самое неприятное осложнение заключается в том, что счетчик секторов в пакете перезаписывается количеством успешно прочитанных секторов, что ломает наш шаблон.

DRIVE_NUMBER equ $+1      mov  dl , 0      mov  ah , 0x42      mov  si , DiskPacket      int 0x13      jc short $      popa      pop  bx 

Числа для печати

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

defcode UDOT, "u."    xchg  ax ,  bx     push " " - "0".split:      xor  dx ,  dx       div word[BASE]      push  dx       or  ax ,  ax       jnz .split.print:      pop  ax       add  al , "0"      cmp  al , "9"      jbe .got_digit      add  al , "A" - "0" - 10.got_digit:      call PutChar      cmp  al , " "      jne short .print      pop  bx 

s: Поместить в строку

s: - это функция, которая, как мне кажется, имеет уникальное значение для бутстраппинга. Это слово принимает адрес буфера и копирует туда остаток текущей строки ввода. Без этого значительный объем кода пришлось бы набирать дважды: сначала для того, чтобы запустить его и загрузить редактор дисковых блоков, а затем еще раз, чтобы сохранить его на диске.

Реализация представляет собой простой цикл, но установка вокруг него заслуживает внимания и мы хотим загрузить входной указатель в SI, но нам также нужно сохранить SI, чтобы мы могли правильно вернуться. Используя xchg, мы можем сохранить его в [InputPtr] на время копирования без дополнительных затрат:

;; Копирует остаток строки в buf.    defcode LINE, "s:" ; ( buf -- buf+len )      xchg  si , [InputPtr].copy:      lodsb      mov [ bx ],  al       inc  bx       or  al ,  al       jnz short .copy.done:      dec  bx       dec  si       xchg  si , [InputPtr]

Указатель назначения хранится в BX. Хотя запись в DI займет всего один стосб, получение указателя в DI и обратно перевешивает это преимущество. В конце мы оставляем в стеке указатель на нулевой терминатор. Таким образом, вы можете продолжить строку, просто используя s: в следующей строке. Поскольку мы не пропускаем пробельные символы, это даже гарантирует правильную расстановку символов.

Другие примитивы

Выбор примитивов для включения в Miniforth - это, пожалуй, самый большой компромисс, который необходимо сделать. Я полностью ожидаю, что некоторые более примитивные слова нужно будет определять во время выполнения, вставляя их в опкоды. В конце концов, здесь нет ни одного слова с ветвлением. Однако я уверен, что эти опкоды можно будет генерировать простым ассемблером FORTH, а не просто жестко закодировать.

Такая базовая арифметика, как +, незаменима. Я определяю и +, и -, хотя, если бы я хотел вписать что-то более важное, я мог бы оставить только - и позже определить : negate 0 swap - ; и : + negate - ;.

Как и в любом низкоуровневом языке программирования, нам нужен способ подглядывать и пихать значения в память. Реализация ! особенно хороша, поскольку мы можем просто заглянуть прямо в [bx]:

defcode PEEK, "@" ; ( addr -- val )    mov bx, [bx]defcode POKE, "!" ; ( val addr -- )    pop word [bx]    pop bx

Существуют также варианты, которые читают и записывают только один байт:

defcode CPEEK, "c@" ; ( addr -- ch )      movzx  bx , byte[ bx ]defcode CPOKE, "c!" ; ( ch addr -- )      pop  ax       mov [bx],  al       pop  bx 

Нам определенно нужны слова для работы со стеком. dup и drop имеют очень простые реализации, а swap определенно слишком полезен, чтобы его пропустить.

defcode DUP, "dup" ; ( a -- a a )      push  bx defcode DROP, "drop" ; ( a -- )      pop  bx defcode SWAP, "swap" ; ( a b -- b a )      pop  ax       push  bx       xchg  ax ,  bx 

Я решил также включить >r и r>, которые позволяют использовать стек возвратов в качестве второго стека для значений (но, очевидно, только в пределах одного слова). Это довольно мощный инструмент. Фактически, в сочетании с dup, drop и swap они позволяют реализовать любое слово для манипуляции стеком, которое вы только можете себе представить.9

defcode TO_R, ">r"      xchg  ax ,  bx       stosw      pop  bx defcode FROM_R, "r>"      dec  di       dec  di       push  bx       mov  bx , [ di ]

Наконец, emit печатает символ. Это достаточно далеко от критического пути bootstrap, чтобы я мог спокойно удалить его в случае необходимости.

defcode EMIT, "emit"      xchg  bx ,  ax       call PutChar      pop  bx 

Заключение

Я доволен тем, что получилось. Для системы, ограниченной загрузочным сектором, я могу назвать ее вполне законченной по функциям - я не могу придумать ничего, что могло бы значительно упростить бутстрап, занимая при этом достаточно мало байт, чтобы это казалось удаленно досягаемым для кодового гольфа. Это во многом благодаря помощи Ильи Курдюкова - без него я бы не смог вписать s:.

Я нашел старый ПК, который могу использовать для своих экспериментов. На нем Miniforth загружается просто отлично:

Я буду документировать свое путешествие по созданию Miniforth в будущих записях этого блога. Если это похоже на вашу чашку чая (а если вы дочитали до этого места, то, вероятно, так оно и есть), подпишитесь на RSS-канал или следите за мной в Twitter, чтобы получать уведомления о новых статьях.

1

У теоретика графов было бы много сильных слов, чтобы описать это, а не только цикл.

2

И даже если бы это было не так, есть много, многопримеров кода x86, написанного с использованием печатаемого подмножества ASCII. Я даже сам однажды сделал этонесколько лет назад.

3 Если вы, дорогой читатель, считаете это неудовлетворительным, я хотел бы пригласить вас в собственное путешествие по бутстрапингу. Это действительно очень весело!

4

Точную экономию на данный момент трудно подсчитать, поскольку некоторые слова не используют добавляемый NEXT.

5

Хотя в этом отрывке справки говорится только о pop ss, аналогичное утверждение содержится в документации по mov.

6

Похоже, это одна из многих ошибок в SDM и использование pop esp для этого не работает. Раздел 6.8.3 ("Маскировка исключений и прерываний при переключении стека") в томе 3A разъясняет, что все одноинструкционные способы загрузки SP работают для этого. Я бы процитировал этот раздел, если бы не тот факт, что, хотя в нем перечислены многие другие типы событий, которые подавляются, в нем не упоминаются реальные прерывания как один из них. Однако в этом разделе упоминаются некоторые интересные крайние случаи. Например, если вы похожи на меня, вам может быть интересно, что произойдет, если много инструкций подряд записываются в SS. Ответ заключается в том, что только первая из них гарантированно подавляет прерывания.

7

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

8

Вы можете спросить, почему бы просто не объявить, что BASE - это переменная размером в байт? Ответ заключается в том, что u., которое является словом, печатающим число, использует div word[BASE], так что результат все еще 16-битный.

9

Сюда не входят слова типа PICK, для них нужны циклы. Однако все, что можно определить как ( <список имен> -- <список имен>), является честной игрой. Доказательство этого факта мы оставляем на усмотрение читателя. 10

10

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

github.com/NieDzejkob

Введение

В этой истории я расскажу вам об увлекательном приключении, которое привело меня к решению одной загадки, которую я сам себе загадал. Разгадка являет собой небольшую подробность в механизме загрузчика 32-х разрядных приложений в системе Windows 7 и выше, а процесс разгадки - длинное путешествие воина, который следует по пути сердца.

Если вы попали на эту страницу в поисках ответа на вопрос, то смотрите спойлер ниже, потому что основное содержание может быть интересно тем, кто только пытается разобраться в механизме SEH.

С чего всё началось

Задумавшись о способе защиты своей программы от копирования, я вспомнил о статье Криса Касперского, в которой я узнал о существовании антиотладочных приёмов. Тщетно пытаясь реализовать разобранный Крисом пример в своей программе, я натыкался на стену непонимания со стороны Windows. Проблема заключалась в том, что Windows отказывалась пользоваться моим обработчиком исключений, посчитав его небезопасным.

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

Ближе к делу

Рассмотрим маленький пример (я пользуюсь компилятором MicrosoftVisual C++ )

int main(){ __asm { mov eax, DWORD PTR SS : [0] }}

Ничего особенного, пытаемся положить в регистр eax содержимое по адресу 0.

Компилируем, запускаем под отладчиком OllyDbg.

Получаем грустное сообщение access violation when reading 0x00000000.

Берем на заметку, что размер инструкции, которая пытается прочитать по адресу 0 - равен 6 байтам. Обратим также внимание на регистр Eip, который указывает на проблемную инструкцию (совпадает с её адресом слева). Сама же инструкция выглядит как последовательность из 6 байт: 36 A1 00 00 00 00.

Теперь я хочу обработать это исключение, не используя ключевых слов __try, __except т.к. мне показалось это интересной и заманчивой идеей.

Напишем же свой собственный обработчик для обработки этого исключения!

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

    struct _EXCEPTION_RECORD* exceptionRecord,    void* establisherFrame,    struct _CONTEXT* contextRecord,    void* dispatcherContext

где exceptionRecord структура, содержащая код ошибки, адрес исключения, а contextRecord структура содержащая контекст регистров (включая регистр Eip). Соглашение о вызове функции-обработчика должно быть __cdecl, а возвратить она должна одно из следующих значений:

typedef enum _EXCEPTION_DISPOSITION{ ExceptionContinueExecution, ExceptionContinueSearch, ExceptionNestedException, ExceptionCollidedUnwind} EXCEPTION_DISPOSITION;

Я решил обработать это исключение таким нехитрым образом:

EXCEPTION_DISPOSITION __cdecl ExceptionHanler(    struct _EXCEPTION_RECORD* exceptionRecord,    void* establisherFrame,    struct _CONTEXT* contextRecord,    void* dispatcherContext){    contextRecord->Eip += 6;    MessageBoxA(0, "Exteption was handled", "Success!", 0);    return ExceptionContinueExecution;}

Сместив регистр Eip на 6 байт, мы обойдём проблемную инструкцию! И говорим: ExceptionContinueExecution продолжить выполнение. Соответственно, выполнение продолжится с инструкции по адресу Eip + 6 и исключений больше возникнуть не должно.

Просто поместить код обработчика в программе - этого мало. Необходимо дать понять системе, что нужно вызывать именно его. И ещё я хочу, чтобы он вызвался самым первым, среди прочих. Для этого нам необходимо где-то создать структуру, состоящую из двух полей: Next и Handler. Поле Next будет содержать указатель на такую же структуру, но с предыдущим обработчиком (с тем, который мы потесним). Поле Handler будет содержать указатель на нашу функцию-обработчик. Указатель на текущую такую структуру находится в TIB (thread information block), иначе говоря, по адресу fs:[0]. Создадим её в стеке.

Преобразуем нашу функцию main:

int main(){__asm{    push ExceptionHanler //положим в стек адрес функции-обработчикаpush fs:[0]          //положим в стек указатель на структуру текущего обработчика                     //теперь в стеке лежит структура, содержащая 2 поля: указатель на     //следующий обработчик и адрес нашего обработчикаmov fs:[0] , esp   //положим указатель на свою структуру, вместо текущего                                                                                                                                                   //обработчика по адресу fs:[0]mov eax, DWORD PTR SS:[0] //пытаемся прочитать по адресу 0    add esp, 8          //чистим стек, удалив 8 байт (размер структуры)}}

По незнанию, я компилирую это с настройками по умолчанию - с флагом /SAFESEH и игнорирую непонятные рекомендации компилятора о том, что мне неплохо было бы отключить этот флаг, раз я записываю что-то по адресу fs:[0]. Да что там говорить, я далеко не сразу обратил на это внимание.

Результат все та же ошибка чтения по адресу 0 и приложение падает как ни в чем не бывало!

Хорошо, что все позади. Теперь я знаю об этом флаге. Пробую компилировать с настройкой /SAFESEH:NO.

Компилируем, выполняем наш код, видим наше развесёлое сообщение:

Жмем ок программа успешно завершается. Фух.

Переломный момент

Но нет, подождите-ка, но что ИМЕННО сделал в тот раз компилятор, чтобы проигнорировать мой обработчик исключения? Что это за фокусы? И как мне быть, если вдруг ну чисто теоретически, мне вдруг однажды захочется сделать так, чтобы моё приложение имело флаг /SAFESEH, но при этом, чтобы оно заработало, я должен буду встроить в него код mov fs:[0], esp, с указателем на свою функцию-обработчик, вызвать в произвольном месте исключение и обработать его так, как моей душе угодно? Не считаю, что флаг /SAFESEH должен быть помехой для моих фантазий.

Пытаясь получить информацию о работе этого флага, я увидел что-то размытое про таблицы безопасных обработчиков. Если они есть, то как мне на них посмотреть? Как добавить в них свой обработчик? Каким образом нужно изменить исполняемый файл, чтобы заставить систему при его исполнении выбирать обработчик именно из этой таблицы или наоборот, отключить выбор обработчика? Столько вопросов и так мало ответов

Не падая духом, в надежде разгадать загадку

Полистав срабатывающие обработчики, я увидел те, которые пушит компилятор на стадии выполнения crt0 (код до функции main), а также обработчик из библиотеки ntdll.dll. Все эти обработчики исправно срабатывают в порядке своей очереди, если я не помещаю свой обработчик по адресу fs:[0]! Но как система узнает, какая функция безопасный обработчик, а какая нет?

В своем путешествии я провёл серию экспериментов. Например, компилируя с флагом /SAFESEH, ставил точку останова перед проблемной инструкцией, брал первый обработчик, на который указывала первая структура по адресу fs:[0] и менял начало функции прямо в отладчике на JMP ExceptionHandler (мой самописный обработчик). Срабатывает! Срабатывает именно мой обработчик! И к чему тогда эта неведомая таблица безопасных, когда я могу легко подставить вместо любого безопасного прыжок на свой опасный? Впрочем, не важно. Это не даёт ответа на мои изначальные вопросы.

Теперь я пробую записать лог от entry point до функции main двух EXE файлов, скомпилированных с флагом /SAFESEH и /SAFESEH:NO, наивно предполагая, что компилятор на этой стадии вызывает некие WinApi функции, с помощью которых можно добавить в систему адреса безопасных обработчиков. Все тщетно. Два лога практически не отличаются, разве что серией дополнительных невнятных инструкций, не имеющих ничего общего с адресами безопасных обработчиков. Но подозрения все равно остались.

Чтобы окончательно исключить crt0 из списка подозреваемых мне необходимо выяснить еще кое-что. Я придумал следующий эксперимент, результат которого даст мне точный ответ на вопрос! Меняю инструкцию точки входа в программу на следующие команды push main, ret. Таким образом, первой командой в стек попадает адрес функции main, а вторая команда ret возвращает регистр указатель на выполнение функции main и функция main выполняется сразу, без crt0! (можно было обойтись и простым JMP, но его немного сложнее реализовать на лету в отладчике)

Я снова был удивлён, ведь мой обработчик вновь не вызвался! Несмотря на неудачу, это дало очень важный ответ: тайна кроется внутри EXE, скомпилированного хитрым образом, а не в коде, который выполняет компилятор.

Может быть, они спрятали этот флаг в PE хедере? В каком-нибудь поле LoaderFlags? И тут неудача У обоих файлов абсолютно идентичные структуры, за исключением разницы в размере секции rdata. Но даже если в секции rdata и лежит несколько дополнительных байт, разве это может быть способом взаимодействия с загрузчиком, кардинально изменяющим работу программы? Я был уверен, что нет

Ведь в секциях можно размещать что угодно, главное - соблюсти ключевые правила, думаю я. Там ведь полно мусора! Всякие строки, цифры, дни недели, это ведь не монолитная структура какая-то, а блоки данных, на которые указывают указатели. Эти блоки располагаются в произвольном месте, но в диапазоне секции. При сравнении двух файлов, никаких указателей на область rdata я не увидел, кроме известной importTable, debug и неизвестного указателя на boundImport. Кроме того, такой же указатель был и в файле без флага /SAFESEH! Его размер в таблице dataDirectories был очень маленьким и он был заполнен нулями. Это не вызывало моих подозрений, потому что я был уверен, что если бы это каким-то образом включало в себя таблицу обработчиков, то в файле без флага /SAFESEH это поле просто напросто отсутствовало бы, что было бы знаком для загрузчика у этого EXE таблицы нет.

Победа близка

Отчаявшись, я беру адрес первого безопасного обработчика, который подсовывает в мой EXE компилятор. А точнее - первые два младших байта его адреса и прошелся поиском по всему файлу. То, что я решил взять именно 2 байта, включая те значения, которые не являются виртуальными адресами, является везением. И вот, я выписал все сырые адреса, по которым располагаются эти значения, преобразовал адреса в виртуальные (их было около 3-х) и приступил к задуманному.

Имея несколько адресов в памяти, предположительно намекающих на законный обработчик от компилятора, я ставлю точку останова перед командой mov eax, DWORD PTR SS : [0] и жму play. Срабатывает. Я расставляю точки останова на чтение памяти по записанным адресам и снова жму play.

Удивительно! О брекпоинт споткнулась некая безымянная функция в библиотеке ntdll.dll.

Смотрим. Функция пытается считать по адресу 0x1341d20 из диапазона rdata число 0x1be0, а затем сравнить его с числом, находящимся в EBX 0x1000. Так, а ведь по адресу imageBase + 0x1000 расположился мой подставной обработчик! Он - то сейчас и находится в числе первых обработчиков. А по адресам 0x1be0, 0x2080 и 0x2351 располагаются безопасные обработчики от компилятора. Вот она эта таблица! Она всё это время была в моём файле!

В отладчике я меняю содержимое адреса 0x1341d20 с 0x1be0 на 0x1000 и мой обработчик стал вдруг безопасным и послушно обработал исключение!

Реализация проверки безопасных обработчиков в открытом виде! Она не находится внутри ядра Windows, как я ожидал. Так что можно даже подкорректировать код в ntdll.dll, чтобы в нужное время он разрешал или запрещал выбранные нами обработчики!

Вернёмся к нашему файлу еще раз внимательно посмотрим, что находится в окрестностях.

Ага, таблица на месте. Кроме того, случайно мне бросился в глаза адрес-указатель на начало таблицы, а также странное совпадение число 3, равное количеству обработчиков.

Попробую-ка я заполнить нулями этот адрес-указатель.

Успех! Программа, которую я скомпилировал с флагом /SAFESEH теперь выполняется так, как будто бы был установлен флаг флага /SAFESEH:NO!

А сравним с файлом, который был скомпилирован без этого флага?

Чёрт ни адреса-указателя на таблицу в этом месте, ни таблицы обработчиков И как я сразу не додумался сравнить два файла скомпилированных с разными флагами в Total Commander?!

Тем не менее, что указывает на это место в PE хедере? Самым близким является boundImport. И вот только теперь я открываю сайт Microsoft с описанием PE формата.

В общем я предлагаю вам самим ознакомиться с тем, что парни из Microsoft пишут там про boundImport. Что-то о таблице каталога отложенной загрузки на этапе связывания пост-обработки? Что?

В этом большом и непонятном документе, в котором описаны разные различия этого формата для разных платформ и т.д. Но меня уже не остановить, я начинаю упорно вводить в поиске слово except прыгаю по результатам поиска.. Вот, .sxdata - содержит индекс символа каждого из обработчиков. Какая . sxdata? У меня такого нет. Есть только виртуальный указатель в поле boundImport, относительно которого неподалёку размещается адрес-указатель и таблица с адресами функций-обработчиков.

Ищу дальше... Вот, ещё говорят, что в разделе pdata содержится массив обработчиков и что таблица может быть в нескольких форматах. Даже если и так, как загрузчик попадает на начало этой таблицы? В том месте, куда указывает boundImport, нет ничего похожего на тот формат, который представлен.

Смотрю дальше... The Load Configuration Structure. Судя по описанию очень похоже! Они говорят, что структура IMAGE_LOAD_CONFIG_DIRECTORY где-то присутствует и описывают ее предназначение, связанное с SEH.

Думаю, а попробую-ка. Взял, да и написал, что по адресу boundImport находится структура IMAGE_LOAD_CONFIG_DIRECTORY32 и рассмотрел её поля. Все сошлось как пазл! Это опять же было большим везением, что я решился на это.

Вот и всё, весь секрет заключался в том, что boundImport в PE хедере (разложенном по таблице из Википедии) указывает на структуру IMAGE_LOAD_CONFIG_DIRECTORY32. Эта структура содержит поля, которые кардинальным образом меняют работу программы! Теперь мы с уверенностью можем сами создать свою таблицу обработчиков и добавить в неё только то, что посчитаем нужным!

Может быть, где-то в недрах документации есть информация о том, что boundImport уже называется не так на моей платформе? Или информация о том, что его назначение изменилось? Может быть, boundImport оказался исключен или сдвинут?

Мир изменился. Я чувствую это в воде, чувствую это в земле, ощущаю в воздухе.

Властелин колец, Джон Рональд Руэл Толкин

Архитектура x86 долгие десятилетия была лидером по высокопроизводительным решениям. И этот факт позволял ей доминировать даже когда количество устройств на архитектуре ARM вокруг нас стало в несколько раз больше. Если вы пишете высокопроизводительный софт для серверов или рабочих станций, до недавнего времени вы могли обходиться лишь знанием x86. Но невозможно игнорировать события, которые могут поменять расклад сил уже совсем скоро. В связи с этим я решил немного поиграться с ARM и нарыл интересных фактов немного больше, чем на тред в твитере.

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

Мой опыт написания высокопроизводительного кода в основном связан с обработкой изображений в библиотеке Pillow-SIMD. Там я использовал интринсики в коде на Си чтобы добиться 6-8-кратного ускорения наиболее частых операций.

Под что вообще пишем?

Честно говоря, это самый высокий порог для вхождения в ARM архитектуру из тех, что будут. А x86 есть базовый набор команд, есть расширения (разные версии SSE, AVX, криптография или виртуализация) и есть разрядность (32 или 64 бита). В ARM же, загибайте пальцы:

• Есть архитектуры, коих более 20. Называются они примерно так: ARMv7-M, ARMv8-R, ARMv8.3-A.

• Есть микроархитектура. Например: Cortex-R4, Cortex-A76.

• Есть профайл: Classic, Microcontroller, Real-time, Application.

• Есть разные наборы команд! A32, A64, Thumb, Thumb2.

• Наконец, расширения набора команд: SIMD, NEON, SVE.

• Ну и никуда не делась разрядность: AArch32 и AArch64.

Не претендуя на полноту описания, я подсвечу основные моменты и укажу, что сейчас можно опустить. Все архитектуры соответствуют одному из четырех профайлов. Classic это прям совсем классик, такое вы вряд ли встретите. Из трёх остальных самое ходовое это Application. Все телефоны, сервера и рабочие станции это Application. Профайл всегда отражён в названии архитектуры в виде постфикса (A, M, R). Актуальных архитектур всего две ARMv7 и ARMv8, зато у ARMv8 вышло уже 6 минорных версий, которые тоже называются архитектурами (например, ARMv8.2-A). Причём 64-битная разрядность появилась только в ARMv8. Однако ARMv8-A не гарантирует наличие 64-битного режима у процессора, а вот ARMv8.1-A уже гарантирует.

Если знание архитектуры чипа нужно нам, разработчикам софта, чтобы знать, какой минимальный набор функциональности возможно использовать, то микроархитектура уже нужна для разработчиков чипов, чтобы знать, сколько кеша нужно насыпать, сколько вычислительных блоков должно быть и какие опциональные технологи нужно включить в чип. Причем, бывает как микроархитектура от самой компании ARM (она обычно называется Cortex и следом снова постфикс профайла), так и кастомная, которая может называться Apple Firestorm, Neoverse N1 или никак не называться.

Набор команд A32 используется в 32-битном режиме AArch32, а A64 в 64-битном режиме AArch64. И казалось бы, зачем выделять такие очевидные вещи. Но дело в том, что A32 не единственный набор команд, который может быть в 32-битном режиме. A32 и A64 всегда используют 32 бита для кодирования любой инструкции, а AArch32 вышел очень давно и многим казалось, что это расточительство и тогда появились альтернативные способы кодирования Thumb и Thumb2. В них часто используемые инструкции занимали 16 бит. Для AArch64 уже ничего такого не завезли, в нём любая инструкция занимает 32 бита.

Ну и наконец, расширения набора команд. Вообще, есть ещё расширения VFPv1-VFPv5 для работы с плавающей точкой, разницу между которыми я так и не смог понять. Как и в x86, в ARM плавающую точку завезли не сразу. В ARMv6 было добавлено расширение SIMD (так и называется), а в ARMv7 появился опциональный 128-битный advanced SIMD, он же ASIMD, он же NEON, по сути прямой аналог SSE последних версий. О нём я буду рассказывать больше всего. А вот аналога AVX в ARM нет, там пошли другим путём. Вместо того, чтобы каждые пять лет представлять новое расширение, под которые нужно будет всё переписывать, было разработано расширение Scalable Vector Extension (SVE), которое позволяет выполнять один и тот же код на чипах, реализующих разный размер векторов. Но на практике, как я понял, SVE реализован только в Fugaku supercomputer.

Это же ужас?

Ну, вообще, да, если вы собрались писать приложение, которое может быть выполнено на любом ARM процессоре, как это бывает с x86. Теоретически на нем может не оказаться не только NEON, но даже 64-битной арифметики с плавающей точкой. Вот только, к счастью, у ARM нет того наследия работающих систем, на которых могли бы запустить ваш код. Это в любом случае будет свежий процессор. И ещё, с максимальной вероятностью это всё же будет AArch64 система. А теперь следите за руками.

AArch64 появился только в ARMv8. ARMv8-A уже гарантирует наличие VFPv4 (64-битный FPU), NEON и криптографии. А SVE можно даже не проверять ещё пару лет. У NEON никаких версий нет. Так же остается только один набор инструкций: A64. А микроархитектура просто ни на что не влияет.

Получается, несмотря на огромное количество вариантов, в реальности писать код под ARM (точнее под AArch64) даже проще, чем под x86. Никакие проверки в рантайме не нужны, просто ставите `#ifdef __aarch64__` и пользуетесь всем, чем хотите.

Знакомство с NEON

Принципиальное устройство x86 и ARM мало чем отличаются. И там и там есть общие регистры и регистры для вычислений с плавающей точкой и SIMD. Для общей картины достаточно прочитать раздел General-purpose registers в AArch64 Instruction Set Architecture. И сразу после этого можно переходить к самому полному вводному гайду Coding for Neon.

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

LD3 { V0.16B, V1.16B, V2.16B }, [x0]

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

Очень приятно удивляет кол-во вариантов всяческих сдвигов. Например, есть вариант, когда сдвиг каждого элемента вектора задается в другом векторе.

В SSE, например, такого нет. Похожая функциональность появилась только в AVX2 с инструкциями vpsrlv[dq], vpsllv[dq], vpsravd. Но, во-первых, в NEON инструкции сдвигают в обе стороны, в зависимости от знака. Во-вторых, в AVX2 можно сдвинуть только 32-битные и 64-битные значения. На этом вкусности NEON не заканчиваются, из других вариантов сдвига есть:

• Сдвиг и сложение с аккумулятором

• Сдвиг вправо с округлением

• Сдвиг с сатурацией

• Сдвиг с уменьшением или увеличением разрядности

Причем некоторые варианты из списка можно комбинировать, и всё это работает с любым типом данных. Поправьте, но вроде SSE ничего из этого не может предложить.

Что касается интринсиков, в отличие от SSE/AVX, где типизированны только регистры для float и double (__m128и __m128d), в NEON есть типы для всех целых типов и названия придерживаются конвенции stdint.h.

uint8x16_t Sx4 = vld1q_u8(&Srgba[i]);uint8x16_t Dx4 = vld1q_u8(&Drgba[i]);uint32x4_t Sax4 = vshrq_n_u32((uint32x4_t) Sx4, 24);uint32x4_t Dax4 = vshrq_n_u32((uint32x4_t) Dx4, 24);

Тут первые две переменны имеют тип 16 беззнаковых int8, вторые 4 беззнаковых int32. Но, так как это одни и те же регистры, их можно приводить друг к другу. Интересно, что есть типы вроде uint8x16x3_t это три регистра подряд. В основном такие типы используются для загрузки и сохранения в оперативную память.

Справочник интринсиков

Если вы за последнее десятилетие писали SIMD-код для x86, вы наверняка пользовались Intel Intrinsics Guide. Это прекрасный справочник с интерактивным поиском и фильтром, понятным описанием и псевдокодом для каждой инструкции. И даже есть таблицы задержек и пропускной способности по разным поколениям процессоров Intel.

В нём можно не только искать нужное, но и изучать новое, просто выбирая какое-то поколение инструкций и читая всё подряд.

У ARM аналогом этого гайда служит Neon Intrinsics Reference. И это просто боль и унижение.

• Нет никаких фильтров

• Поиск работает с перезагрузкой страницы

• На странице выводится только 30 функций, снизу есть постраничная навигация, тоже с перезагрузкой страницы

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

• По запросу "mul" находятся 50 страниц функций! То есть 1500 штук. Знаете, почему в результатах оказалась функция, показанная на скриншоте? Потому что в описании есть слово accumulate!

• У каждой инструкции есть много флагов, которые чуть-чуть меняют поведение и почти каждая инструкция работает с несколькими типами данных, которых около 12. И для всего этого создаются отдельные функции. По факту описание и псевдокод написан не для функций, а для инструкции. То есть понять, чем одна функция отличается от другой, почти такой же, оочень сложно.

• Вы вообще видели этот псевдокод? Он сам по себе очень избыточен и запутан.

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

Подходящая задача

Давайте попробуем NEON в деле. В качестве примера кода, на котором можно поэкспериментировать, я выбрал альфа-композитинг с premultiplied alpha. Его можно описать такой формулой:

Алгоритм идеально ложится на SIMD:

#include <stdint.h>#include <stddef.h>#define SHIFTFORDIV255(a)\    ((((a) >> 8) + a) >> 8)#define DIV255(a)\    SHIFTFORDIV255(a + 0x80)static voidopSourceOver_premul(uint8_t* restrict Rrgba,                    const uint8_t* restrict Srgba,                    const uint8_t* restrict Drgba, size_t len){    size_t i = 0;    for (; i < len*4; i += 4) {        uint8_t Sa = Srgba[i + 3];        Rrgba[i + 0] = DIV255(Srgba[i + 0] * 255 + Drgba[i + 0] * (255 - Sa));        Rrgba[i + 1] = DIV255(Srgba[i + 1] * 255 + Drgba[i + 1] * (255 - Sa));        Rrgba[i + 2] = DIV255(Srgba[i + 2] * 255 + Drgba[i + 2] * (255 - Sa));        Rrgba[i + 3] = DIV255(Srgba[i + 3] * 255 + Drgba[i + 3] * (255 - Sa));    }}

Все операции выполняются над целочисленными значениями. 1 - S_a превращается в 255 - Sa. Так как правую часть мы умножаем на байт, то и левую нужно умножить. А после сложения нужно поделить на 255, это делает макрос DIV255путём нескольких сдвигов.

Запускать я буду на Raspberry Pi 4, естественно под AArch64. Чем богаты, тем и рады, как говорится. Причем в данном случае мне интересно посмотреть именно пиковую производительность, без влияния памяти. Для этого я буду тестировать на строке длиной 1000 пикселей, то есть всего будет задействовано 12 Кб данных за один вызов функции.

Я буду пользоваться компилятором Clang-9, т.к. он в большинстве случаев выдает более быстрый код, чем GCC. Для начала интересно, как быстро работает чистый код, без векторизации.

$ clang-9 -Wall -O2 -o run.64 main.c -fno-tree-vectorize && ./run.64Time elapsed: 0.189449Time elapsed: 0.189280Time elapsed: 0.189272Time elapsed: 0.189272

Время указано в секундах для 20 тысяч прогонов функции с длиной строк 1000 пикселей. То есть можно сказать, что скорость работы примерно 105 МПх/с. И вообще-то это очень мало, даже для Raspberry Pi. Если включить автоматическую векторизацию, результат будет чуть лучше.

$ clang-9 -Wall -O2 -o run.64 main.c -ftree-vectorize && ./run.64Time elapsed: 0.082168Time elapsed: 0.082341Time elapsed: 0.082135Time elapsed: 0.082147

Ускорение в 2.3 раза существенно, но это не всё, на что можно было бы рассчитывать. Посмотрим, что можно сделать вручную.

NEON-версия

Первое, что нужно сделать, чтобы начать программировать на NEON подключить заголовочный файл arm_neon.h. Согласитесь, это приятнее, чем каждый раз гуглить ничего не значащие имена заголовочных файлов, вроде smmintrin.h.

1. Загрузка/сохранение. Хотя видно, что код хорошо векторизуется внутри цикла, можно сразу пойти чуть дальше и читать из памяти 128-битный вектор целиком и работать с четырьмя пикселями.

#include <stdint.h>#include <stddef.h>#include <arm_neon.h>static voidopSourceOver_premul(uint8_t* restrict Rrgba,                    const uint8_t* restrict Srgba,                    const uint8_t* restrict Drgba, size_t len){    size_t i = 0;    for (; i < len*4 - 12; i += 16) {        uint8x16_t Sx4 = vld1q_u8(&Srgba[i]);        uint8x16_t Dx4 = vld1q_u8(&Drgba[i]);        uint8x16_t Rx4 = vaddq_u8(Sx4, Dx4);  // Temporary stub        vst1q_u8(&Rrgba[i], Rx4);    }    for (; i < len*4; i += 4) {        uint8_t Sa = Srgba[i + 3];        Rrgba[i + 0] = DIV255(Srgba[i + 0] * 255 + Drgba[i + 0] * (255 - Sa));        Rrgba[i + 1] = DIV255(Srgba[i + 1] * 255 + Drgba[i + 1] * (255 - Sa));        Rrgba[i + 2] = DIV255(Srgba[i + 2] * 255 + Drgba[i + 2] * (255 - Sa));        Rrgba[i + 3] = DIV255(Srgba[i + 3] * 255 + Drgba[i + 3] * (255 - Sa));    }}

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

$ clang-9 -Wall -O2 -o run.64 main.c && ./run.64Time elapsed: 0.008030Time elapsed: 0.007872Time elapsed: 0.007859Time elapsed: 0.008629

8 мс или 2500 МПх/с! Вот мы и ускорили код с помощью NEON в 25 раз.

2. Выделение альфа-канала. Следующая задача нужно из вектора Sx4отдельно вытащить все компоненты альфа-канала. Они находятся на 3, 7, 11 и 15 позиции. Причем желательно их сразу размножить на все соседние байты этого же пикселя. Несмотря на множество команд перемешивания байтов, я не нашел ничего специального и сделал через векторный поиск в таблице. Дальше нужно вычесть полученное значение из 255.

uint8x16_t vsubq_u8 (uint8x16_t a, uint8x16_t b);uint8x16_t vdupq_n_u8 (uint8_t value);uint8x16_t vqtbl1q_u8 (uint8x16_t t, uint8x16_t idx);uint8x16_t Sax4 = vsubq_u8(    vdupq_n_u8(255),    vqtbl1q_u8(Sx4, (uint8x16_t){3,3,3,3, 7,7,7,7, 11,11,11,11, 15,15,15,15}));

Интересно, что все компиляторы при оптимизации заменяют операцию вычитания из 255 на побитовое отрицание, что логично.

3. Умножение. Дальше нужно все элементы Sx4умножить на 255, а элементы Dx4на соответствующие элементы альфы из Sax4. Все значения 8-битные.

В NEON есть два вида умножения: либо это обычные функции vmulq_*, которые не меняют разрядность и отдают нижнюю часть результата, либо это vmull_* и vmull_high_*, которые делают операцию только над половиной вектора, но зато увеличивают разрядность и отдают результат целиком.

uint16x8_t vmull_u8 (uint8x8_t a, uint8x8_t b);uint8x8_t vget_low_u8 (uint8x16_t a);uint8x8_t vdup_n_u8 (uint8_t value);uint16x8_t vmull_high_u8 (uint8x16_t a, uint8x16_t b);uint16x8_t Rx2lo = vmull_u8(vget_low_u8(Sx4), vdup_n_u8(255));uint16x8_t Rx2hi = vmull_high_u8(Sx4, vdupq_n_u8(255));

Для умножения Dx4 можно было быиспользовать эти же функции, но у них есть ещё одна разновидность, которая тут больше подходит. Это умножение и сложение с аккумулятором. Действительно, нам нужно будет складывать результат умножения, так почему бы не сделать это в одну операцию.

uint16x8_t vmlal_u8 (uint16x8_t a, uint8x8_t b, uint8x8_t c);uint16x8_t vmlal_high_u8 (uint16x8_t a, uint8x16_t b, uint8x16_t c);Rx2lo = vmlal_u8(Rx2lo, vget_low_u8(Dx4), vget_low_u8(Sax4));Rx2hi = vmlal_high_u8(Rx2hi, Dx4, Sax4);

4. Деление на 255. Ну что, пришла пора опробовать в деле крутые сдвиги. В Си-версии это происходит так:

#define DIV255(a)\    ((((a + 0x80) >> 8) + a + 0x80) >> 8)

Первое, что нужно рассмотреть сдвиги с округлением. Для этого до сдвига прибавляется константа в один бит правее сдвига. По сути это уже сильно упрощает описание деления:

#define ROUND_SHR(a, n)\    ((a + (1<<(n-1))) >> n)#define DIV255(a)\    ROUND_SHR(ROUND_SHR(a, 8) + a, 8)

Дальше следует обратить внимание на конструкцию ROUND_SHR(a, 8) + a. Это же сдвиг с аккумулятором vrsraq_n_u16, помните? Ну а последний сдвиг можно сделать так, чтобы он заодно уменьшал разрядность результата, ведь тот не должен превышать 255. Кроме того, можно уменьшить разрядность не только в нижнюю половину вектора, но и в верхнюю (vqrshrn_high_n_u16).

uint8x16_t vqrshrn_high_n_u16 (uint8x8_t r, uint16x8_t a, const int n);uint8x8_t vqrshrn_n_u16 (uint16x8_t a, const int n);uint16x8_t vrsraq_n_u16 (uint16x8_t a, uint16x8_t b, const int n);uint8x16_t Rx4 = vqrshrn_high_n_u16(    vqrshrn_n_u16(vrsraq_n_u16(Rx2lo, Rx2lo, 8), 8),    vrsraq_n_u16(Rx2hi, Rx2hi, 8), 8);

Всё вместе:

static voidopSourceOver_premul(uint8_t* restrict Rrgba,                    const uint8_t* restrict Srgba,                    const uint8_t* restrict Drgba, size_t len){    size_t i = 0;    for (; i < len*4 - 12; i += 16) {        uint8x16_t Sx4 = vld1q_u8(&Srgba[i]);        uint8x16_t Dx4 = vld1q_u8(&Drgba[i]);        uint8x16_t Sax4 = vsubq_u8(            vdupq_n_u8(255),            vqtbl1q_u8(Sx4, (uint8x16_t){3,3,3,3, 7,7,7,7, 11,11,11,11, 15,15,15,15})        );        uint16x8_t Rx2lo = vmull_u8(vget_low_u8(Sx4), vdup_n_u8(255));        uint16x8_t Rx2hi = vmull_high_u8(Sx4, vdupq_n_u8(255));        Rx2lo = vmlal_u8(Rx2lo, vget_low_u8(Dx4), vget_low_u8(Sax4));        Rx2hi = vmlal_high_u8(Rx2hi, Dx4, Sax4);        uint8x16_t Rx4 = vqrshrn_high_n_u16(            vqrshrn_n_u16(vrsraq_n_u16(Rx2lo, Rx2lo, 8), 8),            vrsraq_n_u16(Rx2hi, Rx2hi, 8), 8);        vst1q_u8(&Rrgba[i], Rx4);    }    for (; i < len*4; i += 4) {        uint8_t Sa = Srgba[i + 3];        Rrgba[i + 0] = DIV255(Srgba[i + 0] * 255 + Drgba[i + 0] * (255 - Sa));        Rrgba[i + 1] = DIV255(Srgba[i + 1] * 255 + Drgba[i + 1] * (255 - Sa));        Rrgba[i + 2] = DIV255(Srgba[i + 2] * 255 + Drgba[i + 2] * (255 - Sa));        Rrgba[i + 3] = DIV255(Srgba[i + 3] * 255 + Drgba[i + 3] * (255 - Sa));    }}

Ну и наконец, можно порадоваться результату:

$ clang-9 -Wall -O2 -o run.64 main.c && ./run.64Time elapsed: 0.047613Time elapsed: 0.047455Time elapsed: 0.047452Time elapsed: 0.047448

Это в 1,75 раз быстрее, чем автовекторизованная версия и в 4 раза быстрее, чем версия совсем без векторизации (кстати, для GCC ускорение получается 5,5 раза).

Оптимизация чтения

Полученный результат полностью доказывает жизнеспособность программирования под NEON, однако, от использованной техники (чтение и обработка 4 пикселей, 8 умножений за инструкцию) можно было ожидать больший прирост скорости. Давайте посмотрим, что можно улучшить.

Код выполнялся на процессоре Broadcom BCM2835, который хоть и относительно современный, но супербюджетный. Можно ожидать, что на таком процессоре могут быть существенные задержки даже для доступа к кешу L1. При этом никакие инструкции предвыборки не помогут, т.к. данные уже лежат в самом близком кеше. Зато может помочь предварительное чтение. Для этого нужно на каждом шаге класть в карман данные, которые понадобятся на следующем шаге. А из кармана доставать то, что было выбрано на предыдущем.

    uint8x16_t Sx4_next = vld1q_u8(&Srgba[0]);    uint8x16_t Dx4_next = vld1q_u8(&Drgba[0]);    // for (; i < len*4 - 12; i += 16) {    for (; i < len*4 - 12 - 16; i += 16) {        // uint8x16_t Sx4 = vld1q_u8(&Srgba[i]);        // uint8x16_t Dx4 = vld1q_u8(&Drgba[i]);        uint8x16_t Sx4 = Sx4_next;        uint8x16_t Dx4 = Dx4_next;        Sx4_next = vld1q_u8(&Srgba[i + 16]);        Dx4_next = vld1q_u8(&Drgba[i + 16]);        ...

При этом нужно не забыть, что цикл нужно уменьшить на одну итерацию, чтобы не прочитать данные за пределами указателя.

$ clang-9 -Wall -O2 -o run.64 main.c && ./run.64Time elapsed: 0.038070Time elapsed: 0.037855Time elapsed: 0.037834Time elapsed: 0.037831

Гипотеза оказалась верной, это дало прирост ещё 25%. Итого NEON работает ровно в 5 раз быстрее, чем код без векторизации.

Разбор сгенерированного кода

Ну что, пора посмотреть, что напридумывал компилятор.

$ clang-9 -Wall -O2 -o main.s main.c -S

Это вывод уже отформатированный, с некоторыми переименованными регистрами и с комментариями оригинального кода:

    ldr     q0, [x19]                   // Sx4 = vld1q_u8(&Srgba[0])    ldr     q1, [x20]                   // Dx4 = vld1q_u8(&Drgba[0])    movi    v17.2d, #0xffffffffffffffff    mov     x9, xzr.LBB0_3:    tbl     v5.16b, { v0.16b }, v16.16b // vqtbl1q_u8(Sx4, v16)    mvn     v5.16b, v5.16b              // Sax4 = vsubq_u8(vdupq_n_u8(255), v5)    ext     v6.16b, v0.16b, v0.16b, #8    umull   v3.8h, v1.8b, v5.8b         // Rx2lo = vmull_u8(Dx4, Sax4);    add     x10, x19, x9    add     x11, x20, x9    umull   v4.8h, v6.8b, v17.8b        // Rx2hi = vmull_high_u8(Sx4, 0xff)    umlal   v3.8h, v0.8b, v17.8b        // vmlal_u8(Rx2lo, Sx4, 0xff)    umlal2  v4.8h, v1.16b, v5.16b       // vmlal_high_u8(Rx2hi, Dx4, Sax4)    ldr     q0, [x10, #16]              // Sx4 = vld1q_u8(&Srgba[i + 16])    ldr     q1, [x11, #16]              // Dx4 = vld1q_u8(&Drgba[i + 16])    ursra   v3.8h, v3.8h, #8            // vrsraq_n_u16(Rx2lo, Rx2lo, 8)    ursra   v4.8h, v4.8h, #8            // vrsraq_n_u16(Rx2hi, Rx2hi, 8)    uqrshrn v2.8b, v3.8h, #8            // Rx4 = vqrshrn_n_u16(Rx2lo, 8)    add     x10, x9, #16                uqrshrn2 v2.16b, v4.8h, #8          // vqrshrn_high_n_u16(Rx4, Rx2hi, 8)    cmp     x10, #3972                      str     q2, [x21, x9]               // vst1q_u8(&Rrgba[i], Rx4)    mov     x9, x10    b.lo    .LBB0_3

Хочу напомнить, что q0и v0 это разные названия одного регистра. Первое, что стоит отметить компилятор верно понял задумку с упреждающим чтением и, несмотря на то, что в коде мы использовали копирование из старых переменных в новые, в выводе ничего такого нет. Чтение происходит сразу после того, как данные регистров v0 и v1 больше не используются. Хоть из-за этого загрузка и сместилась с начала итерации в середину, тут стоит положиться на компилятор, т.к. скорее всего он решил так сделать основываясь на латентности операций чтения.

Далее стоит обратить внимание на последовательности umullи umlal. Тут произошло странное, зачем-то компилятор заменил umull2 на ещё один umull. Для этого ему понадобилось в строчке 8 сделать лишнее извлечение верхней части v0 во временный регистр v6. Формально мы использовали функцию vget_low_u8, которая это и подразумевает. Однако это было сделано только для того, чтобы привести переменную к нужному типу. Если посмотреть, что генерируют компиляторы для такого кода, то видно, что они не очень понимают, что нижняя часть регистра это и есть сам регистр. Ну а GCC вообще творит какую-то дичь: создает два разных регистра с константами, делает три копирования.

На этом странности не заканчиваются. Для Rx2loпереставлены местами vmull_u8и vmlal_u8. Формально это ни на что не влияет, но все равно не понятно, зачем.

Ну и последнее, на что можно обратить внимание это странная работа с индексами. Если для команды str q2, [x21, x9]в качестве смещения используется регистр, то для ldrсмещение вычисляется заранее, причем два раза, хотя очевидно, что можно было вычислить x9 + 16и использовать это значение в обеих загрузках.

Пробуем всё это исправить:

    ldr     q0, [x19]                   // Sx4 = vld1q_u8(&Srgba[0])    ldr     q1, [x20]                   // Dx4 = vld1q_u8(&Drgba[0])    movi    v17.2d, #0xffffffffffffffff    mov     x9, xzr                     // i = 0.LBB0_3:    tbl     v5.16b, { v0.16b }, v16.16b // vqtbl1q_u8(Sx4, v16)    mvn     v5.16b, v5.16b              // Sax4 = vsubq_u8(vdupq_n_u8(255), v5)    add     x10, x9, #16                // x10 = i + 16    umull   v3.8h, v0.8b, v17.8b        // Rx2lo = vmull_u8(Sx4, 0xff);    umull2  v4.8h, v0.16b, v17.16b      // Rx2hi = vmull_high_u8(Sx4, 0xff)    ldr     q0, [x19, x10]              // Sx4 = vld1q_u8(&Srgba[i + 16])    umlal   v3.8h, v1.8b, v5.8b         // vmlal_u8(Rx2lo, Dx4, Sax4)    umlal2  v4.8h, v1.16b, v5.16b       // vmlal_high_u8(Rx2hi, Dx4, Sax4)    ldr     q1, [x20, x10]              // Dx4 = vld1q_u8(&Drgba[i + 16])    ursra   v3.8h, v3.8h, #8            // vrsraq_n_u16(Rx2lo, Rx2lo, 8)    ursra   v4.8h, v4.8h, #8            // vrsraq_n_u16(Rx2hi, Rx2hi, 8)    uqrshrn v2.8b, v3.8h, #8            // Rx4 = vqrshrn_n_u16(Rx2lo, 8)    uqrshrn2 v2.16b, v4.8h, #8          // vqrshrn_high_n_u16(Rx4, Rx2hi, 8)    cmp     x10, #3972                      str     q2, [x21, x9]               // vst1q_u8(&Rrgba[i], Rx4)    mov     x9, x10    b.lo    .LBB0_3

Запускаем:

$ clang-9 -Wall -O2 -o main.o -c main.s && gcc ./main.o -o run.64 && ./run.64 Time elapsed: 0.033388Time elapsed: 0.033204Time elapsed: 0.033223Time elapsed: 0.033190

Есть ещё 14% прироста. Итого ускорение 5,7 раз.

Было бы интересно также посчитать, сколько тактов уходит на этот цикл. Имеем 1800МГц (тактов/с), 0.033190 с/запуск и 250 * 20 * 1000 циклов/запуск. Итого: 1800000000 *0.033190 / (250 * 20 * 1000) 12 тактов/цикл. Учитывая, что в цикле 17 инструкций, это прекрасный результат. Я не думал, что такой простой процессор может работать так эффективно.

Решение на SSE

Думаю, будет нелишним решить ту же задачу на SSE и сравнить усилия. Загрузка и выгрузка данных ничем не отличается. Дальше нужно размножить альфа-канал пикселей-источников на все остальные каналы. Тут можно сделать полностью аналогично NEON-версии.

__m128i Sax4 = _mm_sub_epi8(    _mm_set1_epi8((char) 255),    _mm_shuffle_epi8(Sx4, _mm_set_epi8(        15,15,15,15, 11,11,11,11, 7,7,7,7, 3,3,3,3)));

Существенное отличие только в том, что порядок байтов у _mm_set_epi8инвертирован.

Дальше нужно 8-битное умножение. В SSE есть такое, это интринсик _mm_maddubs_epi16. И кстати, он же увеличивает разрядность результата и даже делает сложение соседних элементов. Можно было бы подумать, что дело в шляпе.

// Это неправильный код!__m128i Rx2lo = _mm_maddubs_epi16(    _mm_unpacklo_epi8(_mm_set1_epi8((char) 255), Sax4),    _mm_unpacklo_epi8(Sx4, Dx4));__m128i Rx2hi = _mm_maddubs_epi16(    _mm_unpackhi_epi8(_mm_set1_epi8((char) 255), Sax4),    _mm_unpackhi_epi8(Sx4, Dx4));

Количество инструкций умножения уменьшилось вдвое по сравнению с NEON-версией. Но, к сожалению, _mm_maddubs_epi16 принимаеттолько первый 8-битный аргумент как целое без знака, а второй аргумент считается со знаком, поэтому результат будет неверным. Функции, в которой оба аргумента были бы без знака, нет. А значит, нужно использовать 16-битное умножение и распаковывать каждый аргумент с пустым регистром, что существенно увеличивает и запутывает код.

__m128i Rx2lo = _mm_add_epi16(    _mm_mullo_epi16(_mm_unpacklo_epi8(Sx4, _mm_setzero_si128()),                    _mm_set1_epi16(255)),    _mm_mullo_epi16(_mm_unpacklo_epi8(Dx4, _mm_setzero_si128()),                    _mm_unpacklo_epi8(Sax4, _mm_setzero_si128())));__m128i Rx2hi = _mm_add_epi16(    _mm_mullo_epi16(_mm_unpackhi_epi8(Sx4, _mm_setzero_si128()),                    _mm_set1_epi16(255)),    _mm_mullo_epi16(_mm_unpackhi_epi8(Dx4, _mm_setzero_si128()),                    _mm_unpackhi_epi8(Sax4, _mm_setzero_si128())));

Деление на 255 и запаковку приходится делать, описывая каждый шаг, SSE никак не помогает.

Rx2lo = _mm_add_epi16(Rx2lo, _mm_set1_epi16(0x80));Rx2lo = _mm_srli_epi16(_mm_add_epi16(_mm_srli_epi16(Rx2lo, 8), Rx2lo), 8);Rx2hi = _mm_add_epi16(Rx2hi, _mm_set1_epi16(0x80));Rx2hi = _mm_srli_epi16(_mm_add_epi16(_mm_srli_epi16(Rx2hi, 8), Rx2hi), 8);__m128i Rx4 = _mm_packus_epi16(Rx2lo, Rx2hi);

За вычетом загрузок/сохранений, констант и приведений типов, я насчитал 23 интринсика в SSE версии против 10 в NEON. Предложения по улучшению преветствуются.

Моё впечатление

NEON произвел впечатление очень продуманной и эффективной системы команд. Я нашел для себя такие плюсы:

• В отличие от SSE, есть консистентность типов данных, с которыми работают разные инструкции.

• Порадовало большое количество опций сдвигов, которые оказались полезными на практике.

• Можно встраивать NEON-код в любое место приложения без проверок рантайм.

• Использование NEON дает ощутимый прирост производительности, примерно равный такому от использования SSE.

• Очень понятный ассемблер с типизированными аргументами.

• Были опасения, что будет сильно не хватать инструкции _mm_madd_epi16, делающей 8 умножений и 4 сложения. Однако её функциональность покрывается парой vmull_*/vmlal_*, не требующих подготовки данных.

Минусы я бы отметил следующие:

• Абсолютно неюзабельный справочник интринсиков. Это не минус самого NEON, но это то, с чем придется столкнуться.

• Производительность сильно зависит от компилятора, возможно придется залочиться на clang.

• Имена некоторых интринсиков напоминают читы в играх: vqrshrn_n_u16, vqdmulh_s16

Бенчмарки

Я собрал все варианты из этой статьи в один репозиторий с make-файлом, чтобы быстро запускать на разных системах или с разным окружением. Помимо Raspberry Pi 4 я смог запустить код ещё на c6g.largeинстансе в AWS, которые работают на процессорах AWS Graviton2. Вот что я намерил:

Коэффициентами я обозначил замедление относительно варианта на ассемблере. Таблица получилась очень интересная. Выводов можно сделать много:

• Поведение очень сильно зависит от компилятора. Протестированные версии GCC практически везде медленнее Clang.

• Автоматическая векторизация в целом работает, но не дает такого же эффекта, как ручная.

• Автоматическая векторизация может внезапно не заработать, причем даже на более свежей версии компилятора. При этом функция была выбрана предельно простая для векторизации.

• GCC также не оценил оптимизацию чтения. Я не смотрел код, но выглядит так, будто он её просто выкинул.

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

• Пока что компиляторы не умеют полностью раскрывать возможности ARM, даже при использовании интринсиков.

Кроме этого я все же решил измерить неизмеримое и сравнить несравнимое. Запустил тесты для ARM на Apple M1, а для x86 на Intel(R) Xeon. Выбор M1 понятен кроме него пока нет десктопных процессоров от Apple. А вот на чем запускать x86 было вопросом. На ноутбуке у меня процессор может работать в диапазоне от 2,4 до 4,1 Ггц при разных сценариях. Поэтому я решил запустить на серверном процессоре, у которого стабильная частота.

Ещё момент, в результатах на M1 был сильнейший разброс, вплоть до двух раз. Я запускал не у себя и у меня не было возможности проверить, почему так выходит. Моё предположение, что какое-то время работали слабые ядра. В любом случае, я брал минимальное время.

Коэффициентами я обозначил замедление относительно ручной 128-битной векторизации. Хочется напомнить, что это далеко не всеобъемлющий бенчмарк и по его результатам нельзя делать выводы о производительности всей платформы. Тем не менее.

• Скорость M1 без векторизации впечатляет. Это при том, что частота обоих чипов примерно одинаковая.

• Упс, авто векторизация на x86 не сработала на обоих компиляторах. А случай всё ещё простейший.

• Несмотря на огромное количество кода в цикле (напомню, 23 инструкции против 10), x86 заметно сильнее ускоряется от векторизации. Это можно объяснить большим количеством исполнительных блоков для целочисленных вычислений внутри каждого ядра или более оптимальным микрокодом.

• Хоть 128-битная версия на M1 всё еще выполняется быстрее, чем на x86, против AVX ему нечего противопоставить.

На этом всё. Если нашли какие-то неточности, или знаете ещё что-то интересное о NEON и архитектуре ARM, делитесь в комментариях, обсудим вместе.