libextractor

gpx_extractor.c (42554B)

---

 /*
      This file is part of libextractor.
      Copyright (C) 2026 Vidyut Samanta and Christian Grothoff
 
      libextractor is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published
      by the Free Software Foundation; either version 3, or (at your
      option) any later version.
 
      libextractor is distributed in the hope that it will be useful, but
      WITHOUT ANY WARRANTY; without even the implied warranty of
      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      General Public License for more details.
 
      You should have received a copy of the GNU General Public License
      along with libextractor; see the file COPYING.  If not, write to the
      Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
      Boston, MA 02110-1301, USA.
  */
 /**
  * @file plugins/gpx_extractor.c
  * @brief plugin to support GPX (GPS Exchange Format) track logs
  * @author Christian Grothoff
  *
  * GPX is raw location history: where a device was, when, and -- through
  * the `creator' attribute -- which device or application recorded it.
  * That makes the header of a GPX file one of the more identifying things
  * a volume can contain, which is why this plugin exists.
  *
  * This is deliberately *not* an XML parser.  libextractor has no XML
  * dependency and this plugin must stay unconditional, so what follows is
  * a bounded, single-pass scanner over at most #GPX_SCAN_CAP bytes.  Its
  * limits, stated once here rather than repeated at every call site:
  *
  * - Comments (`<!-- ... -->') and processing instructions are not
  *   skipped, so an element name that only occurs inside a comment is
  *   still seen.  For the fields below that means a false positive, never
  *   an out-of-bounds read.
  * - CDATA is recognised only when it opens the content of an element
  *   whose text we ask for; a CDATA section in the middle of mixed
  *   content is treated as markup.
  * - Only the five predefined entities and numeric character references
  *   are expanded; a document-defined entity is passed through verbatim.
  * - Element content is the run of text up to the next `<'; nested
  *   elements inside a value are not concatenated.
  * - Namespace prefixes are skipped, so `<gpx:name>' and `<name>' are the
  *   same element here.  A document that binds a prefix to some *other*
  *   namespace would be misread; GPX files in the wild do not.
  * - Attribute values are read as raw text; the scanner does not care
  *   whether a document is well-formed.
  *
  * None of that can make the scanner read outside the buffer or fail to
  * make forward progress: every loop below is bounded by the buffer
  * length and advances at least one byte per iteration.
  */
 #include "platform.h"
 #include "extractor.h"
 #include "forensics.h"
 
 #include <math.h>
 
 
 /**
  * How many bytes of the file we are willing to look at.  GPX track logs
  * routinely run to tens of megabytes; a first pass over a volume must
  * not read all of that.  Counts derived from a truncated scan are
  * reported as lower bounds, with a comment saying so.
  */
 #define GPX_SCAN_CAP (1024 * 1024)
 
 /**
  * Longest start tag we will scan for its closing `>'.  Keeps a file made
  * of one unterminated tag from turning the per-element work into a scan
  * of the whole buffer.
  */
 #define GPX_MAX_TAG 8192
 
 /**
  * Longest element text content we will look at.
  */
 #define GPX_MAX_TEXT 4096
 
 /**
  * How far into the file the `<gpx' element has to appear.
  */
 #define GPX_MAGIC_WINDOW 2048
 
 /**
  * Most attributes we parse out of a single start tag.
  */
 #define GPX_MAX_ATTRS 64
 
 /**
  * Mean Earth radius in metres, as used for the haversine sum.
  */
 #define GPX_EARTH_RADIUS 6371000.0
 
 
 /**
  * Everything we picked up while walking the track points.
  */
 struct GpxScan
 {
   /**
    * Bounding box of the points seen, west/south/east/north.
    */
   double minlon;
   double minlat;
   double maxlon;
   double maxlat;
 
   /**
    * Coordinates of the first point, which is where the recording
    * started.
    */
   double first_lat;
   double first_lon;
 
   /**
    * Elevation range seen inside track points.
    */
   double minele;
   double maxele;
 
   /**
    * Sum of the great-circle distances between consecutive track points.
    */
   double distance;
 
   /**
    * Latitude/longitude of the previous track point, for @e distance.
    */
   double prev_lat;
   double prev_lon;
 
   /**
    * First and last timestamp seen inside a track point.
    */
   int64_t first_time;
   int64_t last_time;
 
   /**
    * Number of `<trkpt>', `<wpt>' and `<rtept>' elements.
    */
   uint64_t trkpts;
   uint64_t wpts;
   uint64_t rtepts;
 
   /**
    * Non-zero once at least one point of any kind was seen; before that
    * an `<ele>' or `<time>' belongs to the metadata, not to a point.
    */
   int seen_point;
 
   /**
    * Non-zero once #prev_lat / #prev_lon hold a track point.
    */
   int have_prev;
 
   /**
    * Non-zero once the bounding box fields are meaningful.
    */
   int have_bbox;
 
   /**
    * Non-zero once the elevation range fields are meaningful.
    */
   int have_ele;
 };
 
 
 /**
  * Can @a c appear in an XML name (after the first character)?
  *
  * @param c character to test
  * @return 1 if @a c is a name character, 0 if not
  */
 static int
 gpx_name_char (char c)
 {
   return ( ( ('a' <= c) && ('z' >= c) ) ||
            ( ('A' <= c) && ('Z' >= c) ) ||
            ( ('0' <= c) && ('9' >= c) ) ||
            ('_' == c) || ('-' == c) || ('.' == c) );
 }
 
 
 /**
  * Is the element that starts at @a pos named @a tag?
  *
  * A namespace prefix is skipped, so `<gpx:name' matches "name".
  *
  * @param buf the buffer
  * @param len number of bytes in @a buf
  * @param pos offset of the `<'
  * @param tag element name to compare against
  * @return 1 on a match, 0 otherwise
  */
 static int
 gpx_tag_is (const char *buf,
             size_t len,
             size_t pos,
             const char *tag)
 {
   size_t i;
   size_t start;
   size_t tlen = strlen (tag);
 
   if ( (pos >= len) ||
        ('<' != buf[pos]) )
     return 0;
   i = pos + 1;
   start = i;
   while ( (i < len) &&
           (i - start < 64) &&
           gpx_name_char (buf[i]) )
     i++;
   if ( (i < len) &&
        (':' == buf[i]) )
   {
     i++;
     start = i;
     while ( (i < len) &&
             (i - start < 64) &&
             gpx_name_char (buf[i]) )
       i++;
   }
   if (i - start != tlen)
     return 0;
   return (0 == memcmp (&buf[start],
                        tag,
                        tlen));
 }
 
 
 /**
  * Find the `>' that closes the start tag beginning at @a pos.  Quoted
  * attribute values may contain `>', so quoting is tracked.
  *
  * @param buf the buffer
  * @param len number of bytes in @a buf
  * @param pos offset of the `<'
  * @return offset of the `>', or `(size_t) -1' if there is none within
  *         #GPX_MAX_TAG bytes
  */
 static size_t
 gpx_tag_end (const char *buf,
              size_t len,
              size_t pos)
 {
   char quote = 0;
 
   for (size_t i = pos; (i < len) && (i - pos < GPX_MAX_TAG); i++)
   {
     char c = buf[i];
 
     if (0 != quote)
     {
       if (c == quote)
         quote = 0;
       continue;
     }
     if ( ('"' == c) ||
          ('\'' == c) )
     {
       quote = c;
       continue;
     }
     if ('>' == c)
       return i;
   }
   return (size_t) -1;
 }
 
 
 /**
  * Find the value of attribute @a name in the start tag at @a pos.
  *
  * @param buf the buffer
  * @param len number of bytes in @a buf
  * @param pos offset of the `<'
  * @param name attribute name, without a namespace prefix
  * @param[out] vstart offset of the first byte of the value
  * @param[out] vlen number of bytes in the value
  * @return 1 if the attribute was found, 0 if not
  */
 static int
 gpx_attr (const char *buf,
           size_t len,
           size_t pos,
           const char *name,
           size_t *vstart,
           size_t *vlen)
 {
   size_t end = gpx_tag_end (buf,
                             len,
                             pos);
   size_t i;
   size_t nlen = strlen (name);
 
   if (((size_t) -1) == end)
     return 0;
   i = pos + 1;
   while ( (i < end) &&
           (gpx_name_char (buf[i]) ||
            (':' == buf[i]) ) )
     i++;
   for (unsigned int n = 0; n < GPX_MAX_ATTRS; n++)
   {
     size_t astart;
     size_t alen;
     size_t vs;
     size_t ve;
     char quote;
 
     while ( (i < end) &&
             ( (' ' == buf[i]) || ('\t' == buf[i]) ||
               ('\r' == buf[i]) || ('\n' == buf[i]) ) )
       i++;
     if (i >= end)
       break;
     astart = i;
     while ( (i < end) &&
             (gpx_name_char (buf[i]) ||
              (':' == buf[i]) ) )
       i++;
     if (i == astart)
     {
       i++;         /* not a name: skip a byte so we always progress */
       continue;
     }
     alen = i - astart;
     /* a prefixed attribute matches on its local part */
     for (size_t k = 0; k < alen; k++)
       if (':' == buf[astart + k])
       {
         astart += k + 1;
         alen -= k + 1;
         break;
       }
     while ( (i < end) &&
             ( (' ' == buf[i]) || ('\t' == buf[i]) ||
               ('\r' == buf[i]) || ('\n' == buf[i]) ) )
       i++;
     if ( (i >= end) ||
          ('=' != buf[i]) )
       continue;    /* valueless attribute; i already advanced past a name */
     i++;
     while ( (i < end) &&
             ( (' ' == buf[i]) || ('\t' == buf[i]) ||
               ('\r' == buf[i]) || ('\n' == buf[i]) ) )
       i++;
     if (i >= end)
       break;
     quote = buf[i];
     if ( ('"' == quote) ||
          ('\'' == quote) )
     {
       i++;
       vs = i;
       while ( (i < end) &&
               (quote != buf[i]) )
         i++;
       ve = i;
       if (i < end)
         i++;
     }
     else
     {
       vs = i;
       while ( (i < end) &&
               (' ' != buf[i]) && ('\t' != buf[i]) &&
               ('\r' != buf[i]) && ('\n' != buf[i]) &&
               ('/' != buf[i]) )
         i++;
       ve = i;
     }
     if ( (alen == nlen) &&
          (0 == memcmp (&buf[astart],
                        name,
                        nlen)) )
     {
       *vstart = vs;
       *vlen = ve - vs;
       return 1;
     }
   }
   return 0;
 }
 
 
 /**
  * Text content of the element whose start tag begins at @a pos.
  *
  * @param buf the buffer
  * @param len number of bytes in @a buf
  * @param pos offset of the `<'
  * @param[out] tstart offset of the first content byte
  * @param[out] tlen number of content bytes
  * @return 1 if content was found, 0 if the element is empty or the tag
  *         is malformed
  */
 static int
 gpx_text (const char *buf,
           size_t len,
           size_t pos,
           size_t *tstart,
           size_t *tlen)
 {
   size_t end = gpx_tag_end (buf,
                             len,
                             pos);
   size_t i;
   size_t j;
 
   if (((size_t) -1) == end)
     return 0;
   if ( (end > pos) &&
        ('/' == buf[end - 1]) )
     return 0;   /* self-closing element, no content */
   i = end + 1;
   if ( (i + 9 <= len) &&
        (0 == memcmp (&buf[i],
                      "<![CDATA[",
                      9)) )
   {
     j = i + 9;
     while ( (j + 3 <= len) &&
             (j - i < GPX_MAX_TEXT) )
     {
       if (0 == memcmp (&buf[j],
                        "]]>",
                        3))
       {
         *tstart = i + 9;
         *tlen = j - (i + 9);
         return 1;
       }
       j++;
     }
     return 0;
   }
   j = i;
   while ( (j < len) &&
           ('<' != buf[j]) &&
           (j - i < GPX_MAX_TEXT) )
     j++;
   *tstart = i;
   *tlen = j - i;
   return (0 != *tlen);
 }
 
 
 /**
  * Find the next element named @a tag at or after @a from, staying below
  * @a limit.
  *
  * @param buf the buffer
  * @param limit offset one past the last byte to search
  * @param from where to start searching
  * @param tag element name
  * @return offset of the `<', or `(size_t) -1' if not found
  */
 static size_t
 gpx_find (const char *buf,
           size_t limit,
           size_t from,
           const char *tag)
 {
   for (size_t i = from; i < limit; i++)
   {
     if ('<' != buf[i])
       continue;
     if (gpx_tag_is (buf,
                     limit,
                     i,
                     tag))
       return i;
   }
   return (size_t) -1;
 }
 
 
 /**
  * Expand the five predefined XML entities and numeric character
  * references in @a in.  Anything else is copied through unchanged.
  *
  * @param in input text
  * @param inlen number of bytes in @a in
  * @param[out] out where to write the result
  * @param outsize number of bytes available in @a out
  * @return number of bytes written to @a out
  */
 static size_t
 gpx_unescape (const char *in,
               size_t inlen,
               char *out,
               size_t outsize)
 {
   size_t o = 0;
   size_t i = 0;
 
   while ( (i < inlen) &&
           (o + 5 < outsize) )
   {
     size_t j;
     uint32_t cp = 0;
 
     if ('&' != in[i])
     {
       out[o++] = in[i++];
       continue;
     }
     /* find the terminating `;' within a short window */
     j = i + 1;
     while ( (j < inlen) &&
             (j - i < 12) &&
             (';' != in[j]) )
       j++;
     if ( (j >= inlen) ||
          (';' != in[j]) )
     {
       out[o++] = in[i++];
       continue;
     }
     /* j is the offset of the `;', so the reference is j + 1 - i bytes */
     if ( (4 == j + 1 - i) &&
          (0 == memcmp (&in[i], "&lt;", 4)) )
       cp = '<';
     else if ( (4 == j + 1 - i) &&
               (0 == memcmp (&in[i], "&gt;", 4)) )
       cp = '>';
     else if ( (5 == j + 1 - i) &&
               (0 == memcmp (&in[i], "&amp;", 5)) )
       cp = '&';
     else if ( (6 == j + 1 - i) &&
               (0 == memcmp (&in[i], "&quot;", 6)) )
       cp = '"';
     else if ( (6 == j + 1 - i) &&
               (0 == memcmp (&in[i], "&apos;", 6)) )
       cp = '\'';
     else if ( (j - i > 2) &&
               ('#' == in[i + 1]) )
     {
       size_t k = i + 2;
       int base = 10;
 
       if ( (k < j) &&
            ( ('x' == in[k]) || ('X' == in[k]) ) )
       {
         base = 16;
         k++;
       }
       if (k == j)
       {
         out[o++] = in[i++];
         continue;
       }
       while (k < j)
       {
         int d;
 
         if ( ('0' <= in[k]) && ('9' >= in[k]) )
           d = in[k] - '0';
         else if ( (16 == base) && ('a' <= in[k]) && ('f' >= in[k]) )
           d = in[k] - 'a' + 10;
         else if ( (16 == base) && ('A' <= in[k]) && ('F' >= in[k]) )
           d = in[k] - 'A' + 10;
         else
           break;
         if (cp > 0x110000 / (uint32_t) base)
         {
           cp = 0;
           break;
         }
         cp = cp * (uint32_t) base + (uint32_t) d;
         k++;
       }
       if ( (k != j) ||
            (0 == cp) ||
            (cp > 0x10FFFF) ||
            ( (0xD800 <= cp) && (0xDFFF >= cp) ) )
       {
         out[o++] = in[i++];
         continue;
       }
     }
     else
     {
       out[o++] = in[i++];
       continue;   /* unknown entity: leave it alone */
     }
     if (cp < 0x80)
     {
       out[o++] = (char) cp;
     }
     else if (cp < 0x800)
     {
       out[o++] = (char) (0xC0 | (cp >> 6));
       out[o++] = (char) (0x80 | (cp & 0x3F));
     }
     else if (cp < 0x10000)
     {
       out[o++] = (char) (0xE0 | (cp >> 12));
       out[o++] = (char) (0x80 | ((cp >> 6) & 0x3F));
       out[o++] = (char) (0x80 | (cp & 0x3F));
     }
     else
     {
       out[o++] = (char) (0xF0 | (cp >> 18));
       out[o++] = (char) (0x80 | ((cp >> 12) & 0x3F));
       out[o++] = (char) (0x80 | ((cp >> 6) & 0x3F));
       out[o++] = (char) (0x80 | (cp & 0x3F));
     }
     i = j + 1;
   }
   return o;
 }
 
 
 /**
  * Emit a stretch of XML text after expanding entity references.
  *
  * @param ec extraction context
  * @param type meta data type
  * @param data the text
  * @param len number of bytes in @a data
  * @return 1 if the caller should stop extracting, 0 to continue
  */
 static int
 gpx_emit_xml (struct EXTRACTOR_ExtractContext *ec,
               enum EXTRACTOR_MetaType type,
               const char *data,
               size_t len)
 {
   char buf[EXTRACTOR_FORENSIC_MAX_STRING];
   size_t out;
 
   if (len > sizeof (buf) - 8)
     len = sizeof (buf) - 8;
   out = gpx_unescape (data,
                       len,
                       buf,
                       sizeof (buf));
   return EXTRACTOR_forensic_emit_text_ (ec,
                                         "gpx",
                                         type,
                                         buf,
                                         out);
 }
 
 
 /**
  * Parse a decimal number out of a stretch of bytes that is not
  * NUL-terminated.
  *
  * @param data the bytes
  * @param len number of bytes in @a data
  * @param[out] value where to store the result
  * @return 1 on success, 0 if @a data does not start with a number
  */
 static int
 gpx_parse_double (const char *data,
                   size_t len,
                   double *value)
 {
   char tmp[64];
   char *endp;
   double v;
   size_t i = 0;
   size_t o = 0;
 
   while ( (i < len) &&
           ( (' ' == data[i]) || ('\t' == data[i]) ||
             ('\r' == data[i]) || ('\n' == data[i]) ) )
     i++;
   while ( (i < len) &&
           (o < sizeof (tmp) - 1) &&
           ( ( ('0' <= data[i]) && ('9' >= data[i]) ) ||
             ('+' == data[i]) || ('-' == data[i]) ||
             ('.' == data[i]) || ('e' == data[i]) || ('E' == data[i]) ) )
     tmp[o++] = data[i++];
   tmp[o] = '\0';
   if (0 == o)
     return 0;
   v = strtod (tmp,
               &endp);
   if ( (endp == tmp) ||
        (! isfinite (v)) )
     return 0;
   *value = v;
   return 1;
 }
 
 
 /**
  * Days since 1970-01-01 for a proleptic Gregorian date.  (Howard
  * Hinnant's `days_from_civil'.)
  *
  * @param y year
  * @param m month, 1-12
  * @param d day of month, 1-31
  * @return day number, negative before the epoch
  */
 static int64_t
 gpx_days_from_civil (int64_t y,
                      int64_t m,
                      int64_t d)
 {
   int64_t era;
   int64_t yoe;
   int64_t doy;
   int64_t doe;
 
   y -= (m <= 2);
   era = (y >= 0 ? y : y - 399) / 400;
   yoe = y - era * 400;
   doy = (153 * (m + (m > 2 ? -3 : 9)) + 2) / 5 + d - 1;
   doe = yoe * 365 + yoe / 4 - yoe / 100 + doy;
   return era * 146097 + doe - 719468;
 }
 
 
 /**
  * Parse an ISO 8601 timestamp as GPX writes it:
  * `YYYY-MM-DDThh:mm:ss[.fff][Z|(+|-)hh[:mm]]'.  A missing zone is taken
  * as UTC, which is what the GPX schema requires anyway.
  *
  * @param s the text
  * @param len number of bytes in @a s
  * @param[out] when where to store seconds since the Unix epoch
  * @return 1 on success, 0 if @a s is not a timestamp
  */
 static int
 gpx_parse_iso8601 (const char *s,
                    size_t len,
                    int64_t *when)
 {
   int64_t v[6] = { 0, 0, 0, 0, 0, 0 };
   static const size_t widths[6] = { 4, 2, 2, 2, 2, 2 };
   static const char seps[5] = { '-', '-', 'T', ':', ':' };
   size_t i = 0;
   int64_t off = 0;
 
   while ( (i < len) &&
           ( (' ' == s[i]) || ('\t' == s[i]) ||
             ('\r' == s[i]) || ('\n' == s[i]) ) )
     i++;
   for (unsigned int f = 0; f < 6; f++)
   {
     if (i + widths[f] > len)
       return 0;
     for (size_t k = 0; k < widths[f]; k++)
     {
       if ( ('0' > s[i + k]) ||
            ('9' < s[i + k]) )
         return 0;
       v[f] = v[f] * 10 + (s[i + k] - '0');
     }
     i += widths[f];
     if (f < 5)
     {
       if (i >= len)
         return 0;
       if ( (2 == f) &&
            (' ' == s[i]) )
         i++;   /* `YYYY-MM-DD hh:mm:ss' also occurs */
       else if (seps[f] == s[i])
         i++;
       else
         return 0;
     }
   }
   if ( (v[1] < 1) || (v[1] > 12) ||
        (v[2] < 1) || (v[2] > 31) ||
        (v[3] > 23) || (v[4] > 59) || (v[5] > 60) )
     return 0;
   if ( (i < len) &&
        ('.' == s[i]) )
   {
     i++;
     while ( (i < len) &&
             ('0' <= s[i]) && ('9' >= s[i]) )
       i++;
   }
   if ( (i < len) &&
        ( ('+' == s[i]) || ('-' == s[i]) ) )
   {
     int neg = ('-' == s[i]);
     int64_t oh = 0;
     int64_t om = 0;
 
     i++;
     if (i + 2 > len)
       return 0;
     for (size_t k = 0; k < 2; k++)
     {
       if ( ('0' > s[i + k]) || ('9' < s[i + k]) )
         return 0;
       oh = oh * 10 + (s[i + k] - '0');
     }
     i += 2;
     if ( (i < len) &&
          (':' == s[i]) )
       i++;
     if (i + 2 <= len)
     {
       if ( ('0' <= s[i]) && ('9' >= s[i]) &&
            ('0' <= s[i + 1]) && ('9' >= s[i + 1]) )
       {
         om = (s[i] - '0') * 10 + (s[i + 1] - '0');
         i += 2;
       }
     }
     if ( (oh > 23) || (om > 59) )
       return 0;
     off = oh * 3600 + om * 60;
     if (neg)
       off = -off;
   }
   *when = gpx_days_from_civil (v[0],
                                v[1],
                                v[2]) * 86400
           + v[3] * 3600 + v[4] * 60 + v[5]
           - off;
   return 1;
 }
 
 
 /**
  * Great-circle distance between two points, in metres.
  *
  * @param lat1 latitude of the first point, in degrees
  * @param lon1 longitude of the first point, in degrees
  * @param lat2 latitude of the second point, in degrees
  * @param lon2 longitude of the second point, in degrees
  * @return distance in metres
  */
 static double
 gpx_haversine (double lat1,
                double lon1,
                double lat2,
                double lon2)
 {
   double rad = M_PI / 180.0;
   double dlat = (lat2 - lat1) * rad;
   double dlon = (lon2 - lon1) * rad;
   double a;
 
   a = sin (dlat / 2.0) * sin (dlat / 2.0)
       + cos (lat1 * rad) * cos (lat2 * rad)
       * sin (dlon / 2.0) * sin (dlon / 2.0);
   if (a < 0.0)
     a = 0.0;
   if (a > 1.0)
     a = 1.0;
   return 2.0 * GPX_EARTH_RADIUS * asin (sqrt (a));
 }
 
 
 /**
  * Record a point of any kind in @a sc.
  *
  * @param sc scan state
  * @param lat latitude in degrees
  * @param lon longitude in degrees
  * @param track 1 if this is a `<trkpt>' (which also feeds the distance
  *        sum), 0 for a waypoint or route point
  */
 static void
 gpx_note_point (struct GpxScan *sc,
                 double lat,
                 double lon,
                 int track)
 {
   if ( (lat < -90.0) || (lat > 90.0) ||
        (lon < -180.0) || (lon > 180.0) )
     return;   /* out of range: not a coordinate, do not let it skew the box */
   if (! sc->have_bbox)
   {
     sc->minlat = sc->maxlat = lat;
     sc->minlon = sc->maxlon = lon;
     sc->first_lat = lat;
     sc->first_lon = lon;
     sc->have_bbox = 1;
   }
   else
   {
     if (lat < sc->minlat)
       sc->minlat = lat;
     if (lat > sc->maxlat)
       sc->maxlat = lat;
     if (lon < sc->minlon)
       sc->minlon = lon;
     if (lon > sc->maxlon)
       sc->maxlon = lon;
   }
   if (track)
   {
     if (sc->have_prev)
       sc->distance += gpx_haversine (sc->prev_lat,
                                      sc->prev_lon,
                                      lat,
                                      lon);
     sc->prev_lat = lat;
     sc->prev_lon = lon;
     sc->have_prev = 1;
   }
 }
 
 
 /**
  * Walk the buffer once, tallying points, coordinates, elevations and
  * timestamps.
  *
  * The walk is linear and every iteration advances at least one byte, so
  * it is bounded by @a len regardless of what the file contains.
  *
  * @param buf the buffer
  * @param len number of bytes in @a buf
  * @param[out] sc scan state to fill in
  */
 static void
 gpx_walk_points (const char *buf,
                  size_t len,
                  struct GpxScan *sc)
 {
   for (size_t i = 0; i < len; i++)
   {
     size_t vs;
     size_t vl;
     double lat;
     double lon;
     /* 0 = not a point, 1 = <trkpt>, 2 = <wpt>, 3 = <rtept> */
     unsigned int kind;
 
     if ('<' != buf[i])
       continue;
     if (gpx_tag_is (buf, len, i, "trkpt"))
     {
       kind = 1;
     }
     else if (gpx_tag_is (buf, len, i, "wpt"))
     {
       kind = 2;
     }
     else if (gpx_tag_is (buf, len, i, "rtept"))
     {
       kind = 3;
     }
     else if (sc->seen_point &&
              gpx_tag_is (buf, len, i, "ele") )
     {
       double ele;
 
       if (gpx_text (buf, len, i, &vs, &vl) &&
           gpx_parse_double (&buf[vs], vl, &ele) &&
           (ele > -20000.0) && (ele < 20000.0) )
       {
         if (! sc->have_ele)
         {
           sc->minele = sc->maxele = ele;
           sc->have_ele = 1;
         }
         else
         {
           if (ele < sc->minele)
             sc->minele = ele;
           if (ele > sc->maxele)
             sc->maxele = ele;
         }
       }
       continue;
     }
     else if (sc->seen_point &&
              gpx_tag_is (buf, len, i, "time") )
     {
       int64_t when;
 
       if (gpx_text (buf, len, i, &vs, &vl) &&
           gpx_parse_iso8601 (&buf[vs], vl, &when) )
       {
         if (0 == sc->first_time)
           sc->first_time = when;
         sc->last_time = when;
       }
       continue;
     }
     else
     {
       continue;
     }
     if (1 == kind)
       sc->trkpts++;
     else if (2 == kind)
       sc->wpts++;
     else
       sc->rtepts++;
     sc->seen_point = 1;
     if (gpx_attr (buf, len, i, "lat", &vs, &vl) &&
         gpx_parse_double (&buf[vs], vl, &lat) &&
         gpx_attr (buf, len, i, "lon", &vs, &vl) &&
         gpx_parse_double (&buf[vs], vl, &lon) )
       gpx_note_point (sc,
                       lat,
                       lon,
                       (1 == kind));
   }
 }
 
 
 /**
  * Does @a creator name a piece of hardware rather than an application?
  *
  * Purely a substring test against the GPS makers whose devices write
  * GPX.  It only decides whether we *additionally* report the value as
  * #EXTRACTOR_METATYPE_DEVICE_MODEL; the value is always reported as
  * #EXTRACTOR_METATYPE_CREATED_BY_SOFTWARE.
  *
  * @param creator the `creator' attribute value
  * @param len number of bytes in @a creator
  * @return 1 if it looks like a device model, 0 otherwise
  */
 static int
 gpx_looks_like_device (const char *creator,
                        size_t len)
 {
   static const char *vendors[] = {
     "garmin", "etrex", "oregon", "gpsmap", "edge", "fenix", "forerunner",
     "montana", "dakota", "colorado", "magellan", "suunto", "polar",
     "wahoo", "elemnt", "bryton", "lezyne", "sigma rox", "coros",
     "tomtom", "holux", "qstarz", "columbus", "igotu", "trimble",
     NULL
   };
   char low[128];
   size_t n = len;
 
   if (n > sizeof (low) - 1)
     n = sizeof (low) - 1;
   for (size_t i = 0; i < n; i++)
   {
     char c = creator[i];
 
     if ( ('A' <= c) && ('Z' >= c) )
       c = (char) (c - 'A' + 'a');
     low[i] = c;
   }
   low[n] = '\0';
   for (unsigned int i = 0; NULL != vendors[i]; i++)
     if (NULL != strstr (low,
                         vendors[i]))
       return 1;
   return 0;
 }
 
 
 /**
  * Report everything the `<metadata>' block holds.
  *
  * @param ec extraction context
  * @param buf the buffer
  * @param len number of bytes in @a buf
  * @return 1 if the caller should stop extracting, 0 to continue
  */
 static int
 gpx_do_metadata (struct EXTRACTOR_ExtractContext *ec,
                  const char *buf,
                  size_t len)
 {
   size_t md;
   size_t mdend;
   size_t p;
   size_t vs;
   size_t vl;
 
   md = gpx_find (buf,
                  len,
                  0,
                  "metadata");
   if (((size_t) -1) == md)
   {
     /* GPX 1.0 has no <metadata> element: name, desc, author, email,
        url, time, keywords and bounds are direct children of <gpx>.
        Treat everything from the root element up to the first <wpt>,
        <rte> or <trk> as the metadata block. */
     md = gpx_find (buf,
                    len,
                    0,
                    "gpx");
     if (((size_t) -1) == md)
       return 0;
     mdend = len;
     for (size_t i = md + 1; i < len; i++)
     {
       if ('<' != buf[i])
         continue;
       if (gpx_tag_is (buf, len, i, "wpt") ||
           gpx_tag_is (buf, len, i, "rte") ||
           gpx_tag_is (buf, len, i, "trk") )
       {
         mdend = i;
         break;
       }
     }
   }
   else
   {
     /* the block ends at `</metadata>'; if that is missing (truncated
        file), fall back to the end of the buffer */
     mdend = len;
     for (size_t i = md; i + 11 <= len; i++)
       if (0 == memcmp (&buf[i],
                        "</metadata>",
                        11))
       {
         mdend = i;
         break;
       }
   }
   p = gpx_find (buf, mdend, md + 1, "name");
   if ( (((size_t) -1) != p) &&
        gpx_text (buf, mdend, p, &vs, &vl) &&
        gpx_emit_xml (ec, EXTRACTOR_METATYPE_TITLE, &buf[vs], vl) )
     return 1;
   p = gpx_find (buf, mdend, md + 1, "desc");
   if ( (((size_t) -1) != p) &&
        gpx_text (buf, mdend, p, &vs, &vl) &&
        gpx_emit_xml (ec, EXTRACTOR_METATYPE_DESCRIPTION, &buf[vs], vl) )
     return 1;
   p = gpx_find (buf, mdend, md + 1, "keywords");
   if ( (((size_t) -1) != p) &&
        gpx_text (buf, mdend, p, &vs, &vl) &&
        gpx_emit_xml (ec, EXTRACTOR_METATYPE_KEYWORDS, &buf[vs], vl) )
     return 1;
   /* The author is `<author><name>' in GPX 1.1 and a plain
      `<author>text</author>' in GPX 1.0. */
   p = gpx_find (buf, mdend, md + 1, "author");
   if (((size_t) -1) != p)
   {
     size_t a = gpx_find (buf, mdend, p + 1, "name");
     int emitted = 0;
 
     if ( (((size_t) -1) != a) &&
          gpx_text (buf, mdend, a, &vs, &vl) )
     {
       emitted = 1;
       if (gpx_emit_xml (ec, EXTRACTOR_METATYPE_AUTHOR_NAME, &buf[vs], vl))
         return 1;
     }
     if ( (! emitted) &&
          gpx_text (buf, mdend, p, &vs, &vl) &&
          gpx_emit_xml (ec, EXTRACTOR_METATYPE_AUTHOR_NAME, &buf[vs], vl) )
       return 1;
   }
   /* `<email id="user" domain="host"/>' in GPX 1.1 -- split so that the
      file does not read as a harvestable address -- and a plain
      `<email>user@host</email>' in GPX 1.0. */
   p = gpx_find (buf, mdend, md + 1, "email");
   if (((size_t) -1) != p)
   {
     size_t ds;
     size_t dl;
 
     if (gpx_attr (buf, mdend, p, "id", &vs, &vl) &&
         gpx_attr (buf, mdend, p, "domain", &ds, &dl) )
     {
       if (EXTRACTOR_forensic_emit_ (ec,
                                     "gpx",
                                     EXTRACTOR_METATYPE_AUTHOR_EMAIL,
                                     "%.*s@%.*s",
                                     (int) vl,
                                     &buf[vs],
                                     (int) dl,
                                     &buf[ds]))
         return 1;
     }
     else if (gpx_text (buf, mdend, p, &vs, &vl) &&
              gpx_emit_xml (ec,
                            EXTRACTOR_METATYPE_AUTHOR_EMAIL,
                            &buf[vs],
                            vl) )
     {
       return 1;
     }
   }
   /* `<copyright author="...">' with an optional `<license>' child in
      GPX 1.1; a plain text element in GPX 1.0. */
   p = gpx_find (buf, mdend, md + 1, "copyright");
   if (((size_t) -1) != p)
   {
     if (gpx_attr (buf, mdend, p, "author", &vs, &vl))
     {
       if (gpx_emit_xml (ec, EXTRACTOR_METATYPE_COPYRIGHT, &buf[vs], vl))
         return 1;
     }
     else if (gpx_text (buf, mdend, p, &vs, &vl) &&
              gpx_emit_xml (ec, EXTRACTOR_METATYPE_COPYRIGHT, &buf[vs], vl) )
     {
       return 1;
     }
     {
       size_t l = gpx_find (buf, mdend, p + 1, "license");
 
       if ( (((size_t) -1) != l) &&
            gpx_text (buf, mdend, l, &vs, &vl) &&
            gpx_emit_xml (ec, EXTRACTOR_METATYPE_LICENSE, &buf[vs], vl) )
         return 1;
     }
   }
   /* every `<link href="...">' in the block, capped */
   {
     size_t l = md;
     unsigned int n = 0;
 
     while (n < EXTRACTOR_FORENSIC_MAX_ITEMS)
     {
       l = gpx_find (buf, mdend, l + 1, "link");
       if (((size_t) -1) == l)
         break;
       if (gpx_attr (buf, mdend, l, "href", &vs, &vl))
       {
         n++;
         if (gpx_emit_xml (ec, EXTRACTOR_METATYPE_URL, &buf[vs], vl))
           return 1;
       }
     }
   }
   /* GPX 1.0 spells the same thing `<url>' */
   p = gpx_find (buf, mdend, md + 1, "url");
   if ( (((size_t) -1) != p) &&
        gpx_text (buf, mdend, p, &vs, &vl) &&
        gpx_emit_xml (ec, EXTRACTOR_METATYPE_URL, &buf[vs], vl) )
     return 1;
   p = gpx_find (buf, mdend, md + 1, "time");
   if (((size_t) -1) != p)
   {
     int64_t when;
 
     if (gpx_text (buf, mdend, p, &vs, &vl))
     {
       if (gpx_parse_iso8601 (&buf[vs], vl, &when))
       {
         if (EXTRACTOR_forensic_emit_unix_time_ (ec,
                                                 "gpx",
                                                 EXTRACTOR_METATYPE_CREATION_DATE,
                                                 when))
           return 1;
       }
       else if (gpx_emit_xml (ec,
                              EXTRACTOR_METATYPE_UNKNOWN_DATE,
                              &buf[vs],
                              vl))
       {
         return 1;
       }
     }
   }
   return 0;
 }
 
 
 /**
  * Main entry method for the GPX extraction plugin.
  *
  * @param ec extraction context provided to the plugin
  */
 void
 EXTRACTOR_gpx_extract_method (struct EXTRACTOR_ExtractContext *ec);
 
 void
 EXTRACTOR_gpx_extract_method (struct EXTRACTOR_ExtractContext *ec)
 {
   char head[GPX_MAGIC_WINDOW];
   char *buf = NULL;
   size_t hlen = 0;
   size_t len = 0;
   size_t cap;
   uint64_t fsize;
   size_t root;
   size_t vs;
   size_t vl;
   struct GpxScan sc;
   int truncated;
 
   /* Bail out on the first few bytes: almost nothing we are handed is
      GPX, and we must not pay for the ones that are not. */
   {
     void *data;
     ssize_t ret;
 
     if (0 != ec->seek (ec->cls,
                        0,
                        SEEK_SET))
       return;
     while (hlen < sizeof (head))
     {
       ret = ec->read (ec->cls,
                       &data,
                       sizeof (head) - hlen);
       if (0 >= ret)
         break;
       if (((size_t) ret) > sizeof (head) - hlen)
         return;   /* the IPC layer is misbehaving */
       memcpy (&head[hlen],
               data,
               (size_t) ret);
       hlen += (size_t) ret;
     }
   }
   if (hlen < 16)
     return;
   root = gpx_find (head,
                    hlen,
                    0,
                    "gpx");
   if (((size_t) -1) == root)
     return;   /* not GPX */
   /* GPX is XML; require the declaration or at least that the document
      starts with markup, so that a text file merely containing "<gpx" is
      not claimed. */
   {
     size_t k = 0;
 
     if ( (hlen >= 3) &&
          (0 == memcmp (head, "\xef\xbb\xbf", 3)) )
       k = 3;   /* UTF-8 BOM */
     while ( (k < hlen) &&
             ( (' ' == head[k]) || ('\t' == head[k]) ||
               ('\r' == head[k]) || ('\n' == head[k]) ) )
       k++;
     if ( (k >= hlen) ||
          ('<' != head[k]) )
       return;
   }
 
   fsize = ec->get_size (ec->cls);
   cap = GPX_SCAN_CAP;
   if ( (UINT64_MAX != fsize) &&
        (fsize < (uint64_t) cap) )
     cap = (size_t) fsize;
   if (cap < hlen)
     cap = hlen;
   buf = malloc (cap);
   if (NULL == buf)
     return;
   if (0 != ec->seek (ec->cls,
                      0,
                      SEEK_SET))
   {
     free (buf);
     return;
   }
   while (len < cap)
   {
     void *data;
     ssize_t ret;
 
     ret = ec->read (ec->cls,
                     &data,
                     cap - len);
     if (0 >= ret)
       break;
     if (((size_t) ret) > cap - len)
       break;   /* the IPC layer is misbehaving */
     memcpy (&buf[len],
             data,
             (size_t) ret);
     len += (size_t) ret;
   }
   if (len < 16)
   {
     free (buf);
     return;
   }
   truncated = ( (UINT64_MAX == fsize) ||
                 (fsize > (uint64_t) len) );
 
   if (0 != ec->proc (ec->cls,
                      "gpx",
                      EXTRACTOR_METATYPE_MIMETYPE,
                      EXTRACTOR_METAFORMAT_UTF8,
                      "text/plain",
                      "application/gpx+xml",
                      strlen ("application/gpx+xml") + 1))
     goto out;
 
   root = gpx_find (buf,
                    (len < GPX_MAGIC_WINDOW) ? len : GPX_MAGIC_WINDOW,
                    0,
                    "gpx");
   if (((size_t) -1) != root)
   {
     /* The `creator' attribute is the single most identifying field in
        the format: it names the device or the application that produced
        the track. */
     if (gpx_attr (buf, len, root, "creator", &vs, &vl))
     {
       if (gpx_emit_xml (ec,
                         EXTRACTOR_METATYPE_CREATED_BY_SOFTWARE,
                         &buf[vs],
                         vl))
         goto out;
       if (gpx_looks_like_device (&buf[vs], vl) &&
           gpx_emit_xml (ec,
                         EXTRACTOR_METATYPE_DEVICE_MODEL,
                         &buf[vs],
                         vl) )
         goto out;
     }
     if (gpx_attr (buf, len, root, "version", &vs, &vl) &&
         gpx_emit_xml (ec,
                       EXTRACTOR_METATYPE_FORMAT_VERSION,
                       &buf[vs],
                       vl) )
       goto out;
   }
   /* GPX coordinates are always WGS 84; the schema does not allow
      anything else, so this is a statement about the format. */
   if (EXTRACTOR_forensic_emit_ (ec,
                                 "gpx",
                                 EXTRACTOR_METATYPE_COORDINATE_SYSTEM,
                                 "WGS 84"))
     goto out;
   if (gpx_do_metadata (ec,
                        buf,
                        len))
     goto out;
 
   memset (&sc,
           0,
           sizeof (sc));
   gpx_walk_points (buf,
                    len,
                    &sc);
 
   /* An explicit <bounds> beats what we computed: it covers the whole
      file, ours only covers what we scanned. */
   {
     size_t b = gpx_find (buf, len, 0, "bounds");
     double minlat;
     double minlon;
     double maxlat;
     double maxlon;
     int have = 0;
 
     if (((size_t) -1) != b)
     {
       if (gpx_attr (buf, len, b, "minlat", &vs, &vl) &&
           gpx_parse_double (&buf[vs], vl, &minlat) &&
           gpx_attr (buf, len, b, "minlon", &vs, &vl) &&
           gpx_parse_double (&buf[vs], vl, &minlon) &&
           gpx_attr (buf, len, b, "maxlat", &vs, &vl) &&
           gpx_parse_double (&buf[vs], vl, &maxlat) &&
           gpx_attr (buf, len, b, "maxlon", &vs, &vl) &&
           gpx_parse_double (&buf[vs], vl, &maxlon) &&
           (minlat >= -90.0) && (maxlat <= 90.0) &&
           (minlon >= -180.0) && (maxlon <= 180.0) )
         have = 1;
     }
     if ( (! have) &&
          sc.have_bbox)
     {
       minlat = sc.minlat;
       minlon = sc.minlon;
       maxlat = sc.maxlat;
       maxlon = sc.maxlon;
       have = 1;
     }
     if (have &&
         EXTRACTOR_forensic_emit_ (ec,
                                   "gpx",
                                   EXTRACTOR_METATYPE_BOUNDING_BOX,
                                   "%.6f,%.6f,%.6f,%.6f",
                                   minlon,
                                   minlat,
                                   maxlon,
                                   maxlat) )
       goto out;
   }
   if (sc.have_bbox)
   {
     /* Where the recording started; in a personal track log that is very
        often the recorder's home. */
     if (EXTRACTOR_forensic_emit_ (ec,
                                   "gpx",
                                   EXTRACTOR_METATYPE_GPS_LATITUDE,
                                   "%.6f",
                                   sc.first_lat))
       goto out;
     if (EXTRACTOR_forensic_emit_ (ec,
                                   "gpx",
                                   EXTRACTOR_METATYPE_GPS_LONGITUDE,
                                   "%.6f",
                                   sc.first_lon))
       goto out;
   }
   if (EXTRACTOR_forensic_emit_ (ec,
                                 "gpx",
                                 EXTRACTOR_METATYPE_ENTRY_COUNT,
                                 "%llu",
                                 (unsigned long long) sc.trkpts))
     goto out;
   if (EXTRACTOR_forensic_emit_ (ec,
                                 "gpx",
                                 EXTRACTOR_METATYPE_COMMENT,
                                 "%llu track points, %llu waypoints,"
                                 " %llu route points",
                                 (unsigned long long) sc.trkpts,
                                 (unsigned long long) sc.wpts,
                                 (unsigned long long) sc.rtepts))
     goto out;
   if ( (0 != sc.first_time) &&
        (sc.last_time > sc.first_time) )
   {
     int64_t d = sc.last_time - sc.first_time;
 
     if (EXTRACTOR_forensic_emit_ (ec,
                                   "gpx",
                                   EXTRACTOR_METATYPE_DURATION,
                                   "%lld:%02lld:%02lld",
                                   (long long) (d / 3600),
                                   (long long) ((d / 60) % 60),
                                   (long long) (d % 60)))
       goto out;
   }
   if (0 != sc.first_time)
   {
     /* When the first point was recorded; for a track without a
        <metadata><time> this is the only timestamp in the file. */
     if (EXTRACTOR_forensic_emit_unix_time_ (ec,
                                             "gpx",
                                             EXTRACTOR_METATYPE_CREATION_DATE,
                                             sc.first_time))
       goto out;
     if (EXTRACTOR_forensic_emit_unix_time_ (ec,
                                             "gpx",
                                             EXTRACTOR_METATYPE_MODIFICATION_DATE,
                                             sc.last_time))
       goto out;
   }
   if (sc.have_ele)
   {
     if (sc.maxele - sc.minele < 0.05)
     {
       if (EXTRACTOR_forensic_emit_ (ec,
                                     "gpx",
                                     EXTRACTOR_METATYPE_LOCATION_ELEVATION,
                                     "%.1f m",
                                     sc.minele))
         goto out;
     }
     else if (EXTRACTOR_forensic_emit_ (ec,
                                        "gpx",
                                        EXTRACTOR_METATYPE_LOCATION_ELEVATION,
                                        "%.1f-%.1f m",
                                        sc.minele,
                                        sc.maxele))
     {
       goto out;
     }
   }
   if (sc.distance >= 1.0)
   {
     /* Haversine sum over the track points we scanned -- free, since we
        walked them anyway.  Under the scan cap this is a lower bound. */
     if (EXTRACTOR_forensic_emit_ (ec,
                                   "gpx",
                                   EXTRACTOR_METATYPE_DISTANCE,
                                   "%.0f m",
                                   sc.distance))
       goto out;
   }
   /* Counts from a partial scan are lower bounds, and saying so is the
      whole point: silently under-reporting how many points a track has
      would be worse than not reporting at all. */
   if (truncated &&
       EXTRACTOR_forensic_emit_ (ec,
                                 "gpx",
                                 EXTRACTOR_METATYPE_COMMENT,
                                 "scan truncated at 1 MiB; the counts,"
                                 " bounding box, duration and distance"
                                 " above cover only that prefix of the"
                                 " file") )
     goto out;
 out:
   free (buf);
 }
 
 
 /* end of gpx_extractor.c */