Ist x>>16 das Gleiche wie x/65536?

[Mike (Gast)]

Hallo,

ich programmiere gerade ein simples digitales Filter auf einem ARM 
Cortex M0+ (SAMD11). Der Compiler ist gcc. Dabei muss des öfteren durch 
65536 dividiert werden, um den Zahlenbereich zu begrenzen. Korrekt würde 
es also so lauten:

int32_t x;
...
x /= 65536;

Allerdings ist die Division eine aufwändige Operation, da der ARM sie 
iterativ berechnen muss, denn es gibt keinen Maschinen-Divisionsbefehl. 
Theoretisch würde es genügen, die beiden oberen Bytes von x in die 
beiden niederwertigsten Bytes zu verschieben:

int32_t x;
...
x >>= 16;

Doch ist garantiert, dass bei negativem x von links Einsen eingeschoben 
werden, so dass das Ergebnis negativ bleibt? Die ANSI-C-Dokumentationen 
schweigen sich darüber aus. Mit gcc scheint es zu funktionieren, aber 
wie sieht es bei anderen Compilern aus? Gibt es eine saubere 
Möglichkeit, einen arithmetischen Shift erzwingen?

[Route_66 H. (route_66)]

Mike schrieb:
> Die ANSI-C-Dokumentationen
> schweigen sich darüber aus.

Ausprobieren ist dir zu umständlich?
Hier Hobbyprogrammierer belästigen und eine unzuverlässige Info ist ja 
viiiieeel wertvoller.

[Peter II (Gast)]

Route 6. schrieb:
> Ausprobieren ist dir zu umständlich?

lesen zu umständlich?

> Mit gcc scheint es zu funktionieren

[Noch einer (Gast)]

Hast du kontrolliert, ob "x /= 65536" eine aufwendige Division macht? 
Normalerweise kennt der GCC-Optimizer mehr Tricks, als bei einem 
Programmiere aus den Mathe Vorlesungen hängen geblieben ist.

[(prx) A. K. (prx)]

Mike schrieb:
> Doch ist garantiert, dass bei negativem x von links Einsen eingeschoben
> werden, so dass das Ergebnis negativ bleibt?

Nein. Offiziell nicht. Ich kenne aber keine Plattform, bei der es anders 
ist.

Allerdings ist das Ergebnis bei negativem Nenner auch bei 
reingeschobenem Vorzeichen verschieden, wenn der Rest der Division nicht 
0 ist.

[Leo C. (rapid)]

Division:

  mov  r3, #65536
  sdiv  r0, r0, r3

Shift:

  asrs  r0, r0, #16

gcc version 6.3.1

[(prx) A. K. (prx)]

A. K. schrieb:
> Allerdings ist das Ergebnis bei negativem Nenner auch bei
> reingeschobenem Vorzeichen verschieden, wenn der Rest der Division nicht
> 0 ist.

Allerdings ist das Ergebnis bei negativem Zähler auch bei
reingeschobenem Vorzeichen verschieden, wenn der Rest der Division nicht
0 ist.

[(prx) A. K. (prx)]

Leo C. schrieb:
> Division:
>

>   mov  r3, #65536
>   sdiv  r0, r0, r3
>

gcc 4.7.1, -O1, amd64:
        leal    65535(%rdi), %eax
        testl   %edi, %edi
        cmovns  %edi, %eax
        sarl    $16, %eax

[M. K. (sylaina)]

Mike schrieb:
> Allerdings ist die Division eine aufwändige Operation, da der ARM sie
> iterativ berechnen muss, denn es gibt keinen Maschinen-Divisionsbefehl.

Eigentlich sollte jeder halbwegs moderne Compiler eine 
Division/Multiplikation auf Basis einer Zweipotenz erkennen und in eine 
Schiebeoperation umwandeln.

[Detlev T. (detlevt)]

Ich habe es einmal kurz getestet. Selbst ohne Optimierung (-O0) macht 
der gcc aus (int32_t) /= 65536:

141b        asrs  r3, r3, #16

Also einen Shift-Befehl, der das Vorzeichen erhält.

[(prx) A. K. (prx)]

M. K. schrieb:
> Eigentlich sollte jeder halbwegs moderne Compiler eine
> Division/Multiplikation auf Basis einer Zweipotenz erkennen und in eine
> Schiebeoperation umwandeln.

