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

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

crc = crc ^ ~0U; 

вместо

 crc = ~crc; 

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

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

Не оптимизированная assembly:

  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 вероятно, имеет важное значение, поскольку я 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:

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

Оптимизированная assembly:

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

 // 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 

Что-то никто еще не упоминал; если этот код компилируется на машине с 16-битным unsigned int эти два fragmentа кода отличаются .

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

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

NB. Извините за публикацию этого как «ответ», потому что это не ответ, но он слишком велик, чтобы просто вставить комментарий 🙂

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

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

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

crc остаток = INITIAL_REMAINDER;

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

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

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

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

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

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

 const int zero = 0; 

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

 const int zero = 0x00000000; 

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