assembly - ¿Cómo se hace una división de enteros(con o sin signo) en ARM?

integer-division instruction-set

Question

Estoy trabajando en Cortex-A8 y Cortex-A9 en particular. Sé que algunas arquitecturas no vienen con división de enteros, pero ¿cuál es la mejor manera de hacerlo que no sea convertir a flotar, dividir, convertir a entero? ¿O es esa la mejor solución?

¡Aclamaciones! =)

Answer 1

Algunas copias de pasta de otro lugar para una división entera: Básicamente, 3 instrucciones por bit. Desde this sitio web, aunque también lo he visto en muchos otros lugares. This sitio también tiene una buena versión que puede ser más rápida en general.

@ Entry  r0: numerator (lo) must be signed positive
@        r2: deniminator (den) must be non-zero and signed negative
idiv:
        lo .req r0; hi .req r1; den .req r2
        mov hi, #0 @ hi = 0
        adds lo, lo, lo
        .rept 32 @ repeat 32 times
          adcs hi, den, hi, lsl #1
          subcc hi, hi, den
          adcs lo, lo, lo
        .endr
        mov pc, lr @ return
@ Exit   r0: quotient (lo)
@        r1: remainder (hi)

Answer 2

El compilador normalmente incluye una división en su biblioteca, gcclib, por ejemplo, los he extraído de gcc y los uso directamente:

https://github.com/dwelch67/stm32vld/ then stm32f4d / adventure / gcclib

Ir a flotar y volver probablemente no sea la mejor solución. Puedes probarlo y ver qué tan rápido es ... Esto es una multiplicación, pero podría fácilmente dividirla:

https://github.com/dwelch67/stm32vld/ entonces stm32f4d / float01 / vectors.s

Sin embargo, no tuve tiempo de ver qué tan rápido / lento. Entendido, estoy usando una corteza-m arriba y usted está hablando de una corteza-a, diferentes extremos del espectro, instrucciones similares de flotación y las cosas de gcc lib son similares, para la corteza-m que tengo que construir para el pulgar, pero puede tan fácil de construir para el brazo. En realidad, con gcc, todo debería funcionar automáticamente, no deberías necesitar hacerlo como lo hice yo. Otros compiladores tampoco deberían tener que hacerlo como lo hice en el juego de aventuras anterior.

Answer 3

Escribí las siguientes funciones para el ensamblador ARM GNU . Si no tiene una CPU con udiv/sdiv machine, simplemente corte las primeras líneas hasta la etiqueta "0:" en cualquiera de las funciones.

.arm
.cpu    cortex-a7
.syntax unified

.type   udiv,%function
.globl  udiv
udiv:   tst     r1,r1
        bne     0f
        udiv    r3,r0,r2
        mls     r1,r2,r3,r0
        mov     r0,r3
        bx      lr
0:      cmp     r1,r2
        movhs   r1,r2
        bxhs    lr
        mvn     r3,0
1:      adds    r0,r0
        adcs    r1,r1
        cmpcc   r1,r2
        subcs   r1,r2
        orrcs   r0,1
        lsls    r3,1
        bne     1b
        bx      lr
.size   udiv,.-udiv

.type   sdiv,%function
.globl  sdiv
sdiv:   teq     r1,r0,ASR 31
        bne     0f
        sdiv    r3,r0,r2
        mls     r1,r2,r3,r0
        mov     r0,r3
        bx      lr
0:      mov     r3,2
        adds    r0,r0
        and     r3,r3,r1,LSR 30
        adcs    r1,r1
        orr     r3,r3,r2,LSR 31
        movvs   r1,r2
        ldrvc   pc,[pc,r3,LSL 2]
        bx      lr
        .int    1f
        .int    3f
        .int    5f
        .int    11f
1:      cmp     r1,r2
        movge   r1,r2
        bxge    lr
        mvn     r3,1
2:      adds    r0,r0
        adcs    r1,r1
        cmpvc   r1,r2
        subge   r1,r2
        orrge   r0,1
        lsls    r3,1
        bne     2b
        bx      lr
3:      cmn     r1,r2
        movge   r1,r2
        bxge    lr
        mvn     r3,1
4:      adds    r0,r0
        adcs    r1,r1
        cmnvc   r1,r2
        addge   r1,r2
        orrge   r0,1
        lsls    r3,1
        bne     4b
        rsb     r0,0
        bx      lr
