path: root/maptool/tile.c

/**
 * Navit, a modular navigation system.
 * Copyright (C) 2005-2008 Navit Team
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * version 2 as published by the Free Software Foundation.
 *
 * This program 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 this program; if not, write to the
 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA  02110-1301, USA.
 */


#define _FILE_OFFSET_BITS 64
#define _LARGEFILE_SOURCE
#define _LARGEFILE64_SOURCE
#include <glib.h>
#include <assert.h>
#include <string.h>
#include <signal.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <getopt.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <zlib.h>
#include "file.h"
#include "item.h"
#include "map.h"
#include "zipfile.h"
#include "main.h"
#include "config.h"
#include "linguistics.h"
#include "plugin.h"
#ifdef HAVE_POSTGRESQL
#include <libpq-fe.h>
#endif

#include "maptool.h"

GList *aux_tile_list;
struct tile_head *tile_head_root;
GHashTable *strings_hash,*tile_hash,*tile_hash2;

static char* string_hash_lookup( const char* key )
{
	char* key_ptr = NULL;

	if ( strings_hash == NULL ) {
		strings_hash = g_hash_table_new(g_str_hash, g_str_equal);
	}

	if ( ( key_ptr = g_hash_table_lookup(strings_hash, key )) == NULL ) {
		key_ptr = g_strdup( key );
		g_hash_table_insert(strings_hash, key_ptr,  (gpointer)key_ptr );

	}
	return key_ptr;
}

static char** th_get_subtile( const struct tile_head* th, int idx )
{
	char* subtile_ptr = NULL;
	subtile_ptr = (char*)th + sizeof( struct tile_head ) + idx * sizeof( char *);
	return (char**)subtile_ptr;
}

int
tile(struct rect *r, char *suffix, char *ret, int max, int overlap, struct rect *tr)
{
	int x0,x2,x4;
	int y0,y2,y4;
	int xo,yo;
	int i;
	x0=world_bbox.l.x;
	y0=world_bbox.l.y;
	x4=world_bbox.h.x;
	y4=world_bbox.h.y;
	for (i = 0 ; i < max ; i++) {
		x2=(x0+x4)/2;
		y2=(y0+y4)/2;
		xo=(x4-x0)*overlap/100;
		yo=(y4-y0)*overlap/100;
		if (     contains_bbox(x0,y0,x2+xo,y2+yo,r)) {
			strcat(ret,"d");
			x4=x2+xo;
			y4=y2+yo;
		} else if (contains_bbox(x2-xo,y0,x4,y2+yo,r)) {
			strcat(ret,"c");
			x0=x2-xo;
			y4=y2+yo;
		} else if (contains_bbox(x0,y2-yo,x2+xo,y4,r)) {
			strcat(ret,"b");
			x4=x2+xo;
			y0=y2-yo;
		} else if (contains_bbox(x2-xo,y2-yo,x4,y4,r)) {
			strcat(ret,"a");
			x0=x2-xo;
			y0=y2-yo;
		} else 
			break;
	}
	if (tr) {
		tr->l.x=x0;
		tr->l.y=y0;
		tr->h.x=x4;
		tr->h.y=y4;
	}
	if (suffix)
		strcat(ret,suffix);
	return i;
}

void
tile_bbox(char *tile, struct rect *r, int overlap)
{
	struct coord c;
	int xo,yo;
	*r=world_bbox;
	while (*tile) {
		c.x=(r->l.x+r->h.x)/2;
		c.y=(r->l.y+r->h.y)/2;
		xo=(r->h.x-r->l.x)*overlap/100;
		yo=(r->h.y-r->l.y)*overlap/100;
		switch (*tile) {
		case 'a':
			r->l.x=c.x-xo;
			r->l.y=c.y-yo;
			break;
		case 'b':
			r->h.x=c.x+xo;
			r->l.y=c.y-yo;
			break;
		case 'c':
			r->l.x=c.x-xo;
			r->h.y=c.y+yo;
			break;
		case 'd':
			r->h.x=c.x+xo;
			r->h.y=c.y+yo;
			break;
		}
		tile++;
	}
}

int
tile_len(char *tile)
{
	int ret=0;
	while (tile[0] >= 'a' && tile[0] <= 'd') {
		tile++;
		ret++;
	}
	return ret;
}

