Полиморфный код удобно использовать в вирусах, механизмах защиты прог. от копирования, и как ни странно для оптимизации. По крайней мере это относится к процам архитектуры IA32(x86). Использование полиморфного кода для них позволяет существенно экономить регистры общего назначения. Использовать эту оптимизацию я начал при создании утилиты WGC (аналог Artmoney & TSearch). Задача ставилась такая: как можно быстрее находить вхождения образца в некоторый буффер, используя тип значения и условия поиска (типа > < = !=). Писать отдельные функции на каждый вариант поиска меня не устраивало, поэтому я решил сделать одну полиморфную функцию. Перед началом цикла поиска/отсева изменялись команды сравнения, условного перехода и адресации.
Адресоваться к динамически выделенному буфферу, используя косвенную адресацию типа: mov ecx, [edi + eax] при дефиците регистров я не стал. Записал просто mov ecx, [eax + 12345678h], а перед циклом число 12345678h заменял на адрес буффера, таким образом экономя регистр.
В настоящий момент программа до конца не оптимизирована, но даже не смотря на это поиск достигает 120Mb/s (на Athlon 2000+@1666;512DDR333) , включая упаковку найденых смещений, выделение буферов памяти. Собираюсь развернуть циклы в скором времени.
Что бы не было исключительных ситуаций при записи в область кода, ее приходится разрешать для записи функцией VirtualProtect.

а где вопрос? или это просто информация к сведению? :)

Точнее было бы назвать это не полиморфизмом, а небольшой самомодификацией, IMHO

>2 Funbit
просто информация, сам я в поисках инфы по этой теме никуда не ушел. Надеюсь кто поопытнее поделится своим опытом оптимизации в условиях ограниченых ресурсов ЦП.
> B_108
можно и так назвать, мне важен результ.

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

Вот что пишет сам производитель процессора:

AMD Athlon™ Processor x86 Code Optimization Guide

„Avoid Placing Code and Data in the Same 64-Byte Cache Line
✩ Sharing code and data in the same 64-byte cache line may cause
the L1 caches to thrash (unnecessary castout of code/data) in
order to maintain coherency between the separate instruction
and data caches. The AMD Athlon processor has a cache-line
size of 64 bytes, which is twice the size of previous processors.
Avoid placing code and data together within this larger cache
line, especially if the data becomes modified.

For example, consider that a memory indirect JMP instruction
may have the data for the jump table residing in the same
64-byte cache line as the JMP instruction. This mixing of code
and data in the same cache line would result in lower
performance.

Although rare, do not place critical code at the border between
32-byte aligned code segments and a data segments. Code at
the start or end of a data segment should be executed as
seldomly as possible or simply padded with garbage.

In general, avoid the following:
■ Self-modifying code
■ Storing data in code segments“

У intel тоже самое.

(Кстати, многие компиляторы вопреки этому правилу помещают jump table для switch вблизи самого перехода..)


> „Писать отдельные функции на каждый вариант поиска меня не устраивало, поэтому я решил сделать одну полиморфную функцию. “

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


Ещё, более компактный код вроде

mov ecx, [edi + eax]

будет в некоторых случаях работать быстрее, чем

mov ecx, [eax + 12345678h]


Если кажется что мало регистров, можно использовать EBP и ESP для хранения данных.
А так же MMX - последними и поиск иногда делать удобнее.



> „Что бы не было исключительных ситуаций при записи в область кода, ее приходится разрешать для записи функцией VirtualProtect“

Можно задать атрибут записи для секции кода при линковке.


Скорость чтения памяти Athlon 2000+@1666 на DDR 266 1350Mb/s; на DDR333 думаю столько же будет, тест в аттаче.
для поиска наверное не реально, но есть к чему стремиться.

_1698994866__read_test.exe

2> S_T_A_S_


„Можно одну функцию "размножить" с необходимыми модификациями перед стартом программы - это позволит избежать проблем с кешем.“

Действительно можно: имеем следующее количество функций для (BYTE, WORD, DWORD) x (> < = <> >= <=) т. е. 18 реализаций функций. В коде это относительно мало, но не позволяет использовать ассемблерные вставки (если "размножить" текст - его тяжело будет потом изменять), т. е. придется использовать асм и макросы.

„Хотя, конечно, если цикл довольно долгий, разницы большой не будет.“

Цикл обычно выполняется для буффера в 64К. Затраты на самомодификацию - примерно по 300 тактов на каждое изменение кода, а их у меня бывает от 3 до 5, значит максимальный проигрыш 1500 тактов. Если ведется поиск в процессе на 64Мб, всего будет проиграно 1,5 млн. тактов - не очень заметно по сравнению с другими потерями. Если же в программе один запрос или
запросы по критериям одинаковы, модификацию кода можно выполнить перед началом поиска/отсева.

„Ещё, более компактный код вроде
mov ecx, [edi + eax]
будет в некоторых случаях работать быстрее, чем
mov ecx, [eax + 12345678h]
“

Хорошо бы, но практика показала другое. У последнего варинта кода время выполнения было немного меньше чем у первого.

„
Если кажется что мало регистров, можно использовать EBP и ESP для хранения данных.
А так же MMX - последними и поиск иногда делать удобнее.
“

Отнюдь не кажется, в алгоритмах отсева, особенно текстовых значений регистров едва хватает включая ebp. А что до MMX, то и до него дотянусь, на старых компах мою прогу едва - ли кто использует.

„
Можно задать атрибут записи для секции кода при линковке.
“

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

