chiark - git - mdw - ssr/blob - StraySrc/Libraries/Sapphire/s/divide

   1 ;
   2 ; divide.s
   3 ;
   4 ; Various routines of a division-related nature (MDW/TMA)
   5 ;
   6 ; © 1994-1998 Straylight
   7 ;
   8
   9 ;----- Licensing note -------------------------------------------------------
  10 ;
  11 ; This file is part of Straylight's Sapphire library.
  12 ;
  13 ; Sapphire is free software; you can redistribute it and/or modify
  14 ; it under the terms of the GNU General Public License as published by
  15 ; the Free Software Foundation; either version 2, or (at your option)
  16 ; any later version.
  17 ;
  18 ; Sapphire is distributed in the hope that it will be useful,
  19 ; but WITHOUT ANY WARRANTY; without even the implied warranty of
  20 ; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21 ; GNU General Public License for more details.
  22 ;
  23 ; You should have received a copy of the GNU General Public License
  24 ; along with Sapphire.  If not, write to the Free Software Foundation,
  25 ; 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  26
  27 ;----- Standard header ------------------------------------------------------
  28
  29                 GET     libs:header
  30                 GET     libs:swis
  31
  32 ;----- Simple mathematics ---------------------------------------------------
  33
  34                 AREA    |Sapphire$$Code|,CODE,READONLY
  35
  36 ; --- divide ---
  37 ;
  38 ; On entry:     R0 == dividend
  39 ;               R1 == divisor
  40 ;
  41 ; On exit:      R0 == quotient
  42 ;               R1 == remainder
  43 ;
  44 ; Use:          A standard divide routine.  Fairly speedy, hopefully.
  45 ;               The results are always such that
  46 ;
  47 ;                       |quotient| <= |(divisor/dividend)|,
  48 ;
  49 ;                       |remainder| < |divisor|
  50 ;
  51 ;               and
  52 ;
  53 ;                       quotient * divisor + remainder == dividend
  54
  55                 EXPORT  divide
  56 divide          ROUT
  57
  58                 STMFD   R13!,{R2,R14}           ;Save some registers
  59
  60                 ; --- First, mess about with the signs ---
  61
  62                 ANDS    R2,R0,#&80000000        ;Get the dividend's sign bit
  63                 ORR     R2,R2,R2,LSR #1         ;Copy -- this is sign of mod
  64                 RSBNE   R0,R0,#0                ;Take absolute value of R0
  65                 ANDS    R14,R1,#&80000000       ;Get the divisor's sign too
  66                 RSBNE   R1,R1,#0                ;Take absolute value of R1
  67                 EOR     R2,R2,R14               ;Calculate sign of quotient
  68
  69                 ; --- Now do the division ---
  70
  71                 BL      div_unsigned            ;That's done for us elsewhere
  72
  73                 ; --- Now tidy everything up ---
  74
  75                 TST     R2,#&40000000           ;Is remainder to be negative?
  76                 RSBNE   R1,R1,#0                ;Yes -- negate it
  77                 TST     R2,#&80000000           ;Is quotient to be negative?
  78                 RSBNE   R0,R0,#0                ;Yes -- negate it
  79
  80                 LDMFD   R13!,{R2,PC}^           ;Return to caller
  81
  82                 LTORG
  83
  84 ; --- div_unsigned ---
  85 ;
  86 ; On entry:     R0 == dividend
  87 ;               R1 == divisor
  88 ;
  89 ; On exit:      R0 == quotient
  90 ;               R1 == remainder
  91 ;
  92 ; Use:          As for divide, except that it considers its operands to be
  93 ;               unsigned.
  94
  95                 EXPORT  div_unsigned
  96                 EXPORT  div_byZero
  97 div_unsigned    ROUT
  98
  99                 CMP     R1,#0                   ;Check for divide by zero
 100                 BEQ     div_byZero              ;Yes -- make the error
 101                 STMFD   R13!,{R2,R3,R14}        ;Save some registers
 102
 103                 ; --- A note about the method ---
 104                 ;
 105                 ; We use traditional long division, but unroll the loop a
 106                 ; lot to keep the thing ticking over at a good rate.
 107
 108                 MOV     R14,R1                  ;Look after the divisor
 109                 ANDS    R3,R0,#&80000000        ;Is the top dividend bit set?
 110                 MOVEQ   R3,R0                   ;No -- use the real thing
 111
 112                 ; --- Shift divisor up for long division ---
 113                 ;
 114                 ; We keep shifting the divisor up until it's greater than
 115                 ; the dividend, and then we skip ahead to the divide section
 116
 117                 MOV     R2,#0                   ;Quotient starts off at 0
 118 00div_unsigned  CMP     R3,R14,LSL #0
 119                 BLS     %10div_unsigned
 120                 CMP     R3,R14,LSL #1
 121                 BLS     %11div_unsigned
 122                 CMP     R3,R14,LSL #2
 123                 BLS     %12div_unsigned
 124                 CMP     R3,R14,LSL #3
 125                 BLS     %13div_unsigned
 126                 CMP     R3,R14,LSL #4
 127                 BLS     %14div_unsigned
 128                 CMP     R3,R14,LSL #5
 129                 BLS     %15div_unsigned
 130                 CMP     R3,R14,LSL #6
 131                 BLS     %16div_unsigned
 132                 CMP     R3,R14,LSL #7
 133                 MOVHI   R14,R14,LSL #8
 134                 BHI     %00div_unsigned
 135
 136                 ; --- Now we have the shift-down loop ---
 137                 ;
 138                 ; This is where the actual job of dividing is performed.
 139                 ; We shift the divisor back down until it's back where we
 140                 ; started again.
 141
 142 17div_unsigned  CMP     R0,R14,LSL #7
 143                 ADC     R2,R2,R2
 144                 SUBCS   R0,R0,R14,LSL #7
 145 16div_unsigned  CMP     R0,R14,LSL #6
 146                 ADC     R2,R2,R2
 147                 SUBCS   R0,R0,R14,LSL #6
 148 15div_unsigned  CMP     R0,R14,LSL #5
 149                 ADC     R2,R2,R2
 150                 SUBCS   R0,R0,R14,LSL #5
 151 14div_unsigned  CMP     R0,R14,LSL #4
 152                 ADC     R2,R2,R2
 153                 SUBCS   R0,R0,R14,LSL #4
 154 13div_unsigned  CMP     R0,R14,LSL #3
 155                 ADC     R2,R2,R2
 156                 SUBCS   R0,R0,R14,LSL #3
 157 12div_unsigned  CMP     R0,R14,LSL #2
 158                 ADC     R2,R2,R2
 159                 SUBCS   R0,R0,R14,LSL #2
 160 11div_unsigned  CMP     R0,R14,LSL #1
 161                 ADC     R2,R2,R2
 162                 SUBCS   R0,R0,R14,LSL #1
 163 10div_unsigned  CMP     R0,R14,LSL #0
 164                 ADC     R2,R2,R2
 165                 SUBCS   R0,R0,R14,LSL #0
 166
 167                 CMP     R14,R1                  ;Have we finished dividing?
 168                 MOVHI   R14,R14,LSR #8          ;No -- shift down a byte
 169                 BHI     %17div_unsigned         ;And loop round again
 170
 171                 ; --- Now tidy everything up ---
 172
 173                 MOV     R1,R0                   ;Copy results into registers
 174                 MOV     R0,R2
 175
 176                 LDMFD   R13!,{R2,R3,PC}^        ;Return to caller
 177
 178 div_byZero      ADR     R0,divByZero
 179                 SWI     OS_GenerateError
 180
 181 divByZero       DCD     1
 182                 DCB     "Division by zero",0
 183
 184                 LTORG
 185
 186 ; --- div10 ---
 187 ;
 188 ; On entry:     R0 == integer to divide
 189 ;
 190 ; On exit:      R0 == quotient after division by 10
 191 ;               R1 == remainder after division by 10
 192 ;
 193 ; Use:          Divides an integer very quickly by 10.
 194 ;
 195 ; [Generated by Straylight divc]
 196
 197                 EXPORT  div10
 198 div10           ROUT
 199
 200                 STMFD   R13!,{R2,R14}
 201                 MOVS    R2,R0
 202                 RSBMI   R0,R0,#0
 203                 MOV     R1,R0
 204
 205                 ADD     R0,R0,R0,LSR #1
 206                 ADD     R0,R0,R0,LSR #4
 207                 ADD     R0,R0,R0,LSR #8
 208                 ADD     R0,R0,R0,LSR #16
 209
 210                 MOV     R0,R0,LSR #4
 211
 212                 ADD     R14,R0,R0,LSL #2
 213                 SUB     R1,R1,R14,LSL #1
 214                 SUBS    R1,R1,#10
 215                 ADDGE   R0,R0,#1
 216                 ADDLT   R1,R1,#10
 217
 218                 CMP     R2,#0
 219                 RSBMI   R0,R0,#0
 220                 RSBMI   R1,R1,#0
 221                 LDMFD   R13!,{R2,PC}^
 222
 223                 LTORG
 224
 225 ; --- div_round ---
 226 ;
 227 ; On entry:     R0 == dividend
 228 ;               R1 == divisor
 229 ;
 230 ; On exit:      R0 == quotient, rounded to nearest integer
 231 ;               R1 == remainder
 232 ;
 233 ; Use:          Calculates a rounded-to-nearest quotient, rather than one
 234 ;               rounded towards zero, which is what divide returns you.
 235 ;
 236 ;               The remainder is fiddled during this process, so that the
 237 ;               properties
 238 ;
 239 ;                       quotient * divisor + remainder == dividend
 240 ;
 241 ;               and
 242 ;
 243 ;                       |remainder| < |divisor|
 244 ;
 245 ;               still hold (so the remainder's sign may well change).
 246
 247                 EXPORT  div_round
 248 div_round       ROUT
 249
 250                 STMFD   R13!,{R2,R14}           ;Save some registers
 251                 MOV     R2,R0                   ;Keep a copy of the dividend
 252                 CMP     R1,#0                   ;Is the divisor positive?
 253                 MOVGE   R14,R1                  ;Yes -- just copy it
 254                 RSBLT   R14,R1,#0               ;No -- negate it on the way
 255                 CMP     R0,#0                   ;Is the dividend positive?
 256                 ADDGE   R0,R0,R14,ASR #1        ;Yes -- add half the divisor
 257                 SUBLT   R0,R0,R14,ASR #1        ;No -- subtract it
 258                 SUB     R2,R2,R0                ;Remember this difference
 259                 BL      divide                  ;Do the division
 260                 ADD     R1,R1,R2                ;Modify remainder suitably
 261                 LDMFD   R13!,{R2,PC}^           ;Return to caller
 262
 263                 LTORG
 264
 265 ; --- div_u64x32 ---
 266 ;
 267 ; On entry:     R0,R1 == dividend (high word in R1)
 268 ;               R2 == divisor
 269 ;
 270 ; On exit:      R0 == quotient
 271 ;               R1 == remainder
 272 ;
 273 ; Use:          Divides a 64-bit unsigned value by a 32-bit unsigned value
 274 ;               yielding 32-bit unsigned quotient and remainder.  If there
 275 ;               are more than 32 bits of quotient, the return values are
 276 ;               undefined.
 277
 278                 EXPORT  div_u64x32
 279 div_u64x32      ROUT
 280
 281                 STMFD   R13!,{R14}              ;Save the link register
 282
 283                 MOV     R14,#8                  ;Initialise the loop counter
 284
 285 00div_u64x32
 286
 287                 GBLA    count
 288 count           SETA    4
 289
 290                 WHILE   count>0
 291
 292                 CMP     R1,R2                   ;Can we subtract here?
 293                 SUBCS   R1,R1,R2                ;Yes -- do that then
 294                 ADCS    R0,R0,R0                ;Shift up quotient/dividend
 295                 ADC     R1,R1,R1                ;Put next dividend bit in R1
 296
 297 count           SETA    count-1
 298                 WEND
 299
 300                 SUBS    R14,R14,#1              ;Decrement loop counter
 301                 BGT     %00div_u64x32           ;If more to do, loop round
 302
 303                 CMP     R1,R2                   ;Can we subtract here?
 304                 SUBCS   R1,R1,R2                ;Yes -- do that then
 305                 ADCS    R0,R0,R0                ;Shift up quotient
 306
 307                 LDMFD   R13!,{PC}^              ;And return to caller
 308
 309                 LTORG
 310
 311 ;----- That's all, folks ----------------------------------------------------
 312
 313                 END