arch/arm/lib/lib1funcs.S

   1 /*
   2  * linux/arch/arm/lib/lib1funcs.S: Optimized ARM division routines
   3  *
   4  * Author: Nicolas Pitre <nico@fluxnic.net>
   5  *   - contributed to gcc-3.4 on Sep 30, 2003
   6  *   - adapted for the Linux kernel on Oct 2, 2003
   7  */
   8
   9 /* Copyright 1995, 1996, 1998, 1999, 2000, 2003 Free Software Foundation, Inc.
  10
  11 This file is free software; you can redistribute it and/or modify it
  12 under the terms of the GNU General Public License as published by the
  13 Free Software Foundation; either version 2, or (at your option) any
  14 later version.
  15
  16 In addition to the permissions in the GNU General Public License, the
  17 Free Software Foundation gives you unlimited permission to link the
  18 compiled version of this file into combinations with other programs,
  19 and to distribute those combinations without any restriction coming
  20 from the use of this file.  (The General Public License restrictions
  21 do apply in other respects; for example, they cover modification of
  22 the file, and distribution when not linked into a combine
  23 executable.)
  24
  25 This file is distributed in the hope that it will be useful, but
  26 WITHOUT ANY WARRANTY; without even the implied warranty of
  27 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  28 General Public License for more details.
  29
  30 You should have received a copy of the GNU General Public License
  31 along with this program; see the file COPYING.  If not, write to
  32 the Free Software Foundation, 59 Temple Place - Suite 330,
  33 Boston, MA 02111-1307, USA.  */
  34
  35
  36 #include <linux/linkage.h>
  37 #include <asm/assembler.h>
  38 #include <asm/unwind.h>
  39
  40 .macro ARM_DIV_BODY dividend, divisor, result, curbit
  41
  42 #if __LINUX_ARM_ARCH__ >= 5
  43
  44         clz     \curbit, \divisor
  45         clz     \result, \dividend
  46         sub     \result, \curbit, \result
  47         mov     \curbit, #1
  48         mov     \divisor, \divisor, lsl \result
  49         mov     \curbit, \curbit, lsl \result
  50         mov     \result, #0
  51
  52 #else
  53
  54         @ Initially shift the divisor left 3 bits if possible,
  55         @ set curbit accordingly.  This allows for curbit to be located
  56         @ at the left end of each 4 bit nibbles in the division loop
  57         @ to save one loop in most cases.
  58         tst     \divisor, #0xe0000000
  59         moveq   \divisor, \divisor, lsl #3
  60         moveq   \curbit, #8
  61         movne   \curbit, #1
  62
  63         @ Unless the divisor is very big, shift it up in multiples of
  64         @ four bits, since this is the amount of unwinding in the main
  65         @ division loop.  Continue shifting until the divisor is
  66         @ larger than the dividend.
  67 1:      cmp     \divisor, #0x10000000
  68         cmplo   \divisor, \dividend
  69         movlo   \divisor, \divisor, lsl #4
  70         movlo   \curbit, \curbit, lsl #4
  71         blo     1b
  72
  73         @ For very big divisors, we must shift it a bit at a time, or
  74         @ we will be in danger of overflowing.
  75 1:      cmp     \divisor, #0x80000000
  76         cmplo   \divisor, \dividend
  77         movlo   \divisor, \divisor, lsl #1
  78         movlo   \curbit, \curbit, lsl #1
  79         blo     1b
  80
  81         mov     \result, #0
  82
  83 #endif
  84
  85         @ Division loop
  86 1:      cmp     \dividend, \divisor
  87         subhs   \dividend, \dividend, \divisor
  88         orrhs   \result,   \result,   \curbit
  89         cmp     \dividend, \divisor,  lsr #1
  90         subhs   \dividend, \dividend, \divisor, lsr #1
  91         orrhs   \result,   \result,   \curbit,  lsr #1
  92         cmp     \dividend, \divisor,  lsr #2
  93         subhs   \dividend, \dividend, \divisor, lsr #2
  94         orrhs   \result,   \result,   \curbit,  lsr #2
  95         cmp     \dividend, \divisor,  lsr #3
  96         subhs   \dividend, \dividend, \divisor, lsr #3
  97         orrhs   \result,   \result,   \curbit,  lsr #3
  98         cmp     \dividend, #0                   @ Early termination?
  99         movnes  \curbit,   \curbit,  lsr #4     @ No, any more bits to do?
 100         movne   \divisor,  \divisor, lsr #4
 101         bne     1b
 102
 103 .endm
 104
 105
 106 .macro ARM_DIV2_ORDER divisor, order
 107
 108 #if __LINUX_ARM_ARCH__ >= 5
 109
 110         clz     \order, \divisor
 111         rsb     \order, \order, #31
 112
 113 #else
 114
 115         cmp     \divisor, #(1 << 16)
 116         movhs   \divisor, \divisor, lsr #16
 117         movhs   \order, #16
 118         movlo   \order, #0
 119
 120         cmp     \divisor, #(1 << 8)
 121         movhs   \divisor, \divisor, lsr #8
 122         addhs   \order, \order, #8
 123
 124         cmp     \divisor, #(1 << 4)
 125         movhs   \divisor, \divisor, lsr #4
 126         addhs   \order, \order, #4
 127
 128         cmp     \divisor, #(1 << 2)
 129         addhi   \order, \order, #3
 130         addls   \order, \order, \divisor, lsr #1
 131
 132 #endif
 133
 134 .endm
 135
 136
 137 .macro ARM_MOD_BODY dividend, divisor, order, spare
 138
 139 #if __LINUX_ARM_ARCH__ >= 5
 140
 141         clz     \order, \divisor
 142         clz     \spare, \dividend
 143         sub     \order, \order, \spare
 144         mov     \divisor, \divisor, lsl \order
 145
 146 #else
 147
 148         mov     \order, #0
 149
 150         @ Unless the divisor is very big, shift it up in multiples of
 151         @ four bits, since this is the amount of unwinding in the main
 152         @ division loop.  Continue shifting until the divisor is
 153         @ larger than the dividend.
 154 1:      cmp     \divisor, #0x10000000
 155         cmplo   \divisor, \dividend
 156         movlo   \divisor, \divisor, lsl #4
 157         addlo   \order, \order, #4
 158         blo     1b
 159
 160         @ For very big divisors, we must shift it a bit at a time, or
 161         @ we will be in danger of overflowing.
 162 1:      cmp     \divisor, #0x80000000
 163         cmplo   \divisor, \dividend
 164         movlo   \divisor, \divisor, lsl #1
 165         addlo   \order, \order, #1
 166         blo     1b
 167
 168 #endif
 169
 170         @ Perform all needed substractions to keep only the reminder.
 171         @ Do comparisons in batch of 4 first.
 172         subs    \order, \order, #3              @ yes, 3 is intended here
 173         blt     2f
 174
 175 1:      cmp     \dividend, \divisor
 176         subhs   \dividend, \dividend, \divisor
 177         cmp     \dividend, \divisor,  lsr #1
 178         subhs   \dividend, \dividend, \divisor, lsr #1
 179         cmp     \dividend, \divisor,  lsr #2
 180         subhs   \dividend, \dividend, \divisor, lsr #2
 181         cmp     \dividend, \divisor,  lsr #3
 182         subhs   \dividend, \dividend, \divisor, lsr #3
 183         cmp     \dividend, #1
 184         mov     \divisor, \divisor, lsr #4
 185         subges  \order, \order, #4
 186         bge     1b
 187
 188         tst     \order, #3
 189         teqne   \dividend, #0
 190         beq     5f
 191
 192         @ Either 1, 2 or 3 comparison/substractions are left.
 193 2:      cmn     \order, #2
 194         blt     4f
 195         beq     3f
 196         cmp     \dividend, \divisor
 197         subhs   \dividend, \dividend, \divisor
 198         mov     \divisor,  \divisor,  lsr #1
 199 3:      cmp     \dividend, \divisor
 200         subhs   \dividend, \dividend, \divisor
 201         mov     \divisor,  \divisor,  lsr #1
 202 4:      cmp     \dividend, \divisor
 203         subhs   \dividend, \dividend, \divisor
 204 5:
 205 .endm
 206
 207
 208 ENTRY(__udivsi3)
 209 ENTRY(__aeabi_uidiv)
 210 UNWIND(.fnstart)
 211
 212         subs    r2, r1, #1
 213         reteq   lr
 214         bcc     Ldiv0
 215         cmp     r0, r1
 216         bls     11f
 217         tst     r1, r2
 218         beq     12f
 219
 220         ARM_DIV_BODY r0, r1, r2, r3
 221
 222         mov     r0, r2
 223         ret     lr
 224
 225 11:     moveq   r0, #1
 226         movne   r0, #0
 227         ret     lr
 228
 229 12:     ARM_DIV2_ORDER r1, r2
 230
 231         mov     r0, r0, lsr r2
 232         ret     lr
 233
 234 UNWIND(.fnend)
 235 ENDPROC(__udivsi3)
 236 ENDPROC(__aeabi_uidiv)
 237
 238 ENTRY(__umodsi3)
 239 UNWIND(.fnstart)
 240
 241         subs    r2, r1, #1                      @ compare divisor with 1
 242         bcc     Ldiv0
 243         cmpne   r0, r1                          @ compare dividend with divisor
 244         moveq   r0, #0
 245         tsthi   r1, r2                          @ see if divisor is power of 2
 246         andeq   r0, r0, r2
 247         retls   lr
 248
 249         ARM_MOD_BODY r0, r1, r2, r3
 250
 251         ret     lr
 252
 253 UNWIND(.fnend)
 254 ENDPROC(__umodsi3)
 255
 256 ENTRY(__divsi3)
 257 ENTRY(__aeabi_idiv)
 258 UNWIND(.fnstart)
 259
 260         cmp     r1, #0
 261         eor     ip, r0, r1                      @ save the sign of the result.
 262         beq     Ldiv0
 263         rsbmi   r1, r1, #0                      @ loops below use unsigned.
 264         subs    r2, r1, #1                      @ division by 1 or -1 ?
 265         beq     10f
 266         movs    r3, r0
 267         rsbmi   r3, r0, #0                      @ positive dividend value
 268         cmp     r3, r1
 269         bls     11f
 270         tst     r1, r2                          @ divisor is power of 2 ?
 271         beq     12f
 272
 273         ARM_DIV_BODY r3, r1, r0, r2
 274
 275         cmp     ip, #0
 276         rsbmi   r0, r0, #0
 277         ret     lr
 278
 279 10:     teq     ip, r0                          @ same sign ?
 280         rsbmi   r0, r0, #0
 281         ret     lr
 282
 283 11:     movlo   r0, #0
 284         moveq   r0, ip, asr #31
 285         orreq   r0, r0, #1
 286         ret     lr
 287
 288 12:     ARM_DIV2_ORDER r1, r2
 289
 290         cmp     ip, #0
 291         mov     r0, r3, lsr r2
 292         rsbmi   r0, r0, #0
 293         ret     lr
 294
 295 UNWIND(.fnend)
 296 ENDPROC(__divsi3)
 297 ENDPROC(__aeabi_idiv)
 298
 299 ENTRY(__modsi3)
 300 UNWIND(.fnstart)
 301
 302         cmp     r1, #0
 303         beq     Ldiv0
 304         rsbmi   r1, r1, #0                      @ loops below use unsigned.
 305         movs    ip, r0                          @ preserve sign of dividend
 306         rsbmi   r0, r0, #0                      @ if negative make positive
 307         subs    r2, r1, #1                      @ compare divisor with 1
 308         cmpne   r0, r1                          @ compare dividend with divisor
 309         moveq   r0, #0
 310         tsthi   r1, r2                          @ see if divisor is power of 2
 311         andeq   r0, r0, r2
 312         bls     10f
 313
 314         ARM_MOD_BODY r0, r1, r2, r3
 315
 316 10:     cmp     ip, #0
 317         rsbmi   r0, r0, #0
 318         ret     lr
 319
 320 UNWIND(.fnend)
 321 ENDPROC(__modsi3)
 322
 323 #ifdef CONFIG_AEABI
 324
 325 ENTRY(__aeabi_uidivmod)
 326 UNWIND(.fnstart)
 327 UNWIND(.save {r0, r1, ip, lr}   )
 328
 329         stmfd   sp!, {r0, r1, ip, lr}
 330         bl      __aeabi_uidiv
 331         ldmfd   sp!, {r1, r2, ip, lr}
 332         mul     r3, r0, r2
 333         sub     r1, r1, r3
 334         ret     lr
 335
 336 UNWIND(.fnend)
 337 ENDPROC(__aeabi_uidivmod)
 338
 339 ENTRY(__aeabi_idivmod)
 340 UNWIND(.fnstart)
 341 UNWIND(.save {r0, r1, ip, lr}   )
 342         stmfd   sp!, {r0, r1, ip, lr}
 343         bl      __aeabi_idiv
 344         ldmfd   sp!, {r1, r2, ip, lr}
 345         mul     r3, r0, r2
 346         sub     r1, r1, r3
 347         ret     lr
 348
 349 UNWIND(.fnend)
 350 ENDPROC(__aeabi_idivmod)
 351
 352 #endif
 353
 354 Ldiv0:
 355 UNWIND(.fnstart)
 356 UNWIND(.pad #4)
 357 UNWIND(.save {lr})
 358         str     lr, [sp, #-8]!
 359         bl      __div0
 360         mov     r0, #0                  @ About as wrong as it could be.
 361         ldr     pc, [sp], #8
 362 UNWIND(.fnend)
 363 ENDPROC(Ldiv0)