ESP32 library for offline time zone search with given GPS coordinates

In an article three months ago, I described how to use GPS coordinates to find the time zone and thus set the correct time. In the meantime, however, I hardly work with the Raspberry anymore, but use an ESP32 microcontroller for my projects. This is quite easy with the Raspberry, as there exists a library for it. Unfortunately I haven't found anything comparable for the ESP32. Therefore I had to write my own library, which I would like to present here.

The problem

Especially in the microcontroller area it can happen that you need the exact time without a possibility to get it by input or network. A simple option is the GPS signal, with which not only the position can be determined, but also the exact time is transmitted. However, this is UTC time. To determine the local time, you need the time zone you are in. This gives you the time difference to UTC time including the local rules for daylight saving time.

This image from Wikipedia gives an overview of the world's time zones:

For a general solution you need the outlines of all countries and the corresponding name of the time zone. The country and consequently the time zone can then be determined via the GPS coordinates. 

The time zones database

Fortunately, such a database already exists. Evan Siroky has developed the tool timezone-boundary-builder, which generates a database based on the data of OpenStreetMap, in which all countries of the world are stored as polygons. The current version can be downloaded from GitHub. The database is based on the shapefile format and is about 100 MB in size. For a microcontroller, this is a considerable size. There would be the option to store the database on a SD card, but then I would still need software to be able to read the shapefile format with the microcontroller. 

I have therefore decided on a different variant. My goal was to compress the database enough to fit on a 128 MBit W25Q128 SPI Flash chip. In addition, the database format should be as simple as possible so that the programming effort for the ESP32 is not too high.

The generation of the time zone database is done by a Java program. For reading the shapefile I use an open source library from GeoTools. The compression of the data is kept very simple, but it is enough to bring the data to less than 16 MB. In addition a small statistic of the data:

The compression itself consists of several parts

1. A coordinate consists of longitude and latitude in floating point format. These coordinates are converted to an integer using a function, where a parameter can be used to specify how many bits this number should have. This corresponds to a rounding to a certain number of decimal places.
2. Due to rounding, consecutive coordinates may have the same value. These coordinates are ignored.
3. The exact value of a coordinate only needs to be stored for the first value of a polygon. For the other values, the delta to the previous value is sufficient.
4. The values of the deltas are significantly smaller than the original coordinates. Only as many bytes are used for storage as the value actually needs. The distribution of the deltas looks like this:

   x < 256	10.460.006
   256 <= x < 65536	1.619.509
   x >= 65536	1095

   So according to the amounts it is sufficient to use only one byte, two bytes or 4 bytes each. 

With these simple measures, the size of the database shrinks to 15.4 MB and thus fits easily on the flash chip.

The structure of the database is optimized to be read by the microcontroller very easily and without large memory requirements:

The time zones are sorted by size. Thus, also such cases are found correctly where a country lies within another country. An example is the Vatican, which is located within Italy. A corresponding coordinate would then provide two countries. But since the Vatican is sorted before Italy, it will be found first. 

Before generating the database, the shapefile must be downloaded. This is done with the maven goal download:wget. Then just start the main class. The output file is stored in the target directory under target/classes/output/

The source code of the generator is on GitHub: https://github.com/HarryVienna/ESP32-Timezone-Database-Generator

ESP32 Component

Hardware

The data with the time zones are too large to be saved directly on the ESP32 module. Therefore, the data is stored on an external Winbond W25Q128 SPI Flash chip, which is connected to the ESP32's SPI3 (also called VSPI) controller.

The generated database is saved to the flash chip with this command:

esptool.py --chip esp32 write_flash --flash_mode dio --spi-connection 18,19,23,21,5 0x0000 timezones.bin

This process may take a few minutes. If only a 64 MBit flash chip is available, you can reduce the precision parameter in the generator. With a value of 18 the generated file is only 7.5 MB in size. Of course then the accuracy of the data is lower.  

Software

In order to be able to access the flash chip, the SPI interface must first be initialized and a partition set up. The API is fairly well described on the Espressif website. The code for this looks like this:

