refactor:maptool:Support 56 bit node IDsR6731

We need it because openstreetmap data recently has passed 2^32 node id value.

Also, running maptool on 32 bit systems won't work at least in following cases:

- a node with osm id=>2^32 is a via member of a turn restriction relation;

- input file has unordered node ids, that's the case, for example, for
overpass turbo exported data.

To avoid confusion, I have disabled maptool build for 32bit systems.

6 files changed, 55 insertions, 36 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 38713bd33..d154e1e6c 100755
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -579,6 +579,10 @@ if (APPLE OR USE_UIKIT)
    set(BUILD_BUNDLE TRUE CACHE BOOLEAN "build an osx bundle")
 endif()
 
+if(CMAKE_SIZEOF_VOID_P LESS 8)
+   set_with_reason(BUILD_MAPTOOL "maptool works only on 64 bit architectures" FALSE)
+endif()
+
 set(LOCALEDIR "${LOCALE_DIR}/locale")
 
 find_program(BZCAT NAMES bzcat)
@@ -589,6 +593,9 @@ if (SAMPLE_MAP)
    elseif(NOT BZCAT)
       cfg_feature(SAMPLE_MAP "downloading binary map because of missing bzcat" TRUE)
       set(DOWNLOAD_SAMPLE_MAP TRUE)
+   elseif(NOT BUILD_MAPTOOL)
+      cfg_feature(SAMPLE_MAP "downloading binary map because maptool compilation is disabled" TRUE)
+      set(DOWNLOAD_SAMPLE_MAP TRUE)
    endif(CMAKE_CROSSCOMPILING)
 endif(SAMPLE_MAP)
 
diff --git a/navit/maptool/maptool.h b/navit/maptool/maptool.h
index 7fde891dd..eca708591 100644
--- a/navit/maptool/maptool.h
+++ b/navit/maptool/maptool.h
@@ -115,11 +115,11 @@ struct item_bin_sink {
 	void *priv_data[8];
 	GList *sink_funcs;
 };
-
+#define NODE_ID_BITS 56
 struct node_item {
-	unsigned int id;
-	char ref_way;
 	struct coord c;
+	unsigned long long int nd_id:NODE_ID_BITS;
+	char ref_way;
 };
 
 struct zip_info;
@@ -131,7 +131,7 @@ struct country_table;
  * Must be at least 64 bit wide because IDs will soon exceed 32 bit.
  */
 typedef unsigned long long int osmid;
