Wie können Trap-Repräsentationen vermieden werden, wenn XOR-Bit-Cancellation für signierte Ints ausgeführt wird?

Question

Wie als vorgeschlagene Lösung für Given three numbers, find the second greatest of them, schrieb ich:

int second_largest(int a, int b, int c) { 
    int smallest = min(min(a, b), c); 
    int largest = max(max(a, b), c); 

    /* Toss all three numbers into a bag, then exclude the 
     minimum and the maximum */ 
    return a^b^c^smallest^largest; 
} 

Die Idee ist, dass ^ smallest^largest die Bits aufhebt, so dass die mittlere Zahl bleibt.

Allerdings wies @chux ein Problem aus:

Ein Problem mit singulären int und a^b^c^smallest^largest ist, dass ein Zwischenergebnis eine Falle Darstellung auf seltene Komplement Plattformen non-2 sein kann. - chux

@chux Bitte erläutern? XOR arbeitet nur Stück für Stück, und es ist mir egal, was die Bits darstellen, richtig? - 200_success

XOR kümmert es nicht, aber das Ergebnis kann ein Problem sein: z.B. mit sagen Vorzeichen-Magnitude Ganzzahlen, -1^1 geht zu -0 was vielleicht ein Trap-Wert - Stoppen des Codes. siehe C11 §6.2.6.2 2. Bit-weise Ops sind besser für unsigned Typen. - chux

Weitere C11 §6.2.6.2 3 spezifiziert implementierungsdefiniertes Verhalten für^mit int auf seltenen Nicht-2's Komplement-Plattformen. Insbesondere "Es ist nicht spezifiziert, ob diese Fälle tatsächlich eine negative Null oder eine normale Null erzeugen", wodurch ein möglichst kleiner Wert erreicht wird, der so funktioniert, wie es gewünscht wird, selbst wenn ein Trap-Wert nicht verwendet wird. Der nächste Abschnitt erklärt, wie dies UB sein kann. Am besten lassen Sie diesen neuen Code auf vorzeichenlose Typen zurück. - chux

Es scheint bedauerlich, dass eine Technik, die logisch und mathematisch klingen sollte, durch eine Technizität entgleisen könnte.

Gibt es eine Möglichkeit, diese XOR-Technik zu retten und sie rechtssicher zu machen, idealerweise mit null Laufzeitaufwand? (Etwas Gewerkschaften beteiligt, vielleicht?)

Answer 1

Gibt es eine Möglichkeit, diese XOR-Technik zu retten und es rechtlich sicher zu machen, idealerweise mit Null-Laufzeit-Overhead

Verwendung Inline-Montag. Die Assemblersprache ist nicht an die Regeln von C/C++ gebunden.

Vielleicht etwas wie folgt.

$ cat test.c 
#include <stdio.h> 
#include <stdlib.h> 

#define min(x, y) ((x) < (y) ? (x) : (y)) 
#define max(x, y) ((x) > (y) ? (x) : (y)) 

int second_largest(int a, int b, int c) 
{ 
    int s = min(min(a, b), c); 
    int l = max(max(a, b), c); 

    int result; 
    __asm volatile (
    "mov %1, %0 \n\t" 
    "xor %2, %0 \n\t" 
    "xor %3, %0 \n\t" 
    "xor %4, %0 \n\t" 
    "xor %5, %0 \n\t" 
     : "=r"(result) 
     : "g"(a), "g"(b), "g"(c), "g"(s), "g"(l) 
    ); 

    return result; 
} 

int main(int argc, char* argv[]) 
{ 
    int n = second_largest(10,20,30); 
    printf("Result: %d\n", n); 

    return 0; 
} 

Die r Maschine constraint bedeutet vor ein Register. Die obige Maschineneinschränkung bedeutet ein Register, einen Speicherort oder einen Sofortspeicher. Siehe auch Section 6.42.1 Simple Constraints des GCC-Handbuchs.

Und dann:

$ gcc -Wall -Wstrict-overflow=5 test.c -o test.exe 
$ ./test.exe 
Result: 20 

Unten finden von objdump --disassemble test.o nach bei -O3 kompilieren. Es sieht so aus, als ob der Aufwand auf ein Minimum reduziert wird. Es sieht aus wie Bytes 0x00-0x17 führen die min und max; und es sieht so aus, als ob die xor bei Bytes 0x18-0x20 ausgeführt werden.

0000000000000000 <second_largest>: 
    0: 39 d7     cmp %edx,%edi 
    2: 89 d0     mov %edx,%eax 
    4: 89 d1     mov %edx,%ecx 
    6: 0f 4e c7    cmovle %edi,%eax 
    9: 39 f0     cmp %esi,%eax 
    b: 0f 4f c6    cmovg %esi,%eax 
    e: 39 d7     cmp %edx,%edi 
    10: 0f 4d cf    cmovge %edi,%ecx 
    13: 39 f1     cmp %esi,%ecx 
    15: 0f 4c ce    cmovl %esi,%ecx 
    18: 89 f8     mov %edi,%eax 
    1a: 31 f0     xor %esi,%eax 
    1c: 31 d0     xor %edx,%eax 
    1e: 31 c0     xor %eax,%eax 
    20: 31 c8     xor %ecx,%eax 
    22: c3      retq 

---

Der Nachteil Montage Inline ist es nicht überall verfügbar. IA-32 Code ähnlich wie oben funktioniert für BSDs, Linux, OS X, einige Solaris und einige Windows. Für Hold-Outs, wie vor Solaris Studio 12 oder Visual Studio x64, benötigen Sie eine Funktion in einer Assembly-Quelldatei, die vom Assembler zusammengestellt und aus C/C++ - Code aufgerufen wird (d. H. Eine *.S oder *.asm Datei).

Solaris Studio 12 added support for GCC inline assembly, daher erfordern frühere Versionen von Sun Studio den Assembler. Windows Win32 unterstützt Inline-ASM in Intel-Syntax, aber X64 erfordert, dass Sie MASM verwenden, da keine Inline-Assembly vorhanden ist.