Я много раз пытался написать свою собственную реализацию CRC32 в соответствии с теорией, но так и не получил ожидаемых результатов.
Сегодня я сделал еще одну попытку, имея в виду не только теорию, но и реализацию Boosts. Хотя я наконец-то заставил его работать правильно, я не понимаю, почему это работает так.
Я понимаю, почему boost меняет байт и результат меняет, я знаю, почему его начальный остаток равен 0xffffffff, а результат должен быть обработан XOR с 0xffffffff. Это стандарт. Но когда доходит до функции ProcessBit, я застреваю.
В ответе на Как рассчитывается контрольная сумма CRC32? я нашел полную пример. Я думаю, что реализация ProcessBit выглядит так:
void CRC32::ProcessBit(bool b)
{
/*
x xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxb : x curVal, b coming bit
1 yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy : y polynomial
*/
if (_remainder & 0x80000000) {
_remainder <<= 1;
_remainder |= b;
_remainder ^= polynomial;
} else {
_remainder <<= 1;
_remainder |= b;
}
}
так как первый бит полинома равен 1, если остаток начинается с бита 1, я выполню операцию XOR. Но эта реализация дает неверный результат. Я проследил код в Boost, чтобы увидеть, как он работает, и написал свой собственный:
void CRC32::ProcessBit(bool b)
{
bool high = (_remainder & 0x80000000) ? true : false;
_remainder <<= 1;
if (high != b) {
_remainder ^= polynomial;
}
}
Эта реализация работает хорошо. но я не понимаю почему. Что меня смущает, так это то, что условие для определения того, следует ли выполнить операцию XOR с полиномом для остатка, является:
«первый бит остатка равен следующему биту».
Тогда как в «полном примере» используется другое условие, а именно:
«первый бит остатка равен 1».
Другой вопрос; почему следующий бит не будет добавлен в конец остатка в реализации Boost.
Изменить: я решил проблему. Причина, по которой он дал неправильный результат, заключается в том, что я неправильно понимаю значение «начального значения».
