New non-restoring division routine, sub-optimal but justified to always work

diff --git a/div.py b/div.py
new file mode 100755 (executable)
index 0000000..63f01a6
--- /dev/null
+++ b/div.py
@@ -0,0 +1,8 @@
+#!/usr/bin/env python3
+
+print(
+  f'''{0x1234 // 0x56:04x} {0x1234 % 0x56:04x}
+{0x6543 // 0x21:04x} {0x6543 % 0x21:04x}
+{0xb975 // 0x31:04x} {0xb975 % 0x31:04x}
+{0xdb97 // 0x531:04x} {0xdb97 % 0x531:04x}'''
+)

diff --git a/sm.asm b/sm.asm
index 396fd58..1889d48 100644 (file)
--- a/sm.asm
+++ b/sm.asm
@@ -846,70 +846,157 @@ div_hl_de:
        ld      a,h
        ld      c,l
        ld      hl,0
-       ld      b,8
-       scf
-1$:    rla
-       adc     hl,hl
-       sbc     hl,de
-       jr      c,50$
-2$:    djnz    1$
-       rla
-       add     a,a
-       dec     a
-       push    af
- ld a,'a
- call print_char
+       call    div0
+       ld      b,a
        ld      a,c
+       ld      c,b
+       jr      c,2$
+       call    div0
+       jr      c,3$
+1$:    ld      d,c
+       ld      e,a
+       pop     bc
+       ret
+
+2$:    call    div1
+       jr      nc,1$
+3$:    add     hl,de
+       ld      d,c
+       ld      e,a
+       pop     bc
+       ret
+
+; non-restoring division routine
+
+; de = divisor, hl:a = dividend with hl = previous remainder, a = next byte
+; enter at div0 with positive remainder in hl, such that hl < de
+; enter at div1 with negative remainder in hl, such that hl >= -de
+
+; div0/1 return a = 8-bit quotient as an odd number interpreted as -ff..ff,
+; by summing positive/negative place values, e.g. -80 +40 +20 -10 +8 -4 -2 +1
+
+; if entered at div0, there is a -80 and so quotient is in range -ff..-1
+; if entered at div1, there is a +80 and so quotient is in range 1..ff
+; falls out of loop after div01 with positive remainder, div11 with negative,
+; depending on this we should re-enter at div0 or div1, signalled by cf return
+
+; the successive quotient bytes can be concatenated into a full quotient,
+; but negative bytes require the next higher quotient byte to be decremented,
+; we know in advance if this will happen because the implied sign of the
+; quotient byte depends only on whether we entered at div0 or div1, hence,
+; before the div11 return we'll decrement to compensate for next negative byte
+
+; the decrement can also be seen as compensating for the extra add hl,de that
+; may be needed to make negative remainder positive before return to caller,
+; thus leaving things in a consistent state regardless of which exit occurred,
+; to find out if we need the extra add hl,de we can look for even return byte
+
+; in the following code each sbc hl,de gets an inc a and each add hl,de gets
+; a dec a, guaranteeing the integrity of the division, the initial scf/rla is
+; needed to make the result 100 + -ff..ff or 1..1ff, so that the decrements
+; cannot borrow into the upcoming dividend bits also held in a, and there must
+; be another shift between the scf/rla and increment/decrement so that the scf
+; is implicitly in the 100s place, making the code awkward though it's correct 
+
+div0:
+ push af
+ ld a,'A
+ call print_char
+ pop af
+ call print_word
+ push af
+ ld a,':
+ call print_char
+ pop af
+ call print_byte
+ push af
+ ld a,'/
+ call print_char
+ pop af
+ ex de,hl
+ call print_word
+ ex de,hl
        ld      b,8
        scf
-3$:    rla
-       adc     hl,hl
-       sbc     hl,de
-       jr      c,70$
-4$:    djnz    3$
        rla
+div00: adc     hl,hl
+       sbc     hl,de
+       jr      nc,1$
        add     a,a
-       dec     a
-       pop     de
-       ld      e,a
- ld a,'b
+       inc     a
+       jr      div11
+1$:    add     a,a
+       inc     a
+div01: djnz    div00
+       or      a
+ push af
+ ld a,'B
  call print_char
-       pop     bc
+ pop af
+ push af
+ ld a,'0
+ adc a,0
+ call print_char
+ ld a,':
+ call print_char
+ pop af
+ call print_byte
+ push af
+ ld a,',
+ call print_char
+ pop af
+ call print_word
+ call print_crlf
        ret
 
-50$:   dec     a
-       ;jr     6$
-       dec     b
-       jr      z,60$
-5$:    rla
-       adc     hl,hl
-       add     hl,de
-       jr      c,2$
-6$:    djnz    5$
-60$:   rla
-       add     a,a
-       push    af
- ld a,'c
+div1:
+ push af
+ ld a,'C
  call print_char
-       ld      a,c
+ pop af
+ call print_word
+ push af
+ ld a,':
+ call print_char
+ pop af
+ call print_byte
+ push af
+ ld a,'/
+ call print_char
+ pop af
+ ex de,hl
+ call print_word
+ ex de,hl
        ld      b,8
        scf
-       jr      7$
-70$:   dec     a
-       ;jr     8$
-       dec     b
-       jr      z,80$
-7$:    rla
-       adc     hl,hl
+       rla
+div10: adc     hl,hl
        add     hl,de
-       jr      c,4$
-8$:    djnz    7$
-80$:   rla
+       jr      nc,1$
        add     a,a
-       add     hl,de
-       pop     de
-       ld      e,a
- ld a,'d
+       dec     a
+       jr      div01
+1$:    add     a,a
+       dec     a
+div11: djnz    div10
+       dec     a                       ; compensation
+       scf
+ push af
+ ld a,'D
  call print_char
-       pop     bc
+ pop af
+ push af
+ ld a,'0
+ adc a,0
+ call print_char
+ ld a,':
+ call print_char
+ pop af
+ call print_byte
+ push af
+ ld a,',
+ call print_char
+ pop af
+ call print_word
+ call print_crlf
        ret