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

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

Любите ли вы 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!
Этой публикацией некоторым образом закрыл давний гештальт, поставил галочку, крестик, перевернул страницу, затянул кота в долгий ящик, сделал дело и гуляю смело.

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