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
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.
...<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.
Mabye I didn't understand, the problem doesn't seem solved for me.
ReplyDeleteIf 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.
The problem is solved. Let me explain your example (at least what should happen) :)
DeleteYour 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.
Yes,you are right, I made a big mistake, sorry and thank you for the help :)
DeleteThis comment has been removed by a blog administrator.
ReplyDeleteexcellent work sir, keep it up. I was also trying to solve this problem
ReplyDeleteThank 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