Хорошо парсим NMEA0183

Приветствую, глубокоуважаемые!

Будем стараться делать хорошо, плохо само получится (С)

Любите ли вы NMEA0183, как люблю его я? Умеете ли? Практикуете ли?

Хочу поделиться универсальным, модульным, гибким, шустрым и исключительно нетребовательным к ресурсам парсером для работы с NMEA-сообщениями в Embedded.

Под катом подготовил для вас рассказ о том, как это работает, как использовать, онлайн-демку с пошаговым выполнением алгоритма и подсветкой выполняемых веток кода, а в качестве бонуса еще один парсер NMEA, я бы даже сказал убер-парсер - но уже не для Embedded.

0. Intro

Просто напомню, что NMEA0183 это ASCII-протокол, т.е. сообщения представляют собой, или, точнее рассматриваются как строки из ASCII-кодов. Вот пример сообщения:

$WIMTW,10.8,C*09<CR><LF> 
  │ │    │  │ │ 
  | |    |  | └── CRC (0x09) 
  │ │    |  └──── Единицы измерения (°C) 
  | |    └─────-─ Температура (23.5) 
  │ └──────────── Sentence ID - Тип сообщения (MTW) 
  └────────────── Talker ID - Источник (WI)

Сообщения всегда начинаются с символа $, а заканчиваются \r\n (0x0D 0x0A).
Перед концом сообщения есть необязательное поле контрольной суммы, которое начинается со знака и содержит два шестнадцатеричных символа - побайтное xor всех байт между $ и исключительно.

Внутри сообщение устроено несложно - это просто список значений, разделенных запятыми. При этом самое первое поле - это идентификатор источника и/или сообщения.

Каждому сообщению строго соответствует формат полей - тип данных и как их интерпретировать, например, стандартное сообщение MTW - Mean Water Temperature, идентификатор источника WI - Weather Instrument, первое поле после заголовка содержит вещественное число, соответствующее измеренной температуре воды, а второе поле содержит единицы измерения, в данном случае C - градусы Цельсия.

Сообщения бывают стандартными, как в примере выше и "проприетарными", у которых после $ следует символ P с трехсимвольным идентификатором производителя (Manufacturer ID) и собственно идентификатором сообщения, которое бывают очень разными и зависят от прихотей производителя.

Я нахожу этот протокол исключительно удобным и почти во всем нашем оборудовании его применяем. Вот например, чтобы при помощи гидроакустического модема uWave запросить, скажем глубину другого такого же модема применяется команда такого формата:

$PUWV2,1,0,2*29<CR><LF>
 | | | | | |  |
 | | | | | |  └── CRC (0x29) 
 | | | | | └───── ID запрашиваемого параметра, для uWave здесь 2 - глубина
 | | | | └─────── Номер канала, в котором ждать ответ (0) 
 | | | └───────── Номер канала, в котором ведет прием адресат
 | | └─────────── ID команды, здесь 2 - Remote Request
 | └───────────── Идентификатор системы команды (типа Manufacturer ID)
 └─────────────── P - Proprietary

Если требуется передавать в рамках протокола строки или просто массивы байт, это также несложно сделать. Единственное ограничение на строки - они не должны содержать символы, используемые протоколом для управления: $, ,, *, и символы с кодами 0x0D и 0x0A.

Изначальный стандарт накладывает ограничения на максимальную длину сообщений, если мне не изменяет память, в 82 символа, но совершенно никто не сможет вам помешать использовать для своих целей сообщения большей длины, хотя, конечно, стоит помнить о восьмибитности и некоторой "ущербности" применяемого алгоритма контрольной суммы - все-таки побайтовый xor не самая стойкая к коллизиям конструкция. Можно подумать, что связь по проводам итак достаточно надежная, но нам в работе очень часто приходится передавать такие сообщения, например по радио - обычному, 433 МГц в режиме прозрачного канала, где никто вообще никаких гарантий ни на что не даст.

1. Какой нужен парсер

Задача в целом выглядит так, что надо бы из входного потока байт выбирать целые сообщения по признаку начала и конца, определять тип сообщения и согласно известному списку параметров разбирать их поочередно. Можно выбирать только те, которые интересуют - например, широту и долготу или текущее время.

По сути очевидная реализация - линейный автомат, который:

• ждет $

• накапливает строку до \r\n

• проверяет CRC

• разбивает по запятым

• заполняет структуру по полям

Можно сделать этот простейший "велосипед", можно взять что-то готовое, например, TinyGPS++ или microNMEA - там большое комьюнити и наверное все все постоянно проверяют и дорабатывают, и если нужно просто распарсить данные от GNSS-приемника, то наверное проще взять что-то из этого.

