Зачем использовать 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 циклу. На самом деле, исключающее может иметь штраф за загрузку литерала откуда-то, хотя я не уверен в этом.

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

Изменить 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

11

Решение

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

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

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

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

10

Другие решения

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

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

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

crc остаток = INITIAL_REMAINDER;

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

возврат (остаток ^ FINAL_XOR_VALUE);

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

6

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

1

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

0

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

const int zero = 0;

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

const int zero = 0x00000000;

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

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector