Assembler 64b division

Question

I need some easy way to divide 64b unsigned integers in assembler for x86. My number is saved in two 32b registers EDX:EAX and I need to put result back to EDX:EAX. Factor is in 32b integer. Some code, please?

Just for clarification, do you mean with or without using x64 instructions? That is, is this just a matter of getting the data into 64 bit registers (eg RAX), doing 64 bit division, then splitting them back up into 32 bit registers, or are you trying to emulate 64 bit division on a 32 bit processor? — WeirdlyCheezy, Oct 18 '12 at 23:16
Without 64b reg - I'm trying to emulate 64b division on 32b. — Nick, Oct 18 '12 at 23:21
If that's the case, it sounds like you're basically implementing binary division from almost-scratch. That seems a little broad for a SO question, imo. What have you tried so far? Is there a more-specific part you're stuck on? — WeirdlyCheezy, Oct 18 '12 at 23:29
I need some idea, how to do that. I don't need any check's (owerflows, div by 0, sign control) or something. Just divide and save. I think, this is about 15 lines of code :) — Nick, Oct 18 '12 at 23:41
I'll see what I can scratch together tomorrow if no one else has posted a solution by then. — WeirdlyCheezy, Oct 18 '12 at 23:56
If you are really doing 64/64=64,64 division, you can extend the code from [this answer](http://stackoverflow.com/a/7709021/968261). It does 16/8=8,8 division. By using pairs of 32-bit integers to represent 64-bit quantities instead of 8-bit ones and looping 64 times instead of 8, you can turn that code into 128/64=64,64 division, just like 64-bit `div` in 64-bit mode. — Alexey Frunze, Oct 19 '12 at 01:37
@AlexeyFrunze: If the divisor is larger than the CPU supports, you can't break it into multiple divisions. This means that (for 32-bit 80x86) you can do "123456-bit divided by 32-bit" with multiple divisions, but can't do "64 bit divided by 64-bit" with multiple divisions. — Brendan, Oct 19 '12 at 02:41
@Brendan I didn't imply you could break a larger division into smaller ones (btw, you actually can in some cases, if the dividend and divisor values permit). I merely suggested reusing the same basic long division algorithm (as implemented in the linked answer) for larger integers. — Alexey Frunze, Oct 19 '12 at 02:48
@Alexey Frunze From my reading of the post, it sounds like the op is actually doing 64 bit numerator, 32 bit denominator, so that approach is directly applicable. — WeirdlyCheezy, Oct 19 '12 at 16:48

Alexey Frunze · Accepted Answer · 2012-10-20T12:31:21.650

If I interpret your question correctly (particularly the part Factor is in 32b integer), you want to divide a 64-bit dividend by a 32-bit divisor and get a 64-bit quotient.

If that interpretation is correct, then it's actually easy to do in 32-bit code.

The idea is that you divide both "halves" of the dividend by the divisor and reuse the remainder from the first division for the second division.

C code illustrating how to do it:

#include <stdio.h>
#include <limits.h>

#define C_ASSERT(expr) extern char CAssertExtern[(expr)?1:-1]

#if UINT_MAX >= 0xFFFFFFFF
typedef unsigned int uint32;
#else
typedef unsigned long uint32;
#endif
typedef unsigned long long uint64;

typedef unsigned long ulong;

// Make sure uint32=32 bits and uint64=64 bits
C_ASSERT(sizeof(uint32) * CHAR_BIT == 32);
C_ASSERT(sizeof(uint64) * CHAR_BIT == 64);

int div64by32eq64(uint64* dividend, uint32 divisor)
{
  uint32 dividendHi = (uint32)(*dividend >> 32);
  uint32 dividendLo = (uint32)*dividend;
  uint32 quotientHi;
  uint32 quotientLo;

  if (divisor == 0)
    return 0;

  // This can be done as one 32-bit DIV, e.g. "div ecx"
  quotientHi = dividendHi / divisor;
  dividendHi = dividendHi % divisor;

  // This can be done as another 32-bit DIV, e.g. "div ecx"
  quotientLo = (uint32)((((uint64)dividendHi << 32) + dividendLo) / divisor);

  *dividend = ((uint64)quotientHi << 32) + quotientLo;

  return 1;
}

int main(void)
{
  static const struct
  {
    uint64 dividend;
    uint32 divisor;
  } testData[] =
  {
    { 1 , 0 },
    { 0xFFFFFFFFFFFFFFFFULL, 1 },
    { 0xFFFFFFFFFFFFFFFFULL, 2 },
    { 0xFFFFFFFF00000000ULL, 0xFFFFFFFFUL },
    { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFUL },
  };
  int i;

  for (i = 0; i < sizeof(testData)/sizeof(testData[0]); i++)
  {
    uint64 dividend = testData[i].dividend;
    uint32 divisor = testData[i].divisor;

    printf("0x%016llX / 0x%08lX = ", dividend, (ulong)divisor);

    if (div64by32eq64(&dividend, divisor))
      printf("0x%016llX\n", dividend);
    else
      printf("division by 0 error\n");
  }

  return 0;
}

Output (ideone):

0x0000000000000001 / 0x00000000 = division by 0 error
0xFFFFFFFFFFFFFFFF / 0x00000001 = 0xFFFFFFFFFFFFFFFF
0xFFFFFFFFFFFFFFFF / 0x00000002 = 0x7FFFFFFFFFFFFFFF
0xFFFFFFFF00000000 / 0xFFFFFFFF = 0x0000000100000000
0xFFFFFFFFFFFFFFFF / 0xFFFFFFFF = 0x0000000100000001

And now the equivalent division code in assembly (NASM syntax) without checking for division by 0:

; 64-bit dividend
mov edx, 0xFFFFFFFF
mov eax, 0xFFFFFFFF

; 32-bit divisor
mov ecx, 0xFFFFFFFF

push eax
mov eax, edx
xor edx, edx
div ecx ; get high 32 bits of quotient
xchg eax, [esp] ; store them on stack, get low 32 bits of dividend
div ecx ; get low 32 bits of quotient
pop edx ; 64-bit quotient in edx:eax now
; edx:eax should now be equal 0x0000000100000001

[SOLVED] .. Wow! Working! Thank you, this is what I need :) ... Thank's all of you! — Nick, Oct 20 '12 at 20:15
Ugh... please don't use `xchg` with a memory operand unless you really want a bus lock. — fuz, Oct 05 '17 at 08:17
But the second division is still a full 64-bit division? If the division is actually 32-bit this will return the wrong result when `quotientLo * divisor` would overflow. For example: `0x0000000E10000000ULL / 0x0000000FUL` should be `0xf0000000`. — roeland, Aug 15 '21 at 23:59
@roeland C code's `((((uint64)dividendHi << 32) + dividendLo) / divisor)` is a full 64-bit division. Asm code's divisions are somewhat in between 64-bit and 32-bit because the dividend is 64-bit but the divisor, quotient and remainder are 32-bit. There cannot be overflow in the second division in the asm code. Think about it... — Alexey Frunze, Aug 16 '21 at 00:54
@roeland You get division overflow in the div instruction if the quotient doesn't fit into 32 bits, that is, when it would be 0x100000000 or greater. For that to happen, the dividend's most significant 32 bits would need to be greater than or equal to the divisor. But those 32 bits are guaranteed to be less than the divisor because they are the remainder from the first division by the same divisor. Hence, the second division always produces a quotient that fits into 32 bits. No overflow. — Alexey Frunze, Aug 16 '21 at 00:57
@AlexeyFrunze OK so `div` has a 64-bit input for the dividend? — roeland, Aug 16 '21 at 01:02
@roeland It has been documented in the i80386 documentation since 1986. — Alexey Frunze, Aug 16 '21 at 01:20

