Зачем использовать 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
Ответы
Ответ 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;
Различные люди думают по-разному. Даже о фундаментальной операции.
