мультипардон за непереведенные комментарии в блоке кода Код (Text): ;enu: ;thoughts on int64 division when dvs.hi <> 0 ;2011_05_19, edemko@rambler.ru ;___________________________________________ ;32bit machine allows division of edx:eax dividend by 32bit divisor ;we are keen on using that fact to divide unsigned int64 by int64 ; ;reminder: same mul or div, applied to numerator(dividend) and denominator(divisor), ;do not change output ;indeed 200 200/100 2 ; --- =2= ------- =-= ... ; 100 100/100 1 ; ;can said be used in binary? ;why not 1000b 1000b/10b 100b ; ----- =100b= --------- =----= ... ; 0010b 0010b/10b 001b ; ;is that difficult? ;imagine small and big apple, cut each in-two - you've got 4 parts of 2 apples: 2 small and 2 big ;the pairs differ in scale only, each producing 1 on merge ;do not take numbers strict :) ; ;reminder: that's integer division cpu commonly does with DIV ; ;ok, scaling may be applied ;fake supposing: using scaling, we can reduce $ffff'ffff'ffff'ffff / $0000'0001'ffff'ffff to $ffff'ffff / $0000'0001? ;no, as the simplest proof: 99 9 100 ; -- -> - = 9 <> ~ --- ~ 5 ; 19 1 20 ; ;edx:eax = dvd & ecx:ebx = dvs ; ;reminder: after division cpu expects result to be a 32 bit value to put remainder into edx register ;there, hence, must be such dvd & dvs performation that no overflow ever occurs ;let it be dvd=$ffff'ffff'ffff'ffff and dvs made 32bit value somehow ;then dvs being $8000'0000 causes overflow: $ffff'ffff'ffff'ffff / $8000'0000 = ; = $ffff'ffff'ffff'ffff / 2^31 = ; = $ffff'ffff'ffff'ffff shr 31 = $0000'0001'ffff'ffff <- an odd shift somewhere required ;we should not decrease dvs any more(64->32 bits is a loss) ;relax, i was a bit lying about existence of an uprerformed dvd=$ffff'ffff'ffff'ffff and somehow performed dvs=$8000'0000 ;and an odd shift somewhere required ;this is where scaling required, proportions to retain: ;initial dvd=$ffff'ffff'ffff'ffff ;initial dvs=$0000'1000'1000'0001 etc as making it 32bit, low DWord gets lost partially or totally ;bsr number_of_shifts_right,dvs gives 12 i.e. 12+1 shifts right required to make dvs 32bit value ;dvs shr 13(mind cpu supports 31 max) = $0000'0000'8000'8000 ;dvd shr 13(mind cpu supports 31 max) = $0007'ffff'ffff'ffff ; ;"low DWord gets lost partially or totally" ;initial dvd=$8000'0000'0000'0000 -> shr 31 -> $0000'0001'0000'0000|lost $0000'0000 \ ;initial dvs=$4000'0000'0000'0001 -> shr 31 -> $8000'0000|lost $0000'0001 /results into 2 ;reminder: compare low DWords of dvd & dvs before scaling ;in our case 0 < 1, that's why result = 2 - flags'cf = sbb 2,0 = 1 ; ;how precise results of such scaling are? ;max performed dvd = $7fff'ffff'ffff'ffff ~\ 2^63 ~\ ;min performed dvs = $0000'0000'8000'0000 ~/ 2^31 ~/ 2^(63-31) ~ 2^32 ;THAT'IS WHY LOW DWORDS MUST BE COMPARED BEFORE PERMUTATION/SCALING TO FIX FUTURE OUTPUT ;rus: ;домыслы об int64-делении при dvs.hi <> 0 ;2011_05_19, edemko@rambler.ru ;___________________________________________ ;32bit'ный процессор может делимое в edx:eax разделить на 32bit'ный делитель ;этого достаточно для реализации int64 на int64 ; ;помни: фактор(умножение или деление), примененный к числителю(делимому) и знаменателю(делителю), конечный результат не изменит ; 200 200/100 2 ; --- =2= ------- =-= ... ; 100 100/100 1 ; ;с двоичной также: ; 1000b 1000b/10b 100b ; ----- =100b= --------- =----= ... ; 0010b 0010b/10b 001b ; ;трудно? ;оторви кусок туалетки и сложи вдвое ;возьми листок еще, сложи вдвое ;получилось 2 пары, где сумма элементов каждой = 1 ; ;помни: речь идет про целочисленное деление с помощью инструкции DIV ; ;масштабировать можно, выяснили ;предположим изменив масштаб коим образом, $ffff'ffff'ffff'ffff / $0000'0001'ffff'ffff свели к $ffff'ffff / $0000'0001? ;так нельзя: 99 9 100 ; -- -> - = 9 <> ~ --- ~ 5 ; 19 1 20 ; ;edx:eax = dvd & ecx:ebx = dvs ; ;помни: DIV не ожидает частного более 32 бит, поскольку edx предназначен для остатка ;стоит задача изменить dvd & dvs так, что переполнение никогда не будет ;пусть dvd=$ffff'ffff'ffff'ffff и dvs как-то уместилось в 32bit ;эх, и тут переполнение: $ffff'ffff'ffff'ffff / $8000'0000 = ; = $ffff'ffff'ffff'ffff / 2^31 = ; = $ffff'ffff'ffff'ffff shr 31 = $0000'0001'ffff'ffff <- еще 1 байт ;dvs уменшен достаточно, трогать более его не следует ;я не множко приврал про существование непропорционального dvd=$ffff'ffff'ffff'ffff и кое-как полученного dvs=$8000'0000 ;никаких "еще 1 байт" ;вот где маштабирование должно быть применено правильно: ;изначально dvd=$ffff'ffff'ffff'ffff ;изначально dvs=$0000'1000'1000'0001, неважно - приводя к DWord, младшая часть может потеряться совсем ;bsr сдвигов_вправо,dvs даст 12 т.е. 12+1 сдвигов вправо для получения dvs как 32bit ;dvs shr 13(31 max - лимит цп) = $0000'0000'8000'8000 ;dvd shr 13(31 max - лимит цп) = $0007'ffff'ffff'ffff ; ;"приводя к DWord, младшая часть может потеряться совсем" ;изначально dvd=$8000'0000'0000'0000 -> shr 31 -> $0000'0001'0000'0000|потеря $0000'0000 \ ;изначально dvs=$4000'0000'0000'0001 -> shr 31 -> $8000'0000|потеря $0000'0001 /2 на выходе ;помни: младшие части(DWords) dvd & dvs сравнивай перед масштабировкой ;в нашем случае 0 < 1,поэтому результат = 2-flags'cf = sbb 2,0 = 1 ; ;как точны вычисления? ;max приведенный dvd = $7fff'ffff'ffff'ffff ~\ 2^63 ~\ ;min приведенный dvs = $0000'0000'8000'0000 ~/ 2^31 ~/ 2^(63-31) ~ 2^32 ;ВРОДЕ ТОЧНО, НО... ВЫЧИСЛЕНИЯМ ДОЛЖНО ПРЕДШЕСТВОВАТЬ СРАВНЕНИЕ МЛАДШИХ ЧАСТЕЙ ЧИСЕЛ ;edx:eax <- edx:eax div ecx:ebx ;ecx:ebx <- ? ;;include once 'intro.inc' ;;intro _64div64 test ecx,ecx jnz .dvs.hi_nz test ebx,ebx jnz .dvs.lo_nz sub edx,edx ;stupid(how much water can be spilled through an absent chink?) rule overcome sub eax,eax ;i.e. divide by zero ret 0 ;same CTRL+SHIfT with sqrt(-etc) .dvs.lo_nz: mov ecx,eax ;keep dvd.lo mov eax,edx ;to divide dvd.hi 1st sub edx,edx ; div ebx ; xchg ecx,eax ;divide dvd.lo div ebx ; mov edx,ecx ;restore quo.hi ret 0 ;hi revo! .dvs.hi_nz: cmp eax,ebx ;is dvd.lo < dvs.lo? pushf ;remember the answer push esi mov esi,ecx bsr ecx,ecx ;so many shifts right +1 required to make dvs 32 bit size shrd eax,edx,cl ;compensate dvd shr edx,cl ; shrd eax,edx,1 ; shr edx,1 ; shrd ebx,esi,cl ;as dvs is 32 bit size soon shr esi,cl ; shrd ebx,esi,1 ; pop esi div ebx sub edx,edx ;quo.hi popf ;so, what the answer was? sbb eax,edx ;apply answer adc eax,edx ;0 if 0 was initially ret 0 ;hi amd! ;;end if
Код (Text): title lldiv - signed long divide routine ;*** ;lldiv.asm - signed long divide routine ; ; Copyright (c) Microsoft Corporation. All rights reserved. ; ;Purpose: ; defines the signed long divide routine ; __alldiv ; ;******************************************************************************* .xlist include cruntime.inc include mm.inc .list ;*** ;lldiv - signed long divide ; ;Purpose: ; Does a signed long divide of the arguments. Arguments are ; not changed. ; ;Entry: ; Arguments are passed on the stack: ; 1st pushed: divisor (QWORD) ; 2nd pushed: dividend (QWORD) ; ;Exit: ; EDX:EAX contains the quotient (dividend/divisor) ; NOTE: this routine removes the parameters from the stack. ; ;Uses: ; ECX ; ;Exceptions: ; ;******************************************************************************* CODESEG _alldiv PROC NEAR push edi push esi push ebx ; Set up the local stack and save the index registers. When this is done ; the stack frame will look as follows (assuming that the expression a/b will ; generate a call to lldiv(a, b)): ; ; ----------------- ; | | ; |---------------| ; | | ; |--divisor (b)--| ; | | ; |---------------| ; | | ; |--dividend (a)-| ; | | ; |---------------| ; | return addr** | ; |---------------| ; | EDI | ; |---------------| ; | ESI | ; |---------------| ; ESP---->| EBX | ; ----------------- ; DVND equ [esp + 16] ; stack address of dividend (a) DVSR equ [esp + 24] ; stack address of divisor (b) ; Determine sign of the result (edi = 0 if result is positive, non-zero ; otherwise) and make operands positive. xor edi,edi ; result sign assumed positive mov eax,HIWORD(DVND) ; hi word of a or eax,eax ; test to see if signed jge short L1 ; skip rest if a is already positive inc edi ; complement result sign flag mov edx,LOWORD(DVND) ; lo word of a neg eax ; make a positive neg edx sbb eax,0 mov HIWORD(DVND),eax ; save positive value mov LOWORD(DVND),edx L1: mov eax,HIWORD(DVSR) ; hi word of b or eax,eax ; test to see if signed jge short L2 ; skip rest if b is already positive inc edi ; complement the result sign flag mov edx,LOWORD(DVSR) ; lo word of a neg eax ; make b positive neg edx sbb eax,0 mov HIWORD(DVSR),eax ; save positive value mov LOWORD(DVSR),edx L2: ; ; Now do the divide. First look to see if the divisor is less than 4194304K. ; If so, then we can use a simple algorithm with word divides, otherwise ; things get a little more complex. ; ; NOTE - eax currently contains the high order word of DVSR ; or eax,eax ; check to see if divisor < 4194304K jnz short L3 ; nope, gotta do this the hard way mov ecx,LOWORD(DVSR) ; load divisor mov eax,HIWORD(DVND) ; load high word of dividend xor edx,edx div ecx ; eax <- high order bits of quotient mov ebx,eax ; save high bits of quotient mov eax,LOWORD(DVND) ; edx:eax <- remainder:lo word of dividend div ecx ; eax <- low order bits of quotient mov edx,ebx ; edx:eax <- quotient jmp short L4 ; set sign, restore stack and return ; ; Here we do it the hard way. Remember, eax contains the high word of DVSR ; L3: mov ebx,eax ; ebx:ecx <- divisor mov ecx,LOWORD(DVSR) mov edx,HIWORD(DVND) ; edx:eax <- dividend mov eax,LOWORD(DVND) L5: shr ebx,1 ; shift divisor right one bit rcr ecx,1 shr edx,1 ; shift dividend right one bit rcr eax,1 or ebx,ebx jnz short L5 ; loop until divisor < 4194304K div ecx ; now divide, ignore remainder mov esi,eax ; save quotient ; ; We may be off by one, so to check, we will multiply the quotient ; by the divisor and check the result against the orignal dividend ; Note that we must also check for overflow, which can occur if the ; dividend is close to 2**64 and the quotient is off by 1. ; mul dword ptr HIWORD(DVSR) ; QUOT * HIWORD(DVSR) mov ecx,eax mov eax,LOWORD(DVSR) mul esi ; QUOT * LOWORD(DVSR) add edx,ecx ; EDX:EAX = QUOT * DVSR jc short L6 ; carry means Quotient is off by 1 ; ; do long compare here between original dividend and the result of the ; multiply in edx:eax. If original is larger or equal, we are ok, otherwise ; subtract one (1) from the quotient. ; cmp edx,HIWORD(DVND) ; compare hi words of result and original ja short L6 ; if result > original, do subtract jb short L7 ; if result < original, we are ok cmp eax,LOWORD(DVND) ; hi words are equal, compare lo words jbe short L7 ; if less or equal we are ok, else subtract L6: dec esi ; subtract 1 from quotient L7: xor edx,edx ; edx:eax <- quotient mov eax,esi ; ; Just the cleanup left to do. edx:eax contains the quotient. Set the sign ; according to the save value, cleanup the stack, and return. ; L4: dec edi ; check to see if result is negative jnz short L8 ; if EDI == 0, result should be negative neg edx ; otherwise, negate the result neg eax sbb edx,0 ; ; Restore the saved registers and return. ; L8: pop ebx pop esi pop edi ret 16 _alldiv ENDP end
edemko! Если еще актуален Ваш вопрос, поясните по-русски (без приколов и жаргона) в чем проблема? Целочисленное деление в 32-х разрядной или 64-х разрядной машине? Если да, то какие входные условия: диапазон изменения числителя и знаменателя? если есть постоянные (особенно делитель), то какие значения они имеют? Лучше всего - постановка задачи в терминах метематики.
1212, прошу прощения, отписался от темы и... Там есть ошибка, вот новый вариант. Вынужденное обновление calc. Код (Text): ;format pe gui ;entry $ ; mov edx,$ffff'ffff ; mov ecx,$ffff'ffff ; mov ebx,$0000'0001 ; mov eax,$ffff'ffff ; hlt ; call div64_embarcadero ; ret ;2012/02/22, edemko@rambler.ru. ;rus: Деление 64-битных чисел без использования инструкции div ; на 32-битном процессоре Интел 1985 года и совместимых. ; По материалам embarcadero. ; ; делимое /делитель = ; (часть1+часть2+..) /делитель = ; (часть1+часть2+..)*1/делитель = ; часть1*1/делитель + часть2*1/делитель +.. = ; часть1 /делитель + часть2 /делитель +.. ; ; Выдвинем старший бит делимого, чем не часть, разделим его на делитель - получим конкретные частное, и остаток для последующего деления. ; Примером делимое 11110000b=240 и делитель 101b=5. ; |11110000 ; 1|1110000_ часть начинается с бита 8, частное 0|0000000, остаток 0000000|0 ; 11|110000__ часть начинается с бита 7, частное 00|000000, остаток 000000|11 ; 111|10000___ часть начинается с бита 6, частное 001|00000, остаток 00000|010 ; -101 ; =010 ; 101|0000____ часть начинается с бита 5, частное 001|1|0000,остаток 00000|000 ; -101 ; =000 ; ... = 00110000b=48. ;enu: Int64 division avoiding div on i386 and compatible. ; Based on embarcadero works. ; ; dividend /divisor = ; (part1+part2+..) /divisor = ; (part1+part2+..)*1/divisor = ; part1*1/divisor + part2*1/divisor +.. = ; part1 /divisor + part2 /divisor +.. ; ; Pop most significant dividend bit(minimal part), divide it by divisor - get private quotient, and remainder for further division. ; If dividend=11110000b=240 and divisor=101b=5 then ; |11110000 ; 1|1110000_ part starts at bit 8, quotient 0|0000000, ramainder 0000000|0 ; 11|110000__ part starts at bit 7, quotient 00|000000, ramainder 000000|11 ; 111|10000___ part starts at bit 6, quotient 001|00000, ramainder 00000|010 ; -101 ; =010 ; 101|0000____ part starts at bit 5, quotient 001|1|0000,ramainder 00000|000 ; -101 ; =000 ; ... = 00110000b=48. ;edx:ecx <- edx:ecx div ebx:eax ;ebx:eax <- edx:ecx mod ebx:eax ;flags <- ? div64_embarcadero: test ebx,ebx ;dvs=0 ? jnz .dvs_nz test eax,eax jnz .dvs_nz xchg ebx,edx ;quo=0, rem=dvd xchg eax,ecx ret .dvs_nz: push ebp esi edi mov ebp,64 ;index sub esi,esi ;part sub edi,edi .loop:shl ecx,1 rcl edx,1 rcl edi,1 rcl esi,1 cmp esi,ebx ;part ? jb .no_part ja .part cmp edi,eax jb .no_part .part:sub edi,eax sbb esi,ebx inc ecx ;quo .no_part: dec ebp jnz .loop mov ebx,esi ;rem mov eax,edi pop edi esi ebp ret
