libextractor

kml_extractor.c (37518B)

---

 /*
      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/kml_extractor.c
  * @brief plugin to support KML (Keyhole Markup Language) documents
  * @author Christian Grothoff
  *
  * KML is what Google Earth, Google Maps exports, most GIS tools and a
  * fair number of tracking applications write.  Like GPX it carries
  * coordinates, but it also carries `<NetworkLink>' elements, which make
  * opening the document fetch content from a remote host -- worth
  * flagging on its own.
  *
  * KMZ, the zipped form, is a zip archive whose first member is
  * `doc.kml'.  This plugin does not look inside it: libextractor's zip
  * support lives in the core decompressor, not here, and a KMZ therefore
  * does not reach this plugin as KML.  Nothing below will mistake a zip
  * for KML, since the magic check requires markup at the start of the
  * file.
  *
  * As in `gpx_extractor.c', this is a bounded scanner, not an XML parser
  * -- libextractor has no XML dependency and this plugin must stay
  * unconditional.  What that costs, stated once:
  *
  * - Comments (`<!-- ... -->') and processing instructions are not
  *   skipped, so an element that only occurs inside a comment is still
  *   counted.  A false positive, never an out-of-bounds read.
  * - CDATA is recognised only when it opens the content of an element we
  *   ask for -- which is the case that matters, because `<description>'
  *   almost always wraps its HTML in CDATA.
  * - Only the five predefined entities and numeric character references
  *   are expanded.
  * - Element content is the run of text up to the next `<'; nested
  *   elements inside a value are not concatenated.
  * - Namespace prefixes are ignored, so `<atom:name>' and `<name>' are
  *   the same element here.  That is what lets `<atom:author><atom:name>'
  *   be found without a namespace table, and it is why `<Link>' (KML) and
  *   `<link>' (Atom) have to be told apart by case, which XML guarantees.
  * - An `<Update>' or a `<Schema>' can hold elements with the same names
  *   as the ones we look for; we do not track the containing element, so
  *   such a document would be reported approximately.
  *
  * 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.  KML documents
  * exported from a GIS routinely run to many megabytes of coordinates.
  */
 #define KML_SCAN_CAP (1024 * 1024)
 
 /**
  * Longest start tag we will scan for its closing `>'.
  */
 #define KML_MAX_TAG 8192
 
 /**
  * Longest element text content we will look at, for everything except
  * `<coordinates>' (which gets #KML_MAX_COORD_TEXT).
  */
 #define KML_MAX_TEXT 8192
 
 /**
  * Longest `<coordinates>' body we will walk.
  */
 #define KML_MAX_COORD_TEXT (128 * 1024)
 
 /**
  * Most coordinate tuples we will parse out of one `<coordinates>'
  * element.
  */
 #define KML_MAX_TUPLES 100000
 
 /**
  * How far into the file the `<kml' element has to appear.
  */
 #define KML_MAGIC_WINDOW 2048
 
 /**
  * Most attributes we parse out of a single start tag.
  */
 #define KML_MAX_ATTRS 64
 
 
 /**
  * Everything the single pass over the document collected.
  */
 struct KmlScan
 {
   /**
    * Bounding box over every `<coordinates>' tuple seen.
    */
   double minlon;
   double minlat;
   double maxlon;
   double maxlat;
 
   /**
    * The first coordinate in the document.
    */
   double first_lat;
   double first_lon;
 
   /**
    * Number of `<Placemark>' elements.
    */
   uint64_t placemarks;
 
   /**
    * Number of `<NetworkLink>' elements.
    */
   uint64_t networklinks;
 
   /**
    * Offset of the first `<Placemark>', or `(size_t) -1'.
    */
   size_t first_placemark;
 
   /**
    * Offset of the first `<LookAt>' or `<Camera>', or `(size_t) -1'.
    */
   size_t viewpoint;
 
   /**
    * Non-zero once the bounding box fields are meaningful.
    */
   int have_bbox;
 };
 
 
 /**
  * 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
 kml_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; the comparison is case-sensitive, as XML requires.
  *
  * @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
 kml_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) &&
           kml_name_char (buf[i]) )
     i++;
   if ( (i < len) &&
        (':' == buf[i]) )
   {
     i++;
     start = i;
     while ( (i < len) &&
             (i - start < 64) &&
             kml_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
  *         #KML_MAX_TAG bytes
  */
 static size_t
 kml_tag_end (const char *buf,
              size_t len,
              size_t pos)
 {
   char quote = 0;
 
   for (size_t i = pos; (i < len) && (i - pos < KML_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
 kml_attr (const char *buf,
           size_t len,
           size_t pos,
           const char *name,
           size_t *vstart,
           size_t *vlen)
 {
   size_t end = kml_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) &&
           (kml_name_char (buf[i]) ||
            (':' == buf[i]) ) )
     i++;
   for (unsigned int n = 0; n < KML_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) &&
             (kml_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;
     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 maxtext most content bytes to return
  * @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
 kml_text (const char *buf,
           size_t len,
           size_t pos,
           size_t maxtext,
           size_t *tstart,
           size_t *tlen)
 {
   size_t end = kml_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 < maxtext) )
     {
       if (0 == memcmp (&buf[j],
                        "]]>",
                        3))
       {
         *tstart = i + 9;
         *tlen = j - (i + 9);
         return (0 != *tlen);
       }
       j++;
     }
     return 0;
   }
   j = i;
   while ( (j < len) &&
           ('<' != buf[j]) &&
           (j - i < maxtext) )
     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
 kml_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 (kml_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
 kml_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;
     }
     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;
 }
 
 
 /**
  * Drop HTML markup and collapse runs of white space.  KML
  * `<description>' values are HTML far more often than they are plain
  * text, and the balloon markup is noise for our purposes.
  *
  * Tags are removed by bracket matching, which is exactly as approximate
  * as it sounds: a `<' in the prose that is not markup eats up to the
  * next `>'.  That is the usual trade-off for markup that was never
  * required to be well-formed in the first place.
  *
  * @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
 kml_strip_html (const char *in,
                 size_t inlen,
                 char *out,
                 size_t outsize)
 {
   size_t o = 0;
   size_t i = 0;
   int space = 0;
 
   while ( (i < inlen) &&
           (o + 1 < outsize) )
   {
     if ('<' == in[i])
     {
       while ( (i < inlen) &&
               ('>' != in[i]) )
         i++;
       if (i < inlen)
         i++;
       space = 1;
       continue;
     }
     if ( (' ' == in[i]) || ('\t' == in[i]) ||
          ('\r' == in[i]) || ('\n' == in[i]) )
     {
       space = 1;
       i++;
       continue;
     }
     if (space &&
         (0 != o) &&
         (NULL == strchr (".,;:!?)]}",
                          in[i])) )
       out[o++] = ' ';
     space = 0;
     if (o + 1 < outsize)
       out[o++] = in[i];
     i++;
   }
   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
 kml_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 = kml_unescape (data,
                       len,
                       buf,
                       sizeof (buf));
   return EXTRACTOR_forensic_emit_text_ (ec,
                                         "kml",
                                         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] used number of bytes consumed, may be NULL
  * @param[out] value where to store the result
  * @return 1 on success, 0 if @a data does not start with a number
  */
 static int
 kml_parse_double (const char *data,
                   size_t len,
                   size_t *used,
                   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;
   if (NULL != used)
     *used = i;
   *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
 kml_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 KML writes it:
  * `YYYY-MM-DDThh:mm:ss[.fff][Z|(+|-)hh[:mm]]'.  A missing zone is taken
  * as UTC.  (KML also allows a bare `YYYY', `YYYY-MM' or `YYYY-MM-DD';
  * those are rejected here rather than guessed at.)
  *
  * @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 full timestamp
  */
 static int
 kml_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++;
       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) &&
          ('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 = kml_days_from_civil (v[0],
                                v[1],
                                v[2]) * 86400
           + v[3] * 3600 + v[4] * 60 + v[5]
           - off;
   return 1;
 }
 
 
 /**
  * Fold one coordinate into the bounding box.
  *
  * @param sc scan state
  * @param lon longitude in degrees
  * @param lat latitude in degrees
  */
 static void
 kml_note_coord (struct KmlScan *sc,
                 double lon,
                 double lat)
 {
   if ( (lat < -90.0) || (lat > 90.0) ||
        (lon < -180.0) || (lon > 180.0) )
     return;   /* out of range: not a coordinate */
   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;
     return;
   }
   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;
 }
 
 
 /**
  * Walk the body of one `<coordinates>' element.
  *
  * KML tuples are `lon,lat[,alt]', white-space separated -- note that
  * this is the *reverse* of the GPX attribute order, which is the classic
  * way to get a KML bounding box wrong.
  *
  * @param buf the buffer
  * @param len number of bytes in @a buf
  * @param pos offset of the `<' of the `<coordinates>' start tag
  * @param sc scan state to update
  */
 static void
 kml_walk_coordinates (const char *buf,
                       size_t len,
                       size_t pos,
                       struct KmlScan *sc)
 {
   size_t ts;
   size_t tl;
   size_t i = 0;
 
   if (! kml_text (buf,
                   len,
                   pos,
                   KML_MAX_COORD_TEXT,
                   &ts,
                   &tl))
     return;
   for (unsigned long n = 0; (n < KML_MAX_TUPLES) && (i < tl); n++)
   {
     size_t used;
     double lon;
     double lat;
 
     while ( (i < tl) &&
             ( (' ' == buf[ts + i]) || ('\t' == buf[ts + i]) ||
               ('\r' == buf[ts + i]) || ('\n' == buf[ts + i]) ||
               (',' == buf[ts + i]) ) )
       i++;
     if (i >= tl)
       break;
     if (! kml_parse_double (&buf[ts + i],
                             tl - i,
                             &used,
                             &lon))
     {
       i++;      /* garbage: skip a byte so the loop always progresses */
       continue;
     }
     i += used;
     if ( (i >= tl) ||
          (',' != buf[ts + i]) )
       continue;
     i++;
     if (! kml_parse_double (&buf[ts + i],
                             tl - i,
                             &used,
                             &lat))
       continue;
     i += used;
     kml_note_coord (sc,
                     lon,
                     lat);
     /* an optional altitude follows; skip it if it is there */
     if ( (i < tl) &&
          (',' == buf[ts + i]) )
     {
       i++;
       if (kml_parse_double (&buf[ts + i],
                             tl - i,
                             &used,
                             &lon))
         i += used;
     }
   }
 }
 
 
 /**
  * Walk the document once, counting placemarks and network links and
  * folding every coordinate into the bounding box.
  *
  * @param buf the buffer
  * @param len number of bytes in @a buf
  * @param[out] sc scan state to fill in
  */
 static void
 kml_walk (const char *buf,
           size_t len,
           struct KmlScan *sc)
 {
   for (size_t i = 0; i < len; i++)
   {
     if ('<' != buf[i])
       continue;
     if (kml_tag_is (buf, len, i, "Placemark"))
     {
       sc->placemarks++;
       if (((size_t) -1) == sc->first_placemark)
         sc->first_placemark = i;
     }
     else if (kml_tag_is (buf, len, i, "NetworkLink"))
     {
       sc->networklinks++;
     }
     else if (kml_tag_is (buf, len, i, "coordinates"))
     {
       kml_walk_coordinates (buf,
                             len,
                             i,
                             sc);
     }
     else if ( (((size_t) -1) == sc->viewpoint) &&
               (kml_tag_is (buf, len, i, "LookAt") ||
                kml_tag_is (buf, len, i, "Camera") ) )
     {
       sc->viewpoint = i;
     }
   }
 }
 
 
 /**
  * Report the `<href>' of every `<NetworkLink>' and the `<atom:link
  * href=>' of the document, capped.
  *
  * @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
 kml_do_links (struct EXTRACTOR_ExtractContext *ec,
               const char *buf,
               size_t len)
 {
   size_t p;
   size_t vs;
   size_t vl;
   unsigned int n = 0;
 
   /* <atom:link href="..."/>: the document's own canonical location */
   p = 0;
   while (n < EXTRACTOR_FORENSIC_MAX_ITEMS)
   {
     p = kml_find (buf,
                   len,
                   p,
                   "link");
     if (((size_t) -1) == p)
       break;
     if (kml_attr (buf, len, p, "href", &vs, &vl))
     {
       n++;
       if (kml_emit_xml (ec,
                         EXTRACTOR_METATYPE_URL,
                         &buf[vs],
                         vl))
         return 1;
     }
     p++;
   }
   /* <href> elements: KML's own <Link>, <Icon> and <NetworkLink> all use
      one.  These are what make opening the document talk to a network. */
   p = 0;
   n = 0;
   while (n < EXTRACTOR_FORENSIC_MAX_ITEMS)
   {
     p = kml_find (buf,
                   len,
                   p,
                   "href");
     if (((size_t) -1) == p)
       break;
     if (kml_text (buf, len, p, KML_MAX_TEXT, &vs, &vl))
     {
       n++;
       if (kml_emit_xml (ec,
                         EXTRACTOR_METATYPE_URL,
                         &buf[vs],
                         vl))
         return 1;
     }
     p++;
   }
   return 0;
 }
 
 
 /**
  * Main entry method for the KML extraction plugin.
  *
  * @param ec extraction context provided to the plugin
  */
 void
 EXTRACTOR_kml_extract_method (struct EXTRACTOR_ExtractContext *ec);
 
 void
 EXTRACTOR_kml_extract_method (struct EXTRACTOR_ExtractContext *ec)
 {
   char head[KML_MAGIC_WINDOW];
   char *buf = NULL;
   size_t hlen = 0;
   size_t len = 0;
   size_t cap;
   size_t limit;
   size_t p;
   size_t vs;
   size_t vl;
   uint64_t fsize;
   struct KmlScan sc;
   int truncated;
 
   /* Bail out on the first few bytes: almost nothing we are handed is
      KML, 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;
   if (((size_t) -1) == kml_find (head,
                                  hlen,
                                  0,
                                  "kml"))
     return;   /* not KML */
   {
     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;   /* not markup; in particular, not a KMZ (which is a zip) */
   }
 
   fsize = ec->get_size (ec->cls);
   cap = KML_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,
                      "kml",
                      EXTRACTOR_METATYPE_MIMETYPE,
                      EXTRACTOR_METAFORMAT_UTF8,
                      "text/plain",
                      "application/vnd.google-earth.kml+xml",
                      strlen ("application/vnd.google-earth.kml+xml") + 1))
     goto out;
   /* KML is defined on WGS 84 only; the specification does not offer an
      alternative, so this says something about the format. */
   if (EXTRACTOR_forensic_emit_ (ec,
                                 "kml",
                                 EXTRACTOR_METATYPE_COORDINATE_SYSTEM,
                                 "WGS 84"))
     goto out;
 
   memset (&sc,
           0,
           sizeof (sc));
   sc.first_placemark = (size_t) -1;
   sc.viewpoint = (size_t) -1;
   kml_walk (buf,
             len,
             &sc);
 
   /* The document title is the <name> of the enclosing <Document> or
      <Folder>, which in practice is the first <name> before the first
      <Placemark>. */
   limit = (((size_t) -1) == sc.first_placemark) ? len : sc.first_placemark;
   p = kml_find (buf, limit, 0, "name");
   if ( (((size_t) -1) != p) &&
        kml_text (buf, limit, p, KML_MAX_TEXT, &vs, &vl) &&
        kml_emit_xml (ec, EXTRACTOR_METATYPE_TITLE, &buf[vs], vl) )
     goto out;
   p = kml_find (buf, limit, 0, "description");
   if ( (((size_t) -1) != p) &&
        kml_text (buf, limit, p, KML_MAX_TEXT, &vs, &vl) )
   {
     char stripped[EXTRACTOR_FORENSIC_MAX_STRING];
     size_t slen;
 
     /* <description> is HTML far more often than not; the markup is
        noise, but the text inside it is exactly what we want. */
     slen = kml_strip_html (&buf[vs],
                            vl,
                            stripped,
                            sizeof (stripped));
     if (kml_emit_xml (ec,
                       EXTRACTOR_METATYPE_DESCRIPTION,
                       stripped,
                       slen))
       goto out;
   }
   /* <atom:author><atom:name> */
   p = kml_find (buf, len, 0, "author");
   if (((size_t) -1) != p)
   {
     size_t a = kml_find (buf, len, p + 1, "name");
 
     if ( (((size_t) -1) != a) &&
          kml_text (buf, len, a, KML_MAX_TEXT, &vs, &vl) &&
          kml_emit_xml (ec, EXTRACTOR_METATYPE_AUTHOR_NAME, &buf[vs], vl) )
       goto out;
   }
   if (kml_do_links (ec,
                     buf,
                     len))
     goto out;
   if (0 != sc.networklinks)
   {
     /* Worth saying out loud: a NetworkLink means the document fetches
        content from somewhere else when it is opened. */
     if (EXTRACTOR_forensic_emit_ (ec,
                                   "kml",
                                   EXTRACTOR_METATYPE_COMMENT,
                                   "%llu NetworkLink element%s;"
                                   " opening this document fetches remote"
                                   " content",
                                   (unsigned long long) sc.networklinks,
                                   (1 == sc.networklinks) ? "" : "s"))
       goto out;
   }
   /* <TimeStamp><when> or, failing that, <TimeSpan><begin> */
   {
     size_t t = kml_find (buf, len, 0, "TimeStamp");
     size_t w = (size_t) -1;
 
     if (((size_t) -1) != t)
       w = kml_find (buf, len, t + 1, "when");
     if (((size_t) -1) == w)
     {
       t = kml_find (buf, len, 0, "TimeSpan");
       if (((size_t) -1) != t)
         w = kml_find (buf, len, t + 1, "begin");
     }
     if ( (((size_t) -1) != w) &&
          kml_text (buf, len, w, KML_MAX_TEXT, &vs, &vl) )
     {
       int64_t when;
 
       if (kml_parse_iso8601 (&buf[vs], vl, &when))
       {
         if (EXTRACTOR_forensic_emit_unix_time_ (ec,
                                                 "kml",
                                                 EXTRACTOR_METATYPE_CREATION_DATE,
                                                 when))
           goto out;
       }
       else if (kml_emit_xml (ec,
                              EXTRACTOR_METATYPE_UNKNOWN_DATE,
                              &buf[vs],
                              vl))
       {
         goto out;
       }
     }
   }
   if (((size_t) -1) != sc.first_placemark)
   {
     /* the first Placemark's <name>, bounded by its </Placemark> */
     size_t pend = len;
     size_t nm;
 
     for (size_t i = sc.first_placemark; i + 12 <= len; i++)
       if (0 == memcmp (&buf[i],
                        "</Placemark>",
                        12))
       {
         pend = i;
         break;
       }
     nm = kml_find (buf, pend, sc.first_placemark + 1, "name");
     if ( (((size_t) -1) != nm) &&
          kml_text (buf, pend, nm, KML_MAX_TEXT, &vs, &vl) &&
          kml_emit_xml (ec, EXTRACTOR_METATYPE_LOCATION_NAME, &buf[vs], vl) )
       goto out;
   }
   if (sc.have_bbox)
   {
     if (EXTRACTOR_forensic_emit_ (ec,
                                   "kml",
                                   EXTRACTOR_METATYPE_BOUNDING_BOX,
                                   "%.6f,%.6f,%.6f,%.6f",
                                   sc.minlon,
                                   sc.minlat,
                                   sc.maxlon,
                                   sc.maxlat))
       goto out;
     if (EXTRACTOR_forensic_emit_ (ec,
                                   "kml",
                                   EXTRACTOR_METATYPE_GPS_LATITUDE,
                                   "%.6f",
                                   sc.first_lat))
       goto out;
     if (EXTRACTOR_forensic_emit_ (ec,
                                   "kml",
                                   EXTRACTOR_METATYPE_GPS_LONGITUDE,
                                   "%.6f",
                                   sc.first_lon))
       goto out;
   }
   if (((size_t) -1) != sc.viewpoint)
   {
     /* A <LookAt> or <Camera> is where the *viewer* is put, not where the
        data is; reporting it as a GPS position would conflate the two, so
        it goes into a comment that says which it is. */
     size_t lonp = kml_find (buf, len, sc.viewpoint + 1, "longitude");
     size_t latp = kml_find (buf, len, sc.viewpoint + 1, "latitude");
     double vlon;
     double vlat;
     size_t s2;
     size_t l2;
 
     if ( (((size_t) -1) != lonp) &&
          (((size_t) -1) != latp) &&
          kml_text (buf, len, lonp, KML_MAX_TEXT, &vs, &vl) &&
          kml_parse_double (&buf[vs], vl, NULL, &vlon) &&
          kml_text (buf, len, latp, KML_MAX_TEXT, &s2, &l2) &&
          kml_parse_double (&buf[s2], l2, NULL, &vlat) &&
          (vlat >= -90.0) && (vlat <= 90.0) &&
          (vlon >= -180.0) && (vlon <= 180.0) )
     {
       if (EXTRACTOR_forensic_emit_ (ec,
                                     "kml",
                                     EXTRACTOR_METATYPE_COMMENT,
                                     "%s viewpoint at %.6f, %.6f"
                                     " (latitude, longitude)",
                                     kml_tag_is (buf, len, sc.viewpoint,
                                                 "Camera")
                                     ? "Camera" : "LookAt",
                                     vlat,
                                     vlon))
         goto out;
     }
   }
   if (EXTRACTOR_forensic_emit_ (ec,
                                 "kml",
                                 EXTRACTOR_METATYPE_ENTRY_COUNT,
                                 "%llu",
                                 (unsigned long long) sc.placemarks))
     goto out;
   if (truncated &&
       EXTRACTOR_forensic_emit_ (ec,
                                 "kml",
                                 EXTRACTOR_METATYPE_COMMENT,
                                 "scan truncated at 1 MiB; the placemark"
                                 " count and bounding box above cover"
                                 " only that prefix of the file") )
     goto out;
 out:
   free (buf);
 }
 
 
 /* end of kml_extractor.c */