vcs.maemo.org Git - navit-package/blob - navit/maptool/tile.c

   1 /**
   2  * Navit, a modular navigation system.
   3  * Copyright (C) 2005-2008 Navit Team
   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 #define _FILE_OFFSET_BITS 64
  22 #define _LARGEFILE_SOURCE
  23 #define _LARGEFILE64_SOURCE
  24 #include <glib.h>
  25 #include <assert.h>
  26 #include <string.h>
  27 #include <signal.h>
  28 #include <stdlib.h>
  29 #include <stdio.h>
  30 #include <math.h>
  31 #include <getopt.h>
  32 #include <unistd.h>
  33 #include <fcntl.h>
  34 #include <sys/stat.h>
  35 #include <zlib.h>
  36 #include "file.h"
  37 #include "item.h"
  38 #include "map.h"
  39 #include "zipfile.h"
  40 #include "main.h"
  41 #include "config.h"
  42 #include "linguistics.h"
  43 #include "plugin.h"
  44 #ifdef HAVE_POSTGRESQL
  45 #include <libpq-fe.h>
  46 #endif
  47
  48 #include "maptool.h"
  49
  50 GList *aux_tile_list;
  51 struct tile_head *tile_head_root;
  52 GHashTable *strings_hash,*tile_hash,*tile_hash2;
  53
  54 static char* string_hash_lookup( const char* key )
  55 {
  56         char* key_ptr = NULL;
  57
  58         if ( strings_hash == NULL ) {
  59                 strings_hash = g_hash_table_new(g_str_hash, g_str_equal);
  60         }
  61
  62         if ( ( key_ptr = g_hash_table_lookup(strings_hash, key )) == NULL ) {
  63                 key_ptr = g_strdup( key );
  64                 g_hash_table_insert(strings_hash, key_ptr,  (gpointer)key_ptr );
  65
  66         }
  67         return key_ptr;
  68 }
  69
  70 static char** th_get_subtile( const struct tile_head* th, int idx )
  71 {
  72         char* subtile_ptr = NULL;
  73         subtile_ptr = (char*)th + sizeof( struct tile_head ) + idx * sizeof( char *);
  74         return (char**)subtile_ptr;
  75 }
  76
  77 int
  78 tile(struct rect *r, char *suffix, char *ret, int max, int overlap, struct rect *tr)
  79 {
  80         int x0,x2,x4;
  81         int y0,y2,y4;
  82         int xo,yo;
  83         int i;
  84         x0=world_bbox.l.x;
  85         y0=world_bbox.l.y;
  86         x4=world_bbox.h.x;
  87         y4=world_bbox.h.y;
  88         for (i = 0 ; i < max ; i++) {
  89                 x2=(x0+x4)/2;
  90                 y2=(y0+y4)/2;
  91                 xo=(x4-x0)*overlap/100;
  92                 yo=(y4-y0)*overlap/100;
  93                 if (     contains_bbox(x0,y0,x2+xo,y2+yo,r)) {
  94                         strcat(ret,"d");
  95                         x4=x2+xo;
  96                         y4=y2+yo;
  97                 } else if (contains_bbox(x2-xo,y0,x4,y2+yo,r)) {
  98                         strcat(ret,"c");
  99                         x0=x2-xo;
 100                         y4=y2+yo;
 101                 } else if (contains_bbox(x0,y2-yo,x2+xo,y4,r)) {
 102                         strcat(ret,"b");
 103                         x4=x2+xo;
 104                         y0=y2-yo;
 105                 } else if (contains_bbox(x2-xo,y2-yo,x4,y4,r)) {
 106                         strcat(ret,"a");
 107                         x0=x2-xo;
 108                         y0=y2-yo;
 109                 } else
 110                         break;
 111         }
 112         if (tr) {
 113                 tr->l.x=x0;
 114                 tr->l.y=y0;
 115                 tr->h.x=x4;
 116                 tr->h.y=y4;
 117         }
 118         if (suffix)
 119                 strcat(ret,suffix);
 120         return i;
 121 }
 122
 123 void
 124 tile_bbox(char *tile, struct rect *r, int overlap)
 125 {
 126         struct coord c;
 127         int xo,yo;
 128         *r=world_bbox;
 129         while (*tile) {
 130                 c.x=(r->l.x+r->h.x)/2;
 131                 c.y=(r->l.y+r->h.y)/2;
 132                 xo=(r->h.x-r->l.x)*overlap/100;
 133                 yo=(r->h.y-r->l.y)*overlap/100;
 134                 switch (*tile) {
 135                 case 'a':
 136                         r->l.x=c.x-xo;
 137                         r->l.y=c.y-yo;
 138                         break;
 139                 case 'b':
 140                         r->h.x=c.x+xo;
 141                         r->l.y=c.y-yo;
 142                         break;
 143                 case 'c':
 144                         r->l.x=c.x-xo;
 145                         r->h.y=c.y+yo;
 146                         break;
 147                 case 'd':
 148                         r->h.x=c.x+xo;
 149                         r->h.y=c.y+yo;
 150                         break;
 151                 }
 152                 tile++;
 153         }
 154 }
 155
 156 int
 157 tile_len(char *tile)
 158 {
 159         int ret=0;
 160         while (tile[0] >= 'a' && tile[0] <= 'd') {
 161                 tile++;
 162                 ret++;
 163         }
 164         return ret;
 165 }
 166
 167 static void
 168 tile_extend(char *tile, struct item_bin *ib, GList **tiles_list)
 169 {
 170         struct tile_head *th=NULL;
 171         if (debug_tile(tile))
 172                 fprintf(stderr,"Tile:Writing %d bytes to '%s' (%p,%p) 0x%x %Ld\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));
 173         if (tile_hash2)
 174                 th=g_hash_table_lookup(tile_hash2, tile);
 175         if (!th)
 176                 th=g_hash_table_lookup(tile_hash, tile);
 177         if (! th) {
 178                 th=malloc(sizeof(struct tile_head)+ sizeof( char* ) );
 179                 assert(th != NULL);
 180                 // strcpy(th->subtiles, tile);
 181                 th->num_subtiles=1;
 182                 th->total_size=0;
 183                 th->total_size_used=0;
 184                 th->zipnum=0;
 185                 th->zip_data=NULL;
 186                 th->name=string_hash_lookup(tile);
 187                 *th_get_subtile( th, 0 ) = th->name;
 188
 189                 if (tile_hash2)
 190                         g_hash_table_insert(tile_hash2, string_hash_lookup( th->name ), th);
 191                 if (tiles_list)
 192                         *tiles_list=g_list_append(*tiles_list, string_hash_lookup( th->name ) );
 193                 processed_tiles++;
 194                 if (debug_tile(tile))
 195                         fprintf(stderr,"new '%s'\n", tile);
 196         }
 197         th->total_size+=ib->len*4+4;
 198         if (debug_tile(tile))
 199                 fprintf(stderr,"New total size of %s(%p):%d\n", th->name, th, th->total_size);
 200         g_hash_table_insert(tile_hash, string_hash_lookup( th->name ), th);
 201 }
 202
 203 static int
 204 tile_data_size(char *tile)
 205 {
 206         struct tile_head *th;
 207         th=g_hash_table_lookup(tile_hash, tile);
 208         if (! th)
 209                 return 0;
 210         return th->total_size;
 211 }
 212
 213 static int
 214 merge_tile(char *base, char *sub)
 215 {
 216         struct tile_head *thb, *ths;
 217         thb=g_hash_table_lookup(tile_hash, base);
 218         ths=g_hash_table_lookup(tile_hash, sub);
 219         if (! ths)
 220                 return 0;
 221         if (debug_tile(base) || debug_tile(sub))
 222                 fprintf(stderr,"merging '%s'(%p) (%d) with '%s'(%p) (%d)\n", base, thb, thb ? thb->total_size : 0, sub, ths, ths->total_size);
 223         if (! thb) {
 224                 thb=ths;
 225                 g_hash_table_remove(tile_hash, sub);
 226                 thb->name=string_hash_lookup(base);
 227                 g_hash_table_insert(tile_hash, string_hash_lookup( thb->name ), thb);
 228
 229         } else {
 230                 thb=realloc(thb, sizeof(struct tile_head)+( ths->num_subtiles+thb->num_subtiles ) * sizeof( char*) );
 231                 assert(thb != NULL);
 232                 memcpy( th_get_subtile( thb, thb->num_subtiles ), th_get_subtile( ths, 0 ), ths->num_subtiles * sizeof( char*) );
 233                 thb->num_subtiles+=ths->num_subtiles;
 234                 thb->total_size+=ths->total_size;
 235                 g_hash_table_insert(tile_hash, string_hash_lookup( thb->name ), thb);
 236                 g_hash_table_remove(tile_hash, sub);
 237                 g_free(ths);
 238         }
 239         return 1;
 240 }
 241
 242
 243 static void
 244 get_tiles_list_func(char *key, struct tile_head *th, GList **list)
 245 {
 246         *list=g_list_prepend(*list, key);
 247 }
 248
 249 static GList *
 250 get_tiles_list(void)
 251 {
 252         GList *ret=NULL;
 253         g_hash_table_foreach(tile_hash, (GHFunc)get_tiles_list_func, &ret);
 254         return ret;
 255 }
 256
 257 #if 0
 258 static void
 259 write_tile(char *key, struct tile_head *th, gpointer dummy)
 260 {
 261         FILE *f;
 262         char buffer[1024];
 263         fprintf(stderr,"DEBUG: Writing %s\n", key);
 264         strcpy(buffer,"tiles/");
 265         strcat(buffer,key);
 266 #if 0
 267         strcat(buffer,".bin");
 268 #endif
 269         f=fopen(buffer, "wb+");
 270         while (th) {
 271                 fwrite(th->data, th->size, 1, f);
 272                 th=th->next;
 273         }
 274         fclose(f);
 275 }
 276 #endif
 277
 278 static void
 279 write_item(char *tile, struct item_bin *ib, FILE *reference)
 280 {
 281         struct tile_head *th;
 282         int size;
 283
 284         th=g_hash_table_lookup(tile_hash2, tile);
 285         if (debug_itembin(ib)) {
 286                 fprintf(stderr,"tile head %p\n",th);
 287         }
 288         if (! th)
 289                 th=g_hash_table_lookup(tile_hash, tile);
 290         if (th) {
 291                 if (debug_itembin(ib)) {
 292                         fprintf(stderr,"Match %s %d %s\n",tile,th->process,th->name);
 293                         dump_itembin(ib);
 294                 }
 295                 if (th->process != 0 && th->process != 1) {
 296                         fprintf(stderr,"error with tile '%s' of length %d\n", tile, (int)strlen(tile));
 297                         abort();
 298                 }
 299                 if (! th->process) {
 300                         if (reference)
 301                                 fseek(reference, 8, SEEK_CUR);
 302                         return;
 303                 }
 304                 if (debug_tile(tile))
 305                         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);
 306                 size=(ib->len+1)*4;
 307                 if (th->total_size_used+size > th->total_size) {
 308                         fprintf(stderr,"Overflow in tile %s (used %d max %d item %d)\n", tile, th->total_size_used, th->total_size, size);
 309                         exit(1);
 310                         return;
 311                 }
 312                 if (reference) {
 313                         int offset=th->total_size_used/4;
 314                         fwrite(&th->zipnum, sizeof(th->zipnum), 1, reference);
 315                         fwrite(&offset, sizeof(th->total_size_used), 1, reference);
 316                 }
 317                 if (th->zip_data)
 318                         memcpy(th->zip_data+th->total_size_used, ib, size);
 319                 th->total_size_used+=size;
 320         } else {
 321                 fprintf(stderr,"no tile hash found for %s\n", tile);
 322                 exit(1);
 323         }
 324 }
 325
 326 void
 327 tile_write_item_to_tile(struct tile_info *info, struct item_bin *ib, FILE *reference, char *name)
 328 {
 329         if (info->write)
 330                 write_item(name, ib, reference);
 331         else
 332                 tile_extend(name, ib, info->tiles_list);
 333 }
 334
 335 void
 336 tile_write_item_minmax(struct tile_info *info, struct item_bin *ib, FILE *reference, int min, int max)
 337 {
 338         struct rect r;
 339         char buffer[1024];
 340         bbox((struct coord *)(ib+1), ib->clen/2, &r);
 341         buffer[0]='\0';
 342         tile(&r, info->suffix, buffer, max, overlap, NULL);
 343         tile_write_item_to_tile(info, ib, reference, buffer);
 344 }
 345
 346 int
 347 add_aux_tile(struct zip_info *zip_info, char *name, char *filename, int size)
 348 {
 349         struct aux_tile *at;
 350         GList *l;
 351         l=aux_tile_list;
 352         while (l) {
 353                 at=l->data;
 354                 if (!strcmp(at->name, name)) {
 355                         fprintf(stderr,"exists %s vs %s\n",at->name, name);
 356                         return -1;
 357                 }
 358                 l=g_list_next(l);
 359         }
 360         at=g_new0(struct aux_tile, 1);
 361         at->name=g_strdup(name);
 362         at->filename=g_strdup(filename);
 363         at->size=size;
 364         aux_tile_list=g_list_append(aux_tile_list, at);
 365         return zip_info->zipnum++;
 366 }
 367
 368 int
 369 write_aux_tiles(struct zip_info *zip_info)
 370 {
 371         GList *l=aux_tile_list;
 372         struct aux_tile *at;
 373         char *buffer;
 374         FILE *f;
 375         int count=0;
 376
 377         while (l) {
 378                 at=l->data;
 379                 buffer=malloc(at->size);
 380                 assert(buffer != NULL);
 381                 f=fopen(at->filename,"rb");
 382                 assert(f != NULL);
 383                 fread(buffer, at->size, 1, f);
 384                 fclose(f);
 385                 write_zipmember(zip_info, at->name, zip_info->maxnamelen, buffer, at->size);
 386                 free(buffer);
 387                 count++;
 388                 l=g_list_next(l);
 389                 zip_info->zipnum++;
 390         }
 391         return count;
 392 }
 393
 394 static int
 395 add_tile_hash(struct tile_head *th)
 396 {
 397         int idx,len,maxnamelen=0;
 398         char **data;
 399
 400 #if 0
 401         g_hash_table_insert(tile_hash2, string_hash_lookup( th->name ), th);
 402 #endif
 403         for( idx = 0; idx < th->num_subtiles; idx++ ) {
 404
 405                 data = th_get_subtile( th, idx );
 406
 407                 if (debug_tile(((char *)data)) || debug_tile(th->name)) {
 408                         fprintf(stderr,"Parent for '%s' is '%s'\n", *data, th->name);
 409                 }
 410
 411                 g_hash_table_insert(tile_hash2, *data, th);
 412
 413                 len = strlen( *data );
 414
 415                 if (len > maxnamelen) {
 416                         maxnamelen=len;
 417                 }
 418         }
 419         return maxnamelen;
 420 }
 421
 422
 423 int
 424 create_tile_hash(void)
 425 {
 426         struct tile_head *th;
 427         int len,maxnamelen=0;
 428
 429         tile_hash2=g_hash_table_new(g_str_hash, g_str_equal);
 430         th=tile_head_root;
 431         while (th) {
 432                 len=add_tile_hash(th);
 433                 if (len > maxnamelen)
 434                         maxnamelen=len;
 435                 th=th->next;
 436         }
 437         return maxnamelen;
 438 }
 439
 440 static void
 441 create_tile_hash_list(GList *list)
 442 {
 443         GList *next;
 444         struct tile_head *th;
 445
 446         tile_hash2=g_hash_table_new(g_str_hash, g_str_equal);
 447
 448         next=g_list_first(list);
 449         while (next) {
 450                 th=g_hash_table_lookup(tile_hash, next->data);
 451                 if (!th) {
 452                         fprintf(stderr,"No tile found for '%s'\n", (char *)(next->data));
 453                 }
 454                 add_tile_hash(th);
 455                 next=g_list_next(next);
 456         }
 457 }
 458
 459 void
 460 write_tilesdir(struct tile_info *info, struct zip_info *zip_info, FILE *out)
 461 {
 462         int idx,len,maxlen;
 463         GList *next,*tiles_list;
 464         char **data;
 465         struct tile_head *th,**last=NULL;
 466
 467         tiles_list=get_tiles_list();
 468         info->tiles_list=&tiles_list;
 469         if (phase == 3)
 470                 create_tile_hash_list(tiles_list);
 471         next=g_list_first(tiles_list);
 472         last=&tile_head_root;
 473         maxlen=info->maxlen;
 474         if (! maxlen) {
 475                 while (next) {
 476                         if (strlen(next->data) > maxlen)
 477                                 maxlen=strlen(next->data);
 478                         next=g_list_next(next);
 479                 }
 480         }
 481         len=maxlen;
 482         while (len >= 0) {
 483 #if 0
 484                 fprintf(stderr,"PROGRESS: collecting tiles with len=%d\n", len);
 485 #endif
 486                 next=g_list_first(tiles_list);
 487                 while (next) {
 488                         if (strlen(next->data) == len) {
 489                                 th=g_hash_table_lookup(tile_hash, next->data);
 490                                 if (phase == 3) {
 491                                         *last=th;
 492                                         last=&th->next;
 493                                         th->next=NULL;
 494                                         th->zipnum=zip_info->zipnum;
 495                                         fprintf(out,"%s:%d",(char *)next->data,th->total_size);
 496
 497                                         for ( idx = 0; idx< th->num_subtiles; idx++ ){
 498                                                 data= th_get_subtile( th, idx );
 499                                                 fprintf(out,":%s", *data);
 500                                         }
 501
 502                                         fprintf(out,"\n");
 503                                 }
 504                                 if (th->name[strlen(info->suffix)])
 505                                         index_submap_add(info, th);
 506                                 zip_info->zipnum++;
 507                                 processed_tiles++;
 508                         }
 509                         next=g_list_next(next);
 510                 }
 511                 len--;
 512         }
 513         if (info->suffix[0] && info->write) {
 514                 item_bin_init(item_bin, type_submap);
 515                 item_bin_add_coord_rect(item_bin, &world_bbox);
 516                 item_bin_add_attr_range(item_bin, attr_order, 0, 255);
 517                 item_bin_add_attr_int(item_bin, attr_zipfile_ref, zip_info->zipnum-1);
 518                 item_bin_write(item_bin, zip_info->index);
 519         }
 520 }
 521
 522 void
 523 merge_tiles(struct tile_info *info)
 524 {
 525         struct tile_head *th;
 526         char basetile[1024];
 527         char subtile[1024];
 528         GList *tiles_list_sorted,*last;
 529         int i,i_min,len,size_all,size[5],size_min,work_done;
 530         long long zip_size;
 531
 532         do {
 533                 tiles_list_sorted=get_tiles_list();
 534                 fprintf(stderr,"PROGRESS: sorting %d tiles\n", g_list_length(tiles_list_sorted));
 535                 tiles_list_sorted=g_list_sort(tiles_list_sorted, (GCompareFunc)strcmp);
 536                 fprintf(stderr,"PROGRESS: sorting %d tiles done\n", g_list_length(tiles_list_sorted));
 537                 last=g_list_last(tiles_list_sorted);
 538                 zip_size=0;
 539                 while (last) {
 540                         th=g_hash_table_lookup(tile_hash, last->data);
 541                         zip_size+=th->total_size;
 542                         last=g_list_previous(last);
 543                 }
 544                 last=g_list_last(tiles_list_sorted);
 545                 work_done=0;
 546                 while (last) {
 547                         processed_tiles++;
 548                         len=tile_len(last->data);
 549                         if (len >= 1) {
 550                                 strcpy(basetile,last->data);
 551                                 basetile[len-1]='\0';
 552                                 strcat(basetile, info->suffix);
 553                                 strcpy(subtile,last->data);
 554                                 for (i = 0 ; i < 4 ; i++) {
 555                                         subtile[len-1]='a'+i;
 556                                         size[i]=tile_data_size(subtile);
 557                                 }
 558                                 size[4]=tile_data_size(basetile);
 559                                 size_all=size[0]+size[1]+size[2]+size[3]+size[4];
 560                                 if (size_all < 65536 && size_all > 0 && size_all != size[4]) {
 561                                         for (i = 0 ; i < 4 ; i++) {
 562                                                 subtile[len-1]='a'+i;
 563                                                 work_done+=merge_tile(basetile, subtile);
 564                                         }
 565                                 } else {
 566                                         for (;;) {
 567                                                 size_min=size_all;
 568                                                 i_min=-1;
 569                                                 for (i = 0 ; i < 4 ; i++) {
 570                                                         if (size[i] && size[i] < size_min) {
 571                                                                 size_min=size[i];
 572                                                                 i_min=i;
 573                                                         }
 574                                                 }
 575                                                 if (i_min == -1)
 576                                                         break;
 577                                                 if (size[4]+size_min >= 65536)
 578                                                         break;
 579                                                 subtile[len-1]='a'+i_min;
 580                                                 work_done+=merge_tile(basetile, subtile);
 581                                                 size[4]+=size[i_min];
 582                                                 size[i_min]=0;
 583                                         }
 584                                 }
 585                         }
 586                         last=g_list_previous(last);
 587                 }
 588                 g_list_free(tiles_list_sorted);
 589                 fprintf(stderr,"PROGRESS: merged %d tiles\n", work_done);
 590         } while (work_done);
 591 }
 592
 593 void
 594 index_init(struct zip_info *info, int version)
 595 {
 596         item_bin_init(item_bin, type_map_information);
 597         item_bin_add_attr_int(item_bin, attr_version, version);
 598         item_bin_write(item_bin, info->index);
 599 }
 600
 601 void
 602 index_submap_add(struct tile_info *info, struct tile_head *th)
 603 {
 604         int tlen=tile_len(th->name);
 605         int len=tlen;
 606         char index_tile[len+1+strlen(info->suffix)];
 607         struct rect r;
 608
 609         strcpy(index_tile, th->name);
 610         if (len > 6)
 611                 len=6;
 612         else
 613                 len=0;
 614         index_tile[len]=0;
 615         strcat(index_tile, info->suffix);
 616         tile_bbox(th->name, &r, overlap);
 617
 618         item_bin_init(item_bin, type_submap);
 619         item_bin_add_coord_rect(item_bin, &r);
 620         item_bin_add_attr_range(item_bin, attr_order, (tlen > 4)?tlen-4 : 0, 255);
 621         item_bin_add_attr_int(item_bin, attr_zipfile_ref, th->zipnum);
 622         tile_write_item_to_tile(info, item_bin, NULL, index_tile);
 623 }