[mkgmap-dev] some findings about NT format

Fri Apr 15 15:29:03 BST 2022

Hi all,

I think I understand now the various different ways how route arcs are encoded.
For each arc that is connected to the nodeinfo object (we would call it a RouteNode) we find some info.
Sometimes only the flag that there is an arc, sometimes also a bearing value, sometimes
more info to find the destination node. So, we have forward and backward arcs, indirect arcs
and something new that could be called no-dest-arc where the arc end somewhere without
further connections (a dead end).
This is really different compared to the old format.

Observations for "GARMIN  CN Europe NTU 2022.2":
If both bits 0x10 and 0x80 in the nodeinfo flags are clear there is no more information in the arcs bitstream.
This is rarely the case. Almost all flags have the 0x80 bit set. The 0x10 bit probably flags that the node
is part of one or more route restrictions. The corresponding data follows the arcs data.
I've not yet tried to understand it, I hope the data is similar to the old format.

If the 0x80 bit is set we have at least 16 more bits. I see up to 39 more bits, with lots of zero bits and only a few ones.
I still have no clue what they mean, but there are clear patterns.
It seems the "meaningfull" bytes come last. E.g. all nodes where 23 bits are
remaining start with the same sequence of bits 0x9000, for 22 bits all have 0x4800, 21 -> 0x2400 and so on down to 0x120 for 16 bits.
So, the first (n % 8) bits are always 0 and can probably be skipped so that only full bytes are processed.
That leaves only 6 bits which are frequently changing. Up to now it looks like a waste of space
since there are thousands of nodes with almost the same data.

Maybe the bit patterns are different other img files, I've only looked at few and they all show this.
Maybe this information is about the different activities, but I would expect such info on the arc, not only once on the node.

ciao,
Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen at hotmail.com>
Gesendet: Freitag, 8. April 2022 10:09
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] some findings about NT format

Hi,

seems it helped to write down my thoughts yesterday.

a) I was wrong reg. the backward arcs, they still exist. GPXSee reads them but only uses
the direct forward arcs.

b) GPXSee uses NODFile::absAdjInfo() and NODFile::relAdjInfo() . These are both methods to read
what we would call a RouteArc. My current understanding is that "abs"/"rel" refers to the meaning
of the encoded distance. The length value for the "abs" arcs is the length of the (possibly bending) arc
between the two nodes (including the detour), the length of the "rel" arc seems to contain only the delta
to the direct connection.
b) Both methods calculate a "skip" value which is either 4 for 8.
I am now quite sure that the 4/8 bits encode the direct direction from source to dest node
and the data is only written when the road bends between those two nodes.
The relAdjInfo() methods may read another info wich is probably what we call curve info.

ciao,
Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von N Willink <osm at pinns.co.uk>
Gesendet: Donnerstag, 7. April 2022 10:35
An: mkgmap-dev at lists.mkgmap.org.uk
Betreff: Re: [mkgmap-dev] some findings about NT format

Hi Gerd

Thanks for the update. My goodness, you have been 'busy'! Great that you are persisting!

No idea about roundabouts :Perhaps  bridges have weight / height restrictions?

Good luck!

Nick

On 07/04/2022 09:15, Gerd Petermann wrote:

Hi all,

