Как избежать представления ловушек при выполнении отмены битов XOR для подписанных целых?

Question

Как предложенное решение для данных трех чисел, найти второе из них, я написал:

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;
}

Идея в том, что ^ smallest ^ largest отменяет биты так, что остается среднее число.

Тем не менее, @chux указал на проблему:

Особая проблема с int а также a ^ b ^ c ^ smallest ^ largest является то, что промежуточный результат может быть представлением ловушки на редких, не являющихся дополнением, платформах. - Чукс

@ chux Пожалуйста, объясни? XOR просто работает по крупицам, и ему все равно, что представляют собой эти биты, верно? - 200 успехов

XOR не волнует, но результат может быть проблемой: например, с, скажем, целыми числами знака, -1 ^ 1 идет к -0 что может быть значением ловушки - остановка кода. см. C11 §6.2.6.2 2. Битовые операции лучше использовать на типах без знака. - Чукс

Далее C11 §6.2.6.2 3 определяет поведение, определенное реализацией для ^ с int на редких, не являющихся дополнением, платформах. В частности, "не определено, действительно ли в этих случаях генерируется отрицательный ноль или нормальный ноль", что делает ^ b ^ c ^ наименьшее ^ наибольшее неопределенным, что оно будет работать по желанию, даже если значение ловушки не используется. В следующем разделе объясняется, как это может быть UB. Лучше всего оставить этот новый код неподписанным типам. - Чукс

Кажется прискорбным, что техника, которая должна быть логически и математически обоснованной, может быть сорвана техническими средствами.

Есть ли способ спасти эту технику XOR и сделать ее юридически безопасной, в идеале с нулевыми затратами времени выполнения? (Может быть, что-то с профсоюзами?)

Answer 1

Есть ли способ спасти эту технику XOR и сделать ее юридически безопасной, в идеале с нулевыми затратами времени выполнения

Используйте встроенную сборку. Язык ассемблера не связан правилами C/C++.

Может быть, что-то вроде следующего.

$ 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;
}

r машинное ограничение выше означает регистр. g машинное ограничение, указанное выше, означает регистр, ячейку памяти или непосредственный адрес. Также см. Раздел 6.42.1 "Простые ограничения" руководства GCC.

А потом:

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

Ниже от objdump --disassemble test.o после компиляции в -O3, Похоже, накладные расходы сведены к минимуму. Похоже, байты 0x00-0x17 выполняют min а также max; и похоже, что xor выполняются в байтах 0x18-0x20.

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   

---

Недостатком встроенной сборки является то, что она доступна не везде. Код IA-32, аналогичный приведенному выше, будет работать для BSD, Linux, OS X, некоторых Solaris и некоторых Windows. Для удержаний, таких как pre-Solaris Studio 12 или Visual Studio x64, вам понадобится функция, которая находится в исходном файле сборки, собранном ассемблером и вызываемом из кода C / C++ (т. Е. *.S или же *.asm файл).

В Solaris Studio 12 добавлена ​​поддержка встроенной сборки GCC, поэтому для более ранних версий Sun Studio требуется ассемблер. Windows Win32 поддерживает встроенный ASM в синтаксисе Intel, но X64 требует от вас использования MASM, поскольку встроенная сборка отсутствует.