19

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)

enter image description here Tornado Baseball - Midway (1976)

4
  • 5
    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
  • 1
    Seems that code I've posted implements this algorithm en.wikipedia.org/wiki/…
    – DraganS
    Oct 3, 2021 at 20:25
  • 1
    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
  • 2
    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

3 Answers 3

42

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;
}
3
  • 3
    I'd ask to give the checkmark to this answer, please, as it explains the whole function, not just the underflow handling.
    – Raffzahn
    Oct 4, 2021 at 9:46
  • Totally age. Thanks for you understanding and for your clarification what was the code about.
    – DraganS
    Oct 4, 2021 at 9:51
  • 2
    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
14

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
1
  • 2
    It's also known as restoring division, in contrast to non-restoring division, which is more often seen in hardware implementations.
    – Dave Tweed
    Oct 6, 2021 at 13:59
4

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)

1
  • 1
    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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.