-#define OSMID_FMT LONGLONG_FMT
+#define OSMID_FMT ULONGLONG_FMT
 
 /** Files needed for processing a relation. */
 struct files_relation_processing {
@@ -418,3 +418,6 @@ int zip_get_zipnum(struct zip_info *info);
 void zip_set_zipnum(struct zip_info *info, int num);
 void zip_close(struct zip_info *info);
 void zip_destroy(struct zip_info *info);
+
+/* Break compilation on 32 bit architectures, as we're going to cast osmid's to gpointer to use them as keys to GHashTable's */
+struct maptool_force_64 {char s[sizeof(gpointer)<sizeof(osmid)?-1:1];};
diff --git a/navit/maptool/osm.c b/navit/maptool/osm.c
index 131d7f0eb..2b2884977 100644
--- a/navit/maptool/osm.c
+++ b/navit/maptool/osm.c
@@ -120,10 +120,15 @@ char *attr_strings[attr_string_last];
 
 char *osm_types[]={"unknown","node","way","relation"};
 
-#define REF_MARKER (1 << 30)
-#define IS_REF(c) ((c).x == REF_MARKER)
-#define GET_REF(c) ((unsigned)(c).y)
-#define SET_REF(c,ref) do { (c).x = REF_MARKER; (c).y = ref ; } while(0)
+/*
+ * These macros are designed to handle maptool internal node id reference representation. This representation does not leak 
+ * to binfile, so it's safe to change it without breaking binfile binary compatibility.
+ * Currently it keeps low 31 bits in y coordinate and up to 30 high order bits in x coordinate, allowing for 61 bit osm node id in total.
+ */
+#define REF_MARKER (1ull << 30)
+#define IS_REF(c) (((c).x & REF_MARKER)!=0)
+#define GET_REF(c) ((((osmid)(c).x & ~REF_MARKER)<<31) + (c).y )
+#define SET_REF(c,ref) do { (c).x = REF_MARKER | ((osmid)(ref)>>31); (c).y = (osmid)(ref) & 0x7fffffffull; } while(0)
 
 /* Table of country codes with possible is_in spellings. 
  *  Note: If you update this list, check also country array in country.c 
@@ -793,7 +798,7 @@ build_attrmap_line(char *line)
 		kvl=NULL;
 		if (!(idx=(int)(long)g_hash_table_lookup(attr_hash, kv))) {
 			idx=attr_present_count++;
-			g_hash_table_insert(attr_hash, kv, (gpointer)(long)idx);
+			g_hash_table_insert(attr_hash, kv, (gpointer)(long long)idx);
 		}
 		attr_mapping=g_realloc(attr_mapping, sizeof(struct attr_mapping)+(attr_mapping_count+1)*sizeof(int));
 		attr_mapping->attr_present_idx[attr_mapping_count++]=idx;
@@ -1325,8 +1330,9 @@ node_buffer_to_hash(void)
 {
 	int i,count=node_buffer.size/sizeof(struct node_item);
 	struct node_item *ni=(struct node_item *)node_buffer.base;
+
 	for (i = 0 ; i < count ; i++)
-		g_hash_table_insert(node_hash, (gpointer)(long)(ni[i].id), (gpointer)(long)i);
+		g_hash_table_insert(node_hash, (gpointer)(long long)(ni[i].nd_id), (gpointer)(long long)i);
 }
 
 void
@@ -1374,23 +1380,24 @@ osm_add_node(osmid id, double lat, double lon)
       osmid_attr_value=id;
 
       current_node=allocate_node_item_in_buffer();
-      current_node->id=id;
+      dbg_assert(id < ((2ull<<NODE_ID_BITS)-1));
+      current_node->nd_id=id;
       current_node->ref_way=0;
       current_node->c.x=lon*6371000.0*M_PI/180;
       current_node->c.y=log(tan(M_PI_4+lat*M_PI/360))*6371000.0;
       if (! node_hash) {
-	      if (current_node->id > id_last_node) {
-		      id_last_node=current_node->id;
+	      if (current_node->nd_id > id_last_node) {
+		      id_last_node=current_node->nd_id;
 	      } else {
 		      fprintf(stderr,"INFO: Nodes out of sequence (new " OSMID_FMT " vs old " OSMID_FMT "), adding hash\n",
-			(osmid)current_node->id, id_last_node);
+			(osmid)current_node->nd_id, id_last_node);
 		      node_hash=g_hash_table_new(NULL, NULL);
 		      node_buffer_to_hash();
 	      }
       } else
-	      if (!g_hash_table_lookup(node_hash, (gpointer)(long)(current_node->id)))
-		      g_hash_table_insert(node_hash, (gpointer)(long)(current_node->id),
-			  (gpointer)(long)(current_node-(struct node_item *)node_buffer.base));
+	      if (!g_hash_table_lookup(node_hash, (gpointer)(long long)(current_node->nd_id)))
+		      g_hash_table_insert(node_hash, (gpointer)(long long)(current_node->nd_id),
+			  (gpointer)(long long)(current_node-(struct node_item *)node_buffer.base));
 	      else {
                       remove_last_node_item_from_buffer();
 		      nodeid=0;
@@ -1408,28 +1415,28 @@ clear_node_item_buffer(void)
       }
 }
 
-static long long
+static unsigned long long
 node_item_find_index_in_ordered_list(osmid id)
 {
       struct node_item *node_buffer_base=(struct node_item *)(node_buffer.base);
       long long node_count=node_buffer.size/sizeof(struct node_item);
       long long search_step=node_count>4 ? node_count/4 : 1;
       long long search_index=node_count/2;
-      if (node_buffer_base[0].id > id)
+      if (node_buffer_base[0].nd_id > id)
 	      return -1;
-      if (node_buffer_base[node_count-1].id < id)
+      if (node_buffer_base[node_count-1].nd_id < id)
 	      return -1;
-      while (node_buffer_base[search_index].id != id) {
+      while (node_buffer_base[search_index].nd_id != id) {
 #if 0
 	      fprintf(stderr,"search_index=%d node_count=%d search_step=%d id=%d node_buffer_base[search_index].id=%d\n",
 		  search_index, node_count, search_step, id, node_buffer_base[search_index].id);
 #endif
-	      if (node_buffer_base[search_index].id < id) {
+	      if (node_buffer_base[search_index].nd_id < id) {
 		      search_index+=search_step;
 		      if (search_step == 1) {
 			      if (search_index >= node_count)
 				      return -1;
-			      if (node_buffer_base[search_index].id > id)
+			      if (node_buffer_base[search_index].nd_id > id)
 				      return -1;
 		      } else {
 			      if (search_index >= node_count)
@@ -1440,7 +1447,7 @@ node_item_find_index_in_ordered_list(osmid id)
 		      if (search_step == 1) {
 			      if (search_index < 0)
 				      return -1;
-			      if (node_buffer_base[search_index].id < id)
+			      if (node_buffer_base[search_index].nd_id < id)
 				      return -1;
 		      } else {
 			      if (search_index < 0)
@@ -1461,7 +1468,7 @@ node_item_get(osmid id)
       if (node_hash) {
             // Use g_hash_table_lookup_extended instead of g_hash_table_lookup
             // to distinguish a key with a value 0 from a missing key.
-            if (!g_hash_table_lookup_extended (node_hash, (gpointer)(long)(id), NULL,
+            if (!g_hash_table_lookup_extended (node_hash, (gpointer)(id), NULL,
                                            (gpointer)&result_index)) {
                   result_index=-1;
             }
@@ -1755,9 +1762,9 @@ osm_end_way(struct maptool_osm *osm)
 		return;
 
 	if (dedupe_ways_hash) {
-		if (g_hash_table_lookup(dedupe_ways_hash, (gpointer)(long)wayid))
+		if (g_hash_table_lookup(dedupe_ways_hash, (gpointer)(long long)wayid))
 			return;
-		g_hash_table_insert(dedupe_ways_hash, (gpointer)(long)wayid, (gpointer)1);
+		g_hash_table_insert(dedupe_ways_hash, (gpointer)(long long)wayid, (gpointer)1);
 	}
 
 	count=attr_longest_match(attr_mapping_way, attr_mapping_way_count, types, sizeof(types)/sizeof(enum item_type));
@@ -3002,8 +3009,8 @@ write_item_way_subsection_index(FILE *out, FILE *out_index, FILE *out_graph, str
 	idx[0]=item_bin_get_wayid(orig);
 	idx[1]=ftello(out);
 	if (way_hash) {
-		if (!(g_hash_table_lookup_extended(way_hash, (gpointer)(long)idx[0], NULL, NULL)))
-			g_hash_table_insert(way_hash, (gpointer)(long)idx[0], (gpointer)(long)idx[1]);
+		if (!(g_hash_table_lookup_extended(way_hash, (gpointer)(long long)idx[0], NULL, NULL)))
+			g_hash_table_insert(way_hash, (gpointer)(long long)idx[0], (gpointer)(long long)idx[1]);
 	} else {
 		if (!last_id || *last_id != idx[0])
 			dbg_assert(fwrite(idx, sizeof(idx), 1, out_index)==1);
@@ -3067,6 +3074,7 @@ resolve_ways(FILE *in, FILE *out)
 				c[i].x=ni->c.x;
 				c[i].y=ni->c.y;
 			}
+
 		}
 		item_bin_write(ib,out);
 	}
@@ -3122,7 +3130,6 @@ map_resolve_coords_and_split_at_intersections(FILE *in, FILE *out, FILE *out_ind
 	struct item_bin *ib;
 	struct node_item *ni;
 	long long last_id=0;
-
 	processed_nodes=processed_nodes_out=processed_ways=processed_relations=processed_tiles=0;
 	sig_alrm(0);
 	while ((ib=read_item(in))) {
diff --git a/navit/maptool/osm_o5m.c b/navit/maptool/osm_o5m.c
index 1ca3b1c3c..96a5f7ba7 100644
--- a/navit/maptool/osm_o5m.c
+++ b/navit/maptool/osm_o5m.c
@@ -49,12 +49,12 @@ static unsigned long long
 get_uval(unsigned char **p)
 {
 	unsigned char c;
-	long long ret=0;
+	unsigned long long ret=0;
 	int shift=0;
 
 	for (;;) {
 		c=*((*p)++);
-		ret+=((long long)c & 0x7f) << shift;
+		ret+=((unsigned long long)c & 0x7f) << shift;
 		if (!(c & 0x80)) 
 			return ret;
 		shift+=7;
@@ -64,9 +64,9 @@ get_uval(unsigned char **p)
 static unsigned long long
 get_sval(unsigned char **p)
 {
-	long long ret=get_uval(p);
+	unsigned long long ret=get_uval(p);
 	if (ret & 1) {
-		return -((ret >> 1)+1);
+		return -((long long)(ret >> 1)+1);
 	} else {
 		return ret >> 1;
 	}
diff --git a/navit/maptool/osm_relations.c b/navit/maptool/osm_relations.c
index 1ad04a281..591ca7d9d 100644
--- a/navit/maptool/osm_relations.c
+++ b/navit/maptool/osm_relations.c
@@ -135,7 +135,7 @@ relations_process(struct relations *rel, FILE *nodes, FILE *ways)
 {
 	char buffer[128];
 	struct item_bin *ib=(struct item_bin *)buffer;
-	long long *id;
+	osmid *id;
 	struct coord *c=(struct coord *)(ib+1),cn={0,0};
 	struct node_item *ni;
 	GList *l;
@@ -146,7 +146,7 @@ relations_process(struct relations *rel, FILE *nodes, FILE *ways)
 		item_bin_add_attr_longlong(ib, attr_osm_nodeid, 0);
 		id=item_bin_get_attr(ib, attr_osm_nodeid, NULL);
 		while ((ni=read_node_item(nodes))) {
-			*id=ni->id;
+			*id=ni->nd_id;
 			*c=ni->c;
 			l=g_hash_table_lookup(rel->member_hash[0], id);
 			while (l) {
diff --git a/navit/types.h b/navit/types.h
index 987b42a71..b91e01bd8 100644
--- a/navit/types.h
+++ b/navit/types.h
@@ -29,9 +29,11 @@ typedef int32_t s32;
 typedef uint32_t u32;
 
 #ifdef HAVE_API_WIN32_BASE
+#define ULONGLONG_FMT "%I64u"
 #define LONGLONG_FMT "%I64d"
 #define LONGLONG_HEX_FMT "%I64x"
 #else
+#define ULONGLONG_FMT "%llu"
 #define LONGLONG_FMT "%lld"
 #define LONGLONG_HEX_FMT "%llx"
 #endif