 |
И.Данилов vs В.Богданов (Dr.Web vs AVP):Programmer's Competition
- 23:11 - by z0mbie
|
 |
Глупость всегда заслуживает
высшей меры наказания...
Это глобальное исследование посвящено выявлению частного от
коэффициентов интеллекта указанных в названии статьи программистов -
антивирусописателей. Исследование будет проводиться косвенным путем, а
именно: богданову и данилову (зафиксированным на октябрьской базе и
версии 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.cjb.net
-----------------------------------------------------------------------------
|
||
 |
 |
 |