not much progress since march 16 ...
a)  some roads seem to have an additional backward bitstream (class BitStream4R in GPXSee) that precedes the known one. I think all roundabouts have this
with typically only 3 bytes including the length field. Many - if not all - of the other roads seem to be related to bridges or maybe more general roads which are on embankments.
I did not find any flag for this yet. The bytes for a roundabout look like this: [02, 01, 11] , or [03, 01, 11] , [05, 01, 11] ,  [06, 01, 11], so only the last bits differ (bits are read right to left!) ,
maybe there are also tiles with [04, 01, 11] or other values , I only looked at a few so far.
Maybe those of you who often use the City Navigator maps have an idea what additional data the device shows at roundabouts or near bridges?
b) The code in NODFile::linkInfo() is probably not 100% correct. My current understanding is that the bit 0x100 in the flags field
tells us if a nodeOffset exists or not. GPXSee always reads it and sometimes reads even a few more bits than available according to field linkInfoSize.
No problem there because it will never use the wrong value.
In newer maps like CN from August 2021 I see a lot more bits following but I've no clue yet how to interpret them. The number of "unused" bits is constant for the
all linkinfo within one block but differs between the different blocks. Maps from 2012 only have a few unused bits .
The smallest number that I found was just 3, the latest (2021) can have +40. I am pretty sure that the flags in the NOD header have to be used to understand this data.
Very confusing for me is the fact that some blocks have e.g. 70 bits for the linkinfo but the last 8 bits or so are always 0. Looks like a waste of space.
c) It seems that the "backward arcs" are gone. I've collected informtion about the last used bit in GPXSee methods NODFile::relAdjInfo and NODFile::absAdjInfo()
and most nodes have a lot of "unused" (or ignored) data. My first thought was that GPXSee simply ignores backward arcs but it sometimes reads allmost all bits and in other cases only
8 of +200 bits. The latter happens when several roads end at such a node. The few nodes where it reads all data seem all be connected to ferry routes, sometimes on the water,
sometimes the place that would be a "amenity=ferry_terminal" node in OSM. On the other hand many of those "ferry" nodes have many "unused" bits
I've no clue yet about the meaning of the "unused" bits and I also didn't identify the bits which tell us how many there are.
I can only tell after reading the offsets of all nodes.
d) as the name already suggests the method NodFile::adjDistInfo "ignores" some bits which encode the distance between two nodes. At least I see reasonable values when I feed our method
NodFile.rawToMeters() with this data.
e) the 0x80 bit in field NodeInfo.flags also seems to be related to ferry routes. If not set, the node is part of a ferry route. In maps without ferry routes it seems to be always set.

In general it is likely that Garmin didn't change everything when they introduced the NT format. I would expect that the new structures are better compressed, but not completely different in
meaning, and except for the missing backward arcs this seems to be true.
So, we should find data for route restrictions (no-left-turn etc), access restrictions for vehicles, probably also the "indirect arcs" which point to the next road with a higher class
Possibly missing are the bearing values, the road length which was encoded in NET and other data that can be calculated.

Still  a lot to learn...

ciao,
Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk><mailto:mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen at hotmail.com><mailto:gpetermann_muenchen at hotmail.com>
Gesendet: Mittwoch, 16. März 2022 12:47
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] some findings about NT format

Hi all,

OK, some progress :)
I think the bits in NET 5 contain
a) two bits for the label number
b) k bits for the offset into NET4
c) l bits for the index into the list of zip codes in LBL (the index is off by 1)
d) m bits for the index into the list of cities in LBL (the index is off by 1)
The bits have to be read with the BitReader class.
So, NET 5 is fully understood now (unless I find exceptions ;))

The value m (bits for the index into cities) is also needed to interpret another structure in NET4.
This contains further indexes into the list of cities for roads. I've not yet fully understood that structure.
Depending on m there are 1 .. 3 bytes containing the index into the city list OR - if 0x4 is set in that index) -
something completely different. In the latter case the first 1 or two bytes give a number of bytes.
My experimental code is just able to calculate the correct number of bytes.
This structure occurs 0 .. 3 times, maybe up to 7, the flag1 gives that number  with
n=flag1 >> 4 & 0xf. I've only spotted values 0..3 for n so far.

The flag1 bit 0x80 (I call it has80 for now) indicates that one has to read anoter byte flag.
I've spotted values 1,2,4,or 6 in this flag. The value 1 means that the length for another byte array is following
(length is retrieved with readVarLength()) or - shifted by 1 to the right - the number of bytes that build an id.

Still a lot of bits and bytes that I don't understand ...

reg. LBL:
The lists of cities, regions and countries can contain multiple languages. As with name:de=*, name:fr=* etc in OSM.
My current understanding is that the lists are first calculated by sorting the basic (English) names and
after that the entries for further languages - if any -are added after the corresponding english entry. No idea yet
how those extra entries are sorted. Extra bytes give the country code, I've not yet looked at the details.

Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk><mailto:mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen at hotmail.com><mailto:gpetermann_muenchen at hotmail.com>
Gesendet: Freitag, 11. März 2022 21:33
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] some findings about NT format

Hi Nick,

