flat assembler
Message board for the users of flat assembler.

Index > Compiler Internals > thoughts on int64 division when dvs.hi <> 0

Author
Thread Post new topic Reply to topic
idle



Joined: 06 Jan 2011
Posts: 359
Location: Ukraine
idle
Code:
;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
    
Post 09 May 2011, 09:25
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
idle, I'm a little bit confused, why this belongs to Compiler Internals and not Main?
Post 09 May 2011, 14:52
View user's profile Send private message Reply with quote
idle



Joined: 06 Jan 2011
Posts: 359
Location: Ukraine
idle
i was thinking about div_64 Tomasz used
you should not ask if topic movement required Smile
Post 10 May 2011, 06:26
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17279
Location: In your JS exploiting you and your system
revolution
There are lots of ways the mathematics engine in fasm can be "improved", but for what gain?
Post 07 Jun 2011, 11:12
View user's profile Send private message Visit poster's website Reply with quote
idle



Joined: 06 Jan 2011
Posts: 359
Location: Ukraine
idle
i found bugs, see code section on wasm.ru please
http://wasm.ru/forum/viewtopic.php?pid=467241#p467241

fasm bug?
Code:
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
    
Post 22 Feb 2012, 14:50
View user's profile Send private message Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7725
Location: Kraków, Poland
Tomasz Grysztar
Because fasm's expression calculator is still only 64-bit instead of at least 65, the "$ffff'ffff'ffff'ffff" equals to -1. And -1 divided by any large positive number is 0 (this is integer division here).
Post 22 Feb 2012, 14:57
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7725
Location: Kraków, Poland
Tomasz Grysztar
But, while we are at it, I managed to find a bug in some other calculation. Sign of the result was dropped sometimes and thus (-1FFFFFFFFh)/1FFFFFFFFh was giving result of 1 instead of -1. I'm fixing it right now.
Post 22 Feb 2012, 15:36
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.