XOR и CRC8 руками: суммы, которые не обманешь

Разбор утреннего лога начался с неприятного: две ночные посылки на линию возле контактора прошли проверку и дёрнули насос, хотя я слал команду на остановку. Проверка стояла — XOR-сумма, одна строка кода, и на столе в кабинете она не пропускала ни разу за месяц. В журнале видно, что у обеих посылок побит груз, но сумма сошлась. После этого я пересчитал её руками на бумажке и нашёл то, о чём слышал, но в что не верил: биты переворачиваются парами, и если пара легла в один разряд двух разных байтов, XOR этого не заметит. Разберём обе суммы до дна: как XOR считается по байтам, где его слепое пятно и почему восемь сдвигов CRC8 закрывают дыру.

Фрейм с маркером и длиной уже собран в уроке про контрольную сумму — там же таблица, где простая сумма, XOR и CRC8 стоят по строке каждая. Здесь копаем в сами суммы, а не в рамку вокруг них. XOR — то, чем проверяет целостность GPS-приёмник: каждое предложение NMEA заканчивается звёздочкой и двумя hex-цифрами, за которыми стоит XOR всех символов строки, механика показана в уроке про NMEA. CRC8 — то, чем датчик DS18B20 запечатывает свои девять байтов на шине. Обе суммы считаются руками, без библиотек, и после этого урока вы сможете проверить DS18B20 сами.

XOR складывает байты поразрядно, без переносов: 0x0F и 0x64 дают 0x6B, потому что в каждом разряде единица встретилась ровно у одного из байтов. Пакет из 0x0F и 0x64 уезжает с прицепом 0x6B; приёмник складывает то, что доехало, и сверяет прицеп с расчётом. Вся арифметика — оператор ^ в цикле, на Uno это один-два такта на байт. Для сравнения: сумма по модулю 256 у того же пакета — 0x73, другое число, потому что при сложении бегут переносы. Суммы живут парой не случайно: ловят разное, а стоят вместе четыре строки — про их пересечение чуть ниже, там самое интересное.

Перевёрнутый бит в любом байте переворачивает ровно один бит суммы. Инвертировали бит 0 в грузе: 0x64 стало 0x65, и XOR посылки сдвинулся с 0x6B на 0x6A — промах виден сразу. Отсюда сила XOR: нечётное число инверсий в любой позиции не проходит никогда, сколько бы их ни было. GPS-приёмник шлёт строки по короткому проводу, где чаще всего портится один бит, и этой силы ему хватает на все десятилетия. Побитовая кухня — сдвиги, маски, инверсии — та же, что в уроке про битовые операции, только здесь она работает на целостность посылки.

Слепое пятно — пара инверсий в одном разряде двух разных байтов. Берём пакет 0x0F 0x64 и портим бит 0 в обоих: первый станет 0x0E, второй 0x65. XOR: 0x0E ^ 0x65 = 0x6B — тот же, что у чистого пакета. Сумма по модулю тоже молчит: 14 + 101 = 115, как и было, потому что один байт полегчал на единицу, второй потяжелел на единицу. Обе простые суммы пропускают битую посылку вместе. И это не выдумка для урока: помеха возле катушки реле бьёт пачкой, а пачка кладёт инверсии в один и тот же разряд соседних байтов. Мой вывод после той ночи: XOR — фильтр первый, но не последний.

Обе простые суммы считаются на бумажке за минуту, и я советую сделать это руками хотя бы раз: столбик байтов, XOR по колонкам снизу вверх, рядом — сумма с переносами. После третьего пакета в голове заводится шестнадцатеричная привычка, а гекс-столбики из урока про BIN, HEX и DEC начинают читаться по диагонали. Больше это не понадобится — дальше считает микроконтроллер, — но доверие к цифрам появляется только через руки.

Функция crc8 — весь CRC8 целиком, без таблицы. На каждый байт груза внутренний цикл крутится восемь раз: сдвиг вправо, младший бит от пары «crc и байт» решает, замешивать ли после сдвига константу 0x8C. Это отражённая запись полинома 0x31 из аппноута Dallas — тот же полином, по которому DS18B20 считает свой последний байт скретчпада, и тот же расчёт, что сидит внутри библиотеки OneWire. На Uno восемь итераций — единицы микросекунд на байт при 16 МГц; при 9600 бод байт едет по проводу около миллисекунды, так что охранник успевает с запасом на два порядка. Табличная версия на 256 байтов флеша ускоряет счёт втрое-вчетверо, но имеет смысл только на пакетах в сотни байтов.

Вердикт приёмника я печатаю с эхом всех трёх охранников — та же дисциплина, что в уроке про эхо-протокол: по одной строке BRAK видно, какой именно сторож не сошёлся, и не нужен ни второй анализатор, ни вторая плата. Хекс-печать с ведущим нулём здесь не украшение, а необходимость: байт 0x05 без нуля в потоке байтов глазами теряется. Отброшенную посылку никто не чинит и не пересчитывает — ведущий повторит, это дешевле, чем разбирать полуцелую.

Механика CRC8 стоит того, чтобы проговорить словами. Один сдвиг вправо протаскивает младший бит crc наружу, а верх — с нулём; замес полиномом возвращает в crc единицы там, где полином имеет единицы. После восьми сдвигов каждый бит исходного байта успел повлиять на цепочку битов crc через повторяющиеся замесы. Поэтому одиночная инверсия в грузе ловится гарантированно, парные — практически все на полиноме 0x31, и даже перестановка байтов местами ломает результат: у CRC порядок байтов входит в арифметику, в отличие от обеих простых сумм, которые по определению коммутативны.

Граница применимости у меня простая и проверенная на граблях. Пульт по квартире, посылка в два-четыре байта, провод полметра — хватает XOR, его дыры там не выстреливают, а код весит одну строку. Линия возле реле и контакторов, радиомодуль, телеметрия, которую терять жалко, — CRC8 на сдвигах, тем более что он же проверяет ваши DS18B20 по дороге. Пакеты длиннее пары десятков байтов — смотрите в сторону CRC16, как в Modbus: там груз тянется на десятки байтов, и восьмибитный хвост уже не покрывает всё — урок про Modbus RTU показывает CRC16 в живом запросе.

За кадром таблицы стоит одна честная оговорка: ни одна сумма не видит потерю посылки целиком — считать нечего, сравнивать не с чем. Против тишины работает только таймаут: ведущий шлёт запрос, ждёт ответ секунду, не дождался — повторяет. У меня в гирлянде повтор был бесплатным: команда через две секунды доезжала второй раз, и никто не замечал сбоя. Это ещё один аргумент держать посылки короткими: чем короче кадр, тем дешевле повтор и тем чаще проверка успевает за потоком.