Меня не устроило:

• использование strcmp, strtok и прочих подобных (TinyGPS). Хоть там и нет явного выделения памяти, и в целом вопрос дискуссионный, но лучше знать наверняка, что происходит со стеком, чем не знать;

• Невозможность разбирать только то, что меня интересует: если вы сталкивались обработкой данных с GNSS-приемников, то наверняка знаете, что они вываливают огромную простыню данных, например, параметры DOP, список используемых в решении спутников и их эфемериды. Эти данные не всегда нужны и если решать задачу в лоб, то можно очень много времени тратить на разбор всей этой массы данных;

• И главная причина - мне нужен универсальный парсер, я сам хочу формировать и разбирать свои сообщения. Т.е. по сути все равно придется делать что-то свое. И если делать велосипед, то надо делать хороший.

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

Например, если меня интересуют только сообщения, скажем, --RMC (здесь и далее "--" означает, что нам не важен Talker ID - GN, GP, GL и пр.) и --GGA, то приняв $--GSA парсер уже должен прекратить обработку, перейти к ожиданию начала следующего сообщения и не тратить время.

А еще, возможно, мне захочется прямо на лету включить или отключить обработку какого-либо сообщения, кто знает? Такая возможность тоже вполне пригодилась бы.

Напомню, что речь идет про Embedded - нужна надежность и низкие накладные расходы. Значит мы не будем использовать динамическое выделение памяти - только статический буфер.

2. Устройство парсера

Взглянув на сообщения NMEA можно заметить одну деталь: все стандартные сообщения имеют фиксированный размер Talker и Sentence ID - 2 и 3 байта. А как насчет того, чтобы идентификатор сообщениях хранить не в виде строки, а в виде 24-битного числа? И даже не только хранить, а искать, сравнивать.

Напомню, что сначала нам нужно как можно раньше отсечь сообщения, которые нас не интересуют. Поэтому первые шаги алгоритма могут быть такие:

• ждем $

• накапливаем uint16 - это будет Talker ID

• накапливаем три байта и записываем их в uint32 - это будет Sentence ID

• ищем в массиве обрабатываемых сообщений, присутствует ли такой Sentence ID

• если не присутствует - переходим к ожиданию следующего сообщения

Вот список самых наиболее часто употребимых идентификаторов сообщений, которые парсер поддерживает "из коробки":

Возникает резонный вопрос: как быть с P-сообщениями? Здесь придется оставить место для компромисса. У нас есть две новости: плохая и хорошая.

Плохая заключается в том, что идентификатор проприетарных сообщений вообще никак не стандартизируется - каждый производитель может что угодно делать. Например, у GNSS-приемников с протоколом MTK (Например, Quectel) проприетарный команды имеют идентификаторы 001 - 399. Выглядит это как $PMTK314,....., у некоторых они вообще могут иметь разную длину.

Хорошая же состоит в том, что если требуется создание своего протокола, то это можно лекго учесть: трехбайтный Manufacturer ID вместе одним символом в качестве идентификатора команды дает uint32, который с то же легкостью можно искать в таблице обрабатываемых сообщений.
Можно также "отложить проблему на потом" - искать сообщение с идентификатором, скажем, MTK0 - это умещается в 32-битное целое, а уже при разборе полей анализировать оставшуюся часть этого идентификатора, и выяснить, например, что это сообщение MTK001 или какое-то другое.

Естественно, нужно в алгоритме учесть, обрабатывается ли стандартное или проприетарное сообщение. И еще о чем не стоит забывать - сразу после получения $ нужно начинать считать контрольную сумму: мы будем считать ее на лету и когда дойдем до * то у нас будет с чем сравнить. Если же источник был настолько ленив, что не снабдил сообщение контрольной суммой - это тоже нужно учесть и априори считать, что целостность не нарушена.

Ну и пора ввести необходимые структуры данных и обозначить модули.

У нас будет функция, которая принимает на вход очередной байт и возвращает значение типа enum, которого говорит о текущем состоянии парсера:

typedef enum {
  NMEA_RESULT_PACKET_READY          = 0, // В буфере лежит готовое сообщение
  NMEA_RESULT_BYPASS_BYTE           = 1, // пропустили этот байт
  NMEA_RESULT_PACKET_STARTED        = 2, // начался набор сообщения
  NMEA_RESULT_PACKET_PROCESS        = 3, // сообщение в процессе
  NMEA_RESULT_PACKET_CHECKSUM_ERROR = 4, // сообщение с ошибкой контрольной суммы
  NMEA_RESULT_PACKET_TOO_BIG        = 5, // сообщение никак не кончается а буфер уже
  NMEA_RESULT_PACKET_SKIPPING       = 6, // это сообщение пропускаем
  NMEA_RESULT_UNKNOWN                    // для порядка
} NMEA_Result_Enum;