Yep. Nur ist sdiv kürzer als die Ersatzsequenz.

Cortex M3, gcc 4.8.1, -Os:
        mov     r3, #65536
        sdiv    r0, r0, r3
und bei -O1:
        add     r3, r0, #65280
        adds    r3, r3, #255
        bics    r0, r0, r0, asr #32
        it      cs
        movcs   r0, r3
        asrs    r0, r0, #16

[(prx) A. K. (prx)]

Detlev T. schrieb:
> Ich habe es einmal kurz getestet. Selbst ohne Optimierung (-O0) macht
> der gcc aus (int32_t) /= 65536:
>

> 141b        asrs  r3, r3, #16
>

> Also einen Shift-Befehl, der das Vorzeichen erhält.

Gibt bei -3 / 2 ein falsches Ergebnis. Bissel mehr ist also nötig, siehe 
oben.

[Mike (Gast)]

Leo C. schrieb:
> Division:  mov  r3, #65536
>   sdiv  r0, r0, r3
>
> Shift:  asrs  r0, r0, #16
>
> gcc version 6.3.1

sdiv gibt es nicht beim Cortex M0+:
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0484b/CHDCICDF.html

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Detlev T. schrieb:
> Ich habe es einmal kurz getestet. Selbst ohne Optimierung (-O0) macht
> der gcc ... einen Shift-Befehl, der das Vorzeichen erhält.
Das ist prinzipiell falsch, weil in die falsche Richtung "gerundet" 
wird.
Siehe http://codepad.org/s9bcOmkk oder http://codepad.org/8NMZ194I

[(prx) A. K. (prx)]

Kurioserweise ist der gcc 6.3.1 Code für den Cortex M0
        asr     r3, r0, #31
        lsr     r3, r3, #16
        add     r0, r3, r0
        asr     r0, r0, #16
besser als der zeitoptimierte Code für den Cortex M3
        add     r3, r0, #65280
        adds    r3, r3, #255
        bics    r0, r0, r0, asr #32
        it      cs
        movcs   r0, r3
        asrs    r0, r0, #16
obwohl der M3 ein Superset des M0 ist.

[Mike (Gast)]

Ich habe es mal mit meinem Compiler für die unterschiedlichen 
Optimierungsstufen ausprobiert. Was das Hin-und Hergeschiebe bei -O(1) 
macht, überschaue ich im Moment nicht, da ich mich mit Cortex-Assembler 
nicht gut auskenne. Ab -O(2) wird immer arithmetisch geschoben.
Das Rundungsverhalten ist anscheinend nicht gleich. Arithmetisch ">>" 
rundet ja immer zur nächstkleineren Zahl. "/" scheint dagegen zur Null 
hinzurunden, wenn ich mich richtig erinnere. Der Compiler scheint sich 
wohl nicht darum zu scheren.



