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