I.Danilov vs V.Bogdanov (Dr.Web vs AVP): Programmer's Competition xlated from russian This is a global research of comparing IQ of two av programmers. Danilov and Bogdanov will be fixed on the october's base and version 4.20, after that we will send IDIV command to their input and analyze reaction in the form of the av emulator. Now, the problem description. There are two instructions: DIV and IDIV, performing unsigned and signed division. And there are three forms of each instruction, depending on the size of the divisor: BYTE, WORD or DWORD. Dividend, whose precision is twice larger, is represented in the fixed registers: AX, DX:AX or EDX:EAX. Quotient and remainder are returned in AL:AH, AX:DX or EAX:EDX registers. Because precision of the dividend is twice larger than quoitient's one, there are several situations, when produced result is larger than output register, so result cant be returned, and then CPU generates overflow exception (EXCEPTION_INT_OVERFLOW). Also, there is division-by-zero exception (EXCEPTION_INT_DIVIDE_BY_ZERO), but, it is simple enough to speak about. It is clear, that program emulating DIV and IDIV commands by means of direct execution, must avoid exception in the own code, by means of input registers checking. This checking is a subject of the following disasm. ============================================================================= Danilov's emulator: drweb32.dll ============================================================================= emul_flags = ebp --------------------------------------------------------------------web/div8- emul_div8: mov ecx, edx ; cl = divisor and ecx, 0FFh ;; mov eax, emul_eax ; load emul regs and eax, 0FFFFh ; AX = dividend ;; or ecx, ecx ; div by 0 ? jz emul_div0 cmp ah, cl ; dividend.Hi >= divisor jae emul_div0 ;; xor edx, edx ; prepare to division ;; push emul_flags ; division emulation popf div cx pushf pop emul_flags ;; cmp eax, 0FFh ; overflow check ja emul_div0 ;; mov emul_al, al ; save emul regs mov emul_ah, dl ;; jmp emul_complete -------------------------------------------------------------------web/div16- emul_div16: mov ecx, edx ; cx <- divisor and ecx, 0FFFFh ;; mov eax, emul_eax ; load emul regs and eax, 0FFFFh ; DX:AX = dividend mov edx, emul_edx and edx, 0FFFFh ;; or ecx, ecx ; div by 0 ? jz emul_div0 cmp edx, ecx ; dividend.Hi >= divisor jae emul_div0 ;; shl edx, 10h ; prepare to division mov dx, ax ; EDX:EAX <-- dx:ax mov eax, edx xor edx, edx ;; push emul_flags ; division emulation popf div ecx pushf pop emul_flags ;; cmp eax, 0FFFFh ; overflow check ja emul_div0 ;; mov emul_ax, ax ; save emul regs mov emul_dx, dx ;; jmp emul_complete -------------------------------------------------------------------web/div32- emul_div32: mov ecx, edx ; ecx <- divisor ;; mov eax, emul_eax ; load emul regs mov edx, emul_edx ; EDX:EAX = dividend ;; or edx, edx ; a bug jz emul_complete ; ; or ecx, ecx ; div by 0 ? jz emul_div0 cmp edx, ecx ; dividend.Hi >= divisor jae emul_div0 ;; push emul_flags ; division emulation popf div ecx pushf pop emul_flags ;; mov emul_eax, eax ; save emul regs mov emul_edx, edx ;; jmp emul_complete -------------------------------------------------------------------web/idiv8- emul_idiv8: movsx ecx, dl ; cl = dl = divisor ;; mov ax, emul_ax ; load emul regs ;; ; AX = dividend or ecx, ecx ; div by 0 ? jz emul_div0 ;; test dl, 80h ; abs(dl) jz @@1 neg dl @@1: ;; test ah, 80h ; abs(ah) jz @@2 ; AH = dividend.Hi 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 ; dividend, high bit set? jnz emul_div0 @@3: ;; mov ax, emul_ax ; prepare to division cwd ; DX:AX <-- AX ;; push emul_flags ; division emulation popf idiv cx pushf pop emul_flags ;; cmp ax, 7Fh ; overflow check ja emul_div0 ;; mov emul_al, al ; save emul regs mov emul_ah, dl ;; jmp emul_complete ------------------------------------------------------------------web/idiv16- emul_idiv16: movsx ecx, dx ; ecx = dx = divisor ;; mov ax, emul_dx ; ax = dividend.Hi ;; or ecx, ecx ; div by 0 ? jz emul_div0 ;; test dh, 80h ; abs(dx) jz @@1 neg dx @@1: ;; test ah, 80h ; abs(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 ; dividend.Lo, high bit set? jnz emul_div0 ; @@3: ;; mov eax, emul_eax ; load emul regs and eax, 0FFFFh mov edx, emul_edx and edx, 0FFFFh ;; or ecx, ecx ; div by 0 ? jz emul_div0 ; 2nd checking, for more reliability ;; shl edx, 10h ; prepare to division mov dx, ax ; EDX:EAX <-- dx:ax mov eax, edx cdq ;; push emul_flags ; division emulation popf idiv ecx pushf pop emul_flags ;; cmp eax, 7FFFh ; overflow check ja emul_div0 ;; mov emul_ax, ax ; save emul regs mov emul_dx, dx ;; jmp emul_complete ------------------------------------------------------------------web/idiv32- emul_idiv32: mov emul_eax, 0 ; this is cool mov emul_edx, 0 ;; jmp emul_complete ----------------------------------------------------------------------------- ============================================================================= Bogdanov's emulator: kernel.avc/emul.obj ============================================================================= divisor = ebx --------------------------------------------------------------------avp/div8- emul_div8: cmp byte ptr [divisor], 0 ; div by 0 ? jz emul_int0 ;; mov ax, emul_ax ; load emul regs ;; ; AX = dividend cmp ah, [divisor] ; dividend.Hi >= divisor jae try_emul_int0 ;; push emul_flags ; division emulation popfw div byte ptr [divisor] pushfw pop emul_flags ;; mov emul_ax, ax ; save emul regs ;; jmp emul_complete -------------------------------------------------------------------avp/div16- emul_div16: cmp word ptr [divisor], 0 ; div by 0 ? jz emul_int0 ;; mov ax, emul_ax ; load emul regs mov dx, emul_dx ; DX:AX = dividend ;; cmp dx, [divisor] ; dividend.Hi >= divisor jae try_emul_int0 ;; push emul_flags ; division emulation popfw div word ptr [divisor] pushfw pop emul_flags ;; mov emul_ax, ax ; save emul regs mov emul_dx, dx ;; jmp emul_complete -------------------------------------------------------------------avp/div32- emul_div32: cmp dword ptr [divisor], 0 ; div by 0 ? jz emul_int0 ;; mov eax, emul_eax ; load emul regs mov edx, emul_edx ; EDX:EAX = dividend ;; cmp edx, [divisor] ; dividend.Hi >= divisor jae try_emul_int0 ;; push emul_flags ; division emulation popfw div dword ptr [divisor] pushfw pop emul_flags ;; mov emul_eax, eax ; save emul regs mov emul_edx, edx ;; jmp emul_complete -------------------------------------------------------------------avp/idiv8- emul_idiv8: cmp byte ptr [divisor], 0 ; div by 0 ? jz emul_int0 ;; mov ax, emul_ax ; load emul regs ;; ; AX = dividend cmp ax, 80h ; dividend >= 80h jae emul_complete ;; push emul_flags ; division emulation popfw idiv byte ptr [divisor] pushfw pop emul_flags ;; mov emul_ax, ax ; save emul regs ;; jmp emul_complete ------------------------------------------------------------------avp/idiv16- emul_idiv16: cmp word ptr [divisor], 0 ; div by 0 ? jz emul_int0 ;; mov ax, emul_ax ; load emul regs mov dx, emul_dx ; DX:AX = dividend ;; cmp dx, 0 ; dividend.Hi = 0 jnz emul_complete cmp ax, 8000h ; dividend.Lo >= 8000h jae emul_complete ;; push emul_flags ; division emulation popfw idiv word ptr [divisor] pushfw pop emul_flags ;; mov emul_ax, ax ; save emul regs mov emul_dx, dx ;; jmp emul_complete ------------------------------------------------------------------avp/idiv32- emul_idiv32: cmp dword ptr [divisor], 0 ; div by 0 ? jz emul_int0 ;; mov eax, emul_eax ; load emul regs mov edx, emul_edx ; EDX:EAX = dividend ;; cmp edx, 0 ; dividend.Hi = 0 jnz emul_complete cmp eax, 80000000h ; dividend.Lo >= 2^31 jae emul_complete ;; push emul_flags ; division emulation popfw idiv dword ptr [divisor] pushfw pop emul_flags ;; mov emul_eax, eax ; save emul regs mov emul_edx, edx ;; jmp emul_complete ----------------------------------------------------------------------------- Now, some comments. From the 12 subroutines alogorithmically-correct register-check has only 5 ones. All subroutines has correct or even redundand error-checking, so there is no way to fuckup 'em. Most of register combinations will be emulated incorrectly. 1. subroutines: div8 and div16 bogdanov: correct algorithm, minimal size of code danilov: algorithm is correct, but bogdanov has better one; code sucks. redundand overflow checking. 2. subroutine: div32 bogdanov: correct algorithm, minimal size of code danilov: incorrect algorithm, 'coz of bug; redundand erroneous zero-dividend checking. 3. subroutine: idiv8 bogdanov: incorrect algorithm - only 128 numbers (from 65536) will be divided. absent overflow-checking. danilov: incorrect algorithm, but a bit better than bogdanov's one; for example, AX=C0FF and CL=81 is IDIV-ided correctly, but emulator will begin INT 0 emulation 4. subroutine: idiv16 bogdanov: incorrect algorithm - only 32768 numbers (from 2^32) will be divided; absent overflow-checking. danilov: too many code; incorrect algorithm, but a bit better than bogdanov's one for example, DX=C000, AX=FFFF, CX=8001 are IDIV-ided ok, but drweb emulates INT 0 5. subroutine: idiv32 bogdanov: incorrect algorithm, only 80000000h numbers (from 2^64) will be divided; absent overflow-checking. danilov: completely absent ----------------------------------------------------------------------------- Competition results. Nobody emulated IDIV correctly. subroutines: total programmed correct incorrect bogdanov 6 6 3 3 danilov 6 5 2 3 But, danilov gives as a hope, that sometimes... sometimes he will write correct emulator. As it seems, his code was modifed several times, he even tried to do such things as overflow checking and zero-dividend checking. Also, register checking before IDIV are looking as stealed from somewhere, but with errors. From the other side, bigdanov's emulator works only with 1% of possible number combinations, so it has no overflow checking. So, DANILOV wins! ----------------------------------------------------------------------------- And here is some bonus: ----------------------------------------------------------------------------- subroutine: IDIV emulation, returns CF=1 instead of INT 0. ; input: EDX:EAX = dividend ; ECX = divisor ; output: CF = 0 -- all ok, EAX = quotient, EDX = remainder ; CF = 1 -- error (div0 or overflow) 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 ----------------------------------------------------------------------------- That's all! (x) 2000 Z0MBiE http://z0mbie.host.sk -----------------------------------------------------------------------------