-O(0)

  x /= 65536;
 218:  687b        ldr  r3, [r7, #4]
 21a:  2b00        cmp  r3, #0
 21c:  da02        bge.n  224 <main+0x38>
 21e:  4a11        ldr  r2, [pc, #68]  ; (264 <main+0x78>)
 220:  4694        mov  ip, r2
 222:  4463        add  r3, ip
 224:  141b        asrs  r3, r3, #16
 226:  607b        str  r3, [r7, #4]
  y >>= 16;
 228:  683b        ldr  r3, [r7, #0]
 22a:  141b        asrs  r3, r3, #16
 22c:  603b        str  r3, [r7, #0]

-O(1)

  x /= 65536;
 202:  17eb        asrs  r3, r5, #31
 204:  041b        lsls  r3, r3, #16
 206:  0c1b        lsrs  r3, r3, #16
 208:  195b        adds  r3, r3, r5
 20a:  141b        asrs  r3, r3, #16
  PORT->Group[0].OUT.reg = x;
 20c:  6123        str  r3, [r4, #16]
  y >>= 16;
 20e:  1400        asrs  r0, r0, #16

-O(s), -O(2) und -O(3)

        y >>= 16;
 1e8:  1400        asrs  r0, r0, #16
  x /= 65536;
 1ea:  141b        asrs  r3, r3, #16

[(prx) A. K. (prx)]

Mike schrieb:
> Was das Hin-und Hergeschiebe bei -O(1)
> macht, überschaue ich im Moment nicht,

Der Compiler aber schon ...

> Der Compiler scheint sich wohl nicht darum zu scheren.

... weshalb diese Aussage etwas "mutig" ist. Denn das "Hin-und 
Hergeschiebe" dient eben dazu, die Rundung richtig durchzuführen.

Prinzip für x / (1<<N):
  if (x < 0)
     x += (1<<N)-1;
  x >>= N;
Genau das macht er in der nicht optimierten Version.

Die optimierte Version für den Cortex M0 erzeugt einen zu addierenden 
Wert 0 oder (1<<N)-1 auf recht clevere Art.

[Yalu X. (yalu) (Moderator)]

Man sollte sich in diesem Zusammenhang auch mal Gedanken darüber machen,
welche Rundung man bei Integer-Division überhaupt bevorzugt: zur 0 hin
(wie in C) oder Richtung -∞ (wie in Python). Die letztere ist für mich
die logischere und in den meisten Anwendungen auch die geeignetere.

Reguläre Integer-Divisionen mit negativen Operanden verwende ich
deswegen in C so gut wie nie. Für Skalierungszwecke wie bspw. bei der
Festkommaarithmetik (die ich aber nur selten vorzeichenbehaftet
benötige) verwende ich ausschließlich Shift-Operationen. Dass der
>>-Operator für negative linke Operanden implementation-defined ist,
stört mich dabei nicht so sehr, da diesbezüglich alle von mir bisher
eingesetzten Compiler dasselbe Verhalten zeigen.

Für die vorliegende Anwendung in einem digitalen Filter (die ich
allerdings nicht im Detail kenne) dürfte die Shift-Operation ebenfalls
die bessere Wahl sein.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Yalu X. schrieb:
> Man sollte sich in diesem Zusammenhang auch mal Gedanken darüber machen,
> welche Rundung man bei Integer-Division überhaupt bevorzugt: zur 0 hin
> (wie in C) oder Richtung -∞ (wie in Python). Die letztere ist für mich
> die logischere und in den meisten Anwendungen auch die geeignetere.
Wobei "Runden" im Fall hier der falsche Begriff ist: es geht eher um ein 
korrektes "Abschneiden". Es ist ein wenig verwirrend und überraschend, 
wenn das Ergebnis der "Division" 3/16 den Wert 0 ergibt, aber -3/16 den 
Wert -1

http://codepad.org/fHApZAda

[Yalu X. (yalu) (Moderator)]

Lothar M. schrieb:
> Es ist ein wenig verwirrend […]

für den Kaufmann: ja
für den Mathematiker: nein
für den Ingenieur oder Informatiker: kommt darauf an :)

Im Anhang habe ich mal die verschiedenen Divisionsmöglichkeiten im
Hinblick auf die vorliegende Aufgabenstellung, nämlich die Skalierung
von Signalen, vergleichend dargestellt.

In allen drei Fällen wird von einem Sinussignal mit der Amplitude 120
ausgegangen. Damit die Werte in eine 8-Bit- Variable passen, soll das
Signal um den Faktor 16 herunterskaliert werden. In den drei Diagrammen
ist das ohne Diskretisierung skalierte Signal jeweils in grüner Farbe
eingezeichnet.

Im ersten Beispiel wird dazu die gewöhnliche Integer-Division genommen.
An den Nulldurchgängen entstehen leichte Unregelmäßigkeiten ähnlich den
Übernahmeverzerrungen eines schlechten Gegentaktendstufe. Außerdem ist
die Amplitude um 0,5 LSB zu klein.

Im zweiten Beispiel wird die Division durch eine Shift-Operation
realisiert. Die Nulldurchgangsverzerrungen sind verschwunden und auch
die Amplitude stimmt. Allerdings hat das Signal jetzt einen Offset von
-0,5 LSB, der bei Filteranwendungen aber über einen Koppelkondensator am
Ausgang eliminiert wird und deswegen meist akzeptabel ist.

Man kann diesen Offset aber auch auf digitaler Seite korrigieren, wie
das dritte Beispiel zeigt. Dazu wird vor dem Shift einfach der halbe
Skalierungfaktor zum Signal addiert.