From SMS Power!

Development: Div Mod

+Contents

Overview

Division algorithms differ in terms of the width of the operands and results. The algorithms on this page are classified by the bit-width of these. For the operations A / B = C (Division) and A % B = D (Modulo), the algorithms are classified as "A / B = C, D".

All of these algorithms contain a loop which can be unrolled to increase speed at the expense of code size.

Unsigned "8 / 8 = 8, 8" bit

; Integer divides D by E
; Result in D, remainder in A
; Clobbers F, B
    xor a
    ld b,8
-:  sla d
    rla
    cp e
    jr c,+
    sub e
    inc d
+:  djnz -

Unsigned "16 / 8 = 8, 8" bit

; Integer divides HL by E
; Result in A, remainder in H
; Clobbers F, B, L
    ld b,8
-:  adc hl,hl
    ld a,h
    jr c,+
    cp e
    jr c,++
+:  sub e
    ld h,a
    or a
++: djnz -
    ld a,l
    rla
    cpl

Unsigned "16 / 8 = 16, 8" bit

; Integer divides HL by C
; Result in HL, remainder in A
; Clobbers F, B
    xor a
    ld b,16
-:  add hl,hl
    rla
    cp c
    jr c,+
    sub c
    inc l
+:  djnz -

Unsigned "16 / 16 = 16, 16" bit

; Integer divides A:C by DE
; Result in A:C, remainder in HL
; Clobbers F, B
    ld hl,$0000
    ld b,16
-:  sll c
    rla
    adc hl,hl
    sbc hl,de
    jr nc,+
    add hl,de
    dec c
+:  djnz -

Unsigned "24 / 8 = 24, 8" bit

; Integer divides E:HL by D
; Result in E:HL, remainder in A
; Clobbers F, B
    xor a
    ld b,24
-:  add hl,hl
    rl e
    rla
    cp d
    jr c,+
    sub d
    inc l
+:  djnz -

Unsigned "24 / 16 = 24, 16" bit

; Integer divides A:BC by DE
; Result in A:BC, remainder in HL
; Clobbers F, IYH
    ld hl,$0000
    ld iyh,24
-:  sll c
    rl b
    rla
    adc hl,hl
    sbc hl,de
    jr nc,+
    add hl,de
    dec c
+:  dec iyh
    jp nz,-

Unsigned "32 / 8 = 32, 8" bit

; Integer divides DE:HL by C
; Result in DE:HL, remainder in A
; Clobbers F, B
    xor a
    ld b,32
-:  add hl,hl
    rl e
    rl d
    rla
    cp c
    jr c,+
    sub c
    inc l
+:  djnz -

Unsigned "32 / 16 = 16, 16" bit

; Integer divides HLBC by DE, returns result in BC and remainder in HL
; Clobbers A, F, IYH
; Found on Usenet
Divide16:
    ld iyh,16
-:  rl c
    rl b
    adc hl,hl
    sbc a,a
    or a
    sbc hl,de
    sbc a,0
    jr nc,+
    add hl,de
    scf
+:  dec iyh
    jp nz,-
    rl c
    rl b
    ld a,c
    cpl
    ld c,a
    ld a,b
    cpl
    ld b,a
    ret

Z80 Bits

See also http://baze.au.com/misc/z80bits.html

TODO

Use Meka's CLOCK and/or a test framework to get some timing data.


Retrieved from //www.smspower.org/Development/DivMod
Page last modified on Tue Nov 08, 2011 9:37 am