Теперь опишем структуру состояния парсера, т.к. он у нас конченный автомат:

typedef struct {
  uint8_t* buffer;      // Указатель на буфер
  uint8_t  buffer_size; // Размер буфера
  uint8_t  idx;         // Текущий индекс в буфере
  bool  isReady;        // Признак готового сообщения
  bool  isStarted;      // Признак того, что сообщение в процессе приема
  bool  isPSentence;    // Признак P-сообщения
  uint8_t  chk_act;     // Фактическое значение контрольной суммы
  uint8_t  chk_dcl;     // Заявленное значение контрольной суммы
  uint8_t  chk_dcl_idx; // Индекс байта контрольной суммы
  bool  chk_present;    // Признак наличия поля контрольной суммы
  uint16_t  tkrID;      // Talker ID - идентификатор источника
  uint32_t  sntID;      // Sentence ID - идентификатор сообщения
  uint32_t* sntIDs;     // Указатель на идентификаторы, которые мы обрабатываем
  uint8_t  sntIDs_size; // И размер этого буфера

} NMEA_State_Struct;

За вычетом размеров буфера и массива идентификаторов обрабатываемых сообщений, размер структуры составляет порядка 25-32 байт в зависимости от платформы и выравнивания.

Размер байтового буфера, куда мы складываем сообщение ограничен 256 байтами, но, как правило размеры стандартных сообщений не превышают 100 символов, например, сообщение RMC имеет длину 60 байт и если нас интересует только оно, то общий memory footprint составит порядка 140 байт, без учета стека и пр.

2.1. Пару слов о применении

Прежде чем мы рассмотрим саму функцию обработки входных данных, пару слов о том, как пользователь может инициализировать парсер:

void NMEA_InitStruct(NMEA_State_Struct* uState, uint8_t* buffer, uint8_t buffer_size, uint32_t* sntIDs, uint8_t sntIDs_size) {

  uState->isReady = false;
  uState->buffer = buffer;
  uState->buffer_size = buffer_size;
  uState->sntIDs = sntIDs;
  uState->sntIDs_size = sntIDs_size;
  uState->isStarted = false;
}

Выше функция для инициализации структуры. Как видим, в нее передается буфер под сообщение и его размер, а так же массив, содержащий интересующие нас идентификаторы сообщений с его размером.

Вот фактически пример из реального устройства:

// Объявления и переменные

#define PMTK0_SNT_ID      (0x4D544B30) // MTK0
#define IN_BUFFER_SIZE    (128)
#define GNSS_SNT_IDS_SIZE (2)

uint32_t gnss_sntIDs[GNSS_SNT_IDS_SIZE] = { NMEA_RMC_SNT_ID, PMTK0_SNT_ID };
uint8_t gnss_inbuffer[IN_BUFFER_SIZE];

UCNL_NMEA_State_Struct gnss_parser;
UCNL_NMEA_Result_Enum  n_result;

// В инициализации

NMEA_InitStruct(&gnss_parser, gnss_inbuffer, IN_BUFFER_SIZE, gnss_sntIDs, GNSS_SNT_IDS_SIZE);


// При обработке входящего байта

n_result = UCNL_NMEA_Process_Byte(&gnss_parser, Ring_u8_Read(&gnss_iring));
		if (n_result == UCNL_NMEA_RESULT_PACKET_READY) {
			if (gnss_parser.sntID == UCNL_NMEA_RMC_SNT_ID) {
				UCNL_NMEA_Parse_RMC(&rmc_data, gnss_parser.buffer, gnss_parser.idx);
				CP_RMC_Received(&rmc_data);
			} else if (gnss_parser.sntID == PMTK0_SNT_ID) {
				CP_PMTK0_Received();
			}
			UCNL_NMEA_Release(&gnss_parser); // просто сброс флага isReady
		}
	}

Для пуристов предлагаю схему конечного автомата и таблицу переходов:

2.2. Конечный автомат

