Во время передачи информации от одного устройства к другому могут возникать различные ошибки (помехи в радио-эфире, электромагнитные наводки в проводах), приводящие к повреждению данных. Достаточно повредить один бит, и число может сильно измениться! Например передавали число 123, которое выглядит как 0b01111011 и неправильно передали один бит. Приёмник получил число 0b01011011, что уже является числом 91! Если речь идёт о дистанционном управлении каким-то устройством, то даже один "битый" бит в посылке может привести к серьёзной аварии. Как приёмнику понять, что принятые данные повреждены?
Контрольная сумма #
Самый простой вариант - контрольная сумма (checksum). Перед отправкой данных передатчик суммирует все байты и отправляет их например последними в посылке. Благодаря такой особенности как переполнение переменной, даже в один байт можно бесконечно суммировать данные и получить в итоге конкретное число, олицетворяющее все передаваемые данные. Например, передаём набор байтов 201, 125, 47, 94, 10, 185. Их суммой будет число 662, если брать ячейку uint16_t, или 150, если это uint8_t. Осталось отправить контрольную сумму последним байтом (или двумя, если передаём uint16_t число)! Приёмник получает посылку, в свою очередь суммирует все байты кроме последнего (или двух последних, если контрольная сумма 16-битная), а затем сравнивает это значение с полученной контрольной суммой. Если отличается хоть на 1 - данные повреждены. Причём повреждёнными при передаче могут быть как сами данные, так и контрольная сумма: в любом случае они не совпадут, а это означает, что передача произошла с ошибкой.
Давайте рассмотрим пример "передачи и приёма" структуры. Структуру используем для удобства упаковки и использования данных. Универсальная для любого типа данных функция расчёта хэш-суммы может выглядеть так:
uint8_t getHash(const void* data, size_t length, uint8_t hash = 0) {
const uint8_t* p = (const uint8_t*)data;
while (length--) hash += *p++;
return hash;
}И возвращать байт суммы. Создадим и заполним структуру данными и прогоним через эту функцию. В последний байт структуры запишем контрольную сумму:
// структура данных посылки
struct MyData {
uint8_t channel;
int val_i;
float val_f;
uint8_t hash; // байт контрольной суммы
};
void setup() {
Serial.begin(115200);
// создаём и заполняем дату
MyData data;
data.channel = 16;
data.val_i = 12345;
data.val_f = 3.1415;
data.hash = 0;
// расчёт суммы
uint8_t thisHash = getHash(&data, sizeof(data));
// пакуем в посылку
data.hash = thisHash;
// выведем для отладки
Serial.println(thisHash); // выдаст 102
}
void loop() {
}Теперь можно передать структуру приёмнику! Пример "синтетический", так как кому и каким способом передавать данные мы не рассматриваем. Хотя, можно отправить по Serial, например с одной Ардуины на другую:
Serial.write((uint8_t*)&data, sizeof(data));Далее на приёмнике примем данные:
// структура данных посылки
struct MyData {
uint8_t channel;
int val_i;
float val_f;
uint8_t hash; // байт контрольной суммы
};
void setup() {
Serial.begin(9600);
}
void loop() {
MyData rxData;
if (Serial.readBytes((uint8_t*)&rxData, sizeof(rxData))) {
// приняли данные
}
}Теперь нужно убедиться в том, что данные верны. Для этого пропустим их через ту же суммирующую функцию, но без учёта последнего байта, так как он сам является суммой:
uint8_t thisHash = getHash(&rxData, sizeof(rxData) - 1);Если значение совпадёт с переданным rxData.hash - данные верны! Дополним предыдущий код:
void loop() {
if (Serial.readBytes((uint8_t*)&rxData, sizeof(rxData))) { // читаем дату
uint8_t thisHash = getHash(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++ без привязки к архитектуре:
uint8_t crc8(const void* data, size_t length, uint8_t crc = 0) {
const uint8_t* p = (const uint8_t*)data;
while (length--) {
uint8_t b = *p++, j = 8;
while (j--) {
crc = ((crc ^ b) & 1) ? (crc >> 1) ^ 0x8C : (crc >> 1);
b >>= 1;
}
}
return crc;
}Данная функция применяется точно так же, как предыдущая getHash(), просто "скармливаем" ей данные в байтовом представлении и всё! Но есть пара моментов:
- При расчёте CRC перед отправкой нужно исключить байт самого CRC (последний), даже если он нулевой. То есть в примерах выше:
byte thisHash = crc8(&data, sizeof(data) - 1); - При расчёте CRC на стороне приёмника можно пропустить все данные полностью - вместе с байтом CRC. В этом случае функция вернёт
0, если данные верны! Это очень удобно использовать
Финальный пример. Передатчик:
// структура данных посылки
struct MyData {
uint8_t channel;
int val_i;
float val_f;
uint8_t crc; // байт crc
};
void setup() {
Serial.begin(9600);
// создаём и заполняем дату
MyData data;
data.channel = 16;
data.val_i = 12345;
data.val_f = 3.1415;
// расчёт CRC (без последнего байта)
uint8_t crc = crc8(&data, sizeof(data) - 1);
// пакуем в посылку
data.crc = crc;
}
void loop() {
// отправляем
Serial.write((uint8_t*)&data, sizeof(data));
delay(1000);
}Приёмник:
// структура данных посылки
struct MyData {
uint8_t channel;
int val_i;
float val_f;
uint8_t crc; // байт crc
};
MyData rxData;
void setup() {
Serial.begin(9600);
}
void loop() {
if (Serial.readBytes((uint8_t*)&rxData, sizeof(rxData))) { // читаем дату
uint8_t crc = crc8(&rxData, sizeof(rxData)); // считаем crc посылки полностью
if (crc == 0) {
// данные верны
} else {
// данные повреждены
}
}
}Также коллега поделился реализацией данного алгоритма на ассемблере для AVR, она работает чуть быстрее и весит чуть легче, что может быть критично например для ATtiny:
uint8_t crc8_asm(const void* data, size_t length, uint8_t crc = 0) {
const uint8_t* p = (const uint8_t*)data;
while (length--) {
uint8_t data = *p++;
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;
}Функция используется точно так же, как предыдущая.
CRC32 #
Для повышения надёжности можно использовать не 8, а 32 бит CRC, например при помощи вот такой функции:
uint32_t crc32(const void* data, size_t length, uint32_t crc = 0) {
const uint8_t* p = (const uint8_t*)data;
crc = ~crc;
while (length--) {
crc ^= *p++;
uint8_t i = 8;
while (i--) crc = (crc & 1) ? ((crc >> 1) ^ 0x4C11DB7) : (crc >> 1);
}
return ~crc;
}