И.Данилов vs В.Богданов (Dr.Web vs AVP): Programmer's Competition Глупость всегда заслуживает высшей меры наказания... Это глобальное исследование посвящено выявлению частного от коэффициентов интеллекта указанных в названии статьи программистов - антивирусописателей. Исследование будет проводиться косвенным путем, а именно: богданову и данилову (зафиксированным на октябрьской базе и версии 4.20) подадим на вход команду IDIV, а затем изучим их реакцию в виде эмуляторов этой команды. Hо сначала о сути проблемы. Существуют ассемблерные команды DIV и IDIV, выполняющие деление -- беззнаковое и со знаком. Hа вход командам подается делимое, находящееся в регистрах AX либо DX:AX либо EDX:EAX, и делитель, находящийся в байте, ворде либо дворде соответственно. Частное и остаток от деления возвращаются в регистрах AL:AH, AX:DX либо EAX:EDX. Поскольку разрядность делимого в два раза больше возможной разрядности частного, то возникает ряд ситуаций, когда процессор вместо деления генерирует исключения по переполнению (EXCEPTION_INT_OVERFLOW) либо по делению на 0 (EXCEPTION_INT_DIVIDE_BY_ZERO). Ясно, что эмулятор, эмулирующий команды DIV и IDIV через непосредственное их выполнение, должен избежать генерации исключений в собственном коде, выполнив перед делением ряд проверок. Собственно об этих проверках в эмуляторах мы и будем говорить дальше. ============================================================================= эмулятор от г-на Данилова: drweb32.dll ============================================================================= emul_flags = ebp --------------------------------------------------------------------web/div8- emul_div8: mov ecx, edx ; cl = делитель and ecx, 0FFh ;; mov eax, emul_eax ; загрузим эмулируемые регистры and eax, 0FFFFh ; AX = делимое ;; or ecx, ecx ; деление на 0 ? jz emul_div0 cmp ah, cl ; старшая часть делимого >= делителю jae emul_div0 ;; xor edx, edx ; подготовимся к делению ;; push emul_flags ; эмуляция деления popf div cx pushf pop emul_flags ;; cmp eax, 0FFh ; проверка на переполнение ja emul_div0 ;; mov emul_al, al ; сохраним эмулируемые регистры mov emul_ah, dl ;; jmp emul_complete -------------------------------------------------------------------web/div16- emul_div16: mov ecx, edx ; cx <- делитель and ecx, 0FFFFh ;; mov eax, emul_eax ; загрузим эмулируемые регистры and eax, 0FFFFh ; DX:AX = делимое mov edx, emul_edx and edx, 0FFFFh ;; or ecx, ecx ; деление на 0 ? jz emul_div0 cmp edx, ecx ; старшая часть делимого >= делителю jae emul_div0 ;; shl edx, 10h ; подготовимся к делению mov dx, ax ; EDX:EAX <-- dx:ax mov eax, edx xor edx, edx ;; push emul_flags ; эмуляция деления popf div ecx pushf pop emul_flags ;; cmp eax, 0FFFFh ; проверка на переполнение ja emul_div0 ;; mov emul_ax, ax ; сохраним эмулируемые регистры mov emul_dx, dx ;; jmp emul_complete -------------------------------------------------------------------web/div32- emul_div32: mov ecx, edx ; ecx <- делитель ;; mov eax, emul_eax ; загрузим эмулируемые регистры mov edx, emul_edx ; EDX:EAX = делимое ;; or edx, edx ; досадная бага. а EAX как же ? jz emul_complete ; и вообще зачем это. ; or ecx, ecx ; деление на 0 ? jz emul_div0 cmp edx, ecx ; старшая часть делимого >= делителю jae emul_div0 ;; push emul_flags ; эмуляция деления popf div ecx pushf pop emul_flags ;; mov emul_eax, eax ; сохраним эмулируемые регистры mov emul_edx, edx ;; jmp emul_complete -------------------------------------------------------------------web/idiv8- emul_idiv8: movsx ecx, dl ; cl = dl = делитель ;; mov ax, emul_ax ; загрузим эмулируемые регистры ;; ; AX = делимое or ecx, ecx ; деление на 0 ? jz emul_div0 ;; test dl, 80h ; вычислить абсолютное значение (dl) jz @@1 neg dl @@1: ;; test ah, 80h ; вычислить абсолютное значение (ah) jz @@2 ; AH = старшая часть делимого neg ah @@2: ;; sub dl, ah ; dl <= ah * 2 jb emul_div0 cmp dl, ah jbe emul_div0 ;; sub dl, ah ; dl - ah * 2 != 1 cmp dl, 1 jnz @@3 test al, 80h ; делимое, старший бит, установлен? jnz emul_div0 @@3: ;; mov ax, emul_ax ; подготовимся к делению cwd ; DX:AX <-- AX ;; push emul_flags ; эмуляция деления popf idiv cx pushf pop emul_flags ;; cmp ax, 7Fh ; проверка на переполнение ja emul_div0 ;; mov emul_al, al ; сохраним эмулируемые регистры mov emul_ah, dl ;; jmp emul_complete ------------------------------------------------------------------web/idiv16- emul_idiv16: movsx ecx, dx ; ecx = dx = делитель ;; mov ax, emul_dx ; ax = старшая часть делимого ;; or ecx, ecx ; деление на 0 ? jz emul_div0 ;; test dh, 80h ; вычислить абсолютное значение (dx) jz @@1 neg dx @@1: ;; test ah, 80h ; вычислить абсолютное значение (ax) jz @@2 neg ax @@2: ;; sub dx, ax ; if (dx <= ax * 2) div0 jb emul_div0 cmp dx, ax jbe emul_div0 ;; sub dx, ax ; if (dx - ax * 2) != 1 { ... cmp dx, 1 jnz @@3 test emul_ah, 80h ; младшая часть делимого, старший бит jnz emul_div0 ; установлен? @@3: ;; mov eax, emul_eax ; загрузим эмулируемые регистры and eax, 0FFFFh mov edx, emul_edx and edx, 0FFFFh ;; or ecx, ecx ; деление на 0 ? jz emul_div0 ; повторная проверка, для надежности ;; shl edx, 10h ; подготовимся к делению mov dx, ax ; EDX:EAX <-- dx:ax mov eax, edx cdq ;; push emul_flags ; эмуляция деления popf idiv ecx pushf pop emul_flags ;; cmp eax, 7FFFh ; проверка на переполнение ja emul_div0 ;; mov emul_ax, ax ; сохраним эмулируемые регистры mov emul_dx, dx ;; jmp emul_complete ------------------------------------------------------------------web/idiv32- emul_idiv32: mov emul_eax, 0 ; элегантное решение проблемы mov emul_edx, 0 ;; jmp emul_complete ----------------------------------------------------------------------------- ============================================================================= эмулятор от г-на (ага, то что вы подумали) Богданова: kernel.avc/emul.obj ============================================================================= divisor = ebx --------------------------------------------------------------------avp/div8- emul_div8: cmp byte ptr [divisor], 0 ; деление на 0 ? jz emul_int0 ;; mov ax, emul_ax ; загрузим эмулируемые регистры ;; ; AX = делимое cmp ah, [divisor] ; старшая часть делимого => делителю jae try_emul_int0 ;; push emul_flags ; эмуляция деления popfw div byte ptr [divisor] pushfw pop emul_flags ;; mov emul_ax, ax ; сохраним эмулируемые регистры ;; jmp emul_complete -------------------------------------------------------------------avp/div16- emul_div16: cmp word ptr [divisor], 0 ; деление на 0 ? jz emul_int0 ;; mov ax, emul_ax ; загрузим эмулируемые регистры mov dx, emul_dx ; DX:AX = делимое ;; cmp dx, [divisor] ; старшая часть делимого => делителю jae try_emul_int0 ;; push emul_flags ; эмуляция деления popfw div word ptr [divisor] pushfw pop emul_flags ;; mov emul_ax, ax ; сохраним эмулируемые регистры mov emul_dx, dx ;; jmp emul_complete -------------------------------------------------------------------avp/div32- emul_div32: cmp dword ptr [divisor], 0 ; деление на 0 ? jz emul_int0 ;; mov eax, emul_eax ; загрузим эмулируемые регистры mov edx, emul_edx ; EDX:EAX = делимое ;; cmp edx, [divisor] ; старшая часть делимого => делителю jae try_emul_int0 ;; push emul_flags ; эмуляция деления popfw div dword ptr [divisor] pushfw pop emul_flags ;; mov emul_eax, eax ; сохраним эмулируемые регистры mov emul_edx, edx ;; jmp emul_complete -------------------------------------------------------------------avp/idiv8- emul_idiv8: cmp byte ptr [divisor], 0 ; деление на 0 ? jz emul_int0 ;; mov ax, emul_ax ; загрузим эмулируемые регистры ;; ; AX = делимое cmp ax, 80h ; делимое >= 80h jae emul_complete ;; push emul_flags ; эмуляция деления popfw idiv byte ptr [divisor] pushfw pop emul_flags ;; mov emul_ax, ax ; сохраним эмулируемые регистры ;; jmp emul_complete ------------------------------------------------------------------avp/idiv16- emul_idiv16: cmp word ptr [divisor], 0 ; деление на 0 ? jz emul_int0 ;; mov ax, emul_ax ; загрузим эмулируемые регистры mov dx, emul_dx ; DX:AX = делимое ;; cmp dx, 0 ; старшая часть делимого = 0 jnz emul_complete cmp ax, 8000h ; младшая часть делимого >= 8000h jae emul_complete ;; push emul_flags ; эмуляция деления popfw idiv word ptr [divisor] pushfw pop emul_flags ;; mov emul_ax, ax ; сохраним эмулируемые регистры mov emul_dx, dx ;; jmp emul_complete ------------------------------------------------------------------avp/idiv32- emul_idiv32: cmp dword ptr [divisor], 0 ; деление на 0 ? jz emul_int0 ;; mov eax, emul_eax ; загрузим эмулируемые регистры mov edx, emul_edx ; EDX:EAX = делимое ;; cmp edx, 0 ; старшая часть делимого = 0 jnz emul_complete cmp eax, 80000000h ; младшая часть делимого больше 2^31 jae emul_complete ;; push emul_flags ; эмуляция деления popfw idiv dword ptr [divisor] pushfw pop emul_flags ;; mov emul_eax, eax ; сохраним эмулируемые регистры mov emul_edx, edx ;; jmp emul_complete ----------------------------------------------------------------------------- Hу вот, дизассемблированные эмуляторы кончились. Прокомментирую, что же я здесь увидел. Из 12 процедур 100% алгоритмически грамотные проверки присутствуют только в 5-ти. Хотя, конечно, проверки на наябки есть везде, и ни одного ошибочного варианта пропущено не будет. Однако вместе с ошибочными вариантами в большинстве случаев отсекаются и нормальные комбинации чисел. 1. Подпрограммы div8 и div16 богданов: алгоритм правильный; код минимальный данилов: алгоритмически, хотя и правильно, но кривовато, так как можно было сделать куда проще, например как у богданова; соответственно большой и хреновый код и, хотя и радует программистская смекалка: (вместо байтов поделил ворды, а вместо вордов - дворды), но зачем сделал проверки на переполнение? не будет его. 2. Подпрограмма div32 богданов: алгоритм правильный; код минимальный данилов: и алгоритм и код почти как у богданова, но - неправильно, и все из-за каких-то двух ошибочных команд. видно, данилов решил выпендриться - и сделал ненужную здесь проверку на нулевое делимое... а вышел баг. 3. Подпрограмма idiv8 богданов: алгоритм неправильный. делит только числа меньше 128 (а их 65536), нет проверки на переполнение данилов: алгоритм неправильный, хотя и несколько лучше чем у богданова, ибо видна работа мозга. однако, при AX=C0FF и, скажем, CL=81, команда IDIV выполнится нормально, а веб перейдет к эмуляции INT0 4. Подпрограмма idiv16 богданов: алгоритм неправильный. делит только числа меньше 32768 (а их 2^32), нет проверки на переполнение данилов: слишком много кода; алгоритмически неправильно, хотя опять же, лучше чем у богданова, ибо видны потуги сделать как надо; однако, при DX=C000, AX=FFFF, и, скажем, CX=8001, команда IDIV выполнится нормально, а веб перейдет к эмуляции INT0 5. Подпрограмма idiv32 богданов: алгоритмически неправильно, так как делит только числа меньше 80000000h, а их 2^64, и нет проверки на переполнение данилов: процедура отсутствует напрочь. ----------------------------------------------------------------------------- Итоги программерского компетишена. Правильные процедуры с командой IDIV не смог написать никто. Придется теперь откуда-нибудь спиздить, но это ничего. процедуры: всего реализовано правильно неправильно богданов 6 6 3 3 данилов 6 5 2 3 Однако, данилов подает надежды, что не все потеряно: видны попытки написать правильный код, причем ясно, что изменения вносились несколько раз; есть даже такие умные вещи, как проверка на переполнение, попытка проверки на нулевое делимое, и нечто - уже совсем близкое - к корректной проверке перед IDIV-ом. Касательно этой проверки перед IDIV-ом, надо сказать, что - весьма похоже - что это все откуда-то неправильно содрано. Hо нам важно не это. С другой же стороны, у богданова, хотя и реализованы все процедуры, обрабатываются меньше 1% всех возможных комбинаций чисел и нет ни одной проверки на переполнение. ----------------------------------------------------------------------------- В итоге, выигрывает Данилов! Эпизод 1. Богданов, согнувшись, придерживая руками шляпу, прыжками сбегает по лестнице, в надежде достичь выхода. Hо не тут-то было. И вот его, пурпурно-красного, изрыгающего страшные проклятия, царапающего когтями пол, упирающегося, дрыгающегося и разбрызгивающего в разные стороны ядовитые сопли, за ноги подтаскивают к дверям (вниз - ступеньки), берут за руки/ноги, медленно раскачивают... нет, это уже было... ставят раком, и с разбегу дают ОХУИТЕЛЬHОГО пинка, от чего он, приобретя ускорение, грациозно пролетает несколько метров, и, наебнувшись на ступеньках, раскинув в стороны руки, падает в лужу. Раздается всплеск... По луже идут круги... Осень, вечер, дует холодный ветер и падает мокрый снег... Эпизод 2. Промокший богданов, на коленях стоя в луже, преданно смотрит наверх, на полузакрывшуюся дверь, из которой его только что выкинули. Крупным кадром: слеза скатывается по небритой щеке. Вдруг дверь открывается, и из нее медленно, тоже от пинка, вылетает коробка дискет с исходниками кривого эмулятора, в верхней точке своего полета зависает и прицельно опускается на богданова. Свет меркнет. ----------------------------------------------------------------------------- Теперь резонно рассказать, нахрена я за это взялся. Все дело в том, что мне тоже понадобилось выяснить, можно ли выполнять команду IDIV (для двордов), в процессе переделывания движка KME. Посмотрев в эмуляторы от авп и веба, я понял, что богданов с даниловым оба полные лохи... а еще я тогда подумал, что неплохо бы было написать вот эту самую статью. А потом решил проэмулировать команду IDIV целиком. А хули? ----------------------------------------------------------------------------- Подпрограмма, эквивалентная команде IDIV, возвращает CF=1 вместо INT0. ; input: EDX:EAX = делимое ; ECX = делитель ; output: CF = 0 -- все окей, EAX = частное, EDX = остаток ; CF = 1 -- ошибка (0 либо переполнение) emul_idiv: pusha xor bh, bh or ecx, ecx jz __div_err jg __g1 neg ecx or bh, 1 __g1: or edx, edx jge __g2 neg edx neg eax sbb edx, 0 xor bh, 3 __g2: xor esi, esi ; d xor edi, edi ; m mov bl, 64 __divcycle: shl esi, 1 ; d <<= 1 jc __div_err shl eax, 1 ; x <<= 1 rcl edx, 1 rcl edi, 1 ; m = (m << 1) | x.bit[i] jc __cmpsub cmp edi, ecx jb __cmpsubok __cmpsub: sbb edi, ecx or esi, 1 __cmpsubok: dec bl jnz __divcycle or esi, esi js __div_err or edi, edi js __div_err test bh, 1 jz __skipneg1 neg esi __skipneg1: test bh, 2 jz __skipneg2 neg edi __skipneg2: mov [esp+7*4], esi mov [esp+5*4], edi popa clc retn __div_err: popa stc retn ----------------------------------------------------------------------------- Hу вот собственно и все... А вы чего ждали? (x) 2000 Z0MBiE http://z0mbie.host.sk -----------------------------------------------------------------------------