gbdk-2020 | GameBoy Development Kit |
| download: https://git.y1.nz/archives/gbdk.tar.gz | |
| README | Files | Log | Refs | LICENSE |
commit 230971708aee76983fe7fea5037dda816c32515b parent bab52712cfc1c1d38dd4cb26dec7c596b6b65486 Author: Phidias618 <126189685+Phidias618@users.noreply.github.com> Date: Wed, 21 Jan 2026 16:52:10 +0100 Optimisation of divisions (#856) Optimisation of the integer divisions Diffstat:
| M | gbdk-lib/libc/asm/sm83/div.s | 516 | +++++++++++++++++++++++++++++++++++++++++-------------------------------------- |
1 file changed, 266 insertions(+), 250 deletions(-)
diff --git a/gbdk-lib/libc/asm/sm83/div.s b/gbdk-lib/libc/asm/sm83/div.s @@ -29,166 +29,295 @@ ;-------------------------------------------------------------------------- ;; Originally from GBDK by Pascal Felber. + ;; Updated by Phidias618 .module divmod .area _CODE +.globl __divuchar +.globl __moduchar +.globl __divuint +.globl __moduint + .globl __divsuchar .globl __modsuchar .globl __divuschar .globl __moduschar .globl __divschar .globl __modschar + .globl __divsint .globl __modsint -.globl __divuchar -.globl __moduchar -.globl __divuint -.globl __moduint - -__divsuchar: - ld c, a - ld b, #0 - - jp signexte - -__modsuchar: - ld c, a - ld b, #0 - - call signexte - - ld c, e - ld b, d - - ret - -__divuschar: - ld d, #0 - ld c, a ; Sign extend - rlca - sbc a - ld b,a - - jp .div16 - -__moduschar: - ld d, #0 - ld c, a ; Sign extend - rlca - sbc a - ld b,a +; unsigned division - call .div16 +__moduchar: + ld c, e + ld e, a + xor a + ld b, a + ld d, a +__moduint: + call .divmod_uint_bcde ld c, e ld b, d ret -__divschar: - ld c, a - - call .div8 - +.divmod_uchar_bcde: +__divuchar: + ld c, e + ld e, a + xor a + ld b, a + ld d, a + ; Fall through .divmod_uint_bcde +.divmod_uint_bcde: +__divuint:: + ; computes the quotient and the remainder of X / Y + ; X is stored in de + ; Y is stored in bc + ; outputs the quotient in bc + ; outputs the remainder in de + ; if Y = 0 then the carry is set and quotient = 0 and remainder = 0 + ; otherwise the carry is cleared + + + ; stores -Y in hl and check that -Y is not zero + xor a + sub c + ld l, a + sbc a + sub b + ld h, a + + or l + jr z, .division_by_zero + + ; if X < Y then + ; return quotient = 0 and remainder = X + ; else + ; computes the largest (Y << K) such that (Y << K) <= X + ; put the 17 bit value -(Y << (K + 1)) into hl with the MSB stored using the carry + ; put K, using a base 1 representation, using the most significant bits of bc + ld bc, #0 + + ld a, e + add l + ld a, d + adc h + jr c, 10$ + ; X < Y + ; bc already stores 0 ret - -__modschar: - ld c, a - - call .div8 - - ld c, e - ld b, d - +0$: + rr b + rr c +10$: + add hl, hl + jr nc, 1$ + + ld a, e + add l + ld a, d + adc h + jr c, 0$ + scf +1$: + + ; swaps the content of hl and de + ld a, h + ld h, d + ld d, a + + ld a, l + ld l, e + ld e, a + + ; computes X / Y one bit at a time using the following algorithm + ; r = X + ; q = 0 + ; while K >= 0 + ; b = 0 + ; if (Y << K) <= r then + ; r += -(Y << K) + ; b = 1 + ; q = (q << 1) | b + ; K -= 1 + ; + ; + ; r is stored in hl + ; q is stored in bc + ; storing both q and K in bc will not create issue as they will not use the same bits at the same time + ; -(Y << K) is stored in de +2$: + ; on the first iteration : + ; this shifts DE such that DE now stores -(Y << K) + ; on every iteration but the first: + ; transforms -(Y << K) into -(Y << (K-1)) + ; sra d is not used as the MSB should always be filled with a 1 when shifting de + ; this works because the carry will always be set if this is not the first iteration + rr d + rr e + + ; compare remainder with (Y << K) + ld a, e + add l + ld a, d + adc h + + jr nc, 3$ + add hl, de +3$: + ; fill bc with one bit of the result and decrements K at the same time + rl c + rl b + + jr c, 2$ +ret_hl_in_de: + ld d, h + ld e, l + ; status of the registers + ; bc = quotient + ; de = remainder + ; carry = 0 if Y != 0, 1 if Y == 0 + ret +.division_by_zero: + ; returns both a quotient of 0 and a remainder of 0 + ; if this is reached, then bc = 0 + scf + jr ret_hl_in_de -__divsint: - ld a, e - ld e, c - ld c, a - ld a, d - ld d, b - ld b, a - - jp .div16 - -__modsint: - ld a, e - ld e, c - ld c, a - - ld a, d - ld d, b - ld b, a - - call .div16 - - ld c, e - ld b, d +; mixed sign division +__modsuchar: + call .divmod_suchar_bcde + ld b, d + ld c, e ret +.divmod_suchar_bcde: +__divsuchar: + ld d, #0 + ld c, e + ld e, a + + jr signext_c - ;; Unsigned -__divuchar: - ld c, a - - call .divu8 - +__moduschar: + call .divmod_uschar_bcde + ld b, d + ld c, e ret +.divmod_uschar_bcde: +__divuschar: + ld b, #0 + ld c, e + ld e, a + add a + sbc a + ld d, a + + jr .divmod_sint_bcde + +; signed division -__moduchar: - ld c, a - - call .divu8 - - ld c, e - ld b, d - +__modschar: + call .divmod_schar_bcde + ld b, d + ld c, e ret - -__divuint: - ld a, e - ld e, c - ld c, a - - ld a, d - ld d, b - ld b, a - - jp .divu16 - -__moduint: - ld a, e - ld e, c - ld c, a - - ld a, d - ld d, b - ld b, a - - call .divu16 - - ld c, e - ld b, d - +__modsint:: + call .divmod_sint_bcde + ld b, d + ld c, e ret +; these 2 functions exists for compatibility reasons .div8:: .mod8:: - ld a,c ; Sign extend + ld a, c + ; Fall through .divmod_schar_bcde +.divmod_schar_bcde: +__divschar: + ld c, e + ld e, a + add a + sbc a + ld d, a +signext_c: + ld a, c rlca - sbc a - ld b,a -signexte: - ld a, e ; Sign extend + sbc a + ld b, a + ; Fall through .divmod_sint_bcde +.divmod_sint_bcde: +__divsint:: + ; saves the sign of the quotient as the carry and the sign of the remainder as the 7th bit of A + ld a, d ; high byte of dividend + xor b ; high byte of divisor + rla ; save the 7th bit of A as the carry + ld a, d + push af + + ; take the absolute value of de + add a + jr nc, 0$ + + xor a + sub e + ld e, a + sbc a + sub d + ld d, a +0$: + ; take the absolute value of bc + bit 7, b + jr z, 1$ + + xor a + sub c + ld c, a + sbc a + sub b + ld b, a +1$: + call .divmod_uint_bcde + jr c, .error + pop af ; retrieve the signs the the quotient and the sign of the remainder + + jr nc, 2$ + ld l, a ; saves the sign of the remainder + ; negates the quotient + xor a + sub c + ld c, a + sbc a + sub b + ld b, a + + ld a, l +2$: rlca - sbc a - ld d, a + ret nc + ; negates the remainder + xor a + sub e + ld e, a + sbc a + sub d + ld d, a + + or a ; clears the carry + ret +.error: + pop hl ; do not pop af in order to preserve the carry as set + ret + - ; Fall through to .div16 +; the following functions are here in order to not break compatibility ;; 16-bit division ;; @@ -205,136 +334,23 @@ signexte: ;; Register used: AF,BC,DE,HL .div16:: .mod16:: - ;; Determine sign of quotient by xor-ing high bytes of dividend - ;; and divisor. Quotient is positive if signs are the same, negative - ;; if signs are different - ;; Remainder has same sign as dividend - ld a,b ; Get high byte of dividend - push af ; Save as sign of remainder - xor d ; Xor with high byte of divisor - push af ; Save sign of quotient - - ;; Take absolute value of divisor - bit 7,d - jr Z,.chkde ; Jump if divisor is positive - sub a ; Subtract divisor from 0 - sub e - ld e,a - sbc a ; Propagate borrow (A=0xFF if borrow) - sub d - ld d,a - ;; Take absolute value of dividend -.chkde: - bit 7,b - jr Z,.dodiv ; Jump if dividend is positive - sub a ; Subtract dividend from 0 - sub c - ld c,a - sbc a ; Propagate borrow (A=0xFF if borrow) - sub b - ld b,a - ;; Divide absolute values -.dodiv: - call .divu16 - jr C,.exit ; Exit if divide by zero - ;; Negate quotient if it is negative - pop af ; recover sign of quotient - and #0x80 - jr Z,.dorem ; Jump if quotient is positive - sub a ; Subtract quotient from 0 - sub c - ld c,a - sbc a ; Propagate borrow (A=0xFF if borrow) - sub b - ld b,a -.dorem: - ;; Negate remainder if it is negative - pop af ; recover sign of remainder - and #0x80 - ret Z ; Return if remainder is positive - sub a ; Subtract remainder from 0 - sub e - ld e,a - sbc a ; Propagate remainder (A=0xFF if borrow) - sub d - ld d,a - ret -.exit: - add sp, #4 - ret - + ld hl, #.divmod_sint_bcde +swap_bc_de_jp_hl: + ld a, b + ld b, d + ld d, a + + ld a, c + ld c, e + ld e, a + + jp (hl) .divu8:: .modu8:: ld b,#0x00 ld d,b - ; Fall through to divu16 - + ; Fall through to .divu16 .divu16:: .modu16:: - ;; Check for division by zero - ld a,e - or d - jr Z,.error ; Branch if divisor is zero - - ld l,c ; L = low byte of dividend/quotient - ld h,b ; H = high byte of dividend/quotient - ld bc,#0x00 ; BC = remainder - or a ; Clear carry to start - ld a,#16 ; 16 bits in dividend -.dvloop: - ;; Shift next bit of quotient into bit 0 of dividend - ;; Shift next MSB of dividend into LSB of remainder - ;; BC holds both dividend and quotient. While we shift a bit from - ;; MSB of dividend, we shift next bit of quotient in from carry - ;; HL holds remainder - ;; Do a 32-bit left shift, shifting carry to L, L to H, - ;; H to C, C to B - push af ; save number of bits remaining - rl l ; Carry (next bit of quotient) to bit 0 - rl h ; Shift remaining bytes - rl c - rl b ; Clears carry since BC was 0 - ;; If remainder is >= divisor, next bit of quotient is 1. This - ;; bit goes to carry - push bc ; Save current remainder - ld a,c ; Subtract divisor from remainder - sbc e - ld c,a - ld a,b - sbc d - ld b,a - ccf ; Complement borrow so 1 indicates a - ; successful subtraction (this is the - ; next bit of quotient) - jr C,.drop ; Jump if remainder is >= dividend - pop bc ; Otherwise, restore remainder - pop af ; recover # bits remaining, carry flag destroyed - dec a - or a ; restore (clear) the carry flag - jr NZ,.dvloop - jr .nodrop - -.drop: - pop af ; faster and smaller than 2x inc sp - pop af ; recover # bits remaining, carry flag destroyed - dec a - scf ; restore (set) the carry flag - jr NZ,.dvloop - -.nodrop: - ;; Shift last carry bit into quotient - ld d,b ; DE = remainder - ld e,c - rl l ; Carry to L - ld c,l ; C = low byte of quotient - rl h - ld b,h ; B = high byte of quotient - or a ; Clear carry, valid result - ret - -.error: - ld bc,#0x00 ; Divide by zero error - ld d,b - ld e,c - scf ; Set carry, invalid result - ret + ld hl, #.divmod_uint_bcde + jr swap_bc_de_jp_hl
This webpage is intended to be an accessible preview of this repository. To get a fuller picture, clone it and use the git CLI.