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         movsne  \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 subtractions 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         subsge  \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/subtractions 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 #ifdef CONFIG_ARM_PATCH_IDIV
 209         .align  3
 210 #endif
 211
 212 ENTRY(__udivsi3)
 213 ENTRY(__aeabi_uidiv)
 214 UNWIND(.fnstart)
 215
 216         subs    r2, r1, #1
 217         reteq   lr
 218         bcc     Ldiv0
 219         cmp     r0, r1
 220         bls     11f
 221         tst     r1, r2
 222         beq     12f
 223
 224         ARM_DIV_BODY r0, r1, r2, r3
 225
 226         mov     r0, r2
 227         ret     lr
 228
 229 11:     moveq   r0, #1
 230         movne   r0, #0
 231         ret     lr
 232
 233 12:     ARM_DIV2_ORDER r1, r2
 234
 235         mov     r0, r0, lsr r2
 236         ret     lr
 237
 238 UNWIND(.fnend)
 239 ENDPROC(__udivsi3)
 240 ENDPROC(__aeabi_uidiv)
 241
 242 ENTRY(__umodsi3)
 243 UNWIND(.fnstart)
 244
 245         subs    r2, r1, #1                      @ compare divisor with 1
 246         bcc     Ldiv0
 247         cmpne   r0, r1                          @ compare dividend with divisor
 248         moveq   r0, #0
 249         tsthi   r1, r2                          @ see if divisor is power of 2
 250         andeq   r0, r0, r2
 251         retls   lr
 252
 253         ARM_MOD_BODY r0, r1, r2, r3
 254
 255         ret     lr
 256
 257 UNWIND(.fnend)
 258 ENDPROC(__umodsi3)
 259
 260 #ifdef CONFIG_ARM_PATCH_IDIV
 261         .align 3
 262 #endif
 263
 264 ENTRY(__divsi3)
 265 ENTRY(__aeabi_idiv)
 266 UNWIND(.fnstart)
 267
 268         cmp     r1, #0
 269         eor     ip, r0, r1                      @ save the sign of the result.
 270         beq     Ldiv0
 271         rsbmi   r1, r1, #0                      @ loops below use unsigned.
 272         subs    r2, r1, #1                      @ division by 1 or -1 ?
 273         beq     10f
 274         movs    r3, r0
 275         rsbmi   r3, r0, #0                      @ positive dividend value
 276         cmp     r3, r1
 277         bls     11f
 278         tst     r1, r2                          @ divisor is power of 2 ?
 279         beq     12f
 280
 281         ARM_DIV_BODY r3, r1, r0, r2
 282
 283         cmp     ip, #0
 284         rsbmi   r0, r0, #0
 285         ret     lr
 286
 287 10:     teq     ip, r0                          @ same sign ?
 288         rsbmi   r0, r0, #0
 289         ret     lr
 290
 291 11:     movlo   r0, #0
 292         moveq   r0, ip, asr #31
 293         orreq   r0, r0, #1
 294         ret     lr
 295
 296 12:     ARM_DIV2_ORDER r1, r2
 297
 298         cmp     ip, #0
 299         mov     r0, r3, lsr r2
 300         rsbmi   r0, r0, #0
 301         ret     lr
 302
 303 UNWIND(.fnend)
 304 ENDPROC(__divsi3)
 305 ENDPROC(__aeabi_idiv)
 306
 307 ENTRY(__modsi3)
 308 UNWIND(.fnstart)
 309
 310         cmp     r1, #0
 311         beq     Ldiv0
 312         rsbmi   r1, r1, #0                      @ loops below use unsigned.
 313         movs    ip, r0                          @ preserve sign of dividend
 314         rsbmi   r0, r0, #0                      @ if negative make positive
 315         subs    r2, r1, #1                      @ compare divisor with 1
 316         cmpne   r0, r1                          @ compare dividend with divisor
 317         moveq   r0, #0
 318         tsthi   r1, r2                          @ see if divisor is power of 2
 319         andeq   r0, r0, r2
 320         bls     10f
 321
 322         ARM_MOD_BODY r0, r1, r2, r3
 323
 324 10:     cmp     ip, #0
 325         rsbmi   r0, r0, #0
 326         ret     lr
 327
 328 UNWIND(.fnend)
 329 ENDPROC(__modsi3)
 330
 331 #ifdef CONFIG_AEABI
 332
 333 ENTRY(__aeabi_uidivmod)
 334 UNWIND(.fnstart)
 335 UNWIND(.save {r0, r1, ip, lr}   )
 336
 337         stmfd   sp!, {r0, r1, ip, lr}
 338         bl      __aeabi_uidiv
 339         ldmfd   sp!, {r1, r2, ip, lr}
 340         mul     r3, r0, r2
 341         sub     r1, r1, r3
 342         ret     lr
 343
 344 UNWIND(.fnend)
 345 ENDPROC(__aeabi_uidivmod)
 346
 347 ENTRY(__aeabi_idivmod)
 348 UNWIND(.fnstart)
 349 UNWIND(.save {r0, r1, ip, lr}   )
 350         stmfd   sp!, {r0, r1, ip, lr}
 351         bl      __aeabi_idiv
 352         ldmfd   sp!, {r1, r2, ip, lr}
 353         mul     r3, r0, r2
 354         sub     r1, r1, r3
 355         ret     lr
 356
 357 UNWIND(.fnend)
 358 ENDPROC(__aeabi_idivmod)
 359
 360 #endif
 361
 362 Ldiv0:
 363 UNWIND(.fnstart)
 364 UNWIND(.pad #4)
 365 UNWIND(.save {lr})
 366         str     lr, [sp, #-8]!
 367         bl      __div0
 368         mov     r0, #0                  @ About as wrong as it could be.
 369         ldr     pc, [sp], #8
 370 UNWIND(.fnend)
 371 ENDPROC(Ldiv0)