sdcc/device/lib/z80/divunsigned.s

   1 ;--------------------------------------------------------------------------
   2 ;  divunsigned.s
   3 ;
   4 ;  Copyright (C) 2000-2021, 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         .module divunsigned
  32         .optsdcc -mz80 sdcccall(1)
  33
  34 .area   _CODE
  35
  36 .globl  __divuint
  37 .globl  __divuchar
  38
  39
  40 __divuchar:
  41         ld      e, l
  42         ld      l, a
  43
  44         ;; Fall through
  45 __divu8::
  46         ld      h,#0x00
  47         ld      d,h
  48         ; Fall through to __divu16
  49
  50         ;; unsigned 16-bit division
  51         ;;
  52         ;; Entry conditions
  53         ;;   HL = dividend
  54         ;;   DE = divisor
  55         ;;
  56         ;; Exit conditions
  57         ;;   DE = quotient
  58         ;;   HL = remainder
  59         ;;   carry = 0
  60         ;;   If divisor is 0, quotient is set to "infinity", i.e HL = 0xFFFF.
  61         ;;
  62         ;; Register used: AF,B,DE,HL
  63 __divuint:
  64 __divu16::
  65         ;; Two algorithms: one assumes divisor <2^7, the second
  66         ;; assumes divisor >=2^7; choose the applicable one.
  67         ld      a,e
  68         and     a,#0x80
  69         or      a,d
  70         jr      NZ,.morethan7bits
  71         ;; Both algorithms "rotate" 24 bits (H,L,A) but roles change.
  72
  73         ;; unsigned 16/7-bit division
  74 .atmost7bits:
  75         ld      b,#16           ; bits in dividend and possible quotient
  76         ;; Carry cleared by AND/OR, this "0" bit will pass trough HL.[*]
  77         adc     hl,hl
  78 .dvloop7:
  79         ;; HL holds both dividend and quotient. While we shift a bit from
  80         ;;  MSB of dividend, we shift next bit of quotient in from carry.
  81         ;; A holds remainder.
  82         rla
  83
  84         ;; If remainder is >= divisor, next bit of quotient is 1.  We try
  85         ;;  to compute the difference.
  86         sub     a,e
  87         jr      NC,.nodrop7     ; Jump if remainder is >= dividend
  88         add     a,e             ; Otherwise, restore remainder
  89         ;; The add above sets the carry, because sbc a,e did set it.
  90 .nodrop7:
  91         ccf                     ; Complement borrow so 1 indicates a
  92                                 ;  successful subtraction (this is the
  93                                 ;  next bit of quotient)
  94         adc     hl,hl
  95         djnz    .dvloop7
  96         ;; Carry now contains the same value it contained before
  97         ;; entering .dvloop7[*]: "0" = valid result.
  98         ld      e,a             ; DE = remainder, HL = quotient
  99         ex      de, hl
 100         ret
 101
 102 .morethan7bits:
 103         ld      b,#9            ; at most 9 bits in quotient.
 104         ld      a,l             ; precompute the first 7 shifts, by
 105         ld      l,h             ;  doing 8
 106         ld      h,#0
 107         rr      l               ;  undoing 1
 108 .dvloop:
 109         ;; Shift next bit of quotient into bit 0 of dividend
 110         ;; Shift next MSB of dividend into LSB of remainder
 111         ;; A holds both dividend and quotient. While we shift a bit from
 112         ;;  MSB of dividend, we shift next bit of quotient in from carry
 113         ;; HL holds remainder
 114         adc     hl,hl           ; HL < 2^(7+9), no carry, ever.
 115
 116         ;; If remainder is >= divisor, next bit of quotient is 1. We try
 117         ;;  to compute the difference.
 118         sbc     hl,de
 119         jr      NC,.nodrop      ; Jump if remainder is >= dividend
 120         add     hl,de           ; Otherwise, restore remainder
 121         ;; The add above sets the carry, because sbc hl,de did set it.
 122 .nodrop:
 123         ccf                     ; Complement borrow so 1 indicates a
 124                                 ;  successful subtraction (this is the
 125                                 ;  next bit of quotient)
 126         rla
 127         djnz    .dvloop
 128         ;; Take care of the ninth quotient bit! after the loop B=0.
 129         rl      b               ; BA = quotient
 130         ;; Carry now contains "0" = valid result.
 131         ld      d,b
 132         ld      e,a             ; DE = quotient, HL = remainder
 133         ret
 134