Initial import of r35+comments of the bzr tree of gpx-import
[gpx-import.git] / src / gpx.c
1 /* gpx-import/src/gpx.c
2  *
3  * GPX load and memory management
4  *
5  * Copyright Daniel Silverstone <dsilvers@digital-scurf.org>
6  *
7  * Written for the OpenStreetMap project.
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU General Public License as
11  * published by the Free Software Foundation; version 2 of the License
12  * only.
13  *
14  * This program is distributed in the hope that it will be useful, but
15  * WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17  * General Public License for more details.
18  */
19
20 #include <sys/types.h>
21 #include <expat.h>
22 #include <stdlib.h>
23 #include <alloca.h>
24 #include <unistd.h>
25 #include <fcntl.h>
26 #include <stdbool.h>
27 #include <string.h>
28 #include <strings.h>
29 #include <stdio.h>
30 #include <errno.h>
31 #include <stdarg.h>
32 #include <time.h>
33
34 #include <archive.h>
35 #include <archive_entry.h>
36
37 #include <zlib.h>
38 #include <bzlib.h>
39
40 #include "gpx.h"
41
42 #define GPX_BUFLEN 4096
43 #define ERR_BUFFER_SIZE 1024
44
45 #define PARSE_ERROR(ctx,F...)                           \
46   do {                                                  \
47     if (ctx->err != NULL && *(ctx->err) == NULL)        \
48       gpx_record_error(ctx, F);                         \
49   } while (0)
50
51 void
52 gpx_free(GPX *gpx)
53 {
54   GPXTrackPoint *pt = gpx->points, *ptnext;
55   while (pt != NULL) {
56     ptnext = pt->next;
57     free(pt->timestamp);
58     free(pt);
59     pt = ptnext;
60   }
61   free(gpx);
62 }
63
64 typedef enum {
65   UNKNOWN,
66   TRACKPOINT,
67   ELEVATION,
68   TIMESTAMP,
69 } GPXParseState;
70
71 static const char *
72 gpx_state_name(GPXParseState p)
73 {
74   switch (p) {
75   case UNKNOWN:
76     return "UNKNOWN";
77   case TRACKPOINT:
78     return "TRACKPOINT";
79   case ELEVATION:
80     return "ELEVATION";
81   case TIMESTAMP:
82     return "TIMESTAMP";
83   }
84   return "INVALID";
85 }
86
87 typedef struct {
88   XML_Parser p;
89   GPX *gpx;
90   GPXTrackPoint *point;
91   GPXTrackPoint *lastpoint;
92   uint32_t curseg;
93   char *accumulator;
94   int accumulator_size;
95   GPXParseState state;
96   bool got_lat, got_long, got_ele, got_time;
97   char **err;
98   const char *subfile;
99 } GPXParseContext;
100
101 static void
102 gpx_record_error(GPXParseContext *ctx, char *fmt, ...)
103 {
104   va_list va;
105   int sz;
106   char msg[ERR_BUFFER_SIZE];
107   
108   va_start(va, fmt);
109   sz = vsnprintf(msg, ERR_BUFFER_SIZE, fmt, va);
110   va_end(va);
111   
112   *(ctx->err) = calloc(2, ERR_BUFFER_SIZE);
113   snprintf(*(ctx->err), 2 * ERR_BUFFER_SIZE, "%s%s%s%s\n  XML parser at line %ld column %ld",
114            (ctx->subfile == NULL) ? "" : "In file ",
115            (ctx->subfile == NULL) ? "" : ctx->subfile,
116            (ctx->subfile == NULL) ? "" : " inside your upload:\n  ",
117            msg,
118            XML_GetCurrentLineNumber(ctx->p),
119            XML_GetCurrentColumnNumber(ctx->p));
120 }
121
122 static GPXCoord
123 gpx_parse_coord(const XML_Char *str)
124 {
125   GPXCoord ret = 0;
126   bool is_neg = false;
127   bool is_afterdot = false;
128   int afterdot = 0;
129   
130   if (*str == '-') {
131     is_neg = true;
132     str++;
133   }
134   while (*str != '\0' && afterdot < 9) {
135     if (*str == '.')
136       is_afterdot = true;
137     if (*str != '.') {
138       ret *= 10;
139       ret += (*str - '0');
140       if (is_afterdot == true)
141         afterdot++;
142     }
143     str++;
144   }
145   
146   while (afterdot < 9) {
147     afterdot++;
148     ret *= 10;
149   }
150   
151   return (is_neg ? -ret : ret);
152 }
153
154 static void
155 gpx_clear_accumulator(GPXParseContext *ctx)
156 {
157   if (ctx->accumulator != NULL)
158     free(ctx->accumulator);
159   ctx->accumulator = NULL;
160   ctx->accumulator_size = 0;
161 }
162
163 #define REQUIRE_STATE(S)                                                \
164   if (ctx->state != (S)) {                                              \
165     PARSE_ERROR(ctx, "Expected state %s, got state %s", gpx_state_name(S), gpx_state_name(ctx->state)); \
166     XML_StopParser(ctx->p, 0);                                          \
167     return;                                                             \
168   }
169
170 static void
171 gpx_handle_start_element(void *_ctx, const XML_Char *name, const XML_Char **atts)
172 {
173   GPXParseContext *ctx = (GPXParseContext *)(_ctx);
174   if (strcmp(name, "trkpt") == 0) {
175     REQUIRE_STATE(UNKNOWN);
176     ctx->state = TRACKPOINT;
177     ctx->point = calloc(1, sizeof(GPXTrackPoint));
178     ctx->point->segment = ctx->curseg;
179     ctx->got_lat = ctx->got_long = ctx->got_ele = ctx->got_time = false;
180     while (*atts != NULL) {
181       if (strcmp(*atts, "lat") == 0) {
182         atts++;
183         ctx->point->latitude = gpx_parse_coord(*atts++);
184         ctx->got_lat = true;
185       } else if (strcmp(*atts, "lon") == 0) {
186         atts++;
187         ctx->point->longitude = gpx_parse_coord(*atts++);
188         ctx->got_long = true;
189       } else {
190         atts += 2; /* skip tag + value */
191       }
192     }
193   } else if (strcmp(name, "ele") == 0) {
194     REQUIRE_STATE(TRACKPOINT);
195     ctx->state = ELEVATION;
196     gpx_clear_accumulator(ctx);
197   } else if (strcmp(name, "time") == 0) {
198     if (ctx->state == TRACKPOINT) {
199       ctx->state = TIMESTAMP;
200       gpx_clear_accumulator(ctx);
201     }
202   }
203 }
204
205 #ifndef MIN
206 #define MIN(a,b) (((a) < (b)) ? (a) : (b))
207 #endif
208
209 #ifndef MAX
210 #define MAX(a,b) (((a) > (b)) ? (a) : (b))
211 #endif
212
213 static void
214 gpx_update_minmax(GPX *gpx, GPXTrackPoint *point)
215 {
216   gpx->minlatitude = MIN(gpx->minlatitude, point->latitude);
217   gpx->minlongitude = MIN(gpx->minlongitude, point->longitude);
218   gpx->maxlatitude = MAX(gpx->maxlatitude, point->latitude);
219   gpx->maxlongitude = MAX(gpx->maxlongitude, point->longitude);
220 }
221
222 static void
223 gpx_handle_end_element(void *_ctx, const XML_Char *name)
224 {
225   GPXParseContext *ctx = (GPXParseContext *)(_ctx);
226   if (strcmp(name, "trkpt") == 0) {
227     REQUIRE_STATE(TRACKPOINT);
228     /* Remove the || true if elevation is mandatory. */
229     if (ctx->got_time == false)
230       ctx->gpx->missed_time++;
231     
232     if ((ctx->got_lat == false) ||
233         (ctx->point->latitude < -90000000000) ||
234         (ctx->point->latitude > 90000000000))
235       ctx->gpx->bad_lat++;
236     
237     if ((ctx->got_long == false) ||
238         (ctx->point->longitude < -180000000000) ||
239         (ctx->point->longitude > 180000000000))
240       ctx->gpx->bad_long++;
241     
242     if ((ctx->got_lat && ctx->got_long && (ctx->got_ele || true) && ctx->got_time) &&
243         (ctx->point != NULL) && (ctx->point->longitude >= -180000000000) &&
244         (ctx->point->longitude <= 180000000000) &&
245         (ctx->point->latitude >= -90000000000) &&
246         (ctx->point->latitude <= 90000000000)) {
247       gpx_update_minmax(ctx->gpx, ctx->point);
248       
249       if (ctx->lastpoint == NULL) {
250         INFO("Attaching first point");
251         ctx->gpx->firstlatitude = ctx->point->latitude;
252         ctx->gpx->firstlongitude = ctx->point->longitude;
253         ctx->lastpoint = ctx->point;
254         ctx->gpx->points = ctx->point;
255         ctx->point = NULL;
256       } else {
257         ctx->lastpoint->next = ctx->point;
258         ctx->lastpoint = ctx->point;
259         ctx->point = NULL;
260       }
261       
262       ctx->gpx->goodpoints++;
263       
264     } else {
265       ctx->gpx->badpoints++;
266       if (ctx->point->timestamp != NULL)
267         free(ctx->point->timestamp);
268       free(ctx->point);
269       ctx->point = NULL;
270     }
271     ctx->state = UNKNOWN;
272   } else if (strcmp(name, "ele") == 0) {
273     REQUIRE_STATE(ELEVATION);
274     ctx->point->elevation = strtof(ctx->accumulator, NULL);
275     ctx->state = TRACKPOINT;
276     ctx->got_ele = true;
277   } else if (strcmp(name, "time") == 0) {
278     char *pnull = NULL;
279     struct tm ignored;
280     if (ctx->state == UNKNOWN)
281       return;
282     REQUIRE_STATE(TIMESTAMP);
283     pnull = strptime(ctx->accumulator ? ctx->accumulator : "",
284                      "%Y-%m-%dT%H:%M:%S",
285                      &ignored);
286     if (pnull != NULL && (*pnull == '\0' || *pnull == '.' || *pnull == 'Z')) {
287       ctx->point->timestamp = ctx->accumulator;
288       ctx->accumulator = NULL;
289       ctx->got_time = true;
290     }
291     ctx->state = TRACKPOINT;
292   } else if (strcmp(name, "trkseg") == 0) {
293     REQUIRE_STATE(UNKNOWN);
294     ctx->curseg++;
295   }
296 }
297
298 void
299 gpx_handle_string_data(void *_ctx, const XML_Char *str, int len)
300 {
301   GPXParseContext *ctx = (GPXParseContext *)(_ctx);
302   
303   if ((ctx->state != ELEVATION) &&
304       (ctx->state != TIMESTAMP))
305     /* We only accumulate during elevation or timestamp */
306     return;
307   
308   if (ctx->accumulator == NULL) {
309     ctx->accumulator = malloc(len + 1);
310     memcpy(ctx->accumulator, str, len);
311     ctx->accumulator_size = len + 1;
312   } else {
313     ctx->accumulator = realloc(ctx->accumulator, ctx->accumulator_size + len);
314     memcpy(ctx->accumulator + ctx->accumulator_size - 1, str, len);
315     ctx->accumulator_size += len;
316   }
317   
318   ctx->accumulator[ctx->accumulator_size - 1] = '\0';
319 }
320
321 static bool
322 gpx_create_parser(GPXParseContext *ctx)
323 {
324   ctx->p = XML_ParserCreate(NULL);
325   
326   if (ctx->p == NULL)
327     return false;
328   
329   XML_SetElementHandler(ctx->p, gpx_handle_start_element, gpx_handle_end_element);
330   XML_SetDefaultHandler(ctx->p, gpx_handle_string_data);
331   XML_SetUserData(ctx->p, ctx);
332   
333   return true;
334 }
335
336 static bool
337 gpx_parse_buffer(GPXParseContext *ctx, const char *buffer, ssize_t buflen)
338 {
339   if (XML_Parse(ctx->p, buffer, buflen, XML_FALSE) != XML_STATUS_OK) {
340     if (*(ctx->err) == NULL) {
341       PARSE_ERROR(ctx, "Generic XML parse error");
342     }
343     return false;
344   }
345   return true;
346 }
347
348 static void
349 gpx_free_parser(GPXParseContext *ctx)
350 {
351   if (ctx->p != NULL)
352     XML_ParserFree(ctx->p);
353   ctx->p = NULL;
354 }
355
356 static void
357 gpx_abort_context(GPXParseContext *ctx)
358 {
359   gpx_free(ctx->gpx);
360   if (ctx->point != NULL) {
361     if (ctx->point->timestamp)
362       free(ctx->point->timestamp);
363     free(ctx->point);
364   }
365   if (ctx->accumulator != NULL)
366     free(ctx->accumulator);
367   gpx_free_parser(ctx);
368 }
369
370 static bool
371 gpx_parse_plain_file(GPXParseContext *ctx, const char *gpxfile)
372 {
373   char *buffer = alloca(GPX_BUFLEN);
374   ssize_t bufread;
375   int fd = open(gpxfile, O_RDONLY);
376   
377   if (fd == -1) {
378     PARSE_ERROR(ctx, "Error opening file %s: %s", gpxfile, strerror(errno));
379     return false;
380   }
381   
382   if (gpx_create_parser(ctx) == false) {
383     PARSE_ERROR(ctx, "Unable to create XML parser");
384     close(fd);
385     return false;
386   }
387   
388   while ((bufread = read(fd, buffer, GPX_BUFLEN)) > 0) {
389     if (gpx_parse_buffer(ctx, buffer, bufread) == false) {
390       close(fd);
391       return false;
392     }
393   }
394   
395   close(fd);
396   
397   gpx_free_parser(ctx);
398   
399   return true;
400 }
401
402 static bool
403 gpx_parse_archive(GPXParseContext *ctx, const char *gpxfile)
404 {
405   struct archive *arch;
406   struct archive_entry *ent;
407   bool okay = false;
408   int64_t sublen;
409   char *buffer = alloca(GPX_BUFLEN);
410   int ret;
411   
412   arch = archive_read_new();
413   if (arch == NULL) {
414     return false;
415   }
416   
417   archive_read_support_compression_gzip(arch);
418   archive_read_support_compression_bzip2(arch);
419   archive_read_support_format_all(arch);
420   
421   if (archive_read_open_filename(arch, gpxfile, 1) < ARCHIVE_OK) {
422     goto out;
423   }
424   
425   while ((ret = archive_read_next_header(arch, &ent)) == ARCHIVE_OK) {
426     ctx->subfile = archive_entry_pathname(ent);
427     sublen = archive_entry_size(ent);
428     if (sublen > 0) {
429       INFO("Considering sub-entry %s in job", ctx->subfile);
430       /* There's data, let's try and parse it */
431       gpx_create_parser(ctx);
432       while (sublen > 0) {
433         if (archive_read_data(arch, buffer, MIN(GPX_BUFLEN, sublen)) < ARCHIVE_OK) {
434           PARSE_ERROR(ctx, "Unable to read data from archive.");
435           goto out;
436         }
437         if (gpx_parse_buffer(ctx, buffer, MIN(GPX_BUFLEN, sublen)) == false) {
438           goto out;
439         }
440         sublen -= MIN(GPX_BUFLEN, sublen);
441       }
442       gpx_free_parser(ctx);
443     }
444     ctx->subfile = NULL;
445   }
446   
447   
448   if ((ret == ARCHIVE_EOF) && ctx->gpx->goodpoints > 0)
449     okay = true;
450   
451   out:
452   archive_read_close(arch);
453   archive_read_finish(arch);
454   return okay;
455 }
456
457 static char gzip_magic[] = { 0x1f, 0x8b, 0x08 };
458 static char bzip2_magic[] = { 0x42, 0x5a, 0x68, 0x39, 0x31 };
459
460 static bool
461 gpx_try_gzip(GPXParseContext *ctx, const char *gpxfile)
462 {
463   int fd = open(gpxfile, O_RDONLY);
464   gzFile *f;
465   char *buffer = alloca(GPX_BUFLEN);
466   ssize_t bufread;
467   
468   if (fd == -1) {
469     PARSE_ERROR(ctx, "Unable to open %s (errno=%s)", gpxfile, strerror(errno));
470     return false;
471   }
472   
473   if (read(fd, buffer, sizeof(gzip_magic)) != sizeof(gzip_magic)) {
474     PARSE_ERROR(ctx, "Unable to read data from %s (errno=%s)", gpxfile, strerror(errno));
475     close(fd);
476     return false;
477   }
478   
479   if (memcmp(buffer, gzip_magic, sizeof(gzip_magic)) != 0) {
480     close(fd);
481     return false;
482   }
483   
484   lseek(fd, 0, SEEK_SET);
485   
486   f = gzdopen(fd, "rb"); /* Takes over the FD */
487   
488   INFO("Detected gzip encoded data");
489   
490   if (gpx_create_parser(ctx) == false) {
491     PARSE_ERROR(ctx, "Unable to create XML parser");
492     gzclose(f);
493     return false;
494   }
495   
496   while ((bufread = gzread(f, buffer, GPX_BUFLEN)) > 0) {
497     if (gpx_parse_buffer(ctx, buffer, bufread) == false) {
498       gzclose(f);
499       return false;
500     }
501   }
502   
503   gzclose(f);
504   
505   gpx_free_parser(ctx);
506   
507   return true;
508 }
509
510 static bool
511 gpx_try_bzip2(GPXParseContext *ctx, const char *gpxfile)
512 {
513   int fd = open(gpxfile, O_RDONLY);
514   BZFILE *f;
515   char *buffer = alloca(GPX_BUFLEN);
516   ssize_t bufread;
517   
518   if (fd == -1) {
519     PARSE_ERROR(ctx, "Unable to open %s (errno=%s)", gpxfile, strerror(errno));
520     return false;
521   }
522   
523   if (read(fd, buffer, sizeof(bzip2_magic)) != sizeof(bzip2_magic)) {
524     PARSE_ERROR(ctx, "Unable to read data from %s (errno=%s)", gpxfile, strerror(errno));
525     close(fd);
526     return false;
527   }
528   
529   if (memcmp(buffer, bzip2_magic, sizeof(bzip2_magic)) != 0) {
530     close(fd);
531     return false;
532   }
533   
534   close(fd);
535   
536   f = BZ2_bzopen(gpxfile, "rb");
537   
538   INFO("Detected bzip2 encoded data");
539   
540   if (gpx_create_parser(ctx) == false) {
541     PARSE_ERROR(ctx, "Unable to create XML parser");
542     BZ2_bzclose(f);
543     return false;
544   }
545   
546   while ((bufread = BZ2_bzread(f, buffer, GPX_BUFLEN)) > 0) {
547     if (gpx_parse_buffer(ctx, buffer, bufread) == false) {
548       BZ2_bzclose(f);
549       return false;
550     }
551   }
552   
553   BZ2_bzclose(f);
554   
555   gpx_free_parser(ctx);
556   
557   return true;
558 }
559
560 GPX*
561 gpx_parse_file(const char *gpxfile, char **err)
562 {
563   GPXParseContext ctx;
564   
565   ctx.err = err;
566   
567   ctx.gpx = calloc(1, sizeof(GPX));
568   ctx.gpx->minlatitude = 91000000000;
569   ctx.gpx->minlongitude = 181000000000;
570   ctx.gpx->maxlatitude = -91000000000;
571   ctx.gpx->maxlongitude = -181000000000;
572   ctx.point = NULL;
573   ctx.lastpoint = NULL;
574   ctx.curseg = 0;
575   ctx.accumulator = NULL;
576   ctx.state = UNKNOWN;
577   ctx.accumulator_size = 0;
578   ctx.subfile = NULL;
579   
580   if (gpx_parse_archive(&ctx, gpxfile) == true) {
581     goto success;
582   } else {
583     if (*(ctx.err) != NULL) {
584       ERROR("Archive failure");
585       goto failure;
586     }
587   }
588   
589   if (gpx_try_gzip(&ctx, gpxfile) == true) {
590     goto success;
591   } else {
592     if (*(ctx.err) != NULL) {
593       ERROR("GZip failure");
594       goto failure;
595     }
596   }
597   
598   if (gpx_try_bzip2(&ctx, gpxfile) == true) {
599     goto success;
600   } else {
601     if (*(ctx.err) != NULL) {
602       ERROR("BZip2 failure");
603       goto failure;
604     }
605   }
606   
607   if (gpx_parse_plain_file(&ctx, gpxfile) == false) {
608     goto failure;
609   }
610   
611   if (ctx.gpx->goodpoints == 0) {
612     ERROR("Zero good points, %d bad (%d missed time, %d bad lat, %d bad long)",
613           ctx.gpx->badpoints,
614           ctx.gpx->missed_time,
615           ctx.gpx->bad_lat,
616           ctx.gpx->bad_long);
617     if (ctx.gpx->missed_time > ((ctx.gpx->badpoints * 3) >> 2)) {
618       *(ctx.err) = strdup("Found no good GPX points in the input data. At least 75% of the trackpoints lacked a <time> tag.");
619     } else {
620       *(ctx.err) = strdup("Found no good GPX points in the input data");
621     }
622     goto failure;
623   }
624   
625   success:
626   if (ctx.point)
627     free(ctx.point);
628   if (ctx.accumulator != NULL)
629     free(ctx.accumulator);
630   
631   return ctx.gpx;
632   
633   failure:
634   gpx_abort_context(&ctx);
635   return NULL;
636 }
637
638 void
639 gpx_print(GPX *gpx)
640 {
641   GPXTrackPoint *pt;
642   int pointnr;
643   
644   printf("minlat=%ld maxlat=%ld minlon=%ld maxlon=%ld\n",
645          gpx->minlatitude, gpx->maxlatitude,
646          gpx->minlongitude, gpx->maxlongitude);
647   
648   printf("goodpoints=%d badpoints=%d\n",
649          gpx->goodpoints,
650          gpx->badpoints);
651   return;
652   for (pt = gpx->points, pointnr = 1; pt != NULL; pt = pt->next, pointnr++)
653     printf("%4d: lat=%ld lon=%ld ele=%f time=%s seg=%d\n",
654            pointnr, pt->latitude, pt->longitude, pt->elevation,
655            pt->timestamp, pt->segment);
656   
657 }