NMEA GPRMC sentence parsing for low memory microcontrollers: read GPS date and time from UART

_NMEA GPS datetime for AVR.md

Date/time from GPS without storing NMEA string

This is a first pass at reading the date and time from a serial GPS device on a tiny microcontroller. The target device is an ATTiny13A with only 64 bytes of RAM, which isn't enough to store the full 79 characters of a NMEA sentence, so something like minmea wouldn't work (their API passes around full sentence strings).

When compiled with avr-gcc -Os, this is around 500 bytes of program space. The size can be reduced by 100 bytes if the handling of checksums is removed.

The test case can be compiled and run with:

gcc -std=gnu11 -D__flash="" testcase.c nmea.c -o test

The rest of this project is on Github as avr-doomclock). The code there is probably more up to date.

nmea.c

#include "nmea.h"

#include <stdbool.h>

enum GPRMCField {
    GPRMC_SentenceType = 0,
    GPRMC_Timestamp, // UTC of position fix
    GPRMC_Validity, // Data status (A=ok, V=navigation receiver warning)
    GPRMC_Latitude, // Latitude of fix
    GPRMC_Latitude_NorthSouth, // N or S
    GPRMC_Longitude, // Longitude of fix
    GPRMC_Longitude_EastWest, // E or W
    GPRMC_SpeedInKnots, // Speed over ground in knots
    GPRMC_TrueCourse, // Track made good in degrees True
    GPRMC_DateStamp, // UT date
    GPRMC_Variation, // Magnetic variation degrees (Easterly var. subtracts from true course)
    GPRMC_Variation_EastWest, // E or W
};

enum NmeaReadState {
    kSearchStart,
    kSkipSentence,
    kReadType,
    kReadFields,
    kChecksumVerify,
};

/**
 * Convert a two character hex string to a byte
 *
 * Note this assumes the input is a two character array, not a null terminated string.
 */
static inline uint8_t hex2int(char* hexPair)
{
    uint8_t val = 0;

    for (uint8_t i = 0; i < 2; ++i) {
        // Get current character then increment
        uint8_t byte = hexPair[i];

        // Transform hex character to the 4bit equivalent number, using the ascii table indexes
        if (byte >= '0' && byte <= '9') byte = byte - '0';
        else if (byte >= 'a' && byte <='f') byte = byte - 'a' + 10;
        else if (byte >= 'A' && byte <='F') byte = byte - 'A' + 10;

        // Shift 4 to make space for new digit, and add the 4 bits of the new digit
        val = (val << 4) | (byte & 0xF);
    }

    return val;
}

/**
 * Convert a two character numeric string to an 8-bit number
 *
 * Using this saves 50 bytes of program space over the stdlib implementation by
 * knowing that str has contains exactly two numeric characters (zero padded if one digit).
 * The AVR stdlib version also uses a 16-bit signed integer, which we don't need.
 */
static inline uint8_t gps_atoi(char *str)
{
    uint8_t result = 0;

    result = (result * 10) + str[0] - '0';
    result = (result * 10) + str[1] - '0';

    return result;
}