it's time consuming but it's also great to find a simple rule which replaces lots of if-then-else constructs.
I really like this kind of work!
My NET algo parses 99% of the files that I have, so it's not much that is missing.
Only some very small tiles fail. These are so rare that it is difficult to detect
more pattern with statistical methods.
It still needs the NOD data so I now guess there will always be a NOD when there is NET
in a GMP file.
On the other hand I've not found much about the meaning of all the bits and bytes.
So, my next step is probably to modify some bits to find out what they mean for Basecamp.
I've not even found the place that encodes the city or zip code of a road so far...

Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk><mailto:mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von N Willink <osm at pinns.co.uk><mailto:osm at pinns.co.uk>
Gesendet: Freitag, 11. März 2022 12:46
An: mkgmap-dev at lists.mkgmap.org.uk<mailto:mkgmap-dev at lists.mkgmap.org.uk>
Betreff: Re: [mkgmap-dev] some findings about NT format

Hi Gerd

Just to say you're doing a great job ! It must be like one step fw 2 steps back ...

btw hgt2osm is written by Frank, the one who discovered the DEM structure.

Nick

On 11/03/2022 11:00, Gerd Petermann wrote:

Hi all,

I am still struggling with the NET 4 structures.  Whenever I find a pattern I also find exceptions to it ;)

Reg. NET 5:
It is a replacement for NET 3 (sorted roads)
- first two bits give the label number
- next n bits give the offset, n is the minimal number of bits needed to address all bytes in NET 4. Something like this
  n = Integer.numberOfTrailingZeros(Integer.highestOneBit(<bytes in NET 4>)) + 1;
- the remaining bits are not yet clear to me.

Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk><mailto:mkgmap-dev-bounces at lists.mkgmap.org.uk><mailto:mkgmap-dev-bounces at lists.mkgmap.org.uk><mailto:mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen at hotmail.com><mailto:gpetermann_muenchen at hotmail.com><mailto:gpetermann_muenchen at hotmail.com><mailto:gpetermann_muenchen at hotmail.com>
Gesendet: Samstag, 5. März 2022 11:40
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] some findings about NT format

Hi all,

I think today I've now identified most of the structures of the NET file. Quite a lot of fields and bitstreams and I still don't know much about the meaning of them.
Most of the findings described before were correct as long as some more flags are considered, but there is much more. Bit 0x20 in the first flag byte signals another
bunch of possible structures following.

I think this allows to read NET4 without looking at NOD, and there are some roads which are not referenced in RGN (and ignored by GPXSee). They possibly have no extra lines
or the same lines as they preceding road.
I've not yet made up my mind if I can add code to the existing NetDisplay in display tool or if we need a new GmpDisplay program.

Reg. NET5:
Sample from NET header:
000006d9 | 2d 10 1f 00             | NET5 ???, offset 1f102d
000006dd | c4 9d 01 00             | NET5 ???, length 105924
000006e1 | 27 00                   | ???

The header has a record length (0x27 =39)  but that seems to give the number of bits, not bytes. At least I see some patterns when I print the bitstreams with that length.
In general the record size seems to depend on the number of roads, the more roads the larger the record size.
I guess there is a header which tells us what the bits mean. Todo...

ciao,
Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk><mailto:mkgmap-dev-bounces at lists.mkgmap.org.uk><mailto:mkgmap-dev-bounces at lists.mkgmap.org.uk><mailto:mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen at hotmail.com><mailto:gpetermann_muenchen at hotmail.com><mailto:gpetermann_muenchen at hotmail.com><mailto:gpetermann_muenchen at hotmail.com>
Gesendet: Mittwoch, 23. Februar 2022 09:45
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] some findings about NT format

Hi all,

I've identified a few more bytes following the road labels.
If there are labels there is always an additional byte array.
This starts with a length field (varying number of bytes).
First byte in the array is a flag byte, the lower 4 bits each indicate the existance of another byte array with length prefix.
Example:
buf=[1d, 07, 07, 04, 01, 39, 07, 04, 01, 5b, 09, 2a, f1, 46, 66]
1d == 29 -> length 14
07 flag byte
07 1st array length -> 3
array1=[04, 01, 39]
07 2nd array length -> 3
array2=[04, 01, 5b]
09 3rd array length -> 4
array3=[2a, f1, 46, 66]

The top 4 bits are probably also flags. I've not yet understood what they mean, each seems to flag the existence of further bytes, but the number of those bytes vary.
The flag byte might be 0:
buf=[03, 00]

