Wie kann man ganzzahlige (signierte oder nicht signierte) Division am Arm treiben?

Question

Ich arbeite insbesondere an Cortex-A8 und Cortex-A9. Ich weiß, dass einige Architekturen nicht mit ganzzahliger Division einhergehen, aber wie kann man es am besten tun, als sich um zu schweben, zu teilen, zur Ganzzahl zu konvertieren? Oder ist das tatsächlich die beste Lösung?

Prost! =))

Answer 1

Der Compiler enthält normalerweise eine Kluft in seiner Bibliothek, GCClib, zum Beispiel habe ich sie von GCC extrahiert und verwendet sie direkt:

https://github.com/dwelch67/stm32vld/ Dann STM32F4D/Adventure/GCClib

Es ist wahrscheinlich nicht die beste Lösung zu gehen und zurück zu gehen und zurück zu gehen. Sie können es versuchen und sehen, wie schnell es ist ... dies ist ein Multiplikum, könnte es aber so leicht zu einer Kluft machen:

https://github.com/dwelch67/stm32vld/ dann stm32f4d/float01/vektoren.s

Ich habe es jedoch nicht Zeit, um zu sehen, wie schnell/langsam. Ich verwende einen Cortex-M oben und Sie sprechen von einem Cortex-A, unterschiedlichen Enden des Spektrums, ähnlichen Float-Anweisungen und das GCC-LIB-Zeug sind ähnlich, für die Cortex-M, die ich für Daumen bauen muss, aber Sie können Sie können genauso leicht für Arm zu bauen. Eigentlich sollte mit GCC alles nur automatisch funktionieren, dass Sie es nicht so tun müssen, wie ich es getan habe. Andere Compiler sollten es auch nicht so machen, wie ich es im Abenteuerspiel oben gemacht habe.

Answer 2

Die Teilung durch einen konstanten Wert erfolgt schnell, indem beispielsweise ein 64-Bit-Multiply- und Schichtrechte wie folgt durchgeführt wird:

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

Hier wird R1 bis 1625 geteilt. Die Berechnung erfolgt wie folgt: 64bitreg (R2: R3) = R1*0xa151C331, dann ist das Ergebnis die obere 32 -Bit -Rechte, die um 10 um 10 verschoben wird:

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

Sie können Ihre eigenen Konstanten aus dieser Formel berechnen:

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

Wählen Sie das größte n, für das a <2^32

Answer 3

Einige Kopienpasta von anderer Stelle für eine Ganzzahl-Kluft: Grundsätzlich 3 Anweisungen pro Bit. Aus Dies Website, obwohl ich es auch viele andere Orte gesehen habe.Dies Die Seite hat auch eine schöne Version, die im Allgemeinen schneller sein kann.

@ 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 4

Ich schrieb meine eigene Routine, um eine nicht signierte Abteilung auszuführen, da ich keine nicht signierte Version im Web finden konnte. Ich musste einen 64 -Bit -Wert mit einem 32 -Bit -Wert teilen, um ein 32 -Bit -Ergebnis zu erzielen.

Die innere Schleife ist nicht so effizient wie die oben angegebene signierte Lösung, aber dies unterstützt die nicht signierte Arithmetik. Diese Routine führt eine 32 -Bit -Division durch, wenn der hohe Teil des Zählers (HI) kleiner ist als der Nenner (DEN), ansonsten wird eine volle 64 -Bit -Division durchgeführt (HI: lo/den). Das Ergebnis ist in 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

Eine zusätzliche Überprüfung der Randbedingungen und der Leistung von 2 kann hinzugefügt werden. Vollständige Details finden Sie unter http://www.idwiz.co.za/tips%20and%20tricks/divide.htm

Answer 5

Ich habe die folgenden Funktionen für die geschrieben ARM GNU Assembler. Wenn Sie keine CPU mit haben udiv/sdiv Maschinenunterstützung, schneiden Sie einfach die ersten Einstellungen bis zur Beschriftung "0:" in beiden Funktionen aus.

.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

Es gibt zwei Funktionen, udiv für unsignierte Ganzzahl Division und sdiv Für die unterschriebene Ganzzahlabteilung. Beide erwarten eine 64-Bit-Dividende (entweder signiert oder unsigniert) in r1 (hohes Wort) und r0 (niedriges Wort) und ein 32-Bit-Divisor in r2. Sie geben den Quotienten zurück in r0 und der Rest in r1, Sie können sie also in a definieren C header wie extern Rückgabe einer 64-Bit-Ganzzahl und maskieren Sie den Quotienten und den Rest danach. Ein Fehler (Teilung durch 0 oder Überlauf) wird durch einen Rest angezeigt, der einen absoluten Wert mehr als oder gleich den absoluten Wert des Divisors hat. Der signierte Abteilungsalgorithmus verwendet Fallunterscheidung durch die Vorzeichen sowohl der Dividenden als auch des Divisors; Es wandelt sich nicht zuerst in positive Ganzzahlen um, da dies nicht alle Überlaufbedingungen richtig erkennen würde.