┌─────────────────────────────────────────────────────────────┐
│                       СОСТОЯНИЯ АВТОМАТА                    │
├─────────────────────────────────────────────────────────────┤
│ 1. WAIT_START     - Ожидание начала сообщения ($)           │
│ 2. HEADER_PARSE   - Разбор заголовка (байты 1-5)            │
│ 3. DATA_PARSE     - Разбор данных (байты 6-N)               │
│ 4. CHECKSUM_PARSE - Разбор контрольной суммы (2 байта)      │
│ 5. PACKET_READY   - Сообщение готово (\n получен)           │
│ 6. ERROR_STATES   - Ошибочные состояния                     │
└─────────────────────────────────────────────────────────────┘

                            ┌─────────────────────────────────────┐
                            │        ИСХОДНОЕ СОСТОЯНИЕ           │
                            │    WAIT_START (Ожидание начала)     │
                            │  isStarted = false, isReady = false │
                            └─────────────────┬───────────────────┘
                                              │
                                              │ Получен байт == '$'
                                              ▼
                    ┌────────────────────────────────────────────────────┐
                    │          START_PACKET (Начало сообщения)           │
                    │  isStarted = true, result = PACKET_STARTED         │
                    │  Очистка буфера и счетчиков, запись '$' в буфер    │
                    └─────────────────┬──────────────────────────────────┘
                                      │
                                      │ Следующий байт (idx=1)
                                      ▼
┌─────────────────────────────────────────────────────────────────────────┐
│                            HEADER_PARSE STATE                           │
│   Разбор байтов 1-5: определение типа сообщения и источника             │
│   Состояния: chk_dcl_idx = 0 (парсим данные заголовка)                  │
└───┬──────────────────────────────────────────────────────────────────┬──┘
    │                                                                  │
    │                                                                  │
    │ idx=1: Проверка на 'P' (проприетарное сообщение)                 │
    │ idx=2-5: Сбор sntID (24-битный идентификатор сообщения)          │
    │                                                                  │
    │ После idx=5: Проверка наличия sntID в списке поддерживаемых      │
    │   Если НЕ найден → ERROR_SKIPPING                                │
    │                                                                  │
    ▼                                                                  ▼
    │                                                                  │
    │ После idx>5                                                      │
    │                                                                  │
    ▼                                                                  │
┌─────────────────┐                                                    │
│ DATA_PARSE STATE│                                                    │
│ chk_dcl_idx = 0 │                                                    │
│ Накопление XOR  │                                                    │
│ для контрольной │                                                    │
│ суммы, запись   │                                                    │
│ в буфер         │                                                    │
└────────┬────────┘                                                    │
         │                                                             │
         │ Получен '*' (NMEA_CHK_SEP)                                  │
         │                                                             │
         ▼                                                             │
┌──────────────────┐                                                   │
│ CHECKSUM_PARSE   │                                                   │
│ chk_dcl_idx = 1  │                                                   │
│ Первый hex-символ│                                                   │
└────────┬─────────┘                                                   │
         │                                                             │
         │ Второй hex-символ                                           │
         │ chk_dcl_idx = 2                                             │
         │                                                             │
         ▼                                                             │
┌─────────────────┐                                                    │
│ CHECKSUM_VERIFY │                                                    │
│ chk_dcl_idx = 3 │                                                    │
│ Сравнение CRC   │                                                    │
│ Если ошибка →   │                                                    │
│ ERROR_CHECKSUM  │                                                    │
└────────┬────────┘                                                    │
         │                                                             │
         │                                                             │
         ▼                                                             │
    Получен '\n'                                                       │
    (NMEA_SNT_END)                                                     │
         │                                                             │
         ▼                                                             │
┌─────────────────┐                ┌─────────────────┐                 │
│ PACKET_READY    │                │ ERROR_STATES    │◄────────────────┘
│ isStarted=false │                │ isStarted=false │
│ isReady=true    │                │ result=ERROR    │
│ result=READY    │                └─────────────────┘
└─────────────────┘                         ▲
         │                                  │
         │ Сброс парсера                    │ Ошибки:
         │ NMEA_Release()                   │ 1. PACKET_TOO_BIG (буфер полон)
         ▼                                  │ 2. PACKET_SKIPPING (sntID не найден)
┌─────────────────┐                         │ 3. CHECKSUM_ERROR (CRC не совпал)
│ WAIT_START      │◄────────────────────────┘
└─────────────────┘

Таблица переходов состояний (STT)

Поток данных через автомат выглядит следующим образом:

Байт → [WAIT_START] → [HEADER_PARSE] → [DATA_PARSE] → [CHECKSUM_PARSE] → [Готово]
        ↓               ↓               ↓               ↓
      Пропуск        Сбор ID        XOR CRC       Проверка CRC
      (если не $)   (1-5 байты)    (6+ байты)     (*XX)

