Контрольная сумма, CRC

Во время передачи информации от одного устройства к другому могут возникать различные ошибки (помехи в радио-эфире, электромагнитные наводки в проводах), приводящие к повреждению данных. Достаточно повредить один бит, и число может сильно измениться! Например передавали число 123, которое выглядит как 0b01111011 и неправильно передали один бит. Приёмник получил число 0b01011011, что уже является числом 91! Если речь идёт о дистанционном управлении каким-то устройством, то даже один "битый" бит в посылке может привести к серьёзной аварии. Как приёмнику понять, что принятые данные повреждены?

Контрольная сумма #

Самый простой вариант - контрольная сумма (checksum). Перед отправкой данных передатчик суммирует все байты и отправляет их например последними в посылке. Благодаря такой штуке как переполнение переменной, даже в один байт можно бесконечно суммировать данные и получить в итоге конкретное число, олицетворяющее все передаваемые данные. Например, передаём набор байтов 201, 125, 47, 94, 10, 185. Их суммой будет число 662, если брать ячейку uint16_t, или 150, если это uint8_t. Осталось отправить контрольную сумму последним байтом (или двумя, если передаём uint16_t число)! Приёмник получает посылку, в свою очередь суммирует все байты кроме последнего (или двух последних, если контрольная сумма 16-битная), а затем сравнивает это значение с полученной контрольной суммой. Если отличается хоть на 1 - данные повреждены. Причём повреждёнными при передаче могут быть как сами данные, так и контрольная сумма: в любом случае они не совпадут, а это означает, что передача произошла с ошибкой.

Давайте рассмотрим пример "передачи и приёма" структуры, где будет использоваться конструкция, позволяющая разбивать любые данные на байтовый поток. Три таких конструкции мы рассмотрели в уроке про указатели и ссылки. Структуру используем для удобства упаковки и использования данных. Универсальная для любого типа данных функция расчёта хэш-суммы может выглядеть так:

uint8_t getHash(uint8_t* data, size_t length) {
  uint8_t hash = 0;
  size_t i = 0;
  while (length--) {
    hash += *(data + i);
    i++;
  }
  return hash;
}

И возвращать байт суммы. Создадим и заполним структуру данными и прогоним через эту функцию. В последний байт структуры запишем контрольную сумму:

// структура данных посылки
struct MyData {
  uint8_t channel;
  int val_i;
  float val_f;
  uint8_t hash;  // байт контрольной суммы
};

void setup() {
  Serial.begin(9600);
  // создаём и заполняем дату
  MyData data;
  data.channel = 16;
  data.val_i = 12345;
  data.val_f = 3.1415;
  data.hash = 0;

  // расчёт суммы
  uint8_t thisHash = getHash((uint8_t*)&data, sizeof(data));

  // пакуем в посылку
  data.hash = thisHash;

  // выведем для отладки
  Serial.println(thisHash); // выдаст 102
}

Теперь можно передать структуру приёмнику! Пример "синтетический", так как кому и каким способом передавать данные мы не рассматриваем. Хотя, можно отправить по Serial, например с одной Ардуины на другую:

Serial.write((uint8_t*)&data, sizeof(data));

Далее на приёмнике примем данные:

// структура данных посылки
struct MyData {
  uint8_t channel;
  int val_i;
  float val_f;
  uint8_t hash;  // байт контрольной суммы
};
MyData rxData;

void setup() {
  Serial.begin(9600);
}

void loop() {
  if (Serial.readBytes((uint8_t*)&rxData, sizeof(rxData))) {
    // приняли данные
  }
}

Теперь нужно убедиться в том, что данные верны. Для этого прогоним их через ту же суммирующую функцию, но без учёта последнего байта, так как он сам является суммой:

uint8_t thisHash = getHash((uint8_t*)&rxData, sizeof(rxData) - 1);

Если значение совпадёт с переданным rxData.hash - данные верны! Дополним предыдущий код:

void loop() {
  if (Serial.readBytes((uint8_t*)&rxData, sizeof(rxData))) {           // читаем дату
    uint8_t thisHash = getHash((uint8_t*)&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(uint8_t *buffer, size_t size) {
  uint8_t crc = 0;
  for (size_t i = 0; i < size; i++) {
    uint8_t 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 {
  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((uint8_t*)&data, sizeof(data) - 1);

  // пакуем в посылку
  data.crc = crc;
}

void loop() {
  // отправляем
  Serial.write((uint8_t*)&data, sizeof(data));
  delay(1000);
}

uint8_t crc8(uint8_t *buffer, size_t size) {
  uint8_t crc = 0;
  for (size_t i = 0; i < size; i++) {
    uint8_t 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 {
  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((uint8_t*)&rxData, sizeof(rxData)); // считаем crc посылки полностью
    if (crc == 0) {
      // данные верны
    } else {
      // данные повреждены
    }
  }
}

uint8_t crc8(uint8_t *buffer, size_t size) {
  uint8_t crc = 0;
  for (size_t i = 0; i < size; i++) {
    uint8_t 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:

uint8_t crc8_asm(uint8_t *buffer, size_t size) {
  uint8_t crc = 0;
  for (size_t i = 0; i < size; i++) {
    uint8_t 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;
}

Функция используется точно так же, как предыдущая.

CRC32 #

Для повышения надёжности можно использовать не 8, а 32 бит CRC, например при помощи вот такой функции:

uint32_t crc32(uint32_t crc, uint8_t* buffer, size_t len) {
    crc = ~crc;
    while (len--) {
        crc ^= *buffer++;
        for (uint8_t i = 0; i < 8; i++) crc = (crc & 1) ? ((crc >> 1) ^ 0x4C11DB7) : (crc >> 1);
    }
    return ~crc;
}