# How does this 8080 code perform division with remainder?

Empirically, I've found that this routine (i8080) divides value from E by B and returns the result in D and E (result and remainder of division).

``````divide_by_12_with_rest:
MVI C, 9 ; @1
MOV A, D ; @2
loop_1:
MOV D, A ; @3
MOV A, E
RAL
MOV E, A ; @4
DCR C ; @5
JZ exit
MOV A, D ; @6
RAL ; @7
SUB B ; @8
JNC loop_1
ADD B ; @9 - this will always set CF
JMP loop_1
exit:
MOV A, E
CMA
MOV E, A ; @a
RET
``````

Please, could you tell me whether my assumption is right? What is the math behind. Saw that DE is shifted left 8 times. Don't understand purpose of `SUB B`/`ADD B`. Thanks a lot. This code was written in 1976-7 and it was running in an arcade machine.

##### Updated

Debugging result

``````BC: 0c03
DE: 0030
HL: 0036
AF: 0046

divide_by_B_with_rest
@1    C: 9
@2    A = D: 00
Loop:
@3    D = A: 00    00       00       01      03      06  00      00      00
@4    E: 60        c1       83       07      0f      1f  3e      7d      fb
@5    C: 8          7        6        5       4       3   2       1       0
@6    A = D: 00    00       00       01      03      06  00      00
@7    A: 00        00       00       03      06      0c  00      00
@8    A: f4 (cf)   f4 (cf)  f5 (cf)  f7 (cf) fa (cf) 00  f4 (cf) f4 (cf)
@9    A: 00 (cf)   00 (cf)  01 (cf)  03 (cf) 06 (cf) --  00 (cf) 00 (cf)
Exit:
@a    E: 4, D: 0
``````
##### Update 2

environment used to debug the code (Rust/React/MongoDB) Tornado Baseball - Midway (1976)

• I'm not familiar with 8080 assembler, but subtracting and shifting in a loop is a standard approach on machines lacking hardware divide instructions: en.wikipedia.org/wiki/Binary_number#Division
– pndc
Oct 3, 2021 at 20:22
• Seems that code I've posted implements this algorithm en.wikipedia.org/wiki/… Oct 3, 2021 at 20:25
• Are you sure at point @7 (after the `RAL`) in the third iteration of the loop the accumulator is zero? Oct 4, 2021 at 4:41
• I don’t see how the screenshot adds much of substance to the question. The execution trace still looks wrong. Oct 4, 2021 at 8:54

As was said in the comments, this is the binary long division algorithm. The long division is performed by carefully juggling the bits between the registers and the carry flag.

The algorithm is probably best analysed by looking at each half of the loop as a whole.

``````  MOV D, A
MOV A, E
RAL
MOV E, A
DCR C
JZ exit
``````

The first half of the loop shifts the result bit held in the carry flag (computed in the other half of the loop) into the bottom-most bit of E and simultaneously shifts the top-most bit of E into the carry flag. At the start of the loop, the carry flag is in an indeterminate state, but because the loop iterates nine times, at the end that indeterminate bit is shifted out and does not contribute to the result.

``````  MOV A, D
RAL
SUB B
JNC loop_1
JMP loop_1
``````

The other half of the loop shifts the carry flag (what was the top-most bit of E) into the bottom-most bit of D and then performs subtraction D − B. If this computation underflows, the `SUB` instruction sets the carry flag; the subtraction is then undone, keeping the carry flag set. Otherwise, if the computation succeeds, the carry flag is cleared. Either way, the value of the carry flag is passed along to be shifted into E in the first half of the loop.

After the loop exits, the bits of E are complemented. This is because the value of the carry flag obtained in the second half of the loop is actually the opposite of the corresponding bit of the result. This could have been addressed by executing the `CMC` instruction before shifting the bit into the E register, but, as per the 8080 manual, that would cost 4 CPU cycles per iteration (36 cycles overall), instead of 4 cycles to complement all the bits in bulk and 10 cycles to move them between the E register and the accumulator.