score 0 · Answer 2 · answered Oct 18 '12 at 23:25

0

What about using the div instruction?

answered Oct 18 '12 at 23:25

Jens Björnhager

5,632
3
27
47

Of course, but if you have one long number saved in two registers, you can't just use one or two "div". You need some way, how to divide one part of number (EDX), second part of number (EAX), combine results and save final result back into EDX:EAX. I'm looking for this way, how to do that. – Nick Oct 18 '12 at 23:35

Brendan · Answer 3 · 2012-10-19T02:36:18.267

Quick terminology recap: numerator/divisor = result + remainder/divisor

First check if the divisor is zero (abort if it is).

     test eax,eax
     jne .ok
     test edx,edx
     je .divisionByZero
.ok:

Shift the divisor left until the MSB is set while keeping track of how many shifts you did:

    xor ebp,ebp            ;ebp = bits shifted so far
    test edx,(1 << 31)
    jne .l2
.l1:
    shld edx,eax,1
    shl eax,1
    inc ebp
    test edx,(1 << 31)
    jne .l1
.l2:

Set the current result to zero:

    xor esi,esi
    xor edi,edi

Now shift the divisor back to its original position; while subtracting current divisor from remaining numerator and setting a bit in the result whenever current divisor is less than current numerator:

.nextBit:
    shld edi,esi,1
    shl esi,1

    cmp ecx,edx
    jb .doneBit
    ja .subtract
    cmp ebx,eax
    jb .doneBit

.subtract:
    sub ecx,edx
    sbb ebx,eax
    or esi,1

.doneBit:
    sub ebp,1
    jnc .nextBit

At this point EDX:EAX is the same value it was, EDI:ESI is the result and ECX:EBX is the remainder.

WARNING: All of the above is completely untested. It's just an example/description.

NOTE: If the numbers are signed you need to remove the sign bit from the numerator and divisor first; then set the sign bit in the result and remainder later (sign = numerator_sign XOR divisor_sign).

Assembler 64b division

3 Answers3

Linked