NMEA_Result_Enum NMEA_Process_Byte(NMEA_State_Struct* uState, uint8_t newByte) {

  NMEA_Result_Enum result = NMEA_RESULT_BYPASS_BYTE;

  if (!uState->isReady) {

    if (newByte == NMEA_SNT_STR) {

      uState->isStarted = true;
      result = NMEA_RESULT_PACKET_STARTED;

      uint8_t i = 0;
      for (i = 0; i < uState->buffer_size; i++)
        uState->buffer[i] = 0;

      uState->chk_act     = 0;
      uState->chk_dcl     = 0;
      uState->chk_dcl_idx = 0;
      uState->idx         = 0;

      uState->tkrID       = 0;
      uState->sntID       = 0;

      uState->isPSentence = false;

      uState->buffer[uState->idx] = newByte;
      uState->idx++;
    } else {
      if (uState->isStarted) {

        result = NMEA_RESULT_PACKET_PROCESS;
        uState->buffer[uState->idx] = newByte;

        if (newByte == NMEA_SNT_END) {

          uState->isStarted = false;
          uState->isReady = true;
          result = NMEA_RESULT_PACKET_READY;
        } else if (newByte == NMEA_CHK_SEP) {

          uState->chk_dcl_idx = 1;
          uState->chk_present = true;
        } else {
          if (uState->idx >= uState->buffer_size) {

            uState->isStarted = false;
            result = NMEA_RESULT_PACKET_TOO_BIG;
          } else {
            if (uState->chk_dcl_idx == 0) {

              uState->chk_act ^= newByte;
              if (uState->idx == 1)
                if (newByte == NMEA_PSENTENCE_SYMBOL)
                  uState->isPSentence = true;
                else
                  uState->tkrID = ((uint16_t)newByte) << 8;
              else if (uState->idx == 2)
                if (uState->isPSentence)
                  uState->sntID = ((uint32_t)newByte) << 24;
                else
                  uState->tkrID |= newByte;
              else if (uState->idx == 3)
                if (uState->isPSentence)
                  uState->sntID |= (((uint32_t)newByte) << 16);
                else
                  uState->sntID = (((uint32_t)newByte) << 16);
              else if (uState->idx == 4)
                uState->sntID |= (((uint32_t)newByte) << 8);
              else if (uState->idx == 5) {
                uState->sntID |= newByte;

                uint8_t i = 0;
                while ((i < uState->sntIDs_size) && (uState->sntID != uState->sntIDs[i]))
                  i++;

                if (i >= uState->sntIDs_size) {

                  uState->isStarted = false;
                  result = NMEA_RESULT_PACKET_SKIPPING;
                }
              }
            } else if (uState->chk_dcl_idx == 1) {

              uState->chk_dcl = 16 * STR_HEXDIGIT2B(newByte);
              uState->chk_dcl_idx++;
            } else if (uState->chk_dcl_idx == 2) {

              uState->chk_dcl += STR_HEXDIGIT2B(newByte);
              if (uState->chk_act != uState->chk_dcl) {
                uState->isStarted = false;
                result = NMEA_RESULT_PACKET_CHECKSUM_ERROR;
              }
              uState->chk_dcl_idx++;
            }
          }
        }

        uState->idx++;
      }
    }
  }
  return result;
}

Нельзя, видимо, сказать, что код выглядит элегантно, но и не то чтобы прям совсем плохо. Все в статической памяти, никаких излишеств. В среднем на какой-то простой платформе на обработку одного байта требуется ~10-50 тактов.

Чтобы лучше понять работу алгоритма я подготовил онлайн-демку, которой можно задать сообщение и нажимая кнопку "ШАГ", побайтно скормить сообщение парсеру, наблюдая за активными ветками алгоритма и изменением состояния сознания структуры.

3. Разбор сообщений

Конечно, к этому моменту может возникнуть вопрос: а где же разбор сообщений? Ведь то, что было представлено до этого только с натяжкой является парсером - это скорее поиск и валидация.

Да. После того, как интересующее сообщение попало в буфер нужно достать из него информацию. Здесь я не предложу какие-то новаций.

У меня на каждое сообщение отдельная функция-парсер и соответственно стуктура, которая этой функцией заполняется.

Разберем на примере того же RMC, как наиболее часто употребимого. Вот структура, описывающая его:

typedef struct {
  bool isValid;
  uint8_t hour;
  uint8_t minute;
  float second;
  uint8_t date;
  uint8_t month;
  uint8_t year;
  float latitude_deg;
  float longitude_deg;
  float speed_kmh;
  float course_deg;
} NMEA_RMC_RESULT_Struct;