GpsReadStatus gps_read_time(DateTime* output)
{

    uint8_t calculatedChecksum = 0x0;

    // Buffer for storing number pairs read from the GPS
    char buffer[2];
    uint8_t bufIndex = 0;

    // Which field in the output is currently being written to
    uint8_t outputIndex = 0;

    // RMC sentence matching
    static const __flash char GPRMC[] = "GPRMC";
    uint8_t typeStrIndex = 0;

    enum NmeaReadState state = kSearchStart;
    enum GPRMCField field = GPRMC_SentenceType;

    // Flag to indicate the decimal portion of time is being skipped
    bool hitTimeDecimal = false;

    // Flag to indicate the date/time field was non-empty
    // During start-up the GPS can return blank fields while it aquires a signal
    bool sawTimeFields = false;

    // NMEA sentences are limited to 79 characters including the start '$' and end '\r\n'
    // Limit iterations to this for sanity
    for (uint8_t i = 79; i != 0; --i) {
        char byte = uart_read_byte();

        switch (state) {
            case kSearchStart: {
                // Bail out if end of line hit
                if (byte == '\n') {
                    return kGPS_NoMatch;
                }

                // Look for start character
                if (byte == '$') {
                    state = kReadType;
                    continue;
                }

                // Not the character we're looking for
                continue;
            }

            case kSkipSentence: {
                // Ignore all further bytes until the sentence ends
                if (byte != '\n') {
                    continue;
                }

                return kGPS_NoMatch;
            }

            case kReadType: {
                // Include sentence type in checksum
                calculatedChecksum ^= byte;

                // Try to match against sentence type we want
                if (byte == GPRMC[typeStrIndex]) {
                    if (typeStrIndex == 4) {
                        // Matched last character in the flag we want
                        state = kReadFields;
                    } else {
                        ++typeStrIndex;
                    }
                } else {
                    // Saw a '$' but the sentence type didn't match
                    // Ignore everything further in this message
                    state = kSkipSentence;
                }

                continue;
            }

            case kReadFields: {

                // Asterisk marks the end of the data and start of the checksum
                if (byte == '*') {
                    state = kChecksumVerify;
                    continue;
                }

                // Calculate checksum across sentence contents
                calculatedChecksum ^= byte;

                // Fields are delimited by commas
                if (byte == ',') {
                    ++field;
                    continue;
                }

                switch (field) {
                    case GPRMC_Timestamp: {

                        // Skip the fractional part of the timestamp field as we don't use it
                        // This isn't guaranteed to be present in every message
                        if (hitTimeDecimal || byte == '.') {
                            hitTimeDecimal = true;
                            continue;
                        }

                        // INTENTIONAL FALL THROUGH TO DATETIME
                    }

                    case GPRMC_DateStamp: {

                        // Collect pairs of characters and convert them to numbers
                        buffer[bufIndex] = byte;
                        bufIndex++;

                        if (bufIndex == 2) {
                            bufIndex = 0;
                            ((uint8_t*) output)[outputIndex] = gps_atoi(buffer);
                            ++outputIndex;
                        } else {
                            continue;
                        }

                        sawTimeFields = true;
                        continue;
                    }

                    default:
                        // Skip other fields
                        continue;
                }
            }

            case kChecksumVerify: {
                uint8_t receivedChecksum = 0x0;

                // Collect checksum
                buffer[bufIndex] = byte;
                bufIndex++;

                if (bufIndex == 2) {
                    receivedChecksum = hex2int(buffer);
                } else {
                    continue;
                }

                if (receivedChecksum == calculatedChecksum) {
                    if (sawTimeFields) {
                        return kGPS_Success;
                    } else {
                        return kGPS_NoSignal;
                    }
                } else {
                    return kGPS_InvalidChecksum;
                }
            }

            default:
                // Entered an unrecognised state: abort
                return kGPS_BadFormat;
        }
    }

    // Something has gone wrong
    // The loop ended, which means the sentence was longer than allowed by NMEA
    return kGPS_BadFormat;
}

nmea.h

#pragma once

#include <stdint.h>

typedef struct DateTime {
    uint8_t hour;
    uint8_t minute;
    uint8_t second;
    uint8_t day;
    uint8_t month;
    uint8_t year;
} __attribute__((packed)) DateTime;

typedef enum GpsReadStatus {
    // GPS date and time was successfully read into output parameter
    kGPS_Success = 0,

    // RMC sentence found, but it had no date/time information
    kGPS_NoSignal,

    // Partial sentence or unknown sentence type (this only supports RMC sentences)
    kGPS_NoMatch,

    // Time was read into output parameter, but the calculated checksum failed to match
    kGPS_InvalidChecksum,

    // The sentence had too many characters or fields and could not be parsed
    kGPS_BadFormat,
} GpsReadStatus;

/**
 * Grab a byte from the GPS device
 *
 * Provide your own implementation for this
 */
extern char uart_read_byte();

/**
 * Attempt to match GPRMC sentence in the output of uart_read_byte()
 *
 * The output parameter may be altered regardless of success/failure. In the case a non-success
 * status is returned, the struct should be considered in an invalid state
 */
GpsReadStatus gps_read_time(DateTime* output);

testcase.c

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>

#include "nmea.h"

static const char* currentSentence = NULL;
static int sentenceIdx = 0;

/**
 * Emulated uart for test cases
 */