„Скорость чтения памяти Athlon 2000+@1666 на DDR 266 1350Mb/s;“
Здесь ограничители другие: ReadProcessMemory в частности и GetMem/FreeMem. Покрайней мере если я комментирую функцию поиска, скорость возрастает аж до 250Mb/s. С другой стороны и в самом деле задел просто огромный, простую оптимизацию я посути не выполнял вообще. Особенно медленно должен выполнятся поиск значений DWORD - при инкременте указателя на 1 не раз пересекаются границы кэш линеек. В принципе можно и отказаться от инкремента на 1 - но вполне вероятно что в играх значения могут быть не выровнеными.

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

2143469732__ChAlgs.zip

[offtop]
S_T_A_S_ аттач не грузиться на w2ksp4 , Exception C000012D (COMMITMENT LIMIT) , что это может значить ?

alpet > „В коде это относительно мало, но не позволяет использовать ассемблерные вставки (если "размножить" текст - его тяжело будет потом изменять), т. е. придется использовать асм и макросы. “

Я имел ввиду при запуске программы, выделить память с PAGE_EXECUTE и туда скопировать один код 18 раз, а потом каждый вариант подправить 1 раз и вызывать именно эти кусочки.
2е правило оптимизации - выносим всё что можно за циклы ;-)


> „Хорошо бы, но практика показала другое. У последнего варинта кода время выполнения было немного меньше чем у первого. “

Вообще в теории, время выполнения этих команд одинаково. В той же теории рекомендуется использовать команды, размер опкодов которых меньше - это лучше для декодера. На практике же результат будет зависеть больше от других факторов - от выравнивания циклов, располагается ли опкод на пересечении границ строк кеша или нет. Так что если не учитывать эти факторы, то результаты могут расходиться с теорией. Существует хорошая тулза для анализа таких вещей AMD CodeAnalyst, но для програм на Delphi она будет бесполезна..


„Не пробывал, для Delphi я использовал то что знал на тот момент. “

Не уверен, что в Delphi вообще возможно как-то повлиять на секции PE файла, так что VirtualProtect тут вполне логично. Вариант - заюзать PE tools и исправить атрибуты у готового exe, но это не удобно.


> „Здесь ограничители другие: ReadProcessMemory в частности и GetMem/FreeMem.“

В некоторых случаях оптимизацию делать совсем бессмысленно (разве что для получения опыта) - т.к. тормоза совсем в другом месте - API никогда не отличалось скоростью. GetMem/FreeMem - это что-то из delphi ?


> „В принципе можно и отказаться от инкремента на 1 - но вполне вероятно что в играх значения могут быть не выровнеными.“

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


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

    lodsw
    movzx         eax, ax

Деление заменять умножением

    xor           edx, edx       // Подготовка к делению edx:eax / 10
    div           ecx            // V = V / 10


MagicNumber = 3435973837
mov eax,X
mov edx, MagicNumber
mul edx
SHR edx, 3

Так же pop лучше вообще по возможности избегать - медленно.


Если нужна скорость IMHO лучше не делать универсальную ф-цию для поиска byte/word/dword - специализированные варианты могут работать в разы быстрее иза-распараллеливания. См. Сравнение одним махом



bogrus
„аттач не грузиться на w2ksp4 , Exception C000012D (COMMITMENT LIMIT) , что это может значить ?“

Интересно.. w2k Без SP работает. Наверное не нравится, что VirtualSize у секции кода слишком большой.
Переделал, теперь есть вариант с VirtualAlloc (сорри, сорцы наспех выдраны из другого места)

_1750614076__2.zip

S_T_A_S_ „Наверное не нравится, что VirtualSize у секции кода слишком большой. “

Да действительно , начал его менять 00F01000 - не хочет , 00201000 - выдало "типа свободная виртуальная память заканчиваеться , будет увеличена ..." и заработала , потом снова 00F01000 - работает , а 06001000 не хочет . Видимо от размера свопа зависит .

S_T_A_S_„В некоторых случаях оптимизацию делать совсем бессмысленно (разве что для получения опыта) - т.к. тормоза совсем в другом месте - API никогда не отличалось скоростью. GetMem/FreeMem - это что-то из delphi ?“

ReadProcessMemory - самый главный тормоз, из-за него не раз приходится переключаться между режимом ядра и двумя процессами. Решения два:
1. Использовать как можно реже, в идеале копировать память за раз (это правда нереально из-за фрагментированности виртуальной памяти процесса и физической компа). Не достаток - программа будет "зависать" на время копирования, и наверное потребуется физическая память для копирования между процессами, размером равная копируемым регионам.
2. Искать изнутри чужого процесса. Данная возможность в принципе реализована и показывает небольшой прирост производительности. Другое дело что при инфильтрации dll в чужой процесс, код начинает глючить, некоторые типы поиска и вовсе не работают.

GetMem/FreeMem & New/Delete управляют в Delphi кучей. Быстро, но не идеально, при чем иногда наблюдается рост занимаемой программой памяти (это зависит чисто от Windows), хотя внутри проги все высвобождается вовремя.
Идеи как написать свой менеджер памяти у меня есть, и в нем я тоже думаю применить динамический код.

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

Похоже что для указаного кода, есть решение без потери тактов. Штрафные такты ведь возникают при остановках конвейера, после каждой попытке записи в область кода. Областью кода при этом считается, все что попало в кодовый кэш L1. Значит если модификация производится до выполнения функции (т.е. ее код отсутсвует в L1), процу не надо будет сбрасывать конвейер - он отнесется к коду, как к данным. Возникает задача - после модификации код надо вытеснить из L1.DATA кэша в L2, что бы оттуда он загрузился, при вызове функции, в L1.CODE. Для процессоров AMD Athlon c exlusiv'ной архитектурой кеш памяти, это проблем не представляет, надо просто забить L1.DATA.

По read_test.exe. Сейчас мне до Athlona не добраться, проверил на iCel2400: макс. результат - 1605Ms/s. Скорость поиска колеблется от 100 до 115Мб/с.