How does this 8080 code perform division with remainder?

Question

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)

Answer 1

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 
  ADD B 
  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;
}

Answer 2

Don't understand purpose of SUB B/ADD B

It's an underflow handling

  SUB B       ; Subtract divider
  JNC loop_1  ; No underflow -> Continue
  ADD B       ; Correct underflow
  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

Answer 3

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 [0]  * 2^3
127 - 10 * 2^4 =  -33 [0]  * 2^4
127 - 10 * 2^3 =   47 [1]  * 2^5
 47 - 10 * 2^2 =    7 [1]  * 2^6
  7 - 10 * 2^1 =   -3 [0]  * 2^7
  7 - 10 * 2^0 =   -3 [0]  * 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)