char uart_read_byte()
{
    char out = currentSentence[sentenceIdx];

    if (out != '\0') {
        ++sentenceIdx;
    }

    return out;
}

// Define tests
typedef struct TestCase {
    const char* sentence;
    GpsReadStatus expectedStatus;
    DateTime expectedResult;
} TestCase;

static TestCase testcases[] = {
    {
        .sentence = "$GPRMC,081836,A,3751.65,S,14507.36,E,000.0,360.0,130998,011.3,E*62\r\n",
        .expectedStatus = kGPS_Success,
        .expectedResult = {
            .hour = 8,
            .minute = 18,
            .second = 36,
            .day = 13,
            .month = 9,
            .year = 98
        },
    },
    {
        .sentence = "$GPRMC,220516,A,5133.82,N,00042.24,W,173.8,231.8,130694,004.2,W*70\r\n",
        .expectedStatus = kGPS_Success,
        .expectedResult = {
            .hour = 22,
            .minute = 5,
            .second = 16,
            .day = 13,
            .month = 6,
            .year = 94
        },
    },
    {
        .sentence = "$GPRMC,091502.00,V,,,,,,,040219,,,N*7C\r\n",
        .expectedStatus = kGPS_Success,
        .expectedResult = {
            .hour = 9,
            .minute = 15,
            .second = 2,
            .day = 4,
            .month = 2,
            .year = 19
        },
    },
    {
        .sentence = "$GPRMC,220516,A,5133.82,N,00042.24,W,173.8,231.8,130694,004.2,W*14\r\n",
        .expectedStatus = kGPS_InvalidChecksum,
    },

    // Unknown sentences
    {
        .sentence = "$GPRMB,A,4.08,L,EGLL,EGLM,5130.02,N,00046.34,W,004.6,213.9,122.9,A*3D\r\n",
        .expectedStatus = kGPS_NoMatch,
    },
    {
        .sentence = "$GPGSV,3,1,11,03,03,111,00,04,15,270,00,06,01,010,00,13,06,292,00*74\r\n",
        .expectedStatus = kGPS_NoMatch,
    },
    {
        .sentence = "$GPRMA,A,llll.ll,N,lllll.ll,W,,,ss.s,ccc,vv.v,W*hh\r\n",
        .expectedStatus = kGPS_NoMatch,
    },

    // Junk values
    {
        // Test rejection of an endless bogus message (filled with nulls by gps_read_byte())
        .sentence = "[something very unexpected]",
        .expectedStatus = kGPS_BadFormat,
    },
    {
        // Test something that looks like the right sentence is rejected when not formatted as expected
        .sentence = "$GPRMC,but,not,really\r\n",
        .expectedStatus = kGPS_BadFormat,
    },
};

/**
 * Map status numbers to names
 */
static char* statusToString[] = {
    "kGPS_Success",
    "kGPS_NoSignal",
    "kGPS_NoMatch",
    "kGPS_InvalidChecksum",
    "kGPS_BadFormat",
};

int main()
{
    bool didFail = false;

    for (int i = 0; i < (sizeof(testcases) / sizeof(testcases[0])); i++) {
        TestCase test = testcases[i];

        printf("\nTesting sentence:\n    %s", test.sentence);

        currentSentence = test.sentence;
        sentenceIdx = 0;

        DateTime output = {0, 0, 0, 0, 0, 0};
        GpsReadStatus status = gps_read_time(&output);

        // Test return value matches expected value
        if (status != test.expectedStatus) {
            printf(
                "        --> Test failed: Returned %s when %s expected\n",
                statusToString[status],
                statusToString[test.expectedStatus]
            );
            didFail = true;
            continue;
        }

        // Test the output matches the expected date and time
        if (test.expectedStatus == kGPS_Success) {
            bool outputMatches = true;
            for (int i = 0; i < sizeof(DateTime); i++) {
                if ( ((uint8_t*) &output)[i] != ((uint8_t*) &(test.expectedResult))[i] ) {
                    outputMatches = false;
                    break;
                }
            }

            if (!outputMatches) {
                printf("        --> Test failed: result (");

                for (int i = 0; i < sizeof(DateTime); i++) {
                    printf("%d ", ((uint8_t*) &output)[i]);
                }

                printf(") did not match expected value.\n");

                didFail = true;
            }
        }
    }

    return didFail;
}