flat assembler
Message board for the users of flat assembler.

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

Joined: 06 Jan 2011
Posts: 440
Location: Ukraine
idle 09 May 2011, 09:25
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?
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?
adc     eax,edx    ;0 if 0 was initially
ret     0          ;hi amd!
end if
```
09 May 2011, 09:25
LocoDelAssembly

Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly 09 May 2011, 14:52
idle, I'm a little bit confused, why this belongs to Compiler Internals and not Main?
09 May 2011, 14:52
idle

Joined: 06 Jan 2011
Posts: 440
Location: Ukraine
idle 10 May 2011, 06:26
i was thinking about div_64 Tomasz used
you should not ask if topic movement required
10 May 2011, 06:26
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
revolution 07 Jun 2011, 11:12
There are lots of ways the mathematics engine in fasm can be "improved", but for what gain?
07 Jun 2011, 11:12
idle

Joined: 06 Jan 2011
Posts: 440
Location: Ukraine
idle 22 Feb 2012, 14:50
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
if var1=0
display 'fasm 1.69.33 division error'
end if
```
22 Feb 2012, 14:50
Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8351
Location: Kraków, Poland
Tomasz Grysztar 22 Feb 2012, 14:57
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).
22 Feb 2012, 14:57
Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8351
Location: Kraków, Poland
Tomasz Grysztar 22 Feb 2012, 15:36
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.
22 Feb 2012, 15:36
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum