navit/maptool/tile.c

/**
 * ZANavi, Zoff Android Navigation system.
 * Copyright (C) 2011-2012 Zoff <zoff@zoff.cc>
 *
 * 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.
 */

/**
 * 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 NO_GTYPES_ 1

#define _FILE_OFFSET_BITS 64
#define _LARGEFILE_SOURCE
#define _LARGEFILE64_SOURCE
#include <stdlib.h>
#include <glib.h>
#include <assert.h>
#include <string.h>
#include <signal.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"

#include "maptool.h"

#include "version_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 "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));
}
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 gint get_tiles_list_cmp(gconstpointer s1, gconstpointer s2)
{
        return strcmp((char *) s1, (char *) s2);
}

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);
        ret = g_list_sort(ret, get_tiles_list_cmp);
        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, "write_item: == START == TILE: %s == File: %p\n", tile, reference);
                fprintf(stderr, "tile head %p\n", th);

                fprintf(stderr, "== TILE:item_START ==\n");
                dump_itembin(ib);
                fprintf(stderr, "== TILE:item_END   ==\n");
        }
        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_add_member(zip_info);
}

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_get_maxnamelen(zip_info), buffer, at->size);
                free(buffer);
                count++;
                l = g_list_next(l);
                zip_add_member(zip_info);
        }
        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)
        if (!info->write)
        {
                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)
                                if (!info->write)
                                {
                                        *last = th;
                                        last = &th->next;
                                        th->next = NULL;
                                        th->zipnum = zip_get_zipnum(zip_info);
                                        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_add_member(zip_info);
                                processed_tiles++;
                        }
                        next = g_list_next(next);
                }
                len--;
        }
        if (info->suffix[0] && info->write)
        {
                struct item_bin *item_bin = init_item(type_submap, 0);
                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_get_zipnum(zip_info) - 1);
                item_bin_write(item_bin, zip_get_index(zip_info));
        }
}

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);
}


struct attr map_information_attrs[32];

void index_init(struct zip_info *info, int version)
{
        struct item_bin *item_bin;
        int i;

        map_information_attrs[0].type = attr_version;
        map_information_attrs[0].u.num = version;

        map_information_attrs[1].type = attr_map_release;
        map_information_attrs[1].u.str = SVN_VERSION;

        fprintf(stderr, "writing mapversion num:%d str:%s\n", version, SVN_VERSION);

        item_bin = init_item(type_map_information, 0);
        for (i = 0; i < 32; i++)
        {
                if (!map_information_attrs[i].type)
                {
                        break;
                }
                item_bin_add_attr(item_bin, &map_information_attrs[i]);
        }
        item_bin_write(item_bin, zip_get_index(info));
}

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;
        struct item_bin *item_bin;

        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(type_submap, 0);
        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);
}

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