bool NMEA_Parse_RMC(NMEA_RMC_RESULT_Struct* rdata, const uint8_t* buffer, uint8_t idx) {

  // Sentence example:
  // $GPRMC,230540.00,A,5312.1329616,N,15942.6950884,E,4.9,217.1,290421,999.9,E,D*3C

  bool isNotLastParam = false;
  bool result = true;
  uint8_t pIdx = 0, ndIdx = 0, stIdx = 0;

  do {

    isNotLastParam = NMEA_Get_NextParam(buffer, ndIdx + 1, idx, &stIdx, &ndIdx);

    switch (pIdx) {

      case 1: // Time
        if (ndIdx < stIdx)
          result = false;
        else {
          rdata->hour = STR_CC2B(buffer[stIdx], buffer[stIdx + 1]);
          rdata->minute = STR_CC2B(buffer[stIdx + 2], buffer[stIdx + 3]);
          rdata->second = STR_ParseFloat(buffer, stIdx + 4, ndIdx);

          if (!NMEA_IS_VALID_HOUR(rdata->hour) ||
              !NMEA_IS_VALID_MINSEC(rdata->minute) ||
              !NMEA_IS_VALID_MINSEC(rdata->second))
            result = false;
        }
        break;

      case 2: // Time validity flag
        if ((ndIdx < stIdx) || (buffer[stIdx] != NMEA_TD_VALID))
          result = false;
        break;

      case 3: // Latitude
        if (ndIdx < stIdx)
          result = false;
        else
          rdata->latitude_deg = (float)STR_CC2B(buffer[stIdx], buffer[stIdx + 1]) +
                                STR_ParseFloat(buffer, stIdx + 2, ndIdx) / 60.0;

        if (!NMEA_IS_VALID_LATDEG(rdata->latitude_deg))
          result = false;
        break;

      case 4: // Latitude hemisphere
        if (ndIdx < stIdx)
          result = false;
        else if (buffer[stIdx] == NMEA_SOUTH_SIGN)
          rdata->latitude_deg = -rdata->latitude_deg;
        break;

      case 5: // Longitude
        if (ndIdx <= stIdx)
          result = false;
        else
          rdata->longitude_deg = (float)STR_CCC2B(buffer[stIdx], buffer[stIdx + 1], buffer[stIdx + 2]) +
                                 STR_ParseFloat(buffer, stIdx + 3, ndIdx) / 60.0;

        if (!NMEA_IS_VALID_LONDEG(rdata->longitude_deg))
          result = false;

        break;

      case 6: // Longitude hemisphere
        if (ndIdx < stIdx)
          result = false;
        else if (buffer[stIdx] == NMEA_WEST_SIGN)
          rdata->longitude_deg = -rdata->longitude_deg;
        break;

      case 7: // Speed in knots
        if (ndIdx >= stIdx)
          rdata->speed_kmh = STR_ParseFloat(buffer, stIdx, ndIdx) * 1.852; //
        break;

      case 8: // Course in degrees
        if (ndIdx >= stIdx)
          rdata->course_deg = STR_ParseFloat(buffer, stIdx, ndIdx);
        break;

      case 9: // Date
        if (ndIdx < stIdx)
          result = false;
        else {

          rdata->date = STR_CC2B(buffer[stIdx], buffer[stIdx + 1]);
          rdata->month = STR_CC2B(buffer[stIdx + 2], buffer[stIdx + 3]);
          rdata->year = STR_CC2B(buffer[stIdx + 4], buffer[stIdx + 5]);

          if (!NMEA_IS_VALID_DATE(rdata->date) ||
              !NMEA_IS_VALID_MONTH(rdata->month) ||
              !NMEA_IS_VALID_YEAR(rdata->year))
            result = false;
        }
        break;

      case 12: // Data validity flag
        if ((ndIdx < stIdx) || (buffer[stIdx] == NMEA_DATA_NOT_VALID))
          result = false;
        break;
      default:
        break;
    }
    pIdx++;
  } while (isNotLastParam && result);

  rdata->isValid = result;
  return result;
}

Конечно, этот код легко дорабатывается под конкретные нужды путем выкидывания не интересующих нас веток в switch-case.

Поиск индексов начала и конца текущего параметра выполняются такой функцией:

bool NMEA_Get_NextParam(const uint8_t* buffer, uint8_t fromIdx, uint8_t size, uint8_t* stIdx, uint8_t* ndIdx) {

  uint8_t i = fromIdx + 1;
  *stIdx = fromIdx;
  *ndIdx = *stIdx;

  while ((i <= size) && (*ndIdx == *stIdx)) {

    if ((buffer[i] == NMEA_PAR_SEP) ||
        (buffer[i] == NMEA_CHK_SEP) ||
        (buffer[i] == NMEA_SNT_END1) ||
        (i == size)) {

      *ndIdx = i;
    } else {
      i++;
    }
  }

  (*stIdx)++;
  (*ndIdx)--;

  return ((buffer[i] != NMEA_CHK_SEP) && (i != size) && (buffer[i] != NMEA_SNT_END1));
}

На остальном не буду останавливаться подробно. Скажу лишь, что парсинг (и преобразование в строку) чисел вынесен в отдельный модуль. Так же, как уже было упомянуто, библиотека из коробки имеет арсенал для парсинга основных сообщений, которые можно получить от среднего GNSS-приемника и даже больше.

4. Резюмируем

4.1. Особенности

Среди особенностей реализации можно выделить такие (не все строго положительные - это не плюсы, а особенности):

• Это Гибридный автомат - использует как явные флаги (isStarted, isReady), так и неявное состояние через idx и chk_dcl_idx;

• Ранний отсев - сразу после получения полного sntID (байт 5) происходит проверка, нужно ли это сообщение;

• Инкрементальная проверка CRC - XOR накапливается на лету, а не после получения всего сообщения;

• Обработка проприетарных сообщений - отдельная ветка для сообщений, начинающихся с 'P';

• Защита от переполнения - проверка idx >= buffer_size на каждом шаге;

• Поддержка сообщений без CRC - если * не получен, сообщение считается валидным (при условии корректного \n).

В итоге мы пришли к реализации наших пожеланий к парсеру, а именно:

• минимальный memory footprint

• все делается за один проход (поиск и валидация сообщения, разбор полей - второй проход)

• ненужное отсеивается сразу (хотя можно еще раньше в принципе)

• полностью статическая память

4.2. Memory footprint

Если сравнивать по использованию памяти с самыми популярными парсерами, то получается такая табличка:

Дополнительно приведена колонка, если вдруг нам захочется оптимизировать полностью и мы похожие данные (например, координаты и время несколько раз встречаются в разных сообщениях) объединим.

4.3. Производительность

Я понимаю, что оправдание есть у каждого и у меня до замеров скорости на железе руки не дошли.

Но!

Мы можем волюнтаристически прикинуть производительность нашего парсера и наиболее популярных других.

Какие метрики хотелось бы проанализировать:

• сколько тратится тактов на обработку одного байта

• сколько тактов тратится на обработку одного какого-нибудь популярного сообщения

Итак,

Примерно прикинем для трех платформ - Cortex-M0, Cortex-M4 и AVR сколько тактов требуется на парсинг сообщения RMC.

Для указанных платформ основные операции имеют такую стоимость в тактах:

Для нашего парсера отдельно посчитаем поиск с валидацией и собственно парсинг - разбор полей сообщений.

Для Cortex-M0

Байты 1-6 (заголовок):

• '$': Инициализация: 40 тактов

• 'G': tkrID = byte << 8 (8 тактов): 30 тактов

• 'P': tkrID |= byte: 26 тактов

• 'R': sntID = byte << 16 (16 тактов): 50 тактов

• 'M': sntID |= byte << 8 (8 тактов): 40 тактов

• 'C': sntID |= byte + поиск в массиве: 45 тактов Итого заголовок: 40+30+26+50+40+45 = 231 такт

Байты 7-64 (58 байт данных):

• Базовые проверки + XOR: 20 тактов/байт

• 58 × 20 = 1160 тактов

Байт 65 '*': Переход в режим CRC: 22 такта
Байт 66 '6': Первый hex CRC: 35 тактов
Байт 67 'A': Второй hex CRC: 35 тактов
Байт 68 '\n': Конец сообщения: 25 тактов

Итого валидация: 231+1160+22+35+35+25 = 1508 тактов

NMEA_Get_NextParam: 12 вызовов × 45 тактов = 540 тактов
STR_CC2B: 8 чисел × 15 тактов = 120 тактов
STR_CCC2B: 1 число × 20 тактов = 20 тактов
STR_ParseFloat: 5 чисел × 250 тактов = 1250 тактов
Проверки валидности: 12 × 12 = 144 тактов
Конвертации (узлы→км/ч): 1 × 50 = 50 тактов

Итого парсинг: 540+120+20+1250+144+50 = 2124 такта

