Предположим, мы разрабатываем ассемблер. Абстрагируемся пока от всяких аццких алгоритмических и прочих штук, присущих программе компилятора, сосредоточившись на следующей задаче: - дан код(последовательность команд и меток). например: label1: jc label2 mov eax, ecx mov edx, eax test eax, ecx je label1 xor eax, ecx jne label2 ; ... label2: - у каждой инструкции (кроме переходов) известен размер. = нужен оптимальный алгоритм, определяющий для каждого перехода размер его команды (короткий переход или длинный переход). Вроде и просто, но пока не могу придумать. Всякие вырожденные случаи ломают все мои теории P.S. Не надо отсылать меня к гуглу и исходникам FASM и других ассемблеров. Во-первых, копаться в исходниках FASM долго и тоскливо, во-вторых, мне интересен ВАШ ход мыслей при решении этой задачи.
...здесь бы топологическую сортировку на графе зависимостей длин переходов друг от друга. но в графе могут быть циклы...
а тупо проанализировать адреса если label2-addr jc+2 < 80h => jc label2 = 2 байтам иначе если 16 бит, то если label2-addr jc+4 < 32768 => jc label2 = 4 байтам иначе ошибка (слишком далеко) с jmp тоже самое, но в зависимости от операндов может указываться тип например jmp 80:128 не куда не денешься только jmp ptrSeg:Off = 7 байтам
ну а предположить их максимального размера? и после проанализировать все 4-х байтные jcc переходы, у которых смещение меньше 0x0080+количество переходов между меткой и командой*2
а поподробнее можно насчет boost.graph? там стандартные алгоритмы реализованы, а проблема-то не в них. надо знать, как их применять в данном случае и стоит ли применять вообще.
Наивно предположить, что все переходы между меткой и командой маленькие? (ну раз умножаешь на 2) Предполагать можно всё, что угодно. Такие вот словесные описания могут нести в себе неоднозначность и вызывать недопонимание (к тому же в них неудобно вчитываться). Так что лучше ты, чтоб не быть голословным, предоставь конкретный алгоритм. Авось найдешь еще кучу ошибок...
или вот вам еще один подход. предполагаете, что длина инструкции перехода равна 0 и по возможности генерируете малый jcc. после генерации всех jcc корректируете на их длины все имеющиеся и изменяете маленькие на большие при необходимости. повторяете описанные действия до тех пор, пока не прекратятся корректировки или рекурсия не достигнет пика (допустим в 5 вложенностей, что для средней длины программы более чем достаточно, но если не хватит можно и увеличить)
luckysundog Оптимальный вриант который я применял для морфинга - двухпроходовый парсинг таблицы ветвлений. На первом проходе выполняется дизассемблирование кода и создание сырой таблицы ветвлений, где каждое ветвление определяет его адрес и положений до перехода в таблице. Второй проход - создание таблицы перекрёстных ссылок, в этой таблице каждый элемент определяет положение входа в первой таблице и содержит перекрётсную ссылку в обеих таблицах, что позволяет предельно просто трассировать таблицу и вычислять размер ветвлений. Последний проход - компиляция. Мб на днях выложу ик.
тему не видел до этого. процитирую оттуда: это по сути и есть топологическая сортировка. такое допущение не устраивает.
