Целостность данных, CRC
Во время передачи информации от одного устройства к другому могут возникать различные ошибки (помехи в радио-эфире, электромагнитные наводки в проводах), приводящие к повреждению данных. Достаточно повредить один бит, и число может сильно измениться! Например передавали число 123, которое выглядит как 0b01111011, и неправильно передали один бит. Приёмник получил число 0b01011011, что уже является числом 91! Если речь идёт о дистанционном управлении каким-то устройством, то даже один “битый” бит в посылке может привести к серьёзной аварии. Как приёмнику понять, что принятые данные повреждены?
Контрольная сумма
Самый простой вариант – контрольная сумма. Перед отправкой данных передатчик суммирует все байты и отправляет их например последними в посылке. Благодаря такой штуке как переполнение переменной, даже в один байт можно бесконечно суммировать данные и получить в итоге конкретное число, олицетворяющее все передаваемые данные. Например, передаём набор байтов 201, 125, 47, 94, 10, 185. Их суммой будет число 662, если брать ячейку int, или 150, если это byte. Осталось отправить контрольную сумму последним байтом (или двумя, если передаём int число)! Приёмник получает посылку, в свою очередь суммирует все байты кроме последнего (или двух последних, если контрольная сумма 16-битная), а затем сравнивает это значение с полученной контрольной суммой. Если отличается хоть на 1 – данные повреждены. Причём повреждёнными при передаче могут быть как сами данные, так и контрольная сумма: в любом случае они не совпадут, а это означает, что передача произошла с ошибкой. Давайте рассмотрим пример “передачи и приёма” структуры, где будет использоваться конструкция, позволяющая разбивать любые данные на байтовый поток. Три таких конструкции мы рассмотрели в уроке про указатели и ссылки. Структуру используем для удобства упаковки и использования данных. Универсальная для любого типа данных функция расчёта хеш-суммы может выглядеть так:
byte getHash(byte* data, int length) {
byte hash = 0;
int i = 0;
while (length--) {
hash += *(data + i);
i++;
}
return hash;
}
И возвращать байт суммы. Создадим и заполним структуру данными и прогоним через эту функцию. В последний байт структуры запишем контрольную сумму:
// структура данных посылки
struct MyData {
byte channel;
int val_i;
float val_f;
byte hash; // байт контрольной суммы
};
void setup() {
Serial.begin(9600);
// создаём и заполняем дату
MyData data;
data.channel = 16;
data.val_i = 12345;
data.val_f = 3.1415;
data.hash = 0;
// расчёт суммы
byte thisHash = getHash((byte*)&data, sizeof(data));
// пакуем в посылку
data.hash = thisHash;
// выведем для отладки
Serial.println(thisHash); // выдаст 102
}
Теперь можно передать структуру приёмнику! Пример “синтетический”, так как кому и каким способом передавать данные мы не рассматриваем. Хотя, можно отправить по Serial, например с одной Ардуины на другую, как в уроке по парсингу Serial:
Serial.write((byte*)&data, sizeof(data));
Далее на приёмнике примем данные:
// структура данных посылки
struct MyData {
byte channel;
int val_i;
float val_f;
byte hash; // байт контрольной суммы
};
MyData rxData;
void setup() {
Serial.begin(9600);
}
void loop() {
if (Serial.readBytes((byte*)&rxData, sizeof(rxData))) {
// приняли данные
}
}
Теперь нужно убедиться в том, что данные верны. Для этого прогоним их через ту же суммирующую функцию, но без учёта последнего байта, так как он сам является суммой:
byte thisHash = getHash((byte*)&rxData, sizeof(rxData) - 1);
Если значение совпадёт с переданным rxData.hash – данные верны! Дополним предыдущий код:
void loop() {
if (Serial.readBytes((byte*)&rxData, sizeof(rxData))) { // читаем дату
byte thisHash = getHash((byte*)&rxData, sizeof(rxData) - 1); // считаем сумму
if (thisHash == rxData.hash) {
// данные верны
} else {
// данные повреждены
}
}
}
И по условию можем выполнять какие-то действия, например применить полученные данные к устройству или проигнорировать их. Достоинства контрольной суммы:
- Быстрое и простое вычисление на любой платформе
- Возможность сделать 8 и 16 бит без особых вмешательств в код (это ваше домашнее задание)
Недостатки контрольной суммы:
- Низкая надёжность по сравнению с другими алгоритмами
Низкая надёжность заключается в том, что контрольная сумма не учитывает порядок байтов в посылке, то есть не является уникальным “отпечатком” всех данных. Например, данные повредились так, что из вот такого пакета
data.channel = 16; data.val_i = 12345; data.val_f = 3.1415;
Превратились в такой:
data.channel = 15; data.val_i = 12346; data.val_f = 3.1415;
Но контрольная сумма всё равно будет 102! Также контрольная сумма фактически игнорирует нули, то есть любой набор данных со всеми нулями и условно одной единичкой будет обрабатываться одинаково (например 0, 0, 0, 1, 0, 0 и 0, 1, 0, 0, 0, 0), что также снижает надёжность. Поэтому рассмотрим более хитрый алгоритм, который называется CRC.
CRC
CRC (cyclic redundancy code) – циклический избыточный код. Алгоритм тоже выдаёт некое “число” при прохождении через него потока байтов, но учитывает все предыдущие данные при расчёте. Как работает данный алгоритм мы рассматривать не будем, об этом можно почитать на Википедии или здесь. Рассмотрим реализацию CRC 8 бит по стандарту Dallas, он используется в датчиках этой фирмы (например DS18b20 и домофонные ключи iButton). Данная реализация должна работать на всех платформах, так как это чисто C++ без привязки к архитектуре (компилятор сам разберётся):
byte crc8(byte *buffer, byte size) {
byte crc = 0;
for (byte i = 0; i < size; i++) {
byte data = buffer[i];
for (int j = 8; j > 0; j--) {
crc = ((crc ^ data) & 1) ? (crc >> 1) ^ 0x8C : (crc >> 1);
data >>= 1;
}
}
return crc;
}
Данная функция применяется точно так же, как предыдущая getHash(), просто “скармливаем” ей данные в байтовом представлении и всё! Но есть пара моментов:
- При расчёте CRC перед отправкой нужно исключить байт самого CRC (последний), даже если он нулевой. То есть в примерах выше:
byte thisHash = crc8((byte*)&data, sizeof(data) - 1); - При расчёте CRC на стороне приёмника можно прогнать все данные полностью, вместе с байтом CRC. В этом случае функция вернёт
0, если данные верны! Это очень удобно использовать.
Финальный пример. Передатчик:
// структура данных посылки
struct MyData {
byte channel;
int val_i;
float val_f;
byte crc; // байт crc
};
void setup() {
Serial.begin(9600);
// создаём и заполняем дату
MyData data;
data.channel = 16;
data.val_i = 12345;
data.val_f = 3.1415;
// расчёт CRC (без последнего байта)
byte crc = crc8((byte*)&data, sizeof(data) - 1);
// пакуем в посылку
data.crc = crc;
}
void loop() {
// отправляем
Serial.write((byte*)&data, sizeof(data));
delay(1000);
}
byte crc8(byte *buffer, byte size) {
byte crc = 0;
for (byte i = 0; i < size; i++) {
byte data = buffer[i];
for (int j = 8; j > 0; j--) {
crc = ((crc ^ data) & 1) ? (crc >> 1) ^ 0x8C : (crc >> 1);
data >>= 1;
}
}
return crc;
}
Приёмник:
// структура данных посылки
struct MyData {
byte channel;
int val_i;
float val_f;
byte crc; // байт crc
};
MyData rxData;
void setup() {
Serial.begin(9600);
}
void loop() {
if (Serial.readBytes((byte*)&rxData, sizeof(rxData))) { // читаем дату
byte crc = crc8((byte*)&rxData, sizeof(rxData)); // считаем crc посылки полностью
if (crc == 0) {
// данные верны
} else {
// данные повреждены
}
}
}
byte crc8(byte *buffer, byte size) {
byte crc = 0;
for (byte i = 0; i < size; i++) {
byte data = buffer[i];
for (int j = 8; j > 0; j--) {
crc = ((crc ^ data) & 1) ? (crc >> 1) ^ 0x8C : (crc >> 1);
data >>= 1;
}
}
return crc;
}
Также коллега поделился реализацией данного алгоритма на ассемблере для AVR, она работает чуть быстрее и весит чуть легче, что может быть критично например для ATtiny:
byte crc8_asm(byte *buffer, byte size) {
byte crc = 0;
for (byte i = 0; i < size; i++) {
byte data = buffer[i];
// резкий алгоритм для AVR
uint8_t counter;
uint8_t buffer;
asm volatile (
"EOR %[crc_out], %[data_in] \n\t"
"LDI %[counter], 8 \n\t"
"LDI %[buffer], 0x8C \n\t"
"_loop_start_%=: \n\t"
"LSR %[crc_out] \n\t"
"BRCC _loop_end_%= \n\t"
"EOR %[crc_out], %[buffer] \n\t"
"_loop_end_%=: \n\t"
"DEC %[counter] \n\t"
"BRNE _loop_start_%="
: [crc_out]"=r" (crc), [counter]"=d" (counter), [buffer]"=d" (buffer)
: [crc_in]"0" (crc), [data_in]"r" (data)
);
}
return crc;
}
Функция используется точно так же, как предыдущая.
Полезные страницы
- Набор GyverKIT – большой стартовый набор Arduino моей разработки, продаётся в России
- Каталог ссылок на дешёвые Ардуины, датчики, модули и прочие железки с AliExpress у проверенных продавцов
- Подборка библиотек для Arduino, самых интересных и полезных, официальных и не очень
- Полная документация по языку Ардуино, все встроенные функции и макросы, все доступные типы данных
- Сборник полезных алгоритмов для написания скетчей: структура кода, таймеры, фильтры, парсинг данных
- Видео уроки по программированию Arduino с канала “Заметки Ардуинщика” – одни из самых подробных в рунете
- Поддержать автора за работу над уроками
- Обратная связь – сообщить об ошибке в уроке или предложить дополнение по тексту ([email protected])