5:      cmn     r1,r2
        blt     6f
        tsteq   r0,r0
        bne     7f
6:      mov     r1,r2
        bx      lr
7:      mvn     r3,1
8:      adds    r0,r0
        adcs    r1,r1
        cmnvc   r1,r2
        blt     9f
        tsteq   r0,r3
        bne     10f
9:      add     r1,r2
        orr     r0,1
10:     lsls    r3,1
        bne     8b
        rsb     r0,0
        bx      lr
11:     cmp     r1,r2
        blt     12f
        tsteq   r0,r0
        bne     13f
12:     mov     r1,r2
        bx      lr
13:     mvn     r3,1
14:     adds    r0,r0
        adcs    r1,r1
        cmpvc   r1,r2
        blt     15f
        tsteq   r0,r3
        bne     16f
15:     sub     r1,r2
        orr     r0,1
16:     lsls    r3,1
        bne     14b
        bx      lr

Hay dos funciones, udiv para la división de enteros sin signo y sdiv para la división de enteros con signo. Ambos esperan un dividendo de 64 bits (con o sin signo) en r1 (palabra alta) y r0 (palabra baja), y un divisor de 32 bits en r2 . Devuelven el cociente en r0 y el resto en r1 , por lo que puede definirlos en un C header como extern devuelve un entero de 64 bits y enmascarar el cociente y el resto posteriormente. Un error (división por 0 o desbordamiento) se indica por un resto que tiene un valor absoluto mayor o igual que el valor absoluto del divisor. El algoritmo de división con signo utiliza la distinción entre mayúsculas y minúsculas por los signos tanto de dividendo como de divisor; no se convierte primero a enteros positivos, ya que eso no detectaría todas las condiciones de desbordamiento correctamente.

Answer 4

Escribí mi propia rutina para realizar una división sin firmar ya que no pude encontrar una versión sin firmar en la web. Necesitaba dividir un valor de 64 bits con un valor de 32 bits para obtener un resultado de 32 bits.

El bucle interno no es tan eficiente como la solución firmada proporcionada anteriormente, pero esto sí es compatible con la aritmética no firmada. Esta rutina realiza una división de 32 bits si la parte alta del numerador (hi) es más pequeña que el denominador (den), de lo contrario se realiza una división completa de 64 bits (hi: lo / den). El resultado está en lo.

  cmp     hi, den                   // if hi < den do 32 bits, else 64 bits
  bpl     do64bits
  REPT    32
    adds    lo, lo, lo              // shift numerator through carry
    adcs    hi, hi, hi
    subscc  work, hi, den           // if carry not set, compare        
    subcs   hi, hi, den             // if carry set, subtract
    addcs   lo, lo, #1              // if carry set, and 1 to quotient
  ENDR

  mov     r0, lo                    // move result into R0
  mov     pc, lr                    // return

do64bits:
  mov     top, #0
  REPT    64
    adds    lo, lo, lo              // shift numerator through carry
    adcs    hi, hi, hi
    adcs    top, top, top
    subscc  work, top, den          // if carry not set, compare        
    subcs   top, top, den           // if carry set, subtract
    addcs   lo, lo, #1              // if carry set, and 1 to quotient
  ENDR
  mov     r0, lo                    // move result into R0
  mov     pc, lr                    // return

Se pueden agregar controles adicionales para condiciones de contorno y potencia de 2. Los detalles completos se pueden encontrar en http://www.idwiz.co.za/Tips%20and%20Tricks/Divide.htm

Answer 5

La división por un valor constante se realiza rápidamente haciendo una multiplicación de 64 bits y un desplazamiento hacia la derecha, por ejemplo, como este:

LDR     R3, =0xA151C331
UMULL   R3, R2, R1, R3
MOV     R0, R2,LSR#10

aquí R1 se divide por 1625. El cálculo se realiza de la siguiente manera: 64 bits (R2: R3) = R1 * 0xA151C331, luego el resultado es la parte superior derecha de 32 bits desplazada a la derecha por 10:

R1*0xA151C331/2^(32+10) = R1*0.00061538461545751488 = R1/1624.99999980

Puedes calcular tus propias constantes a partir de esta fórmula:

x / N ==  (x*A)/2^(32+n)   -->       A = 2^(32+n)/N

seleccione la n más grande, para la cual A <2 ^ 32