Thus, as the loop iterates, the D register contains the running remainder of the long division; meanwhile, the remaining bits of the dividend in the E register are gradually replaced by bits of the quotient. The overall register state can be summarised with a diagram:

``````D at entry   E at entry     B
┌─────┴┐ ┌┴─────┐        │
│     low bits of E (inverted)
high bits of E      │       │
┌─┴┐   ┌────┴─┐   ┌─┤┌─── the carry bit (inverted)
00000001_00110000 ÷ 00001100 = 0001
0001_0011┆◁╌╌┌──────────────────── D
− 0000_1100┆   │
───────────┆   │      (not shown: the indeterminate initial
0000_0111▽◀──┘      value of the carry bit, also held in E)
000_01110◁╌╌┘
``````

Below is a roughly equivalent algorithm in C. It is not a literal translation, but it does reflect how bits move between the D and E registers.

``````#include <stdint.h>

uint16_t divide(uint16_t dividend, uint8_t divisor) {
uint8_t d = dividend >> 8, e = dividend;
uint8_t b = divisor;
uint8_t c = 8;

do {
d = (d << 1) | (e >> 7);
e = (e << 1);
if (d >= b) {
d -= b;
e |= 1;
}
} while (--c);

/* result in lower byte, remainder in upper byte */
return (d << 8) | e;
}
``````
• Totally age. Thanks for you understanding and for your clarification what was the code about. Oct 4, 2021 at 9:51
• The C code is great not just for someone who wants to understand the 8080 code, but as an expression of the algorithm for someone who wants to implement division on another processor. Oct 4, 2021 at 20:42

Don't understand purpose of SUB B/ADD B

It's an underflow handling

``````  SUB B       ; Subtract divider
JNC loop_1  ; No underflow -> Continue
JMP loop_1  ; -> Continue
``````
1. B is subtracted from A.
2. If there is no underflow (A was larger than B) then the loop continues with the new (positive) value of A.
3. A is restored to the original value (turned into positive again)
4. Loop is continued
• It's also known as restoring division, in contrast to non-restoring division, which is more often seen in hardware implementations. Oct 6, 2021 at 13:59

The missing piece for me was the math background. Will try to connect math and actual implementation. The fully explanation is given by user3840170's post (hope my post is complementary to user3840170's brilliant post). As example, let me calculate 127:10. The result is 12 and reminder is 7:

``````127 - 10 * 2^5 = -193   * 2^3
127 - 10 * 2^4 =  -33   * 2^4
127 - 10 * 2^3 =   47   * 2^5
47 - 10 * 2^2 =    7   * 2^6
7 - 10 * 2^1 =   -3   * 2^7
7 - 10 * 2^0 =   -3   * 2^8

2 * 127 * 2^3 - 10 * 2^8 = -33 * 2^4
2 * 127 * 2^4 - 10 * 2^8 =  47 * 2^5
2 *  47 * 2^5 - 10 * 2^8 =   7 * 2^6
2 *   7 * 2^6 - 10 * 2^8 =  -3 * 2^7
2 *   7 * 2^7 - 10 * 2^8 =  -3 * 2^7
``````

(a) is reason that DE is shifted left before subtraction.

(b) reason that DE is shifted in each iteration

(c) B should subtracted from D

(d) collects results of comparison

`````` 2 *   7 * 2^7 - 10 * 2^8 =  -3 * 2^7
(a)        (b)        (c)    (d)
``````

As a reference can be used https://web.stanford.edu/class/ee486/doc/chap5.pdf (pg 131)

• In case it helps to have another perspective on this, here is another commented version of the usual algorithm in 6800 assembler. On the 6800 one can rotate memory locations directly (the rotate still goes through the carry bit as well) which I think makes the algorithm a bit more clear.
– cjs
Oct 5, 2021 at 4:32