static void
tile_extend(char *tile, struct item_bin *ib, GList **tiles_list)
{
	struct tile_head *th=NULL;
	if (debug_tile(tile))
		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));
	if (tile_hash2)
		th=g_hash_table_lookup(tile_hash2, tile);
	if (!th)
		th=g_hash_table_lookup(tile_hash, tile);
	if (! th) {
		th=malloc(sizeof(struct tile_head)+ sizeof( char* ) );
		assert(th != NULL);
		// strcpy(th->subtiles, tile);
		th->num_subtiles=1;
		th->total_size=0;
		th->total_size_used=0;
		th->zipnum=0;
		th->zip_data=NULL;
		th->name=string_hash_lookup(tile);
		*th_get_subtile( th, 0 ) = th->name;

		if (tile_hash2)
			g_hash_table_insert(tile_hash2, string_hash_lookup( th->name ), th);
		if (tiles_list)
			*tiles_list=g_list_append(*tiles_list, string_hash_lookup( th->name ) );
		processed_tiles++;
		if (debug_tile(tile))
			fprintf(stderr,"new '%s'\n", tile);
	}
	th->total_size+=ib->len*4+4;
	if (debug_tile(tile))
		fprintf(stderr,"New total size of %s(%p):%d\n", th->name, th, th->total_size);
	g_hash_table_insert(tile_hash, string_hash_lookup( th->name ), th);
}

static int
tile_data_size(char *tile)
{
	struct tile_head *th;
	th=g_hash_table_lookup(tile_hash, tile);
	if (! th)
		return 0;
	return th->total_size;
}

static int
merge_tile(char *base, char *sub)
{
	struct tile_head *thb, *ths;
	thb=g_hash_table_lookup(tile_hash, base);
	ths=g_hash_table_lookup(tile_hash, sub);
	if (! ths)
		return 0;
	if (debug_tile(base) || debug_tile(sub))
		fprintf(stderr,"merging '%s'(%p) (%d) with '%s'(%p) (%d)\n", base, thb, thb ? thb->total_size : 0, sub, ths, ths->total_size);
	if (! thb) {
		thb=ths;
		g_hash_table_remove(tile_hash, sub);
		thb->name=string_hash_lookup(base);
		g_hash_table_insert(tile_hash, string_hash_lookup( thb->name ), thb);

	} else {
		thb=realloc(thb, sizeof(struct tile_head)+( ths->num_subtiles+thb->num_subtiles ) * sizeof( char*) );
		assert(thb != NULL);
		memcpy( th_get_subtile( thb, thb->num_subtiles ), th_get_subtile( ths, 0 ), ths->num_subtiles * sizeof( char*) );
		thb->num_subtiles+=ths->num_subtiles;
		thb->total_size+=ths->total_size;
		g_hash_table_insert(tile_hash, string_hash_lookup( thb->name ), thb);
		g_hash_table_remove(tile_hash, sub);
		g_free(ths);
	}
	return 1;
}


static void
get_tiles_list_func(char *key, struct tile_head *th, GList **list)
{
	*list=g_list_prepend(*list, key);
}

static GList *
get_tiles_list(void)
{
	GList *ret=NULL;
	g_hash_table_foreach(tile_hash, (GHFunc)get_tiles_list_func, &ret);
	return ret;
}

#if 0
static void
write_tile(char *key, struct tile_head *th, gpointer dummy)
{
	FILE *f;
	char buffer[1024];
	fprintf(stderr,"DEBUG: Writing %s\n", key);
	strcpy(buffer,"tiles/");
	strcat(buffer,key);
#if 0
	strcat(buffer,".bin");
#endif
	f=fopen(buffer, "wb+");
	while (th) {
		fwrite(th->data, th->size, 1, f);
		th=th->next;
	}
	fclose(f);
}
#endif

static void
write_item(char *tile, struct item_bin *ib, FILE *reference)
{
	struct tile_head *th;
	int size;

	th=g_hash_table_lookup(tile_hash2, tile);
	if (debug_itembin(ib)) {
		fprintf(stderr,"tile head %p\n",th);
	}
	if (! th)
		th=g_hash_table_lookup(tile_hash, tile);
	if (th) {
		if (debug_itembin(ib)) {
			fprintf(stderr,"Match %s %d %s\n",tile,th->process,th->name);
			dump_itembin(ib);
		}
		if (th->process != 0 && th->process != 1) {
			fprintf(stderr,"error with tile '%s' of length %d\n", tile, (int)strlen(tile));
			abort();
		}
		if (! th->process) {
			if (reference) 
				fseek(reference, 8, SEEK_CUR);
			return;
		}
		if (debug_tile(tile))
			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);
		size=(ib->len+1)*4;
		if (th->total_size_used+size > th->total_size) {
			fprintf(stderr,"Overflow in tile %s (used %d max %d item %d)\n", tile, th->total_size_used, th->total_size, size);
			exit(1);
			return;
		}
		if (reference) {
			int offset=th->total_size_used/4;
			fwrite(&th->zipnum, sizeof(th->zipnum), 1, reference);
			fwrite(&offset, sizeof(th->total_size_used), 1, reference);
		}
		if (th->zip_data)
			memcpy(th->zip_data+th->total_size_used, ib, size);
		th->total_size_used+=size;
	} else {
		fprintf(stderr,"no tile hash found for %s\n", tile);
		exit(1);
	}
}

