webentwicklung-frage-antwort-db.com.de

Wie macht man eine ganzzahlige Division (mit oder ohne Vorzeichen) in ARM?

Ich arbeite insbesondere an Cortex-A8 und Cortex-A9. Ich weiß, dass einige Architekturen nicht mit einer Ganzzahldivision ausgestattet sind, aber was ist der beste Weg, dies zu tun, als in float, divide, convert to integer zu konvertieren? Oder ist das tatsächlich die beste Lösung?

Prost! =)

16
Phonon

Der Compiler enthält normalerweise eine Division in seiner Bibliothek, beispielsweise gcclib, die ich aus gcc extrahiert habe, und verwende sie direkt:

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

schwimmen und zurückgehen ist wahrscheinlich nicht die beste lösung. Sie können es ausprobieren und sehen, wie schnell es ist ... Dies ist ein Multiplikator, könnte aber ebenso leicht zu einer Kluft führen:

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

Ich habe es keine Zeit, um zu sehen, wie schnell/langsam. Verstanden, ich verwende einen Cortex-m oben und du sprichst von einem Cortex-a, verschiedenen Enden des Spektrums, ähnlichen Float-Anweisungen und dem gcc lib-Material ist ähnlich, für den Cortex-m muss ich für den Daumen bauen, aber du kannst genauso leicht für den Arm zu bauen. Eigentlich sollte mit gcc alles automatisch funktionieren, es sollte nicht so sein, wie ich es gemacht habe. Auch andere Compiler sollten Sie nicht so tun müssen, wie ich es im Abenteuerspiel oben getan habe.

4
old_timer

Die Division durch einen konstanten Wert erfolgt schnell, indem Sie beispielsweise eine 64-Bit-Multiplikation durchführen und nach rechts verschieben:

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

hier ist R1 durch 1625 geteilt. Die Berechnung wird wie folgt durchgeführt: 64bitreg (R2: R3) = R1 * 0xA151C331, dann ist das Ergebnis das obere 32-Bit-Recht, das um 10 verschoben ist:

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 aus, für das A <2 ^ 32

10

Einige Copy-Pasta von anderswo für eine ganzzahlige Division: Grundsätzlich 3 Anweisungen pro Bit. Von dieser Website, obwohl ich es auch an vielen anderen Orten gesehen habe. Diese Website hat auch eine Nice-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)
7
Michael Dorgan

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

Die innere Schleife ist nicht so effizient wie die oben beschriebene signierte Lösung, dies unterstützt jedoch nicht signierte Arithmetik. Diese Routine führt eine 32-Bit-Division aus, wenn der obere Teil des Zählers (hi) kleiner als der Nenner (den) ist, andernfalls wird eine vollständige 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

Zusätzliche Prüfung auf Randbedingungen und Potenz von 2 kann hinzugefügt werden. Ausführliche Informationen finden Sie unter http://www.idwiz.co.za/Tips%20and%20Tricks/Divide.htm

2
selwyn

Ich habe die folgenden Funktionen für den ARM GNU Assembler geschrieben. Wenn Sie über keine CPU mit udiv/sdiv-Maschinenunterstützung verfügen, schneiden Sie in beiden Funktionen einfach die ersten Zeilen bis zur Beschriftung "0:" 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 vorzeichenlose Integer-Division und sdiv für vorzeichenbehaftete Integer-Division. Beide erwarten einen 64-Bit-Dividend (entweder mit oder ohne Vorzeichen) in r1 (High Word) und r0 (Low Word) und einen 32-Bit-Divisor in r2. Sie geben den Quotienten in r0 und den Rest in r1 zurück. Sie können sie in C header als extern definieren, wobei eine 64-Bit-Ganzzahl zurückgegeben wird, und den Quotienten und den Rest anschließend maskieren. Ein Fehler (Division durch 0 oder Überlauf) wird durch einen Rest angezeigt, dessen Absolutwert größer oder gleich dem Absolutwert des Divisors ist. Der vorzeichenbehaftete Divisionsalgorithmus verwendet die Unterscheidung zwischen den Dividenden und dem Divisor. Es wird nicht zuerst in positive Ganzzahlen konvertiert, da dies nicht alle Überlaufbedingungen richtig erkennen würde.

0
user371416