/[zanavi_public1]/navit/navit/maptool/tile.c
ZANavi

Contents of /navit/navit/maptool/tile.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (show annotations) (download)
Mon Feb 4 17:41:59 2013 UTC (11 years, 1 month ago) by zoff99
File MIME type: text/plain
File size: 16971 byte(s)
new map version, lots of fixes and experimental new features
1 /**
2 * ZANavi, Zoff Android Navigation system.
3 * Copyright (C) 2011-2012 Zoff <zoff@zoff.cc>
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * version 2 as published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the
16 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 */
19
20 /**
21 * Navit, a modular navigation system.
22 * Copyright (C) 2005-2008 Navit Team
23 *
24 * This program is free software; you can redistribute it and/or
25 * modify it under the terms of the GNU General Public License
26 * version 2 as published by the Free Software Foundation.
27 *
28 * This program is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 * GNU General Public License for more details.
32 *
33 * You should have received a copy of the GNU General Public License
34 * along with this program; if not, write to the
35 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
36 * Boston, MA 02110-1301, USA.
37 */
38
39 #define _FILE_OFFSET_BITS 64
40 #define _LARGEFILE_SOURCE
41 #define _LARGEFILE64_SOURCE
42 #include <stdlib.h>
43 #include <glib.h>
44 #include <assert.h>
45 #include <string.h>
46 #include <signal.h>
47 #include <stdio.h>
48 #include <math.h>
49 #include <getopt.h>
50 #include <unistd.h>
51 #include <fcntl.h>
52 #include <sys/stat.h>
53 #include <zlib.h>
54 #include "file.h"
55 #include "item.h"
56 #include "map.h"
57 #include "zipfile.h"
58 #include "main.h"
59 #include "config.h"
60 #include "linguistics.h"
61 #include "plugin.h"
62
63 #include "maptool.h"
64
65 GList *aux_tile_list;
66 struct tile_head *tile_head_root;
67 GHashTable *strings_hash, *tile_hash, *tile_hash2;
68
69 static char* string_hash_lookup(const char* key)
70 {
71 char* key_ptr = NULL;
72
73 if (strings_hash == NULL)
74 {
75 strings_hash = g_hash_table_new(g_str_hash, g_str_equal);
76 }
77
78 if ((key_ptr = g_hash_table_lookup(strings_hash, key)) == NULL)
79 {
80 key_ptr = g_strdup(key);
81 g_hash_table_insert(strings_hash, key_ptr, (gpointer) key_ptr);
82
83 }
84 return key_ptr;
85 }
86
87 static char** th_get_subtile(const struct tile_head* th, int idx)
88 {
89 char* subtile_ptr = NULL;
90 subtile_ptr = (char*) th + sizeof(struct tile_head) + idx * sizeof(char *);
91 return (char**) subtile_ptr;
92 }
93
94 int tile(struct rect *r, char *suffix, char *ret, int max, int overlap, struct rect *tr)
95 {
96 int x0, x2, x4;
97 int y0, y2, y4;
98 int xo, yo;
99 int i;
100 x0 = world_bbox.l.x;
101 y0 = world_bbox.l.y;
102 x4 = world_bbox.h.x;
103 y4 = world_bbox.h.y;
104 for (i = 0; i < max; i++)
105 {
106 x2 = (x0 + x4) / 2;
107 y2 = (y0 + y4) / 2;
108 xo = (x4 - x0) * overlap / 100;
109 yo = (y4 - y0) * overlap / 100;
110 if (contains_bbox(x0, y0, x2 + xo, y2 + yo, r))
111 {
112 strcat(ret, "d");
113 x4 = x2 + xo;
114 y4 = y2 + yo;
115 }
116 else if (contains_bbox(x2 - xo, y0, x4, y2 + yo, r))
117 {
118 strcat(ret, "c");
119 x0 = x2 - xo;
120 y4 = y2 + yo;
121 }
122 else if (contains_bbox(x0, y2 - yo, x2 + xo, y4, r))
123 {
124 strcat(ret, "b");
125 x4 = x2 + xo;
126 y0 = y2 - yo;
127 }
128 else if (contains_bbox(x2 - xo, y2 - yo, x4, y4, r))
129 {
130 strcat(ret, "a");
131 x0 = x2 - xo;
132 y0 = y2 - yo;
133 }
134 else
135 break;
136 }
137 if (tr)
138 {
139 tr->l.x = x0;
140 tr->l.y = y0;
141 tr->h.x = x4;
142 tr->h.y = y4;
143 }
144 if (suffix)
145 strcat(ret, suffix);
146 return i;
147 }
148
149 void tile_bbox(char *tile, struct rect *r, int overlap)
150 {
151 struct coord c;
152 int xo, yo;
153 *r = world_bbox;
154 while (*tile)
155 {
156 c.x = (r->l.x + r->h.x) / 2;
157 c.y = (r->l.y + r->h.y) / 2;
158 xo = (r->h.x - r->l.x) * overlap / 100;
159 yo = (r->h.y - r->l.y) * overlap / 100;
160 switch (*tile)
161 {
162 case 'a':
163 r->l.x = c.x - xo;
164 r->l.y = c.y - yo;
165 break;
166 case 'b':
167 r->h.x = c.x + xo;
168 r->l.y = c.y - yo;
169 break;
170 case 'c':
171 r->l.x = c.x - xo;
172 r->h.y = c.y + yo;
173 break;
174 case 'd':
175 r->h.x = c.x + xo;
176 r->h.y = c.y + yo;
177 break;
178 }
179 tile++;
180 }
181 }
182
183 int tile_len(char *tile)
184 {
185 int ret = 0;
186 while (tile[0] >= 'a' && tile[0] <= 'd')
187 {
188 tile++;
189 ret++;
190 }
191 return ret;
192 }
193
194 static void tile_extend(char *tile, struct item_bin *ib, GList **tiles_list)
195 {
196 struct tile_head *th = NULL;
197 if (debug_tile(tile))
198 {
199 fprintf (stderr,"Tile:Writing %d bytes to '%s' (%p,%p) 0x%x "LONGLONG_FMT"\n", (ib->len+1)*4, tile, g_hash_table_lookup(tile_hash, tile), tile_hash2 ? g_hash_table_lookup(tile_hash2, tile) : NULL, ib->type, item_bin_get_id(ib));
200 }
201 if (tile_hash2)
202 th=g_hash_table_lookup(tile_hash2, tile);
203 if (!th)
204 th=g_hash_table_lookup(tile_hash, tile);
205 if (! th)
206 {
207 th=malloc(sizeof(struct tile_head)+ sizeof( char* ) );
208 assert(th != NULL);
209 // strcpy(th->subtiles, tile);
210 th->num_subtiles=1;
211 th->total_size=0;
212 th->total_size_used=0;
213 th->zipnum=0;
214 th->zip_data=NULL;
215 th->name=string_hash_lookup(tile);
216 *th_get_subtile( th, 0 ) = th->name;
217
218 if (tile_hash2)
219 g_hash_table_insert(tile_hash2, string_hash_lookup( th->name ), th);
220 if (tiles_list)
221 *tiles_list=g_list_append(*tiles_list, string_hash_lookup( th->name ) );
222 processed_tiles++;
223 if (debug_tile(tile))
224 fprintf(stderr,"new '%s'\n", tile);
225 }
226 th->total_size+=ib->len*4+4;
227 if (debug_tile(tile))
228 {
229 fprintf(stderr,"New total size of %s(%p):%d\n", th->name, th, th->total_size);
230 }
231 g_hash_table_insert(tile_hash, string_hash_lookup( th->name ), th);
232 }
233
234 static int tile_data_size(char *tile)
235 {
236 struct tile_head *th;
237 th = g_hash_table_lookup(tile_hash, tile);
238 if (!th)
239 {
240 return 0;
241 }
242 return th->total_size;
243 }
244
245 static int merge_tile(char *base, char *sub)
246 {
247 struct tile_head *thb, *ths;
248 thb = g_hash_table_lookup(tile_hash, base);
249 ths = g_hash_table_lookup(tile_hash, sub);
250 if (!ths)
251 {
252 return 0;
253 }
254 if (debug_tile(base) || debug_tile(sub))
255 fprintf(stderr, "merging '%s'(%p) (%d) with '%s'(%p) (%d)\n", base, thb, thb ? thb->total_size : 0, sub, ths, ths->total_size);
256 if (!thb)
257 {
258 thb = ths;
259 g_hash_table_remove(tile_hash, sub);
260 thb->name = string_hash_lookup(base);
261 g_hash_table_insert(tile_hash, string_hash_lookup(thb->name), thb);
262
263 }
264 else
265 {
266 thb = realloc(thb, sizeof(struct tile_head) + (ths->num_subtiles + thb->num_subtiles) * sizeof(char*));
267 assert(thb != NULL);
268 memcpy(th_get_subtile(thb, thb->num_subtiles), th_get_subtile(ths, 0), ths->num_subtiles * sizeof(char*));
269 thb->num_subtiles += ths->num_subtiles;
270 thb->total_size += ths->total_size;
271 g_hash_table_insert(tile_hash, string_hash_lookup(thb->name), thb);
272 g_hash_table_remove(tile_hash, sub);
273 g_free(ths);
274 }
275 return 1;
276 }
277
278 static gint get_tiles_list_cmp(gconstpointer s1, gconstpointer s2)
279 {
280 return strcmp((char *) s1, (char *) s2);
281 }
282
283 static void get_tiles_list_func(char *key, struct tile_head *th, GList **list)
284 {
285 *list = g_list_prepend(*list, key);
286 }
287
288 static GList *
289 get_tiles_list(void)
290 {
291 GList *ret = NULL;
292 g_hash_table_foreach(tile_hash, (GHFunc) get_tiles_list_func, &ret);
293 ret = g_list_sort(ret, get_tiles_list_cmp);
294 return ret;
295 }
296
297 #if 0
298 static void
299 write_tile(char *key, struct tile_head *th, gpointer dummy)
300 {
301 FILE *f;
302 char buffer[1024];
303 fprintf(stderr,"DEBUG: Writing %s\n", key);
304 strcpy(buffer,"tiles/");
305 strcat(buffer,key);
306 #if 0
307 strcat(buffer,".bin");
308 #endif
309 f=fopen(buffer, "wb+");
310 while (th)
311 {
312 fwrite(th->data, th->size, 1, f);
313 th=th->next;
314 }
315 fclose(f);
316 }
317 #endif
318
319 static void write_item(char *tile, struct item_bin *ib, FILE *reference)
320 {
321 struct tile_head *th;
322 int size;
323
324 th = g_hash_table_lookup(tile_hash2, tile);
325 if (debug_itembin(ib))
326 {
327 fprintf(stderr, "write_item: == START == TILE: %s == File: %p\n", tile, reference);
328 fprintf(stderr, "tile head %p\n", th);
329
330 fprintf(stderr, "== TILE:item_START ==\n");
331 dump_itembin(ib);
332 fprintf(stderr, "== TILE:item_END ==\n");
333 }
334 if (!th)
335 th = g_hash_table_lookup(tile_hash, tile);
336 if (th)
337 {
338 if (debug_itembin(ib))
339 {
340 fprintf(stderr, "Match %s %d %s\n", tile, th->process, th->name);
341 dump_itembin(ib);
342 }
343 if (th->process != 0 && th->process != 1)
344 {
345 fprintf(stderr, "error with tile '%s' of length %d\n", tile, (int) strlen(tile));
346 abort();
347 }
348 if (!th->process)
349 {
350 if (reference)
351 fseek(reference, 8, SEEK_CUR);
352 return;
353 }
354 if (debug_tile(tile))
355 {
356 fprintf(stderr, "Data:Writing %d bytes to '%s' (%p,%p) 0x%x\n", (ib->len + 1) * 4, tile, g_hash_table_lookup(tile_hash, tile), tile_hash2 ? g_hash_table_lookup(tile_hash2, tile) : NULL, ib->type);
357 }
358 size = (ib->len + 1) * 4;
359 if (th->total_size_used + size > th->total_size)
360 {
361 fprintf(stderr, "Overflow in tile %s (used %d max %d item %d)\n", tile, th->total_size_used, th->total_size, size);
362 exit(1);
363 return;
364 }
365 if (reference)
366 {
367 int offset = th->total_size_used / 4;
368 fwrite(&th->zipnum, sizeof(th->zipnum), 1, reference);
369 fwrite(&offset, sizeof(th->total_size_used), 1, reference);
370 }
371 if (th->zip_data)
372 memcpy(th->zip_data + th->total_size_used, ib, size);
373 th->total_size_used += size;
374 }
375 else
376 {
377 fprintf(stderr, "no tile hash found for %s\n", tile);
378 exit(1);
379 }
380 }
381
382 void tile_write_item_to_tile(struct tile_info *info, struct item_bin *ib, FILE *reference, char *name)
383 {
384 if (info->write)
385 write_item(name, ib, reference);
386 else
387 tile_extend(name, ib, info->tiles_list);
388 }
389
390 void tile_write_item_minmax(struct tile_info *info, struct item_bin *ib, FILE *reference, int min, int max)
391 {
392 struct rect r;
393 char buffer[1024];
394 bbox((struct coord *) (ib + 1), ib->clen / 2, &r);
395 buffer[0] = '\0';
396 tile(&r, info->suffix, buffer, max, overlap, NULL);
397 tile_write_item_to_tile(info, ib, reference, buffer);
398 }
399
400 int add_aux_tile(struct zip_info *zip_info, char *name, char *filename, int size)
401 {
402 struct aux_tile *at;
403 GList *l;
404 l = aux_tile_list;
405 while (l)
406 {
407 at = l->data;
408 if (!strcmp(at->name, name))
409 {
410 fprintf(stderr, "exists %s vs %s\n", at->name, name);
411 return -1;
412 }
413 l = g_list_next(l);
414 } at=g_new0(struct aux_tile, 1);
415 at->name = g_strdup(name);
416 at->filename = g_strdup(filename);
417 at->size = size;
418 aux_tile_list = g_list_append(aux_tile_list, at);
419 return zip_add_member(zip_info);
420 }
421
422 int write_aux_tiles(struct zip_info *zip_info)
423 {
424 GList *l = aux_tile_list;
425 struct aux_tile *at;
426 char *buffer;
427 FILE *f;
428 int count = 0;
429
430 while (l)
431 {
432 at = l->data;
433 buffer = malloc(at->size);
434 assert(buffer != NULL);
435 f = fopen(at->filename, "rb");
436 assert(f != NULL);
437 fread(buffer, at->size, 1, f);
438 fclose(f);
439 write_zipmember(zip_info, at->name, zip_get_maxnamelen(zip_info), buffer, at->size);
440 free(buffer);
441 count++;
442 l = g_list_next(l);
443 zip_add_member(zip_info);
444 }
445 return count;
446 }
447
448 static int add_tile_hash(struct tile_head *th)
449 {
450 int idx, len, maxnamelen = 0;
451 char **data;
452
453 #if 0
454 g_hash_table_insert(tile_hash2, string_hash_lookup( th->name ), th);
455 #endif
456 for (idx = 0; idx < th->num_subtiles; idx++)
457 {
458
459 data = th_get_subtile(th, idx);
460
461 if (debug_tile(((char *) data)) || debug_tile(th->name))
462 {
463 fprintf(stderr, "Parent for '%s' is '%s'\n", *data, th->name);
464 }
465
466 g_hash_table_insert(tile_hash2, *data, th);
467
468 len = strlen(*data);
469
470 if (len > maxnamelen)
471 {
472 maxnamelen = len;
473 }
474 }
475 return maxnamelen;
476 }
477
478 int create_tile_hash(void)
479 {
480 struct tile_head *th;
481 int len, maxnamelen = 0;
482
483 tile_hash2 = g_hash_table_new(g_str_hash, g_str_equal);
484 th = tile_head_root;
485 while (th)
486 {
487 len = add_tile_hash(th);
488 if (len > maxnamelen)
489 maxnamelen = len;
490 th = th->next;
491 }
492 return maxnamelen;
493 }
494
495 static void create_tile_hash_list(GList *list)
496 {
497 GList *next;
498 struct tile_head *th;
499
500 tile_hash2 = g_hash_table_new(g_str_hash, g_str_equal);
501
502 next = g_list_first(list);
503 while (next)
504 {
505 th = g_hash_table_lookup(tile_hash, next->data);
506 if (!th)
507 {
508 fprintf(stderr, "No tile found for '%s'\n", (char *) (next->data));
509 }
510 add_tile_hash(th);
511 next = g_list_next(next);
512 }
513 }
514
515 void write_tilesdir(struct tile_info *info, struct zip_info *zip_info, FILE *out)
516 {
517 int idx, len, maxlen;
518 GList *next, *tiles_list;
519 char **data;
520 struct tile_head *th, **last = NULL;
521
522 tiles_list = get_tiles_list();
523 info->tiles_list = &tiles_list;
524 // if (phase == 3)
525 if (!info->write)
526 {
527 create_tile_hash_list(tiles_list);
528 }
529 next = g_list_first(tiles_list);
530 last = &tile_head_root;
531 maxlen = info->maxlen;
532 if (!maxlen)
533 {
534 while (next)
535 {
536 if (strlen(next->data) > maxlen)
537 {
538 maxlen = strlen(next->data);
539 }
540 next = g_list_next(next);
541 }
542 }
543
544 len = maxlen;
545 while (len >= 0)
546 {
547 #if 0
548 fprintf(stderr,"PROGRESS: collecting tiles with len=%d\n", len);
549 #endif
550 next = g_list_first(tiles_list);
551 while (next)
552 {
553 if (strlen(next->data) == len)
554 {
555 th = g_hash_table_lookup(tile_hash, next->data);
556 // if (phase == 3)
557 if (!info->write)
558 {
559 *last = th;
560 last = &th->next;
561 th->next = NULL;
562 th->zipnum = zip_get_zipnum(zip_info);
563 fprintf(out, "%s:%d", (char *) next->data, th->total_size);
564
565 for (idx = 0; idx < th->num_subtiles; idx++)
566 {
567 data = th_get_subtile(th, idx);
568 fprintf(out, ":%s", *data);
569 }
570
571 fprintf(out, "\n");
572 }
573 if (th->name[strlen(info->suffix)])
574 index_submap_add(info, th);
575 zip_add_member(zip_info);
576 processed_tiles++;
577 }
578 next = g_list_next(next);
579 }
580 len--;
581 }
582 if (info->suffix[0] && info->write)
583 {
584 struct item_bin *item_bin = init_item(type_submap, 0);
585 item_bin_add_coord_rect(item_bin, &world_bbox);
586 item_bin_add_attr_range(item_bin, attr_order, 0, 255);
587 item_bin_add_attr_int(item_bin, attr_zipfile_ref, zip_get_zipnum(zip_info) - 1);
588 item_bin_write(item_bin, zip_get_index(zip_info));
589 }
590 }
591
592 void merge_tiles(struct tile_info *info)
593 {
594 struct tile_head *th;
595 char basetile[1024];
596 char subtile[1024];
597 GList *tiles_list_sorted, *last;
598 int i, i_min, len, size_all, size[5], size_min, work_done;
599 long long zip_size;
600
601 do
602 {
603 tiles_list_sorted = get_tiles_list();
604 fprintf(stderr, "PROGRESS: sorting %d tiles\n", g_list_length(tiles_list_sorted));
605 tiles_list_sorted = g_list_sort(tiles_list_sorted, (GCompareFunc) strcmp);
606 fprintf(stderr, "PROGRESS: sorting %d tiles done\n", g_list_length(tiles_list_sorted));
607 last = g_list_last(tiles_list_sorted);
608 zip_size = 0;
609 while (last)
610 {
611 th = g_hash_table_lookup(tile_hash, last->data);
612 zip_size += th->total_size;
613 last = g_list_previous(last);
614 }
615
616 last = g_list_last(tiles_list_sorted);
617 work_done = 0;
618 while (last)
619 {
620 processed_tiles++;
621 len = tile_len(last->data);
622 if (len >= 1)
623 {
624 strcpy(basetile, last->data);
625 basetile[len - 1] = '\0';
626 strcat(basetile, info->suffix);
627 strcpy(subtile, last->data);
628 for (i = 0; i < 4; i++)
629 {
630 subtile[len - 1] = 'a' + i;
631 size[i] = tile_data_size(subtile);
632 }
633 size[4] = tile_data_size(basetile);
634 size_all = size[0] + size[1] + size[2] + size[3] + size[4];
635 if (size_all < 65536 && size_all > 0 && size_all != size[4])
636 {
637 for (i = 0; i < 4; i++)
638 {
639 subtile[len - 1] = 'a' + i;
640 work_done += merge_tile(basetile, subtile);
641 }
642 }
643 else
644 {
645 for (;;)
646 {
647 size_min = size_all;
648 i_min = -1;
649 for (i = 0; i < 4; i++)
650 {
651 if (size[i] && size[i] < size_min)
652 {
653 size_min = size[i];
654 i_min = i;
655 }
656 }
657 if (i_min == -1)
658 break;
659 if (size[4] + size_min >= 65536)
660 break;
661 subtile[len - 1] = 'a' + i_min;
662 work_done += merge_tile(basetile, subtile);
663 size[4] += size[i_min];
664 size[i_min] = 0;
665 }
666 }
667 }
668 last = g_list_previous(last);
669 }
670 g_list_free(tiles_list_sorted);
671 fprintf(stderr, "PROGRESS: merged %d tiles\n", work_done);
672 }
673 while (work_done);
674 }
675
676 struct attr map_information_attrs[32];
677
678 void index_init(struct zip_info *info, int version)
679 {
680 struct item_bin *item_bin;
681 int i;
682 map_information_attrs[0].type = attr_version;
683 map_information_attrs[0].u.num = version;
684 item_bin = init_item(type_map_information, 0);
685 for (i = 0; i < 32; i++)
686 {
687 if (!map_information_attrs[i].type)
688 break;
689 item_bin_add_attr(item_bin, &map_information_attrs[i]);
690 }
691 item_bin_write(item_bin, zip_get_index(info));
692 }
693
694 void index_submap_add(struct tile_info *info, struct tile_head *th)
695 {
696 int tlen = tile_len(th->name);
697 int len = tlen;
698 char index_tile[len + 1 + strlen(info->suffix)];
699 struct rect r;
700 struct item_bin *item_bin;
701
702 strcpy(index_tile, th->name);
703 if (len > 6)
704 len = 6;
705 else
706 len = 0;
707 index_tile[len] = 0;
708 strcat(index_tile, info->suffix);
709 tile_bbox(th->name, &r, overlap);
710
711 item_bin = init_item(type_submap, 0);
712 item_bin_add_coord_rect(item_bin, &r);
713 item_bin_add_attr_range(item_bin, attr_order, (tlen > 4) ? tlen - 4 : 0, 255);
714 item_bin_add_attr_int(item_bin, attr_zipfile_ref, th->zipnum);
715 tile_write_item_to_tile(info, item_bin, NULL, index_tile);
716 }
717

   
Visit the ZANavi Wiki