void
tile_write_item_to_tile(struct tile_info *info, struct item_bin *ib, FILE *reference, char *name)
{
	if (info->write)
		write_item(name, ib, reference);
	else
		tile_extend(name, ib, info->tiles_list);
}

void
tile_write_item_minmax(struct tile_info *info, struct item_bin *ib, FILE *reference, int min, int max)
{
	struct rect r;
	char buffer[1024];
	bbox((struct coord *)(ib+1), ib->clen/2, &r);
	buffer[0]='\0';
	tile(&r, info->suffix, buffer, max, overlap, NULL);
	tile_write_item_to_tile(info, ib, reference, buffer);
}

int
add_aux_tile(struct zip_info *zip_info, char *name, char *filename, int size)
{
	struct aux_tile *at;
	GList *l;
	l=aux_tile_list;
	while (l) {
		at=l->data;
		if (!strcmp(at->name, name)) {
			fprintf(stderr,"exists %s vs %s\n",at->name, name);
			return -1;
		}
		l=g_list_next(l);
	}
	at=g_new0(struct aux_tile, 1);
	at->name=g_strdup(name);
	at->filename=g_strdup(filename);
	at->size=size;
	aux_tile_list=g_list_append(aux_tile_list, at);
	return zip_info->zipnum++;
}

int
write_aux_tiles(struct zip_info *zip_info)
{
	GList *l=aux_tile_list;
	struct aux_tile *at;
	char *buffer;
	FILE *f;
	int count=0;
	
	while (l) {
		at=l->data;
		buffer=malloc(at->size);
		assert(buffer != NULL);
		f=fopen(at->filename,"rb");
		assert(f != NULL);
		fread(buffer, at->size, 1, f);
		fclose(f);
		write_zipmember(zip_info, at->name, zip_info->maxnamelen, buffer, at->size);
		free(buffer);
		count++;
		l=g_list_next(l);
		zip_info->zipnum++;
	}
	return count;
}

static int
add_tile_hash(struct tile_head *th)
{
	int idx,len,maxnamelen=0;
	char **data;

#if 0
	g_hash_table_insert(tile_hash2, string_hash_lookup( th->name ), th);
#endif
	for( idx = 0; idx < th->num_subtiles; idx++ ) {

		data = th_get_subtile( th, idx );

		if (debug_tile(((char *)data)) || debug_tile(th->name)) {
			fprintf(stderr,"Parent for '%s' is '%s'\n", *data, th->name);
		}

		g_hash_table_insert(tile_hash2, *data, th);

		len = strlen( *data );

		if (len > maxnamelen) {
			maxnamelen=len;
		}
	}
	return maxnamelen;
}


int
create_tile_hash(void)
{
	struct tile_head *th;
	int len,maxnamelen=0;

	tile_hash2=g_hash_table_new(g_str_hash, g_str_equal);
	th=tile_head_root;
	while (th) {
		len=add_tile_hash(th);
		if (len > maxnamelen)
			maxnamelen=len;
		th=th->next;
	}
	return maxnamelen;
}

static void
create_tile_hash_list(GList *list)
{
	GList *next;
	struct tile_head *th;

	tile_hash2=g_hash_table_new(g_str_hash, g_str_equal);

	next=g_list_first(list);
	while (next) {
		th=g_hash_table_lookup(tile_hash, next->data);
		if (!th) {
			fprintf(stderr,"No tile found for '%s'\n", (char *)(next->data));
		}
		add_tile_hash(th);
		next=g_list_next(next);
	}
}