const spi_bus_config_t bus_config = {
        .mosi_io_num = w25q128->config.mosi_io_num,
        .miso_io_num = w25q128->config.miso_io_num,
        .sclk_io_num = w25q128->config.sclk_io_num,
        .quadwp_io_num = -1,
        .quadhd_io_num = -1,
    };

    const esp_flash_spi_device_config_t device_config = {
        .host_id =  w25q128->config.host_id,
        .cs_id = 0,
        .cs_io_num = w25q128->config.cs_io_num,
        .io_mode = w25q128->config.io_mode,
        .speed = w25q128->config.speed
    };

    // Initialize the SPI bus
    ret = spi_bus_initialize(SPI3_HOST, &bus_config, SPI_DMA_CH_AUTO);
    if (ret != ESP_OK) {
        ESP_LOGE(TAG, "Failed to initialize SPI bus: %s (0x%x)", esp_err_to_name(ret), ret);
        return ret;
    }

    // Add device to the SPI bus
    esp_flash_t* ext_flash;
    ret = spi_bus_add_flash_device(&ext_flash, &device_config);
    if (ret != ESP_OK) {
        ESP_LOGE(TAG, "Failed to add Flash: %s (0x%x)", esp_err_to_name(ret), ret);
        return ret;
    }

    // Probe the Flash chip and initialize it
    ret = esp_flash_init(ext_flash);
    if (ret != ESP_OK) {
        ESP_LOGE(TAG, "Failed to initialize external Flash: %s (0x%x)", esp_err_to_name(ret), ret);
        return ret;
    }

    // Print out the ID and size
    uint32_t id;
    ret = esp_flash_read_id(ext_flash, &id);
    if (ret != ESP_OK) {
        ESP_LOGE(TAG, "Failed to read id: %s (0x%x)", esp_err_to_name(ret), ret);
        return ret;
    }
    ESP_LOGI(TAG, "Initialized external Flash, size=%d KB, ID=0x%x", ext_flash->size / 1024, id);

    const char *partition_label = "storage";
    ESP_LOGI(TAG, "Adding external Flash as a partition, label=\"%s\", size=%d KB", partition_label, ext_flash->size / 1024);

    ret = esp_partition_register_external(ext_flash, 0, ext_flash->size, partition_label, ESP_PARTITION_TYPE_DATA, ESP_PARTITION_SUBTYPE_DATA_FAT, &w25q128->partition);
     if (ret != ESP_OK) {
        ESP_LOGE(TAG, "Failed to register external partition: %s (0x%x)", esp_err_to_name(ret), ret);
        return ret;
    }

The data on the flash chip can now be accessed via the pointer to the partition. The most important function for this is

esp_err_t esp_partition_read(const esp_partition_t* partition, size_t src_offset, void* dst, size_t size);

To search the time zone, the structure of the database is read and searched country by country. To increase the speed, a rectangle with the minimum and maximum values of the longitude and latitude is stored for each country. If the point is not within this rectangle, it is possible to continue immediately with the next country. The core function is the so-called Ray casting algorithm, which can be used to determine whether a point lies within a polygon. Since this function processes the data only sequentially, the RAM requirement of the function is very small and thus no problem for a microcontroller.

p1.latitude = start_point.latitude;
p1.longitude = start_point.longitude;

p2.latitude = start_point.latitude;
p2.longitude = start_point.longitude;

double x_inters;
bool odd = false;

for (int k = 0; k < deltas; k++) {
    p2.latitude += next_value(partition, &shape_position);
    p2.longitude += next_value(partition, &shape_position);

    // y must be between min and max of the line
    if (latitude_int > MIN(p1.latitude, p2.latitude) && latitude_int <= MAX(p1.latitude, p2.latitude)) {
        // x must be less than or equal to the greater x value of the line
        if (longitude_int <= MAX(p1.longitude, p2.longitude)) {
            // Horizontal line is ignored because it is already counted at the endpoint of another line.
            if (p1.latitude != p2.latitude) {
                // Equation of a straight line solved for x  
                x_inters = (latitude_int-p1.latitude) * (p2.longitude-p1.longitude) / (p2.latitude-p1.latitude) + p1.longitude;
                if (longitude_int <= x_inters) {
                    odd = !odd;
                }
            }
        }

    }
    p1 = p2;
}

return odd;

For example, an output from the search function for a coordinate in Austria looks like this:

I (9567) w25q128: Timezone Database info: Version: 1   Signature: TZDB   Precision: 24   Creation Date 2022-01-13
I (9572) w25q128: Search Latitude: 47.497700 4427106
I (9578) w25q128:        Longitude: 9.947400 463582
I (9583) w25q128: Entries in TOC: 426
I (9595) w25q128: Inside Bounding Box
I (11259) w25q128: Inside Bounding Box
I (11499) w25q128: Crossed line P1: 47.497696 10.870113   P2: 47.497650 10.870092
I (11980) w25q128: Crossed line P1: 47.497597 11.412392   P2: 47.497715 11.412327
I (12406) w25q128: Crossed line P1: 47.498562 12.906361   P2: 47.496944 12.908721
I (12425) w25q128: Crossed line P1: 47.496418 13.048067   P2: 47.498146 13.048282
I (14309) w25q128: Crossed line P1: 47.497757 16.653557   P2: 47.496845 16.653986
I (17213) w25q128: Crossed line P1: 47.497715 9.988052   P2: 47.497051 9.988675
I (17586) w25q128: Crossed line P1: 47.497555 10.434566   P2: 47.497986 10.434458
I (17601) w25q128: Inside timezone: Europe/Vienna
I (17601) test: 8034.229000 milliseconds

The complete source code of this component for determining the time zone is on GitHub: https://github.com/HarryVienna/ESP32-Timezone-Finder-Component.

Performance

The speed of the search mainly depends on the number of points of the respective country. In my tests, the values are between 47 ms and 8000 ms. The database had an accuracy of 24 bits. Of course, if you reduce the accuracy, the speed also increases.

An interesting detail about the number of points per country is which country has the most points. I would have guessed one of the really big countries like China, Russia or the USA. In fact, it is Germany with over 150,000 points. Whether that has something to do with the thoroughness of the Germans, I can't say :)