array1 and array2 are more often found for major roads, but also on some minor ones. No idea yet what they mean.
I am pretty sure that array3 contains the house numbers, because this array never shows up on motorways.
Our code to read them doesn't (always) work. It seems to extract the base number correctly but then often fails.
So I guess Garmin has extended the format. Maybe Numbers like 1a,1b are supported now?
Another example:
buf=[11, 84, 09, 2a, 30, 00, 27, 02, 57]
11 (=17) -> length 8
84 flag byte : (only) array4 exists, and 0x80 is set
09 array4 length -> 4
array4=[2a, 30, 00, 27]
The remaining bytes x02,x57 are probably a flag and a counter (or id). The flag probably indicates if the counter fits into one or two bytes.
The counter itself simply increases for all roads with labels and the 0x80 bit in the flag byte set. No idea yet where this is used.

I'll soon have access to a Garmin Nüvi. I hope that allows me to load the map in Mapsource or Basecamp. Maybe this will tell me what
additional data we can find.

Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk><mailto:mkgmap-dev-bounces at lists.mkgmap.org.uk><mailto:mkgmap-dev-bounces at lists.mkgmap.org.uk><mailto:mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <GPetermann_muenchen at hotmail.com><mailto:GPetermann_muenchen at hotmail.com><mailto:GPetermann_muenchen at hotmail.com><mailto:GPetermann_muenchen at hotmail.com>
Gesendet: Mittwoch, 16. Februar 2022 17:45
An: mkgmap-dev at lists.mkgmap.org.uk<mailto:mkgmap-dev at lists.mkgmap.org.uk><mailto:mkgmap-dev at lists.mkgmap.org.uk><mailto:mkgmap-dev at lists.mkgmap.org.uk>
Betreff: [mkgmap-dev] some findings about NT format

Hi all,

my findings so far which are not used / needed in GPXSee. Maybe it helps someone else:
- method linkLabel() could extract further road labels, bit 0x800000 flags the last of up to 4 labels.
- method linkLabel()  extracts a flag, the bit 0x08 in this flag seems to signal a tunnel. No idea yet what the other bits mean.
- the flags field in struct LinkInfo is used like this (netfile.cpp)
        bool firstIsShape = (linkInfo.flags >> 10) & 1;
        bool singleTopology = (linkInfo.flags >> 9) & 1;
        bool hasLevels = (linkInfo.flags >> 11) & 1;
My guesses about the meaning of the lower bits:
        //      int     road_speed = linkInfo.flags  & 7;
        //      bool oneway = (linkInfo.flags >> 3) & 1;
        //      int     road_class = (linkInfo.flags >> 4) & 7;

- The NET header can have two more sections, e.g. I see
00000684 | f6 cb 13 00             | NET5 ???, offset 13cbf6
00000688 | 96 0a 01 00             | NET5 ???, length 68246
0000068c | 23 00                   | ???
0000068e | 8c d6 14 00             | NET6 ???, offset 14d68c
00000692 | 28 05 00 00             | NET6 ???, length 1320
00000696 | 03 00                   | NET6 ??? record size 3
00000698 | 02 00 00 00             | ???

NET6 contains a list of offsets into NET4, they are in sorted order
and each offset points to the byte following the flag byte that is read in  linkLabel()
I see 440 recrods here, and 441 NOD6 records in the corresponding NOD file,
so they are obviously related (field blockIndexId).

I've not yet found where the address info like city name, zip name, and house numbers are
stored. Maybe that's in NET5.

I think in the old non-NT format there is no need to know NOD data to be able to read NET, so
I woulld expect that this is also possible with NT maps.

Gerd
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk<mailto:mkgmap-dev at lists.mkgmap.org.uk><mailto:mkgmap-dev at lists.mkgmap.org.uk><mailto:mkgmap-dev at lists.mkgmap.org.uk>
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk<mailto:mkgmap-dev at lists.mkgmap.org.uk><mailto:mkgmap-dev at lists.mkgmap.org.uk><mailto:mkgmap-dev at lists.mkgmap.org.uk>
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk<mailto:mkgmap-dev at lists.mkgmap.org.uk><mailto:mkgmap-dev at lists.mkgmap.org.uk><mailto:mkgmap-dev at lists.mkgmap.org.uk>
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk<mailto:mkgmap-dev at lists.mkgmap.org.uk><mailto:mkgmap-dev at lists.mkgmap.org.uk><mailto:mkgmap-dev at lists.mkgmap.org.uk>
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk<mailto:mkgmap-dev at lists.mkgmap.org.uk>
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk<mailto:mkgmap-dev at lists.mkgmap.org.uk>
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk<mailto:mkgmap-dev at lists.mkgmap.org.uk>
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev