Wednesday, January 2, 2013

32-bit division on an old school 8086 processor

During a 8086 assembler course, a student asked me how he could divide a 32-bit unsigned integer by a 16-bit unsigned integer. I knew that the answer was not to simply use the DIV instruction once, because of potential range limitations. Let me explain.

On the 8086 CPU the DIV instruction takes as input a 32-bit numerator in DX::AX and divides it by a denominator given as the operand of the instruction (a register or a memory address). After the division, AX holds the quotient, while DX contains the remainder of the division. More formal:


DIV   Unsigned divide
Syntax:  DIV    op8 (8-bit register or memory)
        DIV    op16 (16-bit register or memory)
Action:  If operand is op8, unsigned AL = AX / op8  and  AH = AX % op8
         If operand is op16, unsigned AX = DX::AX / op16  and  DX = DX::AX % op16
Flags:   OF=?, SF=?, ZF=?, AF=?, PF=?, CF=?

As shown, the DIV instruction performs a division and modulus operation at once. And, it is clear that one can provide certain values for the numerator when executing the DIV instruction that will result in an error. For example, with DX::AX set to 4000h::0000h, a division by 2 should give 2000h::0000h as the result, but the CPU cannot represent this value in the AX register. The quotient is too big and requires more than 16-bits to be able to represent it. In the worst case when a 32-bit number is divided by 1, then the quotient is that same 32-bit number. Therefore, when the quotient is too large to fit into AX, the CPU will generate a division overflow exception, just as it does with a division by zero.

It is obvious that a solution must exist to tackle this problem. Why else on earth would those Intel engineers in the seventies have designed a DIV instruction that takes 32-bit numerators at the input for 16-bit divisions?

At first, I searched the Internet for a solution. However, it did not take long to realize that either nobody, still working with 8086 assembler, understands or realizes the issue at hand, or that no-one was ever interested in providing a simple solution (I suspect the latter). So, I was forced to think it over myself and I decided to make this blog post about the solution for other people to use.

It appears that those Intel engineers did think about this problem and they provided everything necessary to divide big numbers by a 16-bit divisor. The DIV instruction design allows it to be chained easily with an unspecified amount of subsequent DIV instructions. This basically enables a programmer to use an arbitrary n * 16-bit number as numerator, by splitting the dividend in 32-bit blocks.

So here is a piece of plain old 8086 code (MASM-style). The actual div32 procedure performs a 32-bit unsigned integer division by chaining two DIV instructions. However, larger n * 16-bit numbers could be supported easily. Using LODSW and STOSW, the code becomes very clean and straightforward...

  ...<setup CX, SI, DI, DS, ES and FLAGS>...
  XOR   DX, DX ; set DX := 0
  LODSW        ; load the higher 16-bits into AX
  DIV   CX     ; divide DX::AX by CX
               ; leaves DX with remainder and AX with quotient
  STOSW        ; write out AX to result

  LODSW        ; load the lower 16-bits into AX
  DIV   CX     ; divide DX::AX by CX
               ; leaves DX with remainder and AX with quotient
  STOSW        ; write out AX to result
  ...<cleanup code>...


This LODSW, DIV, STOSW sequence can be repeated as many times as necessary in order to divide n * 16-bit numbers by a 16-bit divident.

I hope this small post will help some people to save some research time. Have fun coding on old-school 8086 :)

Note: The formatting on Google Docs for assembler code is not so great. Indentation is gone, and so is readability. Download the code and view it in a decent text editor to see indentation.

6 comments:

  1. Mabye I didn't understand, the problem doesn't seem solved for me.
    If I have a big 32-bit number, let's say all ones, if I divide it by 2 the result is 31 ones, the higher part is 15 ones and would be in DX which is overwritten by the reminder.

    ReplyDelete
    Replies
    1. The problem is solved. Let me explain your example (at least what should happen) :)

      Your input would be (in hex, big endian) the number FFFF FFFE, and divide this by 2. So, the provided div32 takes the first 16 bit as low part, and sets the DX-register to zero. Thus, it divides 0000 FFFF by 2, which gives DX == 0001 and AX == 7FFF. AX is written back to memory (to store output). Subsequently, AX is loaded with the next 16 bits of the input number. So, AX is loaded with FFFE. DX still contains a 0001. The number we will be dividing by 2 as such is 0001 FFFE. After the second DIV, we get DX == 0000 and AX == FFFF. The contents of AX are also written back to memory as the second 16 bits of the result.

      To summarize, we get as result: 7FFF FFFF and remainder 0000, which is exactly the result of dividing FFFF FFFE by 2.

      So, I don't see why the problem isn't solved.

      Delete
    2. Yes,you are right, I made a big mistake, sorry and thank you for the help :)

      Delete
  2. This comment has been removed by a blog administrator.

    ReplyDelete
  3. excellent work sir, keep it up. I was also trying to solve this problem

    ReplyDelete
  4. Thank you so much for this. I needed a way to convert the 32 bit starting sector number of a partition into a given C/H/S disk geometry. This is perfect.

    ReplyDelete