;thoughts on int64 division when dvs.hi <> 0
;2011_05_09, edemko[at]rambler[.]ru
;___________________________________________
;
;
;
;
;32bit machine allowes 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 existance 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 ~ 2^31
;THAT'IS WHY LOW DWORDS MUST BE COMPARED BEFORE PERMUTATION/SCALING TO FIX FUTURE OUTPUT




;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
    

dq $ffff'ffff'ffff'ffff / $0000'0001'ffff'ffff
load var1 dword from 0
if var1=0
  display 'fasm 1.69.33 division error'
end if