void
write_tilesdir(struct tile_info *info, struct zip_info *zip_info, FILE *out)
{
	int idx,len,maxlen;
	GList *next,*tiles_list;
	char **data;
	struct tile_head *th,**last=NULL;

	tiles_list=get_tiles_list();
	info->tiles_list=&tiles_list;
	if (phase == 3)
		create_tile_hash_list(tiles_list);
	next=g_list_first(tiles_list);
	last=&tile_head_root;
	maxlen=info->maxlen;
	if (! maxlen) {
		while (next) {
			if (strlen(next->data) > maxlen)
				maxlen=strlen(next->data);
			next=g_list_next(next);
		}
	}
	len=maxlen;
	while (len >= 0) {
#if 0
		fprintf(stderr,"PROGRESS: collecting tiles with len=%d\n", len);
#endif
		next=g_list_first(tiles_list);
		while (next) {
			if (strlen(next->data) == len) {
				th=g_hash_table_lookup(tile_hash, next->data);
				if (phase == 3) {
					*last=th;
					last=&th->next;
					th->next=NULL;
					th->zipnum=zip_info->zipnum;
					fprintf(out,"%s:%d",(char *)next->data,th->total_size);

					for ( idx = 0; idx< th->num_subtiles; idx++ ){
						data= th_get_subtile( th, idx );
						fprintf(out,":%s", *data);
					}

					fprintf(out,"\n");
				}
				if (th->name[strlen(info->suffix)])
					index_submap_add(info, th);
				zip_info->zipnum++;
				processed_tiles++;
			}
			next=g_list_next(next);
		}
		len--;
	}
	if (info->suffix[0] && info->write) {
		item_bin_init(item_bin, type_submap);
		item_bin_add_coord_rect(item_bin, &world_bbox);
		item_bin_add_attr_range(item_bin, attr_order, 0, 255);
		item_bin_add_attr_int(item_bin, attr_zipfile_ref, zip_info->zipnum-1);
		item_bin_write(item_bin, zip_info->index);
	}
}

void
merge_tiles(struct tile_info *info)
{
	struct tile_head *th;
	char basetile[1024];
	char subtile[1024];
	GList *tiles_list_sorted,*last;
	int i,i_min,len,size_all,size[5],size_min,work_done;
	long long zip_size;

	do {
		tiles_list_sorted=get_tiles_list();
		fprintf(stderr,"PROGRESS: sorting %d tiles\n", g_list_length(tiles_list_sorted));
		tiles_list_sorted=g_list_sort(tiles_list_sorted, (GCompareFunc)strcmp);
		fprintf(stderr,"PROGRESS: sorting %d tiles done\n", g_list_length(tiles_list_sorted));
		last=g_list_last(tiles_list_sorted);
		zip_size=0;
		while (last) {
			th=g_hash_table_lookup(tile_hash, last->data);
			zip_size+=th->total_size;
			last=g_list_previous(last);
		}
		last=g_list_last(tiles_list_sorted);
		work_done=0;
		while (last) {
			processed_tiles++;
			len=tile_len(last->data);
			if (len >= 1) {
				strcpy(basetile,last->data);
				basetile[len-1]='\0';
				strcat(basetile, info->suffix);
				strcpy(subtile,last->data);
				for (i = 0 ; i < 4 ; i++) {
					subtile[len-1]='a'+i;
					size[i]=tile_data_size(subtile);
				}
				size[4]=tile_data_size(basetile);
				size_all=size[0]+size[1]+size[2]+size[3]+size[4];
				if (size_all < 65536 && size_all > 0 && size_all != size[4]) {
					for (i = 0 ; i < 4 ; i++) {
						subtile[len-1]='a'+i;
						work_done+=merge_tile(basetile, subtile);
					}
				} else {
					for (;;) {
						size_min=size_all;
						i_min=-1;
						for (i = 0 ; i < 4 ; i++) {
							if (size[i] && size[i] < size_min) {
								size_min=size[i];
								i_min=i;
							}
						}
						if (i_min == -1)
							break;
						if (size[4]+size_min >= 65536)
							break;
						subtile[len-1]='a'+i_min;
						work_done+=merge_tile(basetile, subtile);
						size[4]+=size[i_min];
						size[i_min]=0;
					}
				}
			}
			last=g_list_previous(last);
		}
		g_list_free(tiles_list_sorted);
		fprintf(stderr,"PROGRESS: merged %d tiles\n", work_done);
	} while (work_done);
}

void
index_init(struct zip_info *info, int version)
{
	item_bin_init(item_bin, type_map_information);
	item_bin_add_attr_int(item_bin, attr_version, version);
	item_bin_write(item_bin, info->index);
}

void
index_submap_add(struct tile_info *info, struct tile_head *th)
{
	int tlen=tile_len(th->name);
	int len=tlen;
	char index_tile[len+1+strlen(info->suffix)];
	struct rect r;

	strcpy(index_tile, th->name);
	if (len > 6)
		len=6;
	else
		len=0;
	index_tile[len]=0;
	strcat(index_tile, info->suffix);
	tile_bbox(th->name, &r, overlap);

	item_bin_init(item_bin, type_submap);
	item_bin_add_coord_rect(item_bin, &r);
	item_bin_add_attr_range(item_bin, attr_order, (tlen > 4)?tlen-4 : 0, 255);
	item_bin_add_attr_int(item_bin, attr_zipfile_ref, th->zipnum);
	tile_write_item_to_tile(info, item_bin, NULL, index_tile);
}