Qword division

[JK]

How would i divide (unsigned) a qword with 32 bit assembler code without using the FPU?

I basically know how to divide a qword with the DIV instruction and how to get the quotient and the remainder of this division. But when the quotient is larger than 32 bit (IOW when it doesn´t fit into EAX) i get an integer overflow exception. So how to do it without GPF (i need both, the quotient and the remainder of such a dvision)?

Thanks

JK

[jj2007]

Code Select Expand


include \masm32\include\masm32rt.inc
.code
MyQ dq 123456789012345678
start:
  mov eax, dword ptr MyQ
  mov edx, dword ptr MyQ[4]
  mov ecx, 123456789
  div ecx
  printf("eax=%i, edx=%i", eax, edx)
  exit
end start

Code Select Expand

The result:
eax             1000000000
ecx             123456789
edx             12345678

Now if you use mov ecx, 123, you have a problem. Solution: use the fpu

[JK]

Thanks jj,

this is what i tried.

But what happens, if ECX = e.g 10?. As long as EAX after DIV is smaller than 2^32, everything is fine. The trouble starts, if the result (quotient) doesn´t fit into EAX anymore ...

How to properly handle this?


Added: obviously i must somehow split the division into parts in order to avoid a possible overflow. But i´m not able to figure out how this could be done.

[Biterider]

Hi
Look into this macro. Maybe you have to adapt the code for your specific case.

Code Select Expand

; ——————————————————————————————————————————————————————————————————————————————————————————————————
; Macro:      qqdiv
; Purpose:    Divide 2 unsigned QuadWords. Uses edi, esi.
;             Output:  edx::eax = quotient of division of dividend by divisor
;                      ecx::ebx = remainder of division of dividend by divisor
; Arguments:  edx::eax = dividend
;             ecx::ebx = divisor

qqdiv macro
  local @@Exit

  test ecx, ecx                                         ;;check if ecx is zero
  jnz @F
  qddiv                                                 ;;Perform qddiv
  xor ecx, ecx                                          ;;ecx = remainder-hi = zero
  jmp @@Exit
@@:
  push edx                                              ;;save
  push eax                                              ;; dividend
  mov esi, ebx                                          ;;divisor now in
  mov edi, ecx                                          ;; edi:ebx and ecx::esi
  shr edx, 1                                            ;;shift both
  rcr eax, 1                                            ;; divisor and
  ror edi, 1                                            ;;  and dividend
  rcr ebx, 1                                            ;;   right by 1 bit
  bsr ecx, ecx                                          ;;ecx = number of remaining shifts
  shrd ebx, edi, cl                                     ;;scale down divisor and
  shrd eax, edx, cl                                     ;;  dividend such that divisor
  shr edx, cl                                           ;;   less than 2^32 (i.e. fits in ebx)
  rol edi, 1                                            ;;restore original divisor (edi::esi)
  div ebx                                               ;;compute quotient
  pop ebx                                               ;;get dividend lo-word
  mov ecx, eax                                          ;;save quotient
  imul edi, eax                                         ;;quotient * divisor hi-word (low only)
  mul esi                                               ;;quotient * divisor lo-word
  add edx, edi                                          ;;edx:eax = quotient * divisor
  sub ebx, eax                                          ;;dividend-lo - (quot.*divisor)-lo
  mov eax, ecx                                          ;;get quotient
  pop ecx                                               ;;restore dividend hi-word
  sbb ecx, edx                                          ;;subtract divisor * quot. from dividend
  sbb edx, edx                                          ;;0 if remainder > 0, else FFFFFFFFh
  and esi, edx                                          ;;nothing to add
  and edi, edx                                          ;; back if remainder positive
  add ebx, esi                                          ;;correct remaider
  adc ecx, edi                                          ;; and quotient if
  add eax, edx                                          ;;  necessary
  xor edx, edx                                          ;;clear hi-word of quot (eax<=FFFFFFFFh)
@@Exit:

endm


Biterider

[JK]

Thanks Biterider,

i forgot to mention: while the dividend id a qword, the divisor is guaranteed not to be larger than a dword, which might simplify it a bit. I´m going to study your code - thanks again

JK

[jj2007]

; Purpose:    Divide 2 unsigned QuadWords. Uses edi, esi.
;             Output:  edx::eax = quotient of division

Hi Biterider,

That's a nice macro, but you end up with edx::eax, i.e.: a QWORD in disguise (obviously, if the result doesn't fit in 32 bits).

At that point, wouldn't it be simpler to use the fpu?

Code Select Expand

include \masm32\include\masm32rt.inc
.data?
Dest dq ?
.code
MyQ dq 123456789012345678
start:
  cls
  fild MyQ
  push 15873   ; divide by this number
  fidiv dword ptr [esp]
  pop eax
  fistp Dest
  printf("%llu\n", Dest)
  inkey
  exit
end start

[JK]

@Biterider,

using your "qddiv" macro (divisor in dword range), i have this code now,

Code Select Expand

int 3
  mov eax, 0                                          ;load -1152921504606846976 <=> F000 0000 0000 0000h
  mov edx, 0f0000000h

  mov ebx, 10                                         ;divisor


;qddiv macro
  cmp edx, ebx                                          ;;only one division needed ? (ecx = 0)
  jb @F                                                 ;;yes, one division sufficient
  mov ecx, eax                                          ;;save dividend-lo in ecx
  mov eax, edx                                          ;;get dividend-hi
  xor edx, edx                                          ;;zero extend it into edx::eax
  div ebx                                               ;;quotient-hi in eax
  xchg eax, ecx                                         ;;ecx = quotient-hi, eax =dividend-lo
@@:                                                     
  div ebx                                               ;;eax = quotient-lo
  mov ebx, edx                                          ;;ebx = remainder
  mov edx, ecx                                          ;;edx = quot.-hi(quotient in edx::eax)
;endm


; EAX = 00000000h
; EDX = 18000000h
; EBX = 00000000h


; -1152921504606846976 / 10 = -115292150460684697  remainder = 6
; -115292150460684697 <=> FE66666666666667


but the result is not correct. what is wrong here ?

JK

[Biterider]

Hi
0F000'0000'0000'0000h = 17'293'822'569'102'704'640 (dec)
17'293'822'569'102'704'640 (dec) / 10 (dec) = 1'729'382'256'910'270'464 (dec)
1'729'382'256'910'270'464 (dec) = 1800'0000'0000'0000h

=> edx = 1800'0000h; eax = 0000'0000h

You asked for an unsigned division and you are feeding it with signed integers. 

Check this link: https://calc.penjee.com/

Biterider

[JK]

 

yes, my bad - you are right! I once again fell for this signed/unsigned thing, because of using the (limited) Windows Calculator in a hurry, instead of using my brain.

Thanks for the link (which would have been my next question) - and thanks for the code

JK

PS: is there something like Windows calculator without these qword limitations as a desktop version you could recommend?

[Biterider]

Hi JK
I'm sorry, but I don't know of any desktop 128-bit calculator application. Would be nice if someone wrote one. 
Be careful with the Penjee calculator. Sometimes the change of options is not recognized correctly and you have to double check the result.

Biterider