Все в сумме: 1508+2124 = 3632 такта

Для Cortex-M4, имеющего т.н. barrel shifter, сдвиги происходят значительно легче - всего за 1 такт вместо по такту на бит. Поэтому валидация пройдет чуть быстрее (минус 200 тактов), а за счет более быстрых вызовов, примерно на 20% уменьшиться число тактов на разбор полей. Примерно это выльется в 3000+ тактов.

Для AVR, у которого все 32-битное и все, что связано с float сильно дороже, и валидация и разбор полей идут значительно медленнее - примерно должно быть 1800+ и 2500+ тактов соответственно и на все должно быть где-то 4300+ тактов.

Для TinyGPS++, который использует строковые операции с выделением памяти и для MicroNMEA прикинем еще более примерно:

TinyGPS++
Cortex-M0:

• strtok() 12 токенов: 12 × 120 = 1440 тактов

• atof() 6 чисел: 6 × 600 = 3600 тактов (float на M0 очень медленно!)

• String операции: 500 тактов

• Проверки: 300 тактов Итого: ~5840 тактов

Cortex-M4:

• atof() с FPU: 6 × 150 = 900 тактов (в 4× быстрее)

• Остальное: 1440+500+300 = 2240 тактов Итого: 3140 тактов

AVR:

• atof() на AVR: 6 × 800 = 4800 тактов (очень медленно)

• strtok(): 12 × 150 = 1800 тактов Итого: ~7100 тактов

MicroNMEA
Cortex-M0:

• Ручной парсинг чисел (не atof): 6 × 200 = 1200 тактов

• Разбивка полей: 12 × 70 = 840 тактов

• Проверки и CRC: 400 тактов

• Итого: ~2440 тактов

Cortex-M4:

• Парсинг быстрее: 6 × 120 = 720 тактов

• Итого: ~1960 тактов

AVR:

• Ручной парсинг: 6 × 300 = 1800 тактов

• Итого: ~3040 тактов

В итоге получаем такую таблицу, где описывается сколько времени какой парсер тратит на парсинг сообщения RMC:

Да, мы некоторым образом медленнее MicroNMEA, но надо учитывать, что речь идет о сообщении RMC, а в реальности GNSS-приемник валит очень много всего.

Возьмем какой-нибудь типичный GNSS-приемник типа ublox/Quectel, он выдает примерно такой набор раз в секунду:

• RMC - 1× (70 байт) - НУЖНО

• GGA - 1× (75 байт) - НУЖНО

• GSA - 1× (65 байт) - НЕ НУЖНО

• GSV - 3× (70 байт) - НЕ НУЖНО (210 байт)

• VTG - 1× (60 байт) - НЕ НУЖНО

• GLL - 1× (~40 байт) - НЕ НУЖНО

Опять же, валюнтаристически примем, что парсинг GGA чуть дороже, чем RMC и тогда получается такая окончательная таблица:

Конечно, прикидки очень грубые. Конечно, можно у приемника настроить вывод только нужных сообщений. Но в общем-то я пока даже не пытался заниматься низкоуровневой оптимизацией, а там есть где разгуляться.

На этом будем заканчивать и перейдем к обещанному бонусу.

5. Бонус

Я использую NMEA0183, страшно сказать, года с 2008-ого наверное. В 2011-2012 я написал, как мне тогда казалось, убер-библиотеку на эту тему, правда на C# - его я использую для десктопных задач.

Библиотека знает все стандартные сообщения и некоторые проприетарные. И не просто умеет их парсить, а содержит разные описания: что означает тот или иной Talker ID или Sentence ID.
Более того, она позволяет добавлять свои форматы сообщений.

В прошлом году я в полуавтоматическом режиме перевел ее и на JS, поэтому ей можно пользоваться онлайн - просто заходим, скармливаем любое NMEA-сообщение и получаем названия и значения полей.

Я стараюсь по мере сил и времени ее поддерживать в актуальном состоянии.

Все полезные ссылки из этой статьи в одном месте:

• С-библиотека из этой статьи

• Онлайн-демо с возможностью пошаговой демонстрации алгоритма

• Убер-библиотека на C#

• JS-версия убер-библиотеки

• Онлайн-парсер на основе JS-версии

5. Outro

Что ж, Long read - long write!
Этой публикацией некоторым образом закрыл давний гештальт, поставил галочку, крестик, перевернул страницу, затянул кота в долгий ящик, сделал дело и гуляю смело.

Искренне благодарю вас за интерес к этой теме, буду рад выслушать конструктивную критику, предложения, пожелания, вопросы.