1;--------------------------------------------------------------------------
2;  divunsigned.s
3;
4;  Copyright (C) 2000-2012, Michael Hope, Philipp Klaus Krause, Marco Bodrato
5;
6;  This library is free software; you can redistribute it and/or modify it
7;  under the terms of the GNU General Public License as published by the
8;  Free Software Foundation; either version 2, or (at your option) any
9;  later version.
10;
11;  This library is distributed in the hope that it will be useful,
12;  but WITHOUT ANY WARRANTY; without even the implied warranty of
13;  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14;  GNU General Public License for more details.
15;
16;  You should have received a copy of the GNU General Public License
17;  along with this library; see the file COPYING. If not, write to the
18;  Free Software Foundation, 51 Franklin Street, Fifth Floor, Boston,
19;   MA 02110-1301, USA.
20;
21;  As a special exception, if you link this library with other files,
22;  some of which are compiled with SDCC, to produce an executable,
23;  this library does not by itself cause the resulting executable to
24;  be covered by the GNU General Public License. This exception does
25;  not however invalidate any other reasons why the executable file
26;   might be covered by the GNU General Public License.
27;--------------------------------------------------------------------------
28
29        ;; Originally from GBDK by Pascal Felber.
30
31.area   _CODE
32
33.globl	__divuint
34.globl	__divuchar
35
36__divuint:
37        pop     af
38        pop     hl
39        pop     de
40        push    de
41        push    hl
42        push    af
43
44        jr      __divu16
45
46__divuchar:
47        ld      hl,#2+1
48        add     hl,sp
49
50        ld      e,(hl)
51        dec     hl
52        ld      l,(hl)
53
54        ;; Fall through
55__divu8::
56        ld      h,#0x00
57        ld      d,h
58        ; Fall through to __divu16
59
60        ;; unsigned 16-bit division
61        ;;
62        ;; Entry conditions
63        ;;   HL = dividend
64        ;;   DE = divisor
65        ;;
66        ;; Exit conditions
67        ;;   HL = quotient
68        ;;   DE = remainder
69        ;;   carry = 0
70        ;;   If divisor is 0, quotient is set to "infinity", i.e HL = 0xFFFF.
71        ;;
72        ;; Register used: AF,B,DE,HL
73__divu16::
74        ;; Two algorithms: one assumes divisor <2^7, the second
75        ;; assumes divisor >=2^7; choose the applicable one.
76        ld      a,e
77        and     a,#0x80
78        or      a,d
79        jr      NZ,.morethan7bits
80        ;; Both algorithms "rotate" 24 bits (H,L,A) but roles change.
81
82        ;; unsigned 16/7-bit division
83.atmost7bits:
84        ld      b,#16           ; bits in dividend and possible quotient
85        ;; Carry cleared by AND/OR, this "0" bit will pass trough HL.[*]
86        adc     hl,hl
87.dvloop7:
88        ;; HL holds both dividend and quotient. While we shift a bit from
89        ;;  MSB of dividend, we shift next bit of quotient in from carry.
90        ;; A holds remainder.
91        rla
92
93        ;; If remainder is >= divisor, next bit of quotient is 1.  We try
94        ;;  to compute the difference.
95        sub     a,e
96        jr      NC,.nodrop7     ; Jump if remainder is >= dividend
97        add     a,e             ; Otherwise, restore remainder
98        ;; The add above sets the carry, because sbc a,e did set it.
99.nodrop7:
100        ccf                     ; Complement borrow so 1 indicates a
101                                ;  successful substraction (this is the
102                                ;  next bit of quotient)
103        adc     hl,hl
104        djnz    .dvloop7
105        ;; Carry now contains the same value it contained before
106        ;; entering .dvloop7[*]: "0" = valid result.
107        ld      e,a             ; DE = remainder, HL = quotient
108        ret
109
110.morethan7bits:
111        ld      b,#9            ; at most 9 bits in quotient.
112        ld      a,l             ; precompute the first 7 shifts, by
113        ld      l,h             ;  doing 8
114        ld      h,#0
115        rr      l               ;  undoing 1
116.dvloop:
117        ;; Shift next bit of quotient into bit 0 of dividend
118        ;; Shift next MSB of dividend into LSB of remainder
119        ;; A holds both dividend and quotient. While we shift a bit from
120        ;;  MSB of dividend, we shift next bit of quotient in from carry
121        ;; HL holds remainder
122        adc     hl,hl           ; HL < 2^(7+9), no carry, ever.
123
124        ;; If remainder is >= divisor, next bit of quotient is 1. We try
125        ;;  to compute the difference.
126        sbc     hl,de
127        jr      NC,.nodrop      ; Jump if remainder is >= dividend
128        add     hl,de           ; Otherwise, restore remainder
129	;; The add above sets the carry, because sbc hl,de did set it.
130.nodrop:
131        ccf                     ; Complement borrow so 1 indicates a
132                                ;  successful substraction (this is the
133                                ;  next bit of quotient)
134        rla
135        djnz    .dvloop
136        ;; Take care of the ninth quotient bit! after the loop B=0.
137        rl      b               ; BA = quotient
138        ;; Carry now contains "0" = valid result.
139        ld      d,b
140        ld      e,a             ; DE = quotient, HL = remainder
141        ex      de,hl           ; HL = quotient, DE = remainder
142        ret
143
144