Подтвердить что ты не робот

Зачем использовать xor с литералом вместо инверсии (побитовое)

Я встретил этот код CRC32 и было любопытно, почему автор решил использовать

crc = crc ^ ~0U;

вместо

crc = ~crc;

Насколько я могу судить, они эквивалентны.

Я даже разобрал две версии в Visual Studio 2010.

Не оптимизированная сборка:

    crc = crc ^ ~0U;
009D13F4  mov         eax,dword ptr [crc]  
009D13F7  xor         eax,0FFFFFFFFh  
009D13FA  mov         dword ptr [crc],eax 

    crc = ~crc;
011C13F4  mov         eax,dword ptr [crc]  
011C13F7  not         eax  
011C13F9  mov         dword ptr [crc],eax

Я также не могу оправдывать код, думая о количестве циклов, которое берет каждая инструкция, поскольку оба должны выполнить 1 цикл для завершения. Фактически, у xor может быть штраф за то, что нужно загрузить литерал откуда-то, хотя я не уверен в этом.

Итак, я остаюсь думать, что это возможно просто предпочтительный способ описать алгоритм, а не оптимизацию... Правильно ли это?

Изменить 1:

Так как я только понял, что тип переменной crc, вероятно, важно упомянуть, что я включаю весь код (за исключением таблицы поиска, слишком большой), поэтому вам не нужно следовать ссылке.

uint32_t crc32(uint32_t crc, const void *buf, size_t size)
{
    const uint8_t *p;

    p = buf;
    crc = crc ^ ~0U;

    while (size--)
    {
        crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
    }

    return crc ^ ~0U;
}

Изменить 2:

Поскольку кто-то поднял тот факт, что оптимизированная сборка будет интересна, я сделал ее и включил ее ниже.

Оптимизированная сборка:

Обратите внимание, что вся функция (включенная в последнее изменение ниже) была встроена.

// crc = crc ^ ~0U;
    zeroCrc = 0;
    zeroCrc = crc32(zeroCrc, zeroBufferSmall, sizeof(zeroBufferSmall));
00971148  mov         ecx,14h  
0097114D  lea         edx,[ebp-40h]  
00971150  or          eax,0FFFFFFFFh  
00971153  movzx       esi,byte ptr [edx]  
00971156  xor         esi,eax  
00971158  and         esi,0FFh  
0097115E  shr         eax,8  
00971161  xor         eax,dword ptr ___defaultmatherr+4 (973018h)[esi*4]  
00971168  add         edx,ebx  
0097116A  sub         ecx,ebx  
0097116C  jne         main+153h (971153h)  
0097116E  not         eax  
00971170  mov         ebx,eax  

// crc = ~crc;
    zeroCrc = 0;
    zeroCrc = crc32(zeroCrc, zeroBufferSmall, sizeof(zeroBufferSmall));
01251148  mov         ecx,14h  
0125114D  lea         edx,[ebp-40h]  
01251150  or          eax,0FFFFFFFFh  
01251153  movzx       esi,byte ptr [edx]  
01251156  xor         esi,eax  
01251158  and         esi,0FFh  
0125115E  shr         eax,8  
01251161  xor         eax,dword ptr ___defaultmatherr+4 (1253018h)[esi*4]  
01251168  add         edx,ebx  
0125116A  sub         ecx,ebx  
0125116C  jne         main+153h (1251153h)  
0125116E  not         eax  
01251170  mov         ebx,eax
4b9b3361

ОТВЕТЫ

Ответ 1

Что-то еще не упоминалось; если этот код компилируется на машине с 16-битным unsigned int, то эти два фрагмента кода разные.

crc указывается как 32-разрядный неподписанный интегральный тип. ~crc будет инвертировать все биты, но если unsigned int - 16 бит, то crc = crc ^ ~0U будет инвертировать только младшие 16 бит.

Я не знаю достаточно о CRC-алгоритме, чтобы узнать, является ли это преднамеренным или ошибка, возможно, hivert может уточнить; хотя, глядя на образец кода, отправленный OP, он, безусловно, имеет значение для следующего цикла.

NB. Извините, что разместил это как "ответ", потому что это не ответ, но он слишком велик, чтобы просто вставить комментарий:)

Ответ 2

Короткий ответ: поскольку он позволяет иметь единый алгоритм для всех CRC

Причина заключается в следующем: существует много вариантов CRC. Каждый из них зависит от полинома Z/Z2, который используется для евклидова деления. Обычно он реализуется с использованием описанного алгоритма В этой статье Арам Перес. Теперь, в зависимости от используемого вами многочлена, в конце алгоритма есть конечный XOR, который зависит от полинома, целью которого является устранение некоторого углового случая. Случается, что для CRC32 это то же самое, что и глобальное, но это не относится ко всем CRC. В качестве доказательства на Эта веб-страница вы можете прочитать (внимание мое):

Рассмотрим сообщение, которое начинается с некоторого количества нулевых битов. Остальная часть никогда не будет содержать ничего, кроме нуля, до тех пор, пока первая в сообщении не будет смещена в нее. Это опасная ситуация, так как пакеты, начинающиеся с одного или нескольких нулей, могут быть полностью законными, а исключенный или добавленный ноль не будет замечен CRC. (В некоторых приложениях даже пакет всех нулей может быть законным!). Простой способ устранить эту слабость - начать с ненулевого остатка. Параметр, называемый начальным остатком, указывает вам, какое значение использовать для конкретного стандарта CRC. И только одно небольшое изменение требуется для функций crcSlow() и crcFast():

crc остаток = INITIAL_REMAINDER;

Конечное значение XOR существует по той же причине. Чтобы реализовать эту возможность, просто измените значение, возвращаемое crcSlow() и crcFast() следующим образом:

return (остаток ^ FINAL_XOR_VALUE);

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

Ответ 3

Чтобы добавить свое собственное предположение в микс, x ^ 0x0001 хранит последний бит и отбрасывает остальные; для отключения последнего использования бит x & 0xFFFE или x & ~0x0001; для включения последнего бит безоговорочно используйте x | 0x0001. I.e., если вы делаете много бит-twiddling, ваши пальцы, вероятно, знают эти идиомы и просто выкалывают их без особого размышления.

Ответ 4

Я сомневаюсь, что есть какая-то серьезная причина. Возможно, это то, как автор думал об этом ( "Я просто xor со всеми" ), или, возможно, как это было выражено в определении алгоритма.

Ответ 5

Я думаю, что по той же причине некоторые пишут

const int zero = 0;

и другие пишут

const int zero = 0x00000000;

Различные люди думают по-разному. Даже о фундаментальной операции.